Recognition algorithms in knot theory

I. A. Dynnikov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 58 (2003) no. 6, pp. 1093-1139

Résumé

In this paper the problem of constructing algorithms for comparing knots and links is discussed. A survey of existing approaches and basic results in this area is given. In particular, diverse combinatorial methods for representing links are discussed, the Haken algorithm for recognizing a trivial knot (the unknot) and a scheme for constructing a general algorithm (using Haken's ideas) for comparing links are presented, an approach based on representing links by closed braids is described, the known algorithms for solving the word problem and the conjugacy problem for braid groups are described, and the complexity of the algorithms under consideration is discussed. A new method of combinatorial description of knots is given together with a new algorithm (based on this description) for recognizing the unknot by using a procedure for monotone simplification. In the conclusion of the paper several problems are formulated whose solution could help to advance towards the “algorithmization” of knot theory.

Bibliographie

[1] T. P. Kirkman, “The enumeration, description and construction of knots of fewer that ten crossings”, Trans. Roy. Soc. Edinburgh, 32 (1885), 281–309

[2] P. G. Tait, “On knots”, Trans. Roy. Soc. Edinburgh, 28 (1877), 145–190

[3] J. W. Alexander, G. B. Briggs, “On types of knotted curved”, Ann. of Math., 28 (1926/27), 562–586 | DOI | MR

[4] K. Reidemeister, Knotentheorie, Ergeb. Math. Grenzgeb., 1. No. 1, Springer-Verlag, Berlin, 1932 | Zbl

[5] J. W. Alexander, “A lemma on systems of knotted curves”, Proc. Natl. Acad. Sci. USA, 9 (1923), 93–95 | DOI | Zbl

[6] A. A. Markoff, “Über die freie Äquivalenz der geschlossenen Zöpfe”, Matem. sb., 1(43):1 (1936), 73–78 | Zbl

[7] E. Artin, “Theorie der Zöpfe”, Abh. Math. Sem. Univ. Hamburg, 4 (1925), 47–72 | DOI | Zbl

[8] E. Artin, “Theory of braids”, Ann. of Math. (2), 48:1 (1947), 101–126 | DOI | MR | Zbl

[9] W. Haken, “Theorie der Normalflächen. Ein Isotopiekriterium für der Kreisknoten”, Acta Math., 105:3–4 (1961), 245–375 | DOI | MR | Zbl

[10] H. Kneser, “Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten”, Jahresber. Deutsch. Math.-Verein., 38 (1929), 248–260 | Zbl

[11] H. Schubert, “Bestimmung der Primfactorzerlegung von Verkettungen”, Math. Z., 76 (1961), 116–148 | DOI | MR | Zbl

[12] H. Schubert, “Die eindeutige Zerlegbarkeit eines Knotens in Primknoten”, S.-B. Heidelberger Akad. Wiss. Math.-Nat. Kl., 1949:3 (1949), 57–104 | MR

[13] Y. Hashizume, “On the uniqueness of the decomposition of a link”, Osaka Math. J., 10 (1958), 283–300 ; 11 (1959), 249 | MR | MR | Zbl

[14] W. Haken, “Ein Verfahren zur Aufspaltung einer 3-Mannigfaltigkeit in irreduzible 3-Mannigfaltigkeiten”, Math. Z., 76 (1961), 427–467 | DOI | MR | Zbl

[15] W. Haken, “Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I”, Math. Z., 80 (1962), 89–120 | DOI | MR | Zbl

[16] F. Waldhausen, “On irreducible 3-manifolds which are sufficiently large”, Ann. of Math. (2), 87 (1968), 56–88 | DOI | MR | Zbl

[17] K. Johannson, Homotopy Equivalences of 3-Manifolds with Boundaries, Lecture Notes in Math., 761, Springer-Verlag, Berlin, 1979 | MR | Zbl

[18] W. Jaco, P. Shalen, “Seifert fibered spaces in 3-manifolds”, Mem. Amer. Math. Soc., 21, no. 220, 1979 | MR

[19] G. Hemion, “On the classification of homeomorphisms of 2-manifolds and the classification of 3-manifolds”, Acta Math., 142:1–2 (1979), 123–155 | DOI | MR | Zbl

[20] F. Waldhausen, “Recent results on sufficiently large 3-manifolds”, Algebraic and Geometric Topology, Part 2, Proc. Sympos. Pure Math., 32, Amer. Math. Soc., Providence, RI, 1978, 21–38 | MR

[21] K. Johannson, “Classification problems in low-dimensional topology”, Geometric and Algebraic Topology, Banach Center Publ., 18, PWN, Warsaw, 1986, 37–59 | MR

[22] G. Hemion, The Classification of Knots and 3-Dimensional Spaces, Clarendon Press, Oxford Univ. Press, New York, 1992 | MR

[23] S. V. Matveev, “On the recognition problem for Haken 3-manifolds”, Proceedings of the Workshop on Differential Geometry and Topology (Palermo, June 3–9, 1996), Suppl. Rend. Circ. Mat. Palermo, 49, eds. R. Grimaldi et al., Circolo Matematico di Palermo, Palermo, 1997, 131–148 | MR | Zbl

[24] W. Thurston, “On the geometry and dynamics of diffeomorphisms of surfaces”, Bull. Amer. Math. Soc. (N.S.), 19:2 (1988), 417–431 | DOI | MR | Zbl

[25] M. Bestvina, M. Handel, “Train-tracks for surface homeomorphisms”, Topology, 34:1 (1995), 109–140 | DOI | MR | Zbl

[26] S. V. Matveev, Algorithmic Topology and Classification of 3-Manifolds, Algorithms Comput. Math., 9, Springer-Verlag, Berlin, 2003 | MR

[27] W. P. Thurston, “Three dimensional manifolds, Kleinian groups and hyperbolic geometry”, Bull. Amer. Math. Soc. (N.S.), 6 (1982), 357–379 | DOI | MR | Zbl

[28] M. Kapovich, Hyperbolic Manifolds and Discrete Groups, Progr. Math., 183, Birkhäuser, Boston, MA, 2001 | MR | Zbl

[29] G. S. Makanin, “Problema sopryazhennosti v gruppe kos”, Dokl. AN SSSR, 182:3 (1968), 495–496 | MR | Zbl

[30] F. A. Garside, “The braid group and other groups”, Quart. J. Math. Oxford Ser. (2), 20:78 (1969), 235–254 | DOI | MR | Zbl

[31] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Patterson, W. P. Thurston, Word Processing in Groups, Jones and Bartlett, Boston, 1992 | MR | Zbl

[32] E. A. El-Rifai, H. R. Morton, “Algorithms for positive braids”, Quart. J. Math. Oxford Ser. (2), 45:180 (1994), 479–497 | DOI | MR

[33] J. Birman, K. H. Ko, S. J. Lee, “The infimum, supremum, and geodesic length of a braid conjugacy class”, Adv. Math., 164:1 (2001), 41–56 | DOI | MR | Zbl

[34] N. Franco, J. González-Meneses, “Conjugacy problem for braid groups and Garside groups”, J. Algebra, 266:1 (2003), 112–132 | DOI | MR | Zbl

[35] J. Birman, W. Menasco, “Studying links via closed braids. I: A finiteness theorem”, Pacific J. Math., 154:1 (1992), 17–36 | MR | Zbl

[36] J. Birman, W. Menasco, “Studying links via closed braids. II: On a theorem of Bennequin”, Topology Appl., 40:1 (1991), 71–82 | DOI | MR | Zbl

[37] J. Birman, W. Menasco, “Studying links via closed braids. III: Classifying links which are closed 3-braids”, Pacific J. Math., 161:1 (1993), 25–113 | MR | Zbl

[38] J. Birman, W. Menasco, “Studying links via closed braids. IV: Composite links and split links”, Invent. Math., 102:1 (1990), 115–139 | DOI | MR | Zbl

[39] J. Birman, W. Menasco, “Studying links via closed braids. V: The unlink”, Trans. Amer. Math. Soc., 329:2 (1992), 585–606 | DOI | MR | Zbl

[40] J. Birman, W. Menasco, “Studying links via closed braids. VI: A nonfiniteness theorem”, Pacific J. Math., 156:2 (1992), 265–285 | MR

[41] J. Birman, W. Menasco, Stabilization in the braid groups, math/0310279

[42] J. Birman, M. Hirsch, “A new algorithm for recognizing the unknot”, Geom. Topol., 2:9 (1998), 175–220 | MR | Zbl

[43] I. A. Dynnikov, Arc-presentations of links. Monotonic simplification, math/0208153 | MR

[44] J. H. Conway, “An enumeration of knots and links, and some of their algebraic properties”, Computational Problems in Abstract Algebra, Proc. Conf. (Oxford, 1967), Pergamon, Oxford, 1970, 329–358 | MR

[45] C. H. Dowker, M. B. Thistlethwaite, “Classification of knot projections”, Topol. Appl., 16:1 (1983), 19–31 | DOI | MR | Zbl

[46] J. Hoste, M. Thistlethwaite, J. Weeks, “The first 1,701,936 knots”, Math. Intelligencer, 20:4 (1998), 33–48 | DOI | MR | Zbl

[47] 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:1 (1990), 35–53 | DOI | MR | Zbl

[48] R. H. Crowell, R. H. Fox, Introduction to Knot Theory, Ginn, Boston, 1963 ; R. Krouell, R. Foks, Vvedenie v teoriyu uzlov, Mir, M., 1967 | MR | Zbl | MR

[49] G. Burde, H. Zieschang, Knots, de Gruyter Stud. Math., 5, de Gruyter, Berlin, 1985 | MR | Zbl

[50] J. Birman, Braids, Links, and Mapping Class Groups, Ann. of Math. Stud., 82, Princeton Univ. Press / Univ. of Tokyo Press, Princeton / Tokyo, 1974 | MR

[51] P. Cromwell, “Embedding knots and links in an open book. I: Basic properties”, Topology Appl., 64 (1995), 37–58 | DOI | MR | Zbl

[52] P. Vogel, “Representation of links by braids: A new algorithm”, Comment. Math. Helv., 65:1 (1990), 104–113 | DOI | MR | Zbl

[53] W. D. Neumann, G. A. Swarup, “Canonical decompositions of 3-manifolds”, Geom. Topol., 1 (1997), 21–40 | DOI | MR | Zbl

[54] J. Hass, “Algorithms for recognizing knots and 3-manifolds”, Chaos Solitons Fractals, 9:4–5 (1998), 569–581 | DOI | MR | Zbl

[55] F. Bohnenblust, “The algebraical braid group”, Ann. of Math. (2), 48 (1947), 127–136 | DOI | MR | Zbl

[56] W.-L. Chow, “On the algebraical braid group”, Ann. of Math. (2), 49:3 (1948), 654–658 | DOI | MR | Zbl

[57] P. Dehornoy, I. Dynnikov, D. Rolfsen, B. Wiest, Why are Braids Orderable?, Panor. Synthèses, 14, Soc. Math. France, Paris, 2002 | MR | Zbl

[58] I. A. Dynnikov, “Ob odnom otobrazhenii Yanga–Bakstera i uporyadochenii Deornua”, UMN, 57:3 (2002), 151–152 | MR | Zbl

[59] P. Dehornoy, Braids and Self-Distributivity, Progr. Math., 192, Birkhäuser, Basel, 2000 | MR | Zbl

[60] A. V. Malyutin, “Bystrye algoritmy raspoznavaniya i sravneniya kos”, Zap. nauch. semin. POMI, 279 (2001), 200–215

[61] S. I. Adyan, “O fragmentakh slova $\Delta$ v gruppe kos”, Matem. zametki, 36:1 (1984), 25–34 | MR | Zbl

[62] P. Dehornoy, “Groups with a complemented presentation”, J. Pure Appl. Algebra, 116:1–3 (1997), 115–137 | DOI | MR | Zbl

[63] P. Dehornoy, “A fast method for comparing braids”, Adv. Math., 125:2 (1997), 200–235 | DOI | MR | Zbl

[64] J. Birman, K. H. Ko, S. J. Lee, “A new approach to the word and conjugacy problems in the braid groups”, Adv. Math., 139:2 (1998), 322–353 | DOI | MR | Zbl

[65] J. S. Birman, P. Boldi, M. Rampichini, S. Vigna, “Towards an implementation of the B-H algorithm for recognizing the unknot”, J. Knot Theory Ramifications, 11:4 (2002), 601–645 | DOI | MR | Zbl

[66] L. Goeritz, “Bemerkungen zur knotentheorie”, Abh. Math. Sem. Univ. Hamburg, 10 (1934), 201–210 | DOI | Zbl

[67] H. R. Morton, “An irreducible 4-string braid with unknotted closure”, Math. Proc. Cambridge Philos. Soc., 93:2 (1983), 259–261 | DOI | MR | Zbl

[68] D. Bennequin, “Entrelacements et équations de Pfaff”, Astérisque, 107–108 (1983), 87–161 ; D. Benneken, “Zatsepleniya i uravneniya Pfaffa”, UMN, 44:3 (1989), 3–53 | MR | Zbl | MR

[69] J. Hass, J. C. Lagarias, N. Pippenger, “The computational complexity of knot and link problems”, J. ACM, 46:2 (1999), 185–211 | DOI | MR | Zbl

[70] I. Agol, J. Hass, W. Thurston, The computational complexity of knot genus and spanning area, math/0205057 | MR

[71] W. Jaco, J. L. Tollefson, “Algorithms for the complete decomposition of a closed 3-manifold”, Illinois J. Math., 39:3 (1995), 358–406 | MR | Zbl

[72] I. A. Dynnikov, “Trekhstranichnye predstavleniya uzlov. Kodirovanie i lokalnye dvizheniya”, Funkts. analiz i ego pril., 33:4 (1999), 25–37 | MR | Zbl

[73] I. A. Dynnikov, “Trekhstranichnye predstavleniya uzlov. Universalnaya polugruppa”, Funkts. analiz i ego pril., 34:1 (2000), 29–40 | MR | Zbl

[74] I. A. Dynnikov, “Konechno opredelennye gruppy i polugruppy v teorii uzlov”, Tr. MIAN, 231, 2000, 231–248 | MR | Zbl

[75] I. A. Dynnikov, “A new way to represent links. One-dimensional formalism and untangling technology”, Acta Appl. Math., 69:3 (2001), 243–283 | DOI | MR | Zbl

[76] I. A. Dynnikov, “Finitely presented semigroups in knot theory. Oriented case”, Geometry, Topology and Mathematical Physics, S. P. Novikov's Seminar 2001–2003, Amer. Math. Soc. Tranls. Ser. 2, eds. V. M. Buchstaber, I. M. Krichever, 2004 | MR | Zbl