Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 23-31.

A New Algorithm for the Quillen-Suslin Theorem

Reinhard C. Laubenbacher Cynthia J. Woodburn

Department of Mathematics, New Mexico State University Las Cruces, NM 88003, USA e-mail: reinhard@nmsu.edu

Department of Mathematics, Pittsburg State University Pittsburg, KS 66762-7502, USA e-mail: cwoodbur@pittstate.edu

Abstract. In this paper we present a new algorithm for the Quillen-Suslin Theorem for polynomial rings. MSC 1991: 13C10, 13P10, 19A49 Keywords: Gröbner basis, polynomial ring, projective module, Quillen-Suslin Theorem

1. Introduction

In 1955, J.-P. Serre remarked [12, p. 243] that it was not known whether there exist finitely generated projective modules over k[x_{1}, …, x_{r}], k a field, which are not free. This remark turned into the “Serre Conjecture”, stating that indeed there were no such modules. Proven independently in 1976 by D. Quillen [11] and by A. A. Suslin [13], it became subsequently known as the Quillen-Suslin Theorem (QS).

Several algorithms have been given for QS [9, 3, 4]. Given a suitable presentation of a finitely generated projective module over k[x_{1}, …, x_{r}], k a field, these algorithms produce a free basis for the module. Such algorithms might be of interest in applications of QS to problems within as well as outside mathematics. See [15] for applications of QS to problems in control theory. To mention an application to the solution of linear systems of equations with

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2000 Heldermann Verlag

24 Laubenbacher, R. C.; Woodburn, C. J.: A New Algorithm for the Quillen-Suslin Theorem

polynomial coefficients, one may interpret the theorem as follows. Let A be an n × m-matrix with entries in R = k[x_{1}, …, x_{r}], and let

A · y = 0

be a system of linear equations. Define a module P via the presentation

R^{m} ⟶^{A} R^{n} ⟶ P ⟶ 0,

and suppose that P is a projective R-module. Then the Quillen-Suslin Theorem implies that the solution space of the system Ay = 0 has a free basis, and an algorithm for the theorem will compute such a free basis.

This paper contains a new algorithm for QS. It is a variant of the algorithm in [9], and appears implicitly in [7], which contains a more general algorithm for the Quillen-Suslin Theorem for seminormal monoid rings, based on results in [5]. (See also [14].)

All rings which appear are either subrings of polynomial rings over a field, quotients of polynomial rings, or localizations thereof. Thus, all required computations can be carried out using the theory of Gröbner bases, as described in [1], [2], [8]. Since the study of projective modules is properly part of algebraic K-theory, the present paper may be considered a contribution to the computational side of that subject.

Following is a precise statement of the result.

Theorem 1.1. Let k be a field, and P a finitely generated R = k[x_{1}, …, x_{r}]-module, given as the kernel or cokernel of a matrix with entries in R. Then there is an algorithm to test whether P is projective, in which case it computes a free basis for P.

In order to put the result of the present paper in context we describe briefly the algorithm in [9]. It proceeds by induction on the number of variables. In the case of a polynomial ring in one variable, one can use the Smith normal form algorithm. Suppose the theorem is true for all polynomial rings in less than or equal to r variables over any field. Now consider the polynomial ring

R[y] = k[x_{1}, …, x_{r}][y]

in r + 1 variables. The first step in [9] is to reduce the problem to the case of a stably free module. Recall that, for a ring S, a projective S-module P is stably free, if P ⊕ S^{n} ≅ S^{m} for some non-negative integers n and m. Using Gröbner basis techniques, one can compute a free resolution for an arbitrary projective S-module. All the cokernels of the maps in the resolution are projective, so, in particular, the cokernel of the last map in the resolution is stably free. With an algorithm to find free bases for stably free modules, one can now construct a shorter free resolution for P. Proceeding inductively, one obtains a free resolution

0 ⟶ R^{n} ⟶ R^{m} ⟶ P ⟶ 0

of P, from which one can compute a free basis. If P is stably free, then we can assume that the matrix in Theorem 1.1 is unimodular, that is, has a left inverse. Given such a unimodular matrix, its left inverse can be computed with standard Gröbner basis methods (see [9, pp. 236–237]).

The next step in the algorithm is to reduce the problem to that of finding a free basis for the localized modules P_{M} over the rings

k[x_{1}, …, x_{r}]_{M}[y],

for a suitable finite collection of maximal ideals M of k[x_{1}, …, x_{r}]. These free bases for the local modules are then “patched together” to obtain a basis for the module P.

In this paper we present an alternative algorithm for the local problem, that is, to find a free basis for the module P_{M} over k[x_{1}, …, x_{r}]_{M}[y], for a maximal ideal M ⊂ k[x_{1}, …, x_{r}]. We conclude the paper with an example.

2. The local algorithm

Proposition 2.1. Let P be a finitely generated k[x_{1}, …, x_{r}, y]-module, given as the kernel or cokernel of a matrix C with entries in k[x_{1}, …, x_{r}, y]. Let M be a maximal ideal of k[x_{1}, …, x_{r}]. Then there is an algorithm which tests whether P_{M} is projective, in which case it computes a free basis for it.

The conceptual basis for the algorithm is a version of Roberts’ Theorem (even though we will not explicitly use it).

Theorem 2.2. ([14, Theorem 3.2]) Let R be a commutative local ring with maximal ideal M. Let A be an R-algebra, and let P be a finitely generated A-module. Let S be a central multiplicative set of A which is regular on A and on P. Let n be a nonnegative integer. Assume

(1) If f ∈ S, then A/fA is finite over R.

(2) GL_{n}(A_{S}) \ GL_{n}(\overline{A_{S}})/GL_{n}(\overline{A}) = \{1\}, where \overline{A} = A/MA.

(3) There is an R-subalgebra B ⊂ A_{S} with A_{S} = A + B and MB ⊂ J(B), where J(B) is the Jacobson radical of B.

(4) P_{S} ≅ A_{S}^{n} and \overline{P} ≅ \overline{A}^{n}. Then P ≅ A^{n}.

Let R = k[x_{1}, …, x_{r}]_{M} and A = R[y]. To simplify notation, denote the localization of P at M again by P. Let S ⊂ A be the multiplicative set of polynomials, which, when viewed as a polynomial in y, have leading coefficient a unit in R. Taking quotients modulo M, we obtain the commutative diagram

\begin{matrix}A & ⟶ & A_{S} \\ ↓ & & ↓ \\ \overline{A} & ⟶ & \overline{A_{S}}. \end{matrix}

Here \overline{A} = A/MA = k′[y] is a polynomial ring in one variable over the field k′ = k[x_{1}, …, x_{r}]/M. Furthermore, the localization A_{S} can be described as

A_{S} = (k[x_{1}, …, x_{r}]_{M}[y])_{S} = k(y)[x_{1}, …, x_{r}]M̃,

where M̃ is the extension of the maximal ideal M to the polynomial ring over the larger field k(y). Since there are finitely many maximal ideals N_{1}, …, N_{s} of k(y)[x_{1}, …, x_{r}] lying over M, it follows that A_{S} is a semi-local ring. Furthermore, it is the localization of a polynomial ring in r variables, which will allow us to apply our induction hypothesis later on. Consequently,

\overline{A_{S}} = ∏_{i=1}^{s} k(y)[x_{1}, …, x_{r}]/N_{i}

is a product of fields, each of which contains k′. The kernel of the right-hand vertical projection is equal to the intersection of the N_{i}, which is the Jacobson radical of A_{S}.

Outline of the proof of Proposition 2.1. We will only present the proof for a module presented as the kernel of a matrix with polynomial entries. The proof for a cokernel is entirely similar. The proof proceeds by induction on the number of variables of A. A polynomial ring in one variable over a field is a PID, so we can apply the Smith normal form algorithm to C to check whether P is projective, and to compute a free basis for it. Now assume the proposition is true for polynomial rings in r variables over a field. Suppose we are given the following presentation:

0 ⟶ P ⟶ k[x_{1}, …, x_{r}, y]^{m} ⟶^{C} k[x_{1}, …, x_{r}, y]^{n}

of P.

First assume that P_{M} is projective. Using the reduction algorithm in [9] we can assume that P_{M} is stably free. If we reduce modulo the maximal ideal M we get a projective module \overline{P_{M}} over the principal ideal domain k′[y]. Using the Smith normal form algorithm, we find a free basis ū_{1}, …, ū_{t} for \overline{P_{M}} over \overline{A}. Extending scalars from \overline{A} to \overline{A_{S}}, we obtain a free basis ū_{1}, …, ū_{t} of \overline{(P_{M})_{S}} over \overline{A_{S}}. Now lift the elements ū_{1}, …, ū_{t} to elements u_{1}, …, u_{t} ∈ P_{M} ⊂ (P_{M})_{S}, using normal forms with respect to a Gröbner basis for M ⊂ k[x_{1}, …, x_{r}].

To simplify notation, denote P_{M} by P. The module P_{S} over A_{S} has the same presentation matrix C as P. Since A_{S} is the localization of a polynomial ring in r variables, P_{S} is free by induction, and we can find a free basis v_{1}, …, v_{t}. Let \overline{v_{1}}, …, \overline{v_{t}} be the induced basis of \overline{P}_{S} over the product of fields \overline{A_{S}}. Let \overline{W} be a base change matrix that transforms the basis \{\overline{v_{i}}\} into the basis \{ū_{i}\}. It is possible to lift \overline{W} to a matrix W over A_{S}, which restricts to an invertible matrix on the image of C. Transforming the basis {v_{1}, …, v_{t}} via W, we obtain another free basis of P_{S}, again denoted by {v_{i}}, which maps to the basis {ū_{i}} over \overline{A_{S}}. Hence the differences u_{i} − v_{i} lie in the radical of P_{S}. We can now transform the v_{i} into a free A_{S}-basis of P_{S} which is actually contained in P ⊂ P_{S}, so they also form a free A-basis of P.

If P = P_{M} is not projective, then the algorithm fails to either find a free basis for \overline{P} or for P_{S}. Thus, it can be used to test P_{M} for projectivity.

Proof. To begin the proof, assume that P is projective. Using the reduction algorithm in [9] we can assume further that P is in fact stably free, that is, C has a right inverse

D : A^{n} ⟶ A^{m},

such that CD is the identity on A^{n}. Let S be the multiplicative subset of A consisting of those elements which are monic when viewed as polynomials in y. Consider the ring

A_{S} = (k[x_{1}, …, x_{r}]_{M}[y])_{S} = k(y)[x_{1}, …, x_{r}]M̃.

Let

0 ⟶ P ⟶ A_{S}^{m} ⟶^{C} A_{S}^{n} ⟶ 0

be the presentation of P_{S} obtained from C by extending scalars to A_{S}. Our goal is to find a free basis for P_{S}. Since C has a right inverse, we have an effective decomposition

A_{S}^{m} ≅ ker(C) ⊕ A_{S}^{n} = P_{S} ⊕ A_{S}^{n},

given by x = (x − DCx) + DCx for all x ∈ A_{S}^{m}. There is a commutative diagram

k[x_{1}, …, x_{r}][y] ⟶ k(y)[x_{1}, …, x_{r}]
↓  ↓
k[x_{1}, …, x_{r}]_{M}[y] ⟶  A_{S}.

Thus, the module P_{S} is extended from k(y)[x_{1}, …, x_{r}]. By induction, we can find a free basis for projective modules over this ring. Thus, we can extend P to this ring, find a free basis, and then extend to A_{S}. In this way we obtain a free basis v_{1}, …, v_{t} of P_{S}.

We now construct the elements u_{i} ∈ P ⊂ P_{S}. First we reduce the above presentation matrix C over A modulo M to obtain a presentation matrix over

k[x_{1}, …, x_{r}]_{M}[y]/M = k′[y].

Since k′[y] is a principal ideal domain, we can use the Smith normal form algorithm to find an invertible matrix U such that

\overline{C}U = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) ,

where I is an (m × m)-identity matrix. Then the last t = n − m rows of U^{−1} form a free basis ū_{1}, …, ū_{t} for \overline{P}.

We now choose a term order for k[x_{1}, …, x_{r}] and compute a Gröbner basis for the ideal M ⊂ k[x_{1}, …, x_{r}]. Now compute normal forms in k[x_{1}, …, x_{r}] for the polynomials in the entries of ū_{i}. Using these normal forms we obtain elements

u_{1}, …, u_{t} ∈ A^{m},

which map onto the basis for \overline{P}. We modify the u_{i} by elements in M · A^{m}, so that they lie in P as follows. If we replace u_{i} by u_{i} − DCu_{i}, then

C(u_{i} − DCu_{i}) = Cu_{i} − (CD)Cu_{i} = 0.

Thus, we have elements u_{i} ∈ P ⊂ P_{S} which map onto the initial free basis \{ū_{i}\} of \overline{P}.

Now consider the basis \{ū_{i}\} of \overline{P_{S}}. Since \overline{A_{S}} is a product of fields we can compute base change matrices in each component and use the Chinese Remainder Theorem to assemble them to a base change matrix \overline{W} ∈ GL_{t}(\overline{A_{S}}) which maps \{v̄_{i}\} to \{ū_{i}\}. We compute normal forms of the polynomials making up the entries of \overline{W} with respect to the Gröbner basis of M. Using these normal forms we can lift \overline{W} to a matrix

W : A_{S}^{m} ⟶ A_{S}^{m}.

Now replace W by W − DCW. The new W still reduces to the old \overline{W}, and, furthermore, C(W − DCW) = 0. While this new W need not be invertible, it restricts to an invertible transformation on P_{S}. Now replace the basis v_{1}, …, v_{t} of P_{S} by the basis W v_{1}, …, W v_{t}. Then for this new basis \{v_{i}\} of P_{S} we have that ū_{i} = \overline{v_{i}} for all i. Consequently, the differences u_{i} − v_{i} lie in the radical of P_{S}. Using the division algorithm we decompose u_{i} − v_{i} as the sum

u_{i} − v_{i} = f_{i} − g_{i},

where f_{i} ∈ A^{m}, and the degrees of the denominators of the entries in g_{i} are greater than or equal to the degrees of the numerators. Then

u_{i} − f_{i} = v_{i} − g_{i},

so that v_{i} − g_{i} is denominator-free (with respect to elements in S). Replace v_{i} by v_{i} − g_{i}. The new v_{i} are still linearly independent since they map to a free basis modulo the Jacobson radical of A_{S}. If we now further alter the v_{i} by replacing them with

v_{i} − DCv_{i},

then the new v_{i} are still linearly independent and lie in P ⊂ P_{S}. Furthermore, they differ from the initial basis for P_{S} by elements in rad(A_{S})P_{S}, hence they form a free basis for P_{S}. Also, we still have that ū_{i} = \overline{v_{i}} is a free basis for \overline{P} over \overline{A}.

Now consider the free A-submodule P′ of P generated by v_{1}, …, v_{t}. Since \overline{v_{i}} = ū_{i} generates \overline{P}, it follows that

P = P′ + rad(A)P.

Nakayama’s Lemma implies that P′ = P. Hence we have found a free basis for P. If P is not projective, then the algorithm fails to find a free basis for either \overline{P} or P_{S}. □

3. An example

Consider the polynomial ring ℚ[x, y]. Let M be the maximal ideal of ℚ[x] generated by x − 1, and let P = P_{M} be the stably free A = ℚ[x]_{⟨x−1⟩}[y]-module given by the kernel of the unimodular row C = (x^{2}y + 1, x + y − 2, 2xy). Notice that D = (1, 0, −x/2)^{t} is a right inverse of C.

First we find elements ū_{i} which form a free basis of \overline{P_{S}}. Reducing C modulo ⟨x − 1⟩, we obtain \overline{C} = (y + 1, y − 1, 2y). Computing the Smith normal form of \overline{C} yields

(1, 0, 0) = \overline{C}U
= \overline{C} · ( \begin{matrix}1 & −y + 1 & −1 \\ 0 & y + 1 & −1 \\ −\frac{1}{2} & 0 & 1 \end{matrix} )

So, the last two columns of U form a free basis ū_{1} = (−y + 1, y + 1, 0)^{t}, ū_{2} = (−1, −1, 1)^{t} for \overline{P}.

Now lift these to elements u_{1} = (−y + 1, y + 1, 0)^{t}, u_{2} = (−1, −1, 1)^{t} over A, and then modify them so that they lie in P by replacing each u_{i} by u_{i} − DCu_{i}:

u_{1} = (y + 2 + x^{2}y^{2} − x^{2}y − xy − x − y^{2}, y + 1, \frac{−x}{2} (x^{2}y^{2} − x^{2}y + 2y + 1 − xy − x − y^{2}))^{t}
u_{2} = (−2 + x^{2}y + x + y − 2xy, −1, \frac{1}{2} (2 − x^{3}y + x − x^{2} − xy + 2x^{2}y))^{t} .

Next, using Gaussian elimination, we find

V = ( \begin{matrix}1 & −x − y + 2 & −2xy \\ 0 & 1 & 0 \\ \frac{−x}{2} & \frac{x}{2} (x + y − 2) & x^{2}y + 1 \end{matrix} ) ,

with CV = (1, 0, 0). Thus, the last two columns of V,

v_{1} = (−x − y + 2, 1, \frac{x}{2} (x + y − 2))^{t} ,

and

v_{2} = (−2xy, 0, x^{2}y + 1)^{t} ,

form a free basis of P_{S}, and \overline{v_{1}} = (−y + 1, 1, \frac{1}{2} (y − 1))^{t}, \overline{v}_{2} = (−2y, 0, y + 1)^{t} form a free

basis of \overline{P_{S}}. (Notice that \{v_{1}, v_{2}\} is actually a free basis for P. We continue with the example, however, in order to demonstrate the algorithm.)

A base change matrix \overline{W}, which maps \{\overline{v_{i}}\} to \{ū_{i}\}, is

( \begin{matrix}−\frac{1}{2} & −y + 1 & −1 \\ −\frac{1}{2} & y + 1 & −1 \\ \frac{2y + 1}{2y} & \frac{y − 1}{2y} & 2 \end{matrix} )

which has determinant 1. Lifting \overline{W} to A_{S}, we obtain the same matrix W. Now replace W with W = W − DCW =

( \begin{matrix}\frac{1}{2}(x^{2}y − x + y − 4xy − 2) & y + 2 + x^{2}y^{2} − x^{2}y − 2xy − y^{2} & x^{2}y + x + y − 4xy − 2 \\ −1/2 & y + 1 & −1 \\ W_{3,1} & W_{3,2} & W_{3,3} \end{matrix} ) ,

with

W_{3,1} = \frac{1}{4y} (4y + 2 − x^{3}y^{2} + xy + x^{2}y − xy^{2} + 4x^{2}y^{2}),
W_{3,2} = \frac{1}{2y} (y − 1 − x^{3}y^{3} + x^{3}y^{2} − 2xy^{2} − xy + 2x^{2}y^{2} + xy^{3}),
W_{3,3} = \frac{1}{2}(4 − x^{3}y + x − x^{2} − xy + 4x^{2}y).

Although W is not invertible, when restricted to P_{S}, it gives an invertible transformation. Next, replace v_{1} with W v_{1} =

( \begin{matrix}\frac{1}{2} & (6y+4x−3x^{2}y^{2}−3x^{2}−16xy−7x^{3}y+14x^{2}y−3y^{2}+x^{3}+x^{3}y^{2}+5xy^{2}+x^{4}y) \\ \frac{1}{2} & (3x+3y−x^{2}−xy) \\ \frac{−1}{4y} & (2x−8y−2−15x^{2}y^{2}+12xy−2x^{3}y−3x^{2}y+4y^{2}−3x^{3}y^{3}+14x^{3}y^{2}+3xy^{2}−3xy^{3}+x^{4}y−7x^{4}y^{2}+5x^{2}y^{3}+x^{5}y^{2}+x^{4}y^{3}) \end{matrix} ) ,

and v_{2} with

W v_{2} = ( \begin{matrix}& −2xy−5x^{3}y^{2}−xy^{2}+5x^{2}y^{2}−2+x^{4}y^{2}+x^{3}y+x+y \\ & xy−1−x^{2}y \\ \frac{1}{2} & (−5xy−x+5x^{4}y^{2}+7x^{2}y−x^{3}y+x^{2}y^{2}−5x^{3}y^{2}+4−x^{5}y^{2}−x^{4}y−x^{2}) \end{matrix} ) .

Notice that the following differences lie in the radical of P_{S}: u_{1} − v_{1} =

( \begin{matrix}\frac{1}{2} & (−4y+4+7x^{3}y+5x^{2}y^{2}−16x^{2}y+3x^{2}+14xy+y^{2}−5xy^{2}−6x−x^{4}y−x^{3}y^{2}−x^{3}) \\ \frac{1}{2} & (−y+2−3x+x^{2}+xy) \\ \frac{1}{4y} & (2x−8y−13x^{2}y^{2}+10xy−2x^{3}y−x^{2}y+4y^{2}−2−5x^{3}y^{3}+16x^{3}y^{2}−xy^{2}−xy^{3}+x^{4}y−7x^{4}y^{2}+5x^{2}y^{3}+x^{5}y^{2}+x^{4}y^{3}) \end{matrix} )

= (x − 1) · ( \begin{matrix}\frac{1}{2} & (−x^{3}y+6x^{2}y−x^{2}y^{2}−x^{2}+4xy^{2}−10xy+2x+4y−y^{2}−4) \\ \frac{1}{2} & (x+y−2) \\ \frac{1}{4y} & (x^{4}y^{2}+x^{3}y−6x^{3}y^{2}+x^{3}y^{3}−x^{2}y−4x^{2}y^{3}+10x^{2}y^{2}−2xy−3 xy^{2}+xy^{3}+2−4y^{2}+8y) \end{matrix} )

and

u_{2} − v_{2} = ( \begin{matrix}x^{2}y+5x^{3}y^{2}+xy^{2}−5x^{2}y^{2}−x^{4}y^{2}−x^{3}y \\ −xy+x^{2}y \\ \frac{1}{2} (2x−2+4xy−5x^{2}y−5x^{4}y^{2}−x^{2}y^{2}+5x^{3}y^{2}+x^{5}y^{2}+x^{4}y) \end{matrix} )

= (x − 1) · ( \begin{matrix}−(x^{2}y−4xy+x+y)xy \\ xy \\ \frac{1}{2} (x^{4}y^{2}−4x^{3}y^{2}+x^{3}y+x^{2}y^{2}+x^{2}y−4xy+2) \end{matrix} ) .

So, ignoring the denominator-free part of u_{1} − v_{1} and u_{2} − v_{2}, respectively, we have g_{1} = (0, 0, \frac{x − 1}{−2y})^{t} and g_{2} = (0, 0, 0)^{t}. Then v_{2} = v_{2} − g_{2} and replacing v_{1} with v_{1} − g_{1} yields

v_{1} = ( \begin{matrix}\frac{1}{2} & (6y+4x+x^{3}−3x^{2}y^{2}−3x^{2}−16xy−7x^{3}y+14x^{2}y−3y^{2}+x^{3}y^{2}+5xy^{2}+x^{4}y) \\ \frac{1}{2} & (3x+3y−x^{2}−xy) \\ \frac{1}{4} & (8+15x^{2}y−12x+2x^{3}+3x^{2}−4y+3x^{3}y^{2}−14x^{3}y−3xy+3xy^{2}−x^{4}+7x^{4}y−5x^{2}y^{2}−x^{5}y−x^{4}y^{2}) \end{matrix} )

To move v_{1} back to P = ker C, replace v_{1} with v_{1} − DCv_{1}. Then

v_{1} = ( \begin{matrix}\frac{1}{2} & (6x+6y−16xy−3x^{2}y^{2}+x^{3}y^{2}+5xy^{2}+14x^{2}y−7x^{3}y−5x^{2}+x^{3}−3y^{2}+x^{4}y) \\ \frac{1}{2} & (3x+3y−x^{2}−xy) \\ \frac{1}{4} (8−12x+15x^{2}y−14x^{3}y−3xy+x^{2}+4x^{3}+3xy^{2}+3x^{3}y^{2}−4y+7x^{4}y−5x^{2}y^{2}−x^{4}−x^{5}y−x^{4}y^{2}) \end{matrix} )

and

v_{2} = ( \begin{matrix}−2xy−5x^{3}y^{2}−xy^{2}+5x^{2}y^{2}−2+x^{4}y^{2}+x^{3}y+x+y \\ xy−1−x^{2}y \\ \frac{1}{2} (−5xy−x+5x^{4}y^{2}+7x^{2}y−x^{3}y+x^{2}y^{2}−5x^{3}y^{2}+4−x^{5}y^{2}−x^{4}y−x^{2}) \end{matrix} )

lie in P and form the desired free basis.

References

[1] Adams, W.; Loustaunau, P.: An Introduction to Gröbner Bases. Amer. Math. Soc., Graduate Studies in Math. 3, Providence 1994.

[2] Cox, D.; Little, J.; O’Shea, D.: Ideals, Varieties, and Algorithms. Undergrad. Texts in Math., Springer Verlag, New York 1992.

[3] Fitchas, N. (working group): Algorithmic Aspects of Suslin’s Proof of Serre’s Conjecture. Comp. Complexity 3 (1993), 31–55.

[4] Fitchas, N.; Galligo, A.: Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel. Math. Nachr. 149 (1990), 231–253.

[5] Gubeladze, I. Dzh.: Anderson’s Conjecture and the Maximal Monoid Class Over Which Projective Modules Are Free. Math. USSR Sbornik 63 (1989), 165–180.

[6] Lam, T. Y.: Serre’s Conjecture. Lecture Notes in Math. 635, Springer Verlag, New York 1978.

[7] Laubenbacher, R. C.; Woodburn, C. J.: An Algorithm for the Quillen-Suslin Theorem for Monoid Rings. J. Pure Appl. Algebra, to appear.

[8] Logar, A.: Computational Aspects of the Coordinate Ring of an Algebraic Variety. Comm. Algebra 18 (1990), 2641–2662.

[9] Logar, A.; Sturmfels, B.: Algorithms for the Quillen-Suslin Theorem. J. Algebra 145 (1992), 231–239.

[10] Park, H.; Woodburn, C.: An Algorithmic Proof of Suslin’s Stability Theorem for Polynomial Rings. J. Algebra 178 (1995), 277–298.

[11] Quillen, D.: Projective Modules Over Polynomial Rings. Invent. Math. 36 (1976), 167– 171.

[12] Serre, J.-P.: Faisceaux Algébriques Cohérents. Ann. Math. 61 (1955), 191–278.

[13] Suslin, A. A.: Projective Modules Over a Polynomial Ring Are Free. Soviet Math. Dokl. 17 (1976), 1160-1164.

[14] Swan, R. G.: Gubeladze’s Proof of Anderson’s Conjecture. Contemporary Mathematics 124, Amer. Math. Soc. 1992, 215–250.

[15] Youla, D. C.; Pickel, P. F.: The Quillen-Suslin Theorem and the Structure of n-Dimensional Elementary Polynomial Matrices. IEEE Trans. on Circuits and Systems 31 (1994), 513–517.

Received February 24, 1997; revised version March 23, 1999