# Explaining Newton Polygon for proving irreducibility of polynomial in $\mathbb{Z}[x]$ in elementary way

In this question of mine Proving irreduciblity over $\mathbb{Z}$ I was recommended to read Newton Polygon. Also this appears to be an interesting topic. Also I am currently studying irreducibility of polynomials and I saw somewhere that Newton Polygon provides motivation Eisenstein's irreducibility criterion. But I could not understand the content in the links. But I am in high school and my scope is uptil Olympiad level math and i dont know about Abstract Alegbra an p-adics.

So, can anyone explain what Newton Polygons are or some elementary special case of it. Any links would also be great.

I'll try to be as elementary as possible. Take $P\in \mathbb{Q}[X]$ a polynomial of degree $n\in \mathbb{N}^*$. We are interested in its decomposition in irreducible factors in $\mathbb{Q}[X]$.

## Valuation

Let $p$ be a fixed prime number. I will write $v(x)$ for the $p$-adic valuation of $x\in \mathbb{Q}$, meaning that it is the power of $p$ that appears in its prime factorisation ; note that $v(x)\geqslant 0$ if $x\in \mathbb{Z}$, but in general $v(x)$ may be negative, for instance $v(1/p^2)=-2$ (also, $v(0)=\infty$, more or less by convention).

## The Newton polygon

Now take the points in the real plane defined by $A_i = (i,v(a_i))$ for $i=0,\dots,n$, where $P=\sum a_k X^k$. If $a_i=0$ for some $i$, then $a_i$ does not appear on the plane (it is consistant with what follows to imagine that it exists as a point at infinity, but it doesn't matter). The Newton polygon of $P$ (with respect to $p$, implicitly) is the lower convex hull of these points. What does it mean ? You start with $A_0$, then take the segment from $A_0$ to some $A_i$ that has the lowest possible slope. Then you take the segment from this $A_i$ to some $A_j$ (with $j>i$) that has the lowest possible slope. You keep going until you arrive at $A_n$. You can also think of it as taking a string from below the points and pulling it upward, then see what shape it takes when you can't pull it anymore.

Now what you get is not a real polygon, but rather a broken line, made of segments having increasing slopes, starting from $A_0$ and stopping at $A_n$. It is very important to note that drawing it is completely trivial, you just have to find the exponent of $p$ in the coefficients.

Lots of authors demand that $P(0)=1$, which is always possible by dividing $P$ by an appropriate power of $X$, and then by $P(0)$. It has the effect of translating the Newton polygon so that it starts from the point $A_0 = (0,0)$. It is both harmless and mostly useless except for some calculations.

Call $P$ pure if its polygon is just one straight line (no slope changes). If $P(0)=1$, it is equivalent to the fact that $v(a_i)/i\geqslant v(a_n)/n$ for all $i>0$.

## The Newton polygon of a product

The point is the following : if $Q_1,\dots,Q_r\in \mathbb{Q}[X]$ are pure, with increasing slopes, then the Newton polygon of $P=\prod Q_i$ is the concatenation of the Newton polygon of the $Q_i$, meaning that if $Q_i$ has degree $d_i$ and its Newton polygon has slope $s_i$, then the Newton polygon is made of a segment of length $d_1$ and slope $s_1$, followed by a segment of length $d_2$ and slope $s_2$ etc.

Note that if $s_i = s_{i+1}$ then the segments "fuse" in the polygon of $P$ : the product of two pure polynomials with the same slope is pure, with still the same slope.

The proof of the above statement is an interesting but painless excercice in elementary arithmetic. I strongly encourage you to try to do it, starting with the case of two polynomials of small degree to see what happens.

## Consequences

So you can hope to use the Newton polygon of $P$ to detect factorizations. There are two drawbacks:

• You have no converse : just because there are indeed slope changes in the polygon of $P$ (ie it is not pure) does not mean that there is a corresponding decomposition as a product of pure factors.

• If $P$ has a decomposition in pure polynomials each having the same slope, it will not be detected in the Newton polygon (since they will "fuse").

### First obstruction

The first point actually has a very nice solution : you do have a decomposition in pure factors, but not in $\mathbb{Q}[X]$. You have to go find it in $\mathbb{Q}_p[X]$, with $\mathbb{Q}_p$ the field of $p$-adic numbers, which is the completion of $\mathbb{Q}$ for the $p$-adic distance, just as $\mathbb{R}$ is its completion for the ordinary distance. I will assume that $p$-adic numbers are beyond the scope of your question, but this is where stuff really happens (actually it really happens in $\mathbb{C}_p$ but this is an even more complicated field : in this field, $P$ is split, and the Newton polygon gives exactly the valuations of the roots ; this is what the Newton polygon really is about).

### Second obstruction

Now for the second point, it is almost hopeless : whatever the field you work in, the product of two pure polynomials is pure, you can't change that fact. But you can make some ad hoc observation : suppose $n$ in coprime with $v(a_n)$.

Assume that $P=QR$ with $Q,R\in\mathbb{Q}[X]$ both pure of slope $s$, and also that $P(0)=Q(0)=R(0)=1$.

Then if the degree of $Q$ is $d>1$ and if $P=\sum a_k X^k$ and $Q = \sum b_k X^k$, you get $s = v(a_n)/n = v(b_d)/d$, so $dv(a_n)$ is divisible by $n$, and since $n$ is coprime with $v(a_n)$ you get that $n$ divides $d$, so $n=d$ and $R=1$.

So in this case you can deduce that $P$ is irreducible in $\mathbb{Q}[X]$. This is where you get back to Eisenstein criterion as a special case : it states that $P$ is irreducible if $v(a_0)=1$, $v(a_i)>0$ for $0<i<n$, and $v(a_n)=0$. Then dividing $P$ by $a_0$ you get $P(0)=1$ and $v(a_n)=-1$, which is indeed coprime with $n$ (and $v(a_i)\geqslant 0$ for $0<i<n$ which ensures that $P$ is pure).

• This is a great answer, thank you for writing it! – Olivier Bégassat Feb 28 at 15:42