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$ [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$) [Nas2026] 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 (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.

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 [Nas2026] 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.

← Back to the table of constants