In 1998 Galatolo established an upper bound on the number of Reidemeister moves needed to convert a diagram $D$ of the unknot into a trivial loop diagram. The upper bound is a function of $n$, the number of crossings in $D$.

Galatolo reduced the problem to that of limiting the number of crossings the diagram can have during the conversion process. Specifically, he states these problems:

Problem 1. Find some function $f$ such that converting $D$ into a trivial diagram takes at most $f(n)$ Reidemeister moves.

Problem 2. Find some function $F$ such that converting $D$ into a trivial diagram never passes through an intermediate diagram with more than $F(n)$ crossings.

He claims that these problems are trivially equivalent in his footnote labelled $(\,^1)$, part of which says

If we have $F(n)$ then $f(n) < 2^{2F(n)(\log 2F(n) + 1)}$

I don't understand how a bound $F(n)$ on crossings can lead to a bound on moves, because one could do many Type III Reidemeister moves, none of which affect the number of crossings. One could bound the number of essentially different diagrams resulting from Type III moves, but that would not be as trivial as Galatolo claims. Am I missing something?

And by the way, should the bound actually be $f(n) < 2^{2F(n)(\log_2 F(n) + 1)}$? (log base 2)

(This question was originally on math.stackexchange)

My solution starts with a bound of the number of diagrams with crossing number $k$. Every $k$-crossing diagram consists of $k$ "crossing units" that look like $\times$ except with some overstrand and understrand assignment. The four "legs" of the crossing unit are connected to the other "legs" in some way. The number of ways to partition $4k$ legs into pairs is $\frac{(4k)!}{2^{2k}(2k)!}$ (explained in an MSE question), and the overstrand/understrand assignments contribute another factor of $2^k$. Ambient isotopic diagrams obviously correspond to the same "leg pairing". The matching may create more crossings but no matter; we have $$ \text{No. of diagrams with $k$ crossings} \leq \frac{(4k)!}{2^k(2k)!} \leq 2^{-k}(4k)^{2k} = 2^{2k(\log_2 k + 3)} $$

So, assuming $D$ can be converted to the trivial diagram without passing through a diagram with more than $F(n)$ crossings, there are at most $F(n)2^{2F(n)(\log_2 F(n) + 3)}$ different intermediate diagrams. Therefore at most $F(n)2^{2F(n)(\log_2 F(n) + 3)}$ Reidemeister moves are necessary for the conversion.

My bound is significantly larger than Galatolo's. If anyone should provide a simpler way to derive Galatolo's bound, I will accept it as an answer.

  • 1
    $\begingroup$ My guess is that the intended idea is just the one you say, that the number of essentially different diagrams is small. And yes, I think the log should be base two. But in fact the number of diagrams can be bounded singly-exponentially in F, rather than exponentially in F log F (this part is not so trivial). $\endgroup$ – David Eppstein May 7 '14 at 3:45
  • 3
    $\begingroup$ I would like to point out that Lackenby proved in 2013 that the number of Reidemeister moves needed to convert a diagram of the unknot into the trivial diagram is polynomial w.r.t. the number of crossings: arxiv.org/abs/1302.0180 $\endgroup$ – Roberto Frigerio May 9 '14 at 14:09
  • $\begingroup$ @DavidEppstein I have attempted my own bound (see the original question) but it's still $F2^{F \log F}$. How did you bound it exponentially in $F \log F$? $\endgroup$ – Herng Yi May 11 '14 at 11:40
  • 1
    $\begingroup$ There are a single-exponential number of 4-regular planar graphs with $n$ vertices, and a single-exponential number of ways of choosing the above-below relation at each crossing. $\endgroup$ – David Eppstein May 11 '14 at 20:04
  • $\begingroup$ @DavidEppstein do you have a reference for that bound on 4-regular planar graphs? (I hope it's not asymptotic) $\endgroup$ – Herng Yi May 12 '14 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.