Notes of Emmanuel Breuillard’s first course 01-03-2017

Introduction to approximate groups

Today, an overview. Later on, I hope to proceed to the proof of Breuillard-Green-Tao’s structure theorem. I already wrote several surveys, see my web page. Here, I will follow the Minnesota 2014 lectures. See Tao’s blog and books too. Green and Helfgott also wrote surveys.

The subject started some 15 years ago, motivated by asymptotic finite group theory.

1. Diameter bounds

The Rubik’s cube problem asks for diameter bounds for finite Cayley graphs (note that the exact value of the diameter for the Rubik’s cube graph has been obtained only recently, with a large amount of brute force calculation).

Given {S\subset G}, {diam_S(G)=\min\{n\in{\mathbb N}\,;\,S^n=G\}}.

Trivial lower bound: {diam_S(G)\geq\frac{\log|G|}{\log|S|}}.

{{\mathbb Z}/n{\mathbb Z}} with {S=\{-1,0,1\}} has {diam_S(G)\sim |G|}. Thus small diameter is expected only for non-cyclic simple groups.

Conjecture (Babai). There exists a universal constant {C} such that for every finite simple group {G} and any {S\subset G},

\displaystyle \begin{array}{rcl} diam_S(G)\leq C\,(\log|G|)^C. \end{array}

It was known for no group until 2005, when Helfgott obtained a bound for alternating group{A_n}. At the same

After works of Helfgott (for {PSl(2)} and {PSl(3)}) and Hrushovski, the following result was obtained.

Theorem 1 (Pyber-Szabo, Breuillard-Green-Tao) Let {G} be a finite simple group of Lie type, i.e. {G=X(F_q)}. Then

\displaystyle \begin{array}{rcl} diam_S(G)\leq C_1\,(\log|G|)^{C_2}. \end{array}

where {C} depends only on scheme {X}.

The following result is of a different nature.

Theorem 2 (Breuillard-Tointon) Let {G} be a finite simple group. Then

\displaystyle \begin{array}{rcl} \forall\epsilon>0,\exists C_\epsilon \quad \textrm{such that}\quad diam_S(G)\leq C_\epsilon\,|G|^\epsilon. \end{array}

where {C} depends only on scheme {X}.

Indeed, it relies on the following result which does not apply to simple groups.

Theorem 3 (Breuillard-Tointon) Let {G} be a finite group such that {diam_S(G)\geq \frac{|G|^\epsilon}{|S|^\epsilon}}. Then there exists a normal subgroup {H} contained in ball of radius {(diam G)^{1/2 +\delta}} and such that {G/H} has an abelian subgroup of index {\leq C(\epsilon,\delta)}.

\displaystyle \begin{array}{rcl} \forall\epsilon>0,\exists C_\epsilon \quad \textrm{such that}\quad diam_S(G)\leq C_\epsilon\,|G|^\epsilon. \end{array}

where {C} depends only on scheme {X}.

In Theorem 1, conjecturally {C_2=1}. We can show that {C_2} depends only on rank. With Gamburd, we can prove that {C_2=1} for {PSl(2,p)} for almost all primes.

On Babai’s conjecture, Helfgott and Seress got it with {C} polynomial in {\log\log|G|}.

2. Infinite groups

2.1. Polynomial growth

Theorem 4 (Gromov) If there exist {k}and {C} such that {|S^n|\leq C\,n^k}, then {G} is virtually nilpotent. Converse holds.

The first step in the proof is to construct a sequence {n_i} such that

\displaystyle \begin{array}{rcl} \forall i,\quad |S^{3n_i}|\leq 4^K |S^{n_i}|. \end{array}

We call this a small tripling condition. This is what defines approximae groups.

2.2. Hrushovski’s approach

In 2010, Hrushovski proposed a strategy to detrmine approximate groups. As a biproduct, he got

Theorem 5 (Hrushovski) Let {G} be a finitely generated group. Let {\{A_n\}\}} be a nested family of finite subsets whose union is {G} and {|A_n|\leq K|A_n}. Then {G} is virtually nilpotent.

Note that, unlike in Gromov’s proof, no induction on dimension is possible.

A few months later, we got

Theorem 6 (Breuillard-Green-Tao) For all {K}, there exists {n_0(K)} such that if {G} is generated by finite set {S} and {A\subset G} is any finite subset such that

\displaystyle \begin{array}{rcl} |A^2|\leq K|A| \quad \textrm{and}\quad S^{n_0}\subset A, \end{array}

then {G} is virtually nilpotent.

Our method also gives a proof of Gromov’s almost flat manifold theorem: there exists {\epsilon(d)} such that if a compact Riemannian {d}-manifold has {\max\{\mathrm{sectional\, curvature}\}\mathrm{diameter}^2 <\epsilon(d)}, then {\pi_1} is virtually nilpotent.

2.3. Groups of intermediate growth

One is unable to weaken the assumption in Gromov’s theorem substantially. However, elaborating on his result for residuaally nilpotent groups, Grigorchak has formulated:

Grigorchuk’s gap conjecture. There exists {\alpha<1/2} such that if {|S^n|<e^{n^\alpha}}, then {G} is virtually nilpotent.

2.4. Effective bounds

None of the previous results give effective bounds on constants. Elaborating on a different method of proof discovered by Kleiner,

Theorem 7 (Shalom-Tao) There exists {c>0} such that if {|S^n|\leq n^{(\log\log n)^c}}, then {G} is virtually nilpotent.

3. Additive combinatorics

Describe subsets {A\subset{\mathbb Z}} such that {|A+A|\leq 100|A|}.

The Cauchy-Davenport theorem states that for every subset {A\subset{\mathbb Z}/p{\mathbb Z}}, {|A+A|\geq\min\{p,2|A|-1\}}. This is also true in {{\mathbb Z}}. Equality characterizes arithmetic progressions.

One expects that such sets are close to arithmetic progressions. We call this Freiman problem.

Multi-dimensional progressions are sets obtained as affine images of boxes in {{\mathbb Z}^d}. They have small doubling too: a {d}-dimensional progression {A} satisfies {|A+A|\leq 2^d|A|}.

The following result is due to Freiman. Rusza gave a much shorter proof.

Theorem 8 (Freiman-Ruzsa) Let {A\subset {\mathbb Z}} satisfy {|A+A|\leq K|A|}. Then there exist multidimensional progressions {P\subset Q} such that

\displaystyle \begin{array}{rcl} P\subset 2A-2A\subset Q, \end{array}


\displaystyle \begin{array}{rcl} |P|\leq |A|\leq C_K |P|,\quad |Q|\leq |A|\leq C_K |Q|,\quad dim(P),\,dim(Q)\leq C_K. \end{array}

Green-Rusza extended this result to arbitrary abelian groups. The answer is the same, provided multidimensional progressions are replaced with coset progressions {P=HL} where {L} is a multidimensional progression and {H<G} is a finite subgroup.

The proofs use elementary harmonic analysis.

4. Non abelian groups

Problem. In group {G}, describe subsets {A} such that {|AA|\leq K|A|}.

4.1. Baby cases

If {|AA|=|A|}, there exists a finite subgroup {H<G} and {a\in G} such that {A=aH} and {A} is contained in the normalizer of {H}.

If {|AA|\leq K|A|} with {K<\frac{3}{2}}, there exists a finite subgroup {H<G} normalized by {A} and {a\in G} such that {A\subset aH} and {|H|\leq K|A|}.

Find proofs in my surveys.

If {K<2}, several cosets may arise.

If {K=2}, this fails, since arithmetic progressions show up (no finite subgroups in {{\mathbb Z}}.

Larger {K} accomodate not only arithmetic progressions, but also balls in nilpotent groups. The structure theorem says that there is nothing else.


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