Informal Seminar on Stanley-Reisner Theory, UMN, Fall 2002 14 November 2002

Introduction to Gröbner bases, II Speaker: Jeremy Martin

1. Review

Last time we were looking at a polynomial ring R = k[X_{1}, …, X_{n}] and a proper ideal I ⊂ R. We chose a term order < for R, which is a total order on monomials satisfying the properties

• μ | μ′ ⟹ μ ≤ μ′ and
• μ ≤ μ′ ⟹ νμ ≤ νμ′.

With respect to this term order, we can define the initial term in_{<}(f) of any nonzero polynomial f, and the initial ideal of I as

in_{<}(I) = (in_{<}(f) : f ∈ I) .

I said last time that a finite set of generators (f_{1}, …, f_{r}) is a Gröbner basis for I (with respect to a given term order <) if

(1)  (in(f_{1})_{<}, …, in_{<}(f_{r})) = in_{<}(I).

I’ll often suppress the subscript < if we’re only talking about one term order. Theorem 1. Let < be a term order on R. Then I has a Gröbner basis with respect to <.

Proof. Let B_{0} = {f_{1}, …, f_{r}} be a set of generators for I, and I_{0} = (in(f_{1}), …, in(f_{r})). If I_{0} = in(I), great. If not, then there exists some g_{1} ∈ I such that in(g_{1}) ∉ I_{0}. Let B_{1} = B_{0} ∪ {g_{1}} and I_{1} = I_{0} + (in(g_{1})). Note that I_{0} ⊊ I_{1}. If I_{1} = in(I), great. If not, then there exists some g_{2} ∈ I such that in(g_{2}) ∉ I_{1}. So let B_{2} = B_{1} ∪ {g_{2}} and I_{2} = I_{1} + (g_{2}). And so on. But R is Noetherian, so this has to stop eventually. That means that there is some k for which I_{k} = in(I).

□

By the way, this use of the Noetherian property is typical in proving a lot of the results that make the Gröbner basis machine run smoothly. Another fact along these lines, which I will need later, is that term orders are Artinian. That is, every set of monomials has a smallest element. This is completely clear for term orders which refine the partial order by total degree—indeed, those term orders are well-orderings. But in general, it’s not too hard to derive the Artinian property from the definition of a term order (see [2, Lemma 15.2]).

Two brief asides:

1. The Gröbner basis is by no means unique; indeed, by the proof, any finite subset of I which contains a Gröbner basis is itself a Gröbner basis. It is not hard to see, however, that all minimal Gröbner bases have the same cardinality (with respect to a fixed term order), namely the minimal number of generators for the initial ideal. In addition, there’s a particularly nice kind of minimal Gröbner basis called a reduced Gröbner basis, which is unique (see Exercise 15.14 in [2]).

2. You may wonder what happens if we vary the term order. Using the Noetherian property, it can be shown [3, Thm 1.2] that I has only finitely many initial ideals. That is, the term orders on R fall into finitely many equivalence classes, such that in_{<}(I) = in_{<′}(I) if < and <′ are in the same equivalence class.

It follows that I has a universal Gröbner basis, i.e., a finite subset which is a Gröbner basis for all term orders, obtained by taking the union

This is all very well, but how do you produce a Gröbner basis to begin with? How do you decide whether or not one of the B_{i}’s is a Gröbner basis? And if it isn’t, how do you get your hands on an element whose initial term needs to be thrown in? Before I answer these (excellent) questions, let’s look at one of the easiest problems to solve once you have a Gröbner basis. (This may seem unnecessarily tantalizing, but actually the algorithm for producing a Gröbner basis in the first place depends on this construction.) The problem in question is ideal membership, and I claim that the following algorithm solves it:

Input: {f_{1}, …, f_{r}} : Gröbner basis for an ideal I ⊂ R
g  : polynomial in R
Output: An answer to the question “Is g ∈ I?”
Step 1: If in(g) ∉ in(I) = (in(f_{1}), …, in(f_{r})) (which is easy to check), then answer NO and terminate.
Step 2: Otherwise, find f_{i} such that in(g) is divisible by f_{i}.
Step 3: Set h := \frac{in(g)}{in(f_{1})} f_{1} and g := g′ − h.
Step 4: If g′ = 0, then answer YES and terminate. Otherwise, set g := g′ and go to Step 1.

Why does this work? First of all, g′ ≡ g (mod I), so if the algorithm returns YES, then we have actually produced an explicit R-linear combination of the f_{i}’s which equals g. On the other hand, if in(g′) ∉ in(I), then by definition g′ ∉ I, so g ∉ I as well. Okay, but why is the algorithm guaranteed to terminate? The key point is that after each iteration of Step 3, we have

in(g_{1}) < in(g)

since g and h have the same leading term, so the leading term of g′ is some other monomial appearing in one of g or h, which means that it is less than in(g). Since term orders are Artinian, the algorithm must terminate eventually.

This procedure is referred to as reduction, and is quite similar to (in fact, it generalizes) the division algorithm. If feeding g into the algorithm produces g′ at some stage, we will say that “g can be reduced to g′ modulo the f_{i},” and write

g ⟶_{{f_{i}}} g′.

(or just g → g′).

This gives an idea of how we might construct an algorithm to enlarge a generating set {f_{1}, …, f_{r}} for I into a Gröbner basis. Start by pretending that it really is. Think up a polynomial g ∈ I and reduce it modulo {f_{i}}. If g → g′ and in(g′) ∉ (in(f_{1}), …, in(f_{r})), why then we just throw g into the putative Gröbner basis, enlarging the initial ideal.

There are a couple of problems. First, how do you go about thinking up appropriate g’s to feed into the machine? After all, if g → 0, it just says that in(g) ∈ (in(f_{1}), …, in(f_{r})); that doesn’t mean that a different g wouldn’t reduce to something outside in(I). Second of all, how do you know when to stop? The solution is provided by Buchberger’s algorithm.

For f, g ∈ R, define their S-polynomial (S stands for “syzygy”) to be

S(f, g) = \frac{in(f_{2})}{lcm(in(f_{1}), in(f_{2}))} f_{1} − \frac{in(f_{1})}{lcm(in(f_{1}), in(f_{2}))} f_{2}.

As before, we have rigged S(f, g) to ensure that the leading terms cancel. So this might be a way of producing new elements of I whose initial term is not divisible by either in(f_{1}) or in(f_{2}). Of course, we have to take S(f, g) and reduce it modulo our partial Gröbner basis to find out whether we’ve really gotten something new. Buchberger’s criterion says, in effect, that we don’t have to do anything fancier than compute and reduce a bunch of S-polynomials. That is: Theorem 2 (Buchberger). Let I = (f_{1}, …, f_{r}) ⊂ R. If, for every 1 ≤ i < j ≤ r,

S(f_{i}, f_{j}) ⟶_{{f_{i}}} 0,

then the f_{i}’s form a Gröbner basis for I.

I don’t intend to prove this (if you’re interested, it is Theorem 15.8 in [2]), but I do want to work through an example. First, though, I want to tell you one way in which it’s related to Stanley-Reisner theory, which is after all supposed to be the topic of this seminar. Theorem 3. Let I ⊂ R. For any term order < on R, the set of monomials not in in_{<}(I) form a basis for R/I as a k-vector space.

Such monomials are called standard monomials for I (with respect to <).

Proof. It is clear that different linear combinations of standard monomials represent different elements of R/I. On the other hand, any member of R is congruent to some such linear combination, by the reduction algorithm. It □

Corollary 1. If I ⊂ R is a homogeneous ideal, so that R/I is a graded ring, then

Hilb(R/I; t) = Hilb(R/ in_{<}(I); t)

for all term orders <.

This is in itself a nice fact, because a homogeneous ideal I ⊂ k[X_{1} …, X_{n}] corresponds to a subvariety of projective (n−1)-space (at least if I is radical, but let’s not go there), and the Hilbert series encodes a bunch of nice geometric invariants, such as the dimension, degree, and arithmetic genus. As we saw last time, the Hilbert series of a monomial ideal can be computed explicitly.

If you’re really lucky, the ideal I that you want to study might have a squarefree initial ideal. In this case, you can in principle calculate the Hilbert series combinatorially by looking at the Stanley-Reisner complex. For an example of this, see the speaker’s Ph.D. thesis!

Example 1. Let R = k[x, y, z], and take < to be reverse-lex order with x > y > z. Let I be the homogeneous ideal generated by

f_{1} = \underline{xy} − z^{2},
f_{2} = \underline{y^{2}} − xz.

(When working with explicit polynomials, it is convenient to underline the leading term.) The S-pair of the two generators is

f_{3} := S(f_{1}, f_{2}) = yf_{1} − xf_{2} = xy^{2} − yz^{2} − xy^{2} + x^{2}z = −yz^{2} + \underline{x^{2}z}.

Since

in(f_{3}) = x^{2}z ∉ (in(f_{1}), in(f_{2})) = (xy, y^{2}),

it follows by Buchberger that {f_{1}, f_{2}} is not a Gröbner basis. However, as we will show, {f_{1}, f_{2}, f_{3}} is a Gröbner basis. By Buchberger’s theorem, it is enough to check that S(f_{1}, f_{3}) and S(f_{2}, f_{3}) reduce to zero modulo {f_{1}, f_{2}, f_{3}}. Indeed,

S(f_{1}, f_{3}) = xzf_{1} − yf_{3} = −xz^{3} + \underline{y^{2}z^{2}}
→ (−xz^{3} + y^{2}z^{2}) − y^{2}f_{2} = 0

and

S(f_{2}, f_{3}) = x^{2}zf_{2} − y^{2}f_{3} = \underline{−x^{3}z^{2}} + y^{3}z^{2}
→ (−x^{3}z^{2} + y^{3}z^{2}) + xzf_{3} = \underline{y^{3}z^{2}} − xyz^{3}
→ (y^{3}z^{2} − xyz^{3}) − yz^{2}f_{2} = 0.

So {f_{1}, f_{2}, f_{3}} really is a Gröbner basis, and

in_{<}(I) = (xy, y^{2}, x^{2}z) .

Let’s compute its Hilbert series. Let I′ = (xy, y^{2}), so that in_{<}(I) = I′ + (x^{2}z). As described last time, there is an exact sequence of maps

R[−3] ⟶^{x^{2}z} R/I′ → R/ in_{<}(I) → 0

of graded R-modules (recall that R[−d] means the free R-module generated by a single element of degree d). The kernel of the first map is

I′ : x^{2}z =^{def} {μ ∈ R : x^{2}zμ ∈ I′}
= (y),

so we have the short exact sequence

0 → S[−3] → R/I′ → R/ in_{<}(I) → 0,

where S = R/(y) = k[x, z], which says that

Hilb(R/I; t) = Hilb(R/I′; t) − Hilb(S[−3]; t).

The Hilbert series of S is just (1 − t)^{−2}; however, the shift in grading means that we have to multiply by t^{3}. Meanwhile,

R/I′ = \underbrace{k[x, y]/(xy, y^{2})}_{T}[z],

and T is a k-vector space with basis {1, y, x, x^{2}, x^{3}, … }, so

Hilb(T; t) = t + \frac{1}{1 − t} = \frac{1 + t − t^{2}}{1 − t} ‘  and  Hilb(R/I′; t) = \frac{1 + t − t^{2}}{(1 − t)^{2}} .

Putting all this together, we get

Hilb(R/I; t) = \frac{1 + t − t^{2}}{(1 − t)^{2}} − \frac{t^{3}}{(1 − t)^{2}}
= \frac{1 + t − t^{2} − t^{3}}{(1 − t)^{2}}
(2)  = \frac{1 + 2t + t^{2}}{1 − t} .

We can read off quite a bit of information from this. First of all, dim R/I = 1, the order of the pole of Hilb(R/I; t). In particular, codim I = 2, the number of generators of I, so I is a complete intersection (in particular, it is Gorenstein and Cohen-Macaulay, if you know what those properties are). Its degree is 4, which you can obtain by plugging in t = 1 in the numerator of (2). (We would expect this; in general, the degree of a complete intersection is the product of the degrees of the generators, and here they are both quadratic.)

Example 2. Let R = k[a, b, c, d, e, f], and let I = (bd−ae, cd−af, ce−bf). That is, I is the ideal generated by the 2 × 2 minors of the matrix

[ \begin{matrix}a & b & c \\ d & e & f \end{matrix} ] .

Believe it or not, these generators are a universal Gröbner basis [3, Ex. 1.4]. If < is reverse-lex order, then

in_{<}(I) = (ce, cd, bd).

This is squarefree, so we can associate with it a Stanley-Reisner simplicial complex Δ. Since no generator of in_{<}(I) is divisible by a or f, these vertices are cone points of Δ. That is, if Σ is the simplex whose unique facet is {a, f}, then

Δ = Δ′ ∗ Σ =^{def} {F ∪ G : F ∈ Δ′, G ∈ Σ}

for some simplicial complex Δ′ on {b, c, d, e}. The operator ∗ is called “simplicial join,” and behaves fairly nicely: in particular, joining Δ′ with a simplex does not change its h-vector. (By the way, the smallest subcomplex Δ′ ⊂ Δ such that Δ is the join of Δ′ with a simplex is called the core of Δ.)

Meanwhile, Δ′ = ⟨bc, be, de⟩. Therefore,

Δ = •b•c  • d •e  ∗ • a • f

It’s pretty easy to see that Δ′ is shellable, with h-vector (1, 2). Thus the same holds for Δ. Moreover,

dim R/I = dim R/ in_{<}(I) = 1 + dim Δ = 4,

so

Hilb(R/I; t) = \frac{1 + 2t}{(1 − t^{4})}.

By the way, I is not a complete intersection because its codimension (namely 6 − 4 = 2) is smaller than the number of generators, namely 3. In addition, it is not Gorenstein, because the h-vector is not palindromic. However, the fact that Δ is shellable implies that the Stanley-Reisner ring k[Δ] = R/ in_{<}(I) is Cohen-Macaulay, which in turn implies that R/I is Cohen-Macaulay. (That shellability implies CM-ness is far from obvious, but may be proved later in this seminar. For details, see [1].)

References

[1] W. Bruns and J. Herzog. Cohen-Macaulay rings. Cambridge Univ. Press, Cambridge, revised edition, 1993.

[2] D. Eisenbud. Commutative Algebra with a view to Algebraic Geometry. Springer-Verlag, New York, 1995.

[3] B. Sturmfels. Gröbner Bases and Convex Polytopes. American Math. Soc., 1996.