Sidon sets / B_2 sets / Golomb rulers

Statement

Sidon set / $B_2$ set (Simon Sidon, via his work on Fourier series; named/studied by Erdős–Turán 1941): a set $A$ of integers (or elements of an abelian group) such that all pairwise sums $a+b$ with $a\le b\in A$ are distinct. Equivalently — and this is the form most used in proofs — all pairwise differences $a-b$ ($a\ne b\in A$) are distinct, i.e. every nonzero element of the ambient group is represented as a difference of two elements of $A$ at most once. The two formulations (distinct sums / distinct differences) are equivalent for sets of integers by a short direct argument (en.wikipedia.org/wiki/Sidon_set).

Golomb ruler: a set of integer marks $a_1<\cdots<a_m$ such that no two of the $\binom{m}{2}$ pairwise distances $a_i-a_j$ coincide. This is definitionally identical to the distinct-differences form of a Sidon set — Wikipedia states the equivalence explicitly: "all finite Sidon sets are Golomb rulers, and vice versa" (en.wikipedia.org/wiki/Golomb_ruler, en.wikipedia.org/wiki/Sidon_set), proved by contradiction (a repeated distance would force a repeated sum). The *order* of a ruler is $m$ (number of marks); its *length* is $a_m-a_1$. Discovered independently in three contexts: Sidon (1932, harmonic analysis), Babcock (1953, radio-interference engineering), and (as *perfect difference sets*, a closely related but distinct finite-field object, see Facts) Singer (1938, finite projective geometry).

Generalization — $B_h$ sets / $B_h[g]$ sets: $A$ is a $B_h$ set if every $h$-fold sum $a_1+\cdots+a_h$ ($a_1\le\cdots\le a_h\in A$) is distinct (Sidon = $B_2$); $A$ is $B_h[g]$ if every value is attained as such a sum by at most $g$ unordered $h$-tuples (Sidon = $B_2[1]$). This relaxation trades exact uniqueness for higher density — see Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #158 (ancestor result) — the solved $g=1$ liminf-density theorem for infinite Sidon sets, and its bounded-multiplicity generalization.

Core extremal question (function $h(N)$): let $h(N)$ = the largest size of a Sidon set contained in $\{1,\dots,N\}$. The central open problem of the whole area (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets) is the exact second-order asymptotics of $h(N)$; only the leading order $h(N)=(1+o(1))\sqrt N$ is settled (Singer 1938 lower bound + Erdős–Turán 1941 upper bound).

Facts

- Elementary upper bound (why $h(N)=O(\sqrt N)$ at all): for a Sidon set $A\subseteq\{1,\dots,N\}$ of size $m$, the $\binom m2$ positive pairwise differences are all distinct elements of $\{1,\dots,N-1\}$, so $\binom m2\le N-1$, giving $m\le\sqrt{2N}+O(1)$ — a one-line pigeonhole/counting argument. - Sharpened upper bound (Erdős–Turán 1941, [ErTu41]): a more refined "shift/double-counting" argument (bounding, for each shift $t$, how many pairs of elements of $A$ can differ by values near $t$, then summing over a window of shifts) improves the constant to $h(N)\le\sqrt N+O(N^{1/4})$. This exact inequality has been progressively sharpened on the *error term* only, never the leading $\sqrt N$: Lindström [Li69] 1969; Balogh–Füredi–Roy, arXiv:2103.15850 (2021); O'Bryant, arXiv:2207.07800 (2022): $h(N)\le N^{1/2}+0.99703N^{1/4}$; current published record, Carter–Hunter–O'Bryant, arXiv:2310.20032 (2023, publ. Acta Math. Hungarica 2025): $h(N)\le N^{1/2}+0.98183N^{1/4}+O(1)$ (computer-assisted; hand-verifiable weaker version gives $0.99058$); informal further improvement (Nov 2025) via Terence Tao + Daniel Carter running AlphaEvolve on the same admissible-parameter landscape, pushing the constant to $1.9526463099204112$ in the equivalent diameter form (terrytao.wordpress.com/2025/11/05, documented in wiki/problems/30.md). - Matching lower bound — Singer's finite-field/projective-plane construction (1938): for every prime power $q$, the finite projective plane $PG(2,q)$ admits a cyclic collineation permuting its $q^2+q+1$ points; the point-indices lying on one fixed line, read off along the resulting cyclic order, form a perfect difference set of size $q+1$ in $\mathbb Z_{q^2+q+1}$ — every nonzero residue mod $q^2+q+1$ arises as a difference of two set elements *exactly once* (arXiv:1908.05591 background). Reduced mod the group order and reinterpreted over the integers this gives a Sidon set of size $q+1\approx\sqrt N$ inside $\{1,\dots,N\}$, i.e. $h(N)\ge(1-o(1))\sqrt N$ — matching the Erdős–Turán upper bound in leading order. Formalized end-to-end in Lean 4 with zero `sorry`s in arXiv:2605.03274 (May 2026): "for every prime power $q=p^k$ there exists a Sidon set modulo $q^2+q+1$ of cardinality $q+1$." - Perfect Golomb rulers do not exist for $\ge5$ marks (en.wikipedia.org/wiki/Golomb_ruler) — a perfect ruler would measure *every* distance up to its length, which is strictly stronger than being Sidon/collision-free; this non-existence result is why practical work (radio astronomy, coding) instead optimizes *optimal* (shortest-for-given-order) rulers, a NP-hard-flavored search problem — optimal rulers for orders 1–28 are known, with order-28 completed by the distributed.net computing project in November 2022. - Infinite Sidon sets are provably much thinner than the finite-set density. Erdős proved every infinite Sidon set $A\subset\mathbb N$ has $\liminf_N|A\cap\{1,\dots,N\}|/N^{1/2}=0$ (cited in wiki/problems/39.md, /40.md, /1191.md) — density $N^{1/2}$ cannot be sustained infinitely often. Best known construction: Ruzsa [Ru98], $|A\cap\{1,\dots,N\}|\gg N^{\sqrt2-1+o(1)}$ ($\approx N^{0.4142}$), via the fact that the primes are *multiplicatively* Sidon, so $\{\log p:p\text{ prime}\}$ is *additively* Sidon over the reals, discretized/randomized into an integer construction; this exponent is unimproved since 1998 (confirmed as still-the-record by O'Bryant, arXiv:2606.28651, 26 Jun 2026). Cilleruelo gave an explicit non-probabilistic analogue with the same exponent via a discrete-logarithm construction (arXiv:1209.0326: fixed increasing primes + a primitive root mod each, base-expansion encoding), later generalized by Cilleruelo–Tesoro (arXiv:1206.3087) to $B_3,B_4$ sequences with exponent $x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$ — showing the log/discrete-log trick is a genuine reusable engine, not a one-off. An earlier (1981) improvement over the trivial exponent used the semi-random ("nibble") method, introduced in Ajtai–Komlós–Szemerédi's own paper "A Dense Infinite Sidon Sequence" (giving $\gg(N\log N)^{1/3}$) — this is the historical origin of the nibble method later generalized as the Rödl nibble across combinatorics. - $B_h$ generalization, $h=3$ (triple sums): Bose–Chowla (1962) give a construction with $|A|\sim N^{1/3}$; Green (2001, PDF fetched per wiki/problems/241.md) proves a matching-order Fourier/additive-energy upper bound $A(3,1,N)\le(7/2)^{1/3}N^{1/3}(1+o(1))$ — leading order settled only for $h=2$ (Sidon) and, up to the Green/Bose–Chowla constant, for $h=3$; general $r$-fold Bose–Chowla conjecture open for $r\ge4$. - $B_h[g]$ relaxation (bounded, not unique, representation) trades density for exactness: Erdős–Rényi and later Kolountzakis/Cilleruelo–Trujillo/Pliego (arXiv:2405.04154) construct $B_2[g]$ sequences with density up to $N^{g/(2g+1)}\to N^{1/2}$ as $g\to\infty$ — the density ceiling $N^{1/2}$ is only reachable in the limit of *unbounded* multiplicity, which is why the strict Sidon case ($g=1$) is provably thinner (Erdős's liminf-zero theorem above). - $\gamma$-Golomb rulers (O'Bryant, 2026, arXiv:2606.28651): a further generalization unifying Sidon sets ($\gamma=1$) with bounded-multiplicity-$\gamma$ difference sets; proves via a block-decomposition + weighted Cauchy–Schwarz "energy" argument that $\liminf_n A(n)/\sqrt{n/\log n}\le(2/\sqrt{\log2})\sqrt\gamma\approx2.402\sqrt\gamma$, sharpening a 1955-era constant (Stöhr) from $\approx21.2$ (Cilleruelo) — the same block-energy method Erdős and Halberstam–Roth used in 1966, believed by its own most recent user to be "fully optimized," per wiki/problems/1191.md. - Applications outside pure counting: Golomb rulers are used directly in engineering — radio-astronomy synthesis arrays (minimum-redundancy Fourier-component sampling), error-correcting-code design, and radio-frequency channel assignment to reduce intermodulation interference (en.wikipedia.org/wiki/Golomb_ruler) — a rare case in this wiki area of a purely combinatorial extremal object with direct hardware applications. - Equivalent reformulation used across additive combinatorics — "dissociated sets": a set $A$ is dissociated if the only $\{-1,0,1\}$-coefficient linear combination of its elements summing to $0$ is trivial; this is essentially the multiplicative/$\log_2$ analogue of the Sidon condition and is the formulation used by Ruzsa and Conway–Guy for related counting problems, cited as concept/dissociated-sets in wiki/problems/1.md.

Technique

How Sidon sets are used as a proof tool (recombination-ready steps), not just as an object of study:

1. As an extremal-density gadget: whenever a problem needs "a large set with no nontrivial additive coincidences" (distinct sums, distinct differences, no solutions to $x+y=z+w$ except trivially), reach for a Sidon set — it is the maximal-density object with *zero* tolerance for additive collisions of a fixed type. The density ceiling $N^{1/2}$ (finite) or $N^{\sqrt2-1+o(1)}$ (infinite) is the standard benchmark against which "how much structure can you avoid" questions are measured. 2. Construction recipe (finite, near-optimal): use Singer's projective-plane/finite-field method — pick a prime power $q$ near $\sqrt N$, take the cyclic difference set of size $q+1$ inside $\mathbb Z_{q^2+q+1}\approx\mathbb Z_N$ coming from a Singer cycle acting on $PG(2,q)$, and lift back to integers. This is the go-to explicit (non-random) construction achieving the $\sqrt N$ leading order, used as the lower-bound half of essentially every Sidon-type extremal result in this wiki (Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets, Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets via Bose–Chowla, an analogous finite-field construction for $B_3$). 3. Construction recipe (infinite, near-record density): use the log/discrete-log trick — start from a multiplicatively-Sidon set (primes are the canonical example, since unique factorization forces distinct products), pass to $\{\log p\}$ (additively Sidon over $\mathbb R$ by taking logs of a multiplicative-Sidon set), then discretize either probabilistically (Ruzsa 1998, Diophantine-approximation argument) or explicitly (Cilleruelo, replacing $\log$ with a discrete logarithm mod a sequence of primes). This "exponentiate/take-logs to move between multiplicative and additive Sidon-ness" move is the single reusable idea behind every record infinite-Sidon-set construction since 1998, and it transfers directly to $B_h$ ($h\ge3$) with the same exponent formula (Cilleruelo–Tesoro). 4. Upper-bound recipe (the "distinct differences ⇒ pigeonhole" argument): whenever a set has all pairwise differences distinct, the number of pairs is trivially bounded by the size of the ambient difference range — this one-line argument ($\binom m2\le N-1\Rightarrow m=O(\sqrt N)$) is the starting point, refined by Erdős–Turán's shift-counting argument (bound, for a window of shift values $t$, the number of pairs of elements at distance $\approx t$, then sum/optimize over the window) for the sharper $\sqrt N+O(N^{1/4})$ bound. This shift-counting refinement is itself a template: whenever you have a distinctness-of-differences (or distinctness-of-sums) hypothesis, a windowed/weighted double-counting argument typically shaves the error term below the trivial pigeonhole bound — the exact mechanism Balogh–Füredi–Roy → O'Bryant → Carter–Hunter–O'Bryant have iterated on for 85 years, with the newest iteration (2025) being computer/AlphaEvolve-assisted numerical optimization of the same admissible-parameter landscape rather than a new proof idea. 5. As a building block for asymptotic bases: Sidon/$B_h$ sets have recently (2010–2024) been shown to be extendable into asymptotic bases of order $m$ (every large integer is a sum of $m$ elements) for $m=5$ (2010), $m=4$ (2014), $m=3$ (2024) — i.e. beyond their extremal-counting role, dense Sidon-type sets are directly usable as *additive-basis* constructions, a distinct downstream application (en.wikipedia.org/wiki/Sidon_set). 6. WHEN this technique applies: any problem phrased as "how large/dense can a set be while avoiding a repeated additive relation of a fixed, small combinatorial type (sum, difference, or bounded linear pattern)" is a Sidon/$B_h$-type problem, and the finite-field (Singer/Bose–Chowla) vs. shift-counting (Erdős–Turán) machinery transfers directly. It does not directly apply to genuinely unbounded-order patterns (e.g. arbitrarily long APs) — that regime belongs to Szemerédi/polynomial-method territory (Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)), a mechanistically different toolkit (bounded-alphabet tensor-rank sandwiches rather than difference-counting). 7. WHY the finite-field construction achieves the exact matching order: a cyclic difference set built from a projective plane's automorphism has, by the geometric axiom "any two lines meet in exactly one point," an *automatic* uniqueness-of-difference property baked in by the incidence structure itself — no counting or randomness is needed to verify Sidon-ness, only the combinatorial design axioms of $PG(2,q)$. This is why Singer's 85-year-old construction has never been beaten in leading order: it is not a probabilistic near-optimum but an *exact* algebraic optimum up to lower-order terms, and the remaining 85 years of work has all gone into the $O(N^{1/4})$-scale error term, never the exponent.

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — the central open problem: sharp $h(N)=N^{1/2}+O_\epsilon(N^\epsilon)$ asymptotics for finite Sidon sets; carries the fullest technique lineage (Singer construction, Erdős–Turán shift-counting, Lindström/BFR/O'Bryant/CHO error-term chain, AlphaEvolve-assisted numerical optimization, Lean 4 formalization). - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $B_3$ (triple-sum) analogue; Bose–Chowla lower bound, Green 2001 upper bound; same construction-vs-counting game one level up in $h$. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — infinite Sidon set density $N^{1/2-\epsilon}$ for all $\epsilon$; open; Ruzsa's $N^{\sqrt2-1+o(1)}$ construction is the current record, unimproved since 1998. - Erdős #40 — sharp density threshold for Erdős–Turán — Erdős–Turán conjecture on representation-function boundedness for additive bases, closely tied to the $B_2[g]$ density-vs-boundedness trade-off. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the $B_3$ infinite-set liminf-density analogue of #39. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — liminf-oscillation question for infinite Sidon sets (Stöhr 1955 / Erdős 1980), current best constant via O'Bryant's 2026 $\gamma$-Golomb-ruler block-energy method. - erdos/14 — unique-sum-representation complement density, same Sidon-set cluster. - Erdős #42 — every Sidon set has a same-scale Sidon set with disjoint differences, Erdős #43 — Sidon-pair size bound (disproved) — sibling finite Sidon-pair-disjointness problems, recently SOLVED/DISPROVED with heavy AI (GPT-5.5-Pro, ChatGPT+Codex, Terence Tao) assistance on erdosproblems.com — a concrete precedent for AI-assisted attacks on this problem cluster's finite/algorithmically-checkable end. - Erdős #158 (ancestor result) — the solved $g=1$ liminf-density theorem for infinite Sidon sets, and its bounded-multiplicity generalization, erdos/840 — the $B_2[2]$ multiplicity-relaxation and quasi-Sidon ($|A+A|\sim\binom{|A|}2$) relaxations respectively. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — the sibling toolkit for *unbounded*-order additive patterns (e.g. 3-APs over bounded alphabets); mechanistically distinct (tensor-rank sandwich vs. difference-counting) but addresses structurally similar "avoid additive coincidences" questions. - concept/dissociated-sets — the $\{-1,0,1\}$-linear-combination reformulation of the same no-nontrivial-additive-relation idea, used by Ruzsa and Conway–Guy.