MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read this interview with Ian Agol, where he says:

"...I learned that Thurston’s geometrization theorem allowed a complete and practical classification of knots."

My question is:

How does this work exactly? Is this written up somewhere?

I know that every knot in $S^3$ is either a torus knot, a satellite knot or a hyperbolic knot. But as far as I know this is not practical.

(I understand practical as follows: Given a knot diagram, there is a way to find out in which of these 3 classes the knot fits. And given two knots in the same class, there is a way to say if they are the same or not.)

share|cite|improve this question
up vote 12 down vote accepted

You have all the tools to compute the geometric decomposition of knot and link exteriors in the software Regina. I'm one of the authors, although my hands haven't been over that part of the code very much. Most of the 3-manifold decomposition code was written by Ben Burton. The algorithms are primarily due to people like Rubinstein and Jaco, although Ben has done quite a lot of work to find efficient implementations of these algorithms.

Regina uses SnapPea for the hyperbolic manifolds. In a pretty strong sense it is a practical algorithm. The only part of this software for which run-time estimates do not exist is the usage of SnapPea, but in practice it is extremely fast. The primary issue with SnapPea as an algorithm is that it's not known whether SnapPea will always find a hyperbolic structure on knot and link exteriors which are hyperbolisable -- one of the key problems is finding an appropriate triangulation on which the gluing equations have a solution. I believe the precise mathematical question here is whether or not hyperbolisable 1-cusped manifolds admit an ideal triangulation. It's known such manifolds admit ideal Epstein-Penner decompositions but the facets are not always tetrahedra. One may not be able to subdivide these objects into ideal tetrahedra.

Computing the satellite decomposition tends to be slow but most of the time (as long as your diagrams aren't very complicated, say, over 50 crossings) then it performs quite well. The algorithms here tend to be exponential run time.

One of my favourite statements of geometrization for knot and link exteriors is in terms of "splicing". I wrote a survey paper on the topic.

Here is an example of using geometrization of link exteriors to answer a basic question.

share|cite|improve this answer

Edited to reflect Igor's correction.

The precise computational complexity of the homeomorphism problem (even for knot complements in the three-sphere) is not known. It follows from work of Haken, Hemion, and Matveev that the problem for Haken manifolds is decidable (and in fact elementary recursive). Since knot complements are automatically Haken manifolds, this gives one answer to your final question (the homeomorphism problem for knots of the same type). One reference for this approach is Matveev's book "Algorithmic Topology and Classification of 3-Manifolds".

A solution to the homeomorphism problem can also be deduced from the geometrization conjecture (proven by Perelman, Hamilton). In fact, since knot complements are Haken, Thurston's earlier proof also applies. Everybody expects that the approach using geometry will be at worst simply exponential, but this is not yet proven. Igor and Ryan have already mentioned the "unreasonable effectiveness" of SnapPea/snappy and regina so I'll just leave you with several links.

See these MO questions (and this one), Matveev's book, and the program snappy for further information. The link to regina is in Ryan's answer.

share|cite|improve this answer

I don't understand Sam Nead's statement. [He has since addressed this, but I will leave the beginning of this for context] The decidability of the homeomorphism problem for knot complements was claimed by Haken, and written down by Hemion long before geometrization was proved. One may argue that this is not "practical", but no algorithm is, while (as pointed out in the links given by Sam Nead), SnapPea essentially never fails for knots with a reasonable number of crossings. Furthermore, Alexander polynomial is polynomial time, and almost always distinguishes knots (in particular, by computing a table of Alexander polynomials for torus knots, one can usually confirm that the knot is not a torus knot. Edit in fact, the Alexander polynomial of a satellite is reducible, so if your Alexander polynomial is irreducible, you are hyperbolic.

share|cite|improve this answer
    
Dear Igor - Fair point - I'll edit my answer. However, we can't say that the answer was "written down by Hemion". His book is actively wrong in many places. See Scharlemann's MathSciNet review of the book. – Sam Nead Jan 17 at 18:09
    
@SamNead Fair point... But, from the other point, as you know well, you don't need Perelman for knots -the Haken theorem is sufficient (I did not mention it because Thurston's thing was less complete than Haken's, but I guess Otals write-up was complete). – Igor Rivin Jan 17 at 18:13
    
In your comment after "edit" I think some qualifiers have been stripped. A satellite knot's alexander polynomial is a product of Alexander polynomials of the companions (suitably re-parametrized) and the "pattern" link. But it's possible that only one of these ingredient Alexander polynomials might be non-trivial. So a satellite knot can still have an irreducible Alexander polynomial. For example, take the connect sum of a knot whose Alexander polynomial is irreducible and a knot that has trivial Alexander polynomial. This is a satellite with irreducible Alexander polynomial. – Ryan Budney Jan 17 at 23:48
    
@RyanBudney true, it is not so much the qualifiers as the logic that is somewhat convoluted. What I am actually thinking is that (a) a random knot will have irreducible Alexander Polynomial [where random can be defined in a number of ways, but that statement should be invariant under the definition] and that (b) as a practical matter, when you see that the AP is irreducible, you should endeavor to find the hyperbolic structure, while if it is reducible, you should try to find the torus (which is a fairly hard problem, as you say yourself). – Igor Rivin Jan 18 at 0:10
    
There is the variety of "random knot" that comes from using random walks in $\mathbb R^3$. These tend to all have a large number of trefoil summands, more than anything else. – Ryan Budney Jan 18 at 19:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.