Additive basis

for the natural numbers

A set of non-negative integers is called an additive basis of order if every non-negative integer may be written in at least one way as a sum , with all . 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 (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 one writes for the number of representations of the non-negative integer as a sum of terms from , the order of addition being insignificant. A well-known theorem of P. Erdős [a1] claims that there is an asymptotic basis with

(a1)

when is sufficiently large. It is an open problem (as of 2000) if one can have a basis with . The famous Erdős–Turán conjecture states that, for any asymptotic basis of order , the sequence , , cannot be bounded.

Erdős' construction is probabilistic. He shows that if one takes the integer to be in with probability , for a sufficiently large positive constant , then with probability the set is an asymptotic basis satisfying (a1) for suitable constants and , for all but finitely many positive integers . 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 .

Erdős' result was subsequently extended [a2] to bases of order , where the obstacle of having the random variables no more independent for different 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 of the squares, of size which is still an asymptotic additive basis of order .

Another measure for a basis being small is that of minimality. An asymptotic additive basis of order 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 . For example, in [a4] it is proved that for every and every there exists a minimal asymptotic basis of order and with counting function of the order .

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 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