Opened 10 years ago

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

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].

Apply trac_6667_caruso_revised.patch

Attachments (4)

trac_6667.patch (4.0 KB) - added by chapoton 6 years ago.
trac_6667_caruso.patch (7.9 KB) - added by caruso 6 years ago.
trac_6667_review_patch_1.patch (6.3 KB) - added by chapoton 6 years ago.
trac_6667_caruso_revised.patch (9.7 KB) - added by caruso 6 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 10 years ago by roed

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. :-)

comment:2 Changed 10 years ago by roed

  • Report Upstream set to N/A

This is fixed in the new p-adic polynomial code, which is in progress.

comment:3 Changed 8 years ago by jen

  • Stopgaps set to #12701

comment:4 Changed 6 years ago by chapoton

Still there in 5.12.beta2

Changed 6 years ago by chapoton

comment:5 Changed 6 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • 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 6 years ago by chapoton

bot is happy, is there somebody out there for a review ?

comment:7 Changed 6 years ago by caruso

  • 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 6 years ago by chapoton

your patch does not apply on a clean 5.12.beta3

Changed 6 years ago by caruso

comment:9 Changed 6 years ago by caruso

Sorry. I was working with an older version of Sage. It should be fixed now.

Changed 6 years ago by chapoton

comment:10 follow-up: Changed 6 years ago by chapoton

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 6 years ago by caruso

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 6 years ago by caruso

comment:12 Changed 6 years ago by chapoton

  • Authors changed from Frédéric Chapoton to Xavier Caruso
  • Reviewers set to Frédéric Chapoton

comment:13 Changed 6 years ago by chapoton

apply only trac_6667_caruso_revised.patch

comment:14 Changed 6 years ago by chapoton

apply only trac_6667_caruso_revised.patch

comment:15 Changed 6 years ago by chapoton

  • Milestone set to sage-5.12
  • Status changed from needs_review to positive_review

ok, good to me. Positive review

comment:16 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:17 Changed 6 years ago by jdemeyer

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