Alternating Group is Generated by 3-Cycles

From ProofWiki
Jump to navigation Jump to search

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


This article needs to be tidied.
In particular: in due course
Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Tidy}} from the code.


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

Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Alternating_Group_is_Generated_by_3-Cycles&oldid=588202"