Erdős #1191 — how small can an infinite Sidon set's liminf density be?

Statement

Let $A\subset\mathbb{N}$ be an infinite Sidon set (all pairwise sums $a+b$, $a\le b\in A$, distinct). Is it true that \[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{1/2}=0\quad\text{?}\] Does there exist an infinite Sidon set $A$ such that \[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{c}>0\] for some $c>0$? (erdosproblems.com/1191, statement verified verbatim against the live page.)

Facts

- Prize $1000; status open, explicitly flagged "cannot be resolved with a finite computation" (erdosproblems.com/1191, site-owner belief; page last edited 06 April 2026; 0 forum comments as of this fetch). - Falsifiable: no — both sub-questions are statements about the asymptotic behaviour of an infinite set (a liminf equalling 0, or the existence of an infinite Sidon set with a certain liminf property); no finite computation decides either. - Origin: Erdős [Er80, p.98] ("A survey of problems in combinatorial number theory", Ann. Discrete Math. 1980) offered \$1000 "for clearing up the problems" raised here. The question itself is older: Kevin O'Bryant's annotated bibliography (arXiv:math/0407117, entry [12], §12aβ) shows it was first raised by Alfred Stöhr, 1955 ("Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, II", J. Reine Angew. Math. 194), who — after reproving/sharpening Erdős's unpublished result that every infinite Sidon set has $\liminf A(n)\sqrt{\log n}/\sqrt n \ll 1$ — explicitly asks "how large [can] $\liminf A(n)\sqrt{\log n}/\sqrt n$ be, and if the answer is 0, then what would be a suitable replacement for $\sqrt{\log n}$" and "if there is a Sidon set for which $0<\liminf A(n)\sqrt{\log n}/\sqrt n$" — i.e. Stöhr's 1955 questions are verbatim Q1 and Q2 of Erdős #1191, 25 years before [Er80] and 71 years before today. - Known results / best bounds (all read directly, not inferred): - Erdős proved (see [HaRo66], Halberstam & Roth, *Sequences Vol. I*, 1966) that every infinite Sidon set satisfies $\liminf A(x)\sqrt{\log x}/\sqrt x \le c$ for some finite constant $c$ — this only bounds the constant, it does not touch whether it can be forced to $0$ (Q1) or be positive (Q2). - Cilleruelo (2015, unpublished lecture notes "Conjuntos de Sidon", AGRA II school) proved an explicit value of that constant, on the order of $\approx 21.2$ (exact closed form garbled in OCR of the citing PDF — cited here only as "an explicit but large constant", not a precise value), and posed reducing it to $4$ as an exercise. - Kevin O'Bryant, "The Thickness of Infinite Sidon Sets", arXiv:2606.28651 (submitted 26 Jun 2026 — 6 days before this page was written): proves, for the generalized class of $\gamma$-Golomb rulers (Sidon sets are $\gamma=1$), $\liminf_{n\to\infty} A(n)/\sqrt{n/\log n} \le (2/\sqrt{\log 2})\sqrt\gamma \approx 2.402\sqrt\gamma$, via a block-decomposition + weighted Cauchy–Schwarz "energy" argument generalizing Erdős's original method (Theorem 1) — the current best explicit constant. The same paper's Theorem 2 gives the companion $\limsup A(n)/\sqrt n \le \sqrt\gamma$ (Erdős/Krückeberg [Kr61], sharp for $\gamma=1$: this is exactly Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set?), with a matching lower-bound construction $\ge\sqrt{\gamma/2}$ via near-optimal Golomb rulers of Caicedo–Martos–Trujillo. - Neither the Cilleruelo nor the O'Bryant 2026 result resolves Q1 (is the constant forced to 0?) or Q2 (is there a set keeping the product bounded away from 0 with a weaker $(\log x)^c$, $0<c<1/2$, weight?) — both only sharpen the finite constant in Erdős's original inequality. - Growth-rate (limsup/density) side, structurally adjacent but a different question: Ruzsa [Ru98] (J. Number Theory 68, 1998) gave a probabilistic construction of an infinite Sidon set with $A(x)=x^{\sqrt2-1+o(1)}$ (via $\{\log p:p\text{ prime}\}$ being a multiplicative-to-additive Sidon set); Cilleruelo (arXiv:1209.0326) gave a constructive discrete-logarithm analogue with the same exponent, generalizing to $B_h$ sets. This remains the record for infinite-set growth rate but is about a different (limsup/density) quantity than #1191's liminf-oscillation question. - Related problems: Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the site states verbatim that Q2 of #1191 is "a stronger form of" #39 ("is there an infinite Sidon set with $|A\cap\{1,\ldots,N\}|\gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon$?", \$500, open). Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the true limsup companion (how large can $\limsup A(N)/N^{1/2}$ be?), content-verified; the erdosproblems.com "See also [729]" pointer on the #1191 page appears to be a broken/stale cross-reference (see Literature state). Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the foundational finite-Sidon-set $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$ problem, same object, same Erdős–Turán/Lindström-style double-counting toolkit at the root of every bound here.

Literature state

Not resolved anywhere found. Every source checked — erdosproblems.com/1191 itself (0 comments, still marked open, last touched April 2026), O'Bryant's DS11 survey, and every arXiv/Google Scholar/WebSearch query run — confirms both sub-questions (Q1: is the liminf constant forced to 0? Q2: can it be kept positive against a weaker $(\log x)^c$ weight?) remain fully open, with no partial resolution.

The most significant finding is timing, not content: Kevin O'Bryant — the field's own bibliographer (arXiv:math/0407117, EJC DS11) — submitted a new paper on exactly this constant, arXiv:2606.28651, on 26 June 2026, six days before this page was written. It sharpens Erdős's 1955/1966-era inequality's explicit constant from Cilleruelo's $\approx21.2$ down to $2/\sqrt{\log2}\approx2.402$, via a generalization (to $\gamma$-Golomb rulers) of the same block-energy/Cauchy–Schwarz method Erdős and Halberstam–Roth used. Critically, the paper's own "Further problems" section (p.11) poses a *different*, smaller open question (the behaviour of $\min_\ell A(\ell N)/\sqrt{\ell N/\log(\ell N)}$ across blocks $\ell=1,\dots,M$ for a fixed near-extremal Sidon set) and its "Nonrigorous thoughts" subsection explicitly states the author believes the block-energy argument is "fully optimized" and speculates (without proof) that a reverse-martingale or entropy-inequality reformulation might be needed to go further — i.e. the paper's own author signals that Q1/Q2 need a genuinely different technique, not a refinement of the current one.

Notably, arXiv:2606.28651's tool-disclosure section states the paper "was developed in interaction with Anthropic's ClaudeAI" and had typos/errors caught by "Harmonic's AristotleAI" — a live, dated (June 2026) example of AI-assisted work on the exact Sidon-liminf constant family that #1191 belongs to, yet it explicitly does not touch the 0-vs-positive dichotomy that is the actual $1000 question.

No Lean/formal-conjectures entry exists for #1191 (site shows "Formalised statement? No", link to create one on google-deepmind/formal-conjectures). No forum discussion. No claim of partial progress recorded on the problem-status widget (marked "None" — no partial/claimed solutions in comments).

Attack surface

- Mode: derivation+formalization (not finite-search — both sub-questions are about the asymptotic behaviour of an infinite object; erdosproblems.com explicitly rules out a finite-computation resolution). - Concrete first experiment: (1) Reproduce O'Bryant's block-energy proof (arXiv:2606.28651, Theorem 1) symbolically/numerically and probe his own "Further problems" question — compute, for candidate Sidon sets (Ruzsa's [Ru98] probabilistic construction, its constructive discrete-log analogue [arXiv:1209.0326], and the classical Mian–Chowla greedy set), the finite-truncation quantity $\min_{1\le\ell\le M} A(\ell N)\sqrt{\log(\ell N)}/\sqrt{\ell N}$ for a range of $N,M$, to get numerical evidence on whether known constructions' liminf-type ratio is trending toward 0 (support for Q1) or plateauing above 0 (support for Q2). (2) Search his weighted-Cauchy–Schwarz step (the $w_\ell=(\ell\,\psi(\ell N))^{-1/2}$ weight family in the proof) for an alternative weight profile — e.g. via a small LP/evolutionary search analogous to the AlphaEvolve-assisted constant-optimization already run on the companion problem Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — that either drives the derived upper bound toward 0 as $N\to\infty$ (this would be real progress on Q1, since currently the bound is a fixed constant independent of $N$) or provably cannot (evidence the block-energy method has a hard floor, consistent with the author's own "fully optimized" remark). - Oracle: none mechanical for Q1/Q2 themselves (asymptotic liminf statements about infinite sets are not finitely decidable, matching the site's "not-finite" flag). For the exploratory sub-task above: mechanical and cheap — generate/verify a Sidon set (standard $O(n\log n)$ or $O(n^2)$ Sidon-property check) and compute the ratio numerically for $x$ up to whatever range is computationally convenient; this is weak, non-rigorous evidence only, useful to steer conjecture direction, not to prove anything. - Feasibility: honest read — a genuinely hard, 71-year-old problem (Stöhr 1955 → Erdős 1980 → still open July 2026) that the world's most active Sidon-set researcher (O'Bryant) was actively working adjacent to, with AI tool assistance, days before this write-up, and did not resolve. A full proof of Q1 or a construction resolving Q2 is famous-and-hard, likely requiring a qualitatively new technique (the author's own speculation: entropy/martingale methods) beyond the block-energy argument that has been the sole tool since 1955. A realistic, in-reach contribution is the numerical/exploratory sub-task above (auditing known constructions' block-minimum ratio, and probing whether the weighted-Cauchy–Schwarz step in O'Bryant's proof admits an $N$-dependent improvement) — genuinely useful signal, not a resolution.

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — \$500, open; site states Q2 of #1191 is explicitly "a stronger form of" this problem (does there exist an infinite Sidon set with $|A\cap\{1,\ldots,N\}|\gg_\epsilon N^{1/2-\epsilon}$ for all $\epsilon$). - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the limsup companion (how large can $\limsup A(N)/N^{1/2}$ be, open, Erdős–Krückeberg $\ge1/\sqrt2$, conjectured $=1$); content-verified as the true target of the site's "See also" pointer on #1191, which currently mislinks to an unrelated problem (#729, factorial divisibility) — likely a stale renumbering artifact worth flagging to the site maintainer. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the foundational finite Sidon-set size problem $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$; same object, same Erdős–Turán/Lindström double-counting ancestry underlying every bound touched here, already documented in this wiki with the fullest technique lineage (Singer construction, shift-incidence counting, AlphaEvolve-assisted constant optimization). - Sidon sets / B_2 sets / Golomb rulers — the central object ($B_2$ sets / Golomb rulers / Babcock sets). - $\gamma$-Golomb rulers (bounded-multiplicity difference sets generalizing Sidon sets) — the $\gamma$-Golomb-ruler generalization (arXiv:2606.28651) unifying Sidon sets ($\gamma=1$) with bounded-multiplicity difference sets. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the Erdős–Stöhr–Halberstam-Roth–O'Bryant technique: partition into length-$N$ blocks, bound $\sum|\text{block}|^2$ above via the Sidon/$\gamma$-Golomb property and below via weighted Cauchy–Schwarz; the sole known technique behind every bound on this liminf/limsup pair since 1955, explicitly believed "fully optimized" by its most recent user. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — the 1998 probabilistic (and later Cilleruelo constructive discrete-log, arXiv:1209.0326) infinite Sidon set with $A(x)=x^{\sqrt2-1+o(1)}$; relevant as a concrete "known-good" construction to numerically audit against Q1/Q2, though it targets a different (limsup/growth) quantity. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — AI-evolutionary numeric optimization of piecewise-affine bound parameters, already run live on the sibling problem Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets (Tao/Carter, Nov 2025); directly transplantable as the concrete first experiment's weight-search sub-task above.