4 Th e Knot Book

shown i n Figur e 1.6. An y othe r projectio n wit h on e crossin g ca n b e de -

formed t o look like one of these without undoing the crossing. But each of

these is clearly a trivial knot, as we can then untwist the single crossing.

00

© i

(5)

Figure 1.6 One-crossin g projections .

Exercise 1.2 Sho w that there are no two-crossing nontrivial knots.

Much o f kno t theor y i s concerne d wit h tellin g whic h knot s ar e th e

same an d whic h ar e different . On e simplifie d versio n o f thi s questio n i s

the following: "I f we have a projection o f a knot, can we tell whether i t is

the unknot?"

Certainly, if w e pla y wit h a strin g mode l o f th e knot fo r a while an d

we d o manage t o untangle i t completely, it is the unknot. Bu t what i f w e

play with it for tw o weeks and we still haven't untangled it ? It still might

be the unknot an d fo r al l we know , five mor e minute s o f wor k migh t b e

enough to untangle it. So we can't quit.

But in fact, there is a way to decide if a given projection of a knot is the

unknot. In 1961, Wolfgang Hake n came up with a foolproof procedur e fo r

deciding whether o r not a given knot is the unknot (se e Haken, 1961). Ac-

cording to his theory, we should be able to give our projection o f a knot to

a computer (ho w to give a projection to computers is discussed in Chapter

2), and th e computer woul d ru n th e algorithm an d tel l us whether o r no t

the give n kno t wa s th e unknot. Unfortunately , eve n thoug h Hake n cam e

up wit h hi s algorithm ove r 3 0 years ago , it is so complicated tha t n o on e

has ever written a computer program to implement it.

c&qjnsofoed Problem

Write a computer program that can tell whether a knot that it is given

is the unknot. (Thi s is a difficult proble m tha t requires a complete un -

derstanding o f Haken's algorithm . But beware: His paper is 130 pages

long!)

Aside: In 1974, Haken an d Kennet h Appe l solve d on e o f th e mos t fa -

mous problem s i n mathematics , th e Four-Colo r Theorem . The y prove d