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\}$ .