Gröbner Basis

Theorem

Let $F$ be a finite set of polynomials, $SP(f_{1},f_{2})$ S-polynomial of $f_{1}$ and $f_{2}$, and if $g$ is a polynomial and $RF(g)$ is reduced form of $g$. Then

F is a Gröbner basis $\iff \forall f_{1}, f_{2} \in F (RF(F,SP(f_{1},f_{2}))=0)$.

Proof

The direction "$\Rightarrow$" is easy. Namely, if $f_{1},f_{2}\in F$, then $SP(f_{1}, f_{2})\in Ideal(F )$, i.e. $SP(f_{1},f_{2})\equiv_{F} 0$. By the relation between reduction and congruence this implies that $SP(f_{1},f_{2})\leftrightarrow_{F}^{\ast} 0$. Hence, $RF(F,SP(f_{1},f_{2}))=RF(F,0)=0$ because $F$ is a Gr\"{o}bner basis (and because of the equivalence between the Church-Rosser property and the normal form Church-Rosser property).

For the direction "$\Leftarrow$", by the generalized Newman lemma and the fact that $\rightarrow_{F}\subseteq \succ$ , it suffices to prove local connectibility, i.e. it suffices to prove that under the assumption \[ g_{1}\leftarrow_{F} h \rightarrow_{F} g_{2} \] we have \[ g_{1} \stackrel{\prec h}{\longleftrightarrow^{\ast}_{F}} g_{2}. \] Let $LPP(f)$ is leading power product of $f$. Then by the assumption, there exist $f_{1},f_{2} \in F$ and $t_{1},t_{2} \in S(h)$ with $LPP(f_{1})|t_{1}$ and $LPP(f_{2})|t_{2}$, such that $h \rightarrow_{f_{1},t_{1}} g_{1}$ and $h \rightarrow_{f_{2},t_{2}} g_{2}$.

Now we have three cases.

Case $t_{1}\succ t_{2}$: In this case, \begin{align*} g_{1}=& H(h,t_{1})+0 \cdot t_{1}+B(h,t_{1},t_{2})+C(h,t_{2})\cdot t_{2}\\ &+L(h,t_{2})-C(h,t_{1})\cdot u_{1}\cdot R(f_{1}) \end{align*} and \begin{align*} g_{2}=& H(h,t_{1})+C(h,t_{1})\cdot t_{1}+B(h,t_{1},t_{2})+0 \cdot t_{2}\\ &+L(h,t_{2})-C(h,t_{2})\cdot u_{2}\cdot R(f_{2}) \end{align*} where $u_{1}:=t_{1}/LPP(f_{1}), u_{2}:=t_{2}/LPP(f_{2})$.

Furthermore, \begin{align*} g_{2}\rightarrow_{f_{1}} g_{1,2}:=& H(h,t_{1})+0\cdot t_{1}+B(h,t_{1},t_{2})+0\cdot t_{2}+L(h,t_{2})\\ &-C(h,t_{1})\cdot u_{1}\cdot R(f_{1})-C(h,t_{2})\cdot u_{2}\cdot R(f_{2}) \end{align*}

Now $g_{1}=h-C(h,t_{1})\cdot u_{1}\cdot f_{1}$ and $g_{1,2}=g_{2}-C(h,t_{1})\cdot u_{1}\cdot f_{1}$ and, by assumption, $h\rightarrow_{F} g_{2}$. Hence, by sum semi-compatibility, $g_{1}\downarrow_{\stackrel{\ast}{F}} g_{1,2}$ and, hence, $g_{1} \stackrel{\prec h}{\longleftrightarrow^{\ast}_{F}} g_{2}$. (Note that, in general, $g_{1}\rightarrow_{f_{1}} g_{1,2}$ need not be the case. Why not?)

Case $t_{1}\prec t_{2}$: Analogous.

Case $t:=t_{1}=t_{2}$: In this case, \[ g_{1}=H(h,t)+0\cdot t+L(h,t)-C(h,t)\cdot u_{1}\cdot R(f_{1}) \] and \[ g_{2}=H(h,t)+0\cdot t+L(h,t)-C(h,t)\cdot u_{2}\cdot R(f_{2}). \] Hence, \begin{align*} g_{1}-g_{2} &=-C(h,t)\cdot (u_{1}\cdot R(f_{1})-u_{2}\cdot R(f_{2}))\\ &=-C(h,t)\cdot (u_{1}\cdot f_{1}-u_{2}\cdot f_{2})\\ &=-C(h,t)\cdot v\cdot SP(f_{1},f_{2}), \end{align*} where \[ v:=t/LCM(LPP(f_{1}),LPP(f_{2})). \]

We have assumed that $RF(F,SP(f_{1},f_{2}))=0$, i.e. $SP(f_{1},f_{2})\rightarrow_{\stackrel{\ast}{F}} 0$. Hence,by product compatibility, $g_{1}-g_{2}=-C(h,t)\cdot v\cdot SP(f_{1},f_{2})\rightarrow_{\stackrel{\ast}{F}} 0$. This means that there exists a sequence $p\in P^{\ast}$ such that \begin{equation} \begin{array}{l} \displaystyle p_{1}=g_{1}-g_{2}\nonumber\\ \displaystyle \forall 1 \leq i < |p| \hspace{2mm}(p_{i} \rightarrow_{F} p_{i+1}),\tag{1} \end{array} \end{equation}

and \[ p_{|p|}=0 \]

Furthermore note that, because of $\rightarrow_{F} \subseteq \succ$, \[ \forall 1\leq i <|p| \hspace{2mm}(p_{i}\preceq g_{1}-g_{2}\prec h). \] Thus, by sum semi-compatibility applied to ((1)), \begin{eqnarray} && g_{1}=p_{1}+g_{2},\nonumber\\ && \forall 1\leq i < |p| \hspace{2mm}(p_{i}+g_{2}\downarrow_{\stackrel{\ast}{F}} p_{i+1}+g_{2}),\nonumber\\ && g_{2}=p_{|p|}+g+{2}.\nonumber \end{eqnarray} Also, we have \[ \forall 1\leq i <|p| \hspace{2mm}(p_{i}+g_{2} \prec h) \] because \[ \forall 1\leq i <|p| \hspace{2mm}(H(p_{i}+g_{2},t)=H(h,t) \wedge C(p_{i}+g_{2},t)=0). \] Thus, summarizing, $g_{1} \stackrel{\prec h}{\longleftrightarrow^{\ast}_{F}} g_{2}$ also in this case.

Source of Name

This entry was named for Wolfgang Gröbner.

References

Buchberger, B. (1965): An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German). PhD Thesis,University of Innsbruck, Institute for Mathematics.

Buchberger B. and Winkler F. (1998): Gröbner Bases and Applications, London Mathematical Society Lecture Notes Series, volume 251, Cambridge University Press.

The proofwiki editor Pinkpanther has begun this article but has taken a break on 15 Mar. Reason: Under Construction! Please leave this page to be completed by Pinkpanther. If the page goes uncompleted for one week, feel free to leave a note on Pinkpanther's talk page reminding them to complete the article. If he or she does not get back to you within two days, please feel free to complete the proof yourself.