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 .
- 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
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
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 8 Let 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.