§10

Subgroup chain — Thistlethwaite's solver

In 1981, the mathematician Morwen Thistlethwaite realised: rather than directly solving G, decompose it into a chain of four nested subgroups, each phase solving one constraint at a time:

G₀

⟨U, D, L, R, F, B⟩

|G| = 4.3 × 10¹⁹

⊃

G₁

⟨U, D, L, R, F2, B2⟩

[G:G₁] = 2¹¹

⊃

G₂

⟨U, D, L2, R2, F2, B2⟩

[G₁:G₂] = 1,082,565

⊃

G₃

⟨U2, D2, L2, R2, F2, B2⟩

[G₂:G₃] = 29,400

⊃

G₄ = {e}

⟨⟩

[G₃:G₄] = 663,552

Each step "patches" one defect:
G → G₁: orient edges (EO = 0).
G₁ → G₂: orient corners (CO = 0) and bring UD-slice edges home.
G₂ → G₃: corners and edges in their G₃-orbits.
G₃ → G₄: finish using only half-turns.

Thistlethwaite originally bounded each phase at 7 / 13 / 15 / 17 moves, totalling 52 moves for any state. Kociemba later collapsed this into a 2-phase chain G → G₁ → {e}, each phase ≤ 12 moves, total ≤ 24. This is the famous two-phase algorithm behind every modern fast solver.

Interactive § Thistlethwaite subgroup chain

Climb from G down to {e} through four fixed subgroups. Input an alg, see what depth its state is "inside".

alg

identityR2U R2R U R'OLL 26superflip

G₀ = G

⟨U,D,L,R,F,B⟩

G₁

⟨U,D,L,R,F2,B2⟩

G₂

⟨U,D,L2,R2,F2,B2⟩

G₃

⟨U2,D2,L2,R2,F2,B2⟩

G₄ = {e}

⟨⟩

Current state is in G0. From here, the cube can be solved using only G0's generators.

10.1 Sizes of the quotients

Each Thistlethwaite step's quotient size $[G_{i} : G_{i + 1}]$ equals the number of states to look up at that phase. These numbers directly drive a solver's memory footprint:

sizes of consecutive Thistlethwaite quotients

[G : G₁]

orient edges: 12 binary flips constrained by Σeo=0

2,048

[G₁: G₂]

orient corners + UD slice: 3⁷ × (12 choose 4)

1,082,565

[G₂: G₃]

corners and edges into G₃ orbits

29,400

[G₃: G₄]

solve with half-turns only — the "domino" group

663,552

Sanity check: 2048 × 1,082,565 × 29,400 × 663,552 = 4.3 × 10¹⁹ = |G| ✓

Kociemba consolidated this 4-phase chain into a 2-phase one: G → G_1 → {e}, with quotient sizes 2 × 10⁹ and 1.95 × 10¹⁰. The two pruning tables fit in ~100 MB, and solve any state in milliseconds (typically ≤ 24 moves). Every cube app (Cube Explorer, csTimer's built-in solver, ...) is powered by this structure.

10.2 Cosets

Definition 10.1

Let

H \subseteq G

be a subgroup,

g \in G

. The left coset is

g H = {g h : h \in H}

. All cosets have size

∣ H ∣

, and G partitions into

[G : H]

disjoint cosets.

The Thistlethwaite solver's key idea: map cube states to cosets, ignoring the fine structure within a coset. Each phase moves to the next (smaller) coset until reaching G_4 = {e}. Cosets are the trick that turns an exponential problem into a polynomial one.

10.3 Lagrange's theorem

Theorem 10.2 — Lagrange

Let

H \subseteq G

be a subgroup of a finite group. Then

∣ H ∣ ∣ G ∣

(i.e.

∣ H ∣

divides

∣ G ∣

), and

∣ G ∣ = ∣ H ∣ \cdot [G : H]

The most basic theorem in group theory says: any subgroup's order must divide 4.3 × 10¹⁹. So ⟨R, U⟩ has order 73,483,200 | |G|, ⟨U⟩ has order 4 | |G|, |G_3| = 663,552 | |G| — all automatic.

10.4 State-space size and diameter per phase

For each phase, the number of states (cosets) and the BFS diameter on that coset graph:

Phase	Coset size	Diameter (HTM)	Coordinate
$G \to G_{1}$	2¹¹ = 2,048	7	12-edge orientation (11 free)
$G_{1} \to G_{2}$	3⁷ · $(4 12)$ = 2187 · 495 = 1,082,565	10	7-corner orient. + UD-slice edge placement
$G_{2} \to G_{3}$	29,400	13	corners and edges into 4-orbits
$G_{3} \to {e}$	663,552	15	half-turn-only "domino" group
Total upper bound	7 + 10 + 13 + 15 = 45		original 1981 Thistlethwaite gave 52; later refined

Reid (1995) tightened the upper bound to ≤ 52 HTM (matching Thistlethwaite's original); Korf's later experiments showed ≤ 38 empirically. Rokicki (2010) then merged "G → G₂ direct search" — described in §11 — to drive the worst case to exactly 20.

10.5 Kociemba's "merge G → G₂"

Thistlethwaite used 4 stages because each coset table had to fit into 1980s RAM (≤ 10⁶). Kociemba (1990s) noticed that the combined jump $G \to G_{2}$ has $[G : G_{2}] = 2, 217, 093, 120 = 2^{11} \cdot 3^{7} \cdot (4 12) \cdot (more)$

By Lagrange, $∣ G ∣ = [G : G_{2}] \cdot ∣ G_{2} ∣$ , so $∣ G_{2} ∣ = ∣ G ∣/2, 217, 093, 120 \approx 1.95 \times 1 0^{10}$ — matching the known value. IDA* with a ~2 GB pruning table searches G → G₂, then BFS finishes within G₂ — the modern two-phase solver (Kociemba 1992; Reid's cube20 refinements). Average ~21 HTM, worst case 20.

∎

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