Additive representation function $r_{B,h}(n)$

Statement

For $B\subseteq\mathbb N_0$ (or a subset of any abelian semigroup) and a positive integer $h$, the ($h$-fold, ordered) representation function is $$r'_{B,h}(n)\;=\;\#\{(a_1,\dots,a_h)\in B^h : a_1+\cdots+a_h=n\},$$ counting ordered $h$-tuples. The unordered version, more common in the Erdős–Turán literature and written $r_{B,h}(n)$ (also $1_B^{\ast h}(n)$, an $h$-fold convolution of the indicator function), restricts to non-decreasing tuples $a_1\le\cdots\le a_h$, i.e. counts unordered multisets: $r_{B,h}(n)=|\{(a_1,\dots,a_h)\in B^h : n=a_1+\cdots+a_h,\ a_1\le\cdots\le a_h\}|$ (en.wikipedia.org/wiki/Erdős–Turán_conjecture_on_additive_bases). The two differ only by a bounded multiplicative factor (at most $h!$, exactly $h!$ off a measure-zero diagonal set), so "$r_{B,h}(n)=\Theta(f(n))$" statements are insensitive to the choice.

Additive basis of order $h$: $B$ is a basis of order $h$ if $r_{B,h}(n)>0$ for all sufficiently large $n$ (every large integer is a sum of $h$ elements of $B$); equivalently $B+\cdots+B$ ($h$ summands) is cofinite. $h=2$ is the classical case (Sidon's original setting).

Perfect basis: every $n$ has a *unique* representation (up to reordering); for order 2 this means $r_{B,2}(n)\le 2$ everywhere (the factor 2 is the swap $a+b=b+a$ in an involution-free group) — equivalently $B$ is a maximal Sidon-type basis. A Sidon set is exactly the $h=2$, $r_{B,2}(n)\le 1$-*unordered* case (see Sidon sets / B_2 sets / Golomb rulers): distinctness of all pairwise sums is definitionally $r_{B,2}\le 1$.

Erdős–Turán conjecture (Erdős #28 — additive basis forces unbounded representations, Erdős–Turán 1941): if $B\subseteq\mathbb N$ is a basis of order 2 ($B+B$ cofinite), then $\limsup_{n\to\infty} r_{B,2}(n)=\infty$ — no order-2 basis can have *uniformly bounded* representation counts. Open since 1941.

Facts

- Trivial averaging identity (pigeonhole engine). Summing over a range, $\sum_{n\le N} r_{B,h}(n) \asymp |B\cap[1,N]|^h/h!$ (each $h$-subset of $B\cap[1,N]$ contributes to exactly one $n\le hN$; unordered form divides by $h!$). This one identity runs in both directions and is the single most reusable fact about representation functions: (a) if $r_{B,h}$ is bounded above by $M$ on a basis's covering range, density is forced upward, $|B\cap[1,N]|\gg N^{1/h}$ (en.wikipedia.org/wiki/Erdős–Turán_conjecture_on_additive_bases, "Lower Bound" fact) — this is why an order-$h$ basis can never be arbitrarily sparse; (b) conversely, if density is known to be $\gg N^{1/h}\cdot g(N)$ with $g\to\infty$, the identity forces $\limsup r_{B,h}(n)=\infty$ by pigeonhole (the "easy direction" of Erdős–Turán-type problems, e.g. flagged explicitly in wiki/problems/40.md as the trivial dense-side bound bracketing the open sub-polynomial regime). - Dirac's theorem (predecessor result, cited via wiki/problems/28.md's Wikipedia-sourced Facts): the representation function of a basis cannot be *eventually constant* — a first, easy rigidity constraint on $r_B$, historically the starting point before Erdős–Turán's stronger unboundedness conjecture. - Existence side is fully settled (thin/"economical" bases exist): Erdős 1956 constructs, for $h=2$, a basis with $c_1\log n\le r_B(n)\le c_2\log n$ — logarithmic growth is achievable and (matching the pigeonhole lower bound machinery) essentially optimal. Erdős–Tetali theorem (1990, *Random Structures & Algorithms* 1(3):245–261) extends this to every order $h\ge2$: a random set $\omega$ with $\Pr(n\in\omega)=Cn^{1/h-1}(\log n)^{1/h}$ gives $r_{\omega,h}(n)\asymp\log n$ almost surely, via Janson's inequality (lower-tail concentration for dependent events) plus Vu's polynomial-concentration inequality (two-sided). Táfula 2019 (*Random Structures & Algorithms* 55(1):173–214, arXiv:1807.10200) characterizes exactly which growth functions $f$ are achievable as $r_{B,h}(n)\asymp f(n)$ for some order-$h$ basis, with $\log n$ the minimal/critical case. See erdos/erdos-tetali-economical-bases. This existence machinery shows $\log n$-*regularity is achievable*; it does not show it is *forced* — that gap is exactly what the open Erdős–Turán-family problems ask. - Erdős–Fuchs theorem (Erdős–Fuchs 1956, *J. London Math. Soc.* 31:67–73, building on Hardy 1915's work on sums of two squares): the *accumulated* representation function $s_{A,2}(N)=\sum_{n\le N}r_{A,2}(n)$ can never satisfy $s_{A,2}(N)=cN+o(N^{1/4}\log(N)^{-1/2})$ for any $c>0$ — i.e. a set's cumulative representation count can never track a perfectly linear (smooth, "average-case ideal") function too closely; oscillation of size at least $N^{1/4}$-ish is unavoidable. Refined by Sárközy (1980, extension to $k$ near sequences, error form $o(n^{1/4}\log(n)^{1-3k/4})$), Montgomery–Vaughan (1990, $\max_{N\le M}|\sum_{n\le N}r(n)-cn|=\Omega(M^{1/4}\log^{-1/4}M)$), and a Jurkat result (via Hayashi's thesis) removing the log factor entirely, $\Omega(N^{1/4})$ — near matched by Ruzsa's 1997 converse construction achieving $O(N^{1/4}\log N)$, pinning the true exponent at $1/4$ up to log factors. Extended to ordered representation functions $r_k^{\le}, r_k^{<}$ (arXiv:1911.12313, *Ramanujan J.* 2020): same $o(N^{1/4}\log^{-1/2}N)$-impossibility and a mean-squared-error form $\limsup E^\star_{k,c}(A,n)>0$. - Direct unconditional (if numerically weak) partial progress on Erdős–Turán itself: Borwein, Choi, Chu (2006, *Math. Comp.* 75(253):475–484) proved every order-2 basis must have $r_{B,2}(n)>7$ for infinitely many $n$ — a genuine, if small, unconditional lower bound on $\limsup$, via a computer-assisted finite-search-tree argument (see Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7). Konstantoulas (2013, *Acta Arith.* 159:301–313) sharpened the *hypothesis*: if the upper density of $\mathbb N\setminus(B+B)$ is $<1/10$ (near-, not literally, cofinite), then $r_{B,2}(n)>5$ infinitely often — the closest published quantitative result to the conjecture's actual hypothesis. Neither technique (finite pigeonhole/counting) is known to scale toward "unbounded." See Erdős #28 — additive basis forces unbounded representations Facts for the full chain. - The finite/periodic analog is fully quantitative ("Ruzsa's number" $R_m$: least $r$ with $\exists A\subseteq\mathbb Z_m$, $1\le\sigma_A(n)\le r$ for all $n\in\mathbb Z_m$): Chen 2008 ($R_m\le288$) → Ding–Zhao arXiv:2307.12311 (2023/24, $R_m\le192$) → Ding et al. arXiv:2606.11069 (Jun 2026, step bound $|R_{m+1}-R_m|\le144$, exact tables to $m\le100$); lower bound $R_m\ge6$ for $m\ge36$ (Sándor–Yang arXiv:1705.03316). Every *finite* truncation has a small bounded-representation basis — isolating the Erdős–Turán difficulty specifically to the infinite/cofinite limit, not to finiteness. - The infinite-abelian-group analog is fully resolved, in the opposite direction: Konyagin–Lev (arXiv:0901.1649) show that for an infinite abelian group $G$ with $|2G|=|G|$, a perfect basis ($r\equiv1$ generically) exists unless $G$ is a direct sum of an exponent-3 group and the order-2 group. Most infinite abelian groups have *no* Erdős–Turán obstruction — the specific Archimedean order structure of $\mathbb N$, not "infiniteness" per se, is what makes the conjecture hard. See erdos/erdos-turan-conjecture-infinite-groups. - Inverse problem — representation functions alone are unconstrained (Nathanson, arXiv:math/0302091, "Every function is the representation function of an additive basis for the integers"): for *any* target $f:\mathbb Z\to\mathbb N_0\cup\{\infty\}$ with only finitely many zeros, there exists a set $A$ with $r_{A,h}\equiv f$, and $A$ can be made arbitrarily sparse (fewer than any prescribed fast-growing $\varphi(x)$ elements in $[-x,x]$). This is a sharp contrast with the Erdős–Turán setting: a target function is realizable *by itself* with no density cost, so the actual difficulty in Erdős #28 — additive basis forces unbounded representations/Erdős #40 — sharp density threshold for Erdős–Turán-type problems comes strictly from the conjunction of two simultaneous constraints — $B+B$ cofinite (a *global covering* condition) and $r_B$ bounded (a *local sparsity/collision* condition) — never from either condition alone. - Additive-energy identity (standard; Tao–Vu, *Additive Combinatorics*; cross-checked via B. Green's lecture notes, Ch. 4 "Additive Energy and Balog–Szemerédi–Gowers"): the *difference*-form representation function $r_{A-A}(t)=\#\{(a,b)\in A^2:a-b=t\}$ satisfies $\sum_t r_{A-A}(t)=|A|^2$ and the additive energy $E(A):=\sum_t r_{A-A}(t)^2 = |\{(a,b,c,d)\in A^4:a-b=c-d\}|$. Cauchy–Schwarz on the first identity gives $E(A)\ge |A|^4/|A-A|$ (equivalently for sumsets, $E(A)\ge|A|^4/|A+A|$) — the representation function's second moment is the exact bridge between "how collision-heavy is $A$" (energy) and "how large is the sumset/difference-set" (Freiman/Plünnecke–Ruzsa territory); a small sumset forces large energy, and Balog–Szemerédi–Gowers partially converts the reverse implication.

Technique

How $r_{B,h}(n)$ is used as a proof tool, not just studied as an object (recombination-ready steps):

1. Density-from-boundedness (pigeonhole averaging, direction (a) above): whenever a problem gives you "$B$ is a basis of order $h$" (covers everything) plus "$r_{B,h}$ bounded by $M$," immediately apply $\sum_{n\le N}r_{B,h}(n)\asymp|B\cap[1,N]|^h/h!$ against the trivial bound $\sum_{n\le N}r_{B,h}(n)\ge cN$ (coverage) to force $|B\cap[1,N]|\gg (N/M)^{1/h}$. This is the mechanical first move in nearly every Erdős–Turán-family problem and needs no cleverness — it is the "floor" every other technique in this cluster builds on top of. 2. Unboundedness-from-density (pigeonhole, direction (b)): the converse move — given density $|B\cap[1,N]|\gg N^{1/h}g(N)$ with $g\to\infty$, the same identity forces $\limsup r_{B,h}(n)=\infty$ trivially. This is the *easy* direction that brackets open problems like Erdős #40 — sharp density threshold for Erdős–Turán (its actual content is the sub-polynomial gap between "trivially true" density $N^{1/h}g(N)$, $g\to\infty$, and "known false" density $N^{1/h+\epsilon}$). 3. Constructing thin/economical bases (existence side): to build a basis with *prescribed slow* representation growth $f(n)$ (e.g. $\log n$), use the Erdős–Tetali recipe: (i) pick a random-inclusion probability $p(n)$ solving $\mathbb E[r_{\omega,h}(n)]\asymp f(n)$ for the target $n$; (ii) concentrate the resulting dependent-indicator sum via Janson's inequality (lower tail) and a polynomial concentration inequality (Kim–Vu / Vu, two-sided) rather than plain Chernoff, since representation-count indicators are heavily dependent; (iii) close with Borel–Cantelli across all $n$ simultaneously to get an almost-sure, uniform-in-$n$ statement rather than a per-$n$ high-probability one. This exact four-step "Poisson paradigm" shape is the reusable engine behind every thin-basis existence result in this cluster (Erdős 1956, Erdős–Tetali 1990, Táfula 2019) and is the natural starting toolkit even for *attacking* the still-open direction (constructing potential Erdős–Turán counterexamples), per wiki/problems/erdos-tetali-economical-bases.md's own Technique section. 4. Ruling out smooth/linear-average representation counts (Erdős–Fuchs–type negative results): to show a set's *cumulative* representation function cannot be too close to a target linear function $cN$, use the generating-function/Fourier route: form $F(z)=\sum_{a\in A}z^a$ on the unit circle, relate $s_{A,2}(N)=\sum_{n\le N}r_{A,2}(n)$ to an integral/Parseval expression in $F(z)^2$, and show that an $o(N^{1/4})$-close-to-linear hypothesis would force $F$'s $L^2$ mass to be simultaneously too concentrated (near $z=1$) and too spread out (elsewhere), a contradiction. This is the canonical technique for proving "no set can have arbitrarily smooth representation counts" impossibility results, and it recurs with the *same* $N^{1/4}$-exponent across every refinement (Sárközy, Montgomery–Vaughan, Jurkat, the ordered-representation-function extension) — a strong signal the exponent is architectural, not an artifact of one proof. 5. Small-constant unconditional lower bounds via finite pigeonhole (Borwein–Choi–Chu / Konstantoulas style): when a full "$\limsup=\infty$" statement is out of reach, a weaker but fully rigorous move is a finite counting/case-analysis argument bounding $\max_n r_{B,2}(n)$ below by a small absolute constant (7, then 5 under a relaxed near-cofinite hypothesis) — useful as a partial-progress template when the asymptotic machinery (2,3,4) doesn't close the gap, though historically these constants have not scaled to "unbounded" and a genuinely new idea is believed necessary for the full conjecture. 6. Reducing structural difficulty to the group/order-type, not "infiniteness": when stuck on an $\mathbb N$-specific representation-function problem, check the group-theoretic analog (does the same statement hold/fail for general infinite abelian $G$?) — Konyagin–Lev's resolution (opposite direction!) is direct evidence that the true obstruction is $\mathbb N$'s Archimedean order, not cardinality; this reframes "why is this hard" and can suggest which finite/periodic sub-cases (Ruzsa-number-style, $\mathbb Z_m$) are worth computing as calibration. 7. Additive-energy bridge to sumset-size bounds: when a representation-function question can be recast as bounding $E(A)=\sum_t r_{A-A}(t)^2$, reach for Cauchy–Schwarz ($E(A)\ge|A|^4/|A\pm A|$) to move between "collision-heaviness" and "sumset/difference-set size," and Balog–Szemerédi–Gowers to partially invert (large energy $\Rightarrow$ a large structured subset with small sumset) — this connects representation-function problems to the broader Freiman/Plünnecke–Ruzsa inverse-sumset toolkit. 8. WHEN this technique applies: any problem of the shape "a set $B$ covers (a positive-density subset of / cofinitely / entirely) an abelian (semi)group via $h$-fold sums — how large/small/bounded/unique must its representation counts be?" is a representation-function problem. It naturally decomposes into (i) an *existence* half (can a basis be built with prescribed slow growth? — probabilistic/Janson machinery, item 3), (ii) a *forcing* half (must every basis satisfying some density/covering hypothesis have large/unbounded representation counts? — pigeonhole averaging plus, for the hardest cases, still-missing techniques; Erdős–Turán-family problems live entirely in this unresolved half), and (iii) a *smoothness* half (can cumulative counts track a nice target function? — Erdős–Fuchs Fourier machinery, item 4). Recognizing *which* half a given open problem sits in tells you which of items 1–7 to reach for first.

Related

- Erdős #28 — additive basis forces unbounded representations — the central Erdős–Turán conjecture: order-2 basis + cofinite sumset $\Rightarrow\limsup r_{B,2}(n)=\infty$; open since 1941; carries the fullest partial-progress chain (Borwein–Choi–Chu, Konstantoulas, Konyagin–Lev, Ruzsa numbers). - Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7 — full writeup of item 5's Borwein–Choi–Chu 2006 result and its finite-search-tree technique in detail. - Erdős #40 — sharp density threshold for Erdős–Turán — quantitative/threshold sharpening: for which $g(N)\to\infty$ does density $\gg N^{1/2}/g(N)$ already force unboundedness? Open; sub-polynomial regime is the genuine gap. - Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ — sharper form asking whether $r_A(n)/\log n\to c\ne0$ as a genuine *limit* (not just $\Theta(\log n)$), built directly on the Erdős–Tetali construction. - Erdős #749 — upper-density variant solved (Bhalla 2026): bounded representation with sumset density → 1; lower-density case (adjacent to #28) still open — density-relaxed stepping-stone to #28; upper-density case resolved (Bhalla + GPT-5.4 Thinking, Apr 2026); lower-density case (closer to #28) open, active as of Jun 2026. - Erdős #1145 — two-set a_n/b_n→1 additive-basis generalization is OPEN; its own necessity clause is settled by Erdős #331 (Ruzsa's digit-parity construction, DISPROVED) — two-sequence generalization, $A,B$ with $a_n/b_n\to1$, $A+B$ cofinite $\Rightarrow\limsup r_{A,B}(n)=\infty$? Also open. - erdos/erdos-tetali-economical-bases — solved: existence of $\log n$-representation bases for every order $h$; the item-3 construction recipe in full. - erdos/erdos-turan-conjecture-infinite-groups — the group-theoretic analog, resolved in the *opposite* direction (perfect bases exist generically); isolates $\mathbb N$'s Archimedean structure as the true source of difficulty. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$, $r_{B,2}\le1$ (unordered) extremal special case; shares the pigeonhole-averaging and second-moment/energy machinery. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the Chebyshev/Paley–Zygmund special case of the Janson/Vu concentration machinery used in the Erdős–Tetali existence construction (item 3). - Block-decomposition + weighted Cauchy–Schwarz energy method (Erdős–Stöhr–Halberstam–Roth–O'Bryant) — sibling block-decomposition + weighted Cauchy–Schwarz technique, same "bound an energy two ways" architecture as item 7's additive-energy bridge, applied to Sidon-set extremal constants. - B_2[g] sequences — bounded (but not unique) representation, the Sidon relaxation — the bounded-but-not-1 ($B_2[g]$) relaxation of representation-function boundedness; Kolountzakis/Cilleruelo–Trujillo/Pliego density-vs-boundedness trade-off, directly adjacent to Erdős #40 — sharp density threshold for Erdős–Turán. - Erdős–Rényi random-subset-plus-deletion construction (power-law random sets for additive bases) — the 1960 probabilistic-deletion method giving bounded-representation sets of density $N^{1/2-\epsilon}$ for every $\epsilon>0$, ruling out every polynomial threshold function in #40.