In additive number theory, an '''additive basis''' is a set <math>S</math> of natural numbers with the property that, for some finite number <math>k</math>, every natural number can be expressed as a sum of <math>k</math> or fewer elements of <math>S</math>. That is, the sumset of <math>k</math> copies of <math>S</math> consists of all natural numbers. The ''order'' or ''degree'' of an additive basis is the number <math>k</math>. 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 <math>S</math> for which all but finitely many natural numbers can be expressed as a sum of <math>k</math> or fewer elements of <math>S</math>.{{r|bhs18}}
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 <math>k</math>-sided polygons form an additive basis of order <math>k</math>. Similarly, the solutions to Waring's problem imply that the <math>k</math>th powers are an additive basis, although their order is more than <math>k</math>. 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.{{r|bhs18}}
The unproven Erdős–Turán conjecture on additive bases states that, for any additive basis of order <math>k</math>, the number of representations of the number <math>n</math> as a sum of <math>k</math> elements of the basis tends to infinity in the limit as <math>n</math> goes to infinity. (More precisely, the number of representations has no finite supremum.){{r|et41}} The related Erdős–Fuchs theorem states that the number of representations cannot be close to a linear function.{{r|ef56}} The Erdős–Tetali theorem states that, for every <math>k</math>, there exists an additive basis of order <math>k</math> whose number of representations of each <math>n</math> is <math>\Theta(\log n)</math>.{{r|et90}}
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 <math>\varepsilon > 0</math> is an additive basis of order at most <math>\lceil 1/\varepsilon\rceil</math>.{{r|m42}}
==References== <references>
<ref name=bhs18>{{citation | last1 = Bell | first1 = Jason | last2 = Hare | first2 = Kathryn | author2-link = Kathryn E. Hare | last3 = Shallit | first3 = Jeffrey | author3-link = Jeffrey Shallit | arxiv = 1710.08353 | doi = 10.1090/bproc/37 | doi-access = free | journal = Proceedings of the American Mathematical Society | mr = 3835513 | pages = 50–63 | series = Series B | title = When is an automatic set an additive basis? | volume = 5 | year = 2018}}</ref>
<ref name=ef56>{{citation | last1 = Erdős | first1 = P. | author1-link = Paul Erdős | last2 = Fuchs | first2 = W. H. J. | author2-link = Wolfgang Heinrich Johannes Fuchs | doi = 10.1112/jlms/s1-31.1.67 | issue = 1 | journal = Journal of the London Mathematical Society | pages = 67–73 | title = On a problem of additive number theory | volume = 31 | year = 1956| hdl = 2027/mdp.39015095244037 | hdl-access = free }}</ref>
<ref name=et90>{{citation | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | last2 = Tetali | first2 = Prasad | author2-link = Prasad V. Tetali | doi = 10.1002/rsa.3240010302 | issue = 3 | journal = Random Structures & Algorithms | mr = 1099791 | pages = 245–261 | title = Representations of integers as the sum of <math>k</math> terms | volume = 1 | year = 1990}}</ref>
<ref name=et41>{{citation | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | last2 = Turán | first2 = Pál | author2-link = Pál Turán | doi = 10.1112/jlms/s1-16.4.212 | issue = 4 | journal = Journal of the London Mathematical Society | pages = 212–216 | title = On a problem of Sidon in additive number theory, and on some related problems | volume = 16 | year = 1941}}</ref>
<ref name=m42>{{citation | last = Mann | first = Henry B. | author-link = Henry Mann | doi = 10.2307/1968807 | issue = 3 | journal = Annals of Mathematics | jstor = 1968807 | mr = 0006748 | pages = 523–527 | series = Second Series | title = A proof of the fundamental theorem on the density of sums of sets of positive integers | volume = 43 | year = 1942 | zbl = 0061.07406 }}</ref>
</references>
Category:Additive number theory