The regularity of a toric variety

The Regularity of a Toric Variety. E. Briales-Morales and P. Pis´on-Casares Departamento de ´ Algebra, Facultad de Matem´aticas, Apartado 1160, 41080 Sevilla (Spain). Fax: + 34 95 4556938. E-mail: [email protected], [email protected] and A. Vigneron-Tenorio Departamento de Matem´aticas, E.U.E. Empresariales, Por-Vera 54, 11403 Jerez de la Frontera (C´adiz, Spain). Fax: + 34 956 345104. E-mail: [email protected] We give a method computing the degrees of the minimal syzygies of a toric variety by means of combinatorial techniques. Indeed, we complete the explicit description of the minimal free resolution of the semigroup algebra associated, using the simplicial representation of Koszul homology appeared in [8]. As an application, we obtain an algorithm computing the Castelnuovo-Mumford regularity of a projective toric variety. This regularity is explicity bounded by means of the semigroup generators which parametrize the variety. Key Words: Toric varieties, syzygies, simplicial complexes, regularity. INTRODUCTION Let S⊂Zhbe a finitely generated commutative semigroup with zero element, such that S∩(−S) = {0}. Let {n1, . . . , nr} ⊂ Sbe a set of generators for S. Let kbe a field, let k[S] be the semigroup k−algebra associated to S, and let R=k[X1, . . . , Xr] be the polynomial ring in r variables. k[S] is obviously an S−graded ring, and Ris S−graded assigning the degree {ni}to Xi.Let mthe irrelevant ideal of R. The k−algebra 1 2E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO morphism, ϕ:R−→ k[S], defined by ϕ(Xi) = {ni},is an S−graded morphism of degree zero. Thus, the ideal IS=ker(ϕ) is an S−homogeneous ideal that it is called a Semigroup Ideal or a Toric Ideal because it defines a toric variety. The condition S∩(−S) = {0}guarantees the S−graded Nakayama’s lemma (Proposition 1.4 in [4]). Then, there exists a minimal S−graded free resolution of k[S]. Let Nibe the corresponding i-syzygy module (N0=I) and consider the k−vector spaces Vi(m) := (Ni)m (mNi)m , m ∈S. By Nakayama’s lemma: •A minimal generating set of Niconsists exactly of dimk(Vi(m)) elements of degree m, for each m. •The elements of degree min a minimal generating set of Ni, correspond with a basis of Vi(m). In particular, since Ris noetherian, one has Vi(m) = 0 for all mbut finite many of values. It is well-known that there exist methods using Gr¨obner Bases (Schreiyer’s Theorem) computing a minimal generating set of Ni(see for example [11]). However, we are interested in to understand combinatorially these generating sets, and therefore the minimal S−graded free resolution of k[S]. We introduced the following notation: Let Λ := {1, . . . , r}, and if F⊂Λ, nF=Pi∈Fni(n∅= 0). If m∈S, the set ∆m={F⊂Λ|m−nF∈S} is an abstract simplicial complex. These simplicial complexes appear for the first time in the literature in [8]. They are a generalization of some graphs defined in [20]. Although, both works are inside the context of numerical semigroups, actually ∆m appears in a lot of good papers inside more extensive contexts. For example, consider ˜ Hi(∆m) the k−vector space of the i-reduced homology. There exists an isomorphism (∗)˜ Hi(∆m)≃Vi(m). The existence of this isomorphism is proved in [8]. The generalization to a semigroup Swith our initial conditions appears in [10]. A such isomorphism is explicity constructed in [5]. Other very interesting papers inside this line THE REGULARITY OF A TORIC VARIETY 3 are [1], [7],[15]. The connection between free resolutions and simplicial complexes comes from [13] (see also [21] and [6]). Continuing with our problem. Notice that the previous isomorphism provides the following construction to obtain a minimal generating set for Ni. CONSTRUCTION: STEP 1: Find the set Ci:= {m∈S|˜ Hi(∆m)6= 0}of S−degrees for the minimal i-syzygies. STEP 2: For any m∈Ci, take the images of the elements in a basis for the i-reduced homology space ˜ Hi(∆m) by the isomorphism. Step 2 is solved with an algorithmic method in [5] (Remark 3.6). Thus, Construction will be an algorithm when one knows an effective way of computing the set Ci. In particular, since the set C0is arithmetically explicited in [10], this construction provides an algorithm for i= 0 (Toric/Semigroup ideals) by means of Integer Programming, [4]. Using a degree bound for the elements in C0, other alternative algorithm appears in [12]. In [9] new simplicial complexes associated to a partition of Λ allows the authors to deduce applications to concrete situations. However, they cannot compute the finite sets Ciin the general case. Indeed, they establish as the main problem in the computation of the minimal resolution to find finite sets C0 icontaining Ci. A finite set containing C1is effectively computed in [17]. Therefore, a new method computing the first syzygy module N1is obtained. Moreover, an explicit bound for the degree of the minimal first syzygies is given. This bound is described by means of the generators of the semigroups S. In this paper, we generalize the results in [17] to all of higher order syzygies (section 1). Therefore, we obtain a new method computing the minimal generating set of the syzygy modules because we solve effectively Step 1 in Construction. The results in this paper allow us to say that Construction is an algorithm. In this way, we complete the combinatorial description of the minimal S−graded free resolution of k[S] initiated in [8]. As an application, we consider the particular case of a projective toric variety (section 4). We obtain an algorithm computing its Castelnuovo- Mumford regularity. Without using this computation, we describe an explicit bound of the regularity by means of the semigroup generators which parametrize the variety. The key idea to find finite sets C0 icontaining Ciis the following: For any F⊂Λ and for any τtriangulation of Finto i-dimensional faces, we consider a diophantine linear system. The set C0 iis obtained as a union 4E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO of subsets of the Hilbert bases associated to all of these systems. C0 iis finite because the Hilbert bases are finite (Dickson’s lemma). C0 ican be computed in an effective way because there exist algorithms computing the Hilbert basis (see, for example, [16]). We can conclude that: the noetherian property of Ras well as Integer Programming guarantee the set Ciis finite, but Integer Programming provides also the way computing this finite set. 1. FINDING THE SET C I We consider, as in the introduction, S=< n1, . . . , nr>⊂Zha finitely generated semigroup with zero element such that S∩(−S) = {0}, the set Λ = {1, . . . , r}, and for any m∈Sthe simplicial complex ∆m={F⊂Λ|m−nF∈S}, where nF=Pi∈Fni.Given a field k,˜ Hi(∆m) is the k−vector space of the i-reduced homology. We are looking for a finite set C0 icontaining the set Ci:= {m∈S|˜ Hi(∆m)6= 0}. Recall that from the isomorphism (∗) in the introduction, Ciconsists exactly of the S−graded minimal i-syzygies for k[S], the semigroup k−algebra associated of S. Fix m∈S, choose an orientation on each face of ∆m, and consider the augmented chain complex with values in the field k. Let ˜ Ci(∆m) be the k−vector space generated freely by the i-dimensional faces of ∆m, where dimF=]F −1 (dim ∅=−1), and let δi:˜ Ci(∆m)→˜ Ci−1(∆m) the k−linear mapping given by δi(F) = X F0∈∆m,dimF0=i−1 F F 0F0, where F F 0= 0 if F06⊂ F, and F F 0=±1 if F0⊂F,F F 0= 1 if the orientation induced by Fon F0is equal to the orientation chosen on F0, and F F 0=−1 otherwise. We are interested in the link ˜ Ci+1(∆m)δi+1 →˜ Ci(∆m)δi →˜ Ci−1(∆m) with i≥2. Indeed, the tildes can be omitted. However we keep them because our results are true even if i≥0.Let ˜ Zi(∆m) = ker(δi) and ˜ Bi(∆m) = Im(δi+1) be the spaces of cycles and borders. Then, we have THE REGULARITY OF A TORIC VARIETY 5 that ˜ Hi(∆m) = ˜ Zi(∆m)/˜ Bi(∆m). Lemma 1.1. Suppose that ˜ Hi(∆m)6= 0, and let c∈˜ Zi(∆m)−˜ Bi(∆m), c=Pt j=1 λjFj,λj∈k− {0}for any j= 1, . . . , t,Fj6=Flif j6=l. Then, if F=St j=1 Fjone has that ∀p∈F∃q, 1≤q≤t|p /∈Fqand Fq∪ {p}/∈∆m. Proof. We begin proving that ∀p∈F∃j, 1≤j≤t, such that p /∈Fj. Suppose that p∈Fand p∈Fjfor any j, 1≤j≤t. Then, c0= Pt j=1 λjFjFj−{p}(Fj− {p})∈˜ Ci−1(∆m). Notice that c0= 0 because δi(c) = 0, and therefore λj= 0, ∀j= 1, . . . , t. But it is not possible because c6= 0. Fix p∈F. We can suppose that p /∈F1. If F1∪ {p}/∈∆mwe have finished. Suppose then that F1∪ {p} ∈ ∆m. Set l:= {j|p /∈Fj}and F0 1=F1∪ {p}. We consider c1:= c−λ1F0 1F1δi+1(F0 1). Notice that c1∈˜ Zi(∆m)− ˜ Bi(∆m). Moreover, c1= t X j=2 λjFj+X dim(F0)=i,F 06=F1 F1F0F0. Set c1=Pt(1) j=1 λ(1) jF(1) j, where λ(1) j∈k− {0}for any j= 1, . . . , t(1), F(1) j6=F(1) lif j6=l,l(1) := ]{j|p /∈F(1) j}, and F(1) := St(1) j=1 F(1) j. The following properties are satisfied (∗)1:]F(1) ≤F. (∗∗)1: If p /∈F(1) j, then there exists q, 2 ≤q≤tsuch that F(1) j=Fq. (∗ ∗ ∗)1:l(1) < l. Indeed, we replace the face F1in cwith p /∈F1, by several faces F06=F1 with p∈F0to construct c1. We proceed by induction on ]F. If ]F is minimal, in (∗)1the equality holds. Therefore, p∈F(1) and l(1) 6= 0. Using the similar arguments with c1, there exists j, 1 ≤j≤t(1), such that p /∈F(1) j. By (∗∗)1,F(1) j=Fqfor some q, 2 ≤q≤t. If F(1) j∪ {p}/∈∆m, we have finished. But, if F(1) j∪ {p} ∈ ∆m, we can 6E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO obtain c2∈˜ Zi(∆m)−˜ Bi(∆m) from c1, similarly to the construction of c1 from c. Set c2=Pt(2) j=1 λ(2) jF(2) jwhere λ(2) j∈k−{0}for any j= 1, . . . , t(2), F(2) j6=F(2) lif j6=l. Then, if l(2) := ]{j|p /∈F(2) j}, and F(2) := St(2) j=1 F(2) j we obtain the properties: (∗)2:]F(2) ≤F(1). (∗∗)2: If p /∈F(2) j, then there exists q, 2 ≤q≤t(1) such that F(2) j= F(1) q. (∗ ∗ ∗)2:l(2) < l(1). Again, in (∗)2the equality holds because ]F is minimal. Therefore p∈ F(2) and l(2) 6= 0. Now, our result follows by recurrence because the properties (∗∗∗) guarantees that this process must finish in a finite number of steps. Suppose then our result is true for any c0∈˜ Zi(∆m)−˜ Bi(∆m), c0= Pt0 j=1 λ0 jF0 jwhere λ0 j∈k− {0}for any j= 1, . . . , t0,F0 j6=F0 lif j6=l, with ]F0< ]F where F0=St0 j=1 F0 j. Then: If in (∗)1the equality does not hold, it is enough to apply the induction hypothesis to c1. We obtain that there exists F(1) jsuch that p /∈F(1) jand F(1) j∪{p}/∈∆m. By (∗∗)1,F(1) j=Fqwith 2 ≤q≤t, and we have finished. If in (∗)1the equality holds, we repeat the same argument that in the case ]F minimal. If we don’t finish, we construct c2as before. Again, we obtain the result by induction if in (∗)2the equality does not hold. Otherwise, we begin the process. We finish in a finite number of steps by the properties (∗∗∗) which are obtained in the recurrence. Now, our result is proved. Lemma 1.1 associates to m∈Swith ˜ Hi(∆m)6= 0 sets F⊂Λ and F1, . . . , Ft∈∆msuch that: 1. F=St j=1 Fj 2. dim(Fj) = i,∀j= 1, . . . , t 3. F /∈∆m Notice that τ={F1, . . . , Ft}is a triangulation of Finto i-dimensional faces of ∆m. This suggests the following definition. Definition 1.1. Let F⊂Λ. We say that τ={F1, . . . , Ft}is an i-triangulation of Fif the following properties are satisfies: 1. dim(Fj) = i,∀j= 1, . . . , t 2. F=St j=1 Fj THE REGULARITY OF A TORIC VARIETY 7 We say that τis an i-triangulation of Fin ∆m, with m∈S, if Fj∈∆m, ∀j= 1, . . . , t, and F /∈∆m. Lemma 1.2. If ˜ Hi(∆m)6= 0, there exists F⊂Λand τi-triangulation of Fin ∆m. Proof. It is enough to take c∈˜ Zi(∆m)−˜ Bi(∆m) and F, F1, . . . , Ftas in Lemma 1.1. Remark 1. 1. It is clear that given m∈Swith ˜ Hi(∆m)6= 0, Fis not unique in general. Moreover, for a fixed F, the i-triangulation τis not unique in general. Suppose that τ={F1, . . . , Ft}is an i-triangulation of Fin ∆m. Notice that the property F1∈∆mis equivalent to m−nF1∈S. This means that there exists αj∈Nsuch that m=Pr j=1 αjnj, with αj≥1 for any j∈F1. Set Athe matrix whose column vectors are the generators of S,A:= (n1|. . . |nr)∈ Mh×r(Z). Set eF1∈Nrthe vector with coordinates equal to zero, excepting the jth one which is equal to one, for any j∈F1. Then, F1∈∆mif and only if there exists α(1) ∈Nrsuch that Aα(1) =m, and α(1) eF1, where the symbol stands for the natural partial order in Nr. With similar notations we can obtain an analogous condition for Fj∈ ∆m. This is: for any j, 1≤j≤t,Fj∈∆mif and only if there exists α(j)∈Nrsuch that Aα(j)=m, and α(j)eFj. Set A(t) :=        A −A 0 0 0 0 0 0A −A 0 0 ··· 0 0 0 0 A −A 0 0 0 ......... 0 0 0 0 0 A −A        ∈ Mh(t−1)×rt(Z) and eτ:= (eF1, . . . , eFt)∈Nrt. Then, from τ, an i-triangulation of Fin ∆m, we can obtain a vector α= (α(1), . . . , α(t))∈Nrt which satisfies: 1. A(t)α= 0. 2. αeτ 8E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO 3. m=Aα(1) =. . . =Aα(t). But we cannot forget that we are looking for the m∈Ssuch that ˜ Hi(∆m)6= 0. Then, we must proceed on the contrary. Let F⊂Λ and τ={F1, . . . , Ft}an i-triangulation of F. Now, mis not fixed. We are going to look for the elements m∈Ssuch that τis an i-triangulation of Fin ∆m. As before, we consider eτ:= (eF1, . . . , eFt)∈Nrt. Set Rτ:= {α= (α(1), . . . , α(t))∈Nrt | A(t)α= 0 , α eτ}. Notice that if α∈Rτand it is written α= (α(1), . . . , α(t)) with α(j)∈ Nr, for any j, 1≤j≤t, it is obtained Aα(1) =. . . =Aα(t)=m∈S. Set ΣRτ:= {m∈S|m=Aα(1), α = (α(1), α(2), . . . , α(t))∈Rτ}. At the moment it is also known that if m∈Sis such that ˜ Hi(∆m)6= 0, using Lemma 1.1 we find Fand τas before such that m∈ΣRτ. Then, we obtain that Ci=[ F[ τ ΣRτ, where the union is over all of τi-triangulation of F, and F⊂Λ with ]F ≥i+ 2. (Notice that Fcomes from Lemma 1.1 and then ]F ≥i+ 2). The set ΣRτis not finite in general. Therefore, we have yet not found our set C0 i. However, Rτ,HRτ:= {α∈Rτ|αis minimal for } is finite. We are going to prove that Ciis contained in a union as before, but of subsets of ΣHRτ:= {m∈S|m=Aα(1), α = (α(1), α(2), . . . , α(t))∈ HRτ}. By this way, we construct our desired finite set C0 i. We need to introduce some new notation. On the elements of S, we define a partial order ≥S m≥Sm0⇔m−m0∈S If H⊂S, we shall say that m∈His S−minimal in Hif m≥Sm0with m0∈H, implies that m=m0. Set Cτ:= {m∈S|mis S−minimal in ΣRτ}. THE REGULARITY OF A TORIC VARIETY 9 Lemma 1.3. In the conditions as above, for any m∈ΣRτ, there exists m0∈Cτand m00 ∈Ssuch that m=m0+m00. Proof. If m∈Cτ, it is enough to take m0=mand m00 = 0. Otherwise, there exists m0 1∈ΣRτsuch that m≥Sm0 1. Then, m=m0 1+m00 1, with m00 1∈S. If m0 1∈Cτwe have finished. Otherwise, we begin the reasoning with m0 1. By recurrence we construct a sequence of elements m0 j−1=m0 j+m00 j, where m0 j∈ΣRτand m00 j∈S. The condition S∩(−S) = {0}guarantees that the number of different expressions of mas sum of non null elements in Sis finite (Proposition 1.2 in [4]). Then, our process must finish. Suppose that it finishes in the jth step. Then, m0 j∈Cτ. Now m= m0 j+m00 1+...+m00 j, hence it is enough take m0=m0 jand m00 =m00 1+. . .+ m00 j. Lemma 1.4. In the conditions as above, Cτ⊂ΣHRτ. Therefore, the set Cτis finite. Proof. Let m∈Cτ. Then, m=Aα(1) with α= (α(1), . . . , α(t))∈Rτ. If α∈ HRτ, we have finished. Suppose that α /∈ HRτ. Then α=α0+α00, with α0∈ HRτand α00 ∈Nrt. Moreover, α00 =α−α0satisfies that A(t)α00 = 0. Then, if m0=Aα0(1), m0∈ΣHRτ. By m−m0=m00 =Aα00(1) ∈Sand m is S−minimal, we obtain that m=m0∈ΣHRτ. Proposition 1.1. If m∈Sand ˜ Hi(∆m)6= 0, then there exists F⊂Λ with ]F ≥i+ 2, and there exists τi-triangulation of Fin ∆msuch that m∈Cτ. Proof. If ˜ Hi(∆m)6= 0, let c∈˜ Zi(∆m)−˜ Bi(∆m), c=Pt j=1 λjFj,λj∈k− {0} for any j= 1, . . . , t,Fj6=Flif j6=l. Then, if F=∪t j=1Fjand τ= {F1, . . . , Ft}, we have that τis an i-triangulation of Fin ∆mand m∈ΣRτ. By Lemma 1.3 m=m0+m00 with m0∈Cτand m00 ∈S. If m00 = 0, then m=m0∈Cτand we have finished. Suppose that m00 6= 0. Let m00 =Pr j=1 βjnjwith βj∈Nfor any j, 1≤j≤r. We can suppose that β16= 0. If 1 ∈F, we apply lemma 1.1 for p= 1. Then, there exists q, 1≤q≤t, such that 1 /∈Fqand Fq∪ {1}/∈∆m. However, m−nFq−n1∈Sbecause Fq∈∆m,β16= 0 and 1/∈Fq. This is a contradiction with Fq∪ {1}/∈∆m. Therefore, 1 /∈F. 16 E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO Notice that α∈ HRτif and only if α−eτ∈ H{β∈Nrt | A(t)(β+eτ)=0}. Set Aτ:= (A(t)| − A(t)eτ). We are looking for the relation with Hilbert basis of the homogeneous systems Aτβ0= 0, β0∈Nrt+1. It is easy to verify that H{β∈Nrt | A(t)β=−A(t)eτ}={β∈Nrt |(β, 1) ∈ H(Aτ)}. Lemma 3.1. With the notation and conditions as before, the following inequality is satisfied ||(α−eτ,1)||1≤(1 + 4||A||1,∞)h(di−1), being di:= r i+ 1 . Proof. Using the above reasoning we obtain that (α−eτ,1) ∈ H(Aτ). Then, by Remark 3.1 ||(α−eτ,1)||1≤(1 + ||Aτ||1,∞)s, where s=rank(Aτ). Recall that the matrix Aτhas h(t−1) columns, where ]τ =t,τ= {F1, . . . , Ft},Fj⊂F, and ]Fj=i+1, for any j. Then t=]τ ≤]F i+ 1 ≤ r i+ 1 =di, and rankAτ≤h(t−1) ≤h(di−1). Finally, let see us that ||Aτ||1,∞≤4||A||1,∞. It is enough to notice that ||A||1,∞=max1≤j≤t−1{||(A(2)| − A(2)(eFj, eFj+1 ))||1,∞} and ||(A(2)| − A(2)(eFj, eFj+1 ))||1,∞= THE REGULARITY OF A TORIC VARIETY 17 max1≤p≤h{ r X q=1 |apq|+ r X q=1 | − apq|+X q∈Fj |apq|+X q∈Fj+1 | − apq|} ≤ 4||A||1,∞ Theorem 3.2. If m∈Sis an S−degree of a minimal i-syzygy for k[S], then m=Axwith x∈Nrsuch that ||x||1≤(1 + 4||A||1,∞)h(di−1) + (i+ 1)di−1, where di=r i+ 1 . Proof. With the notation in Lemma 3.1, m=Aα(1) with α= (α(1), . . . , α(t)) satisfying this lemma. Now, it is enough to notice that ||α(1)||1≤ ||α||1=||α−eτ+eτ||1≤ ||α−eτ||1+||eτ||1=||(α−eτ,1)||1−1+(i+1)t. By Lemma 3.1, ||α(1)||1≤(1 + 4||A||1,∞)h(di−1) + (i+ 1)di−1. We are going to see how it is possible to improve Theorem 3.2 in the particular cases i= 0,1. Suppose i= 0. It is well-known that any minimal generating set for the ideal I(the 0-syzygies) is contained in the Graver basis of A,GrA GrA:= {Xα−Xβ|(α, β)∈ H(A(2))} (see [22] for details). Then, if m∈Sis a minimal degree of I, we obtain that m=Aα=Aβ, with (α, β)∈ H(A(2)). Using again Remark 3.1 we have that ||α||1≤(1 + 2||A||1,∞)h because ||A(2)||1,∞≤2||A||1,∞. This is clearly an improvement of Theorem 3.2 for the case i= 0. Suppose i= 1. As we have seen before, we can reduce to a special type of 1-triangulations of Fin ∆m, the F-cavities. All of them have the same shape, a polygon with ]F vertices. Thus, following the steps in the proof of Theorem 3.2, we obtain that 18 E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO ||x||1≤(1 + 4||A||1,∞)h(r−1) + 2r−1 because ]F ≤r. The improvement now is that d1=r 2> r because r≥3. In [17] a similar result appears. Even forgetting the torsion, there exists a small difference. In [17] the number D:= max{||Aτ||1,∞|τis an F-cavity, ]F ≥3} replaces to 4||A||1,∞. It is clear that D≤4||A||1,∞(the same arguments used in Theorem 3.2 are right). The advantage of our version is that the bound is straight forward obtained from A, without being necessary to construct any matrix Aτ.It is also clear that in Theorem 3.2 the number Di:= max{||Aτ||1,∞|τis a i-triangulation of F, ]F ≥i+ 2} can replace to 4||A||1,∞, but our version is more useful for the proof of Theorem 4.1. There is no result similar to Theorem 3.2 in the literature, for i≥2. In the following remark we consider the generalization to the case Swith torsion non trivial. Remark 3. 2. S⊂Zh⊕Z/a1Z⊕. . . ⊕Z/asZ with aj∈Z, 1 ≤j≤s. Now, A∈M(h+s)×r(Z) and A(t)∈ M(h+s)(t−1)×rt(Z). To use the reasoning in the without torsion case, we need to remove the congruences in the systems of kind A(t)β=−A(t)eτ. Then, it is enough to consider the auxiliary matrices (see [17] for details) THE REGULARITY OF A TORIC VARIETY 19 T=             0 0 0 0 · · · 0 0 0 . . .. . .. . . 0 0 0 0 · · · 0 0 0 a1−a10 0 0 0 0 0 0 a2−a20· · · 0 0 ......... 0 0 0 0 0 as−as             ∈ M(h+s)×2s(Z), and g A(t)=(A(t)|˜ T), where ˜ T=   T0. . . 0 0 ... 0 0 . . . 0T   ∈ M(t−1)(h+s)×(t−1)2s(Z). Using the system without congruences of kind g A(t)β=−A(t)eτ, the following result is obtained. If m∈Sis an S-degree of a minimal i-syzygy for k[S], then m=Ax with x∈Nrsuch that ||x||1≤(1 + 2a+ 4||A||1,∞)(h+s)(di−1) + (i+ 1)di−1, where a=max1≤j≤s|aj|and di=r i+ 1 . 4. REGULARITY OF PROJECTIVE TORIC VARIETIES In this section we suppose that Iis homogeneous for the natural graduation. This is equivalent to there exists a vector w∈Qhsuch that ni·w= 1, for any i= 1, . . . , r. (Lemma 4.14 in [22]). Geometrically, Idefines a projective variety in Pr−1(k). Notice that if f∈Iis S-homogeneous of S-degree m∈S, then deg(f) = ||α||1, for any α∈Nrwith Aα=m. Suppose that {f1, . . . , fβ1}is a minimal generating set of I,S-deg(fi) = pi∈Sand deg(fi) = ||αi||1, where pi=Aαi, 1 ≤i≤β1. If g= (g1, . . . , gβ1)∈N1is a 1-syzygy of S-degree m∈S, then S-deg(gi) = m−pi and deg(gi) = ||βi||1where Aβi=m−pi. Thus, m=A(αi+βi) and deg(g) = ||αi+βi||1. 20 E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO More generally, if h= (h1, . . . , hβi)∈Niis an i-syzygy of S-degree m∈S, then deg(h) = ||α||1, for any α∈Nrsuch that m=Aα. By this way, we obtain an explicit bound for the Castelnuovo-Mumford regularity of I. In the following theorem, the symbol bc stands for integral part. Theorem 4.1. With assumptions and notations as above, reg(I)≤(1 + 4||A||1,∞)h(d−1) + (r+ 1)(d−1) where d=r br/2c. Proof. The regularity of Iis reg(I) = max1≤i≤r{ti−i}, where tiis the maximum degree of the i-syzygies of I(see, for example, [2]). By Theorem 3.2, ti≤(1 + 4||A||1,∞)h(di−1) + (i+ 1)di−1, with di=r i+ 1 . It is clear that di≤d, for any i. Then ti−i≤(1 + 4||A||1,∞)h(d−1) + (r+ 1)(d−1). It is enough to take maximum. Finally, notice that the effective computation of the regularity of Idoesn’t require the computation of the minimal resolution. It is sufficient to use the Step 1 of Construction in the introduction for any i. We describe this algorithm. Algorithm 1. Computing the regularity Input: Set of generators {n1, . . . , nr}of S. (Recall that they must lie on a rational hiperplane.) Output: The regularity of the ideal Iof S. 1. For any i, 1 ≤i≤r •Compute the set C0 i(Theorem 1.1). •Check the element m∈C0 isuch that ˜ Hi(∆m)6= 0 and obtain Ci. THE REGULARITY OF A TORIC VARIETY 21 •Compute ti={||α||1|m=Aα∈Ci}. 2. Output reg(I) = max{ti−i|i= 1, . . . , r}. REFERENCES 1. A. ARAMOVA, J. HERZOG, Free resolution and Koszul homology. J. of Pure and Applied Algebra, 105 (1995), 1-16. 2. D. BAYER, M. STILLMAN, A criterion for detecting m-regularity. Inventiones mathematicae, 87 (1987), 1-11. 3. 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. 4. 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. 5. E. BRIALES, A. CAMPILLO, C. MARIJU´ AN, P. PIS ´ ON, Combinatorics of syzygies for semigroup algebra. Collet. Math. 49 (1998), 239-256. 6. W. BRUNS, J. HERZOG, Cohen-Macaulay rings. Cambrigde University Press, (1993). 7. W. BRUNS, J. HERZOG, Semigroup rings and simplicial complexes. J. of Pure and Applied Algebra,122 (1997), 185-208. 8. A. CAMPILLO, C. MARIJU´ AN, Higher relations for a numerical semigroup. S´em. Th´eor. Nombres Bordeaux 3(1991), 249-260. 9. A. CAMPILLO, P. GIM´ ENEZ, Syzygies of affine toric varieties. Journal of Algebra to appear. 10. CAMPILLO A.; PIS ´ ON P. L’id´eal d’un semi-grupe de type fini. C. R. Acad. Sci. Paris, S´erie I,316 (1993), 1303-1306. 11. D. EISENBUD, Introduction to Commutative Algebra with a View Towards Algebraic Geometry. Graduate Texts in Mathematics 150 (1995), Springer, New York. 12. P.A. GARC´ IA-S´ ANCHEZ Semigrupos afines. Ph. D. Thesis, Universidad de Granada (1996). 13. M. HOCHSTER, Cohen-Macaulay rings, combinatorics, and simplicial complexes, In BR. McDonald, R.A. Morris editors, Ring Theory II, LNPAM 26, Marcel-Dekker (1995), 171-223. 14. 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. 15. I. PEEVA, B. STURMFELS, Syzygies of codimension 2 lattice ideals, Math. Z. 229 (1998), 163-194. 16. P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO, N−solutions to linear systems over Z.Preprint of University of Sevilla 43 (1998). 17. P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO, First Syzygies of Toric Varieties and Diophantine Equations in Congruence, Preprint of University of Sevilla 52 (1999). 22 E. BRIALES-MORALES, P. PIS ´ ON-CASARES, A. VIGNERON-TENORIO 18. L. POTTIER, Bornes et algorithmes de calcul des generateurs des solutions de syst´emes diophantines lin´earies. C.R. Acad. Sci. Paris, Serie I 311(1990), 813-816. 19. L. POTTIER, Minimal solutions of linear diophantine systems: bounds and algorithms. Proceedings of the Fourth International Conference on Rewriting Techniques and Applications, Italy 1991, 162-173. 20. J.C. ROSALES, Semigrupos num´ericos . PhD Thesis, Universidad de Granada (1991). 21. R. STANLEY, Combinatorics and commutative algebra 2nd ed. Progress in Mathematics Vol.41, Boston Basel Berlin, Birkh¨auser (1996). 22. B. STURMFELS, Gr¨obner bases of Toric Varieties. Tˆohoku Math. J. 43 (1991), 249-261. 23. A. VIGNERON-TENORIO, Semigroup Ideals and Linear Diophantine Equations. Linear Algebra and its Applications, 295 (1999), 133-144.