Cosets and Lagrange's theorem

Lesson 6 ended with an observation: in every example, the order of a subgroup divides the order of the group. This lesson proves that it always happens. The tool is the coset, a translated copy of a subgroup. Cosets split a group into pieces of equal size, and counting the pieces gives Lagrange's theorem, the most used result in finite group theory. Its corollaries include the fact that every group of prime order is cyclic, and two classical theorems of number theory, Fermat's little theorem and Euler's theorem, which underpin RSA encryption.

Cosets

Let \(H\) be a subgroup of \(G\) and \(a \in G\). The left coset of \(H\) containing \(a\) is

\[ aH = \{ah : h \in H\}, \]

and the right coset is \(Ha = \{ha : h \in H\}\). In additive notation the left coset is written \(a + H\). Some first examples:

• In \(\mathbb{Z}\) with \(H = 3\mathbb{Z}\), the cosets are \(0 + 3\mathbb{Z}\), \(1 + 3\mathbb{Z}\) and \(2 + 3\mathbb{Z}\): the three residue classes modulo 3. Every integer lies in exactly one.

• In \(\mathbb{Z}_{12}\) with \(H = \langle 4 \rangle = \{0, 4, 8\}\), the cosets are \(\{0, 4, 8\}\), \(\{1, 5, 9\}\), \(\{2, 6, 10\}\) and \(\{3, 7, 11\}\).

• In \(\mathbb{R}^2\) under vector addition, with \(H\) a line through the origin, the cosets are the lines parallel to \(H\). They cover the plane without overlapping.

• In \(D_n\) with \(H\) the rotation subgroup, there are two cosets: \(H\) itself and \(sH\), the set of all reflections.

Two cosets are often equal even when written differently: in \(\mathbb{Z}_{12}\), \(1 + H = 5 + H = 9 + H\). The rule for when this happens is the most useful fact about cosets.

Lemma. Let \(H \le G\) and \(a, b \in G\). The following are equivalent: (i) \(aH = bH\); (ii) \(b \in aH\); (iii) \(a^{-1}b \in H\). Moreover any two left cosets are either equal or disjoint, and every left coset has exactly \(|H|\) elements.

Proof: (i) implies (ii) because \(b = be \in bH = aH\). (ii) implies (iii): if \(b = ah\) then \(a^{-1}b = h \in H\). (iii) implies (i): if \(a^{-1}b = h \in H\), then \(b = ah\), so \(bh' = a(hh') \in aH\) for every \(h' \in H\), giving \(bH \subseteq aH\); and \(a = bh^{-1}\) gives \(aH \subseteq bH\) in the same way. For disjointness, if \(c \in aH \cap bH\) then by (ii), applied twice, \(aH = cH = bH\). For the size, the map \(h \mapsto ah\) from \(H\) to \(aH\) is onto by definition and one-to-one by cancellation.

The relation \(a \sim b \iff a^{-1}b \in H\) is therefore an equivalence relation on \(G\) whose classes are the left cosets. In \(\mathbb{Z}\) with \(H = n\mathbb{Z}\) it is congruence modulo \(n\), so cosets generalize residue classes.

Lagrange's theorem

Theorem (Lagrange). If \(G\) is a finite group and \(H \le G\), then \(|H|\) divides \(|G|\). More precisely, \(|G| = [G : H]\,|H|\), where the index \([G : H]\) is the number of left cosets of \(H\) in \(G\).

Proof: the left cosets partition \(G\) into \([G : H]\) disjoint blocks, each with exactly \(|H|\) elements, by the lemma. Counting the elements of \(G\) block by block gives \(|G| = [G : H]\,|H|\).

The result carries Lagrange's name because of his 1771 memoir on the solution of polynomial equations, in which he studied how many different values a function of the roots takes when the roots are permuted, and showed that this number divides \(n!\). In modern language that is the special case of the theorem for subgroups of \(S_n\); the general statement for abstract groups, and the coset proof, came decades later once the group concept itself had been formulated.

Corollaries

Corollary 1. In a finite group, the order of every element divides the order of the group. Proof: the order of \(a\) is the order of the cyclic subgroup \(\langle a \rangle\) (lesson 3).

Corollary 2. If \(|G| = n\), then \(a^n = e\) for every \(a \in G\). Proof: if \(a\) has order \(m\), then \(m \mid n\) by Corollary 1, so \(a^n = (a^m)^{n/m} = e\).

Corollary 3. Every group of prime order \(p\) is cyclic, and is generated by any of its nonidentity elements. Proof: if \(a \ne e\), the order of \(a\) divides \(p\) and is not 1, so it is \(p\), and \(\langle a \rangle = G\). So up to renaming there is exactly one group of each prime order, namely \(\mathbb{Z}_p\).

Corollary 4 (Fermat's little theorem). If \(p\) is prime and \(p \nmid a\), then \(a^{p-1} \equiv 1 \pmod p\). Proof: apply Corollary 2 to the class of \(a\) in \(U(p)\), which has order \(p - 1\).

Corollary 5 (Euler's theorem). If \(\gcd(a, n) = 1\) then \(a^{\varphi(n)} \equiv 1 \pmod n\), where \(\varphi(n) = |U(n)|\) is Euler's totient. Proof: the same argument in \(U(n)\).

RSA encryption rests on Corollary 5. A public modulus \(n = pq\) is a product of two large primes, so \(\varphi(n) = (p-1)(q-1)\). Encryption raises a message \(m\) to a public power \(e\), and decryption raises the result to a secret power \(d\) with \(ed \equiv 1 \pmod{\varphi(n)}\). Writing \(ed = 1 + k\varphi(n)\), Euler's theorem gives \(m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m\) for messages coprime to \(n\) (and a short extra argument handles the rest). Computing \(d\) requires \(\varphi(n)\), which is easy for whoever knows \(p\) and \(q\) and believed to be infeasible for anyone who must factor \(n\).

The converse fails

Lagrange's theorem says subgroup orders divide \(|G|\); it does not say every divisor occurs. For cyclic groups every divisor does occur (lesson 3), but the alternating group \(A_4\), of order 12, has no subgroup of order 6.

Proof: \(A_4\) consists of the identity, the three products of two disjoint transpositions, and eight 3-cycles. Suppose \(H \le A_4\) has order 6, so index 2. Then for every \(g \in A_4\), \(g^2 \in H\): if \(g \notin H\), the two cosets are \(H\) and \(gH\); if \(g^2\) were not in \(H\) we would have \(g^2H = gH\), so \(g \in H\) by the lemma, a contradiction. Now let \(\sigma\) be any 3-cycle. Since \(\sigma^3 = e\), we have \(\sigma = \sigma^4 = (\sigma^2)^2 \in H\). So \(H\) contains all eight 3-cycles, which is more than six elements. No such \(H\) exists.

Partial converses do hold. Cauchy's theorem (proved in lesson 11 with group actions) says that if a prime \(p\) divides \(|G|\) then \(G\) has an element, hence a subgroup, of order \(p\). Sylow's theorems of 1872 go further: if \(p^k\) is the largest power of \(p\) dividing \(|G|\), then \(G\) has a subgroup of order \(p^k\).

Classifying the groups of order 4 and 6

Lagrange's theorem is strong enough to list every group of a small order. Two groups are regarded as the same here when one is obtained from the other by renaming elements; lesson 8 makes this precise as isomorphism.

Theorem. Every group of order 4 is either cyclic, like \(\mathbb{Z}_4\), or a Klein four-group, like \(\mathbb{Z}_2 \times \mathbb{Z}_2\).

Proof: element orders divide 4, so they are 1, 2 or 4. If some element has order 4, it generates \(G\) and \(G\) is cyclic. Otherwise every \(a \ne e\) satisfies \(a^2 = e\), so \(a = a^{-1}\). Then for any \(a, b\), \(ab = (ab)^{-1} = b^{-1}a^{-1} = ba\), so \(G\) is abelian. Taking distinct nonidentity elements \(a\) and \(b\), the element \(ab\) is neither \(e\) (else \(b = a^{-1} = a\)) nor \(a\) nor \(b\), so \(G = \{e, a, b, ab\}\) with every square equal to \(e\): that is the Klein table of lesson 2.

Theorem. Every group of order 6 is either cyclic or has the structure of \(D_3\), equivalently \(S_3\).

Proof: suppose \(G\) has order 6 and is not cyclic, so element orders are 1, 2 or 3. Not every nonidentity element can have order 2: then, as above, \(G\) would be abelian and \(\{e, a, b, ab\}\) would be a subgroup of order 4, which does not divide 6. So there is an element \(r\) of order 3, and \(H = \langle r \rangle\) has index 2. By the argument used for \(A_4\), every \(g \notin H\) has \(g^2 \in H\). Such a \(g\) cannot have order 3, since then \(g = (g^2)^{-1} \in H\); and it does not have order 6. So every element outside \(H\) has order 2. Choose \(s \notin H\). Then \(sr \notin H\) as well (else \(s \in Hr^{-1} = H\)), so \((sr)^2 = e\), that is \(srs = r^{-1}\). The six elements \(e, r, r^2, s, sr, sr^2\) are distinct, they are all of \(G\), and they multiply by exactly the rules of \(D_3\) from lesson 5.

Combined with Corollary 3, this settles every order up to 7: there is one group each of orders 1, 2, 3, 5 and 7, and two each of orders 4 and 6. The counts then become irregular. There are five groups of order 8, namely \(\mathbb{Z}_8\), \(\mathbb{Z}_4 \times \mathbb{Z}_2\), \(\mathbb{Z}_2^3\), \(D_4\) and the quaternion group \(Q_8\), fourteen of order 16, and computer searches completed around 2001 found 49,487,365,422 groups of order \(2^{10} = 1024\), the vast majority of all groups of order up to 2000.

Left and right cosets, and computing them

In an abelian group \(aH = Ha\) always. In general they can differ. In \(S_3\) with \(H = \{e, (1\,2)\}\), multiplying right to left, \((1\,3)H = \{(1\,3), (1\,2\,3)\}\) while \(H(1\,3) = \{(1\,3), (1\,3\,2)\}\). The number of right cosets is always equal to the number of left cosets, because \(aH \mapsto Ha^{-1}\) is a well-defined bijection between them, so the index does not depend on the side. Subgroups whose left and right cosets agree are the normal subgroups of lesson 9.

The code below lists the left and right cosets of \(\langle (1\,2) \rangle\) in \(S_3\), checks Lagrange's theorem for every subgroup generated by one or two elements of \(S_4\), and confirms by brute force that \(A_4\) has no subgroup of order 6.

from itertools import permutations, combinations

def compose(a, b):                    # a after b
    return tuple(a[b[i]] for i in range(len(b)))

def generated(gens, n):
    e = tuple(range(n))
    H, frontier = {e}, [e]
    while frontier:
        new = []
        for h in frontier:
            for g in gens:
                x = compose(g, h)
                if x not in H:
                    H.add(x); new.append(x)
        frontier = new
    return frozenset(H)

def sign(p):
    return (-1) ** sum(p[i] > p[j] for i in range(len(p)) for j in range(i + 1, len(p)))

S3 = list(permutations(range(3)))
H = generated([(1, 0, 2)], 3)
left = {frozenset(compose(a, h) for h in H) for a in S3}
right = {frozenset(compose(h, a) for h in H) for a in S3}
print("left cosets:", len(left), " right cosets:", len(right), " same sets:", left == right)

S4 = list(permutations(range(4)))
subs = {generated(c, 4) for k in (1, 2) for c in combinations(S4, k)}
print("subgroup orders in S4:", sorted({len(K) for K in subs}))
print("all divide 24:", all(24 % len(K) == 0 for K in subs))

A4 = [p for p in S4 if sign(p) == 1]
subsA4 = {generated(c, 4) for k in (1, 2) for c in combinations(A4, k)}
print("subgroup orders in A4:", sorted({len(K) for K in subsA4}))

left cosets: 3  right cosets: 3  same sets: False
subgroup orders in S4: [1, 2, 3, 4, 6, 8, 12, 24]
all divide 24: True
subgroup orders in A4: [1, 2, 3, 4, 12]

The subgroups of \(S_4\) found have orders 1, 2, 3, 4, 6, 8, 12 and 24, all divisors of 24, while those of \(A_4\) have orders 1, 2, 3, 4 and 12, with 6 absent. Every subgroup of \(A_4\) is generated by at most two elements, so the search is complete for \(A_4\).