A recent algorithm unknots in quasipolynomial time. But I want to know what happens to the crossing number. Assuming your unknot has $n$ crossings, if I remember correctly it might be necessary to increase $n$ temporarily. But to what? $n+C$? $C*n$? Even worse? (I don't even know if the mentioned algorithm can be translated to actual Reidemeister moves - it might not be necessary if the goal is just recognizing the unknot.)
$\begingroup$
$\endgroup$
6
asked Aug 5, 2021 at 13:10
-
1$\begingroup$ Just as a remark, an analogy in geometric group theory (in solving the word problem in a finitely presented group) for the number of operations (applying relators) is computed by the Dehn function, while this addresses an analogue of the isodiametric Dehn function (controlling the diameter of the loop along the path). $\endgroup$– YCorCommented Aug 5, 2021 at 17:50
-
$\begingroup$ @YCor As a remark to your remark, it is worth adding that for a given finitely presented group the isodiametric Dehn function is computable if and only if the Dehn function is computable (which I am sure you know). $\endgroup$– Carl-Fredrik Nyberg BroddaCommented Aug 5, 2021 at 18:22
-
1$\begingroup$ The Lackenby algorithm finds a PL embedded disc $D^2 \to S^3$ when the knot is unknottable. I imagine if you use handle structure adapted to a diagram for the knot (like Lackenby does in some of his earlier papers) you could translate this result into a statement of the number of Reidemeister moves required. $\endgroup$– Ryan BudneyCommented Aug 5, 2021 at 20:54
-
1$\begingroup$ The upper bound below is interesting! I also feel like another interpretation of the question could be to give a lower bound, i.e. a family of knots that are known to require a large number of introduced crossings/Reidemeister moves, relative to the starting number of crossings. Are there also results along these lines? $\endgroup$– Alex MineCommented Aug 6, 2021 at 5:37
-
$\begingroup$ @AlexMine I agree that would be interesting. I don't know that end of the literature at all though. Hopefully someone else can add a comment with whatever lower bound is known. $\endgroup$– JoshuaZCommented Aug 8, 2021 at 1:53
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
Joel Hass and Jeff Lagarias proved that one can transform any unknot diagram with $n$ crossings into the standard unknot diagram using not more than $2^{cn}$ Reidemster moves. They were able to obtain the explicit value for $c$ of $c=10^{11}$. See here. This was subsequently improved by Marc Lackenby to a polynomial bound in the paper in the Annals "A polynomial upper bound on Reidemeister moves" In that paper, an unknot with at most $n$ crossings is shown to have a transformation into the standard unknot diagram with at most $(236n)^{11}$ Reidemeister moves; at no stage does the diagram have more than $(7n)^2$ crossings.
-
2$\begingroup$ Are there conjectures as to what the sharp bounds are? The numbers look like they might still be way off from the optimum but maybe there are some example unknot diagrams that do require huge numbers of moves to simplify. $\endgroup$– quaragueCommented Aug 6, 2021 at 13:41
-
$\begingroup$ @quarague I don't know about conjectures. The empirical bounds on the other end are apparently not great. has examples where they can show that the crossing number has to go up by at least 3. That seems to be the worst known right now. $\endgroup$– JoshuaZCommented Aug 10, 2021 at 15:38