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 = <x, y> .

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} is an orbit, and so is {6, 7}. These sets are thus blocks for the set of permutations G.

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:

graph

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 .

graph21

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!

Advertisements

Responses

  1. 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! 😉


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: