 Up to Home Maths Knot Theory Site Map | Text version

# Unknot Equivalence

[Fred Curtis - Feb-May 2001]
These working notes were motivated by my horror at the described length and complexity of Haken's 1961 unknot-equivalence algorithm in [Adams94]. [Hass99] indicates no known non-trivial lower bounds to the complexity of the problem at the time of writing.

## Synopsis

Deciding if a given knot diagram is the unknot, i.e. deciding if the diagram can be untangled into a simple loop, is part of the harder, more general task of deciding if two knot diagrams represent the same knot.
Let U0 denote the trivial (0-crossing) diagram of the unknot.

Let +I denote addition of a crossing to a knot diagram by a type I Reidemeister move. Let -I denote removal of a crossing by a type I move. Similarly, let +II (-II) denote addition (removal) of a pair of crossings by a type II Reidemeister move. Let III denote a type III Reidemeister move.

For a knot diagram D, let D|m denote the set of the diagrams which may result when a move m is applied to D. Let D|M denote the set of the diagrams which may result when a move from the set M is applied to D. Let D|M* denote the set of diagrams which may result when a finite sequence of moves from the set M is applied to D. Examples: all possible diagrams of a knot with diagram K may be written as K|{+I,-I,+II,-II,III}* ; this page is largely concerned with the set of all unknot diagrams U0|{+I,-I,+II,-II,III}*.

Write a particular element of D|M* as D|t1|...|tn to mean the result of applying transformations t1,...,tn to D. Each transformation ti consists of a move mi from M plus information to describe where in D|t1|...|ti-1 the move mi should be applied.

Principle of Move Transposition (PMT) : If a diagram D|...|T1|T2|... contains two adjacent transformation sequences T1 and T2 which change disjoint regions then the diagram is unchanged by transposing T1 and T2, i.e. D|...|T1|T2|... = D|...|T2|T1|...

U0, the trivial diagram
of the unknot    Theorem 1: U0|{+I}* = U0|{+I,-I}*     [proof]

Theorem 2: U0|{+II}* = U0|{+II,-II}*     [proof]

The predicate ArbReduce0 captures the reduction of a diagram to U0 by successive removal of crossings via arbitrary moves from a set M. Define ArbReduce0(S, M) for a set M of crossing-removal moves to mean for any diagram D in the set S,

• Either D = U0 or
• D|M is not empty AND ArbReduce0(D|M, M)

Theorem 1 implies ArbReduce0(U0|{+I}*, {-I}).

Theorem 2 implies ArbReduce0(U0|{+II}*, {-II}).

Conjecture 6 : ArbReduce0(U0|{+II}*, {-I,-II})

## Chronology / Working

Assorted Unknot diagrams
A Nasty Unknot - Based on Goeritz's unknot The Monster - Based on file
'monster-init.kps' from [KnotPlot] Cousin It - Based on file
'ks-init.kps' from [KnotPlot] Nemesis - An unknot of Thistlethwaite 9th Feb 2001

• Purchased a copy of [Adams94]. Was horrified at the described length and complexity of Haken's 1961 unknot-equivalence algorithm. Jumped on bus to spend weekend in Canberra.

11th Feb 2001

• Formulated conjecture 1 : a -I, -II or -IIcontrived move can be applied to any unknot diagram with crossings. [proved false by counter-example - e.g. The Monster]
• Read [Hayes97] - complexity of current unknot-equivalence algorithms still seems to be around O(2n) for a diagram with n crossings. 12th Feb 2001

• Decided I didn't have a clue how to prove conjecture 1, so tried something simpler: Formulated conjecture 2 : starting with U0 and performing a sequence of +I moves, the resulting diagram may be reduced to U0 by successive arbitrary type -I moves [proved true 13th-16th Feb - see Theorem 1]

13th Feb 2001

• Downloaded [KnotPlot]. Was chastised to discover scary unknot diagrams like The Monster and Cousin It, which well and truly sank conjecture 1.
• Proved conjecture 2 by graph-theory arguments, but formulation messy -- essentially the graph of any U0|{+I}* diagram can be drawn as a tree of n-gons joined by vertices where each edge is part of the outer boundary ; the n-gon tree further corresponds to a normal tree, where +I and -I moves correspond to leaf addition and removal.
• Formulated conjecture 3 : any unknot diagram with crossings can be simplified by locating a line segment with a sequence of all-over or all-under crossings with endpoints in the infinite planar region, removing the segment and replacing it with an arc in the infinite planar region [proved false by counter-example - e.g. step 3 of Untangling the Monster].

14th Feb 2001

• Started this web page to rid myself of scrap paper scribbles. Gave up trying to use special-purpose software to render knot diagrams & just used a drawing program.
• Found more elegant constructive proof of conjecture 2 - see Theorem 1.
• Found counter-example to conjecture 3 (step 3 of Untangling the Monster). My conjectures have a very short life expectancy.
• Concocted the -R move: let -R denote the removal of crossings from a diagram by locating a line segment with a sequence of all-over or all-under crossings with endpoints in some planar region, removing the segment and replacing it with an arc in the region. The -R move includes -I, -II and -IIcontrived moves. See Untangling the Monster and Untangling the Cousin It for examples of -R moves.
• Formulated conjecture 4 : ArbReduce0(U0|{+I,-I,+II,-II,III}*, {-R}). [proved false by counter-example - e.g. Goeritz's unknot]
• Valentine's day - my SO is in another city, so I romanticly mailed her a parking ticket :-).

16th Feb 2001

• Made up the D|t notation. Typed up this proof:
Theorem 1: U0|{+I}* = U0|{+I,-I}*

Proof:

• U0|{+I}* is a subset of U0|{+I,-I}* since {+I} is a subset of {+I,-I}.
• For any D = U0|t1|t2|...|tn in U0|{+I,-I}*,
• If all ti are +I then D is in U0|{+I}*.
• If least one ti is -I then let tk be the first. U0|t1|t2|...|tk-1 has exactly k - 1 crossings. The crossing removed by tk has either
• exactly one loop, generated by some tj where j < k.
D = U0|t1|...|tj-1|tj|tk|tj+1|...|tk-1|tk+1|...|tn (tk moved by PMT)
= U0|t1|...|tj-1|tj+1|...|tk-1|tk+1|...|tn (tj, tk cancel)
• two loops, in which case U0|t1|t2|...|tk-1 has exactly one crossing, so k = 2, U0|t1|t2 = U0 and D = U0|t1|t2|t3|...|tn = U0|t3|...|tn.

In each case, D may be expressed as U0|t'1|...|t'n-2 containing one less -I move. Successive removal of -I moves yields D is in U0|{+I}*.

In each case D is in U0|{+I}*, so U0|{+I,-I}* is a subset of U0|{+I}*

17th Feb 2001

• Started investigating U0|{+II}*. Jumped on bus to spend weekend in Canberra.

19th Feb 2001

20th Feb 2001

• Dental visit from hell. Plenty of time to doodle knots while recovering.
• Tidied up proof of Theorem 1. Tried reorganising cases as zero -I moves / one trailing -I move / more than one -I moves, but it just got uglier.
• Sketched proof outline for conjecture 5

21st Feb 2001

• Developed PMT to formalise notions of move cancellation ; annotated proof of Theorem 1 to refer to PMT
• Finished proof of conjecture 5, renamed Theorem 2:
Theorem 2: U0|{+II}* = U0|{+II,-II}*

Proof:

• U0|{+II}* is a subset of U0|{+II,-II}* since {+II} is a subset of {+II,-II}.
• For any D = U0|t1|t2|...|tn in U0|{+II,-II}*,
• If all ti are +II then D is in U0|{+II}*.
• If least one ti is -II then let tk be the first. U0|t1|t2|...|tk-1 has exactly 2(k - 1) crossings. The pair of crossings removed by tk were either
• generated by a single +II move tj where j < k.
D = U0|t1|...|tj-1|tj|tk|tj+1|...|tk-1|tk+1|...|tn (tk moved by PMT)
= U0|t1|...|tj-1|tj+1|...|tk-1|tk+1|...|tn (tj, tk cancel)
• generated by two distinct +II moves, say ti and tj where i < j < k. Then
D = U0|t1|...|tj-1|tj|tk|tj+1|...|tk-1|tk+1|...|tn (tk moved by PMT - see fig 2.1)
= U0|t1|...|tj-1|tj+1|...|tk-1|tk+1|...|tn (tj, tk cancel - see fig 2.2)

In each case, D may be expressed as U0|t'1|...|t'n-2 containing one less -II move. Successive removal of -II moves yields D is in U0|{+II}*.
In each case D is in U0|{+II}*, so U0|{+II,-II}* is a subset of U0|{+II}*

 U0|...|ti U0|...|ti...|tj-1 U0|...|ti...|tj U0|...|ti...|tj...|tk-1 U0|...|ti...|tj...|tk     U0|...|ti U0|...|ti...|tj-1 U0|...|ti...|tj-1|tj U0|...|ti...|tj-1|tj|tk = U0|...|ti...|tj-1 U0|...|ti...|tj-1|tj|tk|tj+1...|tk-1 = U0|...|ti...|tj-1|tj+1...|tk-1     • Formulated conjecture 6 : ArbReduce0(U0|{+II}*, {-I,-II})
• Defined the -R move and reworded conjecture 4 to use the more succint notation

22nd Feb 2001

• Added [Hass99] to list of references.

23rd Feb 2001

• Weekend spent in Brisbane moving stuff out of storage
• Defined ArbReduce0 predicate & used it to shorten the wording for some conjectures

26th Feb 2001

• Decided that exploration of unknot diagrams is in order. Devised the oknion notation for general knot/link diagrams on the train home from work.

28th Feb 2001

Early Mar 2001

• Researched encodings of planar graphs to find efficient schemes which could be adapted to efficiently and unambiguously encode knot diagrams.

18th Mar 2001

13th Apr 2001

18th Apr 2001

• Began work on a Perl module for representing the Quad-Edge Data Structure [Guibas85]

Early May 2001

• Solved on paper a few more trivial theorems involving ArbReduce0 and type I & II moves, but would like to find a more concise proof layout than tedious wading-through-the-cases before writing them up.
• Got sidetracked by work on MINSE

22nd May 2001

• Received email from John Steinberger about the top-secret generalized S move!

8th Dec 2001

 1: 2: 3: 4:                         ## References

• [Adams94] Colin C. Adams. The Knot Book - An Elementary Introduction to the Mathematical Theory of Knots. W. H. Freeman and Company, New York, 1994.
• [Guibas85] Leonidas Guibas & Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, vol 4, no 2, April 1985, pp 74-123.
• [KnotPlot] Rob Scharein's marvellous KnotPlot software. http://www.pims.math.ca/knotplot
• [Hayes97] Brian Hayes. Square Knots, Computing Science column in American Scientist, November-December 1997.
• [Hass98] Joel Hass and Jeffrey C. Lagarias. The number of Reidemeister Moves Needed for Unknotting. Preprint, July 1998. [arXiv:math.GT/9807012] [citeseer.nj.nec.com/hass98number.html]
• [Hass99] Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The Computational Complexity of Knot and Link Problems. Journal of the ACM, Vol. 46, No. 2 (March 1999), p.185 [Postscript preprint] This pagelast changed:22 May 2003 [Validate HTML] Donate freefood & land Anzwers Google Websters Dict. Wiktionary Roget's Thes. Open Directory WikiPedia Google News FTP -- English FTP -- Russian Tellaseek Tucows FileDudes Debian Linux MetaCrawler Alta Vista Yahoo RPM Find Perl Modules Search4Science f2.org - This site for Feedback by emailor Web form