2. Todd-Coxeter Simulation

The Todd-Coxeter coset enumeration is a famous method from combinatorial group theory for studying finitely presented groups. It is based on the following fundamental observations: Presenting a group $\mathcal{G}$ in terms of generators $\Sigma$ and relators $R$ corresponds to viewing it as the quotient of the free group $\mathcal{F}$ (generated by $\Sigma$) by the normal subgroup $\mathcal{N}$ generated by $R$. $\mathcal{N}$ can be viewed as the subgroup of $\mathcal{F}$ generated by $N(R) = \{ w \circ r \circ w^{-1} \mid w \in \mathcal{F}, r \in R \}$. Notice, that if $R$ is finite, $\mathcal{N}$, while finitely generated as a normal subgroup of $\mathcal{F}$, need not be finitely generated as a subgroup.

Now given a subgroup $\mathcal{U}$ of ${\mathcal{G}}$ for $g \in \mathcal{G}$ we can study the cosets $\mathcal{U}g = \{ u \circ g \mid u \in \mathcal{U} \}$ of $\mathcal{U}$ in $\mathcal{G}$. Since for $g,h \in \mathcal{G}$ either $\mathcal{U}g = \mathcal{U}h$ or $\mathcal{U}g \cap \mathcal{U}h = \emptyset$ the group ${\mathcal{G}}$ is a disjoint union of cosets and the number of different cosets is called the index $\vert\mathcal{G} : \mathcal{U}\vert$ of $\mathcal{U}$ in $\mathcal{G}$. We know that if $\mathcal{U}$ is generated by a set $U \subseteq \mathcal{G}$ the index of $\mathcal{U}$ in $\mathcal{G}$ is the same as the index of the subgroup ${\mathcal{H}}$ generated by $U \cup N(R)$ in $\mathcal{F}$. While it is undecidable whether a subgroup has finite index in a group, coset enumeration attempts to verify whether the index is finite by enumerating (potential) cosets and their multiplication table. Detailed descriptions of TC procedures can be found e. g. in [16,1,8,3,15].

In [11] Procedure 1 (see page ) was presented which simulates the Todd-Coxeter procedure to enumerate cosets using th ecomputation of prefix Gröbner bases in free group rings (see [7]). Besides the sets $F_R$ and $F_U$ which contain the encoded relators and subgroup relators, respectively, we have three sets. First of all, $N$ which contains the potential coset representatives of the subgroup generated. Next, $G$ which represents the multiplication table obtained so far and is used to decide whether or not elements of $N$ are indeed coset representatives or not. The set $B$ serves as a test set for possible coset representatives. Elements from this set which are not prefix reducible are added to the set $N$ during the enumeration process. A detailed description of the meaning of the sets and of the procedure can be found in [11].

While this approach is based on the idea of computing the index of the subgroup ${\mathcal{H}}$ generated by $U \cup N(R)$ in ${\mathcal{F}}$ and hence uses Gröbner basis techniques in $\mathbb {K}[{\mathcal{F}}]$, a splitting of the relations $R$ can lead to new enumeration procedures $\cite{Re1999}$. For $R = R_1 \cup R_2$ where either $R_1$ is complete or can be finitely completed to $\widetilde{R_1}$, let $\mathcal{G}_1$ be the group presented by $<\Sigma, R_1>$, respectively $<\Sigma, \widetilde{R_1}>$. Then in a similar fashion we can try to compute the index of the subgroup $\mathcal{H}_1$ generated by $U \cup N(R_2)$ in $\mathcal{G}_1$ which is of course again $\vert{\mathcal{F}}: \mathcal{H}\vert = \vert\mathcal{G} : \mathcal{U}\vert$. The resulting procedure is nearly identical with the original procedure extended_todd_coxeter_simulation on input $F_{R_2}$ and $F_U$ except that now the computation takes place in $\mathbb {K}[\mathcal{G}_1]$ and we have to be more careful in choosing $\tau$ to ensure fairness.

In [10] the possibility of moving relators from the set of relators generating the group to the free group was studied. Let the free group be given as $\mathcal{F} = (\Sigma, G)$, were $G = \{ (aa^{-1}, \lambda) \vert a \in \Sigma\} \cup \{ (a^{-1}a, \lambda) \vert a \in \Sigma\}$. Let the relators be given by $R = \{ r \}$. If one of the relators has the form $r = \sigma^n, \sigma \in \Sigma, n \in \mathbb {N}$ then we can remove this relator from $R$ and add it to $G$. The latter is then completed with respect to the ordering required using the Knuth-Bendix completion procedure which is this case is always terminating. We thus get $G'$ the completed set of rules and $R' = R \backslash \{r\}$. Using these we can perform coset enumeration as before. Other relators, too, can be moved provided a finite and convergent presentation for the underlying group exists.

The original procedure extended_todd_coxeter_simulation was implemented in MRC 1.2 (see [13]) and examples known from the literature (see [1,3]) were computed. Soon it was clear that the original version is far too slow to be of any use except for very small examples. This is not surprising as the Gröbner basis computation which is performed after each new coset element added is quite costly (see also Section 3.3 for a comparison to known methods for coset enumeration).

Thus, different frameworks and strategies have been developed in order to find out whether the coset enumeration process described is useful compared to currently known procedures and strategies. Due to implementational reasons time and space requirements are much higher for our implementation compared to available implementations of the Todd-Coxeter-procedure. First of all, in MRC 1.2 cosets are represented by words, not by numbers, which requires more space for large examples. Second, the coefficients are elements of $\mathbb {Q}$ while they can take the values $\{-1, 0, 1\}$ only. Third, since MRC 1.2 handles polynomials, we are encoding relators as polynomials while using binomials would be sufficient. Changing the domain of the coefficients and using binomials reduced time and space requirements drastically.

However, more important to us is whether our system can compete with respect to the crucial numbers of Todd-Coxeter-Enumeration: the maximal number of cosets defined during the enumeration process and the total number of cosets defined. Since the enumeration is performed in a different algebraic structure, new parameters play an important role and might help to study cosets from a different point of view.

All frameworks and strategies presented here can as well be used for monoids as for free and general groups (compare [9]).