1. Introduction

The principal aim of this paper is to establish a link between different methods for computing in groups available in the literature - methods from combinatorial group theory, methods from string rewriting theory and methods from Gröbner basis theory - by giving a coset enumerating procedure using Gröbner basis techniques.

One very popular procedure in combinatorial group theory is due to Todd and Coxeter and systematically enumerates all cosets of a finitely generated subgroup in a given finitely presented group [26]. Nielsen reduced sets allow the computation of Schreier coset representatives hence enabling syntactical solutions to the subgroup problem in finitely generated free groups [22]. Another approach to the study of groups stems from the fact that they can be presented as string rewriting systems and, hence, completion based procedures a la Knuth and Bendix can be applied [12]. Recently, some authors have started using Gröbner basis methods to model groups in appropriate rings and solve group theoretical problems in this setting [17,4].

In [17] the existence of explicit connections between the word problem for monoids and groups and the ideal membership problem in free monoid and free group rings, respectively, as well as connections between the submonoid problem and the subalgebra problem and between the subgroup problem and the one-sided ideal membership problem is proven. These results strongly encourage people designing new algorithms for attacking monoid or group theoretical problems to look for methods in all three fields mentioned above. Here we want to present the fundamental results of Nielsen and Todd and Coxeter from combinatorial group theory using Gröbner basis techniques for free group rings. More on connections between the Todd-Coxeter coset enumeration procedure (abbreviated by TC in the following) and the Knuth-Bendix completion procedure (abbreviated by KB) for the special case of the trivial subgroup can be found in [2,25].

A group ${\cal G}$ is called finitely presented if there is a finite set of generators $\Sigma$ and a finite set of relators R such that ${\cal G}$ is isomorphic to the quotient of the free group generated by $\Sigma$ modulo the congruence generated by R. Let $\bar{\Sigma} = \Sigma \cup \Sigma^{-1}$ where $\Sigma^{-1} = \{a^{-1} \mid a \in \Sigma \}$ denotes the set of formal inverses for the generators. The group elements then are represented as words on $\bar{\Sigma}$. In 1911 Dehn stated decision problems for groups, two of which will be studied here using coset enumeration: The word problem for a group is to decide whether two representations describe the same group element. The subgroup problem for a group is to decide for a group element and a subgroup of the group whether the element is in fact a member of the subgroup. Both problems are undecidable in general, but become decidable when restricted to special classes of groups. For finitely generated free groups the word problem can be solved by free reduction, i.e. by deleting occurrences of subwords of the form aa^-1 and a^-1a for $a \in \Sigma$. The subgroup problem can be solved using Nielsen reduced sets due to the fact that there is a lot of crucial information on the maximal parts of words which can cancel each other when multiplying generating elements of subgroups. A well established procedure for dealing with these two problems in the case of arbitrary finitely presented groups is TC: Given a set of defining relators for the group ${\cal G}$ and a set of generators of the subgroup ${\mathcal{H}}$ (as words in the generators of ${\cal G}$) TC enumerates the cosets of ${\mathcal{H}}$ in ${\cal G}$. Of course this process can only stop in case ${\mathcal{H}}$ has finite index in ${\cal G}$ and then TC also provides the multiplication table of the cosets. Now given a word w in the generators of ${\cal G}$ we have that $w \in {\mathcal{H}}$ if and only if w is in the coset of the identity. Hence TC provides a semi-decision procedure by determining, while enumerating cosets, whether w is in one of the cosets enumerated so far, and answering ``yes'' in case it is in the coset of the identity. It is obvious that the answer ``no'' can only be given in case the procedure terminates, since as long as more cosets are enumerated there is the possibility of cosets collapsing, i.e., even if w is found in a coset which is not the identity it might later on be derived that the coset coincides with the coset of the identity. Notice that when choosing the trivial group as the subgroup ${\mathcal{H}}$ TC in fact enumerates all elements of the group ${\cal G}$ and terminates if and only if ${\cal G}$ is finite.

Group presentations can be interpreted as string rewriting systems and this field is well studied (compare [3]). The most important procedure is due to Knuth and Bendix and allows computing convergent² presentations for groups. In case such a presentation is additionally finite it can be used to compute unique normal forms for the group elements and hence to decide the word problem for the group. The advantage is that this method is often still applicable to infinite groups. For an overview see e.g. [3] and [13]. The presentation of a finitely generated free group in terms of the inverse relators can be interpreted as a convergent string rewriting system and free reduction is exactly reduction using this string rewriting system. In [2] it is outlined how TC and KB are related for the special case of the trivial subgroup: for a modified version of TC, which represents the cosets by appropriate words on $\bar{\Sigma}$ and uses a certain strategy (depending on the ordering chosen for the words representing the elements of the group) to replace cosets when new equations are obtained, on termination the output of KB is a subset of the rules corresponding to the equations generated by TC. What now are the essential differences between TC and KB in this case? In case TC terminates so will a specialized version of KB but the converse does not hold. This is due to the fact that TC, when viewed as a rewriting procedure, does not apply ordinary string rewriting but prefix rewriting. Now if no finite convergent system with respect to prefix rewriting exists, TC does not detect whether it might already have computed a convergent set of rules with respect to ordinary string rewriting and hence will not terminate although KB might. Variants of prefix rewriting have a long tradition when studying subgroups using string rewriting techniques (compare [13]). But there are two main differences: These techniques require certain assumptions for the relators defining the group (e.g. convergence) while TC allows any presentation. The output gained by prefix string rewriting completion techniques is a description of cosets of the subgroup in the group while TC enumerates cosets of the subgroup generated by the original subgroup generators and the normal closure of the relators in the corresponding free group. This difference explains why prefix string rewriting techniques can also handle cases where the subgroup has infinite index. A well-known algorithm can be found for free groups: In a finitely presented free group the subgroup problem can be solved using Nielsen reduced sets of generators and prefix string rewriting.

KB techniques can be applied to complete group presentations as string rewriting systems. Sims incorporated prefix string rewriting techniques for the subgroup generators by decoding them as special rules of the form $\$u \longrightarrow\$ where $ is a new symbol. In [25] he compares running KB on input $\{ r \longrightarrow\lambda \mid r \in R \} \cup \{ \$u \longrightarrow\$ \mid u \in U \}$ where R are the relators and U the subgroup generators to TC. However, in general the completion does not terminate even for subgroups of finite index. This is due to the fact that it will always compute a convergent presentation for the group which need not be finite. In Section 5 we will outline how our procedure using Gröbner basis techniques can be ``translated'' into a Knuth-Bendix type procedure which simulates TC and always terminates if the subgroup has finite index.

In this paper we present TC in an unusual framework due to the fact that monoids and groups can be simulated by binomial ideals³ in free monoid and free group rings. A first explicit connection between finitely presented commutative monoids and ideals in commutative polynomial rings was used 1958 by Emelichev yielding a solution to the word problem in the monoid by deciding the ideal membership problem (compare [18]): Assuming the commutative monoid ${\cal M}$ is presented by a set of generators $x_1, \ldots, x_n$ and a set of defining relations $\ell_1 = r_1, \ldots, \ell_m = r_m$ the following is true: A relation u=w holds in ${\cal M}$ if and only if the polynomial u-w lies in the ideal generated by the polynomials $\ell_1 - r_1, \ldots, \ell_m - r_m$ in the polynomial ring $\mathbb{Q} [x_1, \ldots, x_n]$. In his paper Emelichev uses the result of Hermann presented in [9] to show that the latter question is decidable. Of course the ideal membership problem is also solvable using Buchberger's method of Gröbner bases, which is based on a special reduction system associated to finite sets of polynomials which represent ideal congruences in polynomial rings [6].

It was observed independently in [20,23,17] that similar results hold for congruences on arbitrary finitely generated monoids and groups. Here we want to develop these ideas for the free group case in order to give a coset enumerating procedure using Gröbner techniques for free group rings:

Let ${\mathcal{F}}$ denote the free group generated by $\Sigma = \{a_1, \ldots, a_n \}$. The elements of ${\mathcal{F}}$ are represented by the freely reduced words in $\bar{\Sigma}^*$ and multiplication of two elements, denoted by $\circ$, is just their concatenation followed by free reduction. In the following we will not distinguish between group elements and their representation. The empty word $\lambda$ represents the unit in ${\mathcal{F}}$. By $\mathbb{K} [{\mathcal{F}}]$ we denote the free group ring, i.e. the set of finite formal sums $\sum_{i=1}^k \alpha_i \cdot t_i$, $\alpha_i \in \mathbb{K}\backslash \{ 0 \}$, $t_i \in {\mathcal{F}}$ where $\cdot$ denotes multiplication with scalars and $\ast$ will denote multiplication in $\mathbb{K} [{\mathcal{F}}]$. The elements are called polynomials. The precedence $a_1 \prec a_2 \prec \ldots \prec a_n \prec a_1^{-1} \prec \ldots \prec a_n$ induces a length lexicographical ordering on ${\mathcal{F}}$ denoted by $\leq$ which is well-founded and total, but unfortunately not admissible for ${\mathcal{F}}$⁴. This ordering can be lifted to $\mathbb{K} [{\mathcal{F}}]$ and used to distinguish the head term ${\sf HT}(f)$, head coefficient ${\sf HC}(f)$ and head monomial ${\sf HM}(f)$ of a polynomial f and ${\sf HT}(F) = \{ {\sf HT}(f) \mid f \in F \}$ for subsets F of $\mathbb{K} [{\mathcal{F}}]$ as usual. Identifying the elements of ${\mathcal{F}}$ by their representatives we define the syntactically motivated concept of prefix reduction: For two non-zero polynomials p, f in $\mathbb{K} [{\mathcal{F}}]$, we say f prefix reduces p to q at a monomial $\alpha \cdot t$, $\alpha \in \mathbb{K}\backslash \{ 0 \}$, $t \in {\mathcal{F}}$ of p in one step, denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{f}\,$ } q$, if ${\sf HT}(f)$ is a prefix of t as a word (i.e.  ${\sf HT}(f)w \equiv t$ for some $w \in {\mathcal{F}}$ where ${\sf HT}(f)w$ stands for the concatenation of ${\sf HT}(f)$ and w and $\equiv$ denotes identity as words) and $q = p - \alpha \cdot{\sf HC}(f)^{-1} \cdot f \ast w$. We will call a basis G of a right ideal $\mathfrak{i}$ in $\mathbb{K} [{\mathcal{F}}]$ a prefix Gröbner basis of $\mathfrak{i}$, if ${\sf HT}(\mathfrak{i}) = \{ uw \mid u \in {\sf HT}(G), w \in {\mathcal{F}}\}$. G is called reduced if no polynomial in G is prefix reducible by another polynomial in G. As in the commutative case congruences on the free group ${\mathcal{F}}$ are modeled using special polynomials: A subset of the free group ring $\mathbb{K} [{\mathcal{F}}]$ is called a binomial basis of an ideal $\mathfrak{i} \subset \mathbb{K} [{\mathcal{F}}]$, if it consists solely of polynomials of the form u - v where $u,v \in {\mathcal{F}}$ and u > v⁵. We will speak of binomial ideals in case they have a binomial basis. Such ideals are strongly related to the word problem in groups (compare [23,17]) and hence are the appropriate connection to TC. The FGLM algorithm⁶ (see [7,8,19]) was introduced as a tool to study the duality of ideals: the central procedure MATPHI enumerates as a bonus the set N (called the natural basis of G there) of terms which are irreducible by the Gröbner basis and a table for the multiplication of elements in N by variables. Therefore, by combining a generalization of the MATPHI algorithm presented in [8] and prefix Gröbner bases [15,16] we produce a coset enumeration procedure which is a verbatim interpretation of TC. An implementation of the procedure was done in MRC (a system for computing Gröbner bases in monoid and group rings developed at the University of Kaiserslautern).

The paper is organized as follows: In Section 2 we present the basics on Nielsen reduction and TC. Section 3 summarizes the necessary results from Gröbner basis theory which are applied in Section 4 to give a coset enumeration procedure based on prefix Gröbner bases in free group rings. Section 5 summarizes our results and points out how our procedure can be transformed into a Knuth-Bendix type completion procedure directly comparable to TC.