More on derangements

Francis Bacon, in The New Organon, developed a famous metaphor:

Those who have handled sciences have been either men of experiment or men of dogmas. The men of experiment are like the ant, they only collect and use; the reasoners resemble spiders, who make cobwebs out of their own substance. But the bee takes a middle course: it gathers its material from the flowers of the garden and of the field, but transforms and digests it by a power of its own. Not unlike this is the true business of philosophy; for it neither relies solely or chiefly on the powers of the mind, nor does it take the matter which it gathers from natural history and mechanical experiments and lay it up in the memory whole, as it finds it, but lays it up in the understanding altered and digested. Therefore from a closer and purer league between these two faculties, the experimental and the rational (such as has never yet been made), much may be hoped.

At present, the ants and bees are under lockdown, and are unable to go out and collect their experimental material. But the spiders (the pure mathematicians) can keep themselves sane by sitting at home spinning, so that is what I have been doing for the last couple of weeks. Parts of the resulting web may appear here from time to time.

Last word from the Isaac Newton Institute

At the third (and final) workshop in the GRA programme at the Isaac Newton Institute, Aner Shalev gave a talk remotely.

One topic he mentioned was derangements. Jordan proved in the nineteenth century that a finite transitive permutation group on a set of size bigger than 1 contains a derangement, an element with no fixed points. Since the derangements form a union of conjugacy classes, a finite simple group (in any transitive permutation action) is generated by its derangements. Aner announced that he and his coauthors (Michael Larsen and Pham Huu Tiep) were close to a proof that, if the simple group is sufficiently large, then any element of the group is the product of two derangements. The proof has subsequently been completed, and the paper is on the arXiv.

In the discussion, Michael Giudici mentioned a result that he, together with Rosemary Bailey, Gordon Royle, and me, have had on the back burner for a few years now, because we are stuck on one seemingly small point. But I see no harm in announcing here what we have been able to do. (We started work on this when Rosemary and I visited Perth in 2016: I was recovering from shingles, and had just had a few weeks’ holiday in Adelaide, where I did a little side project on the voyage of Nicolas Baudin reported here and in two preceding posts.)

I have discussed derangements before, for example here, but not this particular aspect.

The basic set-up

First, a finite transitive permutation group G actually contains many derangements. Arjeh Cohen and I showed that, if the group acts on n points, then at least a fraction 1/n of the elements of the group are derangements. More relevant here is a discussion of the subgroup of G generated by derangments. In 1982, H. Zantema (who I think was a student of Arjeh Cohen) published a 50-page paper in Manuscripta Mathematica entitled “Integer valued polynomials over a number field”. To stress once again that there are important connections between number theory and derangements, the paper contains a proof of the following theorem. I will use D(G) for the subgroup of the finite transitive permutation group G which is generated by the derangements in G.

Let G be a finite transitive permutation group of degree n>1. Then D(G) is transitive and contains every element of G whose number of fixed points is different from 1.

I will give the proof, since it follows easily from the Orbit-Counting Lemma (asserting that the average number of fixed points of elements of a finite permutation group is equal to the number of orbits of the group). Let G be a transitive permutation group. Then ∑_G(fix(g)−1) = 0, where fix(g) is the number of fixed points of g. Let H = D(G), and suppose that H has d orbits. Then ∑_H(fix(g)−1) = (d−1)|H|. So ∑_G\H(fix(g)−1) = −(d−1)|H|. But this sum is non-negative, since all the elements g with fix(g)−1 < 0 have been included in H. We conclude that d = 1 and that every element g in G\H has fix(g) = 1.

My coauthors and I added an extra piece to this: D(G) permutes semiregularly the set of G-orbitals (the orbits of G on ordered pairs of distinct elements).

From this we see that the index of D(G) in G divides n−1, with equality if and only if G is sharply 2-transitive.

The easiest examples of groups G with D(G) ≠ G are Frobenius groups, transitive (but not regular) permutation groups in which the stabiliser of any two points is the identity. Frobenius showed that, in such a group, the identity and the derangements form a normal subgroup, the so-called Frobenius kernel. Thus, in this case, D(G) is the Frobenius kernel, and G/D(G) is isomorphic to the Frobenius complement (the one-point stabiliser).

This is already enough to draw one conclusion: for any Zassenhaus group G, we have D(G) = G. (A Zassenhaus group is a 2-transitive group in which the 3-point stabilisers are trivial but the 2-point stabilisers are not.) Suppose for a contradiction that G is a Zassenhaus group with D(G ≠ G. If H is the 1-point stabiliser, then H∩D(G) is a proper subgroup of H, and all the elements of H outside this subgroup are derangements (since they fix only the point stabilised by H); so H is generated by these derangements, thus H = D(H). But H is a Frobenius group; so this contradicts Frobenius’ Theorem.

We conjectured that, if G is not a Frobenius group, then the index of D(G) in G is at most √n−1. This is true if G is imprimitive, or if it is primitive but not of affine type. As I will explain below, the affine type is the most mysterious …

But that is not what I want to explain here.

Frobenius complements

The structure of Frobenius groups is now well understood. A famous theorem of Thompson shows that the Frobenius kernel must be nilpotent. The possible Frobenius complements were determined by Zassenhaus. There is a detailed account of this in Passman’s book Permutation Groups; I used to have a copy but alas it disappeared some time ago. A Frobenius complement is either metacylic (that is, has a cyclic normal subgroup with cyclic quotient) or has a subgroup of index at most 2 which is a direct product of SL(2,3) or SL(2,5) with a metacyclic group of odd order.

I will say a bit more about this. A group H is a Frobenius complement if and only if it acts as automorphisms of a group N so that non-identity elements of H fix only the identity of N. By Thompson’s theorem, N is nilpotent, so it has a characteristic elementary abelian subgroup T, on which H acts. Thus we can assume without loss of generality that N is elementary abelian, so that H is a linear group over a finite prime field. Linear groups will reappear later …

Here is a proof that a Frobenius complement has at most one element of order 2. Remember that elements of the Frobenius complement act as automorphisms of the Frobenius kernel. So the claim is that an automorphism of order 2 of a finite group, which fixes only the identity, must be the inversion map.

This is proved by a nice two-step argument. Let α be an automorphism of G. For the first step, assume that α fixes only the identity. Consider the map that takes g to g⁻¹.gα. This is one-to-one; for if g⁻¹.gα = h⁻¹.hα, then hg⁻¹ = (hg⁻¹)α, and so by assumption g = h. Since G is finite, this map is onto, so every element is of the form g⁻¹.gα.

For the second step, we assume that α has order 2. Then applying α to g⁻¹.gα, we see that

(g⁻¹.gα)α = g^−α.g = (g⁻¹.gα)⁻¹,

so α maps every element of G to its inverse.

Incidentally, a group having such an automorphism must be abelian (of odd order), since

gh = (h⁻¹g⁻¹)⁻¹ = (hα.gα)α = hg.

Now groups G with a unique involution have cyclic or generalized quaternion Sylow 2-subgroups, so if Z is the central subgroup of order 2, then G/Z has cyclic or dihedral Sylow 2-subgroups. Conversely, a group with cyclic or dihedral Sylow 2-subgroups has a unique central extension by a group of order 2 which contains a unique involution. This is discussed here.

But Frobenius complements are much more restricted, as described in the result mentioned earlier.

But that’s not all

The vast majority of transitive groups up to degree 47, or primitive groups of degree up to 4095, satisfy D(G) = G. Of those which don’t, a considerable number are Frobenius groups, and almost all the rest have the quotient G/D(G) isomorphic to a Frobenius complement.

But before we could make a serious conjecture along these lines, we found two primitive groups of degree 625 where this was not so; in one of them, the quotient was the Klein 4-group, in the other the symmetric group of degree 3.

So we are left with the question:

Which finite groups H can occur as G/D(G) for some finite permutation group G?

Note in passing that this is an “inverse problem” in group theory of the sort that Carlo Casolo and I, along with João Araújo and Francesco Matucci, were working on just before Carlo’s untimely death in March.

While we were in the Isaac Newton Institute before the shutdown, Michael Giudici and I managed to find an explanation for some of these examples, and to give a construction which produces more examples. However, we are very far from being able to show that every finite group arises. In fact, all our examples are quotients of Frobenius complements, and we are tempted to conjecture that this is the answer.

I will give a brief hint. The paper will go on the arXiv soon, and I will provide the link.

An extension to the Orbit-Counting Lemma

The Orbit-Counting Lemma asserts, in particular, that the average number of fixed points of elements of a finite transitive permutation group G is 1. More generally, the same holds for the elements of any coset of G in the symmetric group.

Here is the proof; it is only a very slight modification of the proof of the original. I give the proof for left cosets; note that any right coset Gt of a transitive group G is a left coset of another transitive group, namely t(t⁻¹Gt).

Count pairs (a,g) with a∈Ω (the permutation domain) and g∈G such that atg = a. For each of the n choices of a, there are |G|/n elements g mapping at to a. So there are |G| such pairs. But, counting the other way, we get the sum of the numbers of fixed points of the |G| elements of the coset tG.

Affine groups

Let V be a finite vector space. An affine group on V is a group of transformations of the form v → vt+c, where c∈V and t∈H, where H is a group of linear maps on V. This group is a semidirect product of the additive group T of V by H.

Let G = T.H be an affine group. Certainly all the non-zero translations are derangements, so T ≤ D(G). By the extended Orbit-Counting Lemma, the average number of fixed points of the elements of a coset Th is 1, so there are two possibilities:

• Th contains a derangement, whence t∈D(G);
• every element of Th has exactly one fixed point. In particular, h fixes no non-zero vector, and so does not have 1 as an eigenvalue.

The conclusion is that, if R(H) is the subgroup of H generated by elements which have an eigenvalue 1, then D(G) is the semidirect product T.R(H).

Thus our questions for affine groups are equivalent to the following question for linear groups:

Let H be a linear group on a finite vector space V, and R(H) the subgroup of H generated by elements having eigenvalue 1. What can be said about

• the index |H:R(H)|,
• the structure of H/R(H)?

An example

We found a number of examples, including an infinite family. I will just present one here.

Let V be the tensor product of two 2-dimensional vector spaces over the field of five elements. Thus |V| = 625. Let H be the central product of the dihedral group of order 12 acting on the first factor and the quaternion group of order 8 acting on the second.

In the dihedral group of order 8, non-central involutions all have eigenvalues 1 and -1, the other non-central elements do not have eigenvalues in the field of order 5. In the quaternion group, the eigenvalues of the non-central elements are fourth roots of unity in the field. We get the eigenvalues of elements of the central product by multiplying eigenvalues of the constituents. Thus we see that the elements of the dihedral group lie in R(H) while those of the quaternion group (outside the centre) do not. So H/R(H) is the Klein group.