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  
$1 - c$ for an absolute constant $c > 0$ [OAI2026] Power saving: every square-difference-free $A \subseteq \{1, \dots, N\}$ satisfies $\lvert A \rvert \le C N^{1-c}$ with absolute constants $c > 0$ and $C < \infty$ (Theorem 1.1), answering the fixed-power question of [GS2025]. The argument does not give a useful numerical value of $c$. According to Naslund, Claude Opus 5.5 extracted an explicit value from this argument $c \approx 10^{-10^{10^{5782.8}}}$, that is, $\log_{10}\log_{10}(1/c) \approx 5.8 \times 10^{5782}$.

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$ [BG2008] Base-expansion with modulus $205$ and residue set $S={0,2,8,14,77,79,85,96,103,109,111,181}$ (Theorem 3.7). The same exponent was published independently in [Lew2015]
$\approx 0.752796$ [Kra2026] First bound past $3/4$: ten Paley chains (tuples in $\mathbb{F}_p$, $p \equiv 3 \pmod 4$, every forward difference a nonzero square) at $p = 3, 7, 11, 19, 23, 31, 43, 59, 71, 103$ of lengths $t = 2, 3, 4, 5, 5, 7, 7, 9, 9, 11$, glued by CRT; $\alpha^\star = \big(\sum_i \log(p_i t_i)/\log t_i\big) \big/ \big(1 + 2\sum_i \log p_i/\log t_i\big)$.
$\approx 0.753742$ [Jon2026a] Krachun’s gluing over eleven blocks: his nine chains with $p \neq 23$, plus two acyclic square-difference digraphs on square-free composite moduli (any nonzero $z^2 \bmod m$ counts as a square) — on $235$ the residues $\{0, 22, 50, 64, 67, 73, 92, 110, 112, 126, 136, 148, 155, 189, 193, 196, 224\}$ (size $17$, longest path $H = 11$) and on $299$ the residues $\{7, 21, 25, 40, 46, 78, 83, 116, 153, 161, 165, 206, 207, 210, 212, 244, 264, 289, 292\}$ (size $19$, $H = 12$); a chain of length $t$ has $H = t$. Lifted to even-digit blocks by one new lemma; $\alpha_\infty = \big(\sum_i \log(m_i t_i)/\log H_i\big) \big/ \big(1 + 2\sum_i \log m_i/\log H_i\big) = 0.753741541837329405\ldots$. Lean 4 formalization (fs-formal, commit 4e79656; Palomar PALOMAR-2026-08-26-000004) certifies the liminf statement and $0.7537 < \alpha_\infty$.
$0.75806746$ (exact $37903373/50000000$) [Nas2026a] Interval-moment criterion: each digit $x$ of a component carries an ordered interval $[a_x, a_x + w_x]$ (a modular square edge $x \to y$ needs $a_x + w_x \le a_y$), and a component in square base $b$ enters with a moment power $f$ satisfying $\sum_x w_x^{f} \ge b^{\alpha}$; the exponent $\alpha$ is attained once $\sum_i f_i > \alpha$. Nine components in pairwise coprime bases: Paley chains at $p = 3, 7, 11, 31, 59, 103$ (lengths $2, 3, 4, 7, 9, 11$; bases $p^2$), two composite codes with three restricted digits per prime coordinate at $215^6 = (5 \cdot 43)^6$ and $437^6 = (19 \cdot 23)^6$, and a 25-state recursion at the prime $2$ (base $4^{10^{10}}$, moment power $0.154942\ldots$, the largest single contribution); $\sum_i f_i - \alpha = 25671/10^{12}$. Not an asserted optimum of the method. Lean 4 formalization of the criterion and of the full value, registered as Palomar entry PALOMAR-2026-09-19-000006, version 1 (standard axioms only; exact rational checks by decide +kernel); papers and stdlib certificate programs in the repository, not on arXiv at the time of writing.
$0.75806770413$ (exact $75806770413/10^{11}$) [Jon2026b] Naslund’s criterion and components, reallocated: the same nine pairwise coprime components — Paley chains at $p = 3, 7, 11, 31, 59, 103$ (lengths $2, 3, 4, 7, 9, 11$, equal widths $1/t$ on one digit, the other digit free), the two composite three-low-digit codes at $215^6$ and $437^6$ ($4913$ and $19683$ retained words, free multiplicities $215^3$ and $437^3$), and the 25-state binary recursion with its transition rules unchanged (depth $10^{15}$, new rational row weights, certified growth factor $a = 1430119207986461/(5 \cdot 10^{14})$ with $\log_2 a > 2\alpha$) — with several retained words of the $19 \cdot 23$ code replaced, intervals repositioned, rational widths changed, and all nine moment powers reallocated: $f = 0.15494199\ldots$ (binary), $0.18194473\ldots, 0.08579838\ldots, 0.10723242\ldots, 0.08916535\ldots, 0.04217280\ldots, 0.00239690\ldots$ (chains), $0.02653617\ldots, 0.06787893\ldots$ (codes); $\sum_i f_i - \alpha = 38652/10^{15}$. The bound is unconditional with an explicit constant, $r(N) \ge c\,N^{\alpha}$ for every $N \ge 1$, from a criterion proved for every $k \ge 1$ (the same repository gives $D_4(N) \ge c\,N^{0.9142}$ and $D_6(N) \ge c\,N^{0.95295}$ for fourth- and sixth-power differences). Not an asserted optimum of the method. Lean 4 formalization of the criterion and of the full value, registered as Palomar entry PALOMAR-2026-09-21-000004 (standard axioms only; the certificate data are checked by proved Lean verifiers with kernel replay); no paper, the mathematical account is the repository’s PROOF.md.
$0.7580758$ (exact $473797394875551/625000000000000$) [Nas2026b] The interval-moment criterion of [Nas2026a] with new finite witnesses. Lean 4 formalization of the criterion and of the full value on Lean v4.35.0-rc2, registered as version 2 of Palomar entry PALOMAR-2026-09-19-000006 (standard axioms only; exact rational checks by decide +kernel); paper on Hexagon. According to Naslund, this is close to the limit of the current approach.

References

Contribution notes

ChatGPT 5.2 Pro was used to prepare an initial version of this page. The $205/12$ row was reattributed after checking arXiv:0804.4892 Theorem 3.7 against the Lewko 2015 EJC abstract, which records the same exponent. The [Kra2026] and [Jon2026a] rows were drafted with Claude (Anthropic) for the contributor, who verified the references; both constants in those rows were recomputed from the data as stated. The [Nas2026a] row was added on 20 Sep 2026, drafted with Claude (Anthropic) from the registry record and the repository; the six chains, the six chain-power thresholds and the surplus identity $\sum_i f_i - \alpha = 25671/10^{12}$ were rechecked from the paper’s parameter table, while the composite and binary moments were not recomputed here. The [Jon2026b] row was added on 22 Sep 2026, drafted with Claude (Anthropic) from the registry record and the repository’s certificate data; from that data the contributor rechecked the six chains (every forward difference a nonzero square), the six chain-power thresholds, the two composite moment sums over the listed retained words with their free multiplicities, the binary threshold $\log_2 a > 2\alpha$ at the certified growth factor, and the surplus identity $\sum_i f_i - \alpha = 38652/10^{15}$; the composite arc geometry and the binary growth certificate itself were not recomputed here. The [Nas2026b] row was added on 9 Oct 2026, drafted with Claude (Anthropic) from the Hexagon preprint, the registry record and the repository. The [OAI2026] row was added on 9 Oct 2026, drafted with Claude (Anthropic) from the preprint.

← Back to the table of constants