**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 on the symbols {1, 2, 3}, then you can generate this symmetric group with two cycles: (12), and (123). This is easy to show:

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 and let by an arbitrary nonidentity element. Then there exists an element such that .

Basically, this theorem states that as long as you’re not working with , you can choose an arbitrary element (other than the identity, because raising that to powers won’t get you anywhere!), and there will be another element that works with 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 is the whole group . Jordan’s Theorem is a shortcut to figure out if you have such a subgroup $ latex G $:

**Theorem (Jordan). **Suppose that is a primitive subgroup of .

(a) If contains a transposition, then .

(b) If contains a 3-cycle, then or .

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

**Primitive Subgroups**

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

Now think of as acting on . According to this paper, “ is called the **translate** of under the permutation .” Here’s an example: say we’re working with and let =(12) and ={1,2}. Then the translate of under the permutation 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 . Let = {(12), e} and keep the same = {1, 2} from the above problem. is a block for because for each x (i.e., (12) and the identity), the translate is either disjoint from or equal to . Check it out: In both cases, the translate contains 1 and 2, so since ={1, 2}, both translates are equal to . Thus, for this example, we have and the conditions for the block are satisfied.

If 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 the whole set , 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:

= {1, 2, 3}.

Consider = {(123), (132), e}, so .

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

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

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

So, in this case, is a trivial block.

Now that you understand blocks, we can finally define a **primitive** group : a group for which the only blocks are trivial (i.e., singletons, or the entire set of elements, ). 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 , 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 ! (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 , 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 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 is a primitive subgroup of .

(a) If contains a transposition, then .

(b) If contains a 3-cycle, then or .

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 of permutations and an undirected graph. In this proof, each transposition in connects the graph vertices that represent the elements being permuted. For example, (12) looks like this:

The groups of connected vertices are blocks for , and the proof seeks to show that they are permuted by the elements of . 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 and be vertices of the graph, and let and be acted upon by , a permutation in , and let (123). Then what we want is for , 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 .

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

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

Let’s look at an easy example of part (a) of Jordan’s Theorem put into practice. Consider the subgroup , and then let G = (what else?) {(12), e}. Clearly, 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 is primitive and contains a transposition, then . does indeed contain the transposition (12), and is also equivalent to .

A slightly more interesting example of part (b) of Jordan’s Theorem is the primitive subgroup {(123), (132), e} . 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 or . The latter is true; indeed, this subgroup is the set of all even permutations in .

**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!

A great question: what subset of S_n generates the whole group? Surprisingly, given any one element, you need pick only one more, if you choose correctly! A very nice result by itself, but you took an interest also in a particular part of the proof and the method used for that part. It leads me to wonder — is this method useful elsewhere? The idea of putting information into graphs in order to organise it for a proof is actually used often and it makes for particularly appealing proofs. So I’m glad you liked this one. I also enjoyed working on the math in office hours with you.

And awesome drawings, by the way! 😉

By:

Prof. Kateon January 13, 2009at 9:37 pm