Still a bug with factorize

[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.

[mlee]

fixed with 15434

[gorzel]

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

[mlee]

fixed with 15445

[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

[mlee]

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

[gorzel]

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.

[gorzel]

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

[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 .

[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 %

[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.

[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.)