# 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

## Overview¶

Warning

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:

- Determine the
`type of component which contains a given element`

, with respect to some given basis [Lemma 4.28] - Computes the
`quasi-normal basis`

for a given automorphism [Lemma 4.28] - Test to see if two words
`share an orbit`

[Lemma 4.34] - Test to see if two automorphism are
`conjugate`

[Algorithm 5.6] and`power conjugate`

[Algorithm 6.13].

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

Todo

Make this available under an open-source license.