A new algorithm for recognizing the unknot

Birman, Joan S¹ ; Hirsch, Michael D²

¹ Mathematics Department, Columbia University, New York, New York 10027, USA
² Department of Computer Science, Emory University, Atlanta, Georgia 30322, USA

Geometry & topology, Tome 2 (1998) no. 1, pp. 175-220.

Résumé

The topological underpinnings are presented for a new algorithm which answers the question: “Is a given knot the unknot?” The algorithm uses the braid foliation technology of Bennequin and of Birman and Menasco. The approach is to consider the knot as a closed braid, and to use the fact that a knot is unknotted if and only if it is the boundary of a disc with a combinatorial foliation. The main problems which are solved in this paper are: how to systematically enumerate combinatorial braid foliations of a disc; how to verify whether a combinatorial foliation can be realized by an embedded disc; how to find a word in the the braid group whose conjugacy class represents the boundary of the embedded disc; how to check whether the given knot is isotopic to one of the enumerated examples; and finally, how to know when we can stop checking and be sure that our example is not the unknot.

Détail

DOI : 10.2140/gt.1998.2.175

Keywords: knot, unknot, braid, foliation, algorithm

Bibliographie

[1] D Bennequin, Entrelacements et équations de Pfaff, from: "Third Schnepfenried geometry conference, Vol. 1 (Schnepfenried, 1982)", Astérisque 107, Soc. Math. France (1983) 87

[2] J S Birman, Braids, links, and mapping class groups, Annals of Mathematics Studies 82, Princeton University Press (1974)

[3] J S Birman, E Finkelstein, Studying surfaces via closed braids, J. Knot Theory Ramifications 7 (1998) 267

[4] J Birman, K H Ko, S J Lee, A new approach to the word and conjugacy problems in the braid groups, Adv. Math. 139 (1998) 322

[5] J S Birman, W W Menasco, Studying links via closed braids V: The unlink, Trans. Amer. Math. Soc. 329 (1992) 585

[6] E A El-Rifai, H R Morton, Algorithms for positive braids, Quart. J. Math. Oxford Ser. $(2)$ 45 (1994) 479

[7] F A Garside, The braid group and other groups, Quart. J. Math. Oxford Ser. $(2)$ 20 (1969) 235

[8] W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245

[9] J Hass, Algorithms for recognizing knots and 3–manifolds, Chaos Solitons Fractals 9 (1998) 569

[10] J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185

[11] F Jaeger, D L Vertigan, D J A Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990) 35

[12] E S Kang, K H Ko, S J Lee, Band-generator presentation for the 4–braid group, Topology Appl. 78 (1997) 39

[13] P Vogel, Representation of links by braids: a new algorithm, Comment. Math. Helv. 65 (1990) 104

[14] P Xu, The genus of closed 3–braids, J. Knot Theory Ramifications 1 (1992) 303

[15] S Yamada, The minimal number of Seifert circles equals the braid index of a link, Invent. Math. 89 (1987) 347