Additive basis

In additive number theory, an additive basis is a set S {\displaystyle S} of natural numbers with the property that, for some finite number k {\displaystyle k} , every natural number can be expressed as a sum of k {\displaystyle k} or fewer elements of S {\displaystyle S} . That is, the sumset of k {\displaystyle k} copies of S {\displaystyle S} consists of all natural numbers. The order or degree of an additive basis is the number k {\displaystyle 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 {\displaystyle S} for which all but finitely many natural numbers can be expressed as a sum of k {\displaystyle k} or fewer elements of S {\displaystyle S} .^[1]

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 k {\displaystyle k} -sided polygons form an additive basis of order k {\displaystyle k} . Similarly, the solutions to Waring's problem imply that the k {\displaystyle k} th powers are an additive basis, although their order is more than k {\displaystyle k} . 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.^[1]

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

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 ε > 0 {\displaystyle \varepsilon >0} is an additive basis of order at most ⌈ 1 / ε ⌉ {\displaystyle \lceil 1/\varepsilon \rceil } .^[5]

References