§21

Symmetric & alternating groups

Permutation groups are the oldest, most concrete, and most prolific family in group theory. When Cauchy, Cayley, and Galois founded the subject in the 19th century, "group" was essentially synonymous with "permutation set." The cube group lives inside $S_{8} \times S_{12}$ . Understanding $S_{n}$ and $A_{n}$ is half of cube algebra.

Definition 21.1 — symmetric group Sₙ

S_{n}

is the set of all bijections of {1, 2, ..., n} under composition. Its order is

∣ S_{n} ∣ = n!

Definition 21.2 — alternating group Aₙ

A_{n} \subset S_{n}

consists of the even permutations (those decomposable into an even number of transpositions);

A_{n} = ker (sgn : S_{n} \to {\pm 1}) .

A_{n}

is normal in

S_{n}

with

∣ A_{n} ∣ = n! /2

21.1 Simplicity of Aₙ (n ≥ 5)

Theorem 21.3 — Galois

For all

n \geq 5

A_{n}

is a simple group: it has no proper non-trivial normal subgroups.

This theorem is the heart of Galois's proof that the quintic has no radical solution. Brief proof outline:

Verify that Aₙ is generated by 3-cycles (for n ≥ 3, every even permutation is a product of 3-cycles).
Let $N ◃ A_{n}$ be non-trivial. Show N must contain a 3-cycle.
Using conjugation, transport every 3-cycle into N. Hence N contains all the generators of Aₙ, forcing N = Aₙ. Contradiction.

A₅ is the smallest non-Abelian simple group (|A₅| = 60), and the entry point to the classification of finite simple groups. The cube uses both $A_{8}$ (corner permutations) and $A_{12}$ (edges), both non-Abelian simple.

21.2 Interactive: parity calculator

Plug in any alg; the calculator instantly returns sgn(cp), sgn(ep), and their product. The third invariant forces the product to be +1; if you type in an impossible state like a single-edge flip, the calculator shows −1 — algebraic proof of unreachability.

sgn(cp)

even

sgn(ep)

even

sgn(cp) · sgn(ep)

✓ reachable in G

corner cycles[5, 3]

edge cycles[8, 2]

This is the third invariant from §5 in action:

sgn (c_{p}) = sgn (e_{p})

. In G, corner parity and edge parity must flip together; sgn is a homomorphism G → ℤ/2 whose kernel is the "double-even" subgroup.

21.3 Cayley's theorem: every group is a permutation group

Theorem 21.4 — Cayley (1854)

Every group G embeds into a symmetric group:

G ↪ S_{∣ G ∣} .

The map

g \mapsto L_{g}

sends g to the left-multiplication permutation

L_{g} (x) = g x

. This is an injection of groups.

For the cube this is "obvious and useless": abstractly $G ↪ S_{∣ G ∣} = S_{4.3 \times 1 0^{19}}$ , which is astronomically large. In practice G embeds into $S_{48}$ (permutations of 48 stickers), a much lower-dimensional representation. Cayley's theorem inspires the idea; finding minimal faithful representations is the real game.

21.4 Conjugacy classes ↔ partitions — the shape alphabet of Sₙ

Theorem 21.5 — conjugacy classes of Sₙ

Two permutations in

S_{n}

are conjugate iff they share the same disjoint cycle type. Conjugacy classes ↔ integer partitions of

n

in one-to-one correspondence. For a permutation with cycle type

1^{m_{1}} 2^{m_{2}} \dots n^{m_{n}}

, its conjugacy-class size is

∣ [σ] ∣ = \frac{n !}{\prod _{k} k ^{m_{k}} \cdot m _{k} !} .

Example: $S_{8}$ (corner permutations). The number of partitions $p (8) = 22$ , so $S_{8}$ has exactly 22 conjugacy classes. The biggest is the 8-cycle class (cycle type (8)): $∣ [σ] ∣ = 8! /8 = 5040$ , accounting for 1/8 of 8! = 40320.

partition	cycle type	class size	sgn	order
8	(a b c d e f g h)	5,040	−	8
7 + 1	(a b c d e f g)(h)	5,760	+	7
6 + 2	(6)(2)	3,360	−	6
5 + 3	(5)(3)	2,688	+	15
4 + 4	(4)(4)	1,260	+	4
3 + 3 + 2	(3)(3)(2)	1,120	−	6
2 + 2 + 2 + 2	(2)⁴	105	+	2
1⁸	(1)⁸ (identity)	1	+	1

Sanity check: Σ class sizes = 40320 = 8! ✓ (across all 22 partitions). The sgn is determined by the number of even-length cycles: even permutation = even count; odd = odd count. This also explains how $A_{8}$ selects half of these classes: of the 22 in $S_{8}$ , exactly 13 sit in $A_{8}$ (some split into two $A_{8}$ -conjugacy classes).

21.5 Counterexample: A₄ is not simple

Galois's theorem 21.3 requires $n \geq 5$ . For $n = 4$ , $A_{4}$ is not simple: it has a non-trivial normal subgroup, the celebrated Klein four-group $V_{4} = {e, (12) (34), (13) (24), (14) (23)} ◃ A_{4} .$ V₄ contains all "products of two disjoint transpositions," has order 4. All three non-identity elements form one conjugacy class (type (2,2)), so V₄ is closed under $A_{4}$ -conjugation.

The quotient $A_{4} / V_{4} ≅ Z /3$ . This is why quartic equations still have radical solutions — the Galois group $S_{4}$ has composition series $S_{4} ▹ A_{4} ▹ V_{4} ▹ ⟨(12) (34)⟩ ▹ {e}$ with all factors cyclic (ℤ/2, ℤ/3, ℤ/2, ℤ/2) — by definition solvable. For $n \geq 5$ , $A_{n}$ is simple and cannot be broken down further, so $S_{n}$ is not solvable — the algebraic obstruction to radical solutions of higher-degree equations.

21.6 Generators of Sₙ — adjacent transpositions suffice

Three commonly used generating sets for $S_{n}$ :

All transpositions ${(i, j) : 1 \leq i < j \leq n}$ : total $(2 n)$ . Every permutation factors as a product of transpositions.
Adjacent transpositions ${(i, i + 1) : 1 \leq i < n}$ : just $n - 1$ . Yields the "bubble sort" view of $S_{n}$ , satisfying braid relations $s_{i} s_{i + 1} s_{i} = s_{i + 1} s_{i} s_{i + 1}$ , $s_{i}^{2} = e$ , and $s_{i} s_{j} = s_{j} s_{i}$ for $∣ i - j ∣ \geq 2$ .
One transposition + one n-cycle: just 2 elements, namely ${(1, 2), (1, 2, 3, \dots, n)}$ , generate $S_{n}$ . For $A_{n}$ ( $n \geq 3$ ), the pair ${(1, 2, 3), (1, 2, \dots, n)}$ similarly suffices.

The "adjacent transposition + braid relations" presentation links

S_{n}

to topology's braid groups

B_{n}

: dropping the relation

s_{i}^{2} = e

lifts

S_{n}

B_{n}

. Braid groups are infinite and connect to knot theory and (topological) quantum computing. The cube has its own "half-braid" structure under adjacent-face turns — finite and bounded by the conservation laws.

21.7 Pólya cycle index — counting colourings

For G acting on an n-element set X, Pólya defined the cycle index polynomial:

Z_{G} (z_{1}, z_{2}, \dots, z_{n}) = \frac{1}{∣ G ∣} g \in G \sum z_{1}^{c_{1} (g)} z_{2}^{c_{2} (g)} \dots z_{n}^{c_{n} (g)},

where $c_{k} (g)$ is the number of length-k cycles in g. Pólya's enumeration theorem: the number of colourings of X with c colours, up to G-equivalence, equals $# colourings / G = Z_{G} (c, c, \dots, c) .$ Application: the cube's outer symmetry group $O_{h}$ (order 48) acts on 6 faces; "how many essentially different ways to colour the cube with 6 colours?" $Z_{O_{h}} (6, 6, \dots, 6) = \frac{1}{48} (6^{6} + 3 \cdot 6^{4} + \dots) = 30.$ Exactly 30 essentially distinct 6-coloured cubes.

∎

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