HEXAGONbeta

An Upper Bound Exponent of 0.9999873 for Square-Difference-Free Sets

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.NT — Number Theory

Contributed by Eric Naslund ↗

Version 1 / Nov 13, 2026 / CC BY 4.0

Abstract

Let A⊆{1,…,N}A\subseteq\{1,\ldots,N\} contain no two distinct elements whose difference is a nonzero square, and let s(N)s(N) be the largest possible size of such a set. We prove \[ s(N)\le CN^{0.9999873} \] with an absolute constant CC. A recent preprint of OpenAI proves $s(N)\le CN^{1-\eps}$ for some absolute $\eps>0$. Their proof utilizes a certain average of the Fourier transform over (24!)161(24!)^{161} points, and for the parameter choices displayed there we calculate that they obtained $\eps\approx \exp_{10}(-\exp_{10}(\exp_{10}(5782.77)))$, in the sense that $\log_{10}\log_{10}\log_{10}(1/\eps)\approx5782.77$. We follow the same overall strategy, with new work at almost every quantitative step. The largest gain is the use of 7272 slots (positions at which the Fourier transform is evaluated) in place of (24!)161(24!)^{161}: the exponent is roughly a fixed constant divided by the number of slots, so this alone gains many orders of magnitude, but leaves far less room for loss elsewhere. Other savings come from the local construction at each prime. Small primes are handled jointly rather than one by one; and errors are measured in the actual half-distributions of the laws being compared, not bounded term by term against a product model. Where sums over the primes of a block of Weil-type error terms of size O(p−1/2)O(p^{-1/2}) would be too weak, we prove bounds of order O(p−1)O(p^{-1}) for the same error terms using \'etale cohomology over finite fields (Deligne's theorems and Katz--Sarnak monodromy for families of curves), the representation theory of GL2(Fp)\mathrm{GL}_2(\mathbf F_p), exact counts at p≡3(mod4)p\equiv3\pmod4, and a modular evaluation of Ahlgren and Ono. Dependence in our distributions is controlled by the correlation inequalities of Peyre and Kassabov. The remaining finitely many numerical inequalities are verified by exact computer arithmetic, listed in the appendices; all analytic steps are proved in the text. The companion repository \cite{NaslundUpperRepository2026} contains a partial Lean 4 formalization, totaling over 600,000 lines of lean. It establishes s(N)≤CN0.99999s(N)\le C N^{0.99999}, conditional on five named analytic inputs and explicit numerical hypotheses. This formalizes the most critical parts of the proof.

Provenance statement

This paper was written by Claude Opus 5.5, GPT Astra 6, and Muse Wonder-Full 1.0, under my prompting and supervision. The research was carried out by Claude Opus 5.5, GPT Astra 6, and ChatGPT Pro queries. I tried to have the AIs write a readable and comprehensible introduction that details the differences between this work and OpenAI's work, and the new ideas involved. This includes a dependency diagram showing the structure of the overall proof. In earlier drafts I found the introduction to be incomprehensible, and it was re-written under my supervision multiple times, so I hope these updates (primarily from Muse and Codex) help the reader get a sense of the overall work. I also recommend that the reader utilize their AI assistant of choice to help understand the paper. The proof has undergone several intensive adversarial reviews by GPT Astra 6 and other agents; no errors or gaps were found in those reviews. A Lean 4 formalization totaling over 600,000 lines of lean appears in the companion repository \cite{NaslundUpperRepository2026}. This formalization establishes $s(N)\le C N^{0.99999}$, conditional on five named analytic inputs and explicit numerical hypotheses. This lean code was generated by Claude Opus 5.5 and GPT Astra 6, and covers many of the most critical parts of the proof.

Tools used

OpenAI
CodexVersion Astra 6
Anthropic
Claude OpusVersion 5.5
Meta
MuseVersion Wonder-Full-1.0

References

  1. Scott Ahlgren and Ken Ono, A Gaussian hypergeometric series evaluation and Apéry number congruences , J. reine angew. Math. 518 (2000), 187--212.
  2. Rudolf Ahlswede and Péter Gács, Spreading of sets in product spaces and hypercontraction of the M arkov operator , Ann. Probab. 4 (1976), 925--939.
  3. R. Beigel and W. Gasarch, Square-difference-free sets of size Ω(n0.7334⋯)\Omega(n^{0.7334\cdots}) , 2008, arXiv:0804.4892.arXiv
  4. Michael A. Bennett, Greg Martin, Kevin O'Bryant, and Andrew Rechnitzer, Explicit bounds for primes in arithmetic progressions , Illinois J. Math. 62 (2018), no. 1--4, 427--532, The constants cited here are those of the published version (Table 1, p. 432); arXiv:1802.00085v2 lists different values.arXiv
  5. B. C. Berndt, R. J. Evans, and K. S. Williams, Gauss and J acobi sums , Canadian Mathematical Society Series of Monographs and Advanced Texts, Wiley, 1998.
  6. T. F. Bloom and J. Maynard, A new upper bound for sets with no square differences , Compos. Math. 158 (2022), no. 8, 1777--1798.
  7. Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi, Convergent sequences of dense graphs. I : Subgraph frequencies, metric properties and testing , Adv. Math. 219 (2008), 1801--1851.
  8. Jean Bourgain, On triples in arithmetic progression , Geom. Funct. Anal. 9 (1999), 968--984.
  9. D. Conlon and J. Lee, Finite reflection groups and graph norms , Adv. Math. 315 (2017), 130--165.
  10. Harold Davenport, Multiplicative number theory , 3 ed., Graduate Texts in Mathematics, vol. 74, Springer, New York, 2000, Revised by Hugh L. Montgomery.
Show all 74 referencesShow fewer references
  1. V. H. de la Peña and S. J. Montgomery-Smith, Decoupling inequalities for the tail probabilities of multivariate U -statistics , Ann. Probab. 23 (1995), no. 2, 806--816.
  2. P. Deligne, Cohomologie étale ( SGA 4124\frac12) , Lecture Notes in Mathematics, vol. 569, Springer, Berlin, 1977.
  3. — , La conjecture de W eil. II , Inst. Hautes Études Sci. Publ. Math. (1980), no. 52, 137--252.
  4. Pierre Deligne, La conjecture de W eil. I , Publ. Math. Inst. Hautes Études Sci. 43 (1974), 273--307.
  5. Freeman J. Dyson, Elliott H. Lieb, and Barry Simon, Phase transitions in quantum spin systems with isotropic and nonisotropic interactions , J. Statist. Phys. 18 (1978), 335--383.
  6. Étienne Fouvry, Emmanuel Kowalski, and Philippe Michel, Algebraic trace functions over the primes , Duke Math. J. 163 (2014), no. 9, 1683--1736.
  7. — , Algebraic twists of modular forms and H ecke orbits , Geom. Funct. Anal. 25 (2015), no. 2, 580--657.
  8. Étienne Fouvry, Emmanuel Kowalski, Philippe Michel, and Will Sawin, Bilinear forms with trace functions , arXiv:2511.09459, 2025, v3, 2026.arXiv
  9. J. Fröhlich, R. B. Israel, E. H. Lieb, and B. Simon, Phase transitions and reflection positivity. I . G eneral theory and long range lattice models , Comm. Math. Phys. 62 (1978), no. 1, 1--34.
  10. J. Fröhlich and E. H. Lieb, Phase transitions in anisotropic lattice spin systems , Comm. Math. Phys. 60 (1978), no. 3, 233--267.
  11. Jürg Fröhlich, Barry Simon, and Thomas Spencer, Infrared bounds, phase transitions and continuous symmetry breaking , Comm. Math. Phys. 50 (1976), 79--95.
  12. W. Fulton and J. Harris, Representation theory: A first course , Graduate Texts in Mathematics, vol. 129, Springer, New York, 1991.
  13. H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of S zemerédi on arithmetic progressions , J. Analyse Math. 31 (1977), 204--256.
  14. James Glimm and Arthur Jaffe, Quantum physics: A functional integral point of view , 2 ed., Springer, New York, 1987.
  15. W. Timothy Gowers, A new proof of S zemerédi's theorem , Geom. Funct. Anal. 11 (2001), 465--588.
  16. B. Green and M. Sawhney, New bounds for the F urstenberg-- S árközy theorem , 2025, arXiv:2411.17448.arXiv
  17. A. Grothendieck, Revêtements étales et groupe fondamental ( SGA 1) , Lecture Notes in Mathematics, vol. 224, Springer, Berlin, 1971.
  18. A. Grothendieck et al., Cohomologie ℓ\ell-adique et fonctions LL ( SGA 5) , Lecture Notes in Mathematics, vol. 589, Springer, Berlin, 1977.
  19. Hamed Hatami and Serguei Norine, Undecidability of linear inequalities in graph homomorphism densities , J. Amer. Math. Soc. 24 (2011), 547--565.
  20. Hermann O. Hirschfeld, A connection between correlation and contingency , Proc. Cambridge Philos. Soc. 31 (1935), 520--524.
  21. K. Ireland and M. Rosen, A classical introduction to modern number theory , second ed., Graduate Texts in Mathematics, vol. 84, Springer, 1990.
  22. I. Martin Isaacs, Character theory of finite groups , Academic Press, New York, 1976.
  23. H. Iwaniec and E. Kowalski, Analytic number theory , AMS Colloquium Publications, vol. 53, Amer. Math. Soc., 2004.
  24. M. Kassabov, Subspace arrangements and property T , Groups Geom. Dyn. 5 (2011), no. 2, 445--477, arXiv:0911.1983.arXiv
  25. N. M. Katz, Gauss sums, K loosterman sums, and monodromy groups , Annals of Mathematics Studies, vol. 116, Princeton University Press, Princeton, NJ, 1988.
  26. N. M. Katz and P. Sarnak, Random matrices, F robenius eigenvalues, and monodromy , American Mathematical Society Colloquium Publications, vol. 45, American Mathematical Society, Providence, RI, 1999.
  27. Nicholas M. Katz, Exponential sums and differential equations , Annals of Mathematics Studies, vol. 124, Princeton University Press, Princeton, NJ, 1990.
  28. — , Twisted LL -functions and monodromy , Annals of Mathematics Studies, vol. 150, Princeton University Press, Princeton, NJ, 2002.
  29. — , Moments, monodromy, and perversity: A D iophantine perspective , Annals of Mathematics Studies, vol. 159, Princeton University Press, Princeton, NJ, 2005.
  30. Emmanuel Kowalski, La conjecture de C howla et la conjecture des nombres premiers jumeaux sur Fq[T]\mathbf{F}_q[T] , d'après S awin et S husterman , Séminaire Bourbaki, Vol. 2021/2022, Exp. No. 1193, Société Mathématique de France, Paris, 2022.
  31. Emmanuel Kowalski, Philippe Michel, and Will Sawin, Bilinear forms with K loosterman sums and applications , Ann. of Math. (2) 186 (2017), no. 2, 413--500.
  32. — , Stratification and averaging for exponential sums: bilinear forms with generalized K loosterman sums , Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 21 (2020), 1453--1530.
  33. D. Krachun, Square-difference-free sets beyond the three-quarter barrier , 2026, arXiv:2608.01325.arXiv
  34. M. Lewko, An improved lower bound related to the F urstenberg-- S árközy theorem , Electron. J. Combin. 22 (2015), no. 1, Paper 1.32.
  35. László Lovász, Large networks and graph limits , American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012.
  36. H. L. Montgomery and R. C. Vaughan, The large sieve , Mathematika 20 (1973), no. 2, 119--134.
  37. Ramon E. Moore, R. Baker Kearfott, and Michael J. Cloud, Introduction to interval analysis , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009.
  38. Eric Naslund, sarkozy-upper-bound-0.9999875 : manuscript and partial Lean formalization , 2026, Companion repository. https://github.com/enaslund/sarkozy-upper-bound-0.9999875.link
  39. — , Square-difference-free sets: lattice-recursion, finite-field and extra-digit certificate bounds (v2 records; digit-constrained) , Palomar Registry entry PALOMAR-2026-09-19-000006, version 2, 2026.
  40. — , Square-difference-free sets of exponent 0.75807580.7580758 , Hexagon 2610.00151v1, 2026.
  41. Arnold Neumaier, Interval methods for systems of equations , Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, 1990.
  42. OpenAI , A power saving for square-difference-free sets , 2026, Preprint, September 24, 2026. https://github.com/openai/math/tree/main/preprints/A-power-saving-for-square-difference-free-sets-September-24-2026.link
  43. An explicit power saving for square-difference-free sets , 2026, Preprint; the first version of the present paper, proving s(N)≤CN1−cs(N)\le CN^{1-c} with c=2.939⋅10−15c=2.939\cdot10^{-15}. Sources and certificate in the directory paper/ of the repository that accompanies this paper.
  44. R. Peyre, Tensorizing maximal correlations , 2010, arXiv:1004.1602v2 (monograph, 128 pp.).arXiv
  45. Ilya I. Piatetski-Shapiro, Complex representations of GL(2,K){\rm GL}(2,K) for finite fields KK , Contemporary Mathematics, vol. 16, American Mathematical Society, Providence, RI, 1983.
  46. J. Pintz, W. L. Steiger, and E. Szemerédi, On sets of natural numbers whose difference set contains no squares , J. London Math. Soc. (2) 37 (1988), 219--231.
  47. David J. Platt and Timothy S. Trudgian, The error term in the prime number theorem , Math. Comp. 90 (2021), 871--881.
  48. M. Raynaud, Caractéristique d' E uler-- P oincaré d'un faisceau et cohomologie des variétés abéliennes , Séminaire Bourbaki, Vol.\ 9, Exp.\ 286 (1965), Société Mathématique de France, Paris, 1995, Also in Dix exposés sur la cohomologie des schémas , North-Holland, Amsterdam, 1968, 12--30, pp. 129--147.
  49. Alexander A. Razborov, Flag algebras , J. Symbolic Logic 72 (2007), no. 4, 1239--1282.
  50. Alfréd Rényi, On measures of dependence , Acta Math. Acad. Sci. Hungar. 10 (1959), 441--451.
  51. J. Barkley Rosser and Lowell Schoenfeld, Sharper bounds for the C hebyshev functions θ(x)\theta(x) and ψ(x)\psi(x) , Math. Comp. 29 (1975), 243--269.
  52. Klaus F. Roth, On certain sets of integers , J. London Math. Soc. 28 (1953), 104--109.
  53. I. Z. Ruzsa, Difference sets without squares , Period. Math. Hungar. 15 (1984), no. 3, 205--209.
  54. Tom Sanders, On R oth's theorem on progressions , Ann. of Math. (2) 174 (2011), no. 1, 619--636.
  55. A. Sárközy, On difference sets of sequences of integers. I , Acta Math. Acad. Sci. Hungar. 31 (1978), 125--149.
  56. Will Sawin, Square-root cancellation for sums of factorization functions over squarefree progressions in Fq[t]\mathbf{F}_q[t] , Acta Math. 233 (2024), no. 2, 285--418.
  57. Will Sawin, Arthur Forey, Javier Fresán, and Emmanuel Kowalski, Quantitative sheaf theory , J. Amer. Math. Soc. 36 (2023), no. 3, 653--726.
  58. Will Sawin and Mark Shusterman, On the C howla and twin primes conjectures over Fq[T]\mathbf{F}_q[T] , Ann. of Math. (2) 196 (2022), no. 2, 457--506.
  59. W. M. Schmidt, Equations over finite fields: An elementary approach , Lecture Notes in Mathematics, vol. 536, Springer, 1976.
  60. Jean-Pierre Serre, Linear representations of finite groups , Graduate Texts in Mathematics, vol. 42, Springer, New York, 1977.
  61. Terence Tao and Van H. Vu, Additive combinatorics , Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, 2006.
  62. Robert C. Vaughan, The H ardy-- L ittlewood method , 2 ed., Cambridge Tracts in Mathematics, vol. 125, Cambridge University Press, 1997.
  63. André Weil, On some exponential sums , Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204--207.
  64. — , Numbers of solutions of equations in finite fields , Bull. Amer. Math. Soc. 55 (1949), 497--508.

Version history

  1. v1 · 603 pagesSubmitted by Eric NaslundCorrected before publicationCurrentNov 10, 2026