Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by safecracker View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Thanks, that makes more sense now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. i need to generate a formula
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 1st 2011, 02:16 PM
  2. how to generate new formulas?
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: Nov 28th 2010, 06:52 AM
  3. generate
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Nov 17th 2010, 10:51 AM
  4. How to generate this?
    Posted in the Geometry Forum
    Replies: 3
    Last Post: Feb 12th 2010, 10:47 AM
  5. generate the set of polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jan 24th 2010, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum