## Number of the Reidemeister moves needed to transform one diagram into another one

A recent question http://mathoverflow.net/questions/77570/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?

-
front.math.ucdavis.edu/1104.1882 – Agol Oct 11 2011 at 4:32
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. – algori Oct 11 2011 at 5:02
Not an answer, but related: arxiv.org/pdf/math/0501490 – Scott Carter Oct 11 2011 at 13:41
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 – Ryan Budney Oct 11 2011 at 16:41
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 – bb Oct 21 2011 at 22:45

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.