Opened 3 years ago

Closed 6 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

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

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.

Last edited 6 months ago by saraedum (previous) (diff)

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]

Last edited 3 years ago by saraedum (previous) (diff)

comment:4 Changed 3 years ago by zimmerma

  • Cc wbhart added

comment:5 Changed 16 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 11 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 10 months ago by jpflori

  • Cc jpflori added

comment:8 Changed 8 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 8 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:10 Changed 6 months ago by saraedum

  • Authors set to Julian Rueth
  • 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 6 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 6 months ago by saraedum

  • Commit set to bf9f6a725bafc1541077f29d77b92006148d5520
  • Keywords sd59 added

New commits:

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

comment:13 Changed 6 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:

e1c1976content() of integer polynomials equal for NTL and FLINT

comment:14 Changed 6 months ago by mmarco

  • Reviewers set to Miguel Marco
  • Status changed from needs_review to positive_review

comment:15 Changed 6 months ago by vbraun

  • Branch changed from u/saraedum/ticket/13053 to e1c197671f7cc60ce3865319b7043ce1175f38ff
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.