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?

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

This does not terminate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.