Question

I am reading a significant paper of Bourgain and Gamburd on "Uniform expansion bounds for Cayley graphs of $\mathrm{SL}_2(\Bbb{F}_p)$". They have proven a proposition which in their new papers they call it "$L^2$-Flattening Lemma" (Indeed this proposition says more). Let me state their proposition:

Suppose $v$ is a symmetric probability measure on $\mathrm{SL}_2(\Bbb{F}_p)$; that is $$ v(g)=v(g^{-1}), $$ satisfying the following three properties for fixed positive $\gamma$, $0<\gamma<3/4$:

$$ p^{-\frac{3}{2}+\gamma}<|| v ||_2 < p^{-\gamma}, $$ and for any proper subgroup $G_0$ we have

$$ v\ast v[G_0]:=\sum_{a\in G_0}v \ast v(a)< p^{-\gamma}. $$

Then for some $\epsilon=\epsilon(\gamma)> 0$, for all sufficiently large $p$: $$ ||v\ast v ||_2< p^{-\epsilon}||v||_2. $$

Question:

What is a motivation for this proposition? Why this proposition is called "Flattening Lemma"? Is it because of the $L^2$-norm of $v\ast v$ is smallet than the $L^2$-norm of $v$? Or it has another reason.

Thank you in advance.

Answer 1

Perhaps I can add a little to Denis' answer. I have read Bourgain and Gamburd's wonderful paper several times - I don't pretend to fully understand it but I did write some notes on it which you may find useful.

A facetious explanation as to why the $L_2$-flattening lemma is important is that it is a crucial step in proving the main theorem of the paper. This is not really helpful but, in a sense, it is true. One should consider what Bourgain and Gamburd are trying to do:

We have a set $A\subset SL_2(\mathbb{Z})$; we consider the Cayley graph $\mathcal{G}( SL_2(\mathbb{Z}/p\mathbb{Z}), A_p)$ which is obtained by taking the image of elements of $A$ mod $p$ for some prime $p$. BG assume that one has a lower bound on the girth of this Cayley graph, from which it is easy enough to show that, for $p$ large enough, the graph is connected.

So, now, one has to show that $\mathcal{G}( SL_2(\mathbb{Z}/p\mathbb{Z}), A_p)_{p\to \infty}$ is a family of expanders. To do this, some notation:

Let $\mu_p: SL_2(\mathbb{Z}/p\mathbb{Z})\to \mathbb{R}^+$ be the indicator probability measure for the set $A_p$, i.e. it takes the value $1/|A_p|$ for elements of $A_p$ and $0$ elsewhere. There is a standard notion of convolution of measures which is very important in this area: write $\mu_p\ast \mu_p$ for the convolution of $\mu_p$ with itself, and write $\mu_p^{(l)}$ to mean the measure obtained by doing that $l$ times.

Now the following identities are crucial (and easy):

$$N W_{2l} = {\rm tr}(Adj^{2l}) = \sum\limits_{j=0}^{N-1} \lambda_j^{2l}$$

$$\mu_p^{(2l)}(1) = \frac{W_{2l}}{(2k)^{2l}}$$

where $N=|SL_2(\mathbb{Z}/p\mathbb{Z})|$, $k=|A|=$ the valency of the Cayley graph, $Adj$ is the adjacency matrix of the Cayley graph and $\lambda_0,\dots, \lambda_{N-1}$ are the eigenvalues of $Adj$. Recall that to prove that we have an expander family you have to show an eigenvalue gap between $\lambda_0$ and $\lambda_1$, so these identities connect the eigenvalues to the $2l$-fold convolution of measure $\mu_p$.

In particular the $L^2$-flattening lemma is used crucially to prove the following

Prop. For every $\epsilon >0$, there exists $C$ such that for $l\geq C\log_{2k}(p)$, $$\|\mu_p^{(l)}\|_2 < p^{-\frac32+\epsilon}.$$

Combining this with the identities above one obtains that $$\frac{W_{2l}}{(2k)^{2l}} = \mu_p^{(2l)}(1) = \|\mu_p^{(l)}\|_2^2 < p^{-3+2\epsilon}.$$

One closes out the argument by appealing to Frobenius' classical lower bound for the dimension of a non-trivial irreducible representation of $SL_2(\mathbb{Z}/p\mathbb{Z})$. We know that this dimension is at least $\frac12 (p-1)$, hence an easy argument shows that the multiplicity of all eigenvalues of $Adj$ is at least $\frac 12(p-1)$. One obtains immediately that $$\sum\limits_{j=0}^{N-1} \lambda_j^{2l} > \frac12(p-1)\lambda_1^{2l}.$$ Rearranging, and combining inequalities one obtains an upper bound for $\lambda_1$: $$\lambda_1^{2l} \leq 3\frac{(2k)^{2l}}{p^{1-2\epsilon}}.$$ Since $\lambda_0=k$, we have our eigenvalue gap, and the job is done. END OF PROOF SKETCH.

Final remarks: So the point of the $L^2$-flattening lemma, then, is that it allows us to prove the above proposition, a bound on convolutions which turns out to be enough to prove expansion. The idea that the $L^2$-flattening lemma implies the given proposition is, I hope, plausible just by the form of the statements.

What makes the $L^2$-flattening lemma so significant is that it turned out to be the right statement for connecting growth results to convolution bounds. BG's aim was to use Helfgott's growth results for the set $A_p$ in $SL_2(\mathbb{Z}/p\mathbb{Z})$ to prove expansion. One can then exploit the Balog-Szemeredi-Gowers result to derive a bound on the additive energy of $A_p$, or equivalently on the convolution of the measure $\mu_p$. This is the starting point for proving the $L^2$-flattening lemma.

Answer 2

Why this proposition is called "Flattening Lemma"? Is it because of the L2-norm of v∗v is smaller than the L2-norm of v?

Yes, I'd think so. If you have two probability distributions $w$ and $v$, and $w$ has smaller $\ell_2$ norm than $v$, then $w$ is "flatter" than $v$, intuitively speaking.

What is a motivation for this proposition?

If, starting from a measure $v$, you apply the proposition over and over again, you obtain that v*v*v*...*v is very flat, i.e., has very small $\ell_2$ norm. This is a weak form of "mixing", as in "mixing time". You can then deduce a stronger form of "mixing" (equivalent to the expansion property) from this by using the high multiplicity of non-trivial eigenvalues of $SL_2(\mathbb{Z}/p\mathbb{Z})$ (an idea that already occurs in this context in the work of Sarnak-Xue).

Incidentally, there is a simplified proof of the flattening lemma in Tao's notes (referred to below). As before, the main idea is to chop up the measure into chunks to reduce the lemma to, um, Helfgott's theorem on growth in $SL_2(\mathbb{Z}/p\mathbb{Z})$.

Answer 3

This lemma is one of the fundamental tools in the recent progress on proving that families of various Cayley graphs of finite groups are expanders. There is a detailed, well-motived, discussion on T. Tao's blog (search for "the Bourgain-Gamburd expansion machine").

Here is a very rough discussion: one motivation lies in seeing the measure $\nu$ as the distribution of the $k$-th step $X_k$ of a random walk on $SL_2(\mathbf{F}_p)$. Then $\nu\star \nu$ is the distribution of the $2k$-th step. The goal in this paper (and in the developpments of this technique) is to show that, after about $C\log p$ steps (where $C$ is a constant), the random walk is very close to being uniform. In these terms, the flattening lemma implies that if the $k$-th step of the walk is not already very uniformly distributed, then the $2k$-th step is significantly more uniform, unless the walk is too concentrated (in particular, unless it is concentrated on a proper subgroup). Hence, one sees that if one can find a good starting point after $c_1\log p$ steps that it not too concentrated, repeated applications of the lemma will give a very uniform distribution after $C\log p$ steps, where $C$ is a constant (depending on the $\epsilon(\gamma)$ in the lemma).