Monomial Ideals

Serkan Hoşten and Gregory G. Smith

Monomial ideals form an important link between commutative algebra and combinatorics. In this chapter, we demonstrate how to implement algorithms in Macaulay 2 for studying and using monomial ideals. We illustrate these methods with examples from combinatorics, integer programming, and algebraic geometry.

An ideal I in S = ℚ[x_{1}, …, x_{n}] is called a monomial ideal if it satisfies any of the following equivalent conditions:

(a) I is generated by monomials,

(b) if f = ∑_{α∈ℕ^{n}} k_{α}x^{α} belongs to I then x^{α} ∈ I whenever k_{α} ≠ 0,

(c) I is torus-fixed; in other words, if (c_{1}, …, c_{n}) ∈ (ℚ^{∗})^{n}, then I is fixed under the action x_{i} ↦ c_{i}x_{i} for all i.

It follows that a monomial ideal is uniquely determined by the monomials it contains. Most operations are far simpler for a monomial ideal than for an ideal generated by arbitrary polynomials. In particular, many invariants can be effectively determined for monomial ideals. As a result, one can solve a broad collection of problems by reducing to or encoding data in a monomial ideal. The aim of this chapter is to develop the computational aspects of monomial ideals in Macaulay 2 and demonstrate a range of applications.

This chapter is divided into five sections. Each section begins with a discussion of a computational procedure involving monomial ideals. Algorithms are presented as Macaulay 2 functions. We illustrate these methods by solving problems from various areas of mathematics. In particular, we include the Macaulay 2 code for generating interesting families of monomial ideals. The first section introduces the basic functions on monomial ideals in Macaulay 2. To demonstrate these functions, we use the Stanley-Reisner ideal associated to a simplicial complex to compute its f-vector. Next, we present two algorithms for finding a primary decomposition of a monomial ideal. In a related example, we use graph ideals to study the complexity of determining the codimension of a monomial ideal. The third section focuses on the standard pairs of a monomial ideal; two methods are given for finding the set of standard pairs. As an application, we use standard pairs to solve integer linear programming problems. The fourth section examines Borel-fixed ideals and generic initial ideals. Combining these constructions with distractions, we demonstrate that the Hilbert scheme Hilb^{4t+1}(ℙ^{4}) is connected. Finally, we look at the chains of associated primes in various families of monomial ideals.

1 The Basics of Monomial Ideals

Creating monomial ideals in Macaulay 2 is analogous to creating general ideals. The monomial ideal generated by a sequence or list of monomials can be constructed with the function monomialIdeal.

    i1 : S = QQ[a, b, c, d];
    i2 : I = monomialIdeal(a^2, a*b, b^3, a*c)
                         2        3
    o2 = monomialIdeal (a , a*b, b , a*c)
    o2 : MonomialIdeal of S
    i3 : J = monomialIdeal{a^2, a*b, b^2}
                         2        2
    o3 = monomialIdeal (a , a*b, b )
    o3 : MonomialIdeal of S

The type MonomialIdeal is the class of all monomial ideals. If an entry in the sequence or list is not a single monomial, then monomialIdeal takes only the leading monomial; recall that every polynomial ring in Macaulay 2 is equipped with a monomial ordering.

    i4 : monomialIdeal(a^2+a*b, a*b+3, b^2+d)
                         2        2
    o4 = monomialIdeal (a , a*b, b )
    o4 : MonomialIdeal of S

There are also several methods of associating a monomial ideal to an arbitrary ideal in a polynomial ring. The most important of these is the initial ideal — the monomial ideal generated by the leading monomials of all elements in the given ideal. When applied to an Ideal, the function monomialIdeal returns the initial ideal.

    i5 : K = ideal(a^2, b^2, a*b+b*c)
                 2   2
    o5 = ideal (a , b , a*b + b*c)
    o5 : Ideal of S
    i6 : monomialIdeal K
                         2        2     2
    o6 = monomialIdeal (a , a*b, b , b*c )
    o6 : MonomialIdeal of S

This is equivalent to taking the leading monomials of a Gröbner basis for K. In our example, the given generators for K are not a Gröbner basis.

    i7 : monomialIdeal gens K
                         2        2
    o7 = monomialIdeal (a , a*b, b )
    o7 : MonomialIdeal of S

One can also test if a general ideal is generated by monomials with the

function isMonomialIdeal.
    i8 : isMonomialIdeal K
    o8 = false
    i9 : isMonomialIdeal ideal(a^5, b^2*c, d^11)
    o9 = true

The usual algebraic operations on monomial ideals are the same as on general ideals. For example, we have

    i10 : I+J
                          2        2
    o10 = monomialIdeal (a , a*b, b , a*c)
    o10 : MonomialIdeal of S

Example: Stanley-Reisner Ideals and f-vectors

Radical monomial ideals — ideals generated by squarefree monomials — have a beautiful combinatorial interpretation in terms of simplicial complexes. More explicitly, a simplicial complex Δ on the vertex set {x_{1}, …, x_{n}} corresponds to the ideal I_{Δ} in S = ℚ[x_{1}, …, x_{n}] generated by all monomials x_{i_{1}} ⋯ x_{i_{p}} such that {x_{i_{1}}, …, x_{i_{p}}} ∉ Δ. The ideal I_{Δ} is called the Stanley-Reisner ideal of Δ.

To illustrate the connections between Stanley-Reisner ideals and simplicial complexes, we consider the f-vector. Perhaps the most important invariant of a simplicial complex, the f-vector of a d-dimensional simplicial complex Δ is (f_{0}, f_{1}, …, f_{d}) ∈ ℕ^{d+1}, where f_{i} denotes the number of i-dimensional faces in Δ. From the monomial ideal point of view, the f-vector is encoded in the Hilbert series of the quotient ring S/I_{Δ} as follows:

Theorem 1.1. If Δ is a simplicial complex with f-vector (f_{0}, …, f_{d}), then the Hilbert series of S/I_{Δ} is

H_{S/I_{Δ}}(t) = ∑_{i=−1}^{d} \frac{f_{i}t^{i+1}}{(1 − t)^{i+1}} ,

where f_{−1} = 1.

4  S. Hoşten and G. G. Smith

Proof. Following Stanley [24], we work with the fine grading and then specialize. The fine grading of S is the ℤ^{n}-grading defined by deg x_{i} = e_{i} ∈ ℤ^{n}, where e_{i} is the i-th standard basis vector. The support of a monomial x^{α} is defined to be the set supp(x^{α}) = {x_{i} : α_{i} > 0}. Observe that x^{α} ≠ 0 in S/I_{Δ} if and only if supp(x^{α}) ∈ Δ. Moreover, the nonzero monomials x^{α} form a ℚ-basis of S/I_{Δ}. By counting such monomials according to their support, we obtain the following expression for the Hilbert series with the fine grading:

H_{S/I_{Δ}}(t) = ∑_{F ∈Δ} ∑_{\begin{matrix}α∈ℕ^{n} \\ supp(x^{α})=F \end{matrix}} t^{α} = ∑_{F ∈Δ} ∏_{x_{i}∈F} \frac{t_{i}}{1 − t_{i}} .

Finally, by replacing each t_{i} with t, we complete the proof. ⊓ ⊔

Since H_{S/I_{Δ}}(t) is typically expressed in the form \frac{h_{0}+h_{1}t+···+h_{d}t^{d}}{(1−t)^{d+1}} , we can

obtain the f-vector by using the identity ∑_{i} h_{i}t^{i} = ∑_{j=0}^{d} f_{j−1}t^{j}(1−t)^{d−j}. In particular, we can compute f-vectors from Stanley-Reisner ideals as follows:

i11 : fvector = I -> (
           R := (ring I)/I;
           d := dim R;
           N := poincare R;
           t := first gens ring N;
           while 0 == substitute(N, t => 1) do N = N // (1-t);
           h := apply(reverse toList(0..d), i -> N_(t^i));
           f := j -> sum(0..j+1, i -> binomial(d-i, j+1-i)*h#(d-i));
           apply(toList(0..d-1), j -> f(j)));

For example, we can demonstrate that the f-vector of the octahedron is (6, 12, 8).

i12 : S = QQ[x_1 .. x_6];
i13 : octahedron = monomialIdeal(x_1*x_2, x_3*x_4, x_5*x_6)
o13 = monomialIdeal (x x , x x , x x )
                      1 2   3 4   5 6
o13 : MonomialIdeal of S
i14 : fvector octahedron
o14 = {6, 12, 8}
o14 : List

More generally, we can recursively construct simplicial 2-spheres with f_{0} ≥ 4, starting with the tetrahedron, by pulling a point in the relative interior of a facet. This procedure leads to the following family:

i15 : simplicial2sphere = v -> (
           S := QQ[x_1..x_v];
           if v === 4 then monomialIdeal product gens S
           else (
                L := {};
                scan(1..v-4, i -> L = L | apply(v-i-3,
                          j -> x_i*x_(i+j+4)));
                scan(2..v-3, i -> L = L | {x_i*x_(i+1)*x_(i+2)});
                monomialIdeal L));
i16 : apply({4,5,6,7,8}, j -> fvector simplicial2sphere(j))
o16 = {{4, 6, 4}, {5, 9, 6}, {6, 12, 8}, {7, 15, 10}, {8, 18, 12}}
o16 : List

Fig. 1. The octahedron

In fact, it follows from Euler’s formula that the f-vector of any simplicial 2-sphere has the form (v, 3v − 6, 2v − 4) for v ≥ 4. The problem of characterizing the f-vectors for triangulations of d-spheres is open for d ≥ 3. One of the most important results in this direction is the upper bound theorem for simplicial spheres (Corollary 5.4.7 Bruns and Herzog [6]) which states that the cyclic polytope has the maximal number of i-faces for all i. We point out that Stanley’s proof of this theorem depends heavily on these methods from commutative algebra.

On the other hand, the f-vectors for several major classes of simplicial complexes have been characterized. The Kruskal-Katona theorem (Theorem 8.32 in Ziegler [29]) gives necessary and sufficient conditions for a sequence of nonnegative integers to be an f-vector of a simplicial complex. Stanley [24] describes the f-vectors of pure shellable complexes and Cohen-Macaulay complexes. Given the Betti numbers of a simplicial complex, Björner and Kalai [5] specify the f-vectors. Finally, the g-theorem (Theorem 8.35 in Ziegler [29]) characterizes the f-vectors for boundary complexes of a simplicial convex polytope.

For a further study of Stanley-Reisner ideals see Bruns and Herzog [6] and Stanley [24]. For more information of f-vectors, see Ziegler [29] and Björner [4].

2 Primary Decomposition

A primary decomposition of an ideal I is an expression of I as a finite intersection of primary ideals; an ideal J is called primary if r_{1}r_{2} ∈ J implies either r_{1} ∈ J or r_{2}^{ℓ} ∈ J for some ℓ > 0. Providing an algorithm for computing the primary decomposition of an arbitrary ideal in a polynomial ring is quite difficult. However, for monomial ideals, there are two algorithms which are relatively simple to describe.

We first present a recursive method for generating an irreducible primary decomposition. It is based on the following two observations.

Lemma 2.1. Let I be a monomial ideal in S = ℚ[x_{1}, …, x_{n}].

(1) If I is generated by pure powers of a subset of the variables, then it is a primary ideal.

(2) If r is minimal generator of I such that r = r_{1}r_{2} where r_{1} and r_{2} are relatively prime, then I = (I + ⟨r_{1}⟩) ∩ (I + ⟨r_{2}⟩).

Proof. (1) This follows immediately from the definition of primary. (2) Since I is a monomial ideal, it is enough to show that I and (I + ⟨r_{1}⟩) ∩ (I + ⟨r_{1}⟩) contain the same monomials. A monomial r′ belongs to (I + ⟨r_{j}⟩) if and only if r′ ∈ I or r_{j} divides r′. Because r_{1} and r_{2} are relative prime, we have

r′ ∈ (I + ⟨r_{1}⟩) ∩ (I + ⟨r_{1}⟩) ⇔ r′ ∈ I or r_{1}r_{2} divides r′ ⇔ r′ ∈ I . ⊓ ⊔

The following is an implementation of the resulting algorithm:

    i17 : supp = r -> select(gens ring r, e -> r % e == 0);
    i18 : monomialDecompose = method();
    i19 : monomialDecompose List := L -> (
               P := select(L, I -> all(first entries gens I,
                         r -> #supp(r) < 2) === false);
               if #P > 0 then (
                    I := first P;
                    m := first select(first entries gens I,
                         r -> #supp(r) > 1);
                    E := first exponents m;
                    i := position(E, e -> e =!= 0);
                    r1 := product apply(E_{0..i}, (gens ring I)_{0..i},
                         (j, r) -> r^j);
                    r2 := m // r1;
                    monomialDecompose(delete(I, L) | {I+monomialIdeal(r1),
                              I+monomialIdeal(r2)}))
               else L);
    i20 : monomialDecompose MonomialIdeal := I -> monomialDecompose {I};

Here is a small example illustrating this method.

    i21 : S = QQ[a,b,c,d];
    i22 : I = monomialIdeal(a^3*b, a^3*c, a*b^3, b^3*c, a*c^3, b*c^3)
                          3      3   3    3      3     3
    o22 = monomialIdeal (a b, a*b , a c, b c, a*c , b*c )
    o22 : MonomialIdeal of S
    i23 : P = monomialDecompose I;
    i24 : scan(P, J -> << endl << J << endl);
    monomialIdeal (b, c)
    monomialIdeal (a, c)

                    3   3   3
    monomialIdeal (a , b , c )
    monomialIdeal (a, b)
                    3      3
    monomialIdeal (a , b, c )
    monomialIdeal (a, b)
                       3   3
    monomialIdeal (a, b , c )
    i25 : I == intersect(P)
    o25 = true

As we see from this example, this procedure doesn’t necessarily yield an irredundant decomposition.

The second algorithm for finding a primary decomposition of a monomial ideal I is based on the Alexander dual of I. The Alexander dual was first introduced for squarefree monomial ideals. In this case, it is the monomial ideal of the dual of the simplicial complex Δ corresponding to I. By definition the dual complex of Δ is Δ^{∨} = {F : F^{c} ∉ Δ}, where F^{c} = {x_{1}, …, x_{n}} \ F. The following general definition appears in Miller [16], [17]. If I ⊆ ℚ[x_{1}, …, x_{n}] is a monomial ideal and x^{λ} is the least common multiple of the minimal generators of I, then the Alexander dual of I is

I^{∨} = ⟨ ∏_{β_{i}>0} x_{i}^{λ_{i}+1−β_{i}} : \begin{matrix}⟨x_{i}^{β_{i}} : β_{i} ≥ 1⟩ is an irredundant \\ irreducible component of I \end{matrix} ⟩ .

In particular, the minimal generators of I^{∨} correspond to the irredundant irreducible components of I. The next proposition provides a useful way of computing I^{∨} given a set of generators for I.

Proposition 2.2. If I is a monomial ideal and x^{λ} is the least common multiple of the minimal generators of I, then the generators for I^{∨} are those generators of the ideal (⟨x_{1}^{λ_{1}+1}, …, x_{n}^{λ_{n}+1}⟩ : I) that are not divisible by x_{i}^{λ_{i}+1} for 1 ≤ i ≤ n.

Proof. See Theorem 2.1 in Miller [16]. ⊓ ⊔

Miller’s definition of Alexander dual is even more general than the one above. The resulting algorithm for computing this general Alexander dual and primary decomposition are implemented in Macaulay 2 as follows. For the Alexander dual we use, the list a that appears as an input argument for dual should be list of exponents of the least common multiple of the minimal generators of I.

    i26 : code(dual, MonomialIdeal, List)

o26 = -- ../../../m2/monideal.m2:260-278
dual(MonomialIdeal, List) := (I,a) -> ( -- Alexander dual
R := ring I;
X := gens R;
aI := lcmOfGens I;
if aI =!= a then (
     if #aI =!= #a
     then error (
          "expected list of length ",
          toString (#aI));
     scan(a, aI,
          (b,c) -> (
               if b<c then
               error "exponent vector not large enough"
               ));
     );
S := R/(I + monomialIdeal apply(#X, i -> X#i^(a#i+1)));
monomialIdeal contract(
     lift(syz transpose vars S, R),
     product(#X, i -> X#i^(a#i))))
i27 : code(primaryDecomposition, MonomialIdeal)
o27 = -- ../../../m2/monideal.m2:286-295
primaryDecomposition MonomialIdeal := (I) -> (
R := ring I;
aI := lcmOfGens I;
M := first entries gens dual I;
L := unique apply(#M, i -> first exponents M_i);
apply(L, i -> monomialIdeal apply(#i, j -> (
               if i#j === 0 then 0_R
               else R_j^(aI#j+1-i#j)
               )))
)

This direct algorithm is more efficient than our recursive algorithm. In particular, it gives an irredundant decomposition. For example, when we use it to determine a primary decomposition for the ideal I above, we obtain

i28 : L = primaryDecomposition I;
i29 : scan(L, J -> << endl << J << endl);
     3   3   3
monomialIdeal (a , b , c )
monomialIdeal (b, c)
monomialIdeal (a, b)
monomialIdeal (a, c)
i30 : I == intersect L
o30 = true

For a family of larger examples, we consider the tree ideals:

⟨(_{∏i∈F} x_{i})^{n−|F |+1} : ∅ ≠ F ⊆ {x_{1}, …, x_{n}}⟩ .

These ideals are so named because their standard monomials (the monomials not in the ideal) correspond to trees on n + 1 labeled vertices. We determine the number of irredundant irreducible components as follows:

    i31 : treeIdeal = n -> (
               S = QQ[vars(0..n-1)];
               L := delete({}, subsets gens S);
               monomialIdeal apply(L, F -> (product F)^(n - #F +1)));
    i32 : apply(2..6, i -> #primaryDecomposition treeIdeal i)
    o32 = (2, 6, 24, 120, 720)
    o32 : Sequence

Example: Graph Ideals and Complexity Theory

Monomial ideals also arise in graph theory. Given a graph G with vertices {x_{1}, …, x_{n}}, we associate the ideal I_{G} in ℚ[x_{1}, …, x_{n}] generated by the quadratic monomials x_{i}x_{j} such that x_{i} is adjacent to x_{j}. The primary decomposition of I_{G} is related to the graph G as follows. Recall that a subset F ⊆ {x_{1}, …, x_{n}} is called a vertex cover of G if each edge in G is incident to at least one vertex in F.

Lemma 2.3. If G is a graph and C is the set of minimal vertex covers of G then the irreducible irredundant primary decomposition of I_{G} is ⋂_{F ∈C} P_{F^{c}}, where P_{F^{c}} is the prime ideal ⟨x_{i} : x_{i} ∉ F^{c}⟩ = ⟨x_{i} : x_{i} ∈ F ⟩.

Proof. Since each generator of I_{G} corresponds to an edge in G, it follows from the monomialDecompose algorithm that I_{G} has an irreducible primary decomposition of the form: I_{G} = ⋂ P_{F^{c}}, where F is a vertex cover. To obtain an irredundant decomposition, one clearly needs only the minimal vertex covers. ⊓ ⊔

As an application of graph ideals, we examine the complexity of determining the codimension of a monomial ideal. In fact, following Bayer and Stillman [3], we prove

Proposition 2.4. The following decision problem is NP-complete:

Given a monomial ideal I ⊆ ℚ[x_{1}, …, x_{n}] and
m ∈ ℕ, is codim I ≤ m?

(Codim)

By definition, a decision problem is NP-complete if all other problems in the class NP can be reduced to it. To prove that a particular problem is NP-complete, it suffices to show: (1) the problem belongs to the class NP; (2) some known NP-complete problem reduces to the given decision problem (see Lemma 2.3 in Garey and Johnson [8]). One of the “standard NP-complete” problems (see section 3.1 in Garey and Johnson [8]) is the following:

Given a graph G and m ∈ ℕ, is there a vertex cover F such that |F | ≤ m?

(Vertex Cover)

Proof of Proposition. (1) Observe that a monomial ideal I has codimension at most m if and only if I ⊆ P_{F^{c}} for some F with |F | ≤ m. Now, if I has codimension at most m, then given an appropriate choice of F, one can verify in polynomial time that I ⊆ P_{F^{c}} and |F | ≤ m. Therefore, the Codim problem belongs to the class NP.

(2) Lemma 2.3 implies that I_{G} has codimension m if and only if G has a vertex cover of size at most m. In particular, the Vertex Cover problem reduces to the Codim problem. ⊓ ⊔

Thus, assuming P ≠ NP, there is no polynomial time algorithm for finding the codimension of a monomial ideal. Nevertheless, we can effectively compute the codimension for many interesting examples.

To illustrate this point, we consider the following family of examples. Let S = ℚ[X] denote the polynomial ring generated by the entries of a generic m × n matrix X = [x_{i,j}]. Let I_{k} be the ideal generated by the k × k minors of X. Since the Hilbert function of S/I_{k} equals the Hilbert function of S/ in(I_{k}) (see Theorem 15.26 in Eisenbud [7]), we can determine the codimension I_{k} by working with the monomial ideal in(I_{k}). Because Sturmfels [25] shows that the set of k × k-minors of X is the reduced Gröbner basis of I_{k} with respect to the lexicographic term order induced from the variable order

x_{1,n} > x_{1,n−1} > ⋯ > x_{1,1} > x_{2,n} > ⋯ > x_{2,1} > ⋯ > x_{m,n} > ⋯ > x_{m,1} ,

we can easily calculate in(I_{k}). In particular, in Macaulay 2 we have

    i33 : minorsIdeal = (m,n,k) -> (
               S := QQ[x_1..x_(m*n), MonomialOrder => Lex];
               I := minors(k, matrix table(m, n, (i,j) -> x_(i*n+n-j)));
               forceGB gens I;
               I);
    i34 : apply(2..8, i -> time codim monomialIdeal minorsIdeal(i,2*i,2))
         -- used 0.02 seconds
         -- used 0.05 seconds
         -- used 0.1 seconds
         -- used 0.36 seconds
         -- used 1.41 seconds
         -- used 5.94 seconds
         -- used 25.51 seconds
    o34 = (3, 10, 21, 36, 55, 78, 105)
    o34 : Sequence

The properties of I_{k} are further developed in chapter 11 of Sturmfels [26] and chapter 7 of Bruns and Herzog [6]

For more on the relationships between a graph and its associated ideal, see Villarreal [28], Simis, Vasconcelos and Villarreal [23], and Ohsugi and Hibi [19].

    i35 : erase symbol x;

3 Standard Pairs

In this section, we examine a combinatorial object associated to a monomial ideal. In particular, we present two algorithms for computing the standard pairs of a monomial ideal from its minimal generators. Before giving the definition of a standard pair, we consider an example.

Fig. 2. Staircase diagram for I = ⟨xy^{3}z, xy^{2}z^{2}, y^{3}z^{2}, y^{2}z^{3}⟩

Example 3.1. Let I = ⟨xy^{3}z, xy^{2}z^{2}, y^{3}z^{2}, y^{2}z^{3}⟩ in ℚ[x, y, z]. We identify the monomials in ℚ[x, y, z] with the lattice points in ℕ^{3}; see Figure 2. The standard monomials of I, those monomials which are not in I, can be enumerated as follows: (i) monomials corresponding to lattice points in the xy-plane, (ii) monomials corresponding to lattice points in the xz-plane, (iii) monomials corresponding to lattice points in the plane parallel to the xz-plane containing (0, 1, 0), (iv) monomials corresponding to lattice points on the line parallel to the y-axis containing (0, 0, 1), (v) monomials corresponding to lattices point on the line parallel to the x-axis containing (0, 2, 1), and (vi) the monomial y^{2}z^{2}.

Following Sturmfels, Trung and Vogel [27], we make the following definitions. Given a monomial x^{α} and a subset F ⊆ {x_{1}, …, x_{n}}, we index the set of monomials of the form x^{α} · x^{β} where supp(x^{β}) ⊆ F by the pair (x^{α}, F). A standard pair of a monomial ideal I is a pair (x^{α}, F) satisfying the following three conditions:

(1) supp(x^{α}) ∩ F = ∅, (2) all of the monomials represented by this pair are standard, and

(3) (x^{α}, F) ⊈ (x^{β}, G) for any other pair (x^{β}, G) satisfying the first two conditions.

Hence, the six standard pairs

(1, {x, y}), (1, {x, z}), (y, {x, z}), (z, {y}), (y^{2}z, {x}), (y^{2}z^{2}, ∅)

in Example 3.1 correspond to (i)–(vi).

Observe that the set of standard pairs of I gives an irreducible decomposition of I = ⋂⟨x_{i}^{α_{i}+1} : x_{i} ∉ F ⟩, where the intersection is over all standard pairs (x^{α}, F). Moreover, the prime ideal P_{F} := ⟨x_{i} : x_{i} ∉ F ⟩ is an associated prime of I if and only if there exists a standard pair of the form (•, F); see Sturmfels, Trung and Vogel [27] for details.

Our first algorithm for computing the set of standard pairs is taken from Hoşten and Thomas [15]. The ideas behind it are as follows: given a witness w_{1} = x^{α} for the associated prime P_{F} := ⟨x_{i} : x_{i} ∉ F ⟩, that is (I : x^{α}) = P_{F}, set w_{2} = ∏_{x_{i}∈supp(w_{1})∩F^{c}} x_{i}^{α_{i}}. It follows that (w_{2}, F) is a standard pair of I. Now, consider the standard pairs of the slightly larger ideal I + ⟨w_{1}⟩. Clearly (w_{2}, F) is not a standard pair of this ideal because w_{1} “destroys” it. This larger ideal might have standard pairs which cover standard monomials in (w_{2}, F) that are not in the pair (w_{1}, F). However, all other standard pairs are the same as the original ideal I. Thus, the problem of finding all standard pairs of I reduces to determining if a standard pair of I + ⟨w_{1}⟩ is a standard pair for I. To decide if a pair (x^{β}, G) of I + ⟨w_{1}⟩ is a standard pair of I, we first check that P_{F} is an associated prime of I. If this is true, we determine if (w_{2}, F) is covered by (x^{β}, G).

The Macaulay 2 version of this algorithm takes the following form:

    i36 : stdPairs = I -> (
               S := ring I;
               X := gens S;
               std := {};
               J := I;
               while J != S do (
                    w1 := 1_S;
                    F := X;
                    K := J;
                    while K != 0 do (
                         g1 := (ideal mingens ideal K)_0;
                         x := first supp g1;
                         w1 = w1 * g1 // x;
                         F = delete(x, F);
                         K = K : monomialIdeal(g1 // x);
                         L := select(first entries gens K,
                              r -> not member(x, supp r));
                         if #L > 0 then K = monomialIdeal L
                         else K = monomialIdeal 0_S;);
                    w2 := w1;
                    scan(X, r -> if not member(r, supp w1) or member(r, F)
                         then w2 = substitute(w2, {r => 1}));
                    P := monomialIdeal select(X, r -> not member(r, F));

                    if (I:(I:P) == P) and (all(std, p ->
                              (w2 % (first p) != 0) or not
                              isSubset(supp(w2 // first p) | F, last p)))
                    then std = std | {{w2, F}};
                    J = J + monomialIdeal(w1););
               std);

We can compute the standard pairs of Example 3.1 using this Macaulay 2 function:

    i37 : S = QQ[x,y,z];
    i38 : I = monomialIdeal(x*y^3*z, x*y^2*z^2, y^3*z^2, y^2*z^3);
    o38 : MonomialIdeal of S
    i39 : scan(time stdPairs I, P -> << endl << P << endl);
         -- used 0.66 seconds
    {y, {x, z}}
    {1, {x, z}}
      2 2
    {y z , {}}
    {z, {y}}
      2
    {y z, {x}}
    {1, {x, y}}

Our second algorithm is taken from section 3.2 of Saito, Sturmfels and Takayama [22]. The proposition below provides the main ingredient for this algorithm. If I is a monomial ideal and F ⊆ {x_{1}, …, x_{n}}, we write I_{F} for the monomial ideal in ℚ[x_{i} : x_{i} ∉ F] obtained by replacing each x_{i} ∈ F with 1 in every minimal generator of I.

Proposition 3.2. For (x^{α}, F) to be a standard pair of I, it is necessary and sufficient that (x^{α}, ∅) be a standard pair of I_{F}.

Proof. Lemma 3.1 in Sturmfels, Trung and Vogel [27].

The definition of a standard pair implies that (x^{α}, ∅) is a standard pair of I_{F} if and only if x^{α} is one of the finitely many monomials contained in (I_{F} : P_{F}^{∞}) but not contained in I_{F}, where P_{F} = ⟨x_{i} : x_{i} ∉ F ⟩. Since ideal quotients and saturations are implemented in Macaulay 2, this reduces the problem to finding a set D which contains F for every associated prime P_{F} of I. One approach is to simply compute the associated primes of I from a primary decomposition.

The method standardPairs uses this algorithm to determine the set of standard pairs for a monomial ideal.

    i40 : code(standardPairs, MonomialIdeal, List)

o40 = -- ../../../m2/monideal.m2:318-341
standardPairs(MonomialIdeal, List) := (I,D) -> (
R := ring I;
X := gens R;
S := {};
k := coefficientRing R;
scan(D, L -> (
Y := X;
m := vars R;
Lset := set L;
Y = select(Y, r -> not Lset#?r);
m = substitute(m, apply(L, r -> r => 1));
-- using monoid to create ring to avoid
-- changing global ring.
A := k (monoid [Y]);
phi := map(A, R, substitute(m, A));
J := ideal mingens ideal phi gens I;
Jsat := saturate(J, ideal vars A);
if Jsat != J then (
     B := flatten entries super basis (
          trim (Jsat / J));
     psi := map(R, A, matrix{Y});
     S = join(S, apply(B, b -> {psi(b), L}));
     )));
S)
i41 : time standardPairs I;
-- used 0.83 seconds

As an example, we will compute the standard pairs of the permutahedron ideal. Let S = ℚ[x_{1}, …, x_{n}] and let 𝔖_{n} be the symmetric group of order n. We write ρ for the vector (1, 2, …, n) and σ(ρ) for the vector obtained by applying σ ∈ 𝔖_{n} to the coordinates of ρ. The n-th permutahedron ideal is ⟨x^{σ(ρ)} : σ ∈ 𝔖_{n}⟩. We compute the number of standard pairs for 2 ≤ n ≤ 5.

i42 : permutohedronIdeal = n -> (
S := QQ[X_1..X_n];
monomialIdeal terms det matrix table(n ,gens S,
(i,r) -> r^(i+1)));
i43 : L = apply({2,3,4,5}, j -> standardPairs(permutohedronIdeal(j)));
i44 : apply(L, i -> #i)
o44 = {3, 10, 53, 446}
o44 : List
i45 : erase symbol x; erase symbol z;

Example: Integer Programming Problems

As an application of standard pairs, we show how to solve integer linear programming problems. Let A be a d × n matrix of nonnegative integers, let ω ∈ ℝ^{n} and fix β ∈ ℤ^{d}. We focus on the following optimization problem

IP_{A,ω}(β) : minimize ω · α subject to Aα = β, α ∈ ℕ^{n}.

We view this integer linear program as a family depending on the vector β. The algorithm we present for solving IP_{A,ω}(β) depends on the proposition below.

The toric ideal I_{A} ⊆ S = ℚ[x_{1}, …, x_{n}] associated to A is the binomial ideal generated by x^{γ} − x^{δ} where γ, δ ∈ ℕ^{n} and Aγ = Aδ. We write in_{ω}(I_{A}) for the initial ideal of I_{A} with respect to the following order:

x^{γ} ≺_{ω} x^{δ} ⟺ \begin{cases}ω · γ < ω · δ & or \\ ω · γ = ω · δ & and x^{α} ≺_{rlex} x^{γ} . \end{cases}

For more information on toric ideals and their initial ideals see Sturmfels [26].

Proposition 3.3. (1) A monomial x^{α} is a standard monomial of in_{ω}(I_{A}) if

and only if α is the optimal solution to the integer program IP_{A,ω}(Aα).

(2) If (•, F) is a standard pair of in_{ω}(I_{A}), then the columns of A corresponding to F are linearly independent.

Proof. See Proposition 2.1 in Hoşten and Thomas [14] for the proof of the first statement. The second statement follows from Corollary 2.9 of the same article. ⊓ ⊔

The first statement implies that the standard pairs of in_{ω}(I_{A}) cover all optimal solutions to all integer programs in IP_{A,ω}. If α is the optimal solution to IP_{A,ω}(β) covered by the standard pair (x^{γ}, F), then the second statement guarantees there exists a unique δ ∈ ℕ^{n} such that Aδ = β − Aγ. Therefore, α = δ + γ. We point out that the complexity of this algorithm is dominated by determining the set of standard pairs of in_{ω}(I_{A}) which depends only on A and ω. As a result, this method is particularly well suited to solving IP_{A,ω}(β) as β varies.

To implement this algorithm in Macaulay 2, we need a function which returns the toric ideal I_{A}. Following Algorithm 12.3 in Sturmfels [26], we have

    i47 : toBinomial = (b, S) -> (
               pos := 1_S;
               neg := 1_S;
               scan(#b, i -> if b_i > 0 then pos = pos*S_i^(b_i)
                             else if b_i < 0 then neg = neg*S_i^(-b_i));
               pos - neg);
    i48 : toricIdeal = (A, omega) -> (
               n := rank source A;
               S = QQ[x_1..x_n, Weights => omega, MonomialSize => 16];
               B := transpose matrix syz A;
               J := ideal apply(entries B, b -> toBinomial(b, S));
               scan(gens S, r -> J = saturate(J, r));
               J);

Thus, we can solve IP_{A,ω}(β) using the following function.

i49 : IP = (A, omega, beta) -> (
           std := standardPairs monomialIdeal toricIdeal(A, omega);
           n := rank source A;
           alpha := {};
           Q := first select(1, std, P -> (
                F := apply(last P, r -> index r);
                gamma := transpose matrix exponents first P;
                K := transpose syz (submatrix(A,F) | (A*gamma-beta));
                X := select(entries K, k -> abs last(k) === 1);
                scan(X, k -> if all(k, j -> j>=0) or all(k, j -> j<=0)
                     then alpha = apply(n, j -> if member(j, F)
                          then last(k)*k_(position(F, i -> i === j))
                          else 0));
                #alpha > 0));
           if #Q > 0 then (matrix {alpha})+(matrix exponents first Q)
           else 0);

We illustrate this with some examples.

i50 : A = matrix{{1,1,1,1,1},{1,2,4,5,6}}
o50 = | 1 1 1 1 1 |
      | 1 2 4 5 6 |
               2        5
o50 : Matrix ZZ  <--- ZZ
i51 : w1 = {1,1,1,1,1};
i52 : w2 = {2,3,5,7,11};
i53 : b1 = transpose matrix{{3,9}}
o53 = | 3 |
      | 9 |
               2        1
o53 : Matrix ZZ  <--- ZZ
i54 : b2 = transpose matrix{{5,16}}
o54 = | 5  |
      | 16 |
               2        1
o54 : Matrix ZZ  <--- ZZ
i55 : IP(A, w1, b1)
o55 = | 1 1 0 0 1 |
               1        5
o55 : Matrix ZZ  <--- ZZ
i56 : IP(A, w2, b1)
o56 = | 1 0 2 0 0 |
               1        5
o56 : Matrix ZZ  <--- ZZ
i57 : IP(A, w1, b2)
o57 = | 2 1 0 0 2 |

                   1        5
    o57 : Matrix ZZ  <--- ZZ
    i58 : IP(A, w2, b2)
    o58 = | 2 0 1 2 0 |
                   1        5
    o58 : Matrix ZZ  <--- ZZ

4 Generic Initial Ideals

Gröbner basis calculations and initial ideals depend heavily on the given coordinate system. By making a generic change of coordinates before taking the initial ideal, we may eliminate this dependence. This procedure also endows the resulting monomial ideal with a rich combinatorial structure.

To describe this structure, we introduce the following definitions and notation. Let S = ℚ[x_{0}, …, x_{n}]. If g = [g_{i,j}] ∈ GL_{n+1}(ℚ) and f ∈ S, then g·f denotes the standard action of the general linear group on S: x_{i} ↦ ∑_{j=0}^{n} g_{i,j}x_{j}. For an ideal I ⊆ S, we define g·I = {g·f|f ∈ I}. Let B denote the Borel subgroup of GL_{n+1}(ℚ) consisting of upper triangular matrices. A monomial ideal I is called Borel-fixed if it satisfies any of the following equivalent conditions:

(a) g · I = I for every g ∈ B;

(b) if r is a generator of I divisible by x_{j} then \frac{rx_{i}}{x_{j}} ∈ I for all i < j;

(c) in(g · I) = I for every g is some open neighborhood of the identity in B.

For a proof that these conditions are equivalent, see Propositon 1.25 in Green [9].

In Macaulay 2, the function isBorel tests whether a monomial ideal is Borel-fixed.

    i59 : S = QQ[a,b,c,d];
    i60 : isBorel monomialIdeal(a^2, a*b, b^2)
    o60 = true
    i61 : isBorel monomialIdeal(a^2, b^2)
    o61 = false

The function borel generates the smallest Borel-fixed ideal containing the given monomial ideal.

    i62 : borel monomialIdeal(b*c)
                          2        2
    o62 = monomialIdeal (a , a*b, b , a*c, b*c)
    o62 : MonomialIdeal of S
    i63 : borel monomialIdeal(a,c^3)
                             3   2      2   3
    o63 = monomialIdeal (a, b , b c, b*c , c )
    o63 : MonomialIdeal of S

The next theorem provides the main source of Borel-fixed ideals. Theorem 4.1 (Galligo). Fix a term order on S = ℚ[x_{0}, …, x_{n}] such that x_{0} > … > x_{n}. If I is a homogeneous ideal in S, then there is a Zariski open subset U ⊆ GL_{n+1}(ℚ) such that

(1) there is a monomial ideal J ⊆ S such that J = in(g · I) for all g ∈ U;

(2) the ideal J is Borel-fixed. The ideal J is called the generic initial ideal of I.

Proof. See Theorem 1.27 in Green [9]. ⊓ ⊔

The following method allows one to compute generic initial ideals.

    i64 : gin = method();
    i65 : gin Ideal := I -> (
               S := ring I;
               StoS := map(S, S, random(S^{0}, S^{numgens S:-1}));
               monomialIdeal StoS I);
    i66 : gin MonomialIdeal := I -> gin ideal I;

This routine assumes that the random function generates a matrix in the Zariski open subset U. Since we are working over a field of characteristic zero this occurs with probability one. For example, we can determine the generic initial ideal of two generic homogeneous polynomials of degree p and q in ℚ[a, b, c, d].

    i67 : genericForms = (p,q) -> ideal(random(p,S), random(q,S));
    i68 : gin genericForms(2,2)
                          2        3
    o68 = monomialIdeal (a , a*b, b )
    o68 : MonomialIdeal of S
    i69 : gin genericForms(2,3)
                          2     2   4
    o69 = monomialIdeal (a , a*b , b )
    o69 : MonomialIdeal of S

Although the generic initial ideal is Borel-fixed, some non-generic initial ideals may also be Borel-Fixed.

    i70 : J = ideal(a^2, a*b+b^2, a*c)
                  2         2
    o70 = ideal (a , a*b + b , a*c)
    o70 : Ideal of S
    i71 : ginJ = gin J
                          2        2     2
    o71 = monomialIdeal (a , a*b, b , a*c )
    o71 : MonomialIdeal of S

    i72 : inJ = monomialIdeal J
                          2        3        2
    o72 = monomialIdeal (a , a*b, b , a*c, b c)
    o72 : MonomialIdeal of S
    i73 : isBorel inJ and isBorel ginJ
    o73 = true

Finally, we show that the generic initial ideal does depend on the term order by computing lexicographic generic initial ideal for two generic forms of degree p and q in ℚ[a, b, c, d]

    i74 : S = QQ[a,b,c,d, MonomialOrder => Lex];
    i75 : gin genericForms(2,2)
                          2        4     2
    o75 = monomialIdeal (a , a*b, b , a*c )
    o75 : MonomialIdeal of S
    i76 : gin genericForms(2,3)
                          2     2   6       2     6         2       4
    o76 = monomialIdeal (a , a*b , b , a*b*c , a*c , a*b*c*d , a*b*d )
    o76 : MonomialIdeal of S

A more comprehensive treatment of generic initial ideals can be found in Green [9]. The properties of Borel-fixed ideals in characteristic p > 0 are discussed in Eisenbud [7].

Example: Connectedness of the Hilbert Scheme

Generic initial ideals are a powerful tool for studying the structure of the Hilbert scheme. Intuitively, the Hilbert scheme Hilb^{p(t)}(ℙ^{n}) parameterizes subschemes X ⊆ ℙ^{n} with Hilbert polynomial p(t). For an introduction to Hilbert schemes see Harris and Morrison [11]. The construction of the Hilbert scheme Hilb^{p(t)}(ℙ^{n}) can be found in Grothendieck’s original article [10] or Altman and Kleiman [1]. While much is known about specific Hilbert schemes, the general structure remain largely a mystery. In particular, the component structure — the number of irreducible components, their dimensions, how they intersect and what subschemes they parameterize — is not well understood.

Reeves [21] uses generic initial ideals to establish the most important theorem to date on the component structure. The incidence graph of Hilb^{p(t)}(ℙ^{n}) is defined as follows: to each irreducible component we assign a vertex and we connect two vertices if the corresponding components intersect. Reeves [21] proves that the distance (the number of edges in the shortest path) between any two vertices in the incidence graph of Hilb^{p(t)}(ℙ^{n}) is at most 2 deg p(t)+2. Her proof can be divided into three major steps.

Step I: connect an arbitrary ideal to a Borel-fixed ideal. Passing to an initial ideal corresponds to taking the limit in a flat family, in other words a path on the Hilbert scheme; see Theorem 15.17 in Eisenbud [7]. Thus, Theorem 4.1 shows that generic initial ideals connect arbitrary ideals to Borel-fixed ideals.

Step II: connect Borel-fixed ideals by projection. For a homogeneous ideal I ⊆ S = ℚ[x_{0}, …, x_{n}], let π(I) denote the ideal obtained by setting x_{n} = 1 and x_{n−1} = 1 in I. With this notation, we have

Theorem 4.2. If J is a Borel-fixed ideal, then the set of Borel-fixed ideals I, with Hilbert polynomial p(t) and π(I) = J, consists of ideals defining subschemes of ℙ^{n} which all lie on a single component of Hilb^{p(t)}(ℙ^{n}).

Proof. See Theorem 6 in Reeves [21]. ⊓ ⊔

This gives an easy method for partitioning Borel-fixed ideals into classes, each of which must lie in a single component.

Step III: connect Borel-fixed ideals by distraction. Given a Borel-fixed ideal, we produce a new ideal via a two-step process called distraction. First, one polarizes the Borel-fixed ideal. The polarization of a monomial ideal I ⊂ S is defined as:

⟨∏_{i=0}^{n} ∏_{j=1}^{α_{i}} z_{i,j} : where x_{0}^{α_{0}} ⋯ x_{n}^{α_{n}} is a minimal generator of I⟩ .

One then pulls the result back to an ideal in the original variables by taking a linear section of the polarization. Theorem 4.10 in Hartshorne [12] shows that the distraction is connected to the original Borel-fixed ideal. Now, taking the lexicographic generic initial ideal of the distraction yields a second Borelfixed ideal. Reeves [21] proves that repeating this process, at most deg p(t)+1 times, one arrives at a distinguished component of Hilb^{p(t)}(ℙ^{n}) called the lexicographic component. For more information on the lexicographic component see Reeves and Stillman [20].

We can implement these operations in Macaulay 2 as follows:

    i77 : projection = I -> (
               S := ring I;
               n := numgens S;
               X := gens S;
               monomialIdeal mingens substitute(ideal I,
                    {X#(n-2) => 1, X#(n-1) => 1}));
    i78 : polarization = I -> (
               n := numgens ring I;
               u := apply(numgens I, i -> first exponents I_i);
               I.lcm = max \ transpose u;
               Z := flatten apply(n, i -> apply(I.lcm#i, j -> z_{i,j}));
               R := QQ(monoid[Z]);
               Z = gens R;
               p := apply(n, i -> sum((I.lcm)_{0..i-1}));
               monomialIdeal apply(u, e -> product apply(n, i ->
                         product(toList(0..e#i-1), j -> Z#(p#i+j)))));

Monomial Ideals  21

i79 : distraction = I -> (
           S := ring I;
           n := numgens S;
           X := gens S;
           J := polarization I;
           W := flatten apply(n, i -> flatten apply(I.lcm#i,
                     j -> X#i));
           section := map(S, ring J, apply(W, r -> r -
                     random(500)*X#(n-2) - random(500)*X#(n-1)));
           section ideal J);

For example, we have

i80 : S = QQ[x_0 .. x_4, MonomialOrder => GLex];
i81 : I = monomialIdeal(x_0^2, x_0*x_1^2*x_3, x_1^3*x_4)
                      2     2     3
o81 = monomialIdeal (x , x x x , x x )
                      0   0 1 3   1 4
o81 : MonomialIdeal of S
i82 : projection I
                      2     2   3
o82 = monomialIdeal (x , x x , x )
                      0   0 1   1
o82 : MonomialIdeal of S
i83 : polarization I
o83 = monomialIdeal (z      z      , z      z      z      z      , z · · ·
                      {0, 0} {0, 1}   {0, 0} {1, 0} {1, 1} {3, 0}   {1 · · ·
o83 : MonomialIdeal of QQ [z      , z      , z      , z      , z  · · ·
                            {0, 0}   {0, 1}   {1, 0}   {1, 1}   {1, 2} · · ·
i84 : distraction I
           2                             2                     2 · · ·
o84 = ideal (x  - 398x x  - 584x x  + 36001x  + 92816x x  + 47239x , - · · ·
              0       0 3       0 4         3         3 4         4 · · ·
o84 : Ideal of S

To illustrate Reeves’ method, we show that the incidence graph of the Hilbert scheme Hilb^{4t+1}(ℙ^{4}) has diameter at most 2. Note that the rational quartic curve in ℙ^{4} has Hilbert polynomial 4t + 1.

i85 : m =  matrix table({0,1,2}, {0,1,2}, (i,j) -> (gens S)#(i+j))
o85 = | x_0 x_1 x_2 |
      | x_1 x_2 x_3 |
      | x_2 x_3 x_4 |
              3       3
o85 : Matrix S  <--- S
i86 : rationalQuartic = minors(2, m);
o86 : Ideal of S
i87 : H = hilbertPolynomial(S/rationalQuartic);

i88 : hilbertPolynomial(S/rationalQuartic, Projective => false)
o88 = 4$i + 1
o88 : QQ [$i]

There are 12 Borel-fixed ideals with Hilbert polynomial 4t+1; see Example 1 in Reeves [21].

i89 : L = {monomialIdeal(x_0^2, x_0*x_1, x_0*x_2, x_1^2, x_1*x_2, x_2^· · ·
i90 : scan(#L, i -> << endl << i+1 << " : " << L#i << endl);
                    2         2               2
1 : monomialIdeal (x , x x , x , x x , x x , x )
                    0   0 1   1   0 2   1 2   2
                    2         2               3
2 : monomialIdeal (x , x x , x , x x , x x , x , x x )
                    0   0 1   1   0 2   1 2   2   0 3
                        2     2   3
3 : monomialIdeal (x , x , x x , x , x x x )
                    0   1   1 2   2   1 2 3
                        2         4   3
4 : monomialIdeal (x , x , x x , x , x x )
                    0   1   1 2   2   2 3
                            5   4 3
5 : monomialIdeal (x , x , x , x x )
                    0   1   2   2 3
                        2         5         4 2
6 : monomialIdeal (x , x , x x , x , x x , x x )
                    0   1   1 2   2   1 3   2 3
                    2         2               5               4
7 : monomialIdeal (x , x x , x , x x , x x , x , x x , x x , x x )
                    0   0 1   1   0 2   1 2   2   0 3   1 3   2 3
                        2         5   4       2
8 : monomialIdeal (x , x , x x , x , x x , x x )
                    0   1   1 2   2   2 3   1 3
                    2         2               4           2
9 : monomialIdeal (x , x x , x , x x , x x , x , x x , x x )
                    0   0 1   1   0 2   1 2   2   0 3   1 3
                         2     2   4             2
10 : monomialIdeal (x , x , x x , x , x x x , x x )
                     0   1   1 2   2   1 2 3   1 3
                         2         4     3
11 : monomialIdeal (x , x , x x , x , x x )
                     0   1   1 2   2   1 3
                             6   5     4 2
12 : monomialIdeal (x , x , x , x x , x x )
                     0   1   2   2 3   2 3
i91 : all(L, I -> isBorel I and hilbertPolynomial(S/I) == H)
o91 = true

The projection operation partitions the list L into 3 classes:

    i92 : class1 = projection L#0
                          2         2               2
    o92 = monomialIdeal (x , x x , x , x x , x x , x )
                          0   0 1   1   0 2   1 2   2
    o92 : MonomialIdeal of S
    i93 : class2 = projection L#1
                              2         3
    o93 = monomialIdeal (x , x , x x , x )
                          0   1   1 2   2
    o93 : MonomialIdeal of S
    i94 : class3 = projection L#4
                                  4
    o94 = monomialIdeal (x , x , x )
                          0   1   2
    o94 : MonomialIdeal of S
    i95 : all(1..3, i -> projection L#i == class2)
    o95 = true
    i96 : all(4..11, i -> projection L#i == class3)
    o96 = true

Finally, we use the distraction to connect the classes.

    i97 : all(L, I -> I == monomialIdeal distraction I)
    o97 = true
    i98 : all(0..3, i -> projection gin distraction L#i == class3)
    o98 = true

Therefore, the components corresponding to class1 and class2 intersect the one corresponding to class3. Note that class3 corresponds to the lexicographic component.

5 The Chain Property

Hoşten and Thomas [14] recently established that the initial ideals of a toric ideal have an interesting combinatorial structure called the chain property. This structure is on the poset of associated primes where the partial order is given by inclusion. Since a monomial ideal I ⊂ S = ℚ[x_{1}, …, x_{n}] is prime if and only if it is generated by a subset of the variables {x_{1}, …, x_{n}}, the poset of associated primes of I is contained in the power set of the variables. We say that a monomial ideal I has the chain property if the following condition holds:

For any embedded prime P_{F} = ⟨x_{i} : x_{i} ∉ F ⟩ of I, there exists an

associated prime P_{G} ⊂ P_{F} such that |G| = |F | − 1.

In other words, there is a saturated chain from every embedded prime to some minimal prime. Experimental evidence suggests that, in fact, most initial ideals of prime ideals satisfy this saturated chain condition. Because of ubiquity and simplicity of this condition, we are interested in understanding which classes of initial ideals (or more generally monomial ideals) have the chain property.

More recently, Miller, Sturmfels and Yanagawa [18] provided a large class of monomial ideals with the chain property. A monomial ideal I is called generic when the following condition holds: if two distinct minimal generators r_{1} and r_{2} of I have the same positive degree in some variable x_{i}, there is a third generator r_{3} which strictly divides the least common multiple of r_{1} and r_{2}. In particular, if no two distinct minimal generators have the same positive degree in any variable, then the monomial ideal is generic. Theorem 2.2 in Miller, Sturmfels and Yanagawa [18] shows that generic monomial ideals have the chain property.

Examples and Counterexamples

In this final section, we illustrate how to use Macaulay 2 for further experimentation and investigation of the chain property. The following function determines whether a monomial ideal has the chain property:

    i99 : hasChainProperty = I -> (
               L := ass I;
               radI := radical I;
               all(L, P -> radI : (radI : P) == P or (
                         gensP := first entries gens P;
                         all(gensP, r -> (
                                   Q := monomialIdeal delete(r, gensP);
                                   I : (I : Q) == Q)))));

Using hasChainProperty, we examine the initial ideals of four interesting classes of ideals related to toric ideals.

An Initial Ideal of a Toric Ideal. As mentioned above, Hoşten and Thomas proved that any initial ideal of a toric ideal satisfies the saturated chain condition. The following example demonstrates this phenomenon. Consider the matrix A:

    i100 : A = matrix{{1,1,1,1,1,1,1}, {2,0,0,0,1,0,0}, {0,2,0,0,0,1,0}, { · · ·
    o100 = | 1 1 1 1 1 1 1 |
           | 2 0 0 0 1 0 0 |
           | 0 2 0 0 0 1 0 |
           | 2 2 0 2 1 1 1 |
                    4        7
    o100 : Matrix ZZ  <--- ZZ
    i101 : IA = toricIdeal(A, {1,1,1,1,1,1,1})

                          2          2          2
    o101 = ideal (x x  - x , x x  - x , x x  - x )
                   3 4    7   2 3    6   1 3    5
    o101 : Ideal of S
    i102 : inIA = monomialIdeal IA
                                               2     2     2
    o102 = monomialIdeal (x x , x x , x x , x x , x x , x x )
                           1 3   2 3   3 4   2 5   4 5   4 6
    o102 : MonomialIdeal of S
    i103 : hasChainProperty inIA
    o103 = true

An Initial Ideal of a Prime Ideal. Since toric ideals are prime, one naturally asks if the initial ideal of any prime ideal has the chain property. By modifying the previous example, we can show that this is not the case. In particular, making the linear change of coordinates by x_{4} ↦ x_{3} − x_{4}, we obtain a new prime ideal J.

    i104 : StoS = map(S, S, {x_1, x_2, x_3, x_3 - x_4, x_5, x_6, x_7});
    o104 : RingMap S <--- S
    i105 : J = StoS IA
                   2           2          2          2
    o105 = ideal (x  - x x  - x , x x  - x , x x  - x )
                   3    3 4    7   2 3    6   1 3    5
    o105 : Ideal of S

Taking the initial ideal with respect to the reverse lexicographic term order (the default order), we have

    i106 : inJ = monomialIdeal J

                                       2     2     2       2     2       2 · · ·

    o106 = monomialIdeal (x x , x x , x , x x , x x , x x x , x x , x x x · · ·
                           1 3   2 3   3   2 5   3 5   1 4 5   3 6   1 4 6 · · ·
    o106 : MonomialIdeal of S
    i107 : hasChainProperty inJ
    o107 = false

An A-graded Monomial Ideal. Let A be a d × n matrix of nonnegative integers and let a_{i} denote the i-th column of A. Consider the polynomial ring S = ℚ[x_{1}, …, x_{n}] with the ℤ^{d}-grading defined by deg x_{i} = a_{i}. An ideal I ⊂ ℚ[x_{1}, …, x_{n}] is called A-graded provided it is homogeneous with respect to the A-grading and

dim_{ℚ} (\frac{S}{I} )_{b} = \begin{cases}1 & if b ∈ ℕA \\ 0 & otherwise \end{cases}

for all b ∈ ℕ^{d}. Remark 10.1 in Sturmfels [26] shows that the initial ideal of the toric ideal I_{A} is A-graded. Altmann [2] shows that when A has rank 2 every A-graded monomial ideal has the chain property. However, Altmann [2] also provides a counterexample when A has rank 3. We can verify his example in Macaulay 2 as follows:

i108 : A = matrix{{2,0,0,1,0,0,2,1,1,3,2,2,2,3,3,3},
                  {0,2,0,0,1,0,1,2,1,2,3,2,3,2,3,3},
                  {0,0,2,0,0,1,1,1,2,2,2,3,3,3,2,3}};
                3        16
o108 : Matrix ZZ  <--- ZZ

In Macaulay 2, the first entry in degree vector of each variable must be positive. Hence, we append to A the sum of its rows to get a matrix whose columns will serve as the degrees of the variables.

i109 : D = A^{0}+A^{1}+A^{2} || A
o109 = | 2 2 2 1 1 1 4 4 4 7 7 7 8 8 8 9 |
       | 2 0 0 1 0 0 2 1 1 3 2 2 2 3 3 3 |
       | 0 2 0 0 1 0 1 2 1 2 3 2 3 2 3 3 |
       | 0 0 2 0 0 1 1 1 2 2 2 3 3 3 2 3 |
                4        16
o109 : Matrix ZZ  <--- ZZ
i110 : D = entries transpose D;
i111 : S = QQ[vars(0..15), Degrees => D, MonomialSize => 16];
i112 : I = monomialIdeal(d*j, d*k, d*l, d*m, d*n, d*o, d*p, e*j, e*k,
           e*l, e*m, e*n, e*o, e*p, f*j, f*k, f*l, f*m, f*n, f*o, f*p,
           g*j, g*k, g*l, g*m, g*n, g*o, g*p, h*j, h*k, h*l, h*m, h*n,
           h*o, h*p, i*j, i*k, i*l, i*m, i*n, i*o, i*p, g^2, g*h, g*i,
           h^2, h*i, i^2, j^2, j*k, j*l, j*m, j*n, j*o, j*p, k^2, k*l,
           k*m, k*n, k*o, k*p, l^2, l*m, l*n, l*o, l*p, m^2, m*n, m*o,
           m*p, n^2, n*o, n*p, o^2, o*p, p^2, d^2, e^2, f^2, d*h, e*i,
           f*g, f*d*i, d*e*g, e*f*h, c*d*g, a*e*h, b*f*i, c*e*g,
           a*f*h, b*d*i, c*d*e, a*e*f, b*f*d, c*b*d, a*c*e, b*a*f,
           c*b*g, a*c*h, b*a*i);
o112 : MonomialIdeal of S

To help convince you that I is an A-graded ideal, we compute the dim_{ℚ} (\frac{S}{I} )_{a_{i}} for 1 ≤ i ≤ 16.

i113 : apply(D, d -> rank source basis(d, (S^1)/ ideal I))
o113 = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
o113 : List

Finally, we check the chain property.

i114 : hasChainProperty I
o114 = false

The Vertex Ideal. Lastly, we consider a different family of monomials ideals arising from toric ideals. The vertex ideal V_{A} is defined as intersection all the monomial initial ideals of the toric ideal I_{A}. Although there are (in general) infinitely many distinct term orders on a polynomial ring, an ideal has only finitely many initial ideals; see Theorem 1.2 in Sturmfels [26]. In particular, the above intersection is finite. Vertex ideals were introduced and studied by Hoşten and Maclagan [13]. However, the question “Does the vertex ideal V_{A} have the chain property?” remains open.

References

1. Allen B. Altman and Steven L. Kleiman: Compactifying the Picard scheme. Adv. in Math., 35(1):50–112, 1980.

2. Klaus Altmann: The chain property for the associated primes of A-graded ideals. arXiv:math.AG/0004142.

3. Dave Bayer and Mike Stillman: Computation of Hilbert functions. J. Symbolic Comput., 14(1):31–50, 1992.

4. Anders Björner: Nonpure shellability, f-vectors, subspace arrangements and complexity. In Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994), pages 25–53. Amer. Math. Soc., Providence, RI, 1996.

5. Anders Björner and Gil Kalai: An extended Euler-Poincaré theorem. Acta Math., 161(3-4):279–303, 1988.

6. Winfried Bruns and Jürgen Herzog: Cohen-Macaulay rings. Cambridge University Press, Cambridge, 1993.

7. David Eisenbud: Commutative algebra with a view toward algebraic geometry. Springer-Verlag, New York, 1995.

8. Michael R. Garey and David S. Johnson: Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences.

9. Mark L. Green: Generic initial ideals. In Six lectures on commutative algebra (Bellaterra, 1996), pages 119–186. Birkhäuser, Basel, 1998.

10. Alexander Grothendieck: Fondements de la géométrie algébrique. [Extraits du Séminaire Bourbaki, 1957–1962.]. Secrétariat mathématique, Paris, 1962.

11. Joe Harris and Ian Morrison: Moduli of curves. Springer-Verlag, New York, 1998.

12. Robin Hartshorne: Connectedness of the Hilbert scheme. Inst. Hautes Études Sci. Publ. Math., 29:5–48, 1966.

13. Serkan Hoşten and Diane Maclagan: The vertex ideal of a lattice. 20 pages, (2000), preprint.

14. Serkan Hoşten and Rekha R. Thomas: The associated primes of initial ideals of lattice ideals. Math. Res. Lett., 6(1):83–97, 1999.

15. Serkan Hoşten and Rekha R. Thomas: Standard pairs and group relaxations in integer programming. J. Pure Appl. Algebra, 139(1-3):133–157, 1999. Effective methods in algebraic geometry (Saint-Malo, 1998).

16. Ezra Miller: Alexander Duality for Monomial Ideals and Their Resolutions. arXiv:math.AG/9812095.

17. Ezra Miller: The Alexander duality functors and local duality with monomial support. J. Algebra, 231(1):180–234, 2000.

18. Ezra Miller, Bernd Sturmfels, and Kohji Yanagawa: Generic and cogeneric monomial ideals. J. Symbolic Comput., 29(4-5):691–708, 2000. Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998).

19. Hidefumi Ohsugi and Takayuki Hibi: Normal polytopes arising from finite graphs. J. Algebra, 207(2):409–426, 1998.

20. Alyson Reeves and Mike Stillman: Smoothness of the lexicographic point. J. Algebraic Geom., 6(2):235–246, 1997.

21. Alyson A. Reeves: The radius of the Hilbert scheme. J. Algebraic Geom., 4(4):639–657, 1995.

22. Mutsumi Saito, Bernd Sturmfels, and Nobuki Takayama: Gröbner deformations of hypergeometric differential equations. Springer-Verlag, Berlin, 2000.

23. Aron Simis, Wolmer V. Vasconcelos, and Rafael H. Villarreal: The integral closure of subrings associated to graphs. J. Algebra, 199(1):281–289, 1998.

24. Richard P. Stanley: Combinatorics and commutative algebra. Birkhäuser Boston Inc., Boston, MA, second edition, 1996.

25. Bernd Sturmfels: Gröbner bases and Stanley decompositions of determinantal rings. Math. Z., 205(1):137–144, 1990.

26. Bernd Sturmfels: Gröbner bases and convex polytopes. American Mathematical Society, Providence, RI, 1996.

27. Bernd Sturmfels, Ngô Viêt Trung, and Wolfgang Vogel: Bounds on degrees of projective schemes. Math. Ann., 302(3):417–432, 1995.

28. Rafael H. Villarreal: Cohen-Macaulay graphs. Manuscripta Math., 66(3):277– 293, 1990.

29. Günter M. Ziegler: Lectures on polytopes. Springer-Verlag, New York, 1995.

Index

Alexander dual 7

borel 17

Borel-fixed 17

chain property 23 cover 9

distraction 20

dual 7

dual, Alexander 7

f-vector 3

generic initial ideal 18,

20 generic monomial ideal

24 Gröbner basis 2

Hilbert scheme 19

– incidence graph 19 Hilbert series 3 ideal

– A-graded 25

– Borel-fixed 17

– codimension 9

– generic initial 18, 20 – graph 9

– initial 2

– monomial 1, 2

– of minors 10

– permutahedron 14 – primary 5

– Stanley-Reisner 3 – toric 15

– tree 8 initial ideal 2, 15 integer programming

14

isBorel 17
isMonomialIdeal 3

monomial

– support 3 monomial ideal 1, 2

                        MonomialIdeal 2
                        monomialIdeal 2

NP-complete 9

polarization 20

primary decomposition 5, 9, 12

rational quartic curve 21

simplicial complex 3 – f-vector 3 standard pair 11–14

                        standardPairs 13

Stanley-Reisner ideal 3

toric ideal 15

vertex cover 9 vertex ideal 26