# How is Buchberger algorithm a generalization of the Euclid GCD algorithm?

It is said in many places (for example, on the Wikipedia article for Buchberger's algorithm) that Buchberger's algorithm to find Groebner basis is a generalization of Euclid's GCD algorithm.

This is not obvious to me. Just think about two polynomials $f(x)=a_n x^n + \cdots a_0$, and $g(x)=b_m x^m + \cdots b_0$, with $n>m$. Start by finding the subtraction polynomial $S(f,g)$, here I do not see a clue of Euclid's algoritm and what does it have to do with Euclid's GCD algorithm.

Please do not respond that both Euclid and Buchberger produce the same result. I already know that. I am questioning about how one algorithm (Buchberger's) reduce to the other (Euclid's) for univariate polynomials.

Any clue?

Thanks.

• Have you tried to compute $S(f,g)$ for univariate polynomials $f,g$? If yes, then what you get? – user26857 Sep 4 '15 at 19:43
• Is (your version of) Buchberger's algorithm deterministic? Does it tell you how to perform divisions, and what two polynomials to pick for computing the S-polynomial? – darij grinberg Sep 4 '15 at 19:58
• @user26857 Yes. $s(f,g)=\frac{x^n}{a_n x^n} f(x) - \frac{x^n}{b_m x^m} g(x)$. A complicated polynomial which in no way help me understand Euclid division. – Herman Jaramillo Sep 4 '15 at 23:10
• @darijgrinberg Yes , it is deterministic. It the same in the Wikipedia website above. Here again: en.wikipedia.org/wiki/Buchberger's_algorithm – Herman Jaramillo Sep 4 '15 at 23:13
• Your $S$-poly is not complicated at all! It does exactly what you do when start a division between two polynomials with coefficients in a field. (You could try an example.) – user26857 Sep 4 '15 at 23:19

Assume $$f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 , \quad g(x) = b_m x^m + b_{n-1} x^{n-1} + \cdots + b_0 ,$$ and $n \ge m$, $a_n \ne 0 \ne b_m$. We have $\text{LM}(f)=x^n$ and $\text{LM}(g)=x^m$. We call $L= \text{LCM}[ \, \text{LM}(f), \text{LM}(g)] = x^{n}$. Then by definition \begin{eqnarray} S(f,g) &=& \frac{L}{\text{LT}(f)} f - \frac{L}{\text{LT}(g)} g \\ &=& \frac{x^n}{a_n x^n} f - \frac{x^n}{b_m x^m} g \\ &=& \frac{1}{a_n} \left ( f - \frac{ a_n x_n}{b_m x^m}g \right) \\ &=& \frac{1}{a_n} \left (f - \frac{\text{LT}(f)}{\text{LT}(g)} g \right ) \end{eqnarray} On the other hand the first step on the Euclidean algorithm is the division of $f$ by $g$. This step is achieved by finding the remainder $$r_1 = f - \frac{\text{LT}(f)}{{\text{LT}(g)}} g .$$ Setting the $1/a_n$ aside (up to a multiplication by scalar any non-zero multiple of the GCD$(f,g)$ is also Gr\"{o}bner basis member) we have that $S(f,g)=r_1$. If $\text{deg}(r_1) < \text{deg}(f)$ we are done with this remainder, otherwise we keep reducing it until $\text{deg}(r_1) < \text{deg}(f)$.
The Buchberger algorithm starts with $G=\{f, g \}$, and then, if $r_1 \ne 0$, add (append) $r$ to $G$. That is $G = \{f, g , r_1 \}$. The next step is to reduce $r_1$ with respect to $G$. Since $\text{deg}(r_1) < \text{deg}(f)$, we only need to reduce $r$ with respect to $g$. That is, we divide $r$ by $g$, and keep doing this until $r_n=0$. (We do not prove here that the algorithm finishes. It does. That is not the purpose of this exercise). Then $G=\{f, r_1, \dots, r_{n-1} \}$. We find that $\text{GCD}(f,g)=r_{n-1}$, and it is found as if we were doing Euclid's algorithm instead of Buchberger's algorithm.
That $G$ can be reduced to $G=\{r_{n-1} \}= \{ \text{GCD}(f,g)\}$ is another story.