## God’s number for the $n \times n \times n$-cube

This is a question about Rubik's Cube and generalizations of this puzzle, such as Rubik's Revenge, Professor's cube or in general the $n \times n \times n$ cube.

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.

We have $g(1)=0$, $g(2)=11$ and - quite recently - in 2010 it was proven that $g(3)=20$: God's number is 20.

Question. Is anything known about $g(4)$ or $g(5)$?

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?

I would like to ask the same question about $g(n)$ for $n>5$, or rather:

Question. Is anything known about the asymptotic value of $g(n)$?

-
Perhaps it should be mentioned that this result is for the half-turn metric. In light of the comments at matthewkahle.wordpress.com/tag/gods-number, it appears that the situation for the quarter-turn metric will prove to be more elegant mathematically, where the answer is expected to be 26 with a unique position requiring 26 moves to solve. (Also, why restrict to three dimensions? Let's ask for the asymptotics for God's number for the n^k cube). – Peter McNamara Oct 11 2011 at 20:19
Thanks Peter; I didn't know that 20 refers to the half-turn metric. And now I'm rather disappointed that the number for the quater-turn metric (which seems much more natural to me) is still unknown! – Martin Brandenburg Oct 12 2011 at 12:29

Just to make the answer to Q2 explicit: $g(n)= \Theta(n^2 / \log n)$. – Joseph O'Rourke Oct 11 2011 at 17:36