[math-fun] tightening knots
I've posted before about knots are really machines and should be analysed as such. This idea turns out not to be new. Here is a paper http://arxiv.org/abs/1002.1723 with computer simulations of knots trying to find the "tightest" form of each knot type. You can see movies of the tightening process for many knots & links here: http://www.jasoncantarella.com/movs/ Many questions suggest themselves... -- Warren D. Smith http://RangeVoting.org
beautiful movies! I have heard that making the units of string repel each other, while keeping the arc length constant, seems to be a good heuristic for unknotting unknots. However, since telling whether a knot is an unknot or not is believed to be computationally hard (even showing it's in NP is pretty challenging) such a heuristic shouldn't work in all cases --- there should exist knots where it gets stuck. A similar issue arises in numerical general relativity: it shouldn't be easy to tell whether two 4-manifolds are equivalent (it's undecidable because of the word problem!) but there are no known examples where numerical algorithms that try to tell whether a 4-manifold is just a sphere get stuck for a long time. Does anyone know of references on either of these? Cris On Dec 30, 2013, at 1:58 PM, Warren D Smith <warren.wds@gmail.com> wrote:
I've posted before about knots are really machines and should be analysed as such. This idea turns out not to be new. Here is a paper
http://arxiv.org/abs/1002.1723
with computer simulations of knots trying to find the "tightest" form of each knot type. You can see movies of the tightening process for many knots & links here:
http://www.jasoncantarella.com/movs/
Many questions suggest themselves...
-- Warren D. Smith http://RangeVoting.org
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
My understanding was just the opposite -- I've heard knot theorists say that they've never seen an unknot which was not 'obvious', and thus they expected the problem to be easy even though no good general methods are at hand. I have relatively little understanding of the field, personally, so I have no opinion of my own. Charles Greathouse Analyst/Programmer Case Western Reserve University On Mon, Dec 30, 2013 at 6:15 PM, Cris Moore <moore@santafe.edu> wrote:
beautiful movies!
I have heard that making the units of string repel each other, while keeping the arc length constant, seems to be a good heuristic for unknotting unknots. However, since telling whether a knot is an unknot or not is believed to be computationally hard (even showing it's in NP is pretty challenging) such a heuristic shouldn't work in all cases --- there should exist knots where it gets stuck.
A similar issue arises in numerical general relativity: it shouldn't be easy to tell whether two 4-manifolds are equivalent (it's undecidable because of the word problem!) but there are no known examples where numerical algorithms that try to tell whether a 4-manifold is just a sphere get stuck for a long time.
Does anyone know of references on either of these?
Cris
On Dec 30, 2013, at 1:58 PM, Warren D Smith <warren.wds@gmail.com> wrote:
I've posted before about knots are really machines and should be analysed as such. This idea turns out not to be new. Here is a paper
http://arxiv.org/abs/1002.1723
with computer simulations of knots trying to find the "tightest" form of each knot type. You can see movies of the tightening process for many knots & links here:
http://www.jasoncantarella.com/movs/
Many questions suggest themselves...
-- Warren D. Smith http://RangeVoting.org
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hass, Lagarias, and Pippenger proved that Unknot (telling whether a knot can be untied to form a simple loop) is in NP. But even proving this takes a lot of topology. The main problem is that it's not known whether there is always a series of Reidemeister moves of polynomial length (as a function of the number of initial crossings) that succeeds in untying an unknot. The best known upper bound on the number of moves is exponential, due to Hass and Lagarias. In 2011 Kuperberg showed that Unknot is in NP \cap coNP, assuming the generalized Riemann hypothesis (!), and building on work of Koiran. Thus we don't believe that Unknot is NP-complete. However, no polynomial-time algorithm is known --- thus the mystery that it seems hard to find hard examples. (Perhaps all examples of reasonable size are too easy.) Cris On Dec 30, 2013, at 4:35 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
My understanding was just the opposite -- I've heard knot theorists say that they've never seen an unknot which was not 'obvious', and thus they expected the problem to be easy even though no good general methods are at hand. I have relatively little understanding of the field, personally, so I have no opinion of my own.
Charles Greathouse Analyst/Programmer Case Western Reserve University
The player spontaneously jumps back in time (Apple iMac / OS10.9.1 / Safari). Anyone else have this problem? I'd email him, if I could decipher his address! WFL On 12/30/13, Cris Moore <moore@santafe.edu> wrote:
Hass, Lagarias, and Pippenger proved that Unknot (telling whether a knot can be untied to form a simple loop) is in NP. But even proving this takes a lot of topology. The main problem is that it's not known whether there is always a series of Reidemeister moves of polynomial length (as a function of the number of initial crossings) that succeeds in untying an unknot. The best known upper bound on the number of moves is exponential, due to Hass and Lagarias.
In 2011 Kuperberg showed that Unknot is in NP \cap coNP, assuming the generalized Riemann hypothesis (!), and building on work of Koiran. Thus we don't believe that Unknot is NP-complete. However, no polynomial-time algorithm is known --- thus the mystery that it seems hard to find hard examples. (Perhaps all examples of reasonable size are too easy.)
Cris
On Dec 30, 2013, at 4:35 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
My understanding was just the opposite -- I've heard knot theorists say that they've never seen an unknot which was not 'obvious', and thus they expected the problem to be easy even though no good general methods are at hand. I have relatively little understanding of the field, personally, so I have no opinion of my own.
Charles Greathouse Analyst/Programmer Case Western Reserve University
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The spookiest untangling algorithm I've seen is to flow along the downhill gradient of a 1/r^2 repulsive potential (between all pairs of line elements). This energy is scale invariant, but less obviously, Moebius invariant. John Sullivan showed me movies of some very complex tangles transforming effortlessly into a nice round unknot. Last time I spoke with him no one had found an example of a non-trivial critical point of this energy, i.e. a mechanism for the algorithm to get stuck. The motion is global in character, with tightly tangled regions spontaneously expanding and then unraveling. -Veit On Dec 30, 2013, at 6:15 PM, Cris Moore <moore@santafe.edu> wrote:
beautiful movies!
I have heard that making the units of string repel each other, while keeping the arc length constant, seems to be a good heuristic for unknotting unknots. However, since telling whether a knot is an unknot or not is believed to be computationally hard (even showing it's in NP is pretty challenging) such a heuristic shouldn't work in all cases --- there should exist knots where it gets stuck.
A similar issue arises in numerical general relativity: it shouldn't be easy to tell whether two 4-manifolds are equivalent (it's undecidable because of the word problem!) but there are no known examples where numerical algorithms that try to tell whether a 4-manifold is just a sphere get stuck for a long time.
Does anyone know of references on either of these?
Cris
I'd love to see these movies. I'll ask John if they're available over the web. Jim Propp On Tuesday, December 31, 2013, Veit Elser wrote:
The spookiest untangling algorithm I've seen is to flow along the downhill gradient of a 1/r^2 repulsive potential (between all pairs of line elements). This energy is scale invariant, but less obviously, Moebius invariant. John Sullivan showed me movies of some very complex tangles transforming effortlessly into a nice round unknot. Last time I spoke with him no one had found an example of a non-trivial critical point of this energy, i.e. a mechanism for the algorithm to get stuck. The motion is global in character, with tightly tangled regions spontaneously expanding and then unraveling.
-Veit
On Dec 30, 2013, at 6:15 PM, Cris Moore <moore@santafe.edu <javascript:;>> wrote:
beautiful movies!
I have heard that making the units of string repel each other, while keeping the arc length constant, seems to be a good heuristic for unknotting unknots. However, since telling whether a knot is an unknot or not is believed to be computationally hard (even showing it's in NP is pretty challenging) such a heuristic shouldn't work in all cases --- there should exist knots where it gets stuck.
A similar issue arises in numerical general relativity: it shouldn't be easy to tell whether two 4-manifolds are equivalent (it's undecidable because of the word problem!) but there are no known examples where numerical algorithms that try to tell whether a 4-manifold is just a sphere get stuck for a long time.
Does anyone know of references on either of these?
Cris
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right. The energy that I think Sullivan -- and most researchers who talk of Möbius-invariant energy -- work with this one usually attributed to Mike Freedman: It's (by slight abuse of notation), for a smoothly embedded knot K, this double integral over the cartesian square of the knot: E(K) := Int Int over KxK of (1/|x-y|^2 - 1/(d(x,y)^2) dx dy where |x-y| is the distance through Euclidean space, d(x,y) is the distance along the knot, dx, dy elements of arclength along the knot. (The abuse is just that the pieces of the integrand go to infinity at the diagonal x = y. But fortunately, if you avoid integrating over an epsilon-neighborhood of the diagonal, the integral converges as epsilon approaches 0.) The belief that sliding down the gradient of E(K) will never get stuck was already believed by at least 1995. --Dan On 2013-12-31, at 7:05 AM, Veit Elser wrote:
The spookiest untangling algorithm I've seen is to flow along the downhill gradient of a 1/r^2 repulsive potential (between all pairs of line elements). This energy is scale invariant, but less obviously, Moebius invariant. John Sullivan showed me movies of some very complex tangles transforming effortlessly into a nice round unknot. Last time I spoke with him no one had found an example of a non-trivial critical point of this energy, i.e. a mechanism for the algorithm to get stuck. The motion is global in character, with tightly tangled regions spontaneously expanding and then unraveling.
Correction: Veit informs me that it was Jun O'Hara who first invented this energy, and Freedman who first noticed that it is Möbius-invariant.* ----------- --Dan _____________________________ * In a paper with He and Wang P.S. Just to be clear, Möbius-invariant here means conformally-invariant: Let f: S^3 -> S^3 be any angle-preserving transformation. All of them form the conformal (or Möbius) group of S^3. By stereographic projection S: S^n - {*} -> R^n, where * = (0,0,0,1), (with inverse Sinv), f -- or more precisely S o f o Sinv -- is *almost* a homeomorphism of R^n. Since S preserves angles on S^3, so does S o f o Sinv on R^3, where it is defined. So for a knot K in R^n, as long as f(Sinv(K)) does not contain *, we can apply S to it to get K' := S(f(Sinv(K)), another knot in R^3. The statement of conformal or Möbius invariance of E(K) means that for any such new knot, we have E(K') = E(K). The conformal transformations "of R^3 to itself" are generated by translations, rotations, uniform scaling, and inversion in a sphere. (But the last one in undefined at the center of the sphere, taking that point to "infinity".) I wrote:
The energy that I think Sullivan -- and most researchers who talk of Möbius-invariant energy -- work with this one usually attributed to Mike Freedman: It's (by slight abuse of notation), for a smoothly embedded knot K, this double integral over the cartesian square of the knot:
E(K) := Int Int over KxK of (1/|x-y|^2 - 1/(d(x,y)^2) dx dy
participants (7)
-
Charles Greathouse -
Cris Moore -
Dan Asimov -
Fred Lunnon -
James Propp -
Veit Elser -
Warren D Smith