Furstenberg–Sárközy exponent for square-difference-free sets
Description of constant
Let $r(N)$ be the maximum size of a subset $A\subset{1,\dots,N}$ with no non-zero square differences $a-b=n^2$.Then $C_{4b}$ is the least constant such that $r(N) \leq N^{C_{4b}+o(1)}$.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $\tfrac12$ | Trivial / folklore (see [BG2008]) | Can use an arithmetic progression of spacing $p \asymp \sqrt{N}$ |
| $\frac12!\left(1+\frac{\log 7}{\log 65}\right)\approx 0.733077$ | [Ruz1984] | Base-expansion construction |
| $\frac12!\left(1+\frac{\log 12}{\log 205}\right)\approx 0.733412$ | [Lew2015] | Improves modulus and residue set in base expansion |
Additional comments and links
- Many non-trivial upper bounds on $r(N)$ [F1977],[Sar1978],[PSS1988],[BM2021],[GS2025], but unfortunately these bounds have not yet improved the trivial upper bound $C_{4b} \leq 1$.
- The limit $\lim_{N\to\infty} \frac{\log r(N)}{\log N}$ is conjectured to exist [Ruz1984]. This remains open.
- Extensions to other polynomials are discussed in [Rice2019].
- A survey of this problem can be found in [Wol2005].
References
- [F1977] Furstenberg, H. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. Analyse Math. 31 (1977), 204–256. DOI: 10.1007/BF02813304.
- [Sar1978] Sárközy, A. On difference sets of sequences of integers. I. Acta Math. Acad. Sci. Hungar. 31 (1978), 125–149. Available at https://renyi.hu/~p_erdos/1978-19a.pdf
- [PSS1988] Pintz, J.; Steiger, W. L.; Szemerédi, E. On sets of natural numbers whose difference set contains no squares. J. London Math. Soc. (2) 37 (1988), 219–231. DOI: 10.1112/jlms/s2-37.2.219
- [Wol2005] Wolf, J. Sets whose difference set is square-free. 2005. Available at https://www.cs.umd.edu/~gasarch/TOPICS/vdw/wolfsq.pdf
- [BM2021] Bloom, T. F.; Maynard, J. A new upper bound for sets with no square differences. 2021. arXiv:2011.13266
- [GS2025] Green, B.; Sawhney, M. New bounds for the Furstenberg–Sárközy theorem. 2025. arXiv:2411.17448
- [Ruz1984] Ruzsa, I. Z. Difference sets without squares. Period. Math. Hungar. 15 (1984), 205–209. Available at https://www.cs.umd.edu/~gasarch/TOPICS/vdw/sqdiff-ruzsa.pdf
- [Lew2015] Lewko, M. An improved lower bound related to the Furstenberg–Sárközy theorem. Electron. J. Combin. 22 (1) (2015), Paper P1.32. DOI: 10.37236/4656
- [Rice2019] Rice, A. A maximal extension of the best-known bounds for the Furstenberg–Sárközy theorem. Acta Arith. 187 (2019), 1–41. DOI: 10.4064/aa170828-26-8
- [BG2008] Beigel, R.; Gasarch, W. Square-Difference-Free Sets of Size (\Omega(n^{0.7334\ldots})). 2008. arXiv:0804.4892
Contribution notes
ChatGPT 5.2 Pro was used to produce was used to prepare an initial version of this page.