Newton Polygons#

All polygons are determined by a finite collection of points in the rational plane. For Magma, these points are the most basic attribute of any Newton polygon. They are always determined and recorded on creation of a polygon. Throughout this chapter, for a Newton polygon \(N\), these points are denoted by \(P_N\). As seen in the introduction, the main class of polygons is that comprising polygons in the first quadrant of the plane and including the points \(+\infty\) on the two axes. But there are other useful types, especially when calculating factorizations of univariate polynomials over series rings. The data distinguishing the different flavours of Newton polygon is the collection of lines and points that are considered to be faces and vertices.

Creation of Newton Polygons#

These are the functions available for constructing Newton polygons and retrieving the points which describe them.

NewtonPolygon(f): RngMPolElt -> NwtnPgon#

Faces: MonStgElt                    Default: "Inner"

The standard Newton polygon of a polynomial \(f\) in two variables. This is the hull of the Newton points of the polynomial together with the points \(+\infty\) on each axis. The horizontal and vertical ‘end’ faces are not listed among the faces of the polygon; the points at infinity are not listed among the vertices of the polygon.

The parameter Faces can have the value "Inner", "Lower" or "All". This determines which faces are returned by the intrinsic Faces.

NewtonPolygon(f): RngUPolElt -> NwtnPgon#

SwapAxes: BoolElt                      Default: false
Faces   : MonStgElt                    Default: 

The standard Newton polygon of a polynomial in one variable defined over a series ring or a local ring or field. A value of true for SwapAxes is only valid if the polynomial is over a series ring. If SwapAxes is set to true then the exponents of the series variable will be plotted on the horizontal axis and the exponents of the polynomial on the vertical axis.

For a polynomial over a series ring, the hull includes the points \(+\infty\) on each axis. For a polynomial over a local ring, the infinite points are not included.

The parameter Faces can have the value "All", "Inner" or "Lower". This determines which faces are returned by the intrinsic Faces. The default for series rings is "Inner" and for local rings is "Lower".

NewtonPolygon(f, p): RngUPolElt, RngOrdIdl -> NwtnPgon#

NewtonPolygon(f, p): RngUPolElt, RngFunOrdIdl -> NwtnPgon#

NewtonPolygon(f, p): RngUPolElt, RngIntElt -> NwtnPgon#

Faces: MonStgElt                    Default: "Inner"

The newton polygon of \(f\) where \(p\) is a prime used for valuations of the coefficients of \(f\). The polynomial \(f\) may be over the integers or rationals or a number field or algebraic function field or an order thereof. The prime \(p\) may be an integer or a prime ideal. The newton polygon will have points \((i, v_i)\) where \(i\) is the exponent of a term of \(f\) and \(v_i\) is the valuation of the coefficient of the \(i\)th term. The points at \(+\infty\) on each axis are included.

The parameter Faces can have the value "Inner", "Lower" or "All". This determines which faces are returned by the intrinsic Faces.

NewtonPolygon(f, p): RngUPolElt, PlcFunElt -> NwtnPgon#

Faces: MonStgElt                    Default: "Inner"

The newton polygon of the polynomial \(f\) where the place \(p\) of an algebraic function field is the prime used for determining the valuations of the coefficients of \(f\). The points at \(+\infty\) on each axis are included.

The parameter Faces can have the value "Inner", "Lower" or "All". This determines which faces are returned by the intrinsic Faces.

NewtonPolygon(C): Crv -> NwtnPgon#: The standard Newton polygon of the defining polynomial of the curve \(C\).

NewtonPolygon(V): SeqEnum -> NwtnPgon#

NewtonPolygon(V): SetEnum -> NwtnPgon#

Faces: MonStgElt                    Default: "All"

The Newton polygon that is the compact convex hull of the set or sequence \(V\) of points of the form \(\left< a,b \right>\) where \(a\), \(b\) are integers or rational numbers.

The parameter Faces can have the value "All", "Lower" or "Inner". This determines which faces are returned by the intrinsic Faces.

DefiningPoints(N): NwtnPgon -> SeqEnum#: The points of the rational plane used in the initial creation of \(N\). Applying this function to two polygons allows their defining points to be compared. No explicit function is provided for testing whether defining points of two polygons are equal.

Example: Create Ex (ex-4f67e3)#

Some ways of creating Newton Polygons from polynomials are shown below.

> P<y> := PuiseuxSeriesRing(Rationals());
> R<x> := PolynomialRing(P);
> f := 3*x^4 + (5*y^3 + 4*y^(1/4))*x^3 + (7*y^2 + 1/2*y^(1/3))*x^2 + 6*x + y^(
> 4/5);
> N := NewtonPolygon(f);
> N;
Newton Polygon of 3*x^4 + (4*y^(1/4) + 5*y^3)*x^3 + (1/2*y^(1/3) + 7*y^2)*x^2 +
6*x + y^(4/5) over Puiseux series field in y over Rational Field
> P<x> := PolynomialRing(Integers());
> L := ext<ext<pAdicRing(5, 100) | 3> | x^2 + 5>;
> R<x> := PolynomialRing(L);
> f := 3*x^4 + 75*x^3 + 78*x^2 + 10*x + 750;
> NR := NewtonPolygon(f);
> NR;
Newton Polygon of 3*x^4 + 75*x^3 + 78*x^2 + 10*x + 750 over L

Run in calculator

Newton Polygons can also be created by specifying the defining points that the polygon must enclose.

> N2 := NewtonPolygon({<2, 0>, <0, 3>, <4, 1>});
> N2;
Newton Polygon with defining points {(0, 3), (2, 0), (4, 1)}
> N6 := NewtonPolygon({<1, 4>, <1, 6>, <2, 4>, <3, 1>, <6, 1>, <5, 2>, <4, 5>,
> <4, 7>, <6, 6>, <7, 7>, <2, 7>, <5, 9>, <8, 4>, <8, 6>, <8, 8>, <7, 9>});
> N6;
Newton Polygon with defining points {(1, 4), (1, 6), (2, 4), (2, 7), (3, 1), (4,
5), (4, 7), (5, 2), (5, 9), (6, 1), (6, 6), (7, 7), (7, 9), (8, 4), (8, 6), (8,
8)}

Run in calculator

These polygons will be referred to in later examples.

Vertices and Faces of Polygons#

Both the vertices \(\left< a,b \right>\) and faces \(\left< a,b,c \right>\) (representing \(ax + by = c\)) of a given polygon \(N\) are computed as needed. As seen above, these will be a particular choice of possible faces and vertices determined by the data used to create the polygon. They can be recovered using the Faces() and Vertices() intrinsics. A different choice of faces and vertices, those faces and vertices of the compact convex hull of the defining points say, can be made using the other intrinsics below.

Recall that \(P_N\) denotes the set of points used in the definition of the Newton polygon \(N\) whether they arise as the powers of monomials appearing in a polynomial or have been given explicitly as a sequence of pairs.

Faces(N): NwtnPgon -> SeqEnum#: The sequence of faces \(\left< a, b, c \right>\) (representing \(ax + by = c\)) of \(N\) listed anticlockwise. How this is interpreted in terms of the points used to create \(N\) depends on the creation function used (see Section Creation of Newton Polygons). The faces are listed anticlockwise starting with the face with its left endpoint being the lowest of the leftmost points.

InnerFaces(N): NwtnPgon -> SeqEnum#: Those faces of the compact convex hull of \(P_N\) starting at the lowest of the leftmost points which have strictly negative gradient.

LowerFaces(N): NwtnPgon -> SeqEnum#: Those faces of the compact convex hull of \(P_N\) which bound it below in the \(y\) direction.

OuterFaces(N): NwtnPgon -> SeqEnum#: The union of lower faces which aren’t inner faces and the faces which bound the compact convex hull of \(P_N\) above in the \(y\)-direction (ignoring infinite points).

AllFaces(N): NwtnPgon -> SeqEnum#: The faces of the compact convex hull of \(P_N\).

Example: Faces Ex (ex-a15e3f)#

Using some of the polygons defined before the different types of faces are illustrated.

> Faces(N);
[ <4, 5, 4> ]
> InnerFaces(N);
[ <4, 5, 4> ]
> OuterFaces(N);
[ <0, 1, 0>, <-1, -4, -4>, <-11, -60, -48> ]
> AllFaces(N);
[ <4, 5, 4>, <0, 1, 0>, <-1, -4, -4>, <-11, -60, -48> ]
> Faces(NR);
[ <4, 1, 6>, <2, 1, 4>, <0, 1, 0> ]
> InnerFaces(NR);
[ <4, 1, 6>, <2, 1, 4> ]
> LowerFaces(NR);
[ <4, 1, 6>, <2, 1, 4>, <0, 1, 0> ]

Run in calculator

For the polynomial over the Puiseux Field it is no coincidence that InnerFaces and Faces return the same sequences. Similarly, for the polynomial over the local ring Faces is defined to be LowerFaces. For both, this is the category of faces that gives the most information for the purposes that the polygon is used. It can also be noted that combining InnerFaces and OuterFaces will give AllFaces with no repetitions (though repetitions will occur if the polygon has only one face and this face is an inner face).

Vertices(N): NwtnPgon -> SeqEnum#: The sequence of vertices of \(N\). The vertices will be listed anticlockwise from the lowest of the leftmost points.

InnerVertices(N): NwtnPgon -> SeqEnum#: The sequence of vertices which arise as endpoints of inner faces.

LowerVertices(N): NwtnPgon -> SeqEnum#: The sequence of vertices which arise as endpoints of lower faces.

OuterVertices(N): NwtnPgon -> SeqEnum#: The sequence of vertices which arise as endpoints of outer faces.

AllVertices(N): NwtnPgon -> SeqEnum#: The sequence of vertices of the compact convex hull of \(P_N\).

Example: Vertices Ex (ex-534640)#

This example illustrates the types of vertices that can be calculated. Note that the printing of these polygons, created from their defining points, changes as more information is calculated. This would occur in the same manner if faces were being calculated instead of vertices.

> InnerVertices(N2);
[ <0, 3>, <2, 0> ]
> N2;
Newton Polygon with vertices {(0, 3), (2, 0)} and defining points {(0, 3), (2,
0), (4, 1)}
> InnerVertices(N6);
[ <1, 4>, <3, 1> ]
> N6;
Newton Polygon with vertices {(1, 4), (3, 1)} and defining points {(1, 4), (1,
6), (2, 4), (2, 7), (3, 1), (4, 5), (4, 7), (5, 2), (5, 9), (6, 1), (6, 6), (7,
7), (7, 9), (8, 4), (8, 6), (8, 8)}
> Vertices(N2);
[ <0, 3>, <2, 0>, <4, 1> ]
> Vertices(N6);
[ <1, 4>, <3, 1>, <6, 1>, <8, 4>, <8, 8>, <7, 9>, <5, 9>, <2, 7>, <1, 6> ]
> AllVertices(N2);
[ <0, 3>, <2, 0>, <4, 1> ]
> N2;
Newton Polygon with vertices {(0, 3), (2, 0), (4, 1)} and defining points {(0,
3), (2, 0), (4, 1)}
> AllVertices(N6);
[ <1, 4>, <3, 1>, <6, 1>, <8, 4>, <8, 8>, <7, 9>, <5, 9>, <2, 7>, <1, 6> ]
> N6;
Newton Polygon with vertices {(1, 4), (3, 1), (6, 1), (8, 4), (8, 8), (7, 9),
(5, 9), (2, 7), (1, 6)} and defining points {(1, 4), (1, 6), (2, 4), (2, 7), (3,
1), (4, 5), (4, 7), (5, 2), (5, 9), (6, 1), (6, 6), (7, 7), (7, 9), (8, 4), (8,
6), (8, 8)}

Run in calculator

Here Vertices has been defined to be AllVertices. All the known vertices of the polygon are printed when the polygon is printed. There is some overlap between the inner and outer vertices as is shown below. Every vertex is either an inner vertex or an outer vertex with some being both. Not all defining points are vertices.

> OuterVertices(N6);
[ <3, 1>, <6, 1>, <8, 4>, <8, 8>, <7, 9>, <5, 9>, <2, 7>, <1, 6>, <1, 4> ]
> OuterVertices(N2);
[ <2, 0>, <4, 1>, <0, 3> ]

Run in calculator

EndVertices(F): NwtnPgonFace -> SeqEnum#: A sequence containing the two end vertices of the face \(F = \left< a,b,c \right>\).

FacesContaining(N, p): NwtnPgon, Tup -> SeqEnum#: Those faces of the polygon \(N\) returned by Faces on which the point \(p = \langle a, b \rangle\) lies.

Example: Sp Vertices Ex (ex-8ed2f7)#

Using some of the example polygons that have been created above, we illustrate the simple use of EndVertices and FacesContaining.

> AN := AllFaces(N);
> AN;
[ <4, 5, 4>, <0, 1, 0>, <-1, -4, -4>, <-11, -60, -48> ]
> A6 := AllFaces(N6);
> A6;
[ <3, 2, 11>, <0, 1, 1>, <-3, 2, -16>, <-1, 0, -8>, <-1, -1, -16>, <0, -1, -9>,
<2, -3, -17>, <1, -1, -5>, <1, 0, 1> ]
> AllVertices(N);
[ <0, 4/5>, <1, 0>, <4, 0>, <3, 1/4> ]
> AllVertices(N6);
[ <1, 4>, <3, 1>, <6, 1>, <8, 4>, <8, 8>, <7, 9>, <5, 9>, <2, 7>, <1, 6> ]
> EndVertices(AN[1]);
[ <0, 4/5>, <1, 0> ]
> EndVertices(AN[4]);
[ <0, 4/5>, <3, 1/4> ]
> EndVertices(A6[1]);
[ <1, 4>, <3, 1> ]
> EndVertices(A6[5]);
[ <7, 9>, <8, 8> ]
> EndVertices(A6[9]);
[ <1, 4>, <1, 6> ]
> FacesContaining(N, <1, 0>);
[ <4, 5, 4> ]
> FacesContaining(N6, <1, 0>);
[]
> FacesContaining(N6, <4, 1>);
[ <0, 1, 1> ]
> FacesContaining(N, <4, 1>);
[]
> FacesContaining(N6, <3, 1>);
[ <3, 2, 11>, <0, 1, 1> ]

Run in calculator

GradientVector(F): NwtnPgonFace -> Tup#: The \(a\) and \(b\) values of the line describing the face \(F\) of the form \(a*x + b*y = c\) where \(a, b\) and \(c\) are integers.

GradientVectors(N): NwtnPgon -> [ Tup ]#: A sequence containing the gradient vectors of the faces of the newton polygon \(N\).

Weight(F): NwtnPgonFace -> RngIntElt#: The \(c\) value of the line describing the face \(F\) of the form \(a*x + b*y = c\) where \(a, b\) and \(c\) are integers.

Slopes(N): NwtnPgon -> SeqEnum#: The slopes of the faces of the newton polygon \(N\).

InnerSlopes(N): NwtnPgon -> SeqEnum#
LowerSlopes(N): NwtnPgon -> SeqEnum#
AllSlopes(N): NwtnPgon -> SeqEnum#: The slopes of the polygon \(N\) corresponding of InnerFaces, LowerFaces and AllFaces respectively.

Example: Grad Ex (ex-260949)#

In this example GradientVector and Weight can be seen to be access functions on the components of a face of a polygon.

> A := AllFaces(N);
> A;
[ <4, 5, 4>, <0, 1, 0>, <-1, -4, -4>, <-11, -60, -48> ]
> f := A[3];
> GradientVector(f);
<-1, -4>
> Weight(f);
-4

Run in calculator

The gradient of the face can now be easily computed as shown.

> a := GradientVector(f)[1];
> b := GradientVector(f)[2];
> -a/b;
-1/4

Run in calculator

Tests for Points and Faces#

Once more, recall that \(P_N\) denotes the finite set of points in the plane used to define the Newton polygon \(N\). Whether or not a point is considered to lie in a polygon depends on what are considered to be its faces. Magma always uses the list of faces returned by Faces(N) when testing points. Of course, this is not always the case in applications. One must to perform other tests explicitly when there is doubt.

IsFace(N, F): NwtnPgon, Tup -> BoolElt#: Return true if and only if the tuple \(F = \langle a, b, c \rangle\) describes a line coinciding with a face of the polygon \(N\) as returned by Faces.

IsVertex(N, p): NwtnPgon, Tup -> BoolElt#: Return true if and only if the point \(p = \left< a,b \right>\) of the rational plane (given as a tuple) is a vertex of the polygon \(N\) as returned by Vertices.

IsInterior(N, p): NwtnPgon, Tup -> BoolElt#: Return true if and only if the point \(p = \left< a,b \right>\) given as a tuple lies strictly in the interior of the polygon \(N\).

IsBoundary(N, p): NwtnPgon, Tup -> BoolElt#: Return true if and only if the point \(p = \left< a,b \right>\) given as a tuple lies on the boundary of the polygon \(N\), that is, the point is contained in a face of \(N\).

IsPoint(N, p): NwtnPgon, Tup -> BoolElt#: Return true if and only if the point \(p = \left< a,b \right>\) (given as a tuple) lies on the polygon \(N\).