## Monday, 26 October 2009

### Simple groups, the atoms of symmetry

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

## Thursday, 8 October 2009

### Symmetries of PG(n,Fq)

Previously in this blog we looked at the affine geometries AG(n,Fq), and their symmetries. Following that, we looked at the points and lines in the projective geometries PG(n,Fq). This week I want to look at the symmetries of PG(n,Fq).

However, first, something I forgot to mention last week. When we looked at the points in PG(n,Fq), we saw that they can be thought of as the points of AG(n,Fq), plus some additional points "at infinity". What I forgot to do last week was to discuss how the lines in PG(n,Fq) relate to the lines in AG(n,Fq).

Here's PG(2,F3) again:

Recall that the points in PG(2,F3) are (by definition) the lines through the origin in F3^3, each of which can be represented, as here, by one of the non-zero points on it. (Note that for technical reasons, the coordinates are shown as zyx instead of xyz.) We see that these "points" of PG(2,F3) consist of something looking very much like AG(2,F3) - the blue points - together with some additional points, which are said to be "at infinity".

Then, the lines of PG(2,F3) are (by definition) the planes through 0 in F3^3. What is the relationship between lines in AG(2,F3) and "lines" in PG(2,F3)? Well, any line in (the copy of) AG(2,F3) (embedded in PG(2,F3)) is contained in a plane through 0 in F3^3. So each line in AG(2,F3) gives rise to a line in PG(2,F3). In PG(2,F3), however, the line will have an additional point "at infinity".

For example, there is a line in AG(2,F3) consisting of the points {(0,0),(1,0),(2,0)}. These embed into PG(2,F3) as {(1:0:0), (1:1:0), (1:2:0)}. We can ask what is the closure in PG(2,F3) of these points - the least "flat" (point, line, plane, etc) that contains them:

`> closurePG [ [1,0,0],[1,1,0],[1,2,0] ] :: [[F3]]`
`[[0,1,0],[1,0,0],[1,1,0],[1,2,0]]`

So in PG(2,F3), the line gains a point at infinity, (0:1:0).

Similarly, there is a line in AG(2,F3) consisting of the points {(0,1),(1,1),(2,1)}. These embed into PG(2,F3) as {(1:0:1), (1:1:1), (1:2:1)}.

`> closurePG [ [1,0,1],[1,1,1],[1,2,1] ] :: [[F3]]`
`[[0,1,0],[1,0,1],[1,1,1],[1,2,1]]`

Notice that both lines from AG(2,F3) gained the same point at infinity. This is because the two lines were parallel. In PG(2,F3), "parallel lines meet at infinity".

So each line in AG(2,F3) extends to a line in PG(2,F3), gaining an extra point at infinity. In addition to these lines, there is one more line in PG(2,F3) - a line at infinity consisting of the points {(0:0:1), (0:1:0), (0:1:1), (0:1:2)}, corresponding to the plane z = 0 in F3^3.

So, that was all stuff that I should really have talked about last time, but I forgot.

--*--

Okay, so back to the symmetries of PG(n,Fq). So we consider PG(n,Fq) as an incidence structure between points and lines, and we ask which permutations of the points preserve collinearity. That is, given a permutation g of the points of PG(n,Fq), we say that it is a symmetry (or automorphism, or collineation) of PG(n,Fq) if, whenever a and b are collinear points, then so are a^g and b^g, and vice versa.

We can find the symmetries of PG(n,Fq) by forming its incidence graph. This is the bipartite graph having as vertices: the points of PG(n,Fq) on the left (or in blue), the lines of PG(n,Fq) on the right (or in red), with an edge joining a point vertex to a line vertex if the point is incident with the line.

Here's the code:

`incidenceGraphPG n fq = G vs es where`
` points = ptsPG n fq`
` lines = linesPG n fq`
` vs = L.sort \$ map Left points ++ map Right lines`
` es = L.sort [ [Left x, Right b] | b <- lines, x <- closurePG b]`

Let's look at an example. Here's PG(2,F2):

The lines in PG(2,F2), corresponding to planes through 0 in F2^3, are:

`> mapM_ (print . closurePG) \$ linesPG 2 f2`
`[[0,1,0],[1,0,0],[1,1,0]]`
`[[0,1,1],[1,0,0],[1,1,1]]`
`[[0,1,0],[1,0,1],[1,1,1]]`
`[[0,1,1],[1,0,1],[1,1,0]]`
`[[0,0,1],[1,0,0],[1,0,1]]`
`[[0,0,1],[1,1,0],[1,1,1]]`
`[[0,0,1],[0,1,0],[0,1,1]]`

PG(2,F2) is called the Fano plane, and is often represented by the picture below:

You can easily check that this is right. Notice the embedded AG(2,F2) in the bottom left, with parallel lines meeting "at infinity" as expected.

The incidence graph of the Fano plane is called the Heawood graph, and it is often represented like this:

The blue vertices are the points of the Fano plane, the red vertices are the lines. For each red vertex, you can check that the three blue vertices it is connected to are indeed a line of the Fano plane.

Then we can find the automorphisms of the Fano plane as follows:

`> let heawood = incidenceGraphPG 2 f2`
`> let auts = incidenceAuts heawood`
`> mapM_ print auts`
`[[[0,0,1],[0,1,0]],[[1,0,1],[1,1,0]]]`
`[[[0,0,1],[0,1,1],[0,1,0]],[[1,0,1],[1,1,1],[1,1,0]]]`
`[[[0,0,1],[1,0,0],[0,1,0]],[[0,1,1],[1,0,1],[1,1,0]]]`
`[[[0,1,0],[0,1,1]],[[1,1,0],[1,1,1]]]`
`[[[0,1,0],[1,0,0]],[[0,1,1],[1,0,1]]]`
`[[[0,1,0],[1,1,0],[1,0,0]],[[0,1,1],[1,1,1],[1,0,1]]]`
`[[[1,0,0],[1,0,1]],[[1,1,0],[1,1,1]]]`
`[[[1,0,0],[1,1,0]],[[1,0,1],[1,1,1]]]`
`> orderSGS auts`
`168`

Now the symmetries of PG(n,Fq) actually have a very simple description in terms of matrices. Consider the invertible matrices of degree n+1 over Fq - the general linear group GL(n+1,Fq). These matrices act on vectors in Fq^(n+1) by multiplication, and in doing so, they permute the lines and planes through 0 in Fq^(n+1), whilst preserving containment of lines within planes. In other words, they permute the points and lines of PG(n,Fq) and preserve collinearity. However, any scalar matrix within GL(n+1,Fq) - that is, kI, where k is in Fq\{0} and I is the identity - acts as the identity on PG(n,Fq) - since if (x0:x1:...:xn) is a "point" of PG(n,Fq), then (kx0:kx1:...:kxn) represents the same point. So the group of projective transformations of PG(n,Fq) is actually GL(n+1,Fq) factored out by scalar multiplications. This group is called the projective general linear group, PGL(n+1,Fq).

If we are given a symmetry of PG(n,Fq), expressed as a permutation, then we can express it as a matrix by looking at what it does to the basis vectors. For example, consider the symmetry [[[0,0,1],[0,1,0]],[[1,0,1],[1,1,0]]] of PG(2,F2) from above. It sends [1,0,0] to [1,0,0], [0,1,0] to [0,0,1], and [0,0,1] to [0,1,0]. So it can be represented by the matrix
`[1 0 0]`
`[0 0 1]`
`[0 1 0]`

We already worked out the order of GL(n,Fq) in the orderGL function. There are q-1 non-zero scalars to factor out by. So the order of PGL(n,Fq) will be given by the following:

`orderPGL n q = orderGL n q `div` (q-1)`

Let's test it (remembering that we want PGL(n+1,Fq) for PG(n,Fq)):

`> orderPGL 3 2`
`168`
`> orderSGS \$ incidenceAuts \$ incidenceGraphPG 2 f3`
`5616`
`> orderPGL 3 3`
`5616`
`> orderSGS \$ incidenceAuts \$ incidenceGraphPG 2 f4`
`120960`
`> orderPGL 3 4`
`60480`

With F4, we get twice as many automorphisms as we might have expected. If you've been paying attention, you'll remember that this is because F4 has a field automorphism (the Frobenius automorphism) of order 2. The extended group, PGL(n,Fq) plus field automorphisms, is called PGammaL(n,Fq) (or better - but I'm not sure this will work for everybody - PΓL(n,Fq)).

Now, this is kind of a trivial point, but I think it's significant: PG(n,Fq) has more symmetries than AG(n,Fq). Somehow, by adding the points at infinity, PG(n,Fq) has made AG(n,Fq) "whole", making it more symmetrical.

Anyway, that'll do for now. Next week, just a few more odds and ends about finite geometries.