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 PN. 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 +∞ 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.
These are the functions available for constructing Newton polygons and retrieving the points which describe them.
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 +∞ 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.
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 +∞ 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".
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, vi) where i is the exponent of a term of f and vi is the valuation of the coefficient of the ith term. The points at +∞ 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.
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 +∞ 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.
The standard Newton polygon of the defining polynomial of the curve C.
Faces: MonStgElt Default: "All"
The Newton polygon that is the compact convex hull of the set or sequence V of points of the form < a, b > 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.
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.
> 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 LNewton 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)}
These polygons will be referred to in later examples.
Both the vertices < a, b > and faces < a, b, c > (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 PN 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.
The sequence of faces < a, b, c > (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.
Those faces of the compact convex hull of PN starting at the lowest of the leftmost points which have strictly negative gradient.
Those faces of the compact convex hull of PN which bound it below in the y direction.
The union of lower faces which aren't inner faces and the faces which bound the compact convex hull of PN above in the y-direction (ignoring infinite points).
The faces of the compact convex hull of PN.
> 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> ]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).
The sequence of vertices of N. The vertices will be listed anticlockwise from the lowest of the leftmost points.
The sequence of vertices which arise as endpoints of inner faces.
The sequence of vertices which arise as endpoints of lower faces.
The sequence of vertices which arise as endpoints of outer faces.
The sequence of vertices of the compact convex hull of PN.
> 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)}
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> ]
A sequence containing the two end vertices of the face F = < a, b, c >.
Those faces of the polygon N returned by Faces on which the point p = < a, b > lies.
> 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> ]
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.
A sequence containing the gradient vectors of the faces of the newton polygon N.
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.
The slopes of the faces of the newton polygon N.
The slopes of the polygon N corresponding of InnerFaces, LowerFaces and AllFaces respectively.
> 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); -4The gradient of the face can now be easily computed as shown.
> a := GradientVector(f)[1]; > b := GradientVector(f)[2]; > -a/b; -1/4
Once more, recall that PN 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.
Return true if and only if the tuple F = < a, b, c > describes a line coinciding with a face of the polygon N as returned by Faces.
Return true if and only if the point p = < a, b > of the rational plane (given as a tuple) is a vertex of the polygon N as returned by Vertices.
Return true if and only if the point p = < a, b > given as a tuple lies strictly in the interior of the polygon N.
Return true if and only if the point p = < a, b > given as a tuple lies on the boundary of the polygon N, that is, the point is contained in a face of N.
Return true if and only if the point p = < a, b > (given as a tuple) lies on the polygon N.