An infinite Sidon set with counting function $\gg N^{1/2-\epsilon}$ for every $\epsilon>0$? (Erdős #39)
Statement
A set $A \subset \mathbb{N}$ is a Sidon set if all pairwise sums $a+b$ with $a \le b$, $a,b \in A$, are distinct (equivalently, $a+b=c+d$ with $a,b,c,d \in A$ forces $\{a,b\}=\{c,d\}$). Is there an infinite Sidon set $A \subset \mathbb{N}$ such that $$\lvert A \cap \{1,\ldots,N\} \rvert \gg_\epsilon N^{1/2-\epsilon}$$ for all $\epsilon > 0$?
Acceptance. FULLY RESOLVES: an explicit infinite Sidon set (fully specified construction) with a complete proof that its counting function is $\gg_\epsilon N^{1/2-\epsilon}$ for every $\epsilon>0$ — machine-checkable (Lean/Coq) preferred, else a full written proof with all steps; OR a negative resolution — a proof that no infinite Sidon set has counting function $\gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon>0$ (for instance, a proof that every infinite Sidon set has counting function at most $N^{c+o(1)}$ for some explicit $c<1/2$). A computation alone cannot close this. ADVANCES: (a) a new construction with a proven growth exponent strictly larger than the $\sqrt{2}-1$ exponent stated in the background, with full proof; (b) a proven quantitative strengthening of the upper-bound side (a rate in Erdős's $\liminf$ theorem constraining all infinite Sidon sets, strictly beyond what is stated in the background); (c) a machine-checked (Lean) formalization of the Ruzsa record bound or of Erdős's liminf theorem. Deliver the construction definition plus the proof file.
Background
One of Erdős's most-repeated problems, appearing across four decades of his problem papers ([Er56], [Er61], [Er73], [Er77c], [Er80, p.98], [ErGr80, p.48], [Er81], [Er82e], [Er85c], [Er91], [Er95], [Er97c], [Va99, 1.18]); Erdős offered $500 for a solution. Listed as open on erdosproblems.com/39 (fetched 2026-07-13, status 'open', tagged 'number theory | sidon sets | additive combinatorics'). The frontier: the trivial greedy construction (the Mian–Chowla sequence) achieves $\gg N^{1/3}$; the first improvement was by Ajtai, Komlós and Szemerédi [AKS81b], who found an infinite Sidon set with counting function $\gg (N \log N)^{1/3}$; the current record, $\gg N^{\sqrt{2}-1+o(1)}$ (exponent $\approx 0.4142$), is due to Ruzsa [Ru98]. Erdős had earlier offered $25 for any construction achieving $N^c$ with $c>1/3$ and $100 for achieving $\omega(N) N^{1/3}$ with $\omega(N)\to\infty$ [Er73, Er77c, Er80] — both now claimed by the above. The $\epsilon$ loss is necessary: Erdős proved that every infinite Sidon set satisfies $\liminf_{N} \lvert A \cap \{1,\ldots,N\}\rvert / N^{1/2} = 0$. Erdős and Rényi showed the target is nearly reachable if the Sidon condition is relaxed: for every $\epsilon>0$ there is a set $A$ with $\lvert A \cap \{1,\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ for all large $N$ whose additive representation function is merely bounded, $1_A \ast 1_A(n) \ll_\epsilon 1$. Discussed as Problem C9 of Guy's Unsolved Problems in Number Theory [Gu04]. The venue problem on the growth of the Mian–Chowla greedy Sidon sequence (Erdős #340) concerns the exact growth of the trivial construction; this problem asks to beat every known construction all the way up to exponent $1/2-\epsilon$. Attacker's tool: this is construction-plus-proof shaped — plausible routes are new algebraic or digit-interleaving constructions in the style of Ruzsa, possibly found by systematic exploration of parameterized construction families, with Lean formalization of the analysis as a certifying side deliverable.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #39 (T. F. Bloom) | website |
| REF-02 | Formalised statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.