17
$\begingroup$
Question: Given a `hard' diagram of a knot, with over a hundred crossings, what is the best algorithm and software tool to simplify it? Will it also simplify virtual knot diagrams, tangle diagrams, and link diagrams?

The reason that I ask this question is that I have been reading:

Lewin, D., Gan O., Bruckstein A.M.,
TRIVIAL OR KNOT: A SOFTWARE TOOL AND ALGORITHMS FOR KNOT SIMPLIFICATION,
CIS Report No 9605, Technion, IIT, Haifa, 1996.

This technical report is notable not only for its mathematical content, but also for its back-story. It was the undergraduate research project of Daniel M. Lewin, who was a few years later to found Akamai Technology which today manages 15-20% of the world's web traffic, to become a billionaire, and to be the first person to be murdered on 9-11. He is the subject of the 2013 biography No Better Time: The Brief, Remarkable Life of Danny Lewin, the Genius Who Transformed the Internet by Molly Knight Raskin, published by Da Capo Press.

The algorithm used by Bruckstein, Lewin, and Gan doesn't use 3-dimensional topology or normal surface theory, but instead relies on an algorithmic technique called simulated annealing. I suspect that this same technique could be used effectively for other problems in algorithmic topology.

To the best of my knowledge, Bruckstein, Lewin, and Gan's algorithm is unknown to the low-dimensional topology community, but it works very well. Despite it having been written a long time ago, I wonder (for reasons beyond mere curiousity) how far it is from being state of the art today.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ When I was a grad student (maybe a bit before that report appeared), John Sullivan demonstrated a program that approximated a gradient flow of the Mobius energy. In practice, it seemed to work well unknotting the unknot, or getting stuck on a local minimum for knots. Here's a link to the video he made (I converted it to .mp4): dl.dropboxusercontent.com/u/8592391/KnotEnergies.mp4 $\endgroup$
    – Ian Agol
    Commented Oct 7, 2013 at 1:46
  • 4
    $\begingroup$ Does inviting Bob Gompf to visit count as an algorithm? $\endgroup$
    – Kim Morrison
    Commented Oct 8, 2013 at 22:06
  • 2
    $\begingroup$ Note that on the theoretical side, Lackenby has shown that one may untie an unknot with a polynomial number of Reidemeister moves (or grid diagram moves in Dynnikov's algorithm). This gives another proof that unknotting is in NP; however, the algorithm does not indicate how to find the moves to untie. ams.org/mathscinet-getitem?mr=3418524 see also ams.org/mathscinet-getitem?mr=3548477 $\endgroup$
    – Ian Agol
    Commented Apr 12, 2017 at 3:36

3 Answers 3

Reset to default
7
$\begingroup$

Here is one piece of software, the Book Knot Simplifier, by Maria Andreeva, Ivan Dynnikov, Sergey Koval, Konrad Polthier, and Iskander Taimanov, largely based on Dynnikov's work:

Here we offer a set of tools for manipulating knots and links in the three-space by using the three-page presentation of links, which was proposed and developed by I. Dynnikov in [1][2][3].

The approach is based on a simple and very well known observation that every link in the three-space is topologically equivalent to a link that lies entirely in a three-page book, i.e. the union of three half-planes with common boundary. Though being not convenient for human perception, this way of presenting links seems to be very efficient for handling knots by computer. It provides a very quick way from a combinatorial description of a link to its three-dimensional presentation. A three-page link admits a lot of transformations that preserve its isotopy class and can be easily found. This fact is used in the knot simplifying tool included herein.


unknot31
        The unknot with 31 crossings.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This must be it! Thanks! I suspect (without supporting evidence) that this might work better for knots with a few dozen crossings- but I also suspect that, because the simulated annealing algorithm is entirely probabilistic, that it will work better for huge knots of a few hundred or even of a few thousand crossings; and certainly for virtual/welded objects. Random fun idea- wouldn't it be fun to have a knot simplification championship, where teams are provided with a huge knot, and compete to unknot it fastest! $\endgroup$
    – Daniel Moskovich
    Commented Oct 9, 2013 at 4:10
  • 1
    $\begingroup$ That's a great idea, Daniel! DIMACS runs software implementation challenges. For example, David Johnson ran a TSP Challenge. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 9, 2013 at 10:40
6
$\begingroup$

Ben Burton has a paper where he experimentally does Pachner moves to simplify unknot complements. It appears to be very effective. https://arxiv.org/abs/1211.1079

I'd type more but my phone is a little awkward. But you could view this as a coarse type of simulated annealing.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this! Could you explain a bit more how this method can be viewed as a variation on simulated annealing? Simulated annealing is a probabilistic method- were there any probabilistic steps in the preprint to which you linked? $\endgroup$
    – Daniel Moskovich
    Commented Oct 8, 2013 at 6:14
  • $\begingroup$ Hi Daniel, sorry I was going from memory of a conversation with Ben. I had not read that paper. The reference I meant to give is this one: arxiv.org/abs/1110.6080 It's a little orthogonal to your question since it's using Pachner moves on closed manifold triangulations rather than unknot complements, but I believe Ben did similar experiments on knot complements getting essentially the same results -- they're just not written up. But for closed manifolds this is very much an annealing type result. $\endgroup$
    – Ryan Budney
    Commented Oct 10, 2013 at 8:20
3
$\begingroup$

A little Heegaard promotion.

Those of you interested in recognizing unknots, or the 3-sphere, or who are interested in simplifying general geometric 3-manifold presentations might want to try a new version of Heegaard. (Which may eventually replace the original outdated version posted on the website of Marc Culler and Nathan Dunfield at www.math.uic.edu/t3m.)

Heegaard accepts geometric presentations on up to 26 generators and 32 relators. So for knots, Wirtinger presentations, or geometric presentations obtained using over-crossing and under-crossing arcs will work provided the 26 generator restriction is satisfied.

For example, Heegaard easily determines each of the following examples is unknotted in only a few seconds.

Thistlethwaite's Unknot from Wikipedia, Culprit from Kaufmann-Lambropoulou, Fig5 from Kaufmann-Lambropoulou, H) from Henrich & Kauffman, J) from Henrich & Kauffman, G) Goeritz's unknot, Ochiai's unknot 1 from "Non-trivial projections of the trivial knot" URL http://hdl.handlenet/2433/99940, Ochiai's unknot 2 from the same paper, and Freedman's Twisted Unknot.

While the approach Heegaard uses isn't sexy, it does seem to work quite---perhaps unreasonably---well.

Those wishing to check such things for themselves can obtain a current copy of Heegaard from me by email request to jberge at charter 'dot' net.

Note Heegaard is a Unix executable, which runs under terminal on an apple macintosh. So you will probably need a mac. Though Ryan Budney has it running under linux.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome to MathOverflow! Thank you for writing heegaard. If I could make a suggestion: would you please consider posting the source code for Heegaard (and its wonderful documentation) on a public repository such as Github, Bitbucket, SourceForge, etc? yours $\endgroup$
    – Sam Nead
    Commented Oct 26, 2013 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .