Ajtai–Komlós–Szemerédi (1981): first improvement on the trivial $N^{1/3}$ infinite Sidon bound, $A(x)\\gg(x\\log x)^{1/3}$

Statement

Erdős asked whether the exponent $1/3$ in the trivial greedy/inductive lower bound for infinite Sidon sets could be beaten by any construction at all. A Sidon set (or $B_2$ set) $A\subset\mathbb N$ is a set all of whose pairwise sums $a+a'$ ($a\le a'\in A$) are distinct; write $A(x):=|A\cap[1,x]|$ for its counting function. The classical greedy/inductive construction (Mian–Chowla, Erdős–Rényi era) gives, for every infinite Sidon set built by always taking the next integer that creates no collision, $$A(x)\gg x^{1/3},$$ and for roughly fifty years no infinite Sidon set was known that beat this exponent. Erdős offered \$25 for any construction achieving $N^c$ for some $c>1/3$, and \$100 for a construction achieving $\omega(N)\,N^{1/3}$ for any $\omega(N)\to\infty$ (both prizes cited via erdosproblems.com's problem-39 bibliography, cross-confirmed in wiki/problems/39.md).

Theorem (Ajtai, Komlós, Szemerédi, 1981). There exists an infinite Sidon set $A\subset\mathbb N$ with $$A(x)\gg (x\log x)^{1/3}.$$ M. Ajtai, J. Komlós, E. Szemerédi, "A dense infinite Sidon sequence," *European Journal of Combinatorics* 2 (1981), 1–11.

This settled both of Erdős's prize problems at once — it beats exponent $1/3$ (the \$25 problem) via an explicit $\omega(N)=(\log N)^{1/3}\to\infty$ multiplicative gain over the trivial bound (the \$100 problem) — and it was the first improvement of any kind on the 1930s–40s trivial bound.

Facts

- Superseded, but only much later. The exponent itself (not just the log-factor) was first beaten seventeen years later by Ruzsa (1998), $A(x)\gg x^{\sqrt2-1+o(1)}$ ($\sqrt2-1\approx0.4142 > 1/3$) — see Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998). Ruzsa's construction does not build on AKS's log-factor gain at all; it uses an entirely different multiplicative-to-additive (primes $\to\log p$) transfer. The $(x\log x)^{1/3}$ bound is therefore now numerically obsolete, but its method, not its bound, is what later problems depend on. - The engine is a purely graph-theoretic lemma, proved by a genuinely new probabilistic technique. AKS's paper introduces (independently of, and predating, Vojtěch Rödl's 1985 "nibble" paper) the semi-random method: an absolute constant $c>0$ such that every $n$-vertex triangle-free graph $G$ of average degree at most $d$ has independence number $$\alpha(G) \ge c\,\frac{n}{d}\log d.$$ This is a genuine, structural improvement over the *trivial* bound $\alpha(G)\ge n/(d+1)$ that holds for every graph (Turán/Caro–Wei) — the $\log d$ factor is available only because $G$ is triangle-free. J. Shearer later sharpened the constant to $(1-o(1))(n/d)\log d$, matching the truth up to lower-order terms. - Same lemma, same paper, a second famous corollary: $R(3,k)=O(k^2/\log k)$. The identical triangle-free-independent-set bound is the tool behind the classical upper bound on the off-diagonal Ramsey number $R(3,k)$ (a triangle-free graph on $n=\Theta(k^2/\log k)$ vertices with no independent $k$-set would violate the lemma) — see Erdős #165 — asymptotic formula for the Ramsey number R(3,k). That the *same single lemma*, proved once, cracks both a Ramsey problem and an additive-combinatorics density problem is the historical demonstration that the semi-random method is a general-purpose tool, not a Sidon-specific trick. - Extended almost immediately to hypergraphs, disproving Heilbronn's triangle conjecture. Komlós, Pintz, and Szemerédi generalized the 2-uniform (graph) semi-random lemma to 3-uniform hypergraphs, using it to disprove a long-standing conjecture of Heilbronn on the minimum triangle area in $n$ points in the unit square — the first sign the method transfers across uniformities, not just across problems at fixed uniformity. - Origin of the "nibble." Rödl's independently-arrived-at 1985 packing/covering paper ("On a packing and covering problem," *European J. Combin.* 6 (1985), 69–78) gave the technique its now-standard name and pushed it into design theory; the AKS 1981 Sidon paper is the earliest known instance of the *method itself* (semi-random construction + concentration to control a triangle-free / low-codegree structure), predating that naming by four years. See Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings for the fully-generalized modern statement (hypergraph matchings/covers, Kostochka–Rödl, Vu, Gould–Kelly 2025) and its other Erdős-problem applications (large prime gaps Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), the Jacobsthal function Erdős #687 — estimate the Jacobsthal covering function Y(x), $R(3,k)$ Erdős #165 — asymptotic formula for the Ramsey number R(3,k)).

Solution

**The transferable idea: reduce a greedy/inductive extremal-density construction to an independence-number question in a naturally *triangle-free* "conflict graph," then use the semi-random method — not the trivial Turán bound — to extract a free $\log d$ multiplicative gain over whatever the naive greedy bound would give.**

1. Why the trivial bound is $x^{1/3}$ in the first place. Building a Sidon set by always adjoining the next integer that creates no sum-collision is exactly a greedy independent-set construction in the graph $G_x$ whose vertices are the as-yet-unused candidates in a window of size $\sim x$ and whose edges join two candidates whenever choosing both together would create a collision with each other or with previously chosen elements. Each already-chosen element forbids $O(1)$ new pairs per additional chosen element, so this conflict graph has average degree $d=\Theta(|A|)$ where $|A|$ is the target set size; running the trivial *every*-graph bound $\alpha(G)\ge n/(d+1)$ through this self-consistency (density $\sim n/d$, with $d$ itself scaling like the density) is exactly what produces the classical exponent $1/3$. 2. The conflict graph is triangle-free — a structural, not incidental, fact. A triangle in the conflict graph would require three pairwise-colliding candidates, i.e. three simultaneous sum-equality constraints among four-or-fewer integers in a bounded window — a strictly higher-codimension coincidence than a single pairwise collision, and one that (for the standard window/scale choice used in these constructions) does not occur. This is the same generic phenomenon exploited by essentially every Sidon-type extremal construction in this technique family (compare the finite, fully-elementary log-based warm-up in Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998), where the analogous "bad quadruple" structure is likewise sparse/rigid by unique-factorization rather than by chance). 3. Swap the trivial independence bound for the AKS semi-random bound, for free. Since the conflict graph is triangle-free, it is *not* subject only to the universal $\alpha(G)\ge n/(d+1)$ bound — it satisfies the strictly stronger $\alpha(G)\ge c(n/d)\log d$. Re-running the *exact same* self-consistency argument that produced $x^{1/3}$ from the weak bound, but with the strong bound in its place, produces $x^{1/3}$ multiplied by an extra factor of $(\log d)^{1/3}\sim(\log x)^{1/3}$ — precisely the $(x\log x)^{1/3}$ improvement. No new arithmetic input was needed; the entire gain comes from upgrading one graph-theoretic black box (naive independence bound $\to$ semi-random independence bound) inside an unchanged reduction. 4. How the semi-random bound itself is proved (the reusable machine). Rather than picking one random large subset of $G$ (a "big gulp," which for a triangle-free graph only recovers the trivial $n/d$ bound after removing the doomed-vertex neighborhoods), take many *small* random subsets ("nibbles") in succession: each round randomly samples a sparse fraction of the remaining vertices, deletes conflicts, and — because $G$ is triangle-free — a vertex and its random neighbors essentially never "double up" on the same forbidden structure, so each round's yield is provably close to what a naive expectation calculation predicts. Iterating for $\Theta(\log d)$ rounds, and using concentration (originally second-moment/Chebyshev-type arguments; in later, more powerful treatments, the Lovász Local Lemma or Talagrand-type inequalities) to control the *whole trajectory* of degrees across all rounds simultaneously, accumulates a total yield of $\Theta((n/d)\log d)$ rather than the one-round $\Theta(n/d)$ — the extra $\log d$ literally *is* the number of profitable rounds the triangle-free hypothesis allows before degree and codegree collapse together. See Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings for this mechanism generalized to hypergraphs and quantified precisely.

Why this transfers. Any problem of the shape "greedily build a maximum-density combinatorial object by repeatedly avoiding a forbidden local pattern" is, after the same reduction, an independence-number question in a conflict graph. Whenever that conflict graph can be shown triangle-free (or, in the hypergraph generalization, low-codegree), the naive $n/d$ bound used by any first-pass greedy/inductive argument is *never* the best available — the semi-random method upgrades it to $(n/d)\log d$ automatically, at the cost only of the concentration machinery, with no new problem-specific idea required. This is exactly the "free upgrade" later reused, in the same paper's own extension, for Heilbronn's triangle problem (3-uniform hypergraph version), for $R(3,k)$ (same 2-uniform lemma, different corollary), and — via the fully general, quantified modern form — for large prime gaps and the Jacobsthal function (Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings). It is the historical template for "check triangle-freeness/low-codegree first, then swap in the nibble bound" as a generic strengthening move on any greedy density construction, and it is the reason the *technique* of AKS81b, unlike its now-obsolete numerical bound, is still load-bearing for open problems in this cluster (e.g. as the baseline any further attack on Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set must either reuse in a sharper form or replace outright, exactly as Ruzsa's unrelated log-prime method eventually did for the exponent itself).

Related

- Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — the still-open \$500 Erdős problem this result was the historic first progress on ($A(x)\gg_\epsilon x^{1/2-\epsilon}$ for all $\epsilon$?); AKS81b settled Erdős's two smaller prize sub-problems (\$25, \$100) en route, and its record was later superseded in exponent (not just constant) by Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998). - Ruzsa's probabilistic infinite Sidon set, $A(x)=x^{\\sqrt2-1+o(1)}$ (1998) — the 1998 result that replaced AKS81b's $(x\log x)^{1/3}$ with the still-current record $x^{\sqrt2-1+o(1)}$, via a completely different (multiplicative-Sidon-primes $\to$ additive-Sidon-logs) technique; the two pages together bracket the full history of the infinite-Sidon-density record. - Sidon sets / B_2 sets / Golomb rulers — the central object; already documents this result as part of its infinite-Sidon-set density history (Facts section). - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the fully general, modern, quantified statement of the semi-random/nibble method this paper introduced, including its other major applications (large prime gaps Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), Jacobsthal function Erdős #687 — estimate the Jacobsthal covering function Y(x), $R(3,k)$ Erdős #165 — asymptotic formula for the Ramsey number R(3,k)) and the precise mechanism (isolated-edge matchings, waste-set equalization, degree/codegree concentration) sketched only informally here. - Erdős #165 — asymptotic formula for the Ramsey number R(3,k) — $R(3,k)=O(k^2/\log k)$: the second famous corollary of the *same* triangle-free-independent-set lemma proved in this paper, historically demonstrating the method's generality beyond Sidon sets. - Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble — alias page confirming "semi-random method" and "Rödl nibble" name the identical technique in the literature.