João Araújo and I have been working together this week, and the paper, which I discussed here, is nearly ready to submit, after we managed a couple of quite significant improvements.
I’d like to draw attention to a couple of puzzles that arise here.
Variants of k-set transitivity
A permutation group is k-set transitive, or k-homogeneous, if any subset of the domain of size k can be carried to any other such subset by an element of the group. Since k-set transitivity is equivalent to (n−k)-set transitivity, we may assume that k ≤ n/2. With this condition, Livingstone and Wagner, in one of my favourite papers, proved that, if G is k-set transitive, then
- G is (k−1)-set transitive;
- if k ≥ 5, then G is k-transitive;
where k-transitivity means that one k-set can be mapped to another in any prescribed order.
We consider two related concepts:
- G is (k−1,k)-set transitive if any (k−1)-set can be mapped inside any k-set by an element of G;
- G has the k-universal transversal property if, given any k-set S and any partition π with k parts, S can be mapped to a transversal (a section) of π by an element of G.
Now two corollaries of our results are analogues of the first part of the Livingstone–Wagner theorem, as follows. Let k ≤ (n−1)/2, and suppose that G is a permutation group of degree n. Then:
- if G is (k−1,k)-set transitive with k > 1, then G is (k−2,k−1)-set transitive;
- if G has the k-universal transversal property, then it has the (k−1)-universal transversal property.
The second of these results is significant for semigroup theory, as we explain in the paper.
Our proofs depend on the classification of the groups with these properties, via the Classification of Finite Simple Groups.
Problem: Find direct proofs of the above assertions, perhaps along the lines of the Livingstone–Wagner theorem.
In fact, we only require the classification of (k−1,k)-set transitive groups, which turn out to be (k−1)-set transitive with a few small exceptions (of degree at most 9). For the k-universal transversal property implies (k−1,k)-set transitivity, which implies (k−1)-set transitivity with a few small exceptions; clearly (k−1)-set transitivity implies the (k−1)-universal transversal property.
But even the proof of this uses the list of 2-transitive groups, which depends on CFSG.
A number-theoretic problem
In connection with the 1-dimensional affine groups over prime fields, we came up with the following problem, which I mentioned in the earlier post, but missed a rather obvious fact.
Problem: For which primes p does there exist a non-zero element c∈GF(p) such that the elements c, c−1, and −1 generate a proper subgroup of the multiplicative group?
Any prime congruent to 1 (mod 3) and greater than 7 has this property: for if c is a primitive 6th root of unity, then c−1 is a primitive cube root of unity, and so the three elements lie in a subgroup of order 6.
Also, any prime congruent to 1 (mod 4) and greater than 5 has the property. For −1 is a square; if there are two consecutive squares c−1 and c, then all three lie in the subgroup of squares. Could there be no two consecutive squares among 1,2,…p−1? Since there are equally many squares and non-squares, and the first and last are squares, this would imply that squares and non-squares alternate except for one pair of consecutive nonsquares. But any two consecutive integer squares less than p are an odd number of steps apart, so there must be a consecutive pair of non-squares between them. This implies that p is smaller than 9, that is, p = 5.
This leaves only primes congruent to 11 (mod 12). Most of these fail to have the property, but there are some exceptions; those less than 500 are 131, 191, 239, 251, 311, 419, 431, and 491.