Perth, week 1

The first week of the visit is over. The weather has been quite cold, but it is likely to improve as time goes on. The best day so far was yesterday, when we went to Yanchep National Park and had a very pleasant walk. More on this later.

This week, I gave a colloquium talk on “The random graph and its friends“, and Rosemary a seminar talk on “Circular designs balanced for neighbours at distances one and two“.

In addition, we got started on some research. I will just highlight one of the stories here.

In our first meeting, Michael reported that, after he had talked about derangements in Iran, he had been asked to what extent the derangements in a transitive group determine the group.

Jordan proved in 1872 that a finite transitive permutation group of degree n > 1 necessarily contains a derangement (an element with no fixed points). In fact it contains many derangements: Arjeh Cohen and I proved in 1992 that at least a fraction 1/n of the elements of the group are derangements. But I vaguely remembered seeing, at some time in the distant past, a theorem that said:

Let G be a transitive finite permutation group of degree greater than 1, and H the subgroup generated by the derangements in G. Then:

  • H is transitive;
  • H contains all elements of G for which the number of fixed points is different from 1.

Now my memory is not failing too badly: I was able to find a reference, Lemma 6.3 in a paper by H. Zantema, “Integer valued polynomials over a number field”, Manuscripta Math. 40 (1982), 155–203. But, before I did that, I was able to reconstruct the proof, and to add a bit more: with the same hypotheses,

  • G/H acts semiregularly on the H-orbits on ordered pairs of distinct points (equivalently, G1/H1 acts semiregularly on the H1-orbits different from {1}, where the subscript 1 means the stabiliser of the point 1).

In this form we see that Frobenius groups form a special case. In a Frobenius group G, every non-identity element fixes 0 or 1 point; the theorem of Frobenius states that the derangements together with the identity form a normal subgroup H. In this case, H1 is the trivial group, and its orbits are just the points; by definition, G1 permutes them semiregularly. So Frobenius groups give examples with H a proper subgroup of G.

Here is the proof of the theorem. Let π(g) be the number of fixed points of the permutation g. Suppose that the subgroup H generated by the derangements has d orbits.

By the Orbit-Counting Lemma,

∑ {π(g)−1 : gG} = 0,
∑ {π(g)−1 : gH} = (d−1)|H|.


∑ {π(g)−1 : gG\H} = −(d−1)|H|.

In this equation, the left-hand side is at least zero (since the only permutations giving negative contributions are the derangements, which are all in H), whereas the right-hand side is at most zero. So both must be zero, from which we conclude that d = 1 and also that all elements with π(g) ≠ 1 are in H.

For the last part, we use a slight variant. Let rG and rH be the permutation ranks of G and H, the numbers of orbits on ordered pairs. Then

∑ {(π(g)−1)2 : gG} = (rG−1)|G|,
∑ {(π(g)−1)2 : gH} = (rH−1)|H|.

Since all elements of G for which the summand is non-zero are in H, the two sums are equal. We conclude that

(rG−1)|G : H| = rH−1,

from which the second part of the theorem follows easily.

There are other examples apart from Frobenius groups. The unique almost-simple doubly transitive group with a non-2-transitive socle, PΓL(2,8) (degree 28), has the property that its derangements generate PGL(2,8), a subgroup with index 3; the three orbitals are permuted transitively by the field automorphism.

We expect to have substantially more to report on this problem soon!


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s