11
$\begingroup$

A recent question Random Reidemeister moves to unknot contains a link to the paper http://www.ams.org/journals/jams/2001-14-02/S0894-0347-01-00358-7/S0894-0347-01-00358-7.pdf, in which J. Hass and J. Lagarias show that one can transform any unknot diagram with $n$ crossings into the standard unknot diagram using not more than $2^{cn}$ Reidemeister moves, with $c=10^{11}$.

[As an aside: this is quite a large bound, so the first thing that comes to mind when one looks at it is a computer falling apart with all its atoms decaying long before it manages to untie a diagram with a single crossing. As far as I understand, for those diagrams the algorithm works faster, but still it is probably impractical for untying knots that can't be untied by trial and error.]

It seems plausible that the methods of Hass and Lagarias can be adapted to give a similar explicit upper bound for the number of the Reidemeister moves needed to transform two diagrams representing isotopic links into one another. I would like to ask whether this is indeed the case, and if so, whether there is a reference for that.

A related question: given a nonnegative integer $n$, is it possible to estimate from above the minimal $m$ such that any two link diagrams with $\leq n$ crossings that represent isotopic links can be connected by a sequence of diagrams with $\leq m$ crossings such that each is obtained from the preceding one by a Reidemeister move?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ front.math.ucdavis.edu/1104.1882 $\endgroup$
    – Ian Agol
    Commented Oct 11, 2011 at 4:32
  • $\begingroup$ Dear Ian -- thanks a lot! if you choose to post this as an answer, I'll accept it. However, the upper bound they give is absolutely huge, and I am wondering if there is a smaller one for the maximal number of crossings the sequence of diagrams must pass through. $\endgroup$
    – algori
    Commented Oct 11, 2011 at 5:02
  • $\begingroup$ Not an answer, but related: arxiv.org/pdf/math/0501490 $\endgroup$
    – Scott Carter
    Commented Oct 11, 2011 at 13:41
  • 1
    $\begingroup$ I haven't read this paper of Suh's but there's a stated lower bound than the Hass and Lagarias one: front.math.ucdavis.edu/1010.4101 $\endgroup$
    – Ryan Budney
    Commented Oct 11, 2011 at 16:41
  • 1
    $\begingroup$ Hass and Nowik show that the best upper bound you can hope for is quadratic in the number of crossings: arxiv.org/abs/0711.2350 $\endgroup$
    – b b
    Commented Oct 21, 2011 at 22:45

2 Answers 2

Reset to default
5
$\begingroup$

Coward and Lackenby have an upper bound on the number of Reidemeister moves, which is a tower of exponentials. The existence of some such bound is not surprising, since Waldhausen had proven that the knot isotopy problem was solvable, so some computable upper bound exists.

Suppose you had a much better upper bound on the number of crossings of diagrams in the sequence of moves than their bound. Then since the number of diagrams with $c$ crossings is no more than say $k^{k^c}$ for some $k$, one would get a much better bound on the number of reidemeister moves to get between two diagrams. So I think one would need a new idea to get such an estimate.

Improve this answer
$\endgroup$
10
$\begingroup$

Lackenby updated his arXiv paper today (12Dec2014) in which he proves a polynomial bound on the moves to uncross the unknot. I am uncertain if this also implies a polynomial bound on moving from one knot to another.

Marc Lackenby. "A polynomial upper bound on Reidemeister moves." 2014. (62 pages.) (arXiv abs link.)

"We prove that any diagram of the unknot with $c$ crossings may be reduced to the trivial diagram using at most $(236 c)^{11}$ Reidemeister moves. Moreover, every diagram in this sequence has at most $(7 c)^2$ crossings."

(19Feb2021). See update at "Are there any very hard unknots?". for Lackenby's Feb 2021 "Unknot recognition in quasi-polynomial time."

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can one not combine $R_1$ and $R_2$ as $R_1(R_2)^{-1}$, where I am using the symbols as move sequences, and hoping the right intepretation suggests itself? That would give a polynomial bound on move length between knots. $\endgroup$
    – The Masked Avenger
    Commented Dec 12, 2014 at 20:39
  • $\begingroup$ @TheMaskedAvenger: My 1st thought also. But if neither knot is the unknot, I don't really know. Need to spend quality time inside that long paper. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 13, 2014 at 0:20
  • 4
    $\begingroup$ In his survey "Elementary Knot Theory", available on his webpage, Marc Lackenby announces that a similar bound holds for arbitrary knots: "For each link type $K$, there is a polynomial $p_K$ such that any two diagrams of K with crossing number $n$ and $n'$ differ by a sequence of at most $p_K(n) +p_K(n')$ Reidemeister moves. As a consequence, for each link type $K$, the $K$-recognition problem is in NP. Note that the polynomial is not universal though, as it depend on the link type. $\endgroup$
    – Arnaud
    Commented Dec 15, 2014 at 19:17
  • $\begingroup$ @Arnaud: Thanks for finding that clear claim! $\endgroup$
    – Joseph O'Rourke
    Commented Dec 15, 2014 at 19:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .