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 An 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.


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 Xn 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 α1,…α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);
  • x1xnβ is the inverse image of the n-tuple (x1,…,xn) 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 Gn,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

  • Gn,r is finitely presented;
  • Gn,r is simple when n is even, and has a simple subgroup of index 2 (also, of course, finitely presented) when n is odd;
  • Gn,r and Gn,s are isomorphic if r and s are congruent modulo n−1;
  • Thompson’s group V is G2,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 Gn,1 is used, involving operations on infinite strings over a finite alphabet (which can be interpreted as specific homeomorphisms of the Cantor space Cn whose points are paths in the infinite n-branching tree. A simple modification involving r copies of the space gives Gn,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 Cn. A particular case when this holds is when the transducer is synchronous.

Grigorchuk, Nekrashevich and Sushchanskiĭ define the rational group Rn to be the group of homeomorphisms defined by finite transducers. (A simple modification extends this to the two-parameter family Rn,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 Sn,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.


It turns out that

  • Higman’s group Gn,r is a subgroup of Rn,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.
  • Sn,r is the normaliser of Gn,r in the rational group, and is isomorphic to the full automorphism group of Gn,r.
  • The outer automorphism group of Gn,r (the quotient Sn,r /Gn,r) is independent of r. We denote this group by On.

We show a good deal more: the group On is infinite for all n ≥ 2; it contains a subgroup Ln of homeomorphisms with constant Radon–Nikodym derivative, and within that a subgroup Pn 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!

About Peter Cameron

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

7 Responses to The Higman–Thompson groups

  1. Dima says:

    Incidentally I did some work on abstract regular polytopes, too:
    In a nutshell, there is a family of them livings inside some sporadic (and some other) simple groups, presented by “Y-presentations”. They had to wait for someone to know a bit about all this to come along, it seems. 🙂

  2. Yiftach says:

    You have some typo that got me confused: “and F a bijection between F and its Cartesian power F^n”.

  3. Retraction: we made a mistake in the first version: the outer automorphism group of Gn,r is not, after all, independent of r.

  4. xiaobing says:

    Sorry, I am getting confused, did you mean “a transduser which writes nothing is an automaton”? in the second paragraph of Grigorchuk et al?

    • I meant what I said but didn’t express it very well. I have tried to be more clear. An automaton is a transducer which doesn’t write anything, and we are going to decide to disallow this behaviour.

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.