7
$\begingroup$

In an upcoming exam we have to do Gröbnber-Basis computation with Buchberger's algorithm. A typical example looks like this:

$ \langle f_1,f_2 \rangle $

Then I compute the S-Polynomial $S(f_1,f_2)$. Most of the time $S(f_1,f_2)$ is an ugly expression so I use linear combinations of $\langle f_1, f_2, S(f_1,f_2)\rangle$ and obtain a new representation of the ideal with nice polynomials $\langle f_1',f_2',f_3' \rangle$.

Now, I have to restart Buchberger's algorithm because I have changed the ideal representation and compute $S(f_1',f_2'), S(f_1',f_3') \dots$. Usually $\langle f_1',f_2',f_3' \rangle$ is a valid Gröber basis already. But to compute the three (or more) S-Polynomials takes a lot of time. Is there are a (fast computable) criteria to check whether a given basis is already a Gröbner-Basis and to abort the computation?

  • 1
    I believe the answer you are looking for is in these [lecture notes by Victor Adamchik](http://www.andrew.cmu.edu/course/15-355/lectures/lecture11.pdf). I could be incorrect, however, my experiences with Gröbner Bases is mostly computational.2012-09-02

1 Answers 1

2

Given generators $f_1, \dots, f_n$ for an ideal $I$, you can reduce each $S$-polynomial $S(f_i, f_j)$ using the $f_1, \dots, f_n$. Reducing here means repeatedly canceling the highest degree term of $S(f_i, f_j)$ (in whatever admissible monomial ordering you are using) by subtracting a suitable multiple of one of the $f_k$ (i.e., multiply by $f_k$ by some monomial such that its highest terms equal that of $S(f_i, f_j)$ and subtract; repeat until the leading term of what is left of $S(f_i, f_j)$ is not a multiple of the leading term of any of the $f_k$). If all $S$ polynomials reduce to 0, your original generators form a Gröber basis already.

In fact, this is how you would generally compute a Gröber basis: you keep adding reductions of $S$-polynomials to the set of generators until they all reduce to 0. (And in between you simplify the generators by reducing using a newly computed reduction of an $S$-polynomial).

  • 0
    I think what your describing is the cancellation criterion of Buchberger's algorithm. I was trying to avoid that computation and was looking for some kind of short cut to proof that the computation can be stopped at this point. I am starting to think that the answer is that there is no such short-cut.2013-12-10