Additive combinatorics
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 formula_1 and formula_2? 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. Another typical problem is to find a lower bound for formula_3 in terms of formula_4 and formula_5. This can be viewed as an inverse problem with the given information that formula_6  is sufficiently small and the structural conclusion is then of the form that either formula_1 or formula_2 is the empty set; however, in literature, such problems are sometimes considered to be 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 often come from many different fields of mathematics, including combinatorics, ergodic theory, analysis, graph theory, group theory, and linear algebraic and polynomial methods. History of additive combinatorics. Although additive combinatorics is a fairly new branch of combinatorics (in fact the  term "additive combinatorics" was coined by Terence Tao and Van H. Vu in their book in 2000's), an extremely old problem Cauchy–Davenport theorem is one of the most fundamental results in this field. Cauchy–Davenport theorem. Suppose that "A" and "B" are finite subsets of the prime order cyclic group formula_9 for a prime formula_10, then the following inequality holds. Vosper's theorem. Now we have the inequality for the cardinality of the sum set formula_12, it is natural to ask the inverse problem, namely under what conditions on formula_1 and formula_2 does the equality hold? Vosper's  theorem answers this question. Suppose that formula_15 (that is, barring edge cases) and then formula_1 and formula_2 are arithmetic progressions with the same difference. This illustrates the structures that are often studied in additive combinatorics: the combinatorial structure of formula_19 as compared to the algebraic structure of arithmetic progressions. Plünnecke–Ruzsa inequality. A useful theorem in additive combinatorics is Plünnecke–Ruzsa inequality. This theorem gives an upper bound on the cardinality of formula_20 in terms of the doubling constant of formula_1. For instance using Plünnecke–Ruzsa inequality, we are able to prove a version of Freiman's Theorem in finite  fields. Basic notions. Operations on sets. Let "A" and "B" be finite subsets of an abelian group, then the sum set is defined to be For example, we can write formula_23. Similarly we can define the difference set of "A" and "B" to be Here we provide other useful notations. Not to be confused with Doubling constant. Let "A" be a subset of an abelian group. The doubling constant measures how big the sum set formula_27 is compared to its original size |"A"|. We define the doubling constant of "A" to be Ruzsa distance. Let "A" and "B" be two  subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity Ruzsa triangle inequality tells us that the Ruzsa distance obeys the triangle inequality: However, since formula_31 cannot be zero, note that the Ruzsa distance is not actually a metric.