The title is homage to the Gödel’s Last Letter and P=NP blog, which a week ago had a post entitled Two versus three.
At the problem session at the Banff meeting last night, Dugald Macpherson and Andras Pongracz posed various questions suggesting that, for permutation groups, there is a barrier between 3-transitivity and 4-transitivity.
Here is the background. A permutation group G on a set Ω is t-transitive if any t-tuple of distinct elements of Ω can be carried to any other such t-tuple by an element of G. It is t-set transitive if any t-element subset can be carried to any other by an element of G (but not necessarily in any prescribed order). (This condition is often called “t-homogeneous”, but I will avoid this because of confusion with the next concept.)
A relational structure R on Ω is said to be homogeneous if any isomorphism between finite substructures of Ω extends to an automorphism of Ω. According to a theorem of Roland Fraïssé, a countable homogeneous structure R is uniquely determined by its “age”, the class of finite structures embeddable into R. Fraïssé also gave necessary and sufficient conditions for a class of finite structures to be the age of a countable homogeneous structure. His theorem provides a very powerful method for constructing permutation groups of countable degree, and indeed is the essential link between permutation groups and recent developments in Ramsey theory and topological dynamics.
Now there are permutation groups of countable degree which are t-transitive but not (t+1)-transitive. For a simple example, take the homogeneous structure whose age is the class of all finite (t+1)-uniform hypergraphs. But here is some evidence of a barrier between 3 and 4:
- There are infinitely many finite 3-transitive groups other than symmetric and alternating groups, but only finitely many 4-transitive groups (the Mathieu groups).
- There are infinitely many groups which are sharply 3-transitive (that is, a unique group element carries any triple to any other), for example the groups PGL(2,F) for any field F. However, Jordan showed that the only finite sharply 4-transitive groups are S4, S5, A6 and the Mathieu group M11. Jacques Tits extended this to the infinite by showing in 1951 that there are no infinite sharply 4-transitive groups. Three years later, Marshall Hall showed that there are still no groups if we replace “a unique element” by “a finite odd number of elements”; after a quarter of a century, Yoshizawa deleted the word “odd” here.
- My first theorem about infinite permutation groups states that if a permutation group is t-set transitive for all t but fails to be t-transitive for some t, then it can be at most 3-transitive. The extreme case is given by the group of permutations of a circle which preserve or reverse the circular order.
- Samson Adeleke and Peter Neumann show that a group with a primitive Jordan set (a proper subset of Ω with the property that the pointwise stabiliser of its complement acts primitively on it) which fails to be t-transitive for some t can be at most 3-transitive.
The questions that Dugald and Andras asked were the following. Here R is a homogeneous relational structure with automorphism group G. We assume that G is 4-transitive.
- Is it possible for the age of R to contain no infinite antichain?
- Is it possible for the theory of R not to have the independence property? (This is a model-theoretic condition which Dugald didn’t define, so I won’t either.)
- Is it possible for the age of R to have the Ramsey property?
- Is it possible for the action of G on the space of dense linear orders of Ω to have a non-empty proper closed invariant subspace?
The suggestion is that here are four phenomena which can occur for 3-transitive groups but not for 4-transitive groups.