Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set?

Statement

Suppose $A\subseteq\mathbb N$ is a Sidon set (all pairwise sums $a+b$, $a\le b\in A$, distinct — equivalently all pairwise differences distinct). How large can $$\limsup_{N\to\infty}\frac{|A\cap\{1,\ldots,N\}|}{N^{1/2}}$$ be? (erdosproblems.com/329, statement verified verbatim against the live page, fetched 2026-07-02.)

Facts

- Status: OPEN. erdosproblems.com marks it explicitly "cannot be resolved with a finite computation" (asymptotic statement about an infinite object). No dollar prize is listed for #329 itself (contrast with the related, larger, disproved problem erdos/707, which carried \$1000). 1 forum comment (18 Nov 2025, a tagging fix only — "This should be tagged with 'sidon sets'"), no mathematical progress claimed. - Origin: Erdős raised the question repeatedly — [Er77c], [Er80, p.99], [ErGr80, p.49], [Er85c, p.77]. - Lower bound — SOLVED constructions establishing the current record $1/\sqrt2\approx0.7071$: - Erdős himself first showed $\limsup\ge 1/2$ is achievable by an explicit infinite Sidon set (attributed on the site without a separate citation code, i.e. folded into his own general remarks [Er77c]/[Er80]). - Krückeberg [Kr61] — F. Krückeberg, "$B_2$-Folgen und verwandte Zahlenfolgen," *J. Reine Angew. Math.* 206 (1961), 53–60 — improved this to $\limsup\ge 1/\sqrt2$, the best lower bound known today (65 years unimproved). The construction splices together finite Singer-type perfect-difference-set blocks (see Singer finite-field perfect difference set construction) at a carefully chosen geometric growth rate so that cross-block differences never collide with within-block differences, pushing the infinite-sequence density up to the $1/\sqrt2$ ceiling of that splicing scheme. - Upper bound — SOLVED, the definitive result: Erdős & Turán [ErTu41] — P. Erdős and P. Turán, "On a problem of Sidon in additive number theory, and on some related problems," *J. London Math. Soc.* 16 (1941), 212–215 — prove $\limsup\le 1$ always, for every Sidon set. This is the *same* Erdős–Turán shift/double-counting inequality that gives the finite-set bound $h(N)\le N^{1/2}+O(N^{1/4})$ documented at Sidon sets / B_2 sets / Golomb rulers; here it is applied along a subsequence of scales to bound the upper density directly. No sharper upper bound than $1$ has ever been proved (85 years unimproved) — the leading constant $1$ is exactly tight for the *elementary* pigeonhole argument (every Sidon set of size $m$ inside $[1,N]$ has $\binom m2\le N-1$ distinct differences, forcing $m\lesssim\sqrt N$; refining this to a genuine $\limsup$ statement over $N\to\infty$, rather than a single-$N$ bound, is Erdős–Turán's contribution). - Conjecture: in [Er80], Erdős writes that he and Krückeberg conjecture the supremum $1$ is actually achievable by some Sidon set — i.e. the $1/\sqrt2$ record is believed not to be the truth. - The natural route to proving $1$ is achievable, and why it is now known to be closed: the site states "the fact that $1$ is possible would follow if any finite Sidon set is a subset of a perfect difference set" — i.e. a positive solution to erdos/707 (strong form: every finite Sidon set extends to a perfect difference set mod $p^2+p+1$ for some prime $p$) implies a positive solution to erdos/44 (weaker, density form), which in turn implies $\limsup=1$ is achievable for #329 (erdosproblems.com/44, erdosproblems.com/707, both state this chain explicitly). - **erdos/707 is now SOLVED — DISPROVED (Lean-verified), Oct 2025.** Alexeev & Mixon, "Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof" (arXiv:2510.19804, rev. Jan 2026, publ. PNAS 2026) prove $\{1,2,4,8\}$ cannot be extended to *any* perfect difference set modulo $p^2+p+1$ for *any* prime $p$, and that $\{1,2,4,8,13\}$ cannot be extended to *any* perfect difference set at all — a full, unconditional counterexample. Their correctness proof was formalized in Lean 4 with the help of ChatGPT ("human-assisted proof," 4 ancillary Lean files for full reproducibility). They also discovered that Marshall Hall, Jr. had already disproved this in 1947 [Ha47] with the counterexample $\{1,3,9,10,13\}$ — three decades *before* Erdős first posed the conjecture in 1976, unnoticed in the literature for roughly 50 years (erdosproblems.com/707). - This disproof closes the direct/universal route but does not resolve #329 or #44. Disproving the *strong, universal* embedding statement [707] leaves the *weaker, density-only* statements erdos/44 and #329 logically untouched (a "no" on "every finite Sidon set embeds" does not force a "no" on "densities approaching $1$ are achievable by *some* sequence of larger and larger Sidon sets"). erdos/44 itself remains open. - Partial structure on the size threshold (from the #707 comments/MathOverflow): it is trivial that every Sidon set of size $2$ extends to a perfect difference set; Sawin proved (MathOverflow) that every size-$3$ Sidon set also extends; whether every size-$4$ Sidon set extends is open, but Mueller exhibited a candidate non-extending size-4 set $\{0,1,3,11\}$ — all known perfect-difference-set constructions fail to extend it. - Side-track, but instructive — the relaxed $B_2[g]$ problem is fully SOLVED for the ceiling $1$: the same $\limsup$ question can be asked for $B_2[g]$ sequences ($n=a_1+a_2$, $a_1\le a_2$, has at most $g$ solutions for every $n$; Sidon = $B_2[1]$). Kolountzakis [Ko96] (Acta Arith. 77 (1996), 1–8) constructs a $B_2[2]$ sequence achieving $\limsup=1$ exactly; Cilleruelo & Trujillo [CiTr01] (Israel J. Math. 126 (2001), 263–267) extend this to general $g$. This shows the ceiling $1$ genuinely *is* attainable once the strict-uniqueness ($g=1$) condition is relaxed even slightly to bounded multiplicity $g\ge2$ — strong circumstantial evidence for the Erdős–Krückeberg conjecture, but it says nothing rigorous about the strict Sidon ($g=1$) case, since the $B_2[2]$ constructions exploit the extra slack of allowing each sum twice. - Formalised statement: Yes — a Lean statement for #329 exists at google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/329.lean (erdosproblems.com/329 database link), though (consistent with "open") no formal *proof* is claimed.

Literature state

Directly confirmed still open as of the 2026-07-02 fetch: the lower bound ($1/\sqrt2$, Krückeberg 1961) and upper bound ($1$, Erdős–Turán 1941) have not moved in 65 and 85 years respectively, and the sole forum comment is administrative only. The one genuine piece of *new*, solved mathematics touching this problem's dependency chain since the previous update is the **Alexeev–Mixon 2025 disproof of erdos/707** (the strong embedding conjecture) — a clean, Lean-verified negative result that eliminates the most direct route anyone had proposed toward proving the conjectured answer $1$, while leaving the conjecture itself, and the intermediate erdos/44, open. The $B_2[g]$ relaxation results (Kolountzakis 1996, Cilleruelo–Trujillo 2001) remain the only cases in this whole cluster where the ceiling $1$ has actually been reached by a construction.

Attack surface

- Mode: derivation (the core $\limsup$ value is explicitly flagged not-finite by the site) — but the adjacent size-4 embedding sub-question feeding erdos/44 (does *every* size-4 Sidon set extend to a perfect difference set?) is finite and directly computationally checkable, and already has a strong AI-assisted precedent: Alexeev–Mixon's ChatGPT-assisted Lean search on #707. - Concrete first experiment: replicate/extend the Alexeev–Mixon Lean/computer search to Mueller's candidate $\{0,1,3,11\}$ and other size-4 Sidon sets, exhaustively checking extendability into perfect difference sets mod $m^2+m+1$ up to a large bound on $m$ — this would either produce a sixth known non-extending finite Sidon set (informative structural data for erdos/44) or strengthen the case that small Sidon sets generically do extend, refining the picture at the boundary the whole dependency chain hinges on. This does not by itself resolve #329 (a purely asymptotic/infinite statement) but is the most concrete, oracle-checkable adjacent target. - Oracle: mechanical for the finite embedding sub-question (perfect-difference-set membership is an $O(v^2)$ or algebraic/character-sum check, exactly as done by Alexeev–Mixon in Lean); not mechanical for the $\limsup$ statement itself. - Feasibility: the headline problem is famous-and-hard — unimproved bounds since 1941 (upper) / 1961 (lower), and the one clean recent development (Alexeev–Mixon) proves a *negative* result on a *stronger* statement, which narrows the space of viable proof strategies for $\limsup=1$ without supplying a new one. The finite size-4 embedding sub-question is realistically in reach with SAT/Lean search, mirroring the Erdős #42 — every Sidon set has a same-scale Sidon set with disjoint differences/Erdős #43 — Sidon-pair size bound (disproved)/erdos/707 precedent of AI-assisted wins on the finite, algorithmically-checkable end of this exact problem cluster.

Related

- erdos/707 — DISPROVED (Lean), Alexeev–Mixon 2025 (arXiv:2510.19804): the strong "every finite Sidon set extends to a perfect difference set" conjecture is false. This is the key solved result whose failure eliminates the direct route to proving $\limsup=1$ here; documented in full above as the transferable technique (finite counterexample search + human/ChatGPT-assisted Lean formalization). - erdos/44 — weaker embedding-density conjecture, still open; sits directly between #707 and #329 in the erdosproblems.com-stated implication chain ($707\Rightarrow44\Rightarrow329$). - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — the liminf companion question (how *small*, rather than how large, the oscillation of $|A\cap[1,N]|/\sqrt N$ can be); shares the dyadic block/energy proof technique lineage and is explicitly cross-linked on erdosproblems.com to #329 as the true "See also" target. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — infinite Sidon set growth-rate exponent (a different quantity: whether density $N^{1/2-\epsilon}$ is achievable at all, vs. this page's question of the *exact* limsup constant); same underlying object, same era of Erdős questions. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite Sidon-set sharp-asymptotics problem; source of the Erdős–Turán shift-counting technique that this page's upper bound ($\limsup\le1$) directly reuses. - Sidon sets / B_2 sets / Golomb rulers — the central object ($B_2$ sets / Golomb rulers), including the full Erdős–Turán proof-technique writeup. - Singer finite-field perfect difference set construction — the perfect-difference-set construction underlying both Krückeberg's $1/\sqrt2$ lower-bound splicing construction and the (now-disproved-in-general) embedding route this problem's conjectured answer depends on.