Notes of Emmanuel Breuillard’s second lecture 07-03-2017

Introduction to approximate groups, II

1. Approximate groups

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

  • {|AA|\leq K|A|}. This is called small doubling.
  • A weaker assumption is small tripling {|AAA|\leq K|A|}.
  • Prob{_{a,b\in A}(ab\in A)\geq \frac{1}{K}}.
  • Coincidences {ab=cd} are frequent:

    \displaystyle \begin{array}{rcl} |\{(a,b,c,d)\in A^4\,;\,ab=cd\}|\geq\frac{1}{K}|A|^3. \end{array}

  • {\exists X\subset G} with {|X|\leq K} and {AA\subset XA}.

In his Combinatorica paper, T. Tao showed that all these notions are roughly equivalent: there exists a universal constant {C} such that for every {K} there exists {K'\leq K^C} such that if one of these properties holds with constant {K} for some set {A}, then any other holds with constant {K'} for a set {A'} such that {|A\cap A'|\geq |A|/K'}, {|A'|\leq K'|A|}. Therefore Tao has chosen the following

Definition 1 (Tao) A finite set {A\subset G} is a {K}-approximate group if

  1. {1\in A}, {A^{-1}=A},
  2. there exists {X\subset G} with {|X|\leq K} and {AA\subset XA}.


Beware that small doubling does not imply small tripling. Indeed, the union of a subgroup {H} and an element {x\notin H} satisfies {|AA|\leq 4|A|} but {|AAA|\geq (|A|-1)^2}.

This shows that one indeed needs to go to a smaller set {A'} which has small tripling (here, remove {x}). However, small tripling implies small {n}-pling for all {n\geq 3}. In fact, more is true: {|AA\cdots A|\leq K^C|A|} with {C} independent on the number of factors.

2. Rusza’s distance

Definition 2 (Rusza) The Rusza distance between finite subsets {A} and {B} of group {G} is

\displaystyle \begin{array}{rcl} d(A,B)=\log\frac{|AB^{-1}|}{\sqrt{|A||B|}}. \end{array}


Thus {|AA|\leq K|A|\Leftrightarrow d(A,A^{-1})\leq \log K}.

This is symmetric, nonnegative and satisfies triangle inequality. Furthermore, {d(A,A)=0} iff {A} is a coset of a finite group.

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

Proof of triangle inequality

Consider map

\displaystyle \begin{array}{rcl} AC^{-1}\times B\rightarrow AB^{-1}\times BC^{-1},\quad (x,b)\mapsto (a_x b^{-1},bc_x^{-1}), \end{array}

where {x=a_x c_x^{-1}}, {a_x\in A}, {c_x\in C}. This map is injective.

This shows that {|AC^{-1}||B|\leq |AB^{-1}||BC^{-1}|}, qed.

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

Lemma 3 (Rusza’s covering lemma) Assume that {|AB|\leq K|A|}. Then {\exists X\subset B} such that {|X|\leq K} and {B\subset AA^{-1}X}.

Indeed, pick a maximal set {X\subset B} such that {Ax}, {x\in X} 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 {G} is abelian, if {|A+A|\leq K|A|}, then {|mA-nA|\leq K^{m+n}|A|}. In particular, small doubling implies small tripling.

Petridis has found a non-abelian version of this.

Lemma 5 (Petridis) If {|AB|\leq K|A|}, then there exists {X\subset A} such that for all {C\subset G}, {|CXB|\leq K|CX|}.

Taking {C=\{1\}} shows that {X} is a definite fraction of {B}.

Proof. Pick {X\subset A} such that {\frac{|XB|}{|X|}} is minimal (hence {\leq K}). Then argue by induction on {|C|}.

Theorem 6 (Balog-Szemeredi-Gowers) Let {A}, {B\subset G}. Let {\mathcal{G}} be a bipartite graph with vertex sets {A} and {B}. Assume that

  • {|A|=|B|}.
  • {|}edges of {\mathcal{G}|\geq \frac{1}{K}|A||B|}.
  • {|A\cdot_\mathcal{G}B|\leq K|A|},

where {A\cdot_\mathcal{G}B=\{ab\,;\,(a,b)} is an edge of {\mathcal{G}\}}. Then there exist {A'\subset A} and {B'\subset B} of size comparable to {|A|} and such that {|A'B'|\leq K^C|A|}.

The proof is graph theory.

4. Statement of the structure theorem

We start with a weak version.

Theorem 7 (Breuillard-Green-Tao) Let {k\geq 1}. Let {A\subset G} be a finite group such that {|AA|\leq K|A|}. Then there exists a virtually nilpotent subgroup {H} of {G} and {g\in G} such that {|A\cap gH|\geq \frac{1}{C(K)}|A|}.

{C(K)} depends only on {K}, not on {G}. Unfortunately, the proof does not give an effective bound on {C(K)}.

One can be more precise: {H=F\cdot N} where {N} is nilpotent with bounded number of generators and nilpotency class. Also{F} is bounded in the product of boundedly many copies o {(A\cup A^{-1})^C}.

Apply Rusza’s covering theorem, one gets {A\subset H\cdot X} for some {X\subset G} with {|X|\leq C(K)}.

4.1. Link with Gromov’s polynomial growth theorem

As it stands, this statement implies Gromov’s polynomial growth theorem. Indeed, if {G} has a polynomial growth, there are infinitely many {n} such that {|S^{2n}|\leq K|S^n|}. The structure theorem implies that {S^n\subset H_n X_n}, {|X_n|\leq C(K)}. If {n>C(K)}, then the index of {H} is the subgroup generated by {S} is at most {C(H)}.

4.2. Link with Margulis lemma

Corollary 8 Let {X} be a metric space with bounded geometry (every ball of radius 4 is covered by a bounded number {K} of balls of radius 1). Let {\Gamma} a discrete group of isometries of {X}. For {\epsilon\leq \epsilon_0(K)}, the subgroup generated by the set {S_\epsilon(x_0)} of elements {\gamma\in \Gamma} such that {d(\gamma x_0,x_0)<\epsilon} is virtually nilpotent.

Proof. Since {(S_\epsilon(x_0))^n\subset S_{n\epsilon}(x_0)}, {S_\epsilon(x_0)} has small doubling.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s