4. Enumerating Cosets Using Gröbner Techniques

Let ${\cal G}$, $\mathcal{U}$, ${\mathcal{H}}$ and $\Sigma$, R, U be as defined before. In this section we combine the ideas presented in Section 3 in order to give a procedure with the following output:

1.

If $R = \emptyset$ the procedure terminates with the monic prefix Gröbner basis G which allows to decide the subgroup problem for the subgroup generated by U in ${\mathcal{F}}$ and to compute the Schreier coset representatives (with respect to >). The set $\{ uv^{-1} \mid u-v \in G \}$ is Nielsen reduced for U.

2.

If $R \neq \emptyset$ then, similar to the Todd-Coxeter procedure, the procedure enumerates cosets of the subgroup generated by $U \cup N(R)$ in ${\mathcal{F}}$ and on termination provides the set of all coset representatives of ${\mathcal{H}}$ in ${\mathcal{F}}$ and the multiplication table for the cosets with elements in $\bar{\Sigma}$ encoded in the prefix Gröbner basis.

In contrast to TC we do not need the assumption that each generator occurs in at least one relator.

Let us start by giving an informal description of our procedure: The input are encodings of the relators R and the subgroup generators U in binomial sets $F_R = \{ r -1 \mid r \in R \}$ and $F_U = \{ u -1 \mid u \in U \}$, respectively. All ring operations take place in $\mathbb{K} [{\mathcal{F}}]$. The following sets are used by the procedure:

1.

$N \subseteq {\mathcal{F}}$ contains potential coset representatives of ${\mathcal{H}}$ in ${\mathcal{F}}$. This set corresponds to the natural basis in MATPHI.

2.

$B \subseteq {\mathcal{F}}$ is a test set for possible coset representatives of ${\mathcal{H}}$ in ${\mathcal{F}}$. It corresponds to the border set in MATPHI.

3.

$H \subseteq \mathbb{K} [{\mathcal{F}}]$ is used to increment the generating set of the subgroup in order to achieve a generating set for ${\mathcal{H}}$.

4.

$G \subseteq \mathbb{K} [{\mathcal{F}}]$ is the monic prefix Gröbner basis which is used to decide, whether the candidates in B are indeed coset representatives of the subgroup generated so far or not.

In the first step, the procedure checks, whether the set of relators is empty. If this is the case, the prefix Gröbner basis of the set F_U is computed⁹ and the output of the procedure is this basis, which allows to solve the subgroup problem for $\mathcal{U}$ and can be transformed into a Nielsen reduced set for U according to Theorem 7. If the set of relators is not empty the procedure starts to enumerate cosets: The set N is initialized with the empty word which is the coset representative of the subgroup itself. N will remain prefix closed throughout the computation, i.e. it will contain all prefixes of its elements. The border set is $B = \{ a \mid a \in \bar{\Sigma} \}$. The set G contains the monic prefix Gröbner basis¹⁰ which allows to solve the subgroup problem for the subgroup generated by $U \cup R$. Now, while there are elements in B we proceed as follows: The smallest element $\tau$ of B is removed. Then if $\tau$ is not prefix reducible by G, it is added to N and all border elements $\tau a$ are added to B where $a \in \bar{\Sigma} \backslash \{ (\ell(\tau))^{-1} \}$ and $(\ell(\tau))^{-1}$ is the inverse of the last letter of the freely reduced word $\tau$. Moreover, we compute the auxiliary set $H = \{ \tau \ast(r -1) \mid r \in R \}$¹¹. In computing the monic prefix Gröbner basis of the set $G \cup H$ we are then able to solve the subgroup problem for the subgroup now generated by the previous generating set extended by the generators $\tau \circ r \circ\tau^{-1}$. This of course corresponds to incrementally approaching the (infinite) generating set $U \cup N(R)$. According to the new prefix Gröbner basis we have to ``correct'' our set of possible cosets N. This is done by removing all elements with a prefix reducible with the new prefix Gröbner basis, as these elements are no longer coset representatives of the incremented subgroup¹². Notice that this operation does not change the property of N of being prefix closed. The procedure terminates as soon as the set B becomes empty.

Procedure: EXTENDED TC SIMULATION

llGiven: 		 

$F_R = \{ r -1 \mid r \in R \}$, a set of binomials encoding the relators.
		 

$F_U = \{ u -1 \mid u \in U \}$, a set of binomials encoding the subgroup generators.
[1ex]

$N := \emptyset$; 
if  

$R = \emptyset$ then 

$G := {\sf prefix.groebner.basis}(F_U)$; 
else 		 

$N := \{ \lambda \}$;
		 

$B := \{ a \mid a \in \bar{\Sigma} \}$;
		 

$G := {\sf prefix.groebner.basis}(F_R \cup F_U)$;
		 while 

$B \neq \emptyset$ do
		 		 

$\tau := {\sf min}_{<}(B)$;
		 		 

$B := B \backslash \{ \tau \}$;
		 		 if  $\tau$ is not prefix reducible by G
		 		  then 		    

$N := N \cup \{ \tau \}$;
		 		 		  

$B := B \cup \{ \tau a \mid a \in \bar{\Sigma} \backslash \{ (\ell(\tau))^{-1} \} \}$;
		 		 		  

$H := \{ \tau \ast(r - 1) \mid r -1 \in F_R \}$;
		 		 		  

$G := {\sf prefix.groebner.basis}(G \cup H)$;
		 		 		  

$S := \{ w \in N \mid w \mbox{ is prefix reducible by } G \}$;
		 		 		  

$N := N \backslash S$;
				 endif
		 endwhile 
endif 

On termination by construction N is either empty or a set of prefix closed coset representatives with respect to the ordering >. The latter is ensured as for each $\tau$ added to N the set B contains all border elements $\tau a$, $a \in \bar{\Sigma} \backslash \{ (\ell(\tau))^{-1} \}$ and removing the set of elements $S = \{ w \in N \mid w \mbox{ is prefix reducible by } G \}$ from N does not destroy the property of being prefix closed.

Moreover, we have the following important invariant for the case that R is not empty: Let N_o, B_o, G_o denote the sets when starting the execution of the while loop and N_n, B_n, G_n the ones at the end. Then for the sets N_n, B_n, and G_n at the end of each loop we have that for each w which is not prefix reducible by G_n one of the following three conditions holds:

1.

$w \in N_n$, or

2.

$w \equiv w_1a$, $a \in \bar{\Sigma}$ and $w_1 \in N_n$, $w \in B_n$, or

3.

$w \equiv w_1aw_2$, $a \in \bar{\Sigma}$, $w_2 \in {\mathcal{F}}$ and $w_1 \in N_n$, $w_1a \in B_n$.

This is true for the sets $N_o = \{ \lambda \}$ and $B_o = \{ a \mid a \in \bar{\Sigma} \}$ before entering the while loop. Notice that due to the construction the elements prefix irreducible with respect to G_n are a (not necessarily proper) subset of those prefix irreducible with respect to G_o. In the loop first the smallest element $\tau$ is removed from B_o. If it is prefix reducible by G_o the new sets are N_n = N_o, $B_n = B_o \backslash \{ \tau \}$ and G_n = G_o and the property still holds, since then $\tau$ cannot be a prefix of any element not prefix reducible by G_n. Now if $\tau$ is not prefix reducible by G_o it is first added to N and its border elements are added to B. We get $G_n = {\sf prefix.groebner.basis}(G_o \cup H)$, $N_n = (N_o \cup \{ \tau \}) \backslash S$ and $B_n = (B_o \backslash \{ \tau \}) \cup \{ \tau \circ a \mid a \in \bar{\Sigma} \backslash \{ (\ell(\tau))^{-1} \} \}$. Let w be prefix irreducible with respect to G_n. Then w was also prefix irreducible with respect to G_o and we have to check the three possible cases:

1.

If $w \in N_o$, since w is still prefix irreducible by G_n it cannot be in S, hence $w \in N_n$.

2.

If $w \equiv w_1a$, $a \in \bar{\Sigma}$ and $w_1 \in N_o$, $w \in B_o$, as $w_1 \not\in S$ we find $w_1 \in N_n$ and either $\tau \equiv w \in N_n$ or $w \in B_n$.

3.

If $w \equiv w_1aw_2$, $a \in \bar{\Sigma}$, $w_2 \in {\mathcal{F}}$ and $w_1 \in N_o$, $w_1a \in B_o$, again as $w_1 \not\in S$ we find $w_1 \in N_n$ and $\tau \equiv w_1a \in N_n$ or $w_1a \in B_n$.

For non-empty R the procedure will only terminate when B becomes empty. Then because of the invariant the set N must contain all elements of ${\mathcal{F}}$ which are not prefix reducible by the final set G. The next theorem now states that on termination the subgroup ${\mathcal{H}}$ generated by $U \cup N(R)$ in ${\mathcal{F}}$ is in fact finitely generated (by $\{ uv^{-1} \mid u-v \in G \}$). G can be used to decide the subgroup problem for ${\mathcal{H}}$ by prefix reduction. Moreover, if R is not empty, G contains the respective (non-trivial) equations which are also generated by TC and encode the multiplication table for the cosets with generators as follows: For each polynomial xa - y where $x, y \in {\mathcal{F}}$, $a \in \bar{\Sigma}$ we know that x and y are coset representatives and the corresponding entry in the table for x and a is $x \circ a = y$.

Theorem 9   Let R and U be as specified above. If procedure EXTENDED TC SIMULATION terminates, then the subgroup ${\mathcal{H}}$ generated by $U \cup \mathcal{N}(R)$ is finitely generated.

Proof: 
If the set of relators is empty ${\mathcal{H}}$ is generated by U and we are done. On the other hand, for non-empty R on termination the set G contains a prefix Gröbner basis which can be used to decide the subgroup membership problem for the subgroup ${\mathcal{H}}_1$ generated by the set $U \cup \{ x \circ a \circ r \circ a^{-1} \circ x^{-1} \mid x \in N, a \in \bar{\Sigma}, r \in R \}$ in ${\mathcal{F}}$ (compare Theorem 6). We have to show that ${\mathcal{H}}_1$ is in fact ${\mathcal{H}}$, the subgroup generated by $U \cup N(R)$ in ${\mathcal{F}}$. This is done by proving that for any $w \in {\mathcal{F}}$, $r \in R$ the element $w \circ r \circ w^{-1}$ is in ${\mathcal{H}}_1$. Let us assume ${\mathcal{H}}_1 \neq {\mathcal{H}}$. Then there is $w \in {\mathcal{F}}$ minimal with respect to > such that for appropriate $r \in R$ we have $w \circ r \circ w^{-1} \not\in{\mathcal{H}}_1$. The case $w \in N$ immediately gives us a contradiction to our construction. Therefore, by our invariant w cannot be irreducible by G as this would imply $w \in N$. Hence let $w \equiv w_1w_2$ such that w₁ is the head term of some polynomial w₁ - v in G. Then we know $w_1v^{-1} \in {\mathcal{H}}_1$ and $w > v \circ w_2$. Now we get $w \circ r \circ w^{-1} = w_1v^{-1} \circ(v \circ w_2) \circ r \circ(v \circ w_2)^{-1} \circ(w_1v^{-1})^{-1}$ and as w was a minimal counter example $(v \circ w_2) \circ r \circ(v \circ w_2)^{-1} \in {\mathcal{H}}_1$. But this implies $w \circ r \circ w^{-1} \in {\mathcal{H}}_1$ as $w_1v^{-1}, (w_1v^{-1})^{-1} \in {\mathcal{H}}_1$ contradicting our assumption. q.e.d.

1.11

Now, if ${\mathcal{H}}$ is finitely generated and contains a non-trivial normal subgroup then ${\mathcal{H}}$ has finite index in ${\mathcal{F}}$ (Proposition 3.11 in [14]). Since TC terminates in case ${\mathcal{H}}$ has finite index in ${\mathcal{F}}$ it remains to show that this is also the case for procedure EXTENDED TC SIMULATION.

Theorem 10   Let R and U be as specified above. If the subgroup generated by $U \cup N(R)$ has finite index in ${\mathcal{F}}$, then procedure EXTENDED TC SIMULATION terminates.

Proof: 
Let the subgroup ${\mathcal{H}}$ generated by $U \cup N(R)$ in ${\mathcal{F}}$ have finite index. If the set of relators is empty then there is nothing to show. The set of coset representatives can for example be computed by enumerating the set of elements which are not prefix reducible by the obtained prefix Gröbner basis G of the right ideal generated by F_U.

Hence let us assume that R is not empty. As ${\mathcal{F}}$ is finitely generated ${\mathcal{H}}$ is also finitely generated (Proposition 3.9 in [14]) and hence has a finite Schreier transversal S. Then for $s \in S$, $a \in \bar{\Sigma}$ and every $s \circ a$ there exists just one $s_a \in S$ such that $s \circ a \in {\mathcal{H}}s_a$. Since $s \circ a = h \circ s_a$ for some $h \in {\mathcal{H}}$ we have $s \circ a \circ{s_a}^{-1} = h \in {\mathcal{H}}$. The set $\{ s \circ a \circ{s_a}^{-1} \mid s \in S, a \in \Sigma \cup \Sigma^{-1} \}$ generates ${\mathcal{H}}$ (compare Chapter 1 in [10]). But then $\{ s \circ a \circ r \circ{s_a}^{-1}, s \circ r \circ s^{-1} \mid s \in S, a \in \bar{\Sigma}, r \in R \}$ again is a generating set for ${\mathcal{H}}$ as $s \circ a \circ{s_a}^{-1} = (s \circ a \circ r \circ{s_a}^{-1}) \circ (s_a \circ r^{-1} \circ{s_a}^{-1})$. Hence the procedure will terminate at least after checking the candidates $s \circ a$ for $s \in S$. q.e.d.

1.11

Reviewing Example 4 with $\Sigma = \{ a,b \}$, $R = \{ aaa, abab, bbb \}$ and $U = \{ a \}$ we get the output $N = \{ \lambda, b, b^{-1}, ba^{-1} \}$ and $G = \{ a - 1, a^{-1} -1, ba - b^{-1}, ba^{-1}a^{-1} - b^{-1}, ba^{-1}b - ba^{-1... ...ba^{-1}, bb - b^{-1}, b^{-1}a - ba^{-1}, b^{-1}a^{-1} - b, b^{-1}b^{-1} - b \}$ which corresponds to the non-trivial part of the multiplication table on page when interpreting the polynomials as described above: $\lambda \circ a = \lambda$, $\lambda \circ a^{-1} = \lambda$, $b \circ a = b^{-1}, (ba^{-1}) \circ a^{-1} = b^{-1}, (ba^{-1}) \circ b = ba^{-1... ...-1}, b^{-1} \circ a = ba^{-1}, b^{-1} \circ a^{-1} = b, b^{-1} \circ b^{-1} = b$. Notice that the set G does not give us the trivial relations as $\lambda \circ x = x$ or $x \circ x^{-1} = \lambda$ for $x \in \bar{\Sigma}$. They can be applied to make the multiplication table complete. On the other hand G directly corresponds to the prefix string rewriting system in Example 4 by translating rules $u \longrightarrow v$ into polynomials u-v and vice versa.