OP-12000OpenNumber theory

Furstenberg–Sárközy square-difference constant ( $C_{4b}$ )

Furstenberg–Sárközy square-difference constant: determine $C_{4b}$ or improve its bounds; the repository records 0.758068 (lower) and 1 (upper).

MSC 11B30 · Arithmetic combinatorics; higher degree uniformity

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

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)}$ .

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

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 (from the repository page)

[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
[Kra2026] Krachun, D. Square-difference-free sets beyond the three-quarter barrier. 2026. arXiv:2608.01325
[Jon2026a] Jones, JD. A lower bound for the Furstenberg–Sárközy problem. 2026. Note, data and verification script: fs-lower-bound (commit c2c0687). Lean 4 / Mathlib formalization: fs-formal (commit 4e79656), Palomar registry entry PALOMAR-2026-08-26-000004. AI-generated with a human managing the workflow; see the repository's DISCLOSURE.md.
[Nas2026] Naslund, E. Square-difference-free sets of exponent 0.75806746: ordered intervals, composite digit codes, and a binary recursion. 2026. Paper, a companion note (A simpler construction of square-difference-free sets beyond exponent 0.758, exponent $0.758001$ ), exact certificate programs and the Lean 4 / Mathlib formalization: sarkozy-lower-bound-0.758 (commit e5d6937, Apache-2.0); Palomar registry entry PALOMAR-2026-09-19-000006, An interval-moment criterion for square-difference-free integer sets. The papers disclose that they were written by GPT-6-Astra under the author's supervision and the Lean development with Codex agents; see the repository's formalization.yaml.
[Jon2026b] Jones, JD. Lower bounds for sets without perfect-power differences. 2026. Lean 4 / Mathlib formalization with the exact certificate data and the mathematical account (PROOF.md): nk-lean (commit 55acbf0, MIT); Palomar registry entry PALOMAR-2026-09-21-000004. The repository discloses substantial AI assistance (OpenAI Codex agents; GPT 6 Pro, Claude and Grok) with a human directing the work and responsible for the submission; see its DISCLOSURE.md. Not on arXiv at the time of writing.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 0.758068; best known upper bound 1. Values marked with an asterisk have minimal verification.

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

[1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Furstenberg–Sárközy square-difference constant ($C_{4b}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Source & evidence

https://teorth.github.io/optimizationproblems/constants/4b.html

Constant page from github.com/teorth/optimizationproblems at commit 2c1968c, Apache-2.0. The maintainers review submissions for plausibility and replicability but do not certify correctness; asterisked bounds have minimal verification.

Source date: Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differ
Imported: 2026-10-10

How we use sources ↗

Record

Difficulty: HardResisted sustained effort by specialists.
Posed by: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers) and contributors
Posed: 2026
Source: Curated problem listOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOriginal statement ↗
Citation: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Furstenberg–Sárközy square-difference constant ($C_{4b}$)
Added: 5 Nov 2026
Views: 0

Fields

Number theory