Finite geometries, part 2: Symmetries of AG(n,Fq)

Last time, we met the finite affine geometries AG(n,Fq), which are analogous to n-dimensional Euclidean geometry, but defined over the finite fields Fq instead of the reals R. This time I want to talk about the symmetries of AG(n,Fq).

Recall that when we were looking at graphs, we defined a symmetry of a graph as a permutation of the vertices which left the edges (collectively) in the same places. For the moment, we will think of a finite geometry as a configuration of points and lines, and define a symmetry as a permutation of the points which leaves the lines (collectively) in the same places.

Here's AG(2,F3) again:

There's an obvious four-fold rotational symmetry, which moves all the points except the middle point, moves all the lines, but leaves the lines collectively in the same places. Less obvious perhaps is that reflection in the middle line, or translating everything one point to the right (with wraparound), are also symmetries. Remember that the straightness or otherwise of the lines doesn't matter - the only thing we're interested in is which points they are incident with.

So how can we find all the symmetries? Well, when we were looking at graphs, we used depth-first search, trying to create a pairing of source and target vertices, and backtracking whenever the adjacency between the source vertices didn't match the adjacency between the target vertices. Unfortunately, this method doesn't easily generalize to finite geometries. Exercise: Why not?

Instead, we will change the problem into a problem about graphs. Given a collection of points and lines, we can create an "incidence graph". This is the bipartite graph constructed as follows. On the left, we have a vertex for every point. On the right, we have a vertex for every line. We have an edge joining a point on the left to a line on the right just in the case that the point is incident with the line in our geometry.

Here's the code to create the incidence graph of AG(n,Fq):

incidenceGraphAG n fq = G vs es where

    points = ptsAG n fq

    lines = linesAG n fq

    vs = L.sort $ map Left points ++ map Right lines

    es = L.sort [ [Left x, Right b] | b <- lines, x <- closureAG b]

(Recall that a line is represented by two distinct points on it. "closureAG" calculates all the points on the line.)

Now, the trick is, that we can find the symmetries of the finite geometry by finding the symmetries of its incidence graph. For clearly, any symmetry of the finite geometry permutes the points among themselves, permutes the lines among themselves, and preserves incidence - hence it gives rise to a symmetry of the incidence graph. So in principle, we can find the symmetries of the finite geometry by doing the following:

> mapM_ print $ graphAuts $ incidenceGraphAG 2 f3

[[Left [0,0],Left [0,1]],[Left [1,0],Left [2,2],Left [1,1],Left [2,1],Left [1,2],Left [2,0]],[Right [[0,0],[1,0]],Right [[0,1],[1,0]],Right [[0,0],[1,1]],Right [[0,1],[1,1]],Right [[0,0],[1,2]],Right [[0,1],[1,2]]],[Right [[0,2],[1,0]],Right [[0,2],[1,2]],Right [[0,2],[1,1]]],[Right [[1,0],[1,1]],Right [[2,0],[2,1]]]]

[[Left [0,0],Left [0,2],Left [0,1]],[Left [2,0],Left [2,1],Left [2,2]],[Right [[0,0],[1,0]],Right [[0,2],[1,0]],Right [[0,1],[1,0]]],[Right [[0,0],[1,1]],Right [[0,2],[1,1]],Right [[0,1],[1,1]]],[Right [[0,0],[1,2]],Right [[0,2],[1,2]],Right [[0,1],[1,2]]]]

...

However, there are a couple of minor problems with this:

1. We only really want to know what happens to the points. What happens to the lines follows from that. So we only want to know about the Left parts, not the Right parts. (Furthermore, if we were to show only the Left part, we then wouldn't need all those Lefts and Rights which are cluttering up the output.)
2. It is just possible that the incidence graph might have some symmetries which interchange points and lines. This is a very interesting situation, which we'll discuss in due course. But it is a symmetry of the graph which does not correspond to a symmetry of the geometry.
   

For these reasons, HaskellForMaths provides an "incidenceAuts" function, which works just like graphAuts, except that it knows that the input is an incidence graph, so it avoids wasting time looking for point-line crossover symmetries, and outputs only the permutations of the points.

> mapM_ print $ incidenceAuts $ incidenceGraphAG 2 f3

[[[0,0],[0,1]],[[1,0],[2,2],[1,1],[2,1],[1,2],[2,0]]]

[[[0,0],[0,2],[0,1]],[[2,0],[2,1],[2,2]]]

[[[0,0],[1,0],[0,1]],[[0,2],[2,0],[2,2]],[[1,1],[2,1],[1,2]]]

[[[0,1],[0,2]],[[1,1],[1,2]],[[2,1],[2,2]]]

[[[0,1],[1,0]],[[0,2],[2,0]],[[1,2],[2,1]]]

[[[0,1],[1,1],[1,2],[2,0],[0,2],[2,2],[2,1],[1,0]]]

[[[1,0],[1,1],[1,2]],[[2,0],[2,2],[2,1]]]

[[[1,0],[2,0]],[[1,1],[2,1]],[[1,2],[2,2]]]

This is a strong generating set for the symmetries of AG(2,F3). We could now go on to investigate further. We could ask what different types of symmetries there are, using the conjClassReps function, or how many symmetries there are, using the orderSGS function.

For example, among the elements of the SGS, some have obvious interpretations:

[[[1,0],[2,0]],[[1,1],[2,1]],[[1,2],[2,2]] - remember that this means that it swaps [1,0] and [2,0], swaps [1,1] and [2,1], and swaps [1,2] and [2,2]. So it can be thought of as a reflection in the line x = 0, or as a 2* stretch of the x-coordinate. It is given by the matrix [[2,0],[0,1]]. (In F3, 2 = -1, which is why this can be thought of as either a reflection or a stretch.)

[[[1,0],[1,1],[1,2]],[[2,0],[2,2],[2,1]]] is the shear given by the matrix [[1,1],[0,1]].

[Later: You might question whether a shear is a symmetry. We have defined a symmetry informally as a change that leaves things looking the same. But, for example, a shear in R^2 doesn't leave the unit square looking the same. Is it really a symmetry? Well, when we're studying geometries within combinatorics, we're only interested in the incidence between points and lines, and not, for example, distances. From this point of view, a shear is indeed a symmetry, because it preserves incidence. We will later look at what happens when we require symmetries to preserve more than just incidence.]

[[[0,0],[1,0],[0,1]],[[0,2],[2,0],[2,2]],[[1,1],[2,1],[1,2]]] cannot be represented by a 2*2 matrix, since it moves the origin. However, it can be represented by a 3*3 matrix, as follows:

[x']   [2 2 1] [x]

[y'] = [1 0 0] [y]

[ 1]   [0 0 1] [1]

This is the same as saying:

[x'] = [2 2] [x] + [1]

[y']   [1 0] [y]   [0]

So we see that it is a composite of some sort of shear, followed by a translation.

Indeed, we could conjecture that all symmetries of AG(n,Fq) are of this form - a linear transformation followed by a translation. Let's see whether we can confirm this conjecture by counting symmetries.

We have seen that some symmetries can be represented by a 2*2 matrix. In fact, the matrix must be non-singular, otherwise we won't have a permutation. The group of 2*2 non-singular matrices over Fq is the general linear group GL(2,Fq). How many elements does it have? Well, for the first row, we can choose any non-zero vector in Fq^2, of which there are q^2-1. For the second row, we can choose any vector in Fq^2 which is not linearly dependent on the one we already chose, of which there are q^2-q. Generalising to GL(n,Fq), the following code calculates the number of elements of GL(n,Fq):

orderGL n q = product [q^n - q^i | i <- [0..n-1] ]

Then, in addition to these linear transformations, all of which leave the origin fixed, we can do a translation. The number of translations of Fq^n is of course q^n.

A transformation consisting of a translation and a linear transformation is called an affine transformation. The group of all such is called the affine group, Aff(n,Fq). It is straightforward to calculate the number of elements of this group:

orderAff n q = q^n * orderGL n q

(Note that by multiplying the number of translations by the number of linear transformations, I have made an assumption that they are "semi-independent" of one another. This assumption is valid, but at this stage I don't want to spell out exactly what it means.)

Okay, so our conjecture is that all symmetries of AG(n,Fq) are affine transformations. Let's test our conjecture:

> orderSGS $ incidenceAuts $ incidenceGraphAG 2 f3

432

> orderAff 2 3

432

> orderSGS $ incidenceAuts $ incidenceGraphAG 2 f4

5760

> orderAff 2 4

2880

Uh-oh - what's going on here? We seem to have twice as many symmetries as we expected.

It took me quite a while to figure this one out actually. What's going on?

Well, remember that when we looked at extension fields, I mentioned that there can be field automorphisms. (For example, in the complex numbers, we have complex conjugation.) When we looked at the finite fields Fq, for q = p^n a prime power, I mentioned the Frobenius automorphism x -> x^p. Okay, well what's going on is that the field automorphisms of Fq give rise to further symmetries of AG(n,Fq). If q = p^n, then the number of such automorphisms is n, so the total number of symmetries of AG(n,Fq) will be n * orderAff n q.

And now that really does account for all symmetries of AG(n,Fq). Apart from the following exceptions:

> orderSGS $ incidenceAuts $ incidenceGraphAG 3 f2

40320

> orderAff 3 2

1344

What's going on here? Well the problem is that AG(n,F2) is degenerate. A line in AG(n,F2) has just two points - and every pair of points forms a line. So in fact, AG(n,F2) is just the complete graph K (2^n), and hence has (2^n)! symmetries.

That's it for now. Next time, finite projective geometries.