# Gröbner Basis

## Contents

## Theorem

Let $F$ be a finite set of polynomials.

Let $SP \left({f_1, f_2}\right)$ be the $S$-polynomial of $f_1$ and $f_2$.

Let $g$ be a polynomial.

Let $RF \left({g}\right)$ be the reduced form of $g$.

Then $F$ is a Gröbner basis if and only if:

- $\forall f_1, f_2 \in F \left({RF \left({F, SP \left({f_1, f_2}\right)}\right) = 0}\right)$

## Proof

### Necessary Condition

Let $F$ be a Gröbner basis.

Let $f_1, f_2 \in F$.

Then:

- $SP \left({f_1, f_2}\right) \in Ideal \left({F}\right)$

That is:

- $SP \left({f_1, f_2}\right) \equiv_F 0$

By the relation between reduction and congruence this implies that:

- $SP \left({f_1, f_2}\right) \leftrightarrow_F^* 0$

Hence:

- $RF \left({F, SP \left({f_1, f_2}\right)}\right) = RF \left({F, 0}\right) = 0$

because $F$ is a Gröbner basis (and because of the equivalence between the Church-Rosser property and the normal form Church-Rosser property).

$\Box$

### Sufficient Condition

Let:

- $\forall f_1, f_2 \in F \left({RF \left({F, SP \left({f_1, f_2}\right)}\right) = 0}\right)$

By the generalized Newman lemma and:

- $\gets_F \mathop \subseteq \succ$

it suffices to prove local connectibility.

That is, it suffices to prove that under the assumption:

- $g_1 \to_F h \gets_F g_2$

we have:

- $g_1 \stackrel{\prec h} {\longleftrightarrow^*_F} g_2$

Let $LPP \left({f}\right)$ be the leading power product of $f$.

Then by the assumption, there exist $f_1, f_2 \in F$ and $t_1, t_2 \in S \left({h}\right)$ with:

- $LPP \left({f_1}\right) | t_1$

and:

- $LPP \left({f_2}\right) | 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:

\(\displaystyle g_1\) | \(=\) | \(\displaystyle H \left({h, t_1}\right) + 0 \cdot t_1 + B \left({h, t_1, t_2}\right) + C \left({h, t_2}\right) \cdot t_2\) | |||||||||||

\(\displaystyle \) | \(\) | \(\, \displaystyle + \, \) | \(\displaystyle L \left({h, t_2}\right) - C \left({h, t_1}\right) \cdot u_1 \cdot R \left({f_1}\right)\) |

and:

\(\displaystyle g_2\) | \(=\) | \(\displaystyle H \left({h, t_1}\right) + C \left({h, t_1}\right) \cdot t_1 + B \left({h, t_1, t_2}\right) + 0 \cdot t_2\) | |||||||||||

\(\displaystyle \) | \(\) | \(\, \displaystyle + \, \) | \(\displaystyle L \left({h, t_2}\right) - C \left({h, t_2}\right) \cdot u_2 \cdot R \left({f_2}\right)\) |

where:

- $u_1 := \dfrac {t_1} {LPP \left({f_1}\right)}$

and:

- $u_2 := \dfrac {t_2} {LPP \left({f_1}\right)}$

Furthermore:

\(\displaystyle g_2 \to_{f_1} g_{1, 2}\) | \(=\) | \(\displaystyle H \left({h, t_1}\right) + 0 \cdot t_1 + B \left({h, t_1, t_2}\right) + 0 \cdot t_2 + L \left({h, t_2}\right)\) | |||||||||||

\(\displaystyle \) | \(\) | \(\, \displaystyle - \, \) | \(\displaystyle C \left({h, t_1}\right) \cdot u_1 \cdot R \left({f_1}\right) - C \left({h, t_2}\right) \cdot u_2 \cdot R \left({f_2}\right)\) |

Now:

- $g_1 = h - C \left({h, t_1}\right) \cdot u_1 \cdot f_1$

and:

- $g_{1, 2} = g_2 - C \left({h, t_1}\right) \cdot u_1 \cdot f_1$

and, by assumption:

- $h \to_F g_2$

Hence, by sum semi-compatibility:

- $g_1 \downarrow_{\stackrel{*} {F} } g_{1, 2}$

and hence:

- $g_1 \stackrel{\prec h}{\longleftrightarrow^{*}_F} g_2$

(Note that, in general, $g_1 \to_{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 \left({h, t}\right) + 0 \cdot t + L \left({h, t}\right) - C \left({h, t}\right) \cdot u_1 \cdot R \left({f_1}\right)$

and:

- $g_2 = H \left({h, t}\right) + 0 \cdot t + L \left({h, t}\right) - C \left({h, t}\right) \cdot u_2 \cdot R \left({f_2}\right)$

Hence:

\(\displaystyle g_1 - g_2\) | \(=\) | \(\displaystyle - C \left({h, t}\right) \cdot \left({u_1 \cdot R \left({f_1}\right) - u_2 \cdot R \left({f_2}\right)}\right)\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle - C \left({h, t}\right) \cdot \left({u_1 \cdot f_1 - u_2 \cdot f_2}\right)\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle - C \left({h, t}\right) \cdot v \cdot SP \left({f_1, f_2}\right)\) |

where:

- $v := t / LCM \left({LPP \left({f_1}\right), LPP \left({f_2}\right)}\right)$

We have assumed that:

- $RF \left({F, SP \left({f_1, f_2}\right)}\right) = 0$

That is:

- $SP \left({f_1, f_2}\right) \to_{\stackrel{\ast}{F}} 0$

Hence,by product compatibility:

- $g_1 - g_2 = - C \left({h, t}\right) \cdot v \cdot SP \left({f_1, f_2}\right) \to_{\stackrel{*}{F}} 0$

This means that there exists a sequence $p \in P^{\ast}$ such that:

\(\displaystyle p_1\) | \(=\) | \(\displaystyle g_1 - g_2\) | |||||||||||

\(\text {(1)}: \quad\) | \(\displaystyle \forall 1 \le i < \left\vert{p}\right\vert:\) | \(\) | \(\displaystyle \left({p_i \to_F p_{i + 1} }\right)\) |

and:

- $p_{\left\vert{p}\right\vert} = 0 $

Furthermore note that, because of $\to_F \subseteq \succ$:

- $\forall 1 \le i < \left\vert{p}\right\vert: p_i\preceq g_1 -g_2 \prec h$

Thus, by sum semi-compatibility applied to $(1)$:

- $g_1 = p_1 + g_2$

- $\forall 1 \le i < \left\vert{p}\right\vert: p_i + g_2 \downarrow_{\stackrel{*}{F} } p_{i+1} + g_2$

- $g_2 = p_{\left\vert{p}\right\vert} + g + 2$

Also, we have:

- $\forall 1 \le i < \left\vert{p}\right\vert: p_i + g_2 \prec h$

because:

- $\forall 1 \le i < \left\vert{p}\right\vert: H \left({p_i + g_2, t}\right) = H \left({h, t}\right) \wedge C \left({p_i + g_2, t}\right) = 0$

Thus, summarizing:

- $g_1 \stackrel{\prec h} {\longleftrightarrow^{*}_F} g_2$ also in this case.

## Buchberger's Algorithm

**Input**: a finite set of polynomials $F$

**Output**: $GB \left({F}\right)$, a Gröbner bases of $Ideal \left({F}\right)$

- $Grobner$-$Basis \left({F}\right) := GB \left({F, \left\{ {f_1, f_2}\right\} | f_1, f_2 \in F}\right)$
- $GB \left({F, \varnothing}\right) := F$
- $GB \left({F, \left\{ {f_1, f_2}\right\} \cup B}\right) := \begin{cases} GB \left({F, B}\right) & : h = 0 \\ GB \left({F \cup h, B \cup \left\{ {h, f | f \in F}\right\} }\right) & : \text{otherwise} \end{cases}$

where:

- $h := RF \left({F, SP \left({f_1, f_2}\right)}\right)$

## Source of Name

This entry was named for Wolfgang Gröbner.

## Sources

- 1965: Bruno Buchberger:
*Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal*() (PhD thesis)

- 1970: Bruno Buchberger:
*An Algorithmic Criterion for the Solvability of a System of Algebraic Equations*(*Aequationes Mathematicae***Vol. 4**: pp. 374 – 383)

- 2006: Bruno Buchberger:
*An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal*(*J. Symb. Comput.***Vol. 41**: pp. 471 – 511)

- (translated by Michael P. Abramson from "Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal")