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: and generate if, and only if and are relatively prime.

A partial sketch of proof (of the sufficiency):

You can first prove that and always generate by showing that they generate the transpositions , and then any transposition (note that if I'm not mistaking).

If and are relatively prime, it suffices to show that is in the group generated by and . The idea is very similar to the proof of the first case. Let . First show that you can get the transpositions , and then find 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.