Opened 4 years ago

Closed 4 years ago

#14826 closed enhancement (fixed)

Newton polygons

Reported by: caruso Owned by: roed
Priority: major Milestone: sage-5.12
Component: padics Keywords: Newton polygons
Cc: Merged in: sage-5.12.beta3
Authors: Xavier Caruso Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14987 Stopgaps:

Description (last modified by vbraun)

This patch implements basic functions on Newton polygons.

A small demo is available here: https://cethop.math.cnrs.fr:8443/home/pub/5/


Apply only trac_14826_newton_polygons.patch

Attachments (3)

18484.patch (3.1 KB) - added by jantuitman 4 years ago.
minor corrections
trac_14826_structure.patch (14.0 KB) - added by vbraun 4 years ago.
Initial patch
trac_14826_newton_polygons.patch (25.4 KB) - added by caruso 4 years ago.

Download all attachments as: .zip

Change History (32)

comment:1 Changed 4 years ago by caruso

  • Status changed from new to needs_review

comment:2 follow-up: Changed 4 years ago by vbraun

That is of course not the same Newton polygon as

sage: R.<x,y> = QQ[]
sage: (1+x+y).newton_polytope()
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices

There might be a better place that does not require another global name, maybe as method of local fields? At the very least the NewtonPolygon docstring should make an effort to disambiguate.

A less scary way than _normalize() to compute the hull is to use some of Sage's existing polyhedral computation facilities:

sage: hull = Polyhedron([(0,0), (1,1), (2,-1), (3,0)], rays=[(0,1)])
sage: hull.vertices()
(A vertex at (0, 0), A vertex at (3, 0), A vertex at (2, -1))

Docstrings frequently need INPUT / OUTPUT, see the sage developer manual

PEP 8 spacing, e.g.

    def __le__(self,other):    # no
    def __le__(self, other):   # yes
  • ParentNewtonPolygon.__repr__ should be _repr_
  • NewtonPolygon_lastslope._repr_ docstring has unused import

comment:3 in reply to: ↑ 2 Changed 4 years ago by caruso

Replying to vbraun:

There might be a better place that does not require another global name, maybe as method of local fields? At the very least the NewtonPolygon docstring should make an effort to disambiguate.

If there is some risk of confusion, the best is probably to remove the import of the constructor NewtonPolygon. Indeed, as you say, these Newton polygons are mainly used for polynomials or series over padics (see tickets #14828 and #14830) and the user is definitely supposed to write f.newton_polygon() if f is such a polynomial or a series and not to construct a Newton polygon by himself.

A less scary way than _normalize() to compute the hull is to use some of Sage's existing polyhedral computation facilities:

I wonder if it makes sense to derive the class NewtonPolygon (provided by this patch) from Polyhedron_QQ.

There are obviously similarities (Newton polygons are polyhedrons in Q2) but also differences (the sum of two Newton polygons are their convex hull, the product of two Newton polygons are their Minkowski sum).

What is your opinion?

Docstrings frequently need INPUT / OUTPUT, see the sage developer manual

PEP 8 spacing, e.g.

    def __le__(self,other):    # no
    def __le__(self, other):   # yes
  • ParentNewtonPolygon.__repr__ should be _repr_
  • NewtonPolygon_lastslope._repr_ docstring has unused import

Thanks. I will fix it.

comment:4 Changed 4 years ago by vbraun

If your aim is to construct newton polygons from polynomials over local fields anyways then I would just make it a method there.

Inheriting from Polyhedron would give you a lot of undesirable methods, so I would probably use composition over inheritance (than is, have a self._polyhedron attribute instead of superclass). Though at the end of the day both ways would work.

comment:5 Changed 4 years ago by caruso

Ok. Revised version posted...

comment:6 Changed 4 years ago by roed

  • Status changed from needs_review to needs_work

I like this implementation much more than redoing everything from scratch (as is done in #6084).

  • Not all functions have doctests or even documentation.
  • There are doctest failures (click on the yellow blob at the top of this page to see them)

comment:7 Changed 4 years ago by caruso

  • Status changed from needs_work to needs_review

Thanks! It's fixed.

comment:8 Changed 4 years ago by amy

The function last_slope on lines 230 - 241 doesn't have input and output blocks, or an example block.

comment:9 Changed 4 years ago by caruso

  • Authors set to Xavier Caruso

Fixed.

comment:10 Changed 4 years ago by jantuitman

nice and useful code!

after testing a bit myself I only found one possible issue:

self._lastslope has not necessarily been set when it is used on line 602 resulting in bug in plot()

sage:NP=NewtonPolygon([(0,0),(1,0)],last_slope=2)
sage:NP.plot()

there are also some unimportant typos like:

line 85: explicitly mentioned
line 90: greater than or equal to
line 272: is infinite
line 351: are the union of those
line 614: image of this

I hope this is useful, I'm currently at the SAGE days in Leiden and using this as practice

Last edited 4 years ago by jantuitman (previous) (diff)

Changed 4 years ago by jantuitman

minor corrections

comment:11 follow-up: Changed 4 years ago by vbraun

Try the @cached_method decorator instead of caching manually.

The docstrings should start with a short (ideally one-line) description

def vertices(self, copy=True): 
    """ 
    Return the vertices of the Newton polytope.

    INPUT: 
    ...

Are you going to add a method to polynomaials or is that going to be in a future ticket?

You should run the testsuite for parents and elements somewhere in your code (see http://www.sagemath.org/doc/reference/misc/sage/misc/sage_unittest.html#sage.misc.sage_unittest.TestSuite)

comment:12 in reply to: ↑ 11 Changed 4 years ago by caruso

  • Status changed from needs_review to needs_info

Replying to vbraun:

Are you going to add a method to polynomaials or is that going to be in a future ticket?

See ticket #14828

You should run the testsuite for parents and elements somewhere in your code

Hmm. In order to make this testsuite work, it seems that I need to put ParentNewtonPolygon? in a category and I don't know which one is appropriate. Do you have a suggestion?

comment:13 follow-up: Changed 4 years ago by vbraun

Is sage/categories/polyhedra.py appropriate? If not, skip the categories test.

comment:14 in reply to: ↑ 13 Changed 4 years ago by caruso

Replying to vbraun:

Is sage/categories/polyhedra.py appropriate?

I tried this. But the test fails because the elements (which are instances of NewtonPolygon_element) are not instances of PolyhedralSets and I do not really want to derive from this class.

If not, skip the categories test.

I can skip the category test, but it is also included in the elements tests. So, should I skip both?

comment:15 follow-up: Changed 4 years ago by vbraun

Since you are deriving from RingElement your category should probably be Rings. Does that work?

comment:16 in reply to: ↑ 15 Changed 4 years ago by caruso

Replying to vbraun:

Since you are deriving from RingElement your category should probably be Rings. Does that work?

It should. Nevertheless, I just realized that the set of Newton polygons is not a ring but just a semiring (there is no additive inverse). The category of semirings exists in sage (it seems that it is only used for the parent NN) but there is apparently no generic class for elements in semirings. So, I don't know what I am supposed to do:

  • should I implement a generic class for element in semirings (in sage.structure.elements)
  • can I derive my class from RingElement and raise an error in the _neg_ function?
  • something else...

comment:17 Changed 4 years ago by vbraun

There are two ways for your elements get an __add__ method: Either they inherit it from RingElement or your category is (a refinement of) AdditiveMagmas. If you don't want to have a ring (no __neg__ method) then you have to go the latter route. Just derive from Element and initialize your category to

        from sage.categories.all import Magmas, AdditiveMagmas
        category = (Magmas(), AdditiveMagmas())
        super(...).__init__(..., category=category)

This is roughly how the polyhedra work, except they define a new category as the join.

comment:18 Changed 4 years ago by caruso

Thanks!

I've tried to review my patch following your answer but I got a problem: it seems that the specials functions + and * are not catched correctly by the category framework (although it works for __add__ and __mul__). As far as I understand, the reason is that the method Element.__getattr__ is not called in these cases (and, as a consequence, the methods in category().element_class are not examined).

I don't know if it is supposed to be a bug; if it is, I can open a new ticket about it.

In the attached patch, I've implemented a dirty hack (cf. lines 195-198) to get around this problem and make additions and multiplications of Newton polygons work correctly.

comment:19 Changed 4 years ago by caruso

  • Dependencies set to #14987

Changed 4 years ago by vbraun

Initial patch

comment:20 Changed 4 years ago by vbraun

You must never use the bare element class (NewtonPolygon_class in your case). Always use parent.element_class

sage: from sage.combinat.newton_polygon import *
sage: NewtonPolygon_element
<class 'sage.combinat.newton_polygon.NewtonPolygon_element'>
sage: ParentNewtonPolygon().element_class
<class 'sage.combinat.newton_polygon.ParentNewtonPolygon_with_category.element_class'>

My patch fixes that, and _add_ is now called the way it is supposed to.

Various docstrings need to be formatted according to http://www.sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx

Also, you need to get to 100% coverage:

$ sage -coverage sage/combinat/newton_polygon.py 
------------------------------------------------------------------------
SCORE sage/combinat/newton_polygon.py: 82.6% (19 of 23)

Missing documentation:
     * line 656: def _an_element_(self)

Missing doctests:
     * line 488: def plot(self, **kwargs)
     * line 650: def _repr_(self)
     * line 659: def _element_constructor_(self, arg, sort_slopes=True, last_slope=Infinity)
------------------------------------------------------------------------

I would put the file in sage/geometry instead of sage/combinat.

comment:21 Changed 4 years ago by caruso

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

Thanks a lot for your message (and your patience).

I fold the two patches (yours and mine), moved the file in sage/geometry and completed doctests.

Last edited 4 years ago by caruso (previous) (diff)

comment:22 Changed 4 years ago by vbraun

Can you double-check the docstrings? I see a couple that aren't typeset correctly. E.g.

- polyhedron -- a polyhedron defining the Newton polygon        # no
- ``polyhedron`` -- a polyhedron defining the Newton polygon    # yes

- repetition -- a boolean (default: True)           # no
- ``repetition`` -- a boolean (default: ``True``)   # yes


Returns ``self`` dilated by `exp`    # no
Returns ``self`` dilated by ``exp``  # yes  

You can implement the comparison operators much easier via

def __cmp__(self, other):
    c = cmp(type(self), type(other))
    if c != 0:
        return c
    return cmp(self._polyhedron, other._polyhedron)

though doing it the hard way is also acceptable.

comment:23 Changed 4 years ago by vbraun

  • Description modified (diff)

comment:24 Changed 4 years ago by caruso

I've posted a revised patch.

Concerning comparison, I'm not sure I can use the __cmp__ construction because the natural order on Newton polygons is not total (and I've read that - I don't remember where presently - that __cmp__ is only used to implement total order). Am I wrong?


For the bot: apply trac_14826_newton_polygons.patch

Changed 4 years ago by caruso

comment:25 follow-up: Changed 4 years ago by vbraun

Comparison deviates slightly in Sage vs. Python, especially for equality testing. If you don't have a total order then sort() will have undefined behavior. But apart from that there is nothing wrong with it. The Element base class already implements __cmp__, so you can only override it but not get rid of it.

Did you upload the right patch? I get doctest failures in _test_prod

comment:26 in reply to: ↑ 25 Changed 4 years ago by caruso

Replying to vbraun:

Did you upload the right patch? I get doctest failures in _test_prod

The current patch works well on my computer. Did you apply #14987 (see Dependencies)?

comment:27 Changed 4 years ago by vbraun

  • Reviewers set to Volker Braun

Thanks, forgot about that. Patch looks good to me.

comment:28 Changed 4 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:29 Changed 4 years ago by jdemeyer

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