J. Symbolic Computation (2004) 11, 1–000

Algorithms for graded injective resolutions and local cohomology over semigroup rings

David Helm and Ezra Miller

Mathematics Department, Harvard University, Cambridge, MA, USA Mathematical Sciences Research Institute, Berkeley, CA, USA

(current address: School of Mathematics, University of Minnesota, Minneapolis, MN, USA)

(Received 22 March 2004)

Let Q be an affine semigroup generating ℤ^{d}, and fix a finitely generated ℤ^{d}-graded module M over the semigroup algebra k[Q] for a field k. We provide an algorithm to compute a minimal ℤ^{d}-graded injective resolution of M up to any desired cohomological degree. As an application, we derive an algorithm computing the local cohomology modules H_{I}^{i}(M) supported on any monomial (that is, ℤ^{d}-graded) ideal I. Since these local cohomology modules are neither finitely generated nor finitely cogenerated, part of this task is defining a finite data structure to encode them.

Contents

1 Introduction 2 Effective irreducible hulls 3 Computing with irreducible hulls 4 Computing injective resolutions 5 Sector partitions from injectives 6 Computing sector partitions 7 Computing local cohomology with monomial support References

1. Introduction

Injective resolutions are fundamental homological objects in commutative algebra. For general noetherian rings with arbitrary gradings, however, injective modules are so big, and injective resolutions so intractable, that effective computations are never made using them. But when the ring in question is an affine semigroup ring of dimension d, the natural grading by ℤ^{d} is substantially better behaved: ℤ^{d}-graded injective modules can be expressed polyhedrally and are therefore quite explicit. In this paper we provide algorithms to compute ℤ^{d}-graded injective resolutions over affine semigroups rings. Part of this task is finding a finite data structure to express the output.

As an application, we provide an algorithm to compute the local cohomology, supported

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 2004 Academic Press Limited

on an arbitrary monomial ideal, of a finitely generated ℤ^{d}-graded module over a normal affine semigroup ring. As far as we are aware, this is the first algorithm to compute local cohomology for any general class of modules over any class of nonregular rings.

Our motivation was to make a systematic study of conditions on a support ideal that cause the local cohomology of its ambient ring to have infinite Bass numbers. In particular, when does the local cohomology contain an infinite-dimensional vector subspace annihilated by a maximal ideal? A counterexample to Grothendieck’s conjectured answer of ‘never’ was provided by (Har70), and our motivation was to characterize when Grothendieck’s conjecture fails. That such infinite behavior occurs only in nonregular contexts suggested that we work over affine semigroup rings, which are among the simplest singular rings. We have not yet implemented the algorithms in this paper, as doing so would only be the first step to providing examples of the infinite-dimensional socle phenomenon: it still remains to find an algorithm computing the ℤ^{d}-graded socle degrees.

To make our context precise, let Q ⊂ ℤ^{d} be an affine semigroup, that is, a finitely generated submonoid of ℤ^{d}. We assume that Q is sharp, meaning that Q has no units, and that Q generates ℤ^{d} as a group. Consider the semigroup algebra k[Q] = ⨁_{a∈Q} k·{x^{a}} over a field k. The modules that concern us comprise the category M of ℤ^{d}-graded modules H = ⨁_{α∈ℤ^{d}} H_{α} for which there exists a bound independent of α on the dimensions of the graded pieces H_{α} as vector spaces over k. The injective objects in M are described in Section 2, and every finitely generated ℤ^{d}-graded module lies in M. Our main theorem concerning injectives is the following.

Theorem 1.1. Fix a finitely generated ℤ^{d}-graded module M over an affine semigroup ring k[Q] and an integer n ≥ 0. The first n stages in a minimal ℤ^{d}-graded injective resolution of M can be expressed in a finite, algorithmically computable data structure.

A more precise version, along with a pointer to the algorithms that do the job, is stated in Theorem 4.7. The data structure consists of a list of monomial matrices, as we define in Section 2, generalizing those for Q = ℕ^{d} in (Mil00). The idea of the algorithm in Theorem 1.1 is to do all computations using irreducible resolutions (Mil02) as faithful approximations to injective resolutions. Background on irreducible hulls is presented in Section 2; the algorithms for working with them constitute Section 3. The derivation of an algorithm for injective resolutions is then completed in Section 4.

Even more seriously than is the case with injective resolutions, a substantial part of building an algorithm to compute local cohomology is finding a finite data structure to express the output. Indeed, unlike injectives in our category M, and in stark contrast with the regular case (even without a grading (HS93, Lyu93)), the local cohomology H_{I}^{i}(M) often has neither a finite generating set nor a finite cogenerating set (Har70, HM03). This remains true even when M is finitely generated and I ⊆ k[Q] is a ℤ^{d}-graded ideal—that is, generated by monomials. Our solution is to decompose ℤ^{d} into tractable regions on which the local cohomology is constant.

Definition 1.2. Suppose H is a ℤ^{d}-graded module over an affine semigroup ring k[Q]. A sector partition of H is

1. a finite partition ℤ^{d} = · ⋃_{S∈S} S of the lattice ℤ^{d} into sectors, each of which is required to consist of the lattice points in a finite disjoint union of rational polyhedra defined as intersections of half-spaces for hyperplanes parallel to facets of Q; 2. a finite-dimensional vector space H_{S} for each sector S ∈ S, along with isomorphisms

H_{α} → H_{S} for all ℤ^{d}-graded degrees α ∈ S; and

3. vector space homomorphisms H_{S} ⟶^{x^{T −S}} H_{T} whenever there exist α ∈ S and β ∈ T satisfying β − α ∈ Q, such that for all choices of α and β, the diagram commutes:

x^{β−α} H_{α} ⟶ H_{β}

↓  ↓ x^{T −S} H_{S} ⟶ H_{T}

Write S ⊢ H to indicate the above sector partition. (The commutativity of the above diagram implies immediately that x^{S−S} is the identity, and that x^{R−T} x^{T −S} = x^{R−S}.)

The finite data structure of a sector partition S ⊢ H, including the spaces H_{S} and the maps x^{T −S}, clearly suffice to reconstruct H up to isomorphism. The second half of this paper is devoted to computing sector partitions for H when H = H_{I}^{i}(M) is a local cohomology module.

Theorem 1.3. For any finitely generated ℤ^{d}-graded module M over a normal semigroup ring k[Q] and any monomial ideal I, each local cohomology module H_{I}^{i}(M) has an algorithmically computable sector partition S ⊢ H_{I}^{i}(M).

Section 5 demonstrates how sector partitions arise for the cohomology of any complex of injectives over a normal semigroup ring. Algorithms for producing these sector partitions, particlularly the expressions of sectors as unions of polyhedral sets of lattice points, occupy Section 6. The proof of Theorem 1.3, by expressing local cohomology as the cohomology of a complex of injectives (algorithmically computed by Theorem 1.1) in the usual way, occurs in Section 7. That section also treats complexity issues. The main thrust is that for fixed dimension d, the running times of our algorithms are all polynomial in the Bass numbers of the finitely generated input module M and the number of facets of Q, times the usual factor arising from the complexity of Gröbner basis computation, where it occurs. If d is allowed to vary, then the numbers of polyhedra comprising sectors increase exponentially with d.

Theorem 1.3 allows the computation of many features of local cohomology modules. For example, Hilbert series simply record the vector space dimensions in each of the finitely many sectors S ∈ S. Our algorithms can actually calculate these dimensions without computing the maps in part 3 of Definition 1.2, making it easier to determine when (for example) H_{I}^{i}(M) is nonzero. Future algorithmic methods (currently open problems) include the calculation of associated primes and locations of socle degrees (even if there are infinitely many) using a sector partition as input. In particular, because of the finiteness of the number of polyhedra partitioning sectors, we believe that the socle degrees should lie along polyhedrally describable subsets of ℤ^{d}.

Historical context

There have been a number of recent algorithmic computations in local cohomology, such as those by Walther (Wal99) (based on abstract methods of Lyubeznik (Lyu93)), Eisenbud–Mustaţǎ–Stillman (EMS00), Miller (Mil00), Mustaţǎ (Mus00), and Yanagawa (Yan02). These and related papers fall naturally into a number of categories. For instance, the last three deal with ℤ^{d}-graded modules over polynomial rings in d variables; in particular, they compute local cohomology with support on monomial ideals. In contrast, the paper (EMS00) works with coarser gradings—but still with monomial support, while (Wal99) requires no grading at all. As the gradings used become coarser, the papers increasingly depend on Gröbner bases: the monomial ideal papers require very little (if any) Gröbner basis computation; the coarser gradings depend heavily on commutative Gröbner bases; and the nongraded methods rely on noncommutative Gröbner bases over the Weyl algebra.

Regardless of the methods, all of the above papers share one fundamental aspect: the base ring is regular (usually a polynomial ring, in the algorithmic setting). The reason for restricting to these rings is that local cohomology over them behaves in many respects like a finitely generated module, even though it usually fails to be finitely generated. For example, Lyubeznik (Lyu93) and Walther (Wal99) take advantage of the fact that local cohomology modules over regular rings are finitely generated (indeed, holonomic) over the corresponding algebra of differential operators, and that the algebra of differential operators of a regular ring is easily presented, at least in characteristic zero.

Generally speaking, our methods lie somewhere between the monomial and coarsely graded methods described above, relying on a mix of Gröbner bases and integer programming. The principle underlying our computation of injective resolutions is that one should attempt to recover entire ℤ^{d}-graded modules from their Q-graded parts. This idea originated for polynomial rings in (Mil98, Mus00, Mil00), was transfered in a restricted form to semigroup rings in (Yan01), and developed generally for semigroup-graded noetherian rings in (HM03). In the present context, the recovery of a module from its Q-graded part suggested that we compute injective resolutions via the irreducible resolutions of (Mil02).

Origins of the notion of sector partition can be seen in the Hilbert series formula for the local cohomology of canonical modules of normal semigroup rings (Ter99, Yan02), where the cellular homology was constant on large polyhedral regions of ℤ^{d}. The accompanying notion of straight module (Yan01, HM03) abstracted this constancy; in fact, our Theorem 5.2 is really a theorem about straight modules as in (HM03, Definition 5.1). In any case, once the injective resolution has been computed using irreducible resolutions, the sector partition for local cohomology requires the entire ℤ^{d}-graded structure of the injective resolution, and not just its Q-graded part.

Conventions and notation

In addition to the notation introduced thus far, we close this Introduction with a note on conventions. The semigroup Q is required to be saturated in Sections 5–7 because we do not know how to compute sector partitions in the unsaturated context (Remark 6.7). Other than the temporary saturation requirement in Section 3.2, the semigroup can be unsaturated in Sections 2–4. (Reminders of these conventions appear in each section).

The symbol x^{α} ∈ k[ℤ^{d}] denotes a Laurent monomial in the localization k[ℤ^{d}] of the semigroup ring k[Q]. The k-vector space spanned by {x^{α} | α ∈ T } for a subset T ⊆ ℤ^{d} will be denoted by k{T }. The k-subalgebra of k[ℤ^{d}] will be denoted by k[T].

The faces of Q are those subsets minimizing linear functionals on Q. The edges and facets are the faces of dimension 1 and codimension 1. To every face F corresponds a prime ideal P_{F} and a quotient affine semigroup ring k[F] = k{F }.

All modules in this paper are ℤ^{d}-graded unless otherwise stated. In particular, injective modules (defined in Section 5) are ℤ^{d}-graded injective, which means that they are usually not injective in the category of all k[Q]-modules. Two subsets S, T ⊆ ℤ^{d} have the difference set T − S = {β − α | α ∈ S and β ∈ T } ⊆ ℤ^{d}. This allows us to write the localization of M along a face F as the module M[ℤF] := M ⊗_{k[Q]} k[Q − F]. Homomorphisms N → N′ of modules are assumed to have ℤ^{d}-graded degree 0, so that N_{α} → N′_{α} for all α ∈ ℤ^{d}.

We assume in this paper that standard algorithmic calculations with finitely generated modules over k[Q] are available. In particular, we assume that the homology of any three-term (nonexact) sequence of finitely generated modules can be calculated, as can the submodule annihilated by a prime ideal of k[Q]. The ℤ^{d}-grading only makes these computations easier, and the results of all such algorithms are still ℤ^{d}-graded.

2. Effective irreducible hulls

In this section the affine semigroup Q need not be saturated. In the ℤ^{d}-graded category M from the Introduction, the injective modules have simple descriptions.

Definition 2.1. Let T ⊂ ℤ^{d} be closed under addition of elements of −Q, by which we mean T − Q ⊂ T. Then k{T } can be given the structure of a k[Q]-module by setting

x^{a}x^{β} = \{ \begin{matrix}x^{a+β} & if a + β ∈ T \\ 0 & otherwise. \end{matrix}

An indecomposable injective is any module of the form k{α + F − Q}, for some face F and α ∈ ℤ^{d}.

All such objects are injective in M, and every injective object of M is isomorphic to a finite direct sum of indecomposable injectives (MS03, Chapter 11). We shall work exclusively with objects in M. Thus the term “injective module” in the rest of this paper will refer to modules of the above type.

Injectives are infinitely generated. For computations, we therefore work with certain finitely generated approximations. A module N is called Q-graded if N equals its Qgraded part N_{Q} := ⨁_{a∈Q} N_{a}. A submodule N of a module N′ is an essential submodule if N intersects every nonzero submodule of N′ nontrivially; the inclusion N ↪ N′ is also called an essential extension. In particular, N must be nonzero.

Definition 2.2. An irreducible sum is a module that can be expressed as the Qgraded part J_{Q} of some injective module J. An irreducible hull of a Q-graded module N is an irreducible sum \overline{W} along with an essential extension N ↪ \overline{W}.

The existence of unique minimal injective resolutions (MS03, Corollary 11.35) includes the fact that every finitely generated module has an injective hull (that is, an inclusion into an injective that is an essential extension) that is unique up to isomorphism. Taking Q-graded parts yields immediately the following lemma.

Lemma 2.3. Every Q-graded module has an irreducible hull. It is unique up to isomorphism, and isomorphic to the Q-graded part of an injective hull of M.

We call the modules of Definition 2.2 irreducible sums because of the next lemma, which is (Mil02, Lemma 2.2). An ideal W is called irreducible if W can not be expressed as an intersection of two ideals properly containing it.

Lemma 2.4. A monomial ideal W is irreducible if and only if the Q-graded part of some indecomposable injective module J satisfies J_{Q} = \overline{W}.

Modules M are usually stored as data structures keeping track of their generators and relations—that is, as quotients of free modules. In the context of injective resolutions and local cohomology, storing M as a submodule of an irreducible sum is also useful. Our next definition specifies a data structure that precisely describes an irreducible sum \overline{W}.

Definition 2.5. Effective data for an irreducible sum \overline{W} = ⨁_{j=1}^{r} k\{α_{j} + F_{j} − Q\}_{Q} consist of:

1. an ordered r-tuple F_{1}, …, F_{r} of faces of Q; and

2. an ordered r-tuple α_{1}, …, α_{r}, where α_{j} ∈ ℤ^{d}/ℤF_{j} satisfies Q ∩ (α_{j} + ℤF_{j}) ≠ ∅.

An effective vector of degree a ∈ Q is an r-tuple (λ_{1}, …, λ_{r}) ∈ k^{r} such that λ_{j} = 0 whenever a ∉ α_{j} + F_{j} − Q. Concatenation of the respective face and degree data from two effective data yields their direct sum.

Note that the faces F_{j} need not be distinct. The condition α ∈ ℤ^{d}/ℤF takes care of the fact that two degrees α and α′ off by an element of ℤF give the same module k{α + F − Q} = k{α′ + F − Q}. Usually the α’s are recorded as elements of ℤ^{d}, since the quotient mod ℤF can be deduced from the face data. The condition Q ∩ (α + ℤF) ≠ ∅ ensures that k{α + F − Q} has nonzero Q-graded part. The condition on the λ’s simply requires each nonzero component to lie in a nonzero degree of the corresponding irreducible summand.

Definition 2.6. An effective irreducible hull of a Q-graded module M consists of effective data for \overline{W} plus a list of finitely many effective vectors in \overline{W} generating a submodule isomorphic to M.

An irreducible hull M ↪ \overline{W} is not quite dual to an expression F → M as a quotient of a free module. The generators of F have as their dual notion the face data F_{1}, …, F_{r}, which as abstract objects associated to M are known as cogenerators. Just as the degrees of the generators of F need to specified, so must the degree data for the cogenerators. However, the notion of effective vector for M as a submodule of \overline{W} is dual not to the notion of relation for M inside F, but rather to the notion of cogenerator for M. Relations for M are, in actuality, dual to the notion of cogenerators for the cokernel of M ↪ \overline{W}, which correspond to indecomposable summands in cohomological degree 1 of the minimal injective resolution of M; we dub these the correlations of M. Thus a presentation of M by generators and relations is dual to a presentation of M by cogenerators and correlations, whereas an irreducible hull presents M by generators and cogenerators.

3. Computing with irreducible hulls

Given a Q-graded module M in the usual way, via generators and relations, this section computes an irreducible hull M ↪ \overline{W} as well as the cokernel of this inclusion.

Calculating an effective irreducible hull of M is, by definition, equivalent to calculating an irreducible decomposition of M. Thinking of the case M = k[Q]/I for a monomial ideal I, this procedure is polyhedral in nature: it writes the set of monomials outside of I as a union of convex polyhedral regions whose facets are parallel to those of Q. The algorithm for computing an effective irreducible hull M ↪ \overline{W}, culminating in Proposition 3.7, does not require Q to be saturated.

Computing the cokernel, however, is strictly easier for saturated semigroups. The main point is the computation of generators for irreducible ideals. For saturated semigroups this is Proposition 3.14. The harder unsaturated case, in Proposition 3.16, relies on the computation of irreducible ideals over its saturation. To highlight the simplification in the saturated case, we state the main result of Sections 3.2–3.3 here.

Proposition 3.1. Generators and relations for M and \overline{W} /M are algorithmically computable from an effective irreducible hull M ↪ \overline{W} over any affine semigroup ring k[Q].

Proof. Generators for \overline{W} are already given, and relations for \overline{W} constitute a direct sum of irreducible ideals calculated as in Proposition 3.14 for saturated semigroups, and Proposition 3.16 in general. Since M is specified by its generators as a submodule of \overline{W}, the current proposition reduces to calculating submodules and quotients of modules presented by generators and relations. □

3.1. Effective irreducible hulls from generators and relations

This subsection does not require the affine semigroup Q to be saturated. The next two results make Algorithm 3.6 possible to state and easier to read. The notation ⟨y_{1}, …, y_{j}⟩ means ‘the k[Q]-submodule generated by the elements y_{1}, …, y_{j} in their ambient module’, and (0 :_{M} P_{F}) is the submodule of M annihilated by P_{F}.

Lemma 3.2. Suppose F has minimal dimension among faces of Q such that P_{F} is associated to M. Then the natural map (0 :_{M} P_{F}) to its localization (0 :_{M} P_{F})[ℤF] along F is an inclusion. Furthermore, we can find algorithmically a set B ⊂ (0 :_{M} P_{F}) of homogeneous elements that consitute a k[ℤF]-basis for (0 :_{M} P_{F})[ℤF].

Proof. The k[Q]-module (0 :_{M} P_{F}) is naturally a torsion-free k[F]-module, by minimality of dim F. Therefore (0 :_{M} P_{F}) includes into its localization along F, which must be a free k[ℤF]-module. Now use the following algorithm. □

Algorithm 3.3. (for Lemma 3.2) Choose any element of (0 :_{M} P_{F}) as the first basis vector y_{1} ∈ B. Having chosen y_{j}, let y_{j+1} be any element of (0 :_{M} P_{F}) whose image in (0 :_{M} P_{F})/⟨y_{1}, …, y_{j}⟩ generates a submodule of Krull dimension dim F (equivalently, the image of y_{j+1} has annihilator P_{F}). The algorithm terminates when the Krull dimension of the quotient (0 :_{M} P_{F})/⟨y_{1}, …, y_{j}⟩ is strictly less than dim F.

Lemma 3.4. In the situation of Lemma 3.2, the scalar factor on the (monomial) coefficient of y ∈ B in the unique k[ℤF]-linear combination of elements in B equaling any fixed element z ∈ (0 :_{M} P_{F}) can be computed algorithmically.

We present the proof as an algorithm.

Algorithm 3.5. (for Lemma 3.4) Let B(z) = {y ∈ B | deg(y) ≡ deg(z) (mod ℤF)}. The coefficient of y in z is zero if y ∉ B(z). Otherwise, find elements a and {a_{y} | y ∈ B(z)} in the face F such that a + deg(z) = a_{y} + deg(y) for all y ∈ B(z). By construction, {x^{a_{y}} ·y | y ∈ B(z)} is a k-basis for the degree a+deg(z) piece of (0 :_{M} P_{F}), and standard methods allow us to calculate the syzygy with x^{a} · z.

Write Γ_{F} N := Γ_{P_{F}} N = (0 :_{N} P_{F}^{∞}) for the set of elements in N annihilated by all high powers of P_{F}.

Algorithm 3.6.

input Q-graded module M given by a generating set G ⊂ M and relations output effective irreducible hull \overline{W} of M with effective vector set Λ indexed by G

initialize N := M \overline{W} := (\{\}, \{\}), the empty effective datum for the irreducible sum 0 λ_{g} := () for all g ∈ G; here () is the effective vector of length zero in \overline{W} i := 1

define (F_{1}, …, F_{s}) := an ordering of the faces of Q with dim(F_{i}) ≤ dim(F_{i+1})

while i ≤ s do

define F := F_{i}
B := k[ℤF]-basis for (0 :_{N} P_{F})[ℤF], as in Algorithm 3.3
while y ∈ B and g ∈ G do
if (0 :_{⟨g⟩} P_{F}) ≠ 0 in some degree a_{yg} ≡ deg(y) (mod ℤF)

then λ_{yg} := scalar coefficient of y on x^{a_{yg}−deg(g)} · g, as in Al-

gorithm 3.5

else λ_{yg} := 0 end if-then-else

end while-do redefine λ_{g} := concatenation of the two vectors λ_{g} and (λ_{yg})_{y∈B}, for g ∈ G

\overline{W} := \overline{W} ⊕ (#B copies of F, ℤ^{d}-degrees of vectors in B)
N := M/Γ_{F} M
i := i + 1

end while-do output \overline{W} along with Λ = \{λ_{g}\}_{g∈G}, where λ_{g} is in degree deg(g)

Proposition 3.7. Algorithm 3.6 outputs an effective irreducible hull of M, using generators and relations for M as input.

Proof. We must show that the homomorphism M → \overline{W} determined by G and Λ is well-defined and injective. More precisely: monomial combinations z of the generators of M are zero if and only if the corresponding monomial combinations z_{λ} of the λ_{g} are zero in \overline{W}; here, λ_{g} represents not a data structure but an element of \overline{W}.

The combination z is nonzero in M if and only if the submodule ⟨z⟩ ⊆ M generated by z has an associated prime. The associated prime is F := F_{i} if and only if the image of ⟨z⟩ in the succesive quotient N = M/Γ_{F}_{i−1}M intersects (0 :_{N} P_{F}) nontrivially (this in particular imlplies that (0 :_{N} P_{F}) is nonzero, so P_{F} is associated to M). This nontriviality of ⟨z⟩ ∩ (0 :_{N} P_{F}) is equivalent to having at least one of the terms monomial·g appearing in z be nonzero in the same (0 :_{N} P_{F}), because B is a basis for (0 :_{N} P_{F})[ℤF]. Finally, monomial·g is nonzero precisely when the corresponding element monomial·λ_{g} has nonzero coefficient in the appropriate summand of \overline{W}. □

Remark 3.8. Some alterations to Algorithm 3.6 may improve its running time.

1. It is possible to avoid taking the successive quotients N/Γ_{F} M at the redefine step. These quotients are designed to make Lemmas 3.2 and 3.4 apply, as well as to make N successively simpler. However, the cost of taking these quotients may not be worth it, since the final sentence of Lemma 3.2 holds even if F doesn’t have minimal dimension (so (0 :_{M} P_{F}) doesn’t include into its localization along F). In fact, both of Algorithms 3.3 and 3.5 still work in this more general setting.

2. Of the faces on the list (F_{1}, …, F_{s}), only those associated to M need to be tested. If desired, these faces can be detected using homological methods.

3. Instead of computing and working with (0 :_{M} P_{F}) for each face separately, one could work with the modules (0 :_{M} I_{c}) for each c, where I_{c} is the intersection of all primes P_{F} for faces F of dimension c.

3.2. Generators and relations from irreducible hulls: saturated case

In this subsection we assume that Q is saturated. Our goal is to compute relations on the generators for M that come as part of an effective irreducible hull M ↪ \overline{W}. As we shall see in the proof of Proposition 3.1, the computation essentially reduces to the case where M = \overline{W} is an indecomposable irreducible sum \overline{W}, so we are to determine the kernel of the surjection k[Q] → \overline{W}. More explicitly, given a face F and a degree a ∈ Q, we must find generators of

W := k{Q \ (a + F − Q)}  (3.1)

as an ideal in k[Q].

Since Q is saturated, there is a unique minimal set of oriented hyperplanes inside ℤ^{d} whose closed positive half-spaces in ℤ^{d} have intersection equal to Q. The map sending H ↦ H ∩Q gives a bijection from these hyperplanes to the facets of Q. Denote by H_{+} the closed positive half-space determined by an oriented hyperplane H, and by H_{+}^{∘} the open positive half-space. Thus H_{+}^{∘} is the complement of −H_{+} but can also be characterized as the lattice distance 1 translate of H_{+} in the positive direction.

Lemma 3.9. Given any face F of Q and any element a ∈ Q,

Q \ (a + F − Q) = ⋃_{H⊇F}(a + H_{+}^{∘}) ∩ Q.

Proof. We have a + F − Q = ⋂_{H⊇F} a − H_{+} because Q is saturated (recall F − Q = −(Q + ℤF)). Thus ℤ^{d} \ (a + F − Q) = ⋃_{H⊇F} a + H_{+}^{∘}. Now intersect with Q. □

Lemma 3.9 reduces the computation of generators for W as in (3.1) to the case where F is itself a facet, at least when Q is saturated. The next algorithm and two lemmas cover this case by producing some rational polytopes whose integer points do the job. For notation, ℝ_{+}F denotes the real cone generated by F in ℝ^{d} = ℝ ⊗ ℤ^{d}, and ℝH denotes the real span of a hyperplane H. Also, by a Q-set we mean a subset of ℤ^{d} closed under addition by elements of Q. A set G of vectors in ℤ^{d} generates a Q-set T if T = G + Q.

Lemma 3.10. Let G_{Q} be the zonotope that is the Minkowski sum of all primitive integer vectors along rays of Q. Then, for all α ∈ ℝ^{d}, the lattice points in α + G_{Q} generate (α + ℝ_{+}Q) ∩ ℤ^{d} as a Q-set.

Proof. Let β be a lattice point in α + ℝ_{+}Q. If there is no primitive integer vector ρ along a ray of Q such that β − ρ still lies in α + ℝ_{+}Q, then β ∈ α + G_{Q}. □

Algorithm 3.11.

input Q := a saturated semigroup H := one of the hyperplanes bounding Q a ∈ Q

output finite set B ⊂ Q such that the ideal ⟨x^{b} | b ∈ B⟩ equals k{(a + H_{+}^{∘}) ∩ Q} define G := the polytope G_{Q} in Lemma 3.10

F := H ∩ Q, a facet of Q Δ := the set of faces of Q intersecting F only at 0 ∈ Q

initialize B := {}, the empty subset of Q

while D ∈ Δ do

define B_{D} := lattice points in Minkowski sum ((a + ℝH) ∩ ℝ_{+}D) + G redefine B := B ∪ B_{D}

next D

end while-do output B

Lemma 3.12. Algorithm 3.11 computes generators for the ideal k{(a + H_{+}^{∘}) ∩ Q}.

Proof. Suppose b ∈ (a+H_{+}^{∘})∩Q. The intersection (b+ℝH)∩ℝ_{+}Q is a polyhedron whose bounded faces are precisely the polytopes (b+ℝH)∩ℝ_{+}D for D ∈ Δ, and whose recession cone is ℝ_{+}F. Therefore b ∈ b′ +ℝ_{+}F for some real vector b′ ∈ (b+ℝH)∩ℝ_{+}D and some face D ∈ Δ. Moreover, b′ lies in b′′ + ℝ_{+}D for some real vector b′′ ∈ (a + ℝH) ∩ ℝ_{+}D. Consequently, b lies in b′′ + ℝ_{+}(D + F), and therefore in b′′ + ℝ_{+}Q. Now x^{b} lies in the k[Q]-module generated by k{B_{D}}, by definition of G. □

Remark 3.13. Some alterations to Algorithm 3.11 may improve its running time.

1. Instead of computing just one polytope G = G_{Q} and Minkowski summing it to define every B_{D}, we could define B_{D} with G_{D+F} in place of G, for each face D ∈ Δ.

This might reduce the number of lattice points in B dramatically, but would require more computations as in Lemma 3.10.

2. Restricting to the maximal elements in Δ will speed things up.

Let us summarize the above algorithm and three lemmas. (See Section 7 for issues concerning the output of the algorithm in the following proposition, and post-processing for the purpose of reducing its complexity.)

Proposition 3.14. Generators of the irreducible ideal W = ker(k[Q] → \overline{W}) are algorithmically computable using as input an indecomposable effective irreducible sum \overline{W} over a normal semigroup ring k[Q].

Proof. Apply Algorithm 3.11 to each of the sets (a + H_{+}^{∘}) ∩ Q in Lemma 3.9. □

3.3. Generators and relations from irreducible hulls: unsaturated case

Now we return to the general case, where Q need not be saturated, and denote by Q^{sat} the saturation of Q. The basic idea for computing generators of irreducible ideals in k[Q] is to intersect (as k[Q]-modules) the submodule k[Q] ⊂ k[Q^{sat}] with the ideal W ⊆ k[Q^{sat}] output in the saturated case, Proposition 3.14. Then it remains to find the appropriate F -primary component of W as a k[Q]-module, where F is the unique face of dimension dim(\overline{W}) associated to \overline{W} (as a k[Q]-module).

Every module in Algorithm 3.15 is to be considered as a k[Q]-module—even those generated as k[Q^{sat}]-modules. Thus F is always a face of Q, and we consider F − Q as opposed to F − Q^{sat}. Note, however, that k{F − Q^{sat}} does equal the corresponding injective over k[Q^{sat}], even though F is a face of Q; subtracting Q^{sat} automatically saturates F.

Algorithm 3.15.

input Q := a semigroup, not necessarily saturated F := a face of Q

a ∈ Q

output B ⊂ Q such that ⟨x^{b} | b ∈ B⟩ equals the ideal k{Q \ (a + F − Q)} in k[Q] define \overline{V} := k\{Q^{sat} \ (a + F − Q^{sat})\}, an indecomposable irreducible over k[Q^{sat}]

V := the kernel of k[Q^{sat}] → \overline{V} output by Proposition 3.14 W := V ∩ k[Q], the intersection taken inside k[Q^{sat}] I := ⋂ {P_{D} | D is a facet of F }, an ideal in k[Q]

initialize B := degrees of the elements generating W

\overline{W} := k[Q]/W while (0 :_{\overline{W}} P_{F}) has a generator in some degree ≢ a (mod ℤF) do

define G := generators for (0 :_{\overline{W}} P_{F}) that lie in degrees ≢ a (mod ℤF) redefine B := B ∪ degrees of the elements in G

\overline{W} := \overline{W} /G define G′ := generators for Γ_{I} \overline{W}

redefine B := B ∪ degrees of the elements in G′

\overline{W} := \overline{W} /G′

end while-do

output B

Proposition 3.16. Algorithm 3.15 outputs generating degrees for k{Q \ (a + F − Q)}.

Proof. The module \overline{W} gets initialized as a quotient of k[Q^{sat}] with dimension dim(F) as a k[Q]-module. This much holds by the saturated version Proposition 3.14 applied to \overline{V}, and the preservation of dimension (Eis95, Proposition 9.2) for the module-finite ring extension k[Q] ⊆ k[Q^{sat}] applied to V. One part of the output is clear: the set ⟨x^{b} | b ∈ B⟩ generates the kernel of the map k[Q] → \overline{W} at every stage in the algorithm. The question is whether \overline{W} is the claimed indecomposable irreducible sum.

In the first redefine step, the annihilator of x^{a} ∈ \overline{W} remains P_{F}. Indeed, any element killed by P_{F} that generates a submodule containing a nonzero element in degree a must itself have degree congruent to a (modℤF). The second redefine step only kills elements with annihilators strictly larger than that of x^{a}; such elements can’t generate submodules containing x^{a}. Therefore, \overline{W} has only one associated prime P_{F} after each loop of whiledo, by dimension considerations.

When the loop terminates, the localization (0 :_{\overline{W}} P_{F})[ℤF] along F is indecomposable, being isomorphic to k\{a + ℤF \}. It follows that the kernel of the surjection k[Q] → \overline{W} is an irreducible ideal (Vas98, Proposition 3.1.7). We are done by Lemma 2.4, because k{a + F − Q}_{Q} is the only indecomposable irreducible sum for which the annihilator of x^{a} is P_{F}. □

Remark 3.17. Some alterations to Algorithm 3.15 may improve its efficiency.

1. The step \overline{W} := \overline{W} /Γ_{I} \overline{W} need not occur until the very last step before output. Its current placement is designed to speed the computation by simplifying \overline{W} in each loop, but the cost of taking the colon may not make up for it. Instead, the end of the algorithm can be replaced by:

while (0 :_{\overline{W}} P_{F}) has rank strictly larger than 1 over k[F] do

define G := generators for (0 :_{\overline{W}} P_{F}) lying in degrees ≢ a (mod ℤF) redefine B := B ∪ degrees of the elements in G

\overline{W} := \overline{W} /G

end while-do redefine B := B ∪ degrees of the generators of Γ_{I} \overline{W} output B

2. As in Remark 3.8, it is not necessary to compute all of (0 :_{\overline{W}} P_{F}) in the while-do loop. It suffices instead to let G be a basis for (0 :_{\overline{W}} P_{F})[ℤF]. This remark also holds for the reworked while-do loop in the previous item.

3. The set B can become rather redundant. Since the machine will have to keep a presentation of \overline{W} in memory, the algorithm could simply spit out the relations defining \overline{W} as a k[Q]-module at the very end, without keeping track of B at all.

4. Computing injective resolutions

In this section the semigroup Q is not required to be saturated. Our goal is the main result (Theorem 4.7) in the first half of the paper: an algorithm to compute injective resolutions of finitely generated modules over k[Q], in the ℤ^{d}-graded setting. That is, given generators and relations for a finitely generated ℤ^{d}-graded module M, we will compute an exact sequence 0 → M → J^{0} → J^{1} → ⋯ in which J^{i} is a ℤ^{d}-graded injective module for each i. Of course, we shall only say how to calculate up to some specified cohomological degree, as injective resolutions usually do not terminate. This will not pose a problem for our subsequent computation in Section 7 of local cohomology, which vanishes past cohomological degree d + 1 anyway.

The upshot is to reduce the computation of injective resolutions to finding irreducible hulls of finitely generated Q-graded modules and computing their cokernels, which we have already done in Section 3.

The data structures we employ for ℤ^{d}-graded injective resolutions are the matrices we introduce in the next definition.

Definition 4.1. A monomial matrix is a matrix of constants λ_{qp} along with

1. a vector α_{q} ∈ ℤ^{d} and a face F_{q} ∈ Q for each row, and

2. a vector α_{p} ∈ ℤ^{d} and a face F_{p} ∈ Q for each column

such that λ_{qp} = 0 unless F_{p} ⊆ F_{q} and α_{p} ∈ α_{q} + F_{q} − Q.

These monomial matrices generalize those in (Mil00), which were for Q = ℕ^{d}.

To any monomial matrix we can associate a map J ↦ J′ of injective modules in the following manner. Each row and column label gives the data of an indecomposable injective; we think of the row labels as giving summands of J and the column labels as giving summands of J′. To give a map from J to J′ is thus the same as giving a matrix of maps from the row indecomposables to the column indecomposables. Such a map k{α_{q} + F_{q} − Q} ↦ k{α_{p} + F_{p} − Q} is necessarily zero unless F_{p} ⊆ F_{q} and α_{p} ∈ α_{q} + F_{q} − Q. In the latter case it is determined by a single scalar λ_{qp}. Hence

\begin{matrix}⋮ & ⋮ \\ F_{q} & α_{q} \\ ⋮ & ⋮ \end{matrix}( \begin{matrix}⋯ F_{p} ⋯ \\ ⋯ α_{p} ⋯ \\ λ_{qp} \end{matrix} )

is a monomial matrix representing a map

⨁_{q} k{α_{q} + F_{q} − Q} ↦ ⨁_{p} k{α_{p} + F_{p} − Q}.

The component k{α_{q} + F_{q} − Q} ↦ k{α_{p} + F_{p} − Q} of this homomorphism takes x^{α} to λ_{qp}x^{α} for all α ∈ α_{p} + F_{p} − Q, and is zero elsewhere.

Note that in degree α, the map J_{α} ↦ J′_{α} given by a monomial matrix is obtained by deleting the rows and columns labeled by α_{p}, F_{p} such that α does not lie in α_{p} + F_{p} − Q. (This corresponds to ignoring those summands of J and J′ not supported at α.) Ignoring the labels on what remains gives us a matrix with entries in k, which defines the k-vector space map J_{α} ↦ J′_{α}.

Two monomial matrices represent the same map of injectives (with given decompositions into direct sums of indecomposable injectives) if and only if (i) their scalar entries are equal, (ii) the corresponding faces F_{r} are equal, where r = p, q, and (iii) the corresponding vectors α_{r} are congruent modulo ℤF_{r}.

Rather than compute directly with cumbersome, infinitely generated injectives, it is more convenient to approximate injective resolutions using irreducible sums.

Definition 4.2. An irreducible resolution of a Q-graded module M is an exact sequence 0 → M → \overline{W}^{0} → \overline{W}^{1} → ⋯ in which each \overline{W}^{j} is an irreducible sum.

Irreducible resolutions are approximations to injective resolutions; indeed, the Qgraded part of any injective resolution is an irreducible resolution (Mil02, Theorem 2.4). In particular, monomial matrices just as well represent homomorphisms of irreducible sums, as long as the degree labels α_{q} and α_{p} all can be chosen to lie in Q. The (apparent) advantage to irreducible resolutions over injective resolutions is their finiteness.

Corollary 4.3. For any finitely generated Q-graded k[Q]-module M, Propositions 3.1 and 3.7 inductively compute a minimal irreducible resolution \overline{W}. of M algorithmically.

Proof. Minimal irreducible resolutions have finite length (that is, they vanish in all sufficiently high cohomological degrees) by (Mil02, Theorem 2.4). The computability therefore follows from Propositions 3.1 and 3.7 by induction on the highest cohomological degree required. □

The next result demonstrates the precise manner in which irreducible resolutions approximate injective resolutions for computational purposes.

Proposition 4.4. Let M be a finitely generated module with minimal injective resolution J. and minimal irreducible resolution \overline{W}.. Suppose that every indecomposable summand in the first n cohomological degrees of J. has nonzero Q-graded part. Then M is Q-graded, and the data contained in the first n stages of \overline{W}. constitute a finite data structure for the first n cohomological degrees of J..

Proof. Every map in J. can be expressed using the finite data of a monomial matrix, and this data can be read immediately off the maps in \overline{W}.. □

If we can algorithmically determine a ℤ^{d}-graded shift of M so that the hypotheses of Proposition 4.4 are satisfied, then we can compute the minimal injective resolution of M up to cohomological degree n. This task requires a lemma, in which 𝔪 denotes the maximal ideal P_{{0}} generated by nonunit monomials in k[Q].

Lemma 4.5. Let J. be a minimal injective resolution of a finitely generated module M, and F a face of Q. If every indecomposable summand of Γ_{𝔪}J^{j+d−dim(F)} has nonzero Qgraded part, then every indecomposable summand of J^{j} isomorphic to a ℤ^{d}-graded shift of k{F − Q} has nonzero Q-graded part.

Proof. (HM03, Proposition 3.5), in the special case of an affine semigroup ring. □

Every indecomposable summand of Γ_{𝔪}J^{j} is a shift k{α − Q} of k{−Q}. Such an indecomposable injective has nonzero Q-graded part if and only if α ∈ Q. Our final lemma in this section describes the (standard) way to calculate the shifts α appearing in Γ_{𝔪}J^{j}. The number μ^{j,α}(M) of shifts k{α − Q} appearing as summands in cohomological degree j of the minimal injective resolution of M is called the j^{th} Bass number of M in degree α.

Lemma 4.6. Let F. be a free resolution of the residue field k. The Bass number μ^{j,α}(M) is effectively computable as the k-vector space dimension of H^{j}(F., M)_{α}.

Proof. This expression of Bass numbers as dimensions (over k) of Ext modules is standard; see (BH93, Chapter 3). The computability follows because we can calculate free resolutions, homomorphisms, and homology over k[Q]. □

Now we come to our central result. For notation, M(−a) denotes the ℤ^{d}-graded shift of M up by a, so that M(−a)_{b} = M_{b−a}.

Theorem 4.7. Fix a finitely generated k[Q]-module M and an integer i. There is an algorithmically computable a ∈ Q for which Propositions 3.1 and 3.7 inductively compute the minimal injective resolution of M(−a) through cohomological degree i + 1.

Proof. After using Lemma 4.6 to compute the Bass numbers of M up to cohomological degree i + 1 + dim(M), choose a so that the corresponding Bass numbers of M(−a) have ℤ^{d}-graded degrees lying in Q. At this point, M(−a) satisfies the hypotheses of Proposition 4.4 with n = i + 1, by Lemma 4.5. Now apply Corollary 4.3. □

5. Sector partitions from injectives

We turn now to sector partitions, for which we assume henceforth that the affine semigroup Q is saturated. As a prerequisite to producing sector partitions of local cohomology modules, we demonstrate in this section that injective modules admit sector partitions, as does the homology of any complex of injective modules.

Proposition 5.1. Suppose J = ⨁_{i=1}^{r} J_{i} is an injective module decomposed into summands J_{i} = k{α_{i} + F_{i} − Q}. For each subset A ⊆ {1, …, r} define S_{A} to be the set

S_{A} = {α ∈ ℤ^{d} | (J_{i})_{α} ≅ k for i ∈ A}

of all degrees in ℤ^{d} such that the summands of J nonzero in that degree are precisely those indexed by A. The sets S_{A} canonically determine a sector partition S(J) ⊢ J.

Proof. For each α ∈ ℤ^{d}, either (J_{i})_{α} = {0} or (J_{i})_{α} = k · x^{α}. Therefore S(J) is indeed a partition of ℤ^{d}. Now we must show that S_{A} is a finite union of polyhedra as in part 1 of Definition 1.2. The set α + F − Q of degrees is the set of lattice points in a polyhedron of the desired form because the half-spaces whose intersection is α + F − Q are bounded by hyperplanes parallel to facets of Q, by definition. These hyperplanes divide ℤ^{d} into finitely many disjoint regions (place the lattice points lying on each hyperplane in the region on the positive side of that hyperplane), each of which consists of the lattice points in a polyhedron of the desired form. Thus the complement ℤ^{d} \(α+F −Q) is the required kind of finite union. We conclude that S_{A} is a finite union of regions, each of which is an intersection of r polyhedral regions—one from each of the summands J_{i}.

For each index set A such that S_{A} is nonempty, define J_{S_{A}} ⊆ k^{r} to be the subspace spanned by the basis vectors e_{i} such that i ∈ A. Then for each degree α in S_{A}, the map J_{α} → J_{S_{A}} required by part 2 of Definition 1.2 can be taken to equal the zero map on (J_{i})_{α} for i not in A, and the map sending x^{α} to e_{i} on (J_{i})_{α} for i in A.

To define the maps x^{S_{B}−S_{A}} for index sets A and B such that S_{B} − S_{A} is nonempty, as in part 3 of Definition 1.2, it suffices to define the image of e_{i} for each i in A. We take x^{S_{B}−S_{A}}(e_{i}) = e_{i} if i is in B, and x^{S_{B}−S_{A}}(e_{i}) = 0 otherwise. Commutativity of the required diagram follows from the definition of the module structure on k{α_{i} + F_{i} − Q}. Specifically, for α ∈ S_{A} and β ∈ S_{B} with β − α ∈ Q, multiplication by x^{β−α} takes x^{α} to x^{β} in J_{i} for i ∈ B, and takes x^{α} to zero in J_{i} for i outside B. □

The sector partition in Proposition 5.1 descends to the cohomology H of any complex of injectives, via monomial matrices. The forthcoming sector partition of H is really determined canonically by J. (without its direct sum decomposition), even though the way we present things here makes it look like bases must be chosen. We chose this route because bases are good for computation, while uniqueness is immaterial.

Theorem 5.2. If H is a module that can be expressed as the (middle) homology of a complex J. : J′ → J → J′′ in which all three modules are injective, or all three modules are flat, then there is a sector partition S(J.) ⊢ H determined by J..

Proof. Choose direct sum decompositions to write

J′ = ⨁_{i=1}^{r′} J′_{i}, J = ⨁_{i=1}^{r} J_{i}, and J′′ = ⨁_{i=1}^{r′′} J′′_{i}.

Let Φ and Ψ be the monomial matrices representing the maps J′ ↦ J and J ↦ J′′, respectively. The sectors in the sector partition S(J′ ⊕J ⊕J′′) ⊢ J′ ⊕J ⊕J′′ are indexed by triples (A′, A, A′′) of subsets of {1, …, r′}, {1, …, r}, {1, …, r′′}, respectively, and automatically satisfy the polyhedrality condition in part 1 of Definition 1.2 by Proposition 5.1. We take S(J.) to partition ℤ^{d} into these sectors.

For each triple (A′, A, A′′) we have maps Φ_{A′}^{A} : J′_{S_{A′}} → J_{S_{A}} and Ψ_{A}^{A′′} : J_{S_{A}} → J′′_{S_{A′′}} whose monomial matrices are defined by deleting: row i′ of Φ for i′ not in A′; column i of Φ and row i of Ψ for i not in A; and column i′′ of Ψ for i′′ not in A′′. Let

H_{S_{A′,A,A′′}} = ker(Ψ_{A}^{A′′})/im(Φ_{A′}^{A}).  (5.1)

For any α in S_{A′,A,A′′}, we have a commutative diagram

\begin{matrix}J′_{α} & ⟶ & J_{α} & ⟶ & J′′_{α} \\ ↓ & & ↓ & & ↓ \\ J′_{S_{A′}} & ⟶^{Φ_{A′}^{A}} & J_{S_{A}} & ⟶^{Ψ_{A}^{A′′}} & J′′_{S_{A′′}} \end{matrix}  (5.2)

that induces the required isomorphism H_{α} ≅ H_{S_{A′,A,A′′}}. It is routine to check that the maps H_{S_{A′,A,A′′}} → H_{S_{B′,B,B′′}} induced from the corresponding maps on J′_{A′}, J_{A}, and J′′_{A′′} commute with this isomorphism. □

Once we have Theorem 5.2, the only step remaining to prove Theorem 1.3 is to exhibit H_{I}^{i}(M) as the homology of a complex of injectives.

Remark 5.3. The results in this section hold just as well for flat objects of M, which are Matlis dual to injective objects and hence isomorphic to finite direct sums of modules of the form k{α + F + Q} for some α in ℤ^{d} and some face F of Q (MS03, Chapter 11). For the proofs, simply apply Matlis duality to the results for injectives.

6. Computing sector partitions

Again letting Q be a saturated affine semigroup, the next task is actually computing the finitely many polyhedra whose lattice points comprise the sectors in the sector partition S(J) ⊢ J of an injective module. That is, we need to make Proposition 5.1 and its proof into an algorithm.

Since Q is saturated, there are unique primitive integer linear functionals τ_{1}, …, τ_{n} taking ℤ^{d} → ℤ, one for each facet of Q, such that Q = ⋂_{i=1}^{n}{τ_{i} ≥ 0} is the set of lattice points in the intersection of their positive half-spaces. The degrees on which indecomposable injectives are supported can be expressed in terms of these linear functionals, via the following identity:

α + F − Q = {β ∈ ℤ^{d} | τ_{i}(β) ≤ τ_{i}(α) whenever τ_{i}(F) = 0}.  (6.1)

In other words, F −Q is the intersection of the negative half-spaces for those functionals τ_{i} vanishing on F, and α + F − Q is simply a translate. By convention, we use the notation τ_{i}(β) ≤ ∞ to mean that there is no restriction on the value of τ_{i}(β). This allows a notation τ_{F} (α) ∈ (ℤ ∪ ∞)^{n} for the vector whose i^{th} coordinate satisfies

τ_{F} (α)_{i} = \begin{cases}τ_{i}(α) & if τ_{i}(F) = 0 \\ ∞ & otherwise. \end{cases}

The point is that a vector β ∈ ℤ^{d} lies in α + F − Q if and only if τ(β) ≤ τ_{F} (α), where

τ(β) = (τ_{1}(β), …, τ_{n}(β))

and the ‘≤’ symbol denotes componentwise comparison. We shall use the corresponding definitions of τ_{F} (α) and τ(β) for vectors α, β ∈ ℝ^{d} = ℝ ⊗ ℤ^{d}, so τ_{F} (α) ∈ (ℝ ∪ ∞)^{n}.

For the rest of this section, let

J = ⨁_{j=1}^{r} J^{j}, with J^{j} = k{α_{j} + F_{j} − Q},  (6.2)

be an injective module, and define

τ^{j} := τ_{F_{j}}(α_{j}) for j = 1, …, r.

Thus for i = 1, …, n the vector τ^{j} has i^{th} coordinate τ_{i}^{j} = τ_{F_{j}}(α_{j})_{i}, which equals either τ_{i}(α_{j}) or ∞, depending on whether τ_{i} vanishes on F_{j} or not. Even without calculating the set S(J) algorithmically, the vectors τ^{j} specify the map from ℤ^{d} to S(J), by definition. We record a precise version of this statement in the next lemma.

Lemma 6.1. A degree α ∈ ℤ^{d} lies in S_{A} if and only if A = {j ∈{1, …, r} | τ(α) ≤ τ^{j}}.

It remains to ascertain which sets S_{A} of lattice points are nonempty, and to determine the pairs A, B for which we must compute a map x^{B−A} : J_{A} → J_{B}. (The maps themselves, which are canonical, are constructed in the proof of Proposition 5.1.) For each functional τ_{i} there is a permutation w_{i} of {1, …, r} satisfying τ_{i}^{w_{i}(1)} ≤ ⋯ ≤ τ_{i}^{w_{i}(r)}. To simplify notation, we write τ̃_{i}^{ℓ} instead of τ_{i}^{w_{i}(ℓ)}. Also, set τ̃_{i}^{0} = −∞ and τ̃_{i}^{r+1} = ∞.

For fixed i, the parallel affine hyperplanes {τ_{i} = τ̃_{i}^{ℓ}}_{ℓ=1}^{r} divide ℤ^{d} into strips

{β ∈ ℤ^{d} | τ̃_{i}^{ℓ} + 1 ≤ τ_{i}(β) ≤ τ̃_{i}^{ℓ+1}}

for ℓ = 0, …, r. At most r + 1 of these strips are nonempty, because some of the hyperplanes may coincide. Also, the last few of the τ̃_{i}^{ℓ} will equal ∞; we interpret any strip where τ_{i}^{ℓ} = τ_{i}^{ℓ+1} = ∞ as empty, and ignore it.

Proposition 6.2. Let J be as in (6.2). For any fixed ℓ_{1}, …, ℓ_{n} ∈ {0, …, r}, the lattice points in the polyhedron

Δ(ℓ_{1}, …, ℓ_{n}) := ⋂_{i=1}^{n}{β ∈ ℝ^{d} | τ̃_{i}^{ℓ_{i}} + 1 ≤ τ_{i}(β) ≤ τ̃_{i}^{ℓ_{i}+1}}

all lie inside a single sector in S(J). The partition of ℤ^{d} by the polyhedra Δ(ℓ_{1}, …, ℓ_{n}) refines the partition of ℤ^{d} by the sectors in S(J).

Proof. This follows from the definitions and (6.1), which uses that Q is saturated. □

Proposition 6.2 makes way for an algorithm to compute the set of sectors.

Algorithm 6.3.

input J = ⨁_{j=1}^{r} J^{j}, an injective module over k[Q], with J^{j} = k{α_{j} + F_{j} − Q} output the set S(J) of sectors, each expressed as a list of polyhedra that partition it define ϕ : ℤ^{d} → subsets of {1, …, r}, as in Lemma 6.1

initialize A := {}, the empty collection of subsets of {1, …, r}

while ℓ_{1}, …, ℓ_{n} ∈ {0, …, r} do

if Δ(ℓ_{1}, …, ℓ_{n}) ≠ ∅

then define A := ϕ(Δ(ℓ_{1}, …, ℓ_{n}))
else next (ℓ_{1}, …, ℓ_{n})

end if-then-else if A ∈ A

then redefine S_{A} := S_{A} ∪ {Δ(ℓ_{1}, …, ℓ_{n})} else initialize S_{A} := {Δ(ℓ_{1}, …, ℓ_{n})} redefine A := A ∪ {A}

end if-then-else next (ℓ_{1}, …, ℓ_{n})

end while-do output {S_{A} | A ∈ A}

Note that ϕ is constant on Δ(ℓ_{1}, …, ℓ_{n}) by definition, and can easily be determined directly from the data (ℓ_{1}, …, ℓ_{n}).

Next comes the determination of which maps x^{B−A} need computing. In the coming algorithm, we write Δ(ℓ_{1}, …, ℓ_{n}) ≤ Δ(ℓ′_{1}, …, ℓ′_{n}) if (ℓ_{1}, …, ℓ_{n}) ≤ (ℓ′_{1}, …, ℓ′_{n}) as vectors in (ℤ ∪ ∞)^{n}. Such notation is justified because Δ(ℓ_{1}, …, ℓ_{n}) ≰ Δ(ℓ′_{1}, …, ℓ′_{n}) automatically implies that Δ(ℓ′_{1}, …, ℓ′_{n}) − Δ(ℓ_{1}, …, ℓ_{n}) fails to intersect Q.

Algorithm 6.4.

input sectors S_{A} and S_{B} in S(J) from the output of Algorithm 6.3 output the truth value of: “there exist α ∈ S_{A} and β ∈ S_{B} with β − α ∈ Q”

initialize val := false

while (Δ_{A}, Δ_{B}) ∈ S_{A} × S_{B} and val = false, do if A ⊇ B and Δ_{A} ≤ Δ_{B}

then define Δ_{B} − Δ_{A} := the Minkowski sum of Δ_{B} and −Δ_{A}
else next (Δ_{A}, Δ_{B})

end if-then-else

if Q ∩ (Δ_{B} − Δ_{A}) ≠ ∅ then redefine val := true else next (Δ_{A}, Δ_{B})

end if-then-else end while-do

output val

The proof of correctness for Algorithm 6.4 is straightforward from the definitions, except for the first if-then-else procedure, which relies on Lemma 6.5, below. Note the non-necessity in Algorithm 6.4 of actually finding a witness in Δ_{B} − Δ_{A} for S_{A} ⪯ S_{B}; as we have seen in (5.1) and (5.2) from the proof of Theorem 5.2, the natural map on cohomology is induced by taking submatrices of the monomial matrix, regardless of where the witnesses lie.

Lemma 6.5. If S(J) is as in Proposition 5.1, then Q ∩ (S_{B} − S_{A}) ≠ ∅ implies A ⊇ B.

Proof. If a ∈ Q and (J_{i})_{α} = 0, then (J_{i})_{a+α} = 0, so the set of summands nonzero in degree a + α can only be smaller. □

Unfortunately, Algorithm 6.4 is necessary, because Δ_{B} − Δ_{A} ≠ ∅ need not always hold when Δ_{A} ≤ Δ_{B}, as the example to come shortly demonstrates. It does seem, however, that the offending pairs of polytopes are usually “small”. For instance, we know of no examples where the lattice points in either polytope affinely span ℤ^{d}.

Example 6.6. Let Q be the subsemigroup of ℕ^{2} generated by (2, 0), (1, 1), and (0, 2). Name the faces of Q as 0, X, Y, Q, and set E_{F} = F − Q. Let

J = k{(0, 0) + E_{0}} ⊕ k{(0, 1) + E_{X}} ⊕ k{(0, 0) + E_{Y} }
⊕ k{(0, −1) + E_{X}} ⊕ k{(−2, 0) + E_{Y} },

with the summands labeled in order as J_{1}, …, J_{5}. Letting X be facet number 1 and Y be facet number 2, the arrays τ_{i}^{j} and τ̃_{i}^{ℓ} look like

( \begin{matrix}τ_{1}^{j} \\ τ_{2}^{j} \end{matrix} ) = ( \begin{matrix}0 & 1 & ∞ & −1 & ∞ \\ 0 & ∞ & 0 & ∞ & −2 \end{matrix} ) and ( \begin{matrix} & τ̃_{1}^{ℓ} \\ & τ̃_{2}^{ℓ} \end{matrix} ) = ( \begin{matrix}−∞ & −1 & 0 & 1 & ∞ & ∞ & ∞ \\ −∞ & −2 & 0 & 0 & ∞ & ∞ & ∞ \end{matrix} )

The sectors S_{{1,2,3}} and S_{{2,3}} contain one polytope each, and both of these polytopes contain exactly one lattice point. Specifically, identifying the sector, the polytope, and the lattice point, we have

S_{{1,2,3}} = Δ(−1, −2) = (0, 0)  and  S_{{2,3}} = Δ(0, −2) = (−1, 1).

Now Δ(−1, −2) ≤ Δ(0, −2), but subtracting the vector in S_{{1,2,3}} from the one in S_{{2,3}} yields (−1, 1), which does not lie in the semigroup Q.

Remark 6.7. The notion of sector partition ought to have a refinement that takes into account the various kinds of failures of saturation for arbitrary affine semigroup. The resulting notion would produce sector partitions for the cohomology of complexes of injectives over nonnormal affine semigroup rings. The failures of saturation fall into two categories: the geometric kind, arising from polyhedral “holes” in the semigroup (as compared with its saturation), and the arithmetic kind, arising from finite-index sublattices generated by faces. Even in the case where arithmetic failure is absent, however, we do not know how to bound the sizes and shapes of the “holes” sufficiently to carry out an analysis such as the one producing the algorithms above.

7. Computing local cohomology with monomial support

Still assuming that Q is sturated, we have now finally developed enough tools to prove the main theorem on local cohomology with monomial support, namely Theorem 1.3 from the Introduction.

Proof of Theorem 1.3. Take i = d in Theorem 4.7, and let J.(−a) be the minimal ℤ^{d}-graded injective resolution computed there. Then J. is an algorithmically computed injective resolution of M. By definition, H_{I}^{i}(M) is the middle cohomology of the complex Γ_{I} J^{i−1} → Γ_{I} J^{i} → Γ_{I} J^{i+1}, where Γ_{I} J^{j} is the direct sum of all indecomposable summands of J^{j} whose unique associated prime contains I. Having now expressed H_{I}^{i}(M) as the cohomology of an effectively computed complex of injectives, Theorem 5.2 says that H_{I}^{i}(M) has a sector partition. The set of sectors in part 1 of Definition 1.2 is computed by Algorithm 6.3. The vector spaces in part 2 of Definition 1.2 are specified in (5.1) from the proof of Theorem 5.2, and naturally determine the maps in part 3 of Definition 1.2, given the computation in Algorithm 6.4. □

Now we turn to issues of complexity. There is little sense in completing a formal complexity analysis of all of the algorithms presented in this paper, as they involve Gröbner basis computation, which is doubly-exponential from a worst-case perspective. However, it is worth mentioning where the complexity in our algorithms comes from, up to a factor arising from the complexity of Gröbner basis computation, since Gröbner basis computations are often more efficient than expected. The purpose of what follows, therefore, is to assure the reader that our algorithms have not amplified the faux-doubly-exponential complexity of Gröbner bases with some “honest” exponential complexity.

Let us assume that the dimension d is fixed, and analyze the complexity of computing all of the local cohomology of a finitely generated module M supported on a fixed monomial ideal I over a normal semigroup ring k[Q]. This computation involves all of the algorithms in the paper except the one in Section 3.3. (The complexity of Algorithm 3.15 above and beyond Algorithm 3.6 is only about as bad as that of k[Q^{sat}]/k[Q] as a k[Q]-module, anyway.)

In Algorithm 3.6, the only non-Gröbner contribution to the running time comes from the number of basis elements constructed (see Remark 3.8.2, which can be used to ensure that we only check faces of Q giving rise to basis elements). This number is by definition a Bass number of M. Thus, up to Gröbner basis computation, Algorithm 3.6 is only as complex as its output.

Next we consider the algorithm in Proposition 3.14. The algorithm works by taking the union (over a set of facets of Q) of ideals output by Algorithm 3.11. The output presents the generators of each such ideal as the lattice points in a union of polytopes having the form ((a + ℝH) ∩ ℝ_{+}D) + G, where D is a face of Q. The computation of each such polytope is by standard techniques to intersect polyhedra and take Minkowski sums with the fixed zonotope G. Hence, up to factors coming from the number of facets of Q and from standard procedures, we need only bound

1. the number of polytopes output by Algorithm 3.11, and

2. the number of lattice points in each such polytope.

The former is polynomial in the number of facets of Q by Remark 3.13.2. The latter is polynomial in the input vector a ∈ Q by the piecewise polynomiality of the lattice point enumeration function of (a + ℝH) ∩ ℝ_{+}D as a function of a (McM77), along with the fact that G is fixed. Actually computing the set of lattice points in each polytope can be accomplished using the efficient algorithms of Barvinok and Woods (BW02).

Remark 7.1. We need to do Gröbner basis computations with the irreducible ideals W output by the algorithm in Proposition 3.14. This means that, for our purposes, the short rational generating functions output by the algorithms of (BW02) do not suffice: we actually require the list of lattice point explicitly, to get a generating set of W as a list of monomials. Thus the short generating functions must be expanded. To reduce complexity, the short generating functions can be post-processed using the methods of (BW02) to yield short generating functions for the minimal generators of the ideals W in question. Then we can expand only these “minimal” short generating functions.

The remaining contributions to the complexity of our local cohomology computation come from Algorithm 6.3, which computes the sets of polytopes whose disjoint unions constitute the sectors, and Algorithm 6.4. The latter is quadratic in the output of Algorithm 6.3, times a factor coming from the Minkowski sum operations and the decision procedure for whether each such sum contains a lattice point after intersecting with Q. Therefore it remains only to analyze Algorithm 6.3.

Proposition 7.2. The number of polyhedra arising in Algorithm 6.3 is polynomial in the Bass numbers of M and the number of facets of Q.

Proof. Each Bass number of M represents an indecomposable injective module whose bounding hyperplanes subdivide ℝ^{d} into a number of regions. Consider the subdivision of ℝ^{d} obtained by taking simultaneously all of the hyperplanes corresponding all of the Bass numbers of M. The number of hyperplanes contributed by each Bass number is at most the number of facets of Q, so the total number of hyperplanes is at most the number of facets of Q times the sum of the contributing Bass numbers. It is well known (and follows by induction on n and the dimension d) that n hyperplanes subdivide ℝ^{d} into a number of regions that is a polynomial in n of degree d. □

This proof shows that the number of polyhedra is exponential in the dimension. Exponential growth as a function of dimension also occurs in the analysis before Remark 7.1, where we apply (McM77).

Remark 7.3. A large number of rational polyhedra arise in the course of computing local cohomology modules. When the identification of all the lattice points in these polyhedra is necessary, the complexity of this task should be drastically reduced by the fact that most of these polyhedra have facets parallel to those of Q itself. Results such as those in (BV97) could be helpful along these lines.

Acknowledgments

We wish to thank Gennady Lyubeznik, who motivated us to make our previously abstract methods algorithmic. Both authors were partially supported by the National Science Foundation.

References

Winfried Bruns and Jürgen Herzog, Cohen–Macaulay rings, Cambridge Studies in Advanced Mathemat-

ics, vol. 39, Cambridge University Press, Cambridge, 1993. Michel Brion and Michèle Vergne, Residue formulae, vector partition functions and lattice points in

rational polytopes, J. Amer. Math. Soc. 10 (1997), no. 4, 797–833. Alexander Barvinok and Kevin Woods, Short rational generating functions for lattice point problems,

J. Amer. Math. Soc., to appear. arXiv:math.CO/0211146 David Eisenbud, Commutative algebra, with a view toward algebraic geometry, Graduate Texts in Math-

ematics, vol. 150, Springer-Verlag, New York, 1995, first printing. David Eisenbud, Mircea Mustaţǎ, and Mike Stillman, Cohomology on toric varieties and local cohomol-

ogy with monomial supports, J. Symbolic Comput. 29 (2000), no. 4-5, 583–600. Robin Hartshorne, Affine duality and cofiniteness, Invent. Math. 9 (1969/1970), 145–164. David Helm and Ezra Miller, Bass numbers of semigroup-graded local cohomology, Pacific J. Math. 209

(2003), no. 1, 41–66. Craig Huneke and Rodney Sharp, Bass numbers of local cohomology modules, Trans. Amer. Math Soc.

339 (1993), 765–779. Gennady Lyubeznik, Finiteness properties of local cohomology modules (an application of D-modules to

commutative algebra), Invent. Math. 113 (1993), no. 1, 41–55. P. McMullen, Valuations and Euler-type relations on certain classes of convex polytopes, Proc. London

Math. Soc. (3) 35 (1977), no. 1, 113–135. Ezra Miller, Alexander duality for monomial ideals and their resolutions, math.AG/9812095, 1998. Ezra Miller, The Alexander duality functors and local duality with monomial support, J. Algebra 231

(2000), 180–234. Ezra Miller, Cohen–Macaulay quotients of normal semigroup rings via irreducible resolutions, Math.

Res. Lett. 9 (2002), no. 1, 117–128. Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra, version of 30 July 2003 (currently

available at http://math.umn.edu/˜ ezra), in progress. Mircea Mustaţǎ, Local cohomology at monomial ideals, J. Symbolic Comput. 29 (2000), no. 4-5, 709–720. Naoki Terai, Local cohomology modules with respect to monomial ideals, preprint, 1999. Wolmer V. Vasconcelos, Computational methods inn commutative algebra and algebraic geometry, Al-

gorithms and Computation in Mathematics, vol. 2, Springer-Verlag, Berlin, 1998, With chapters by David Eisenbud, Daniel R. Grayson, Jürgen Herzog and Michael Stillman.

Uli Walther, Algorithmic computation of local cohomology modules and the cohomological dimension of

algebraic varieties, J. Pure Appl. Algebra 139 (1999), 303–321. Kohji Yanagawa, Sheaves on finite posets and modules over normal semigroup rings, J. Pure Appl.

Algebra 161 (2001), no. 3, 341–366. Kohji Yanagawa, Squarefree modules and local cohomology modules at monomial ideals, Local cohomol-

ogy and its applications (Guanajuato, 1999), Lecture Notes in Pure and Appl. Math., vol. 226, Dekker, New York, 2002, pp. 207–231.