How does $(12\dots n)$ and $(a\, b)$ generate $S_n$? [duplicate]

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

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

Can you somehow get to $(1\,2)$ or reduce it to some other previous case?

Solution 1:

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

Solution 2:

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

Solution 3:

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.