The (strengthened) Hanna Neumann Conjecture

A few days ago, Joel Friedman posted a paper on the arXiv purporting to give a proof of the (strengthened) Hanna Neumann conjecture, a well-known problem in geometric group theory.

Simply stated, the problem is as follows.

Conjecture (Hanna Neumann): Let be a free group, and let and be finitely generated subgroups. For a subgroup of , let . Then there is an inequality .

This conjecture was further strengthened by Walter Neumann (her son):

Conjecture (strengthened Hanna Neumann): With notation above, there is an inequality where the sum is taken over , i.e. the double coset representatives.

Notice by the way that since any free group embeds into , the free group of rank , one can assume that has rank above. This fact is implicit in the discussion below.

Friedman’s paper seems to be very carefully written, and contains some new ideas (which I do not yet really understand), namely an approach using sheaf theory. But in this post I want to restrict myself to some simple (and probably well-known) geometric observations.

The first step is to reduce the problem to a completely graph-theoretic one, following Stallings; in fact, Benson Farb tells me that he thinks this reduction was known to Stallings, or at least to Dicks/Formanek (and in any case is very close to some ideas Stallings and Gersten introduced to study the problem; more on that in a later post). Friedman makes the following definition:

Definition: Let be a finite group and be two elements (that do not necessarily generate ). The directed Cayley graph is the graph with vertex set and with a directed edge from to labeled for each and .

In other words, is a graph whose edges are oriented and labeled with either or in such a way that each vertex has at most one outgoing and one incoming edge with each label, and such that there is a transitive (on the vertices) free action of a group on . (Note: for some reason, Friedman wants his group to act on the right, and therefore has directed edges from to , but this is just a matter of convention).

For any finite graph , not necessarily connected, let ; i.e. where the sum is taken over the connected components of . Friedman shows (but this reduction is well-known) that the SHNC is equivalent to the following graph-theoretic inequality:

Theorem: The SHNC is equivalent to the following statement. For any graph as above, and any two subgraphs we have .

The purpose of this blog entry is to show that there is a very simple proof of this inequality when is replaced with . This is not such a strange thing to do, since and are equal for graphs without acyclic components (i.e. without components that are trees), and for “random” graphs one does not expect the difference between and to be very big. The argument proceeds as follows. Suppose has vertices and edges of kind respectively, and define similarly for . Then

• 

On the other hand, since Euler characteristic is local, we just need to count how many vertices and edges of each kind turn up in each . But this is easy: every vertex of is equal to exactly one translate of every vertex of , and similarly for edges of each kind. Hence

• 

So the inequality one wants to show is which simplifies to

• 

On the other hand, each graph has at most two edges at any vertex with either label, and therefore we have inequalities . Subject to these constraints, the inequality above is straightforward to prove. To see this, first fix some non-negative values of and let be the four-dimensional cube of possible values of . Since both sides of the inequality are linear as a function of each or , if the inequality is violated at any point in one may draw a straight line in corresponding to varying one of the co-ordinates (e.g. ) while keeping the others fixed, and deduce that the inequality must be violated on one of the faces of . Inductively, if the inequality is violated at all, it is violated at a vertex of , which may be ruled out by inspection; qed.

This argument shows that the whole game is to understand the acyclic components of ; i.e. those which are topologically trees, and therefore contribute to , but to .

Incidentally, for all I know, this simple argument is explicitly contained in either Stallings’ or Gersten’s paper (it is surely not original in any case). If a reader can verify this, please let me know!

Update: Walter Neumann informs me that this observation (that the inequality is true with in place of ) is in his paper in which he introduces the SHNC! He further shows in that paper that for “most” , the SHNC is true for all .

Update (6/29): Warren Dicks informs me that he was not aware of the reduction of SHNC to the graph-theoretic formulation described above. Friedman’s webpage acknowledges the existence of an error in the paper, and says that he is working to correct it. One problem that I know of (discovered mostly by my student Steven Frankel) concerns the commutativity of the diagram on page 10.

Update (10/22): It has been a few months since I last edited this page, and Joel Friedman has not updated either the arXiv paper, or the statement on his webpage that he is “trying to fix the error”. Since wikipedia mentions Friedman’s announcement, I thought it would be worth going on record at this point to say that Friedman’s arXiv paper (version 1 — the only version at the point I write this) is definitely in error, and that I believe the error is fundamental, and cannot be repaired (this is not to say that the paper does not contain some things of interest (it does), or that Friedman does not acknowledge the error (he does), just that it is worth clearing up any possible ambiguity about the situation for readers who are wondering about the status of the SHNC). The problem is the “not entirely standard” (quote from Friedman’s paper) diagrams, like the one on page 10. In particular, the claimed proof of Theorem 5.6, that the projections constructed in Lemma 5.5 (by a very general dimension counting argument) fit into a diagram with the desired properties is false. Any construction of projections satisfying the desired properties must be quite special. Nevertheless, one can certainly still define Friedman’s sheaf , and ask whether it has (in Friedman’s sense); this would, as far as I can tell, prove SHNC; however, I do not know of any reason why it should hold (or whether there are any counterexamples, which might exist even if SHNC is true).

Groups with free subgroups

More ambitious than simply showing that a group is infinite is to show that it contains an infinite subgroup of a certain kind. One of the most important kinds of subgroup to study are free groups. Hence, one is interested in the question:

Question: When does a group contain a (nonabelian) free subgroup?

Again, one can (and does) ask this question both about a specific group, and about certain classes of groups, or for a typical (in some sense) group from some given family.

Example: If is a property of groups that is inherited by subgroups, then if no free group satisfies , no group that satisfies can contain a free subgroup. An important property of this kind is amenability. A (discrete) group is amenable if it admits an invariant mean; that is, if there is a linear map (i.e. a way to define the average of a bounded function over ) satisfying three basic properties:

1. if (i.e. the average of a non-negative function is non-negative)
2. where is the constant function taking the value everywhere on (i.e. the average of the constant function is normalized to be )
3. for every and , where (i.e. the mean is invariant under the obvious action of on )

If is a subgroup of , there are (many) -invariant homomorphisms taking non-negative functions to non-negative functions, and to ; for example, the (left) action of on breaks up into a collection of copies of acting on itself, right-multiplied by a collection of right coset representatives. After choosing such a choice of representatives , one for each coset , we can define . Composing with shows that every subgroup of an amenable group is amenable (this is harder to see in the “geometric” definition of amenable groups in terms of Folner sets). On the other hand, as is well-known, a nonabelian free group is not amenable. Hence, amenable groups do not contain nonabelian free subgroups.

The usual way to see that a nonabelian free group is not amenable is to observe that it contains enough disjoint “copies” of big subsets. For concreteness, let denote the free group on two generators , and write their inverses as . Let denote the set of reduced words that start with either or , and let denote the indicator functions of respectively. We suppose that is amenable, and derive a contradiction. Note that , so . Let denote the set of reduced words that start with one of the strings , and let denote the indicator function of . Notice that is made of two disjoint copies of each of . So on the one hand, , but on the other hand, .

Conversely, the usual way to show that a group is amenable is to use the Folner condition. Suppose that is finitely generated by some subset , and let denote the Cayley graph of (so that is a homogeneous locally finite graph). Suppose one can find finite subsets of vertices so that (here means the number of vertices in , and   means the number of vertices in that share an edge with ). Since the “boundary” of is small compared to , averaging a bounded function over is an “almost invariant” mean; a weak limit (in the dual space to ) is an invariant mean. Examples of amenable groups include

1. Finite groups
2. Abelian groups
3. Unions and extensions of amenable groups
4. Groups of subexponential growth

and many others. For instance, virtually solvable groups (i.e. groups containing a solvable subgroup with finite index) are amenable.

Example: No amenable group can contain a nonabelian free subgroup. The von Neumann conjecture asked whether the converse was true. This conjecture was disproved by Olshanskii. Subsequently, Adyan showed that the infinite free Burnside groups are not amenable. These are groups with generators, and subject only to the relations that the th power of every element is trivial. When is odd and at least , these groups are infinite and nonamenable. Since they are torsion groups, they do not even contain a copy of , let alone a nonabelian free group!

Example: The Burnside groups are examples of groups that obey a law; i.e. there is a word in finitely many free variables, such that for every choice of . For example, an abelian group satisfies the law . Evidently, a group that obeys a law does not contain a nonabelian free subgroup. However, there are examples of groups which do not obey a law, but which also do not contain any nonabelian free subgroup. An example is the classical Thompson’s group , which is the group of orientation-preserving piecewise-linear homeomorphisms of with finitely many breakpoints at dyadic rationals (i.e. points of the form for integers ) and with slopes integral powers of . To see that this group does not obey a law, one can show (quite easily) that in fact is dense (in the topology) in the group of all orientation-preserving homeomorphisms of the interval. This latter group contains nonabelian free groups; by approximating the generators of such a group arbitrarily closely, one obtains pairs of elements in that do not satisfy any identity of length shorter than any given constant. On the other hand, a famous theorem of Brin-Squier says that does not contain any nonabelian free subgroup. In fact, the entire group does not contain any nonabelian free subgroup. A short proof of this fact can be found in my paper as a corollary of the fact that every subgroup of has vanishing stable commutator length; since stable commutator length is nonvanishing in nonabelian free groups, this shows that there are no such subgroups of . (Incidentally, and complementarily, there is a very short proof that stable commutator length vanishes on any group that obeys a law; we will give this proof in a subsequent post).

Example: If surjects onto , and contains a free subgroup , then there is a section from to (by freeness), and therefore contains a free subgroup.

Example: The most useful way to show that contains a nonabelian free subgroup is to find a suitable action of on some space . The following is known as Klein’s ping-pong lemma. Suppose one can find disjoint subsets and of , and elements so that , , and similarly interchanging the roles of and . If is a reduced word in , one can follow the trajectory of a point under the orbit of subwords of to verify that is nontrivial. The most common way to apply this in practice is when act on with source-sink dynamics; i.e. the element has two fixed points so that every other point converges to under positive powers of , and to under negative powers of . Similarly, has two fixed points with similar dynamics. If the points are disjoint, and is compact, one can take any small open neighborhoods of , and then sufficiently large powers of and will satisfy the hypotheses of ping-pong.

Example: Every hyperbolic group acts on its Gromov boundary . This boundary is the set of equivalence classes of quasigeodesic rays in (the Cayley graph of) , where two rays are equivalent if they are a finite Hausdorff distance apart. Non-torsion elements act on the boundary with source-sink dynamics. Consequently, every pair of non-torsion elements in a hyperbolic group either generate a virtually cyclic group, or have powers that generate a nonabelian free group.

It is striking to see how easy it is to construct nonabelian free subgroups of a hyperbolic group, and how difficult to construct closed surface subgroups. We will return to the example of hyperbolic groups in a future post.

Example: The Tits alternative says that any linear group (i.e. any subgroup of for some ) either contains a nonabelian free subgroup, or is virtually solvable (and therefore amenable). This can be derived from ping-pong, where is made to act on certain spaces derived from the linear action (e.g. locally symmetric spaces compactified in certain ways, and buildings associated to discrete valuations on the ring of entries of matrix elements of ). 

Example: There is a Tits alternative for subgroups of other kinds of groups, for example mapping class groups, as shown by Ivanov and McCarthy. The mapping class group (of a surface) acts on the Thurston boundary of Teichmuller space. Every subgroup of the mapping class group either contains a nonabelian free subgroup, or is virtually abelian. Roughly speaking, either elements move points in the boundary with enough dynamics to be able to do ping-pong, or else the action is “localized” in a train-track chart, and one obtains a linear representation of the group (enough to apply the ordinary Tits alternative). Virtually solvable subgroups of mapping class groups are virtually abelian.

Example: A similar Tits alternative holds for . This was shown by Bestvina-Feighn-Handel in these three papers (the third paper shows that solvable subgroups are virtually abelian, thus emphasizing the parallels with mapping class groups).

Example: If is a finitely generated group of homeomorphisms of , then there is a kind of Tits alternative, first proposed by Ghys, and proved by Margulis: either preserves a probability measure on (which might be singular), or it contains a nonabelian free subgroup. To see this, first note that either has a finite orbit (which supports an invariant probability measure) or the action is semi-conjugate to a minimal action (one with all orbits dense). In the second case, the proof depends on understanding the centralizer of the group action: either the centralizer is infinite, in which case the group is conjugate to a group of rotations, or it is finite cyclic, and one obtains an action of on a “smaller” circle, by quotienting out by the centralizer. So one may assume the action is minimal with trivial centralizer. In this case, one shows that the action has the property that for any nonempty intervals in , there is some with ; i.e. any interval may be put inside any other interval by some element of the group. For such an action, it is very easy to do ping-pong. Incidentally, a minor variation on this result, and with essentially this argument, was established by Thurston in the context of uniform foliations of -manifolds before Ghys proposed his question.

Example: If is an (algebraic) family of representations of a (countable) free group into an algebraic group, then either some element is in the kernel of every , or the set of faithful representations is “generic”, i.e. the intersection of countably many open dense sets. This is because the set of representations for which a given element is in the kernel is Zariski closed, and therefore its complement is open and either empty or dense (one must add suitable hypotheses or conditions to the above to make it rigorous).

Infinite groups

Before looking for surface subgroups, it is worth thinking about how to find (or rule out the existence of) simpler classes of subgroups. This is a very general question, and I do not intend to give a complete survey; however, it is instructive to build up to the question of surface subgroups incrementally and to catalog some of the interesting examples and counterexamples along the way.

Question: When is a group infinite?

Already this question is more than hard enough. But first we must examine some unstated assumptions behind the question. We have some group in mind, and want to know whether it is infinite or not. But in what sense do we “have” the group ? There are several things we might mean by this, including:

1. An explicit group given by generators and relations; i.e. .
2. A group given together with an action on a set .
3. A group not uniquely defined, but described implicitly in terms of its properties (e.g. is amenable, or left-orderable, or has property , or is linear, or is residually , or is a -manifold group, or is finitely presented, or satisfies a law, etc.).

In general, it is hard to learn much about a group from a presentation. However, sometimes one can have some success:

Example: If is given by a finite presentation , the deficiency of the presentation is the difference between the number of generators and the number of relators; i.e. . The deficiency of is the maximum of the deficiency of all finite presentations. In practice, it is very difficult to determine the deficiency of a group, but trivial to determine the deficiency of a given presentation. The rank of the abelianization of (i.e. the rank of ) is at least as big as the deficiency; hence if the deficiency is positive, is infinite, and in fact contains a copy of .

Example: Daniel Allcock observed that one can do better when some of the relators as above are proper powers. Geometrically, a relator of order counts as only “ of a relator” for the purposes of computing the rank of . Explicitly, Allcock shows that if is a group with a presentation of the form then if is a normal subgroup of of index and for each index , one has for then the rank of the abelianization of is at least . If this rank is positive, then is infinite, and therefore so is .

Example: A much more subtle example is the famous Golod-Shafarevich inequality. Let be a finite -group (i.e. a group in which every element is torsion, with order a power of ). Let be the minimum number of generators of , and the number of relations between these generators in the corresponding free pro--group (if denotes the minimum number of relations defining as a discrete group then ). The G-S inequality is the inequality . In particular, if is a nontrivial pro--group for which (or which implies it) then is infinite. This inequality enabled Golod to give a negative answer to the generalized Burnside’s problem, by showing that for each prime there is an infinite group generated by three elements, in which every element has order a power of .

Example: Marc Lackenby has made very nice use of the Golod-Shafarevich inequality in his work on Kleinian groups with finite non-cyclic subgroups. A Kleinian group is a finitely generated discrete subgroup of the group of isometries of hyperbolic -space; such a group is the fundamental group of a hyperbolic -orbifold. Marc shows that if a Kleinian group contains a finite non-cyclic subgroup, then is finite, or virtually free, or contains a closed surface subgroup. The argument is very interesting and delicate, and I hope to return to it in a later post. But for the moment I just want to remark that the form of the G-S inequality Marc uses is as follows. Let be a group with a finite presentation . Let denote the dimension of where is a prime. If then is infinite.

Example: Another way to show a group is infinite is if the relators are very long. This is the method of small cancellation theory, and can be implemented in many different ways. From the modern perspective, a group presentation satisfies a small cancellation condition if one can build a -complex from the presentation which is manifestly non-positively curved in some explicit sense. For example, if is a symmetrized presentation (i.e. one in which elements of are cyclically reduced, and is closed under taking cyclic permutations and inverses), a piece is a word in the generators if there are distinct relations in . If no relation is a product of fewer than pieces, one says that satisfies the small cancellation condition . So, for example, if is , one can build a -complex presenting built from polygons, each of which has at least sides, and is non-positively curved (and therefore is infinite). 

Example: Instead of showing that a particular group is infinite, one can show that certain groups whose presentations are obtained by a statistical process, are infinite with overwhelming probability. Yann Ollivier wrote an introduction to Gromov’s theory of Random Groups, in which it is made precise what one means by a “random group”, and many important properties of such groups are delineated. There is a parameter in the theory which governs the density of relations added to a generating set to determine the random group. The most striking aspect of the theory (in my opinion) is the existence of a phase transition. Gromov showed that if is a random group at density then if , with overwhelming probability, is infinite, hyperbolic, torsion-free and of geometric dimension (i.e. it is not free, but admits a -dimensional ). However, if , with overwhelming probability, is either trivial or .

Example: A group which admits a finite dimensional is torsion-free, and therefore either trivial or infinite. This follows from the fact that the ‘s are the infinite dimensional Lens spaces, which have nontrivial homology in infinitely many dimensions, together with elementary covering space theory. This example begs the question: how do you tell if a group has a finite dimensional ? Well, one way is to exhibit a free, properly discontinuous action of on a finite dimensional contractible space; of course, given such an action, it is probably easier to directly find elements in of infinite order. 

Example: A function is said to be a length function if it satisfies , if it is symmetric (i.e. for all ) and if it is subadditive: . A group is said to be strongly bounded if every length function on is bounded. The strongly bounded property was introduced by George Bergman in this paper. A countable group is strongly bounded if and only if it is finite (the fact that finite groups are strongly bounded is obvious). Moreover, a group which admits an unbounded length function is evidently infinite. However, it turns out that there are many interesting uncountable but strongly bounded groups! Bergman showed that the group of permutations of any set is strongly bounded. Yves de Cornulier, in an appendix to a paper of mine with Mike Freedman, showed that the same is true for , the group of homeomorphisms of an -sphere.

Example: One of the most spectacular proofs of the finiteness of a (certain class of) group(s) is Margulis’ proof of the normal subgroup theorem, which says that if is a lattice in a higher rank Lie group, then every normal subgroup in is either finite, or of finite index. The proof has three steps: first, one shows that if is infinite, then is amenable. Second, since has property , the same is true for . Third, an amenable group with property is finite. The second and third steps are not very complicated: a group has property if the trivial representation is isolated in the space of all irreducible unitary representations, in a certain topology. A quotient of a group by a closed normal subgroup certainly has no more unitary representations than the original group itself, so the second step is not hard to show. An amenable group has almost invariant vectors in ; since it has property , it has an invariant vector in ; but this implies that is finite. So the hard part is to show that is amenable. This is done using what is now known as boundary theory, and is described in Chapter VI of Margulis’ book.

I would be curious to hear other people’s favorite tricks/techniques to show that a group is or is not infinite.

five week plan

As an experiment, I plan to spend the next five weeks documenting my current research on this blog. This research comprises several related projects, but most are concerned in one way or another with the general program of studying the geometry of a space by probing it with surfaces. Since I am nominally a topologist, these surfaces are real -manifolds, and I am usually interested in working in the homotopy category (or some rational “quotient” of it). I am especially concerned with surfaces with boundary, and even (occasionally) with corners. 

Since it is good to have a “big question” lurking somewhere in the background (for the purposes of motivation and advertising, if nothing else), I should admit from the start that I am interested in Gromov’s well-known question about surface subgroups, which asks:

Question (Gromov): Does every one-ended word-hyperbolic group contain a closed hyperbolic surface subgroup?

I don’t have strong feelings about whether the answer to this question is “yes” or “no”, but I do think the question can be sharpened usefully in many ways, and it is my intention to do so. Gromov’s question is certainly inspired by questions such as Waldhausen’s conjecture and the virtual fibration conjecture in -manifold topology, but it is hard to imagine that a proof of one of these conjectures would shed much light on Gromov’s question in general. At least one essential tool in -manifold topology — namely Dehn’s lemma — has no meaningful analogue in geometric group theory, and I think it is important to try to imagine different methods of constructing surface groups from “first principles”.

Another long-term project that informs much of my current research is the problem of understanding stable commutator length in free groups. The interested reader can learn something about this from my monograph (which can be downloaded from this page). I hope to explain why this is a fundamental and interesting problem, with rich structure and many potential applications.