Chapter 6 · Groups

6.3 Permutation Groups, Group Actions and the Class Equation

Every finite group is a group of permutations. Cycle notation, parity and conjugacy in $S_n$; group actions, the orbit–stabiliser theorem and Burnside's counting lemma; and the class equation, which forces every $p$-group to have a non-trivial centre and every group of order $p^2$ to be abelian.

Groups were first studied as groups of permutations: Lagrange, Ruffini and Galois looked at the ways of shuffling the roots of a polynomial, and Cauchy developed the cycle notation we still use. Abstract groups came later, and Cayley's theorem says that nothing was lost: every group is (isomorphic to) a group of permutations. So the symmetric groups $S_n$ are not just one family of examples among many — they are the universal examples, and the language of cycles, parity and conjugacy that we develop for them is used throughout algebra, combinatorics and geometry.

The second idea of the section turns this round. Instead of studying permutations for their own sake, we let a group act on a set — rotations acting on the faces of a cube, a group acting on itself by conjugation, a group acting on the cosets of a subgroup — and read off information from the orbits. Three counting formulas come out of this: the orbit–stabiliser theorem, Burnside's lemma (how many essentially different necklaces are there?) and the class equation (why does every group of order $p^2$ commute?). CSIR NET examines all of this directly: "how many elements of order $4$ in $S_6$?", "which of these are class equations?", "how many colourings up to rotation?", "is the centre of a group of order $p^3$ trivial?" are standard Part B and Part C questions, and the class equation is the engine behind the Sylow theorems of §6.4.

Notation (as in §6.1–6.2): $e$ is the identity, $o(g)$ the order of an element, $[G:H]$ the index, $Z(G)$ the centre, $H\trianglelefteq G$ a normal subgroup, $\mathbb{Z}_n$ the cyclic group of order $n$, $D_n$ the dihedral group of order $2n$ (the symmetries of a regular $n$-gon) and $Q_8=\{\pm1,\pm i,\pm j,\pm k\}$ the quaternion group.

Permutations and Cycle Notation

📘 Definition 6.19 — Symmetric groups and cycles

For a set $X$, $\operatorname{Sym}(X)$ is the group of all bijections $X\to X$ under composition; $S_n=\operatorname{Sym}(\{1,2,\dots,n\})$, a group of order $n!$. We compose right to left, like functions: $\sigma\tau$ means "first $\tau$, then $\sigma$", so $(\sigma\tau)(i)=\sigma(\tau(i))$.

  • For distinct $a_1,\dots,a_k$ ($k\ge2$) the $k$-cycle $(a_1\ a_2\ \cdots\ a_k)$ is the permutation $a_1\mapsto a_2\mapsto\cdots\mapsto a_k\mapsto a_1$ that fixes every other point; $k$ is its length. A $2$-cycle is a transposition. The same cycle can be written starting at any of its entries: $(1\ 4\ 7)=(4\ 7\ 1)=(7\ 1\ 4)$.
  • The support of $\sigma$ is $\{i:\sigma(i)\ne i\}$. Cycles are disjoint if their supports are disjoint.
  • If $\sigma$ is a product of disjoint cycles of lengths $k_1\ge k_2\ge\cdots\ge k_r$, where we also count each fixed point as a cycle of length $1$ so that $k_1+\cdots+k_r=n$, the partition $(k_1,\dots,k_r)$ of $n$ is the cycle type of $\sigma$. We also write it as $1^{m_1}2^{m_2}\cdots n^{m_n}$, where $m_k$ is the number of $k$-cycles; e.g. $(1\ 3\ 5)(2\ 4)\in S_6$ has type $(3,2,1)=1^1\,2^1\,3^1$.
📐 Theorem 6.32 — Disjoint cycle decomposition
Every $\sigma\in S_n$ other than $e$ is a product of disjoint cycles of length at least $2$, and this decomposition is unique up to the order of the factors. Disjoint cycles commute with each other.

Proof. For $i,j\in\{1,\dots,n\}$ put $i\approx j$ if $j=\sigma^k(i)$ for some $k\in\mathbb{Z}$. This is an equivalence relation ($\sigma^0=e$; $j=\sigma^k(i)\Rightarrow i=\sigma^{-k}(j)$; $\sigma^l(\sigma^k(i))=\sigma^{k+l}(i)$); its classes are the orbits of $\langle\sigma\rangle$. Fix $i$. The points $i,\sigma(i),\sigma^2(i),\dots$ cannot all be distinct, so $\sigma^r(i)=\sigma^s(i)$ for some $r\lt s$, i.e. $\sigma^{s-r}(i)=i$. Let $k\ge1$ be the least exponent with $\sigma^k(i)=i$. Then $i,\sigma(i),\dots,\sigma^{k-1}(i)$ are distinct (an equality $\sigma^a(i)=\sigma^b(i)$ with $0\le a\lt b\lt k$ would give $\sigma^{b-a}(i)=i$ with $0\lt b-a\lt k$), and for any $m\in\mathbb{Z}$, writing $m=qk+r$ with $0\le r\lt k$ gives $\sigma^m(i)=\sigma^r(i)$. So the orbit of $i$ is exactly $\{i,\sigma(i),\dots,\sigma^{k-1}(i)\}$ and $\sigma$ acts on it as the cycle $\gamma_i=(i\ \sigma(i)\ \cdots\ \sigma^{k-1}(i))$. Taking one such cycle for each orbit with at least two points, $\sigma$ and the product of these cycles agree at every point, so they are equal.

Disjoint cycles $\gamma,\delta$ commute: a point in the support of $\gamma$ is moved by $\gamma$ to another point of that support, which $\delta$ fixes, so $\gamma\delta$ and $\delta\gamma$ both act there as $\gamma$; similarly on the support of $\delta$; elsewhere both fix the point. Uniqueness: if $\sigma=\delta_1\cdots\delta_r$ with disjoint cycles $\delta_j$, then on the support of $\delta_j$ the permutation $\sigma$ acts as $\delta_j$, so that support is an orbit of $\langle\sigma\rangle$ and $\delta_j$ is the cycle $\gamma_i$ of any of its points. ∎

📐 Theorem 6.33 — Order of a permutation; powers of a cycle

(a) A $k$-cycle has order $k$. (b) If $\sigma$ is a product of disjoint cycles of lengths $k_1,\dots,k_r$, then $o(\sigma)=\operatorname{lcm}(k_1,\dots,k_r)$. (c) If $\gamma$ is a $k$-cycle and $j\in\mathbb{Z}$, then $\gamma^j$ is a product of $d=\gcd(j,k)$ disjoint cycles, each of length $k/d$. In particular $\gamma^j$ is again a $k$-cycle iff $\gcd(j,k)=1$.

Proof. (a) Label the cycle $\gamma=(a_0\ a_1\ \cdots\ a_{k-1})$ with indices in $\mathbb{Z}_k$, so $\gamma(a_i)=a_{i+1}$ and $\gamma^j(a_i)=a_{i+j}$. Hence $\gamma^j=e$ iff $j\equiv0\pmod k$. (b) Write $\sigma=\gamma_1\cdots\gamma_r$. Because disjoint cycles commute, $\sigma^m=\gamma_1^m\cdots\gamma_r^m$, and the factors $\gamma_i^m$ move points only inside the (disjoint) supports of the $\gamma_i$. So $\sigma^m=e$ iff $\gamma_i^m=e$ for every $i$ iff $k_i\mid m$ for every $i$, by (a); the least such $m\ge1$ is $\operatorname{lcm}(k_1,\dots,k_r)$. (c) On the labels, $\gamma^j$ is the translation $i\mapsto i+j$ of $\mathbb{Z}_k$. Its orbits are the cosets of the subgroup $\langle j\rangle$ of $\mathbb{Z}_k$, which has order $k/\gcd(j,k)$ (§6.1); there are $\gcd(j,k)$ cosets, each of size $k/\gcd(j,k)$. ∎

📐 Theorem 6.34 — Counting permutations of a given cycle type
The number of permutations in $S_n$ of cycle type $1^{m_1}2^{m_2}\cdots n^{m_n}$ (so $\sum_k k\,m_k=n$) is $$\frac{n!}{z},\qquad z=\prod_{k=1}^{n}k^{m_k}\,m_k!\,.$$ For example, $S_n$ contains $\dfrac{n!}{k\,(n-k)!}$ cycles of length $k$, and $(n-1)!$ cycles of length $n$.

Proof. Write down a "template" of brackets of the prescribed lengths — $m_n$ brackets of length $n$, …, $m_1$ brackets of length $1$, in a fixed order — and fill the $n$ slots with $1,\dots,n$ in any order: $n!$ fillings, each giving a permutation of the right type, and every such permutation arises. A permutation arises from exactly $z$ fillings: each $k$-cycle can be started at any of its $k$ entries ($k^{m_k}$ choices for the $k$-cycles), and the $m_k$ cycles of equal length can be put into the $m_k$ brackets of that length in any order ($m_k!$ choices); different choices give different fillings, and these are the only fillings producing the same permutation, by the uniqueness in Theorem 6.32. ∎

✏️ Example 1 — Computing in $S_9$
Let $\sigma\in S_9$ be given in two-line form by $\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\4&5&8&7&2&3&1&9&6\end{pmatrix}$ and let $\tau=(1\ 2)(3\ 4\ 5)$. Find the cycle decomposition and order of $\sigma$; compute $\sigma\tau$, $\tau\sigma$, $\sigma^{-1}$ and $\sigma^{2026}$.
Cycles Follow the arrows from the smallest unused point: $1\to4\to7\to1$; $2\to5\to2$; $3\to8\to9\to6\to3$. So $$\sigma=(1\ 4\ 7)(2\ 5)(3\ 8\ 9\ 6),$$ of cycle type $(4,3,2)$ and order $\operatorname{lcm}(3,2,4)=12$ (Theorem 6.33).
Products For $\sigma\tau$ apply $\tau$ first: $1\overset{\tau}{\mapsto}2\overset{\sigma}{\mapsto}5$, $5\mapsto3\mapsto8$, $8\mapsto8\mapsto9$, $9\mapsto6$, $6\mapsto3$, $3\mapsto4\mapsto7$, $7\mapsto1$; and $2\mapsto1\mapsto4$, $4\mapsto5\mapsto2$. Hence $$\sigma\tau=(1\ 5\ 8\ 9\ 6\ 3\ 7)(2\ 4).$$ Similarly $$\tau\sigma=(1\ 5)(2\ 3\ 8\ 9\ 6\ 4\ 7).$$ Both have order $14$ and they are different: $S_9$ is not abelian. (They have the same cycle type, which is no accident: $\tau\sigma=\tau(\sigma\tau)\tau^{-1}$ is a conjugate of $\sigma\tau$, see Theorem 6.37.)
Inverse Reverse every cycle: $\sigma^{-1}=(7\ 4\ 1)(5\ 2)(6\ 9\ 8\ 3)=(1\ 7\ 4)(2\ 5)(3\ 6\ 9\ 8)$.
A high power Since $o(\sigma)=12$ and $2026=12\cdot168+10$, $\sigma^{2026}=\sigma^{10}$. Power each disjoint cycle separately: $(1\ 4\ 7)^{10}=(1\ 4\ 7)^{1}$, $(2\ 5)^{10}=e$, and $(3\ 8\ 9\ 6)^{10}=(3\ 8\ 9\ 6)^{2}=(3\ 9)(8\ 6)$, which splits into $\gcd(2,4)=2$ cycles of length $2$ (Theorem 6.33(c)). So $$\sigma^{2026}=(1\ 4\ 7)(3\ 9)(6\ 8).$$
✏️ Example 2 — Which orders occur, and how often?
(a) Find the largest order of an element of $S_7$, $S_8$ and $S_{10}$. (b) What is the least $n$ for which $S_n$ has an element of order $30$? Of order $60$? (c) How many elements of order $6$ are there in $S_6$? (d) How many elements of order $2$ are there in $S_5$?
Principle By Theorem 6.33 the possible orders in $S_n$ are the numbers $\operatorname{lcm}(k_1,\dots,k_r)$ with $k_1+\cdots+k_r=n$. To make the lcm large, use pairwise coprime parts (repeating a part or using parts with a common factor wastes symbols).
(a) $S_7$: $4+3$ gives $12$ (the alternatives $5+2\to10$, $7\to7$, $3+2+2$ or $6+1\to6$ are smaller), so the maximum is $12$. $S_8$: $5+3$ gives $15$. $S_{10}$: $5+3+2$ gives $30$. (For comparison, $S_9$: $5+4\to20$.)
(b) An element of order $30$ needs cycles whose lengths have lcm $30$, so lengths divisible by $2$, by $3$ and by $5$ must occur; the cheapest way is $2+3+5=10$ symbols (a single $30$-cycle or a $6$-cycle with a $5$-cycle costs more). So $n=10$. For order $60=4\cdot3\cdot5$ the cheapest is $4+3+5=12$, so $n=12$.
(c) In $S_6$ the order is $6$ exactly for the types $(6)$ and $(3,2,1)$. By Theorem 6.34: type $(6)$ gives $6!/6=120$; type $(3,2,1)$ gives $6!/(3\cdot2\cdot1)=120$. Total $240$.
(d) Order $2$ means type $(2,1,1,1)$ or $(2,2,1)$: $\dfrac{5!}{2\cdot3!}=10$ transpositions and $\dfrac{5!}{2^2\cdot2!}=15$ double transpositions. Total $25$.
Interactive 1 — Hunting the Cycles of a Permutation

Each point $i$ has an arrow to $\sigma(i)$. The tracer starts at the smallest point not yet used and follows arrows until it returns — that closes a cycle (Theorem 6.32). Watch the cycle notation, cycle type, order $=\operatorname{lcm}$ and sign being built. Then press × transposition: $\sigma$ is replaced by $\sigma\,(a\ b)$ for a random pair, and the number of cycles changes by exactly one — a split if $a,b$ were in the same cycle, a merge otherwise — so the sign flips (Theorem 6.35).

cycle notation—
cycle type—
order—
sign—
size of its class in Sₙ—

Transpositions, Parity and the Alternating Group

📘 Definition 6.20 — Even and odd permutations
A permutation is even if it is a product of an even number of transpositions and odd if it is a product of an odd number of transpositions. For $\sigma\in S_n$ let $c(\sigma)$ be the number of cycles of $\sigma$, fixed points included (so $c(e)=n$), and define the sign $$\operatorname{sgn}(\sigma)=(-1)^{\,n-c(\sigma)}.$$
📐 Theorem 6.35 — Parity is well defined

Let $n\ge2$.

  1. Every $\sigma\in S_n$ is a product of transpositions; explicitly $$(a_1\ a_2\ \cdots\ a_k)=(a_1\ a_k)\cdots(a_1\ a_3)(a_1\ a_2),$$ a product of $k-1$ transpositions.
  2. If $\tau=(a\ b)$ is a transposition then $c(\sigma\tau)=c(\sigma)+1$ when $a,b$ lie in the same cycle of $\sigma$, and $c(\sigma\tau)=c(\sigma)-1$ when they lie in different cycles.
  3. If $\sigma=\tau_1\tau_2\cdots\tau_m$ with transpositions $\tau_i$, then $(-1)^m=\operatorname{sgn}(\sigma)$. Hence no permutation is both even and odd, and $\operatorname{sgn}:S_n\to\{1,-1\}$ is a surjective homomorphism.
  4. A $k$-cycle has sign $(-1)^{k-1}$. A permutation is even iff it has an even number of cycles of even length.

Proof. (1) Read the product from the right. $a_1$ goes to $a_2$ under $(a_1\ a_2)$ and no later factor moves $a_2$. For $2\le i\le k-1$, $a_i$ is fixed by the factors before $(a_1\ a_i)$, which sends it to $a_1$, and then $(a_1\ a_{i+1})$ sends $a_1$ to $a_{i+1}$, which no later factor moves. Finally $a_k$ is fixed until the last factor $(a_1\ a_k)$ sends it to $a_1$. Points outside $\{a_1,\dots,a_k\}$ are fixed. Combine with Theorem 6.32 ($e=(1\ 2)(1\ 2)$).

(2) Only the cycles of $\sigma$ through $a$ and $b$ are affected. If they are in one cycle, write it as $(a\ x_1\ \cdots\ x_r\ b\ y_1\ \cdots\ y_s)$ ($r,s\ge0$). Then $\sigma\tau$ sends $a\mapsto\sigma(b)=y_1\mapsto\cdots\mapsto y_s\mapsto a$ and $b\mapsto\sigma(a)=x_1\mapsto\cdots\mapsto x_r\mapsto b$: the cycle splits into $(a\ y_1\ \cdots\ y_s)(b\ x_1\ \cdots\ x_r)$, one more cycle. If they are in different cycles $(a\ x_1\ \cdots\ x_r)(b\ y_1\ \cdots\ y_s)$, then $\sigma\tau$ sends $a\mapsto y_1\mapsto\cdots\mapsto y_s\mapsto b$ and then $b\mapsto x_1\mapsto\cdots\mapsto x_r\mapsto a$: the two cycles merge into one.

(3) Build $\sigma$ from $e$ by multiplying on the right by $\tau_1,\tau_2,\dots,\tau_m$ in turn. We start with $c(e)=n$ and by (2) each step changes $c$ by $\pm1$, so $c(\sigma)\equiv n-m\pmod 2$, i.e. $(-1)^m=(-1)^{n-c(\sigma)}=\operatorname{sgn}(\sigma)$. Thus the parity of $m$ depends only on $\sigma$. If $\sigma$ is a product of $m$ transpositions and $\rho$ of $l$, then $\sigma\rho$ is a product of $m+l$, so $\operatorname{sgn}(\sigma\rho)=(-1)^{m+l}=\operatorname{sgn}(\sigma)\operatorname{sgn}(\rho)$; and $\operatorname{sgn}(1\ 2)=-1$, so sgn is onto. (4) follows from (1) and multiplicativity: a cycle of length $k$ contributes $(-1)^{k-1}$, which is $-1$ exactly when $k$ is even. ∎

📘 Definition 6.21 — The alternating group
The alternating group $A_n$ is the set of even permutations in $S_n$, i.e. the kernel of $\operatorname{sgn}:S_n\to\{\pm1\}$.
📐 Theorem 6.36 — Properties of $A_n$
For $n\ge2$, $A_n\trianglelefteq S_n$, $[S_n:A_n]=2$ and $|A_n|=n!/2$. For $n\ge3$, $A_n$ is generated by the $3$-cycles.

Proof. $A_n$ is the kernel of a homomorphism, hence normal, and by the first isomorphism theorem (§6.2) $S_n/A_n\cong\operatorname{sgn}(S_n)=\{\pm1\}$, so the index is $2$. A $3$-cycle is even ($(a\ b\ c)=(a\ c)(a\ b)$), so the $3$-cycles generate a subgroup of $A_n$. Conversely an even permutation is a product of an even number of transpositions; group them in pairs. A pair is either $(a\ b)(a\ b)=e$, or $(a\ b)(a\ c)=(a\ c\ b)$ (one common point), or $(a\ b)(c\ d)=(a\ c\ b)(a\ c\ d)$ (disjoint; multiply out to check). So every even permutation is a product of $3$-cycles. ∎

✏️ Example 3 — Parity and the orders available in $A_n$
(a) Is the permutation $\sigma$ of Example 1 even or odd? (b) Find all orders of elements of $A_6$. Does $A_6$ have an element of order $6$? (c) Does $A_7$ have elements of order $6$ or $10$? (d) Does $A_5$ have an element of order $4$?
(a) Even $\sigma=(1\ 4\ 7)(2\ 5)(3\ 8\ 9\ 6)$ has $c(\sigma)=3$ cycles on $9$ points, so $\operatorname{sgn}\sigma=(-1)^{9-3}=+1$. Equivalently: it has two cycles of even length (the $2$-cycle and the $4$-cycle).
(b) Types in $A_6$ List the partitions of $6$ with an even number of even parts: $(1^6)$, $(2,2,1,1)$, $(3,1,1,1)$, $(3,3)$, $(4,2)$, $(5,1)$. Their orders are $1,2,3,3,4,5$. The order-$6$ types $(6)$ and $(3,2,1)$ have one even part each, so they are odd. Hence $A_6$ has elements of orders $1,2,3,4,5$ only — no element of order $6$, although $6$ divides $|A_6|=360$.
(c) Order $6$: type $(3,2,2)$ uses $7$ symbols and has two even parts, so it lies in $A_7$ — yes. Order $10$ needs a $5$-cycle and a cycle of even length; in $S_7$ the only such type is $(5,2)$, which is odd. So $A_7$ has no element of order $10$, while $S_7$ has $504$ of them.
(d) No Order $4$ in $S_5$ means type $(4,1)$, a $4$-cycle, which is odd. The orders in $A_5$ are $1,2,3,5$.

Conjugacy in $S_n$ and $A_n$

📘 Definition 6.22 — Conjugacy classes and centralisers
Elements $a,b$ of a group $G$ are conjugate if $b=gag^{-1}$ for some $g\in G$. Conjugacy is an equivalence relation; its classes are the conjugacy classes $\operatorname{cl}(a)=\{gag^{-1}:g\in G\}$. The centraliser of $a$ is the subgroup $C_G(a)=\{g\in G: ga=ag\}$. The centre $Z(G)$ consists of the elements whose class is a single point.
📐 Theorem 6.37 — Conjugation relabels the cycles
(a) For $\tau\in S_n$ and a cycle, $$\tau\,(a_1\ a_2\ \cdots\ a_k)\,\tau^{-1}=(\tau(a_1)\ \cdots\ \tau(a_k)).$$ Consequently $\tau\sigma\tau^{-1}$ is obtained by applying $\tau$ to every entry of the cycle notation of $\sigma$. (b) Two permutations are conjugate in $S_n$ if and only if they have the same cycle type. (c) The number of conjugacy classes of $S_n$ equals the number $p(n)$ of partitions of $n$.

Proof. (a) Let $\gamma=(a_1\ \cdots\ a_k)$. For a point $\tau(a_i)$: $\tau\gamma\tau^{-1}(\tau(a_i))=\tau(\gamma(a_i))=\tau(a_{i+1})$ (indices mod $k$). For a point $x$ not of the form $\tau(a_i)$, $\tau^{-1}(x)\notin\{a_1,\dots,a_k\}$ is fixed by $\gamma$, so $\tau\gamma\tau^{-1}(x)=x$. For a product of cycles use $\tau(\gamma_1\cdots\gamma_r)\tau^{-1}=(\tau\gamma_1\tau^{-1})\cdots(\tau\gamma_r\tau^{-1})$; disjoint cycles stay disjoint because $\tau$ is injective.

(b) By (a), conjugation preserves cycle lengths. Conversely, if $\sigma,\sigma'$ have the same type, write their cycle decompositions — including $1$-cycles — one above the other with cycles of equal length aligned, and let $\tau$ send each symbol of the top row to the symbol below it. Each of $1,\dots,n$ occurs exactly once in each row, so $\tau$ is a bijection, and by (a) $\tau\sigma\tau^{-1}=\sigma'$. (c) Cycle types are exactly the partitions of $n$, and each partition occurs. ∎

📐 Theorem 6.38 — Generators of $S_n$
For $n\ge2$, $S_n$ is generated by each of the following sets: (a) all transpositions; (b) $(1\ 2),(1\ 3),\dots,(1\ n)$; (c) the adjacent transpositions $(1\ 2),(2\ 3),\dots,(n-1\ \ n)$; (d) the two elements $(1\ 2)$ and $(1\ 2\ \cdots\ n)$.

Proof. (a) is Theorem 6.35(1). (b) For distinct $a,b\ne1$, $(a\ b)=(1\ a)(1\ b)(1\ a)$ by Theorem 6.37(a) (conjugating $(1\ b)$ by $(1\ a)$ replaces $1$ by $a$). (c) Conjugating $(1\ k)$ by $(k\ \ k{+}1)$ gives $(1\ \ k{+}1)$, so by induction all $(1\ k)$ lie in the subgroup generated by the adjacent transpositions; apply (b). (d) With $\rho=(1\ 2\ \cdots\ n)$, Theorem 6.37(a) gives $\rho^{k}(1\ 2)\rho^{-k}=(\rho^k(1)\ \rho^k(2))=(k{+}1\ \ k{+}2)$ for $0\le k\le n-2$; apply (c). ∎

📐 Theorem 6.39 — Class sizes and centralisers in $S_n$
Let $\sigma\in S_n$ have cycle type $1^{m_1}2^{m_2}\cdots n^{m_n}$. Then $|C_{S_n}(\sigma)|=z=\prod_k k^{m_k}m_k!$, and the conjugacy class of $\sigma$ has $n!/z$ elements. More generally, in any finite group $|\operatorname{cl}(a)|=[G:C_G(a)]$, which divides $|G|$.

Proof. In any group, $gag^{-1}=hah^{-1}$ $\iff$ $h^{-1}g\,a=a\,h^{-1}g$ $\iff$ $h^{-1}g\in C_G(a)$ $\iff$ $gC_G(a)=hC_G(a)$. So $gC_G(a)\mapsto gag^{-1}$ is a well-defined bijection from the left cosets of $C_G(a)$ onto $\operatorname{cl}(a)$, and $|\operatorname{cl}(a)|=[G:C_G(a)]$, a divisor of $|G|$ by Lagrange's theorem (§6.1). In $S_n$ the class of $\sigma$ is the set of all permutations of its type (Theorem 6.37(b)), which has $n!/z$ elements (Theorem 6.34); hence $|C_{S_n}(\sigma)|=n!/(n!/z)=z$. ∎

📐 Theorem 6.40 — Splitting of classes in $A_n$
Let $\sigma\in A_n$, $n\ge2$. Either the $S_n$-class of $\sigma$ is a single conjugacy class of $A_n$, or it splits into two $A_n$-classes of equal size. It splits if and only if $C_{S_n}(\sigma)\subseteq A_n$, and this happens if and only if the cycle type of $\sigma$ (fixed points counted as $1$-cycles) consists of distinct odd lengths.

Proof. By Theorem 6.39 applied in $A_n$, $|\operatorname{cl}_{A_n}(\sigma)|=[A_n:C_{A_n}(\sigma)]$, and $C_{A_n}(\sigma)=C_{S_n}(\sigma)\cap A_n$ has index $1$ or $2$ in $C_{S_n}(\sigma)$ (it is the kernel of sgn restricted to $C_{S_n}(\sigma)$). If $C_{S_n}(\sigma)$ contains an odd permutation, the index is $2$ and $|\operatorname{cl}_{A_n}(\sigma)|=\dfrac{n!/2}{z/2}=\dfrac{n!}{z}$: the whole $S_n$-class. If $C_{S_n}(\sigma)\subseteq A_n$, then $|\operatorname{cl}_{A_n}(\sigma)|=\dfrac{n!/2}{z}$, half the $S_n$-class; and for an odd $\rho$ the class of $\rho\sigma\rho^{-1}$ in $A_n$ is the other half (the cosets $A_n$ and $\rho A_n$ conjugate $\sigma$ onto the two halves).

Now the criterion. If $\sigma$ has a cycle $\gamma$ of even length, $\gamma$ commutes with $\sigma$ and is odd. If $\sigma$ has two cycles of the same odd length $k$, say $(a_1\ \cdots\ a_k)$ and $(b_1\ \cdots\ b_k)$ (possibly two fixed points, $k=1$), then $\pi=(a_1\ b_1)(a_2\ b_2)\cdots(a_k\ b_k)$ swaps them, so $\pi\sigma\pi^{-1}=\sigma$ by Theorem 6.37(a), and $\pi$ is odd since $k$ is odd. Conversely, suppose the cycle lengths are distinct and odd, and $\rho\in C_{S_n}(\sigma)$. Then $\rho\sigma\rho^{-1}=\sigma$ is obtained by relabelling each cycle by $\rho$; as the lengths are distinct, $\rho$ maps each cycle $\gamma=(a_1\ \cdots\ a_k)$ onto itself, with $(\rho(a_1)\ \cdots\ \rho(a_k))=\gamma$, so $\rho$ acts on its support as a power of $\gamma$. Thus $\rho$ is a product of powers of the cycles of $\sigma$, all of odd length, hence even. ∎

Classes of $S_4$$24=1+3+6+6+8$ (types $1^4$, $2^2$, $2\,1^2$, $4$, $3\,1$).
Classes of $A_4$$12=1+3+4+4$: the eight $3$-cycles (type $(3,1)$, distinct odd parts) split.
Classes of $S_5$$120=1+10+15+20+20+24+30$.
Classes of $A_5$$60=1+15+20+12+12$: only the $5$-cycles split; the $3$-cycles (type $(3,1,1)$, repeated $1$) do not.
✏️ Example 4 — Conjugacy in $S_4$ and $S_5$
(a) Tabulate the conjugacy classes of $S_4$ with their sizes and centraliser orders. (b) Find $\tau\in S_5$ with $\tau\,(1\ 2\ 3)(4\ 5)\,\tau^{-1}=(2\ 4\ 5)(1\ 3)$. (c) Find $C_{S_4}((1\ 2\ 3\ 4))$. (d) Are $\sigma=(1\ 2\ 3\ 4\ 5)$ and $\sigma^2$ conjugate in $S_5$? In $A_5$?
(a) By Theorems 6.34 and 6.39:
typerepresentativeclass size $24/z$$|C(\sigma)|=z$
$1^4$$e$$1$$24$
$2\,1^2$$(1\ 2)$$6$$2\cdot2!=4$
$2^2$$(1\ 2)(3\ 4)$$3$$2^2\cdot2!=8$
$3\,1$$(1\ 2\ 3)$$8$$3$
$4$$(1\ 2\ 3\ 4)$$6$$4$
The sizes add to $24$ and each divides $24$.
(b) Same type $(3,2)$, so a $\tau$ exists. Align: top row $(1\ 2\ 3)(4\ 5)$, bottom row $(2\ 4\ 5)(1\ 3)$, and read off $\tau$: $1\mapsto2$, $2\mapsto4$, $3\mapsto5$, $4\mapsto1$, $5\mapsto3$, i.e. $\tau=(1\ 2\ 4)(3\ 5)$. Check by Theorem 6.37(a): $\tau(1\ 2\ 3)\tau^{-1}=(2\ 4\ 5)$ and $\tau(4\ 5)\tau^{-1}=(1\ 3)$. (Any $\tau\rho$ with $\rho\in C_{S_5}((1\ 2\ 3)(4\ 5))$, a group of order $6$, also works.)
(c) $|C_{S_4}((1\ 2\ 3\ 4))|=4$ by the table, and $\langle(1\ 2\ 3\ 4)\rangle$ is a subgroup of the centraliser of order $4$. So $C_{S_4}((1\ 2\ 3\ 4))=\{e,(1\ 2\ 3\ 4),(1\ 3)(2\ 4),(1\ 4\ 3\ 2)\}$.
(d) $\sigma^2=(1\ 3\ 5\ 2\ 4)$ is again a $5$-cycle (Theorem 6.33(c)), so the two are conjugate in $S_5$, e.g. by $\tau=(2\ 3\ 5\ 4)$ ($1\mapsto1$, $2\mapsto3$, $3\mapsto5$, $4\mapsto2$, $5\mapsto4$). All conjugating elements form the coset $\tau\,C_{S_5}(\sigma)=\tau\langle\sigma\rangle$; $\tau$ is a $4$-cycle (odd) and $\langle\sigma\rangle\subseteq A_5$, so every conjugator is odd. Hence $\sigma$ and $\sigma^2$ are not conjugate in $A_5$ — the two $A_5$-classes of $5$-cycles in Theorem 6.40 are those of $\sigma$ and of $\sigma^2$.

Group Actions: Cayley, Orbit–Stabiliser and Burnside

📘 Definition 6.23 — Group actions, orbits and stabilisers

An action of a group $G$ on a set $X$ is a map $G\times X\to X$, $(g,x)\mapsto g\cdot x$, such that $e\cdot x=x$ and $g\cdot(h\cdot x)=(gh)\cdot x$ for all $g,h\in G$, $x\in X$. For $x\in X$ and $g\in G$:

  • the orbit of $x$ is $G\cdot x=\{g\cdot x:g\in G\}$ and the stabiliser of $x$ is $G_x=\{g\in G:g\cdot x=x\}$;
  • the fixed set of $g$ is $\operatorname{Fix}(g)=\{x\in X:g\cdot x=x\}$, and $X^G=\{x: g\cdot x=x\text{ for all }g\}$ is the set of fixed points of the action;
  • the action is transitive if there is only one orbit, and faithful if only $e$ fixes every point.
📐 Theorem 6.41 — Actions are homomorphisms into $\operatorname{Sym}(X)$
If $G$ acts on $X$, each map $\lambda_g:x\mapsto g\cdot x$ is a bijection of $X$ and $\lambda:G\to\operatorname{Sym}(X)$, $g\mapsto\lambda_g$, is a homomorphism (the permutation representation of the action), with kernel $\bigcap_{x\in X}G_x$. Conversely every homomorphism $\lambda:G\to\operatorname{Sym}(X)$ defines an action $g\cdot x=\lambda(g)(x)$. The action is faithful iff $\lambda$ is injective.

Proof. $\lambda_g\lambda_h(x)=g\cdot(h\cdot x)=(gh)\cdot x=\lambda_{gh}(x)$, and $\lambda_e=\mathrm{id}$, so $\lambda_g\lambda_{g^{-1}}=\lambda_{g^{-1}}\lambda_g=\mathrm{id}$: each $\lambda_g$ is a bijection and $\lambda$ is a homomorphism. Its kernel consists of the $g$ with $g\cdot x=x$ for all $x$. The converse is a direct check of the two axioms, and faithful means trivial kernel. ∎

📐 Theorem 6.42 — Cayley's theorem
Every group $G$ is isomorphic to a subgroup of $\operatorname{Sym}(G)$. In particular every group of finite order $n$ is isomorphic to a subgroup of $S_n$.

Proof. $G$ acts on the set $G$ by left multiplication, $g\cdot x=gx$: indeed $ex=x$ and $g(hx)=(gh)x$. The action is faithful, since $gx=x$ for all $x$ (even for $x=e$ alone) forces $g=e$. By Theorem 6.41, $\lambda:G\to\operatorname{Sym}(G)$ is an injective homomorphism, so $G\cong\lambda(G)\le\operatorname{Sym}(G)$. If $|G|=n$, numbering the elements of $G$ as $1,\dots,n$ identifies $\operatorname{Sym}(G)$ with $S_n$. ∎

The embedding $\lambda$ is the left regular representation. For $g\ne e$, $\lambda_g$ has no fixed point and all its cycles have length $o(g)$ (the cycle through $x$ is $x,gx,g^2x,\dots$), so $\lambda_g$ is a product of $n/o(g)$ disjoint $o(g)$-cycles. For $\mathbb{Z}_4=\{0,1,2,3\}$ the generator $1$ becomes the $4$-cycle $(0\ 1\ 2\ 3)$; for the Klein group $V_4=\{e,a,b,ab\}$ the three non-identity elements become the three double transpositions of $S_4$.

📐 Theorem 6.43 — Orbit–stabiliser theorem
Let $G$ act on $X$. (a) The orbits partition $X$. (b) Each stabiliser $G_x$ is a subgroup of $G$, and $g\,G_x\mapsto g\cdot x$ is a well-defined bijection from the left cosets of $G_x$ onto the orbit $G\cdot x$. Hence, for finite $G$, $$|G\cdot x|=[G:G_x]=\frac{|G|}{|G_x|},$$ so the size of every orbit divides $|G|$. (c) Points in the same orbit have conjugate stabilisers: $G_{g\cdot x}=g\,G_x\,g^{-1}$.

Proof. (a) $x\sim y\iff y=g\cdot x$ for some $g$ is an equivalence relation: $x=e\cdot x$; $y=g\cdot x\Rightarrow x=g^{-1}\cdot y$; $y=g\cdot x$, $z=h\cdot y\Rightarrow z=(hg)\cdot x$. Its classes are the orbits. (b) $e\in G_x$, and if $g,h\in G_x$ then $(gh)\cdot x=g\cdot(h\cdot x)=x$ and $g^{-1}\cdot x=g^{-1}\cdot(g\cdot x)=x$. Next, $g\cdot x=h\cdot x$ $\iff$ $(h^{-1}g)\cdot x=x$ $\iff$ $h^{-1}g\in G_x$ $\iff$ $gG_x=hG_x$; read from left to right this shows the map is well defined, and from right to left that it is injective. It is onto the orbit by definition. (c) $h\in G_{g\cdot x}$ $\iff$ $hg\cdot x=g\cdot x$ $\iff$ $g^{-1}hg\in G_x$ $\iff$ $h\in gG_xg^{-1}$. ∎

Two actions of $G$ on itself are used constantly. Left multiplication (Cayley) is transitive with trivial stabilisers. Conjugation, $g\cdot x=gxg^{-1}$, has the conjugacy classes as orbits and the centralisers as stabilisers, so Theorem 6.43 contains Theorem 6.39. A third: $G$ acts on the set $G/H$ of left cosets of a subgroup $H$ by $g\cdot xH=gxH$, transitively, with $G_{xH}=xHx^{-1}$.

📐 Theorem 6.44 — The action on cosets; subgroups of small index
Let $H\le G$ with $[G:H]=n$ finite. Then there is a homomorphism $G\to S_n$ whose kernel $K=\bigcap_{x\in G}xHx^{-1}$ is a normal subgroup of $G$ contained in $H$, and $[G:K]$ divides $n!$. Consequently: (a) if $G$ is finite and $|G|\nmid n!$, then $G$ has a normal subgroup $K\ne\{e\}$ inside $H$; (b) if $G$ is finite and $p$ is the smallest prime dividing $|G|$, every subgroup of index $p$ is normal. In particular subgroups of index $2$ are normal.

Proof. Apply Theorem 6.41 to the action on the $n$ cosets: the kernel is $\bigcap_x G_{xH}=\bigcap_x xHx^{-1}\subseteq H$ (take $x=e$), and $G/K$ is isomorphic to a subgroup of $S_n$, so $[G:K]\mid n!$ by Lagrange. (a) If $K=\{e\}$ then $|G|=[G:K]$ divides $n!$. (b) Let $[G:H]=p$. Then $[G:K]=[G:H][H:K]=p\,[H:K]$ divides $p!$, so $[H:K]$ divides $(p-1)!$. But $[H:K]$ divides $|G|$, all of whose prime factors are $\ge p$, while all prime factors of $(p-1)!$ are $\lt p$. Hence $[H:K]=1$, $H=K$ is normal. ∎

✏️ Example 5 — Orbit–stabiliser at work
(a) Show that $Q_8$ is not isomorphic to a subgroup of $S_n$ for any $n\le7$, so Cayley's bound $n=|G|$ is sharp for $Q_8$. (b) Find the order of the group $R$ of rotations of a cube, and show that $R\cong S_4$.
(a) Subgroups of $Q_8$ The only element of order $2$ in $Q_8$ is $-1$, and the elements $\pm i,\pm j,\pm k$ of order $4$ all square to $-1$. So every subgroup $H\ne\{1\}$ contains $-1$: it contains some $h\ne1$, and either $h=-1$ or $h^2=-1$.
(a) The action Suppose $\phi:Q_8\to S_n$ is an injective homomorphism with $n\le7$; it is a faithful action of $Q_8$ on $\{1,\dots,n\}$. Every orbit has size dividing $8$ (Theorem 6.43) and at most $7$, so size $1$, $2$ or $4$, and then every stabiliser has order $8$, $4$ or $2$ — it is non-trivial and so contains $-1$. Thus $-1$ fixes every point and $\phi(-1)=e$, contradicting injectivity. Hence the smallest symmetric group containing a copy of $Q_8$ is $S_8$, and Cayley's theorem cannot be improved for $Q_8$. (For most groups it can: $S_n$ itself has order $n!$ but sits in $S_n$.)
(b) Counting $R$ acts transitively on the $6$ faces, and the stabiliser of a face consists of the $4$ rotations about the axis through its centre. So $|R|=6\cdot4=24$. Checks: $8$ vertices with stabilisers of order $3$, $12$ edges with stabilisers of order $2$ — again $24$.
(b) $R\cong S_4$ $R$ permutes the $4$ long diagonals (lines through opposite vertices), giving a homomorphism $\psi:R\to S_4$. Let $g\in\ker\psi$. If $g$ fixes some vertex $v$, it is a rotation about the diagonal through $v$, and the non-trivial rotations about that diagonal (by $\pm120^\circ$) permute the other three diagonals cyclically; so $g=e$. If $g$ fixes no vertex, it sends every vertex $v$ to $-v$ (it preserves each diagonal), and since the vertices span $\mathbb{R}^3$, $g=-I$, which has determinant $-1$ and is not a rotation. So $\psi$ is injective, and $|R|=24=|S_4|$ makes it an isomorphism.
📐 Theorem 6.45 — Burnside's lemma (the orbit-counting lemma)
Let a finite group $G$ act on a finite set $X$. The number of orbits is the average number of fixed points: $$\#\{\text{orbits}\}=\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|.$$

Proof. Count the set $F=\{(g,x)\in G\times X: g\cdot x=x\}$ in two ways. Summing over $g$ gives $|F|=\sum_g|\operatorname{Fix}(g)|$. Summing over $x$ gives $|F|=\sum_x|G_x|=\sum_x\dfrac{|G|}{|G\cdot x|}$ by Theorem 6.43. Group the last sum by orbits: an orbit $\mathcal{O}$ contributes $|\mathcal{O}|\cdot\dfrac{|G|}{|\mathcal{O}|}=|G|$. Hence $|F|=|G|\cdot\#\{\text{orbits}\}$. ∎

🧭 Problem-solving strategy — counting colourings up to symmetry
  1. Identify the symmetry group $G$ and the set it permutes (beads, faces, edges, vertices). Let $X$ be the set of all colourings with $k$ colours, $|X|=k^{(\text{number of positions})}$.
  2. For each $g\in G$ find the number $c(g)$ of cycles of $g$ on the positions (fixed positions count as cycles). A colouring is fixed by $g$ iff it is constant on each cycle, so $|\operatorname{Fix}(g)|=k^{c(g)}$.
  3. Conjugate elements have the same cycle structure, so work class by class: $\#\text{orbits}=\dfrac1{|G|}\sum_{\text{classes}}(\text{class size})\cdot k^{c(g)}$.
  4. Check: the answer must be an integer, and for $k=1$ it must be $1$.
✏️ Example 6 — Necklaces and coloured cubes
(a) How many different necklaces of $6$ beads can be made with beads of $2$ colours, if two necklaces are the same when one is a rotation of the other? (b) The same if reflections (turning the necklace over) are also allowed. (c) In how many essentially different ways can the faces of a cube be coloured with $3$ colours, up to rotation?
(a) Rotations $G=\mathbb{Z}_6$ acts on the $6$ positions; the rotation by $j$ steps has $\gcd(j,6)$ cycles (Theorem 6.33(c)). The values of $c$ for $j=0,1,\dots,5$ are $6,1,2,3,2,1$, so $$\#=\frac{2^6+2^1+2^2+2^3+2^2+2^1}{6}=\frac{84}{6}=14.$$
(b) Rotations and reflections $G=D_6$, of order $12$. The $3$ reflections through two opposite beads have $2$ fixed positions and two $2$-cycles: $c=4$. The $3$ reflections through midpoints of opposite gaps have three $2$-cycles: $c=3$. So $$\#=\frac{84+3\cdot2^4+3\cdot2^3}{12}=\frac{84+48+24}{12}=\frac{156}{12}=13.$$ (Exactly one pair of the $14$ rotation-classes is merged by turning over: $110100$ and its mirror image $001011$, read cyclically.)
(c) The cube The $24$ rotations (Example 5) fall into five types acting on the $6$ faces: the identity ($c=6$); $6$ quarter-turns about face axes ($2$ fixed faces and a $4$-cycle, $c=3$); $3$ half-turns about face axes ($c=4$); $8$ rotations by $\pm120^\circ$ about vertex diagonals (two $3$-cycles, $c=2$); $6$ half-turns about axes through midpoints of opposite edges (three $2$-cycles, $c=3$). So $$\#=\frac{3^6+6\cdot3^3+3\cdot3^4+8\cdot3^2+6\cdot3^3}{24}=\frac{729+162+243+72+162}{24}=\frac{1368}{24}=57.$$
Check With $k=1$: $(1+6+3+8+6)/24=1$. With $k=2$ the same formula gives $(64+48+48+32+48)/24=10$.
Interactive 2 — Burnside's Lemma, One Symmetry at a Time

The animation runs through every element $g$ of the rotation group $\mathbb{Z}_n$ (or the dihedral group $D_n$) of an $n$-bead necklace. Beads in the same cycle of $g$ get the same colour; a colouring is fixed by $g$ exactly when it is constant on each cycle, so $|\operatorname{Fix}(g)|=k^{c(g)}$. The table adds up the fixed points; dividing by $|G|$ gives the number of different necklaces (Theorem 6.45).

symmetry g—
cycles c(g)—
|Fix(g)| = kᶜ—
running sum—
necklaces = sum / |G|—

The Class Equation and $p$-Groups

📐 Theorem 6.46 — The class equation
Let $G$ be a finite group and let $a_1,\dots,a_r$ be representatives of the conjugacy classes of $G$ that have more than one element. Then $$|G|=|Z(G)|+\sum_{i=1}^{r}[G:C_G(a_i)],$$ where each $[G:C_G(a_i)]$ is a divisor of $|G|$ greater than $1$.

Proof. The conjugacy classes partition $G$ (they are the orbits of the conjugation action, Theorem 6.43). A class $\operatorname{cl}(a)$ is the single point $\{a\}$ iff $gag^{-1}=a$ for all $g$, i.e. iff $a\in Z(G)$; these one-point classes together contribute $|Z(G)|$. Every other class has $|\operatorname{cl}(a_i)|=[G:C_G(a_i)]\gt1$ elements (Theorem 6.39), a divisor of $|G|$. ∎

📘 Definition 6.24 — $p$-groups
Let $p$ be a prime. A finite group is a $p$-group if its order is a power of $p$, $|G|=p^n$ with $n\ge0$. (Then the order of every element is a power of $p$; the converse — that a finite group in which every element has $p$-power order is a $p$-group — follows from Cauchy's theorem in §6.4.)
📐 Theorem 6.47 — Fixed points of $p$-groups; the centre of a $p$-group
(a) If a $p$-group $P$ acts on a finite set $X$, then $|X|\equiv|X^P|\pmod p$. In particular, if $p\nmid|X|$ the action has a fixed point. (b) If $P\ne\{e\}$ is a $p$-group, then $Z(P)\ne\{e\}$; in fact $p$ divides $|Z(P)|$.

Proof. (a) $X$ is the disjoint union of its orbits. An orbit has size $[P:P_x]$, a power of $p$; it has size $1$ exactly when its point is fixed by all of $P$. So $|X|=|X^P|+S$, where $S$ is a sum of positive powers of $p$, and $|X|\equiv|X^P|\pmod p$. (b) Let $P$ act on $X=P$ by conjugation; the fixed points are the elements of $Z(P)$. By (a), $|Z(P)|\equiv|P|\equiv0\pmod p$, and $|Z(P)|\ge1$ because $e\in Z(P)$. Hence $|Z(P)|\ge p$. (In terms of the class equation: every term $[P:C_P(a_i)]$ is a positive power of $p$, so $p$ divides $|P|-\sum_i[P:C_P(a_i)]=|Z(P)|$.) ∎

📐 Theorem 6.48 — If $G/Z(G)$ is cyclic, $G$ is abelian
For any group $G$, if the quotient group $G/Z(G)$ is cyclic then $G$ is abelian (and so $G/Z(G)$ is trivial). Consequently $[G:Z(G)]$ is never a prime.

Proof. Write $Z=Z(G)$ and $G/Z=\langle gZ\rangle$. Every element of $G$ lies in some coset $g^iZ$, so it has the form $g^iz$ with $z\in Z$. For $x=g^iz$ and $y=g^jw$ ($z,w\in Z$): $xy=g^ig^jzw=g^{i+j}zw$ and $yx=g^jg^iwz=g^{i+j}zw$, using that $z,w$ commute with everything. So $G$ is abelian, $Z=G$, and $G/Z$ is trivial. A group of prime order is cyclic and non-trivial, so it cannot be $G/Z(G)$. ∎

📐 Theorem 6.49 — Groups of order $p^2$ are abelian
If $|G|=p^2$ with $p$ prime, then $G$ is abelian, and $G\cong\mathbb{Z}_{p^2}$ or $G\cong\mathbb{Z}_p\times\mathbb{Z}_p$. These two are not isomorphic, so there are exactly two groups of order $p^2$ up to isomorphism.

Proof. By Theorem 6.47, $|Z(G)|\in\{p,p^2\}$. If $|Z(G)|=p$, then $G/Z(G)$ has order $p$, hence is cyclic, and Theorem 6.48 gives $Z(G)=G$ — a contradiction. So $Z(G)=G$: $G$ is abelian. If $G$ has an element of order $p^2$ it is cyclic, $G\cong\mathbb{Z}_{p^2}$. Otherwise every $a\ne e$ has order $p$. Choose $a\ne e$ and $b\notin\langle a\rangle$. Then $\langle a\rangle\cap\langle b\rangle$ is a proper subgroup of the group $\langle b\rangle$ of prime order, so it is $\{e\}$. The map $\phi:\mathbb{Z}_p\times\mathbb{Z}_p\to G$, $(i,j)\mapsto a^ib^j$, is a homomorphism because $G$ is abelian; it is injective because $a^ib^j=e$ gives $a^i=b^{-j}\in\langle a\rangle\cap\langle b\rangle=\{e\}$, so $p\mid i$ and $p\mid j$; and both groups have $p^2$ elements, so $\phi$ is an isomorphism. Finally $\mathbb{Z}_p\times\mathbb{Z}_p$ has no element of order $p^2$, so it is not cyclic. ∎

📐 Theorem 6.50 — $p$-groups have normal subgroups of every possible order
If $|G|=p^n$, then for each $k=0,1,\dots,n$ the group $G$ has a normal subgroup of order $p^k$.

Proof. Induction on $n$; the cases $n\le1$ are clear. Let $n\ge2$ and $1\le k\le n$. By Theorem 6.47, $Z(G)\ne\{e\}$; pick $z\ne e$ in $Z(G)$, of order $p^s$ with $s\ge1$; then $c=z^{p^{s-1}}$ is central of order $p$, and $N=\langle c\rangle$ is normal (every subgroup of the centre is normal). The quotient $G/N$ has order $p^{n-1}$, so by induction it has a normal subgroup $\bar M$ of order $p^{k-1}$. By the correspondence theorem (§6.2), $\bar M=M/N$ for a normal subgroup $M$ of $G$ containing $N$, and $|M|=|N|\,|\bar M|=p^k$. ∎

There is no general converse of Lagrange's theorem — $A_4$, of order $12$, has no subgroup of order $6$ (§6.4) — but Theorem 6.50 is a converse for $p$-groups, and in §6.4 the Sylow theorems extend it to the prime-power divisors of any finite group.

✏️ Example 7 — Which of these are class equations?
Decide, with proof, whether each of the following can be the class equation of a finite group (the first term being $|Z(G)|$ written as a sum of $1$s): (a) $8=1+1+2+2+2$; (b) $10=1+2+2+5$; (c) $6=1+1+1+3$; (d) $10=1+4+5$; (e) $9=1+1+1+3+3$; (f) $12=1+3+4+4$.
(a) Yes $D_4=\langle r,s\rangle$ (symmetries of a square): centre $\{e,r^2\}$, and the classes $\{r,r^3\}$, $\{s,sr^2\}$, $\{sr,sr^3\}$. ($Q_8$ has the same class equation: centre $\{\pm1\}$, classes $\{\pm i\},\{\pm j\},\{\pm k\}$.)
(b) Yes $D_5$: the centre is trivial ($n=5$ is odd), the rotations fall into the classes $\{r,r^4\}$ and $\{r^2,r^3\}$, and all five reflections are conjugate.
(c) No All the sizes divide $6$, so a subtler argument is needed. Here $|Z(G)|=3$ and $G/Z(G)$ would have order $2$, hence be cyclic; by Theorem 6.48, $G$ would be abelian, and then every class has one element — there is no class of size $3$.
(d) No A class has $[G:C_G(a)]$ elements, a divisor of $|G|$; but $4\nmid10$.
(e) No A group of order $9=3^2$ is abelian (Theorem 6.49), so its class equation is $9=1+1+\cdots+1$. (Again every size divides $9$; the arithmetic test alone does not decide.)
(f) Yes $A_4$: the double transpositions form a class of size $3$ and the eight $3$-cycles split into two classes of size $4$ (Theorem 6.40); the centre is trivial.
⚠️ Counterexamples and pitfalls
  1. Conventions change products. Right to left, $(1\ 2\ 3)(2\ 3\ 4)=(1\ 2)(3\ 4)$; left to right the same symbols give $(1\ 3)(2\ 4)$. Fix the convention before computing (and in an exam, check which one the options use: both answers often appear).
  2. The lcm rule needs disjoint cycles. $(1\ 2)(2\ 3)=(1\ 2\ 3)$ has order $3$, not $\operatorname{lcm}(2,2)=2$. Always decompose into disjoint cycles first.
  3. A $k$-cycle has sign $(-1)^{k-1}$. Even-length cycles are odd permutations: a $4$-cycle is odd, a $3$-cycle and a $5$-cycle are even.
  4. Divisibility does not give elements. $6$ divides $|A_6|=360$ but $A_6$ has no element of order $6$; $4$ divides $|A_5|=60$ but $A_5$ has no element of order $4$.
  5. Same cycle type is not enough in $A_n$. $(1\ 2\ 3\ 4\ 5)$ and $(1\ 3\ 5\ 2\ 4)$ are conjugate in $S_5$ but not in $A_5$; in $A_4$, $(1\ 2\ 3)$ and $(1\ 3\ 2)$ are not conjugate.
  6. Splitting needs distinct odd parts, fixed points included. In $A_5$ the $3$-cycles do not split (type $(3,1,1)$ repeats the part $1$), while in $A_4$ they do (type $(3,1)$).
  7. Orbits can have different sizes. Only their sizes divide $|G|$. Stabilisers of points in one orbit are conjugate, not equal: in $S_3$ acting on $\{1,2,3\}$ the stabilisers are the three different subgroups of order $2$.
  8. Burnside averages fixed points. The number of $6$-bead $2$-colour necklaces is not $2^6/6$ (not even an integer) but $14$ — colourings with symmetry have orbits smaller than $|G|$.
  9. Non-trivial centre does not mean abelian. Every $p$-group has $Z(G)\ne\{e\}$, but $D_4$ and $Q_8$ (order $2^3$) are non-abelian; order $p^2$ is the largest prime-power order that forces commutativity.
  10. $G/Z(G)$ is never cyclic of order $\gt1$. So $[G:Z(G)]\ne p$; for a non-abelian group of order $p^3$, $|Z(G)|=p$ and $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$.
  11. Divisor sums are necessary, not sufficient. $6=1+1+1+3$ and $9=1+1+1+3+3$ pass the divisibility test but are not class equations.
  12. Centres of symmetric groups. $Z(S_n)=\{e\}$ for $n\ge3$, but $S_2\cong\mathbb{Z}_2$ is abelian; $Z(A_n)=\{e\}$ for $n\ge4$, but $A_3\cong\mathbb{Z}_3$.

Exercises

I
Cycle notation and orders.
  • 1 Write $\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\3&6&5&8&1&2&4&7\end{pmatrix}$ as a product of disjoint cycles; find $o(\sigma)$, $\sigma^{-1}$ and $\sigma^{100}$.
  • 2 Compute $(1\ 2\ 3)(2\ 3\ 4)$ and $(2\ 3\ 4)(1\ 2\ 3)$ in $S_4$.
  • 3 List all orders of elements of $S_6$.
  • 4 Find the least $n$ such that $S_n$ contains an element of order $12$; of order $35$; of order $42$.
  • 5 How many elements of order $3$ are there in $S_6$?
  • 6 How many $5$-cycles are there in $S_7$?
  • 7 Let $\gamma=(1\ 2\ 3\ 4\ 5\ 6\ 7\ 8)$. Write $\gamma^2$, $\gamma^3$ and $\gamma^4$ in cycle notation.
  • 8 Prove that an element of prime order $p$ in $S_n$ is a product of disjoint $p$-cycles, and deduce that $S_p$ has exactly $(p-1)!$ elements of order $p$.
  • 9 Prove that a permutation $\sigma$ is a product of two disjoint cycles of the same length $k$ whenever $\sigma=\gamma^2$ for a $2k$-cycle $\gamma$, and decide whether every product of two disjoint $3$-cycles is the square of some element of $S_6$.
1 $1\to3\to5\to1$, $2\to6\to2$, $4\to8\to7\to4$: $\sigma=(1\ 3\ 5)(2\ 6)(4\ 8\ 7)$, $o(\sigma)=\operatorname{lcm}(3,2,3)=6$, $\sigma^{-1}=(1\ 5\ 3)(2\ 6)(4\ 7\ 8)$. Since $100\equiv4\pmod6$, $\sigma^{100}=\sigma^4=(1\ 3\ 5)^4(2\ 6)^4(4\ 8\ 7)^4=(1\ 3\ 5)(4\ 8\ 7)$.
2 Right to left: $(1\ 2\ 3)(2\ 3\ 4)$: $1\mapsto1\mapsto2$, $2\mapsto3\mapsto1$, $3\mapsto4\mapsto4$, $4\mapsto2\mapsto3$, giving $(1\ 2)(3\ 4)$. Similarly $(2\ 3\ 4)(1\ 2\ 3)=(1\ 3)(2\ 4)$. The two products differ but are conjugate (same type).
3 Partitions of $6$ and their lcms: $6\to6$; $5{+}1\to5$; $4{+}2\to4$; $4{+}1{+}1\to4$; $3{+}3\to3$; $3{+}2{+}1\to6$; $3{+}1^3\to3$; $2{+}2{+}2$, $2{+}2{+}1{+}1$, $2{+}1^4\to2$; $1^6\to1$. Orders: $1,2,3,4,5,6$.
4 $12=4\cdot3$: $4+3=7$ symbols (a $12$-cycle or $6+4$ costs more), so $n=7$. $35=5\cdot7$: $5+7=12$, $n=12$. $42=2\cdot3\cdot7$: $2+3+7=12$, $n=12$.
5 Types $(3,1,1,1)$ and $(3,3)$: $\dfrac{720}{3\cdot3!}+\dfrac{720}{3^2\cdot2!}=40+40=80$.
6 Type $(5,1,1)$: $\dfrac{7!}{5\cdot2!}=504$ (equivalently $\binom75\cdot4!=21\cdot24$).
7 By Theorem 6.33(c): $\gamma^2=(1\ 3\ 5\ 7)(2\ 4\ 6\ 8)$; $\gamma^3=(1\ 4\ 7\ 2\ 5\ 8\ 3\ 6)$ (still an $8$-cycle, $\gcd(3,8)=1$); $\gamma^4=(1\ 5)(2\ 6)(3\ 7)(4\ 8)$.
8 If $o(\sigma)=p$ then $\operatorname{lcm}$ of the cycle lengths is $p$, so each length divides $p$: every cycle has length $1$ or $p$. In $S_p$ this means one $p$-cycle, and there are $p!/p=(p-1)!$ of them (Theorem 6.34).
9 By Theorem 6.33(c) with $j=2$ and length $2k$, $\gamma^2$ has $\gcd(2,2k)=2$ cycles of length $k$. Conversely $(a_1\ a_2\ a_3)(b_1\ b_2\ b_3)=\gamma^2$ for $\gamma=(a_1\ b_1\ a_2\ b_2\ a_3\ b_3)$: then $\gamma^2$ sends $a_1\mapsto a_2\mapsto a_3\mapsto a_1$ and $b_1\mapsto b_2\mapsto b_3\mapsto b_1$. So yes, every such product is a square. (Also, every $3$-cycle is a square: $(a\ b\ c)=(a\ c\ b)^2$.)
II
Parity, $A_n$ and conjugacy.
  • 1 Decide the parity of $(1\ 2\ 3\ 4\ 5\ 6)$, of $(1\ 2)(3\ 4\ 5)(6\ 7\ 8\ 9)$, and of the permutation $\sigma$ in I.1.
  • 2 Show that for $n\ge3$, $A_n$ is generated by the $3$-cycles $(1\ 2\ k)$, $3\le k\le n$.
  • 3 Show that $\sigma=(1\ 2\ 3)(4\ 5\ 6)$ and $\sigma'=(1\ 4\ 2)(3\ 6\ 5)$ are conjugate in $S_6$ and in $A_6$, and find conjugating elements.
  • 4 How many conjugacy classes have $S_5$, $S_6$ and $A_5$?
  • 5 Find $|C_{S_7}(\sigma)|$ for $\sigma=(1\ 2\ 3)(4\ 5)$ and describe $C_{S_7}(\sigma)$ explicitly.
  • 6 Show that $Z(S_n)=\{e\}$ for $n\ge3$.
  • 7 Let $n\ge2$ and let $\phi:S_n\to A$ be a homomorphism into an abelian group. Show that $\phi$ is constant on transpositions, and deduce that the only homomorphisms $S_n\to\mathbb{C}^{\times}$ are the trivial one and sgn.
  • 8 Which conjugacy classes of $S_6$ split in $A_6$? Write the class equation of $A_6$.
  • 9 Prove that for $n\ge3$ the $3$-cycles are all conjugate in $A_n$ when $n\ge5$, but not when $n=3$ or $4$.
1 A $6$-cycle is odd ($(-1)^5$). $(1\ 2)(3\ 4\ 5)(6\ 7\ 8\ 9)$ has two even-length cycles: even. $\sigma=(1\ 3\ 5)(2\ 6)(4\ 8\ 7)$ has one even-length cycle: odd.
2 By Theorem 6.36 it suffices to write every $3$-cycle using the $(1\ 2\ k)$. 3-cycles through $1$: $(1\ 2\ b)$ is on the list; $(1\ a\ 2)=(1\ 2\ a)^2$; and for $a,b\ne2$, $(1\ a\ b)=(1\ 2\ b)(1\ 2\ a)^2$ — follow the points: $(1\ 2\ a)^2=(1\ a\ 2)$ sends $1\mapsto a$, which $(1\ 2\ b)$ fixes; $a\mapsto2\mapsto b$; $b\mapsto b\mapsto1$; $2\mapsto1\mapsto2$. 3-cycles avoiding $1$: for distinct $a,b,c\ne1$, $(a\ b\ c)=(1\ a\ b)(1\ b\ c)$ ($a\mapsto a\mapsto b$, $b\mapsto c\mapsto c$, $c\mapsto1\mapsto a$, $1\mapsto b\mapsto1$), a product of two $3$-cycles through $1$, handled above.
3 Same type $(3,3)$, so conjugate in $S_6$: aligning gives $\tau=(2\ 4\ 3)(5\ 6)$ ($1\mapsto1$, $2\mapsto4$, $3\mapsto2$, $4\mapsto3$, $5\mapsto6$, $6\mapsto5$), which is odd. The element $\pi=(1\ 4)(2\ 5)(3\ 6)$ swaps the two cycles of $\sigma$, commutes with $\sigma$ and is odd, so $\tau\pi=(1\ 3\ 5\ 4)(2\ 6)$ is even and also conjugates $\sigma$ to $\sigma'$. (This is Theorem 6.40: type $(3,3)$ repeats a part, so the class does not split.)
4 $p(5)=7$ and $p(6)=11$ classes. $A_5$: the even types $(1^5),(2,2,1),(3,1,1),(5)$ give four $S_5$-classes, of which only $(5)$ splits, so $5$ classes: $60=1+15+20+12+12$.
5 Type $3^1\,2^1\,1^2$: $z=3\cdot2\cdot2!=12$. The centraliser contains $\langle(1\ 2\ 3)\rangle\times\langle(4\ 5)\rangle\times\operatorname{Sym}\{6,7\}$, of order $3\cdot2\cdot2=12$, so it equals this group.
6 Let $\sigma\ne e$, say $\sigma(a)=b\ne a$, and pick $c\notin\{a,b\}$ (possible as $n\ge3$). With $\tau=(b\ c)$, $\tau\sigma\tau^{-1}(a)=\tau\sigma(a)=\tau(b)=c\ne b=\sigma(a)$, so $\tau\sigma\tau^{-1}\ne\sigma$ and $\sigma\notin Z(S_n)$.
7 All transpositions are conjugate (Theorem 6.37), and $\phi(g\tau g^{-1})=\phi(g)\phi(\tau)\phi(g)^{-1}=\phi(\tau)$ in an abelian group. So $\phi(\tau)=t$ for every transposition, with $t^2=\phi(\tau^2)=1$. Since transpositions generate $S_n$, $\phi$ is determined by $t$: $t=1$ gives the trivial homomorphism; $t=-1$ (in $\mathbb{C}^\times$) gives $\phi(\sigma)=(-1)^m=\operatorname{sgn}\sigma$.
8 Even types in $S_6$: $1^6$ ($1$), $2^2 1^2$ ($45$), $3\,1^3$ ($40$), $3^2$ ($40$), $4\,2$ ($90$), $5\,1$ ($144$). Distinct odd parts: only $(5,1)$, which splits into $72+72$. Class equation: $360=1+45+40+40+90+72+72$.
9 For $n\ge5$ the type $(3,1,\dots,1)$ has at least two parts equal to $1$, so the class does not split (Theorem 6.40): all $3$-cycles are conjugate in $A_n$. (Directly: $(4\ 5)$ commutes with $(1\ 2\ 3)$ and is odd.) In $A_4$ the type $(3,1)$ has distinct odd parts and the eight $3$-cycles split as $4+4$; $A_3=\{e,(1\ 2\ 3),(1\ 3\ 2)\}$ is abelian, so its two $3$-cycles are not conjugate.
III
Actions, orbit–stabiliser and Burnside.
  • 1 $S_4$ acts on the set of $2$-element subsets of $\{1,2,3,4\}$. Find the orbit and the stabiliser of $\{1,2\}$ and check the orbit–stabiliser theorem.
  • 2 Find the order of the rotation group of a regular tetrahedron and of a regular dodecahedron (12 pentagonal faces) by orbit–stabiliser.
  • 3 How many different necklaces of $5$ beads in $3$ colours are there up to rotation? Up to rotation and reflection?
  • 4 In how many ways can the four edges of a square be coloured with $2$ colours, up to the symmetries of the square?
  • 5 Let $G$ act transitively on a finite set $X$ with $|X|\ge2$. Prove that some $g\in G$ has no fixed point.
  • 6 Let $H\le G$ with $[G:H]=n$. Show that $H$ contains a normal subgroup $N$ of $G$ with $[G:N]$ dividing $n!$. Deduce that a group of order $36$ with a subgroup of order $9$ is not simple.
  • 7 Prove that a group of order $2m$ with $m$ odd has a normal subgroup of index $2$. (Hint: an element of order $2$ acts in the left regular representation as a product of $m$ transpositions.)
  • 8 (a) A group of order $25$ acts on a set with $17$ elements. Show that at least two points are fixed by the whole group. (b) Show that a group of order $15$ can act on a set with $17$ elements without any fixed point.
1 Every $2$-subset is the image of $\{1,2\}$ (send $1,2$ to its two elements), so the orbit has all $\binom42=6$ subsets. The stabiliser is $\{\sigma:\sigma\{1,2\}=\{1,2\}\}=\{e,(1\ 2),(3\ 4),(1\ 2)(3\ 4)\}$, of order $4$; and $6\cdot4=24=|S_4|$.
2 Tetrahedron: transitive on $4$ faces, each stabilised by the $3$ rotations about the axis through it: $4\cdot3=12$ (it is $A_4$). Dodecahedron: $12$ faces, stabiliser of order $5$: $60$ (it is isomorphic to $A_5$).
3 Rotations: the identity fixes $3^5=243$; each of the $4$ non-trivial rotations is a $5$-cycle on positions and fixes $3$. Orbits: $(243+12)/5=51$. Reflections ($5$ of them, each with one fixed bead and two $2$-cycles, $c=3$) add $5\cdot27=135$: $(255+135)/10=39$.
4 $D_4$ on the $4$ edges: identity $2^4=16$; quarter-turns ($2$): one $4$-cycle, $2$ each; half-turn: two $2$-cycles, $4$; the $2$ reflections through midpoints of opposite edges fix those two edges and swap the others ($c=3$), $8$ each; the $2$ diagonal reflections swap edges in pairs, $4$ each. Total $16+2+2+4+8+8+4+4=48$, so $48/8=6$ colourings.
5 By Burnside with one orbit, $\sum_g|\operatorname{Fix}(g)|=|G|$: the average number of fixed points is $1$. The identity fixes $|X|\ge2$ points, more than the average, so some $g$ fixes fewer than $1$, i.e. none.
6 This is Theorem 6.44 with $N=\bigcap_x xHx^{-1}$. For $|G|=36$ and $|H|=9$: $n=4$, and $36\nmid4!=24$, so $N\ne\{e\}$; also $N\subseteq H\ne G$. So $G$ is not simple.
7 By Cauchy's theorem (§6.4) — or directly, pairing each element with its inverse — $G$ has an element $t$ of order $2$. In the left regular representation $\lambda:G\to S_{2m}$, $\lambda_t$ has no fixed points and all cycles of length $2$: it is a product of $m$ transpositions, which is odd as $m$ is odd. So $\operatorname{sgn}\circ\lambda:G\to\{\pm1\}$ is onto, and its kernel is a normal subgroup of index $2$.
8 (a) $25=5^2$, so Theorem 6.47(a) gives $|X^G|\equiv17\equiv2\pmod5$; hence $|X^G|\ge2$. (b) Orbit sizes must divide $15$, and $17=5+3+3+3+3$ uses no $1$s. Realise it: let $\mathbb{Z}_{15}$ act on one copy of $\mathbb{Z}_5$ by $g\cdot x=x+g\pmod5$ and on four copies of $\mathbb{Z}_3$ by $g\cdot x=x+g\pmod3$ (actions through the quotients $\mathbb{Z}_5$ and $\mathbb{Z}_3$). There are five orbits, none of size $1$. The fixed-point congruence needs a group of prime-power order; $15$ is not one.
IV
The class equation and $p$-groups.
  • 1 Write the class equations of $S_3$, $Q_8$ and $D_6$ (order $12$).
  • 2 Write the class equation of $S_5$.
  • 3 Show that every group of order $25$ is abelian, and list them up to isomorphism.
  • 4 Let $G$ be a non-abelian group of order $p^3$. Show that $|Z(G)|=p$ and $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$, and that $G$ has exactly $p^2+p-1$ conjugacy classes. How many classes has a non-abelian group of order $27$?
  • 5 Let $G$ be a $p$-group and $N\ne\{e\}$ a normal subgroup. Prove that $N\cap Z(G)\ne\{e\}$.
  • 6 Let $G$ be a finite non-abelian group. Prove that the probability that two independently and uniformly chosen elements commute is at most $5/8$, and that $D_4$ attains this bound.
  • 7 Show that a group of order $p^n$ ($n\ge1$) has a subgroup of index $p$, and that every such subgroup is normal.
1 $S_3$: $6=1+2+3$ (the $3$-cycles; the transpositions). $Q_8$: $8=1+1+2+2+2$. $D_6=\langle r,s: r^6=s^2=e,\ srs^{-1}=r^{-1}\rangle$: centre $\{e,r^3\}$; classes $\{r,r^5\}$, $\{r^2,r^4\}$, $\{s,sr^2,sr^4\}$, $\{sr,sr^3,sr^5\}$: $12=1+1+2+2+3+3$.
2 Types $1^5,\,2\,1^3,\,2^2 1,\,3\,1^2,\,3\,2,\,4\,1,\,5$ with sizes $1,10,15,20,20,30,24$: $120=1+10+15+20+20+24+30$.
3 $25=5^2$: Theorem 6.49 gives abelian, and the groups are $\mathbb{Z}_{25}$ and $\mathbb{Z}_5\times\mathbb{Z}_5$.
4 $|Z|\in\{p,p^2\}$ ($Z\ne\{e\}$ by Theorem 6.47, $Z\ne G$). $|Z|=p^2$ would make $G/Z$ of order $p$, cyclic — impossible (Theorem 6.48). So $|Z|=p$, and $G/Z$ has order $p^2$, so it is $\mathbb{Z}_{p^2}$ or $\mathbb{Z}_p^2$; not cyclic, so $\mathbb{Z}_p\times\mathbb{Z}_p$. For $a\notin Z$, $C_G(a)$ contains $Z$ and $a$, so $|C_G(a)|\ge p^2$, and $C_G(a)\ne G$; thus $|C_G(a)|=p^2$ and $|\operatorname{cl}(a)|=p$. Number of classes: $p$ central ones plus $(p^3-p)/p=p^2-1$ others, total $p^2+p-1$. For $p=3$: $11$.
5 $N$ is a union of conjugacy classes (it is normal), so $G$ acts on $N$ by conjugation. By Theorem 6.47(a), $|N^G|\equiv|N|\equiv0\pmod p$, and $N^G=N\cap Z(G)$ contains $e$; hence it has at least $p$ elements.
6 The number of commuting pairs is $\sum_{x}|C_G(x)|=\sum_x|G|/|\operatorname{cl}(x)|=|G|\cdot k$, where $k$ is the number of classes, so the probability is $k/|G|$. With $z=|Z(G)|$: $k\le z+\tfrac{|G|-z}{2}$ (non-central classes have at least $2$ elements). As $G/Z(G)$ is not cyclic, $[G:Z]\ge4$, so $z\le|G|/4$ and $k/|G|\le\tfrac12+\tfrac{z}{2|G|}\le\tfrac12+\tfrac18=\tfrac58$. $D_4$ has $5$ classes and order $8$: probability $5/8$.
7 Existence: Theorem 6.50 with $k=n-1$. Normality: Theorem 6.44(b), since $p$ is the smallest (indeed the only) prime dividing $p^n$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA The number of elements of order $4$ in the symmetric group $S_6$ is (A) $90$; (B) $120$; (C) $180$; (D) $270$.

Idea Order $4$ means the lcm of the cycle lengths is $4$: types $(4,1,1)$ and $(4,2)$.
Count By Theorem 6.34: $(4,1,1)$: $\dfrac{720}{4\cdot2!}=90$; $(4,2)$: $\dfrac{720}{4\cdot2}=90$. Option (A) forgets the second type.
Answer (C) $180$.

E2. CSIR Part B The number of ways of colouring the six faces of a cube, each face red or blue, where two colourings are regarded as the same if a rotation of the cube carries one to the other, is (A) $8$; (B) $10$; (C) $12$; (D) $64$.

Idea Burnside with the $24$ rotations, classified as in Example 6(c).
Count $\dfrac{2^6+6\cdot2^3+3\cdot2^4+8\cdot2^2+6\cdot2^3}{24}=\dfrac{64+48+48+32+48}{24}=\dfrac{240}{24}=10.$ (Directly: $0,1,2,3,\dots$ red faces give $1,1,2,2,2,1,1$ classes — two red faces adjacent or opposite, three red faces around a corner or in a band.)
Answer (B) $10$.

E3. CSIR Part B A group of order $81$ acts on a set with $23$ elements. Which of the following could be the number of points fixed by the whole group? (A) $0$; (B) $1$; (C) $2$; (D) $3$.

Idea $81=3^4$, so Theorem 6.47(a) applies: $|X^G|\equiv|X|=23\equiv2\pmod3$.
Options Among $0,1,2,3$ only $2$ is $\equiv2\pmod3$. (It is attained, e.g. by two fixed points and seven orbits of size $3$ for a suitable action of $\mathbb{Z}_{81}$ through its quotient $\mathbb{Z}_3$.)
Answer (C).

E4. CSIR Part C Which of the following statements are true? (One or more options may be correct.) (A) $S_7$ has an element of order $12$. (B) $A_7$ has an element of order $10$. (C) $(1\ 2\ 3)(4\ 5\ 6\ 7)$ and $(1\ 2\ 3\ 4)(5\ 6\ 7)$ are conjugate in $S_7$. (D) $S_7$ has exactly $720$ elements of order $7$.

(A) True Type $(4,3)$ has order $\operatorname{lcm}(4,3)=12$ and uses $7$ symbols.
(B) False Order $10$ in $S_7$ forces type $(5,2)$, which has one even-length cycle and is odd (Example 3(c)).
(C) True Both have cycle type $(4,3)$ (Theorem 6.37(b)).
(D) True An element of order $7$ in $S_7$ is a $7$-cycle (Exercise I.8), and there are $6!=720$ of them.
Answer (A), (C), (D).

E5. CSIR Part C GATE MA Let $G$ be a non-abelian group of order $p^3$, $p$ prime. Which of the following are true? (A) $|Z(G)|=p$. (B) $G$ has exactly $p^2+p-1$ conjugacy classes. (C) $G/Z(G)$ is cyclic. (D) Every subgroup of $G$ of order $p$ is normal in $G$.

(A) True Exercise IV.4: $Z(G)\ne\{e\}$, $Z(G)\ne G$, and $|Z(G)|=p^2$ would make $G/Z(G)$ cyclic.
(B) True Exercise IV.4: $p$ central classes and $p^2-1$ classes of size $p$.
(C) False Theorem 6.48: $G/Z(G)$ cyclic would make $G$ abelian. In fact $G/Z(G)\cong\mathbb{Z}_p\times\mathbb{Z}_p$.
(D) False In $D_4$ ($p=2$) the subgroup $\{e,s\}$ is not normal: $rsr^{-1}=sr^{-2}=sr^2\notin\{e,s\}$. (Subgroups of order $p^2$, of index $p$, are normal — Exercise IV.7.)
Answer (A), (B).

E6. CSIR Part C A finite group $G$ acts transitively on a finite set $X$ with $|X|=n\ge2$. Which of the following are necessarily true? (A) $n$ divides $|G|$. (B) Some element of $G$ fixes no point of $X$. (C) The stabilisers of any two points are conjugate subgroups. (D) If $G$ is abelian, every stabiliser is trivial.

(A) True $X$ is a single orbit, and $|X|=[G:G_x]$ (Theorem 6.43).
(B) True Burnside: the average number of fixed points is $1$ and the identity fixes $n\ge2$ (Exercise III.5).
(C) True $y=g\cdot x$ for some $g$, and $G_y=gG_xg^{-1}$.
(D) False $\mathbb{Z}_4$ acts transitively on $X=\mathbb{Z}_2$ by $k\cdot x=x+k\pmod 2$; the stabiliser of each point is $\{0,2\}$. (What is true: for abelian $G$ all stabilisers are equal, since conjugate subgroups of an abelian group coincide, so the stabiliser is the kernel of the action.)
Answer (A), (B), (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Permutations. Fix the right-to-left convention on the board first. Theorems 6.32–6.34 with Example 1 done live; project Interactive 1 on the Example-1 permutation and on the out-shuffle. Example 2 (Landau-type questions) as a class race. Then parity: Theorem 6.35 via split/merge — press "× transposition" a few times and let students predict split or merge — and Theorem 6.36, Example 3.
  2. Conjugacy and actions. Theorem 6.37 by "relabelling"; Example 4(b) as a two-minute exercise; class sizes (Theorem 6.39) and the $A_n$ splitting rule (Theorem 6.40) with the rule cards for $S_4,A_4,S_5,A_5$. Define actions; Cayley; orbit–stabiliser; Example 5 (the cube is very concrete — bring one).
  3. Burnside and $p$-groups. Burnside's lemma with Interactive 2 ($n=6$, $k=2$, rotations, then dihedral); Example 6. Class equation, Theorems 6.47–6.50, and Example 7 as a "true or false" round. Finish with Exam-corner E3 and E5.

Discussion questions. (1) Why must conjugate permutations have the same cycle type, and why is the converse true in $S_n$ but not in $A_n$? (2) Burnside's lemma counts orbits by averaging fixed points; why would counting "colourings divided by $|G|$" overcount symmetric colourings? (3) The class equation of a $p$-group forces a non-trivial centre; what goes wrong for $|G|=6$?

Misconceptions to watch for. Mixing composition conventions; applying the lcm rule to non-disjoint cycles; "a $4$-cycle is even because $4$ is even"; "same cycle type ⇒ conjugate in $A_n$"; dividing the number of colourings by $|G|$; believing that $p$-groups are abelian; accepting any list of divisors as a class equation.

Suggested homework. I(1, 4, 5, 7, 8), II(1, 3, 4, 6, 8), III(1, 3, 4, 5, 7), IV(1, 3, 4, 6); Exam corner E1, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 45 minutes

Research question. A "perfect" riffle shuffle cuts a deck exactly in half and interleaves the halves card by card. How many perfect shuffles bring a deck back to its original order — and why does the answer for $52$ cards jump from $8$ to $52$ when the top card is allowed to move?

Why it matters. Stage magicians and casino dealers have used perfect shuffles for centuries, and the mathematics of shuffling (how many ordinary riffle shuffles make a deck random?) became a research field in probability in the 1980s and 1990s. The same permutations — "perfect shuffles" of $2n$ positions — are used to route data in parallel computers (the shuffle–exchange network) and in fast Fourier transform algorithms.

What to do.

  1. Number the positions $0,1,\dots,2n-1$. Write the out-shuffle (top card stays on top) and the in-shuffle (top card goes to second place) as permutations of the positions, and find their cycle decompositions for $2n=8,10,52$ by hand or with a short program.
  2. Compute their orders with Theorem 6.33 and tabulate them for $2n\le60$.
  3. Show that the out-shuffle fixes positions $0$ and $2n-1$ and acts on the other positions as $x\mapsto2x\pmod{2n-1}$; deduce that its order is the multiplicative order of $2$ modulo $2n-1$ (§5.3). Find the corresponding formula for the in-shuffle.
  4. Decide the parity of the out-shuffle for several deck sizes and look for a pattern.

Tools: Python (a permutation is a list; compose and count cycles); the multiplicative-order material of §5.3.

Hand in: A one-page table of orders for $2n\le60$, the two order formulas with a proof for the out-shuffle, and one surprising observation.

Going further. A magician can move the top card to any position $k$ by a sequence of in- and out-shuffles read off from the binary digits of $k$. Find the rule, and read about which permutations of a deck can be generated by the two perfect shuffles together.

Instructor note: for $52$ cards the out-shuffle has cycle type $8^6\,2^1\,1^2$ (six $8$-cycles, one transposition, the top and bottom cards fixed), so its order is $8=\operatorname{ord}_{51}(2)$; the in-shuffle is a single $52$-cycle, of order $52=\operatorname{ord}_{53}(2)$, since position $x$ goes to $2x+1$ and, shifting labels by one, this is multiplication by $2$ modulo $2n+1=53$. For $8$ cards the out-shuffle has order $3$ (as in Interactive 1), for $10$ cards order $6$, for $64$ cards order $6$.

🧪 Self-check quiz

0/5 correct

Q1. The order of $(1\ 2\ 3)(4\ 5)(6\ 7\ 8\ 9)$ in $S_9$ is

Q2. Which of these permutations is even?

Q3. Two permutations in $S_n$ are conjugate in $S_n$ if and only if

Q4. The number of necklaces with $4$ beads, each black or white, counted up to rotation, is

Q5. Let $p$ be a prime. Every group of order $p^2$ is