10
$\begingroup$

I want to solve the following:

Let $p$ be a prime number and let $a$ be a $p$-cycle in $S_p$, and let $b$ be a transposition in $S_p$. Show $S_p$ is generated by $a$ and $b$.

My attempt

Write $a=(y_1 \space y_2 \space ...\space y_p)$ and $b=(z_1 \space z_2)$. WLOG, $y_1=z_1=1$. WLOG, we can also assume $a=(1 \space 2 \space ... \space p).$

Let $σ\in S_p$. It should be obvious that $σ$ is a product of transpositions, so to show $σ \in S_p$, it suffices to show every transposition can be written in terms of $(1 \space 2 \space ... \space p)$ and $(1 \space z_2)$. But how do I show this?

Duplicate? I think not.

Although another question (already answered on math.SE) is similar to mine, I do not believe that mine is a duplicate. The other question is equivalent to mine only for the special case when $z_2=2$, but not for general $z_2$.

$\endgroup$
1
  • $\begingroup$ Although this has long since been answered, it really is equivalent to the version with $z_2 = 2$, as can be seen by conjugating everything by $(2\ z_2)$ if $z_2 \ne 2$ (just as you assumed WLOG that $y_1 = z_1 = 1$). $\endgroup$
    – LSpice
    Apr 1 at 23:40

1 Answer 1

13
$\begingroup$

To use in a simpler typographic matter the fact that $p$ is a prime, let us use the symbols $0,1,2,\dots(p-1)$ to be permuted. We have to show that the cycle $c$ and a transposition $$ \begin{aligned} c &= (0,1,2\dots,(p-1))\ ,\\ t &= (0,a)\ ,\ a\ne 0\ ,\ a\in \Bbb F_p\ , \end{aligned} $$ are generating the full permutation group. Let $G$ be the group generated by $c,t$.

We conjugate $t$ with $c$, so all transpositions $(k, k+a)$ are in $G$.

So $(0,a)$, $(a,2a)$, $(2a,3a)$, $\dots$ are in $G$.

We stop the above at the $b$-value, ($b$ is both seen in $\Bbb Z$ and in $\Bbb F_p$, depending on context,) so that $ab=1$ in $\Bbb F_p$.

Now, using $$(0,a), \ (a,2a), \ (2a,3a),\ \dots\ ((b-1)a,1)$$ we can produce iteratively $$(0,a), \ (0,2a),\ (0,3a),\ \dots\ (0,\underbrace{1}_{ba})\ .$$ (For instance, $(0,a)(a,2a)(0,a)=(0,2a)$.) Finally, $c$ and $(0,1)$ are standard generators for the full symmetric group.

$\blacksquare$

$\endgroup$
2
  • $\begingroup$ how's that you can write $t$ and $c$ both starting at $0$? What you're doing when you re-write $c$ is basically to stabish a permutation on $\{1,2,\dots, n\}$, but given a random transposition $(i,j)$ how can you garantee that the same permutation sends $i$ to $0$? $\endgroup$
    – user733335
    Nov 21, 2022 at 4:20
  • $\begingroup$ @SamHaze $c$ and $t$ are permutations of a set of symbols, which we may assume are not numbers first, we intentionally want to avoid integers at this step. Then pick a symbol among the two symbols in the transposition. Now write the $p$-cycle to start with the same symbol as a cycle, and use a new notation using integers $0,1,2,\dots$ instead of the symbols, replacing the symbols in order so that the cycle becomes $(0,1,2,3,\dots,(p-1))$ $\endgroup$
    – dan_fulea
    Nov 21, 2022 at 21:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .