---
tag: YC90FXM4SA
kind: definition
name: Buchberger's algorithm
msc: [13P10, 68W30]
defines: 4RH1D40WG1
uses: [04C5ZBG1WT, 0SDC934R52, E874NARWPV, 007NPQX34K, T8EN3CAEQF, C83KPT47R0, 4G25S7PJ22, 0YKA9J3XEE]
sources:
  - url: https://en.wikipedia.org/wiki/Buchberger's_algorithm
---

## Definition

Let $k$ be a [[field|04C5ZBG1WT]], let $S = k[x_1, \ldots, x_n]$ be the [[polynomial ring|0SDC934R52]], and fix a [[monomial order|E874NARWPV]].
For nonzero $f \in S$, let $\operatorname{LT}(f)$ be its leading term and $\operatorname{LM}(f)$ its leading monomial.
For nonzero $f, g \in S$, let $x^\gamma$ be the [[least common multiple|007NPQX34K]] of $\operatorname{LM}(f)$ and $\operatorname{LM}(g)$; the *S-polynomial* of $f$ and $g$ is
$$S(f, g) = \frac{x^\gamma}{\operatorname{LT}(f)} \, f - \frac{x^\gamma}{\operatorname{LT}(g)} \, g.$$
*Buchberger's algorithm* takes a finite set $F$ of nonzero elements of $S$ and proceeds as follows.

1. Set $G = F$.
2. For each pair $f \ne g$ in $G$, compute the remainder $r$ of $S(f, g)$ under the [[multivariate division algorithm|T8EN3CAEQF]] by $G$, listed in a fixed order.
3. If some such $r$ is nonzero, add all the nonzero remainders to $G$ and go back to step 2.
4. If all such remainders are zero, return $G$.

## Remarks

The algorithm rests on Buchberger's criterion.
Let $G$ be a finite set of generators of an ideal $I$.
Then $G$ is a [[Gröbner basis|C83KPT47R0]] of $I$ if and only if each $S(f, g)$ with $f, g \in G$ has remainder zero on division by $G$.
The algorithm stops for the following reason.
Each pass with a nonzero remainder makes the [[monomial ideal|4G25S7PJ22]] generated by the leading terms of $G$ strictly larger.
An ascending chain of ideals of $S$ is stationary by [[Hilbert's basis theorem|0YKA9J3XEE]].
The output is a Gröbner basis of the ideal generated by $F$.

Example: in $k[x, y]$ with the lexicographic order $x > y$, let $F = \set{x + y, \; x}$.
Then $S(x + y, x) = (x + y) - x = y$, which has remainder $y \ne 0$ on division by $F$, so $y$ is added.
For $G = \set{x + y, x, y}$, one finds $S(x + y, y) = y(x + y) - x y = y^2$, with remainder $0$, and $S(x, y) = 0$, and $S(x + y, x) = y$ now has remainder $0$.
So $G$ is a Gröbner basis of $(x, y)$.

Non-example: the set $F$ above fails the test in step 4, since $S(x + y, x)$ has nonzero remainder; this is why $F$ is not a Gröbner basis.