God’s Number: The Math Behind the Rubik’s Cube
(generated with NotebookLM)Some math before we begin
Sets
A set is a collection of distinct objects. We list elements inside curly braces.
$$S = {1, 2, 3, 4, 5, 6}$$
The set $S$ has 6 elements. We write $|S| = 6$ and call this the cardinality of $S$. Two sets are equal if they contain exactly the same elements: ${1, 2, 3} = {3, 1, 2}$.
Functions and mappings
A function $f: A \to B$ is a rule that assigns to every element of the set $A$ exactly one element in the set $B$. We call $A$ the domain and $B$ the codomain.
$$f: {1, 2, 3} \to {a, b, c}, \quad f(1) = a,\ f(2) = b,\ f(3) = c$$
A function is injective (one-to-one) if distinct inputs map to distinct outputs: $f(x) = f(y)$ implies $x = y$. It is surjective (onto) if every element of $B$ is hit by at least one input. A function that is both injective and surjective is a bijection. Bijections are perfectly reversible: if $f$ is a bijection, there exists an inverse function $f^{-1}: B \to A$ such that $f^{-1}(f(x)) = x$ for all $x \in A$.
Permutations
A permutation of a set $S$ is a bijection $\sigma: S \to S$, a rearrangement of $S$ onto itself. For $S = {1, 2, 3}$, here is one permutation written in two-row notation:
$$ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$
This means $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 1$. In cycle notation: $\sigma = (1\ 2\ 3)$, meaning $1 \mapsto 2 \mapsto 3 \mapsto 1$. An element that maps to itself is a fixed point and is omitted from the cycle notation.
Here is another permutation of ${1, 2, 3, 4}$:
$$\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 2 & 3 \end{pmatrix} = (2\ 4\ 3)$$
Element 1 is a fixed point. Elements 2, 4, 3 cycle among themselves.
The set of all permutations of an $n$-element set is called $S_n$, the symmetric group on $n$ elements. It has exactly $n!$ elements.
$$|S_n| = n!$$
So $|S_3| = 6$, $|S_4| = 24$, and $|S_{48}| = 48!$, a truly enormous number.
Composition
If $\sigma$ and $\tau$ are two permutations of the same set, their composition $\tau \circ \sigma$ means: first apply $\sigma$, then apply $\tau$. Let us compute an example with $\sigma = (1\ 2\ 3)$ and $\tau = (1\ 2)$ on the set ${1, 2, 3}$:
$$(\tau \circ \sigma)(1) = \tau(\sigma(1)) = \tau(2) = 1$$ $$(\tau \circ \sigma)(2) = \tau(\sigma(2)) = \tau(3) = 3$$ $$(\tau \circ \sigma)(3) = \tau(\sigma(3)) = \tau(1) = 2$$
So $\tau \circ \sigma = (2\ 3)$. Now try the other order:
$$(\sigma \circ \tau)(1) = \sigma(\tau(1)) = \sigma(2) = 3$$ $$(\sigma \circ \tau)(2) = \sigma(\tau(2)) = \sigma(1) = 2$$ $$(\sigma \circ \tau)(3) = \sigma(\tau(3)) = \sigma(3) = 1$$
So $\sigma \circ \tau = (1\ 3)$. Since $(2\ 3) \neq (1\ 3)$, we see that $\tau \circ \sigma \neq \sigma \circ \tau$. Order matters. This non-commutativity is a central feature of the Rubik’s Cube.
What is a Group?
A group is one of the most elegant ideas in all of mathematics. It captures the abstract essence of symmetry and reversibility, stripping away everything except the bare minimum structure needed for the concept to hold together.
Formally, a group $(G, \cdot)$ is a set $G$ together with a binary operation $\cdot$ satisfying four axioms:
| Axiom | Formal Statement | Plain Meaning |
|---|---|---|
| Closure | $\forall, a, b \in G:\ a \cdot b \in G$ | Combining two elements stays inside $G$ |
| Associativity | $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ | Grouping of operations does not matter |
| Identity | $\exists, e \in G:\ e \cdot a = a \cdot e = a$ | There is a “do nothing” element |
| Inverses | $\forall, a \in G,\ \exists, a^{-1} \in G:\ a \cdot a^{-1} = e$ | Every action can be undone |
If additionally $a \cdot b = b \cdot a$ for all $a, b \in G$, the group is called abelian (after the Norwegian mathematician Niels Abel). Most groups we encounter in everyday arithmetic are abelian. The interesting and hard cases, including the Rubik’s Cube, are not.
Example 1: Integers under Addition
$(\mathbb{Z}, +)$ is a group.
- Closure: $3 + 5 = 8 \in \mathbb{Z}$. The sum of two integers is an integer.
- Associativity: $(3 + 4) + 5 = 3 + (4 + 5) = 12$.
- Identity: $0$. We have $n + 0 = 0 + n = n$ for all $n$.
- Inverses: The inverse of $n$ is $-n$. We have $n + (-n) = 0$.
- Abelian: $3 + 5 = 5 + 3$. Yes.
This group is infinite and abelian.
Example 2: Integers mod $n$
Fix a positive integer $n$. Define $\mathbb{Z}/n\mathbb{Z} = {0, 1, 2, \ldots, n-1}$ with addition modulo $n$. For $n = 5$:
$$3 + 4 \equiv 2 \pmod{5}$$
This is a finite abelian group of order $n$. The identity is $0$. The inverse of $k$ is $n - k$. For example, in $\mathbb{Z}/5\mathbb{Z}$, the inverse of $3$ is $2$, since $3 + 2 = 5 \equiv 0$.
Example 3: Nonzero Rationals under Multiplication
$(\mathbb{Q}^*, \times)$ is an abelian group. The identity is $1$. The inverse of $q$ is $\frac{1}{q}$, which exists since $q \neq 0$.
Example 4: Symmetries of an Equilateral Triangle
Take an equilateral triangle and label its vertices $1, 2, 3$.
1
/ \
/ \
2-----3
A symmetry is any rigid motion that maps the triangle back onto itself. There are exactly 6:
- $e$: identity, do nothing
- $r$: rotate $120°$ counterclockwise: $(1\ 2\ 3)$
- $r^2$: rotate $240°$ counterclockwise: $(1\ 3\ 2)$
- $s_1$: reflect through the axis from vertex $1$ to the midpoint of side $23$: $(2\ 3)$
- $s_2$: reflect through the axis from vertex $2$ to the midpoint of side $13$: $(1\ 3)$
- $s_3$: reflect through the axis from vertex $3$ to the midpoint of side $12$: $(1\ 2)$
This set under composition is the dihedral group $D_3$, of order 6. Let us verify it is non-abelian by computing $r \circ s_1$ and $s_1 \circ r$ explicitly:
$$r \circ s_1: \quad 1 \xrightarrow{s_1} 1 \xrightarrow{r} 2, \quad 2 \xrightarrow{s_1} 3 \xrightarrow{r} 1, \quad 3 \xrightarrow{s_1} 2 \xrightarrow{r} 3 \quad \Rightarrow \quad r \circ s_1 = (1\ 2) = s_3$$
$$s_1 \circ r: \quad 1 \xrightarrow{r} 2 \xrightarrow{s_1} 3, \quad 2 \xrightarrow{r} 3 \xrightarrow{s_1} 2, \quad 3 \xrightarrow{r} 1 \xrightarrow{s_1} 1 \quad \Rightarrow \quad s_1 \circ r = (1\ 3) = s_2$$
Since $s_3 \neq s_2$, we confirm $r \circ s_1 \neq s_1 \circ r$. Non-abelian.
Non-Example 1: Natural Numbers under Addition
$(\mathbb{N}, +)$ where $\mathbb{N} = {1, 2, 3, \ldots}$ is not a group. There is no identity element: no $e \in \mathbb{N}$ satisfies $n + e = n$ for all $n$, since $0 \notin \mathbb{N}$. The identity axiom fails.
If we include zero, $(\mathbb{N}_0, +)$ with $\mathbb{N}_0 = {0, 1, 2, \ldots}$, we restore the identity but still have no inverses: $5$ has no inverse in $\mathbb{N}_0$ since $-5 \notin \mathbb{N}_0$. Still not a group.
Non-Example 2: Integers under Multiplication
$(\mathbb{Z}, \times)$ is not a group. The identity is $1$ and multiplication is closed and associative. But $2$ has no multiplicative inverse in $\mathbb{Z}$: we would need $\frac{1}{2}$, which is not an integer. The inverses axiom fails.
Non-Example 3: All $2 \times 2$ Real Matrices under Multiplication
Let $M_{2}(\mathbb{R})$ be the set of all $2 \times 2$ matrices with real entries. $(M_2(\mathbb{R}), \times)$ is not a group because singular matrices have no inverse. For example:
$$A = \begin{pmatrix} 1 & 0 \ 0 & 0 \end{pmatrix}$$
There is no matrix $B$ satisfying $AB = I$. The inverses axiom fails.
However, restricting to invertible $2 \times 2$ matrices (those with nonzero determinant) gives the general linear group $GL_2(\mathbb{R})$, which is a non-abelian group.
Non-Example 4: Positive Reals under Subtraction
$(\mathbb{R}{>0}, -)$ is not a group. Subtraction is not even closed: $3 - 5 = -2 \notin \mathbb{R}{>0}$. The closure axiom fails immediately, and we need not check further.
Subgroups
A subgroup $H \leq G$ is a subset of $G$ that is itself a group under the same operation. To verify $H$ is a subgroup, three conditions suffice:
- $e \in H$
- $a, b \in H \Rightarrow a \cdot b \in H$
- $a \in H \Rightarrow a^{-1} \in H$
The even integers $2\mathbb{Z} = {\ldots, -4, -2, 0, 2, 4, \ldots}$ form a subgroup of $(\mathbb{Z}, +)$. The rotations ${e, r, r^2}$ form a subgroup of $D_3$.
Lagrange’s Theorem: If $H \leq G$ and $G$ is finite, then $|H|$ divides $|G|$. This is one of the first great theorems of group theory, and it has an immediate implication for the Rubik’s Cube: the order of any subgroup of $G_{RC}$ must divide $43{,}252{,}003{,}274{,}489{,}856{,}000$.
The Rubik’s Cube
A standard $3 \times 3 \times 3$ Rubik’s Cube has:
- 6 faces, each assigned a color
- 26 visible pieces: 8 corner pieces, 12 edge pieces, 6 center pieces
- The 6 center pieces never move relative to each other and define which color belongs to which face
[U]
|
[L] -- [F] -- [R] -- [B]
|
[D]
The six face moves are U (Up), D (Down), L (Left), R (Right), F (Front), B (Back). Each turn rotates one face $90°$ clockwise. The prime notation $R’$ means $90°$ counterclockwise. The notation $R^2$ means $180°$.
The standard move set is:
$$\mathcal{M} = {U, U’, U^2, D, D’, D^2, L, L’, L^2, R, R’, R^2, F, F’, F^2, B, B’, B^2}$$
That is 18 possible single moves.
The Rubik’s Cube Group
Every sequence of moves is a permutation of the 48 colored facelets (each of the 6 faces has 9 stickers, minus the 6 fixed centers, leaving 48 stickers that can move). Since each move is a bijection from one cube state to another, and we can compose moves and invert them, the set of all reachable states forms a group.
This is the Rubik’s Cube Group:
$$G_{RC} = \langle U, D, L, R, F, B \rangle$$
The angle brackets denote that the group is generated by those six moves: every reachable state is some finite composition of these generators and their inverses. Let us verify the four group axioms.
- Closure: Performing any sequence of moves on a valid cube state produces another valid cube state.
- Associativity: Function composition is always associative: $(f \circ g) \circ h = f \circ (g \circ h)$.
- Identity: The move sequence of length zero is the identity $e$.
- Inverses: The inverse of $R$ is $R’$. The inverse of the sequence $R \cdot U \cdot F$ is $F’ \cdot U’ \cdot R’$. Every sequence reverses.
All four axioms hold. $G_{RC}$ is a group.
The order of this group is:
$$|G_{RC}| = 43{,}252{,}003{,}274{,}489{,}856{,}000 \approx 4.3 \times 10^{19}$$
Counting the States
Corner pieces: There are 8 corners. They can be placed in $8!$ arrangements. Each corner can sit in 3 orientations, giving $3^8$ possibilities. The total twist of all corners must equal zero modulo 3 (a physical constraint of the mechanism), so we divide by 3:
$$\frac{8! \times 3^8}{3} = 8! \times 3^7$$
Edge pieces: There are 12 edges. They can be placed in $12!$ arrangements. Each edge can be flipped, giving $2^{12}$ possibilities. The total number of flipped edges must be even, so we divide by 2. The parity of the corner permutation must equal the parity of the edge permutation, giving another factor of $\frac{1}{2}$:
$$\frac{12! \times 2^{12}}{4}$$
Combining both:
$$|G_{RC}| = \frac{8! \times 3^8 \times 12! \times 2^{12}}{12} = 43{,}252{,}003{,}274{,}489{,}856{,}000$$
$G_{RC}$ is a proper subgroup of $S_{48}$: most permutations of 48 facelets are physically unreachable by legal moves.
Why it is not abelian?
$$R \cdot U \neq U \cdot R$$
Turn the Right face clockwise, then the Top face clockwise. Now undo both and try Top first, then Right. The resulting states are different. The group is non-abelian, and this is precisely what makes the cube hard: solving one part inevitably disturbs previously solved parts.
Permutations nside the Cube
Every move is a permutation expressible in cycle notation. The move $U$ cycles four edge facelets and four corner pieces in two disjoint 4-cycles:
$$U = (\text{UF}\ \ \text{UR}\ \ \text{UB}\ \ \text{UL})(\text{UFR}\ \ \text{URB}\ \ \text{UBL}\ \ \text{ULF})$$
This is the same cycle notation from Section 1, now applied to physical stickers on a cube.
A commutator $[A, B] = A \cdot B \cdot A^{-1} \cdot B^{-1}$ measures how far $A$ and $B$ are from commuting. If they commuted perfectly, $[A, B] = e$. When they do not commute, the commutator is a nontrivial permutation that moves only a small number of pieces, because most of the permutation cancels algebraically.
The sequence $R \cdot U \cdot R^{-1} \cdot U^{-1}$ is a commutator. Repeating it 6 times returns the cube to the solved state. It moves only a handful of corner pieces, which is exactly what is needed when solving the last layer without disturbing the rest of the cube. Most named speedcubing algorithms are commutators or conjugates ($A \cdot X \cdot A^{-1}$) in disguise.
Could a newborn solve it?
Here is a philosophical question with mathematical teeth.
Imagine placing a Rubik’s Cube in front of a child raised in complete isolation, no mathematics, no culture, no algorithms. Can they solve it?
In principle, yes, by exhaustive search. The cube has $4.3 \times 10^{19}$ states. If our hypothetical solver tries one new state per second, the expected time is roughly $1.4 \times 10^{12}$ years. The universe is about $1.4 \times 10^{10}$ years old. Brute force takes approximately 100 times the age of the universe.
What about random moves? A random walk on the Cayley graph of $G_{RC}$ will eventually reach the solved state with probability 1, since the graph is finite and connected. But the expected number of steps before hitting any specific target vertex in a graph of $4.3 \times 10^{19}$ nodes is of the same astronomical order.
What any solver actually needs, whether they know it or not, is to exploit the group structure: that certain move sequences affect only a few pieces, that the problem decomposes into layers, that inverses are easy to compute. Every human solving method, from beginner layer-by-layer to CFOP to Roux, is implicitly navigating a subgroup tower of $G_{RC}$.
Memorized algorithms are shortcuts through the group. They encode mathematical insight as procedural memory. The cube is solvable without knowing group theory, but it is truly understandable only with it.
The Cayley Graph
The Cayley graph $\text{Cay}(G, S)$ of a group $G$ with generating set $S$ is a directed graph where:
- Each vertex is a group element
- There is a directed edge from $g$ to $g \cdot s$ for each generator $s \in S$
For $G_{RC}$ with the 18-move generating set $\mathcal{M}$, every vertex has out-degree 18. The solved state is one distinguished vertex. Solving the cube from a scrambled state is finding a shortest path in this graph from the current vertex to the solved vertex.
[scrambled] --R--> [state A] --U--> [state B] -- ... --> [solved]
The diameter of the Cayley graph, the length of the longest shortest path over all vertex pairs, is exactly God’s Number.
God’s Number
God’s Number is the maximum, over all $4.3 \times 10^{19}$ scrambled states, of the minimum number of moves needed to solve that state. In other words: if an omniscient solver always chose the optimal sequence, what is the worst case?
For decades this was an open problem. Bounds tightened steadily:
| Year | Lower Bound | Upper Bound |
|---|---|---|
| 1981 | 18 | 52 |
| 1992 | 18 | 42 |
| 2008 | 20 | 26 |
| 2010 | 20 | 20 |
In 2010, Rokicki, Kociemba, Davidson, and Dethridge proved:
$$\boxed{G_{\text{God}} = 20}$$
Every one of the $4.3 \times 10^{19}$ states can be solved in at most 20 moves. States requiring exactly 20 exist; the superflip (every edge piece flipped in its correct position, every corner correct) is one known example.
How Was It Proved?
Pure algebra alone could not do it. The proof combined group theory, coset decomposition, and large-scale computation.
Step 1: Symmetry reduction. The cube has 48 symmetries (rotations and reflections of the physical object). Grouping states related by symmetry into equivalence classes reduces $4.3 \times 10^{19}$ states to about $2.2 \times 10^{18}$ distinct classes.
Step 2: Coset decomposition. The team chose a subgroup $H \leq G_{RC}$ of order approximately $10^{10}$, consisting of all states reachable using only ${U, D, R, L, F^2, B^2}$. The left cosets of $H$ partition all of $G_{RC}$ into about $2 \times 10^{9}$ cosets, each of size approximately $10^{10}$.
Step 3: Optimal coset solver. For each coset, the team computed the optimal solution depth. This required approximately 35 CPU-years of computation, distributed across Google’s servers.
Step 4: Conclusion. No coset required more than 20 moves to bring into $H$, and no element of $H$ required more than 20 moves to solve from there. The lower bound of 20 came from a separate verification that the superflip requires exactly 20 moves. Therefore God’s Number is 20.
The group structure is what made the computation feasible. Without cosets and subgroups to partition the search space, no amount of computing power could check all $4.3 \times 10^{19}$ states individually in any reasonable time.
Is There a Formula?
There is no simple closed-form expression that maps a scrambled cube state to an optimal solution sequence. What exists are optimal solvers like Kociemba’s algorithm, which operates in two phases:
- Phase 1: Use the full move set $\mathcal{M}$ to reach the subgroup $H$ in a small number of moves
- Phase 2: Solve within $H$ using only ${U, D, R, L, F^2, B^2}$
This is not brute force. It uses precomputed lookup tables encoding the group structure of $G_{RC}/H$ and $H$ separately. For any scramble, it finds an optimal or near-optimal solution typically in milliseconds on modern hardware.
The key insight is that $H$ is a subgroup, so the coset space $G_{RC}/H$ and the group $H$ itself can each be searched efficiently. Without the subgroup structure, there is no decomposition and no feasible algorithm.
Real-World Applications of Group Theory
The Rubik’s Cube is a delightful example, but group theory is foundational across science and engineering.
Cryptography. RSA and elliptic curve cryptography rely on the group structure of modular arithmetic and elliptic curves. The security of HTTPS connections rests on the computational hardness of the discrete logarithm problem in certain groups: given $g$ and $g^k$ in a group, find $k$.
Particle Physics. The Standard Model of particle physics is organized by Lie groups: $U(1)$, $SU(2)$, $SU(3)$. Every elementary particle corresponds to a representation of one of these groups. The classification of quarks and leptons is, at its core, a classification of group representations.
Error-Correcting Codes. Linear codes are subspaces (and subgroups) of $\mathbb{F}_2^n$, the group of binary strings of length $n$ under componentwise XOR. The group structure guarantees that errors can be detected and corrected. Every digital communication system uses this.
Chemistry and Crystallography. Molecular symmetry is described by point groups. Benzene has $C_{6v}$ symmetry. Methane has $T_d$ symmetry. Chemists use these groups to predict infrared and Raman spectra, reaction pathways, and molecular orbital structure.
Robotics and Computer Graphics. Rotations in 3D space form the group $SO(3)$, the special orthogonal group. Every rotation of a rigid body is an element of $SO(3)$. Every 3D game engine, robot arm controller, and satellite attitude system computes in this group continuously.
Does knowing Group Theory help solve the Cube?
Practically, not directly. Knowing that $G_{RC}$ is a subgroup of $S_{48}$ will not help finish the last layer faster. Competitive speedcubers memorize hundreds of algorithms without knowing their algebraic names.
Conceptually, the understanding is enormous. Group theory explains:
- Why layer-by-layer methods work: each layer corresponds to a subgroup, and solving a layer means navigating into a coset
- Why commutators move so few pieces: most of the permutation cancels algebraically
- Why the cube is always solvable from any legal state: $G_{RC}$ is a single connected component in its Cayley graph
- Why it is impossible to swap exactly two corners without swapping two more: this is a parity constraint, a consequence of how $G_{RC}$ sits inside the alternating group $A_{48}$
That last point deserves emphasis. If a cube is disassembled and its pieces reassembled at random, there is a $\frac{11}{12}$ probability that the result is a state unreachable by any legal sequence of moves. The cube will look scrambled but will be physically unsolvable. Group theory reveals this fact before touching a cube, purely from the algebraic structure of permutation parities.
The bigger picture
The Rubik’s Cube sits at the intersection of several mathematical disciplines:
- Group theory: algebraic structure, generators, subgroups, cosets, conjugates, commutators
- Combinatorics: counting $4.3 \times 10^{19}$ states precisely from physical constraints
- Graph theory: Cayley graphs, diameter, shortest paths, random walks
- Computational complexity: optimal solving, and NP-hardness for the $n \times n \times n$ generalization
God’s Number is not a curiosity about a toy. It is a theorem, proved with mathematical certainty, that a specific combinatorial object has Cayley graph diameter 20 in the half-turn metric. The proof required both the elegance of abstract algebra and the raw power of distributed computation. That combination is increasingly characteristic of modern mathematics.
In a follow-up post, we will go further.