Discrete-logarithm explicit Sidon construction (Cilleruelo)

Statement

The object. For a prime power $q$ and a fixed generator (primitive root) $g$ of the cyclic group $\mathbb F_q^\ast$, the discrete logarithm $\log_g:\mathbb F_q^\ast\to\mathbb Z/(q-1)\mathbb Z$ is a group isomorphism from *multiplication* mod $q$ to *addition* mod $q-1$: $\log_g(xy)\equiv\log_g x+\log_g y\pmod{q-1}$.

Finite construction (Cilleruelo, arXiv:1209.0326, §1). For a prime power $q$ and generator $g$ of $\mathbb F_q^\ast$, $$A=\{\log_g p:\ p\text{ prime},\ p\le\sqrt q\}\ \subset\ \mathbb Z_{q-1}$$ is a Sidon set (all pairwise sums distinct mod $q-1$) of size $|A|=\pi(\sqrt q)\sim\dfrac{2\sqrt q}{\log q}$ — density matching the classical $\sqrt N$ Sidon ceiling. The proof is two lines: unique factorization makes $\{p\text{ prime}\}$ *multiplicatively* Sidon (if $p_1p_2\equiv p_3p_4\pmod q$ with $p_i\le\sqrt q$ then, since $p_1p_2,p_3p_4<q$, the congruence is an honest equality of integers, forcing $\{p_1,p_2\}=\{p_3,p_4\}$ by unique factorization); the discrete log is a group isomorphism, so it transports this multiplicative exactness to additive exactness in $\mathbb Z_{q-1}$ with zero loss — no rounding, no probability, no deletion step needed at the finite level.

Infinite construction (Cilleruelo, arXiv:1209.0326, §2–3). 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}^\ast$. Partition the primes into size-classes $\mathcal P_k$ by a growth-rate parameter, and encode each prime $p$ as a mixed-radix digit string $a_p = x_k(p)\,x_{k-1}(p)\cdots x_1(p)$ (concatenated with zero-padding between blocks) whose $j$-th digit solves the discrete-log congruence $g_j^{x_j(p)}\equiv p\pmod{q_j}$. The resulting sequence $A=(a_p)$ is an explicit infinite Sidon sequence with counting function $$A(x) = x^{\sqrt2-1+o(1)},\qquad \sqrt2-1\approx0.4142,$$ matching Ruzsa's 1998 non-constructive probabilistic record exactly, but produced deterministically — the algorithm lists all elements $\le x$ in $O(x^{\sqrt2-1+o(1)})$ elementary operations. A weaker, deletion-free version (Theorem 1.1) gives exponent $c=(3-\sqrt5)/2\approx0.382>1/3$ with no thinning step at all — already the first *explicit* infinite Sidon sequence beating the trivial $1/3$ exponent (previously exceeded only via Ruzsa's non-constructive argument or the semi-random nibble method).

$B_h$ generalization (Cilleruelo, Thm 1.3; Cilleruelo–Tesoro, arXiv:1206.3087). For every $h\ge3$ there is an explicit infinite $B_h$ sequence (all $h$-fold sums distinct) with $$A(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}.$$

Facts

- Why this is a genuine derandomization, not just a different proof. Ruzsa's 1998 construction fixes a single real parameter $\alpha\in[1,2)$ and shows *almost every* choice works (an existence, not a construction — no algorithm is given for finding a good $\alpha$, and verifying a specific $\alpha$ works is not obviously decidable). Cilleruelo replaces the one unbounded real parameter with a *sequence of independent, finite, exactly-checkable* discrete-log congruences (fresh $q_j,g_j$ per digit block); every step is a finite computation, so the whole construction — and the (thin) set of "bad" primes to delete — is explicitly listable. - The finite warm-up needs no deletion step at all; the infinite version does. At the finite, single-modulus level ($A=\{\log_g p:p\le\sqrt q\}$), unique factorization gives an *exact* Sidon set with no exceptions. The infinite version's digit-encoding introduces its own new failure mode (a collision between mixed-radix strings can in principle occur even when the underlying discrete logs don't literally collide, because concatenation across blocks of different primes $q_j$ is not itself injective a priori) — this is repaired the same way Ruzsa's probabilistic route is repaired: bound the number of "bad" (collision-producing) tuples at each scale via a direct pigeonhole/divisor-counting argument (no averaging over a parameter needed, since each $q_j$ is a finite fixed choice) and delete one element from each bad tuple. - Blockwise zero-padding is the load-bearing engineering trick that makes discrete logs usable as digits. Deliberate zero-padding between the digit blocks encoding different $q_j$'s ensures that if two encoded integers collide as sums, the collision must decompose *block by block* (no "carrying" across block boundaries) — turning an opaque integer equation $a_{p_1}+a_{p_2}=a_{p_3}+a_{p_4}$ into a clean system of per-modulus congruences $g_j^{x_j(p_1)}g_j^{x_j(p_2)}\equiv g_j^{x_j(p_3)}g_j^{x_j(p_4)}\pmod{q_j}$ for each $j$ — i.e. it recovers the multiplicative-Sidon structure of the primes from *inside* the additive digit encoding, which is exactly what makes the collision bound provable at all. - A second explicit substrate: $\mathbb F_2[X]$ (Cilleruelo, §4). Replacing primes with irreducible polynomials over $\mathbb F_2$ (unique factorization holds there too) and the discrete log with the analogous group isomorphism gives 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 identical exponents — direct evidence the mechanism is "any UFD with a well-understood prime-counting function admits a discrete-log-flavored Sidon construction," not a $\mathbb Z$-specific trick. - The exponent $\sqrt2-1$ has not been improved by any variant of the log/discrete-log family in 28 years (1998–2026) — real log (Ruzsa), discrete log (Cilleruelo), Gaussian-integer argument (Maldonado López, arXiv:1103.5732), and $\mathbb F_2[X]$-log (Cilleruelo §4) all independently converge on the identical number, confirmed still the record by O'Bryant (arXiv:2606.28651, 26 Jun 2026) — strong circumstantial evidence this is a genuine barrier of the whole technique family, not an artifact of one execution. - Distinct from, but a direct structural cousin of, Singer's construction. Cilleruelo's finite warm-up $A=\{\log_g p:p\le\sqrt q\}\subset\mathbb Z_{q-1}$ and Singer's perfect difference set $D\subset\mathbb Z_{q^2+q+1}$ (Singer finite-field perfect difference set construction) both produce a $\sqrt{|\text{group}|}$-size Sidon set inside a cyclic group derived from a finite field, but by different mechanisms: Singer uses a projective-plane collineation (an incidence axiom, Flavor A in Finite-field / projective-plane constructions for extremal additive sets's taxonomy), while Cilleruelo uses a bare discrete logarithm plus unique factorization of $\mathbb Z$ (no geometry at all) — the two are not the same construction, only structurally parallel outputs.

Technique

WHEN this applies. Reach for a discrete-logarithm construction whenever (a) you need an explicit, deterministic, non-probabilistic witness for a set with a multiplicative-to-additive collision-avoidance property (Sidon, $B_h$, or more generally "no nontrivial multiplicative relation among a chosen set of primes/irreducibles should survive being mapped into an additive group"), and (b) the natural probabilistic/measure-theoretic proof of the same result (e.g. Ruzsa's "almost every real $\alpha$ works") leaves you wanting an actual algorithm or a finitely-checkable certificate rather than an existence statement. It is the go-to move whenever a finite cyclic group $\mathbb F_q^\ast$ is available at (or can be built to) the right scale and the target combinatorial obstruction is fundamentally a unique-factorization fact in disguise.

WHY it works (the mechanism). 1. Unique factorization of $\mathbb Z$ makes the primes $\le\sqrt q$ *exactly* multiplicatively Sidon within $\mathbb F_q^\ast$: two distinct products of two such primes can never coincide, because if they did as integers below $q$ they would coincide *exactly*, contradicting unique factorization. This piece is exact algebra, not an estimate. 2. $\log_g:\mathbb F_q^\ast\to\mathbb Z_{q-1}$ is a genuine group isomorphism — unlike a real logarithm, it requires no truncation: the additive Sidon-ness of $\log_g(\{p\le\sqrt q\})$ is transported from the multiplicative Sidon-ness of the primes with *zero* error, because both sides live in exact finite arithmetic. 3. To go from one finite modulus to an infinite sequence, the single discrete log is replaced by a *sequence* of independent discrete logs (fresh $q_j,g_j$ per digit block), each still exact and finite; the only place approximation/deletion re-enters is in bounding cross-block digit-string collisions, which is done by an explicit, non-probabilistic pigeonhole/divisor-count argument rather than an averaging-over-a-parameter argument — this is precisely what makes the construction "explicit" rather than merely "probabilistically almost surely explicit."

HOW to use it to prove things (recombination steps)

1. Identify the multiplicative-Sidon substrate: primes in $\mathbb Z$, Gaussian primes in $\mathbb Z[i]$, irreducible polynomials in $\mathbb F_2[X]$, or any UFD with a usable "prime"-counting asymptotic — the source of the *exact* no-collision property you will transport. 2. Pick a finite cyclic group at the target scale: $\mathbb F_q^\ast$ for a prime power $q$ near the scale you need (for the finite version), or a growing sequence $q_1<q_2<\cdots$ of auxiliary primes (for the infinite version, one modulus per digit block). 3. Fix a primitive root and take discrete logs — this is the exact, zero-error multiplicative-to-additive transport step; verify it algebraically (no estimate needed) rather than by counting. 4. For the infinite case, mixed-radix-encode with zero-padding between blocks so that any integer collision among encoded sums is forced to decompose block-by-block into per-modulus discrete-log congruences — this is the step that lets you recover a checkable, finite collision-counting argument instead of an opaque one. 5. Bound bad (collision-producing) tuples by direct pigeonhole/divisor-counting (not by an expectation over a random parameter) and delete one element per bad tuple; verify the deleted fraction is $o(1)$ so the target density exponent survives. 6. Optimize the digit-block growth-rate parameter to balance "raw density of each size class" against "density of bad tuples" — this is the step that produces the final numerical exponent (e.g. $\sqrt2-1$ for $h=2$, $\sqrt{(h-1)^2+1}-(h-1)$ for $B_h$). 7. When it does NOT directly apply: this is a *lower-bound/existence-with-an-algorithm* technique only, not an upper-bound technique (upper bounds for Sidon-set density come from the Erdős–Turán shift-counting side, Sidon sets / B_2 sets / Golomb rulers); it has not, in any of its four independently-discovered variants (real log, discrete log, Gaussian-integer argument, $\mathbb F_2[X]$-log), broken the $\sqrt2-1$ exponent in 28 years, so it is not currently a route to the still-open conjectured density $N^{1/2-\epsilon}$ (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set) without a structurally new idea (e.g. hybridizing with the semi-random nibble method).

Related

- Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — the fuller comparative deep-dive covering both Ruzsa's original 1998 probabilistic real-log construction *and* this discrete-log derandomization side by side, with the shared "unique factorization → log transport → discretize → delete bad tuples" template spelled out; this page is the narrower, mechanism-focused companion specifically on the discrete-log route. - Singer finite-field perfect difference set construction — a structurally parallel but mechanistically distinct finite-cyclic-group Sidon construction (projective-plane incidence axiom rather than discrete log + unique factorization); useful contrast for "two ways to get a $\sqrt{|G|}$-size Sidon set out of a cyclic group derived from a finite field." - Finite-field / projective-plane constructions for extremal additive sets — the broader umbrella of explicit algebraic constructions over finite fields/projective spaces for extremal additive/combinatorial objects; this discrete-log technique is a distinct, UFD-unique-factorization-driven member of that family rather than an incidence-axiom (Flavor A) or Weil-bound (Flavor B) instance. - Sidon sets / B_2 sets / Golomb rulers — the parent combinatorial object (Sidon/$B_2$/Golomb-ruler sets); already documents this construction at survey depth as the "log/discrete-log trick." - 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); this construction's exponent $\sqrt2-1$ is the current record for an *explicit* construction, matching the non-constructive record and unimproved since 1998/2012. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ infinite-density analogue; the Cilleruelo–Tesoro $B_h$ generalization (arXiv:1206.3087) is the best known explicit construction on this problem's constructive side. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the finite Sidon-set sharp-asymptotics problem; uses the mechanistically different Singer/finite-field construction for its own matching lower bound, but shares the "cyclic group derived from a finite field yields a near-optimal Sidon set" theme. - AlphaEvolve — LLM-guided evolutionary search over verifier-checked numeric parameter spaces — flagged (wiki/concepts/alphaevolve-constant-optimization.md) as a plausible tool to point at this construction's free parameters (digit-block growth rate, choice of auxiliary primes $q_j$) for empirical exponent/constant improvement.