The thompson package

Nathan Barker, Andrew Duncan and David Robertson have submitted a paper entitled The power conjugacy problem in Higman-Thompson groups which addresses the following problem in the groups named \(G_{n,r}\).

[AS74] Given two elements \(x\) and \(y\) of a group, are there integers \(a\) and \(b\) and a third element \(z\) for which \(x^a = zy^bz^{-1} \neq 1\)? If so, provide them.

This package aims to implement the algorithms described in the paper. To do so it provides tools for working in

  • the algebra \(V_{n,r}\), a certain set of words, and
  • the automorphism group \(G_{n,r} = \operatorname{Aut}(V_{n,r})\).

This documentation serves three purposes. Firstly, it is meant to serve as a gentle introduction, explaining how to install and use the package. Secondly, it is meant to be a reference to all the various classes and functions provided by thompson. Finally, a number of examples are included throughout the documentation, which can be used as a means to test the implementation.

David M. Robertson, Aug 27, 2018



For the most part, this documentation is automatically generated by Sphinx , so it’s not the prettiest thing that’s ever been written.

This all began as a series of tools to draw tree pair diagrams in Thompson’s group \(V = G_{2,1}\), hence the name thompson. The focus has moved away from trees diagrams towards bijections between bases of words. From there, the package has grown and it now serves as an implementation of the algorithms we describe in the paper. Chief among these are the algorithms which:

Implementation details

The implementation is written in Python and runs under Python 3.3 and above. The intent was to provide a proof-of-concept rather than a perfectly optimised implementation. Despite this, we have found the program useful as a calculator for \(G_{n,r}\), as a means to generate examples, and for experimentally testing conjectures. The source code (both to the program and this documentation) is publicly available from GitHub.


Make this available under an open-source license.