Tag Archives: expanders

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 , , , , , ,

Gonality, the Bogomolov property, and Habegger’s theorem on Q(E^tors)

I promised to say a little more about why I think the result of Habegger’s recent paper, ” Small Height and Infinite Non-Abelian Extensions,” is so cool.

First of all:  we say an algebraic extension K of Q has the Bogomolov property if there is no infinite sequence of non-torsion elements x in K^* whose absolute logarithmic height tends to 0.  Equivalently, 0 is isolated in the set of absolute heights in K^*.  Finite extensions of Q evidently have the Bogomolov property (henceforth:  (B)) but for infinite extensions the question is much subtler.  Certainly \bar{\mathbf{Q}} itself doesn’t have (B):  consider the sequence 2^{1/2}, 2^{1/3}, 2^{1/4}, \ldots  On the other hand, the maximal abelian extension of Q is known to have (B) (Amoroso-Dvornicich) , as is any extension which is totally split at some fixed place p (Schinzel for the real prime, Bombieri-Zannier for the other primes.)

Habegger has proved that, when E is an elliptic curve over Q, the field Q(E^tors) obtained by adjoining all torsion points of E has the Bogomolov property.

What does this have to do with gonality, and with my paper with Chris Hall and Emmanuel Kowalski from last year?

Suppose we ask about the Bogomolov property for extensions of a more general field F?  Well, F had better admit a notion of absolute Weil height.  This is certainly OK when F is a global field, like the function field of a curve over a finite field k; but in fact it’s fine for the function field of a complex curve as well.  So let’s take that view; in fact, for simplicity, let’s take F to be C(t).

What does it mean for an algebraic extension F’ of F to have the Bogomolov property?  It means that there is a constant c such that, for every finite subextension L of F and every non-constant function x in L^*, the absolute logarithmic height of x is at least c.

Now L is the function field of some complex algebraic curve C, a finite cover of P^1.  And a non-constant function x in L^* can be thought of as a nonzero principal divisor.  The logarithmic height, in this context, is just the number of zeroes of x — or, if you like, the number of poles of x — or, if you like, the degree of x, thought of as a morphism from C to the projective line.  (Not necessarily the projective line of which C is a cover — a new projective line!)  In the number field context, it was pretty easy to see that the log height of non-torsion elements of L^* was bounded away from 0.  That’s true here, too, even more easily — a non-constant map from C to P^1 has degree at least 1!

There’s one convenient difference between the geometric case and the number field case.  The lowest log height of a non-torsion element of L^* — that is, the least degree of a non-constant map from C to P^1 — already has a name.  It’s called the gonality of C.  For the Bogomolov property, the relevant number isn’t the log height, but the absolute log height, which is to say the gonality divided by [L:F].

So the Bogomolov property for F’ — what we might call the geometric Bogomolov property — says the following.  We think of F’ as a family of finite covers C / P^1.  Then

(GB)  There is a constant c such that the gonality of C is at least c deg(C/P^1), for every cover C in the family.

What kinds of families of covers are geometrically Bogomolov?  As in the number field case, you can certainly find some families that fail the test — for instance, gonality is bounded above in terms of genus, so any family of curves C with growing degree over P^1 but bounded genus will do the trick.

On the other hand, the family of modular curves over X(1) is geometrically Bogomolov; this was proved (independently) by Abramovich and Zograf.  This is a gigantic and elegant generalization of Ogg’s old theorem that only finitely many modular curves are hyperelliptic (i.e. only finitely many have gonality 2.)

At this point we have actually more or less proved the geometric version of Habegger’s theorem!  Here’s the idea.  Take F = C(t) and let E/F be an elliptic curve; then to prove that F(E(torsion)) has (GB), we need to give a lower bound for the curve C_N obtained by adjoining an N-torsion point to F.  (I am slightly punting on the issue of being careful about other fields contained in F(E(torsion)), but I don’t think this matters.)  But C_N admits a dominant map to X_1(N); gonality goes down in dominant maps, so the Abramovich-Zograf bound on the gonality of X_1(N) provides a lower bound for the gonality of C_N, and it turns out that this gives exactly the bound required.

What Chris, Emmanuel and I proved is that (GB) is true in much greater generality — in fact (using recent results of Golsefidy and Varju that slightly postdate our paper) it holds for any extension of C(t) whose Galois group is a perfect Lie group with Z_p or Zhat coefficients and which is ramified at finitely many places; not just the extension obtained by adjoining torsion of an elliptic curve, for instance, but the one you get from the torsion of an abelian variety of arbitrary dimension, or for that matter any other motive with sufficiently interesting Mumford-Tate group.

Question:   Is Habegger’s theorem true in this generality?  For instance, if A/Q is an abelian variety, does Q(A(tors)) have the Bogomolov property?

Question:  Is there any invariant of a number field which plays the role in the arithmetic setting that “spectral gap of the Laplacian” plays for a complex algebraic curve?

A word about Habegger’s proof.  We know that number fields are a lot more like F_q(t) than they are like C(t).  And the analogue of the Abramovich-Zograf bound for modular curves over F_q is known as well, by a theorem of Poonen.  The argument is not at all like that of Abramovich and Zograf, which rests on analysis in the end.  Rather, Poonen observes that modular curves in characteristic p have lots of supersingular points, because the square of Frobenius acts as a scalar on the l-torsion in the supersingular case.  But having a lot of points gives you a lower bound on gonality!  A curve with a degree d map to P^1 has at most d(q+1) points, just because the preimage of each of the q+1 points of P^1(q) has size at most d.  (You just never get too old or too sophisticated to whip out the Pigeonhole Principle at an opportune moment….)

Now I haven’t studied Habegger’s argument in detail yet, but look what you find right in the introduction:

The non-Archimedean estimate is done at places above an auxiliary prime number p where E has good supersingular reduction and where some other technical conditions are met…. In this case we will obtain an explicit height lower bound swiftly using the product formula, cf. Lemma 5.1. The crucial point is that supersingularity forces the square of the Frobenius to act as a scalar on the reduction of E modulo p.

Yup!  There’s no mention of Poonen in the paper, so I think Habegger came to this idea independently.  Very satisfying!  The hard case — for Habegger as for Poonen — has to do with the fields obtained by adjoining p-torsion, where p is the characteristic of the supersingular elliptic curve driving the argument.  It would be very interesting to hear from Poonen and/or Habegger whether the arguments are similar in that case too!

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

JMM, Golsefidy, Silverman, Scanlon

Like Emmanuel, I spent part of last week at the Joint Meetings in New Orleans, thanks to a generous invitation from Alireza Salefi Golsefidy and Alex Lubotzky to speak in their special session on expander graphs.  I was happy that Alireza was willing to violate a slight taboo and speak in his own session, since I got to hear about his work with Varju, which caps off a year of spectacular progress on expansion in quotients of Zariski-dense subgroups of arithmetic groups.  Emmanuel’s Bourbaki talk is your go-to expose.

I think I’m unlike most mathematicians in that I really like these twenty-minute talks.  They’re like little bonbons — you enjoy one and then before you’ve even finished chewing you have the next in hand!  One nice bonbon was provided by Joe Silverman, who talked about his recent work on Lehmer’s conjecture for polynomials satisfying special congruences.  For instance, he shows that a polynomial which is congruent mod m to a multiple of a large cyclotomic polynomial can’t have a root of small height, unless that root is itself a root of unity.  He has a similar result where the implicit G_m is replaced by an elliptic curve, and one gets a lower bound for algebraic points on E which are congruent mod m to a lot of torsion points.  This result, to my eye, has the flavor of the work of Bombieri, Pila, and Heath-Brown on rational points.  Namely, it obeys the slogan:  Low-height rational points repel each other. More precisely — the global condition (low height) is in tension with a bunch of local conditions (p-adic closeness.)  This is the engine that drives the upper bounds in Bombieri-Pila and Heath-Brown:  if you have too many low-height points, there’s just not enough room for them to repel each other modulo every prime!

Anyway, in Silverman’s situation, the points are forced to nestle very close to torsion points — the lowest-height points of all!  So it seems quite natural that their own heights should be bounded away from 0 to some extent.  I wonder whether one can combine Silverman’s argument with an argument of the Bombieri-Pila-Heath-Brown type to get good bounds on the number of counterexamples to Lehmer’s conjecture….?

One piece of candy I didn’t get to try was Tom Scanlon’s Current Events Bulletin talk about the work of Pila and Willkie on problems of Manin-Mumford type.  Happily, he’s made the notes available and I read it on the plane home.  Tom gives a beautifully clear exposition of ideas that are rather alien to most number theorists, but which speak to issues of fundamental importance to us.  In particular, I now understand at last what “o-minimality” is, and how Pila’s work in this area grows naturally out of the Bombieri-Pila method mentioned above.  Highly recommended!

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 , , , , , , , , , , , ,

In which I publish my first paper

The first one I wrote, that is.  It happened like this:  my undergraduate thesis advisor was Persi Diaconis, and in 1993, my senior year, Diaconis was really peeved about the proof via Selberg that every element of SL_2(F_p) could be expressed as a word of length at most C log p in the standard unipotent generators.  (See Emmanuel’s comment on Terry’s blog for useful references.)  Diaconis felt it was a combinatorial problem and it should be solvable by purely combinatorial means, and that a hard-working undergraduate who was good at Putnam problems, like me, ought to be able to do it.

That turned out not to be the case.

So Persi gave me another thesis problem; he asked if I could get good bounds on the diameter of the unipotent subgroup U of SL_n(F_p), with its standard generating set id + e_{i,i+1}.  When n = 2, this is easy; the unipotent group is just Z/pZ and its diameter is about p.  The question is:  what happens asymptotically when n and p are allowed to grow?

It’s not possible any longer for the diameter of U to be on order log |U|, as is the case for SL_2(F_p); the abelianization of U looks like (Z/pZ)^{n-1}, which already has diameter on order of np.  Unless n is much larger than p, this swamps log |U|.

But it turns out this is in some sense the only obstacle:  one can prove that diam(U) is bounded above and below by constant multiples of

np + log |U|.

(My memory is that I conceived the key step of the argument during a boring Advocate meeting.)

Much later, when I was a new postdoc at Princeton, I talked about this problem with Julianna Tymoczko, then a graduate student working with Bob McPherson.  Julianna very quickly saw how to make the argument much more conceptual and general, and in particular how to extend it to all the classical groups.  So we decided to write it up as a joint paper.  That was probably 2002.  Then we got around to writing the paper and submitting it.  That was 2005.  It was accepted in 2007.  And now here it is!  That’s the abstract; if you’re at a computer that doesn’t subscribe to Forum Math, here’s the arXiv version.  17 years from first version of the theorem to publication!

Update: Harald Helfgott politely comment-hints at something I should have put in the original post, which is that nowadays, thanks to him, there is a combinatorial proof that the diameter of SL_2(F_p) is on order log p!  The subject of uniform bounds for word growth and spectral gaps in finite groups of Lie type is currently moving very quickly.  I won’t try to summarize the state of the art, but you can expect in the medium-term to hear something about an interesting application of Harald’s work to arithmetic geometry.

Tagged , , , , ,

Get every new post delivered to your Inbox.

Join 316 other followers

%d bloggers like this: