Esperantism expands, but not so quickly

Today, as it has been for a long time, it can only be a fantastic dream to know and understand all of mathematics, and virtuous mathematicians must perforce look for alternatives. One of the best is to find some analogy between different areas — a brilliant instance, being Vojta’s rapprochement between questions of diophantine approximation (e.g, Roth’s Theorem) and questions of Nevanlinna Theory. Another great satisfaction is to see surprising direct connections between two such areas: I still remember my surprise and delight on learning in a probability class how complex Brownian motion can be used to solve Partial Differential Equations (such as the Dirichlet problem, as shown by Kakutani).

A very new joint work with J. Ellenberg and C. Hall brought (at least to me!) some of these emotions. The barest summary would be as follows: we describe very strong connections between the combinatorial notion of expander graphs (or, more properly, expander families) and certain types of finiteness statements in arithmetic geometry. There is already a bit of magic here, but the result is even nicer in that the proof depends crucially on another unexpected connection with a result of differential geometry of Li and Yau.

I won’t describe the arithmetic geometry now (partly because Jordan has already written a very good summary…). Rather I want to explain what are the esperantist graphs that we introduce in the paper, and discuss some vague but enticing “philosophical” questions that this paper suggests.

Let us start with expanders (a very good place to start); it might be that, with the possible exception of root systems, this is the most amazingly ubiquitous notion of 20th Century Mathematics — amazing in the sense that the definition can look hyper-specialized, until its influence extends (pun intended), and one day you realize that what looked like a practical network-communication question is needed, for instance, to give counterexamples to some form of the Baum-Connes conjecture (about which I don’t know anything, except for what a superb talk by N. Higson taught me about ten years ago). I highly recommend downloading the long survey paper of Hoory, Linial and Wigderson to get an idea of the breadth and importance of this notion.

Now, there are different equivalent definitions of expanders, and I’ll use the least intuitive, for the simple reason that this is the one that comes in most naturally for our applications: given a sequence of graphs

(\Gamma_n)_{n\geq 1},

which we assume — for simplicity — to be connected and k-regular for a fixed k, one says that this sequence is an expander if (1) the number of vertices goes to infinity

\lim_{n\rightarrow +\infty} |\Gamma_n|=+\infty,

and (2) there is a uniform spectral gap δ>0 for all n:

\lambda_1(\Gamma_n)\geq \delta>0,

for all n, where λ1 is the first non-zero eigenvalue of the square matrix of size n| given by

\Delta_n=k-A(\Gamma_n),

in terms of the adjacency matrices of the graphs (this is known as the combinatorial Laplace operator; it is a non-negative symmetric matrix, with first eigenvalue equal to 0 with the constant eigenvector, which is unique up to scalar since the graph is assumed to be connected.)

As it turns out, for our application, one does not need such a strong condition as uniform spectral gap. Precisely, we say that the family above is an esperantist family if it satisfies

 \lambda_1(\Gamma_n)\geq c(\log 2|\Gamma_n|)^{-A}

for all n and some constants

(c,A),\quad\quad c>0,\quad\quad A\geq 0.

(Note: The factor 2 simply avoids ever talking of 1/0.) Thus expanders correspond to esperantist families where one can take A=0.

Now, the obvious question: why did we select this name? Mostly, it is a question of alliteration; and we feel it just sounds nice (like étale topology sounds nice, or barreled spaces, or adèles, etc…)

Then, scientifically, what does it mean, and why is it interesting? For us, the meaning is given in practice by a theorem of Diaconis and Saloff-Coste: if the family is a family of Cayley graphs for some finite groups Gn, with respect to systems of generators with constant size k, then they will form an esperantist family as soon as the diameter of the Cayley graphs grows polylogarithmically in the size of the groups, i.e., if there exists

(c,B),\quad\quad c>0,\quad B\geq 0,

such that

\mathrm{diam}(\Gamma_n)\leq c(\log 2|G_n|)^B.

And the fact is that showing this type of diameter growth is, at the moment, an indispensable staging point in all the recent developpments concerning growth and expansion in linear groups over finite fields, starting with the breakthrough by Helfgott (for SL(2,Fp). (For our purpose, the results of Pyber-Szabó are the most directly useful, because sometimes we do not control the groups well enough to claim, for instance, that they are given by G(Fp), where p varies, for a fixed algebraic group G; however, other papers with important results in this direction are one of Gill and Helfgott and one of Breuillard, Green and Tao.)

As a matter of fact (this has been confirmed to us by many people), it is almost certain that all the families we consider in our paper are, really, expanders, and very likely that this will be formally proved and published in the near future. But as long as the proofs of this require showing the esperanto property first, and require additional non-trivial steps (which is the case for the moment), our own applications seem to be more transparent when phrased in terms of esperantism. And there might of course be applications where the graphs do not form expanders (though we have not found one yet).

Now for the philosophy: the very barest summary of our main result is that, provided a family of finite (unramified) coverings

U_n\rightarrow U,

of a fixed algebraic curve over a number field has the property that the associated Cayley-Schreier graphs associated to the sets of cosets

\pi_1(U)/\pi_1(U_n),

form an esperantist family, then there are very strong diophantine restrictions on the points of the coverings defined over extensions of the base field of a fixed degree. (There is more information in Jordan’s post.) There is an unsuspected deus ex machina hidden, which makes the proof quite surprising: we use an inequality from global analysis of Li and Yau (already used by Abramovich in the setting of classical modular curves), which seems to come completely out of the blue.

This seems to suggest that the following general analogue problem might deserve attention: suppose you have some “objects” for which it makes sense to speak of finite coverings, and of Galois groups, etc, and you have a sequence of these (say ?n) with finite coset spaces

\mathrm{Gal}(?)/\mathrm{Gal}(?_n),

and some finite generating set of the base Galois group (or something similar). Can one say anything interesting on the “geometry” if one assumes that this family of graphs is esperantist (or expanding)?

Even the most natural analogues of our setting seem very interesting and quite tricky to think about:

(1) what about coverings of a base curve defined over a function field of positive characteristic (say, with tame ramification to avoid unpleasantness)? Here one would think that the direct analogue of our statements might hold, but the Li-Yau inequality evaporates, and we are left scratching our heads (though one might hope, maybe, that some p-adic analogue could be true?)

(2) what about coverings of higher-dimensional base varieties over a number field? Here, we do not even know yet what a reasonable consequence could look like…


[Note: our results also depend on the comparison between hyperbolic and discrete laplace eigenvalues, specifically on the results of Burger in this direction, which are somewhat sharper than those of Brooks; since Burger’s method is described only sketchily in his papers, and his thesis — which contains the full details — is hard to find, we included the proof of the comparison we require as an Appendix to our paper, in the case of surfaces with finite hyperbolic area. This might be of some interest to some readers.]

Published by

Kowalski

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

4 thoughts on “Esperantism expands, but not so quickly”

  1. Bonege! Gratulojn!

    Chu vi (aux iu ajn el via legantoj) scias chu la implikacio (polilogaritma diametro -> esperantismo) validas ne nur por la grafoj de Cayley, sed ankau por la grafoj Cayley-Schreier?

    (La implikacio alidirekta funkcias por chiu grafo de grado barita.)

    PS. Demande de l’aide a Jordan si tu as encore des limitations linguistiques nationales.

  2. Emmanuel,

    One silly question to go on langage issues. How do you translate <esperantist family> in French?

    Guillaume.

  3. OK, I’ll attempt a translation of Harald’s question:

    “Do you know […] if the implication (polylogarithmic diameter –> esperantism) is valid not only for Cayley graphs, but also for Cayley-Schreier graphs?”

    To which the answer is that I don’t know at the moment, though this seems very reasonable.

    [Amplification added later] Note that in our paper, we do need to get the esperantist property for Cayley-Schreier graphs. However, all our families can be described as quotients

    G_n/H_n

    of a family of finite groups by a family of subgroups. This works in our case because

    \lambda_1(G_n/H_n)\geq \lambda_1(G_n),

    (eigenfunctions of the quotient give eigenfunctions on the group by composition with the quotient map) and the subgroups Hn that we use happen to have “large” index, precisely

    \log [G_n:H_n] \gg \log |G_n|,

    which ensures that the esperantist property for the Cayley graphs of the Gn gives the esperantist property for the quotients.

Leave a Reply to Harald Cancel reply

Your email address will not be published. Required fields are marked *