Newton polygons part 2

31 Dec, 2024

In the previous post I covered Newton polygons as a way of computing valuations of algebraic numbers. Specifically: if $f(x)$ is a polynomial with rational coefficients, then the slopes of the $p$-adic Newton polygon of $f$ are the valuations of the roots of $f$ under any extension of the $p$-adic valuation function.

This time around we'll talk about cool things we can do with Newton polygons. Our focus will be on polynomials rather than numbers as in the first post, since that's where Newton polygons are more useful. In fact for "most" algebraic numbers we actually can't describe them any better than saying "it's one of the roots of this polynomial" thanks to the Abel-Ruffini theorem, so we're not really changing the setting as much as it may seem.

Factoring polynomials and Newton polygons

Theorem (join theorem): if we multiply rational coefficient polynomials $g(x)$ and $h(x)$, the $p$-adic Newton polygon of the product $f(x)=g(x)h(x)$ is the polygon with slopes the union of those of $g$ and $h$. Pictorially, the $p$-adic Newton polygon of $f$ can be formed by cutting apart the segments of the polygons of $g$ and $h$ at their vertices, ordering them by increasing slope, and joining them back along vertices.

Proof: the roots of $f$ are the union of the roots of $g$ and $h$. The fundamental theorem of Newton polygons applied to $f$ tells us that the slopes of the $p$-adic Newton polygon of $f$ are therefore the union of those of $g$ and $h$, since the $p$-adic valuations of the roots of $f$ are those of $g$ and $h$.

Taking the converse of this, we can get conditions for when and how a polynomial might factor based on its Newton polygons. Since the vertices of the Newton polygon of a polynomial with rational coefficients must occur at integer lattice points, and the Newton polygon of a product is directly assembled by joining the Newton polygons of the factors, the segments of a Newton polygon restrict factors.

Just to offer an example, suppose we have a polynomial with the following Newton polygon:

Figure 1: an example Newton polygon to discuss factoring polynomials.

Under any factorization of this polynomial, the two factors must among them have 4 roots of valuation $-\frac{3}{2}$ coming from the first two horizontal segments of length 2 of the Newton polygon. However since this segment only passes through an integer point in the middle, it cannot be the case that one factor has 3 of these roots and the other 1; they must come in pairs, since the Newton polygon of each factor must have integer lattice vertices.

More generally the constraint we make use of is the following: if a rational polynomial $f(x)$'s $p$-adic Newton polygon consists of segments of horizontal lengths ${\ell }_1,{\ell }_2,\dots ,{\ell }_k$ (where we always break segments whenever they pass through a lattice point), then any factor of $f$ with rational coefficients has $p$-adic Newton polygon assembled from a subset of these $k$ segments and in particular its degree is a sum of some subset of ${\ell }_1,\dots ,{\ell }_k$.

Eisenstein's criterion

One of the theorems that it is often covered in an undergrad abstract algebra class is Eisenstein's theorem.

Theorem (Eisenstein's criterion): if $f(x)$ is a monic polynomial with integer coefficients and there is a prime number $p$ where then $f(x)$ is irreducible.

• each coefficient of $f(x)$ other than the leading one is divisible by $p$
• the constant term of $f(x)$ is not divisible by $p^2$ (i.e. ${\text{val}}_p(a_0)=1$)

The theorem's condition might seem a bit restrictive, but in fact Eisenstein polynomials show up more often than you might expect. In addition to being useful, the standard proof is a great example of abstract algebra techniques. The basic idea: if $f$ factors as $g$ times $h$, then since $f$ reduced mod $p$ is just equal to $x^n$, $g$ and $h$ must each also be powers of $x$ when reduced mod $p$. But that means that the non-leading coefficients of $g$ and $h$ are also all divisible by $p$, and since the constant term of $f$ is the product of the constant terms of $g$ and $h$ it would have to be divisible by at least $p^2$, a contradiction. There's some details to make that fully rigorous, but the core idea of reducing mod $p$ and looking at constant terms is the blueprint for a lot of abstract algebra proofs.

There is a super slick proof of Eisenstein's criterion that one can give with Newton polygons! Let's look at the $p$-adic Newton polygon of an Eisenstein polynomial $f(x)$:

• the first vertex we plot is at height one, by the assumption that the constant term of $f(x)$ has valuation 1
• all of the other non-leading terms give us vertices of height at least 1, since those coefficients are all divisible by $p$ at least once
• the final vertex (the $n$-th if the polynomial is degree $n$) is plotted at height 0 since the polynomial is monic

This gives us a Newton polygon which is a single segment of slope $\frac{-1}{n}$. So $f(x)$ must be irreducible over the integers, since this Newton polygon can't be split up into Newton polygons of possible factors $g(x)$ and $h(x)$: there's no way to split up this single slope polygon into two polygons coming from rational coefficient polynomials.

One of the reasons this Newton polygon proof is super slick is that it generalizes super easily: if the $p$-adic Newton polygon of $f(x)$ is a single segment which doesn't pass through any lattice points (other than its endpoints), then $f$ must be irreducible!

Combining primes

A super neat culmination of using Newton polygons to examine polynomial factorization are the truncated exponential polynomials:

We'll prove that these polynomials are irreducible using Newton polygons! Unlike with Eisenstein's criterion we won't be able to get to this conclusion by using a single prime. The strategy will be to put together information from the $p$-adic Newton polygons from several primes $p$.

Let's look at all the Newton polygons for $E_6(x)$:

Figure 2: the Newton polygons of $E_6(x)$.

In words these are

• for primes $p>5$ the Newton polygons are straight horizontal segments of length 6, as the coefficients are just (reciprocals of) factorials up to $6!$, so the only primes dividing the coefficients are $2,3,5$
• the $2$-adic Newton polygon of $E_6$ has a segment of slope $-\frac{3}{4}$ and length 4, and a segment of slope $-\frac{1}{2}$ and length 2
• the $3$-adic Newton polygon of $E_6$ has 2 segments of slope $-\frac{1}{3}$ and length 3
• the $5$-adic Newton polygon of $E_6$ has a segment of slope $-\frac{1}{5}$ and a segment of slope 0

The $2$-adic polygon alone tells us that the best we can hope for is factors of degree $4$ and $2$, the $3$-adic polygon tells us that the best we could get is two factors of degree $3$, and the $5$-adic polygon gives at best factorization into degrees $5$ and $1$. Given all these constraints in this case it is clear the only possibility is that $E_6(x)$ is irreducible.

How to attack this problem generally? Let's do a bigger example: $E_{12}(x)$. The relevant primes are $2,3,5,7,11$; the Newton polygons for all larger primes are horizontal.

Figure 3: the Newton polygons of $E_{12}(x)$.

It's no longer true in this example that we can combine information from any two of these primes: looking at just the $5$- and $7$-adic Newton polygons, we can't rule out a factorization of $E_{12}(x)$ into degree $5$ and $7$ pieces, because the trailing horizontal parts of the polygon give us wiggle room in possible factorizations.

We can however, deduce irreducibility of $E_{12}(x)$ from just the $2$- and $3$-adic Newton polygons. Again Notice that $2$ and $3$ are exactly the primes which divide $12$!¹ The useful reframing here is that since every segment of the $2$-adic Newton polygon has length divisible by $4$ (which exactly divides $12$), we're guaranteed that in any factorization of $E_{12}(x)$ all of the factors have degree divisible by $4$. Similarly for the $3$-adic polygon and degrees being divisible by $3$. Since the degree of any factor must have degree divisible by both $3$ and $4$ it must have degree divisible by $12$. But $E_{12}(x)$ has degree $12$, so any factor must just be the whole polynomial!

This is the strategy in general: for the primes $p$ dividing $n$, we'll do some analysis of valuations of factorials to show that each segment of the $p$-adic Newton polygon has length divisible by $p^{{\text{val}}_p(n)}$, and since the degree of a hypothetical factor of $E_n(x)$ is a sum of those lengths it must have that same condition on its degree. Combining this over all primes $p$ dividing $n$ we get that any factor must have degree divisible by $n$.

The convenient way to completely describe the $p$-adic Newton polygon of $E_n(x)$ uses the base $p$ expansion of $n$. Let's say that

is that base $p$ expansion, meaning that each $c_i$ is between $0$ and $p-1$. Then the $p$-adic Newton polygon expansion of $E_n(x)$ consists of

• a total of $c_0+c_1+\dots +c_k$ segments,
• for each $i$ there are $c_i$ segments of horizontal length $p^i$, each of which has slope $-\frac{1+p+\dots +p^{i-1}}{p^i}$.

In particular, if $p$ divides $n$ then every segment of the $p$-adic Newton polygon of $E_n(x)$ has length which is a multiple of $p$.

Wrap up

I want to leave you with a little teaser about where things can go from here. I started this post with the "join theorem" which tells us how to build the Newton polygon of a product from those of the factors. Is there a converse to this? In other words, if you can decompose the Newton polygon into segments with integer lattice endpoints, can you always factor the starting polynomial into polynomials having those segments as their Newton polygons?

The answer turns out to be yes, if you work over the $p$-adic numbers! Proving this is outside of what I want to do in this post though, so it will have to wait for another one.

Lest you think that Newton polygons are a magic solution for everything let me leave you with a glimpse of what they can't do in algebraic number theory. For a rational number $n$, knowing the ${\text{val}}_p(n)$ for all primes $p$ determines it almost completely. The only additional piece of information you need is if $n$ is positive or negative. For an algebraic number one can compute its valuation (assuming we know it's minimal polynomial, and modulo the caveats from last time of picking extensions of valuations), but that turns out to be pretty far from determining the number completely. This is because of units: algebraic numbers whose valuation is $0$ at every prime (really at every finite place to use the more precise terminology). Units are interesting as they are the algebraic numbers which are algebraic integers (their monic minimal polynomial has integer rather than rational coefficients) whose multiplicative inverses are also algebraic integers. In the regular integers $\pm 1$ are the only units, but there are lots and lots of units out there in the wild, and valuations don't (directly) give us any way to get a hold on them.

More coming soon!