§ What the hell is a Grobner basis? Ideals as rewrite systems

§ A motivating example

The question a Grobner basis allows us to answer is this: can the polynomial p(x,y)=xy2+yp(x, y) = xy^2 + y be factorized in terms of a(x,y)=xy+1,b(x,y)=y21a(x, y) = xy + 1, b(x, y) = y^2 - 1, such that p(x,y)=f(x,y)a(x,y)+g(x,y)b(x,y)p(x, y) = f(x, y) a(x, y) + g(x, y) b(x, y) for some arbitrary polynomials f(x,y),g(x,y)R[x,y]f(x, y), g(x, y) \in R[x, y]. One might imagine, "well, I'll divide and see what happens!" Now, there are two routes to go down:
  • xy2+y=y(xy+1)=ya(x,y)+0b(x,y)xy^2 + y = y(xy + 1) = y a(x, y) + 0 b(x, y). Well, problem solved?
  • xy2+y=xy2x+x+y=x(y21)+x+y=xb(x,y)+(x+y)xy^2 + y = xy^2 - x + x + y = x (y^2 - 1) + x + y = x b(x, y) + (x + y). Now what? we're stuck, and we can't apply a(x, y)!
So, clearly, the order in which we perform of factorization / division starts to matter! Ideally, we want an algorithm which is not sensitive to the order in which we choose to apply these changes. x2+1x^2 + 1.

§ The rewrite rule perspective

An alternative viewpoint of asking "can this be factorized", is to ask "can we look at the factorization as a rewrite rule"? For this perspective, notice that "factorizing" in terms of xy+1xy + 1 is the same as being able to set xy=1xy = -1, and then have the polynomial collapse to zero. (For the more algebraic minded, this relates to the fact that R[x]/p(x)R(roots of p)R[x] / p(x) \sim R(\text{roots of p})). The intuition behind this is that when we "divide by xy+1xy + 1", really what we are doing is we are setting xy+1=0xy + 1 = 0, and then seeing what remains. But xy+1=0    xy=1xy + 1 = 0 \iff xy = -1. Thus, we can look at the original question as: How can we apply the rewrite rules xy1xy \rightarrow -1, y21y^2 \rightarrow 1, along with the regular rewrite rules of polynomial arithmetic to the polynomial p(x,y)=xy2+yp(x, y) = xy^2 + y, such that we end with the value 00? Our two derivations above correspond to the application of the rules:
  • xy2+yxy=1y+y=0xy^2 + y \xrightarrow{xy = -1} -y + y = 0
  • xy2+yy2=1x+ystuck!xy^2 + y \xrightarrow{y^2 = 1} x + y \nrightarrow \text{stuck!}
That is, our rewrite rules are not confluent) The grobner basis is a mathematical object, which is a a confluent set of rewrite rules for the above problem. That is, it's a set of polynomials which manage to find the rewrite p(x,y)0p(x, y) \xrightarrow{\star} 0, regardless of the order in which we apply them. It's also correct, in that it only rewrites to 00 if the original system had some way to rewrite to 00.

§ The buchberger's algorithm

We need to identify critical pairs), which in this setting are called as S-polynomials. Let fi=H(fi)+R(fi)f_i = H(f_i) + R(f_i) and fj=H(fj)+R(fj)f_j = H(f_j) + R(f_j). Let m=lcm(H(fi),H(fj))m = lcm(H(f_i), H(f_j)), and let mi,mjm_i, m_j be monomials such that miH(fi)=m=mjH(fj)m_i \cdot H(f_i) = m = m_j \cdot H(f_j). The S-polynomial induced by fi,fjf_i, f_j is defined as S(fi,fj)=mifimifjS(f_i, f_j) = m_i f_i - m_i f_j.

§ References