Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Division algorithm in a polynomial ring with variable coefficients

I am working on an algorithm to divide a polynomial f by a list of polynomials [g1, g2, ..., gm]. The following is my algorithm:

def div(f,g): # Division algorithm on Page 11 of Using AG by Cox;
# f is the dividend;
# g is a list of ordered divisors;
# The output consists of a list of coefficients for g and the remainder;
# p is the intermediate dividend;
n = len(g)
p, r, q = f, 0,  [0 for x in range(0,n)]
while p != 0:
    i, divisionoccured = 0, False
    while i < n and divisionoccured == False:
        if g[i].lt().divides(
            q[i] = q[i] +[i].lt()
            p = p - ([i].lt())*g[i]
            divisionoccured = True
            i = i + 1
    if divisionoccured == False:
        r = r +
        p = p -
return q, r

Here is an example of implementing the algorithm:

K.<a,b> = FractionField(PolynomialRing(QQ,'a, b'))
P.<x,y,z> = PolynomialRing(K,order='lex')

Here is the result:

(a*x^2*y^3 + x*y + 2*b, 0, [0, 0])
(((-2)/a)*x*y^3 + x*y + 2*b, 0, [1/a*x*y^3, 0])
(x*y + 4/a^3*y^3 + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3, 0])
(4/a^3*y^3 + ((-2)/a^2)*y + 2*b, 0, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(((-2)/a^2)*y + 2*b, 4/a^3*y^3, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
(2*b, 4/a^3*y^3 + ((-2)/a^2)*y, [1/a*x*y^3 + ((-2)/a^3)*y^3 + 1/a^2*y, 0])
Error in lines 6-6
Traceback (most recent call last):

and some other error messages.

We can see that it worked well until the leading term is 2b. it does not recognize the 2b as a term. I tried:


It gives the answer False. But I tried


It gives error message. Is there a way to solve this? Thank you for your help!