Polynomial Factorisation
p-adic Root Finding and Newton Polygons
Finding roots in p-adic fields by lifting, and reading ramification structure off the Newton polygon of a polynomial.
Engineering / MathematicsPolynomial Factorisation2 min readKV-MATH-0572
The Newton polygon encodes the valuations of the roots of a polynomial directly from its coefficients. It is the standard tool for understanding local behaviour at a prime, and it drives the hardest cases of prime decomposition.
Construction
Plot a point for each coefficient at its degree and its valuation, then take the lower convex hull. The polygon's segments carry the information.
Constructing the Newton polygon
- PlotFor each non-zero coefficient, plot the index against the p-adic valuation of that coefficient.
- HullTake the lower convex hull of the plotted points.
- Read segmentsEach segment has a slope and a horizontal length.
What it tells you
| Polygon feature | Meaning |
|---|---|
| A single segment of slope zero | All roots are units; the polynomial is unramified in this respect |
| Several distinct slopes | The polynomial factors over the p-adic field, one factor per segment |
| A slope with denominator e in lowest terms | Ramification of index at least e |
| Slope zero segment of length one | A simple unit root; lifts by Hensel |
p-adic root finding
A simple root modulo p lifts uniquely to a p-adic root by Hensel lifting, which is Newton iteration in the p-adic metric. The condition is that the derivative does not vanish at the root modulo p.
Use in prime decomposition
Decomposing a prime that divides the index cannot be done by simple factorisation modulo p. Newton polygon methods handle these cases by working locally, and are one of the two standard approaches — the other being the Buchmann-Lenstra method. See Newton polygon methods for decomposition.
Regular polygons and recursion
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.6.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.