The first mathematics book that I read really seriously was Helmut Wielandt’s Finite Permutation Groups. So I have known the definition of a primitive permutation group for more than forty years. But there is still more to learn. My recent interest in semigroups has shown me two more equivalent definitions. I’ll make a list here; I am sure I have missed a few.
Let G be a permutation group on a finite set Ω. I will assume that |Ω| > 1. I also will assume that G acts transitively on Ω. (In fact, without this assumption, the only extra group that arises is the trivial group acting on two points. This is of great theoretical importance, for example in the O’Nan–Scott Theorem, but can be ignored here without loss.
Now the following conditions are all equivalent. The first is what I take to be the definition of primitivity, though other people use different definitions. Indeed, Wielandt used the third condition as the definition.
- The only equivalence relations on Ω preserved by G are the relation of equality and the universal relation.
- The only G-invariant partitions of Ω are the partition into singletons and the partition with a single part.
- The only subsets Δ of Ω which satisfy Δg=Δ or Δg∩Δ=∅ for all g∈G are the empty set, singletons, and the whole of Ω.
- The stabiliser of a point of Ω is a maximal proper subgroup of G.
- Every non-null G-invariant graph on Ω is connected.
- For any 2-element subset A of Ω and any 2-part partition P of Ω, there exists g∈G such that Ag is a transversal to P.
- For any map f : Ω→Ω of rank n−1 (where n = |Ω|), the semigroup generated by G and f contains an element of rank 1. (Here the rank of a map is the cardinality of its image.)
A word about the equivalences. The equivalence of the first two has nothing to do with groups; it is the basic connection between equivalence relations and partitions. For the third, call a subset Δ a block if Δg=Δ or Δg∩Δ=∅ for all g∈G. Then any equivalence class of a G-invariant partition is a block; and conversely, if Δ is a block, then so is any translate of Δ, so the translates form a G-invariant partition.
The equivalence of the fourth condition with the others is a standard result. If there is a subgroup H of G strictly between the stabiliser of x and the whole group, then the H-orbit of x is a block; conversely, the stabiliser of a block contains the stabiliser of any of its points.
The fifth condition is Donald Higman’s test. If a G-invariant graph is disconnected, then its connected components give a G-invariant partition. Conversely, if G fixes a partition, then it preserves the disjoint union of complete graphs on the parts of the partition.
The sixth condition is trivially equivalent to the fifth. A graph is connected if and only if, given any 2-part partition, there is an edge which has one end in each part.
Finally, the seventh condition is a theorem of Rystsov. The simplest proof depends on a connection between graphs and transformation semigroups which I have mentioned before:
Theorem A transformation semigroup on Ω contains no element of rank 1 if and only if it is contained in the semigroup of endomorphisms of some non-null graph on Ω. Moreover, this graph can be chosen to have clique number equal to chromatic number.
Now suppose that the semigroup generated by G and f contains no map of rank 1. Then it is contained in the endomorphism semigroup of a graph X. If f has rank n−1, then it collapses two points v,w to the same point x; all other points are mapped bijectively by f. Since f is an endomorphism, {v,w} is a non-edge; so all the neighbours of v are mapped bijectively to the neighbours of x, and so are the neighbours of w. Thus v and w have the same neighbour set. The relation “same neighbour set” is then a G-invariant equivalence relation, and G is imprimitive.
For the converse, suppose that G is imprimitive; then it preserves a complete multipartite graph whose parts form the G-invariant partition. Then the map which collapses two points in the same part and fixes everything else is an endomorphism of this graph; and the semigroup of endomorphisms contains no element of rank 1.
The importance of primitivity in permutation group theory is that there is a reduction theorem for transitive but imprimitive groups; such a group can be embedded in the wreath product of two smaller groups (the group induced on a block by its setwise stabiliser, and the group induced by G on the set of parts of the corresponding partition.)
One of the reasons for wanting multiple definitions of some concept is that they may generalise in different ways. How could the above definitions be generalised?
One way is to allow Ω to be infinite. The first six statements remain equivalent, and provide the definition of primitivity for an infinite permutation group. For the last, there are various problems which I won’t address here.
Wielandt pointed out that there is a strengthening of primitivity for infinite groups, which he called strong primitivity: a permutation group G on Ω is strongly primitive if there is no G-invariant reflexive and transitive relation on Ω except for the two trivial equivalence relations. There are versions of the fourth and fifth conditions which are equivalent to this. A group G is strongly primitive if the stabiliser of a point is a maximal proper sub-semigroup of G. And G is strongly primitive if and only if every G-invariant directed graph is strongly connected.
(Here, a digraph is connected if the underlying graph, forgetting directions, is connected; it is strongly connected if there is a directed path between any two vertices. Thus, a city with one-way streets is connected if you can walk from any point to any other, and strongly connected if you can drive from any point to any other. Exercise: Show that a finite vertex-transitive connected digraph is strongly connected.)
One can also define a permutation group G to be strong if every reflexive and transitive G-invariant relation is symmetric; then a group is strongly primitive if and only if it is strong and primitive. An example of a strong group is one which is generously transitive, that is, any two points can be interchanged by some element of the group.
Another variant is to allow a parameter in the definition.
Let t be a positive integer with t < |Ω|−1, and let G be a t-transitive permutation group on Ω. Consider the following three definitions.
- G is t-primitive if the stabiliser of t−1 points acts primitively on the remaining points.
- G is t-set primitive if it acts primitively on the set of t-element subsets of Ω.
- G is t-Steiner primitive if the only subsets Δ of Ω which satisfy Δg=Δ or |Δg∩Δ|<t for all g∈G are subsets of cardinality at most t or the whole of Ω.
It is clear that all three concepts reduce to primitivity when k=1. The first is a standard definition due to Wielandt, which he used to refine Jordan’s work on normal subgroups of multiply-transitive groups.
The reason for the name “t-Steiner primitive” is that, if this condition fails, so that some set Δ of size k strictly between t and n=Ω satisfies the hypothesis, then the images of Δ under G are the blocks of a Steiner system S(t,k,n). Now t-primitivity and t-Steiner primitivity each imply t-set primitivity: if G preserves a Steiner system S(t,k,v), then the “blocks” of the Steiner system containing a given t−1 points are blocks of imprimitivity for the stabiliser of these points; and the t-sets contained in a particular “block” of the Steiner system form a block of imprimitivity for G acting on t-sets.
It is not clear how to put a parameter into the fourth and fifth conditions. It can be done with the last two, but the situation is rather different. This is, in part, the subject of two recent preprints of mine with João Araújo, the second also with Jorge André (and not yet ready for public consumption).
Say that a permutation group G has the t-universal transversal property if, given any t-set A and any t-part partition P, there is an element g∈G such that Ag is a transversal for P. As we saw above, the 2-universal transversal property is equivalent to primitivity; but, for higher t, the groups with this property were almost completely classified in the paper 1204.2195 on the arXiv.
For the last condition, one possible generalisation would be to consider groups G with the property that, if f is any map of rank (at least) n−t, then the semigroup generated by G and f contains an element of rank 1. We were able to show that every primitive group has this property for t=2, and conjecture that the same holds for all t up to n/2. The main tool in the proof is again the theorem about graph endomorphisms.
João has a more general conjecture: if G is a primitive group and f a non-uniform map (that is, the inverse images of points in the image don’t all have the same size), then the semigroup generated by G and f contains an element with rank 1. We were able to prove a few more cases of this; it is true if the rank of f is at most 4.
The earlier theorem shows that the conjecture is really about the possible endomorphisms of primitive graphs.