# .

# Additive number theory

In number theory, the specialty additive number theory studies subsets of integers and their behavior under addition. More abstractly, the field of "additive number theory" includes the study of Abelian groups and commutative semigroups with an operation of addition. Additive number theory has close ties to combinatorial number theory and the geometry of numbers. Two principal objects of study are the sumset of two subsets A and B of elements from an Abelian group G,

\( A + B = \{a+b : a \in A, b \in B\}, \)

and the h-fold sumset of A,

\( hA = \underset{h}{\underbrace{A + \cdots + A}}. \)

There are two main subdivisions listed below.

Additive number theory

The first is principally devoted to consideration of *direct problems* over (typically) the integers, that is, determining the structure of *hA* from the structure of *A*: for example, determining which elements can be represented as a sum from *hA*, where *A* is a fixed subset.^{[1]} Two classical problems of this type are the Goldbach conjecture (which is the conjecture that 2*P* contains all even numbers greater than two, where *P* is the set of primes) and Waring's problem (which asks how large must *h* be to guarantee that *hA _{k}* contains all positive integers, where

\( A_k=\{0^k,1^k,2^k,3^k,\ldots\} \)

is the set of k-th powers). Many of these problems are studied using the tools from the Hardy-Littlewood circle method and from sieve methods. For example, Vinogradov proved that every sufficiently large odd number is the sum of three primes, and so every sufficiently large even integer is the sum of four primes. Hilbert proved that, for every integer k > 1, every nonnegative integer is the sum of a bounded number of k-th powers. In general, a set A of nonnegative integers is called a basis of order h if hA contains all positive integers, and it is called an asymptotic basis if hA contains all sufficiently large integers. Much current research in this area concerns properties of general asymptotic bases of finite order. For example, a set A is called a minimal asymptotic basis of order h if A is an asymptotic basis of order h but no proper subset of A is an asymptotic basis of order h. It has been proved that minimal asymptotic bases of order h exist for all h, and that there also exist asymptotic bases of order h that contain no minimal asymptotic bases of order h. Another question to be considered is how small can the number of representations of n as a sum of h elements in an asymptotic basis can be. This is the content of the Erdős–Turán conjecture on additive bases.

Additive combinatorics

Main article: Arithmetic combinatorics

The second is principally devoted to consideration of inverse problems, often over more general groups than just the integers, that is, given some information about the sumset A+B, the aim is find information about the structure of the individual sets A and B.[2] (A more recent name sometimes associated to this sub-division is additive combinatorics.) Unlike problems related to classical bases, as described above, this sub-area often deals with finite subsets rather than infinite ones. A typical question is what is the structure of a pair of subsets whose sumset has small cardinality (in relation to |A| and |B|). In the case of the integers, the classical Freiman's theorem provides a potent partial answer to this question in terms of multi-dimensional arithmetic progressions. Another typical problem is simply to find a lower bound for |A+B| in terms of |A| and |B| (this can be view as an inverse problem with the given information for A+B being that |A+B| is sufficiently small and the structural conclusion then being that that either A or B is the empty set; such problems are often considered direct problems as well). Examples of this type include the Erdős–Heilbronn Conjecture (for a restricted sumset) and the Cauchy–Davenport Theorem. The methods used for tackling such questions draw from across the spectrum of mathematics, including combinatorics, ergodic theory, analysis, graph theory, group theory, and linear algebraic and polynomial methods.

See also

Shapley–Folkman lemma

Multiplicative number theory

References

Nathanson (1996) II:1

Nathanson (1996) II:6

Henry Mann (1976). Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley ed.). Huntington, New York: Robert E. Krieger Publishing Company. ISBN 0-88275-418-1.

Nathanson, Melvyn B. (1996). Additive Number Theory: The Classical Bases. Graduate Texts in Mathematics 164. Springer-Verlag. ISBN 0-387-94656-X. Zbl 0859.11002.

Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and the Geometry of Sumsets. Graduate Texts in Mathematics 165. Springer-Verlag. ISBN 0-387-94655-1. Zbl 0859.11003.

Tao, Terence; Vu, Van (2006). Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105. Cambridge University Press.

External links

Hazewinkel, Michiel, ed. (2001), "Additive number theory", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

Weisstein, Eric W., "Additive Number Theory", MathWorld.

1 Examples of spectral methods

1.1 A concrete, linear example

1.1.1 Algorithm

1.2 A concrete, nonlinear example

2 A relationship with the spectral element method

3 See also

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License