Ruzsa's log-of-primes probabilistic Sidon construction

Statement

**Theorem (I. Ruzsa, "An Infinite Sidon Sequence," *J. Number Theory* 68 (1998), 63–71).** There exists an infinite Sidon set $A\subset\mathbb N$ — a set with all pairwise sums $a+a'$ ($a\le a'\in A$) distinct — whose counting function satisfies $$A(x) := |A\cap\{1,\dots,x\}| = x^{\sqrt2-1+o(1)}, \qquad \sqrt2-1\approx0.41421\ldots$$ This broke the exponent-$1/3$ barrier standing since Erdős's 1930s greedy construction (only shaved by a $\log$ factor via the Ajtai–Komlós–Szemerédi nibble method in 1981, giving $(x\log x)^{1/3}$), and — as of mid-2026 — is still the largest known exponent for an infinite Sidon set (confirmed unimproved by K. O'Bryant, arXiv:2606.28651, 26 Jun 2026).

The construction, precisely. The starting observation is a one-line consequence of unique factorization:

> The primes are a multiplicatively Sidon set: $p_1p_2=p_3p_4$ for primes forces $\{p_1,p_2\}=\{p_3,p_4\}$. Equivalently, $\{\log p : p \text{ prime}\}$ is an additively Sidon set of real numbers: $\log p_1+\log p_2=\log p_3+\log p_4 \iff p_1p_2=p_3p_4$.

If one could use the exact real numbers $\log p$ directly as set elements this would already solve the problem — but $\{\log p\}$ isn't a set of integers, and truncating $\log p$ to finite precision to force it into $\mathbb N$ can *manufacture* additive coincidences that were not present in the exact reals. Ruzsa's construction is the machinery for discretizing $\{\log p\}$ into an honest subset of $\mathbb N$ without losing the multiplicative-exactness that makes it Sidon, and it is probabilistic: it does not exhibit one explicit winning set but shows that "most" instances of a randomized family work.

Concretely (Cilleruelo's summary of Ruzsa's argument, from the Erdős Centennial 2013 slides, slide 8): Ruzsa introduces a real random parameter $\alpha\in[1,2]$ and, for each prime $p$, forms the real number $\alpha\log p$, takes its binary expansion, and cuts that expansion into growing blocks (separated by zero-padding "spacer" digits so that additive carries can never cross a block boundary), reassembling the blocks into a single integer $a_p$. This defines a sequence $$A_\alpha = (a_p)_{p\in\mathcal P}.$$ He then proves: for almost all $\alpha\in[1,2]$ (Lebesgue-a.e., via a first/second-moment argument on the expected number of "bad" collision-producing 4-tuples at each dyadic scale), the number of additive collisions in $A_\alpha$ is small enough that deleting one element from every colliding 4-tuple removes only a vanishing fraction of $A_\alpha$ at every scale, leaving a genuine Sidon set with counting function $x^{\sqrt2-1+o(1)}$. The exponent $\sqrt2-1$ itself falls out of optimizing the one free parameter of the construction (the block-growth rate, controlling the trade-off between "raw density of digit-blocks" and "probability of a collision at that scale") — solving a quadratic $\beta^2-2\beta-1=0$ for $\beta=1+\sqrt2$, i.e. $1/\beta=\sqrt2-1$ (worked out explicitly in the simplified re-derivation, Maldonado López, arXiv:1103.5732, Theorem 4.5, attributed there directly to Ruzsa 1998).

Facts

- Existence, not exhibition. The theorem asserts a Sidon set exists with the stated density; the proof gives no algorithm to produce it (nor even a single explicit value of $\alpha$ known to work) — only that the "bad" set of $\alpha$'s has Lebesgue measure zero. This is the defining feature that separates Ruzsa's construction from the *later*, *explicit* discrete-logarithm analogue by Cilleruelo (arXiv:1209.0326, 2012/2013) that matches the same exponent $\sqrt2-1$ without any randomness — see Discrete-logarithm explicit Sidon construction (Cilleruelo). - The exponent $\sqrt2-1$ has stood unimproved for 28 years (1998–2026), across two structurally different reproofs (Ruzsa's original real-log/random-$\alpha$ route and Cilleruelo's discrete-log derandomization), which is circumstantial evidence it is a genuine ceiling of the log/discrete-log technique family, not an artifact of one execution. The conjectured truth (Erdős, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) is density $x^{1/2-\epsilon}$ for every $\epsilon>0$ — a $500 problem still open. - Two competing costs are being balanced. As with essentially every "build dense random structure, then delete the collisions" construction, the exponent is fixed by equating (a) the raw density gained by using longer digit-blocks / bigger prime ranges at scale $k$, against (b) the density of "bad" (repeat-sum) 4-tuples created by discretization at that same scale — the block-growth-rate parameter is chosen at exactly the point where these two exponential rates balance, which is what produces the specific irrational number $\sqrt2-1$ rather than some other constant. - Not the first probabilistic Sidon construction, but the density record-setter. Ajtai–Komlós–Szemerédi (1981) had already used a semi-random "nibble"-type construction to beat the trivial greedy exponent $1/3$, reaching $(x\log x)^{1/3}$ — historically the origin of the semi-random/nibble method later generalized across combinatorics (see Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings). Ruzsa's 1998 log-of-primes idea is a *different* randomization mechanism (parametrized digit-truncation of an exact real-valued Sidon sequence, not incremental random deletion) that jumped straight to $\sqrt2-1\approx0.414$, well past the nibble-method exponent $1/3$. - Later generalized to $B_h$ sets ($h\ge3$, all $h$-fold sums distinct) by essentially the same log-of-primes idea plus a variant randomization, giving density $x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$ (Cilleruelo–Tesoro, arXiv:1206.3087, and Cilleruelo arXiv:1209.0326 §3) — direct evidence the "transport multiplicative Sidon-ness of the primes into an additive setting via a logarithm" idea is a reusable engine, not a one-off trick for $h=2$.

Technique

WHEN it applies. Whenever a problem asks for a dense/large subset of the integers (or another additively-structured set) that must avoid a repeated additive relation of the *sum-collision* type ($a+b=c+d$, or more generally an $h$-fold sum collision), and a genuinely *multiplicative* structure with the analogous no-collision property is available to seed the construction. The primes-under-multiplication is the canonical seed because unique factorization gives the multiplicative no-collision property *exactly*, for free, with no error term at all.

WHY it works (the mechanism). 1. Unique factorization is exact algebra, not an estimate. $p_1p_2=p_3p_4 \Rightarrow \{p_1,p_2\}=\{p_3,p_4\}$ holds with zero tolerance — this is the one non-asymptotic, non-probabilistic ingredient in the whole argument, and it is what makes the construction possible at all. 2. $\log$ is a group isomorphism $(\mathbb R^{>0},\times)\to(\mathbb R,+)$, so it sends the exact multiplicative Sidon-ness of the primes to exact additive Sidon-ness of $\{\log p\}\subset\mathbb R$. If real numbers of unbounded precision could be used as set elements directly, the theorem would already be proved with no randomness needed. 3. The only genuine difficulty is discretization. To land in $\mathbb N$, $\alpha\log p$ must be truncated to finitely many binary digits; truncation is a many-to-one, lossy operation, so it can — and at high enough density, will — create additive coincidences among the truncated integers $a_p$ that were not present among the exact reals $\log p$. Ruzsa's entire technical contribution is bounding *how often* this happens. 4. Randomizing the discretization scale ($\alpha$) turns a worst-case discretization problem into an average-case one. Rather than analyzing one fixed truncation rule (which might interact badly with the specific arithmetic of $\{\log p\}$), Ruzsa treats $\alpha\in[1,2]$ as a random variable and bounds the *expected* number of bad 4-tuples at each scale, over the randomness in $\alpha$. Markov/first-moment reasoning then shows that this expectation being small forces the *actual* count to be small for almost every individual $\alpha$ — the standard "expectation small $\Rightarrow$ most outcomes are close to expectation" probabilistic-method move (cf. Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs). 5. Deletion repairs the remaining, rare collisions. Once a good $\alpha$ is fixed (existentially, by the a.e. argument), the residual bad 4-tuples are deleted one element at a time; because their count is $o(1)$ relative to the scale's total element count, the surviving set's density exponent is unaffected in the limit. This "build almost-Sidon, then delete the rare collisions" template recurs throughout this technique family (see Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue, Facts, "the deletion technique"). 6. Blockwise zero-padding is the engineering trick that makes step 4 tractable. Encoding each $a_p$ as digit-blocks separated by zero spacers ensures that if two encoded sums collide as plain integers, the collision must decompose *block by block* — no carrying across block boundaries — converting an opaque equation $a_{p_1}+a_{p_2}=a_{p_3}+a_{p_4}$ into a clean, analyzable system of congruences/near-equalities among the underlying primes. Without this, the bad-4-tuple count could not be bounded at all.

HOW to use it to prove things (recombination steps for a solver). 1. Identify a multiplicative (or otherwise non-additive) structure with an *exact*, zero-error no-collision property — unique factorization of $\mathbb Z$ (primes) is the default choice, but any UFD with a well-understood "prime"-counting function is a candidate (Gaussian integers, $\mathbb F_2[X]$ — see Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue Facts for both variants). 2. Transport that structure to an additive one via a logarithm-type isomorphism (real $\log$, here; or a bounded analogue if unboundedness of $\log p$ as $p\to\infty$ is a problem). 3. Introduce a free real randomization parameter controlling the discretization/truncation rule, and bound the *expected* (over that parameter) number of collisions created by discretization at each scale. 4. Use a first-moment/Markov argument to conclude the bound holds for almost every value of the parameter, then fix one such value existentially. 5. Delete the (asymptotically negligible) remaining bad tuples to recover an exactly-Sidon set. 6. Optimize the one free growth-rate parameter in the construction to balance "raw density gained" against "collision density incurred" — this optimization is what produces the final numerical exponent. 7. When it does not directly apply: this is a *lower-bound / existence* construction only, and it is inherently non-constructive — if an *explicit*, algorithmically-producible set is required, use the derandomized discrete-logarithm analogue instead (Discrete-logarithm explicit Sidon construction (Cilleruelo)). It also has not been pushed past $\sqrt2-1$ in 28 years by any variant of this idea (real log, discrete log, Gaussian-integer log, polynomial-ring log all converge on the identical exponent) — closing the gap to the conjectured $1/2$ (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) likely needs a structurally different idea, not a further refinement of this technique.

Related

- Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — the consolidated deep-dive concept page covering *both* this probabilistic construction and Cilleruelo's explicit discrete-log analogue in full technical detail (digit-block mechanics, exact Lemma-by-Lemma collision bookkeeping, $B_h$ generalization, $\mathbb F_2[X]$-analogue); read that page for the complete recombination-ready technique writeup this page summarizes. - Discrete-logarithm explicit Sidon construction (Cilleruelo) — Cilleruelo's later (2012/2013) fully explicit, non-probabilistic construction matching the identical exponent $\sqrt2-1$, by replacing the single unbounded real parameter $\alpha$ with a sequence of independently-chosen finite discrete logarithms mod auxiliary primes; the natural "derandomize this" companion technique. - Sidon sets / B_2 sets / Golomb rulers — parent concept page for Sidon/$B_2$/Golomb-ruler theory; situates this construction against the finite-Sidon-set (Singer/Erdős–Turán) side of the field. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — "$500 for an infinite Sidon set with density $N^{1/2-\epsilon}$ for every $\epsilon>0$" — open; this exact construction is the current world record and the technique this page documents is the one that needs to be beaten or replaced to make progress. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ infinite-density analogue; the log-of-primes idea generalizes here too (Cilleruelo–Tesoro, arXiv:1206.3087), via a Gaussian-prime-argument variant of the same mechanism. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the earlier (1981), mechanistically distinct semi-random construction technique (Ajtai–Komlós–Szemerédi) that first beat the trivial greedy Sidon exponent, superseded in density by this construction but historically prior and conceptually related as another "random deletion repairs near-extremal structure" template. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the general probabilistic-method machinery (expectation bounds $\Rightarrow$ almost-every-instance-is-good) underlying step 4 of this construction's proof.