Semi-random nibble vs. probabilistic log-prime/discrete-log constructions: two routes to beating the greedy exponent

Statement

Two historically entangled but technically distinct families solve the same shape of problem — "build a dense/near-perfect combinatorial structure that avoids some collision pattern" — by the same high-level template (construct almost-extremal, bound the rare bad events, delete them) but with different engines under the hood:

1. The semi-random nibble method (Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings, Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble): iterate many *small* random selections ("nibbles") of a hypergraph's edges, each round followed by a concentration argument (originally second-moment/Chebyshev; now Lovász Local Lemma or Talagrand-type), so that a low-codegree, near-regular hypergraph is whittled down to a near-perfect matching/covering/colouring after $\Theta(\log D)$ rounds. Introduced implicitly by Ajtai–Komlós–Szemerédi, "A dense infinite Sidon sequence," *European J. Combin.* 2(1) (1981), 1–11, giving an infinite Sidon set of density $\gg(N\log N)^{1/3}$ — the first improvement past the trivial greedy exponent $1/3$ — and made into a general-purpose tool by V. Rödl, "On a packing and covering problem," *European J. Combin.* 6 (1985), 69–78 (resolving the Erdős–Hanani conjecture).

2. The probabilistic log-prime / discrete-log Sidon construction (Ruzsa's log-of-primes probabilistic Sidon construction, Discrete-logarithm explicit Sidon construction (Cilleruelo), Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue): transport the *exact*, zero-error multiplicative-Sidon-ness of the primes (a one-line consequence of unique factorization: $p_1p_2=p_3p_4\Rightarrow\{p_1,p_2\}=\{p_3,p_4\}$) into an additive setting via a logarithm-type map — a genuine real logarithm with a randomized truncation parameter $\alpha\in[1,2)$ (I. Ruzsa, "An infinite Sidon set," *J. Number Theory* 68 (1998), 63–71, probabilistic/non-constructive) or a discrete logarithm mod a sequence of auxiliary primes (J. Cilleruelo, "Infinite Sidon sequences," arXiv:1209.0326, explicit/deterministic) — then delete the rare additive collisions the discretization step introduces. Both variants achieve the strictly larger exponent $x^{\sqrt2-1+o(1)}$, $\sqrt2-1\approx0.4142$, still the record for an infinite Sidon set as of O'Bryant, arXiv:2606.28651 (26 Jun 2026).

The historical link: AKS 1981 is the common ancestor. Ajtai–Komlós–Szemerédi's 1981 semi-random construction was the *first* technique to beat the greedy $1/3$ exponent for infinite Sidon sets, using exactly the "many small random deletions + concentration" mechanism later generalized and named "the Rödl nibble." Ruzsa's 1998 log-of-primes construction is a structurally different randomization mechanism (parametrized digit-truncation of an exact real-valued sequence, not incremental random deletion from a hypergraph) that superseded it in density, jumping from $(N\log N)^{1/3}$ straight to $N^{\sqrt2-1}$. The two families are therefore siblings in *motivation* (same problem, same "probabilistic method" parent) but cousins, not twins, in *mechanism* — the nibble deletes from an initially-huge random hypergraph selection round by round; the log-prime method starts from an already highly-structured, near-exact multiplicative object and only needs one (or a bounded sequence of) discretization-and-delete steps.

Facts

- Where the nibble still wins: generality. The nibble method is a *general-purpose* hypergraph-matching/covering/colouring engine, applicable whenever a near-regular, low-codegree hypergraph structure can be exhibited — it underlies solutions far outside Sidon sets: large prime gaps (Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), via Ford–Green–Konyagin–Maynard–Tao arXiv:1412.5029's reweighted nibble), the Jacobsthal function (Erdős #687 — estimate the Jacobsthal covering function Y(x)), Ramsey number $R(3,t)$ asymptotics (Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Kim 1995), and near-optimal edge/list-colouring (Pippenger–Spencer 1989; Kahn 1996; Molloy–Reed 2000). The log-prime/discrete-log method, by contrast, is narrow: it only fires when the target collision-avoidance property is secretly a *unique-factorization* fact in a UFD (primes in $\mathbb Z$, Gaussian primes in $\mathbb Z[i]$, irreducibles in $\mathbb F_2[X]$) that can be transported via a logarithm-type isomorphism. - Where the log-prime method wins: sharper density on its narrow target. For infinite Sidon sets specifically, the nibble-based AKS 1981 record $(N\log N)^{1/3}$ was strictly beaten by Ruzsa's log-of-primes method reaching $N^{\sqrt2-1}$ ($\sqrt2-1\approx0.4142>1/3\approx0.3333$) — the log-prime method exploits the *exact* (zero-error, not merely high-probability) collision-avoidance of unique factorization, which is a strictly stronger starting point than the nibble's near-regular-hypergraph hypothesis, when that exact structure happens to be available. - A genuine derandomization exists on the log-prime side but not (in the same sense) on the nibble side. Cilleruelo's discrete-log construction (arXiv:1209.0326) fully derandomizes Ruzsa's real-log construction, replacing the "almost every $\alpha$ works" existence argument with an explicit, checkable sequence of finite discrete logarithms — see Discrete-logarithm explicit Sidon construction (Cilleruelo) for the exact mechanism. The nibble method has no comparable "replace all randomness with one exact algebraic witness" derandomization for its general hypergraph-matching output; it is inherently a randomized-algorithm-flavored technique (though the *existence* results it proves are, once concentration is invoked, effectively deterministic-with-high-probability, not probabilistic-in-the-Monte-Carlo sense). - No published hybrid of the two families exists as of 2026-07-02 (confirmed via WebSearch this session; also flagged as an open direction in Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue's own Technique section: "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"). The exponent $\sqrt2-1$ has stood unimproved for 28 years across *four* independently-discovered variants of the log-prime family alone (real log, discrete log, Gaussian-integer argument, $\mathbb F_2[X]$-log) — a strong signal that closing the gap to Erdős's conjectured $N^{1/2-\epsilon}$ (Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, \$500) needs either a genuinely new construction or exactly the kind of cross-pollination this page flags as unexplored. - Both families share the identical three-step "probabilistic deletion method" DNA, despite differing in what gets randomized: (1) build an object that is *almost* extremal (a near-regular hypergraph pre-nibble; a raw digit-encoded log-of-primes sequence pre-deletion); (2) bound the number of "bad" events (colliding hyperedges after a nibble round; colliding 4-tuples after discretization) via a concentration/expectation argument small enough to be $o(1)$ relative to scale; (3) delete one element/edge per bad event, verifying the deleted fraction doesn't damage the target density/matching-size exponent. This shared template — "construct near-perfect, then repair by deletion, using a first/second-moment bound to certify the repair is cheap" — is the actual reusable idea beneath both surface techniques; see Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs for the concentration machinery common to the classical (pre-LLL) versions of both. - Blockwise/scale separation is the load-bearing engineering trick in the log-prime family, playing a role structurally analogous to concentration-per-round in the nibble. Both Ruzsa's and Cilleruelo's constructions insert zero-padding between digit blocks so an additive collision must decompose block-by-block into per-modulus congruences (see Ruzsa's log-of-primes probabilistic Sidon construction, Discrete-logarithm explicit Sidon construction (Cilleruelo)); the nibble's analogous device is the "waste set" equalization step (Gould–Kelly 2025, arXiv:2511.11375, §6.1) that keeps every vertex's survival probability identical across rounds so the leftover can again be treated as near-regular. Both are examples of "impose an artificial independence structure so the collision-counting argument stays tractable across an unbounded/iterated construction."

Technique

WHEN to reach for which. - Reach for the nibble when the target object is naturally a hypergraph matching/covering/colouring/packing (design-theoretic or Ramsey-flavored), the relevant near-collision-avoidance hypothesis is a *statistical* one (near-regularity, low codegree — not an exact algebraic identity), and you need an existence result that tolerates a small, uncontrolled leftover (or is willing to pair with the absorption method to finish exactly). - Reach for the log-prime/discrete-log family when the target collision-avoidance property is secretly a unique-factorization fact in a UFD — i.e. the problem is really "no nontrivial multiplicative relation among chosen primes/irreducibles should survive being mapped into an additive group" — and either (a) an explicit, algorithmically-producible witness is wanted (discrete-log route) or (b) only existence is needed and a real-valued logarithm is more convenient to set up (Ruzsa's real-log route). - When your problem doesn't obviously fit either template, ask whether it can be *recast* into one: many "avoid a collision pattern in a dense subset" problems can be reformulated either as a hypergraph-matching problem (unlocking the nibble) or as a hidden-multiplicative-structure problem (unlocking log-transport) — the reformulation step is itself usually the creative work, as documented for FGKMT's prime-gaps hypergraph recasting (Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)) on the nibble side and Cilleruelo's mixed-radix digit encoding on the log-prime side.

WHY each works, side by side. - *Nibble*: randomly thinning a near-regular hypergraph reduces a vertex's *degree* roughly linearly in the thinning probability $p$ but reduces *codegree* (pairwise overlap) roughly quadratically — this asymmetry means the ratio $D/D_2$ (how far from "perfectly regular" the leftover is) shrinks with each round, so $\Theta(\log D)$ rounds of controlled random thinning plus concentration produce a near-perfect matching with a provably tiny uncovered residual. - *Log-prime*: unique factorization gives an *exact* (not merely high-probability) multiplicative-Sidon structure on the primes for free; a logarithm-type isomorphism transports this exactly into an additive group with zero loss; the only place randomness/approximation is needed at all is in bounding the rare collisions created by the unavoidable discretization step (truncating a real log to finite binary digits, or reducing a discrete log mod a finite auxiliary prime) — a fundamentally *smaller* amount of "give" than the nibble needs, because the starting structure (unique factorization) is already exact rather than merely statistical.

HOW to use this comparison to prove things (recombination steps for a solver facing a new Erdős-style density/collision-avoidance problem): 1. Classify the collision-avoidance hypothesis. Is it a *statistical/regularity* hypothesis (bounded codegree, near-regular degree sequence) → nibble is the default. Is it an *exact algebraic* hypothesis reducible to unique factorization in some ring → log-prime family is the default. 2. Check which exponent/bound each route would give, if both apply. For infinite Sidon sets specifically, the log-prime route ($\sqrt2-1\approx0.414$) strictly beats the historical nibble route ($1/3$) — but this is problem-specific, not a universal ranking; for Ramsey numbers ($R(3,t)$, Erdős #165 — asymptotic formula for the Ramsey number R(3,k)) the nibble (Kim 1995) was long the record and only recently overtaken by nibble-*free* pseudorandom constructions (2025), a reminder that neither family is universally optimal even within its own historical signature application. 3. If neither route alone closes an open gap (e.g. Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set's conjectured $N^{1/2-\epsilon}$, currently stuck at the log-prime family's $N^{\sqrt2-1}$ ceiling for 28 years), consider explicitly whether a hybrid is possible: e.g. using a nibble-style iterated-deletion argument to control the collision tuples that a log-prime discretization step creates, rather than the log-prime family's own pigeonhole/expectation bound — no such hybrid has been published as of 2026-07-02, making it a genuinely open recombination direction rather than a known dead end. 4. When neither applies: both families are lower-bound/existence techniques; neither says anything about matching upper bounds (for Sidon-set density, the upper-bound side is the Erdős–Turán shift-counting argument, Sidon sets / B_2 sets / Golomb rulers; for hypergraph covering, it's the trivial counting bound the nibble is shown to asymptotically achieve). If the open problem is an upper bound / impossibility result, look elsewhere entirely.

Related

- Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the canonical, fully-sourced deep-dive on the nibble/semi-random method: precise Erdős–Hanani statement, Kostochka–Rödl/Vu/Gould–Kelly quantified bounds, the six-step reusable recipe, and the full list of Erdős-problem applications (Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), Erdős #687 — estimate the Jacobsthal covering function Y(x), Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Erdős #159 — polynomial improvement to R(C4,Kn) upper bound, Erdős #74 — almost-bipartite graph of infinite chromatic number). - Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble — alias page redirecting to Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings; same technique, literature-standard alternate name. - Ruzsa's log-of-primes probabilistic Sidon construction — the dedicated deep-dive on Ruzsa's original 1998 probabilistic real-log construction, including the full digit-block/random-$\alpha$/almost-all-$\alpha$-deletion mechanism and the exponent-fixing optimization $\beta^2-2\beta-1=0$. - Discrete-logarithm explicit Sidon construction (Cilleruelo) — the dedicated deep-dive on Cilleruelo's explicit discrete-log derandomization matching the same exponent, including the finite warm-up, the mixed-radix infinite construction, and the $B_h$ generalization. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue — the pre-existing consolidated page covering both log-prime variants side by side in full technical detail; this page's natural "read next" companion for the log-prime side specifically. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the classical concentration machinery common to the original 1985 nibble proofs and to Ruzsa's almost-every-$\alpha$ argument; the shared mathematical tool beneath both surface techniques. - 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 nibble gave the first improvement past the trivial exponent (AKS 1981, $(N\log N)^{1/3}$), the log-prime family holds the current record ($N^{\sqrt2-1}$, unimproved since 1998/2012), and closing the remaining gap is flagged by this wiki as plausibly requiring a hybrid of the two families documented here. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$/$B_h$ infinite-density analogue; both families have been generalized here (nibble: historically first; log-prime: Cilleruelo–Tesoro arXiv:1206.3087, current record). - Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Erdős #159 — polynomial improvement to R(C4,Kn) upper bound — Ramsey-number problems where the nibble (not the log-prime family, which has no natural Ramsey analogue) is the historically dominant technique, useful contrast for "nibble's generality vs. log-prime's narrowness."