Breuillard’s ICM talk: uniform expansion, Lehmer’s conjecture, tauhat

Emmanuel Breuillard is in Korea talking at the ICM; here’s his paper, a very beautiful survey of uniformity results for growth in groups, by himself and others, and of the many open questions that remain.

He starts with the following lovely observation, which was apparently in a 2007 paper of his but which I was unaware of.  Suppose you make a maximalist conjecture about uniform growth of finitely generated linear groups.  That is, you postulate the existence of a constant c(d) such that, for any finite subset S of GL_d(C),  you have a lower bound for the growth rate

.

It turns out this implies Lehmer’s conjecture!  Which in case you forgot what that is is a kind of “gap conjecture” for heights of algebraic numbers.  There are algebraic integers of height 0, which is to say that all their conjugates lie on the unit circle; those are the roots of unity.  Lehmer’s conjecture says that if x is an algebraic integer of degree n which is {\em not} a root of unity, it’s height is bounded below by some absolute constant (in fact, most people believe this constant to be about 1.176…, realized by Lehmer’s number.)

What does this question in algebraic number theory have to do with growth in groups?  Here’s the trick; let w be an algebraic integer and consider the subgroup G of the group of affine linear transformations of C (which embeds in GL_2(C)) generated by the two transformations

x -> wx

and

x -> x+1.

If the group G grows very quickly, then there are a lot of different values of g*1 for g in the word ball S^n.  But g*1 is going to be a complex number z expressible as a polynomial in w of bounded degree and bounded coefficients.  If w were actually a root of unity, you can see that this number is sitting in a ball of size growing linearly in n, so the number of possibilities for z grows polynomially in n.  Once w has some larger absolute values, though, the size of the ball containing all possible z grows exponentially with n, and Breuillard shows that the height of z is an upper bound for the number of different z in S^n * 1.  Thus a Lehmer-violating sequence of algebraic numbers gives a uniformity-violating sequence of finitely generated linear groups.

These groups are all solvable, even metabelian; and as Breuillard explains, this is actually the hardest case!  He and his collaborators can prove the uniform growth results for f.g. linear groups without a finite-index solvable subgroup.  Very cool!

One more note:  I am also of course pleased to see that Emmanuel found my slightly out-there speculations about “property tau hat” interesting enough to mention in his paper!  His formulation is more general and nicer than mine, though; I was only thinking about profinite groups, and Emmanuel is surely right to set it up as a question about topologically finitely generated compact groups in general.

 

 

 

 

 

 

Is there a noncommutative Siegel’s Lemma?

Let f be the smallest function satisfying the following:

Suppose given two matrices A and B in SL_3(Z), with all entries at most N.  If there is a word w(A,B,A^{-1},B^{-1}) which vanishes in SL_3(Z), then there is a word w'(A,B,A^{-1},B^{-1}) of length at most f(N) which vanishes in SL_3(Z).

What are the asymptotics of f(N)?

The reason for the title is that, if SL_3(Z) is replaced by Z^n, this is Siegel’s lemma:  if two (or, for that matter, k) vectors in [-N..N]^n are linearly dependent, then there is a linear dependency whose height is polynomial in N.  (Here k and n are constants and N is growing.)

I don’t have any particular need to know this — the question came up in conversation at the very stimulating MSRI Thin Groups workshop just concluded.  Sarnak’s notes are an excellent guide to the topics discussed there.

 

 

 

Homology of the Torelli group and negative-dimensional vector spaces

OK, not really.  You know and I know there’s no such thing as a negative-dimensional vector space.

And yet…

The Torelli group T_g is a subject of hot interest to mapping class groups people — it’s the kernel of the natural surjection from the mapping class group Γ_g to Sp_{2g}(Z).  You can think of it as “the part of the mapping class group that arithmetic lattices can’t see,” or at least can’t see very well, and as such it is somewhat intimidating.  We know very little about it, even in small genera.  One thing we do know is that for g at least 3 the Torelli group is finitely generated; this is a theorem of Johnson, and a recent paper by Andy Putman provides a small generating set.  So H_1(T_g,Q) is finite-dimensional.  (From now on all cohomology groups will be silently assigned rational coefficients.)

But a charming argument of Akita shows that, in general, T_g has some infinite-dimensional homology groups.  How do we know?  Because if it didn’t, you would be able to compute the integer χ(T_g) from the formula

χ(T_g) =  χ( Γ_g)/ χ(Sp_{2g}(Z)).

But both the numerator and denominator of the right-hand-side are known, and their quotient is not an integer once g is at least 7.  Done!

At the Park City Mathematics Institute session I visited this summer, there was a lot of discussion of what these infinite-dimensional homology groups of Torelli might look like.  We should remember that the outer action of Sp_2g(Z) on Torelli yields an action of Sp_2g(Z) on the homology of Torelli — so one should certainly think of these spaces as representations of Sp_2g(Z), not as naked vector spaces.  In the few cases these groups have been described explicitly, they are induced from finite-dimensional representations of infinite-index subgroups H of Sp_2g(Z).

I just wanted to record the small observation that in cases like this, there’s a reasonably good way to assign a “dimension” to the homology group!  Namely:  suppose G is a discrete group and H a a subgroup, and suppose that both BG and BH are homotopic to finite complexes.  (This is not quite true for G = Sp_2g(Z), but surely you’re willing to spot me a little finite level structure wherever I need it.)  Let W be a finite-dimensional representation of H and let V be the induction of W up to G.

Now if H were finite-index in G you’d have

dim V = [G:H] dim W

or, what’s the same,

dim V = χ(BH)/χ(BG) dim W

But note that the latter formula makes sense even if H is infinite-index in G!  And this allows you to assign a “dimension” to some infinite-dimensional homology groups.

For instance, consider T_2, which is not finitely generated.  By a theorem of Mess, it’s a free group on a countable set of generators; these generators are naturally in bijection with cosets in Sp_4(Z) of a subgroup H containing SL_2(Z) x SL_2(Z) with index 2.  Compute the Euler characteristics of H and Sp_4 and you find that the “dimension” of H_1(T_2) is -5.

And when you ask Akita’s argument about this case, you find that the purported Euler characteristic of T_2 is 6; a perfectly good integer, but not such a great Euler characteristic for a free group to have.  Unless, of course, it’s a free group on -5 generators.

If you want to see this stuff written up a bit (but only a bit) more carefully, here’s a short .pdf version, which also includes a discussion of the hyperelliptic Torelli group in genus 3.

Should you be surprised by the diameter of the nxnxn Rubik’s group?

A press release from MIT reports on a new theorem of Erik Demaine, Martin Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow:  the group of transformations of the n x n x n Rubik’s cube has diameter on order n^2 / log n in the standard generators.  The press release quotes (Erik) Demaine as saying

“That that’s the answer, and not N², is a surprising thing,”

That they were able to prove this is surprising, and impressive, indeed!  Upper bounds on diameters of Cayley graphs are hard; you use a big spectral hammer if you have one at hand, and otherwise you really have to get dirty and explain algorithmically how you’re going to get all the group elements from short words.  And in general, the best you can hope for is an asymptotic result like the one obtained by Demaine et al; the precise diameter of the 3x3x3 Rubik’s group was only just determined to be 20 with the help of 35 CPU-years donated by Google.

But the truth of the theorem is much less surprising, in my opinion.  Let’s start with the lower bound, which is easy, as Demaine recounts.

“In the first hour, we saw that it had to be at least N²/log N,” Demaine says.

Why was this so fast?  Because the number of generators is just 6 N; for each of the 3 coordinate axes, there are N clockwise quarter-turns perpendicular to the axis and N counterclockwise quarter-turns.  So the total number of words of length k in those generators is on order N^k; for this to cover the whole group, whose size is known to be exponential in N^2, you need k to be at least N^2 / log N.

If all those words were distinct, then the diameter of the group would be N^2/log N.  But they’re not distinct!  The Rubik’s group has relations; it is not free. Far from it.

But how far from it, is the question.

To measure this, we write W(k) for the number of distinct words of length k, or “the volume of the word ball.”  If the group were free on the given generators, we’d have W(k) = (6N)^k, exponential in k.  If, on the other hand, the group were free abelian on the given generators, W(k) would be on order of k^(6N), polynomial in k.  Commutativity crushes words together a lot.  And notice that a lot of the Rubik generators commute with each other:  whenever two twists are perpendicular to the same axis, they commute.  Does that make W(k) grow a lot more slowly?

The Cartier-Foata theorem is a beautiful identity that addresses this question.  It provides an exact formula for the number of length-k words in a “partially commutative monoid,” where some pairs of generators commute, and others don’t.  Namely:  if we construct a generating function

then

where C ranges over all commutative cliques, i.e. mutually commutative subsets of the generators.  When there are no commutation relations, the commutative cliques are just the subsets of size 0 and 1, so you get P(t) = 1/(1-mt) where m is the number of generators, and W(k) grows like m^k.  When all generators commute, every subset is a commutative clique, and you get P(t) = (1-t)^(-m), whose coefficients have polynomial growth.  Julianna Tymoczko and I used the Cartier-Foata formula to give a lower bound for the diameter of unipotent subgroups of Lie groups of finite type.  In our case, the number of generators grew with the rank n of the group, but the generators commute to such a great extent that the diameter was on order log |G| instead of log |G| / n.

The Rubik’s group is not quite that commutative.  The commutative cliques are just the subsets of generators which are perpendicular to the same axis, so there are

commutative cliques of size a for all positive a.  Cartier-Foata tells us that the monoid whose only relations are these commutations has

whose smallest pole, if I did this right, is at around (log 3/2)(1/2N).  So the t^k coefficient, which is an upper bound for the W(k) of the Rubik’s group, is exponential on order of (2/log(3/2)N)^k.  In particular, this poses no obstacle to filling up the whole group with words of length O(N^2 / log N).

Now that doesn’t mean you can actually do it!  W(k) might be much smaller.  But in my (limited) experience, commutativity relations really do a lot of the work.  (For instance, in my paper with Tymoczko, we give an algorithmic way of writing group elements as short words that shows that the Cartier-Foata bound is correct up to a constant, just as in the Rubik’s case.  Also as in the Rubik’s case, that upper bound is the hard part.)  Of course it’s easy to construct examples where the Cartier-Foata estimate is way off  (e.g. a free k-nilpotent group on N generators.)  But if you had made me guess what the asymptotic behavior of the Rubik’s group is, I like to think I would have gotten it right.

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.

Fritz Grunewald, RIP

Fritz Grunewald died unexpectedly this week, just before his 61st birthday.  I never met him but have always been an admirer of his work, and I’d been meaning to post about his lovely paper with Lubotzky, “Linear representations of the automorphism group of the free group.” I’m sorry it takes such a sad event to spur me to get around to this, but here goes.

Let F_n be the free group of rank n, and Aut(F_n) its automorphism group.  How to understand what this group is like?  A natural approach is to study its representation theory.  But it’s actually not so easy to get a handle on representations of this group.  Aut(F_n) acts on F_n^ab = Z^n, so you get one n-dimensional representation; but what else can you find?

The insight of Grunewald and Lubotzky is to consider the action of Aut(F_n) on the homology of interesting finite-index subgroups of F_n.  Here’s a simple example:  let R be the kernel of a surjection F_n -> Z/2Z.  Then R^ab is a free Z-module of rank 2n – 1, and the -1 eigenspace of R^ab has rank n-1.  Now F_n may not act on R, but some finite-index subgroup H of F_n does (because there are only finitely many homomorphisms F_n -> Z/2Z, and we can take H to be the stabilizer of the one in question.)  So H acquires an action on R^ab; in particular, there is a homomorphism from H to GL_{n-1}(Z).  Grunewald and Lubotzky show that this homomorphism has image of finite index in GL_{n-1}(Z).  In particular, when n = 3, this shows that a finite-index subgroup of Aut(F_3) surjects onto a finite-index subgroup of GL_2(Z).  Thus Aut(F_3) is “large” (it virtually surjects onto a non-abelian free group), and in particular it does not have property T.  Whether Aut(F_n) has property T for n>3 is still, as far as I know, unknown.

Grunewald and Lubotzky construct maps from Aut(F_n) to various arithmetic groups via “Prym constructions” like the one above (with Z/2Z replaced by an arbitrary finite group G), and prove under relatively mild conditions that these maps have image of finite index in some specified arithmetic lattice.  Of course, it is natural to ask what one can learn from this method about interesting subgroups of Aut(F_n), like the mapping class groups of punctured surfaces.  The authors indicate in the introduction that they will return to the question of representations of mapping class groups in a subsequent paper.  I very much hope that Lubotzky and others will continue the story that Prof. Grunewald helped to begin.

“Every curve is a Teichmuller curve,” or “Why SL_2(Z) has the congruence subgroup property.”

A Teichmüller curve in M_g, the moduli space of genus-g curves, is an algebraic curve V in M_g such that the inclusion V -> M_g induces an isometry between the constant-curvature metric on V and the restriction of the Teichmüller metric on M_g.

Alternatively:  the cotangent bundle of M_g, considered as a real manifold, admits a natural action of SL_2(R); the orbits are all copies of SL_2(R) / SO(2), or the upper half-plane.  Most of the time, when you project that hyperbolic plane H down to M_g, you get a dense orbit that wanders all over M_g.  But every once in a while, the fibers of the map H -> M_g are a lattice in H, and the image is actually an algebraic curve; that, again, is a Teichmüller curve.

Teichmüller curves are the subject of lots of recent research; for now, let me just say that they are interestingly canonical curves inside M_g.  Matt Bainbridge proved strong results about their intersection numbers in Hilbert modular surfaces.  McMullen classified Teichmuller curves in M_2, giving a very nice algebraic description of the 1-parameter families of genus-2 curves parametrized by Teichmüller curves.  (As far as I know, there’s no such description in higher genus.)  In a recent note, McMullen proved that they are all defined over number fields.

This leads one to ask:  which curves defined over algebraic number fields are Teichmüller curves?  This is the subject of a paper Ben McReynolds and I just posted to the arXiv, “Every curve is a Teichmüller curve.”  The title should be read birationally; what we prove is that every curve X over an algebraic number field is birational (over C) to a Teichmüller curve in some M_g.  (In the posted version, we prove the slightly weaker statement that X is birational to a Teichmüller curve in M_{g,n}), but we’ve since tweaked the argument to get the closed-surface version.)

So why does SL_2(Z) have the congruence subgroup property?  Especially given that it, y’know, doesn’t?

Here’s what I mean.  Let Gamma_{g,n} be the mapping class group of a genus-g surface with n punctures.  Then Gamma_{g,n} acts as a group of outer automorphisms of the fundamental group pi_{g,n} of the surface; and from this, you get an action of Gamma_{g,n} on the finite set

Hom(pi_{g,n},G)/~

where G is a finite group and ~ is conjugacy.

By a congruence subgroup of Gamma_{g,n} let’s mean a stabilizer in this action.  Why this definition?  Well, when g = 1, n = 0, and G = Z/NZ, the stabilizer is just the standard congruence subgroup Gamma_0(N).  And you can easily check that the class of congruence subgroups of Gamma_{1,0} is cofinal with the usual class of congruence subgroups in SL_2(Z).

Now Gamma_{1,1} is also isomorphic to SL_2(Z), but the notion of “congruence subgroup of SL_2(Z)” afforded by this isomorphism is much more general than the usual one.  So much so that one gets the following, which is really the main point of my paper with Ben:

Every finite-index subgroup of Gamma_{1,1} containing the center and contained in Gamma(2) is a congruence subgroup.

It turns out that the finite covers of the moduli space M_{1,1} corresponding to such finite-index subgroups are always Teichmüller curves; since, by Belyi’s theorem, every curve over a number field can be so expressed, we get the desired result.

The italicized assertion above can be thought of as a very strong kind of “congruence subgroup property.”  Of course, CSP usually refers to the property that every finite-index subgroup contains a principal congruence subgroup.  That finite-index subgroups Gamma_{1,1} (and even Gamma_{1,n}) always contain congruence subgroups as defined above is a theorem of Asada, and it’s conjectured to be true for all g,n.  But the statement that every finite-index subgroup of a mapping class group is a congruence subgroup on the nose is substantially stronger, and I imagine it’s true only for (1,1) and the closely related case (0,4), which was proved, in somewhat different language, in the paper “Every curve is a Hurwitz space,” by Diaz, Donagi, and Harbater.  Our argument is very much inspired by theirs — it was to emphasize this debt that we gave our paper more or less the same title.

F_1, buildings, the braid group, GL_n(F_1[t,1/t])

It used to be you had to talk about “the field with one element” very quietly, and only among people whose opinion of you was secure. The reason, of course, is that there is no field with one element. Which doesn’t stop people from saying “But if there _were_ a field with one element, what would it be like?”

Nowadays all kinds of people are musing about this odd question in the bright light of day, and no one finds it kooky. John Baez covered the basics in a 2007 issue of This Week’s Finds. And as of a few weeks ago the field with one element has its own blog, “Ceci N’est Pas Un Corps.”

From a recent post on CNPUC, I learned the interesting fact that the braid group on n strands can be thought of as GL_n(F_1[t]).

So here’s a question: what is GL_n(F_1[t,1/t])?

Proposed answer below the fold.