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 ![]() |
[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 |
Additive basis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Additive_basis&oldid=18543