You are currently browsing the tag archive for the ‘free groups’ tag.

I am in Melbourne at the moment, in the middle of giving a lecture series, as part of the 2009 Clay-Mahler lectures (also see here). Yesterday I gave a lecture with the title “faces of the scl norm ball”, and I thought I would try to give a sense of what it was all about. This also gives me an excuse to fiddle around with images in wordpress.

One starts with a basic question: given an immersion of a circle in the plane, when is there an immersion of the disk in the plane that bounds the given immersion of a circle? I.e., given a immersion , when is there an immersion for which factors through ? Obviously this depends on . Consider the following examples:

The first immersed circle obviously bounds an immersed disk; in fact, an embedded disk.

The second circle does not bound such a disk. One way to see this is to use the Gauss map, i.e. the map that takes each point on the circle to the unit tangent to its image under the immersion. The degree of the Gauss map for an embedded circle is (depending on a choice of orientation). If an immersed circle bounds an immersed disk, one can use this immersed disk to define a 1-parameter family of immersions, connecting the initial immersed circle to an embedded immersed circle; hence the degree of the Gauss map is aso for an immersed circle bounding an immersed disk; this rules out the second example.

The third example maps under the Gauss map with degree 1, and yet it does not bound an immersed disk. One must use a slightly more sophisticated invariant to see this. The immersed circle divides the plane up into regions. For each bounded region , let be an embedded arc, transverse to , that starts in the region and ends up “far away” (ideally “at infinity”). The arc determines a homological intersection number that we denote , where each point of intersection contributes depending on orientations. In this example, there are three bounded regions, which get the numbers , , respectively:

If is any map of any oriented surface with one boundary component whose boundary factors through , then the (homological) degree with which maps over each region complementary to the image of is the number we have just defined. Hence if bounds an immersed disk, these numbers must all be positive (or all negative, if we reverse orientation). This rules out the third example.

The complete answer of which immersed circles in the plane bound immersed disks was given by S. Blank, in his Ph.D. thesis at Brandeis in 1967 (unfortunately, this does not appear to be available online). The answer is in the form of an algorithm to decide the question. One such algorithm (not Blank’s, but related to it) is as follows. The image of cuts up the plane into regions , and each region gets an integer . Take “copies” of each region , and think of these as pieces of a jigsaw puzzle. Try to glue them together along their edges so that they fit together nicely along and make a disk with smooth boundary. If you are successful, you have constructed an immersion. If you are not successful (after trying all possible ways of gluing the puzzle pieces together), no such immersion exists. This answer is a bit unsatisfying, since in the first place it does not give any insight into which loops bound and which don’t, and in the second place the algorithm is quite slow and impractial.

As usual, more insight can be gained by generalizing the question. Fix a compact oriented surface and consider an immersed -manifold . One would like to know which such -manifolds bound an immersion of a surface. One piece of subtlety is the fact that there are examples where itself does not bound, but a finite cover of (e.g. two copies of ) does bound. It is also useful to restrict the class of -manifolds that one considers. For the sake of concreteness then, let be a hyperbolic surface with geodesic boundary, and let be an oriented immersed geodesic -manifold in . An immersion is said to *virtually bound* if the map factors as a composition where the second map is , and where the first map is a covering map with some degree . The fundamental question, then is:

**Question:** Which immersed geodesic -manifolds in are virtually bounded by an immersed surface?

It turns out that this question is unexpectedly connected to stable commutator length, symplectic rigidity, and several other geometric issues; I hope to explain how in the remainder of this post.

First, recall that if is any group and , the *commutator length* of , denoted , is the smallest number of commutators in whose product is equal to , and the *stable commutator length* is the limit . One can geometrize this definition as follows. Let be a space with , and let be a homotopy class of loop representing the conjugacy class of . Then over all surfaces (possibly with multiple boundary components) mapping to whose boundary wraps a total of times around . One can extend this definition to -manifolds in the obvious way, and one gets a definition of stable commutator length for formal sums of elements in which represent in homology. Let denote the vector space of real finite linear combinations of elements in whose sum represents zero in (real group) homology (i.e. in the abelianization of , tensored with ). Let be the subspace spanned by chains of the form and . Then descends to a (pseudo)-norm on the quotient which we denote hereafter by ( for homogeneous).

There is a dual definition of this norm, in terms of *quasimorphisms*.

**Definition:** Let be a group. A function is a *homogeneous quasimorphism* if there is a least non-negative real number (called the *defect*) so that for all and one has

- (homogeneity)
- (quasimorphism)

A function satisfying the second condition but not the first is an (ordinary) quasimorphism. The vector space of quasimorphisms on is denoted , and the vector subspace of homogeneous quasimorphisms is denoted . Given , one can homogenize it, by defining . Then and . A quasimorphism has defect zero if and only if it is a homomorphism (i.e. an element of ) and makes the quotient into a Banach space.

Examples of quasimorphisms include the following:

- Let be a free group on a generating set . Let be a reduced word in and for each reduced word , define to be the number of copies of in . If denotes the corresponding element of , define (note this is well-defined, since each element of a free group has a unique reduced representative). Then define . This quasimorphism is not yet homogeneous, but can be homogenized as above (this example is due to Brooks).
- Let be a closed hyperbolic manifold, and let be a -form. For each let be the geodesic representative in the free homotopy class of . Then define . By Stokes’ theorem, and some basic hyperbolic geometry, is a homogeneous quasimorphism with defect at most .
- Let be an orientation-preserving action of on a circle. The group of homeomorphisms of the circle has a natural central extension , the group of homeomorphisms of that commute with integer translation. The preimage of in this extension is an extension . Given , define ; this descends to a -valued function on , Poincare’s so-called rotation number. But on , this function is a homogeneous quasimorphism, typically with defect .
- Similarly, the group has a universal cover with deck group . The symplectic group acts on the space of Lagrangian subspaces in . This is equal to the coset space , and we can therefore define a function . After picking a basepoint, one obtains an -valued function on the symplectic group, which lifts to a real-valued function on its universal cover. This function is a quasimorphism on the covering group, whose homogenization is sometimes called the
*symplectic rotation number*; see e.g. Barge-Ghys.

Quasimorphisms and stable commutator length are related by Bavard Duality:

**Theorem (Bavard duality):** Let be a group, and let . Then there is an equality where the supremum is taken over all homogeneous quasimorphisms.

This duality theorem shows that with the defect norm is the dual of with the norm. (this theorem is proved for elements by Bavard, and in generality in my monograph, which is a reference for the content of this post.)

What does this have to do with rigidity (or, for that matter, immersions)? Well, one sees from the examples (and many others) that homogeneous quasimorphisms arise from geometry — specifically, from *hyperbolic geometry* (negative curvature) and *symplectic geometry* (causal structures). One expects to find rigidity in extremal circumstances, and therefore one wants to understand, for a given chain , the set of extremal quasimorphisms for , i.e. those homogeneous quasimorphisms satisfying . By the duality theorem, the space of such extremal quasimorphisms are a nonempty closed convex cone, dual to the set of hyperplanes in that contain and support the unit ball of the norm. The fewer supporting hyperplanes, the smaller the set of extremal quasimorphisms for , and the more rigid such extremal quasimorphisms will be.

When is a free group, the unit ball in the norm in is a rational polyhedron. Every nonzero chain has a nonzero multiple contained in the boundary of this polyhedron; let denote the face of the polyhedron containing this multiple in its interior. The smaller the codimension of , the smaller the dimension of the cone of extremal quasimorphisms for , and the more rigidity we will see. The best circumstance is when has codimension one, and an extremal quasimorphism for is unique, up to scale, and elements of .

An infinite dimensional polyhedron need not necessarily have any top dimensional faces; thus it is natural to ask: does the unit ball in have any top dimensional faces? and can one say anything about their geometric meaning? We have now done enough to motivate the following, which is the main theorem from my paper “Faces of the scl norm ball”:

**Theorem:** Let be a free group. For every isomorphism (up to conjugacy) where is a compact oriented surface, there is a well-defined chain . This satisfies the following properties:

- The projective class of intersects the interior of a codimension one face of the norm ball
- The unique extremal quasimorphism dual to (up to scale and elements of ) is the rotation quasimorphism (to be defined below) associated to any complete hyperbolic structure on
- A homologically trivial geodesic -manifold in is virtually bounded by an immersed surface in if and only if the projective class of (thought of as an element of ) intersects . Equivalently, if and only if is extremal for . Equivalently, if and only if .

It remains to give a definition of . In fact, we give two definitions.

First, a hyperbolic structure on and the isomorphism determines a representation . This lifts to , since is free. The composition with rotation number is a homogeneous quasimorphism on , well-defined up to . Note that because the image in is discrete and torsion-free, this quasimorphism is integer valued (and has defect ). This quasimorphism is .

Second, a geodesic -manifold in cuts the surface up into regions . For each such region, let be an arc transverse to , joining to . Let denote the homological (signed) intersection number. Then define .

We now show how 3 follows. Given , we compute as above. Let be such a surface, mapping to . We adjust the map by a homotopy so that it is *pleated*; i.e. so that is itself a hyperbolic surface, decomposed into ideal triangles, in such a way that the map is a (possibly orientation-reversing) isometry on each ideal triangle. By Gauss-Bonnet, we can calculate . On the other hand, wraps times around (homologically) so where the sign in each case depends on whether the ideal triangle is mapped in with positive or negative orientation. Consequently with equality if and only if the sign of every triangle is . This holds if and only if the map is an immersion; on the other hand, equality holds if and only if is extremal for . This proves part 3 of the theorem above.

Incidentally, this fact gives a fast algorithm to determine whether is the virtual boundary of an immersed surface. Stable commutator length in free groups can be computed in polynomial time in word length; likewise, the value of can be computed in polynomial time (see section 4.2 of my monograph for details). So one can determine whether projectively intersects , and therefore whether it is the virtual boundary of an immersed surface. In fact, these algorithms are quite practical, and run quickly (in a matter of seconds) on words of length 60 and longer in .

One application to rigidity is a new proof of the following theorem:

**Corollary (Goldman, Burger-Iozzi-Wienhard):** Let be a closed oriented surface of positive genus, and a Zariski dense representation. Let be the Euler class associated to the action. Suppose that (note: by a theorem of Domic and Toledo, one always has ). Then is discrete.

Here is the first Chern class of the bundle associated to . The proof is as follows: cut along an essential loop into two subsurfaces . One obtains homogeneous quasimorphisms on each group (i.e. the symplectic rotation number associated to ), and the hypothesis of the theorem easily implies that they are extremal for . Consequently the symplectic rotation number is equal to , at least on the commutator subgroup. But this latter quasimorphism takes only integral values; it follows that each element in fixes a Lagrangian subspace under . But this implies that is not dense, and since it is Zariski dense, it is discrete. (Notes: there are a couple of details under the rug here, but not many; furthermore, the hypothesis that is Zariski dense is not necessary (but can be derived as a conclusion with more work), and one can just as easily treat representations of compact surface groups as closed ones; finally, Burger-Iozzi-Wienhard prove more than just this statement; for instance, they show that the space of maximal representations is always real semialgebraic, and describe it in some detail).

More abstractly, we have shown that *extremal quasimorphisms on* *are unique*. In other words, by prescribing the value of a quasimorphism on a single group element, one determines its values on the entire commutator subgroup. If such a quasimorphism arises from some geometric or dynamical context, this can be interpreted as a kind of rigidity theorem, of which the Corollary above is an example.

I have just uploaded a paper to the arXiv, entitled “Scl, sails and surgery”. The paper discusses a connection between stable commutator length in free groups and the geometry of sails. This is an interesting example of what sometimes happens in geometry, where a complicated topological problem in low dimensions can be translated into a “simple” geometric problem in high dimensions. Other examples include the Veronese embedding in Algebraic geometry (i.e. the embedding of one projective space into another taking a point with homogeneous co-ordinates to the point whose homogeneous co-ordinates are the monomials of some fixed degree in the ), which lets one exhibit any projective variety as an intersection of a Veronese variety (whose geometry is understood very well) with a linear subspace.

In my paper, the fundamental problem is to compute stable commutator length in free groups, and more generally in free products of Abelian groups. Let’s focus on the case of a group where are free abelian of finite rank. A is just a wedge of tori of dimension equal to the ranks of . Let be a free homotopy class of -manifold in , which is homologically trivial. Formally, we can think of as a chain in , the vector space of group -boundaries, modulo homogenization; i.e. quotiented by the subspace spanned by chains of the form and . One wants to find the simplest surface mapping to that rationally bounds . I.e. we want to find a map such that factors through , and so that the boundary wraps homologically times around each loop of , in such a way as to infimize . This infimum, over all maps of all surfaces of all possible genus, is the *stable commutator length* of the chain . Computing this quantity for all such finite chains is tantamount to understanding the bounded cohomology of a free group in dimension .

Given such a surface , one can cut it up into simpler pieces, along the preimage of the basepoint . Since is a surface with boundary, these simpler pieces are surfaces with *corners*. In general, understanding how a surface can be assembled from an abstract collection of surfaces with corners is a hopeless task. When one tries to glue the pieces back together, one runs into trouble at the corners — how does one decide when a collection of surfaces “closes up” around a corner? The wrong decision leads to branch points; moreover, a decision made at one corner will propogate along an edge and lead to constraints on the choices one can make at other corners. This problem arises again and again in low-dimensional topology, and has several different (and not always equivalent) formulations and guises, including -

- Given an abstract branched surface and a weight on that surface, when is there an unbranched surface carried by the abstract branched surface and realizing the weight?
- Given a triangulation of a -manifold and a collection of normal surface types in each simplex satisfying the gluing constraints but *not* necessarily satisfying the quadrilateral condition (i.e. there might be more than one quadrilateral type per simplex), when is there an immersed unbranched normal surface in the manifold realizing the weight?
- Given an immersed curve in the plane, when is there an immersion from the disk to the plane whose boundary is the given curve?
- Given a polyhedral surface (arising e.g. in computer graphics), how can one choose smooth approximations of the polygonal faces that mesh smoothly at the vertices?

I think of all these problems as examples of what I like to call the *holonomy problem*, since all of them can be reduced, in one way or another, to studying representations of fundamental groups of punctured surfaces into finite groups. The fortunate “accident” in this case is that every corner arises by intersecting a cut with a boundary edge of . Consequently, one never wants to glue more than two pieces up at any corner, and the holonomy problem does not arise. Hence in principle, to understand the surface one just needs to understand the pieces of that can arise by cutting, and the ways in which they can be reassembled.

This is still not a complete solution of the problem, since infinitely many kinds of pieces can arise by cutting complicated surfaces . The -manifold decomposes into a collection of arcs in the tori and which we denote respectively, and the surface (hereafter abbreviated to ) has edges that alternate between elements of , and edges mapping to . Since is a torus, handles of mapping to can be compressed, reducing the complexity of , and thereby , so one need only consider *planar* surfaces .

Let denote the real vector space with basis the set of ordered pairs of elements of (not necessarily distinct), and the real vector space with basis the elements of . A surface determines a non-negative integral vector , by counting the number of times a given pair of edges appear in succession on one of the (oriented) boundary components of . The vector satisfies two linear constraints. First, there is a map defined on a basis vector by . The vector satisfies . Second, each element is a based loop in , and therefore corresponds to an element in the free abelian group . Define on a basis vector by (warning: the notation obscures the fact that and map to quite different vector spaces). Then ; moreover, a non-negative rational vector satisfying has a multiple of the form for some as above. Denote the subspace of consisting of non-negative vectors in the kernel of and by . This is a rational polyhedral cone — i.e. a cone with finitely many extremal rays, each spanned by a rational vector.

Although every integral is equal to for some , many different correspond to a given . Moreover, if we are allowed to consider formal weighted sums of surfaces, then even more possibilities. In order to compute stable commutator length, we must determine, for a given vector , an expression where the are positive real numbers, which minimizes . Here denotes *orbifold* Euler characteristic of a surface with corners; each corner contributes to . The reason one counts complexity using this modified definition is that the result is additive: . The contribution to from corners is a linear function on . Moreover, a component with can be covered by a surface of high genus and compressed (increasing ); so such a term can always be replaced by a formal sum for which . Thus the only nonlinear contribution to comes from the surfaces whose underlying topological surface is a *disk*.

Call a vector a *disk vector* if where is topologically a disk (with corners). It turns out that the set of disk vectors has the following simple form: it is equal to the union of the integer lattice points contained in certain of the open faces of (those satisfying a combinatorial criterion). Define the *sail* of to be equal to the boundary of the convex hull of the polyhedron (where here denotes Minkowski sum). The *Klein function* is the unique continuous function on , linear on rays, that is equal to exactly on the sail. Then over expressions satisfies where denotes norm. To calculate stable commutator length, one minimizes over contained in a certain rational polyhedron in .

Sails are considered elsewhere by several authors; usually, people take to be the set of all integer vectors except the vertex of the cone, and the sail is therefore the boundary of the convex hull of this (simpler) set. Klein introduced sails as a higher-dimensional generalization of continued fractions: if is a polyhedral cone in two dimensions (i.e. a sector in the plane, normalized so that one edge is the horizontal axis, say), the vertices of the sail are the continued fraction approximations of the boundary slope. Arnold has revived the study of such objects in recent years. They arise in many different interesting contexts, such as numerical analysis (especially diophantine approximation) and algebraic number theory. For example, let be a matrix with irreducible characteristic equation, and all eigenvalues real and positive. There is a basis for consisting of eigenvalues, spanning a convex cone . The cone — and therefore its sail — is invariant under ; moreover, there is a subgroup of consisting of matrices with the same set of eigenvectors; this observation follows from Dirichlet’s theorem on the units in a number field, and is due to Tsuchihashi. This abelian group acts freely on the sail with quotient a (topological) torus of dimension , together with a “canonical” cell decomposition. This connection between number theory and combinatorics is quite mysterious; for example, Arnold asks: which cell decompositions can arise? This is unknown even in the case .

The most interesting aspect of this correspondence, between stable commutator length and sails, is that it allows one to introduce *parameters*. An element in a free group can be expressed as a word in letters , e.g. , which is usually abbreviated with exponential notation, e.g. . Having introduced this notation, one can think of the exponents as parameters, and study stable commutator length in families of words, e.g. . Under the correspondence above, the parameters only affect the coefficients of the linear map , and therefore one obtains families of polyhedral cones whose extremal rays depend linearly on the exponent parameters. This lets one prove many facts about the stable commutator length spectrum in a free group, including:

**Theorem: **The image of a nonabelian free group of rank at least under scl in is precisely .

and

**Theorem:** For each , the image of the free group under scl contains a well-ordered sequence of values with ordinal type . The image of contains a well-ordered sequence of values with ordinal type .

One can also say things about the precise dependence of scl on parameters in particular families. More conjecturally, one would like to use this correspondence to say something about the *statistical* distribution of scl in free groups. Experimentally, this distribution appears to obey power laws, in the sense that a given (reduced) fraction appears in certain infinite families of elements with frequency proportional to for some power (which unfortunately depends in a rather opaque way on the family). Such power laws are reminiscent of Arnold tongues in dynamics, one of the best-known examples of *phase locking* of coupled nonlinear oscillators. Heuristically one expects such power laws to appear in the geometry of “random” sails — this is explained by the fact that the (affine) geometry of a sail depends only on its orbit, and the existence of invariant measures on a natural moduli space; see e.g. Kontsevich and Suhov. The simplest example concerns the (-dimensional) cone spanned by a random integral vector in . The orbit of such a vector depends only on the gcd of the two co-ordinates. As is easy to see, the probability distribution of the gcd of a random pair of integers obeys a power law: with probability . The rigorous justification of the power laws observed in the scl spectrum of free groups remains the focus of current research by myself and my students.

The development and scope of modern biology is often held out as a fantastic opportunity for mathematicians. The accumulation of vast amounts of biological data, and the development of new tools for the manipulation of biological organisms at microscopic levels and with unprecedented accuracy, invites the development of new mathematical tools for their analysis and exploitation. I know of several examples of mathematicians who have dipped a toe, or sometimes some more substantial organ, into the water. But it has struck me that I know (personally) few mathematicians who believe they have something substantial to learn from the biologists, despite the existence of several famous historical examples. This strikes me as odd; my instinctive feeling has always been that intellectual ruts develop so easily, so deeply, and so invisibly, that continual cross-fertilization of ideas is essential to escape ossification (if I may mix biological metaphors . . .)

It is not necessarily easy to come up with profound examples of biological ideas or principles that can be easily translated into mathematical ones, but it is sometimes possible to come up with suggestive ones. Let me try to give a tentative example.

Deoxiribonucleic acid (DNA) is a nucleic acid that contains the genetic blueprint for all known living things. This blueprint takes the form of a code — a molecule of DNA is a long polymer strand composed of simple units called *nucleotides*; such a molecule is typically imagined as a string in a four character alphabet , which stand for the nucleotides Adenine, Thymine, Guanine, and Cytosine. These molecular strands like to arrange themselves in tightly bound oppositely aligned pairs, matching up nucleotides in one string with complementary nucleotides in the other, so that matches with , and with .

The geometry of a strand of DNA is very complicated — strands can be tangled, knotted, linked in complicated ways, and the fundamental interactions between strands (e.g. transcription, recombination) are facilitated or obstructed by mechanical processes depending on this geometry. Topology, especially knot theory, has been used in the study of some of these processes; the value of topological methods in this context include their robustness (fault-tolerance) and the discreteness of their invariants (similar virtues motivate some efforts to build topological quantum computers). A complete mathematical description of the salient biochemistry, mechanics, and semantic content of a configuration of DNA in a single cell is an unrealistic goal for the foreseeable future, and therefore attempts to model such systems depends on ignoring, or treating statistically, certain features of the system. One such framework ignores the ambient geometry entirely, and treats the system using symbolic, or combinatorial methods which have some of the flavor of geometric group theory.

One interesting approach is to consider a mapping from the alphabet of nucleotides to a standard generating set for , the free group on two generators; for example, one can take the mapping where are free generators for , and denote their inverses. Then a pair of oppositely aligned strands of DNA translates into an edge of a van Kampen diagram — the “words” obtained by reading the letters along an edge on either side are inverse in .

Strands of DNA in a configuration are *not* always paired along their lengths; sometimes junctions of three or more strands can form; certain mobile four-strand junctions, so-called “Holliday junctions”, perform important functions in the process of genetic recombination, and are found in a wide variety of organisms. A configuration of several strands with junctions of varying valences corresponds in the language of van Kampen diagrams to a *fatgraph* — i.e. a graph together with a choice of cyclic ordering of edges at each vertex — with edges labeled by inverse pairs of words in (note that this is quite different from the fatgraph model of proteins developed by Penner-Knudsen-Wiuf-Andersen). The energy landscape for branch migration (i.e. the process by which DNA strands separate or join along some segment) is very complicated, and it is challenging to model it thermodynamically. It is therefore not easy to predict in advance what kinds of fatgraphs are more or less likely to arise spontaneously in a prepared “soup” of free DNA strands.

As a thought experiment, consider the following “toy” model, which I do not suggest is physically realistic. We make the assumption that the energy cost of forming a junction of valence is for some fixed constant . Consequently, the energy of a configuration is proportional to , i.e. the negative of Euler characteristic of the underlying graph. Let be a reduced word, representing an element of , and imagine a soup containing some large number of copies of the strand of DNA corresponding to the string . In thermodynamic equilibrium, the partition function has the form where is Boltzmann’s constant, is temperature, and is the energy of a configuration (which by hypothesis is proportional to ). At low temperature, minimal energy configurations tend to dominate; these are those that minimize per unit “volume”. Topologically, a fatgraph corresponding to such a configuration can be thickened to a surface with boundary. The words along the edges determine a homotopy class of map from such a surface to a (e.g. a once-punctured torus) whose boundary components wrap multiply around the free homotopy class corresponding to the conjugacy class of . The infimum of where is the winding degree on the boundary, taken over all configurations, is precisely the *stable commutator length* of ; see e.g. here for a definition.

Anyway, this example is perhaps a bit strained (and maybe it owes more to thermodynamics than to biology), but already it suggests a new mathematical object of study, namely the partition function as above, and one is already inclined to look for examples for which the partition function obeys a symmetry like that enjoyed by the Riemann zeta function, or to specialize temperature to other values, as in random matrix theory. The introduction of new methods into the study of a classical object — for example, the decision to use thermodynamic methods to organize the study of van Kampen diagrams — bends the focus of the investigation towards those examples and contexts where the methods and tools are most informative. Phenomena familiar in one context (power laws, frequency locking, phase transitions etc.) suggest new questions and modes of enquiry in another. Uninspired or predictable research programs can benefit tremendously from such infusions, whether the new methods are borrowed from other intellectual disciplines (biology, physics), or depend on new technology (computers), or new methods of indexing (google) or collaboration (polymath).

One of my intellectual heroes — Wolfgang Haken — worked for eight years in R+D for Siemens in Munich after completing his PhD. I have a conceit (unsubstantiated as far as I know by biographical facts) that his experience working for a big engineering firm colored his approach to mathematics, and made it possible for him to imagine using industrial-scale “engineering” tools (e.g. integer programming, exhaustive computer search of combinatorial possibilities) to solve two of the most significant “pure” mathematical open problems in topology at the time — the knot recognition problem, and the four-color theorem. It is an interesting exercise to try to imagine (fantastic) variations. If I sit down and decide to try to prove (for example) Cannon’s conjecture, I am liable to try minor variations on things I have tried before, appeal for my intuition to examples that I understand well, read papers by others working in similar ways on the problem, etc. If I imagine that I have been given a billion dollars to prove the conjecture, I am almost certain to prioritize the task in different ways, and to entertain (and perhaps create) much more ambitious or innovative research programs to tackle the task. This is the way in which I understand the following quote by John Dewey, which I used as the colophon of my first book:

Every great advance in science has issued from a new audacity of the imagination.

A basic reference for the background to this post is my monograph.

Let be a group, and let denote the commutator subgroup. Every element of can be expressed as a product of commutators; the *commutator length* of an element is the minimum number of commutators necessary, and is denoted . The *stable commutator length* is the growth rate of the commutator lengths of powers of an element; i.e. . Recall that a group is said to satisfy a *law* if there is a nontrivial word in a free group for which every homomorphism from to sends to .

The purpose of this post is to give a very short proof of the following proposition (modulo some background that I wanted to talk about anyway):

**Proposition:** Suppose obeys a law. Then the stable commutator length vanishes identically on .

The proof depends on a duality between stable commutator length and a certain class of functions, called *homogeneous quasimorphisms*.

**Definition:** A function is a *quasimorphism* if there is some least number (called the* defect*) so that for any pair of elements there is an inequality . A quasimorphism is *homogeneous* if it satisfies for all integers .

Note that a homogeneous quasimorphism with defect zero is a homomorphism (to ). The defect satisfies the following formula:

**Lemma: **Let be a homogeneous quasimorphism. Then .

A fundamental theorem, due to Bavard, is the following:

**Theorem:** (Bavard duality) There is an equality where the supremum is taken over all homogeneous quasimorphisms with nonzero defect.

In particular, vanishes identically on if and only if every homogeneous quasimorphism on is a homomorphism.

One final ingredient is another geometric definition of in terms of Euler characteristic. Let be a space with , and let be a free homotopy class representing a given conjugacy class . If is a compact, oriented surface without sphere or disk components, a map is *admissible* if the map on factors through , where the second map is . For an admissible map, define by the equality in (i.e. is the degree with which wraps around ). With this notation, one has the following:

**Lemma:** There is an equality .

Note: the function is the sum of over non-disk and non-sphere components of . By hypothesis, there are none, so we could just write . However, it is worth writing and observing that for more general (orientable) surfaces, this function is equal to the function defined in a previous post.

We now give the proof of the Proposition.

*Proof.* Suppose to the contrary that stable commutator length does not vanish on . By Bavard duality, there is a homogeneous quasimorphism with nonzero defect. Rescale to have defect . Then for any there are elements with , and consequently by Bavard duality. On the other hand, if is a space with , and is a loop representing the conjugacy class of , there is a map from a once-punctured torus to whose boundary represents . The fundamental group of is free on two generators which map to the class of respectively. If is a word in mapping to the identity in , there is an essential loop in that maps inessentially to . There is a finite cover of , of degree depending on the word length of , for which lifts to an embedded loop. This can be compressed to give a surface with . However, Euler characteristic is multiplicative under coverings, so . On the other hand, so . If obeys a law, then is fixed, but can be made arbitrarily small. So does not obey a law. qed.

In a previous post, I discussed some methods for showing that a given group contains a (nonabelian) free subgroup. The methods were analytic and/or dynamical, and phrased in terms of the existence (or nonexistence) of certain functions on or on spaces derived from , or in terms of actions of on certain spaces. Dually, one can try to find a free group in by finding a homomorphism and looking for circumstances under which is injective.

For concreteness, let for some (given) space . If is a free group, a representation up to conjugation determines a homotopy class of map where is a . The most natural ‘s to consider are *graphs* and *surfaces* (with boundary). It is generally not easy to tell whether a map of a graph or a surface to a topological space is -injective at the topological level, but might be easier if one can use some geometry.

**Example**: Let be a complete Riemannian manifold with sectional curvature bounded above by some negative constant . Convexity of the distance function in a negatively curved space means that given any map of a graph one can flow by the negative gradient of total length until it undergoes some topology change (e.g. some edge shrinks to zero length) or it (asymptotically) achieves a local minimum (the adjective “asymptotically” here just means that the flow takes infinite time to reach the minimum, because the size of the gradient is small when the map is almost minimum; there are no analytic difficulties to overcome when taking the limit). A typical topological change might be some loop shrinking to a point, thereby certifying that a free summand of mapped trivially to and should have been discarded. Technically, one probably wants to choose to be a trivalent graph, and when some interior edge collapses (so that four points come together) to let the -valent vertex resolve itself into a pair of -valent vertices in whichever of the three combinatorial possibilities is locally most efficient. The limiting graph, if nonempty, will be trivalent, with geodesic edges, and vertices at which the three edges are all (tangentially) coplanar and meet at angles of . Such a graph can be certified as -injective provided the edges are sufficiently long (depending on the curvature ). After rescaling the metric on so that the supremum of the curvatures is , a trivalent geodesic graph with angles at the vertices and edges at least is -injective. To see this, lift to maps between universal covers, i.e. consider an equivariant map from a tree to . Let be an embedded arc in , and consider the image in . Using Toponogov’s theorem, one can compare with a piecewise isometric map from to . The worst case is when all the edges are contained in a single , and all corners “bend” the same way. Providing the image does not bend as much as a horocircle, the endpoints of the image of stay far away in . An infinite sided convex polygon in with all edges of length and all angles osculates a horocycle, so we are done.

**Remark**: The fundamental group of a negatively curved manifold is word-hyperbolic, and therefore contains many nonabelian free groups, which may be certified by pingpong applied to the action of the group on its Gromov boundary. The point of the previous example is therefore to certify that a certain subgroup is free in terms of local geometric data, rather than global dynamical data (so to speak). Incidentally, I would not swear to the correctness of the constants above.

**Example**: A given free group is the fundamental group of a surface with boundary in many different ways (this difference is one of the reasons that a group like is so much more complicated than the mapping class group of a surface). Pick a realization . Then a homomorphism up to conjugacy determines a homotopy class of map from to as above. If is negatively curved as before, each boundary loop is homotopic to a unique geodesic, and we may try to find a “good” map with boundary on these geodesics. There are many possible classes of good maps to consider:

- Fix a conformal structure on and pick a harmonic map in the homotopy class of . Such a map exists since the target is nonpositively curved, by the famous theorem of Eells-Sampson. The image is real analytic if is, and is at least as negatively curved as the target, and therefore there is an
*a priori*upper bound on the intrinsic curvature of the image; if the supremum of the curvature on is normalized to be , then the image surface is , which just means that pointwise it is at least as negatively curved as hyperbolic space. By Gauss-Bonnet, one obtains an*a priori*bound on the area of the image of in terms of the Euler characteristic (which just depends on the rank of ). On the other hand, this map depends on a choice of marked conformal structure on , and the space of such structures is noncompact. - Vary over all conformal structures on and choose a harmonic map of least energy (if one exists) or find a sequence of maps that undergo a “neck pinch” as a sequence of conformal structures on degenerates. Such a neck pinch exhibits a
*simple*curve in that is essential in but whose image is inessential in ; such a curve can be compressed, and the topology of simplified. Since each compression increases , after finitely many steps the process terminates, and one obtains the desired map. This is Schoen-Yau‘s method to construct a stable minimal surface representative of . When the target is -dimensional, the surface may be assumed to be unbranched, by a trick due to Osserman. - Following Thurston, pick an ideal triangulation of (i.e. a geodesic lamination of whose complementary regions are all ideal triangles); since has boundary, we may choose such a lamination by first picking a triangulation (in the ordinary sense) with all vertices on and then “spinning” the vertices to infinity. Unless factors through a cyclic group, there is some choice of lamination so that the image of can be straightened along the lamination, and then the image spanned with ideal triangles to produce a
*pleated surface*in representing (note: if has constant negative curvature, these ideal triangles can be taken to be totally geodesic). The space of pleated surfaces in fixed (closed) of given genus is compact, so this is a reasonable class of maps to work with. - If is merely a hyperbolic group, one can still construct pleated surfaces, not quite in , but equivariantly in Mineyev’s flow space associated to . Here we are not really thinking of the triangles themselves, but the geodesic laminations they bound (which carry the same information).
- If is complete and -dimensional but noncompact, the space of pleated surfaces of given genus is generally not compact, and it is not always easy to find a pleated surface where you want it. This can sometimes be remedied by
*shrinkwrapping*; one looks for a minimal/pleated/harmonic surface subject to the constraint that it cannot pass through some prescribed set of geodesics in (which act as “barriers” or “obstacles”, and force the resulting surface to end up roughly where one wants it to).

Anyway, one way or another, one can usually find a map of a surface, or a space of maps of surfaces, representing a given homomorphism, with some kind of *a priori* control of the geometry. Usually, this control is *not* enough to certify that a given map is -injective, but sometimes it might be. For instance, a totally geodesic (immersed) surface in a complete manifold of constant negative curvature is always -injective, and any surface whose extrinsic curvature is small enough will also be -injective.

Geometric methods to certify injectivity of free or surface groups are very useful and flexible, as far as they go. Unfortunately, I know of very few *topological* methods to certify injectivity. By far the most important exception is the following:

**Example**: In -dimensions, one should look for *properly embedded* surfaces. If is a -manifold (possibly with boundary), and is a two-sided properly embedded surface, the famous *Dehn’s Lemma *(proved by Papakyriakopoulos) implies that either is -injective, or there is an *embedded* essential loop in that bounds an embedded disk in on one side of . Such a loop may be compressed (i.e. may be cut open along the loop, and two copies of the compressing disk sewn in) preserving the property of embeddedness, but increasing . After finitely many steps, either compresses away entirely, or one obtains a -injective surface. One way to ensure that does not compress away entirely is to start with a surface that is essential in (relative) homology; another way is to look for a surface dual to an action (of ) on a tree. In the latter case, one can often construct quite different free subgroups in by pingpong on the ends of the tree. Note by the way that this method produces *closed* surface subgroups as well as free subgroups. Note too that two-sidedness is essential to apply Dehn’s Lemma.

**Remark**: Modern -manifold topologists are sometimes unreasonably indifferent to the power of Dehn’s Lemma (probably because this tool has been incorporated so fully into their subconscious?); it is worth reading Ralph Fox’s review of Papakyriakopoulos’s paper (linked above). Of this paper, he writes:

. . . it has already led to renewed attack on the problem of classifying the 3-dimensional manifolds; significant results have been and are being obtained. A complete solution has suddenly become a definite possibility.

Remember this was written more than 50 years ago — before the geometrization conjecture, before the JSJ decomposition, before the Scott core theorem, before Haken manifolds. The only reasonable reaction to this is: !!!

**Example**: The construction of injective surfaces by Dehn’s Lemma may be abstracted in the following way. Given a target space , and a class of maps of surfaces into (in some category; e.g. homotopy classes of maps, pleated surfaces, surfaces, etc.) suppose one can find a complexity with values in some ordered set, such that if is not injective, one can find of smaller complexity. Then if is well-ordered, an injective surface may be found. If is not well-ordered, one may ask at least that is upper semi-continuous on , and hope to extend it upper semi-continuously to some suitable compactification of . Even if is not well-ordered, one can at least *certify* that a map is injective, by showing that it minimizes . Here are some potential examples (none of them entirely satisfactory).

- Given a (homologically trivial) homotopy class of loop in , one can look at all maps of orientable surfaces to with boundary factoring through . For such a surface, let denote the degree with which the (possibly multiple) boundary (components) of wrap homologically around , and let denote the sum of Euler characteristics of non-disk and non-sphere components of . For each surface , one considers the quantity (the factor of can be ignored if desired). The important feature of this quantity is that it does not change if is replaced by a finite cover. If is not injective, let be an essential loop on whose image in is inessential. Peter Scott showed that any essential loop on a surface lifts to an embedded loop in some finite cover. Hence, after passing to such a cover, may be compressed, and the resulting surface satisfies . In other words, a global minimizer of this quantity is injective. Such a surface is called extremal. The problem is that extremal surfaces do not always exist; but this construction motivates one to look for them.
- Given a surface with geodesic boundary in , one can retract to a geodesic spine, and encode the surface by the resulting fatgraph, with edges labelled by homotopy classes in . Since Euler characteristic is local, one does not really care precisely how the pieces of the fatgraph are assembled, but only how many pieces of what kinds are needed for a given boundary. So if only finitely many such pieces appear in some infinite family of surfaces, one can in fact construct an extremal surface as above, which is necessarily injective (more technically, one reduces the computation of Euler characteristic to a linear programming problem, finds a rational extremal solution (which corresponds to a weighted sum of pieces of fatgraph), and glues together the pieces to construct the extremal surface; one situation in which this scheme can be made to work is explained in this paper of mine). Edges can be subdivided into a finite number of possibilities, so one just needs to ensure finiteness of the number of vertex types. One condition that ensures finiteness of vertex types is the existence of a uniform constant so that for each surface in the given family, and for each point , there is an estimate . If this condition is violated, one finds pairs which converge in the geometric topology to a point in a
*complete*(i.e. without boundary, but probably noncompact) surface. - Given , either compress an embedded essential loop, or realize by a least area surface. If is not injective, pass to a cover, compress a loop, and realize the result by a least area surface. Repeat this process. One obtains in this way a sequence of least area surfaces in (typically of bigger and bigger genus) and there is no reason to expect the process to terminate. If is a -manifold, the curvature of a least area surface admits two-sided curvature bounds away from the boundary, by a theorem of Schoen (near the boundary, the negative curvature might blow up, but only in controlled ways — e.g. after rescaling about a sequence of points with the most negative curvature, one may obtain in the limit a helicoid). Away from the boundary, the family of surfaces one obtains vary precompactly in the topology, and one may obtain a complete locally least area lamination in the limit. If is not injective, one can continue to pass to covers (applying a version of Scott’s theorem for infinite surfaces) and compress, and by transfinite induction, eventually arrive at a locally least area lamination with injective . Of course, such a limit might well be a lamination by planes. However, the lamination one obtains is not completely arbitrary: since it is a limit of limits of . . . compact surfaces, one can choose a limit that admits a nontrivial invariant transverse measure (one must be careful here, since the lamination will typically have boundary). Or, as in bullet 2. above, one may insist that this limit lamination is complete (i.e. without boundary).

It is more tricky to find a limit lamination as in 3. without boundary and admitting an invariant transverse measure; in any case, this motivates the following:

**Question**: Is there a closed hyperbolic -manifold which admits a locally least area transversely measured complete immersed lamination , all of whose leaves are disks? (note that the answer is negative if one asks for the lamination to be *embedded *(there are several easy proofs of this fact)).

Secretly, the function that assigns to a homologically trivial loop is the *stable commutator length* of the conjugacy class in represented by . Extremal surfaces can sometimes be certified by constructing certain functions on called *homogeneous quasimorphisms*, but a discussion of such functions will have to wait for another post.

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:

- if (i.e. the average of a non-negative function is non-negative)
- where is the constant function taking the value everywhere on (i.e. the average of the constant function is normalized to be )
- 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

- Finite groups
- Abelian groups
- Unions and extensions of amenable groups
- 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).

## The (strengthened) Hanna Neumann Conjecture

May 29, 2009 in Commentary, Groups | Tags: free groups, graphs, Hanna Neumann Conjecture | by Danny Calegari | 1 comment

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

linearas 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

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