1. Introduction

In 1936 Todd and Coxeter [16] developed a procedure to enumerate cosets of a subgroup of a group which turned out to be one strong tool for studying groups in combinatorial group theory. Implementations of these ideas are available in computer algebra systems for groups as GAP, Cayley, and ace2. Other approaches to coset enumeration using the Knuth-Bendix algorithm or automata followed.

This paper now tries to use a new approach consisting of several frameworks and strategies to gain new insights into this process based on prefix Gröbner bases. In fact this could be narrowed down to prefix string rewriting for the examples considered here. On the other hand the examples presented by Linton in [5] can be computed using prefix Gröbner bases, too, and thus justify an extensive study of coset enumeration based on prefix Gröbner bases. As the prefix Gröbner basis setting in MRC 1.2 produces a lot of overhead and hence we considered numbers of cosets instead of measuring times. However, if our findings prove to be valuable, they can either be incorporated into existing implementations of Todd Coxeter or if this is not possible, a specialized reimplementation on the basis of prefix string rewriting is possible. We present the results for a set of examples presented in [1,3] which were achieved using our methods. As expected we are sometimes better, sometimes worse than the existing methods like Felsch- or HLT-type enumeration procedures. Remarkably, for some examples we are considerably better than these methods.

Further, if we compare our approach to the findings of Havas presented in [3] we get the following results. First of all, all methods including our own are syntactical ones. While the existing methods use strategies to cleverly fill the coset table our strategy introduces new cosets based on the multiplication table represented by the prefix Gröbner basis. We found, too, that adding the symmetric relators improved the enumeration process considerably. Further, our method treats all group generators as subgroup generators per se which was introduced for the Felsch method by Havas in [3].

Besides the possibility to study coset enumeration from a different point of view due to a different procedure, current methods seem to use length-lexicographical orderings with the precedence on the letters being the only parameter. Our method supports all kinds of orderings provided they are well-founded. Three different types of them, Knuth-Bendix orderings, syllable orderings and of course the length-lexicographical ordering are implemented in MRC 1.2 right now and were used to compute the examples. Results achieved using the Knuth-Bendix and the syllable orderings can be much better compared with the length-lexicographical one.

Taking for example (see also [3,4]) the Fibonacci group $F(2,7)$ presented by $ab = c, bc = d, cd = e, de = f, fg = a, ga = b$, we get that the index of any subgroup generated by one element is $1$, that is $index(F(2,7) \vert <f>) = 1$. This group was studied in detail in [4]. Currently (according to [3]) the best coset enumeration program enumerates 169 cosets before the collaps occurs. Using our program we can do the same enumeration by defining 134 cosets using a Knuth-Bendix ordering before the collaps occurs. This is already much closer to the target of 129 cosets set by Leech in [4]. But is still far from the best results achieved by optimizing the enumeration by hand which only needs 53 cosets before the collaps occurs. Examining more Knuth-Bendix or other orderings might improve the performance of our program further.

In this paper we show how the procedure presented in [11] for theoretical reasons to show how rewriting methods and Todd Coxeter are related, can be improved when having real computation in mind. In order to do so, we introduce so called frameworks which can be compared to the strategies Felsch and HLT for the original Todd-Coxeter enumeration procedure. They are supplemented by strategies adding cosets cleverly. In addition we studied the influence of well-founded orderings on the enumeration process and how different combinations of frameworks, strategies, and orderings behave. The improved frameworks as well as the examples evaluated are presented.

For the rest of the paper we assume that the reader is familiar with the methods available for coset enumeration. Descriptions of these methods can be found in [16,1,8,3,15]. The description of the procedure simulating the Todd-Coxeter procedure using prefix Gröbner bases and a comparison with Knuth-Bendix completion can be found in [11]. The Paper is organized as follows. In Section 2 we shortly recall the most important concept from coset enumeration and of the simulating procedure. As this procedure is only appropriate for small examples, we propose two frameworks which are presented in Section 3. They use strategies which are described in Section 4. As orderings play an important role they are introduced in Section 5. The examples used for this report are taken from [1,3] and are presented in Section 6. The frameworks and strategies were evaluated and the results of this evaluation are described in Section 7. In Section 8 the influence of the ordering on the coset enumeration is described. Section 9 describes the results obtained for the MacDonald groups (see also [6]). Possible enhancements are pointed out in Section 11. Appendix A lists the algorithms while the results are tabulated in Appendix B, C, and D.

Acknowledgement The authors thank Prof. K. E. Madlener and Christoph Kögl for valuable discussions on this paper.