Infinite Sidon sets: is $\liminf A(x)(\log x/x)^{1/2}=0$, or can $(\log x)^c$ stay positive? (Erdős #1191)
Statement
Let $A\subset\mathbb{N}$ be an infinite Sidon set (all pairwise sums $a+b$ with $a\le b$ distinct) and write $A(x)=\lvert A\cap[1,x]\rvert$ for its counting function. Two questions: (1) Is it true that for every infinite Sidon set $$\liminf_{x\to\infty} \frac{A(x)}{x^{1/2}}(\log x)^{1/2}=0?$$ (2) Does there exist an infinite Sidon set $A$ and some $c>0$ such that $$\liminf_{x\to\infty} \frac{A(x)}{x^{1/2}}(\log x)^{c}>0?$$
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else full written proof) answering question (1) — either that the liminf is $0$ for every infinite Sidon set, or an explicit infinite Sidon set with proof that its liminf is positive (which would also answer (2) with $c=1/2$); or answering question (2) — an explicit infinite Sidon set and $c>0$ with proof that $\liminf A(x)(\log x)^c/x^{1/2}>0$, or a proof that no such set exists. A submission fully answering either numbered question with proof counts as resolving; state clearly which. No finite computation can settle these. ADVANCES: (a) an explicit admissible constant $c$ in Erdős's theorem ($\liminf A(x)(\log x)^{1/2}/x^{1/2}\le c$ for all infinite Sidon sets), or any strict improvement of the weight function beyond $(\log x)^{1/2}$ stated in the background, with proof; (b) a construction of an infinite Sidon set with $\liminf A(x)g(x)/x^{1/2}>0$ for any weight $g$ growing faster than the polynomial-loss constructions stated in the background (e.g. beating $A(x)\gg x^{\sqrt{2}-1}$ at every scale), with proof; (c) a proof of (1) restricted to a natural class (e.g. perfect difference set unions, greedy-type sets); (d) a Lean formalization of Erdős's liminf upper bound theorem. Deliver the proof file or the construction plus proof.
Background
From Erdős [Er80, p.98]; listed as open on erdosproblems.com/1191 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | sidon sets'). Erdős proved (see Halberstam–Roth [HaRo66]) that every infinite Sidon set satisfies $\liminf_{x\to\infty} A(x)(\log x)^{1/2}/x^{1/2}\leq c$ for some absolute constant $c>0$ — so question (1) asks whether that constant can be driven to zero, i.e. whether the $(\log x)^{1/2}$ weight is exactly critical. In [Er80] Erdős offered $1000 'for clearing up the problems' raised by this; per Bloom's commentary he may have meant determining the optimal weight $f$ such that $\liminf A(x)f(x)/x^{1/2}=0$ for all infinite Sidon sets. Question (2) is a strengthened form of Erdős #39 (erdosproblems.com/39), which asks how dense an infinite Sidon set can be; the densest known constructions there (Ruzsa's probabilistic/logarithmic construction) achieve $A(x)=x^{\sqrt{2}-1+o(1)}\approx x^{0.4142}$ for all large $x$ — far below the $x^{1/2}/(\log x)^{c}$ scale demanded by (2), so an affirmative answer would be a dramatic advance in dense Sidon constructions. The $\limsup$ analogue is Erdős #729. The venue's problem on the Mian–Chowla greedy Sidon sequence (Erdős #340) concerns the growth of one specific infinite Sidon set and is related but distinct. The attacker's tool: this is proof/construction-shaped — refined greedy or Ruzsa-style constructions with density guarantees at every scale for (2), and second-moment/gap arguments sharpening Erdős's liminf theorem for (1); numerics on large algorithmically generated Sidon sets can guide but cannot certify either answer.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1191 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #39 — density of infinite Sidon sets (weaker form of question 2) | website |
| REF-03 | Erdős Problem #729 — the limsup analogue | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.