Nearly two years ago, I posed the problem of finding an “elementary” deterministic polynomial-time algorithm for finding a fixed-point-free element (or derangement) in a transitive permutation group. The background is that there are so many fpf elements (at least a fraction 1/n of the group, where n is the degree) that finding one by choosing elements at random works very well; and Emil Vaughan gave a deterministic algorithm which is rather complicated and requires the classification of finite simple groups to prove its correctness.
This month, Vikraman Arvind from Chennai posted a paper on the arXiv solving this problem. It is such a pretty solution that I’d like to discuss it here.
Average number of fixed points over a coset
The Orbit-Counting Lemma says that the average number of fixed points of elements in a permutation group is equal to the number of orbits of the group. In particular, in a transitive group, the average number is 1. (This immediately gives Jordan’s theorem: if the degree is greater than 1, then the identity fixes more than one point, and so some element fixes fewer than one point.) What is not as well known as it should be is that, if G is transitive, then any coset Gh of G in the symmetric group has the property that the average number of fixed points is 1.
The proofs are always the same: we count pairs (x,g) where x is a point, g an element of G, and xg = x, in the case of a subgroup, or xgh = x (in the case of a coset). The answer is |G| times the average number of fixed points; but it is also the sum, over all points x, of the order of the stabiliser of x (in the subgroup case), or the number of elements of G mapping x to xh−1 (in the case of a coset). The sum of these orders over all elements in an orbit is equal to |G|, by the Orbit–Stabiliser Theorem.
What about a coset of an intransitive group? There is no definite value for the average in this case; but Arvind points out that we can compute it efficiently. If xh−1 is not in the G-orbit containing x, then there are no elements g with the required property; if it is, then these elements form a coset of the stabiliser of x, so the number of them is equal to the order of this stabiliser, which of course is |G| divided by the orbit size.
So to compute the average number of fixed points of an element in a coset Gh, we sum, over all points x such that xh−1 lies in the G-orbit of x, the reciprocal of the size of this orbit.
Given generators for G, the orbits can be calculated efficiently, and the whole procedure is simple.
Finding a derangement
A step in the Schreier–Sims algorithm takes generators for a permutation group G and a point x, and finds, in polynomial time, coset representatives for the stabiliser of x in G, and generators for this stabiliser.
Using this, if we are given a coset Gh of G for which we know the average number of fixed points, we an choose a point x not fixed by G, split Gh into cosets of the stabiliser of x, and compute the average number of fixed points in each coset.
Hence we can choose a coset of the stabiliser for which the average number of fixed points does not exceed the average in Gh.
This is the main step in Arvind’s argument. Starting with a transitive group G, we successively fix points and choose cosets such that the average number of fixed points is non-increasing. Eventually the coset consists of a single element.
In the transitive group, the average is 1. At the first step, it decreases strictly: for the stabiliser has at least two orbits, so the average over the stabiliser is at least 2; thus there is some coset for which the average is less than 1.
So, when we reach a singleton coset, its unique element has strictly less than 1 fixed point; it is the required derangement.