I recently attended a talk by Marc Lackenby on knot theory, and in particular the problem of “quickly” ascertaining that a knot is in fact the unknot, i.e. not knotted at all. “Quickly” here means identifying a knot diagram with n crossings as representing the unknot in only polynomially many operations as a function of n:
Theorem 1 (Lackenby, 2012). Every diagram of the unknot with n crossings can be trivialized using at most (231 n)11 Reidemeister moves.
Lackenby made a good effort to ensure that the first half of the talk set the stage well in general terms, and then spent the second half of the talk covering the main ingredients of the proof of this theorem. Also, the talk concluded with general laughter at what was probably the largest number the audience had ever seen written on a blackboard.
For mathematicians, a knot is an embedding of the unit circle S1 into three-dimensional Euclidean space ℝ3. Of course, two different embeddings may really be “the same knot”, and the precise notion of “sameness” is called ambient isotopy, which roughly corresponds to rearranging this loop in ℝ3 without ever passing one part of the loop through another, nor cutting it and re-connecting the resulting free ends. The unknot U is the trivial knot, which is not knotted at all, and could for instance be written as the unit circle in the (or indeed any) plane in ℝ3, e.g.
Knots are often studied using their diagrams, i.e. projections of the knot onto two-dimensional planes (like sheets of paper and blackboards). For most knots, a diagram will have over- and under-crossings; subject to a mild perturbation, you can alter the knot by ambient isotopy just enough to ensure that there will be no triple crossings, and so the diagram unambiguously represents a knot. For example, here is a diagram (taken from Wikimedia Commons) of the trefoil knot, the simplest non-trivial knot:
It’s a highly non-trivial but useful fact that deforming the knot by an ambient isotopy corresponds to deforming a diagram of the knot using three elementary operations called Reidemeister moves (pictures taken from Wikimedia Commons):
Reidemeister Move #1
Reidemeister Move #2
Reidemeister Move #3
An obvious question to ask is this: given two knot diagrams D1 and D2, how many Reidemeister moves will it take to determine whether or not D1 and D2 represent the same knot K? Even more simply, given a diagram D of the unknot, how many Reidemeister moves will it take to transform it into the trivial diagram with no crossings at all? This question may be easy to ask, but it is surprisingly hard to answer. These kinds of questions are of interest because of the following fundamental equivalence: an upper bound on the number of Reidemeister moves required to trivialize a diagram of the unknot is equivalent to a computable algorithm for detecting whether a knot diagram represents the unknot.
A first complication is that it is not true that reducing a diagram of the unknot to the trivial diagram can always be done just by “simplifying” the diagram. For example, there is a famous diagram of the unknot given by Goeritz which can be trivialized using Reidemeister moves, but doing so involves temporarily increasing the number of crossings in the diagram. In particular, this implies that there are n-crossing diagrams for the unknot that take more than n Reidemeister moves to trivialize. How bad can this situation get? One answer, a lower bound, is given by the following theorem:
Theorem 2 (Hass & Nowik, 2010). There exist diagrams of the unknot with n crossings that require n2 / 25 Reidemeister moves to trivialize.
In the other direction, there is the following upper bound:
Theorem 3 (Hass & Lagarias, 2001). Every diagram of the unknot with n crossings can be trivialized using at most 21011n Reidemeister moves.
The gap between n2 / 25 and 21011n is huge, and no-one wants to have to use exponentially many Reidermeister moves to do anything! Compared to this, Lackenby’s upper bound of (231 n)11 is a huge improvement, even though there is a substantial gap between n2 / 25 and (231 n)11.
To be honest, I couldn’t follow the technical details of the talk, but one supporting result that seemed to be key in Lackenby’s proof was this result, which states that certain “nice” diagrams of the unknot can be trivialized without increasing the crossing number more than quadratically:
Theorem 4 (Dynnikov, 2004). Suppose that D is a rectangular diagram of the unknot, i.e. the arcs are all horizontal and vertical straight lines and the vertical arc is always the over-arc at any crossing. Suppose also that D has n crossings. Then D can be trivialized using Reidemeister moves without increasing increasing the number of crossings beyond C n2, for some absolute constant C > 0
The funny part of the talk came right at the end, when someone in the audience asked Lackenby how one would extend the above results to the problem of converting one diagram of a knot into another. Lackenby’s answer contained a truly huge upper bound (which he and his collaborators are working to improve). Suppose that D1 and D2 are diagrams of a knot K with n1 and n2 crossings respectively. Then there is a sequence of Reidemeister moves taking D1 to D2 in at most
moves, where n = n1 + n2 and the tower is (101000000)n entries tall! Now that is a BIG number!