Newton polygons

30 Nov, 2024

This post is on one of my favourite tools in number theory: Newton polygons. I think this topic is an excellent vehicle for introducing a lot of the ideas that are at the heart of algebraic number theory. To this day, I still find Newton polygons to be one of the most magical phenomena in mathematics: with just a simple picture, Newton polygons give you profound insights into what numbers are really doing. Without further ado, let's get started!

Figure 1: a polygonal Newton (not actually what this post is about).

Main question

The problem that Newton polygons help us understand is the following: if I give you a number $x$ , can you tell me how divisible by $2$ $x$ is? Or more generally¹, for any prime number $p$ can you tell me how divisible by $p$ $x$ is?

For small examples we can do this by inspection: $40$ is divisible by $2$ exactly $3$ times ( $40 = 2^{3} \cdot 5$ ). For larger integer examples you can bust out the Euclidean algorithm. For integer values of $x$ , the fundamental theorem of arithmetic is what guarantees for us that there is a well-defined answer, since $x$ factors in a unique way as a product of powers of prime numbers.

The place that things start to get interesting is when we consider non-integer values of $x$ . How divisible by $2$ is $\sqrt{8}$ ? What about for a rational number like $\frac{3}{16}$ ? A more complicated irrational number like $4 + 6 \sqrt{2}$ ? Complex numbers like $1 + i$ ? Real numbers like $π$ ? And moreover, what should this even mean when we start working with non-integer values of $x$ since we don't have the fundamental theorem of arithmetic telling us that the answer is well-defined. For some of these examples you can provide a convincing answer.

Claim: I claim that $\sqrt{8}$ is be divisible by $2$ exactly $\frac{3}{2}$ times.

Proof 1: taking square roots is dividing exponents by $2$ , so we divide the exponent of $2$ in $8 = 2^{3}$ by $2$ to get $\frac{3}{2}$ .

Proof 2: from a different angle, $\sqrt{8} \cdot \sqrt{8} = 8 = 2^{3}$ is divisible by $2$ a total of $3$ times. Since each $\sqrt{8}$ should contribute the same amount to the divisibility by $2$ of $8$ , we get $\frac{3}{2}$ .

You can employ similar thinking to convince yourself of the correct values for the next 3 examples I mentioned (give it a try!). But what about $π$ ? The same techniques don't work because the strategies for the other numbers revolve around reducing the problem to one about integers, which isn't something you can do with $π$ .

This example shows pretty convincingly that we should allow fractional answers when we start working with non-integer values of $x$ . To help guide our thinking it is useful at this point to come up with a more precise statement of what it should mean that a non-integer $x$ is divisible by $2$ by some amount. The language that is useful for this is valuations.

Valuations

Definition: the $2$ -adic valuation function ${val}_{2}$ is the function from integers to integers which takes in an integer $x$ and outputs the number of times $k$ that $x$ is divisible by $2$ . In other words, $x = 2^{k} y$ for some integer $y$ which isn't divisible by $2$ .

This function will be useful to us in the following ways:

The function ${val}_{2}$ has a bunch of properties that encode what it means for a number to be divisible by $2$ .
We can re-frame our original question to the following: how can we compute ${val}_{2} (x)$ ?
To answer this question for non-integer values $x$ we want to extend the domain of ${val}_{2}$ to accept non-integer inputs, while preserving the properties that make ${val}_{2}$ meaningfully compute "divisibility by 2".

Here are the important properties of ${val}_{2}$ , which I'll label as V1, V2, V3.²

V1: for integers $x$ and $y$ , ${val}_{2} (x y) = {val}_{2} (x) + {val}_{2} (y)$ .
V2: for integers $x$ and $y$ , ${val}_{2} (x + y) \geq min ({val}_{2} (x), {val}_{2} (y))$ . Moreover, if ${val}_{2} (x) \neq {val}_{2} (y)$ , then ${val}_{2} (x + y) = min ({val}_{2} (x), {val}_{2} (y))$ (we'll call this second part V2-strong when we need to reference it specifically).
V3: by convention ${val}_{2} (0) = \infty$ , and $0$ is the only number with an infinite valuation.

With this language of valuations set up, we can provide a precise answer for what "how divisible is $x$ by $2$ " mean for non-integer values of $x$ : the answer should be a value $ν_{2} (x)$ for some function $ν_{2}$ which

agrees with the usual ${val}_{2}$ for integer inputs,
has a domain containing the non-integer $x$ ,
and satisfies properties V1, V2, V3.

Returning to our examples from before, we can see that the relationships our non-integers have with integers let us establish conclusively what these values $ν_{2} (x)$ would have to be just based on the properties V1, V2(-strong), and V3, without ever actually needing to construct the function $ν_{2}$ .

For $\sqrt{8}$ , we can use the fact that $ν_{2}$ agrees with $\val_{2}$ on integers and property V1 to get $3 = {val}_{2} (8) = ν_{2} (8) = 2 ν_{2} (\sqrt{8})$ and from here we divide by $2$ to get $ν_{2} (\sqrt{8}) = \frac{3}{2}$ .
Use that $\frac{3}{16} \cdot 16 = 3$ has valuation $0$ and $16$ has valuation $4$ , so $ν_{2} (\frac{3}{16}) = - 4$ .
Use V2-strong: $4$ has a $2$ -adic valuation of $2$ , $6 \sqrt{2}$ has a valuation of $\frac{3}{2}$ , and since they're distinct the overall valuation is the smaller of the two, $\frac{3}{2}$ .
Figuring out the valuation of the complex number $1 + i$ is a little bit more involved; V2 itself doesn't help right away since both $1$ and $i$ have valuation $0$ (since $i^{2} = - 1$ ). The trick insight is to involve the complex conjugate $1 - i$ since that helps us move back to the world of integers. The key relations here are:

(1 + i) (1 - i) = 2 and (1 + i) + (1 - i) = 2 .

The $2$ -adic valuations of $1 \pm i$ must add to $1$ by V1, and by V2-strong rules out the case they are different since then the smaller of the two valuations would have to equal $1$ . So the $2$ -adic valuations of $1 \pm i$ must be $\frac{1}{2}$ .

Theorem (hard non-constructive algebra theorem): there exists an extension $ν_{2}$ of ${val}_{2}$ to the full set of complex numbers which satisfies the properties V1, V2, V3.³

This theorem is both good news and bad news. Good news, in that it tells us that no matter how complicated our number looks, we can assign a sensible $2$ -adic valuation to it The bad news is actually sort of the same thing, and it is sort of hidden in the epithet I've given the theorem: sometimes there are too many choices! For any real number $r$ that you pick, there's infinitely many different valuations with $ν_{2} (π) = r$ . So for $π$ , there's no "true" $2$ -adic valuation; it could be anything, depending on which extension $ν_{2}$ you pick.

But we saw before that for numbers like $4 + 6 \sqrt{2}$ and $1 + i$ the properties V1, V2, V3 do determine the $2$ -adic valuation uniquely. The key difference here is that all of these numbers are algebraic, i.e. they are roots of polynomials with integer coefficients, whereas $π$ is transcendental, it is not the root of any polynomial with integer coefficients.

This is where Newton polygons enter the picture: for algebraic numbers we've thus far been figuring out the valuations with an ad hoc process that relies on properties V1, V2, V3. Newton polygons give us a slick way to compute valuations of algebraic numbers just by drawing a simple picture based on the polynomial that they're a root of.

Newton polygons

Take a polynomial $f (x)$ with rational coefficients. Let's write

f (x) = a_{0} + a_{1} x + \dots + a_{n} x^{n}

and assume that $a_{0} \neq 0$ ( $f (x)$ isn't divisible by $x$ ) and $a_{n} \neq 0$ ( $f (x)$ has degree $n$ ).

For a prime number $p$ , the $p$ -adic Newton polygon is formed as follows:

plot the points $(i, {val}_{p} (a_{i}))$ in the plane;
form their "lower convex hull", i.e. imagine pulling a string taut against those points from below;
the resulting set of line segments stretching from $x = 0$ to $x = n$ are called the $p$ -adic Newton polygon of $f$ .

Figure 2: forming the $2$ -adic Newton polygon of $32 + 8 x + 8 x^{2} + 2 x^{3} + 4 x^{4} + x^{5} .$

The term "polygon" is a bit of a misnomer here, since we're really working work with just a set of line segments rather than a polygon in the traditional sense.

Why are we doing this? It is instructive to work through what is going on in the case of a general quadratic polynomial. Let's assume that $f (x)$ is monic, and has two roots $α$ and $β$ . Thus we have that

f (x) = a_{0} + a_{1} x + x^{2} = (x - α) (x - β) .

For some $ν_{p}$ which extends ${val}_{p}$ let's say that $ν_{p} (α) = λ$ and $ν_{p} (β) = μ$ .

What can we say about the Newton polygon of $f (x)$ ? No matter what we'll have that

{val}_{p} (a_{0}) = ν_{p} (α β) = λ + μ .

Since $- a_{1} = α + β$ , in general we can only guarantee that

{val}_{p} (a_{1}) = ν_{p} (α + β) \geq min (λ, μ)

using property V2 of $ν_{p}$ . There's really only two cases to consider here: either $λ \neq μ$ in which case the strong form of V2 applies and we know ${val}_{p} (a_{1})$ exactly, or $λ = μ$ in which case we just have the inequality above.

In the $λ \neq μ$ case we can read off the valuations $λ$ and $μ$ as the negatives of the slopes of the two-segment Newton polygon; in the $λ = μ$ case the inequality implies that the point at $x = 1$ lies on or above the line connecting the $x = 0$ and $x = 2$ points, giving a Newton polygon with a single segment of horizontal length 2 and slope the negative of $λ = μ$ .

You could (and it is instructive!) to think through a similar analysis for cubic polynomials, to get a feel for what goes on in the general case. Here's the full theorem relating Newton polygons and valuations of roots of polynomials.

Theorem: the $p$ -adic valuations of the roots of a rational polynomial $f (x)$ are equal to the negatives of the slopes of the $p$ -adic Newton polygon of $f (x)$ (counted with multiplicity according to the horizontal length of the Newton polygon segments).

Proof: In principle we could prove this the same way that we handled the cubic case above, with a lot of careful bookkeeping.

Let's instead formulate the proof this way: there are two polygons we could draw given the polynomial $f (x)$ . One is the $p$ -adic Newton polygon, based on the valuations of the coefficients of $f (x)$ . The second is the polygon with the property that we want: the slopes of this polygon will be the negatives of the $p$ -adic valuations of the roots of $f (x)$ .

For simplicity let us assume that $f (x)$ is monic (i.e. if it has degree $n$ , the coefficient $a_{n}$ of $x^{n}$ is equal to $1$ , we can also divide out by $a_{n}$ to arrange this, which doesn't change the set of roots or the slopes of the Newton polygon). This will let us line up the valuation polygon vertically with the Newton polygon. Let's say that the roots of $f (x)$ are $α_{1}, \dots, α_{n}$ , with If the roots of $f (x)$ have valuations $λ_{i} = ν_{p} (α_{i})$ , we'll order the roots to ensure that

λ_{1} \geq λ_{2} \geq . . . λ_{n}

To form the valuation polygon, draw the lines segments connecting the points $(i, \sum_{j = i + 1}^{n} λ_{j})$ . Notice that this makes the valuation polygon:

start at $(0, λ_{1} + \dots + λ_{n})$ and end at $(n, 0)$ ,
have slope $- λ_{i}$ between the $x$ values $i - 1$ and $i$ ,
and by our ordering of the $λ_{i}$ the slopes increase from left to right.

To prove that this valuation polygon is equal to the Newton polygon we'll prove two things: the points plotted to make the Newton polygon lie on or above the points plotted to make the valuation polygon, and these points agree wherever there's a change in slope of the valuation polygon. Since in both cases the slopes increase from left to right, this implies that they are equal.

To prove that the points making up the Newton polygon are above the corresponding points in the valuation polygon, we need to prove that ${val}_{p} (a_{k}) \geq λ_{n - k + 1} + \dots + λ_{n}$ for each $k = 0, \dots, n$ . We know that $a_{k}$ is the sum over all possible products of $k$ of the roots of $f (x)$ , i.e.

a_{k} = \sum_{1 \leq i_{1} < \dots < i_{k} \leq n} α_{i_{1}} \dots α_{i_{k}}

We can just compute the valuation of this using valuation axioms V1 and V2! We can guarantee that the term $α_{n - k + 1} \dots α_{n}$ has valuation smaller than or equal to all other terms by the ordering of the roots, so we get that

{val}_{p} (a_{k}) \geq ν_{p} (α_{n - k + 1} \dots α_{n}) = λ_{n - k + 1} + \dots + λ_{n} .

Moreover if this is an index where the slope of the valuation polygon changes, i.e. $λ_{n - k} \neq λ_{n - k + 1}$ , then we are guaranteed that the term $α_{n - k + 1} \dots α_{n}$ has strictly smaller valuation than all other terms in the sum making up $a_{k}$ . Applying the strong form of V2 gives that

{val}_{p} (a_{k}) = λ_{n - k + 1} + \dots + λ_{n}

at these indices, i.e. the vertices of the Newton and valuation polygons agree here.

Wrap up

So there you have it! For any algebraic number we can figure out how divisible it is by a given prime $p$ : find the polynomial $f (x)$ it is a root of, draw the $p$ -adic Newton polygon of $f$ , and read off the (negatives of the) slopes of the polygon. No matter what valuation $ν_{p}$ we've chosen to extend ${val}_{p}$ , the valuation of our root is (the negative of) one of those slopes, and the Newton polygon itself doesn't need to know anything about $ν_{p}$ . This is magical. In the words of one of my Mathcamp students: Newton polygons are OP.

There's a subtlety still remaining: the Newton polygon tells us the set of valuations that the roots of a polynomial have, but it can't in general tell us which root has which valuation. In fact this is to be expected, since different extensions of ${val}_{p}$ will permute which of the possible valuations the roots get!

In the next post, I'll talk about this bigger picture of this world of valuations, and we'll give some really slick proofs of cool theorems using Newton polygons.

I'm using $p = 2$ to keep things concrete for much of this post, but everything works the same for a general prime number $p$ .↩
These properties break down when you try to use them for divisibility by $n$ for non-primes $n$ , which is why we restrict to primes when talking about valuations.↩
Proving that valuations extend to the complex numbers is well beyond what I want to do in this post, but here's the brief idea if you have a bit of background. The $p$ -adic valuation extends from $ℤ$ in a unique to all algebraic extensions of the $p$ -adic numbers $ℚ_{p}$ , and hence also to the algebraic closure ${\overset{―}{ℚ}}_{p}$ . By continuity, that valuation also extends to the complex $p$ -adics $ℂ_{p}$ . Since the complex numbers $ℂ$ are abstractly isomorphic to the complex $p$ -adics $ℂ_{p}$ (they are algebraically closed fields of the same cardinality and characteristic), you can pick such an isomorphism and use it to "compute" valuations of complex numbers.↩