Fwd: Multivariate Polynomial Factoring is Broken

[David Harvey]

Begin forwarded message:

From: Genya Zaytman <gzay...@math.harvard.edu>

Date: March 31, 2008 1:15:21 PM EDT

To: David Harvey <dmha...@math.harvard.edu>

Subject: Fwd: Multivariate Polynomial Factoring is Broken

Begin forwarded message:

From: Genya Zaytman <gzay...@math.harvard.edu>

Date: March 31, 2008 1:14:39 PM EDT

Subject: Multivariate Polynomial Factoring is Broken

sage: version()

'SAGE Version sage-2.11, Release Date: 2008-03-30'

sage: q = 1073741789

sage: T.<aa, bb> = PolynomialRing(GF(q))

sage: f = aa^2 + 12124343*bb*aa + 32434598*bb^2; f

aa^2 + 12124343*aa*bb + 32434598*bb^2

sage: f.factor()

(32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2)

sage: g = (32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2); g

aa^2 - 49344938*aa*bb + 32434598*bb^2

sage: f == g

False

So basically, in the example above, we factor a homogeneous degree 2 polynomial in two variables, multiply it back out and get a different answer.

david

[mabshoff]

On Mar 31, 7:30 pm, David Harvey <dmhar...@math.harvard.edu> wrote:
> Begin forwarded message:
>
>
>
> > From: Genya Zaytman <gzayt...@math.harvard.edu>
> > Date: March 31, 2008 1:15:21 PM EDT
> > To: David Harvey <dmhar...@math.harvard.edu>
> > Subject: Fwd: Multivariate Polynomial Factoring is Broken
>
> > Begin forwarded message:

> >> From: Genya Zaytman <gzayt...@math.harvard.edu>

> >> Date: March 31, 2008 1:14:39 PM EDT
> >> Subject: Multivariate Polynomial Factoring is Broken
>
> >> sage: version()
> >> 'SAGE Version sage-2.11, Release Date: 2008-03-30'
> >> sage: q = 1073741789
> >> sage: T.<aa, bb> = PolynomialRing(GF(q))
> >> sage: f = aa^2 + 12124343*bb*aa + 32434598*bb^2; f
> >> aa^2 + 12124343*aa*bb + 32434598*bb^2
> >> sage: f.factor()
> >> (32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2)
> >> sage: g = (32434598) * (16373350*aa^2 + 437239695*aa*bb + bb^2); g
> >> aa^2 - 49344938*aa*bb + 32434598*bb^2
> >> sage: f == g
> >> False
>
> So basically, in the example above, we factor a homogeneous degree 2  
> polynomial in two variables, multiply it back out and get a different  
> answer.

Sigh. I guess it is time for another email to the Singular people:

mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.0.alpha0$ ./sage -
singular
SINGULAR /
Development
A Computer Algebra System for Polynomial Computations / version
3-0-4
0<
by: G.-M. Greuel, G. Pfister, H. Schoenemann \ Nov 2007
FB Mathematik der Universitaet, D-67653 Kaiserslautern \
> ring r =1073741789,(aa,bb),lp;
> poly f = aa^2 + 12124343*bb*aa + 32434598*bb^2;
> f;
aa^2+12124343*aa*bb+32434598*bb^2
> factorize(f);
[1]:
_[1]=32434598
_[2]=16373350*aa^2+437239695*aa*bb+bb^2
[2]:
1,1
> poly g=32434598*(16373350*aa^2+437239695*aa*bb+bb^2);
> f-g;
61469281*aa*bb
> Auf Wiedersehen.

> david

Cheers,

Michael