Tag Archives: spectral gap

Superstrong approximation for monodromy groups (and Galois groups?)

Hey, I posted a paper to the arXiv and forgot to blog about it!  The paper is called “Superstrong approximation for monodromy groups” and it roughly represents the lectures I gave at the MSRI workshop last February on “Thin Groups and Superstrong Approximation.”  Hey, as I write this I see that MSRI has put video of these lectures online:

But the survey paper has more idle speculation in it than the lectures, and fewer “um”s, so I recommend text over video in this case!  I mean, if you like idle speculation.  But if you don’t, would you be reading this blog?

I’m going to recount one of the idle speculations here, but first:

What is superstrong approximation?

Let’s say you have a graph on N vertices, regular of degree d.  One basic thing you want to know about the graph is what the connected components are, or at least how many there are.  That seems like a combinatorial question, and it is, but in a sense it is also a spectral question:  the random walk on the graph, thought of as an operator T on the space of functions on the graph, is going to have eigenvalues between [1,-1], and the mutiplicity of 1 is precisely the number of components; the eigenspace consists of the locally constant functions which are constant on connected components. 

So being connected means that the second-largest eigenvalue of T is strictly less than 1.  And so you might say a graph is superconnected (with respect to some positive constant x) if the second-largest eigenvalue is at most 1-x.  But we don’t say “superconnected” because we already have a word for this notion; we say the graph has a spectral gap of size x.  Now of course any connected graph has a spectral gap!  But the point is always to talk about families of graphs, typically with d fixed and N growing; we say the family has a spectral gap if, for some positive x, each graph in the family has a spectral gap of size at least x.  (Such a family is also called an expander family, because the random walks on those graphs tend to bust out of any fixed-size region very quickly; the relation between this point of view and the spectral one would be a whole nother post.)

When does life hand you a family of graphs?  OK, here’s the situation — let’s say you’ve got d matrices in SL_n(Z), or some other arithmetic group.  For every prime p, your matrices project to d elements in SL_n(Z/pZ), which produce a Cayley graph X_p, and X_p is connected just when those elements generate SL_n(Z/pZ).  If your original matrices generate SL_n(Z), their reductions mod p generate SL_n(Z/pZ); this is just the (not totally obvious!) fact that SL_n(Z) surjects onto SL_n(Z/pZ).  But more is true; it turns out that if the group Gamma generated by your matrices is Zariski-dense in SL_n, this is already enough to guarantee that X_p is connected for almost all p.  This statement is called strong approximation for Gamma.

But why stop there — we can ask not only whether X_p is connected, but whether it is superconnected!  That is:  does the family of graphs X_p have a spectral gap?  If so, we say Gamma has superstrong approximation, which is now seen to be a kind of quantitative strengthening of strong approximation.

We know much more than we did five years ago about which groups have superstrong approximation, and what the applications are when this is so.  Sarnak’s paper  from the same conference provides a good overview.

Idle speculation:  superstrong approximation for Galois groups

Another way to express superstrong approximation is to say that Gamma has property tau with respect to the congruence quotients SL_n(Z/pZ).

In the survey paper, I wonder whether there is some way to talk about superstrong approximation for Galois groups with bounded ramification.  For instance; let G be the Galois group of the maximal extension of Q which is tamely ramified everywhere, and unramified away from 2,3,5, and 7.  OK, that’s some profinite group.  I don’t know much about it.  By Golod-Shafarevich I could prove it was infinite, unless I couldn’t, in which case I would toss in some more ramified primes until I could.

We could ask something like the following.  Given any finite quotient Q of G, and any two elements of G whose images generated Q, we get a connected Cayley graph of degree 4 on the elements of Q, by means of those two elements and their inverses.  Is there a uniform spectral gap for all those graphs?

I have no real reason to think so.  But remark:  this would imply immediately that every finite-index subgroup of G has finite abelianization, and that’s true.  It would also imply that there are only finitely many n such that G surjects onto S_n, and that might be true.  Reader survey for those who’ve read this far:  do you think there’s a finite set S of primes such that there are tamely ramified S_n-extensions of Q, for n arbitrarily large, unramified outside S?

Acknowledgment:  I was much aided in formulating this question by the comments on the MathOverflow question I asked about it.

Tagged , , , , , ,

Idle question: cluster algebras over finite fields and spectral gaps

Yet another great talk at the JMM:  Lauren Williams gave an introduction to cluster algebras in the Current Events section which was perfect for people, like me, who didn’t know the definition.  (The talks by Wei Ho, Sam Payne, and Mladen Bestvina were equally good, but I don’t have any idle questions about them!)

This post will be too long if I try to include the definitions myself, and I wouldn’t do as good a job of exposition as Williams did, so it’s good news that she’s arXived a survey paper which covers roughly the same ground as her talk.

Setup for idle question:  you can get a cluster algebra comes from a process called “seed mutation” — given a rational function field K = k(x_1, … x_m), a labelled seed is a pair (Q,f) where Q is a quiver on m vertices and f = (f_1, … f_m) is a labelling of the vertices of Q with rational functions in K.  For each i, there’s a seed mutation mu_i which is an involution on the labelled seeds; see Williams’s paper for the definition.

Now start with a labelled seed (Q,(x_1, … x_m)) and let T be the set of labelled seeds obtainable from the starting seed by repeated application of seed mutations mu_1, …. m_n for some n < m.  (I didn’t think carefully about the meaning of this special subset of n vertices, which are called the mutable vertices.)

It’s called T because it’s a tree, regular of degree n; each vertex is indexed by a word in the n seed mutations with no letter appearing twice in succession.

Anyway, for each vertex of T and each mutable vertex i you have a rational function f_i.  The cluster algebra is the algebra generated by all these rational functions.

The great miracle — rather, one of the great miracles — is that, by a theorem of Fomin and Zelevinsky, the f_i are all Laurent; that is, their denominators are just monomials in the original functions x_i.

We are now ready for the idle question!

Let’s take k to be a finite field F_q, and let U be (F_q^*)^m, the rational points of the m-torus over F_q.  Choose a point u = (u_1, … u_n) in (F_q^*)^m.

Then for any vertex of T, we can (thanks to the Laurent condition!) evaluate the functions (f_1, …. f_m) at u, getting an element of F_q^m.

So a random walk on the tree T, combined with evaluation at u, gives you a random walk on F_q^m.

Idle question:  Is there a spectral gap for this family of walks, independent of q?

Update:  As David Speyer explains in the comments, this finite random walk is not in general well-defined.  Let me try another phrasing which I think makes sense.

Let t be the endpoint of a length-R random walk on T; then evaluation at (1,1,..1) gives a probability distribution P_{R,N} on (Z/NZ)^m.  Let U_N be the uniform distribution on (Z/NZ)^m.  Now for each N we can ask about the limit

\Lambda_N = \lim_{R \rightarrow \infty} ||P_{R,N} - U_{N}||^{1/R}

(I don’t think it matters what norm we use.)

The idea is that the random walk on the tree should be equidistributing mod N, and the speed of convergence is governed by Λ_N.  Then we can ask

Idle question mark 2:  Is Λ_N bounded away from 1 by a constant independent of N?

This is a question in “spectral gap” style, which, if I did it right, doesn’t a priori have to do with a sequence of finite graphs.

Motivation:  this setup reminds me of a very well-known story in arithmetic groups; you have a discrete group Gamma which comes equipped with an action on an set of objects “over Z” — then reducing mod p for all p gives you a family of actions of Gamma on larger and larger finite sets, and a critical organizing question is:  do the corresponding graphs have a spectral gap?

For that matter, what happens if you, say, keep k = C and then evaluate your f_i at (1,1,… 1)?  Looking at a bigger and bigger ball in the tree you get bigger and bigger sets of elements of C^m; what do these look like?  Do they shoot off to infinity, accumulate, equidistribute…..?


Tagged , , , , , ,

Expander graphs, gonality, and variation of Galois representations

New paper on the arXiv with Chris Hall and Emmanuel Kowalski.

Suppose you have a 1-dimensional family of polarized abelian varieties — or, just to make things concrete, an abelian variety A over Q(t) with no isotrivial factor.

You might have some intuition that abelian varieties over Q don’t usually have rational p-torsion points — to make this precise you might ask that A_t[p](Q) be empty for “most” t.

In fact, we prove (among other results of a similar flavor) the following strong version of this statement.  Let d be an integer, K a number field, and A/K(t) an abelian variety.  Then there is a constant p(A,d) such that, for each prime p > p(A,d), there are only finitely many t such that A_t[p] has a point over a degree-d extension of K.

The idea is to study the geometry of the curve U_p parametrizing pairs (t,S) where S is a p-torsion point of A_t.  This curve is a finite cover of the projective line; if you can show it has genus bigger than 1, then you know U_p has only finitely many K-rational points, by Faltings’ theorem.

But we want more — we want to know that U_p has only finitely many points over degree-d extensions of K.  This can fail even for high-genus curves:  for instance, the curve

C:   y^2 = x^100000 + x + 1

has really massive genus, but choosing any rational value of x yields a point on C defined over a quadratic extension of Q.  The problem is that C is hyperelliptic — it has a degree-2 map to the projective line.  More generally, if U_p has a degree-d map to P^1,  then U_p has lots of points over degree-d extensions of K.  In fact, Faltings’ theorem can be leveraged to show that a kind of converse is true.

So the relevant task is to show that U_p admits no map to P^1 of degree less than d; in other words, its gonality is at least d.

Now how do you show a curve has large gonality?  Unlike genus, gonality isn’t a topological invariant; somehow you really have to use the geometry of the curve.  The technique that works here is one we learned from an paper of Abramovich; via a theorem of Li and Yau, you can show that the gonality of U_p is big if you can show that the Laplacian operator on the Riemann surface U_p(C) has a spectral gap.  (Abramovich uses this technique to prove the g=1 version of our theorem:  the gonality of classical modular curves increases with the level.)

We get a grip on this Laplacian by approximating it with something discrete.  Namely:  if U is the open subvariety of P^1 over which A has good reduction, then U_p(C) is an unramified cover of U(C), and can be identified with a finite-index subgroup H_p of the fundamental group G = pi_1(U(C)), which is just a free group on finitely many generators g_1, … g_n.  From this data you can cook up a Cayley-Schreier graph, whose vertices are cosets of H_p in G, and whose edges connect g H with g_i g H.  Thanks to work of Burger, we know that this graph is a good “combinatorial model” of U_p(C); in particular, the Laplacian of U_p(C) has a spectral gap if and only if the adjacency matrix of this Cayley-Schreier graph does.

At this point, we have reduced to a spectral problem having to do with special subgroups of free groups.  And if it were 2009, we would be completely stuck.  But it’s 2010!  And we have at hand a whole spray of brand-new results thanks to Helfgott, Gill, Pyber, Szabo, Breuillard, Green, Tao, and others, which guarantee precisely that Cayley-Schreier graphs of this kind, (corresponding to finite covers of U(C) whose Galois closure has Galois group a perfect linear group over a finite field) have spectral gap; that is, they are expander graphs. (Actually, a slightly weaker condition than spectral gap, which we call esperantism, is all we need.)

Sometimes you think about a problem at just the right time.  We would never have guessed that the burst of progress in sum-product estimates in linear groups would make this the right time to think about Galois representations in 1-dimensional families of abelian varieties, but so it turned out to be.  Our good luck.

Tagged , , , , , , , , , , , ,

Get every new post delivered to your Inbox.

Join 320 other followers

%d bloggers like this: