A thrifty algorithm

Two important classical parameters of a permutation group G of degree n are

• the base size, the smallest size of a collection of points whose pointwise stabiliser is the identity; and
• the minimal degree, the smallest number of points moved by a non-identity element of the group.

There are a number of connections between these parameters. First, n minus the minimal degree is the largest size of a collection of points whose pointwise stabiliser is not the identity. Second, any set whose pointwise stabiliser is the identity must intersect the support of any non-identity element of the group. So in a transitive group, it follows that the product of base size and minimal degree is at least n (though usually this bound is far from being tight).

In a lovely paper in 1992, Kenneth Blaha gave a greedy algorithm for estimating the base size. To see how it works, consider how you would find a base for a permutation group. Run a calculation which maintains a pair (H,L) where H is a subgroup of G and L a list of points. Start with H = G and L the empty list. Then choose a point x not in L; add x to L and replace H by the subgroup of H stabilising x. When we reach the point where H is the trivial group, L will be a base.

The index of each subgroup in the preceding one is the size of the H-orbit containing x. So there is an obvious “greedy algorithm”: to get down to the bottom quickly, make each step as large as possible; in other words, choose each new point in an orbit of maximum size for the stabiliser of its predecessors.

Blaha’s lovely result is that, while this does not compute the exact result, it overestimates only by a factor log log n.

Moreover, for primitive groups, it appears to do even better, never overestimating by more than a constant factor. The constant might be 9/8+o(1) as the base size goes to infinity: this value is achieved by the symmetric group of degree m acting on the set of 2-element subsets of {1,…,m}, which has base size about 2m/3, but where the greedy algorithm finds a base of size about 3m/4. (I noticed this many years ago; maybe more is known now. If there is a base of size 2, the greedy algorithm will find it; and thanks to the work of Tim Burness and collaborators, we now know that this is the case for almost simple primitive groups with “known” exceptions. Nick Cavenagh found an example of a primitive group with base size 3, where the greedy algorithm finds 4.)

What about the minimal degree? Computing this in a general permutation group seems quite difficult. The brute force method simply looks at all elements of the group and counts the size of their supports. One could be more clever and do a backtrack search. But can we get a Blaha-like bound?

Let us try the opposite of Blaha’s approach, the thrifty algorithm, where each new point is chosen in the smallest orbit of the stabiliser of the preceding points. This will produce a rather large base. But consider fixing the last base point. The subgroup H has the property that the stabiliser of a point in its smallest orbit is trivial; so all the orbits have the same size, and H acts regularly on them. This means that there is an element whose support size is nb+1, where b is the base size found by the thrifty algorithm. So this number is an upper bound for the minimal degree.

How close is it?

I tried a few small examples, and found it seemed to be giving the right answer. But a little further thought produced an example in which it is a long way off.

Consider the direct product of m copies of the cyclic group of order 2. Let this group act on 2m−1+2m points as follows. There are m orbits of size 2, one for each generator; the corresponding generator transposes the points in that orbit and fixes the points in the others. Then there is an orbit of size 2m−1, on which the kernel of the action consists of the identity and the product of all the generators, and the quotient acts regularly. The thrifty algorithm finds a base of size 2m−1, by fixing all but one of the points in the short orbits; so it gives the estimate 2m−1+2 for the minimal degree. But the true minimal degree is 2m, realised by the product of the generators. So the algorithm fails by an exponential margin.

What about primitive groups?

A quick search using GAP found that, up to degree 31, the thrifty algorithm gives the right answer for all but three groups, where it is out by 1 or 2. The limiting factor in the search was the brute force approach to the true minimal degree. Maybe someone has written a better algorithm for this parameter and could push the search further.

So to end with a question:

Does the thrifty algorithm overestimate the minimal degree by a constant factor in primitive groups? Perhaps even by an additive constant? Could it even be exact in almost all cases??

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

4 Responses to A thrifty algorithm

1. The final speculation is almost certainly false, and the second one quite dubious. With an improved minimal degree algorithm I checked primitive groups up to degree 63 and found that the thrifty algorithm could overestimate by as much as 6 for groups in this range.

2. Jon Awbrey says:

Groups like $Z_2^m$ acting on the space of $2^{2^m}$ boolean functions on $m$ variables come up in my explorations of differential logic.

I’ve been having trouble posting links lately, so I will try to do that in a couple of separate comments.