Prove that if $\alpha$ is any cycle of length $n$, and $\beta$ is any transposition, then ${\alpha, \beta}$ generates $S_n$

180 Views Asked by At

questions

Question 6 from the above set of exercises has me a bit stumped. I see that you can rotate then relabel $\alpha = (a_1 a_2 \cdots a_n)$ such that $\alpha = (1 2 \cdots n)$ and $\beta = (1 m)$ — that almost makes the problem reducible to the result of question 5, but not quite, since we do not know that $m = 2$, and this fact is crucial in the proof for question 5. I would appreciate any tips.

1

There are 1 best solutions below

10
On BEST ANSWER

Statement 6 is not true as stated. For example, $(1\ \ 3)$ and $(1\ \ 2\ \ 3\ \ 4)$ fail to generate $S_4$. In particular, the subgroup generated by these two elements is isomorphic to the dihedral group $D_4$ of order $8$.


In fact, we can see that for $n>2$, $\alpha = (1\cdots n)$ and $\beta = (1\ \ m)$ will generate $S_n$ if and only if $n$ and $m-1$ are coprime.

For the $\Longleftarrow$ direction, it suffices to repeat the construction in the hint for part 5.

In particular, we have $$ \alpha^{m-1}(1\ \ m)\alpha^{1 - m} = (m\quad 2m - 1), \quad (1\ \ m)(m\quad 2m - 1)(1 \ \ m) = (1\ \ 2m - 1). $$ Here, $2m - 1$ is taken modulo $n$, as are any further operations here. With that, we have constructed every transposition of the form $(1\quad 1 + k(m-1))$. However, because $m-1$ and $n$ are relatively prime, we see that every element of $\{0,1,\dots,n-1\}$ can be written in the form $k(m-1)$ for some $k$. So, we have constructed every transposition of the form $(1\ \ k)$ (for $k \in \{1,\dots,n\}$), which was precisely the point of the hint.

For the $\implies$ direction: let $d = \gcd(m-1,n)$. Note that $\alpha, \beta$ have the property that whenever $i \equiv j \pmod d$, then it holds that $\alpha(i) \equiv \alpha(j)$ and $\beta(i) \equiv \beta(j)$, modulo $d$. It follows that every element of the subgroup generated by $\alpha$ and $\beta$ also has this property. We therefore see that the subgroup generated by $\alpha$ and $\beta$ does not include all of $S_n$ because, for instance, the element $(1\ \ 2)$ does not have this property.