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 F be a free group, and let G and H be finitely generated subgroups. For a subgroup E of F, let \rho(E) = \max(\text{rank}(E)-1,0). Then there is an inequality \rho(G \cap H) \le \rho(G)\rho(H).

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

Conjecture (strengthened Hanna Neumann): With notation above, there is an inequality \sum_x \rho(G \cap xHx^{-1}) \le \rho(G)\rho(H) where the sum is taken over x \in H\backslash F / G, i.e. the double coset representatives.

Notice by the way that since any free group embeds into F_2, the free group of rank 2, one can assume that F has rank 2 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 \mathcal{G} be a finite group and g_1,g_2 \in \mathcal{G} be two elements (that do not necessarily generate \mathcal{G}). The directed Cayley graph C is the graph with vertex set \mathcal{G} and with a directed edge from v to vg_i labeled i for each v \in \mathcal{G} and i=1,2.

In other words, C is a graph whose edges are oriented and labeled with either 1 or 2 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 \mathcal{G} on C. (Note: for some reason, Friedman wants his group to act on the right, and therefore has directed edges from v to g_iv, but this is just a matter of convention).

For any finite graph K, not necessarily connected, let \rho(K) = \sum_j \max(0,-\chi(K_j)); i.e. \rho(K) = \sum_j \rho(\pi_1(K_j)) where the sum is taken over the connected components K_j of K. 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 C as above, and any two subgraphs K,K' we have \sum_{g \in \mathcal{G}} \rho(K \cap gK') \le \rho(K)\rho(K').

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

  • (-\chi(K))(-\chi(K')) = (v-e_1-e_2)(v'-e_1'-e_2')

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 K \cap gK'. But this is easy: every vertex of K is equal to exactly one translate of every vertex of K', and similarly for edges of each kind. Hence

  • \sum_g -\chi(K \cap gK') = e_1e_1' + e_2e_2' - vv'

So the inequality one wants to show is e_1e_1' + e_2e_2' - vv' \le (v-e_1-e_2)(v'-e_1'-e_2') which simplifies to

  • v(e_1' + e_2') + v'(e_1 + e_2) \le 2vv' + e_1e_2' + e_2 e_1'

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

This argument shows that the whole game is to understand the acyclic components of K \cap gK'; i.e. those which are topologically trees, and therefore contribute 0 to \rho, but -1 to -\chi.

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 -\chi in place of \rho) is in his paper in which he introduces the SHNC! He further shows in that paper that for “most” G, the SHNC is true for all H.

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 \mathcal{K}, and ask whether it has \rho(\mathcal{K})=0 (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).

This entry was posted in Commentary, Groups and tagged , , . Bookmark the permalink.

1 Response to The (strengthened) Hanna Neumann Conjecture

  1. Pingback: Quasimorphisms and laws « Geometry and the imagination

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s