Transitive Subgroup of Prime containing Transposition

From ProofWiki
Jump to navigation Jump to search


Let $p$ be a prime number.

Let $S_p$ denote the symmetric group on $p$ letters.

Let $H$ be a transitive subgroup of $S_p$.

If $H$ contains a transposition, then $H = S_p$.


Without loss of generality, let $\tuple {1, 2}$ be the transposition contained by $H$.

Let us define an equivalence relation $\sim$ on the set $\N_p = \set {1, 2, \ldots, p}$ as:

$i \sim j \iff \tuple {i, j} \in H$

Because $H$ is a transitive subgroup it follows that each $\sim$-equivalence class has the same number of elements.

In fact, if $\phi \in H$ and $\phi_1 := \map \phi 1 = i$, then $\phi$ yields a bijection from the $\sim$-equivalence class of $1$ to that of $i$, because:

$\tuple {1, k} \in H \iff \tuple {i, \phi_k} = \tuple {\phi_1, \phi_k} = \phi \circ \tuple {1, k} \circ \phi^{-1} \in H$

The number $s$ of elements of any given $\sim$-equivalence class must be a divisor of $p$.

Thus $s = 1$ or $s = p$.

However, the $\sim$-equivalence class of $1$ contains at least both $1$ and $2$.

So there can be only one $\sim$-equivalence class which then contains $p$ elements.

In other words, $H$ contains all the transpositions of $S_p$.

From Existence and Uniqueness of Cycle Decomposition, every permutation is a composition of transpositions.


$H = S_p$