Additive combinatorics

Template:Short description 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 Template:Mvar and Template:Mvar? 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 Template:Abs in terms of Template:Abs and Template:Abs. This can be viewed as an inverse problem with the given information that Template:Abs is sufficiently small and the structural conclusion is then of the form that either Template:Mvar or Template:Mvar 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 (the term additive combinatorics was coined by Terence Tao and Van H. Vu in their 2006 book of the same name), a much older problem, the Cauchy–Davenport theorem, is one of the most fundamental results in this field.

Cauchy–Davenport theorem

Suppose that Template:Mvar and Template:Mvar are finite subsets of the cyclic group ℤ/pℤ for a prime Template:Mvar, then the following inequality holds.

$|A+B|\ge \min (|A|+|B|-1,p)$

Vosper's theorem

Now we have the inequality for the cardinality of the sum set A + B, it is natural to ask the inverse problem, namely under what conditions on Template:Mvar and Template:Mvar does the equality hold? Vosper's theorem answers this question. Suppose that Template:Abs,Template:Abs ≥ 2 (that is, barring edge cases) and

$|A+B|\le |A|+|B|-1\le p-2,$

then Template:Mvar and Template:Mvar are arithmetic progressions with the same difference. This illustrates the structures that are often studied in additive combinatorics: the combinatorial structure of A + B 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 Template:Abs in terms of the doubling constant of Template:Mvar. 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 Template:Mvar and Template:Mvar be finite subsets of an abelian group; then the sum set is defined to be

$A+B=\{a+b:a\in A,b\in B\}.$

For example, we can write Template:Mset + Template:Mset = Template:Mset. Similarly, we can define the difference set of Template:Mvar and Template:Mvar to be

$A-B=\{a-b:a\in A,b\in B\}.$

The Template:Mvar-fold sumset of the set Template:Mvar with itself is denoted by

$kA=\underset{k\text{ terms }}{\underbrace{A+A+\cdots +A}}=\{a_1+\cdots +a_k:a_1\in A,\dots ,a_k\in A\},$

which must not be confused with

$k\cdot A=\{ka:a\in A\}.$

Doubling constant

Let Template:Mvar be a subset of an abelian group. The doubling constant measures how big the sum set $|A+A|$ is compared to its original size Template:Abs. We define the doubling constant of Template:Mvar to be

$K=\frac{|A+A|}{|A|}.$

Ruzsa distance

Let Template:Mvar and Template:Mvar be two subsets of an abelian group. We define the Ruzsa distance between these two sets to be the quantity

$d(A,B)=\log \frac{|A-B|}{\sqrt{|A||B|}}.$

The Ruzsa triangle inequality asserts that the Ruzsa distance obeys the triangle inequality:

$d(B,C)\le d(A,B)+d(A,C).$

However, since d(A,A) cannot be zero, the Ruzsa distance is not actually a metric.

See also

• Arithmetic combinatorics
• Additive number theory

References

Citations

• Tao, T., & Vu, V. (2006). Additive combinatorics. Cambridge: Cambridge University Press.
• Green, B. (2009, January 15). Additive Combinatorics Book Review. Retrieved from https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf.