# Additive basis

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Additive_basis
> Markdown URL: https://mediated.wiki/source/Additive_basis.md
> Source: https://en.wikipedia.org/wiki/Additive_basis
> Source revision: 1329524030
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [additive number theory](/source/additive_number_theory), an '''additive basis''' is a set <math>S</math> of [natural number](/source/natural_number)s 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](/source/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](/source/Lagrange's_four-square_theorem), the set of [square number](/source/square_number)s is an additive basis of order four, and more generally by the [Fermat polygonal number theorem](/source/Fermat_polygonal_number_theorem) the [polygonal number](/source/polygonal_number)s for <math>k</math>-sided polygons form an additive basis of order <math>k</math>. Similarly, the solutions to [Waring's problem](/source/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](/source/Vinogradov's_theorem), the [prime number](/source/prime_number)s are an asymptotic additive basis of order at most four, and [Goldbach's conjecture](/source/Goldbach's_conjecture) would imply that their order is three.{{r|bhs18}}

The unproven [Erdős–Turán conjecture on additive bases](/source/Erd%C5%91s%E2%80%93Tur%C3%A1n_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](/source/supremum).){{r|et41}} The related [Erdős–Fuchs theorem](/source/Erd%C5%91s%E2%80%93Fuchs_theorem) states that the number of representations cannot be close to a [linear function](/source/linear_function).{{r|ef56}} The [Erdős–Tetali theorem](/source/Erd%C5%91s%E2%80%93Tetali_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](/source/Lev_Schnirelmann) states that any sequence with positive [Schnirelmann density](/source/Schnirelmann_density) is an additive basis. This follows from a stronger theorem of [Henry Mann](/source/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](/source/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](/source/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](/source/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](/source/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

---
Adapted from the Wikipedia article [Additive basis](https://en.wikipedia.org/wiki/Additive_basis) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Additive_basis?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.