It is an intriguing fact that the 3-dimensional world in which we live is, from a mathematical point of view, rather special. Dimension 3 is very different from dimension 4 and these both have very different theories from that of dimensions 5 and above. The study of space in dimensions 2, 3 and 4 is the field of low-dimensional topology, the research area of Oxford Mathematician Marc Lackenby.

One of the reasons that 3-dimensional space is different from the others is the presence of knots. A knot is just a piece of string that is usually closed up to form a loop (mathematically, it is a smoothly embedded simple closed curve). It is a familiar everyday fact that there are many different knots, the simplest two being the unknot and the trefoil shown below. However, if you put a knotted piece of string into 4-dimensional space, you can always unknot it.

The existence of non-trivial knots is a key feature of 3-dimensional space, and so it is a worthwhile goal to attempt to classify knots. One is immediately led to the following simple questions: given two knot diagrams, how can we decide whether they are the same knot? In fact, how can we even decide whether a knot diagram represents the unknot? These questions are simple to state, but actually are very difficult to answer. What is needed is an algorithm that can definitively resolve such questions in finite time. It is known that similar problems in high dimensions are unsolvable, but the situation in dimension 3 is tractable, just.

It is an old theorem (dating back to the 1920s) that any two diagrams of a knot differ by a sequence of Reidemeister moves, which are local modifications to a diagram, shown below:

This has the following algorithmic consequence: if two diagrams represent the same knot, then it will always be possible to prove this, as follows. Apply all possible Reidemeister moves to one of the diagrams. Then apply all possible Reidemeister moves to each of the resulting collection of diagrams, and so on. If the two knots are the same, this procedure will eventually reach the second diagram and so you will have proved that the two knots are equivalent. But if the knots are different, this process will not terminate. So, to turn this into an effective algorithm to decide whether two knots are the same, one needs to be given, in advance, an upper bound on the number of Reidemeister moves required to relate two diagrams of a knot. The search for such a bound is what Marc Lackenby has been working on recently. He has shown that for any diagram of the unknot with c crossings, there is a sequence of at most (236 c)11(236 c)11 moves that takes it to the diagram with no crossings. The bound (236 c)11(236 c)11 may seem large, but it is actually much smaller than what was known previously, which was an exponential function of c. The existence of such a polynomial bound had been a well-known longstanding problem. To prove this theorem, Marc had to use a wide variety of different techniques from across low-dimensional topology. His paper was recently published in the Annals of Mathematics.

This polynomial bound is not the end of the story. The procedure for deciding whether a knot is the unknot using Reidemeister moves is simple but not particularly efficient. Even with the polynomial bound on the number of moves, the running time of the algorithm is an exponential function of the initial crossing number c. Can one do better than this? No-one knows, but Marc is currently working on this problem, and hopes to find an algorithm that runs in sub-exponential time.