wrong sign in square-free decomposition of polynomials over ZZ

[saraedum]

The NTL wrapper for SquareFreeDecomp gets the sign wrong for some FLINT polynomials:

sage: R.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: f=-x^2
sage: f.squarefree_decomposition()
(-x)^2

It works correctly for NTL:

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f=-x^2
sage: f.squarefree_decomposition()
(-1) * x^2

CC: @zimmermann6 @sagetrac-spancratz @wbhart @jpflori

Component: factorization

Keywords: sd40.5 FLINT NTL ZZ sd59

Author: Julian Rueth

Branch/Commit: e1c1976

Reviewer: Miguel Marco

Issue created by migration from https://trac.sagemath.org/ticket/13053

[saraedum]

comment:1

I CCed you since you seemed to have some interest in square-free factorization related issues.

[saraedum]

comment:2

The problem is that the FLINT/NTL return a different content:

sage: R.<x> = PolynomialRing(ZZ,implementation="FLINT")
sage: (-x).content()
1
sage: R.<x> = PolynomialRing(ZZ,implementation="NTL")
sage: (-x).content()
-1

If the content should just be a generator of the ideal generated by the coefficients, then both are correct. Personally, I think that NTL's behaviour is more intuitive though.

[saraedum]

comment:3

Could we change this to return -1 like NTL does? (not sure if that would break too many doctests)

If not, is there some easy way to get the leading coefficient's sign in FLINT?

[CCed spancratz since he apparently wrote fmpz_poly_content]

[rwst]

comment:8

FWIW in Mathematica, FactorTermsList[-x^2, x] results in {-1, 1, x^2} (where the first is the content), despite the definition in
http://mathworld.wolfram.com/Content.html

"(1) The content of an integer polynomial P in Z[x], denoted cont(P), is the largest integer k>=1 such that P/k also has integer coefficients. (2) Gauss's lemma for contents states that if P and Q are two polynomials with integer coefficients, then cont(PQ)=cont(P)cont(Q) (Séroul 2000, p. 287)."

Note that while the Mathematica output violates (1) it still satisfies (2).

[saraedum]

Author: Julian Rueth

[saraedum]

comment:10

I pushed a branch which fixes this. Here are some timings. Without my changes

sage: R.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: f=(2*x^2 - 4*x^4 + 14*x^7)
sage: %timeit f.content()
1000000 loops, best of 3: 183 ns per loop
sage: %timeit x.content()
1000000 loops, best of 3: 165 ns per loop
sage: f=R(0)
sage: %timeit f.content()
1000000 loops, best of 3: 108 ns per loop

With my changes

sage: R.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: f=(2*x^2 - 4*x^4 + 14*x^7)
sage: %timeit f.content()
1000000 loops, best of 3: 194 ns per loop
sage: %timeit x.content()
1000000 loops, best of 3: 139 ns per loop
sage: f=R(0)
sage: %timeit f.content()
1000000 loops, best of 3: 165 ns per loop

[saraedum]

Branch: u/saraedum/ticket/13053

[saraedum]

Changed keywords from sd40.5 FLINT NTL ZZ to sd40.5 FLINT NTL ZZ sd59

[saraedum]

Commit: bf9f6a7

[saraedum]

New commits:

bf9f6a7

made the content() of integer polynomials equal for NTL and FLINT

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e1c1976

content() of integer polynomials equal for NTL and FLINT

[sagetrac-git]

Changed commit from bf9f6a7 to e1c1976

[miguelmarco]

Reviewer: Miguel Marco

[vbraun]

Changed branch from u/saraedum/ticket/13053 to e1c1976