# 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?

• 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
• – Bach Dec 18 '19 at 1:12

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

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.