Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets

Statement

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$ (a set where all pairwise sums $a+b$, $a\leq b$, are distinct). Is it true that, for every $\epsilon>0$, \[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\] Erdős remarks it may even be true that $h(N)=N^{1/2}+O(1)$, but calls this "perhaps too optimistic" (erdosproblems.com/30).

Facts

- Prize $1000; status open, and per erdosproblems.com/30 explicitly "cannot be resolved with a finite computation" (site-owner belief, reflects a genuine-proof requirement, not a search). - Falsifiable: no in the finite-counterexample sense — the statement is an asymptotic $O_\epsilon(N^\epsilon)$ claim over all $\epsilon>0$, not decidable by exhibiting one bad $N$; a disproof would need a proof that the error term is $\gg N^{c}$ for some fixed $c>0$ infinitely often. - Origin: a problem of Erdős and Turán [ErTu41]; restated by Erdős across [Er61][Er69][Er70b][Er70c][Er72][Er73][Er77c][Er80,p.99][Er80e][Er81][Er81h,p.174][Er91][Er92c][Er94b][Er95][Er97c]; also Vaughan [Va99,§1.18]. It is Problem 31 on Ben Green's open-problems list (https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf) and Problem C9 in Guy's "Unsolved Problems in Number Theory" [Gu04]. - Known results / best bounds (chain of the *same* double-counting method, all sourced and verified directly): - Lower bound (matches leading term): Singer [Si38] — via a perfect difference set constructed in the finite field $\mathbb F_q$ (projective-plane / Singer-cycle construction), giving $h(N)\geq(1-o(1))N^{1/2}$. Formalized in Lean 4 with zero sorrys in arXiv:2605.03274 (May 2026): "for every prime power $q=p^k$ there exists a Sidon set modulo $q^2+q+1$ of cardinality $q+1$." - Upper bound, original: Erdős–Turán [ErTu41, 1941] and, independently, Lindström [Li69] both prove $h(N)\leq N^{1/2}+N^{1/4}+1$. - Upper bound, 2021: Balogh, Füredi, Roy [BFR21], arXiv:2103.15850 (publ. Amer. Math. Monthly 130(5), 2023): $h(N)\leq N^{1/2}+0.998N^{1/4}$ (combines two elementary counting arguments). - Upper bound, 2022: O'Bryant [OB22], arXiv:2207.07800: $h(N)\leq N^{1/2}+0.99703N^{1/4}$, via a logically simpler but computationally heavier variant of the same shift-counting method. - Upper bound, 2023/2025 (current published record): Carter, Hunter, O'Bryant [CHO25], arXiv:2310.20032 (publ. Acta Math. Hungarica 175:108–126, 2025): diameter of a $k$-element Sidon set is $\geq k^2-bk^{3/2}-O(k)$ with $b\leq1.96365$, equivalently $h(N)\leq N^{1/2}+0.98183N^{1/4}+O(1)$. Computer-assisted; a weaker hand-verifiable version gives $b\leq1.99058$. Confirmed directly from the arXiv abstract page. - Upper bound, informal/unpublished, Nov 2025: Terence Tao's blog post "Mathematical exploration and discovery at scale" (https://terrytao.wordpress.com/2025/11/05/mathematical-exploration-and-discovery-at-scale/, comment thread, read directly) records that Daniel Carter (a CHO25 co-author) proposed feeding the CHO25 bound's piecewise-affine parameter-optimization problem (parameters $\tau,\alpha,c_s$) to DeepMind's AlphaEvolve. After Carter supplied an admissibility-checking verifier (an earlier attempt was exploited by AlphaEvolve via a floating-point LP-solver failure mode), AlphaEvolve improved $b$ from 1.96365 to 1.952659676624688; Carter then hand-verified and further optimized to $b=1.9526463099204112$ — i.e. $h(N)\leq N^{1/2}+0.97632N^{1/4}+O(1)$, a real but not yet peer-reviewed / not on erdosproblems.com's own record improvement over CHO25. Directly relevant precedent: this is a live example of an LLM-driven evolutionary search (AlphaEvolve) advancing the exact numerical frontier of a stated Erdős problem's best-known bound. - Survey: O'Bryant, "A Complete Annotated Bibliography of Work Related to Sidon Sequences" [OB04], arXiv:math/0407117, EJC Dynamic Survey DS11 (2004) — the reference erdosproblems.com itself points to for the literature. - Related problems: Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $B_3$ analogue (distinct triple sums $a+b+c$), same Erdős/Turán-era family, still open, same style of algebraic-construction-vs-counting-bound game (Bose–Chowla lower bound, Green 2001 upper bound). erdos/840 — quasi-Sidon sets ($|A+A|=(1+o(1))\binom{|A|}{2}$), bounded by Erdős–Freud [ErFr91] between $(2/\sqrt3+o(1))N^{1/2}$ and $(2+o(1))N^{1/2}$, i.e. the *coefficient* of $N^{1/2}$ itself is open there, a strictly weaker but structurally adjacent question.

Literature state

Not resolved anywhere — every source checked (erdosproblems.com/30 itself, the O'Bryant survey DS11, and every 2021–2026 arXiv paper found) confirms this is still fully open as of July 2026. What exists is ~85 years of continuous, still-active incremental progress narrowing the *constant* in the $N^{1/4}$-order upper-bound error term: $1\to0.998\to0.99703\to0.98183\to$(informally)$\to0.97632$ (ErTu41/Li69 → BFR21 2021 → OB22 2022 → CHO25 2023/25 → AlphaEvolve-assisted, Nov 2025). This is real, verifiable, monotone progress, and it is happening on a visibly *shrinking* timescale (constant improvements roughly every 1–2 years, now including an AI-assisted iteration).

Critically, none of this progress touches the actual conjecture. The problem asks for the error term to be $O_\epsilon(N^\epsilon)$ for every $\epsilon>0$ — i.e. sub-polynomial savings, potentially down to $O(1)$ per Erdős's stronger remark — whereas every result above, including the AlphaEvolve-assisted one, is of the form $N^{1/2}+c\cdot N^{1/4}+O(1)$ for a shrinking but strictly positive constant $c$. Shrinking $c$ from 1 toward ~0.976 does not shrink the *exponent* $1/4$ at all; $N^{1/4}$ is not $O_\epsilon(N^\epsilon)$ for $\epsilon<1/4$. So the entire 1941–2026 upper-bound literature, including the newest AI-optimized value, is evidence *consistent with* the conjecture but operates one exponent-order away from what would be needed to resolve it — a genuinely different technique (not a refinement of Lindström-style double counting of shifts/collisions) appears to be needed to kill the $N^{1/4}$ term itself. This matches the erdosproblems.com framing ("cannot be resolved with a finite computation") — the current best-known method is fundamentally a real-analysis/counting optimization over finitely many parameters and cannot, by construction, reach a sub-power error term.

AI/formal-methods involvement found: (1) AlphaEvolve (Google DeepMind), applied live by Terence Tao + Daniel Carter to exactly this bound's optimization landscape, per the source above — first documented AI system to move the numerical needle on Erdős #30's best-known bound, though the result is informal (blog comment, not yet a paper) and explicitly flagged by Tao as needing careful anti-exploit verifier design. (2) A full Lean 4 formalization (arXiv:2605.03274, ~7500 lines, zero sorry) of Singer's lower-bound construction and of a *conditional reduction*: if prime gaps are subpolynomial AND a full subpolynomial upper-error hypothesis for $h(N)$ holds, then the Erdős #30 estimate follows. This gives a formal, machine-checked map of exactly what extra input (a prime-gaps hypothesis plus the currently-missing sub-polynomial upper bound) would suffice — useful scaffolding, not a resolution.

Attack surface

- Mode: derivation+formalization (not finite-search — the site explicitly rules out a finite computation resolving it; the live edge is either (a) push the shift/incidence-counting optimization further numerically/algebraically, which cannot alone resolve the conjecture but is a concrete, verifiable, currently AI-tractable sub-task, or (b) find/adapt a genuinely different upper-bound technique that produces a sub-polynomial, not just smaller-constant-times-$N^{1/4}$, error term). - Concrete first experiment: reproduce and try to further optimize the Carter–Hunter–O'Bryant piecewise-affine bound landscape (public verifier at https://github.com/dcartermath/sidon/blob/main/verify.py per Tao's blog post) with an evolutionary/LLM search over the parameters $\tau,\alpha,c_s$, starting from the already-improved $b=1.9526463099204112$; this is the exact task Tao/Carter ran with AlphaEvolve and is fully reproducible with an off-the-shelf verifier once the admissibility/side-conditions are made exploit-proof (their own experience: a naive verifier gets gamed via LP-solver floating-point failure modes). - Oracle: mechanical for the sub-task — the CHO25/Carter verifier takes $(\tau,\alpha,c_s)$, checks admissibility, and returns the implied upper bound on $b$; any claimed improvement is checked by re-running the verifier (as Tao/Carter did, catching one AlphaEvolve exploit this way). Not mechanical for the actual conjecture — no finite oracle exists; only a full proof (of a $N^\epsilon$-type error bound) would resolve it. - Feasibility: the constant-optimization sub-task is realistically in reach right now (it's the literal task AlphaEvolve was just run on, publicly documented with a semi-public verifier) but provably cannot resolve Erdős #30 itself, since it stays inside the $c\cdot N^{1/4}$ error regime. Full resolution is famous-and-hard: 85 years of Erdős–Turán-era attention, no qualitative-technique breakthrough found in any source checked. A realistic contribution: (1) reproduce/extend the AlphaEvolve-assisted constant, citably, as a small but real record improvement; (2) survey/derive whether analytic number theory tools that give sub-polynomial-error results elsewhere (e.g. in the finite-field/quadratic-residue Sidon-set constructions, or techniques from the Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets $B_3$ literature) can be transplanted to attack the exponent itself, which is the qualitatively different move nobody in the literature checked here has made.

Related

- Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $B_3$ (three-term-sumset) Sidon analogue, same Erdős–Turán-era origin, same construction-vs-counting bound-tightening game (Bose–Chowla lower / Green 2001 upper), still open. - erdos/840 — quasi-Sidon sets, a relaxation where even the leading-order constant (not just the error term) is open (Erdős–Freud [ErFr91] bounds). - Sidon sets / B_2 sets / Golomb rulers — the central combinatorial object ($B_2$ sets / Golomb rulers). - Singer finite-field perfect difference set construction — the finite-field perfect-difference-set construction giving the matching $(1-o(1))N^{1/2}$ lower bound; formalized in Lean, arXiv:2605.03274. - Lindström-style shift/collision double-counting (upper-bound method for Sidon sets) — the Lindström-style counting-of-collisions technique underlying every published upper bound from [ErTu41]/[Li69] through [CHO25] (arXiv:2310.20032); structurally capped at giving $N^{1/2}+c N^{1/4}$-type bounds, not the sub-polynomial error the conjecture needs. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — AI-evolutionary optimization applied live (Nov 2025, Tao/Carter, terrytao.wordpress.com) to the CHO25 piecewise-affine parameter space; concrete reproducible sub-task. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — arXiv:2605.03274, formal (7541-line, zero-sorry) Lean 4 proof of Singer's construction plus a conditional reduction of Erdős #30 to a prime-gaps + sub-polynomial-error hypothesis pair. - Finite-field / projective-plane constructions for extremal additive sets — projective-plane / perfect-difference-set methods (Singer 1938, Bose–Chowla 1962) that give the best known lower bounds across the whole Sidon/$B_h$ family.