Notes of Arindam Biswas’ informal Cambridge lecture 28-02-2017

Spectral gaps for {Sl(2,F_p)}

1. Context

Goal: produce expanders. These will be Cayley graphs of finite quotients of a group, {Sl(2,{\mathbb Z})}, which does not have property (T). Therefore, the method is new. Lubotsky had pointed out that, prior to Bourgain-Gamburd’s work, one did not know wether the following generating systems

\displaystyle  \begin{array}{rcl}  S^i_p =\{\begin{pmatrix} 1 & i \\ 0 & 1 \end{pmatrix},\begin{pmatrix} 1 & 0 \\ i & 1 \end{pmatrix}\} \end{array}

produce an expander, as {p\rightarrow\infty}, when {i=3}. When {i=1} or 2, it follows from Selberg’s {\frac{3}{16}} theorem.

Theorem 1 (Bourgain-Gamburd) Fix a finite subset {S} of {SL(2,{\mathbb Z})}. Let {S_p} be the image of {S} in {G_p:=Sl(2,F_p)}. Then the family {Cay(G_p,S_p)} is an expander iff {S} generates a non-elementary subgroup of {Sl(2,{\mathbb Z})}.

{\Rightarrow} is straightforward.

2. Scheme of proof

The main result is

Proposition 2 Fix {k\geq 2}. Suppose that none of the {k} generators is an involutions and that

\displaystyle  \begin{array}{rcl}  \mathrm{girth}(Cay(G_p,S_p))\geq|tau\,\log_{2k}p. \end{array}

Then {Cay(G_p,S_p)} form an expander.

Indeed, Gamburd had observed earlier that the girth is at least logarithmic, when {S} is free. It follows from a short argument going back to Margulis.

3. Connectedness of {Cay(G_p,S_p)}

This follows from Dickson’s classification of subgroups of {G_p}. If {p\geq 5}, proper subgroups either

  1. contain a cyclic subgroup of index 2,
  2. have order {\leq 120},
  3. or lie in a Borel subgroup.

All such subgroups (but those of order {\leq 120}) satisfy the following law: all brackets {[[g_1,g_2],[g_3,g_4]]} vanish. This implies that the girth of a non-generating subset {S_p} would stay bounded, contradiction.

4. Measures

We consider probability measures on {G_p} and study how their {\ell^2} norm decays under convolution. We then apply this to the uniform measure {\mu_S} on {S_p}. It yields information on random walks, hence on spectral gap.

Indeed, let {W_{2\ell}} denote the number of walks on {Cay(G_p,S_p)}. Let {T} be the adjacency matrix of this graph and {\lambda_0,\ldots,\lambda_{N-1}} its eigenvalues. Its size is {N=|G_p|=\frac{1}{2}(p^2-1)}. Then

  1. {NW_{2\ell}=\mathrm{trace}(T^{2\ell})=\sum_{i}\lambda_i^{2\ell}}.
  2. {\mu_S^{2\ell}(1)=\frac{W_{2\ell}}{(2k)^{2\ell}}}.
  3. {\mu_S^{2\ell}} is symmetric.

The main point in the proof is the following Lemma.

Lemma 3 Let {|S_p|=2k}. Assume that {Cay(G_p,S_p)} has logarithmic girth. Then for all {\epsilon>0}, there exists {C(\epsilon,\tau)} such that for {\ell\geq C},

\displaystyle  \begin{array}{rcl}  \|\mu_S^{\ell}\|_2 \leq p^{-\frac{3}{2}+\epsilon}. \end{array}

4.1. Here is how the Lemma implies the Proposition

The Lemma implies that, for {\ell\geq C\,\log_{2k}p},

\displaystyle  \begin{array}{rcl}  W_{2\ell}\leq (2k)^{2\ell}p^{-3+2\epsilon}. \end{array}

We know that the every nontrivial representation of {G_p} occurs in {\ell^2(G_p)} with multiplicity at least {\frac{1}{2}(p-1)} (Frobenius). The trivial representation occurs only for {\lambda_0}. Therefore {\lambda_1} has multiplicity at least {\frac{1}{2}(p-1)}. Hence

\displaystyle  \begin{array}{rcl}  \lambda_1^{2\ell}\leq N\frac{(2k)^{2\ell}}{\frac{1}{2}(p-1)p^{3-2\epsilon}}\leq const.\frac{(2k)^{2\ell}}{p^{-2\epsilon}} \end{array}

Choosing {2\ell= C\,\log_{2k}p} yields a constant lower bound on {\lambda_0-\lambda_1}, whence the expansion.

5. Decay of {\ell^2} norms

Lemma 4 Fix {\gamma<\frac{3}{4}}. Assume a probability measure satisfies

  1. {\|\nu\|_\infty<p^{-\gamma}},
  2. {\|\nu\|_2\geq p^{-\frac{3}{2}+\gamma}},
  3. for every proper subgroup {G_0},

    \displaystyle  \begin{array}{rcl}  \nu\star\nu(G_0)\leq p^{-\gamma}. \end{array}


\displaystyle  \begin{array}{rcl}  \|\nu\star\nu\|_2 \leq p^{-\epsilon}\|\nu\|_2. \end{array}

The proof of this relies on Helfgott’s product theorem and approximate subgroups.

First, one splits {G_p} into level sets of {\nu} and approximates {\nu} with {\tilde\nu} which takes values in powers of {1/2}. Then, using triangle inequality, the estimate boils down to estimating the convolution of two characteristic functions of subsets.

Define multiplicative energy

\displaystyle  \begin{array}{rcl}  E(A,B)=|\{(x_1,x_2,y_1,y_2)\in A^2\times B^2\, x_1y_1=x_2y_2\}|=\|\chi_A \star\chi_B\|_2^2. \end{array}

If Lemma fails, we find subsets {A} and {B} such that

\displaystyle  \begin{array}{rcl}  E(A,B)\geq p^{-4\epsilon}|A|^{3/2}|B|^{3/2}. \end{array}

Then, Balog-Szemeredi-Gowers’ theorem implies that {A} contains a subset {X} such that {|X|\geq c|A|} and {|XX^{-1}|\leq C\,|A|}. Thus there is an approximate subgroup {H} of comparable size, i.e. at most {p^{3-2\gamma}}.

Helfgott’s product theorem states that if {|H|\leq p^{3-\gamma}} and {H} is not contained in a proper subgroup, then {|HHH|\geq c|H|^{1+\kappa}}. This gives the required contradiction, and proves Lemma 4.

6. Proof of Lemma 3

The girth assumption implies that walks of length {\tau\log_{2k}p} behave like in a {2k}-regular tree, where {\ell^2} norms decay exponentially under convolution (Kesten).

Lemma 4 is used iteratively to pass from time scale {\tau\log_{2k}p} to {C\,\log_{2k}p}.

7. Final remarks

In a finite group {G}, assume that one has the following bounds:

  1. Lower bound on degrees of nontrivial representations: {\geq |G|^\beta}.
  2. Classification of approximate subgroups: {|G|^\delta}-approximate subgroup either have size {\geq |G|^{1-\epsilon}} or do not differ much from cosets of subgroups.
  3. Non-concentration estimate for convolutes on subgroups: {\mu_S^n(H)\leq [G:H]^{-\kappa}}.

Then {\lambda_1(Cay(G,S))\geq \beta e^{-C/\delta}}.

Thus fact 3 (non-concentration) is the suitable generalization of the girth bound.

Benoist-de Saxce implement a similar strategy in the continuous setting. Their almost Diophantine assumption is a non-concentration estimate.

They conjecture that every probability measure generating a dense subgroup is almost Diophantine. They prove this for measures whose support is contained in matrices with algebraic entries (this relies on Benoist-Quint).


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 seminar 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