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.
Looking at your list of exceptions:
131, 191, 239, 251, 311, 419, 431, and 491
Take the ones congruent to 11 mod 60, not just mod 12:
11,71,131,191,251,311,431,491.
Apart from the first two (like the 1 mod 3 case), and 371 which isn’t prime, they are all on the list. In this case it seems that there exist consecutive primitive n/5th roots of unity, where n=p-1.
This only leaves 239 and 419. Erm, come back to this one later!
Professor, are you aware of any work on the minimum cardinality of k-transitive sets of permutations (non-sharp, non-group)?
I do have something to say about this, but I think a new post is the right place for it…
Too hasty, too hasty…
(k−1,k)-set transitivity implies (k−2,k−1)-set transitivity (for k≤(n+1)/2) with the exception of the 2-dimensional affine group over GF(3) and its subgroup of index 2, which are (4,5)-set transitive but not (3,4)-set transitive. This has a curious consequence for the semigroup theory. I hope that everything will be in order before the paper is submitted!
The paper is now on the arXiv, 1204.2195.
Sequence A270596 of the OEIS now lists the first 1983 terms of the sequence you defined here.
Thank you!