# How does $(12\cdots n)$ and $(ab)$ generate $S_n$?

I know that $S_n$ is generated by a number of things, like all transpositions, all transpositions of form $(1a)$, the transpositions $(12),(23),(34),\cdots(n-1n)$, and just the two elements $(123\cdots n),(12)$.

Suppose $n$ is prime. If you just have $(123\cdots n)$ and some arbitrary transposition $(ab)$, how does this also generate $S_n$?

Can you somehow get to $(12)$ or reduce it to some other previous case?

-
I think you have to assume that $n$ is prime. – Dylan Moreland Sep 15 '11 at 18:26
My mistake, let me add that. – groops Sep 15 '11 at 18:28

If $n$ is composite (as in the initial version of the question): not necessarily. For example, $(1234)$ and $(24)$ cannot generate $S_4$, because both preserve the property that odd elements are next to evens and vice versa.

On the other hand, if $n$ is prime then it does always work. If $x$ is an arbitrary $p$-cycle and $(ab)$ an arbitrary transposition, then let $k$ be the distance between $a$ and $b$ in $x$. Now $x^k$ either takes $a$ to $b$ or $b$ to $a$ (depending on which way we count), and $x^k$ must still be a $p$-cycle (it cannot be the identity unless $a=b$, and its order has to divide the order of $x$). So a simple relabeling of the positions gets us back to the case $(123\cdots p), (12)$.

-
Sorry, Dylan Moreland pointed out the missing hypothesis that $n$ is prime. My mistake. – groops Sep 15 '11 at 18:30
Thanks! ${}{}{}$ – groops Sep 16 '11 at 22:24

Try to prove that $(123\dots n)$ and $(ab)$ generate $S_n$ if and only if $\text{gcd}(|a-b|,n)=1$.

In particular, for $n$ prime, this shows that every transposition $(ab)$ and cycle $(12\dots n)$ generate $S_n$.

-

Another slightly different way of looking at it for $n = p$ a prime, if you prefer:

Let $\sigma = (12 \ldots p)$. Then $\sigma (ab) \sigma^{-1} = (\sigma(a) \sigma(b)) = (a+1 \ \ b+1)$. Continuing, we generate all transpositions of the form $(a+k\ \ b+k$) (working modulo $p$). Let $t = b - a$, and we see we have all transpositions of the form $(a \ \ a+t)$. Given any $c,d \in \{0 , \ldots , p-1 \}$, there is an $s$ such that $c + st = d \ (\mathrm{mod} \ p)$ (specifically $s = t^{-1}(c-d)$, which always exists as $\mathbb Z / p \mathbb Z$ is a field; this wouldn't work if $n$ wasn't prime). So we have generated all transpositions, and so the whole group.

-