Hard Diagrams of the Unknot

Abstract

We present three “hard” diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in ${\mathbb{S}}^2$. Two of them are constructed by applying previously proposed methods. The proof of their hardness uses significant computational resources. We also determine that no small “standard” example of a hard unknot diagram requires more than one extra crossing for Reidemeister moves in ${\mathbb{S}}^2$.

Keywords:

• Knot theory
• unknot recognition problem
• Reidemeister moves
• unknot
• mathematical software

Acknowledgments

The authors would like to thank Dagstuhl and the organizers of the Dagstuhl seminar 19352: “Computation in Low-Dimensional Geometry and Topology” where this work has been initiated.

Notes

1 Note that this definition of a knot diagram may not be considered as standard. In many settings the target of the projection is the plane ${\mathbb{R}}^2$ rather than its one-point compactification ${\mathbb{R}}^2\cup \left\{\infty \right\}={\mathbb{S}}^2$; this is more intuitive when drawing a diagram by hand. We focus on knot diagrams in the 2-sphere because it is more natural from an algorithmic point of view.

2 Our third hard unknot diagram PZ₇₈ was discovered by simplifying the unknot diagram from [18, Figure 27]. It shares some characteristics with D₂₈, but is not discussed in further detail in this article.

3 Note that braids with high topological entropy per generator have also been used by Hass, Snoeyink and Thurston [12] in order to provide hard unknots, but for a notion of hardness very different to ours (the size of the smallest piecewise-linear spanning disk).

4 all drawings of the section are generated with SnapPy’s Spherogram and PLink modules [3].

Additional information

Funding

The work of Burton was supported by the Australian Research Council under the Discovery Project Scheme, grant number DP150104108. Maria was partially funded by ANR project ANR-20-CE48-0007 AlgoKnot. The work of Spreer was supported by the Australian Research Council under the Discovery Project Scheme, grant number DP220102588.