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$
12
  • 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, 2015 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$ Sep 4, 2015 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$ Sep 4, 2015 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$ Sep 4, 2015 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, 2015 at 23:19

1 Answer 1

5
$\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$
3
  • $\begingroup$ The proper way to thank user26857 for his hint is to upvote his comment. $\endgroup$ Sep 5, 2015 at 16:25
  • $\begingroup$ @SergioParreiras how do I "upvote" a comment? Thanks. $\endgroup$ Sep 28, 2015 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$ Sep 28, 2015 at 22:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .