Opened 10 years ago

Closed 10 years ago

# Still a bug with factorize

Reported by: Owned by: gorzel somebody major 3-1-6 and higher dontKnow 3-1-5

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.

### comment:1 Changed 10 years ago by mlee

Resolution: → fixed new → closed

fixed with 15434

### comment:2 Changed 10 years ago by gorzel

Description: modified (diff) fixed closed → reopened

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 10 years ago by gorzel (previous) (diff)

### comment:3 Changed 10 years ago by mlee

Resolution: → fixed reopened → closed

fixed with 15445

### comment:4 Changed 10 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 10 years ago by gorzel (previous) (diff)

### comment:5 Changed 10 years ago by anonymous

Resolution: fixed closed → reopened

### comment:6 Changed 10 years ago by mlee

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

### comment:7 Changed 10 years ago by gorzel

Resolution: → fixed reopened → closed

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 10 years ago by gorzel (previous) (diff)

### comment:8 Changed 10 years ago by gorzel

Resolution: fixed closed → reopened

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),

```
```> 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 10 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 10 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 10 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 10 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),