Generalized Sidon set constructions — the $B_h[g]$ toolbox (finite-field unions, interleaving, products)

Statement

$B_h[g]$ set. Fix an abelian group $G$ (usually $\mathbb Z$, $[n]=\{1,\dots,n\}$, or $\mathbb Z_n$) and integers $h\ge2$, $g\ge1$. A set $S\subseteq G$ is a $B_h[g]$ set if every element of $G$ has at most $g$ representations as an unordered sum of $h$ elements of $S$ (with repetition allowed). Equivalently, writing $S*S*\cdots*S$ ($h$-fold convolution of the indicator function) or, as Martin–O'Bryant do for $h=2$, the ordered-pair count $\|S*S\|_\infty=\max_k|\{(s_1,s_2)\in S^2:s_1+s_2=k\}|$: $S$ is $B_h[g]$ iff this max is $\le g$ (or $\le2g$/$\le2g+1$ in the ordered-count convention — conventions differ across papers on a factor of $\sim2$; always check which count a source uses, arXiv:math/0408081 p.2 flags this explicitly). $B_2[1]$ = Sidon set (Sidon sets / B_2 sets / Golomb rulers); $g\ge3$ (in the ordered convention) is what Martin–O'Bryant call a "generalized Sidon set."

The two extremal functions this toolbox is built around (arXiv:math/0408081, eq. (1)-(2)): $$R(g,n):=\max\{|S|:S\subseteq[n],\ \|S*S\|_\infty\le g\},\qquad C(g,n):=\max\{|S|:S\subseteq\mathbb Z_n,\ \|S*S\|_\infty\le g\}.$$ $C$ (the cyclic/modular version) is the workhorse: nearly every explicit construction of a large $R(g,n)$ (subset of the integers) is obtained by first building a large $C(g,n')$ (subset of $\mathbb Z_{n'}$) via finite-field algebra, then lifting to integers. Both satisfy $\Theta(\sqrt{gn})$ growth; the constant is measured by $\sigma(g):=\liminf_{n\to\infty}R(g,n)/\sqrt{\lfloor g/2\rfloor\,n}$.

Core toolbox claim: three explicit finite-field constructions (Ruzsa, Bose, Singer — originally built for Sidon sets, $g=1$) generalize uniformly to arbitrary $g$ by taking a union of $K$ shifted/scaled copies of the base construction, and a fourth device (interleaving / product of two smaller $B_h[g]$ sets) multiplies two constructions together, multiplying their $g$'s. These four moves, composed, give "the largest known generalized Sidon sets in virtually all cases" (arXiv:math/0408081 abstract) and are the concrete recipe a solver reaches for whenever a problem needs an *explicit*, *finite*, *density-$\Theta(\sqrt{gn})$* set with a prescribed bounded-representation cap $g$.

Facts

- Upper bounds on $C(g,n)$ (Theorem 1, arXiv:math/0408081, full proofs pp.8-9): $C(2,n)\le\sqrt n+1$ (pigeonhole on the $\binom{|S|}2$ distinct nonzero differences, exactly the Sidon argument); $C(3,n)\le\sqrt{n+9/4}+3/2$-type bound; $C(4,n)\le\sqrt{3n+7/6}$ (the first genuinely new/nontrivial case, via a second-moment "$S\circ S$ is small on average" argument attributed to Cilleruelo); $C(g,n)\le\sqrt{gn}$ for even $g$; $C(g,n)\le\sqrt{(1-1/g)\,gn}+1$ for odd $g$ (both via the trivial identity $|S|^2\le gn$ — each of the $n$ possible sums realized $\le g$ times — sharpened by $1$ for odd $g$ since an odd-multiplicity sum must include a "doubled" element $2s$). - Generalized Ruzsa construction: for prime $p$, generator $\theta$ of $(\mathbb Z/p)^\times$, define $a_{t,i}\equiv t\pmod{p-1}$, $a_{t,i}\equiv i\theta^t\pmod p$ for $1\le t<p$; $\mathrm{Ruzsa}(p,\theta,i):=\{a_{t,i}:1\le t<p\}\subseteq\mathbb Z_{p^2-p}$ is Sidon for a single $i$ (Ruzsa's original 1993 result). The generalization: for any $K\subseteq[1,p{-}1]$, $\mathrm{Ruzsa}(p,\theta,K)=\bigcup_{i\in K}\mathrm{Ruzsa}(p,\theta,i)$ has $|K|(p-1)$ elements and $\|(\cdot)*(\cdot)\|_\infty\le2|K|^2$ (proved via unique factorization of a quadratic over $\mathbb F_p[x]$: two sums colliding forces two of three pairs to coincide mod $p$, contradiction — arXiv:math/0408081 §3.2, full proof). - Generalized Bose construction: $q$ a prime power, $\theta$ a generator of $\mathbb F_{q^2}^\times$, $\mathrm{Bose}(q,\theta,k):=\{a\in[q^2{-}1]:\theta^a-k\theta\in\mathbb F_q\}$ is Sidon for fixed $k\ne0$; the union over $K\subseteq\mathbb F_q\setminus\{0\}$ gives $|K|q$ elements with $\|\cdot\|_\infty\le2|K|^2$, again via unique factorization (now in $\mathbb F_{q^2}[x]$, a quadratic in the unknowns). - Generalized Singer construction: $q$ a prime power, $\theta$ a generator of $\mathbb F_{q^3}^\times$; for $\vec k=(k_1,k_2)\in\mathbb F_q^2$ define a set of size $q$ (or $q+1$ including $0$) in $\mathbb Z_{q^2+q+1}$ from the coefficient of $1$ when $\theta^{s'}$ is expanded in the basis $\{\theta^2,\theta,1\}$ of $\mathbb F_{q^3}/\mathbb F_q$. Union over any $K\subseteq\mathbb F_q\times\mathbb F_q$ containing no two $\mathbb F_q$-scalar-multiple pairs gives $|K|q+1$ elements with $\|\cdot\|_\infty\le2|K|^2$ (proved by a heavier unique-factorization argument tracking two collision-eliminating auxiliary quadratics — arXiv:math/0408081 §3.2, pp.10-11). Singer's construction is "slightly thicker" (denser) than Bose's, which is slightly thicker than Ruzsa's, at the cost of a more complex proof. - Product/interleaving construction (Kolountzakis $\to$ Jia $\to$ Cilleruelo–Ruzsa–Trujillo/Habsieger–Plagne $\to$ Martin–O'Bryant, arXiv:math/0408081 §2.2.4, Theorem 2(iv)-(v)): if $S\subseteq\mathbb Z_x$ is $B_2[g]$ and $M\subseteq\mathbb Z_y$ is $B_2[f]$ with $\gcd(x,y)=1$, the "digit-splice" set $M+yS:=\{m+ys\bmod xy:m\in M',s\in S'\}\subseteq\mathbb Z_{xy}$ is $B_2[gf]$: $C(gf,xy)\ge C(g,x)C(f,y)$. Kolountzakis's original special case ($g=f=2$, $S=$ a Sidon set, $M=\{0,1\}$): $S\cup(S+1)$ is always $B_2[4]$ — interleaving two shifted copies of a Sidon set doubles density while only quadrupling the collision cap, the cheapest possible density boost. This is a genuinely reusable *tensor/product* device: any two known $B_2[g]$ and $B_2[f]$ constructions combine into a $B_2[gf]$ construction on the product modulus, for free. - Resulting asymptotic constant $\sigma(g)$: explicit numeric lower bounds proved for $g=4,\dots,22$ (Theorem 3, e.g. $\sigma(4)\ge\sqrt{8/7}>1.069$, $\sigma(20)\ge\sqrt{40/33}>1.100$) and a general-$g$ formula (Theorem 4) giving $\liminf_{g\to\infty}\sigma(g)\ge11/\sqrt{96}\approx1.123$; separately Martin–O'Bryant prove $\limsup_g\sigma(g)<1.8391$ as an upper bound (companion paper, cited but not detailed in this session) — so the true limiting constant is pinned to roughly $[1.12,1.84]$, itself an open gap. - $h\ge3$ analogue: Ruiz–Trujillo, arXiv:1302.0071 (2013/2016), give three constructions of $B_h[g]$ sets as products of abelian groups, directly generalizing the $h=2$ product trick (Theorem 2(iv) above) to arbitrary $h$ — confirming the tensor/product device is not $h=2$-specific. Separately, Cilleruelo–Ruzsa–Trujillo (J. Number Theory 97 (2002), already fetched in full by B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation) give the general-$h$ finite upper bound $F_h(g,N)\le\frac1{(1+\cosh(\pi/h))^{1/h}}(h\cdot h!\cdot gN)^{1/h}$. - Existence-only (non-constructive) companion for $g\to\infty$ jointly with density $\to N^{1/2}$: unlike the finite-field constructions above (which are explicit for *fixed* $g$), reaching density exponent $g/(2g+1)\to1/2$ as $g\to\infty$ currently requires either the Erdős–Rényi 1960 probabilistic-deletion method or Pliego's 2024 refinement (arXiv:2405.04154) — see Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases) and B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation for that side of the toolbox; the finite-field toolbox on this page is the *explicit, fixed-$g$, exact-modulus* complement to those probabilistic/greedy existence results.

Technique

WHEN to reach for this toolbox: whenever a problem needs an explicit, finite set $S\subseteq[n]$ or $\subseteq\mathbb Z_n$ with a prescribed bounded (not necessarily $=1$) representation count $g$ for $h$-fold sums, and either (a) $g$ is small/fixed and you want the best known *density constant* (not just asymptotic exponent), or (b) you need an actual algebraic description (for a Lean formalization, an explicit numerical witness, or to feed into a further construction) rather than a probabilistic existence claim.

HOW to build one (recombination recipe, in order of increasing $g$/complexity)

1. Start from a Sidon set ($g=1$ base case): pick Ruzsa's, Bose's, or Singer's finite-field construction near the target modulus (Singer densest, Ruzsa simplest — see Sidon sets / B_2 sets / Golomb rulers, Finite-field / projective-plane constructions for extremal additive sets). 2. **To reach a *specific* target $g$, take a $K$-union of $|K|=\lceil\sqrt{g/2}\rceil$-ish shifted copies of the *same* base construction** (same $p,\theta$ or $q,\theta$, varying only the index $i$/$k$/$\vec k$ over a subset $K$ of the parameter space): this multiplies the set size by $|K|$ while the collision cap grows only as $|K|^2$ — a quadratic, not linear, price, because collisions *between* different copies are controlled by the *same* unique-factorization argument that made the base construction Sidon in the first place (the copies are related by the group action, so cross-copy sums still correspond to roots of a bounded-degree polynomial). 3. **To combine two *different* constructions (different $g$, different modulus), take the product/digit-splice**: $M+yS$ on $\mathbb Z_{xy}$ multiplies the collision caps ($gf$) and the set sizes multiply too — this is the move to reach for when you already have two good gadgets (e.g. a dense small-modulus $B_2[f]$ set and a large Singer $B_2[g]$ set) and want a single set on a bigger modulus without re-deriving anything algebraically. It is also the *cheapest possible* density-doubling trick in its simplest form (Kolountzakis: any Sidon set unioned with its own $+1$-shift is $B_2[4]$, no algebra needed at all). 4. For $h\ge3$: use the same product-of-groups device (Ruiz–Trujillo) rather than trying to re-derive a Singer/Bose/Ruzsa-style unique-factorization argument from scratch for each new $h$ — the finite-field base constructions generalizing Bose/Singer to $h\ge3$ (Bose–Chowla for $B_3$, see Sidon sets / B_2 sets / Golomb rulers Facts) still exist individually, but the *composition* step (going from $g=1$ base to arbitrary $g$) is the product trick, uniformly in $h$. 5. WHY the $K$-union trick works (the core mechanism): in each of Ruzsa/Bose/Singer, "does $S(k_1)\cap S(k_2)$ collide with $S(k_3)\cap S(k_4)$" reduces, via the finite-field encoding, to "does a specific low-degree polynomial (quadratic in Ruzsa/Bose, a cubic-derived quadratic in Singer) have $\ge3$ roots over $\mathbb F_q$" — and unique factorization in $\mathbb F_q[x]$ caps the root count at the polynomial's degree, giving the $\le2$ (hence $\le2|K|^2$ after summing over the $|K|^2$ pairs of indices) bound for free. This is exactly the same "geometric/algebraic axiom does the counting for you" mechanism that makes the base $g=1$ Singer construction exact (see Sidon sets / B_2 sets / Golomb rulers Technique #7) — the toolbox's generalized-$g$ machinery is a *direct algebraic descendant* of the same unique-factorization argument, not a new idea. 6. WHY the product trick works: $S*S=(\sum_i S_i)*(\sum_j S_j)=\sum_{i,j}S_i*S_j$ is a sum of $k^2$ nonnegative pieces (Cauchy-product expansion of the convolution over disjoint blocks), so the max of the sum is trivially $\le k^2\cdot\max_{i,j}\|S_i*S_j\|_\infty$ — no cancellation is needed, only that each cross-term is itself controlled (which the base construction's own unique-factorization property, or coprimality of moduli in the digit-splice case, already guarantees). 7. Upper-bound recipe alongside the constructions: when checking whether a given construction is *close to optimal*, use Theorem 1's bounds — trivial pigeonhole ($|S|^2\lesssim gn$) for a first pass, then the sharper $g=3,4$-specific double-counting/second-moment refinements (arXiv:math/0408081 §3.1) when $g$ is small and the trivial bound is too lossy; these refinements are the $B_h[g]$-toolbox analogue of the Erdős–Turán shift-counting argument for plain Sidon sets (Sidon sets / B_2 sets / Golomb rulers Technique #4). 8. WHEN this does NOT suffice: the finite-field toolbox is explicit but only economical for fixed, modest $g$ — it does not by itself solve the regime where $g=g(N)\to\infty$ must grow *jointly* with $N$ at a controlled (e.g. sub-polynomial) rate while density approaches $N^{1/2}$; that regime is the territory of the probabilistic/greedy constructions in B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation and Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases), which this page's toolbox complements but does not replace. Conversely, when a problem needs an *exact*, *checkable*, *deterministic* witness (e.g. for Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open-style additive-basis-of-$\mathbb Z_m$ questions, or a Lean formalization), prefer this page's finite-field+product toolbox over the probabilistic route.

Related

- Sidon sets / B_2 sets / Golomb rulers — the $g=1$, $h=2$ base case; this page's Ruzsa/Bose/Singer constructions are direct generalizations of that page's "construction recipe" Technique #2, and share its unique-factorization mechanism (Technique #7 there). - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — the companion page on the *density-vs-$g$ trade-off theory* (Cilleruelo–Ruzsa–Trujillo upper bounds, Erdős–Rényi/Pliego $g\to\infty$-jointly-with-$N$ constructions); this page is the *explicit finite-field construction toolbox* half of the same overall topic, complementary rather than overlapping. - Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases) — the probabilistic-deletion alternative to this page's explicit finite-field machinery, used when $g$ must grow with $N$; both are cross-referenced as "two independent construction engines" in B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue, Discrete-logarithm explicit Sidon construction (Cilleruelo) — the infinite-set ($g=1$) log/discrete-log analogue; a structurally different transport mechanism (multiplicative-to-additive, not finite-field unique factorization) for building dense infinite Sidon-type sets. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — a sibling finite-field "bounded-multiplicity coverage" construction for the closely related additive-basis-of-$\mathbb Z_m$ setting, sharing this page's lacunary/scale-splicing and finite-field-algebra flavor. - Perfect additive basis / unique representation basis ($r_A\\equiv1$) — the $g\equiv1$-everywhere (perfect, not just bounded) extreme case; Bose/Singer difference sets are cited there too as the finite-field engine behind explicit perfect-basis constructions. - Additive representation function $r_{B,h}(n)$ — $r_A(m)$, the object whose uniform boundedness by $g$ this whole toolbox exists to control. - Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — sharp $h(N)$ asymptotics for plain Sidon sets ($g=1$); the Singer/Bose/Ruzsa base constructions this page generalizes are the lower-bound engine there. - Erdős #40 — sharp density threshold for Erdős–Turán — Erdős–Turán quantitative conjecture on $g(N)\to\infty$; this page's fixed-$g$ toolbox is explicitly the *complementary, non-solving* regime flagged in Technique #8. - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $B_3$ ($h=3$) analogue (Bose–Chowla lower bound); the Ruiz–Trujillo product-of-groups generalization to $h\ge3$ (Facts) is the relevant $B_h[g]$-toolbox extension. - Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open — additive/subtractive bases of $\mathbb Z_m$; an explicit-witness application where this page's deterministic finite-field+product toolbox (rather than probabilistic existence) is the natural tool.