2. The Special Case of One Equation

Let $f_0, \ldots, f_k \in \mathbb {Z}[{\cal M}]$ and $f_1 \ast X_1 + \ldots + f_m \ast X_m = f_0$ be the equation we want to solve. In order to describe the generating set of solutions we have to find one solution of the inhomogeneous equation

$$f_1 \ast X_1 + \ldots + f_m \ast X_m = f_0.$$ (1)

and if possible a finite set of generators for the solutions of the homogeneous equation

$$f_1 \ast X_1 + \ldots + f_m \ast X_m = 0.$$ (2)

The set of solutions of equation 2 forms a right $\mathbb {Z}[{\cal M}]$-module $\mathbb {Z}[{\cal M}]^m$ which is called the right module of syzygies of $f_1, \ldots, f_k$ according to the term used for ordinary Gröbner bases in the literature (see e.g. [2]). To find a generating set for this right module we proceed as suggested in [1]:

1. Let $G = \{ g_1, \ldots, g_n \}$ be a finite reduced prefix Gröbner basis of the right ideal generated by $\{ f_1, \ldots, f_m \}$ in $\mathbb {Z}[{\cal M}]$, and ${\bf f} = (f_1, \ldots, f_m)$, ${\bf g} = (g_1, \ldots, g_n)$ corresponding vectors. 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 1 is solvable if and only if $f_0 \in {\sf ideal}_{r}^{}(\{ f_1, \ldots, f_m \})$. This is equivalent to $f_0 \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$ and the reduction sequence gives rise to a representation $f_0 = \sum_{i=1}^n g_i \ast h_i = {\bf g} \cdot {\bf h}$ where ${\bf h} = (h_1, \ldots, h_n)$. Then, as ${\bf f} \cdot P = {\bf g}$, we get ${\bf g} \cdot {\bf h} = ({\bf f} \cdot P) \cdot {\bf h}$ and $P \cdot {\bf h}$ is such a solution of equation 1.
3. Let $\{ {\bf z}_1, \ldots, {\bf z}_r \}$ be a generating set for the solutions of the homogeneous equation
   

   $$g_1 \ast X_1 + \ldots + g_n \ast X_n = 0.$$ (3)

   
   
   and let $I_m$ be the $m \times m$ identity matrix. Further let ${\bf w}_1, \ldots, {\bf w}_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 equation 2 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 2:
   Let ${\bf q} = (q_1, \ldots, q_m)$ be an arbitrary solution of equation 2, i.e.  ${\bf f} \cdot {\bf q} = 0$. Then $Q \cdot {\bf q}$ is a solution of equation 3 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 \ast q_1 + \ldots + {\bf w}_m \ast 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 equation 3. Let $G = \{ g_1, \ldots, g_n \}$ be a finite reduced prefix Gröbner basis of the right ideal generated by $\{ f_1, \ldots, f_m \}$ and let ${\sf HT}(g_i) = t_i$, ${\sf HC}(g_i) > 0$ for $1 \leq i \leq n$. In [1] the following situations define a set of generating zeros:

For every $g_i,g_j \in G$ such that ${\sf HT}(g_i)$ is a prefix (as a word) of ${\sf HT}(g_j)$, i.e.  ${\sf HT}(g_j) \equiv {\sf HT}(g_i)u$ for some $1 \neq u \in {\cal M}$, by Lemma 8 (see Section 5) we know ${\sf HC}(g_i) = {\sf HC}(g_j) \cdot b$ for some $b \in \mathbb {N}\backslash \{ 0,1 \}$. We determine vectors ${\bf a}_{ij}$ as follows:

$${\sf spol}_{p}(g_i,g_j) = b \cdot g_j - g_i \ast u = \sum_{l=1}^n g_l \ast h_l,$$

where the polynomials $h_l \in \mathbb {Z}[{\cal M}]$ are due to the reduction sequence ${\sf spol}_{p}(g_i,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 3 as $\sum_{l=1}^n g_l \ast h_l -b \cdot g_j + g_i \ast u = 0$.

If no such polynomials exist in $G$, Baader concluded that the homogeneous equation 3 in the free monoid ring had no solution. This is no longer true for arbitrary monoid rings.

Example 1   Let $\mathbb {Z}[{\cal M}]$ be a monoid ring where ${\cal M}$ is presented by the string rewriting system $\Sigma = \{a,b\}$, $T = \{ ab \longrightarrow 1 \}$. Then for the homogeneous equation

$$(a+1)\ast X_1 + (b+1) \ast X_2 = 0$$

we find that the set $\{a+1, b+1\}$ is a reduced prefix Gröbner basis of the right ideal it generates. Moreover neither of the head terms of the polynomials in this basis is prefix of the other. Still the equation can be solved: $(b, -1)$ is a solution since $(a+1) \ast b - (b+1) = b+1 - (b+1) = 0$.

This phenomenon is due to the fact that in most monoid rings s-polynomials are not sufficient for a Gröbner basis test. In [6] such a test for monoid rings as described here is presented. Besides testing s-polynomials the following test set has to be considered²:

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 $g_i$ and $1 \leq \ell \leq \vert C({\sf HT}(g_i))\vert$ as follows: Let $C({\sf HT}(g_i)) = \{ w_1, \ldots, w_s \}$. For every $g_i \ast w_{\ell}$ we know $g_i \ast w_\ell= \sum_{l=1}^n 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 equation 3 as $\sum_{l=1}^n g_l \ast h_l - g_i \ast w_\ell = 0$.

Lemma 2   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}(g_i))\vert$ form a right generating set for all solutions of equation 3.

Proof : 1.1  
Let ${\bf p} = (p_1, \ldots, p_n)$ be an arbitrary (non-trivial) solution of 3. Let $t_p = \max \{ {\sf HT}(g_1){\sf HT}(p_1), \ldots, {\sf HT}(g_n){\sf HT}(p_n) \}$ be the maximal term when concatenating the head terms of the multiples in the sum $\sum_{i=1}^n g_i \ast p_i = 0$ and $K_p$ the number of multiples $g_i \ast p_i$ with ${\sf HT}(g_i){\sf HT}(p_i) \equiv t_p$. 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 we can distinguish two cases:

1. If there is $1 \leq i \leq n$ such that $t_p \equiv {\sf HT}(g_i){\sf HT}(p_i)\not\equiv {\sf HT}(g_i \ast p_i)$, then ${\sf HT}(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}(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 3. It remains to show that it is a smaller one. To see this we have to examine the multiples $g_l \ast q_l$ for all $1 \leq l \leq n$. Remember that since $t_p \equiv {\sf HT}(g_i){\sf HT}(p_i) \equiv {\sf HT}(g_i)w_lv > {\sf HT}(g_i \ast w_i)v$ we get ${\sf HT}(g_l){\sf HT}(h_l)v\leq {\sf HT}(g_i \ast w_l)v < t_p$ as the $h_l$ arise from the reduction sequence $g_i \ast w_l \mbox{$\,\stackrel{*}{\longrightarrow }\!\!\mbox{}^{{\rm p}}_{G}\,$} 0$.
   1. For $l = i$ we get $g_i \ast q_i = g_i \ast (p_i + {\sf HC}(p_i) \cdot (h_i - w_{\ell}) \ast v) = ... ...}(p_i) \cdot g_i \ast h_i \ast v - {\sf HC}(p_i) \cdot g_i \ast w_{\ell} \ast v$ and as ${\sf HT}(g_i){\sf HT}(p_i) \equiv {\sf HT}(g_i)w_{\ell}v$ and the resulting monomials add up to zero we get ${\sf HT}(g_i){\sf HT}(q_i) < t_p$.
   2. For $l \neq i$ we get $g_l \ast q_l = g_l \ast (p_l + {\sf HC}(p_i) \cdot h_l \ast v) = g_l \ast p_l + {\sf HC}(p_i) \cdot g_l \ast h_l \ast v$ and either ${\sf HT}(g_l){\sf HT}(q_l) \equiv t_p$ if ${\sf HT}(g_l){\sf HT}(p_l) \equiv t_p$ or else ${\sf HT}(g_l){\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 HT}(g_i \ast p_i) \equiv {\sf HT}(g_i){\sf HT}(p_i) \equiv t_p \equiv {\sf HT}(g_j){\sf HT}(p_j) \equiv {\sf HT}(g_j \ast p_j)$. Without loss of generality we can assume that ${\sf HT}(g_j) \equiv {\sf HT}(g_i)u$ for some $u \in {\cal M}$. Then by Lemma 8 we know that ${\sf HC}(g_i) = {\sf HC}(g_j) \cdot b$ for some $b \in \mathbb {Z}$. For the corresponding s-polynomial $g_i \ast u - 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 \ast q_l$ for all $1 \leq l \leq n$.
   1. For $l \neq i,j$ we get $g_l \ast q_l = g_l \ast p_l + {\sf HC}(p_i) \cdot g_l \ast h_l \ast v$ and by Lemma 8 ${\sf HT}(g_l \ast h_l) < {\sf HT}(g_i)u$. Hence ${\sf HT}({\sf HC}(p_i) \cdot g_l \ast h_l \ast v) < {\sf HT}(g_i){\sf HT}(p_i) \equiv t_p$ implying either ${\sf HT}(g_l){\sf HT}(q_l) \equiv t_p$ if ${\sf HT}(g_l){\sf HT}(p_l) \equiv t_p$ or else ${\sf HT}(g_l){\sf HT}(q_l) < t_p$.
   2. For $l = i$ we get $g_i \ast q_i = g_i \ast p_i + {\sf HC}(p_i) \cdot g_i \ast h_i \ast v - {\sf HC}(p_i) \cdot g_i \ast u \ast v$. Since ${\sf HM}(g_i \ast p_i) = {\sf HM}({\sf HC}(p_i) \cdot g_i \ast u \ast v)$ we find ${\sf HT}(g_i){\sf HT}(q_i) < t_p$.
   3. For $l = j$ we get $g_j \ast q_j = g_j \ast p_j + {\sf HC}(p_i) \cdot g_j \ast h_j \ast v + {\sf HC}(p_i) \cdot g_j \ast b \ast v$. Hence either ${\sf HT}(g_j \ast q_j) = t_p$ if ${\sf HM}(g_j \ast p_j) \neq - {\sf HM}({\sf HC}(p_i) \cdot b \cdot g_j \ast v)$ or ${\sf HT}(g_j \ast q_j) < t_p$.
   Hence we find that either $t_q < t_p$ or in case $t_q = t_p$, $K_q < K_p$. Therefore, in all cases the solution ${\bf q}$ derived from ${\bf p}$ is smaller and we can show our claim by induction.