6.3. 6.3 Gröbner basis

Let be a field and be a multivariate polynomial ring in variables over . Let . First we determine a necessary and sufficient condition for the polynomials having common roots in . We can see that the problem is a generalisation of the case from the previous subsection. Let

denote the ideal generated by polynomials . Then the polynomials form a basis of ideal . The variety of an ideal is the set

The knowledge of the variety means that we also know the common roots of . The most important questions about the variety and ideal are as follows.

Fortunately, in a special basis of ideal , in the so-called Gröbner basis, these questions are easy to answer. First let us study the case . Since is a Euclidean ring,

We may assume that . Let and divide by with remainder. Then there exist unique polynomials with and . Hence,

Moreover, if are the distinct linear factors of . Unfortunately, equality (6.14) is not true in case of two or more variables. Indeed, a multivariate polynomial ring over an arbitrary field is not necessary Euclidean, therefore we have to find a new interpretation of division with remainder. We proceed in this direction.

6.3.1. 6.3.1 Monomial order

Recall that a partial order is a total order (or simply order) if either or for all . The total order ` ` is allowable if

(i) for all ,

(ii) for all .

It is easy to prove that any allowable order on is a well-order (namely, every nonempty subset of has a least element). With the notation already adopted consider the set

The elements of are called monomials. Observe that is closed under multiplication in , constituting a commutative monoid. The map , is an isomorphism, therefore, for an allowable total order on , we have that

(i) for all ,

(ii)

The allowable orders on are called monomial orders. If , the natural order is a monomial order, and the corresponding univariate monomials are ordered by their degree. Let us see some standard examples of higher degree monomial orders. Let

where the variables are ordered as .

  • Pure lexicographic order.

    and .

  • Graded lexicographic order.

    or ( and ).

  • Graded reverse lexicographic order.

    or ( and and ).

The proof that these orders are monomial orders is left as an exercise. Observe that if , then . The graded reverse lexicographic order is often called a total degree order and it is denoted by .

Example 6.11 Let and let . Then

Let and again, . Then

Let a monomial order be given. Furthermore, we identify the vector with the monomial . Let be a non-zero polynomial, . Then are the terms of polynomial , is the multidegree of the polynomial (where the maximum is with respect to the monomial order), is the leading coefficient of , is the leading monomial of , and is the leading term of . Let and .

Example 6.12 Consider the polynomial . Let and . Then

If and , then

6.3.2. 6.3.2 Multivariate division with remainder

In this subsection, our aim is to give an algorithm for division with remainder in . Given multivariate polynomials and monomial order , we want to compute the polynomials and such that and no monomial in is divisible by any of .

Multivariate-Division-with-Remainder( )

  1     2     3  
                        FOR
                      
                      
                     
                        TO
                      
                        4    
                        DO
                      
                        5  
                        WHILE
                      
                        6    
                        DO
                      
                     
                        IF
                      
                      divides  for some    7       
                        THEN
                      choose such an  and    8             9       
                        ELSE
                      
                       10            11  
                        RETURN
                      
                      and  
                  

The correctness of the algorithm follows from the fact that in every iteration of the while cycle of lines 5–10, the following invariants hold

(i) and ,

(ii) for all ,

(iii) no monomial in is divisible by any .

The algorithm has a weakness, namely, the multivariate division with remainder is not deterministic. In line 7, we can choose arbitrarily from the appropriate values of .

Example 6.13 Let , , , the monomial order , , and in line 7, we always choose the smallest possible . Then the result of the algorithm is , , . But if we change the order of the functions and (that is, and ), then the output of the algorithm is , and .

As we have seen in the previous example, we can make the algorithm deterministic by always choosing the smallest possible in line . In this case, the quotients and the remainder are unique, which we can express as .

Observe that if , then the algorithm gives the answer to the ideal membership problem: if and only if the remainder is zero. Unfortunately, if , then this is not true anymore. For example, with the monomial order

and the quotients are , . On the other hand, , which shows that .

6.3.3. 6.3.3 Monomial ideals and Hilbert's basis theorem

Our next goal is to find a special basis for an arbitrary polynomial ideal such that the remainder on division by that basis is unique, which gives the answer to the ideal membership problem. But does such a basis exist at all? And if it does, is it finite?

The ideal is a monomial ideal if there exists a subset such that

that is, ideal is generated by monomials.

Lemma 6.11 Let be a monomial ideal, and . Then

Proof. The direction is obvious. Conversely, let and such that . Then the sum has at least one member which contains , therefore .

The most important consequence of the lemma is that two monomial ideals are identical if and only if they contain the same monomials.

Lemma 6.12 (Dickson's lemma) Every monomial ideal is finitely generated, namely, for every , there exists a finite subset such that .

Lemma 6.13 Let be an ideal in . If is a finite subset such that , then .

Proof. Let . If is an arbitrary polynomial, then division with remainder gives , with , such that either or no term of is divisible by the leading term of any . But , hence, . This, together with Lemma (6.11), implies that , therefore .

Together with Dickson's lemma applied to , and the fact that the zero polynomial generates the zero ideal, we obtain the following famous result.

Theorem 6.14 (Hilbert's basis theorem) Every ideal is finitely generated, namely, there exists a finite subset such that and .

Corollary 6.15 (ascending chain condition) Let be an ascending chain of ideals in . Then there exists an such that .

Proof. Let . Then is an ideal, which is finitely generated by Hilbert's basis theorem. Let . With , we have .

A ring satisfying the ascending chain condition is called Noetherian. Specifically, if is a field, then is Noetherian.

Let be a monomial order on and an ideal. A finite set is a Gröbner basis of ideal with respect to if . Hilbert's basis theorem implies the following corollary

Corollary 6.16 Every ideal in has a Gröbner basis.

It is easy to show that the remainder on division by the Gröbner basis does not depend on the order of the elements of G. Therefore, we can use the notation . Using the Gröbner basis, we can easily answer the ideal membership problem.

Theorem 6.17 Let be a Gröbner basis of ideal with respect to a monomial order and let . Then .

Proof. We prove that there exists a unique such that (1) , (2) no term of is divisible by any monomial of . The existence of such an comes from division with remainder. For the uniqueness, let for arbitrary and suppose that no term of or is divisible by any monomial of . Then , and by Lemma 6.11, is divisible by for some . This means that .

Thus, if is a Gröbner basis of , then for all ,

6.3.4. 6.3.4 Buchberger's algorithm

Unfortunately, Hilbert's basis theorem is not constructive, since it does not tell us how to compute a Gröbner basis for an ideal and basis . In the following, we investigate how the finite set can fail to be a Gröbner basis for an ideal .

Let be nonzero polynomials, , , and . The S-polynomial of and is

It is easy to see that , moreover, since , therefore .

The following theorem yields an easy method to test whether a given set is a Gröbner basis of the ideal .

Theorem 6.18 The set is the Gröbner basis of the ideal if and only if

Using the -polynomials, it is easy to give an algorithm for constructing the Gröbner basis. We present a simplified version of Buchberger's method (): given a monomial order and polynomials , the algorithm yields a Gröbner basis of the ideal .

Gröbner-basis( )

  1     2     3  
                        WHILE
                      
                        4    
                        DO
                      
                      an arbitrary pair from    5          6          7       
                        IF
                      
                        8          
                        THEN
                      
                        9               10  
                        RETURN
                      
                       
                  

First we show the correctness of the Gröbner-basis algorithm assuming that the procedure terminates. At any stage of the algorithm, set is a basis of ideal , since initially it is, and at any other step only those elements are added to that are remainders of the -polynomials on division by . If the algorithm terminates, the remainders of all -polynomials on division by are zero, and by Theorem (6.18), is a Gröbner basis.

Next we show that the algorithm terminates. Let and be the sets corresponding to successive iterations of the while cycle (lines 3-9). Clearly, and . Hence, ideals in successive iteration steps form an ascending chain, which stabilises by Corollary (6.15). Thus, after a finite number of steps, we have . We state that in this case. Let and . Then and either or , and using the definition of the remainder, we conclude that .

Example 6.14 Let , , , .

by step one, and by step two.

At the first iteration of the while cycle, let us choose the pair . Then , and . Therefore, and .

At the second iteration of the while cycle, let us choose the pair . Then , , , hence, and .

At the third iteration of the while cycle, let us choose the pair . Then , , .

At the fourth iteration, let us choose the pair . Then , , .

In the same way, the remainder of the -polynomials of all the remaining pairs on division by are zero hence, the algorithm returns with which constitutes a Gröbner basis.

6.3.5. 6.3.5 Reduced Gröbner basis

In general, the Gröbner basis computed by Buchberger's algorithm is neither unique nor minimal. Fortunately, both can be achieved by a little finesse.

Lemma 6.19 If is a Gröbner basis of , and , then is a Gröbner basis of as well.

We say that the set is a minimal Gröbner basis for ideal if it is a Gröbner basis, and for all ,

  • ,

  • .

An element of a Gröbner basis is said to be reduced with respect to if no monomial of is in the ideal . A minimal Gröbner basis for is reduced if all of its elements are reduced with respect to .

Theorem 6.20 Every ideal has a unique reduced Gröbner basis.

Example 6.15 In Example 6.14 not only but also is a Gröbner basis. It is not hard to show that is a reduced Gröbner basis.

6.3.6. 6.3.6 The complexity of computing Gröbner bases

The last forty years (since Buchberger's dissertation) was not enough to clear up entirely the algorithmic complexity of Gröbner basis computation. Implementation experiments show that we are faced with the intermediate expression swell phenomenon. Starting with a few polynomials of low degree and small coefficients, the algorithm produces a large number of polynomials with huge degrees and enormous coefficients. Moreover, in contrast to the variants of the Euclidean algorithm, the explosion cannot be kept under control. In , Kühnle and Mayr gave an exponential space algorithm for computing a reduced Gröbner basis. The polynomial ideal membership problem over is EXPSPACE-complete.

Let be polynomials over a field with (). If , then

for polynomials for which their degrees are bounded by . The double exponential bound is essentially unavoidable, which is shown by several examples. Unfortunately, in case , the ideal membership problem falls into this category. Fortunately, in special cases better results are available. If (Hilbert's famous Nullstellensatz), then in case , the bound is , while for , the bound is . But the variety is empty if and only if , therefore the solvability problem of a polynomial system is in PSPACE. Several results state that under specific circumstances, the (general) ideal membership problem is also in PSPACE. Such a criterion is for example that is zero-dimensional (contains finitely many isolated points).

In spite of the exponential complexity, there are many successful stories for the application of Gröbner bases: geometric theorem proving, robot kinematics and motion planning, solving polynomial systems of equations are the most widespread application areas. In the following, we enumerate some topics where the Gröbner basis strategy has been applied successfully.

  • Equivalence of polynomial equations. Two sets of polynomials generate the same ideal if and only if their Gröbner bases are equal with arbitrary monomial order.

  • Solvability of polynomial equations. The polynomial system of equations is solvable if and only if .

  • Finitely many solutions of polynomial equations. The polynomial system of equations has a finite number of solutions if and only if in any Gröbner basis of for every variable , there is a polynomial such that its leading term with respect to the chosen monomial order is a power of .

  • The number of solutions. Suppose that the system of polynomial equations has a finite number of solutions. Then the number of solutions counted with multiplicityes is equal to the cardinality of the set of monomials that are not multiples of the leading monomials of the polynomials in the Gröbner basis, where any monomial order can be chosen.

  • Simplification of expressions.

We show an example for the last item.

Example 6.16 Let be given such that

Compute the value of . So let and be elements of and let , . Then the Gröbner basis of is

Since , the answer to the question follows.

Exercises

6.3-1 Prove that the orders and are monomial orders.

6.3-2 Let be a monomial order on , . Prove the following:

a. ,

b. if , then , where equality holds if .

6.3-3 Let .

a. Determine the order of the monomials in for the monomial orders , and with in all cases.

b. For each of the three monomial orders from (), determine , , and .

6.3-4 Prove Dickson's lemma.

6.3-5 Compute the Gröbner basis and the reduced Gröbner basis of the ideal using the monomial order , where . Which of the following polynomials belong to : ?