Grobner Bases Explainer

Alternatively: I taught Prof. Brian Conrad something new (the Koiran result & the rough outline), though he later made fun of the fact that I forgot how to read a clock on the spot (I was checking for my timer on my phone, but instead looked at the clock and forgot when I had started).

I now think that reading Fulton is probably not the best way to “learn algebraic geometry,” most notably because he avoids talking about sheaves for the longest time. You should read some text in Commutative Algebra, and then either the Rising Sea or Hartshorne, where read is the same as “do the problems in.”

Abstract

Algebraic Geometry can be thought of as bridging together polynomial equations over general fields to an geometric space that describes the set of solutions of those polynomials. The question is then how one might computationally attack these problems. This caused the birth of the field of computational algebraic geometry in 1979. The main object of interest at the time was that of a Gröbner Basis. This work will go into describing what this is and hopefully how it is utilized.

Introduction

We let $k$ be a field. This expository paper will use Schenck [Schenck2003], Lauritzen [Lauritzen2003], and Abramson [Abramson2009] as my main resources, as they are meant to be helpful introductions to the subject.

Motivation and History

The formal derivation of a Gröbner basis was developed in Bruno Buchberger’s 1965 Ph.D. thesis. Gröbner was his advisor, and the thesis problem was to find “a basis of the residue class ring of a zero-dimensional polynomial ideal”. For clarity, a zero-dimensional polynomial ideal $I \in k[X_1, \ldots, X_n]$ simply means that the quotient $k[X_1, \ldots, X_n]/I$ is finitely generated, and thus the question is simply “how do we find good basis elements of this quotient ring?” Note that an equivalent kind of question that is a direct result of Hilbert’s Basis Theorem is “how do we find good generating elements of $I$”? This question matters almost immediately to check if an arbitrary polynomial is present within the ideal $I$! So the question we have to deal with here first is what is “good” and then derive an algorithm.

While Buchberger apparently invented and named this object, he attributed to Gröbner as he had developed these methods over the course of “about 17 years,” applying them mostly to problems such as finding bases of integrals of differential equations. However, as he was doing this work in the 1930s, the notion of a computational problem was not yet well-founded, and so Buchberger had the task of formalizing “goodness” and asserting termination/correctness of the respective algorithm.

To understand why this is a hard question, one doesn’t really have to look any further than Gaussian Elimination. If we are only dealing with linear polynomials in our ideal $I$, we can immediately apply the Gaussian Elimination algorithm to get our free variables, which admit a basis of the quotient ring immediately. If we have some equalities left over, we can use the Euclidean Algorithm on these (as a polynomial ring over a field is a Euclidean domain) to further simplify.

In some sense, you can also do this if you have higher-degree polynomials, but as you might have many more auxiliary variables than equations, you may not be able to simplify the problem at all.

To attack this problem, Buchberger had to invent the formal notion of an $S$-polynomial. We will get there soon.

Basic Definitions

First, let us attack the moral question of what makes a “good” polynomial. First, let us live in $k[X]$. If we are given an ideal with some set of generators, we want to find “better” generators. Note that $k[X]$ is a principal ideal domain, so in some sense this is the easiest possible problem we could handle.

Oftentimes, when we write down a polynomial, we write it down in order of “the most impactful terms,” i.e. the ones with largest degree are first and we end with the constant term. So, when we are asked to solve problems of this type, we solve it via the Euclidean Algorithm, which allows us to efficiently compute the GCD of polynomials in our generating set.

The standard argument for this algorithm is based upon invariants, in this specific case being the degree of the polynomials, and decreasing it at every step. So, we’d like to bring this over to the multivariate case in $k[X_1, \ldots, X_n]$.

First, we need to have some notion of term order that is similar to the ordering of degrees. To this end, we have some definitions.

Definition. Letting $\alpha = (\alpha_1, \ldots, \alpha_n) \in \mathbb{N}^n$, we write \(x^{\alpha} := X_1^{\alpha_1}\cdots X_n^{\alpha_n}.\) We call elements of this type terms, which are monomials with coefficient one. We write $\mid\alpha\mid = \sum_i \alpha_i$ as the degree of the term.

Definition. A monomial/term order $>$ is a total order on the terms of $k[X_1, \ldots, X_n]$, equivalently a total order on $\mathbb{N}^n$, which satisfies the following properties:

1. For any $\gamma$, if $\alpha > \beta$, then $\alpha + \gamma > \beta + \gamma$.
2. Any nonempty subset of terms has a smallest element, i.e. $>$ admits a well-ordering.

Note that a total order is the same as a linear order, and that the second property forces it to have similar properties to the natural ordering on $\mathbb{N}$.

Definition. We define the initial monomial, denoted by $\mathrm{in}(f)$, as the largest monomial that appears in $f$ under a fixed term ordering $<$. As $f$ is an element of a polynomial ring over a field, we can always force the coefficient of $\mathrm{in}(f)$ to be $1$, which forces which representative of $f$ we use.

Clearly, we have been using these all our lives. We have the lexicographic ordering, where we say $\alpha > \beta$ if the leftmost nonzero entry of $\alpha - \beta$ is positive, which immediately admits this property. This is the normal degree ordering in $k[X]$. However, in the multivariate case such as $k[X, Y, Z]$ we would then have $X > Y^{10000} > Z$, and it is much nicer to operate over some of these than the others.

So, we instead “grade” the term by the degree first. More normally, we use the Graded Lexicographic ordering, where $\alpha > \beta$ if $\mid\alpha\mid > \mid\beta\mid$ or $\mid\alpha\mid = \mid\beta\mid$ and the leftmost nonzero entry of $\alpha - \beta$ is positive. This gives us the notion of $Y^{10000} > X > Z$, which is much nicer in the multivariate case.

So, assume we have some monomial order on $k[X_1, \ldots, X_n]$ denoted by $<$. Say $f, f_1, \ldots, f_m \in k[X_1, \ldots, X_n]$, and we want to see if $f \in (f_1, \ldots, f_m)$. In the spirit of the Euclidean Algorithm, we run the following algorithm:

Algorithm 1 (Simple Division Algorithm)

Let $\mathrm{div}, \mathrm{rem} := 0, 0$.

1. If $f = 0$ then we are done. Otherwise,
2. If $\mathrm{in}(f_i) \cdot a_i = \mathrm{in} (f)$ for some $a_i \in k[X_1, \ldots, X_n]$, then add $a_if_i$ to $\mathrm{div}$, and subtract $a_if_i$ from $f$. Note that the initial term is decreasing.
3. If there is no $a_i$ that works, add $\mathrm{in}(f)$ to the remainder, and subtract $\mathrm{in}(f)$ from $f$.
4. Repeat this process.

This terminates as at each step, the initial term of $f$ decreases, and by the well-ordering property, this process cannot go on indefinitely. Letting $a_i$ be the total sum of each partial $a_i$ witnessed during this algorithm and $r$ as the remainder term, we can then write $f = \sum_i a_if_i + r$. Can we then faithfully say that if $r = 0$, then $f \in (f_1, \ldots, f_m)$?

No! This clearly doesn’t work! First of all, it is sensitive to the ordering of the $f_i$’s, but it is also sensitive to the ordering that we choose! Say we want to check if $x \in (x^{100}, x^{100}+x)$. Using the graded lexicographic ordering… it immediately fails. But this failure shows us that we have to focus on the basis’s generating elements, and more specifically that we want the ability to cancel out initial terms whenever possible. We can now look at the notion of a Gröbner basis.

Definition. A subset ${g_1, \ldots, g_k}$ of an ideal $I$ is called Gröbner for $I$ if the ideal generated by initial monomials of elements of $I$, which we denote as $\mathrm{in}(I)$, is also generated by $(\mathrm{in}(g_1), \ldots, \mathrm{in}(g_k))$. Note that $k$ might be larger than our given set of generating polynomials!

I’ll skip over the proof that it exists as the proof of termination of an algorithm computing it is sufficient.

However, for this to be useful, we do need to guarantee that a Gröbner subset is also a basis!

Lemma. A Gröbner subset of $I$ is also a basis of $I$.

Proof. Let ${g_1, \ldots, g_k}$ be a Gröbner subset of ideal $I$. We run Algorithm 1 on $f \in I$ to get $f = \sum_i a_i g_i + r$. We want to show that $r = 0$. Assume that it is not. Then note $r \in I$. Note then that $\mathrm{in}(r) \in \mathrm{in}(I)$. However, as $(\mathrm{in}(g_1), \ldots, \mathrm{in}(g_k))$ generates $\mathrm{in}(I)$, so $\mathrm{in}(r)$ is a multiple of some $\mathrm{in}(g_j)$. However, note that within the algorithm, each monomial within the remainder term must not have been divisible by some initial element. Thus we have a contradiction, so $r = 0$. Note the other inclusion direction is immediate as a Gröbner subset is a subset of $I$. $\square$

So, how does Algorithm 1 change when we use a Gröbner basis? Well, it actually works!

So… how do we compute it? What was Buchberger’s insight? Well, we want some kind of way of getting rid of those nasty leading terms…

Definition. We define the syzygy pair, or $S$-pair/$S$-polynomial of monic polynomials $f, g$ as

Note that $\mathrm{lcm}$ on a term takes the maximum of each exponent.

Note that if $f, g$ are in an ideal, then their $S$-polynomial must also necessarily be. Also note that this polynomial attempts to cancel out leading terms, as it minimally raises both $f, g$ to a common leading term and gets rid of it by monotonicity.

Theorem (Buchberger’s Criterion). Let $G = {g_1, \ldots, g_k}$ be a basis of some ideal $I$. Then $G$ is a Gröbner basis iff $S(g_i, g_j)$ has remainder $0$ after running Algorithm 1 using $G$, for all pairs $g_i, g_j \in G$.

We sketch this out by allowing ourselves a hidden lemma.

Lemma. Suppose we have a finite sum $\sum_i p_i$ where the initial term for each $p_i$ is $\alpha \in \mathbb{N}^n$ but the sum has initial term strictly less than $\alpha$, i.e. we have cancellation. Then we have that $\sum_i p_i$ can be expressed as a $k$-linear combination of the $S$-polynomials $S(p_j, p_l)$.

Note that each $S$-polynomial has initial term strictly less than $\delta$, which tells us that we can pass our sums downward until we do not have a cancellation of initial terms. We can now outline the proof sketch of Buchberger’s Criterion.

Proof. Let $f \in I$ and let $G = {g_1, \ldots g_k} \subset I$ such that $G$ is a basis and all $S$-pairs of $g_i, g_j$ are in $(G)$. We want to show that $G$ is Gröbner, which means that we want to show that $\mathrm{in}(f) \in (\mathrm{in}(g_1), \ldots, \mathrm{in}(g_k))$. As $G$ is basis, we can write $f = \sum_i a_ig_i$. Then we can have two cases. First we might have $\mathrm{in}(f)$ is the same initial monomial of one of the $a_ig_i$, in which case we are done by taking initials on both sides.

Otherwise, we have some cancellation of larger initial terms (i.e. they appear multiple times across the sum), call the largest $\alpha$. Isolate those $a_ig_i$’s with the largest initial terms. Further isolate them by splitting that sum into $\mathrm{in}(a_i)g_i + (a_i - \mathrm{in}(a_i))g_i$. Note that only the first term has the larger initial term. By the previous lemma, we can rewrite the sum of those terms as a linear combination of $S$-polynomials of $\mathrm{in}(a_i)g_i$. It can be shown that

where $\beta_{ij} = \mathrm{lcm}(\mathrm{in}(g_i), \mathrm{in}(g_j))$.

As the $S$-polynomials admit zero remainder after being divided by $G$ by hypothesis, and by the nature of the algorithm, when we write $S(g_i, g_j) = \sum_w q_wg_w$, we must have that $\mathrm{in}(q_wg_w)$ is bounded above by the initial term in $S(g_i, g_j)$.

Thus we can reduce the largest initial term if it is not already $\mathrm{in}(f)$ by using the decompositions of the $S$ terms, which then have largest initial term $\alpha - \beta_{ij} + \mathrm{in}(S(g_i, g_j))$. Note that $\beta_{ij} > \mathrm{in}(S(g_i, g_j)$ by the nature of the $S$-polynomial construction.

So we have rewritten $\sum_i a_ig_i$ as a new sum $\sum_i b_ig_i$ where $\mathrm{in}(b_ig_i) < \alpha$. We keep on doing this until we reach $\mathrm{in}(b_ig_i) = \mathrm{in}(f)$, thus we have shown $G$ is Gröbner. $\square$

And so now we have a computable criterion! So here comes the algorithm of the hour.

Algorithm 2 (Buchberger’s Algorithm). Let $I = (f_1, \ldots, f_m)$ be a polynomial ideal over $k[X_1, \ldots, X_n]$. We construct a Gröbner basis as follows. Let $G = {f_1, \ldots, f_m}$. Then,

1. Let $G’ = G$.
2. For each pair $p\neq q$ in $G’$ compute $r$ under the result of dividing $S(p, q)$ by $G’$ using Algorithm 1. If $r \neq 0$, add it to $G$. Otherwise do nothing.
3. If $G’ = G$, i.e. we didn’t add anything, then we are done. Otherwise, repeat this process.

Theorem. The algorithm (Buchberger’s Algorithm) terminates in a finite number of steps and admits a Gröbner basis.

Proof. Note that throughout this process, $(G) = I$, as $G$ contains a basis of $I$, and we only add the remainder of the polynomial $S(p, q)$ under division by polynomials already in $G$, meaning we only add polynomials in $(G)$. So we do not add too many elements ever. Clearly, if the algorithm terminates, it is correct.

Letting $G_0, G_1, G_2, \ldots$ be $G’$ at the $i$th step, note that we have $G_0 \subseteq G_1 \subseteq G_2 \subseteq \ldots$. Note that we must have $\mathrm{in}(G_0) \subseteq \mathrm{in}(G_1) \subseteq \mathrm{in}(G_2) \subseteq \ldots$, where $\mathrm{in}(S)$ is the ideal generated by initial terms of polynomials in the set $S$. Note that these ideals live in $k[X_1, \ldots, X_n]$, which under Hilbert’s Basis Theorem is Noetherian, meaning this ascending chain of ideals terminates. So, we will eventually have $\mathrm{in}(G’) = \mathrm{in}(G)$.

We will show that this implies $G = G’$ by contrapositive. Say $G’ \neq G$, i.e. some nonzero remainder $r$ of an $S$-polynomial in $G’$ has been adjoined to $G$. This means that $\mathrm{in}(r)$ is not divisible by the leading terms of elements in $G’$, meaning $\mathrm{in}(r) \not \in \mathrm{in}(G’)$, so $\mathrm{in}(G’) \subset \mathrm{in}(G)$.

Thus whenever we get $\mathrm{in}(G’) = \mathrm{in}(G)$, we must have $G = G’$, so this algorithm terminates in a finite number of steps. $\square$

This is the Buchberger algorithm. Note the main powerful theorem we needed to compute a good basis that admits a membership division algorithm/canonical representative in the quotient ring was Hilbert’s Basis Theorem, which asserts that $k[X_1, \ldots, X_n]$ is Noetherian, meaning not only that our ideals are describable with a finite number of polynomials, but that this algorithm is even possible via the ascending chain condition.

We end with the following definition. We cannot simply use the size of a basis for uniqueness here, but instead we have to do the following.

Definition (Reduced Gröbner Basis). A reduced Gröbner basis $G = {g_1, \ldots, g_k}$ for an ideal $I$ is a Gröbner basis for $I$ such that each $g_k$ is monic (doesn’t matter for us, as we are poly over a field), and also for all $p \in G$, no monomial of $p$ is inside of $\mathrm{in}(G \setminus {p})$.

It is hopefully clear that you can use the aforementioned algorithms to compute this once you have a basis already, though it is clearly tedious as of now to do so. However, this admits the following representation theorem.

Theorem. For a nonzero ideal $I$ and a given monomial order, $I$ has a unique reduced Gröbner basis.

This allows us to check if $I = J$ for two different ideals $I, J$.

Computed Examples

Let’s work over simple examples.

Example 1. Let $I = (x^2 + y^2 - 1, x - y)$. Note this is the unit circle and a line. We use the lex-ordering $x > y$.

First, we compute the $S$-polynomial of these

Under the division algorithm, we get the remainder

As $2y^2 - 1$ is not zero, we add it to $I$. Now we only need to check $S(y^2 - 1/2, x^2+y^2-1)$ and $S(y^2-1/2, x-y)$.

Forcing monotonicity, we have the polynomials $x^2 - 1/2$ and $x - 2y^3$. Using our division algorithm,

Thus these $S$-polynomials reduce to $0$, and so our basis is $(x^2 + y^2 - 1, x-y, y^2-1/2)$. Furthermore $(x-y, y^2-1/2)$ is the reduced Gröbner basis.

Now say we are solving for $V(I)$. Note this last polynomial in our basis is single variable and so we can solve it exactly, which gives us $y = \pm \sqrt{1/2}$. Then this makes $x-y$ into a single variable equation $x\mp \sqrt{1/2}$, which admits all solutions.

This is a simple example, but the general truth is when you have a lexicographic term ordering with $x_1 > x_2 > \ldots > x_n$, you will often end up with a minimal-variable number polynomial at the end of it (as you are decreasing the initial term) and so it will become much easier to solve. However, note that the lex ordering doesn’t actually care about the degree, meaning that we might end up with few variable high degree polynomials. The lexicographic ordering admits degree explosion and is therefore computationally somewhat expensive.

Example 2. We will use a term ordering called graded reverse lexicographic. We let $\alpha > \beta$ if $\mid\alpha\mid > \mid\beta\mid$ or $\mid\alpha\mid = \mid\beta\mid$ and the rightmost nonzero term of $\alpha - \beta$ is negative. Intuitively, this allows us to bias for total degree and for smaller indeterminants to appear more often. This is used in Gröbner basis solvers. We call this grevlex.

Let $I = (x^2 - y, xy-1)$. It can be shown that under the lex-ordering we get the basis $(y^3-1, x-y^2)$. We compute the $S$-polynomials with respect to the grevlex:

The leading term here is $-y^2$, so we rewrite it as $y^2-x$. Note that this cannot be divided using the division algorithm, so we have to add it to our system. We compute the two new $S$-polynomials

The second $S$ polynomial immediately reduces, and we have $x^3 - y^3 = x(x^2-y) -y(y^2-x)$, so both $S$ polynomials reduce. Thus we have a grevlex-basis $(x^2-y, xy-1, y^2-x)$. This can be further reduced to $(x^2-y, y^2-x)$. This method keeps the degree of the generating elements at most $2$.

So, the lex-order forces the elimination of earlier indeterminants by creating higher powers of later ones, and grevlex keeps the calculations degree controlled while still attempting to do what lex is doing.

You can solve for $V(I)$ using the lex-order and computing a Gröbner basis. Note that solving $V(I)$ is really useful when solving optimization problems via the Lagrangian!

Complexity of Algorithms

It should be very clear that Algorithm 1 and Buchberger’s Algorithm are descriptively very simple and as a result computationally quite slow. There are multiple ways of speeding them up, but most of them will require some slight tweaking of what Buchberger’s Criterion really says. However, what is the actual lower bound on these bases?

Theorem (Mayr-Meyer-Dubé). There exist ideals $I \subset k[X_1, \ldots, X_n]$ such that minimal Gröbner bases have size of order

As a result, you can’t really hope to be that much faster. This is kind of an extension of what Hermann did in ‘26 as well, when he wrote down a bound on the degrees in representations of elements in an ideal. It also gives us an effective version of the nullstellensatz with upper bounds singly exponential. But what happens in practice?

In 1999, Faugére developed a practically faster algorithm for the same problem. Specifically, when we run Buchberger’s algorithm, we have to compute each $S(f_i, f_j)$ under the result of the division algorithm. Faugére’s F4 algorithm finds for all critical pairs of a fixed degree $d$ the set

and then converts each polynomial in $S_d$ into the row of a sparse matrix whose columns correspond to monomials. Then, you perform sparse Gaussian elimination on this matrix to simultaneously perform all reductions on the $S$ polynomials.

Note that you expect $\mid R_{F4}\mid \ll \mid R_B\mid$ where $R_A$ is the set of remainder polynomials added by algorithm $A$. Thus at each step we have a faster way of calculating the remainder polynomials and we expect to compute less! Formally, you should be somewhat suspicious of this as we are using some $S$-polynomials to reduce other ones, but all this requires is revisiting the cancellation lemma.

Now, Faugére also has another algorithm called the F5 algorithm. This algorithm has a pretty new add-on, wherein it tracks a computational `signature’ of a polynomial that detect polynomial syzygies before we even begin this simultaneous reduction. You can understand a signature of the generators $f_i$ as $(i, 1)$ and of $mf_i$ as $(i, m)$. Then for an arbitrary $f$ take the maximal index $mf_i$ in its decomposition and write it as $(i, m)$. it maintains the invariant: If a polynomial with signature $(i, m)$ has already been reduced, then any other polynomial whose signature divides $(i, m)$ must reduce to $0$. In this way, it uses a signature as a check before it does a reductive process, especially as you care store each polynomial as a linear combination of the original basis polys. As a result, you avoid a huge fraction of the work.

Table 1: Complexity of selected Gröbner-basis algorithms

However, what about the amount of working space? One would expect that you always need an exponential amount. But really, you can show that the ideal membership problem only needs exponential working space, given to us by Mayr. Working space here is not the same as output space.

Finally, note that checking if $1$ is inside of an ideal is the same as checking if the vanishing set of a set of polynomials is empty, and Hilbert’s Nullstellensatz says that if I have an ideal $I$ such that $V(I)$ is empty, then $\sqrt{I}$ must contain $1$, thus $I$ must contain $1$, and so the membership problem allows us to check this. We have the somewhat surprising result from Koiran.

Theorem (Koiran ‘96). Under the assumption of the Generalized Riemann Hypothesis we have that the membership problem of $1$ in a given polynomial ideal $I$ over $\mathbb{Z}[X]$ lies in the polynomial hierarchy, specifically the Arthur-Merlin class.

This is a randomized algorithm that checks sufficiently many primes, which is why it requires the GRH assumption.

Finally, we will end with a nice theorem.

Theorem (Krick-Logar ‘91). If $I$ is an ideal of $k[X_1, \ldots, X_n]$ and has dimension $\leq 1$, then a Gröbner basis can be calculated in time $2^{O(n)}$, assuming unit costs of arithmetic in $k$.

This means that for large enough ideals $I$, you don’t actually need to do that much work.

Open/Future Questions

What are open questions with regards to Buchberger’s algorithm? Well, since it is an algorithm, we have some natural questions:

1. Can we characterize classes of ideals where Buchberger runs in singly-exponential time? Does the Krick-Logar theorem have a converse?
2. What is the algorithm’s complexity under probabilistic models of random polynomial systems?
3. We are currently using the $S$-polynomial criterion from Buchberger. He also has other criterion’s called the product and chain criterion, and the F4/F5 algorithms show that the selection order of $S$-polys affects runtime. Is there a provably optimal $S$-pair selection strategy given any term ordering?
4. In the F4/F5 algorithms, we are solving matrices, which can be made parallel. Where else is it possible to utilize a parallel algorithm? What is the parallel complexity of basis computation? Does Buchberger’s algorithm admit polylogarithmic depth?
5. We are currently working over $k$ field. What happens when you change this to just a Euclidean Domain? A DVR? A tropical semiring? How does the complexity change?
6. The $S$ in $S$-polynomials stands for syzygy, which can be understood geometrically, but so far we have derived the algorithm as purely algebraic. However, we are working in algebraic geometry, and so we care about the geometry. Does Buchberger’s algorithm say anything geometric?

Thanks for reading!

References

Schenck, H. (2003). Computational Algebraic Geometry. London Mathematical Society Student Texts, 58. Cambridge University Press, Cambridge UK; New York NY. ISBN: 978-0-521-82964-9. Draft lecture notes, “FINAL FINAL” version

Lauritzen, N. (2003). Concrete Abstract Algebra: From Numbers to Gröbner Bases. Cambridge University Press, Cambridge UK; New York NY. Pages: xiv, 240. ISBN: 978-0-521-53410-6. Archive.org

Abramson, M. P. (2009). Historical background to Gröbner’s paper. ACM Communications in Computer Algebra, 43(1/2), 22–23. DOI: 10.1145/1610296.1610301