Maximal Orders and Decomposition II
Newton Polygon Methods for Prime Decomposition
Using Newton polygons to decompose primes locally, handling the cases where factoring modulo p is insufficient.
Engineering / MathematicsMaximal Orders and Decomposition II2 min readKV-MATH-0615
Newton polygon methods decompose a prime by working in the local field at that prime, reading structure off the polygon rather than performing linear algebra over the whole order.
The approach
The prime decomposition of p corresponds to the factorisation of the defining polynomial over the p-adic numbers. The Newton polygon gives a first factorisation, one factor per distinct slope.
Decomposition by Newton polygon
- Build the polygonPlot coefficient indices against p-adic valuations; take the lower convex hull.
- Split by slopeDistinct slopes give distinct p-adic factors immediately.
- Read e and fThe slope denominator gives the ramification index; the residual polynomial degree gives the residue degree.
- Recurse where neededIf a residual polynomial is not separable, refine by a change of variable and repeat.
Regular and irregular cases
| Case | Condition | Handling |
|---|---|---|
| Regular | Residual polynomials separable | Decomposition read off directly |
| Irregular | Some residual polynomial not separable | Refine with a change of variable and recurse |
Comparison with the algebra-splitting route
| Aspect | Newton polygon | Buchmann-Lenstra |
|---|---|---|
| Works with | The defining polynomial locally | The order modulo p as an algebra |
| Main tool | Convex hull and residual polynomials | Linear algebra and algebra splitting |
| Scales with | Degree of the polynomial | Degree squared or cubed, from the matrices |
| Best for | High degree, high ramification | Moderate degree; conceptually simpler |
Maximal order as a by-product
The local analysis also produces the local contribution to the maximal order at that prime, so decomposition and maximality are computed together rather than sequentially as in Round 2.
Verification
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 6.2.1. 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.