** 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 , .

Trivial lower bound: .

with has . Thus small diameter is expected only for non-cyclic simple groups.

**Conjecture (Babai)**. There exists a universal constant such that for every finite simple group and any ,

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

After works of Helfgott (for and ) and Hrushovski, the following result was obtained.

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

where depends only on scheme .

The following result is of a different nature.

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

where depends only on scheme .

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

Theorem 3 (Breuillard-Tointon)Let be a finite group such that . Then there exists a normal subgroup contained in ball of radius and such that has an abelian subgroup of index .

where depends only on scheme .

In Theorem 1, conjecturally . We can show that depends only on rank. With Gamburd, we can prove that for for almost all primes.

On Babai’s conjecture, Helfgott and Seress got it with polynomial in .

**2. Infinite groups **

** 2.1. Polynomial growth **

Theorem 4 (Gromov)If there exist and such that , then is virtually nilpotent. Converse holds.

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

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 be a finitely generated group. Let be a nested family of finite subsets whose union is and . Then 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 , there exists such that if is generated by finite set and is any finite subset such that

then is virtually nilpotent.

Our method also gives a proof of Gromov’s almost flat manifold theorem: there exists such that if a compact Riemannian -manifold has , then 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 such that if , then 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 such that if , then is virtually nilpotent.

**3. Additive combinatorics **

Describe subsets such that .

The Cauchy-Davenport theorem states that for every subset , . This is also true in . 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 . They have small doubling too: a -dimensional progression satisfies .

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

Theorem 8 (Freiman-Ruzsa)Let satisfy . Then there exist multidimensional progressions such that

and

Green-Rusza extended this result to arbitrary abelian groups. The answer is the same, provided multidimensional progressions are replaced with coset progressions where is a multidimensional progression and is a finite subgroup.

The proofs use elementary harmonic analysis.

**4. Non abelian groups **

**Problem**. In group , describe subsets such that .

** 4.1. Baby cases **

If , there exists a finite subgroup and such that and is contained in the normalizer of .

If with , there exists a finite subgroup normalized by and such that and .

Find proofs in my surveys.

If , several cosets may arise.

If , this fails, since arithmetic progressions show up (no finite subgroups in .

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