Monthly Archives: March 2010

Fermat’s Little Theorem

Use Lagrange’s Theorem in the multiplicative group (\mathbb{Z}/(p))^\times to prove Fermat’s Little Theorem: if p is prime then a^p \equiv a \ \mathrm{mod}\ p.

If p is prime, then \varphi(p) = p-1 (where \varphi denotes the Euler totient). Thus |((\mathbb{Z}/(p))^\times| = p-1. So for all a \in (\mathbb{Z}/(p))^\times, we have |a| divides p-1. Hence a = 1 \cdot a = a^{p-1} a = a^p mod p.

Compute the stabilizer of an element under a given action of Sym(n)

Fix i \in \{ 1, \ldots, n \} = A, and let S_n act on A in the natural way. Show that \mathsf{stab}_{S_n}(i) \cong S_{n-1}.

It is clear that \mathsf{stab}_{S_n}(i) = \{ \sigma \in S_n \ |\ \sigma(i) = i \}. Removing from each function in this set the pair (i,i), we have the full symmetric group on \{ 1, 2, \ldots, i-1,i+1,\ldots,n\}. We saw in a previous exercise that the isomorphism type of S_A depends only on the cardinality of A, so that the conclusion holds.

Sym(4) has no normal subgroups of order 8 or 3

Prove that S_4 does not have a normal subgroup of order 8 or a normal subgroup of order 3.

Let K \leq S_4 be a subgroup of order 3; then K = \langle (a\ b\ c) \rangle for some (a\ b\ c). Note that K(a\ d) = \{ (a\ d), (a\ d\ b\ c), (a\ d\ c\ b) \} and (a\ d)K = \{ (a\ d), (a\ b\ c\ d), (a\ c\ b\ d) \}, so that K is not normal in S_4.

Now suppose H \leq S_4 is a subgroup of order 8. Now the order of every element in H must divide 8 by Lagrange, and no element of S_4 has order 8. Moreover, S_4 has 9 elements of order 2: 6 2-cycles and 3 products of disjoint 2-cycles. Suppose H does not contain an element of order 4. If H contains all 3 products of 2 cycles, then (WLOG) we have (a\ c) \circ (a\ b)(c\ d) = (a\ b\ c\ d) \in H, a contradiction. If H does not contain all the products of 2 cycles then it must contain at least 5 2-cycles; WLOG then H contains elements (a\ b), (a\ c), and (a\ d), and (a\ d)(a\ c)(a\ b) = (a\ b\ c\ d) \in H, a contradiction. Thus H contains a 4-cycle.

Say (a\ b\ c\ d) \in H. Then \langle (a\ b\ c\ d) \rangle \leq H, where \langle (a\ b\ c\ d) \rangle = \{ 1, (a\ b\ c\ d), (a\ c)(b\ d), (a\ d\ c\ b) \}. Suppose for a moment that H contains another element \sigma of order 4; without loss of generality, \sigma is one of (a\ b\ d\ c) and (a\ c\ b\ d). If (a\ b\ d\ c) \in H, then \langle (a\ b\ d\ c) \rangle = \{ 1, (a\ b\ d\ c), (a\ d)(b\ c), (a\ c\ d\ b) \} \leq H. But then (a\ b\ d\ c)(a\ b\ c\ d) = (a\ d\ b) \in H, but (a\ d\ b) has order 3. Thus (a\ b\ d\ c) \notin H. Similarly, (a\ c\ b\ d) \notin H, hence the remaining elements of H all have order 2. There are 8 such elements remaining.

Note that (a\ b)(a\ b\ c\ d) = (b\ c\ d), (a\ d)(a\ b\ c\ d) = (a\ b\ c), (b\ c)(a\ b\ c\ d) = (a\ c\ d), and (c\ d)(a\ b\ c\ d) = (a\ b\ d), so that (a\ b), (a\ d), (b\ c), and (c\ d) are not in H. Then the remaining elements must be in H, so that H = \{ 1, (a\ b\ c\ d), (a\ c)(b\ d), (a\ d\ c\ b), (a\ c), (b\ d), (a\ b)(c\ d), (a\ d)(b\ c) \}. A simple calculation shows that indeed H = \langle (a\ b\ c\ d), (b\ d) \rangle.

We saw in the previous exercise that, if K = \langle (a\ b\ c) \rangle, then HK \neq KH. By Corollary 15 in the text, then, H is not normal in S_4.

Exhibit two subgroups which do not commute in Sym(4)

Fix any labeling of the vertices of a square and use this to identify D_8 as a subgroup of S_4. Prove that the subgroups D_8 and \langle (1\ 2\ 3) \rangle do not commute in S_4.

We can label the vertices of a square as follows.

Now a 90 degree clockwise rotation corresponds to the permutation (1\ 2\ 3\ 4) and a reflection across the (1,3) axis to (2\ 4).

Now let H = \langle (1\ 2\ 3\ 4), (2\ 4) \rangle and K = \langle (1\ 2\ 3) \rangle. If HK = KH, then in particular (1\ 2\ 3\ 4)(1\ 2\ 3)(1\ 4\ 3\ 2) = (2\ 3\ 4) \in K, a contradiction. So HK \neq KH.

Given a subgroup of a group, the numbers of left and right cosets are equal

Let G be a group and H \leq G. Prove that the map x \mapsto x^{-1} sends each left coset to a right coset (of H), and hence |H \backslash G| = |G/H|.

(This is a slightly different approach.)

Define \psi : G \rightarrow H \backslash G by \psi(x) = Hx^{-1}. Suppose y^{-1}x \in H; then y^{-1} \in Hx^{-1}. and we have Hy^{-1} = Hx^{-1}, so \psi(x) = \psi(y). By a lemma to a previous exercise, this induces a mapping \varphi : G/H \rightarrow H \backslash G given by \varphi(xH) = Hx^{-1}. \psi is clearly surjective, so \varphi is surjective. Now suppose \varphi(x) = \varphi(y); then Hx^{-1} = Hy^{-1}, so that in particular y^{-1} \in Hx^{-1} and hence y^{-1}x \in H. Thus xH = yH. Hence \varphi is a bijection.

Subgroup index is multiplicative across intermediate subgroups

Let G be a group and K \leq H \leq G. Prove that [G : K] = [G : H] \cdot [H : K].

We proved this as a lemma to a previous theorem.

Bounds on the index of an intersection of two subgroups

Let G be a group and let H,K \leq G be subgroups of finite index; say [G:H] = m and [G:K] = n. Prove that \mathsf{lcm}(m,n) \leq [G: H \cap K] \leq mn. Deduce that if m and n are relatively prime, then [G: H \cap K] = [G : H] \cdot [G : K].

Lemma 1: Let A and B be sets, \varphi : A \rightarrow B a map, and \Phi an equivalence relation on A. Suppose that if a_1 \,\Phi\, a_2 then \varphi(a_1) = \varphi(a_2) for all a_1,a_2 \in A. Then \psi : A/\Phi \rightarrow B given by [a]_\Phi \mapsto \varphi(a) is a function. Moreover, if \varphi is surjective, then \psi is surjective, and if \varphi(a_1) = \varphi(a_2) implies a_1 \,\Phi\, a_2 for all a_1,a_2 \in A, then \psi is injective. Proof: \psi is clearly well defined. If \varphi is surjective, then for every b \in B there exists a \in A such that \varphi(a) = b. Then \psi([a]_\Phi) = b, so that \psi is surjective. If \psi([a_1]) = \psi([a_2]), then \varphi(a_1) = \varphi(a_2), so that a_1 \,\Phi\, a_2, and we have [a_1] = [a_2]. \square

First we prove the second inequality.

Lemma 2: Let G be a group and let H,K \leq G be subgroups. Then there exists an injective map \psi : G/(H \cap K) \rightarrow G/H \times G/K. Proof: Define \varphi : G \rightarrow G/H \times G/K by \varphi(g) = (gH,gK). Now if g_2^{-1}g_1 \in H \cap K, then we have g_2^{-1}g_1 \in H, so that g_1H = g_2H, and g_2^{-1}g_1 \in K, so that g_1K = g_2K. Thus \varphi(g_1) = \varphi(g_2). Moreover, if (g_1H,g_2K) = (g_1H,g_2K) then we have g_2^{-1}g_1 \in H \cap K, so that g_1(H \cap K) = g_2(H \cap K). By Lemma 1, there exists an injective mapping \psi : G/(H \cap K) \rightarrow G/H \times G/K given by \psi(g(H \cap K)) = (gH,gK). \square

As a consequence, if [G : H] and [G : K] are finite, [G : H \cap K] \leq [G : H] \cdot [G : K].

Now to the first inequality.

Lemma 3: Let G be a group and K \leq H \leq G. Let S be a set of coset representatives of G/H. Then the mapping \psi : S \times H/K \rightarrow G/K given by \psi(g,hK) = ghK is bijective. Proof: (Well defined) Suppose h_2^{-1}h_1 \in K. Then h_1K = h_2K, so that gh_1K = gh_2K, and we have \psi(g,h_1K) = \psi(g,h_2K). (Surjective) Let gK \in G/K. Now g \in \overline{g}H for some \overline{g} \in S; say g = \overline{g}h. Then \psi(\overline{g},hK) = gK, so that \psi is surjective. (Injective) Suppose \psi(g_1,h_1K) = \psi(g_2,h_2K). Then g_1h_1K = g_2h_2K; in particular, g_1h_1 \in g_2h_2K \subseteq g_2H, so that g_1 \in g_2H and hence g_2^{-1}g_1 \in H. So g_1H = g_2H, and in fact g_2 = g_1. Thus h_1K = h_2K, and \psi is injective. \square

As a consequence, we have [G : H] \cdot [H : K] = [G : K].

Now in this case we have H \cap K \leq H \leq G. Thus m divides [G : H \cap K] and n divides [G : H \cap K], so that \mathsf{lcm}(m,n) divides [G : H \cap K]. In particular, since all numbers involved are natural, \mathsf{lcm}(m,n) \leq [G : H \cap K].

Finally, if m and n are relatively prime, then \mathsf{lcm}(m,n) = mn, and we have [G : H \cap K] = mn.

Alternate proof of Cauchy’s Theorem

Let G be a finite group and let p be a prime dividing |G|. Let \mathcal{S} denote the set of all p-tuples of elements of G whose product is 1. That is, \mathcal{S} = \{ (x_1, x_2, \ldots, x_p) \ |\ x_i \in G\ \mathrm{and}\ x_1x_2 \ldots x_p = 1 \}. Now define a relation \sim on \mathcal{S} as follows: \alpha \sim \beta if and only if \beta is a cyclic permutation of \alpha.

  1. Prove that \mathcal{S} has |G|^{p-1} elements, hence has order divisible by p.
  2. Prove that a cyclic permutation of an element of \mathcal{S} is again in \mathcal{S}.
  3. Prove that \sim is an equivalence relation.
  4. Prove that an equivalence class contains a single element if and only if it is of the form (x,x,\ldots,x) for some x with x^p = 1.
  5. Prove that every equivalence class has order 1 or p. Deduce that |G|^{p-1} = k+pd, where k is the number of classes of size 1 and d is the number of classes of size p.
  6. Noting that \{(1,1,\ldots,1)\} is a class of size 1, deduce that there exists a nonidentity element x \in G such that x^p = 1.

  1. We prove this equality by attempting to choose an arbitrary element of \mathcal{S}. Note that the first p-1 elements x_1,x_2, \ldots, x_{p-1} of an arbitrary tuple in \mathcal{S} may be chosen arbitrarily – with |G| choices for each; a total of |G|^{p-1} distinct choices. This having been done, the last entry is determined uniquely, namely (x_1 x_2 \ldots x_{p-1})^{-1}. This exhausts all possible ways of choosing an element of \mathcal{S}, so that |\mathcal{S}| = |G|^{p-1}.
  2. Suppose (x_1,x_2,\ldots,x_p) \in \mathcal{S}, and let (x_k,x_{k+1},\ldots,x_p,x_1,\ldots,x_{k-1}) be a cyclic permutation. Then (x_1x_2\ldots x_{k-1})(x_k x_{k+1}\ldots x_p) = 1, so that (x_k x_{k+1}\ldots x_p)(x_1x_2\ldots x_{k-1}) = 1. Thus the cyclic permutation is in \mathcal{S}.
    1. Every p-tuple is trivially a cyclic permutation of itself, so that \sim is reflexive.
    2. If \sigma is a cyclic permutation of \tau, say by k slots, then \tau may be recovered by cyclically permuting \sigma p-k times.
    3. If \sigma is the k-th cyclic permutation of \tau and \theta the \ell-th cyclic permutation of \sigma, then \theta is the k+\ell-th cyclic permutation of \tau.

    Hence \sim is an equivalence relation.

  3. (\Rightarrow) Let \{ \sigma = (x_1,x_2,\ldots,x_p) \} be a \sim equivalence class containing a single element, and let 1 \leq k \leq p. Now the k-th cyclic permutation of \sigma is again \sigma, so that x_k = x_1 for all such k. Thus \sigma = (x,x,\ldots,x).

    (\Leftarrow) Trivial.

  4. Suppose \sigma \in \mathcal{S} has exactly k distinct cyclic permutations; note that k \leq p. Now for each 1 \leq i \leq p, we have x_i = x_{k+i}, where indices are taken mod p. More generally, x_i = x_{ak+i} for each i and a \in \mathbb{Z}, with indices taken modulo p. Suppose k does not divide p; since p is prime, then, \mathsf{gcd}(k,p) = 1. We saw previously that ak+1 ranges over all residue classes of \mathbb{Z}/(p), so that \sigma = (x,x,\ldots,x) for some x \in G. Otherwise, k divides p, so that k = 1 (and \sigma = (x,x,\ldots,x)) or k = p. Hence every \sigma \in \mathcal{S} is in a \sim-equivalence class of size 1 or p. Counting elements of \mathcal{S}, then, we have |G|^{p-1} = k+pd where k is the number of size 1 equivalence classes and d the number of size p equivalence classes.
  5. Since p divides |G| and pd, we have p|k where k is the number of size 1 equivalence classes. Hence k > 1, and there exists at least one size one equivalence class which is not trivial – i.e., has the form \{ (x,x,\ldots,x) \} for some nonidentity x \in G. Thus there exists an element x \in G such that x^p = 1.

Finite subgroups with relatively prime orders intersect trivially

Let G be a group and let H, K \leq G be finite subgroups of relatively prime order. Prove that H \cap K = 1.

Let |H|=p and |K|=q. We saw in a previous exercise that H \cap K is a subgroup of both H and K; by Lagrange’s Theorem, then, |H \cap K| divides p and q. Since \mathsf{gcd}(p,q) = 1, then, |H \cap K| = 1. Thus H \cap K = 1.

Alternate characterization of cosets as equivalence classes

Let G be a group and H \leq G. Define a relation \sim on G by a \sim b if and only if b^{-1} a \in H. Prove that \sim is an equivalence relation and describe for each a \in G the equivalence class [a]. Use this to prove the following proposition.

Proposition: Let G be a group and H \leq G. Then (i) the set of left cosets of H is a partition of G and (ii) for all u,v \in G, uH = vH if and only if v^{-1} u \in H.

  1. \sim is an equivalence:
    1. Reflexive: x^{-1}x = 1 \in H, so that x \sim x for all x \in G.
    2. Symmetric: Suppose x \sim y. Then y^{-1} x \in H. Since H is a subgroup, (y^{-1}x)^{-1} = x^{-1} y \in H, and we have y \sim x.
    3. Transitive: Suppose x \sim y and y \sim z. Then y^{-1}x \in H and z^{-1}y \in H. Thus we have y^{-1}x = h_1 and z^{-1}y = h_2 for some h_1,h_2 \in H. Now y = xh_1^{-1}, and substituting yields z^{-1}xh_1^{-1} = h_2, hence z^{-1}x = h_2h_1. Thus x \sim z.

    So \sim is an equivalence.

  2. Let x \in G and suppose y \sim x. Then x^{-1}y = h for some h \in H, hence y = xh. Thus y \in xH; so [x] \subseteq xH. Now suppose y \in xH. Then y = xh for some h \in H, hence x^{-1}y \in H and we have y \sim x, so that xH \subseteq [x]. Thus the \sim-equivalence classes of G are precisely the left cosets of H.
  3. Proof of Proposition 4: The left cosets of H form the equivalence classes of a relation \sim on G defined by x \sim y if and only if y^{-1}x \in H; the second conclusion of Proposition 4 follows trivially.