# Monthly Archives: October 2016

## A nice group theory result

While working on some group theory problems today a friend and I came up with the following result.

Lemma. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. If the order of $g\in G$ divides $|H|$, then $g\in H$.

Proof. Let $d$ be the order of $g$. Then the order $d'$ of $gH$ in $G/H$ divides both $d$ and $|G/H|$. But $\gcd(d,|G/H|)=1$. Hence $d'=1$, i.e., $gH=H$, i.e., $g\in H$. $\square$

Corollary 1. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. If $K\le G$ such that $|K|$ divides $|H|$, then $K\le H$.

Proof. Apply the lemma to the elements of $K$. $\square$

Corollary 2. Let $H$ be a normal subgroup of a finite group $G$ such that $\gcd(|H|,|G/H|)=1$. Then $H$ is the unique subgroup of $G$ of order $|H|$.

Proof. Use Corollary 1. $\square$

Here is an example of the lemma in action.

Problem. Show that $S_4$ has no normal subgroup of order $8$ or $3$.

Solution. If $H$ is a normal subgroup of $S_4$ of order $8$, then $\gcd(|H|,|S_4/H|)=1$. Hence every element of order $2$ or $4$ in $S_4$ must lie in $H$. In particular, $(1\ 2),(1\ 2\ 3\ 4)\in H$. By a result in the previous post, $H=S_4$, a contradiction.

Likewise, if $H$ is a normal subgroup of $S_4$ of order $3$, then $H$ must contain every 3-cycle; in particular, $(1\ 2\ 3),(2\ 3\ 4)\in H$. Hence $(1\ 2\ 3)(2\ 3\ 4)=(1\ 2)(3\ 4)\in H$. But this has order 2, and $2\nmid 3$, a contradiction. $\square$

More generally, we can prove the following.

Corollary 3. $S_n$ for $n\ge 4$ has no non-trivial proper normal subgroup $H$ with $\gcd(|H|,|S_n/H|)=1$.

Proof. Suppose otherwise and let $d$ divide $|H|$. Then $H$ must contain all $d$-cycles. So if $|H|$ is even then taking $d=2$ gives $H=S_n$. If $|H|$ is odd, it contains the cycles $\sigma=(1\ \cdots\ d)$ and $\rho=(d\ \cdots\ 2\ n)$ for some $3\le d. Then $\sigma\rho=(1\ 2\ n)\in H$ has order 3. So $|H|$ contains all 3-cycles, i.e., $A_n\le H$. Since $A_n\le S_n$ is maximal, either $H=A_n$ or $H=S_n$, a contradiction. $\square$

Filed under Algebra

## Generating the symmetric group

It’s a fairly well-known fact that the symmetric group $S_n$ can be generated by the transposition $(1\ 2)$ and the $n$cycle $(1\ \cdots\ n)$. One way to prove it is as follows.

1. Show that the transpositions $(a\ b)$ for $a,b\in\{1,\dots,n\}$ generate $S_n$.
2. Show that any transposition $(a\ b)$ can be obtained from $(1\ 2)$ and $(1\ \cdots\ n)$.

We also need the following key lemma the proof of which is routine.

Lemma. $\rho (a\ b)\rho^{-1}=(\rho(a)\ \rho(b))$ for any $\rho\in S_n$ and $a,b\in\{1,\dots,n\}$.

(1) is easily proven by the observation that any permutation of $1,\dots,n$ can be obtained by swapping two elements at a time. (2) is a bit more interesting.

We first use the lemma to observe that any transposition of the form $(a\ a+1)$ can be obtained from $(1\ 2)$ upon repeated conjugation by $(1\ \cdots\ n)$. Now, since $(a\ b)=(b\ a)$, WLOG let $a. Using the lemma, conjugating $(a\ a+1)$ by $(a+1\ a+2)$ gives $(a\ a+2)$, conjugating $(a\ a+2)$ by $(a+2\ a+3)$ gives $(a\ a+3)$, etc. In this way we can eventually get $(a\ b)$. So we are done by (1).

This argument shows that $S_n$ can in fact be generated by $(a\ a+1)$ and $(1\ \cdots\ n)$ for any $a$.

Now let’s consider an arbitrary transposition $\tau$ and an $n$-cycle $\sigma$ in $S_n$. By relabeling $1,\dots,n$, we can assume that $\sigma=(1\ \cdots\ n)$ and $\tau=(a\ b)$ for $a. Note that $\sigma^{-a+1}\tau\sigma^{a-1}=(1\ c)$ where $c=b-a+1$, so WLOG $\tau=(1\ c)$. Then $\sigma^k\tau\sigma^{-k}=(1+k\ c+k)$ for each $k$. In particular, taking $k=c-1$ gives $\sigma^{c-1}\tau\sigma^{-c+1}=(c\ 2c-1)=:\rho$. Then $\rho\tau\rho^{-1}=(1\ 2c-1)$. Repeating this procedure produces $(1\ c+k(c-1))$ for $k=0,1,2,\dots$. Now $\{c+k(c-1):k=0,1,\dots,n-1\}$ is a complete set of residues mod $n$ if and only if $\gcd(c-1,n)=1$, i.e., $\gcd(b-a,n)=1$. So we’ve shown that

Theorem. Let $\tau=(a\ b)$ be a transposition and $\sigma=(c_1\ \cdots\ c_n)$ be an $n$-cycle in $S_n$. Then $\tau$ and $\sigma$ generate $S_n$ if and only if $\gcd(c_b-c_a,n)=1$.

In particular, $(a\ b)$ and $(1\ \cdots\ n)$ generate $S_n$ if and only if $\gcd(b-a,n)=1$.

Corollary. $S_p$ is generated by any transposition and any $p$-cycle for $p$ prime.

1 Comment

Filed under Algebra

## A combinatorial identity

$(*)\qquad\qquad\qquad\displaystyle\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk=4^n$.

One way to prove it is to count the number of possible triples $(A,B,C)$ of sets with $C\subseteq B\subseteq A\subseteq S=\{1,\dots,n\}$. This can be done in two ways. First, if $A, B, C$ contain $i,j,k$ elements respectively then the number of such triples clearly equals the left-hand side of $(*)$. On the other hand, since each element of $S$ must belong to one of the four disjoint regions in the picture below

the number of such triples equals precisely $4^n$.

An algebraic proof can be obtained by repeated use of the binomial theorem:

$\displaystyle 4^n=\sum_{n\ge i\ge 0}\binom ni3^i=\sum_{n\ge i\ge j\ge 0}\binom ni\binom ij2^j=\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk$.

Similarly, one obtains the more general identity

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\binom{n}{i_1}\binom{i_1}{i_2}\cdots\binom{i_{m-1}}{i_m}=(m+1)^n$.

This also follows from the multinomial theorem since the left-hand side equals

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\frac{n!}{(n-i_1)!(i_1-i_2)!\cdots (i_{m-1}-i_m)!i_m!}=(m+1)^n$.