[New release, HaskellForMaths-0.1.9, available here. Contains documentation improvements, new version of graphAuts using equitable partitions, and the code used in this blog post.]
Over the last few months on this blog, we have been looking at symmetry. We started out by looking at symmetries of graphs, then more recently we've been looking at symmetries of finite geometries. Last time, I said that there was more to say about finite geometries. There is, but first of all I realised that I need to say a bit more about groups.
We've come across groups already many times. Whenever we have an object, then the collection of all symmetries of that object is called a group. (Recall that a symmetry is a change that leaves the object looking the same.) Suppose that we call this group G, and arbitrary elements in the group g and h. Then G satisfies the following properties:
- There is a binary operation, *, defined on G. (g*h is the symmetry that you get if you do g then h.)
- If g and h are in G, then so is g*h. (Doing one symmetry followed by another is again a symmetry.)
- There is an element 1 in G, the identity, such that 1*g = g = g*1. (1 is the symmetry "do nothing".)
- If g is in G, then there is an element g^-1 in G, called the inverse of g, such that g*g^-1 = g^-1*g = 1. (Doing g^-1 is the same as undoing g.)
- (g*h)*k = g*(h*k)
Mathematicians sometimes (usually) turn things the other way round: They define a group by the properties above, and then observe that the collection of symmetries of an object fits the definition. The problem with this is that it covers over the original intuitions behind the concept.
For us, the key point to take away from the definition is that groups are "closed". We've been looking at symmetries, represented by permutations. But symmetries and permutations just are the sort of thing that you can multiply (do one then another), that have an identity (do nothing), and that have inverses (undo). Those all come for free. So when we say that a collection of symmetries, or of permutations, is a group, the only new thing that we're claiming is that the collection is closed - for g, h in G, g*h, g^-1, and 1 are also in G.
Okay, so now we know what a group is. Now you know what mathematicians are like - as soon as they've discovered some new type of structure, they always ask themselves questions like the following:
- can we classify all structures of this type?
- can smaller structures of this type be combined into larger structures of the same type?
- can larger structures of this type be broken down into smaller structures?
- can we classify all "atomic" structures of this type, that can't be broken down any further?
What about groups? Well, the answer is, for finite groups, mostly yes. Specifically, groups are made out of "atoms" - but there isn't a complete understanding of all the different ways they can be built from the atoms. Anyway, for the moment I'm going to skip the first two questions (about building groups up), and concentrate on the last two (breaking them down).
Okay, so can groups be broken down into smaller groups? Well, groups can have smaller groups contained within them. For example, let's consider the group D10 - the symmetries of the pentagon. (Somewhat confusingly, it's called D10 rather than D5, because it has 10 elements.)
> :load Math.Algebra.Group.PermutationGroup
> mapM_ print $ elts $ _D 10
[]
[[1,2],[3,5]]
[[1,2,3,4,5]]
[[1,3,5,2,4]]
[[1,3],[4,5]]
[[1,4],[2,3]]
[[1,4,2,5,3]]
[[1,5,4,3,2]]
[[1,5],[2,4]]
[[2,5],[3,4]]
Now, any subset of these elements, which is closed, is again a group. For example, the set { [], [[1,2],[3,5]] } is closed - 1, and all products and inverses of elements in the set, are in the set. This is called a subgroup of D10.
Here's Haskell code to find all subgroups of a group. (The group is passed in as a list of generators, and the subgroups are returned as lists of generators.)
> subgps gs = [] : subgps' S.empty [] (map (:[]) hs) where
> hs = filter isMinimal $ elts gs
> subgps' found ls (r:rs) =
> let ks = elts r in
> if ks `S.member` found
> then subgps' found ls rs
> else r : subgps' (S.insert ks found) (r:ls) rs
> subgps' found [] [] = []
> subgps' found ls [] = subgps' found [] [l ++ [h] | l <- reverse ls, h <- hs, last l < h]
> -- g is the minimal elt in the cyclic subgp it generates
> isMinimal 1 = False
> isMinimal g = all (g <=) primitives -- g == minimum primitives
> where powers = takeWhile (/=1) $ tail $ iterate (*g) 1
> n = orderElt g -- == length powers + 1
> primitives = filter (\h -> orderElt h == n) powers
By the way, most of the code we'll be looking at this week, including the above, should only be used with small groups.
Okay, so let's try it out:
> mapM_ print $ subgps $ _D 10
[]
[[[1,2],[3,5]]]
[[[1,2,3,4,5]]]
[[[1,3],[4,5]]]
[[[1,4],[2,3]]]
[[[1,5],[2,4]]]
[[[2,5],[3,4]]]
[[[1,2],[3,5]],[[1,2,3,4,5]]]
The last in the list is D10 itself, generated by a reflection and a rotation. Then there are five subgroups generated by five different reflections. (For example, recall that [[2,5],[3,4]] is the reflection that swaps 2 with 5, and 3 with 4 - in other words, reflection in the vertical axis.). Then there is also a subgroup generated by the rotation [[1,2,3,4,5]] - the clockwise rotation that moves 1 to 2, 2 to 3, 3 to 4, 4 to 5, and 5 to 1. Finally, [] is the subgroup with no generators, which by convention is the group consisting of just the single element 1.
So can we break a group down into its subgroups? Well, not quite. When we break something down, we should end up with two (or more) parts. Subgroups are parts. But we may not always be able to find another matching part to make up the group.
I'm probably being a bit cryptic. Let's consider an analogy. We know that 15 = 3*5. We also have 5 = 15/3. So 15 = 3 * (15/3). Given a group G, and a subgroup H, we would like to be able to build G as G = H * (G/H). I'm not going to dwell on the * in this statement. What about the / ?
Well, it turns out that we can form a quotient G/H of a group by a subgroup - but only if the subgroup satisfies some extra conditions.
Given any subsets X and Y of G, we can define a product XY:
> xs -*- ys = toListSet [x*y | x <- xs, y <- ys]
For X or Y consisting of just a single element, we can form the products xY = {x}Y, or Xy = X{y}:
> xs -* y = L.sort [x*y | x <- xs] -- == xs -*- [y]
> x *- ys = L.sort [x*y | y <- ys] -- == [x] -*- ys
Now it turns out that we can use this multiplication to define a quotient G/H. We let the elements of G/H be the (right) "cosets" Hg, for g in G. For example:
> let hs = [1, p [[1,2],[3,5]]]
> let x = p [[1,2,3,4,5]]
> let y = p [[2,5],[3,4]]
> hs -* x
[[[1,2,3,4,5]],[[1,3],[4,5]]]
> hs -* y
[[[1,5,4,3,2]],[[2,5],[3,4]]]
Here we have taken a subgroup H in D10, and then found the cosets Hx, Hy, for a couple of elements x, y in D10.
Now, to get our quotient group working, what we'd like is to have (Hx) (Hy) = H(xy). Unfortunately, this isn't guaranteed to be true. For example:
> (hs -* x) -*- (hs -* y)
[[],[[1,2],[3,5]],[[1,4,2,5,3]],[[1,5],[2,4]]]
> hs -* (x*y)
[[[1,4,2,5,3]],[[1,5],[2,4]]]
Oh dear. But there are some subgroups for which this construction does work. Suppose that we had a subgroup K, such that for all g in G, g^-1 K g = K. Then Kx Ky = Kx (x^-1Kx)y = KKxy = Kxy. (KK=K follows from the fact that K is a subgroup, hence closed.)
A subgroup K of G such that g^-1 K g = K for all g in G is called a normal subgroup. For a normal subgroup, we can form the quotient G/K, and so we have broken G down into two parts, K and G/K.
Here's the code:
> isNormal gs ks = all (== ks') [ (g^-1) *- ks' -* g | g <- gs]
> where ks' = elts ks
> normalSubgps gs = filter (isNormal gs) (subgps gs)
> quotientGp gs ks
> | ks `isNormal` gs = gens $ toSn [action cosetsK (-* g) | g <- gs]
> | otherwise = error "quotientGp: not well defined unless ks normal in gs"
> where cosetsK = cosets gs ks
> gs // ks = quotientGp gs ks
For example:
> mapM_ print $ normalSubgps $ _D 10
[]
[[[1,2,3,4,5]]]
[[[1,2],[3,5]],[[1,2,3,4,5]]]
Two of these are "trivial". [] is the subgroup {1}, which will always be normal. The last subgroup listed is D10 itself. A group will always be a normal subgroup of itself. So the only "proper" normal subgroup is [ [[1,2,3,4,5]] ] - the subgroup of rotations of the pentagon.
In this case, there are only two cosets:
> mapM_ print $ cosets (_D 10) [p [[1,2,3,4,5]]]
[[],[[1,2,3,4,5]],[[1,3,5,2,4]],[[1,4,2,5,3]],[[1,5,4,3,2]]]
[[[1,2],[3,5]],[[1,3],[4,5]],[[1,4],[2,3]],[[1,5],[2,4]],[[2,5],[3,4]]]
Not surprisingly then, the quotient group is rather simple:
> _D 10 // [p [[1,2,3,4,5]]]
[[[1,2]]]
Just to explain a little: In quotientGp gs ks, we form the cosets of ks, and then we look at the action of the gs on the cosets by right multiplication - g sends Kh to Khg. So the elements of the quotient group are permutations of the cosets. However, if we printed this out, it would be hard to see what was going on. So we call "toSn", which labels the cosets 1,2,..., and rewrites the elements as permutations of the numbers. In the case above, we see that the quotient group can be generated by a single element, which simply swaps the two cosets.
Let's look at another example. S 4 is the group of all permutations of [1..4] - which also happens to be the symmetry group of the tetrahedron. S 4 has lots of subgroups:
> mapM_ print $ subgps $ _S 4
[]
[[[1,2]]]
[[[1,2],[3,4]]]
[[[1,2,3]]]
[[[1,2,3,4]]]
[[[1,2,4,3]]]
[[[1,2,4]]]
[[[1,3],[2,4]]]
[[[1,3,2,4]]]
[[[1,3]]]
[[[1,3,4]]]
[[[1,4],[2,3]]]
[[[1,4]]]
[[[2,3]]]
[[[2,3,4]]]
[[[2,4]]]
[[[3,4]]]
[[[1,2]],[[1,2],[3,4]]]
[[[1,2]],[[1,2,3]]]
[[[1,2]],[[1,2,3,4]]]
[[[1,2]],[[1,2,4]]]
[[[1,2]],[[1,3],[2,4]]]
[[[1,2],[3,4]],[[1,2,3]]]
[[[1,2],[3,4]],[[1,2,3,4]]]
[[[1,2],[3,4]],[[1,2,4,3]]]
[[[1,2],[3,4]],[[1,3],[2,4]]]
[[[1,3],[2,4]],[[1,3]]]
[[[1,3]],[[1,3,4]]]
[[[1,4],[2,3]],[[1,4]]]
[[[2,3]],[[2,3,4]]]
However, only a few of them are normal:
> mapM_ print $ normalSubgps $ _S 4
[]
[[[1,2]],[[1,2,3,4]]]
[[[1,2],[3,4]],[[1,2,3]]]
[[[1,2],[3,4]],[[1,3],[2,4]]]
The first two are 1 and S4 itself. The third is the group of rotations of the tetrahedron. The fourth is just the rotations which move all the points.
Why are these subgroups normal, but the others aren't? Well, let's have a look at some of the ones that aren't.
We have a subgroup [ [[1,2]] ], and another [ [[1,3]] ], and several others that "look the same" - they just swap two points. We also have a subgroup [ [[1,2,3]] ], a subgroup [ [[1,2,4]] ], and several others that "look the same" - they just just rotate three points while leaving the fourth fixed. In fact, in both cases we have a set of conjugate subgroups. What I mean is, for a subgroup to be normal, we required that g^-1 K g = K. If a subgroup is not normal, then we can find a g such that g^-1 H g /= H. Then g^-1 H g will also be a subgroup (exercise: why?), and it will "look the same" as H.
By contrast, a normal subgroup is often the only subgroup that "looks like that".
Okay, so we've seen how groups can be broken down into smaller groups. Now, what about "atoms"? Well, a group always has itself and 1 as normal subgroups. If it has other normal subgroups, then we can break it down as K, G/K. We can keep going, and see if either of these in their turn has non-trivial normal subgroups. Eventually, we will end up with groups which have no non-trivial normal subgroups. Such a group is called a simple group. This is a bit like a prime number - which has no other factors besides itself and 1. Mark Ronan, in Symmetry and the Monster, calls simple groups the "atoms of symmetry". They are the pieces out of which all symmetry groups are made.
(Note that starting from a group G, with normal subgroups K1, K2, ..., we have more than one choice of how to break it down. Luckily, it turns out that if we keep going, then at the end we will have the same collection of "atoms", no matter which order we chose.)
So, what do simple groups look like?
Well, first, here's some code to detect them:
> isSimple gs = length (normalSubgps gs) == 2
Then the finite simple groups are as follows:
- The cyclic groups of order p, p prime (the rotation group of a regular p-gon):
> _C n | n >= 2 = [p [[1..n]]]
For example:
> isSimple $ _C 5
True
> isSimple $ _C 6
False
Exercise: Why is C n simple when n is prime, and not when it is not?
- The alternating groups A n, n >= 5. (A n is the subgroup of S n consisting of those elements of S n which are "even" - see wikipedia.)
> isSimple $ _A 4
False
> isSimple $ _A 5
True
(As it happens, A4 is the group of rotations of the tetrahedron, and A5 is the group of rotations of the dodecahedron. Unfortunately, An, n>5, doesn't have any such intuitive interpretation.)
- The projective special linear groups PSL(n,Fq) (except for PSL(2,F2), PSL(2,F3) and PSL(3,F2)). This is the subgroup of PGL(n,Fq) consisting of projective transformations with determinant 1. (Recall that last time we looked at PΓL(n,Fq), the group of symmetries of the projective geometry PG(n-1,Fq), which includes both projective transformations and field automorphisms.)
- Several more infinite families of subgroups of PΓL(n,Fq), with geometric significance.
- Finally, there are 26 "sporadic" simple groups, which don't belong to any of the infinite families described above.
I should just say a thing or two about the classification of finite simple groups:
- The proof of the classification was a monster effort by a whole generation of group theorists. The proof runs to 10000 pages.
- The part that mathematicians find most interesting is the sporadic simple groups. In many mathematical classifications, one only finds infinite families (for example, the primes), so the sporadic groups feel like little miracles that have dropped out of the sky. Why are they there?
Two of the things I'm hoping to do in future blog posts is describe and construct some of the other "simple groups of Lie type" (subgroups of PΓL(n,Fq), and describe and construct some of the sporadic simple groups.
