Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998)

Statement

Erdős asked (relaying Sidon's 1932 question, and explicitly as "is there an infinite Sidon sequence $a_1<a_2<\cdots$ with $a_k=o(k^{3-\epsilon})$ for every $\epsilon>0$") whether the exponent $1/3$ — the density achieved by the trivial greedy algorithm — could be beaten by *any* infinite Sidon set (a set $A\subset\mathbb N$ with all pairwise sums $a+a'$, $a\le a'\in A$, distinct). For 50 years the greedy bound $A(x)\gg x^{1/3}$ (where $A(x):=|A\cap[1,x]|$) stood unimproved; Ajtai–Komlós–Szemerédi (1981) pushed it to $A(x)\gg(x\log x)^{1/3}$ via a new semi-random ("nibble") method, still writing in their own paper that "the task of constructing a denser sequence has so far resisted all efforts, both constructive and random methods" (quoted in Cilleruelo arXiv:1209.0326 §1).

Ruzsa's theorem (1998): there exists an infinite Sidon set $A\subset\mathbb N$ with counting function $$A(x) = x^{\sqrt2-1+o(1)}, \qquad \sqrt2-1\approx0.41421,$$ strictly beating the exponent $1/3\approx0.333$ of every prior construction. (I.Z. Ruzsa, "An infinite Sidon sequence," *J. Number Theory* 68 (1998), 63–71, MR 99a:11014.)

Facts

- This exponent is still the record, 28 years later. O'Bryant, "The Thickness of Infinite Sidon Sets," arXiv:2606.28651 (26 Jun 2026), states explicitly that Ruzsa's $x^{\sqrt2-1+o(1)}$ "remains the record for an infinite set." The matching *upper*-bound question — is there an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$ for all $\epsilon$? — is Erdős's $500 open problem Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, still unresolved; Ruzsa's construction is the current best lower bound toward it, with a large unclosed gap ($0.4142$ vs. the conjectured-achievable $0.5$). - Ruzsa's proof is non-constructive — an existence proof via a positive/full-measure probabilistic argument over a continuous real parameter $\alpha$, not an explicit formula. Cilleruelo, arXiv:1209.0326 (2012), later gave the first explicit, deterministic construction matching the identical exponent $\sqrt2-1$, using a discrete logarithm mod a sequence of primes in place of Ruzsa's real logarithm/parameter $\alpha$ — confirming the exponent is a genuine structural threshold, not an artifact of the probabilistic method. - The core arithmetic input is multiplicative-to-additive transfer. The primes are a *multiplicative* Sidon set (unique factorization: $pq=rs\Rightarrow\{p,q\}=\{r,s\}$), so $\{\log p:p\text{ prime}\}$ is an *additive* Sidon set of reals. This one fact is the seed of every record infinite-Sidon construction since 1998, and Cilleruelo–Tesoro (arXiv:1206.3087) show the same seed, replayed with a variant encoding, generalizes to $B_3,B_4$ sequences with exponent $x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$. - Maldonado's simplification (arXiv:1103.5732, 2011) replaces $\log p$ (unbounded, which forces delicate case-by-case handling in Ruzsa's original argument) with the argument $\varphi_p\in[0,1)$ of a Gaussian prime factor of $p\equiv1\pmod4$ (i.e. $p=\rho_p\bar\rho_p$ in $\mathbb Z[i]$, $\bar\rho_p/\rho_p=e^{2\pi i\varphi_p}$): $(\varphi_p)$ is additively Sidon over $\mathbb R/\mathbb Z$ by the same unique-factorization argument, now in the Gaussian integers, and is bounded, which removes the main technical headache while reproducing the identical exponent $\sqrt2-1$. - The finite warm-up version is completely elementary: for $p$ prime, $p\le\sqrt n/(2\log n)$, the set $X=\{[\,\frac{2n}{\log n}\log p\,]\}$ is already a Sidon set of size $\sim\sqrt{2n}/\log^{3/2}n$ in $\{1,\dots,n\}$ — a one-page proof using only $|\{x\}+\{y\}-\{z\}-\{w\}|\le2$ and unique factorization (Maldonado, Thm 2.1). The hard part of Ruzsa's paper is entirely in extending this trick from a *finite truncation* to a genuine *infinite* set without the density collapsing.

Solution

The transferable idea: encode a multiplicatively-Sidon arithmetic object (primes, via unique factorization) into a real-valued additively-Sidon sequence via logs/discrete logs, then use a "blockwise-independent" digit-encoding to discretize it into integers, and finish with a probabilistic-existence + alteration (delete-the-bad-elements) argument to force exact Sidon-ness without losing the exponent. Four stages:

1. Multiplicative $\to$ additive transfer via logarithms. Since the primes have unique factorization, $pq=rs\Rightarrow\{p,q\}=\{r,s\}$ for primes $p,q,r,s$ — i.e. $\{p\}$ is Sidon under *multiplication*. Taking logs converts this for free into: $\{\log p:p\text{ prime}\}$ is Sidon under *addition*, over $\mathbb R$. (Maldonado's variant does the same with Gaussian-integer factorization and the *argument* $\varphi_p$ of a Gaussian prime factor, landing in the bounded group $\mathbb R/\mathbb Z$ instead of unbounded $\mathbb R^+$ — same trick, better-behaved target.) This single move is why the exponent $\sqrt2-1$ shows up at all: it converts an *infinite, unbounded-density* combinatorial question about integers into a much more tractable equidistribution/Diophantine-approximation question about a sequence of reals.

2. A one-real-parameter family, not one fixed sequence. Rather than trying to discretize $\{\log p\}$ (or $\{\varphi_p\}$) directly — which fails, because rounding to integers creates spurious near-collisions — Ruzsa introduces a free real parameter $\alpha\in[1,2)$ and studies the *whole family* $A_\alpha=(a_p)_{p\in P}$ simultaneously, where $a_p$ is built from the binary digits of $\alpha\log p$ (resp. $\alpha\varphi_p$). This is the "probabilistic method with a continuous parameter" pattern: instead of choosing a random subset directly, randomize a single scalar knob that controls a whole deterministic construction, then prove almost every value of the knob works.

3. Digit block-encoding with zero-buffers to force "blockwise independence." The binary expansion of $\alpha\varphi_p$ is chopped into consecutive blocks $\Delta_{1p},\Delta_{2p},\dots,\Delta_{K_p,p}$ of *quadratically growing* length ($|\Delta_{ip}|\sim i^2$ bits), each block separated by a run of zero bits, and reassembled (with an extra leading block encoding the magnitude class $K_p\sim(\log p)^{1/\beta}$ exactly) into the integer $a_p$. The zero-buffers are the key device: when four such integers are added, $a_p+a_q=a_r+a_s$, no bit-carry can cross a buffer, so the equation is forced to hold block by block ($\Delta_{ip}+\Delta_{iq}=\Delta_{ir}+\Delta_{is}$ for every $i$) and, separately, exactly on the leading magnitude blocks ($K_p=K_r$, $K_q=K_s$ after WLOG ordering) — turning one hard global arithmetic identity over huge integers into a matched system of small, per-block digit conditions plus an exact magnitude-matching condition, which is what makes the subsequent counting argument tractable at all. (This "insert deliberate zero-gaps so additions decompose into independent sub-problems" move is a general discretization trick usable anywhere a real-valued additive structure needs to be ported into $\mathbb Z$ without cross-scale interference.) 4. Probabilistic existence (measure argument) + alteration (delete the bad tuples). Call $(p,q,r,s)$ a bad 4-tuple if $a_p+a_q=a_r+a_s$ (a genuine collision, i.e. $A_\alpha$ fails to be Sidon there). Because of the block decomposition, a bad 4-tuple forces a rigid congruence on the digit expansions, e.g. $m_p\equiv m_r\pmod{2^{K^2-L^2}}$ (Maldonado's Lemma 4.1). For fixed $p,q,r,s$, the set of $\alpha\in[1,2)$ for which this congruence holds is then shown, by a direct interval-counting argument, to have small Lebesgue measure, $\mu\{\alpha:\text{collision}\}\ll2^{L^2-K^2}$ (Lemma 4.2) — small because the primes/Gaussian-prime-arguments are equidistributed enough that the map $\alpha\mapsto$ (digits of $\alpha\varphi_p$) behaves like an independent random rounding. Summing this measure bound over all candidate bad 4-tuples of a given size shows: (a) the total *bad measure* is $<1$, so a positive- (in fact almost-full-) measure set of $\alpha$ gives a sequence $A_\alpha$ with only a controllably sparse set of collisions, and (b) the expected/counted number of bad tuples up to $x$ is $o(x^{\sqrt2-1})$ — so deleting one element (the largest) from every bad 4-tuple (the classical *alteration method*: build something slightly wrong, then prune the flaws) removes a negligible fraction of $A_\alpha\cap[1,x]$ and leaves a genuine, exactly-Sidon set with the same leading exponent $x^{\sqrt2-1+o(1)}$.

Why the answer is the specific number $\sqrt2-1$

the block-length schedule ($|\Delta_{ip}|\sim i^2$, magnitude class $K_p\sim p^\beta$-scaled) has one free shape-parameter that trades off two competing effects — coarser blocks make more numbers collide (worse), finer blocks waste bits and thin out the achievable density (also worse) — and $\sqrt2-1$ is exactly the value of that parameter at which the two error sources balance; Cilleruelo's later explicit construction (Theorem 1.1) first reaches only the sub-optimal $c=\frac{3-\sqrt5}{2}$ with the naive (no-deletion) scheme, and recovers the full $\sqrt2-1$ only after adding the same deletion/pruning idea (his Theorem 1.2) — direct confirmation that the alteration step, not just the encoding, is what buys the extra density.

Why this transfers: any time a target combinatorial-extremal object over $\mathbb Z$ (or $\mathbb N$) is secretly the image of a much cleaner algebraic-Sidon-type object living over $\mathbb R$ or $\mathbb R/\mathbb Z$ (via logs of a unique-factorization structure, arguments of Gaussian/algebraic primes, discrete logs mod a prime, etc.), the recipe (i) transfer to the real/torus setting via an exp↔log-type map, (ii) introduce one scalar randomization parameter and a zero-buffered block/digit encoding to discretize without cross-scale interference, (iii) bound the measure of "bad" parameter values by direct counting, (iv) delete the residual sparse set of collisions via alteration is a fully reusable four-step engine — it is exactly what Cilleruelo–Tesoro reran (with $\theta(p)$, Gaussian primes) to reach $B_3,B_4$ sequences, and it is the template any attempt to beat $\sqrt2-1$ (toward Erdős's conjectured $1/2-\epsilon$, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) or to formalize the result in Lean would have to either optimize further or replace outright.

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the still-open $500 Erdős problem this construction is the current record lower bound for: is there an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$? Ruzsa's exponent $\sqrt2-1\approx0.4142$ is unimproved since 1998 per O'Bryant arXiv:2606.28651 (26 Jun 2026); this page is the technique writeup that problem page's "Facts" section points back to. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ (distinct-triple-sum) infinite-density analogue; Cilleruelo–Tesoro (arXiv:1206.3087) extend this exact construction's exponent formula to $h=3,4$. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set sharp-asymptotics sibling; unrelated construction (Singer, finite-field) but same overall "construction vs. matching upper bound" game one level down (finite instead of infinite density). - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — liminf-oscillation question for infinite Sidon sets; same problem cluster, different extremal statistic. - Singer's finite-field perfect difference set construction (1938) — the sibling *finite*-Sidon-set solved-construction page; structurally the same "arithmetize a Sidon-type structure via a cyclic/multiplicative group, then read off a dense integer set" strategy, but via finite-field collineations instead of a real-parameter digit encoding — the two solved pages together bracket the whole Sidon-set toolkit (finite: exact algebraic optimum; infinite: probabilistic/discretized near-optimum). - Sidon sets / B_2 sets / Golomb rulers — the central object and concept page; already documents this construction as Fact/Technique #3 ("log/discrete-log trick"), of which this page is the full derivation. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the semi-random method used by Ajtai–Komlós–Szemerédi (1981) for the prior record $(x\log x)^{1/3}$; a *different* probabilistic engine (iterative sparse random deletion) than Ruzsa's single-parameter-plus-alteration method, useful as a contrast in what "probabilistic construction" can mean in this area. - Discrete-logarithm explicit Sidon construction (Cilleruelo) — Cilleruelo's explicit derandomization of this exact construction (arXiv:1209.0326), matching the same exponent $\sqrt2-1$ without any measure-theoretic existence step. - concept/dissociated-sets — the $\{-1,0,1\}$-linear-combination reformulation of the Sidon condition used in related Ruzsa constructions.