Newton polygons

[caruso]

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​

[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

[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 Q²) 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.

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

[caruso]

Ok. Revised version posted...

[roed]

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)

[caruso]

Thanks! It's fixed.

[amy]

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

[caruso]

Fixed.

[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

[jantuitman]

minor corrections

[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)

[caruso]

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?

[vbraun]

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

[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?

[vbraun]

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

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

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

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

[vbraun]

Initial patch

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

[caruso]

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.

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

[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​

[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

[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)?

[vbraun]

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