B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation

Statement

Definition. A set $A\subseteq\mathbb N$ (or of an abelian group) is a $B_2[g]$ sequence if every integer $m$ has at most $g$ representations of the shape $m=b_1+b_2$ with $b_1\le b_2\in A$ — equivalently, the representation function $$r_A(m)=\#\{(b_1,b_2)\in A^2: b_1\le b_2,\ b_1+b_2=m\}$$ satisfies $r_A(m)\le g$ for every $m$ (arXiv:2405.04154, abstract, verbatim definition). $B_2[1]$ is exactly a Sidon set (Sidon sets / B_2 sets / Golomb rulers): $g$ is the "slack" parameter that relaxes uniqueness of representation to bounded multiplicity. The general $B_h[g]$ version bounds $h$-fold sum representations by $g$ (Sidon = $B_2[1]$; see Sidon sets / B_2 sets / Golomb rulers for the $B_h$, $h\ge3$ sibling family).

The central trade-off this concept exists to quantify: relaxing $g=1\to g>1$ buys strictly higher achievable density (up to the ceiling $N^{1/2}$, and even the exact constant $\limsup=1$), in exchange for tolerating boundedly-many (not zero) additive collisions. This is the precise combinatorial content of the Erdős–Turán conjecture Erdős #28 — additive basis forces unbounded representations and its quantitative sharpening Erdős #40 — sharp density threshold for Erdős–Turán: is there any way to let $g\to\infty$ (however slowly) while pushing density all the way up to $N^{1/2}/o(1)$? The known constructions below all answer "yes, but only for a fixed $g$," never for $g\to\infty$ jointly with density $\to N^{1/2}$.

Facts

- Finite extremal bound (Cilleruelo–Ruzsa–Trujillo, J. Number Theory 97 (2002), 26–34). Let $F_2(g,N)$ be the largest size of a $B_2[g]$ subset of $\{1,\dots,N\}$. They prove the non-trivial upper bound $F_2(g,N)\le1.864(gN)^{1/2}+1$ (and, for the $h$-fold generalization, $F_h(g,N)\le\frac{1}{(1+\cosh(\pi/h))^{1/h}}(h\cdot h!\cdot gN)^{1/h}$ for $h>2$) — the first upper bound for $F_h(g,N)$ nontrivial for infinitely many $g$. They also give an explicit lower-bound construction: a $B_2[g]$ subset of $\{1,\dots,N\}$ of size $\frac{g+\lfloor g/2\rfloor}{g+2\lfloor g/2\rfloor}N^{1/2}+o(N^{1/2})$ — so both directions are $\Theta(\sqrt{gN})$ in $N$, with $g$ entering the leading constant, not the exponent, at *fixed finite* $g$. - Erdős–Rényi 1960 (probabilistic method, Acta Arith. 6, 83–110) — the founding result: for every $\epsilon>0$ there exists $g=g(\epsilon)$ (growing as $\epsilon\to0$) and a $B_2[g]$ sequence $A$ with $|A\cap[1,x]|\gg_\epsilon x^{1/2-\epsilon}$. Proved via random deletion: take a random subset of $\{1,\dots,N\}$ at density $\sim N^{-1/2+\epsilon}$ per residue class, then delete one element from every collision that would push some $r_A(m)$ above $g$; a second-moment/Borel–Cantelli argument shows only a vanishing fraction needs deleting. This is the historical origin of "trade $g\to\infty$ for exponent $\to1/2$" and is the *existence*-only (non-constructive) end of the technique. Vu later generalized this to all $h\ge2$ (for every $h,\epsilon$ there is $g=g_h(\epsilon)$ and a $B_h[g]$ sequence of density $\gg x^{1/h-\epsilon}$), per WebSearch summary of arXiv:0911.2870. - Cilleruelo's explicit/deterministic greedy construction (arXiv:1601.00928) gives the *constructive* counterpart: a greedy algorithm builds an infinite $B_h[g]$ sequence with $n$-th term $a_n\le 2gn^{h+(h-1)/g}$, i.e. $|A\cap[1,x]|\gg (x/2g)^{1/(h+(h-1)/g)}$ — for $h=2$ this is $|A\cap[1,x]|\gg x^{1/(2+1/g)}=x^{g/(2g+1)}$, matching the exponent later reproven by Pliego (below) but via a completely different, deterministic route (greedy selection, not random deletion + Fourier/large-deviation cleanup). - Pliego 2024 (arXiv:2405.04154, "On the Erdős–Turán Conjecture and the growth of $B_2[g]$ sequences") — the current sharpest quantitative record cited by this wiki's own Erdős #40 — sharp density threshold for Erdős–Turán page: for any $0<\epsilon<1$ and integer $g>1/\epsilon$, there is a $B_2[g]$ sequence with $|A\cap[1,x]|\gg x^{g/(2g+1)}$ — note $g/(2g+1)\to1/2$ as $g\to\infty$, so this is the sharpest known way to approach the $N^{1/2}$ ceiling while paying only a *fixed* (not diverging) representation bound $g$. The paper explicitly frames this as improving on "earlier results of Cilleruelo and of Erdős and Rényi." Additionally, the construction has extra structure: nearly all large integers are representable as a sum of three elements of $A$, with the largest summand $\le n^\epsilon$ (a byproduct useful for basis-type applications). - The $\limsup=1$ ceiling is exactly attained once $g\ge2$ — a sharp qualitative jump from the strict Sidon case. Kolountzakis (Acta Arith. 77 (1996), 1–8) constructs a $B_2[2]$ sequence with $\limsup_{N\to\infty}|A\cap[1,N]|/N^{1/2}=1$ exactly (the true supremum, not just close to it); Cilleruelo–Trujillo (Israel J. Math. 126 (2001), 263–267) extend this to every $g\ge2$. Contrast with strict Sidon sets ($g=1$): the ceiling $\limsup\le1$ is only proven (Erdős–Turán 1941), never shown attained — the best known Sidon construction (Krückeberg 1961) only reaches $1/\sqrt2$, and whether $1$ is attainable for $g=1$ is the still-open Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set?. So relaxing $g=1\to g=2$ is already enough to *close* the extremal question at the top of the density range — a clean illustration of why $B_2[g]$ is the natural relaxation to reach for when a strict-Sidon question resists. - Erdős's liminf obstruction is a $g=1$-only phenomenon. Erdős proved every infinite Sidon set ($g=1$) has $\liminf_N|A\cap[1,N]|/N^{1/2}=0$ — density $\Theta(\sqrt N)$ cannot be sustained at *every* scale infinitely often. This obstruction is specific to strict uniqueness; it is exactly what the $g\ge2$ relaxation escapes (per wiki/problems/40.md, wiki/concepts/sidon-sets.md), which is *why* $B_2[g]$ constructions are the tool of choice whenever a problem needs density arbitrarily close to $N^{1/2}$ sustained everywhere, not just occasionally. - Schinzel–Schmidt conjecture on $B_2[g]$ sets is a related open extremal question (Cambridge Core listing found by WebSearch, title only: "$B_2[g]$ Sets and a Conjecture of Schinzel and Schmidt," *Combin. Probab. Comput.*) — not independently verified in detail this session, flagged here only as a pointer for further derivation, not relied upon for any claim above.

Technique

WHEN to reach for $B_2[g]$ sequences. Use this relaxation whenever a problem is phrased as "how dense can a set be while keeping its representation function *bounded* (not necessarily $\le1$)" — i.e. whenever the strict Sidon condition ($g=1$) is either (a) provably too restrictive to reach the density you need (Erdős's liminf-zero obstruction, or the finite $F_2(1,N)=(1+o(1))\sqrt N$ ceiling with no room to spare), or (b) not actually required by the downstream application, which really only needs *some* uniform cap on collisions (e.g. constructing counterexamples/near-counterexamples to Erdős–Turán-type conjectures Erdős #28 — additive basis forces unbounded representations, Erdős #40 — sharp density threshold for Erdős–Turán, or building additive bases with controlled representation-function growth).

WHY it works (the mechanism). The key insight is that the extremal exponent for $B_2[g]$ sets, at *fixed* $g$, stays pinned at $N^{1/2}$ (finite case: $F_2(g,N)=\Theta_g(\sqrt N)$, Cilleruelo–Ruzsa–Trujillo) — allowing collisions up to a fixed multiplicity does not change the leading-order density in the finite/compact setting, only the constant. The real payoff shows up in the infinite setting: Erdős's liminf obstruction is a genuinely $g=1$-specific phenomenon (a strict-uniqueness pigeonhole argument that breaks the moment $g\ge2$ gives any slack), so moving to $g\ge2$ lets a construction sustain near-$N^{1/2}$ density at every scale simultaneously, not just occasionally — this is exactly what Kolountzakis's $\limsup=1$ result exploits. Separately, letting $g\to\infty$ jointly with $N\to\infty$ (rather than fixing $g$ first) is the second, distinct lever: Pliego's and Cilleruelo's exponent $g/(2g+1)\to1/2$ shows that density can be pushed arbitrarily close to the Sidon ceiling $N^{1/2}$ by paying an ever-larger (but still $N$-independent, fixed) $g$ — this is the quantitative form of the density-vs-boundedness trade-off that the still-open Erdős #40 — sharp density threshold for Erdős–Turán asks whether can be pushed all the way to $g=g(N)\to\infty$ *slowly*, with no known construction achieving that yet.

HOW it is used to prove things (recombination steps)

1. To build a counterexample or lower-bound witness against a "bounded representation forces sparsity" type conjecture: pick a target density exponent $\alpha<1/2$, solve $g/(2g+1)>\alpha$ (Pliego) or the greedy-construction exponent $1/(2+1/g)$ (Cilleruelo) for the smallest workable integer $g$, then instantiate the corresponding construction — this is a direct recipe, not just an existence claim, for producing an explicit set with density $\gg x^\alpha$ and representation function $\le g$ everywhere. 2. Two independent construction engines, useful for cross-checking or hybridizing: (a) probabilistic (Erdős–Rényi 1960 / Vu): random subset + collision-deletion + second-moment cleanup — non-constructive but historically the first to establish any $g(\epsilon)$; (b) greedy/deterministic (Cilleruelo, arXiv:1601.00928): explicitly build $A=\{a_1,a_2,\dots\}$ by always taking the least integer not yet violating the $g$-bound — constructive, gives an explicit growth rate $a_n\le2gn^{h+(h-1)/g}$, and generalizes uniformly to all $h\ge2$. When a problem needs an *explicit* witness (e.g. for a Lean formalization or a finite-truncation numerical check), prefer the greedy route; when only *existence* is needed for a fixed $g$, the probabilistic route is often easier to adapt. 3. To close a "does the ceiling $C$ get attained" question: if the strict $g=1$ case only proves an upper bound $\limsup\le C$ without a matching construction, try the minimal relaxation $g=2$ first (Kolountzakis's exact recipe) — the qualitative jump from "not known to be attained" to "attained exactly" can occur at the very first relaxation step, before any asymptotic-in-$g$ machinery is needed. This is a cheap, high-value first move whenever a Sidon-type $\limsup$/ceiling question resists at $g=1$. 4. **Splicing at growing scales (structurally the same device used for strict Sidon sets, see Sidon sets / B_2 sets / Golomb rulers's technique #2/#3, and Finite-field parabola/Sidon-block construction with lacunary-scale gluing's Layer 3)**: both the Krückeberg-style Sidon splicing and the Cilleruelo–Trujillo $B_2[g]$ extension build the infinite sequence as a union of finite blocks placed at rapidly growing scales so that cross-block sums cannot collide with within-block sums — the $g\ge2$ slack is what lets the *within-block* piece itself be denser (closer to the $\sqrt N$ ceiling) before splicing, which is the proximate reason the spliced limsup reaches exactly $1$ for $g\ge2$ but only $1/\sqrt2$ is known for $g=1$. 5. WHEN this does NOT suffice: none of the above constructions solve the case $g=g(N)\to\infty$ jointly with $N\to\infty$ at less-than-polynomial cost (i.e. sub-polynomial correction $g(N)=N^{o(1)}$, Erdős #40 — sharp density threshold for Erdős–Turán's exact open regime) — every known result here fixes $g$ first, then lets $N\to\infty$ within that fixed-$g$ regime. Recognizing this ceiling is itself useful derivation fuel: an attempted proof strategy that only ever produces "for every $\epsilon$ there's a $g$" results (as all constructions above do) cannot, by construction, resolve Erdős #40 — sharp density threshold for Erdős–Turán or Erdős #28 — additive basis forces unbounded representations — a genuinely different mechanism (uniform-in-$g$ control) would be needed.

Related

- Sidon sets / B_2 sets / Golomb rulers — the $g=1$ parent object; $B_2[g]$ is its bounded-multiplicity relaxation, and this page's Facts/Technique sections are the direct sequel to that page's own "$B_h[g]$ relaxation" bullet. - Erdős #28 — additive basis forces unbounded representations — the Erdős–Turán conjecture (no set can have $A+A$ cofinite with $r_A$ eventually bounded); $B_2[g]$ constructions are exactly the *evidence-gathering* tool for how close one can get without resolving it. - Erdős #40 — sharp density threshold for Erdős–Turán — the quantitative sharpening (for which $g(N)\to\infty$ can density stay $\gg N^{1/2}/g(N)$); this page's constructions (Erdős–Rényi, Pliego, Cilleruelo) are cited there as the exact current state of the negative/constructive direction, and the "fixed-$g$-only" ceiling described above is precisely the open gap. - Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? — the Sidon-set $\limsup$ ceiling question; the Kolountzakis / Cilleruelo–Trujillo $B_2[g\ge2]$ results ($\limsup=1$ exactly) are cited there as strong circumstantial (but not conclusive, since $g\ge2$) evidence for the Erdős–Krückeberg conjecture that $g=1$ also reaches $1$. - Additive representation function $r_{B,h}(n)$ — $r_A(m)$, the object whose boundedness this whole family is parameterized by. - Finite-field parabola/Sidon-block construction with lacunary-scale gluing — a structurally analogous (but algebraically different) "bounded-multiplicity coverage" construction for the closely related additive-basis setting; both share the lacunary-scale-splicing device (Technique #4 above). - Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases) — the 1960 probabilistic-deletion method that is the historical origin of the $B_2[g]$ relaxation itself.