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.



This article needs to be linked to other articles.
In particular: throughout
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
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 {{MissingLinks}} 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 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.


This article, or a section of it, needs explaining.
In particular: The above statement is incomprehensible. Please check the grammar.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
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 {{Explain}} from the code.


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

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$

$\blacksquare$


Sources

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