Editing Newton polygon

{{Short description|Tool for solving polynomial equations}}
{{Use British English|date=October 2024}}
In [[mathematics]], the '''Newton polygon''' is a tool for understanding the behaviour of [[polynomial]]s over [[local field]]s, or more generally, over ultrametric fields. 
In the original case, the ultrametric field of interest was ''essentially'' the field of [[formal Laurent series]] in the indeterminate ''X'', i.e. the [[field of fractions]] of the [[formal power series]] ring <math>K[[X]]</math>,
over <math>K</math>, where <math>K</math> was the [[real number]] or [[complex number]] field. This is still of considerable utility with respect to [[Puiseux expansion]]s. The Newton polygon is an effective device for understanding the leading terms <math>aX^r</math>
of the [[power series]] expansion solutions to equations <math>P(F(X)) = 0</math>
where <math>P</math> is a polynomial with coefficients in <math>K[X]</math>, the [[polynomial ring]]; that is, [[implicit function|implicitly defined]] [[algebraic function]]s. The exponents <math>r</math> here are certain [[rational number]]s, depending on the [[branch of a function|branch]] chosen; and the solutions themselves are power series in <math>K[[Y]]</math>
with <math>Y = X^{\frac{1}{d}}</math> for a denominator <math>d</math> corresponding to the branch. The Newton polygon gives an effective, algorithmic approach to calculating <math>d</math>.

After the introduction of the [[p-adic number]]s, it was shown that the Newton polygon is just as useful in questions of [[Ramification (mathematics)|ramification]] for local fields, and hence in [[algebraic number theory]].  Newton polygons have also been useful in the study of [[elliptic curve]]s.

==Definition==
[[Image:Newton-polygon.gif|thumb|right|Construction of the Newton polygon of the polynomial 1 + 5 ''X'' + 1/5 ''X''{{sup|2}} + 35 ''X''{{sup|3}} + 25 ''X''{{sup|5}} + 625 ''X''{{sup|6}} 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 <math>K</math> be a [[Field (mathematics)|field]] endowed with a non-archimedean [[valuation (algebra)|valuation]] <math>v_K: K \to \mathbb R\cup \{ \infty \}</math>, and let

:<math>f(x) = a_nx^n + \cdots + a_1x + a_0 \in K[x],</math>
with <math>a_0 a_n \ne 0</math>.  Then the Newton polygon of <math>f</math> is defined to be the lower boundary of the [[convex hull]] of the set of points <math>P_i=\left(i,v_K(a_i)\right),</math> 
ignoring the points with <math>a_i = 0</math>.

Restated geometrically, plot all of these points ''P''<sub>''i''</sub> on the ''xy''-plane. Let's assume that the points indices increase from left to right (''P''<sub>''0''</sub> is the leftmost point, ''P''<sub>''n''</sub> is the rightmost point). Then, starting at ''P''<sub>0</sub>, draw a [[ray (geometry)|ray]] straight down parallel with the ''y''-axis, and rotate this ray counter-clockwise until it hits the point ''P''<sub>k<sub>1</sub></sub> (not necessarily ''P''<sub>1</sub>). Break the ray here. Now draw a second ray from ''P''<sub>k<sub>1</sub></sub> straight down parallel with the ''y''-axis, and rotate this ray counter-clockwise until it hits the point ''P''<sub>k<sub>2</sub></sub>. Continue until the process reaches the point ''P''<sub>''n''</sub>;  the resulting polygon (containing the points ''P''<sub>0</sub>, ''P''<sub>k<sub>1</sub></sub>, ''P''<sub>k<sub>2</sub></sub>, ..., ''P''<sub>k<sub>m</sub></sub>, ''P''<sub>''n''</sub>) is the Newton polygon.

Another, perhaps more intuitive way to view this process is this : consider a rubber band surrounding all the points ''P''<sub>0</sub>, ..., ''P''<sub>n</sub>. 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.

== Main theorem ==
With the notations in the previous section, the main result concerning the Newton polygon is the following theorem,<ref>For an interesting demonstration based on hyperfields, see Matthew Baker, Oliver Lorscheid, (2021). ''Descartes' rule of signs, Newton polygons, and polynomials over hyperfields''.Journal of Algebra, Volume 569, p. 416-441.</ref> which states that the valuation of the roots of <math>f</math> are entirely determined by its Newton polygon:

Let  <math>\mu_1, \mu_2, \ldots, \mu_r</math>
be the slopes of the line segments of the Newton polygon of <math>f(x)</math> (as defined above) arranged in increasing order, and let
<math>\lambda_1, \lambda_2, \ldots, \lambda_r</math>
be the corresponding lengths of the [[line segment]]s projected onto the x-axis (i.e. if we have a line segment stretching between the points <math>P_i</math> and <math>P_j</math> then the length is <math>j-i</math>).

* The <math>\mu_i</math> are distinct;
* <math>\sum_i \lambda_i = n</math>;
* if <math>\alpha</math> is a root of <math>f</math> in <math>K</math>, <math>v(\alpha) \in \{-\mu_1, \ldots , -\mu_r\}</math>;
* for every <math>i</math>, the number of roots of <math>f</math> whose valuations are equal to <math>-\mu_i</math> (counting multiplicities) is at most <math>\lambda_i</math>, with equality if <math>f</math> splits into the product of linear factors over <math>K</math>.

== Corollaries and applications<span class="anchor" id="Applications"></span> ==

With the notation of the previous sections, we denote, in what follows, by <math>L</math> the splitting field of <math>f</math> over <math>K</math>, and by <math>v_L</math> an extension of <math>v_K</math> to <math>L</math>.

Newton polygon theorem is often used to show the irreducibility of polynomials, as in the next corollary for example:
* ''Suppose that the valuation <math>v</math> is discrete and normalized, and that the Newton polynomial of <math>f</math> contains only one segment whose slope is <math>\mu</math> and projection on the x-axis is <math>\lambda</math>. If <math>\mu = a/n</math>, with <math>a</math> coprime to <math>n</math>, then <math>f</math> is irreducible over <math>K</math>. In particular, since the Newton polygon of an Eisenstein polynomial  consists of a single segment of slope <math>-\frac{1}{n}</math> connecting <math>(0,1)</math> and <math> (n,0)</math>, [[Eisenstein criterion]] follows.''
   
Indeed, by the main theorem, if <math>\alpha</math> is a root of <math>f</math>, <math>v_L(\alpha) = -a/n.</math> 
If <math>f</math> were not irreducible over <math>K</math>, then the degree <math>d</math> of <math>\alpha</math> would be <math>< n </math>, and there would hold <math>v_L(\alpha) \in {1\over d}\mathbb Z</math>. But this is impossible since <math>v_L(\alpha) = -a/n</math> with <math>a</math> coprime {{nobr|to <math>n</math>}}.

Another simple corollary is the following:

* ''Assume that <math>(K, v_K)</math> is [[Henselian ring|Henselian]]. If the Newton polygon of <math>f</math> fulfills <math>\lambda_i = 1</math> for some <math>i</math>,  then <math>f</math> has a root in <math>K</math>.''

''Proof:'' By the main theorem, <math>f</math> must have a single root <math>\alpha</math> whose valuation is <math>v_L(\alpha) = -\mu_i.</math> In particular, <math>\alpha</math> is separable over <math>K</math>. 
If <math>\alpha</math> does not belong to <math>K</math>, <math>\alpha</math> has a distinct Galois conjugate <math>\alpha'</math> over <math>K</math>, with <math>v_L(\alpha') = v_L(\alpha)</math>,<ref>Recall that in Henselian rings, any valuation extends uniquely to every algebraic extension of the base field. Hence <math>v_K</math> extends uniquely to <math>v_L</math>. But <math>v_L\circ \sigma</math> is an extension of <math>v_K</math> for every automorphism <math>\sigma</math> of <math>L</math>, therefore <math>v_L(\alpha') = v_L\circ \sigma (\alpha) = v_L(\alpha).</math></ref> and <math>\alpha'</math> is a root of <math>f</math>, a contradiction.

More generally, the following factorization theorem holds:

* ''Assume that <math>(K, v_K)</math> is [[Henselian ring|Henselian]]. Then <math>f = A\,f_1\, f_2\cdots f_r,</math>, where <math>A\in K</math>, <math>f_i\in K[X]</math> is monic for every <math>i</math>, the roots of <math>f_i</math> are of valuation <math>-\mu_i </math>, and <math>\deg(f_i) = \lambda_i</math>.''<ref> J. W. S. Cassels, Local Fields, Chap. 6, thm. 3.1.</ref> 
:''Moreover, <math>\mu_i =  v_K(f_i(0))/\lambda_i</math>, and if <math>v_K(f_i(0))</math> is coprime to <math>\lambda_i</math>, <math>f_i</math> is irreducible over <math>K</math>.'' 

''Proof:''
For every <math>i</math>, denote by <math>f_i</math> the product of the monomials <math>(X - \alpha)</math> such that <math>\alpha</math> is a root of <math>f</math> and <math>v_L(\alpha) = -\mu_i</math>. We also denote <math>f = A P_1^{k_1}P_2^{k_2}\cdots P_s^{k_s}</math> the factorization of <math>f </math> in <math>K[X]</math> into prime monic factors <math>(A\in K).</math>
Let <math>\alpha</math> be a root of <math>f_i</math>. We can assume that <math>P_1</math> is the minimal polynomial of <math>\alpha</math> over <math>K</math>. 
If <math>\alpha'</math> is a root of <math>P_1</math>, there exists a K-automorphism <math>\sigma</math> of <math>L</math> that sends <math>\alpha</math> to <math>\alpha'</math>, and we have <math>v_L(\sigma \alpha) = v_L(\alpha)</math> since <math>K</math> is Henselian. Therefore <math>\alpha'</math> is also a root of <math>f_i</math>.
Moreover, every root of <math>P_1</math> of multiplicity <math>\nu</math> is clearly a root of <math> f_i</math> of multiplicity <math>k_1\nu</math>, since repeated roots share obviously the same valuation. This shows that <math>P_1^{k_1}</math> divides <math> f_i.</math>
Let <math>g_i = f_i/P_1^{k_1}</math>. Choose a root <math>\beta </math> of <math>g_i</math>. Notice that the roots of <math>g_i</math> are distinct from the roots of <math>P_1</math>. Repeat the previous argument with the minimal polynomial of <math>\beta</math> over <math>K</math>, assumed w.l.g. to be <math>P_2</math>, to show that <math>P_2^{k_2}</math> divides <math> g_i</math>. 
Continuing this process until all the roots of <math>f_i</math> are exhausted, one eventually arrives to 
<math>f_i = P_1^{k_1}\cdots P_m^{k_m}</math>, with <math>m \leq s</math>. This shows that <math>f_i\in K[X]</math>, <math>f_i</math> monic.   
But the <math>f_i</math> are coprime since their roots have distinct valuations. Hence clearly <math>f = A f_1\cdot f_2\cdots f_r</math>, showing the main contention.
The fact that <math>\lambda_i = \deg(f_i)</math> follows from the main theorem, and so does the fact that <math>\mu_i =  v_K(f_i(0))/\lambda_i</math>, by remarking that the Newton polygon of <math>f_i</math> can have only one segment joining <math>(0,  v_K(f_i(0))</math> to <math>(\lambda_i, 0 = v_K(1))</math>. The condition for the irreducibility of <math>f_i</math> 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 <math>(K, v_K)</math> is [[Henselian ring|Henselian]]. If the Newton polygon does not reduce to a single segment <math>(\mu, \lambda),</math> then <math>f</math> is reducible over <math>K</math>.'' 
  

 [[Image:Diagram_of_a_Newton_Polygon_Convex_hull.svg|thumb|right| The Newton polygon for {{nowrap|1= 3''x''<sup>2</sup> ''y''<sup>3</sup> − ''xy''<sup>2</sup> + 2''x''<sup>2</sup>''y''<sup>2</sup> − ''x''<sup>3</sup>''y''}} with positive monomials in red and negative monomials in cyan. Faces are labelled with their limiting terms.
]]
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 
<math>  3 x^2 y^3 - x y^2 + 2 x^2 y^2 - x^3 y = 0. </math>

==Symmetric function explanation==
In the context of a valuation, we are given certain information in the form of the valuations of [[elementary symmetric function]]s 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 sum symmetric polynomial|power sums]], by means of [[Newton's identities]].

== History==
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]].<ref>[[Egbert Brieskorn]], [[Horst Knörrer]] (1986). ''Plane Algebraic Curves'', pp. 370–383.</ref>

==See also==

*[[F-crystal]]
*[[Eisenstein's criterion]]
*[[Newton–Okounkov body]]
*[[Newton polytope]]

==References==
{{reflist}}
* {{Citation | last=Goss | first=David | title=Basic structures of function field arithmetic | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] | isbn=978-3-540-61087-8 |mr=1423131 | year=1996 | volume=35 | doi=10.1007/978-3-642-61480-4}}
* [[Fernando Q. Gouvêa|Gouvêa, Fernando]]: p-adic numbers: An introduction. Springer Verlag 1993. p.&nbsp;199.

== External links ==
{{Commons category|Newton polygon}}
* [http://www.math.sc.edu/~filaseta/newton/newton.html Applet drawing a Newton Polygon]

{{Isaac Newton}}

[[Category:Algebraic number theory]]
[[Category:Symmetric functions]]
[[Category:Isaac Newton]]