Between transitive and primitive, 2: results

Partitions and the partition lattice

The partitions of a set Ω are partially ordered by refinement: Π₁ is below Π₂ if every part of Π₁ is contained in a part of Π₂. With this order, they form a lattice; the infimum or meet of two partitions is the partition whose parts are all non-empty intersections of a part of the first with a part of the second, and the supremum or join is the partition in which the part containing a point α consists of all points that can be reached from α by taking steps alternately within a part of each of the two partitions. The greatest element is the universal partition U with a single part, while the smallest is the partition E whose parts are singletons.

Now let G be a transitive permutation group on Ω. The set of G-invariant partitions has the following properties:

• it is a sublattice of the partition lattce;
• it contains U and E;
• all of its elements are uniform, that is, have all parts of the same size.

This is a situation which has been studied in experimental design in statistics, the partitions corresponding to factors which are likely to affect the experimental result. But statisticians like their factors to be orthogonal, and so add an extra condition:

• the equivalence relations corresponding to the partitions commute.

This has the effect that the part containing α of the supremum of two partitions is found by taking a step within a part of one and then a step within a part of the other (in either order); no further steps are required. This condition implies that the lattice satisfies the modular law, but not conversely. (The modular law states that, if a≤c, then a∨(b∧c) = (a∨b)∧c.)

I note in passing that commuting is not itself enough to imply nice properties for general equivalence relations. Statisticians associate a vector space with each partition, the functions which are constant on its parts (the effect of that factor), and want the orthogonal projections onto these subspaces to commute; only if the partitions are uniform does this reduce to commutativity of the relations.

A set of partitions satisfying these four conditions is called an orthogonal block structure.

Permutation groups

We will say that a transitive permutation group G on Ω has the OB property if its invariant partitions form an orthogonal block structure.

This may look a bit unmotivated in the permutation group context, but it turns out to be surprisingly common: of the 1954 transitive groups of degree 16, in 1886 of them the invariant partitions form an orthogonal block structure.

This raises the first of many open questions: What proportion of transitive groups have the OB property? How does it behave for large degree? In particular, characterise the degrees for which every transitive group has the OB property. (This set includes all primes, as well as numbers such as 15, 33 and 35.)

This can be looked at another way. If G is transitive, the lattice of invariant partitions is isomorphic to the lattice of subgroups containing the stabiliser of a point α in Ω. The correspondence works like this: to a partition Π corresponds the setwise stabiliser of the part of Π containing α. Thus G has the OB property if and only if the subgroups containing G_α commute (in the sense that HK = KH).

In particular, a regular group has the OB property if and only if any pair of its subgroups permute. These groups are determined by a theorem of Iwasawa. They are nilpotent, and there are only a few possibilities for the Sylow subgroups.

Another consequence is that, since normal subgroups commute, a pre-primitive permutation group (as described in the preceding post) has the OB property.

Distributive lattices, generalised wreath products, and the PB property

A lattice is distributive if, for all a,b,c, we have a∨(b∧c) = (a∧b)∨(a∧c).

The distributiive law is equivalent to its dual (with ∧ and ∨ interchanged) and implies the modular law. Every finite distributive lattice is isomorphic to a sublattice of the Boolean lattice of subsets of a set. More precisely, an element of a lattice is called join-indecomposable or JI if it cannot be written as the join of two smaller elements. Now the non-zero JI elements of a distributive lattice L form a poset P, and conversely, the down-sets (sets closed downwards in the order) in a poset form a distributive lattice; these constructions are mutually inverse.

Statisticians have also been interested in orthogonal block structures satisfying the distributive law. Such a structure can be built from a finite poset P with a finite set associated to each point of P; the set Ω is the Cartesian product of these subsets. The order is a little complicated so I won’t describe it here. A distributive orthogonal block structure is called a poset block structure because of this construction.

A feature of poset block structures is that they all have large and precisely describable automorphism groups, unlike general orthogonal block structures. The latter include structures built from Latin squares: Ω is the set of cells of the square, and the partitions other than U and E correspond to rows, columns and letters. Automorphisms are just isotopisms of the Latin square (permutations of rows, columns and letters preserving the structure), and it is known that almost all Latin squares have no non-trivial isotopisms.

By contrast, there is a notion of generalised wreath product of a family of transitive permutation groups indexed by a poset P, which includes the direct product (in its product action) if P is a 2-element antichain, and the wreath product (in its imprimitive action) if P is a 2-element chain. Now it can be shown that the automorphism group of a poset block structure is the generalised wreath product of symmetric groups on the sets associated with the elements of P.

We say that a permutation group G has the PB property if its invariant partitions form a poset block structure. Thus, we see that a group with the PB property is embeddable in a generalised wreath product of symmetric groups.

In fact, a stronger embedding theorem is true. A classical result of Krasner and Kaloujnine states that an imprimitive permutation group G is embeddable in the wreath product of the group induced by the stabiliser of a block on the points of the block with the group induced by G on the set of blocks. Motivated by this, we show that, given a permutation group G with the PB property, with associated poset P, we can associate a group G*(p) with each element p in P in such a way that G is embeddable in the generalised wreath product of these groups over P.

I will say a little more about the embedding. Given a group G with the PB property, there is one obvious choice for a subgroup G(p). The element p of the poset corresponds to a join-indecomposable non-zero partition Π in the lattice. There is then a unique partition Π⁻ maximal with respect to being finer than Π. We could put G(p) to be the group induced by the stabiliser of a part of Π on the set of parts of Π⁻ it contains. This is exactly what happens in the KK theorem. Unfortunately, examples show that it doesn’t work in general, so we need something more complicated. There is a unique coarsest partition Γ satisfying Γ∧Π = Π⁻; we take the group induced by a part of Γ∨Π on the parts of Γ it contains. This is the group G*(p) of the theorem.

We have also looked at what happens if we have more than one poset. Given a family of groups on an index set M, the map from posets on M to the corresponding generalised wreath products preserves intersection and inclusion, where the relations on posets are on the subsets of M² forming the order relations. This implies that any generalised wreath product is the intersection of the iterated wreath products over the linear extensions of the posets.

There is lots more in the paper, including a detailed history of orthogonal block structures, but that is enough for an overlong post.