Buchburger's algorithm

The following algorithm was given by Buchburger in his 1965 PhD thesis (as a student of Gröbner at the Univ. of Innsbruck, Austria). Our discussion follows Buchburger [Bu] and Nakos-Glinos [NG].

Input: A finite set $F$ of polynomials generating an ideal $I$ in $R[x_1,...,x_n]$.

Output: A Gröbner basis for $I$.

Let

$$P:=\{\ \{f,g\}\ \vert\ f,g\in F,\ f\not= g\}.$$

(a)

Pick a pair $\{f,g\}$ in $P$.

(b)

Let $P=P-\{f,g\}$. Compute $NF(S(f,g),F)$.

(c)

If $NF(S(f,g),F)=0$ and if $P$ is non-empty then go to (a). If $NF(S(f,g),F)=0$ and there are no more elements in $P$ then stop and output $F$. If $NF(S(f,g),F)\not= 0$, let $F=F\cup \{$NF(S(f,g),F)$\}$.

(d)

Go to (a).

Example 2.8.12   Let $<$ be the graded lexicographic ordering on $\mathbb{Q}[x,y]$. Let $f_1(x,y)=xy-2x$, $f_2(x,y)=x^2-y$, $G=\{f_1,f_2\}$. We have $S(f_1,f_2)=y^2-2x^2$ and $y^2-2x^2 \stackrel{G}{\rightarrow}y^2-2y$, so $NF(S(f_1,f_2))=y^2-2y$. Let $f_3(x,y)=y^2-2y$ and $G=\{f_1,f_2,f_3\}$. We have $S(f_1,f_2)=0$, so $G$ is not increased. We have $S(f_1,f_3) \stackrel{G}{\rightarrow}0$, so, again, no more is to be added to $G$. The Gröbner basis for the ideal $I=(f_1,f_2)\subset \mathbb{Q}[x,y]$ is $G=\{f_1,f_2,f_3\}$.