Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue

Statement

The core transfer principle. The positive integers under multiplication have *unique factorization*, hence the primes form a multiplicatively Sidon set: if $p_1p_2 = p_3p_4$ for primes (with $\{p_1,p_2\}\ne\{p_3,p_4\}$), unique factorization forces a contradiction. Any injective homomorphism-like map that sends multiplication to addition — a logarithm, real or discrete — therefore sends $\{p : p\text{ prime}\}$ to an additively Sidon set of the target group, *provided the map is exact enough that no rounding/reduction can create an accidental additive coincidence between multiplicatively-inequivalent quadruples.* Managing that "provided" clause — because a real logarithm must be truncated to an integer, and a discrete logarithm lives in a finite cyclic group where wraparound is possible — is the entire technical content of the constructions below.

**Ruzsa's theorem (I. Ruzsa, "An infinite Sidon set," *J. Number Theory* 68 (1998), 63–71). There exists an infinite Sidon set $S\subset\mathbb N$ (a set with all pairwise sums $a+b$, $a\le b\in S$, distinct) whose counting function satisfies $$S(x) := |S\cap\{1,\dots,x\}| = x^{\sqrt2-1+o(1)}, \qquad \sqrt2-1\approx0.4142.$$ The proof is probabilistic and non-constructive**: for a real parameter $\alpha\in[1,2)$ Ruzsa builds a set $A_\alpha=(a_p)_{p\text{ prime}}$ by taking the binary expansion of $\alpha\log p$ for each prime $p$, cutting it into growing blocks (block $j$ has length $\sim j^2$, separated by zero-padding), and reassembling the blocks — with a size marker — into a single natural number $a_p$. He shows that for *almost every* $\alpha\in[1,2)$ this $A_\alpha$ is only a *bounded distance* from Sidon: the number of "bad" (repeated-sum) 4-tuples at each dyadic scale $K$ is, in expectation over $\alpha$, small enough that deleting one element from each bad 4-tuple removes only a vanishing fraction of $A_\alpha$, leaving an honest Sidon set of density $x^{\sqrt2-1+o(1)}$ (arxiv.org/pdf/1103.5732, full simplified re-derivation, Theorem 4.5 there attributed explicitly to Ruzsa 1998; the exponent $\beta$ in that write-up satisfies $1/\beta=\sqrt2-1$, obtained by optimizing $\beta^2-2\beta-1=0\Rightarrow\beta=1+\sqrt2$).

Cilleruelo's discrete-log constructive analogue (J. Cilleruelo, "Infinite Sidon sequences," arXiv:1209.0326, 2012/2013). There is an explicit, non-probabilistic infinite Sidon sequence $A=(a_p)_{p\in\mathcal P^*}$ (indexed by an explicitly describable set $\mathcal P^*$ of primes) with the *same* record exponent $$A(x) = x^{\sqrt2-1+o(1)},$$ constructed by replacing Ruzsa's real logarithm $\alpha\log p$ with a family of discrete logarithms: fix an increasing sequence of auxiliary primes $q_1<q_2<\cdots$ and, for each $j$, a primitive root $g_j$ of $\mathbb F_{q_j}^*$; encode each prime $p$ (grouped by size into classes $\mathcal P_k$) as a mixed-radix integer $a_p=x_k(p)\ldots x_1(p)$ whose digits $x_j(p)$ solve $g_j^{x_j(p)}\equiv p\pmod{q_j}$. The construction is fully deterministic once the $q_j$'s and $g_j$'s are fixed (only a *thin, explicitly describable* set of "bad" primes need be deleted to kill the residual collisions — no probabilistic existence argument is needed at this step, only a direct pigeonhole bound), and the whole algorithm lists all elements $\le x$ in $O(x^{\sqrt2-1+o(1)})$ elementary operations.

Finite warm-up version (both papers). The core mechanism is already visible, with no digit-encoding machinery at all, in a finite Sidon set. Cilleruelo's motivating example (arxiv.org/pdf/1209.0326, §1): for a prime power $q$ and a generator $g$ of $\mathbb F_q^*$, $$A = \{\log_g p : p\text{ prime},\ p\le\sqrt q\}$$ is a Sidon set in $\mathbb Z_{q-1}$ of size $|A|=\pi(\sqrt q)\sim 2\sqrt q/\log q$ — density matching the classical $\sqrt N$ ceiling, via nothing but "primes are multiplicatively Sidon" transported through the group isomorphism $\mathbb F_q^*\cong\mathbb Z_{q-1}$. The corresponding real-log finite prototype (Maldonado, arxiv.org/pdf/1103.5732, Thm 2.1): for large $n$, $$X = \Big\{\Big\lfloor\tfrac{2n}{\log n}\log p\Big\rfloor : p\text{ prime},\ p\le\sqrt{n/(2\log n)}\Big\}$$ is a Sidon set of size $\sim\sqrt{2n}/\log^{3/2}n$, proved directly from $|\{x\}+\{y\}-\{z\}-\{w\}|\le2$ and $\log(pq/rs)\ge1/(2rs)$ for distinct products — a two-line unique-factorization-plus-fractional-part argument with no probability involved.

Facts

- Named result / origin: I. Ruzsa, "An infinite Sidon set," *J. Number Theory* 68 (1998), 63–71 — broke the exponent-$1/3$ barrier that had stood (bar the 1981 Ajtai–Komlós–Szemerédi nibble-method improvement to $(x\log x)^{1/3}$) since Erdős's 1930s-era greedy construction; still the current record exponent as of mid-2026, per O'Bryant's arXiv:2606.28651 (26 Jun 2026), cited in wiki/problems/39.md. - The exponent $\sqrt2-1$ is not arbitrary — it is the output of an explicit optimization. In both the probabilistic (Ruzsa/Maldonado) and constructive (Cilleruelo) versions, the construction has one free real parameter (called $\beta$ in Maldonado's write-up, $c$ in Cilleruelo's) controlling how fast the "block size" / prime-range partition grows; the number of "bad" (collision-producing) elements at each scale is bounded by an expression whose exponent is a function of that parameter, and setting the two competing exponents equal — solving $\beta^2-2\beta-1=0$ in Maldonado's derivation (giving $\beta=1+\sqrt2$, i.e. $1/\beta=\sqrt2-1$), equivalently $2c/(1-c)-1=c$ in Cilleruelo's ($c=\sqrt2-1$) — is what fixes the final density exponent. This is a genuine extremal trade-off, not a magic number: it is the point where the "deletion cost" (bad 4-tuples to remove) and the "raw density" (elements per scale) balance. - Cilleruelo's weaker-but-simpler Theorem 1.1 (arxiv.org/pdf/1209.0326) gives, with *no deletion step at all* (just the raw digit-encoded sequence over *all* primes, not a thinned subset), an explicit Sidon sequence with exponent $c=(3-\sqrt5)/2\approx0.382$ — strictly less than $\sqrt2-1\approx0.414$ but still beating the trivial $1/3$, and it is "the first time an infinite Sidon sequence with $A(x)\gg x^\delta$ for $\delta>1/3$ is constructed *explicitly*" (i.e. before Cilleruelo's paper, exceeding $1/3$ was known only via AKS's nibble method or Ruzsa's non-constructive probabilistic argument). - The deletion technique (used in both the probabilistic and explicit versions) is the standard "almost-Sidon $\to$ Sidon" repair move: build a set that is *nearly* collision-free, prove the number of colliding 4-tuples at each scale is a vanishing fraction of the scale's total elements, then delete (say) the largest element of every bad 4-tuple. Because deleting one element kills every bad 4-tuple it participates in, and the bad-tuple count is $o(|\mathcal P_k|)$, the surviving set retains the same growth exponent up to $o(1)$ in the exponent. This exact template also appears in Cilleruelo–Tesoro's $B_h$ generalization (Theorem 1.3 there) and is a generic move whenever "almost every instance of a random/parametrized structure is nearly extremal." - Blockwise-independent digit encoding is the load-bearing engineering trick. Both constructions insert deliberate zero-padding ("spacer" digits/bits) between the blocks encoding different primes' contributions, so that when two encoded sums collide as *integers*, the collision is forced to decompose into a collision *block by block* — no "carrying" across block boundaries is possible. This converts an opaque integer equation $a_{p_1}+a_{p_2}=a_{p_3}+a_{p_4}$ into a clean system of congruences $p_1p_2\equiv p_3p_4\pmod{Q_1}$, $p_1\equiv p_3\pmod{Q_2}$, etc. (Cilleruelo's Proposition 2) — recovering the multiplicative-Sidon structure of the primes from inside the additive encoding, which is exactly what makes the whole method provable. - Generalizes to $B_h$ sets ($h\ge3$): Cilleruelo's paper proves (Theorem 1.3, via a probabilistic argument — this part is *not* made explicit even in the discrete-log paper) that for every $h\ge3$ there is an infinite $B_h$ sequence (all $h$-fold sums distinct) with $$A(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)},$$ beating the greedy exponent $1/(2h-1)$. Cilleruelo–Tesoro, "Dense infinite $B_h$ sequences," arXiv:1206.3087 (2012), settle $h=3,4$ *explicitly*, using a variant with the sequence $(\theta(\mathfrak p))$ of arguments of Gaussian primes $\mathfrak p=|\mathfrak p|e^{2\pi i\theta(\mathfrak p)}$ instead of $(\log p)$ — matching Maldonado's Gaussian-integer real-log variant in spirit but for higher $h$; this variant does not extend to all $h$. - A second explicit "alternative construction" exists over $\mathbb F_2[X]$ (Cilleruelo, §4): irreducible polynomials over $\mathbb F_2$ play the role of primes (their unique-factorization property is the exact same lever), giving a finite Sidon set of size $\gg2^{n/2}/n$ in $\mathbb Z_{2^n-1}$, and an infinite analogue reproving Theorems 1.1–1.3 with the same exponents — direct evidence that "any ring/domain with unique factorization and a good size-vs-count profile of primes" is a valid substrate for this technique, not just $\mathbb Z$. - Maldonado's real-log variant uses Gaussian integers, not the reals directly. Because $\log p$ is unbounded as $p\to\infty$ (a genuine technical headache for Ruzsa's original binary-digit truncation, explicitly flagged in arxiv.org/pdf/1103.5732 §1: "this set is unbounded, which created some trouble"), Maldonado instead uses the *bounded* argument $\phi_p\in[0,1)$ of the Gaussian prime factor of $p\equiv1\pmod4$ (i.e. $p=\rho_p\bar\rho_p$ in $\mathbb Z[i]$, $\phi_p:=\arg(\bar\rho_p/\rho_p)/2\pi$) — unique factorization in $\mathbb Z[i]$ makes $(\phi_p)_p$ additively Sidon exactly as $(\log p)$ is, but boundedness removes the truncation headache Ruzsa had to manage, at the cost of only using $1/4$ of the primes (those $\equiv1\bmod4$). This is presented explicitly as a *simplification* of Ruzsa's original argument, reproducing the identical final exponent $\sqrt2-1$ via Theorem 4.5. - No improvement on the exponent $\sqrt2-1$ in 28 years (1998–2026), despite two structurally different reproofs (Ruzsa's real-log/binary-digit probabilistic method; Cilleruelo's discrete-log fully explicit method) converging on the *identical* number — strong circumstantial evidence the exponent is a genuine barrier of this technique family, not an artifact of one particular execution. Confirmed still-current by O'Bryant, arXiv:2606.28651 (26 Jun 2026): Ruzsa's bound "remains the record for an infinite set" (cited in wiki/problems/39.md).

Technique

WHY it works (the mechanism, both versions). 1. Unique factorization of $\mathbb Z$ (or $\mathbb Z[i]$, or $\mathbb F_2[X]$ — any UFD with a good prime-counting function) makes the primes *exactly* multiplicatively Sidon: $p_1p_2=p_3p_4\Rightarrow\{p_1,p_2\}=\{p_3,p_4\}$, with zero error tolerance — this is the one piece of the argument that is not asymptotic or probabilistic, it is exact algebra. 2. A logarithm-type map (real $\log$, discrete $\log_g$ mod a prime, or the finite-field/Gaussian-integer analogues) sends this multiplicative structure to an *additive* one, because $\log(p_1p_2)=\log p_1+\log p_2$. If this map were exact and unbounded-precision, $\{\log p\}$ would already be an exact additively-Sidon set of reals (or discrete-log residues). 3. The entire remaining difficulty is that the map has to be discretized (truncated to finitely many binary digits, or reduced mod a finite modulus $q_j-1$) to land back in $\mathbb N$, and discretization can in principle *create* additive coincidences that weren't there in the exact real/discrete-log values. Managing this is done two structurally different ways: - Ruzsa's route (probabilistic): introduce a free real "stretching" parameter $\alpha$, show that for *almost every* $\alpha$ the number of discretization-induced collisions is small (a second-moment/expectation argument over $\alpha$, cf. Maldonado's Lemmas 4.1–4.4), then fix one good $\alpha$ and delete the few remaining bad elements. Existence, not explicit construction. - Cilleruelo's route (explicit/derandomized): replace the single unbounded real parameter with a *sequence* of independently-chosen finite discrete logarithms (a fresh prime $q_j$ and primitive root $g_j$ for each digit-block $j$), each of which is an *exact*, finite, checkable congruence with no truncation ambiguity; collisions are then bounded by a direct divisor-counting/pigeonhole argument on which primes $q_j$ *could* create a collision, with no need to average over a continuum of parameters. The "randomness" survives only in the *choice of the auxiliary prime sequence $q_j$*, and even that step (§3, Theorem 1.3's $B_h$ case) can be made probabilistic-in-expectation over the $q_j$'s while remaining explicit in every other respect. 4. Blockwise zero-padding is what makes discretization tractable at all (see Facts): without it, an additive collision among the encoded integers would not decompose into per-block/per-prime information, and neither the probabilistic nor the explicit route could extract usable congruences from a raw collision $a_{p_1}+a_{p_2}=a_{p_3}+a_{p_4}$.

HOW to use it to prove things (recombination steps)

1. Identify a UFD/unique-factorization substrate with countably many "primes" and a good density function: $\mathbb Z$ (primes, $\pi(x)\sim x/\log x$), $\mathbb Z[i]$ (Gaussian primes via $p\equiv1\bmod4$), $\mathbb F_2[X]$ (irreducible polynomials, count $\sim2^j/j$ at degree $j$) are the three substrates already used; any UFD with comparably well-understood prime-counting asymptotics is a candidate. 2. Pick a logarithm-type map into an additive group: real $\log$ (unbounded, needs the deletion/truncation machinery), a bounded analogue like Gaussian-prime argument $\phi_p\in[0,1)$ (bounded, technically simpler), or — for the fully explicit route — a discrete logarithm mod a sequence of auxiliary primes $q_1,q_2,\ldots$ with chosen primitive roots $g_1,g_2,\ldots$. 3. Partition the primes into size classes $\mathcal P_k$ by a growth-rate parameter (Ruzsa/Maldonado's $\beta$, Cilleruelo's $c$) and encode each prime's image as a mixed-radix / block-digit integer, inserting zero-padding between blocks to guarantee blockwise-independent addition (no "carrying"). 4. Bound the number of "bad" (collision-producing) tuples at each scale — via a bad-4-tuple pigeonhole/divisor-count argument in the explicit route, or an expectation-over-a-random-parameter argument in the probabilistic route — and choose the growth-rate parameter to balance the two competing exponents (the raw density of the size classes vs. the density of bad tuples), which is the step that produces the final numerical exponent (here $\sqrt2-1$, or $\sqrt{(h-1)^2+1}-(h-1)$ for $B_h$). 5. Delete one element from every surviving bad tuple (largest-element-of-each-bad-tuple is the standard rule) to obtain a genuinely collision-free set, and verify the deleted fraction is $o(1)$ of each size class so the exponent survives the cleanup. 6. **When it does *not* directly apply**: this is a *lower-bound/construction* technique only — it says nothing about upper bounds on Sidon-set density (that's the Erdős–Turán shift-counting side of Sidon sets / B_2 sets / Golomb rulers); it has not been pushed past $\sqrt2-1$ in 28 years by any variant of this method (real log, discrete log, Gaussian-integer log, $\mathbb F_2[X]$-log all converge on the identical number), suggesting a genuine technique ceiling — closing the gap to the conjectured $N^{1/2-\epsilon}$ (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) likely needs either a structurally different construction or a hybrid with the semi-random nibble method (as used by Ajtai–Komlós–Szemerédi for the earlier, weaker $(\log)^{1/3}$-type record). 7. WHEN it applies: whenever a problem needs an explicit or probabilistic construction of a dense set with a *multiplicative* no-collision property in disguise (e.g. "products $p_1p_2$ are all distinct" is trivial by unique factorization; the actual work is always in transporting that multiplicative exactness into whatever *additive* combinatorial structure the target problem is stated in) — Sidon/$B_h$ sets are the canonical target, but the log/discrete-log transfer principle is reusable wherever unique factorization needs to be smuggled into an additive setting.

Related

- Sidon sets / B_2 sets / Golomb rulers — the parent concept page for Sidon/$B_2$/Golomb-ruler theory as a whole; already summarizes this construction at survey depth (Facts point on Ruzsa/Cilleruelo, Technique point 3) and is the place to look for the *finite*-Sidon-set side (Singer/Erdős–Turán) that this page's discrete-log technique deliberately parallels (Cilleruelo's finite warm-up example, $A=\{\log_g p\}\subset\mathbb Z_{q-1}$, is a direct structural cousin of Singer's finite-field difference-set construction, though algebraically distinct — Singer uses a projective-plane collineation, this uses a bare cyclic-group discrete log). - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — "$500 for an infinite Sidon set of density $N^{1/2-\epsilon}$ for all $\epsilon$" — open; the exponent $\sqrt2-1$ produced by this exact technique is the current world record (unimproved since 1998, confirmed by O'Bryant arXiv:2606.28651, 26 Jun 2026) and the gap to the conjectured $1/2$ is the central open question this construction feeds into. That page's own Related section forward-links to concept/ruzsa-log-prime-construction and concept/discrete-logarithm-sidon-construction — this page (at the requested slug concept/ruzsa-sidon-construction) is the consolidated deep-dive covering both. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ (distinct-triple-sum) infinite-density analogue; Cilleruelo–Tesoro's arXiv:1206.3087 extension of this exact method (Gaussian-prime-argument variant) is the best known *construction* on the complementary/witness side of that problem. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set sharp-asymptotics sibling; uses a *different* (Singer/finite-field) construction for its lower bound, but shares the "unique factorization / finite-field exactness beats probabilistic near-optimality" theme. - Finite-field / projective-plane constructions for extremal additive sets — the broader family of "explicit algebraic construction from a finite field or UFD" techniques in extremal combinatorics, of which Cilleruelo's discrete-log route and Singer's projective-plane route are both instances, contrasted with genuinely probabilistic/semi-random alternatives (nibble method). - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — a structurally distinct "explicit construction via number-theoretic exactness" technique (covering congruences rather than unique factorization) documented at comparable depth in this wiki; useful as a contrast case for what "the construction skeleton, not just the final theorem, is the reusable object" looks like in a different problem area.