Gröbner bases and geometry

Algebra is the offer made by the devil to the mathematician. The devil says: “I will give you this powerful machine, it will answer any question you like. All you need to do is give me your soul: give up geometry and you will have this marvelous machine. — Michael Atiyah

Back in the day when dinosaurs still roamed Palo Alto and I was a clueless Stanford junior undergrad, I tried and failed many times to understand Gröbner bases. Now I have to implement Gröbner bases for my research, after a Saturday’s suffering, I finally seem to understand what’s going on with Gröbner bases from the wonderful paper [1] What can be computed in algebraic geometry?. This note summarises my learning so far. In retrospect, I hope someone taught me this when I took my first scheme-based algebraic geometry class as an example of the subtlety of algebraic structures compatible with algebraic varieties.

Gröbner Bases

First recall Buchberger’s algorithm which finds a basis for an ideal ${I}$ of a polynomial ring ${R}$ proceeds as follows (pseudo-code generated by Claude based on the Wikipedia page).

Input A set of polynomials ${F}$ that generates ${I}$

Output A Gröbner basis ${G}$ for ${I}$

${G := F}$
For every ${f_i, f_j}$ in ${G}$ , denote by ${g_i}$ the leading term of ${f_i}$ with respect to the given monomial ordering, and by ${a_{ij}}$ the least common multiple of ${g_i}$ and ${g_j}$ .
Choose two polynomials in ${G}$ and let ${S_{ij} = \frac{a_{ij}}{g_i} f_i - \frac{a_{ij}}{g_j} f_j}$ (Note that the leading terms here will cancel by construction).
Reduce ${S_{ij}}$ with the multivariate division algorithm relative to the set ${G}$ until the result is not further reducible. If the result is non-zero, add it to ${G}$ .
Repeat steps 2–4 until all possible pairs are considered, including those involving the new polynomials added in step 4.
Output ${G}$ .

When I first learnt about this, it seemed to me extremely unclear what exactly is going on. Why do we choose a monomial ordering? How does the choice of a different monomial ordering affect the runtime? The geometric insight in [1] is to relate the monomial ordering to a 1-parameter family of automorphism of the projective space wherein the variety defined by the set of polynomials ${F}$ embeds.

In particular, let ${X}$ be the algebraic variety defined by ${F}$ (take homogenization) in some projective scheme ${\mathbb{P}^n}$ , consider a one-parameter subgroup ${\lambda(t) \subset GL(n + 1)}$ of the diagonal form

$\displaystyle \lambda(t) = \begin{bmatrix} t^{w_0} & & & \\ & t^{w_1} & & \\ & & \ddots & \\ & & & t^{w_n} \end{bmatrix},$ where each ${\lambda(t)}$ induces an automorphism of ${\mathbb{P}^n}$ where we identify the image of ${X}$ as ${X_t}$ . Let ${x^A = x_0^{a_0}\ldots x_n^{a_n}}$ be a monomial in the homogeneous coordinate ring of ${\mathbb{P}^n}$ . Then the automorphism ${\lambda(t)}$ maps a homogenous polynomial ${f = ax^A + bx^B + \ldots}$ to ${\lambda f = at^{W\cdot A}x^A + bt^{W\cdot B}x^B + \ldots}$ .

From here, one may take projective limits of ${\lambda f}$ and ${X_t}$ in the projective spaces and ponder what happens at ${t = 0}$ . The upshot is that with a particular choice of the one-parameter automorphism groups, we can recover exactly the monomial ordering (exercise: recover the lexicographic and reverse lexicographic ordering this way; the reverse lexicographic order described in [1] is actually the graded lexicographic order, but they coincide here since we consider homogeneous coordinates) as the projective limit of ${\lambda f_t}$ for ${t}$ away from ${0}$ .

Back to the question about what happens to ${\varprojlim X_t}$ as ${t}$ approaches ${0}$ , the “right” perspective is to define a ${\mathbb{P}^n[t]}$ -scheme ${X'}$ whose fiber at ${t}$ recovers ${X_t}$ . An obvious attempt is to define ${X'}$ to be generated by each ${g_t}$ as the quotient of ${f}$ divided by the largest power of ${t}$ in its monomials, which would recover ${X_t}$ at fibers away from ${0}$ . However, at ${t = 0}$ , the situation is not nice as the projection from ${X'}$ is not necessarily flat (or equivalently the syzygies upstairs do not generate the ones downstairs). To make it flat, we lift syzygies upstairs, which amounts to adding “ ${t}$ -torsion” points to the coordinate rings, which recovers exactly the “multivariate division” part of Buchberger’s algorithm! Therefore the Gröbner bases in some sense define a flat family of varieties whose fiber at general position recovers the original variety ${X}$ .

Connections to Regularity

It turns out Gröbner bases relate to Hilbert functions and its computational complexity relates to Castelnuovo-Mumford regularity (also can be used to construct Hilbert schemes). I strongly recommend working through the example in [1] to gain intuition. One particular nice thing is that reducing by lexicographic order or reversed lexicographic order is related to projection of the orignal variety to some subspaces ([1] discusses really cool connections to flag varieties in birational geoemtry). The upshot is that lexicographic order reduction corresponds to the projection ${\mathbb{P}^n \rightarrow \mathbb{P}^{n-1}}$ where ${\mathbb{P}^n}$ is viewed as the Thom space of the tautological bundle over ${\mathbb{P}^{n-1}}$ and reverse lexicographic order reduction corresponds to projection from the point at infinity. This intuitively explains why in practice reverse lexicographic order reduction works better, as the relevant projection maps are simpler – which is pretty cool as the hidden geometry is not obvious at all if one only thinks about the ordering.

Gröbner bases and geometry

Share this:

Comments

Leave a comment Cancel reply

More posts

Miller’s Algorithm and Pairing

Gröbner bases and geometry

Starting a blog