Borwein–Choi–Chu (2006) — the representation function of any order-2 additive basis cannot be bounded by 7

Statement

Background (Erdős–Turán, 1941). A set $A=\{0=\delta_0<\delta_1<\delta_2<\cdots\}\subset\mathbb N$ is an additive basis of order 2 if every $n\in\mathbb N$ is a sum of two elements of $A$. Writing the generating function $s(z)=\sum_i z^{\delta_i}$, the squared series $$s^2(z) = \sum_{i\ge0} b_i z^i$$ has $b_i = \#\{(x,y)\in A\times A : x+y=i\}$, the (ordered) representation function. The Erdős–Turán conjecture (Erdős #28 — additive basis forces unbounded representations) asserts $\{b_n\}$ is always unbounded — no order-2 basis can have a uniformly bounded number of representations. It carries a \$500 prize (Erdős–Graham, *Old and New Problems and Results in Combinatorial Number Theory*, 1980, p. 48) and remains open.

The solved sub-problem (Borwein, Choi, Chu, 2006). Rather than proving unboundedness outright, fix a small integer $k$ and ask the purely finite question: *can $\{b_n\}$ be bounded above by $k$, for every $n$, for some basis $A$?* Equivalently (Theorem 1.1 of the paper): for any sequence of nonnegative integers $(a_i)$ with $f(z)=\sum a_i z^i$ and $f^2(z)=\sum b_i z^i$, if $b_i>0$ for all $i$ then $$\sup_i \{b_i\} \ge 8.$$

Answer: proved TRUE, with $k=7$. No order-2 additive basis of $\mathbb N$ can have every representation number $\le7$. The maximum representation number of *any* basis is $\ge8$. This is unconditional and fully rigorous (not a heuristic or a numerical experiment) — it is a genuine, if numerically small, unconditional lower bound directly on the 1941 conjecture's own statement, improving Grekos–Haddad–Helou–Pihko's 2003 bound of $\ge6$.

Facts

- History of the bound. Dirac (predecessor, cited via Erdős #28 — additive basis forces unbounded representations): $b_n$ cannot be *eventually constant*. Erdős (1956): constructed a basis with $b_n=\Theta(\log n)$, showing logarithmic growth is achievable (an *existence*, not *impossibility*, result — see Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$). Grekos, Haddad, Helou, Pihko (2003, *J. Number Theory* 102(2):339–352): first unconditional finite lower bound, $\limsup b_n\ge6$, via analytic/combinatorial case-analysis ("involving considerably more analysis and less computation," per Borwein–Choi–Chu's own comparison). Borwein, Choi, Chu (2006): improved $6\to8$ by a completely different, purely computational route. Still the record ~20 years later: Konstantoulas (2013, Konstantoulas (2013) — near-cofinite sumset forces representation function $>5$ infinitely often) gets only $>5$, but under a strictly *weaker* hypothesis (near-cofinite sumset, not an exact basis); no published work has pushed the exact-basis bound past 8 as of the sources checked (2012–2026). - Three equivalent restatements of the parent conjecture are given in the paper (§2, Conjectures 2.1–2.3): (i) the "original" $\delta_i$-indexed form above; (ii) allowing arbitrary nonnegative-integer coefficients $a_i$ (not just 0/1 indicators) with $b_i>0$ for *all but finitely many* $i$; (iii) the same with $b_i>0$ for *all* $i$. The paper shows (ii)$\Leftrightarrow$(iii) trivially (finitely many extra positive terms don't affect boundedness) and that the 0/1-indicator basis form is, without loss of generality, the one to attack. - The computation is enormous and exhibits parity behavior. The number of finite "candidate bases" surviving the bound-$k$ search, $|E(k)|$, is: $|E(2)|=3$, $|E(3)|=9$, $|E(4)|=404$, $|E(5)|=6{,}355$, $|E(6)|=11{,}482{,}910{,}373$ ($\approx1.1\times10^{10}$), $|E(7)|=1{,}268{,}361{,}281{,}038$ ($\approx1.27\times10^9$) — note $E(7)$ is actually *smaller* than $E(6)$, a parity effect the authors observed and attribute to how often distinct-index pairs $(j,k)$ with $j+k=i$ coincide vs. collide. The longest surviving candidate basis for $k=7$ has 41 terms and degree (largest exponent) 328. - This was a genuinely distributed, weeks-long computation. $E(6)$ took $\approx6.5$ hours on one 2.2GHz personal computer. $E(7)$ was infeasible on a single machine and was computed using Apple's XGrid distributed-computing system across 65 networked Apple G4 computers, running for about one month. The authors explicitly flag $k=8$ as out of reach of the same algorithm in reasonable time, and conjecture $|E(k)|$ grows exponentially or faster in $k$ — which is exactly why the 8-bound has not been improved by brute force since 2006 (a real, acknowledged scaling ceiling of the method itself). - The Erdős–Turán conjecture is false over $\mathbb Z$ (allowing negative $\delta_i$) — an explicit counterexample due to Nathanson (2003, *Acta Arith.* 108(1):1–8) — so the positivity of the index sequence is essential to the whole problem, a fact the paper notes explicitly (§1) to delimit the conjecture's true content. - The finite/periodic ($\mathbb Z_m$) analog of this whole question is a *separate*, fully quantitative research track ("Ruzsa's number" $R_m$; see Ruzsa's number $R_m$: every finite cyclic group has an absolutely-bounded-representation basis (Ruzsa, 1990)) — unrelated numerically (bounds like $R_m\le192$) but structurally the same "finite bounded-representation basis" object, just on a cyclic group instead of $\mathbb N$.

Solution

**The transferable idea: turn an infinite non-existence claim ("no basis stays $\le k$ forever") into a question about whether a specific, precisely-bounded, finitely-branching combinatorial search tree is finite — then settle *that* by exhaustive, distributed computer search.** This is a genuinely different technique family from the analytic/counting arguments of Grekos–Haddad–Helou–Pihko (2003); the authors are explicit that their method is "surprisingly simple though computationally very intensive," trading cleverness for brute-force scale. Four ingredients make the reduction work:

1. Truncate the infinite object and track only "locked-in" coefficients. For a partial basis $s_n(z)=\sum_{i=0}^n z^{\delta_i}$ (its first $n+1$ terms), write $s_n^2(z)=\sum_i B_i(n)z^i$. Lemma 2.4 (monotonicity/stabilization): extending the partial basis by one more term can only *increase* each coefficient, $B_i(n)\le B_i(n+1)$, and — crucially — coefficients up to index $\delta_n$ are already final: $B_i(n)=B_i(n+1)$ for $i\le\delta_n$. So the low-order representation counts of any infinite basis extending $s_n$ are *fully determined* by the finite prefix already chosen; no future extension can ever change them. This is what makes a finite check meaningful at all — it converts "property of an infinite object" into "property of a long-enough finite prefix."

2. Define the finite search space $E_n(k)$: partial bases whose already-locked coefficients stay $\le k$. $E_n(k)$ is the (finite, by construction) set of degree-$\delta_n$ partial bases $s_n(z)$ for which every locked coefficient $B_0,\ldots,B_{\delta_n}$ is positive and $\le k$. Lemma 2.6 + Corollary 2.5: every element of $E_n(k)$ is a bounded extension of a *unique* element of $E_{n-1}(k)$, with the new exponent $\gamma$ satisfying $\deg(q)<\gamma\le2\deg(q)+1$ — a hard, explicit bounded-branching-factor guarantee. Combined with an explicit degree cap (at most $n^2+2n-2$), this proves $E(k):=\bigcup_n E_n(k)$ is a well-defined, finitely-branching rooted tree at every level.

3. Reduce the infinite conjecture to tree-finiteness (Theorem 2.7). If, for some finite $n_0$, $E_{n_0}(k)=\varnothing$ (the search dies out — no partial basis can be extended any further while keeping every coefficient $\le k$), then no infinite basis with $\sup b_i\le k$ can exist at all: any such infinite basis would restrict to an infinite chain of nonempty $E_n(k)$'s, contradicting the tree's termination. This is the crux logical move — an existence question about an *infinite* object is now equivalent to a *terminate/don't-terminate* question about a completely explicit, algorithmically generable finite structure.

4. Settle tree-finiteness by exhaustive, optimized, distributed search. The tree is generated depth-first (breadth-first blows memory — a trial run showed $E_{17}(6)$ alone has $\sim200$ million nodes), with an explicit pruning rule (Lemma 3.1: once the *first zero coefficient* index $\phi$ is known for a candidate, only extensions with exponent $\gamma\le\phi$ need be tried, cutting the branching factor sharply) — a genuine, if elementary, algorithmic optimization layered on top of the pure existence argument. Running this to completion for $k=2,\ldots,7$ and finding every $E(k)$ finite (with $|E(7)|\approx1.27$ billion, requiring $\approx$ a month on 65 machines via Apple's XGrid) proves no basis can keep $b_n\le7$ forever, i.e. $\sup b_n\ge8$ for every basis.

Why this transfers. The general recipe — *(i) find a monotone "locking-in" property of finite prefixes so an infinite property becomes checkable via long-enough finite truncations, (ii) prove the resulting search space has bounded branching and a computable degree/size cap so it is genuinely finite-if-it-terminates, (iii) exploit the logical equivalence (tree terminates $\iff$ the bounded-infinite object doesn't exist), then (iv) settle termination by an optimized, and if necessary distributed, exhaustive computer search* — is a template for any Erdős-style "must some parameter exceed constant $k$" claim where a naive analytic argument caps out at a small constant. It is exactly the same shape of technique later reused for pushing GHHP's $\ge6$ to $\ge8$: swap careful human case-analysis for machine-verified exhaustive search, at the price of scalability (the method's own authors flag $k=8$ as infeasible with 2006-era hardware and their algorithm, which is precisely why the record has stood since). Anyone trying to push the bound past 8, or attacking the full $\limsup=\infty$ conjecture computationally, inherits this exact reduction as the natural starting scaffold — the open question is whether a smarter pruning rule, a better encoding of $E_n(k)$, or fundamentally different (non-tree-search) machinery is needed to escape the observed exponential-in-$k$ blowup.

Related

- Erdős #28 — additive basis forces unbounded representations — the parent \$500 open Erdős–Turán conjecture ($\limsup b_n=\infty$ for every order-2 basis) that this page's result is unconditional partial progress on; this technique caps out at a small finite constant and is not known to scale toward "unbounded." - Konstantoulas (2013) — near-cofinite sumset forces representation function $>5$ infinitely often — a 2013 result in the same numerical-lower-bound tradition, trading a stronger hypothesis (near-cofinite, not exact basis) for a weaker constant (>5 instead of ≥8); same overall research cluster, different (finite pigeonhole/density) technique. - Erdős–Tetali theorem — existence of $\\log n$-representation ('economical') additive bases of every order $h$ — the *existence* side of the same conjecture: bases with $b_n=\Theta(\log n)$ do exist (Erdős 1956, generalized by Erdős–Tetali 1990), showing the conjectured lower bound "unbounded" is realistically tight, not vacuous — a probabilistic-construction counterpart to this page's finite-search impossibility result. - Ruzsa (1990) — a basis of order 2 with representation function bounded in square mean, $\\sum_{n\\le N}\\sigma_A(n)^2=O(N)$ — a different weakening of the same 1941 question (bounded in *square mean*, not pointwise/$L^\infty$); explicitly not comparable to this page's $L^\infty$ statement. - Ruzsa's number $R_m$: every finite cyclic group has an absolutely-bounded-representation basis (Ruzsa, 1990) — the fully quantitative finite/periodic ($\mathbb Z_m$) analog of "how small can the max representation number be," a numerically separate but structurally parallel track (bounds like $R_m\le192$), under active 2023–2026 research. - Konyagin–Lev: the Erdős–Turán problem, fully resolved for infinite abelian groups — the general infinite-abelian-group analog, resolved (Konyagin–Lev) in the *opposite* direction: perfect bases exist for most such groups, isolating $\mathbb N$'s Archimedean order as the true source of the classical conjecture's difficulty. - Additive representation function $r_{B,h}(n)$ — the central object $r_{B,h}(n)$ this whole problem cluster is about, including this result's exact place in its Facts/Technique sections.