Square-difference-free sets: the Furstenberg–Sárközy exponent

How large can a set of integers up to $N$ be if no two of its elements differ by a perfect square? The answer is a power $N^{C}$ with $C$ known only to lie between 0.7580758 and $1 - c$ for a tiny unspecified $c > 0$. Both bounds moved in 2026, and lower-bound constructions now come with machine-checked proofs.

Problem

Let $r(N)$ be the largest size of a set $A \subseteq \{1, \dots, N\}$ such that $a - b$ is never a nonzero perfect square for $a, b \in A$. Let $C$ be the least exponent with

$$r(N) \le N^{C + o(1)} \quad (N \to \infty).$$

Determine $C$, or narrow the known range. (Whether $\log r(N) / \log N$ has a limit is itself open.)

Background

Furstenberg (1977, using ergodic theory) and Sárközy (1978) proved independently that $r(N) = o(N)$. Taking multiples of a prime near $\sqrt{N}$ gives $r(N) \ge N^{1/2 - o(1)}$, and Erdős conjectured this was sharp up to polylogarithmic factors; Sárközy and then Ruzsa (1984) disproved that. Ruzsa's construction builds the set digit by digit in a suitable base, and he remarked that $3/4$ looked like the natural barrier of the method. Upper bounds improved many times (Pintz, Steiger and Szemerédi; Bloom and Maynard; Green and Sawhney) but stayed of the form $N^{1 - o(1)}$ until 2026.

What is known

• Upper bound: $C \le 1 - c$ for an absolute constant $c > 0$, the first power saving (OpenAI, preprint dated September 2026, not refereed or formalized); the argument gives no useful numerical value of $c$.
• Lower bounds: $\tfrac12$ (folklore); $\tfrac12\left(1 + \tfrac{\log 7}{\log 65}\right) \approx 0.733077$ (Ruzsa, 1984); $\tfrac12\left(1 + \tfrac{\log 12}{\log 205}\right) \approx 0.733412$ (Beigel and Gasarch, 2008, and independently Lewko, 2015).
• 2026 constructions: $0.752796$ (Krachun, August), the first beyond $3/4$, gluing "Paley chains" modulo several primes by the Chinese remainder theorem; then $0.753742$ (Jones), $0.75806746$ (Naslund), $0.75806770413$ (Jones) and the current record $0.7580758$ (Naslund, October), each of these four with a Lean 4 formalization of the bound. All five are preprints or code repositories, not yet refereed. Naslund remarks that this is close to the limit of the current approach.

What would count as progress

• A construction with exponent above $0.7580758$: the finite components (residue sets, chains, digit codes) and the arithmetic that turns them into an exponent. Checking the components is a finite computation over residues; the recent records also come with Lean proofs, which is the standard to aim for.
• A new kind of construction, since the current method appears to be near saturation.
• An upper bound with an explicit, reasonable value of $c$, or any proof of $C \le 1 - c$ with $c$ that can be computed.

References

1. A. Sárközy, "On difference sets of sequences of integers. I", Acta Mathematica Academiae Scientiarum Hungaricae 31 (1978), 125–149. doi:10.1007/BF01896079
2. I. Z. Ruzsa, "Difference sets without squares", Periodica Mathematica Hungarica 15 (1984), 205–209. doi:10.1007/BF02454169
3. M. Lewko, "An improved lower bound related to the Furstenberg–Sárközy theorem", Electronic Journal of Combinatorics 22 (2015), P1.32. doi:10.37236/4656
4. B. Green and M. Sawhney, "New bounds for the Furstenberg–Sárközy theorem" (2024). arXiv:2411.17448
5. D. Krachun, "Square-difference-free sets beyond the three-quarter barrier" (2026). arXiv:2608.01325

Source

Imported from Optimization Constants in Mathematics, constant 4b, curated by Terence Tao and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.