Random groups contain surface subgroups

A few weeks ago, Ian Agol, Vlad Markovic, Ursula Hamenstadt and I organized a “hot topics” workshop at MSRI with the title Surface subgroups and cube complexes. The conference was pretty well attended, and (I believe) was a big success; the organizers clearly deserve a great deal of credit. The talks were excellent, and touched on a wide range of subjects, and to those of us who are mid-career or older it was a bit shocking to see how quickly the landscape of low-dimensional geometry/topology and geometric group theory has been transformed by the recent breakthrough work of (Kahn-Markovic-Haglund-Wise-Groves-Manning-etc.-) Agol. Incidentally, when I first started as a graduate student, I had a vague sense that I had somehow “missed the boat” — all the exciting developments in geometry due to Thurston, Sullivan, Gromov, Freedman, Donaldson, Eliashberg etc. had taken place 10-20 years earlier, and the subject now seemed to be a matter of fleshing out the consequences of these big breakthroughs. 20 years and several revolutions later, I no longer feel this way. (Another slightly shocking aspect of the workshop was for me to realize that I am older or about as old as 75% of the speakers . . .)

The rationale for the workshop (which I had some hand in drafting, and therefore feel comfortable quoting here) was the following:

Recently there has been substantial progress in our understanding of the related questions of which hyperbolic groups are cubulated on the one hand, and which contain a surface subgroup on the other. The most spectacular combination of these two ideas has been in 3-manifold topology, which has seen the resolution of many long-standing conjectures. In turn, the resolution of these conjectures has led to a new point of view in geometric group theory, and the introduction of powerful new tools and structures. The goal of this conference will be to explore the further potential of these new tools and perspectives, and to encourage communication between researchers working in various related fields.

I have blogged a bit about cubulated groups and surface subgroups previously, and I even began this blog (almost 4 years ago now) initially with the idea of chronicling my efforts to attack Gromov’s surface subgroup question. This question asks the following:

Gromov’s Surface Subgroup Question: Does every one-ended hyperbolic group contain a subgroup which is isomorphic to the fundamental group of a closed surface of genus at least 2?

The restriction to one-ended groups is just meant to rule out silly examples, like finite or virtually cyclic groups (i.e. “elementary” hyperbolic groups), or free products of simpler hyperbolic groups. Asking for the genus of the closed surface to be at least 2 rules out the sphere (whose fundamental group is trivial) and the torus (whose fundamental group \mathbb{Z}^2 cannot be a subgroup of a hyperbolic group). It is the purpose of this blog post to say that Alden Walker and I have managed to show that Gromov’s question has a positive answer for “most” hyperbolic groups; more precisely, we show that a random group (in the sense of Gromov) contains a surface subgroup (in fact, many surface subgroups) with probability going to 1 as a certain natural parameter (the “length” n of the random relators) goes to infinity. (update April 8: the preprint is available from the arXiv here.)

First let’s start with the precise definition of a random group. There are actually two parameters in the definition — the density D and the length n. A random group at density D and length n is obtained by fixing a finite generating set S with at least 2 elements, and adding “random” reduced words R=\lbrace r_i\rbrace of length n as relators, where the number of relators to add is governed by the density D. Precisely, D is the multiplicative density of the relators. There are (approximately) (2k-1)^n cyclically reduced words of length n, so we choose (2k-1)^{Dn} subwords, independently and with the uniform measure, as our relators r_i, and then define G = \langle S \; | \; R\rangle to be our “random group”.

Gromov introduced random groups and established some of their basic properties. One talks about a random group at density D, and says that it has a certain property with overwhelming probability. What this means is that with fixed D, the probability that the property holds goes to 1 as n \to \infty. Gromov showed that there is a remarkable phase transition in this definition. Explicitly, he showed:

Theorem (Gromov): A random group has the following properties with overwhelming probability:

1. At D>1/2 the group is either trivial or isomorphic to \mathbb{Z}/2\mathbb{Z};

2. At D<1/2 the group is infinite, hyperbolic, and 2-dimensional; and

3. At D the group satisfies the small cancellation condition C'(2D).

The story at density D=1/2 is more subtle, and it is not so clear what happens, as far as I know. (update April 6: Piotr Przytycki points out that the one-endedness of random groups is actually due to Dahmani-Guirardel-Przytycki. Thanks Piotr!)

With this definition, the main theorem Alden and I prove is the following:

Theorem (Calegari-Walker): A random group at density D<1/2 contains many quasiconvex surface subgroups, with probability 1-O(e^{-n^c}).

In particular, they contain surface subgroups with overwhelming probability. In fact, at the MSRI conference I gave a partial announcement of this theorem, saying only that we could prove the existence of surface subgroups at “some positive density”; I was worried about the fact that at density D>1/12 the group is no longer C'(1/6) and therefore not a small cancellation group in the classical sense. However, it turns out that Yann Ollivier developed enough elements of a kind of small cancellation theory for random groups at any D<1/2 that the argument can be pushed all the way.

The proof contains some technical details, but I believe that some of the main ideas of the proof can be given in a blog post. But before I do so, I think it is worth discussing (very) briefly why one might be interested in finding surface subgroups.

For certain classes of hyperbolic groups — for example, fundamental groups of hyperbolic 3-manifolds — finding a surface subgroup was always known to be an important question to give insight into the virtual Haken conjecture. In fact, the Kahn-Markovic construction of such subgroups turned out to be one of the key steps in the eventual proof of that conjecture by Agol. But even beyond 3-manifolds per se, surface subgroups play an important role. At the MSRI conference Vlad Markovic talked about an approach he has to Cannon’s Conjecture — which says if G is a hyperbolic group whose boundary is homeomorphic to a 2-sphere, then G is virtually isomorphic to a (hyperbolic) 3-manifold group — and his approach depends on being able to find “enough” (quasiconvex) surface subgroups of G. I asked Gromov (by email) what had motivated him to pose this question; I don’t think he would mind if I shared his reply, which was:

I do not remember exactly my motivations and heuristic evidence in favor of the existence of “many surface groups in many hyperbolic groups” except for connectedness arguments at the boundaries, but I had  (and am having) a feeling that these are essential structural components of hyperbolic groups.

My own view, and my main interest in this question, is stimulated by a belief that surface groups (not necessarily closed, and possibly with boundary) can act as a sort of “bridge” between hyperbolic geometry and symplectic geometry (through their connection to causal structures, quasimorphisms, stable commutator length, etc). Surface groups are the “simplest” kind of hyperbolic groups after free groups, and surfaces themselves are the “simplest” class of symplectic manifold; any route between the two kinds of geometry must surely say a lot about surfaces. In this vein, I should remark that in the world of 3-manifold topology (where these issues are infinitely better understood), surfaces again play the premier role in both worlds: minimal/pleated/shrinkwrapped surfaces in the hyperbolic world, norm minimizing/pseudoholomorphic/convex in the contact/symplectic world. It is worth remarking that for the longest time embedded surfaces played a preeminent role in both theories, but that recent breakthroughs (on the hyperbolic side) have depended on developing a deep understanding of immersed surfaces. I wonder whether there is an important role for immersed surfaces on the symplectic side (in 3\pm 1-manifold topology)? Maybe a reader who is an expert on Heegaard Floer homology can offer an opinion.

OK, let’s move on to the proof of the Random Group Surface Subgroup Theorem. The first step of the proof builds on a construction in our paper Surface subgroups from Linear Programming, where we show that a sufficiently random homologically trivial collection of cyclic words in a free groups can be taken to bound a certain kind of combinatorial object called a Folded Fatgraph (this result also underpins the main theorem in my recent related paper Random graphs of free groups contain surface subgroups, joint with Henry Wilton). A fatgraph is just an ordinary graph together with a choice of cyclic ordering on the edges incident to each vertex. Such a graph can be canonically fattened to a compact surface (with boundary) in which it lies as a spine. Stallings famously observed that an immersion (i.e. a locally injective simplicial map) between graphs is injective on fundamental groups; such a map of graphs is said to be folded. Thus a folded fatgraph gives an injective surface (with boundary!) subgroup of a free group with prescribed boundary.

The first step in our paper is to make this result more quantitative. A trivalent fatgraph with reduced boundary words is necessarily folded. Our first main result is the following

 Thin Fatgraph Theorem: If \Gamma is a sufficiently random homologically trivial collection of cyclically reduced words in a free group F, then for any L there is some N depending only on L so that N copies of \Gamma bounds a trivalent fatgraph in which every edge has length at least L.

These fatgraphs have very long edges and are trivalent; hence are “thin”. Let me not say anything about the proof except that the first part of it closely models the proof of Thm 8.9 from our SSLP paper linked above, but the last step (which was done by computer in the SSLP paper) depends on an elementary but complicated combinatorial argument (which takes up almost half the paper!). (It is worth remarking that this last combinatorial step has something morally in common with the Kahn-Markovic proof of the Ehrenpreis conjecture via the theory of “good pants homology”, in that we want to cancel some collection of “superfluous” short loops which can be thought of as random excitations on the surface of a (Dirac) sea of perfectly equidistributed loops. I should also remark that some version of this theory — “pants homology” if you will — was earlier developed by me in my paper Faces of the scl norm ball, in which I showed that every homologically trivial immersed collection of geodesics on a hyperbolic surface virtually cobounds an immersed subsurface with a sufficiently large multiple of the boundary.)

By the way, it is natural to wonder just how “random” the collection \Gamma needs to be for the conclusion of the theorem to hold (technically, we work with a deterministic property called “pseudorandomness” which is a kind of controlled equidistribution at certain scales). One can ask how long a random cyclically reduced (homologically trivial) word needs to be before it bounds a trivalent fatgraph (with, for the sake of concreteness, no constraint on the length of edges). This is a question that can be addressed experimentally by computer. The results are very interesting. For rank 3, we looked at between 100000 and 400000 such words of each even length from 10 to 120. The proportion of such words that bound trivalent fatgraphs is plotted below:

trivalent_graph

The first time we did this experiment, we only looked at words up to length 50 or so; needless to say, this gives a somewhat misleading idea of the asymptotic picture!

How can one use thin fatgraphs to build surface subgroups? Before tackling a random group, let’s consider a one-relator group with a single (long, random) relator r. We can imagine building a (polygonal) surface S out of disks, each of which has either r or r^{-1} on its boundary, where the disks are glued to each other along mutually inverse subwords of the boundary words. Since a random word will probably not be homologically trivial, we build a surface out of N disks labeled r and N disks labeled r^{-1}, where N is as in the Thin Fatgraph Theorem. The 1-skeleton Y of S is a graph, and the way in which it sits in S gives it a fatgraph structure.

The first thing one might think therefore is that one should just apply the Thin Fatgraph Theorem to build a fatgraph bounding Nr + Nr^{-1}. One can do this, but why should one expect the resulting surface to be injective? In order for the surface S to fail to be injective there must be some essential loop \gamma in the 1-skeleton Y which bounds a van Kampen disk \mathcal{D} in the group. Without loss of generality, we can assume that this disk has a minimal number of faces; note that each face has either r or r^{-1} on its boundary. A (random) 1-relator group is hyperbolic; in fact, it is C'(\lambda) for any \lambda with overwhelming probability, when the length n of the relator gets long. So in such a van Kampen diagram there must be very long subwords (of length O(n)) in r or r^{-1} which are subwords of \gamma. Of course, Y does contain long subwords of r and r^{-1}; the boundary of the fattening of Y consists entirely of such words! But in a minimal van Kampen diagram such “boundary” subwords must not occur, and the question is whether Y contains long subwords in common with r or r^{-1} that are not boundary-parallel.

A counting estimate gives the following heuristic answer. By the defining property of a Thin Fatgraph, for any T there are O(2^{T/L}) paths in Y of length T starting at any point, and only |Y|=O(n) starting points. On the other hand, there are (2k-1)^T random reduced words of length T, and the relator r contains at most n of them. The difficulty in making this argument rigorous is that the fatgraph Y is not independent of r; in fact it is constructed “from” r in a direct sense! So the trick is to break up r into small subwords, and build thin fatgraphs bounding each subword, and then each small thin fatgraph will be independent of the other subwords.

Explicitly, we find what we call a Bead Decomposition of r; this is a decomposition of r into subwords r_i^\pm of length O(n^{1-\delta}) which start and end with mutually inverse subwords of length C\log(n). The inverse subwords at the start of each r_i^\pm are paired, to produce a collection of beads of size O(n^{1-\delta}), separated by intervals of length C\log(n) called necks. Each bead on its own will probably be homologically essential, but we can perform a bead decomposition at “the same” locations in the word r^{-1} to get a collection of pairs of inverse beads B_i, B_i^{-1} of length O(n^{1-\delta}). Taking N copies of each pair of beads, we can build a thin fatgraph that bounds it, and then these thin fatgraphs are joined one to the next along necks. By construction, the subwords contained in the spine of the fatgraph bounding a bead B_i are independent of the subwords in B_j for i \ne j, so with overwhelming probability, they have no long subwords in common. The necks are sufficiently long that whenever a subword passes over a neck, another copy of that subword cannot appear within distance n^{\epsilon} for some 0 <\epsilon < \delta (with high probability). But the existence of a van Kampen diagram would give rise to a long string of such coincidences, and therefore we deduce that no van Kampen diagram exists, and the surface is injective.

We now throw in an additional (2k-1)^{nD} random relators of length n independently, and with the uniform measure. Now the naive counting argument above is rigorous, and each additional relator r' is unlikely to have a long segment in common with a subpath in the spine Y. In fact, what can be shown is that for each E<D there are of order (2k-1)^{n(D-E)} relators that have En of their boundary in common with a subpath of Y (this common part does not need to be consecutive, but we do need to bound the number of connected components by some constant independent of n; this is where Ollivier’s small cancellation work comes in to bootstrap such “local” small cancellation estimates to “global” ones). From this argument, and some elementary reasoning with van Kampen diagrams, the result follows.

One subtlety is that it is necessary to control the size of the van Kampen diagrams we consider independently of n. A path in a hyperbolic group which is not quasigeodesic can be shortened on a segment of size 8\delta, where \delta is the constant of hyperbolicity. Ollivier shows that \delta is linear in n, for fixed D, and therefore we can obtain estimates on the probability that S fails to be injective by considering van Kampen diagrams containing a bounded number of disks.

This entry was posted in Ergodic Theory, Groups, Surfaces and tagged , , , , . Bookmark the permalink.

2 Responses to Random groups contain surface subgroups

  1. SecretDoves says:

    Is there anything that can be said about the index of these surface subgroups?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s