Notes of Emmanuel Breuillard’s second Oxford lecture 21-03-2017

Approximate groups, II

1. Expansion in Cayley graphs

Solvable groups cannot lead to expanders. On the other hand, simple groups do.

Theorem 1 (Kassabov-Lubotsky-Nikolov) There is a {k>0} and a {\epsilon>0} such that every finite simple group has a generating set of size {\leq k} that makes the collection of corresponding Cayley graphs an expander.

In fact, Suzuki groups were excluded from the theorem, until Breuillard-Green-Tao filled in this case.

Theorem 2 (Breuillard-Green-Guralnick-Tao) There exists {\epsilon=\epsilon(r)} with the following significance. Let {G} be a finite simple group of Lie type and of rank {r}. With at most {|G|^{2-\epsilon}} exceptions, pairs of elements of {G} produce Cayley graphs that constitute an {\epsilon}-expander.

We conjecture that there should be no exception provided more generators should be allowed (with {\epsilon=\epsilon(r,k)}).

1.1. Superstrong approximation

The following improves on the classical Weisfeiler-Matthew-Vaserstein theorem. It results from the efforts of many people.

Theorem 3 Let {G} be a simply connected semisimple algebraic group over {{\mathbb Q}}. If {S} generates a Zariski dense subgroup of {G({\mathbb Q})}, then {S\mod p} generates {G({\mathbb Z}/p{\mathbb Z})} and the associated Cayley graphs form an expander, as prime {p} tends to infinity.

We expect this to generalize from {p} prime to {n} integer prime to some {n_0}.

See Salehi-Golsefidy’s talk on friday.

2. The Bourgain-Gamburd method

  1. Initial stage ({n\leq c\log|G|}): exponential non-concentration on proper subgroups.
  2. Middle stage ({c\log|G|\leq n\leq C\log|G|}): {\ell^2}-flattening lemma. Convolution quantitatively decreases measure.
  3. Final stage ({n\geq C\log|G|}): quasirandomness.

The middle stage involves approximate groups. It is similar to Balog-Gowers-Szemeredi’s theorem.

3. Classification of approximate groups of {G(q)}

Every approximate group is either

  1. bounded,
  2. very large.

Equivalently, subset grow under tripling (Product Theorem).

Conjecturally, the theorem should extend to other linear groups in the following form: if {A} generates an approximate subgroup, then there exist subgroups {N} and {H} normalized by {A}, such that

  1. {N\subset A\cdots A},
  2. {H/N} is nilpotent,
  3. {A} is contained in finitely many cosets of {H}.

3.1. Consequences

Diameter bound: partial results on Babai’s conjecture.

4. What about alternating groups?

There are non-trivial approximate subgroups. For instance (Pyber), inside {\mathfrak{S}_n}, take {A=H\cup \{\sigma^{\pm 2}\}}, where {\sigma} is a long cycle and {H} is generated by {n/2} transpositions with disjoint supports.

Question. Is every approximate subgroup of {\mathfrak{S}_n} close to an approximate subgroup of a proper subgroup?

5. Proof of Product Theorem

It relies on the determnation of subgroups of {G(q)}. Done by Weisfeiler, but it is a different argument, due to Larsen-Pink, which helps us. They prove a non-concentration estimate, in terms of size of intersection of subgroup with algebraic subvarieties of {Gl_n(q)}.

Hrushovski found an approximate group version of Larsen-Pink’s theorem.


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