# A variation of Buchberger algorithm

Let $I$ be an ideal of a polynomial ring $R$. Fix a monomial order. Denote the $S$-polynomial of $f, g\in R$ by $S(f, g)$ and denote the gcd of their leading terms by $T(f, g)$.

Consider the following variation of the Buchberger algorithm

• Input: A set of polynomials $F$ that generates the ideal $I$
• Output: A Gröbner basis $G$ for $I$

1. $G :=F$
2. For every $f_i$, $f_j$ in $G$, if $T(f_i, f_j)\neq 1$, add $S(f_i, f_j)$ to $G$.
3. Repeat 2. until for every $f_i, f_j$ in $G$ we have $T(f_i, f_j)=1$ or $S(f_i, f_j)\in G$.

It can be shown (using a variant of Buchberger criterion) that if this algorithm terminates then $G$ is a Gröbner basis for $I$.

My question is: is it true that the algorithm always terminates?

• what does it do with $F = \{x^3 ; x^2+1\}$ ? $T(f_1,f_2) = 1$ so nothing happens on step 2 ? – mercio Dec 9 '15 at 15:18
• @mercio: With the lex order, $T(x^3, x^2+1)=x^2$. – user72870 Dec 9 '15 at 16:12
• Do you have an example of the algorithm not terminating when you omit the $T(f_1,f_2)=1$ condition ? – Ewan Delanoy Dec 11 '15 at 6:59

The answer is no. (Even if $F$ is already a Gröbner basis, the algorithm does not terminate.)
Consider the lexicographic order ($x > y$) and the polynomials $$f= x^2 - y^2, \quad g_1= xy - y^2$$
The set $F=\{f,g_0\}$ is a Gröbner basis. Applying the algorithm inductively to $g_i= xy^{i+1}-y^{i+2}$ and $f$ gives:
$$T(g_0,f) = \gcd(x^2,xy) = x \neq 1 \implies \textrm{add new polynomial: } g_1 = S(g_0,f) =xy^2 - y^3$$ $$T(g_2,f) = \gcd(x^2,xy^2) = x \neq 1 \implies \textrm{add new polynomial: } g_2 = S(g_1,f) =xy^3 - y^4$$ $$\vdots$$