In additive number theory, an additive basis is a set of natural numbers with the property that, for some finite number , every natural number can be expressed as a sum of or fewer elements of . That is, the sumset of copies of consists of all natural numbers. The order or degree of an additive basis is the number . When the context of additive number theory is clear, an additive basis may simply be called a basis. An asymptotic additive basis is a set for which all but finitely many natural numbers can be expressed as a sum of or fewer elements of .
For example, by Lagrange's four-square theorem, the set of square numbers is an additive basis of order four, and more generally by the Fermat polygonal number theorem the polygonal numbers for -sided polygons form an additive basis of order . Similarly, the solutions to Waring's problem imply that the th powers are an additive basis, although their order is more than . By Vinogradov's theorem, the prime numbers are an asymptotic additive basis of order at most four, and Goldbach's conjecture would imply that their order is three.
The unproven Erdős–Turán conjecture on additive bases states that, for any additive basis of order , the number of representations of the number as a sum of elements of the basis tends to infinity in the limit as 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 , there exists an additive basis of order whose number of representations of each is .
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, unless their sum consists of all natural numbers. Thus, any sequence of Schnirelmann density is an additive basis of order at most .
- Bell, Jason; Hare, Kathryn; Shallit, Jeffrey (2018), "When is an automatic set an additive basis?", Proceedings of the American Mathematical Society, Series B, 5: 50–63, arXiv:1710.08353, doi:10.1090/bproc/37, MR 3835513
- Erdős, Paul; Turán, Pál (1941), "On a problem of Sidon in additive number theory, and on some related problems", Journal of the London Mathematical Society, 16 (4): 212–216, doi:10.1112/jlms/s1-16.4.212
- Erdős, P.; Fuchs, W. H. J. (1956), "On a problem of additive number theory", Journal of the London Mathematical Society, 31 (1): 67–73, doi:10.1112/jlms/s1-31.1.67, hdl:2027/mdp.39015095244037
- Erdős, Paul; Tetali, Prasad (1990), "Representations of integers as the sum of terms", Random Structures & Algorithms, 1 (3): 245–261, doi:10.1002/rsa.3240010302, MR 1099791
- Mann, Henry B. (1942), "A proof of the fundamental theorem on the density of sums of sets of positive integers", Annals of Mathematics, Second Series, 43 (3): 523–527, doi:10.2307/1968807, JSTOR 1968807, MR 0006748, Zbl 0061.07406