Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$

Statement

Question (S. Sidon, 1932, for $h=2$; generalized by Erdős 1956 and posed for all orders by Erdős–Tetali): For a fixed integer $h\ge 2$, does there exist a set $B\subseteq\mathbb N$ that is an additive basis of order $h$ — i.e. every (sufficiently large) $n\in\mathbb N$ can be written as a sum of $h$ elements of $B$ — whose representation function $$r_{B,h}(n) \;=\; \#\{(b_1,\dots,b_h)\in B^h : b_1+\cdots+b_h=n\}$$ grows as slowly as possible, specifically at the logarithmic rate $r_{B,h}(n)\asymp\log n$ (i.e. $r_{B,h}(n)$ bounded above and below by constant multiples of $\log n$, for all large $n$)? Such a $B$ is called an economical (or thin) basis of order $h$: it is a genuine basis (covers everything) yet uses each element as sparingly as an actual basis of that order can.

Facts

- Answer: yes, for every fixed $h\ge2$. Erdős, P.; Tetali, P., "Representations of integers as the sum of $k$ terms," *Random Structures & Algorithms* 1(3):245–261 (1990) — construct, for each $h$, a $B$ with $r_{B,h}(n)\asymp\log n$ for all sufficiently large $n$. - Why $\log n$ is the right target, not an arbitrary choice: a counting argument shows any order-$h$ basis needs $|B\cap[1,N]|\gg N^{1/h}$ (an $h$-fold sumset of a size-$m$ set has $\ll m^h$ elements, and must cover $\sim N$ values). The random construction that minimizes the number of *elements* used while still covering *every* large $n$ is exactly the additive analogue of the coupon-collector / random-graph-connectivity threshold: to hit every one of $\sim N$ target sums with positive probability under a union bound over independent-ish events, the expected number of representations of each $n$ must be $\gg\log N$ (below that, a positive fraction of $n$ would, whp, get zero representations — the same $\log n$ threshold that governs $G(n,p)$ connectivity at $p=\log n/n$). $\log n$ is thus the critical/minimal achievable order. - Predecessor case ($h=2$): Erdős, P., "Problems and results in additive number theory," *Colloque sur la Théorie des Nombres* (Bruxelles, 1955), 127–137 (1956) — first proved the $h=2$ case, resolving Sidon's 1932 question, by the same probabilistic method later generalized by Erdős–Tetali. - All known proofs are non-constructive (the underlying probability space is over infinite random subsets of $\mathbb N$): existence, not an algorithm, is what the theorem delivers. - Derandomization (partial): Kolountzakis, M. N., "An effective additive basis for the integers," *Discrete Mathematics* 145(1):307–313 (1995) — derandomizes the $h=2$ case into an explicit recursive set, computable in time polynomial in $n$ for $B\cap[1,n]$. The analogous effective/recursive construction for $h\ge3$ was left open by Kolountzakis. - Fully explicit (non-recursive-search) construction, $h=2$: Jain, V.; Pham, H. T.; Sawhney, M.; Zakharov, D., "An Explicit Economical Additive Basis" (2024), arXiv:2405.08650 — gives a closed-form order-2 economical basis (representation count $o(N^\epsilon)$ for every $\epsilon>0$), explicitly framed as answering a further constructivization question of Erdős beyond Kolountzakis's recursive result. Does not extend to $h\ge3$. - Generalization to other growth rates: Táfula, C., "An extension of the Erdős–Tetali theorem," *Random Structures & Algorithms* 55(1):173–214 (2019) — characterizes exactly which functions $f$ (subject to regularity conditions) are achievable as $r_{B,h}(n)\asymp f(n)$ for some order-$h$ basis $B$; $f=\log$ is the minimal/critical case recovering Erdős–Tetali exactly. - **What the theorem does *not* say: it is a pure existence** (upper-bound-achievability) result — it shows $\log n$-growth bases exist and that $\log n$ is essentially the best (smallest) achievable order for a basis. It says nothing about whether *every* basis of order $h$ must have representation function at least this large — that direction (is $\log n$-growth *forced*, not just *achievable*) is exactly the content of the still-open Erdős–Turán conjecture family: Erdős #28 — additive basis forces unbounded representations (does every order-2 basis with $A+A$ cofinite have $\limsup r_A(n)=\infty$?), its quantitative form Erdős #40 — sharp density threshold for Erdős–Turán, and the sharpened literal-limit form Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ (does some $A$ achieve $r_A(n)/\log n\to c\neq0$ as an actual limit — Erdős–Tetali shows $\Theta(\log n)$ *without* a limit is achievable; a genuine limit is the open refinement).

Solution

The transferable technique: tune a random inclusion-probability so the target statistic hits the log-threshold in expectation, then upgrade "right on average" to "right everywhere, simultaneously, almost surely" via a concentration inequality strong enough to survive both (a) heavy dependence between the underlying indicator events and (b) a union bound over infinitely many targets.

1. Pick the density that makes the mean exactly logarithmic. Build a random set $\omega\subseteq\mathbb N$ by including each integer $n$ independently with probability $$\Pr(n\in\omega) = C\cdot n^{1/h-1}(\log n)^{1/h}.$$ This exponent is not arbitrary: it is reverse-engineered so that the expected count of ordered $h$-tuples from $\omega$ summing to a given large $n$, $$\mathbb E[r_{\omega,h}(n)] \;=\;\sum_{\substack{n_1+\cdots+n_h=n}} \prod_{i=1}^h \Pr(n_i\in\omega),$$ comes out $\asymp \log n$ — the same computation, structurally, that sets $p=\log n/n$ as the sharp threshold for $G(n,p)$ connectivity or for random-set covering problems generally (an instance of what probabilists call the Poisson paradigm: rare, roughly-independent local events, each with probability $\sim c/n$, need $\sim\log n$ "trials" before a union bound guarantees *every* one of $\sim n$ targets is hit). 2. The mean alone is not enough — dependence is the obstacle. $r_{\omega,h}(n)$ is a sum of $\sim n^{h-1}$ indicator variables (one per ordered $h$-tuple summing to $n$), and these indicators are not independent: tuples sharing a common coordinate $n_i$ are positively correlated through that shared Bernoulli variable. A naive Chernoff bound (which needs independence, or at least a controlled martingale-difference structure) does not directly apply, and — critically — the theorem needs *simultaneous* control over infinitely many $n$ at once (an event for each $n$, with failure probabilities that must be summable for Borel–Cantelli to close the argument), not just one $n$ in isolation. 3. Concentration despite dependence: Janson's inequality / Vu's polynomial-concentration inequality. The proof controls the lower tail (the dangerous direction — a specific $n$ ending up with $r_{\omega,h}(n)=0$, breaking "basis" entirely) using Janson's inequality, the standard tool for bounding $\Pr(\text{no event in a dependent family occurs})$ when the dependency graph between the underlying Bernoulli variables is sparse/bounded — exactly the situation here, since two $h$-tuples summing to $n$ are dependent only if they share a coordinate. For the matching upper tail (and general two-sided concentration of $r_{\omega,h}(n)$, viewed as a low-degree polynomial in the independent inclusion-indicators $\{\mathbf 1[n_i\in\omega]\}$), the proof uses Vu's concentration inequality for polynomials of independent random variables with small expectation (the generalization, in this regime, of the Kim–Vu polynomial concentration machinery). Together these give, for each large $n$, a failure probability small enough that summing over all $n$ and applying Borel–Cantelli yields: almost surely, $r_{\omega,h}(n)=\Theta(\log n)$ for all sufficiently large $n$ simultaneously — not merely in expectation, and not merely for a density-one subset of $n$. 4. Clean-up. A single realization of $\omega$ satisfying step 3 already witnesses the theorem; any finitely many small exceptional $n$ (where the asymptotic regime hasn't kicked in) are patched by hand, since finitely many values never affect an $\asymp$-statement.

Why this recipe is the reusable part. The four-step shape — (i) solve for the density/parameter that makes $\mathbb E[\text{target statistic}]$ land exactly on the conjectured critical growth rate; (ii) recognize that the statistic is a sum over a large, *dependent* family of local indicator events; (iii) reach for the tool built precisely for dependent-family lower tails (Janson) and, for two-sided/higher-moment control, a polynomial-concentration inequality (Vu/Kim–Vu) rather than plain Chernoff–Hoeffding; (iv) close with Borel–Cantelli across an infinite (not single) family of targets to get an *almost-sure, uniform-in-$n$* statement instead of a per-$n$ high-probability one — is the same "Poisson paradigm" template used across random-graph threshold phenomena (connectivity, Hamiltonicity, subgraph appearance) and is exactly what this wiki's Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs page documents as the more elementary Chebyshev/Paley–Zygmund special case of the same family of arguments. It is the template flagged as load-bearing by the open problems that build on this theorem: Erdős #28 — additive basis forces unbounded representations's and Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$'s own "Related"/"Facts" sections already point to this exact construction (as "the random-greedy $B_2$-type construction" and "Erdős–Tetali probabilistic method") as the natural starting toolkit for constructing potential extremal examples or counterexamples in that harder, still-open direction — the open problems ask whether $\log n$-type regularity can be *forced* on every basis, and any attack necessarily has to first understand, and often directly reuses pieces of, the machinery that shows $\log n$-regularity is *achievable* at all.

Related

- Erdős #28 — additive basis forces unbounded representations — Erdős–Turán conjecture on additive bases (order 2): this solved theorem settles the "existence of thin bases" side that motivates conjecture (i) in #28's Facts (that $\limsup r_A(n)/\log n>0$ should hold for *every* complete basis); Erdős–Tetali shows $\log n$ is achievable, not that it is forced. - Erdős #40 — sharp density threshold for Erdős–Turán — quantitative/threshold form of Erdős–Turán; same representation-function-regularity family. - Erdős #66 — additive basis with $r_A(n)/\\log n \\to c\\neq 0$ — sharper open question (does some $A$ have $r_A(n)/\log n\to c\neq0$ as a genuine limit?) explicitly built on top of this theorem's $\Theta(\log n)$-without-a-limit construction; erdos/66.md's Facts cite "the standard random-greedy $B_2$-type construction giving $r_A(n)\asymp\log n$ almost everywhere" as the starting point whose exceptional-set removal is the open difficulty. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the more elementary variance/Paley–Zygmund special case of the same "existence via controlled second moment" family that Janson's inequality and Vu's concentration inequality generalize for dependent-event lower/upper tails. - Sidon sets / B_2 sets / Golomb rulers — the $h=2$ ancestor object (Sidon's 1932 question was the seed of this whole theorem); this wiki's Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets, Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, Erdős #241 — sharp $N^{1/3}$ asymptotics for $B_3$ sets, Erdős #329 — how large can limsup |A∩[1,N]|/N^{1/2} be for a Sidon set? are the sibling open Sidon/$B_h$-density problems in the same neighborhood.