God's number

God's number is usually used in context of Rubik's cubes. It takes at most 20 moves to solve a Rubik's cube; as such, God's number for the Rubik's cube (at least, the 3×3 one) is 20.

What is God's number?

A Rubik's cube is a very specific instance of a permutation group. The "moves" are a set of base permutations, with which all states of a Rubik's cube may be reached. This is generalizable to groups in general. For any group $G$, we pick a certain number of elements $a_1, \dots a_n$. Our moves then are all powers of these moves. In terms of a Rubik's cube, we can start with turning each side once clockwise. The powers of those are then turning each side any amount of time. We do this so that, for example, a half turn on a Rubik's cube still counts as "one move". Then, we can create "layers", $C_1, C_2, \dots$, where $C_1$ is the collection of moves, and each $C_i$ contains the elements from $C_{i-1}$ and any $u$ such that there is a move $m\in C_1$ and an $x\in C_{i-1}$ with $u = x\cdot m$. In other words; $C_i$ is the set of states you can reach by doing $i$ moves. Now, the smallest $n$ with $C_n = C_{n+1}$ is what we define to be "God's number".

Note that we might not reach the entire group $G$. For a Rubik's cube, not every state is solvable; for example, swapping two corner pieces is impossible.

How do you find God's number?

That's a good question. Nobody knows, really, how to do it in the general case. It took until 2010 for mathematicians to figure out God's number for the Rubik's cube. And they didn't even really "prove" it in the traditional sense of the word, they ran simulations on many computers to show that any state is solvable in 20 moves. It's a proof, but it doesn't create understanding about the structures of groups in general or even about the Rubik's cube group specifically.

Layer sizes

Before, we defined layers $C_i$. These layers were cumulative, i.e. each $C_i$ contains the $C_{i-1}$ before it. We can therefore also define $L_i$ such that $L_0 = {1}$, $L_1 = C_1 \setminus {1}$, and $L_i = C_{i} \setminus C_{i-1}$. This way of thinking about the layers is helpful because it's a bit easier to think about what happens to their sizes. For the initial handful of layers, we know that the amount of moves more-or-less determines how many elements are in the next layer.

For example, for a Rubik's cube, there are 18 moves we can do at any given point. After having done a move, there are 15 possible moves that would not be mergeable with the previous move. So, $L_0$ just has the "solved" cube in it, i.e. $1$; the identity permutation. Then $L_1$ has 18 moves. Now, we know $L_2$ has at most $18\cdot 15$ moves. It's not exactly that, because moving the top layer first, and then the bottom layer, is the same as doing it the other way around. Those positions are counted twice, so actually $|L_2| = 243$. But this line of thinking still works, and we find in general that the sizes of the layers rack up exponentially. However, at some point we find it goes back down (since $L_{g+1} = 0$ for God's number $g$). For Rubik's cubes, we see that the ratio between the sizes of the two layers sit between $13$ and $13\tfrac12$ right up until the 16th layer (according to cube20.org).

An idea

With this in mind, we maybe don't need to compute all the layers all the way till the end. If we look at their logarithmic sizes, perhaps there is something to deduce from how the layers grow in size and the rate at which is decreases compared to that exponential curve, what God's number will be.

I'll write some code to do some testing with this. To be continued…