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

Leave a comment

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 ncycle (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<b. 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<b. 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

While tutoring today a student asked me about the following 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

screenshot-2016-10-03-21

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.

Leave a comment

Filed under Combinatorics