Loading field map
Additive number theory is the branch of number theory concerned with the behavior of sums of sets of integers. Its central objects are not individual numbers but collections of numbers, and its guiding questions ask how large a collection must be, or what structure it must have, before its sums cover all integers, all integers of a certain form, or a substantial portion of the integers. The field sits at the intersection of classical number theory, combinatorics, and harmonic analysis, and it has developed through a series of distinct but overlapping research programs that continue to coexist.
The fundamental setting is a set \(A\) of integers (or, more generally, of elements of an abelian group). The sumset \(A+B\) is the set of all sums \(a+b\) with \(a \in A\) and \(b \in B\); when \(A=B\), one writes \(2A\) for \(A+A\), and more generally \(hA\) for the \(h\)-fold sumset. The field asks three broad families of questions.
First, existence and representation: Given a set \(A\), which integers can be written as sums of elements of \(A\)? The classical example is Lagrange's four-square theorem, which states that every nonnegative integer is a sum of four squares. This is a statement about the set \(A\) of squares: the sumset \(4A\) (allowing zero) contains every nonnegative integer. More generally, one asks whether a given set \(A\) is an additive basis of order \(h\), meaning that \(hA\) contains all sufficiently large integers.
Second, density and size: How large must a set be, in a suitable sense, before its sumsets become large or universal? The additive energy of a set—the number of quadruples \(a1+a2 = a3+a4\) with all elements in \(A\)—measures how much additive structure the set possesses. A set with high additive energy behaves like an arithmetic progression, while a set with low energy behaves like a random set. The sumset size \(|A+A|\) is another basic measure: for a finite set of size \(n\), the sumset always has size at least \(2n-1\), with equality only for arithmetic progressions, and at most \(n(n+1)/2\), with equality only for sets with no additive structure at all.
Third, structure: What can be said about a set whose sumset is small, or whose additive energy is high? The answer, in broad strokes, is that such sets must be close to arithmetic progressions or to their multidimensional analogues. This structural theme runs through the entire field and connects it to Fourier analysis, geometry of numbers, and ergodic theory.
The origins of additive number theory lie in the classical problem of representing integers as sums of powers. Fermat's theorem that every integer is a sum of three triangular numbers, Lagrange's four-square theorem, and Waring's problem—posed in 1770, asking whether every positive integer is a sum of a bounded number of \(k\)-th powers—established the template. These are statements about specific sets (squares, cubes, triangular numbers) and their sumsets.
The first systematic method for attacking such problems was the circle method, developed by G. H. Hardy and John Edensor Littlewood in the 1910s and 1920s. The idea is to encode the representation function \(r(n)\), the number of ways to write \(n\) as a sum of elements of \(A\), as a Fourier coefficient of a generating function. Writing \(f(\theta) = \sum_{a \in A} e^{2\pi i a \theta}\), the number of representations of \(n\) as a sum of \(h\) elements of \(A\) is the integral of \(f(\theta)^h e^{-2\pi i n \theta}\) over the unit interval. The circle method splits this integral into major arcs (intervals around rational points with small denominator, where the integrand is large and well understood) and minor arcs (the rest, where the integrand is small and must be bounded by other means). The major arcs yield a main term, typically a product of local factors, and the minor arcs yield an error term that is small when the set \(A\) is sufficiently dense or has sufficient structure.
The circle method proved Waring's problem for all sufficiently large integers, and it remains the primary tool for questions about sums of powers. Its limitations are equally instructive: the minor arc estimates require strong bounds on exponential sums, and these become harder as the order \(h\) grows or as the set \(A\) becomes sparser. The method works best when the set \(A\) is "large" in a precise sense—for example, when it contains a positive proportion of the integers up to \(N\).
A parallel tradition, rooted in the work of the 1930s and 1940s, asks what happens for arbitrary sets, not just sets of powers. The central figure here is Paul Erdős, who with Paul Turán posed the question that became the Erdős–Turán conjecture: if a set \(A\) of positive integers has positive upper density (meaning that the proportion of integers up to \(N\) that lie in \(A\) does not tend to zero), then \(A\) must contain arbitrarily long arithmetic progressions. This conjecture was proved by Endre Szemerédi in 1975, and the proof introduced the Szemerédi regularity lemma, a structural decomposition of arbitrary graphs that has become a cornerstone of extremal combinatorics.
Szemerédi's theorem is not itself an additive statement, but it is intimately connected to additive structure: a set with no long arithmetic progressions must have zero density, and the proof proceeds by showing that any set with positive density must contain a long progression. The theorem has multiple proofs, each illuminating a different aspect of the subject. Hillel Furstenberg's 1977 proof used ergodic theory, showing that the combinatorial statement follows from a multiple recurrence theorem for measure-preserving systems. Timothy Gowers's 2001 proof used Fourier analysis and introduced higher-order Fourier analysis, a refinement of classical Fourier methods that captures not just linear phases \(e^{2\pi i a \theta}\) but quadratic and higher-degree phases. Ben Green and Terence Tao's 2008 proof combined ergodic theory with the regularity lemma.
The density increment strategy, common to several proofs, is instructive. To show that a set of positive density contains a structure, one assumes it does not, then shows that the set must have increased density on some arithmetic progression or Bohr set (a set of integers whose fractional parts lie in a small interval). Iterating, the density increases until it exceeds 1, a contradiction. This strategy reveals a deep principle: sets that avoid additive structure must be highly concentrated on structured subsets.
A central modern theme is the inverse problem: given that a set has large additive energy or small sumset, what is its structure? The simplest case is the Cauchy–Davenport theorem and its generalization, the Freiman–Ruzsa theorem. The Cauchy–Davenport theorem, proved in the 1930s, states that for subsets \(A, B\) of the cyclic group \(\mathbb{Z}/p\mathbb{Z}\) with \(p\) prime, \(|A+B| \ge \min(p, |A|+|B|-1)\). Equality holds when \(A\) and \(B\) are arithmetic progressions. The Freiman–Ruzsa theorem, proved by Gregory Freiman in the 1960s and refined by Imre Ruzsa, addresses the inverse question in the integers: if \(|A+A| \le C|A|\), then \(A\) is contained in a generalized arithmetic progression of dimension and size bounded in terms of \(C\) alone. This theorem is a structural classification: small sumset forces the set to be a large subset of a low-dimensional progression.
The modern refinement of this program is higher-order Fourier analysis, developed by Gowers, Green, Tao, and others. Classical Fourier analysis detects linear structure: a set with large Fourier coefficient at frequency \(\theta\) has a bias toward lying in a half-space defined by the linear phase \(e^{2\pi i \theta n}\). But sets that avoid arithmetic progressions of length 4 or more can have small linear Fourier coefficients while still possessing quadratic or higher structure. Gowers's work introduced Gowers uniformity norms, which measure the extent to which a function correlates with polynomial phases of degree \(d-1\). The inverse theorem for these norms, proved by Green and Tao in the case of the integers and extended by them and others to finite fields and other groups, states that a function with large \(U^d\) norm must correlate with a polynomial phase of degree \(d-1\). This theorem is the technical heart of the modern proof of Szemerédi's theorem and of many related results.
The polynomial Freiman–Ruzsa conjecture, which would give a sharp quantitative version of the Freiman–Ruzsa theorem, remains open in general, though it has been proved in several settings, including finite fields of odd characteristic. Its resolution is one of the most sought-after goals in the field.
The term additive combinatorics, coined in the 1990s, describes the fusion of the combinatorial and analytic traditions. It studies sumsets, additive energy, and related quantities for arbitrary finite sets, with an emphasis on quantitative bounds and on applications to other areas. The field's tools include the Plünnecke–Ruzsa inequalities, which bound the sizes of iterated sumsets in terms of the size of a single sumset; the Balog–Szemerédi–Gowers theorem, which shows that large additive energy implies the existence of a large subset with small sumset; and the Szemerédi–Trotter theorem from incidence geometry, which has found unexpected applications to sum-product problems.
The sum-product phenomenon, first observed by Erdős and Szemerédi in 1983, states that a finite set of real numbers cannot simultaneously have small sumset and small product set. The precise bounds are still open, but the phenomenon has been proved in many settings, including finite fields, where it has applications to the construction of expander graphs and to the distribution of powers. The sum-product problem illustrates a recurring theme: additive structure and multiplicative structure are in tension, and sets that are small under one operation must be large under the other.
Additive combinatorics has found applications far beyond number theory. It has been used to prove results in computer science, such as the construction of pseudorandom generators and the analysis of communication complexity; in group theory, where it contributes to the classification of approximate groups; and in ergodic theory, where it informs the study of multiple recurrence. The Green–Tao theorem of 2004, which states that the primes contain arbitrarily long arithmetic progressions, is a landmark application: it combines Szemerédi's theorem with a transference principle that allows one to transfer density results from the integers to sparse pseudorandom sets, and it required a deep analysis of the structure of the primes via the circle method and sieve theory.
The circle method has not been superseded; it remains an active and essential tool, particularly for problems involving sums of powers and for questions about the distribution of prime sums. Its modern form, developed by Vaughan, Heath-Brown, and others, uses major arc approximations that are more precise than the classical ones and minor arc estimates that exploit the structure of exponential sums over primes and over powers. The method has been extended to function fields (polynomials over finite fields), where the analog of the integers is the polynomial ring \(\mathbb{F}_q[t]\), and where the method often yields stronger results because the underlying geometry is simpler.
A notable modern development is the transference principle, introduced by Green and Tao, which allows one to apply density results to sparse sets that are pseudorandom in a precise sense. The principle has been used to prove Szemerédi-type theorems for the primes and for other sparse sets, and it has become a standard tool in the field.
Contemporary additive number theory is characterized by the productive interaction of its three main traditions: the analytic circle method, the combinatorial density theory, and the structural inverse theory. A typical modern result might use the circle method to establish a main term, a transference principle to handle sparsity, and higher-order Fourier analysis to control error terms. The field is also connected to model theory, where the study of sets definable in certain structures has led to new results on sumsets and progressions; to probability theory, where random sets and random sumsets are studied; and to computational complexity, where the difficulty of computing sumsets and related quantities is investigated.
Several major open problems define the frontier. The Erdős–Turán conjecture in its quantitative form—that a set with positive density contains arbitrarily long progressions with quantitative bounds on the length in terms of the density—is only partially resolved; the best bounds, due to Gowers and to Green–Tao, are far from the conjectured ones. The polynomial Freiman–Ruzsa conjecture remains open. The sum-product problem for the reals is unsolved in its full generality. And the Waring problem for arbitrary powers, though solved in the qualitative sense, has quantitative aspects—the minimal number of \(k\)-th powers needed—that are known only for small \(k\).
The field's methods have become increasingly unified. The distinction between "combinatorial" and "analytic" approaches, once sharp, has blurred: modern proofs often use both, and the structural theorems of inverse theory are now standard tools in the analytic tradition. The field's history is not a sequence of replacements but a layering of techniques, each of which remains in use and each of which has extended the range of questions that can be asked and answered.