Subgroups & Lagrange's Theorem

Most groups have smaller groups living inside them: the rotations inside a dihedral group, the even numbers inside $\mathbb{Z}$. This page is about those groups-within-groups. We'll learn how to check that a subset is one, how to build the smallest one containing whatever elements you like, and how to draw all of them at once. Then we'll count them, and the counting gives one of the most useful theorems in the course: the size of a subgroup always divides the size of the group. Everything here is written multiplicatively.

Subgroups

Suppose $G$ is a group. Here's the definition.

Only two conditions, and yet they're enough. These conditions guarantee that $H$ is a group with respect to the binary operation on $G$. Here's why each group axiom holds:

• Condition (i) guarantees that the restriction of the binary operation to $H$ is well defined: multiplying two elements of $H$ never lands you outside $H$.
• Associativity in $(H, \cdot)$ follows from associativity in $(G, \cdot)$. The elements of $H$ are elements of $G$, so they already associate.
• Existence of identity (and in fact $e_H = e_G$): $H$ is non-empty $\Rightarrow \exists g \in H$. Condition (ii) $\Rightarrow g^{-1} \in H$. Condition (i) $\Rightarrow gg^{-1} = e_G \in H$. And $\forall h \in H$, $e_G h = h e_G = h$.
• Existence of inverses follows from condition (ii).

Notice how "non-empty" quietly did real work in the identity bullet: we needed some element $g$ to start from. Now for examples. The first one is written additively, so "$gh$" becomes $g + h$ and "$g^{-1}$" becomes $-g$.

Nothing about the number $2$ mattered there.

Next, some finite examples, using groups from the Foundations pages.

Those examples were easy to check because the sets were small. Most subsets aren't subgroups, though, and one bad product is all it takes to rule one out.

Some Facts and Terminology

Let $G$ be a group. Every group has at least two subgroups without trying: $G \le G$ and $\{e\} \le G$.

The other one, $G$ itself, is a bit too big to be interesting, so the subgroups that aren't the whole group get their own name.

Checking two conditions every time gets old. The first shortcut packs them into one.

Proof.

• ($\Rightarrow$) If $H \le G$ and $g, h \in H$, then $h^{-1} \in H$ by (ii), so $gh^{-1} \in H$ by (i).
• ($\Leftarrow$) $H \neq \emptyset \Rightarrow \exists g \in H$. Then:
  • $e = gg^{-1} \in H$.
  • $\forall h \in H$, $h^{-1} = eh^{-1} \in H$. (closed under inverses)
  • $\forall g, h \in H$, $h^{-1} \in H$, so $g(h^{-1})^{-1} = gh \in H$. (closed under multiplication) $\blacksquare$

For finite sets, there's an even lazier test: closure under inverses comes for free.

Proof. ($\Rightarrow$) is condition (i). For ($\Leftarrow$), we only need to show that $H$ is closed under taking inverses. Let $g \in H$. By closure, $\{g, g^2, g^3, \dots\} \subseteq H$. Since $|H| \lt \infty$, these powers can't all be different, so $\exists i, j \in \mathbb{N}$ with $i \lt j$ and $g^i = g^j$. Multiplying both sides by $g^{-i}$ (in $G$) gives $g^{j-i} = e$.

• If $j - i = 1$, then $g = e$, so $g^{-1} = e = g \in H$.
• If $j - i \ge 2$, then $g \cdot g^{j-i-1} = g^{j-i} = e$, so $g^{-1} = g^{j-i-1}$. Since $j - i - 1 \ge 1$, this is a positive power of $g$, so $g^{-1} \in H$. $\blacksquare$

Try the finite criterion yourself. Pick elements to put in $H$, and the widget builds $H$'s own multiplication table. As soon as every product stays inside, $H$ is a subgroup, and you'll see the inverses were there all along.

One more fact, and it's the one that makes the next section possible: subgroups can be intersected, and the result is still a subgroup. This works for any non-empty collection, even infinitely many subgroups at once.

Proof. Write $H = \bigcap_{i \in I} H_i$. Then:

• $\forall i \in I$, $e \in H_i \Rightarrow e \in H \Rightarrow H \neq \emptyset$.
• If $g, h \in H$ then, since $g, h \in H_i$, $\forall i \in I$, we have that $gh^{-1} \in H_i$, $\forall i \in I$ (subgroup criterion). Therefore $gh^{-1} \in H$.

It follows from the subgroup criterion that $H \le G$. $\blacksquare$

Unions, on the other hand, are a different story.

The Subgroup Generated by a Subset

Suppose you have a handful of elements $S \subseteq G$ and you want a subgroup containing them. $G$ itself always works, but that's lazy. What's the smallest subgroup containing $S$? The intersection theorem hands us the answer.

A few things to notice about that definition:

• Since $S \subseteq G$ there is always at least one subgroup of $G$ containing $S$ (namely, $G$), so the collection being intersected is non-empty, and $\langle S \rangle \le G$ by the intersection theorem.
• $\langle S \rangle$ is the smallest subgroup of $G$ containing $S$, in the sense that, if $H \le G$ and $S \subseteq H$, then $\langle S \rangle \le H$. ($H$ is one of the subgroups being intersected.)
• If $S = \{g_1, \dots, g_n\}$ then we also write $\langle S \rangle = \langle g_1, \dots, g_n \rangle$.

Groups that can be built from finitely many elements get a name.

Let's revisit the earlier examples. Each subgroup we found turns out to be generated by just one or two elements.

That note about infinite groups deserves a counterexample in the other direction too: an infinite group that is not finitely generated. The rationals are the classic one.

Show proof

Proof. Suppose $S = \{r_1, r_2, \dots, r_n\} \subseteq \mathbb{Q}$, and write $r_i = \frac{p_i}{q_i}$ with $p_i \in \mathbb{Z}$, $q_i \in \mathbb{N}$. Let

$$H = \left\{a_1 r_1 + a_2 r_2 + \dots + a_n r_n : a_1, \dots, a_n \in \mathbb{Z}\right\}.$$

Then:

• $H \le \mathbb{Q}$ (subgroup criterion: $0 \in H$, and the difference of two such sums is another one).
• $S \subseteq H \Rightarrow \langle S \rangle \subseteq H$ (definition of $\langle S \rangle$).
• $H \subseteq \langle S \rangle$ (subgroup criterion applied to $\langle S \rangle$: it contains each $r_i$ and is closed under sums and negatives, so it contains every $a_1 r_1 + \dots + a_n r_n$).

Therefore $\langle S \rangle = H$.

Now let $q = \text{lcm}(q_1, \dots, q_n)$. Then $\forall x \in H$, since $x = \sum_{i=1}^n a_i \left(\frac{p_i}{q_i}\right)$ for some $a_1, \dots, a_n \in \mathbb{Z}$, we have that

$$qx = \sum_{i=1}^n a_i p_i \left(\frac{q}{q_i}\right) \in \mathbb{Z}.$$

But then, since $q \left(\frac{1}{2q}\right) = \frac{1}{2} \notin \mathbb{Z}$, we find that $\frac{1}{2q} \notin H \Rightarrow H \neq \mathbb{Q}$. No finite set generates $\mathbb{Q}$. $\blacksquare$

The definition of $\langle S \rangle$ as an intersection is clean, but it doesn't tell you what's actually in it. This theorem does: $\langle S \rangle$ is everything you can spell using elements of $S$ and their inverses.

Proof. Let $H = \{g_1^{u_1} g_2^{u_2} \cdots g_n^{u_n} : n \in \mathbb{N},\ g_1, \dots, g_n \in S,\ u_1, \dots, u_n \in \{\pm 1\}\}$. Then:

• $H \le G$ (subgroup criterion). $S \neq \emptyset$, so $H \neq \emptyset$. If $x = g_1^{u_1} \cdots g_n^{u_n}$ and $y = h_1^{v_1} \cdots h_m^{v_m}$ are in $H$, then $xy^{-1} = g_1^{u_1} \cdots g_n^{u_n} h_m^{-v_m} \cdots h_1^{-v_1}$ is another product of the same kind, so $xy^{-1} \in H$.
• $S \subseteq H$ (take $n = 1$, $u_1 = 1$) $\Rightarrow \langle S \rangle \subseteq H$ (definition of $\langle S \rangle$).
• $H \subseteq \langle S \rangle$: $\langle S \rangle$ is a subgroup containing $S$, so it contains every $g^{-1}$ with $g \in S$ and every product of those (subgroup criterion applied to $\langle S \rangle$).

Therefore $\langle S \rangle = H$. $\blacksquare$

The "non-empty" is there because of item 0 in Example 6: with $S = \emptyset$ there are no products to write down, yet $\langle \emptyset \rangle = \{e\}$. When $G$ is Abelian, the order of the factors stops mattering, so we can gather all the copies of each generator together.

Watch the theorem in action. Round 1 is the elements of $S$ and their inverses. Each round after that multiplies everything so far by one more letter. When a round adds nothing new, you've found all of $\langle S \rangle$.

Cyclic Subgroups and Orders of Elements

The simplest generated subgroups use a single element: $\langle g \rangle$. How big is it? That depends on how long it takes the powers of $g$ to come back around to $e$.

To find an order, keep multiplying by $g$ until you hit $e$.

In $C_6$, the orders were $1, 6, 3, 2, 3, 6$, and the cyclic subgroups had sizes $|\langle x^3 \rangle| = 2$ and $|\langle x^2 \rangle| = 3$. That's not a coincidence.

Proof. To prove (i), consider the contrapositive. Suppose that $g^i = g^j$ for some $i, j \in \mathbb{Z}$ with $i \neq j$. W.L.O.G., suppose $i \lt j$. Then $g^{j-i} = e$ and $j - i \in \mathbb{N} \Rightarrow |g| \lt \infty$. This establishes (i).

To prove (ii), suppose $|g| = k$ and $g^i = g^j$ for some $i, j \in \mathbb{Z}$. Then $g^{j-i} = e$. By the Division Algorithm, $\exists q, r \in \mathbb{Z}$ with $0 \le r \lt k$ s.t. $j - i = qk + r$. Since

$$e = g^{j-i} = g^{qk+r} = (g^k)^q g^r = e^q g^r = g^r,$$

and since $k$ is the smallest element of $\mathbb{N}$ satisfying $g^k = e$, it follows that $r = 0$. Then $j - i = qk \Rightarrow i \equiv j \pmod k$. Conversely, $i \equiv j \pmod k \Rightarrow j - i = qk \Rightarrow g^{j-i} = (g^k)^q = e \Rightarrow g^j = g^i$.

Finally, every element of $\langle g \rangle$ is a power $g^n$. Dividing, $n = qk + r$ with $0 \le r \lt k$, and $g^n = (g^k)^q g^r = g^r$, so $\langle g \rangle \subseteq \{e, g, \dots, g^{k-1}\}$ (and the other inclusion is clear). These $k$ powers are all different, because no two of $0, 1, \dots, k-1$ are congruent mod $k$. Therefore $\langle g \rangle = \{e, g, g^2, \dots, g^{k-1}\}$ and $|\langle g \rangle| = k$. $\blacksquare$

Part (ii) says the exponents of $g$ wrap around with period $|g|$, in both directions. Lay the integers out in a line and you can see it: pick any exponent, and every exponent that gives the same element lights up, spaced exactly $|g|$ apart.

Lattice of Subgroups of a Group

Once you've found the subgroups of a group, it helps to see how they fit inside each other.

The whole group goes at the top, $\{e\}$ at the bottom, and a line joins a subgroup to the bigger subgroups directly above it.

The third example is the first non-Abelian one, and it comes with an argument that nothing has been missed.

The explorer below draws all three lattices, plus two bigger ones. Look at the scale on the left: every subgroup sits at a height that divides $|G|$. Keep that in mind for the next section.

Lagrange's Theorem

Every lattice so far had subgroups only at heights that divide $|G|$: orders $1, 2, 4$ in $V_4$, and $1, 2, 3, 6$ in $C_6$ and $D_6$. Here's why. The proof chops $G$ into pieces that all have the same size as $H$, and those pieces have a name.

Multiply on the other side and you get the mirror image.

Notice that $g = ge \in gH$, so every element lives in at least one left coset (its own). Now the theorem.

Proof.

Step 1: Define a relation $\sim$ on $G$ by the rule that, $\forall g, g' \in G$, $g \sim g'$ if and only if $\exists h \in H$ s.t. $g = g'h$. This relation is:

• Reflexive ✓: $e \in H$ and $\forall g \in G$, $g = ge \Rightarrow g \sim g$.
• Symmetric ✓: Suppose $g \sim g'$. Then $\exists h \in H$ s.t. $g = g'h$. But $h^{-1} \in H$ and $g' = gh^{-1} \Rightarrow g' \sim g$.
• Transitive ✓: Suppose $g_1 \sim g_2$ and $g_2 \sim g_3$. Then $\exists h_1, h_2 \in H$ s.t. $g_1 = g_2 h_1$ and $g_2 = g_3 h_2$. Then $g_1 = (g_3 h_2) h_1 = g_3 (h_2 h_1)$ and $h_2 h_1 \in H \Rightarrow g_1 \sim g_3$.

Therefore, the relation $\sim$ is an equivalence relation on $G$. (Its equivalence class containing $g'$ is $\{g'h : h \in H\} = g'H$: the equivalence classes are exactly the left cosets of $H$.)

Step 2: Let $A_1, \dots, A_k$ be the equivalence classes of $\sim$. Note that there are only finitely many, and that $|A_i| \lt \infty$, $1 \le i \le k$, because $|G| \lt \infty$. Since $\{A_i\}_{i=1}^k$ is a partition of $G$, we have that $|G| = \sum_{i=1}^k |A_i|$.

Now suppose $1 \le i \le k$, choose $g \in A_i$, and define a map $\tau : H \rightarrow A_i$ by $\tau(h) = gh$, $\forall h \in H$. The map $\tau$ is:

• Surjective ✓: $\forall g' \in A_i$, $g' \sim g \Rightarrow \exists h \in H$ s.t. $g' = gh = \tau(h)$.
• Injective ✓: If $\tau(h) = \tau(h')$ then $gh = gh' \Rightarrow h = h'$ (cancellation law).

Therefore $\tau$ is a bijection, so $|H| = |A_i|$ ($\forall 1 \le i \le k$). Finally,

$$|G| = \sum_{i=1}^k |A_i| = k|H| \Rightarrow |H| \mid |G|. \qquad \blacksquare$$

So the left cosets tile $G$ with $k$ tiles, each exactly the size of $H$. Build the tiling yourself: tap any element that isn't covered yet, and its whole coset slides into place as a new row.

A warning before the consequences: Lagrange's theorem only goes one way.

Consequences of Lagrange's Theorem

Combine Lagrange's theorem with $|g| = |\langle g \rangle|$ and you get facts about single elements.

Proof. $|g| = |\langle g \rangle|$ (the theorem in the section on orders), and $|\langle g \rangle| \mid |G|$ by Lagrange's theorem, since $\langle g \rangle \le G$. $\blacksquare$

Proof. $|g| \mid |G| \Rightarrow \exists k \in \mathbb{N}$ s.t. $|G| = k \cdot |g|$. Then $g^{|G|} = (g^{|g|})^k = e^k = e$. $\blacksquare$

That corollary pays off two debts from Foundations. The first: groups of prime order.

Proof. Let $g \in G$ with $g \neq e$. Then $|g| \mid p$ and $|g| \neq 1$ (only $e$ has order $1$), so $|g| = p$. So $\langle g \rangle$ is a subgroup with $|\langle g \rangle| = p = |G|$ elements, which forces $\langle g \rangle = G$. By part (ii) of the order theorem, $G = \{e, g, \dots, g^{p-1}\}$ with $g^i g^j = g^{i+j}$ and exponents read mod $p$, which is exactly the multiplication table of $C_p = \langle x \rangle$ with $g$ renamed $x$. $\blacksquare$

The second debt is Euler's theorem.

Proof. Let $G = (\mathbb{Z}/n\mathbb{Z})^\times$. Then $|G| = \varphi(n)$, and $(a, n) = 1 \Rightarrow a \in G$. By the above corollary, $a^{\varphi(n)} \equiv 1 \pmod n$. $\blacksquare$

Lagrange also makes primitive roots much cheaper to find. The order of $a$ in $(\mathbb{Z}/p\mathbb{Z})^\times$ has to divide $p - 1$, so instead of checking every exponent up to $p - 1$, we only check the divisors.

We can trim that list even further.

Compare the three strategies below: brute force, every divisor, and just the $(p-1)/q$ shortcut.

Spicy Bonus

Lagrange tells you which orders are allowed, but it never promises that any of them actually occur. Here's one case where a pairing argument does promise it.