Abstract
Short description of the post.
- Abstract
- Introduction
- Special Cases
- Generalising Long Division
- Leading Monomial Hold Center Stage
- Gröbner Basis
- Buchberger Algorithm for Constructing Gröbner Basis
- Equivalent Characterisations of Gröbner Basis
- Footnotes
Introduction
When an algebraic variety occurs in the wild, it is frequently given by the common vanishing set of a collection of polynomials. That is, we have a possibly infinite set of polynomials $\set{f_1(x), f_2(x), \dots} \subset k[x_1, \dots, x_d]$\(k[x_1, \dots, x_d]\) is the ring of polynomials in $d$ variables with coefficients in a field $k$ which we mostly assume to be $\R$ or $\C$. We sometimes write $k[x]$ when it is clear that $x = (x_1, \dots, x_n)$. , and our variety $X$ is given by
\[X = \V\brac{\{f_i\}_i} := \set{f_1(x) = 0 \text{ and } f_2(x) = 0, \text{ and } \dots}.\]And really, it is the ideal generated by the set of polynomials that matters not the polynomials themselves. The given set of polynomials should be treated as the generators of the ideal, \(I = \abrac{f_1, f_2, \dots}\). We then write the same algebraic variety as
\[X = \V\brac{I} = \V\brac{\abrac{f_1, f_2, \dots}}\]If we wish to do computation with varieties and their associated ideals, it would be nice to be able to do the following:
Reduce to finite description Outside of toy examples, the initial description of the variety probably have infinite number of generators $f_i$. It would be nice if we can reduce to a cleverly selected finite set of generators $g_i$ that encode the same ideal. This also begs the question: given another set of generators \(\brac{g_i}\), how can we tell with finite computation if they describe the same ideal?
Check ideal membership Given another polynomial $p \in k[x]$, can we check that $p$ is in fact in the ideal $I$? Well, we need to check that $p$ is a finite combination of the generators, $p = \sum_{i} q_i f_i$ with polynomial coefficients $q_i \in k[x]$. How do we find those?
Identify variety from ideal Given the ideal, \(I = \abrac{f_i}\) how do we actually solve the system of polynomial equations, $f_1(x) = f_2(x) = \dots = 0$, to obtain the points in the variety.
Identify ideal from variety
If the variety is instead given by a (rationally) parametrised geometric object, can we recover the ideal from the parametrisation? For example, the unit circle in $\R^2$ is parametrised by \begin{equation} t \mapsto \brac{\frac{1 - t^2}{1 + t^2}, \frac{2t}{1 + t^2}}. \end{equation} Can we recover the defining polynomial $x^2 + y^2 = 1$ from the parametrisation above?
Special Cases
It turns out that the solution to the above problems for special cases correspond to familiar concepts and algorithms. Specifically,
$f_i$ are polynomials of degree 1 with $d \geq 1$ variables, meaning they are linear equations in $d$ unknowns, then methods in linear algebra applies. Specifically, we can use Gaussian Elimination algorithm to reduce the system of equations into a convenient normal form.
$f_i$ are polynomials of degree $\geq 1$ in only $d=1$ variable, then we can use Euclidean division, again, to reduce the problem into a normal form.
As we shall see, algorithms for the special cases above fails in the general case in specific ways and fixing them give rise to Grobner basis.
Degree $=1$ but Multivariable
Here, we are given $n$ linear polynomialsmore precisely degree $=1$ polynomials in $k[x_1, x_2, \dots, x_d]$
\[\begin{aligned} f_1(x_1, \dots, x_d) &= a_{11}x_1 + a_{12} x_2 + \dots a_{1d} x_d + c_1 = 0 \\ f_2(x_1, \dots, x_d) &= a_{21}x_1 + a_{22} x_2 + \dots a_{2d} x_d + c_2 = 0 \\ &\vdots \\ f_n(x_1, \dots, x_d) &= a_{n1}x_1 + a_{n2} x_2 + \dots a_{nd} x_d + c_n = 0 \end{aligned}\]and the task is to find their vanishing set \(\V\brac{f_1, \dots, f_n}\). Here, we can bring to bear the full weight of linear algebra. In particular, we have the famous Gaussian elimination procedure.
Lets do an example,
\[\begin{aligned} f_1 &= 2x + 3y - z = 0\\ f_2 &= x + y -1 = 0\\ f_3 &= x + z -3 = 0 \end{aligned}\]
Using gaussian elimination to solve the special case of varieties defined by polynomials of degree 1
Single Variable but Degree $>1$
In this case, we have $n$ single variable polynomials in $k[x]$, each having arbitrary degree
\[\begin{aligned} f_1(x) &= a_{10} + a_{11}x + \dots + a_{1d_1}x^{d_1}\\ f_2(x) &= a_{20} + a_{21}x + \dots + a_{2d_2}x^{d_2}\\ &\vdots\\ f_n(x) &= a_{n0} + a_{n1}x + \dots + a_{nd_n}x^{d_n}.\\ \end{aligned}\]Fortunately, for $k$ a field, $k[x]$ is an Euclidean domaininformally, an integral domain where the Euclidean algorithm make sense and works. and therefore, by a standard result in algebra, a principal domain, meaning the ideal \(I = \left\langle f_1, \dots, f_n \right\rangle\) is actually generated by a single $g \in I$. Indeed, the ideal is generated by any element with the lowest degree in $I$. One way to compute a generator is to simply perform the eponymous Euclidean algorithm for finding $gcd(f_1, \dots, f_n)$.
Example,
\[\begin{aligned} f_1 &= x^4 + x^2 - x -1 \\ f_2 &= x^3 -1 \end{aligned}\]
Using Euclidean long division repeatedly to find the greatest common divisor between two polynomials
We can then conclude that the ideal $\abrac{f_1, f_2}$ is simply the ideal generated by their gcd, that is
\[\abrac{f_1, f_2} = \abrac{x -1}\]This means that the variety is simply given by
\[\V(f_1, f_2) = \V(x -1) = \set{x \in \R \st x -1 = 0} = \set{1}.\]This description is (slightly) easier than the original for identifying points on the variety:
\[\V(f_1, f_2) = \set{x \in \R \mid x^4 + x^2 -x - 1 = 0 \text{ and } x^3 - 1 = 0}.\]Generalising Long Division
As we saw above, an essential feature of the single variable case that makes the Euclidean algorithm work is the ability to do long division. Put it another way, given polynomial $p$ and polynomial divisor $f$ , we can find the quotient polynomial $q$ such that
\[p(x) = q(x)f(x) + r(x)\]with $r(x)$ having lower degree than the divisor $f$.
To generalise this to multivariate polynomials, we seek to generalise the above in two ways:
- we allow multivariate polynomials $p \in k[x_1, \dots, x_d]$ and
- we are allow to divide by a finite set of polynomials $f_1, \dots f_n$. Meaning want to find a set of quotients $q_1, \dots, q_n$ and a possibly zero polynomial remainder $r$ such that \begin{aligned} p = q_1 f_1 + \dots + q_n f_n + r \end{aligned} where we enforce that $r$ cannot in some sense be further divided by any of the $f_i$.
The generalisation is rather straight forward. However, as we shall see, it loses some desirable properties that we rely on in the two special cases we investigated.
Example, TODO….
Leading Monomial Hold Center Stage
The last example is particularly galling. Getting zero remainder immediately give us an expression of $p = q_1f_1 + \dots + q_nf_n$ which is a witness that \(p \in \left\langle f_1, \dots, f_n \right\rangle\). However, whether we end up with zero remainder or not depend on how we order the generators. Worse still, sometimes the division produces "intermediate" remainder terms. In either case, even ifthere is a little magic happening here where we suddenly restrict ourselves to just long division of element of the ideal. Turns out solving this case is enough though. $p \in I$, whether we get zero remainder is a matter of luck and the issue seems to be that the algorithm run into a blocker: The leading term of some intermediate remainder ${\mathrm{LT}}(r)$ is no longer divisible by any leading term $\mathrm{LT}(f_i)$ of the generating polynomials. This is the root of all evil.
To rephrase, we have the scenario that some combination $\sum q_i f_i$ of the generators produces remainderdifference of elements of the ideal is in the ideal., $r = p - \sum q_i f_i \in I$, but $\mathrm{LT}(r)$ is no longer divisible by any of $\mathrm{LT}(f_i)$, i.e. $\mathrm{LT}(r)$ is not in the ideal generated by $\mathrm{LT}(f_1), \dots, \mathrm{LT}(f_n)$. Varying $q_i$, the expression of the form $p - \sum q_i f_i$ is all of $I$, so our issue is thatnote that \(\left\langle \mathrm{LT}(f_1),\mathrm{LT}(f_2), \dots \right\rangle \subset \left\langle \mathrm{LT}(I) \right\rangle\) follows trivially from definition. It is the reverse inclusion that is causing grief. \(\begin{aligned} \left\langle \mathrm{LT}(f_1),\mathrm{LT}(f_2), \dots \right\rangle \neq \left\langle \mathrm{LT}(I) \right\rangle \end{aligned}\) where \(\mathrm{LT}(I) = \left\{\mathrm{LT}(p) \, \, : \,p \in I\right\}\).
Since it is really the ideal that we care about, not the given generators per se, our quest to solve the problems pose at the beginning would be resolved if we can find another set of generatorsAlso note this second jedi mind trick where I switch to using notation to $\mathrm{LT}(f_1), \dots$ suggesting potentially infinite generating set. We are hoping that $G$ turns out to be finite regardless of the initial size of \(\left\{f_i\right\}\). $G \subset I$ such that we do have
Monomially Generated Ideals
Our problem motivate the study of ideals that are generated by all leading terms of $p \in I$. These generating sets are monomials.
An ideal $I \subset k[x_1, \dots, x_d]$ is monomially generated[@Cox2013-xd] calls it monomial ideals, but I personally remember this name better. if it has a (potentially infinite) generating set consist of only monomials.
That is
\(\begin{aligned} I = \left\langle x^\alpha \, \, : \,\alpha \in A \right\rangle \end{aligned}\) for some multiindex set $A \subset \N^d$.
Fortunately for us, it turns out that the membership problem for monomially generated ideals is simpler.
A monomial $x^\beta$ is in a monomially generated ideal \(I = \left\langle x^\alpha \, \, : \,\alpha \in A \right\rangle\) if and only if $x^\alpha$ divides $x^\beta$ for some $\alpha \in A$. Furthermore, any polynomial $p$ is in $I$ if and only if all of its monomial is in $I$.[@Cox2013-xd Chapter 2.4, Lemma 2]
In other words, we can test ideal membership of a monomial by testing if $\beta \geq \alpha$ for some $\alpha \in A$ with the lexicographic ordering on $\N^d$.
A main result here is that
Monomially generated ideals are finitely generated by monomials. Furthermore, the finite generating set can be chosen from any monomial generating set. [@Cox2013-xd Chapter 2.4, Theorem 5]
This is more or less the Hilbert basis theorem for monomially generated ideals and we shall see that this result extends directly to the full Hilbert basis theorem.
Gröbner Basis
We are very close to our AH HA! moment. Our problem is that the leading terms of the original generators $f_i$ does not generate \(\left\langle \mathrm{LT}(I) \right\rangle\). But \(\left\langle \mathrm{LT}(I) \right\rangle\) is a monomially generated ideal and Dickson’s lemma says that it is actually finitely generated by some \(\mathrm{LT}(g_1), \dots, \mathrm{LT}(g_m)\), $g_i \in I$. In other words,
\(\begin{aligned} \left\langle \mathrm{LT}(g_1), \dots,\mathrm{LT}(g_m) \right\rangle = \left\langle \mathrm{LT}(I) \right\rangle. \end{aligned}\) All we need is that these $g_i$’s will themselves, with their trailing terms and all, generate all of $I$. Well, they do!
Let $I \subset k[x_1, \dots, x_d]$ be any ideal. Let $g_1, \dots, g_m \in I$ be such that \(\left\langle \mathrm{LT}(g_1), \dots,\mathrm{LT}(g_m) \right\rangle = \left\langle \mathrm{LT}(I) \right\rangle\), then \(\left\{g_1, \dots, g_m\right\}\) generates $I$.
In honour of such nice property, we give such generating sets a name.
A generating set \(\left\{g_1, \dots, g_m\right\} \subset I\) of any ideal $I$ of $k[x_1, \dots, x_d]$ with the property that
\[\left\langle \mathrm{LT}(g_1), \dots,\mathrm{LT}(g_m) \right\rangle = \left\langle \mathrm{LT}(I) \right\rangle\]is called a Gröbner basismore a Gröbner generating set really. It doesn’t have the unique coefficient property like a basis of vector space..
Buchberger Algorithm for Constructing Gröbner Basis
Equivalent Characterisations of Gröbner Basis
Let $k$ be any field and $I$ be an ideal of the polynomial ring $k[x_1, \dots, x_d]$ generated by \(G = \left\{g_1, \dots, g_n\right\}\). The following are equivalentin somewhat increasing order of "finiteness".
$G$ is a Gröbner basis for $I$.
for all $p \in k[x_1, \dots, x_d]$, the remainder of $p$ divided by $G$ is unique.
division of $p$ by $G$ does not generate “intermediate remainder” at any stage of the algorithm.
$p \in I$ if and only if $p \equiv 0$ mod $G$.
\(\left\langle \mathrm{LT}(G) \right\rangle = \left\langle \mathrm{LT}(I) \right\rangle\).
for all $p \in I$, \(\mathrm{LT}(p) \in \left\langle \mathrm{LT}(G) \right\rangle\).
for all $p \in I$, $\mathrm{LT}(g_i)$ divides $LT(p)$ for some $g_i \in G$.
$G$ satisfies Buchberger’s criterion.
Comments powered by Disqus.