Finite geometries, part 1: AG(n,Fq)

Time to recap a little. Through June and July, we looked at graphs and their symmetries. Then through August, we looked at finite fields. Now I want to look at finite geometries. Why?

Well, it's a continuation of my earlier investigation of symmetry. I chose graphs as the starting point because they're easy to understand. However, graphs are not the only combinatorial structure having symmetry - far from it. Finite geometries are important for several reasons:
1. We'll see that all symmetry groups turn out to be composed out of "atoms of symmetry", called "simple groups". There are several infinite families of finite simple groups - and a few "sporadic" ones that don't fit into any family. One of the infinite families are symmetries of finite projective geometries, which we will look at in due course. (I got the term "atoms of symmetry" from Ronan, Symmetry and the Monster, which is a nice easy read on this stuff.)
2. The symmetry groups of infinite geometries are very important in physics (especially particle physics). So if you like, you can pretend that what we're looking at here will help you understand physics.

This time, I want to look at affine geometries, but what we're aiming towards is projective geometries.

Within mathematics, there are probably many different definitions of geometry. Within combinatorics, we're just interested in the combinatorial structure, so roughly speaking, a geometry is just a collection of points, lines, planes and so on, together with a relation, called "incidence", saying which points are on which lines, and so on. Most of the time it's natural to think of a line as just being a set of points, in which case we can think of the incidence relation as just being the membership relation. However, this isn't always the best way to represent things in the code (or in the maths), as we shall see.

The most familiar geometry is the Euclidean plane, R^2. In this geometry, every pair of lines meets in at most one point. Then of course, there are Euclidean spaces of three or more dimensions. There are also non-Euclidean geometries. For example, spherical geometry is geometry on the surface of a sphere, with the lines being great circles. In this case, every pair of lines meets in exactly two points.

If you know about vector spaces, then you might think that Euclidean geometry is basically about the vector space R^n, with points, lines, planes being the zero-, one-, two-dimensional subspaces, and so on. However, this isn't quite right, because a vector space has a distinguished point, the origin, and every subspace of a vector space contains the origin. In Euclidean geometry there is no such distinguished point - we can have points, lines, planes which don't contain the origin. So we need to take the vector space R^n, and then "forget" the origin. If we do this, we get what is called an affine space. The subspaces of an affine space are the subspaces of the underlying vector space and their translates. The collection of points, lines, planes, and so on in an affine space, together with the incidence relation, is called an affine geometry.

We can construct finite affine geometries simply by replacing R by a finite field Fq in the above. In this way, we obtain the affine geometries AG(n,Fq). So in AG(n,Fq), we will have points, lines, planes and so on, but there will be only a finite number of each. Let's start with the points. Well, that's easy. The points of AG(n,Fq) are just the points Fq^n. The HaskellForMaths code goes like this:

ptsAG 0 fq = [[]]
ptsAG n fq = [x:xs | x <- fq, xs <- ptsAG (n-1) fq]

Actually, I think the stylish way to do this in Haskell would be:

ptsAG n fq = sequence $ replicate n fq


In any case, here's an example:

> :load Math.Combinatorics.FiniteGeometry
> ptsAG 2 f3
[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

In other words, the points of AG(2,F3) form a 3*3 grid.

What about the lines? Well, the points of AG(2,F3) are the vector space F3^2. The lines are just the one-dimensional subspaces of this vector space, and their translates. Here's a picture:


Don't worry about the fact that the lines aren't straight. All we're concerned about is which points are incident with which lines. You might just want to convince yourself that every one-dimensional subspace of F3^2 is shown, as well as every translate.

Hopefully this picture makes the analogy between finite geometries and graphs pretty obvious. Points are analogous to vertices; lines are analogous to edges. The main difference is that unlike edges, lines can have more than two points on them. Indeed, if we consider just the points and lines (and not planes, hyperplanes, etc), then a finite geometry gives rise to a "hypergraph" - a graph, but where the "hyperedges" are allowed to contain more than two points. However, finite geometries have some additional structure, since they can also contain planes, hyperplanes etc.

Anyway, we want to calculate the symmetries of finite geometries, and in order to do that, we're going to need to work out what the lines are. First, let's think about how to represent the lines in code. There are several ways we could do it, including at least the following:
- We could represent a line as a list/set of the points on it. We will occasionally want to list all the points on a line, but as a way to represent a line, it's not very efficient.
- A line in the plane has an equation ax+by=c. We could represent a line by the triple (a,b,c). However, that would only work in two dimensions.
- We could represent a line by any pair of distinct points on the line. This will work in any number of dimensions, and will generalise to planes (represented by three points), and so on.

This last approach is the one we will take. So we would like two functions:
- given a pair of points in AG(n,Fq), return all points on the line that they generate
- given n, Fq, return all lines in AG(n,Fq) (represented as a pair of points)

The first is straightforward:

lineAG [p1,p2] = L.sort [ p1 <+> (c *> (p2 <-> p1)) | c <- fq ] where
    fq = eltsFq undefined 

There are a couple of unfamiliar things here. <+>, <->, *> are the HaskellForMaths functions for adding two vectors, subtracting, and multiplying by a scalar. The second line is just a little bit of phantom type trickery, using type inference to magic up the elements of Fq. Note that the points are returned sorted.

Now to find all the lines. The naive way to do this is as follows:
- list all pairs of points in AG(n,Fq)
- but any pair of points on a line generates the same line, so each line will be listed many times
- so keep only those pairs of points which are the first two points on the line

Here's the code:

linesAG1 n fq = [ [x,y] | [x,y] <- combinationsOf 2 (ptsAG n fq),
                          [x,y] == take 2 (lineAG [x,y]) ]

(This is not a very efficient way to find the lines, but we don't yet have the background to do it more efficiently.)