How to Compute the Canonical Module of a Set of Points

by Stefan Beck and Martin Kreuzer

Contents.

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Filtered Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Some Useful Computer Algebra Techniques . . . . . . . . . . . . . . . . 7 4. A Gröbner Basis of the Canonical Module . . . . . . . . . . . . . . . . 11 5. A Gröbner Basis of the Syzygy Module . . . . . . . . . . . . . . . . . 14 6. A Presentation of the Canonical Module . . . . . . . . . . . . . . . . . 17 7. Application to Minimal Resolutions . . . . . . . . . . . . . . . . . . . 19 8. Application to Checking Uniformity Conditions . . . . . . . . . . . . . . 25

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Abstract. For a set of reduced points 𝕏 ⊆ ℙ_{K}^{n}, we describe an efficient algorithm to compute a minimal graded presentation of the canonical module of the homogeneous coordinate ring of 𝕏. Applications are given for computing minimal graded free resolutions of points with generic Hilbert function, and for checking uniformity conditions such as the Cayley-Bacharach property and the uniform position property.

AMS Classification. Primary 13 P 99, secondary 14 Q 99, 13 C 05, 14 N 05.

Keywords. Canonical module, set of points, 0-dimensional scheme, Gröbner basis, minimal free resolution, uniform position property.

1. Introduction

Suppose K is a computable field and 𝕏 ⊆ ℙ_{K}^{n} is a set of points (i.e. a 0-dimensional, reduced subscheme with K-rational support) given by their coordinates. The first object of interest in this situation is, of course, the homogeneous vanishing ideal I_{𝕏} ⊆ K[X_{0}, …, X_{n}] of 𝕏. A naïve and inefficient approach to find this ideal would be to form the homogeneous prime ideals of height n corresponding to those points and to compute their intersection. It has been shown to be much faster, and in fact of polynomial complexity in n and the number of points, to use the Buchberger-Möller algorithm for this task (cf. [MMM]). Based on the results of this algorithm, many elementary properties of 𝕏 and its homogeneous coordinate ring R like its Hilbert function, Cohen-Macaulay type, a minimal system of generators of I_{𝕏}, the separators (cf. [GKR], sect. 2), etc. can be easily computed.

What is the canonical module?

In this paper we want to deal computationally with deeper geometric properties of 𝕏 resp. algebraic properties of R. Our main object of interest is the canonical module of R. This finitely generated, graded R-module historically was first introduced in Duality Theory via

ω_{R} ≅ \underline{Hom}_{K}(H_{𝔪}^{1}(R), K).

Here 𝔪 = ⊕_{i>0}R_{i} is the homogeneous maximal ideal of R and \underline{Hom} means “graded homomorphisms”, i.e. finite sums of homogeneous linear maps. The module ω_{R} plays a key rôle in this theory because of the

Graded Duality Theorem. (cf. [GW], 2.1.6) For every finitely generated, graded R-module M there is an isomorphism

\underline{Hom}_{R}(M, ω_{R}) ≅ \underline{Hom}_{K}(H_{𝔪}^{1}(M), K)

of graded R-modules which is functorial in M.

Why are we interested in the canonical module?

Later it was realized that the multiplicative structure of this module carries a large amount of information about the geometry of the points of 𝕏 (cf. [GKR], [K1], [K2]). In particular, it is possible to characterize the Cayley-Bacharach property, various uniformity conditions, linearly and higher order general position properties solely in terms of the structure of the multiplication maps from one homogeneous component of ω_{R} to another.

Thirdly, considering the Adjunction Formula

ω_{R} ≅ \underline{Ext}_{K[X_{0},...,X_{n}]}^{n}(R, K[X_{0}, …, X_{n}])(−n − 1)

it is clear that knowing ω_{R} may be useful for computing the minimal graded free P := K[X_{0}, …, X_{n}]-resolution of R. Some hints in this direction were already given in [K1], sect. 5, but let us be more precise. If

0 ⟶ ⨁_{i=1}^{β_{n}} P (−α_{ni}) ⟶^{Φ_{n}} ⋯ ⟶ ⨁_{i=1}^{β_{1}} P (−α_{1i}) ⟶^{Φ_{1}} P ⟶ R ⟶ 0

is the minimal graded free P -resolution of R, then

0 → P (−n − 1) ⟶^{Φ_{1}} ˇ ⨁_{i=1}^{β_{1}} P (α_{1i} − n − 1) ⟶ ⋯ ⟶^{Φ_{n}} ˇ ⨁_{i=1}^{β_{n}} P (α_{ni} − n − 1) → ω_{R} → 0

is the minimal graded free P -resolution of ω_{R}, since R is a Cohen-Macaulay ring and ω_{R} is given by the adjunction formula (cf. sect. 7). Thus the resolution of ω_{R} is dual to the resolution of R. Now, often it happens that the Betti numbers β_{i} or the shifts α_{ij} we are interested in are the ones near the end of the resolution of R. Clearly, if we know a minimal graded presentation of ω_{R} and start resolving it, we can find those numbers much more easily.

A case in point is the situation when 𝕏 has generic Hilbert function, e.g. if the points of 𝕏 are chosen randomly. In section 7 we shall demonstrate that it suffices in this case to compute either the linear part of the resolution of R or of ω_{R}, in order to get all numbers α_{ij}, β_{i}. Consequently, we are able to compute those numbers very efficiently, and we apply our results to solve the Minimal Resolution Conjecture computationally in many cases.

How can we calculate a minimal graded presentation of ω_{R}?

This is the main topic of the present paper. We want to give a solution in the spirit of the Buchberger-Möller algorithm, i.e. avoiding the potentially expensive calculation of Gröbner bases via Buchberger’s algorithm. In view of this strategy, the naïve method of using the description of ω_{R} given by the Adjunction Formula is totally out of the question: computing the whole resolution of R requires computing n Gröbner bases of its syzygy modules, the sizes of the middle ones of which are known to be large because of the exponential growth of the Betti numbers.

A much better idea is to change coordinates such that 𝕏 ⊆ D_{+}(X_{0}) = ℙ_{K}^{n} \ 𝒱(X_{0}) and to use the description of the canonical module

ω_{R} ≅ \underline{Hom}_{K[x_{0}]}(R, K[x_{0}])(−1)

derived from the Noetherian Normalization K[x_{0}] ⊆ R. Here x_{0}, the image of X_{0} in R, is a linear nonzerodivisor. The elements of ω_{R} are then viewed as K[x_{0}]-linear maps φ : R ⟶ K[x_{0}], and its R-module structure is given by (rφ)(r′) = φ(rr′) for r, r′ ∈ R.

Now we give a more detailed outline of the contents of the individual sections. In section 2 we introduce a generalization of the usual theory of graded and filtered rings and modules. We allow rings with filtrations indexed by abelian groups and modules with filtrations indexed by sets on which those abelian groups operate suitably. This allows us to treat the cases of filtrations of free modules (cf. Example 2.6) and dual modules (cf. Example 2.7) simultaneously. Then, in section 3, we review and adapt some standard computer algebra techniques which are useful for our purposes. In particular, we recall how one can deal computationally with 0-dimensional subschemes of ℙ_{K}^{n}, and we provide some reduction techniques for syzygies (cf. Propositions 3.7 and 3.8).

Sections 4 to 6 form the central part of this paper and contain the main algorithm. In section 4 we start by describing a Gröbner basis of ω_{R} w.r.t. a suitable filtration. The idea for constructing it comes from looking at the order ideal 𝒪_{σ}(J_{𝕏}) of the affine ideal J_{𝕏} of 𝕏 ⊆ D_{+}(X_{0}): each monomial there has a multiple which is a socle monomial, i.e. all of whose multiples are outside 𝒪_{σ}(J_{𝕏}). In the language of projections R ⟶ K[x_{0}] to those monomials this says that the projections to socle monomials generate ω_{R} as an R-module. In fact, if we filter ω_{R} suitably, those projections actually form a minimal Gröbner basis.

Thus we proceed by studying the module of syzygies of those projections. Again, by looking at the above order ideal, we see that one has to consider two kinds of syzygies (cf. Propositions 5.1 and 5.2), and we construct from them a Gröbner basis of the syzygy module of all projections (cf. Proposition 5.3). Then we reduce those syzygies to a Gröbner basis of the syzygy module of the minimal Gröbner basis found before (cf. Proposition 5.4). Finally, we apply in section 6 several minimalization steps to get the desired minimal graded presentation of ω_{R}.

The paper concludes with two sections about applications of the canonical module. First, in section 7, we explain in detail how one can use ω_{R} to speed up the computation of minimal graded free resolutions of points with generic Hilbert function. In particular, this method is applied to produce proofs or counterexamples to the Minimal Resolution Conjecture for numerous cases with small n and moderate numbers of points.

In the last section, we give some applications to checking higher uniformities. For small uniformities, we can give a fast direct method (cf. Remark 8.2), whereas for high uniformities we can apply our knowledge of ω_{R} to reduce the problem to checking biinjectivity of certain explicitly computable bilinear maps of finite dimensional Kvector spaces. For that problem we offer two approaches (cf. Remarks 8.3 and 8.4), both of which, however, require standard Gröbner basis computations.

Acknowledgements. The authors are indebted to E. Kunz (Regensburg) for his continuing interest in this project, and for the opportunity to lecture about it in his seminar. They would also like to thank T. Mora (Genova), L. Robbiano (Genova), and F. Schreyer (Bayreuth) for stimulating discussions about the subject. Last but not least, thanks to the organizers of the conference “MEGA 94” (Santander / Spain) for enabling the second author to present this work to a wider audience.

Implementation. The algorithms described in this paper have been implemented by the first author using C ++ in a program called “COP” (Computation Of Points). This program runs on PC’s and Unix platforms equipped with the GNU compiler, and is available from the authors upon request.

2. Filtered Modules

For our purposes, it will prove useful to introduce the following generalization of the usual theory of graded and filtered rings and modules (cf. [R1], [PS]). We start with an abelian group (G, +) which operates additively on a set H.

Definition 2.1. A G-grading on a ring R is a set of additive subgroups R_{g} ⊆ R for g ∈ G such that R = ⊕_{g∈G}R_{g} and R_{g} · R_{g′} ⊆ R_{g+g′} for g, g′ ∈ G. An H-grading on an R-module M is a set of R-submodules M_{h} ⊆ M for h ∈ H such that M = ⊕_{h∈H}M_{h} and R_{g} · M_{h} ⊆ M_{g+h} for g ∈ G, h ∈ H.

Example 2.2. If R is a G-graded ring, g ∈ G, and M an H-graded R-module, then M(g) is the H-graded R-module such that M(g)_{h} = M_{g+h}. We call M(g) the shift of M by g.

Now let (G, <_{σ}) and (H, <_{τ}) be totally ordered, and assume that the operation + : G×H ⟶ H is compatible with those orderings, i.e. h <_{τ} h′ implies g +h <_{τ} g +h′ and g <_{σ} g′ implies g + h <_{τ} g′ + h for g, g′ ∈ G and h, h′ ∈ H.

Definition 2.3. An (ascending, exhaustive) G-filtration 𝒢 of an R-algebra S is a set of R-submodules 𝒢_{g} ⊆ S for g ∈ G such that

a) 𝒢_{g} ⊆ 𝒢_{g′} for g, g′ ∈ G with g <_{σ} g′,

b) 𝒢_{g} · 𝒢_{g′} ⊆ 𝒢_{g+g′} for g, g′ ∈ G,

c) 1 ∈ 𝒢_{0},

d) ∪_{g∈G}𝒢_{g} = S.

If (S/R, 𝒢) is a G-filtered algebra and M an S-module, then an (ascending, exhaustive) H-filtration ℋ of M is a set of R-submodules ℋ_{h} ⊆ M for h ∈ H such that

a) ℋ_{h} ⊆ ℋ_{h′} for h, h′ ∈ H such that h <_{τ} h′,

b) 𝒢_{g} · ℋ_{h} ⊆ ℋ_{g+h} for g ∈ G, h ∈ H,

c) ∪_{h∈H}ℋ_{h} = M.

In the sequel, we let (S/R, 𝒢) be a G-filtered algebra and (M, ℋ) an H-filtered S-module. As usual, letting ℋ_{h}^{<} = ∪_{h′<h}ℋ_{h′} and (gr_{ℋ} M)_{h} = ℋ_{h}/ℋ_{h}^{<} for h ∈ H, we obtain an R-module gr_{ℋ} M = ⊕_{h∈H}(gr_{ℋ} M)_{h} which we call the associated graded module of (M, ℋ). By (s + 𝒢_{g}^{<}) · (m + ℋ_{h}^{<}) := sm + ℋ_{g+h}^{<} for g ∈ G, h ∈ H, s ∈ 𝒢_{g}, m ∈ ℋ_{h}, it has the structure of an H-graded module over the associated G-graded ring gr_{𝒢} S = ⊕_{g∈G}𝒢_{g}/𝒢_{g}^{<} of (S/R, 𝒢).

Definition 2.4. (cf. [PS], 2.19 and 4.1) The H-filtration ℋ of M is called valued, if for any m ∈ M \ {0} the order ord_{ℋ} m = min{h ∈ H | m ∈ ℋ_{h}} exists. Furthermore, ℋ is called a Gröbner filtration, if it is valued and the set {ord_{ℋ} m | m ∈ M \ {0}} is well-ordered w.r.t. <_{τ}.

From now on, all filtrations will be assumed to be Gröbner filtrations. For m ∈ M \ {0}, the element L_{ℋ} m = m + ℋ_{ord_{ℋ} m}^{<} ∈ gr_{ℋ} M is called the leading form of m. If m = 0, we let L_{ℋ} m := 0. Note that, with M, also every S-submodule N ⊆ M resp. every quotient module M/N is canonically H-filtered via {N ∩ ℋ_{h}}_{h∈H} resp. {ℋ_{h}/(N ∩ℋ_{h})}_{h∈H}. The following proposition collects some basic properties of Gröbner filtrations. Its proof is completely analogous to the classical case (cf. [R1], sect. 3 and [PS], sect. 4) and will be omitted.

Proposition 2.5. Let (M, ℋ) be an H-filtered S-module and N ⊆ M an S-submodule. a) The induced filtrations on N and M/N are Gröbner filtrations again.

b) If gr_{ℋ} N = ∑_{i=1}^{r} gr_{𝒢} S · L_{ℋ} m_{i} for some elements m_{1}, …, m_{r} ∈ N, then N = ∑_{i=1}^{r} Sm_{i}. In this case, {m_{1}, …, m_{r}} is called a Gröbner basis of N.

c) A set {m_{1}, …, m_{r}} is a Gröbner basis of N if and only if every element n ∈ N \{0} has a representation n = ∑_{i=1}^{r} s_{i}m_{i} with s_{i} ∈ S and ord_{𝒢} s_{i}+ord_{ℋ} m_{i} ≤ ord_{ℋ} n whenever s_{i} ≠ 0.

Example 2.6. (Canonical filtration of a free module)

For a G-filtered algebra (S/R, 𝒢), we want to define an H-filtration ℋ of M = S^{r} with r ≥ 1 such that H = G × {1, …, r}, and the standard basis vectors e_{1}, …, e_{r} satisfy ord_{ℋ} e_{i} = (a_{i}, i) with preassigned weights a_{i} ∈ G. We start by defining an operation of G on H by g + (g′, i) := (g + g′, i) and a total ordering <_{τ} on H by

(g, i) <_{τ} (g′, j) :⇔ \{ \begin{matrix}g − a_{i} <_{σ} g′ − a_{j} & or \\ g − a_{i} = g′ − a_{j} & and i < j \end{matrix}

for g, g′ ∈ G, i, j ∈ {1, …, r}. Then we let ℋ = {ℋ_{h}}_{h∈H} with ℋ_{(g,i)} being the R-sub-module of S^{r} generated by all elements of the form se_{j} with s ∈ S and (ord_{𝒢} s+a_{j}, j) <_{τ} (g, i). It is easy to check that (S^{r}, ℋ) is an H-filtered S-module, ℋ is a Gröbner filtration, and we have a canonical isomorphism of H-graded gr_{𝒢} S-modules

gr_{ℋ} S^{r} ⟶ ⨁_{i=1}^{r}(gr_{𝒢} S)(−a_{i})

which maps L_{ℋ} e_{i} to the i^{th} standard basis vector of the right-hand side.

Example 2.7. (Canonical filtration of the dual module)

For a G-filtered algebra (S/R, 𝒢), the dual module Hom_{R}(S, R) carries a natural S-module structure via s·φ : S ⟶ R (s′ ↦ φ(ss′)). Suppose {− ord_{𝒢} s | s ∈ S \{0}} is well-ordered and 𝒢_{g} is a direct R-summand of S for each g ∈ G. We define a G-filtration ℋ = {ℋ_{g}}_{g∈G} on Hom_{R}(S, R) by setting ℋ_{g} := {φ ∈ Hom_{R}(S, R) | φ(𝒢_{−g}^{<}) = 0} for g ∈ G. It is easy to check that this makes (Hom_{R}(S, R), ℋ) a G-filtered S-module, ℋ is a Gröbner filtration, and we have a canonical isomorphism of G-graded gr_{𝒢} S-modules

gr_{ℋ} Hom_{R}(S, R) ⟶  Hom_{R}(gr_{𝒢} S, R)
L_{ℋ} φ  ⟼ (L_{𝒢} s ↦ \{ \begin{matrix}φ(s) & if ord_{𝒢} s = − ord_{ℋ} φ, \\ 0 & otherwise. \end{matrix} )

3. Some Useful Computer Algebra Techniques

Later in this paper we want to calculate a minimal homogeneous presentation of a certain graded module over an explicitly given standard graded algebra. For this we review concrete methods to deal computationally with the material explained in the previous section. The techniques presented subsequently are elaborated from the introductory papers [R2] and [MR].

Let us start with the simplest algebraic objects available for computer manipulation, namely terms (sometimes also called monomials), i.e. objects of the form X^{ν} := X_{1}^{ν_{1}} ⋯ X_{n}^{ν_{n}} with variables X_{1}, …, X_{n}, an exponent ν = (ν_{1}, …, ν_{n}) ∈ ℕ^{n}, and n ≥ 1. The set of all terms is denoted by 𝒯^{n}. A subset ℳ ⊆ 𝒯^{n} is called a monoideal, if t ∈ ℳ implies tt′ ∈ ℳ for all t′ ∈ 𝒯^{n}. A subset 𝒪 ⊆ 𝒯^{n} is called an order ideal, if t ∈ 𝒪 implies t′ ∈ 𝒪 for all t′ ∈ 𝒯^{n} dividing t. Clearly, if ℳ ⊆ 𝒯^{n} is a monoideal, then 𝒪 = 𝒯^{n} \ ℳ is an order ideal, and vice versa. The set ℬ := {t ∈ M | t = X_{i}t′ for some t′ ∈ 𝒪, i ∈ {1, …, n}} is called the border of ℳ. Obviously 𝒪 ∪ ℬ is an order ideal, too. A subset ℳ′ ⊆ ℳ is called a system of generators of ℳ, if any term in ℳ is a multiple of some term in ℳ′. The following proposition helps us to compute a minimal system of generators of ℳ (cf. [R2], sect. 3).

Proposition 3.1. Every monoideal ℳ ⊆ 𝒯^{n} has a unique, finite, minimal system of generators, namely ℳ_{0} = {t ∈ ℳ | t/X_{i} ∉ ℳ for all i such that X_{i} | t}.

A term ordering <_{σ} on 𝒯^{n} is a total ordering such that t <_{σ} t′ implies st <_{σ} st′ for all s, t, t′ ∈ 𝒯^{n}, and such that 1 <_{σ} t for all t ∈ 𝒯^{n} \ {1}. By looking at the exponents only, we can regard <_{σ} as an ordering on ℕ^{n}. Then we can extend <_{σ} uniquely to ℤ^{n} by defining ν <_{σ} μ for ν, μ ∈ ℤ^{n} if and only if ν = ν′ − ν′′, μ = μ′ − μ′′ with ν′, ν′′, μ′, μ′′ ∈ ℕ^{n}, and ν′ + μ′′ <_{σ} μ′ + ν′′.

Now we extend those methods to deal with arbitrary polynomials. From now on, we will always work over a computable base field K. We let A = K[X_{1}, …, X_{n}] be the polynomial ring, and <_{σ} a term ordering on 𝒯^{n}.

Definition 3.2. The ℤ^{n}-filtration ℱ^{σ} = {ℱ_{ν}^{σ}}_{ν∈ℤ^{n}} given by

ℱ_{ν}^{σ} = \{ \begin{matrix}⟨\{t ∈ 𝒯^{n} | t ≤_{σ} X^{ν}\}⟩_{K} & if ν ∈ ℕ^{n}, \\ 0 & otherwise, \end{matrix}

is called the term filtration of A associated with <_{σ}.

It is easy to verify that ℱ^{σ} is in fact a Gröbner filtration of A (cf. [R2], 3.5). The associated graded ring gr_{ℱ^{σ}} A is nothing but A, together with its canonical ℤ^{n}- grading. Every polynomial f ∈ A \ {0} has a unique representation f = ∑_{i=1}^{r} c_{i}t_{i} with c_{i} ∈ K \ {0}, t_{i} ∈ 𝒯^{n}, and t_{1} >_{σ} ⋯ >_{σ} t_{r}. We call lt_{σ}(f) := t_{1} the leading term of f and lc_{σ}(f) := c_{1} the leading coefficient of f.

Next we extend our methods again and deal with ideals and residue class rings of A. For an ideal I ⊆ A, we call lt_{σ}(I) := (lt_{σ}(f))_{f∈I} the ideal of leading terms of I. Clearly, this is a monoideal in 𝒯^{n}. Its associated order ideal 𝒯^{n} \ lt_{σ}(I) will be denoted by 𝒪_{σ}(I). This order ideal contains information about the arithmetic of A/I (cf. [R2], sect. 8).

Proposition 3.3. Let I ⊆ A be an ideal. Then every polynomial f ∈ A has a unique decomposition f = g + h such that g ∈ I and h ∈ ⟨𝒪_{σ}(I)⟩_{K}. In particular, we have isomorphisms of K-vector spaces A ≅ I ⊕ ⟨𝒪_{σ}(I)⟩_{K} and A/I ≅ ⟨𝒪_{σ}(I)⟩_{K}.

For a decomposition f = g + h as above, we call can(f, I) := h the normal form of f w.r.t. I and <_{σ}. Our goal now is to show how to compute can(f, I) and thus compute in A/I. Recall that, with A, also I is ℤ^{n}-filtered by {I ∩ ℱ_{ν}^{σ}}_{ν∈ℤ^{n}}. From Proposition 2.5 we obtain the following characterization of Gröbner bases.

Proposition 3.4. For an ideal I ⊆ A and {f_{1}, …, f_{r}} ⊆ I \ {0}, the following conditions are equivalent.

a) The set {f_{1}, …, f_{r}} is a Gröbner basis of I, i.e. gr_{ℱ^{σ}} I = (L_{ℱ^{σ}} f_{1}, …, L_{ℱ^{σ}} f_{r}).

b) The monoideal lt_{σ}(I) is generated by {lt_{σ}(f_{1}), …, lt_{σ}(f_{r})}.

c) Every f ∈ I has a representation f = ∑_{i=1}^{r} g_{i}f_{i} such that g_{i} ∈ A, and such that lt_{σ}(g_{i}) lt_{σ}(f_{i}) ≤_{σ} lt_{σ}(f) whenever g_{i} ≠ 0.

Suppose we are given a Gröbner basis {f_{1}, …, f_{r}} of I w.r.t. <_{σ}. Then can(f, I) can be computed for any f ∈ A by the division algorithm (cf. [R2], sect. 4 and [MR], sect. 1.1). From that Gröbner basis we also get a minimal system of generators {t_{1}, …, t_{s}} of lt_{σ}(I) by applying Proposition 3.1. Now Proposition 3.4 yields the following situation.

Corollary 3.5. a) The set {t_{1} − can(t_{1}, I), …, t_{s} − can(t_{s}, I)} is a Gröbner basis of I. It is uniquely determined by I and <_{σ} and is called the reduced Gröber basis of I w.r.t. <_{σ}.

b) For i = 1, …, s, the leading term of t_{i} − can(t_{i}, I) w.r.t. <_{σ} is t_{i} ∈ lt_{σ}(I), and all other terms appearing in this polynomial are from 𝒪_{σ}(I).

Thus we are able to compute in the coordinate ring of a closed subscheme of 𝔸_{K}^{n}, if we are given a Gröbner basis of its vanishing ideal. Most of the time, however, we are interested in closed subschemes of the projective space ℙ_{K}^{n} and their homogeneous coordinate rings. Hence we have to extend our methods once again.

The homogeneous coordinate ring of ℙ_{K}^{n} itself is P := K[X_{0}, …, X_{n}]. For t = X^{ν} = X_{1}^{ν_{1}} ⋯ X_{n}^{ν_{n}} ∈ 𝒯^{n}, we call deg t := ν_{1} + ⋯ + ν_{n} the degree of t. If f ∈ A \ {0} is in its standard form f = ∑_{i=1}^{r} c_{i}t_{i} with c_{i} ∈ K \ {0}, t_{i} ∈ 𝒯^{n}, and t_{1} >_{σ} ⋯ >_{σ} t_{r}, then deg f := max_{i=1..r}{deg t_{i}} is called the degree of f, and^{h}f := ∑_{i=1}^{r} c_{i}t_{i}X_{0}^{deg f−deg t_{i}} ∈ P is called the homogenization of f. For an ideal I ⊆ A, its homogenization ^{h}I is defined by ^{h}I := (^{h}f)_{f∈I} ⊆ P. Here we let ^{h}0 := 0.

Conversely, if we start with a homogeneous polynomial g ∈ P and an ideal J ⊆ P, we have their dehomogenizations ^{a}g := g(1, X_{1}, …, X_{n}) ∈ A and ^{a}J := (^{a}g)_{g∈J} ⊆ A. The processes of homogenization and dehomogenization are almost inverses of each other, in the sense that ^{a}(^{h}f) = f for f ∈ A and X_{0}^{ϵ} ·^{h}(^{a}g) = g for g ∈ P homogeneous and ϵ = max{i ∈ ℕ | X_{0}^{i} divides g}.

A similar procedure can be applied to term orderings <_{σ} of 𝒯^{n}. We extend <_{σ} to an ordering on 𝒯^{n+1} = {X_{0}^{ν_{0}}X^{ν} | (ν_{0}, ν) ∈ ℕ^{n+1}} by defining

X_{0}^{i}X^{ν} <_{τ} X_{0}^{j}X^{μ} ⇔ \{ \begin{matrix}ν <_{σ} μ & or \\ ν = μ & and i < j. \end{matrix}

We call <_{τ} the projective extension of <_{σ}. Clearly, <_{τ} is again a term ordering, and its associated term filtration ℱ^{τ} is a ℤ^{n+1}-filtration of the K-algebra P. The basic properties of the described processes are summarized by the following proposition (cf. [MR], sect. 1.1).

Proposition 3.6. Suppose <_{σ} is a degree-compatible term ordering on 𝒯^{n}, i.e. all t, t′ ∈ 𝒯^{n} with deg t < deg t′ satisfy t <_{σ} t′. Let <_{τ} be the projective extension of <_{σ}, let I ⊆ A be an ideal, and let {f_{1}, …, f_{r}} be a Gröbner basis of I w.r.t. <_{σ}.

a) For all f ∈ A we have lt_{σ}(f) = lt_{τ} (^{h}f).

b) The set {^{h}f_{1}, …,^{h}f_{r}} is a Gröbner basis of ^{h}I w.r.t. <_{τ}.
c) We have 𝒪_{τ} (^{h}I) = ∪_{i≥0}X_{0}^{i} · 𝒪_{σ}(I).

d) For g ∈ P, we have can(g,^{h}I) = X_{0}^{deg g−deg^{a}g} · ^{h} can(^{a}g, I). In particular, if f ∈ A is homogeneous, then can(f,^{h}I) = ^{h} can(f, I).

e) If {f_{1}, …, f_{r}} is the reduced Gröbner basis of I w.r.t. <_{σ}, then {^{h}f_{1}, …,^{h}f_{r}} is the reduced Gröbner basis of ^{h}I w.r.t. <_{τ}.

Consequently, given a closed subscheme 𝕏 ⊆ ℙ_{K}^{n} and a Gröbner basis of the vanishing ideal I of 𝕏 ∩ D_{+}(X_{0}) in D_{+}(X_{0}) ≅ 𝔸_{K}^{n} with respect to a degree-compatible term ordering, we can effectively compute in the homogeneous coordinate ring R = P/^{h}I of 𝕏 in ℙ_{K}^{n}. In the present paper, this will be applied to compute in the homogeneous coordinate ring of a set of points, i.e. a reduced 0-dimensional subscheme of ℙ_{K}^{n} consisting of K-rational points, which we can (and shall) assume to be entirely contained in D_{+}(X_{0}). In this case, the Buchberger - Möller algorithm (cf. [BM] and [MR], sect. 1.2) allows us to compute the desired Gröbner basis in a very efficient and fast way. As a by-product, we are also given the order ideal 𝒪_{σ}(I) of 𝕏 in 𝔸_{K}^{n}.

Finally, for one last time, we have to extend the scope of our methods in order to be able to deal with a finitely generated, graded module M over R = P/J, where J is a homogeneous ideal of P. Consider M as a graded P -module, and let M be given via a homogeneous presentation

P^{q} ⟶^{δ} P^{r} ⟶^{ϵ} M ⟶ 0,

i.e. if we let m_{i} := ϵ(ẽ_{i}) and s_{j} = (s_{j1}, …, s_{jr}) := δ(e_{j}) for i = 1, …, r and j = 1, …, q, then {m_{1}, …, m_{r}} is a homogeneous system of generators of M, and the matrix of δ is the transpose of the matrix 𝔐 whose rows are the syzygies s_{1}, …, s_{q}.

Recalling that for any term filtration ℱ^{τ} of P, we have canonical Gröbner filtrations of P^{r} (cf. Example 2.6) and M (cf. Proposition 2.5.a), it is clear what the notions leading term, Gröbner basis, etc. mean in this context. It is also clear, how one can adapt the previously explained material to effectively compute in M, if one is given a Gröbner basis of the syzygy module ker ϵ. We conclude by showing how one can extract a minimal homogeneous system of generators of M from the given one, and how one can compute its module of syzygies. The first step is an extension of the case of ideals (cf. [MMM] and [MR], sect. 2.1), and follows easily from the graded version of Nakayama’s Lemma.

Proposition 3.7. Let \overline{𝔐} = (s̄_{ij}) be the matrix of constants s̄_{ij} = s_{ij}(0, …, 0) of 𝔐. Let u be the rank of \overline{𝔐}, and let \{j_{1}, …, j_{u}\} be the numbers of the columns involved in some nonzero maximal minor of \overline{𝔐}. Then Γ := \{m_{j} | j ∈ \{1, …, r\} \ \{j_{1}, …, j_{u}\}\} is a minimal homogeneous system of generators of M.

Now we permute the columns of 𝔐 (i.e. the copies of P in P^{r}) such that j_{1} = 1, …, j_{u} = u. We also permute the rows of 𝔐 (i.e. the copies of P in P^{q}) such that the rows involved in our maximal minor of \overline{𝔐} have numbers \{1, …, u\}. By applying suitable Klinear operations on those rows, we can assume that (s̄_{ij})_{i,j=1..u} is the identity matrix. Since 𝔐 is homogeneous, then even s_{ii} = 1 for i = 1, …, u. Next we use Gaußian elimination to annihilate every entry in 𝔐 below this partial diagonal by homogeneous P -linear row operations. Notice that the entries s_{11} = ⋯ = s_{uu} = 1 do not change, since all operations are homogeneous and all elements above this partial diagonal have constant term zero. We end up with a matrix 𝔑 of the form

𝔑 = [ \begin{matrix}1 & & ∗ \\ & ... & & ∗ \\ 0 & & 1 \\ & & & s′_{1} \\ & 0 & & ⋮ \\ & & & s′_{p} \end{matrix} ]

where p = q − u and s′_{1}, …, s′_{p} ∈ P^{r−u}. Obviously 𝔑 has same row space as 𝔐. The elementary proof of our last result in this section is left to the reader.

Proposition 3.8. Using the above notations, the elements s′_{1}, …, s′_{p} form a homogeneous system of generators of the module of syzygies of Γ. If {s_{1}, …, s_{q}} is a minimal system of generators of ker ϵ, then {s′_{1}, …, s′_{p}} is also minimal.

4. A Gröbner Basis of the Canonical Module

For the remainder of this paper we will use the following notations. Let 𝕏 be a 0-dimensional, reduced, K-rational subscheme of (i.e. a set of points in) some projective space ℙ_{K}^{n} over a computable field K. Let s := deg 𝕏 be the number of those points. The homogeneous vanishing ideal of 𝕏 in P := K[X_{0}, …, X_{n}] is denoted by I_{𝕏}. Then R = P/I_{𝕏} is the homogeneous coordinate ring of 𝕏. We always assume that 𝕏 is entirely contained in the affine space D_{+}(X_{0}) ≅ 𝔸_{K}^{n}. Then the image x_{0} of X_{0} in R is a linear nonzerodivisor, and we can identify K[X_{0}] with its image under the canonical epimorphism P −↠ R. The affine ideal of 𝕏 is J_{𝕏} = (I_{𝕏} + (X_{0} − 1))/(X_{0} − 1) ⊆ A := K[X_{1}, …, X_{n}].

Let <_{σ} be a degree-compatible term ordering on 𝒯^{n}. We suppose that a Gröbner basis of J_{𝕏} w.r.t. <_{σ} and 𝒪_{σ}(J_{𝕏}) have been computed from the coordinates of the points via the Buchberger-Möller algorithm. As laid out in section 3, we can then effectively compute in A/J_{𝕏} and R = P/I_{𝕏}. Let 𝒪_{σ}(J_{𝕏}) = {T_{1}, …, T_{s}} with T_{i} = X^{ν_{i}} = X_{1}^{ν_{i1}} ⋯ X_{n}^{ν_{in}} and ν_{i} = (ν_{i1}, …, ν_{in}) ∈ ℕ^{n} for i = 1, …, s, and let t_{i} = T_{i} + I_{𝕏} ∈ R. W.l.o.g. let ν_{1} <_{σ} ⋯ <_{σ} ν_{s}. Then the degrees n_{i} := deg T_{i} satisfy n_{1} ≤ ⋯ ≤ n_{s}.

Algebraically, R = ⊕_{i≥0}R_{i} is a standard graded K-algebra (i.e. R_{0} = K, dim_{K} R_{1} is finite, and R = K[R_{1}]) which is a 1-dimensional Cohen-Macaulay ring with Noetherian normalization K[x_{0}] ⊆ R. In particular, R is a free K[x_{0}]-module of rank s with K[x_{0}]- basis {t_{1}, …, t_{s}} (cf. Propositions 3.3 and 3.6).

Definition 4.1. The graded R-module

ω_{R} := \underline{Hom}_{K[x_{0}]}(R, K[x_{0}])(−1)

is called the canonical module of R (cf. [K1]). Its R-module structure is given by r · φ : R ⟶ K[x_{0}] (r′ ↦ φ(rr′)), and \underline{Hom} means graded homomorphisms, i.e. in each degree i ∈ ℤ we have (ω_{R})_{i} = Hom_{K[x_{0}]}(R, K[x_{0}])_{i−1}.

Our goal in this section is to find a Gröbner basis of ω_{R} w.r.t. a suitable filtration. If we consider P = K[X_{0}][X_{1}, …, X_{n}] as a polynomial ring over K[X_{0}], then <_{σ} induces a ℤ^{n}-filtration ℰ = {ℰ_{ν}}_{ν∈ℤ^{n}} of P with ℰ_{ν} = ⟨{X^{μ} | μ ≤_{σ} ν}⟩_{K[X_{0}]} for ν ∈ ℤ^{n}. Let ℱ = {ℱ_{ν}}_{ν∈ℤ^{n}} be the induced ℤ^{n}-filtration of R/K[x_{0}], i.e. for ν ∈ ℤ^{n} we have ℱ_{ν} = ⟨{x^{μ} | μ ≤_{σ} ν}⟩_{K[x_{0}]}, where x^{μ} denotes the image of X^{μ} in R. Using Example 2.7, we obtain a ℤ^{n}-filtration 𝒢 = \{𝒢_{ν}\}_{ν∈ℤ^{n}} of \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]) which is given by 𝒢_{ν} = ⟨{φ : R → K[x_{0}] homogeneous, K[x_{0}]−linear | φ(ℱ_{−ν}^{<}) = 0}⟩_{K[x_{0}]} for ν ∈ ℤ^{n}. Then ω_{R} is ℤ^{n}-filtered by 𝒢, too, and we are looking for a Gröbner basis of ω_{R} w.r.t. this filtration. We start by studying the filtration ℱ more closely.

Proposition 4.2. a) Let ν ∈ ℤ^{n}. If ν <_{σ} ν_{1}, then ℱ_{ν} = {0}, and if ν ≥_{σ} ν_{1}, then ℱ_{ν} = ℱ_{ν_{i}} for some i ∈ {1, …, s}. Thus the filtration ℱ consists only of the s+1 different K[x_{0}]-modules

{0} ⊊ ℱ_{ν_{1}} ⊊ ⋯ ⊊ ℱ_{ν_{s}} = R.

b) The set {L_{ℱ} t_{1}, …, L_{ℱ} t_{s}} is a K[x_{0}]-basis of gr_{ℱ} R. In particular, gr_{ℱ} R is a 1-dimensional Cohen-Macaulay ring with Noetherian normalization K[x_{0}] ⊆ gr_{ℱ} R and canonical module ω_{gr_{ℱ} R} ≅ \underline{Hom}_{K[x_{0}]}(gr_{ℱ} R, K[x_{0}])(−1).

Proof: Part “a)” is clear, since {t_{1}, …, t_{s}} is a K[x_{0}]-basis of R and ord_{ℱ} t_{i} = ν_{i} for i = 1, …, s. Choose ν_{0} ∈ ℤ^{n} such that ν_{0} <_{σ} ν_{1}. Then gr_{ℱ} R = ⊕_{i=1}^{s}ℱ_{ν_{i}}/ℱ_{ν_{i−1}} shows that {L_{ℱ} t_{1}, …, L_{ℱ} t_{s}} is a K[x_{0}]-basis of gr_{ℱ} R. The additional claims follow from this observation using [M], 19.1 and [GW], 2.2.9. □

Next we consider the K[x_{0}]-linear maps p_{i} : R ⟶ K[x_{0}] which are given by p_{i}(t_{j}) = δ_{ij} for i, j = 1, …, s, i.e. {p_{1}, …, p_{s}} is the dual basis of {t_{1}, …, t_{s}}. Obviously, p_{i} is homogeneous of degree deg p_{i} = −n_{i} in \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]), of degree −n_{i} + 1 in ω_{R}, and we have ord_{𝒢} p_{i} = −ν_{i} for i = 1, …, s. The following proposition describes the module structure of ω_{R} in terms of those projections.

Proposition 4.3. a) Suppose t_{i}t_{k} = ∑_{j=1}^{s} c_{ijk}t_{j} with c_{ijk} ∈ K[x_{0}] for i, j, k = 1, …, s. Then

t_{i}p_{j} = ∑_{k=1}^{s} c_{ijk}p_{k} = \{ \begin{matrix}∑_{{k=1,...,s \atop T_{i}T_{k}>σ T_{j}}} c_{ijk}p_{k} & if T_{i} ∤ T_{j}, \\ p_{m} + ∑_{k=m+1}^{s} c_{ijk}p_{k} & if T_{j} = T_{i}T_{m}. \end{matrix}

b) The set \{L_{𝒢} p_{1}, …, L_{𝒢} p_{s}\} is a K[x_{0}]-basis of gr_{𝒢} \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]). In particular, \{p_{1}, …, p_{s}\} is a Gröbner basis of \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]) and of ω_{R}.

Proof: From t_{i}p_{j}(t_{k}) = p_{j}(t_{i}t_{k}) = ∑_{l=1}^{s} p_{j}(c_{ilk}t_{l}) = c_{ijk} = (∑_{l=1}^{s} c_{ijl}p_{l})(t_{k}) we conclude that t_{i}p_{j} = ∑_{k=1}^{s} c_{ijk}p_{k}. Furthermore, from Proposition 4.2.b and t_{i}t_{k} = ∑_{j=1}^{s} c_{ijk}t_{j} it follows that c_{ijk} = 0 whenever T_{i}T_{k} <_{σ} T_{j}, and c_{ijm} = 1 whenever T_{i}T_{m} = T_{j}. Thus claim “a)” is proved, and we turn to showing “b)”. Proposition 4.2.a implies that the filtration 𝒢 is completely described by

\{0\} = 𝒢_{−ν_{s+1}} ⊊ 𝒢_{−ν_{s}} ⊊ ⋯ ⊊ 𝒢_{−ν_{1}} = \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]),

where ν_{s+1} ∈ ℤ^{n} is any tuple such that ν_{s+1} >_{σ} ν_{s}. Thus we have an isomorphism of K[x_{0}]-algebras gr_{𝒢} \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]) ≅ ⊕_{i=1}^{s}𝒢_{−ν_{i}}/𝒢_{−ν_{i+1}}. If L_{𝒢} φ ∈ 𝒢_{−ν_{i}}/𝒢_{−ν_{i+1}} for some φ ∈ \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]), then φ(t_{j}) = 0 for j < i and φ(t_{i}) ≠ 0. Hence φ = ∑_{j≥i} φ(t_{j})p_{j} and L_{𝒢} φ = φ(t_{i})L_{𝒢} p_{i}. Since {L_{𝒢} p_{1}, …, L_{𝒢} p_{s}} is obviously K[x_{0}]- linearly independent, the claim follows. □

For computational purposes, the Gröbner basis {p_{1}, …, p_{s}} of ω_{R} we just found is much too large and has too many syzygies. Therefore we want to find a subset which is a minimal Gröbner basis, i.e. whose leading forms are a minimal system of generators of the gr_{ℱ} R-module gr_{𝒢} ω_{R}.

The elements of the set soc 𝒪_{σ}(J_{𝕏}) = {T_{i} ∈ 𝒪_{σ}(J_{𝕏}) | X_{j}T_{i} ∉ 𝒪_{σ}(J_{𝕏}) for all j = 1, …, n} are called the socle monomials of 𝕏. Let t ≥ 1 and μ_{1}, …, μ_{t} ∈ {1, …, s} such that soc 𝒪_{σ}(J_{𝕏}) = {T_{μ_{1}}, …, T_{μ_{t}}}. Actually, from the proof of our next proposition it is clear that t is the Cohen-Macaulay type of the ring gr_{ℱ} R.

Proposition 4.4. The set {p_{μ_{1}}, …, p_{μ_{t}}} is a minimal Gröbner basis of the R-module \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]), and therefore also of ω_{R}.

Proof: We apply the isomorphism gr_{𝒢} \underline{Hom}_{K[x_{0}]}(R, K[x_{0}]) ≅ \underline{Hom}_{K[x_{0}]}(gr_{ℱ} R, K[x_{0}]) described in Example 2.7, and denote for i = 1, …, s the image of L_{𝒢} p_{i} by π_{i}. From the definition of p_{i} and this isomorphism we get π_{i}(L_{ℱ} t_{j}) = δ_{ij} for i, j = 1, …, s. Now we use the multiplication table

L_{ℱ} t_{i} · L_{ℱ} t_{k} = \{ \begin{matrix}L_{ℱ} (t_{i}t_{k}) & if T_{i}T_{k} ∈ 𝒪_{σ}(J_{𝕏}), \\ 0 & otherwise, \end{matrix}

of gr_{ℱ} R and conclude that the multiplication table of \underline{Hom}_{K[x_{0}]}(gr_{ℱ} R, K[x_{0}]) is given by

L_{ℱ} t_{i} · π_{j} = \{ \begin{matrix}0 & if T_{i} ∤ T_{j}, \\ π_{m} & if T_{j} = T_{i}T_{m}. \end{matrix}

In view of this table it is immediately clear that {π_{μ_{1}}, …, π_{μ_{t}}} is a minimal system of generators of the gr_{ℱ} R-module \underline{Hom}_{K[x_{0}]}(gr_{ℱ} R, K[x_{0}]). □

5. A Gröbner Basis of the Syzygy Module

As explained in section 3, in order to compute effectively in ω_{R}, we need a Gröbner basis of the syzygy module ker ϵ_{t} of the graded epimorphism ϵ_{t} : ⊕_{i=1}^{t}P (n_{μ_{i}} −1) ⟶ ω_{R} given by e_{i} ↦ p_{μ_{i}} for i = 1, …, t. This is achieved by finding generators for the module of syzygies ker ϵ_{s} of the epimorphism ϵ_{s} : ⊕_{i=1}^{s}P (n_{i} − 1) ⟶ ω_{R} (e_{i} ↦ p_{i}) first, and then reducing them to syzygies of {p_{μ_{1}}, …, p_{μ_{t}}} using the process described at the end of section 3.

Recall that <_{σ} was a degree-compatible term ordering on 𝒯^{n}. Let <_{τ} be the projective extension of <_{σ}. Then (P, ℱ^{τ}) is a ℤ^{n+1}-filtered K-algebra. By setting H := ℤ^{n+1} × {1, …, s} and applying Example 2.6, we can obtain an H-filtration ℋ of P^{s} such that ord_{ℋ} = ((0, ord_{𝒢} p_{i}), i) = ((0, −ν_{i}), i) and gr_{ℋ} P^{s} ≅ ⊕_{i=1}^{s}P (0, ν_{i}). The ordering on H will be denoted by <_{η}. Recall also that the multiplication table of R is given by t_{i}t_{k} = ∑_{j=1}^{s} c_{ijk}t_{j} with c_{ijk} ∈ K[x_{0}] for i, j, k = 1, …, s. Clearly, we can choose c_{ijk} ∈ K[x_{0}] homogeneous of degree n_{i} − n_{j} + n_{k}, and we can identify c_{ijk} with its preimage in K[X_{0}]. Thirdly, recall that 𝒪_{σ}(J_{𝕏}) = {T_{1}, …, T_{s}} is an order ideal. For i, j ∈ {1, …, s} we thus find g(i, j), v(i, j) ∈ {1, …, s} such that T_{g(i,j)} = gcd(T_{i}, T_{j}) and T_{i} = T_{g(i,j)}T_{v(i,j)}.

Proposition 5.1. For i, j ∈ {1, …, s} with i < j, the element

S_{ij} = T_{v(i,j)}e_{i} − T_{v(j,i)}e_{j} − ∑_{k=g(i,j)+1}^{s}(c_{v(i,j)ik} − c_{v(j,i)jk})e_{k}

of P^{s} is a syzygy of p_{1}, …, p_{s} with leading form L_{ℋ} S_{i,j} = T_{v(i,j)}e_{i}. Considered as an element of ker ϵ_{s} ⊆ ⊕_{k=1}^{s}P (n_{k} − 1), it is homogeneous of degree −n_{g(i,j)} + 1.

Proof: By Proposition 4.3.a, we have t_{v(i,j)}p_{i} = p_{g(i,j)} + ∑_{k=g(i,j)+1}^{s} c_{v(i,j)ik}p_{k} and t_{v(j,i)}p_{j} = p_{g(i,j)} + ∑_{k=g(i,j)+1}^{s} c_{v(j,i)jk}p_{k}. Consequently, S_{ij} is a syzygy of p_{1}, …, p_{s}. Since ν_{v(i,j)} − ν_{i} = ν_{v(j,i)} − ν_{j} = −ν_{g(i,j)} for i < j, we get the inequality ord_{ℋ} T_{v(i,j)}e_{i} = ((0, ν_{v(i,j)} − ν_{i}), i) >_{η} ord_{ℋ} T_{v(j,i)}e_{j} = ((0, ν_{v(j,i)}−ν_{j}), j) and the equation deg T_{v(i,j)}e_{i} = deg T_{v(j,i)}e_{j} = −n_{g(i,j)} + 1. Because of ν_{v(i,j)} − ν_{i} = −ν_{g(i,j)} >_{σ} −ν_{k} for k > g(i, j), we have ord_{ℋ} T_{v(i,j)}e_{i} = ((0, ν_{v(i,j)} − ν_{i}), i) >_{η} ord_{ℋ} (c_{v(i,j)ik} − c_{v(j,i)jk})e_{k} = ((−n_{g(i,j)} + n_{k}, −ν_{k}), k) and deg(c_{v(i,j)ik} − c_{v(j,i)jk})e_{k} = −n_{g(i,j)} + 1. Therefore the leading form of S_{ij} is T_{v(i,j)}e_{i}, and S_{ij} is homogeneous of degree −n_{g(i,j)} + 1. □

Recall that, for i = 1, …, s, we have T_{i} = X^{ν_{i}} = X_{1}^{ν_{i1}} ⋯ X_{n}^{ν_{in}} with ν_{ij} ∈ ℕ. Clearly, {X_{1}^{ν_{i1}+1}, …, X_{n}^{ν_{in}+1}} is a set of generators of the monoideal {T ∈ 𝒯^{n} | T ∤ T_{i}}. Those elements can be used to construct more syzygies of p_{1}, …, p_{s}.

Proposition 5.2. For i ∈ {1, …, s} and j ∈ {1, …, n} we write can(X_{j}^{ν_{ij}+1}T_{l}, I_{𝕏}) = ∑_{k=1}^{s} d_{ijkl}T_{k} with homogeneous elements d_{ijkl} ∈ K[X_{0}] of degree deg d_{ijkl} = ν_{ij} + 1 − n_{k} + n_{l}. The element

S′_{ij} = X_{j}^{ν_{ij}+1}e_{i} − ∑_{k=1}^{s} d_{ijik}e_{k}

of P^{s} is a syzygy of p_{1}, …, p_{s} with leading form L_{ℋ} S′_{ij} = X_{j}^{ν_{ij}+1}e_{i}. Considered as an element of ker ϵ_{s} ⊆ ⊕_{k=1}^{s}P (n_{k} − 1), it is homogeneous of degree ν_{ij} − n_{i} + 2.

Proof: For l = 1, …, s we have (X_{j}^{ν_{ij}+1}p_{i})(t_{l}) = p_{i}(X_{j}^{ν_{ij}+1}t_{l}) = p_{i}(∑_{k=1}^{s} d_{ijkl}t_{l}) = d_{ijil} = (∑_{k=1}^{s} d_{ijik}p_{k})(t_{k}). Consequently, S′_{ij} is a syzygy of p_{1}, …, p_{s}. If d_{ijik} ≠ 0 for some k ∈ {1, …, s}, then X_{j}^{ν_{ij}+1}T_{k} ≥_{σ} T_{i}, since the division algorithm only reduces leading forms. In this case we even have X_{j}^{ν_{ij}+1}T_{k} >_{σ} T_{i}, since X_{j}^{ν_{ij}+1} is not a divisor of T_{i}. Therefore ν_{ij} + 1 − ν_{i} >_{σ} −ν_{k} and ord_{ℋ} X_{j}^{ν_{ij}+1}e_{i} = ((0, ν_{ij} + 1 − ν_{i}), i) >_{η} ord_{ℋ} d_{ijik}e_{k} = ((ν_{ij} +1−n_{i} +n_{k}, −ν_{k}), k). Hence we have L_{ℋ} S′_{ij} = X_{j}^{ν_{ij}+1}e_{i}, and from deg X_{j}^{ν_{ij}+1}e_{i} = ν_{ij} − n_{i} + 2 = deg d_{ijik}e_{k} we get the last claim. □

After constructing sufficiently many syzygies of p_{1}, …, p_{s}, we show that they actually form a Gröbner basis of ker ϵ_{s}.

Proposition 5.3. The set 𝔖_{s} = {S_{ij} | i, j ∈ {1, …, s}, i < j}∪{S′_{ij} | i ∈ {1, …, s}, j ∈ {1, …, n}} is a Gröbner basis of ker ϵ_{s} w.r.t. the filtration ℋ. In particular, 𝔖_{s} is a system of generators of ker ϵ_{s}.

Proof: Let S = (F_{1}, …, F_{s}) ∈ (ker ϵ_{s})_{α} with F_{i} ∈ P_{n_{i}−1+α} be a homogeneous syzygy of p_{1}, …, p_{s} of degree α, and let L_{ℋ} S = X_{0}^{m}X^{ν}e_{i} for m ≥ 0, ν ∈ ℤ^{n}, and i ∈ {1, …, s}. We have to show L_{ℋ} S ∈ ⟨L_{ℋ} S′⟩_{S′∈𝔖_{s}}. For each term cX_{0}^{m′}X^{ν′}e_{i′} with c ∈ K \ {0} appearing in S we have ((m′, ν′), i′) ≤_{η} ((m, ν), i), implying (m′, ν′ −ν_{i′}) ≤_{τ} (m, ν −ν_{i}), and therefore ν′ − ν_{i′} ≤_{σ} ν − ν_{i}. Since deg F_{i} = n_{i} − 1 + α = m + deg X^{ν} and deg F_{i′} = n_{i′} − 1 + α = m + deg X^{ν′}, and since the degree-compatibility of <_{σ} yields deg X^{ν′} − n_{i′} ≤ deg X^{ν} − n_{i}, we obtain m′ ≥ m. Thus S is divisible by X_{0}^{m}, and we can assume m = 0. Now we distinguish two cases.

Case 1: X^{ν} ∤ T_{i}. Then we have X_{j}^{ν_{ij}+1} | X^{ν} for some j ∈ {1, …, n}. This yields that L_{ℋ} S is a multiple of L_{ℋ} S′_{ij} = X_{j}^{ν_{ij}+1}e_{i}.

Case 2: X^{ν} | T_{i}. We set x^{ν} := X^{ν} + I_{𝕏} ∈ R and f_{j} := F_{j} + I_{𝕏} ∈ R for j = 1, …, s. Since X^{ν} | T_{i}, we have x^{ν}p_{i} ≠ 0, and thus ord_{𝒢} (f_{i}p_{i}) = ν − ν_{i}. Now ∑_{j=1}^{s} f_{j}p_{j} = 0, together with ord_{ℱ} f_{j} ≤_{σ} ν − ν_{i} + ν_{j} and ord_{𝒢} p_{j} = −ν_{j}, shows ∑_{j∈L} L_{𝒢} (f_{j}p_{j}) = ∑_{j∈L} L_{ℱ} f_{j}L_{𝒢} p_{j} = 0 for L = {j ∈ {1, …, s} | ord_{𝒢} (f_{j}p_{j}) = ν − ν_{i}}. Hence there is an index j ∈ L \ {i} such that L_{ℱ} f_{j}L_{𝒢} p_{j} ≠ 0.

Write L_{ℱ} f_{j} = X_{0}^{m′}X^{ν′} with m′ ≥ 0 and ν′ ∈ ℕ^{n} such that ν′ ≤_{σ} ν and m′ + deg X^{ν′} = deg X^{ν}. From X^{ν′}L_{𝒢} p_{j} ≠ 0 we conclude that X^{ν′} | T_{j} and ν′ − ν_{j} = ν − ν_{i}. Hence T_{i} = X^{ν}T and T_{j} = X^{ν′}T for some T ∈ 𝒪_{σ}(J_{𝕏}), and henceforth T_{v(i,j)} | X^{ν}. Since ν′ ≤_{σ} ν, we also get j > i. Altogether, L_{ℋ} S = X^{ν}e_{i} is a multiple of L_{ℋ} S_{ij} = T_{v(i,j)}e_{j}.

Having established that 𝔖_{s} is a Gröbner basis of ker ϵ_{s}, we conclude from Proposition 2.5.b that 𝔖_{s} is also a system of generators of ker ϵ_{s}, since ℋ is a Gröbner filtration by Example 2.6. □

Next we proceed with our task to find a Gröbner basis of ker ϵ_{t}. For i ∈ {1, …, s}\ {μ_{1}, …, μ_{t}} choose λ(i) ∈ {1, …, s} such that T_{λ(i)} is the largest multiple of T_{i} w.r.t. <_{σ} which is in 𝒪_{σ}(J_{𝕏}). Clearly, T_{λ(i)} is a socle monomial, i.e. λ(i) ∈ {μ_{1}, …, μ_{t}}. Now we form the matrix 𝔐 whose rows are the syzygies S_{iλ(i)} for i ∈ {1, …, s}\{μ_{1} …, μ_{t}}, S_{ij} for i, j ∈ {μ_{1}, …, μ_{t}} with i < j, and S′_{ij} for i ∈ {μ_{1}, …, μ_{t}}, j ∈ {1, …, n}.

We apply the process described at the end of section 3. For i ∈ {1, …, s} \ {μ_{1}, …, μ_{t}} we have T_{i} | T_{λ(i)} by construction, so T_{v(i,λ(i))} = 1. Thus the syzygy S_{iλ(i)} has leading form L_{ℋ} S_{iλ(i)} = 1 · e_{i}, and after a suitable permutation of columns the matrix \overline{𝔐} is of the form

\overline{𝔐} = [ \begin{matrix}1 & & ∗ \\ & ... & & ∗ \\ ∗ & & 1 \\ & ∗ & & ∗ \end{matrix} ]

with the partial diagonal consisting of ones being of size s−t. As explained in section 3, we can then use that partial diagonal and homogeneous P -linear row operations to reduce 𝔐 to a matrix 𝔑 of the form

𝔑 = [ \begin{matrix}1 & & ∗ \\ & ... & & ∗ \\ 0 & & 1 \\ & 0 & & s_{ij} \\ & 0 & & s′_{kl} \end{matrix} ]

where i, j ∈ {μ_{1}, …, μ_{t}} with i < j, k ∈ {μ_{1}, …, μ_{t}}, l ∈ {1, …, n}, and s_{ij}, s′_{kl} ∈ ⊕_{i=1}^{t}P (n_{μ_{i}}−1) are homogeneous syzygies of p_{μ_{1}}, …, p_{μ_{t}}. We end this section by showing that those syzygies solve our problem.

Proposition 5.4. a) Consider the injection ι : ⊕_{i=1}^{t}P (n_{μ_{i}} − 1) ⟶ ⊕_{j=1}^{s}P (n_{j} − 1) given by e_{i} ↦ e_{μ_{i}} for i = 1, …, t, and equip ⊕_{i=1}^{t}P (n_{μ_{i}} − 1) with the induced filtration ℋ′ = {ι^{−1}(ℋ_{ν} ∩ im ι)}_{ν∈H}. Then L_{ℋ′} s_{ij} = T_{v(i,j)}e_{i} for i, j ∈ {μ_{1}, …, μ_{t}} with i < j, and L_{ℋ′} s′_{kl} = X_{l}^{ν_{kl}+1}e_{k} for k ∈ {μ_{1}, …, μ_{t}}, l ∈ {1, …, n}.

b) The set 𝔖_{t} = {s_{ij} | i, j ∈ {μ_{1}, …, μ_{t}}, i < j} ∪ {s′_{kl} | k ∈ {μ_{1}, …, μ_{t}}, l ∈ {1, …, n}} is a Gröbner basis of ker ϵ_{t} w.r.t. ℋ′. In particular, 𝔖_{t} is a set of generators of ker ϵ_{t}.

Proof: All syzygies from {S_{ij} | i, j ∈ {μ_{1}, …, μ_{t}}, i < j} ∪ {S′_{kl} | k ∈ {μ_{1}, …, μ_{t}}, l ∈ {1, …, n}} have their leading form w.r.t. ℋ in one of their last t columns (cf. Propositions 5.1 and 5.2). Thus this leading form is not changed during the elimination process and part “a)” follows. The proof of part “b)” is completely analogous to the proof of Proposition 5.3, and therefore left to the reader. □

6. A Presentation of the Canonical Module

In the previous sections we found a presentation of ω_{R} of the form P^{\binom{t}{2}+nt} ⟶ P^{t} ⟶ ω_{R} ⟶ 0. Of course we could use the elements of 𝔖_{t} now in order to find a minimal system of generators of ω_{R} via Proposition 3.7, and a set of generators of their syzygy module via Proposition 3.8. But as we are interested in a minimal homogeneous presentation of ω_{R}, we would then have to compute a Gröbner basis of that syzygy module to be able to minimize its set of generators. Since this could become quite costly, we find it easier to proceed as follows.

First we renumber the elements of 𝔖_{t} such that 𝔖_{t} = \{s_{1}, …, s_{q}\} with q = \binom{t}{2}+nt. The module ⊕_{i=1}^{t}P (n_{μ_{i}} − 1) is H-filtered by ℋ′. As, in fact, all elements have orders in the subset of H which is the image of H′ = ℤ^{n+1} × {1, …, t} under the injection H′ ⟶ H, (ν, i) ↦ (ν, μ_{i}), we can consider ℋ′ as an H′-filtration. The induced ordering on H′ is denoted by <_{η′}. For i = 1, …, q we let ord_{ℋ′} s_{q} = (ψ_{i}, ϱ_{i}) with ψ_{i} ∈ ℤ^{n+1} and ϱ_{i} ∈ {1, …, t} given by Proposition 5.4.a. The free P -module P^{q} has an I := ℤ^{n+1} × {1, …, q}-filtration 𝒥 = {𝒥_{(ν,i)}}_{(ν,i)∈I} such that ord_{𝒥} e_{i} = (ψ_{i}, i) for i = 1, …, q. Our next goal is to find a Gröbner basis of the syzygy module of 𝔖_{t} w.r.t. this filtration 𝒥.

For i, j = 1, …, q we let k(i, j) ∈ ℤ^{n+1} be the componentwise maximum of ψ_{i} and ψ_{j}, and w(i, j) := k(i, j) − ψ_{i} ∈ ℕ^{n+1}. Setting \underline{X}^{v} = X_{0}^{v_{0}} ⋯ X_{n}^{v_{n}} for v = (v_{0}, …, v_{n}) ∈ ℤ^{n+1}, we can interpret \underline{X}^{k(i,j)} as the least common multiple of \underline{X}^{ψ_{i}} and \underline{X}^{ψ_{j}}, although some components of ψ_{i} and ψ_{j} may be negative. Obviously, for i, j ∈ {1, …, q} we have ord_{ℋ′} (\underline{X}^{w(i,j)}s_{i}) = (k(i, j), ϱ_{i}). Now we are ready to describe the desired Gröbner basis.

Proposition 6.1. Let i, j ∈ {1, …, q} such that i < j and ϱ_{i} = ϱ_{j}.

a) There are homogeneous polynomials E_{ijk} ∈ P of degree deg E_{ijk} = deg \underline{X}^{w(i,j)} + deg s_{i} − deg s_{k} such that

\underline{X}^{w(i,j)}s_{i} − \underline{X}^{w(j,i)}s_{j} = ∑_{k=1}^{q} E_{ijk}s_{k}

and such that ord_{ℋ′} E_{ijk}s_{k} <_{η′} (k(i, j), ϱ_{i}) for all k ∈ {1, …, q} with E_{ijk} ≠ 0.

b) The element Σ_{ij} = \underline{X}^{w(i,j)}e_{i} − \underline{X}^{w(j,i)}e_{j} − ∑_{k=1}^{q} E_{ijk}e_{k} of P^{q} is a homogeneous syzygy of s_{1}, …, s_{q} with leading form L_{𝒥}Σ_{ij} = \underline{X}^{w(i,j)}e_{i}.

c) The set 𝔖_{q} = {Σ_{ij} | i, j ∈ {1, …, q}, ϱ_{i} = ϱ_{j}} is a Gröbner basis of the module of syzygies ker ϵ_{q} of s_{1}, …, s_{q} w.r.t. the filtration 𝒥. Here ϵ_{q} is the homomorphism ϵ_{q} : P^{q} ⟶ P^{t} given by e_{i} ↦ s_{i} for i = 1, …, q.

Proof: Part “a)” follows immediately from the observation that ord_{ℋ′} (\underline{X}^{w(i,j)}s_{i} − \underline{X}^{w(j,i)}s_{j}) <_{η′} (k(i, j), ϱ_{i}) and the fact that \{s_{1}, …, s_{q}\} is a homogeneous Gröbner basis of ker ϵ_{t} by Propsition 5.4.b. Part “b)” is then clear, and the proof of part “c)” is completely analogous to the proof of Proposition 5.3 and therefore omitted. □

Using this proposition, we are able to compute the desired minimal presentation. In the first step, we apply Propsition 3.7 and use our knowledge of 𝔖_{q} to find a minimal system of generators 𝔖′ ⊆ 𝔖_{t} of ker ϵ_{t}. Then we apply Proposition 3.7 for a second time and find a minimal system of generators 𝔊 ⊆ {p_{μ_{1}}, …, p_{μ_{t}}} of ω_{R}. Let β be the minimal number of generators of ω_{R}, i.e. the Cohen-Macaulay type of R, and let m_{1}, …, m_{β} ∈ {μ_{1}, …, μ_{t}} such that 𝔊 = {p_{m_{1}}, …, p_{m_{β}}}. Also, let α_{i} = deg p_{m_{i}} for i = 1, …, β. In the third step, we apply the second part of Proposition 3.8 and compute from 𝔖′ a minimal system of generators 𝔖 of the module of syzygies of 𝔊. Let 𝔖 = {s′_{1}, …, s′_{β′}} with β′ ≥ 0, and let α′_{i} = deg s′_{i} for i = 1, …, β′. Altogether, we arrive at the following result.

Proposition 6.2. The exact sequence

\begin{matrix}⨁_{i=1}^{β′} P (−α′_{i}) & ⟶ & ⨁_{i=1}^{β} P (−α_{i}) & ⟶ & ω_{R} & ⟶ & 0 \\ e_{i} & ⟼ & s′_{i} e_{i} & ⟼ & p_{m_{i}} \end{matrix}

is a minimal homogeneous presentation of the graded P -module ω_{R}.

7. Application to Minimal Resolutions

Starting again with a 0-dimensional, reduced subscheme 𝕏 ⊆ ℙ_{K}^{n}, consisting of K-rational points, with homogeneous coordinate ring R = P/I_{𝕏}, and with canonical module ω_{R}, we are going to examine the minimal graded free resolutions of I_{𝕏} and ω_{R}, considered as graded modules over P = K[X_{0}, …, X_{n}]. The graded free P -resolution of I_{𝕏} is of the form

0 ⟶ ⨁_{i=1}^{β_{n}} P (−α_{ni}) ⟶^{Φ_{n}} ⋯ ⟶ ⨁_{i=1}^{β_{1}} P (−α_{1i}) ⟶^{Φ_{1}} I_{𝕏} ⟶ 0

with α_{ij}, β_{i} ∈ ℕ, and homogeneous P -linear maps Φ_{i} of degree zero whose matrices 𝔄_{i} consist of homogeneous polynomials of positive degree.

Since R is a 1-dimensional Cohen-Macaulay ring, we have \underline{Ext}_{P}^{i} (R, P) = 0 for i = 0, …, n − 1 (see [M], 17.1, or [G], IV, § 4, for an elementary approach) and ω_{R} ≅ \underline{Ext}_{P}^{n} (R, P)(−n − 1) (cf. [GW], 2.1.6). Therefore, if we dualize and shift the above resolution, we obtain a minimal graded free P -resolution of ω_{R} of the form

0 → P (−n − 1) ⟶^{Φ_{1}} ˇ ⨁_{i=1}^{β_{1}} P (α_{1i} − n − 1) ⟶ ⋯ ⟶^{Φ_{n}} ˇ ⨁_{i=1}^{β_{n}} P (α_{ni} − n − 1) → ω_{R} → 0.

The numbers α_{ij}, β_{i} are invariants of 𝕏 ⊆ ℙ_{K}^{n} and thus interesting to compute. For two of them we reserve special names: α_{𝕏} = min{α_{11}, …, α_{1β_{1}}} = min{i ∈ ℕ | (I_{𝕏})_{i} ≠ 0} and σ_{𝕏} = max{α_{n1} − n − 1, …, α_{nβ_{n}} − n − 1} = − min{i ∈ ℤ | (ω_{R})_{i} ≠ 0}.

It is known (cf. [S], Kor. 1) that σ_{𝕏} ≥ α_{𝕏} − 2 holds all the time, and that the numbers α_{ij}, β_{i} are uniquely determined, if σ_{𝕏} = α_{𝕏} − 2 (cf. [S], Thm. A). The next case is of particular interest.

Definition 7.1. The Hilbert function of 𝕏 is the function H_{𝕏} : ℤ ⟶ ℕ given by i ↦ dim_{K} R_{i}. We say that 𝕏 has generic Hilbert function, if H_{𝕏} = min{H_{ℙ^{n}}, deg 𝕏}.

It follows from [K1], Lemma 1.3.c, that σ_{𝕏} = max{i ∈ ℤ | H_{𝕏}(i) < deg 𝕏}, and therefore 𝕏 has generic Hilbert function, if and only if σ_{𝕏} ≤ α_{𝕏} − 1. The reason for the choice of this name is that, in case of an algebraically closed field K, a generic set of points 𝕏 ⊆ ℙ_{K}^{n} has generic Hilbert function. Here “generic set of points” means that there is a nonempty open subset of the symmetric power (ℙ_{K}^{n})^{(s)} such that all sets of s points in ℙ_{K}^{n} corresponding to closed points of this open set have the stated property.

For the remainder of this section, we shall assume that K is algebraically closed and 𝕏 ⊆ ℙ_{K}^{n} is a set of points with σ_{𝕏} = α_{𝕏} − 1. Our goal is to compute the invariants α_{ij}, β_{i}. W.l.o.g. we can assume that α_{i1} ≤ ⋯ ≤ α_{iβ_{i}} for i = 1, …, n. Since all entries in the matrices 𝔄_{1}, …, 𝔄_{n} have positive degrees, we have α_{11} < ⋯ < α_{n1}. Since their transposed matrices have the same property, we can look at the above resolution of ω_{R} and get α_{1β_{1}} < ⋯ < α_{nβ_{n}}. Thus σ_{𝕏} = α_{𝕏} − 1 implies that in the chain of inequalities σ_{𝕏} = α_{nβ_{n}} − n − 1 ≥ α_{n1} − n − 1 ≥ α_{n−1 1} − n ≥ ⋯ ≥ α_{11} − 2 = α_{𝕏} − 2 we have exactly one step where there is a strict decrease by one, and otherwise we have equality. In other words, the resolution of I_{𝕏} is of the form (∗)

0 → P (−α_{𝕏}−n+1)^{a_{n}} ⊕P (−α_{𝕏}−n)^{b_{n}} → ⋯ → P (−α_{𝕏})^{a_{1}} ⊕P (−α_{𝕏}−1)^{b_{1}} → I_{𝕏} → 0

and we want to compute the numbers a_{i}, b_{i}. Clearly, if a_{i} = 0 for some i ∈ {1, …, n}, then a_{i} = … = a_{n} = 0, and if b_{i} = 0, then b_{1} = … = b_{i} = 0. For the numbers a_{i}, b_{i} there is the following intriguing conjecture (cf. [L], sect. 2).

Minimal Resolution Conjecture (MRC). If 𝕏 ⊆ ℙ_{K}^{n} is a generic set of points and m := ⌈α_{𝕏}(\binom{α_{𝕏}+n}{n}/ deg 𝕏 − 1)⌉, then a_{m+1} = b_{m−1} = 0.

In fact, we shall see in a moment that if 𝕏 satisfies MRC, then all numbers a_{i}, b_{i} are uniquely determined. Since σ_{𝕏} = α_{𝕏} − 1, we have \binom{n+α_{𝕏}−1}{n} = H_{ℙ^{n}}(α_{𝕏} − 1) < deg 𝕏 < H_{ℙ^{n}}(α_{𝕏}). The number Δ_{𝕏} = deg 𝕏 − \binom{n+α_{𝕏}−1}{n} is called the last difference of 𝕏, as it is the last nonzero value of the first difference function of H_{𝕏}. Recall that the minimal graded free resolution of \binom{n+α_{𝕏}−1}{n} points 𝕐 ⊆ ℙ_{K}^{n} is given by

0 ⟶ P (−α_{𝕏} − n + 1)^{c_{n}} ⟶ ⋯ ⟶ P (−α_{𝕏})^{c_{1}} ⟶ I_{𝕐} ⟶ 0

with c_{i} = \binom{n+α_{𝕏}−1}{i+α_{𝕏}−1}\binom{i+α_{𝕏}−2}{α_{𝕏}−1} for i = 1, …, n (cf. [S], Thm. A.b). Our next proposition gives a strong restriction on the numbers a_{i}, b_{i} of 𝕏 and implies the description of the conjectured generic minimal resolution in [L], 2.3. (A different proof is given in [Eh], sect. 4).

Lemma 7.2. For natural numbers α, i, n with i ≤ n we have

∑_{j=0}^{i}(−1)^{j}\binom{n+i−j}{n}\binom{n+α−1}{α+j}\binom{α−1+j}{α−1} = \binom{n+α+i}{n} − \binom{n+α−1}{n}.

Proof: In view of the Gould inverse relations given by a_{i} = ∑_{j=0}^{i} \binom{n+1}{i−j}b_{j} and b_{i} = ∑_{j=0}^{i}(−1)^{i+j}\binom{n+i−j}{i−j}a_{j} (cf. [Ri], p. 52), we see that it suffices to show the equation

∑_{j=0}^{i}(−1)^{j}\binom{n+1}{i−j}\binom{n+α+j}{n} − ∑_{j=0}^{i}(−1)^{j}\binom{n+1}{i−j}\binom{n+α−1}{n} = \binom{n+α−1}{α+i}\binom{α−1+i}{α−1}.

Using [Ri], p. 33, ex. 9, this boils down to showing that ∑_{j=0}^{i}(−1)^{j}\binom{n+1}{i−j}\binom{n+α+j}{n} = \binom{n+α}{α+i}\binom{α−1+i}{α−1}. By applying [Ri], ch. 1.3, eqs. (3), (5a), and (11), we find

\begin{matrix}∑_{j=0}^{i}(−1)^{j}\binom{n+1}{i−j}\binom{n+α+j}{n} = & ∑_{j=0}^{i}(−1)^{j}\binom{n+1}{i−j} ∑_{k≥0} \binom{n+α}{n−k}\binom{j}{k} \\ = & ∑_{k≥0}(−1)^{i}\binom{n+α}{n−k} ∑_{j=0}^{i}(−1)^{j}\binom{n+1}{j}\binom{i−j}{k} \\ = & ∑_{k≥0}(−1)^{i}\binom{n+α}{n−k}\binom{i−n−1}{i−k} = ∑_{k≥0}(−1)^{k}\binom{n+α}{n−k}\binom{n−k}{n−i} \\ = & ∑_{k≥0}(−1)^{n−k}\binom{k}{n−i}\binom{n+α}{k} = \binom{α+i−1}{i}\binom{n+α}{n−1}, \end{matrix}

as desired. □

Proposition 7.3. Let 𝕏 ⊆ ℙ_{K}^{n} be a set of points with σ_{𝕏} = α_{𝕏} − 1.

a) We have a_{1} = \binom{n+α_{𝕏}}{n} − deg 𝕏, b_{n} = Δ_{𝕏}, and a_{i} − b_{i−1} = c_{i} − Δ_{𝕏}\binom{n}{i−1} for i = 2, …, n.

b) If 𝕏 satisfies MRC, then

a_{i} = \{ \begin{matrix}c_{i} − Δ_{𝕏}\binom{n}{i−1} & if c_{i} − Δ_{𝕏}\binom{n}{i−1} ≥ 0, \\ 0 & otherwise, and \end{matrix}
b_{i−1} = \{ \begin{matrix}−c_{i} + Δ_{𝕏}\binom{n}{i−1} & if c_{i} − Δ_{𝕏}\binom{n}{i−1} ≤ 0, \\ 0 & otherwise. \end{matrix}

Proof: In order to prove “a)”, we compute the dimensions of the homogeneous components of (∗) and get

dim_{K}(I_{𝕏})_{α_{𝕏}+i} = a_{1}\binom{n+i}{n} + ∑_{j=1}^{i}(−1)^{j}(a_{j+1} − b_{j})\binom{n+i−j}{n}

for i = 0, …, n − 1. Thus a_{1} = dim_{K}(I_{𝕏})_{α_{𝕏}} = \binom{n+α_{𝕏}}{n} − deg 𝕏 and a_{2} − b_{1} = a_{1}\binom{n+1}{n} − dim_{K}(I_{𝕏})_{α_{𝕏}+1} = (n + 1)\binom{n+α_{𝕏}}{n} − n deg 𝕏 − \binom{n+α_{𝕏}+1}{n} = α_{𝕏}\binom{n+α_{𝕏}−1}{α_{𝕏}+1} − n deg 𝕏 + n\binom{n+α_{𝕏}−1}{n} = c_{2} − Δ_{𝕏}\binom{n}{1}. Letting α := α_{𝕏}, remembering dim_{K}(I_{𝕏})_{α+i} = \binom{n+α+i}{n} − deg 𝕏, and using Lemma 7.2, we get for i = 1, …, n − 1 inductively

a_{i+1} − b_{i} =(−1)^{i} dim_{K}(I_{𝕏})_{α+i} + (−1)^{i+1}\binom{n+i}{n}a_{1}+ (−1)^{i+1} ∑_{j=1}^{i−1}(−1)^{j}(a_{j+1} − b_{j})\binom{n+i−j}{n}
=(−1)^{i}\binom{n+α+i}{n} + (−1)^{i+1} deg 𝕏 + (−1)^{i+1}\binom{n+i}{n}\binom{n+α}{n} + (−1)^{i}\binom{n+i}{n} deg 𝕏

+ (−1)^{i} ∑_{j=1}^{i−1}(−1)^{j}\binom{n+i−j}{n}\binom{n}{j} deg 𝕏 + (−1)^{i+1} ∑_{j=1}^{i−1}(−1)^{j}\binom{n+i−j}{n}\binom{n}{j}\binom{n+α−1}{α−1}

+ (−1)^{i+1} ∑_{j=1}^{i−1}(−1)^{j}\binom{n+i−j}{n}\binom{n+α−1}{α+j}\binom{α−1+j}{α−1}

=\binom{n+α−1}{α+i}\binom{α−1+i}{α−1} − \binom{n}{i} deg 𝕏 + \binom{n}{i}\binom{n+α−1}{α−1} = c_{i+1} − Δ_{𝕏}\binom{n}{i}.

Part “b)” follows immediately from “a)” and a_{m+1} = b_{m−1} = 0. □

Let us illustrate this proposition with an example.

Example 7.4. Let K be an algebraically closed field of characteristic zero, and let 𝕏 ⊆ ℙ_{K}^{6} be a set of 11 generic points. The Hilbert function of 𝕏 is H_{𝕏} : 1 7 11 11 ⋯, so σ_{𝕏} = 1, α_{𝕏} = 2, and Δ_{𝕏} = 4. The minimal resolution of 7 generic points in ℙ_{K}^{6} is given by the table

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 \\ c_{i} & 21 & 70 & 105 & 84 & 35 & 6 \end{matrix}

Subtracting Δ_{𝕏} = 4 times the 6^{th} row of Pascal’s triangle yields

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ c_{i} − 4\binom{6}{i−1} & 17 & 46 & 45 & 4 & -25 & -18 & -4 \end{matrix}

Hence the minimal resolution of I_{𝕏} expected by MRC is given by the table

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 \\ a_{i} & 17 & 46 & 45 & 4 & 0 & 0 \\ b_{i} & 0 & 0 & 0 & 25 & 18 & 4 \end{matrix}

In fact, in concrete examples the minimal resolution of 𝕏 is really given by the table

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 \\ a_{i} & 17 & 46 & 45 & 5 & 0 & 0 \\ b_{i} & 0 & 0 & 1 & 25 & 18 & 4 \end{matrix}

still in accordance with part a) of Proposition 7.3, but violating MRC.

How can we use the material presented in sections 3 to 6 and Proposition 7.3 to calculate minimal resolutions, in particular of schemes 𝕏 ⊆ ℙ_{K}^{n} with σ_{𝕏} = α_{𝕏} − 1 ? The following remark collects what we know so far.

Remark 7.5. a) Given 𝕏 ⊆ ℙ_{K}^{n}, the Buchberger-Möller algorithm allows us to compute I_{𝕏} ⊆ K[X_{0}, …, X_{n}] in a fast (polynomial-time) way.

b) The algorithm described in sections 4 to 6 allows us to compute a minimal presentation of ω_{R} in a fast way. The resolution of ω_{R} is dual to the resolution of I_{𝕏}.

c) If we want to know the numbers a_{i}, b_{i} for 𝕏 ⊆ ℙ_{K}^{n} with σ_{𝕏} = α_{𝕏} − 1, it suffices by Proposition 7.3.a to compute either a_{1}, …, a_{n} or b_{1}, …, b_{n}. As an additional help, we can use a_{i} = 0 ⇒ a_{i} = … = a_{n} = 0 and b_{i} = 0 ⇒ b_{1} = … = b_{i} = 0.

Now we consider the following notion.

Definition 7.6. Let P = K[X_{0}, …, X_{n}], let M be a finitely generated, graded P - module, and let α = min{i ∈ ℤ | M_{i} ≠ 0}. Furthermore, let

0 ⟶ ⨁_{i=1}^{β_{n}} P (−α_{ni}) ⟶ ⋯ ⟶ ⨁_{i=1}^{β_{0}} P (−α_{0i}) ⟶ M ⟶ 0

be the minimal graded free P -resolution of M, where α + i ≤ α_{i1} ≤ ⋯ ≤ α_{iβ_{i}} for i = 0, …, n. Then the subcomplex

0 ⟶ ⨁_{{i|α_{ni}=α+n}} P (−α − n) ⟶ ⋯ ⟶ ⨁_{{i|α_{0i}=α}} P (−α) ⟶ M ⟶ 0

is called the linear part of the resolution of M.

In our situation, the linear part of the resolution of I_{𝕏} is given by

0 ⟶ P (−α_{𝕏} − n + 1)^{a_{n}} ⟶ ⋯ ⟶ P (−α_{𝕏})^{a_{1}} ⟶ I_{𝕏} ⟶ 0,

and the linear part of the resolution of ω_{R} is given by

0 ⟶ P (σ_{𝕏} − n + 1)^{b_{1}} ⟶ ⋯ ⟶ P (σ_{𝕏})^{b_{n}} ⟶ ω_{R} ⟶ 0.

Therefore we can compute the numbers a_{i}, b_{i} by finding the linear parts of the resolutions of I_{𝕏} and ω_{R}. This is done as follows.

Remark 7.7. Let M ⊆ ⊕_{i=1}^{r}P (−α_{i}) be a graded submodule, let α = min{i ∈ ℤ | M_{i} ≠ 0}, let <_{σ} be a degree-compatible term ordering of 𝒯^{n+1}, and let 𝒢 be the ℤ^{n+1} × {1, …, r}-filtration induced by ℱ^{σ} on ⊕_{i=1}^{r}P (−α_{i}) such that ord_{𝒢} e_{i} = (m_{i}, i) for some m_{1}, …, m_{r} ∈ ℤ^{n+1}. Furthermore, let {g_{1}, …, g_{s}} be a K-basis of M_{α} such that L_{𝒢} g_{i} = T_{i}e_{μ(i)} with T_{1}, …, T_{s} ∈ 𝒯^{n+1} pairwise distinct, and with μ(i) ∈ {1, …, r}. Thus we have deg T_{1} + α_{μ(1)} = … = deg T_{s} + α_{μ(s)}. Then we form the set

S = {X_{β}g_{i} − X_{γ}g_{j} | i, j ∈ {1, …, s}, β, γ ∈ {0, …, n}, X_{β}T_{i} = X_{γ}T_{j}},

and we reduce each element of this set against {g_{1}, …, g_{s}} \ {g_{i}, g_{j}} (resp. the part of the Gröbner basis of M w.r.t. 𝒢 found so far) by successively eliminating leading forms until we either find a linear syzygy of g_{1}, …, g_{s} or a new element of the Gröbner basis of M w.r.t. 𝒢. It is clear that in this way we obtain a system of generators of the linear part of the syzygy module of M which we can then interreduce again to continue the process.

By repeatedly applying this remark, we can quickly calculate the linear part of the resolution of a given module, in particular of I_{𝕏} and ω_{R}. In view of the next proposition, this allows us to prove MRC in many cases computationally.

Proposition 7.8. Let K be an algebraically closed field. If there exists a set of s points in ℙ_{K}^{n} satisfying MRC, then the generic set of s points in ℙ_{K}^{n} satisfies MRC.

Proof: W.l.o.g. we can assume that σ_{𝕏} = α_{𝕏} − 1, as in case σ_{𝕏} = α_{𝕏} − 2 there is only one possible set of invariants c_{1}, …, c_{n}. Let ℍ be the Hilbert scheme parametrizing 0-dimensional subschemes 𝕏 ⊆ ℙ_{K}^{n} with deg 𝕏 = s. From [BG], 2.15 it follows that there is an open subset 𝕌 ⊆ ℍ whose closed points correspond to schemes 𝕏 with H_{𝕏} = min{H_{ℙ^{n}}, deg 𝕏} and minimal Betti numbers a_{1} + b_{1}, …, a_{n} + b_{n}. Since a_{1}, a_{2} − b_{1}, …, a_{n} − b_{n−1}, b_{n} are fixed by Proposition 7.3.a, this means that such schemes have minimal numbers a_{i}, b_{i}. Clearly, the values of a_{i}, b_{i} given in Proposition 7.3.b are the least possible, so if there exists a set of points 𝕏 having those invariants (i.e. satisfying MRC), then the same is true for every 0-dimensional scheme corresponding to a closed point of 𝕌.

Let 𝕍 be the open subscheme of the Hilbert scheme whose closed points correspond to reduced 0-dimensional schemes. By assumption, 𝕌 ∩ 𝕍 is not empty. Now we apply the Hilbert-Chow morphism ℍ ⟶ (ℙ_{K}^{n})^{(s)} (cf. [F], [MF]). This morphism induces an isomorphism of 𝕍 with the open subset 𝕎 of (ℙ_{K}^{n})^{(s)} parametrizing cycles of s distinct points of ℙ_{K}^{n}. Thus the image of 𝕌 ∩ 𝕍 in 𝕎 is a nonempty open subset whose closed points correspond to sets of points in ℙ_{K}^{n} satisfying MRC. □

Using this proposition and the computational techniques described before, the authors were able to prove the following result by computer calculation.

Proposition 7.9. Let K be an algebraically closed field of characteristic zero. Then the Minimal Resolution Conjecture is true for generic sets of s points in ℙ_{K}^{n}, as long as n ≤ 9, s ≤ 50, and (n, s) ∉ {(6, 11), (7, 12), (8, 13)}.

What about the remaining three cases? In 1992, F. Schreyer pointed out that 12 generic points in ℙ_{ℂ}^{7} and 13 generic points in ℙ_{ℂ}^{8} appear to yield counterexamples to MRC. Using “random” points in ℙ_{ℚ}^{n}, the authors found for 12 generic points in ℙ_{ℂ}^{7} the resolution table

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ a_{i} & 24 & 84 & 126 & 84 & 4 & 0 & 0 \\ b_{i} & 0 & 0 & 0 & 4 & 36 & 21 & 4 \end{matrix}

and for 13 generic points in ℙ_{ℂ}^{8} it is given by

\begin{matrix}i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ a_{i} & 32 & 136 & 266 & 280 & 140 & 2 & 0 & 0 \\ b_{i} & 0 & 0 & 0 & 0 & 10 & 49 & 24 & 4 \end{matrix}

The apparent failure of MRC for 11 generic points in ℙ_{ℂ}^{6} was reported by M. Boij and R. Fröberg in 1993 (see Example 7.4).

How can one disprove MRC in those particular cases using a computer? In view of [BG], 2.15 and Propsition 7.3.a, it suffices to compute the numbers a_{i}, b_{i} for the set of points 𝕏 = {P_{1}, …, P_{s}} with P_{i} = (1 : Y_{i1} : …: Y_{in}) over the field K = ℚ(Y_{ij})_{i=1...s,j=1...n}. Programming fast and efficient arithmetics for large fields of rational functions, however, seems to be a difficult problem that still awaits an answer.

8. Application to Checking Uniformity Conditions

Let K be an algebraically closed field. For a 0-dimensional, reduced subscheme 𝕏 ⊆ ℙ_{K}^{n} consisting of s = deg 𝕏 K-rational points, we have the following notion of uniformity (cf. [K1]).

Definition 8.1. For i ≥ 0, we say that 𝕏 is i-uniform, if every subset 𝕐 ⊆ 𝕏 of degree deg 𝕐 ≥ s − i has Hilbert function H_{𝕐} = min{H_{𝕏}, deg 𝕐}. Equivalently, 𝕏 is i-uniform, if and only if any two subsets 𝕐, 𝕐′ of degree s − i ≤ deg 𝕐 = deg 𝕐′ ≤ s have the same Hilbert function H_{𝕐} = H_{𝕐′}.

The two extremal cases have special names. A 1-uniform set of points is also called a Cayley-Bacharach scheme (for short, CB-scheme, cf. [GKR]), and an (s − 1)-uniform scheme is said to be in uniform position (cf. [H]).

In this section, we want to give a solution to the problem of checking those uniformity conditions computationally, if we are given the set of points 𝕏 via their coordinates. The naïve approach is, of course, to calculate all Hilbert functions of the subsets 𝕐 ⊆ 𝕏 under consideration. For instance in the case of checking uniform position, this entails the calculation of 2^{s} Hilbert functions. Already for moderate numbers of points s, this is clearly impracticable. Therefore we shall exhibit a different approach.

For small uniformities, and in particular for checking the Cayley-Bacharach property, the solution is provided by the following remark based on [K1], 3.4. Recall that, given 𝕏 = {P_{1}, …, P_{s}} ⊆ ℙ_{K}^{n}, we assumed 𝕏 ⊆ D_{+}(X_{0}), we let P = K[X_{0}, …, X_{n}] and R = P/I_{𝕏}, and we defined the invariants σ_{𝕏} = − min{i ∈ ℤ | (ω_{R})_{i} ≠ 0} and Δ_{𝕏} = H_{𝕏}(σ_{𝕏} + 1) − H_{𝕏}(σ_{𝕏}).

Remark 8.2. Using the Buchberger-Möller algorithm, we can calculate a Gröbner basis of I_{𝕏} w.r.t. a degree-compatible term ordering <_{τ} from the coordinates of P_{1}, …, P_{s}. As a by-product, this algorithm yields polynomials f_{1}, …, f_{s} ∈ P_{σ_{𝕏}+1} such that f_{i}(P_{j}) = δ_{ij} for i, j = 1, …, s (cf. [MR], sect. 1.2 and [GKR], sect. 2). Here we write P_{i} = (1 : p_{i1} :

…: p_{in}), and we set f(P_{i}) = f(1, p_{i1}, …, p_{in}) for a homogeneous polynomial f ∈ P. The polynomials f_{1}, …, f_{s} are called the separators of 𝕏 and are represented in normal form w.r.t. I_{𝕏}. Their images in R_{σ_{𝕏}+1} form a K-basis of that vector space (cf. [GKR], 1.13.a).

Next we compute f̄_{i}(X_{1}, …, X_{n}) = f_{i}(0, X_{1}, …, X_{n}) for i = 1, …, s. As the polynomials f_{1}, …, f_{s} were in their normal form w.r.t. I_{𝕏}, the elements f̄_{1}, …, f̄_{s} are K-linear combinations of the Δ_{𝕏} monomials of 𝒪_{τ} (J_{𝕏}) of degree σ_{𝕏} +1 (cf. sect. 3). Let T_{1}, …, T_{Δ} be those monomials, and let f̄_{i} = ∑_{j=1}^{Δ} c_{ij}T_{j} with c_{ij} ∈ K for i = 1, …, s. Then [K1], 3.4, says that for any i ∈ {1, …, Δ_{𝕏}} the following conditions are equivalent:

a) The scheme 𝕏 is i-uniform.

b) Any i columns of the matrix (c_{ij}) are K-linearly independent. Of course, condition b) is easy to check for small i, and we are done.

A much more difficult situation arises for higher uniformities. It appears to be impossible to check those directly from the Gröbner basis of I_{𝕏} or the separators. Again the results from [K1] come to the rescue: the relevant information is encoded in the multiplication maps of the canonical module ω_{R}! More precisely, [K1], 3.2, says that for i = s − H_{𝕏}(j) and j ∈ {0, …, σ_{𝕏}} the following conditions are equivalent:

a) The scheme 𝕏 is i-uniform.

b) For each k ∈ {j, …, σ_{𝕏}}, the multiplication map μ : R_{k} ⊗ (ω_{R})_{−k} ⟶ (ω_{R})_{0} is biinjective.

Here “biinjective” means that μ(r ⊗ φ) = 0 implies r = 0 or φ = 0. Let us see how one can check condition b) computationally. From sections 4 to 6 we know how to get a minimal graded presentation

⨁_{i=1}^{β′} P (−α′_{i}) ⟶ ⨁_{i=1}^{β} P (−α_{i}) ⟶ ω_{R} ⟶ 0.

Thus we can find elements φ_{1}, …, φ_{m} ∈ (⨁_{i=1}^{β} P (−α_{i}))_{−k} whose images form a K-basis of

(ω_{R})_{−k}. Here k ∈ {j, …, σ_{𝕏}} and m = dim_{K}(ω_{R})_{−k} = s − H_{𝕏}(k). In the same way, we

can find elements ψ_{1}, …, ψ_{s−1} ∈ (⨁_{i=1}^{β} P (−α_{i}))_{0} whose images form a K-basis of (ω_{R})_{0}.

Moreover, let r_{1}, …, r_{l} ∈ P_{k} with l = H_{𝕏}(k) be those monomials from 𝒪_{τ} (J_{𝕏}) whose residue classes form a K-basis of R_{k}. Then we write r_{λ}φ_{μ} in normal form w.r.t. the syzygy module of ω_{R}, and we get representations r_{λ}φ_{μ} = ∑_{ν=1}^{s−1} c_{λμν}ψ_{ν} with c_{λμν} ∈ K for λ = 1, …, l and μ = 1, …, m. With this setup, we have at our disposal the following two methods to check whether the bilinear map given by (c_{λμν}) is biinjective.

Remark 8.3. After introducing new variables Y_{1}, …, Y_{l} and Z_{1}, …, Z_{m}, we form the quadratic polynomials f_{ν} = ∑_{λ,μ} c_{λμν}Y_{λ}Z_{μ} for ν = 1, …, s−1. Since we want to check whether (a_{1}r_{1} + ⋯ + a_{l}r_{l})(b_{1}φ_{1} + ⋯ + b_{m}φ_{m}) = 0 implies that a_{1} = … = a_{l} = 0 or b_{1} = … = b_{m} = 0, we need to find out whether f_{1}(a_{1}, …, a_{l}, b_{1}, …, b_{m}) = … = f_{s−1}(a_{1}, …, a_{l}, b_{1}, …, b_{m}) = 0 yields the same implication. Thus we have to check whether the ideal (Y_{1}, …, Y_{l}) ∩ (Z_{1}, …, Z_{m}) = (Y_{λ}Z_{μ})_{λ=1..l,μ=1..m} is contained in the radical of (f_{1}, …, f_{s−1}), a condition which can be decided by standard computer algebra techniques (cf. e.g. [GTZ], sect. 9).

Our second method is based on a result of D. Eisenbud (cf. [Ei], 1.1).

Remark 8.4. For ν = 1, …, s − 1 we let ℭ_{ν} = (c_{λμν})_{λ=1..l,μ=1..m}, and we denote by M the subspace of Hom_{K}(K^{m}, K^{l}) generated by ℭ_{1}, …, ℭ_{s−1}. Then we let M^{⊥} be the subspace of Hom_{K}(K^{l}, K^{m}) which is dual to M w.r.t. the trace map, i.e. the space

M^{⊥} = {𝔇 ∈ Hom_{K}(K^{l}, K^{m}) | tr(𝔇ℭ_{1}) = … = tr(𝔇ℭ_{s−1}) = 0}.

Obviously M^{⊥} can be computed by solving a system of linear equations. Let 𝔇_{1}, …, 𝔇_{lm−s−1} be a K-basis of M^{⊥}. We introduce new variables Y_{1}, …, Y_{lm−s−1} and let 𝔐 = 𝔇_{1}Y_{1} + ⋯ + 𝔇_{lm−s−1}Y_{lm−s−1} be the matrix of linear forms associated to M^{⊥} (cf. [Ei], sect. 1). By [Ei], 1.1, we have to check whether (M^{⊥})_{1} = 0, i.e. whether the ideal of 2 × 2-minors of 𝔐 has radical (Y_{1}, …, Y_{lm−s−1}). Again this is a straightforward task using standard techniques.

Thus we are able to check i-uniformity in case i is of the form i = s − H_{𝕏}(j) with j ∈ {0, …, σ_{𝕏}}. Notice that this means, in particular, that we can check the uniform position property. Finally, we are left with the general case. Let i ∈ {Δ_{𝕏}, …, s−1}, and write i = s−H_{𝕏}(j)+k with j ∈ {0, …, σ_{𝕏}} and k ∈ {0, …, H_{𝕏}(j)−H_{𝕏}(j−1)−1}. Using Remark 8.3 or Remark 8.4, we first check whether 𝕏 is (s − H_{𝕏}(j))-uniform. Suppose this is the case. Then, for each subscheme 𝕐 ⊆ 𝕏 consisting of s − H_{𝕏}(j) points, we have H_{𝕐} = min{H_{𝕏}, deg 𝕐}, and we have to check whether 𝕐 is k-uniform. Since the Hilbert function of 𝕐 is H_{𝕐} = min{H_{𝕏}, H_{𝕏}(j)}, we have Δ_{𝕐} = H_{𝕏}(j) − H_{𝕏}(j − 1) and k < Δ_{𝕐}, so that we can check 𝕐 for k-uniformity by applying Remark 8.2.

Let us end this section by showing how one can apply the described methods in a concrete example.

Example 8.5. Let 𝕏 ⊆ ℙ_{K}^{3} be a set of 24 randomly chosen points, where K = \overline{ℚ} and “randomly” means that the coordinates of the points of 𝕏 are random integers between, say, 0 and 100. Suppose a calculation of the Hilbert function H_{𝕏} yields the expected result H_{𝕏} : 1 4 10 20 24 24 ⋯, and we want to check the uniformity of 𝕏. Of course, we expect 𝕏 to be in uniform position.

For checking Δ_{𝕏} = 4-uniformity, it suffices to find the separators of 𝕏 via the Buchberger-Möller algorithm, and to compute the \binom{24}{4} = 10, 626 maximal minors of the resulting 4 × 24-matrix (cf. Remark 8.2). It follows that the multiplication map R_{3} ⊗ (ω_{R})_{−3} ⟶ (ω_{R})_{0} is biinjective (cf. [K1], 3.1). Furthermore, we can easily check whether 𝕏 is in linearly general position (cf. [K1], sect. 4) by computing another \binom{24}{4} = 10, 626 determinants of 4 × 4-matrices made up from the coordinates of the points of 𝕏. By [K1], 4.2, we then know that the multiplication map R_{1} ⊗ (ω_{R})_{−1} ⟶ (ω_{R})_{0} is biinjective.

Thus we are left with checking the biinjectivity of the multiplication map R_{2} ⊗ (ω_{R})_{−2} ⟶ (ω_{R})_{0}. After finding the minimal homogeneous presentation of ω_{R} as outlined in sections 4 to 6, we calculate the (dim_{K} R_{2})(dim_{K}(ω_{R})_{−2})(s − 1) = 3220 coefficients c_{λμν} as explained above. From those we get 23 quadratic polynomials f_{ν}(Y_{1}, …, Y_{10}, Z_{1}, …, Z_{14}), and we have to check whether the 140 polynomials Y_{λ}Z_{μ} are in the radical of (f_{1}, …, f_{23}). This is achieved by computing a Gröbner basis of (f_{1}, …, f_{23}) degree by degree and checking at each stage which of the polynomials (Y_{λ}Z_{μ})^{ν} are already contained in it.

The reader may compare this with the naïve method, where we would have to find 2^{24} = 16, 777, 216 Hilbert functions of subsets of 𝕏.

References

[BG] M. Boratynski and S. Greco, Hilbert functions and Betti numbers in a flat family, Ann. di Mat. Pura e Appl. (IV) 142 (1986), 277–292

[BM] B. Buchberger and H.M. Möller, The construction of multivariate polynomials with preassigned zeros, Computer Algebra, EUROCAM ’82, Conf. Marseille / France 1982, Lect. Notes Comput. Sci. 144 (1982), 24–31

[Eh] S. Ehbauer, Graduierte Syzygienzahlen von Punkten im projektiven Raum und Anwendungen, dissertation, Universität Bayreuth 1993

[Ei] D. Eisenbud, Linear sections of determinantal varieties, Amer. J. Math. 110 (1988), 541–575

[F] J. Fogarty, Algebraic families on an algebraic surface, Amer. J. Math. 90 (1968), 511–521

[G] W. Gröbner, Algebraische Geometrie II, B.I. Hochschultaschenbücher 737, Bibliographisches Institut, Mannheim 1970

[GKR] A.V. Geramita, M. Kreuzer, and L. Robbiano, Cayley-Bacharach schemes and their canonical modules, Trans. Amer. Math. Soc. 339 (1993), 163–189

[GW] S. Goto and K. Watanabe, On graded rings, I, J. Math. Soc. Japan 30 (1978), 179–213 [GTZ] P. Gianni, B. Trager, and G. Zacharias, Gröbner bases and primary decompo-

sition of polynomial ideals, J. Symbolic Comput. 6 (1988), 149–167

[H] J. Harris, The genus of space curves, Math. Ann. 249 (1980), 191–204

[K1] M. Kreuzer, On the canonical module of a 0-dimensional scheme, Can. J. Math. (to appear)

[K2] M. Kreuzer, Some applications of the canonical module of a 0-dimensional scheme, in: Proc. Conf. Zero-Dimensional Schemes, Ravello / Italy 1992 (to appear)

[L] A. Lorenzini, The minimal resolution conjecture, J. Algebra 156 (1993), 5–35 [M] H. Matsumura, Commutative ring theory, Cambridge University Press, Cam-

bridge 1986

[MF] D. Mumford and J. Fogarty, Geometric invariant theory, Ergebnisse der Mathematik 34, Springer, Berlin–Heidelberg–New York 1982

[MMM]M.G. Marinari, H.M. Möller, and F. Mora, Gröber bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Eng. Commun. Comput. 4 (1993)

[MR] F. Mora and L. Robbiano, Points in affine and projective spaces, in: Proc. Conf. Computational Algebraic Geometry and Commutative Algebra, Cortona / Italy 1991, Symp. Math. 34, Cambridge University Press, Cambridge 1993

[PS] D. Portelli and W. Spangher, Rees algebras and Gröbner bases, Comm. Algebra 18 (1990), 2177–2197

[Ri] J. Riordan, Combinatorial identities, J. Wiley & Sons, New York 1968

[R1] L. Robbiano, On the theory of graded structures, J. Symbolic Comput. 2 (1986), 139–170

[R2] L. Robbiano, Introduction to the theory of Gröbner bases, in: The Curves Seminar at Queen’s, Vol. V, Queen’s Papers in Pure and Appl. Math. 80, Queen’s University, Kingston 1988

[S] P. Schenzel, Über die freien Auflösungen extremaler Cohen-Macaulay Ringe, J. Algebra 64 (1980), 93–101

Authors’ Address.

Fakultät für Mathematik Universität Regensburg D-93040 Regensburg Germany