University Mathematics — Year 2 · Bachelor Year 2

1Sets and Structures

This opening chapter sharpens the foundations laid in the Year 1 volume into working tools of the trade: the calculus of sets and quotients, the comparison of infinite sets (countability, Cantor–Bernstein), and the structural theory of groups and rings — Lagrange’s theorem, the symmetric group with its signature, ideals and the Chinese remainder theorem. Everything here is used relentlessly in the rest of the book: the signature builds the determinant (Chapter 2), quotient rings drive arithmetic, and countability underlies both topology and probability.

1.1 Sets, maps, quotients

We use freely the language of sets, maps, and equivalence and order relations set up in the Year 1 volume. Two upgrades deserve a proper statement.

Proposition 1.1 (Images and preimages of families)

Let $f \colon E \to F$ and let $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ be families of subsets of $E$ , resp. $F$ . Then

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{equality for injective } f).

Proof. Each identity is an unwinding of definitions; for instance $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ for all $j$ $\iff x \in f^{-1}(B_j)$ for all $j$ . The image identities and the failure of equality in the intersection case (with the injectivity fix) were proved in the Year 1 volume for two sets; the arguments are identical for families. ∎

Example 1.2 (Where the image inclusion is strict)

Take $f \colon \R \to \R$ , $f(x) = x^2$ , with $A_1 = \intcc{-1}{0}$ and $A_2 = \intcc{0}{1}$ . Then

f(A_1 \cap A_2) = f(\{0\}) = \{0\}, \qquad f(A_1) \cap f(A_2) = \intcc{0}{1} \cap \intcc{0}{1} = \intcc{0}{1} :

the inclusion of Proposition 1.1 is as strict as can be — the two preimage points $\pm x$ of a common value live in different $A_i$ . Injectivity is exactly what forbids this splitting, which is why preimages (which never merge points) satisfy all four identities unconditionally while images lose the one about intersections. Rule of thumb for the whole book: push preimages through set operations freely; handle images with care.

Definition 1.3 (Quotient set)

Let $\mathcal{R}$ be an equivalence relation on $E$ . The quotient set $E/\mathcal{R}$ is the set of equivalence classes; the surjection $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , is the canonical projection.

Universal property (factorization): if $f \colon E \to F$ is compatible with $\mathcal{R}$ (i.e. $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), there is exactly one map $\overline f \colon E/\mathcal{R} \to F$ with $f = \overline f \circ \pi$ .

Proof of the universal property. Uniqueness: the requirement $f = \overline f \circ \pi$ reads

\overline f\bigl(\mathrm{cl}(x)\bigr) = f(x) \qquad (x \in E),

and since $\pi$ is surjective, every element of $E/\mathcal{R}$ is some $\mathrm{cl}(x)$ : the values of $\overline f$ are all forced. Existence: take the display as the definition of $\overline f$ ; it is unambiguous precisely by compatibility — if $\mathrm{cl}(x) = \mathrm{cl}(y)$ , then $x \mathbin{\mathcal{R}} y$ , so $f(x) = f(y)$ and the two candidate values agree — and it factorizes $f$ by construction. Note the division of labour: surjectivity of $\pi$ gives uniqueness, compatibility gives existence. ∎

Example 1.4

$\Z/n\Z$ is the quotient of $\Z$ by congruence modulo $n$ ; the well-definedness checks of the Year 1 volume were instances of the universal property. Quotients turn “compatible constructions on representatives” into honest maps — we use this constantly below.

1.2 Countability and cardinality

Definition 1.5 (Equipotence, countability)

Two sets are equipotent when a bijection joins them. A set is countable when it is equipotent to $\N$ (some authors include finite sets; we say at most countable for “finite or countable”).

Proposition 1.6 (Stability properties)

Every infinite subset of $\N$ is countable; a set is at most countable iff it injects into $\N$ iff it is empty or a surjective image of $\N$ .
$\N \times \N$ is countable; a product of two at most countable sets is at most countable.
An at most countable union of at most countable sets is at most countable.
$\Z$ and $\Q$ are countable.

Proof. (1) List an infinite $A \subseteq \N$ by repeated minima: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (nonempty since $A$ is infinite); the map $k \mapsto a_k$ is strictly increasing, injective, and surjective onto $A$ (every $a \in A$ exceeds only finitely many elements of $A$ , so it is reached). If $E$ injects into $\N$ via $\varphi$ , then $E$ is equipotent to $\varphi(E) \subseteq \N$ : finite or countable. If $s \colon \N \to E$ is surjective, then $x \mapsto \min s^{-1}(\{x\})$ injects $E$ into $\N$ .

(2) The map $(p, q) \mapsto 2^p(2q + 1) - 1$ is a bijection $\N^2 \to \N$ (every positive integer has a unique odd–even split $2^p m$ with $m$ odd, by unique factorization). Products: compose injections.

(3) Given sets $E_n$ with surjections $s_n \colon \N \to E_n$ (harmless when some $E_n$ is finite: repeat values), the map $(n, k) \mapsto s_n(k)$ is a surjection from the countable $\N^2$ onto $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : countable union. $\Q$ is a surjective image of $\Z \times \N^*$ (the fraction map), hence at most countable, and infinite. ∎

Example 1.7 (A pairing function, computed)

The bijection $(p, q) \mapsto 2^p(2q + 1) - 1$ of the proof deserves to be seen at work. Its first values:

\begin{array}{c|ccccc} & q = 0 & q = 1 & q = 2 & q = 3 & q = 4\\ \hline p = 0 & 0 & 2 & 4 & 6 & 8\\ p = 1 & 1 & 5 & 9 & 13 & 17\\ p = 2 & 3 & 11 & 19 & 27 & 35\\ p = 3 & 7 & 23 & 39 & 55 & 71 \end{array}

Row $p$ collects the integers $n$ for which $n + 1$ is exactly divisible by $2^p$ : every natural number appears exactly once. Decoding is as explicit as encoding: for $n = 43$ , factor $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , so $(p, q) = (2, 5)$ . The closing insight: countability proofs are often algorithms in disguise — here, “factor out the twos”.

Example 1.8 (The algebraic numbers are countable)

A complex number is algebraic when it annihilates some nonzero polynomial with rational coefficients. The set $\overline\Q$ of algebraic numbers is countable: polynomials of degree $\leq d$ over $\Q$ inject into $\Q^{d+1}$ , a finite product of countable sets (Proposition 1.6 (2)); the union over $d$ enumerates the nonzero rational polynomials as $P_0, P_1, P_2, \dots$ ; each $P_k$ has finitely many roots; and

\overline\Q = \bigcup_{k \in \N}\ \{\text{roots of } P_k\}

is a countable union of finite sets (Proposition 1.6 (3)), infinite since it contains $\Q$ . Combined with the uncountability of $\R$ (Theorem 1.9 below), this proves — without exhibiting a single one — that transcendental numbers exist and form an uncountable majority: Cantor’s counting argument of 1874, existence by cardinality alone.

Theorem 1.9 (Cantor; uncountability of $\R$ )

For every set $E$ , there is no surjection $E \to \mathcal{P}(E)$ .
$\R$ is not countable.

Proof. (1) was proved in the Year 1 volume (the diagonal set $D = \{x : x \notin f(x)\}$ ).

(2) Suppose $(x_n)_{n \in \N}$ enumerates $\R$ . Build nested segments $I_0 \supseteq I_1 \supseteq \dots$ with $\abs{I_n} = 3^{-n}$ and $x_n \notin I_n$ : split the current segment into three closed thirds; at least one third avoids $x_n$ (a point meets at most two of the three). The nested-segments theorem (adjacent endpoints) provides $\ell \in \bigcap_n I_n$ ; but $\ell = x_N$ for some $N$ , and $x_N \notin I_N$ : contradiction. ∎

Theorem 1.10 (Cantor–Bernstein)

If $E$ injects into $F$ and $F$ injects into $E$ , then $E$ and $F$ are equipotent.

Proof. Let $f \colon E \to F$ and $g \colon F \to E$ be injections. For each point (of $E$ or $F$ ), trace its ancestor chain of successive preimages, $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — each step is defined as long as the current point lies in the image of the relevant injection, and is then unique by injectivity. Three mutually exclusive fates: the chain stops at a point of $E \setminus g(F)$ (origin in $E$ ), stops at a point of $F \setminus f(E)$ (origin in $F$ ), or never stops. This partitions $E = E_E \cup E_F \cup E_\infty$ and $F = F_E \cup F_F \cup F_\infty$ according to the origin.

Now observe: $f$ maps $E_E$ onto $F_E$ — the chain of $f(x)$ is the chain of $x$ prefixed with one step, so origins match; and every $y \in F_E$ has a chain with at least one step (its origin lies in $E$ ), so $y = f(x)$ with $x \in E_E$ . The same argument gives bijections $f \colon E_\infty \to F_\infty$ and $g \colon F_F \to E_F$ . Gluing,

h(x) = \begin{cases} f(x) & \text{if } x \in E_E \cup E_\infty,\\ g^{-1}(x) & \text{if } x \in E_F, \end{cases}

is a bijection from $E$ onto $F = F_E \cup F_\infty \cup F_F$ : it is bijective piecewise, and the three target pieces are disjoint. ∎

Example 1.11

$\intoo{0}{1}$ and $\intcc{0}{1}$ are equipotent: the identity injects one way, $x \mapsto \frac{x + 1}{3}$ the other; the theorem manufactures the (necessarily discontinuous) bijection. Likewise $\R$ , $\intoo{0}{1}$ (via $\tanh$ -type bijections) and $\mathcal{P}(\N)$ (binary expansions, Exercise 1.3) are all equipotent: “the cardinality of the continuum”.

Example 1.12 (The segment and the square)

$\intcc{0}{1}$ and $\intcc{0}{1}^2$ are equipotent — dimension is invisible to cardinality. One injection is trivial: $x \mapsto (x, 0)$ . For the other, send $(x, y)$ to the real whose decimal digits interleave those of $x$ and $y$ ,

(0.x_1x_2x_3\dots,\ 0.y_1y_2y_3\dots) \;\longmapsto\; 0.x_1y_1x_2y_2x_3y_3\dots,

choosing for each coordinate the expansion that does not end in all $9$ ’s: with that convention the digits of the image determine those of $x$ and $y$ , so the map is injective (it need not be surjective — images never have, say, odd-position digits eventually $9$ — and that is fine). Cantor–Bernstein (Theorem 1.10) assembles a genuine bijection. Continuity, of course, is hopeless: a continuous bijection between them is impossible — the metric chapters explain why (connectedness distinguishes the line from the plane, Chapter 4).

1.3 Groups

Definition 1.13 (Generated subgroup; order)

Let $G$ be a group and $A \subseteq G$ . The subgroup generated by $A$ , written $\langle A \rangle$ , is the smallest subgroup containing $A$ — concretely, all finite products of elements of $A$ and their inverses. A group is cyclic when generated by one element: $\langle a\rangle = \{a^k : k \in \Z\}$ . The order of $a \in G$ is $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (possibly infinite); when finite, it is the least $n \geq 1$ with $a^n = e$ , and $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Proof of the order characterization. If some $a^m = e$ with $m \geq 1$ , let $n \geq 1$ be least with $a^n = e$ . The elements $e, a, \dots, a^{n-1}$ are pairwise distinct ( $a^{i} = a^{j}$ with $0 \leq i < j < n$ gives $a^{j-i} = e$ , contradicting minimality), and every $a^k$ reduces to one of them by Euclidean division $k = nq + r$ : $\langle a\rangle$ has exactly $n$ elements, and $a^k = a^r = e \iff r = 0 \iff n \mid k$ . If no power is trivial, all $a^k$ ( $k \in \Z$ ) are distinct (same division argument) and the order is infinite. ∎

Theorem 1.14 (Lagrange)

Let $G$ be a finite group and $H$ a subgroup. Then $\abs H$ divides $\abs G$ . In particular the order of every element divides $\abs G$ , and $a^{\abs G} = e$ for all $a \in G$ .

Proof. The relation $x \sim y \iff x^{-1}y \in H$ is an equivalence (reflexive: $e \in H$ ; symmetric: inverses; transitive: products). The class of $x$ is the left coset $xH = \{xh : h \in H\}$ , and $h \mapsto xh$ is a bijection $H \to xH$ (inverse $y \mapsto x^{-1}y$ ): all classes have $\abs H$ elements. Classes partition $G$ (the general partition theorem of the Year 1 volume), so $\abs G = \abs H \times (\text{number of cosets})$ . For an element: apply this to $H = \langle a\rangle$ ; then $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Example 1.15 (Cosets in action: $A_3$ inside $\mathfrak{S}_3$ )

Take $G = \mathfrak{S}_3$ (order $6$ ) and $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . The left cosets are

H = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}, \qquad (1\,2)H = \{(1\,2),\ (2\,3),\ (1\,3)\} :

two classes of three elements partitioning $G$ , exactly as the count $\abs G = \abs H \times (\text{number of cosets})$ demands — and visibly the partition into even and odd permutations. Note $(1\,3)H = (1\,2)H$ although $(1\,3) \neq (1\,2)$ : cosets are classes, not labelled by their representatives, and $x^{-1}y \in H$ is the only legitimate comparison. This two-class picture is the general one for the signature: $A_n$ and its lone companion coset split $\mathfrak{S}_n$ in half, which is how the weekend problem counts reachable puzzle positions.

Example 1.16

Two immediate dividends. Groups of prime order are cyclic: if $\abs G = p$ is prime and $a \neq e$ , then $\operatorname{ord}(a)$ divides $p$ and is not $1$ , so it is $p$ : $\langle a\rangle = G$ . The subgroup lattice of $\Z/12\Z$ : by Proposition 1.17 below, there is exactly one subgroup per divisor of $12$ — orders $1, 2, 3, 4, 6, 12$ , generated respectively by $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . The closing caution: the converse of Lagrange fails in general — $A_4$ has order $12$ but no subgroup of order $6$ , as we prove in this chapter’s weekend problem (Problem 1.1, question 14). Lagrange restricts the possible orders; it does not promise them.

The subgroup lattice of ℤ/12ℤ: one subgroup per divisor of 12 (), with an edge when one contains the other with prime index. Inclusions run against divisibility of the generator: 4 ⊂eq 2 because 4 is a multiple of 2. — The subgroup lattice of $\Z/12\Z$ : one subgroup per divisor of $12$ (Proposition 1.17), with an edge when one contains the other with prime index. Inclusions run *against* divisibility of the generator: $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ because $4$ is a multiple of $2$ .

Proposition 1.17 (Cyclic groups)

Let $G = \langle a \rangle$ be cyclic of order $n$ .

$G$ is isomorphic to $(\Z/n\Z, +)$ , via $\overline k \mapsto a^k$ .
Every subgroup of $G$ is cyclic; for each divisor $d \mid n$ there is exactly one subgroup of order $d$ , namely $\langle a^{n/d}\rangle$ .
$a^k$ generates $G$ if and only if $\gcd(k, n) = 1$ : $G$ has $\varphi(n)$ generators (Euler’s function).

Proof. (1) The map $k \mapsto a^k$ from $\Z$ onto $G$ is compatible with congruence mod $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , by the order characterization); the universal property (Definition 1.3) yields a well-defined bijective morphism from $\Z/n\Z$ .

(2) Let $H \leq G$ be nontrivial and $m$ least $\geq 1$ with $a^m \in H$ . Euclidean division shows $H = \langle a^m\rangle$ (for $a^k \in H$ : $k = mq + r$ forces $a^r \in H$ , so $r = 0$ ), and $m \mid n$ (divide $n$ by $m$ : $a^{n \bmod m} \in H$ ). Then $\abs H = n/m$ ; taking $m = n/d$ realizes each divisor $d$ . Uniqueness: any subgroup of order $d$ is, by the above, of the form $\langle a^m \rangle$ with $n/m = d$ — so $m = n/d$ is forced and the subgroup is determined.

(3) We claim $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Write $d = \gcd(k, n)$ . For any $m \geq 1$ , the order characterization of Definition 1.13 gives the chain of equivalences

(a^k)^m = e \iff n \mid km \iff \frac{n}{d} \,\Big|\, \frac{k}{d}\,m \iff \frac{n}{d} \,\Big|\, m ,

the last step by Gauss’s lemma, since $\frac nd$ and $\frac kd$ are coprime. The least such $m$ is $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , which equals $n$ iff $\gcd(k, n) = 1$ . There are $\varphi(n)$ such classes $k$ modulo $n$ . ∎

1.4 The symmetric group

Definition 1.18

$\mathfrak{S}_n$ is the group of permutations of $\intint{1}{n}$ (order $n!$ ). A cycle $(a_1\,a_2\,\cdots\,a_k)$ maps $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ and fixes everything else; $k$ is its length, a $2$ -cycle is a transposition. Two cycles are disjoint when their supports (non-fixed points) are.

Theorem 1.19 (Cycle decomposition)

Every permutation $\sigma \neq \mathrm{id}$ is a product of pairwise disjoint cycles, uniquely up to the order of the factors. Disjoint cycles commute, and $\operatorname{ord}(\sigma)$ is the lcm of the lengths.

Proof. Consider the “orbit” relation on the support of $\sigma$ : $x \sim y$ iff $y = \sigma^k(x)$ for some $k \in \Z$ — an equivalence relation. Each class $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finite, so the iterates cycle back — the first repetition must return to $x$ by injectivity) carries the cycle $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , and $\sigma$ is the product of these cycles: on each orbit, only the corresponding cycle acts. Uniqueness: any disjoint-cycle factorization reproduces exactly the orbits (the cycle through $x$ must be $(x\ \sigma(x)\ \cdots)$ ). Disjoint cycles commute since they move disjoint points; the order statement follows because $\sigma^m = \mathrm{id}$ iff each cycle’s $m$ -th power is (disjointness), iff each length divides $m$ . ∎

Example 1.20 (Cycle type as a census)

How many permutations of $\mathfrak{S}_9$ have the cycle type $(4, 3, 2)$ — one $4$ -cycle, one $3$ -cycle, one transposition? Choose the supports and the cyclic orders:

\frac{9!}{4\cdot 3\cdot 2} = \frac{362\,880}{24} = 15\,120 :

list the nine symbols in a row ( $9!$ ways), bracket the first four, next three, last two into cycles, and divide by the rotations inside each bracket ( $4$ , $3$ and $2$ of them) which give the same permutation. (Distinct cycle lengths here, so no further division; equal lengths would also require dividing by the permutations of the equal brackets.) Every such permutation has order $\operatorname{lcm}(4,3,2) = 12$ and signature $(-1)^3(-1)^2(-1)^1 = +1$ (Theorem 1.19 and the signature theorem below). One partition of $9$ , one conjugacy class, one census — the combinatorics of $\mathfrak{S}_n$ is the arithmetic of partitions.

Theorem 1.21 (Signature)

There is exactly one group morphism $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (for $n \geq 2$ ) taking the value $-1$ on transpositions: the signature. Moreover $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ where $I(\sigma)$ is the number of inversions (pairs $i < j$ with $\sigma(i) > \sigma(j)$ ), a $k$ -cycle has signature $(-1)^{k-1}$ , and the alternating group $A_n = \ker\varepsilon$ has order $\frac{n!}{2}$ .

Proof. Existence. For $\sigma \in \mathfrak{S}_n$ set

\varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} .

The factors’ absolute values multiply to $1$ (the unordered pairs $\{\sigma(i), \sigma(j)\}$ run over all pairs), so $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Morphism: for $\sigma, \tau$ ,

\varepsilon(\sigma\tau) = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{j - i} = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{\tau(j) - \tau(i)} \cdot \prod_{i<j} \frac{\tau(j) - \tau(i)}{j - i} = \varepsilon(\sigma)\,\varepsilon(\tau),

the middle product being $\varepsilon(\sigma)$ after reindexing by the pairs $\{\tau(i), \tau(j)\}$ (each unordered pair appears once, and numerator and denominator flip sign together). A transposition $\tau = (a\,b)$ with $a < b$ has an odd number of inversions; counted exactly: the inverted pairs $(i, j)$ , $i < j$ , with $\tau(i) > \tau(j)$ are

(a, j) \ \text{for } a < j < b, \qquad (i, b) \ \text{for } a < i < b, \qquad (a, b) \ \text{itself},

that is $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ of them, odd. (Alternatively: check $(1\,2)$ directly, with one inversion, and conjugate — conjugates have equal signature since $\varepsilon$ is a morphism to an abelian group.) Hence $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Uniqueness. Transpositions generate $\mathfrak{S}_n$ (any cycle $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , and Theorem 1.19 finishes); a morphism to $\{\pm1\}$ is determined by its values on generators.

Consequences. The cycle identity above writes a $k$ -cycle as $k - 1$ transpositions: signature $(-1)^{k-1}$ . $A_n$ : the morphism $\varepsilon$ is surjective (transpositions exist for $n \geq 2$ ), and the two “cosets” $A_n$ and $(1\,2)A_n$ are equipotent and partition $\mathfrak{S}_n$ (Lagrange’s argument): $\abs{A_n} = \frac{n!}{2}$ . ∎

Example 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : order $\operatorname{lcm}(3,2) = 6$ , signature $(-1)^{2}\cdot(-1)^{1} = -1$ . The signature is the fastest parity check on shuffles — and the engine of the determinant in Chapter 2.

Example 1.23 (Three roads to one sign)

Let $\sigma \in \mathfrak{S}_5$ send $1, 2, 3, 4, 5$ to $3, 5, 4, 1, 2$ . Via cycles: $1 \mapsto 3 \mapsto 4 \mapsto 1$ and $2 \mapsto 5 \mapsto 2$ , so $\sigma = (1\,3\,4)(2\,5)$ and $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Via inversions: in the value list $3, 5, 4, 1, 2$ the out-of-order pairs are $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : seven of them, and $(-1)^7 = -1$ . Via transpositions: $\sigma = (1\,4)(1\,3)(2\,5)$ , three factors, $(-1)^3 = -1$ . Three computations, one parity: the uniqueness in Theorem 1.21 guarantees that no bookkeeping scheme can ever make them disagree — which is exactly what makes $\varepsilon$ usable as an invariant (see the weekend problem).

Remark 1.24 (Where the signature goes from here)

The signature is the seed of three later harvests: it builds the determinant and its product rule in Chapter 2; it powers parity invariants for combinatorial puzzles (this chapter’s weekend problem solves the fifteen puzzle with it); and the alternating groups $A_n$ it defines become central in the Year 3 volume, where their simplicity for $n \geq 5$ explains why degree- $5$ equations have no solution in radicals.

1.5 Rings, ideals, quotients

Definition 1.25 (Ideal)

Let $A$ be a commutative ring. An ideal $I \subseteq A$ is an additive subgroup such that $a x \in I$ for all $a \in A$ , $x \in I$ . Kernels of ring morphisms are ideals; $I = A$ iff $1 \in I$ iff $I$ contains a unit. The ideal generated by $x$ is $xA = \{xa\}$ (a principal ideal).

Theorem 1.26 (Ideals of $\Z$ and of $K[X]$ )

Every ideal of $\Z$ is $n\Z$ for a unique $n \in \N$ ; every ideal of $K[X]$ ( $K$ a field) is $P\,K[X]$ for a unique monic (or zero) $P$ . Consequently gcd’s exist in both rings with Bézout relations: $x\Z + y\Z = \gcd(x,y)\Z$ , and likewise for polynomials.

Proof. For $\Z$ this was the subgroup theorem of the Year 1 volume (an ideal is in particular a subgroup, and $n\Z$ is an ideal). For $K[X]$ : let $I \neq \{0\}$ be an ideal and $P \in I$ nonzero of minimal degree, normalized monic. For $F \in I$ , Euclidean division $F = PQ + R$ gives $R = F - PQ \in I$ with $\deg R < \deg P$ : minimality forces $R = 0$ , so $I = P\,K[X]$ . Uniqueness: two monic generators divide each other. The Bézout statements are the equality of the ideal $x\Z + y\Z$ (resp. its polynomial analogue) with the principal ideal of the gcd — the very definition of gcd used in Year 1, now recognized as a statement about ideals. ∎

Example 1.27 (A polynomial gcd, two ways)

Compute $\gcd(X^3 - 1,\ X^2 - 1)$ in $\Q[X]$ . By Euclid:

X^3 - 1 = X\,(X^2 - 1) + (X - 1), \qquad X^2 - 1 = (X + 1)(X - 1) + 0 ,

so the gcd is $X - 1$ , and back-substitution gives the Bézout relation

X - 1 = 1\cdot(X^3 - 1) - X\cdot(X^2 - 1).

By ideals: the ideal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ is principal (Theorem 1.26); it contains $X - 1$ (the display) and is contained in $(X - 1)\Q[X]$ (both generators vanish at $1$ , hence are multiples of $X - 1$ ): the monic generator is $X - 1$ . The closing insight: the ideal viewpoint identifies the gcd without dividing — common roots locate the ideal, and Euclid merely certifies it.

Definition 1.28 (Quotient ring $\Z/n\Z$ , revisited)

For an ideal $I$ of $A$ , the relation $x \sim y \iff x - y \in I$ is an equivalence compatible with $+$ and $\times$ ; the quotient set $A/I$ inherits a ring structure — the quotient ring — making $\pi \colon A \to A/I$ a morphism with kernel $I$ . For $A = \Z$ , $I = n\Z$ this is the $\Z/n\Z$ of the Year 1 volume, now with its universal property: any morphism killing $I$ factors through $A/I$ .

Theorem 1.29 (Chinese remainder theorem, ring form)

If $\gcd(m, n) = 1$ , the map

\Z/mn\Z \longrightarrow \Z/m\Z \times \Z/n\Z, \qquad \overline{x} \longmapsto (x \bmod m,\; x \bmod n)

is a ring isomorphism. Consequently $\varphi(mn) = \varphi(m)\varphi(n)$ for coprime $m, n$ , and

\varphi(n) = n \prod_{p \mid n} \Bigl(1 - \frac 1p\Bigr) \quad (p \text{ prime}).

Proof. The map is a well-defined ring morphism (compatibilities are immediate). Injectivity: $x \equiv 0$ mod $m$ and mod $n$ with $\gcd(m,n) = 1$ forces $mn \mid x$ (Gauss). Surjectivity: both sides have $mn$ elements, so injectivity suffices (finite equal cardinalities) — or explicitly: from a Bézout relation $um + vn = 1$ , the class of

x = b\,um + a\,vn

maps to $(a \bmod m,\ b \bmod n)$ , since $vn = 1 - um \equiv 1 \pmod m$ makes $x \equiv a \pmod m$ , and symmetrically mod $n$ — the recipe used numerically in Example 1.30. Units correspond to pairs of units (a product ring’s units are the pairs of units), so $\varphi(mn) = \varphi(m)\varphi(n)$ . For a prime power, $\varphi(p^k) = p^k - p^{k-1}$ (the non-units mod $p^k$ are the multiples of $p$ ); multiplicativity assembles the product formula. ∎

Example 1.30 (Inverting the Chinese isomorphism)

Take $m = 8$ , $n = 9$ . The inverse of the isomorphism is made explicit by the two idempotents: seek $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ and $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . From $u = 9k \equiv 1 \pmod 8$ : $k \equiv 1$ , so $u = 9$ ; from $v = 8k \equiv 1 \pmod 9$ : $-k \equiv 1$ , $k \equiv 8$ , so $v = 64$ . Then the class of $x = 9a + 64b$ modulo $72$ is the unique solution of $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : for $a = 3$ , $b = 5$ one gets $27 + 320 = 347 \equiv 59 \pmod{72}$ — exactly the intermediate value found by substitution in Exercise 1.8. The closing insight: $u$ and $v$ satisfy $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ modulo $72$ ; they are the images of $(1, 0)$ and $(0, 1)$ , and every Chinese decomposition is at bottom a decomposition of $1$ into orthogonal idempotents.

Theorem 1.31 (Euler; Fermat revisited)

The units of $\Z/n\Z$ form a group of order $\varphi(n)$ ; hence for $\gcd(a, n) = 1$ :

a^{\varphi(n)} \equiv 1 \pmod n \qquad (\text{Euler's theorem}),

and Fermat’s little theorem is the case $n = p$ prime, now one line from Lagrange.

Proof. The invertible classes are exactly those of integers coprime to $n$ (Year 1 volume): $\varphi(n)$ of them, forming a group under multiplication. Lagrange (Theorem 1.14): every element to the power of the group order is the identity. ∎

Example 1.32 (A unit group without a generator)

The group $(\Z/15\Z)^*$ has $\varphi(15) = \varphi(3)\varphi(5) = 8$ elements. Is it cyclic? Compute orders using the Chinese isomorphism $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (a unit mod $15$ is a pair of units): the factors have orders $2$ and $4$ , so every element’s order divides $\operatorname{lcm}(2, 4) = 4 < 8$ — no element generates. Concretely:

2^4 = 16 \equiv 1, \qquad 4^2 = 16 \equiv 1, \qquad 7^4 \equiv 1, \qquad 11^2 = 121 \equiv 1, \qquad 14^2 \equiv 1 \pmod{15} :

orders $4, 2, 4, 2, 2$ and never $8$ . Contrast with Exercise 1.10: $(\Z/p\Z)^*$ is cyclic for $p$ prime, because there the unit group sits inside a field. Euler’s theorem still applies with exponent $\varphi(15) = 8$ , but the true universal exponent here is $4$ — Euler is an upper bound, not always the sharp one.

Definition 1.33 (Algebra)

A $K$ -algebra is a $K$ -vector space $A$ with a ring structure whose multiplication is $K$ -bilinear. Examples: $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , function spaces $\mathcal{F}(X, K)$ , $\C$ as an $\R$ -algebra. Morphisms of algebras are linear ring morphisms; the evaluation $P \mapsto P(u)$ from $K[X]$ to $\mathcal{L}(E)$ (or $\mathcal{M}_n(K)$ ) is the central example, driving Chapter 3.

Example 1.34 (An evaluation morphism and its kernel)

Take $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ and the evaluation $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Since $A^2 = 0$ ,

P(A) = P(0)\,I + P'(0)\,A = \begin{pmatrix} P(0) & P'(0)\\ 0 & P(0)\end{pmatrix},

(only the constant and linear terms of $P$ survive). Hence $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : a principal ideal, exactly as Theorem 1.26 predicts, generated by the monic $X^2$ of least degree in the kernel — the minimal polynomial of $A$ , star of Chapter 3. The image is the two-dimensional commutative algebra $\{aI + bA\}$ : evaluation morphisms shrink the infinite-dimensional $\R[X]$ onto small, computable algebras.

Remark 1.35 (Perspectives: three melodies to listen for)

Three structural ideas from this chapter recur throughout the volume, each time in heavier orchestration. Factorization through a quotient (Definition 1.3): it builds $\Z/n\Z$ here, defines maps on solution sets of linear systems in Chapter 2, and silently underlies every “well defined on classes” argument. Invariants: the signature is a morphism to $\{\pm1\}$ that no legal move can dodge — the same logic gives the determinant’s product rule (Chapter 2), the trace’s similarity invariance, and the conserved quantities of Chapter 16. Counting against a structure: Lagrange counts through cosets, dimension counts through bases (Chapter 2), multiplicity counts through polynomial degrees (Chapter 3); whenever a bound looks miraculous, some partition or grading is doing the counting.

Remark 1.36 (Common pitfalls)

Four classics. (i) A map on a quotient must be checked well defined: “ $\overline x \mapsto$ (formula on $x$ )” is legitimate only if the formula is constant on classes — the compatibility of Definition 1.3, not a formality. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ is false in general, even for commuting elements ( $a$ and $a^{-1}$ ); Exercise 1.4 gives the correct coprime-and-commuting statement, and disjoint cycles the correct permutation version. (iii) Countability survives countable unions and finite products, but not countable products: $\{0,1\}^{\N}$ is uncountable (Exercise 1.3) although each factor has two elements. (iv) Cantor–Bernstein needs only injections both ways, but the bijection it builds is usually discontinuous and non-explicit — do not expect a formula (Example 1.11).

Remark 1.37 (Where this chapter is used)

Almost everywhere. The signature builds determinants (Chapter 2); the evaluation morphism $P \mapsto P(u)$ and the principal ideals of $K[X]$ produce minimal polynomials and the kernel decompositions of Chapter 3; countability is the stage on which Chapter 21 performs (probability on countable spaces) and the reason topology keeps producing countable dense sets (Chapter 4). The quotient construction $A/I$ is redeployed in the Year 3 volume to build fields $K[X]/(P)$ and, from them, Galois theory: the universal property proved here is used there word for word.

1.6 Exercises

Exercise 1.1 ★

Which of the following sets are countable? The set of finite subsets of $\N$ ; the set of all subsets of $\N$ ; $\R \setminus \Q$ ; the set of polynomials with rational coefficients; the set of sequences of $0$ ’s and $1$ ’s that are eventually zero.

Solution

Solution of Exercise 1.1.

Finite subsets of $\N$ : countable — the set of subsets of $\intint{0}{n}$ is finite, and the finite subsets form the countable union over $n$ of these (Proposition 1.6 (3)); infinite since it contains all singletons.

All subsets of $\N$ : not countable, by Cantor’s theorem (Theorem 1.9 (1) with $E = \N$ ).

$\R \setminus \Q$ : not countable — otherwise $\R = \Q \cup (\R\setminus\Q)$ would be a union of two countable sets, contradicting Theorem 1.9 (2).

Polynomials over $\Q$ : countable — the polynomials of degree $\leq n$ inject into $\Q^{n+1}$ (finite products of countable sets), and take the union over $n$ .

Eventually-zero binary sequences: countable — they biject with finite subsets of $\N$ (the support).

Exercise 1.2 ★

In $\mathfrak{S}_7$ , let $\sigma = (1\,4\,2\,6)(3\,5)$ and $\tau = (2\,3\,7)$ . Compute $\sigma\tau$ and $\tau\sigma$ in disjoint-cycle form, the orders and signatures of all four permutations, and $\sigma^{2026}$ .

Solution

Solution of Exercise 1.2.

Compute element by element, applying the right factor first. $\sigma\tau$ sends $1 \mapsto \sigma(1) = 4$ , $\;2 \mapsto \sigma(3) = 5$ , $\;3 \mapsto \sigma(7) = 7$ , $\;4 \mapsto \sigma(4) = 2$ , $\;5 \mapsto \sigma(5) = 3$ , $\;6 \mapsto \sigma(6) = 1$ , $\;7 \mapsto \sigma(2) = 6$ :

\sigma\tau = (1\,4\,2\,5\,3\,7\,6),

a $7$ -cycle. Likewise $\tau\sigma$ sends $1 \mapsto \tau(4) = 4$ , $\;2 \mapsto \tau(6) = 6$ , $\;3 \mapsto \tau(5) = 5$ , $\;4 \mapsto \tau(2) = 3$ , $\;5 \mapsto \tau(3) = 7$ , $\;6 \mapsto \tau(1) = 1$ , $\;7 \mapsto \tau(7) = 2$ :

\tau\sigma = (1\,4\,3\,5\,7\,2\,6),

also a $7$ -cycle (as expected: $\sigma\tau$ and $\tau\sigma$ are conjugate, hence share their cycle type).

Orders and signatures: $\sigma$ has cycle type $(4,2)$ : order $\operatorname{lcm}(4,2) = 4$ , signature $(-1)^3(-1)^1 = +1$ ; $\tau$ is a $3$ -cycle: order $3$ , signature $+1$ ; both products are $7$ -cycles: order $7$ , signature $(-1)^6 = +1$ .

$\sigma^{2026}$ : $2026 = 4 \times 506 + 2$ , so $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (square the $4$ -cycle; the transposition squares away).

Exercise 1.3 ★

Construct explicit injections showing that $\mathcal{P}(\N)$ , $\intcc{0}{1}$ and the set $\{0,1\}^{\N}$ of binary sequences are pairwise equipotent (binary expansions both ways; Cantor–Bernstein absorbs the double-representation nuisance).

Solution

Solution of Exercise 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : a sequence maps to its support — a bijection (indicator functions), no theorem needed.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : the base- $3$ map $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ is injective (two distinct sequences differ first at rank $N$ ; the tails cannot compensate a gap of $2\cdot 3^{-N-1}$ , since $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : binary expansion, choosing (say) the expansion not ending in all $1$ ’s: injective.

By Cantor–Bernstein (Theorem 1.10) applied to the last two injections, $\intcc{0}{1}$ and $\{0,1\}^{\N}$ are equipotent, hence all three sets are.

Exercise 1.4 ★

Let $G$ be a group and $a, b \in G$ commuting elements of finite coprime orders $m$ and $n$ . Prove that $\operatorname{ord}(ab) = mn$ . Show by an example in $\mathfrak{S}_3$ that commutation is essential.

Solution

Solution of Exercise 1.4.

Let $c = ab = ba$ and $d = \operatorname{ord}(c)$ . First $c^{mn} = a^{mn} b^{mn} = e$ (commutation allows splitting the power), so $d \mid mn$ . Conversely $c^d = e$ gives $a^d = b^{-d}$ ; this element lies in $\langle a\rangle \cap \langle b\rangle$ , a subgroup whose order divides both $m$ and $n$ (Lagrange in each cyclic group), hence is trivial: $a^d = b^d = e$ , so $m \mid d$ and $n \mid d$ , and by coprimality $mn \mid d$ . Hence $d = mn$ .

In $\mathfrak{S}_3$ : take $a = (1\,2)$ (order $2$ ) and $b = (1\,2\,3)$ (order $3$ ), coprime orders, which do not commute: $ab = (2\,3)$ has order $2 \neq 6$ — indeed $\mathfrak{S}_3$ has no element of order $6$ . Commutation is essential.

Exercise 1.5 ★★

Let $G$ be a finite group of even order. Prove that $G$ contains an element of order $2$ . (Pair each element with its inverse; count the self-paired ones.)

Solution

Solution of Exercise 1.5.

Pair every $x \in G$ with $x^{-1}$ . The pairs $\{x, x^{-1}\}$ with $x \neq x^{-1}$ have two elements and partition their union; the remaining elements are exactly those with $x = x^{-1}$ , i.e. $x^2 = e$ . Since $\abs G$ is even and the two-element pairs cover an even number of elements, the set $\{x : x^2 = e\}$ has even cardinality; it contains $e$ , so it contains at least one other element $x \neq e$ — an element of order $2$ .

Exercise 1.6 ★★

Prove that $A_n$ ( $n \geq 3$ ) is generated by the $3$ -cycles. (A product of two transpositions is a $3$ -cycle or a product of two $3$ -cycles.)

Solution

Solution of Exercise 1.6.

Every element of $A_n$ is a product of an even number of transpositions (Theorem 1.21: decompose into transpositions; the count is even since the signature is $+1$ ). It suffices to write each product of two transpositions with $3$ -cycles:

(a\,b)(a\,c) = (a\,c\,b), \qquad (a\,b)(c\,d) = (a\,c\,b)(a\,c\,d) \quad (\text{distinct } a,b,c,d),

(check by evaluation), and $(a\,b)(a\,b) = \mathrm{id}$ . So the $3$ -cycles generate $A_n$ .

Exercise 1.7 ★★

Determine all group morphisms: from $(\Q, +)$ to $(\Z, +)$ ; from $(\Z/n\Z, +)$ to $(\Z/m\Z, +)$ (count them: $\gcd(m,n)$ ); from $(\Q, +)$ to $(\Q_+^*, \times)$ .

Solution

Solution of Exercise 1.7.

$(\Q,+) \to (\Z,+)$ : only the zero morphism. For any $x$ and every $n \geq 1$ , $f(x) = n f\bigl(\frac xn\bigr)$ is divisible by $n$ in $\Z$ ; the only integer divisible by every $n$ is $0$ , so $f(x) = 0$ for all $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : a morphism is determined by $c = f(\overline 1)$ , which must satisfy $n c \equiv 0 \pmod m$ , i.e. $c$ is a multiple of $\frac{m}{\gcd(m,n)}$ ; there are $\gcd(m,n)$ such classes, and each choice does define a morphism (factor $k \mapsto kc$ through $\Z/n\Z$ by the universal property).

$(\Q, +) \to (\Q_+^*, \times)$ : only the trivial one. If $f(x) = y$ , then for every $n$ , $y = f(n \cdot \frac xn) = f(\frac xn)^n$ is an $n$ -th power in $\Q_+^*$ . But a rational $y \neq 1$ cannot be an $n$ -th power for all $n$ : some prime appears in $y$ with a nonzero exponent $v$ , and $n \nmid v$ for $n > \abs v$ (exponents of $n$ -th powers are multiples of $n$ , by unique factorization). Hence $f \equiv 1$ .

Exercise 1.8 ★★

Using the Chinese remainder theorem, compute $\varphi(360)$ , find all $x$ with $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ and $x \equiv 2 \pmod 5$ , and compute the last two digits of $3^{2026}$ (Euler mod $100$ ; beware: work mod $4$ and mod $25$ ).

Solution

Solution of Exercise 1.8.

$360 = 2^3 \cdot 3^2 \cdot 5$ : $\varphi(360) = 360\bigl(1 - \tfrac12\bigr)\bigl(1 - \tfrac13\bigr)\bigl(1 - \tfrac15\bigr) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 96$ .

System: moduli $8, 9, 5$ pairwise coprime, total $360$ . From $x \equiv 3 \pmod 8$ and $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ with $3 + 8k \equiv 5 \pmod 9$ , i.e. $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Then $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ , $2\ell \equiv 3 \equiv 8$ , $\ell \equiv 4 \pmod 5$ : $x \equiv 59 + 288 = 347 \pmod{360}$ .

Last two digits of $3^{2026}$ : mod $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Mod $25$ : $\varphi(25) = 20$ and $2026 = 20\cdot101 + 6$ , so $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Solve $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ : $x = 4 + 25k \equiv 1 \pmod 4$ gives $k \equiv 1 \pmod 4$ : $x \equiv 29 \pmod{100}$ . The last two digits are $29$ .

Exercise 1.9 ★★★

Prove that a finite integral domain is a field. Deduce that $\Z/n\Z$ is a field iff $n$ is prime (again).

Solution

Solution of Exercise 1.9.

Let $A$ be a finite integral domain and $a \in A$ , $a \neq 0$ . The map $x \mapsto ax$ is injective ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , no zero divisors); an injective map of a finite set to itself is surjective (Year 1 volume, the pigeonhole equivalence). So $1 = ab$ for some $b$ : every nonzero element is invertible, $A$ is a field.

$\Z/n\Z$ : if $n$ is prime it is an integral domain ( $n \mid ab \implies n \mid a$ or $n \mid b$ , Euclid’s lemma), finite, hence a field; if $n = rs$ is composite, $\overline r\,\overline s = \overline 0$ exhibits zero divisors.

Exercise 1.10 ★★★

(A classic) Let $K$ be a field and $G$ a finite subgroup of $(K^*, \times)$ . Prove that $G$ is cyclic. Hint: let $m$ be the maximal order among elements of $G$ ; show every element’s order divides $m$ (using Exercise 1.4 on suitable coprime parts), so all of $G$ satisfies $x^m = 1$ ; count roots of $X^m - 1$ . In particular $(\Z/p\Z)^*$ is cyclic.

Solution

Solution of Exercise 1.10.

Let $m = \max\{\operatorname{ord}(x) : x \in G\}$ , attained at $a$ .

Claim: every $x \in G$ has order dividing $m$ . Suppose some $x$ has order $q$ with $q \nmid m$ : then some prime power $p^k$ divides $q$ but not $m$ . Write $m = p^j m'$ with $p \nmid m'$ and $j < k$ . The element $a^{p^j}$ has order $m'$ ; the element $x^{q/p^k}$ has order $p^k$ ; these orders are coprime and the two elements commute ( $G \subseteq K^*$ is abelian), so by Exercise 1.4 their product has order $p^k m' > p^j m' = m$ : contradicting maximality.

So all $x \in G$ satisfy $x^m = 1$ : the polynomial $X^m - 1$ has at least $\abs G$ roots in the field $K$ , whence $\abs G \leq m$ (a nonzero polynomial of degree $m$ has at most $m$ roots, Year 1 volume). But $m = \operatorname{ord}(a) \leq \abs G$ by Lagrange. Hence $m = \abs G$ and $\langle a \rangle$ , of cardinality $m = \abs G$ , is all of $G$ : cyclic.

For $K = \Z/p\Z$ : $(\Z/p\Z)^*$ is a finite subgroup of $K^*$ , hence cyclic (of order $p - 1$ ).

Exercise 1.11 ★★★

Prove that the group $(\Q, +)$ is not cyclic, and worse: it is not even finitely generated. Prove on the other hand that every finitely generated subgroup of $(\Q, +)$ is cyclic.

Solution

Solution of Exercise 1.11.

Not cyclic: the subgroup $\langle \frac pq\rangle$ consists of the integer multiples of $\frac pq$ , all of which have denominator dividing $q$ (in lowest terms); it therefore misses $\frac{1}{2q}$ . No single generator can reach the unbounded denominators of $\Q$ .

Not finitely generated: the subgroup generated by $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ consists of rationals whose denominators divide $Q = q_1 \cdots q_k$ (integer combinations have denominator dividing $Q$ ): it misses $\frac{1}{2Q}$ .

Finitely generated subgroups are cyclic: with $Q$ as above, the subgroup $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ is contained in $\frac{1}{Q}\Z$ . The map $x \mapsto Qx$ is an isomorphism from $\frac1Q\Z$ onto $\Z$ carrying $H$ to a subgroup of $\Z$ , which is $n\Z$ for some $n$ (Year 1 volume): so $H = \frac{n}{Q}\Z$ is cyclic, generated by $\frac nQ$ .

Exercise 1.12 ★★

(Dedekind’s criterion) Prove that every infinite set contains a countable subset, and deduce that a set $E$ is infinite if and only if it is equipotent to a proper subset of itself. (For the direct implication, shift a countable subset by one step; for the converse, recall the pigeonhole principle.)

Solution

Solution of Exercise 1.12.

A countable subset. Let $E$ be infinite. Construct $a_0, a_1, a_2, \dots$ inductively: $E$ is nonempty, pick $a_0 \in E$ ; if $a_0, \dots, a_n$ are chosen, $E \setminus \{a_0, \dots, a_n\}$ is nonempty ( $E$ is not finite), pick $a_{n+1}$ there. The $a_n$ are pairwise distinct by construction, so $A = \{a_n : n \in \N\}$ is a countable subset of $E$ .

Infinite $\implies$ equipotent to a proper subset. Define $f \colon E \to E \setminus \{a_0\}$ by $f(a_n) = a_{n+1}$ and $f(x) = x$ for $x \notin A$ . It is injective (the two pieces are injective with disjoint images) and surjective onto $E \setminus \{a_0\}$ : every $a_{n+1}$ is hit, every $x \notin A$ is hit. So $E$ is equipotent to the proper subset $E \setminus \{a_0\}$ .

Converse. If $E$ is finite and $g \colon E \to F$ is a bijection onto $F \subseteq E$ with $F \neq E$ , then $g$ is an injection of $E$ into itself that is not surjective, contradicting the pigeonhole principle (Year 1 volume: an injective self-map of a finite set is bijective). So a set equipotent to a proper subset is infinite.

1.7 Problem: The Fifteen Puzzle

The fifteen puzzle is a $4 \times 4$ tray holding fifteen sliding tiles numbered $1$ to $15$ and one empty cell; a move slides one of the tiles adjacent to the empty cell into it. In the 1890s Sam Loyd popularized the puzzle by offering $1000 to anyone who could exchange the tiles $14$ and $15$ and return every other tile to its place. Nobody ever collected, and this weekend problem proves both halves of the reason: the signature of Theorem 1.21 forbids Loyd’s exchange, and — the harder, constructive half — everything the signature allows is genuinely solvable. The full statement is the Johnson–Story theorem (1879).

The solved configuration and Sam Loyd’s 14–15 configuration. The $1000 question: can legal slides turn the right tray into the left one? — The solved configuration and Sam Loyd’s $14$ – $15$ configuration. The $1000 question: can legal slides turn the right tray into the left one?

Problem 1.1

Weekend problem — the Johnson–Story solvability theorem

Number the cells $1$ to $16$ in reading order (left to right, top to bottom), so that cell $k$ sits in row $i$ and column $j$ with $k = 4(i - 1) + j$ . Cell $16$ (bottom right) is the home of the empty cell; we treat the empty cell as a sixteenth tile, written $b$ and identified with the number $16$ . A configuration is a bijection $\sigma \colon \intint1{16} \to \intint1{16}$ , cell $\mapsto$ content; the solved configuration is $\sigma = \mathrm{id}$ . Throughout, $\varepsilon$ is the signature of Theorem 1.21 and two cells are adjacent when they share an edge of the tray.

Part I — Configurations, moves, signatures.

Justify that the configurations are exactly the elements of $\mathfrak{S}_{16}$ , so there are $16! = 20\,922\,789\,888\,000$ of them, and that the number of legal moves from a given configuration is $2$ , $3$ or $4$ , according to whether the empty cell lies in a corner, on an edge, or in the interior.
Let $\sigma$ be a configuration, $p = \sigma^{-1}(16)$ the cell of the blank, and $c$ a cell adjacent to $p$ . Show that sliding the tile of $c$ into $p$ produces the configuration $\sigma' = \sigma \circ \tau$ with $\tau = (p\ c)$ , and deduce that every move flips the signature: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Checkerboard the tray: $\chi(k) = (-1)^{i+j}$ for the cell $k$ in row $i$ , column $j$ . Show that every move flips $\chi(\text{cell of the blank})$ , and deduce that a sequence of moves returning the blank to its starting cell has even length.
Show that

$I(\sigma) = \varepsilon(\sigma)\, \chi\bigl(\sigma^{-1}(16)\bigr)$

is invariant under every legal move, and compute $I(\mathrm{id})$ .

Part II — Loyd’s bounty: the invariant at work.

Loyd’s configuration $\sigma_L$ agrees with the solved one except that cells $14$ and $15$ hold tiles $15$ and $14$ . Compute $I(\sigma_L)$ and conclude that no sequence of moves links $\sigma_L$ to the solved configuration: Loyd’s $1000 was never in danger.
Show that exactly half of all configurations satisfy $I = +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (For a fixed blank cell, pair configurations by composing with one fixed transposition of two other cells.)
Show that every move is undone by a legal move, that “ $\sigma'$ is reachable from $\sigma$ by legal moves” is an equivalence relation, and that the class $R$ of the solved configuration satisfies $R \subseteq \{I = +1\}$ . Conclude that there are at least two classes.
Suppose the blank is home: $\sigma(16) = 16$ . Show that $I(\sigma) = \varepsilon(\rho)$ where $\rho \in \mathfrak{S}_{15}$ is the restriction of $\sigma$ to the cells $1, \dots, 15$ , and that any configuration can be carried by legal moves to one with the blank home. Conclude: to prove $R = \{I = +1\}$ it suffices to realize every even permutation of the fifteen non-home cells by a sequence of moves starting and ending with the blank home.

Part III — Blank tours and the program group. A program is a finite sequence of legal moves, started from a configuration with the blank home, whose final configuration again has the blank home. Its effect is the permutation $\pi$ of the cells defined by: the content of cell $x$ ends in cell $\pi(x)$ .

Show that a program run from $\sigma$ ends at $\sigma \circ \pi^{-1}$ ; that running two programs in succession composes their effects; and that the set $H$ of all effects is a subgroup of $\mathfrak{S}_{15}$ (permutations of the cells $1, \dots, 15$ ) contained in the alternating group $A_{15}$ .
(The elementary tour) From the blank at home, slide the blank around the bottom-right $2 \times 2$ block: cells $16 \to 12 \to 11 \to 15 \to 16$ . Show the effect is the $3$ -cycle $(11\ 12\ 15)$ , and that the reverse tour gives $(11\ 15\ 12)$ . Both lie in $H$ .
(The grand tour) Verify that

$16 \to 15 \to 14 \to 13 \to 9 \to 5 \to 1 \to 2 \to 3 \to 4 \to 8 \to 7 \to 6 \to 10 \to 11 \to 12 \to 16$

is a closed walk through all sixteen cells (adjacent steps only), and that its effect is the $15$ -cycle

$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\ 14) .$

Writing $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ for its cycle order, check that the reverse elementary tour of question 10 is exactly $(x_0\ x_1\ x_2)$ .
Prove the conjugation formula in any $\mathfrak{S}_n$ : for a permutation $g$ and a $3$ -cycle,

$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$

and note that $H$ , being a group, is closed under conjugation by its own elements.
Deduce that $H$ contains all fifteen consecutive $3$ -cycles of the grand tour:

$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z, \text{ indices mod } 15).$

Part IV — Generating the alternating group.

(Lemma A) Let $s$ and $t$ be $3$ -cycles whose supports share exactly two points, say supports $\{a, b, c\}$ and $\{b, c, d\}$ . Show that, after replacing $s$ or $t$ by its inverse if necessary (which changes nothing to the generated subgroup), the product $st$ is a double transposition; show that $A_4$ contains no subgroup of order $6$ (a subgroup of index $2$ contains every square; count the $3$ -cycles among squares); and conclude that $\langle s, t\rangle$ is the whole alternating group of the four letters $\{a, b, c, d\}$ .
(Lemma B) Let $X$ be a set of $k \geq 4$ letters, $w \notin X$ , and let $G$ be a subgroup of some $\mathfrak{S}_n$ containing every even permutation of $X$ and one $3$ -cycle $(u\ v\ w)$ with $u, v \in X$ . Show that for all distinct $a, b \in X$ there is an even permutation $g$ of $X$ with $g(u) = a$ , $g(v) = b$ , and deduce $(a\ b\ w) \in G$ .
Deduce that the group $G$ of Lemma B contains every even permutation of $X \cup \{w\}$ (use Exercise 1.6: the $3$ -cycles generate). Then, chaining Lemmas A and B along the consecutive $3$ -cycles $s_0, s_1, \dots, s_{12}$ of question 13, prove that $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Conclude that $H = A_{15}$ : every even rearrangement of the fifteen tiles is achievable by a program, and $H$ has $15!/2 = 653\,837\,184\,000$ elements.
(The Johnson–Story theorem, 1879) Assemble questions 6, 7, 8 and 17: the configurations reachable from the solved one are exactly the $16!/2 = 10\,461\,394\,944\,000$ configurations with $I = +1$ ; and reachability has exactly two classes, the class of the solved configuration and the class of Loyd’s $\sigma_L$ . (For the second point, relabel the tiles $14$ and $15$ : show $\sigma \mapsto (14\ 15) \circ \sigma$ maps move sequences to move sequences and exchanges $\{I = +1\}$ with $\{I = -1\}$ .)

Part V — Criteria, variants, and the view from above.

(The practical criterion) Read the fifteen tiles in reading order of their cells, skipping the blank, and let $N$ be the number of inversions of this list; let $r$ be the row of the blank counted from the bottom. Show that $I(\sigma) = (-1)^{N + r + 1}$ , so that $\sigma$ is solvable if and only if $N + r$ is odd.
(Group actions) An action of a group $G$ on a set $X$ is a map $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , with $e \cdot x = x$ and $g \cdot (h \cdot x) = (gh) \cdot x$ ; the orbit of $x$ is $G \cdot x$ , and the action is free when $g \cdot x = x$ forces $g = e$ . Show that $h \cdot \sigma = \sigma \circ h^{-1}$ defines a free action of $H$ on the set of blank-home configurations, that its orbits are exactly the classes of mutual reachability by programs, and recover from the orbit count that these configurations split into exactly $15!\,/\,\abs H = 2$ classes.
(The $3 \times 3$ obstruction) Show that the $3 \times 3$ board admits no closed walk visiting every cell exactly once: the grand-tour strategy of Part III fails for the eight puzzle. (Checkerboard the nine cells.)
(The repair) On the $3 \times 3$ board with cells $1$ to $9$ in reading order and home $9$ : compute the effects of the perimeter tour $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (a $7$ -cycle $\zeta'$ fixing the center $5$ ) and of the corner tour $9 \to 6 \to 5 \to 8 \to 9$ (a $3$ -cycle through the center). Conjugating the latter by the powers of $\zeta'$ and chaining Lemmas A and B, prove that the eight puzzle’s program group is all of $A_8$ , hence that exactly $9!/2 = 181\,440$ of the $9! = 362\,880$ configurations are solvable.
(A poor board) Now let the board be a single cycle of $n \geq 4$ cells carrying $n - 1$ tiles. Show that the cyclic order of the tiles is invariant, that each reachability class has exactly $n(n - 1)$ configurations (the classes are the orbits of a cyclic group of order $\operatorname{lcm}(n, n-1) = n(n-1)$ ), and that there are $(n - 2)!$ classes — for $n \geq 5$ far more than $2$ : on a thin board the parity invariant captures almost nothing, and geometry rules.
Two verdicts by the criterion of question 19: the fully reversed tray (tiles $15, 14, \dots, 1$ in cells $1$ to $15$ , blank home) and the tray with the blank in cell $1$ followed by the tiles $15, 14, \dots, 1$ in cells $2$ to $16$ . Which one is solvable?
(Synthesis) The proof has two independent pillars: an invariant ( $I$ , built from the signature morphism) showing at most half the configurations are reachable, and an explicit generation theorem ( $H = A_{15}$ ) showing at least half are. In one sentence each, say where the following entered: the morphism property of $\varepsilon$ ; Lagrange’s theorem; the generation of $A_n$ by $3$ -cycles; conjugation. State the meta-principle in one line.

Solution

Solution of Problem 1.1.

1. A configuration assigns to each of the $16$ cells one of the $16$ contents (tiles $1$ – $15$ or the blank $b = 16$ ), each exactly once: precisely a bijection $\intint1{16} \to \intint1{16}$ , an element of $\mathfrak{S}_{16}$ ; there are $16! = 20\,922\,789\,888\,000$ of them. A legal move slides one tile adjacent to the blank, so the number of moves is the number of neighbours of the blank’s cell: $2$ for the four corner cells, $3$ for the eight edge cells, $4$ for the four interior cells.

2. After the slide, cell $p$ holds the former content of $c$ and cell $c$ holds the blank; all other cells are untouched: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ , $\sigma' = \sigma$ elsewhere. That is exactly $\sigma' = \sigma \circ (p\ c)$ . Since $\varepsilon$ is a morphism and $\varepsilon\bigl((p\ c)\bigr) = -1$ : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Adjacent cells differ by one step in exactly one of the two coordinates, so $i + j$ changes parity: $\chi$ takes opposite values on adjacent cells. A move transfers the blank from $p$ to the adjacent $c$ , flipping $\chi(\text{blank cell})$ . Along a closed walk of the blank, $\chi$ is flipped once per move and returns to its initial value: the number of moves is even.

4. By questions 2 and 3, one move flips both factors of $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ ; their product is unchanged. For the solved configuration: $\varepsilon(\mathrm{id}) = +1$ and the blank is at cell $16$ , row $4$ , column $4$ : $\chi(16) = (-1)^{8} = +1$ , so $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ is the transposition $(14\ 15)$ of cells: $\varepsilon(\sigma_L) = -1$ ; its blank is home, $\chi(16) = +1$ : $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Since $I$ is preserved by every move, no sequence of moves joins $\sigma_L$ and $\mathrm{id}$ . The prize was structurally safe.

6. Fix a cell $p$ and two other cells $c \neq d$ distinct from $p$ , and set $\tau_0 = (c\ d)$ . On the set of configurations with blank at $p$ , the map $\sigma \mapsto \sigma \circ \tau_0$ is an involution (it preserves $\sigma(p) = 16$ since $\tau_0$ fixes $p$ ) and flips $\varepsilon$ , hence flips $I$ : it pairs the configurations with $I = +1$ bijectively with those with $I = -1$ . So each of the $16$ blank positions contributes $15!/2$ configurations with $I = +1$ , and

\abs{\{I = +1\}} = 16 \cdot \frac{15!}{2} = \frac{16!}{2}.

7. The move sliding the tile of $c$ into $p$ is undone by sliding that same tile (now in $p$ ) back into $c$ : composing with $(p\ c)$ twice is the identity. Hence: reflexivity (empty sequence), symmetry (reverse the sequence, undoing each move), transitivity (concatenate): an equivalence relation. Every $\sigma \in R$ has $I(\sigma) = I(\mathrm{id}) = +1$ by question 4, so $R \subseteq \{I = +1\}$ ; and $\sigma_L \notin R$ gives a second class.

8. If $\sigma(16) = 16$ , then $\sigma$ permutes the cells $1, \dots, 15$ ; call $\rho$ this restriction. Appending a fixed point changes neither the cycle type nor the signature (decompose $\rho$ into transpositions; the same product works in $\mathfrak{S}_{16}$ ), so $\varepsilon(\sigma) = \varepsilon(\rho)$ , and $\chi(16) = +1$ gives $I(\sigma) = \varepsilon(\rho)$ . Any configuration can be carried to a blank-home one: the grid is connected, so walk the blank along a path of adjacent cells to cell $16$ (each step is a legal move). Now suppose every even $\rho \in \mathfrak{S}_{15}$ is realized by a program. Given $\sigma$ with $I(\sigma) = +1$ : walk the blank home to reach $\widetilde\sigma$ (equivalent to $\sigma$ ), with $I(\widetilde\sigma) = +1$ , i.e. its restriction $\rho$ is even; the program realizing $\rho$ carries $\widetilde\sigma$ to $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (see question 9). By transitivity $\sigma \in R$ , whence $\{I = +1\} \subseteq R$ and equality.

9. Single move: the content of $c$ ends in $p$ and the blank in $c$ : the effect is $\pi = (p\ c)$ , and indeed $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Induction: if a sequence has effect $\pi_1$ and carries $\sigma$ to $\sigma \circ \pi_1^{-1}$ , following it with a move of effect $\pi_2 = (p'\ c')$ yields $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , and contents move by $\pi_2 \circ \pi_1$ (first $\pi_1$ , then $\pi_2$ ). So effects compose, and a program run from $\sigma$ ends at $\sigma \circ \pi^{-1}$ . Subgroup: the empty program has effect $\mathrm{id}$ ; concatenation gives products; reversing a program (question 7) gives inverses. A program’s effect fixes cell $16$ (blank starts and ends home), so $H \leq \mathfrak{S}_{15}$ . Evenness: a program of $k$ moves has $k$ even (question 3), and $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ forces $\varepsilon(\pi) = +1$ : $H \subseteq A_{15}$ .

10. Track the four slides from the blank at $16$ : move $16 \to 12$ sends the content of $12$ to $16$ ; move $12 \to 11$ sends the content of $11$ to $12$ ; move $11 \to 15$ sends the content of $15$ to $11$ ; move $15 \to 16$ sends the content parked in $16$ (originally in $12$ ) to $15$ . Net: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , blank home: the effect is $(11\ 12\ 15)$ . The reverse tour undoes it: effect $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Both are effects of programs, hence in $H$ .

11. Adjacency of consecutive cells: within each listed pair the cells differ by $1$ in the same row ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) or by $4$ within a column ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): a closed walk through all $16$ cells, of length $16$ . Effect: as in question 10, writing the visited cells $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ : the content of $c_i$ moves to $c_{i-1}$ for $i = 2, \dots, 15$ , and the content of $c_1$ , parked in $16$ after the first move, is carried to $c_{15}$ by the last move. So the effect maps $15 \mapsto 12$ , and $14 \mapsto 15$ , $13 \mapsto 14$ , $9 \mapsto 13$ , $5 \mapsto 9$ , $1 \mapsto 5$ , $2 \mapsto 1$ , $3 \mapsto 2$ , $4 \mapsto 3$ , $8 \mapsto 4$ , $7 \mapsto 8$ , $6 \mapsto 7$ , $10 \mapsto 6$ , $11 \mapsto 10$ , $12 \mapsto 11$ : exactly the $15$ -cycle $\zeta$ . Its cycle order starts $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , and $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ maps $15 \mapsto 12 \mapsto 11 \mapsto 15$ — which is precisely $(11\ 15\ 12)$ , the reverse elementary tour.

12. Let $\gamma = (a\ b\ c)$ and $x \in \intint1n$ . If $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; likewise $g(b) \mapsto g(c)$ and $g(c) \mapsto g(a)$ . If $x \notin \{g(a), g(b), g(c)\}$ , then $g^{-1}(x) \notin \{a,b,c\}$ is fixed by $\gamma$ , so $x$ is fixed. Hence $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . And for $g, h \in H$ , $ghg^{-1} \in H$ by the subgroup axioms.

13. $\zeta \in H$ (question 11) and $s_0 = (x_0\ x_1\ x_2) \in H$ (questions 10–11). Since $\zeta(x_i) = x_{i+1}$ (indices mod $15$ ), question 12 gives

\zeta^{t}\,s_0\,\zeta^{-t} = \bigl(\zeta^t(x_0)\ \zeta^t(x_1)\ \zeta^t(x_2)\bigr) = (x_t\ x_{t+1}\ x_{t+2}) = s_t \in H \qquad (t = 0, 1, \dots, 14).

14. Up to inverting, assume $s = (a\ b\ c)$ and $t = (b\ c\ d)$ (a $3$ -cycle on $\{a,b,c\}$ is $(a\ b\ c)$ or its inverse; likewise on $\{b,c,d\}$ ; replacing a generator by its inverse leaves $\langle s, t\rangle$ unchanged). Then, applying $t$ first,

st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad d \mapsto c, \qquad\text{i.e.}\quad st = (a\ b)(c\ d),

a double transposition. The subgroup $G = \langle s, t\rangle$ consists of even permutations of the four letters, so $G \leq A_4$ and $\abs G \mid 12$ ; it contains an element of order $3$ and one of order $2$ , so $6 \mid \abs G$ (Lagrange, Theorem 1.14, applied to the two cyclic subgroups). If $A_4$ had a subgroup $K$ of order $6$ , it would have index $2$ , and then $g^2 \in K$ for every $g \in A_4$ : for $g \in K$ this is clear; for $g \notin K$ the only cosets are $K$ and $gK$ , so the coset $g^2K$ is $K$ or $gK$ , and $g^2K = gK$ would force $g \in K$ . So every square lies in $K$ . But every $3$ -cycle $\gamma$ is a square, $\gamma = (\gamma^2)^2$ , and $A_4$ contains eight $3$ -cycles: $8 > 6$ , contradiction. Hence $\abs G = 12$ : $G = A_4$ .

15. Extend $u \mapsto a$ , $v \mapsto b$ to a bijection $g_0$ of $X$ (send the remaining $k - 2$ letters bijectively anywhere onto the complement of $\{a, b\}$ ). If $g_0$ is odd, pick two distinct letters $s_1, t_1 \in X \setminus \{u, v\}$ (possible: $k \geq 4$ ) and replace $g_0$ by $g_0 \circ (s_1\ t_1)$ , which is even and still maps $u \mapsto a$ , $v \mapsto b$ . Extend by the identity off $X$ : an even permutation $g \in G$ (it is an even permutation of $X$ ). Then question 12:

g\,(u\ v\ w)\,g^{-1} = (g(u)\ g(v)\ g(w)) = (a\ b\ w) \in G,

using $g(w) = w$ .

16. Every $3$ -cycle of $X \cup \{w\}$ lies in $G$ : those supported in $X$ are even permutations of $X$ ; one with support $\{a, b, w\}$ is $(a\ b\ w)$ or $(b\ a\ w)$ , both delivered by question 15. By Exercise 1.6, the $3$ -cycles of the $(k+1)$ -element set $X \cup \{w\}$ generate its alternating group, so $G$ contains every even permutation of $X \cup \{w\}$ . Chaining: let $G = \langle s_0, \dots, s_{12}\rangle$ . Lemma A applied to $s_0 = (x_0\ x_1\ x_2)$ and $s_1 = (x_1\ x_2\ x_3)$ (supports share $\{x_1, x_2\}$ ) gives all even permutations of $X_4 = \{x_0, x_1, x_2, x_3\}$ . If $G$ contains all even permutations of $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), then $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ has $u = x_{m-2}, v = x_{m-1} \in X_m$ and new letter $w = x_m$ : Lemma B and the first part give all even permutations of $X_{m+1}$ . Induction up to $m = 14$ : $G \supseteq A_{15}$ (even permutations of all fifteen cells), and $G \subseteq A_{15}$ since each $s_t$ is even: $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Questions 13 and 16: $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; question 9: $H \subseteq A_{15}$ . So $H = A_{15}$ , of order $15!/2 = 653\,837\,184\,000$ : every even rearrangement of the fifteen tiles is the effect of a program.

18. Question 8 reduced $R = \{I = +1\}$ to realizing every even $\rho \in \mathfrak{S}_{15}$ by a program: done by question 17. With question 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Two classes: let $t_0 = (14\ 15)$ act on contents: $\varphi(\sigma) = t_0 \circ \sigma$ . A legal move from $\sigma$ is a legal move from $\varphi(\sigma)$ (the blank cell is unchanged: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , and the moved cell is the same), and $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ maps move sequences to move sequences, bijectively (it is an involution). It flips $I$ : $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , same blank cell. Hence $\varphi$ maps the class $R = \{I = +1\}$ of $\mathrm{id}$ bijectively onto the class of $\varphi(\mathrm{id}) = \sigma_L$ , which is therefore all of $\{I = -1\}$ : exactly two classes. This is the Johnson–Story theorem.

19. Index the cells in reading order and let $k = 4(i - 1) + j$ be the blank’s cell. Count the inversions of $\sigma$ (pairs of cells $x < y$ with $\sigma(x) > \sigma(y)$ ): pairs of two tile cells contribute $N$ ; pairs involving the blank: cells after the blank all hold tiles $< 16$ , each inverted ( $16 - k$ pairs), cells before it are never inverted. So $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Since $k = 4(i-1) + j \equiv j \pmod 2$ ,

I(\sigma) = (-1)^{N + j}\,(-1)^{i + j} = (-1)^{N + i} = (-1)^{N + r + 1}

using $i = 5 - r$ . By question 18, $\sigma$ is solvable iff $I(\sigma) = +1$ iff $N + r$ is odd. Check: solved, $N = 0$ , $r = 1$ : odd, solvable; Loyd, $N = 1$ , $r = 1$ : even, unsolvable.

20. Action: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ and $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; and $\sigma \circ h^{-1}$ is again a blank-home configuration ( $h$ fixes cell $16$ ). Free: $\sigma \circ h^{-1} = \sigma$ gives $h^{-1} = \mathrm{id}$ (compose with $\sigma^{-1}$ ). Orbits = program classes: question 9 says the configurations reachable from $\sigma$ by programs are exactly the $\sigma \circ \pi^{-1}$ , $\pi \in H$ : the orbit $H \cdot \sigma$ . Count: freeness makes $h \mapsto h \cdot \sigma$ injective, so every orbit has $\abs H = 15!/2$ elements; the $15!$ blank-home configurations therefore split into $15!\,/\,(15!/2) = 2$ orbits — the blank-home shadow of the two Johnson–Story classes.

21. The $3 \times 3$ grid is bipartite for the checkerboard colouring: every step of a walk changes colour, so every closed walk has even length. A closed walk visiting each of the $9$ cells exactly once would have length $9$ , odd: impossible. The grand-tour construction of Part III is therefore unavailable on the eight puzzle.

22. Perimeter tour $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (all steps adjacent; length $8$ , even): by the bookkeeping of question 11 with $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ , the effect is

\zeta' = (8\ 6\ 3\ 2\ 1\ 4\ 7),

a $7$ -cycle fixing the center $5$ (content of $7$ moves to $8$ , of $4$ to $7$ , of $1$ to $4$ , of $2$ to $1$ , of $3$ to $2$ , of $6$ to $3$ , and of $8$ to $6$ ). Corner tour $9 \to 6 \to 5 \to 8 \to 9$ : effect $(6\ 8\ 5)$ (content of $5$ moves to $6$ , of $8$ to $5$ , of $6$ — parked at $9$ — to $8$ ). Set $y_t = \zeta'^{\,t}(8)$ : $y_0 = 8, y_1 = 6, y_2 = 3, y_3 = 2, y_4 = 1, y_5 = 4, y_6 = 7$ . Conjugation (question 12):

\zeta'^{\,t}\,(6\ 8\ 5)\,\zeta'^{-t} = (y_{t+1}\ y_t\ 5) =: T_t \in H_{3\times3},

since $\zeta'$ fixes $5$ . The supports of $T_0 = (y_1\ y_0\ 5)$ and $T_1 = (y_2\ y_1\ 5)$ share exactly $\{y_1, 5\}$ : Lemma A gives all even permutations of $\{y_0, y_1, y_2, 5\}$ . Then $T_2 = (y_3\ y_2\ 5)$ adjoins $y_3$ by Lemma B (its letters $y_2, 5$ lie in the current set, $k = 4$ ), and $T_3, T_4, T_5$ adjoin $y_4, y_5, y_6$ in turn: all even permutations of the eight non-home cells lie in the program group, which also consists of even permutations (the argument of question 9 is board-independent). So $H_{3\times3} = A_8$ , and the reasoning of questions 6, 8, 18 — also board-independent — shows the reachable configurations are exactly those with $I = +1$ : half of $9!$ , i.e. $181\,440$ .

23. Label the cells $0, \dots, n-1$ around the cycle. A move swaps the blank with one of its two neighbours. Read the tiles in cyclic order starting just after the blank: a word $w$ listing the $n - 1$ tiles. Moving the blank one step forward replaces $(p, w)$ by $(p + 1, \rho w)$ , where $p$ is the blank cell and $\rho$ cyclically rotates the word by one; the backward move is the inverse. The cyclic order of the tiles (the word up to rotation) is thus invariant. The reachable class of $(p, w)$ is the orbit of the map $g \colon (p, w) \mapsto (p+1, \rho w)$ , an element of order $\operatorname{lcm}(n, n-1) = n(n-1)$ in the product of the two cyclic groups (translations of $\Z/n\Z$ and rotations of the $n-1$ word positions), the lcm being $n(n-1)$ because $\gcd(n, n-1) = 1$ : each class has exactly $n(n-1)$ configurations, all with the same necklace. Classes: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . For $n \geq 5$ , $(n-2)! > 2$ : the parity invariant (two classes at best) is blind to almost all of the obstruction; the wealth of the $4 \times 4$ board — where parity is the only obstruction — is a genuinely geometric fact, not a formal one.

24. Both trays have the tiles in fully reversed order, so $N = \binom{15}{2} = 105$ in both cases (every pair of tiles is inverted). Blank home: $r = 1$ , $N + r = 106$ even: unsolvable. Blank in cell $1$ : the blank is in the top row, $r = 4$ , $N + r = 109$ odd: solvable. Two trays that differ only by where the hole sits fall on opposite sides of the wall.

25. Morphism property: it converts “one move = one transposition” into “one move = one sign flip” (questions 2, 4), making $I$ computable move by move. Lagrange: it forced $6 \mid \abs{\langle s, t\rangle}$ in Lemma A and sized the cosets in the order- $6$ exclusion (question 14). Generation by $3$ -cycles: it converted “ $H$ contains enough $3$ -cycles” into “ $H$ contains all of $A_{15}$ ” (question 16). Conjugation: it manufactured the fifteen consecutive $3$ -cycles from a single $2 \times 2$ tour transported by the grand tour (questions 12–13), and the $3$ -cycles $(a\ b\ w)$ in Lemma B. Meta-principle: an invariant proves impossibility, an explicit construction proves possibility, and a problem is fully solved exactly when the two bounds meet — here, at one half.