Explicit multiplicative combinatorics

One of the goals of my course on expanders is to (try to) get an explicit spectral gap for the Cayley graphs of \mathrm{SL}_2(\mathbf{F}_p), for p prime, with respect to the generating set
S_p=\{u,u^{-1}, v,v^{-1}\}
u=\begin{pmatrix} 1& 3\\ 0&1\end{pmatrix},\quad\quad v=\begin{pmatrix} 1&0\\3&1\end{pmatrix}
(which corresponds to the reduction modulo p of the Cayley graph of the “Lubotzky group” L, generated in \mathrm{SL}_2(\mathbf{Z}) by the “same” matrices.)

The first thing to do in order to obtain an explicit estimate is to get an explicit form of the relation between “pairs of sets with large multiplicative energy” and “cosets of a common approximate group” — indeed, this is a crucial point in the first step of the argument discovered by Bourgain and Gamburd to derive expansion for some Cayley graphs from a classification of approximate subgroups (or more directly, of sets with “small tripling”, a classification which had been produced by Helfgott for \mathrm{SL}_2(\mathbf{F}_p)).

To explain this, recall that if A, B\subset G are subsets of a finite group G, the normalized multiplicative energy e(A,B) is defined by
e(A,B)=|\{(x_1,y_1,x_2,y_2)\in A^2\times B^2\,\mid\, x_1y_1=x_2y_2\}|/(|A||B|)^{3/2}.
It is easy to show that e(A,B)\leq 1, and it is a pleasant exercise to prove that the extreme case e(A,B)=1 occurs if and only if there exists a subgroup H of G and elements x, y of G such that
A=xH,\quad\quad B=Hy.

The Bourgain-Gamburd argument depends on understanding sets A and B such that
e(A,B)\geq |G|^{-\varepsilon}
for some (small) \varepsilon>0.
This can now be done, in some cases, by first proving an “approximate” version of the characterization of the extreme e(A,B)=1, and then classifying the resulting “approximate” objects. The second step is much more involved, and I won’t talk about it here, but the first can be done in full generality. The standard texts explaining this are the book of Tao and Vu and a paper of Tao (which contains more details than the summary in the book.)

It is clear from reading the proofs that they are “effective”, but these sources do not give explicit inequalities. So I did the exercise of going through the arguments to get actual constants, inputing the recent explicit results of Petridis to get better control on product sets than the corresponding argument in Tao’s paper. After three or four rounds of checks, I get the following: if
e(A,B)\geq \frac{1}{\alpha},
then there exist a \beta-approximate subgroup H of G and elements x, y\in G,
such that
|H|\leq \beta_2|A|,\quad\quad |A\cap xH|\geq \beta_1^{-1}|A|,\quad\quad |B\cap Hy|\geq \beta_1^{-1}|B|,
\beta\leq 2^{14257}\alpha^{6330},\quad\quad \beta_1\leq 2^{14667}\alpha^{6553},\quad\quad \beta_2\leq 2^{283}\alpha^{126},
(and a \beta-approximate subgroup is defined to be a symmetric subset, containing the identity, such that H\cdot H\subset X\cdot H for some subset of size |X|\leq \beta.)

For the moment, I’ve only typed a very condensed note spelling this out, which is found on my page of unpublished notes; I admit that I had some fun devising an arrow notation to simplify keeping track of the relation and sizes between the sets involved…

All this will be incorporated in my lectures notes on expanders, and then expanded later to a full proof so that the latter are self-contained. I will also attempt to improve these constants, which are not very promising when I think of what the spectral gap will become in the end…

Published by


I am a professor of mathematics at ETH Zürich since 2008.

2 thoughts on “Explicit multiplicative combinatorics”

  1. So, you are just asking for good constants in the noncommutative Balog-Szemeredi-Gowers theorem, right? Or am I missing something?

    1. The Balog-Szemerédi-Gowers theorem is actually one for which there are already fully explicit, and quite good, bounds in the literature, e.g. in Tao-Vu, following Sudakov-Szemerédi-Vu. The constants degrade in the later steps (at least when following the standard proof…), when one wants to extract an approximate group (or set with explicit tripling constant, though one can see from the argument that the tripling constant is actually better than what follows from what I wrote and the definition of approximate group.)

Comments are closed.