ETH – Page 7 – E. Kowalski's blog

Journals

Two cents on the current journal/Elsevier controversy: this recent article in the ETH online magazine indicates that commercial publishers are suing ETH for providing a scanning service, where researchers in Switzerland (members of one of the libraries belonging to the Nebis consortium) are able to ask that the ETH library scan and send them by email any article available in the library (sometimes for a fee; this service is highly convenient to access articles not available online because the stacks of the main library at ETH are not accessible to its users.)

Note that Springer and Elsevier are both explicitly mentioned as two of the plaintiffs in that case.

Self-improvements

I’m currently profiting from the vacations to clean-up various aspects of my tentative to obtain explicit expansion bounds for subgroups of $\mathrm{SL}_2(\mathbf{Z})$ which are Zariski dense in $\mathrm{SL}_2$ . To review the previous episodes, there are three basic ingredients that needed to be made explicit:

basic multiplicative combinatorics;
Helfgott’s growth theorem;
the Bourgain-Gamburd expansion criterion (especially the so-called “ $L^2$ -flattening” lemma).

I’ve already talked about the first and second. For the growth theorem, after a few more changes, my current result is that any generating subset $H$ of $G=\mathrm{SL}_2(\mathbf{F}_p)$ satisfies either $H\cdot H\cdot H=G$ or
$|H\cdot H\cdot H|\geq |H|^{1+1/1344},$
(with no condition on $p$ ).

For multiplicative combinatorics, I have reworked the argument after noticing the fact (certainly obvious to all cognoscenti) that, for the purpose I need it, one can work mainly with symmetric sets, for which the basic relation between tripling constant and growth of $n$ -fold product sets is quite a bit better (in explicit terms) than the corresponding one of “mixed” $n$ -fold products involving either a set or its inverse. This gives much better exponents.

The most important gain comes, however, from a second look at the Bourgain-Gamburd inequality. The point is that they argue from a “dyadic” viewpoint, considering (in effect) the steps $X_{2^jk}$ of a random walk (for a suitable starting point $k$ where the walk has started to expand non-trivially). Each step from $j$ to $j+1$ gives a fixed improvement of the counting of closed geodesics of the corresponding length, and the number of steps which is required is directly related to the spectral gap one obtains.

From a qualitative point of view, there is nothing to argue with this. But if one wants to get explicit constants, one notices (this is also certainly known to the aforementioned cognoscenti, as shown by Helfgott’s comment on my previous post…) that the argument of Bourgain-Gamburd works essentially just as well for steps $2jk$ of the random walk: what is needed is a small adaptation of their main inequality to bound the spread of products $X_1X_2$ where $X_1$ and $X_2$ are independent random variables with $X_2$ at least “as well spread out” as $X_1$ .

Apart from this last part, which I will include soon since I just wrote down the details, I’ve incorporated these improvements in my notes. The last point, rather satisfyingly, improves exponentially the estimates for spectral gaps: for the Lubotzky group, it becomes now $2^{-38}$ , instead of $2^{-2^{36}}$ (for $p$ large enough, and I confess that I don’t yet know what this last condition means explicitly…)

We’re not yet in the realm of really macroscopic numbers, but this is certainly encouraging…

Explicit growth for generating subsets of SL_2 over finite fields

I have one more lecture next week in my expander class, but today I finished the proof of Helfgott’s growth theorem for $\mathrm{SL}_2(\mathbf{F}_p)$ . As I had hoped, I did this in my notes with explicit constants (I didn’t try to follow those constants on the blackboard).

Taking into account some grains de sel, since there may well be minor computational mistakes lurking around (though I have already corrected a few), the result I obtain is the following: if $p\geq 7$ is prime, and if $H\subset \mathrm{SL}_2(\mathbf{F}_p)$ is a symmetric generating set, containing $1$ for simplicity, then either the triple product
$H^{(3)}=\{xyz\,\mid\, x,y,z\in H\}$
is all of $\mathrm{SL}_2(\mathbf{F}_p)$ , or otherwise we have
$|H^{(3)}|\geq \frac{1}{2}|H|^{1+\delta}$
where
$\delta=\frac{1}{186}=0.0053763440860215053763440860215053763441\ldots$

(Of course, the factor $1/2$ can be incorporated into a slightly-smaller exponent, but that introduces an ugly-looking dependency on the size of $H$ , which one must recover using an uglier trivial bound for $|H|$ small, so I preferred this version…)

The current version of the notes contains the argument, though it is a bit rough (I will soon rearrange some of it, to attempt to provide more motivation — at least the way I understand how it goes…)

For the proof, I followed the clear outline in the first sections of the paper of Pyber and Szabó. This reduces the problem, rather quickly and cleanly, to a “non-concentration” estimate for the intersection of $H$ with a regular-semisimple conjugacy class $C$ , of the type
$|C\cap H|\leq c|H^{(k)}|^{2/3}$
for some fixed $k$ and absolute constant $c$ . This inequality is now commonly called a (generalized) Larsen-Pink inequality (the prototype going back to the late 90’s preprint — now published — of Larsen and Pink for the non-concentration of finite subgroups of algebraic groups in subvarieties). Though the general case is quite tricky, there is here an easy enough argument, based on studying the fibers of the map
$(x_1,x_2,x_3)\mapsto (x_1x_2,x_1x_3)$
where the three arguments $x_i$ are all in $C$ (this is the basic idea already presented by Larsen and Pink to explain their result, in another case).

It turns out that, if one imposes that $C$ is not the conjugacy class of elements of trace 0, which can be ensured (using bare hands) by “escape from subvarieties”, the cases where this map has positive-dimensional fibers are rather simple to analyze (I owe this computation to R. Pink…)

Moreover, only one case requires another instance of Larsen-Pink-type inequalities (those readers who have looked at the paper of Larsen and Pink, or the one of Breuillard-Green-Tao which has a general “approximate” version, will know that there is a rather complicated induction involved in general), and it is a very easy one: if $U$ is the subgroup of upper-triangular unipotent matrices, then
$|U\cap H|\leq 1+|H^{(5)}|^{1/3}\leq 2|H^{(5)}|^{1/3},$
which is an instructive exercise. (In fact, in rearranging this section of my notes, I will use this as a motivating example…)

With this final ingredient, I can now produce (with the same amount of salt…) an effective spectral gap for the Cayley graphs of the Lubotzky subgroup of $\mathrm{SL}_2(\mathbf{Z})$ , generated by
$u=\begin{pmatrix} 1& 3\\ 0&1\end{pmatrix},\quad\quad v=\begin{pmatrix} 1&0\\3&1\end{pmatrix},$
modulo primes, namely (drumroll) for $p$ large enough (drumroll; but I won’t tell you how large today), we have (drumroll)
$\lambda_1(\Gamma_p)\geq 2^{-2^{34}}.$

(Actually, I already know various points of inefficiency in my treatment of the Bourgain-Gamburd expansion argument which should lead to some improvements, and I hope to find other avenues to explore and stones to turn to do better…)

Trevisan’s L^1-style Cheeger inequality

My expander class at ETH continues, and for the moment the course notes are kept updated (and in fact I have some more in the notes than I did in class).

Last week, I presented the inequalities relating the definition of expanders based on the expansion ratio with the “spectral” definition. In fact, I used the random walk definition first, which is only very slightly different for general families of graphs (with bounded valency), and is entirely equivalent for regular graphs. For a connected $k$ -regular graph $\Gamma$ , the inequalities state that
$\frac{2}{k}\lambda_1(\Gamma)\leq h(\Gamma)\leq k\sqrt{2\lambda_1(\Gamma)},$
where:

$\lambda_1(\Gamma)$ is the smallest non-zero eigenvalue of the normalized Laplace operator $\Delta$ , i.e., the operator acting on functions on the vertex set by
$\Delta\varphi(x)=\varphi(x)-\frac{1}{k}\sum_{y\text{ adjacent to x}}{\varphi(y)}$ .
$h(\Gamma)$ is the expansion ratio of $\Gamma$ , given by $h(\Gamma)=\min_{1\leq |W|\leq |\Gamma|/2}\frac{|E(W)|}{|W|},$ the set $E(W)$ in the numerator being the set of edges in $\Gamma$ with one extremity in $W$ and one outside.

The left-hand inequality is rather simple, once one knows (or notices) the variational characterization
$\lambda_1(\Gamma)=\min_{\varphi\perp 1}\frac{\langle \Delta\varphi,\varphi\rangle}{\|\varphi\|^2}$
of the spectral gap: basically, for a characteristic function $\varphi$ of a set $W$ of vertices, the right-hand side of this expression reduces (almost) to the corresponding ratio $|E(W)|/|W|$ . The second inequality, which is called the discrete Cheeger inequality, is rather more subtle.

The proof I presented is the one presented by L. Trevisan in his recent lectures on expanders (see, specifically, Lecture 4). Here, the idea is to construct a test set for $h(\Gamma)$ of the form
$W_t=\{x\in V_{\Gamma}\,\mid\, \varphi(x)\leq t\},$
for a suitable real-valued function $\varphi$ on the group. The only minor difference is that, in order to motivate the distribution of a random “threshold” $t$ that Trevisan uses to construct those test sets, I first stated a general lemma where the threshold is picked according to a fairly general probability measure. Then I first showed what happens for a uniform choice in this interval, to motivate the “better” one that leads to Cheeger’s inequality.

As it turns out, I just found an older blog post of Trevisan explaining his proof, where he also discusses first the computations based on the uniform measure supported on $[\min \varphi,\max\varphi]$ , and explains why it is problematic.

But there is some good in this inequality. First, the precise form it takes (which I didn’t find elsewhere, and will therefore name Trevisan’s inequality) is
$h(\Gamma)\leq \frac{A}{B}$
where, for any non-constant real-valued function $\varphi$ with minimum $a$ , maximum $b$ and median $t_0$ , we have
$A=\frac{1}{2}\sum_{x,y\in V}{a(x,y)|\varphi(x)-\varphi(y)|},$
(where $a(x,y)$ is the number of edges between $x$ and $y$ ) and
$B=\sum_{x\in V}{|\varphi(x)-t_0|}.$

The interesting fact is that this can be sharper than Cheeger’s inequality. Indeed, this happens at least for the family of graphs $\Gamma_n$ which are the Cayley graphs of $\mathfrak{S}_n$ with respect to the generating set
$S_n=\{(1\ 2),(1\ 2\ \cdots\ n)^{\pm 1}\}.$
From an analysis of the random walks by Diaconis and Saloff-Coste (see Example 1 in Section 3 of their paper), it is known that
$\lambda_1(\Gamma_n)\asymp \frac{1}{n^3},$
and Cheeger’s inequality leads to
$h(\Gamma_n)\ll n^{-3/2}.$
However (unless I completely messed up my computations…), one sees that the test function used by Diaconis and Saloff-Coste, namely the cyclic distance between $\sigma^{-1}(1)$ and $\sigma^{-1}(2)$ , satisfies
$\frac{A}{B}\ll \frac{1}{n^2},$
and therefore we get a better upper-bound
$h(\Gamma)\ll \frac{1}{n^2}$
using Trevisan’s inequality.

(Incidentally, we see here an easy example of a sequence of graphs which forms an esperantist family, but is not an expander.)

Action graphs

The beginning of my lecture notes on expander graphs is now available. These first sections are really elementary. If it were not grossly insulting to the noble brotherhood (and sisterhood) of bookkeepers, I would say that I deal here mostly with bookkeeping: setting up a rigorous “coding” of the class of graphs I want to consider (which are unoriented graphs where multiple edges are allowed as well as loops), defining maps between such graphs, and setting up the basic examples of Cayley graphs and Schreier graphs.

But still, I managed to trip once on the last point, and my first definition turned out to be rather bad. Of course, it is not that I don’t know what a Schreier graph is supposed to be, but rather that I stumbled when expressing properly this intuition in the specific “category” I am using (where a graph is a triple $(V,E,e)$ , with vertex set $V$ , edge set $E$ , and
$e\,:\, E\rightarrow \{\text{subsets of } V\text{ with } 1 \text{ or } 2\text{ elements}\}$
is the “endpoints” map.)

What I knew about the Schreier graph of a group $G$ with respect to a subgroup $H$ and a (symmetric) generating set $S$ is that it should be $|S|$ -regular, and the combinatorial Laplace operator $\Delta$ should be given by
$\Delta\varphi(x)=\varphi(x)-\frac{1}{|S|}\sum_{s\in S}{\varphi(sx)},$
for any function $\varphi$ on $G/H$ . This I managed to ensure on the second try, though the definition is a bit more complicated than I would like.

I actually wrote things down for more general “action graphs”, which are pretty much the obvious thing: given an action of the group $G$ on a set $X$ , one takes $X$ as vertices, and moves along edges (set up properly) from $x$ to $s\cdot x$ for $s$ in the given subset $S$ of $G$ . Here is a query concerning this: do these general graphs have a standard name? I have not seem the definition in this generality before, but it seems very natural and should be something well-known, hence named. (Of course, using decomposition in orbits, such a graph is a disjoint union of Schreier graphs modulo stabilizers of certain points of $X$ , but that doesn’t make it less natural.)

In any case, here is an illustration of the action graph for the symmetric group $S_5$ , with generators $S=\{(1\ 2), (1\ 2\ 3\ 4\ 5), (1\ 5\ 4\ 3\ 2)\}$ , acting on $X=\{1,2,3,4,5\}$ by evaluation:

Equivalently, this is the Schreier graph of $G/H$ with respect to $S$ , where $H$ is the stabilizer of $1$ .

As it should be, this graph is $3$ -regular, and this property would fail if loops and multiple edges were not permitted. It is true that, in that case, the resulting graph (a cycle of length $5$ ) would remain regular after removing loops and multiple edges, but the interested reader will have no problem checking that if $S$ is replaced by
$S'=S\cup\{(1\ 2\ 3), (1\ 3\ 2)\},$
removing loops and multiple edges from the corresponding action graph leads to a non-regular graph. (The vertex 1 has three neighbors then, namely $\{2, 3, 5\}$ , while the others have only 2.)

(The typesetting of the graph is done using the tkz-graph package already mentioned in my previous post.)