- Atlas
- Mathematics
- Additive Combinatorics
Additive Combinatorics
Additive combinatorics studies what happens when you add things up.
7 frameworks, from 1935 to today · Combinatorics · Mathematics
Overview
Additive combinatorics studies what happens when you add things up1. Take a finite set of whole numbers, or of points in a group, and ask how large its sumset is—the set of all pairwise sums you can form from it12. Sometimes the sumset is barely bigger than the original set, as with an arithmetic progression; sometimes it is much bigger, as with a set whose elements are chosen to avoid additive coincidences. The subject asks which structures force which behaviour, and what that tells us about the integers, about finite groups, and about the polynomials and exponentials that live on them. Its questions are elementary to state and often deep to answer, and its history is a story of methods borrowed from number theory, analysis, ergodic theory, and algebraic geometry being fused into a discipline of its own.
Sumsets and the arithmetic of small doubling
The oldest strand is the study of sumsets in the integers. In 1935, Lev Schnirelmann used a simple counting argument—now called the Schnirelmann density—to show that any set of integers with positive density, added to itself enough times, eventually covers all sufficiently large integers. This was a first proof that additive structure can be forced by density alone, and it fed into his work with Landau on Goldbach-type problems.
The central early result is the Cauchy–Davenport theorem, proved by Cauchy in 1813 and rediscovered by Davenport in 1935: if $A$ and $B$ are subsets of the integers modulo a prime $p$, then $|A+B| \ge \min(p, |A|+|B|-1)$. The bound is sharp, attained when $A$ and $B$ are arithmetic progressions with the same difference. In the 1950s and 1960s, the Hungarian school around Paul Erdős, Alfréd Rényi, and later Imre Ruzsa developed the "small doubling" viewpoint: a finite set $A$ in a group has small doubling if $|A+A|$ is close to $|A|$. Ruzsa's inequalities—relating $|A+B|$, $|A-A|$, and iterated sumsets—turned this into a calculus, letting one pass between different additive configurations13. The message was that sets with small doubling are "almost" structured, a theme that would dominate the field.
Sidon sets and extremal questions
A Sidon set is a set in which all pairwise sums are distinct (up to order), so that $|A+A| = \binom{|A|+1}{2}$ is as large as possible. Named after Simon Sidon, who studied them in the 1930s in connection with Fourier series, these sets are the extremal opposite of arithmetic progressions. Erdős and Pál Turán in the 1940s gave bounds on how large a Sidon set can be inside $\{1,\dots,N\}$, and the problem of pinning down the exact asymptotic—whether the maximum size is $\sqrt{N}+O(N^{1/4})$ or something else—remains open. This line of work, together with questions about sets free of three-term progressions (Roth's theorem, 1953) and about sums and differences coinciding, established extremal combinatorial number theory as a recognisable pursuit: how large can a set be before additive patterns are forced4?
Freiman's inverse theorem
The decisive structural result came from Gregory Freiman in the 1960s5. The forward direction—small doubling implies near-progression—was folklore; Freiman proved the inverse: if $|A+A| \le c|A|$ for a set of integers, then $A$ is contained in a generalised arithmetic progression (a sum of a few arithmetic progressions) of bounded size depending only on $c$. This is the inverse sumset theorem, and it reframed additive combinatorics as a classification problem: describe all sets with small doubling15. Freiman's methods were elementary but intricate, and for decades the theorem was known mainly to specialists. Its importance grew as it became clear that many problems—from Freiman's own work on sums of sets to later applications in number theory—reduce to understanding the structure of sets with small doubling.
The polynomial method
A different technique emerged from algebraic geometry. The polynomial method, developed in the 1990s and 2000s by combinatorialists including Noga Alon, uses a low-degree polynomial that vanishes on a set to bound the set's size or structure. The prototype is the Combinatorial Nullstellensatz, formulated by Alon in 1999: if a polynomial of bounded degree vanishes on a grid but not everywhere, one can extract a nonzero coefficient and derive a contradiction67. Applied to additive problems, the method gives clean proofs of results like the Cauchy–Davenport theorem and bounds on restricted sumsets (where sums $a+b$ with $a \ne b$ are counted). Its appeal is that it converts additive questions into linear algebra over polynomials, often yielding short, self-contained arguments. It became a standard tool in the extremal toolkit.
The ergodic-theoretic correspondence
In 1975, Hillel Furstenberg proved Szemerédi's theorem—that any set of positive density contains arbitrarily long arithmetic progressions—by a new route, using ergodic theory. The idea is a correspondence principle: a set of integers with positive density can be modelled by a measure-preserving dynamical system, and combinatorial statements about the set become statements about recurrence in the system. Furstenberg's multiple recurrence theorem then delivers the progressions. This was a conceptual revolution: it linked additive combinatorics to the ergodic theory of $\mathbb{Z}$-actions and opened the door to higher-order recurrence. The correspondence was later made explicit and quantitative by others, and it remains one of the deepest bridges between combinatorics and dynamics.
Sum-product phenomena
Around the same time, Erdős and Szemerédi posed the sum-product problem: for a finite set $A$ of real numbers, is $\max(|A+A|, |A\cdot A|)$ always large, roughly $|A|^{2-\epsilon}$? The intuition is that a set cannot be simultaneously additively and multiplicatively structured—arithmetic progressions have small sumsets but large products, and geometric progressions the reverse. The problem was solved in the integers by Elekes, Nathanson, and Ruzsa in the 1990s and in the reals by Solymosi and others in the 2000s, with the exponent gradually improved. The sum-product theme generalised into a broad programme: results like the Balog–Szemerédi–Gowers theorem, which says that if many sums coincide then a large subset has small doubling, became central. This theorem, proved in the 1990s, is a workhorse connecting additive structure to combinatorial incidence.
Higher-order Fourier analysis and Gowers norms
The most recent major turning point is higher-order Fourier analysis. Classical Fourier analysis decomposes a function into characters $e^{2\pi i n \theta}$ and measures correlation with linear phases8. In 1998, Tim Gowers introduced the Gowers norms, a hierarchy of norms that measure correlation with polynomial phases of degree $k$. A function with large $k$-th Gowers norm behaves like a polynomial of degree $k-1$; small norm means it is "pseudorandom" at that order. This gave a quantitative proof of Szemerédi's theorem and, more importantly, a structure theorem: any function can be decomposed into a structured part (a polynomial phase), a small part, and a pseudorandom part. The Green–Tao theorem (2004)—that the primes contain arbitrarily long arithmetic progressions—was proved using precisely this machinery, together with a transference principle moving from the primes to a dense model set. Higher-order Fourier analysis, developed by Gowers, Green, Tao, and others, is now the standard framework for additive problems in which linear Fourier analysis is insufficient.
The present
Today additive combinatorics is a mature field with several interacting strands. Classical sumset theory and Freiman inverse theory continue through the work of Tao, Green, and others on polynomial Freiman–Ruzsa conjectures and on sumsets in groups. The polynomial method remains a flexible tool, especially in finite-field settings. Ergodic correspondences and higher-order Fourier analysis are central to the study of arithmetic progressions and to the structure of dense sets. Sum-product theory has grown into a broad area touching incidence geometry and algebraic combinatorics. Open questions include the exact asymptotics for Sidon sets, the optimal exponents in sum-product estimates, the full polynomial Freiman–Ruzsa conjecture, and the extent to which higher-order structure theorems can be made effective and quantitative. The field's history is one of methods migrating from neighbouring areas—number theory, dynamics, algebraic geometry—and being reshaped into a coherent additive toolkit.
References
- Additive combinatorics (introduction, Operations on sets, Ruzsa distance), Wikipedia
- Minkowski addition, Wikipedia
- Ruzsa triangle inequality, Wikipedia
- Szemerédi's theorem (History), Wikipedia
- Freiman's theorem (introduction, History of Freiman's theorem), Wikipedia
- Polynomial method in combinatorics, Wikipedia
- Restricted sumset (Combinatorial Nullstellensatz), Wikipedia
- Gowers norm, Wikipedia
The frameworks of Additive Combinatorics
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1935-Present
- 1940-Present
Extremal Additive Combinatorics
How large can a set be before additive patterns are forced?
- 1960-Present
- 1975-Present
Ergodic-Theoretic Correspondence
How can recurrence in dynamics model arithmetic patterns?
- 1990-Present
Sum-Product Theory
Can a set be additively and multiplicatively structured at once?
- 1998-Present
Higher-Order Fourier Analysis
How can polynomial phases be measured and decomposed?
- 1999-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Freiman Inverse Theory grew out of Classical Sumset Theory and Small Doubling
Freiman's inverse sumset theorem was framed as the converse of the small-doubling observations of the 1950s–60s, classifying the sets whose sumsets are barely larger than themselves.
Carried by Gregory Freiman.
Extremal Additive Combinatorics grew out of Classical Sumset Theory and Small Doubling
Erdős and Turán's 1941 study of Sidon sets and their bounds on sumsets grew directly out of the small-doubling and sumset counting questions of the 1930s, turning them toward extremal size questions.
Carried by Paul Erdős; Pál Turán.
Polynomial Method influenced by Classical Sumset Theory and Small Doubling
Alon's Combinatorial Nullstellensatz was applied to give short proofs of Cauchy–Davenport and restricted-sumset bounds, taking the classical sumset questions as its test cases.
Carried by Noga Alon.
Ergodic-Theoretic Correspondence influenced by Extremal Additive Combinatorics
Furstenberg's correspondence principle was aimed at Szemerédi's theorem, itself a product of the extremal combinatorial number theory tradition of Roth and Erdős on sets free of arithmetic progressions.
Carried by Hillel Furstenberg.
Sum-Product Theory grew out of Extremal Additive Combinatorics
The sum-product conjecture was posed by Erdős and Szemerédi within the extremal combinatorial number theory programme, asking how large a set's sumset and product set must jointly be.
Carried by Paul Erdős; Endre Szemerédi.
Higher-Order Fourier Analysis influenced by Extremal Additive Combinatorics
Gowers norms were built to quantify the extremal question of how dense a set must be to contain long arithmetic progressions, the central concern of Roth and Szemerédi.
Carried by Timothy Gowers.
Sum-Product Theory influenced by Freiman Inverse Theory
The Balog–Szemerédi–Gowers theorem, a workhorse of sum-product theory, says that many coinciding sums force a large subset with small doubling, directly invoking Freiman's structural viewpoint.
Carried by Antal Balog; Endre Szemerédi; Timothy Gowers.
Higher-Order Fourier Analysis influenced by Ergodic-Theoretic Correspondence
Higher-order Fourier analysis grew out of Furstenberg's ergodic approach to multiple recurrence, replacing the dynamical correspondence with quantitative norms and structure theorems.
Carried by Timothy Gowers; Hillel Furstenberg.
Freiman Inverse Theory influenced by Extremal Additive Combinatorics
Freiman's work on sums of sets and on sets with few additive coincidences drew on the extremal tradition of Erdős and Turán, though the inverse theorem itself was a new structural turn.
Carried by Gregory Freiman.
Beyond the field
Where Additive Combinatorics's ideas came from in other fields, and what they led to there: the strongest 12 of 19 links.
Classical Sumset Theory and Small Doubling influenced by Additive number theory in Number Theory
Classical additive number theory, especially Waring's problem and Goldbach-type questions, supplied the central problems that sumset theory addressed. The Erdos–Szekeres and Schnirelmann work of the 1930s grew directly out of these number-theoretic questions about sums of sets of integers.
Carried by Lev Schnirelmann; Paul Erdős.
Freiman Inverse Theory influenced by Additive number theory in Number Theory
Freiman's inverse theorems grew out of additive number theory, asking when a set with small sumset must resemble an arithmetic progression. The question and its tools came from the classical study of sums of integers, which Freiman recast as an inverse problem.
Carried by Gregory Freiman.
Ergodic-Theoretic Correspondence influenced by Additive combinatorics and inverse sumset theory in Additive Number Theory
The ergodic-theoretic correspondence arose by applying ergodic theory to the recurrence and density questions of additive combinatorics and inverse sumset theory. Furstenberg's 1977 proof of Szemerédi's theorem via ergodic theory is the defining instance of this transfer.
Carried by Hillel Furstenberg.
Sum-Product Theory influenced by Additive combinatorics and inverse sumset theory in Additive Number Theory
Sum-product theory grew directly out of additive combinatorics and inverse sumset theory, using sumset and product-set bounds together. Erdős and Szemerédi's 1983 sum-product conjecture and its later proofs are the direct descendants of inverse sumset methods.
Carried by Paul Erdős; Endre Szemerédi.
Higher-Order Fourier Analysis influenced by Fourier analysis in Harmonic Analysis
Higher-order Fourier analysis generalized classical Fourier analysis by replacing characters with higher-order nilsequence objects. Gowers's 2001 proof of Szemerédi's theorem built directly on the Fourier-analytic method of Roth and the classical Fourier transform.
Carried by Timothy Gowers; Klaus Roth.
Classical Sumset Theory and Small Doubling influenced by Classical theory of representations by sums of powers in Additive Number Theory
The classical theory of representing integers as sums of powers (Waring's problem, Lagrange, Hilbert) posed the questions about additive structure that early sumset results generalized. Schnirelmann's and later small-doubling results reframed these representation questions in terms of sumsets of arbitrary sets.
Carried by David Hilbert; Lev Schnirelmann.
Extremal Additive Combinatorics influenced by Additive number theory in Number Theory
Additive number theory provided the motivating questions, such as sums of residues and Waring-type problems, that extremal additive combinatorics recast as extremal questions about sets. The Erdős school moved between the two fields, carrying techniques and problems across.
Carried by Paul Erdős.
Extremal Additive Combinatorics grew out of Extremal Combinatorics in Combinatorics
Extremal additive combinatorics is a branch that grew out of extremal combinatorics when its counting and density methods were transferred to sumsets and additive structures.
Extremal Additive Combinatorics influenced Additive Combinatorics and Transference in Analytic Number Theory
Extremal additive combinatorics, especially Szemerédi's theorem on arithmetic progressions, set the density questions that transference and the Green–Tao theorem addressed. The later work extended these results to sparse sets such as the primes.
Carried by Endre Szemerédi; Ben Green; Terence Tao.
Freiman Inverse Theory influenced Higher-order Fourier analysis in Additive Number Theory
Freiman inverse theory supplied the structural conclusions about sets with small doubling that higher-order Fourier analysis uses in its inverse theorems. The inverse theorem for Gowers norms is a higher-order analogue of Freiman's structural result.
Carried by Gregory Freiman; Ben Green; Terence Tao.
Freiman Inverse Theory influenced Transference principle in Additive Number Theory
Freiman inverse theory supplied the structural decomposition of sets with small doubling that the transference principle relies on when passing between dense and sparse models. The inverse theorems are a direct input to the transference machinery.
Carried by Gregory Freiman; Ben Green; Terence Tao.
Freiman Inverse Theory influenced Additive Combinatorics and Transference in Analytic Number Theory
Freiman's inverse theory of sumsets supplied the structural classification that inverse sumset arguments in additive combinatorics rely on. The transference and density-increment methods build on Freiman-type structure.
Carried by Gregory Freiman.

Additive Combinatorics is a planet in Nousfarer
Its city has a tower for each of these 7 frameworks. Land, walk in, and climb one concept at a time.
Land on Additive CombinatoricsRelated fields
Fields its ideas are linked to
- Additive Number Theory 7 links
- Number Theory 4 links
- Extremal Combinatorics 2 links
- Combinatorics 2 links
- Analytic Number Theory 2 links
- Harmonic Analysis 1 link
- Applied Mathematics 1 link
More in Combinatorics
- Algebraic Combinatorics
- Coding Theory
- Combinatorial Optimization
- Combinatorics
- Design Theory
- Enumerative Combinatorics
- Extremal Combinatorics
- Graph Theory
- Matroid Theory
- Order Theory
- Probabilistic Combinatorics
See where Additive Combinatorics sits on the Map of Human Knowledge