Notes of Emmanuel Breuillard’s lecture nr 1

Posted on February 9, 2011 by metric2011

The main theme is approximate groups. The subject is classical in case the group is commutative. The key word is additive combinatorics, with applications to arithmetic progressions (Van der Waerden…). It also appeared in model theory. When the group is non commutative, interest is recent. Applications exists in group theory, probability.

Today, I give an overview of the course.

Note of the scribe: I will post only the overview. Emmanuel Breuillard plans to write notes himself.

 

1. Overview

 

1.1. Doubling

 

{G} is an ambient group, {A\subset G} a finite set. We want to roughly describe sets {A} such that {|AA|\leq K|A|}, where

  • {|A|} is the cardinal of {A},
  • {K\geq 1} is a parameter,
  • {AA=\{a_1 a_2 \,;\,a_1 ,\,a_2 \in A\}}.

Example: If {A} is a subgroup, then {AA=A}.

Exercise: {|AA|=|A|} iff {A=xH} where {H} is a subgroup and {xH=Hx}.

Definition 1 A subset {A} of {G} such that {|AA|\leq K|A|} is called a set of doubling at most {K}.

This is reminiscent of the notion of a doubling metric space.

The idea is that for fixed {K}, sets with doubling {K} are not so far from cosets of subgroups.

Proposition 2 If {|AAA|\leq K|A|}, then {|A^{n}|\leq K^{2n-2}|A|} for every {n\geq 1}.

“Small tripling implies small {n}-pling for all {n}“. But this does not work for doubling.

 

1.2. Connection with growth of groups

 

Given a finite generating (symmetric) set {S} of {G}, one can define the {n}-balls {S^n} of any integral radius. The volume growth (growth type of {|S^n|}) does not depend on the choice of {S}. Here is the most spectacular result.

Theorem 3 (Gromov 1981) If {G} is finitely generated and has polynomial volume growth, then {G} is virtually nilpotent.

Virtually means up to taking a finite index subgroup.

Definition 4 Let {G} be a group. Denote by {C^0 (G)=G}, {C^{k+1}(G)=[G,C^{k}(G)]} the descending central series. {G} is nilpotent if there exists {r} such that {C^r (G)=\{1\}}.

 

Proof: of Gromov’s theorem (sketch). Polynomial growth implies that at many scales, there will be doubling. Indeed, if {|S^{2n}|>K|S^{n}|} for all {n}, then {|S^{2^k}|>K^k |S|} contradicts polynomial growth of degree {\leq \log_2 K}.

Further steps in the proof rely on the solution of Hilbert’s fifth problem: a characterization of Lie groups among locally compact groups. \Box

 

1.3. Application to finite simple groups

 

Thirty years ago, group theorists came up with a classification of finite simple groups: these are matrix groups, alternating groups, plus a finite set of exceptions.

This left open the question of the geometry of the possible Cayley graphs of these groups.

Definition 5 Let {G} be a group, {S} a symmetric generating set. The Cayley graph {Cay(G,S)} has vertex set {G}, and one connects {x} to {y} iff there is an {s\in S} such that {y=xs}.

{G} acts by automorphisms (left translation on vertices) of {Cay(G,S)}. The simplicial metric on {Cay(G,S)} induces the word metric on {G}.

Question: Let {G} be a finite simple group. What is the diameter of {Cay(G,S)} ?

László Babai conjectured that there exists a universal constant {C} such that for every finite simple group {G} and every generating set {S},

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

Theorem 6 (Helfgott 2005) Babai’s conjecture holds for {G=PSL_2 ({\mathbb Z}/p{\mathbb Z})}, {p} a prime.

Helfgott proved that generating sets have large tripling, i.e. there exists {\epsilon>0} such that for every generating set {A},

\displaystyle \begin{array}{rcl} |AAA|\geq\min\{|G|,|A|^{1+\epsilon}\}. \end{array}

 

1.4. Application to expanders

 

Expanders were born in computer science. They have been applied recently to number theory, in the sieve method, see below and forthcoming workshop.

Definition 7 Let {k\geq 3}. A family of {k}-regular graphs {\mathcal{G}_n} is a family of expanders if there exists {\epsilon>0} such that for all {n} and all subsets {A} of vertices of {\mathcal{G}_n} (of size at most half of {\mathcal{G}_n}), the vertex boundary

\displaystyle \begin{array}{rcl} \partial_{v}A=\{v\in \mathcal{G}_n \,;\,x\notin A,\,d(v,A)=1\} \end{array}

has size {|\partial_{v}A|\geq\epsilon|A|}.

 

Although random {k}-regular graphs are expanders, it is not easy to construct explicit families of expanders. Margulis observed that the Cayley graphs of the finite quotients {SL_3 ({\mathbb Z}/p{\mathbb Z})} of {SL_3 ({\mathbb Z})}, with a generating set coming from {SL_3 ({\mathbb Z})}, form an expanding family. This relies on Kazhdan’s property (T), a fact from representation theory, that fails for {SL_2 ({\mathbb Z})}.

In a Cayley graph {Cay(G,S)}, {\partial_{v}A=SA\setminus A}. Being an {\epsilon}-expander means that for every set {A\in G} of size at most half, {|AS|\geq (1+\epsilon)|A|}.

In 2005, Bourgain and Gamburd came up with a new method to prove expansion.

Theorem 8 (Bourgain, Gamburd) Fix a set {S\subset SL_2 ({\mathbb Z})} that does not generate a virtually cyclic group. Then the Cayley graphs {Cay(SL_2 ({\mathbb Z}/p{\mathbb Z}),S} mod {p)} are a family of expanders.

The fact that {SL_2 ({\mathbb Z}/p{\mathbb Z})} has very few subgroups allows fro the very weak assumption on {S}.

Bourgain and Gamburd use Helfgott’s result on tripling. Consider the simple random walk on the Cayley graph. An equivalent definition of expansion is the fact that this random walk equidistributes fast (in logarithmic time). In small time, the walk only sees a tree, where equidistribution is entirely understood. Then comes the time where the walk reaches the diameter. If it does not equidistribute, it has to be stuck in a set which has small tripling.

 

1.5. Lubotzky’s 1-2-3 problem

 

Long before Bourgain and Gamburd’s recent results, Alex Lubotzky had advertised the following problem.

Consider the subgroups of {SL_2 ({\mathbb Z})} generated by the following matrices:

\displaystyle \begin{array}{rcl} S_1 &:& \begin{pmatrix}1&1\\ 0&1 \end{pmatrix},\quad \begin{pmatrix}1&0\\ 1&1 \end{pmatrix},\\ S_2 &:& \begin{pmatrix}1&2\\ 0&1 \end{pmatrix},\quad \begin{pmatrix}1&0\\ 2&1 \end{pmatrix},\\ S_1 &:& \begin{pmatrix}1&3\\ 0&1 \end{pmatrix},\quad \begin{pmatrix}1&0\\ 3&1 \end{pmatrix}. \end{array}

The first two have finite index in {SL_2 ({\mathbb Z})} (but the third one does not) and this was used to show (using powerful number theoretic results of Selberg) that {Cay(SL_2 ({\mathbb Z}/p{\mathbb Z}),S_1)} or {Cay(SL_2 ({\mathbb Z}/p{\mathbb Z}),S_2)} are families of expanders. But the method did not apply to {S_3}, a case which remained open for a long time.

 

1.6. Application to number theory

 

Pioneered by Bourgain, Gamburd, Sarnak, and more recently by Kowalski, Ellenberg. Here is a striking application to Appolonian packings.

If four circles in Euclidean plane are tangent, and if three curvatures (inverse of radii) are integers, so is the fourth one. So the picture generates a sequence of integers, which can be viewed as an orbit of a rather large discrete subgroup, Zariski dense but not a lattice, of an orthogonal group. Sarnak asked wether this sequence contains infinitely many primes (note that an arithmetic progression is an orbit of an action of {{\mathbb Z}}). Bourgain, Gamburd and Sarnak show that there are infinitely many almost primes, i.e. numbers with a bounded number of divisors. In this non commutative sieving theorem, tripling plays a key role.

 

2. Plan of the course

 

  1. Tools from combinatorics 
    • Approximate groups, Ruzsa distance
    • Balog-Szemeredi Gowers theorem
    • Smu-product phenomenon
  2. Abelian theory
    • Freiman’s theorem
    • Bohr sets
    • Nilpotent Freiman, nilprogressions
  3. Linear theory
    • Helfgott’s theorem for {SL_2}
    • Its generalizations (Pyber-Szabo, Breuillard-Green-Tao)
    • Jordan’s theorem
    • Jordan’s theorem in positive characteristic (Weisfeiler-Nori, Larsen-Pink)
    • Hrushovski’s theorem
  4. Applications
    • Bourgain-Gamburd’s method for expansion
    • Diameter of Cayley graphs

We shall see that many arguments in group theory adapt to approximate groups. For instance, Jordan’s theorem does. The model theory approach of Hrushovski does not give sharp enough estimates as required by applications, but is interesting anyway. The fourth part, on applications, will be continued by Alex Gamburd in his course.

 

References

 

Babai, László; Seress, \’Akos; On the diameter of Cayley graphs of the symmetric group. J. Combin. Theory Ser. A 49 (1988), no. 1, 175–179.

Bourgain, Jean; Gamburd, Alex; Uniform expansion bounds for Cayley graphs of {{\rm SL}_2(\Bbb F_p)}. Ann. of Math. (2) 167 (2008), no. 2, 625–642.

Bourgain, Jean; Gamburd, Alex; Sarnak, Peter; Affine linear sieve, expanders, and sum-product. Invent. Math. 179 (2010), no. 3, 559–644.

Gromov, Mikhael; Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. No. 53 (1981), 53–73.

Helfgott, Harald; Growth and generation in {{\rm SL}_2(\Bbb Z/p\Bbb Z)}. Ann. of Math. (2) 167 (2008), no. 2, 601–623.

 

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 http://www.math.ens.fr/metric2011/
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a comment