Tag Archives: permutation

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$

1 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 $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

Permutation of Digits by Multiplication

Here is an expository write-up of this post.

The number $N=142857$ is interesting because of the following property

\begin{aligned}N&=142857\\ 2N&=285714\\ 3N&=428571\\ 4N&=571428\\ 5N&=714285\\ 6N&=857142\end{aligned}

and $7N=999999$. The last equation means that

$\displaystyle\frac 17=0.\overline{142857}.$

So multiplying $N$ by $1,2,3,4,5,6$ simply permutes the digits of $N$. As elements of $S_6$ these permutations correspond to (using cycle notation)

$\hbox{id}$, $(153)(264)$, $(165432)$, $(135)(246)$, $(123456)$, $(14)(25)(36)$

respectively. We can read off the following from this list.

• Since $(165432)$ and $(123456)$ are full-length cycles, $3$ and $5$ are primitive roots modulo $7$.
• $2$ and $4$ have order $3$ modulo $7$, while $6$ has order $2$.

In general, if $p$ is an odd prime and $b$ is a positive integer with order $d$ modulo $p$, then $1/p$ will have period $(b^d-1)/p$ of length $d$ in base $b$. This follows simply from observing that if $b^d-1=mp$ then

$\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots$.

Now let $b>p$ be a primitive root modulo $p$. We shall work in base $b$. Then $1/p$ will have period $L=(b^{p-1}-1)/p$ of length $p-1$. Since the periods of $1/p,2/p,\dots,(p-1)/p$ are $L,2L,\dots,(p-1)L$, all of length $p-1$, which are all powers of some permutation of the digits of $L$, and no two of which are congruent modulo $b$, it follows that the digits of $L$ are all distinct. So we’ve shown the following.

Theorem. If $p$ is an odd prime and $b>p$ is a primitive root modulo $p$, then the base $b$ expansion of $1/p$ has period of length $p-1$ with distinct digits.

Taking $p=7$, $b=10$ gives our previous example. So the prime $7$ in base $10$ is indeed very special, since it is the only prime less than $10$ for which $10$ is a primitive root.

1 Comment

Filed under Number Theory

Symmetric Polynomials in Two Variables

Let $R$ be a commutative ring. The fundamental theorem of symmetric polynomials says that any symmetric polynomial in $R[X,Y]$ can be expressed uniquely as a polynomial in $X+Y$ and $XY$.

Recently I was thinking about this along the following lines. Let $R[X,Y]^{S_2}$ denote the set of all symmetric polynomials in $R[X,Y]$. Then the theorem above is saying that $R[X,Y]^{S_2}$ is generated by $\{X+Y,XY\}$ as an $R$algebra, i.e., $R[X,Y]^{S_2}=R[X+Y,XY]$. Being unsuccessful at utilising this I ended up with the following. (I can’t see the best way of showing that a set generates an algebra.)

Let $f(X,Y)=\sum_{i,j}a_{i,j}X^iY^j\in R[X,Y]^{S_2}$. Since $f(X,Y)=f(Y,X)$, we have $a_{i,j}=a_{j,i}$ for all $i,j$. Hence $f(X,Y)=\sum_{i\le j}a_{i,j} (XY)^i(X^{j-i}+Y^{j-i})$. So it suffices to show that $X^n+Y^n$ can be expressed as a polynomial in $X+Y$ and $XY$ for each $n\ge 0$. But this follows easily by induction and the following identity

$X^n+Y^n=(X+Y)(X^{n-1}+Y^{n-1})-XY(X^{n-2}+Y^{n-2})$.

However, this argument doesn’t generalise immediately to more variables, and I don’t particularly like any of the proofs that I’ve found so far.

Filed under Algebra

Number of Permutations of Prime Order

In the last post we counted the number of elements of order 2 in the symmetric group $S_n$. In exactly the same way we can count the number of elements of order $p$, where $p$ is a prime number. Let this number be denoted by $N_p(n)$. Then

\displaystyle\begin{aligned}N_p(n)&=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{(p-1)!^k}{k!}\binom np\binom{n-p}{p}\cdots\binom{n-pk+p}{p}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{n!}{k!(n-pk)!p^k}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\binom{n}{pk}\frac{(pk)!}{k!p^k}.\end{aligned}

Here we adopt the convention $\binom nm=0$ if $m>n$. Note that

$\displaystyle\frac{(pk)!}{k!p^k}=\frac{(pk)!}{p\cdot 2p\cdots kp}\equiv (p-1)!^k\equiv (-1)^k\pmod p$

by Wilson’s theorem. So

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$.

If $n=n_rp^r+\cdots+n_1p+n_0$ and $k=k_{r}p^{r-1}+\cdots+k_2p+k_1$ are base $p$ expansions, then using Lucas’ theorem one has

$\displaystyle\binom{n}{pk}\equiv\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p$.

Therefore

\displaystyle\begin{aligned}N_p(n)&\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p\\ &\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{k_1+\cdots+k_r}\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p\\ &\equiv -1+\prod_{j=1}^r\sum_{k_j=0}^{n_j}(-1)^{k_j}\binom{n_j}{k_j}\pmod p\\ &\equiv -1\pmod p\end{aligned}

This generalizes the result from the previous post.

Corollary. The number of subgroups of order $p$ in $S_n$ is congruent to $1\pmod p$.

Proof. If there are $k$ subgroups of order $p$ in $S_n$, then $N_p(n)=k(p-1)\equiv -1\pmod p$ and so $k\equiv 1\pmod p$. $\square$

1 Comment

Filed under Combinatorics, Number Theory