# 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: \$\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 AM
safecracker
Thanks, that makes more sense now.