Vokint's StudyLog

Posts 01 and 02 studied groups one at a time: their elements, subgroups, cosets and quotients. This post studies the maps between groups and the ways a group can move a set. Homomorphisms explain what quotient groups really are (every quotient is the image of a homomorphism, and every image is a quotient). Group actions turn a group into a counting machine: the orbit–stabilizer theorem, the class equation and Burnside's lemma all come from one idea. The payoff is the Sylow theorems, which let you prove facts such as "every group of order 15 is cyclic" using nothing but divisibility. The chapter closes with the classification of finite abelian groups. > Series map: 00 Integers, Relations & Modular Arithmetic → 01 Groups & Subgroups → 02 Cosets, Lagrange & Quotient Groups → 03 Homomorphisms, Group Actions & Sylow (this post) → 04 Rings, Ideals & Fields → 05 Field Extensions & Galois Theory. Learning Outcome - Define a group homomorphism, its kernel and its image, and prove that the kernel is a normal subgroup.- Decide whether two groups are isomorphic by comparing invariants (order, element orders, abelian or not).- Prove that $\operatorname{Aut}(\mathbb{Z}/n\mathbb{Z}) \cong (\mathbb{Z}/n\mathbb{Z})^\times$.- State and prove the First Isomorphism Theorem, and state the Second, Third and Correspondence theorems.- Prove Cayley's theorem: every group is a group of permutations.- Define a group action, orbits and stabilizers, and prove the orbit–stabilizer theorem.- Derive the class equation and use it to prove that a $p$-group has a nontrivial center.- Count colourings up to symmetry with Burnside's lemma.- State Cauchy's and Sylow's theorems and use them to analyse groups of order 12, 15 and 20.- List all abelian groups of a given order, in both elementary-divisor and invariant-factor form. Chapter 1 — Homomorphisms Terminology - Homomorphism — a map $\varphi : G \to H$ between groups with $\varphi(ab) = \varphi(a)\varphi(b)$ for all $a, b \in G$. The product on the left is in $G$, the one on the right is in $H$.- Kernel — $\ker \varphi = \{ g \in G : \varphi(g) = eH \}$, the elements sent to the identity.- Image — $\operatorname{im} \varphi = \varphi(G) = \{ \varphi(g) : g \in G \}$.- Monomorphism / epimorphism — an injective / surjective homomorphism.- Isomorphism — a bijective homomorphism. Write $G \cong H$ when one exists.- Automorphism — an isomorphism $G \to G$. The automorphisms of $G$ form a group $\operatorname{Aut}(G)$ under composition.- Inner automorphism — conjugation by a fixed element: $cg(x) = gxg^{-1}$. First properties Let $\varphi : G \to H$ be a homomorphism. Then: 1. $\varphi(eG) = eH$. Proof: $\varphi(e) = \varphi(ee) = \varphi(e)\varphi(e)$; multiply both sides by $\varphi(e)^{-1}$.2. $\varphi(g^{-1}) = \varphi(g)^{-1}$. Proof: $\varphi(g)\varphi(g^{-1}) = \varphi(gg^{-1}) = \varphi(e) = eH$.3. $\varphi(g^k) = \varphi(g)^k$ for every integer $k$ (induction, plus property 2 for negative $k$).4. If $g$ has finite order $n$, then the order of $\varphi(g)$ divides $n$, because $\varphi(g)^n = \varphi(g^n) = eH$.5. $\ker \varphi$ is a subgroup of $G$ and $\operatorname{im}\varphi$ is a subgroup of $H$. Property 4 is the workhorse for ruling maps out. There is no nontrivial homomorphism $\mathbb{Z}/3\mathbb{Z} \to \mathbb{Z}/4\mathbb{Z}$: the image of the generator would need an order dividing both 3 and 4, so it is the identity. Examples worth knowing | Homomorphism | Kernel | Image ||---|---|---|| $\det : GLn(\mathbb{R}) \to \mathbb{R}^\times$ | $SLn(\mathbb{R})$ | all of $\mathbb{R}^\times$ || $\operatorname{sgn} : Sn \to \{\pm 1\}$, $n \ge 2$ | $An$ | $\{\pm 1\}$ || $\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$, $k \mapsto k \bmod n$ | $n\mathbb{Z}$ | all of $\mathbb{Z}/n\mathbb{Z}$ || $\exp : (\mathbb{R}, +) \to (\mathbb{R}{>0}, \cdot)$ | $\{0\}$ | all of $\mathbb{R}{>0}$ (isomorphism) || $(\mathbb{R}, +) \to S^1$, $t \mapsto e^{2\pi i t}$ | $\mathbb{Z}$ | the unit circle $S^1$ || $cg : G \to G$, $x \mapsto gxg^{-1}$ | $\{e\}$ | $G$ (automorphism) | Homomorphisms out of a cyclic group. A homomorphism $\varphi : \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z}$ is fixed by $a = \varphi(1)$, since $\varphi(k) = ka$. The only condition is that $n \cdot 1 = 0$ must go to $0$, that is $na \equiv 0 \pmod m$. The solutions are the multiples of $m/\gcd(n,m)$, so there are exactly $\gcd(n, m)$ homomorphisms. For $n = 12$, $m = 18$: $12a \equiv 0 \pmod{18}$ holds for $a \in \{0, 3, 6, 9, 12, 15\}$, which is $\gcd(12, 18) = 6$ maps. > Common pitfall: "$k \mapsto k \bmod m$" is not a well-defined map $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z}$ unless $m \mid n$. In $\mathbb{Z}/4\mathbb{Z}$, $0 = 4$, but $0 \bmod 3 \ne 4 \bmod 3$. Always check that a map defined on representatives does not depend on the representative chosen. Kernels are normal, and injectivity Theorem. If $\varphi : G \to H$ is a homomorphism, then $\ker\varphi$ is a normal subgroup of $G$. Proof. It is a subgroup: $\varphi(e) = e$; if $\varphi(a) = \varphi(b) = e$ then $\varphi(ab^{-1}) = \varphi(a)\varphi(b)^{-1} = e$. It is normal: for $k \in \ker\varphi$ and any $g \in G$, $$\varphi(gkg^{-1}) = \varphi(g)\,\varphi(k)\,\varphi(g)^{-1} = \varphi(g)\,e\,\varphi(g)^{-1} = e,$$ so $gkg^{-1} \in \ker\varphi$. ∎ Theorem. $\varphi$ is injective if and only if $\ker\varphi = \{e\}$. Proof. If $\varphi$ is injective, only $e$ maps to $e$. Conversely, if $\ker\varphi = \{e\}$ and $\varphi(a) = \varphi(b)$, then $\varphi(ab^{-1}) = e$, so $ab^{-1} = e$ and $a = b$. ∎ More precisely, the fibres of $\varphi$ are exactly the cosets of the kernel: $\varphi(a) = \varphi(b)$ if and only if $a\ker\varphi = b\ker\varphi$. This is the whole content of the First Isomorphism Theorem in Chapter 2. Isomorphism invariants Isomorphic groups are "the same group with renamed elements", so any property defined only from the group operation is shared. To prove two groups are not isomorphic, find a property one has and the other lacks: - the order $|G|$;- being abelian or cyclic;- the number of elements of each order;- the size of the center, the number of subgroups of a given order, and so on. $\mathbb{Z}/4\mathbb{Z}$ has an element of order 4; in $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ every non-identity element has order 2. So they are not isomorphic, although both have order 4 and are abelian. On the other hand $\mathbb{Z}/6\mathbb{Z} \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$ via $k \mapsto (k \bmod 2, k \bmod 3)$; this is the Chinese Remainder Theorem from post 00. In general $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ is cyclic if and only if $\gcd(m, n) = 1$. > Watch out: to prove two groups are isomorphic you must produce a map and check it. Matching every invariant you can think of is evidence, not proof. Automorphisms of cyclic groups Theorem. $\operatorname{Aut}(\mathbb{Z}/n\mathbb{Z}) \cong (\mathbb{Z}/n\mathbb{Z})^\times$, the group of units modulo $n$. In particular $\lvert\operatorname{Aut}(\mathbb{Z}/n\mathbb{Z})\rvert = \phi(n)$, Euler's totient function from post 00. (This post writes Euler's function as $\phi$ to keep $\varphi$ free for homomorphisms.) Proof. Every endomorphism of $\mathbb{Z}/n\mathbb{Z}$ is $\mua(k) = ak$ for $a = \mua(1)$ (see "Homomorphisms out of a cyclic group" with $m = n$). The map $\mua$ is a bijection exactly when its image contains $1$, that is when $ab \equiv 1 \pmod n$ for some $b$, that is when $a$ is a unit. Define $\Psi : (\mathbb{Z}/n\mathbb{Z})^\times \to \operatorname{Aut}(\mathbb{Z}/n\mathbb{Z})$, $a \mapsto \mua$. It is surjective by what was just said and injective since $\mua(1) = a$ recovers $a$. It is a homomorphism because $\mua \circ \mub (k) = abk = \mu{ab}(k)$. ∎ Example: $(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$ and each element squares to $1$ ($3^2 = 9$, $5^2 = 25$, $7^2 = 49$ are all $\equiv 1$). So $\operatorname{Aut}(\mathbb{Z}/8\mathbb{Z}) \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$, not cyclic. In the other direction, $\operatorname{Aut}(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}) \cong S3$: an automorphism may permute the three non-identity elements in any of the $3! = 6$ ways. Inner automorphisms. The map $G \to \operatorname{Aut}(G)$, $g \mapsto cg$, is a homomorphism ($cg ch = c{gh}$). Its kernel is the set of $g$ with $gxg^{-1} = x$ for all $x$, which is the center $Z(G)$ from post 02. Its image is $\operatorname{Inn}(G)$. By the First Isomorphism Theorem (next chapter), $\operatorname{Inn}(G) \cong G/Z(G)$. For $D4$ (order 8) the center is $\{e, r^2\}$, so $\operatorname{Inn}(D4)$ has order $8/2 = 4$. Chapter 2 — The isomorphism theorems The First Isomorphism Theorem Theorem (First Isomorphism Theorem). Let $\varphi : G \to H$ be a homomorphism with kernel $K$. Then $K$ is normal in $G$ and $$G/K \;\cong\; \operatorname{im}\varphi, \qquad gK \mapsto \varphi(g).$$ Proof. Normality of $K$ was proved in Chapter 1. Define $\bar\varphi : G/K \to \operatorname{im}\varphi$ by $\bar\varphi(gK) = \varphi(g)$. - Well defined. If $gK = g'K$ then $g' = gk$ for some $k \in K$, so $\varphi(g') = \varphi(g)\varphi(k) = \varphi(g)$.- Homomorphism. $\bar\varphi(gK \cdot g'K) = \bar\varphi(gg'K) = \varphi(gg') = \varphi(g)\varphi(g') = \bar\varphi(gK)\,\bar\varphi(g'K)$.- Injective. If $\bar\varphi(gK) = e$ then $\varphi(g) = e$, so $g \in K$ and $gK = K$, the identity of $G/K$. A homomorphism with trivial kernel is injective.- Surjective. Every element of $\operatorname{im}\varphi$ is $\varphi(g) = \bar\varphi(gK)$. ∎ Read it as a factorisation: every homomorphism is "quotient map, then isomorphism, then inclusion", $G \to G/K \xrightarrow{\;\cong\;} \operatorname{im}\varphi \hookrightarrow H$. For finite $G$ it also gives the counting rule $|G| = |\ker\varphi| \cdot |\operatorname{im}\varphi|$. Worked applications of the table in Chapter 1: - $GLn(\mathbb{R}) / SLn(\mathbb{R}) \cong \mathbb{R}^\times$ (via $\det$).- $Sn / An \cong \{\pm 1\} \cong \mathbb{Z}/2\mathbb{Z}$ (via $\operatorname{sgn}$), so $[Sn : An] = 2$ and $|An| = n!/2$.- $\mathbb{Z}/n\mathbb{Z}$ really is $\mathbb{Z}$ modulo the kernel $n\mathbb{Z}$ of reduction.- $\mathbb{R}/\mathbb{Z} \cong S^1$ (via $t \mapsto e^{2\pi i t}$): "the real line wrapped around a circle". > Trick: to identify a quotient $G/N$, do not work with cosets directly. Find a surjective homomorphism out of $G$ whose kernel is exactly $N$; its target is the answer. The Second and Third Isomorphism Theorems Theorem (Second, or "diamond"). Let $H \le G$ and $N \trianglelefteq G$. Then $HN$ is a subgroup of $G$, $H \cap N$ is normal in $H$, and $$HN/N \;\cong\; H/(H \cap N).$$ (Proof idea: $H \to HN/N$, $h \mapsto hN$, is surjective with kernel $H \cap N$; apply the First theorem.) For finite groups it gives $|HN| = |H|\,|N| / |H \cap N|$. Theorem (Third). Let $N \subseteq K$ be normal subgroups of $G$. Then $K/N$ is normal in $G/N$ and $$(G/N)\big/(K/N) \;\cong\; G/K.$$ (Proof idea: $G/N \to G/K$, $gN \mapsto gK$, is well defined and surjective with kernel $K/N$.) Example: $(\mathbb{Z}/12\mathbb{Z}) / (4\mathbb{Z}/12\mathbb{Z}) \cong \mathbb{Z}/4\mathbb{Z}$. The subgroup $4\mathbb{Z}/12\mathbb{Z} = \{0, 4, 8\}$ has order 3, and $12/3 = 4$. Theorem (Correspondence). Let $N \trianglelefteq G$ and $\pi : G \to G/N$ the quotient map. Then $K \mapsto K/N = \pi(K)$ is a bijection between subgroups $K$ of $G$ that contain $N$ and subgroups of $G/N$. It preserves inclusion, indices ($[G:K] = [G/N : K/N]$) and normality. So the subgroup lattice of $G/N$ is exactly the part of the lattice of $G$ that sits above $N$. Cayley's theorem Theorem (Cayley). Every group $G$ is isomorphic to a subgroup of the symmetric group $\operatorname{Sym}(G)$. If $|G| = n$, then $G$ is isomorphic to a subgroup of $Sn$. Proof. For $g \in G$ let $\lambdag : G \to G$, $\lambdag(x) = gx$. It is a bijection with inverse $\lambda{g^{-1}}$, so $\lambdag \in \operatorname{Sym}(G)$. The map $\Lambda : G \to \operatorname{Sym}(G)$, $g \mapsto \lambdag$, is a homomorphism because $\lambdag\lambdah(x) = g(hx) = (gh)x = \lambda{gh}(x)$. Its kernel is trivial: if $\lambdag$ is the identity then $g = ge = \lambdag(e) = e$. By the First Isomorphism Theorem $G \cong \operatorname{im}\Lambda \le \operatorname{Sym}(G)$. ∎ Cayley's theorem is historically important (it says the abstract definition of a group loses nothing compared with "groups of permutations") but it is wasteful: it embeds a group of order 8 in $S8$, of order 40320. Group actions on smaller sets give much better information, which is the next chapter. Chapter 3 — Group actions Terminology - Action — a group $G$ acts on a set $X$ if there 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$.- Permutation representation — equivalently, a homomorphism $\rho : G \to \operatorname{Sym}(X)$, with $\rho(g)(x) = g\cdot x$. The two descriptions are the same thing.- Faithful action — one whose homomorphism $\rho$ is injective (only $e$ acts as the identity).- Orbit — $G\cdot x = \{ g\cdot x : g \in G \}$, everywhere $x$ can be moved to.- Stabilizer — $Gx = \{ g \in G : g\cdot x = x \}$, the elements that fix $x$. It is a subgroup of $G$.- Transitive action — one with a single orbit.- Fixed set — $X^g = \{ x \in X : g\cdot x = x \}$, the points a given $g$ fixes. Examples 1. $Sn$ acts on $\{1, \dots, n\}$ by $\sigma\cdot i = \sigma(i)$. Transitive and faithful.2. $D4$ (order 8, the symmetries of a square, notation from post 01) acts on the four vertices. Label them $1, 2, 3, 4$ counter-clockwise; then $r = (1\,2\,3\,4)$ and, taking $s$ to be the reflection in the diagonal through vertices 1 and 3, $s = (2\,4)$.3. The rotation group of a cube (24 elements) acts on the 6 faces, the 8 vertices and the 12 edges.4. Any group acts on itself by left multiplication, $g\cdot x = gx$ (this is Cayley's action), and on the left cosets $G/H$ by $g\cdot xH = gxH$.5. Any group acts on itself by conjugation, $g\cdot x = gxg^{-1}$. Orbits are conjugacy classes $\operatorname{cl}(x)$, and the stabilizer of $x$ is the centralizer $CG(x) = \{ g : gx = xg \}$. The orbits of an action partition $X$: the relation "$y = g\cdot x$ for some $g$" is an equivalence relation (reflexive via $e$, symmetric via $g^{-1}$, transitive via products), and orbits are its classes (equivalence relations are from post 00). The orbit–stabilizer theorem Theorem (orbit–stabilizer). Let a finite group $G$ act on $X$ and let $x \in X$. Then $$|G\cdot x| \;=\; [G : Gx] \;=\; \frac{|G|}{|Gx|}.$$ Proof. Define $f$ from the set of left cosets of $Gx$ to the orbit by $f(gGx) = g\cdot x$. - Well defined and injective. For $g, h \in G$: $g\cdot x = h\cdot x \iff h^{-1}g\cdot x = x \iff h^{-1}g \in Gx \iff gGx = hGx$. Reading the chain left to right gives injectivity; right to left gives well-definedness.- Surjective. Every orbit element is $g\cdot x = f(gGx)$. So the orbit is in bijection with the cosets of $Gx$, and there are $[G:Gx] = |G|/|Gx|$ of them by Lagrange's theorem (post 02). ∎ Worked example: $D4$ on the square. The orbit of vertex 1 is all four vertices (rotations reach each one). The stabilizer of vertex 1 is $\{e, s\}$: the only non-identity symmetry fixing vertex 1 is the reflection in the diagonal through it. So $|G\cdot 1| \cdot |G1| = 4 \cdot 2 = 8 = |D4|$. The proof's bijection is concrete here. The four cosets of $\{e, s\}$ are $\{e, s\}$, $\{r, rs\}$, $\{r^2, r^2s\}$, $\{r^3, r^3s\}$, and both elements of $r^k\{e, s\}$ send vertex 1 to vertex $k+1$. Worked example: the cube. The rotation group acts transitively on faces, vertices and edges. A face is fixed by the 4 rotations about the axis through its centre; a vertex by the 3 rotations about the long diagonal through it; an edge by the identity and the half-turn about the axis through its midpoint. All three counts agree: $$6 \cdot 4 \;=\; 8 \cdot 3 \;=\; 12 \cdot 2 \;=\; 24.$$ This is also the standard way to find the order of a symmetry group: pick an object, count where it can go, and count what fixes it. > Trick: points in the same orbit have conjugate stabilizers: $G{g\cdot x} = g\,Gx\,g^{-1}$. So all stabilizers along one orbit have the same size, as the formula requires. The class equation Apply orbit–stabilizer to conjugation. The orbit of $x$ is $\operatorname{cl}(x)$ and its stabilizer is $CG(x)$, so $|\operatorname{cl}(x)| = [G : CG(x)]$, which divides $|G|$. An element has a class of size 1 exactly when it commutes with everything, that is when $x \in Z(G)$. Splitting $G$ into classes and collecting the size-1 classes gives the class equation: $$|G| \;=\; |Z(G)| \;+\; \sum{i=1}^{k} [G : CG(xi)],$$ where $x1, \dots, xk$ are representatives of the classes with more than one element. Each term in the sum is a divisor of $|G|$ bigger than 1. | Group | Order | Class sizes | Center ||---|---|---|---|| $S3$ | 6 | 1, 2, 3 | trivial || $D4$ | 8 | 1, 1, 2, 2, 2 | $\{e, r^2\}$ || $A4$ | 12 | 1, 3, 4, 4 | trivial || $S4$ | 24 | 1, 3, 6, 6, 8 | trivial || $A5$ | 60 | 1, 12, 12, 15, 20 | trivial | For $D4$ the classes are $\{e\}$, $\{r^2\}$, $\{r, r^3\}$, $\{s, r^2s\}$, $\{rs, r^3s\}$. In $Sn$ two permutations are conjugate exactly when they have the same cycle type; in $S4$ the classes are the identity (1), double transpositions (3), transpositions (6), 4-cycles (6), 3-cycles (8). p-groups have a nontrivial center A $p$-group is a group of order $p^n$ for a prime $p$ and some $n \ge 1$. Theorem. If $|G| = p^n$ with $n \ge 1$, then $Z(G) \ne \{e\}$. Proof. In the class equation, each $[G : CG(xi)]$ is a divisor of $p^n$ bigger than 1, so it is divisible by $p$. The left side $p^n$ is divisible by $p$. Hence $|Z(G)| = p^n - \sum [G : CG(xi)]$ is divisible by $p$. Since $e \in Z(G)$, $|Z(G)| \ge 1$, so $|Z(G)| \ge p$. ∎ Lemma. If $G/Z(G)$ is cyclic, then $G$ is abelian. Proof. Let $gZ(G)$ generate $G/Z(G)$. Every element of $G$ has the form $g^i z$ with $z \in Z(G)$. Two such elements commute: $g^i z \cdot g^j w = g^{i+j} z w = g^j w \cdot g^i z$, since $z, w$ commute with everything. ∎ Corollary. Every group of order $p^2$ is abelian, hence isomorphic to $\mathbb{Z}/p^2\mathbb{Z}$ or $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}$. Proof. $|Z(G)|$ is $p$ or $p^2$. If it were $p$, then $G/Z(G)$ would have order $p$, hence be cyclic, hence $G$ abelian by the lemma, so $Z(G) = G$ has order $p^2$: a contradiction. So $Z(G) = G$. The two possibilities come from Chapter 5. ∎ $D4$ shows that the corollary stops at $p^2$: it has order $2^3$, is not abelian, and its center has order $2$. Burnside's lemma Theorem (Burnside's lemma, also called the Cauchy–Frobenius lemma). If a finite group $G$ acts on a finite set $X$, the number of orbits is $$\#\text{orbits} \;=\; \frac{1}{|G|} \sum{g \in G} |X^g|,$$ the average number of points fixed by an element. Proof. Count the pairs $(g, x)$ with $g\cdot x = x$ in two ways. By $g$ first: $\sumg |X^g|$. By $x$ first: $\sumx |Gx| = \sumx |G|/|G\cdot x|$. Group the $x$ by orbits. An orbit $O$ contributes $|O| \cdot |G|/|O| = |G|$. So the total is $|G|$ times the number of orbits. ∎ The typical use is counting colourings "up to symmetry". If $g$ permutes the positions with $c(g)$ cycles, a colouring with $k$ colours is fixed by $g$ exactly when it is constant on each cycle, so $|X^g| = k^{c(g)}$. Worked example: necklaces. Colour 6 beads on a circle black or white; two necklaces are the same if one is a rotation of the other. The group is the cyclic group of rotations by $0, 1, \dots, 5$ steps. A rotation by $j$ steps has $\gcd(j, 6)$ cycles on the beads: $6, 1, 2, 3, 2, 1$ cycles for $j = 0, \dots, 5$. So $$\#\text{necklaces} = \frac{2^6 + 2^1 + 2^2 + 2^3 + 2^2 + 2^1}{6} = \frac{64 + 2 + 4 + 8 + 4 + 2}{6} = \frac{84}{6} = 14.$$ If flips are also allowed (the dihedral group of order 12, so "bracelets"), the count drops to 13. With 3 colours and rotations only, the same formula gives $(729 + 3 + 9 + 27 + 9 + 3)/6 = 780/6 = 130$. Worked example: colouring a cube's faces. The 24 rotations of the cube, sorted by type, with the number of cycles each makes on the 6 faces: | Rotation type | How many | Cycles on faces ||---|---|---|| identity | 1 | 6 || 90° or 270° about a face axis | 6 | 3 (two fixed faces, one 4-cycle) || 180° about a face axis | 3 | 4 (two fixed faces, two 2-cycles) || 120° or 240° about a vertex diagonal | 8 | 2 (two 3-cycles) || 180° about an edge axis | 6 | 3 (three 2-cycles) | With 3 colours: $$\frac{3^6 + 6\cdot 3^3 + 3\cdot 3^4 + 8\cdot 3^2 + 6\cdot 3^3}{24} = \frac{729 + 162 + 243 + 72 + 162}{24} = \frac{1368}{24} = 57.$$ With 2 colours the same table gives $(64 + 48 + 48 + 32 + 48)/24 = 240/24 = 10$. > Common pitfall: dividing the number of colourings by $|G|$ ($3^6/24$ is not even an integer) is wrong because symmetric colourings have smaller orbits. Burnside's average of fixed points corrects for exactly this. Chapter 4 — Cauchy and Sylow Lagrange's theorem says the order of a subgroup divides $|G|$. The converse is false: $A4$ has order 12 but no subgroup of order 6. The theorems in this chapter recover as much of the converse as is true, for prime powers. Terminology - Sylow $p$-subgroup — if $|G| = p^k m$ with $p$ prime and $p \nmid m$, a subgroup of order exactly $p^k$ (the largest power of $p$ allowed by Lagrange).- $np$ — the number of Sylow $p$-subgroups of $G$.- Normalizer — $NG(H) = \{ g : gHg^{-1} = H \}$, the stabilizer of $H$ when $G$ acts on its subgroups by conjugation.- Simple group — a nontrivial group whose only normal subgroups are $\{e\}$ and itself (post 02). The theorems Theorem (Cauchy). If a prime $p$ divides $|G|$, then $G$ has an element of order $p$. (A short proof, due to McKay, lets $\mathbb{Z}/p\mathbb{Z}$ rotate the $p$-tuples $(g1, \dots, gp)$ with $g1 g2 \cdots gp = e$ and counts fixed points modulo $p$.) Theorem (Sylow). Let $|G| = p^k m$ with $p$ prime, $k \ge 1$ and $p \nmid m$. 1. Existence. $G$ has a subgroup of order $p^k$. More generally, every $p$-subgroup of $G$ is contained in some Sylow $p$-subgroup.2. Conjugacy. Any two Sylow $p$-subgroups are conjugate: if $P, Q$ are Sylow, then $Q = gPg^{-1}$ for some $g \in G$.3. Counting. $np \equiv 1 \pmod p$, and $np$ divides $m$. Moreover $np = [G : NG(P)]$ for any Sylow $p$-subgroup $P$. Two consequences are used constantly: - $np = 1$ if and only if the Sylow $p$-subgroup is normal. (Conjugates of a Sylow subgroup are Sylow, and by part 2 all Sylow subgroups are conjugates of one of them.)- When $p$ divides $|G|$ only once, the Sylow $p$-subgroups have prime order $p$. Two distinct subgroups of prime order meet only in $\{e\}$, so the $np$ of them contain $np(p-1)$ elements of order $p$. Sylow counts in familiar groups (checked by listing subgroups): | Group | Order | $n2$ | $n3$ | $n5$ ||---|---|---|---|---|| $S3$ | $2 \cdot 3$ | 3 | 1 | — || $A4$ | $2^2 \cdot 3$ | 1 | 4 | — || $S4$ | $2^3 \cdot 3$ | 3 | 4 | — || $A5$ | $2^2 \cdot 3 \cdot 5$ | 5 | 10 | 6 | Every entry obeys part 3: for $A5$, $n5 = 6 \equiv 1 \pmod 5$ and $6 \mid 12$; $n3 = 10 \equiv 1 \pmod 3$ and $10 \mid 20$. Application 1 — every group of order 15 is cyclic Let $|G| = 15 = 3 \cdot 5$. - $n3$ divides 5 and $n3 \equiv 1 \pmod 3$. The divisors of 5 are 1 and 5, and $5 \equiv 2$. So $n3 = 1$.- $n5$ divides 3 and $n5 \equiv 1 \pmod 5$. The divisors of 3 are 1 and 3, and $3 \not\equiv 1$. So $n5 = 1$. So $G$ has a normal subgroup $P$ of order 3 and a normal subgroup $Q$ of order 5. Their intersection is a subgroup of both, so its order divides $\gcd(3, 5) = 1$: $P \cap Q = \{e\}$. For $a \in P$, $b \in Q$, the commutator $aba^{-1}b^{-1}$ lies in $Q$ (as $aba^{-1} \in Q$) and in $P$ (as $ba^{-1}b^{-1} \in P$), so it is $e$ and $ab = ba$. Then $ab$ has order $\operatorname{lcm}(3, 5) = 15$, and $G = \langle ab \rangle \cong \mathbb{Z}/15\mathbb{Z}$. The same argument proves: if $p < q$ are primes and $p \nmid q - 1$, every group of order $pq$ is cyclic. (For $p = 2$, $q = 3$ it fails, correctly: $S3$ has order 6 and $2 \mid 3 - 1$.) Application 2 — no group of order 12 is simple Let $|G| = 12 = 2^2 \cdot 3$. Then $n3 \mid 4$ with $n3 \equiv 1 \pmod 3$, so $n3 \in \{1, 4\}$; and $n2 \mid 3$ with $n2$ odd, so $n2 \in \{1, 3\}$. - If $n3 = 1$, the Sylow 3-subgroup is normal and $G$ is not simple.- If $n3 = 4$, the four subgroups of order 3 contain $4 \cdot 2 = 8$ elements of order 3. That leaves $12 - 8 = 4$ elements. A Sylow 2-subgroup has 4 elements, none of order 3, so it must be exactly these 4 elements. There is room for only one, so $n2 = 1$ and it is normal. Either way $G$ has a proper nontrivial normal subgroup. $A4$ is the second case: $n3 = 4$ and $n2 = 1$, the normal subgroup being $V4 = \{e, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3)\}$. Application 3 — order 20 If $|G| = 20 = 2^2 \cdot 5$, then $n5 \mid 4$ and $n5 \equiv 1 \pmod 5$ force $n5 = 1$. So every group of order 20 has a normal subgroup of order 5 and is not simple. > Trick: the recipe for "no simple group of order $n$" is: list the allowed $np$ for each prime; if some prime forces $np = 1$, you are done; if not, count elements of prime order and look for a contradiction, as for order 12. > Watch out: Sylow part 3 gives only candidates. $n2 \in \{1, 3\}$ for order 12 does not mean both values occur in every group; $A4$ has $n2 = 1$, while the dihedral group of order 12 has $n2 = 3$. Chapter 5 — Finite abelian groups For abelian groups the story is complete: they are classified by lists of numbers. Theorem (fundamental theorem of finite abelian groups). Every finite abelian group $A$ is isomorphic to a direct product of cyclic groups of prime-power order, $$A \;\cong\; \mathbb{Z}/p1^{a1}\mathbb{Z} \times \cdots \times \mathbb{Z}/pr^{ar}\mathbb{Z},$$ and the list of prime powers $pi^{ai}$ (the elementary divisors) is unique up to order. Equivalently, $A \cong \mathbb{Z}/d1\mathbb{Z} \times \cdots \times \mathbb{Z}/ds\mathbb{Z}$ with $d1 \mid d2 \mid \cdots \mid ds$ and $d1 > 1$, and the invariant factors $di$ are unique. To go from elementary divisors to invariant factors, write the prime powers of each prime in decreasing order, then multiply across: the largest power of every prime gives $ds$, the next largest gives $d{s-1}$, and so on. This uses $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/mn\mathbb{Z}$ for coprime $m, n$ (Chapter 1). Counting. The number of abelian groups of order $p1^{e1} \cdots pr^{er}$ is the product of the partition numbers $p(e1) \cdots p(er)$, since each prime's part is chosen independently as a partition of its exponent. Worked example: order 72. $72 = 2^3 \cdot 3^2$. The exponent 3 has three partitions ($3$, $2+1$, $1+1+1$) and the exponent 2 has two ($2$, $1+1$), so there are $3 \cdot 2 = 6$ abelian groups of order 72: | Elementary divisors | Invariant factors ||---|---|| $8, 9$ | $\mathbb{Z}/72$ || $8, 3, 3$ | $\mathbb{Z}/3 \times \mathbb{Z}/24$ || $4, 2, 9$ | $\mathbb{Z}/2 \times \mathbb{Z}/36$ || $4, 2, 3, 3$ | $\mathbb{Z}/6 \times \mathbb{Z}/12$ || $2, 2, 2, 9$ | $\mathbb{Z}/2 \times \mathbb{Z}/2 \times \mathbb{Z}/18$ || $2, 2, 2, 3, 3$ | $\mathbb{Z}/2 \times \mathbb{Z}/6 \times \mathbb{Z}/6$ | (Here $\mathbb{Z}/n$ abbreviates $\mathbb{Z}/n\mathbb{Z}$.) Check one row: for $4, 2, 3, 3$ the powers of 2 in decreasing order are $4, 2$ and of 3 are $3, 3$; multiplying across gives $4\cdot 3 = 12$ and $2 \cdot 3 = 6$, so $\mathbb{Z}/6 \times \mathbb{Z}/12$, and indeed $6 \mid 12$. > Common pitfall: $\mathbb{Z}/2 \times \mathbb{Z}/36$ and $\mathbb{Z}/4 \times \mathbb{Z}/18$ are the same group (both have elementary divisors $4, 2, 9$). Always reduce to one normal form before comparing. The same theorem, stated for finitely generated modules over a principal ideal domain, is the structure theory behind the Jordan normal form; it is planned as a later post. Practice Exercises 1. How many homomorphisms are there from $\mathbb{Z}/20\mathbb{Z}$ to $\mathbb{Z}/8\mathbb{Z}$? List the possible images of $1$. <details><summary>Solution</summary> A homomorphism is fixed by $a = \varphi(1)$, subject to $20a \equiv 0 \pmod 8$, i.e. $4a \equiv 0 \pmod 8$, i.e. $a$ even. So $a \in \{0, 2, 4, 6\}$: four homomorphisms, which is $\gcd(20, 8) = 4$. </details> 2. Show that $\mathbb{Z}/8\mathbb{Z}$, $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ and $(\mathbb{Z}/2\mathbb{Z})^3$ are pairwise non-isomorphic. <details><summary>Solution</summary> Compare the largest element order. $\mathbb{Z}/8\mathbb{Z}$ has an element of order 8. In $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ the order of $(a, b)$ is $\operatorname{lcm}$ of the orders, at most $\operatorname{lcm}(4, 2) = 4$, and $(1, 0)$ has order 4. In $(\mathbb{Z}/2\mathbb{Z})^3$ every non-identity element has order 2. The maximal orders 8, 4, 2 differ, so no two are isomorphic. (These are the three abelian groups of order 8, from the partitions $3$, $2+1$, $1+1+1$.) </details> 3. $S4$ acts on the set of its three "pairings" $\{\{1,2\},\{3,4\}\}$, $\{\{1,3\},\{2,4\}\}$, $\{\{1,4\},\{2,3\}\}$. Use orbit–stabilizer to find the order of the stabilizer of one pairing, and find the kernel of the action. <details><summary>Solution</summary> The action is transitive (for instance $(2\,3)$ swaps the first two pairings, $(2\,4)$ swaps the first and third), so the orbit has size 3 and the stabilizer has order $24/3 = 8$. It is a Sylow 2-subgroup (a copy of $D4$). The kernel is the set of permutations fixing all three pairings: $V4 = \{e, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3)\}$. By the First Isomorphism Theorem, $S4/V4$ is isomorphic to the image in $S3$, which has order $24/4 = 6$, so $S4/V4 \cong S3$. </details> 4. How many ways are there to colour the 4 vertices of a square with 3 colours, up to rotation? Up to all 8 symmetries of $D4$? <details><summary>Solution</summary> Rotations by $0^\circ, 90^\circ, 180^\circ, 270^\circ$ have $4, 1, 2, 1$ cycles on the vertices: $(3^4 + 3 + 3^2 + 3)/4 = (81 + 3 + 9 + 3)/4 = 96/4 = 24$. For $D4$ add the reflections. The two diagonal reflections fix 2 vertices and swap 2: 3 cycles each. The two reflections through edge midpoints swap two pairs: 2 cycles each. Total $(96 + 2\cdot 27 + 2 \cdot 9)/8 = (96 + 54 + 18)/8 = 168/8 = 21$. </details> 5. Prove that no group of order 35 is simple, and in fact that every group of order 35 is cyclic. <details><summary>Solution</summary> $35 = 5 \cdot 7$. $n5 \mid 7$ and $n5 \equiv 1 \pmod 5$: the divisors are 1, 7 and $7 \equiv 2$, so $n5 = 1$. $n7 \mid 5$ and $n7 \equiv 1 \pmod 7$: the divisors are 1, 5 and $5 \not\equiv 1$, so $n7 = 1$. Both Sylow subgroups are normal, meet trivially, and commute elementwise, exactly as for order 15, so $G \cong \mathbb{Z}/5 \times \mathbb{Z}/7 \cong \mathbb{Z}/35$. (This is the "$p \nmid q - 1$" criterion with $5 \nmid 6$.) </details> 6. List the abelian groups of order 36 in both normal forms. <details><summary>Solution</summary> $36 = 2^2 \cdot 3^2$, and $p(2) \cdot p(2) = 2 \cdot 2 = 4$ groups: - $4, 9$ → $\mathbb{Z}/36$- $4, 3, 3$ → $\mathbb{Z}/3 \times \mathbb{Z}/12$- $2, 2, 9$ → $\mathbb{Z}/2 \times \mathbb{Z}/18$- $2, 2, 3, 3$ → $\mathbb{Z}/6 \times \mathbb{Z}/6$ </details> 7. Let $G$ be a finite group and $H$ a subgroup of index $n$. Using the action of $G$ on the cosets $G/H$, show that $G$ has a normal subgroup $K \subseteq H$ with $[G:K]$ dividing $n!$. Deduce that a simple group of order 60 has no subgroup of index 2, 3 or 4. <details><summary>Solution</summary> The action gives a homomorphism $\rho : G \to \operatorname{Sym}(G/H) \cong Sn$. Its kernel $K$ is normal; anything in $K$ fixes the coset $H$, so $K \subseteq H$. By the First Isomorphism Theorem $G/K$ embeds in $Sn$, so $[G:K]$ divides $n!$ by Lagrange. If $G$ is simple of order 60 and $[G:H] = n \in \{2, 3, 4\}$, then $K$ is $\{e\}$ or $G$. $K = G$ is impossible since $K \subseteq H \ne G$. So $K = \{e\}$ and $60$ divides $n! \le 24$, a contradiction. </details> Cheat-sheet | Idea | Statement ||---|---|| Homomorphism | $\varphi(ab) = \varphi(a)\varphi(b)$; then $\varphi(e) = e$, $\varphi(g^{-1}) = \varphi(g)^{-1}$ || Kernel | always a normal subgroup; trivial exactly when $\varphi$ is injective || Maps between cyclic groups | $\gcd(n, m)$ homomorphisms $\mathbb{Z}/n \to \mathbb{Z}/m$, fixed by the image of 1 || Automorphisms | $\operatorname{Aut}(\mathbb{Z}/n) \cong (\mathbb{Z}/n)^\times$, order $\phi(n)$; $\operatorname{Inn}(G) \cong G/Z(G)$ || First Isomorphism Theorem | $G/\ker\varphi \cong \operatorname{im}\varphi$ || Second | $HN/N \cong H/(H \cap N)$ when $N$ is normal || Third | $(G/N)/(K/N) \cong G/K$ || Cayley | $G$ embeds in $\operatorname{Sym}(G)$; order $n$ embeds in $Sn$ || Orbit–stabilizer | orbit size times stabilizer size $= \lvert G\rvert$ || Class equation | $\lvert G\rvert = \lvert Z(G)\rvert + \sum [G : CG(xi)]$ || $p$-groups | nontrivial center; order $p^2$ implies abelian || Burnside | orbits = average number of fixed points; colourings fixed by $g$: $k^{c(g)}$ || Cauchy | prime $p$ divides the order, so an element of order $p$ exists || Sylow | exist; all conjugate; $np \equiv 1 \bmod p$ and $np \mid m$ || Normal Sylow | $np = 1$ exactly when the Sylow $p$-subgroup is normal || Order $pq$, $p < q$ | cyclic if $p \nmid q - 1$ || Finite abelian groups | product of cyclic prime-power groups; count = product of partition numbers | What's next Post 04 moves from one operation to two. A ring has addition and multiplication tied by the distributive law; the integers, the integers modulo $n$, polynomials and matrices are the models. Every idea of this post has a ring version: ring homomorphisms and their kernels (now called ideals), quotient rings, and a First Isomorphism Theorem with the same proof. Prime and maximal ideals then explain why $\mathbb{Z}/p\mathbb{Z}$ is a field, and the same construction applied to polynomials builds $\mathbb{C}$ and the finite fields that post 05 needs. References - D. S. Dummit and R. M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004 — Chapters 3.3 (isomorphism theorems), 4 (group actions, class equation, Sylow) and 5.2 (finite abelian groups).- M. Artin, Algebra, 2nd edition, Pearson, 2011 — Chapters 6 (symmetry, group actions, counting) and 7 (class equation, Sylow theorems).- J. A. Gallian, Contemporary Abstract Algebra, 10th edition, CRC Press, 2021 — homomorphisms, Burnside's lemma worked examples, Sylow theorems.- J. J. Rotman, An Introduction to the Theory of Groups, 4th edition, Springer GTM 148, 1995 — full proofs of Sylow and the basis theorem.- MIT OpenCourseWare, 18.701 Algebra I (Fall 2010) and 18.702 Algebra II (Spring 2011) — lecture notes and problem sets.- K. Conrad, Expository papers ("blurbs") — short notes on group actions, Sylow theorems and finite abelian groups.- J. H. McKay, "Another proof of Cauchy's group theorem", American Mathematical Monthly 66 (1959), p. 119. > Note: this post is in progress. Planned additions: full proofs of the three Sylow theorems (via the action on subsets of size $p^k$ and on Sylow subgroups by conjugation), semidirect products and the classification of groups of order 12 and of order $pq$, and the Pólya enumeration theorem as a refinement of Burnside's lemma.

Post 00 established what a container is at runtime. This post covers the artifact it runs from: the image. An image is not a tarball of a machine — it is an ordered stack of filesystem layers plus two small JSON documents, and almost every practical skill (fast rebuilds, small images, no leaked secrets, reproducible deploys) follows from understanding that structure. The Dockerfile is the build script that produces it, and its instructions have exact semantics that are easy to use wrongly: where was meant, where was meant, shell-form that silently breaks signal handling. This post goes through all of it, then builds working multi-stage Node and Python images and measures the size difference. > Series map: 00 Containers from First Principles → 01 Images and Dockerfiles (this post) → 02 Networking, Volumes and Compose → 03 Registries, Supply Chain and Security → 04 Kubernetes Architecture and Core Objects → 05 Config, Storage and Stateful Workloads → 06 Scheduling, Resources, Probes and Rollouts → 07 Ingress, Observability, RBAC and GitOps. Learning Outcome - Describe an image as layers + manifest + config, and use every meaningful Dockerfile instruction with correct semantics — including the /, /, and / distinctions.- Predict exactly which layers a change invalidates, and order instructions so dependency installs stay cached.- Write a that keeps the build context small and the cache stable.- Build multi-stage images for a Node service and a Python service, running as a non-root user.- Choose between , , , and full base images with the musl/glibc trade-offs in mind.- Use BuildKit cache mounts, secret mounts, and multi-platform builds.- Measure your own before/after image sizes and pin base images by digest for reproducibility. Chapter 1 — What an image is made of Terminology - Layer — a tar archive of filesystem changes (added, modified, and whiteout entries), stored as a content-addressed blob. Its is the SHA-256 of the uncompressed tar.- Digest — the SHA-256 of a stored blob or manifest as the registry holds it. What refers to.- Manifest — a small JSON listing the config blob and the layer blobs for one platform.- Index / manifest list — a JSON listing several manifests, one per platform (Post 03).- Image config — JSON holding , , , , , , , the , and a array.- Build context — the set of files sent to the builder, from which may read. Anatomy Look at a real one: Three facts worth internalising immediately: 1. Layers are shared. Ten images built store that base once. Pulls only fetch blobs the host lacks.2. Layers are additive. Deleting a file in layer 3 does not shrink layers 0–2; it writes a whiteout. in one instruction and in the next leaves the package lists inside the image.3. The config is the runtime contract. , , , , and live there — not in the filesystem — which is why can override them without touching a layer. Chapter 2 — The Dockerfile instruction set Every starts a new stage and resets the filesystem; only s declared before the first survive across stage boundaries, and then only for use in lines unless redeclared. Runs a command in a new layer on top of the current image. Chain related commands with in one so cleanup happens in the same layer as the thing it cleans up. A separate cleanup instruction removes nothing from the image. vs does everything does plus two magic behaviours: it auto-extracts local tar archives into the destination, and it can fetch remote URLs (and, with current BuildKit, Git repositories). | Situation | Use ||-----------|-----|| Copying files or directories from the context | || Copying from a previous build stage | || Extracting a local you control | (this is its one clear win) || Downloading a remote file | prefer , or | Why is usually wrong: the tar auto-extraction is implicit, so behaves completely differently from ; a plain historically performed no integrity check and produced an un-cacheable layer that could not be validated. has one behaviour and it is the one you expected. The Docker docs' own best-practices guide says the same: prefer . creates the directory if missing and persists for later instructions and at run time. Always use it rather than — a inside a affects only that shell, which is a common source of "why is my file in ?". vs | | | ||--|-------|-------|| Available during build | yes | yes || Present in the final image | no | yes || Set from the CLI | | (at run time) || Scope | the current stage (plus pre- globals in lines) | from the instruction to the end of the stage, and at run time || Visible in | yes | yes || Safe for secrets | no | no | If both are defined with the same name, wins for the rest of the build. Neither is a secret store: prints build args, and prints env vars. Post 03 goes into the leak in detail; the fix is BuildKit secret mounts, in Chapter 6 below. publishes nothing. It is metadata: documentation for humans, a hint for tooling, and the list uses when assigning random host ports. Actual publishing is at run time (Post 02). Leaving out does not prevent anything from working. vs - — the executable. Not overridden by trailing arguments.- — default arguments (or the default command when there is no ). Replaced by trailing arguments. The canonical combination: - →- → the is replaced- → drops you into a shell Exec form vs shell form | | Exec form | Shell form ||--|----------------------|------------------|| What runs as PID 1 | your program | || Variable expansion () | no | yes || Pipes, , redirection | no | yes || Receives from | yes | usually not || Requires a shell in the image | no (works on /) | yes | The signal problem, precisely: with shell form, PID 1 is and your app is a child. sends to PID 1. A minimal does not forward signals to children, so your app never learns it should shut down; after the grace period (10 s by default) the kernel s everything. In-flight requests are dropped, buffers are not flushed, and in Kubernetes this shows up as failed rolling updates (Post 06). > Common pitfall: applications that spawn children (a shell wrapper, a supervisor, a chain) also need to reap zombies. Use (or as the entrypoint) when your PID 1 is not a real init. Applies to every subsequent and to the container at run time. Prefer a numeric UID: a name resolves only if in that image maps it, which and may not. Exit 0 = healthy, 1 = unhealthy; shows the state and Compose's uses it (Post 02). Kubernetes ignores entirely — it has its own probes (Post 06). Keep the check cheap and local: one that queries a database turns a dependency outage into a self-inflicted restart loop. Use the standard keys — registries and scanners read them, and links a package on GHCR back to its repository. Declares that a path should be backed by a volume; without one mounted there, Docker creates an anonymous volume. Caveats: any writing to that path after the instruction is discarded, and every leaves another anonymous volume behind. In application images, document the path instead and let Compose or Kubernetes mount it. Chapter 3 — Build cache mechanics How the cache decides For each instruction the builder computes a cache key and looks for a matching existing layer: - — the key is the command string (plus the parent layer). BuildKit does not know or care what the command actually did. will happily reuse a six-month-old package index.- / — the key includes a checksum of the copied file contents and metadata. Change one byte of one copied file and this layer and every layer after it rebuild.- Metadata instructions — the key is the instruction text. A cache miss cascades. Once one instruction misses, everything below it rebuilds, regardless of whether it would have hit on its own. The canonical ordering Dependencies change rarely; source code changes constantly. So copy the dependency manifest first, install, and only then copy the source. Before — every code edit reinstalls every dependency: After — code edits reuse the install layer: Measure the difference on your own project: Watch the build output: the reused steps print . On a dependency-heavy project the second rebuild typically drops from tens of seconds (or minutes) to a couple of seconds — the exact figures depend on your dependency tree, so record your own. The same pattern elsewhere: copy before ; + / before or ; + before ; + before ; before . > Trick: (not ) and where possible. They fail loudly when the lockfile and the manifest disagree instead of silently resolving a different tree — which is what makes the cached layer trustworthy. Chapter 4 — The build context is everything the CLI hands to the builder. Without a , that includes , , build outputs, virtualenvs, and any stray database dump in the directory. Three separate costs: transfer time (the context is packed and sent before instruction one runs), cache poisoning ( hashes everything in the context, so a that changes on every commit invalidates the copy layer and everything below it — the usual cause of builds that "randomly" stop hitting cache), and accidental inclusion (, , and full history shipped inside the image, readable by anyone who pulls it). A workable starting point: Check the size of what you are actually sending: > Watch out: is not . Files that git ignores are still in the build context unless also lists them. Keeping the two in sync is worth a moment of attention every time you add a build output directory. Chapter 5 — Multi-stage builds One stage compiles; another, tiny, stage runs. Toolchains, headers, compilers, and source code never reach the shipped image. Worked example — Node Worked example — Python The virtualenv carries installed packages across stages cleanly while keeping the runtime free of compilers: it installs only , not and . And builds only up to a named stage — handy for debugging, and for a test stage ( + ) that fails the build when the suite fails. Chapter 6 — Base images and BuildKit features Choosing a base | Base | Size class | Package manager | libc | Good for ||------|-----------|-----------------|------|----------|| / (full) | large | apt | glibc | build stages, debugging, exotic native deps || (e.g. ) | medium | apt | glibc | most production apps — the sensible default || | small | apk | musl | small tools, Go/Rust binaries, careful use elsewhere || | small | none | glibc (or static) | production runtime with no shell and no package manager || | 0 | none | none | fully static binaries (Go/Rust with ) | The Alpine caveats Alpine uses musl libc rather than glibc, which produces real differences: - Python wheels target (glibc), so on Alpine pip often compiles from source: slower builds, a toolchain dragged in, and frequently a larger image than . wheels exist but coverage is thinner.- DNS resolution differs: musl's resolver has diverged from glibc on search-domain handling and parallel A/AAAA queries, and TCP fallback for large responses only arrived in musl 1.2.4. In Kubernetes, where discovery leans on and search domains (Post 07), this is the classic "works on Debian, flaky on Alpine" bug.- Native modules built against glibc will not run; anything with or prebuilt files must be rebuilt. Alpine is excellent for statically linked Go and Rust binaries and for small utility images. For Python and for Node projects with native modules, is usually the better default and distroless the better production endpoint. Distroless No shell, no package manager, no busybox — which removes most of the tooling an attacker would use after a compromise, and also your ability to . Debug with the variants, ephemeral containers (Post 07), or a stage. BuildKit BuildKit is the default builder in current Docker Engine. Add the syntax directive at the top of the Dockerfile to guarantee a modern frontend: Cache mounts A persistent, build-only cache directory that is not part of any layer: The same works for () — with an apt cache mount, do not also , since the mount is already outside the image. Secret mounts The right way to use a private registry token, an SSH key, or a licence file during a build without it ever entering a layer: The file exists only for the duration of that . Compare with the broken approaches: lands in ; leaves the file in an earlier layer forever (Post 03 shows how to extract it). Multi-platform builds One tag, backed by an OCI index with one manifest per architecture, so an Apple-silicon laptop and an x86 server pull the right variant from the same name. Non-native architectures build through QEMU emulation unless you attach a native builder node — emulated builds of compiled languages are markedly slower, so prefer native runners in CI. Post 03 covers the index format. Chapter 7 — Size, measurement, and reproducibility Measure, do not guess Typical orders of magnitude for a small Node service — your figures will differ with dependency count and base version, which is exactly why you run the command: | Variant | Typical size class | What dominates ||---------|-------------------|----------------|| Full base + dev dependencies + | around 1 GB | the full distro base and dev dependencies || / base, production deps only | a few hundred MB | base + || Multi-stage runtime stage | roughly 100–200 MB | base runtime + production || Distroless or (static Go/Rust) | tens of MB or less | just the binary | Where the savings actually come from, in order of impact: not shipping the build toolchain (multi-stage); not shipping dev dependencies, tests, and source when only a build artifact is needed; a smaller base image; cleaning package-manager caches within the same ; and never adding a large file in one layer and deleting it in another. > Trick: smaller images matter most for cold-start latency — node pulls in Kubernetes, autoscaling, and CI. If your image is 1 GB and your rollout pulls it onto 40 nodes, the size shows up directly as deployment time. Reproducibility and digest pinning A tag is a mutable pointer. today and next month are different images. For anything you must be able to rebuild identically: then pins the exact bytes, forever. Pair digest pinning with an automated updater (Dependabot, Renovate) so the pin is refreshed deliberately rather than drifting silently, and add lockfiles for language dependencies. The rule Post 03 formalises: tags for humans, digests for machines. Practice Exercises Exercise 1 — Read an image Pull . Using only and , report its , , , and exposed ports, count its layers, and explain why shows more rows than there are layers. <details><summary>Solution</summary> Instructions that only change the config (, , , , …) get a row in with size but add no layer; only steps that change the filesystem (mainly , , ) add an entry to . </details> Exercise 2 — Fix the cache Take the "before" Dockerfile from Chapter 3, rebuild after touching a source file, and record the time. Reorder it, rebuild the same way, and record again. Report both numbers and which steps printed . <details><summary>Solution</summary> Move + above , then: </details> Exercise 3 — Signal handling Build two images from the same trivial Node/Python server, one with shell-form and one with exec form. Start each, run , and time how long the stop takes. Explain the difference. <details><summary>Solution</summary> Fix: , or if shell expansion is genuinely required. </details> Exercise 4 — Multi-stage conversion Convert a single-stage image of your own to multi-stage and record sizes before and after. Confirm the runtime image ships no compiler: should fail. Exercise 5 — Secret that does not leak Build an image that needs a token during (or from a private index). Do it once with and once with a BuildKit secret mount. Then try to recover the token from each image. <details><summary>Solution</summary> </details> Exercise 6 — Non-root and pinned Rewrite one of your images to run as UID 10001 with , verify with , then pin its base by digest and confirm that no longer changes the base layer. Cheat-sheet | What | How ||------|-----|| Build with a tag / one stage | / || Verbose log, no cache, fresh base | , , || Layer history and sizes | || Image config (Cmd, Env, User) | || vs | always, except local tar extraction || vs | = build only (and visible in history); = persists to run time || / + | documentation only / executable + default args (trailing run args replace ) || Exec form | — required for correct || PID 1 reaping | , or as entrypoint || Non-root | , || Cache ordering / context size | copy lockfile → install deps → copy source; keep a || BuildKit cache mount | || BuildKit secret mount | + || Multi-platform | || Reproducible base | || Multi-stage copy | | What's next Post 02 takes these images and connects them to the world: Networking, Volumes and Compose — bridge vs host vs none, why only a user-defined network gives DNS by container name, port publishing and the caveat, named volumes vs bind mounts vs tmpfs with their permission traps, and a complete Compose stack (web app + PostgreSQL + Redis) with health-gated startup that you can run end to end. References - Dockerfile reference — the authoritative instruction semantics.- Docker build documentation — best practices (including over ), BuildKit cache and secret mounts, multi-platform builds.- OCI Image Specification — manifests, configs, layer media types.- Distroless base images — minimal runtime bases.- Alpine Linux, musl libc, and — the small-base ecosystem, its libc, and a layer-by-layer image explorer. > Note: this post is in progress. Planned additions: a Go/ static-binary example; for multi-image builds; a CI recipe for registry-backed cache export/import.

A subgroup $H$ of a group $G$ cuts $G$ into translated copies of itself, the cosets of $H$. Because the cosets all have the same size and never overlap, the size of $H$ must divide the size of $G$. That is Lagrange's theorem, the first real structure theorem of group theory, and it re-proves Fermat's and Euler's theorems from post 00 in one line. This post then asks when the cosets can themselves be multiplied to form a new, smaller group. The answer is exactly when $H$ is a normal subgroup, and the new group is the quotient group $G/H$. Clock arithmetic $\mathbb{Z}/n\mathbb{Z}$ turns out to be the quotient of $\mathbb{Z}$ by $n\mathbb{Z}$. The post closes with the center, the commutator subgroup, and simple groups, the groups that have no quotients to take. It uses the notation of post 01: permutations compose right to left, and $Dn$ has order $2n$. > Series map: 00 Integers, Relations & Modular Arithmetic → 01 Groups & Subgroups → 02 Cosets, Lagrange & Quotient Groups (this post) → 03 Homomorphisms, Group Actions & Sylow → 04 Rings, Ideals & Fields → 05 Field Extensions & Galois Theory. Learning Outcome - Compute left and right cosets and prove that the left cosets of $H$ partition $G$ into sets of size $\lvert H \rvert$.- State and prove Lagrange's theorem and its corollaries: element orders divide $\lvert G \rvert$, groups of prime order are cyclic, Fermat and Euler.- Use the index $[G : H]$ and the tower law.- Explain why the converse of Lagrange's theorem fails, using $A4$.- Prove the equivalent conditions for a subgroup to be normal, and test normality with the conjugation rule for cycles.- Construct the quotient group $G/N$, prove that its operation is well defined, and see exactly how it breaks for a non-normal subgroup.- Compute the center and the commutator subgroup of small groups, and use "$G/Z(G)$ cyclic implies $G$ abelian".- Define simple groups and explain what "$A5$ is simple" means. Chapter 1 — Cosets Terminology - For a subgroup $H \leq G$ and $g \in G$, the left coset is $gH = \{gh : h \in H\}$ and the right coset is $Hg = \{hg : h \in H\}$. In additive notation: $g + H$.- $g$ is a representative of the coset $gH$. Any element of the coset can serve.- The index $[G : H]$ is the number of left cosets of $H$ in $G$ (possibly infinite). First examples In $\mathbb{Z}$ with $H = 3\mathbb{Z}$, the cosets are $0 + 3\mathbb{Z}$, $1 + 3\mathbb{Z}$, $2 + 3\mathbb{Z}$: exactly the congruence classes mod 3 from post 00. So $[\mathbb{Z} : 3\mathbb{Z}] = 3$. In $\mathbb{R}^2$ under addition, let $H$ be a line through the origin. The coset $v + H$ is the parallel line through the point $v$. The cosets are all the lines parallel to $H$: they fill the plane and never cross. This picture — parallel copies of the subgroup, filling the group without overlap — is the right mental model in every example. Cosets in $S3$ Use $r = (1 \ 2 \ 3)$ and $s = (2 \ 3)$ as in post 01, so $S3 = \{e, r, r^2, s, rs, r^2 s\}$ with $r^2 = (1 \ 3 \ 2)$, $rs = (1 \ 2)$, $r^2 s = (1 \ 3)$, and $sr = r^2 s$. Take $H = \langle s \rangle = \{e, (2 \ 3)\}$. The left cosets are $$H = \{e, (2 \ 3)\}, \qquad rH = \{r, rs\} = \{(1 \ 2 \ 3), (1 \ 2)\}, \qquad r^2 H = \{r^2, r^2 s\} = \{(1 \ 3 \ 2), (1 \ 3)\}.$$ The right cosets are $H$, $Hr = \{r, sr\} = \{r, r^2 s\} = \{(1 \ 2 \ 3), (1 \ 3)\}$ and $Hr^2 = \{r^2, sr^2\} = \{r^2, rs\} = \{(1 \ 3 \ 2), (1 \ 2)\}$. Both families split $S3$ into three pairs, but into different pairs: $rH \neq Hr$. Now take the rotation subgroup $A3 = \langle r \rangle = \{e, r, r^2\}$. Its cosets are $A3$ itself and $sA3 = \{s, sr, sr^2\} = \{s, rs, r^2 s\}$, the three reflections (transpositions). Here $sA3 = A3 s$: left and right cosets agree. The coset lemma Lemma 1.1. Let $H \leq G$ and $a, b \in G$. 1. $a \in aH$.2. $aH = bH$ if and only if $a^{-1}b \in H$. In particular $aH = H$ if and only if $a \in H$.3. Two left cosets are either equal or disjoint.4. $\lvert aH \rvert = \lvert H \rvert$. Proof. Define $a \sim b$ if $a^{-1}b \in H$. This is an equivalence relation: $a^{-1}a = e \in H$; if $a^{-1}b \in H$ then its inverse $b^{-1}a \in H$; if $a^{-1}b, b^{-1}c \in H$ then their product $a^{-1}c \in H$. Its class of $a$ is $\{b : a^{-1}b \in H\} = \{b : b = ah \text{ for some } h \in H\} = aH$. So the left cosets are exactly the equivalence classes, and parts 1–3 are Theorem 2.3 of post 00 (classes partition the set; one common element makes two classes equal). For part 4, the map $H \to aH$, $h \mapsto ah$, is onto by definition and one-to-one by cancellation. $\blacksquare$ The same holds for right cosets with $ba^{-1} \in H$ in part 2. The map $gH \mapsto Hg^{-1}$ is a well-defined bijection from left cosets to right cosets (because $(gh)^{-1} = h^{-1}g^{-1}$), so the number of left cosets equals the number of right cosets, even when the cosets themselves differ. > Common pitfall: $aH = bH$ does not mean $a = b$, and it is tested by $a^{-1}b \in H$, not by $ab^{-1} \in H$ (that is the test for right cosets). In $S3$ above, $rH = (rs)H$ because $r^{-1}(rs) = s \in H$. Chapter 2 — Lagrange's theorem Theorem 2.1 (Lagrange). If $G$ is a finite group and $H \leq G$, then $\lvert H \rvert$ divides $\lvert G \rvert$, and $$[G : H] = \frac{\lvert G \rvert}{\lvert H \rvert}.$$ Proof. By Lemma 1.1 the left cosets of $H$ partition $G$, and each has exactly $\lvert H \rvert$ elements. If there are $k = [G : H]$ of them, counting the elements of $G$ coset by coset gives $\lvert G \rvert = k \lvert H \rvert$. $\blacksquare$ The proof is three lines because the work was done in the coset lemma. Lagrange's theorem is a restriction: it says which subgroup orders are impossible. A group of order 12 can only have subgroups of orders 1, 2, 3, 4, 6, 12; a group of order 8 has no subgroup (and so no element) of order 3. Corollaries Corollary 2.2. In a finite group, the order of every element divides $\lvert G \rvert$. Proof. $\lvert g \rvert = \lvert \langle g \rangle \rvert$ (post 01, Lemma 3.1), and $\langle g \rangle$ is a subgroup. $\blacksquare$ Corollary 2.3. $g^{\lvert G \rvert} = e$ for every $g$ in a finite group $G$. Proof. $\lvert G \rvert = m \lvert g \rvert$ for some integer $m$, so $g^{\lvert G \rvert} = (g^{\lvert g \rvert})^m = e$. $\blacksquare$ Corollary 2.4. A group of prime order $p$ is cyclic, and every non-identity element generates it. In particular it is abelian and, up to isomorphism, it is $\mathbb{Z}/p\mathbb{Z}$. Proof. Take $g \neq e$. Then $\lvert g \rvert$ divides $p$ and is not 1, so $\lvert g \rvert = p$ and $\langle g \rangle = G$. $\blacksquare$ Corollary 2.5 (Euler and Fermat, again). If $\gcd(a, n) = 1$ then $a^{\varphi(n)} \equiv 1 \pmod n$; if $p$ is prime and $p \nmid a$ then $a^{p-1} \equiv 1 \pmod p$. Proof. $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group of order $\varphi(n)$ containing $[a]$; apply Corollary 2.3. Fermat is $n = p$, $\varphi(p) = p - 1$. $\blacksquare$ Compare the proof in post 00, which rearranged a product of all the units: that argument is Lagrange's theorem in disguise, specialised to one group. Lagrange also explains the remark there that $\varphi(n)$ need not be the smallest exponent that works: the order of each element divides $\varphi(n)$ but can be smaller. In $(\mathbb{Z}/20\mathbb{Z})^\times$, of order $\varphi(20) = 8$, the elements $3, 7, 13, 17$ have order 4 and $9, 11, 19$ have order 2, so in fact $a^4 \equiv 1 \pmod{20}$ for every $a$ coprime to 20. Application: the groups of order 4 Proposition 2.6. Every group of order 4 is cyclic or is the Klein four group $V$. Proof. Element orders divide 4. If some element has order 4, the group is cyclic. Otherwise every non-identity element has order 2; write $G = \{e, a, b, c\}$. The product $ab$ is not $e$ (since $a^{-1} = a \neq b$), not $a$ (else $b = e$), and not $b$ (else $a = e$). So $ab = c$, and the same argument fills in the rest of the table: it is the table of $V$. $\blacksquare$ Index and the tower law Proposition 2.7 (tower law). If $K \leq H \leq G$ with $G$ finite, then $[G : K] = [G : H][H : K]$. Proof. $\dfrac{\lvert G \rvert}{\lvert K \rvert} = \dfrac{\lvert G \rvert}{\lvert H \rvert} \cdot \dfrac{\lvert H \rvert}{\lvert K \rvert}$. $\blacksquare$ (The law also holds for infinite groups when the indices are finite, by a direct coset argument.) Example: in $\mathbb{Z}/12\mathbb{Z} \geq \langle 2 \rangle \geq \langle 4 \rangle$, of orders $12, 6, 3$: $[\mathbb{Z}/12\mathbb{Z} : \langle 4 \rangle] = 4 = 2 \cdot 2$. > Trick: if $H$ and $K$ are finite subgroups with $\gcd(\lvert H \rvert, \lvert K \rvert) = 1$, then $H \cap K = \{e\}$, because $\lvert H \cap K \rvert$ divides both orders. This quick consequence of Lagrange is used constantly in post 03's Sylow arguments. Chapter 3 — The converse of Lagrange fails Lagrange says a subgroup's order divides $\lvert G \rvert$. The converse — "for every divisor $d$ of $\lvert G \rvert$ there is a subgroup of order $d$" — is true for cyclic groups (post 01, Theorem 5.2) but false in general. The smallest counterexample is the alternating group $A4$. $A4$ is the group of even permutations of $\{1, 2, 3, 4\}$, of order $4!/2 = 12$. Sorting its elements by cycle type: | type | elements | count ||---|---|---|| identity | $e$ | 1 || double transpositions | $(1 \ 2)(3 \ 4)$, $(1 \ 3)(2 \ 4)$, $(1 \ 4)(2 \ 3)$ | 3 || 3-cycles | $(1 \ 2 \ 3)$, $(1 \ 3 \ 2)$, $(1 \ 2 \ 4)$, $(1 \ 4 \ 2)$, $(1 \ 3 \ 4)$, $(1 \ 4 \ 3)$, $(2 \ 3 \ 4)$, $(2 \ 4 \ 3)$ | 8 | Proposition 3.1. $A4$ has no subgroup of order 6, although 6 divides 12. Proof. Suppose $H \leq A4$ with $\lvert H \rvert = 6$. Then $[A4 : H] = 2$, so there are only two left cosets, $H$ and the complement. Let $\sigma$ be any 3-cycle. The three cosets $H$, $\sigma H$, $\sigma^2 H$ cannot all be different, so two coincide: $\sigma^i H = \sigma^j H$ with $0 \leq i < j \leq 2$, which by Lemma 1.1 means $\sigma^{j-i} \in H$, with $j - i \in \{1, 2\}$. If $\sigma^2 \in H$ then also $\sigma = \sigma^4 = (\sigma^2)^2 \in H$. Either way $\sigma \in H$. So $H$ contains all eight 3-cycles, too many for a set of 6 elements. $\blacksquare$ In fact $A4$ has subgroups of orders 1, 2, 3, 4 and 12 only: three of order 2 (one per double transposition), four of order 3 (one per pair of inverse 3-cycles), and one of order 4, the Klein four group $V = \{e, (1 \ 2)(3 \ 4), (1 \ 3)(2 \ 4), (1 \ 4)(2 \ 3)\}$. Partial converses do hold, and they are the subject of post 03: Cauchy's theorem (if a prime $p$ divides $\lvert G \rvert$, there is an element of order $p$) and the Sylow theorems (subgroups of every prime-power order dividing $\lvert G \rvert$ exist). Chapter 4 — Normal subgroups Terminology - The conjugate of $x$ by $g$ is $gxg^{-1}$. For a subset, $gHg^{-1} = \{ghg^{-1} : h \in H\}$. If $H \leq G$ then $gHg^{-1}$ is again a subgroup, of the same order.- A subgroup $N \leq G$ is normal, written $N \trianglelefteq G$, if $gNg^{-1} \subseteq N$ for every $g \in G$. Equivalent conditions Theorem 4.1. For a subgroup $N \leq G$ the following are equivalent: 1. $gNg^{-1} \subseteq N$ for all $g \in G$;2. $gNg^{-1} = N$ for all $g \in G$;3. $gN = Ng$ for all $g \in G$;4. every left coset of $N$ is a right coset of $N$. Proof. (1 ⇒ 2) Apply (1) to $g^{-1}$: $g^{-1}Ng \subseteq N$. Conjugating by $g$ gives $N \subseteq gNg^{-1}$. (2 ⇒ 3) $gN = gNg^{-1}g = Ng$. (3 ⇒ 4) Clear. (4 ⇒ 1) Suppose $gN = Nx$ for some $x$. Since $g \in gN$, $g \in Nx$, so $Nx$ and $Ng$ are right cosets sharing $g$, hence equal. So $gN = Ng$. Then for $n \in N$, $gn \in Ng$, so $gn = n'g$ for some $n' \in N$ and $gng^{-1} = n' \in N$. $\blacksquare$ > Watch out: $gN = Ng$ is an equality of sets. It does not say $gn = ng$ for each $n$; it says $gn = n'g$ for some possibly different $n' \in N$. Normal subgroups need not commute elementwise with $G$. Examples - Every subgroup of an abelian group is normal: $gng^{-1} = n$.- Index 2 subgroups are normal. If $[G : N] = 2$, the left cosets are $N$ and $G \setminus N$, and so are the right cosets. So for $g \notin N$, $gN = G \setminus N = Ng$. Hence $An \trianglelefteq Sn$, the rotations $\langle r \rangle \trianglelefteq Dn$, and $A3 \trianglelefteq S3$ (as the coset computation in Chapter 1 showed directly).- $SLn(\mathbb{R}) \trianglelefteq GLn(\mathbb{R})$: $\det(gAg^{-1}) = \det g \cdot \det A \cdot (\det g)^{-1} = \det A = 1$.- In $Q8$ every subgroup is normal. The subgroups are $\{1\}$, $\{\pm 1\}$, $\langle i \rangle$, $\langle j \rangle$, $\langle k \rangle$ and $Q8$; the three cyclic subgroups of order 4 have index 2, and $\{\pm 1\}$ consists of elements that commute with everything. So $Q8$ is a non-abelian group all of whose subgroups are normal. The conjugation rule for cycles In $Sn$ there is a fast way to conjugate: for any $\sigma \in Sn$, $$\sigma \, (a1 \ a2 \ \dots \ ak) \, \sigma^{-1} = (\sigma(a1) \ \sigma(a2) \ \dots \ \sigma(ak)).$$ Proof. The right side sends $\sigma(ai) \mapsto \sigma(a{i+1})$. The left side does too: $\sigma^{-1}$ takes $\sigma(ai)$ to $ai$, the cycle takes it to $a{i+1}$, and $\sigma$ takes that to $\sigma(a{i+1})$. On a point $\sigma(b)$ with $b$ outside the cycle, both sides give $\sigma(b)$. $\blacksquare$ So conjugation relabels the entries and keeps the cycle type. Consequences: - Non-example. $H = \{e, (2 \ 3)\}$ is not normal in $S3$: with $\sigma = (1 \ 2 \ 3)$, $\sigma (2 \ 3) \sigma^{-1} = (\sigma(2) \ \sigma(3)) = (3 \ 1) = (1 \ 3) \notin H$. This matches the different left and right cosets found in Chapter 1.- $V \trianglelefteq S4$: $V$ consists of $e$ and all three permutations of type "two disjoint transpositions", and conjugation preserves type.- Normality is not transitive. $K = \{e, (1 \ 2)(3 \ 4)\}$ is normal in $V$ (index 2, or: $V$ is abelian), and $V \trianglelefteq A4$, but $K$ is not normal in $A4$: $(1 \ 2 \ 3)(1 \ 2)(3 \ 4)(1 \ 2 \ 3)^{-1} = (2 \ 3)(1 \ 4) = (1 \ 4)(2 \ 3) \notin K$. Worked example: the normal subgroups of $D4$ $D4$ has ten subgroups (post 01). Sort them by order and test each: | order | subgroups | normal? | reason ||---|---|---|---|| 1 | $\{e\}$ | yes | trivial || 2 | $\{e, r^2\}$ | yes | $r^2$ is in the center: $r^2$ commutes with $r$, and $s r^2 s = r^{-2} = r^2$ || 2 | $\{e, s\}$, $\{e, rs\}$, $\{e, r^2 s\}$, $\{e, r^3 s\}$ | no | $r s r^{-1} = r^2 s$, and in general $r (r^k s) r^{-1} = r^{k+2} s$ || 4 | $\langle r \rangle$, $\{e, r^2, s, r^2 s\}$, $\{e, r^2, rs, r^3 s\}$ | yes | index 2 || 8 | $D4$ | yes | whole group | So $D4$ has six normal subgroups out of ten. The computation $r (r^k s) r^{-1} = r^{k+1} (s r^{-1}) = r^{k+1} r s = r^{k+2} s$ uses $s r^{-1} = r s$, which is $srs = r^{-1}$ read with $r$ replaced by $r^{-1}$. Products of subgroups For subgroups $H, K \leq G$ let $HK = \{hk : h \in H, k \in K\}$. Proposition 4.2. If $H$ and $K$ are finite, $\lvert HK \rvert = \dfrac{\lvert H \rvert \lvert K \rvert}{\lvert H \cap K \rvert}$. If moreover one of $H, K$ is normal in $G$, then $HK$ is a subgroup. Proof. $HK$ is the union of the left cosets $hK$ for $h \in H$, each of size $\lvert K \rvert$. Two of them coincide, $h1 K = h2 K$, exactly when $h1^{-1} h2 \in K$, that is (both being in $H$) when $h1^{-1} h2 \in H \cap K$, i.e. when $h1$ and $h2$ lie in the same left coset of $H \cap K$ in $H$. So the number of distinct cosets $hK$ is $[H : H \cap K] = \lvert H \rvert / \lvert H \cap K \rvert$, giving the formula. If $K \trianglelefteq G$, then $hK = Kh$ for each $h$, so $HK = KH$, and $(h1 k1)(h2 k2)^{-1} = h1 k1 k2^{-1} h2^{-1} \in h1 K h2^{-1} = h1 h2^{-1} K \subseteq HK$; the one-step test applies. The case $H \trianglelefteq G$ is symmetric. $\blacksquare$ Without normality $HK$ can fail to be a subgroup, and Lagrange detects it. In $S3$ with $H = \{e, (1 \ 2)\}$ and $K = \{e, (1 \ 3)\}$: $\lvert HK \rvert = 2 \cdot 2 / 1 = 4$, namely $\{e, (1 \ 2), (1 \ 3), (1 \ 2)(1 \ 3) = (1 \ 3 \ 2)\}$. Since 4 does not divide 6, $HK$ cannot be a subgroup. Chapter 5 — Quotient groups Let $N \trianglelefteq G$. The quotient group (factor group) $G/N$ is the set of cosets of $N$ with the operation $$(aN)(bN) = (ab)N.$$ The formula uses representatives $a$ and $b$, so the first job is to check that the answer does not depend on which representatives are chosen — the same worry as for $\mathbb{Z}/n\mathbb{Z}$ in post 00. Theorem 5.1. If $N \trianglelefteq G$, the operation $(aN)(bN) = abN$ is well defined, and it makes $G/N$ a group with identity $eN = N$ and inverses $(aN)^{-1} = a^{-1}N$. If $G$ is finite, $\lvert G/N \rvert = [G : N] = \lvert G \rvert / \lvert N \rvert$. Proof. Suppose $aN = a'N$ and $bN = b'N$, so $a' = an1$ and $b' = bn2$ with $n1, n2 \in N$. Then $$a'b' = a n1 b n2 = ab \, (b^{-1} n1 b) \, n2.$$ By normality $b^{-1} n1 b \in N$, so $a'b' \in abN$ and $a'b'N = abN$. The group axioms are inherited from $G$: $(aN \cdot bN) \cdot cN = (ab)c N = a(bc) N = aN \cdot (bN \cdot cN)$, $N \cdot aN = aN$, and $aN \cdot a^{-1}N = N$. $\blacksquare$ Where it breaks without normality Take the non-normal $H = \{e, s\}$ in $S3$. Two names for the same coset: $eH = sH = H$. Multiply each by $rH$: - with representative $e$: $(eH)(rH) = rH = \{(1 \ 2 \ 3), (1 \ 2)\}$;- with representative $s$: $(sH)(rH) = srH = r^2 s H = r^2 H = \{(1 \ 3 \ 2), (1 \ 3)\}$. Same inputs, different outputs: the "operation" is not a function. Normality is exactly what is needed. Indeed, if the coset product is well defined for $H$, then for $h \in H$ and $g \in G$, $(hg)H = (hH)(gH) = (eH)(gH) = gH$, so $g^{-1}hg \in H$, and $H$ is normal. Examples of quotients - $\mathbb{Z}/n\mathbb{Z}$ is the quotient of $\mathbb{Z}$ by the subgroup $n\mathbb{Z}$: the cosets $a + n\mathbb{Z}$ are the congruence classes, and the coset sum is the addition of classes from post 00. This is where the notation comes from.- $S3/A3$ has two elements, $A3$ (rotations) and $sA3$ (reflections). "Rotation times reflection is a reflection; reflection times reflection is a rotation": the quotient is $\mathbb{Z}/2\mathbb{Z}$. Likewise $Sn / An \cong \mathbb{Z}/2\mathbb{Z}$ records only the sign.- $(\mathbb{Z}/12\mathbb{Z})/\langle 4 \rangle$: the cosets of $\{0, 4, 8\}$ are $\{0, 4, 8\}$, $\{1, 5, 9\}$, $\{2, 6, 10\}$, $\{3, 7, 11\}$. The coset $1 + \langle 4 \rangle$ has order 4 (the first multiple of 1 landing in $\{0, 4, 8\}$ is $4$), so the quotient is cyclic of order 4.- $Q8 / \{\pm 1\}$ has order 4. Every $q \in Q8$ has $q^2 = \pm 1$, so every coset squares to the identity coset, and by Proposition 2.6 the quotient is $V$.- $\mathbb{R}/\mathbb{Z}$: cosets $x + \mathbb{Z}$ are "real numbers up to whole turns", added mod 1. It behaves like the circle group $S^1$ via $x + \mathbb{Z} \mapsto e^{2\pi i x}$ (post 03 makes this an isomorphism with the first isomorphism theorem). A quotient table: $D4 / Z(D4)$ The center of $D4$ is $Z = \{e, r^2\}$ (Chapter 6 below; it is the normal subgroup of order 2 found in Chapter 4). Its four cosets are $$Z = \{e, r^2\}, \quad rZ = \{r, r^3\}, \quad sZ = \{s, r^2 s\}, \quad rsZ = \{rs, r^3 s\}.$$ Multiply cosets through representatives, then look up which coset the product lies in: | $\cdot$ | $Z$ | $rZ$ | $sZ$ | $rsZ$ ||---|---|---|---|---|| $Z$ | $Z$ | $rZ$ | $sZ$ | $rsZ$ || $rZ$ | $rZ$ | $Z$ | $rsZ$ | $sZ$ || $sZ$ | $sZ$ | $rsZ$ | $Z$ | $rZ$ || $rsZ$ | $rsZ$ | $sZ$ | $rZ$ | $Z$ | For instance $(sZ)(rZ) = srZ = r^3 s Z$, and $r^3 s \in rsZ$; while $(rZ)(sZ) = rsZ$. In $D4$, $sr \neq rs$, but in the quotient the two products land in the same coset: the quotient is abelian, a copy of $V$. Passing to $G/N$ forgets the information inside $N$, here the difference between $r^3 s$ and $rs$. The correspondence theorem (statement) Theorem 5.2 (correspondence). Let $N \trianglelefteq G$. The subgroups of $G/N$ correspond one-to-one to the subgroups $H$ of $G$ that contain $N$, via $H \mapsto H/N$. The correspondence preserves inclusion, and $H/N$ is normal in $G/N$ exactly when $H$ is normal in $G$. Example: the subgroups of $\mathbb{Z}/12\mathbb{Z}$ containing $\langle 4 \rangle = \{0, 4, 8\}$ are $\langle 4 \rangle$, $\langle 2 \rangle$ and the whole group, of orders 3, 6 and 12. They match the three subgroups of the quotient $(\mathbb{Z}/12\mathbb{Z})/\langle 4 \rangle \cong \mathbb{Z}/4\mathbb{Z}$, of orders $3/3 = 1$, $6/3 = 2$ and $12/3 = 4$. The proof is cleanest with homomorphisms and is part of post 03. Order of an element in $G/N$. $gN$ has order the smallest $k \geq 1$ with $g^k \in N$, since $(gN)^k = g^k N$ equals $N$ exactly when $g^k \in N$. The order of $gN$ therefore divides the order of $g$. > Common pitfall: $G/N$ is not a subgroup of $G$. Its elements are subsets of $G$ (cosets), and its identity is the whole of $N$. Sometimes $G$ happens to contain a subgroup isomorphic to $G/N$ (for $S3/A3$, the subgroup $\{e, s\}$), but often it does not: $Q8/\{\pm 1\} \cong V$, while $Q8$ has only one element of order 2 and so contains no copy of $V$. Chapter 6 — Center, commutators and simple groups The center The center of $G$ is $Z(G) = \{z \in G : zg = gz \text{ for all } g \in G\}$, the elements that commute with everything. Proposition 6.1. $Z(G)$ is a normal subgroup of $G$. $G$ is abelian if and only if $Z(G) = G$. Proof. $e \in Z(G)$. If $y, z \in Z(G)$, then $yz^{-1}g = y g z^{-1} = g y z^{-1}$ (from $zg = gz$ we get $gz^{-1} = z^{-1}g$). So the one-step test passes. Normality: $gzg^{-1} = zgg^{-1} = z$. $\blacksquare$ | $G$ | $Z(G)$ ||---|---|| abelian $G$ | $G$ || $S3$ (and $Sn$, $n \geq 3$) | $\{e\}$ || $D4$ | $\{e, r^2\}$ || $Q8$ | $\{\pm 1\}$ || $GLn(\mathbb{R})$ | non-zero scalar matrices $\lambda I$ | Theorem 6.2. If $G/Z(G)$ is cyclic, then $G$ is abelian. Proof. Write $Z = Z(G)$ and let $gZ$ generate $G/Z$. Every element of $G$ lies in some coset $g^k Z$, so has the form $g^k z$ with $z \in Z$. Two such elements commute: $(g^a z1)(g^b z2) = g^{a+b} z1 z2 = (g^b z2)(g^a z1)$, because the $zi$ commute with everything and powers of $g$ commute with each other. $\blacksquare$ So for a non-abelian group, $G/Z(G)$ is never cyclic; in particular $\lvert G/Z(G) \rvert$ is never a prime. For $D4$: $\lvert D4/Z(D4) \rvert = 8/2 = 4$, and since every $g \in D4$ has $g^2 \in \{e, r^2\}$, the quotient is $V$, not cyclic, as the theorem requires. The commutator subgroup The commutator of $a$ and $b$ is $[a, b] = aba^{-1}b^{-1}$. It equals $e$ exactly when $ab = ba$, so it measures failure to commute. The commutator subgroup (derived subgroup) $G'$ is the subgroup generated by all commutators. Theorem 6.3. $G' \trianglelefteq G$, the quotient $G/G'$ is abelian, and for any normal subgroup $N$: $G/N$ is abelian if and only if $G' \leq N$. Proof. Conjugation respects products and $g[a, b]g^{-1} = [gag^{-1}, gbg^{-1}]$, so a conjugate of a product of commutators is again one; hence $G'$ is normal. For $N \trianglelefteq G$: $G/N$ is abelian iff $abN = baN$ for all $a, b$, iff $(ba)^{-1}(ab) = a^{-1}b^{-1}ab = [a^{-1}, b^{-1}] \in N$ for all $a, b$. As $a, b$ range over $G$ so do $a^{-1}, b^{-1}$, so this says every commutator lies in $N$, that is $G' \leq N$. Taking $N = G'$ shows $G/G'$ is abelian. $\blacksquare$ $G/G'$ is the largest abelian quotient of $G$. Examples: $G' = \{e\}$ exactly when $G$ is abelian; $S3' = A3$; $D4' = \{e, r^2\}$ (for instance $[r, s] = rsr^{-1}s^{-1} = r \cdot r = r^2$); $Q8' = \{\pm 1\}$; $A4' = V$; $S4' = A4$. Simple groups A group $G \neq \{e\}$ is simple if its only normal subgroups are $\{e\}$ and $G$. A simple group has no non-trivial quotients: it cannot be broken into a normal subgroup and a smaller quotient group. Proposition 6.4. An abelian group is simple if and only if it is cyclic of prime order. Proof. Groups of prime order have no subgroups except $\{e\}$ and $G$ (Lagrange), so they are simple. Conversely let $G$ be abelian and simple; all its subgroups are normal, so it has none except $\{e\}$ and $G$. For $g \neq e$, $\langle g \rangle = G$, so $G$ is cyclic. It is not infinite ($\langle g^2 \rangle$ would be a proper non-trivial subgroup of $\mathbb{Z}$), so $G \cong \mathbb{Z}/n\mathbb{Z}$, and $n$ must be prime since there is a subgroup for every divisor of $n$ (post 01, Theorem 5.2). $\blacksquare$ The first non-abelian simple group is $A5$, of order 60. Theorem 6.5 (stated). $A5$ is simple. More generally, $An$ is simple for every $n \geq 5$. A sketch for $A5$, whose missing step comes in post 03: a normal subgroup is a union of conjugacy classes (sets $\{gxg^{-1} : g \in G\}$), and it contains the identity. The conjugacy classes of $A5$ have sizes $1, 12, 12, 15, 20$. The sums that include the class $\{e\}$ of size 1 are $1, 13, 16, 21, 25, 28, 33, 36, 40, 45, 48, 60$, and by Lagrange a subgroup's order must divide 60. Only $1$ and $60$ do. So the only normal subgroups are $\{e\}$ and $A5$. Simple groups are the "atoms" of finite group theory: the Jordan–Hölder theorem says every finite group is built from a uniquely determined list of simple groups, much as an integer is built from primes. The classification of finite simple groups, completed through the work of many mathematicians, lists them all: the cyclic groups of prime order, the alternating groups $An$ for $n \geq 5$, the groups of Lie type (built from matrix groups over finite fields), and 26 sporadic groups. In post 05 the simplicity of $A5$ is the group-theoretic fact behind the theorem that the general quintic equation cannot be solved by radicals. Practice Exercises 1. In $D4$ (order 8, $r^4 = s^2 = e$, $srs = r^{-1}$), list the left and the right cosets of $H = \{e, s\}$. Is $H$ normal? <details><summary>Solution</summary> Left: $\{e, s\}$, $\{r, rs\}$, $\{r^2, r^2 s\}$, $\{r^3, r^3 s\}$. Right: $\{e, s\}$, $\{r, sr\} = \{r, r^3 s\}$, $\{r^2, sr^2\} = \{r^2, r^2 s\}$, $\{r^3, sr^3\} = \{r^3, rs\}$ (using $sr^k = r^{-k}s$). Since $rH = \{r, rs\} \neq \{r, r^3 s\} = Hr$, $H$ is not normal. Note that $[D4 : H] = 4 = 8/2$, as Lagrange requires. </details> 2. Let $H$ and $K$ be subgroups of a finite group with $\gcd(\lvert H \rvert, \lvert K \rvert) = 1$. Prove $H \cap K = \{e\}$. Deduce that in a group of order 15, a subgroup of order 3 and a subgroup of order 5 meet only in $e$. <details><summary>Solution</summary> $H \cap K$ is a subgroup of both $H$ and $K$, so by Lagrange its order divides $\lvert H \rvert$ and $\lvert K \rvert$, hence divides their gcd, 1. For the second part, 3 and 5 are coprime. </details> 3. Without computing any powers, explain why $a^{8} \equiv 1 \pmod{20}$ for every $a$ with $\gcd(a, 20) = 1$. Then show that the exponent 8 can be replaced by 4. <details><summary>Solution</summary> $(\mathbb{Z}/20\mathbb{Z})^\times$ has order $\varphi(20) = 8$; apply Corollary 2.3. Its elements are $1, 3, 7, 9, 11, 13, 17, 19$. By Lagrange each order divides 8. None has order 8: $3^2 = 9$, $3^4 = 81 \equiv 1$; $7^2 = 49 \equiv 9$, so $7^4 \equiv 81 \equiv 1$; $9^2 = 81 \equiv 1$; $11^2 = 121 \equiv 1$; $13 \equiv -7$ and $17 \equiv -3$ have fourth powers equal to those of $7$ and $3$; $19 \equiv -1$. So every order divides 4. </details> 4. Use the conjugation rule to decide whether $H = \{e, (1 \ 2)(3 \ 4)\}$ is normal in $S4$, and whether $V$ is. <details><summary>Solution</summary> $H$ is not normal: conjugating by $(2 \ 3)$ gives $(1 \ 3)(2 \ 4) \notin H$. $V$ is normal: it consists of $e$ and all permutations with cycle type two disjoint transpositions, and conjugation preserves cycle type. </details> 5. In $(\mathbb{Z}/18\mathbb{Z})/\langle 6 \rangle$, find the order of the quotient, the order of $4 + \langle 6 \rangle$, and whether the quotient is cyclic. <details><summary>Solution</summary> $\langle 6 \rangle = \{0, 6, 12\}$ has order 3, so the quotient has order $18/3 = 6$. The order of $4 + \langle 6 \rangle$ is the least $k$ with $4k \in \{0, 6, 12\}$ modulo 18: $4, 8, 12$, so $k = 3$. The coset $1 + \langle 6 \rangle$ has order 6 (the least $k$ with $k \in \{0, 6, 12\}$ is 6), so the quotient is cyclic, isomorphic to $\mathbb{Z}/6\mathbb{Z}$. </details> 6. Prove that $\lvert G/Z(G) \rvert$ is never a prime number. <details><summary>Solution</summary> If $\lvert G/Z(G) \rvert = p$ is prime, $G/Z(G)$ is cyclic (Corollary 2.4), so $G$ is abelian (Theorem 6.2). Then $Z(G) = G$ and $\lvert G/Z(G) \rvert = 1$, not $p$. Contradiction. </details> 7. Find the commutator subgroup of $D4$ and identify $D4/D4'$. <details><summary>Solution</summary> $[r, s] = rsr^{-1}s^{-1} = r(sr^{-1}s) = r \cdot r = r^2$, so $\{e, r^2\} \leq D4'$. The quotient $D4/\{e, r^2\}$ has order 4, and every group of order 4 is abelian (Proposition 2.6), so by Theorem 6.3 $D4' \leq \{e, r^2\}$. Hence $D4' = \{e, r^2\} = Z(D4)$, and $D4/D4' \cong V$ (every element squares into $\{e, r^2\}$). </details> Cheat-sheet | Idea | Statement ||---|---|| Left coset | $gH = \{gh : h \in H\}$ || Same coset | $aH = bH$ iff $a^{-1}b \in H$ || Coset facts | cosets partition $G$; each has $\lvert H \rvert$ elements || Lagrange | $\lvert H \rvert$ divides $\lvert G \rvert$; $[G:H] = \lvert G \rvert / \lvert H \rvert$ || Element orders | $\lvert g \rvert$ divides $\lvert G \rvert$; $g^{\lvert G \rvert} = e$ || Prime order | cyclic, $\cong \mathbb{Z}/p\mathbb{Z}$ || Tower law | $[G:K] = [G:H][H:K]$ || Converse fails | $A4$ (order 12) has no subgroup of order 6 || Normal | $gNg^{-1} = N$ iff $gN = Ng$ for all $g$ || Index 2 | always normal || Conjugating a cycle | $\sigma (a1 \dots ak) \sigma^{-1} = (\sigma(a1) \dots \sigma(ak))$ || Quotient | $G/N$, $(aN)(bN) = abN$, needs $N$ normal || Order in $G/N$ | least $k$ with $g^k \in N$ || Center | $Z(G)$ normal; $G/Z(G)$ cyclic implies abelian || Commutators | $G/N$ abelian iff $G' \leq N$ || Simple | only $\{e\}$ and $G$ normal; $A5$ simple | What's next Post 03 introduces homomorphisms, maps between groups that respect the operation. Their kernels are exactly the normal subgroups, and the first isomorphism theorem says $G/\ker\phi \cong \operatorname{im}\phi$, which turns statements such as $GLn(\mathbb{R})/SLn(\mathbb{R}) \cong \mathbb{R}^\times$ and $\mathbb{R}/\mathbb{Z} \cong S^1$ into one-line proofs. Group actions give the orbit–stabiliser theorem and the class equation (which supplies the conjugacy class sizes used for $A5$ above), and the Sylow theorems give the partial converse of Lagrange's theorem that Chapter 3 promised. References - David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004 — Sections 3.1–3.2 (quotient groups, Lagrange's theorem) and 3.4 (composition series, Jordan–Hölder).- Joseph A. Gallian, Contemporary Abstract Algebra, 10th edition, CRC Press, 2021 — Chapters 7 (cosets and Lagrange's theorem) and 9 (normal subgroups and factor groups).- Michael Artin, Algebra, 2nd edition, Pearson, 2011 — Chapter 2, sections on cosets, normal subgroups and quotient groups.- John B. Fraleigh, A First Course in Abstract Algebra, 7th edition, Addison-Wesley, 2003 — Sections 10 (cosets and Lagrange), 14–15 (factor groups, simple groups).- Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), judsonbooks.org — chapters on cosets and Lagrange's theorem and on normal subgroups and factor groups.- MIT OpenCourseWare, 18.701 Algebra I (Fall 2010) — lectures on cosets, Lagrange, and quotient groups.- Keith Conrad, Expository papers on group theory (University of Connecticut) — including notes on the simplicity of $An$ and on conjugation in $Sn$. > Note: this post is in progress. Planned additions: a full proof that $An$ is simple for $n \geq 5$, a proof of the correspondence theorem, and a drawing of the cosets of a line in $\mathbb{R}^2$.

Containers are the packaging and isolation unit that most modern deployment runs on: CI pipelines, Kubernetes clusters, serverless container platforms, and local development environments all assume them. The trouble is that the popular one-line explanation — "a container is a lightweight VM" — is wrong in a way that produces bad decisions later, especially around security and state. This first post builds the correct model from the Linux primitives upward: a container is an ordinary process whose view of the system has been narrowed by namespaces, whose resource usage has been capped by cgroups, and whose root filesystem has been swapped for an image. Everything else in this course — Dockerfiles, Compose, registries, Kubernetes pods — is machinery layered on top of that one sentence. > Series map: 00 Containers from First Principles (this post) → 01 Images and Dockerfiles → 02 Networking, Volumes and Compose → 03 Registries, Supply Chain and Security → 04 Kubernetes Architecture and Core Objects → 05 Config, Storage and Stateful Workloads → 06 Scheduling, Resources, Probes and Rollouts → 07 Ingress, Observability, RBAC and GitOps. Learning Outcome - Define a container in terms of namespaces, cgroups, and a root filesystem — and state precisely where the "lightweight VM" analogy breaks.- Name the Linux namespaces and what each one virtualises, and read a process's namespace set from .- Explain how cgroups v2 enforces CPU, memory, and I/O limits, and read those limits from inside a running container.- Describe overlayfs and copy-on-write layering, and predict what happens to a file written inside a container.- Compare containers and VMs on startup, density, and isolation, including the shared-kernel security caveat.- Place the OCI specifications and the Docker CLI → dockerd → containerd → runc stack, and say where Podman fits.- Install Docker on Linux, macOS, or Windows and run, inspect, and remove your first container. Chapter 1 — What a container actually is Terminology - Container — a process (or small process tree) running on the host kernel with a restricted view of the system: its own namespaces, a cgroup limiting its resources, and a root filesystem taken from an image.- Image — a read-only, layered filesystem plus metadata (entrypoint, environment, exposed ports). The template.- Namespace — a kernel feature that gives a process a private instance of a global resource (process IDs, mounts, network stack, hostname, …).- cgroup (control group) — a kernel mechanism that accounts for and limits a group of processes' CPU, memory, I/O, and process count.- Container runtime — the software that turns an image plus a config into a running process. Low-level: , . High-level: , .- Host kernel — the single Linux kernel that every container on a machine shares. There is no second kernel. The one-sentence definition On Linux, this is a container: Nothing is emulated. Nothing is virtualised in the hardware sense. results in an process visible in the host's process table. Prove it on a Linux host: Inside the container that same process believes it is PID 1. Outside, it is just another entry in . Both views are true; they differ only by namespace. Where "lightweight VM" fails The analogy is seductive because both give you "a box that looks like its own machine". It fails on four concrete points, and every one of them bites in production: 1. There is no guest kernel. A VM boots its own kernel on virtual hardware. A container calls the host's kernel directly. A kernel panic, a kernel CVE, or a that must differ per workload is therefore not isolated by a container.2. There is no boot. A VM boots firmware → bootloader → kernel → init → services, in seconds to a minute. A container is + in milliseconds. That is why "one container per process" is normal and "one VM per process" is absurd.3. The isolation boundary is a kernel API surface, not a hardware boundary. A VM escape requires defeating the hypervisor's narrow virtual-device interface. A container escape requires defeating one of 300-plus syscalls, plus every cgroup, namespace, and filesystem interface the kernel exposes. The attack surface is orders of magnitude wider.4. The filesystem is layered and disposable by default. A VM has a disk that persists. A container's writable layer is thrown away with unless you explicitly mount a volume. Treating a container like a small server — SSH in, edit a config, restart — loses your edit the moment the container is replaced. > Watch out: the fourth point is the most common beginner failure. Anything a container writes that is not on a mounted volume is temporary storage attached to that container instance, not to the image and not to the service. Images vs containers — classes and instances If you know object-oriented programming, this mapping is exact enough to use: | OOP | Containers | Notes ||-----|-----------|-------|| Class | Image | Immutable definition, versioned, shared. || Instance | Container | Created from an image, has its own state and lifetime. || Constructor arguments | flags, env vars, mounts | Same image, different behaviour per instance. || Static/shared data | Image layers | Shared read-only across every container from that image. || Instance fields | The container's writable layer | Discarded with the instance. | One image, a hundred containers: the read-only layers exist once on disk and once in page cache. Only each container's thin writable layer is private. That is the density story, and it is a filesystem property, not a virtualisation one. Chapter 2 — The Linux primitives Terminology - — the syscall that creates a process; namespace flags such as decide which namespaces the child gets fresh.- / — move the current process into new namespaces without creating a container runtime.- Copy-on-write (CoW) — a write to a shared read-only file first copies it into a private layer, then modifies the copy.- Capability — one slice of root's power (e.g. = bind ports below 1024), grantable independently.- seccomp — a kernel filter that decides, per syscall, whether a process may make that call. Namespaces Each namespace virtualises exactly one global resource. | Namespace | Flag | Virtualises | Visible effect ||-----------|------|-------------|----------------|| pid | | process IDs | the container's first process is PID 1; it cannot see host PIDs || net | | interfaces, routes, iptables, sockets | its own , its own , its own port space || mnt | | mount table | its own , its own , host mounts hidden || uts | | hostname, domainname | returns the container ID by default || ipc | | System V IPC, POSIX message queues | shared memory segments are not shared with the host || user | | UID/GID mappings | UID 0 inside can map to an unprivileged UID outside || cgroup | | the cgroup hierarchy root | shows the container's own root, not the host's || time | | boot/monotonic clock offsets (Linux 5.6+) | rarely used by container runtimes today | Build one by hand — no Docker involved: Read the namespace identity of any process; two processes in the same namespace share the same inode number: The user namespace is the one that changes the security story: with it, a process can be UID 0 inside while being an unprivileged UID outside. That is what makes rootless containers (rootless Docker, Podman's default) possible. cgroups v2 cgroups v1 had one hierarchy per controller and a pile of inconsistencies. cgroups v2 (the unified hierarchy) is the default on all current mainstream distributions and is what Kubernetes and Docker assume today. Controllers you will actually meet: | Controller | Key files | What it does ||-----------|-----------|--------------|| | , | bandwidth cap ( in µs) and relative share || | , , | hard limit (OOM kill), soft throttle limit, live usage || | , | per-device IOPS and bandwidth caps || | | fork-bomb protection | Read the limits from inside a container — with cgroup namespaces the container sees its own cgroup root: Two behaviours to internalise now, because they reappear in Kubernetes (Post 06): - Memory over the limit = the kernel OOM-kills the process (exit code 137). It is not paged out, it is not throttled, it is killed.- CPU over the limit = throttling, not killing. The process is simply not scheduled for the rest of the period, which shows up as latency, not as a crash. > Common pitfall: language runtimes that read or host memory instead of the cgroup limit will size their thread pools and heaps for the whole machine. Modern JVMs (, on by default since JDK 10) and Go 1.25's cgroup-aware handle this; older runtimes and many libraries do not. overlayfs and copy-on-write layers An image is a stack of read-only directories. presents them, plus one writable directory, as a single tree: Rules that follow directly from that structure: - Reading a file finds the topmost layer that contains it.- Writing an existing file triggers a copy-up: the whole file is copied into first. Editing one byte of a 2 GB file copies 2 GB.- Deleting a file from a lower layer creates a whiteout entry in . The bytes remain in the image layer — which is exactly why a secret added in one Dockerfile layer and 'd in the next is still in the image (Post 03).- deletes . All container-local writes vanish. Inspect the layer chain of a running container: > Trick: because copy-up is per-file and whole-file, databases and other write-heavy workloads should always write to a volume, not to the writable layer. You get both better performance and persistence. Post 02 covers volumes properly. Capabilities and seccomp — the introductory version Traditional UNIX has a binary answer to "are you root?". Linux splits root's power into 40 capabilities, so a process can bind port 80 () without also being able to load kernel modules (). A container started by Docker does not get full root even when it runs as UID 0. The daemon drops all but a small default set (, , , , , , , , , , , , , ). Tighten it: seccomp filters syscalls. Docker applies a default profile that blocks roughly 40 of the 300-plus syscalls — things like , , , and old flags — with no measurable cost for typical applications. Add AppArmor (Debian/Ubuntu) or SELinux (Fedora/RHEL) labels on top, and you have the four layers of the runtime sandbox: namespaces (what you can see), cgroups (how much you can use), capabilities + seccomp (what you can ask the kernel to do), LSM (what the policy engine permits). Post 03 turns all of this into a hardening checklist. Chapter 3 — Containers vs VMs, honestly | Dimension | Container | Virtual machine ||-----------|-----------|-----------------|| Kernel | shares the host kernel | own guest kernel || Boot/start | milliseconds ( + ) | seconds to a minute (firmware → kernel → init) || Image size | tens of MB typical | hundreds of MB to GB || Density per host | hundreds | tens || Memory overhead | the process itself | guest kernel + guest services, per VM || Isolation boundary | kernel syscall/namespace surface | hypervisor + virtual hardware || Different OS kernel | no (Linux containers need a Linux kernel) | yes (any guest OS) || Custom /kernel module | mostly no — shared kernel | yes || Live migration | not a native concept | mature || Best at | packaging and scaling application processes | multi-tenant isolation, OS diversity, kernel-level work | The security caveat, stated plainly A shared kernel is a shared attack surface. Container isolation is enforced by the same kernel that a compromised container is talking to. A kernel privilege-escalation bug that a container can reach is, in the worst case, a host compromise — and from the host, every other container on that machine. VM escapes exist too, but the interface an attacker must break is far narrower. Practical consequences: - Do not treat containers as a hard multi-tenant boundary for untrusted code. Running arbitrary customer code? Put a VM or a sandboxed runtime (gVisor, Kata Containers, Firecracker microVMs) around it.- disables almost every layer described above (capabilities, device restrictions, and typically seccomp). It converts "isolated process" into "root on the host with extra steps". Post 03 covers the alternatives.- Mounting into a container is equivalent to granting root on the host: whoever can talk to the daemon can start a privileged container mounting .- Patch the host kernel. No amount of rebuilding your images fixes a host kernel CVE. > Watch out: "containers are more secure than VMs" and "containers are insecure" are both marketing. The accurate statement is: containers give strong workload isolation with a wide kernel attack surface; use them for your own code, and add a VM boundary when the tenant is untrusted. Chapter 4 — OCI specs and the runtime stack Terminology - OCI (Open Container Initiative) — the Linux Foundation body that standardised container formats, so images are not a Docker-only artifact.- Image spec — how an image is laid out: a manifest, a config JSON, and content-addressed layer blobs.- Runtime spec — how a runtime turns an unpacked filesystem bundle plus a into a running process.- Distribution spec — the HTTP API registries speak () for pushing and pulling those blobs.- CRI (Container Runtime Interface) — the gRPC API Kubernetes uses to talk to a runtime. Not an OCI spec; it sits above one. Because of these specs, an image built by Docker's BuildKit runs unchanged under containerd, CRI-O, or Podman, and can be stored in Docker Hub, GHCR, ECR, Harbor, or a plain object store fronted by a registry. The stack, top to bottom is a short-lived program: it configures the sandbox, starts the process, and exits. The shim, not the daemon, is the process's parent — which is why does not kill running containers on a modern Engine. Kubernetes (Post 04) removes the top two layers entirely: the kubelet talks CRI to (or CRI-O) directly. This is the whole content of the December 2020 "Kubernetes deprecates Docker" story (dockershim was deprecated in 1.20 and removed in 1.24, in 2022) — the image format never changed, only the shim Kubernetes used to reach the runtime. Where Podman fits | | Docker | Podman ||--|--------|--------|| Architecture | client → long-running root daemon | daemonless; the CLI forks the runtime directly || Default user | root daemon (the group ≈ root) | rootless by default via user namespaces || Per-container supervisor | | || Low-level runtime | | (default on most distros) or || Compose | (v2, built in) | / || Kubernetes affinity | — | , , native pod concept || CLI | | — deliberately argument-compatible | Podman's pods (a group of containers sharing a network namespace) are the same idea Kubernetes calls a Pod, which makes Podman a pleasant local mirror of cluster semantics. Everything in this course works with except a handful of daemon-specific commands; where they differ, the post says so. Chapter 5 — Installing Docker, and what "Docker on macOS" really means Linux — Docker Engine (the real thing) Debian/Ubuntu, using the official repository rather than the distro package: To use without : > Watch out: membership of the group is equivalent to root on that host, because any member can start a privileged container that mounts . On a shared or production machine, prefer rootless mode or Podman. macOS and Windows — there is a Linux VM under there Linux containers need a Linux kernel. macOS and Windows do not have one, so Docker Desktop ships a small Linux VM and runs the engine inside it: | Host | Mechanism | Notes ||------|-----------|-------|| macOS | Apple Virtualization framework (or the older HyperKit) running a Linux VM | file sharing via VirtioFS by default in current Desktop versions || Windows (recommended) | WSL2 — a real Linux kernel in a lightweight utility VM | Docker Desktop integrates with your WSL2 distros || Windows (legacy) | Hyper-V backend | slower start, more memory pinned || Windows containers | native Windows kernel isolation, on Windows hosts only | separate image ecosystem () | Consequences you will feel every day: 1. The "host" your container sees is the VM, not your laptop. A port published with is forwarded by Docker Desktop from the VM to your machine, which is why it still works — but a container reaching your laptop's other services must use , not (Post 02).2. Bind mounts cross a filesystem boundary and are slow. Every on a mounted source tree traverses VirtioFS/9p into the VM. Node's , Python's site-packages, and large monorepo builds are the usual victims. Keeping dependencies in a named volume or inside the image instead of a bind mount typically restores most of the speed.3. On Windows, keep your code inside the WSL2 filesystem (), not on . Crossing the Windows/Linux filesystem boundary is the single largest performance cliff in the WSL2 setup.4. CPU/memory are the VM's, not the machine's. Docker Desktop's resource sliders cap what any container can use. Measure it on your own machine rather than trusting a number from a blog post: On a native Linux host the two numbers are close. On macOS or Windows with a bind mount they usually are not. Chapter 6 — First commands The lifecycle The commands you need on day one | Task | Command ||------|---------|| Run interactively, delete on exit | || Run detached with a name and port | || List running containers | || List all containers, including exited | || Follow logs | || Last 50 log lines with timestamps | || Shell into a running container | || Run a one-off command inside it | || Stop (SIGTERM, then SIGKILL after 10 s) | || Kill immediately | || Remove a stopped container | || Stop and remove in one step | || Live resource usage | || Inspect full config as JSON | || Processes inside the container | || Copy a file out | || List images | || Reclaim space | then | A five-minute walkthrough That last pair of commands is the whole persistence lesson: the writable layer belongs to the container instance, not to the image and not to the name. > Trick: on every exploratory keeps your machine clean. Reserve un-'d containers for things you actually intend to restart, and run weekly — stopped containers, dangling images, and orphaned volumes add up to tens of GB surprisingly fast. Practice Exercises Exercise 1 — Build a container by hand Without Docker, on a Linux host, create a process with its own PID, UTS, and mount namespaces, confirm it sees itself as PID 1, and give it the hostname . <details><summary>Solution</summary> </details> Exercise 2 — Prove the shared kernel Run on your Linux host and inside three containers built from different distributions (, , ). Explain the result in one sentence. <details><summary>Solution</summary> </details> Exercise 3 — Watch a cgroup limit take effect Start a container with and make it allocate more than that. Record the exit code and explain it. <details><summary>Solution</summary> Compare with a CPU limit, which throttles instead of killing: </details> Exercise 4 — Namespace archaeology Start detached. Using only host-side tools (, , ), find its host PID, list the eight namespaces it belongs to (seven on kernels older than 5.6, which have no namespace), and confirm that its PID namespace inode differs from your shell's. Exercise 5 — The disappearing file Reproduce the writable-layer lesson: write a file inside a container, restart the container, confirm the file survives; then remove and recreate the container from the same image and confirm the file is gone. Write one sentence explaining which layer held the file. Exercise 6 — Measure your own bind-mount penalty Using the + pair from Chapter 5, measure read throughput from a bind mount and from a named volume on your machine. Record both numbers and your platform. If you are on Linux, note how close they are; on macOS or Windows, note the gap. Exercise 7 — Capability probe Run normally and with , and in each case try . Explain which capability the failure corresponds to. Cheat-sheet | What | How ||------|-----|| Definition of a container | process + namespaces + cgroups + image rootfs + security profile || Namespaces list | pid, net, mnt, uts, ipc, user, cgroup (+ time, 5.6+) || See a process's namespaces | || Make namespaces by hand | || cgroup v2 memory limit | → || cgroup v2 CPU limit | → = || Over memory limit | OOM kill, exit code 137 || Over CPU limit | throttled, not killed || Image layers | read-only overlayfs s, shared between containers || Container writes | copy-up into a private , deleted with the container || OCI specs | image-spec, runtime-spec, distribution-spec || Runtime stack | → → → → || Kubernetes path | kubelet → CRI → containerd/CRI-O → runc || Podman | daemonless, rootless by default, + || Run and clean up | || Detached with port | || Logs / exec / stop / rm | , , , || Disk usage / cleanup | , || Docker group warning | group ≈ root on that host || macOS/Windows reality | a Linux VM; bind mounts cross a filesystem boundary | What's next Post 01 moves from running other people's images to building your own: Images and Dockerfiles — the layer/manifest/config anatomy of an image, every meaningful Dockerfile instruction with its exact semantics, build-cache mechanics and the instruction ordering that makes rebuilds fast, , multi-stage builds for Node and Python, base-image choice, BuildKit cache and secret mounts, and measured image-size reduction you can reproduce. References - Docker documentation — installation, Engine, CLI reference.- Open Container Initiative — image, runtime, and distribution specifications.- and — the reference low-level and high-level runtimes.- Linux , , — the authoritative primitive documentation.- Linux kernel: control group v2 — the unified hierarchy in detail.- Linux kernel: overlayfs — layering and copy-up semantics.- Podman — daemonless, rootless alternative with a compatible CLI.- Docker rootless mode — running the daemon without root. > Note: this post is in progress. Planned additions: a from-scratch bundle walkthrough using ; a diagram of the overlayfs copy-up path; notes on gVisor and Kata Containers as sandboxed runtimes.

The final post in the advanced track combines four production topics that don't each need a full post but every working MongoDB engineer eventually faces: Kubernetes deployment via the new MongoDB Controllers for Kubernetes Operator (replacing the older Community + Enterprise operators), mongosync for cluster-to-cluster + multi-region active-active patterns, cost optimisation strategies for Atlas + self-hosted, and the compliance baselines (HIPAA, PCI-DSS, GDPR, SOC 2) every regulated workload needs. > Series map: 26 OpenTelemetry → 27 Geo → 28 Time-series extreme → 29 K8s + mongosync + cost + compliance (this post — final advanced). Learning Outcome - Deploy MongoDB on Kubernetes with the modern MongoDB Controllers operator.- Use mongosync for cluster migration + multi-region sync.- Apply cost-optimisation playbooks for Atlas + self-hosted.- Architect for HIPAA, PCI-DSS, GDPR, SOC 2 baselines. Part 1 — Kubernetes deployment Chapter 1 — Operator choice in 2026 Three Kubernetes deployment options: | Option | What | When ||--------|------|------|| MongoDB Controllers for Kubernetes Operator | new unified operator (replaces older Community + Enterprise operators) | new self-hosted on K8s || MongoDB Community Operator (older) | Community editions; replica sets; basic ops | existing self-hosted on K8s; small workloads || MongoDB Enterprise Operator (older, deprecated) | Enterprise features + Ops Manager integration | being migrated to Controllers operator || Percona Operator for MongoDB | third-party; supports Community edition; sharding + backups + PITR included | self-hosted needing sharding + backups without Enterprise licence || Atlas on K8s? — no. Atlas is managed; don't K8s it. | | | For new projects in 2026, MongoDB Controllers for Kubernetes Operator is the official path. Percona is a strong OSS alternative when you need sharding + PBM-style backups on Community. Chapter 2 — Install the Controllers operator (Helm) Creates the operator + CRDs (, , , etc.) in the namespace. Chapter 3 — Deploy a replica set The operator provisions StatefulSet, PVCs, services, runs , configures users. Chapter 4 — Production checklist - Storage: SSD class, ReadWriteOnce, ≥ 3× working-set size.- Node affinity: spread pods across nodes / zones ().- Resource requests + limits: match instance sizing.- PVC backup: Velero or CSI snapshots into S3.- Monitoring: deploy sidecar; scrape into Prometheus → Grafana.- TLS: Operator creates cert-manager-backed certs; clients use them.- Network policies: only app namespace reaches mongod ports.- Backups: Percona Backup for MongoDB (PBM) sidecar, schedule + offsite S3.- Updates: roll one member at a time via Operator-managed updates. Chapter 5 — When NOT to run Mongo on K8s - Atlas is available and you don't have a sovereignty / on-prem requirement → use Atlas. Saves enormous ops time.- Team has no K8s expertise → managed first, K8s later.- Small workloads (< 100 GB, < 1k QPS) → cheaper + simpler on plain VMs or managed. K8s pays off when: you already run K8s for everything else; you have multiple stateful workloads to operate; on-prem or sovereign cloud is required; you need infra-as-code for the DB itself. Part 2 — mongosync Chapter 6 — What mongosync does Mongosync replicates data continuously from a source cluster to a destination cluster, with minimal downtime cut-over. Works between any combination of self-hosted + Atlas + clouds + regions. Use cases: - One-time migrations (on-prem → Atlas, AWS → GCP, cluster tier change).- Multi-region passive-standby — destination always current; failover updates DNS.- Pre-production environments — sync prod data nightly into staging (with PII scrubbing post-sync).- Reverse-sync for rollback. Chapter 7 — Mongosync basics Then orchestrate via the REST API on : Phases: 1. Initial sync — bulk copy of every doc.2. Steady state — continuous oplog tailing.3. Commit — drain remaining oplog, freeze writes briefly, declare destination authoritative. Downtime for cut-over: seconds in normal cases. Chapter 8 — Multi-region active-passive On region A outage: 1. Stop the mongosync direction (or accept its catch-up lag).2. Flip your app's connection string / DNS to cluster B.3. Optionally start reverse mongosync (B → A) for when A recovers. Active-active (writes in both regions) is not natively supported — last-writer-wins conflict resolution would be needed; Mongo doesn't have it. For active-active you typically shard by region (each region writes only to its own shard); mongosync isn't the right tool. Chapter 9 — Sharded cluster sync For sharded source + destination: run one mongosync per source shard to parallelise. Coordinated commit ensures consistency on cut-over. Chapter 10 — Mongosync vs other tools | Tool | When ||------|------|| mongosync | Mongo → Mongo; one-time or continuous || mongodump / mongorestore | small / non-time-critical dumps; cross-version migrations || Debezium MongoDB connector | Mongo → Kafka → anywhere (Post 24) || Atlas Live Migration | one-time migration into Atlas || Atlas backup restore | DR scenarios | For Mongo → Mongo, mongosync is the modern default. Part 3 — Cost optimisation Chapter 11 — Atlas tier sizing Atlas pricing scales with tier (M0 free → M700+ enterprise). Cost levers: - Right-size the cluster by working set, not by RAM × N.- Reduce non-essential indexes (write amplification + RAM bloat).- Online Archive old data (Post 16) — 10× cheaper than hot tier.- Search nodes sized separately; right-size for index size + traffic.- Backup retention — long retention = more cost. Right-size to compliance need.- Data transfer — cross-region replication / clients in different regions = egress fees. Co-locate. Chapter 12 — Index pruning Hidden index pattern (Post 03) lets you test removal safely. Quarterly index review on every production collection. Easy 10-30 % storage + RAM win. Chapter 13 — Query cost Each slow query = wasted CPU + IOPS. The profiler + Atlas Performance Advisor (Post 04) surface them. Fix top-N slowest queries every sprint. A query halved is two queries worth of capacity reclaimed. Index investments scale your fleet without scaling your tier. Chapter 14 — Storage compression - WiredTiger default is snappy. Switching new collections to zstd (Post 15) compresses 25 % better at similar CPU.- Old collections can be re-collected (offline) to apply new compression. Chapter 15 — Connection cost Each pool connection costs server-side resources. Right-size client pools by Little's Law (Post 08). Big over-pools waste Atlas tier capacity. Chapter 16 — Hot vs cold tiers For data that's queried rarely: - Atlas Online Archive → cheap S3-like storage; federated query.- Manual archive to S3 (Parquet, compressed) → cheapest, custom-query path.- For analytics, push old data to ClickHouse (Post 28). The two ratios that matter: hot/cold size + hot/cold cost. If 80 % of data is rarely queried, tier it; you'll cut cluster cost in half. Chapter 17 — Atlas cost-control tactics | Tactic | Saving ||--------|--------|| Right-size tier | up to 50 % if over-provisioned || Drop unused indexes | 10-30 % RAM || Online Archive cold data | 50 %+ on cold-heavy workloads || Switch to zstd | 20-30 % storage || Co-locate clients + cluster | data-transfer egress reduction || Annual commit / reserved pricing | 20-40 % discount || Stop dev / staging clusters off-hours | tier-hour reduction || Audit + cancel forgotten resources | varies; can be huge | Chapter 18 — Self-hosted cost considerations Cost = hardware (or cloud VMs) + storage + network + people-ops. Compared to Atlas: - Self-hosted hardware is often cheaper per GB-RAM at large scale.- But operating cost (people, on-call, backup infra, monitoring) often exceeds the Atlas premium.- Most teams break even around 50 nodes / multi-TB; below that, Atlas wins on TCO. The right answer depends on your ops headcount + cloud commit + sovereignty needs. Part 4 — Compliance Chapter 19 — HIPAA, PCI-DSS, GDPR, SOC 2 baselines These are the four most common compliance frameworks regulated workloads hit. Mongo + Atlas provides primitives; you assemble the controls. | Framework | Concerns ||-----------|----------|| HIPAA (US healthcare) | Patient health info (PHI). Audit, encryption, access control, BAA with vendor. || PCI-DSS (cards) | Cardholder data (PAN). Encryption, network isolation, key rotation, logging, scanning. || GDPR (EU) | Personal data of EU residents. Right to be forgotten, data residency, breach notification (72 h). || SOC 2 (general trust) | Security, availability, processing integrity, confidentiality, privacy. Audit-based. | Chapter 20 — Atlas + HIPAA - Atlas enterprise tier required + Business Associate Agreement (BAA) with MongoDB Inc.- Customer-managed KMS keys for encryption at rest.- Audit log enabled + shipped offsite.- TLS in transit (default).- VPC private endpoint; no public access.- MFA + SSO + RBAC for all users.- BAAs with every downstream subprocessor. Document everything for the audit. Chapter 21 — PCI-DSS For storing PAN (primary account number): - CSFLE or Queryable Encryption (Post 13) so PAN is unreadable to ops staff.- KMS-managed keys with rotation policy + access logs.- Network isolation; no internet egress from the DB host.- Audit log capturing every PAN access + every privileged op.- Quarterly external scanning; annual penetration test.- Vendor PCI attestation (Atlas has SAQ-D Service Provider). Better: don't store PAN at all. Use a tokenisation service (Stripe / Adyen / Spreedly); store tokens. Chapter 22 — GDPR — right to be forgotten Article 17 — data subjects can request deletion. Patterns: - Hard delete via secondary key (email / customerid). Find every collection referencing the subject; delete or anonymise. Mongo's lack of FK makes this app-side; document each collection's owner.- Soft delete via anonymisation — replace PII with placeholders; keep aggregate analytics integrity.- Backup considerations — backups also contain the subject's data. Most regulators accept "purged on backup rotation"; document the retention.- Audit — log every deletion request + resolution.- Data residency — Atlas regions match EU AWS / Azure / GCP regions to keep data in-EU. Chapter 23 — SOC 2 controls — common requirements - Documented security policies (you write; auditor reviews).- Access reviews — quarterly audit of who has what role.- Change management — every prod change reviewed + approved.- Vendor management — Atlas + every downstream vendor reviewed.- Incident response plan — written + practised.- Monitoring + alerts — proven via logs.- Backup + restore — tested (Post 14). The audit checks evidence over a 6 or 12 month observation period. Tooling (Vanta, Drata, Secureframe) automates most of the evidence collection. Chapter 24 — Audit logging discipline Every privileged operation + every data access on sensitive collections should be auditable: - Atlas audit log → SIEM (Splunk, Datadog, ELK).- Self-hosted: Enterprise audit log feature, with filters for noise reduction.- App-level audit: every PII-touching endpoint logs into an collection with TTL of regulator-required years. Chapter 25 — Common pitfalls (compliance) | Pitfall | Cause | Fix ||---------|-------|-----|| PAN in plaintext | "we'll encrypt later" | tokenise via payment provider; never store || EU data in US region | accidental cluster region | always pin region for GDPR-relevant data || Audit log not preserved | retention too short | retention by regulator (often 7 years for HIPAA) || Backups not encrypted | self-hosted pipeline missed | encrypt every backup at rest || MFA only on humans, not service accounts | service accounts hijacked | use IAM auth where possible; rotate other secrets || Deletion request not honoured | backups still hold the data | document backup-rotation purge; honour as best-effort || Privileged role too broad | default instead of custom | least-privilege custom roles | Course complete You've covered MongoDB from the document model through CRUD, indexes, aggregation, schema design, pool + concurrency, transactions, replication, sharding, change streams, security, backup, performance, Atlas (Search + Vector + Triggers + Stream Processing), drivers, modelling case studies, Mongoose, Beanie, the outbox pattern, CQRS + Event Sourcing, production RAG, SQL→Mongo migration, Kafka + Debezium CDC, testing, OpenTelemetry, geospatial, time-series at extreme scale, Kubernetes, mongosync, cost, and compliance. That's the working knowledge of a senior MongoDB engineer + the architectural awareness of a platform engineer. Where you go from here: - Read MongoDB Inc. release notes per major version — the engine evolves fast.- Build something real that exercises 5+ of these areas end-to-end.- Contribute to OSS — drivers, operators, ODMs all welcome patches.- Pair with a database that complements Mongo for your edge cases (ClickHouse for analytics, Redis for hot cache). The series will get future extensions (single-post deep dives on subtopics, case studies from real production migrations, performance benchmarks). The base + advanced you have today is enough to ship serious systems. Cheat-sheet (omnibus) | Area | Key ||------|-----|| K8s operator | MongoDB Controllers (new) > Community / Enterprise (older) > Percona (OSS sharding+backup) || K8s sizing | SSD storage class; PVC ≥ 3× working-set; podAntiAffinity across zones || K8s vs Atlas | Atlas almost always wins on TCO unless sovereign / on-prem || mongosync | source → destination; commit phase has seconds of downtime || Multi-region active-passive | mongosync + DNS flip on outage || Active-active | not native; use region-sharded writes || Atlas cost levers | right-size tier; drop unused indexes; archive; zstd; co-locate clients || Self-hosted cost | wins at large scale + headcount; loses on small/medium || HIPAA | BAA + CMK + audit log + private endpoint + MFA || PCI | CSFLE / QE + KMS + tokenise where possible || GDPR | right to be forgotten; data residency; document backups || SOC 2 | document + audit; tools like Vanta automate evidence || Compliance baseline | least-privilege RBAC + TLS + audit log + tested restore | References - MongoDB Controllers for Kubernetes Operator- MongoDB Community Operator (older)- Percona Operator for MongoDB- Mongosync- Atlas pricing + cost controls- Atlas HIPAA / PCI documentation- MongoDB security checklist > Note: this post is in progress. Planned additions: end-to-end K8s operator walkthrough with TLS + backups; multi-region mongosync drill; Atlas cost case studies; PCI-DSS scope-reduction patterns via tokenisation.

A group is a set with one operation that can always be undone. That short definition covers the integers under addition, clock arithmetic, the shuffles of a deck of cards, the rotations and reflections of a square, invertible matrices, and the unit quaternions used to rotate objects in 3D graphics. This post gives the axioms and their first consequences, builds the standard zoo of examples (symmetric, dihedral, matrix, quaternion and Klein four groups), and then studies subgroups, with a complete description of the subgroups of a cyclic group. It relies on post 00 for $\gcd$, the division algorithm and $\mathbb{Z}/n\mathbb{Z}$; post 02 builds on it with cosets and Lagrange's theorem. > Series map: 00 Integers, Relations & Modular Arithmetic → 01 Groups & Subgroups (this post) → 02 Cosets, Lagrange & Quotient Groups → 03 Homomorphisms, Group Actions & Sylow → 04 Rings, Ideals & Fields → 05 Field Extensions & Galois Theory. Learning Outcome - State the group axioms and decide whether a given set and operation form a group.- Prove the basic consequences: unique identity and inverses, cancellation, $(ab)^{-1} = b^{-1}a^{-1}$.- Compute in $Sn$ with cycle notation, using a stated composition convention, and find the order and sign of a permutation.- Work with the dihedral group $Dn$ through its generators $r, s$ and the relation $srs = r^{-1}$.- Recognise $GLn$, $SLn$, the quaternion group $Q8$ and the Klein four group, and build and check a Cayley table.- Compute orders of elements, including $\lvert k \rvert = n/\gcd(k, n)$ in $\mathbb{Z}/n\mathbb{Z}$.- Apply the one-step and two-step subgroup tests.- Prove that every subgroup of a cyclic group is cyclic, list all subgroups of $\mathbb{Z}/n\mathbb{Z}$, and draw the subgroup lattice of $\mathbb{Z}/12\mathbb{Z}$.- Form direct products and decide when $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ is cyclic. Chapter 1 — The group axioms Terminology - A binary operation on a set $G$ is a function $G \times G \to G$, written $(a, b) \mapsto a b$ or just $ab$. "The result lies in $G$" is called closure; it is part of the definition of a binary operation.- The operation is associative if $(ab)c = a(bc)$ for all $a, b, c$.- An identity is an element $e$ with $ea = ae = a$ for all $a$.- An inverse of $a$ is an element $b$ with $ab = ba = e$.- A group is a set with an associative binary operation that has an identity, in which every element has an inverse.- A group is abelian (commutative) if $ab = ba$ for all $a, b$. Abelian groups are often written additively: $a + b$, identity $0$, inverse $-a$.- The order of a group, $\lvert G \rvert$, is the number of its elements (possibly infinite). Examples and non-examples | Set and operation | Group? | Reason ||---|---|---|| $\mathbb{Z}$, $+$ | yes, abelian | identity 0, inverse $-a$ || $\mathbb{Z}$, $-$ | no | not associative: $(1-1)-1 \neq 1-(1-1)$ || $\mathbb{N}$, $+$ | no | $1$ has no inverse in $\mathbb{N}$ || $\mathbb{Z}$, $\times$ | no | $2$ has no inverse in $\mathbb{Z}$ || $\mathbb{Q}^\times = \mathbb{Q} \setminus \{0\}$, $\times$ | yes, abelian | inverse $1/a$ || $\mathbb{Z}/n\mathbb{Z}$, $+$ | yes, abelian, order $n$ | post 00 || $\mathbb{Z}/6\mathbb{Z} \setminus \{0\}$, $\times$ | no | not closed: $2 \cdot 3 = 0$ || $(\mathbb{Z}/n\mathbb{Z})^\times$, $\times$ | yes, abelian, order $\varphi(n)$ | units, post 00 || $n \times n$ real matrices, $\times$ | no | singular matrices have no inverse | First consequences Proposition 1.1. In any group $G$: 1. the identity is unique;2. each element has exactly one inverse, written $a^{-1}$;3. $(a^{-1})^{-1} = a$ and $(ab)^{-1} = b^{-1}a^{-1}$;4. cancellation: $ab = ac$ implies $b = c$, and $ba = ca$ implies $b = c$;5. the equations $ax = b$ and $ya = b$ have the unique solutions $x = a^{-1}b$ and $y = ba^{-1}$. Proof. (1) If $e$ and $e'$ are identities, $e = ee' = e'$. (2) If $b$ and $c$ are inverses of $a$, then $b = be = b(ac) = (ba)c = ec = c$. (3) $a$ satisfies the definition of an inverse of $a^{-1}$, so by (2) it is the inverse. For the product, $(ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1} = aa^{-1} = e$, and similarly in the other order. (4) Multiply $ab = ac$ on the left by $a^{-1}$ and use associativity. (5) $x = a^{-1}b$ works; if $x'$ also works, $ax = ax'$ and cancellation gives $x = x'$. $\blacksquare$ > Common pitfall: $(ab)^{-1} = b^{-1}a^{-1}$, not $a^{-1}b^{-1}$ (the "socks and shoes" rule: to undo putting on socks then shoes, remove the shoes first). The two agree only when $a$ and $b$ commute. Powers are defined as usual: $a^0 = e$, $a^{n} = a \cdots a$ ($n$ factors), $a^{-n} = (a^{-1})^n$. The laws $a^m a^n = a^{m+n}$ and $(a^m)^n = a^{mn}$ hold in every group, but $(ab)^n = a^n b^n$ can fail when $ab \neq ba$. In additive notation $a^n$ becomes $na$. Cayley tables A Cayley table lists every product $xy$, with $x$ labelling the row and $y$ the column. Part 5 of Proposition 1.1 says each element appears exactly once in every row and every column (a Latin square). Here is $(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$ under multiplication mod 8: | $\times$ | 1 | 3 | 5 | 7 ||---|---|---|---|---|| 1 | 1 | 3 | 5 | 7 || 3 | 3 | 1 | 7 | 5 || 5 | 5 | 7 | 1 | 3 || 7 | 7 | 5 | 3 | 1 | Every element squares to 1. Compare $(\mathbb{Z}/10\mathbb{Z})^\times = \{1, 3, 7, 9\}$: there $3^2 = 9$, $3^3 = 27 \equiv 7$, $3^4 = 81 \equiv 1$, so the powers of 3 already give every element. Both groups have order 4, but they are not "the same group": one has an element of order 4 and the other does not. > Watch out: a Latin square is necessary but not sufficient. A table can have every row and column a permutation and still fail associativity. Checking associativity by hand means checking $n^3$ triples, which is why groups are usually built from known ones (permutations, matrices, residues) where associativity is inherited. Chapter 2 — The standard examples Symmetric groups $Sn$ A permutation of $\{1, \dots, n\}$ is a bijection from the set to itself. The permutations form the symmetric group $Sn$ under composition, with $\lvert Sn \rvert = n!$. Composition of functions is associative, the identity map is the identity, and a bijection has an inverse (post 00, Proposition 2.1). Convention used in this series. $\sigma\tau$ means $\sigma \circ \tau$: apply $\tau$ first, then $\sigma$ (right to left, like function composition). Dummit & Foote, Gallian and Artin use this convention; some books and some software (including SymPy's product) use the opposite one, so always check. Cycle notation. The cycle $(a1 \ a2 \ \dots \ ak)$ sends $a1 \mapsto a2 \mapsto \dots \mapsto ak \mapsto a1$ and fixes everything else. It has length $k$; a 2-cycle is a transposition. Every permutation is a product of disjoint cycles, uniquely up to order and up to cycling each cycle's entries. Disjoint cycles commute. To convert two-line notation: the permutation $1 \mapsto 3, 2 \mapsto 5, 3 \mapsto 1, 4 \mapsto 4, 5 \mapsto 6, 6 \mapsto 2$ follows $1 \to 3 \to 1$ and $2 \to 5 \to 6 \to 2$, with 4 fixed, so it is $(1 \ 3)(2 \ 5 \ 6)$. Composing. In $S3$ let $\sigma = (1 \ 2 \ 3)$ and $\tau = (1 \ 2)$. For $\sigma\tau$, follow each point through $\tau$ first, then $\sigma$: $1 \to 2 \to 3$, $2 \to 1 \to 2$, $3 \to 3 \to 1$. So $\sigma\tau = (1 \ 3)$. In the other order, $\tau\sigma$: $1 \to 2 \to 1$, $2 \to 3 \to 3$, $3 \to 1 \to 2$, so $\tau\sigma = (2 \ 3)$. Since $\sigma\tau \neq \tau\sigma$, $S3$ is not abelian, and neither is $Sn$ for any $n \geq 3$. A longer example in $S5$: $(1 \ 3 \ 5)(1 \ 2)(3 \ 4)$. Apply $(3 \ 4)$, then $(1 \ 2)$, then $(1 \ 3 \ 5)$: $1 \to 1 \to 2 \to 2$; $2 \to 2 \to 1 \to 3$; $3 \to 4 \to 4 \to 4$; $4 \to 3 \to 3 \to 5$; $5 \to 5 \to 5 \to 1$. The product is the 5-cycle $(1 \ 2 \ 3 \ 4 \ 5)$. Order of a permutation. A $k$-cycle has order $k$. For a product of disjoint cycles, the order is the least common multiple of the cycle lengths, because the cycles commute and act on separate points. So $(1 \ 2 \ 3)(4 \ 5)$ has order $\operatorname{lcm}(3, 2) = 6$, $(1 \ 3)(2 \ 5 \ 6)$ has order 6, and $(1 \ 2 \ 3 \ 4)(5 \ 6)$ has order 4. > Common pitfall: the lcm rule needs disjoint cycles. $(1 \ 2)(1 \ 3)$ is a product of two elements of order 2, but it equals $(1 \ 3 \ 2)$, which has order 3. Rewrite in disjoint form first. The sign of a permutation Every cycle is a product of transpositions: $(a1 \ a2 \ \dots \ ak) = (a1 \ ak)(a1 \ a{k-1}) \cdots (a1 \ a2)$, which uses $k - 1$ transpositions. Hence every permutation is a product of transpositions, in many different ways. The number of transpositions is not fixed, but its parity is. Theorem 2.1. Define $\operatorname{sgn} \sigma = \prod{1 \leq i < j \leq n} \dfrac{\sigma(j) - \sigma(i)}{j - i}$. Then $\operatorname{sgn} \sigma \in \{+1, -1\}$, $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$, and every transposition has sign $-1$. Consequently a permutation cannot be both a product of an even number and of an odd number of transpositions. Proof. The numerator runs over the same unordered pairs $\{\sigma(i), \sigma(j)\}$ as the denominator, each once, possibly with a sign change, so the product is $\pm 1$; it is $(-1)^{N}$ where $N$ is the number of inversions (pairs $i < j$ with $\sigma(i) > \sigma(j)$). For multiplicativity write $$\operatorname{sgn}(\sigma\tau) = \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}.$$ The second product is $\operatorname{sgn} \tau$. In the first, each factor is unchanged when its two indices are swapped, and as $\{i, j\}$ runs over all pairs so does $\{\tau(i), \tau(j)\}$, so it equals $\operatorname{sgn} \sigma$. Finally, the transposition $(a \ b)$ with $a < b$ has exactly $2(b - a) - 1$ inversions: the pair $(a, b)$ and, for each $c$ strictly between them, the pairs $(a, c)$ and $(c, b)$. That number is odd. $\blacksquare$ So a $k$-cycle has sign $(-1)^{k-1}$: a 3-cycle is even, a transposition is odd. Examples: $\operatorname{sgn}((1 \ 2 \ 3 \ 4)(5 \ 6)) = (-1)^3 (-1)^1 = +1$; $\operatorname{sgn}((1 \ 3)(2 \ 5 \ 6)) = (-1)^1(-1)^2 = -1$. The even permutations form the alternating group $An$, of order $n!/2$ for $n \geq 2$. Dihedral groups $Dn$ For $n \geq 3$, $Dn$ is the group of symmetries of a regular $n$-gon: rigid motions of the plane that map the polygon onto itself. Convention: in this series $Dn$ has order $2n$ (as in Gallian and Artin); Dummit & Foote call the same group $D{2n}$. Label the vertices $1, \dots, n$ counterclockwise. Let $r$ be rotation by $2\pi/n$ counterclockwise and $s$ the reflection in the line through vertex 1 and the centre. Then $$Dn = \{e, r, r^2, \dots, r^{n-1}, \ s, rs, r^2 s, \dots, r^{n-1}s\}, \qquad r^n = s^2 = e, \quad srs = r^{-1}.$$ The $n$ elements $r^k$ are rotations and the $n$ elements $r^k s$ are reflections. The relation $srs = r^{-1}$ (equivalently $sr = r^{-1}s$) lets you move every $s$ to the right, so any word in $r$ and $s$ simplifies to one of the $2n$ normal forms. For example $s r^k = r^{-k} s$ and $(r^k s)^2 = r^k (s r^k s) = r^k r^{-k} = e$: every reflection has order 2. Acting on the vertices, $D3$ is all of $S3$: $r = (1 \ 2 \ 3)$, $s = (2 \ 3)$, and then $r^2 = (1 \ 3 \ 2)$, $rs = (1 \ 2)$, $r^2 s = (1 \ 3)$. Its Cayley table (entry = row $\cdot$ column, column applied first): | $\cdot$ | $e$ | $r$ | $r^2$ | $s$ | $rs$ | $r^2s$ ||---|---|---|---|---|---|---|| $e$ | $e$ | $r$ | $r^2$ | $s$ | $rs$ | $r^2s$ || $r$ | $r$ | $r^2$ | $e$ | $rs$ | $r^2s$ | $s$ || $r^2$ | $r^2$ | $e$ | $r$ | $r^2s$ | $s$ | $rs$ || $s$ | $s$ | $r^2s$ | $rs$ | $e$ | $r^2$ | $r$ || $rs$ | $rs$ | $s$ | $r^2s$ | $r$ | $e$ | $r^2$ || $r^2s$ | $r^2s$ | $rs$ | $s$ | $r^2$ | $r$ | $e$ | Row $s$, column $r$ gives $sr = r^2 s = r^{-1}s$, as the relation predicts. For the square, $D4$ acting on vertices $1, 2, 3, 4$ has $r = (1 \ 2 \ 3 \ 4)$ and $s = (2 \ 4)$; its eight elements are four rotations of orders $1, 4, 2, 4$ and four reflections of order 2. Unlike $D3$, $D4$ is a proper subgroup of $S4$ (order 8 versus 24). Matrix groups - $GLn(\mathbb{R})$, the general linear group: invertible $n \times n$ real matrices under multiplication. Closure: $\det(AB) = \det A \det B \neq 0$.- $SLn(\mathbb{R})$, the special linear group: matrices of determinant 1.- Over the field $\mathbb{F}p = \mathbb{Z}/p\mathbb{Z}$, $GL2(\mathbb{F}p)$ is finite. A matrix is invertible exactly when its columns are linearly independent: $p^2 - 1$ choices for a non-zero first column, then $p^2 - p$ for a second column that is not a multiple of the first. So $\lvert GL2(\mathbb{F}p) \rvert = (p^2 - 1)(p^2 - p)$, giving 6 for $p = 2$ and 48 for $p = 3$. Matrix groups are the standard non-abelian examples: with $A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ and $B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$, $$AB = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}, \qquad BA = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}.$$ The quaternion group $Q8$ and the Klein four group $Q8 = \{\pm 1, \pm i, \pm j, \pm k\}$ with $-1$ central (commuting with everything), $(-1)^2 = 1$, and Hamilton's rules $$i^2 = j^2 = k^2 = ijk = -1, \qquad ij = k, \quad jk = i, \quad ki = j, \quad ji = -k, \quad kj = -i, \quad ik = -j.$$ Orders: $1$ has order 1, $-1$ has order 2, and the six elements $\pm i, \pm j, \pm k$ have order 4. $Q8$ is non-abelian of order 8 but is not $D4$: $D4$ has five elements of order 2, $Q8$ has only one. The Klein four group $V = \{e, a, b, c\}$ has every non-identity element of order 2 and $ab = c$, $bc = a$, $ca = b$. The table of $(\mathbb{Z}/8\mathbb{Z})^\times$ above is $V$ with $a, b, c = 3, 5, 7$. Inside $S4$ it appears as $\{e, (1 \ 2)(3 \ 4), (1 \ 3)(2 \ 4), (1 \ 4)(2 \ 3)\}$. Groups from geometry: the circle and the roots of unity - The circle group $S^1 = \{z \in \mathbb{C} : \lvert z \rvert = 1\}$ under multiplication: $\lvert zw \rvert = \lvert z \rvert \lvert w \rvert$ gives closure and $z^{-1} = \bar{z}$. Writing $z = e^{i\theta}$, multiplying means adding angles.- The $n$-th roots of unity $\mun = \{e^{2\pi i k/n} : k = 0, \dots, n-1\}$ form a subgroup of $S^1$ of order $n$, generated by $\zeta = e^{2\pi i/n}$. They are the rotations of the regular $n$-gon, written as complex numbers.- The orthogonal group $O(n)$ of real matrices with $A^{\mathsf{T}} A = I$ (distance-preserving linear maps) and its subgroup $SO(n)$ of rotations ($\det A = 1$). $SO(2)$ is the circle group again, with $e^{i\theta}$ matching the rotation matrix $\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$. These infinite groups are where group theory meets geometry and physics (Lie groups); this series stays mostly with finite groups. Chapter 3 — Orders of elements Terminology - The order $\lvert g \rvert$ of an element $g$ is the smallest $n \geq 1$ with $g^n = e$, or $\infty$ if no such $n$ exists. In additive notation: the smallest $n$ with $ng = 0$.- The cyclic subgroup generated by $g$ is $\langle g \rangle = \{g^k : k \in \mathbb{Z}\}$. In $\mathbb{Z}$ every non-zero element has infinite order. In $\mathbb{Z}/12\mathbb{Z}$, $4$ has order 3 ($4 + 4 + 4 = 12 \equiv 0$). In $\mathbb{R}^\times$, $-1$ has order 2 and $2$ has infinite order. Lemma 3.1. Let $\lvert g \rvert = n < \infty$. Then $g^m = e$ if and only if $n \mid m$. Also $g^a = g^b$ if and only if $a \equiv b \pmod n$, so $\langle g \rangle = \{e, g, \dots, g^{n-1}\}$ has exactly $n$ elements. Proof. Divide: $m = qn + r$ with $0 \leq r < n$. Then $g^m = (g^n)^q g^r = g^r$. By minimality of $n$, $g^r = e$ forces $r = 0$. The second claim applies the first to $g^{a-b}$. $\blacksquare$ So $\lvert g \rvert = \lvert \langle g \rangle \rvert$: the order of an element equals the order of the subgroup it generates. This is the link that lets Lagrange's theorem in post 02 say that element orders divide group orders. Theorem 3.2. If $\lvert g \rvert = n$ and $k$ is an integer, then $\lvert g^k \rvert = \dfrac{n}{\gcd(k, n)}$. In particular, in $\mathbb{Z}/n\mathbb{Z}$ the class $k$ has order $n/\gcd(k, n)$. Proof. Let $d = \gcd(k, n)$. By Lemma 3.1, $(g^k)^m = e$ iff $n \mid km$ iff $\frac{n}{d} \mid \frac{k}{d} m$. Since $\gcd(\frac{n}{d}, \frac{k}{d}) = 1$, Euclid's lemma turns this into $\frac{n}{d} \mid m$. The smallest positive such $m$ is $n/d$. $\blacksquare$ Examples in $\mathbb{Z}/20\mathbb{Z}$: $\lvert 8 \rvert = 20/\gcd(8, 20) = 20/4 = 5$, and $\langle 8 \rangle = \{0, 4, 8, 12, 16\} = \langle 4 \rangle$. The elements of order 20 are the $k$ with $\gcd(k, 20) = 1$: $1, 3, 7, 9, 11, 13, 17, 19$, which is $\varphi(20) = 8$ elements. Proposition 3.3. In any group: (a) $\lvert g^{-1} \rvert = \lvert g \rvert$; (b) $\lvert ab \rvert = \lvert ba \rvert$; (c) if $ab = ba$ and $\gcd(\lvert a \rvert, \lvert b \rvert) = 1$ (both finite), then $\lvert ab \rvert = \lvert a \rvert \lvert b \rvert$. Proof. (a) $(g^{-1})^m = (g^m)^{-1}$, which is $e$ exactly when $g^m = e$. (b) $ba = a^{-1}(ab)a$, and $(a^{-1} x a)^m = a^{-1} x^m a$ is $e$ exactly when $x^m = e$. (c) Let $m = \lvert a \rvert$, $n = \lvert b \rvert$. Since $a, b$ commute, $(ab)^{mn} = (a^m)^n (b^n)^m = e$. Conversely, if $(ab)^k = e$ then $a^k = b^{-k}$ lies in $\langle a \rangle \cap \langle b \rangle$. The order of this element divides both $m$ and $n$ (Lemma 3.1), so it is 1: $a^k = b^k = e$. Then $m \mid k$ and $n \mid k$, so $mn = \operatorname{lcm}(m, n)$ divides $k$. $\blacksquare$ Part (c) fails without commutativity: in $S3$, $(1 \ 2)$ and $(1 \ 2 \ 3)$ have coprime orders 2 and 3, but their product $(1 \ 2)(1 \ 2 \ 3) = (2 \ 3)$ has order 2, not 6. It also fails without coprimality: in $\mathbb{Z}/4\mathbb{Z}$, $1$ and $3$ both have order 4, and $1 + 3 = 0$ has order 1. > Trick: $\langle k \rangle = \langle \gcd(k, n) \rangle$ in $\mathbb{Z}/n\mathbb{Z}$. Both have order $n/\gcd(k, n)$, and $\gcd(k, n)$ is a multiple of $k$ modulo $n$ by Bézout, so one contains the other and they have the same size. Chapter 4 — Subgroups Terminology - A subgroup $H \leq G$ is a subset that is a group under the same operation.- $\{e\}$ is the trivial subgroup; $H \neq G$ is a proper subgroup. The subgroup tests Theorem 4.1 (two-step test). A non-empty subset $H \subseteq G$ is a subgroup if and only if it is closed under products ($a, b \in H \Rightarrow ab \in H$) and under inverses ($a \in H \Rightarrow a^{-1} \in H$). Theorem 4.2 (one-step test). A non-empty subset $H \subseteq G$ is a subgroup if and only if $a, b \in H \Rightarrow ab^{-1} \in H$. Theorem 4.3 (finite test). A non-empty finite subset $H \subseteq G$ closed under products is a subgroup. Proofs. Two-step: associativity is inherited from $G$; pick $a \in H$, then $a^{-1} \in H$ and $e = aa^{-1} \in H$. One-step: take $b = a$ to get $e = aa^{-1} \in H$; then $a^{-1} = ea^{-1} \in H$; then $ab = a(b^{-1})^{-1} \in H$, so the two-step test applies. The "only if" directions are clear. Finite test: for $a \in H$ the powers $a, a^2, a^3, \dots$ lie in the finite set $H$, so two coincide, $a^i = a^j$ with $i < j$, and $a^{j-i} = e$. If $a = e$ its inverse is itself. Otherwise $j - i \geq 2$ and $a^{-1} = a^{j-i-1}$ is a positive power of $a$, hence in $H$. $\blacksquare$ Examples. - $n\mathbb{Z} = \{nk : k \in \mathbb{Z}\} \leq \mathbb{Z}$: $na - nb = n(a - b)$ (one-step test, additive form $a - b$).- $SLn(\mathbb{R}) \leq GLn(\mathbb{R})$: $\det(AB^{-1}) = \det A / \det B = 1$.- $An \leq Sn$: the product of even permutations is even, and $\sigma^{-1}$ has the same sign as $\sigma$.- The rotations $\{e, r, \dots, r^{n-1}\} = \langle r \rangle \leq Dn$.- $\{z \in \mathbb{C} : z^n = 1\}$, the $n$-th roots of unity, is a subgroup of $\mathbb{C}^\times$ of order $n$. Non-examples. The odd integers (no 0). $\{e, (1 \ 2), (1 \ 3)\} \subseteq S3$ (not closed: $(1 \ 2)(1 \ 3) = (1 \ 3 \ 2)$). $\mathbb{N}$ in $\mathbb{Z}$ (no inverses). Proposition 4.4. The intersection of any collection of subgroups is a subgroup. The union of two subgroups is a subgroup only if one contains the other. Proof. Intersection: one-step test in each subgroup at once. Union: if $a \in H \setminus K$ and $b \in K \setminus H$, then $ab \notin H$ (else $b = a^{-1}(ab) \in H$) and $ab \notin K$ (else $a \in K$). $\blacksquare$ For example $2\mathbb{Z} \cup 3\mathbb{Z}$ contains $2$ and $3$ but not $5$. The smallest subgroup containing a set $S$ is the intersection of all subgroups containing $S$, written $\langle S \rangle$ and called the subgroup generated by $S$. For instance $Dn = \langle r, s \rangle$. Worked example: subgroups of $D4$ of order 4 With $r = (1 \ 2 \ 3 \ 4)$ and $s = (2 \ 4)$ acting on the vertices of a square, the eight elements of $D4$ are | rotations | $e$ | $r = (1 \ 2 \ 3 \ 4)$ | $r^2 = (1 \ 3)(2 \ 4)$ | $r^3 = (1 \ 4 \ 3 \ 2)$ ||---|---|---|---|---|| reflections | $s = (2 \ 4)$ | $rs = (1 \ 2)(3 \ 4)$ | $r^2 s = (1 \ 3)$ | $r^3 s = (1 \ 4)(2 \ 3)$ | Is $K = \{e, r^2, s, r^2 s\}$ a subgroup? It is finite, so by Theorem 4.3 closure is enough. Using $s r^k = r^{-k} s$ and $r^4 = e$: $r^2 \cdot r^2 = e$, $s \cdot s = e$, $r^2 s \cdot r^2 s = e$ (reflections have order 2), $r^2 \cdot s = r^2 s$, $s \cdot r^2 = r^{-2} s = r^2 s$, $r^2 \cdot r^2 s = s$, $r^2 s \cdot r^2 = r^2 r^{-2} s = s$, $s \cdot r^2 s = r^{-2} = r^2$ and $r^2 s \cdot s = r^2$. Every product lands in $K$, so $K \leq D4$. Every non-identity element of $K$ has order 2, so $K$ is a Klein four group, not cyclic. $D4$ has exactly three subgroups of order 4: the cyclic $\langle r \rangle = \{e, r, r^2, r^3\}$, and two Klein four groups, $K$ and $\{e, r^2, rs, r^3 s\}$. The last one, written as permutations, is $\{e, (1 \ 3)(2 \ 4), (1 \ 2)(3 \ 4), (1 \ 4)(2 \ 3)\}$, the copy of $V$ inside $S4$ from Chapter 2. > Common pitfall: a subset is not a subgroup just because it contains $e$ and is closed under inverses. $\{e, s, rs\}$ has both properties but $s \cdot rs = r^{-1} s s = r^{-1} = r^3$ is missing, and in any case a subgroup of $D4$ cannot have 3 elements (post 02: the order of a subgroup divides the order of the group). Chapter 5 — Cyclic groups A group $G$ is cyclic if $G = \langle g \rangle$ for some $g$, called a generator. Cyclic groups are abelian ($g^a g^b = g^{a+b} = g^b g^a$). Examples: $\mathbb{Z} = \langle 1 \rangle = \langle -1 \rangle$; $\mathbb{Z}/n\mathbb{Z} = \langle 1 \rangle$; $(\mathbb{Z}/10\mathbb{Z})^\times = \langle 3 \rangle$; the rotation subgroup $\langle r \rangle$ of $Dn$. Non-examples: $V$ and $(\mathbb{Z}/8\mathbb{Z})^\times$ (no element of order 4), $\mathbb{Q}$ under addition, every non-abelian group. Two groups are isomorphic, $G \cong H$, if there is a bijection $\phi : G \to H$ with $\phi(ab) = \phi(a)\phi(b)$; post 03 studies such maps properly. Lemma 3.1 shows that a cyclic group of order $n$ is isomorphic to $\mathbb{Z}/n\mathbb{Z}$ via $g^k \mapsto [k]$, and an infinite cyclic group is isomorphic to $\mathbb{Z}$. So up to isomorphism, $\mathbb{Z}$ and the $\mathbb{Z}/n\mathbb{Z}$ are the only cyclic groups. Subgroups of cyclic groups Theorem 5.1. Every subgroup of a cyclic group is cyclic. Proof. Let $G = \langle g \rangle$ and $H \leq G$. If $H = \{e\}$, then $H = \langle e \rangle$. Otherwise $H$ contains some $g^k$ with $k \neq 0$, and also its inverse $g^{-k}$, so it contains a positive power of $g$. Let $m$ be the smallest positive integer with $g^m \in H$ (well-ordering). Clearly $\langle g^m \rangle \subseteq H$. Conversely take $g^t \in H$ and divide: $t = qm + r$ with $0 \leq r < m$. Then $g^r = g^t (g^m)^{-q} \in H$, and minimality of $m$ forces $r = 0$. So $g^t = (g^m)^q \in \langle g^m \rangle$, and $H = \langle g^m \rangle$. $\blacksquare$ Applied to $\mathbb{Z}$: every subgroup of $\mathbb{Z}$ is $n\mathbb{Z}$ for a unique $n \geq 0$. Theorem 5.2 (fundamental theorem of finite cyclic groups). Let $G = \langle g \rangle$ have order $n$. For every positive divisor $d$ of $n$, $G$ has exactly one subgroup of order $d$, namely $\langle g^{n/d} \rangle$. It has no subgroups of other orders. Proof. By Theorem 3.2, $\lvert g^{n/d} \rvert = n / \gcd(n/d, n) = n/(n/d) = d$, so a subgroup of order $d$ exists. Now let $H$ be any subgroup. By the proof of Theorem 5.1, $H = \langle g^m \rangle$ where $m$ is the least positive exponent in $H$ (if $H$ is trivial it is the unique subgroup of order 1). Since $g^n = e \in H$, the same division argument shows $m \mid n$. Then $\lvert H \rvert = \lvert g^m \rvert = n/\gcd(m, n) = n/m$. So the order of $H$ divides $n$, and $H$ is determined by its order: $\lvert H \rvert = d$ forces $m = n/d$. $\blacksquare$ Corollary 5.3. In a cyclic group of order $n$, $g^k$ is a generator if and only if $\gcd(k, n) = 1$; there are $\varphi(n)$ generators. The number of elements of order $d$ (for $d \mid n$) is $\varphi(d)$, so $\sum{d \mid n} \varphi(d) = n$. The subgroup lattice of $\mathbb{Z}/12\mathbb{Z}$ The divisors of 12 are $1, 2, 3, 4, 6, 12$, so $\mathbb{Z}/12\mathbb{Z}$ has exactly six subgroups: | order $d$ | subgroup $\langle 12/d \rangle$ | elements | elements of order $d$ ||---|---|---|---|| 1 | $\langle 0 \rangle$ | 0 | 0 || 2 | $\langle 6 \rangle$ | 0, 6 | 6 || 3 | $\langle 4 \rangle$ | 0, 4, 8 | 4, 8 || 4 | $\langle 3 \rangle$ | 0, 3, 6, 9 | 3, 9 || 6 | $\langle 2 \rangle$ | 0, 2, 4, 6, 8, 10 | 2, 10 || 12 | $\langle 1 \rangle$ | all 12 | 1, 5, 7, 11 | The last column has $1 + 1 + 2 + 2 + 2 + 4 = 12$ entries, one for each element, matching $\sum{d \mid 12} \varphi(d) = 12$. Containment follows divisibility: the subgroup of order $d1$ lies inside the subgroup of order $d2$ exactly when $d1 \mid d2$. Drawing each subgroup as a node, with a line up to each subgroup that contains it with no subgroup in between, gives the subgroup lattice (Hasse diagram): The lattice of $\mathbb{Z}/12\mathbb{Z}$ is the divisor lattice of 12 turned into groups. Non-cyclic groups have richer lattices: $D4$, of order 8, has ten subgroups (one of order 1, five of order 2, three of order 4, one of order 8), and two different subgroups of order 4 can exist, which Theorem 5.2 forbids for cyclic groups. > Watch out: "for every divisor $d$ of $\lvert G \rvert$ there is a subgroup of order $d$" is a special property of cyclic groups (and, as post 03 shows, of some other families). Post 02 shows it fails for the alternating group $A4$, of order 12, which has no subgroup of order 6. Cayley's theorem Permutation groups are not just one example among many: every group is one. Theorem 5.4 (Cayley). Every group $G$ is isomorphic to a subgroup of the group $\operatorname{Sym}(G)$ of all permutations of the set $G$. In particular a group of order $n$ is isomorphic to a subgroup of $Sn$. Proof. For $g \in G$ define $\lambdag : G \to G$ by $\lambdag(x) = gx$. It is a bijection, with inverse $\lambda{g^{-1}}$. Associativity gives $\lambdag \lambdah (x) = g(hx) = (gh)x = \lambda{gh}(x)$, so $g \mapsto \lambdag$ respects the operations (with the right-to-left convention for composing). It is injective, because $\lambdag = \lambdah$ gives $g = \lambdag(e) = \lambdah(e) = h$. So $G$ is isomorphic to its image $\{\lambdag\}$, which is a subgroup of $\operatorname{Sym}(G)$ (closed under products by the formula above and under inverses by $\lambdag^{-1} = \lambda{g^{-1}}$). $\blacksquare$ Example: in $(\mathbb{Z}/8\mathbb{Z})^\times = \{1, 3, 5, 7\}$, multiplication by 3 swaps $1 \leftrightarrow 3$ and $5 \leftrightarrow 7$, which is the row of 3 in the Cayley table read as a permutation; multiplication by 5 is $1 \leftrightarrow 5$, $3 \leftrightarrow 7$. Each row of a Cayley table is exactly the permutation $\lambdag$, which is another way to see why rows never repeat an entry. Chapter 6 — Direct products and abelian groups The (external) direct product of groups $G$ and $H$ is $G \times H$ with the componentwise operation $(g1, h1)(g2, h2) = (g1 g2, h1 h2)$. Its identity is $(e, e)$, inverses are $(g^{-1}, h^{-1})$, and $\lvert G \times H \rvert = \lvert G \rvert \lvert H \rvert$. It is abelian exactly when both factors are. Proposition 6.1. If $g$ and $h$ have finite orders, then $\lvert (g, h) \rvert = \operatorname{lcm}(\lvert g \rvert, \lvert h \rvert)$. Proof. $(g, h)^k = (g^k, h^k) = (e, e)$ iff $\lvert g \rvert \mid k$ and $\lvert h \rvert \mid k$ (Lemma 3.1), iff $\operatorname{lcm}(\lvert g \rvert, \lvert h \rvert) \mid k$. $\blacksquare$ Theorem 6.2. $\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ is cyclic if and only if $\gcd(m, n) = 1$. Proof. Every element has order $\operatorname{lcm}(\lvert a \rvert, \lvert b \rvert)$, which divides $\operatorname{lcm}(m, n) = mn/\gcd(m, n)$. If $\gcd(m, n) > 1$, no element reaches order $mn$, so the group is not cyclic. If $\gcd(m, n) = 1$, then $(1, 1)$ has order $\operatorname{lcm}(m, n) = mn$ and generates. $\blacksquare$ So $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z} \cong \mathbb{Z}/6\mathbb{Z}$ (this is the additive half of the Chinese remainder theorem from post 00), while $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \cong V$ is not cyclic. In $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}$ (order 24) the largest element order is $\operatorname{lcm}(4, 6) = 12$; for example $(2, 3)$ has order $\operatorname{lcm}(2, 2) = 2$. Direct products describe all finite abelian groups. The fundamental theorem of finite abelian groups (stated here; proved in the references) says that every finite abelian group is isomorphic to a direct product of cyclic groups of prime-power order, uniquely up to the order of the factors. For order 8 this gives exactly three abelian groups: $\mathbb{Z}/8\mathbb{Z}$, $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ and $(\mathbb{Z}/2\mathbb{Z})^3$. Together with the non-abelian $D4$ and $Q8$ these are all five groups of order 8, up to isomorphism. > Trick: to tell groups apart, count elements of each order; an isomorphism preserves orders. $\mathbb{Z}/8\mathbb{Z}$, $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$, $(\mathbb{Z}/2\mathbb{Z})^3$, $D4$ and $Q8$ have $1, 3, 7, 5, 1$ elements of order 2 respectively. Practice Exercises 1. Show that $G = \mathbb{R} \setminus \{-1\}$ with $a b = a + b + ab$ is an abelian group. What are the identity and the inverse of $a$? <details><summary>Solution</summary> Note $1 + a b = (1 + a)(1 + b)$. Closure: if $a, b \neq -1$ then $(1+a)(1+b) \neq 0$, so $a b \neq -1$. Associativity and commutativity follow from those of multiplication, since both $(a b) c$ and $a (b c)$ equal $(1+a)(1+b)(1+c) - 1$. Identity: $0$. Inverse: $(1 + a)(1 + a') = 1$ gives $a' = \frac{1}{1+a} - 1 = \frac{-a}{1+a}$. In fact $a \mapsto 1 + a$ is an isomorphism to $\mathbb{R}^\times$. </details> 2. In $S6$ write $\sigma = (1 \ 2 \ 3)(4 \ 5)$ and $\tau = (1 \ 4)(2 \ 6)$. Compute $\sigma\tau$ in disjoint cycle form, its order and its sign. <details><summary>Solution</summary> Apply $\tau$ first: $1 \to 4 \to 5$, $5 \to 5 \to 4$, $4 \to 1 \to 2$, $2 \to 6 \to 6$, $6 \to 2 \to 3$, $3 \to 3 \to 1$. So $\sigma\tau = (1 \ 5 \ 4 \ 2 \ 6 \ 3)$, a 6-cycle: order 6, sign $(-1)^5 = -1$. Check with signs: $\operatorname{sgn}\sigma = (+1)(-1) = -1$, $\operatorname{sgn}\tau = (+1)$, product $-1$. </details> 3. Find the order of every element of $(\mathbb{Z}/15\mathbb{Z})^\times$. Is it cyclic? <details><summary>Solution</summary> The group is $\{1, 2, 4, 7, 8, 11, 13, 14\}$, order $\varphi(15) = 8$. Orders: $1$ has order 1; $4, 11, 14$ have order 2 ($16, 121, 196$ are all $\equiv 1$); $2, 7, 8, 13$ have order 4 (e.g. $2^2 = 4$, $2^4 = 16 \equiv 1$). No element has order 8, so it is not cyclic. (It is isomorphic to $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$.) </details> 4. In $Dn$ simplify $s r^3 s r^{2}$ and show that $r^k s$ has order 2 for every $k$. <details><summary>Solution</summary> $s r^3 s = r^{-3}$ (apply $srs = r^{-1}$ three times, or use $s r^k = r^{-k} s$ and $s^2 = e$). So $s r^3 s r^2 = r^{-3} r^2 = r^{-1}$. For the order: $(r^k s)(r^k s) = r^k (s r^k) s = r^k r^{-k} s s = e$, and $r^k s \neq e$. </details> 5. List all subgroups of $\mathbb{Z}/20\mathbb{Z}$ with a generator for each, and find all generators of the subgroup of order 5. <details><summary>Solution</summary> One per divisor of 20: $\langle 0 \rangle$ (order 1), $\langle 10 \rangle$ (2), $\langle 5 \rangle$ (4), $\langle 4 \rangle$ (5), $\langle 2 \rangle$ (10), $\langle 1 \rangle$ (20). The subgroup of order 5 is $\{0, 4, 8, 12, 16\}$; all four non-zero elements generate it (each has order $20/\gcd(k, 20) = 20/4 = 5$), matching $\varphi(5) = 4$. </details> 6. Show that $Q8$ is not isomorphic to $D4$, and that $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}$ is not isomorphic to $\mathbb{Z}/24\mathbb{Z}$. <details><summary>Solution</summary> Isomorphisms preserve element orders. $Q8$ has one element of order 2 ($-1$); $D4$ has five ($r^2$ and the four reflections). $\mathbb{Z}/24\mathbb{Z}$ has an element of order 24; every element of $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/6\mathbb{Z}$ has order dividing $\operatorname{lcm}(4, 6) = 12$. </details> 7. Prove that a group in which every element satisfies $g^2 = e$ is abelian. <details><summary>Solution</summary> Every element is its own inverse. For any $a, b$: $ab = (ab)^{-1} = b^{-1}a^{-1} = ba$. </details> Cheat-sheet | Idea | Statement ||---|---|| Group | associative operation, identity, inverses || Inverse of product | $(ab)^{-1} = b^{-1}a^{-1}$ || Cayley table | every row and column is a permutation || Composition in $Sn$ | $\sigma\tau$ = apply $\tau$ first || Order of a permutation | lcm of disjoint cycle lengths || Sign | $k$-cycle has sign $(-1)^{k-1}$; $\lvert An \rvert = n!/2$ || $Dn$ (order $2n$) | $r^n = s^2 = e$, $srs = r^{-1}$ || $Q8$ | $i^2 = j^2 = k^2 = ijk = -1$ || $GL2(\mathbb{F}p)$ | order $(p^2-1)(p^2-p)$ || Order and powers | $g^m = e$ iff $\lvert g \rvert \mid m$ || Order of a power | $\lvert g^k \rvert = n/\gcd(k, n)$ || One-step test | non-empty and $ab^{-1} \in H$ || Cyclic subgroups | all cyclic; one per divisor $d$, namely $\langle g^{n/d} \rangle$ || Generators of $\mathbb{Z}/n\mathbb{Z}$ | $k$ with $\gcd(k, n) = 1$; $\varphi(n)$ of them || Direct product | $\lvert (g, h) \rvert = \operatorname{lcm}(\lvert g \rvert, \lvert h \rvert)$ || Cyclic product | $\mathbb{Z}/m \times \mathbb{Z}/n$ cyclic iff $\gcd(m, n) = 1$ | What's next Post 02 asks how a subgroup sits inside its group. Translating a subgroup $H$ by an element gives a coset $gH$; the cosets partition $G$ into pieces of equal size, which proves Lagrange's theorem: $\lvert H \rvert$ divides $\lvert G \rvert$. That single fact explains Theorem 5.2's "divisors only" and re-proves Fermat and Euler from post 00. Then comes the question of when the cosets themselves form a group, which leads to normal subgroups and quotient groups such as $\mathbb{Z}/n\mathbb{Z}$, which turns out to be $\mathbb{Z}$ read modulo its subgroup $n\mathbb{Z}$. References - David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004 — Chapters 1–2 (groups, dihedral and symmetric groups, subgroups, cyclic groups, lattices).- Joseph A. Gallian, Contemporary Abstract Algebra, 10th edition, CRC Press, 2021 — Chapters 1–5 and 8 (groups, finite groups and subgroups, cyclic groups, permutation groups, direct products).- Michael Artin, Algebra, 2nd edition, Pearson, 2011 — Chapter 2 (groups).- John B. Fraleigh, A First Course in Abstract Algebra, 7th edition, Addison-Wesley, 2003 — Sections 1–11.- Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), judsonbooks.org — chapters on groups, cyclic groups and permutation groups.- MIT OpenCourseWare, 18.701 Algebra I (Fall 2010) — lectures on groups, subgroups and permutations.- Keith Conrad, Expository papers on group theory (University of Connecticut) — notes on dihedral groups, the sign of a permutation and the quaternion group. > Note: this post is in progress. Planned additions: the subgroup lattice of $D4$ drawn out, a proof of the fundamental theorem of finite abelian groups (or a pointer to it once post 03 has homomorphisms), and matrix representations of $Q8$.

Abstract algebra studies structures: a set together with one or more operations that obey a short list of rules. Instead of asking "what is $7 \cdot 13$?", it asks "which facts about multiplication follow from the rules alone, so that they hold for integers, for clock arithmetic, for matrices, for symmetries of a molecule, all at once?". That shift pays off in many places: symmetry (crystallography, chemistry, physics), cryptography (RSA and elliptic-curve systems are group theory in disguise), coding theory (error-correcting codes on every phone and disk are built over finite fields), and the classical question of solving polynomial equations, which Galois settled with groups. This series follows the standard senior undergraduate path of Dummit & Foote, Gallian, Artin and Fraleigh: groups, then rings and fields, then Galois theory. Post 00 lays the ground: the proof methods used throughout, sets and functions, equivalence relations, and the arithmetic of the integers up to modular arithmetic, the Chinese remainder theorem and a small but complete RSA example. Every later post uses $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$ as its first examples. > Series map: 00 Integers, Relations & Modular Arithmetic (this post) → 01 Groups & Subgroups → 02 Cosets, Lagrange & Quotient Groups → 03 Homomorphisms, Group Actions & Sylow → 04 Rings, Ideals & Fields → 05 Field Extensions & Galois Theory. Learning Outcome - Read and write the four basic proof patterns: direct, contrapositive, contradiction, induction.- Decide whether a function is injective, surjective or bijective, and use the fact that bijections are exactly the invertible functions.- Prove that an equivalence relation on a set is the same thing as a partition of that set.- State and prove the division algorithm from the well-ordering principle.- Run the Euclidean algorithm and the extended Euclidean algorithm by hand, and prove Bézout's identity and Euclid's lemma.- Prove the fundamental theorem of arithmetic (existence and uniqueness).- Compute in $\mathbb{Z}/n\mathbb{Z}$, find inverses, and decide which classes are units.- Use Euler's $\varphi$ function, Fermat's little theorem and Euler's theorem to reduce huge powers.- Solve simultaneous congruences with the Chinese remainder theorem.- Carry out a toy RSA key generation, encryption and decryption, and explain why decryption works. Chapter 1 — The proof toolkit Abstract algebra is a proof-based subject. Almost every statement is an implication "if $P$ then $Q$", and there are four standard ways to prove one. Terminology - Proposition / theorem / lemma / corollary — a proved statement; a lemma is a helper, a corollary follows quickly from a theorem.- Definition — fixes the meaning of a word. Definitions are "if and only if" even when written with "if".- Contrapositive of "$P \Rightarrow Q$" is "not $Q \Rightarrow$ not $P$". It is logically equivalent to the original.- Converse of "$P \Rightarrow Q$" is "$Q \Rightarrow P$". It is a different statement and may be false.- Counterexample — one concrete case that shows a universal statement is false. Direct proof Assume $P$, reason forward, reach $Q$. Claim. The sum of two odd integers is even. Proof. Odd integers can be written $2a+1$ and $2b+1$ with $a, b \in \mathbb{Z}$. Their sum is $2a + 2b + 2 = 2(a+b+1)$, which is even. $\blacksquare$ Proof by contrapositive Prove "not $Q \Rightarrow$ not $P$" instead. Claim. If $n^2$ is even, then $n$ is even. Proof. Contrapositive: if $n$ is odd then $n^2$ is odd. Write $n = 2k+1$; then $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$, which is odd. $\blacksquare$ Proof by contradiction Assume the statement is false and derive something impossible. Claim. $\sqrt{2}$ is irrational. Proof. Suppose $\sqrt{2} = p/q$ with integers $p, q$, $q \neq 0$, and the fraction in lowest terms. Then $p^2 = 2q^2$, so $p^2$ is even, so $p$ is even by the previous claim. Write $p = 2m$: then $4m^2 = 2q^2$, so $q^2 = 2m^2$ is even and $q$ is even. Both $p$ and $q$ are even, contradicting lowest terms. $\blacksquare$ Proof by induction To prove a statement $S(n)$ for all integers $n \geq n0$: prove $S(n0)$ (the base case), then prove $S(k) \Rightarrow S(k+1)$ for every $k \geq n0$ (the inductive step). In strong induction the inductive step may assume $S(n0), \dots, S(k)$ all at once. Claim. For every $n \geq 1$, $1 + 3 + 5 + \dots + (2n-1) = n^2$. Proof. Base case $n=1$: $1 = 1^2$. Inductive step: if the sum of the first $k$ odd numbers is $k^2$, adding the next one gives $k^2 + (2k+1) = (k+1)^2$. $\blacksquare$ > Watch out: proving the converse is not proving the statement. "If $n$ is even then $n^2$ is even" is true, but it does not prove "if $n^2$ is even then $n$ is even"; that needed its own proof above. Chapter 2 — Sets, functions and equivalence relations Terminology - $\mathbb{N} = \{0, 1, 2, \dots\}$ (some books start at 1; this series includes 0), $\mathbb{Z}$ the integers, $\mathbb{Q}$ the rationals, $\mathbb{R}$ the reals, $\mathbb{C}$ the complex numbers.- $A \times B = \{(a, b) : a \in A, b \in B\}$ is the Cartesian product.- A function $f : A \to B$ assigns to each $a \in A$ exactly one $f(a) \in B$. $A$ is the domain, $B$ the codomain, $f(A)$ the image.- $f$ is injective (one-to-one) if $f(a1) = f(a2)$ implies $a1 = a2$.- $f$ is surjective (onto) if every $b \in B$ equals $f(a)$ for some $a$.- $f$ is bijective if it is both. A bijection from a set to itself is a permutation of the set.- A relation on $A$ is a subset $R \subseteq A \times A$; write $a \sim b$ when $(a, b) \in R$. Functions and inverses Examples on $\mathbb{Z}$: $f(x) = 2x$ is injective but not surjective (odd numbers are missed). $g(x) = \lfloor x/2 \rfloor$ is surjective but not injective ($g(0) = g(1) = 0$). $h(x) = x + 5$ is bijective with inverse $x \mapsto x - 5$. Proposition 2.1. A function $f : A \to B$ has an inverse function $g : B \to A$ (with $g \circ f = \mathrm{id}A$ and $f \circ g = \mathrm{id}B$) if and only if $f$ is bijective. Proof. If $g$ exists: $f(a1) = f(a2)$ gives $a1 = g(f(a1)) = g(f(a2)) = a2$, so $f$ is injective; and any $b$ equals $f(g(b))$, so $f$ is surjective. Conversely, if $f$ is bijective, each $b$ has exactly one preimage; define $g(b)$ to be it. Then both compositions are identities. $\blacksquare$ Proposition 2.2 (pigeonhole). If $A$ is a finite set and $f : A \to A$ is injective, then $f$ is bijective. Proof. An injective $f$ sends the $\lvert A\rvert$ elements of $A$ to $\lvert A\rvert$ distinct elements of $A$, so the image is all of $A$. $\blacksquare$ This small fact drives the proofs of Fermat's little theorem below and of Cayley's theorem later in the series. It is false for infinite sets: $x \mapsto 2x$ on $\mathbb{Z}$ is injective but not surjective. Equivalence relations A relation $\sim$ on $A$ is an equivalence relation if it is - reflexive: $a \sim a$ for all $a$;- symmetric: $a \sim b$ implies $b \sim a$;- transitive: $a \sim b$ and $b \sim c$ imply $a \sim c$. The equivalence class of $a$ is $[a] = \{x \in A : x \sim a\}$. Examples: equality on any set; "same birthday" on people; "$a - b$ is divisible by $n$" on $\mathbb{Z}$ (Chapter 5); "same determinant" on $2 \times 2$ matrices. Non-examples: $\leq$ on $\mathbb{R}$ is reflexive and transitive but not symmetric; "$\lvert a - b\rvert \leq 1$" on $\mathbb{R}$ is reflexive and symmetric but not transitive ($0 \sim 1$, $1 \sim 2$, but $0 \not\sim 2$). A partition of $A$ is a collection of non-empty subsets of $A$ such that every element of $A$ lies in exactly one of them. Theorem 2.3 (equivalence relations = partitions). If $\sim$ is an equivalence relation on $A$, its equivalence classes form a partition of $A$. Conversely, every partition $\mathcal{P}$ of $A$ comes from exactly one equivalence relation: $a \sim b$ if and only if $a$ and $b$ lie in the same block of $\mathcal{P}$. Proof. Each class is non-empty and every $a$ lies in a class, because $a \in [a]$ by reflexivity. It remains to show that two classes are either equal or disjoint. Suppose $c \in [a] \cap [b]$, so $c \sim a$ and $c \sim b$. Take any $x \in [a]$: then $x \sim a$, $a \sim c$ (symmetry), $c \sim b$, so $x \sim b$ by transitivity twice, and $x \in [b]$. Hence $[a] \subseteq [b]$, and by the same argument $[b] \subseteq [a]$. So overlapping classes are equal. Conversely, given a partition, "same block" is reflexive (every element is in a block), symmetric (obvious), and transitive (if $a, b$ share block $P$ and $b, c$ share block $Q$, then $b \in P \cap Q$, so $P = Q$ because blocks are disjoint). Its classes are exactly the blocks. $\blacksquare$ > Trick: to show two classes are equal it is enough to find one common element. This "one overlap means equal" step is used again for cosets in post 02, where it gives Lagrange's theorem almost for free. Chapter 3 — Divisibility, gcd and the Euclidean algorithm Terminology - $a$ divides $b$, written $a \mid b$, if $b = ak$ for some integer $k$. Every integer divides $0$; $0$ divides only $0$.- A prime is an integer $p \geq 2$ whose only positive divisors are $1$ and $p$. An integer $n \geq 2$ that is not prime is composite.- The greatest common divisor $\gcd(a, b)$ of integers not both zero is the largest integer dividing both. Set $\gcd(0, 0) = 0$.- $a$ and $b$ are coprime (relatively prime) if $\gcd(a, b) = 1$.- Well-ordering principle: every non-empty set of non-negative integers has a least element. It is equivalent to induction and is taken as an axiom about $\mathbb{N}$. The division algorithm Theorem 3.1 (division algorithm). For integers $a$ and $b$ with $b > 0$ there are unique integers $q, r$ with $$a = qb + r, \qquad 0 \leq r < b.$$ Proof. Existence: let $S = \{a - kb : k \in \mathbb{Z}, \ a - kb \geq 0\}$. $S$ is non-empty (take $k = -\lvert a\rvert$; then $a - kb = a + \lvert a\rvert b \geq a + \lvert a\rvert \geq 0$). By well-ordering $S$ has a least element $r = a - qb \geq 0$. If $r \geq b$, then $r - b = a - (q+1)b$ is a smaller element of $S$, a contradiction. So $0 \leq r < b$. Uniqueness: if $qb + r = q'b + r'$ with both remainders in $[0, b)$, then $b(q - q') = r' - r$ and $\lvert r' - r\rvert < b$. The only multiple of $b$ strictly between $-b$ and $b$ is $0$, so $r = r'$ and $q = q'$. $\blacksquare$ For negative $a$ the remainder is still non-negative: $-17 = (-4) \cdot 5 + 3$, not $(-3) \cdot 5 - 2$. > Common pitfall: in many programming languages returns (C, Java, JavaScript) while Python returns . Mathematics always uses $0 \leq r < b$. The Euclidean algorithm Lemma 3.2. If $a = qb + r$, then $\gcd(a, b) = \gcd(b, r)$. Proof. Any common divisor of $a$ and $b$ divides $r = a - qb$; any common divisor of $b$ and $r$ divides $a = qb + r$. The two pairs have the same common divisors, so the same greatest one. $\blacksquare$ Repeating the division algorithm, the remainders strictly decrease and so reach $0$; the last non-zero remainder is the gcd. For $\gcd(240, 46)$: $$\begin{aligned}240 &= 5 \cdot 46 + 10 \\46 &= 4 \cdot 10 + 6 \\10 &= 1 \cdot 6 + 4 \\6 &= 1 \cdot 4 + 2 \\4 &= 2 \cdot 2 + 0\end{aligned}$$ So $\gcd(240, 46) = 2$. The number of steps is small: it grows like the number of digits (Lamé's theorem bounds it by five times the number of decimal digits of the smaller number). Bézout's identity and the extended algorithm Theorem 3.3 (Bézout). For integers $a, b$ not both zero, there are integers $x, y$ with $ax + by = \gcd(a, b)$. Moreover $\gcd(a, b)$ is the smallest positive integer of the form $ax + by$. Proof. Let $S = \{ax + by : x, y \in \mathbb{Z}\} \cap \{1, 2, 3, \dots\}$. It is non-empty (it contains $a^2 + b^2 > 0$), so it has a least element $d = ax0 + by0$. Divide: $a = qd + r$ with $0 \leq r < d$. Then $r = a - q(ax0 + by0) = a(1 - qx0) + b(-qy0)$ has the same form, so by minimality $r = 0$ and $d \mid a$. Likewise $d \mid b$. Any common divisor $c$ of $a, b$ divides $ax0 + by0 = d$, so $c \leq d$. Hence $d = \gcd(a, b)$. $\blacksquare$ The proof shows $x, y$ exist but does not find them. The extended Euclidean algorithm does: keep, next to every remainder $ri$, integers $si, ti$ with $ri = 240 si + 46 ti$. Start with $r0 = 240 = 240 \cdot 1 + 46 \cdot 0$ and $r1 = 46 = 240 \cdot 0 + 46 \cdot 1$; each new row is "row two above minus $q$ times row above". | $i$ | $ri$ | $qi$ | $si$ | $ti$ | check $240 si + 46 ti$ ||---|---|---|---|---|---|| 0 | 240 | — | 1 | 0 | 240 || 1 | 46 | — | 0 | 1 | 46 || 2 | 10 | 5 | 1 | −5 | 240 − 230 = 10 || 3 | 6 | 4 | −4 | 21 | −960 + 966 = 6 || 4 | 4 | 1 | 5 | −26 | 1200 − 1196 = 4 || 5 | 2 | 1 | −9 | 47 | −2160 + 2162 = 2 || 6 | 0 | 2 | — | — | stop | So $2 = 240 \cdot (-9) + 46 \cdot 47$. The same answer comes from back-substitution, reading the divisions from the bottom up: $2 = 6 - 4 = 6 - (10 - 6) = 2 \cdot 6 - 10 = 2(46 - 4 \cdot 10) - 10 = 2 \cdot 46 - 9 \cdot 10 = 2 \cdot 46 - 9(240 - 5 \cdot 46) = 47 \cdot 46 - 9 \cdot 240$. > Trick: the $x, y$ are not unique: $(x + 23k, \ y - 120k)$ works for every integer $k$, because $240 \cdot 23 = 46 \cdot 120$. Add a check column like the one above; one wrong sign early ruins every later row. Euclid's lemma Theorem 3.4 (Euclid's lemma). If $a \mid bc$ and $\gcd(a, b) = 1$, then $a \mid c$. In particular, if a prime $p$ divides $bc$, then $p \mid b$ or $p \mid c$. Proof. By Bézout, $ax + by = 1$ for some $x, y$. Multiply by $c$: $c = acx + bcy$. The number $a$ divides $acx$ and divides $bcy$ (because $a \mid bc$), so $a \mid c$. For the prime case: if $p \nmid b$ then $\gcd(p, b) = 1$ (the only positive divisors of $p$ are $1$ and $p$), so $p \mid c$. $\blacksquare$ > Watch out: the prime hypothesis matters. $6 \mid 4 \cdot 9 = 36$ but $6 \nmid 4$ and $6 \nmid 9$. Chapter 4 — The fundamental theorem of arithmetic Theorem 4.1 (fundamental theorem of arithmetic). Every integer $n \geq 2$ can be written as a product of primes $n = p1 p2 \cdots pk$, and this factorisation is unique up to the order of the factors. Proof. Existence, by strong induction on $n$. If $n$ is prime, it is its own factorisation. Otherwise $n = ab$ with $2 \leq a, b < n$; by the induction hypothesis both $a$ and $b$ are products of primes, so $n$ is too. Uniqueness, by induction on $n$. Suppose $n = p1 \cdots pk = q1 \cdots ql$ with all $pi, qj$ prime. Then $p1$ divides $q1 \cdots ql$, so by Euclid's lemma (applied repeatedly) $p1 \mid qj$ for some $j$. Since $qj$ is prime and $p1 \geq 2$, $p1 = qj$. Reorder so that $j = 1$ and cancel: $p2 \cdots pk = q2 \cdots ql$ is a smaller number (or both sides are empty products equal to $1$), and by induction the remaining primes agree up to order. $\blacksquare$ Grouping equal primes gives the canonical form $n = p1^{e1} \cdots pr^{er}$ with $p1 < \dots < pr$. Examples: $360 = 2^3 \cdot 3^2 \cdot 5$, $1001 = 7 \cdot 11 \cdot 13$, $2026 = 2 \cdot 1013$. Corollary 4.2 (Euclid). There are infinitely many primes. Proof. Given primes $p1, \dots, pk$, the number $N = p1 \cdots pk + 1$ has a prime factor $p$ by Theorem 4.1. If $p$ were some $pi$, then $p$ would divide $N - p1 \cdots pk = 1$, which is impossible. So no finite list contains every prime. $\blacksquare$ Uniqueness is not automatic. In the set $\{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$, $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ gives two genuinely different factorisations into elements that cannot be split further. Explaining when unique factorisation holds is one of the main themes of ring theory (post 04). Chapter 5 — Congruences and $\mathbb{Z}/n\mathbb{Z}$ Terminology - Fix an integer $n \geq 1$, the modulus. $a$ is congruent to $b$ modulo $n$, written $a \equiv b \pmod{n}$, if $n \mid a - b$.- The class of $a$ is $[a]n = \{a + kn : k \in \mathbb{Z}\}$, also written $\bar{a}$ or just $a$ when the modulus is clear.- $\mathbb{Z}/n\mathbb{Z}$ (also written $\mathbb{Z}n$) is the set of the $n$ classes $[0], [1], \dots, [n-1]$.- A class $[a]$ is a unit if there is $[b]$ with $[a][b] = [1]$. The units form $(\mathbb{Z}/n\mathbb{Z})^\times$, also written $U(n)$.- A non-zero class $[a]$ is a zero divisor if $[a][b] = [0]$ for some non-zero $[b]$. Congruence mod $n$ is an equivalence relation: $n \mid 0$ (reflexive); $n \mid a - b$ implies $n \mid b - a$ (symmetric); $n \mid a - b$ and $n \mid b - c$ imply $n \mid a - c$ (transitive). By Theorem 2.3 its classes partition $\mathbb{Z}$, and by the division algorithm each class contains exactly one of $0, 1, \dots, n-1$, so there are exactly $n$ classes. Arithmetic on classes Define $[a] + [b] = [a + b]$ and $[a] \cdot [b] = [ab]$. Proposition 5.1. These operations are well defined: the result does not depend on which representatives are chosen. Proof. Suppose $a \equiv a'$ and $b \equiv b'$, say $a' = a + kn$ and $b' = b + ln$. Then $a' + b' = a + b + (k + l)n \equiv a + b$ and $a'b' = ab + (al + bk + kln)n \equiv ab$. $\blacksquare$ "Well defined" is the central worry whenever an operation is defined on classes through representatives. The same check, done for cosets, is what forces the definition of a normal subgroup in post 02. In practice: reduce early and often. For example $3^{100} \bmod 7$: $3^6 \equiv 1 \pmod 7$ (checked below), and $100 = 6 \cdot 16 + 4$, so $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 3^4 = 81 \equiv 4 \pmod 7$. Units and zero divisors In $\mathbb{Z}/12\mathbb{Z}$: $[3][4] = [12] = [0]$, so $[3]$ and $[4]$ are zero divisors. On the other hand $[5][5] = [25] = [1]$, $[7][7] = [49] = [1]$ and $[11][11] = [121] = [1]$. The units are exactly $[1], [5], [7], [11]$, the classes coprime to $12$, and each of them is its own inverse. Theorem 5.2. $[a]$ is a unit in $\mathbb{Z}/n\mathbb{Z}$ if and only if $\gcd(a, n) = 1$. If $\gcd(a, n) = d > 1$ and $n \nmid a$, then $[a]$ is a zero divisor. Proof. If $\gcd(a, n) = 1$, Bézout gives $ax + ny = 1$, so $ax \equiv 1$ and $[x]$ is the inverse. Conversely if $ab \equiv 1$, then $ab - 1 = kn$, so $ab - kn = 1$ and every common divisor of $a$ and $n$ divides $1$. For the last claim: $a \cdot (n/d) = (a/d) \cdot n \equiv 0$, and $[n/d] \neq [0]$ because $0 < n/d < n$. $\blacksquare$ Corollary 5.3. $\mathbb{Z}/n\mathbb{Z}$ has every non-zero class invertible if and only if $n$ is prime. Theorem 5.2 is also an algorithm: the inverse is the Bézout coefficient. To invert $17$ modulo $43$: $43 = 2 \cdot 17 + 9$, $17 = 1 \cdot 9 + 8$, $9 = 1 \cdot 8 + 1$. Back-substitute: $1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$. So $17^{-1} \equiv -5 \equiv 38 \pmod{43}$. Check: $17 \cdot 38 = 646 = 15 \cdot 43 + 1$. Linear congruences Theorem 5.4. The congruence $ax \equiv b \pmod n$ has a solution if and only if $d = \gcd(a, n)$ divides $b$. In that case it has exactly $d$ solutions modulo $n$. Proof sketch. A solution means $ax - ny = b$ for some $y$, and by Bézout the values of $ax - ny$ are exactly the multiples of $d$. If $d \mid b$, divide through: $(a/d)x \equiv b/d \pmod{n/d}$, and $a/d$ is a unit mod $n/d$, so $x$ is unique mod $n/d$. That single class mod $n/d$ splits into $d$ classes mod $n$. $\blacksquare$ Example: $14x \equiv 6 \pmod{20}$. Here $\gcd(14, 20) = 2$ divides $6$. Divide by 2: $7x \equiv 3 \pmod{10}$. Since $7 \cdot 3 = 21 \equiv 1$, $7^{-1} \equiv 3 \pmod{10}$, so $x \equiv 9 \pmod{10}$, giving $x \equiv 9$ or $19 \pmod{20}$. Check: $14 \cdot 9 = 126 = 6 \cdot 20 + 6$ and $14 \cdot 19 = 266 = 13 \cdot 20 + 6$. > Common pitfall: you may not "divide both sides" of a congruence by a number that is not a unit. $2 \cdot 3 \equiv 2 \cdot 9 \pmod{12}$, but $3 \not\equiv 9 \pmod{12}$. Division by $a$ modulo $n$ is multiplication by $a^{-1}$, which exists only when $\gcd(a, n) = 1$; otherwise the modulus must be divided too, as above. Chapter 6 — Euler's phi, Fermat and Euler Euler's phi function $\varphi(n)$ is the number of integers in $\{1, \dots, n\}$ coprime to $n$; by Theorem 5.2 it is the number of units, $\varphi(n) = \lvert(\mathbb{Z}/n\mathbb{Z})^\times\rvert$. - For a prime $p$: $\varphi(p) = p - 1$.- For a prime power: $\varphi(p^k) = p^k - p^{k-1}$, because the numbers in $\{1, \dots, p^k\}$ not coprime to $p^k$ are exactly the $p^{k-1}$ multiples of $p$.- Multiplicative: if $\gcd(m, n) = 1$ then $\varphi(mn) = \varphi(m)\varphi(n)$. This follows from the Chinese remainder theorem (Chapter 7): $a$ is coprime to $mn$ exactly when it is coprime to both $m$ and $n$, and the CRT bijection matches such $a$ with pairs of units. Together these give, for $n = p1^{e1} \cdots pr^{er}$, $$\varphi(n) = n \prod{p \mid n} \left(1 - \frac{1}{p}\right).$$ Examples: $\varphi(12) = 12 \cdot \tfrac12 \cdot \tfrac23 = 4$ (the units $1, 5, 7, 11$); $\varphi(36) = 36 \cdot \tfrac12 \cdot \tfrac23 = 12$; $\varphi(100) = 100 \cdot \tfrac12 \cdot \tfrac45 = 40$; $\varphi(35) = \varphi(5)\varphi(7) = 4 \cdot 6 = 24$. Fermat's little theorem Theorem 6.1 (Fermat's little theorem). If $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. Consequently $a^p \equiv a \pmod p$ for every integer $a$. Proof. Consider the map $x \mapsto ax$ on the set $R = \{[1], [2], \dots, [p-1]\}$ of non-zero classes mod $p$. It lands in $R$ (a product of two units is a unit, so never $[0]$) and is injective, because $ax \equiv ay$ implies $x \equiv y$ after multiplying by $a^{-1}$. By the pigeonhole Proposition 2.2 it is a bijection, so it just reorders $R$. Multiply all elements of $R$ both ways: $$(a \cdot 1)(a \cdot 2) \cdots (a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod p,$$ that is $a^{p-1} (p-1)! \equiv (p-1)! \pmod p$. Every factor of $(p-1)!$ is a unit, so $(p-1)!$ is a unit and can be cancelled: $a^{p-1} \equiv 1$. For the second statement multiply by $a$; if $p \mid a$ both sides are $0$. $\blacksquare$ Check with $p = 7$, $a = 3$: multiplying $1, 2, 3, 4, 5, 6$ by 3 gives $3, 6, 2, 5, 1, 4$ modulo 7, the same six classes in a new order, and $3^6 = 729 = 104 \cdot 7 + 1$. Euler's theorem Theorem 6.2 (Euler). If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod n$. Proof. Repeat the proof above with the set $U$ of the $\varphi(n)$ units mod $n$ instead of $R$: $x \mapsto ax$ permutes $U$, so $a^{\varphi(n)} \prod{u \in U} u \equiv \prod{u \in U} u$, and the product of units is a unit, so it cancels. $\blacksquare$ Fermat is the case $n = p$. Post 02 re-proves both in one line from Lagrange's theorem, because $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group of order $\varphi(n)$ and the order of an element divides the order of the group. Example: the last digit of $7^{222}$. $\varphi(10) = 4$ and $\gcd(7, 10) = 1$, so $7^4 \equiv 1 \pmod{10}$. Since $222 = 4 \cdot 55 + 2$, $7^{222} \equiv 7^2 = 49 \equiv 9$. The last digit is 9. > Watch out: Euler's theorem needs $\gcd(a, n) = 1$. $2^{\varphi(4)} = 2^2 = 4 \equiv 0 \pmod 4$, not 1. Also, $\varphi(n)$ is an exponent that always works, not always the smallest one: modulo 12, every unit already satisfies $u^2 \equiv 1$ although $\varphi(12) = 4$. Chapter 7 — The Chinese remainder theorem Theorem 7.1 (Chinese remainder theorem). Let $n1, \dots, nk$ be pairwise coprime positive integers and $N = n1 \cdots nk$. For any integers $a1, \dots, ak$ the system $$x \equiv a1 \pmod{n1}, \quad \dots, \quad x \equiv ak \pmod{nk}$$ has a solution, and any two solutions are congruent modulo $N$. Proof. Existence: put $Ni = N / ni$. Since $ni$ is coprime to every other $nj$, it is coprime to $Ni$, so there is $Mi$ with $Ni Mi \equiv 1 \pmod{ni}$. Let $x = \sumi ai Ni Mi$. Modulo $nj$, every term with $i \neq j$ vanishes (because $nj \mid Ni$), and the $j$-th term is $aj \cdot 1$. Uniqueness: if $x, x'$ both work, each $ni$ divides $x - x'$; the $ni$ are pairwise coprime, so (by Euclid's lemma, repeatedly) their product $N$ divides $x - x'$. $\blacksquare$ Worked example (Sunzi's classic puzzle). Find $x$ with $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. Here $N = 105$. | $i$ | $ni$ | $ai$ | $Ni = N/ni$ | $Ni \bmod ni$ | $Mi$ | $ai Ni Mi$ ||---|---|---|---|---|---|---|| 1 | 3 | 2 | 35 | 2 | 2 | 140 || 2 | 5 | 3 | 21 | 1 | 1 | 63 || 3 | 7 | 2 | 15 | 1 | 1 | 30 | Sum: $140 + 63 + 30 = 233 \equiv 23 \pmod{105}$. Check: $23 = 7 \cdot 3 + 2$, $23 = 4 \cdot 5 + 3$, $23 = 3 \cdot 7 + 2$. In structural language, the theorem says that the map $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n1\mathbb{Z} \times \dots \times \mathbb{Z}/nk\mathbb{Z}$, $[x] \mapsto ([x]{n1}, \dots, [x]{nk})$, is a bijection that respects addition and multiplication. Both sides have $N$ elements, so it is enough to know the map is injective, which is the uniqueness part. Post 01 meets the additive version as "$\mathbb{Z}/6\mathbb{Z}$ is the same group as $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}$", and post 04 the ring version. > Common pitfall: the moduli must be pairwise coprime. The system $x \equiv 0 \pmod 4$, $x \equiv 1 \pmod 6$ has no solution: the first says $x$ is even, the second says $x$ is odd. Chapter 8 — A toy RSA RSA (Rivest, Shamir and Adleman, 1978) is Euler's theorem put to work. The numbers below are tiny so that every step can be checked by hand; real keys use primes of about 1024 bits or more and a padding scheme, and textbook RSA as shown here is not secure. Key generation. 1. Pick primes $p = 11$, $q = 17$. The modulus is $n = pq = 187$.2. $\varphi(n) = (p-1)(q-1) = 10 \cdot 16 = 160$.3. Pick a public exponent $e$ coprime to 160: $e = 7$.4. The private exponent is $d = e^{-1} \bmod \varphi(n)$: since $7 \cdot 23 = 161 = 160 + 1$, $d = 23$. Public key $(n, e) = (187, 7)$; private key $d = 23$. Encryption of the message $m = 88$ (any integer with $0 \leq m < n$): $c = m^e \bmod n$, computed by repeated squaring so that no number exceeds $186^2$: $$\begin{aligned}88^2 &= 7744 \equiv 77 \pmod{187} \\88^4 &\equiv 77^2 = 5929 \equiv 132 \\88^7 &= 88^4 \cdot 88^2 \cdot 88 \equiv 132 \cdot 77 \cdot 88 \equiv 66 \cdot 88 = 5808 \equiv 11\end{aligned}$$ So the ciphertext is $c = 11$. Decryption: $c^d = 11^{23} \bmod 187$. Write $23 = 16 + 4 + 2 + 1$ and square repeatedly: $11^2 = 121$, $11^4 \equiv 121^2 = 14641 \equiv 55$, $11^8 \equiv 55^2 = 3025 \equiv 33$, $11^{16} \equiv 33^2 = 1089 \equiv 154$. Then $$11^{23} \equiv 154 \cdot 55 \cdot 121 \cdot 11 \equiv 55 \cdot 121 \cdot 11 \equiv 110 \cdot 11 = 1210 \equiv 88 \pmod{187}.$$ The original message comes back. Why it works. $ed = 1 + k\varphi(n)$ for some $k \geq 0$. If $\gcd(m, n) = 1$, Euler gives $m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m \pmod n$. (If $m$ shares a factor with $n$, the result still holds: check it modulo $p$ and modulo $q$ separately with Fermat, then combine with the CRT.) Why it is believed hard to break. Anyone who knows $\varphi(n)$ can compute $d$ with the extended Euclidean algorithm, and $\varphi(n)$ is easy from $p$ and $q$. So the security rests on the difficulty of factoring $n$; no fast classical factoring algorithm is known. Practice Exercises 1. Prove by induction that $6 \mid n^3 - n$ for every integer $n \geq 0$. <details><summary>Solution</summary> Base: $0^3 - 0 = 0$. Step: $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1)$. The first term is divisible by 6 by hypothesis; $k(k+1)$ is a product of consecutive integers, hence even, so $3k(k+1)$ is divisible by 6. (A direct proof also works: $n^3 - n = (n-1)n(n+1)$ is a product of three consecutive integers, so it is divisible by 2 and by 3.) </details> 2. On $\mathbb{R}^2$ define $(x1, y1) \sim (x2, y2)$ if $x1^2 + y1^2 = x2^2 + y2^2$. Show this is an equivalence relation and describe the partition. <details><summary>Solution</summary> It is "$f(p1) = f(p2)$" for the function $f(x, y) = x^2 + y^2$, and any relation of that form inherits reflexivity, symmetry and transitivity from equality. The classes are the circles centred at the origin, plus the single point $(0,0)$. </details> 3. Use the extended Euclidean algorithm to find $\gcd(252, 198)$ and integers $x, y$ with $252x + 198y = \gcd(252, 198)$. <details><summary>Solution</summary> $252 = 1 \cdot 198 + 54$, $198 = 3 \cdot 54 + 36$, $54 = 1 \cdot 36 + 18$, $36 = 2 \cdot 18$. So the gcd is 18. Back-substitute: $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198$. Check: $1008 - 990 = 18$. </details> 4. Find all solutions of $14x \equiv 6 \pmod{20}$ by the method of Theorem 5.4, and explain why $14x \equiv 5 \pmod{20}$ has none. <details><summary>Solution</summary> As in Chapter 5: $x \equiv 9$ or $19 \pmod{20}$. For the second congruence, $\gcd(14, 20) = 2$ does not divide 5: the left side $14x - 20y$ is always even, the right side is odd. </details> 5. Compute $2^{1000} \bmod 13$ and the last two digits of $3^{2026}$. <details><summary>Solution</summary> By Fermat $2^{12} \equiv 1 \pmod{13}$; $1000 = 12 \cdot 83 + 4$, so $2^{1000} \equiv 2^4 = 16 \equiv 3$. For the last two digits work mod 100: $\varphi(100) = 40$ and $\gcd(3, 100) = 1$, so $3^{40} \equiv 1$; $2026 = 40 \cdot 50 + 26$, so $3^{2026} \equiv 3^{26}$. Now $3^5 = 243 \equiv 43$, $3^{10} \equiv 43^2 = 1849 \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 1$. (The order of 3 mod 100 is actually 20, a divisor of 40.) So $3^{26} \equiv 3^{6} = 729 \equiv 29$. The last two digits are 29. </details> 6. Solve $x \equiv 3 \pmod 4$, $x \equiv 4 \pmod 9$. <details><summary>Solution</summary> $N = 36$. $N1 = 9 \equiv 1 \pmod 4$, so $M1 = 1$; $N2 = 4$ and $4 \cdot 7 = 28 \equiv 1 \pmod 9$, so $M2 = 7$. Then $x = 3 \cdot 9 \cdot 1 + 4 \cdot 4 \cdot 7 = 27 + 112 = 139 \equiv 31 \pmod{36}$. Check: $31 = 7 \cdot 4 + 3$ and $31 = 3 \cdot 9 + 4$. </details> 7. With $p = 5$, $q = 11$ and $e = 3$, find $n$, $\varphi(n)$ and $d$; encrypt $m = 7$ and decrypt the result. <details><summary>Solution</summary> $n = 55$, $\varphi(n) = 4 \cdot 10 = 40$, $d = 27$ because $3 \cdot 27 = 81 = 2 \cdot 40 + 1$. Encrypt: $7^3 = 343 = 6 \cdot 55 + 13$, so $c = 13$. Decrypt: $13^2 = 169 \equiv 4$, $13^4 \equiv 16$, $13^8 \equiv 256 \equiv 36$, $13^{16} \equiv 36^2 = 1296 \equiv 31$. With $27 = 16 + 8 + 2 + 1$: $31 \cdot 36 = 1116 \equiv 16$, $16 \cdot 4 = 64 \equiv 9$, $9 \cdot 13 = 117 \equiv 7$. The message 7 comes back. </details> Cheat-sheet | Idea | Statement or method ||---|---|| Equivalence relation | reflexive, symmetric, transitive; classes partition the set || Division algorithm | $a = qb + r$, $0 \leq r < b$, unique || Euclidean algorithm | $\gcd(a, b) = \gcd(b, a \bmod b)$; last non-zero remainder || Bézout | $ax + by = \gcd(a, b)$; gcd is the least positive such value || Extended Euclid | new row = row two above minus $q$ times row above || Euclid's lemma | $p \mid bc \Rightarrow p \mid b$ or $p \mid c$ || FTA | unique factorisation into primes, up to order || $\mathbb{Z}/n\mathbb{Z}$ | $n$ classes; $+$ and $\cdot$ well defined || Unit test | $[a]$ invertible iff $\gcd(a, n) = 1$; inverse from Bézout || $ax \equiv b$ | solvable iff $\gcd(a,n) \mid b$; then $\gcd(a,n)$ solutions || Euler phi | $\varphi(n) = n \prod (1 - 1/p)$ over primes $p \mid n$ || Fermat | $a^{p-1} \equiv 1 \pmod p$ if $p \nmid a$ || Euler | $a^{\varphi(n)} \equiv 1 \pmod n$ if $\gcd(a, n) = 1$ || CRT | pairwise coprime moduli: unique solution mod $N = \prod ni$ || RSA | $n = pq$, $ed \equiv 1 \pmod{\varphi(n)}$, $c = m^e$, $m = c^d$ mod $n$ | What's next Post 01 takes the pattern seen here (a set, one operation, an identity, inverses) and turns it into the definition of a group. $\mathbb{Z}$ under addition, $\mathbb{Z}/n\mathbb{Z}$ under addition and $(\mathbb{Z}/n\mathbb{Z})^\times$ under multiplication become the first examples, joined by permutations, symmetries of polygons, invertible matrices and the quaternions. The division algorithm reappears in the proof that every subgroup of a cyclic group is cyclic, and $\gcd$ returns in the formula $n / \gcd(k, n)$ for the order of $k$ in $\mathbb{Z}/n\mathbb{Z}$. References - David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd edition, Wiley, 2004 — Chapter 0 (preliminaries: relations, integers, $\mathbb{Z}/n\mathbb{Z}$).- Joseph A. Gallian, Contemporary Abstract Algebra, 10th edition, CRC Press, 2021 — Chapter 0 (preliminaries, including the RSA-style applications).- Michael Artin, Algebra, 2nd edition, Pearson, 2011.- John B. Fraleigh, A First Course in Abstract Algebra, 7th edition, Addison-Wesley, 2003 — Section 0 (sets and relations).- Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991 — divisibility, congruences, the CRT.- Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), judsonbooks.org — chapters on the integers and on RSA.- MIT OpenCourseWare, 18.701 Algebra I (Fall 2010) — lecture notes and problem sets following Artin.- R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), 1978, pp. 120–126. > Note: this post is in progress. Planned additions: a proof that well-ordering and induction are equivalent, the CRT proof of multiplicativity of $\varphi$ written out in full, Wilson's theorem, and a short section on fast modular exponentiation cost (number of multiplications versus bit length).

Schema design is the decision with the longest half-life in any system. Indexes can be added, queries can be rewritten, hardware can be replaced — but a wrong key choice or a wrong normalization decision propagates into every query, every migration, and every downstream consumer for years. This post covers the formal part (normal forms, keys, constraints), the pragmatic part (when denormalization is correct, how to model hierarchies and temporal data), the PostgreSQL-specific part (JSONB and when it is the right answer), and the operational part (how to change a schema without locking production out of its own database). > Series map: 00 Foundations & Setup → 01 SQL Fundamentals & Data Types → 02 Joins, Aggregation & Window Functions → 03 Indexes & the Query Planner → 04 Query Optimization & Statistics → 05 Transactions, MVCC, Isolation & Locking → 06 Schema Design, Normalization & JSONB (this post) → 07 Operations, Backup, Replication & Security. Learning Outcome - Decompose a table through 1NF, 2NF, 3NF and BCNF, and state what each step eliminates.- Make an informed, reversible decision to denormalize, and name the cost you accepted.- Choose between natural keys, identity, UUIDv4 and UUIDv7 with index locality as the deciding factor.- Model one-to-many, many-to-many, inheritance, and hierarchies with the standard patterns and their trade-offs.- Represent temporal data with range types and forbid overlaps with an constraint.- Apply a clear rule for when a value belongs in JSONB and when it belongs in a real column, and index JSONB correctly.- Run schema migrations with expand/contract so no deployment needs a maintenance window. Chapter 1 — Normalization, worked Terminology - Functional dependency — means every value of determines exactly one value of .- Candidate key — a minimal set of columns that functionally determines every other column.- Primary key — the candidate key you chose to designate.- Partial dependency — a non-key column depending on only part of a composite key.- Transitive dependency — a non-key column depending on another non-key column.- Update anomaly — one logical fact stored in many rows, so changing it requires changing many rows and can leave them inconsistent. Start with the classic denormalized order sheet, one row per line item: 1NF — atomic values, no repeating groups and hold lists. Split them into rows; every cell now holds a single value. 1NF eliminates: parsing strings in clauses, and the impossibility of indexing or constraining an individual product. 2NF — no partial dependencies on a composite key The key is . But , , , , depend on alone. Split. 2NF eliminates: repeating the customer's email once per line item. 3NF — no transitive dependencies In , : those depend on the customer, not on the order. In , . Both are non-key columns determining other non-key columns. 3NF eliminates: the update anomaly where changing a supplier's phone number requires touching every order line they ever appeared on. Note stays on even though products have prices. That is not a normalization failure — the price at the time of sale is a genuinely different fact from the current catalogue price. Ask "does this value depend on the key, or on the moment?" before deleting a column that looks redundant. BCNF — every determinant is a candidate key 3NF still permits an anomaly when a table has overlapping candidate keys. Classic example: a course scheduling table where each course is taught by one instructor, and each instructor teaches one course. BCNF decomposition: In practice 3NF is the working target and BCNF violations are rare; they show up mostly where two natural keys overlap. Chapter 2 — The honest case for denormalization Normalization optimises for write correctness. It costs joins on read. Denormalize when you can state, in one sentence, which read you are buying and which write cost you are paying. Defensible denormalizations: | Pattern | Buys | Costs | Keep correct with ||---------|------|-------|-------------------|| Cached counter () | Removing a from every page render | Drift if the write path is missed | Trigger, or a scheduled reconciliation job || Copied immutable value () | Historical accuracy, not just speed | Nothing — this is not really denormalization | Nothing needed || Denormalized read table / summary table | A dashboard query that would otherwise join six tables | Staleness, extra storage, refresh cost | Materialized view or incremental refresh (post 04) || Duplicated on child tables | Row-level security and partition pruning without joins | An extra column to keep consistent | Foreign key on the composite | Indefensible ones: duplicating a mutable attribute with no trigger and no reconciliation, or "we might need to join later so let's flatten now". The test is whether you can describe how the copy stays correct. If you cannot, you have not denormalized — you have introduced a bug with a schedule. > Watch out: this trigger serialises all comment inserts for a single hot post onto one row lock. For a viral post that is a contention bottleneck. The alternative is an append-only delta table summed periodically — a trade of freshness for throughput. Chapter 3 — Keys: natural, surrogate, and index locality Terminology - Natural key — a key drawn from the data itself: ISBN, ISO country code, email address.- Surrogate key — a meaningless generated identifier: a sequence or a UUID.- Index locality — how close together in the btree consecutive inserts land. High locality means new entries pack into the same few rightmost pages. Natural keys are excellent when the value is genuinely immutable, short, and externally defined — ISO country codes, currency codes, ISBNs. They are dangerous when the "obviously stable" value turns out to be mutable: email addresses change, national ID formats get reissued, SKUs get renumbered in an acquisition. A natural key that changes forces a cascading update across every referencing table. Default to a surrogate primary key and a constraint on the natural key. You get stable references and enforced uniqueness. bigint identity vs UUIDv4 vs UUIDv7 | | identity | UUIDv4 | UUIDv7 ||---|---|---|---|| Size | 8 bytes | 16 bytes | 16 bytes || Insert locality in a btree | Perfect — always the rightmost page | Terrible — every insert lands on a random page | Good — time-prefixed, so near-sequential || Generatable client-side | No (needs a round trip or a sequence cache) | Yes | Yes || Leaks information | Yes — row counts and creation order are guessable | No | Creation timestamp only || Merging data from multiple sources | Collides | Safe | Safe | Index locality is the real issue, not the extra 8 bytes. With random UUIDv4 primary keys, every insert dirties a different btree leaf page. Once the index exceeds the shared buffer cache, each insert becomes a random read plus a random write, write amplification rises through full-page writes in the WAL, and the index fragments. This is the reason UUIDv4 primary keys develop a reputation for "getting slow at scale" — and the reason UUIDv7, which puts a millisecond timestamp in the high bits, fixes most of it while keeping client-side generation. Practical guidance: - Single database, ids never leave the system → .- Ids exposed in URLs, generated on the client, or merged across services → UUIDv7.- UUIDv4 → only when unpredictability of ordering is itself a requirement.- Never store a UUID as . The type is 16 bytes; the text form is 36 plus overhead and compares slower. Chapter 4 — Modelling patterns One-to-many A foreign key on the many side. Decide the delete behaviour explicitly — the default is a good default precisely because it forces the conversation. > Common pitfall: PostgreSQL indexes the referenced side (it must be unique) but never the referencing side. A missing index on the child's foreign key column makes every parent delete or update do a sequential scan of the child table, and makes the child hold locks longer. Many-to-many with a composite primary key The composite primary key does double duty: it enforces "a tag can only be applied once" and serves as the access path from post to tags. The second index serves tag to posts. Add a surrogate key to a join table only when something else must reference the relationship itself. Inheritance: single table vs class table For a hierarchy of related entities — say with and subtypes: | Approach | Shape | Good | Bad ||----------|-------|------|-----|| Single table | One table, a discriminator, all subtype columns nullable | One query returns everything; no joins | Cannot enforce per subtype without gymnastics; wide sparse rows || Class table | + + , each subtype table referencing the parent | Proper constraints per subtype; narrow tables | Every read joins; enforcing "exactly one subtype" needs work || Concrete table | and fully independent, no parent | Simplest per-type queries | No way to reference "a vehicle" generically; duplicated columns | Single table with constraints is the usual pragmatic answer for two or three subtypes with mostly shared columns: PostgreSQL's own table inheritance exists but is largely a legacy feature — it does not propagate unique or foreign key constraints to children. Use the patterns above instead. Hierarchies: adjacency list, closure table, ltree | Pattern | Storage | Read a subtree | Move a subtree | Notes ||---------|---------|----------------|----------------|-------|| Adjacency list () | 1 column | Recursive CTE | Update one row | Simple, correct, the default choice || Closure table | One row per ancestor/descendant pair | Single indexed join | Delete + reinsert the subtree's pairs | Fast reads, expensive writes, exact || | One path column | with a GiST index | Rewrite paths of all descendants | Elegant for shallow, rarely-moved trees | Start with the adjacency list. Move to a closure table or only when subtree reads are measurably the bottleneck. Soft deletes and what they cost The costs are real and cumulative: - Every query must remember the filter. One forgotten is a data leak.- Unique constraints stop working. now blocks re-registering an address whose owner "deleted" their account.- Foreign keys stop meaning what they say. A child can reference a soft-deleted parent.- The table never shrinks, and indexes carry dead weight forever. Mitigations, in order of preference: Option 3 keeps the live table clean, the constraints honest, and the history intact. Prefer it unless the row must remain referenceable. Chapter 5 — Temporal data and exclusion constraints Two different time concepts are often conflated: - Transaction time — when the database learned the fact (, ).- Valid time — when the fact is true in the real world (, ). A price that takes effect next Monday has a valid time in the future and a transaction time of now. Model them separately when both matter. Range types make valid-time intervals a first-class value and let the database forbid overlaps outright: An constraint is the generalisation of : instead of "no two rows are equal on these columns", it says "no two rows satisfy these operators pairwise". is exactly . Useful range operators: overlaps, contains, contained by, adjacent, union, intersection. Always use the half-open bound convention for time — it makes back-to-back intervals adjacent rather than overlapping, and it composes correctly. For a full history table, / plus an exclusion constraint on gives a non-overlapping, gap-tolerant slowly-changing-dimension table that the database itself keeps consistent. Chapter 6 — JSON vs JSONB Terminology - — stores the exact input text. Preserves whitespace, key order, and duplicate keys. Re-parsed on every access.- — stores a decomposed binary representation. Loses whitespace, key order, and duplicates (last wins). Parsed once on input; indexable.- — the SQL/JSON path language, available through and the / operators. Use . is appropriate only when you must reproduce the input byte-for-byte, which is an audit-log requirement, not a data-modelling one. Operators | Operator | Returns | Example ||----------|---------|---------|| | | || | | || | at a path | || | at a path | || | boolean, containment | || | boolean, key exists | || / | any / all keys exist | || | boolean, jsonpath matches | || | boolean, jsonpath predicate | || | set of | | Indexing JSONB Choosing: if you query a known key with equality or range, use an expression btree index. If you query arbitrary keys with containment, use GIN — when is all you need, default when you also need key-existence operators. > Common pitfall: compares text, so is true. Cast explicitly — — and make sure your index uses the identical expression, cast included, or it will not be used. The rule for JSONB vs a real column Make it a real column when any of these is true: - You filter, sort, join, or group by it regularly.- It must be , unique, checked, or a foreign key.- Every row has it.- Its type matters (dates, money, booleans). Make it JSONB when all of these are true: - The shape is genuinely open-ended or supplied by an external system you do not control.- It is read as a whole blob far more often than it is queried by an inner field.- The set of keys varies by row and enumerating them would produce a wide sparse table. Typical correct shapes: webhook payloads as received, third-party API responses, per-tenant custom fields, feature flags, sparse product attributes that differ by category, and event payloads whose schema evolves faster than your migration cadence. The failure mode is "the whole row is one JSONB column". You lose constraints, statistics quality, and type safety, and you gain nothing PostgreSQL was not already better at. If you find yourself writing on every query, that key wanted to be a column. The hybrid — a normalized core with a JSONB sidecar for genuinely variable attributes — is the design that ages well. For the document-database perspective on the same modelling questions (embed vs reference, and how those map back to relational tables), see the MongoDB course posts and . The mapping is close: MongoDB's "embed" corresponds to JSONB or a composite type here, and its "reference" corresponds to a foreign key — with the difference that PostgreSQL will actually enforce the reference. Chapter 7 — Enum vs lookup table, revisited | | Enum type | Lookup table | Text + CHECK ||---|---|---|---|| Storage | 4 bytes | Text or a small FK | Text || Add a value | — cannot run inside a transaction block in older versions, and cannot be used in the same transaction that adds it | — ordinary DML | + add — takes a lock and validates || Remove or rename a value | Rename since PostgreSQL 10; removal requires recreating the type | (FK protects in-use values) | Constraint swap || Attach metadata (label, ordering, flags) | No | Yes | No || Ordering | Declaration order, built in | column | Alphabetical only | Rule of thumb: an enum for a closed set that genuinely never changes (, weekday names) and where the 4-byte storage matters. A lookup table for anything a product manager might want to add to, or that needs a human-readable label, an ordering, or extra attributes — which in practice is most status columns. Chapter 8 — Migration discipline Every schema change happens against a running system. The rule is that a migration must never require the application and the database to change at the same instant. Expand / contract Split every breaking change into phases that are individually backwards-compatible: 1. Expand — add the new structure. Nullable column, new table, new index built . Old code keeps working.2. Backfill — populate the new structure in batches, committing as you go so no single transaction holds a snapshot for hours.3. Dual-write — deploy application code that writes both old and new. Reads still come from old.4. Migrate reads — deploy code that reads from new. Verify.5. Contract — stop writing the old structure, then drop it, once you are certain no rollback will need it. Renaming a column becomes: add → backfill → dual-write → switch reads → drop . Five deployments instead of one, and zero downtime at every step. Adding a NOT NULL column safely Adding a plain column with a default has been non-rewriting since PostgreSQL 11 — the default is recorded in the catalogue and materialised lazily. That makes this fast even on a huge table: A volatile default still rewrites the whole table: For that case, and for adding to an existing column, use the constraint-first route: The same → two-step works for foreign keys, and it is the only sane way to add one to a large table. Why a careless ALTER TABLE is dangerous Most forms take an lock — the mode that conflicts with everything, including plain . Two things make that far worse than it sounds: 1. The lock request must wait for existing conflicting locks to be released. One long-running or an open session (post 05) delays it indefinitely.2. While it waits, every subsequent query queues behind it. PostgreSQL's lock queue is ordered. A migration blocked for 30 seconds behind one slow report takes the whole table offline for those 30 seconds — for everyone. The discipline: Wrap DDL in a retry loop with , and check for long transactions before you start. Also remember: - and avoid the exclusive lock (at the cost of two table passes and the possibility of leaving an index behind if they fail — check and re-run).- cannot run inside a transaction block, which means most migration frameworks need an explicit "no transaction" flag for that step.- Changing a column's type generally rewrites the table. Widening to or to does not; narrowing does.- Adding a column is cheap; dropping one is also cheap (the column is only marked dropped), but the space is not reclaimed until the rows are rewritten. Practice Exercises Exercise 1 — Normalize the order sheet Take from Chapter 1 and produce the full 3NF schema yourself, with all foreign keys, constraints, and s. Then write the single query that reconstructs the original flat view. Exercise 2 — Find the BCNF violation Given a table where each instructor teaches exactly one course, list the functional dependencies, show why it is in 3NF but not BCNF, and give the decomposition. <details><summary>Solution</summary> </details> Exercise 3 — Measure UUID index locality Create two tables of ten million rows, one keyed by identity and one by . Compare insert throughput, final of the primary key index, and WAL generated ( or deltas). Report what you measured on your own hardware rather than assuming a figure. Exercise 4 — Forbid overlapping bookings Build the table with an constraint. Prove it holds under concurrency: two sessions each insert an overlapping booking for the same room inside open transactions, and show that the second blocks and then fails on commit. <details><summary>Solution</summary> </details> Exercise 5 — JSONB or column? Given an events table receiving webhooks from three providers, decide for each of these fields whether it should be a real column or stay inside : , , , , , . Justify each in one sentence, then write the DDL and the indexes. <details><summary>Solution</summary> </details> Exercise 6 — Zero-downtime rename Write the five-step expand/contract plan to rename to , including the exact SQL for each step and what the application deploys in between. Exercise 7 — Hierarchy showdown Load a 100 000-node category tree. Implement it three ways (adjacency list, closure table, ) and measure: full-subtree read, ancestor path lookup, and moving a mid-level subtree. Record which pattern wins each operation. Cheat-sheet | What | How ||------|-----|| Surrogate key, modern form | || Time-ordered UUID | (PostgreSQL 18+; earlier) || Natural key alongside a surrogate | surrogate PK + || Index a foreign key | — never automatic || Many-to-many | join table with + mirror index || Case-insensitive unique | column, or || Uniqueness among live rows only | || Subtree read | on , with a depth guard || Materialised path | + , query with || No overlapping intervals | (needs ) || Half-open interval | || JSON containment | || JSON scalar as text | (cast before comparing numerically) || JSON path query | || Smallest JSONB index | — supports only || Hot JSON key | expression btree: || Closed value set with metadata | lookup table + FK, not an enum || Add column with static default | — no rewrite since PG 11 || Add NOT NULL safely | → → || Add FK safely | → || Build an index online | (not inside a transaction block) || Protect production from DDL | before every | What's next Post 07 closes the base series with operations: what the WAL really is, backup strategies from to point-in-time recovery, streaming and logical replication with their failover hazards, why connection pooling is near-mandatory in front of PostgreSQL's process-per-connection model, roles and row-level security, and the handful of metrics worth waking someone up for. References - Data Definition- Constraints- JSON Types- JSON Functions and Operators- Range Types, including exclusion constraints--- UUID functions- RFC 9562 — UUID versions 6, 7, and 8- Date, C. J., Database Design and Relational Theory — normal forms treated rigorously.- MongoDB course, posts 07 () and 23 () — the document-model counterparts. > Note: this post is in progress. Planned additions: multi-tenancy schema strategies (shared table vs schema-per-tenant vs database-per-tenant), a composite-type and array-column section, and a measured comparison of GIN versus index size on a real payload set.

A transaction is the unit in which a database promises to be correct. PostgreSQL implements that promise with MVCC — multi-version concurrency control — where writers never block readers and readers never block writers, because every row can exist in several versions at once. That design explains almost everything else in this post: why an writes a new row instead of editing one, why exists at all, why an idle transaction can quietly break your cluster, and why hands you an error instead of a lock. This post covers the mechanics, the four isolation levels as PostgreSQL actually implements them, explicit locking, deadlocks, and the vacuum consequences. > Series map: 00 Foundations & Setup → 01 SQL Fundamentals & Data Types → 02 Joins, Aggregation & Window Functions → 03 Indexes & the Query Planner → 04 Query Optimization & Statistics → 05 Transactions, MVCC, Isolation & Locking (this post) → 06 Schema Design, Normalization & JSONB → 07 Operations, Backup, Replication & Security. Learning Outcome - State each ACID property precisely and name the PostgreSQL mechanism that provides it.- Explain MVCC through , , tuple versions and snapshots, and say why an creates a new tuple.- Choose an isolation level knowing exactly which anomalies it prevents in PostgreSQL.- Write a serialization-failure retry loop, because at the application is required to have one.- Use , , , and deliberately.- Reproduce a deadlock, read the server's deadlock report, and fix it with consistent lock ordering.- Explain how long transactions block vacuum, what transaction ID wraparound is, and why is dangerous.- Distinguish , , and freezing, and measure bloat. Chapter 1 — ACID, stated precisely Terminology - Atomicity — a transaction's effects are all applied or none are. PostgreSQL gets this from the commit record in the WAL: until the commit record is durable, the transaction's tuples are simply invisible.- Consistency — the database moves from one state satisfying all declared constraints to another. This is the application's and the schema's property; the database enforces it through constraints, not by magic.- Isolation — concurrent transactions produce a result consistent with some acceptable ordering. How strong that guarantee is depends on the isolation level (Chapter 3).- Durability — once returns, the effects survive a crash. Provided by write-ahead logging plus ; weakened deliberately by .- Anomaly — a concurrency outcome that a given isolation level permits: dirty read, non-repeatable read, phantom read, lost update, write skew. Every statement in PostgreSQL runs in a transaction. Outside an explicit , each statement is its own transaction that commits on success — "autocommit". There is no such thing as an unwrapped statement. Savepoints give partial rollback inside a transaction: > Watch out: after any error inside a transaction block, PostgreSQL puts the session into the aborted state — every subsequent statement fails with "current transaction is aborted" until you or . Drivers that wrap each statement in an implicit savepoint hide this and pay for it in overhead. Chapter 2 — MVCC mechanics Terminology - Tuple — one physical row version on a heap page. A logical row is a chain of tuples.- — the transaction ID that inserted this tuple version.- — the transaction ID that deleted or superseded it; while the version is live.- — the physical location of a tuple. Changes on every update.- Snapshot — the set of transactions considered committed at a point in time. Determines which tuple versions a statement can see.- Dead tuple — a version no snapshot in the system can still see. Reclaimable by vacuum. Every table has these hidden system columns. Select them directly: The old tuple at is still on the page with . It stays there, invisible, until vacuum reclaims it. Why UPDATE writes a new version Overwriting in place would destroy the version that concurrent readers are still entitled to see. Instead: 1. The new version is written (usually on the same page if there is room).2. The old version's is set to the updating transaction's ID.3. Readers with older snapshots continue to see the old version; readers with newer snapshots see the new one.4. Vacuum removes the old version once no snapshot needs it. Consequences you have to live with: - An costs roughly as much as a plus an .- Every index entry pointing at the row must be updated too — unless the update is a HOT (Heap-Only Tuple) update, which requires that no indexed column changed and that the new version fits on the same page. HOT updates are why below 100 can help write-heavy tables.- Tables grow under update load. Reclaiming the space is vacuum's job (Chapter 8). Snapshots and visibility A snapshot records: the next unassigned transaction ID, and the list of transactions in flight. A tuple is visible if its committed before the snapshot and its either is zero or belongs to a transaction that had not committed at snapshot time. - READ COMMITTED takes a new snapshot at the start of each statement. Two identical s in one transaction can return different data.- REPEATABLE READ and SERIALIZABLE take one snapshot at the first statement and keep it for the whole transaction. Chapter 3 — Isolation levels, as PostgreSQL implements them The SQL standard defines four levels by which anomalies they may permit. PostgreSQL's implementations are strictly stronger than the minimum in two important places. | Level | Dirty read | Non-repeatable read | Phantom read | Serialization anomaly (write skew) ||-------|-----------|---------------------|--------------|-------------------------------------|| READ UNCOMMITTED | not possible | possible | possible | possible || READ COMMITTED (default) | not possible | possible | possible | possible || REPEATABLE READ | not possible | not possible | not possible | possible || SERIALIZABLE | not possible | not possible | not possible | not possible | Two facts that trip people coming from other databases: 1. behaves exactly like . It is accepted for standards compliance but there is no dirty-read mode in PostgreSQL. MVCC never exposes uncommitted tuple versions, so dirty reads are structurally impossible.2. also prevents phantom reads, which the standard permits at that level. Because the whole transaction runs off one snapshot, a range query re-executed later returns exactly the same rows. PostgreSQL's is snapshot isolation. What still allows is write skew: two transactions each read a set of rows, each decides its write is safe based on what it read, and the combined result violates an invariant that neither transaction alone broke. At , a write-write conflict on the same row raises (SQLSTATE ). Different rows, as above, produce no error at all. SERIALIZABLE and SSI PostgreSQL 9.1 and later implement with Serializable Snapshot Isolation (SSI). It runs on top of snapshot isolation and tracks read/write dependencies between concurrent transactions with predicate locks (SIREAD locks). When it detects a dependency cycle that could not occur in any serial ordering, it aborts one of the transactions with SQLSTATE . Properties worth internalising: - It does not block. There is no extra waiting; the cost is aborts and the memory used for predicate locks.- The guarantee is real: if every transaction runs at and every serialization failure is retried, the outcome is equivalent to some serial execution. No hand-written locking required.- It is all-or-nothing per workload. A transaction at running alongside serializable ones is not protected and can break their guarantee.- Read-only transactions can be marked to reduce false positives: waits until a safe snapshot exists, then never aborts. > Watch out: the same rewritten SSI example above, run at , aborts one session with . That abort is the feature. The retry loop is mandatory Any code path that uses or must be prepared to run the whole transaction again. This is not optional error handling; it is part of the contract. Rules for the retry body: - Retry the whole transaction, not the failing statement. The snapshot is gone; re-reading is the point.- Never leave side effects outside the transaction inside the retried block — no emails, no queue publishes, no HTTP calls. Collect them and fire after commit.- Cap the attempts and back off with jitter, or a hot row turns into a retry storm.- Instrument it. A rising 40001 rate is a real signal about contention. MongoDB's driver-level helper does the equivalent retry automatically for — see the MongoDB course post for the contrast. PostgreSQL's drivers deliberately do not retry for you, because only the application knows whether the transaction body is safe to re-execute. Chapter 4 — Explicit row locking MVCC removes the need for read locks, but some patterns genuinely need to reserve a row. | Clause | Blocks | Use for ||--------|--------|---------|| | other , , , , and updates/deletes | Read-modify-write on a row you are about to change || | same, except it does not block | Updates that do not touch the primary/unique key — the lock takes internally || | writers, not other readers | "This row must not change until I commit" || | only | The lock a foreign key check takes on the parent row | The weaker modes exist so that inserting a child row (which must verify the parent exists) does not block an unrelated update of that parent's non-key columns. SKIP LOCKED — the queue pattern (PostgreSQL 9.5+) tells the executor to silently ignore rows another transaction has locked. That turns a table into a safe multi-consumer work queue with no external broker. Without every worker queues behind the first one on the same row and throughput collapses to one worker. NOWAIT raises (SQLSTATE ) immediately instead of waiting. Use it when a fast failure is better than an unbounded wait — an interactive "edit this record" screen, for example. Between them: = "fail if busy", = "give me whatever is free", default = "wait your turn". Table-level locks Every statement takes a table lock, usually implicitly. The modes, weakest to strongest: | Mode | Taken by | Conflicts with ||------|----------|----------------|| | | only || | | , || | , , , | and above || | (non-full), , , many variants | itself and everything above || | (non-concurrent) | and above, except itself || | , some | and above || | | everything except || | , , , , most , | everything, including plain | The rule that matters operationally: blocks readers, and a queued request blocks every later request behind it. A migration waiting behind one long will freeze the whole table for everyone who arrives afterwards. Always set a before DDL: Inspect current locks with: Chapter 5 — Deadlocks A deadlock is a cycle in the wait-for graph: A holds a lock B wants and B holds a lock A wants. PostgreSQL detects it after (default ) and aborts one transaction with SQLSTATE . Reproducing one Two sessions: Reading the log entry Everything you need is there: two PIDs, the statement each was executing, and the tuple involved. Set to also log waits that exceed without becoming deadlocks — those are the near-misses that precede real ones. The fix: consistent lock ordering Deadlocks come from two transactions acquiring the same set of locks in different orders. Impose a global order — sorting by primary key is the standard choice — and the cycle becomes impossible. Other reliable mitigations: keep transactions short, do not interleave user think-time inside a transaction, and touch tables in the same order everywhere in the codebase. And keep the retry loop from Chapter 3 — a deadlock abort is retryable by definition. Chapter 6 — Advisory locks Advisory locks are application-defined mutexes stored in PostgreSQL's lock manager. The database attaches no meaning to them; you choose the key. Typical uses: making a cron job single-instance across many app servers, serialising a migration, or guarding a per-tenant critical section keyed by tenant ID. > Trick: prefer over . Transaction-scoped locks cannot be leaked by a crashed code path — they disappear at the end of the transaction. > Common pitfall: advisory locks are per session, and PgBouncer in transaction pooling mode hands your session to someone else between statements. Session-scoped advisory locks are unusable there; transaction-scoped ones are fine. Post 07 covers this. Chapter 7 — Long transactions, wraparound, and "idle in transaction" Why long transactions are expensive Vacuum can only remove a dead tuple if no snapshot in the entire cluster could still see it. One transaction that started an hour ago and is still open pins the global horizon at its own snapshot. For that hour, no dead tuple newer than it can be removed anywhere in the database — even in tables that transaction has never touched. The result is bloat everywhere, slowly, invisibly, until someone notices the disk. is the worst state on that list: the client issued , did some work, and then went off to call an external API or wait on a user. It holds its snapshot, holds any locks it took, and consumes a connection slot, while doing nothing. Defences, all of which should be set in production: Set them per role rather than globally when a reporting user legitimately needs longer. Transaction ID wraparound Transaction IDs are 32-bit. PostgreSQL treats them as a circle: from any XID, roughly 2 billion are "in the past" and 2 billion are "in the future". A tuple whose fell more than 2 billion transactions behind would suddenly appear to be from the future — invisible. To prevent that, old tuples are frozen: marked as unconditionally visible, so their no longer matters. Freezing is vacuum's other job. | Parameter | Default | Meaning ||-----------|---------|---------|| | 50 million | Age at which a tuple becomes eligible for freezing during a normal vacuum || | 200 million | Age at which an anti-wraparound autovacuum is forced, even on a table nothing writes to || | 150 million | Age at which vacuum scans the whole table rather than only unfrozen pages | If freezing never catches up, PostgreSQL first warns loudly in the log, then refuses new write transactions to protect the data: Monitor the margin continuously: The usual causes of a wraparound scare are a long-lived open transaction, an abandoned replication slot, an orphaned prepared transaction (), or autovacuum being throttled too aggressively. Check all four. Chapter 8 — VACUUM, autovacuum, and bloat Terminology - Bloat — space occupied by dead tuples and free space that has not been returned to the OS.- — reclaims dead tuples for reuse within the table, updates the visibility map, freezes old tuples. Takes only ; runs concurrently with reads and writes.- — rewrites the table into a new file, returning space to the OS. Takes for the whole rewrite and needs disk for a second copy.- Autovacuum — the background daemon that runs and on a threshold.- Visibility map — per-page bits recording "all tuples on this page are visible to everyone", which is what makes index-only scans possible. Autovacuum thresholds A table is vacuumed when dead tuples exceed — by default 50 rows plus 20 % of the table. On a 100-million-row table that is 20 million dead tuples before anything happens, which is far too lenient. Tune the big tables individually: PostgreSQL 13 added (default 1000), which triggers vacuum on insert-only tables so their visibility map and freeze state keep up — a real fix for append-only time-series tables that previously never got vacuumed at all. Measuring dead tuples and bloat For a precise bloat figure install the extension: gives exact dead-tuple percentage at the cost of a full scan. Steady state is a dead-tuple percentage that oscillates and comes back down. A percentage that only climbs means autovacuum is not keeping up: either it is being blocked by long transactions, or its cost limits are throttling it, or the table's thresholds are too lenient. > Watch out: is not a routine maintenance command. It locks the table completely, and if the table is bloated because of a long-transaction problem, the bloat comes straight back. Fix the cause; use when you need an online rewrite. Chapter 9 — Contrast with MongoDB Worth holding both models in mind, especially if you work across the two. | Aspect | PostgreSQL | MongoDB ||--------|-----------|---------|| Default unit of atomicity | The statement (autocommit), extendable with | The single document || Multi-record transactions | Native since forever; the normal way to work | Available since 4.0 / 4.2, deliberately used sparingly || Isolation inside a transaction | Choice of four levels, default | Snapshot isolation || Concurrency control | MVCC with row versions on the heap | MVCC in WiredTiger with document-level locking || Retry on conflict | Application must retry / | Driver retries transient errors automatically || Time limit | None by default; bounded with | 60 s default || Reclaiming dead versions | / autovacuum, visible in operations | Handled inside the storage engine | The design advice rhymes: in MongoDB you ask "can single-document atomicity do this?" before reaching for a transaction; in PostgreSQL you ask "can one statement do this?" before reaching for and a read-modify-write round trip. needs no explicit lock and no retry at ; check the row count to detect the insufficient-funds case. See in the MongoDB course for that side in full. Practice Exercises Exercise 1 — Watch a row version move Create a small table, insert a row, and select . Update the row twice and observe the change each time. Run and check whether the space is reused. Exercise 2 — Non-repeatable read, then not In two sessions, demonstrate that a repeated inside a transaction can change when the other session commits — then show the same sequence at returning stable results. <details><summary>Solution</summary> </details> Exercise 3 — Produce a serialization failure Build the on-call write-skew scenario. Run it at and confirm the invariant breaks. Run it at and confirm one session receives SQLSTATE . <details><summary>Solution</summary> </details> Exercise 4 — Deadlock and fix Reproduce the two-session deadlock from Chapter 5. Copy the deadlock report out of the server log and identify both statements. Then rewrite both transactions to lock in primary-key order and confirm the deadlock no longer occurs. Exercise 5 — Job queue with SKIP LOCKED Build the table. Start three concurrent workers claiming batches of 10. Verify no job is processed twice and that throughput scales with worker count. Then remove and observe the collapse. <details><summary>Solution</summary> </details> Exercise 6 — Long transaction blocks vacuum Open a transaction in session A and leave it idle after one . In session B, generate heavy update churn on an unrelated table and run . Read the "dead row versions cannot be removed yet" line. Commit A and vacuum again. Exercise 7 — Autovacuum tuning Take a table with high update churn and record its curve over an hour. Lower for that table only, and show the curve flattening. Cheat-sheet | What | How ||------|-----|| Start a transaction | … / || Partial rollback | … || Set isolation for one transaction | || Set the session default | || See row versions | || Current transaction ID | (13+), earlier || Serialization failure | SQLSTATE — retry the whole transaction || Deadlock | SQLSTATE — retry, then fix lock ordering || Lock a row for update | || Weaker row lock | , , || Queue consumer | || Fail instead of waiting | (SQLSTATE ) || Blocking DDL lock | — always precede DDL with || Inspect locks | joined to || Log lock waits | , || Application mutex | || Find long transactions | ordered by || Kill idle transactions | || Dead tuples per table | || Wraparound margin | || Aggressive autovacuum for one table | || Online table rewrite | , not | What's next Post 06 covers schema design, normalization and JSONB — normal forms worked through one progressively decomposed example, natural versus surrogate keys and why UUIDv4 hurts index locality, the standard modelling patterns for hierarchies and many-to-many relationships, range types with exclusion constraints for temporal data, when a column should be JSONB and when it absolutely should not, and how to run migrations that do not take an lock at the worst possible moment. References - Concurrency Control- Transaction Isolation- Explicit Locking- / locking clauses- Routine Vacuuming, including wraparound- Advisory lock functions-- Ports & Grittner, Serializable Snapshot Isolation in PostgreSQL, VLDB 2012.- MongoDB course, post 09 () — the counterpart treatment of multi-document transactions. > Note: this post is in progress. Planned additions: a SSI predicate-lock memory-exhaustion walkthrough, two-phase commit () and when it is justified, and a measured comparison of HOT-update rates at different settings.

The final base post covers the territory that "barely existed" when the prior posts' patterns were stabilising and is now front-of-mind: AI-generated 3D assets (text-to-3D and image-to-3D in seconds), NavMesh + pathfinding for AI-driven characters, Gaussian Splatting for photoreal scanned environments, and the procedural generation techniques (noise, L-systems, wave-function collapse) that complement or replace authored assets. None of these are exclusive to Three.js, but they all show up in production Three.js pipelines today. > Series map: 00 Foundations → 01 Geometry & Materials → 02 Cameras & Controls → 03 Lighting & Shadows → 04 Textures & PBR → 05 Asset Pipeline → 06 Animation → 07 Instancing & Batching → 08 Low-End Perf → 09 Shaders → 10 Post-Processing → 11 Physics → 12 R3F → 13 AI 3D + NavMesh + Procedural (this post — final in the base series). Learning Outcome - Use AI tools (Meshy, Tripo, Luma Genie, TripoSR, Hunyuan3D, CSM) to generate 3D models from text or images.- Clean up + optimise AI-generated meshes for production.- Generate a NavMesh from your scene with recast-navigation-js.- Pathfind across a NavMesh with Detour.- Display Gaussian Splatting captures in Three.js.- Generate procedural terrain with Perlin / Simplex noise.- Recognise where each technique fits in a pipeline. Chapter 1 — Text-to-3D + image-to-3D (the 2026 landscape) In 2026, a usable 3D model from a text prompt or single reference image takes about a minute and costs a few cents. None of these tools fully replace a 3D artist for hero work, but they're production-ready for backgrounds, props, prototypes, and indie / mid-tier projects. | Tool | Inputs | Outputs | Notes ||------|--------|---------|-------|| Meshy | text, image | textured glTF / FBX / USDZ; auto-rig; 500+ animation presets | most-complete pipeline; web + API || Tripo | text, image | textured glTF | fast; web + API; cheaper than Meshy || Luma Genie | text | glTF | strong geometric reasoning; web || TripoSR | single image | mesh in < 0.5 s on an A100 | open-source (Stability AI + Tripo); self-hostable || Hunyuan3D (Tencent) | text, image | high-quality textured mesh | open-source, top-tier quality || CSM (Common Sense Machines) | concept art / character sheet | proportion-faithful character mesh | designer-friendly || Spline AI | text | scenes within Spline (Three.js compatible export) | designer tool with AI assist || Rodin | text | high quality | newer, gaining traction | Workflow for AI-generated mesh → Three.js 1. Generate at the tool's UI. Iterate on prompt + reference images until happy.2. Download glTF.3. Clean up in Blender — fix the inevitable issues:- Floating / disconnected geometry → merge by distance.- Hyper-dense topology → decimate.- Wrong scale / orientation → fix root transform.- Inverted normals → recalculate.- Texture seams or bake noise → repaint patches.4. Optimise with (Post 05).5. Drop into your Three.js scene with . > Trick: AI-generated meshes look right at "hero camera" angles and wrong from close-up. Always test from your actual camera. For backgrounds it doesn't matter; for player-inspected props, plan to clean up. Production readiness in 2026 - Prototype quality is trivial — minutes from prompt to scene.- Production quality still needs human review for: hero characters, branded assets, anything inspected closely, manufacturing geometry, anything with text on it (still flaky in 2026).- Round-trip test always — export from AI tool, import into your engine, render at production camera, before committing. Chapter 2 — API integration For automated pipelines (user-generated content sites, game asset farms, procedural batches): Tripo, Luma, Hunyuan have similar REST + polling APIs. TripoSR runs entirely on your own GPU — no external API. Self-hosting TripoSR Requires a CUDA GPU (A100 ideal, RTX 3060 / 4070 viable). 0.5-3 seconds per mesh. Self-host when you need privacy, batch volume, or zero per-call cost. Chapter 3 — NavMesh + pathfinding For AI-driven characters that need to walk around obstacles, NavMesh (Navigation Mesh) is the standard. A NavMesh is a polygon graph of the walkable surface; pathfinding queries return a sequence of polygons + a straight path inside them. The canonical library for JS is recast-navigation-js — a WASM port of the C++ Recast (NavMesh construction) + Detour (pathfinding) libraries used in Unreal, Unity, and most game engines. Install Generate a NavMesh from a Three.js scene Pathfind Visualise the path: Move a character along the path Each frame, advance toward the next waypoint at walking speed; pop the waypoint when reached. Crowds For many AI characters, Detour Crowd handles avoidance between them: For dynamic scenes (rebuild NavMesh as the world changes), use tiled NavMesh via — only rebuild affected tiles. Chapter 4 — Procedural generation When you can't or don't want to author every prop, generate procedurally. Perlin / Simplex noise (the workhorse) Layering noise at multiple frequencies + amplitudes (fractal Brownian motion) gives natural-looking terrain. L-systems for plants / fractals Useful for plants, branches, trees. Wave Function Collapse (WFC) Generate tile-based maps from a small example. Libraries: (npm). Use for dungeons, city blocks, decorative patterns. Voronoi / Delaunay Cell partitioning — useful for procedural ground textures, cracked surfaces, cell-shaded foliage clumps. Library: . Marching cubes Convert a 3D scalar field (e.g., from noise) into a triangle mesh — generates caves, blob shapes, organic terrain. Three.js has in addons. > Trick: "looks too perfect / too repetitive" is the procedural-generation tell. Layer multiple techniques (noise + WFC + hand-placed accents). Add small artist-authored variation on top to break uniformity. Chapter 5 — Gaussian Splatting (3DGS) Gaussian Splatting (2023) is a new way to represent and render 3D scenes — a cloud of millions of view-dependent ellipsoids ("splats") rather than a triangle mesh. Captured from photos with tools like Luma AI, Polycam, PostShot. Renders extremely fast even on mobile. Status in 2026: - Three.js doesn't yet ship a built-in 3DGS renderer.- Use or to render / files in a Three.js scene. Use cases: virtual scans of real places, e-commerce showroom captures, AR scene reconstruction. Limitations: editing is hard (no triangle mesh to nudge); animation harder still. Chapter 6 — Pipeline integration Putting it all together — a realistic mixed pipeline for a game / interactive experience: Three.js (or R3F) sits in the middle, integrating all of it through , custom loaders, NavMesh queries, and the patterns from posts 00-12. Chapter 7 — Ethical + legal notes AI-generated 3D models: - Licensing of training data is contested. Most commercial tools (Meshy, Tripo, Luma) claim model output is yours to use; check current ToS.- Open-source models (TripoSR, Hunyuan3D) have permissive licences for output but may have non-commercial training-data caveats.- Brand / IP prompts ("a Star Wars X-wing") will produce IP-infringing outputs; you carry the legal risk, not the tool.- Disclose AI-generated content where required by platform rules (App Store, Steam, etc.).- Workflow auditability — log prompts + tool + version per asset for future review. NavMesh + procedural generation aren't ethically loaded; standard library licensing applies (most are MIT / Apache-2.0). Gaussian Splat captures of real places — same as photography: respect private property, get model releases for people, follow GDPR / local rules for identifiable people. Practice Exercises Exercise 1 — Generate + import Generate a model on Meshy (free tier) of "a stylised mushroom". Download glTF. Load into a Three.js scene. Add Environment + OrbitControls. Note quality and what you'd need to fix. Exercise 2 — Optimise the AI mesh Run then . Compare file size + draw calls + visual quality. Exercise 3 — NavMesh on a room Build a simple "room" scene: floor + several walls + a couple of obstacles. Generate a NavMesh via . Visualise it (the NavMesh has a method or similar). Exercise 4 — Click-to-walk Click anywhere on the floor → pathfind from character position to click target → move character along the path. Exercise 5 — Procedural terrain Generate a 100×100 terrain with layered Simplex noise. Add an LOD swap for distant chunks. Tile with a grass texture (Post 04). Exercise 6 — Gaussian Splat viewer Find a free file on luma.com/featured or download one. Display it in a Three.js scene via . Add OrbitControls. Exercise 7 — Full mini-pipeline Build a 30-second prototype scene: AI-generated mushroom forest (5 species via Meshy/Tripo), procedural noise terrain, recast-navigation crowd of 20 agents wandering between waypoints, R3F + Drei + Rapier for the engine, deployed on Vercel. Note the friction at each step. Cheat-sheet | What | How ||------|-----|| Text-to-3D | Meshy, Tripo, Luma Genie, CSM, Spline AI, Rodin || Image-to-3D | TripoSR (open-source), Meshy, Tripo || Open-source self-host | TripoSR, Hunyuan3D || Round-trip test | always render in your engine at your camera before committing || Cleanup after AI | Blender: merge by distance, decimate, normals, scale || NavMesh library | + || Build NavMesh | || Pathfind | || Many agents + avoidance | from recast-navigation || Dynamic world | tiled NavMesh, rebuild affected tiles || Noise terrain | layered as fBm || L-system / WFC | for plants / tiled maps || Marching cubes | scalar field → mesh (caves, blobs) || Gaussian Splat viewer | || Legal | check tool ToS; disclose AI; respect IP | Course base complete This concludes the 14-post base series. You've covered: - Foundations (00).- Geometry + materials (01).- Cameras + controls (02).- Lighting + shadows (03).- Textures + PBR (04).- Asset pipeline + glTF (05).- Animation (06).- Instancing + batching (07).- Low-end performance (08).- Custom shaders (09).- Post-processing + colour (10).- Physics + interactivity (11).- React Three Fiber + Drei (12).- AI + NavMesh + procedural (13). That covers 95 % of what working Three.js engineers touch week-to-week. Planned future extensions | # | Topic | Why follow ||---|-------|-----------|| 14 | WebXR — VR + AR + handheld | needed for immersive 3D || 15 | WebGPU compute deep dive | particle sims, GPU pathfinding, ML || 16 | Networked 3D — Yjs / Colyseus / Hathora | collaborative scenes || 17 | Cloth, soft body, fluid | advanced physics || 18 | Audio-reactive scenes | Web Audio API + Three.js || 19 | Theatre.js / cinematic cameras | timeline-based animation || 20 | Three.js + Spline + Houdini integrations | designer pipelines || 21 | Production-grade asset CI/CD | gltf-transform in pipelines || 22 | Benchmarks + tuning case studies | real-world performance investigations | References - Meshy — text-to-3D + auto-rig.- Tripo — fast text-to-3D.- Luma Genie — text-to-3D.- TripoSR (open-source)- Hunyuan3D (open-source)- CSM — concept-faithful character mesh.- recast-navigation-js- @recast-navigation/three- @mkkellogg/gaussian-splats-3d- simplex-noise- Best AI 3D model generators 2026 (comparison)- Best AI Tools for 3D Game Assets 2026 (Meshy) > Note: this post — and the base course — is in progress. Planned additions: full AI pipeline walkthrough; tiled NavMesh + dynamic obstacles; Gaussian Splat editing tooling; Houdini PDG → Three.js batch generation.