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

• Oct 30th 2008, 07:51 PM
safecracker
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.
• Oct 31st 2008, 04:39 AM
Laurent
Quote:

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

My conjecture: $(1\ x)$ and $(1\ \cdots\ n)$ generate $S_n$ if, and only if $x-1$ and $n$ are relatively prime.

A partial sketch of proof (of the sufficiency):

You can first prove that $(1\ 2)$ and $(1\ \cdots\ n)$ always generate $S_n$ by showing that they generate the transpositions $(k\ k+1)$, and then any transposition (note that $(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 $n$ and $x-1$ are relatively prime, it suffices to show that $(1\ 2)$ is in the group generated by $(1\ x)$ and $(1\ \cdots\ n)$. The idea is very similar to the proof of the first case. Let $p=x-1$. First show that you can get the transpositions $(k\ (k+p))$, and then find $(1\ 2)$ by composing the previous ones in a neat way (very much like the first case).
• Oct 31st 2008, 09:52 AM
safecracker
Thanks, that makes more sense now.