Opened 3 years ago
Closed 8 months ago
#13053 closed defect (fixed)
wrong sign in square-free decomposition of polynomials over ZZ
Reported by: | saraedum | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 3 years ago by saraedum
- Cc zimmerma added
comment:2 Changed 3 years ago by saraedum
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 3 years ago by saraedum
- 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 3 years ago by zimmerma
- Cc wbhart added
comment:5 Changed 19 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:6 Changed 13 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:7 Changed 13 months ago by jpflori
- Cc jpflori added
comment:8 Changed 11 months ago by rws
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 10 months ago by vbraun_spam
- Milestone changed from sage-6.2 to sage-6.3
comment:10 Changed 8 months ago by saraedum
- 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 8 months ago by saraedum
- Branch set to u/saraedum/ticket/13053
- Created changed from 05/28/12 18:06:49 to 05/28/12 18:06:49
- Modified changed from 06/24/14 21:23:47 to 06/24/14 21:23:47
comment:12 Changed 8 months ago by saraedum
- Commit set to bf9f6a725bafc1541077f29d77b92006148d5520
- Keywords sd59 added
New commits:
bf9f6a7 | made the content() of integer polynomials equal for NTL and FLINT |
comment:13 Changed 8 months ago by git
- 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 8 months ago by mmarco
- Reviewers set to Miguel Marco
- Status changed from needs_review to positive_review
comment:15 Changed 8 months ago by vbraun
- 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 square-free factorization related issues.