additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigro ...

, an additive basis is a set

S

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

s 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 In additive combinatorics, the sumset (also called the Minkowski sum) of two subsets A and B of an abelian group G (written additively) is defined to be the set of all sums of an element from A with an element from B. That is, :A + B = \. The n-fo ...

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. An asymptotic additive basis is a set

S

for which all but finitely many natural numbers can be expressed as a sum of

k

or fewer elements of

S

. For example, by

Lagrange's four-square theorem Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four. p = a_0^2 + a_1^2 + a_2^2 + a_3 ...

, the set of

square number In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals and can be written as . The u ...

s is an additive basis of order four, and more generally by the

Fermat polygonal number theorem In additive number theory, the Fermat polygonal number theorem states that every positive integer is a sum of at most -gonal numbers. That is, every positive integer can be written as the sum of three or fewer triangular numbers, and as the sum ...

the

polygonal number In mathematics, a polygonal number is a number represented as dots or pebbles arranged in the shape of a regular polygon. The dots are thought of as alphas (units). These are one type of 2-dimensional figurate numbers. Definition and examples ...

s for

k

-sided polygons form an additive basis of order

k

. Similarly, the solutions to

Waring's problem In number theory, Waring's problem asks whether each natural number ''k'' has an associated positive integer ''s'' such that every natural number is the sum of at most ''s'' natural numbers raised to the power ''k''. For example, every natural numb ...

imply that the

k

th powers are an additive basis, although their order is more than

k

. By

Vinogradov's theorem In number theory, Vinogradov's theorem is a result which implies that any sufficiently large odd integer can be written as a sum of three prime numbers. It is a weaker form of Goldbach's weak conjecture, which would imply the existence of such a r ...

, the

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...

s 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

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 In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

.) The related

Erdős–Fuchs theorem In mathematics, in the area of additive number theory, the Erdős–Fuchs theorem is a statement about the number of ways that numbers can be represented as a sum of elements of a given additive basis, stating that the average order of this number ...

states that the number of representations cannot be close to a

linear function In mathematics, the term linear function refers to two distinct but related notions: * In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For di ...

. The

Erdős–Tetali theorem In additive number theory, an area of mathematics, the Erdős–Tetali theorem is an existence theorem concerning economical additive bases of every order. More specifically, it states that for every fixed integer h \geq 2, there exists a subset o ...

states that, for every

k

, there exists an additive basis of order

k

whose number of representations of each

n

\Theta(\log n)

. A theorem of

Lev Schnirelmann Lev Genrikhovich Schnirelmann (also Shnirelman, Shnirel'man; ; 2 January 1905 – 24 September 1938) was a Soviet mathematician who worked on number theory, topology and differential geometry. Work Schnirelmann sought to prove Goldbach's conj ...

states that any sequence with positive Schnirelmann density is an additive basis. This follows from a stronger theorem of

Henry Mann Henry Berthold Mann (27 October 1905, Vienna – 1 February 2000, Tucson) was a professor of mathematics and statistics at the Ohio State University. Mann proved the Schnirelmann-Landau conjecture in number theory, and as a result earned the 19 ...

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

\varepsilon > 0

is an additive basis of order at most

\lceil 1/\varepsilon\rceil

References

{{reflist, refs= {{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 , journal =

Proceedings of the American Mathematical Society ''Proceedings of the American Mathematical Society'' is a monthly peer-reviewed scientific journal of mathematics published by the American Mathematical Society. As a requirement, all articles must be at most 15 printed pages. According to the ...

, mr = 3835513 , pages = 50–63 , series = Series B , title = When is an automatic set an additive basis? , volume = 5 , year = 2018 {{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 The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS), the Institute of Mathematics and its Applications (IMA), the Edinburgh Mathematica ...

, pages = 67–73 , title = On a problem of additive number theory , volume = 31 , year = 1956, hdl = 2027/mdp.39015095244037 , hdl-access = free {{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

k

terms , volume = 1 , year = 1990 {{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 =

, pages = 212–216 , title = On a problem of Sidon in additive number theory, and on some related problems , volume = 16 , year = 1941 {{citation , last = Mann , first = Henry B. , author-link = Henry Mann , doi = 10.2307/1968807 , issue = 3 , journal =

Annals of Mathematics The ''Annals of Mathematics'' is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study. History The journal was established as ''The Analyst'' in 1874 and with Joel E. Hendricks as t ...

, 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 Additive number theory