Posted by: elenadbutler | November 18, 2008

## Reading Project: Generating Symmetric Groups

Introduction

In our class, we’ve talked a lot about groups that can be generated by a single element raised to successive powers. This paper by I. M. Isaacs and Thilo Zieschang takes the concept a step further: they discuss and prove theorems about how to generate symmetric groups by choosing two elements from that group. For example, if you consider the symmetric group $S_3$ on the symbols {1, 2, 3}, then you can generate this symmetric group with two cycles: (12), and (123). This is easy to show:

$(12)=(12), (12)^2=e, (123)=(123), (123)^2=(132), (12)(123)=(23), (12)(123)^2=(13).$

Not sure you could come up with elements to generate a group? Isaacs and Zieschang write about some nifty and helpful rules for picking generators, including the main theorem in this paper, Theorem A:

Theorem A. Assume that $n\neq4$ and let $x \in S_n$ by an arbitrary nonidentity element. Then there exists an element $y \in S_n$ such that $S_n = $.

Basically, this theorem states that as long as you’re not working with $S_4$, you can choose an arbitrary element $x$ (other than the identity, because raising that to powers won’t get you anywhere!), and there will be another element $y$ that works with $x$ to generate your symmetric group!

Before they can prove Theorem A, the authors introduce a new and (they think) slicker proof of Jordan’s Theorem, which was discovered in 1870 by (surprise!) C. Jordan. Instrumental in the proof of Theorem A is being able to tell when a subgroup $G$ $\subseteq$ $S_n$ is the whole group $S_n$. Jordan’s Theorem is a shortcut to figure out if you have such a subgroup $latex G$:

Theorem (Jordan). Suppose that $G$ is a primitive subgroup of $S_n$.

(a) If $G$ contains a transposition, then $G = S_n$.

(b) If $G$ contains a 3-cycle, then $G = S_n$ or $G = A_n$.

The key word here is primitive subgroup. What is a primitive subgroup? Good question!

Primitive Subgroups

Consider the set of elements $\Omega$={1, 2, 3, …, n}.  Remember, $\Omega$ is a set of numbers. Then let $x \in S_n$. So remember, $x$ is a permutation. (I got confused about this a lot when I was reading the paper, so consider yourself warned.) Now we have $\Delta \subseteq \Omega$. (So, $\Delta$ is set of numbers!)

Now think of $\Delta x \subseteq \Omega$ as $x$ acting on $\Delta$. According to this paper, “$\Delta x$ is called the translate of $\Delta$ under the permutation $x$.” Here’s an example: say we’re working with $S_3$ and let $x$=(12) and $\Delta$={1,2}. Then the translate of $\Delta$ under the permutation $x$ is {2, 1}, because ((12) carries 1 to 2 and e carries 1 to itself.

Now I introduce another concept: the block. Consider the subgroup $G \in S_3$. Let $G$ = {(12), e} and keep the same $\Delta$= {1, 2} from the above problem. $\Delta$ is a block for $G$ because for each x (i.e., (12) and the identity), the translate is either disjoint from or equal to $\Delta$. Check it out: In both cases, the translate contains 1 and 2, so since $\Delta$={1, 2}, both translates are equal to $\Delta$. Thus, for this example, we have $\Delta x = x$ and the conditions for the block are satisfied.

If $\Delta$ contains only one element, the conditions for a block will always be satisfied, sine a permutation acting on a single element will either give that element or an element disjoint from it. Likewise, if $\Delta =$ the whole set $\Omega$, the conditions will be satisfied. These blocks are pretty boring, so they’re called trivial blocks. Let’s look at an example of the latter kind of trivial block:

$\Delta = \Omega$ = {1, 2, 3}.

Consider $x$ = {(123), (132), e}, so $x \subseteq S_3$.

Translate #1 (x=(123)):

(123) acting on 1 is 2. (123) acting on 2 is 3. (123) acting on 3 is 1. So, for this translate, $\Delta x = \Delta$.

Translate #2 (x=(132)):

(132) acting on 1 is 3. (132) acting on 2 is 1. (132) acting on 3 is 2. Again, for this translate, $\Delta x = \Delta$.

Translate #3 (x=e):

The identity acting on 1 is 1. The identity acting on 2 is 2. The identity acting on 3 is 3. Again, for this translate, $\Delta x = \Delta$.

So, in this case, $\Delta = \Omega$ is a trivial block.

Now that you understand blocks, we can finally define a primitive group $G$: a group for which the only blocks are trivial (i.e., singletons, or the entire set of elements, $\Omega$). This allows us to move on to the proof of Jordan’s Theorem.

But first, an example of a kind of block that I think is cool.

Orbits

We all know that the planets have orbits, but did you know that if you permute a set of elements, the elements can have orbits too? The permutations of elements under a group of permutations trace out an orbit for each element in $\Omega$, which tells you where that element “travels” as it is permuted. These orbits turn out to be blocks (because they are the results of a group of permutations acting on an element) that decompose $\Omega$! (For more details, read the paper.) This concept is a bit hard to explain, so here’s a drawing:

In this image, {1, 2, 3, 4, 5} and {6, 7}, which decompose $\Omega$, are orbits and blocks for your group because they describe the paths of elements under the permutations in your group. It is not surprising that if your group is primitive, either all orbits are singleton sets (because the only blocks are singletons!) or $\Omega$ itself is the orbit, but again, if you want the details about the relationship between orbits and blocks, I recommend reading through the beginning of this paper!

Jordan’s Theorem

Finally, let’s take a look at Isaacs and Zieschang’s slick proof for Jordan’s Theoerem. The proof is  divided into two parts, one for part (a) and one for part (b).

Theorem (Jordan). Suppose that $G$ is a primitive subgroup of $S_n$.

(a) If $G$ contains a transposition, then $G = S_n$.

(b) If $G$ contains a 3-cycle, then $G = S_n$ or $G = A_n$.

The proof is a bit long, and the two parts of the proof employ a similar sequence of arguments, so I will only discuss part (a). Here’s a summary!

I thought this proof was pretty cool because it uses an isomorphism between the group $G$ of permutations and an undirected graph. In this proof, each transposition in $G$ connects the graph vertices that represent the elements being permuted. For example, (12) looks like this:

The groups of connected vertices are blocks for $G$, and the proof seeks to show that they are permuted by the elements of $G$. We do this by showing that if two vertices are connected in the graph, then they remain connected on the graph when acted upon by a permutation.

To understand this concept, consider the graph below (this is NOT part of the summary of the proof). Let $a$ and $b$ $\in \Omega$ be vertices of the graph, and let  $a=1$ and $b=2$ be acted upon by $g$, a permutation in $G$, and let $g =$ (123). Then what we want is for $(a)g = (b)g$, i.e., the result of (123) acting on (1) is connected to the result of (123) acting on 2. Since 2 and 3 are connected on the graph, we have $(a)g = (b)g$.

Once the authors prove that $(a)g = (b)g$, we recall that (unlike in the image above) $G$ is primitive, so each connected group is either a singleton or the entire set $\Omega$. Since $G$ contains at least one transposition, the singleton option is out, and we know that the graph is connected.

In order to prove that $G$ is the full symmetric group, the authors use proof by contradiction. They assume that two vertices $a$ and $b$ aren’t connected to show that whatever path you choose to get from $a$ to $b$ on the graph, you can always find a shorter path. This is a contradiction, so $a$ and $b$ are connected.

Let’s look at an easy example of part (a) of Jordan’s Theorem put into practice. Consider the subgroup $G \in S_2$, and then let G = (what else?) {(12), e}. Clearly, $G$ is a primitive subgroup — since it only has two elements, its blocks will either be singletons or the pair of elements, i.e., the entire subgroup. According to Jordan’s Theorem, if $G$ is primitive and contains a transposition, then $G = S_n$. $G$ does indeed contain the transposition (12), and is also equivalent to $S_n$.

A slightly more interesting example of part (b) of Jordan’s Theorem is the primitive subgroup {(123), (132), e} $\in S_3$. I leave it to you to show yourself why this is a primitive subgroup, but anyway, this subgroup contains a 3-cycle, so the subgroup should either be equal to $S_3$ or $A_3$. The latter is true; indeed, this subgroup is the set $A_3$ of all even permutations in $S_3$.

Conclusion

If you want to get really good at choosing two permutations that generate a symmetric group, read this paper! I enjoyed hacking through it because it contained a lot of Math 152 concepts, like permutations, sets, groups, conjugation, and graph theory. I got to learn about them in even more depth than we have in the course! Wahoo!