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^{n} 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);
- x_{1}…x_{n}β is the inverse image of the n-tuple (x_{1},…,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!
Incidentally I did some work on abstract regular polytopes, too: http://arxiv.org/abs/1603.01710
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. 🙂
You have some typo that got me confused: “and F a bijection between F and its Cartesian power F^n”.
Sorry — fixed now!
Retraction: we made a mistake in the first version: the outer automorphism group of G_{n,r} is not, after all, independent of r.
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.
Thank you!