4. Group Rings

In this section we show how structural information on certain classes of groups can be used to prove termination of procedure PREFIX GR¨OBNER BASES and to improve it. Let us start with the classes of finite, free respectively plain groups. These groups have in common that they can be presented using convergent 2-monadic group presentations, i.e., $\Sigma$ contains inverses of length one for all generators and for all rules $(l,r) \in T$, $\vert l\vert \leq 2$ and $\vert r\vert \leq 1$ hold. In fact finite or free groups are also plain groups, but sometimes it is useful to take advantage of the additional information we have concerning them. For example we can improve the process of saturation. Given a non-trivial group element w we let $\ell(w)$ denote the last letter and ${\sf inv}\/(w)$ the inverse of w.

Definition 4..1   For a polynomial $p \in {\bf K}[{\cal G}]$ which has more than one monomial, we define

$$\sigma(p) \max \{ u \in {\cal G}\mid {\sf HT}(p \ast u) = {\sf HT}(p) \circ u \mbox{ is a prefix of } {\sf HT}(p) \}.$$ =

Then we can set ${\sf can}(p)= p \ast\sigma(p)$ and ${\sf acan}(p) = {\sf can}(p) \ast{\sf inv}\/(\ell({\sf HT}({\sf can}(p))))$. For a non-zero polynomial $\alpha \cdot t \in {\bf K}[{\cal G}]$ we set $\sigma(p)= {\sf inv}\/(t)$ and ${\sf can}(p) = {\sf acan}(p) = \alpha$.

Notice that ${\sf HT}({\sf can}(p)) = {\sf HT}(p) \circ\sigma(p)$, but in case p has more than one monomial ${\sf HT}({\sf acan}(p)) \neq {\sf HT}(p) \circ\sigma(p) \circ {\sf inv}\/(\ell({\sf HT}({\sf can}(p))))$.

Example 4..2   Let $\Sigma = \{ a,b \}$ and $T = \{ab \longrightarrow\lambda, ba \longrightarrow \lambda \}$ be a presentation of a group ${\cal G}$ with a length-lexicographical ordering induced by $a \succ b$. Then for the polynomial $p= b^4 + b^2 + \lambda \in {\bf Q}[{\cal G}]$ we get $\sigma(p) = a$, ${\sf can}(p) = p \ast\sigma(p) = \underline{b^3} + b + a$, and ${\sf acan}(p) = p \ast a^2 = b^{2} + \lambda + \underline{a^{2}}$.

These polynomials can be used to define prefix saturating sets.

Lemma 4..3   Let $p \in {\bf K}[{\cal G}]$ contain more than one monomial. Then the following statements hold:

(1)

In case ${\cal G}$ is a free group presented by $(\Sigma, T_{I})$, then $\mbox{\sc Sat}_p(p) = \{ {\sf can}(p), {\sf acan}(p) \}$ is a prefix saturating set for p.

(2)

In case ${\cal G}$ is a plain group presented by a reduced convergent 2-monadic group system $(\Sigma, T)$, $a = \ell({\sf HT}({\sf can}(p)))$ and $a' = \ell({\sf HT}({\sf acan}(p)))$, then $\mbox{\sc Sat}_p(p) = \{ {\sf can}(p), {\sf can}(p) \ast b \mid (ab, c) \in T \} \cup \{ {\sf acan}(p), {\sf acan}(p) \ast b \mid (a'b, c) \in T\}$ is a prefix saturating set for p.

Then we can compute finite prefix Gröbner bases of finitely generated right ideals for plain group rings using procedure PREFIX GR¨OBNER BASES and specifying saturating sets as described in lemma 4.3.

Theorem 4..4   Given a 2-monadic confluent group presentation for a group ${\cal G}$ and a finite set of polynomials $F \subseteq {\bf K}[{\cal G}]$, procedure PREFIX GR¨OBNER BASES terminates.

We continue to show how we can gain a similar result for context-free group rings. A finitely generated context-free group ${\cal G}$ is a group with a free normal subgroup of finite index. Hence, let the group ${\cal G}$ be given by X a finite set of generators for a free subgroup ${\cal F}$ and ${\cal E}$ a finite group such that $({\cal E}\backslash\{ \lambda \}) \cap X = \emptyset$ and ${\cal G}/{\cal F}\cong {\cal E}$. For all $e \in {\cal E}$ let $\phi_e : X \cup X^{-1} \longrightarrow{\cal F}$ be a function such that $\phi_{\lambda}$ is the inclusion and for all $x \in X \cup X^{-1}$, $\phi_e(x) = {\sf inv}\/(e) \circ_{{\cal G}} x \circ_{{\cal G}} e$. For all $e_1,e_2 \in {\cal E}$ let $z_{e_1,e_2} \in {\cal F}$ such that $z_{e_1,\lambda} \equiv z_{\lambda,e_1} \equiv\lambda$ and for all $e_1,e_2,e_3 \in {\cal E}$ with $e_1 \circ_{\cal E} e_2 =_{\cal E} e_3$, $e_1 \circ_{{\cal G}} e_2 \equiv e_3z_{e_1,e_2}$. Let $\Sigma = ({\cal E} \backslash \{ \lambda \}) \cup X \cup X^{-1}$ and let T contain the following rules:

		xx-1 

$\longrightarrow$
$\lambda$
and
		x-1x 

$\longrightarrow$
$\lambda$
for all $x \in X$,
		e1e2 

$\longrightarrow$


e3ze1,e2 for all 

$e_1,e_2 \in {\cal E} \backslash \{ \lambda \}, e_3 \in {\cal E}$
such that 

$e_1 \circ_{\cal E} e_2 =_{\cal E} e_3$,
		xe 

$\longrightarrow$


$e \phi_e(x)$
and
		x-1e 

$\longrightarrow$


$e \phi_e(x^{-1})$
for all        

$e \in {\cal E} \backslash \{ \lambda \}, x \in X$.

$(\Sigma, T)$ then is convergent and is called a virtually free presentation (compare [CrOt94]). Presenting ${\cal G}$ in this way we find that the elements of the group are of the form eu where $e \in {\cal E}$ and $u \in {\cal F}$. We can specify a total well-founded ordering on the group by combining a total well-founded ordering $\succeq_{\cal E}$ on ${\cal E}$ and a length-lexicographical ordering $\geq_{\rm lex}$ on ${\cal F}$: Let $w_1,w_2 \in {\cal G}$ such that $w_i \equiv e_iu_i$ where $e_i \in {\cal E}$, $u_i \in {\cal F}$. Then we define $w_1 \succ w_2$ if and only if |w₁| > |w₂| or (|w₁| = |w₂| and $e_1 \succ_{\cal E} e_2)$ or (|w₁| = |w₂|, $e_1 =_{\cal E} e_2$ and $u_1 >_{\rm lex} u_2)$. This ordering is compatible with right concatenation using elements in ${\cal F}$ in the following sense: Given $w_1,w_2 \in {\cal G}$ presented as described above, $w_1 \succ w_2$ implies $w_1u \succ w_2u$ for all $u \in {\cal F}$ in case $w_1u, w_2u \in {\cal G}$.

Example 4..5   Let ${\cal E}$ be the finite group presented by $\Sigma' = \{ a \}$ and $T' = \{ a^2 \longrightarrow\lambda \}$ and ${\cal F}$ the free group generated by $X = \{ x \}$. Further let $\phi_a(x) = x$ and $\phi_a(x^{-1}) = x^{-1}$ be a conjugation homomorphism. Then $\Sigma = \{a, x, x^{-1} \}$ and $T = \{ xx^{-1} \longrightarrow\lambda, x^{-1}x \longrightarrow\lambda \} \cup \... ...w \lambda \} \cup \{ xa \longrightarrow ax, x^{-1}a \longrightarrow a x^{-1} \}$ is a virtually free presentation of ${\cal G}$, the direct product of ${\cal E}$ and ${\cal F}$.

Let us take a closer look at prefix reduction in ${\bf K}[{\cal G}]$.

Example 4..6   Let ${\cal G}$ be the group specified in example 4.5. Further let $p = ax^2 + x + \lambda$, q₁ = a + x and $q_2 = x^2 + \lambda$ be polynomials in ${\bf Q}[{\cal G}]$.
Then the polynomial p is prefix reducible at its head term ax² by q₁ giving us

$$p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_... ...ambda - \underline{ax^2} - x^3 = x + \lambda + \underline{x^3}.$$

On the other hand, as x² is no prefix of ax², this is not true for q₂.

Since prefix reduction using a non-constant¹³ polynomial involves right multiples of the polynomial with elements in ${\cal F}$ only, we can restrict ourselves to special prefix-saturating sets.

Definition 4..7   A set $F \subseteq \{ \alpha \cdot p \ast w \mid \alpha \in {\bf K}^*, w \in {\cal F}\}$ is called a ${\cal F}$-prefix saturating set for a non-zero polynomial p in ${\bf K}[{\cal G}]$, if for all $w \in {\cal F}$ the polynomial $p \ast w$ is prefix reducible to zero using F in one step. A set of polynomials $F \subseteq {\bf K}[{\cal G}]$ is called a ${\cal F}$-prefix saturated set, if for all $f \in F$ and for all $w \in {\cal F}$ the polynomial $f \ast w$ is prefix reducible to zero using F in one step.

Reviewing the results on free groups, for a polynomial p in ${\bf K}[{\cal G}]$ we can specify ${\sf can}(p)$ and ${\sf acan}(p)$ and use them to define ${\cal F}$-prefix saturating sets.

Definition 4..8   For a non-zero polynomial $p \in {\bf K}[{\cal G}]$ containing more than one monomial we define

$$\sigma(p) = \max \{ u \in {\cal F}\mid {\sf HT}(p \ast u) = {\sf HT}(p) \circ u \mbox{ is a prefix of } {\sf HT}(p) \}$$

and set ${\sf can}(p)= p \ast\sigma(p)$. In case ${\sf HT}(p) \neq e{\sf inv}\/(\sigma(p))$ for $e \in {\cal E}$ we define ${\sf acan}(p)= {\sf can}(p) \ast{\sf inv}\/(\ell({\sf can}(p)))$ and else ${\sf acan}(p) = {\sf can}(p)$. For a polynomial $p = \alpha \cdot t \in {\bf K}[{\cal G}]$ we set ${\sf can}(p) = {\sf acan}(p) = \alpha$.

Lemma 4..9   For a non-zero polynomial p in ${\bf K}[{\cal G}]$ the set $\{ {\sf can}(p), {\sf acan}(p) \}$ is a ${\cal F}$-prefix saturating set.

Example 4..10   Let ${\cal G}$ be the group specified in example 4.5 and $p = ax^2 + x + \lambda$ a polynomial in ${\bf Q}[{\cal G}]$. Then the polynomials $p \ast x^{-1} = \underline{ax} + \lambda + x^{-1} = {\sf can}(p)$ and $p \ast x^{-2} = a + x^{-1} + \underline{x^{-2}} = {\sf acan}(p)$ give us a ${\cal F}$-prefix-saturating set for p.

The following lemma will be used as an analogon to lemma 3.30 when we characterize prefix Gröbner bases by using prefix reduction, prefix s-polynomials and now ${\cal F}$-prefix saturated sets.

Lemma 4..11   Let p be a non-zero polynomial and F a set of polynomials in ${\bf K}[{\cal G}]$.
Then $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{F}\,$ } 0$ gives us a representation of $p = \sum_{i=1}^k \alpha_i \cdot f_i \ast w_i$, with $\alpha_i \in {\bf K}^*, f_i \in F, w_i \in {\cal G}$ such that for all $w \in {\cal F}$ with ${\sf HT}(p \ast w) \equiv{\sf HT}(p)w$, we get ${\sf HT}(p)w \succeq {\sf HT}(f_i \ast w_i \ast w)$. In particular for all $t \in {\cal M}$ with $t \succeq {\sf HT}(p)$, if $t \circ w \equiv tw$ for some $w \in {\cal M}$, then $tw \succeq {\sf HT}(f_i \ast w_i \ast w)$ holds.

For every $e \in {\cal E}$ let the mapping $\psi_e: {\bf K}[{\cal G}] \longrightarrow{\bf K}[{\cal G}]$ be defined by $\psi_e(f) := f \ast e$ for $f \in {\bf K}[{\cal G}]$. We now can give a characterization of prefix Gröbner bases by transforming a generating set for a right ideal using these finitely many mappings. This will enable us to restrict ourselves to ${\cal F}$-prefix saturated sets when characterizing prefix Gröbner bases.

Theorem 4..12   Let $F \subseteq {\bf K}[{\cal G}]$ and $G \subseteq {\bf K}[{\cal G}]$ such that

(a)

${\sf ideal}_{r}^{}(F) = {\sf ideal}_{r}^{}(G)$,

(b)

$F \cup \{ \psi_e(f) \vert f \in F, e \in {\cal E} \} \subseteq G$, and

(c)

G is ${\cal F}$-prefix saturated.

Then the following statements are equivalent:

(1)

For all $g \in {\sf ideal}_{r}^{}(F)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ } 0$.

(2)

For all $f_{k}, f_{l} \in G$ we have ${\sf spol}_{p}(f_{k}, f_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ } 0$.

On first sight the characterization given in theorem 4.12 above might seem artificial. The crucial point is that in losing the property ``admissible'' for our ordering, an essential lemma in Buchberger's context, namely that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{F}\,$ } 0$ implies $p \ast w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{F}\,$ } 0$ for any term w, no longer holds. Defining reduction by restricting ourselves to prefixes we gain enough structural information to weaken this lemma, but we have to do additional work to still describe the right ideal congruence. One step is to close the set of polynomials generating the right ideal with respect to the finite group ${\cal E}$: For a set of polynomials F using the ${\cal E}$-closure $F_{\cal E} = \{ \psi_e(f) \mid f \in F, e \in {\cal E} \}$ we can characterize the right ideal generated by F in terms of $F_{\cal E}$ since ${\sf ideal}_{r}^{}(F) = \{ \sum_{i = 1}^k \alpha_i \cdot f_i \ast u_i \mid \alpha_i \in {\bf K}, f_i \in F_{\cal E}, u_i \in {\cal F}\}$. If we additionally incorporate the concept of saturation, prefix reduction can be used to express the right ideal congruence and then a prefix Gröbner basis can be characterized as usual by prefix s-polynomials. Now, using the characterization given in theorem 4.12 we can modify procedure PREFIX GR¨OBNER BASES as follows:

Procedure: PREFIX GR¨OBNER BASES IN CONTEXT-FREE GROUP RINGS
< tex2html_comment_mark>

Given: 		 A finite set of polynomials 

$F \subseteq {\bf K}[{\cal M}]$,
and
		  

$(\Sigma, T)$
a virtually free presentation of                   ${\cal G}$.
Find: 		 

$\mbox{\sc Gb}(F)$
a prefix Gröbner basis of F.

G := 

$\{ {\sf can}(\psi_e(f)), {\sf acan}(\psi_e(f)) \mid e \in {\cal E}, f\in F \}$;
% G fulfills (a), (b) and (c) of theorem 4.12
B := 

$\{ (q_{1}, q_{2}) \mid q_{1}, q_{2} \in G, q_{1} \neq q_{2} \}$;
while 

$B \neq \emptyset$
do
		% Test if  statement (2) of theorem 4.12 is valid
		  

(q1, q2) := remove(B);
		  % Remove an element using a fair strategy
		      if 		  

${\sf spol}_{p}(q_{1}, q_{2})$
exists
		 		 % The s-polynomial is not trivial
		 		then		   h:= normal form

$({\sf spol}_{p}(q_{1}, q_{2}),\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm p}}_{G}\,$ })$;
		 		 		 % Compute a normal form using        prefix reduction
		 		 		      if 		 $h \neq 0$
		 		 				      then 		 G := 

$G \cup \{ {\sf can}(h), {\sf acan}(h)\}$;
		 		 				 		% G fulfills (a), (b) and (c) of theorem 4.12
		 		 				 		 B := 

$B \cup \{ (f, {\tilde h}), ( {\tilde h},f) \mid f \in G, {\tilde h} \in \{ {\sf can}(h), {\sf acan}(h) \} \}$;
		 		 		 endif
		 endif 
endwhile  


$\mbox{\sc Gb}(F):= G$

Termination can be shown as in theorem 4.4.

Notice that the classes of groups studied in this section are known to have solvable subgroup problem. For free groups there is Nielsen's approach known as Nielsen reduction (compare [LySch77,AvMa84]). Kuhn and Madlener have developed prefix reduction methods and applied them successfully to the class of plain groups (see [KuMa89]). Cremanns and Otto successfully treated the class of context-free groups (see [CrOt94]).