Opened 5 years ago
Closed 3 years ago
#13053 closed defect (fixed)
wrong sign in squarefree decomposition of polynomials over ZZ
Reported by:  saraedum  Owned by:  tbd 

Priority:  major  Milestone:  sage6.3 
Component:  factorization  Keywords:  sd40.5 FLINT NTL ZZ sd59 
Cc:  zimmerma, spancratz, wbhart, jpflori  Merged in:  
Authors:  Julian Rueth  Reviewers:  Miguel Marco 
Report Upstream:  N/A  Work issues:  
Branch:  e1c1976 (Commits)  Commit:  e1c197671f7cc60ce3865319b7043ce1175f38ff 
Dependencies:  Stopgaps: 
Description
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
Change History (15)
comment:1 Changed 5 years ago by
 Cc zimmerma added
comment:2 Changed 5 years ago by
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.
comment:3 Changed 5 years ago by
 Cc spancratz added
 Status changed from new to needs_info
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]
comment:4 Changed 5 years ago by
 Cc wbhart added
comment:5 Changed 4 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:6 Changed 4 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:7 Changed 4 years ago by
 Cc jpflori added
comment:8 Changed 4 years ago by
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).
comment:9 Changed 4 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:10 Changed 3 years ago by
 Status changed from needs_info to needs_review
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
comment:11 Changed 3 years ago by
 Branch set to u/saraedum/ticket/13053
 Created changed from 05/29/12 01:06:49 to 05/29/12 01:06:49
 Modified changed from 06/25/14 04:23:47 to 06/25/14 04:23:47
comment:12 Changed 3 years ago by
 Commit set to bf9f6a725bafc1541077f29d77b92006148d5520
 Keywords sd59 added
New commits:
bf9f6a7  made the content() of integer polynomials equal for NTL and FLINT

comment:13 Changed 3 years ago by
 Commit changed from bf9f6a725bafc1541077f29d77b92006148d5520 to e1c197671f7cc60ce3865319b7043ce1175f38ff
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

comment:14 Changed 3 years ago by
 Reviewers set to Miguel Marco
 Status changed from needs_review to positive_review
comment:15 Changed 3 years ago by
 Branch changed from u/saraedum/ticket/13053 to e1c197671f7cc60ce3865319b7043ce1175f38ff
 Resolution set to fixed
 Status changed from positive_review to closed
I CCed you since you seemed to have some interest in squarefree factorization related issues.