§23

Distance distribution & the 20-move proof

The cube's Cayley-graph distance distribution is a striking diagram: nearly all 4.3 × 10¹⁹ states land at d = 18 or 19, while only 4.9 × 10⁸ states sit at d = 20. This distribution is exactly what the God's-number-20 proof produced.

23.1 Interactive chart (HTM)

hover to see count at each distance d

enumerated (Rokicki et al.) approximated

Vertical axis is log₁₀(count). A few features to notice:

d = 0…8: roughly $\sim 18 \cdot 1 5^{d - 1}$ (18 generators, with cancellations); near-exponential growth.
d = 8…15: exponential growth saturates; unvisited neighbors per state plateau.
d = 15…18: peak around 18 or 19. The bulk of G's elements live there.
d = 20: 4.9 × 10⁸ states. "God's number = 20" is the joint fact that this row is non-zero and any d = 21 row would have to be empty.

23.2 HTM vs QTM

Metric	Generators	Diameter	Random avg	Bound proof
HTM (half-turn)	18	20	~18	2010 Rokicki et al.
QTM (quarter-turn)	12	26	~22	2014 Rokicki & Kociemba
STM (slice)	27	≤ 20 (unproven)	~17	partial enumerations

23.3 Superflip & the "strict-20" club

Four states were once known as "the furthest": superflip (all edges flipped; Reid 1995 proved it requires 20 HTM), and superflip composed with the 4-spot or 6-spot patterns. After 2010, the full census reveals 4.9 × 10⁸ states at exactly distance 20.

Interestingly, these 4.9 × 10⁸ "farthest" states make up 10⁻¹¹ of |G|. A random scramble has expected distance 18 and essentially never hits 20. The "God's number" is an extreme-value result, not a measure of difficulty.

23.4 Exact numerical table (HTM)

The table below gives exact counts for d = 0…15 (full enumeration, Kociemba 2013) and the established counts for d = 16…20 (symmetry-reduced proofs after Rokicki et al. 2014). The column totals to |G| = 43,252,003,274,489,856,000.

d	states at d	fraction of \|G\|	ratio
0	1	~0	—
1	18	~0	18.0×
2	243	~0	13.5×
3	3,240	~0	13.3×
4	43,239	~0	13.3×
5	574,908	~0	13.3×
6	7,618,438	~0	13.3×
7	100,803,036	~0	13.2×
8	1,332,343,288	3.1 × 10^-11	13.2×
9	17,596,479,795	4.1 × 10^-10	13.2×
10	232,248,063,316	5.4 × 10^-9	13.2×
11	3,063,288,809,012	7.1 × 10^-8	13.2×
12	40,374,425,656,248	9.3 × 10^-7	13.2×
13	531,653,418,284,628	1.2 × 10^-5	13.2×
14	6,989,320,578,825,358	1.6 × 10^-4	13.1×
15	91,365,146,187,124,313	2.1 × 10^-3	13.1×
16	≈ 1.10 × 10¹⁸	2.5%	12.0×
17	≈ 1.22 × 10¹⁹	28.3%	11.1×
18	≈ 2.98 × 10¹⁹	68.9%	2.4×
19	≈ 1.50 × 10¹⁸	3.5%	0.05×
20	490,000,000	1.1 × 10^-11	3.3 × 10^-10×
21+	0	0	—
Σ	4.325 × 10¹⁹	100%	= \|G\|

The "ratio" column shows the geometric structure of the Cayley graph: from d = 1 to d = 15, each shell grows by ~13.2× (well below 18, because moves like $R \cdot R = R^{2}$ overlap and reduce the effective branching factor). Then between d = 16…18, growth saturates dramatically — 97% of G's elements cluster in shells 17 and 18. d = 19 already drops to 3.5%; d = 20 is nearly empty (only 4.9 × 10⁸). This is the canonical "ball explosion then boundary collapse" shape of finite Cayley graphs.

Corollary 23.4 — average distance

E [d] = \frac{1}{∣ G ∣} d = 0 \sum 20 d \cdot N_{d} \approx 17.97

where

N_{d}

is the state count at distance d. A uniformly random scramble has expected optimal length ~17.97 HTM (~22 in QTM). The gap from human solvers (~50–60 HTM) reflects the cost of using heuristic strategies rather than optimal search — about a 40-move gap.

23.5 Growth function & asymptotic geometry

For any group G with generating set S, the ball growth function is $B (r) := # {g \in G : d_{S} (g, e) \leq r}$ the total state count within radius r. For the finite cube group, B(r) saturates at |G| for r ≥ 20. For infinite groups (free groups, hyperbolic groups), the asymptotic growth of B(r) reveals a group's "geometric dimension."

Polynomial growth (Gromov 1981): $B (r) \sim r^{d}$ ⟺ G is virtually nilpotent. ℤⁿ has d = n.
Exponential growth: $B (r) \sim c^{r}$ , free groups and most non-Abelian groups. The cube has exponential local growth in the small-r regime.
Intermediate growth: Grigorchuk's group (1980) — growth strictly between polynomial and exponential. A landmark in geometric group theory.

The cube group is finite, so growth is ultimately constant (B(r) = |G| for r ≥ 20). But in the "young" regime r ≤ 12, growth is nearly exponential (~13.2× per step), close to the free group

F_{18}

's 18× — until relations accumulate. This "exponential growth then collapse" is the standard template for studying word-length functions and group diameters.

∎

cuberoot.me · Rubik's Cube as a Group · 2026