Additive basis

for the natural numbers

A set $B$ of non-negative integers is called an additive basis of order $h$ if every non-negative integer may be written in at least one way as a sum $b_1+\dots+b_h$, with all $b_i\in B$. One is usually only interested to represent in such a way all sufficiently large positive integers and speaks then of an asymptotic additive basis. For example, the set of squares is an asymptotic additive basis of order $4$ (Lagrange's theorem). Most of the results about asymptotic additive bases deal with the existence of "thin" bases, for various meanings of the word thin.

For a given set $B\subseteq\mathbf N$ one writes $r_{B,h}(x)$ for the number of representations of the non-negative integer $x$ as a sum of $h$ terms from $B$, the order of addition being insignificant. A well-known theorem of P. Erdős [a1] claims that there is an asymptotic basis $B$ with

$$C_1\log x\leq r_{B,2}(x)\leq C_2\log x,\label{a1}\tag{a1}$$

when $x$ is sufficiently large. It is an open problem (as of 2000) if one can have a basis with $r_{B,2}(x)=o(\log x)$. The famous Erdős–Turán conjecture states that, for any asymptotic basis $B$ of order $2$, the sequence $r_{B,2}(x)$, $x\in\mathbf N$, cannot be bounded.

Erdős' construction is probabilistic. He shows that if one takes the integer $x$ to be in $B$ with probability $K(\log(x)/x)^{1/2}$, for a sufficiently large positive constant $K$, then with probability $1$ the set $B$ is an asymptotic basis satisfying \eqref{a1} for suitable constants $C_1$ and $C_2$, for all but finitely many positive integers $x$. See also [a5] for a modified probabilistic construction which can be derandomized to yield a polynomial-time algorithm for the determination of such a basis up to any desired integer $n$.

Erdős' result was subsequently extended [a2] to bases of order $h>2$, where the obstacle of having the random variables $r_{B,h}(x)$ no more independent for different $x$ was removed with the help of Janson's inequality [a3]. Janson's inequality has also been used by J. Spencer [a6] to prove that one may take a small subset $A$ of the squares, of size $|A\cap[1,x]|\leq Cx^{1/4}\log x$ which is still an asymptotic additive basis of order $4$.

Another measure for a basis being small is that of minimality. An asymptotic additive basis of order $h$ is called minimal if it has no proper subset that is an asymptotic additive basis of the same order. Such bases are known to exist for all $h$. For example, in [a4] it is proved that for every $h$ and every $\alpha<1/h$ there exists a minimal asymptotic basis of order $h$ and with counting function of the order $x^\alpha$.

References

[a1]	P. Erdős, "Problems and results in additive number theory" , Colloque sur la Theorié des Nombres (CBRM, Bruxelles) , G. Thone (1955) pp. 255–259
[a2]	P. Erdős, P. Tetali, "Representations of integers as the sum of $k$ terms" Random Struct. Algor. , 1 : 3 (1990) pp. 245–261
[a3]	S. Janson, "Poisson approximation for large deviations" Random Struct. Algor. , 1 : 2 (1990) pp. 221–229
[a4]	X.-D. Jia, M.B. Nathanson, "A simple construction for minimal asymptotic bases" Acta Arith. , 52 : 2 (1989) pp. 95–101
[a5]	M. Kolountzakis, "An effective additive basis for the integers" Discr. Math. , 145 (1995) pp. 1–3; 307–313
[a6]	J. Spencer, "Four squares with few squares" , Number Theory (New York, 1991-1995) , Springer (1996) pp. 295–297