Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know that $S_n$ is generated by a number of things, like all transpositions, all transpositions of form $(1a)$, the transpositions $(12),(23),(34),\cdots(n-1n)$, and just the two elements $(123\cdots n),(12)$.

Suppose $n$ is prime. If you just have $(123\cdots n)$ and some arbitrary transposition $(ab)$, how does this also generate $S_n$?

Can you somehow get to $(12)$ or reduce it to some other previous case?

share|improve this question
1  
I think you have to assume that $n$ is prime. –  Dylan Moreland Sep 15 '11 at 18:26
    
My mistake, let me add that. –  groops Sep 15 '11 at 18:28

3 Answers 3

up vote 11 down vote accepted

If $n$ is composite (as in the initial version of the question): not necessarily. For example, $(1234)$ and $(24)$ cannot generate $S_4$, because both preserve the property that odd elements are next to evens and vice versa.

On the other hand, if $n$ is prime then it does always work. If $x$ is an arbitrary $p$-cycle and $(ab)$ an arbitrary transposition, then let $k$ be the distance between $a$ and $b$ in $x$. Now $x^k$ either takes $a$ to $b$ or $b$ to $a$ (depending on which way we count), and $x^k$ must still be a $p$-cycle (it cannot be the identity unless $a=b$, and its order has to divide the order of $x$). So a simple relabeling of the positions gets us back to the case $(123\cdots p), (12)$.

share|improve this answer
    
Sorry, Dylan Moreland pointed out the missing hypothesis that $n$ is prime. My mistake. –  groops Sep 15 '11 at 18:30
    
Thanks! ${}{}{}$ –  groops Sep 16 '11 at 22:24

Try to prove that $(123\dots n)$ and $(ab)$ generate $S_n$ if and only if $\text{gcd}(|a-b|,n)=1$.

In particular, for $n$ prime, this shows that every transposition $(ab)$ and cycle $(12\dots n)$ generate $S_n$.

share|improve this answer

Another slightly different way of looking at it for $n = p$ a prime, if you prefer:

Let $\sigma = (12 \ldots p)$. Then $\sigma (ab) \sigma^{-1} = (\sigma(a) \sigma(b)) = (a+1 \ \ b+1)$. Continuing, we generate all transpositions of the form $(a+k\ \ b+k$) (working modulo $p$). Let $t = b - a$, and we see we have all transpositions of the form $(a \ \ a+t)$. Given any $c,d \in \{0 , \ldots , p-1 \}$, there is an $s$ such that $c + st = d \ (\mathrm{mod} \ p)$ (specifically $s = t^{-1}(c-d)$, which always exists as $\mathbb Z / p \mathbb Z$ is a field; this wouldn't work if $n$ wasn't prime). So we have generated all transpositions, and so the whole group.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.