Groebner Bases and Buchberger’s Algorithm

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

About Charles Siegel

Charles Siegel is currently a postdoc at Kavli IPMU in Japan. He works on the geometry of the moduli space of curves.
This entry was posted in AG From the Beginning, Algebraic Geometry, Big Theorems, Computational Methods. Bookmark the permalink.

7 Responses to Groebner Bases and Buchberger’s Algorithm

  1. Groebner bases give computational proofs of several of the problems in the first section of the dreaded book of Hartshorne.

    But the first section isn’t the dreaded part. It’s the hugely unmotivated leap from the first to the second.

  2. Charles says:

    I’m aware, but still, these techniques helped when I sat down and did all the problems in chapter 1 in order to convince myself that I had enough classical geometry to understand the second part. I was way off in that belief, but still, it WAS helpful.

    As for the unmotivated leap, I hope that I’ve at least helped motivate it by talking about nonreduced things, as well as schemes that are like nonreduced varieties but not of finite type (ie, the Hilbert scheme). Hartshorne even mentions the Hilbert scheme in his section on flatness, but is vague about it and doesn’t even define moduli spaces.

    Plus, these techniques can be used on some of the problems later in the book, or at least generalizations of them can, at least in the special case of abstract varieties.

  3. Todd Trimble says:

    I remember working through chunks of Hartshorne in graduate school when I took a course in algebraic geometry; since you say you’ve done all the problems in chapter 1, maybe I could ask you whether the techniques described in this post have any bearing on problem 1.11 [which as I recall gave me a lot of trouble -- I don't think I managed to solve it :-( ]?

  4. Charles says:

    The techniques specifically don’t, but the ideas of looking at lead terms of polynomials do. Let me know if you want the trick. Was going to use these techniques explicitly to solve the problems involving cuspidal and twisted cubics.

  5. Jason Starr says:

    I especially like how Groebner bases allow you to do the elimination theory to compute images of projective varieties. According to Hartshorne, to find the image in P^n of a projective subvariety of P^n x P^m, you should do something crazy with valuation rings. According to Harris’s book, you should compute some huge number of resultants, which is also unreasonable. But in fact, you should just compute a Groebner basis.

  6. Charles says:

    Yeah, a lot of problems like that are just tricks involving writing down the right ring homomorphism and computing the kernel. This is, I believe, my favorite use of Groebner bases, and sadly it doesn’t appear in Cox, Little, O’Shea, though it’s easy to prove it as a consequence of Elimination.

  7. Pingback: Elimination and Extension Theorems « Rigorous Trivialities

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s