# Thread: permutations (1x) and (123 ... n) generate Sn

1. ## permutations (1x) and (123 ... n) generate Sn

Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.

2. Originally Posted by safecracker
Conjecture a necessary and sufficient condition involving x and n for (1x) and (123 ... n) to generate Sn.
My conjecture: $\displaystyle (1\ x)$ and $\displaystyle (1\ \cdots\ n)$ generate $\displaystyle S_n$ if, and only if $\displaystyle x-1$ and $\displaystyle n$ are relatively prime.

A partial sketch of proof (of the sufficiency):

You can first prove that $\displaystyle (1\ 2)$ and $\displaystyle (1\ \cdots\ n)$ always generate $\displaystyle S_n$ by showing that they generate the transpositions $\displaystyle (k\ k+1)$, and then any transposition (note that $\displaystyle (1\ k)=(1\ 2)(2\ 3)\cdots(k-2\ k-1)(k-1\ k)(k-2\ k-1)\cdots(2\ 3)(1\ 2)$ if I'm not mistaking).

If $\displaystyle n$ and $\displaystyle x-1$ are relatively prime, it suffices to show that $\displaystyle (1\ 2)$ is in the group generated by $\displaystyle (1\ x)$ and $\displaystyle (1\ \cdots\ n)$. The idea is very similar to the proof of the first case. Let $\displaystyle p=x-1$. First show that you can get the transpositions $\displaystyle (k\ (k+p))$, and then find $\displaystyle (1\ 2)$ by composing the previous ones in a neat way (very much like the first case).

3. Thanks, that makes more sense now.