# Buchberger's algorithm

I am trying to calculate a Gröbner basis for $I=\langle \mathcal{B}\rangle$, where $\mathcal{B}=\{f=x_3-x_1^5, g=x_2-x_1^3\}$, with respect both lexicographic and graded reverse lexicographic orders. I get how to calculate the $S$-polynomial but then I have to calculate the reminder on dividing $S(f,g)$ by $\mathcal{B}$ and I don't really know what do they mean by that or how to compute it.

P.D. I know I could use macaulay2 but I want to see the process with an example.

P.D.2. I could use any other step by step example.

• I still don't understand what do they mean by dividing $S(f,g)$ by $\mathcal{B}$. I am reading Introduction to algebraic geometry by Hassett, and I can't find how to compute that. – Smurf Sep 16 '15 at 15:17
• I'm confused, then you get two division which means two reminders? – Smurf Sep 16 '15 at 15:23
• Yes sorry, I answered before seeing that. It says tho that division algorithm doesn't tell you, sometimes, when a polynomial belongs to a certain ideal. How can I prove that it doesn't then? – Smurf Sep 16 '15 at 15:26
• Alright I think I was thinking it wrong. The gröbner basis doesn't have to be "minimal" so isn't necessary to know whether every $S$-polynomial belongs to $I$ or not, right? – Smurf Sep 16 '15 at 15:34

I understood your misunderstanding by reading comments. No, there is no two division "$S(f,g)$ to $f$ and $S(f,g)$ to $g$"! There is division algorithm for dividing one polynomial to several polynomial at the same time. From your question, it seems you know monomial ordering or at least those two ones you mentioned. So You can read section 3 of chapter 2 of the book Ideals, Varieties and Algorithms written by David Cox et al. which is an easy books to read, if you didn't know about monomial ordering then read section 2 of chapter 2 before it.

I checked book of Hassett that you mentioned in comments of your question, there is does mentioned what is division to several polynomials at the same time on pages 13-14.

In your example above, $f=x_3-x_1^5,g=x_2-x_1^3$,

With lexicographic order and $x_1>x_2>x_3$ we have $LT(f)=-x_1^5,LT(g)=-x_1^3$. So $S(f,g)=\frac{x_1^5}{-x_1^5}(x_3-x_1^5)-\frac{x_1^5}{-x_1^3}(x_2-x_1^3)=x_1^2x_2-x_3$ Now for dividing $x_1^2x_2-x_3$ with $\{x_3-x_1^5,x_2-x_1^3\}$ we look if leading terms of any of divisors divides leading term of $S(f,g)$ or not. none of $-x_1^5$ and $-x_1^3$ divide $x_1^2x_2$ so the division algorithm stops at the beginning and the remainder is $x_1^2x_2-x_3$. So we add it to our set and we continue computing S-polynomials for the new set $\{x_3-x_1^5,x_2-x_1^3,x_1^2x_2-x_3\}$.

As in our previous step the division was trivial let's compute next step too. Rename our three polynomials with $f_1,f_2=g,f_3=S(f,g)$. Now we construct $S(f_1,f_3)$. $$S(f_1,f_3)=\frac{x_1^5x_2}{-x_1^5}(x_3-x_1^5)-\frac{x_1^5x_2}{x_1^2x_2}(x_1^2x_2-x_3)=x_1^3x_3-x_3$$ Now dividing $x_1^3x_3-x_3$ with $\{x_3-x_1^5,x_2-x_1^3,x_1^2x_2-x_3\}$.

$LT(f_2)=-x_1^3$ divides $LT(x_1^3x_3-x_3)=x_1^3x_3$, then $(x_1^3x_3-x_3)-x_3f_2=x_3x_2-x_3$ And now $LT(x_3x_2-x_3)=x_2x_3$ not dividable with leading terms of $f_1,f_2,f_3$. So $x_3x_2-x_3$ is remainder of this division.

And so on...

I strongly recommend you to use softwares for computing Grobner basis, and if you want results of steps for small examples and exercises, step by step, you can write a small piece of code (also in Maple as I did too) then computer shows you all computations.