** Introduction to approximate groups, II **

**1. Approximate groups **

Naively, think of a finite subset in a group as approximately a subgroup if it does not increase much under multiplication. Here are various measurements:

- . This is called small doubling.
- A weaker assumption is small tripling .
- Prob.
- Coincidences are frequent:
- with and .

In his Combinatorica paper, T. Tao showed that all these notions are roughly equivalent: there exists a universal constant such that for every there exists such that if one of these properties holds with constant for some set , then any other holds with constant for a set such that , . Therefore Tao has chosen the following

Definition 1 (Tao)A finite set is a -approximate group if

- , ,
- there exists with and .

Beware that small doubling does not imply small tripling. Indeed, the union of a subgroup and an element satisfies but .

This shows that one indeed needs to go to a smaller set which has small tripling (here, remove ). However, small tripling implies small -pling for all . In fact, more is true: with independent on the number of factors.

**2. Rusza’s distance **

Definition 2 (Rusza)The Rusza distance between finite subsets and of group is

Thus .

This is symmetric, nonnegative and satisfies triangle inequality. Furthermore, iff is a coset of a finite group.

This is used in the proof that small tripling implies small -pling.

**Proof of triangle inequality**

Consider map

where , , . This map is injective.

This shows that , qed.

**Question**. Is there some interesting geometry in this semi-metric ?

Lemma 3 (Rusza’s covering lemma)Assume that . Then such that and .

Indeed, pick a maximal set such that , are disjoint.

**3. Further combinatorial tools **

The theory has a small number of elementary tricks. We give 3 of them.

Proposition 4 (Plunnecke-Rusza, Petridis)When is abelian, if , then . In particular, small doubling implies small tripling.

Petridis has found a non-abelian version of this.

Lemma 5 (Petridis)If , then there exists such that for all , .

Taking shows that is a definite fraction of .

**Proof**. Pick such that is minimal (hence ). Then argue by induction on .

Theorem 6 (Balog-Szemeredi-Gowers)Let , . Let be a bipartite graph with vertex sets and . Assume that

- .
- edges of .
- ,
where is an edge of . Then there exist and of size comparable to and such that .

The proof is graph theory.

**4. Statement of the structure theorem **

We start with a weak version.

Theorem 7 (Breuillard-Green-Tao)Let . Let be a finite group such that . Then there exists a virtually nilpotent subgroup of and such that .

depends only on , not on . Unfortunately, the proof does not give an effective bound on .

One can be more precise: where is nilpotent with bounded number of generators and nilpotency class. Also is bounded in the product of boundedly many copies o .

Apply Rusza’s covering theorem, one gets for some with .

** 4.1. Link with Gromov’s polynomial growth theorem **

As it stands, this statement implies Gromov’s polynomial growth theorem. Indeed, if has a polynomial growth, there are infinitely many such that . The structure theorem implies that , . If , then the index of is the subgroup generated by is at most .

** 4.2. Link with Margulis lemma **

Corollary 8Let be a metric space with bounded geometry (every ball of radius 4 is covered by a bounded number of balls of radius 1). Let a discrete group of isometries of . For , the subgroup generated by the set of elements such that is virtually nilpotent.

**Proof**. Since , has small doubling.