Why is $S_5$ generated by any combination of a transposition and a 5-cycle? Is this true for any prime $p$ (in this case $p=5$)?

up vote 18 down vote accepted

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.