# Additive combinatorics

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Additive_combinatorics
> Markdown URL: https://mediated.wiki/source/Additive_combinatorics.md
> Source: https://en.wikipedia.org/wiki/Additive_combinatorics
> Source revision: 1314274977
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Area of combinatorics in mathematics

**Additive combinatorics** is an area of [combinatorics](/source/Combinatorics) in [mathematics](/source/Mathematics). One major area of study in additive combinatorics are *inverse problems*: given the size of the [sumset](/source/Sumset) *A* + *B* is small, what can we say about the structures of A and B? In the case of the integers, the classical [Freiman's theorem](/source/Freiman's_theorem) provides a partial answer to this question in terms of [multi-dimensional arithmetic progressions](/source/Multi-dimensional_arithmetic_progression).

Another typical problem is to find a lower bound for |*A* + *B*| in terms of |*A*| and |*B*|. This can be viewed as an inverse problem with the given information that |*A* + *B*| is sufficiently small and the structural conclusion is then of the form that either A or B 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](/source/Erd%C5%91s%E2%80%93Heilbronn_conjecture) (for a [restricted sumset](/source/Restricted_sumset)) and the [Cauchy–Davenport Theorem](/source/Cauchy%E2%80%93Davenport_theorem). The methods used for tackling such questions often come from many different fields of mathematics, including [combinatorics](/source/Combinatorics), [ergodic theory](/source/Ergodic_theory), [analysis](/source/Analysis), [graph theory](/source/Graph_theory), [group theory](/source/Group_theory), and [linear-algebraic](/source/Linear_algebra) 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](/source/Terence_Tao) and [Van H. Vu](/source/Van_H._Vu) in their 2006 book of the same name), a much older problem, the [Cauchy–Davenport theorem](/source/Cauchy%E2%80%93Davenport_theorem), is one of the most fundamental results in this field.

### Cauchy–Davenport theorem

Suppose that *A* and *B* are finite subsets of the [cyclic group](/source/Cyclic_group) ℤ/*p*ℤ for a prime p, then the following inequality holds.

- | A + B | ≥ min ( | A | + | B | − 1 , p ) {\displaystyle |A+B|\geq \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 A and B does the equality hold? Vosper's theorem answers this question. Suppose that |*A*|,|*B*| ≥ 2 (that is, barring edge cases) and

- | A + B | ≤ | A | + | B | − 1 ≤ p − 2 , {\displaystyle |A+B|\leq |A|+|B|-1\leq p-2,}

then A and B 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](/source/Pl%C3%BCnnecke%E2%80%93Ruzsa_inequality). This theorem gives an upper bound on the cardinality of |*nA* − *mA*| in terms of the doubling constant of A. 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](/source/Abelian_group); then the sum set is defined to be

- A + B = { a + b : a ∈ A , b ∈ B } . {\displaystyle A+B=\{a+b:a\in A,b\in B\}.}

For example, we can write {1,2,3,4} + {1,2,3} = {2,3,4,5,6,7}. Similarly, we can define the difference set of *A* and *B* to be

- A − B = { a − b : a ∈ A , b ∈ B } . {\displaystyle A-B=\{a-b:a\in A,b\in B\}.}

The k-fold sumset of the set A with itself is denoted by

- k A = A + A + ⋯ + A ⏟ k terms = { a 1 + ⋯ + a k : a 1 ∈ A , … , a k ∈ A } , {\displaystyle kA=\underbrace {A+A+\cdots +A} _{k{\text{ terms }}}=\{a_{1}+\cdots +a_{k}:a_{1}\in A,\dots ,a_{k}\in A\},}

which must not be confused with

- k ⋅ A = { k a : a ∈ A } . {\displaystyle k\cdot A=\{ka:a\in A\}.}

### Doubling constant

Let *A* be a subset of an abelian group. The doubling constant measures how big the sum set | A + A | {\displaystyle |A+A|} is compared to its original size |*A*|. We define the doubling constant of A to be

- K = | A + A | | A | . {\displaystyle K={\dfrac {|A+A|}{|A|}}.}

## 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

- d ( A , B ) = log ⁡ | A − B | | A | | B | . {\displaystyle d(A,B)=\log {\dfrac {|A-B|}{\sqrt {|A||B|}}}.}

The [Ruzsa triangle inequality](/source/Ruzsa_triangle_inequality) asserts that the Ruzsa distance obeys the triangle inequality:

- d ( B , C ) ≤ d ( A , B ) + d ( A , C ) . {\displaystyle d(B,C)\leq d(A,B)+d(A,C).}

However, since *d*(*A*,*A*) cannot be zero, the Ruzsa distance is not actually a [metric](/source/Metric_space).

## See also

- [Arithmetic combinatorics](/source/Arithmetic_combinatorics)

- [Additive number theory](/source/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.

---
Adapted from the Wikipedia article [Additive combinatorics](https://en.wikipedia.org/wiki/Additive_combinatorics) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Additive_combinatorics?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.