5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Have you tried to compute $S(f,g)$ for univariate polynomials $f,g$? If yes, then what you get? $\endgroup$ – user26857 Sep 4 '15 at 19:43
  • $\begingroup$ 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? $\endgroup$ – darij grinberg Sep 4 '15 at 19:58
  • $\begingroup$ @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. $\endgroup$ – Herman Jaramillo Sep 4 '15 at 23:10
  • $\begingroup$ @darijgrinberg Yes , it is deterministic. It the same in the Wikipedia website above. Here again: en.wikipedia.org/wiki/Buchberger's_algorithm $\endgroup$ – Herman Jaramillo Sep 4 '15 at 23:13
  • 3
    $\begingroup$ 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.) $\endgroup$ – user26857 Sep 4 '15 at 23:19
4
$\begingroup$

Thanks to @user26857, for his great hint.

Assume \begin{equation} 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 , \end{equation} 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 \begin{equation} r_1 = f - \frac{\text{LT}(f)}{{\text{LT}(g)}} g . \end{equation} 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.

$\endgroup$
  • $\begingroup$ The proper way to thank user26857 for his hint is to upvote his comment. $\endgroup$ – Sergio Parreiras Sep 5 '15 at 16:25
  • $\begingroup$ @SergioParreiras how do I "upvote" a comment? Thanks. $\endgroup$ – Herman Jaramillo Sep 28 '15 at 21:59
  • $\begingroup$ place the cursor at the beginning of the comment (left side), you should see a triangle and then the words "this comment adds something useful to the post", click on the triangle. $\endgroup$ – Sergio Parreiras Sep 28 '15 at 22:22

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.