Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set

Statement

Is there an infinite Sidon set $A\subset \mathbb{N}$ (i.e. all pairwise sums $a+b$, $a\le b\in A$, are distinct) such that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all $\epsilon>0$? (erdosproblems.com/39)

Facts

- Prize $500; status open, and per erdosproblems.com/39 explicitly "cannot be resolved with a finite computation" — it is an asymptotic-growth-rate question, not decidable by any finite example. - Falsifiable: no in the finite-counterexample sense. A "no" answer would require proving every infinite Sidon set has $\limsup |A\cap\{1,\ldots,N\}|/N^{1/2-\epsilon} = 0$ for some $\epsilon>0$ — an unbounded statement, not a finite search. - Origin: raised repeatedly by Erdős across [Er56][Er61][Er73][Er77c][Er80,p.98][ErGr80,p.48][Er81][Er82e][Er85c][Er91][Er95][Er97c]; also Vaughan [Va99,§1.18]; discussed as problem C9 in Guy's "Unsolved Problems in Number Theory" [Gu04]. - Known results / best bounds (all sourced, verified directly or via abstract): - Trivial baseline: greedy/inductive construction gives $\gg N^{1/3}$. - 1981: Ajtai, Komlós, Szemerédi [AKS81b], "A Dense Infinite Sidon Sequence," Eur. J. Combin. 2(1) — first improvement, $\gg (N\log N)^{1/3}$, via the semi-random ("nibble") method, which AKS introduced in this very paper (it is now a foundational technique across combinatorics, later generalized as the Rödl nibble). - 1998 (current record): Ruzsa [Ru98] — a probabilistic construction giving $\gg N^{\sqrt2-1+o(1)}$ ($\sqrt2-1\approx0.4142$), built from the fact that the primes form a *multiplicative* Sidon set, so $\{\log p : p \text{ prime}\}$ is an *additive* Sidon set of reals, which Ruzsa discretizes/randomizes into an integer set via a Diophantine-approximation argument. Simplified expositions: Maldonado, arXiv:1103.5732 (2011, "simplified proof ... as suggested in a paper of Ruzsa and Cilleruelo, *Real and $p$-adic Sidon sequences*, Acta Sci. Math (Szeged) 70 (2004), 505-510"). - ~2010–2012: Cilleruelo gave an *explicit* (non-probabilistic) construction matching the same exponent $x^{\sqrt2-1+o(1)}$, replacing Ruzsa's real logarithm with a family of discrete logarithms (fixed increasing primes, a primitive root mod each, base-expansion encoding); "Infinite Sidon sequences," arXiv:1209.0326. Cilleruelo–Tesoro, "Dense infinite $B_h$ sequences," arXiv:1206.3087 (2012), extend the *same* exponent formula $x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$ to $B_3,B_4$ sequences, showing Ruzsa's method is a genuine general-purpose engine, not a one-off trick. - 2026 (confirms no improvement since 1998): O'Bryant, "The Thickness of Infinite Sidon Sets," arXiv:2606.28651 (26 Jun 2026) — studies the more general $\gamma$-Golomb-ruler setting and states explicitly that Ruzsa's $x^{\sqrt2-1+o(1)}$ "remains the record for an infinite set," i.e. as of a week before this page was written, the exponent $\sqrt2-1$ is still unbeaten after 28 years. - Upper-bound side: Erdős himself proved that for *every* infinite Sidon set $A$, $\liminf_{N} |A\cap\{1,\ldots,N\}|/N^{1/2} = 0$ — so no infinite Sidon set can stay at density $N^{1/2}$ infinitely often; the $\epsilon$ in the problem statement is provably necessary. Erdős and Rényi separately constructed, for every $\epsilon>0$, a (non-Sidon, only "$B_2[g]$"-type bounded-representation) set with $|A\cap\{1,\ldots,N\}|\gg_\epsilon N^{1/2-\epsilon}$ and $1_A*1_A(n)\ll_\epsilon 1$ — i.e. the target density $N^{1/2-\epsilon}$ *is* achievable once the strict-Sidon (multiplicity-exactly-1) condition is relaxed to bounded multiplicity. This is exactly the gap the $500 prize is about closing. - Related, smaller cash offers by Erdős on the same exponent gap: $25 [Er73] for any construction beating $N^{1/3}$ (settled by AKS81b); $100 [Er77c][Er80] for $\omega(N)N^{1/3}$ with $\omega(N)\to\infty$ (also settled by AKS81b / superseded by Ruzsa). - Survey: O'Bryant, "A Complete Annotated Bibliography of Work Related to Sidon Sequences," EJC Dynamic Survey DS11, arXiv:math/0407117 (2004). - Related problems: Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set analogue ($h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$?, $1000, also open); Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ (distinct-triple-sums) analogue, same Erdős-era origin, $500, open, with the general-$h$ version proved false for $h=4$ (Nash [Na89]) and all even $h$ (Chen [Ch96b]); erdos/14 — unique-representation complement density, same family, open; Erdős #42 — every Sidon set has a same-scale Sidon set with disjoint differences and Erdős #43 — Sidon-pair size bound (disproved) — closely related finite-Sidon-pair problems in the *same* $500/$100 cluster, both recently SOLVED with heavy AI/LLM involvement (see Literature state).

Literature state

Not resolved anywhere. Every source checked — erdosproblems.com/39 itself (last edited 06 April 2026, zero comments, zero claimed partial solutions), the O'Bryant survey DS11, and the newest arXiv paper found on the topic (O'Bryant, arXiv:2606.28651, submitted 26 June 2026, six days before this page was written) — agrees the exponent $\sqrt2-1\approx0.4142$ from Ruzsa [Ru98] is still the best known lower-bound growth rate for a genuine infinite Sidon set, unimproved in 28 years despite an explicit alternative construction (Cilleruelo, discrete-log, arXiv:1209.0326) and a generalization to $B_h$ sets (Cilleruelo–Tesoro, arXiv:1206.3087) reaching the same exponent by essentially the same method. No paper found claims to close the gap between $N^{\sqrt2-1}$ ($\approx N^{0.4142}$) and the target $N^{1/2-\epsilon}$.

Two structurally close *sibling* problems in the same Sidon-set cluster on erdosproblems.com were resolved very recently with heavy AI assistance, which is directly relevant as a technique precedent even though it does not touch #39 itself: - #42 (finite Sidon-pair disjoint-differences existence, [Er95,p.5]): proved for small $M$ by a user "Sedov" using ChatGPT + Codex in the site comments, then proved *for all $M$* by "GPT 5.5 Pro" (prompted by user Sandhu), giving an explicit growth rate $|B|\gg(\log\log N/\log\log\log N)^{1/2}$ — status now SOLVED (LEAN). - #43 ($1000 problem, disjoint-difference Sidon-pair size bound): the first question was answered negatively as an immediate corollary of the #42 construction; Terence Tao gave a clean proof of the upper bound in the comments; Kevin Barreto gave a negative answer to the second (refined) question — now status DISPROVED. - A third, closely related published result: Alexeev & Mixon, "Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof," arXiv:2510.19804 (Oct 2025, rev. Jan 2026, publ. PNAS 2026) — resolves a different $1000 Erdős prize (every finite Sidon set extends to a finite perfect difference set — false, counterexample $\{1,2,4,8,13\}$), with the correctness of both their counterexample and a 1976-predating counterexample by Marshall Hall Jr. checked via a ChatGPT-"vibe-coded" Lean 4 proof (ancillary files on arXiv, fully reproducible).

So the *cluster* of Sidon-set problems Erdős left is actively being cracked, but the two problems solved (#42, #43) and the one via literature-rediscovery (Alexeev–Mixon) are all finite, algorithmically-checkable statements about a specific small structure or a specific counterexample search — exactly the falsifiability profile erdosproblems.com marks as *not* holding for #39. #39 is explicitly tagged "cannot be resolved with a finite computation," which is precisely why the AI-assisted / SAT / Lean-proof-search wins seen next door on #42/#43 have not (yet) touched it: those wins are search-and-verify over finite objects; #39 needs either (a) a new *general* infinite construction beating exponent $\sqrt2-1$, or (b) a genuinely new impossibility proof, neither of which is a finite-computation task.

Attack surface

- Mode: derivation+formalization (not finite-search — explicitly ruled out by the site). The live sub-tasks are: (a) try to push Ruzsa/Cilleruelo's exponent $\sqrt2-1$ higher by a genuinely different infinite construction; (b) formalize/verify the existing Ruzsa–Cilleruelo construction and the Erdős $\liminf=0$ upper-bound result in Lean, which would at minimum give a rock-solid, machine-checked floor to build on (no formalization of this specific result was found in this search, unlike the sibling Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets which already has one, arXiv:2605.03274). - Concrete first experiment: reproduce Cilleruelo's *explicit* discrete-logarithm construction (arXiv:1209.0326) computationally for finite truncations $N\le 10^6$–$10^8$, verify the empirical growth exponent numerically matches $\sqrt2-1$, then try parameter/base variations (different prime sequences, different primitive-root choices, hybrid with the AKS nibble method) in a numerical-optimization or evolutionary-search loop (à la the AlphaEvolve-on-CHO25 precedent documented for Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) to see if the *constant* (not just verifying the known exponent) can be improved, or — more ambitiously — whether a hybrid nibble+discrete-log scheme can beat the exponent itself on large finite truncations, which would at least be informative even though it can't constitute a proof for the infinite statement. - Oracle: for any finite truncation, "is this a Sidon set of size $\gg N^c$" is fully mechanical (check all pairwise sums for collisions, $O(n^2)$ or $O(n\log n)$ with sorting) — so empirical/heuristic exponent-improvement search is oracle-checkable end-to-end even though it cannot resolve the actual (infinite, all-$\epsilon$) conjecture. - Feasibility: famous and hard as literally stated — 28 years unimproved on the core exponent despite active, repeated attention (multiple independent constructions converging on the exact same $\sqrt2-1$, a strong signal it's a genuine technique barrier, not a neglect gap); O'Bryant's own June-2026 paper works around it (studies a relaxed $\gamma$-Golomb-ruler variant) rather than attacking it head-on. A realistic near-term contribution is *not* resolving #39 but (1) a Lean formalization of Ruzsa/Cilleruelo + the Erdős upper bound (cheap, high-value scaffolding, mirrors what happened on Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets), or (2) an AlphaEvolve/LLM-search-driven numerical push on the *finite-truncation* empirical exponent of hybrid constructions, purely as an exploratory/derivation-fuel exercise, not a proof.

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set sharp-asymptotics sibling ($1000, open); same Erdős–Turán-era origin; already has an active AI-assisted numerical-improvement precedent (AlphaEvolve on the Carter–Hunter–O'Bryant bound) that #39's attack surface should imitate. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ (distinct-triple-sum) density analogue, $500, open; general-$h$ version resolved for $h=4$ and even $h$ (Nash [Na89], Chen [Ch96b]) but not for the base Sidon ($h=2$, i.e. #39-adjacent) case. - erdos/14 — unique-sum-representation complement density, same Sidon-set cluster, open. - Erdős #42 — every Sidon set has a same-scale Sidon set with disjoint differences — sibling finite Sidon-pair-disjointness problem, SOLVED (LEAN) by GPT-5.5-Pro / user-supplied ChatGPT+Codex proofs in the erdosproblems.com comments — direct evidence of what AI-assisted attack looks like on the *finite* end of this same problem cluster. - Erdős #43 — Sidon-pair size bound (disproved) — sibling $1000 problem, DISPROVED, Tao + Barreto in comments. - Sidon sets / B_2 sets / Golomb rulers — the central object ($B_2$ sets); shared with Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets. - Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble — the Ajtai–Komlós–Szemerédi 1981 technique [AKS81b], introduced in this exact problem's literature, now a foundational combinatorics tool (Rödl nibble). - Ruzsa's log-of-primes probabilistic Sidon construction — Ruzsa [Ru98]: primes are multiplicatively Sidon $\Rightarrow \{\log p\}$ is additively Sidon $\Rightarrow$ randomized/discretized into the current-record integer construction, exponent $\sqrt2-1$. - Discrete-logarithm explicit Sidon construction (Cilleruelo) — Cilleruelo's explicit variant (arXiv:1209.0326) replacing Ruzsa's real log with discrete logs mod a sequence of primes; generalized to $B_h$ by Cilleruelo–Tesoro (arXiv:1206.3087). - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — machine-checked-proof precedent from the adjacent Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets (arXiv:2605.03274) and from Erdős #42 — every Sidon set has a same-scale Sidon set with disjoint differences/Erdős #43 — Sidon-pair size bound (disproved)/Alexeev–Mixon (arXiv:2510.19804, ChatGPT-assisted Lean), none of which yet exists for #39 itself. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — the AI-evolutionary numerical-search precedent (documented on Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) that is the most plausible near-term reusable machinery for probing #39's finite-truncation exponent empirically.

PRIOR-ART SCAN (2026-07-03)

Verdict: HARD-OPEN.

This is an independent, from-scratch re-scan (not a reuse of the 2026-07-02 page content above), run specifically to guard against the #64-style failure mode of claiming novelty for something already public. Result: nothing found anywhere changes the picture — no improvement, no active attack, no hidden repo.

Sources actually fetched/read this pass: - curl of erdosproblems.com/39 directly (2026-07-03): statement unchanged, tag "OPEN — cannot be resolved with a finite computation," 0 comments on the problem, comment-activity widget shows no partial/claimed status, page metadata "last edited 06 April 2026." Also surfaced a link not in our prior page: a Lean formalization exists. - curl of erdosproblems.com/forum/discuss/39: confirms 0 comments, nothing to incorporate. - github.com/google-deepmind/formal-conjectures — FormalConjectures/ErdosProblems/39.lean fetched directly: the theorem statement is formalized but the proof body is a bare sorry (plus a TODO comment "add the various known bounds as variants" — not done). Commit history for this file (via GitHub API): added 2025-08-20 (PR #580), touched only for cosmetic namespace/spacing fixes since (2025-11-04, 2026-01-06, 2026-01-24) — zero mathematical progress, no branch divergence (repo has only main + one unrelated revert branch). - github.com/teorth/erdosproblems data/problems.yaml (raw fetch, all 13k+ lines, isolated the number: "39" block): status.state: open, formalized.state: yes (the stub above) — matches site. - github.com/teorth/erdosproblems/wiki — fetched the AI-contributions-to-Erdős-problems wiki page (the exact "AI contributions wiki" named in the task) and the Notable-cases page in full: grepped for 39 and Sidon/sidon across every section (1a AI-standalone, 1b AI-alongside-literature, 1c AI-building-on-literature, and the notable-cases page) — zero hits. #39 has never been touched by any AI system tracked on that wiki, positive or negative. - arXiv API (export.arxiv.org) searches for abs:"infinite Sidon" and abs:"Sidon set" AND abs:density, sorted newest-first: no paper post-1998 improves the growth-rate exponent for a genuine infinite Sidon set. Closest near-misses checked by abstract and ruled out as different problems: arXiv:1911.13275 (Kohayakawa–Lee–Moreira–Rödl-style "$\alpha$-strong" Sidon sets in *random* infinite subsets — a different, relaxed notion, not the base problem); arXiv:2605.30922 ("An Improvement of Konstantoulas' Density Constant," May 2026 — Erdős–Turán representation-function constant, unrelated); arXiv:2602.23282 ("Largest Sidon subsets in weak Sidon sets," Feb 2026 — resolves a *finite* Sárközy–Sós problem, unrelated); arXiv:2606.28651 (O'Bryant, "The Thickness of Infinite Sidon Sets," 26 Jun 2026 — re-confirmed via direct abstract read that it explicitly states Ruzsa's $x^{\sqrt2-1+o(1)}$ "remains the record for an infinite set"). - OpenAlex API, newest-first search on "infinite Sidon set density": scanned the 15 most recent hits (through 2026-06-21) — nothing on-topic beyond the arXiv items above. - Semantic Scholar: rate-limited (429) on this pass; not blocking since OpenAlex + arXiv + erdosproblems.com's own bibliography jointly triangulate the same "no improvement since Ruzsa 1998" conclusion from three independent indexes.

Why HARD-OPEN and not FRESH-AND-TRACTABLE: the site itself marks it explicitly non-finite ("cannot be resolved with a finite computation"); the record exponent $\sqrt2-1$ has stood unimproved for 28 years despite at least two structurally different constructions (Ruzsa's probabilistic log-prime argument, Cilleruelo's explicit discrete-log variant) independently landing on the *exact same* exponent, which is a strong signal of a genuine technique ceiling rather than neglect; there is no in-progress human or AI attempt anywhere (0 forum comments, 0 AI-wiki entries, a Lean stub untouched mathematically for 8+ months). Not RESOLVED-IN-LITERATURE (confirmed still open by every index checked) and not ACTIVELY-WORKED (no evidence of any live attempt, human or AI, on the core question). No new experiment is proposed here beyond what the existing "Attack surface" section above already scopes (Lean formalization of the known bound as scaffolding, or empirical finite-truncation exponent search as an exploratory, non-resolving side task) — this scan found no new angle that would upgrade the verdict.