8: Cosets and Lagrange's Theorem
- Page ID
- 74645
Let \(G\) be a group and let \(H\) be a subgroup of \(G\). For each element \(a\) of \(G\) we define \[aH= \{ ah \ | \ h \in H \}.\] We call \(aH\) the coset of \(H\) in \(G\) generated by \(a\).
In the case of additive notation the coset of \(H\) in \(G\) generated by \(a\) is written in the form \[a + H = \{ a + h \ | \ h \in H \}\]
Sometimes \(aH\) is called a left coset and the set \(Ha = \{ ha \ | \ h \in H \}\) is called a right coset. Since we will only use left cosets, we will leave off the modifier left.
Problem 8.1 Here we consider all the cosets of a particular subgroup of the group \(U_{13}\). Recall that \[U_{13} = \{1, 2, \dots, 11, 12 \}\] and that the element \(2 \in U_{13}\) has order 12, so \[U_{13}= \{1, 2, 2^2, 2^3, \dots, 2^{11} \}.\] Since 2 has order 12, \(2^{12} = 1\), but \(2^i \neq 1\) for \(1 \le i \le 11\). It follows that \((2^4)^2 = 2^8 \neq 1\), but \((2^4)^3 = 2^{12} = 1\). Hence \(2^4\) has order 3 so \[H = \langle 2^{4} \rangle = \{ 1, 2^4, 2^8 \}\] is a subgroup of \(U_{13}\).
Show that the subgroup \(H\) just defined has exactly four different cosets in \(U_{13}\). Note that if we list all the cosets \[2H,\ 2^2H, \ 2^3H,\ \dots, \ 2^{11}H, \ 2^{12}H,\] it appears that there are 12 cosets. Show however that there are only four different cosets.
Note that none of the cosets overlap, that is, if two cosets are different, then their intersection is the empty set. Also note that every element of \(U_{13}\) is in one and only one of the four different cosets and each coset of \(H\) has the same number of elements as \(H\).
Problem 8.2 Find all cosets of the subgroup \(H = \langle (1\ 2) \rangle\) of the group \(S_3\).
Problem 8.3 Let \(G\) be a finite group and let \(H\) be a subgroup of \(G\). Let \(a,b \in G\). Prove the following statements.
- \(a \in aH\).
- \(\vert aH \vert = \vert H \vert\).
- If \(aH \cap bH \neq \emptyset\), then \(aH = bH\).
Suppose \(G = \{g_1, g_2, \dots, g_n \}\) is a group with \(n\) elements and \(H \le G\). Then if we form the list of all cosets of \(H\) in \(G\) we have \[g_1H, g_2H, \dots, g_nH.\] But as noted in the above examples some of the cosets in this list are repeated several times. If we remove all repetitions from the list we are left with what we shall call the distinct cosets of \(H\) in \(G\). If there are \(s\) distinct cosets we may denote them by \(a_1H, a_2H, \dots, a_sH\).
If \(G\) is a finite group and \(H \le G\) then \(\vert H \vert\) divides \(\vert G \vert\).
Proof Let \(n\) be the order of \(G\), and let \(k\) be the order of \(H\). We want to show that \(k \ \vert \ n\). Let \(a_1H, a_2H, \dots, a_sH\) be the distinct cosets of \(H\) in \(G\). Note that \(s\) is the number of distinct cosets. By Problem 8.3, these cosets are pairwise disjoint and their union is the whole group. That is, \[G = a_1H \cup a_2H \cup \cdots \cup a_sH \ \mbox{ and $a_iH \cap a_jH = \emptyset$ when $i \neq j$}.\] Since also each coset has the same number of elements as \(H\), we have \[\begin{aligned} \vert G \vert &=& \vert a_1H \vert + \vert a_2H \vert + \cdots + \vert a_sH \vert\\ &=& \vert H \vert + \vert H \vert + \cdots + \vert H \vert \\ &=& k + k + \cdots + k \\ &=& ks.\end{aligned}\] It follows that \(n=ks\). This shows that \(k \ \vert \ n\), and proves the theorem.
The following problems give some important corollaries of Lagrange’s Theorem.
Problem 8.4 Prove that if \(G\) is a finite group and \(a \in G\) then \(o(a)\) divides \(\vert G \vert\).
Problem 8.5 Prove that if \(G\) is a finite group and \(a \in G\) then \(a^{|G|}=e.\)
Problem 8.6 Prove that if \(p\) is a prime and \(a\) is a non-zero element of \(\mathbb{Z}_p\) then \(a^{p-1} =1\). [Here the product is multiplication modulo \(p\).] In number theory this is called Fermat’s Little Theorem
Problem 8.7 Prove that if \(n \in \mathbb{N}\) and \(a \in U_n\) then \(a^{\phi(n)} =1\). [Here the product is multiplication modulo \(n\).] In number theory this is called Euler’s Theorem.
Problem 8.8 Prove that if \(|G|=p\) where \(p\) is a prime then \(G\) is a cyclic group.
Problem 8.9 Prove that if \(G\) and \(H\) are groups of order \(p\) where \(p\) is prime then \(G \cong H\).
Problem 8.10 Let \(G\) be a group. Prove the following statements.
- If \(|G| = 2\) then \(G \cong \mathbb{Z}_2\).
- If \(|G| = 3\) then \(G \cong \mathbb{Z}_3\).
- If \(|G| = 5\) then \(G \cong \mathbb{Z}_5\).
Note that we have seen the first two items previously. But now we may give easier proofs.
Problem 8.11 Find two groups of order 4 that are not isomorphic.
Problem 8.12 Find two groups of order 6 that are not isomorphic.
We say that there are \(k\) isomorphism classes of groups of order \(n\) if there are \(k\) groups \(G_1, G_2, \dots, G_k\) such that (1) if \(i \neq j\) then \(G_i\) and \(G_j\) are not isomorphic, and (2) every group of order \(n\) is isomorphic to \(G_i\) for some \(i \in \{ 1, 2, \dots , k \}\).
This is sometimes expressed by saying that there are \(k\) groups of order \(n\) up to isomorphism or that there are \(k\) non-isomorphic groups of order \(n\).
In more advanced courses in algebra, it is shown that the number of isomorphism classes of groups of order \(n\) for \(n \le 17\) is given by the following table: \[\begin{array} {rccccccccccccccccc} Order:&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17 \\ Number:&1&1&1&2&1&2&1&5&2&2&1&5&1&2&1&14&1 \end{array}\]
This table means, for example, that one may find 14 groups of order 16 such that every group of order 16 is isomorphic to one and only one of these 14 groups.
Gordon Royle has such a list for groups of order up to 1000 (with the exception of orders 512 and 768). It is interesting to note that the largest number of groups seems to appear when the order is a power of 2, that is for 2, 4, 8, 16 32, etc. There are, for example, 56092 non-isomorphic groups of order 256.For the entire list go to Gordon Royle’s homepage at http://www.cs.uwa.edu.au/~gordon/ and follow the link to Combinatorial Data.
In a recent paper The groups of order at most 2000 by H. U. Besche, B. Eick, and E. A. O’Brien it is announced that they have been able to extend known results so that the number of groups of each order up to 2000 is now known. The research announcement may be found at http://www.ams.org/jourcgi.
In Table 8.1, we list the ten most challenging orders as taken from the paper by Besche, et al and the number of groups of each order. It is interesting to note that according to this paper there are 49, 487,365,422 groups of order \(2^{10}\) and only 423,164,062 remaining groups of order \(\le 2000\). Thus in excess of 99 % of the groups of order \(\le 2000\) are of order \(2^{10}\).
At the opposite extreme there are some orders for which there is only one isomorphism class of groups. For example, there is only one isomorphism class of groups of order \(n\) if \(n\) is prime. But there are some non-primes that have this property, for example, 15.
No formula is known for the number of isomorphism classes of groups of order \(n\). Although the number isomorphism classes of groups of order \(n\) is not known in general, it is possible to calculate easily the number of isomorphism classes of abelian groups of order \(n\) using the following famous theorem which we state without proof.
If \(G\) is a finite abelian group of order at least two then \[G \cong \mathbb{Z}_{p_1^{n_1}} \times \mathbb{Z}_{p_2^{n_2}} \times \cdots \times \mathbb{Z}_{p_s^{n_s}}\] where for each \(i\), \(p_i\) is a prime and \(n_i\) is a positive integer. Moreover, the prime powers \(p_i^{n_i}\) are unique except for the order of the factors.\(\blacksquare\)
If the group \(G\) in the above theorem has order \(n\) then \[n={p_1^{n_1}}{p_2^{n_2}}\dots {p_s^{n_s}}.\] So the \(p_i\) may be obtained from the prime factorization of the order of the group \(G\). These primes are not necessarily distinct, so we cannot say what the \(n_i\) are. However, we can find all possible choices for the \(n_i\). For example, if \(G\) is an abelian group of order \(72=3^2 \cdot 2^3\) then \(G\) is isomorphic to one and only one of the following groups. Note that each corresponds to a way of factoring 72 as a product of prime powers. \[\begin{array} {ll} \mathbb{Z}_9 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 & \qquad 72 = 9 \cdot 2 \cdot 2 \cdot 2 \\ \mathbb{Z}_9 \times \mathbb{Z}_4 \times \mathbb{Z}_2 & \qquad 72 = 9 \cdot 4 \cdot 2 \\ \mathbb{Z}_9 \times \mathbb{Z}_8 & \qquad 72 = 9 \cdot 8 \\ \mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2 & \qquad 72 = 3 \cdot 3 \cdot 2 \cdot 2 \cdot 2 \\ \mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_4 \times \mathbb{Z}_2 & \qquad 72 = 3 \cdot 3 \cdot 4 \cdot 2 \\ \mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_8 & \qquad 72 = 3 \cdot 3 \cdot 8 \end{array}\] Thus there are exactly 6 non-isomorphic abelian groups of order 72.
Corollary For \(n \ge 2\), the number of isomorphism classes of abelian groups of order \(n\) is equal to the number of ways to factor \(n\) as a product of prime powers (where the order of the factors does not count).
Problem 8.13 Determine the number of non-isomorphic abelian groups of order \(n\) where \(n \in \{ 4, 6, 8, 16,1800 \}\)
Problem 8.14 Prove that \(\mathbb{Z}_6 \cong \mathbb{Z}_2 \times \mathbb{Z}_3\).
In number theory it is proven that if \(n=a b\) and \(\gcd (a,b) = 1\) then \(\mathbb{Z}_n \cong \mathbb{Z}_a \times \mathbb{Z}_b\). This is called the Chinese Remainder Theorem.