Random Reidemeister moves to unknot - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T07:28:26Z http://mathoverflow.net/feeds/question/77570 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77570/random-reidemeister-moves-to-unknot Random Reidemeister moves to unknot Joseph O'Rourke 2011-10-09T00:54:19Z 2011-10-24T23:00:16Z <p>Suppose one has a link diagram of the unknot, and applies random Reidemeister moves until the unknot is reached. Surely it requires an exponential number of moves, exponential in, say, the crossing number of the original diagram? The 2001 Hass-Lagarias paper, "<a href="http://www.ams.org/journals/jams/2001-14-02/S0894-0347-01-00358-7/" rel="nofollow">The number of Reidemeister moves needed for unknotting</a>," established an exponential upper bound on the number of moves needed, but I am not finding a result on the expected number of <em>random</em> moves needed. I would like affirmation that not only is it hard, but one would not easily stumble into a solution, because then it would not truly be hard! (This in the spirit of Gower's much more substantive MO question, "<a href="http://mathoverflow.net/questions/53471/" rel="nofollow">Are there any very hard unknots?</a>")</p> <p>A reference would be appreciated! Thanks!</p> <p><em>Edit</em>: Apologies for the flawed question (thanks to Ryan Budney for clarifying it). I had in mind the expected number of random moves to reach the unknot from a random (in some sense!) diagram of the unknot.</p> <p><b>Answered.</b> The question has been answered in the comments by Theo Johnson-Freyd and Ori Gurel-Gurevich: the expected number of moves is $\infty$! As Ori put it,</p> <blockquote> <p>for any starting diagram of the unknot, there is a positive probability of never unknotting it.</p> </blockquote> http://mathoverflow.net/questions/77570/random-reidemeister-moves-to-unknot/77595#77595 Answer by Joseph O'Rourke for Random Reidemeister moves to unknot Joseph O'Rourke 2011-10-09T12:45:46Z 2011-10-09T12:45:46Z <p>I found an answer of sorts in the paper, "Mean unknotting times of random knots and embeddings," by Yao-ban Chan, Aleksander L Owczarek, Andrew Rechnitzer, and Gordon Slade (<a href="http://iopscience.iop.org/1742-5468/2007/05/P05004" rel="nofollow"><em>Journal of Statistical Mechanics: Theory and Experiment</em>, Volume 2007, May 2007</a>.) Here is the beginning of their Abstract:</p> <blockquote> <p>We study mean unknotting times of knots and knot embeddings by crossing reversals, in a problem motivated by DNA entanglement. Using self-avoiding polygons (SAPs) and self-avoiding polygon trails (SAPTs) we prove that the mean unknotting time grows exponentially in the length of the SAPT and at least exponentially with the length of the SAP.</p> </blockquote> <p>Their SAPs are on a 3D lattice; their SAPTs are on a 2D lattice; see below. Interesting that they did not establish an upper bound for SAPs. <br /> <img src="http://cs.smith.edu/~orourke/MathOverflow/SAPT.jpg" alt="SAPT"></p> http://mathoverflow.net/questions/77570/random-reidemeister-moves-to-unknot/79035#79035 Answer by Joseph O'Rourke for Random Reidemeister moves to unknot Joseph O'Rourke 2011-10-24T23:00:16Z 2011-10-24T23:00:16Z <p>This question has been fully answered (the expected number of moves is $\infty$), as detailed in an addendum to the question. I place this community-wiki "answer" here so I can accept it (It let me!) and so (hopefully!) prevent the MO software-bot from re-asking the question.</p>