ALGEBRA III SEPTEMBER 9, 2004

GABRIEL C. DRUMMOND-COLE

Monomial ideals are easiest: I = ⟨m_{i}|i ∈ A⟩ ⊂ k[x_{1}, …, x_{n}] = S. Monomials are m = \underline{x}\underline{α} = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}. We can look at the staircase diagram that comes from α.

So we want to look at the dimension of R = k[x_{1}, …, x_{n}]/I = ⊕_{i=0}^{∞}R_{i} a k-vectorspace. Note that R_{i}R_{j} ⊂ R_{i+j}.

Now, dim_{k}(R) = and dim_{k}(R_{i}) is the number of monomials of degree i in S not in I_{i}.

Now say J is a more general ideal. We’re going to find a monomial ideal I such that all monomials not in I form a basis for S/J as a k-vector space. This will prove the Hilbert basis theorem. It will also eventually allow us to decide whether an element of S lives in J. If J is homogeneous, I’ll also be able to find the dimensions of the graded pieces. If J is a homogeneous ideal ⟨f_{1}, …, f_{n}⟩, then S/J is a graded vector space ⊕_{i=0}^{∞}V_{j}. We have a very important function H : p → dim)k(S/J)_{p}. It turns out that this agrees with a polynomial except at finitely many values.

Now if J were a monomial ideal, then counting this dimension would be easy. So how do you find this monomial ideal? You essentially want to pick monomials out of the polynomials you have. So you need some sort of ordering.

Now you need your monomial ideal to contain a monomial from each generator polynomial of J.

Definition 1. Given an order on the variables, a monomial order on S = k[x_{1}, …, x_{n}] is a relation ≻ on \underline{x}\underline{α} such that

(1) ≻ is a total ordering

(2) ≻ is compatible with ·, so that \underline{x}\underline{α} ≻ \underline{x}\underline{β} implies \underline{x}\underline{γ} \underline{x}\underline{α} ≻ \underline{x}\underline{γ} \underline{x}\underline{β}(≻ \underline{x}\underline{γ}

(3) ≻ is a well-ordering (redundant with the end of the previous line)

Exercise 1. Show that any selection function to give the monomial ideal I must be a monomial order.

Exercise 2. Show that there is only one monomial order on k[x], the order by degree.

Typically a monomial order will refine the degree. Now say you are in k[x_{1}, …, x_{n}]. Here are some orders:

• lex: Here, \underline{x}\underline{α} ≻ \underline{x}\underline{β} if the leftmost nonzero entry of \underline{α} − \underline{β} is positive.

• Grlex: Grade first by degree, i.e., by α ≻ β if |α| > |β| and then if |α| = |β| you grade by lex.

• This is a bad order, but is the best possible for doing computations. You can eliminate variables. revlex: \underline{x}\underline{α} ≻ \underline{x}\underline{β} if either |α| > |β| or |α| = |β| and the rightmost nonzero entry of α − β is negative.

Exercise 3. There is one order refining degree in two variables.

So compare x^{3}y^{6} with x^{3}y^{4}z, then x^{3}y^{6} is greater in glex. This is also largest in revlex.

On the other hand, for xz and y^{2} we have xz larger in glex and y^{2} larger in revlex.

There are other orders you can build, which have some geometric interpretation. You look at some weighted functional related to a polytope in some way.

Definition 2. If f ∈ k[x_{1}, …, x_{n}] and ≻ is a monomial ordering, then the initial m_{≻}(f) is the largest monomial in f with respect to ≻ .

Exercise 4. (1) If m_{lex}(f) ∈ k[x_{s}, …, x_{n}], then f ∈ k[x_{s}, …, x_{n}]. If f is homogeneous then

the same is true for m_{Grlex}.

(2) If m_{revlex}(f) ∈ (x_{s}, …, x_{n}), then f ∈ (x_{s}, …, x_{n}). Note that this is an ideal whereas in the first case it was a subring.

Lemma 1. Dickson Lemma Any set of monomials has only finitely many minimal elements in the partial order given by divisibility. Equivalently, every monomial ideal is finitely generated (by a subcollection of any set of monomial generators)

Now take your favorite ideal J ⊂ S and a monomial ordering ≻ . Now take from each polynomial in J the initial monomial to get the initial ideal of J, m_{≻}(J) = ⟨m_{≻}(f)|f ∈ J⟩. With the Dickson lemma this will give us the Hilbert basis theorem. That is, m_{≻}(J) will be a monomial ideal. Then a subcollection ⟨m_{≻}(g_{1}), …, m_{≻}(g_{m})⟩ will generate m_{≻}(J) and we can get that ⟨g_{1}, …, g_{m}⟩ generates J. Then J is finitely generated. If you want to be really picky, this works not just over a field, but over any Noetherian ring. Now such a set {g_{1}, …, g_{m}} is called a Gröbner basis.

This shouldn’t really be called a Gröbner basis because Gröbner didn’t really work with these. His student did. Other people were already working with things like these, in, say, power series rings.

This is essentially Gordon’s proof of Hilbert’s basis theorem. The standard proof was by induction and was nonconstructive. Hilbert put the German mathematicians looking for these things out of business by saying that these were always finitely generated. But he gave no way to find the generators. Gordon gave you a way to find it.

You use this stuff to prove that k[x_{1}, …, x_{n}]^{σ_{n}} = k[y_{1}, …, y_{n}] by y_{i} → σ_{i}, where these are the symmetric polynomials of degree i.

Now I’m going to give you an algorithm. A lot of these are no good from a computer scientist standpoint. If you work in Grlex, the degree of the Gröbner basis will be doubly exponential in the number of variables, whereas with revlex the degree will be roughly comparable with the number of variables.

By the way, this also solves the problem of ideal membership. I give you a finite polynomial basis and I want to know if another polynomial, say 1 for instance, is in their span. You look instead at the initials. It is a combination if and only if the initial term is in the initial ideal.

Now let’s prove Dickson’s lemma. We’ll proceed by induction on the number of variables. If n = 1 then the ideal is ⟨x_{1}^{α}|α ∈ A ⊂ ℕ⟩ = ⟨x_{1}^{α_{min}}|α_{min} = min{α|α ∈ A}⟩ So if n = 1 then the ideal is principally generated.

For the induction step, I’m going to use \underline{x} to refer to the monomial factor in the first n − 1 variables. Now, we want to look at (I : x_{n}^{∞}) by which we mean ⟨\underline{x}\underline{α}|∃m_{α}, \underline{x}\underline{α}x_{n}^{m_{α}} ∈ I⟩. This is an ideal J ⊂ k[x_{1}, …, x_{n−1}] which is finitely generated (by \{\underline{x}\underline{α_{1}}, …, \underline{x}\underline{α_{s}}\} by induction. So take first \underline{x}\underline{α_{i}}x_{n}^{m_{i}} For each k < max\{m_{i}\} let J_{k} = (I : x_{n}^{k}) = ⟨\underline{x}\underline{α}|\underline{x}\underline{α}x_{n}^{k} ∈ I⟩ ⊂ k[x_{1}, …, x_{n−1}]. This is finitely generated by \{\underline{x}\underline{α_{k1}}, …, \underline{x}\underline{α_{ks}}\}. Then my Gröbner basis will be \{\underline{x}\underline{α_{i}}x_{n}^{m_{i}}, \underline{x}\underline{α_{kj}}x_{n}^{k}\}. So you just show that these generate I, which is fairly straightforward.

The only thing missing is that you can always get a subcollection. Say I = ⟨\underline{x}\underline{α}, α ∈ A⟩. We pick a Gröbner basis \{\underline{x}\underline{β_{i}}\}; each of these must be a multiple of some \underline{x}\underline{α_{i}}. Then this collection of corresponding \underline{x}\underline{α_{i}} generates I as well.

This triviality is called Macaulay’s theorem:

Theorem 1. A basis of S/I is formed by all monomials not in m_{≻}(I).