Coverage for local/lib/python2.7/site-packages/sage/geometry/newton_polygon.py : 92%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
""" Newton Polygons
This module implements finite Newton polygons and infinite Newton polygons having a finite number of slopes (and hence a last infinite slope). """
############################################################################# # Copyright (C) 2013 Xavier Caruso <xavier.caruso@normalesup.org> # # Distributed under the terms of the GNU General Public License (GPL) # # http://www.gnu.org/licenses/ #############################################################################
""" Class for infinite Newton polygons with last slope. """ """ Initialize a Newton polygon.
INPUT:
- polyhedron -- a polyhedron defining the Newton polygon
TESTS:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NewtonPolygon([ (0,0), (1,1), (3,5) ]) Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 5)
sage: NewtonPolygon([ (0,0), (1,1), (2,8), (3,5) ], last_slope=3) Infinite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 5) ending by an infinite line of slope 3
::
sage: TestSuite(NewtonPolygon).run() """
""" Return a string representation of this Newton polygon.
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,5) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 5)
sage: NP._repr_() 'Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 5)' """ else: else: else:
""" Returns the list of vertices of this Newton polygon
INPUT:
- ``copy`` -- a boolean (default: ``True``)
OUTPUT:
The list of vertices of this Newton polygon (or a copy of it if ``copy`` is set to True)
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,5) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 5)
sage: v = NP.vertices(); v [(0, 0), (1, 1), (2, 5)]
TESTS:
sage: del v[0] sage: v [(1, 1), (2, 5)] sage: NP.vertices() [(0, 0), (1, 1), (2, 5)] """ else:
def last_slope(self): """ Returns the last (infinite) slope of this Newton polygon if it is infinite and ``+Infinity`` otherwise.
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP1 = NewtonPolygon([ (0,0), (1,1), (2,8), (3,5) ], last_slope=3) sage: NP1.last_slope() 3
sage: NP2 = NewtonPolygon([ (0,0), (1,1), (2,5) ]) sage: NP2.last_slope() +Infinity
We check that the last slope of a sum (resp. a produit) is the minimum of the last slopes of the summands (resp. the factors)::
sage: (NP1 + NP2).last_slope() 3 sage: (NP1 * NP2).last_slope() 3 """
""" Returns the slopes of this Newton polygon
INPUT:
- ``repetition`` -- a boolean (default: ``True``)
OUTPUT:
The consecutive slopes (not including the last slope if the polygon is infinity) of this Newton polygon.
If ``repetition`` is True, each slope is repeated a number of times equal to its length. Otherwise, it appears only one time.
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (3,6) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 6)
sage: NP.slopes() [1, 5/2, 5/2]
sage: NP.slopes(repetition=False) [1, 5/2] """ else:
""" Returns the convex hull of ``self`` and ``other``
INPUT:
- ``other`` -- a Newton polygon
OUTPUT:
The Newton polygon, which is the convex hull of this Newton polygon and ``other``
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP1 = NewtonPolygon([ (0,0), (1,1), (2,6) ]); NP1 Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 6) sage: NP2 = NewtonPolygon([ (0,0), (1,3/2) ], last_slope=2); NP2 Infinite Newton polygon with 2 vertices: (0, 0), (1, 3/2) ending by an infinite line of slope 2
sage: NP1 + NP2 Infinite Newton polygon with 2 vertices: (0, 0), (1, 1) ending by an infinite line of slope 2 """
""" Returns the Minkowski sum of ``self`` and ``other``
INPUT:
- ``other`` -- a Newton polygon
OUTPUT:
The Newton polygon, which is the Minkowski sum of this Newton polygon and ``other``.
.. NOTE::
If ``self`` and ``other`` are respective Newton polygons of some polynomials `f` and `g` the self*other is the Newton polygon of the product `fg`
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP1 = NewtonPolygon([ (0,0), (1,1), (2,6) ]); NP1 Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 6) sage: NP2 = NewtonPolygon([ (0,0), (1,3/2) ], last_slope=2); NP2 Infinite Newton polygon with 2 vertices: (0, 0), (1, 3/2) ending by an infinite line of slope 2
sage: NP = NP1 * NP2; NP Infinite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 5/2) ending by an infinite line of slope 2
The slopes of ``NP`` is the union of thos of ``NP1`` and those of ``NP2`` which are less than the last slope::
sage: NP1.slopes() [1, 5] sage: NP2.slopes() [3/2] sage: NP.slopes() [1, 3/2] """
""" Returns ``self`` dilated by ``exp``
INPUT:
- ``exp`` -- a positive integer
OUTPUT:
This Newton polygon scaled by a factor ``exp``.
NOTE::
If ``self`` is the Newton polygon of a polynomial `f`, then ``self^exp`` is the Newton polygon of `f^{exp}`.
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,6) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 6)
sage: NP^10 Finite Newton polygon with 3 vertices: (0, 0), (10, 10), (20, 60) """
""" Returns ``self`` shifted by `(0,i)`
INPUT:
- ``i`` -- a rational number
OUTPUT:
This Newton polygon shifted by the vector `(0,i)`
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,6) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 6)
sage: NP << 2 Finite Newton polygon with 3 vertices: (0, 2), (1, 3), (2, 8) """
""" Returns ``self`` shifted by `(0,-i)`
INPUT:
- ``i`` -- a rational number
OUTPUT:
This Newton polygon shifted by the vector `(0,-i)`
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,6) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (2, 6)
sage: NP >> 2 Finite Newton polygon with 3 vertices: (0, -2), (1, -1), (2, 4) """
""" Returns `self(x)`
INPUT:
- ``x`` -- a real number
OUTPUT:
The value of this Newton polygon at abscissa `x`
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (3,6) ]); NP Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 6)
sage: [ NP(i) for i in range(4) ] [0, 1, 7/2, 6] """ # complexity: O(log(n)) return Infinity return vertices[-1][1] + lastslope * (x - vertices[-1][0]) else:
r""" Comparisons of two Newton polygons.
TESTS::
sage: from sage.geometry.newton_polygon import NewtonPolygon
sage: NP1 = NewtonPolygon([ (0,0), (1,1), (3,6) ]) sage: NP2 = NewtonPolygon([ (0,0), (1,1), (2,6), (3,6) ]) sage: NP1 == NP2 True sage: NP1 != NP2 False
sage: NP1 >= NP1 and NP2 >= NP2 True sage: NP1 > NP1 or NP2 > NP2 False
sage: NP1 = NewtonPolygon([ (0,0), (1,1), (2,6) ]) sage: NP2 = NewtonPolygon([ (0,0), (1,3/2) ], last_slope=2) sage: NP3 = NP1 + NP2
sage: NP1 <= NP2 False sage: NP3 <= NP1 True sage: NP3 <= NP2 True
sage: NP1 < NP1 False sage: NP1 < NP2 False
sage: NP1 >= NP2 False
sage: NP1 >= NP3 True
sage: NP1 > NP1 False sage: NP1 > NP2 False
sage: NP1 >= NP3 and NP2 >= NP3 and NP3 <= NP1 and NP3 <= NP2 True sage: NP1 > NP3 and NP2 > NP3 True sage: NP3 < NP2 and NP3 < NP1 True """ return True return False
else: return False
""" Plot this Newton polygon.
.. NOTE::
All usual rendering options (color, thickness, etc.) are available.
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,6) ]) sage: polygon = NP.plot() """ from sage.plot.graphics import Graphics return Graphics() else: + line([(xstart, ystart+0.5)] + vertices + [(xend, yend+0.5)], **kwargs) \ + line([(xend, yend+0.5), (xend, yend+1)], linestyle="--", **kwargs) else: return line([(xstart, ystart+1), (xstart,ystart+0.5)], linestyle="--", **kwargs) \ + line([(xstart, ystart+0.5)] + vertices + [(xend+0.5, yend + 0.5*self.last_slope())], **kwargs) \ + line([(xend+0.5, yend + 0.5*self.last_slope()), (xend+1, yend+self.last_slope())], linestyle="--", **kwargs)
""" Returns the symmetric of ``self``
INPUT:
- ``degree`` -- an integer (default: the top right abscissa of this Newton polygon)
OUTPUT:
The image this Newton polygon under the symmetry '(x,y) \mapsto (degree-x, y)`
EXAMPLES:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NP = NewtonPolygon([ (0,0), (1,1), (2,5) ]) sage: NP2 = NP.reverse(); NP2 Finite Newton polygon with 3 vertices: (0, 5), (1, 1), (2, 0)
We check that the slopes of the symmetric Newton polygon are the opposites of the slopes of the original Newton polygon::
sage: NP.slopes() [1, 4] sage: NP2.slopes() [-4, -1] """ raise ValueError("Can only reverse *finite* Newton polygons")
""" Construct a Newton polygon.
INPUT:
- ``arg`` -- a list/tuple/iterable of vertices or of slopes. Currently, slopes must be rational numbers.
- ``sort_slopes`` -- boolean (default: ``True``). Specifying whether slopes must be first sorted
- ``last_slope`` -- rational or infinity (default: ``Infinity``). The last slope of the Newton polygon
OUTPUT:
The corresponding Newton polygon.
.. note::
By convention, a Newton polygon always contains the point at infinity `(0, \infty)`. These polygons are attached to polynomials or series over discrete valuation rings (e.g. padics).
EXAMPLES:
We specify here a Newton polygon by its vertices::
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NewtonPolygon([ (0,0), (1,1), (3,5) ]) Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 5)
We note that the convex hull of the vertices is automatically computed::
sage: NewtonPolygon([ (0,0), (1,1), (2,8), (3,5) ]) Finite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 5)
Note that the value ``+Infinity`` is allowed as the second coordinate of a vertex::
sage: NewtonPolygon([ (0,0), (1,Infinity), (2,8), (3,5) ]) Finite Newton polygon with 2 vertices: (0, 0), (3, 5)
If last_slope is set, the returned Newton polygon is infinite and ends with an infinite line having the specified slope::
sage: NewtonPolygon([ (0,0), (1,1), (2,8), (3,5) ], last_slope=3) Infinite Newton polygon with 3 vertices: (0, 0), (1, 1), (3, 5) ending by an infinite line of slope 3
Specifying a last slope may discard some vertices::
sage: NewtonPolygon([ (0,0), (1,1), (2,8), (3,5) ], last_slope=3/2) Infinite Newton polygon with 2 vertices: (0, 0), (1, 1) ending by an infinite line of slope 3/2
Next, we define a Newton polygon by its slopes::
sage: NP = NewtonPolygon([0, 1/2, 1/2, 2/3, 2/3, 2/3, 1, 1]) sage: NP Finite Newton polygon with 5 vertices: (0, 0), (1, 0), (3, 1), (6, 3), (8, 5) sage: NP.slopes() [0, 1/2, 1/2, 2/3, 2/3, 2/3, 1, 1]
By default, slopes are automatically sorted::
sage: NP2 = NewtonPolygon([0, 1, 1/2, 2/3, 1/2, 2/3, 1, 2/3]) sage: NP2 Finite Newton polygon with 5 vertices: (0, 0), (1, 0), (3, 1), (6, 3), (8, 5) sage: NP == NP2 True
except if the contrary is explicitely mentioned::
sage: NewtonPolygon([0, 1, 1/2, 2/3, 1/2, 2/3, 1, 2/3], sort_slopes=False) Finite Newton polygon with 4 vertices: (0, 0), (1, 0), (6, 10/3), (8, 5)
Slopes greater that or equal last_slope (if specified) are discarded::
sage: NP = NewtonPolygon([0, 1/2, 1/2, 2/3, 2/3, 2/3, 1, 1], last_slope=2/3) sage: NP Infinite Newton polygon with 3 vertices: (0, 0), (1, 0), (3, 1) ending by an infinite line of slope 2/3 sage: NP.slopes() [0, 1/2, 1/2]
Be careful, do not confuse Newton polygons provided by this class with Newton polytopes. Compare::
sage: NP = NewtonPolygon([ (0,0), (1,45), (3,6) ]); NP Finite Newton polygon with 2 vertices: (0, 0), (3, 6)
sage: x, y = polygen(QQ,'x, y') sage: p = 1 + x*y**45 + x**3*y**6 sage: p.newton_polytope() A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices sage: p.newton_polytope().vertices() (A vertex at (0, 0), A vertex at (1, 45), A vertex at (3, 6)) """
""" Parent class for all Newton polygons.
sage: from sage.geometry.newton_polygon import ParentNewtonPolygon sage: ParentNewtonPolygon() Parent for Newton polygons
TESTS:
This class is a singleton.
sage: ParentNewtonPolygon() is ParentNewtonPolygon() True
::
sage: TestSuite(ParentNewtonPolygon()).run() """
""" Returns the string representation of this parent, which is ``Parent for Newton polygons``
TESTS:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NewtonPolygon Parent for Newton polygons
sage: NewtonPolygon._repr_() 'Parent for Newton polygons' """
""" Returns a Newton polygon (which is the empty one)
TESTS:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NewtonPolygon._an_element_() Empty Newton polygon """
""" INPUT:
- ``arg`` -- an argument describing the Newton polygon
- ``sort_slopes`` -- boolean (default: ``True``). Specifying whether slopes must be first sorted
- ``last_slope`` -- rational or infinity (default: ``Infinity``). The last slope of the Newton polygon
The first argument ``arg`` can be either:
- a polyhedron in `\QQ^2`
- the element ``0`` (corresponding to the empty Newton polygon)
- the element ``1`` (corresponding to the Newton polygon of the constant polynomial equal to 1)
- a list/tuple/iterable of vertices
- a list/tuple/iterable of slopes
OUTPUT:
The corresponding Newton polygon.
For more informations, see :class:`ParentNewtonPolygon`.
TESTS:
sage: from sage.geometry.newton_polygon import NewtonPolygon sage: NewtonPolygon(0) Empty Newton polygon sage: NewtonPolygon(1) Finite Newton polygon with 1 vertex: (0, 0) """ vertices=[(0,0)], rays=[(0,1)]) try: arg = list(arg) except TypeError: raise TypeError("argument must be a list of coordinates or a list of (rational) slopes") raise TypeError("argument must be a list of coordinates or a list of (rational) slopes") else:
else:
|