Wednesday, March 7, 2007

classification of finite simple groups

back to top back to best labs summary contents

Here is another static tautological system with simple rules that will give us a surprisingly diverse but not totally chaotic behavior. No dynamics or random input required, though i suppose you could work out the consequences by seting up an iterative system with stochastic input to explore the space and 'discover' all the possible groups... hmmm..

So we can define a mathematical object called a group, in a similar way that we defined prime numbers.

a group is a set of elements with an operator *, that has the following properties:
1) closure: for any two elements in the group (not necessarily different) a, b, a*b, is also an element in the group.
2) the operation is associative: a*(b*c) = (a*b)*c
3) identity element: there exists an element e such that for all elements a in the group, e*a=a*e=a
4) inverses: for every element a, in the group, there exists an element A (the inverse of a), such that a*A=A*a=e

there are lots of examples. the simplest most familiar is the set of integers with addition:

1) x+z is an integer.
2) addition is associative
3) 0 is the additive identity
4) the inverse of x is -x

that's an example of a group with an infinite number of elements.

the next simplest example is NOT familiar but motivated the invention of the idea of groups:

look at a book on your desk. i can rotate it in a number of ways. let's start out simple, just leaving the book flat on the desk. i can rotate it 90deg clockwise, now it faces to the right. i can rotate it 90 again, and if faces towards you. or i could have rotated it 180* clockwise, same result. So lets make that the group operation: 90#90 = 180 means follow a 90* by another 90*. I can rotate it 90* again and get 270*. one more 90 gets me 360 which is the same as no rotation at all or 0*. rotating 90* again gets me 450 but that's the same as 90* so nothing new. looks like our group of elements is 90, 180, 270, 0. is it a group? start combining different rotations. work it out. is it closed? two rotations always result in a rotation in the group?

Arrange your knowlege of the structure of this group in a 'multiplication' table, i'll start it out for you:

#      0    90    180   270

0      0    90    180   270
90    90    180   270  ...

Is it associative? Is 90 #(180#270) =(90#180)#270? what's the identity element? does every rotation have an inverse? 270#what=your identity?

so that's a finite group.

look at this group: remember the imaginary number i, the square root of minus one? the defining feature of i was that i*i=-1. can we make a group? i*-1=-i, i*-i=--1=1, i*1=i. so it's closed: 1, i, -1, -i. does it work? identity? inverses? associative?

now make a table for this one too.

same groups aren't they? the GROUP is the structure itself, an abstraction of the examples of square roots of minus 1 and the physical rotations of books...

can we make different group with 4 elements? how about e,A,B,C with A#A = B#B = C#C = e. now fill in the table. let's let A#B=C. now what is A#C=? well, if A#B=C then A#(A#B)=A#C, now we use the associative property, so (A#A)#B=A#C and now we use the fact that A is its own inverse: e#B=A#C, and identity property: B=A#C. so A#C = B! see how the 3 properties create the structure of the group. now you can fill in the rest of the group using these games and see if it is all consistant. is it a different group than our first two?

now comes fun. how many groups can you think up with ONE element. what does the element have to be?

how about groups with two elements? e, A. what must A#A be?

groups with three elements? do we have some choices?

and four elements...

Are there any patterns? There are certain classes of these finite groups. For instance our first example of group size 4, is a member of the class of cyclic groups of order n: for any n, use 0,1,2...,n-1 as your group elements and use addition as your operation. but it's not closed! (n-1)+1 is not in the group! so adjust the addition to work modulo n, i.e. (n-1)+1=0, (n-1)+2=1, etc.. check to see that 0,1,2,3 with that operation makes yet another group that is the same structure as our first 2 groups of size 4.

another class of groups is the group of permutations of n objects. work it out for 3 objects: From (abc) you can make (acb) (that's a flip of two letters), (bac) (another flip), (bca) (that's a rotation from front to back)... There are 6 possible permutations in all. The group operation is to follow one permutation by another, like our rotations of the book. For instance (acb ) followed by (bac) is: start with (abc) then flip the last two letters: (acb) . then flip the first two letters: (cab) . There is yet another element of the group: flipping the first and last letter! Don't forget the identity element: (bac) followed by (abc) is (bac). (abc) is do nothing, like rotate 0 degrees. Did you find all 6 permutations? Now arrange them in a big 6X6 multiplication table. And work out all the multiplications. If you arrange them in the right order, you will see a nice pattern.

It would take quite alot of exploration to find All the different kinds of groups we can make with 6 elements! The permuation group is certainly different than the cyclic group modulo 6!

So we start getting all kinds of cool structures and patterns, how does all this structure come out of our very simple abstract definition of a group? it's like the structure that comes out of our simple definition of prime numbers, or the structures that come out of our simple definitions of the behavior of conway life.

neat, huh?

like prime numbers there are certainly infinitely many finite groups, for instance the cyclic groups of order n form one such class. now we know that there are infinitely many primes, but we can't really get a handle on just what numbers they all are, there's not quite a pattern...

So, can we work out all the possible groups for each size n? Is there any pattern? One tool is to look at not just any groups, but just as we can factor numbers into primes and generate all the numbers by multiplying primes, we can factor groups We factor them into what are called simple groups, the 'primes' of groups. the cyclic group of element 4 we found was a simple group. the one with A#A = B#B = C#C = e, is not. it 'factors'. How to do this will get us too far afield, but you can look it up in a book about group theory. It's a little wild!

Nevertheless, as the size of the simple group gets bigger there are more and more different kinds for each size, or are there? Does the diversity of simple groups keep growing chaotically for bigger and bigger size? NO! we have classified ALL the finite simple groups, as the size goes to infinity the number of different kinds of groups of each size does keep growing, it settles down. the diversity of groups is interesting but settles down to a FINITE number of classes. There are in fact only 18 infinite classes of finite simple groups. That means that for each class, there are bigger and bigger groups that share the structure of the class. The cyclic groups is one such class. So that's that, right? No! There were also found to be 26 other sporadic simple groups that did not fit into these classes, and the largest one of these has
808,017,424,794,512,875,886,459,904,961,710,757,005,754,368,000,000,000 elements in it! It is appropriately called "the monster"! 

Where on earth in our definition of a group, did this crazy beast come from? And why do the sporadic groups go on up to the 26th one and then no others can be formed? 

Here is yet another example, like the 96 stable elements in the periodic chart of a simple system with simple laws giving us a surprisingly diverse but not totally chaotic array of behaviors.

This is a fascinating recent result of mathematics. By the way, working it all out and writing up the proofs that we got all the groups takes up about 10,000 pages of math journals! There are only a few mathematicians in the world who have a grasp the whole result.

Here is some more information on this result:

And here is an advanced summary:

Here is a nice video describing groups and some clips of John Horton Conway (who worked with the monster) describing how much this puzzle disturbs him!

No comments: