BASIC TOOLS FOR COMPUTING

IN MULTIGRADED RINGS

MARTIN KREUZER Fachbereich Mathematik Universität Dortmund D-44221 Dortmund, Germany

          (martin.kreuzer@mathematik.uni-dortmund.de)

LORENZO ROBBIANO Dipartimento di Matematica Universitá di Genova Via Dodecaneso 35 I-16146 Genova, Italy

          (robbiano@dima.unige.it)

Abstract. In this paper we study ℤ^{m}-gradings on the polynomial ring P = K[x_{1}, …, x_{n}] over a field K which are suitable for developing algorithms which take advantage of the full amount of homogeneity contained in a given problem. After introducing and characterizing weakly positive and positive gradings, we provide the basic properties of Macaulay bases and multihomogenization with respect to such gradings as well as the connection between these notions. Finally, we formulate the multihomogeneous version of the Buchberger algorithm for computing homogeneous Gröbner bases and minimal homogeneous systems of generators.

Key words: multigraded ring, homogenization, Macaulay basis, Gröbner basis

2000 Mathematics Subject Classification: 13XXX, 14XXX

1. Introduction

In Computational Commutative Algebra it is a well-known phenomenon that one can improve many algorithms if one knows beforehand that only homogeneous polynomials or vectors of polynomials occur. In some sense, the whole purpose of Gröbner basis theory is to reduce computations for arbitrary polynomials to the case of the most homogeneous polynomials, i.e. to terms, where they acquire a combinatorial nature and are easier to tame.

From these observations it is natural to develop the idea of using the maximum amount of homogeneity contained in a given problem. Thus we want to develop Gröbner basis theory in a multigraded setting. Although many advances have been made in this direction, a unified foundation for this approach seems to be lacking, and our goal here will be to improve that situation.

In Section 2 we start off by studying gradings on polynomial rings which are suitable for actual computations, namely ℤ^{m}-gradings defined by matrices whose columns contain the multidegrees of the indeterminates. After identifying monomial ideals as the most homogeneous ideals, we explain how the gradings change under matrix operations. To use them in actual algorithms, multigradings should have a number of additional properties:

1) The homogeneous components of the polynomial ring and of finitely generated graded modules over it should be finite dimensional vector spaces, i.e. Hilbert functions should exist.

2) The graded version of Nakayama’s lemma should hold, i.e. there should be a well-behaved number of minimal generators.

3) There should be a natural and effective way to compare multidegrees, and the set of all multidegrees occurring in a module should be wellordered (in order to allow algorithms based on chains of terms of decreasing multidegrees).

4) A Macaulay basis (the analogue of a Gröbner basis) should generate the module, and Macaulay bases should be effectively computable. As we shall see, the correct notion for properites 1) and 2) is the notion

of a weakly positive grading, while positive gradings are those enjoying all four properties. Both notions will be described using simple properties of the matrices defining the gradings.

Section 3 contains some results about leading forms and Macaulay bases. In analogy with Gröbner bases, Macaulay bases are defined by the property that their leading forms generate the leading form module. We show that they have good properties in the positively graded case, and we give an algorithm for computing them.

In Section 4 we generalize the process of homogenizing a polynomial to the multigraded situation. All the usual rules for homogenizing polynomials and ideals are generalized, and as a highlight of the section we prove that Macaulay bases are characterized by the property that their multihomogenizations generate the multihomogenization of the ideal. Section 5 contains the multihomogeneous version of the Buchberger algorithm, and a variant which also determines a minimal system of generators contained in a given one.

This paper is largely of an expository nature. Nevertheless, we hope that the effort of providing a unified and easily accessible foundation for multigraded computations is worthwhile, in particular since we are not aware of suitable references containing this material in the generality achieved here. Its content is currently being used as the foundation of the implementation of Gröbner basis theory in the ongoing project CoCoA 5.

As for our notations, we refer the reader to our book [3]. Further developments and applications will be contained in the forthcoming second volume [4].

2. Multigradings

In this section we introduce the gradings on the polynomial ring which we intend to study throughout the paper. We always let K be be a field and P = K[x_{1}, …, x_{n}] the polynomial ring in n indeterminates over K.

REMARK 2.1. Given a commutative monoid Γ and γ_{1}, …, γ_{n} ∈ Γ, there exists exactly one Γ-grading on P such that non-zero constant polynomials are homogeneous of degree zero and, for i = 1, …, n, the indeterminate x_{i} is homogeneous of degree γ_{i}.

Under this grading, the set {γ ∈ Γ | P_{γ} ≠ 0} is the submonoid of Γ generated by {γ_{1}, …, γ_{n}}.

Here we are interested in the case Γ = ℤ^{m}. We can thus specify a grading by a matrix.

DEFINITION 2.2. Let m ≥ 1, and let P = K[x_{1}, …, x_{n}] be equipped with a ℤ^{m}-grading such that K ⊆ P_{0} and x_{1}, …, x_{n} are homogeneous elements.

a) For j = 1, …, n, let (w_{1j}, …, w_{mj}) ∈ ℤ^{m} be the degree of x_{j}. The matrix W = (w_{ij}) ∈ Mat_{m,n}(ℤ) is called the degree matrix of the given grading. The rows of this matrix are called the weight vectors of the indeterminates x_{1}, …, x_{n}.

b) Conversely, given a matrix W = (w_{ij}) ∈ Mat_{m,n}(ℤ), we can consider the ℤ^{m}-grading on P such that K ⊆ P_{0} and such that the indeterminates are homogeneous elements whose degrees are given by the columns of W. In this case, we say that P is multigraded by W, or simply graded by W.

c) Let d ∈ ℤ^{m}. The set of homogeneous elements of P of degree d is denoted by P_{W,d}, or simply by P_{d} if it is clear which grading we are considering. A polynomial f ∈ P_{W,d} is also called homogeneous of multidegree d, or simply of degree d, and we write deg_{W} (f) = d.

Note that a multidegree is a column vector in ℤ^{m}, whereas a weight vector will be represented as a row. If a grading on P is defined by a matrix W ∈ Mat_{m,n}(ℤ), then the degree of a term t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} can be computed by deg_{W} (t) = W · (α_{1}, …, α_{n})^{tr}. Therefore we have {d ∈ ℤ^{m} | P_{W,d} ≠ 0} = {W · (α_{1}, …, α_{n})^{tr} | (α_{1}, …, α_{n}) ∈ ℕ^{n}}.

The grading on P by W = (1, …, 1) is called the standard grading. A monomial ideal in P is homogeneous with respect to every multigrading. In fact, it is easy to see that monomial ideals are characterized by this property.

PROPOSITION 2.3. For an ideal I of P, the following conditions are equivalent.

a) The ideal I is a monomial ideal.

b) There is a non-singular matrix W ∈ Mat_{n}(ℤ) such that I is homogeneous w.r.t. the multigrading defined by W.

c) For every non-singular matrix W ∈ Mat_{n}(ℤ), the ideal I is homogeneous w.r.t. the multigrading defined by W.

Proof. It suffices to show that b) implies a). Given a homogeneous polynomial f ∈ I_{W,d} and two terms t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} and t′ = x_{1}^{β_{1}} ⋯ x_{n}^{β_{n}} in its support, it follows that W · (α_{1}, …, α_{n})^{tr} = deg_{W} (t) = d = deg_{W} (t′) = W · (β_{1}, …, β_{n})^{tr}. Since det(W) ≠ 0, we get (α_{1}, …, α_{n}) = (β_{1}, …, β_{n}) and t = t′. ⊓ ⊔

In this sense monomial ideals are the most homogeneous ideals. If two matrices in Mat_{m,n}(ℤ) can be transformed into each other by elementary row operations, the relation between the corresponding multigradings on P is simple to understand.

PROPOSITION 2.4. Let m ≥ 1, let W ∈ Mat_{m,n}(ℤ), let P be multigraded by W, and let V ∈ Mat_{ℓ,m}(ℤ) for some ℓ ≥ 1. Then P is also multigraded by V · W, and we have P_{W,d} ⊆ P_{V ·W,V ·d} for all d ∈ ℤ^{m}.

Moreover, if the map ψ : ℤ^{m} ⟶ ℤ^{ℓ} given by V is injective, we have P_{W,d} = P_{V ·W,V ·d} for all d ∈ ℤ^{m}.

Proof. For a term t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} ∈ P_{W,d}, we have deg_{V ·W} (t) = V · W · (α_{1}, …, α_{n})^{tr} = V · d, and therefore t ∈ P_{V ·W,V ·d}. If ψ is injective, then V ·W ·(α_{1}, …, α_{n})^{tr} = deg_{V ·W} (t) = V ·d implies W ·(α_{1}, …, α_{n})^{tr} = d, i.e. we get t ∈ P_{W,d} and the inclusion P_{W,d} ⊆ P_{V ·W,V ·d} is in fact an equality. ⊓ ⊔

Given δ_{1}, …, δ_{r} ∈ ℤ^{m}, the graded free P -module ⨁_{i=1}^{r} P (−δ_{i}) is naturally equipped with an induced ℤ^{m}-grading given by (⨁_{i=1}^{r} P (−δ_{i}))_{d} = ⨁_{i=1}^{r} P_{W,d−δ_{i}} for all d ∈ ℤ^{m}. We shall from now on denote this graded P -module by F. For a graded submodule M ⊆ F, we shall say that M is multigraded by W and denote its homogeneous component of multidegree d by M_{W,d}. From the preceding proposition it follows that, given a matrix V ∈ Mat_{ℓ,m}(ℤ) for some ℓ ≥ 1, the module M is also a graded submodule of ⨁_{i=1}^{r} P (−V · δ_{i}) w.r.t. the multigrading defined by V · W.

Using the preceding proposition, we can clearly assume that the rows of the matrix W are ℤ-linearly independent. Unless stated otherwise, we shall from now on make this assumption.

In order to be useful for explicit computer calculations, the multigradings under consideration should have additional properties. For instance, the homogeneous components of the polynomial rings and finitely generated graded modules over it should be finite dimensional K-vector spaces. Moreover, the finiteness proof of many algorithms depends on the fact that no infinite sequence of homogeneous elements of strictly decreasing multidegrees exist. In order to have such good properties, we need some positivity assumptions for our multigradings.

DEFINITION 2.5. Let P be multigraded by W, and let w_{1}, …, w_{m} be the rows of W.

a) The multigrading defined by W is called weakly positive if there exist integers a_{1}, …, a_{m} ∈ ℤ such that a_{1}w_{1}+⋯+a_{m}w_{m} has positive entries only.

b) The multigrading defined by W is called positive if rk(W) = m, if no column of W is zero, and if the first non-zero entry in each column of W is positive.

The notion of a weakly positive grading is precisely what we need for having finite dimensional homogeneous components and a graded Nakayama lemma.

PROPOSITION 2.6. Let P be weakly positively graded by W, and let M be a finitely generated graded P -module.

a) We have P_{W,0} = K and dim_{K}(M_{W,d}) < ∞ for every d ∈ ℤ^{m}.

b) There exists a monoid ordering τ on the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} which is a well-ordering.

c) There exists a module ordering σ on the Γ-submonomodule Σ of ℤ^{m} generated by {d ∈ ℤ^{m} | M_{W,d} ≠ 0} which is a well-ordering and compatible with τ.

d) The Graded Version of Nakayama’s Lemma holds: Homogeneous elements v_{1}, …, v_{s} ∈ M generate the module M if and only if their residue classes \overline{v}_{1}, …, \overline{v}_{s} in M/(x_{1}, …, x_{n})M generate that K-vector space.

In particular, every homogeneous system of generators of M contains a minimal one and all irredundant homogeneous systems of generators of M have the same number of elements, μ(M).

Proof. First we show a). By assumption, there exists a matrix V = (a_{1}, …, a_{m}) ∈ Mat_{1,m}(ℤ) such that V · W has positive entries only. Using Proposition 2.4, we see that P_{W,0} ⊆ P_{V,0}. Now it suffices to note that every term t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} ≠ 1 has a positive degree deg(t) = V · W · (α_{1}, …, α_{n})^{tr} > 0.

In order to prove the second claim, we choose a finite homogeneous system of generators of M and consider the corresponding representation M ≅ ⨁_{i=1}^{r} P (−δ_{i})/N with δ_{1}, …, δ_{r} ∈ ℤ^{m} and a graded submodule N of ⨁_{i=1}^{r} P (−δ_{i}).

Clearly, it suffices to prove the claim for ⨁_{i=1}^{r} P (−δ_{i}), hence for every P (−δ_{i}). Since P (−δ_{i})_{d} = P_{d−δ_{i}}, it suffices to prove that dim_{K}(P_{W,d}) < ∞ for all d ∈ ℤ^{m}. By assumption, there exists a row-matrix V such that V · W has positive entries only. We use Proposition 2.4 to see that P_{W,d} ⊆ P_{V ·W,V ·d}. Hence we only have to show that the K-vector spaces P_{V ·W,i} are finite dimensional for all i ∈ ℤ. Clearly their bases {x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} | V · W · (α_{1}, …, α_{n})^{tr} = i} are finite, because V · W has positive entries.

Next we show b). Using the definition and some elementary row operations on W, we find a matrix U ∈ Mat_{m}(ℤ) such that det(U) ≠ 0 and U · W has positive entries only. For vectors d, d′ ∈ ℤ^{m}, we define d ≥_{τ} d′ if and only if U · d ≥_{Lex} U · d′. Clearly, this rule specifies a monoid ordering τ on ℤ^{m}. Its restriction to the submonoid Γ is again a monoid ordering. It remains to show that τ|_{Γ} is a well-ordering on Γ.

Suppose that d_{1} >_{τ} d_{2} >_{τ} ⋯ is an infinite descending chain of elements of Γ. Then, by definition, we have U · d_{1} >_{Lex} U · d_{2} >_{Lex} · · ·. For every degree d_{i} ∈ Γ, there exists a term t_{i} = x_{1}^{α_{i1}} ⋯ x_{n}^{α_{in}} such that d_{i} = W · (α_{i1}, …, α_{in})^{tr}. Therefore we have U · d_{i} = U · W · (α_{i1}, …, α_{in})^{tr}, and this vector has non-negative entries only. Since Lex is a term ordering on ℕ^{n}, Theorem 1.4.19 of [3] implies that an infinite chain U ·d_{1} >_{Lex} U ·d_{2} >_{Lex} ⋯ does not exist.

To prove c), we let {m_{1}, …, m_{s}} ⊆ M \ {0} be a homogeneous system of generators of the P -module M, and we let γ_{i} = deg(m_{i}) for i = 1, …, s. By Corollary 1.7.11 of [3], we have Σ ⊆ ∪_{i=1}^{s}(Γ + γ_{i}). Thus we may define σ to be the restriction of the term ordering τ constructed above to the Γ-submonomodule Σ of ℤ^{m}. Clearly, σ is a module ordering which is compatible with τ.

Now we show that the restriction of τ to ∪_{i=1}^{s}(Γ + γ_{i}) is a well-ordering. Suppose there exists a chain d_{1} >_{τ} d_{2} >_{τ} ⋯ in ∪_{i=1}^{s}(Γ + γ_{i}). Then one of the sets Γ + γ_{i} has to contain infinitely many multidegrees d_{j}, i.e. there exist indices j_{1} < j_{2} < ⋯ such that d_{j_{1}} >_{τ} d_{j_{2}} >_{τ} ⋯ is a chain in Γ + γ_{i}. Now the chain d_{j_{1}} − γ_{i} >_{τ} d_{j_{2}} − γ_{i} >_{τ} ⋯ contradicts the fact that τ is a well-ordering on Γ.

Finally, we prove d). By Proposition 1.4.18 of [3], every well-ordering is a term ordering. Hence the ordering τ on Γ in b) is a term ordering, which implies that P_{+} = (x_{1}, …, x_{n}). Thus d) follows from Corollary 1.7.16.a of [3], because we have P/P_{+} ≅ K = P_{W,0} by a) and because K is a field.

⊓ ⊔

As we mentioned above, for practical computations we need the somewhat stronger notion of a positive multigrading. The reason can be gleaned from part b) of the following proposition which provides us with several characterization of positive gradings. Recall that a module ordering σ on the set of terms 𝕋^{n}⟨e_{1}, …, e_{r}⟩ of the graded free module F is called degree compatible or compatible with deg_{W} if deg_{W} (te_{i}) >_{Lex} deg_{W} (t′e_{j}) implies te_{i} >_{σ} t′e_{j} for all t, t′ ∈ 𝕋^{n} and all i, j ∈ {1, …, r}.

PROPOSITION 2.7. Let P be graded by W, where W has ℤ-linearly independent rows and non-zero columns. Then the following conditions are equivalent.

a) The grading on P given by W is positive.

b) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a well-ordering.

c) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a term ordering.

d) There exists a term ordering τ on 𝕋^{n} which is compatible with deg_{W}.

e) There exists a module term ordering σ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ which is compatible with the grading given by W.

Proof. To prove that a) implies b), we note that it suffices to show that every infinite chain d_{1} ≥_{Lex} d_{2} ≥_{Lex} ⋯ in Γ is eventually stationary.

For every i ≥ 1, we can find a term t_{i} ∈ 𝕋^{n} such that d_{i} = deg_{W} (t_{i}). For j = 1, …, m, let C_{j} denote the set of all indices k ∈ {1, …, n} such that the k^{th} column of W has its first non-zero entry in the j^{th} row. Then every term t_{i} has a decomposition t_{i} = t_{i1} ⋯ t_{im}, where t_{ij} is a term of the form t_{ij} = ∏_{k∈C_{j}} x_{k}^{α_{ijk}} with α_{ijk} ≥ 0. In other words, we group t_{i} into terms t_{ij} involving only the indeterminates corresponding to the set C_{j}. Furthermore, for every term t_{i} ≠ 1, we define δ(t_{i}) = min{j ∈ {1, …, m} | t_{ij} ≠ 1}, and we let δ(1) = m + 1.

In order to prove the claim, it suffices to find a subchain of d_{1} ≥_{Lex} d_{2} ≥_{Lex} ⋯ which is eventually stationary. If δ(t_{1}) = m + 1, i.e. if t_{1} = 1, the whole chain is stationary, since Lex is a term ordering on 𝕋^{n}. Now let i = δ(t_{1}) ≤ m. When we compute the multidegree of t_{1}, we see that it is of the form d_{1} = deg_{W} (t_{1}) = W · log(t_{1}) = (0, …, 0, a, ∗, …, ∗)^{tr}, where a > 0 occurs in the i^{th} position.

Since W has positive entries in columns C_{i} of the i^{th} row w_{i}, there are only finitely many terms t_{1i} such that we have a = w_{i} ·log(t_{1i}). Hence there exists a subchain d_{ℓ_{1}} ≥_{Lex} d_{ℓ_{2}} ≥_{Lex} ⋯ such that 1 ≤ ℓ_{1} < ℓ_{2} < ⋯ and such that the terms t_{ℓ_{1}}, t_{ℓ_{2}}, … satisfy t_{ℓ_{1} i} = t_{ℓ_{2} i} = · · ·. For j ≥ 1, we now define t′_{j} = t_{ℓ_{j}}/t_{ℓ_{j} i} and d′_{j} = deg_{W} (t′_{j}). Then we obtain a chain d′_{1} ≥_{Lex} d′_{2} ≥_{Lex} ⋯ such that δ(t′_{1}) = i + 1. By descending induction on i, we are done.

Since implication “b) ⇒ c)” holds quite generally (see [3], Prop. 1.4.18), we now show “c) ⇒ d)”. As W has ℤ-linearly independent rows {w_{1}, …, w_{m}}, we can find n−m further rows {w_{m+1}, …, w_{n}} such that {w_{1}, …, w_{n}} is a ℤ-basis of ℤ^{n}. Hence the matrix V ∈ Mat_{n,n}(ℤ) with rows w_{1}, …, w_{n} satisfies det(V) ≠ 0. Then τ = Ord(V) is a term ordering on 𝕋^{n} by Proposition 1.4.12 of [3], since deg_{W} (x_{i}) ≥_{Lex} 0 implies that the first non-zero entry of each column of V is positive. Furthermore, the term ordering τ is clearly compatible with deg_{W}.

To show that d) implies e), we define an ordering σ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ as follows. Given te_{i}, t′e_{j} ∈ 𝕋^{n}⟨e_{1}, …, e_{r}⟩, we let te_{i} ≥_{σ} t′e_{j} if deg_{W} (te_{i}) >_{Lex} deg_{W} (t′e_{j}), or if deg_{W} (te_{i}) = deg_{W} (t′e_{j}) and i < j, or if deg_{W} (te_{i}) = deg_{W} (t′e_{j}) and i = j and t ≥_{τ} t′. It is easy to check that σ is a module ordering. We note that te_{i} ≥_{σ} t′e_{i} if and only if t ≥_{τ} t′, i.e. inside one of the components of F the ordering σ is induced by τ. Thus we see that te_{i} ≥_{σ} e_{i} for all t ∈ 𝕋^{n} and all i ∈ {1, …, r}. Hence σ is a module term ordering. By construction, σ is degree compatible.

Finally, we show that a) follows from e). For i = 1, …, n, we have x_{i}e_{1} >_{σ} e_{1}, and thus deg_{W} (x_{i}e_{1}) = deg_{W} (x_{i}) + deg_{W} (e_{1}) ≥_{Lex} deg_{W} (e_{1}). Consequently, we have deg_{W} (x_{i}) ≥_{Lex} 0. Since deg_{W} (x_{i}) is the i^{th} column of W and no column of W is zero, this yields the claim. ⊓ ⊔

We end this section with further useful properties of positive gradings.

COROLLARY 2.8. Let P be positively graded by W, and let M be a graded submodule of the graded free P -module F.

a) The ring P is weakly positively graded by W.

b) The restriction of Lex to the set Σ = {d ∈ ℤ^{m} | M_{W,d} ≠ 0} is a well-ordering.

Proof. To prove a), we let C_{i} denote for i = 1, …, m the set of all indices j ∈ {1, …, n} such that the j^{th} column of W has its first non-zero entry in the i^{th} row. We start with row number i_{0} = max{i | C_{i} ≠ ∅}. If C_{i_{0}−1} ≠ ∅, we add to this row a high enough multiple of row i_{0} − 1 so that the result has positive entries in the columns indexed by C_{i_{0}−1}. The entries in the columns corresponding to C_{i_{0}} do not change, since row i_{0} − 1 has zero entries there. If C_{i_{0}−2} ≠ ∅, we then add a high enough multiple of row i_{0} − 2 to make the entries indexed by C_{i_{0}−2} positive, and so on. Finally we arrive at a row which has positive entries in columns C_{1} ∪ ⋯ ∪ C_{i_{0}}, i.e. everywhere.

Claim b) follows from part b) of the proposition, since we have Σ ⊆

∪_{i=1}^{r}(Γ + δ_{i}). ⊓ ⊔

3. Multi Leading Forms

As before, we let K be a field, P = K[x_{1}, …, x_{n}] a polynomial ring over K which is multigraded by W ∈ Mat_{m,n}(ℤ), and F = ⨁_{i=1}^{r} P (−δ_{i}) a graded free P -module.

DEFINITION 3.1. Let M be a graded P -module, let v ∈ M \ {0}, and let v = v_{d_{1}} + ⋯ + v_{d_{s}} be its decomposition into homogeneous components, where d_{i} = deg_{W} (v_{d_{i}}) ∈ ℤ^{m} for i = 1, …, s. Without loss of generality, we may assume that we have d_{1} >_{Lex} ⋯ >_{Lex} d_{s}.

Then the tuple deg_{W} (v) = d_{1} ∈ ℤ^{m} is called the multidegree of v with respect to the multigrading defined by W. If it is clear which multigrading we are considering, we shall also write deg(v) and call it simply the degree of v. The element LF_{W} (v) = v_{d_{1}} ∈ M is called the leading form of v with respect to the multigrading defined by W. For the zero vector, we define LF_{W} (0) = 0.

Notice that multidegrees are always compared lexicographically. For the standard grading, this definition agrees with the usual definition of the degree and the leading form of a polynomial. We have the following rules for computing with leading forms.

REMARK 3.2. Let v_{1}, v_{2} ∈ M \ {0}, and let f ∈ P.

a) If deg_{W} (v_{1}) = deg_{W} (v_{2}) and LF_{W} (v_{1}) ≠ − LF_{W} (v_{2}), then we have LF_{W} (v_{1} + v_{2}) = LF_{W} (v_{1}) + LF_{W} (v_{2}).

b) If deg_{W} (v_{1}) >_{Lex} deg_{W} (v_{2}), then we have LF_{W} (v_{1} + v_{2}) = LF_{W} (v_{1}). c) We have LF_{W} (fv_{1}) = LF_{W} (f) · LF_{W} (v_{1}).

Next we introduce analogues for the notions of leading term ideals and Gröbner bases.

DEFINITION 3.3. Let M be a P -submodule of F.

a) The graded P -submodule LF_{W} (M) = ⟨LF_{W} (v) | v ∈ M \ {0}⟩ of F is called the leading form module of M with respect to the multigrading defined by W.

b) A set of vectors {v_{1}, …, v_{s}} ⊆ M \ {0} is called a Macaulay basis (or an H-basis) of M with respect to the multigrading defined by W if we have LF_{W} (M) = ⟨LF_{W} (v_{1}), …, LF_{W} (v_{s})⟩.

The following proposition shows that a Macaulay basis generates the module if the grading is positive. We note that this result does not hold for weakly positive gradings.

PROPOSITION 3.4. Let M be a P -submodule of F, and let the multigrading defined by W be positive. Then every Macaulay basis {v_{1}, …, v_{s}} ⊆ M \ {0} of M is a system of generators of the P -module M.

Proof. Suppose that the claim is wrong, i.e. that ⟨v_{1}, …, v_{s}⟩ ⊂ M. From Corollary 2.8.b we know that Σ = {d ∈ ℤ^{m} | F_{W,d} ≠ 0} is well-ordered with respect to Lex. Thus there exists a vector v ∈ M \ ⟨v_{1}, …, v_{s}⟩ such that d = deg_{W} (v) is minimal. Using Corollary 1.7.11 of [3], we can write LF_{W} (v) = f_{1} LF_{W} (v_{1}) + ⋯ + f_{s} LF_{W} (v_{s}) with homogeneous polynomials f_{1}, …, f_{s} ∈ P of degree deg_{W} (f_{i}) = d − deg_{W} (v_{i}) for i = 1, …, s. Now the rules given in Remark 3.2 show deg_{W} (v − f_{1}v_{1} − ⋯ − f_{s}v_{s}) <_{Lex} d. Because of the minimality of d, this implies that there are polynomials g_{1}, …, g_{s} such that v − f_{1}v_{1} − ⋯ − f_{s}v_{s} = g_{1}v_{1} + ⋯ + g_{s}v_{s}. This representation contradicts v ∉ M and finishes the proof. ⊓ ⊔

Furthermore, we know from Section 2 that positive multigradings are characterized by the existence of degree compatible term orderings. Now we can connect the two fundamental notions of a Gröbner basis and a Macaulay basis as follows.

PROPOSITION 3.5. Let P be positively graded by W ∈ Mat_{m,n}(ℤ), let σ be a term ordering which is compatible with deg_{W}, and let G = {g_{1}, …, g_{s}} be a σ-Gröbner basis of M.

a) The set {LF_{σ}(g_{1}), …, LF_{σ}(g_{s})} is a σ-Gröbner basis of LF_{W} (M).

b) The set G is a Macaulay basis of M with respect to W.

Proof. Let v ∈ M \ {0}. Since σ is degree compatible, the term LT_{σ}(v) has to be one of the terms in Supp(LF_{W} (v)), and therefore LT_{σ}(v) = LT_{σ}(LF_{W} (v)). By assumption, LT_{σ}(v) is divisible by LT_{σ}(g_{j}) for some j ∈ {1, …, s}, so a) is proved.

To show b), we let v ∈ M \ {0}. Since G is a σ-Gröbner basis of M, there exists an index i_{1} ∈ {1, …, s} and a term t_{1} ∈ 𝕋^{n} such that LT_{σ}(v) = t_{1} LT_{σ}(g_{i_{1}}). Now we consider the vector v′ = v − \frac{LC_{σ}(v)}{LC_{σ}(g_{i_{1}})} t_{1} g_{i_{1}}. Either deg_{W} (v′) <_{Lex} deg_{W} (v), or we find an index i_{2} ∈ {1, …, s} and a term t_{2} ∈ 𝕋^{n} such that LT_{σ}(v′) = t_{2} LT_{σ}(g_{i_{2}}). Continuing in this way for all terms in Supp(LF_{W} (v)), we finally arrive at a representation

v = c_{1}t_{1}g_{i_{1}} + ⋯ + c_{ℓ}t_{ℓ}g_{i_{ℓ}} + ṽ

with c_{1}, …, c_{ℓ} ∈ K, with t_{1}, …, t_{ℓ} ∈ 𝕋^{n}, with i_{1}, …, i_{ℓ} ∈ {1, …, s}, and with a vector ṽ ∈ M such that deg_{W} (ṽ) <_{Lex} deg_{W} (v) or ṽ = 0. Thus we have LF_{W} (v) = c_{1}t_{1} LF_{W} (g_{i_{1}}) + ⋯ + c_{ℓ}t_{ℓ} LF_{W} (g_{i_{ℓ}}). ⊓ ⊔

Now we use this result to show how one can compute Macaulay bases effectively.

COROLLARY 3.6. (Computation of Macaulay Bases) Let P be positively graded by W ∈ Mat_{m,n}(ℤ), and let M be a P -submodule of F. Consider the following instructions.

1) Choose a matrix W′ ∈ Mat_{n−m,n}(ℕ) such that V = \binom{W}{W′} is nonsingular. (For instance, one can append suitable standard basis vectors.)

2) Using Buchberger’s Algorithm, compute a Gröbner basis G of M with respect to the term ordering Ord(V).

3) Return the result G and stop.

This is an algorithm which computes a Macaulay basis G of M with respect to the grading given by W.

Proof. Clearly, we may assume that M ≠ 0. The matrix V constructed in step 1) has the property that the first non-zero entry in each column is positive. By Proposition 1.4.12 of [3], the monoid ordering σ = Ord(V) is then a term ordering. Hence Buchberger’s Algorithm can be used to compute a σ-Gröbner basis of M. By the proposition, this Gröbner basis is also a Macaulay basis of M with respect to the multigrading defined by W. ⊓ ⊔ 4. Multihomogenization

As above, we let K be a field and assume that the polynomial ring P = K[x_{1}, …, x_{n}] is multigraded by W ∈ Mat_{m,n}(ℤ). In this situation we intend to generalize the processes of homogenizing and dehomogenizing polynomials as follows. First we choose new indeterminates y_{1}, …, y_{m} (called homogenizing indeterminates) and equip \overline{P} = K[y_{1}, …, y_{m}, x_{1}, …, x_{n}] with the multigrading defined by the matrix \overline{W} = (I_{m} | W), where I_{m} denotes the identity matrix of size m × m.

DEFINITION 4.1. Given a polynomial f ∈ P \{0}, we write f = c_{1}t_{1}+⋯+ c_{s}t_{s} with c_{1}, …, c_{s} ∈ K \ {0} and pairwise distinct terms t_{1}, …, t_{s} ∈ 𝕋^{n}. For i = 1, …, s, we write deg_{W} (t_{i}) = (τ_{i1}, …, τ_{im}) ∈ ℤ^{m}. Furthermore, for j = 1, …, m, we let μ_{j} = max{τ_{ij} | i = 1, …, s} be the maximum of the j^{th} components of the multidegrees of the terms in the support of f. Then the multihomogenization of f is the polynomial

f^{hom} = ∑_{i=1}^{s} c_{i} t_{i} y_{1}^{μ_{1}−τ_{i1}} ⋯ y_{m}^{μ_{m}−τ_{im}} ∈ \overline{P}

For the zero polynomial, we set 0^{hom} = 0. If it is clear which grading we are considering, we shall simply call f^{hom} the homogenization of f. The tuple topdeg_{W} (f) = (μ_{1}, …, μ_{m}) is called the top degree of f.

Clearly, f^{hom} is homogeneous of multidegree deg\overline{W} (f^{hom}) = topdeg_{W} (f) in \overline{P}. The generalization of the process of dehomogenizing a polynomial can be defined as usual. Indeed, given a multihomogeneous polynomial F ∈ \overline{P}, we let the dehomogenization of F be the polynomial F^{deh} = F (1, …, 1, x_{1}, …, x_{m}) ∈ P. The well-known rules for homogenizing and dehomogenizing polynomials generalize as follows.

PROPOSITION 4.2. (Rules for Multihomogenizing Polynomials) Let polynomials f, g ∈ P and homogeneous polynomials F, G ∈ \overline{P} be given.

a) Let f ≠ 0, let d = topdeg_{W} (f), and let f = f_{1} + ⋯ + f_{r} be the decomposition of f into its multihomogeneous components, where f_{i} is homogeneous of multidegree d_{i} = deg_{W} (f_{i}) for i = 1, …, r. Then we have

f^{hom} = y^{d−d_{1}} f_{1} + ⋯ + y^{d−d_{r}} f_{r}

where y^{d−d_{i}} = y_{1}^{α_{i1}} ⋯ y_{m}^{α_{im}} for d − d_{i} = (α_{i1}, …, α_{im}) ∈ ℤ^{m}.

b) We have (f^{hom})^{deh} = f.

c) If fg ≠ 0, we have topdeg_{W} (fg) = topdeg_{W} (f) + topdeg_{W} (g).

d) We have (fg)^{hom} = (f^{hom})(g^{hom}). e) Let f, g, f + g ∈ P \ {0}, let d = topdeg_{W} (f) and d′ = topdeg_{W} (g). If

we let d′′ be the componentwise maximum of d and d′, then we have

y^{d′′−topdeg_{W} (f+g)} · (f + g)^{hom} = y^{d′′−d} · f^{hom} + y^{d′′−d′} · g^{hom}

f) We have (F G)^{deh} = F^{deh} G^{deh} and (F + G)^{deh} = F^{deh} + G^{deh}.

g) Suppose that F^{deh} ≠ 0, and let s_{j} = max{i ≥ 0 | y_{j}^{i} divides F } for j = 1, …, m. Then we have y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}} · (F^{deh})^{hom} = F.

Proof. Claim a) follows by combining the terms t_{1}, …, t_{s} in Definition 4.1 into groups according to their multidegrees. Claim b) follows easily from the definition. To prove c), we proceed component by component. Let j ∈ {1, …, m}, let topdeg_{W} (f) = (μ_{1}, …, μ_{m}), and let topdeg_{W} (g) = (ν_{1}, …, ν_{m}). Then we write f = f′ + f′′ where f′ contains the terms of f whose multidegree has j^{th} component μ_{j} and f′′ contains the remaining terms of f. Similarly, we decompose g = g′ + g′′. Then fg = f′g′ + (f′g′′ + f′′g′ + f′′g′′) where f′g′ consists of terms whose multidegree has j^{th} component μ_{j} + ν_{j} and the second summand consists of terms whose multidegree has a smaller j^{th} component. Hence the j^{th} component of topdeg_{W} (fg) is μ_{j} + ν_{j}, as we wanted to show.

For the proof of claim d), we use a) and c). Claim e) follows easily from the definition, and f) expresses the fact that dehomogenization is nothing but the substitution homomorphism y_{i} ↦ 1 for i = 1, …, m. Finally we prove claim g). We write F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}} F̃, where F̃ is not divisible by one of the indeterminates y_{1}, …, y_{m}. We need to show that (F̃^{deh})^{hom} = F̃.

To this end, we note the fact that no two terms in the support of F̃ dehomogenize to the same term, since the dehomogenization of the term t = y_{1}^{α_{1}} ⋯ y_{m}^{α_{m}}x_{1}^{β_{1}} ⋯ x_{n}^{β_{n}} is t^{deh} = x_{1}^{β_{1}} ⋯ x_{n}^{β_{n}} and the exponents α_{1}, …, α_{m} are determined by t^{deh} and the equation (α_{1}, …, α_{m})^{tr} = deg\overline{W} (F̃) − W · (β_{1}, …, β_{n})^{tr}. Moreover, the multidegree of (F̃^{deh})^{hom} equals deg\overline{W} (F̃), because for every j ∈ {1, …, m} there exists one term in the support of F̃ which is not divisible by y_{j}. Altogether, the multihomogenization of F̃^{deh} is F̃, as claimed. ⊓ ⊔

Now we can give the standard definitions of the multihomogenization and dehomogenization of ideals. In other words, given an ideal I in P, we call I^{hom} = (f^{hom} | f ∈ I) the multihomogenization of I, and given a homogeneous ideal J in \overline{P}, we call J^{deh} = (F^{deh} | F ∈ J homogeneous) the dehomogenization of J. Clearly, the ideal J^{deh} is the image of J under the substitution homomorphism y_{i} ↦ 1 for i = 1, …, m. The multihomogenization of ideals obeys the following rules.

PROPOSITION 4.3. (Rules for Multihomogenizing Ideals) Let I be an ideal in P and J a homogeneous ideal in \overline{P}.

a) We have (I^{hom})^{deh} = I. In particular, the operation which associates to an ideal in P its homogenization is injective, and the operation which associates to a homogeneous ideal in \overline{P} its dehomogenization is surjective.

b) For a homogeneous polynomial F ∈ \overline{P}, we have

F ∈ I^{hom} ⇔ F^{deh} ∈ I
⇔ F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}f^{hom} for some f ∈ I and s_{1}, …, s_{m} ∈ ℕ

c) For a homogeneous polynomial F ∈ \overline{P}, we have F^{deh} ∈ J^{deh} if and only if (y_{1} ⋯ y_{m})^{s}F ∈ J for some s ≥ 0.

d) We have J ⊆ (J^{deh})^{hom} = J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞}.

e) If I ≠ P, then y_{1} ⋯ y_{m} is a non-zerodivisor for \overline{P} /I^{hom}.

f) If I is a proper homogeneous ideal in P, then we have I^{hom} = I · \overline{P}. In particular, in this case y_{1} ⋯ y_{m} is a non-zerodivisor for \overline{P} /I · \overline{P}.

Proof. First we prove a). By Proposition 4.2.b, we have I ⊆ (I^{hom})^{deh}. Now let f ∈ (I^{hom})^{deh}. By definition, the polynomial f is of the form f = (∑_{i=1}^{r} G_{i}g_{i}^{hom})^{deh}, where G_{1}, …, G_{r} ∈ \overline{P} and g_{1}, …, g_{r} ∈ I. Using Proposition 4.2.f, it follows that f = ∑_{i=1}^{r} G_{i}^{deh}g_{i} ∈ I.

Next we show b). For F ∈ I^{hom}, we have F^{deh} ∈ (I^{hom})^{deh} = I by a). Given F ∈ \overline{P} such that F^{deh} ∈ I, we have F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}f^{hom} for f = F^{deh} and some s_{1}, …, s_{m} ∈ ℕ by Proposition 4.2.g. And if F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}f^{hom}, then we clearly have F ∈ I^{hom}.

For the proof of c), we note that the implication “⇐” follows from the fact that (y_{1} ⋯ y_{m})^{s}F ∈ J implies F^{deh} = ((y_{1} ⋯ y_{m})^{s}F)^{deh} ∈ J^{deh}. Conversely, let a homogeneous polynomial F ∈ \overline{P} be given such that F^{deh} ∈ J^{deh}. Since J^{deh} is a homomorphic image of J, there exists a homogeneous polynomial G ∈ J such that G^{deh} = F^{deh}. Thus Proposition 4.2.g yields numbers s_{1}, …, s_{m}, s′_{1}, …, s′_{m} ∈ ℕ such that F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}(F^{deh})^{hom} = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}(G^{deh})^{hom} and G = y_{1}^{s′_{1}} ⋯ y_{m}^{s′_{m}}(G^{deh})^{hom}. Altogether, this shows (y_{1} ⋯ y_{m})^{s}F ∈ (G) ⊆ J for s = max{0, max{s′_{i} − s_{i} | i = 1, …, m}}.

The inclusion J ⊆ (J^{deh})^{hom} in d) follows from Proposition 4.2.g, and (J^{deh})^{hom} ⊆ J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞} is a consequence of c). To prove the remaining containment, we note that J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞} is clearly a homogeneous ideal in \overline{P}. Let a homogeneous polynomial F ∈ J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞} be given. Then there exists an r ≥ 0 such that (y_{1} ⋯ y_{m})^{r}F ∈ J, and therefore F^{deh} ∈ J^{deh}. Using Proposition 4.2.g, we get numbers s_{1}, …, s_{m} ∈ ℕ such that F = y_{1}^{s_{1}} ⋯ y_{m}^{s_{m}}(F^{deh})^{hom} ∈ (J^{deh})^{hom}, and this was to be shown.

To prove e), we suppose that y_{1} ⋯ y_{m} F ∈ I^{hom} for some homogeneous polynomial F ∈ \overline{P}. Part a) implies F^{deh} = (y_{1} ⋯ y_{m}F)^{deh} ∈ (I^{hom})^{deh} = I, and then b) yields F ∈ I^{hom}. Finally, we observe that a homogeneous polynomial in P is its own homogenization because of Proposition 4.2.a. This proves claim f). ⊓ ⊔

These rules for homogenizing ideals have two useful applications.

COROLLARY 4.4. (Characterization of the Multihomogenization) Let I be an ideal in P. For an ideal J in \overline{P}, the following conditions are equivalent.

a) J = I^{hom}

b) The ideal J is homogeneous, has dehomogenization I, and satisfies J = J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞}.

Proof. Since a) implies b) by parts a) and d) of the proposition, it remains to prove the converse. Using the hypothesis and part d) of the proposition, we calculate J = J :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞} = (J^{deh})^{hom} = I^{hom}. ⊓ ⊔

COROLLARY 4.5. (Computation of Multihomogenizations) Let I be an ideal in P which is generated by polynomials f_{1}, …, f_{r} ∈ P. Then the multihomogenization of I can be computed via the formula

I^{hom} = (f_{1}^{hom}, …, f_{r}^{hom}) :_{\overline{P}} (y_{1} ⋯ y_{m})^{∞}

Proof. This follows from part d) of the proposition, since I is the dehomogenization of (f_{1}^{hom}, …, f_{r}^{hom}). ⊓ ⊔

We leave it to the reader to check that multihomogenization and dehomogenization have the standard behaviour under ideal theoretic operations like sums, intersections, and radicals. Our next result describes the connection between the homogenization of an ideal and Macaulay bases. Notice that we have to assume m = 1 for this theorem. In this case it is customary to denote the homogenizing indeterminate by x_{0}.

THEOREM 4.6. (Macaulay Bases and Homogenization) Suppose that P is positively ℤ-graded by W. Let I ⊂ P be a proper ideal of P, and let {f_{1}, …, f_{r}} ⊆ P \ {0} be a system of generators of I. Then the following conditions are equivalent.

a) We have I^{hom} = (f_{1}^{hom}, …, f_{r}^{hom}). b) The set {f_{1}, …, f_{r}} is a Macaulay basis of I with respect to the grading

given by W.

Proof. First we show that a) implies b). Given f ∈ I \ {0}, we use the hypothesis to find a representation f^{hom} = ∑_{i=1}^{r} G_{i}f_{i}^{hom}, where G_{i} is a homogeneous polynomial in \overline{P} of degree deg_{W} (f) − deg_{W} (f_{i}). If we substitute x_{0} ↦ 0 in this equation and use Proposition 4.2, we obtain LF_{W} (f) = ∑_{i=1}^{r} G_{i}(0, x_{1}, …, x_{n}) LF_{W} (f_{i}), as we had to show.

Now we prove that b) implies a). The ideal J = (f_{1}^{hom}, …, f_{r}^{hom}) is a homogeneous ideal in \overline{P} which is contained in I^{hom}. Using induction on d, we shall prove J_{d} = I_{d}^{hom} for all d ≥ 0. For d = 0, we have I_{0}^{hom} = J_{0} = (0), since I ⊂ P means that I contains no non-zero constant polynomial. For d > 0, we let G ∈ I_{d}^{hom}. By Proposition 4.2.g, the polynomial G is of the form G = x_{0}^{s}(G^{deh})^{hom} for some s ≥ 0, and Proposition 4.3.e implies (G^{deh})^{hom} ∈ I_{d−s}^{hom}. Thus the claim follows from the induction hypothesis I_{d−s}^{hom} = J_{d−s} if s > 0. Hence we may assume that s = 0, i.e. that G = (G^{deh})^{hom}.

By assumption and Corollary 1.7.11 of [3], there are homogeneous polynomials g_{1}, …, g_{r} ∈ P of degree deg_{W} (g_{i}) = deg_{W} (G^{deh}) − deg_{W} (f_{i}) such that LF_{W} (G^{deh}) = ∑_{i=1}^{r} g_{i} LF_{W} (f_{i}). Hence the polynomial G^{deh} ∈ P is of the form G^{deh} = ∑_{i=1}^{r} g_{i}f_{i} + h with a polynomial h ∈ P of degree deg_{W} (h) < deg_{W} (G^{deh}) = d. Using Proposition 4.2, we obtain G = (G^{deh})^{hom} = ∑_{i=1}^{r} g_{i}f_{i}^{hom} +x_{0}^{t}H with t > 0 and a homogeneous polynomial H ∈ \overline{P} which is not divisible by x_{0}. Consequently, we have H = (H^{deh})^{hom} and x_{0}^{t}H ∈ I_{d}^{hom}. Therefore Proposition 4.3.e and the induction hypothesis show H ∈ I_{d−t}^{hom} = J_{d−t}. Altogether, we find G ∈ J_{d} as claimed. ⊓ ⊔

This theorem can be used to compute homogenizations in another way if P is positively ℤ-graded.

COROLLARY 4.7. Given an ideal I in P, consider the following sequence of instructions.

1) Choose a non-singular matrix V ∈ Mat_{n}(ℤ) of the form V = \binom{W}{W′}, where W′ ∈ Mat_{n−1,n}(ℤ).

2) Compute a Gröbner basis {g_{1}, …, g_{s}} of I with respect to Ord(V).

3) Return the ideal (g_{1}^{hom}, …, g_{s}^{hom}) and stop. This is an algorithm which computes I^{hom} = (g_{1}^{hom}, …, g_{s}^{hom}).

Proof. It suffices to combine Corollary 3.6 and the theorem. ⊓ ⊔ 5. Multihomogeneous Gröbner Bases

In the sequel let K be a field, let P = K[x_{1}, …, x_{n}] be a polynomial ring over K which is positively graded by a matrix W ∈ Mat_{m,n}(ℤ), let r ≥ 1, let δ_{1}, …, δ_{r} ∈ ℤ^{m}, and let M be a graded submodule of F = ⨁_{i=1}^{r} P (−δ_{i}) which is generated by a set of non-zero homogeneous vectors {v_{1}, …, v_{s}}. Furthermore, we choose a module term ordering σ on the monomodule of terms 𝕋^{n}⟨e_{1}, …, e_{r}⟩ in F, and we let V = (v_{1}, …, v_{s}).

Our goal is to describe an algorithm which computes a homogeneous σ-Gröbner basis of M degree-by-degree and a variant of this algorithm which also yields a minimal system of generators of M contained in V. To ease the notation, we shall use the following convention: whenever a vector g_{i} appears, we write LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}}, where c_{i} ∈ K \ {0}, where t_{i} ∈ 𝕋^{n}, and where γ_{i} ∈ {1, …, r}. For two indices i, j such that γ_{i} = γ_{j}, we let σ_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} e_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} e_{j} and S_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} g_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} g_{j}.

THEOREM 5.1. (The Multihomogeneous Buchberger Algorithm) In the above situation, consider the following instructions.

1) Let B = ∅, W = V, G = ∅, and let s′ = 0.

2) Let d be the smallest degree with respect to Lex of a component of W or an element of {§_{ij} | (i, j) ∈ B}. Form the subtuple W_{d} of elements of degree d in W and the subset B_{d} = {(i, j) ∈ B | deg_{W} (S_{ij}) = d}, and delete their entries from W and B, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, chose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute the S-vector S_{ij} and its normal remainder S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 6).

8) Increase s′ by one, append g_{s′} = v′ to the tuple G, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9) If B = ∅ and W = ∅, return the tuple G and stop. Otherwise, continue with step 2).

This is an algorithm which returns a multihomogeneous σ-Gröbner basis G = (g_{1}, …, g_{s′}) of M, where the elements of G have non-decreasing multidegrees.

Proof. First we prove finiteness. Every time step 3) is executed, we remove an element from the set B_{d}, and every time step 6) is executed, we remove an element from the tuple W_{d}. Thus, for each degree d, the execution of steps 3) to 8) is finite. The tuple W is never enlarged. The set B is enlarged only in steps 5) and 8). When this happens, an element g_{s′} is appended to G which has a leading term outside ⟨LT_{σ}(g_{1}), …, LT_{σ}(g_{s′−1})⟩. Since every ascending chain of monomial submodules of F becomes eventually stationary, steps 5) and 8) can be executed only finitely many times. Thus we arrive eventually at a point where W = ∅ and B = ∅, and the procedure terminates by step 9).

Now we show that the algorithm returns a homogeneous σ-Gröbner basis of M. For every new element g_{s′} which is added to G, all pairs {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} are added to B in steps 5) and 8). Hence all pairs {(i, j) | 1 ≤ i < j ≤ s′, γ_{i} = γ_{j}} are added to B at some point during the execution of the algorithm. Notice that a pair (i, j) which is added to B in step 5) or in step 8) has a degree d′ greater than d, and is therefore put into the list B_{d′} at a later stage. Every time a pair (i, j) is deleted in step 3), steps 4) and 5) guarantee that the corresponding syzygy σ_{ij} has a lifting in Syz(G). Therefore G is a σ-Gröbner basis of ⟨g_{1}, …, g_{s′}⟩ by Buchberger’s criterion. Since all generators {v_{1}, …, v_{s}} of M are eventually treated by steps 6), 7), and 8), we have M = ⟨g_{1}, …, g_{s′}⟩ when the algorithm stops.

Moreover, the elements S′_{ij} or v′ are normal remainders of homogeneous elements with respect to reduction by a list of homogeneous vectors. Thus it follows by induction on s′ that G continues to consist of homogeneous vectors throughout. Finally, the fact that the multidegrees of the elements of G are ordered non-decreasingly follows from the choice of the next degree d in step 9), because an element g_{s′} which is appended to G in step 5) or 8) has the current degree d. ⊓ ⊔

Let us add some observations about this algorithm.

REMARK 5.2. If we interrupt the execution of the Multihomogeneous Buchberger Algorithm after some degree d_{0} is finished, the tuple G contains a d_{0}-truncated Gröbner basis of M. Consequently, we can compute truncated Gröbner bases efficiently.

Moreover, in this case it suffices to append only the pairs {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}, deg_{W} (S_{is′}) ≤_{Lex} d_{0}} to the set B in steps 5) and 8). The reason is that pairs of higher degree are never processed anyway, since we stop the computation after finishing degree d_{0}.

REMARK 5.3. In the theorem, it is not required that σ is a degree compatible module term ordering. The reason is that, during the computation of the Gröbner basis, only comparisons of terms in the support of a homogeneous vector are performed. Thus these terms have the same degree, and it does not matter whether σ is degree compatible or not.

REMARK 5.4. When we compute a normal remainder in step 4) or step 7) of the Multihomogeneous Buchberger Algorithm, we can improve the performance of the Division Algorithm by noting that we have only to consider reductors whose multidegree is componentwise less than or equal to the multidegree of the given element.

The reason for introducing the two loops in steps 3)–5) and steps 6)–8) in the algorithm of the theorem is the following variant which computes a minimal system of generators of M while computing a multihomogeneous Gröbner basis. The proof of the next corollary requires some more sophisticated techniques and will be contained in [4].

COROLLARY 5.5. In the situation of the theorem, we replace steps 1), 8), and 9) by the following instructions. 1’) Let B = ∅, W = V, G = ∅, let s′ = 0, and let H = ∅.

8’) Increase s′ by one, append g_{s′} = v′ to the tuple G and to the tuple H, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9’) If B = ∅ and W = ∅, return the pair (G, H) and stop. Otherwise,

continue with step 2). Then the resulting set of instructions defines an algorithm. It returns a pair (G, H) such that G is a homogeneous σ-Gröbner basis of M and H is a subtuple of G which minimally generates M.

6. Conclusions

In this paper, we have provided some basic tools for computing in modules over polynomial rings in a multigraded setting. We have identified two types of multigradings, namely weakly positive and positive multigradings, which allow us to have a graded version of Nakayama’s lemma, Hilbert functions, good Macaulay bases, and a multigraded Buchberger algorithm. Furthermore, we have generalized the process of homogenizing and dehomogenizing polynomials and ideals to the multigraded situation and we have proven the rules governing those operations. Macaulay bases, the analogue of Gröbner bases in the multigraded case, can sometimes be used to compute those multihomogenizations. We also exhibited a multihomogeneous version of the Buchberger algorithm.

Based on this work, it is possible to develop algorithms for computing multigraded minimal free resolutions, multigraded Hilbert functions, and multigraded Hilbert series. Moreover, those algorithms can then be used to speed up Gröbner basis and related computations in the multihomogeneous case (see for instance [1]). Further developments in this direction will be contained in [2] and [4].

Acknowledgements

The stimulating and friendly atmosphere at the Sinaia NATO workshop provided us with an excellent opportunity to continue the work started with this paper. We are very grateful to the organizers for the superb job they have done. Moreover, the first author acknowledges the hospitality an support of the CoCoA project and of Genova University during the preparatory phases of this work. This project was supported by CNR.

References

1. Caboara, M., De Dominicis, G., and Robbiano, L., Multigraded Hilbert functions and Buchberger algorithm, in: Lakshman, Y.N. (ed.), Proceedings of ISSAC ’96, ACM, New York 1996, pp. 72–78.

2. Caboara, M., Kreuzer, M., and Robbiano, L., Minimal sets of critical pairs, preprint 2002.

3. Kreuzer, M. and Robbiano, L., Computational Commutative Algebra 1, Springer, Heidelberg 2000.

4. Kreuzer, M. and Robbiano, L., Computational Commutative Algebra 2, Springer, Heidelberg (in preparation).