A power saving in Sárközy's theorem on square differences
By the Furstenberg–Sárközy theorem a subset of $\{1, \dots, N\}$ of positive density has two elements differing by a nonzero square. Green and Sawhney showed that $|A| > N \exp(-c \sqrt{\log N})$ suffices. In the other direction, Ruzsa's construction shows that the exponent $c$ below cannot exceed $0.267$. For $p - 1$, $p$ prime, in place of squares, Green proved a bound of the form $|A| \ll N^{1 - c}$.
Problem. Is there $c > 0$ such that, for all sufficiently large $N$, every $A \subset \{1, \dots, N\}$ with $|A| \ge N^{1 - c}$ has $A - A$ containing a nonzero square?
Source: A. Sárközy, On difference sets of sequences of integers (1978), for the problem of square differences; the power saving is asked in B. Green, 100 open problems (version of January 2026), Problem 65.
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- NT — Number Theory
- Secondary
- CO
- Keywords
- additive combinatorics, Furstenberg–Sárközy theorem, square differences
- Literature checked
- Nov. 3, 2026 by clemens-admin
References
@article{sarkozy1978difference,
author = {S{\'a}rk{\"o}zy, A.},
title = {On difference sets of sequences of integers. {I}},
journal = {Acta Mathematica Academiae Scientiarum Hungaricae},
volume = {31},
number = {1-2},
pages = {125--149},
year = {1978},
doi = {10.1007/BF01896079}
}
@article{ruzsa1984squares,
author = {Ruzsa, I. Z.},
title = {Difference sets without squares},
journal = {Periodica Mathematica Hungarica},
volume = {15},
pages = {205--209},
year = {1984}
}
@article{bloommaynard2022squares,
author = {Bloom, Thomas F. and Maynard, James},
title = {A new upper bound for sets with no square differences},
journal = {Compositio Mathematica},
volume = {158},
number = {8},
pages = {1777--1798},
year = {2022},
doi = {10.1112/S0010437X22007679}
}
@misc{greensawhney2024furstenberg,
author = {Green, Ben and Sawhney, Mehtaab},
title = {New bounds for the {F}urstenberg--{S}{\'a}rk{\"o}zy theorem},
year = {2024},
eprint = {2411.17448},
archivePrefix = {arXiv}
}
@article{green2023shiftedprimes,
author = {Green, Ben},
title = {On {S}{\'a}rk{\"o}zy's theorem for shifted primes},
journal = {Journal of the American Mathematical Society},
year = {2023},
doi = {10.1090/jams/1036}
}
@misc{fanlott2026vandercorput,
author = {Fan, Steve and Lott, Andrew},
title = {The optimal van der {C}orput property for squares},
year = {2026},
eprint = {2610.07765},
archivePrefix = {arXiv}
}
@misc{openai2026squares,
author = {{OpenAI}},
title = {A power saving for square-difference-free sets},
howpublished = {\url{https://github.com/openai/math/blob/4eaee87548250b2682affda7d05d947c05554bae/preprints/A-power-saving-for-square-difference-free-sets-September-24-2026/paper.pdf}},
note = {AI-generated, unrefereed; dated 24 September 2026},
year = {2026}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 65; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
We prove that there are absolute constants $c>0$ and $C<\infty$ such that every set $A\subseteq\{1,\ldots,N\}$ with no nonzero square difference satisfies $|A|\le C N^{1-c}$. This answers the fixed-power question posed by Green and Sawhney.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-11-08 | Needs verification → Solution claimed | — | Recorded here: math @ 4eaee87, build/main.tex. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01139, "A power saving in Sárközy's theorem on square differences", clopen.solutions.