Newton polygons

[xcaruso]

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 attachment: trac_14826_newton_polygons.patch

Depends on #14987

Component: padics

Keywords: Newton polygons

Author: Xavier Caruso

Reviewer: Volker Braun

Merged: sage-5.12.beta3

Issue created by migration from https://trac.sagemath.org/ticket/14826

[vbraun]

comment:2

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

[xcaruso]

comment:3

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]

comment:4

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.

[xcaruso]

comment:5

Ok. Revised version posted...

[roed314]

comment:6

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)

[xcaruso]

comment:7

Thanks! It's fixed.