Ask Your Question

Patrick Reichert's profile - activity

2018-02-07 17:11:41 -0600 received badge  Nice Question (source)
2018-02-07 16:32:54 -0600 received badge  Scholar (source)
2018-02-07 16:32:16 -0600 commented answer Bug report: Kernel dies after 1 hour while dividing polynomials

Thank you very much for the given approach, that helps me a lot, because I still have some calculations of this kind ahead of me.

To round off this example, I would like to briefly complete the background to this question:

i2 is the general form of an elliptic curve with 17-torsion point P = (0,0) and base point O.

i1 describes the relationship between the parameters e and f and is usually referred as X_1(17).

poly1 and poly2 are meremorphic functions on the elliptic curve with the divisors

div (poly1) = 4[P] + 2[4P] +[-4P] +[-8P] +[-8P] - 8[O]

and

div (poly2) =[4P] +[-4P] - 2[O]

Thus, the quotient has the divisor

div (poly1/poly2) = 4[P] +[4P] +[-8P] - 6[O]

and can therefore be represented as a denomination-free polynomial, since the base point O is the only pole.

2018-02-05 14:57:18 -0600 received badge  Student (source)
2018-02-05 02:07:50 -0600 received badge  Editor (source)
2018-02-02 15:28:10 -0600 answered a question Bug report: Kernel dies after 1 hour while dividing polynomials

I repeat my posting since many multiplication signs are not shown in the original post:

SAGE source code:

Q.< E,F,X,Y > = QQ['E', 'F', 'X', 'Y'];

i1 = F^4+(E^3+E^2-E+2) * F^3+(E^3-3 * E+1) * F^2-(E^4+2 * E) * F+E^3+E^2;

i2 = Y^2+(E^3+E^2 * (3 * F+2)-E * (F^2-2 * F-1)-F * (F^2+3 * F+1)) * X * Y+(F * (E+1) * (E-F) * (E+F+1)^2 * (E^2+E-F) * (E^2+E * F+E-F^2-F)) * Y-X^3-(F * (E+1) * (E-F) * (E+F+1) * (E^2+E-F)) * X^2;

J = Q.ideal(i1, i2);

R.< e,f,x,y > = QuotientRing(Q, J);

poly1 = x^4+(-e^2 * f^4+e^4 * f+2 * e^3 * f^2-e * f^4-2 * e * f^3+2 * f^4+2 * e^2 * f-6 * e * f^2+f^3+5 * e^2-5 * e * f+11 * f^2-17 * e+18 * f+16) * x^3+(-2 * e^3-2 * e^2 * f+e * f^2+f^3-3 * e^2+2 * f^2-e+f) * x^2 * y+(-6 * e^2 * f^5+11 * e * f^6-3 * f^7+3 * e^6-6 * e^5 * f+17 * e^4 * f^2-69 * e^2 * f^4+5 * e * f^5+17 * f^6-5 * e^5+26 * e^4 * f+83 * e^3 * f^2-106 * e^2 * f^3-104 * e * f^4+71 * f^5-28 * e^4+66 * e^3 * f+57 * e^2 * f^2-149 * e * f^3+54 * f^4-55 * e^3+78 * e^2 * f+9 * e * f^2-32 * f^3-35 * e^2+70 * e * f-35 * f^2) * x^2+(-e^2 * f^7-e^7 * f-3 * e^6 * f^2-2 * e^2 * f^6-e * f^7-5 * e^6 * f-e^5 * f^2-6 * e^2 * f^5-6 * e * f^6+2 * f^7+3 * e^5 * f-2 * e^4 * f^2-2 * e^2 * f^4-15 * e * f^5+2 * f^6-2 * e^5-7 * e^4 * f-4 * e^3 * f^2-9 * e^2 * f^3-4 * e * f^4+3 * e^4+20 * e^3 * f-43 * e^2 * f^2-21 * e * f^3+28 * f^4-e^3-32 * e^2 * f-61 * e * f^2+61 * f^3-22 * e^2-53 * e * f+59 * f^2-16 * e+16 * f) * x * y+(e^6+2 * e^5 * f+3 * e^5-4 * e^3 * f^2-2 * e^2 * f^3+2 * e * f^4+f^5+3 * e^4-5 * e^2 * f^2+2 * f^4+3 * e^3-3 * e^2 * f-e * f^2+4 * f^3-3 * e^2+e * f-9 * f^2+17 * e-18 * f-16) * y^2+(11 * e * f^9-3 * f^10-3 * e^9-5 * e^7 * f^2-101 * e^2 * f^7+30 * e * f^8+11 * f^9-e^8-32 * e^7 * f-74 * e^6 * f^2-422 * e^2 * f^6-117 * e * f^7+121 * f^8+35 * e^7-39 * e^6 * f-134 * e^5 * f^2-486 * e^2 * f^5-660 * e * f^6+276 * f^7+141 * e^6-106 * e^5 * f-226 * e^4 * f^2+384 * e^2 * f^4-1019 * e * f^5+36 * f^6+189 * e^5-367 * e^4 * f-681 * e^3 * f^2+1382 * e^2 * f^3+130 * e * f^4-884 * f^5+61 * e^4-1019 * e^3 * f+565 * e^2 * f^2+1914 * e * f^3-1521 * f^4-251 * e^3-499 * e^2 * f+1751 * e * f^2-1001 * f^3-231 * e^2+462 * e * f-231 * f^2) * y;

poly2 = x+e^5 * f+e^4 * f^2-e^2 * f^4+2 * e^4 * f+e^3 * f^2-3 * e^2 * f^3+f^5+3 * e^3 * f-3 * e^2 * f^2-3 * e * f^3+3 * f^4+e^3+e^2 * f-5 * e * f^2+3 * f^3+e^2-2 * e * f+f^2;

print (poly1 / poly2);

Singular source code:

ring R = 0,(x,y,e,f),dp;

poly i1 = f^4+(e^3+e^2-e+2) * f^3+(e^3-3 * e+1) * f^2-(e^4+2 * e) * f+e^3+e^2;

poly i2 = y^2 + (e^3 + e^2 * (3 * f+2) - e * (f^2-2 * f-1) - f * (f^2+3 * f+1)) * x * y + (f * (e+1) * (e-f) * (e+f+1)^2 * (e^2+e-f) * (e^2+e * f+e-f^2-f)) * y - x^3 - (f * (e+ 1) * (e-f) * (e+f+1) * (e^2+e-f)) * x^2;

ideal I = i1,i2;

ideal J = std(I);

reduce((x^4 + (-e^2 * f^4 + e^4 * f + 2 * e^3 * f^2 - e * f^4 - 2 * e * f^3 + 2 * f^4 + 2 * e^2 *
f - 6 * e * f^2 + f^3 + 5 * e^2 - 5 * e * f + 11 * f^2 - 17 * e + 18 * f + 16) * x^3 + (-2 * e^3 - 2 * e^2 * f + e * f^2 + f^3 - 3 * e^2 + 2 * f^2 - e + f) * x^2 * y + (-6 * e^2 * f^5 + 11 * e * f^6 - 3 * f^7 + 3 * e^6 - 6 * e^5 * f + 17 * e^4 * f^2 - 69 * e^2 * f^4 + 5 * e * f^5 + 17 * f^6 - 5 * e^5 + 26 * e^4 * f + 83 * e^3 * f^2 - 106 * e^2 * f^3 - 104 * e * f^4 + 71 * f^5 - 28 * e^4 + 66 * e^3 * f + 57 *
e^2 * f^2 - 149 * e * f^3 + 54 * f^4 - 55 * e^3 + 78 * e^2 * f + 9 * e * f^2 - 32 * f^3 - 35 * e^2 + 7 0 * e * f - 35 * f^2) * x^2 + (-e^2 * f^7 - e^7 * f - 3 * e^6 * f^2 - 2 * e^2 * f^6 - e * f^7 - 5 * e^6 *
f - e^5 * f^2 - 6 * e^2 * f^5 - 6 * e * f^6 + 2 * f^7 + 3 * e^5 * f - 2 * e^4 * f^2 - 2 * e^2 * f^4 - 15 * e * f^5 + 2 * f^6 - 2 * e^5 - 7 * e^4 * f - 4 * e^3 * f^2 - 9 * e^2 * f^3 - 4 * e * f^4 + 3 * e^4 + 20 *
e^3 * f - 43 * e^2 * f^2 - 21 * e * f^3 + 28 * f^4 - e^3 - 32 * e^2 * f - 61 * e * f^2 + 61 * f^3 - 22 * e^2 - 53 * e * f + 59 * f^2 - 16 * e + 16 * f) * x * y + (e^6 + 2 * e^5 * f + 3 * e^5 - 4 * e^3 * f^2 - 2 * e^2 * f^3 + 2 * e * f^4 + f^5 + 3 * e^4 - 5 * e^2 * f^2 + 2 * f^4 + 3 * e^3 - 3 * e^2 * f - e * f^2 + 4 * f^3 - 3 * e^2 + e * f - 9 * f^2 + 17 * e - 18 * f - 16) * y^2 + (11 * e * f^9 - 3 * f^10 - 3 *
e^9 - 5 * e^7 * f^2 - 101 * e^2 * f^7 + 30 * e * f^8 + 11 * f^9 - e^8 - 32 * e^7 * f - 74 * e^6 * f^2
- 422 * e^2 * f^6 - 117 * e * f^7 + 121 * f^8 + 35 * e^7 - 39 * e^6 * f - 134 * e^5 * f^2 - 486 * e^2 *
f^5 - 660 * e * f^6 + 276 * f^7 + 141 * e^6 - 106 * e^5 * f - 226 * e^4 * f^2 + 384 * e^2 * f^4 - 10 19 * e * f^5 + 36 * f^6 + 189 * e^5 - 367 * e^4 * f - 681 * e^3 * f^2 + 1382 * e^2 * f^3 + 130 * e * f^4 - 884 * f^5 + 61 * e^4 - 1019 * e^3 * f + 565 * e^2 * f^2 + 1914 * e * f^3 - 1521 * f^4 - 251 * e^3 - 499 * e^2 * f + 1751 * e * f^2 - 1001 * f^3 - 231 * e^2 + 462 * e * f - 231 * f^2) * y)/(x + e^5 *
f + e^4 * f^2 - e^2 * f^4 + 2 * e^4 * f + e^3 * f^2 - 3 * e^2 * f^3 + f^5 + 3 * e^3 * f - 3 * e^2 * f^ 2 - 3 * e * f^3 + 3 * f^4 + e^3 + e^2 * f - 5 * e * f^2 + 3 * f^3 + e^2 - 2 * e * f + f^2), J);

Singular output:

15yef9-3yf10+23ye9-33ye7f2-93ye2f7+27yef8+15yf9-3x2e7+62ye8+6x2e6f-82ye7f-12x2e5f2-3xye5f2-147ye6f2-6x2e2f5+3xye2f5+15x2ef6-366ye2f6-3x2f7-120yef7+120yf8-6x2e6+2xye6+8ye7+21x2e5f-3xye5f-67ye6f-12x2e4f2-3xye4f2-121ye5f2-57x2e2f4+6xye2f4-6x2ef5-3xyef5-405ye2f5+21x2f6-513yef6+225yf7-18x2e5-xye5+97ye6+93x2e4f-4xye4f-233ye5f+3x3e2f2+9x2e3f2-12xye3f2-82ye4f2-93x2e2f3-45xye2f3-81x2ef4+12xyef4+138ye2f4+54x2f5+12xyf5-816yef5+57yf6-3x3e3-36x2e4+21xye4+44ye5+3x3e2f+120x2e3f+41xye3f-120ye4f-3x3ef2-36x2e2f2-49xye2f2-3y2e2f2-215ye3f2-90x2ef3-30xyef3+648ye2f3+39x2f4+33xyf4-277yef4-483yf5+6x3e2-43x2e3-6xye3+3y2e3-455ye4-6x3ef+78x2e2f-66xye2f-3y2e2f-485ye3f+15x3f2-10xyef2+3y2ef2+641ye2f2-27x2f3+33xyf3+1130yef3-1152yf4-18x3e-16x2e2-64xye2-6y2e2-832ye3+3x3f+83x2ef-66xyef+6y2ef-352ye2f-39x2f2+86xyf2-15y2f2+1830yef2-1140yf3+30x3-37x2e-27xye+18y2e-658ye2+26x2f+26xyf-3y2f+780yef-443yf2+2x2+9xy-29y2-11ye-221yf-318y

2018-02-02 15:28:10 -0600 asked a question Bug report: Kernel dies after 1 hour while dividing polynomials

I want to submit an error report for SAGE 7.0 and 8.0:

The division of two polynomials in an ideal causes an kernel death after one hour of computation. Singular performs the calculation in about 10 seconds.

Sage source code:

Q.<E,F,X,Y> = QQ['E', 'F', 'X', 'Y'];

i1 = F^4+(E^3+E^2-E+2)*F^3+(E^3-3*E+1)*F^2-(E^4+2*E)*F+E^3+E^2;

i2 = Y^2+(E^3+E^2*(3*F+2)-E*(F^2-2*F-1)-F*(F^2+3*F+1))*X*Y+(F*(E+1)*(E-F)*(E+F+1)^2*(E^2+E-F)*(E^2+E*F+E-F^2-F))*Y-X^3-(F*(E+1)*(E-F)*(E+F+1)*(E^2+E-F))*X^2;

J = Q.ideal(i1, i2);

R.<e,f,x,y> = QuotientRing(Q, J);

poly1 = x^4+(-e^2*f^4+e^4*f+2*e^3*f^2-e*f^4-2*e*f^3+2*f^4+2*e^2*f-6*e*f^2+f^3+5*e^2-5*e*f+11*f^2-17*e+18*f+16)*x^3+(-2*e^3-2*e^2*f+e*f^2+f^3-3*e^2+2*f^2-e+f)*x^2*y+(-6*e^2*f^5+11*e*f^6-3*f^7+3*e^6-6*e^5*f+17*e^4*f^2-69*e^2*f^4+5*e*f^5+17*f^6-5*e^5+26*e^4*f+83*e^3*f^2-106*e^2*f^3-104*e*f^4+71*f^5-28*e^4+66*e^3*f+57*e^2*f^2-149*e*f^3+54*f^4-55*e^3+78*e^2*f+9*e*f^2-32*f^3-35*e^2+70*e*f-35*f^2)*x^2+(-e^2*f^7-e^7*f-3*e^6*f^2-2*e^2*f^6-e*f^7-5*e^6*f-e^5*f^2-6*e^2*f^5-6*e*f^6+2*f^7+3*e^5*f-2*e^4*f^2-2*e^2*f^4-15*e*f^5+2*f^6-2*e^5-7*e^4*f-4*e^3*f^2-9*e^2*f^3-4*e*f^4+3*e^4+20*e^3*f-43*e^2*f^2-21*e*f^3+28*f^4-e^3-32*e^2*f-61*e*f^2+61*f^3-22*e^2-53*e*f+59*f^2-16*e+16*f)*x*y+(e^6+2*e^5*f+3*e^5-4*e^3*f^2-2*e^2*f^3+2*e*f^4+f^5+3*e^4-5*e^2*f^2+2*f^4+3*e^3-3*e^2*f-e*f^2+4*f^3-3*e^2+e*f-9*f^2+17*e-18*f-16)*y^2+(11*e*f^9-3*f^10-3*e^9-5*e^7*f^2-101*e^2*f^7+30*e*f^8+11*f^9-e^8-32*e^7*f-74*e^6*f^2-422*e^2*f^6-117*e*f^7+121*f^8+35*e^7-39*e^6*f-134*e^5*f^2-486*e^2*f^5-660*e*f^6+276*f^7+141*e^6-106*e^5*f-226*e^4*f^2+384*e^2*f^4-1019*e*f^5+36*f^6+189*e^5-367*e^4*f-681*e^3*f^2+1382*e^2*f^3+130*e*f^4-884*f^5+61*e^4-1019*e^3*f+565*e^2*f^2+1914*e*f^3-1521*f^4-251*e^3-499*e^2*f+1751*e*f^2-1001*f^3-231*e^2+462*e*f-231*f^2)*y;

poly2 = x+e^5*f+e^4*f^2-e^2*f^4+2*e^4*f+e^3*f^2-3*e^2*f^3+f^5+3*e^3*f-3*e^2*f^2-3*e*f^3+3*f^4+e^3+e^2*f-5*e*f^2+3*f^3+e^2-2*e*f+f^2;

print (poly1 / poly2);

Singular source code:

In Singular you cannot use the operator "/" to divide polynomials, since "non divisible terms" will be discarded and set to zero, see manual https://www.singular.uni-kl.de/Manual/4-0-3/sing_150.htm#SEC189.

So in Singular we have to use the "lift" command to calculate the quotient "poly 1 / poly2":

ring R = 0,(x,y,e,f),dp;

poly i1 = f^4+(e^3+e^2-e+2)*f^3+(e^3-3*e+1)*f^2-(e^4+2*e)*f+e^3+e^2;

poly i2 = y^2 + (e^3 + e^2*(3*f+2) - e*(f^2-2*f-1) - f*(f^2+3*f+1))*x*y + (f * (e+1) * (e-f) * (e+f+1)^2 * (e^2+e-f) * (e^2+e*f+e-f^2-f)) * y - x^3 - (f * (e+ 1) * (e-f) * (e+f+1) * (e^2+e-f)) * x^2;

ideal I = i1,i2; 

ideal J = std(I);

poly poly1 = x^4 + (-e^2*f^4 + e^4*f + 2*e^3*f^2 - e*f^4 - 2*e*f^3 + 2*f^4 + 2*e^2* 
f - 6*e*f^2 + f^3 + 5*e^2 - 5*e*f + 11*f^2 - 17*e + 18*f + 16)*x^3 + (-2*e^3 - 2 
*e^2*f + e*f^2 + f^3 - 3*e^2 + 2*f^2 - e + f)*x^2*y + (-6*e^2*f^5 + 11*e*f^6 - 3 
*f^7 + 3*e^6 - 6*e^5*f + 17*e^4*f^2 - 69*e^2*f^4 + 5*e*f^5 + 17*f^6 - 5*e^5 + 26 
*e^4*f + 83*e^3*f^2 - 106*e^2*f^3 - 104*e*f^4 + 71*f^5 - 28*e^4 + 66*e^3*f + 57* 
e^2*f^2 - 149*e*f^3 + 54*f^4 - 55*e^3 + 78*e^2*f + 9*e*f^2 - 32*f^3 - 35*e^2 + 7 
0*e*f - 35*f^2)*x^2 + (-e^2*f^7 - e^7*f - 3*e^6*f^2 - 2*e^2*f^6 - e*f^7 - 5*e^6* 
f - e^5*f^2 - 6*e^2*f^5 - 6*e*f^6 + 2*f^7 + 3*e^5*f - 2*e^4*f^2 - 2*e^2*f^4 - 15 
*e*f^5 + 2*f^6 - 2*e^5 - 7*e^4*f - 4*e^3*f^2 - 9*e^2*f^3 - 4*e*f^4 + 3*e^4 + 20* 
e^3*f - 43*e^2*f^2 - 21*e*f^3 + 28*f^4 - e^3 - 32*e^2*f - 61*e*f^2 + 61*f^3 - 22 
*e^2 - 53*e*f + 59*f^2 - 16*e + 16*f)*x*y + (e^6 + 2*e^5*f + 3*e^5 - 4*e^3*f^2 - 
 2*e^2*f^3 + 2*e*f^4 + f^5 + 3*e^4 - 5*e^2*f^2 + 2*f^4 + 3*e^3 - 3*e^2*f - e*f^2 
 + 4*f^3 - 3*e^2 + e*f - 9*f^2 + 17*e - 18*f - 16)*y^2 + (11*e*f^9 - 3*f^10 - 3* 
e^9 - 5*e^7*f^2 - 101*e^2*f^7 + 30*e*f^8 + 11*f^9 - e^8 - 32*e^7*f - 74*e^6*f^2  
- 422*e^2*f^6 - 117*e*f^7 + 121*f^8 + 35*e^7 - 39*e^6*f - 134*e^5*f^2 - 486*e^2* 
f^5 - 660*e*f^6 + 276*f^7 + 141*e^6 - 106*e^5*f - 226*e^4*f^2 + 384*e^2*f^4 - 10 
19*e*f^5 + 36*f^6 + 189*e^5 - 367*e^4*f - 681*e^3*f^2 + 1382*e^2*f^3 + 130*e*f^4 
 - 884*f^5 + 61*e^4 - 1019*e^3*f + 565*e^2*f^2 + 1914*e*f^3 - 1521*f^4 - 251*e^3 
 - 499*e^2*f + 1751*e*f^2 - 1001*f^3 - 231*e^2 + 462*e*f - 231*f^2)*y;

poly poly2 = x + e^5*f + e^4*f^2 - e^2*f^4 + 2*e^4*f + e^3*f^2 - 3*e^2*f^3 + f^5 
+ 3*e^3*f - 3*e^2*f^2 - 3*e*f^3 + 3*f^4 + e^3 + e^2*f - 5*e*f^2 + 3*f^3 + e^2 - 2*e*f 
+ f^2;

poly t1 = lift(poly2,poly1)[1,1];

Singular output:

t1;

-ye9+5ye7f2-5ye8+7ye7f+15ye6f2+4ye2f6-2yef7+x2e6-10ye7-2x2e5f+14ye6f-x2e4f2+20ye5f2+26ye2f5+yef6-5yf7+3x2e5-11ye6-7x2e4f+22ye5f+3ye4f2+4x2e2f3-2x2ef4+49ye2f4+43yef5-22yf6+3x2e4+4ye5-12x2e3f-7ye4f+10x2e2f2-27ye3f2+4x2ef3+10ye2f3-5x2f4+91yef4-18yf5-x2e3+xye3+29ye4-5x2e2f+7xye2f+11ye3f+13x2ef2-2xyef2-99ye2f2-7x2f3-2xyf3-4yef3+63yf4-2x2e2+3xye2+73ye3+4x2ef+6xyef-29ye2f-2x2f2-7xyf2-161yef2+117yf3-2x3+2xye+53ye2-2xyf-106yef+53yf2+3y2