Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 Kaufmann 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 Kaufmann 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.
Fig2

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 Kaufmann 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 Kaufmann-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.
Fig5

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:
Fig 3.5

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.

share|improve this question
20  
I took the liberty of adding K-L's Figs.2 & 5; hope you don't mind. –  Joseph O'Rourke Jan 27 '11 at 12:04
6  
Far from minding, I'm absolutely delighted, and would have had no idea how to do it myself. Many thanks. –  gowers Jan 27 '11 at 12:12
5  
Dynnikov's algorithm (mentioned in Budney's answer) is the closest known method to what you are asking. The grid number is monotonically simplified by a version of generalized Reidemeister moves suited to grid diagrams, which allow you to do the sorts of moves that you describe (move two strands past each other, even though there are other strands in front and behind). However, this method is not strictly monotonic, since there could possibly be superexponentially many unknot diagrams of a fixed grid number. As a grad student, I used this method to simplify some unknots constructed by Haken: –  Ian Agol Jan 29 '11 at 18:44
2  
math.uic.edu/~agol/unknots.html –  Ian Agol Jan 29 '11 at 18:44
1  
I have thought an algorithm that also loosens all the knots the knot gordiano of haken. in www.zanellati.it/knot it is available the pdf with all the movements. –  adolfo zanellati Oct 13 at 22:31

10 Answers 10

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 Kaufmann 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.

share|improve this answer
16  
I have had enough children to have the marionette experience several times, but had not thought of connecting that to the unknot question. –  gowers Jan 27 '11 at 12:48

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.

share|improve this answer
13  
This is somewhat tangential, but it's certainly not the majority opinion that being in coNP intersect NP is strong evidence for being in P. The most prominent example is factoring, which (when phrased as a decision problem) is in coNP intersect NP, but it is not the case that the majority of computer scientists regard this fact as strong evidence for the existence of a polynomial-time algorithm for factoring. –  Timothy Chow Jan 29 '11 at 21:25

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":
          The Culprit
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.


(29Jul14). 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.

share|improve this answer

I believe it's not known whether or not the uniform electrostatic charge potential function (as studied by Bryson, Freedman, He and Wang: http://front.math.ucdavis.edu/9301.5212) 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: http://arxiv.org/abs/math.GT/0208153 I went to a couple of his talks on this topic but didn't understand the core of the argument.

share|improve this answer

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 [arXiv:math/9807012], and the Hass-Lagarias-Pippenger result that unknottedness is in NP [arXiv:math/9807016]. 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.

share|improve this answer

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....!)

share|improve this answer
    
Oh, as I posted this I see that Ryan posted a similar answer with a different proposed potential function! –  JSE Jan 27 '11 at 16:13
1  
Small clarification: It's a formal consequence of Hatcher's theorem that there a function on the space of unknots that has no critical points other than the global minimum being the "round unknot" subspace. The issue is whether or not it can be chosen to be a physically meaningful function, like the uniform electric charge potential function. For every component of the space of embeddings of $S^1$ in $S^3$ I give a finite-dimensional subspace where that component deformation-retracts to in my "splicing operad" paper. So it's the analogue of "round unknots" but for actual knots. –  Ryan Budney Jan 27 '11 at 16:20
    
I don't get it -- if the existence of such a function is a corollary of Hatcher's theorem, why does he write about it in the later linked paper in a "one might hope..." kind of way? –  JSE Jan 27 '11 at 16:24
    
or maybe I get it -- you're saying just the existence of a retract says formally that there IS a smooth function, but there's no reason that decrease in that function should correspond to anything T-Gow thinks of as "simplification," unless the function is physically meaningful. –  JSE Jan 27 '11 at 16:26
1  
Yes, knowing such a function exists is very different from having an explicit (useful) such function that you can use. It's kind of like Smale's proof that you can turn the sphere inside out -- people wanted to see it happen, beyond an abstract proof that it can be done. –  Ryan Budney Jan 27 '11 at 18:06

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

A polynomial upper bound on Reidemeister moves http://arxiv.org/abs/1302.0180

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?

share|improve this answer

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.

share|improve this answer
    
OK you're right that my comment is misleading, and thank you for the explanation about what SnapPea does. I should therefore say that I am asking specifically about greedy algorithms that use mild generalizations of Reidemeister moves. What you might say is that I am interested in arguments that work directly from knot diagrams and do not construct any auxiliary objects. –  gowers Jan 27 '11 at 16:23
    
Yes, Snappea mainly recognizes unknottability and recognition of knots, rather than recognition of the unknot. There is some analytic/combinatorial interaction in this: in particular, recognizing that there are incompressible surfaces by degeneration of simplices, and also, sometimes, retriangulating based on geometry. It would be interesting to show that recognition of unknotability is in P or even NP. –  Bill Thurston Jan 27 '11 at 16:52
    
@gowers - This is a reasonable enough. However, are you sure that you are really interested in "diagram complexity"? Per Thurston's answer I thought you wanted to allow physical moves like "grab a sub-tangle and rotate it". Similarly, in the first paragraph of your post you explicitly say that it was the physical approach (and so not attached to any particular diagram!) that led you to ask the question. --- I'm arguing here that SnapPea's messing about with triangulations appears to have access to that three-dimensional "intuition". –  Sam Nead Jan 27 '11 at 17:03
    
@Thurston - I am now confused. What is the difference between recognizing the unknot and recognizing "unknotability"? –  Sam Nead Jan 27 '11 at 17:41
    
@Sam, that's a good question, and the truth is that I don't have a completely clear answer to it. I think what I'm interested in is the possibility of a 2-dimensional argument that captures some of the 3-dimensional intuition that certain moves are easy even though if you break them up into Reidemeister moves then you have to increase the number of crossings. So it's more 3D than just Reidemeister moves but more 2D than constructing triangulations and the like. –  gowers Jan 27 '11 at 18:35

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.

share|improve this answer
    
Thank you for this example. It's quite interesting as it is in some sense a "product" of smaller knots. I tried replacing the bundles of strands (most of the time four strands) by a single strand and obtained a picture of a knot that I can't instantly see to be the unknot, though I did find a local way of reducing the number of crossings. If this "quotient" knot is not the unknot, then it's a very interesting example. –  gowers May 9 '13 at 14:49
    
Reply from Panos (under a different account): Yes, it seems that the 4 strands travel together and there is some linking on the upper part of the diagram and a 'knot' on the bottom. In the previous examples it seemed that one could simplify the diagram by moving one strand by a `generalized Reidemeister move'. If I understand you correctly you say that you can simplify Dynikov's example by moving 4 strands together ? I am curious to see this. (this is a comment to the previous comment but apparently I can not post it as a comment). –  S. Carnahan May 13 '13 at 8:21
1  
I drew the "quotient" knot and the picture has been sitting on my desk for about a month. At first it looked hard to simplify, but then I saw that one could make a "hole" in the middle and take a chunk of knot and pass it up through the hole and back down again. This kind of global untwisting would, I think, have to be part of any unknotting procedure of the kind I fantasize about. At some point I might make the knot out of string and see whether I can indeed untie it fairly straightforwardly starting with that move. –  gowers Jun 13 '13 at 12:18
    
Reply from Panos: Thank you, you are right it seems the quotient knot is trivial. It took me 10 minutes and 10 seconds to prove this. 10 minutes to make the knot using a string (I put the string on top of Dynnikov's example gluing the corners with play dough) and then I tied the ends and lifted this. It took about 10 seconds to unknot but I have no idea what I did. It seems unlikely that I made a mistake as one wrong crossing would make it non trivial I assume. Still I am curious to see your 1st unknotting move as I really don't know what happened after I lifted the knot. –  S. Carnahan Jun 15 '13 at 22:36

The unknot on the Wikipedia doesn't seem trivial:

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

Lucas

share|improve this answer
    
I found a generalized move that reduces the number of crossings. Again it's not that easy to describe, but here's a try: if you look at the two bottom horizontal bits of the knot, they cross once at the bottom left, and if you follow them round clockwise they cross again fairly near the top. If you ignore the rest of the knot, you can do a Reidemeister move on just those strands and it reduces the number of crossings. So it's not minimal in the sense I tried to describe. (I see my task always as proving non-minimality rather than disentangling the entire knot.) –  gowers Jan 27 '11 at 23:48
    
I have looked at it closer, and indeed, it is less complicated than it looks like. –  Lucas K. Jan 28 '11 at 23:03
    
A suggestion for you actual question. What about counting layers instead of crossings? I don't know the effect. When the rope crosses, it may only when the two pieces are on different layers. Between crossings, the rope can change of layer. Count the minimal required layer changes. In your figure 2, this number might not increase when simplifying. –  Lucas K. Jan 28 '11 at 23:36

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.