§25

Computational group theory: BSGS & Schreier–Sims

How do we exactly compute |G| = 43,252,003,274,489,856,000? Not by formula — by a recursive algorithm called Schreier–Sims. It constructs G's BSGS (Base + Strong Generating Set), the canonical internal representation used by GAP, Magma, and SageMath for all finite permutation groups.

Definition 25.1 — base & stabilizer chain

Let G act on Ω (cube: |Ω| = 48 stickers). Choose a base

B = (b_{1}, b_{2}, \dots, b_{k}) \subset Ω

giving a stabilizer chain

G \supset G^{(1)} \supset G^{(2)} \supset \dots \supset G^{(k)} = {e}

where

G^{(i)} = Stab_{G} (b_{1}, \dots, b_{i})

. Then

∣ G ∣ = \prod_{i} ∣ G^{(i - 1)} \cdot b_{i} ∣

(product of orbit sizes).

25.1 Interactive: the cube's stabilizer chain

level	fixed stickers	\|stab\|	orbit size
0	0	4.33e+19	48
1	1	9.01e+17	24
2	2	5.63e+16	16
3	3	4.69e+15	12
4	4	4.69e+14	10
5	5	4.70e+13	10
10	10	2.00e+9	small
15	15	50000	small
20	20	240	tiny
23	23	8	2
24	24	1	1

View G as permutations of 48 stickers. Schreier–Sims iteratively fixes one sticker at a time, restricting to its stabilizer subgroup, producing a chain

G = G^{0} ⊋ G^{1} ⊋ \dots ⊋ {e}

. Multiplying orbit sizes at each level gives

∣ G ∣

. This is how GAP / Magma exactly compute

∣ G ∣ = 4.3 \times 1 0^{19}

25.2 Schreier–Sims algorithm (1970)

Idea (Schreier 1927 + Sims 1970): given generators $S = {s_{1}, \dots, s_{m}}$ , recursively build the base B and the strong generating set $S^{*}$ . Use Schreier's lemma at each level to compute generators of the next stabilizer. The algorithm runs in polynomial time $O (n^{5})$ with n = |Ω|.

GAP code (verify |G| = 4.3 × 10¹⁹):

gap> G := Group( > (1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19), > # ... 5 more generators encoding U, D, L, R, F, B as permutations of 48 stickers > );; gap> Size(G); 43252003274489856000 gap> StructureDescription(G); "(C2 x C2 x C2 x C2 x C2 x C2 x C2) : ((C3 x C3 x C3 x C3 x C3 x C3 x C3) : (A8 x A12))"

25.3 Schreier's lemma + pseudocode

Schreier's lemma (1927)

Let

H \leq G

have index

[G : H]

T = {t_{1}, \dots, t_{m}}

a left transversal of H in G (with

t_{1} = e

), and

S

a generating set for G. For

g \in G

, write

\overset{g}{ˉ}

for its T-representative. Then

H = ⟨ \overset{ˉ}{(t \cdot s)}^{- 1} \cdot (t \cdot s) : t \in T, s \in S ⟩ .

So H is generated by these

m ∣ S ∣

"Schreier generators".

Applying "H is generated by G-generators + transversal" recursively yields the Schreier–Sims algorithm:

SchreierSims(S, base B): for i = 1 to |B|: compute orbit O_i = G^(i-1) · b_i via BFS on S^(i-1) record Schreier vector V_i (transversal lookup) derive S^(i) = { Schreier generators for Stab(b_i) } recurse on (S^(i), B[i+1:]) return BSGS = (B, S* = union of S^(i)) Size(G) = ∏_i |O_i| Membership(g): for i = 1 to |B|: let j = position of g(b_i) in O_i if j undefined: return false g = g · V_i[j]^(-1) return (g == identity)

25.4 The cube's stabilizer chain, explicitly

Take Ω = the 20 movable cubies (8 corners + 12 edges, position layer). A natural base $B = (1, 2, \dots, 20)$ yields:

i	base point b_i	\|O_i\|	stabilizes to
1	corner URF	8	G⁽¹⁾
2	corner UFL	7	G⁽²⁾
…	…	…	…
8	last corner	3	cor twists ÷ 3
9	edge UR	12	G⁽⁹⁾
…	…	…	…
19	last edge	2	edge flip ÷ 2
20	parity	1	{e}

∣ G ∣ = = 8! 8 \cdot 7 \cdot 6 \dots 2 \cdot corner twist 3 \cdot = 12! 12 \cdot 11 \dots 2 \cdot edge flip 2 \cdot parity 1 \cdot prior twists 3^{6} \cdot prior flips 2^{10}

Multiplying the orbit sizes gives precisely $8! \cdot 12! \cdot 3^{7} \cdot 2^{11} /2 = 43, 252, 003, 274, 489, 856, 000$ . This is why BSGS is more fundamental than the closed-form factorization — it doesn't assume the invariants; it derives them from generators.

25.5 Complexity & related algorithms

Deterministic Schreier–Sims runs in $O (n^{5} + n^{2} ∣ S ∣)$ time, $O (n^{2} ∣ B ∣ + ∣ S^{*} ∣)$ memory. Improved variants:

Sims 1971 (Las Vegas): expected time $O (n^{4} lo g ∣ G ∣)$ .
Knuth 1991: with strong-generator reorganisation, an order of magnitude faster in practice.
Babai–Cooperman 1989: introduced "nearly-linear-time" BSGS, expected $O (n^{2} lo g^{c} n)$ .
Holt–Eick–O'Brien 2005 (modern GAP/Magma backend): empirical $\sim n^{3}$ , handling |Ω| ~ 10⁶ groups in seconds.

BSGS-adjacent algorithms in the computational toolkit:

Todd–Coxeter (1936): given a finite presentation (generators + relations) and a subgroup H, enumerates cosets G/H. Dual to BSGS: one starts from permutations, the other from relations.
Baby-step giant-step: gives $O (∣ G ∣)$ for the word problem, agnostic to structure — but for G ≈ 4.3 × 10¹⁹ that's still ~6 × 10⁹ operations, infeasible. BSGS reduces it to O(n²) — which is why "BSGS is foundational."
Brownian motion in the symmetric group (Diaconis): couples BSGS with §24's random walks, giving the expected number of random generators needed to generate all of G.

25.6 Why does this matter for cube algorithms?

BSGS is the natural data structure for the membership test: given g, is g ∈ G? Layer-by-layer reduce via Schreier transversals; total fully reduced ⇒ yes. Time $O (k \cdot n^{2})$ . Not directly useful for solvers (they need short presentations; BSGS gives long ones, average $lo g ∣ G ∣ \approx 65$ moves), but indispensable for group questions:

"Does this alg set generate all of G?" — run BSGS, check if Size equals |G|.
"What is the index of this subgroup?" — BSGS yields |H| directly, hence |G|/|H|.
"Enumerate conjugacy classes / centre / commutator subgroup" — BSGS yields a uniform-random sampling algorithm on G (Furst–Hopcroft–Luks).

∎

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