Opened 6 years ago

Closed 6 years ago

# Newton polygons

Reported by: Owned by: caruso roed major sage-5.12 padics Newton polygons sage-5.12.beta3 Xavier Caruso Volker Braun N/A #14987

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

### comment:1 Changed 6 years ago by caruso

• Status changed from new to needs_review

### comment:2 follow-up: ↓ 3 Changed 6 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 6 years ago by caruso

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

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

Ok. Revised version posted...

### comment:6 Changed 6 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 6 years ago by caruso

• Status changed from needs_work to needs_review

Thanks! It's fixed.

### comment:8 Changed 6 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 6 years ago by caruso

• Authors set to Xavier Caruso

Fixed.

### comment:10 Changed 6 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 6 years ago by jantuitman (previous) (diff)

### Changed 6 years ago by jantuitman

minor corrections

### comment:11 follow-up: ↓ 12 Changed 6 years ago by vbraun

Try the `@cached_method` decorator instead of caching manually.

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

• Status changed from needs_review to needs_info

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: ↓ 14 Changed 6 years ago by vbraun

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

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

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: ↓ 16 Changed 6 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 6 years ago by caruso

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 6 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
super(...).__init__(..., category=category)
```

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

### comment:18 Changed 6 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 6 years ago by caruso

• Dependencies set to #14987

Initial patch

### comment:20 Changed 6 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 6 years ago by caruso

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

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

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

### comment:22 Changed 6 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 6 years ago by vbraun

• Description modified (diff)

### comment:24 Changed 6 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

### comment:25 follow-up: ↓ 26 Changed 6 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 6 years ago by caruso

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

• Reviewers set to Volker Braun

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

### comment:28 Changed 6 years ago by vbraun

• Status changed from needs_review to positive_review

### comment:29 Changed 6 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.