3. The General Case

Let $f_{i,j} \in \mathbb {Z}[{\cal M}]$, $1 \leq i \leq m$, $0 \leq j \leq k$ and

$$f_{1,1} \ast X_1 + \ldots + f_{1,m} \ast X_m = f_{1,0}$$

$$f_{2,1} \ast X_1 + \ldots + f_{2,m} \ast X_m = f_{2,0}$$

$$\vdots \phantom{ + f_{2,m} \ast X_m } \vdots$$

$$f_{k,1} \ast X_1 + \ldots + f_{k,m} \ast X_m = f_{k,0}$$

be the system of equations we want to solve in $\mathbb {Z}[{\cal M}]$. Let ${\bf f}_i = (f_{1,i}, f_{2,i}, \ldots, f_{k,i})$, $0 \leq i \leq m$ be vectors in the right $\mathbb {Z}[{\cal M}]$-module $\mathbb {Z}[{\cal M}]^k$. Hence we can abbreviate the system of inhomogeneous equations by

$${\bf f}_1 \cdot X_1 + \ldots + {\bf f}_m \cdot X_m = {\bf f}_0.$$ (4)

In order to describe the generating set of solutions we have to find one solution of the inhomogeneous system 4 and if possible a finite set of generators for the solutions of the homogeneous system

$${\bf f}_1 \cdot X_1 + \ldots + {\bf f}_m \cdot X_m = {\bf0}.$$ (5)

We can proceed as described in the previous section. Of course now the prefix Gröbner bases are bases of submodules in the right $\mathbb {Z}[{\cal M}]$-module $\mathbb {Z}[{\cal M}]^k$, i.e., their elements are vectors ${\bf g}_{i} = (g_{1,i}, g_{2,i}, \ldots, g_{k,i})$ in $\mathbb {Z}[{\cal M}]^k$.

1. Let $G = \{ {\bf g}_1, \ldots, {\bf g}_n \}$ be a finite reduced prefix Gröbner basis of the right submodule generated by $\{ {\bf f}_1, \ldots, {\bf f}_m \}$ in $\mathbb {Z}[{\cal M}]^k$, and ${\bf F} = ({\bf f}_1, \ldots, {\bf f}_m)$, ${\bf G} = ({\bf g}_1, \ldots, {\bf g}_n)$ the corresponding vectors of course now in $(\mathbb {Z}[{\cal M}]^k)^m$ respectively $(\mathbb {Z}[{\cal M}]^k)^n$. There are two linear mappings given by matrices $P \in {\sf M}_{m \times n}(\mathbb {Z}[{\cal M}])$, $Q \in {\sf M}_{n \times m}(\mathbb {Z}[{\cal M}])$ such that ${\bf F} \cdot P = {\bf G}$ and ${\bf G} \cdot Q = {\bf F}$.
2. Equation 4 is solvable if and only if ${\bf f}_0 \in {\sf submodule}_{r}{}(\{ {\bf f}_1, \ldots, {\bf f}_m \})$ which is again decidable using prefix reduction with respect to $G$.
3. Let $\{ {\bf z}_1, \ldots, {\bf z}_r \} \subseteq \mathbb {Z}[{\cal M}]^n$ be a generating set for the solutions of the homogeneous system
   

   $${\bf g}_1 \ast X_1 + \ldots + {\bf g}_n \ast X_n = {\bf0}.$$ (6)

   
   
   and let $I_m$ be the $m \times m$ identity matrix. Further let ${\bf w}_1, \ldots, {\bf w}_m \in \mathbb {Z}[{\cal M}]^m$ be the columns of the matrix $P \cdot Q - I_m$. Since ${\bf F} \cdot (P \cdot Q - I_m) = {\bf F} \cdot P \cdot Q - {\bf F} \cdot I_m = {\bf G} \cdot Q - {\bf F} = 0$ these are solutions of the homogeneous system 5 as well. We can even show that the set $\{ {P \cdot {\bf z}_1,} \ldots, {P \cdot {\bf z}_r,} {\bf w}_1, \ldots, {\bf w}_m \}$ generates all solutions of 5:
   Let ${\bf q} = (q_1, \ldots, q_m)$ be an arbitrary solution of system 5, i.e.  ${\bf F} \ast {\bf q} = 0$. Then $Q \cdot {\bf q}$ is a solution of system 6 as ${\bf F} = {\bf G} \cdot Q$. Hence there are $h_1, \ldots, h_r \in \mathbb {Z}[{\cal M}]$ such that $Q \cdot {\bf q} = {\bf z}_1 \ast h_1 + \ldots {\bf z}_r \ast h_r$. Further we find
   

   $${\bf q} = P \cdot Q \cdot {\bf q} - (P \cdot Q - I_m) \cdot {\bf q}$$

   $$= P \cdot {\bf z}_1 \ast h_1 + \ldots + P \cdot {\bf z}_r \ast h_r$$

   $$+ {\bf w}_1 \cdot q_1 + \ldots + {\bf w}_m \cdot q_m$$

   
   
   and hence ${\bf q}$ is a right linear combination of elements in $\{ P \cdot {\bf z}_1, \ldots, P \cdot {\bf z}_r, {\bf w}_1, \ldots, {\bf w}_m \}$.

Now the important part is to find a generating set for the solutions of the homogeneous system 6. Let $G = \{ {\bf g}_1, \ldots, {\bf g}_n \}$ be a finite reduced prefix Gröbner basis of the right submodule generated by $\{ {\bf f}_1, \ldots, {\bf f}_m \}$. Notice that for vectors ${\bf f}$ the head term is defined to be the polynomial in the first non-zero component. We define ${\sf nz}({\bf f}) = i$ where $f_j = 0$ for $1 \leq j < i$ and $f_i \neq 0$, ${\sf nz}({\bf0}) = 0$. See Section 5 for details how to realize a reduction relation for the module case. Hence we get ${\sf HT}({\bf f}) \in \mathbb {Z}[{\cal M}]$ and ${\sf HT}({\sf HT}({\bf f})) \in {\cal M}$. As before we have to distinguish two cases.

1. For every ${\bf g}_i,{\bf g}_j \in G$ with ${\sf nz}({\bf g}_i) = {\sf nz}({\bf g}_j)$ such that ${\sf HT}({\sf HT}({\bf g}_i)) = {\sf HT}(g_{i,s}) = t_{i,s}$ is a prefix (as a word) of ${\sf HT}({\sf HT}({\bf g}_{j,s}))= t_{j,s}$, i.e.  $t_{j,s} \equiv t_{i,s}u$ for some $1 \neq u \in {\cal M}$, by Lemma 8 we know ${\sf HC}(g_{i,s}) = {\sf HC}(g_{j,s}) \cdot b$ for some $b \in \mathbb {N}\backslash \{ 0,1 \}$. We determine vectors ${\bf a}_{ij}$ as follows:
   
   $${\sf spol}_{}({\bf g}_i,{\bf g}_j) = b \cdot {\bf g}_j - {\bf g}_i \ast u = \sum_{l=1}^n {\bf g}_l \ast h_l,$$
   
   
   where the polynomials $h_l \in \mathbb {Z}[{\cal M}]$ are due to the reduction sequence ${\sf spol}_{}({\bf g}_i,{\bf g}_j) \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$.
   Then ${\bf a}_{ij} = ( \alpha_1, \ldots, \alpha_n)$, where
   

   $$\alpha_i = h_i + u,$$

   $$\alpha_j = h_j - b,$$

   $$\alpha_l = h_l,$$

   
   
   $l \neq i,j$, is a solution of 6 as $\sum_{l=1}^n {\bf g}_l \ast h_l -b \cdot {\bf g}_j + {\bf g}_i \ast u = 0$.
2. For $t \in {\cal M}$ let $C(t) = \{ w \in \Sigma^* \mid tw \equiv u_{1}u_{2}w \equiv u_{1}l, u_2 \neq 1$ for some $(l, r) \in T \}$. Additionally, we define vectors ${\bf b}_{i,\ell} = ( \beta_1, \ldots, \beta_n)$ for ${\sf HT}({\sf HT}({\bf g}_i)) = {\sf HT}(g_{i,s}) = t_{i,s}$ and $1 \leq \ell \leq \vert C(t_{i,s})\vert$ as follows: Let $C(t_{i,s}) = \{ w_1, \ldots, w_s \}$. For every ${\bf g}_i \ast w_{\ell}$ we know ${\bf g}_i \ast w_\ell= \sum_{l=1}^n {\bf g}_l \ast h_l$ as $G$ is a prefix Gröbner basis. Then ${\bf b}_{i,\ell} = ( \beta_1, \ldots, \beta_n)$, where
   

   $$\beta_i = h_i - w_{\ell},$$

   $$\beta_l = h_l,$$

   
   
   $l \neq i$, is a solution of system 6 as $\sum_{l=1}^n {\bf g}_l \ast h_l - {\bf g}_i \ast w_\ell = 0$.

Lemma 3   The finitely many vectors ${\bf a}_{i,j}, {\bf b}_{i,\ell}$, $1 \leq i,j \leq n$, $1 \leq \ell \leq \vert C({\sf HT}({\sf HT}({\bf g}_i)))\vert$ form a right generating set for all solutions of system 6.

Proof : 1.1  
Let ${\bf p} = (p_1, \ldots, p_n)$ be an arbitrary (non-trivial) solution of 6. We proceed by showing for all $1 \leq s \leq k$ as follows: Let $t_p = \max \{ {\sf HT}({\sf HT}({\bf g}_i)){\sf HT}(p_i) \mid {\sf nz}({\bf g}_i)=s \}$ be the maximal term when concatenating the head terms of the multiples in the sum $\sum_{i=1}^n {\bf g}_i \ast p_i = 0$ and $K_p$ the number of multiples ${\bf g}_i \ast p_i$ with ${\sf HT}({\sf HT}({\bf g}_i)){\sf HT}(p_i) \equiv t_p$ and ${\sf nz}({\bf g}_i)=s$. A solution ${\bf q}$ is called smaller than ${\bf p}$ if either $t_q < t_p$ or $t_q = t_p$ and $K_q < K_p$. We will prove our claim by induction on $t_p$ and $K_p$⁴. Since we assume ${\bf p}$ to be a non-trivial solution, we know $K_p > 1$. Then following the lines of the proof of Lemma 2 we can distinguish two cases:

1. If there is $1 \leq i \leq n$ such that $t_p \equiv {\sf HT}({\sf HT}({\bf g}_i)){\sf HT}(p_i)\not\equiv {\sf HT}({\sf HT}({\bf g}_i) \ast p_i)$, then ${\sf HT}({\sf HT}({\bf g}_i)) \equiv u_1u_2$, ${\sf HT}(p_i) \equiv w_{\ell}v$, $u_2 \neq 1 \neq w_{\ell}$ and $u_2w_{\ell} \equiv l$ for some $l \longrightarrow r \in T$, $w_{\ell} \in C({\sf HT}({\sf HT}({\bf g}_i)))$. Then ${\bf q} = {\bf p} + {\sf HC}(p_i) \cdot {\bf b}_{i,\ell} \ast v$ with
   

   $$q_i = p_i + {\sf HC}(p_i) \cdot (h_i - w_{\ell}) \ast v$$

   $$q_l = p_l + {\sf HC}(p_i) \cdot h_l \ast v$$

   
   
   $l \neq i$, is again a solution of 6. It remains to show that it is a smaller one. To see this we have to examine the multiples $g_{l,s} \ast q_l$ for all $1 \leq l \leq n$ where ${\sf nz}({\bf g}_l)=s$ and $g_{l,s} = {\sf HT}({\bf g}_l)$:
   1. For $l = i$ we get $g_{i,s} \ast q_i = g_{i,s} \ast (p_i + {\sf HC}(p_i) \cdot (h_i - w_{\ell}) \as... ...cdot g_{i,s} \ast h_i \ast v - {\sf HC}(p_i) \cdot g_{i,s} \ast w_{\ell} \ast v$ and as ${\sf HT}(g_{i,s}){\sf HT}(p_i) \equiv {\sf HT}(g_{i,s)}w_{\ell}v$ and the resulting monomials add up to zero we get ${\sf HT}(g_{i,s}){\sf HT}(q_i) < t_p$⁵.
   2. For $l \neq i$ we get $g_{l,s} \ast q_l = g_{l,s} \ast (p_l + {\sf HC}(p_i) \cdot h_l \ast v) = g_{l,s} \ast p_l + {\sf HC}(p_i) \cdot g_{l,s} \ast h_l \ast v$ and either ${\sf HT}(g_{l,s}){\sf HT}(q_l) \equiv t_p$ if ${\sf HT}(g_{l,s}){\sf HT}(p_l) \equiv t_p$ or else ${\sf HT}(g_{l,s}){\sf HT}(q_l) < t_p$
   Hence either $t_q < t_p$ or $K_p$ is decreased.
2. Let us now assume there are $1 \leq i,j \leq n$ such that ${\sf nz}({\bf g}_i)= {\sf nz}({\bf g}_j = s$ and ${\sf HT}({\sf HT}({\bf g}_i)) = t_{i,s}$, ${\sf HT}({\sf HT}({\bf g}_j)) = t_{j,s}$ with ${\sf HT}(t_{i,s} \ast p_i) \equiv t_{i,s}{\sf HT}(p_i) \equiv t_p \equiv t_{j,s}{\sf HT}(p_j) \equiv {\sf HT}(t_{j,s} \ast p_j)$. Without loss of generality we can assume that $t_{j,s} \equiv t_{i,s}u$ for some $1 \neq u \in {\cal M}$. Then by Lemma 8 we know that ${\sf HC}(g_{i,s}) = {\sf HC}(g_{j,s}) \cdot b$ for some $b \in \mathbb {Z}$. For the corresponding s-polynomial ${\bf g}_i \ast u - {\bf g}_j \cdot b$ we have a vector ${\bf a}_{ij}$ and we can define ${\bf q} = {\bf p} + {\sf HC}(p_i) \cdot {\bf a}_{i,j} \ast v$ where $v = {\sf HT}(p_j)$ with
   

   $$q_i = p_i + {\sf HC}(p_i) \cdot (h_i - u) \ast v$$

   $$q_j = p_j + {\sf HC}(p_i) \cdot (h_j + b) \ast v$$

   $$q_l = p_l + {\sf HC}(p_i) \cdot h_l \ast v$$

   
   
   $l \neq i,j$. It remains to show that this solution indeed is smaller. To do this we examine the multiples $g_{l,s} \ast q_l$ for all $1 \leq l \leq n$ where ${\sf nz}({\bf g}_l)=s$ and $g_{l,s} = {\sf HT}({\bf g}_l)$.
   1. For $l \neq i,j$ we get $g_{l,s} \ast q_l = g_{l,s} \ast p_l + {\sf HC}(p_i) \cdot g_{l,s} \ast h_l \ast v$ and by Lemma 8 ${\sf HT}(g_{l,s} \ast h_l) < {\sf HT}(g_{i,s})u$. Hence ${\sf HT}({\sf HC}(p_i) \cdot g_{l,s} \ast h_l \ast v) < {\sf HT}(g_{i,s}){\sf HT}(p_i) \equiv t_p$ implying either ${\sf HT}(g_{l,s}){\sf HT}(q_l) \equiv t_p$ if ${\sf HT}(g_{l,s}){\sf HT}(p_l) \equiv t_p$ or else ${\sf HT}(g_{l,s}){\sf HT}(q_l) < t_p$.
   2. For $l = i$ we get $g_{i,s} \ast q_i = g_{i,s} \ast p_i + {\sf HC}(p_i) \cdot g_{i,s} \ast h_i \ast v - {\sf HC}(p_i) \cdot g_{i,s} \ast u \ast v$. Since ${\sf HM}(g_{i,s} \ast p_i) = {\sf HM}({\sf HC}(p_i) \cdot g_{i,s} \ast u \ast v)$ we find ${\sf HT}(g_{i,s}){\sf HT}(q_i) < t_p$.
   3. For $l = j$ we get $g_{j,s} \ast q_j = g_{j,s} \ast p_j + {\sf HC}(p_i) \cdot g_{j,s} \ast h_j \ast v + {\sf HC}(p_i) \cdot g_{j,s} \ast b \ast v$. Hence either ${\sf HT}(g_{j,s} \ast q_j) = t_p$ if ${\sf HM}(g_{j,s} \ast p_j) \neq - {\sf HM}({\sf HC}(p_i) \cdot b \cdot g_{j,s} \ast v)$ or ${\sf HT}(g_{j,s} \ast q_j) < t_p$ else.
   Hence we find that either $t_q < t_p$ or in case $t_q = t_p$, $K_q < K_p$.