B_h sets — generalized Sidon sets of order h (distinct h-fold sums)

Statement

$B_h$ set (Sidon set of order $h$, "generalized Sidon set"): fix an integer $h\ge2$. For a set $A$ of integers (or elements of an abelian group $\Lambda$), consider the $h$-fold sumset $hA=\{a_1+\cdots+a_h:(a_1,\ldots,a_h)\in A^h\}$ and, for $w\in\Lambda$, the unordered representation function $r_{A,h}(w)=\#\{[a_1,\ldots,a_h]\in A^h/S_h : a_1+\cdots+a_h=w\}$, i.e. the number of *multisets* of $h$ elements of $A$ (not ordered tuples) summing to $w$. $A$ is a $B_h$ set if $r_{A,h}(w)\le1$ for every $w$ — every value is hit by at most one unordered $h$-tuple. $B_2$ is exactly a classical Sidon sets / B_2 sets / Golomb rulers (Sidon set). (Nathanson, arXiv:2104.12711, Section 1, verbatim definitions.)

$B_h[g]$ set (bounded, not unique, representation): relax to $r_{A,h}(w)\le g$ for all $w$; $B_h[1]=B_h$. Convention warning (genuine literature hazard, not a typo): O'Bryant's survey defines a *separate* ordered-count function $A^{*h}(k)=\#\{(a_1,\ldots,a_h)\in A^h : a_1+\cdots+a_h=k\}$ (counting ordered tuples, so a repeated-coordinate-free representation is counted $h!$ times) and calls $A$ a "$B_h[g]$ sequence" exactly when $A^{*h}\le h!\,g$ — i.e. **O'Bryant's $B_h[g]$ is defined as $B^*_h[h!g]$ in his own ordered-count notation**, which coincides with Nathanson's $r_{A,h}\le g$ only asymptotically (finitely many $h$-tuples have a repeated coordinate, so the two conventions agree up to lower-order terms, but *some* authors instead define $B_h[g]$ as $B^*_h[h!(g+1)-1]$, off by a full unit of $g$ in the small-$g$ regime — O'Bryant explicitly flags this has "not been proven to hold except for $h=2,g=1$"; arXiv:math/0407117, Section 2, Definitions 1–3 and the paragraph immediately following). Always check which convention a source uses before combining bounds across papers.

Core extremal quantity — $\sigma_h$: let $F_h(n)$ (Nathanson's notation) $=R_h(1,n)$ (O'Bryant's notation) denote the size of the largest $B_h$ subset of $\{1,\ldots,n\}$. Define $\sigma_h:=\lim_{n\to\infty}F_h(n)/n^{1/h}$ (not known to exist as a genuine limit for $h>2$; read as $\limsup$/$\liminf$ bounds otherwise). The elementary pigeonhole bound gives $F_h(n)=O(n^{1/h})$, so $0<\sigma_h<\infty$ is finite and the only question is its exact value — settled ($\sigma_2=1$) only for $h=2$. For $h\ge3$, $\sigma_h$ is open — this is exactly Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets for $h=3$, and its generalization for all $h\ge3$ (Bose–Chowla's original conjecture).

Facts

- Elementary upper bound ($F_h(n)=O(n^{1/h})$): an $h$-fold generalization of the Sidon-set pigeonhole argument — an $h$-element-subset $B_h$ set of $\{1,\ldots,n\}$ has $\binom{|A|+h-1}{h}$ distinct $h$-fold sums, all lying in $\{h,\ldots,hn\}$, forcing $|A|^h/h!\lesssim hn$, i.e. $F_h(n)\ll n^{1/h}$ (Nathanson arXiv:2104.12711, Section 2, "a simple counting argument shows that $F_h(n)\ll n^{1/h}$"). - Bose–Chowla theorem (1962/63, Comment. Math. Helv. 37, 141–147) — the matching-order finite-field lower bound, $\sigma_h\ge1$: for every $h\ge2$ and prime power $q$, let $\mathbb F_q\subset\mathbb F_{q^h}$ and let $\theta$ generate the cyclic group $\mathbb F_{q^h}^\times$ (order $q^h-1$). For each $\lambda_j\in\mathbb F_q$ there is a unique $a_j\in\{1,\ldots,q^h-2\}$ with $\theta^{a_j}=\theta-\lambda_j$; the set $A=\{a_j\}_{j=1}^q$ is a $B_h$ set modulo $q^h-1$ of size $q$ (Nathanson, Theorem 1, full proof reproduced: uniqueness of the factorization $\prod_j(t-\lambda_j)$ into linear factors over $\mathbb F_q$, forced because $\theta$'s minimal polynomial over $\mathbb F_q$ has degree exactly $h$, is the entire mechanism). Corollary: $F_h(q^h-2)\ge q$. Combined with a prime-gap input (Hoheisel 1930 / Heath-Brown 1988: primes $p,p'$ consecutive $\Rightarrow p'-p<p^\alpha$ for some $\alpha<1$), this upgrades to the clean asymptotic $\liminf_{n\to\infty}F_h(n)/n^{1/h}\ge1$ (Nathanson, Theorem 2, full proof) — i.e. $\sigma_h\ge1$ for every $h\ge2$, matching the elementary upper bound's exponent exactly, though not (for $h\ge3$) its constant. - $\sigma_2=1$ exactly (only fully solved case): Singer's 1938 projective-plane construction (a special case of Bose–Chowla with the sharper constant, see Sidon sets / B_2 sets / Golomb rulers, Singer finite-field perfect difference set construction) matches Erdős–Turán's 1941 upper bound $F_2(n)\le n^{1/2}+n^{1/4}+O(1)$ exactly in leading order. No analogous matching-constant result is known for any $h\ge3$ — this is the single biggest qualitative gap between $h=2$ and $h\ge3$ in the whole area. - Best known upper-bound constants for small $h\ge3$ (O'Bryant survey, Section 4.2, citing Green 2001 and Cilleruelo 2001): Green (*Acta Arith.* 100 (2001), 365–390, arXiv-unlisted PDF) proves $\sigma_3\le(7/2)^{1/3}<1.519$ and $\sigma_4\le7^{1/4}<1.627$, via a Fourier/additive-energy lower bound on $M(n)=\inf_{f:[n]\to\mathbb R,\sum f=n}\sum_{a+b=c+d}f(a)f(b)f(c)f(d)$ — the same technique cited in Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets. Cilleruelo (*Adv. Math.* 159 (2001), 1–17) had already given $\sigma_3\le1.576$, $\sigma_4\le1.673$ via a related but distinct cosine-sum-minimization method; Green's bound is sharper for $h=3,4$ but both papers give explicit formulas valid for all $h$ (Cilleruelo's holds for $h>75$ with separate closed forms for odd/even $h$; Green's general-$h$ bound is $\sigma_h\le\frac1{2e}\big(h+\tfrac32\log h+o_h(\log h)\big)$, derived from the observation that if $X_i$ are i.i.d. uniform on $A$ then $X_1+\cdots+X_h$ becomes approximately normal for large $h$ — a central-limit-theorem argument, structurally unlike the finite-parameter Cauchy–Schwarz chain used for fixed small $h$). - Lower-order-$h$ closed forms (Kruckeberg 1961, [14] in O'Bryant's bibliography): $\frac1h h^{1/h}\le\sigma_h\le(h\cdot h!)^{1/h}$ — both bounds are simple pigeonhole-type estimates, weaker than Bose–Chowla/Singer on the lower side and than Cilleruelo/Green on the upper side, but historically the first general-$h$ bracket and still the source of the general-$h$ lower bound $\liminf_{h\to\infty}\sigma_h\cdot(\text{normalization})$ discussion. - Odd/even-$h$ split bounds (Jia 1993, Chen 1994): for $h=2r$ even, Jia proves $F_{2r}(n)\le r^{1/2r}(r!)^{1/r}n^{1/2r}+O(n^{1/4r})$, i.e. $\sigma_h\le(h/2\cdot(\lceil h/2\rceil!)^2)^{1/h}$; for $h=2r-1$ odd, Chen proves the analogous $F_{2r-1}(n)\le((r!)^2n)^{1/(2r-1)}+O(n^{1/(4r-2)})$, i.e. $\sigma_h^h\le(\lceil h/2\rceil!)^2$. O'Bryant notes "sadly, there isn't even a conjecture as to growth of $\sigma_h$ as a function of $h$ (it may well depend on the parity of $h$)" — the odd/even case split is baked into every known general-$h$ upper-bound technique, not an artifact of one paper. - The only exactly known values are $\sigma_2(2)=\sigma_2(3)=1$ (i.e. even the $g=2,3$ relaxations of the $h=2$ case, not any $h\ge3$ value) — everything for $h\ge3$ or $g\ge4$ is bracketed between nontrivial but non-matching upper/lower bounds (O'Bryant survey, Section 4). - Infinite $B_h$ sets — Erdős's liminf-zero obstruction generalizes: exactly as for $h=2$ (see Sidon sets / B_2 sets / Golomb rulers), Stöhr strengthened an unpublished Erdős result to show every infinite Sidon set has $\liminf_n A(n)/\sqrt{n/\log n}\ne\infty$; Sheng Chen conjectures the direct $B_h$ generalization, $\liminf_{n\to\infty}A(n)(\log n/n)^{1/h}<\infty$ for every infinite $B_h$ sequence $A$ — proved by Chen himself only for even $h$ (Chen 1993/96, and Helm 1994 sharpening the log-power); the odd-$h$ case and the full extension to $B^*_h[g]$ sequences remain, per O'Bryant's survey, unresolved ("neither the results nor the conjectures have been extended to $B^*_h[g]$ sequences"). - Cilleruelo–Tesoro discrete-log construction generalizes the record infinite exponent to all $h$ (verified independently by Sidon sets / B_2 sets / Golomb rulers's own provenance chain, arXiv:1206.3087): the same log/discrete-log trick that gives Ruzsa's record $x^{\sqrt2-1+o(1)}$ infinite Sidon-set density generalizes to infinite $B_h$ sequences with density $\gg x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}$ — confirming the technique (not just the $h=2$ result) is the reusable primitive. - Every construction technique for finite Sidon sets ($h=2$) has a documented $B_h$ generalization (O'Bryant survey, Section 3): the greedy algorithm generalizes verbatim to $\mathcal G_h[g]$; Ruzsa's discrete-log construction was extended to $B_2[g^2]$ (not yet fully to general $h$); Bose's construction is literally stated for general $h$ (Bose_h(q,θ,k) := {a ∈ [q^h-1] : θ^a - kθ ∈ F_q}, a $B_h\pmod{q^h-1}$ set — this is the same object as Nathanson's Bose–Chowla Theorem 1, in O'Bryant's independent notation); Singer's construction was extended to general $h$ (Singer_h, giving a $B_h\pmod{\frac{q^{h+1}-1}{q-1}}$ set, slightly denser than Bose's $B_h$ set exactly as in the $h=2$ case); the probabilistic Erdős–Rényi construction is stated for general $h,g$ from the start.

Technique

WHEN to reach for $B_h$ sets ($h\ge3$), as distinct from plain Sidon sets: whenever a problem needs "a set with no nontrivial coincidence among sums of a fixed number $h>2$ of (not-necessarily-distinct) elements" — e.g. constructing dense sets avoiding a solution to $a_1+\cdots+a_h=a_1'+\cdots+a_h'$ except by rearrangement, or building a Sidon-type gadget for a higher-arity additive pattern than pairwise sums. This is mechanically the *same* toolkit as ordinary Sidon sets (finite-field construction for the lower bound, Fourier/energy or pigeonhole counting for the upper bound) but with the exponent $1/2\to1/h$ and, critically, no known matching constant for any $h\ge3$ — treat any $h\ge3$ instance as an *open* leading-constant problem, not a solved one, even though the leading *exponent* $1/h$ is always settled.

HOW to construct a near-optimal finite $B_h$ set (recombination recipe): 1. Pick a prime power $q\approx n^{1/h}$. 2. Form the degree-$h$ field extension $\mathbb F_{q^h}/\mathbb F_q$ and a generator $\theta$ of $\mathbb F_{q^h}^\times$. 3. For each of the $q$ elements $\lambda\in\mathbb F_q$, solve $\theta^{a_\lambda}=\theta-\lambda$ for the unique exponent $a_\lambda\in\{1,\ldots,q^h-2\}$; output $A=\{a_\lambda\}$. 4. $A$ is automatically a $B_h$ set modulo $q^h-1$, hence (reduced to integers) a genuine $B_h\subseteq\{1,\ldots,q^h-2\}$ of size $q\approx n^{1/h}$. This is a direct, non-probabilistic, algebraically-exact construction (no randomness, no Borel–Cantelli cleanup) — the uniqueness of $h$-fold-sum collisions follows purely from unique factorization of degree-$\le h-1$ polynomials over $\mathbb F_q$ having $\theta$ (whose minimal polynomial has degree exactly $h$) as a root only when the polynomial is zero. Why it works: this is the *same* algebraic-rigidity mechanism as Singer's $h=2$ construction (an incidence-structure/field-degree argument, not a counting argument) — it generalizes to any $h$ with zero change in the proof strategy, only the field-extension degree changes. This is why the *exponent* $1/h$ has never needed improvement since 1962/63, while the *constant* (which the finite-field construction does not pin down exactly for $h\ge3$, unlike $h=2$'s Singer/Erdős–Turán match) has resisted 60+ years of effort.

HOW to prove a matching or near-matching upper bound (two competing recipes, both reusable): 1. Cosine-sum / pigeonhole route (Cilleruelo 2001, Jia/Chen for odd/even $h$): bound $F_h(n)$ via an explicit minimum-of-a-dense-cosine-sum inequality or a direct counting argument on how many $h$-tuples can collide; gives closed-form bounds valid for all $h$ (not just small $h$), at the cost of a weaker constant than the Fourier route for small $h$. 2. Fourier/additive-energy route (Green 2001): lower-bound the "energy" $M(n)=\inf_f\sum_{a+b=c+d}f(a)f(b)f(c)f(d)$ over normalized weight functions, then push this through a large-spectrum/Cauchy–Schwarz chain; gives the sharpest known constants for $h=3,4$ specifically (and an asymptotic-in-$h$ bound $\sigma_h\lesssim h/2e$ via a central-limit-theorem heuristic for large $h$), but the proof is more delicate and — per Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets's own "Attack surface" analysis — has never been numerically/computer-optimized the way the analogous $h=2$ error-term chain has (Balogh–Füredi–Roy/O'Bryant/Carter–Hunter–O'Bryant/AlphaEvolve), representing a live, transplantable opportunity. 3. WHEN to use which: reach for the finite-field construction (Bose–Chowla/Singer-style) whenever you need an explicit, deterministic near-$n^{1/h}$-size witness set — no other construction beats the exponent, and it is provably optimal in leading order. Reach for the Fourier/energy route (Green) when you need the best available constant for small, fixed $h$ (3 or 4) specifically; reach for the cosine-sum/pigeonhole route (Cilleruelo, Jia, Chen) when you need a bound valid uniformly in $h$ with a closed algebraic form, e.g. for asymptotic-in-$h$ arguments. 4. The convention trap (Statement, above) is itself a reusable checklist item: before combining a $B_h[g]$-bound from one paper with a construction from another, always verify whether "$B_h[g]$" there means Nathanson's unordered $r_{A,h}\le g$, or O'Bryant's/others' ordered $A^{*h}\le h!g$ (or $h!(g+1)-1$) — silently mixing conventions introduces spurious factors of $h!$ that can make a "new record" claim wrong by a multiplicative constant. 5. Extension to linear forms beyond plain sums: Nathanson's $\varphi$-Sidon-system framework (arXiv:2104.12711, Section 3) generalizes the entire theory to *any* linear form $\varphi=c_1x_1+\cdots+c_hx_h$ (not just $x_1+\cdots+x_h$), with an $h$-tuple of sets $(A_1,\ldots,A_h)$ each required to have all $\varphi$-values distinct (up to bounded multiplicity $g$); Theorem 3–4 show the Bose–Chowla construction and its $\liminf\ge1$ asymptotic survive this generalization whenever the coefficients $c_i$ avoid a finite bad set of primes $\mathcal P(h)$ (those $p$ with $p-1\mid h$) — a directly reusable template for any "avoid a fixed linear additive relation with coefficients $c_i$" problem, not just plain equal-weight $h$-fold sums.

Related

- Sidon sets / B_2 sets / Golomb rulers — the $h=2$ parent case; carries the fully-solved leading-order asymptotics ($\sigma_2=1$, Singer+Erdős–Turán) that $B_h$, $h\ge3$, has never matched; also the discrete-log/log-trick infinite-construction engine that Cilleruelo–Tesoro generalizes to all $h$. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — the $h=2$, general-$g$ relaxation; illustrates the convention issues (Nathanson vs. O'Bryant $g$-normalization) that recur, amplified by the extra $h!$ factor, in the general-$h$ $B_h[g]$ case documented above. - Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets — the $h=3$ instance of exactly this page's open "$\sigma_h=1$?" question: Bose–Chowla's lower bound $1$ vs. Green's upper bound $(7/2)^{1/3}\approx1.5199$, unchanged since 2001; flagged there as a concrete, never-yet-attempted target for the same AlphaEvolve/numerical-optimization playbook that moved the $h=2$ error term. - erdos/840 — quasi-Sidon sets ($|A+A|=(1+o(1))\binom{|A|}2$), a *different* relaxation direction (approximate rather than order-$h$) in the same Bose–Chowla/Erdős family, also with an open leading constant. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #40 — sharp density threshold for Erdős–Turán, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — the infinite-density and representation-function-boundedness questions in the $h=2$/$h=3$ cluster that this page's "Sheng Chen conjecture" (Facts) is the direct $B_h$-general analogue of. - Erdős #1191 — how small can an infinite Sidon set's liminf density be? — the $\gamma$-Golomb-ruler generalization (O'Bryant 2026), a sibling relaxation axis (bounded-multiplicity-$\gamma$ differences rather than order-$h$ sums) using a structurally related block-energy method. - Finite-field / projective-plane constructions for extremal additive sets, Finite-field parabola/Sidon-block construction with lacunary-scale gluing, Singer finite-field perfect difference set construction — the family of finite-field/projective-geometry techniques (Bose, Singer, Bose–Chowla) that supply every known matching-exponent lower bound in this area, for both $h=2$ and general $h$. - Additive representation function $r_{B,h}(n)$ — the object $r_{A,h}(w)$ / $A^{*h}(k)$ whose boundedness defines $B_h$ and $B_h[g]$ sets; the general-$h$, general-linear-form ($\varphi$-Sidon-system) extension is due to Nathanson, arXiv:2104.12711. - Ruzsa's prime-logarithm probabilistic Sidon-set construction and its discrete-log constructive analogue, Discrete-logarithm explicit Sidon construction (Cilleruelo) — the $h=2$ log/discrete-log infinite-construction engines that Cilleruelo–Tesoro (arXiv:1206.3087) generalize to record-density infinite $B_h$ sequences for all $h\ge2$.