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^{3} x S^{1}). 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_{2}(ℂ) 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 ℤ^{2}. 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.

Initially, the reference to Manning’s algorithm was missing. It has now been added.

Comment by Henry Wilton — January 27, 2010 @ 12:39 pm |

In Nathan Dunfields August 31, 2009 post on the Virtual Haken Conjecture he mentioned Conjecture 7, that all closed hyperbolic manifold fundamental groups are LERF. So are LERF groups recursively enumerable with solvable isomorphism problem, or do they suffer from the same problem as three manifold groups in general, that is that they are too well behaved to be recursive?

Comment by Mayer A. Landau — January 27, 2010 @ 1:49 pm |

LERF groups have solvable word problem. In fact all residually finite groups do, for a slightly silly reason: list all possible maps to finite groups; if your element is non-trivial, eventually you’ll find a map under which its image is non-trivial. So the same argument shows that LERF groups are not recursive.

This leaves open the (very faint) possibility that they could be recursively enumerable and/or have solvable isomorphism problem. Off the top of my head, I don’t know any classes of groups that are known NOT to be recursively enumerable. But if LERF groups were recursively enumerable that would suggest that they had some sort of structure theory, and it’s very hard to imagine what that would look like.

I would bet my house (if I had one) that the isomorphism problem is not solvable for LERF groups. However, I don’t think we have the technology to prove it, at this point. Constructions of LERF groups are still quite thin on the ground.

Comment by Henry Wilton — January 27, 2010 @ 2:27 pm |

In your section on RECURSIVE ENUMERABILITY you state that all 3-manifold fundamental groups are recursively enumerable due to Moise’s triangulation theorem. But, then you state that the recursive enumerability of hyperbolic 3-manifold fundamental groups is due to Manning. What did Manning have to prove if it already follows from Moise?

Comment by Mayer A. Landau — January 27, 2010 @ 5:51 pm |

It doesn’t follow from Moise. I think you’re assuming that any subclass of a recursively enumerable class is recursively enumerable – but this isn’t true. For instance, the class of all finitely presented groups is recursively enumerable, for silly reasons!

But there are plenty of classes of finitely presentable groups that are not recursively enumerable. In a comment above, I said that I couldn’t think of any, but I was overlooking the fact that the argument in the RECURSIVENESS section shows that the class of all ‘not 3-manifold’ groups is not recursively enumerable! Similarly, if P is any recursively enumerable Markov property then the class of groups with not P is not recursively enumerable.

Comment by Henry Wilton — January 27, 2010 @ 6:01 pm |

That’s kind of weird that a subclass of a recursively enumerable class does not need to be recursively enumerable. So from your definition, in the general case, the Turing machine does not know how to restrict the presentations it puts out in order to conform to some arbitrary subclass.

Comment by Mayer A. Landau — January 28, 2010 @ 12:53 am |

Exactly!

Comment by Henry Wilton — January 28, 2010 @ 12:57 am |

OK, but how about the isomorphism recognition problem. From your discussion it seems that that does respect subclasses. So if 3-manifold groups have an isomorphism recognition algorithm, as you show, then any subclass will as well. So LERF groups that are also 3-manifold groups have an isomorphism problem that is solvable. Is that a correct statement?

Comment by Mayer A. Landau — January 28, 2010 @ 2:22 am |

That is correct. But there are many LERF groups that are not 3-manifold groups.

Comment by Henry Wilton — January 28, 2010 @ 11:39 am |

When you say “A class of finitely presentable groups is recursive if both it and its complement are recursively enumerable”, I assume that you are taking complements in the set (or is it class?) of all finitely presentable groups. Is that correct?

Comment by Mayer A. Landau — January 28, 2010 @ 3:20 pm |

Yes.

Comment by Henry Wilton — January 28, 2010 @ 3:32 pm |

[...] by this post in blog Low-Dimensional Topology about low-dimensions and logic. Categories: Research Musings [...]

Pingback by Low-Dimensions and the Isometric Embedding Problem « Mathematics Expressions — April 26, 2010 @ 9:33 am |