# Computable Criteria to check whether a given basis is a Gröbner Basis

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?

-
I believe the answer you are looking for is in these lecture notes by Victor Adamchik. I could be incorrect, however, my experiences with Gröbner Bases is mostly computational. –  process91 Sep 2 '12 at 15:06

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).