Additive combinatorics

Additive combinatorics studies additive patterns in subsets of groups and related algebraic structures. It connects the size and structure of sets with the sums, differences, and configurations they contain.

Sumset: The set of all sums formed by adding an element of one set to an element of another. Sumsets are the basic objects whose size and structure additive combinatorics investigates.
Plünnecke–Ruzsa inequalities: Inequalities bounding iterated sumset growth from bounds on a set's initial sumset growth. They turn small doubling into control over many repeated sums and differences.
Green–Tao theorem: The theorem that the prime numbers contain arithmetic progressions of every finite length. Its proof combines additive structure with relative density inside the primes.
Random set: A set generated by including elements according to a specified probability distribution. Random sets provide a baseline for distinguishing accidental patterns from structured ones.
Difference set: The set of all differences between elements of a set or between two sets. Difference sets reveal additive structure and underpin many growth arguments.
Balog–Szemerédi–Gowers theorem: A theorem extracting a large subset with small doubling from sufficiently high additive energy. It converts many additive coincidences into a structured subset.
Roth's theorem on arithmetic progressions: A density theorem guaranteeing a three-term arithmetic progression in sufficiently large subsets of the integers. This classic application illustrates the density-versus-pattern principle in a focused setting.
Bohr set: A subset of an abelian group defined by requiring selected characters to lie near the identity. Bohr sets are structured objects that often replace intervals in groups without a natural order.
Additive energy: A count of quadruples satisfying an equality of pairwise sums, measuring additive coincidences in a set. High energy signals many repeated sums and often points to hidden structure.
Freiman's theorem: A theorem describing finite sets with small doubling as lying in a generalized arithmetic progression of bounded rank. It explains why restricted sumset growth forces sets to resemble low-dimensional arithmetic structure.

Linked from 14 pages