3. Towards Gröbner Bases

In commutative polynomial rings there is a strong relation between Gröbner bases of an ideal and its quotient ring. In fact Gröbner bases enable computations in the quotient ring by normal form computations. The quotient is determined as a $\mathbb{K}$-vector space by the natural basis associated to the reduced Gröbner basis of the ideal. This natural basis consists of those commutative terms which are irreducible with respect to the Gröbner basis, i.e. it is a regular subset of the commutative terms (when viewed as a formal language). Of course such a vector space basis is strongly dependent on the ordering chosen for computing the Gröbner basis. In [8] the procedure MATPHI is presented which, given a reduced Gröbner basis, enumerates the natural basis: This is done systematically by initializing the natural basis to $N = \{ \lambda \}$ and the set of border elements to $B = \{ X_i \mid X_i \mbox{ is a variable of the polynomial ring} \}$. While there are elements in B the minimal one $\tau$ is removed and it is checked whether it is irreducible with respect to the Gröbner basis. If this is the case for each new element $\tau$ added to N the border elements $\tau X_i$ are added to B. On termination N contains the natural basis. Additionally MATPHI computes a multiplication table which for each $m \in N$ and each variable X_i contains the result of the normal form computation ${\sf normal.form}(mX_i, \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{G}\,$ })$. While in general the entries of this multiplication table are vectors, when restricted to binomial polynomials they can be interpreted as terms. Notice that then the output is similar to the one produced by TC where on termination we get a set of coset representatives and a multiplication table $g \circ a$ for all coset representatives g and $a \in \bar{\Sigma}$.

However, MATPHI works in the setting of commutative polynomial rings using a Gröbner basis as input while TC belongs to the setting of groups using arbitrary relators and subgroup generators as input. In order to compare both methods, we have to use the generalized setting presented in Section 1 - binomial ideals in free group rings - and enable the new procedure to deal with possibly infinite generating sets $U \cup N(R)$ in a finitary manner.

To encode the input of TC as binomials we associate the relators R and the subgroup generators U with two sets of polynomials $F_R = \{ r -1 \mid r \in R \}$ and $F_U = \{ u -1 \mid u \in U \}$. Essentially we want to check whether the subgroup generated by $U \cup N(R)$ in ${\mathcal{F}}$ is finitely generated and this will be done in an incremental fashion using the fact that for a given finitely generated subgroup of a free group the membership problem can be solved using prefix Gröbner bases and the generating subset of the subgroup is then enlarged by adding polynomials modified by left multiplication with suitable group elements in order to ``approximate'' N(R).

To compute prefix Gröbner bases of subgroups in the free group ring $\mathbb{K} [{\mathcal{F}}]$ we need the concept of weak prefix saturation: A set $F \subseteq \mathbb{K} [{\mathcal{F}}]$ is called weakly prefix saturated if for every $p \in F$, $w \in {\mathcal{F}}$ we have $p \ast w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$. This becomes necessary as the ordering on $\mathbb{K} [{\mathcal{F}}]$ is no longer admissible (see [23] for the details).

Theorem 5 ([23])   A set $F \subseteq \mathbb{K} [{\mathcal{F}}]$ is a prefix Gröbner basis of the right ideal it generates if it is prefix reduced and weakly prefix saturated.

The property of being weakly saturated can be ensured for a set of polynomials by using a procedure to compute a saturating set for a polynomial, i.e. a set such that each right multiple of the polynomial prefix reduces to 0 in one step by a polynomial in the saturating set. For free groups there are saturating sets consisting of at most two polynomials called ${\sf can}$ and ${\sf acan}$. In our setting of binomials u - v, informally ${\sf can}(u-v)$ is gained from u-v by ``shortening'' the head term u without losing its head position while ${\sf acan}(u-v)$ is derived from ${\sf can}(u-v)$ by forcing the shortened head term to lose its head position by cutting off its last letter. Then ${\sf can}(u - v) = xa - y$ and ${\sf acan}(u - v) = (xa - y) \circ a^{-1}$ where $x, y \in {\mathcal{F}}$, $a, a^{-1} \in \bar{\Sigma}$ and there exists $w \in {\mathcal{F}}$ such that $u \equiv xaw$, $y = v \circ w^{-1}$, ${\sf HT}({\sf can}(u-v)) = {\sf HT}((u-v) \circ w^{-1}) = u \circ w^{-1} \equiv xa$ and ${\sf HT}({\sf acan}(u-v)) = {\sf HT}((u-v) \circ w^{-1}a^{-1}) = v \circ w^{-1}a^{-1} \equiv ya^{-1}$.

Procedure: PREFIX GR¨OBNER BASES OF RIGHT IDEALS IN FREE GROUP RINGS
< tex2html_comment_mark>

Given: 		 A finite set 

$F \subseteq \mathbb{K} [{\mathcal{F}}]$.
Find: 		 G, the monic reduced prefix Gröbner basis of the right ideal generated by F.
[1ex]G := 

$\{ {\sf can}(f), {\sf acan}(f) \mid f \in F \}$;
while there is $g \in G$
such that 

${\sf HT}(g)$
is prefixreducible by 

$G \backslash \{ g \}$
do
		 G := 

$G \backslash \{ g \}$;
		 f := 

${\sf normal.form}(g,\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ })$;
		 % Compute a normal form (if non-zero with head coefficient 1).
		 if 		$f \neq 0$
		 		then 		G := 

$G \cup \{ {\sf can}(f), {\sf acan}(f) \}$;
		 endif 
endwhile

Correctness and termination follow from the results presented in [23,16]. The procedure can be used to solve the subgroup problem for a subgroup in ${\mathcal{F}}$:

Theorem 6 ([15])   Let U be the generating subset of a subgroup $\mathcal{U}$ in ${\mathcal{F}}$. Then $w \in {\mathcal{F}}$ is an element of $\mathcal{U}$ if and only if w prefix reduces to 1 using a prefix Gröbner basis of the right ideal generated by $\{ u -1 \mid u \in U\}$ in $\mathbb{K} [{\mathcal{F}}]$.

In [23] it was shown how the computation of the monic prefix Gröbner basis as well as the resulting solution for the subgroup problem are related to Nielsen reduction:

Theorem 7   Let U be a finite subset of ${\mathcal{F}}$ and G the monic reduced prefix Gröbner of the right ideal generated by $\{ u -1 \mid u \in U\}$ in $\mathbb{K} [{\mathcal{F}}]$. Then the set $X_G = \{ uv^{-1} \mid u-v \in G \}$ is Nielsen reduced for U.

However, in general the subgroup ${\mathcal{H}}$ of ${\mathcal{F}}$ we are interested in is generated by the set $U \cup N(R)$ where the set of relators is not empty. We have to find a way to treat this possibly infinitely generated subgroup of ${\mathcal{F}}$ in a finitary manner in order to verify whether it is in fact finitely generated. The normal closure of a set of relators R can be approached using a result similar to the one presented in [11] to solve the ideal membership problem for two-sided ideals in solvable polynomial rings using one-sided ideals (compare also Zharkov's idea to compute Janet bases in [27]). For a set $F \subseteq \mathbb{K} [{\mathcal{F}}]$ let ${\sf ideal}_{}^{}(F)$ denote the two-sided and ${\sf ideal}_{r}^{}(F)$ the right ideal generated by F in $\mathbb{K} [{\mathcal{F}}]$.

Theorem 8 ([16])   For $F \subseteq \mathbb{K} [{\mathcal{F}}]$ the following properties are equivalent:

1.

F is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(F)$ and ${\sf ideal}_{r}^{}(F) = {\sf ideal}_{}^{}(F)$.

2.

F is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(F)$ and for all $w \in {\mathcal{F}}$, $p \in F$ we have $w \ast p \in {\sf ideal}_{r}^{}(F)$.

3.

F is a prefix Gröbner basis of ${\sf ideal}_{r}^{}(F)$ and for all $a \in \bar{\Sigma}$, $p \in F$ we have $a \ast p \in {\sf ideal}_{r}^{}(F)$.

This theorem is the basis of a procedure which computes prefix Gröbner bases of two-sided ideals by iterating the computation of prefix Gröbner bases and extending them by multiplication with elements in $\bar{\Sigma}$ until a prefix Gröbner basis of the two-sided ideal is computed. For a set of relators R, on input $F_R = \{ r -1 \mid r \in R \}$ this is equivalent to computing a prefix Gröbner basis of an encoding of the the normal closure of R and it halts if and only if the subgroup generated by N(R) in ${\mathcal{F}}$ is finitely generated. This will be a special case of the procedure presented in the next section.