# Alternating Group is Generated by 3-Cycles

## Theorem

Let $n \in \N$ such that $n \ge 3$.

Let $A_n$ denote the alternating group on $n$ letters.

Then $A_n$ can be generated by the set of $3$-cycles:

$\set {\tuple {1, i, n}: i \in \set {2, 3, \ldots, n - 1} }$

## Proof

Let $B_n$ be the group generated by $\set {\tuple {1, i, n}: i \in \set {2, 3, \ldots, n - 1} }$.

As every $3$-cycle is even, we have:

$B_n \subseteq A_n$

Therefore, we want to prove $A_n \subseteq B_n$.

We shall prove the statement by induction on $n$.

### Basis for the Induction

For $n = 3$ we have:

$\tuple {1, 2, 3}, \tuple {1, 3, 2}, e \in B_3$

This is because:

$\tuple {1, 2, 3}$ is in $B_3$ by hypothesis
$\tuple {1, 3, 2}$ is its inverse
$e$ is the identity.

Therefore:

$A_3 \subseteq B_3$

and:

$A_3 = B_3$

This is the base case.

### Induction Hypothesis

This is our induction hypothesis:

$A_{n - 1} = B_{n - 1}$

### Induction Step

This is our induction step:

Suppose $\pi \in A_n$.

If there exists a number $l$ such that $\map \pi l = l$, $\pi$ fixes $l$ and permutes the other $n - 1$ letters.

So it may be regarded as a member of $A_{n - 1}$ and is in $B_{n - 1} \subset B_n$ by hypothesis.

We may then take $\pi$ to not map any number from its domain to itself.

Now suppose that $\map \pi x = y$ for all $y$ such that $\map \pi y = x$.

As $n \ge 4$, there exist at least two such disjoint pairs of numbers $\tuple {x, y}$.

Without loss of generality, assume they are $\tuple {1, 2}$ and $\tuple {3, n}$.

We may write $\pi = \tuple {1, 2} \tuple {3, n} \pi'$ for some even permutation $\pi'$.

$\pi'$ is a permutation of $n - 4$ letters, so $\pi' \in B_{n - 4}$ by hypothesis ($\pi' = e$ if $n = 4$).

Furthermore:

$\pi = \tuple {1, 2} \tuple {3, n} \pi' = \tuple {1, 3, n} \tuple {1, 2, n} \pi' \implies \pi \in B_n$

We may, then, assume that this is not the case.

Therefore, there exists some number $k$ such that $\map \pi k = l$ for some number $l \ne k$ and such that $\map \pi l$ is distinct from both $k$ and $l$.

Another restriction can be imposed: both $k$ and $l$ are different from $1$.

Truly, if there exists one pair $(x, y)$ such that $\map \pi x = y$, but $\map \pi y \neq x$, then there must exist at least one other pair, otherwise $\pi$ would not be injective.

$\tuple {1, x, y} = \tuple {1, n, y} \tuple {1, x, n}$

so $\forall x, y: tuple {1, x, y} \in B_n$.

Taking into account these assumptions, note that:

$\tuple {1, k, l}, \tuple {1, l, \map \pi l} \in B_n$

and let:

$\alpha_0 = \tuple {1, k, l} \tuple {1, l, \map \pi l} = \tuple {\map \pi l, k, l} \in B_n$.

$\alpha_0^{-1} = \tuple {\map \pi l, l, k} \in B_n$

Now consider $\sigma = \alpha_0^{-1} \pi$.

This permutation satisfies:

$\map \sigma l = \tuple {\map \pi l, l, k} \map \pi l = l$

Therefore, $\sigma$ fixes $l$.

As $\pi$ and $\alpha_0^{-1}$ are both even, so is $\sigma$

Hence we may regard it as an even permutation on $\set {1, 2, \ldots, n} \setminus \set l$.

As such, $\sigma \in A_{n - 1}$ and can be generated by $B_{n - 1}$ by the inductive hypothesis.

Take $\sigma = \alpha_1 \alpha_2 \ldots \alpha_m$ for some $\alpha_1, \alpha_2, \ldots, \alpha_m \in B_{n - 1} \subset B_n$.

Then:

$\alpha_0 \alpha_1 \alpha_2 \ldots \alpha_m = \alpha_0 \sigma = \alpha_0 \alpha_0^{-1} \pi = \pi$

and we have written an $\pi$ as a product of elements of $B_n$.

As $\pi$ was an arbitrary element of $A_n$, we have $A_n \subseteq B_n$ and $A_n = B_n$.