Permutation groups and regular semigroups

This week, I gave a talk in the Pure Mathematics seminar explaining what João Araújo and I have been up to this summer. I will try to summarise here.

João believes that semigroup theorists have shied away from studying the influence of the group of units of a monoid on the whole monoid. He believes that advances in finite group theory make it timely to consider finite semigroups from this point of view, and enlisted me to help.

Regular elements

A quasi-inverse of an element a of a semigroup S is an element b of S satisfying aba=a and bab=b. The element a is regular if it has a quasi-inverse, and the semigroup S is regular if all its elements are. The terminology is adapted from von Neumann’s terminology in ring theory in an obvious way: regularity does not depend on the additive structure.

To test whether an element is regular, we can cut a corner. If there exists b such that aba=a, then a is regular. For, let c=bab. Then aca=ababa=aba=a, and cac=bababab=bab=c.

João is interested in regular elements in transformation semigroups, and how they are related to the set of permutations in the semigroup (which form a permutation group). So let G be a permutation group on the n-element set Ω. The question is:

When is it true that a is regular in the semigroup ⟨G,a⟩ generated by G and a?

Now suppose that the element a has rank k. This means that its image is a set of size k, while its kernel is a partition with k parts. (The kernel of a map is the partition of its domain given by the inverse images of the points in the image.) Now our condition above on a turns out to be true if and only if there exists gG such that Im(a)g is a transversal for Ker(a). Since this is the key to what follows, I’ll give a proof.

Suppose first that Im(a)g is a transversal for Ker(a). Then ga induces a permutation on Im(a). Since this set is finite, there exists m such that (ga)m is the identity on Im(a). But this means that a(ga)m=a, so that a is regular in ⟨G,a⟩.

Conversely, suppose that a is regular in ⟨G,a⟩. Then aba=a for some b, necessarily of the form g1ag2agm-1agm. Now aba and a both have rank k, so no partial product can have smaller rank; this means that g1 maps Im(a) to a transversal for Ker(a).

João was interested in the question:

Which permutation groups G have the property that, given any map a of rank k (for some fixed k), a is regular in ⟨G,a⟩?

By what we just observed, this is exactly equivalent to asking:

Given k, which permutation groups have the property that, given any k-set K and any partition π with k parts, there exists gG such that Kg is a transversal for π?

Now this last question has no mention of semigroups, but is a kind of transitivity property for a permutation group. This is what we set out to solve. Such groups are said to have the kuniversal transversal property, or k-ut for short.


Given k, the permutation group G is k-transitive if it acts transitively on the set of all k-tuples of distinguished points; it is k-set transitive if it acts transitively on the set of k-element subsets. Now observe:

  • k-set-transitivity is equivalent to nk-set-transitivity for a permutation group on n points. So, without loss, we may assume that kn/2.
  • A k-transitive group is k-set transitive. Livingstone and Wagner gave a beautiful elementary proof of the converse for 5≤kn/2. Subsequently, Kantor, using more adanced group theory, determined all groups which are k-set transitive but not k-transitive for k=2,3,4.
  • It follows from the Classification of Finite Simple Groups (CFSG) that all k-transitive groups are known for k≥2. In particular, the only k-transitive groups for k≥6 are the symmetric and alternating groups. (There is no prospect of a proof without CFSG.)

Now say that a permutation group G is (k−1,k)-set transitive if, given a (k−1)-set A and a k-set B, there is an element of G which maps A to a subset of B. Clearly a (k−1)-set transitive group is (k−1,k)-set transitive; our main theorem is a near-converse. Note also that a group is (k−1,k)-set transitive if and only if it is (nk,nk+1)-set transitive; so we may assume without loss that k≤(n+1)/2.

Our theorem asserts:

Let G be (k−1,k)-set transitive. Then either G is (k−1)-set transitive, or G is one of five specific groups:

  • n=5, k=3, G is cyclic or dihedral of order 5 or 10;
  • n=7, k=4, G=AGL(1,7);
  • n=9, k=5, G=ASL(2,3) or AGL(2,3).

I won’t even attempt to give the proof; a rough sketch is that one shows that G is transitive, then G is primitive (doesn’t preserve a non-trivial partition of Ω), then G is 2-set transitive (since if not, then there is a G-invariant graph whose edges are a G-orbit on 2-sets); and finally we use the list of 2-set transitive groups.

The connection

The connection between the ut property and set-transitivity is:

If G has the k-ut property, then it is (k−1,k)-set transitive.

For if A and B have cardinalities k−1 and k, let π be the partition whose parts are the singletons corresponding to the elements of A and a single part containing everything else. If g maps B to a transversal to π, then obviously Bg contains A, so that Ag-1 is a subset of B.

Can we classify these groups? For k=2, there is no hope:

A group has the 2-ut property if and only if it is primitive.

If G does preserve a partition σ, let K be a pair of points in the same part of σ, and let π be a 2-part partition which coarsens σ; then no permutation can map K to a transversal of π. The converse is similar.

For k>2, then the group is 2-set-transitive, and so is one of groups on the classification of such groups. Some of these groups are k-ut; some are not; and at the moment, there are some for which we can’t decide. But we hope that, in the fairly near future, we will have a complete list of such groups.

An example illustrates the point. Let G=AGL(1,p), where p is prime, and k=3. Then G is 2-transitive, so every orbit on 3-sets has a representative of the form {0,1,u}. Now calculation shows that the set {0,1,x} lies in the same orbit if and only if x is one of the elements u, 1−u, u-1, 1-u-1, (1-u)-1, and u(u−1)-1. If it happens that, for some u, these six elements lie in a proper subgroup H of the multiplicative group of the integers mod p, then no element of this orbit is a transversal to the partition with parts {0}, H, and the rest; so G is not 3-ut.

In particular, for u=2, these six elements reduce to just three, namely 2, 1/2, and −1. If p is congruent to 1 mod 8, all of these are squares. So AGL(2,p) is not 3-ut for such p. However, there are other primes for which the 3-ut property does hold.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics and tagged , . Bookmark the permalink.

5 Responses to Permutation groups and regular semigroups

  1. Benjamin Steinberg says:

    Peter, Mohan Putcha takes this view for the representation theory of monoids, but perhaps with the opposite goal. He asks how does an irreducible representation of a monoid decompose as a representation of its unit group. For any finite group G of Lie Type he and Renner constructed a canonical monoid of Lie type M with unit group G. The Steinberg representation is constructed as the restriction of an irreducible representation of the monoid to the group.

    Putcha also studied how semi simplicity of the algebra of invariants for the action of the unit group can in important cases imply semi simplicity of the monoid algebra.

    Monoids if Lie type have essentially Zariski dense groups of units and so they control the monoid structure. In general the group of units can be too small to influence the monoid.

  2. Bill Fahle says:

    I realize this post is a few months old, but I have recently become interested in k-transitive groups, particularly Mathieu groups. You said that “k-transitivity is equivalent to n−k-transitivity for a permutation group on n points. So, without loss, we may assume that k≤n/2.” But it is known that, for example, that M12 is 5-transitive on 12 points. But it is not also 7-transitive, is it? That would contradict your other statement that “In particular, the only k-transitive groups for k≥6 are the symmetric and alternating groups. (There is no prospect of a proof without CFSG.)” I appreciate your response.

    • Sorry, my mistake: it should be set-transitivity. I’ll fix it.

      • Bill Fahle says:

        Oh, right. I think they call that k-homogenous in the book I’m looking at: Finite Groups III by Huppert and Blackburn. Thanks for your response.

      • Yes, that’s right. I used to use this term but now one of the things I work on is “homogeneous relational structures” where the word has a different meaning.

        Terminology is difficult. For relational structures, people used to use “ultrahomogeneous” and “homogeneous”, roughly parallel to “transitive” and “set-transitive” for groups. Then, when they settled on “homogeneous” for the stronger concept, at least one researcher started using “transitive” for the weaker one. [In the stronger concept, whenever you have an isomorphism between finite substructures, you can extend it to an automorphism of the whole structure; in the weaker concept, whenever two structures are isomorphic, then some automorphism of the whole structure carries one to the other. These exactly agree with the permutation concept if “structures” are k-element subsets and “automorphisms” are elements of the group.]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.