God's number for the $n \times n \times n$-cube - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:18:46Z http://mathoverflow.net/feeds/question/77836 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77836/gods-number-for-the-n-times-n-times-n-cube God's number for the $n \times n \times n$-cube Martin Brandenburg 2011-10-11T16:24:39Z 2012-01-14T20:01:58Z <p>This is a question about <a href="http://en.wikipedia.org/wiki/Rubik%2527s_Cube" rel="nofollow">Rubik's Cube</a> and generalizations of this puzzle, such as <a href="http://en.wikipedia.org/wiki/Rubik%2527s_Revenge" rel="nofollow">Rubik's Revenge</a>, <a href="http://en.wikipedia.org/wiki/Professor%2527s_Cube" rel="nofollow">Professor's cube</a> or in general the $n \times n \times n$ cube.</p> <p>Let $g(n)$ be the smallest number $m$, such that every realizable arrangement of the $n \times n \times n$ cube can be solved with $m$ moves. In other words, this is the "radius" of the Cayley graph of the $n \times n \times n$ cube group with respect to the canonical generating system.</p> <p>We have $g(1)=0$, $g(2)=11$ and - quite recently - in 2010 it was proven that $g(3)=20$: <a href="http://cube20.org/" rel="nofollow">God's number is 20</a>.</p> <p><strong>Question.</strong> Is anything known about $g(4)$ or $g(5)$?</p> <p>I expect that the precise number is unkwown since the calculation for Rubik's cube already took three decades. Nevertheless, is there any work in progress? Are any lower or upper bounds known?</p> <p>I would like to ask the same question about $g(n)$ for $n>5$, or rather:</p> <p><strong>Question.</strong> Is anything known about the asymptotic value of $g(n)$?</p> http://mathoverflow.net/questions/77836/gods-number-for-the-n-times-n-times-n-cube/77841#77841 Answer by Theo Johnson-Freyd for God's number for the $n \times n \times n$-cube Theo Johnson-Freyd 2011-10-11T16:55:02Z 2011-10-11T16:55:02Z <p>I am not an expert, but I remember seeing <a href="http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html" rel="nofollow">this press release from MIT</a> not too long ago. <a href="http://arxiv.org/abs/1106.5736" rel="nofollow">The corresponding arXiv article</a> should answer your second question.</p>