13

Suppose one has a link diagram of the unknot, and applies random Reidemeister moves until the unknot is reached. Surely it requires an exponential number of moves, exponential in, say, the crossing number of the original diagram? The 2001 Hass-Lagarias paper, "The number of Reidemeister moves needed for unknotting," established an exponential upper bound on the number of moves needed, but I am not finding a result on the expected number of random moves needed. I would like affirmation that not only is it hard, but one would not easily stumble into a solution, because then it would not truly be hard! (This in the spirit of Gower's much more substantive MO question, "Are there any very hard unknots?")

A reference would be appreciated! Thanks!

Edit: Apologies for the flawed question (thanks to Ryan Budney for clarifying it). I had in mind the expected number of random moves to reach the unknot from a random (in some sense!) diagram of the unknot.

Answered. The question has been answered in the comments by Theo Johnson-Freyd and Ori Gurel-Gurevich: the expected number of moves is $\infty$! As Ori put it,

for any starting diagram of the unknot, there is a positive probability of never unknotting it.

YCor
  • 60,149
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 1
    I'm a little confused as to why you say "surely" as it's does take an exponential number of moves in general. Moreover, I would guess that if you only make random moves, it's highly unlikely you will ever find a route to the unknot -- it seems more likely that you would be endlessly lost in diagram space. – Ryan Budney Oct 09 '11 at 01:12
  • @Ryan: Perhaps the cases that require an exponential number of moves are rare? You say, "in general." That is what I would like quantified. And, Yes, it is highly unlikely to wander into the unknot. But has this been proved? Perhaps it follows from Hass-Lagarias in a way I am not seeing... – Joseph O'Rourke Oct 09 '11 at 01:22
  • 3
    Here's one reason to think that the answer to your question is $\infty$. Let's work with knots with more than, say, two crossings (as two-crossing knots are not hard to untie). Then there are plenty of strands that with some isotoping can be made parallel. Ok, so among other moves you have access to are the Reidemester-II moves, one direction of which increases the crossing number. If you are not careful, it is easy to use these to include into your diagram space a lattice of large dimension. And you know that it's easy to get lost in them: a drunk bird never arrives home. – Theo Johnson-Freyd Oct 09 '11 at 01:33
  • And you do need to allow yourself to increase the crossing number. See e.g. the linked question by Gowers. – Theo Johnson-Freyd Oct 09 '11 at 01:36
  • 1
    @Joseph: I think I don't entirely understand your question. There are concrete knot diagrams for which you have to make a large number of Reidemeister moves to simplify them to standard unknot diagrams. So perhaps I've misplaced the quantifier when you use the word "expected" -- are you choosing your knot randomly, as well as choosing the Reidemeister moves randomly? – Ryan Budney Oct 09 '11 at 02:04
  • @Ryan: Yes, I see now. I was imagining a random knot drawing, and then applying random moves. My fault for not making the relevant distinction! I'm now inclined to Theo's answer: $\infty$! – Joseph O'Rourke Oct 09 '11 at 02:17
  • 2
    Theo is correct that the diagram space contains lattices of any dimension. Therefore, for any starting diagram of the unknot, there is a positive probability of never unknotting it. (BTW, you can also do it with type I moves). I would just like to add that even if the diagram space was recurrent, the expected number of moves to unknotting would still be infinite, as is the case for simple random walk on any infinite graph. – Ori Gurel-Gurevich Oct 09 '11 at 16:42
  • @Ori: Thanks for those insights! But now I am puzzled by a theorem in the paper I quoted. Perhaps this just depends on their model, but they prove: "There is a $\lambda > 1$ such that the mean unknotting time of every 2-dimensional SAPT of length $n$ is bounded above by $\lambda^n$." How can this finite upper bound be reconciled with your remarks? – Joseph O'Rourke Oct 09 '11 at 17:00
  • @Joseph: See my comment to your answer. – Ori Gurel-Gurevich Oct 10 '11 at 01:29
  • 1
    I suspect the answer might change if there were a non-zero "drift" such that the walk along the Reidemeister graph encourages unknotting Type I / Type II moves over "knotting" Type I / Type II? That is, given a knot diagram with a list of potential Reidemeister moves, if one favor unknotting moves that reduce the crossing number over knotting moves that increase the crossing number, then one may have a non-zero probability of unknotting eventually. – Mark S Nov 18 '17 at 14:49
  • 1
    A better question might be whether the expected number of grid moves (exchanges or switches) to untie a grid diagram of the unknot (by "untie", I mean put it in a grid diagram with no crossings). Dynnikov showed that one can untie using switches, and Lackenby showed that one can do it in polynomially many moves. But it's unclear what the expected number of random switches to unknot would be. https://arxiv.org/abs/1302.0180 – Ian Agol Nov 23 '17 at 21:09
  • 1
    Given a grid diagram, call a sequence of translations, castlings, and destabilizations a Dynnikov ratchet. Marc Culler's gridlink (http://homepages.math.uic.edu/~culler/gridlink/) applies a Dynnikov ratchet of 1000 random moves to grid diagrams of grid dimension about 12. I think gridlink is greedy, always taking a destabilization if allowed. Culler suggests that a 12x12 grid may be close to minimal after a Dynnikov ratchet of 1000 moves. – Mark S Jun 10 '18 at 12:44

3 Answers3

5

This question has been fully answered (the expected number of moves is $\infty$), as detailed in an addendum to the question. I place this community-wiki "answer" here so I can accept it and so prevent the MO software-bot from re-asking the question.

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
2

I found an answer of sorts in the paper, "Mean unknotting times of random knots and embeddings," by Yao-ban Chan, Aleksander L Owczarek, Andrew Rechnitzer, and Gordon Slade (Journal of Statistical Mechanics: Theory and Experiment, Volume 2007, May 2007.) Here is the beginning of their Abstract:

We study mean unknotting times of knots and knot embeddings by crossing reversals, in a problem motivated by DNA entanglement. Using self-avoiding polygons (SAPs) and self-avoiding polygon trails (SAPTs) we prove that the mean unknotting time grows exponentially in the length of the SAPT and at least exponentially with the length of the SAP.

Their SAPs are on a 3D lattice; their SAPTs are on a 2D lattice; see below. Interesting that they did not establish an upper bound for SAPs.
SAPT

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 3
    This paper deals with another question. The "unknotting" they refer to is achieved by reversing crossings, not by Reidemeister's moves. In particular, the diagram is never changed, so the space is finite size. – Ori Gurel-Gurevich Oct 10 '11 at 01:29
1

Reviewing the appendix of Quantum Money from Knots by Farhi, Gosset, Hassidim, Lutomirski, and Shor, the authors provide a finite, doubly-stochastic Markov chain, where transitions act on grid diagrams.

Thus, the limiting distribution of their chain applied (classically) to a given grid diagram representing the unknot is uniform, and one of the states would be a canonical $2\times 2$ unknot.

In order to keep the Markov chain finite, they have a security parameter $\bar{D}$ and declare that two grid diagrams $G_1$ and $G_2$ don't represent the same knot/link if all sequence of moves from $G_1$ to $G_2$ require transitioning to a grid of size $d\gt 2\bar{D}$.

As I understand their quantum verification protocol, given a superposition of grid diagrams $\tilde{G}$, all with the same Alexander polynomial, their quantum-computer enabled merchant randomly apply $O(\textrm{poly}\:\bar{D})$ cyclic permutations, transpositions, stabilizations, and destabilizations to each state, if she can, to generate a "new" superposition of grid diagrams $G$. The verification succeeds only if $\tilde{G}=G$; by the no-cloning theorem, such superpositions cannot be easily forged.

In order to show the chain is doubly-stochastic, they note that cyclic permutations are invertable. Transpositions that are allowed are invertable, and similarly stabilizations and destabilizations. Stabilizations increase the grid number $d$, whereas destabilizations decrease the grid number $d$. For reasons similar to Theo's comment, a stabilization move is more likely to be done than a destabilization move; however, because of the way they uniformly choose their moves, any move that increases $d$ to more than $2\bar{D}$ won't be done. Thus, they (or rather their quantum verification algorithm) simply walks along the space of all grid diagrams equivalent to $G$ that are less than or equal to $2\bar{D}\times 2\bar{D}$ in size.

Thinking classically, and, rather than applying the quantum algorithm to a superposition of states, only applying their same Markov chain to a single grid diagram $G$ of grid number $\bar{D}$ which represents the unknot, the stable distribution will be uniform over every grid diagram equivalent to $G$ having a grid number less than or equal to $2\bar{D}$.

(They also require a weighting index $i$ of the grid diagram, because they would like the grid dimension $d$ in their superposition of grid diagrams to be centered around $\bar{D}$. Thus, they let $i$ be appropriately normally distributed, and their stable distribution is uniform over pairs $(G,i)$.)

Farhi, Gosset, Hassidim, Lutomirski, and Shor note that, for most knots, the security of their quantum money depends on the mixing time of their Markov chain being polynomial in $\bar{D}$. I think Lackenby's A polynomial upper bound on Reidemeister moves results, mentioned in the comments, suggest that the unknot in particular would mix in polynomial time. Accordingly, if the given knot is the unknot, it may take an exponentially long time to walk along this space (the hitting time may be exponential), but a $2\times 2$ grid diagram representing the unknot should eventually be reached.

Mark S
  • 2,143