Subgroups, Cosets, and Lagrange's Theorem

A subgroup is a subset that is itself a group under the same operation. The rotations of a square, $\{e, r, r^2, r^3\}$, form a subgroup of $D_4$: compose two rotations and you get a rotation, and each undoes. The reflections do not, since composing two reflections gives a rotation and leaves the set.

Checking all four axioms is unnecessary. Associativity is inherited, so for a non-empty finite subset only closure needs testing.

Definition: $H \leq G$ means $H$ is a subgroup of $G$. Every group has two trivial subgroups, $\{e\}$ and $G$ itself. The interesting question is always what sits between them, because that is where a group's internal structure lives.

Even integers are a subgroup of the integers under addition. Multiples of 3 are another. Odd integers are not, for the same reason the reflections were not.

Take a subgroup $H$ and an element $g$. The left coset is the whole subgroup shifted by $g$:

$gH = \{gh : h \in H\}$

In $D_4$, let $H$ be the four rotations. Then $eH = H$, and $sH = \{s, sr, sr^2, sr^3\}$, which is the four reflections. Two cosets, four elements each, eight elements total, no overlap.

That is not luck. Two facts do all the work:

• Every coset has exactly $|H|$ elements. The map $h \mapsto gh$ is a bijection, since multiplying by $g^{-1}$ undoes it.
• Two cosets are identical or disjoint. If they share one element, multiplying through by inverses shows every element is shared.

So the cosets of $H$ tile $G$ completely, in equal-sized pieces, with none left over.

Put the two facts together and the theorem is immediate.

Theorem (Lagrange). If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$.

Proof. The cosets of $H$ partition $G$, and each has exactly $|H|$ elements. If there are $k$ of them, then $|G| = k \cdot |H|$. $\blacksquare$

The number $k$ is called the index of $H$ in $G$, written $[G : H]$.

$|G| = [G : H] \cdot |H|$

Key idea: This is counting one set two ways, the same technique that gave the handshake lemma for graphs. No structure was needed beyond "equal-sized pieces that do not overlap", which is why the conclusion is so strong for so little input.

A group of order 12 can only have subgroups of order 1, 2, 3, 4, 6 or 12. Nothing else is possible, in any group of that size, ever.

The pattern generalises. The order of any element divides $|G|$, because the element generates a cyclic subgroup whose size is that order.

$g^{|G|} = e \quad \text{for every } g \in G$

Raise any element to the size of the group and you land on the identity. Do it in a group of card shuffles and you have proved that repeating any shuffle enough times restores the deck.

Take $p$ prime and let $G$ be the non-zero residues mod $p$ under multiplication. Every element has an inverse, because $\gcd(a, p) = 1$ for all $a$ from 1 to $p-1$, so $G$ is a group of order $p - 1$.

Now apply $g^{|G|} = e$ directly:

$a^{p-1} \equiv 1 \pmod{p}$

That is Fermat's little theorem, the result that collapsed a million-digit exponent to four multiplications in the discrete mathematics course. Here it arrives as a special case of a statement about abstract groups, proved by counting cosets, with no number theory involved at all.

Key idea: This is what the bare axioms buy. Fermat proved his theorem in 1640 and Lagrange's coset argument came later and independently, yet the general result contains the specific one entirely. Prove something once about groups and it is true everywhere a group turns up, including places nobody was looking.

To compare two groups you need maps that respect the operation. A homomorphism $\varphi : G \to H$ satisfies

$\varphi(ab) = \varphi(a)\,\varphi(b)$

Combine first and then map, or map first and then combine: same answer.

The exponential row is the reason logarithms were useful for three centuries: it converts a hard operation into an easy one by moving between two groups that have the same structure.

Every homomorphism comes with two subgroups that describe exactly how much information it loses.

Definition: The kernel is everything mapped to the identity, $\ker \varphi = \{g : \varphi(g) = e\}$. The image is everything reached in $H$.

The kernel measures collapse. If it contains only $e$, nothing is conflated and the map is injective. The determinant's kernel is the matrices of determinant 1, an enormous set, which is precisely how much the determinant forgets about a matrix.

The first isomorphism theorem ties them together: $G$ modulo the kernel is isomorphic to the image. Informally, quotient out exactly what the map throws away and what remains is a faithful copy of what it produced.

In practice: This is the same idea as a hash's collision structure or a lossy encoding's equivalence classes. "What does this transformation destroy?" has a precise answer, and it is a subgroup.

An isomorphism is a homomorphism that is also a bijection, and two groups related by one are the same group wearing different labels. Order alone does not decide it.

There are exactly two groups of order 4, and they are genuinely different:

No relabelling turns one into the other, because $\mathbb{Z}_4$ contains an element of order 4 and $V$ does not, and element orders survive any isomorphism.

Gotcha: "Same number of elements" tells you nothing about structure. Finding an invariant that differs, element orders, abelian or not, number of subgroups, is how you prove two groups are distinct, and it is far easier than exhaustively checking that no bijection works.

Lagrange constrains structure but does not determine it, and the count of distinct groups of a given order is wildly irregular.

Order 15 has exactly one group; order 16, one larger, has fourteen. Primes always give exactly one, by the argument two steps back. Powers of 2 explode: there are 49,487,365,422 groups of order 1024.

That explosion is why classification became the central problem of the field. The building blocks are the finite simple groups, those with no non-trivial normal subgroup, and their complete list was assembled over decades: several infinite families, plus exactly 26 sporadic groups belonging to no family at all, the largest of which has about $8 \times 10^{53}$ elements.

Small groups are concrete enough to inspect directly, and building the multiplication table is usually the fastest way to answer a structural question.

from itertools import product

# Z_4 under addition mod 4, and the Klein four-group as pairs under XOR
Z4 = list(range(4))
add4 = lambda a, b: (a + b) % 4

V = list(product([0, 1], repeat=2))
xor = lambda a, b: (a[0] ^ b[0], a[1] ^ b[1])

def element_orders(elems, op, identity):
    orders = []
    for g in elems:
        x, k = g, 1
        while x != identity:
            x, k = op(x, g), k + 1
        orders.append(k)
    return sorted(orders)

element_orders(Z4, add4, 0)          # [1, 2, 4, 4]
element_orders(V, xor, (0, 0))       # [1, 2, 2, 2]

The two multisets differ, so no isomorphism exists. That is a complete proof, and it took nine lines. For anything larger, computational algebra systems such as GAP hold the classified groups and answer these questions directly.