${\mathbb{N}}$ for reduction, we will mainly require the part of the ordering
on ${\mathbb{N}}$ which then coincides with the natural ordering on this set.
Then we will drop the suffix363636In the literature other orderings on the
integers are used by Buchberger and Stifter [Sti87] and Kapur and Kandri-Rody
[KRK88]. They then have to consider s- and t-polynomials as critical
situations..

This ordering $<_{Z}$ can be used to induce an ordering on ${\cal
F}_{{\mathbb{Z}}}$ as follows: for two elements $f,g$ in ${\cal F}$ we define
$f\succ g$ iff ${\sf HT}(f)\succ{\sf HT}(g)$ or ($({\sf HT}(f)={\sf HT}(g)$
and ${\sf HC}(f)>_{Z}{\sf HC}(g)$) or ($({\sf HM}(f)={\sf HM}(g)$ and ${\sf
RED}(f)\succ{\sf RED}(g)$).

The reduction relation presented in Definition 4.2.53 now can be adapted to
this special case: Let $\Longrightarrow$ be our reduction relation on
${\mathbb{Z}}$ where $\alpha\Longrightarrow_{\gamma}\beta$, if $\gamma>0$ and
for some $\delta\in{\mathbb{Z}}$ we have $\alpha=\gamma\cdot\delta+\beta$ with
$0\leq\beta<\gamma$, i.e. $\beta$ is the remainder of $\alpha$ modulo
$\gamma$.

###### Definition 4.2.62

Let $p$, $f$ be two non-zero polynomials in ${\cal F}_{{\mathbb{Z}}}$. We say
$f$ right reduces $p$ to $q$ at a monomial $\alpha\cdot t$ in one step, i.e.
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}q$, if there exists $s\in{\sf T}({\cal F}_{{\mathbb{Z}}})$ such
that

  1. 1.

$t\in{\sf supp}(p)$ and $p(t)=\alpha$,

  2. 2.

${\sf HT}({\sf HT}(f)\star s)={\sf HT}(f\star s)=t\geq{\sf HT}(f)$,

  3. 3.

$\alpha\geq_{{\mathbb{Z}}}{\sf HC}(f\star m)>0$ and
$\alpha\Longrightarrow_{{\sf HC}(f\star s)}\delta$ where $\alpha={\sf
HC}(f\star s)\cdot\beta+\delta$ with $\beta,\delta\in{\mathbb{Z}}$,
$0\leq\delta<{\sf HC}(f\star s)$, and

  4. 4.

$q=p-f\star m$ where $m=\beta\cdot s$.

We write
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}$ if there is a polynomial $q$ as defined above and $p$ is then
called right reducible by $f$. Further, we can define
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}\,$},\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}\,$}$ and $\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}\,$ as usual. Right reduction by
a set $F\subseteq{\cal F}\backslash\\{o\\}$ is denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}q$ and abbreviates
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}q$ for some $f\in F$. $\diamond$

As before, for this reduction relation we can still have $t\in{\sf supp}(q)$.
Hence other arguments than those used in the proof of Lemma 4.2.44 have to be
used to show termination. The important part now is that if we still have
$t\in{\sf supp}(q)$ then its coefficient will be smaller according to our
ordering $<_{{\mathbb{Z}}}$ chosen for ${\mathbb{Z}}$ and since this ordering
is well-founded we are done. Notice that in contrary to Lemma 4.2.55 we do not
have to restrict ourselves to finite sets of polynomials in order to ensure
termination.

The additional information we have on the coefficients before and after the
reduction step now enables us to prove an analogon of the Translation Lemma
for function rings over the integers. The first and second part of the lemma
are only needed to prove the essential third part.

###### Lemma 4.2.63

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{Z}}}$ and $p,q,h$
polynomials in ${\cal F}_{{\mathbb{Z}}}$.

  1. 1.

Let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}h$ such that the reduction step takes place at the monomial
$\alpha\cdot t$ and we additionally have $t\not\in{\sf supp}(h)$. Then there
exist $p^{\prime},q^{\prime}\in{\cal F}_{{\mathbb{Z}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}p^{\prime}$ and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}q^{\prime}$ and $h=p^{\prime}-q^{\prime}$.

  2. 2.

Let $o$ be the unique normal form of $p$ with respect to $F$ and $t={\sf
HT}(p)$. Then there exists a polynomial $f\in F$ such that
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}p^{\prime}$ and $t\not\in{\sf supp}(p^{\prime})$.

  3. 3.

Let $o$ be the unique normal form of $p-q$ with respect to $F$. Then there
exists $g\in{\cal F}_{{\mathbb{Z}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g$ and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g$.

Proof :

  1. 1.

Let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}h$ at the monomial $\alpha\cdot t$, i.e., $h=p-q-f\star m$ for some
$m=\beta\cdot s\in{\sf M}({\cal F}_{{\mathbb{Z}}})$ such that ${\sf HT}({\sf
HT}(f)\star s)={\sf HT}(f\star s)=t\geq{\sf HT}(f)$ and ${\sf HC}(f\star
s)>0$. Remember that $\alpha$ is the coefficient of $t$ in $p-q$. Then as
$t\not\in{\sf supp}(h)$ we know $\alpha={\sf HC}(f\star m)$. Let $\alpha_{1}$
respectively $\alpha_{2}$ be the coefficients of $t$ in $p$ respectively $q$
and $\alpha_{1}={\sf HC}(f\star m)\cdot\beta_{1}+\gamma_{1}$ respectively
$\alpha_{2}={\sf HC}(f\star m)\cdot\beta_{2}+\gamma_{2}$ for some
$\beta_{1},\beta_{2},\gamma_{1},\gamma_{2}\in{\mathbb{Z}}$ where
$0\leq\gamma_{1},\gamma_{2}<{\sf HC}(f\star s)\leq{\sf HC}(f\star m)$. Then
$\alpha={\sf HC}(f\star m)=\alpha_{1}-\alpha_{2}={\sf HC}(f\star
m)\cdot(\beta_{1}-\beta_{2})+(\gamma_{1}-\gamma_{2})$, and as
$\gamma_{1}-\gamma_{2}$ is no multiple of ${\sf HC}(f\star m)$ we have
$\gamma_{1}-\gamma_{2}=0$ and hence $\beta_{1}-\beta_{2}=1$. We have to
distinguish two cases:

    1. (a)

$\beta_{1}\neq 0$ and $\beta_{2}\neq 0$: Then
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}p-f\star m\cdot\beta_{1}=p^{\prime}$,
$q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}q-f\star m\cdot\beta_{2}=q^{\prime}$ and
$p^{\prime}-q^{\prime}=p-f\star m\cdot\beta_{1}-q+f\star
m\cdot\beta_{2}=p-q-f\star m=h$.

    2. (b)

$\beta_{1}=0$ and $\beta_{2}=-1$ (the case $\beta_{2}=0$ and $\beta_{1}=1$
being symmetric): Then $p^{\prime}=p$,
$q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}q-f\star m\cdot\beta_{2}=q+f\star m\cdot\beta=q^{\prime}$ and
$p^{\prime}-q^{\prime}=p-q-f\star m=h$.

  2. 2.

Since
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$, ${\sf HM}(p)=\alpha\cdot t$ must be $F$-reducible. Let
$f_{1},\ldots,f_{k}\in F$ be all polynomials in $F$ such that $\alpha\cdot t$
is reducible by them. Let $m_{1},\ldots m_{k}$ be the respective monomials
involved in possible reduction steps. Moreover, let $\gamma=\min_{1\leq i\leq
k}\\{{\sf HC}(f_{i}\star m_{i})\\}$ and without loss of generality ${\sf
HM}(f\star m)=\gamma\cdot t$ for some $f\in F$, ${\sf HT}({\sf HT}(f)\star
m)={\sf HT}(f\star m)\geq{\sf HT}(f)$. We claim that for
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f_{1}}\,$}p-f\star m=p^{\prime}$ we have $t\not\in{\sf
supp}(p^{\prime})$. Suppose ${\sf HT}(p^{\prime})=t$. Then by our definition
of reduction we must have $0<{\sf HC}(p^{\prime})<{\sf HC}(f\star m)$. But
then $p^{\prime}$ would no longer be $F$-reducible contradicting our
assumption that $o$ is the unique normal form of $p$.

  3. 3.

Since $o$ is the unique normal form of $p-q$ by 2. there exists a reduction
sequence
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f_{i_{1}}}\,$}h_{1}\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f_{i_{2}}}\,$}\ldots\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f_{i_{k}}}\,$}o$ such that for the head terms we get ${\sf
HT}(p-q)\succ{\sf HT}(h_{1})\succ\ldots$. We show our claim by induction on
$k$, where $p-q\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$}o$ is such a reduction
sequence. In the base case $k=0$ there is nothing to show as then $p=q$.
Hence, let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}h\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$}o$. Then by 1. there are
polynomials $p^{\prime},q^{\prime}\in{\cal F}_{{\mathbb{Z}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}p^{\prime}$ and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}q^{\prime}$ and $h=p^{\prime}-q^{\prime}$. Now the induction
hypothesis for $p^{\prime}-q^{\prime}\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$}o$ yields the existence
of a polynomial $g\in{\cal F}_{{\mathbb{Z}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g$ and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g$.

q.e.d.

Hence weak Gröbner bases are in fact Gröbner bases and can be characterized as
follows:

###### Definition 4.2.64

A set $F\subseteq{\cal F}_{{\mathbb{Z}}}\backslash\\{o\\}$ is called a (weak)
right Gröbner basis of ${\sf ideal}_{r}(F)$ if for all $g\in{\sf
ideal}_{r}(F)$ we have
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$. $\diamond$

###### Corollary 4.2.65

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{Z}}}$ and $g$ a non-
zero polynomial in ${\sf ideal}_{r}(F)$ such that
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$. Then $g$ has a representation of the form

$g=\sum_{i=1}^{n}f_{i}\star m_{i},f_{i}\in F,m_{i}\in{\sf M}({\cal
F}_{{\mathbb{Z}}}),n\in{\mathbb{N}}$

such that ${\sf HT}(g)={\sf HT}({\sf HT}(f_{i})\star m_{i})={\sf
HT}(f_{i}\star m_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq k$, and ${\sf
HT}(g)\succ{\sf HT}(f_{i}\star m_{i})={\sf HT}({\sf HT}(f_{i})\star m_{i})$
for all $k+1\leq i\leq n$.

Proof :
We show our claim by induction on $n$ where $g\mbox{$\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$}o$. If $n=0$ we are done.
Else let $g\mbox{$\,\stackrel{{\scriptstyle
1}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g_{1}\mbox{$\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$}o$. In case the reduction
step takes place at the head monomial, there exists a polynomial $f\in F$ and
a monomial $m=\beta\cdot s\in{\sf M}({\cal F})$ such that ${\sf HT}({\sf
HT}(f)\star s)={\sf HT}(f\star s)={\sf HT}(g)\geq{\sf HT}(f)$ and ${\sf
HC}(g)\Longrightarrow_{{\sf HC}(f\star s)}\delta$ with ${\sf HC}(g)={\sf
HC}(f\star s)\cdot\beta+\delta$ for some $\beta,\delta\in{\mathbb{Z}}$,
$0\leq\delta<{\sf HC}(f\star s)$. Moreover the induction hypothesis then is
applied to $g_{1}=g-f\star m$. If the reduction step takes place at a monomial
with term smaller ${\sf HT}(g)$ for the respective monomial multiple $f\star
m$ we immediately get ${\sf HT}(g)\succ{\sf HT}(f\star m)$ and we can apply
our induction hypothesis to the resulting polynomial $g_{1}$. In both cases we
can arrange the monomial multiples $f\star m$ arising from the reduction steps
in such a way that gives us the desired representation.
q.e.d.

We can even state that ${\sf
HC}(g)\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{\\{{\sf
HC}(f_{i}\star m_{i})\mid 1\leq i\leq k\\}}\,$}0$. Now right Gröbner bases can
be characterized using the concept of s-polynomials combined with the
technique of saturation which is necessary in order to describe the whole
right ideal congruence by the reduction relation.

###### Definition 4.2.66

Let $p_{1},p_{2}$ be two polynomials in ${\cal F}_{{\mathbb{Z}}}$. If there
are respective terms $t,u_{1},u_{2}\in{\cal T}$ such that ${\sf HT}({\sf
HT}(p_{i})\star u_{i})={\sf HT}(p_{i}\star u_{i})=t\geq{\sf HT}(p_{i})$ let
$HC(p_{i}\star u_{i})=\gamma_{i}$.
Assuming $\gamma_{1}\geq\gamma_{2}>0$373737Notice that $\gamma_{i}>0$ can
always be achieved by studying the situation for $-p_{i}$ in case we have
$HC(p_{i}\star u_{i})<0$., there are $\beta,\delta\in{\mathbb{Z}}$ such that
$\gamma_{1}=\gamma_{2}\cdot\beta+\delta$ and $0\leq\delta<\gamma_{2}$ and we
get the following s-polynomial

${\sf spol}_{r}(p_{1},p_{2},t,u_{1},u_{2})=p_{2}\star u_{2}\cdot\beta-
p_{1}\star u_{1}.$

The set ${\sf SPOL}(\\{p_{1},p_{2}\\})$ then is the set of all such
s-polynomials corresponding to $p_{1}$ and $p_{2}$. $\diamond$

These sets can be infinite383838This is due to the fact that in general we
cannot always find finite locations for $t$. One well-studied field are monoid
rings..

###### Theorem 4.2.67

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{Z}}}\backslash\\{o\\}$.
Then $F$ is a right Gröbner basis of ${\sf ideal}_{r}(F)$ if and only if

  1. 1.

for all $f$ in $F$ and for all $m$ in ${\sf M}({\cal F}_{{\mathbb{Z}}})$ we
have $f\star
m\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$, and

  2. 2.

all s-polynomials corresponding to $F$ as specified in Definition 4.2.66
reduce to $o$ using $F$.

Proof :
In case $F$ is a right Gröbner basis, since the multiples $f\star m$ and the
respective s-polynomials are all elements of ${\sf ideal}_{r}(F)$ they must
reduce to zero using $F$.
The converse will be proven by showing that every element in ${\sf
ideal}_{r}(F)$ is reducible by $F$. Then as $g\in{\sf ideal}_{r}(F)$ and
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}g^{\prime}$ implies $g^{\prime}\in{\sf ideal}_{r}(F)$ we have
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$. Notice that this is sufficient as the reduction relation
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$
is Noetherian.
Let $g\in{\sf ideal}_{r}(F)$ have a representation in terms of $F$ of the
following form: $g=\sum_{j=1}^{m}f_{j}\star w_{j}\cdot\alpha_{j}$ such that
$f_{j}\in F$, $w_{j}\in{\cal T}$ and $\alpha_{j}\in{\mathbb{Z}}$. Depending on
this representation of $g$ and the well-founded total ordering $\succeq$ on
${\cal T}$ we define $t=\max_{\succeq}\\{{\sf HT}(f_{j}\star w_{j})\mid 1\leq
j\leq m\\}$, $K$ as the number of polynomials $f_{j}\star w_{j}$ with head
term $t$, and $M=\\{\\{{\sf HC}(f_{i}\star w_{i})\mid{\sf HT}(f_{j}\star
w_{j})=t\\}\\}$ a multiset in ${\mathbb{Z}}$. We show our claim by induction
on $(t,M)$, where $(t^{\prime},M^{\prime})<(t,M)$ if and only if
$t^{\prime}\prec t$ or $(t^{\prime}=t$ and $M^{\prime}\ll M)$393939We define
$M^{\prime}\ll M$ if $M$ can be transformed into $M^{\prime}$ by substituting
elements in $M$ with sets of smaller elements (with respect to our ordering on
the integers..
Since by our first assumption every multiple $f_{j}\star w_{j}$ in this sum
reduces to zero using $F$ and hence has a representation as specified in
Corollary 4.2.65, we can assume that ${\sf HT}({\sf HT}(f_{j})\star
w_{j})={\sf HT}(f_{j}\star w_{j})\geq{\sf HT}(f_{j})$ holds. Moreover, without
loss of generality we can assume that the polynomial multiples with head term
$t$ are just $f_{1}\star w_{1},\ldots,f_{K}\star w_{K}$ and additionally we
can assume ${\sf HC}(f_{j}\star w_{j})>0$404040This can easily be achieved by
adding $-f$ to $F$ for all $f\in F$ and using $(-f_{j})\star w_{j}$ in case
${\sf HC}(f_{j}\star w_{j})<0$..
Obviously, $t\succeq{\sf HT}(g)$ must hold. If $K=1$ this gives us $t={\sf
HT}(g)$ and even ${\sf HM}(g)={\sf HM}(f_{1}\star w_{1}\cdot\alpha_{1})$,
implying that $g$ is right reducible at ${\sf HM}(g)$ by $f_{1}$.
Hence let us assume $K>1$.
Without loss of generality we can assume that ${\sf HC}(f_{1}\star
w_{1})\geq{\sf HC}(f_{2}\star w_{2})>0$ and there are
$\alpha,\beta\in{\mathbb{Z}}$ such that ${\sf HC}(f_{2}\star
w_{2})\cdot\alpha+\beta={\sf HC}(f_{1}\star w_{1})$ and ${\sf HC}(f_{2}\star
w_{2})>\beta\geq 0$. Since $t={\sf HT}(f_{1}\star w_{1})={\sf HT}(f_{2}\star
w_{2})$ by Definition 4.2.66 we have an s-polynomial ${\sf
spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})=f_{2}\star w_{2}\cdot\alpha-f_{1}\star
w_{1}$. If ${\sf spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})\neq o$414141In case
${\sf spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})=o$ the proof is similar. We just
have to substitute $o$ in the equations below which immediately gives us a
smaller representation of $g$. then ${\sf
spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$ implies ${\sf
spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})=\sum_{i=1}^{k}\delta_{i}\cdot h_{i}\star
v_{i}$, $\delta_{i}\in{\mathbb{Z}}$, $h_{i}\in F$, $v_{i}\in{\cal T}$ where
this sum is a representation in the sense of Corollary 4.2.65 with terms
bounded by ${\sf HT}({\sf spol}_{r}(f_{1},f_{2},t,w_{1},w_{2}))\leq t$. This
gives us

$\displaystyle g$ $\displaystyle=$ $\displaystyle f_{1}\star
w_{1}\cdot\alpha_{1}+f_{2}\star w_{2}\cdot\alpha_{2}+\sum_{j=3}^{m}f_{j}\star
w_{j}\cdot\alpha_{j}$ $\displaystyle=$ $\displaystyle f_{1}\star
w_{1}\cdot\alpha_{1}+\underbrace{f_{2}\star w_{2}\cdot\alpha_{1}\cdot\alpha-
f_{2}\star w_{2}\cdot\alpha_{1}\cdot\alpha}_{=o}+f_{2}\star
w_{2}\cdot\alpha_{2}+\sum_{j=3}^{m}f_{j}\star w_{j}\cdot\alpha_{j}$
$\displaystyle=$ $\displaystyle f_{2}\star
w_{2}\cdot(\alpha_{1}\cdot\alpha+\alpha_{2})-\underbrace{(f_{2}\star
w_{2}\cdot\alpha-f_{1}\star w_{1}}_{={\sf
spol}_{r}(f_{1},f_{2},t,w_{1},w_{2})}\cdot\alpha_{1}+\sum_{j=3}^{m}f_{j}\star
w_{j}\cdot\alpha_{j}$ $\displaystyle=$ $\displaystyle f_{2}\star
w_{2}\cdot(\alpha_{1}\cdot\alpha+\alpha_{2})-(\sum_{i=1}^{k}\delta_{i}\cdot
h_{i}\star v_{i})\cdot\alpha_{1}+\sum_{j=3}^{m}f_{j}\star
w_{j}\cdot\alpha_{j}$

and depending on this new representation of $g$ we define
$t^{\prime}=\max_{\succeq}\\{{\sf HT}(f_{j}\star w_{j}),{\sf HT}(h_{j}\star
v_{j})\mid f_{j},h_{j}\mbox{ appearing in the new representation }\\}$, and
$M^{\prime}=\\{\\{{\sf HC}(f_{i}\star w_{i}),{\sf HC}(h_{j}\star
v_{j})\mid{\sf HT}(f_{j}\star w_{j})={\sf HT}(h_{j}\star
v_{j})=t^{\prime}\\}\\}$ and we either get $t^{\prime}\prec t$ and have a
smaller representation for $g$ or in case $t^{\prime}=t$ we have to
distinguish two cases

  1. 1.

$\alpha_{1}\cdot\alpha+\alpha_{2}=0$.
Then $M^{\prime}=M-\\{\\{{\sf HC}(f_{1}\star w_{1}),{\sf HC}(f_{2}\star
w_{2})\\}\\}\cup\\{\\{{\sf HC}(h_{j}\star v_{j})\mid{\sf HT}(h_{j}\star
v_{j})=t\\}\\}$. As those polynomials $h_{j}$ with ${\sf HT}(h_{j}\star
v_{j})=t$ are used to right reduce the monomial $\beta\cdot t={\sf HM}({\sf
spol}_{r}(f_{1},f_{2},t,w_{1},w_{2}))$ we know that for them we have $0<{\sf
HC}(h_{j}\star v_{j})\leq\beta<{\sf HC}(f_{2}\star w_{2})\leq{\sf
HC}(f_{1}\star w_{1})$. Hence $M^{\prime}\ll M$ and we have a smaller
representation for $g$.

  2. 2.

$\alpha_{1}\cdot\alpha+\alpha_{2}\neq 0$.
Then $M^{\prime}=(M-\\{\\{{\sf HC}(f_{1}\star w_{1})\\}\\})\cup\\{\\{{\sf
HC}(h_{j}\star v_{j})\mid{\sf HT}(h_{j}\star v_{j})=t\\}\\}$. Again
$M^{\prime}\ll M$ and we have a smaller representation for $g$.

Notice that the case $t^{\prime}=t$ and $M^{\prime}\ll M$ cannot occur
infinitely often but has to result in either $t^{\prime}<t$ or will lead to
$t^{\prime}=t$ and $K=1$ and hence to reducibility by
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}_{F}\,$.
q.e.d.

Now the question arises when the critical situations in this characterization
can be localized to subsets of the respective sets as in Theorem 4.2.41.
Reviewing the Proof of Theorem 4.2.41 we find that Lemma 4.2.26 is central as
it describes when multiples of polynomials which have a right reductive
standard representation in terms of some set $F$ again have such a
representation. As we have seen before, this will not hold for function rings
over reduction rings in general. As in Section 4.2.2, to give localizations of
Theorem 4.2.67 the concept of stable subsets is sufficient:

###### Definition 4.2.68

A set $C\subset S\subseteq{\cal F}_{{\mathbb{Z}}}$ is called a stable
localization of $S$ if for every $g\in S$ there exists $f\in C$ such that
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}o$. $\diamond$

Stable localizations for the sets of s-polynomials again arise from the
appropriate sets of least common multiples as presented on page 4.2.23. In
case ${\cal F}_{{\mathbb{Z}}}$ and
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm r}}\,$
allow such stable localizations, we can rephrase Theorem 4.2.67 as follows:

###### Theorem 4.2.69

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{Z}}}\backslash\\{o\\}$.
Then $F$ is a right Gröbner basis of ${\sf ideal}_{r}(F)$ if and only if

  1. 1.

for all $s$ in a stable localization of $\\{f\star m\mid f\in{\cal
F}_{{\mathbb{Z}}},m\in{\sf M}({\cal F}_{{\mathbb{Z}}})\\}$ we have
$s\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$, and

  2. 2.

for all $h$ in a stable localization of the s-polynomials corresponding to $F$
as specified in Definition 4.2.66 we have
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$.

When proving Theorem 4.2.69, we can substitute the critical situation using an
analogon of Lemma 4.2.26, which will be sufficient to make the representation
used in the proof smaller. It is a direct consequence of Lemma 4.2.61.

###### Corollary 4.2.70

Let $F\subseteq{\cal F}_{{\mathbb{Z}}}\backslash\\{o\\}$ and $f$, $p$ non-zero
polynomials in ${\cal F}_{{\mathbb{Z}}}$. If
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{f}\,$}o$ and
$f\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$, then $p$ has a representation of the form

$p=\sum_{i=1}^{n}f_{i}\star l_{i},f_{i}\in F,l_{i}\in{\sf M}({\cal
F}_{{\mathbb{Z}}}),n\in{\mathbb{N}}$

such that ${\sf HT}(p)={\sf HT}({\sf HT}(f_{i})\star l_{i})={\sf
HT}(f_{i}\star l_{i})\geq{\sf HT}(f_{i})$ for $1\leq i\leq k$ and ${\sf
HT}(p)\succ{\sf HT}(f_{i}\star l_{i})$ for all $k+1\leq i\leq n$ (compare
Definition 4.2.15).

Proof Theorem 4.2.69:
The proof is basically the same as for Theorem 4.2.67. Due to Corollary 4.2.70
we can substitute the multiples $f_{j}\star w_{j}$ by appropriate
representations. Hence, we only have to ensure that despite testing less
polynomials we are able to apply our induction hypothesis. Taking the
notations from the proof of Theorem 4.2.67, let us check the situation for
$K>1$.
Without loss of generality we can assume that ${\sf HC}(f_{1}\star
w_{1})\geq{\sf HC}(f_{2}\star w_{2})>0$ and there are
$\alpha,\beta\in{\mathbb{Z}}$ such that ${\sf HC}(f_{2}\star
w_{2})\cdot\alpha+\beta={\sf HC}(f_{1}\star w_{1})$ and ${\sf HC}(f_{2}\star
w_{2})>\beta\geq 0$. Since $t={\sf HT}(f_{1}\star w_{1})={\sf HT}(f_{2}\star
w_{2})$ by Definition 4.2.66 we have an s-polynomial $h\in{\sf
SPOL}(f_{1},f_{2})$ and $m\in{\sf M}({\cal F}_{{\mathbb{Z}}})$ such that
$h\star m=\alpha\cdot f_{2}\star w_{2}-f_{1}\star w_{1}$. If $h\neq o$424242In
case $h=o$ the proof is similar. We just have to substitute $o$ in the
equations below which immediately gives us a smaller representation of $g$.
then by Corollary 4.2.70 $f_{2}\star w_{2}\cdot\alpha-f_{1}\star
w_{1}\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{h}\,$}o$ and
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
r}}_{F}\,$}o$ imply $f_{2}\star w_{2}\cdot\alpha-f_{1}\star
w_{1}=\sum_{i=1}^{k}h_{i}\star v_{i}\cdot\delta_{i}$,
$\delta_{i}\in{\mathbb{Z}}$, $h_{i}\in F$, $v_{i}\in{\cal T}$ where this sum
is a representation in the sense of Corollary 4.2.65 with terms bounded by
${\sf HT}(h\star m)\leq t$. As in the proof of Theorem 4.2.67 we now can use
this bounded representation to get a smaller representation of $g$ and are
done.
q.e.d.

We close this subsection by outlining how different structures known to allow
finite Gröbner bases can be interpreted as function rings. Using the
respective interpretations the terminology can be adapted at once to the
respective structures and in general the resulting characterizations of
Gröbner bases coincide with the results known from literature.

##### Polynomial Rings

A commutative polynomial ring ${\mathbb{Z}}[x_{1},\ldots,x_{n}]$ is a function
ring according to the following interpretation:

  * •

${\cal T}$ is the set of terms $\\{x_{1}^{i_{1}}\ldots x_{n}^{i_{n}}\mid
i_{1},\ldots,i_{n}\in{\mathbb{N}}\\}$.

  * •

$\succ$ can be any admissible term ordering on ${\cal T}$. For the reductive
ordering $\geq$ we have $t\geq s$ if $s$ divides $t$ as as term.

  * •

Multiplication $\star$ is specified by the action on terms, i.e. $\star:{\cal
T}\times{\cal T}\longrightarrow{\cal T}$ where $x_{1}^{i_{1}}\ldots
x_{n}^{i_{n}}\star x_{1}^{j_{1}}\ldots x_{n}^{j_{n}}=x_{1}^{i_{1}+j_{1}}\ldots
x_{n}^{i_{n}+j_{n}}$.

We do not need the concept of weak saturation.

Since the integers are an instance of euclidean domains, similar reductions to
those given by Kandri-Rodi and Kapur in [KRK88] arise. A stable localization
of ${\cal C}_{s}(p,q)$ is already provided by the tuple corresponding to the
least common multiple of the terms ${\sf HT}(p)$ and ${\sf HT}(q)$. In
contrast to the s- and t-polynomials studied by Kandri-Rodi and Kapur, we
restrict ourselves to s-polynomials as described in Definition 4.2.66.

Since this structure is Abelian, one-sided and two-sided ideals coincide.
Buchberger’s Algorithm provides an effictive procedure to compute finite
Gröbner bases.

##### Non-commutative Polynomial Rings

A non-commutative polynomial ring ${\mathbb{Z}}[\\{x_{1},\ldots,x_{n}\\}^{*}]$
is a function ring according to the following interpretation:

  * •

${\cal T}$ is the set of words on $\\{x_{1},\ldots,x_{n}\\}$.

  * •

$\succ$ can be any admissible ordering on ${\cal T}$. For the reductive
ordering $\geq$ we can chose $t\geq s$ if $s$ is a subword of $t$.

  * •

Multiplication $\star$ is specified by the action on words which is just
concatenation.

We do not need the concept of weak saturation. A stable localization of ${\cal
C}_{s}(p,q)$ is already provided by the tuples corresponding to word overlaps
resulting from the equations $u_{1}{\sf HT}(p)v_{1}={\sf HT}(q)$, $u_{2}{\sf
HT}(q)v_{2}={\sf HT}(p)$, $u_{3}{\sf HT}(p)={\sf HT}(q)v_{3}$ respectively
$u_{4}{\sf HT}(q)={\sf HT}(p)v_{4}$ with the restriction that $|u_{3}|<|{\sf
HT}(q)|$ and $|u_{4}|<|{\sf HT}(p)|$, $u_{i},v_{i}\in{\cal T}$. The
coefficients arise as described in Definition 4.2.66.

This structure is not Abelian. For the case of one-sided ideals finite Gröbner
bases can be computed. The case of two-sided ideals only allows an enumerating
procedure. This is not surprising as the word problem for monoids can be
reduced to the problem of computing the respective Gröbner bases (see e.g.
[Mor87, MR98d]).

##### Monoid and Group Rings

A monoid or group ring ${\mathbb{Z}}[{\cal M}]$ is a function ring according
to the following interpretation:

  * •

${\cal T}$ is the monoid or group ${\cal M}$. In the cases studied by us as
well as in [Ros93, Lo96], it is assumed that the elements of the monoid or
group have a certain form. This presentation is essential in the approach. We
will assume that the given monoid or group is presented by a convergent semi-
Thue system.

  * •

$\succ$ will be the completion ordering induced from the presentation of
${\cal M}$ to ${\cal M}$ and hence to ${\cal T}$. The reductive ordering
$\geq$ depends on the choice of the presentation.

  * •

Multiplication $\star$ is specified by lifting the monoid or group operation.

The concept of weak saturation and the choice of stable localizations of
${\cal C}_{s}(p,q)$ again depend on the choice of the presentation. More on
this topic can be found in [Rei95].

###  4.3 Right ${\cal F}$-Modules

The concept of modules arises naturally as a generalization of the concept of
an ideal in a ring: Remember that an ideal of a ring is an additive subgroup
of the ring which is additionally closed under multiplication with ring
elements. Extending this idea to arbitrary additive groups then gives us the
concept of modules.

In this section we turn our attention to right modules, but left modules can
be defined similarly and all results carry over (with the respective
modifications of the terms “right” and “left”). Let ${\cal F}$ be a function
ring with unit ${\bf 1}$.

###### Example 4.3.1

Let us provide some examples for right ${\cal F}$-modules.

  1. 1.

Any right ideal in ${\cal F}$ is of course a right ${\cal F}$-module.

  2. 2.

The set ${\cal M}=\\{{\bf 0}\\}$ with right scalar multiplication ${\bf
0}\star f={\bf 0}$ is a right ${\cal F}$-module called the trivial right
${\cal F}$-module.

  3. 3.

Given a function ring ${\cal F}$ and a natural number $k$, let ${\cal
F}^{k}=\\{(f_{1},\ldots,f_{k})\mid f_{i}\in{\cal F}\\}$ be the set of all
vectors of length $k$ with coordinates in ${\cal F}$. Obviously ${\cal F}^{k}$
is an additive commutative group with respect to ordinary vector addition.
Moreover, ${\cal F}^{k}$ is a right ${\cal F}$-module with right scalar
multiplication $\star:{\cal F}^{k}\times{\cal F}\longrightarrow{\cal F}^{k}$
defined by $(f_{1},\ldots,f_{k})\star f=(f_{1}\star f,\ldots,f_{k}\star f)$.
$\diamond$

###### Definition 4.3.2

A subset of a right ${\cal F}$-module ${\cal M}$ which is again a right ${\cal
F}$-module is called a right submodule of ${\cal M}$. $\diamond$

For example any right ideal of ${\cal F}$ is a right submodule of the right
${\cal F}$-module ${\cal F}^{1}$. Provided a set of vectors $S\subset{\cal M}$
the set $\\{\sum_{i=1}^{s}{\bf m}_{i}\star{g_{i}}\mid
s\in{\mathbb{N}},g_{i}\in{\cal F},{\bf m}_{i}\in S\\}$ is a right submodule of
${\cal M}$. This set is denoted as $\langle S\rangle_{r}$ and $S$ is called
its generating set. If $\langle S\rangle_{r}={\cal M}$ then $S$ is a
generating set of the right module itself. If $S$ is finite then ${\cal M}$ is
said to be finitely generated. A generating set is called linearly independent
or a basis if for all $s\in{\mathbb{N}}$, pairwise different ${\bf
m}_{1},\ldots,{\bf m}_{s}\in S$ and $g_{1},\ldots,g_{s}\in{\cal F}$,
$\sum_{i=1}^{s}{\bf m}_{i}\star g_{i}={\bf 0}$ implies $g_{1}=\ldots=g_{s}=o$.
A right ${\cal F}$-module is called free if it has a basis. The right ${\cal
F}$-module ${\cal F}^{k}$ is free and one such basis is the set of unit
vectors ${\bf e}_{1}=({\bf 1},o,\ldots,o),{\bf e}_{2}=(o,{\bf
1},o,\ldots,o),\ldots,{\bf e}_{k}=(o,\ldots,o,{\bf 1})$. Using this basis the
elements of ${\cal F}^{k}$ can be written uniquely as ${\bf
f}=\sum_{i=1}^{k}{\bf e}_{i}\star f_{i}$ where ${\bf f}=(f_{1},\ldots,f_{k})$.
Moreover, ${\cal F}^{k}$ has special properties similar to the special case of
${\mathbb{K}}[x_{1},\ldots,x_{n}]$ and we will continue to state some of them.

###### Theorem 4.3.3

Let ${\cal F}$ be right Noetherian. Then every right submodule of ${\cal
F}^{k}$ is finitely generated.

Proof :
Let ${\cal S}$ be a right submodule of ${\cal F}^{k}$. We show our claim by
induction on $k$. For $k=1$ we find that ${\cal S}$ is in fact a right ideal
in ${\cal F}$ and hence by our hypothesis finitely generated. For $k>1$ let us
look at the set $I=\\{f_{1}\mid(f_{1},\ldots,f_{k})\in{\cal S}\\}$. Then again
$I$ is a right ideal in ${\cal F}$ and hence finitely generated. Let
$\\{g_{1},\ldots,g_{s}\mid g_{i}\in{\cal F}\\}$ be a generating set of $I$.
Choose ${\bf g}_{1},\ldots,{\bf g}_{s}\in{\cal S}$ such that the first
coordinate of ${\bf g}_{i}$ is $g_{i}$. Similarly, the set
$\\{(f_{2},\ldots,f_{k})\mid(o,f_{2},\ldots,f_{k})\in{\cal S}\\}$ is a
submodule of ${\cal F}^{k-1}$ and hence finitely generated by some set
$\\{(n_{2}^{i},\ldots,n_{k}^{i}),1\leq i\leq w\\}$. Then the set $\\{{\bf
g}_{1},\ldots,{\bf g}_{s}\\}\cup\\{{\bf
n}_{i}=(o,n_{2}^{i},\ldots,n_{k}^{i})\mid 1\leq i\leq w\\}$ is a generating
set for ${\cal S}$. To see this assume ${\bf m}=(m_{1},\ldots,m_{k})\in{\cal
S}$. Then $m_{1}=\sum_{i=1}^{s}g_{i}\star h_{i}$ for some $h_{i}\in{\cal F}$
and ${\bf m^{\prime}}={\bf m}-\sum_{i=1}^{s}{\bf g}_{i}\star h_{i}\in{\cal S}$
with first coordinate $o$. Hence ${\bf m^{\prime}}=\sum_{i=1}^{w}{\bf
n}_{i}\star l_{i}$ for some $l_{i}\in{\cal F}$ giving rise to

${\bf m}={\bf m^{\prime}}+\sum_{i=1}^{s}{\bf g}_{i}\star
h_{i}=\sum_{i=1}^{w}{\bf n}_{i}\star l_{i}+\sum_{i=1}^{s}{\bf g}_{i}\star
h_{i}.$

q.e.d.

${\cal F}^{k}$ is called right Noetherian if and only if all its right
submodules are finitely generated.

If ${\cal F}$ is a right reduction ring, results on the existence of right
Gröbner bases for the right submodules carry over from modifications of the
proofs in Section 4.3.

A natural reduction relation using the right reduction relation in ${\cal F}$
denoted by $\Longrightarrow$ can be defined using the representation as
(module) polynomials with respect to the basis of unit vectors as follows:

###### Definition 4.3.4

Let ${\bf f}=\sum_{i=1}^{k}{\bf e}_{i}\star f_{i}$, ${\bf
p}=\sum_{i=1}^{k}{\bf e}_{i}\star p_{i}\in{\cal F}^{k}$. We say that ${\bf f}$
reduces ${\bf p}$ to ${\bf q}$ at ${\bf e}_{s}\star p_{s}$ in one step,
denoted by ${\bf p}\longrightarrow_{\bf f}{\bf q}$, if

  1. 1.

$p_{j}=o$ for $1\leq j<s$,

  2. 2.

$p_{s}\Longrightarrow_{f_{s}}q_{s}$,

  3. 3.

${\bf q}$ | = |  ${\bf p}-\sum_{i=1}^{n}{\bf f}\cdot d_{i}$
---|---|---
| = |  $(0,\ldots,0,q_{s},p_{s+1}-\sum_{i=1}^{n}f_{s+1}\cdot d,\ldots,p_{k}-\sum_{i=1}^{n}f_{k}\cdot d)$.

$\diamond$

Notice that item 2 of this definition is dependant on the definition of the
reduction relation $\Longrightarrow$ in ${\cal F}$. If we assume that the
reduction relation is the one specified in Definition 4.2.43 we get
$p_{s}=q_{s}+f_{s}\cdot d$, $d\in{\sf M}({\cal F})$, but there are other
possibilities. Reviewing the introduction of right modules to reduction rings
we could substitute 2. by $p_{s}=q_{s}+f_{s}\cdot d$, $d\in{\cal F}$ as well
(compare Definition 3.4.8).

To show that our reduction relation is terminating we have to extend the
ordering from ${\cal F}$ to ${\cal F}^{k}$. For two elements ${\bf
p}=(p_{1},\ldots,p_{k})$, ${\bf q}=(q_{1},\ldots,q_{k})\in{\cal F}^{k}$ we
define ${\bf p}\succ{\bf q}$ if and only if there exists $1\leq s\leq k$ such
that $p_{i}=q_{i}$, $1\leq i<s$, and $p_{s}\succ q_{s}$.

###### Lemma 4.3.5

Let $F$ be a finite set of module polynomials in ${\cal F}^{k}$.

  1. 1.

For ${\bf p},{\bf q}\in{\cal F}^{k}$ ${\bf
p}\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}{\bf
q}$ implies ${\bf p}\succ{\bf q}$.

  2. 2.

$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$ is
Noetherian in case $\Longrightarrow_{F_{i}}$ is for $1\leq i\leq k$ and
$F_{i}=\\{f_{i}\mid f=(f_{1},\ldots,f_{k})\in F\\}$.434343Notice that
$F_{i}\subseteq{\cal F}$..

Proof :

  1. 1.

Assuming that the reduction step takes place at ${\bf e}_{s}\star p_{s}$, by
Definition 4.3.4 we know $p_{s}\Longrightarrow_{f_{s}}q_{s}$ and $p_{s}>q_{s}$
implying ${\bf p}\succ{\bf q}$.

  2. 2.

This follows from 1. and Axiom (A1).

q.e.d.

###### Definition 4.3.6

A subset $B$ of ${\cal F}^{k}$ is called a right Gröbner basis of the right
submodule ${\cal S}=\langle B\rangle_{r}$, if
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}=\;\;\equiv_{{\cal
S}}$ and $\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{B}\,$
is convergent. $\diamond$

For any reduction relation in ${\cal F}$ fulfilling the Axioms (A1)–(A3), the
following theorem holds.

###### Theorem 4.3.7

If in $({\cal
F},\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}\,$})$
every finitely generated right ideal has a finite right Gröbner basis, then
the same holds for finitely generated right submodules in $({\cal
F}^{k},\longrightarrow)$.

Proof :
Let ${\cal S}=\langle\\{{\bf s}_{1},\ldots,{\bf s}_{n}\\}\rangle$ be a
finitely generated right submodule of ${\cal F}^{k}$. We show our claim by
induction on $k$. For $k=1$ we find that ${\cal S}$ is in fact a finitely
generated right ideal in ${\cal F}$ and hence by our hypothesis must have a
finite right Gröbner basis. For $k>1$ let us look at the set
$I=\\{f_{1}\mid(f_{1},\ldots,f_{k})\in{\cal S}\\}$ which is in fact the right
ideal generated by $\\{s_{1}^{i}\mid{\bf
s}_{i}=(s_{1}^{i},\ldots,s_{k}^{i}),1\leq i\leq n\\}$. Hence $I$ must have a
finite right Gröbner basis $H=\\{g_{1},\ldots,g_{s}\mid g_{i}\in{\cal F}\\}$.
Choose ${\bf g}_{1},\ldots,{\bf g}_{s}\in{\cal S}$ such that the first
coordinate of ${\bf g}_{i}$ is $g_{i}$. Similarly the set ${\cal
S}^{\prime}=\\{(f_{2},\ldots,f_{k})\mid(o,f_{2},\ldots,f_{k})\in{\cal S}\\}$
is a submodule in ${\cal F}^{k-1}$ which by our induction hypothesis then must
have a finite right Gröbner basis
$\\{(\tilde{g}_{2}^{i},\ldots,\tilde{g}_{k}^{i}),1\leq i\leq w\\}$. Then the
set $G=\\{{\bf g}_{1},\ldots,{\bf
g}_{s}\\}\cup\\{{\bf\tilde{g}}_{i}=(o,\tilde{g}_{2}^{i},\ldots,\tilde{g}_{k}^{i})\mid
1\leq i\leq w\\}$ is a right Gröbner basis for ${\cal S}$. As shown in the
proof of Theorem 4.3.3, $G$ is a generating set for ${\cal S}$. It remains to
show that $G$ is in fact a right Gröbner basis.
First we have to show
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{G}\,$}=\;\;\equiv_{{\cal
S}}$. By the definition of the reduction relation in ${\cal F}^{k}$ we
immediately find
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{G}\,$}\subseteq\;\;\equiv_{{\cal
S}}$. To see the converse let ${\bf p}=(p_{1},\ldots,p_{k})\equiv_{{\cal
S}}{\bf q}=(q_{1},\ldots,q_{k})$. Then
$p_{1}\equiv_{\langle\\{s^{1}_{i}\mid{\bf
s}_{i}=(s_{1}^{i},\ldots,s_{k}^{i}),1\leq i\leq n\\}\rangle_{r}}q_{1}$ and
hence by the definition of $G$ we get
$p_{1}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{\\{g_{1}^{i}\mid{\bf
g}_{i}=(g_{1}^{i},\ldots,g_{k}^{i}),1\leq i\leq s\\}}\,$}q_{1}$. But this
gives us ${\bf
p}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{H}\,$}{\bf
p}+\sum_{i=1}^{s}{\bf g}_{i}\star r_{i}={\bf
p}^{\prime}=(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})$, $r_{i}\in{\cal
F}$, and we get $(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})\equiv_{{\cal
S}}(q_{1},q_{2},\ldots,q_{k})$ and hence
$(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})-(q_{1},q_{2},\ldots,q_{k})=(o,{p_{2}}^{\prime}-q_{2},\ldots,{p_{k}}^{\prime}-q_{k})\in{\cal
S}$ implying $({p_{2}}^{\prime}-q_{2},\ldots,{p_{k}}^{\prime}-q_{k})\in{\cal
S}^{\prime}$ and
$(o,{p_{2}}^{\prime}-q_{2},\ldots,{p_{k}}^{\prime}-q_{k})=\sum_{i=1}^{w}{\bf\tilde{g}}_{i}\star{\eta_{i}}$
for $\eta_{i}\in{\cal F}$. Hence
$(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})$ and
$(q_{1},q_{2},\ldots,q_{k})=(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})-(o,{p_{2}}^{\prime}-q_{2},\ldots,{p_{k}}^{\prime}-q_{k})=(q_{1},{p_{2}}^{\prime},\ldots,{p_{k}}^{\prime})-\sum_{i=1}^{w}{\bf\tilde{g}}_{i}\star{\eta_{i}}$
must be joinable by $\\{{\bf\tilde{g}}_{i}\mid 1\leq i\leq w\\}$ as the
restriction of this set without the first coordinate is a right Gröbner basis
of ${\cal S}^{\prime}$.
Since the reduction relation using the finite set $G$ is terminating we only
have to show local confluence. Let us assume there are ${\bf p}$, ${\bf
q}_{1}$, ${\bf q}_{2}\in{\cal F}^{k}$ such that ${\bf
p}\longrightarrow_{G}{\bf q}_{1}$ and ${\bf p}\longrightarrow_{G}{\bf q}_{2}$.
Then by the definition of $G$ the first coordinates $q^{1}_{1}$ and
$q^{2}_{1}$ are joinable to some element say $s$ by
$H=\\{g_{1},\ldots,g_{s}\\}$ giving rise to the elements ${\bf p}_{1}={\bf
q}_{1}+\sum_{i=1}^{s}{\bf g}_{i}\star h_{i}$ and ${\bf p}_{2}={\bf
q}_{2}+\sum_{i=1}^{s}{\bf g}_{i}\star\tilde{h}_{i}$ with first coordinate $s$.
As before, ${\bf p}_{1}={\bf
p}_{2}+\sum_{i=1}^{w}{\bf\tilde{g}}_{i}\star{\eta_{i}}$ and hence ${\bf
p}_{1}$ and ${\bf p}_{2}$ must be joinable by $\\{{\bf\tilde{g}}_{i}\mid 1\leq
i\leq w\\}$.
q.e.d.

Now given a right submodule ${\cal S}$ of ${\cal M}$, we can define ${\cal
M}/{\cal S}=\\{{\bf f}+{\cal S}\mid{\bf f}\in{\cal M}\\}$. Then with addition
defined as $({\bf f}+{\cal S})+({\bf g}+{\cal S})=({\bf f}+{\bf g})+{\cal S}$
the set ${\cal M}/{\cal S}$ is an Abelian group and can be turned into a right
${\cal F}$-module by the action $({\bf f}+{\cal S})\star g={\bf f}\star
g+{\cal S}$. ${\cal M}/{\cal S}$ is called the right quotient module of ${\cal
M}$ by ${\cal S}$.

As usual this quotient can be related to homomorphisms. The results carry over
from commutative module theory as can be found in [AL94]. Recall that for two
right ${\cal F}$-modules ${\cal M}$ and ${\cal N}$, a function $\phi:{\cal
M}\longrightarrow{\cal N}$ is a right ${\cal F}$-module homomorphism if

$\phi({\bf f}+{\bf g})=\phi({\bf f})+\phi({\bf g})\mbox{ for all }{\bf
f,g}\in{\cal M}$

and

$\phi({\bf f})\star g=\phi({\bf f}\star g)\mbox{ for all }{\bf f}\in{\cal
M},g\in{\cal F}.$

The homomorphism is called an isomorphism if $\phi$ is one to one and we then
write ${\cal M}\cong{\cal N}$. Let ${\cal S}={\rm ker}(\phi)=\\{{\bf
f}\in{\cal M}\mid\phi({\bf f})={\bf 0}\\}$. Then ${\cal S}$ is a right
submodule of ${\cal M}$ and $\phi({\cal M})$ is a right submodule of ${\cal
N}$. Since all are Abelian groups we know ${\cal M}/{\cal S}\cong\phi({\cal
M})$ under the mapping ${\cal M}/{\cal S}\longrightarrow\phi({\cal M})$ with
${\bf f}+{\cal S}\mapsto\phi({\bf f})$ which is in fact an isomorphism. All
right submodules of the quotient ${\cal M}/{\cal S}$ are of the form ${\cal
L}/{\cal S}$ where ${\cal L}$ is a right submodule of ${\cal M}$ containing
${\cal S}$.

We can even show that every finitely generated right ${\cal F}$-module is of a
special form.

###### Lemma 4.3.8

Every finitely generated right ${\cal F}$-module ${\cal M}$ is isomorphic to
${\cal F}^{k}/{\cal N}$ for some $k\in{\mathbb{N}}$ and some right submodule
${\cal N}$ of ${\cal F}^{k}$.

Proof :
Let ${\cal M}$ be a finitely generated right ${\cal F}$-module with generating
set ${\bf f}_{1},\ldots{\bf f}_{k}\in{\cal M}$. Consider the mapping
$\phi:{\cal F}^{k}\longrightarrow{\cal M}$ defined by
$\phi(g_{1},\ldots,g_{k})=\sum_{i=1}^{k}{\bf f}_{i}\star g_{i}$. Then $\phi$
is an ${\cal F}$-module homomorphism with image ${\cal M}$. Let ${\cal N}$ be
the kernel of $\phi$, then the First Isomorphism Theorem for modules yields
our claim. Note that $\phi$ is uniquely defined by specifying the image of
each unit vector ${\bf e}_{1},\ldots,{\bf e}_{k}$, namely by $\phi({\bf
e}_{i})={\bf f}_{i}$.
q.e.d.

Now, there are two ways to give a finitely generated right ${\cal F}$-module
${\cal M}\subset{\cal F}^{k}$. One is to be given explicit ${\bf
f}_{1},\ldots{\bf f}_{t}\in{\cal F}^{k}$ such that ${\cal M}=\langle\\{{\bf
f}_{1},\ldots{\bf f}_{s}\\}\rangle_{r}$. The other way is to give a right
submodule ${\cal N}=\langle\\{{\bf g}_{1},\ldots{\bf g}_{s}\\}\rangle_{r}$ for
explicit ${\bf g}_{1},\ldots{\bf g}_{s}\in{\cal F}^{k}$ such that ${\cal
M}\cong{\cal F}^{k}/{\cal N}$. This is called a presentation of ${\cal M}$.

Presentations are chosen when studying right ideals of ${\cal F}$ as right
${\cal F}$-modules. To see how this is done let $\mathfrak{i}$ be the right
ideal generated by $\\{f_{1},\ldots,f_{k}\\}$ in ${\cal F}$. Let us consider
the right ${\cal F}$-module homomorphism defined as a mapping $\phi:{\cal
F}^{k}\longrightarrow\mathfrak{i}$ with
$\phi(g_{1},\ldots,g_{k})=\sum_{i=1}^{k}f_{i}\star g_{i}$. Then
$\mathfrak{i}\cong{\cal F}^{k}/{\rm ker}(\phi)$ as ${\cal F}$-modules. ${\rm
ker}(\phi)$ is called the right syzygy of $\\{f_{1},\ldots,f_{k}\\}$ denoted
by ${\rm Syz}(f_{1},\ldots,f_{k})$. In fact ${\rm Syz}(f_{1},\ldots,f_{k})$ is
the set of all solutions of the linear equation
$f_{1}X_{1}+\ldots+f_{k}X_{k}=o$ in ${\cal F}$. Syzygies play an important
role in Gröbner basis theory for ordinary polynomial rings.

###  4.4 Ideals and Standard Representations

A subset $\mathfrak{i}\subseteq{\cal F}$ is called a (two-sided) ideal, if

  1. 1.

$o\in\mathfrak{i}$,

  2. 2.

for $f,g\in\mathfrak{i}$ we have $f\oplus g\in\mathfrak{i}$, and

  3. 3.

for $f\in\mathfrak{i}$, $g,h\in{\cal F}$ we have $g\star f\star
h\in\mathfrak{i}$.

Ideals can also be specified in terms of a generating set. For
$F\subseteq{\cal F}\backslash\\{o\\}$ let ${\sf
ideal}(F)=\\{\sum_{i=1}^{n}g_{i}\star f_{i}\star h_{i}\mid f_{i}\in
F,g_{i},h_{i}\in{\cal F},n\in{\mathbb{N}}\\}=\\{\sum_{i=1}^{m}m_{i}\star
f_{i}\star l_{i}\mid f_{i}\in F,m_{i},l_{i}\in{\sf M}({\cal
F}),n\in{\mathbb{N}}\\}$. These generated sets are in fact subsets of ${\cal
F}$ since for $f,g\in{\cal F}$ we have that $f\star g$ as well as $f\oplus g$
are again elements of ${\cal F}$, and it is easily checked that they are in
fact ideals:

  1. 1.

$o\in{\sf ideal}(F)$ since $o$ can be written as the empty sum.

  2. 2.

For two elements $\sum_{i=1}^{n}g_{i}\star f_{i}\star h_{i}$ and
$\sum_{i=1}^{m}\tilde{g}_{i}\star\tilde{f}_{i}\star\tilde{h}_{i}$ in ${\sf
ideal}(F)$, the sum $\sum_{i=1}^{n}g_{i}\star f_{i}\star
h_{i}\oplus\sum_{i=1}^{m}\tilde{g}_{i}\star\tilde{f}_{i}\star\tilde{h}_{i}$ is
again an element in ${\sf ideal}(F)$.

  3. 3.

For an element $\sum_{i=1}^{n}g_{i}\star f_{i}\star h_{i}$ in ${\sf
ideal}_{r}(F)$ and two polynomials $g,h$ in ${\cal F}$, the product
$g\star(\sum_{i=1}^{n}g_{i}\star f_{i}\star h_{i})\star
h=\sum_{i=1}^{n}(g\star g_{i})\star f_{i}\star(h_{i}\star h)$ is again an
element in ${\sf ideal}(F)$.

Given an ideal $\mathfrak{i}\subseteq{\cal F}$ we call a set $F\subseteq{\cal
F}\backslash\\{o\\}$ a basis of $\mathfrak{i}$ if $\mathfrak{i}={\sf
ideal}(F)$. Then every element $g\in{\sf ideal}(F)\backslash\\{o\\}$ can have
different representations of the form

$g=\sum_{i=1}^{n}g_{i}\star f_{i}\star h_{i},f_{i}\in F,g_{i},h_{i}\in{\cal
F},n\in{\mathbb{N}}.$

Notice that the $f_{i}$ occurring in this sum are not necessarily different.
The distributivity law in ${\cal F}$ allows to convert such a representation
into one of the form

$g=\sum_{j=1}^{m}m_{i}\star f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf
M}({\cal F}),n\in{\mathbb{N}}.$

Again special representations can be distinguished in order to characterize
special ideal bases. An ordering on ${\cal F}$ is used to define appropriate
standard representations. As in the case of right ideals we will first look at
generalizations of standard representations for the case of function rings
over fields.

####  4.4.1 The Special Case of Function Rings over Fields

Let ${\cal F}_{{\mathbb{K}}}$ be a function ring over a field ${\mathbb{K}}$.
We first look at an analogon to Definition 4.2.7

###### Definition 4.4.1

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $g$ a non-
zero polynomial in ${\sf ideal}(F)$. A representations of the form

$g=\sum_{i=1}^{n}m_{i}\star f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf
M}({\cal F}_{{\mathbb{K}}}),n\in{\mathbb{N}}$

where additionally ${\sf HT}(g)\succeq{\sf HT}(m_{i}\star f_{i}\star l_{i})$
holds for $1\leq i\leq n$ is called a standard representation of $g$ in terms
of $F$. If every $g\in{\sf ideal}(F)\backslash\\{o\\}$ has such a
representation in terms of $F$, then $F$ is called a standard basis of ${\sf
ideal}(F)$. $\diamond$

Notice that since we assume $f\cdot\alpha=\alpha\cdot f$, we can also
substitute the monomials $l_{i}$ by terms $w_{i}\in{\cal T}$, i.e. study
representations of the form

$g=\sum_{i=1}^{n}m_{i}\star f_{i}\star w_{i},f_{i}\in F,m_{i}\in{\sf M}({\cal
F}),w_{i}\in{\cal T},n\in{\mathbb{N}}.$

We will use this additional information in some proofs later on.

As with right standard representations, in order to change an arbitrary
representation of an ideal element into a standard representation we have to
deal with special sums of polynomials. We get the following analogon to
Definition 4.2.8.

###### Definition 4.4.2

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $t$ an
element in ${\cal T}$. Then we define a set ${\cal C}(F,t)$ to contain all
tuples of the form
$(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k},l_{1},\ldots,l_{k})$,
$k\in{\mathbb{N}}$, $f_{1},\ldots,f_{k}\in F$,
$m_{1},\ldots,m_{k},l_{1},\ldots,l_{k}\in{\sf M}({\cal F}_{{\mathbb{K}}})$
such that

  1. 1.

${\sf HT}(m_{i}\star f_{i}\star l_{i})=t$, $1\leq i\leq k$, and

  2. 2.

$\sum_{i=1}^{k}{\sf HM}(m_{i}\star f_{i}\star l_{i})=0$.

We set ${\cal C}(F)=\bigcup_{t\in{\cal T}}{\cal C}(F,t)$. $\diamond$

Notice that this definition is motivated by the definition of syzygies of head
monomials in commutative polynomial rings over rings. We can characterize
standard bases using this concept (compare Theorem 4.2.9).

###### Theorem 4.4.3

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.
Then $F$ is a standard basis of ${\sf ideal}(F)$ if and only if for every
tuple $(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k},l_{1},\ldots,l_{k})$ in ${\cal
C}(F)$ the polynomial $\sum_{i=1}^{k}m_{i}\star f_{i}\star l_{i}$ (i.e. the
element in ${\cal F}_{{\mathbb{K}}}$ corresponding to this sum) has a standard
representation with respect to $F$.

Proof :
In case $F$ is a standard basis since the polynomials related to the tuples
are all elements of ${\sf ideal}(F)$ they must have standard representations
with respect to $F$.
To prove the converse, it remains to show that every element in ${\sf
ideal}(F)$ has a standard representation with respect to $F$. Hence, let
$g=\sum_{j=1}^{m}m_{j}\star f_{j}\star l_{j}$ be an arbitrary representation
of a non-zero polynomial $g\in{\sf ideal}(F)$ such that $f_{j}\in F$,
$m_{j},l_{j}\in{\sf M}({\cal F}_{{\mathbb{K}}})$, $m\in{\mathbb{N}}$.
Depending on this representation of $g$ and the well-founded total ordering
$\succeq$ on ${\cal T}$ we define $t=\max_{\succeq}\\{{\sf HT}(m_{j}\star
f_{j}\star l_{j})\mid 1\leq j\leq m\\}$ and $K$ as the number of polynomials
$m_{j}\star f_{j}\star l_{j}$ with head term $t$. Then $t\succeq{\sf HT}(g)$
and in case ${\sf HT}(g)=t$ this immediately implies that this representation
is already a standard one. Else we proceed by induction on $t$. Without loss
of generality let $f_{1},\ldots,f_{K}$ be the polynomials in the corresponding
representation such that $t={\sf HT}(m_{j}\star f_{j}\star l_{j})$, $1\leq
j\leq K$. Then the tuple
$(t,f_{1},\ldots,f_{K},m_{1},\ldots,m_{K},l_{1},\ldots,l_{K})$ is in ${\cal
C}(F)$ and let $h=\sum_{j=1}^{K}m_{j}\star f_{j}\star l_{j}$. We will now
change our representation of $g$ in such a way that for the new representation
of $g$ we have a smaller maximal term. Let us assume $h$ is not $o$444444In
case $h=o$, just substitute the empty sum for the representation of $h$ in the
equations below.. By our assumption, $h$ has a standard representation with
respect to $F$, say
$\sum_{i=1}^{n}\tilde{m}_{i}\star\tilde{f}_{i}\star\tilde{l}_{i}$, where
$\tilde{f}_{i}\in F$, and $\tilde{m}_{i},\tilde{l}_{i}\in{\sf M}({\cal
F}_{{\mathbb{K}}})$ and all terms occurring in the sum are bounded by
$t\succ{\sf HT}(h)$. This gives us:

$\displaystyle g$ $\displaystyle=$ $\displaystyle\sum_{j=1}^{K}m_{j}\star
f_{j}\star l_{j}+\sum_{j=K+1}^{m}m_{j}\star f_{j}\star l_{j}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\tilde{m}_{i}\star\tilde{f}_{i}\star\tilde{l}_{i}+\sum_{j=K+1}^{m}m_{j}\star
f_{j}\star l_{j}$

which is a representation of $g$ where the maximal term of the involved
monomial multiples is decreased.
q.e.d.

Weak Gröbner bases can be defined as in Definition 4.2.10. Since the ordering
$\succeq$ and the multiplication $\star$ in general are not compatible,
instead of considering multiples of head terms of the generating set $F$ we
look at head terms of monomial multiples of polynomials in $F$.

###### Definition 4.4.4

A subset $F$ of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ is called a weak
Gröbner basis of ${\sf ideal}(F)$ if ${\sf HT}({\sf
ideal}(F)\backslash\\{o\\})={\sf HT}(\\{m\star f\star l\mid f\in F,m,l\in{\sf
M}({\cal F}_{{\mathbb{K}}})\\}\backslash\\{o\\})$. $\diamond$

In the next lemma we show that in fact both characterizations of special
bases, standard bases and weak Gröbner bases, coincide as in the case of
polynomial rings over fields (compare Lemma 4.2.11).

###### Lemma 4.4.5

Let $F$ be a subset of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$. Then $F$ is
a standard basis if and only if it is a weak Gröbner basis.

Proof :
Let us first assume that $F$ is a standard basis, i.e., every polynomial $g$
in ${\sf ideal}(F)$ has a standard representation with respect to $F$. In case
$g\neq o$ this implies the existence of a polynomial $f\in F$ and monomials
$m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such that ${\sf HT}(g)={\sf
HT}(m\star f\star l)$. Hence ${\sf HT}(g)\in{\sf HT}(\\{m\star f\star l\mid
m,l\in{\sf M}({\cal F}_{{\mathbb{K}}}),f\in F\\}\backslash\\{o\\})$. As the
converse, namely ${\sf HT}(\\{m\star f\star l\mid m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}}),f\in F\\}\backslash\\{o\\})\subseteq{\sf HT}({\sf
ideal}(F)\backslash\\{o\\})$ trivially holds, $F$ then is a weak Gröbner
basis.
Now suppose that $F$ is a weak Gröbner basis and again let $g\in{\sf
ideal}(F)$. We have to show that $g$ has a standard representation with
respect to $F$. This will be done by induction on ${\sf HT}(g)$. In case $g=o$
the empty sum is our required standard representation. Hence let us assume
$g\neq o$. Since then ${\sf HT}(g)\in{\sf HT}({\sf
ideal}(F)\backslash\\{o\\})$ by the definition of weak Gröbner bases we know
there exists a polynomial $f\in F$ and monomials $m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}})$ such that ${\sf HT}(g)={\sf HT}(m\star f\star l)$. Then
there exists a monomial $\tilde{m}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such
that ${\sf HM}(g)={\sf HM}(\tilde{m}\star f\star l)$, namely454545Notice that
this step requires that we can view ${\cal F}_{{\mathbb{K}}}$ as a vector
space. In order to get a similar result without introducing vector spaces we
would have to use a different definition of weak Gröbner bases. E.g. requiring
that ${\sf HM}({\sf ideal}(F)\backslash\\{o\\})={\sf HM}(\\{m\star f\star
l\mid f\in F,m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})\\}\backslash\\{o\\}\\})$
would be a possibility. However, then no localization of critical situations
to head terms is possible, which is the advantage of having a field as
coefficient domain. $\tilde{m}=({\sf HC}(g)\cdot{\sf HC}(m\star f\star
l)^{-1})\cdot m)$. Let $g_{1}=g-\tilde{m}\star f\star l$. Then ${\sf
HT}(g)\succ{\sf HT}(g_{1})$ implies the existence of a standard representation
for $g_{1}$ which can be added to the multiple $\tilde{m}\star f\star l$ to
give the desired standard representation of $g$.
q.e.d.

Inspecting this proof closer we get the following corollary (compare Corollary
4.2.12).

###### Corollary 4.4.6

Let a subset $F$ of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ be a weak
Gröbner basis. Then every $g\in{\sf ideal}(F)$ has a standard representation
in terms of $F$ of the form $g=\sum_{i=1}^{n}m_{i}\star f_{i}\star
l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf M}({\cal
F}_{{\mathbb{K}}}),n\in{\mathbb{N}}$ such that ${\sf HM}(g)={\sf
HM}(m_{1}\star f_{1}\star l_{1})$ and ${\sf HT}(m_{1}\star f_{1}\star
l_{1})\succ{\sf HT}(m_{2}\star f_{2}\star l_{2})\succ\ldots\succ{\sf
HT}(m_{n}\star f_{n}\star l_{n})$.

Notice that we hence get stronger representations as specified in Definition
4.4.1 for the case that the set $F$ is a weak Gröbner basis or a standard
basis.

In order to proceed as before in the case of one-sided ideals we have to
extend our restriction of the ordering $\succeq$ on ${\cal F}$ to cope with
two-sided multiplication similar to Definition 4.2.13.

###### Definition 4.4.7

We will call an ordering $\geq$ on ${\cal T}$ a reductive restriction of the
ordering $\succeq$ or simply reductive, if the following hold:

  1. 1.

$t\geq s$ implies $t\succeq s$ for $t,s\in{\cal T}$.

  2. 2.

$\geq$ is a partial well-founded ordering on ${\cal T}$ which is compatible
with multiplication $\star$ in the following sense: if for
$t,t_{1},t_{2},w_{1},w_{2}\in{\cal T}$ $t_{2}\geq t_{1}$, $t_{1}\succ t$ and
$t_{2}={\sf HT}(w_{1}\star t_{1}\star w_{2})$ hold, then $t_{2}\succ{\sf
HT}(w_{1}\star t\star w_{2})$. $\diamond$

Again we can distiguish special “divisors” of monomials: For
$m_{1},m_{2}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ we call $m_{1}$ a (stable)
divisor of $m_{2}$ if and only if ${\sf HT}(m_{2})\geq{\sf HT}(m_{1})$ and
there exist $l_{1},l_{2}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such that
$m_{2}={\sf HM}(l_{1}\star m_{1}\star l_{2})$. We then call $l_{1},l_{2}$
stable multipliers of $m_{1}$. The intention is that for all terms $t$ with
${\sf HT}(m_{1})\succ t$ we then can conclude ${\sf HT}(m_{2})\succ{\sf
HT}(l_{1}\star t\star l_{2})$. Reduction relations based on this divisibility
of terms will again have the stability properties we desire. In the
commutative polynomial ring we can state a reductive restriction of any term
ordering by $t\geq s$ for two terms $t$ and $s$ if and only if $s$ divides $t$
as a term. In the non-commutative polynomial ring we can state a reductive
restriction of any term ordering by $t\geq s$ for two terms $t$ and $s$ if and
only if $s$ is a subword of $t$. Let us continue with an algebraic consequence
related to this reductive ordering by distinguishing special standard
representations as we have done in Definition 4.2.15.

###### Definition 4.4.8

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $g$ a non-
zero polynomial in ${\sf ideal}(F)$. A representation of the form

$g=\sum_{i=1}^{n}m_{i}\star f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf
M}({\cal F}_{{\mathbb{K}}}),n\in{\mathbb{N}}$

such that ${\sf HT}(g)={\sf HT}(m_{i}\star f_{i}\star l_{i})={\sf
HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq k$
for some $k\geq 1$, and ${\sf HT}(g)\succ{\sf HT}(m_{i}\star{\sf
HT}(f_{i})\star l_{i})$ for $k<i\leq n$ is called a reductive standard
representation in terms of $F$. $\diamond$

Again the empty sum is taken as reductive standard representation of $o$.

In case we have $\star:{\cal T}\times{\cal T}\longrightarrow{\cal T}$ the
condition can be rephrased as ${\sf HT}(g)=m_{i}\star f_{i}\star l_{i}={\sf
HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq
k$.

###### Definition 4.4.9

A set $F\subseteq{\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ is called a
reductive standard basis (with respect to the reductive ordering $\geq$) of
${\sf ideal}(F)$ if every polynomial $f\in{\sf ideal}(F)$ has a reductive
standard representation in terms of $F$. $\diamond$

Again, in order to change an arbitrary representation into one fulfilling our
additional condition of Definition 4.4.8 we have to deal with special sums of
polynomials.

###### Definition 4.4.10

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $t$ an
element in ${\cal T}$. Then we define the critical set ${\cal C}_{r}(t,F)$ to
contain all tuples of the form
$(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k},l_{1},\ldots,l_{k})$,
$k\in{\mathbb{N}}$, $f_{1},\ldots,f_{k}\in F$464646As in the case of
commutative polynomials, $f_{1},\ldots,f_{k}$ are not necessarily different
polynomials from $F$., $m_{1},\ldots,m_{k},l_{1},\ldots,l_{k}\in{\sf M}({\cal
F})$ such that

  1. 1.

${\sf HT}(m_{i}\star f_{i}\star l_{i})={\sf HT}(m_{i}\star{\sf HT}(f_{i})\star
l_{i})=t$, $1\leq i\leq k$,

  2. 2.

${\sf HT}(m_{i}\star f_{i}\star l_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq k$,
and

  3. 3.

$\sum_{i=1}^{k}{\sf HM}(m_{i}\star f_{i}\star l_{i})=o$.

We set ${\cal C}_{r}(F)=\bigcup_{t\in{\cal T}}{\cal C}_{r}(t,F)$. $\diamond$

Unfortunately, as in the case of right reductive standard bases, these
critical situations will not be sufficient to characterize reductive standard
bases (compare again Example 4.2.18). But we can give an analogon to Theorem
4.2.19.

###### Theorem 4.4.11

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.
Then $F$ is a reductive standard basis of ${\sf ideal}(F)$ if and only if

  1. 1.

for every $f\in F$ and every $m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ the
multiple $m\star f\star l$ has a reductive standard representation in terms of
$F$,

  2. 2.

for every tuple $(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k},l_{1},\ldots,l_{k})$
in ${\cal C}_{r}(F)$ the polynomial $\sum_{i=1}^{k}m_{i}\star f_{i}\star
l_{i}$ (i.e., the element in ${\cal F}$ corresponding to this sum) has a
reductive standard representation with respect to $F$.

Proof :
In case $F$ is a reductive standard basis, since these polynomials are all
elements of ${\sf ideal}(F)$, they must have reductive standard
representations with respect to $F$.
To prove the converse, it remains to show that every element in ${\sf
ideal}(F)$ has a reductive standard representation with respect to $F$. Hence,
let $g=\sum_{j=1}^{m}m_{j}\star f_{j}\star l_{j}$ be an arbitrary
representation of a non-zero polynomial $g\in{\sf ideal}(F)$ such that
$f_{j}\in F$, $m_{j},l_{j}\in{\sf M}({\cal F}_{{\mathbb{K}}})$,
$m\in{\mathbb{N}}$. By our first statement every such monomial multiple
$m_{j}\star f_{j}\star l_{j}$ has a reductive standard representation in terms
of $F$ and we can assume that all multiples are replaced by them. Depending on
this representation of $g$ and the well-founded total ordering $\succeq$ on
${\cal T}$ we define $t=\max_{\succeq}\\{{\sf HT}(m_{j}\star f_{j}\star
l_{j})\mid 1\leq j\leq m\\}$ and $K$ as the number of polynomials $m_{j}\star
f_{j}\star l_{j}$ with head term $t$. Then for each monomial multiple
$m_{j}\star f_{j}\star l_{j}$ with ${\sf HT}(m_{j}\star f_{j}\star l_{j})=t$
we know that ${\sf HT}(m_{j}\star f_{j}\star l_{j})={\sf HT}(m_{j}\star{\sf
HT}(f_{j})\star l_{j})\geq{\sf HT}(f_{j})$ holds. Then $t\succeq{\sf HT}(g)$
and in case ${\sf HT}(g)=t$ this immediately implies that this representation
is already a reductive standard one. Else we proceed by induction on $t$.
Without loss of generality let $f_{1},\ldots,f_{K}$ be the polynomials in the
corresponding representation such that $t={\sf HT}(m_{i}\star f_{i}\star
l_{i})$, $1\leq i\leq K$. Then the tuple
$(t,f_{1},\ldots,f_{K},m_{1},\ldots,m_{K},l_{1},\ldots,l_{K})$ is in ${\cal
C}_{r}(F)$ and let $h=\sum_{i=1}^{K}m_{i}\star f_{i}\star l_{i}$. We will now
change our representation of $g$ in such a way that for the new representation
of $g$ we have a smaller maximal term. Let us assume $h$ is not $o$474747In
case $h=o$, just substitute the empty sum for the representation of $h$ in the
equations below.. By our assumption, $h$ has a reductive standard
representation with respect to $F$, say $\sum_{j=1}^{n}\tilde{m}_{j}\star
h_{j}\star\tilde{l}_{j}$, where $h_{j}\in F$, and
$\tilde{m}_{j},\tilde{l}_{j}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ and all terms
occurring in the sum are bounded by $t\succ{\sf HT}(h)$ as $\sum_{i=1}^{K}{\sf
HM}(m_{i}\star f_{i}\star l_{i})=o$. This gives us:

$\displaystyle g$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{K}m_{i}\star
f_{i}\star l_{i}+\sum_{i=K+1}^{m}m_{i}\star f_{i}\star l_{i}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\tilde{m}_{j}\star
h_{j}\star\tilde{l}_{j}+\sum_{i=K+1}^{m}m_{i}\star f_{i}\star l_{i}$

which is a representation of $g$ where the maximal term is smaller than $t$.
q.e.d.

An algebraic characterization of weak Gröbner bases again can be given by a
property of head monomials based on stable divisors of terms (compare
Definition 4.2.20).

###### Definition 4.4.12

A set $F\subseteq{\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ is called a weak
reductive Gröbner basis of ${\sf ideal}(F)$ (with respect to the reductive
ordering $\geq$) if ${\sf HT}({\sf ideal}(F)\backslash\\{o\\})={\sf
HT}(\\{m\star f\star l\mid f\in F,m,l\in{\sf M}({\cal F}_{{\mathbb{K}}}),{\sf
HT}(m\star f\star l)={\sf HT}(m\star{\sf HT}(f)\star l)\geq{\sf
HT}(f)\\}\backslash\\{o\\})$. $\diamond$

We will later on see that an analogon of the Translation Lemma holds for the
reduction relation related to reductive standard representations. Hence weak
reductive Gröbner bases and Gröbner bases coincide. This is again due to the
fact that the coefficient domain is a field and will not carry over for
reduction rings as coefficient domains.

The next lemma states that in fact both characterizations of special bases
provided so far coincide.

###### Lemma 4.4.13

Let $F$ be a subset of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$. Then $F$ is
a reductive standard basis if and only if it is a weak reductive Gröbner
basis.

Proof :
Let us first assume that $F$ is a reductive standard basis, i.e., every
polynomial $g$ in ${\sf ideal}(F)$ has a reductive standard representation
with respect to $F$. In case $g\neq o$ this implies the existence of a
polynomial $f\in F$ and monomials $m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$
such that ${\sf HT}(g)={\sf HT}(m\star f\star l)={\sf HT}(m\star{\sf
HT}(f)\star l)\geq{\sf HT}(f)$. Hence ${\sf HT}(g)\in{\sf HT}(\\{m\star f\star
l\mid m,l\in{\sf M}({\cal F}_{{\mathbb{K}}}),f\in F,{\sf HT}(m\star f\star
l)={\sf HT}(m\star{\sf HT}(f)\star l)\geq{\sf HT}(f)\\}\backslash\\{o\\})$. As
the converse, namely ${\sf HT}(\\{m\star f\star l\mid m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}}),f\in F,{\sf HT}(m\star f\star l)={\sf HT}(m\star{\sf
HT}(f)\star l)\geq{\sf HT}(f)\\}\backslash\\{o\\})\subseteq{\sf HT}({\sf
ideal}(F)\backslash\\{o\\})$ trivially holds, $F$ is a weak reductive Gröbner
basis.
Now suppose that $F$ is a weak reductive Gröbner basis and again let $g\in{\sf
ideal}(F)$. We have to show that $g$ has a reductive standard representation
with respect to $F$. This will be done by induction on ${\sf HT}(g)$. In case
$g=o$ the empty sum is our required reductive standard representation. Hence
let us assume $g\neq o$. Since then ${\sf HT}(g)\in{\sf HT}({\sf
ideal}(F)\backslash\\{o\\})$ by the definition of weak reductive Gröbner bases
we know there exists a polynomial $f\in F$ and monomials $m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}})$ such that ${\sf HT}(m\star f\star l)={\sf HT}(m\star{\sf
HT}(f)\star l)\geq{\sf HT}(f)$ and there exists $\alpha\in{\mathbb{K}}$ such
that ${\sf HC}(g)={\sf HC}(m\star f\star l)\cdot\alpha$, i.e., ${\sf
HM}(g)={\sf HM}(m\star f\star l\cdot\alpha)$. Let $g_{1}=g-m\star f\star
l\cdot\alpha$. Then ${\sf HT}(g)\succ{\sf HT}(g_{1})$ implies the existence of
a reductive standard representation for $g_{1}$ which can be added to the
multiple $m\star f\star l\cdot\alpha$ to give the desired reductive standard
representation of $g$.
q.e.d.

A close inspection of this proof reveals that in fact we can provide a
stronger condition for standard representations in terms of weak reductive
Gröbner bases.

###### Corollary 4.4.14

Let a subset $F$ of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ be a weak
reductive Gröbner basis. Every $g\in{\sf ideal}(F)$ has a reductive standard
representation in terms of $F$ of the form $g=\sum_{i=1}^{n}m_{i}\star
f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf M}({\cal
F}_{{\mathbb{K}}}),n\in{\mathbb{N}}$ such that ${\sf HT}(g)={\sf
HT}(m_{1}\star f_{1}\star l_{1})\succ{\sf HT}(m_{2}\star f_{2}\star
l_{2})\succ\ldots\succ{\sf HT}(m_{n}\star f_{n}\star l_{n})$ and ${\sf
HT}(m_{i}\star f_{i}\star l_{i})={\sf HT}(m_{i}\star{\sf HT}(f_{i})\star
l_{i})\geq{\sf HT}(f_{i})$ for all $1\leq i\leq n$.

The importance of Gröbner bases in commutative polynomial rings stems from the
fact that they can be characterized by special polynomials, the so-called
s-polynomials. This characterization can be combined with a reduction relation
to an algorithm which computes finite Gröbner bases.

We provide a first characterization for our function ring over the field
${\mathbb{K}}$. Here critical situations lead to s-polynomials as in the
original case and can be identified by studying term multiples of polynomials.
Let $p$ and $q$ be two non-zero polynomials in ${\cal F}_{{\mathbb{K}}}$. We
are interested in terms $t,u_{1},u_{2},v_{1},v_{2}$ such that ${\sf
HT}(u_{1}\star p\star v_{1})={\sf HT}(u_{1}\star{\sf HT}(p)\star v_{1})=t={\sf
HT}(u_{2}\star q\star v_{2})={\sf HT}(u_{2}\star{\sf HT}(q)\star v_{2})$ and
${\sf HT}(p)\leq t$, ${\sf HT}(q)\leq t$. Let ${\cal C}_{s}(p,q)$ (this is a
specialization of Definition 4.4.2) be the set containing all such tuples
$(t,u_{1},u_{2},v_{1},v_{2})$ (as a short hand for
$(t,p,q,u_{1},u_{2},v_{1},v_{2})$. We call the polynomial ${\sf HC}(u_{1}\star
p\star v_{1})^{-1}\cdot u_{1}\star p\star v_{1}-{\sf HC}(u_{2}\star q\star
v_{2})^{-1}\cdot u_{2}\star q\star v_{2}={\sf
spol}{}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ the s-polynomial of $p$ and $q$
related to the tuple $(t,u_{1},u_{2},v_{1},v_{2})$.

Again these critical situations are not sufficient to characterize weak
Gröbner bases (compare Example 4.2.18) and additionally we have to test
monomial multiples of polynomials now from both sides.

###### Theorem 4.4.15

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.
Then $F$ is a weak Gröbner basis of ${\sf ideal}(F)$ if and only if

  1. 1.

for all $f$ in $F$ and for all $m,l$ in ${\sf M}({\cal F}_{{\mathbb{K}}})$ the
multiple $m\star f\star l$ has a reductive standard representation in terms of
$F$, and

  2. 2.

for all $p$ and $q$ in $F$ and every tuple $(t,u_{1},u_{2},v_{1},v_{2})$ in
${\cal C}_{s}(p,q)$ the respective s-polynomial ${\sf
spol}{}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ has a reductive standard
representation in terms of $F$.

Proof :
In case $F$ is a weak Gröbner basis it is also a reductive standard basis, and
since the multiples $m\star f\star l$ as well as the respective s-polynomials
are all elements of ${\sf ideal}(F)$ they must have reductive standard
representations in terms of $F$.
The converse will be proven by showing that every element in ${\sf ideal}(F)$
has a reductive standard representation in terms of $F$. Now, let
$g=\sum_{j=1}^{m}\alpha_{j}\cdot v_{j}\star f_{j}\star w_{j}$ be an arbitrary
representation of a non-zero polynomial $g\in{\sf ideal}(F)$ such that
$\alpha_{j}\in{\mathbb{K}}^{*},f_{j}\in F$, and $v_{j},w_{j}\in{\cal T}$.
Since by our first assumption every multiple $v_{j}\star f_{j}\star w_{j}$ in
this sum has a reductive standard representation we can assume that ${\sf
HT}(v_{j}\star{\sf HT}(f_{j})\star w_{j})={\sf HT}(v_{j}\star f_{j}\star
w_{j})\geq{\sf HT}(f_{j})$ holds.
Depending on this representation of $g$ and the well-founded total ordering
$\succeq$ on ${\cal T}$ we define $t=\max_{\succeq}\\{{\sf HT}(v_{j}\star
f_{j}\star w_{j})\mid 1\leq j\leq m\\}$ and $K$ as the number of polynomials
$v_{j}\star f_{j}\star w_{j}$ with head term $t$. Without loss of generality
we can assume that the polynomial multiples with head term $t$ are just
$v_{1}\star f_{1}\star w_{1},\ldots,v_{K}\star f_{K}\star w_{K}$. We proceed
by induction on $(t,K)$, where $(t^{\prime},K^{\prime})<(t,K)$ if and only if
$t^{\prime}\prec t$ or $(t^{\prime}=t$ and $K^{\prime}<K)$484848Note that this
ordering is well-founded since $\succ$ is well-founded on ${\cal T}$ and
$K\in{\mathbb{N}}$..
Obviously, $t\succeq{\sf HT}(g)$ must hold. If $K=1$ this gives us $t={\sf
HT}(g)$ and by our assumptions our representation is already of the required
form. Hence let us assume $K>1$. Then for the two polynomials $f_{1},f_{2}$ in
the corresponding representation494949Not necessarily $f_{2}\neq f_{1}$. such
that $t={\sf HT}(v_{1}\star{\sf HT}(f_{1})\star w_{1})={\sf HT}(v_{1}\star
f_{1}\star w_{1})={\sf HT}(v_{2}\star f_{2}\star w_{2})={\sf
HT}(v_{2}\star{\sf HT}(f_{2})\star w_{2})$ and $t\geq{\sf HT}(f_{1})$,
$t\geq{\sf HT}(f_{2})$. Then the tuple $(t,v_{1},v_{2},w_{1},w_{2})$ is in
${\cal C}_{s}(f_{1},f_{2})$ and we have an s-polynomial $h={\sf HC}(v_{1}\star
f_{1}\star w_{1})^{-1}\cdot v_{1}\star f_{1}\star w_{1}-{\sf HC}(v_{2}\star
f_{2}\star w_{2})^{-1}\cdot v_{2}\star f_{2}\star w_{2}$ corresponding to this
tuple. We will now change our representation of $g$ by using the additional
information on this s-polynomial in such a way that for the new representation
of $g$ we either have a smaller maximal term or the occurrences of the term
$t$ are decreased by at least 1. Let us assume the s-polynomial is not
$o$505050In case $h=o$, just substitute the empty sum for the reductive
representation of $h$ in the equations below.. By our assumption, $h$ has a
reductive standard representation in terms of $F$, say
$\sum_{i=1}^{n}\tilde{\alpha}_{i}\cdot\tilde{v}_{i}\star\tilde{f}_{i}\star\tilde{w}_{i}$,
where $\tilde{\alpha}_{i}\in{\mathbb{K}}^{*},\tilde{f}_{i}\in F$, and
$\tilde{v}_{i},\tilde{w}_{i}\in{\cal T}$ and all terms occurring in this sum
are bounded by $t\succ{\sf HT}(h)$. This gives us:

$\displaystyle\alpha_{1}\cdot v_{1}\star f_{1}\star w_{1}+\alpha_{2}\cdot
v_{2}\star f_{2}\star w_{2}$ (4.6) $\displaystyle=$
$\displaystyle\alpha_{1}\cdot v_{1}\star f_{1}\star
w_{1}+\underbrace{\alpha^{\prime}_{2}\cdot\beta_{1}\cdot v_{1}\star f_{1}\star
w_{1}-\alpha^{\prime}_{2}\cdot\beta_{1}\cdot v_{1}\star f_{1}\star
w_{1}}_{=\,0}$
$\displaystyle+\underbrace{\alpha^{\prime}_{2}\cdot\beta_{2}}_{\alpha_{2}}\cdot
v_{2}\star f_{2}\star w_{2}$ $\displaystyle=$
$\displaystyle(\alpha_{1}+\alpha^{\prime}_{2}\cdot\beta_{1})\cdot v_{1}\star
f_{1}\star w_{1}-\alpha^{\prime}_{2}\cdot\underbrace{(\beta_{1}\cdot
v_{1}\star f_{1}\star w_{1}-\beta_{2}\cdot v_{2}\star f_{2}\star
w_{2})}_{=\,h}$ $\displaystyle=$
$\displaystyle(\alpha_{1}+\alpha^{\prime}_{2}\cdot\beta_{1})\cdot v_{1}\star
f_{1}\star
w_{1}-\alpha^{\prime}_{2}\cdot(\sum_{i=1}^{n}\tilde{\alpha}_{i}\cdot\tilde{v}_{i}\star\tilde{f}_{i}\star\tilde{w}_{i})$

where $\beta_{1}={\sf HC}(v_{1}\star f_{1}\star w_{1})^{-1}$, $\beta_{2}={\sf
HC}(v_{2}\star f_{2}\star w_{2})^{-1}$ and
$\alpha^{\prime}_{2}\cdot\beta_{2}=\alpha_{2}$. Substituting (4.6) in the
representation of $g$ gives rise to a smaller one.
q.e.d.

Notice that both test sets in this characterization in general cannot be
described in a finitary manner, i.e., provide no finite test for the property
of being a Gröbner basis.

A problem which is related to the fact that the ordering $\succeq$ and the
multiplication $\star$ in general are not compatible is that an important
property fulfilled for representations of polynomials in commutative
polynomial rings no longer holds: As in the case of right ideals the existence
of a standard representation for some polynomial $f\in{\cal F}_{{\mathbb{K}}}$
no longer implies the existence of one for a multiple $m\star f\star l$ where
$m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$. However there are restrictions where
this implication will hold (compare Lemma 4.2.26).

###### Lemma 4.4.16

Let $F$ be a subset of ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ and $p$ a
non-zero polynomial in ${\cal F}_{{\mathbb{K}}}$. If $p$ has a reductive
standard representation with respect to $F$ and $m,l$ are monomials such that
${\sf HT}(m\star p\star l)={\sf HT}(m\star{\sf HT}(p)\star l)\geq{\sf HT}(p)$,
then the multiple $m\star p\star l$ again has a reductive standard
representation with respect to $F$.

Proof :
Let $p=\sum_{i=1}^{n}m_{i}\star f_{i}\star l_{i}$ with $n\in{\mathbb{N}}$,
$f_{i}\in F$, $m_{i},l_{i}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ be a reductive
standard representation of $p$ in terms of $F$, i.e., ${\sf HT}(p)={\sf
HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})={\sf HT}(m_{i}\star f_{i}\star
l_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq k$ and ${\sf HT}(p)\succeq{\sf
HT}(m_{i}\star f_{i}\star l_{i})$ for all $k+1\leq i\leq n$.
Let us first analyze the multiple $m\star m_{j}\star f_{j}\star l_{j}\star l$.
Let ${\sf T}(m_{j}\star f_{j}\star l_{j})=\\{s_{1},\ldots,s_{k}\\}$ with
$s_{1}\succ s_{i}$, $2\leq i\leq l$, i.e. $s_{1}={\sf HT}(m_{j}\star
f_{j}\star l_{j})={\sf HT}(m_{j}\star{\sf HT}(f_{j})\star l_{j})={\sf HT}(p)$.
Hence ${\sf HT}(m\star{\sf HT}(p)\star l)={\sf HT}(m\star s_{1}\star
l)\geq{\sf HT}(p)=s_{1}$ and as $s_{1}\succ s_{i}$, $2\leq i\leq l$, by
Definition 4.4.7 we can conclude ${\sf HT}(m\star{\sf HT}(p)\star l)={\sf
HT}(m\star s_{1}\star l)\succ m\star s_{i}\star l\succeq{\sf HT}(m\star
s_{i}\star l)$ for $2\leq i\leq l$. This implies ${\sf HT}(m\star{\sf
HT}(m_{j}\star f_{j}\star l_{j})\star l)={\sf HT}(m\star m_{j}\star f_{j}\star
l_{j}\star l)$. Hence we get

$\displaystyle{\sf HT}(p\star m)$ $\displaystyle=$ $\displaystyle{\sf
HT}(m\star{\sf HT}(p)\star l)$ $\displaystyle=$ $\displaystyle{\sf
HT}(m\star{\sf HT}(m_{j}\star f_{j}\star l_{j})\star l),\mbox{ as }{\sf
HT}(p)={\sf HT}(m_{j}\star f_{j}\star l_{j})$ $\displaystyle=$
$\displaystyle{\sf HT}(m\star m_{j}\star f_{j}\star l_{j}\star l)$

and since ${\sf HT}(m\star p\star l)\geq{\sf HT}(p)\geq{\sf HT}(f_{j})$ we can
conclude ${\sf HT}(m\star m_{j}\star f_{j}\star l_{j}\star l)\geq{\sf
HT}(f_{j})$. It remains to show that $m\star m_{j}\star f_{j}\star l_{j}\star
l$ has a reductive standard representation in terms of $F$. First we show that
${\sf HT}(m\star m_{j}\star{\sf HT}(f_{j})\star l_{j}\star l)\geq{\sf
HT}(f_{j})$. We know $m_{j}\star{\sf HT}(f_{j})\star l_{j}\succeq{\sf
HT}(m_{j}\star{\sf HT}(f_{j})\star l_{j})={\sf HT}(m_{j}\star f_{j}\star
l_{j})$515151Notice that $m_{j}\star{\sf HT}(f_{j})\star l_{j}$ can be a
polynomial and hence we cannot conclude $m_{j}\star{\sf HT}(f_{j})\star
l_{j}={\sf HT}(m_{j}\star{\sf HT}(f_{j})\star l_{j})$. and hence ${\sf
HT}(m\star m_{j}\star{\sf HT}(f_{j})\star l_{j}\star l)={\sf HT}(m\star{\sf
HT}(m_{j}\star f_{j}\star l_{j})\star l)={\sf HT}(m\star m_{j}\star f_{j}\star
l_{j}\star l)\geq{\sf HT}(f_{j})$. Now in case $m\star m_{j},l_{j}\star
l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ we are done as then $(m_{j}\star m)\star
f_{j}\star(l_{j}\star l)$ is a reductive standard representation in terms of
$F$.
Hence let us assume $m\star m_{j}=\sum_{i=1}^{k_{1}}\tilde{m}_{i}$,
$l_{j}\star l=\sum_{i^{\prime}=1}^{k_{1}^{\prime}}\tilde{l}_{i^{\prime}}$,
$\tilde{m}_{i},\tilde{l}_{i^{\prime}}\in{\sf M}({\cal F}_{{\mathbb{K}}})$. Let
${\sf T}(f_{j})=\\{t_{1},\ldots,t_{w}\\}$ with $t_{1}\succ t_{i}$, $2\leq
i\leq w$, i.e. $t_{1}={\sf HT}(f_{j})$. As ${\sf HT}(m_{j}\star{\sf
HT}(f_{j})\star l_{j})\geq{\sf HT}(f_{j})\succ t_{p}$, $2\leq p\leq w$, again
by Definition 4.4.7 we can conclude ${\sf HT}(m_{j}\star{\sf HT}(f_{j})\star
l_{j})\succ m_{j}\star t_{p}\star l_{j}\succeq{\sf HT}(m_{j}\star t_{p}\star
l_{j})$, and $m_{j}\star{\sf HT}(f_{j})\star
l_{j}\succ\sum_{p=2}^{w}m_{j}\star t_{p}\star l_{j}$. Then for each $s_{i}$,
$2\leq i\leq l$ there exists $t_{q}\in{\sf T}(f_{1})$ such that $s_{i}\in{\sf
supp}(m_{j}\star t_{q}\star l_{j})$. Since ${\sf HT}(p)\succ s_{i}$ and even
${\sf HT}(p)\succeq m_{j}\star t_{q}\star l_{j}$ we find that either ${\sf
HT}(m\star p\star l)\succeq{\sf HT}(m\star(m_{j}\star t_{q}\star l_{j})\star
l)={\sf HT}((m\star m_{j})\star t_{q}\star(l_{j}\star l))$ in case ${\sf
HT}(m_{j}\star t_{q}\star l_{j})={\sf HT}(m_{j}\star f_{j}\star l_{j})$ or
${\sf HT}(m\star p\star l)\succ{\sf HT}(m\star(m_{j}\star t_{q}\star
l_{j})\star l)={\sf HT}((m\star m_{j})\star t_{q}\star(l_{j}\star l))$. Hence
we can conlude $\tilde{m}_{i}\star f_{j}\star\tilde{l}_{i^{\prime}}\preceq{\sf
HT}(m\star p\star l)$, $1\leq i\leq k_{1}$, $1\leq i^{\prime}\leq
k_{1}^{\prime}$ and for at least one such multiple we get ${\sf
HT}(\tilde{m}_{i}\star f_{1}\star\tilde{l}_{i^{\prime}})={\sf HT}(m\star
m_{j}\star f_{j}\star l_{j}\star l)\geq{\sf HT}(f_{j})$.
It remains to analyze the situation for the function
$(\sum_{i=k+1}^{n}m\star(m_{i}\star f_{i}\star l_{i})\star l$. Again we find
that for all terms $s$ in the $m_{i}\star f_{i}\star l_{i}$, $k+1\leq i\leq
n$, we have ${\sf HT}(p)\succ s$ and we get ${\sf HT}(m\star p\star
l)\succeq{\sf HT}(m\star s\star l)$. Hence all polynomial multiples of the
$f_{i}$ in the representation
$\sum_{i=k+1}^{n}((\sum_{j=1}^{k_{i}}\tilde{m}^{i}_{j})\star
f_{i}\star(\sum_{j=1}^{k^{\prime}_{i}}\tilde{l}^{i}_{j}))$, where $m\star
m_{i}=\sum_{j=1}^{k_{i}}\tilde{m}^{i}_{j}$, $l_{i}\star
l=\sum_{j=1}^{k^{\prime}_{i}}\tilde{l}^{i}_{j}$, are bounded by ${\sf
HT}(m\star p\star l)$.
q.e.d.

Notice that this lemma no longer holds in case we only require ${\sf
HT}(m\star{\sf HT}(p)\star l)={\sf HT}(m\star p\star l)\succeq{\sf HT}(p)$, as
then ${\sf HT}(p)\succ s$ no longer implies ${\sf HT}(m\star p\star
l)\succ{\sf HT}(m\star s\star l)$.

Our standard representations from Definition 4.4.8 are closely related to a
reduction relation based on the divisibility of terms as defined in the
context of reductive restrictions of orderings on page 4.4.7.

###### Definition 4.4.17

Let $f,p$ be two non-zero polynomials in ${\cal F}_{{\mathbb{K}}}$. We say $f$
reduces $p$ to $q$ at a monomial $\alpha\cdot t$ in one step, denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q$,
if there exist $m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such that

  1. 1.

$t\in{\sf supp}(p)$ and $p(t)=\alpha$,

  2. 2.

${\sf HT}(m\star{\sf HT}(f)\star l)={\sf HT}(m\star f\star l)=t\geq{\sf
HT}(f)$,

  3. 3.

${\sf HM}(m\star f\star l)=\alpha\cdot t$, and

  4. 4.

$q=p-m\star f\star l$.

We write
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}$
if there is a polynomial $q$ as defined above and $p$ is then called reducible
by $f$. Further, we can define
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$},\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}\,$}$
and $\,\stackrel{{\scriptstyle n}}{{\longrightarrow}}\\!\\!\mbox{}\,$ as
usual. Reduction by a set $F\subseteq{\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$
is denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q$
and abbreviates
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q$
for some $f\in F$. $\diamond$

Due to the fact that the coefficients lie in a field, again if for some terms
$w_{1},w_{2}\in{\cal T}$ we have ${\sf HT}(w_{1}\star f\star w_{2})={\sf
HT}(w_{1}\star{\sf HT}(f)\star w_{2})=t\geq{\sf HT}(f)$ this implies
reducibility at the monomial $\alpha\cdot t$.

###### Lemma 4.4.18

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.

  1. 1.

For $p,q\in{\cal F}_{{\mathbb{K}}}$ we have that
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q$
implies $p\succ q$, in particular ${\sf HT}(p)\succeq{\sf HT}(q)$.

  2. 2.

$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$ is
Noetherian.

Proof :

  1. 1.

Assuming that the reduction step takes place at a monomial $\alpha\cdot t$, by
Definition 4.4.17 we know ${\sf HM}(m_{1}\star f\star m_{2})=\alpha\cdot t$
which yields $p\succ p-m_{1}\star f\star m_{2}$ since ${\sf HM}(m_{1}\star
f\star m_{2})\succ{\sf RED}(m_{1}\star f\star m_{2})$.

  2. 2.

This follows directly from 1. as the ordering $\succeq$ on ${\cal T}$ is well-
founded (compare Lemma 4.2.3).

q.e.d.

The next lemma shows how reduction sequences and reductive standard
representations are related.

###### Lemma 4.4.19

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $p$ a non-
zero polynomial in ${\cal F}_{{\mathbb{K}}}$. Then
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$
implies that $p$ has a reductive standard representation in terms of $F$.

Proof :
This follows directly by adding up the polynomials used in the reduction steps
occurring in the reduction sequence
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
q.e.d.

If
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q$,
then $p$ has a reductive standard representation in terms of $F\cup\\{q\\}$,
especially $p-q$ has one in terms of $F$.

As stated before an analogon to the Translation Lemma holds.

###### Lemma 4.4.20

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}$ and $p,q,h$
polynomials in ${\cal F}_{{\mathbb{K}}}$.

  1. 1.

Let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}h$.
Then there exist $p^{\prime},q^{\prime}\in{\cal F}_{{\mathbb{K}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}p^{\prime}$
and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q^{\prime}$
and $h=p^{\prime}-q^{\prime}$.

  2. 2.

Let $o$ be a normal form of $p-q$ with respect to $F$. Then there exists
$g\in{\cal F}_{{\mathbb{K}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g$
and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g$.

Proof :

  1. 1.

Let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}h$
at the monomial $\alpha\cdot t$, i.e., $h=p-q-m\star f\star l$ for some
$m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such that ${\sf HT}(m\star{\sf
HT}(f)\star l)={\sf HT}(m\star f\star l)=t\geq{\sf HT}(f)$ and ${\sf
HM}(m\star f\star l)=\alpha\cdot t$. We have to distinguish three cases:

    1. (a)

$t\in{\sf supp}(p)$ and $t\in{\sf supp}(q)$: Then we can eliminate the
occurence of $t$ in the respective polynomials by reduction and get
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}p-\alpha_{1}\cdot(m\star
f\star l)=p^{\prime}$,
$q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q-\alpha_{2}\cdot(m\star
f\star l)=q^{\prime}$, where $\alpha_{1}\cdot{\sf HC}(m\star f\star l)$ and
$\alpha_{2}\cdot{\sf HC}(m\star f\star l)$ are the coefficients of $t$ in $p$
respectively $q$. Moreover, $\alpha_{1}\cdot{\sf HC}(m\star f\star
l)-\alpha_{2}\cdot{\sf HC}(m\star f\star l)=\alpha$ and hence
$\alpha_{1}-\alpha_{2}=1$, as ${\sf HC}(m\star f\star l)=\alpha$. This gives
us $p^{\prime}-q^{\prime}=p-\alpha_{1}\cdot(m\star f\star
l)-q+\alpha_{2}\cdot(m\star f\star l)=p-q-(\alpha_{1}-\alpha_{2})\cdot(m\star
f\star l)=p-q-m\star f\star l=h$.

    2. (b)

$t\in{\sf supp}(p)$ and $t\not\in{\sf supp}(q)$: Then we can eliminate the
term $t$ in the polynomial $p$ by right reduction and get
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}p-m\star
f\star l=p^{\prime}$, $q=q^{\prime}$, and, therefore,
$p^{\prime}-q^{\prime}=p-m\star f\star l-q=h$.

    3. (c)

$t\in{\sf supp}(q)$ and $t\not\in{\sf supp}(p)$: Then we can eliminate the
term $t$ in the polynomial $q$ by right reduction and get
$q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q+m\star
f\star l=q^{\prime}$, $p=p^{\prime}$, and, therefore,
$p^{\prime}-q^{\prime}=p-(q+m\star f\star l)=h$.

  2. 2.

We show our claim by induction on $k$, where
$p-q\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$. In the base case $k=0$ there is
nothing to show as then $p=q$. Hence, let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}h\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$. Then by 1. there are
polynomials $p^{\prime},q^{\prime}\in{\cal F}_{{\mathbb{K}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}p^{\prime}$
and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q^{\prime}$
and $h=p^{\prime}-q^{\prime}$. Now the induction hypothesis for
$p^{\prime}-q^{\prime}\mbox{$\,\stackrel{{\scriptstyle
k}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$ yields the existence of a
polynomial $g\in{\cal F}_{{\mathbb{K}}}$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g$
and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g$.

q.e.d.

The essential part of the proof is that reducibility as defined in Definition
4.4.17 is connected to stable divisors of terms and not to coefficients. We
will later see that for function rings over reduction rings, when the
coefficient is also involved in the reduction step, this lemma no longer
holds.

Next we state the definition of Gröbner bases based on the reduction relation.

###### Definition 4.4.21

A subset $G$ of ${\cal F}_{{\mathbb{K}}}$ is called a Gröbner basis (with
respect to the reduction relation
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}\,$) of the ideal
${\mathfrak{i}}={\sf ideal}(G)$, if
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{G}\,$}=\;\;\equiv_{{\mathfrak{i}}}$
and $\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{G}\,$ is
confluent.

Remember the free group ring in Example 4.2.18 where the polynomial
$b+\lambda$ lies in the ideal generated by the polynomial $a+\lambda$. Then of
course $b+\lambda$ also lies in the ideal generated by $a+\lambda$. Unlike in
the case of polynomial rings over fields where for any set of polynomials $F$
we have
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}=\;\;\equiv_{{\sf ideal}(F)}$, here we have $b+\lambda\equiv_{{\sf
ideal}(\\{a+\lambda\\})}0$ but
$b+\lambda\mbox{$\,\,\,\,{\not\\!\\!\\!\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}_{a+\lambda}}\,$}0$.
Hence the first condition of Definition 4.4.21 is again neccessary.

Now by Lemma 4.4.20 and Theorem 3.1.5 weak Gröbner bases are Gröbner bases and
can be characterized as follows:

###### Corollary 4.4.22

Let $G$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.
$G$ is a (weak) Gröbner basis of ${\sf ideal}(G)$ if and only if for every
$g\in{\sf ideal}(G)$ we have
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{G}\,$}o$.

Finally we can characterize Gröbner bases similar to Theorem 2.3.11.

###### Theorem 4.4.23

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$.
Then $F$ is a Gröbner basis of ${\sf ideal}(G)$ if and only if

  1. 1.

for all $f$ in $F$ and for all $m,l$ in ${\sf M}({\cal F}_{{\mathbb{K}}})$ we
have $m\star f\star
l\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
and

  2. 2.

for all $p$ and $q$ in $F$ and every tuple $(t,u_{1},u_{2},v_{1},v_{2})$ in
${\cal C}(p,q)$ and the respective s-polynomial ${\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ we have ${\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.

We will later on prove a stronger version of this theorem.

The importance of Gröbner bases in the classical case stems from the fact that
we only have to check a finite set of s-polynomials for $F$ in order to
decide, whether $F$ is a Gröbner basis. Hence, we are interested in localizing
the test sets in Theorem 4.4.23 – if possible to finite ones.

###### Definition 4.4.24

A set of polynomials $F\subseteq{\cal F}_{{\mathbb{K}}}\backslash\\{o\\}$ is
called weakly saturated, if for all monomials $m,l$ in ${\sf M}({\cal
F}_{{\mathbb{K}}})$ and every polynomial $f\in F$ we have $m\star f\star
l\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
$\diamond$

This of course implies that for a weakly saturated set $F$ and any $m,l\in{\sf
M}({\cal F}_{{\mathbb{K}}})$, $f\in F$ the multiple $m\star f\star l$ has a
reductive standard representation in terms of $F$.

Notice that since the coefficient domain is a field we could restrict
ourselves to multiples with elements of ${\cal T}$. However, as we will later
on allow reduction rings as coefficient domains, we present this more general
definition.

###### Definition 4.4.25

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{0\\}$.
A set ${\sf SAT}(F)\subseteq\\{m\star f\star l\mid f\in F,m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}})\\}$ is called a stable saturator for $F$ if for any $f\in
F$, $m,l\in{\sf M}({\cal F}_{{\mathbb{K}}})$ there exist $s\in{\sf SAT}(F)$,
$m^{\prime},l^{\prime}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ such that $m\star
f\star l=m^{\prime}\star s\star l^{\prime}$, ${\sf HT}(m\star f\star l)={\sf
HT}(m^{\prime}\star{\sf HT}(s)\star l^{\prime})\geq{\sf HT}(s)$.

###### Corollary 4.4.26

Let ${\sf SAT}(F)$ be a stable saturator of a set $F\subseteq{\cal
F}_{{\mathbb{K}}}$. Then for any $f\in F$, $m,l\in{\sf M}({\cal
F}_{{\mathbb{K}}})$ there exists $s\in{\sf SAT}(F)$ such that $m\star f\star
l\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{s}\,$}o$.

###### Lemma 4.4.27

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{0\\}$.
If for all $s\in{\sf SAT}(F)$ we have
$s\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
then for every $m$, $l$ in ${\sf M}({\cal F}_{{\mathbb{K}}})$ and every
polynomial $f$ in $F$ the multiple $m\star f\star l$ has a reductive standard
representation in terms of $F$.

Proof :
This follows immediately from Lemma 4.4.16 and Lemma 4.4.19.
q.e.d.

###### Definition 4.4.28

Let $p$ and $q$ be two non-zero polynomials in ${\cal F}_{{\mathbb{K}}}$. Then
a subset $C\subseteq\\{{\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mid(t,u_{1},u_{2},v_{1},v_{2})\in{\cal
C}_{s}(p,q)\\}$ is called a stable localization for the critical situations if
for every s-polynomial ${\sf spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ related to
a tuple $(t,u_{1},u_{2},v_{1},v_{2})$ in ${\cal C}_{s}(p,q)$ there exists a
polynomial $h\in C$ and monomials $\alpha\cdot w_{1},1\cdot w_{2}\in{\sf
M}({\cal F}_{{\mathbb{K}}})$ such that

  1. 1.

${\sf HT}(h)\leq{\sf HT}({\sf spol}(p,q,t,u_{1},u_{2},v_{1},v_{2}))$,

  2. 2.

${\sf HT}(w_{1}\star h\star w_{2})={\sf HT}(w_{1}\star{\sf HT}(h)\star
w_{2})={\sf HT}({\sf spol}(p,q,t,u_{1},u_{2},v_{1},v_{2}))$,

  3. 3.

${\sf spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})=(\alpha\cdot w_{1})\star h\star
w_{2}$. $\diamond$

The idea behind this definition is to reduce the number of s-polynomials,
which have to be considered when checking for the Gröbner basis property.

###### Corollary 4.4.29

Let $C\subseteq\\{{\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mid(t,u_{1},u_{2},v_{1},v_{2})\in{\cal
C}_{s}(p,q)\\}$ be a stable localization for two polynomials $p,q\in{\cal
F}_{{\mathbb{K}}}$. Then for any s-polynomial ${\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ there exists $h\in C$ such that ${\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{h}\,$}o$.

###### Lemma 4.4.30

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{0\\}$.
If for all $h$ in a stable localization $C\subseteq\\{{\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mid(t,u_{1},u_{2},v_{1},v_{2})\in{\cal
C}_{s}(p,q)\\}$, we have
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
then for every $(t,u_{1},u_{2},v_{1},v_{2})$ in ${\cal C}_{s}(p,q)$ the
s-polynomial ${\sf spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})$ has a reductive
standard representation in terms of $F$.

Proof :
This follows immediately from Lemma 4.4.16 and Lemma 4.4.19.
q.e.d.

###### Theorem 4.4.31

Let $F$ be a set of polynomials in ${\cal F}_{{\mathbb{K}}}\backslash\\{0\\}$.
Then $F$ is a Gröbner basis if and only if

  1. 1.

for all $s$ in ${\sf SAT}(F)$ we have
$s\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
and

  2. 2.

for all $p$ and $q$ in $F$, and every polynomial $h$ in a stable localization
$C\subseteq\\{{\sf
spol}(p,q,t,u_{1},u_{2},v_{1},v_{2})\mid(t,u_{1},u_{2},v_{1},v_{2})\in{\cal
C}(p,q)\\}$, we have
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.

Proof :
In case $F$ is a Gröbner basis by Lemma 4.4.22 all elements of ${\sf
ideal}(F)$ must reduce to zero by $F$. Since the polynomials in the saturator
and the respective localizations of the s-polynomials all belong to the ideal
generated by $F$ we are done.
The converse will be proven by showing that every element in ${\sf ideal}(F)$
has a reductive standard representation in terms of $F$. Now, let
$g=\sum_{j=1}^{n}(\alpha_{j}\cdot w_{j})\star f_{j}\star z_{j}$ be an
arbitrary representation of a non-zero polynomial $g\in{\sf ideal}(F)$ such
that $\alpha_{j}\in{\mathbb{K}}^{*},f_{j}\in F$, and $w_{j},z_{j}\in{\cal T}$.
By the definition of the stable saturator for every multiple $w_{j}\star
f_{j}\star z_{j}$ in this sum we have some $s\in{\sf SAT}(F)$, $m,l\in{\sf
M}({\cal F}_{{\mathbb{K}}})$ such that $w_{j}\star f_{j}\star z_{j}=m\star
s\star l$ and ${\sf HT}(w_{j}\star f_{j}\star z_{j})={\sf HT}(m\star s\star
l)={\sf HT}(m\star{\sf HT}(s)\star l)\geq{\sf HT}(s)$. Since we have
$s\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
by Lemma 4.4.16 we can conclude that each $w_{j}\star f_{j}\star z_{j}$ has a
reductive standard representation in terms of $F$. Therefore, we can assume
that ${\sf HT}(w_{j}\star{\sf HT}(f_{j})\star z_{j})={\sf HT}(w_{j}\star
f_{j}\star z_{j})\geq{\sf HT}(f_{j})$ holds.
Depending on this representation of $g$ and the well-founded total ordering
$\succeq$ on ${\cal T}$ we define $t=\max_{\succeq}\\{{\sf HT}(w_{j}\star
f_{j}\star z_{j})\mid 1\leq j\leq n\\}$ and $K$ as the number of polynomials
$w_{j}\star f_{j}\star z_{j}$ with head term $t$.
Without loss of generality we can assume that the polynomial multiples with
head term $t$ are just $(\alpha_{1}\cdot w_{1})\star f_{1}\star
z_{1},\ldots,(\alpha_{K}\cdot w_{K})\star f_{K}\star z_{K}$. We proceed by
induction on $(t,K)$, where $(t^{\prime},K^{\prime})<(t,K)$ if and only if
$t^{\prime}\prec t$ or $(t^{\prime}=t$ and $K^{\prime}<K)$525252Note that this
ordering is well-founded since $\succ$ is well-founded on ${\cal T}$ and
$K\in{\mathbb{N}}$..
Obviously, $t\succeq{\sf HT}(g)$ must hold. If $K=1$ this gives us $t={\sf
HT}(g)$ and by our assumption our representation is already of the required
form.
Hence let us assume $K>1$, then for the two not necessarily different
polynomials $f_{1},f_{2}$ in the corresponding representation we have $t={\sf
HT}(w_{1}\star{\sf HT}(f_{1})\star z_{1})={\sf HT}(w_{1}\star f_{1}\star
z_{1})={\sf HT}(w_{2}\star f_{2}\star z_{2})={\sf HT}(w_{2}\star{\sf
HT}(f_{2})\star z_{2})$ and $t\geq{\sf HT}(f_{1})$, $t\geq{\sf HT}(f_{2})$.
Then the tuple $(t,w_{1},w_{2},z_{1},z_{2})$ is in ${\cal C}(f_{1},f_{2})$ and
we have a polynomial $h$ in a stable localization $C\subseteq\\{{\sf
spol}(f_{1},f_{2},t,w_{1},w_{2},z_{1},z_{2})\mid(t,w_{1},w_{2},z_{1},z_{2})\in{\cal
C}(f_{1},f_{2})\\}$ and $\alpha\cdot w,1\cdot z\in{\sf M}({\cal
F}_{{\mathbb{K}}})$ such that ${\sf
spol}(f_{1},f_{2},t,w_{1},w_{2},z_{1},z_{2})={\sf HC}(w_{1}\star f_{1}\star
z_{1})^{-1}\cdot w_{1}\star f_{1}\star z_{1}-{\sf HC}(w_{2}\star f_{2}\star
z_{2})^{-1}\cdot w_{2}\star f_{2}\star z_{2}=(\alpha\cdot w)\star h\star z$
and ${\sf HT}({\sf spol}(f_{1},f_{2},t,w_{1},w_{2},z_{1},z_{2})={\sf
HT}(w\star h\star z)={\sf HT}(w\star{\sf HT}(h)\star z)\geq{\sf HT}(h)$.
We will now change our representation of $g$ by using the additional
information on this situation in such a way that for the new representation of
$g$ we either have a smaller maximal term or the occurrences of the term $t$
are decreased by at least 1. Let us assume the s-polynomial is not $o$535353In
case $h=o$, just substitute the empty sum for the right reductive
representation of $h$ in the equations below.. By our assumption,
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$
and by Lemma 4.4.19 $h$ has a reductive standard representation in terms of
$F$. Then by Lemma 4.4.16 the multiple $(\alpha\cdot w)\star h\star z$ again
has a right reductive standard representation in terms of $F$, say
$\sum_{i=1}^{n}m_{i}\star h_{i}\star l_{i}$, where $h_{i}\in F$, and
$m_{i},l_{i}\in{\sf M}({\cal F}_{{\mathbb{K}}})$ and all terms occurring in
this sum are bounded by $t\succ{\sf HT}((\alpha\cdot w)\star h\star z)$. This
gives us:

$\displaystyle(\alpha_{1}\cdot w_{1})\star f_{1}\star z_{1}+(\alpha_{2}\cdot
w_{2})\star f_{2}\star z_{2}$ (4.7) $\displaystyle=$
$\displaystyle(\alpha_{1}\cdot w_{1})\star f_{1}\star
z_{1}+\underbrace{(\alpha^{\prime}_{2}\cdot\beta_{1}\cdot w_{1})\star
f_{1}\star z_{1}-(\alpha^{\prime}_{2}\cdot\beta_{1}\cdot w_{1})\star
f_{1}\star z_{1}}_{=\,0}$
$\displaystyle+\underbrace{(\alpha^{\prime}_{2}\cdot\beta_{2}}_{=\alpha_{2}}\cdot
w_{2})\star f_{2}\star z_{2}$ $\displaystyle=$
$\displaystyle((\alpha_{1}+\alpha^{\prime}_{2}\cdot\beta_{1})\cdot w_{1})\star
f_{1}\star z_{1}-\alpha^{\prime}_{2}\cdot\underbrace{((\beta_{1}\cdot
w_{1})\star f_{1}\star z_{1}-(\beta_{2}\cdot w_{2})\star f_{2}\star
z_{2})}_{=\,(\alpha\cdot w)\star h\star z}$ $\displaystyle=$
$\displaystyle((\alpha_{1}+\alpha^{\prime}_{2}\cdot\beta_{1})\cdot w_{1})\star
f_{1}\star z_{1}-\alpha^{\prime}_{2}\cdot(\sum_{i=1}^{n}m_{i}\star h_{i}\star
l_{i})$

where $\beta_{1}={\sf HC}(w_{1}\star f_{1}\star z_{1})^{-1}$, $\beta_{2}={\sf
HC}(w_{2}\star f_{2}\star z_{2})^{-1}$ and
$\alpha^{\prime}_{2}\cdot\beta_{2}=\alpha_{2}$. By substituting (4.7) in our
representation of $g$ the representation becomes smaller.
q.e.d.

Obviously this theorem states a criterion for when a set is a Gröbner basis.
As in the case of completion procedures such as the Knuth-Bendix procedure or
Buchberger’s algorithm, elements from these test sets which do not reduce to
zero can be added to the set being tested, to gradually describe a not
necessarily finite Gröbner basis. Of course in order to get a computable
completion procedure certain assumptions on the test sets have to be made,
e.g. they should themselves be recursively enumerable, and normal forms with
respect to finite sets have to be computable. The examples from page 4.2.1 can
also be studied with respect to two-sided ideals. For polynomial rings, skew-
polynomial rings commutative monoid rings and commutative respectively poly-
cyclic group rings finite Gröbner bases can be computed in the respective
setting.

####  4.4.2 Function Rings over Reduction Rings

The situation becomes more complicated if ${\sf R}$ is not a field.

Let ${\sf R}$ be a non-commutative ring with a reduction relation
$\Longrightarrow_{B}$ associated with subsets $B\subseteq{\sf R}$ as described
in Section 3.1.

When following the path of linking special standard representations and
reduction relations we get the same results as in Section 4.2.2, i.e., such
representations naturally arise from the respective reduction relations. Hence
we proceed by studying a special reduction relation which subsumes the two
reduction relations presented for one-sided ideals in function rings over
reduction rings. As before for our ordering $>_{{\sf R}}$ on ${\sf R}$ we
require: for $\alpha,\beta\in{\sf R}$, $\alpha>_{{\sf R}}\beta$ if and only if
there exists a finite set $B\subseteq{\sf R}$ such that
$\alpha\mbox{$\,\stackrel{{\scriptstyle+}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta$.
This ordering will ensure that the reduction relation on ${\cal F}$ is
terminating. The reduction relation on ${\sf R}$ can be used to define various
reduction relations on the function ring. Here we want to present a reduction
relation which in some sense is based on the “divisibility” of the term to be
reduced by the head term of the polynomial used for reduction.

###### Definition 4.4.32

Let $f,p$ be two non-zero polynomials in ${\cal F}$. We say $f$ reduces $p$ to
$q$ at a monomial $\alpha\cdot t$ in one step, denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q$,
if there exist monomials $m,l\in{\sf M}({\cal F})$ such that

  1. 1.

$t\in{\sf supp}(p)$ and $p(t)=\alpha$,

  2. 2.

${\sf HT}(m\star{\sf HT}(f)\star l)={\sf HT}(m\star f\star l)=t\geq{\sf
HT}(f)$,

  3. 3.

$\alpha\Longrightarrow_{{\sf HC}(m\star f\star l)}\beta$, with545454Remember
that by Axiom (A2) for reduction rings $\alpha\Longrightarrow_{\gamma}\beta$
implies $\alpha-\beta\in{\sf ideal}(\gamma)$ and hence
$\alpha=\sum_{i=1}^{k}\gamma_{i}\cdot\gamma\cdot\delta_{i}+\beta$,
$\gamma_{i},\delta_{i}\in{\sf R}$. $\alpha=\sum_{i=1}^{k}\gamma_{i}\cdot{\sf
HC}(m\star f\star l)\cdot\delta_{i}+\beta$ for some
$\beta,\gamma_{i},\delta_{i}\in{\sf R}$, $1\leq i\leq k$, and

  4. 4.

$q=p-\sum_{i=1}^{k}\gamma_{i}\cdot m\star f\star l\cdot\delta_{i}$.

We write
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}$
if there is a polynomial $q$ as defined above and $p$ is then called reducible
by $f$. Further, we can define
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$},\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}\,$}$
and $\,\stackrel{{\scriptstyle n}}{{\longrightarrow}}\\!\\!\mbox{}\,$ as
usual. Reduction by a set $F\subseteq{\cal F}\backslash\\{o\\}$ is denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q$
and abbreviates
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}q$
for some $f\in F$. $\diamond$

By specializing item 3. of this definition to

$3.~{}\alpha\Longrightarrow_{{\sf HC}(m\star f\star l)}\mbox{ such that
}\alpha={\sf HC}(m\star f\star l)$

we get an analogon to Definition 4.2.43. Similarly, specializing 3. to

$3.~{}\alpha\Longrightarrow_{{\sf HC}(m\star f\star l)}\beta\mbox{ such that
}{\sf HC}(m\star f\star l)+\beta$

gives us an analogon to Definition 4.2.53.

Reviewing Example 4.2.54 we find that the reduction relation is not
terminating when using infinite sets of polynomials for reduction. But for
finite sets we get the following analogon of Lemma 4.2.55.

###### Lemma 4.4.33

Let $F$ be a finite set of polynomials in ${\cal F}\backslash\\{o\\}$.

  1. 1.

For $p,q\in{\cal F}$,
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}q$
implies $p\succ q$, in particular ${\sf HT}(p)\succeq{\sf HT}(q)$.

  2. 2.

$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$ is
Noetherian.

Proof :

  1. 1.

Assuming that the reduction step takes place at a monomial $\alpha\cdot t$, by
Definition 4.4.32 we know ${\sf HM}(p-\sum_{i=1}^{k}\gamma_{i}\cdot m_{1}\star
f\star m_{2}\cdot\delta_{i})=\beta\cdot t$ which yields $p\succ
p-\sum_{i=1}^{k}\gamma_{i}\cdot m_{1}\star f\star m_{2}\cdot\delta_{i}$ since
$\alpha>_{{\sf R}}\beta$.

  2. 2.

This follows from 1. and Axiom (A1) as long as only finite sets of polynomials
are involved.

q.e.d.

As for the one-sided case a Translation Lemma does not hold for this reduction
relation. Hence we have to distinguish between weak Gröbner bases and Gröbner
bases.

###### Definition 4.4.34

A set $F\subseteq{\cal F}\backslash\\{o\\}$ is called a weak Gröbner basis of
${\sf ideal}(F)$ if for all $g\in{\sf ideal}(F)$ we have
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
$\diamond$

Now as for one-sided weak Gröbner bases, weak Gröbner bases allow special
representations of the polynomials in the ideal they generate.

###### Corollary 4.4.35

Let $F$ be a set of polynomials in ${\cal F}$ and $g$ a non-zero polynomial in
${\sf ideal}(F)$ such that
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
Then $g$ has a representation of the form

$g=\sum_{i=1}^{n}m_{i}\star f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf
M}({\cal F}),n\in{\mathbb{N}}$

such that ${\sf HT}(g)={\sf HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})={\sf
HT}(m_{i}\star f_{i}\star l_{i})\geq{\sf HT}(f_{i})$ for $1\leq i\leq k$, and
${\sf HT}(g)\succ{\sf HT}(m_{i}\star f_{i}\star l_{i})$ for all $k+1\leq i\leq
n$.

Proof :
We show our claim by induction on $n$ where $g\mbox{$\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$. If $n=0$ we are done. Else let
$g\mbox{$\,\stackrel{{\scriptstyle
1}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g_{1}\mbox{$\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$. In case the reduction step
takes place at the head monomial, there exists a polynomial $f\in F$ and
monomial $m,l\in{\sf M}({\cal F})$ such that ${\sf HT}(m\star{\sf HT}(f)\star
l)={\sf HT}(m\star f\star l)={\sf HT}(g)\geq{\sf HT}(f)$ and ${\sf
HC}(g)\Longrightarrow_{{\sf HC}(m\star f\star l)}\beta$ with ${\sf
HC}(g)\Longrightarrow_{{\sf HC}(m\star f\star l)}\beta$ with ${\sf
HC}(g)=\beta+\sum_{i=1}^{k}\gamma_{i}\cdot{\sf HC}(m\star f\star
l)\cdot\delta_{i}$ for some $\gamma_{i},\delta_{i}\in{\sf R}$, $1\leq i\leq
k$. Moreover the induction hypothesis then is applied to
$g_{1}=g-\sum_{i=1}^{k}\gamma_{i}\cdot m\star f\star l\cdot\delta_{i}$. If the
reduction step takes place at a monomial with term smaller ${\sf HT}(g)$ for
the respective monomial multiple $m\star f\star l$ we immediately get ${\sf
HT}(g)\succ{\sf HT}(m\star f\star l)$ and we can apply our induction
hypothesis to the resulting polynomial $g_{1}$. In both cases we can arrange
the monomial multiples $m\star f\star l$ arising from the reduction steps in
such a way that gives us th desired representation.
q.e.d.

As in Theorem 4.4.15 we can characterize weak Gröbner bases using g- and
m-polynomials instead of s-polynomials.

###### Definition 4.4.36

Let $P=\\{p_{1},\ldots,p_{k}\\}$ be a multiset of (not necessarily different)
polynomials in ${\cal F}$ and $t$ an element in ${\cal T}$ such that there are
$u_{1},\ldots,u_{k},v_{1},\ldots,v_{k}\in{\cal T}$ with ${\sf HT}(u_{i}\star
p_{i}\star v_{i})={\sf HT}(u_{i}\star{\sf HT}(p_{i})\star v_{i})=t$, for all
$1\leq i\leq k$. Further let $\gamma_{i}={\sf HC}(u_{i}\star p_{i}\star
v_{i})$ for $1\leq i\leq k$.
Let $G$ be a (weak) Gröbner basis of $\\{\gamma_{1},\ldots,\gamma_{k}\\}$ with
respect to $\Longrightarrow$ in ${\sf R}$ and

$\alpha=\sum_{i=1}^{k}\sum_{j=1}^{n_{i}}\beta_{i,j}\cdot\gamma_{i}\cdot\delta_{i,j}$

for $\alpha\in G$, $\beta_{i,j},\delta_{i,j}\in{\sf R}$, $1\leq i\leq k$, and
$1\leq j\leq n_{i}$. Then we define the g-polynomials (Gröbner polynomials)
corresponding to $p_{1},\ldots,p_{k}$ and $t$ by setting

$g_{\alpha}=\sum_{i=1}^{k}\sum_{j=1}^{n_{i}}\beta_{i,j}\cdot u_{i}\star
p_{i}\star v_{i}\cdot\delta_{i,j}.$

Notice that ${\sf HM}(g_{\alpha})=\alpha\cdot t$.
We define the m-polynomials (module polynomials) corresponding to $P$ and $t$
as those

$h=\sum_{i=1}^{k}\sum_{j=1}^{n_{i}}\beta_{i,j}\cdot u_{i}\star p_{i}\star
v_{i}\cdot\delta_{i,j}$

where
$\sum_{i=1}^{k}\sum_{j=1}^{n_{i}}\beta_{i,j}\cdot\gamma_{i}\cdot\delta_{i,j}=0$.
Notice that ${\sf HT}(h)\prec t$. $\diamond$

Notice that while we allow the multiplication of two terms to have influence
on the coefficients of the result555555Skew-polynomial rings are a classical
example, see Section 4.2.1. we require that $t\cdot\alpha=\alpha\cdot t$.

Given a set of polynomials $F$, the set of corresponding g- and m-polynomials
is again defined for all possible multisets of polynomials in $F$ and
appropriate terms $t$ as specified by Definition 4.4.36. Notice that given a
finite set of polynomials the corresponding sets of g- and m-polynomials in
general will be infinite.

We can use g- and m-polynomials to characterize special bases in function
rings over reduction rings satisfying Axiom (A4) in case we add an additional
condition as before.

###### Theorem 4.4.37

Let $F$ be a finite set of polynomials in ${\cal F}\backslash\\{o\\}$ where
the reduction ring satisfies (A4). Then $F$ is a weak Gröbner basis if and
only if

  1. 1.

for all $f$ in $F$ and for all $m,l$ in ${\sf M}({\cal F})$ we have $m\star
f\star
l\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
and

  2. 2.

all g- and all m-polynomials corresponding to $F$ as specified in Definition
4.4.36 reduce to zero using $F$.

Proof :
In case $F$ is a weak Gröbner basis, since the multiples $m\star f\star l$ as
well as the respective g- and m-polynomials are all elements of ${\sf
ideal}(F)$ they must reduce to zero using $F$.
The converse will be proven by showing that every element in ${\sf ideal}(F)$
is reducible by $F$. Then as $g\in{\sf ideal}(F)$ and
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}g^{\prime}$
implies $g^{\prime}\in{\sf ideal}(F)$ we have
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
Notice that this only holds in case the reduction relation
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$ is
Noetherian. This follows as by our assumption $F$ is finite.
Let $g\in{\sf ideal}(F)$ have a representation in terms of $F$ of the
following form: $g=\sum_{j=1}^{n}m_{j}\star f_{j}\star l_{j}$, $f_{j}\in F$
and $m_{j},l_{j}\in{\sf M}({\cal F})$. Depending on this representation of $g$
and the well-founded total ordering $\succeq$ on ${\cal T}$ we define
$t=\max_{\succeq}\\{{\sf HT}(m_{j}\star f_{j}\star l_{j})\mid 1\leq j\leq
n\\}$ and $K$ as the number of polynomials $m_{j}\star f_{j}\star l_{j}$ with
head term $t$. We show our claim by induction on $(t,K)$, where
$(t^{\prime},K^{\prime})<(t,K)$ if and only if $t^{\prime}\prec t$ or
$(t^{\prime}=t$ and $K^{\prime}<K)$.
Since by our first assumption every multiple $m_{j}\star f_{j}\star l_{j}$ in
this sum reduces to zero using $F$ and hence has a representation as described
in Corollary 4.4.35 we can assume that ${\sf HT}(m_{j}\star{\sf
HT}(f_{j})\star l_{j})={\sf HT}(m_{j}\star f_{j}\star l_{j})\geq{\sf
HT}(f_{j})$ holds. Without loss of generality we can assume that the
polynomial multiples with head term $t$ are just $m_{1}\star f_{1}\star
l_{1},\ldots,m_{K}\star f_{K}\star l_{K}$.
Obviously, $t\succeq{\sf HT}(g)={\sf HT}(m_{1}\star{\sf HT}(f_{1})\star
l_{1})\geq{\sf HT}(f_{1})$ must hold. If $K=1$ this gives us $t={\sf HT}(g)$
and even ${\sf HM}(g)={\sf HM}(m_{1}\star f_{1}\star l_{1})$, implying that
$g$ is reducible at ${\sf HM}(g)$ by $f_{1}$.
Hence let us assume $K>1$.
First let $\sum_{j=1}^{K}{\sf HM}(m_{j}\star f_{j}\star l_{j})=o$. Then there
is a m-polynomial $h$, corresponding to the polynomials $f_{1},\ldots,f_{K}$
and the term $t$ such that $\sum_{j=1}^{K}l_{j}\star f_{j}\star m_{j}=h$. We
will now change our representation of $g$ by using the additional information
on this m-polynomial in such a way that for the new representation of $g$ we
have a smaller maximal term. Let us assume the m-polynomial is not $o$565656In
case $h=o$, just substitute the empty sum for the reductive representation of
$h$ in the equations below.. By our assumption, $h$ is reducible to zero using
$F$ and hence has a representation with respect to $F$ as described in
Corollary 4.4.35, say
$\sum_{i=1}^{n}\tilde{m}_{i}\star\tilde{f}_{i}\star\tilde{l}_{i}$, where
$\tilde{f}_{i}\in F$, $\tilde{m}_{i},\tilde{l}_{i}\in{\sf M}({\cal F})$ and
all terms occurring in the sum are bounded by $t\succ{\sf HT}(h)$. Hence
replacing the sum $\sum_{j=1}^{K}m_{j}\star f_{j}\star l_{j}$ by
$\sum_{i=1}^{n}\tilde{m}_{i}\star\tilde{f}_{i}\star\tilde{l}_{i}$ gives us a
smaller representation of $g$.
Hence let us assume $\sum_{j=1}^{K}{\sf HM}(m_{j}\star f_{j}\star l_{j})\neq
0$. Then we have ${\sf HT}(m_{1}\star f_{1}\star l_{1}+\ldots+m_{K}\star
f_{K}\star l_{K})=t={\sf HT}(g)$, ${\sf HC}(g)={\sf HC}(m_{1}\star f_{1}\star
l_{1}+\ldots+m_{K}\star f_{K}\star l_{K})\in{\sf ideal}_{r}(\\{{\sf
HC}(m_{1}\star f_{1}\star l_{1}),\ldots,{\sf HC}(m_{K}\star f_{K}\star
l_{K})\\})$ and even ${\sf HM}(m_{1}\star f_{1}\star l_{1}+\ldots+m_{K}\star
f_{K}\star l_{K})={\sf HM}(g)$. Hence ${\sf HC}(g)$ is
$\Longrightarrow$-reducible by $\alpha$, $\alpha\in G$, $G$¡a (weak) right
Gröbner basis of ${\sf ideal}_{r}(\\{{\sf HC}(m_{1}\star f_{1}\star
l_{1}),\ldots,{\sf HC}(m_{K}\star f_{K}\star l_{K})\\})$ in ${\sf R}$ with
respect to the reduction relation $\Longrightarrow$. Let $g_{\alpha}$ be the
respective g-polynomial corresponding to $\alpha$. Then we know that
$g_{\alpha}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
Moreover, we know that the head monomial of $g_{\alpha}$ is reducible by some
polynomial $f\in F$ and we assume ${\sf HT}(g_{\alpha})={\sf HT}(m\star{\sf
HT}(f)\star l)={\sf HT}(m\star f\star l)\geq{\sf HT}(f)$ and ${\sf
HC}(g_{\alpha})\Longrightarrow_{{\sf HC}(m\star f\star l)}$. Then, as ${\sf
HC}(g)$ is $\Longrightarrow$-reducible by ${\sf HC}(g_{\alpha})$, ${\sf
HC}(g_{\alpha})$ is $\Longrightarrow$-reducible to zero and (A4) holds, the
head monomial of $g$ is also reducible by some $f^{\prime}\in F$ and we are
done.
q.e.d.

Of course this theorem is still true for infinite $F$ if we can show that for
the respective function ring the reduction relation is terminating.

Now the question arises when the critical situations in this characterization
can be localized to subsets of the respective sets. Reviewing the Proof of
Theorem 4.4.31 we find that Lemma 4.4.16 is central as it describes when
multiples of polynomials which have a reductive standard representation in
terms of some set $F$ again have such a representation. As before, this does
not hold for function rings over reduction rings in general. We have stated
that it is not natural to link right reduction as defined in Definition 4.4.32
to special standard representations. Hence, to give localizations of Theorem
4.4.37 another property for ${\cal F}$ is sufficient:

###### Definition 4.4.38

A set $C\subset S\subseteq{\cal F}$ is called a stable localization of $S$ if
for every $g\in S$ there exists $f\in C$ such that
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}o$.
$\diamond$

In case ${\cal F}$ and
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}\,$ allow such
stable localizations, we can rephrase Theorem 4.4.37 as follows:

###### Theorem 4.4.39

Let $F$ be a finite set of polynomials in ${\cal F}\backslash\\{o\\}$ where
the reduction ring satisfies (A4). Then $F$ is a weak Gröbner basis of ${\sf
ideal}(F)$ if and only if

  1. 1.

for all $s$ in a stable localization of $\\{m\star f\star l\mid f\in{\cal
F},m,l\in{\sf M}({\cal F})\\}$ we have
$s\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
and

  2. 2.

for all $h$ in a stable localization of the g- and m-polynomials corresponding
to $F$ as specified in Definition 4.4.36 we have
$h\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.

We have stated that for arbitrary reduction relations in ${\cal F}$ it is not
natural to link them to special standard representations. Still, when proving
Theorem 4.4.39, we will find that in order to change the representation of an
arbitrary ideal element, Definition 4.4.38 is not enough to ensure
reducibility. However, we can substitute the critical situation using an
analogon of Lemma 4.4.16, which while not related to reducibility in this case
will still be sufficient to make the representation smaller.

###### Lemma 4.4.40

Let $F\subseteq{\cal F}\backslash\\{o\\}$ and $f$, $p$ non-zero polynomials in
${\cal F}$. If
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}o$
and
$f\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$,
then $p$ has a standard representation of the form

$p=\sum_{i=1}^{n}m_{i}\star f_{i}\star l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf
M}({\cal F}),n\in{\mathbb{N}}$

such that ${\sf HT}(p)={\sf HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})={\sf
HT}(m_{i}\star f_{i}\star l_{i})\geq{\sf HT}(f_{i})$ for $1\leq i\leq k$ and
${\sf HT}(p)\succ{\sf HT}(m_{i}\star f_{i}\star l_{i})$ for all $k+1\leq i\leq
n$.

Proof :
If
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{f}\,$}o$
then $p=\sum_{j=1}^{s}\gamma_{j}\cdot m^{\prime}\star f\star
l^{\prime}\cdot\delta_{j}$ with $m^{\prime},l^{\prime}\in{\sf M}({\cal F})$,
$\gamma_{j},\delta_{j}\in{\sf R}$, and ${\sf HT}(p)={\sf HT}(m\star{\sf
HT}(f)\star l)={\sf HT}(m\star f\star l)\geq{\sf HT}(f)$. Similarly
$f\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$
implies575757Notice that in this representation we write the products of the
form $\gamma\cdot m$ respectively $l\cdot\delta$ arising in the reduction
steps as simple monomials. $f=\sum_{i=1}^{n}m_{i}\star f_{i}\star
l_{i},f_{i}\in F,m_{i},l_{i}\in{\sf M}({\cal F}),n\in{\mathbb{N}}$ such that
${\sf HT}(f)={\sf HT}(m_{i}\star{\sf HT}(f_{i})\star l_{i})={\sf
HT}(m_{i}\star f_{i}\star l_{i})\geq{\sf HT}(f_{i})$, $1\leq i\leq k$, and
${\sf HT}(f)\succ{\sf HT}(m_{i}\star f_{i}\star l_{i})$ for all $k+1\leq i\leq
n$.
We show our claim for all multiples with $\gamma_{j}\cdot m^{\prime}$ and
$l^{\prime}\cdot\delta_{j}$ for $1\leq j\leq s$. Let $m=\gamma_{j}\star
m^{\prime}$ and $l=l^{\prime}\cdot\delta_{j}$ and let us analyze $m\star
m_{i}\star f_{i}\star l_{i}\star l$ with ${\sf HT}(m_{i}\star f_{i}\star
l_{i})={\sf HT}(f)$, $1\leq i\leq k$. Let ${\sf T}(m_{i}\star f_{i}\star
l_{i})=\\{s_{1}^{i},\ldots,s_{w_{i}}^{i}\\}$ with $s_{1}^{i}\succ s_{j}^{i}$,
$2\leq j\leq w_{i}$, i.e. $s_{1}^{i}={\sf HT}(m_{i}\star f_{i}\star
l_{i})={\sf HT}(p)$. Hence $m\star{\sf HT}(p)\star l=m\star s_{1}^{i}\star
l\geq{\sf HT}(p)=s_{1}^{i}$ and as $s_{1}^{i}\succ s_{j}^{i}$, $2\leq j\leq
w_{i}$, by Definition 4.4.7 we can conclude ${\sf HT}(m\star{\sf HT}(p)\star
l)={\sf HT}(m\star s_{1}^{i}\star l)\succ m\star s_{j}^{i}\star l\succeq{\sf
HT}(m\star s_{j}^{i}\star l)$ for $2\leq j\leq w_{i}$. This implies ${\sf
HT}(m\star{\sf HT}(m_{i}\star f_{i}\star l_{i})\star l)={\sf HT}(m\star
m_{i}\star f_{i}\star l_{i}\star l)$ Hence we get

$\displaystyle{\sf HT}(m\star f\star l)$ $\displaystyle=$ $\displaystyle{\sf
HT}(m\star{\sf HT}(f)\star l)$ $\displaystyle=$ $\displaystyle{\sf
HT}(m\star{\sf HT}(m_{i}\star f_{i}\star l_{i})\star l),\mbox{ as }{\sf
HT}(p)={\sf HT}(m_{i}\star f_{i}\star l_{i})$ $\displaystyle=$
$\displaystyle{\sf HT}(m\star m_{i}\star f_{i}\star l_{i}\star l)$

and since ${\sf HT}(m\star f\star l)\geq{\sf HT}(f)\geq{\sf HT}(f_{i})$ we can
conclude ${\sf HT}(m\star m_{i}\star f_{i}\star l_{i}\star l)\geq{\sf
HT}(f_{i})$. It remains to show that $m\star(m_{i}\star f_{i}\star l_{i})\star
l=(m\star m_{i})\star f_{i}\star(l_{i}\star l)$ has representations of the
desired form in terms of $F$. First we show that ${\sf HT}((m\star
m_{i}\star{\sf HT}(f_{i})\star l_{i}\star l)\geq{\sf HT}(f_{i})$. We know
$m_{i}\star{\sf HT}(f_{i})\star l_{i}\succeq{\sf HT}(m_{i}\star{\sf
HT}(f_{i})\star l_{i})={\sf HT}(m_{i}\star f_{i}\star l_{i})$ and hence ${\sf
HT}(m\star m_{i}\star{\sf HT}(f_{i})\star l_{i}\star l)={\sf HT}(m\star{\sf
HT}(m_{i}\star f_{i}\star l_{i})\star l)={\sf HT}(m\star m_{i}\star f_{i}\star
l_{i}\star l)\geq{\sf HT}(f_{i})$.
Now in case $m\star m_{i},l_{i}\star l\in{\sf M}({\cal F})$ we are done as
then $(m\star m_{i})\star f_{i}\star(l_{i}\star l)$ is a representation of the
desired form.
Hence let us assume $m\star
m_{i}=\sum_{j=1}^{k_{i}}\tilde{m}^{i}_{j}$,$l_{i}\star
l=\sum_{j^{\prime}=1}^{k^{\prime}_{i}}\tilde{l}^{i}_{j}$
$\tilde{m}^{i}_{j},\tilde{l}^{i}_{j^{\prime}}\in{\sf M}({\cal F})$. Let ${\sf
T}(f_{i})=\\{t^{i}_{1},\ldots,t^{i}_{w}\\}$ with $t^{i}_{1}\succ t^{i}_{j}$,
$2\leq j\leq w$, i.e. $t^{i}_{1}={\sf HT}(f_{i})$. As ${\sf HT}(m_{i}\star{\sf
HT}(f_{i})\star l_{i})\geq{\sf HT}(f_{i})\succ t_{j}$, $2\leq j\leq w$, again
by Definition 4.4.7 we can conclude that ${\sf HT}(m_{i}\star{\sf
HT}(f_{i})\star l_{i})\succ m_{i}\star t^{i}_{j}\star l_{i}\succeq{\sf
HT}(m_{i}\star t^{i}_{j}\star l_{i})$, $2\leq j\leq l$, and $m_{i}\star{\sf
HT}(f_{i})\star l_{i}\succ\sum_{j=2}^{w}m_{i}\star t^{i}_{j}\star l_{i}$. Then
for each $s^{i}_{j}$, $2\leq j\leq w_{i}$, there exists
$t^{i}_{j^{\prime}}\in{\sf T}(f_{i})$ such that $s^{i}_{j}\in{\sf
supp}(m_{i}\star t^{i}_{j^{\prime}}\star l_{i})$. Since ${\sf HT}(f)\succ
s^{i}_{j}$ and even ${\sf HT}(f)\succ m_{i}\star t^{i}_{j^{\prime}}\star
l_{i}$ we find that either ${\sf HT}(m\star f\star l)\succeq{\sf
HT}(m\star(m_{i}\star t^{i}_{j^{\prime}}\star l_{i})\star l)={\sf HT}((m\star
m_{i})\star t^{i}_{j^{\prime}}\star(l_{i}\star l))$ in case ${\sf
HT}(m_{i}\star t^{i}_{j^{\prime}}\star l_{i})={\sf HT}(m_{i}\star f_{1}\star
l_{i})$ or ${\sf HT}(m\star f\star l)\succ m\star(m_{i}\star
t^{i}_{j^{\prime}}\star l_{i})\star l=(m\star m_{i})\star
t^{i}_{j^{\prime}}\star(l_{i}\star l)$. Hence we can conclude
$\tilde{m}^{i}_{j}\star f_{i}\star\tilde{l}^{i}_{j^{\prime}}\preceq{\sf
HT}(m\star f\star l)$, $1\leq j\leq k_{i}$, $1\leq j^{\prime}\leq K_{i}$ and
for at least one $\tilde{m}^{i}_{j}$, $\tilde{l}^{i}_{j^{\prime}}$ we get
${\sf HT}(\tilde{m}^{i}_{j}\star f_{i}\star\tilde{l}^{i}_{j^{\prime}})={\sf
HT}(m\star m_{i}\star f_{i}\star l_{i}\star l)\geq{\sf HT}(f_{i})$.
It remains to analyze the situation for the functions
$(\sum_{i=k+1}^{n}m\star(m_{i}\star f_{i}\star l_{i})\star l$. Again we find
that for all terms $s$ in the $m_{i}\star f_{i}\star l_{i}$, $k+1\leq i\leq
n$, we have ${\sf HT}(f)\succeq s$ and we get ${\sf HT}(m\star f\star
l)\succeq{\sf HT}(m\star s\star l)$. Hence all polynomial multiples of the
$f_{i}$ in the representation
$\sum_{i=k+1}^{n}(\sum_{j=1}^{k_{i}}\tilde{m}^{i}_{j})\star
f_{i}\star(\sum_{j=1}^{K_{i}}\tilde{l}^{i}_{j^{\prime}})$, where $m\star
m_{i}=\sum_{j=1}^{k_{i}}\tilde{m}^{i}_{j}$, $l_{i}\star
l=\sum_{j=1}^{K_{i}}\tilde{l}^{i}_{j^{\prime}}$, are bounded by ${\sf
HT}(m\star f\star l)$.
q.e.d.

Proof Theorem 4.4.39:
The proof is basically the same as for Theorem 4.4.37. Due to Lemma 4.4.40 we
can substitute the multiples $m_{j}\star f_{j}\star l_{j}$ by appropriate
representations without changing $(t,K)$. Hence, we only have to ensure that
despite testing less polynomials we are able to apply our induction
hypothesis. Taking the notations from the proof of Theorem 4.4.37, let us
first check the situation for m-polynomials.
Let $\sum_{j=1}^{K}{\sf HM}(m_{j}\star f_{j}\star l_{j})=o$. Then by
Definition 4.4.36 there exists a module polynomial $h=\sum_{j=1}^{K}m_{j}\star
f_{j}\star l_{j}$ and by our assumption there is a polynomial $h^{\prime}$ in
the stable localization such that
$h\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{h^{\prime}}\,$}o$.
Moreover,
$h^{\prime}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
Then by Lemma 4.4.40 the m-polynomial $h$ has a standard representations
bounded by $t$. Hence we can change the representation of $g$ by substituting
$h$ by its representation giving us a smaller representation and by our
induction hypothesis $g$ is reducible by $F$ and we are done.
It remains to study the case where $\sum_{j=1}^{K}{\sf HM}(m_{j}\star
f_{j}\star l_{j})\neq 0$. Then we have ${\sf HT}(\sum_{j=1}^{K}m_{j}\star
f_{j}\star l_{j})=t={\sf HT}(g)$, ${\sf HC}(g)={\sf
HC}(\sum_{j=1}^{K}m_{j}\star f_{j}\star l_{j})\in{\sf ideal}(\\{{\sf
HC}(m_{1}\star f_{1}\star l_{1}),\ldots,{\sf HC}(m_{K}\star f_{K}\star
l_{K})\\})$ and even ${\sf HM}(\sum_{j=1}^{K}m_{j}\star f_{j}\star l_{j})={\sf
HM}(g)$. Hence ${\sf HC}(g)$ is $\Longrightarrow$-reducible by $\alpha$,
$\alpha\in G$, $G$ a (weak) Gröbner basis of ${\sf ideal}(\\{{\sf
HC}(m_{1}\star f_{1}\star l_{1}),\ldots,{\sf HC}(m_{K}\star f_{K}\star
l_{K})\\})$ in ${\sf R}$ with respect to the reduction relation
$\Longrightarrow$. Let $g_{\alpha}$ be the respective g-polynomial
corresponding to $\alpha$. Then we know that
$g_{\alpha}\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{g_{\alpha}^{\prime}}\,$}o$
for some $g_{\alpha}^{\prime}$ in the stable localization and
$g_{\alpha}^{\prime}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{F}\,$}o$.
Moreover, we know that the head monomial of $g_{\alpha}^{\prime}$ is reducible
by some polynomial $f\in F$ and we assume ${\sf HT}(g_{\alpha})={\sf
HT}(m\star{\sf HT}(f)\star l)={\sf HT}(m\star f\star l)\geq{\sf HT}(f)$ and
${\sf HC}(g_{\alpha})\Longrightarrow_{{\sf HC}(m\star f\star l)}$. Then, as
${\sf HC}(g)$ is $\Longrightarrow$-reducible by ${\sf HC}(g_{\alpha})$, ${\sf
HC}(g_{\alpha})$ is $\Longrightarrow$-reducible by ${\sf