Erdős #158 (ancestor result) — the solved $g=1$ liminf-density theorem for infinite Sidon sets, and its bounded-multiplicity generalization

Statement

Important framing note. erdosproblems.com's own problem #158 is OPEN, not solved, as verified by direct fetch on 2026-07-02. It asks: let $A\subset\mathbb N$ be infinite with, for every $n$, at most $2$ solutions to $a+b=n$ ($a\le b$, i.e. $A$ is a sum-bounded $B_2[2]$ set). Must $$\liminf_{N\to\infty}\frac{|A\cap\{1,\ldots,N\}|}{N^{1/2}}=0\ ?$$ This page does not claim to resolve that. Per the site's own remark on #158: *"If we replace $2$ by $1$ then $A$ is a Sidon set, for which Erdős proved this is true."* This page documents that solved $g=1$ ancestor — the classical theorem that every infinite Sidon set has liminf density $0$ — together with its recent (June 2026) extension to the analogous difference-bounded multiplicity-$\gamma$ family, which is the closest existing generalization and the technique that any future attack on the true (sum-bounded) #158 would need to adapt.

Solved theorem (Erdős, via Stöhr 1955; sharp constant: O'Bryant 2026). Every infinite Sidon set (i.e. $B_2[1]$ set: at most one solution to $a+b=n$, equivalently at most one solution to $a-b=d$) $A\subset\mathbb N$ satisfies $$\liminf_{n\to\infty}\ A(n)\sqrt{\frac{\log n}{n}}\ \le\ \frac{2}{\sqrt{\log 2}}\approx 2.402,\qquad A(n):=|A\cap[0,n)|,$$ and in particular $\liminf_{n\to\infty}A(n)/\sqrt n=0$.

Generalization (O'Bryant, arXiv:2606.28651, submitted 26 Jun 2026 — six days before this page was written). Call $A$ a $\gamma$-Golomb ruler if every $d>0$ has at most $\gamma$ pairs $(a,b)\in A\times A$ with $d=a-b$ (bounded-multiplicity *differences*; $\gamma=1$ = Sidon). Then every infinite $\gamma$-Golomb ruler $A$ satisfies $$\liminf_{n\to\infty}\frac{A(n)}{\sqrt{n/\log n}}\ \le\ \frac{2}{\sqrt{\log 2}}\sqrt\gamma.$$ This is the direct bounded-multiplicity generalization of the $g=1$ theorem above, proved by a natural extension of the same technique ("the extension from Sidon sets to $\gamma$-Golomb rulers is new, but easy" — O'Bryant's own words).

Facts

- erdosproblems.com/158 citation tag is [ESS94] = P. Erdős, A. Sárközy, V. T. Sós, "On sum sets of Sidon sets I," *J. Number Theory* 47 (1994), 329–347 — the paper that raised the sum-bounded $B_2[2]$ liminf question as open (title/venue corroborated via web search of citing literature; full text not independently obtained, paywalled). - History of the solved $g=1$/Sidon case: Erdős's original result appears not to have an independent citable publication of its own — the earliest citable source found is Alfred Stöhr, "Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, II," J. Reine Angew. Math. 194 (1955), 40–65, 111–140, §12aβ, which reports *two* results explicitly attributed to Erdős: (a) there is an infinite Sidon set with $\limsup A(n)/\sqrt n\ge 1/2$; (b) every infinite Sidon set has $\liminf A(n)/\sqrt n=0$, refined by Stöhr to the sharper quantitative form $\liminf A(n)\sqrt{\log n}/\sqrt n\ll 1$. Both are also reported as Theorems 8–9 of Chapter II in **Halberstam & Roth, *Sequences, Vol. I*** (Clarendon Press, 1966) [source: Kevin O'Bryant, "A Complete Annotated Bibliography of Work Related to Sidon Sequences," EJC DS11 (2004), arXiv:math/0407117, bibliography entry [12]]. - Stöhr himself then *asked* (in the same 1955 paper) how small $\liminf A(n)\sqrt{\log n}/\sqrt n$ could be, and whether $0$ is forced, or whether some Sidon set keeps it strictly positive — this quantitative refinement is still open today as erdosproblems.com/1191, documented on this wiki as Erdős #1191 — how small can an infinite Sidon set's liminf density be? (which is the natural "how sharp is the solved bound" companion to this page, not to be confused with #158's different sum-vs-difference generalization axis). - Constant-sharpening chain (the $2/\sqrt{\log2}$ constant above): Erdős/Stöhr established only *finiteness* of the liminf bound (no explicit constant); Javier Cilleruelo, lecture notes "Conjuntos de Sidon" (AGRA II, ICTP-CIMPA, Cusco, Peru, 2015) gave the explicit constant $8\sqrt7\approx21.2$ and suggested reaching $4$ as an exercise; Kevin O'Bryant, "The Thickness of Infinite Sidon Sets," arXiv:2606.28651 (26 Jun 2026) pushed the constant down to $2/\sqrt{\log2}\approx2.402$ — the current record — and states "we believe that we have fully optimized this argument." - The $\gamma$-Golomb-ruler generalization is genuinely new (June 2026): before O'Bryant's paper, the bounded-multiplicity liminf bound was known only for $\gamma=1$ (Sidon); the paper's Theorem 1, quoted above, is stated and proved for all integers $\gamma\ge1$ in one uniform argument. - Companion (limsup, not liminf) result, same paper's Theorem 2 — context, not the main content of this page: every $\gamma$-Golomb ruler has $\limsup A(n)/\sqrt n\le\sqrt\gamma$ (Erdős gave constant $1/2$ for $\gamma=1$, sharpened by Fritz Krückeberg, *J. Reine Angew. Math.* 206 (1961), 53–60, to $2^{-1/2}$); a matching construction gives $\limsup A(n)/\sqrt n\ge(1/\sqrt2)\sqrt\gamma$ for a $\gamma$-Golomb ruler, built by gluing finite-field near-optimal $\gamma$-Golomb rulers (Caicedo–Martos–Trujillo, *Rev. Integr. Temas Mat.* 33 (2015), 161–172) across rapidly-separated scales. - Crucial precision gap, flagged explicitly: erdosproblems.com's actual #158 is phrased with bounded sums ($a+b=n$, at most $g$ solutions — the classical $B_2[g]$ notion used by Erdős–Sárközy–Sós, Cilleruelo, Plagne, Habsieger–Plagne in the finite-density literature), whereas O'Bryant's $\gamma$-Golomb ruler is phrased with bounded differences ($a-b=d$, at most $\gamma$ solutions). These two notions coincide only at multiplicity $1$ (the classical fact that a Sidon set has distinct sums iff it has distinct differences — see Sidon sets / B_2 sets / Golomb rulers); no source found in this search establishes an equivalence (even up to constants) between sum-bounded-$g$ and difference-bounded-$\gamma$ multiplicity for $g,\gamma\ge2$. So O'Bryant's 2026 theorem is the closest known generalization of the solved $g=1$ result and directly demonstrates the *technique* extends past Sidon sets — but it does not itself settle the actual (sum-bounded) erdosproblems.com/158. - Elementary counting fact, true and easy, for the sum-bounded side too (not new, included for completeness): any finite $B_2[g]$ set (sum-bounded) in $\{1,\ldots,N\}$ has size $O(\sqrt{gN})$ by the same pigeonhole double-counting used for Sidon sets — this is the finite ceiling that erdosproblems.com/158 asks whether an *infinite* $B_2[2]$ set must dip below infinitely often (in the liminf sense), exactly mirroring what Erdős proved for $g=1$.

Solution

The transferable technique: partition into growing blocks, bound the block "energy" $\sum_\ell(\text{count in block }\ell)^2$ two different ways — once using the bounded-multiplicity hypothesis (upper bound), once using a weighted Cauchy–Schwarz argument fed by the liminf assumption itself (lower bound) — and let the two bounds collide as the block length $\to\infty$.

This is the same technique used by Erdős/Stöhr in 1955 and reproved with the current-best constant, and *generalized wholesale from bounded differences at $\gamma=1$ to arbitrary $\gamma$*, by O'Bryant (2026). Concretely (following O'Bryant's proof of Theorem 1):

1. Set up a running infimum. For a threshold $N$, define $\tau_N:=\inf_{n\ge N}A(n)\sqrt{\log n/n}$. This is exactly the quantity whose $N\to\infty$ limit is the liminf being bounded; the whole proof is a mechanism for capping $\tau_N$. 2. Cut $[0,\infty)$ into blocks of length $N$, with a free choice of offset $t\in[0,N)$: $F^{(t)}_\ell:=|A\cap[t+(\ell-1)N,\,t+\ell N)|$. Average over the offset and select the specific offset $T$ that does at least as well as the average — this one move removes an otherwise-unavoidable boundary/edge-effect term and is what turns a soft averaged bound into a genuine per-instance bound. 3. Upper-bound the energy via the bounded-multiplicity hypothesis. Any pair of elements of $A$ with difference $d<N$ is counted in some $F^{(t)}_\ell$ for roughly $N-d$ choices of offset $t$; summing this over all offsets and using that each difference $d$ has at most $\gamma$ representations (the defining bounded-multiplicity property) collapses a double sum into $E=\sum_\ell F_\ell^2\le\gamma N+o(N)$ — a clean linear-in-$N$ ceiling that only uses the hypothesis, nothing about the liminf assumption. 4. Lower-bound the same energy via weighted Cauchy–Schwarz, fed by the liminf assumption. Apply Cauchy–Schwarz with weights $w_\ell=(\ell\,\log(e\ell N))^{-1/2}$ (chosen, not arbitrary — this specific decay rate is what makes the sum telescope cleanly) to get $E\ge(\sum_\ell w_\ell F_\ell)^2/\sum_\ell w_\ell^2$. Bound the denominator by an integral comparison ($\sum w_\ell^2\le\log2+o(1)$), and lower-bound the numerator by summation by parts, injecting the assumption that $A(n)\ge\tau_N\sqrt{n\log n}$ at every scale $n\ge N$ (that is literally what $\tau_N$ encodes) — this produces $E\ge\tau_N^2\,(\log2/4)\,N+o(N)$: an energy lower bound that grows with $\tau_N$. 5. Collide the two bounds. Since both bounds are for the *same* quantity $E$, as $N\to\infty$: $\tau_N^2\log2/4\le\gamma$, i.e. $\tau_N\le(2/\sqrt{\log2})\sqrt\gamma$ for all $N$ — exactly Theorem 1.

Why this is the reusable part. - The core move is turning "bounded multiplicity" into an energy (second-moment) ceiling, and turning "liminf density stays high" into an energy floor that grows without bound in the assumed density — forcing a contradiction unless the density dips. This is a general recipe for *any* infinite combinatorial object with (i) a local bounded-multiplicity/collision constraint and (ii) a candidate density lower bound to falsify: block it, energy-bound it two ways, let $N\to\infty$. - The specific weight profile $w_\ell\propto(\ell\log(\ell N))^{-1/2}$ is the log-saving trick. A naive/uniform-weight Cauchy–Schwarz only reproduces the trivial finite-interval bound (no log gain); the $1/\sqrt{\log}$-decaying weight is precisely tuned so that summation by parts against a $\sqrt{n\log n}$-shaped assumed lower bound telescopes to a clean constant ($\log2$) rather than diverging or vanishing — this is the one nontrivial idea in the whole argument, and it is exactly the kind of "reverse-engineer the weight from the target asymptotic" move that recurs across this wiki's other second-moment-method solved pages (cf. Pliego 2024 — sharp density-vs-boundedness trade-off for $B_2[g]$ sequences's reverse-engineered inclusion probability). - The extension from $\gamma=1$ (differences bounded by 1, i.e. Sidon) to general $\gamma$ is a one-line change: step 3's "at most one representation per difference" becomes "at most $\gamma$," which just rescales the energy upper bound linearly in $\gamma$ — nothing else in the argument (the weighted-C-S machinery of step 4) needs to change. This is exactly why O'Bryant calls the generalization "new, but easy," and it is the concrete evidence that this technique family is a genuine transferable engine, not a one-off trick tied to Sidon sets specifically. - What would be needed to reuse this on the actual (sum-bounded) #158: step 3's energy upper bound currently exploits the *difference*-bounded hypothesis directly (pairs sharing a difference $d$). A sum-bounded hypothesis ($a+b=n$, $\le2$ solutions) does not immediately give the same per-block collision count — the natural next step for anyone attacking the true erdosproblems.com/158 is re-deriving an analogous energy upper bound from sum-collisions (rather than difference-collisions) inside each block, then re-running the identical weighted-Cauchy–Schwarz lower bound unchanged. This translation step is exactly the open gap flagged above and is the concrete, well-defined starting point this solved page hands to #158 and to Erdős #1191 — how small can an infinite Sidon set's liminf density be?.

Related

- Erdős #1191 — how small can an infinite Sidon set's liminf density be? — open: the direct quantitative refinement of *this page's own* $g=1$/Sidon result — asks whether the liminf constant can be forced all the way to $0$ (vs. merely bounded, which is what's proved here), and (Q2) whether some Sidon set keeps $\liminf A(n)\sqrt{\log n}/\sqrt n$ strictly positive. Cites the identical Erdős/Stöhr/O'Bryant chain as this page. - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the limsup companion problem to the liminf question addressed here (mentioned via wiki/problems/1191.md's cross-reference); Theorem 2 of O'Bryant's paper (Erdős/Krückeberg constant, $\gamma$-Golomb generalization) bears on it directly. - Sidon sets / B_2 sets / Golomb rulers — parent concept page; documents the sum/difference equivalence at multiplicity 1, the classical finite-Sidon density ceiling $N^{1/2}$, and already cites this exact liminf theorem and O'Bryant's 2026 generalization in its own Facts section. - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — the named technique family (block partition + energy double-count + weighted Cauchy–Schwarz telescoping over scales) this page's Solution documents in full technical detail; the sole known technique behind every bound on the Sidon/$\gamma$-Golomb liminf-density family since 1955. - Pliego 2024 — sharp density-vs-boundedness trade-off for $B_2[g]$ sequences — sibling solved page on the *sum-bounded* $B_2[g]$ family (the same object erdosproblems.com/158 itself concerns), but answering a different question (density-vs-additive-basis trade-off, not liminf density); its probabilistic-construction technique is a useful contrast to this page's purely deterministic energy-bound technique, and together they map the two ends (existence-of-dense-construction vs. forced-thinness) of the same $B_2[g]$ territory that #158 sits inside. - Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #28 — additive basis forces unbounded representations — the broader Erdős–Turán-conjecture cluster on bounded representation functions for additive bases, adjacent territory sharing the same $B_2[g]$ object family.