Opened 8 years ago

Closed 7 years ago

#12404 closed defect (fixed)

is_squarefree() incorrect over imperfect fields

Reported by: saraedum Owned by: malb
Priority: minor Milestone: sage-5.1
Component: commutative algebra Keywords: sd40.5
Cc: sydahmad Merged in: sage-5.1.beta3
Authors: Julian Rueth Reviewers: Paul Zimmermann, Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #9054,#13043, #12988, #10902 Stopgaps:

Description (last modified by jdemeyer)

The method is_squarefree() is incorrect for polynomials over function fields over finite fields:

sage: K.<x> = FunctionField(GF(3))
sage: R.<T> = K[]
sage: f=T^3-x
sage: f.factor(proof=False)
T^3 + 2*x
sage: f.is_squarefree()
False

Apply:

  1. trac_12404.patch
  2. trac_12404_warning.patch
  3. 12404_examples.patch

to the sage library.

Attachments (3)

trac_12404.patch (4.5 KB) - added by saraedum 7 years ago.
distinguish characteristic zero and nonzero
trac_12404_warning.patch (1.9 KB) - added by saraedum 7 years ago.
warning about inconsistency with squarefree_decomposition
12404_examples.patch (1002 bytes) - added by jdemeyer 7 years ago.

Download all attachments as: .zip

Change History (27)

comment:1 follow-up: Changed 8 years ago by saraedum

The method is_squarefree() returns self.derivative().gcd(self).degree() <= 0. In the example the derivative vanishes which leads to the incorrect behaviour.

As a quick workaround one can do:

True in [d>=2 for (f,d) in f.factor(proof=False)]

comment:2 in reply to: ↑ 1 Changed 8 years ago by saraedum

Replying to saraedum:

True in [d>=2 for (f,d) in f.factor(proof=False)]

This would be "is_not_squarefree()" of course.

comment:3 Changed 7 years ago by zimmerma

see also #12198.

Paul

comment:4 Changed 7 years ago by zimmerma

see also #12129.

Paul

comment:5 Changed 7 years ago by saraedum

Thanks for pointing these out. Since both are in the multivariate case, I don't think they're related.

comment:6 Changed 7 years ago by saraedum

  • Authors set to Julian Rueth
  • Dependencies changed from #9054 to #9054, #12404
  • Status changed from new to needs_review

The attached patch should fix the problem.

comment:7 Changed 7 years ago by saraedum

  • Dependencies changed from #9054, #12404 to #9054, #12988

comment:8 Changed 7 years ago by saraedum

  • Keywords sd40.5 added

comment:9 follow-up: Changed 7 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to needs_work
  • Work issues set to coherence with squarefree_decomposition, fix error

the documentation of is_squarefree says that f is not square-free if g^2 divides f where g is a non-unit. In particular 4*x is not considered square free by is_squarefree, but it is by squarefree_decomposition:

sage: R.<x> = ZZ[]
sage: f = 4*x
sage: f.is_squarefree()
False
sage: f.squarefree_decomposition()
(4) * x

Sage should be coherent in that matter. Personally I prefer not to decompose the coefficient content.

Moreover the following produces an error:

sage: R.<x> = ZZ[]
sage: f = 2*x^2
sage: f.is_squarefree()
...
AttributeError: 'int' object has no attribute 'is_zero'

Paul

comment:10 in reply to: ↑ 9 Changed 7 years ago by saraedum

Replying to zimmerma:

the documentation of is_squarefree says that f is not square-free if g^2 divides f where g is a non-unit. In particular 4*x is not considered square free by is_squarefree, but it is by squarefree_decomposition:

sage: R.<x> = ZZ[]
sage: f = 4*x
sage: f.is_squarefree()
False
sage: f.squarefree_decomposition()
(4) * x

Sage should be coherent in that matter. Personally I prefer not to decompose the coefficient content.

That is true. I also noted this inconsistency. To not break existing code, I'd rather add a warning section in the docstring. Generally I agree that having squarefree_decomposition() factor the content is not what one wants for most purposes.

Would you be ok with just adding a warning and an example showing this problem?

Moreover the following produces an error:

sage: R.<x> = ZZ[]
sage: f = 2*x^2
sage: f.is_squarefree()
...
AttributeError: 'int' object has no attribute 'is_zero'

This should not happen when applying the dependency #12988.

comment:11 Changed 7 years ago by saraedum

  • Status changed from needs_work to needs_info

comment:12 Changed 7 years ago by saraedum

I added a patch with such a warning. I still have to check how it renders in the docs.

comment:13 Changed 7 years ago by saraedum

  • Description modified (diff)
  • Status changed from needs_info to needs_review

I made a few docstring changes in the latest patch.

Changed 7 years ago by saraedum

distinguish characteristic zero and nonzero

comment:14 Changed 7 years ago by saraedum

Btw. I will add the respective warning for squarefree_decomposition() in #13008.

comment:15 follow-up: Changed 7 years ago by zimmerma

Julian, there is a typo in trac_12404_warning.patch: not to consider to content should read not to consider the content.

Would it break a lot of code if is_squarefree returns False for 4*x? Did you try?

Paul

Changed 7 years ago by saraedum

warning about inconsistency with squarefree_decomposition

comment:16 Changed 7 years ago by saraedum

Thanks, the typo should be fixed now.

No I haven't tried. I was actually thinking about external code using that method. If you insist we can change it. I don't have a very strong opinion about this. I just believe that inconsistency isn't bad as long as it's documented. IMHO breaking the interface is worse than documented inconsistency.

comment:17 in reply to: ↑ 15 Changed 7 years ago by jdemeyer

Replying to zimmerma:

Would it break a lot of code if is_squarefree returns False for 4*x?

Did you mean "if is_squarefree returns True for 4*x"?

comment:18 Changed 7 years ago by jdemeyer

  • Dependencies changed from #9054, #12988 to #9054, #12988, #10902

Changed 7 years ago by jdemeyer

comment:19 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Reviewers changed from Paul Zimmermann to Paul Zimmermann, Jeroen Demeyer

Positive review to the first two patches. Anybody else can review my patch?

comment:20 Changed 7 years ago by was

  • Status changed from needs_review to positive_review

jdmeyer -- I positively review your patch.

comment:21 Changed 7 years ago by jdemeyer

  • Report Upstream changed from Not yet reported upstream; Will do shortly. to N/A
  • Work issues coherence with squarefree_decomposition, fix error deleted

comment:22 Changed 7 years ago by jdemeyer

  • Milestone set to sage-5.1

comment:23 Changed 7 years ago by jdemeyer

  • Dependencies changed from #9054, #12988, #10902 to #9054,#13043, #12988, #10902

comment:24 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.