Square-difference-free sets of exponent 0.7580758

Eric Naslund

Square-difference-free sets of exponent 0.7580758

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

Contributed by Eric Naslund ↗

Version 1 / Oct 08, 2026 / CC BY 4.0

Abstract

Let

D(N)

be the largest cardinality of a subset of

\{1,\ldots,N\}

containing no two elements whose difference is a nonzero perfect square. We give a computer-assisted construction proving

D(N)\ge N^{0.7580758318008816-o(1)}

, improving the exponent

0.752796455874514\ldots

of Krachun's ranked-block construction. The residues we use carry subintervals of

[0,1]

that are ordered along every modular square difference. A finite stopping-word argument shows that if finitely many such alphabets, in pairwise coprime perfect-square moduli, have interval moments whose contributions sum to more than

\alpha

, then

\alpha

is an attainable exponent. Krachun's prime chains reproduce his exponent in this framework. The gain comes from an alphabet modulo a power of

4

, built by a

25

-state recursion, and from two composite alphabets, at the primes

5,43

and at

19,23

, in which the first differing digit is read separately at each prime. The numerical conclusion is computer-assisted. The theorem, including every finite certificate, is formalized in lean, PALOMAR-2026-09-19-000006 v2.

Provenance statement

This paper was written by GPT-6-Astra and revised by Claude Opus 5.5 under my prompting and supervision. The core argument I understand well, but have not carefully read some of the optimizations, and why the AI believes that this is the limit of the method through exhaustive searching.

FormalizationsPalomar

Tools used

Anthropic: Claude OpusVersion 5.5
OpenAI: ChatGPTVersion Astra 6

References

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions , J. Analyse Math. 31 (1977), 204--256. https://doi.org/10.1007/BF02813304 doi:10.1007/BF02813304 .DOI
A. Sárközy, On difference sets of sequences of integers. I , Acta Math. Acad. Sci. Hungar. 31 (1978), no. 1--2, 125--149. https://doi.org/10.1007/BF01896079 doi:10.1007/BF01896079 .DOI
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), no. 2, 219--231. https://doi.org/10.1112/jlms/s2-37.2.219 doi:10.1112/jlms/s2-37.2.219 .DOI
T. F. Bloom and J. Maynard, A new upper bound for sets with no square differences , Compos. Math. 158 (2022), no. 8, 1777--1798. https://doi.org/10.1112/S0010437X22007679 doi:10.1112/S0010437X22007679 .DOI
B. Green and M. Sawhney, New bounds for the Furstenberg--Sárközy theorem , 2025, https://arxiv.org/abs/2411.17448v2 arXiv:2411.17448v2 (first version 2024).arXiv
I. Z. Ruzsa, Difference sets without squares , Period. Math. Hungar. 15 (1984), no. 3, 205--209. https://doi.org/10.1007/BF02454169 doi:10.1007/BF02454169 .DOI
R. Beigel and W. Gasarch, Square-difference-free sets of size $(n^ 0.7334 )$ , 2008, https://arxiv.org/abs/0804.4892v3 arXiv:0804.4892v3 .arXiv
M. Lewko, An improved lower bound related to the Furstenberg--Sárközy theorem , Electron. J. Combin. 22 (2015), no. 1, Paper 1.32, 6 pp. https://doi.org/10.37236/4656 doi:10.37236/4656 .DOI
M. R. Gabdullin, Sets in $Z_m$ whose difference sets avoid squares , Sb. Math. 209 (2018), no. 11, 1603--1610. https://doi.org/10.1070/SM8992 doi:10.1070/SM8992 .DOI
B. Georgiev, J. Gómez-Serrano, T. Tao, and A. Z. Wagner, Mathematical exploration and discovery at scale , 2025, https://arxiv.org/abs/2511.02864v1 arXiv:2511.02864v1 .arXiv
E. Naslund, Paley graphs and Sárközy's theorem in function fields , 2022, https://arxiv.org/abs/2203.01293v3 arXiv:2203.01293v3 , Conjecture 13.arXiv
JD Jones, ns-lean: Naslund's Conjecture 13 is false at $q=3$ , $k=2$ , for every $n$ congruent to $0$ mod $4$ with $n 8$ , Palomar, entry https://palomar-registry.org/entry?id=PALOMAR-2026-09-17-000003&version=1 PALOMAR-2026-09-17-000003 , version 1, 17 September 2026.link
D. Krachun, Square-difference-free sets beyond the three-quarter barrier , 2026, https://arxiv.org/abs/2608.01325v1 arXiv:2608.01325v1 .arXiv
S. Satake, On the restricted isometry property of the Paley matrix , Linear Algebra Appl. 631 (2021), 35--47. https://doi.org/10.1016/j.laa.2021.08.018 doi:10.1016/j.laa.2021.08.018 .DOI
L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in Automated Deduction---CADE 28 , A. Platzer and G. Sutcliffe (eds.), Lecture Notes in Computer Science 12699 , Springer, Cham, 2021, 625--635. https://doi.org/10.1007/978-3-030-79876-5_37 doi:10.1007/978-3-030-79876-5_37 .DOI
The mathlib Community, The Lean mathematical library , in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020) , Association for Computing Machinery, New York, 2020, 367--381. https://doi.org/10.1145/3372885.3373824 doi:10.1145/3372885.3373824 .DOI
T. M. Cover and J. A. Thomas, Elements of Information Theory , second ed., Wiley-Interscience, Hoboken, NJ, 2006. https://doi.org/10.1002/047174882X doi:10.1002/047174882X .DOI
R. P. Stanley, Two poset polytopes , Discrete Comput. Geom. 1 (1986), 9--23. https://doi.org/10.1007/BF02187680 doi:10.1007/BF02187680 .DOI
E. Seneta, Non-negative Matrices and Markov Chains , second ed., Springer Series in Statistics, Springer, New York, 1981, reprinted 2006. https://doi.org/10.1007/0-387-32792-4 doi:10.1007/0-387-32792-4 .DOI
R. E. Moore, R. B. Kearfott, and M. J. Cloud, Introduction to Interval Analysis , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2009. https://doi.org/10.1137/1.9780898717716 doi:10.1137/1.9780898717716 .DOI

Version history

v1Submitted by Eric NaslundInitial depositCurrentOct 07, 2026