Help with computation in Gröbner Basis.

Question

The problem is to compute the Gröbner basis of the following ideal using Buchberger's algorithm.

Let $u=a+bx+cx^2+dx^3$, $v= a+by+cy^2+dy^3$, $w=a+bz+cz+dz^3 $.

The ideal is $I= \langle a+bx+cx^2+dx^3,a+by+cy^2+dy^3,a+bz+cz+dz^3 \rangle $ where the monomial ordering is $(a,b,c,d,x,y,z)$ lexicographic.

I did some code in Singular and found the result as ,

$I[1]=cx^2y-cx^2z-cxy^2+cxz^2+cy^2z-cyz^2+dx^3y-dx^3z-dxy^3+dxz^3+dy^3z-dyz^3$

$I[2]=by-bz+cy^2-cz^2+dy^3-dz^3$

$I[3]=bx-bz+cx^2-cz^2+dx^3-dz^3$

$I[4]=a+bz+cz^2+dz^3$.

I tried stepwise implementation of Buchberger algorithm to verify and understand the above result got from Singular.So using the buchberger's criterion I got the following result :

$S(u,v)=b(x-y)+c(x^2-y^2)+d(x^3-y^3)=p_1$.

I used reduce(S(u,v),I)=p_2 and found the remainder to be same as $b(x-y)+c(x^2-y^2)+d(x^3-y^3)=p_3$ which means that I will update this as my basis.

Similarly using reduce (S(v,w),I) and reduce(S(u,w),I) we get the same result .

So my basis becomes $\textit{I}= \langle a+bx+cx^2+dx^3,a+by+cy^2+dy^3,a+bz+cz+dz^3,b(x-y)+c(x^2-y^2)+d(x^3-y^3),by-bz+cy^2-cz^2+dy^3-dz^3 ,bx-bz+cx^2-cz^2+dx^3-dz^3\rangle $.

The problem arises when I calculate $S(u,p_1)=aby-acx^2+acy^2-adx^3+ady^3+b^2x^2+bcx^3+bdx^4$ then when I use reduce(S(u,p_1),I) I get,

$$ f=cdx^2y^3-cdx^2z^3-cdxy^4-cdxy^3z+cdxyz^3+cdxz^4+cdy^4z-cdyz^4-d^2x^4y^2-d^2x^4yz-d^2x^4z^2+2d^2x^3y^3+d^2x^3y^2z+d^2x^3yz^2-d^2x^3z^3+d^2xy^2z^3+d^2xyz^4+d^2xz^5-d^2y^6-d^2y^2z^4-d^2yz^5$$ update my basis again,

This is where I get a problem because when I do reduce(f,groebner(I)) I am still getting a non-zero polynomial which is not possible as $f \in I$.

Can someone check my last S-polynomial and help me with the computation of the Gröbner basis .I need to show the calculation steps.

My code in sage

from sage.rings.polynomial.toy_buchberger import spol

R.<a,b,c,d,x,y,z>=PolynomialRing(QQ,order="lex");

I = R.ideal([a+b*x+c*x^2+d*x^3,a+b*y+c*y^3+d*y^3,a+b*z+c*z^2+d*z^3,b*(x-y)+c*(x^2-y^2)+d*(x^3-y^3),b*(y-z)+c*(y^2-z^2)+d*(y^3-z^3)]);


g = spol(a+b*x+c*x^2+d*x^3,b*(x-y)+c*(x^2-y^2)+d*(x^3-y^3));

g.reduce(I);

f= spol(a+b*x+c*x^2+d*x^3,b*(y-z)+c*(y^2-z^2)+d*(y^3-z^3));

f.reduce(I);

Both the answers that I am getting is $0$. So I am getting the remainder $s_{0,4}$ to be as $0$ after reducing it and I don't update my basis.

The problem with this code is that whatever be the spol (say spol(3,4)) and then if I do spol(3,4).reduce(I) , I am getting a $0$ .However the remainder should be as computed by @autodavid in the answer.

Answer 1

$\require{cancel}$

I followed your computation and find out that my $S(u,p_1)$ is the same as yours, but $\text{reduce}(S(u,p_1),I_{[0..3]})$ is zero. Indeed $$S(u,p_1) = (b y - c x^{2} + c y^{2} - d x^{3} + d y^{3})(\underbrace{a + b x + c x^{2} + d x^{3}}_{I_{[0]}=u})\\ \phantom{S(u,p_1) = ==} +(b x + c x^{2} + d x^{3})(\underbrace{b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3}}_{I_{[3]}=p_1})$$

The followings are my computations, which didn't encounter the term $S(u,p_1)$.

My computations (with sagemath)

$I=[\underbrace{a + b x + c x^{2} + d x^{3}}_{I_{[0]}}, \underbrace{a + b y + c y^{2} + d y^{3}}_{I_{[1]}}, \underbrace{a + b z + c z^{2} + d z^{3}}_{I_{[2]}}]$.

Compute the s-polynomials of $I_{[i]}, I_{[j]}$

(i, j) = (0, 1)

$s_{ij} = b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3}$

$r = b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3}$

update basis = $$\left[a + b x + c x^{2} + d x^{3},\\ a + b y + c y^{2} + d y^{3},\\ a + b z + c z^{2} + d z^{3},\\ b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3}\right]$$

(i, j) = (0, 2)

$s_{ij} = b x - b z + c x^{2} - c z^{2} + d x^{3} - d z^{3}$

$r = b y - b z + c y^{2} - c z^{2} + d y^{3} - d z^{3}$

update basis = $$\left[a + b x + c x^{2} + d x^{3},\\ a + b y + c y^{2} + d y^{3},\\ a + b z + c z^{2} + d z^{3},\\ b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3},\\ b y - b z + c y^{2} - c z^{2} + d y^{3} - d z^{3}\right]$$

(i, j) = (1, 2),(0, 3),(1, 3),(2, 3),(0, 4),(1, 4),(2, 4)

skip

(i, j) = (3, 4)

$s_{ij} = b x z - b y^{2} + c x^{2} y - c x y^{2} + c x z^{2} - c y^{3} + d x^{3} y - d x y^{3} + d x z^{3} - d y^{4}$

$r = c x^{2} y - c x^{2} z - c x y^{2} + c x z^{2} + c y^{2} z - c y z^{2} + d x^{3} y - d x^{3} z - d x y^{3} + d x z^{3} + d y^{3} z - d y z^{3}$

update basis = $$\left[a + b x + c x^{2} + d x^{3},\\ a + b y + c y^{2} + d y^{3},\\ a + b z + c z^{2} + d z^{3},\\ b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3},\\ b y - b z + c y^{2} - c z^{2} + d y^{3} - d z^{3},\\ c x^{2} y - c x^{2} z - c x y^{2} + c x z^{2} + c y^{2} z - c y z^{2} + d x^{3} y - d x^{3} z - d x y^{3} + d x z^{3} + d y^{3} z - d y z^{3}\right]$$

(i, j) = (0, 5)(1, 5)(2, 5)

skip

(i, j) = (3, 5)

$s_{ij} = b c x^{2} z - b c x z^{2} - b c y^{2} z + b c y z^{2} - b d x^{3} y + b d x^{3} z + b d x y^{3} - b d x z^{3} - b d y^{3} z + b d y z^{3} + c^{2} x^{3} y - c^{2} x y^{3} + c d x^{4} y - c d x y^{4}$

$r = 0$

no adding

(i, j) = (4, 5)

skip

basis = $$\left[\cancel{a + b x + c x^{2} + d x^{3}},\\ \cancel{a + b y + c y^{2} + d y^{3}},\\ a + b z + c z^{2} + d z^{3},\\ b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3},\\ b y - b z + c y^{2} - c z^{2} + d y^{3} - d z^{3},\\ c x^{2} y - c x^{2} z - c x y^{2} + c x z^{2} + c y^{2} z - c y z^{2} + d x^{3} y - d x^{3} z - d x y^{3} + d x z^{3} + d y^{3} z - d y z^{3}\right]$$

Edit: Finding $\text{reduce (S(u,p_1), I_{[0..3]})}$

Let $f=S(u,p_1)=a b y - a c x^{2} + a c y^{2} - a d x^{3} + a d y^{3} + b^{2} x^{2} + b c x^{3} + b d x^{4}$.

substract $( a + b x + c x^{2} + d x^{3} )( b y )$ from f. f becomes $ -a c x^{2} + a c y^{2} - a d x^{3} + a d y^{3} + b^{2} x^{2} - b^{2} x y + b c x^{3} - b c x^{2} y + b d x^{4} - b d x^{3} y $

substract $( a + b x + c x^{2} + d x^{3} )( -c x^{2} )$ from f. f becomes $ a c y^{2} - a d x^{3} + a d y^{3} + b^{2} x^{2} - b^{2} x y + 2 b c x^{3} - b c x^{2} y + b d x^{4} - b d x^{3} y + c^{2} x^{4} + c d x^{5} $

substract $( a + b x + c x^{2} + d x^{3} )( c y^{2} )$ from f. f becomes $ -a d x^{3} + a d y^{3} + b^{2} x^{2} - b^{2} x y + 2 b c x^{3} - b c x^{2} y - b c x y^{2} + b d x^{4} - b d x^{3} y + c^{2} x^{4} - c^{2} x^{2} y^{2} + c d x^{5} - c d x^{3} y^{2} $

substract $( a + b x + c x^{2} + d x^{3} )( -d x^{3} )$ from f. f becomes $ a d y^{3} + b^{2} x^{2} - b^{2} x y + 2 b c x^{3} - b c x^{2} y - b c x y^{2} + 2 b d x^{4} - b d x^{3} y + c^{2} x^{4} - c^{2} x^{2} y^{2} + 2 c d x^{5} - c d x^{3} y^{2} + d^{2} x^{6} $

substract $( a + b x + c x^{2} + d x^{3} )( d y^{3} )$ from f. f becomes $ b^{2} x^{2} - b^{2} x y + 2 b c x^{3} - b c x^{2} y - b c x y^{2} + 2 b d x^{4} - b d x^{3} y - b d x y^{3} + c^{2} x^{4} - c^{2} x^{2} y^{2} + 2 c d x^{5} - c d x^{3} y^{2} - c d x^{2} y^{3} + d^{2} x^{6} - d^{2} x^{3} y^{3} $

substract $( b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3} )( b x )$ from f. f becomes $ b c x^{3} - b c x^{2} y + b d x^{4} - b d x^{3} y + c^{2} x^{4} - c^{2} x^{2} y^{2} + 2 c d x^{5} - c d x^{3} y^{2} - c d x^{2} y^{3} + d^{2} x^{6} - d^{2} x^{3} y^{3} $

substract $( b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3} )( c x^{2} )$ from f. f becomes $ b d x^{4} - b d x^{3} y + c d x^{5} - c d x^{3} y^{2} + d^{2} x^{6} - d^{2} x^{3} y^{3} $

substract $( b x - b y + c x^{2} - c y^{2} + d x^{3} - d y^{3} )( d x^{3} )$ from f. f becomes $ 0 $

Edit: Codes for reduction

def ltDiv(a, b):  # returns lt(a)/lt(b)
    ea = a.exponents()[0]
    eb = b.exponents()[0]
    v = a.parent().gens()
    result = 1
    for ((eea, eeb), ev) in zip(zip(ea, eb), v):
        result *= ev^(eea - eeb)
    return result*a.lc()/b.lc()
            
def divisionAlgorithm(f, Gens): # ie, reduce
    quotients = [0]*len(Gens)
    remainder = 0
    while f != 0:
        division_occurred = false
        for g in Gens:
            if division_occurred == false and g != 0 and f.lt() % g.lt() == 0:
                quotient = ltDiv(f.lt(),g.lt())
                f -= quotient*g
                quotients[Gens.index(g)] += quotient
                division_occurred = true
                print("substract (" + str(g) + ")(" + str(quotient) + ") from f. f becomes ")
                print(str(remainder+f))
        if division_occurred == false:
            remainder += f.lt()
            f -= f.lt()
    return quotients, remainder

This is essentially the same as the division algorithm in Ideals, Varieties, and Algorithms by Cox, Little, O'shea.