The Higman–Thompson groups

I celebrated the last day of spring last week with the appearance of two substantial papers on the arXiv: one with Maria Elisa Fernandes, Dimitri Leemans, and Mark Mixer, proving that the maximum rank of a regular polytope whose group is the alternating group A_n for n ≥ 12 is the floor of (n−1)/2; the other, with Collin Bleak, Yonah Meissel, Andrés Navas, and Feyishayo, on a description of the automorphism groups of Graham Higman’s generalisations of Richard Thompson’s finitely presented infinite simple group.

In both cases, I joined a long-standing collaboration; the other authors must have thought I had contributed something, and I am proud to be in both of these groups.

I have described the first of these results here, so I will say a few words about the second. The first section is somewhat orthogonal to the content of the preprint.

Higman

Some time in the 1970s, Graham Higman discussed his generalisations of Richard Thompson’s group in his “advanced class” in Oxford. This series of lectures, one a week during term-time, was an exposition of his current interest; often, at the start of term, he didn’t know whether he would have a theorem to talk about by the end. What follows is entirely based on my memory of a particular term’s lectures, I cannot remember exactly when.

Suppose that X is a non-empty set, and F a bijection between X and its Cartesian power Xⁿ for some integer n > 1. Note that, if X is not a singleton, then it is infinite.

We can describe the situation in algebraic terms as follows. Define n unary operations α₁,…α_n and an n-operation β as follows (writing the operators on the right of their argument):

• xα_i is the i-th coordinate of F(x);
• x₁…x_nβ is the inverse image of the n-tuple (x₁,…,x_n) under F.

Then X, with these operations, form an algebra (in the sense of universal algebras); indeed, the algebras arising in this way form a variety. (It is a straightforward exercise to write down identities for the operators which guarantee that they arise for a bijection to the nth power in this way.)

Higman’s group G_n,r is the automorphism group of the r-generator free algebra in this variety. (You may want to pause for a bit to think what this algebra looks like before reading on.)

Higman showed that

• G_n,r is finitely presented;
• G_n,r is simple when n is even, and has a simple subgroup of index 2 (also, of course, finitely presented) when n is odd;
• G_n,r and G_n,s are isomorphic if r and s are congruent modulo n−1;
• Thompson’s group V is G_2,1.

All the above is taken from my memories of the lectures, and may not be entirely reliable.

Nowdays, a more concrete representation of the groups G_n,1 is used, involving operations on infinite strings over a finite alphabet (which can be interpreted as specific homeomorphisms of the Cantor space C_n whose points are paths in the infinite n-branching tree. A simple modification involving r copies of the space gives G_n,r.

The best known exposition of these groups and their friends is an article by Cannon, Floyd and Parry in Enseign. Math. in 1996.

Grigorchuk et al.

I have described automata (as they arise in synchronization theory) in many places including here. These are very simple machines; at any time, an automaton is in one of a set of internal states; when it reads a symbol, it undergoes a transition (a map from the set of states to itself).

A transducer is a slightly more complicated machine which, as well as changing state when it reads an input symbol, also writes a string on its output tape. Of course, an automaton (which writes nothing) is a transducer, though not a very interesting one; we will rule this out by always assuming that our transducers have the property that when they read an infinite string they also write an infinite string.

One way to ensure this is to require that, when one input symbol is read, one output symbol is written. Such a transducer is called synchronous. Of course, our condition is much more general. What we require is that, when the automaton traverses a cycle in the directed graph given by the transitions, it should write at least one symbol.

A transducer induces a map from the set of infinite strings over the given finite alphabet to itself. If this map is a bijection, whose inverse is also given by a transducer, then it is a homeomorphism of the corresponding Cantor space C_n. A particular case when this holds is when the transducer is synchronous.

Grigorchuk, Nekrashevich and Sushchanskiĭ define the rational group R_n to be the group of homeomorphisms defined by finite transducers. (A simple modification extends this to the two-parameter family R_n,r we are interested in: there is a disjoint set of r initial states, and on its first move the transducer goes into one of the n non-initial states.) We are interested in a subgroup S_n,r consisting of homeomorphisms induced by bi-synchronizing transducers, those for which there is a number m such that both the transducer and its inverse, after reading m symbols, are in a state which depends only on the symbols read and not on the starting state.

Connections

It turns out that

• Higman’s group G_n,r is a subgroup of R_n,r, in which the “core” of the transducer has a single state and simply acts as the identity on the symbols processed from that state.
• S_n,r is the normaliser of G_n,r in the rational group, and is isomorphic to the full automorphism group of G_n,r.
• The outer automorphism group of G_n,r (the quotient S_n,r /G_n,r) is independent of r. We denote this group by O_n.

We show a good deal more: the group O_n is infinite for all n ≥ 2; it contains a subgroup L_n of homeomorphisms with constant Radon–Nikodym derivative, and within that a subgroup P_n consisting of homeomorphisms induced by synchronous transducers (these maps are related to sliding-block codes).

There is a good deal more, including many examples of transducers inducing homeomorphisms with interesting properties; and there is much more we intend to investigate in this subject!