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.