Exercise 6.4.13

Lemma : Let $p$be a prime number. Let $\alpha =(i,j)\in S_p$be a transposition, and $\beta \in S_p$a $p$-cycle. Then $S_p=⟨\alpha ,\beta ⟩$.

Proof of lemma. $\beta \in S_p$ is a $p$-cycle, so $\beta =(a_1,a_2,\dots ,a_p)=(a,\beta (a),\dots ,{\beta }^{p-1}(a))$,

where $1\le a=a_1\le p$ is fixed.

The ${\beta }^i(a)$ are distinct, otherwise ${\beta }^i(a)={\beta }^j(a),i<j$ implies ${\beta }^{j-i}(a)=a$, so the cycle would have an order at most equal to $j-i<p$, thus not equal to $p$.

The support of $\beta$, $\mathrm{Supp}(\beta )=\{a_1,\cdots ,a_p\}$ has so $p$ elements, therefore

So there exist $r<p,s<p$ such that $i={\beta }^r(a),j={\beta }^s(a)$, thus $j={\beta }^{s-r}(i)$.

Let $k$ be the remainder of the division of $s-r$ by $p$. Then ${\beta }^k(i)=j,0\le k\le p-1.$ Moreover $i\ne j$, since $\alpha =(\mathit{ij})$ is a transposition, thus $k\ne 0$, so

As $p$ is prime, and $1\le k\le p-1$, ${\beta }^k$ is also a $p$-cycle.

Indeed, $H=\{n\in \mathbb{Z}|{({\beta }^k)}^n(a)=a\}$ is a subgroup of $\mathbb{Z}$, therefore it is of the form $H=\mathit{d\mathbb{Z}},d>0$.

As $p\in H$, $d$ divides $p$, and $d\ne 1$ (otherwise ${\beta }^k(a)=a,k<p$), thus $d=p$.

Consequently ${\beta }^k=(a,{\beta }^k(a),{\beta }^{2k}(a),\dots ,{\beta }^{(p-1)k}(a))$ is a $p$-cycle, thus $i$ is in the support of ${\beta }^k$, hence ${\beta }^k=(i,j={\beta }^k(i),\cdots ,{\beta }^{(p-1)k}(i))$.

Now we prove that $\alpha =(i,j),{\beta }^k=(i,j={\beta }^k(i),\cdots ,{\beta }^{(p-1)k}(i))$ generate $S_p$. In Exercice 7 where we have proved that $\tau =(1,2)$ and $\sigma =(1,2,\dots ,p)$ generate $S_p$.

A simple relabeling of the roots permits to prove that $\alpha ,{\beta }^k$ generate $S_p$. More formally, write

Let $g$ be any permutation in $S_n$. Then ${\gamma }^{-1}\mathit{g\gamma }\in S_n=⟨\sigma ,\tau ⟩$.

So ${\gamma }^{-1}\mathit{g\gamma }={\sigma }_1{\sigma }_2\cdots {\sigma }_l$, where ${\sigma }_i=\tau$, or ${\sigma }_i=\sigma$ (we can avoid negative powers since each element is of finite order).

Then $g=(\gamma {\sigma }_1{\gamma }^{-1})(\gamma {\sigma }_2{\gamma }^{-1})\cdots (\gamma {\sigma }_l{\gamma }^{-1})$, and $\gamma {\sigma }_i{\gamma }^{-1}\in \{\alpha ,{\beta }^k\}$, since by the Lemma of Exercise 6.4.1: $\mathit{\gamma \tau }{\gamma }^{-1}=\alpha ,\mathit{\gamma \sigma }{\gamma }^{-1}={\beta }^k$.

$S_n$ is generated by $\alpha ,{\beta }^k$, a fortiori by $\alpha ,\beta$.

Conclusion: if $p$ is prime, a $p$-cycle $\beta$, and any transposition $(i,j)$ generate $S_n$. $\square$