A power saving in the Furstenberg-Sarkozy theorem (square-difference-free sets)

Let $s(N)$ be the largest size of a set $A\subseteq\{1,\ldots,N\}$ with no two elements differing by a nonzero perfect square. Answering a question of Lovasz, Furstenberg and Sarkozy proved $s(N)=o(N)$ . Quantitative bounds improved through Pintz-Steiger-Szemeredi and Bloom-Maynard to Green and Sawhney's $s(N)\ll N\exp(-c\sqrt{\log N})$ , while Ruzsa-type constructions give $s(N)\gg N^{0.7334}$ . Green and Sawhney asked whether a fixed power saving holds. Is there an absolute $c>0$ with $s(N)\ll N^{1-c}$ ?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Additive combinatorics; Furstenberg-Sarkozy theorem
Posed by: B. Green and M. Sawhney, New bounds for the Furstenberg-Sarkozy theorem (arXiv:2411.17448), Section 1.1; the underlying problem originates with Lovasz
Year posed: 2024
Years open: 2y
Solved: 2026-09-24
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 50 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: absolute $c>0$ , $C$ with $|A|\le CN^{1-c}$ for every square-difference-free $A\subseteq[N]$ ; consequently the square-difference graph on $[N]$ has chromatic number at least $C^{-1}N^c$ . Companions: for an intersective $h$ of degree $k\ge2$ , a power saving $O_h(N^{1-c_k})$ with exponent depending only on $k$ ; and for $h$ with a unit root modulo every modulus, a power saving $C_hN^{1-c_h}$ for differences $h(p)$ at primes. The exponent is tiny and not computed, far from Ruzsa's lower-bound exponent $0.733$ ; the true exponent is not addressed.

What the AI did

Produced by an unreleased internal OpenAI model as part of the openai/math release (pinned commit adc7f12). The release README says results were produced by one fixed procedure averaging about three hours of ChatGPT Pro thinking compute each; this result is not among the README exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored as OpenAI with no human author named. A Lean formalization accompanies it (Comparator challenge SquareDifference).

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction and Theorem 1.1 of the TeX source, read against Green and Sawhney's question as cited. Lean: Comparator challenge SquareDifference, declaration OAI.SquareDifference.power_saving. This challenge is not in lean/formalization.yaml; its JSON config and solution module exist at the pinned commit. Its statement was read here: there exist reals $c>0$ and $C$ such that for every $N\ge1$ every finite set of integers $A\subseteq[1,N]$ with $a-b\ne m^2$ for all $a,b\in A$ and $m\ge1$ has $|A|\le CN^{1-c}$ . That is exactly the headline. Not rebuilt here. The paper says the exponent is extremely small and not computed. The two 5 October companions (intersective polynomials, prime arguments) are not formalized; the prime-argument one depends on a companion zero-free half-plane theorem for Dirichlet L-functions.

A power saving in the Furstenberg-Sarkozy theorem (square-difference-free sets)

What was actually shown

What the AI did

Verification

Sources

Discussion