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 P_{I} of Ω form a sublattice of the partition lattice on Ω, and the map I → P_{I} 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 q^{2}.
We need to interpret Latin squares a bit differently. Let Ω be the set of q^{2} 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 q^{2} 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 q^{2} 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 q^{2} letters to consist of all triples [x,y,z] of group elements satisfying xyz = 1. In cell (a,b,c), put the triple [b^{−1}c,c^{−1}a,a^{−1}b]. 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 Ω = A^{m}. Consider the following subgroups of Ω:
- A_{i}, the i^{th} coordinate subgroup (with the identity in all positions different from the i^{th}), for i = 1,…,m;
- A_{0}, the diagonal subgroup consisting of the m-tuples with all entries equal.
Let P_{i} be the partition of Ω into right cosets of A_{i}, 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 P_{1},…,P_{m}. For the others, note that we can swap P_{0} and P_{1}, fixing the other partitions, by the map taking (a_{1},a_{2},…,a_{m}) to (a_{1}^{−1},a_{1}^{−1}a_{2},…,a_{1}^{−1}a_{m}), 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 A^{m}, acting by right multiplication;
- the diagonal group A_{0}, 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 P_{0} and P_{1}).
The main theorem
Now I can state the main theorem.
Theorem Let P_{0},…,P_{m} 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!
I talked about this (among other things) in a virtual talk to the Rocky Mountain Algebraic Combinatorics seminar last Friday.
Since you mentioned the virtual talk, has it been recorded? With so many available seminar series online I’ve ended up overlooking a few I should have virtually attended!
I don’t think it was recorded. But we are in the final stages of writing the paper — I found a beautiful proof of the induction step last night — so it should be on the arXiv before too long (hopefully). Email (or Stephen Glasby) if you want the slides of the talk.
The paper went on the arXiv this morning: https://arxiv.org/abs/2007.10726
Does this have any implications for the existence (or non-existence) of the missing Moore graph?
Background: the missing Moore graph — if it exists — is regular of degree 57, girth 5, and order 3250. If you designate one vertex arbitrarily as a root $r$, one of its neighbors arbitrarily as $u$ and its others as $v_i, i = 1\ldots 56$, you can then label the other neighbors of $u$ as $u_j, j= 1\ldots 56$. Finally, designate the other vertices as $w_{ij}$, with $\{ v_i, w_{ij} \} \in E$ and $\{ u_j, w_{ij} \} \in E$. The adjacency matrix of the induced subgraph on the $w$s can be represented as a Latin cube with some interesting properties (you have to give each $w$ a self-edge to complete the cube, but that’s not too difficult). I believe you can represent the cube either as being of the first or second types, but I am pretty sure it is not regular. It _might_ however satisfy the preconditions of the main theorem. I haven’t worked that out — I don’t know enough about Cartesian lattices.
Fundamentally, you have a set of 56^2 vertices, and 4 partitions into sets of 56 (by the first coordinate, by the second coordinate, having an edge to $w_{i*}$, and having an edge to $w_{*j}$). Does the girth-5 nature of the graph imply that any 3 partitions are the minimal non-trivial elements of a Cartesian lattice?
Sorry, ignore my second statement — the latter two are not correct partitions. Fixing $i$, “having an edge to $w_{ij}$” partitions the vertices as $j$ varies, and vice versa. So in fact you can partition it in 2 + 2*56 ways — but I’m not sure any given subset of 4 will satisfy the preconditions of your theorem.
In fact, if this argument worked, then it would disprove the existence of the Moore graph on 50 vertices, since there do not exist two orthogonal Latin squares of order 6.