Go to previous page Go up Go to next page

4.4 Gröbner basis

The first step is to obtain the Gröbner basis for the ideal U generated by the coefficients in Equation (27View Equation):
2 2 u1 = 1 - D1D2D3, u2 = D1D3 - D2, u3 = D1(1 - D3), u4 = 1- D 1. (28)
The ideal U consists of linear combinations of the form sum viui where vi, i = 1,...,4 are polynomials in the ring R. There can be several sets of generators for U. A Gröbner basis is a set of generators which is ‘small’ in a specific sense.

There are several ways to look at the theory of Gröbner basis. One way is the following: Suppose we are given polynomials g1,g2,...,gm in one variable over say Q and we would like to know whether another polynomial f belongs to the ideal generated by the g’s. A good way to decide the issue would be to first compute the gcd g of g 1, g 2, …, g m and check whether f is a multiple of g. One can achieve this by doing the long division of f by g and checking whether the remainder is zero. All this is possible because Q[x] is a Euclidean domain and also a principle ideal domain (PID) wherein any ideal is generated by a single element. Therefore we have essentially just one polynomial - the gcd - which generates the ideal generated by g1,g2,...,gm. The ring of integers or the ring of polynomials in one variable over any field are examples of PIDs whose ideals are generated by single elements. However, when we consider more general rings (not PIDs) like the one we are dealing with here, we do not have a single gcd but a set of several polynomials which generates an ideal in general. A Gröbner basis of an ideal can be thought of as a generalization of the gcd. In the univariate case, the Gröbner basis reduces to the gcd.

Gröbner basis theory generalizes these ideas to multivariate polynomials which are neither Euclidean rings nor PIDs. Since there is in general not a single generator for an ideal, Gröbner basis theory comes up with the idea of dividing a polynomial with a set of polynomials, the set of generators of the ideal, so that by successive divisions by the polynomials in this generating set of the given polynomial, the remainder becomes zero. Clearly, every generating set of polynomials need not possess this property. Those special generating sets that do possess this property (and they exist!) are called Gröbner bases. In order for a division to be carried out in a sensible manner, an order must be put on the ring of polynomials, so that the final remainder after every division is strictly smaller than each of the divisors in the generating set. A natural order exists on the ring of integers or on the polynomial ring Q(x); the degree of the polynomial decides the order in Q(x). However, even for polynomials in two variables there is no natural order a priori (is x2 + y greater or smaller than x + y2?). But one can, by hand as it were, put an order on such a ring by saying x » y, where » is an order, called the lexicographical order. We follow this type of order, D1 » D2 » D3 and ordering polynomials by considering their highest degree terms. It is possible to put different orderings on a given ring which then produce different Gröbner bases. Clearly, a Gröbner basis must have ‘small’ elements so that division is possible and every element of the ideal when divided by the Gröbner basis elements leaves zero remainder, i.e. every element modulo the Gröbner basis reduces to zero.

In the literature, there exists a well-known algorithm called the Buchberger algorithm which may be used to obtain the Gröbner basis for a given set of polynomials in the ring. So a Gröbner basis of U can be obtained from the generators u i given in Equation (28View Equation) using this algorithm. It is essentially again a generalization of the usual long division that we perform on univariate polynomials. More conveniently, we prefer to use the well known application Mathematica. Mathematica yields a 3-element Gröbner basis G for U:

G = {D23- 1, D22 - 1,D1 - D2D3}. (29)
One can easily check that all the ui of Equation (28View Equation) are linear combinations of the polynomials in G and hence G generates U. One also observes that the elements look ‘small’ in the order mentioned above. However, one can satisfy oneself that G is a Gröbner basis by using the standard methods available in the literature. One method consists of computing the S-polynomials (see Appendix A) for all the pairs of the Gröbner basis elements and checking whether these reduce to zero modulo G.

This Gröbner basis of the ideal U is then used to obtain the generators for the module of syzygies. Note that although the Gröbner basis depends on the order we choose among the Dk, the module itself is independent of the order [2Jump To The Next Citation Point].

  Go to previous page Go up Go to next page