Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 36 (1995), No. 2, 281-298.

Gröbner Bases of Lattices,

Corner Polyhedra, and Integer Programming

Bernd Sturmfels^{1}, Robert Weismantel, and Günter M. Ziegler^{2}

Department of Mathematics, University of California at Berkeley Berkeley, CA 94720, USA bernd@math.berkeley.edu

Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) Heilbronner Str. 10, D-10711 Berlin, Germany weismantel@zib-berlin.de

Fachbereich Mathematik, Sekr. 6-1, Technische Universität Berlin Strasse des 17. Juni 136, D-10623 Berlin, Germany ziegler@math.tu-berlin.de

Abstract. There are very close connections between the arithmetic of integer lattices, algebraic properties of the associated ideals, and the geometry and the combinatorics of corresponding polyhedra. In this paper we investigate the generating sets (“Gröbner bases”) of integer lattices that correspond to the Gröbner bases of the associated binomial ideals. Extending results by Sturmfels & Thomas, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. In the special case where the lattice has finite index, the corner polyhedra were studied by Gomory, and there is a close connection to the “group problem in integer programming.” We present exponential lower and upper bounds for the maximal size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.

1Partially supported by the National Science Foundation and the David and Lucile Packard Foundation 2Partially supported by a “Gerhard-Hess-Prize” of the German Science Foundation (DFG)

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1995 Heldermann Verlag, Berlin

1. Introduction

For any integer lattice L ⊆ ZZ^{n} there is an associated binomial ideal

I_{L} := ⟨ x^{a^{+}} − x^{a^{−}} : a ∈ L ⟩ ⊂ k[x_{1}, …, x_{n}].

Here k is any field, and, given any lattice point a = (a_{1}, …, a_{n}), we use the abbreviation

x^{a^{+}} − x^{a^{−}} := ∏_{i:a_{i}>0}x_{i}^{a_{i}} − ∏_{j:a_{j}<0}x_{j}^{−a_{j}}.

Our aim is to study the combinatorics, geometry, and complexity of Gröbner bases for the ideals I_{L}. These occur (under different guises) in quite diverse areas of application:

• optimization and sensitivity analysis in integer programming [9, 24, 25]

• primary decomposition of general binomial ideals [12]

• certain sampling algorithms in computational statistics [11]

• the computation of short lattice vectors in the geometry of numbers [17],

• the “group problem” in integer programming [14, 21].

The quotient ZZ^{n}/L can be expressed as the direct sum of a finite abelian group and a free abelian group. What happens when either of these constituents is trivial? If ZZ^{n}/L is free abelian, then the lattice L is saturated and I_{L} is a prime ideal [12]. Such primes are called toric ideals. Gröbner bases for toric ideals and their application to integer programming have been studied by several authors (including Conti & Traverso [9], Moulinet & Pottier [19], Sturmfels [22], Thomas [24, 25]), and what follows is a natural continuation and extension of their results. Our paradigm in this paper, however, is the other extreme case when L has finite index in ZZ^{n}. This index is the order of the finite abelian group ZZ^{n}/L. It is called the determinant of the lattice L and is denoted det(L). Here the ideal I_{L} is zero-dimensional, and the k-dimension of k[x_{1}, …, x_{n}]/I_{L} equals det(L). The study of such binomial ideals arises naturally from the “group problem in integer programming”, as will be explained in Section 6.

A main algorithmic step in understanding an integer lattice L is the computation of a Gröbner basis for the ideal I_{L}, for a term order that refines the partial order given by a linear functional. Such a Gröbner basis can be computed by an adaptation of Buchberger’s classical S-pair reduction algorithm [1, 4, 6, 10]. The action of Buchberger’s algorithm in our specific setting can be understood in entirely combinatorial terms. This was worked out by Thomas in her “Geometric Buchberger Algorithm” [25].

In the following section we collect basic properties of the ideals I_{L}. Some of them appear in more general form in [12], but we include proofs for completeness. In Section 3 we give an explicit combinatorial characterization of the reduced Gröbner basis of I_{L} with respect to any term order. In the toric case this characterization is due to Moulinet & Pottier [19]. In Section 4 we estimate the size of reduced Gröbner bases of a lattice of finite index in ZZ^{n}. This size can be exponential even for n = 3.

In Section 5 we examine the universal Gröbner basis of I_{L}. We characterize it geometrically in terms of the vertices and edges of the associated corner polyhedra. In Section 6 we turn to applications in integer programming. An algebraic localization relates the “global”

Gröbner basis of an integer program (as studied in [1, 9, 25]) and the “local” situation where L has finite index in ZZ^{n}. Finally, in Section 7 we study the simplicial complex associated with the (radical of the) initial ideal init_{ω}(I_{L}). As an application we obtain a new algebraic method for computing face posets of simple polyhedra.

2. The ideal of a lattice

The symbol IN denotes the positive integers including 0. We write 0 for the zero vector in IN^{n} and 1 for the vector with all components equal to 1. The componentwise partial order on IN^{n} is denoted by “≤”. If we write u < v for vectors, then this means u ≤ v and u ≠ v, that is, v − u is nonnegative and at least one coordinate of v − u is positive. We use the notation x^{a} for the monomial x_{1}^{a_{1}}x_{2}^{a_{2}} … x_{n}^{a_{n}}, and the usual decomposition a = a^{+} − a^{−} into positive and negative part, where (a^{+})_{i} = max{a_{i}, 0}, and a^{−} = (−a)^{+} ≥ 0. The partial order a ≤ b corresponds to divisibility of monomials, x^{a} divides x^{b}. Note that a ≤ b implies ωa ≤ ωb for every ω ≥ 0. (Here ω denotes a row vector, so ωa is a scalar product.) We write supp(a) := {i : a_{i} ≠ 0} ⊆ {1, …, n} for the support of a vector, and similarly for monomials supp(x^{a}) := supp(a).

Let L ⊆ ZZ^{n} be an integral lattice. Our basic object of study is the binomial ideal I_{L} = ⟨x^{a^{+}} − x^{a^{−}} : a ∈ L⟩. Every generating set of binomials for I_{L} corresponds to a generating set of L (this follows from Corollary 2.4), but the converse is not true, unless we impose a certain positivity hypothesis. (For example, \{\binom{2}{−1}, \binom{−3}{2}\} is a basis for ZZ^{2}, but the ideal ⟨x^{2} − y, y^{2} − x^{3}⟩ is properly contained in I_{ZZ}^{2} = ⟨x − 1, y − 1⟩.)

Lemma 2.1 Let A = {a_{1}, …, a_{N}} ⊆ ZZ^{n} be a generating set for the lattice L (i.e., L = {∑_{i=1}^{N} λ_{i}a_{i} : λ_{i} ∈ ZZ}). If the sum of the vectors in A ∩ IN^{n} has all its coordinates positive, then the ideal I_{L} coincides with

I_{A} := ⟨x^{a_{i}^{+}} − x^{a_{i}^{−}} : 1 ≤ i ≤ N⟩.

Proof: Clearly we have I_{A} ⊆ I_{L}. The following computation will show that the two ideals coincide. For a, b ∈ A ∩ IN^{n} we have x^{a} − 1, x^{b} − 1 ∈ I_{A}, and thus also

x^{a+b} − 1 = x^{a}(x^{b} − 1) + (x^{a} − 1) ∈ I_{A}.

Hence for every integer M > 0 the ideal I_{A} contains an element x^{m} − 1 with m_{i} ≥ M for all i. Thus, for g = g^{+} − g^{−} ∈ L, we can use

x^{g^{+}} − x^{g^{−}} = −(x^{g^{+}} − x^{g^{−}}) (x^{m} − 1) + x^{m}(x^{g^{+}} − x^{g^{−}})

to see that is suffices to show x^{m}(x^{g^{+}} − x^{g^{−}}) ∈ I_{A} for large enough m_{i} ≥ M. Now since a_{i} and −a_{i} determine the same binomial (up to a sign), we may assume that g is written in the form g = ∑_{k=1}^{K} a_{i_{k}} ∈ L (i.e., as a sum of copies of the vectors a_{i} with coefficients all 1). With this we write

x^{m}(x^{g^{+}} − x^{g^{−}}) = x^{m+g^{−}}(x^{g} − 1) = x^{m+g^{−}}( ∏_{k=1}^{K} x^{a_{i_{k}}} − 1)

= ∑_{k=1}^{K}(x^{m+g^{−}−a_{i_{k}}^{−}} ∏_{l=1}^{k−1} x^{a_{i_{l}}}) (x^{a_{i_{k}}^{+}} − x^{a_{i_{k}}^{−}}),

where the last sum is clearly in I_{A}, provided m_{i} ≥ M is large enough for all i.

The “positive vector condition” on A is satisfied in two basic situations: first, if A is a nonnegative basis for the lattice L (with a_{i} ≥ 0 for all i), and second, if A is any basis of L together with a strictly positive vector in L. Such a positive vector exists if L has finite index in ZZ^{n} but not in general (see also Proposition 3.7).

We will use ≻ to denote term orders on ZZ^{n}, that is, additive total orders such that a ≻ 0 for all a ∈ IN^{n}\0. (We refer to [4] and [10] for the basics about term orders, Gröbner bases, S-pairs, reduction, and the Buchberger algorithm.) It is known (Robbiano [20, Sect. 2]) that every term order can be obtained by refinement of a linear function, that is, for every ≻ there exists a nonzero, nonnegative vector ω ∈ (IR_{≥0})^{n} such that ωa > ωb implies a ≻ b. The refinement is in general obtained lexicographically via a sequence of linear functions. However, every Gröbner basis can also be obtained from a “rank one” term order of the form ≻_{ω}, for some ω ∈ (IR_{>0})^{n} whose components ω_{i} are linearly independent over the rationals, by Mora & Robbiano [18, Thm. 2.7]. Thus, we do not loose anything when, from now on, we assume that ≻ is represented by a positive weight vector ω. We will sometimes write init_{ω}(f) instead of init_{≻}(f) to denote the initial (leading) monomial of a polynomial f with respect to ≻ = ≻_{ω}.

For every nonzero binomial in I_{L} the initial monomial is given by

init_{≻}(x^{a^{+}} − x^{a^{−}}) := \{ \begin{matrix}x^{a^{+}} & if a^{+} ≻ a^{−}, \\ x^{a^{−}} & otherwise. \end{matrix}

Using the term order ≻, we define the positive part of the lattice:

L^{≻0} := {a ∈ L : a ≻ 0},

where a ≻ 0 is equivalent to a^{+} ≻ a^{−}. We can view init_{≻} as a map from L^{≻0} to IN^{n}.

We recall that a subset F of an ideal I is a Gröbner basis of I if and only if the set of initial terms {init_{≻}(f) : f ∈ F} generates the initial ideal init_{≻}(I) := ⟨init(f) : f ∈ I⟩. If F is minimal and no trailing term appearing in any f ∈ F lies in init_{≻}(I) then F is unique and is called the reduced Gröbner basis of I with respect to ≻. Every reduced Gröbner basis of a binomial ideal I consists of binomials. Indeed, starting with a binomial generating set of I, the Buchberger algorithm produces a reduced binomial Gröbner basis, since S-pairs and reduction are binomial-friendly operations.

Proposition 2.2 The initial ideal of a lattice ideal is given by

init_{≻}(I_{L}) = ⟨ x^{u^{+}} : u ∈ L^{≻0} ⟩.

Proof: Clearly, the right hand side is contained in the left hand side. For the converse let x^{a} be a minimal generator of init_{≻}(I_{L}). Since the reduced Gröbner basis consists of binomials, there exists a monomial x^{b} with ωb < ωa such that x^{a} − x^{b} appears in the reduced Gröbner basis of I_{L}. We have a − b ∈ L because the operations of forming S-pairs and reduction (of binomials) preserve the lattice spanned by the differences of the exponent vectors. Let u := a − b and write u = u^{+} − u^{−} ∈ L. Since ωu^{+} > ωu^{−}, we have x^{u^{+}} ∈ init_{≻}(I_{L}). By construction x^{u^{+}} divides x^{a}, and since x^{a} is a minimal generator of init_{≻}(I_{L}), we conclude x^{a} = x^{u^{+}}, as desired.

This proposition motives the following definition.

Definition 2.3 Fix a term order ≻ on IN^{n}. A Gröbner basis of the lattice L is a family G ⊆ L^{≻0} such that {x^{g^{+}} − x^{g^{−}} : g ∈ G} is a Gröbner basis of I_{L}. We denote by RGB_{≻}(L) the set of vectors in L^{≻0} that corresponds to the reduced Gröbner basis of I_{L}.

Corollary 2.4 A binomial x^{a} − x^{b} is contained in I_{L} if and only if a − b ∈ L.

Proof: We must show the only-if direction. Suppose x^{a} − x^{b} ∈ I_{L}. Then the monomials x^{a} and x^{b} have the same normal form, say x^{c}, under reduction with respect to the reduced Gröbner basis of I_{L}. A simple calculation shows that reduction of a monomial by lattice binomials preserves the residue class of the exponent vector with respect to the lattice spanned by the binomials in the Gröbner basis. Therefore a − c ∈ L and b − c ∈ L, and hence a − b ∈ L.

3. Combinatorics of the reduced Gröbner basis

In this section we present a combinatorial characterization of the reduced Gröbner basis of a lattice L, for a fixed term order ≻ = ≻_{ω}. This characterization was first proved by Moulinet & Pottier [19, Thm. 3] in the toric case. We here extend their result to arbitrary integer lattices.

Fix a term order ≻ on IN^{n}. We introduce a new partial order ⊐ on ZZ^{n} as follows:

a ⊐ b  :⟺  either a^{+} ≥ b^{+} and a^{+} ≠ b^{+},
or  a^{+} = b^{+} and a^{−} ≻ b^{−}.

Note that this partial order uses and extends the componentwise partial order “≤” on IN^{n}. The extension is different from ≤ on ZZ^{n}, which is why we need a different symbol. The crucial point is that the partial order ⊐ depends on the term order ≻.

Lemma 3.1 The partial order ⊐ has no infinite antichains, and no infinite decreasing chains. Thus ⊐ defines a well-ordering of ZZ^{n}, and thus, in particular, of (ZZ^{n})^{≻0}.

Proof: This is immediate from the fact that both ≥ and ≻ do not have infinite antichains, or infinite decreasing chains, on the positive orthant IN^{n}.

If P is any subset of ZZ^{n} then MIN_{⊐}(P) denotes the set of minimal elements in P under the partial order ⊐. The main result of this section expresses the reduced Gröbner basis of a lattice as the image of its “positive half” under the operator MIN_{⊐}.

Theorem 3.2 The reduced Gröbner basis of the lattice L equals the set of all minimal elements of L^{≻0} in the partial order ⊐:

RGB_{≻}(L) = MIN_{⊐}(L^{≻0}).

Proof: With Proposition 2.2 and Corollary 2.4, we see that MIN_{⊐}(L^{≻0}) is a minimal Gröbner basis, whose elements cannot be reduced.

Note that in Theorem 3.2 one cannot replace ⊐ by the similar partial order ⊐′ on ZZ^{n} defined by

a ⊐′ b  :⟺  either a^{+} > b^{+},
or  a^{+} = b^{+}, and a^{−} > b^{−}.

which is independent of ≻. Since the term order ≻ is a linear extension of the divisibility order >, we see that ⊐′ is coarser than ⊐ and hence

RGB_{≻}(L) = MIN_{⊐}(L^{≻0}) ⊆ MIN_{⊐′}(L^{≻0}).

However, the right hand side may be much larger than the left hand side, as the following example shows. For N ≥ 1 let L ⊂ ZZ^{3} denote the kernel of the 1 × 3-matrix [N, 1, 1], and let “≻” be the purely lexicographic term order. The reduced Gröbner basis is a lattice basis, MIN_{⊐}(L^{≻0}) = {(1, 0, −N), (0, 1, −1)}, while

MIN_{⊐′}(L^{≻0}) = MIN_{⊐}(L^{≻0}) ∪ { (1, −i, −N + i) : i = 1, 2, …, N − 1 }.

A basic problem in the algorithmic theory of numbers is finding short lattice vectors. Here is a Gröbner basis perspective on this problem.

Corollary 3.3 The set MIN_{⊐}(L^{≻0}) contains the shortest nonnegative vector in L∩IN^{n}, that is, the vector that is minimal with respect to the linear ordering on L ∩ IN^{n} given by the term ordering ≻. In particular, if we take a term order that refines the order of monomials by degrees (like the degree-lexicographic term order), then G contains a vector g ∈ L ∩ IN^{n}\{0} that minimizes the sum of coordinates ∑_{i=1}^{n} g_{i}.

Proof: If b is the unique nonzero vector in L ∩ IN^{n} that minimizes ω, then it cannot be reducible: if we could reduce it by a ∈ L^{≻0} with a ≠ b, then we would immediately obtain a nonnegative vector of smaller weight.

Corollary 3.4 The nonnegative vectors in a reduced Gröbner basis of L have disjoint supports; in particular, RGB_{≻}(L) contains at most n nonnegative vectors. If it contains a strictly positive vector, then it does not contain any other nonnegative vectors.

Proof: If b′, b′′ ∈ RGB_{≻}(L) ∩ IN^{n} have b′_{i}, b′′_{i} > 0 for some i, with b′ ≻ b′′, then we can use the vector b′ − b′′ to reduce b′: a contradiction.

However, although we have just seen that RGB_{≻}(L) ∩ IN^{n} cannot be large, we will show in Section 4 that the cardinality of RGB_{≻}(L) can be exponentially large. If L is a lattice of finite index in ZZ^{n}, then the complement of the initial ideal has the following geometric interpretation.

Corollary 3.5 Let L be a lattice of finite index in ZZ^{n}. Then the set

S := {a ∈ IN^{n} : there is no b ∈ MIN_{⊐}(L^{≻0}) with b^{+} ≤ a}

is a fundamental domain of L, and thus has cardinality det(L).

Proof: A monomial x^{a} is called standard if it does not lie in init_{≻}(I_{L}), that is, if a lies in the set S.

Every monomial reduces to a standard monomial via Buchberger reduction. Thus every point in IN^{n} is mapped to a unique point in the fundamental domain by a sequence of steps which correspond to subtraction of lattice vectors. Furthermore, if two monomials x^{a} and x^{b} are in the same equivalence class modulo L and (without loss of generality) a − b ∈ L^{≻0}, then x^{a} is not standard. This proves that there is a bijection between ZZ^{n}/L and the set S of standard monomials.

Example 3.6 Let L_{A} ⊆ ZZ^{2} be the 2-dimensional lattice of determinant 13 generated by the

columns of A = ( \begin{matrix}1 & 4 \\ 4 & 3 \end{matrix} ).

There are four different reduced Gröbner bases for the corresponding zero-dimensional ideal I_{L}. For example, if we choose a total degree term order that refines the weight vector ω = (1, 1), then L^{≻0} is the set of lattice points above the dotted line. The corresponding Gröbner basis is

G_{(1,1)} = {xy^{4} − 1, x^{3} − y, y^{5} − x^{2}}.

The corresponding three vectors in the Gröbner basis of L are marked by “2”; the cone of all vectors −ω such that ω defines this Gröbner basis is also labelled “2”. The dashed line surrounds the integral points corresponding to the standard monomials.

We close this section with a well-known algorithmic technique for computing the reduced Gröbner basis RGB_{≻}(L). (For toric ideals this technique was introduced in [9].) We embed ZZ^{n} into ZZ^{n+1} by adding a zeroth coordinate, so that ZZ^{n+1} = ZZe_{0} ⊕ ZZ^{n}. Any term order ≻ on ZZ^{n} is extended to ZZ^{n+1} as follows: if a, b ∈ ZZ^{n} then a_{0}e_{0} + a ≻ b_{0}e_{0} + b if and only if either a_{0} > b_{0}, or a_{0} = b_{0} and a ≻ b.

Proposition 3.7 Given any lattice L ⊂ ZZ^{n}, we let L̂ denote the sublattice of ZZ^{n+1} spanned by L and the vector e = ∑_{i=0}^{n} e_{i}. Then

RGB_{≻}(L) = RGB_{≻}(L̂) ∩ ZZ^{n}.

To compute RGB_{≻}(L̂) from any basis for L one can use the remark after the proof of Lemma 2.1: we have e as a strictly positive vector in L̂. When computing RGB_{≻}(L) in practice, many improvements are possible (and yet to be explored). For instance, the experiments reported in Hosten & Sturmfels [15] show that a significant speed-up can be achieved by precomputing a basis of L which is reduced in the sense of Lovász [17].

4. On the size of the Gröbner basis

In this section we examine the size of reduced Gröbner bases of a finite index sublattice L ⊆ ZZ^{n}. We provide upper and lower bounds which are exponential in the bit complexity of a basis for L, even for fixed rank n = 3.

Proposition 4.1 The cardinality of any reduced Gröbner basis of an n-dimensional lattice L ⊆ ZZ^{n} is bounded above by (n − 1) det(L) + 1.

Proof: At most one of the minimal generators of init_{ω}(I_{L}) has full support {1, …, n}. All other minimal generators x^{a} contain at most n−1 variables x_{i}. The monomial x^{a}/x_{i} is one of the det(L) many standard monomials. Hence the number of minimal generators of init_{ω}(I_{L}) not having full support is at most the product (n − 1) det(L).

The slightly weaker upper bound n det(L) is given by Faugère, Gianni, Lazard & Mora [13, Cor. 2.1]. A similar but more careful argument gives the even better upper bound (n − 2) det(L) + n + 1. Bounds for |G| in terms of n and det(L) that are essentially best possible follow from theorems in extremal set theory. The sharp bounds are quite complicated (see Clements [8]), but they imply the following.

Theorem 4.2 The cardinality #RGB of the reduced Gröbner basis of an n-dimensional lattice L ⊆ ZZ^{n} is bounded above by the implication

det(L) < \binom{k}{n}  ⟹  #RGB < \binom{k}{n − 1}

for any integer k ≥ n. In particular, for a fixed number n of variables we have

#RGB = O( (det(L))^{1−1/n} ).

Proof: In the terminology of extremal set theory, see Clements [8], the initial monomials of a reduced Gröbner basis #RGB correspond to an “antichain A of multisets” on the ground set \{1, 2, …, n\} with unrestricted multiplicities k_{i} = ∞. The associated downset \underline{A} corresponds to the set of all monomials dividing one of the initial monomials of #RGB, so the standard monomials correspond to \underline{A}\A, and we have #RGB = |A| and det(L) = |\underline{A}\A|.

Thus we can apply the results of Clements [7, 8]. Essentially the claim follows from the fact that if A is the set of all multisets of a given fized size, then A has the smallest downset among all antichains of the same size |A| (see [7, Theorem on p. 154], [8, p. 256]). Explicitly, we get from [8, Theorem on p. 257] that if #RGB = |A| ≥ \left⟨{n \atop h−1}\right⟩ = \binom{n+h−2}{n−1},

then det(L) = |\underline{A}\A| ≥ ∑_{i=0}^{h−2} \left⟨{n \atop i}\right⟩ = ∑_{i=0}^{h−2} \binom{n+i−1}{i} = \binom{n+h−2}{n}, using that \left⟨{n \atop i}\right⟩ = \binom{n−1+i}{i} for k_{i} = ∞. Now we set k = n + h − 2.

(One may note that the preceding proposition and theorem are more general: with the same proofs, they give upper bounds for the maximal size of a minimal Gröbner basis of a zero-dimensional ideal in terms of the degree and the number of variables.)

We next present a lower bound which matches the upper bound in Proposition 4.1 up to a factor of 2, provided n is allowed to vary.

Proposition 4.3 For each integer n > 1 there exists a lattice L_{n} ⊆ ZZ^{n} with det(L_{n}) = n+1 such that the reduced Gröbner basis of L_{n} with respect to the total degree order has cardinality \frac{1}{2}n(n + 1) = \frac{1}{2}n det(L_{n}).

Proof: Consider the lattice

L_{n} := { (u_{1}, u_{2}, …, u_{n}) ∈ ZZ^{n} : u_{1} + 2u_{2} + 3u_{3} + ⋯ + nu_{n} ≡ 0 mod n + 1 }.

With respect to the total degree ordering on k[x_{1}, x_{2}, …, x_{n}], the reduced Gröbner basis of L_{n} equals

\{ \underline{x_{i}x_{j}} − x_{i+j} : i + j ≤ n \} ∪ \{ \underline{x_{i}x_{j}} − 1 : i + j = n + 1 \}
∪ \{ \underline{x_{i}x_{j}} − x_{i+j−n−1} : i + j ≥ n + 2\}.

Indeed, there are \frac{1}{2}n(n + 1) elements in this set, and each of them is easily seen to lie in I_{L_{n}}. They form a Gröbner basis because precisely n + 1 = det(L_{n}) monomials are not divisible by any of the underlined leading terms. These standard monomials are 1, x_{1}, x_{2}, …, x_{n}.

We next present an exponential lower bound for fixed dimension n = 3.

Theorem 4.4 The reduced Gröbner basis of a finite index sublattice L of ZZ^{3} may have exponential size in the bit complexity of a positive basis of L

Consider the following family of trivariate ideals:

I_{r} := ⟨x^{r}y^{r}z^{r} − 1, x^{r−1}y^{r+1}z^{r−1}, z^{r−2} − 1⟩, r ≥ 4.

The bit complexity of this presentation is O(log(r)). The vector space dimension of the residue ring k[x, y, z]/I_{r} equals 2r(r − 2), which is the determinant of the corresponding lattice

L_{r} = ZZ⟨(r, r, r), (r − 1, r + 1, r − 1), (0, 0, r − 2)⟩ ⊂ ZZ^{3}.

Theorem 4.4 is implied by the following lemma:

Lemma 4.5 The reduced Gröbner basis of I_{r} with respect to degree lexicographic term order equals the following set of 2r − 2 binomials:

\{ \underline{xz} − y, \underline{x^{r−2}} − y^{r−2}, \underline{y^{2r}} − 1\} ∪ \{ \underline{y^{i}z^{r−2−i}} − x^{i} : i = 0, …, r − 3\}
∪ \{\underline{x^{i}y^{2r−i}} − z^{r−2−i} : i = 1, …, r − 3\}.

Proof: This set lies in I_{r} because the vectors

(1, −1, 1), (r − 2, 0, 2 − r), (0, 2r, 0), (−i, i, r − 2 − i), (i, 2r − i, r − 2 − i)

lie in the lattice L_{r}. It suffices to show that there are precisely 2r(r − 2) monomials outside the ideal generated by the underlined leading monomials. We give the complete list of these monomials in three disjoint groups:

(a) x^{a}y^{b} for 0 ≤ a ≤ r − 3, 0 ≤ b ≤ r + 2,

(b) x^{b}y^{a} for r + 3 ≤ a ≤ 2r − 1, 0 ≤ b ≤ 2r − a − 1, and

(c) y^{b}z^{a} for 1 ≤ a ≤ r − 3, 0 ≤ b ≤ r − 3 − a. Each monomial not listed under (a), (b) or (c) is a multiple of one of the underlined terms. The group (a) consists of (r+3)(r−2) monomials, while (b) and (c) consist of \binom{r−2}{2} monomials

each. Thus we have (r + 3)(r − 2) + 2\binom{r−2}{2} = 2r(r − 2) in total.

We close with the observation that n = 3 is best possible.

Remark 4.6 Every reduced Gröbner basis of a sublattice L ⊂ ZZ^{2} has at most three elements.

Proof: Let G be the reduced Gröbner basis of I_{L} with respect to ω. If rank(L) ≤ 1 then I_{L} is principal and G is a singleton. If rank(L) = 2 then the minimal generators of init_{ω}(I_{L}) must have distinct supports. For the support {1, 2} this holds by Corollary 3.4, for the supports {1} and {2} this holds because any two univariate monomials are comparable with respect to divisibility.

5. Geometry of the universal Gröbner basis

The universal Gröbner basis of a sublattice L ⊆ ZZ^{n} is the union of all reduced Gröbner bases of the ideal I_{L} as the cost function varies. In this section we study this set from the point of view of polyhedral geometry. Our results are direct generalizations of Theorem 5.1 in [24], which dealt with the special case where L is saturated and contains no positive vector. Also the proof techniques in this section are extensions of the techniques in [24]. To begin with, we show that the universal Gröbner basis is a finite set, and we present a method for computing a superset of it.

Given any sublattice L of ZZ^{n}, we define a sublattice L̂ of ZZ^{2n} as follows:

L̂ := { u ⊕ (−u) ∈ ZZ^{2n} : u ∈ L }.

Here ZZ^{2n} is to be identified with ZZ^{n} ⊕ ZZ^{n}. Note that any basis of L lifts immediately to a basis of L̂. However, L̂ has no positive basis, so that one needs the algorithm referred to after Proposition 3.7 to compute a generating set for the corresponding ideal I_{L}. We view I_{L} as an ideal in the polynomial ring k[x_{1}, …, x_{n}, y_{1}, …, y_{n}].

Proposition 5.1 Let x^{a} − x^{b} be an element of some reduced Gröbner basis of I_{L}. Then x^{a}y^{b} −x^{b}y^{a} appears in every reduced Gröbner basis of I_{L}. Thus if Ĝ is any reduced Gröbner basis of I_{L}, then {a ∈ ZZ^{n} : x^{a^{+}}y^{a^{−}} − x^{a^{−}}y^{a^{+}} ∈ Ĝ} is a finite set that contains the universal Gröbner basis of L.

Proof: Suppose there exists a reduced Gröbner basis of I_{L} which does not contain x^{a}y^{b} − x^{b}y^{a}. Then there exists x^{c}y^{d} − x^{d}y^{c} in I_{L} such that x^{c}y^{d} divides x^{a}y^{b}. This implies c ≤ a and d ≤ b. Given any term order, the binomial x^{a}−x^{b} can be reduced by x^{c}−x^{d} ∈ I_{L}.

For our main result in this section we shall need the following lemma.

Lemma 5.2 Let x^{a} − x^{b} be an element of the reduced Gröbner basis of L with respect to ω. If c is a point in (a + L) ∩ IN^{n} with ωc ≤ ωa and c ≠ a, then supp(a) ∩ supp(c) = ∅.

Proof: Suppose x^{a} and x^{c} have a common factor x_{i}, and consider the binomial f := (x^{a} − x^{c})/x_{i} = x^{a−e_{i}} − x^{c−e_{i}} ∈ I_{L}. If ωc < ωa, then x^{a−e_{i}} is the leading term of f, which is a contradiction to the hypothesis that x^{a} is a minimal generator of init_{ω}(I_{L}). If ωa = ωc, then a = c.

For any vector b ∈ ZZ^{n} the translate b + L is considered as a residue class of the quotient ZZ^{n}/L. With this residue class we associate the polyhedron

P [b] := conv ((b + L) ∩ IN^{n})

If L has finite index in ZZ^{n} then there are det(L) residue classes. In that case the polyhedra P [b] are called the corner polyhedra of L. They were introduced and studied by Gomory in connection with the group problem in integer programming [14],[21, p. 363]. We shall discuss this problem in Section 6. We also define the polyhedron

Q := conv(L ∩ IN^{n} \ {0}).

In [24] and [25] the polyhedra P [b] were called fibers, and it was assumed that they are polytopes (i.e. bounded). This assumption holds if and only if Q is the empty set.

Theorem 5.3 Let L ⊂ ZZ^{n} be any integer lattice and I_{L} its ideal. Then the universal Gröbner basis of I_{L} consists of the following two sets:

• the binomials x^{a} − 1, where a is a vertex of the polyhedron Q = conv(L ∩ IN^{n} \ {0}),

• the binomials x^{a} − x^{b}, where a − b is a primitive vector in L, supp(a) ∩ supp(b) = ∅, and conv{a, b} is an edge of the corner polyhedron P [a] = P [b].

Proof: With our discussion in Section 3, we can see that the two types of binomials listed above have to lie in the universal Gröbner basis. Namely, the binomials of the first kind are needed (for a suitable function ω) by Corollary 3.3. For binomials of the second type we can choose an objective function ω such that x^{a} is nonstandard and x^{b} is the only monomial of smaller weight in the lattice equivalence class of a. To see that a − b is contained in UGB(I_{L}), it suffices to show that x^{a} is a minimal generator of init_{ω}(I_{L}). If not, then there exists x^{a′} − x^{b′} with leading term x^{a′} such that a′ < a. Then a − a′ + b′ is a lattice point in P [a] having smaller weight than a, hence it must coincide with b. We conclude that a − b = a′ − b′, which gives a contradiction to supp(a) ∩ supp(b) = ∅.

For the converse consider any element x^{a} − x^{b} with leading term x^{a} in the reduced Gröbner basis of I_{L} with respect to ω. If b = 0 then a is the unique minimum of the linear functional ω over all nonnegative nonzero elements of L, which means that a is a vertex of Q. Hence it remains to analyze the case b ≠ 0. We must show that conv{a, b} is an edge of its corner polyhedron. We may assume that all coordinates of ω are positive. Let ω′ be the restriction of ω to the complement of supp(a), that is, ω′_{i} = 0 if a_{i} > 0 and ω′_{i} = ω_{i} if a_{i} = 0. Our hypotheses imply 0 = ω′a < ω′b = ωb < ωa. We define the positive weight vector

ω′′ := (ω(a − b)) · ω′ + (ω′(b − a)) · ω,

which has the property ω′′(a − b) = 0 by construction, and thus ω′′a = ω′′b. In order to prove that conv{a, b} is an edge, it suffices to show ω′′a < ω′′c for all c ∈ IN^{n}\{a, b} with c − a ∈ L.

We distinguish two cases. First suppose that ωc ≤ ωa. Then supp(a) ∩ supp(c) = ∅ by Lemma 5.2, and hence ωc = ω′c. We also know ωc > ωb, otherwise x^{a} − x^{b} wouldn’t be in the reduced Gröbner basis (by Theorem 3.2). This implies

ω′′c = (ω(a − b) + ω′(b − a))ωc > (ω(a − b) + ω′(b − a))ωb = ω′′b = ω′′a.

Next consider the case ωc > ωa. Then we have ω′c ≥ 0 = ω′a, and thus

ω′′c = (ω(a − b))ω′c + (ω′(b − a))ωc > (ω(a − b))ω′a + (ω′(b − a))ωa = ω′′a.

This completes the proof.

For any ideal I ⊂ k[x_{1}, …, x_{n}] there is a natural equivalence relation on the space IR^{n} of weight vectors: We say that ω and ω′ are equivalent if init_{ω}(I) = init_{ω′}(I). It was shown by Mora & Robbiano [18] that the equivalence classes are the cones of a polyhedral fan in IR^{n}, called the Gröbner fan of I. If I is homogeneous then the Gröbner fan is complete, and it was shown by Bayer & Morrison [2] that the Gröbner fan is the normal fan of a polytope in IR^{n}, called the state polytope of I. By an extension of the arguments in [2], one can see that for any ideal I (not necessarily homogeneous) there exists a polyhedron in IR^{n} whose normal fan equals the Gröbner fan. Any such polyhedron will be called a state polyhedron for I.

Theorem 5.4 The Gröbner fan of I_{L} is the common refinement of the normal fans of the corner polyhedra P [b], where b ranges over ZZ^{n}/L.

Proof: It suffices to show that two sufficiently generic weight vectors ω, ω′ ∈ IR_{+}^{n} define the same initial ideal of I if and only if they support the same vertex of P [b] for all b. (See [28] for the basic polyhedral notions used here).

Given a polynomial f ∈ k[x_{1}, …, x_{n}], we write nf_{ω}(f) for its normal form modulo the reduced Gröbner basis of I_{L} with respect to ω. Note that if f = ∑_{a} c_{a}x^{a} is the monomial expansion, then nf_{ω}(f) = ∑_{a} c_{a}nf_{ω}(x^{a}); in other words, nf_{ω}(·) is a k-linear map.

Now, given ω, ω′ ∈ IR_{+}^{n} we have (cf. Mora & Robbiano [18])

init_{ω}(I) = init_{ω′}(I) ⟺ nf_{ω}(f) = nf_{ω′}(f) for all f ∈ k[x_{1}, …, x_{n}]  (1)
⟺ nf_{ω}(x^{a}) = nf_{ω′}(x^{a}) for all monomials x^{a}, a ∈ IN^{n}.

However, the normal form of a monomial x^{a} modulo the binomial ideal I is another monomial, say x^{c}. The vector c ∈ IN^{n} is characterized by the property that c ≡ a mod L, and c has minimum weight ωc with this property. Equivalently, c is the unique vertex of P [a] supported by ω. Therefore, (1) is equivalent to the statement that ω and ω′ support the same vertex of P [a] for all a in IN^{n}.

We recall that the normal fan of a Minkowski sum of two polyhedra is the common refinement of the normal fans of the two polyhedra. This fact extends to the Minkowski sum of any finite number of polyhedra, and it even extends to Minkowski integrals of infinite families of polyhedra (see e.g. [5]). This implies the following corollaries.

Corollary 5.5 Let L be a sublattice of finite index in ZZ^{n}. Then the Minkowski sum of Gomory’s corner polyhedra

∑_{γ∈ZZ^{n}/L}conv(γ ∩ IN^{n}).

is a state polyhedron for the associated zero-dimensional ideal I_{L}.

Corollary 5.6 Let L be any sublattice of ZZ^{n}, and let db be any probability measure with support IN^{n} such that ∫ bdb is a (finite) point in IR_{+}^{n}. Then the Minkowski integral ∫ P [b]db is a state polyhedron for the ideal I_{L}.

6. Localization in integer programming

The problem to minimize a linear functional over the nonnegative elements in a congruence class of a lattice of finite index in ZZ^{m} was studied by Gomory [14]. It is known as the group problem in integer programming (see Schrijver [21, p. 364]). We will show how the group problem appears as a certain algebraic localization from the general integer programming problem. This establishes an algorithmic bridge between the two extreme cases discussed in the introduction, namely, saturated lattices and lattices of finite index.

Our presentation follows [21, p. 364]. It is informal in the sense that no theorems or propositions are stated. Let A be an integer d × n-matrix of rank d, b ∈ ZZ^{d} and ω ∈ IR^{n}. The general integer programming problem can be written as follows:

minimize ω · u subject to u ∈ ZZ^{n}, Au = b, u ≥ 0.  (2)

Let u^{0} ∈ ZZ^{n} be any feasible (but not optimal) solution of (2). Suppose we are also given a basic optimal solution u^{∗} ∈ IR^{n} for the LP-relaxation

minimize ω · u subject to u ∈ IR^{n}, Au = b, u ≥ 0.  (3)

There exists a column basis {i_{1}, …, i_{d}} ⊂ {1, 2, …, n} of A such that supp(u^{∗}) ⊆ {i_{1}, …, i_{d}}. We replace ω by the unique vector ω̃ ∈ IR^{n} with support in [n]\{i_{1}, …, i_{d}} such that ω − ω̃ lies in the row space of A. Let π : ZZ^{n} → ZZ^{n−d} denote the projection onto the nonbasic coordinates. The lattice L := π(ker_{ZZ}(A)) has finite index in ZZ^{n−d}. Identify ω̃ with its image in ZZ^{n−d}, set b̃ := π(u^{0}), and consider the group problem:

minimize ω̃ · v subject to v ∈ ZZ^{n−d}, v ≥ 0, v ≡ b̃ (modL).  (4)

This problem is a relaxation of (2). Indeed, if v^{1} is an optimal solution to (4), then we can choose u^{1} ∈ ZZ^{n} with π(u^{1}) = v^{1} and Au^{1} = b. If u^{1} ≥ 0 then u^{1} is an optimal solution to (2), otherwise ωu^{1} ≥ ωu^{∗} is a new lower bound for the optimum value of (2).

These transformations have a natural reformulation in the setting of Gröbner bases. We recall the Gröbner basis approach to integer programming as presented in [1, 9, 25, 15, 23, 27, 26]. Let L′ ⊂ ZZ^{n} be the kernel of A. Then L′ is saturated and its ideal I_{L′} ⊂ k[x_{1}, …, x_{n}] is the toric ideal of A. The optimal solution of the integer program (2) is obtained by reducing the monomial x^{u^{0}} with respect to the reduced Gröbner basis RGB_{ω}(L′).

Let X = {x_{1}, …, x_{n}} \ {x_{i_{1}}, …, x_{i_{d}}} and consider the homomorphism

ρ : k[x_{1}, …, x_{n}] → k[X]

which maps the variables x_{i_{1}}, …, x_{i_{d}} to 1 and leaves the other variables unchanged. (This amounts to localizing at the prime ideal ⟨x_{j} : j ∉ {i_{1}, …, i_{d}}⟩, whence the title of this section.) We have the following relation among the toric ideal and the zero-dimensional ideal:

ρ( I_{L′}) = I_{L}.

The punchline of our discussion is that, instead of computing RGB_{ω}(L′), it is much easier to compute RGB_{ω}(L), the reduced Gröbner basis of a zero-dimensional binomial ideal. Indeed, the “local Gröbner basis” RGB_{ω}(L) has typically much smaller cardinality than the “global Gröbner basis” RGB_{ω}(L′). The solution to the relaxation (4) is obtained by reducing the monomial xb̃ modulo RGB_{ω}(L).

That the relaxation (4) may fail to have the same optimum as (2) can be explained by the fact that the “global” initial ideal init_{ω}(I_{L′}) is smaller than the preimage in k[x_{1}, …, x_{n}] of the “localized” initial ideal

init_{ω}(I_{L}) = init_{ω}(ρ(I_{L′})) = ρ(init_{ω}(I_{L′})).  (5)

More precisely, the set of right hand sides b for which (4) fails to solve (2) corresponds to embedded primary components of the ideal init_{ω}(I_{A}). This correspondence is studied in [23, Chapter 12].

We remark that, in spite of the identity (5), the \underline{reduced} Gröbner basis RGB_{ω}(L) is generally \underline{not} a subset of ρ(RGB_{ω}(L′)). For instance, take n = 4, d = 1, A = [13, 19, 21, 29] and ω = ω̃ = (41, 50, 10, 0). Here ρ maps the basic variable x_{4} to 1, and L is a sublattice of index 29 in ZZ^{3}. In binomial notation, we have

RGB_{ω}(L) = {x_{3}^{17} − x_{2}^{2}, x_{2}x_{3}^{6} − 1, x_{2}^{3} − x_{3}^{11}, x_{1} − x_{3}^{2}}.

The global Gröbner basis RGB_{ω}(L′) has 14 elements. The local Gröbner basis element x_{2}^{3} − x_{3}^{11} does not appear in ρ(RGB_{ω}(L′)).

7. The initial complex of a lattice

For any ideal I ⊆ k[x_{1}, …, x_{n}] and any term order ω ∈ IR^{n} there is an associated simplicial complex Δ_{ω}(I) with vertex set {1, 2, …, n}. It is called the initial complex [16] and is defined as follows: a subset F ⊆ {1, …, n} is a face of Δ_{ω}(I) if there is no polynomial f ∈ I whose initial monomial init_{ω}(f) has support F. Equivalently, Δ_{ω}(I) is the simplicial complex whose Stanley-Reisner ideal is the radical of init_{ω}(I).

It is our objective to determine the initial complex of a lattice L ⊂ ZZ^{n}. By this we mean Δ_{ω}(L) := Δ_{ω}(I_{L}). Let L_{IR} := L ⊗ IR be the real vector space spanned by L, and let L_{IR}^{⊥} be its orthogonal complement in IR^{n}. We define the closed convex polyhedron

P_{ω} := IR_{+}^{n} ∩ ( ω + L_{IR}^{⊥}).

Lemma 7.1 If the weight vector ω ∈ IR^{n} defines a term order for the ideal I_{L} then the polyhedron P_{ω} is simple.

Proof: Let d = rank(L) and suppose P_{ω} is not simple. Then there exists a point u ∈ P_{ω} such that |supp(u)| ≤ d − 1. This implies the existence of a nonzero vector a ∈ L with supp(a) ∩ supp(u) = ∅. Moreover, we may choose a to have minimal support (i.e., a is a circuit of L_{IR}). This implies ua^{+} = ua^{−} = 0. Moreover, since u − ω ∈ L_{IR}^{⊥}, we have ωa = ua = 0. Therefore both x^{a^{+}} and x^{a^{−}} are contained in the monomial ideal init_{ω}(I). Hence there exists b ∈ L such that ωb = ub > 0 and x^{b^{+}} divides x^{a^{+}}. Since u is nonnegative we conclude 0 < ub^{+} ≤ ua^{+}. This is a contradiction.

Our main result in this section gives an algebraic expression for the combinatorial structure of the polyhedron P_{ω}. In the special case where I_{L} is a homogeneous prime ideal this theorem was proved in [22]. The following version is considerably more general and its proof more direct. We thank Serkan Hosten for suggesting the use of LP-duality in proving Theorem 7.2.

Theorem 7.2 The initial complex Δ_{ω}(L) equals the simplicial complex that is polar to the boundary complex of the simple polyhedron P_{ω}.

Corollary 7.3 The initial complex of a lattice is either a sphere or a ball.

Proof: Our assertion is equivalent to the following statement: A subset F ⊆ {1, …, n} is a face of Δ_{ω}(L) if and only if there exists u ∈ P_{ω} such that supp(u) = {1, …, n}\F. We write e_{F} := ∑_{i∈F} e_{i} for the incidence (row) vector of a subset F.

Let A be an integer d × n-matrix whose rows form a basis for the lattice L, and let b := Aω. By linear programming duality [21, Cor. 7.1.g],

min { e_{F} · u : u ∈ IR^{n}, u ≥ 0, Au = b } = max { v · b : v ∈ IR^{d}, vA ≤ e_{F} }.

This translates into the equivalent statement

min { e_{F} · u : u ∈ P_{ω} } = max { a · ω : a ∈ L_{IR}, a ≤ e_{F} }.

Clearly, the left hand side is nonnegative. It is zero if and only if there is a point u ∈ P_{ω} whose support is contained in {1, …, n}\F. By Lemma 7.1, the family {supp(u): u ∈ P_{ω}} is closed under taking supersets, so that “is contained in” can be replaced by “equals” in the previous sentence. The maximum on the right hand side is positive if and only if there exists a = a^{+} − a^{−} ∈ L with a^{+}ω > a^{−}ω and supp(a^{+}) ⊆ F. This holds if and only if there exists f ∈ I_{L} with supp(init_{ω}(f)) ⊆ F, which is equivalent to F not being a face of Δ_{ω}(L).

As an application we obtain the following algebraic method for computing the minimal nonfaces of a simple polytope.

Corollary 7.4 Let A = (a_{ij}) be a nonnegative integer d × n-matrix with no zero column, and let b ∈ IR^{d} be a general point in the cone spanned by the columns of A. Then P = {u ∈ IR^{n} : u ≥ 0, Au = b } is a simple polytope. Its boundary complex is polar to the initial complex, with respect to any weight vector ω ∈ P, of the ideal

I = ⟨ ∏_{j=1}^{n}x_{ij}^{a_{ij}} − 1 : i = 1, …, d ⟩.

Proof: The assumption that A is nonnegative and has no zero column implies (using Lemma 2.1) that I = I_{L} where L is the lattice spanned by the rows of A. Corollary 7.4 now follows from Theorem 7.2 by identifying u = ω.

In order to compute the (supports of the) vertices of the polytope P, we need to find the minimal associated primes of the initial ideal init_{ω}(I).

Corollary 7.5 Using the notation above, we have the prime decomposition

Rad(init_{ω}(I)) = _{v vertex of P}^{⋂}⟨x_{i} : i ∈ supp(v)⟩.

Naturally these corollaries are most useful for practical computations when the ideal init_{ω}(I) is square-free to begin with. A sufficient condition for this property can be given using [24, Thm. 3.17]: if L is the row span of a unimodular matrix then init_{ω}(I) is a radical ideal. We illustrate our techniques for such a unimodular example.

Example 7.6 (A Simple 3 × 5-Transportation Polytope) Let X = (x_{ij}) be a 3 × 5-matrix of indeterminates, and let L be the sublattice of ZZ^{15} ≅ ZZ^{3} ⊗ ZZ^{5} defined by the binomial ideal

I_{L} = ⟨x_{11}x_{12}x_{13}x_{14}x_{15} − 1, x_{21}x_{22}x_{23}x_{24}x_{25} − 1, x_{31}x_{32}x_{33}x_{34}x_{35} − 1,
x_{11}x_{21}x_{31} − 1, x_{12}x_{22}x_{32} − 1, x_{13}x_{23}x_{33} − 1, x_{14}x_{24}x_{34} − 1, x_{15}x_{25}x_{35} − 1⟩.

Let ω be the 3 × 5-matrix with all entries equal to 1. This weight matrix defines the total degree term order for I_{L}. The polytope P_{ω} is the set consisting of all real nonnegative 3 × 5matrices with all row sums equal to 5 and all column sums equal to 3. In order to compute this transportation polytope, we compute the reduced Gröbner basis of I_{L} with respect to ω. It consists of 50 binomials of degrees three and four. Since L is unimodular, the initial ideal is square-free:

init_{ω}(I_{L}) = ⟨x_{11}x_{12}x_{13}x_{14}, x_{11}x_{12}x_{13}x_{15}, x_{11}x_{12}x_{14}x_{15}, …, x_{32}x_{33}x_{34}x_{35}⟩.

Using a computer algebra system such as MACAULAY [3] it takes a fraction of a second to determine the prime decomposition as in Corollary 7.5. We find that the simple polytope P_{ω} has dimension 7 and has 360 vertices. By computing the numerator of the Hilbert series of init_{ω}(I_{L}), we find its h-vector to be h(P_{ω}) = (1, 7, 28, 79, 130, 79, 28, 7, 1).

References

[1] W. W. Adams & P. Loustaunau: An Introduction to Gröbner Bases, American Mathematical Society, Graduate Studies in Math., Vol. III, 1994.

[2] D. Bayer & I. Morrison: Gröbner bases and geometric invariant theory I, J. Symbolic Computation 6 (1988), 209-217.

[3] D. Bayer & M. Stillman: Macaulay: a computer algebra system for algebraic geometry, available by anonymous ftp from zariski.harvard.edu.

[4] T. Becker & V. Weispfenning: Gröbner Bases: A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics 141, Springer-Verlag 1993.

[5] L. J. Billera & B. Sturmfels: Fiber polytopes, Annals of Mathematics 135 (1992), 527-549.

[6] B. Buchberger: Gröbner bases: an algorithmic method in polynomial ideal theory, in: N.K. Bose (ed.), “Multidimensional Systems Theory”, D. Reidel 1985, 184-232.

[7] G. F. Clements: The minimal number of basic elements in a multiset antichain J. Combinatorial Theory, Ser. A 25 (1978), 153-162.

[8] G. F. Clements: Multiset antichains having minimal downsets, J. Combinatorial Theory, Ser. A 48 (1988), 255-258.

[9] P. Conti & C. Traverso: Buchberger algorithm and integer programming, Proceedings AAECC-9 (New Orleans), Springer LNCS 539, 1991, pp. 130-139.

[10] D. A. Cox, J. B. Little & D. O’Shea: Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, Springer-Verlag, New York 1992.

[11] P. Diaconis, B. Sturmfels: Algebraic algorithms for sampling from conditional distributions, Annals of Statistics, to appear.

[12] D. Eisenbud & B. Sturmfels: Binomial ideals, preprint 1994, 44 pages.

[13] J. C. Faugère, P. Gianni, D. Lazard & T. Mora: Efficient computation of zerodimensional Gröbner bases by change of ordering, J. Symbolic Computation 16 (1993), 329-344.

[14] R. E. Gomory: Some polyhedra related to combinatorial problems, Linear Algebra and its Applications 2 (1969), 451-455.

[15] S. Hosten & B. Sturmfels: GRIN: An implementation of Gröbner bases for integer programming, Proceedings IPCO IV (Copenhagen), Springer LNCS, 1995, to appear.

[16] M. Kalkbrener & B. Sturmfels: Initial complexes of prime ideals, Advances in Mathematics, to appear.

[17] A. K. Lenstra, H. W. Lenstra & L. Lovász: Factoring polynomials with rational coefficients, Math. Annalen 261 (1982), 513–534.

[18] T. Mora & L. Robbiano: The Gröbner fan of an ideal, J. Symbolic Computation 6 (1988), 183-208.

[19] C. Moulinet & L. Pottier: Gröbner bases of toric ideals: properties, algorithms, and applications, preprint, INRIA Sophia Antipolis, 10 pages.

[20] L. Robbiano: On the theory of graded structures, J. Symbolic Computation 2 (1986), 139-170.

[21] A. Schrijver: Theory of Linear and Integer Programming, Wiley-Interscience, Chichester 1986.

[22] B. Sturmfels: Gröbner bases of toric varieties, Tôhoku Math. Journal 43 (1991), 249-261.

[23] B. Sturmfels: Gröbner Bases and Convex Polytopes, American Mathematical Society, Providence, R.I., to appear in 1996.

[24] B. Sturmfels & R. R. Thomas: Variation of cost functions in integer programming, preprint, Cornell University 1994, 31 pages.

[25] R. R. Thomas: A geometric Buchberger algorithm for integer programming, Mathematics of Operations Research, to appear.

[26] R. R. Thomas & R. Weismantel: A multivariate grading and truncated Gröbner bases for toric ideals in integer programming, Preprint SC 95-09, ZIB-Berlin, March 1995, 13 pages.

[27] R. Urbaniak, R. Weismantel & G. M. Ziegler: A variant of the Buchberger algorithm for integer programming, Preprint SC 94-29, ZIB-Berlin, January 1995, 19 pages.

[28] G. M. Ziegler: Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York 1995.

Received April 28, 1995