|
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".
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, 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.
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 < 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.
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
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)}
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.
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> ]
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.
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)}
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.
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> ]
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.
LowerSlopes(N) : NwtnPgon -> SeqEnum
AllSlopes(N) : NwtnPgon -> SeqEnum
The slopes of the polygon N
corresponding of InnerFaces, LowerFaces and
AllFaces respectively.
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
The 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|