---
tag: 5ZKP6E4JCE
kind: definition
name: Gröbner basis
msc: [13P10, 68W30]
defines: C83KPT47R0
uses: [04C5ZBG1WT, 0SDC934R52, E874NARWPV, 096Z9MP2ME, 4G25S7PJ22, T8EN3CAEQF, 4RH1D40WG1, 0YKA9J3XEE]
sources:
  - url: https://en.wikipedia.org/wiki/Gröbner_basis
---

## 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]] on $S$.
For a nonzero $f \in S$, let $\operatorname{LT}(f)$ be its leading term.
Let $I$ be an [[ideal|096Z9MP2ME]] of $S$, and let $\operatorname{LT}(I)$ be the ideal generated by the leading terms $\operatorname{LT}(f)$ of all nonzero $f \in I$.
A finite subset $G = \set{g_1, \ldots, g_t}$ of $I \setminus \set{0}$ is a *Gröbner basis* of $I$ if
$$(\operatorname{LT}(g_1), \ldots, \operatorname{LT}(g_t)) = \operatorname{LT}(I).$$

## Remarks

$\operatorname{LT}(I)$ is a [[monomial ideal|4G25S7PJ22]].
Equivalent forms: for every nonzero $f \in I$, some $\operatorname{LT}(g_i)$ divides $\operatorname{LT}(f)$.
Or: for every $f \in S$, the remainder of $f$ under the [[multivariate division algorithm|T8EN3CAEQF]] by $G$ is zero if and only if $f \in I$.
A Gröbner basis of $I$ generates $I$, and every ideal has a Gröbner basis; this gives another proof of [[Hilbert's basis theorem|0YKA9J3XEE]].
A Gröbner basis is *reduced* if each $\operatorname{LT}(g_i)$ has coefficient $1$ and no monomial of $g_i$ is divisible by $\operatorname{LT}(g_j)$ for $j \ne i$.
For a given monomial order, each ideal has a unique reduced Gröbner basis.
[[Buchberger's algorithm|4RH1D40WG1]] computes a Gröbner basis from any finite set of generators.

Example: $G = \set{x, y}$ is a Gröbner basis of $I = (x, y)$ in $k[x, y]$, for any monomial order.
Every nonzero $f \in I$ has no constant term, so each of its monomials, in particular $\operatorname{LT}(f)$, is divisible by $x$ or by $y$.

Non-example: for the lexicographic order with $x > y$, the set $G = \set{x + y, \; x}$ generates the same ideal $I$, and both leading terms equal $x$.
But $y = x - (x + y) \in I$ and $\operatorname{LT}(y) = y \notin (x)$, so $G$ is not a Gröbner basis of $I$.