Solving the unknotting problem by pulling both ends of the string

Question

It is an open question as to whether there is a polynomial time algorithm for recognizing the unknot.

Consider the following procedure for doing so on an actual physical string: Suppose there is a physical string that is tangled and I am holding both of its ends. To determine whether the string is knotted, all I have to do is pull on both ends, tightening the string. If we end up with an unknotted string, then the string is unknotted. Otherwise, the string is knotted. I would think if we simulated this process on a digital computer, it would take polynomial time, since in real life it is quick, at least in my experience. Has this idea ever been considered in the literature?

Update: When I wrote this question, I made a mistake in my understanding of what is the unknot. The mathematical definition is a string with its ends glued together with the topology of a torus. I had thought that a string with no knots in it is for all practical purposes the same thing, at least for this question. It turns out that they are not the same. In fact, I now can remember learning a few magic tricks that make use of the fact that they are not the same. Thanks to Andy Putman for pointing my mistake out in the comments.

Another update: Thank you to JoshuaZ in the comments for the link to the problem unknot. I tried it out on my own rope and indeed this example shows that the premise of my question is false. Pulling the ends of this rope will not solve this problem.

Another update: Tying shoelaces in double knots is another counterexample that I had forgotten about.

What you say isn't even true. You're holding the string with two hand, so the union of the string and your arms/body can form a nontrivial knot that will not come undone when you pull it even if the actual string is not knotted. — Andy Putman, Mar 12 '24 at 15:35
@AndyPutnam I don’t see the problem here. I only care about knots on the string, not my body. — Craig Feinstein, Mar 12 '24 at 15:45
People have tried similar things, e.g.: https://arxiv.org/abs/2006.07859 But simulating a physical string means discretizing it and with that it is very easy to accidentally jump in topology. In addition, seeing that this process seems to work in examples is easy. But showing that it always finishes the job in polynomial time seems more or less impossible. — mlk, Mar 12 '24 at 15:55
You've missed some key issues. You need your rope to be thick (or else you pull it tight, breaking the topology) and you need your rope to be frictionless. Is that your set-up? If so, you should edit it into your question. If you allow friction you get genuine critical points -- this is the subject of traditional knots, like used in climbing or fisheries. — Ryan Budney, Mar 12 '24 at 16:10
@RyanBudney I was assuming friction would be very small or zero, since if there is too much friction it could be hard to get things untangled (from my own experience doing magic tricks with ropes). — Craig Feinstein, Mar 12 '24 at 16:40
Even with a very slippery piece of string, something which is an unknot can seem to get caught when you pull tight on it. For one which I think will show this somewhat, making this unknot out of string and pulling it tight this way after cutting the upper left https://i.stack.imgur.com/dtMM9.jpg . — JoshuaZ, Mar 12 '24 at 17:48
I've downvoted, but I feel I should explain. It looks like you are asking for a reference. But the reference you are asking for is "has anybody had my idea before me?" For that to be a real question, you have to place some flesh on your (currently) skeleton of an idea. — Sam Nead, Mar 12 '24 at 18:51
@CraigFeinstein: Yes, but unless the string can pass through whatever is holding it it cannot become unknotted. This is why I think you are being led astray by relatively simple knots. If you tried this for something genuinely complicated it would not come undone. — Andy Putman, Mar 12 '24 at 19:09
(you also should spell my name correctly if you want me to notice your comment) — Andy Putman, Mar 12 '24 at 19:10
@AndyPutman sorry about the name misspelling. Am I understanding you correctly that this problem may have a different answer for a rope that has two ends with a restriction on what moves can be made to unknot it than a rope in which the ends are glued together? — Craig Feinstein, Mar 12 '24 at 19:23
@CraigFeinstein: No. Here is a picture of an unknot. If you grab it at the red and blue points and pull, it will not come undone. https://imgur.com/a/lJKSlrj — Andy Putman, Mar 12 '24 at 19:33
I think the downvotes are excessive. Yes, the question is vague, but there is a real, research-level question lurking here as evinced by the various references people have provided. — Sam Hopkins, Mar 12 '24 at 19:40
@AndyPutman now I understand. Many magic tricks with rope are built around that principle. — Craig Feinstein, Mar 12 '24 at 20:20
@SamHopkins: I agree that one could ask an interesting question along these lines, but this isn’t it. I really think the whole premise (at least as described in the question) is based around a fallacy. — Andy Putman, Mar 12 '24 at 20:28
I'm curious if in your experiments included knots (physical knots, mathematically really unknots) designed to be loaded on the free ends. The two that come to mind are the alpine butterfly and the sheepshank. A figure-8 on a bight is also worth trying, though I can see that rolling with frictionless rope. — Yoav Kallus, Mar 12 '24 at 20:43
@AndyPutman I updated my question. I still think the question is a good question even though my definition of unknot is not so rigorous. — Craig Feinstein, Mar 12 '24 at 21:12
I think you need to be precise in the question you are asking. Right now you have a bit of a "shotgun" question, where it's up to the reader which of many possible questions you might want answered. — Ryan Budney, Mar 12 '24 at 23:42
@ryanbudney I’m not sure what you mean. I read your comment before. The physical attributes of the string might affect things in the real world but on a computer they can be easily adjusted. We might as well make it frictionless. — Craig Feinstein, Mar 13 '24 at 00:23
It seems that it should follow from the work by Nabutovsky and Weinberger on logical complexity of thick ropes that such "pulling" will necessarily get stuck on some trivial knots; see https://web.archive.org/web/20170809004938id_/http://www.mathunion.org/ICM/ICM2010.2/Main/icm2010.2.0862.0881.pdf — Mikhail Katz, Mar 14 '24 at 12:10
@CraigFeinstein: you still have an ill-defined question. For example, the dynamics of pulling tight will be different depending on how torsionally-rigid your rope is. For example, think of the difference between a cotton shoe-lace and a garden hose. Being torsionally stiff will increase the likelyhood of the knot forming tight self-twists, and can cause different critical points of the flow. — Ryan Budney, Mar 25 '24 at 17:42
A string with its ends glued together is a solid torus (not a "torus"). — Daniel Asimov, Mar 25 '24 at 18:05
If we use an actual curve for the knot (with zero thickness), then a merely continuous motion of pulling it tight can cause any knot to disappear. — Daniel Asimov, Mar 25 '24 at 18:09
@Ryanbudney the counterexample given in these comments appears to me to be impossible to undo given any material. I have tried it on magician’s rope. — Craig Feinstein, Mar 25 '24 at 18:25
@AndyPutman I don't understand your imgur example -- what you get when you join the ends is a trefoil knot, no? — RegularGraph, Mar 25 '24 at 21:23
@RegularGraph: What I drew is the whole knot. There are no ends to join — if you follow the path of it, it closes up. It has two parallel strands that seem to trace out two parallel trefoils, but then at the ends join together. So it’s an unknot. — Andy Putman, Mar 25 '24 at 21:51
@AndyPutman I see now, thanks for explaining. I thought you had just drawn it thickened to make it look more like an actual rope. It's still true that if you cut it at some point and then pull the ends, you can get it to untie (assuming no issue with friction etc). I came late to this discussion; I guess this was meant to refute a claim in the original post that has since been edited away. — RegularGraph, Mar 26 '24 at 00:58
@RegularGraph: If you cut any knot at any point it becomes the unknot, so I'm not sure what the point of that is. This knot refutes the claim on the OP that if you have an unknot, then pulling it apart from two points and letting strands slide past each other with no friction will turn it into the standard unknot. — Andy Putman, Mar 26 '24 at 01:06
@AndyPutman Once you cut the string, it's no longer an embedding from S^1, so speaking of the unknot seems a little strange. I'm not saying anything non-trivial, just that the procedure of testing for unknottedness by cutting the knot at one point, and then pulling on the two ends, is at least topologically reasonable. Your knot will be untied in this way, while the actual trefoil knot will not be. I would prefer the main post be a little clearer, but I think in its current state it no longer contains a topological fallacy. Do you agree? — RegularGraph, Mar 27 '24 at 13:13
@RegularGraph I did not edit anything out of the regular post. I only made updates. — Craig Feinstein, Mar 27 '24 at 21:25
@CraigFeinstein The phenomenon that AndyPutman's imgur picture illustrates is kind of interesting, but I don't see how it has much to do with your original question. (If it had been someone else commenting, I would have just ignored it, but Putman is a strong mathematician, so I'm trying to understand his point. Maybe this is a bad attitude on my part.) — RegularGraph, Mar 28 '24 at 01:30
@RegularGraph his point is valid, but hard to understand. His picture convinced me. I commented on it in my update of the question. — Craig Feinstein, Mar 28 '24 at 03:23

score 13 · Accepted Answer · edited Mar 12 '24 at 21:36

13

Here is a paper that, I think, underlines some of the difficulties in recognising the unknot using the physical process of "pulling tight".

Nontrivial embeddings of polygonal intervals and unknots in 3-space

by Cantarella and Johnston. They prove that there are "stuck" stick unknots for any stick number $n \geq 6$. That is, polygonal knots that are topologically the unknot but cannot be unknotted without changing the lengths of the sticks (or adding breakpoints).

As another piece of negative evidence we have the paper

Topological and physical link theory are distinct

by Coward and Hass. They give a link (made of "rope" - thus each component has a given thickness and length) which is topologically unlinked but cannot be physically unlinked.

edited Mar 12 '24 at 21:36

The Amplitwist

1,446

answered Mar 12 '24 at 19:05

Sam Nead

26,191

These papers give problems that such an algorithm may encounter (unknots that cannot be unknotted) but also give solutions on a computer (change the lengths of the sticks so they can be unknotted). They might be problematic in the physical world but not in the virtual world. – Craig Feinstein Mar 12 '24 at 22:34
1

Your question said "since in real life it is quick, at least in my experience". These papers are pointing out that physical experience may be misleading you. Your comment is saying that these counterexamples "might be problematic in the physical world but not in the virtual world". But you've not given me any hints of how you wish to proceed in the virtual world... so how can I evaluate your plan to recognise the unknot? – Sam Nead Mar 12 '24 at 22:42
if the problem is the length of sticks as shown in the first paper (or even the width of the sticks), whenever the algorithm runs into this issue, it could bypass it by making the sticks longer and thinner or add breakpoints if that doesn’t work. If it continues to do this, it will get the string unknotted. And probably polynomial time too since this little adjustment shouldn’t take too long. – Craig Feinstein Mar 12 '24 at 23:29
1

Your argument is an “intuition pump”- en.wikipedia.org/wiki/Intuition_pump - which is then followed by a “bait and switch” - rationalwiki.org/wiki/Bait-and-switch - … To clarify - I am not suggesting that you are arguing in bad faith… – Sam Nead Mar 13 '24 at 08:05
2

Instead I am saying that all people have emotional attachment to their positions, which makes it hard to understand other people’s attitudes and backgrounds. – Sam Nead Mar 13 '24 at 08:05
1

your assessment is correct, but I don’t think this is a bad thing. This is how problems get solved. – Craig Feinstein Mar 13 '24 at 11:50
All I am saying is that in real life, it is not so difficult to recognize an unknot. Thus, if a computer simulates real life, it shouldn’t be so difficult to recognize an unknot on a computer. – Craig Feinstein Mar 13 '24 at 12:17
4

You may be interested in the discussion of physical knots between Tim Gowers and Bill Thurston here: https://mathoverflow.net/questions/53471/are-there-any-very-hard-unknots - in particular they end by agreeing that there are "tangled marionettes" that are very hard to untangle. I regard this as evidence against the claim that "in real life, it is not so difficult to recognize an unknot". – Sam Nead Mar 13 '24 at 13:54
In any case, it seems that you found the references I provided of some interest. If that is the case, you might consider accepting my answer to your question. (And then thinking a bit, and then asking another question. :) – Sam Nead Mar 13 '24 at 13:55
yes thank you very much for your help and the link. I am new to the subject matter of knots, except for my experience with them in magic. – Craig Feinstein Mar 13 '24 at 16:11
My experience is that with magician’s rope, my proposal would probably work. It is both flexible and sturdy. I will try it out on the hard unknots that were listed in the links you gave. – Craig Feinstein Mar 13 '24 at 18:06
1

If you read my update, my proposal did not work. – Craig Feinstein Mar 14 '24 at 11:30
3

Negative results are still results! Good luck on your journey. :) – Sam Nead Mar 14 '24 at 15:58

score 6 · Answer 2 · edited Mar 25 '24 at 18:52

As noted in the comments, it is difficult to make this intuitive idea mathematically precise. In practice, even slip knots get stuck on themselves when pulled tight.

One may look for monotonic ways of untying an unknot. Holding a long unknot and pulling on the ends, one may expect for example that the number of maxima with respect to direction between the ends does not increase. Otal proved that one may always undo an unknot without increasing the number of maxima, so there is no obstruction of this type (he works with closed knots, but I think the proof should work for long unknots, ie unknotted strings/1-tangles). Dynnikov proved that one may monotonically simplify a (closed) unknot in grid position /arc diagram, but it’s hard to see how this might translate into something physical by pulling both ends of a long unknot.

score 2 · Answer 3 · edited Mar 25 '24 at 18:51

I think your description of a knot as a string with endpoints pulled apart is similar to embedding knots in $\mathbb{RP}^3$, with the free endpoints corresponding to a single point on $\mathbb{R}^3$'s boundary. There are several papers on knots in $\mathbb{RP}^3$. The most notable related knots in $\mathbb{RP}^3$ to knots in $\mathbb{R}^3$ by sliding a small reflecting sphere along the knot and looking at the knot's reflection. IIRC, there are examples of unknots in $\mathbb{R}^3$ that cannot be untied monotonically.

Solving the unknotting problem by pulling both ends of the string

3 Answers3