# Is it possible to reliably generate a particular approximation of an ideal knot via a simulated annealing approach?

Say I take a cord, tie a loose knot in three-dimensional space, and pull tightly on the ends to generate an approximation of an ideal knot. If the cord has a fixed knot topology and a random initial configuration in space, are there any conditions under which I am guaranteed to generate a particular ideal knot approximation? In other words, if I perform something akin to simulated annealing to approximate the ideal knot, is it possible for me to always arrive at the same final state (whatever that may be) within some small error?

[Sept. 29th, 2011] - Are there any conditions/constraints under which I might be able to reliably achieve some local (or global) minima in the energy landscape of a knot?

-
What is an "ideal knot"? –  Igor Rivin Sep 27 '11 at 19:41
@Igor Rivin, an ideal knot is a representation of a knot consisting of the shortest possible length of a frictionless cord of some thickness 'R'. One might attempt to approximate this by pulling on the ends of a knotted cord. –  UltraBlue06 Sep 27 '11 at 20:00
One of the main motivations for looking at some knot energies is the hope that a gradient flow will move a generic realization of a knot to a unique global minimum. torus.math.uiuc.edu/jms/Videos/ke This appears to work often in practice, but AFAIK it has not been proven. I am quite skeptical that "pulling tightly on the ends" will straighten out a complicated presentation of a knot, or even for the unknot, since that seems to be an ineffective method in practice. –  Douglas Zare Sep 27 '11 at 21:06
I don't have a proof of this but from talking with Sullivan and Kusner, my impression is that the "rope length" functional on knot spaces has many very distinct local minima. So "the ideal knot" generally does not exist. There are just many ropelength minimizers. For example, for the $(p,q)$-torus knot in R^3, the space of all knots isotopic to it (i.e. embeddings of $S^1$ in $\mathbb R^3$ modulo parametrization) has the homotopy-type of a double mapping cylinder $SO_3 / \mathbb Z_p \leftarrow SO_3 \to SO_3 / \mathbb Z_q$. The $SO_3 / \mathbb Z_p$ and $SO_3 / \mathbb Z_q$ appear to be ... –  Ryan Budney Sep 27 '11 at 21:44
Just stumbled upon this, but Patrick D. Bangert's PhD thesis bit.ly/qmEkCN [PDF] deals with just this problem. He states the minimal word problem for braids, finds an NP-complete algorithm to solve the minimal word problem, then simulates braids as elastic strings and has them relax to heuristically "solve" the minimal word problem. Running his simulation at a non-zero "temperature" would be equivalent to using simulated annealing. –  Kelly Davis Sep 29 '11 at 15:04

I suspect what you are seeking is not known. One of the experts in this area is Jason Cantarella, who coauthored (with R. Kusner and J. Sullivan) one of the definitive papers on this topic, "On the minimum ropelength of knots and links," Inventiones Mathematicae, Volume 150, Number 2, 257-286, 2002; Springer link). Jason has developed software that he calls RidgeRunner which implements a rope-length minimization, knot-tightening procedure. (I cannot speak to the details of his software, in particular, I don't know if it is "akin to simulated annealing.") He maintains a wonderful web page with (Quicktime) movies of his minimizer approaching what you call the "ideal knot" for many (more than 100!) knots and links. Here, for example, is the endpoint of his optimizer for $8_5$:

Update. See the just-released paper, "The Shapes of Tight Composite Knots," arXiv:1110.3262 (math.DG), by Jason Cantarella and Al LaPointe and Eric Rawdon, for a description of the RidgeRunner software mentioned above. It "proceeds by constrained gradient descent," and "is designed to stop at local minima of the ropelength function." They reduce the probability of "false local minima" with several strategies. Their dataset now contains almost 1000 knots and links.

-
Does your exclamation point mean (a) more than 100 (excitement) or (b) more than 100 factorial? –  MTS Sep 29 '11 at 21:50
@MTS: Ha! Only on MO could an excitement "bang" be misinterpreted as factorial! :-) –  Joseph O'Rourke Sep 29 '11 at 23:15

The only conditions that I know of under which it's absolutely known that gradient flow will converge to a minimum energy state is when the initial configuration is planar. Zheng-Xu He proved this for his renormalized $1/r^2$ potential 'Mobius' energy in The Euler-Lagrange equation and heat flow for the Möbius energy (CPAM 53, 2000). We proved a similar theorem for 'repulsive' energies on planar polygons in An energy-driven approach to linkage unfolding (SOCG 2004).

For a nonplanar configuration, you're right to think that there's a general theorem that simulated annealing has a positive probability of converging to the global minimum" which applies to these problems, but it's ineffective in practice. The configuration space is in practice very high dimensional (3 x number of vertices) and reducing an energy functional such as ropelength generally requires a coordinated global motion of these vertices, so it's quite rare to generate such a move randomly. AFAIK, nobody knows how to estimate the probability of convergence under these circumstances, so there's no hard information on how long to run an annealer.

FWIW, RidgeRunner really isn't an annealer: it generates 'coordinated motions' for tightening deterministically using a linear algebra algorithm to deflect the gradient of length for a polygon into a ropelength-decreasing direction using the active distance and curvature constraints. The algorithm is described in Knot Tightening By Constrained Gradient Descent (Experimental Math, 2011).

You're welcome to play with RidgeRunner yourself if you'd like to try tightening: the software can be downloaded at link text.

-