How dense can an infinite Sidon set be along N^{1/2}? (Erdős #329)
Statement
A set $A\subseteq\mathbb{N}$ is a 'Sidon set' (a $B_2$ set) if all pairwise sums $a+a'$ (with $a\le a'$, $a,a'\in A$) are distinct — equivalently, all positive pairwise differences are distinct. For an infinite Sidon set $A$, how large can $$\limsup_{N\to\infty}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}$$ be? Determine the supremum of this quantity over all infinite Sidon sets.
Acceptance. FULLY RESOLVES: determine the supremum $S$ of $\limsup_N \lvert A\cap\{1,\ldots,N\}\rvert/N^{1/2}$ over infinite Sidon sets — in particular prove the Erdős–Krückeberg conjecture $S=1$ (or establish whatever the true value is) — with a complete proof; a Lean/Coq formalisation is preferred, otherwise a full written proof (a family of Sidon sets with density arbitrarily close to the claimed value, plus a matching upper bound). ADVANCES (each checkable): improve the achievable lower bound by constructing an infinite Sidon set whose density constant $\limsup_N \lvert A\cap\{1,\ldots,N\}\rvert/N^{1/2}$ strictly exceeds the best value stated in the background ($1/\sqrt2$), delivering an explicit (e.g. periodic or algebraically described) construction with a verifiable certificate that it is Sidon and attains the claimed density; or improve the upper bound strictly below $1$, with proof. Deliver the proof, or the explicit Sidon construction plus Sidon-property certificate plus density calculation.
Background
Asked by Erdős [Er77c; Er80, p.99; ErGr80, p.49; Er85c, p.77]. Listed as open on erdosproblems.com/329 (fetched 2026-07-13, status 'open', tagged 'number theory | sidon sets'); a Lean 4 formalisation exists in google-deepmind/formal-conjectures. Since a Sidon set contained in $\{1,\ldots,N\}$ has at most $(1+o(1))N^{1/2}$ elements, the limsup is at most $1$ — this upper bound is due to Erdős and Turán [ErTu41]. On the achievability side, Erdős showed the value $1/2$ is attainable, and Krückeberg [Kr61] improved this to $1/\sqrt{2}\approx 0.707$, still the densest construction known. Erdős and Krückeberg conjecture the extremal value is exactly $1$ [Er80]. A sufficient condition: the value $1$ would follow if every finite Sidon set embeds in a perfect difference set — closely tied to the venue problems on completing finite Sidon sets to near-maximal ones (Erdős #44, erdosproblems.com/44) and Erdős #707 (erdosproblems.com/707), and adjacent to the venue's dense infinite-Sidon question (Erdős #39). This embedding route is now closed, however: not every finite Sidon set is a subset of a perfect difference set — Hall exhibited the obstruction $\{1,3,9,10,13\}$ in 1947, and Alexeev and Mixon (2025) resolved Erdős #707 in the negative with further explicit non-extendable Sidon sets — so a proof that the supremum equals $1$ must proceed by other means; the extremal density constant itself remains open, pinned to $[1/\sqrt2,1]$. In the relaxed $B_2[g]$ setting (each integer has at most $g$ representations $n=a_1+a_2$ with $a_1\le a_2$; $B_2[1]$ = Sidon) the analogue is settled — Kolountzakis [Ko96] built a $B_2[2]$ sequence with limsup $1$, and Cilleruelo and Trujillo [CiTr01] handled larger $g$ — but the Sidon case ($g=1$) remains open, pinned only to $[1/\sqrt2,\,1]$. No Erdős prize is recorded. Attacker's tool: computational construction of dense infinite Sidon sets (greedy extension, or algebraic Singer / Bose–Chowla difference-set families, or SAT/ILP search over long finite prefixes) to beat Krückeberg's $1/\sqrt2$ density constant, or a matching upper-bound argument pushing the constant below $1$ (note the classical route of embedding every finite Sidon set into a perfect difference set is now blocked — that conjecture, Erdős #707, is false).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #329 (T. F. Bloom) | website |
| REF-02 | Lean 4 formalisation — google-deepmind/formal-conjectures #329 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.