5. Prefix Gröbner Bases in $\mathbb {Z}[{\cal M}]$ and $\mathbb {Z}[{\cal M}]^k$

In [3] it was shown how to characterize and compute prefix Gröbner bases in monoid rings $\mathbb {Z}[{\cal M}]$ where ${\cal M}$ is presented by a finite convergent string rewriting system. Here we want to show that if a finite prefix Gröbner basis exists for a right ideal, then there is also a finite reduced prefix Gröbner basis and we want to list two important properties of such a basis needed to characterize the solutions of the homogeneous equations in the previous section. Further we outline how the technique of Gröbner bases extends to right $\mathbb {Z}[{\cal M}]$-modules $\mathbb {Z}[{\cal M}]^k$.

In order to use elements of $\mathbb {Z}[{\cal M}]$ as rules for reduction we need an ordering on $\mathbb {Z}$ and one on ${\cal M}$: We will first specify a total well-founded ordering on $\mathbb {Z}$ ⁶:

$$a <_Z b \mbox{ iff } \left\{ \begin{array}{l} a \geq 0 \mbox{... ...{ and } a<b \\ a<0, b<0 \mbox{ and } a>b \end{array} \right.$$

and $a \leq_Z b$ iff $a=b$ or $a <_Z b$⁷.

As ordering on ${\cal M}$ we take the one induced by the completion ordering on $\Sigma^*$ of the string rewriting system. This ordering has the advantage that it is admissible with respect to concatenation and we have $uv > u \ast v$ where $u,v \in {\cal M}$ and the multiplication $\ast$ on ${\cal M}$ is realized by normal form computation with respect to the string rewriting system presenting ${\cal M}$.

Then for any $p \in \mathbb {Z}[{\cal M}]$ we can characterize its largest term as head term ${\sf HT}(p)$, the coefficient of this term as ${\sf HC}(p)$, ${\sf HM}(p) = {\sf HC}(p) \cdot {\sf HT}(p)$ and ${\sf RED}(p) = p - {\sf HM}(p)$.

Let us briefly recall the reduction relation used for $\mathbb {Z}[{\cal M}]$ in [3].

Definition 4   Let $p$, $f$ be two non-zero polynomials in $\mathbb {Z}[{\cal M}]$.
We say $f$ prefix reduces $p$ to $q$ at $a \cdot t$ in one step, i.e. $p \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{g}\,$} q$, if

(a)

$t \equiv {\sf HT}(f)u$ for some $u \in {\cal M}$, i.e. ${\sf HT}(f)$ is a prefix of $t$ as a word.

(b)

${\sf HC}(f) > 0$ and $a = {\sf HC}(f) \cdot b + d$ with $b,d \in \mathbb {Z}$, $b \neq 0$, and $0 \leq d < {\sf HC}(f)$.

(c)

$q = p - f \ast (b \cdot u)$.

Prefix Gröbner bases with respect to this reduction relation then can be characterized using the concept of prefix s-polynomials combined with some extra polynomials which are necessary to describe the whole right ideal congruence by prefix reduction.

Definition 5   Given two polynomials $p_{1}, p_{2} \in \mathbb {Z}[{\cal M}]$ with $HC(p_{i}) = c_{i}>0, HT(p_{i}) = t_{i}, RED(p_{i}) = r_{i}$ for $i = 1, 2$. If there is $u \in {\cal M}$ with $t_{1} \equiv t_{2}u$ we have to distinguish:

1. If $c_1 \geq c_2$, $c_{1} = a\cdot c_{2} + b$, where $a, b \in \mathbb {Z}$, $0 \leq b <c_2$, we get the following superposition causing a critical pair:
   $a \cdot c_{2} \cdot t_{2}u + b \cdot t_2u = c_{1} \cdot t_{1}$
   $\swarrow \hspace{4cm} \searrow$
   $-a \cdot r_{2} \ast u + b \cdot t_{2}u$ $- r_{1}$
   
   This gives us the prefix s-polynomial
   
   $${\sf spol}_{p}(p_{1}, p_{2}) = a \cdot r_{2} \ast u - b \cdot t_{2}u - r_{1} = a \cdot p_2 \ast u - p_1.$$
   
   

2. If $c_2>c_1$, $c_{2} = a\cdot c_{1} + b$, where $a, b \in \mathbb {Z}$, $0 \leq b <c_1$, we get the following superposition causing a critical pair:
   $c_{2} \cdot t_{2}u = a \cdot c_{1} \cdot t_{1} + b \cdot t_{1}$
   $\swarrow \hspace{4cm} \searrow$
   $-r_{2} \ast u$ $-a \cdot r_{1} + b \cdot t_{1}$
   
   This gives us the prefix s-polynomial
   
   $$spol_p(p_{1}, p_{2}) = a \cdot r_{1} - r_{2} \ast u - b \cdot t_{1} = a \cdot p_1 - p_2 \ast u.$$
   
   

Prefix Gröbner bases then can be characterized by the following theorem from [6]:

Theorem 6   Equivalent are:

1. $ideal_{r}(G) \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$.
2. • For all $g_{k}, g_{l} \in G$ we have ${\sf spol}_{p}(g_{k}, g_{l}) \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$.
   • For all $g \in G$, $w \in C({\sf HT}(g)) = \{ w \in \Sigma^* \mid {\sf HT}(g)w \equiv t_{1}t_{2}w \equiv t_{1}l, t_2 \neq 1, (l, r) \in T \}$ we have $g \ast w \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$.

The set $G$ then is called a prefix Gröbner basis of the right ideal it generates. Notice that without loss of generality we can always assume that all head coefficients of its polynomials are greater than zero.

Lemma 7   Let $G$ be a finite prefix Gröbner basis and $g \in G$ such that $g \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G \backslash \{ g \}}\,$} g'$. Then $G\backslash \{ g \} \cup \{ canon(g') \}$⁸ is again a prefix Gröbner basis of the same right ideal.

Proof : 1.1  
This follows as $\mathbb {Z}[{\cal M}]$ can be shown to be a ring with a reduction relation fulfilling the axioms (A1) - (A4) for reduction rings as presented in [4]. It is easy to see that the reduction relation is terminating (A1), preserves the right ideal congruence (A2) and for any non-zero polynomial $p \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{p}\,$} 0$ holds (A3). The important axiom allowing to reduce prefix Gröbner bases without losing the prefix Gröbner basis property⁹(A4) holds if for any $h,p,f,q \in \mathbb {Z}[{\cal M}]$, $h \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{p}\,$}$ and $p \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{f}\,$} q$ imply $h \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{\{ f,q \}}\,$}$.
Let $h \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{p}\,$}$ at some monomial $a \cdot t$, i.e.  $t \equiv {\sf HT}(p)u$ for some $u \in {\cal M}$, $a = {\sf HC}(p) \cdot b + d$, $b,d \in \mathbb {Z}$, $b \neq 0$ and $0 \leq d < {\sf HC}(p)$. Moreover, let $p \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{f}\,$} q$ at some monomial $c \cdot s$, i.e.  $s \equiv {\sf HT}(f)v$ for some $v \in {\cal M}$, $c = {\sf HC}(f) \cdot b' + d'$, $b',d' \in \mathbb {Z}$, $b' \neq 0$ and $0 \leq d' < {\sf HC}(f)$. We have to distinguish the following cases:

1. If $t \neq s$ then we are done at once, since ${\sf HM}(q) = {\sf HM}(p)$ and hence $h \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{q}\,$}$.
2. If $t = s$ we have to be more careful as $c \cdot s = {\sf HM}(p)$, i.e. the reduction step took place at the head monomial of $p$ and $c = {\sf HC}(p)$, $s = {\sf HT}(p)$.
   1. If $d' \neq 0$ then ${\sf HM}(q) = d' \cdot {\sf HT}(p)$. We get $a = {\sf HC}(p) \cdot b + d = ({\sf HC}(f) \cdot b' + d') \cdot b + d = {\sf HC}(f) \cdot (b' \cdot b) + d' \cdot b + d$. Now either $0 \leq d' \cdot b + d < {\sf HC}(f)$ or there exist $b'', d'' \in \mathbb {Z}$ such that $d' \cdot b + d = {\sf HC}(f) \cdot b'' + d''$ with $0 \leq d'' < {\sf HC}(f)$. In either case $h$ then can be prefix reduced using $f$.
   2. If $d'=0$ then ${\sf HC}(p) = {\sf HC}(f) \cdot b'$ and hence $a = {\sf HC}(f) \cdot b' \cdot b$ and $t \equiv {\sf HT}(p)u \equiv {\sf HT}(f)vu$ imply that $h$ is prefix reducible by $f$.

Now it is easy to see that $G' = G \backslash \{ g \} \cup \{ canon(g') \}$ is again a prefix Gröbner basis of the same right ideal. If some polynomial $h \in {\sf ideal}_{r}^{}(G)$ is reducible by $G$ it will also be reducible by $G'$. q.e.d.

1 Now a prefix Gröbner basis $G$ is called reduced if no $g \in G$ is prefix reducible by $G\backslash\{g\}$.

Lemma 8   Let $G$ be a reduced prefix Gröbner basis. Further let $g_1,g_2 \in G$ such that ${\sf HC}(g_i) = c_i > 0$ and ${\sf HT}(g_2) \equiv {\sf HT}(g_1)u$ for some $u \in {\cal M}$. Then $c_1 = c_2 \cdot b$ for some $b \in \mathbb {N}\backslash \{ 0,1 \}$ and $u \neq 1$.

Proof : 1.1  
We show that the other cases are not possible.

1. Assume that $u = 1$.
   Then without loss of generality we can also assume $c_1 > c_2$ and hence $c_1 = c_2 \cdot b + d$, $b, d \in \mathbb {N}$, $b \neq 0$ and $0 \leq d < c_2$. Therefore, $g_1 \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{g_2}\,$} g_1 - g_2 \cdot b$ contradicting the assumption that $G$ is supposed to be reduced.
2. Now let $u \neq 1$. We have to distinguish two cases:
   1. If $c_1 > c_2$ again we have $c_1 = c_2 \cdot b + d$, $b, d \in \mathbb {N}$, $b \neq 0$ and $0 < d < c_2$. This situation now gives rise to an s-polynomial ${\sf spol}_{p}(g_1, g_2) = g_1 \ast u - g_2 \cdot b$. Notice that this s-polynomial has head monomial $d \cdot {\sf HT}(g_2)$ and hence is neither reducible by $g_1$ nor by $g_2$. On the other hand, as $G$ is a prefix Gröbner basis, the s-polynomial must be reducible to zero using elements of $G$. Additionally we know that $g_2$ is reducible by this s-polynomial which implies that then $g_2$ must also be reducible by some element in $G$ contradicting our assumption of $G$ being reduced.
   2. If $c_2>c_1$ we get $c_2 = c_1 \cdot b + d$, $b, d \in \mathbb {N}$, $b \neq 0$ and $0 \leq d < c_1$. Then $g_2 \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{g_1}\,$} g_2 - g_1 \cdot (b \cdot u)$ as before contradicting the assumption that $G$ is supposed to be reduced.

Hence the only possible case remains to be $c_1 = c_2 \cdot b$ for some $b \in \mathbb {N}\backslash \{ 0,1 \}$ and $u \neq 1$. As before this gives rise to an s-polynomial, but now we cannot conclude that one of the polynomials $g_1$, $g_2$ is reducible by it hence since we get no contradiction to $G$ being reduced, this case is possible. q.e.d.

1

If we want to compute prefix Gröbner bases of submodules in a right $\mathbb {Z}[{\cal M}]$-module $\mathbb {Z}[{\cal M}]^k$ this can be done by introducing a reduction relation and completing it. Provided a finite basis ${\bf e}_1 = (1, 0, \ldots, 0)$, ..., $(0, \ldots, 0, 1)$ of $\mathbb {Z}[{\cal M}]^k$ its elements can be represented by polynomials ${\bf f} = \sum_{i=1}^k {\bf e}_i \cdot f_i$. A reduction relation now can be defined as follows:

Definition 9   Let ${\bf f} = \sum_{i=1}^k {\bf e}_i \ast f_i$, ${\bf p} = \sum_{i=1}^k {\bf e}_i \ast p_i\in \mathbb {Z}[{\cal M}]^k$. We say that ${\bf f}$ prefix reduces ${\bf p}$ to ${\bf q}$ at ${\bf e}_s \ast p_s$ in one step, denoted by ${\bf p} \longrightarrow _{\bf f} {\bf q}$, if

(a)

$p_j = 0$ for $1 \leq j \leq s$,

(b)

$p_s \mbox{$\,\stackrel{}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{f_s}\,$} q_s$ with $q_s = p_s - a \cdot f_s \ast w$, and

(c)

${\bf q} = {\bf p} - a \cdot {\bf f} \ast w = (p_1, \ldots , p_{s-1}, q_s, p_{s+1} - a \cdot f_{s+1} \ast w, \ldots , p_k - a \cdot f_k \ast w)$.

Hence prefix reduction in $\mathbb {Z}[{\cal M}]^k$ reduces to prefix reduction in $\mathbb {Z}[{\cal M}]$. One can show that $\mathbb {Z}[{\cal M}]^k$ together with this reduction relation fulfills (A1) - (A4) for reduction rings as specified in [4] and Gröbner bases can be characterized using g- and m-polynomials. The basic idea is to compute a prefix Gröbner basis of a right $\mathbb {Z}[{\cal M}]$-module generated by a set of vectors $F$ by modifying the set $F$ according to the following steps:

1. initialize a counter $i = 1$,
2. compute a prefix Gröbner basis of the right ideal generated by the head terms of those vectors ${\bf f} \in F$ with ${\sf nz}({\bf f}) = i$ which is in fact a prefix Gröbner basis computation in $\mathbb {Z}[{\cal M}]$ which also affects the components of the vectors involved ``below'' the i-th component,
3. compute a set of solutions for the homogeneous equation related to those vectors ${\bf f} \in F$ with ${\sf nz}({\bf f}) = i$ hence generating new generators for the submodule with non-zero component larger than $i$,
4. continue for $i = i+1$ until all components have been handled.