Minimal resolutions of lattice ideals and integer linear programming

Minimal Resolutions of Lattice Ideals and Integer Linear Programming Emilio Briales-Morales Dpto de ´ Algebra Universidad de Sevilla E-mail: [email protected] ∗ Antonio Campillo-L´opez Dpto de ´ Algebra Geometr´ıa y Topolog´ıa Universidad de Valladolid E-mail: [email protected] Pilar Pis´on-Casares Dpto de ´ Algebra Universidad de Sevilla E-mail: [email protected] † Alberto Vigneron-Tenorio Dpto de Matem´aticas Universidad de C´adiz E-mail: [email protected] ‡ Dedicated to Professor J.L. Vicente on his sixtieth birthday. Abstract A combinatorial description of the minimal free resolution of a lattice ideal allows us to the connection of Integer Linear Programming and Algebra. The non null reduced homology spaces of some simplicial complexes are the key. The extremal rays of the associated cone reduce the number of variables. Keywords : Resolutions, simplicial complex, syzygy, lattice ideal, regularity, Integer Linear Programming, Hilbert bases, Gr¨ obner bases 2000 Mathematics Subject Classification:Primary 13D02, 14M25; Secondary 13P10, 68W30, 90C27 Introduction The objective of this paper is to describe how Integer Linear Programming allows us to obtain the minimal free resolution of a lattice ideal, I, from the generators of the semigroup, S, which parametrizes the associated algebraic variety. Concretely, Hilbert bases of some diophantine systems are employed. These bases are the solution of the typical Integer Linear Programming Problem, but the mini- ∗Supported by MCyT Spain, BFM2000-1523, and Junta de Andaluc´ıa, FQM304. †Supported by MCyT Spain, BFM2000-1523, and Junta de Andaluc´ıa, FQM304. ‡Supported by MCyT Spain, BFM2000-1523, and Junta de Andaluc´ıa, FQM304. 2Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 mality with respect to a cost map is not imposed. Recall that this typical problem is: min{c·x|Ax =b, x ∈Nn}, where Ais an integer matrix, ban integer vector and ca real vector (c·xis the cost map). Anybody who has solved linear diophantine equations in non negative integers, even with the more recent methods (see [18], [20], [23], [44] and [46]), knows that only in the case of a few variables the problem is tractable. It is well-known that this problem is NP-complete (see for example [37]). Therefore, from the computational viewpoint, our description is not practical in order to obtain the minimal free resolution. However, the method can be used to the contrary. Our description allows the understanding of the relation between the syzygies of the ideal and Integer Linear Programming. One can compute with Gr¨obner bases using for example the Schreyer Theorem and its improvements (see [33]), and look for applications to Integer Programming. This philosophy comes from [19] and [46], and provides a lot of applications in [50]. For example, the typical Integer Linear Programming Problem can be solved computing the reduced Gr¨obner basis of an associated lattice ideal. Or for instance, the Graver basis ([28]) of an ideal can be obtained from a reduced Gr¨obner basis of its Lawrence lifting, which is its unique minimal generating set. Nevertheless, at the moment this philosophy has only been employed in the case of the ideal I, but not the syzygies of the higher order (the ideal can be considered as the syzygies of order zero). Our description yields the generalization. As in [30] and [48], the combinatorial objects we use are simplicial complexes. Concretely, for any element of the semigroup S, we associate two simplicial complexes. The elements in the semigroup represent the degrees of the syzygies, in fact, the minimal free resolution is S-graded. The study of the non null reduced homology spaces of the simplicial complexes provides the concept of i-triangulation. This concept is the key in order to understand the relation between Integer Linear Programming and Algebra, concretely, between Hilbert bases and ith syzygies. By means of a partition of the generating set of S, the number of variables is reduced to the number of extremal rays of the associated cone. This is another possible point to continue researching. A generator over each extremal ray is chosen. Fixing the attention on this subset of generators, a new resolution is considered, the minimal free resolution of Iover a polynomial ring with only the variables corresponding to these generators. We begin in section 1 with the definition of the algebraic objects we employ. In section 2 we give the combinatorial description of the two minimal free resolutions. Section 3 is dedicated to the i-triangulations in a simplicial complex and some applications. The exposition of how to compute both resolutions with Gr¨obner bases is in section 4. All these sections include the results we have already obtained using the techniques this paper describes. For details the reader may also want to consult the reference joined to the concrete result. 3 Another possible application of our description is in Toric Geometry. The normal toric varieties [26], and more generally, the non-normal toric varieties [27] and [50], appear as algebraic varieties whose ideals are lattice ones. Among our results can be found descriptions of the regularity of these ideals as well as upper bounds for the degree of their generators. It is expected that there is some relation between these results and the conjetures of [24] and [50] (see also [49] and [39]). For a survey of the modern developments in the theory of toric varieties see [21]. Some applications of this theory to the Arithmetic and Integer Programming can be found in [17]. The hull resolution is another free resolution of a lattice ideal. This resolution is a generalization of the results for generic lattice ideals in [2] and [38]. It was introduced in [5] using Integer Programming. The study of the minimality of this resolution is a current research objective (see [3] where the case of unimodular lattice ideals is considered, and [36] for the monomial curves in the affine space of low dimension). On the other hand, it is known that any binomial ideal is an intersection of cellular ideals [25]. The cellular ideals are closely related to the lattice ideals. Using the cellular decomposition of a binomial ideal, it is possible to obtain information about the binomial ideal from the properties of the lattice ideals (for example, primary decomposition or nilpotence index, see [34] and [35]). 1 The two minimal free resolutions associated with a lattice ideal Let kbe a commutative field and k[X] = k[X1, . . . , Xn] the polynomial ring in n indeterminates, and the ideal m= (X1, . . . , Xn). Let L ⊂ Znbe a lattice. The ideal of the lattice Lis IL=hXu+−Xu−|u∈ Li, where u=u+−u−,u+, u−∈Nn,have disjoint support. Let Sbe a cancellative commutative semigroup, with zero element and generated by nelements Λ = {m1, . . . , mn}. Thus, Sis a subsemigroup of a finitely generated abelian group. Denote G(S) the smallest group containing S. The semigroup kalgebra is k[S] = Lm∈Skχm,(χm·χm0=χm+m0). The ideal of Srelative to Λ is ker(ϕ0), where ϕ0is the k-algebra morphism ϕ0:k[X]−→ k[S] defined by ϕ0(Xi) = χmi.Notice that ϕ0is surjective, and hence k[S]≃k[X]/ker(ϕ0). If ILis the ideal of the lattice L ⊂ Zn, then ILis the ideal of the subsemigroup of Zn/Lgenerated by {e1+L, . . . , en+L}, where the ei’s are the unit vectors. On the other hand, the ideal of any semigroup Srelative to a generating set Λ is the ideal of the lattice {u= (u1, . . . , un)∈Zn|Puimi= 0}(see [52] for details). 4Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 From now on, we fix a lattice Lor equivalently a semigroup S. Assume that L ∩ Nn= (0), or equivalently S∩(−S) = (0). Let Ibe the ideal relative to a fixed generating set Λ = {m1, . . . , mn}of S. Notice that Iis S-graded because ϕ0is an S-graded morphism of degree zero, considering k[S] with the natural S-grading and k[X] as an S-graded ring, assigning the degree mito Xi. The condition S∩(−S) = (0) says that k[X]m, the homogeneous elements of degree m∈Sin k[X], is a k-vector space of finite dimension (see [8]). Another application of the condition S∩(−S) = (0), is Nakayama’s lemma for Sgraded k[X]-modules (see [8]). Thus, there exists an S-graded minimal free resolution of k[S], which is unique up to isomorphism. We denote such a resolution by 0→k[X]bpϕp → · · · → k[X]b2ϕ2 →k[X]b1ϕ1 →k[X]ϕ0 →k[S]→0, and let Ni= ker(ϕi) be the ith module of syzygies 0 ≤i≤p(N0=I). Notice that bi+1 = dim(Ni/mNi), where Ni/mNiis considered as a k-vector space. Moreover, since this space is Sgraded, if Vi(m) := (Ni/mNi)m, where m∈S, then bi+1 =X m∈S dimVi(m). The Auslander-Buchbaum theorem guarantees that p=n−depthk[X]k[S], where depthk[X]k[S] is the depth of k[S] as k[X]-module. It is known that depthk[X]k[S] is bounded by dimk[S], which is the rank of the abelian group G(S). In the case the bound is reached, k[S] is a Cohen-Macaulay ring. Thus, this case will be called CohenMacaulay case. On the other hand, if S6={0}, it is satisfied that depthk[X]k[S]≥1. Assume that rank(G(S)) = d, let V=G(S)NZQ, and let C(S) be the cone generated by the image ¯ S, of Sin V. The cone C(S) is strongly convex because S∩(−S) = (0).Thus, if fis the number of extremal rays of C(S), then f≥d. This implies that there exists a set E⊂Λ with ]E =f, such that C(E) = C(S),where C(E) is the cone in Vgenerated by E. Fix such a set E. The Apery set Qof Srelative to Eis defined as Q={q∈S|q−e6∈ S, ∀e∈E}. Denote k[E] the subalgebra of k[S], k[E] = M m∈SE kχm, where SEis the subsemigroup of Sgenerated by E. Let k[XE] be the polynomial ring in the findeterminates associated with E.k[XE] can be projected over k[E], it is enough to associate to the indeterminate Xithe symbol χmi, for any mi∈E. 5 k[S] is a k[E]-module, and therefore also a k[XE]-module. The set {χq|q∈Q}, is a minimal system of generators of k[S] as k[E]-module, and therefore, also as k[XE]- module. Since k[E]⊂k[S] is an integral extension and k[S] is finitely generated as a k[E]-algebra, k[S] is finitely generated as a k[E]-module. So k[S] is a finitely generated k[E]-module, and Qis a finite set. Suppose that β0=]Q,Q={q1, . . . , qβ0}, and consider Φ0:k[XE]β0−→ k[S] defined by Φ0(ei) = χqi,1≤i≤β0. We can consider the S-graded minimal resolution of k[S] as k[XE]-module 0→k[XE]βqΦq → · · · → k[XE]β2Φ2 →k[XE]β1Φ1 →k[XE]β0Φ0 →k[S]→0, which is unique except isomorphisms. Let Mi= ker(Φi) be the ith module of syzygies of k[S] as k[XE]-module, 0 ≤i≤q. As before, by S-graded Nakayama’s lemma, we obtain βi+1 =X m∈S dimWi(m), where Wi(m) := (Mi/mEMi)mis consider as a k-vector space, and mEis the ideal of k[XE] generated by the indeterminates of XE(Xisuch that mi∈E). The Auslander-Buchbaum theorem guarantees that q=f−depthk[XE]k[S], where depthk[XE]k[S] is the depth of k[S] as k[XE]-module. Using the combinatorial descriptions of the above two resolutions in the following section, and the theorem 4.1 in [13], one gets that depthk[X]k[S] = depthk[XE]k[S]. Therefore, p≥q. Now, we will call the S-graded minimal free resolution of k[S] as k[X]-module the long resolution, and the short resolution the S-graded minimal free resolution of k[S] as k[XE]-module. 2 Combinatorial description of the resolutions Assume that S6= (0), and consider the S-graded minimal free resolution, 0→k[X]bpϕp → · · · → k[X]b2ϕ2 →k[X]b1ϕ1 →k[X]ϕ0 →k[S]→0. 6Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 For any m∈S(or even m∈G(S)) we define (inspired in some graphs of [47]) the simplicial complex : ∆m={F⊂Λ|m−nF∈S}, where nF=Pm0∈Fm0. Let e Hi(∆m) be the k-vector space of the ith reduced homology of ∆m, and ˜ hi(∆m) = dim( ˜ Hi(∆m)). There exists an effective isomorphism (∗)˜ Hi(∆m)≃Vi(m), for any m∈Sand for any i, 1 ≤i≤n−2, (for details see [14],[16] and [7], or also [1]). These isomorphisms are a bridge between Combinatorics and Algebra. For example, notice that the numbers biin the long resolution can be described by the following formula bi+1 =X m∈S ˜ hi(∆m). Another example, k[S] is Cohen Macaulay if and only if one has e Hn−d(∆m) = 0 for every m∈S, where d= rank G(S). If k[S] is Cohen Macaulay then the Cohen Macaulay type τk[X]of k[S] is given by τk[X]=X m∈Se hn−d−1(∆m). Thus, in particular, k[S] is Gorenstein if and only if k[S] is Cohen Macaulay and if e Hn−d−1(∆m)6= 0 exactly for one mfor which, moreover, one has e hn−d−1(∆m) = 1. The formula for τk[X]follows from the fact that τk[X]=bn−din the Cohen Macaulay case. Moreover, it is possible to generalize the well known characterization of Gorensteiness for numerical semigroups due to Kunz [32]. To state the result, notice that for m∈G(S)−S, ∆mis the empty simplicial complex and therefore one has ˜ Hi(∆m) = 0 for such an mand i≥ −1. Also notice that ∆0is the only complex among the ∆m’s with the property ˜ H−1(∆m)6= 0 (in fact it is a one dimensional space). Finally set ˜ Hi(∆m) = 0 for i∈Z,i < −1, and m∈G(S). From the symmetry of the graded resolution in the Gorenstein case, if Ris Gorenstein and let m∈Sbe the element such that ˜ Hn−d−1(∆m)6= 0, then for any couple of elements m1, m2∈G(S) with m1+m2=mand i∈Zone has ˜ Hi(∆m1)≃˜ Hn−d−i−2(∆m2) (see [7] for details). In the case of a numerical semigroup, let cbe the least element, such that m∈S for any m≥c.˜ Hi(∆m) = 0 for any m≥c+nΛ−1 and any i, because ∆mis the full simplex. Therefore, if Sis symmetric, the above isomorphism provides a symmetric property on the matrix {˜ hi(∆m)}i,m.(This particular case was proved in [14]) Another important application of these isomorphisms is the construction of minimal generating sets of syzygies. Notice that S(i) := {m∈S|e Hi(∆m)6= 0}, n −2≥i≥0, 7 is the set of S-degrees for the minimal i-syzygies. The notherian property guarantees that S(i) is a finite set, therefore the following construction provides a method for computing a minimal generating set of Ni. CONSTRUCTION: STEP 1: Compute S(i). STEP 2: For any m∈S(i), take the images of the elements in a basis for the ith reduced homology space ˜ Hi(∆m) by the isomorphism. Step 1 is completely solved in [12], but the partial solution for i= 0 appears in [8], and for i= 1 in [43]. Step 2 is solved with an algorithmic method in [7] (Remark 3.6). The case i= 0 corresponds to the ideal I=N0. In this case, step 1 is equivalent to determine the element m∈Ssuch that ∆mis non-connected. These elements are characterized by the concept of to be m-isolated ([16]) given by three arithmetical conditions. Concretely: Let m∈S, and let B={i1, ..., ip} ⊂ C⊂Λ, C6= Λ. We shall say Bis m-isolated from Λ −Cif: 1. It is possible to write m= p X j=1 γijnij=X t6∈C ρtnt, where γij,ρt∈N, and 0 < γijfor any j, 1 ≤j≤p. 2. If there exists m0∈Ssuch that it is possible to write m0= p X j=1 γ0 ijnij=X t6∈B ρtnt, with γ0 ij,ρt∈N,γ0 ij6= 0, and there exists t6∈ Csuch that ρt6= 0, then (γ0 i1, ..., γ0 ip)6<(γi1, ..., γip). 3. If B0={l1, ..., ls} ⊂ Band there exists m0∈Ssuch that it is possible to write m0= s X j=1 γ0 ljnlj=X t6∈B0 ρtnt, with γ0 lj,ρt∈N, and there exists t6∈ Csuch that ρt6= 0, then (γ0 l1, ..., γ0 ls)6≤ (γl1, ..., γls). We obtain the following result: Theorem 1 ([16]) Let m∈S, the following conditions are equivalents: 1: ∆mis non-connected ( ˜ H0(∆m)6= 0). 2: There exists C⊂Λ, such that: 8Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 •C=∪g j=1Tj. •Tjis m-isolated from Λ−C, for any j. •Tj∩Tj+1 6=∅, for any j, 1≤j≤g−1. This characterization allows us to find the particular solutions given for few generators in the numerical case in [29] (n=3), [6] and [40] (n=4), and [15] (n=5). Moreover, by means of new combinatorial elements, the theorem yields an algorithm. Concretely, the vertices of some ladders, or equivalently, the Hilbert bases of some diophantine systems are used. (See [8] for details) The case i= 1 is solved in [43] by construction of a finite set containing S(1). This set is obtained after studying the non-null spaces ˜ H1(∆m)6= (0).The concept of F-cavity in ∆mallows us to associate with Ssome diophantine systems. The Hilbert bases of these systems provide a check finite set. This technique is generalized in [12] for i≥2 . A new concept is necessary, the i-triangulation in ∆m. Now, consider the S-graded minimal free resolution of k[S] as k[XE]-module 0→k[XE]βf−1Φf−1 → · · · → k[XE]β2Φ2 →k[XE]β1Φ1 →k[XE]β0Φ0 →k[S]→0. This resolution can be described by means of other simplicial complexes ([13]). Concretely, if m∈S, let Tmbe the simplicial complex Tm={F⊂E|m−nF∈S}. Denote e Hi(Tm) the ith reduced homology space of the simplicial complex Tm, and let ˜ hi(Tm) = dim( ˜ Hi(Tm)). There exists an isomorphism (∗∗)˜ Hi(Tm)≃Wi(m), for any m∈Sand for any i, 1 ≤i≤f−2 (see [41]). As an application of these isomorphisms, if denote D(i) := {m∈S|e Hi(Tm)6= 0}, we obtain that βi+1 =X m∈D(i)e hi(Tm),0≤i≤f−2. Notice that, by the noetherian property, D(i) is finite. In [10] is shown how the sets D(i) can be obtained generalizing the techniques used for computing S(i) in [12]. This process will be recalled in the following section. Let A= Λ \E, ]A =n−f=r. A first application of the above formula is that S(i)⊂Ci, where Ci={m∈S|m=m+nF,with m∈D(t) and F⊂A, ]F =i−t, for some t≥ −1} (see [13]). Therefore, in order to determine the set S(i) it is enough to compute D(t) for any t,−1≤t≤min(i, f −2).Notice that this result allows us to construct the long resolution from the short one. 9 3i-Triangulations The objective of this section is to describe how the sets S(i), 0 ≤i≤n−2, and D(i), −1≤i≤f−2, can be obtained solving diophantine systems in non negative integers. Notice that D(−1) = Q, and since C(E) = C(S) for any element a∈Athere exists qa∈Nsuch that qa·a=X e∈E λe·e with λe∈N. Remark 1 Therefore, in order to obtain the set Q, one can do: 1. Compute the bounds qa,a∈A. 2. Determine the elements m=Pa∈Aλa·a, with λa∈Nand λa< qa. 3. Check whether the elements mare in Qusing Integer Linear Programming. Notice that one can compute the set Qsolving some diophantine equations in non negative integers, although this way is not practical. For solving the other cases, we need the concept of i-triangulation in a simplicial complex. Let ∆ be an abstract simplicial complex with vertices over a finite set V. The reduced i-homology of the simplicial complex ∆ is the k-vector space ˜ Hi(∆) = ˜ Zi(∆)/˜ Bi(∆), where ˜ Zi(∆) and ˜ Bi(∆) are the spaces of cycles and boundaries respectively. Let i≥0 and F⊂ V. We will say that τ={F1, . . . , Ft}is an i-triangulation of F if the following properties are satisfied: 1. ]Fj=i+ 1, ∀j= 1, . . . , t. 2. F=St j=1 Fj. We will say that τis an i-triangulation of Fin ∆, if Fj∈∆, ∀j= 1, . . . , t, and F /∈∆. If ˜ Hi(∆) 6= 0, then there is c∈˜ Zi(∆) −˜ Bi(∆), c=Pt j=1 λjFj, such that τ= {F1, . . . , Ft}is an i-triangulation of Fin ∆, for F=St j=1 Fj. In the cases ∆ = ∆mor Tm,V= Λ or Erespectively, if F⊂ V, and τ= {F1, . . . , Ft}is an i-triangulation of F, in ∆mor respectively in Tm, we can associate with τa diophantine system solution. Concretely, let Gbe the matrix whose columns are the chosen generators of S,G:= (m1|. . . |mn)∈ M(d+s)×n(Z),considering the 16 Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 References [1] A. ARAMOVA, J. HERZOG, Free resolution and Koszul homology. J. of Pure and Applied Algebra, 105(1) (1995), 1-16. [2] D. BAYER, I. PEEVA, B. STURMFELS, Monomial resolutions. Math. Res. Lett.,5, 1-2, (1998), 31-46. [3] D. BAYER, S. POPESCU, B. STURMFELS, Syzygies of unimodular Lawrence ideals. J. Reine Angew. Math. 534 (2001), 169–186. [4] D. BAYER, M. STILLMAN, A criterion for detecting m-regularity. Inventiones mathematicae, 87 (1987), 1-11. [5] D. BAYER, B. STURMFELS, Cellular resolutions of monomial modules. J. reine angew. Math.,502, (1998), 123-140. [6] H. BRESINSKY, Binomial generating sets for monomial curves, with applications in A4.Rend. Sem. Mat. Univers. Politecn. Torino,46(3), (1998), 353-370. [7] E. BRIALES, A. CAMPILLO, C. MARIJU´ AN, P. PIS ´ ON, Combinatorics of syzygies for semigroup algebra. Collet. Math.,49, 2-3, (1998), 239-256. [8] E. BRIALES, A. CAMPILLO, C. MARIJU´ AN, P. PIS ´ ON, Minimal Systems of Generators for Ideals of Semigroups. J. of Pure and Applied Algebra, 124 (1998), 7-30. [9] E. BRIALES, A. CAMPILLO, P. PIS´ ON, On the equations defining toric projective varieties. Geometric and Combinatorial Aspects of Commutative Algebra, Ed: Herzog/Restuccia, Marcel Dekker, 217-5, (2001), 57-66. [10] E. BRIALES, A. CAMPILLO, P. PIS´ ON, A. VIGNERON, Simplicial Complexes and Syzygies of Lattice Ideals. In Symbolic Computation: Solving Equations in Algebra, Geometry and Engineering, American Mathematical Society, Contemporary Mathematics, 286, (2001), 169-183. [11] E. BRIALES, P. PIS´ ON, A. VIGNERON, Cotas para la Regularidad de un Ideal de Ret´ıculo. Actas del Encuentro de Matem´aticos Andaluces. Servicio de publicaciones de la Univ. de Sevilla, (2002), 171-178. [12] E. BRIALES, P. PIS´ ON, A. VIGNERON, The Regularity of a Toric Variety. Journal of Algebra,237, (2001), 165-185. [13] A. CAMPILLO, P. GIM´ ENEZ, Syzygies of affine toric varieties. Journal of Algebra,225, (2000), 142-161. [14] A. CAMPILLO, C. MARIJU´ AN, Higher relations for a numerical semigroup. S´em. Th´eor. Nombres Bordeaux,3(1991), 249-260. 17 [15] A. CAMPILLO, P. PIS´ ON, Generators of a monomial curve and graphs for the associated semigroup. Bulletin de la Societe Mathematique de Belgique, V. 45, 1-2, Serie A, (1993), 45-58. [16] A. CAMPILLO, P. PIS´ ON, L’id´eal d’un semi-grupe de type fini. C. R. Acad. Sci. Paris, S´erie I,316, (1993), 1303-1306. [17] A. CAMPILLO, P. PIS´ ON, Toric Mathematics from semigroup viewpoint. Ring Theory and Algebraic Geometry, Ed: A. Granja, JA. Hermida and A. Verschoren. Series: Lectures Notes in Pure and Applied Mathematics, 221-5, (2001), 95-112. [18] M. CLAUSEN, A. FORTENBACHER, Efficent solution of linear Diophantine equations. Journal of Symbolic Computations,8, (1989), 201-216. [19] P. CONTI, C. TRAVERSO, Buchberger algorithm and integer programming. Proceedings AAECC-9 (New Orleans), Springer LNCS 539, (1991), 130-139. [20] E. COTEJEAN, H. DEVIE, An efficient Algorithm for solving systems of diophantine equations. Information and Computation,113(1), (1994), 143-172. [21] D. COX, Recent developments in toric geometry. Collection: Algebraic geometrySanta Cruz 1995,389-436, Proc. Sympos. Pure Math.,62, Part 2, Amer. Math. Soc., Providence, RI, (1997). [22] F. DI BIASE, R. URBANKE, An Algorithm to Calculate the Kernel of Certain Polynomial Ring Homomorphisms. Experimental Mathematics, Vol.4, No. 3 (1995), 227-234. [23] E. DOMENJOUD, Outils pour la D´eduction Automatique dans les Th´eories Associatives-Commutatives. Th´ese de doctorat d’Universit´e, Universit´e de Nancy I, (1991). [24] D. EISENBUD, S. GOTO, Linear free resolutions and minimal multiplicity. Journal of Algebra,88, (1984), 89-133. [25] D. EISENBUD, B. STURMFELS, Binomial ideals. Duke Mathematical Journal, 84, No. 1, (1996), 1-45. [26] W. FULTON, Introduction to Toric Varieties. Priceton University Press, (1993). [27] I. GELFAND, M. KAPRANOV, A. ZELEVINSKY, Discriminants, Resultants, and Multidimensional Determinants. Birkh¨auser, Boston Basel Berlin, (1994). [28] J.E. GRAVER, On the foundations of linear and integer programming I. Mathematical Programming 8(1975), 207-226. [29] J. HERZOG, Generators and Relations of Semigroups and Semigroup Rings. Manuscripta Math. 3, (1970), 175-193. 18 Algebraic Geometry and Singularities. Sevilla, September 19-22, 2001 [30] M. HOCHSTER, Cohen-Macaulay rings, combinatorics, and simplicial complexes. Lect. Notes in Pure and Appl. Math. Dekker 26, (1977), 171-223. [31] S. HOSTEN, B. STURMFELS, GRIN, An Implementation of Gr¨obner Bases for Integer Programming. In E. Balas and J. Clausen editors, Integer Programming and Combinatorial Optimization, LNCS 920, Springer-Verlag (1995), 267-276. [32] E. KUNZ, The value-semigroup of a one-dimensional Gorenstein ring. Proc. Amer.Math.Soc.,25, (1970), 748-751. [33] R. LA SCALA, M. STILLMAN, Strategies for Computing Minimal Free Resolutions. J. Symbolic Computation,26, (1998), 409-431. [34] I. OJEDA, R. PIEDRA, Cellular binomial ideals. Primary decomposition of binomial ideals. Journal Symbolic Computation,30(3), (2000), 383-400. [35] I. OJEDA, R. PIEDRA, Nullstellensatz for binomial ideals. J. of Algebra, 255(1), (2000), 135-147. [36] I. OJEDA, P. PIS´ ON, The hull Resolution of a monomial curve in A3(k). Prepublicaciones del Departamento de ´ Algebra de la Universidad de Sevilla,12, (2001). [37] C.H. PAPADIMITRIOU, On the complexity of integer programming. J. Assoc. Comput. Mach.,28, (1981), 765-768. [38] I. PEEVA, B. STURMFELS, Generic Lattice Ideals. Journal of the American Mathematical Society,11, 2, (1998), 363-373. [39] I. PEEVA, B. STURMFELS, Syzygies of codimension 2 lattice ideals. Mathematische Zeitschrift,229, (1998), 163-194. [40] P. PIS´ ON, M´etodos combinatorios en ´ Algebra local y Curvas monomiales en dimensi´on 4. Doctoral thesis, Universidad de Sevilla, (1991). [41] P. PIS´ ON, The short resolution of a lattice ideal. Proc. Amer.Math.Soc., to appear. [42] P. PIS´ ON-CASARES, A. VIGNERON-TENORIO, Computing Toric First Syzygies. International Conference IMACS-ACA, El Escorial, Madrid, Spain, (1999). [43] P. PIS´ ON-CASARES, A. VIGNERON-TENORIO, First Syzygies of Toric Varieties and Diophantine Equations in Congruence. Communications in Algebra, 29, 4, (2001). [44] P. PIS´ ON-CASARES, A. VIGNERON-TENORIO, N−solutions to linear systems over Z.Prepublicaci´on de la Universidad de Sevilla, Secci´on ´ Algebra,43, (1998). [45] P. PIS´ ON-CASARES, A. VIGNERON-TENORIO, On the Graver Bases of Semigroup Ideals. Prepublicaciones del Departamento de ´ Algebra de la Universidad de Sevilla, 10, (2001), 1-12. Preprint. 19 [46] L. POTTIER, Minimal solutions of linear diophantine systems: bounds and algorithms. Proceedings of the Fourth International Conference on Rewriting Techniques and Applications, In R:V: Book (ed.), Lectures Notes in Computer Science 488, Springer-Verlag, (1991), 162-173. [47] J.C. ROSALES, Semigrupos num´ericos. Doctoral thesis, Universidad de Granada, (1991). [48] R. STANLEY, Combinatorics and commutative algebra 2nd ed. Progress in Mathematics Vol.41, Boston Basel Berlin, Birkh¨auser, (1996). [49] B. STURMFELS, Equations defining toric varieties. Collection: Algebraic geometrySanta Cruz 1995,437-449, Proc. Sympos. Pure Math.,62, Part 2, Amer. Math. Soc., Providence, RI, (1997). [50] B. STURMFELS, Gr¨obner Bases and Convex Polytopes. AMS University Lectures Series, Vol. 8 (1995). [51] B. STURMFELS, Gr¨obner bases of Toric Varieties. Tˆohoku Math. J. 43 (1991), 249-261. [52] A. VIGNERON-TENORIO, Semigroup Ideals and Linear Diophantine Equations. Linear Algebra and its Applications, 295 (1999), 133-144. [53] A. VIGNERON-TENORIO, ´ Algebras de Semigrupos y Aplicaciones. Doctoral thesis, Universidad de Sevilla, (2000).