3-manifold groups are known, right?

During the nice talk that Ian Biringer gave on the structure of hyperbolic 3-manifolds at Caltech on Friday, a 4-manifold theorist in the back was heard to ask ‘3-manifold groups are known, right?’

I know what he meant. Any finitely presented group can arise as the fundamental group of a 4-manifold (this is a nice exercise that you can do for yourself, involving surgery on a connect sum of copies of S³ x S¹). With a little care, you can deduce that classifying topological 4-manifolds is at least as impossible as classifying finitely presented groups (which is impossible).

In contrast, there are constraints on the fundamental groups of closed 3-manifolds. One of the first is an easy consequence of the existence of Heegaard splittings: any closed 3-manifold group admits a balanced presentation, meaning that there are no more relations than generators.

What does it mean to ‘know’ a class of finitely presentable groups? Do we really ‘know’ the class of (orientable) 3-manifold groups? The point of view that I will adopt in addressing these questions is algorithmic, and comes from combinatorial group theory.

Dehn formulated the three classical decision problems that are often the most basic questions that one asks about a class of groups.

1. The word problem. Is there an algorithm to determine whether or not a given a word in the generators represents the identity?

2. The conjugacy problem. Is there an algorithm to determine whether or not a pair of words in the generators are conjugate?

3. The isomorphism problem. Is there an algorithm to determine whether or not a pair of presentations of groups in the class present isomorphic groups?

The first two of these questions are rather local in nature, as they deal with individual elements of groups. I won’t say much further about them, except to comment that geometrisation implies that both are solvable (the word problem is essentially due to Waldhausen; the solution to the conjugacy problem doesn’t seem to be very well known, and is due to Préaux), and that neither is known in the absence of geometrisation.

Instead, I want to situate the isomorphism problem in the context of some other basic algorithmic properties of classes of groups.

4. A class of finitely presentable groups is recursively enumerable if there is a Turing machine that outputs a list of presentations such that every presentation represents a group in the class and every group is represented by some presentation on the list.

This means that we can eventually confirm that a given group G is in our class: using Tietze transformations, we can modify our list so that eventually every presentation of every group in our class appears; just wait for the given presentation of G to appear. Note that if G isn’t in our class then this procedure will run forever.

5. A class of finitely presentable groups is recursive if both it and its complement are recursively enumerable.

If this is true, then we can eventually determine whether or not a given group G is in our class of groups.

Thinking about it like this, we can reformulate the isomorphism problem in the following way.

3′. A class of groups is recursively enumerable and has solvable isomorphism problem if and only if there is a Turing machine that outputs a list of presentations for the groups in the class such that each group appears exactly once on the list.

In the remainder of this post, I’ll try to explain what I know about these problems for 3-manifold groups.

RECURSIVE ENUMERABILITY

This is an easy consequence of Moise’s famous theorem that 3-manifolds can be triangulated. Just build a Turing machine that lists all 3-dimensional simplicial complexes. It is easy to check whether the link of every vertex is a combinatorial 2-sphere. A complex with this property represents a 3-manifold, and conversely Moise’s Theorem implies that every 3-manifold can be represented in this way. You can easily read off a presentation for the fundamental group from such a triangulation.

We could also do this using the existence of Heegaard splittings, which is a consequence of Moise’s Theorem.

More interestingly, the class of hyperbolic 3-manifold groups is recursively enumerable. This is an immediate consequence of a beautiful theorem of Jason Fox Manning, which provides an algorithm that finds a faithful discrete representation of the fundamental group to PSL₂(ℂ) if one exists [9].

RECURSIVENESS

Slightly counter-intuitively, the class of 3-manifold groups is too well behaved to be recursive.

It is a fundamental (though not easy!) fact about finitely presented groups that there is no algorithm to determine whether such a group is trivial.

Suppose now that the class of 3-manifold groups is recursive, so there is an algorithm to determine whether a given presentation represents the fundamental group of some 3-manifold. Applying this algorithm to an arbitrary presentation P, we can determine whether P presents a 3-manifold group or not. But the trivial group is a 3-manifold group, and we can easily use the solution to the word problem for 3-manifold groups to determine which 3-manifold groups are trivial. Putting these two observations together would give an algorithm to determine whether a given group is trivial, which is known to be impossible.

This argument is very general. In fact, a property of groups P is called Markov if some finitely presentable group has P and some other finitely presentable group cannot be embedded in any group with P. If P is Markov then the class of groups with P is not recursive.

Thus, there is a curious sense in which we understand 4-manifold groups better than 3-manifold groups! The class of 4-manifold groups is recursive, for vacuous reasons.

THE ISOMORPHISM PROBLEM

Having seen that recursiveness was far too much to hope for, let’s turn our attention to our final decidability property: the isomorphism problem.

I will sketch an outline of the solution to the isomorphism problem for 3-manifold groups. This is all from the point of view of a geometric group theorist, so I’ll mostly restrict my tools to geometrisation, a few other basic facts about 3-manifolds, and some quite powerful recent group-theoretic results.

After starting to write this post, I discovered that William H. Jaco has a nice series of lecture notes available on the Homeomorphism Problem for 3-manifolds. You should look at Jaco’s notes if you want to understand the ‘right’ way of doing this.

The first step is to compute the Kneser–Milnor decomposition. Every orientable 3-manifold decomposes (more or less uniquely) as a connect sum

where each M_i is irreducible, ie contains no essential 2-sphere. Correspondingly, the fundamental group of M has a unique Grushko decomposition as

where F_r is a free group of rank r. Nowadays, one can compute this decomposition from very general considerations. Nicholas Touikan showed how to compute the Grushko decomposition of any group Γ, given nothing more than a solution to the word problem in Γ [12].

This reduces the problem to the case of irreducible 3-manifolds. Geometrisation tells us that any such 3-manifold M satisfies (at least) one of the following.

1. M is hyperbolic.
2. M is elliptic, ie finitely covered by the 3-sphere.
3. M is Seifert-fibred. (This actually includes case 2, but it might be better to think of the case with infinite fundamental group separately.)
4. M contains an essential torus. (Again, there is some overlap between 3 and 4.)

Let’s deal with these cases one by one.

1. M is hyperbolic

If our 3-manifold is hyperbolic then Manning’s algorithm will eventually find a hyperbolic structure. Another, less subtle, approach to the problem of certifying that M is hyperbolic would be to use an algorithm of Panos Papazoglou [10] to find a word-hyperbolic structure on the fundamental group. Geometrisation implies that the fundamental group is word-hyperbolic if and only if M is hyperbolic or elliptic, and given a word-hyperbolic structure one can determine which case we fall into.

The isomorphism problem for the fundamental groups of closed hyperbolic 3-manifolds was solved by Zlil Sela [11]. I won’t discuss his beautiful solution here, except to comment that it relies on the fact that one can algorithmically solve systems of equations and inequations over word-hyperbolic groups.

We also need to deal with the finite-volume case, which will be important later. I’m not sure whether Manning’s algorithm can be generalised to this case, but Dahmani extended Papazoglou’s algorithm to the ‘finite-volume’ group-theoretic setting, namely relatively hyperbolic groups [2]. Again, geometrisation implies that the fundamental group admits a hyperbolic structure relative to its maximal virtually abelian subgroups if and only if M is hyperbolic of finite volume or elliptic, and we can determine which case we’re in.

Finally, Sela’s solution to the isomorphism problem was generalised to the relatively hyperbolic case by Francois Dahmani and Daniel Groves [3]. So, in summary, the fundamental groups of finite-volume hyperbolic manifolds are recursively enumerable with solvable isomorphism problem.

2. M is elliptic if and only if the fundamental group is finite. In this case, a naive computation of the multiplication table will eventually prove that the fundamental group is finite. (Note that this procedure will not terminate if the group is not finite, but we don’t have to worry about this!) For similarly naive reasons, the isomorphism problem is solvable for finite groups.

There’s a point here that needs to be made clear. All of this is done using a solution to the word problem, which is only known in the presence of geometrisation. On the other hand, algorithms are known that recognise the 3-sphere in the absence of geometrisation. You could say that the difficulty of the Poincare Conjecture lies in recognising that your manifold is simply connected, rather than in recognising that it’s the 3-sphere (though perhaps that’s too glib).

3. M is Seifert-fibred.

A 3-manifold M is Seifert-fibred if and only if it can be foliated by circles [4], which occurs if and only if the fundamental group Γ has a cyclic normal subgroup K [1,5], generated by a generic fibre. Given the fundamental group of a Seifert-fibred 3-manifold, we will always eventually find K by a naive search.

The quotient Q=Γ/K is the fundamental group of a 2-dimensional orbifold O. To check whether another Seifert-fibred group is isomorphic to Γ, we need to compute the Euler number of the bundle (which can be read off a suitable presentation) and to solve the isomorphism problem for the base orbifold O.

This reduces the problem to the isomorphism problem for 2-orbifold groups, which is certainly known (although I don’t know a reference). For instance, one can find a torsion-free normal subgroup, use the index to bound the torsion, and then check finitely many possibilities.

4. M contains an essential torus.

Closed, orientable, irreducible 3-manifolds have a canonical torus decomposition, due to Jaco–Shalen [6] and, independently, Johannsson [8]. This consists of a minimal collection of essential embedded tori, such that the complementary pieces are either Seifert-fibred or atoroidal, (meaning that every essential embedded immersed torus is boundary parallel).

Geometrisation asserts that the atoroidal pieces are either elliptic or hyperbolic.

The final remaining piece of the puzzle is therefore to compute the torus decomposition of M. An algorithm to compute the torus decomposition of a 3-manifold was described by Jaco and Tollefson [7]. However, it turns out that we already have enough machinery at our disposal to compute the torus decomposition in a simple-minded fashion.

Essential tori correspond to splittings of our group Γ as an amalgamated product or HNN extension over ℤ². A naive enumeration of presentations for Γ will eventually find one that exhibits such a splitting. So ‘cut’ along this torus and repeat. We are done when every piece is either Seifert-fibred or (finite-volume) hyperbolic. As we have seen above, we have procedures that will eventually confirm if our manifold is Seifert-fibred or hyperbolic! Thus, running all these tests in parallel, we will eventually find a finite number of splittings and discover that all the remaining pieces are Seifert-fibred or hyperbolic, as required.

It’s possible that in this process we will ‘overshoot’, and discover a set of tori that is not minimal. In other words, we might accidentally cut along an essential torus in the interior of a Seifert-fibred piece. Therefore, at the end we need to check whether the Seifert-fibred structures of any pieces on either side of each torus are compatible – if they are, we should remove this torus and glue the pieces on either side together.

Once this is done, to check isomorphism is mostly just a matter of checking that the decomposition is the same and that the individual pieces are isomorphic, each of which (appealing to geometrisation and Dahmani–Groves) we already know how to do.

As occurs very often in 3-manifold theory, manifolds finitely covered by torus bundles over the circle form an important exceptional case. Some of these bundles do not admit a Seifert-fibred structure and so have non-trivial torus decomposition, but they are better thought of as lattices in the Lie group Sol. It turns out that, with a few explicit exceptions, such an M actually is a torus bundle, and so is determined by the conjugacy class of its monodromy. This is enough to solve the isomorphism problem in this case.

This completes my take on the isomorphism problem for 3-manifold groups. I want to reiterate that there are many other ways to do this, that I’ve skated over various details, and that this solution is sub-optimal in various senses. Comments, corrections and clarifications welcome!

REFERENCES

[1] Casson, Andrew and Jungreis, Douglas. Convergence groups and Seifert fibered 3-manifolds. Invent. Math. 118 (1994), no. 3, 441–456.

[2] Dahmani, François. Finding relative hyperbolic structures. Bull. Lond. Math. Soc. 40 (2008), no. 3, 395–404.

[3] Dahmani, François and Groves, Daniel. The isomorphism problem for toral relatively hyperbolic groups. Publ. Math. Inst. Hautes Études Sci. No. 107 (2008), 211–290.

[4] Epstein, D. B. A. Periodic flows on three-manifolds. Ann. of Math. (2) 95 1972 66–82.

[5] Gabai, David. Convergence groups are Fuchsian groups. Ann. of Math. (2) 136 (1992), no. 3, 447–510.

[6] Jaco, William and Shalen, Peter B. A new decomposition theorem for irreducible sufficiently-large 3-manifolds. Algebraic and geometric topology (Proc. Sympos. Pure Math., Stanford Univ., Stanford, Calif., 1976), Part 2, pp. 71–84, Proc. Sympos. Pure Math., XXXII, Amer. Math. Soc., Providence, R.I., 1978.

[7] Jaco, William and Tollefson, Jeffrey L. Algorithms for the complete decomposition of a closed 3-manifold. Illinois J. Math. 39 (1995), no. 3, 358–406.

[8] Johannson, Klaus. Homotopy equivalences of 3-manifolds with boundaries.
Lecture Notes in Mathematics, 761. Springer, Berlin, 1979. ii+303 pp. ISBN: 3-540-09714-7

[9] Manning, Jason. Algorithmic detection and description of hyperbolic structures on closed 3-manifolds with solvable word problem. Geom. Topol. 6 (2002), 1–25

[10] Papasoglu, P. An algorithm detecting hyperbolicity. Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), 193–200, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996.

[11] Sela, Z. The isomorphism problem for hyperbolic groups. I. Ann. of Math. (2) 141 (1995), no. 2, 217–283.

[12] Touikan, Nicholas W. M. Effective Grushko Decompositions, arXiv:0906.3902.