AN ALGORITHM FOR THE QUILLEN-SUSLIN

THEOREM FOR MONOID RINGS

Reinhard C. Laubenbacher and Cynthia J. Woodburn

Abstract. Let k be a field, and let M be a commutative, seminormal, finitely generated monoid, which is torsionfree, cancellative, and has no nontrivial units. J. Gubeladze proved that finitely generated projective modules over kM are free. This paper contains an algorithm for finding a free basis for a finitely generated projective module over kM. As applications one obtains alternative algorithms for the Quillen-Suslin Theorem for polynomial rings and Laurent polynomial rings, based on Quillen’s proof.

I. Introduction

In 1955, J.-P. Serre remarked in [Se, p. 243] that it was not known whether there exist finitely generated projective modules over k[x_{1}, …, x_{n}], 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 [Qu] and by A. A. Suslin [Su], it became subsequently known as the Quillen-Suslin Theorem (QS).

In 1978, D. F. Anderson [An] conjectured that QS holds for affine normal subrings of polynomial rings generated by monomials, that is, all finitely generated projective modules over such rings are free. In 1988, J. Gubeladze [Gu] proved this conjecture, and showed that QS holds exactly for monoid rings of seminormal monoids. For normal monoids, this says in geometric language that algebraic vector bundles over affine toric varieties are trivial (see [Fu, p. 31]).

Several algorithms have been given for QS over polynomial rings [LS, F, FG]. Given a finitely generated projective module over k[x_{1}, …, x_{n}], k a field, presented, for instance, as the cokernel of a matrix with polynomial entries, these algorithms produce a free basis for the module. They are all based on Suslin’s proof and proceed by first reducing the problem to considering a unimodular row. See [YP] for applications of these algorithms to problems in signal processing. This paper contains an algorithm for QS over seminormal monoid rings, which we will call the QS-Algorithm. One way to interpret this algorithm in a special case is that if A is a polynomial d × n-matrix whose entries are “sparse” polynomials, in the sense that the appearing monomials lie in a pre-specified submonoid of ℕ^{n}, and suppose that

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 13C10, 13P10, 14Q15, 19A49.

Key words and phrases. affine toric variety, Gröbner basis, monoid ring, projective module, Quillen-Suslin Theorem.

The authors would like to thank Bernd Sturmfels for suggesting the problem, and for helpful discussions. The first author would like to thank Joseph Gubeladze for several helpful conversations. Finally, thanks are due to several referees for their comments.

the (d × d)-minors of A span the unit ideal, then the QS-algorithm produces n − d polynomial vectors with the same “monomial sparsity pattern” which freely span the cokernel of A. As a corollary we obtain a QS-algorithm for Laurent polynomial rings (Corollary 8.2). Such an algorithm was first given by H. Park [Pa]. We also obtain an alternative version of the QS-algorithm for polynomial rings (Corollary 5.8). It differs from the existing algorithms in that it relies on Quillen’s proof. All essential ingredients of the algorithm are implicitly (and, in some cases, explicitly) contained in [Gu] and R. Swan’s exposition [S2] of Gubeladze’s result. All rings which appear are either subrings of polynomial rings over a field, or 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 [AL], [CLO], [Lo]. 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 this subject.

Following is a precise statement of the result.

Theorem 1.1. Let k be a field, and let M be a finitely generated, commutative, torsionfree, seminormal, cancellative monoid without nontrivial units. If P is a finitely generated projective kM-module, given as the cokernel of a matrix with entries in kM, then there is an algorithm to compute a free basis for P.

We will call such monoids toric, since, if M is normal, then their monoid rings kM are the coordinate rings of affine toric varieties. The contents of the paper are as follows. Section 2 contains a summary of definitions and results [Gu, S2] pertaining to toric monoids that will be needed subsequently. In Section 3 we describe algorithms to carry out “Milnor patching” for certain kinds of pullback squares. Precisely, given a commutative square of rings

R ⟶ R_{1}
↓  ↓
R_{2} ⟶ R̄

such that

R ≅ {(r_{1}, r_{2}) ∈ R_{1} × R_{2} | r̄_{1} = r̄_{2} in R̄},

then, with certain extra hypotheses, projective modules over R can be obtained by “patching together” pairs of projective modules over R_{1} and R_{2}.

In Section 4, we reduce the problem for normal toric monoids M to finding an algorithm for the “interior” submonoid M^{∗} of M. In Section 7, we construct a sequence of monoids

M = M_{0}, M_{1}, …, M_{k} = F,

ending in a free monoid F. In Sections 5 and 6 we construct subalgorithms to show that this sequence has the property that projective modules over kM_{i} are obtained from projective modules over kM_{i+1} by restriction or extension of scalars. Since kF is just a polynomial ring, we can use the Logar-Sturmfels algorithm for the ordinary QS.

In Section 8, we summarize the different steps of the algorithm in their natural order. As an application we give an algorithm for QS for Laurent polynomial rings, first proven by Swan [S1].

The QS-algorithm proceeds by induction on the rank of the monoid M. If rk(M) = 1, then kM is simply a polynomial ring in one variable over k, so the desired algorithm is just the Smith normal form algorithm. Thus, we will from now on assume the following:

Induction Hypothesis 1.2. There is a QS-algorithm for all fields and all toric monoids of rank less than the rank of M.

II. Toric Monoids

All monoids in this paper are assumed to be commutative and cancellative. For each monoid M, there exists an abelian group gp(M) which contains M (or at least an isomorphic copy of M), and which is the smallest such group, called the group completion of M. Furthermore, gp(M) is unique up to isomorphism. The rank of M, denoted rk(M), will be defined to be the rank of gp(M). We write ⟨g_{1}, …, g_{t}⟩ to denote the monoid generated by the elements g_{1}, …, g_{t}. Generally, we will write monoids multiplicatively, except in the examples, which are all submonoids of ℕ^{d}.

Definition. A monoid is said to be torsionfree if x = y whenever x^{n} = y^{n} for some integer n > 0. It is cancellative if ax = ay implies x = y.

Definition. A monoid M is seminormal if x ∈ gp(M) and x^{2}, x^{3} ∈ M imply x ∈ M, and normal if x ∈ gp(M) and x^{n} ∈ M for some n > 0 imply x ∈ M. The normalization of a torsionfree monoid M in a group G is

M̃ = {x ∈ G | x^{n} ∈ M for some n > 0}.

Example. An example of a monoid which is seminormal but not normal is

M = ⟨(2, 3), (3, 5), (3, 6), (1, 1), (2, 1)⟩ ⊂ ℕ^{2}.

The normalization of M is M̃ = ⟨(1, 2), (1, 1), (2, 1)⟩.

Definition. We will call a monoid M toric if M is finitely generated, torsionfree, cancellative, seminormal, and has no nontrivial units.

Since a toric monoid M can be naturally embedded in the real vector space ℝ ⊗_{ℤ} gp(M) [S2, p. 224], we can view M as a subset of ℕ^{d}. So a normal toric monoid M can be defined as

M = {(a_{1}, …, a_{d}) ∈ ℕ^{d} | (a_{1}, …, a_{d}) · A ≤ 0},

for some matrix A with d rows, where each row of A corresponds to a bounding hyperplane of M in ℝ^{d} [Fu, p. 9]. For example,

M = ⟨(1, 2), (1, 1), (2, 1)⟩

= \{(a_{1}, a_{2}) ∈ ℕ^{2} | (a_{1}, a_{2}) ( \begin{matrix}−2 & 1 \\ 1 & −2 \end{matrix} ) ≤ (0, 0)\}

has bounding hyperplanes −2x+y = 0 and x−2y = 0 in ℝ^{2}. Whenever M is given in this manner, that is, as the solution set of a system of linear inequalities, it is an integer programming problem to find a minimal generating set for M. Such a generating set, called a Hilbert basis, can be found by means of an algorithm such as the one given in [St, p. 22-23], which uses Gröbner basis theory.

Definition. We define the interior of a monoid M to be

Int(M) = {x ∈ M | for each y ∈ M there exists n > 0, z ∈ M such that x^{n} = yz}.

We use the notation M^{∗} to denote the submonoid Int(M) ∪ {1}. Observe that M^{∗} need not be finitely generated, even if M is. If the rank of M is finite, then M and M^{∗} will have the same rank, however.

Definition. A nonempty submonoid E of a monoid M is extremal whenever x, y ∈ M with xy ∈ E implies x, y ∈ E.

Notice that if we consider M ⊂ ℕ^{d}, it is not difficult to verify that extremal submonoids of a toric monoid M lie on bounding hyperplanes of M [S2, Theorem 5.4].

Lemma 2.1. If M = ⟨g_{1}, …, g_{t}⟩ is a toric monoid with gp(M) = ℤ^{d}, then generators for all extremal submonoids of M can be found.

Proof. We will write M additively. First, we eliminate from consideration those generators of M which lie in Int(M). Since g ∈ Int(M) if and only if M[−g] = {∑_{j=1}^{t} a_{j}g_{j} − bg | a_{j}, b ∈ ℕ} = gp(M) = ℤ^{d} [S2, Lemma 9.5], showing g ∈ Int(M) amounts to solving a system of 2d linear equations over ℕ. Once each generator of M has been tested for membership in Int(M), let S = {s_{1}, …, s_{q}} be the largest subset of generators of M contained in the complement of Int(M).

Next, using the set S = {s_{1}, …, s_{q}}, we begin forming maximal extremal submonoids of M, relying on the fact that if E is an extremal submonoid of M then E ∩ S is a generating set for E [S2, p. 225]. Starting with s_{1}, consider ⟨s_{1}, s_{2}⟩. We need to know whether or not ⟨s_{1}, s_{2}⟩ ∩ Int(M) = ∅. Note ⟨s_{1}, s_{2}⟩ ∩ Int(M) ≠ ∅ if and only if ℤ^{d} = {∑_{j=1}^{t} a_{j}g_{j} − b_{1}s_{1} − b_{2}s_{2} | a_{j}, b_{i} ∈ ℕ}, so again this involves solving linear systems of equations over ℕ. If ⟨s_{1}, s_{2}⟩ ∩ Int(M) = ∅, then ⟨s_{1}, s_{2}⟩ is contained in some extremal submonoid of M [S2, Lemma 5.1]. We can find a maximal such extremal monoid by continuing this process to enlarge the set of generators as much as possible. If ⟨s_{1}, s_{2}⟩ ∩ Int(M) ≠ ∅, then consider ⟨s_{1}, s_{3}⟩. Repeating the process by considering all possible combinations of elements of S, we can obtain all maximal extremal submonoids of M. If we repeat the process on each submonoid so obtained and continue in this manner until the process terminates, we will have obtained the set of all extremal submonoids of M. □

An algorithm to find the maximal faces of M is implemented in the program PORTA (see [Zi, Lecture 0]).

Lemma 2.2. Let M be a toric monoid. Then generators for the normalization of M can be found.

Proof. By [S2, Lemma 6.6], Int(M) = Int(M̃). Let E be an extremal submonoid of M. Notice that M being seminormal implies E is also seminormal. For if x^{2}, x^{3} ∈ E for some x ∈ gp(E), then x ∈ M. Consequently, by the definition of extremal submonoid, x ∈ E. Thus, an extremal submonoid of M̃ is the normalization of an extremal submonoid of M. It is therefore sufficient to find generators for the normalizations of all proper extremal submonoids of M, which can be accomplished by computing Hilbert bases of the bounding hyperplanes of M, since each proper extremal submonoid of M lies on a bounding hyperplane of M [S2, Theorem 5.4]. □

The proof of the following result was suggested by one of the referees.

Lemma 2.3. [S2, Lemma 11.2] Given a toric monoid M = ⟨g_{1}, …, g_{m}⟩, there exists a free monoid F contained inside M^{∗} with gp(F) = gp(M).

Proof. Since gp(M) is a free abelian group, we may assume that it is equal to ℤ^{n} for some n ≥ 1. Choose an element z ∈ Int(M), for instance, let z = g_{1} + ⋯ + g_{m}. Using the Euclidean algorithm, z can be extended to a basis z = z_{1}, …, z_{n} of ℤ^{n}. (Note that this amounts to carrying out a QS-algorithm for ℤ). Now choose N large enough such that z_{i}+Nz_{1} ∈ M^{∗} for all i = 1, …, n. Then z_{1}, z_{2}+Nz_{1}, …, z_{n}+Nz_{1} is a free basis for a free monoid F contained in M^{∗} such that gp(F) = gp(M) = ℤ^{n}. □

Lemma 2.4. Given two normal toric submonoids N_{1} and N_{2} of a toric monoid M, then N_{1} ∩ N_{2} is a normal toric submonoid of M.

Proof. Let N_{1} = {(a_{1}, …, a_{d}) ∈ ℕ^{d} \ {0} | (a_{1}, …, a_{d}) · A_{1} ≤ 0}, and N_{2} = {(a_{1}, …, a_{d}) ∈ ℕ^{d} \ {0} | (a_{1}, …, a_{d}) · A_{2} ≤ 0}, where A_{1} and A_{2} are the coefficient matrices of the systems of linear inequalities corresponding to the bounding hyperplanes of N_{1} and N_{2}, respectively. Then N_{1} ∩ N_{2} = {(a_{1}, …, a_{d}) ∈ ℕ^{d} \ {0} | (a_{1}, …, a_{d})·B ≤ 0}, where B = (A_{1}|A_{2}). Consequently, generators for N_{1}∩N_{2} can be found by computing a Hilbert basis for the system of linear inequalities formed by considering the bounding hyperplanes of both submonoids. □

Definition. Let M be a normal toric monoid and let ψ : M → ℕ be a homomorphism with ψ^{−1}(0) = {1}. (For example, ψ might be the defining equation for a hyperplane H such that H ∩M = {1}.) Let m be a positive integer and z ∈ Int(M). Then the homothetic transformation with center z is the map

θ_{m} : M → M
x ↦ x^{m}z^{ψ(x)}.

A homothetic submonoid of M with center z, denoted M^{(m)}, is the normalization of the image θ_{m}(M) in gp(M).

Lemma 2.5. Let M = ⟨g_{1}, …, g_{t}⟩ be a normal toric monoid and z ∈ Int(M). Then a finite generating set for the m-th homothetic submonoid M^{(m)} of M can be found.

Proof. By Lemma 2.1, we can find generators for each of the maximal extremal submonoids {E_{1}, …, E_{p}} of M. Note that the generators of each E_{i} lie on some bounding hyperplane of M [S2, Theorem 5.4]. Therefore, the images of the generators of E_{i} under the homothetic transformation will lie on a bounding hyperplane of M^{(m)}. Thus, M^{(m)} is the solution set to the system of linear inequalities resulting from applying the homothetic transformation to each E_{i}, and computing a Hilbert basis for the system will yield a generating set for M^{(m)}. □

Lemma 2.6. [S2, Lemma 9.6] Let M = ⟨g_{1}, …, g_{t}⟩ be a normal toric monoid and N a finitely generated submonoid such that gp(N) = gp(M). Let θ_{m} : M → M be a homothetic transformation with center z for some z ∈ Int(N) and m ∈ ℕ. Then one can find s ∈ ℕ such that (θ_{m})^{s}(M) ⊂ N^{∗}.

Proof. Since ⟨z^{−1}, N⟩ = gp(N) = gp(M) [S2, Lemma 9.5], by repeatedly multiplying by z, we can find a p such that z^{p}g_{i} ∈ Int(N) for all i. Put s = pm. Then (θ_{m})^{s}(g_{i}) ∈ Int(N) ⊂ N^{∗} for each i, and hence (θ_{m})^{s}(M) ⊂ N^{∗}, as desired. □

Lemma 2.7. Let M be a toric monoid, N a submonoid of the same rank as M. Let x ∈ Int(N), y ∈ M. Then there exists an integer n ≥ 0 such that x^{n}y ∈ Int(N).

Proof. Since N and M have the same rank, we have gp(N) = gp(M). Recall that x ∈ Int(N) if and only if N[x^{−1}] = gp(N). Therefore we can find z ∈ N and n′ ≥ 0 such that y = x^{−n′}z. Hence x^{n′}y = z ∈ N, and consequently x^{n′+1}y = x^{n}y ∈ Int(N). □

III. Milnor Patching

In this section we derive an algorithmic version of Milnor patching for some special types of Milnor squares and Karoubi squares. First we consider Milnor squares. Let R_{1}, R_{2} be commutative rings with a common quotient ring R̄. Assume furthermore that the quotient map R_{1} ⟶ R̄ is a split surjection. Now consider the pullback square

R ⟶ R_{1}
↓  ^{f}↓
R_{2} ⟶ R̄.

where R = {(r_{1}, r_{2}) ∈ R_{1} × R_{2} | r̄_{1} = r̄_{2}}. Such a square is a special case of a Milnor square. (For a discussion of more general Milnor squares see [S2, Sect. 2].)

Patching Algorithm 3.1. Input: A finitely generated projective R_{1}-module P, of rank r, given as the cokernel of a matrix

R_{1}^{n} ⟶^{A} R_{1}^{m} ⟶ P ⟶ 0.

Suppose we are also given an isomorphism

α : P̄ ⟶ R̄^{r}.

That is, we have a commutative diagram:

R̄^{n} ⟶^{Ā} R̄^{m} ⟶ P̄ ⟶ 0
=↓  B̄↓  ≅↓
R̄^{n} ⟶^{B̄Ā} R̄^{m} ⟶ R̄^{r} ⟶ 0

with B̄ an invertible matrix over R̄, such that

(3.1)  B̄Ā = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) ,

where the upper left-hand block I is an (m − r) × (m − r)-identity matrix. Output: A projective R-module Q, and an R_{1}-isomorphism from Q ⊗_{R} R_{1} to P.

As a set,

Q = {(x_{1}, x_{2}) ∈ P × R_{2}^{r} | α(x̄_{1}) = x̄_{2}}.

We need to compute generators for Q. Since the right-hand vertical map f is a split epimorphism we can lift B̄ to an invertible m × m-matrix B over R_{1}. Then the cokernel of BA is a projective R_{1}-module P′ isomorphic to P via the base change matrix B. Now let Q be the cokernel of the n × m-matrix with entries in R, whose R_{1}-part is BA and whose R_{2}-part is (3.1). Note that this gives indeed a well-defined matrix over R. Furthermore, upon extending scalars to R_{1}, resp. R_{2}, Q extends to P′, resp. R_{2}^{r}. □

Now we consider a certain type of Karoubi square. Suppose that M is a normal toric monoid, and N ⊂ M is a nondegenerate pyramidal extension (see Section 6). That is, we have a homomorphism δ : M ⟶ ℤ, with N = {x ∈ M | δ(x) ≤ 0}. Furthermore, there exists an element v ∈ M such that δ(v) > 0, and M is integral over ⟨N, v⟩, that is, for each x ∈ M there exists n > 0 such that x^{n} ∈ ⟨N, v⟩. Let M^{∗} be the maximal ideal of kN^{∗} generated by the set N^{∗} \ {1}. Localizing at M^{∗}, we obtain a special case of a Karoubi square:

kN^{∗} ⟶ kM^{∗}
↓  ↓
kN_{M^{∗}}^{∗} ⟶ kM_{M^{∗}}^{∗}.

Patching Algorithm 3.2. Input: A finitely generated projective kM^{∗}-module P, presented by a matrix A with coefficients in kM^{∗}, and an isomorphism

α : P_{M^{∗}} ⟶^{≅} (kM_{M^{∗}}^{∗})^{t},

represented as in the input for the Patching Algorithm 3.1. Output: A finitely generated projective kN^{∗}-module Q and an isomorphism from Q to P over kM^{∗}.

Since kM^{∗} is a domain, there is a short exact sequence of kM^{∗}-modules

0 ⟶ P ⟶ P_{M^{∗}} ≅ (kM_{M^{∗}}^{∗})^{t} ⟶ L ⟶ 0,

where the first map is the inclusion and L is the quotient. Restriction of the quotient map gives an exact sequence of kN^{∗}-modules

0 ⟶ Q ⟶ (kN_{M^{∗}}^{∗})^{t} ⟶ L.

It is shown in [Gu, Lemma 2.6] that the module Q is a finitely generated projective kN^{∗}-module which extends to P. We now compute a set of generators of Q and an explicit isomorphism from Q to P over kM^{∗}. Let A be an m × n-matrix with entries in kM^{∗} whose cokernel is P. Let U be an invertible m × m-matrix with entries in kM_{M^{∗}}^{∗} such that

U · A = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) ,

which exists by hypothesis. Thus, we have a short exact sequence

(3.2)  0 ⟶ P ⟶^{incl} P_{M^{∗}} ⟶^{U} (kM_{M^{∗}}^{∗})^{t} ⟶ L ⟶ 0.

Let f be a common denominator of the entries in U. Then P becomes free over kM_{f}^{∗}. We obtain a short exact sequence

0 ⟶ P ⟶^{incl} P_{f} ⟶^{U} (kM_{f}^{∗})^{t} ⟶ L′ ⟶ 0,

which becomes sequence (3.2) upon extension of scalars to kM_{M^{∗}}^{∗}. The kernel K of the projection (kM_{f}^{∗})^{t} ⟶ L′ is generated as a kM^{∗}-module by the projection of the columns of U onto the last t coordinates. Define Q′ = K ∩ (kN_{f})^{t}. In order to compute generators for Q′ as a kN^{∗}-module, observe that the elements of K all have denominator f. Thus, Q′ is the intersection of K with the kN^{∗}-submodule of (kN_{f}^{∗})^{t} generated by the elements (\frac{1}{f} , 0, …, 0), …, (0, …, \frac{1}{f}). Then

Q = Q′ ∩ ⟨IntN⟩_{f},

where ⟨Int(N)⟩ is the ideal of kN generated by the set Int(N). The intersections can be computed using Gröbner basis theory, since they involve only submodules of free modules. From the commutative diagram

0 ⟶ Q ⟶ (kN_{f}^{∗})^{t} ⟶ L′ ⟶ 0
↓  ^{incl}↓  ^{=}↓
0 ⟶ P ⟶ (kM_{f}^{∗})^{t} ⟶ L′ ⟶ 0

we obtain an explicit kN^{∗}-monomorphism from Q to P, which becomes an isomorphism upon extending scalars to kM^{∗}. □

IV. Reduction to M^{∗}.

In this section, let M be a normal toric monoid. We assume the Induction Hypothesis 1.2, that we can carry out the QS-algorithm for all fields and all toric monoids of rank less than the rank of M.

We now use Milnor patching on a sequence of Milnor squares to reduce the problem to that for monoids of the form M^{∗}. Roughly speaking, we obtain M^{∗} from M by successively deleting extremal submonoids from M, first all those of rank one, then the interiors of those of rank two, etc. Each such deletion is accomplished via a Milnor square in which the right-hand vertical map is a split surjection, so that we can use the Milnor patching algorithm from the previous section.

Lemma 4.1. Let E ⊂ M be an extremal submonoid. Then the ideal I of kM generated by M \ E is a prime ideal, and the canonical projection kM ⟶ kM/I is a split epimorphism.

Proof. That I is a prime ideal follows directly from the definition of an extremal submonoid.

Note that there is a canonical isomorphism kM/I ≅ kE, so the inclusion kE ⟶ kM provides a splitting for the projection. □

Interior Algorithm 4.2. Input: A normal toric monoid M and a finitely generated projective kM-module P. Output: A finitely generated projective kM^{∗}-module Q and an isomorphism from Q to P over kM. The algorithm proceeds by induction on the rank of M. As before, if rk(M) = 1, then M = M^{∗}, and there is nothing to be done. So assume that rk(M) > 1. Step 1: Compute all extremal submonoids of M (Lemma 2.1), and list them in order of increasing rank:

M_{01} = {1}, M_{11}, M_{12}, …, M_{1n_{1}}, M_{21}, …, M_{d1} = M,

such that M_{ij} has rank i. Step 2: Construct a sequence of Milnor squares as follows. Let I_{11} be the ideal of kM generated by the set M \ M_{11}, and let K_{11} be the submonoid (M \ M_{11}) ∪ {1} of M. Then I_{11} is a prime ideal, and we obtain the Milnor square

kK_{11} ⟶ kM
↓  ↓
k ⟶ kM/I_{11}.

Note that by the above lemma kM/I_{11} ≅ kM_{11}, and that therefore the right-hand vertical map is a split surjection. Furthermore, rk(M_{11}) < rk(M), so that the Induction Hypothesis 1.2 applies to M_{11}. Use it to find an isomorphism from the image P̄ of P to a free kM/I_{11}-module. Now use the Patching Algorithm 3.1 to construct a projective kK_{11}-module P_{11}, and an isomorphism to P over kM.

Now consider M_{12}. Since rk(M_{11}) = rk(M_{12}) = 1, it follows that M_{11} ∩ M_{12} = {1}. Let I_{12} be the ideal of kK_{11} generated by the set

K_{11} \ (K_{11} ∩ M_{12}) = K_{11} \ M_{12} = M \ (M_{11} ∪ M_{12}).

Then I_{12} is a prime ideal of kK_{11}, and the canonical surjection

kK_{11} ⟶ kK_{11}/I_{12} ≅ kM_{12}

is split by the inclusion kM_{12} ⟶ kK_{11}. Let K_{12} be the submonoid K_{11} \ (K_{11} ∩ M_{12}) ∪ {1}. Then we obtain the Milnor square

kK_{12} ⟶ kK_{11}
↓  ↓
k ⟶ kM_{12}

with split surjective right-hand map. Now apply the same construction as above to P_{11} in order to obtain a projective kK_{12}-module P_{12}, and an isomorphism to P_{11} over kK_{11}.

Continue in this way through all rank 1 extremal submonoids. The last such Milnor square is of the form

kK_{1n_{1}} ⟶ kK_{1,n_{1}−1}
↓  ↓
k ⟶ kM_{1n_{1}}.

Observe that

K_{1n_{1}} = M \ (M_{11} ∩ ⋯ ∩ M_{1n_{1}}) ∪ {1}.

Now consider the first rank 2 extremal submonoid M_{21}. First observe that M_{21} ∩ K_{1n_{1}} = M_{21}^{∗}. Let

K_{21} = (K_{1n_{1}} \ M_{21}^{∗}) ∪ {1}.

Furthermore, let I_{21} be the ideal of kK_{1n_{1}} generated by K_{1n_{1}} \ M_{21}^{∗}. Then we obtain the Milnor square

kK_{21} ⟶ kK_{1n_{1}}
↓  ↓
k ⟶ kM_{21}^{∗}

with the right-hand map a split surjection.

Continuing in this fashion we finally arrive at the Milnor square

kM^{∗} ⟶ kK_{d−1,n_{d−1}−1}
↓  ↓
k ⟶ kM_{d−1,n_{d−1}}.

We have constructed a projective kM^{∗}-module Q = P_{d−1,n_{d}−1} and an isomorphism to P over kM. □

V. The Induction Step

This section contains the key result needed for the induction step of the QSalgorithm. Several subalgorithms are needed. The first one concerns a special case of the Quillen Patching Theorem [S2, Theorem 3.1]. The algorithm for its proof is a variant of the algorithm in [LS], incorporating part of the algorithm in [PW].

Proposition 5.1. Let M be a normal toric monoid, and let R = kM[x] be the polynomial ring in one variable over kM. Let P be a finitely generated projective Rmodule. Suppose that P_{M} is free for all maximal ideals M of kM, and furthermore that there is a QS-algorithm for finitely generated projective kM-modules. Then P is free, and there is an algorithm to find a free basis for P.

Proof and Algorithm. Represent kM as k[x_{1}, …, x_{t}]/I where I is the binomial ideal generated by the defining relations of M [Gi, Thm. 7.1]. Then

R = kM[x] = k[x_{1}, …, x_{t}, x]/I.

Suppose that P has rank r, and a free presentation:

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

where A is an (m × n)-matrix with entries in R. Then P is free if and only if there exists an invertible m × m-matrix U over R and a commutative diagram

R^{n} ⟶^{A} R^{m} ⟶ P ⟶ 0
=↓  ^{U}↓  ≅↓
R^{n} ⟶^{B} R^{m} ⟶ R^{r} ⟶ 0,

such that

B = U · A = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

We now construct a sequence of maximal ideals of kM as follows. Let a_{1} ∈ k̄^{t} be a common root for the generators of I in an algebraic closure k̄ of k, and let

M̃_{1} = {f ∈ k[x_{1}, …, x_{t}] | f(a_{1}) = 0}.

Then M̃_{1} is a maximal ideal of k[x_{1}, …, x_{t}] which contains I. Thus, it corresponds to a maximal ideal M_{1} of kM.

We will subsequently write A(x), etc., to indicate that a given matrix is defined over the ring kM[x], so that A(0) becomes a matrix over kM. Let U_{1}(x) ∈ GL_{m}(kM_{M_{1}}[x]) be such that

U_{1}(x) · A(x) = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} );

such a U_{1} can be computed by hypothesis. Let r_{1} ∈ kM be a common denominator for all the entries in U_{1}. Then r_{1} ∉ M_{1} by construction. Lift r_{1} to r̃_{1} ∈ k[x_{1}, …, x_{t}], and let a_{2} be a common zero of the elements in I and r̃_{1}. Then define

M̃_{2} = {f ∈ k[x_{1}, …, x_{t}] | f(a_{2}) = 0}.

As before, M̃_{2} is a maximal ideal which contains I. Furthermore, it is different from M̃_{1}, since r̃_{1} ∈ M̃_{2} \ M̃_{1}. So M̃_{2} corresponds to a maximal ideal M_{2} of kM which contains r_{1}. Let U_{2}(x) ∈ GL_{m}(kM_{M_{2}}) be such that

U_{2}(x) · A(x) = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

Define r_{2} to be a common denominator for all entries in U_{2}, with lifting r̃_{2} ∈ k[x_{1}, …, x_{t}]. Note that r_{2} ∉ ⟨r_{1}⟩, since r_{1} ∈ M_{2} but r_{2} ∉ M_{2}.

Continuing this construction, we obtain r_{3} ∉ ⟨r_{1}, r_{2}⟩, and so on. Since kM is noetherian, we must reach a point where

⟨r_{1}, …, r_{s}⟩ = kM.

Then, for every d ≥ 1, we can find g_{1}, …, g_{s} ∈ kM such that

r_{1}^{d}g_{1} + ⋯ + r_{s}^{d}g_{s} = 1.

This holds in particular for d = m. Define

Δ_{i}(u, z) = U_{i}^{−1}(u + z)U_{i}(u)

for i = 1, …, k. Then Δ_{i}(u, z) is invertible, with entries in kM_{M_{i}}[u, z]. Recall that r_{i} is a common denominator for U_{i}(u) and U_{i}(u + z). Since

U_{i}^{−1}(u + z) = det (U_{i}(u + z)) · adj (U_{i}(u + z)) ,

we see that r_{i}^{m−1} is a common denominator for U_{i}^{−1}(u + z). Therefore, r_{i}^{m} is a common denominator for Δ_{i}(u, z). Expand Δ_{i}(u, z) as a polynomial in z with matrix coefficients over kM_{M_{i}}[u]:

Δ_{i}(u, z) = Δ_{i0}(u) + Δ_{i1}(u)z + ⋯ + Δ_{id_{i}}(u)z^{d_{i}}.

Then Δ_{i0}(u) = Δ_{i}(u, 0) = I_{m}. Now replace z by zr_{i}^{m}:

Δ_{i}(u, zr_{i}^{m}) = I_{m} + r_{i}^{m}Δ_{i1}(u)z + r_{i}^{2m}Δ_{i2}(u)z^{2} + ⋯ + r_{i}^{d_{i}m}Δ_{id_{i}}(u)z^{d_{i}}.

Since r_{i}^{m} is a common denominator for Δ_{i}(u, z), it is also a common denominator for all Δ_{ij}(u), so that the above expansion is denominator-free, and Δ_{i}(u, zr_{i}^{m}) is an invertible matrix over kM[u, z]. Observe furthermore that

Δ_{i}(u, zr_{i}^{m}) · A(u) = U_{i}^{−1}(u + zr_{i}^{m})U_{i}(u)A(u)

= U_{i}^{−1}(u + zr_{i}^{m}) ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} )

= U_{i}^{−1}(u + zr_{i}^{m})U_{i}(u + zr_{i}^{m})A(u + zr_{i}^{m}) = A(u + zr_{i}^{m})

in kM[u, z]. Now define

U(x) = Δ_{s}(x − ∑_{i=1}^{s−1} xg_{i}r_{i}^{m}, −xg_{s}r_{s}^{m}) · Δ_{s−1}(x − ∑_{i=1}^{s−2} xg_{i}r_{i}^{m}, −xg_{s−1}r_{s−1}^{m})
⋯ Δ_{2}(x − xg_{1}r_{1}^{m}, −xg_{2}r_{2}^{m}) · Δ_{1}(x, −xg_{1}r_{1}^{m}).

The s factors in this product are obtained by substitutions of variables, hence U(x) is invertible over kM[x]. Furthermore,

U(x) · A(x) = A(x − ∑_{i=1}^{s} xg_{i}r_{i}^{m}) = A(0).

But A(0) is a matrix over kM, so that the projective module it represents is free, and we can find an explicit isomorphism by hypothesis. This completes the proof. □

This algorithm is needed as a subroutine in the next result, which represents the induction step in our main algorithm.

Proposition 5.2. Suppose that M is a toric monoid and QS holds for M, then QS also holds for the monoid M × ℤ.

Proof and Algorithm. Let P be a finitely generated projective module over k[M ×ℤ]. Represent k[M ×ℤ] as kM[x, x^{−1}]. Let S, resp. T, be the set of monic polynomials in k[x], resp. k[x^{−1}]. Proposition 5.3 below implies that it is sufficient to find free bases for P_{S} and P_{T}. But k[M ×ℤ]_{S} = k(x)M, so we can find an isomorphism from P_{S} to a free module by hypothesis. Similarly, k[M × ℤ]_{T} = k(x^{−1})M ≅ k(x)M. (The last isomorphism follows from the fact that k is a field.) Therefore it is sufficient to give an algorithm for the following result.

Proposition 5.3. Let P be a finitely generated projective kM[x, x^{−1}]-module. If P ⊗ k(x^{−1}) is free, then P is free.

To begin the proof, let U be a matrix with entries in k(x^{−1})M which represents an isomorphism between P ⊗ k(x^{−1}) and a free k(x^{−1})M-module, which can be found by hypothesis. Let f ∈ k[x^{−1}] be a common denominator for the entries of U. Then P_{f} is free over kM[x, x^{−1}]_{f}, with the same matrix U representing an isomorphism to a free module. Let f = x^{−n}g with g ∈ kM[x] and g(0) = 1. Consider the commutative square

(5.1)  \begin{matrix}kM[x] & ⟶ & kM[x, x^{−1}] \\ ↓ & & ↓ \\ kM[x]_{g} & ⟶ & kM[x, x^{−1}]_{g} & = kM[x, x^{−1}]_{f}. \end{matrix}

In order to continue the proof of Proposition 5.3, we need the following result.

Lemma 5.4. Let R be a domain, f, g ∈ R elements such that fR + gR = R. Then the square

R ⟶ R_{f}
↓  ↓
R_{g} ⟶ R_{gf}

is isomorphic to a pullback square.

Proof. We need to show that

R ≅ \{(\frac{a}{s}, \frac{b}{t}) ∈ R_{f} × R_{g} | \frac{a}{s} = \frac{b}{t} in R_{fg}\}.

Since R is a domain, we have that ta = sb. Since f and g are comaximal, so are any of their powers. Let xs + yt = 1, and define r = xa + yb. Then sr = sxa + syb = sxa + tya = a, so that r = a/s in R_{f}. Likewise r = b/t in R_{g}. □

We will show that this square has the Milnor patching property. (In fact, it is a so-called localization square, or generalized Karoubi square; see [S2, p. 219].)

Rewrite the matrix U over kM[x, x^{−1}]_{f} so that all denominators are equal to f = x^{−n}g. Let α ∈ ℤ be such that x^{α} · U does not contain any occurrence of x^{−1} in its entries. Replace P by the projective module x^{α}P which is isomorphic to P as a kM[x, x^{−1}]-module. After inverting f, x^{α}P becomes isomorphic to a free module, with an isomorphism given by the matrix x^{α}U. This matrix has common denominator g and numerators in kM[x], hence is a matrix over kM[x]_{g}. Let F be the free kM[x]_{g}-module given by the columns of the matrix (x^{α}U)^{−1}. Then F becomes EQUAL to x^{α}P upon extending coefficients to kM[x, x^{−1}]_{g}. Presentation matrices of x^{α}P and F are

diag(x^{α})A  and  ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} )

respectively, where I stands for an identity matrix of the appropriate size. The matrices become equal over kM[x, x^{−1}]_{g}, hence they lift to a matrix B over kM[x], which presents a projective module Q that becomes equal to x^{α}P over kM[x, x^{−1}]. In particular, if Q is free, then it follows that P is free also.

It is therefore sufficient to give a constructive proof of the following result.

Lemma 5.5. If all projective modules over kM are free, then the same is true for kM[x].

The key ingredient in the proof is Gubeladze’s version of Roberts’ Theorem, applied to our situation.

Theorem 5.6. [Gu, Theorem 2.3] Let (R, M) be a local ring, and A an R-algebra. Let P be a finitely generated A-module, and S a multiplicative set of A which is regular on A and P. Let n be a nonnegative integer. Suppose further that

(1) for every f ∈ S, A/fA is a finitely generated R-module;

(2) the map SL_{n}(A_{S}) ⟶ SL_{n}(\overline{A_{S}}) is onto (where the bar denotes reduction modulo the maximal ideal M of R), and the group of unitsU(\overline{A_{S}}) is generated by the images of U(Ā) and U(A_{S});

(3) A_{S} contains a subalgebra B such that A_{S} = A + B and MB ⊂ J(B) (the Jacobson radical of B);

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

Algorithm 5.7. Input: A toric monoid M, so that there exists a QS-algorithm for M and all fields, and a finitely generated projective kM[x]-module P of rank t, with presentation

kM[x]^{n} ⟶^{C} kM[x]^{m} ⟶ P ⟶ 0.

Output: An m × m invertible matrix U over kM[x] such that

U · C = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

By Quillen’s Patching Theorem it is enough to show that P_{M} is free for all maximal ideals M of kM. Let R = kM_{M} and A = R[x]. Let S ⊂ A be the multiplicative set of monic polynomials in x with coefficients in k. Then we have a commutative diagram

A ⟶ A_{S}
↓  ↓
Ā ⟶ Ā_{S},

where

Ā = A/MA = k′[y], A_{S} = (kM_{M}[x])_{S} = k(x)M_{M}, Ā_{S} = k′(y),

with k′ = kM/M, a field extension of k. The map

SL_{t}(A_{S}) = SL_{t} (k(x)M_{M}) ⟶ SL_{t}(Ā_{S}) = SL_{t} (k′(y))

is surjective, since k′(y) is a field, so SL_{t} (k′(y)) = E_{t} (k′(y)), the subgroup generated by all elementary matrices, and the right vertical map is surjective. Since A_{S} is a local ring with quotient field k′(y), the corresponding map on unit groups is surjective. Thus, Condition (2) of Roberts’ Theorem is satisfied, and so is (1).

Since (P_{M})_{S} = (P_{S})_{M} (subsequently denoted by P_{S}), we obtain an isomorphism to a free module by hypothesis, given by the commutative diagram

A_{S}^{n} ⟶^{C} A_{S}^{m} ⟶ P_{S} ⟶ 0
=↓  ^{U}↓  ≅↓
A_{S}^{n} ⟶^{UC} A_{S}^{m} ⟶ A_{S}^{t} ⟶ 0,

where U ∈ GL_{m}(A_{S}) and

UC = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

Since Ā = k′[y], we obtain a similar isomorphism by computing the Smith normal form of the image of the presentation matrix C for P, obtaining a matrix V ∈ GL_{m}(Ā) such that

V C̄ = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

Let u_{1}, …, u_{t} be the A_{S}-basis of P_{S} that maps to the canonical basis of A_{S}^{t} under the isomorphism induced by U, that is, the image in P_{S} of the last t columns of U^{−1}. Similarly, let v̄_{1}, …, v̄_{t} in P̄ form the Ā-basis for P̄ which maps to the canonical basis of Ā^{t} under the isomorphism induced by V. Lift the v̄_{i} ∈ P̄ to v_{1}, …, v_{t} in P, using Gröbner basis theory. Thus we obtain two free bases {ū_{i}} and \{v̄_{i}\} for P̄_{S} = \overline{P_{S}}. Compute a base change matrix \overline{W} ∈ GL_{t}(Ā_{S}) which maps \{v̄_{i}\} to \{ū_{i}\}. If ā = det(\overline{W}), a unit in Ā_{S}, then

\overline{W} = \overline{W} · ( \begin{matrix}ā^{−1} & 0 & … & 0 \\ 0 & 1 & & 0 \\ . & . & . \\ 0 & 0 & … & 1 \end{matrix} ) · ( \begin{matrix}ā & 0 & … & 0 \\ 0 & 1 & & 0 \\ . & . & . \\ 0 & 0 & … & 1 \end{matrix} ) .

The product of the first two factors is in SL_{t}(Ā_{S}), hence lifts to a matrix SL_{t}(A_{S}). Likewise, the third factor lifts to an invertible matrix, since units lift. Thus, W̄ lifts to an invertible matrix W ∈ GL_{t}(A_{S}). Now replace the basis u_{1}, …, u_{t} of P_{S} by the basis W^{−1}u_{1}, …, W^{−1}u_{t}. Then for this new basis of P_{S} we have that ū_{i} = v̄_{i} for all i.

Let P′ = ∑ A · u_{i} be the A-submodule of P_{S} generated by the u_{i}. Since {u_{i}} is a free A_{S}-basis of P_{S}, it follows that it forms a free A-basis for P′. Furthermore, the modules P and P′ have the same image in P̄_{S}, since ū_{i} = v̄_{i}. We will now construct an explicit isomorphism between P and the free A-module P′.

Given an element a = ∑ α_{i}u_{i} ∈ P_{S}, we can write

α_{i} = \frac{g_{i}}{h_{i}} = g′_{i} + \frac{g′′_{i}}{h_{i}} ,

with g′_{i} ∈ A, and deg(g′′_{i}) ≤ deg(h_{i}). Then

a = ∑ \frac{g′′_{i}}{h_{i}} · u_{i} + ∑ g′_{i}u_{i}.

Furthermore,

g′_{i}u_{i} = g′_{i} \frac{w_{i}}{f_{i}} = \frac{g_{i}}{f_{i}} w_{i} = \frac{q_{i}f_{i} + r_{i}}{f_{i}} w_{i} = q_{i}w_{i} + \frac{r_{i}}{f_{i}} w_{i},

with w_{i} ∈ P and deg(r_{i}) ≤ deg(f_{i}). We obtain a similar decomposition for g′′_{i}u_{i}. Now we apply this decomposition to the elements u_{j} − v_{j} to obtain

u_{j} − v_{j} = ∑ \frac{g_{i}}{h_{i}} · w_{i} + ∑ g′_{i}w_{i},

with deg(h_{i}) ≥ deg(g_{i}). It is shown in [La, p. 116] that the elements

v_{j} + ∑ g′_{i}w_{i}, j = 1, …, t,

form a free A-basis of P. This completes Algorithm 5.7, needed to complete the proof of Lemma 5.5, hence that of Propositions 5.3 and 5.2. □

We now summarize the results of this section.

Induction Algorithm 5.8. Input: A normal toric monoid M for which there exists a QS-algorithm, and a finitely generated projective module P over k[M × ℤ], presented by a matrix A. Output: An invertible matrix U over k[M × ℤ] such that

U · A = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

Step 1: Represent k[M × ℤ] as kM[x, x^{−1}]. Compute such a U over k(x^{−1})M, which is possible by the hypothesis on M. Step 2: Construct a projective module Q over kM[x] by Milnor Patching applied to the generalized Karoubi square (5.1), as described after Lemma 5.4. Step 3: Use the Quillen Patching Theorem algorithm (Prop. 5.1) to find a free basis for Q, with Algorithm 5.7 as the local loop to compute free bases for Q over the localizations at the various maximal ideals produced by the Patching Algorithm. Let V be the invertible matrix affecting the base change in the presentation of Q over kM[x]. Then the desired U is obtained from V by extension of scalars.

Corollary 5.9. The algorithm for Lemma 5.5 applied to free monoids provides a QS-algorithm for polynomial rings.

VI. Pyramidal extensions and projective modules

Definition. A pyramidal extension is an extension of monoids N ⊂ M such that (1) M is a normal toric monoid.

(2) There is a homomorphism δ : M → ℤ with N = {x ∈ M | δ(x) ≤ 0}.

(3) There exists an element v ∈ M such that δ(v) > 0 and M is integral over

⟨N, v⟩, that is, for each x ∈ M there is n > 0 such that x^{n} ∈ ⟨N, v⟩. A pyramidal extension will be called nondegenerate if there is an x such that δ(x) < 0.

Note that if N ⊂ M is a nondegenerate pyramidal extension then rk(N) = rk(M) [S2, p. 234].

Let N ⊂ M be a nondegenerate pyramidal extension of toric monoids, and let P be a projective module over kM^{∗}. The final, and most complicated, ingredient in the QS-Algorithm is to construct a projective module over kN^{∗} which extends to P under extension of scalars. This construction will then be applied to the admissible sequence constructed in Section 7, in order to complete the QS-Algorithm. We proceed by carrying out Milnor patching for the Karoubi square

kN^{∗} ⟶ kM^{∗}
↓  ↓
kN_{M^{∗}}^{∗} ⟶ kM_{M^{∗}}^{∗},

where M^{∗} is the maximal ideal of kN^{∗} generated by N^{∗} \ {1}, after showing that all projective modules over the lower right-hand ring are free. Thus, we need to prove

Proposition 6.1. Let N ⊂ M be a nondegenerate pyramidal extension of normal toric monoids, and let M^{∗} be the maximal ideal of kN^{∗} generated by N^{∗} \ {1}. If P is a finitely generated projective kM^{∗}-module, then one can find an explicit isomorphism from P_{M^{∗}} to a free kM_{M^{∗}}^{∗}-module.

The proof will proceed by induction on the rank of M. If rk(M) = 1, then kM = kM^{∗} is a polynomial ring in one variable over k, and P itself has a free basis, computed by the Smith normal form algorithm. So assume that rk(M) > 1.

Let N ⊂ M be a nondegenerate pyramidal extension of toric monoids, and P a finitely generated projective kM^{∗}-module, with the free presentation

(kM^{∗})^{n} ⟶^{A} (kM^{∗})^{r} ⟶ P ⟶ 0,

where A is a matrix with entries in kM^{∗}. Choose z ∈ Int(N), and find an integer m large enough so that all entries of A are contained in the homothetic submonoid M^{(m)} (which can be computed as in Lemma 2.5). Such an m exists by Lemma 2.6.

Then P is obtained by extension of scalars from the projective k(M^{(m)})-module Q defined by the same presentation matrix A. Furthermore,

N^{(m)} ⊂ M^{(m)}

is also a nondegenerate pyramidal extension [Sw, Lemma 10.1]. Let M′ be the maximal ideal of kN^{(m)} generated by Int(N^{(m)}). Since P_{M^{∗}} is obtained by extension of scalars from Q_{M′}, it is sufficient to find an isomorphism from Q_{M′} to a free kM^{(m)}-module. That is, we need to prove the following:

Proposition 6.2. Let N ⊂ M be a nondegenerate pyramidal extension, and M the maximal ideal of kN generated by N \{1}. If P is a finitely generated projective kM-module, then one can find an isomorphism from P_{M} to a free kM_{M}-module.

Proof and Algorithm. Let v ∈ M be as in (3) of the definition at the beginning of the section. We first show that it is sufficient to find an isomorphism from P_{v} to a free kM[v^{−1}]-module. Observe that

kM[v^{−1}] ≅ k[⟨M, v^{−1}⟩],

and

⟨M, v^{−1}⟩ ≅ M′ × ⟨v⟩ ≅ M′ × ℤ.

Since rk(M′) < rk(M), we can apply the Induction Algorithm 5.8 to the monoid M′ × ℤ. Therefore the proof of Proposition 6.2 will be complete if we can show the following result.

Proposition 6.3. With hypotheses as in Proposition 6.2, if P_{v} is free, then P_{M} is free.

Proof and Algorithm. The proof proceeds by applying Roberts’ Theorem to the ring R = kN_{M} and the R-algebra A = kM_{M}, similar to the proof of Lemma 5.5. First we define a grading on the algebra A.

Suppose N ⊂ M is a pyramidal extension with w ∈ M such that δ(w) > 0 and M is integral over ⟨N, w⟩. Then w lies on an extremal submonoid E = ⟨v⟩ of M [S2, Lemma 8.3]. If w = (a_{1}, …, a_{d}) ∈ ℕ^{d}, then v = (a_{1}/a, …, a_{d}/a) where a = gcd(a_{1}, …, a_{d}). We now replace w by v, and call it a vertex of the pyramidal extension. Notice that if M = ⟨g_{1}, …, g_{s}⟩, then by direct computation we can find m > 0 with each g_{i}^{m} ∈ ⟨N, v⟩. So, x^{m} ∈ ⟨N, v⟩ for each x ∈ M implying x^{m} = v^{a}y for some a ≥ 0 and y ∈ N. For the rest of the discussion, such an m will be fixed.

Definition.

(1) Let x ∈ M. Then deg(x) = min{a ≥ 0 | x^{m} = v^{a}y for some y ∈ N}.

(2) Let f = r_{1}x_{1} + ⋯ + r_{t}x_{t} ∈ A where r_{i} ∈ R and x_{i} ∈ M. Then deg(f) < p if and only if deg(x_{i}) < p for i = 1, …, t.

(3) If f = v^{a} + g with deg(g) < deg(v^{a}), we call f monic.

The following result provides us with a division algorithm in A.

Proposition 6.4. [S2, Cor. 8.5] Let f, g ∈ A with g monic. Then there are q, r ∈ A with deg(r) < deg(g) such that f = qg + r.

Proof. Begin by initializing q := 0 and r := f. If deg(r) < deg(g), we are done. Suppose deg(r) ≥ deg(g) = deg(v^{a}) = am. Write r = r_{1}x_{1} + ⋯ + r_{t}x_{t}, where each r_{i} ∈ R and x_{i} ∈ M. Then one of the x_{i} is such that deg(x_{i}) ≥ deg(v^{a}) = am. Claim: We can write x_{i} = v^{a}x̃_{i} where x̃_{i} = x_{i}v^{−a} ∈ M with deg(x̃_{i}) ≤ deg(x_{i})−am. If we replace r with r − r_{i}x̃_{i}g and q with q + r_{i}x̃_{i}, then f = qg + r. If deg(r) is still greater than or equal to deg(g), repeat the process. Since the degree of r strictly decreases with each pass, the process must eventually terminate with f = qg + r and deg(r) < deg(g).

Proof of Claim. Since N ⊂ M is a pyramidal extension, there exist w_{i} ∈ N and b ≥ 0 such that x_{i}^{m} = v^{b}w_{i}. But deg(x_{i}) ≥ am so x_{i}^{m} = v^{am}(v^{b−am}w_{i}) or (x_{i}v^{−a})^{m} = v^{b−am}w_{i}. Therefore, x̃_{i} = x_{i}v^{−a} ∈ M since M is normal. Notice that deg(x̃_{i}) ≤ b − am ≤ deg(x_{i}) − deg(v^{a}). □

Let S ⊂ A be the multiplicatively closed set of monic elements. Consider the commutative square

A ⟶ A_{S}
↓  ↓
Ā ⟶ Ā_{S}.

Let

A^{n} ⟶^{C} A^{m} ⟶ P ⟶ 0

be a presentation for P. First we find isomorphisms from P_{S} and P̄ to free modules. First of all, since v ∈ S and there exists an isomorphism from P_{v} to a free A_{v}- module, we obtain an isomorphism from P_{S} to a free A_{S}-module by extension of scalars.

Now consider P̄. If x ∈ M, then we can write x^{m} = v^{b}y with y ∈ N. So we can write any element in A as a sum of a polynomial in v and an element which is nilpotent modulo M. Hence Ā_{red} = k[v], and the canonical quotient map

Ā = kM_{M}/MkM_{M} = kM/⟨N \ {1}⟩ ⟶ k[v] = kM/⟨M \ ⟨v⟩⟩

is a split surjection. This can be seen by observing that ⟨v⟩ ⊂ M is extremal [Sw, Lemma 8.3], so we can use Lemma 4.1. Using a Smith normal form computation, we can find an isomorphism from P̄_{red} to a free module, that is, we can find an invertible matrix U_{red} over Ā_{red} such that

U_{red} · C̄_{red} = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

Lifting U_{red} to Ā via the splitting, we obtain an invertible matrix U over Ā such that

U · C̄ = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

(Recall that if a module Q is free modulo a nilpotent ideal, then it is free.) Thus, P̄ is free. Furthermore, P̄ and P_{S} have the same rank since A is a domain.

As in Roberts’ Theorem, we now proceed to construct a free module F over A from the free modules P̄ and P_{S}, and an isomorphism from P to F. Let x_{1}, …, x_{t} be a free basis for P_{S}, for instance the inverse image of the canonical basis of A_{S}^{t} under the isomorphism constructed above. Furthermore, let y_{1}, …, y_{t} ∈ P be elements such that ȳ_{1}, …, ȳ_{t} is a free basis for P̄. We first modify the basis for P_{S} so that x̄_{i} = ȳ_{i} in P̄_{S}.

Both, {x̄_{i}} and {ȳ_{i}} are free bases for P̄_{S} over Ā_{S}. Let V be the invertible base change matrix which transforms the basis {x̄_{i}} to the basis {ȳ_{i}}, with a = det(V).

Lemma 6.5. There exist units b ∈ Ā and c ∈ A_{S} such that a = b · c̄ in Ā_{S}.

Proof and Algorithm. Write a = \frac{f}{s} with s ∈ S̄ and f ∈ Ā. It is sufficient to show that f is a product of a unit in Ā and an element of S̄, which is done in the lemma below.

Observe that Ā has a graded structure,

Ā = ⨁_{i} Ā_{i},

where Ā_{i} = {ā ∈ Ā | δ(a) = i} (see [Sw, p. 232]). Let d = δ(v).

Lemma 6.6. With notation as above, f = (1 + η)g, where η is nilpotent and g = v^{n} + a_{nd−1} + ⋯ + a_{0}, with a_{i} ∈ Ā_{i}. Furthermore, 1 + η is a unit in Ā, and g ∈ Ā lies in the image of S, so that g ∈ Ā_{S} is the image of a unit from A_{S}.

Proof. Observe first that the image of S in Ā_{red} = k[v] consists of all monic polynomials, so that (Ā_{S})_{red} = k(v). Since f divides an element of S, it follows that up to a unit of k, f maps to a monic polynomial in k[v]. Therefore, f ≡ v^{n}+a_{nd−1}+⋯+a_{0} modulo the nilradical of A. We now compute a decomposition

f = (1 + η)g,

with η nilpotent, and g ∈ ⨁_{i=0}^{nd−1} A_{i}. For this we need the following lemma.

Lemma 6.7. Let B be the quotient of Ā modulo a nilpotent graded ideal, and let M be a finitely generated graded B-module, such that multiplication by v ∈ Ā_{d} induces an isomorphism v : M_{i} ⟶ M_{i+d} for all i ≥ 0. Let f be as above, and z ∈ M. Then we can write z = fq + r with q ∈ M and r ∈ M_{0} + ⋯ + M_{nd−1}. Moreover, q and r are unique.

Proof. Let f = f_{0} +⋯+f_{m}, with f_{i} homogeneous of degree i. Then f_{nd+1}, …, f_{m} and f_{nd} − v^{n} are nilpotent, and therefore generate a homogeneous nilpotent ideal J. Compute a nonnegative integer h such that J^{h} = 0. We proceed by induction on h. If h = 0, then we can simply use the usual division algorithm. Now let h > 0, and

N = {x ∈ Ā | v^{k}x ∈ J^{h−1} for some k ≥ 0} = ⋃_{k≥0}(J^{h−1} : v^{k}).

To compute N observe that this union is actually finite, since (J^{h−1} : v^{k}) ⊂ (J^{h−1} : v^{k+1}), so that we obtain an increasing sequence of ideals, and Ā is noetherian. Now observe that N is a graded ideal of Ā, and multiplication by v induces an isomorphism N_{i} ⟶ N_{i+d}, since

N_{i} = N ∩ Ā_{i} ≅ N ∩ Ā_{i+d} = N_{i+d}.

Therefore, the same is true for Ā/N. Furthermore, Ā/N is a module over Ā/J^{h−1} and N is a module over Ā/J. By induction the conclusion applies to N and to Ā/N. So we can write

z̄ = f̄q̄ + r̄

in Ā/N. Now lift back to Ā to obtain

z = fq + r + w,

with w ∈ N. Write w = fq′ + r′, so that z = f(q + q′) + r + r′. □

Now apply this lemma to M = A and z = v^{n}. We obtain v^{n} = fq + r. Modulo the nilradical, f has the form v^{n} + a_{nd−1} + ⋯ + a_{0}. Substitution gives that q̄ = 0 in A/nil(A), so that q = 1 + μ with μ nilpotent. Therefore q is a unit, with inverse 1 + η. This completes the proof of Lemma 6.6. □

Returning to the proof of Proposition 6.3, we have now factored a = det(V) = b·c̄ in A_{S}. We now change the basis {x_{i}} for P_{S} by the invertible matrix

( \begin{matrix}c^{−1} & 0 & 0 & … & 0 \\ 0 & 1 & 0 & & 0 \\ . & . & . \\ 0 & 0 & … & & 1 \end{matrix} ) ,

and the basis {ȳ_{i}} for P̄ by a similar matrix, replacing c^{−1} by b^{−1}. Now the new base change matrix V over Ā_{S} has determinant 1. But Ā_{S} is a local ring [S2, p. 231], so SL_{n}(Ā_{S}) = E_{n}(Ā_{S}). An explicit factorization of a determinant 1 matrix into a product of elementary matrices can be obtained as follows. Use the fact that for an element x in a local ring, x or 1 − x is a unit to see that the first column must contain a unit. Now carry out Gauss-Jordan elimination by induction.

This shows that we can lift the base change matrix V to an invertible matrix Ṽ over A_{S}. Now change the basis {x_{i}} by the matrix Ṽ^{−1}. The resulting basis has the property that x̄_{i} = ȳ_{i} in Ā_{S} for all i = 1, …, t.

We now proceed as in the proof of Lemma 5.5. Let P′ = ∑_{i} A · x_{i} be the free A-submodule of P_{S} generated by the x_{i}. We will construct an isomorphism between P and P′. Let a = ∑ α_{i}x_{i} ∈ A_{S}. We can write α_{i} = f/g with g monic. Write f = qg + r as in Proposition 6.4. Then

\frac{f}{g} = q + \frac{r}{g} ,

with deg(r) < deg(g). Thus,

a = ∑ \frac{r_{i}}{g_{i}} x_{i} + ∑ q_{i}x_{i}.

For each i, write x_{i} = \frac{w_{i}}{h_{i}} with w_{i} ∈ P and h_{i} ∈ S, then

q_{i}x_{i} = q_{i} \frac{w_{i}}{h_{i}} = \frac{q′_{i}h_{i} + r′_{i}}{h_{i}} w_{i} = q′_{i}w_{i} + \frac{r′_{i}}{h_{i}} w_{i},

with deg(r′_{i}) < deg(h_{i}). We obtain a similar decomposition for r_{i}x_{i}. Now apply these decompositions to the elements x_{j} − y_{j} to obtain

x_{j} − y_{j} = ∑ \frac{f_{i}}{g_{i}} w_{i} + ∑ h_{i}w_{i},

with deg(g_{i}) < deg(g_{i}) and h_{i} ∈ A. It is shown in [S2, p. 232] and [La, p. 116] that the elements

x_{j} + ∑ h_{i}w_{i}, j = 1, …, t,

form a free A-basis for P. This completes the proof of Proposition 6.2. □

To complete the proof of Proposition 6.1, let P be a projective kM-module. Then we can find a free basis for P_{M}, where M is the maximal ideal of kN generated by N^{∗} \ {1}. The proof of Proposition 6.1 is now complete. □

Now consider the Karoubi square

kN^{∗} ⟶ kM^{∗}
↓  ↓
kN_{M^{∗}}^{∗} ⟶ kM_{M^{∗}}^{∗}.

Let P be a projective module over kM^{∗}, and assume that we can find a free basis for projective modules over kN^{∗}. We have just completed an algorithm for finding a free basis of P_{M^{∗}} over kM_{M^{∗}}^{∗}. Now use the Patching Algorithm 3.2 to construct a projective module Q over kN^{∗} which extends to P. By hypothesis we can find a free basis for Q, thereby obtaining a free basis for P.

We summarize the results of this section.

Local Algorithm 6.8. Input: A nondegenerate pyramidal extension N ⊂ M of normal toric monoids, and a finitely generated projective module P over kM^{∗}, presented by a matrix A with entries in kM^{∗}. Output: An invertible matrix U over kM_{M^{∗}}^{∗} such that

U · A = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) .

We proceed by induction on the rank of M. If rk(M) = 1, then kM = kM^{∗} is a polynomial ring in one variable and one can find a free basis for P by computing the Smith normal form of the presenting matrix A. So we may assume that rk(M) > 1. Step 1: Compute homothetic submonoids N^{(m)} ⊂ M^{(m)} so that the entries of A are contained in M^{(m)}. Hence P can be viewed as a module over kM^{(m)}. Replace M by M^{(m)}, similarly for N.

Step 2: In this step we compute a free basis for the kM_{M}-module P (Prop. 6.2). Let v be a vertex of the extension N ⊂ M. View P as a module over kM[v^{−1}].

Step 2.1: Find a free basis for P over kM[v^{−1}] as follows. Observe that

kM[v^{−1}] ≅ k[⟨M, v^{−1}⟩],

and

⟨M, v^{−1}⟩ ≅ M′ × ⟨v⟩ ≅ M′ × ℤ.

Since rk(M′) < rk(M), we can compute free bases for projective kM′- modules inductively. Now use the Induction Algorithm 5.8 on the monoid M′ × ℤ to find a free basis for P over kM[v^{−1}]. Let U be the base change matrix corresponding to the given presentation of P. Step 2.2: Now use the algorithm of Proposition 6.3 to compute a free basis for P over kM_{M}, with resulting base change matrix U.

Step 3: Extending scalars to the original monoid ring kM^{∗}, we obtain the desired base change matrix U.

Extension Algorithm 6.9. Input: A normal toric monoid M and a nondegenerate pyramidal extension N ⊂ M, as well as a projective module P over kM^{∗}, presented by a matrix A all of whose entries lie in kM^{∗}. Output: A projective module Q over kN^{∗}, presented by a matrix B with entries in kN^{∗}, together with an isomorphism Q ≅ P over kM^{∗}.

Consider the Karoubi square

kN^{∗} ⟶ kM^{∗}
↓  ↓
(kN)_{M^{∗}}^{∗} ⟶ kM_{M^{∗}}^{∗},

where M^{∗} is the maximal ideal of kN^{∗} generated by N^{∗} \ {1}. Step 1: View P as a module over kM_{M^{∗}}^{∗} by extension of scalars. Now use the Local Algorithm to compute a free basis for P over this ring.

Step 2: Use the Patching Algorithm 3.2 to construct a projective module Q over kN^{∗} which extends to P.

VII. Admissible Sequences

Let M be a normal toric monoid.

Definition. A sequence of submonoids

M = M_{0}, M_{1}, …, M_{n}

of M is an admissible sequence if each M_{i} is a normal toric monoid, and for each i, either

(1) M_{i+1} ⊂ M_{i} is a nondegenerate pyramidal extension, or

(2) M_{i} ⊂ M_{i+1}.

A sequence will be called weakly admissible if we do not require the pyramidal extensions to be nondegenerate.

The objective of this section, Algorithm 7.5, is to construct an admissible sequence of submonoids starting with a normal toric monoid M and ending with a free monoid F contained in M^{∗} with gp(F) = gp(M). The construction will proceed by induction on the rank of M. Before describing the details, we give an overview.

To begin, we find a free monoid F contained inside M^{∗} with gp(F) = gp(M) with which the admissible sequence will end, by using Lemma 2.3. Then, applying Proposition 7.1, which uses the extremal submonoids of M, we find an admissible sequence

M = M_{0}, M_{1}, …, M_{k} ⊊ M^{∗}.

After obtaining a submonoid M_{k} which lies entirely within M^{∗}, we find by means of Lemma 7.2 a homothetic transformation of M such that some homothetic submonoid M^{(m)} lies strictly between M_{k} and M; thus we can extend to the admissible sequence

M = M_{0}, M_{1}, …, M_{k}, M^{(m)}.

Since homothetic transformations behave well with respect to nondegenerate pyramidal extensions,

M = M_{0}, M_{1}, …, M_{k}, M^{(m)}, M_{1}^{(m)}, …, M_{k}^{(m)}

is also an admissible sequence. Choose the homothetic transformation so that its center lies in Int(F) for the chosen free monoid F, then after a sufficient number s of iterations, we have (M^{(m)})^{s} ⊂ F^{∗}. Consequently, we obtain the desired admissible sequence,

M = M_{0}, M_{1}, …, M_{k}, M^{(m)}, …, M_{k}^{(m)}, (M^{(m)})^{2}, …, (M^{(m)})^{s}, F.

Proposition 7.1. [S2, Corollary 11.8] Let M be a normal toric monoid which is not free. Then one can find an admissible sequence

M = M_{0}, M_{1}, …, M_{k}

such that M_{k} ⊊ M^{∗}.

Proof and Algorithm. Step 1: Compute the proper extremal submonoids E_{1}, …, E_{p} of M using Lemma 2.1. Initialize i := 0. Step 2: Set i := i + 1 and E := E_{i}. Since rk(E) ⪇ rk(M), by the Induction Hypothesis 1.2, there is an admissible sequence

E = E_{0}, E_{1}, …, E_{n} = F,

with F free. Extend the sequence to the weakly admissible sequence

(*) E, E_{1}, …, E_{n} = F = ⟨x_{1}, …, x_{s}⟩, E_{n+1} = ⟨x_{2}, …, x_{s}⟩, …, E_{m} = {1}.

Step 3: We now use (*) to form an admissible sequence for M. Notice that at each stage of (*), either E_{i} ⊃ E_{i+1} is a pyramidal extension or E_{i} ⊂ E_{i+1}. Initialize j := 0.

Step 3.1: If E_{j} ⊃ E_{j+1} is a pyramidal extension, we can construct a submonoid M_{j+1} such that M_{j} ⊃ M_{j+1} is a nondegenerate pyramidal extension.

If the pyramidal extension E_{j} ⊃ E_{j+1} is nondegenerate, it follows from the definition of nondegenerate pyramidal extension that E_{j+1} contains an extremal submonoid F such that F ∩Int(E_{j}) ≠ ∅. Compute generators for F using Lemma 2.1. Using elementary linear algebra, determine a hyperplane H = {z ∈ R̄^{d} | c · z = 0}, where c = (c_{1}, …, c_{d}) ∈ ℤ^{d}, passing through the generators of F. Choose the signs on the vector c so that c · x ≥ 0 for all x ∈ E_{j+1}. Define δ : M → ℤ by δ(x) = c · x.

If the pyramidal extension E_{j} ⊃ E_{j+1} is degenerate, it follows from the definition of pyramidal extension that E_{j+1} is an extremal submonoid of E_{j}. Use Lemma 2.1 to find generators for E_{j+1} and determine a hyperplane H = {z ∈ R̄^{d} | c · z = 0} containing these generators with c chosen so that c · x ≥ 0 for all x ∈ E_{j}. Define δ : M → ℤ by δ(x) = c · x.

Next, use Lemma 2.1 to find generators for E_{j} and then find a hyperplane H = {y ∈ R̄^{d} | d · y = 0} passing through these generators. Choose the signs on d so that d · x ≥ 0 for all x ∈ M. Set θ : M → ℤ where θ(x) = d · x.

Now define δ_{k} : M → ℤ as δ_{k} = δ − kθ. Let {g_{1}, …, g_{r}} be the subset of generators of M_{i} not contained in E_{i}. By solving a system of r linear inequalities in the variable k, find a k such that δ_{k}(g_{j}) < 0 for 1 ≤ j ≤ r. Set M_{i+1} = {x ∈ M_{i} | δ_{k}(x) ≤ 0}. Then one can verify that M_{i+1} ⊂ M_{i} is a nondegenerate pyramidal extension. Notice that M_{i+1} ∩ E_{i} = E_{i+1}, and generators for M_{i+1} can be found by using a Hilbert basis algorithm. Step 3.2: If E_{j} ⊂ E_{j+1}, put M_{j+1} equal to the normalization of ⟨M_{j}, E_{j+1}⟩. Generators for M_{j+1} can be found using Lemma 2.2. Step 3.3: Set j := j + 1. If j = m, proceed to Step 4. If j < m and E_{j} ⊃ E_{j+1} is a pyramidal extension, go to Step 3.1. If j < m and E_{j} ⊂ E_{j+1}, go to Step 3.2.

Step 4: If i < p, return to Step 2. Once i = p, we have the desired admissible sequence.

Example. We demonstrate Proposition 7.1 applied to the two-dimensional monoid

M = \{(x, y) ∈ ℕ^{2} | (x, y) · ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(3, 2), (1, 1), (1, 2), (1, 3), (1, 4)⟩.

The proper extremal submonoids of M are E_{1} = ⟨(3, 2)⟩ and E_{2} = ⟨(1, 4)⟩. So, E_{1}, {(0, 0)} and E_{2}, {(0, 0)} are weakly admissible sequences.

First, put δ : E_{1} → ℤ : (x, y) ↦ x. Then {(0, 0)} = {x ∈ E_{1} | δ(x, y) ≤ 0} as desired. Define ϕ : M → ℕ as (x, y) ↦ −2x + 3y. Notice that −2x + 3y = 0 is the equation of the line corresponding to E_{1} with the signs chosen so that ϕ(x, y) > 0 for all (x, y) ∈ M. Then δ_{k} = (2k + 1)x − 3ky. We want to find k ≥ 1 such that

δ_{k}(1, 1) = −k + 1 < 0
δ_{k}(1, 2) = −4k + 1 < 0
δ_{k}(1, 3) = −7k + 1 < 0
δ_{k}(1, 4) = −10k + 1 < 0.

By inspection, one can see that k = 2 works. Thus, if we set

M_{1} = {(x, y) ∈ M | δ_{2}(x, y) = 5x − 6y ≤ 0}
= ⟨(6, 5), (1, 1), (1, 2), (1, 3), (1, 4)⟩,

then the sequence M, M_{1} is admissible.

Next, to continue the sequence, consider E_{2}. Define δ : E_{2} → ℤ by (x, y) ↦ y and ϕ : M_{1} → ℕ by (x, y) ↦ 4x − y. Then setting δ_{4} = −16x + 5y yields an admissible sequence M, M_{1}, M_{2} where

M_{2} = {(x, y) ∈ M_{1} | −16x + 5y ≤ 0}
= ⟨(6, 5), (1, 1), (1, 2), (1, 3), (5, 16)⟩ ⊊ M^{∗}.

Lemma 7.2. [S2, Lemmas 9.2, 9.3] Let M be a normal toric monoid and let N be a submonoid such that N ⊊ M^{∗}. Then there exists a homothetic submonoid M^{(m)} with N ⊊ M^{(m)} ⊊ M.

Proof. Let θ_{m} : M → M be any homothetic transformation with center z ∈ Int(N). First, we claim that M^{(i)} ⊂ M^{(i+1)} for all i ≥ 1. Let x ∈ M^{(i)}. Then

θ_{i}(x)^{i+1} = x^{i(i+1)}z^{ψ(x)(i+1)}
= x^{i(i+1)}z^{ψ(x)i}z^{ψ(x)}
= θ_{i+1}(x)^{i}z^{ψ(x)} ∈ M^{(i+1)}.

Next, we claim that ⋃ M^{(i)} = M^{∗}. Clearly, ⋃ M^{(i)} ⊂ M^{∗}. Let x ∈ Int(M). By definition, x^{k} = yz for some k ∈ ℕ and y ∈ M. Set i = ψ(y). Then θ_{i}(y) = y^{i}z^{i} = x^{ki} ∈ M^{(i)}. But M^{(i)} is normal, so x ∈ M^{(i)}. Consequently, since N ⊊ M^{∗} and M^{∗} is not finitely generated, there must be an m ∈ ℕ with N ⊊ M^{(m)} ⊊ M. □

Algorithm for Lemma 7.2. Input: A normal toric monoid M = ⟨g_{1}, …, g_{t}⟩ and submonoid N ⊊ M^{∗}.

Output: A homothetic submonoid M^{(m)} with N ⊊ M^{(m)} ⊊ M. Step 1: If N is finitely generated, set z equal to the product of all the generators of N. If N is not finitely generated, let z be a finite product of generators such that z ∈ Int(N). Define ψ : M → ℕ by ψ(x) = x_{1}+⋯+x_{d} where x = (x_{1}, …, x_{d}) ∈ M. Let θ_{m} : M → M be the homothetic transformation with center z defined by θ_{m}(x) = x^{m}z^{ψ(x)}. Initialize m := 0.

Step 2: Set m := m + 1. Using Lemma 2.5, compute generators for M^{(m)}. If N ⊊ M^{(m)} ⊊ M, we are done; otherwise repeat Step 2. This process must terminate by the proof of Lemma 7.2 above.

Example. Continuing with the previous example, we apply Lemma 7.2 to

M = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(3, 2), (1, 1), (1, 2), (1, 3), (1, 4)⟩,
N = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−16 & 5 \\ 5 & −6 \end{matrix} ) ≤ (0, 0)\}
= ⟨(6, 5), (1, 1), (1, 2), (1, 3), (5, 16)⟩,
and F = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−2 & 1 \\ 1 & −1 \end{matrix} ) ≤ (0, 0)\}
= ⟨(1, 1), (1, 2)⟩.

Let z = (1, 1) + (1, 2) = (2, 3) and define ψ : M → ℤ by (x, y) ↦ x + y. Then θ_{m} : M → M is defined by θ_{m}(x, y) = m(x, y)+(x+y)(2, 3). Notice θ_{m}(3, 2) = (10+ 3m, 15 + 2m) and θ_{m}(1, 4) = (10 + m, 15 + 4m). Recall we want N ⊂ M^{(m)} ⊂ M^{∗}. So, set m = 22, the smallest m such that \frac{2}{3} < \frac{2m+15}{3m+10} < \frac{5}{6} and \frac{16}{5} < \frac{15+4m}{10+m} < 4. Thus, we have extended our admissible sequence to

M = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(3, 2), (1, 1), (1, 2), (1, 3), (1, 4)⟩,
M_{1} = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(6, 5), (1, 1), (1, 2), (1, 3), (1, 4)⟩,
M_{2} = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(6, 5), (1, 1), (1, 2), (1, 3), (5, 16)⟩,
M^{(22)} = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−103 & 59 \\ 32 & −76 \end{matrix} ) ≤ (0, 0)\},

which by Lemma 7.3 below, can be extended further to the admissible sequence

M, M_{1}, M_{2}, M^{(22)}, M_{1}^{(22)}, M_{2}^{(22)}.

Lemma 7.3. Let M be a normal toric monoid and N ⊂ M a nondegenerate pyramidal extension. Let θ_{m} be a homothetic transformation with center z ∈ Int(N). Then N^{(m)} ⊂ M^{(m)} also forms a nondegenerate pyramidal extension.

Proof. Assume N ⊂ M is a nondegenerate pyramidal extension with δ : M → ℤ such that N = {x ∈ M | δ(x) ≤ 0} and v ∈ M \ N with M integral over ⟨v, N⟩. Then one can verify that N^{(m)} ⊂ M^{(m)} forms a nondegenerate pyramidal extension with respect to δθ_{m} and v. □

28 REINHARD C. LAUBENBACHER AND CYNTHIA J. WOODBURN

Lemma 7.4. Let M = ⟨g_{1}, …, g_{t}⟩ be a normal toric monoid and let F ⊂ M^{∗} be a free monoid with gp(F) = gp(M). Let θ_{m} : M → M be a homothetic transformation with center z ∈ Int(F). Then after a finite number s of iterations, (M^{(m)})^{s} ⊂ F^{∗}. Proof. This result follows directly from Lemma 2.6. □ Example. We now apply Lemma 7.4 to the above example. Recall

M = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−4 & 2 \\ 1 & −3 \end{matrix} ) ≤ (0, 0)\}
= ⟨(3, 2), (1, 1), (1, 2), (1, 3), (1, 4)⟩,
M^{(22)} = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−103 & 59 \\ 32 & −76 \end{matrix} ) ≤ (0, 0)\},
F = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}−2 & 1 \\ 1 & −1 \end{matrix} ) ≤ (0, 0)\}
= ⟨(1, 1), (1, 2)⟩,
and  z = (2, 3).

We want p large enough so that (3, 2) + p(2, 3), (1, 4) + p(2, 3) ∈ Int(F), i.e.

1 < \frac{2 + 3p}{3 + 2p}  and  \frac{4 + 3p}{1 + 2p} < 2.

The smallest such p is p = 3. If we set s = pm = 3(22) = 66, then

(M^{(22)})^{66} = \{(x, y) ∈ ℕ^{2} | (x, y) ( \begin{matrix}a & b \\ c & d \end{matrix} ) ≤ (0, 0)\} ⊂ F,

where

a = −8853803609322864800478421182048227632384771108443008831
0301033665675178270489652496482918655371,
b = 885379564906878648877366695367041415623079
24017832909006082274160386482330378469499773547373963,
c = 59025291060035112738983189310506405247948651
500789076120018389522709538896900449167064136369074,
d = −5902537066257589585603073159428454000948843
8567386255424237149027998234837011632163773507650482.

Consequently,

M, M_{1}, M_{2}, M^{(22)}, M_{1}^{(22)}, M_{2}^{(22)}, (M^{(22)})^{2}, (M_{1}^{(22)})^{2}, (M_{2}^{(22)})^{2}, …, (M^{(22)})^{66}, F

is an admissible sequence beginning with M and ending with F.

Admissible Sequence Algorithm 7.5. Input: A normal toric monoid M = ⟨g_{1}, …, g_{t}⟩. Output: An admissible sequence

M = M_{0}, …, M_{n} = F,

where F ⊂ M^{∗} is a free monoid with gp(F) = gp(M). Step 1: Using Lemma 2.3, find a free monoid F ⊂ M^{∗} with gp(F) = gp(M). Step 2: Apply Proposition 7.1 to form an admissible sequence M = M_{0}, M_{1}, …, M_{k} with M_{k} ⊂ M^{∗}. Step 3: Construct a homothetic submonoid M^{(m)} with center z ∈ Int(F) such that M_{k} ⊊ M^{(m)} ⊊ M by using Lemma 7.2. Step 4: By Lemma 7.3, extend to an admissible sequence

M = M_{0}, M_{1}, …, M_{k}, M^{(m)}, M_{1}^{(m)}, …, M_{k}^{(m)}.

Step 5: By direct calculation, find a p ≥ 0 such that z^{p}g_{i} ∈ Int(F) for i = 1, …, t. Set s = pm. Then, by Lemma 7.4, extending to

M = M_{0}, M_{1}, …, M_{k}, M^{(m)}, M_{1}^{(m)}, …, M_{k}^{(m)}, …, (M^{(m)})^{s}, F,

yields the desired admissible sequence.

VIII. The Algorithm

In this section we summarize the algorithm with the steps in their natural order.

QS-ALGORITHM 8.1. Input:

(1) A toric monoid M, described in terms of generators and relations. The monoid ring kM can then be described as the quotient of a polynomial ring over k modulo the binomial ideal of defining relations [Gi, Theorem 7.11];

(2) a finitely generated projective kM-module P, presented as the cokernel of

a matrix A:

(kM)^{n} ⟶^{A} (kM)^{m} ⟶ P ⟶ 0.

Output: An invertible matrix U with entries in kM such that

U · A = ( \begin{matrix}I & 0 \\ 0 & 0 \end{matrix} ) ,

where I denotes an identity matrix of size t × t, equal to the rank t of P, which in turn is equal to the rank of A. The last t rows of U^{−1} form a free basis for P.

The algorithm proceeds by induction on the rank of M. If rk(M) = 1, then kM is a polynomial ring in one variable, so we can find U by computing the Smith normal form of A. Step 1: Compute the normalization M̃ of M. Since M̃^{∗} = M^{∗} [S2, Lemma 6.6], we can replace M by M̃ and assume from now on that M is normal.

Step 2: Compute all extremal submonoids E_{1}, …, E_{r} of M (Lemma 2.1), listed in order of increasing rank, as in Section 4. Step 3: Carry out the Reduction Algorithm 4.2 to compute a projective module Q over kM^{∗} and an isomorphism from Q to P over kM. Step 4: Find an admissible sequence

M = M_{0}, M_{1}, …, M_{s} = F

(Admissible Sequence Algorithm 7.5). Step 5: Set i = 0, and Q_{0} = Q. While i ≤ s − 1 do:

If M_{i} ⊂ M_{i+1}, then set Q_{i+1} = Q_{i}, viewed as a kM_{i+1}-module by extension of scalars.

Otherwise, apply the Extension Algorithm 6.8 to the nondegenerate pyramidal extension M_{i+1} ⊂ M_{i} to construct a projective module Q_{i+1} and an isomorphism from Q_{i+1} to Q over kM_{i}. Set i := i + 1.

Step 6: Apply the Logar-Sturmfels Algorithm to find a free basis for the module Q_{s} over the polynomial ring kF. Step 7: Extend the resulting base change matrix in the free presentation of Q_{s} to kM to obtain the desired matrix U.

Corollary 8.2. There is a QS-Algorithm over Laurent polynomial rings.

Proof. Let M = ℤ^{n}, then R = kM = k[x_{1}^{±1}, …, x_{n}^{±1}]. Consider the commutative diagram

k[x_{1}^{±1}, …, x_{n−1}^{±1}] ⟶ R
↓  ↓
k  ⟶ k[x_{n}^{±1}].

It is a Milnor square, and the right vertical map, which sends the first n−1 variables to 1, is a split epimorphism. The Induction Algorithm applies to the lower righthand corner, viewed as the monoid ring of the monoid {1} × ℤ. The Patching Algorithm 3.1 applies to carry out an induction argument.

Remark. The same type of argument allows the extension of the algorithm to monoids which do contain nontrivial units, alternatively, to all subrings of Laurent polynomial rings which are generated by monomials and are seminormal [S2, Theorem 1.1′].

References

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

[An] D. F. Anderson, Projective Modules Over Subrings of k[X, Y] Generated by Monomials, Pacific J. Math. 79 (1978), 5–17.

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

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

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

[Fu] W. Fulton, Introduction to Toric Varieties, Annals of Mathematics Studies 131, Princeton University Press, Princeton, NJ, 1993.

[Gi] R. Gilmer, Commutative Semigroup Rings, Chicago Lectures in Mathematics, The University of Chicago Press, Chicago, 1984.

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

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

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

[LS] A. Logar and B. Sturmfels, Algorithms for the Quillen-Suslin Theorem, J. Algebra 145 (1992), 231-239.

[Pa] H. Park, A Computational Theory of Laurent Polynomial Rings and Multidimensional Fir Systems, Ph.D. Thesis, UC Berkeley, Berkeley, CA, 1995.

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

[Qu] D. Quillen, Projective Modules Over Polynomial Rings, Invent. Math. 36 (1976), 167-171.

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

[St] B. Sturmfels, Algorithms in Invariant Theory, Springer Verlag, New York, 1993.

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

[S1] R. G. Swan, Projective Modules Over Laurent Polynomial Rings, Trans. AMS 237 (1978), 111–120.

[S2] , Gubeladze’s Proof of Anderson’s Conjecture, Azumaya Algebras, Actions and Modules (D. Haile and J. Osterburg, eds.), Contemporary Mathematics 124, AMS, Providence, pp. 215–250.

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

[Zi] G. M. Ziegler, Lectures on Polytopes, Grad. Texts in Math 152, Springer Verlag, New York, 1995.

Department of Mathematics, New Mexico State University, Las Cruces, NM 88003, USA

E-mail address: reinhard@nmsu.edu

Department of Mathematics, Pittsburg State University, Pittsburg, KS 66762-7502, USA

E-mail address: cwoodbur@pittstate.edu