Conjecture a necessary and sufficient condition involvingxandnfor (1x) and (123 ...n) to generateSn.

Printable View

- Oct 30th 2008, 07:51 PMsafecrackerpermutations (1x) and (123 ... n) generate Sn
Conjecture a necessary and sufficient condition involving

*x*and*n*for (1*x*) and (123 ...*n*) to generate*Sn*. - Oct 31st 2008, 04:39 AMLaurent
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). - Oct 31st 2008, 09:52 AMsafecracker
Thanks, that makes more sense now.