Example
If A is a set of N integers, how large or small can the sumset
the difference set
and the product set
be, and how are the sizes of these sets related? (Not to be confused: the terms difference set and product set can have other meanings.)
In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive combinatorics is the special case when only the operations of addition and subtraction are involved.
Ben Green explains arithmetic combinatorics in his review of "Additive Combinatorics" by Tao and Vu. [1]
Szemerédi's theorem is a result in arithmetic combinatorics concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured [2] that every set of integers A with positive natural density contains a k term arithmetic progression for every k. This conjecture, which became Szemerédi's theorem, generalizes the statement of van der Waerden's theorem.
The Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, [3] states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, there exist arithmetic progressions of primes, with k terms, where k can be any natural number. The proof is an extension of Szemerédi's theorem.
In 2006, Terence Tao and Tamar Ziegler extended the result to cover polynomial progressions. [4] More precisely, given any integer-valued polynomials P1,..., Pk in one unknown m all with constant term 0, there are infinitely many integers x, m such that x + P1(m), ..., x + Pk(m) are simultaneously prime. The special case when the polynomials are m, 2m, ..., km implies the previous result that there are length k arithmetic progressions of primes.
The Breuillard–Green–Tao theorem, proved by Emmanuel Breuillard, Ben Green, and Terence Tao in 2011, [5] gives a complete classification of approximate groups. This result can be seen as a nonabelian version of Freiman's theorem, and a generalization of Gromov's theorem on groups of polynomial growth.
If A is a set of N integers, how large or small can the sumset
the difference set
and the product set
be, and how are the sizes of these sets related? (Not to be confused: the terms difference set and product set can have other meanings.)
The sets being studied may also be subsets of algebraic structures other than the integers, for example, groups, rings and fields. [6]
In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.
In additive combinatorics, the sumset of two subsets and of an abelian group is defined to be the set of all sums of an element from with an element from . That is,
Terence Chi-Shen Tao is an Australian mathematician. He is a professor of mathematics at the University of California, Los Angeles (UCLA), where he holds the James and Carol Collins chair. His research includes topics in harmonic analysis, partial differential equations, algebraic combinatorics, arithmetic combinatorics, geometric combinatorics, probability theory, compressed sensing and analytic number theory.
Ben Joseph Green FRS is a British mathematician, specialising in combinatorics and number theory. He is the Waynflete Professor of Pure Mathematics at the University of Oxford.
In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if is small, then can be contained in a small generalized arithmetic progression.
Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.
In number theory, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number k, there exist arithmetic progressions of primes with k terms. The proof is an extension of Szemerédi's theorem. The problem can be traced back to investigations of Lagrange and Waring from around 1770.
In additive number theory and combinatorics, a restricted sumset has the form
Problems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view.
Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.
Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are inverse problems: given the size of the sumset A + B is small, what can we say about the structures of and ? In the case of the integers, the classical Freiman's theorem provides a partial answer to this question in terms of multi-dimensional arithmetic progressions.
Vitaly Bergelson is a mathematical researcher and professor at Ohio State University in Columbus, Ohio. His research focuses on ergodic theory and combinatorics.
In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set of integers, at least one of , the set of pairwise sums or , the set of pairwise products form a significantly larger set. More precisely, the Erdős–Szemerédi theorem states that there exist positive constants c and such that for any non-empty set
In mathematics, in the field of additive combinatorics, a Gowers norm or uniformity norm is a class of norms on functions on a finite group or group-like object which quantify the amount of structure present, or conversely, the amount of randomness. They are used in the study of arithmetic progressions in the group. They are named after Timothy Gowers, who introduced it in his work on Szemerédi's theorem.
Tamar Debora Ziegler is an Israeli mathematician known for her work in ergodic theory, combinatorics and number theory. She holds the Henry and Manya Noskwith Chair of Mathematics at the Einstein Institute of Mathematics at the Hebrew University.
In mathematics, an approximate group is a subset of a group which behaves like a subgroup "up to a constant error", in a precise quantitative sense. For example, it is required that the set of products of elements in the subset be not much bigger than the subset itself. The notion was introduced in the 2010s but can be traced to older sources in additive combinatorics.
Rudin's conjecture is a mathematical hypothesis concerning an upper bound for the number of squares in finite arithmetic progressions. The conjecture, which has applications in the theory of trigonometric series, was first stated by Walter Rudin in his 1960 paper Trigonometric series with gaps.
In mathematics, and in particular in arithmetic combinatorics, a Salem-Spencer set is a set of numbers no three of which form an arithmetic progression. Salem–Spencer sets are also called 3-AP-free sequences or progression-free sets. They have also been called non-averaging sets, but this term has also been used to denote a set of integers none of which can be obtained as the average of any subset of the other numbers. Salem-Spencer sets are named after Raphaël Salem and Donald C. Spencer, who showed in 1942 that Salem–Spencer sets can have nearly-linear size. However a later theorem of Klaus Roth shows that the size is always less than linear.
Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's theorem is a special case of Szemerédi's theorem for the case .
