Cilleruelo (2012/2014) — an explicit, deterministic infinite Sidon set matching Ruzsa's exponent $x^{\\sqrt2-1+o(1)}$, via discrete logarithms

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. Write $A(x):=|A\cap[1,x]|$ for its counting function. For 50 years the best known infinite Sidon set was Erdős's greedy construction, $A(x)\gg x^{1/3}$, improved only slightly by Ajtai–Komlós–Szemerédi (1981) to $A(x)\gg(x\log x)^{1/3}$ via the semi-random ("nibble") method — the AKS authors themselves wrote 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, non-constructive): there exists an infinite Sidon set with $A(x)=x^{\sqrt2-1+o(1)}$, $\sqrt2-1\approx0.41421$, strictly beating $1/3$. Ruzsa's proof is a probabilistic-existence argument over a continuous real parameter $\alpha\in[1,2)$: it proves *almost every* choice of $\alpha$ works, but exhibits no single explicit set (I. Ruzsa, "An infinite Sidon sequence," *J. Number Theory* 68 (1998), 63–71 — see Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) for the full derivation).

The problem Cilleruelo solves: can the *same* record exponent $\sqrt2-1$ be reached by an explicit, fully deterministic infinite Sidon set — one for which every element can be written down by a closed algorithmic rule, with no existence-only probabilistic step?

Facts

- Source: Javier Cilleruelo, "Infinite Sidon sequences," arXiv:1209.0326 (submitted Sep 2012, revised May 2013); published in *Advances in Mathematics* 255 (2014), 474–486. - Answer: yes. Theorem 1.2 of the paper constructs an explicit infinite Sidon sequence $A=(a_p)_{p\in P^*}$, indexed by an explicitly describable set $P^*$ of primes, with $$A(x) = x^{\sqrt2-1+o(1)},$$ matching Ruzsa's exponent exactly. "Note that the exponent of the counting function in the explicit construction of Theorem 1.2 is the same that Ruzsa obtained in his random construction" (paper, §1, remark immediately following Thm 1.2). - It is efficient, not just explicit. The paper notes the algorithm listing all elements $a_p\le x$ uses only $O(x^{\sqrt2-1+o(1)})$ elementary operations — the construction is algorithmically tractable, not merely non-random in principle. - A weaker but simpler warm-up result comes for free. Theorem 1.1 gives, with the *same* digit-encoding machine but *no deletion step at all* (i.e. keeping every prime, not thinning), an explicit Sidon set with exponent $c=\frac{3-\sqrt5}{2}\approx0.382$ — strictly less than $\sqrt2-1\approx0.4142$ but still beating the trivial greedy $1/3$, and (per the paper) "the first time that an infinite Sidon sequence $A$ with $A(x)\gg x^\delta$ for some $\delta>1/3$ is constructed explicitly." Reaching the *full* $\sqrt2-1$ (Theorem 1.2) requires adding a deletion/thinning step on top of the same base construction. - Motivating finite prototype (no digit-encoding needed at all). For a prime power $q$ and a primitive root (generator) $g$ of $\mathbb F_q^*$, the set $$A=\{\log_g p : p\text{ prime},\ p\le\sqrt q\}$$ is already a Sidon set in $\mathbb Z_{q-1}$ of size $|A|=\pi(\sqrt q)\sim2\sqrt q/\log q$. Cilleruelo remarks: "Despite the simplicity of the construction of this finite Sidon set we have not seen it previously in the literature." This one-line finite object is the seed idea scaled up, via digit-encoding across infinitely many auxiliary primes, into the infinite construction. - Generalizes to $B_h$ sequences ($h\ge3$, all $h$-fold sums distinct): Theorem 1.3 gives an infinite $B_h$ sequence with $$A(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)},$$ beating the greedy exponent $1/(2h-1)$. Unlike the $h=2$ (Sidon) case, this generalization is not fully derandomized — the paper explicitly states "we need to introduce a probabilistic argument in an unusual way and it becomes the proof of the following theorem not constructive." The randomness here is only over the *choice of the auxiliary prime sequence* $q_1,q_2,\dots$ (not over a continuous real parameter as in Ruzsa), so it is a strictly weaker, more localized use of probability than Ruzsa's original argument. - A second, independent instantiation of the same skeleton exists over $\mathbb F_2[X]$ (§4 of the paper): irreducible polynomials over $\mathbb F_2$ play the role of primes (their unique factorization is the same lever), giving a finite Sidon set of size $\gg2^{n/2}/n$ in $\mathbb Z_{2^n-1}$ and reproving Theorems 1.1–1.3 with identical exponents — direct evidence the discrete-log skeleton is substrate-agnostic (works over any UFD with a good "prime"-counting function and cyclic unit-group structure), not a one-off trick specific to $\mathbb Z$. - No improvement on the exponent $\sqrt2-1$ in 28 years, across two structurally different proofs. O'Bryant, "The Thickness of Infinite Sidon Sets," arXiv:2606.28651 (26 Jun 2026), states explicitly that Ruzsa's (equivalently, Cilleruelo's) $x^{\sqrt2-1+o(1)}$ "remains the record for an infinite set." That Ruzsa's real-log/probabilistic route and Cilleruelo's discrete-log/deterministic route — genuinely different proof engines — converge on the *identical* number is strong circumstantial evidence $\sqrt2-1$ is a real structural ceiling of this technique family, not an artifact of one execution. - The still-open target this feeds: Erdős's conjecture/problem Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set ($500) asks whether an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$ for every $\epsilon>0$ exists. Both Ruzsa's and Cilleruelo's constructions are the current record lower bound toward this, with a large unclosed gap between $0.4142$ and the conjectured $0.5$.

Solution

**The transferable technique — replace a real-valued (hence unbounded, truncation-prone) logarithm with a *family of independent, exact, finite discrete logarithms*, one per digit-block, so that "is this map injective enough to preserve Sidon-ness" becomes a checkable finite congruence-counting question instead of a measure-theoretic existence argument.**

The key move, in one sentence: Ruzsa needed randomness because a single real parameter $\alpha$ has to *simultaneously* control infinitely many primes' encodings with no possibility of correcting one without perturbing all the others; Cilleruelo removes that coupling by giving *each digit block its own independent, finite, exactly-checkable discrete logarithm*, so that the "did discretization introduce a spurious collision" question becomes a finite divisibility/pigeonhole computation per block instead of a global measure bound over a continuum of $\alpha$.

1. Set up one independent finite cyclic group per digit-block. Fix an increasing sequence of auxiliary primes $q_1<q_2<\cdots$ growing doubly-exponentially ($2^{2j-1}<q_j\le2^{2j+1}$), and for each $j$ a primitive root $g_j$ of $\mathbb F_{q_j}^*$. Each $q_j$ furnishes an *exact*, finite discrete-log map $\mathbb F_{q_j}^*\to\mathbb Z_{q_j-1}$ — no truncation, no approximation, unlike a real logarithm.

2. Partition the primes by size into classes $P_k$, and encode each prime $p\in P_k$ as a *mixed-radix* integer $a_p=x_k(p)\ldots x_1(p)$ in the base $q:=(4q_1,4q_2,\ldots)$, where digit $x_j(p)$ is defined by the discrete-log congruence $$g_j^{x_j(p)}\equiv p\pmod{q_j},\qquad q_j+1\le x_j(p)\le 2q_j-1$$ (and $x_j(p)=0$ for $j>k$). Restricting $x_j(p)$ to the upper half of its residue range, rather than allowing all of $\{0,\ldots,q_j-1\}$, is what keeps mixed-radix digit sums *bounded away* from wraparound and makes the "no carrying across blocks" property (step 3) provable rather than merely plausible.

3. Additivity of the encoding turns one hard global integer identity into a clean per-block congruence system. Because $0\le x_j(p_1)+x_j(p_2)<4q_j$ for every digit, a putative collision $a_{p_1}+a_{p_2}=a_{p_1'}+a_{p_2'}$ forces the digit sums to match *exactly, block by block* — no carrying can cross a digit boundary. Unwinding this (Proposition 2 of the paper) shows any such collision forces $p_1p_2\equiv p_1'p_2'\pmod{q_1\cdots q_{k_2}}$ and $p_1\equiv p_1'\pmod{q_{k_2+1}\cdots q_{k_1}}$ for scale indices $k_2\le k_1$ satisfying $k_2^2<\frac{c}{1-c}k_1^2$ — i.e. a genuine multiplicative-Sidon-of-the-primes fact (unique factorization) has been recovered *inside* the additive digit encoding, exactly as intended.

4. Choose the scale/growth parameter $c$ to make collisions impossible outright, if you can afford it (the "free" theorem). For $c=\frac{3-\sqrt5}{2}$, the inequality forced by a genuine collision ($1-c<\frac{c}{1-c}$) is simply false — so *zero* collisions can ever occur, and no cleanup step is needed at all (Theorem 1.1). This is the cheap, fully-elementary regime: no probability, no deletion, just picking the parameter conservatively enough that the pigeonhole argument alone rules out bad tuples.

5. Push the parameter to the truly optimal value by allowing (and then removing) a controlled fraction of collisions. At $c=\sqrt2-1$, collisions among primes in the same size class *can* occur, but every prime $p_1\in P_{k_1}$ involved in one is forced to divide some nonzero integer in an explicitly describable finite set $S_{k_2,k_1}$ (built from the same congruence data as step 3). Counting divisors, not estimating a measure: since $\tau(n)=n^{o(1)}$ (no probability needed — this is a deterministic divisor bound), the set $B_{k_1}$ of "bad" primes in $P_{k_1}$ satisfies $|B_{k_1}|\le(\tfrac12+o(1))|P_{k_1}|$, *provably*, via the algebraic identity $\frac{2c}{1-c}-1=c$ and $\frac{1-c}{c}=\sqrt2$ that hold exactly at $c=\sqrt2-1$. Delete every prime in $B_{k_1}$ (the classical alteration-method move: build something slightly flawed, then prune) — this removes at most half of each size class, which costs nothing in the leading exponent, and what survives, $P^*=\bigcup_{k_1}(P_{k_1}\setminus B_{k_1})$, is a genuine, exactly-Sidon set with $A(x)=x^{\sqrt2-1+o(1)}$.

6. Why this is more powerful than Ruzsa's route, and exactly where the trade-off lives. Ruzsa's real parameter $\alpha$ has to make *every* prime's discretization simultaneously well-behaved, so "does $\alpha$ work" is answerable only in expectation/measure over a continuum — genuinely probabilistic, non-constructive. Cilleruelo's discrete logs mod $q_j$ are chosen once, are exact, finite objects, and the bad-tuple bound (step 5) is a *deterministic* divisor-counting argument, not an expectation. The price is that the $h\ge3$ generalization (Theorem 1.3) reintroduces probability — but now only over the *choice of the finite auxiliary sequence $(q_j,g_j)$*, a strictly smaller and more localized randomization than a continuous real $\alpha$, and the paper explicitly frames this as the one place its method has not yet been fully derandomized.

Why this is the reusable part. The general recipe — (i) find a UFD/multiplicative-Sidon substrate (primes, Gaussian primes, irreducible polynomials over $\mathbb F_2$ — anything with unique factorization and a countable, well-understood "prime"-counting function); (ii) replace a single unbounded real-valued logarithm with a *sequence of independent, exact, finite discrete logarithms*, one per digit block, chosen so each block's residue range keeps digit sums carry-free; (iii) use the carry-free block structure to reduce "did I create a spurious additive collision" to a per-block, purely algebraic congruence system; (iv) tune one scale-growth parameter so that either collisions are impossible outright (cheap, suboptimal exponent) or a deterministic divisor-counting bound shows at most half of each size class is ever implicated (the alteration/deletion step, optimal exponent) — is directly reusable anywhere a probabilistic-existence Sidon-type (or more generally additive-collision-avoidance) construction needs to be derandomized. It is the exact template Cilleruelo–Tesoro reran (with Gaussian-prime arguments) for the $B_3,B_4$ cases, and the natural first tool for anyone attacking the still-open Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set gap toward exponent $1/2$: since two structurally different engines (real-log-probabilistic and discrete-log-deterministic) both cap out at exactly $\sqrt2-1$, closing that gap plausibly requires a *third*, structurally different substrate or transfer map, not a further optimization of either existing skeleton.

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the still-open $500 Erdős problem this construction is a (derandomized) record lower bound for: an infinite Sidon set with $A(x)\gg_\epsilon x^{1/2-\epsilon}$ for all $\epsilon>0$? Exponent $\sqrt2-1\approx0.4142$ unimproved since 1998/2012, confirmed still-current by O'Bryant arXiv:2606.28651 (26 Jun 2026). - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ infinite-density analogue; Cilleruelo's own Theorem 1.3 (this paper) and the follow-up Cilleruelo–Tesoro, "Dense infinite $B_h$ sequences," arXiv:1206.3087, extend the exponent formula $\sqrt{(h-1)^2+1}-(h-1)$ to $h=3,4$ explicitly. - Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) and Ruzsa's infinite Sidon set of density $x^{\\sqrt2-1+o(1)}$ (1998) — current record — the original 1998 non-constructive theorem this page's construction matches in exponent and derandomizes in method; near-duplicate sibling pages covering Ruzsa's real-log/probabilistic-measure route in full technical depth, with Cilleruelo mentioned there as a corroborating fact rather than the primary object (as here). - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — survey/deep-dive concept page already covering both Ruzsa's and Cilleruelo's constructions side by side at comparable technical depth; this problem page is citable as that concept page's fuller worked derivation of the Cilleruelo half specifically. - Sidon sets / B_2 sets / Golomb rulers — the parent concept page for the whole Sidon/$B_h$/Golomb-ruler area; documents this construction as one of its core "Technique" recipes (log/discrete-log trick). - Finite-field / projective-plane constructions for extremal additive sets — the broader family of "explicit algebraic construction from a finite field or UFD" techniques, of which Cilleruelo's discrete-log route (this page) and Singer's projective-plane route (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) are both instances. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite-Sidon-set sharp-asymptotics sibling; different (Singer/finite-field-geometric, not discrete-log) construction, but the same "exact finite-field/UFD algebra beats probabilistic near-optimality" theme, and the direct structural cousin of Cilleruelo's own finite warm-up example $A=\{\log_g p:p\le\sqrt q\}\subset\mathbb Z_{q-1}$.