%\input{preamble.tex}
\unittitle{Newton polygons}

In this unit, we then review the theory of Newton polygons for polynomials over fields with 
valuations. In the process of doing this, we will also generalize to
polynomials twisted by a differential operator.

\section{Slopes and Newton polygons}

A \emph{normed differential field} is a field $F$ equipped with an absolute value
$|\cdot|_F$ and a derivation $d$ which is bounded as a linear operator on $F$
over $F_0 = \ker(d)$. If the absolute value is nonarchimedean, corresponding to a
valuation $v$, this means that the quantity
\[
r_0 = \min_{f \in F^\times} \{v(d(f)) - v(f)\}
\]
is finite. We'll abbreviate ``nonarchimedean normed differential field'' to
``nonarchimedean differential field''.

Let $F$ be a nonarchimedean differential field.
Let $P(T) = \sum_{i=0}^n P_i T^i$ be a twisted polynomial
of degree $n$ over $F$. Draw the points in $\RR^2$ given by
\[
\{(-i, v(f_i)): i= 0,\dots,n, P_i \neq 0\}.
\]
Then form the lower convex hull of these points, i.e., take the intersection
of every closed halfplane lying above some nonvertical line containing all the
points. The boundary of this region is called the \emph{Newton polygon} of
$P$.

Another way to represent the same data is to form the multiset consisting of
the slopes of the polygon, each occurring with multiplicity equal to the
width of the corresponding segment. The total cardinality is at most $n$,
with equality if and only if $P_0 \neq 0$; in case of a shortfall, we 
conventionally put in $+\infty$ as a slope with the missing multiplicity.
This gives the \emph{slope multiset (multiset of slopes)} of the twisted polynomial.

Keep in mind that we may take $d=0$, in which case $r_0 = +\infty$; 
this gives the usual Newton polygon
of an untwisted polynomial.
A key example with $d \neq 0$ will be the case
$F = \CC((z))$ with the $z$-adic valuation and $d = z \frac{d}{dz}$; 
in this case, $r_0 = 0$.

\section{The multiplicativity property}

For untwisted polynomials, it was known to Newton (in the case $F = \CC((z))$)
that for $P,Q \in F[T]$, the slope multiset of $PQ$ is the union
of the slope multisets of $P$ and $Q$.
For twisted polynomials, this is only partly true; we must account
for the extent the derivation disturbs absolute
values, as measured by $r_0$.

To do this, it is convenient to use yet another representation of the data
contained in the Newton polygon. For $r \in \RR$, define the 
\emph{sloped valuation function} $v_r$ on $F\{T\}$ as
\[
v_r\left( \sum_i P_i T^i\right)
= \min_i \{v(P_i) + ri\}.
\]
That is, $v_r$ is the $y$-intercept of the supporting line of the
Newton polygon of slope $r$. Note that for $P \in F\{T\}$,
the function $r \mapsto v_r(P)$ is continuous.

\begin{prop}[Robba] \label{P:robba}
For $r \leq r_0$ and $P,Q \in F\{T\}$, we have
$v_r(PQ) = v_r(P) + v_r(Q)$.
\end{prop}
\begin{proof}
By the continuity of $r \mapsto v_r(*)$, it suffices to check the
claim for $r < r_0$.
Write $P = \sum_i P_i T^i$ and $Q = \sum_j Q_j T^j$; then 
\[
PQ = \sum_k \left( \sum_{i+j=k} \sum_{h\geq 0}
\binom{i+h}{h} P_{i+h} d^h(Q_j) \right) T^k,
\]
and hence
\begin{equation} \label{eq:Newton slope}
\begin{split}
v_r(PQ) &\geq \min_{h,i,j} \{ v(P_{i+h}) + v(b_j) + r(i+j) + (v(d^h(Q_j)) - v(Q_j))\} \\
&\geq \min_{h,i,j} \{ v(P_{i+h}) + v(Q_j) + r(i+j) + h r_0 \} \\
&\geq \min_{h,i,j} \{ v(P_{i+h}) + v(Q_j) + r(i+h+j)\}.
\end{split}
\end{equation}
This immediately yields $v_r(PQ) \geq v_r(P) + v_r(Q)$. To  establish 
equality, 
let $i_0$ and $j_0$ be the smallest values of $i$ and $j$
which minimize 
$ri + v(P_i)$ and $rj + v(Q_j)$, respectively; then \eqref{eq:Newton slope}
achieves its minimum for $h=0, i = i_0, j=j_0$ but not for any other
$h,i,j$ with $i+j = i_0 + j_0$. Hence $v_r(PQ) = v_r(P) + v_r(Q)$.
\end{proof}
\begin{cor} \label{C:multi}
For $r < r_0$, the multiplicity of $r$ as a slope of $PQ$ is the sum of 
the multiplicities of $r$ as a slope of $P$ and $Q$.
\end{cor}
\begin{proof}
This follows from Proposition~\ref{P:robba} and the fact that
the left and right endpoints of the segment of slope $r$ in the
Newton polygon are the points where the support lines of slightly smaller
and slightly larger slope, respectively, touch the polygon. (Note
that this means that we cannot deduce the same conclusion for $r=r_0$; see
exercises.)
\end{proof}
\begin{cor} \label{C:slopes roots}
Suppose $P$ factors as $(T-c_1)\cdots(T - c_n)$ where $v(c_i) < r_0$
for $i=1,\dots,n$. Then the slopes of $P$ are $v(c_1), \dots, v(c_n)$;
that is, the  Newton polygon computes the valuations of the roots of $P$
(counted with multiplicity).
\end{cor}

Note that one can also prove multiplicativity using the following
property.
\begin{prop} \label{P:twisted adjoint}
The Newton polygon of any twisted polynomial and its formal adjoint
have the same multiplicities for slopes less than $r_0$.
\end{prop}
\begin{proof}
Exercise. (This can also be easily deduced \emph{a posteriori}
using Proposition~\ref{P:diff factor} below.)
\end{proof}

In the other direction, one gets good behavior of $v_r$ under the division
algorithm provided that you are dividing by a polynomial with all slopes
equal to $r$, and $r$ is not too large.
\begin{lemma} \label{L:divide by Gauss}
Let $P(T) \in F\{T\}$ be a polynomial whose slopes are all equal to $r < r_0$.
Let $S(T) \in F\{T\}$ be any polynomial, and write
$S = PQ + R$ with $\deg(R) < \deg(P)$. Then
\[
v_r(S) = \min\{v_r(P) + v_r(Q), v_r(R)\}.
\]
\end{lemma}
\begin{proof}
Exercise.
\end{proof}

\section{Slope factorizations (Hensel's lemma)}

When $F$ is complete for a nonarchimedean absolute value, one
has a sort of converse of Proposition~\ref{P:robba}.
\begin{prop}[Robba] \label{P:diff factor}
Let $F$ be a differential field complete for a valuation $v$.
Fix $r < r_0$ and $m \in \ZZ_{\geq 0}$.
Let $R \in F\{T\}$ be a twisted polynomial such that 
$v_r(R - T^m) > v_r(T^m)$. Then $R$ can be factored uniquely as $PQ$, where
$P \in F\{T\}$ has degree $\deg(R) - m$ and
all slopes less than
$r$, $Q \in F\{T\}$ is monic of degree $m$ and has all slopes
greater than $r$, $v_r(P - 1) > 0$, and $v_r(Q - T^m) > v_r(T^m)$.
\end{prop}
\begin{proof}
We first check existence. Define sequences $\{P_l\}, \{Q_l\}$ as follows.
Define $P_0 = 1$ and $Q_0 = T^m$. Given $P_l$ and $Q_l$, write
\[
R - P_l Q_l = \sum_i a_i T^i,
\]
then put
\[
X_l = \sum_{i \geq m} a_i T^{i-m}, \qquad
Y_l = \sum_{i < m} a_i T^i
\]
and set $P_{l+1} = P_l + X_l$, $Q_{l+1} = Q_l + Y_l$.
Put $c_l = v_r(R- P_l Q_l) - rm$, so that $c_0 > 0$.
Suppose that $v_r(P_l-1) \geq c_0$, $v_r(Q_l-T^m) \geq c_0 + rm$,
and $c_l \geq c_0$.
Then visibly $v_r(P_{l+1}-1) \geq c_0$ and $v_r(Q_{l+1}-T^m) \geq c_0 + rm$;
by Proposition~\ref{P:robba},
\begin{align*}
c_{l+1} &= v_r(R - (P_l + X_l)(Q_l + Y_l)) - rm \\
%&= v_r(R - P_l Q_l - X_l Q_l - P_l Y_l - X_l Y_l) - rm\\
&= v_r(X_l(T^m - Q_l) + (1-P_l)Y_l - X_lY_l) - rm \\
%&\geq \min\{v_r(X_l) + v_r(T^m - Q_l) 
%, v_r(1-P_l) + v_r(Y_l), v_r(X_l) + v_r(Y_l) \}  - rm \\
&\geq \min\{c_l + (c_0 +rm), c_0 + (c_l+rm) , c_l + (c_l+rm)\} - rm \\
&\geq c_l + c_0.
\end{align*}
By induction on $l$, we deduce that $c_l \geq (l+1) c_0$.
Consequently, the sequences $\{P_l\}$ and $\{Q_l\}$ converge 
under $v_r$, and their limits
$P$ and $Q$ have the desired properties.

We next check uniqueness. Suppose $R = P_1 Q_1$ is a second such factorization;
put $c = \min\{v_r(P - P_1), v_r(Q - Q_1) - v_r(T^m)\}$.
Put
\[
X = R - P_1 Q = (P - P_1)Q = P_1(Q_1 - Q),
\]
and suppose $X \neq 0$; then $v_r(X) = c + v_r(T^m)$
by Proposition~\ref{P:robba}.
Write $X = \sum b_k T^k$, and choose $k$ such that
$v_r(X) = v_r(b_k T^k)$. The equality
\[
X = (P - P_1)T^m + (P - P_1)(Q - T^m)
\]
shows that we cannot have $k < m$, while the equality
\[
X = Q_1 - Q + (P_1 - 1)(Q_1 - Q)
\]
shows that we cannot have $k \geq m$. This contradiction
forces $X=0$, proving $P = P_1, Q = Q_1$ as desired.
\end{proof}
This yields the following.
\begin{theorem} \label{T:factor}
Any monic twisted polynomial $P \in F\{T\}$ admits a unique factorization
\[
P = P_{r_1} \cdots P_{r_m} P_+
\]
for some $r_1 < \cdots < r_m < r_0$,
where each $P_{r_i}$ is monic with all slopes equal to $r_i$,
and $P_+$ is monic with all slopes at least $r_0$.
\end{theorem}
\begin{proof}
We induct on $\deg(P)$. If $P$ has all slopes at least $r_0$, we
may simply set $P_+ = P$; if $P$ has all slopes equal to some $r < r_0$,
we may set $P_r = P$. Otherwise, let $r_1$ be the least slope of $P$,
let $r_2$ be the next smallest slope, and pick $r \in (r_1,r_2)$.
Apply Proposition~\ref{P:diff factor} to $P$ and $r$, 
and call the second factor $P_{r_1}$.
Then apply the induction hypothesis to the first factor.
\end{proof}
Theorem~\ref{T:factor}
also holds with the factors in the reverse order (exercise).

\section{Another version of Hensel's lemma}

You may be more accustomed
 to thinking of Hensel's lemma as a statement about lifting
factorization of polynomials from $\FF_p$ to $\ZZ_p$. That statement
also admits a twisted analogue, also from [Rob80].
\begin{prop} \label{P:robba2}
Assume that $r_0 > 0$. Suppose $R \in \gotho_F\{T\}$
and that the reduction of $R$ modulo $\gothm_F$ factors into the product
$\overline{P} \overline{Q}$ of two coprime factors. This 
factorization then lifts to a factorization $R = PQ$ in $\gotho_F\{T\}$.
\end{prop}
\begin{proof}
Exercise.
\end{proof}

\section{Applications in the untwisted case}

We will apply the above results to differential modules 
in the next unit, but for the rest of this unit, take $d=0$.
We use the aforementioned properties of Newton polygons (which in the untwisted
case should be familiar)
to tie up the loose ends left in our earlier discussion of 
extensions of nonarchimedean absolute values. Note that $r_0 = \infty$
in the untwisted case,
so the results do not carry any restrictions on slopes.

We first check that if $F$ is a complete nonarchimedean field, then any finite
extension $E$ of $F$ admits an extension of $|\cdot|$ to an absolute value on $E$.
If $E'$ is a field intermediate between $F$ and $E$, we may first extend the
absolute value to $E'$ and then to $E$. Consequently,
it suffices to check the case where $E = F(\alpha)$ for some
$\alpha \in E$, that is, $E \cong F[T]/(P(T))$ for some monic irreducible polynomial $P
\in F[T]$
(the minimal polynomial of $\alpha$).
Apply Theorem~\ref{T:factor}; since $P(T)$ cannot factor
nontrivially, we deduce that $P$ must have a single slope $r$.
We now define an absolute value on $E$ as follows: for 
$\beta = c_0 + c_1 \alpha + \cdots + c_{n-1} \alpha^{n-1}$,
with $n = \deg(P) = [E:F]$, put
\[
|\beta|_E = \max_i \{|c_i| e^{-ri}\}.
\]
That is, take $|\beta|_E$ to be the $e^{-r}$-Gauss norm of the polynomial
$c_0 + c_1 T + \cdots + c_{n-1} T^{n-1}$. The multiplicativity
of $|\cdot|_E$ is then a consequence of Lemma~\ref{L:divide by Gauss}.

We next check that the completion $E$ of an algebraically closed nonarchimedean
field $F$ is itself algebraically closed.
Let $P(T) \in E[T]$ be a monic polynomial of degree $d$.

\begin{lemma} \label{L:small root}
With notation as above, for any $\epsilon > 0$, we can find $z \in F$
such that $|z| \leq |P(0)|^{1/d}$ and $|P(z)| < \epsilon$.
\end{lemma}
\begin{proof}
If $P(0)= 0$ we may pick $z=0$, so assume $P(0) \neq 0$.
Put $P = T^d + \sum_{i=0}^{d-1} P_i T^i$. For any $\delta>0$,
we can pick a polynomial $Q = T^d + \sum_{i=0}^{d-1} Q_i d^i \in F[T]$
with $|Q_i-P_i| < \delta$ for $i=0,\dots,d-1$.

Now assume $\delta < \min\{|P_0|, \epsilon, \epsilon/|P_0|\}$,
so that $|Q_0| = |P_0|$.
By Corollary~\ref{C:slopes roots}, we can find 
a root $z \in F$ of $Q_0$ with $|z| \leq |Q_0|^{1/d}
= |P_0|^{1/d}$. We now have
\[
|P(z)| = |(P-Q)(z)| \leq \delta \max\{1,|z|\}^d \leq
\delta \max\{1, |P(0)|\} < \epsilon,
\]
as desired.
\end{proof}

Define a sequence of polynomials $P_0, P_1,  \dots$ as follows. Put
$P_0 = P$. Given $P_i$, apply Lemma~\ref{L:small root}
to construct $z_i$
with $|z_i| \leq |P_i(0)|^{1/d}$ and $|P_i(z_i)| < 2^{-i}$,
then set $P_{i+1}(T) = P_i(T + z_i)$ so that $P_{i+1}(0) = P_i(z_i)$.
If some $P_i$ satisfies $P_i(0)= 0$, then $z_0 + \cdots + z_{i-1}$ is a
root of $P$. Otherwise, we 
get an infinite sequence $z_0, z_1, \dots$ such that $z_0 + z_1 + \cdots$
converges to a root of $P$.

\notes

Newton polygons for differential operators were considered by Dwork
and Robba [DR77, \S 6.2.3]; the first systematic treatment seems to
have been made by Robba [Rob80], and our results are taken from there.
The proofs of Proposition~\ref{P:robba} and~\ref{P:diff factor}
were self-plagiarized from [Ked07, Lemma~3.1.5 and Proposition~3.2.2].

\exercises

\begin{enumerate}
\item
Prove Proposition~\ref{P:twisted adjoint}.
\item
Prove Lemma~\ref{L:divide by Gauss}.
\item
Give an example with $F = \CC((z))$ and $d = z \frac{d}{dz}$ to show that
the conclusion of Corollary~\ref{C:multi} need not hold for $r = r_0$,
even though Proposition~\ref{P:robba} holds for $r=r_0$.
\item
Deduce the analogue of Theorem~\ref{T:factor} with the factors in the opposite
order, \emph{without} doing any recalculation. (Hint: the key word here is
``opposite''.)
\item
State and prove a precise version of the assertion that ``the roots of a
polynomial over a complete algebraically closed nonarchimedean
field vary continuously
in the coefficients.''
\item
Prove Proposition~\ref{P:robba2}.
\end{enumerate}

%\end{document}