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$ 
:$\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$ .
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}$.
, 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}$ ($\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$.
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:
:$\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$
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$.
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 some arbitrary $\pi \in A_n$ as a product of elements of $B_n$.
As $\pi$ was arbitrary, we have:
:$A_n \subseteq B_n$ 
and:
:$A_n = B_n$
== Sources ==
* : Chapter $2$: The Symmetric Groups: $\S 82 \alpha$
Category:Alternating Groups
Category:Examples of Generators of Groups