A polynomial upper bound on Reidemeister moves

Abstract

We prove that any diagram of the unknot with $c$ crossings may be reduced to the trivial diagram using at most $(236 \,c)^{11}$ Reidemeister moves.

  • [1] I. Agol, Knot genus is NP, 2002.
    @misc{1,
      author = {Agol, I.},
      title = {Knot genus is {NP}},
      note = {conference presentation},
      year = {2002},
      zblnumber = {1192.68305},
      }
  • [2] D. Bennequin, "Entrelacements et équations de Pfaff," in Third Schnepfenried Geometry Conference, Vol. 1, Paris: Soc. Math. France, 1983, vol. 107, pp. 87-161.
    @incollection{2, mrkey = {0753131},
      author = {Bennequin, Daniel},
      title = {Entrelacements et équations de {P}faff},
      booktitle = {Third {S}chnepfenried Geometry Conference, {V}ol. 1},
      venue = {{S}chnepfenried, 1982},
      series = {Astérisque},
      volume = {107},
      pages = {87--161},
      publisher = {Soc. Math. France},
      address = {Paris},
      year = {1983},
      mrclass = {58F18 (57R15)},
      mrnumber = {0753131},
      mrreviewer = {Yakov Eliashberg},
      zblnumber = {0573.58022},
      }
  • [3] Go to document J. S. Birman and E. Finkelstein, "Studying surfaces via closed braids," J. Knot Theory Ramifications, vol. 7, iss. 3, pp. 267-334, 1998.
    @article{3, mrkey = {1625362},
      author = {Birman, Joan S. and Finkelstein, Elizabeth},
      title = {Studying surfaces via closed braids},
      journal = {J. Knot Theory Ramifications},
      fjournal = {Journal of Knot Theory and its Ramifications},
      volume = {7},
      year = {1998},
      number = {3},
      pages = {267--334},
      issn = {0218-2165},
      mrclass = {57M25},
      mrnumber = {1625362},
      mrreviewer = {Sergei K. Lando},
      doi = {10.1142/S0218216598000176},
      zblnumber = {0907.57006},
      }
  • [4] Go to document J. S. Birman and W. W. Menasco, "Studying links via closed braids. IV. Composite links and split links," Invent. Math., vol. 102, iss. 1, pp. 115-139, 1990.
    @article{4, mrkey = {1069243},
      author = {Birman, Joan S. and Menasco, William W.},
      title = {Studying links via closed braids. {IV}. {C}omposite links and split links},
      journal = {Invent. Math.},
      fjournal = {Inventiones Mathematicae},
      volume = {102},
      year = {1990},
      number = {1},
      pages = {115--139},
      issn = {0020-9910},
      coden = {INVMBH},
      mrclass = {57M25 (20F36)},
      mrnumber = {1069243},
      mrreviewer = {Hugh Reynolds Morton},
      doi = {10.1007/BF01233423},
      zblnumber = {0711.57006},
      }
  • [5] Go to document A. Coward and M. Lackenby, "An upper bound on Reidemeister moves," Amer. J. Math., vol. 136, iss. 4, pp. 1023-1066, 2014.
    @article{5, mrkey = {3245186},
      author = {Coward, Alexander and Lackenby, Marc},
      title = {An upper bound on {R}eidemeister moves},
      journal = {Amer. J. Math.},
      fjournal = {American Journal of Mathematics},
      volume = {136},
      year = {2014},
      number = {4},
      pages = {1023--1066},
      issn = {0002-9327},
      mrclass = {57M27 (57M25)},
      mrnumber = {3245186},
      mrreviewer = {Stefan K. Friedl},
      doi = {10.1353/ajm.2014.0027},
      zblnumber = {06337019},
      }
  • [6] Go to document P. R. Cromwell, "Embedding knots and links in an open book. I. Basic properties," Topology Appl., vol. 64, iss. 1, pp. 37-58, 1995.
    @article{6, mrkey = {1339757},
      author = {Cromwell, Peter R.},
      title = {Embedding knots and links in an open book. {I}. {B}asic properties},
      journal = {Topology Appl.},
      fjournal = {Topology and its Applications},
      volume = {64},
      year = {1995},
      number = {1},
      pages = {37--58},
      issn = {0166-8641},
      coden = {TIAPD9},
      mrclass = {57M25},
      mrnumber = {1339757},
      mrreviewer = {Hugh Reynolds Morton},
      doi = {10.1016/0166-8641(94)00087-J},
      zblnumber = {0845.57004},
      }
  • [7] Go to document P. R. Cromwell and I. J. Nutt, "Embedding knots and links in an open book. II. Bounds on arc index," Math. Proc. Cambridge Philos. Soc., vol. 119, iss. 2, pp. 309-319, 1996.
    @article{7, mrkey = {1357047},
      author = {Cromwell, Peter R. and Nutt, Ian J.},
      title = {Embedding knots and links in an open book. {II}. {B}ounds on arc index},
      journal = {Math. Proc. Cambridge Philos. Soc.},
      fjournal = {Mathematical Proceedings of the Cambridge Philosophical Society},
      volume = {119},
      year = {1996},
      number = {2},
      pages = {309--319},
      issn = {0305-0041},
      coden = {MPCPCO},
      mrclass = {57M25},
      mrnumber = {1357047},
      mrreviewer = {Hugh Reynolds Morton},
      doi = {10.1017/S0305004100074181},
      zblnumber = {0860.57007},
      }
  • [8] Go to document I. A. Dynnikov, "Arc-presentations of links: monotonic simplification," Fund. Math., vol. 190, pp. 29-76, 2006.
    @article{8, mrkey = {2232855},
      author = {Dynnikov, I. A.},
      title = {Arc-presentations of links: monotonic simplification},
      journal = {Fund. Math.},
      fjournal = {Fundamenta Mathematicae},
      volume = {190},
      year = {2006},
      pages = {29--76},
      issn = {0016-2736},
      mrclass = {57M25},
      mrnumber = {2232855},
      mrreviewer = {Nikolai N. Saveliev},
      doi = {10.4064/fm190-0-3},
      zblnumber = {1132.57006},
      }
  • [9] Go to document W. Floyd and U. Oertel, "Incompressible surfaces via branched surfaces," Topology, vol. 23, iss. 1, pp. 117-125, 1984.
    @article{9, mrkey = {0721458},
      author = {Floyd, W. and Oertel, U.},
      title = {Incompressible surfaces via branched surfaces},
      journal = {Topology},
      fjournal = {Topology. An International Journal of Mathematics},
      volume = {23},
      year = {1984},
      number = {1},
      pages = {117--125},
      issn = {0040-9383},
      coden = {TPLGAF},
      mrclass = {57N10},
      mrnumber = {0721458},
      mrreviewer = {John Hempel},
      doi = {10.1016/0040-9383(84)90031-4},
      zblnumber = {0524.57008},
      }
  • [10] Go to document O. Goldreich, Computational Complexity. A Conceptual Perspective, Cambridge: Cambridge Univ. Press, 2008.
    @book{10, mrkey = {2400985},
      author = {Goldreich, Oded},
      title = {Computational Complexity. A Conceptual Perspective},
      publisher = {Cambridge Univ. Press},
      address = {Cambridge},
      year = {2008},
      pages = {xxiv+606},
      isbn = {978-0-521-88473-0},
      mrclass = {68-01 (03D15 68Q15 68Q17 68Q25 94A60 94A62)},
      mrnumber = {2400985},
      mrreviewer = {Gerhard Lischke},
      doi = {10.1017/CBO9780511804106},
      zblnumber = {1154.68056},
      }
  • [11] Go to document W. Haken, "Theorie der Normalflächen," Acta Math., vol. 105, pp. 245-375, 1961.
    @article{11, mrkey = {0141106},
      author = {Haken, Wolfgang},
      title = {Theorie der {N}ormalflächen},
      journal = {Acta Math.},
      fjournal = {Acta Mathematica},
      volume = {105},
      year = {1961},
      pages = {245--375},
      issn = {0001-5962},
      mrclass = {55.20 (55.60)},
      mrnumber = {0141106},
      doi = {10.1007/BF02559591},
      zblnumber = {0100.19402},
      }
  • [12] Go to document W. Haken, "Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I," Math. Z., vol. 80, pp. 89-120, 1962.
    @article{12, mrkey = {0160196},
      author = {Haken, Wolfgang},
      title = {Über das {H}omöomorphieproblem der 3-{M}annigfaltigkeiten. {I}},
      journal = {Math. Z.},
      fjournal = {Mathematische Zeitschrift},
      volume = {80},
      year = {1962},
      pages = {89--120},
      issn = {0025-5874},
      mrclass = {54.78},
      mrnumber = {0160196},
      mrreviewer = {D. B. A. Epstein},
      doi = {10.1007/BF01162369},
      zblnumber = {0106.16605},
      }
  • [13] Go to document J. Hass and J. C. Lagarias, "The number of Reidemeister moves needed for unknotting," J. Amer. Math. Soc., vol. 14, iss. 2, pp. 399-428, 2001.
    @article{13, mrkey = {1815217},
      author = {Hass, Joel and Lagarias, Jeffrey C.},
      title = {The number of {R}eidemeister moves needed for unknotting},
      journal = {J. Amer. Math. Soc.},
      fjournal = {Journal of the American Mathematical Society},
      volume = {14},
      year = {2001},
      number = {2},
      pages = {399--428},
      issn = {0894-0347},
      mrclass = {57M25 (57M27 68W40)},
      mrnumber = {1815217},
      mrreviewer = {Lorenzo Traldi},
      doi = {10.1090/S0894-0347-01-00358-7},
      zblnumber = {0964.57005},
      }
  • [14] Go to document J. Hass, J. C. Lagarias, and N. Pippenger, "The computational complexity of knot and link problems," J. ACM, vol. 46, iss. 2, pp. 185-211, 1999.
    @article{14, mrkey = {1693203},
      author = {Hass, Joel and Lagarias, Jeffrey C. and Pippenger, Nicholas},
      title = {The computational complexity of knot and link problems},
      journal = {J. ACM},
      fjournal = {Journal of the ACM},
      volume = {46},
      year = {1999},
      number = {2},
      pages = {185--211},
      issn = {0004-5411},
      mrclass = {68Q25 (57M25)},
      mrnumber = {1693203},
      mrreviewer = {Lorenzo Traldi},
      doi = {10.1145/301970.301971},
      zblnumber = {1065.68667},
      }
  • [15] Go to document J. Hass and T. Nowik, "Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle," Discrete Comput. Geom., vol. 44, iss. 1, pp. 91-95, 2010.
    @article{15, mrkey = {2639820},
      author = {Hass, Joel and Nowik, Tahl},
      title = {Unknot diagrams requiring a quadratic number of {R}eidemeister moves to untangle},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {44},
      year = {2010},
      number = {1},
      pages = {91--95},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {57M25 (68U05)},
      mrnumber = {2639820},
      mrreviewer = {Peiyi Zhao},
      doi = {10.1007/s00454-009-9156-4},
      zblnumber = {1191.57006},
      }
  • [16] Go to document J. Hass, J. Snoeyink, and W. P. Thurston, "The size of spanning disks for polygonal curves," Discrete Comput. Geom., vol. 29, iss. 1, pp. 1-17, 2003.
    @article{16, mrkey = {1946790},
      author = {Hass, Joel and Snoeyink, Jack and Thurston, William P.},
      title = {The size of spanning disks for polygonal curves},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {29},
      year = {2003},
      number = {1},
      pages = {1--17},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {57M25},
      mrnumber = {1946790},
      mrreviewer = {Lorenzo Traldi},
      doi = {10.1007/s00454-002-2707-6},
      zblnumber = {1015.57008},
      }
  • [17] Go to document G. Hemion, "On the classification of homeomorphisms of $2$-manifolds and the classification of $3$-manifolds," Acta Math., vol. 142, iss. 1-2, pp. 123-155, 1979.
    @article{17, mrkey = {0512214},
      author = {Hemion, Geoffrey},
      title = {On the classification of homeomorphisms of {$2$}-manifolds and the classification of {$3$}-manifolds},
      journal = {Acta Math.},
      fjournal = {Acta Mathematica},
      volume = {142},
      year = {1979},
      number = {1-2},
      pages = {123--155},
      issn = {0001-5962},
      coden = {ACMAA8},
      mrclass = {57N05 (57N10)},
      mrnumber = {0512214},
      mrreviewer = {J. S. Birman},
      doi = {10.1007/BF02395059},
      zblnumber = {0402.57027},
      }
  • [18] Go to document A. Henrich and L. H. Kauffman, "Unknotting unknots," Amer. Math. Monthly, vol. 121, iss. 5, pp. 379-390, 2014.
    @article{18, mrkey = {3193721},
      author = {Henrich, Allison and Kauffman, Louis H.},
      title = {Unknotting unknots},
      journal = {Amer. Math. Monthly},
      fjournal = {American Mathematical Monthly},
      volume = {121},
      year = {2014},
      number = {5},
      pages = {379--390},
      issn = {0002-9890},
      mrclass = {57M27},
      mrnumber = {3193721},
      doi = {10.4169/amer.math.monthly.121.05.379},
      zblnumber = {06367521},
      }
  • [19] Go to document W. Jaco and U. Oertel, "An algorithm to decide if a $3$-manifold is a Haken manifold," Topology, vol. 23, iss. 2, pp. 195-209, 1984.
    @article{19, mrkey = {0744850},
      author = {Jaco, William and Oertel, Ulrich},
      title = {An algorithm to decide if a {$3$}-manifold is a {H}aken manifold},
      journal = {Topology},
      fjournal = {Topology. An International Journal of Mathematics},
      volume = {23},
      year = {1984},
      number = {2},
      pages = {195--209},
      issn = {0040-9383},
      coden = {TPLGAF},
      mrclass = {57N10},
      mrnumber = {0744850},
      mrreviewer = {Martin Scharlemann},
      doi = {10.1016/0040-9383(84)90039-9},
      zblnumber = {0545.57003},
      }
  • [20] Go to document W. Jaco and J. L. Tollefson, "Algorithms for the complete decomposition of a closed $3$-manifold," Illinois J. Math., vol. 39, iss. 3, pp. 358-406, 1995.
    @article{20, mrkey = {1339832},
      author = {Jaco, William and Tollefson, Jeffrey L.},
      title = {Algorithms for the complete decomposition of a closed {$3$}-manifold},
      journal = {Illinois J. Math.},
      fjournal = {Illinois Journal of Mathematics},
      volume = {39},
      year = {1995},
      number = {3},
      pages = {358--406},
      issn = {0019-2082},
      coden = {IJMTAW},
      mrclass = {57N10},
      mrnumber = {1339832},
      mrreviewer = {Darren D. Long},
      url = {http://projecteuclid.org/euclid.ijm/1255986385},
      zblnumber = {0858.57018},
      }
  • [21] Go to document G. Kuperberg, "Knottedness is in ${ NP}$, modulo GRH," Adv. Math., vol. 256, pp. 493-506, 2014.
    @article{21, mrkey = {3177300},
      author = {Kuperberg, Greg},
      title = {Knottedness is in {${\rm NP}$},
      modulo {GRH}},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {256},
      year = {2014},
      pages = {493--506},
      issn = {0001-8708},
      mrclass = {57M25 (11M26 68Q25)},
      mrnumber = {3177300},
      mrreviewer = {Jonathan Spreer},
      doi = {10.1016/j.aim.2014.01.007},
      zblnumber = {06284931},
      }
  • [22] S. Matveev, Algorithmic Topology and Classification of 3-Manifolds, Second ed., New York: Springer-Verlag, 2007, vol. 9.
    @book{22, mrkey = {2341532},
      author = {Matveev, Sergei},
      title = {Algorithmic Topology and Classification of 3-Manifolds},
      series = {Algorithms Comput. Math.},
      volume = {9},
      edition = {Second},
      publisher = {Springer-Verlag},
      year = {2007},
      pages = {xiv+492},
      isbn = {978-3-540-45898-2},
      mrclass = {57N10 (57M50)},
      mrnumber = {2341532},
      address = {New York},
      zblnumber = {1128.57001},
      }
  • [23] Go to document J. A. Storer, "On minimal-node-cost planar embeddings," Networks, vol. 14, iss. 2, pp. 181-212, 1984.
    @article{23, mrkey = {0741438},
      author = {Storer, James A.},
      title = {On minimal-node-cost planar embeddings},
      journal = {Networks},
      fjournal = {Networks. An International Journal},
      volume = {14},
      year = {1984},
      number = {2},
      pages = {181--212},
      issn = {0028-3045},
      coden = {NTWKAA},
      mrclass = {05C10},
      mrnumber = {0741438},
      mrreviewer = {Mukkai S. Krishnamoorthy},
      doi = {10.1002/net.3230140202},
      zblnumber = {0546.94033},
      }
  • [24] Go to document A. Turing, "Solvable and Unsolvable Problems," Science News, vol. 31, p. 7, 1954.
    @article{24,
      author = {Turing, A.},
      title = {Solvable and Unsolvable Problems},
      journal = {Science News},
      volume = {31},
      year = {1954},
      pages = {7–23},
      url = {http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.247.3954&rep=rep1&type=pdf},
      }

Authors

Marc Lackenby

Mathematical Institute, University of Oxford, Oxford, UK