**The Algorithm**

**1)**Build a LIST of 3-manifold triangulations, and initialize LIST to contain only TRI. Inductively, enumerate the normal 2-spheres in the triangulations in LIST. On each normal 2-sphere we perform the crushing operation (collapsing the sphere to a point in the manifold). This turns your 3-manifold into a wedge sum of other 3-manifolds which have less complex triangulations in the sense of number of tetrahedra (I’ll return to this). Replace each triangulation from LIST by these wedge summands and repeat this process until none of the 3-manifolds in your LIST contain normal 2-spheres. Of course, if your manifold was an the crushing operation might have converted it into an with two points identified — but you could have computed the homology beforehand and noticed your manifold wasn’t a homology sphere to begin with. And every 3-manifold has normal 2-spheres, the vertex-linking ones. We ignore those.

**2)**A 3-manifold triangulation with no normal 2-spheres is the 3-sphere if and only if it contains an almost-normal 2-sphere. So you just check the manifolds of LIST to ensure they all have almost-normal 2-spheres. If you’re not familiar with almost-normal surfaces, conceptually the way to think about them is that they are the “intermediate” surfaces one needs if you are interested in the isotopy relation among normal surfaces, or more generally the embedded-surgery relation among normal surfaces. They are also enumerable in terms of integer programming problems, much like normal surfaces.

**That’s it. That’s the algorithm.** You can turn it into an algorithm to find the connect-sum decomposition of a 3-manifold, since that’s essentially what you’re doing. There are a few qualifiers I’ve neglected to tell you. The big one is the crushing operation I’ve left vague. That’s because it’s an especially brutal version of crushing that Jaco and Rubinstein use — and it’s brutality is a rather lovely feature. Below is a picture I’ve stolen from Ben Burton’s recent paper.

When you crush a normal 2-sphere, a tetrahedron can be converted into a variety of things. Ben calls these respectively: tetrahedra, purses and footballs. The crushing operation turns the footballs into edges and purses into triangles, and of course you keep the tetrahedra. So when you crush in this manner you sometimes eliminate summands that are non-trivial manifolds. It turns out the “damage” you can do in this way is quite limited, crushing can eliminate , and summands, but that is all — otherwise it faithfully computes the connect sum decomposition.

This version of the 3-sphere recognition algorithm appears Rubinstein and Jaco’s 0-efficiency paper:

The 3-sphere recognition and connect-sum algorithms are implemented in the software Regina. Here is a link to the code for its implementation. You might find the code easier to read than my blogpost!

The “crushing” operation can alternatively be described in terms of the dual spine. In those terms, you just split the sheets of the dual spine into multiple copies in a pretty intuitive way, and you don’t need the brutal operations. The 3 manifolds you listed are those which have a simple spine with no vertices.

Comment by Dylan Thurston — May 31, 2013 @ 9:06 pm |

Hi, just a note: in step (1) you only need to find one normal sphere for each triangulation in LIST, not all. This has a surprisingly good impact on the running time – essentially you can solve a single non-convex optimisation problem (maximise Euler characteristic) to avoid an expensive enumeration of all vertex normal surfaces, and when done the right way this collapses to a polynomial-time search surprisingly often.

(For reference: the full pseudocode for 3-sphere recognition as it looks today is in arXiv:1208.2504, algorithm 3.2, and the optimisation techniques are in arXiv:1211.1079.)

Comment by Benjamin Burton — June 2, 2013 @ 8:59 pm |