§ 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) = xy^2 + y$ be factorized in terms of $a(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)$ for some arbitrary polynomials $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:

• $xy^2 + y = y(xy + 1) = y a(x, y) + 0 b(x, y)$. Well, problem solved?
• $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. $x^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 + 1$ is the same as being able to set $xy = -1$, and then have the polynomial collapse to zero. (For the more algebraic minded, this relates to the fact that $R[x] / p(x) \sim R(\text{roots of p})$). The intuition behind this is that when we "divide by $xy + 1$", really what we are doing is we are setting $xy + 1 = 0$, and then seeing what remains. But $xy + 1 = 0 \iff xy = -1$. Thus, we can look at the original question as: How can we apply the rewrite rules $xy \rightarrow -1$, $y^2 \rightarrow 1$, along with the regular rewrite rules of polynomial arithmetic to the polynomial $p(x, y) = xy^2 + y$, such that we end with the value $0$? Our two derivations above correspond to the application of the rules:

• $xy^2 + y \xrightarrow{xy = -1} -y + y = 0$
• $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) \xrightarrow{\star} 0$, regardless of the order in which we apply them. It's also correct , in that it only rewrites to $0$ if the original system had some way to rewrite to $0$.

§ The buchberger's algorithm

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

§ References

• The term rewriting perspective is from the book "term rewriting and all that"
• Sympy has excellent reading material on grobner basis