## 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.