§ 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
be factorized in terms of ,
such that for some arbitrary polynomials
One might imagine, "well, I'll divide and see what happens!" Now, there are two
routes to go down:
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. .
- . Well, problem solved?
- . Now what? we're stuck, and we can't apply
§ 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 is the same as being
able to set , and then have the polynomial collapse to zero.
(For the more algebraic minded, this relates to the fact that ).
The intuition behind this is that when we "divide by ", really what
we are doing is we are setting , and then seeing what remains. But
. Thus, we can look at the original question as:
How can we apply the rewrite rules , ,
along with the regular rewrite rules of polynomial arithmetic to the polynomial
, such that we end with the value ?
Our two derivations above correspond to the application of the rules:
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 , regardless of the order in which
we apply them. It's also correct , in that it only rewrites to if the
original system had some way to rewrite to .
§ The buchberger's algorithm
We need to identify
critical pairs ),
which in this setting are called as S-polynomials.
Let and . Let ,
and let be monomials such that .
The S-polynomial induced by is defined as .