Opened 11 years ago
Closed 7 years ago
#6667 closed defect (fixed)
bug in newton_polygon() for p-adic polynomials
Reported by: | AlexGhitza | Owned by: | roed |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | padics | Keywords: | newton polygon |
Cc: | Merged in: | sage-5.12.rc0 | |
Authors: | Xavier Caruso | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14826 | Stopgaps: | #12701 |
Description (last modified by )
This is as simple as I can make it at the moment:
---------------------------------------------------------------------- | Sage Version 4.1.1.rc0, Release Date: 2009-07-29 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- ********************************************************************** * * * Warning: this is a prerelease version, and it may be unstable. * * * ********************************************************************** sage: K = Qp(2, prec=5) sage: P.<x> = K[] sage: f = P(x^4 + 2^3*x^3 + 2^13*x^2 + 2^21*x + 2^37) sage: f.newton_polygon() [(0, 37), (1, 21), (2, 13), (3, 3), (4, 0)]
This is wrong, as it's not convex (the point (2,13) should not be there). Indeed, note that the sequence of Newton slopes is not non-increasing:
sage: f.newton_slopes() [16, 8, 10, 3]
This should be [16, 9, 9, 3].
Attachments (4)
Change History (21)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
- Report Upstream set to N/A
This is fixed in the new p-adic polynomial code, which is in progress.
comment:3 Changed 9 years ago by
- Stopgaps set to #12701
comment:4 Changed 7 years ago by
Still there in 5.12.beta2
Changed 7 years ago by
comment:5 Changed 7 years ago by
- Status changed from new to needs_review
here is a quick patch that should fix the problem
I have not been careful concerning the precision of the coefficients
Needs review !
comment:6 Changed 7 years ago by
bot is happy, is there somebody out there for a review ?
comment:7 Changed 7 years ago by
- Dependencies set to #14826
Here is a patch taking in account precision issues (see discussion in ticket #14828).
For the bot: apply only trac_6667_caruso.patch
comment:8 Changed 7 years ago by
your patch does not apply on a clean 5.12.beta3
Changed 7 years ago by
comment:9 Changed 7 years ago by
Sorry. I was working with an older version of Sage. It should be fixed now.
Changed 7 years ago by
comment:10 follow-up: ↓ 11 Changed 7 years ago by
here is a review patch, with only minor changes to your code
in my opinion, it would be good to add examples for the two other raise statements.
comment:11 in reply to: ↑ 10 Changed 7 years ago by
Replying to chapoton:
here is a review patch, with only minor changes to your code
Thanks!
in my opinion, it would be good to add examples for the two other raise statements.
Actually, I believe that they can't occur but it seemed to be really safer to check them anyway. (I added a comment in the code to mention that.)
I also corrected another bug: the valuation of the coefficients are not the values in the list self._valadded
but these values augmented by self._valbase
(as far as I understand David's code). As a consequence, the computation was wrong when the gcd of all coefficients was not 1. I added a doctest to check this issue.
Apply only trac_6667_caruso_revised.patch (it includes your review).
Changed 7 years ago by
comment:12 Changed 7 years ago by
- Reviewers set to Frédéric Chapoton
comment:13 Changed 7 years ago by
apply only trac_6667_caruso_revised.patch
comment:14 Changed 7 years ago by
apply only trac_6667_caruso_revised.patch
comment:15 Changed 7 years ago by
- Milestone set to sage-5.12
- Status changed from needs_review to positive_review
ok, good to me. Positive review
comment:16 Changed 7 years ago by
- Description modified (diff)
comment:17 Changed 7 years ago by
- Merged in set to sage-5.12.rc0
- Resolution set to fixed
- Status changed from positive_review to closed
I'm probably not going to be able to take a look at this until August 20 or so. If someone else wants to fix it, feel free. :-)