Home Online Mathematical Communication Peter Cameron's Blog The geometry of diagonal groups

The geometry of diagonal groups

Peter Cameron's Blog 2020-04-18

This is an interim report on ongoing work with Rosemary Bailey, Cheryl Praeger and Csaba Schneider. We have reached a point where we have a nice theorem, even though there is still a lot more to do before the project is finished.

Primitive permutation groups

This is an attempt to understand and characterise a class of permutation groups. So I begin with some reminders. We always assume that G is a permutation group on a set Ω, usually but not always assumed finite. We say that G is transitive if any point of Ω can be moved to any other by an element of G (in other words, G preserves no non-empty proper subset of Ω). We also say that G is primitive if it preserves no non-trivial equivalence relation on Ω (the trivial equivalence relations, equality and the “universal” relation with a single class, are preserved by any permutation group).

In the interests of full disclosure, I should point out that the only equivalence relations on a 2-element set are the trivial ones, so even the identity group of degree 2 is primitive according to this definition. This is usually excluded by adding to the definition the requirement that the group is transitive.

According to a simplified version of the O’Nan–Scott Theorem, there are four kinds of finite primitive group:

  • non-basic groups;
  • affine groups;
  • diagonal groups;
  • almost simple groups.

Almost simple groups are the ragbag here. The reason that the O’Nan–Scott Theorem is almost contemoraneous with Gorenstein’s announcement of the Classification of Finite Simple Groups is that, without CFSG, there is almost nothing we can say about this class, since all we know is that they lie between a non-abelian simple group and its automorphism group, and we have no information at all about the way they act except that it is primitive. For the other classes, the action is specified, and we are in a stronger position, as I will describe.

In the affine and non-basic cases, the groups are automorphism groups of well-known and well-studied geometric/combinatorial structures. The aim of the project is to understand the structures on which diagonal groups act.

Affine groups

These are groups of permutations of vector spaces which contain the translation group of the space as a normal subgroup, and are generated by this together with a group of linear transformations of the space. The maximal affine group (for any given vector space) takes the group of linear transformations to be the full general linear group on the space (all invertible linear transformations).

These groups preserve a well-known structure, the affine geometry on the vector space, whose points are the vectors, and whose subspaces are the cosets of the vector subspaces.

We may always assume that the field is a prime field (that is, the integers mod p for some prime p), by simply restricting scalars.

Non-basic groups and Cartesian lattices

Let A be an alphabet of size q, and let Ω be the set of all words of length n over A. The maximal non-basic group is generated by two kinds of transformation:

  • independent permutations on the letters in the ith coordinate of a word, for all i (these form the direct product of n copies of the symmetric group on the alphabet A);
  • permutations of the coordinates (these form the symmetric group of degree n).

The group generated is the wreath product of the symmetric groups of degree q and n.

What natural structure is preserved by this group? There are two possible answers.

A coding theorist would say, the Hamming graph, whose vertex set is the set of all words, in which two words are adjacent if they differ in just one position (that is, a single error will transform one into the other). So the distance of two vertices in the Hamming graph is the number of errors required to turn one into the other. The automorphism group of the Hamming graph is the wreath product just constructed.

We need a slightly different answer. For every subset I of {1,…,n}, define an equivalence relation ≡I on Ω as follows: two words are equivalent if they agree in all coordinates except those in I. The corresponding partitions PI of Ω form a sublattice of the partition lattice on Ω, and the map I → PI is an isomorphism from the Boolean lattice of subsets of {1,…,n} to this lattice just constructed, which we call a Cartesian lattice associated with A and n. Its automorphism group is again the wreath product of symmetric groups. Its dimension is n.

Two features of the Cartesian lattice should be noted.

The maximal proper partitions in the lattice (corresponding to the case where I = {1,…,n}\{i} for some i) form what Cheryl Praeger and Csaba Schneider call a Cartesian decomposition of Ω in their book Permutation Groups and Cartesian Decompositions. They generate the lattice by taking meets (infima).

The minimal proper partitions in the lattice correspond to the case where I contains just a single element. The parts of each minimal partition are maximal cliques in the Hamming graph. These minimal partitions also generate the lattice, by taking joins (suprema).

For n = 3, think of a cube; the maximal partitions are those into slices parallel to the faces of the cube (which we will call layers), while the minimal partitions are those into lines parallel to the edges.

Latin squares

A Latin square can be regarded as a square array of size q×q with entries from an alphabet of size q, so that each letter occurs once in each row and once in each column of the array.

Latin squares exist in great profusion. (The Cayley table of a group is a Latin square; but these form only a tiny fraction of the total.) The precise number (as function of q) is not known for q > 11; upper and lower bounds are known, both growing faster than the exponential of q2.

We need to interpret Latin squares a bit differently. Let Ω be the set of q2 cells. We have three partitions of Ω:

  • the partition R into rows;
  • the partition C into columns;
  • the partition L into letters (two cells in the same part if they contain the same letter).

These three partitions together with the partitions E (equality) and U (universal) form a sublattice of the partition lattice. For us, the crucial property is:

Any two of R,C,L, together with E and U, form a Cartesian lattice of dimension 2.

Latin cubes

Before plunging into the general case, I will describe Latin cubes; it turns out that the heart of our proof involves this case.

Here we have to face the fact that there are different definitions of Latin cubes. In all cases we have a q×q×q array of letters. I will use the term layer for a slice of the cube parallel to one of the faces (containing q2 cells), and line for the intersection of two non-parallel layers (containing q cells).

By far the commonest definition of Latin cube requires an alphabet of q letters, arranged so that each letter occurs once in each line. But this is not what we want. So I will call it a Latin cube of the first kind, and move on to the definition we do want.

A Latin cube of the second kind has an alphabet of q2 letters, arranged in the cube such that each layer contains each letter exactly once.

Another definition. A Latin cube of the second kind is regular if the sets of letters on two parallel lines are either equal or disjoint. Thus, for each parallel class of lines, the letters are partitioned into q sets of size q so that each line has the letters from one of these sets, and all q sets occur on the lines in a given layer.

This definition is from a paper of Preece, Pearce and Kerr. They do not attempt to classify these things, naturally enough: if Latin squares are wild, you might expect Latin cubes to be even wilder! But, surprisingly, it is not so.

Now let A be a group of order q. We can take the three coordinates of the cube as being elements of A. Take the set of q2 letters to consist of all triples [x,y,z] of group elements satisfying xyz = 1. In cell (a,b,c), put the triple [b−1c,c−1a,a−1b]. It is not too hard to see that this is a Latin cube of the second kind, and is regular.

Now here is our theorem about these:

Theorem Every regular Latin cube of the second kind comes by the above construction from a group, unique up to isomorphism.

As I said, this is the heart of the argument; the proof of it is the most complicated part of the whole thing, and I will not attempt to describe it here. Note that the group emerges naturally from the combinatorial structure.

Diagonal structures and groups

After that interlude, back to the main business. Let A be a group and m a positive integer. We take Ω = Am. Consider the following subgroups of Ω:

  • Ai, the ith coordinate subgroup (with the identity in all positions different from the ith), for i = 1,…,m;
  • A0, the diagonal subgroup consisting of the m-tuples with all entries equal.

Let Pi be the partition of Ω into right cosets of Ai, for i = 0,…,m.

We claim that any m of these m+1 partitions are the minimal non-trivial elements of a Cartesian lattice. This is clear for P1,…,Pm. For the others, note that we can swap P0 and P1, fixing the other partitions, by the map taking (a1,a2,…,am) to (a1−1,a1−1a2,…,a1−1am), and so we can permute the m+1 partitions arbitrarily.

The set-theoretic union of the Cartesian lattices generated by all these m-tuples of partitions is closed under join (but not meet), and so forms a join-semilattice. This is the diagonal semilattice.

The full diagonal group D(A,m) is the automorphism group of the (m+1)-set of partitions, or of the semilattice it generates. It contains (and is generated by)

  • the group Am, acting by right multiplication;
  • the diagonal group A0, acting by left multiplication;
  • automorphisms of A, acting simultaneously on all coordinates;
  • the symmetric group of degree m+1, permuting the partitions (generated by the symmetric group of degree m permuting the coordinate subgroups, and the transposition defined above swapping P0 and P1).

The main theorem

Now I can state the main theorem.

Theorem Let P0,…,Pm be partitions of Ω, for m ≥ 2. Suppose that any m of these partitions are the mimimal non-trivial elements of a Cartesian lattice on Ω.

  • If m = 2, then the three partitions, together with the two trivial partitions, form a Latin square, unique up to isotopy.
  • If m > 2, then there is a group A, unique up to isomorphism, such that the m+1 partitions are the minimal non-trivial elements in a diagonal semilattice for D(A,m).

This theorem has a similar structure to the Veblen–Young characterisation of projective spaces. In the low-dimensional case, the objects are “wild” (projective planes there, Latin squares here); in all higher dimensions, they are described by algebraic structures (skew fields there, groups here).

The proof is not so difficult from what we have already seen. For m = 2, the assertion is almost obvious. For m = 3, we have to match up the description of the Latin cube with that of the diagonal structure. Finally for m > 3, the proof is by induction.

Final note: The theorem makes sense in the infinite case (m is finite but the set Ω and the output group A are allowed to be infinite). We think our proof works for these as well. All this, of course, is subject to careful checking!