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

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

1. Motivation

1.1. Computational Commutative Algebra. Let R = k[X_{1}, …, X_{n}] (or more generally any commutative Noetherian ring) and

I = (a_{1}, …, a_{r}),
J = (b_{1}, …, b_{s})

nonzero proper ideals of R (i.e., I, J ≠ R). There are all sorts of questions that we might want to ask about I and J:

1. Determine whether or not a given ring element f lies in I. I.e., determine whether or not there exist ring elements c_{i} such that

f = ∑_{i=1}^{r} a_{i}c_{i}.

This sounds trivial, but how do you compute the c_{i}’s? There might be lots of possible c_{i}’s that might work, but it’s not at all obvious how to design an algorithm for finding even one such list.

It seems that any such algorithm ought to be based on the fact that R is a k-vector space and I is a subspace. After all, in principle, if W ⊂ V are vector spaces and v ∈ V, then you ought to be able to do something like the following: fix an inner product on V, find a basis for W, compute the projection v′ of v onto W, and check whether v = v′. One problem with this that R and I are infinite-dimensional vector spaces. Another problem is that it’s not clear how to write down a k-basis (i.e., a basis as a k-vector space) for I in terms of its generators.

2. We’d like to be able to compute ideals such as

I ∩ J,
I + J = {x + y : x ∈ I, y ∈ J},
IJ = {∑ x_{i}y_{j} : x_{i} ∈ I, y_{j} ∈ J},
\sqrt{I} = \{x ∈ R : x^{n} ∈ I for some n
I : J = {x ∈ R : xJ ⊂ I},
Sat(I, J) = {x ∈ R : x^{n}J ⊂ I for some n},

etc. By “compute,” I mean “give a system of generators for.” This is easy to do for I + J = (a_{i} + b_{j}) and IJ = (a_{i}b_{j}), but highly nontrivial for all the others.

3. Compute numerical invariants of I and J (or, alternatively, of the quotient rings R/I and R/J) such as

• Krull dimension, depth, degree, minimal number of generators, etc.

• the Hilbert series Hilb(R/I; t) (in the case that I is homogeneous)

4. Compute homological things such as minimal free resolutions, Koszul complexes, Ext, Tor, and whatnot. Also, determine whether R/I has various “niceness” properties such as being Cohen-Macaulay, Gorenstein, normal, regular, etc.

5. While we’re at it, it would be nice to find techniques that can be used to study R-modules other than ideals and quotient rings.

1.2. Monomial Ideals. In the special case that I and J are monomial ideals—that is, generated by monomials—many of these problems are much easier, because we can give explicit k-bases for I and R/I. R has a “God-given” k-basis, namely the set M of monomials in x_{1}, …, x_{n}, and to say that I is a monomial ideal is to say that I is an ideal which has a k-vector space basis M′ ⊂ M. So we can solve the ideal membership problem immediately: given f ∈ R, write f = ∑ μ_{i}, where the μ_{i} are monomials. If every μ_{i} is divisible by a generator of I, then f ∈ I; otherwise it isn’t.

Intersections are also easy for monomial ideals: Proposition 1. Let I = (μ_{1}, …, μ_{r}) and J = (ν_{1}, …, ν_{s}), where the μ_{i} and ν_{j} are monomials. Then

I ∩ J = (lcm(μ_{i}, ν_{j}) : 1 ≤ i ≤ r, 1 ≤ j ≤ s) .

The proof is left to the reader; it’s not hard.

Another example of something that is easy to compute for monomial ideals is the Hilbert series of a quotient ring R/I: it’s just the generating function for the k-basis M′ by total degree. In the case that I is principal, generated by a monomial of degree d, it is not hard to see that

Hilb(R/I; t) = \frac{1 − t^{d}}{(1 − t)^{n}} = \frac{1 + t + ⋯ + t^{d−1}}{(1 − t)^{n−1}} .

More generally, if I has a minimal generator of degree d, then you can write down an exact sequence of graded modules

0 → (S/I′′)[−d] → S/I′ → S/I → 0,

where I′ and I′′ are monomial ideals minimially generated by fewer elements than I itself. This implies that

Hilb(R/I; t) = Hilb(R/I′; t) − Hilb(R/I′′; t)

and allows us to calculate Hilb(R/I; t) by induction. (See p. 321 of Eisenbud for more details.)

Part 1. Gröbner bases

To avoid repeating the hypotheses over and over again, R will be a polynomial ring k[x_{1}, …, x_{n}] over a field k, and I ⊂ R will be an ideal.

Gröbner bases (also known as standard bases, or Gordan bases around UCSD) provide a method of reducing questions about arbitrary ideals of R to questions about monomial ideals. The basic idea is that for an arbitrary ideal I, we can define “an” associated monomial ideal in(I), called the initial ideal of I, then translate questions about ideals and rings into questions about linear algebra, which are much easier to compute. (The word “an” is in quotes because, as we’ll see, you have quite a lot of choice in defining in(I).)

Another way to think of a Gröbner basis is that it lets you “straighten” quotient rings R/I. For instance, suppose I is homogeneous, but not a monomial ideal. Then R/I is a perfectly good graded ring, hence it has a Hilbert series. But the Hilbert series is difficult to compute directly the way we did with quotients by monomial ideals, because we have to find a convenient basis to express elements of the quotient ring. If you know a Gröbner basis of I, however, then you know an explicit monomial basis for R/I, so you can find the Hilbert series.

The “naive” way to change an arbitrary nonzero polynomial into a monomial is to replace it with one of the monomials appearing in it:

x^{2}y + x^{4}z^{3} + \underline{wy^{3}} + wxyz ⇝ wy^{3}.

This is actually not so far from the way we’re going to transform an arbitrary ideal of I into an monomial ideal: choose a set of generators f_{i} for I, then for each f_{i}, choose a monomial μ_{i} appearing in f_{i}. Then replace I with the ideal (μ_{i}). Of course, we can’t just do this at random. We need to have some sort of sensible way of choosing the monomials μ_{i}, namely: let < be a total ordering on M, and replace each f_{i} with the monomial appearing in it which is greatest with respect to <. Also, < must satisfy some “natural” conditions, i.e., it must be a term order in the following sense: Definition 1. A term order on R is a total ordering < on the monomials of R which satisfies the following properties:

• refines the partial ordering given by divisibility; that is, if μ | μ′, then μ ≤ μ′; and • is compatible with multiplication, in the sense that for all monomials ν,

μ ≤ μ′ ⟹ νμ ≤ νμ′.

The three most commonly used orders are as follows. Let μ = x_{1}^{a_{1}}x_{2}^{a_{2}} … x_{n}^{a_{n}} and ν = x_{1}^{b_{1}}x_{2}^{b_{2}} … x_{n}^{b_{n}}, and suppose that the variables x_{i} are ordered by

(1)  x_{1} > x_{2} > ⋯ > x_{n}.

Lexicographic order. μ >_{lex} ν if there exists some i ∈ {1, 2, …, n} such that a_{i} > b_{i}, and a_{j} = b_{j} for all j < i.

Graded lexicographic order. This is similar to lex order, but the first criterion is total degree. That is, μ >_{glex} ν if deg(μ) > deg(ν), or if deg(μ) = deg(ν) and μ >_{lex} ν.

Reverse lexicographic order. No, it’s not the opposite of <_{lex}. The idea is that instead of looking for higher powers of more important variables, we are looking for lower powers of less important variables. That is, μ >_{rlex} ν if deg(μ) > deg(ν), or if there exists some i ∈ {1, 2, …, n} such that a_{i} < b_{i}, and a_{j} = b_{j} for all j > i. Perhaps surprisingly, this is the “best” term order to use for many applications.

For instance, the ten quadratic monomials in k[a, b, c, d], listed largest to smallest in lex order, are

a^{2}, ab, ac, ad, b^{2}, bc, bd, c^{2}, cd, d^{2},

while in reverse lex order they are

a^{2}, ab, b^{2}, ac, bc, c^{2}, ad, bd, cd, d^{2}.

In what follows, < is always a term order on R. Definition 2. Let f ∈ R, so that we may write f = ∑_{i∈I} c_{i}μ_{i}, where I is a finite index set, the μ_{i} are monomials, and c_{i} ∈ k. The initial term of f with respect to <, written in_{<}(f) or in(f), is that term c_{i}μ_{i} such that μ_{i} is maximal. Definition 3. The initial ideal of I with respect to < is

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

The fundamental reason that this is so useful is the following theorem, due to Macaulay (it’s Theorem 15.3 in Eisenbud): Theorem 1. The set of monomials not in in_{<}(I) is a basis for R/I as a k-vector space.

In particular, R/I ≅ R/ in(I) as vector spaces. If I is homogeneous, then this implies that R/I and R/ini(I) have the same Hilbert series.

It is obvious that if {f_{i}} are generators for I, then

in_{<}(I) ⊇ (in_{<}(f_{i})).

However, the reverse inclusion is NOT in general true. It’s not hard to come up with a counterexample. Suppose we have a term order < on k[x, y, z] in which x > y > z. Consider the ideals

I = (x − y), J = (x − y, x − z).

Then in_{<}(x − y) = in_{<}(x − z) = x, but surely we can’t want to replace both I and J with the monomial ideal (x), which doesn’t even have the same codimension as J. Besides, choosing a different set of generators for J would produce more initial terms: J = (x − y, y − z), and in(y − z) = (y). So it looks as if we should replace J with the monomial ideal (x, y), rather than x. Definition 4. A finite subset {f_{1}, …, f_{r}} ⊂ I is a Gröbner basis for I with respect to < if

in_{<}(I) = (in_{<}(f_{i})).

Theorem 2. Every ideal of R has a Gröbner basis.

Proof: Left as an exercise. (Hint: Use the fact that R is Noetherian.)

It’s not clear from the definition how to get your hands on a Gröbner basis. Fortunately, there is an algorithm, due to Buchberger, which takes as input a set of generators for an ideal and outputs a Gröbner basis.