Bug #1449: Bivariate factor bug: sometimes a factor is reducible - CoCoALib - CoCoA Project

Bug #1449

Bivariate factor bug: sometimes a factor is reducible

Added by John Abbott about 4 years ago. Updated almost 4 years ago.

Status:

Closed

Priority:

Urgent

Assignee:

John Abbott

Category:

Maths Bugs

Target version:

CoCoALib-0.99710

Start date:

20 Apr 2020

Due date:

% Done:

100%

Estimated time:

5.99 h

Spent time:

5.85 h

Description

The following code prints out some faulty (i.e. not irred) factorizations:

use QQ[x,y];

p1 := (x+y)*(500*y^8 +400*y^7*x +1283*y^6*x^2 +2620*y^5*x^3 +2474*y^4*x^4 +2620*y^3*x^5 +1283*y^2*x^6 +400*y*x^7 +500*x^8 -10800*y^6 -18144*y^5*x -29808*y^4*x^2 -44928*y^3*x^3 -29808*y^2*x^4 -18144*y*x^5 -10800*x^6 +85968*y^4 +177984*y^3*x +184032*y^2*x^2 +177984*y*x^3 +85968*x^4 -297216*y^2 -501120*y*x -297216*x^2 +373248);

for j := 1 to 100 do
facs := factor(p1);
  if len(facs.multiplicities) <> 3 then println [j,facs];  endif;
endfor;

Reported by Jasper Nalbach (from Aachen)

Related issues

History

#1 Updated by John Abbott about 4 years ago

I have simplified slightly the problem (from what Nalbach reported by email).

About 7% of calls gave a wrong result (after running a loop with 1000 iters).
Almost certainly an "unlucky random number" (but that should never happen...)

#2 Updated by John Abbott about 4 years ago

Status changed from New to In Progress
Assignee set to John Abbott
% Done changed from 0 to 10

Here is a simpler failing example:

p1 := (x+y)*(2*x^2 +x*y +2*y^2 -12)*(120*x^6 +250*y^6  +168*x*y  -104);

I'll try making it simpler still. If I set coeffs of x^6 and y^6 both to 1 then it seems to work fine...

#3 Updated by John Abbott about 4 years ago

Here is a simpler example:

p1 := (x+y)*(x^2 +y^2)*(2*x^6 +y^6 +2);

I have tried reducing the exponent 6 but without success (i.e. the factorization comes out right).

This is probably simple enough that I should now start the hard phase... 8-{

#4 Updated by John Abbott about 4 years ago

% Done changed from 10 to 20

The problem is in the univariate factorizer (ouch!)

use QQ[x,y];
jj := (x+41)*(x^2+41^2)*(2*x^6+41^6+2); // subst(p1,y,41);
factor(jj); --> only 2 factors!!

p1 := (x+y)*(x^2 +y^2)*(2*x^6 +y^6+2);
subst(p1,y,37); // or -37, also goes wrong
subst(p1,y,41); // or -41, also goes wrong

#5 Updated by Anna Maria Bigatti about 4 years ago

John Abbott wrote:

The problem is in the univariate factorizer (ouch!)

[...]

I confirm on my Mac: 2 factors :-(

#6 Updated by John Abbott about 4 years ago

% Done changed from 20 to 30

I have found a bug... not yet sure how to fix it. :-/
The crucial line is around DUPZfactor_combine.c:315; the value of max_tuple_size can be incorrectly set to THIS->nfactors/2.
We have modular factors of degs 1,1,1,6, and have just found a linear factor; so remaining modular factors have degs 1,1,6, and for some reason the code thinks the search does not need to consider 2-tuples... logic error!

Here is a simpler univariate problem poly:

f := (x+41)*(x^2+41^2)*(2*x^6+1608941);

#7 Updated by John Abbott about 4 years ago

% Done changed from 30 to 40

Here is an even simpler example:

f := (x+11)*(x^2+11^2)*(2*x^4+235885);

f := (x+11)*(x^2+1)*(2*x^4+235771); -- 2*x^7 +22*x^6 +2*x^5 +22*x^4 +235771*x^3 +2593481*x^2 +235771*x +2593481

And some even simpler examples:

flist := [(x+11)*(x^2+1)*(x^4+n) | n in [21458,21469,21470,21484,21496,21497]];

UPDATE I did a "quick" search for bad polys of the form (x+m)*(x^2+1)*(n1*x^3+n2) but found none (for m=11,..,20, n1=1,..,10 and n2=1,..,250000)