# 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 definitionally in $B_3$, $\tuple {1, 3, 2}$ is its inverse and $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 \geq 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 \neq 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.

Additionally, note that $\tuple {1, x, y} = \tuple {1, n, y} \tuple {1, x, n}$, so $\tuple {1, x, y} \in B_n; \forall x, y$.

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$. Additionally, $\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$, and 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 is 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$.

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