Gröbner Bases

2 Division Algorithms and Gröbner Bases

Whenever we have a monomial ordering, we have a notion of leading coefficient, namely the highest nonzero term according to the ordering. Given an ideal \((f_1,\dots f_n)\), we would like to run the following division algorithm: Take a polynomial \(g\), and compare leading coefficients with each \(f_i\). If the leading coefficient of \(f_i\) divides one of \(g\)’s terms, subtract the corresponding multiple of \(f_i\) from \(g\). If you are not capable of doing this with any of the \(f_i\), then set the leading term aside as a remainder, and continue with the rest of the polynomial. As the monomial ordering is well-ordered, this will stop eventually, ie. none of the leading terms of the \(f_i\) will divide any of what is left of \(g\). We would like this process to yield a unique remainder for any two members of the same coset of the ideal so we can do computations in the quotient. Given arbitrary generators of an ideal, this may not always work unfortunately.

For example, consider \((x+y,x^2+xy+y^2)\) with the lexicographical order \(x>y\). We can try to reduce the polynomial \(x^2 + xy\) in two ways. First we can subtract \(x(x+y)\) from it to get \(0\), after which we are done. Or we can subtract \(1(x^2+xy+y^2)\) from it to get \(-y^2\), after which we are done. Note that we got different remainders, which is not what we’d like. To fix this, we should choose a different set of generators for the ideal that also generate the ideal of leading coefficients, for example \((y^2,x+y)\). If we were to run the algorithm on this set of generators, we would get \(0\) both times. This is because \((y^2,x+y)\) is a Gröbner basis.

Definition 2.1. If \(f\) is a polynomial, \(LT(f)\) denotes its leading term (with the coefficient). If \(I\) is an ideal \(LT(I)\) is the ideal of leading terms. A Gröbner basis \(G\) of \(I\) is a nonempty subset of \(I\) whose leading terms generate \(LT(I)\).

Proposition 2.2. If \(G\) is a Gröbner basis of \(I\), then the division algorithm yields a unique representative for each coset of \(R[x_1,\dots ,x_n]/I\). In particular, it is \(0\) iff the element is in the ideal, so \(G\) generates \(I\).

Proof. Suppose we have two remainders of elements from the same coset, \(r_1, r_2\) and we subtract them. We’ll get something in \(I\) but if it is nonzero, we can apply the algorithm to it as \(G\) is a Gröbner basis. But any term we remove must have come from either \(r_1\) or \(r_2\), which is a contradiction, as it means the division algorithm was not yet complete on \(r_1\) or \(r_2\). If \(r_1\) is in the ideal, it must be \(0\) or else the algorithm again is not complete. □

By Proposition 2.2 and the proof of the Hilbert Basis Theorem (except now we are working with arbitrary monomial orderings) we get that every ideal has a Gröbner basis. How can we actually compute it? The Buchberger Criterion gives a way to do this. From now on, we will work over a field \(K\).

To motivate this, consider the example before with \((x+y,x^2+xy+y^2)\). We can look at the leading terms, \(x\) and \(x^2\), and take the LCM, \(x^2\). We can then add in the extra term \(x(x+y)-1(x^2+xy+y^2) = -y^2\). Adding this in to our list of generators, we do get a Gröbner basis. The Buchberger Criterion says this strategy will always work.

First we will set up some notation. Fix a set of generators of \(I\), \(G\). We say \(f \mapsto r\) to mean that applying the algorithm to \(f\) with \(G\) yields \(r\) as the remainder. If \(f,g\) are polynomials, then we let \(LCM = LCM(LT(f),LT(g))\) denote the monic that is the \(LCM\) of the leading terms of \(f\) and \(g\). We define \(S(f,g)\) = \(\frac {LCM}{LT(f)}f-\frac {LCM}{LT(g)}g\). We would like to say that any missing generators to make a Gröbner basis will be produced by repeatedly adding the \(S(f,g)\) until they are no longer needed.

Before we prove the Buchberger Criterion, a simple lemma:

Lemma 2.3. Suppose that \(f_1 \dots f_n\) are polynomials of the same leading monomial. Then if \(h = \sum _1^n s_if_i, s_i \in K\) has leading term smaller than the \(f_i\), then \(h = \sum _1^{n-1}r_iS(f_i,f_{i+1}), r_i \in K\).

Proof. WLOG assume the \(f_i\) are monic. Note \(S(f_i,f_{i+1})\) is just \(f_i-f_{i+1}\). Then write \(\sum _1^n s_if_i\) as \(\sum _1^{n-1} \big (\sum _1^is_i\big )(f_i-f_{i+1}) + \big (\sum _1^ns_i\big )f_n\). Each of the terms in the first sum has leading term smaller than the \(f_i\), so \(\big (\sum _1^ns_i\big )f_n = 0\), and we get that \(h = \sum _1^ns_if_i = \sum _1^{n-1}\big (\sum _1^is_i\big )S(f_i,f_{i+1})\). □

Theorem 2.4 (Buchberger Criterion). \(G = \{f_1 \dots f_n\} \subset I\) is a Gröbner basis iff each \(S(f_i,f_j) \mapsto 0\) and if \(G\) generates \(I\).

Proof. The only if follows from Proposition 2.2. Now suppose each \(S(f_i,f_j) \mapsto 0\) and \(G\) generates \(I\). Take any \(f \in I\), and apply the division algorithm to get a remainder \(f'\). Choose a representation \(f' = \sum _1^ng_if_i\) such that the maximal leading term of each summand is minimal, say \(\alpha \). Suppose \(f' \neq 0\), so that \(\alpha > LT(f)\). We will try to find a smaller representation using the fact that \(S(f_i,f_j) \mapsto 0\).

We have:
\(\seteqnumber{0}{}{0}\)
\begin{align*} f' &= \sum _1^ng_if_i\\ &= \sum _{LT(g_if_i)=\alpha }LT(g_i)f_i + \sum _{LT(g_if_i)=\alpha }(g_i-LT(g_i))f_i + \sum _{LT(g_if_i)<\alpha }g_if_i\\ &= \sum s_iS(LT(g_i)f_i,LT(g_j)f_j) + \sum _{LT(g_if_i)=\alpha }(g_i-LT(g_i))f_i + \sum _{LT(g_if_i)<\alpha }g_if_i \end{align*} The second two sums have all their terms smaller than \(\alpha \) so Lemma 2.3 applies to the first sum, which is what has been done in the last step.

However now we have a contradiction as \(S(LT(g_i)f_i,LT(g_j)f_j)\) is a monomial multiplied with \(S(f_i,f_j)\) so we have \(S(LT(g_i)f_i,LT(g_j)f_j) \mapsto 0\) so it can be written as a linear combination of the \(f_i\) with degrees of each term at most that of \(S(LT(g_i)f_i,LT(g_j)f_j)\), which in particular is smaller than \(\alpha \). This contradicts minimality of \(\alpha \). □

Buchberger’s Criterion allows us to produce Gröbner bases. In particular, given a set of generators \(\{f_1 \dots f_n\}\) we can compute the \(S(f_i,f_j)\), and reduce them. If they are all zero, we have a Gröbner basis, otherwise we add the remainder to the list and repeat until the criterion is satisfied. Now that we can find Gröbner bases, we can compute in quotient rings, and make nontrivial statements about the ideals that we are working with. In particular, this gives an effective Nullstellensatz, as an ideal is trivial iff \(1\) is in a Gröbner basis of it.