Ruzsa's infinite Sidon set of density $x^{\\sqrt2-1+o(1)}$ (1998) — current record

Statement

A Sidon set (or $B_2$ set) $A\subset\mathbb N$ is a set with all pairwise sums $a+a'$ ($a\le a'\in A$) distinct. Let $A(x):=|A\cap[1,x]|$. The greedy algorithm gives an infinite Sidon set with $A(x)\gg x^{1/3}$, unimproved for 50 years except for Ajtai–Komlós–Szemerédi's 1981 semi-random "nibble" refinement to $A(x)\gg(x\log x)^{1/3}$ — the authors' own paper noted "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). Erdős asked (relaying Sidon's original 1932 question) whether any infinite Sidon set could beat exponent $1/3$ at all, and separately conjectured the true ceiling is $1/2-\epsilon$ for every $\epsilon>0$ — the still-open $\$500$ problem Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set.

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

Facts

- Still the record 28 years later. O'Bryant, arXiv:2606.28651 (26 Jun 2026), states Ruzsa's $x^{\sqrt2-1+o(1)}$ "remains the record for an infinite set." The matching upper bound — an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$ — is Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, open, with a large unclosed gap between $0.4142$ and the conjectured $0.5$. - Non-constructive originally. Ruzsa's 1998 proof is a probabilistic existence argument over a continuous real parameter $\alpha$. Cilleruelo (arXiv:1209.0326) later gave a fully explicit deterministic construction hitting the identical exponent $\sqrt2-1$, using discrete logarithms mod a sequence of auxiliary primes instead of a real logarithm — evidence the exponent is a genuine structural threshold of the technique, not an artifact of randomness. - The seed idea: multiplicative Sidon $\to$ additive Sidon. Primes have unique factorization, so $pq=rs\Rightarrow\{p,q\}=\{r,s\}$: the primes are *multiplicatively* Sidon. Taking logarithms transfers this for free into $\{\log p\}$ being *additively* Sidon over $\mathbb R$. This single fact seeds every record infinite-Sidon construction since 1998, including Cilleruelo–Tesoro's extension (arXiv:1206.3087) to $B_3,B_4$ sequences with exponent $x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$. - Finite elementary warm-up. For prime $p\le\sqrt n/(2\log n)$, the set $X=\{\lfloor\frac{2n}{\log n}\log p\rfloor\}$ is already Sidon in $\{1,\dots,n\}$ of size $\sim\sqrt{2n}/\log^{3/2}n$ — a one-page proof from $|\{x\}+\{y\}-\{z\}-\{w\}|\le2$ plus unique factorization (Maldonado, Thm 2.1). The hard part of the 1998 paper is pushing this from a finite truncation to a genuine infinite set without the exponent collapsing. - Maldonado's simplification (arXiv:1103.5732) replaces the unbounded $\log p$ with the bounded argument $\varphi_p\in[0,1)$ of a Gaussian-prime factor of $p\equiv1\pmod4$; unique factorization in $\mathbb Z[i]$ makes $(\varphi_p)$ additively Sidon just as $(\log p)$ is, over the bounded group $\mathbb R/\mathbb Z$, reproducing the same exponent $\sqrt2-1$ with less bookkeeping.

Solution

The transferable idea: encode a *multiplicatively*-Sidon arithmetic object (primes, via unique factorization) into a real-valued *additively*-Sidon sequence via logarithms; discretize it into integers with a zero-buffered, "blockwise-independent" digit encoding; then finish with a probabilistic-existence-plus-alteration (delete-the-bad-elements) argument to force exact Sidon-ness without losing the exponent.

1. Multiplicative → additive transfer via logs. Unique factorization gives $pq=rs\Rightarrow\{p,q\}=\{r,s\}$, i.e. $\{p\}$ is Sidon under multiplication. Logs convert this into: $\{\log p\}$ is Sidon under addition over $\mathbb R$. This move turns an unbounded-density integer question into a tractable equidistribution/Diophantine-approximation question about reals. 2. A one-real-parameter family. Directly discretizing $\{\log p\}$ fails (rounding creates spurious near-collisions). Ruzsa instead studies the whole family $A_\alpha=(a_p)_{p\in P}$ for $\alpha\in[1,2)$, where $a_p$ is built from the binary digits of $\alpha\log p$ — probabilistic method with a continuous knob controlling a deterministic construction, then showing almost every value of the knob works. 3. Digit block-encoding with zero-buffers. The binary expansion of $\alpha\log p$ is chopped into blocks of quadratically growing length, separated by runs of zero bits, and reassembled into $a_p$ (with a leading block encoding the magnitude class). Because no bit-carry can cross a zero buffer, a collision $a_p+a_q=a_r+a_s$ is forced to hold block by block — turning one hard global integer identity into a matched system of small per-block digit conditions. This "insert deliberate zero-gaps so additions decompose into independent sub-problems" move is reusable anywhere a real-valued additive structure must be ported into $\mathbb Z$ without cross-scale interference. 4. Probabilistic existence + alteration. Call $(p,q,r,s)$ a *bad 4-tuple* if $a_p+a_q=a_r+a_s$. The block structure forces a rigid digit congruence for any bad tuple; for fixed $p,q,r,s$ the measure of $\alpha\in[1,2)$ satisfying it is shown to be small, $\ll2^{L^2-K^2}$ (Maldonado's Lemma 4.2). Summing over all candidate bad tuples shows the total bad measure is $<1$ (so almost every $\alpha$ works) and the count of bad tuples up to $x$ is $o(x^{\sqrt2-1})$. Deleting the largest element of every bad 4-tuple — the classical alteration method — removes a negligible fraction of $A_\alpha\cap[1,x]$, leaving an exactly Sidon set with unchanged leading exponent.

Why $\sqrt2-1$ specifically: the block-length schedule has one free shape parameter trading off two competing error sources — coarser blocks create more collisions, finer blocks waste bits and thin the density — and $\sqrt2-1$ is exactly where they balance (solving $\beta^2-2\beta-1=0\Rightarrow\beta=1+\sqrt2$, $1/\beta=\sqrt2-1$, per Maldonado's derivation). Cilleruelo's explicit construction first reaches only $c=(3-\sqrt5)/2\approx0.382$ with no deletion step (Thm 1.1), recovering the full $\sqrt2-1$ only after adding the identical deletion/pruning idea (Thm 1.2) — direct confirmation that the alteration step, not just the encoding, buys the extra density.

Why this transfers: whenever a target extremal object over $\mathbb Z$ is secretly the image of a cleaner algebraic-Sidon-type object over $\mathbb R$ or $\mathbb R/\mathbb Z$ (via logs of a unique-factorization structure, discrete logs mod a prime, arguments of algebraic primes), the four-step engine — (i) transfer via an exp↔log map, (ii) randomize with one scalar parameter plus a zero-buffered digit encoding, (iii) bound "bad" parameter measure by direct counting, (iv) delete the residual sparse collisions via alteration — is fully reusable. It is exactly what Cilleruelo–Tesoro reran for $B_3,B_4$ sequences, and it is the template any attempt to close the gap toward Erdős's conjectured $1/2-\epsilon$ (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) must either optimize further or replace.

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the still-open $\$500$ Erdős problem this construction is the record lower bound for: an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$? Unimproved gap between $0.4142$ (Ruzsa) and $0.5$ (conjectured). - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ infinite-density analogue; Cilleruelo–Tesoro (arXiv:1206.3087) extend this exact technique'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 (Singer's finite-field construction, different technique, same construction-vs-upper-bound game one level down). - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — liminf-oscillation question for infinite Sidon sets; same problem cluster. - Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) — near-duplicate sibling solved-problem page at an adjacent slug covering this identical result in greater depth (finite warm-up proof, full bad-4-tuple measure argument, Cilleruelo's discrete-log derandomization); treat the two as companions. - Sidon sets / B_2 sets / Golomb rulers — the central object/concept page. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — deep-dive concept page on this construction and Cilleruelo's discrete-log analogue. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the earlier (1981) semi-random alternative probabilistic engine (Ajtai–Komlós–Szemerédi), contrast case for "probabilistic construction." - Discrete-logarithm explicit Sidon construction (Cilleruelo) — Cilleruelo's explicit derandomization matching exponent $\sqrt2-1$. - concept/dissociated-sets — the $\{-1,0,1\}$-linear-combination reformulation of the Sidon condition, used in related Ruzsa constructions.