9512.net
ÌðÃÎÎÄ¿â
µ±Ç°Î»ÖÃ£ºÊ×Ò³ >> >>

# The associated primes of initial ideals of lattice ideals

The associated primes of initial ideals of lattice ideals
Serkan Hosten Mathematical Sciences Department George Mason University Fairfax, VA 22030
shosten@gmu.edu

Rekha R. Thomas Department of Mathematics Texas A&M University College Station, TX 77843
rekha@math.tamu.edu

November 20, 1998

Abstract
This paper concerns the associated primes and primary decompositions of the monomial initial ideals of lattice ideals. For a xed initial ideal, we show that the multiplicities of its associated primes and its arithmetic degree are the cardinalities of sets of polytopes in which the origin is the unique lattice point. The associated primes are shown to exhibit a rare connectivity property: each embedded prime contains an associated prime of one higher dimension. The length of any such chain of associated primes can be bounded above by a function that depends only on the codimension of the lattice ideal. We express the unique irredundant irreducible decomposition of an initial ideal of a lattice ideal using maximal lattice point free polytopes de ned by the lattice and the cost vector inducing the initial ideal.

1 Introduction and main results
Given a sublattice L of Zn of rank m, the lattice ideal of L is the (n ? m)-dimensional binomial ideal IL := hxu ? xv : u ? v 2 Li k x1 ; : : : ; xn ] =: k x]: If L is saturated, i.e., (L Z Q) \ Zn = L then IL is prime and there exists a matrix A 2 Z(n?m) n of rank n ? m such that L = fu 2 Zn : Au = 0g. In this case, IL is the toric ideal of A Ful], Stu] which is denoted as IA . Let N denote the set of non-negative integers. Throughout this paper we assume that L \ Nn = f0g which implies that IL is homogeneous with respect to a degree grading where degree(xi ) = ai > 0. For simplicity we assume that ai = 1 for all i = 1; : : : ; n. 1

In this paper we study the associated primes and primary decompositions of inc (IL ), the initial ideal of IL with respect to a cost vector c 2 Rn . Here inc (IL ) is the ideal generated by the initial forms of the polynomials in IL, with respect to c. In general inc(IL ) may not be a monomial ideal, but throughout this paper we assume that it is a monomial ideal, in which case c is said to be generic. In other words, inc (IL ) = in (IL ) for some term order , and c is a vector that lies in the interior of the Grobner cone corresponding to in (IL ) (see Stu], Chapters 1 and 2). Since L\ Nn = f0g, every Grobner cone of IL has a non-trivial intersection with the non-negative orthant of Rn , and hence we may assume that c is a non-zero non-negative integral vector. In Section 3 we show that the associated primes of inc(IL ) come in saturated chains which is a rare property for an arbitrary monomial ideal. Theorem 3.1 If P is an embedded prime of inc(IL), then P contains an associated prime Q of inc (IL ) such that dim(Q) = dim(P ) + 1. Let Ass(inc(IL )) denote the partially ordered set (poset) of associated primes of inc (IL ) where Q P if Q P . The minimal primes of inc (IL ) are hence the maximal elements of Ass(inc (IL)). In Section 3 we also show that the length of a maximal chain in Ass(inc (IL )) can be bounded above by a function that depends only on the codimension of IL and that this bound is sharp. This result also follows from Theorem 2.3 in PS]. Theorem 3.4 The length of a maximal chain in Ass(inc(IL)) is at most min(n ? m; 2m ? (m +1)). The associated primes of a monomial ideal M are closely related to the standard pair decomposition STV] of the standard monomials of M which we now describe. Recall that a monomial xm is a standard monomial of M if xm 2 M . For m 2 Nn, let the support of m be denoted by = m ) := supp(m). Let n] := f1; : : : ; ng. supp(m) := fi : mi 6= 0g and let supp(x

De nition 1.1 For a monomial xm 2 k x] and n], we say that (xm ; ) is an admissible pair of a monomial ideal M if (i) supp(m) \ = ; and (ii) every monomial in xm k xj : j 2 ]
is a standard monomial of M .

There is a natural partial order on the set of all admissible pairs of M given by (xm ; ) (xm0 ; 0 ) if and only if xm divides xm0 and supp(xm0 =xm ) 0 .

De nition 1.2 An admissible pair (xm ; ) of M is called a standard pair of M if it is a minimal
element in the poset of all admissible pairs with respect to the above partial order.

The standard pairs of M induce a unique covering of the set of standard monomials of M which we refer to as the standard pair decomposition of M . It was shown in STV] that the arithmetic degree BM] of M , denoted arithdeg(M ), equals the number of standard pairs of M . This paper gives a bound for arithdeg(M ) in terms of the degrees of the minimal generators and dimension of M . Algebraically, arithdeg(M ) = P mult(P )deg(P ) where the sum is over all homogeneous prime 2

ideals P in k x], and mult(P ) denotes the length of the largest ideal of nite length in the ring k x]P =Mk x]P , and deg(P ) is the geometric degree of the variety of P . The integer mult(P ) is positive if and only if P is an associated prime of M . In our situation, since M is a monomial ideal, every associated prime of M has the form p := hxj : j 62 i for some n] and, deg(p ) = 1 since deg(xi ) = 1.

Theorem 1.3 STV] Given a monomial ideal M and p = hxj : j 62 i for some

n]: (i) p is an associated prime of M if and only if M has a standard pair of the form ( ; ). If p is an associated prime of M then mult(p ) equals the number of standard pairs of M of the form P mult(p ) is the number of standard pairs of M . ( ; ). Hence, arithdeg(M ) = n] (ii) p is a minimal prime of M if and only if (1; ) is a standard pair of M .
Let B 2 Zn m be a matrix whose columns form a basis for L. By our earlier assumptions, ker(B T ) contains a strictly positive vector and hence the rows of B denoted as b1 ; : : : ; bn span Rm positively, i.e., cone(b1 ; : : : ; bn ) = Rm . Given a generic cost vector c 2 Rn , the vector cB lies in the relative interior of a collection C of m-dimensional simplicial cones whose generators are in fb1 ; : : : ; bng. We identify each such cone with the set of row indices of its generators. Then it can be shown that the complements of (the indices of the generators of) the cones in C form the maximal faces of an (n ? m)-dimensional pure simplicial complex on n] (see BFS]). For a xed lattice L this simplicial complex depends only on c, and hence we will denote it by c. In other words, is a face of c if and only if Pv (0) := fu 2 Rm : ?(cB ) u 0; B u vg is a polytope (i.e., bounded polyhedron) for all v 2 Nj j where = n]n and B is the submatrix of B whose rows are indexed by . In Section 2 we characterize the standard monomials and standard pairs of inc(IL ) in terms of polytopes de ned by L and c in which the origin is the unique lattice point. These characterizations are then used to prove the results of Section 3. An important feature of our results is that the ideal inc (IL ) is never needed in explicit form (in terms of a minimal generating set for example) in order to obtain its associated primes, irreducible decomposition and standard pairs. The two main results of Section 2 are as follows:

Theorem 2.3 The monomial xv is a standard monomial of inc(IL) if and only if 0 is the unique lattice point in Pv (0) := fu 2 Rm : Bu v; ?(cB ) u 0g.
lattice point in Pv (0) and all of the inequalities in the system B u v are essential, i.e., removing any inequality introduces a new lattice point into the resulting polyhedron.

Theorem 2.5 An admissible pair (xv ; ) of inc(IL) is a standard pair if and only if 0 is the unique

Theorems 2.3 and 2.5 give the following combinatorial interpretation of the mutliplicity of an associated prime of inc (IL ) and the arithmetic degree of inc(IL ). 3

Corollary 2.7 (i) The multiplicity of p is the number of polytopes of the form Pv (0) where v 2 Nj j , 0 is the unique lattice point in Pv (0) and all inequalities in B u v are essential.

(ii) The arithmetic degree of inc (IL ) is the total number of such polytopes Pv (0) as ranges over the subsets of n]. We conclude in Section 4 with an explicit formula for an irreducible primary decomposition of inc(IL ) in terms of the maximal lattice point free polytopes BSS], Lov] of the form Pv (0). The crucial idea here is to prove a bijection between the socle elements in the localization of inc (IL ) at the associated prime p and the maximal lattice point free polytopes of the form Pv (0).

2 Multiplicity of associated primes and arithmetic degree
Two lattice points v; u 2 Nn are congruent modulo L if v ? u 2 L. The congruence classes of Nn modulo L are called the bers of L. Since L \ Nn = f0g, each ber C 2 Nn =L is nite, and since the cost vector c is generic, each ber contains a unique lattice point that minimizes the linear functional c x (follows from Section 5 in SWZ]). These optimal solutions de ne inc (IL ).

Proposition 2.1 SWZ] A monomial xv is a standard monomial of inc(IL) if and only if v minimizes the linear functional c x in its ber.

Given a ber C of L and v 2 C we can identify this ber with the lattice points in the polytope

Pv := fu 2 Rm : Bu vg;

(1)

via the map Pv \ Zm ! Nn such that u ! v ? Bu. In particular, 0 2 Pv maps to v 2 C . If v; v0 2 C , then Pv and Pv0 are lattice translates of each other and hence we may represent C by any of the polytopes Pv where v 2 C . This representation of a ber of L was introduced in PS].
monomial of inc(IL ) if and only if u is the optimal solution to the integer program minimizef?(cB ) u : u 2 Pv \ Zm g:

Proposition 2.2 Let v be an element of a ber C . Then the monomial x(v?Bu ) is a standard
(2)

Proof: By Proposition 2.1, the monomial xv is a standard monomial of inc (IL ) if and only if the lattice point v 2 C minimizes c x over C . This happens () there exists u 2 Zm such that v = v ? Bu 0 and c(v ? Bu ) < c(v ? Bu) for all u 6= u 2 Zm with v ? Bu 0 () there exist u 2 Pv \ Zm such that ?(cB ) u < ?(cB ) u for all u 2 Pv \ Zm and u 6= u () u is the optimal solution of the integer program (2). 2 4

Using the optimal solution u to the program (2), we de ne the following subpolytope of Pv which plays an important role in this paper:

Pv (u ) := fu 2 Rm : Bu v; ?(cB ) u ?(cB ) u g:

(3)

Theorem 2.3 Let v 2 Nn be a lattice point in a ber C . Then xv?Bu is a standard monomial

of inc(IL ) if and only if u is the unique lattice point in Pv (u ). In particular, xv is a standard monomial if and only if 0 is the unique lattice point in Pv (0) = fu 2 Rm : Bu v; ?(cB ) u 0g.

Proof: Since c is assumed to be generic, each integer program (2) has a unique optimal solution. By Proposition 2.2, u 2 Zm is the optimal solution to (2) if and only if u is in Pv and there is no u 6= u in Pv \ Zm such that ?(cB ) u ?(cB ) u . This is equivalent to u being the unique lattice point in Pv (u ). The second statement follows immediately. 2

Example 2.4 Consider the lattice L of rank two which is generated by the rows of " # 5 2 ?6 5 ?6 T= B : ?1 1 ?1 0 1
The codimension two lattice ideal IL is homogeneous with respect to the usual total degree grading. Let c = (6 2 1 1 7) and consider the ber C of v = (2; 0; 5; 2; 3). The polytope Pv = fu 2 R2 : Bu vg is de ned by the ve inequalities whose normal vectors are the columns b1 ; : : : ; b5 of B T (see Figure 1). Observe that there are three lattice points in Pv : (0; 0); (0; ?1); (0; ?2). They correspond to the vectors (2; 0; 5; 2; 3); (1; 1; 4; 2; 4); (0; 2; 3; 2; 5) in C , respectively. If we add the constraint ?(cB ) u 0 to Pv where ?(cB ) = (9; ?2) we get Pv (0). Figure 1 shows that 0 is the unique lattice point in Pv (0), and Theorem 2.3 implies that xv is a standard monomial of inc(IL ). Indeed, the reduced Grobner basis of IL with respect to c is Gc = fx4 x8 ? x7 x5 ; x5 x7 ? x6 x2 x5 ; x6 x6 ? 4 3 5 1 1 4 3 5 3 5

x5 x2 x5 ; x7 x5 ? x4 x3 x5 ; x8 x4 ? x3 x4 x5; x9 x3 ? x2 x5 x5; x10 x2 ? x1 x6 x5 ; x2 x5 ? x1 x3; x7 x5 ? x11 x5 g 3 2 4 2 4 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 2 4 3 5 2 with respect to which x2 x5 x2 x3 is a standard monomial. 1 3 4 5

For n], let Pv := fu 2 Rm : B u v g be the polyhedron obtained from Pv by removing the inequalities indexed by . Here we use v to denote the truncation of v obtained by restricting to the coordinates indexed by (v lies in Nj j). Let Pv (0) := fu 2 Rm : (?cB ) u 0; B u v g which is gotten from Pv by adding the additional constraint (?cB ) u 0. For a polyhedron P = fx 2 Rp : Ti x ti ; i = 1; : : : ; qg we say that an inequality Ti x ti is essential if the relaxation of the polyhedron obtained by removing Ti x ti contains a new lattice point.

Theorem 2.5 An admissible pair (xv ; ) of inc(IL) is a standard pair if and only if 0 is the unique
lattice point in Pv (0) and all of the inequalities in the system B u v are essential.

5

b2 (0,0) b4 b5
-

b2 (0,0) b5 b4 -cB

b3

b1

b3

b1

Figure 1: Pv and Pv (0) of Example 2.4. Proof: An admissible pair (xv ; ) of M := inc (IL ) is a standard pair if and only if all monomials in xv k xj : j 2 ] are standard monomials, and for every i 2 there exists mi > 0 such that xmi xv 2 M . By Theorem 2.3, this is the case if and only if for every v0 with support in , the i origin is the unique lattice point in P(v+v0 ) (0) = fu 2 Rm : B u v ; B u v0 ; (?cB ) u 0g and for each i 2 there exists mi > 0 such that P(vi +v0 ) (0) where vi = v + (0; : : : ; 0; mi ; 0; : : : ; 0) contains an extra lattice point. This is equivalent to saying that Pv (0) contains the origin as the unique lattice point, and each inequality in this polytope is essential. 2

polytope. But we cannot take a superset of and maintain the same property. Hence (x3 ; ) is a 5 standard pair of inc (IL ). 2 Using Theorem 2.5 we obtain a combinatorial interpretation for mult(p ) and arithdeg(inc (IL )).

Example 2.6 Example 2.4 continued. If we examine Pv (0) in this example, we see that removing the inequalities corresponding to = f1; 3; 4g keeps 0 as the unique lattice point in the resulting

Corollary 2.7 (i) The multiplicity of p is the number of polytopes of the form Pv (0) := fu 2 Rm : B u v ; ?(cB ) u 0g where v 2 Nn, 0 is the unique lattice point in Pv (0) and all

inequalities in B u v are essential. (ii) The arithmetic degree of inc (IL ) is the total number of such polytopes Pv (0) as ranges over the subsets of n].

6

In the rest of this section we will relate the faces of the simplicial complex c from the introduction to the associated primes of inc(IL ). We start with the maximal faces of c.

Theorem 2.8 The prime ideal p is a minimal prime of inc(IL) if and only if is a maximal face of c. The multiplicity of such a minimal prime is jdet(B )j.
Proof: If is a maximal face of c, by the de nition of this simplicial complex, the vector cB is in the interior of the full-dimensional simplicial cone generated by the rows of B . Therefore Pv (0) is a polytope for all v 2 Nn de ned by m + 1 inequalities (Pv (0) is a full dimensional simplex in Rm ), and if we omit any one of these inequalities the resulting polyhedron will be unbounded. In particular, when v = 0 the polytope Pv (0) is just the origin itself and each inequality is essential. This proves that (1; ) is a standard pair of inc (IL ), and by Theorem 1.3 (ii) p is a minimal prime. Conversely, if p is a minimal prime then (1; ) is a standard pair. Hence P0 (0) is bounded, and therefore there exists a strictly positive linear relation on ?(cB ) and the rows of B , i.e, s(?cB ) + Pi= sibi = 0 for some s; si > 0. This means that the vector cB is in the relative interior 2 of the cone generated by the rows of B , and hence for a maximal face of c . By the rst part of the proof, p is a minimal prime and hence = . For the second claim, rst note that B is an m m nonsingular matrix since its rows generate a full-dimensional simplicial cone in Rm . Since the lattice L0 generated by the columns of B has index jdet(B )j in Zm , and since such a lattice will always contain a strictly positive vector, the number of bers of Nm =L0 is equal to this index. Hence for each such ber there exists v 2 Nn with support in such that Pv (0) contains the origin as the unique lattice point. Since omitting any inequality de ning this polytope gives rise to an unbounded set, we conclude that (xv ; ) is a standard pair. Using Corollary 2.7 (i) we see that jdet(B )j is the multiplicity of p . 2
Moreover, if p is an associated prime of inc (IL ), then is a face of c.

Corollary 2.9 The radical of inc(IL) is the Stanley-Reisner ideal of the simplicial complex

c.

Proof: The Stanley-Reisner ideal of a nite simplicial complex is the ideal generated by all monomials xi1 xik such that fi1 ; : : : ; ik g is a non-face of the complex. By Theorem 2.8 the radical of inc(IL ) is the intersection of p as runs through the maximal faces of c. 2 The above corollary also shows the well known fact that inc (IL ) is an equidimensional ideal (all minimal primes have the same dimension n ? m). This follows from the fact that c is a pure simplicial complex whose maximal faces have dimension n ? m. When the lattice ideal IL is the toric ideal IA , the simplicial complex c is the regular triangulation of A induced by c, and Theorem 2.8 and Corollary 2.9 for the toric case can be found in Chapter 8 of Stu]. To illustrate Theorem 2.5 and Theorem 2.8 we give the following example in which the lattice ideal is toric. 7

d 2 c 4 33 e 24 14 a 39

b

Figure 2: The bold faces of c index the embedded primes of inc (IL ).

3 2 1 1 1 1 17 6 Example 2.10 Consider A = 6 0 4 5 2 0 7 and c = (17; 21; 0; 0; 0). We let a; b; z; d; e be 5 4

0 1 4 5 2 the variables indexing the ve columns of A. Then L = ker(A) \ Z5 is generated by the rows " # T = ?8 7 ?6 1 6 ; and ?(cB ) = (?11; 11). Since the columns of A lie on the of B ?13 10 ?8 0 11 hyperplane x1 = 1, we can draw (the regular triangulation) c as a triangulation of a pentagon as in Figure 2. Recall that c is a triangulation of the cone in R3 generated by the ve columns of A, and the pentagon in Figure 2 is the intersection of this cone with the hyperplane fx 2 R3 : x1 = 1g. The minimal primes of inc (IL ) are in bijection with the three maximal faces of c. The simplices 2 c such that p is an embedded prime of inc(IL) are the faces of c indicated by bold lines. The multiplicity of each embedded prime is given next to the corresponding face. In particular, all embedded primes of inc (IL ) have dimension two and pf2;5g is not an embedded prime. Consider = f3; 5g in c . We group the monomials appearing in the 33 standard pairs of the form ( ; f3; 5g) into two groups depending on the exponent of the variable d:

Each inequality is labeled by a monomial in the variable indexing the inequality. The exponent of this monomial is the component of v in the slot indexed by this variable. In Figure 3, the inequality indexed by d is xed at right hand side value one. Notice that 0 is the unique lattice point in the shaded polytope and that all the three inequalities (indexed by a; b; d) are essential for the shaded polytope (if you remove inequality d, the lattice point (3; ?2) enters the relaxation). By Theorem 2.5, Figure 3 can be used to compute all the monomials in Group 1 by translating inequalities a and b to all positions that will keep Pv (0) lattice point free except for the origin and 8

a3 b5 d; a3 b6 d; a4 bd; a4 b2 d; a4 b3 d; a4 b4 d; a4 b5 d; a4 b6 d; b4 d; ab4 d; b5 d; ab5 d; b6 d; ab6 d; a4 b6 d. Group 2:(exponent of d is two) a2bd2 ; a3 bd2 ; a4bd2 ; a2 b2 d2; a3 b2 d2; a4 b2 d2; a2 b3 d2 ; a3b3 d2 ; a4 b3d2 : We rst consider Group 1. The shaded polytope in Figure 3 is Pv (0) for the monomial a2 bd.

Group 1: (exponent of d is one) a2 bd; a2 b2d; a2 b3d; a2 b4 d; a2 b5d; a2 b6d; a3 bd; a3 b2d; a3 b3 d; a3 b4d;

d

cost

0

b b4 a2 a4 b

6

Figure 3: The polytopes Pv (0) for the monomials in Group 1.

d

2

cost

0

b3 a2 a4 b

Figure 4: The polytopes Pv (0) for the monomials in Group 2. 9

all inequalities essential. For instance, for any right hand side value of inequality b between one and six and any right hand side value of inequality a between two and four Pv (0) has the properties of Theorem 2.5. This shows that the rst 18 monomials in Group 1 appear in standard pairs with = f3; 5g. At the right hand side values between four and six for inequality b, you can decrease the right hand side of inequality a from two to zero while still maintaining the required properties for Pv (0). This takes care of the last six monomials in Group 1. Figure 4 illustrates Theorem 2.5 for the monomials in Group 2. 2

3 The poset of associated primes
We now establish a structural result for Ass(inc (IL )), the poset of associated primes of inc (IL ) where for P; Q 2 Ass(inc (IL )), we write P Q if P Q. Corollary 2.9 implies that Ass(inc(IL )) is a subposet of the face lattice of c , both posets having the same maximal elements.

Theorem 3.1 Let be a non-maximal face of c such that p is an embedded prime of inc(IL). Then there exists a 0 2 c such that 0 , j 0 j = j j +1 and p 0 is an associated prime of inc (IL ).
Proof: Since p is an embedded prime, inc (IL ) has a standard pair of the form (xv ; ) where v 6= 0 and supp(v) . By Theorem 2.5, the origin is the unique lattice point in Pv (0) = fu 2 Rm : B u v ; ?(cB ) u 0g and all the inequalities of B u v are essential. For each i 2 , let Ri be the relaxation of Pv (0) obtained by removing the ith inequality bi u vi , i.e., Ri := fu 2 Rm : B fig u v fig ; ?(cB ) u 0g. Let E i := RinPv (0) = fu 2 Rm : B fig u v fig ; bi u > vi ; ?(cB ) u 0g. Clearly, E i \ Pv (0) = ;, and since the removal of each inequality introduces at least one lattice point into Ri we have E i \ Zm 6= ;. Let ui be the optimal solution to the integer program minf?(cB ) u : u 2 E i \ Zmg. This integer program is always feasible since E i \ Zm 6= ;, but it may not have a nite optimal value. However, there exists at least one i 2 for which the above integer program is bounded. To see this, pick a maximal simplex 2 c such that . The polytope fu 2 Rm : B u v ; ?(cB ) u 0g is a simplex and hence bounded. This polytope contains all E i for i 2 n and hence all these E i are bounded and have nite optima with respect to ?(cB ). We may assume that the inequalities in B u v are labeled so that the nite ?(cB ) up where f1; 2; : : : ; pg. optimal values are ordered as ?(cB ) u1 ?(cB ) u2 Claim: Let N 1 := fu 2 Rm : B f1g u v f1g ; ?(cB ) u ?(cB ) u1g. Then u1 is the unique lattice point in N 1 and all inequalities are essential. Proof: Since u1 lies in R1 , 0 = ?(cB ) 0 ?(cB ) u1 . However, 0 > ?(cB ) u1 since otherwise, both u1 and 0 would be optimal solutions to minf?(cB ) u : u 2 R1 g contradicting that c is generic. Therefore, N 1 = R1 \ fu 2 Rm : ?(cB ) u ?(cB ) u1 g = (E 1 Pv (0)) \ fu 2 Rm : ?(cB ) u ?(cB ) u1 g = (E 1 \fu 2 Rm : ?(cB ) u ?(cB ) u1 g) S(Pv (0)\fu 2 Rm : ?(cB ) u ?(cB ) u1 g). 10

Translating N 1 by ?u1 we get Pv0 f1g (0) := fu 2 Rm : ?(cB ) u 0; B f1g u v0 g where v0 = v f1g ? B f1g u1 0 since u1 is feasible for all inequalities except the rst one. Now Pv0 f1g (0) contains only the origin as an integral vector and hence (xv0 ; f1g) is a standard pair of inc (IL ). 2 one. However, there is no associated prime generated by a pair of variables.

Since c is generic, u1 is the unique lattice point in the rst polytope and the second polytope is free of lattice points. Hence u1 is the unique lattice point in N 1 . The relaxation of N 1 got by removing bj u vj is the polyhedron N 1 (E j \ fu 2 Rm : ?(cB ) u ?(cB ) u1 g) for j 2 and j 6= 1. Either this is unbounded, in which case there is a lattice point u in this relaxation such that ?(cB ) u1 ?(cB ) u or (if j p), we have ?(cB ) u1 ?(cB ) uj and uj lies in this relaxation which shows that bj u vj is essential for N 1 . }

Remark 3.2 Theorem 3.1 fails for general monomial ideals. The associated primes of the monomial ideal hx2 yz; xy2 z; xyz 2 i k x; y; z ] are hxi, hyi, hz i, and hx; y; z i and each has multiplicity Remark 3.3 Theorem 3.1 may fail when the cost vector is not generic. We thank David Eisenbud and Sorin Popescu for pointing1 to the following example. Consider the toric ideal IA where A = us 0 B3 2 2 1 1 0 0 0 0C B 0 1 0 2 0 3 2 1 0 C and the cost vector ! = (1; 1; 1; 1; 1; 1; 1; 1; 0). Then in! (IA) = A @
hh ; gh; ch; eg; e2 ; ce; aeh; g2 ? fh; cg ? bh; ef ? dh; cf ? bg; de ? bh; be ? ah; d2 ? bf; cd ? ag; bd ? af; c2 ? ae; b2 ? adi which shows that ! is not generic. Here, the variables a; b; c; d; e; f; g; h; i have been associated with the columns of A. The associated primes of in! (IA ) are P1 = hc; e; g; h; d2 ? bf; bd ? af; b2 ? adi of dimension three and P2 = ha; b; c; d; e; f; g; hi of dimension one. The embedded prime
2

0 0 1 0 2 0 1 2 3

initial ideal.

P2 contains the minimal prime P1 . However, there is no embedded prime of dimension two for this

Since the dimension of inc (IL ) is n ? m, the length of a maximal chain in Ass(inc(IL )), which we denote as length(Ass(inc (IL ))), is at most n ? m. However, when m which is the codimension of inc (IL ) is small compared to the dimension of inc (IL ), length(Ass(inc (IL ))) has a stronger upper bound as shown below. We need the following result (Corollary 16.5a in Sch]).

Theorem 3.4 Let Ax b be a system of linear inequalities in n variables, and let c 2 Rn. If max fc x : Ax b; x 2 Zn g is a nite number, then max fc x : Ax b; x 2 Zn g = max fc x : A0 x b0; x 2 Zng for some subsystem A0 x b0 of Ax b with at most 2n ? 1 inequalities. Theorem 3.5 The length of a maximal chain in Ass(inc(IL)) is at most min(n ? m; 2m ? (m +1)). Proof: As we noted before we have length(Ass(inc (IL ))) (n ? m). Suppose xv is a standard
monomial of inc (IL ). Then the origin is the optimal solution to the integer program (2): min 11

f?(cB ) u : Bu v; u 2 Zmg. By Theorem 3.4, we need at most 2m ? 1 inequalities to describe the same integer program. This means we can remove at least n ? (2m ? 1) inequalities from
Bu v without changing the optimal solution. After removing these inequalities the corresponding polytope Pv (0) will meet the conditions in Theorem 2.5 for some 2 c . Therefore is of size at least n ? (2m ? 1). This implies that the maximal length of a chain in Ass(inc(IL )) is at most (n ? m) ? (n ? (2m ? 1)) = 2m ? (m + 1). 2

toric. The algorithm proceeds by building inc (IL ) from localizations of inc (IL ) at its associated primes starting at the top level of c (i.e. at the minimal primes) and then working down the poset one level at a time. Theorems 3.1 and 3.5 provide stopping criteria and bounds for this algorithm.

Corollary 3.6 The dimension of an associated prime of inc(IL) is at least max(0; n ? (2m ? 1)) and the codimension is at most min(n; 2m ? 1). Corollary 3.7 If L has rank two, then length(Ass(inc(IL))) 1. Proof: In this situation, 2m ? (m + 1) = 4 ? (4 ? 2 + 1) = 4 ? 3 = 1. 2 Remark 3.8 In HT] we describe a non-Buchberger algorithm to construct inc(IL) when IL is

We conclude this section with a family of lattice ideals of codimension m for which the length of Ass(inc(IL )) attains the bound in Theorem 3.5. This family was used in PS] to give lattice ideals with maximal projective dimension.

Proposition 3.9 For each m > 1, there is a codimension m lattice ideal and a cost vector c 2 Rn where n = 2m ? 1 such that length(Ass(inc (IL ))) = 2m ? (m + 1). Proof: Given m > 1, let B = (bij ) 2 Z(2m ?1) m be the matrix whose rows are all possible vectors in Rm that use 1 and ?1 as entries except v = (?1; ?1; : : : ; ?1). The lattice generated by the columns of B has rank m, and therefore we can nd a cost vector c 2 Rn (where n = 2m ? 1) such that ?cB = v. For each row bi we set ri := jfbij : bij = 1gj, and let r be the vector of all ri 's. By construction, the polytope P := fu 2 Rm : Bu r; ?(cB ) u 0g has no lattice points in its interior and each of its 2m facets has exactly one vertex of the unit cube in Rm in its relative interior. If we let wi = ri ? 1, then the polytope fu 2 Rm : Bu w; ?(cB ) u 0g is Pwn] (0).

The origin is the only lattice point in Pwn](0) and all the inequalities are essential. By Theorem 2.5, (xw ; ;) is a standard pair of inc (IL ). Since a maximal face of c is (2m ? 1 ? m)-dimensional, Theorem 3.1 implies that length(Ass(inc(IL ))) = 2m ? 1 ? m. 2

4 Irreducible primary decomposition
De nition 4.1 A polyhedron is maximal lattice point free if and only if it contains no interior
lattice points but every facet of it contains an interior lattice point.

12

In Section 2 we saw that a standard pair (xv ; ) of inc (IL ) gives the polytope Pv (0) = fu 2 Rm : B u v ; (?cB ) u 0g in which the origin is the only lattice point and all inequalities are essential. Suppose we now increase the coordinates of v by integral amounts until Pv (0) becomes maximal lattice point free. Then Pv (0) is a full dimensional polytope in which every row of B u v gives rise to a facet of Pv (0).

Theorem 4.2 The ideal inc(IL) has the irreducible primary decomposition \ qi inc(IL ) = (xi : i 2 )
Pq (0)

where the intersection is over all maximal lattice point free polytopes of the form Pq (0).

For an arbitrary monomial ideal M , let M denote its localization at the associated prime p . We identify M with its projection in k x ] := k xi : i 2 ] under the map : k x1 ; : : : ; xn ] ! k x ] such that xi 7! 1 if i 2 and xi 7! xi otherwise. Under this projection, the standard pairs of M of the form (xv ; ) are in bijection with the standard pairs of M of the form (xv ; ;). For a set J , let eJ denote the vector in Nj j with one in the positions indexed by J and zero otherwise. Let q 2 Nj j be such that q := p + e where xp is a socle element modulo M . i.e., xpxi 2 M for all i 62 . (M has nitely many socle elements and each such p gives a standard pair (xp; ;) of M .) We now recall the following result from STV].

Lemma 4.3 STV] A monomial ideal M admits the irreducible primary decomposition \ M = (xqi : i 2 ) i
where the intersection is over all n] and all q 2 Nj j such that q = p + e and xp is a socle element modulo the localization of M at the associated prime p .

Proof: A monomial xm does not lie in M if and only if there is a standard pair (xv ; ) of M such that xm = xv xt for some t 2 Nj j. Let xp be a socle element of M such that v p. Then 2 xm = xv xt if and only if xm 62 (xpi+1 : i 2 ). i In order to prove Theorem 4.2 we establish a bijection between the socle elements of inc (IL ) and the maximal lattice point free polytopes of the form Pv (0). We assume that p 2 Ass(inc (IL )).
, the polytope Pp+eJ (0) has no lattice points in its relative interior, but it contains lattice points on all of its facets indexed by J .

Lemma 4.4 Let xp be a socle element of inc(IL) . Then, for J

Proof: The polytope Pp+eJ (0) is obtained by relaxing each constraint bi x pi in Pp (0) to bi x pi + 1 for i 2 J . Suppose the non-zero lattice point z is in the relative interior of Pp+eJ (0). 13

This implies that bi z < pi +1 for all i 2 J , which in turn implies that bi z pi for all i 2 J . However, this contradicts that Pp (0) has no non-zero lattice points. Since the monomial xp xi 2 inc (IL ) for each i 2 J , the polytope Pp+ei (0) contains lattice points that satisfy bi x = pi + 1. This shows 2 that Pp+eJ (0) contains lattice points on all of its facets indexed by J .

Proposition 4.5 The polytope Pq (0) where q 2 Nj j has full support is maximal lattice point free
if and only if q = p + e where xp is a socle element of inc (IL ) .

Proof: Suppose q = p + e where xp is a socle element of inc (IL ) . Since xq 2 inc (IL ) , Pq (0) has non-zero lattice points in it but by the above lemma, all of these points lie on the boundary. Since qi > 0 for all i 2 , no inequality in B x q is binding at the origin which implies that the origin lies in the interior of the facet de ned by the cost vector. Suppose for some i 2 , the facet bi x = pi + 1 of Pq (0) has no lattice point in its interior. Then by tightening all of the inequalities bj x pj + 1 back to bj x pj for all j 6= i, you get a polytope with no nonzero lattice points. However, this polytope is Pp+ei (0) which does contain nonzero lattice points since xp xi 2 inc(IL ) . Conversely, suppose Pq (0) is maximal lattice point free. Notice rst that the origin can be the only lattice point in the interior of the facet de ned by the cost vector. Else, after tightening each of the inequalities bi x qi to bi x qi ? 1 we get an integer program with two optimal solutions which contradicts that c is generic. Since Pq (0) is maximal lattice point free, the body Pq?e (0) has no lattice points other than the origin. Therefore, xp = xq?e is a standard monomial of inc(IL ) . Also, since there are lattice points in the interior of every facet, every intermediate body got by tightening a subset of the inequalities in B x q contains non-zero lattice points. This implies that xp is a socle element of inc (IL ) . 2 Proof of Theorem 4.2: The result follows from Lemma 4.3 and Proposition 4.5.

2

References
BSS] I. Barany, H.E. Scarf and D. Shallcross, The topological structure of maximal lattice point free convex bodies: the general case, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 920, Springer-Verlag, Berlin (1995) 244{251. BM] D. Bayer and D. Mumford, What can be computed in algebraic geometry? In Computational Algebraic Geometry and Commutative Algebra, eds. D. Eisenbud and L. Robbiano], Symposia Mathematica XXXIV, Cambridge University Press (1993) 1{48. BFS] L.J. Billera, P. Filliman and B. Sturmfels, Constructions and complexity of secondary polytopes, Advances in Mathematics 83 (1990) 155{179. 14

CT] P. Conti and C. Traverso, Buchberger Algorithm and Integer Programming, Proceedings AAECC-9 (New Orleans), Springer Verlag LNCS 539 (1991) 130-139. Ful] W. Fulton, Introduction to Toric Varieties, Princeton University Press, Princeton, 1993. HT] S. Hosten and R.R. Thomas, Standard pairs and group relaxations in integer programming, to appear in t Journal of Pure and Applied Algebra. Lov] L. Lovasz, Geometry of numbers and integer programming, in Mathematical Programming: Recent Developments and Applications, eds. M. Iri and K. Tanebe], Kluwer Academic Press (1989) 177{210. PS] I. Peeva and B. Sturmfels, Syzygies of codimension 2 lattice ideals, Mathematische Zeitschrift 229 (1998) 163{194. Sch] A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York, 1986. Stu] B. Sturmfels, Grobner Bases and Convex Polytopes, American Mathematical Society, Providence, RI, 1995. STV] B. Sturmfels, N. Trung and W. Vogel, Bounds on projective schemes, Mathematische Annalen 302 (1995) 417{432. SWZ] B. Sturmfels, R. Weismantel and G. Ziegler, Grobner bases of lattices, corner polyhedra and integer programming, Beitrage zur Algebra und Geometrie 36 (1995) 281{298.

15

ÔÞÖúÉÌÁ´½Ó

¸ü¶àÏà¹ØÎÄÕÂ£º