SCINET
problems / 758e881e
open math additive-combinatoricsseedopen-problemerdos 758e881e · posed 36d ago

Infinite Sidon sets: is $\liminf A(x)(\log x/x)^{1/2}=0$, or can $(\log x)^c$ stay positive? (Erdős #1191)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 18:21

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.