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).