Rubiks Cube function -- how many configurations reachable in n moves.

Question

I'm working on a relatively low-level math project, and for one part of it I need to find to a function that returns how many many configurations are reachable within n moves. from the solved state.

Because there are 18 moves ( using the double moves metric ), one form of the function could be $\sum_{k=1}^{i} 18^{k} $, since it would technically be the sum of all permutations reachable by the amount of moves 0,1,...,n. However, what would a more optimised function, which takes into account factors like inverses, cube symmetry, ...etc look like?

Answer 1

http://cube20.org/ shows exact counts for $n$ up to 15, but only has approximate counts above that.

This probably means no nice formula that would make those higher values easy to compute is known.

(If there were a nice exact formula, it would presumably have shown immediately that going from 20 to 21 moves reveals no new configurations, mooting the whole brute-force search for "god's number").

Answer 2

Too long for a comment, making CW

Alexander Chervov recently asked a very similar question on MO. He noted that the http://cube20.org data, mentioned by Henning, grows as $13^n$, slower than the $18^n$ bound proposed by Mychil and corresponding to a free group. He wondered why it's dissimilar from an abelian group such as $\mathbb{Z}/2\mathbb{Z}^n$, which looks like a Galton board and grows quadratically.

In his answer, Derek Holt noted that under the half-turn metric, moving the same face twice in a row does not lead to a new position, thus reducing the growth from $18$ to $15$. He developed his reasoning further to consider the presentation of another infinitude group having a subset of relations of the Rubik's Cube group. Holt's presentation was

$$\langle a_i, b_i\ (1 \le i \le 6) \mid a_i^4= 1,a_i^2=b_i\ (1 \le i\le 6), a_1a_4=a_4a_1,a_2a_5=a_5a_2,a_3a_6=a_6a_3 \rangle$$

With Singmaster notation we can have $F=a_1,\:F'=a_1^{-1},\:F^2=b_1,\:B=a_4,\vdots$

This group is infinite and automatic. It is amenable to study with the Knuth-Bendix completion algorithm, which is similar to Buchberger's algorithm.

Holt goes on to find a Taylor series expansion of the growth function for his infinite group. The coefficients begin to deviate from the cube20 data after the 4th move, which he takes to mean that the Rubik's Cube group has relators of length $8$ that cause the deviation (and may be the source of the finiteness of the Rubik's Cube group), although he was unable to find the relation.

I didn't know anything about the Knuth-Bendix completion algorithm prior to Holt's answer. As I envision it, Holt has managed to find the above infinite group with only a small number of relations, and show that it is in a certain sense "tangential" to the finite Rubik's Cube group.