Unravelling knots just got easier. One of the biggest problems in the mathematical study of knots is recognising the difference between an actual knot and a piece of string that can be untangled into a single loop. A new algorithm can find this “unknot” far faster than any previous one can, which could come in handy for studying the tangles of DNA or the fluid dynamics of stars.
Mathematically, the definition of a knot is a closed curve – like a piece of string with the ends tied together – that cannot be untangled into a simple loop. Anything that can be untangled into a simple loop, no matter how complicated or tangled it appears at first glance, is called the unknot. “Just like zero isn’t a number, the unknot isn’t a knot,” says Mark Dennis at the University of Birmingham in the UK.
Mathematicians have been working on finding an algorithm to tell whether a given knot is actually the unknot for about 100 years – pioneering mathematician and computer scientist Alan Turing even wrote about it in his final published paper in 1954. Now, Marc Lackenby at the University of Oxford that can make this distinction far faster than any other.
Advertisement
“Although finding the unknot seems quite intuitive because throughout our lives we are untangling wires and pieces of string and headphone cords and things, it turns out that mathematically it touches on much more abstract areas of maths, questions to do with geometry in higher-dimensional spaces,” says Dennis. “There are knot diagrams that you need to make more complicated before you can simplify them down,” he says, and computers aren’t great at recognising when to do so.
The level of complexity of a given knot is defined by the number of crossings it contains. A crossing is the spot at which one part of the string passes over or under another part, and any tangle that can be manipulated so that it has no crossings is the unknot.
“You might expect it not to be a difficult problem, and the issue is that when you start to think about how a computer would actually decide such a question you realise that you don’t have the right tools to even come to a decisive answer about whether a thing is or isn’t knotted,” says Lackenby.
Other mathematicians have come up with algorithms that can find whether a given tangle is knotted or not, but every added crossing doubles the time needed to figure out if a tangle is the unknot.
Lackenby has come up with the first algorithm that can figure it out faster than that. His work relies on defining each knot as representing the edge of a three-dimensional shape.
“You can imagine a round unknot just lying in the plane, well that’s the boundary of a disc,” Lackenby says. “Or you can imagine taking a strip of paper and gluing it together in a loop with some little twists in it, and the boundary of that strip of paper will be a knot.”
If the shape corresponding to a knot can be manipulated and simplified into a disc, that knot is actually the unknot. Determining whether a knot is the unknot has far-ranging applications, from studying how DNA is tangled up within cells to understanding the loops of plasma that make up stars, so a faster algorithm could be enormously helpful.
Sign up to Lost in Space-Time, a free monthly newsletter on the weirdness of reality
