Newton polygon

Construction of the Newton polygon of the polynomial 1 + 5 X + 1/5 X² + 35 X³ + 25 X⁵ + 625 X⁶ with respect to the 5-adic valuation.

A priori, given a polynomial over a field, the behaviour of the roots (assuming it has roots) will be unknown. Newton polygons provide one technique for the study of the behaviour of the roots.

Let ${\displaystyle K}$ be a field endowed with a non-archimedean valuation ${\displaystyle v_{K}:K\to \mathbb {R} \cup \{\infty \}}$, and let

${\displaystyle f(x)=a_{n}x^{n}+\cdots +a_{1}x+a_{0}\in K[x],}$

with ${\displaystyle a_{0}a_{n}\neq 0}$. Then the Newton polygon of ${\displaystyle f}$ is defined to be the lower boundary of the convex hull of the set of points ${\displaystyle P_{i}=\left(i,v_{K}(a_{i})\right),}$ ignoring the points with ${\displaystyle a_{i}=0}$.

Restated geometrically, plot all of these points P_i on the xy-plane. Let's assume that the points indices increase from left to right (P₀ is the leftmost point, P_n is the rightmost point). Then, starting at P₀, draw a ray straight down parallel with the y-axis, and rotate this ray counter-clockwise until it hits the point P_k1 (not necessarily P₁). Break the ray here. Now draw a second ray from P_k1 straight down parallel with the y-axis, and rotate this ray counter-clockwise until it hits the point P_k2. Continue until the process reaches the point P_n; the resulting polygon (containing the points P₀, P_k1, P_k2, ..., P_km, P_n) is the Newton polygon.

Another, perhaps more intuitive way to view this process is this : consider a rubber band surrounding all the points P₀, ..., P_n. Stretch the band upwards, such that the band is stuck on its lower side by some of the points (the points act like nails, partially hammered into the xy plane). The vertices of the Newton polygon are exactly those points.

For a neat diagram of this see Ch6 §3 of "Local Fields" by JWS Cassels, LMS Student Texts 3, CUP 1986. It is on p99 of the 1986 paperback edition.

With the notations in the previous section, the main result concerning the Newton polygon is the following theorem,[1] which states that the valuation of the roots of ${\displaystyle f}$ are entirely determined by its Newton polygon:

Let ${\displaystyle \mu _{1},\mu _{2},\ldots ,\mu _{r}}$ be the slopes of the line segments of the Newton polygon of ${\displaystyle f(x)}$ (as defined above) arranged in increasing order, and let ${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{r}}$ be the corresponding lengths of the line segments projected onto the x-axis (i.e. if we have a line segment stretching between the points ${\displaystyle P_{i}}$ and ${\displaystyle P_{j}}$ then the length is ${\displaystyle j-i}$).

• The ${\displaystyle \mu _{i}}$ are distinct;
• ${\displaystyle \sum _{i}\lambda _{i}=n}$;
• if ${\displaystyle \alpha }$ is a root of ${\displaystyle f}$ in ${\displaystyle K}$, ${\displaystyle v(\alpha )\in \{-\mu _{1},\ldots -\mu _{r}\}}$;
• for every ${\displaystyle i}$, the number of roots of ${\displaystyle f}$ whose valuations are equal to ${\displaystyle -\mu _{i}}$ (counting multiplicities) is at most ${\displaystyle \lambda _{i}}$, with equality if ${\displaystyle f}$ splits into the product of linear factors over ${\displaystyle K}$.

With the notation of the previous sections, we denote, in what follows, by ${\displaystyle L}$ the splitting field of ${\displaystyle f}$ over ${\displaystyle K}$, and by ${\displaystyle v_{L}}$ an extension of ${\displaystyle v_{K}}$ to ${\displaystyle L}$.

Newton polygon theorem is often used to show the irreducibility of polynomials, as in the next corollary for example:

• Suppose that the valuation ${\displaystyle v}$ is discrete and normalized, and that the Newton polynomial of ${\displaystyle f}$ contains only one segment whose slope is ${\displaystyle \mu }$ and projection on the x-axis is ${\displaystyle \lambda }$. If ${\displaystyle \mu =a/n}$, with ${\displaystyle a}$ coprime to ${\displaystyle n}$, then ${\displaystyle f}$ is irreducible over ${\displaystyle K}$. In particular, since the Newton polygon of an Eisenstein polynomial consists of a single segment of slope ${\displaystyle -{\frac {1}{n}}}$ connecting ${\displaystyle (0,1)}$ and ${\displaystyle (n,0)}$, Eisenstein criterion follows.

Indeed, by the main theorem, if ${\displaystyle \alpha }$ is a root of ${\displaystyle f}$, ${\displaystyle v_{L}(\alpha )=-a/n.}$ If ${\displaystyle f}$ were not irreducible over ${\displaystyle K}$, then the degree ${\displaystyle d}$ of ${\displaystyle \alpha }$ would be ${\displaystyle <n}$, and there would hold ${\displaystyle v_{L}(\alpha )\in {1 \over d}\mathbb {Z} }$. But this is impossible since ${\displaystyle v_{L}(\alpha )=-a/n}$ with ${\displaystyle a}$ coprime to ${\displaystyle n}$.

Another simple corollary is the following:

• Assume that ${\displaystyle (K,v_{K})}$ is Henselian. If the Newton polygon of ${\displaystyle f}$ fulfills ${\displaystyle \lambda _{i}=1}$ for some ${\displaystyle i}$, then ${\displaystyle f}$ has a root in ${\displaystyle K}$.

Proof: By the main theorem, ${\displaystyle f}$ must have a single root ${\displaystyle \alpha }$ whose valuation is ${\displaystyle v_{L}(\alpha )=-\mu _{i}.}$ In particular, ${\displaystyle \alpha }$ is separable over ${\displaystyle K}$. If ${\displaystyle \alpha }$ does not belong to ${\displaystyle K}$, ${\displaystyle \alpha }$ has a distinct Galois conjugate ${\displaystyle \alpha '}$ over ${\displaystyle K}$, with ${\displaystyle v_{L}(\alpha ')=v_{L}(\alpha )}$,[2] and ${\displaystyle \alpha '}$ is a root of ${\displaystyle f}$, a contradiction.

More generally, the following factorization theorem holds:

• Assume that ${\displaystyle (K,v_{K})}$ is Henselian. Then ${\displaystyle f=A\,f_{1}\,f_{2}\cdots f_{r},}$, where ${\displaystyle A\in K}$, ${\displaystyle f_{i}\in K[X]}$ is monic for every ${\displaystyle i}$, the roots of ${\displaystyle f_{i}}$ are of valuation ${\displaystyle -\mu _{i}}$, and ${\displaystyle \deg(f_{i})=\lambda _{i}}$.[3]

Moreover, ${\displaystyle \mu _{i}=v_{K}(f_{i}(0))/\lambda _{i}}$, and if ${\displaystyle v_{K}(f_{i}(0))}$ is coprime to ${\displaystyle \lambda _{i}}$, ${\displaystyle f_{i}}$ is irreducible over ${\displaystyle K}$.

Proof: For every ${\displaystyle i}$, denote by ${\displaystyle f_{i}}$ the product of the monomials ${\displaystyle (X-\alpha )}$ such that ${\displaystyle \alpha }$ is a root of ${\displaystyle f}$ and ${\displaystyle v_{L}(\alpha )=-\mu _{i}}$. We also denote ${\displaystyle f=AP_{1}^{k_{1}}P_{2}^{k_{2}}\cdots P_{s}^{k_{s}}}$ the factorization of ${\displaystyle f}$ in ${\displaystyle K[X]}$ into prime monic factors ${\displaystyle (A\in K).}$ Let ${\displaystyle \alpha }$ be a root of ${\displaystyle f_{i}}$. We can assume that ${\displaystyle P_{1}}$ is the minimal polynomial of ${\displaystyle \alpha }$ over ${\displaystyle K}$. If ${\displaystyle \alpha '}$ is a root of ${\displaystyle P_{1}}$, there exists a K-automorphism ${\displaystyle \sigma }$ of ${\displaystyle L}$ that sends ${\displaystyle \alpha }$ to ${\displaystyle \alpha '}$, and we have ${\displaystyle v_{L}(\sigma \alpha )=v_{L}(\alpha )}$ since ${\displaystyle K}$ is Henselian. Therefore ${\displaystyle \alpha '}$ is also a root of ${\displaystyle f_{i}}$. Moreover, every root of ${\displaystyle P_{1}}$ of multiplicity ${\displaystyle \nu }$ is clearly a root of ${\displaystyle f_{i}}$ of multiplicity ${\displaystyle k_{1}\nu }$, since repeated roots share obviously the same valuation. This shows that ${\displaystyle P_{1}^{k_{1}}}$ divides ${\displaystyle f_{i}.}$ Let ${\displaystyle g_{i}=f_{i}/P_{1}^{k_{1}}}$. Choose a root ${\displaystyle \beta }$ of ${\displaystyle g_{i}}$. Notice that the roots of ${\displaystyle g_{i}}$ are distinct from the roots of ${\displaystyle P_{1}}$. Repeat the previous argument with the minimal polynomial of ${\displaystyle \beta }$ over ${\displaystyle K}$, assumed w.l.g. to be ${\displaystyle P_{2}}$, to show that ${\displaystyle P_{2}^{k_{2}}}$ divides ${\displaystyle g_{i}}$. Continuing this process until all the roots of ${\displaystyle f_{i}}$ are exhausted, one eventually arrives to ${\displaystyle f_{i}=P_{1}^{k_{1}}\cdots P_{m}^{k_{m}}}$, with ${\displaystyle m\leq s}$. This shows that ${\displaystyle f_{i}\in K[X]}$, ${\displaystyle f_{i}}$ monic. But the ${\displaystyle f_{i}}$ are coprime since their roots have distinct valuations. Hence clearly ${\displaystyle f=Af_{1}\cdot f_{2}\cdots f_{r}}$, showing the main contention. The fact that ${\displaystyle \lambda _{i}=\deg(f_{i})}$ follows from the main theorem, and so does the fact that ${\displaystyle \mu _{i}=v_{K}(f_{i}(0))/\lambda _{i}}$, by remarking that the Newton polygon of ${\displaystyle f_{i}}$ can have only one segment joining ${\displaystyle (0,v_{K}(f_{i}(0))}$ to ${\displaystyle (\lambda _{i},0=v_{K}(1))}$. The condition for the irreducibility of ${\displaystyle f_{i}}$ follows from the corollary above. (q.e.d.)

The following is an immediate corollary of the factorization above, and constitutes a test for the reducibility of polynomials over Henselian fields:

• Assume that ${\displaystyle (K,v_{K})}$ is Henselian. If the Newton polygon does not reduce to a single segment ${\displaystyle (\mu ,\lambda ),}$ then ${\displaystyle f}$ is reducible over ${\displaystyle K}$.

Other applications of the Newton polygon comes from the fact that a Newton Polygon is sometimes a special case of a Newton polytope, and can be used to construct asymptotic solutions of two-variable polynomial equations like ${\displaystyle 3x^{2}y^{3}-xy^{2}+2x^{2}y^{2}-x^{3}y=0.}$

This diagram shows the Newton polygon for P(x,y) = 3x² y³ − xy² + 2x²y² − x³y, with positive monomials in red and negative monomials in cyan. Faces are labelled with the limiting terms they correspond to.

In the context of a valuation, we are given certain information in the form of the valuations of elementary symmetric functions of the roots of a polynomial, and require information on the valuations of the actual roots, in an algebraic closure. This has aspects both of ramification theory and singularity theory. The valid inferences possible are to the valuations of power sums, by means of Newton's identities.

Newton polygons are named after Isaac Newton, who first described them and some of their uses in correspondence from the year 1676 addressed to Henry Oldenburg.[4]

• F-crystal
• Eisenstein's criterion
• Newton–Okounkov body
• Newton polytope

• Goss, David (1996), Basic structures of function field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 35, Berlin, New York: Springer-Verlag, doi:10.1007/978-3-642-61480-4, ISBN 978-3-540-61087-8, MR 1423131
• Gouvêa, Fernando: p-adic numbers: An introduction. Springer Verlag 1993. p. 199.

Wikimedia Commons has media related to Newton polygon.

• Applet drawing a Newton Polygon