Knot Tightening by Constrained Gradient Descent

Abstract

We present new computations of approximately length-minimizing polygons with fixed thickness. These curves model the centerlines of “tight” knotted tubes with minimal length and fixed circular cross-section. Our curves approximately minimize the ropelength (or quotient of length and thickness) for polygons in their knot types. While previous authors have minimized ropelength for polygons using simulated annealing, the new idea in our code is to minimize length over the set of polygons of thickness at least one using a version of constrained gradient descent. We rewrite the problem in terms of minimizing the length of the polygon subject to an infinite family of differentiable constraint functions. We prove that the set of variations of a polygon of thickness one that does not decrease thickness to first order is a finitely generated polyhedral cone, and give an explicit set of generators. Using this cone, we give a first-order minimization procedure and a Karush–Kuhn–Tucker criterion for polygonal-ropelength criticality. Our main numerical contribution is a set of 379 almost-critical knots and links, including all prime knots with ten and fewer crossings and all prime links with nine and fewer crossings. For links, these are the first published ropelength figures, and for knots they improve on existing figures. We give new maps of the self-contacts of these knots and links, and discover some highly symmetric tight knots with particularly simple-looking self-contact maps.

2000 AMS Subject Classification:

• 49M25
• 49Q10
• 53A04
• 57M25

Keywords:

• ropelength
• tight knots
• ideal knots
• constrained gradient descent
• sparse nonnegative least-squares problem (snnls)
• knot-tightening

Acknowledgments

The authors would like to mention the hard work of Sivan Toledo, whose TAUCS library made tlsqr and tsnnls possible. Our code was made much faster by Toledo's carefully written supernodal multifrontal Cholesky factorization code. We are similarly indebted to Portugal, Judice, and Vicente for developing the block principal pivoting algorithm. Many colleagues provided helpful conversations and insights about these and similar problems, including Joe Fu, Rob Kusner, John Sullivan, Piotr Pierański, John Maddocks, and Andrzej Stasiak. The authors would also like to acknowledge the support of the National Science Foundation through the University of Georgia VIGRE grant (DMS-00-89927), DMS-02-04826 (to Cantarella and Fu), and DMS-08-10415 (to Rawdon).

Notes

¹Federer referred to this number as the reach of γ [Federer 59].

²Our measurement of curvature by is sensitive to edge length and seems to come out much larger than his ropelengths would indicate. This is probably a discretization effect, and it is certainly possible that the Fourier knots defined by Gilbert's data have ropelengths corresponding to Gilbert's claimed numbers.

³The notable exception to this rule has been the “biarc” spline-annealing method of [Carlen et al. 05], which has produced well-resolved contact maps for the 3₁ and 4₁ knots.

⁴We could improve the accuracy and speed of this portion of the computation by using a smarter ODE solving method. But these steps have no linear algebra involved, so they are already orders of magnitude faster than those to come. In practice, this portion of the run consumes less than one percent of the total runtime.

⁵Available at http://www.knotplot.com.

⁶The source code for roundout_rl is freely available as part of the octrope library.

⁷These animations are posted on the web at http://www.jasoncantarella.com/movs/.