A Graphical Explanation of the Todd-Coxeter Algorithm

Using a group presentation is often the most compact and elegant way to define a group, and in some cases it is also the most natural¹. However, it is in general quite difficult to analyze groups written in this form. In fact, it is impossible to create an algorithm that determines whether a group is finite, trivial, or abelian from its group presentation alone¹.

We can, however, analyze the cosets within these groups. The Todd-Coxeter Algorithm, which was originally created by J. A. Todd and H. S. M. Coxeter in the 1930s², is a clever and surprisingly simple algorithm that enumerates the cosets of a given subgroup using only the presentation of the parent group and the generators of the subgroup. In this post, I will endevour to explain the concepts behind this algorithm, the procedure itself, and the inner workings of an implementation of this algorithm.

Group Presentations

Before we continue, we need to nail down a working definition for group presentations. As taken from Derek Holt's lecture notes¹, if $\langle X \mid R \rangle$ is a presentation of the group $G$, then $G$ is the "largest" group generated by the elements of $X$ for which the relations in $R$ hold in $G$. For example, $\langle r,s \mid r^6 = s^2 = (rs)^2 = e \rangle$ is a presentation for the dihedral group $D_6$. Note that presentations are not necessarily unique.

The set $R$ may alternatively be defined to be a set of words following the form $g_1g_2...g_n$ with $g_i \in X$ or $g_i^{-1} \in X$ such that $g_1g_2...g_n=e$. For convenience's sake, we will use this definition from now on.

Group Actions

Group actions are also fundamental to the theory behind the Todd-Coxeter Algorithm.

Let $S$ be a set and let $G$ be a group. A (left) group action of $G$ on $S$ is a function $\alpha: G \times S \rightarrow S$ that meets the following requirements.

If a group action of $G$ on $S$ exists, $G$ is said to act on $S$. If $G$ acts transitively on $S$, then the following is also true.

In otherwords, $S$ only has one orbit.

When working with group actions, $\alpha(g, s)$ is often simplified to $g \cdot s$ or $gs$. We will do this from now on.

Schreier Graphs

Now that we've defined both group presentations and group actions, we can define the Schreier graph, the fundamental data structure that underpins the Todd-Coxeter algorithm.

Let $G = \langle X \mid R \rangle$ and let $G$ act transitively on $S$. The Schreier graph for $S$ is a directed and labeled graph $\Gamma$ with $S$ as its vertex set and with edges labeled $g$ from $s$ to $gs$ $\forall s \in S$ and $\forall g \in X$.

Some Observations

• Since group actions act bijectively on $S$ for a fixed $g$, each vertex has exactly one incomming and one outgoing edge for each label $g \in X$.
• A starting point $s \in S$ and a word $g_1g_2...g_k$ with $g_i \in X$ or $g_i^{-1} \in X$ defines a path in $\Gamma$
• Every word in $R$ corresponds with a loop in $\Gamma$

An Example

Let $G = \langle r, s \mid r^3, s^2, (rs)^2 \rangle$. That is, $G = \langle X \mid R \rangle$ with $X = \{r, s\}$ and $R = \{rrr, ss, rsrs\}$. Let $S$ be a set of arbitrary regular triangles represented by the ordered triplets $(1,2,3)$, $(2,3,1)$, $(3,1,2)$, $(1,3,2)$, $(3,2,1)$, and $(2,1,3)$. Finally, let $G$ act on $S$ with $r \cdot (a,b,c) = (b,c,a)$ and $s \cdot (a,b,c) = (a,c,b)$.

A possible solution for the Schreier graph of $S$ is as follows.

Notice that the observations we just made hold for this example.

The Todd-Coxeter Algorithm

The Todd-Coxeter Algorithm takes two inputs.

• A presentation $G = \langle X \mid R \rangle$ with finite sets $X$ and $R$
• A finite set $Y$ that generates $H$, a subgroup of $G$

The output of the algorithm is the Schreier graph for the set of left cosets of $H$ in $G$, $G/H$, with the following group action.

The Procedure

From a theoretical standpoint, we start with the Schreier graph for the free group generated by $X$. It need not (and indeed cannot, since it is infinite) be entirely represented in memory. Then, we follow the steps below.

1. Label the vertex corresponding to the coset $H$ with the label $1$ (this is represented in memory).

2. For each word $h \in H$, start at vertex $1$ and follow the path defined by $h$. Give the vertices along this path new labels and identify the vertex at the end with vertex $1$.

To identify two vertices, remove the one with the higher label and then merge its edges with the edges of the other vertex. If there are two outgoing edges with the same label or two incoming edges with the same label, the vertecies at the other end of those edges must also be identified so that we are left with at most one outgoing edge and one incoming edge for each label.

3. For each vertex that is labeled or that will be labeled (including the ones that will be labeled during this step), define a path starting at that vertex for each word in $R$ (so, if $S$ is the set of all vertices that will eventually be labeled, there should be $|S|\cdot|R|$ paths in total). Then, for each path $p$, label the vertices along $p$ and identify starting point of $p$ with the endpoint of $p$.

If and when this final step terminates, we will be left with a Schreier graph for $G/H$ that is completely labeled.

Some Observations

• If H is trivial then the Schreier graph represents $G$ since $G/\{e\} \cong G$
• A spanning tree rooted at vertex $1$ gives us a way to recover all of the cosets of $H$ (or the elements of $G$ if $H$ is trivial) using only the generators in $X$

An Interactive Example

Let $G = D_6 = \langle r,s \mid r^6, s^2, (rs)^2 \rangle$ and let $H=\langle r^3 \rangle$. So, the inputs for the Todd-Coxeter Algorithm are as follows.

Note: Some steps are skipped since they don't permanently affect the tree

Implementation

An implementation of this algorithm written in python can be found on GitHub here or downloaded here. Most of its core logic was taken from Kyle Miller's implementation³, but it was rewritten using classes. This, in my opinion, makes it a lot easier to read. It was also written as a terminal application in order to increase its ease of use.

To use this program, download it and then run the following command to get more usage information.

python3 todd-coxeter.py -h

To run this program for the example above, use the following command.

python3 todd-coxeter.py --ngens 2 --rels 1,1,1,1,1,1 2,2 1,2,1,2 --hgens 1,1,1

In this command, --ngens 2 is used to specify that there are two generators (they will be labeled $1$ and $2$, corresponding to $r$ and $s$ respectively, and their inverses will be labeled $-1$ and $-2$). After the --rels flag, the relations in $R$ are specified using the following format: each generator is separated with a comma, and each word in $R$ is separated by a space. After the --hgens flag, the generators for $H$ are specified using the same format.

The rest of this section will outline the general structure of this implementation. If you are interested in the exact syntax used, I would encourage you to look directly at the source code.

Data Structures and Classes

There are two main data structures used within this implementation: a disjoint-set (or union-find) data structure implemented by the UnionFind class and a graph represented by an adjecency list (implemented with a list of dictionaries). These two data structures are combined to create the PartialSchreierGraph class, which represents the Schreier graph before the Todd-Coxeter Algorithm terminates.

The SchreierGraph class inherites from PartialSchreierGraph and contains the logic for the Todd-Coxeter Algorithm. This algorithm is executed within the constructor of SchreierGraph (i.e. it must terminate for an instance of SchreierGraph to finish being constructed) so that all instances are guaranteed to represent a valid Schreier graph for $G/H$. This class, in conjuction with the Permutation class, also provides a way to interpret the graph without displaying it in its entirety. Instead, for each generator, it displays a product of cycles that corresponds with how that generator permutes the cosets of $H$.

A Closer Look at UnionFind and its Role in PartialSchreierGraph

The disjoint-set (or union-find) data structure represents a set of disjoint sets using disjoint trees. This forest is represented by a single list parent with the following constraint.

parent[index/label of child] = index/label of parent

When using disjoint-sets, we have access to two operations.

• Find: For any given label, find the root of the tree that contains that label
• Union: For any two labels, if those labels are a part of different trees, combine those two trees. In our implementation, the root with the lower label is used as the root of the new tree.

More information about this data structure can be found here.

Within the PartialSchreierGraph class, the disjoint-set data structure is used to keep track of vertex labels. We could just use a single label for each vertex, but if a label is removed (and this happens quite a lot during identification) then all references to that label must be updated or removed. That would require looping through all of the edges of the graph, which is inefficient. With the disjoint-set keeping track of labels, we don't need to worry about this. Instead, whenever we want to run an operation on a vertex label, we first run the find operation on that label to get the actual (that is, the lowest) label for that vertex. And, whenever we identify two nodes, we run the union operation on their labels.

Supporting Inverses

It is not technically necessary to keep track of inverses within the adjacency list for our Schreier graph since every incoming edge is an outgoing edge for some other vertex. However, we would like to be able to include inverses in the words in $R$ and $Y$, and therefore we need to be able to calculate $g^{-1}s$ quickly. For this reason, we do include inverses in our adjacency list.

To keep the inverse edges pointing in the right direction, we add a trivial relation $gg^{-1}$ to $R$ for each $g \in X$. This ensures that, after the completion of the algorithm, we are left with a valid Schreier graph. No other changes are necessary.

Conclusion

Although this post is not quite mathematically complete, I hope that it has provided some valuable insight into the Todd-Coxeter Algorithm from a mathematical perspective and from the perspective of computer science.

In addition to being a fun project, this post was also an assignment for a class taken at Cleveland State University in cooperation with the Jack, Joseph and Morton Mandel Honors College. Special thanks to Dr. Galetto for his guidence during this project.

If you have any questions or find any errata, feel free to email me at [email protected] or create a GitHub issue here (if that's your kind of thing). Also, keep in mind that this entire website is open source, so if you want to learn how to make a website like this or a interactive graph like the one I have above, feel free to check out its source code here.

Resources

1. Holt, Derek. (2013). Presentation of Groups. https://warwick.ac.uk/fac/sci/maths/people/staff/fbouyer/presentation_of_group.pdf

2. Todd, J., & Coxeter, H. (1936). A practical method for enumerating cosets of a finite abstract group. Proceedings of the Edinburgh Mathematical Society, 5(1), 26-34. doi:10.1017/S0013091500008221 (pdf: https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0013091500008221)

3. Miller, Kyle. (2016). The Todd-Coxeter algorithm. https://math.berkeley.edu/~kmill/notes/todd_coxeter.html

4. vis.js: https://visjs.org/. Used to display the interactive graphs

5. react-graph-vis: https://github.com/crubier/react-graph-vis. A vis.js wrapper for ReactJS