2. The Special Case of One Equation

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

The set of solutions of equation 2 forms a right -module which is called the right module of syzygies of 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]:

- Let
be a finite reduced prefix Gröbner basis of the right ideal
generated by
in
, and
,
corresponding vectors.
There are two linear mappings given by matrices
^{1}, such that and . - Equation 1 is solvable if and only if . This is equivalent to and the reduction sequence gives rise to a representation where . Then, as , we get and is such a solution of equation 1.
- Let
be a generating set for the solutions of the
homogeneous equation

and let be the identity matrix. Further let be the columns of the matrix . Since these are solutions of the homogeneous equation 2 as well. We can even show that the set generates*all*solutions of 2:

Let be an arbitrary solution of equation 2, i.e. . Then is a solution of equation 3 as . Hence there are such that . Further we find

and hence is a right linear combination of elements in .

For every such that is a prefix (as a word) of ,
i.e.
for some
, by Lemma 8 (see Section 5)
we know
for some
.
We determine vectors as follows:

where the polynomials are due to the reduction sequence .

Then , where

, is a solution of 3 as .

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

we find that the set 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: is a solution since .

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^{2}:

For
let
for some
.
Additionally, we define vectors
for and
as follows:
Let
.
For every
we know
as is a prefix Gröbner basis.
Then
, where

, is a solution of equation 3 as .

Let be an arbitrary (non-trivial) solution of 3. Let be the maximal term when concatenating the head terms of the multiples in the sum and the number of multiples with . A solution is called smaller than if either or and . We will prove our claim by induction on and

- If there is
such that
,
then
,
,
and
for some
,
.
Then
with

, 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 for all . Remember that since we get as the arise from the reduction sequence .- For we get and as and the resulting monomials add up to zero we get .
- For we get and either if or else .

- Let us now assume there are
such that
.
Without loss of generality we can assume that
for some
.
Then by Lemma 8 we know that
for some
.
For the corresponding s-polynomial
we have a vector
and we can define
where
with

. It remains to show that this solution indeed is smaller. To do this we examine the multiples for all .- For we get and by Lemma 8 . Hence implying either if or else .
- For we get . Since we find .
- For we get . Hence either if or .