Between transitive and primitive, I: history

I do enjoy being able to describe some mathematics to you. In this post and the next, it is the somewhat neglected class of transitive but imprimitive finite permutation groups. The paper is on the arXiv, 2409.10461.

The official history

In the late 1960s, combinatorial methods seriously entered permutation group theory.

If a permutation group G on a finite set Ω is primitive but not 2-transitive, then any orbit of G on ordered pairs of distinct elements of Ω is the edge set of a connected (indeed, strongly connected) digraph whose automorphism group contains G. Moreover, the collection all these digraphs forms a combinatorial structure called a homogeneous coherent configuration. These structures had been developed in three different areas of mathematics: permutation groups (via Schur, Wielandt and Donald Higman); experimental design in statistics (via Bose and his school), and the graph isomorphism problem (Weisfeiler and his colleagues).

So when we (Marina Anagnostopoulou-Merkouri, Rosemary Bailey and I) came to look at permutation groups which are transitive but not primitive, it was natural to follow this format. What do such groups preserve? (The answer: partitions.) What structure do these partitions form? (The answer: a lattice.) So the combinatorial structures underlying our study should be lattices of partitions.

We have just put a paper on the arXiv developing the theory.

The secret history

Mathematics is a human activity, and as in all human activities, nothing is quite as simple as it seems.

I arrived in Oxford to study for a DPhil in 1968. My supervisor, Peter Neumann, was just putting the finishing touches to a long paper on primitive permutation groups of degree 3p (extending a result of Wielandt for groups of degree 2p). I was given the paper to read; it kindled my lifelong interest in the interface between group theory and combinatorics.

The paper was never published. One of the reasons for this was that Leonard Scott and Olaf Tamaschke had obtained similar results. (There was a plan that Neumann and Scott would collaborate, but nothing came of it.) Had it been published, it would have been a significant contribution to the rapidly developing area between permutation groups and combinatorics. However, a decade later, the Classification of Finite Simple Groups had rendered the main theorem of the paper obsolete.

Peter died, a victim of Covid in care homes, in late 2020. In the summer of 2022, Marina, finishing her penultimate year of her MMath in St Andrews, asked me if I would supervise her on a summer research project. I had in mind that there was some serious combinatorial information in the 3p paper, and suggested a project to extract results about coherent configurations and association schemes from it. Leonard Scott was able to provide a scan of the paper, with only a few small bits missing (my copy had disappeared long ago). We applied for, and were awarded, an Undergraduate Research Bursary by the London Mathematical Socety.

So Marina set to work, and we produced a paper doing the job, combining combinatorics, group theory, and history. We submitted it to the Journal of the London Mathematical Society, which I considered appropriate since the paper crossed boundaries and would interest many readers. To my slight surprise (since Peter had been a stalwart of the LMS, including Publications Secretary for many years), they turned it down, almost by return, not because of the mathematics, but because it was inappropriate. It found a home in Algebraic Combinatorics (though it probably won’t have the same breadth of readership there).

Anyway, Marina had finished the work before the money ran out, so she asked me for another problem. I hit on the following idea. Suppose that Q and Q⁻ are permutation group properties, with Q stronger than Q⁻. Is there a “natural” property P, logically independent of Q⁻, such that the conjunction of P and Q⁻ is equivalent to Q? (This would hopefully throw light on the gap between Q and Q⁻.)

We found several candidates among the synchronization hierarchy; most of them turned out to be rather trivial. But we struck gold in one place, arising from a confusion of Galois which had been pointed out by Peter Neumann.

Two possible properties of a permutation group are primitivity (no non-trivial invariant partitions) and quasi-primitivity (every non-trivial normal subgroup is transitive). The first easily implies the second. Neumann showed that, in his Second Memoir, Galois sometimes used one, sometimes the other, to mean “primitivity”. These two properties are ideal for the Q and Q⁻ of our set-up; take P to be the property “every invariant partition is the orbit partition of a subgroup (which, without loss of generality, can be taken to be a normal subgroup)”. We called this property pre-primitivity.

So we wrote a paper on this, with contributions from Enoch Suleiman, and it was published in the Journal of Algebra.

Having found a profitable line on properties weaker than primitivity, we wished to continue, and it was only at this point that we realised that we should be looking at lattices of partitions.

As it happened, at the other desk in my office, and overhearing my conversations with Marina, was Rosemary, who was able to point out that statisticians working on experimental design (Fisher, Yates, Nelder, Kempthorne, Speed, and others including herself) had been looking at such things for some time, and had developed a considerable body of theory. So of course she joined the team. I will tell you about some of the results in the next post.

Footnote

This is my fourth ABC collaboration.