After all that technical work and careful but rather abstract technique developed for the construction of a bunch of moduli spaces, I’ve decided to take a break from that line of reasoning and to look to one that’s rather dear to me. It’s probably just that these methods were my first real introduction to algebraic geometry, and I use them to construct examples routinely. We’re not just dropping back to varieties here, we’re going all the way back to affine varieties over an algebraically closed field for a bit, and eventually will be stepping all the way back to characteristic zero for some stuff related to representation theory. Well, truthfully, it’s time for algebra in the coordinate ring.

We start as Cox, Little and O’Shea did in their book Ideals, Varieties and Algorithms by asking a bunch of questions. The same questions, actually. Well, mostly. We assume that we’re given an ideal I=(f_1,\ldots,f_r) in k[x_1,\ldots,x_n]. First up, can we determine if a given polynomial is in I? Well, if n=1, then the answer is easy: use long division. If the remainder is zero, then yes, if not, then no. Simple. But what about if n\geq 2? Is there an algorithmic way to check? The answer turns out to be yes, but requires some care in the set up.

First we need a nice ordering of all monomials in k[x_1,\ldots,x_n]. By this, what we mean is a relation on the monomials > such that it is a total order (ie, given two monomials, one is always greater than the other), such that if x^\alpha>x^\beta, and x^\gamma any monomial, we have x^{\alpha+\gamma}>x^{\beta+\gamma}. That is, it is preserved by multiplication of monomials. Finally, we want it to be a well-ordering. That is, every nonempty subset has a smallest element. We’ll sometimes, for simplicity, refer to the exponents (which are multi-indices, so x^\alpha=x_1^{\alpha_1}\ldots x_n^{\alpha_n}) as the elements being ordered. Being finite lists of natural numbers, we can add and subtract them nicely.

There are many natural orderings to use. The first one to come to mind is the lexicographic ordering. It says that \alpha>\beta if and only if \alpha-\beta has its leftmost nonzero entry positive. That is, the first term in which they disagree, \alpha has the bigger entry. Another good one is called graded lexicographic order, which first orders by degree, and then lexicographically within each degree.

However, for reasons that require a grounding in computational complexity, the best one (ie, it has the average best runtime for the algorithm we’ll talk about shortly) is graded reverse lexicographic. First it orders by degree. Then, it has \alpha>\beta if and only if the rightmost nonzero entry of \alpha-\beta is negative. I haven’t read the paper that proves that it’s the best, and probably won’t, but from having worked with it, I’m willing to believe it. (Partly because I’m not trying to prove anything based on it being the best)

Now, we define the multidegree of a polynomial to be the maximal \alpha which appears in it. the lead monomial is then x^\alpha, and the lead coefficient is the coefficient of x^\alpha. Now, these orderings all reduce to the normal ordering on k[x], and there we use the grading to do division. It turns out that a monomial ordering is just what we needed for bigger rings.

Let I=(f_1,\ldots,f_s) in k[x_1,\ldots,x_n] and fix a monomial ordering. Then there is a division algorithm. We start with the generators of the ideal, in some order, and the polynomial to be divided by them. Then we proceed by taking the lead term of f, which is the lead coefficient times the lead monomial, and we look to see if the lead monomial of f_1 divides it, and failing that, we check all the other lead terms, in order. The goal is to write f=a_1f_1+\ldots+a_sf_s+r, so what we do is we take a_i (all of which start at zero) and replace it by a_i+\frac{LT(f)}{LT(f_i)}, and then we replace f with f-\frac{LT(f)}{LT(f_i)}f_i. Now, if none of the lead terms divide the lead term of f, we replace r (which starts as zero, of course) with r+LT(f) and replace f with f-LT(f). We continue this process until f is gone. In fact, the remainder is a linear combination of monomials, none of which is divisible by any of the lead terms.

Now, this does tell us if f lies in I. If will if r=0. However, there are some problems with this algorithm. For one, the choice of generating set for the ideal matters, and, even worse, the ordering of the generating set matters. Try dividing x^2y+xy^2+y^2 by xy-1 and y^2-1 with the lexicographic order. The result will be (x+y)(xy-1)+(y^2-1)+x+y+1. Reversing the order, the division gives (x+1)(y^2-1)+x(xy-1)+2x+1.

To solve this problem, we define another ideal. Given I, we define LT(I) to be the ideal generated by the elements of the form LT(f) for f\in I. Now, this is finitely generated, which is helpful. We define a Groebner basis for I to be a set g_1,\ldots,g_t if the ideal (LT(g_1),\ldots,LT(g_t)) is equal to LT(I). Now, every ideal other than the zero ideal has a Groebner basis, and a Groebner basis necessarily generates the ideal.

Groebner bases have the nice property that for any I and f, if you take a Groebner basis for I, then there’s a unique r such that no term of r is divisible by the lead term of an element of the Groebner basis and there is g\in I such that f=g+r. The point of this is that it doesn’t matter what order you perform the division in! This gives us the fact that if we divide a polynomial by a Groebner basis, then f\in I iff r=0, which is great, it solves the ideal membership problem completely, so long as we can find the Groebner bases.

So for now we set up the following notation: if F is an ordered s-tuple of polynomials, then we denote by \bar{f}^F the remainder upon division by F. Now, given two monomials x^\alpha and x^\beta, we will denote their least common multiple by x^\gamma. In fact, given f and g polynomials, we’ll use x^\gamma to denote the least common multiple of their leat monomials. So then we define the S-polynomial to by S(f,g)=\frac{x^\gamma}{LT(f)}f-\frac{x^\gamma}{LT(g)}g. The S stands for syzygy, and we’ll talk about sygygies more at some point in the future. It just happens that all the syzygies in this situation are given by S-polynomials.

Now, Buchberger gave a criterion for when a basis is a Groebner basis, which can then be turned into an algorithm. If G=(g_1,\ldots,g_t) is a basis, it is a Groebner basis if and only if for all i\neq j, we have \overline{S(g_i,g_j)}^G=0.

So now Buchberger’s algorithm is a simple idea. Take any basis F=(f_1,\ldots,f_s) and toss things into it until it’s a Groebner basis. Start out with G=F and take a pair (p,q) in it. Then look at S=\overline{S(p,q)}^G. If S isn’t zero, then append it to G. Continue until done. This process can be shown to terminate, and so shows that any basis can be extended to a Groebner basis.

Now, we get all sorts of extra stuff in our basis this way, stuff that isn’t needed even for it to be Groebner. To get a smaller one, we note that if p\in G such that LT(p) is in the ideal generated by the lead terms of the other elements of G, then G\setminus \{p\} is also a Groebner basis.

Now, we can use Groebner bases to do all sorts of fun things. They let us put together computational versions of the Elimination and Extension Theorems (we’re heading in that direction) and let us compute the kernels of certain ring homomorphisms, which means that we can get the ideals for varieties defined parametrically. We can even use them to perform Primary Decomposition. This means that Groebner bases give computational proofs of several of the problems in the first section of the dreaded book of Hartshorne. We’ll see more consequences of these ideas as we go.

About these ads