Additive basis

In additive number theory, an additive basis is a set $S$ of natural numbers with the property that, for some finite number $k$, every natural number can be expressed as a sum of $k$ or fewer elements of $S$. That is, the sumset of $k$ copies of $S$ consists of all natural numbers. The order or degree of an additive basis is the number $k$. When the context of additive number theory is clear, an additive basis may simply be called a basis.

The unproven Erdős–Turán conjecture on additive bases states that, for any additive basis of order $k$, the number of representations of the number $n$ as a sum of $k$ elements of the basis tends to infinity in the limit as $n$ goes to infinity. (More precisely, the number of representations has no finite supremum.) The related Erdős–Fuchs theorem states that the number of representations cannot be close to a linear function. The Erdős–Tetali theorem states that, for every $k$, there exists an additive basis of order $k$ whose number of representations of each $n$ is $\Theta (\log n)$.

A theorem of Lev Schnirelmann states that any sequence with positive Schnirelmann density is an additive basis. This follows from a stronger theorem of Henry Mann according to which the Schnirelmann density of a sum of two sequences is at least the sum of their Schnirelmann densities. Thus, any sequence of Schnirelmann density $\varepsilon >0$ is an additive basis of order at most $\lceil 1/\varepsilon \rceil$.