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$.

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$$.

• 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$). Apr 1 at 23:40

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$

• 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$?
– user733335
Nov 21, 2022 at 4:20
• @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))$ Nov 21, 2022 at 21:58