Opened 11 years ago

Closed 11 years ago

#462 closed bug (fixed)

Still a bug with factorize

Reported by: gorzel Owned by: somebody
Priority: major Milestone: 3-1-6 and higher
Component: dontKnow Version: 3-1-5
Keywords: Cc:

Description (last modified by gorzel)

Checked with the lastest 3-1-5 nightly build, there is still a problem with factorize:

> ring rw15 = (0,w),(x,y),dp;
> minpoly = w^2-w+4;

> poly f1 = 46082720409696000*x^7+(-46082720409696000*w)*x^6*y-92165440819392000*x^5*y^2+(46082720409696000*w-92165440819392000)*x^4*y^3+(46082720409696000*w+46082720409696000)*x^3*y^4+92165440819392000*x^2*y^5+(-46082720409696000*w+46082720409696000)*x*y^6-46082720409696000*y^7+(33201767234937600*w-30647785139942400)*x^5+(9771757580851200*w+100160515203724800)*x^4*y+(-44639165312524800*w+72399840258124800)*x^3*y^2+(-50857556500339200*w+8661330583027200)*x^2*y^3+(-9771757580851200*w-100160515203724800)*x*y^4+(33645938034067200*w-26095034448864000)*y^5+(-27845878235380000*w-122690040515260000)*x^4+(118340445370520000*w-78316910631160000)*x^3*y+(49599903465540000*w+143572936815180000)*x^2*y^2+(-68740541904980000*w+221889847446340000)*x*y^3+(-46553976962930000*w-92669364707510000)*y^4+(-10245093811971840*w-22646289009116160)*x^3+(13836455538428160*w-45510917399009280)*x^2*y+(23501184011055360*w-81074549479680)*x*y^2+(1628715454398720*w+33167517920305920)*y^3+(-39904964412744000*w+71294643532392000)*x^2+(-33810691604940000*w-61360144023780000)*x*y+(33142826091756000*w-83566672337148000)*y^2+(31945832606457089*w+80538751785644435)*x+(-60831105992681752*w+16100113835778104)*y+(6386463969822000*w+7137812672154000);

> poly f2 = 2294919476402860800*x^8+(2294919476402860800*w)*x^7*y+(2294919476402860800*w-4589838952805721600)*x^6*y^2-4589838952805721600*x^5*y^3-2294919476402860800*x^4*y^4-4589838952805721600*x^3*y^5+(-2294919476402860800*w-2294919476402860800)*x^2*y^6+(-2294919476402860800*w+2294919476402860800)*x*y^7+2294919476402860800*y^8+(2079252344885483520*w+199077352169886720)*x^6+(1664507861198219520*w-6691211003487859200)*x^5*y+(-940087496357798400*w-4357582041940853760)*x^4*y^2+(-132718234779924480*w-1360361906494225920)*x^3*y^3+(11059852898327040*w-5164951303518727680)*x^2*y^4+(-2615655210454344960*w-3058049326387426560)*x*y^5+(-1725337052139018240*w+3428554398481382400)*y^6+(-303374279659956000*w-5069995781923932000)*x^5+(-3770035487253912000*w-433219676416104000)*x^4*y+(-4550011664055924000*w+3596807869771812000)*x^3*y^2+(-2903294868999996000*w+8363429372035788000)*x^2*y^3+(-888281095906038000*w+7908367952545854000)*x*y^4+(2166700912923936000*w+2079936471472032000)*y^5+(423632341377847296*w-2525937150738157056)*x^4+(-1427080802231483136*w+208937943910563840)*x^3*y+(233775974997891072*w+1098882998754621696)*x^2*y^2+(909106583118508800*w-2643717921543353088)*x*y^3+(-1102041053136433152*w-662978218196823552)*y^4+(-2937940392496416000*w-2605343366930784000)*x^3+(-4025809830284004000*w+6326272590446292000)*x^2*y+(-2903294868999996000*w+8363429372035788000)*x*y^2+(1552119452639616000*w+5543283759427200000)*y^3+(-15951155173959635*w+2981235020448425687)*x^2+(1622440449955667768*w+1652892262372213288)*x*y+(1685231063399012416*w-2263997141199178816)*y^2+(-1166168320889497200*w+991554882467540400)*x+2294919476402860800*y+(941170437657378096*w+239157859721078160);

> if(size(factorize(f1*f2,1))<2) { "Bug with factorize";};
Bug with factorize
> division(f1*f2,f1)[1][1,1]==f2;  // yet
1

Back tracking to earlier versions e.g. 3-1-4 Singular also did not factorize.

Change History (13)

comment:1 Changed 11 years ago by mlee

Resolution: fixed
Status: newclosed

fixed with 15434

comment:2 Changed 11 years ago by gorzel

Description: modified (diff)
Resolution: fixed
Status: closedreopened

Here is another example where factorize does not work correctly, unaltered despite your latest fix:

> ring rw =(0,w),(x,y),dp;minpoly = w4-w3+2w2+w+1; 
> poly f = x15-y15-15*x13+15*y13+90*x11-90*y11-275*x9+275*y9+450*x7-450*y7-378*x5+378*y5+140*x3-140*y3-15*x+15*y;
> factorize(f);
[1]:
   _[1]=1
   _[2]=x-y
   _[3]=x2+(1/2w3+3/2)*xy+y2+(1/2w3-3/2)
   _[4]=x2+(-1/2w3-1/2)*xy+y2+(-1/2w3-7/2)
   _[5]=x2+xy+y2-3
   _[6]=x8-x7y+x5y3-x4y4+x3y5-xy7+y8-7*x6+4*x5y+3*x4y2-9*x3y3+3*x2y4+4*xy5-7*y6+14*x4+3*x3y-8*x2y2+3*xy3+14*y4-8*x2-8*xy-8*y2+1
[2]:
   1,1,1,1,1,1
> factorize(_[1][6]);  // But this is reducible!!
[1]:
   _[1]=1
   _[2]=x4+(1/2w3+1/2)*x3y+(-1/2w3-1/2)*x2y2+(1/2w3+1/2)*xy3+y4+(1/2w3-5/2)*x2+(-5/2w3-7/2)*xy+(1/2w3-5/2)*y2+(-1/2w3+1/2)
   _[3]=x4+(-1/2w3-3/2)*x3y+(1/2w3+3/2)*x2y2+(-1/2w3-3/2)*xy3+y4+(-1/2w3-9/2)*x2+(5/2w3+13/2)*xy+(-1/2w3-9/2)*y2+(1/2w3+5/2)
[2]:
   1,1,1
Last edited 11 years ago by gorzel (previous) (diff)

comment:3 Changed 11 years ago by mlee

Resolution: fixed
Status: reopenedclosed

fixed with 15445

comment:4 Changed 11 years ago by anonymous

Just for notification: The following bug has also gone away:

> ring ra11 = (0,a),(x,y),dp;
> minpoly = (1331a5-1331a4-5484322580a3-279218820639a2+4247309240411457a-1402706609307145691);
> poly F11 = x11-y11-11*x9+11*y9+44*x7-44*y7-77*x5+77*y5+55*x3-55*y3-11*x+11*y;
>  factorize (F11);
convertFacCF2NTLzz_pX: coefficient not immediate!, char=536300041

it now gives

[1]:
   _[1]=1
   _[2]=x-y
   _[3]=x2+(23861351480320871396437536/3555941291619449132439795402119947079a4+2308720746603927337762383479/3555941291619449132439795402119947079a3-83572375552814840574829353504768/3555941291619449132439795402119947079a2-30098631735440341391412583822199229/3555941291619449132439795402119947079a+37025313228575179485700296525884161128/3555941291619449132439795402119947079)*xy+y2+(20521806961427079037746577/3555941291619449132439795402119947079a4-10647469275139757833667715337/3555941291619449132439795402119947079a3-57531287778331120480082390876523/3555941291619449132439795402119947079a2+8177861685328503333952454386005122/3555941291619449132439795402119947079a+1380670094891985263615208035187416019/3555941291619449132439795402119947079)
   _[4]=x2+(-20521806961427079037746577/3555941291619449132439795402119947079a4+10647469275139757833667715337/3555941291619449132439795402119947079a3+57531287778331120480082390876523/3555941291619449132439795402119947079a2-8177861685328503333952454386005122/3555941291619449132439795402119947079a-8492552678130883528494798839427310177/3555941291619449132439795402119947079)*xy+y2+(-18387611948323442185368744/3555941291619449132439795402119947079a4-3340860258777304183289428224/3555941291619449132439795402119947079a3+66154788241129464190661517246912/3555941291619449132439795402119947079a2+21919012210843006290534984319222417/3555941291619449132439795402119947079a-38496582632396647662026559262563922174/3555941291619449132439795402119947079)
   _[5]=x2+(4382069856325522341261721/3555941291619449132439795402119947079a4+10190436453413217024043713792/3555941291619449132439795402119947079a3-20601768514030323541191311386180/3555941291619449132439795402119947079a2-29751993989608550084064951592359936/3555941291619449132439795402119947079a+14791025772214013503410987488469440018/3555941291619449132439795402119947079)*xy+y2+(-23861351480320871396437536/3555941291619449132439795402119947079a4-2308720746603927337762383479/3555941291619449132439795402119947079a3+83572375552814840574829353504768/3555941291619449132439795402119947079a2+30098631735440341391412583822199229/3555941291619449132439795402119947079a-44137195811814077750579887330124055286/3555941291619449132439795402119947079)
   _[6]=x2+(-26109226323542756885321424/3555941291619449132439795402119947079a4-26487486733934206378763240832/3555941291619449132439795402119947079a3+112797644529643507826599791261337/3555941291619449132439795402119947079a2+89947499621220401099964974119786704/3555941291619449132439795402119947079a-71152545080196609725323658231130371906/3555941291619449132439795402119947079)*xy+y2+(-4382069856325522341261721/3555941291619449132439795402119947079a4-10190436453413217024043713792/3555941291619449132439795402119947079a3+20601768514030323541191311386180/3555941291619449132439795402119947079a2+29751993989608550084064951592359936/3555941291619449132439795402119947079a-21902908355452911768290578292709334176/3555941291619449132439795402119947079)
   _[7]=x2+(18387611948323442185368744/3555941291619449132439795402119947079a4+3340860258777304183289428224/3555941291619449132439795402119947079a3-66154788241129464190661517246912/3555941291619449132439795402119947079a2-21919012210843006290534984319222417/3555941291619449132439795402119947079a+31384700049157749397146968458324028016/3555941291619449132439795402119947079)*xy+y2+(26109226323542756885321424/3555941291619449132439795402119947079a4+26487486733934206378763240832/3555941291619449132439795402119947079a3-112797644529643507826599791261337/3555941291619449132439795402119947079a2-89947499621220401099964974119786704/3555941291619449132439795402119947079a+64040662496957711460444067426890477748/3555941291619449132439795402119947079)
[2]:
   1,1,1,1,1,1,1

Note,the degree 5 algebraic extension is the same as the following with monic minpoly:

> ring ra11 = (0,a),(x,y),dp;
> minpoly =  a^5 - a^4 - 4*a^3 + 3*a^2 + 3*a - 1;
> poly F11 = x11-y11-11*x9+11*y9+44*x7-44*y7-77*x5+77*y5+55*x3-55*y3-11*x+11*y;
> factorize (F11);
[1]:
   _[1]=1
   _[2]=x-y
   _[3]=x2+(-a2+2)*xy+y2+(a4-4a2)
   _[4]=x2+(-a4+4a2-2)*xy+y2+(-a3+3a-2)
   _[5]=x2+(a4-a3-3a2+2a+1)*xy+y2+(-a-2)
   _[6]=x2+(a)*xy+y2+(a2-4)
   _[7]=x2+(a3-3a)*xy+y2+(-a4+a3+3a2-2a-3)
[2]:
   1,1,1,1,1,1,1
Last edited 11 years ago by gorzel (previous) (diff)

comment:5 Changed 11 years ago by anonymous

Resolution: fixed
Status: closedreopened

comment:6 Changed 11 years ago by mlee

I cannot reproduce your failures, neither with the current git master branch nor the nightly built.

comment:7 Changed 11 years ago by gorzel

Resolution: fixed
Status: reopenedclosed

You are right, these problems do no longer occur. In my previous (anonymous) comment I used an old version of Singular instead of the nightly-built, which caused the false alarm. (I was a bit distrait). So I have edited comment 4 accordingly.

Last edited 11 years ago by gorzel (previous) (diff)

comment:8 Changed 11 years ago by gorzel

Resolution: fixed
Status: closedreopened

I was wrong, there are still problems. Another product which is not factorized:

Singular for x86_64-Linux version 3-1-5 (3150)  Dec  9 2012 06:53:35
with
        factory(@(#) factoryVersion = 3.1.5),libfac(3.1.5,July 2012),
        GMP(5.0),NTL(5.5.2),64bit,static readline,Plural,fan/cone,DBM,

> ring r13b = (0,b),(x,y),dp; minpoly =  (b4-b3+2b2+4b+3);
> poly A = x^4+(-1/3*b^3+b^2-5/3*b-1)*x^3*y+(-1/3*b^3+1/3*b-2)*x^2*y^2+(2/3*b^3-b^2+4/3*b+1)*x*y^3+y^4+(29*b^3-51*b^2+88*b+63)*x^2+(9*b^3-9*b+99)*x*y+(-27*b^3+51*b^2-90*b-54)*y^2+(14*b^3-15*b^2+22*b+72)*x+(-3*b^3+15*b^2-33*b+36)*y+(-188*b^3+188*b-1860);
> poly B = x^9+(1/3*b^3-b^2+5/3*b+1)*x^8*y+(-1/3*b^3-2/3*b-1)*x^7*y^2+(1/3*b^3-b^2+2/3*b+1)*x^6*y^3+(-1/3*b^3-2/3*b-2)*x^5*y^4+(-b+1)*x^4*y^5+(1/3*b^3-b^2+2/3*b)*x^3*y^6+(-b)*x^2*y^7+(2/3*b^3-b^2+4/3*b+1)*x*y^8-y^9+(36*b^3-66*b^2+120*b+54)*x^7+(-29*b^3+33*b^2-37*b-177)*x^6*y+(6*b^3+9*b+33)*x^5*y^2+(-36*b^3+48*b^2-57*b-171)*x^4*y^3+(-11*b^3+48*b^2-82*b+78)*x^3*y^4+(-b^3+16*b-18)*x^2*y^5+(-4*b^3+33*b^2-62*b+111)*x*y^6+(38*b^3-66*b^2+118*b+102)*y^7+(77*b^3-102*b^2+160*b+318)*x^6+(48*b^3-147*b^2+294*b-165)*x^5*y+(-78*b^3+153*b^2-270*b-120)*x^4*y^2+(90*b^3-162*b^2+288*b+189)*x^3*y^3+(-89*b^3+153*b^2-259*b-228)*x^2*y^4+(115*b^3-147*b^2+227*b+507)*x*y^5+(36*b^3-102*b^2+201*b-81)*y^6+(-1177*b^3+1362*b^2-2000*b-5694)*x^5+(-384*b^3+1146*b^2-2334*b+1293)*x^4*y+(-711*b^3+750*b^2-1107*b-3684)*x^3*y^2+(-145*b^3+750*b^2-1673*b+1866)*x^2*y^3+(-904*b^3+1146*b^2-1814*b-4011)*x*y^4+(-336*b^3+1362*b^2-2841*b+2517)*y^5+(873*b^3-5823*b^2+12510*b-16362)*x^4+(-9912*b^3+17244*b^2-29832*b-23958)*x^3*y+(1719*b^3-3132*b^2+5463*b+3591)*x^2*y^2+(-9084*b^3+17244*b^2-30660*b-15786)*x*y^3+(5529*b^3-5823*b^2+7854*b+29745)*y^4+(5298*b^3+3186*b^2-12507*b+65970)*x^3+(492*b^3-9387*b^2+21342*b-35820)*x^2*y+(9915*b^3-9387*b^2+11919*b+57654)*x*y^2+(-8763*b^3+3186*b^2+1554*b-73179)*y^3+(-177372*b^3+315549*b^2-549198*b-399789)*x^2+(24816*b^3-45054*b^2+79026*b+51921)*x*y+(-170001*b^3+315549*b^2-556569*b-326781)*y^2+(-273648*b^3+279297*b^2-369627*b-1509480)*x+(-33876*b^3+279297*b^2-609399*b+866205)*y+(434277*b^3-788940*b^2+1382445*b+908361);
> if(size(factorize(A*B,1))<2) { "Bug with factorize";};
Bug with factorize

comment:9 Changed 11 years ago by gorzel

Note the following: One obtains a factorization if one modifies the content of the lower terms in the following way:

> ideal I = factorize(subst(A*B,x,3*x,y,3*y)/bigint(3)^13,1);
> subst(I[1],x,1/3*x,y,1/3*y)*3^4 == A;
1
> subst(I[2],x,1/3*x,y,1/3*y)*3^9 == B;
1

Seemingly, this only works with (or is better is due to ?) the integer 3 .

comment:10 Changed 11 years ago by gorzel

Here is one more example, in three variables, It shows in more detail the strange behavior of the content. In fact the variable T has only to be considered as a parameter.

ring rw13 = (0,w),(T,x,y),dp; 
minpoly = (w^4-w^3+2*w^2+4*w+3);

poly Hneu = 
x^13-y^13+(-65*w^3+117*w^2-208*w-156)*T*x^11+(65*w^3-91*w^2+143*w+234)*T*y^11+(-39*w^3+117*w^2-234*w+117)*T*x^10+(78*w^3-91*w^2+130*w+390)*T*y^10+(-689*w^3-2171*w^2+5746*w-16107)*T^2*x^9+(-16705/3*w^3+32435/3*w^2-58045/3*w-8788)*T^2*y^9+(-15210*w^3+21606*w^2-34476*w-57798)*T^2*x^8+(-16614*w^3+28002*w^2-47892*w-43992)*T^2*y^8+(-14547*w^3+26052*w^2-45435*w-32058)*T^2*x^7+(-15054*w^3+24882*w^2-42237*w-42120)*T^2*y^7+(308581*w^3-505388*w^2+854893*w+883038)*T^3*x^7+(47242*w^3-237302*w^2+499135*w-553488)*T^3*y^7+(452270*w^3-1191463*w^2+2291003*w-644709)*T^3*x^6+(582439*w^3-1362920*w^2+2555917*w-92508)*T^3*y^6+(-270816*w^3-229515*w^2+799266*w-3670641)*T^3*x^5+(883662*w^3-1973829*w^2+3661710*w+262431)*T^3*y^5+(-4396327/3*w^3+19510634/3*w^2-40530178/3*w+13462280)*T^4*x^5+(5640596*w^3-6386068*w^2+9065030*w+28409901)*T^4*y^5+(-830401*w^3+974207*w^2-1412983*w-4036071)*T^3*x^4+(760643*w^3-1689688*w^2+3130322*w+266370)*T^3*y^4+(20294378*w^3-26643448*w^2+41060318*w+86440380)*T^4*x^4+(5279066*w^3+3610412*w^2-13593424*w+67843698)*T^4*y^4+(34683727*w^3-58690697*w^2+100467835*w+91123968)*T^4*x^3+(6227858*w^3+7596407*w^2-23720320*w+94392402)*T^4*y^3+(-269815676/3*w^3+390512551/3*w^2-629448482/3*w-331043258)*T^5*x^3+(-94859661*w^3+166063209*w^2-287546493*w-225369144)*T^5*y^3+(31413330*w^3-69137640*w^2+127795122*w+13769730)*T^4*x^2+(2733874*w^3+19260358*w^2-47086208*w+109961202)*T^4*y^2+(-421494307/3*w^3+945300395/3*w^2-1755321490/3*w-36293842)*T^5*x^2+(-193843104*w^3+274995669*w^2-439410660*w-737414028)*T^5*y^2+(6677424*w^3-25392744*w^2+51796368*w-43097184)*T^4*x+(4253080*w^3+7591792*w^2-21735272*w+74806680)*T^4*y+(-52820170*w^3+190018127*w^2-384748741*w+294246537)*T^5*x+(-196474785*w^3+296309208*w^2-485858373*w-671785452)*T^5*y+(5248218976/27*w^3-12863190080/27*w^2+24372820576/27*w-1115453924/9)*T^6*x+(136336200*w^3-396591312*w^2+776924772*w-355580316)*T^6*y+(-153999872/3*w^3+341724448/3*w^2-632914880/3*w-18505760)*T^5+(196115972/3*w^3-887376100/3*w^2+1847311544/3*w-624999544)*T^6;


" 1. Case, unmodified: approximately 30 % wrong ";
int bugcnt;
for (int i=1;i<=100;i++) 
{
  i;
  if (size(factorize(Hneu,1))<2) { "failed";bugcnt++;}
}
if (bugcnt) { "Bug with factorize: ",bugcnt,"% wrong";} else { "OK"; }
// Bug with factorize:  34 % wrong

"2.Modified coefficients: large denominators: 0 % false";
int bugcnt;
for (int i=1;i<=100;i++) 
{ 
  i;
  if (size(factorize(subst(Hneu,x,3*x,y,3*y)/bigint(3)^13,1))<2) { "failed";bugcnt++;}
}
if (bugcnt) { "Bug with factorize: ",bugcnt,"% wrong";} else { "OK"; }
// OK

"3. Modified coefficients: denominatorfree 100 % wrong";
int bugcnt;
for (int i=1;i<=100;i++) 
{ 
  i;
  if (size(factorize(subst(Hneu,x,1/3*x,y,1/3*y)*bigint(3)^13,1))<2) { "failed";bugcnt++;}
}
if (bugcnt) { "Bug with factorize: ",bugcnt,"% wrong";} else { "OK"; }
// Bug with factorize:  100 % wrong

Further remarks:

1.) If one looks with 'top' on the memory consumption, then one notices that after the first

trials of factorize, the memory growth suddenly and then increases continously. (To see it clearly, iterate the for loop longer (or let it run on a machine with few memory.)

So one may ask: Is there a memory leak?

2.) Why is in case 1. the percentage rate of failure so randomly, meaning why does it

On my 32-bit Laptop I got a percentages within 25, 33, 34, 37. On a 64-bit machine (x86_64-Linux) the variation is narrow, all near 30 %

comment:11 Changed 11 years ago by mlee

I have fixed it with 15513, both the bug itself and the memory leak. The first case fails randomly since we substitute a random value for T. This substitution may or may not clear the 1/3.

comment:12 Changed 11 years ago by gorzel

It seems to be OK now. I will make some further test with this new version, then ticket can be closed.

Note that apart from the memory leak, the other bugs with factorization did not occur with this old version:

Singular for x86_64-Linux version 3-1-4 (3140- 14545 )  Jan 30 2012 06:26:35
with
        factory(@(#) factoryVersion = 3.1.3),libfac(3.1.3,March 2011),
        GMP(5.0),NTL(5.5.2),64bit,static readline,Plural,fan/cone,DBM,
        dynamic modules,OM_CHECK=0,OM_TRACK=0,random=1355502374
        CC= gcc -march=k8 -O3 -fomit-frame-pointer -DNDEBUG -DOM_NDEBUG -Dx86_64_Linux -DHAVE_CONFIG_H,
        CXX= g++ -march=k8 -O3 -fomit-frame-pointer --no-rtti -I.. -I/tmp/hannes -DNDEBUG -DOM_NDEBUG -Dx86_64_Linux -DHAVE_CONFIG_H (4.4.5)

(So my initial remark that Singular 3-1-4 also could not factorize was not quite correct.)

comment:13 Changed 11 years ago by boehm

Resolution: fixed
Status: reopenedclosed
Note: See TracTickets for help on using tickets.