Are there any very hard unknots?

Question

Some years ago I took a long piece of string, tied it into a loop, and tried to twist it up into a tangle that I would find hard to untangle. No matter what I did, I could never cause the later me any difficulty. Ever since, I have wondered whether there is some reasonably simple algorithm for detecting the unknot. I should be more precise about what I mean by "reasonably simple": I mean that at every stage of the untangling, it would be clear that you were making the knot simpler.

I am provoked to ask this question by reading a closely related one: can you fool SnapPea? . That question led me to a paper by Kauffman and Lambropoulou, which appears to address exactly my question: http://www.math.uic.edu/~kauffman/IntellUnKnot.pdf , since they define a diagram of the unknot to be hard if you cannot unknot it with Reidemeister moves without making it more complicated. For the precise definition, see page 3, Definition 1.

A good way to understand why their paper does not address my question (by the way, when I say "my" question, I am not claiming priority -- it's clear that many people have thought about this basic question, undoubtedly including Kauffman and Lambropoulou themselves) is to look at their figure 2, an example of an unknot that is hard in their sense. But it just ain't hard if you think of it as a three-dimensional object, since the bit of string round the back can be pulled round until it no longer crosses the rest of the knot. The fact that you are looking at the knot from one particular direction, and the string as it is pulled round happens to go behind a complicated part of the tangle is completely uninteresting from a 3D perspective.

So here's a first attempt at formulating what I'm actually asking: is there a generalization of the notion of Reidemeister moves that allows you to pull a piece of string past a whole chunk of knot, provided only that that chunk is all on one side, so to speak, with the property that with these generalized Reidemeister moves there is an unknotting algorithm that reduces the complexity at every stage? I'm fully expecting the answer to be no, so what I'm really asking for is a more convincing unknot than the ones provided by Kauffman and Lambropoulou. (There's another one on the Wikipedia knot theory page, which is also easily unknotted if you allow slightly more general moves.)

I wondered about the beautiful Figure 5 in the Kauffman-Lambropoulou paper, but then saw that one could reduce the complexity as follows. (This will be quite hard to say in words.) In that diagram there are two roughly parallel strands in the middle going from bottom left to top right. If you move the top one of these strands over the bottom one, you can reduce the number of crossings. So if this knot were given to me as a physical object, I would have no trouble in unknotting it.

With a bit of effort, I might be able to define what I mean by a generalized Reidemeister move, but I'm worried that then my response to an example might be, "Oh, but it's clear that with that example we can reduce the number of crossings by a move of the following slightly more general type," so that the example would merely be showing that my definition was defective. So instead I prefer to keep the question a little bit vaguer: is there a known unknot diagram for which it is truly the case that to disentangle it you have to make it much more complicated? A real test of success would be if one could be presented with it as a 3D object and it would be impossible to unknot it without considerable ingenuity. (It would make a great puzzle ...)

I should stress that this question is all about combinatorial algorithms: if a knot is hard to simplify but easily recognised as the unknot by Snappea, it counts as hard in my book.

Update. Very many thanks for the extremely high-quality answers and comments below: what an advertisement for MathOverflow. By following the link provided by Agol, I arrived at Haken's "Gordian knot," which seems to be a pretty convincing counterexample to any simple proposition to the effect that a smallish class of generalized moves can undo a knot monotonically with respect to some polynomially bounded parameter. Let me see if I can insert it:

^{(J.O'Rourke substituted a hopefully roughly equivalent image for Timothy's now-inaccessible image link.)}

I have stared at this unknot diagram for some time, and eventually I think I understood the technique used to produce it. It is clear that Haken started by taking a loop, pulling it until it formed something close to two parallel strands, twisting those strands several times, and then threading the ends in and out of the resulting twists. The thing that is slightly mysterious is that both ends are "locked". It is easy to see how to lock up one end, but less easy to see how to do both. In the end I think I worked out a way of doing that: basically, you lock one end first, then having done so you sort of ignore the structure of that end and do the same thing to the other end with a twisted bunch of string rather than a nice tidy end of string. I don't know how much sense that makes, but anyway I tried it. The result was disappointing at first, as the tangle I created was quite easy to simplify. But towards the end, to my pleasure, it became more difficult, and as a result I have a rather small unknot diagram that looks pretty knotted. There is a simplifying move if one looks hard enough for it, but the move is very "global" in character -- that is, it involves moving several strands at once -- which suggests that searching for it algorithmically could be quite hard. I'd love to put a picture of it up here: if anyone has any suggestions about how I could do this I would be very grateful.

Answer 1

As you suggest, a lot of people have thought about this question. It's hard to find arrangements of an unknot that are convincingly hard to untie, but there are techniques that do pretty well.

Have you ever had to untangle a marionette, especially one that a toddler has played with? They tend to become entangled in a certain way, by a series of operations where the marionette twists so that two bundles of control strings are twisted in an opposite sense, sometimes compounded with previous entanglements. It can take considerable patience and close attention to get the mess undone. The best solution: don't give marionettes to young or inattentive children!

You can apply this to the unknot, by first winding it up in a coil, then taking opposite sides of the coil and braiding them (creating inverse braids on the two ends), then treating what you have like a marionette to be tangled. Once the arrangement has a bit of complexity, you can regroup it in another pattern (as two globs of stuff connected by $2n$ strands) and do some more marionette type entanglement. In practice, unknots can become pretty hard to undo.

As far as I can tell, the Kauffman and Lambropoulou paper you cited deals is discussing various cases of this kind of marionette-tangling operation.

I think it's entirely possible that there's a polynomial-time combinatorial algorithm to unknot an unknottable curve, but this has been a very hard question to resolve. The minimum area of a disk that an unknot bounds grows exponentially in terms of the complexity of an unknotted curve. However, such a disk can be described with data that grows as a polynomial in terms of the number of crossings or similar measure, using normal surface theory. It's unknown (to me) but plausible (to me) that unknotting can be done by an isotopy of space that has a polynomially-bounded, perhaps linearly-bounded, "complexity", suitably defined --- that is, things like the marionette untangling moves. This would not imply you can find the isotopy easily---it just says the problem is in NP, which is already known.

One point: the Smale Conjecture, proved by Allen Hatcher, says that the group of diffeomorphisms of $S^3$ is homotopy equivalent to the subgroup $O(4)$. A corollary of this is that the space of smooth unknotted curves retracts to the space of great circles, i.e., there exists a way to isotope smooth unknotted curves to round circles that is continuous as a function of the curve.

Answer 2

There is a new paper on this topic by Allison Henrich and Louis Kauffman, "Unknotting Unknots," arXiv:1006.4176v4 [math.GT]. In particular,

we show how to obtain a quadratic upper bound for the number of crossings that must be introduced into a sequence of unknotting moves.

A more precise version of their theorem is:

Theorem 4. Suppose $K$ is a diagram (in Morse form) of the unknot with crossing number cr$(K)$ and number of maxima b$(K)$. Let $M = 2$b$(K)$ $+$ cr$(K)$. Then the diagram can be unknotted by a sequence of Reidemeister moves so that no intermediate diagram has more than $(M − 2)^2$ crossings.

For the "Culprit" (discussed in Timothy's post), their theorem yields a bound of 324, but "in actuality we only needed a diagram with 12 crossings in our unknotting sequence":
          
They conclude their Introduction with this disclaimer:

we warn the reader that the difference between the lower bounds and upper bounds that are known is still vast. The quest for a satisfying answer to these questions continues.

---

(29Jul2014). The revised version of "Hard Unknots and Collapsing Tangles" by Louis Kauffman and Sofia Lambropoulou (8 years after its first version) was just posted: arXiv:math/0601525:

This paper gives infinitely many examples of unknot diagrams that are hard, in the sense that the diagrams need to be made more complicated by Reidemeister moves before they can be simplified.

---

(19Feb2021): See this update to @Arnaud's 2013 post and my own 2014 post: Marc Lackenby, "Unknot recognition in quasi-polynomial time." Feb2021. PDF slides. Here is his (109th and) last slide:

Answer 3

Maybe the slightly off the topic of whether there are hard unknots but here are a few more comments about detecting unknots. Regarding complexity theory as Bill mentioned detecting the unknot is NP. Agol has also proved that it is co-NP (i.e. proving that a knot is not the unknot is NP). My computer science friends tell me that such problem, simultaneously coNP and NP are thought to be polynomial time.

So far this thread has mentioned Haken's algorithm and its descendants, the Snappea algorithm and Dynnikov's algorithm (Marc Culler has an implementation of this algorithm in his program gridlink) "Culler's Grid Link Page". There is also the Birman Hirsch algorithm based on braid simplification. All of these algorithms, I think it is fair to say, involve an exhaustive search through an exponentially large set.

The various kinds of knot homologies give certificates of unknottedness of a rather different nature. A knot $K$ is unknotted if and only if $H(K)=H(U)$. In historical order the Seiberg-Witten Floer homology of the zero surgery, Ozsvath-Szabo-Rasmussen knot homology and Khovanov homology are known to detect the unknot. The later two have combinatorially definitions which are rather straightforward to code up on a computer (making the programs run fast is a non-trivial task). Khovnanov homology having been around longer has rather good algorithms at this point. All the algorithms run however in exponential time. Since Khovanov homology determines the Jones polynomial and computing the Jones polynomial is a known computationally hard problem Khonvanov homology is likely also hard (unless by some miracle computing the group without the bigrading is computationally simpler). The OSR knot group on the other hand determines Alexander polynomial which is polynomial time computable so there is some (I think extremely slim) hope that the OSR group is polynomial time computable. In any case these algorithms have a rather different flavor, they do not involve an exhaustive search on the other hand they require dealing with exponentially large matrices. They do not tell you how to unknot the knot even if you know it to be so.

Answer 4

There are really two questions here: (1) Can you an untangle any unknot with relatively little work, say a polynomial number of geometric moves of some kind? (2) Given a knot, can you quickly figure out that it is an unknot, say with a polynomial amount of thought? It seems that both questions are open and that neither one implies a solution to the other. You do get an elementary relation in one direction, which however is not useful for current bounds: If you have a good bound on the number of moves, then you can do an exhaustive search to find them. Except maybe for improved constants, I do not know of rigorous bounds that are better than the Hass-Lagarias result that you need at most an exponential number of moves (The number of Reidemeister Moves Needed for Unknotting, J. Amer. Math. Soc. 14 (2001), 399–428.), and the Hass-Lagarias-Pippenger result that unknottedness is in NP (The Computational Complexity of Knot and Link Problems, J. A. C. M. 46 (1999) 185–211). In fact the two results are related in the converse direction. Their certificate of unknottedness is a disk which may have exponential area and gives you the moves; but the disk has a polynomial-length description.

As Timothy Chow says, being both in NP and coNP is certainly not strong evidence by itself that unknottedness is in P. On the contrary, people believe that NP ∩ coNP is much bigger than P. But there is no strong reason to believe that unknottedness is hard or easy as far as I know. There is a theorem of Thurston and Garside that a trivial braid can be recognized in polynomial time; maybe the same is true of the unknot. One question that interests me, maybe for no good reason, is whether unknottedness is in BQP (quantum polynomial time).

As Tom says, if people do find a polynomial-time algorithm to tell if a knot is the unknot, it almost certainly won't be by computing its Khovanov homology. It's known to be #P-hard to compute the Jones polynomial of a knot, or even to derive various sorts of partial information about the Jones polynomial. For instance, usually a single value is already #P-hard. Khovanov homology, its categorification, is even more information. It is a theorem of Kronheimer and Mrowka that Khovanov homology distinguishes the unknot; this is also a conjecture for the original Jones polynomial. In other words, if you do find a fast algorithm to distinguish the unknot, there will be many large knots for which you can say, "No, that isn't unknot!" even though you won't know its Jones polynomial or its Khovanov homology in a million years. You'll just know that the latter and probably the former isn't trivial.

Answer 5

I did not see any mention of this paper by Marc Lackenby, probably because the question is quite old :

Lackenby, Marc, A polynomial upper bound on Reidemeister moves, Ann. Math. (2) 182, No. 2, 491-564 (2015). ZBL1329.57010.

Building on the techniques introduced by Dynnikov and adding some normal surface theory, he shows that any unknot can be unknotted using only a polynomial number of Reidemeister moves.

So if we interpret the "much more complicated" by "exponentially more complicated", it gives quite a strong "no" answer to

is there a known unknot diagram for which it is truly the case that to disentangle it you have to make it much more complicated?

Answer 6

I believe it's not known whether or not the uniform electrostatic charge potential function (as studied by Bryson, Freedman, He and Wang: Möbius invariance of knot energy) has any critical points other than the global minimum, on the space of unknots in $S^3$.

If the above were true and there were no critical points, that should in principle give you an algorithm to simplify any trivializable knot. Perhaps it could be implemented diagramatically, via a combination of things like simplifying Reidemeister moves and inversions on circles in the diagrams corresponding to conformal transformations of $S^3$.

Ivan Dynnikov has done some work on this and has a paper claiming diagrammatic "monotonic" simplification of unknot diagrams: Arc-presentations of links. Monotonic simplification. I went to a couple of his talks on this topic but didn't understand the core of the argument.

Answer 7

Allen Hatcher, in a preprint "Topological Moduli Spaces of Knots," subsequent to his proof of Smale's conjecture, remarks that one might expect there to be a nice energy function on the space of unknots (or, for that matter, on the space of knots of any given isotopy type) with the property that gradient flow in the direction of decreased energy always terminates at a standard form for the knot (or some very low-dimensional space of standard forms.) So you could certainly ask whether one would expect the complexity of a given unknot, in whatever sense this is meant, to be monotone decreasing as you flow it towards a nice round circle.

Greg Buck gave an interesting talk here at UW where he presented a candidate for such a function, and showed several cool movies (not available) of crimped, tangled unknots resolving to round circles. Buck said that he'd never observed the flow getting caught at a local minimum. (I didn't ask him whether the knot ever "gets more tangled on its way to being less tangled," but one could define this problem away by using his energy as the definition of tangledness....!)

Answer 8

I should stress that this question is all about combinatorial algorithms: if a knot is hard to simplify but easily recognised as the unknot by Snappea, it counts as hard in my book.

With respect, this comment is confused. When SnapPea "recognizes" an unknot it only uses combinatorial algorithms.

When you give SnapPea a diagram of the unknot it first uses ad hoc, but purely combinatorial, techniques to triangulate and then simplify the knot complement. After getting down to some very small number of tetrahedra (2 to 5, say) it then tries to find a finite volume hyperbolic structure on the knot complement. SnapPea uses Newton's method as applied to the Thurston gluing equations: I would not call this step combinatorial. However, that is not relevant to your question -- Snappea always fails to find such a structure because it does not exist.

You then ask SnapPea "What is the fundamental group of the knot complement?" SnapPea then uses other ad hoc, but combinatorial, techniques to simplify the fundamental group. These succeed because the number of tetrahedra is small -- SnapPea reports that $\pi_1 \cong \mathbb{Z}$ and Bob's your uncle by the Disk Theorem.

Edit: I was going to give a brief description of what SnapPea does in the retriangulation step. But Jeff Weeks' code and comments are very clear: the file to look at is simplify_triangulation.c in the SnapPea kernel.

Answer 9

There is a nice example of a trivial knot in Dynnikov's paper: A New Way to Represent Links. One-Dimensional Formalism and Untangling Technology.

It was verified by computer. It is big but it fits in a page. I am not sure there is an obvious simplifying move, it would be nice to know. By the way it would be interesting to have a definition of what a 'generalized Reidemeister move' is. A 'good' definition could perhaps give interesting diagrams of the unknot that are not easy to simplify.

Answer 10

The unknot on the Wikipedia doesn't seem trivial:

http://en.wikipedia.org/wiki/File:Thistlethwaite_unknot.svg

Lucas