Why is $S_5$ generated by any combination of a transposition and a 5-cycle?

Solution 1:

Proposition. $S_n$ is generated by a transposition $\tau=(xy)$ and an $n$-cycle $\sigma$ if and only if $|\rm{i}_x-\rm{i}_y|$ is coprime to $n$, where $\rm{i}_m$ denotes the index of $m$ as a letter in $\sigma$.

Proof. Let $\tau=(xy)$, $\sigma=(x_1x_2\ldots x_n)$, and assume w.l.o.g. that $x=x_a$, $y=x_b$ with $a<b$. We may then relabel $1,\ldots, n\longrightarrow x_1,\ldots ,x_n$, so that $\sigma=(12\ldots n)$ and $\tau=(ab)$. Therefore, it suffices to consider an arbitrary transposition $\tau=(ab)$ with the $n$-cycle $\sigma=(12\ldots n)$. Throughout this proof, take all letters modulo $n$ unless otherwise specified. Set $d=\operatorname{gcd}(n,b-a)$.

We begin with $d=1$. Observing that $\sigma^{k}(i)= i+k$, we see that $\sigma^{b-a}(a)= b$, and thus $\sigma^{b-a}$ is an $n$-cycle $\sigma^{b-a}=(ab\ldots)$. Thus again we may suitably relabel $1,\ldots, n$ so that $\tau=(12),\sigma^{b-a}=(1\ldots n)$. We know that conjugating $\tau$ by $\sigma^{k(b-a)}$ yields the transposition $(k,k+1)$, and it is not difficult to see that $\{(12),(23),\ldots,(n-1,n)\}$ generates $S_n$, so we see that $\langle \tau, \sigma^{b-a}\rangle=S_n$. Because $\operatorname{gcd}(b-a,n)=1$, $\sigma^{b-a}$ generates $\langle \sigma \rangle$, and thus we conclude that $S_n=\langle \tau,\sigma\rangle$.

To prove the converse, we will consider the induced action of $\tau$ and $\sigma$ modulo $d>1$, then apply our observations to find an element of $S_n$ which cannot be in $\langle \tau, \sigma \rangle$.

Define $\theta:\langle \tau,\sigma \rangle\rightarrow S_d$ by $\theta(g)=\theta_g$, where $\theta_g(i)=g(i)\mod d$. We must verify that $\theta$ really is a function, that is, that $\theta_g$ is a well-defined permutation in $S_d$ for every $g\in\langle \tau,\sigma \rangle$. By closure in $S_d$ we have that if $\theta_g$ and $\theta_h$ are well defined, then $\theta_g\theta_h=\theta_{gh}$ is as well, so it suffices to check only $\theta_\tau$ and $\theta_\sigma$. In the former case, the assertion is obvious, as $b\equiv a \pmod{d}$ by definition of $d$ and vice versa. In the latter case, we observe that because $d\mid n$, $$i\equiv j \pmod d \Leftrightarrow i+1\equiv j+1\pmod d.$$ Thus $\theta$ is in fact a function (and, moreover, a homomorphism) into $S_d$.

We now use make use of the assumption that $d>1$. Pick a transposition $(ij)\in S_n$ where $i\not\equiv j \pmod d$. By design, $\theta_{(ij)}$ fails to be well-defined, so we must have that $(ij)$ is not in the domain of $\theta$ - that is $(ij)\notin \langle \tau,\sigma \rangle$. In particular, this means that $\langle \tau,\sigma \rangle$ is proper in $S_n$.

Corollary. $S_n$ is generated by any combination of a transposition and an $n$-cycle if and only if $n$ is prime.

Proof. If $n$ is prime, everything's coprime to $n$. Conversely, let $p$ be a prime factor of $n$ and apply the proposition to $\tau=(12),\sigma=(a_1a_2\ldots a_n)$ with $a_1=1$ and $a_{p+1}=2$.