text:
\begin{document}

\newcommand{\g}{\Gamma}
\newcommand{\h}{\Phi}
\newcommand{\ch}{{\operatorname{char}}}
\newcommand{\ini}{{\operatorname{in}}}
\newcommand{\ord}{{\operatorname{ord}}}
\newcommand{\gr}{{\operatorname{gr}}}
\newcommand{\rk}{{\operatorname{rk}}}
\newcommand{\md}{{\operatorname{mod}}}

\renewcommand{\do}{,\ldots ,}

\maketitle

\begin{abstract}
In this paper we present a refined version of MacLane's theory of key polynomials \cite{57,58}, similar to those considered by M. Vaqui\'e \cite{72}, and reminiscent of related objects studied by Abhyankar and Moh (approximate roots \cite{5}, \cite{6}) and T.C. Kuo \cite{50}, \cite{51}.

Let $K$ be a valued field with rank 1 valuation $\nu$. Given a simple transcendental extension of valued fields $\iota:K\hookrightarrow L\cong K(x)$ we associate to $\iota$ a countable well ordered set of polynomials of $K[x]$ called key polynomials. We define limit key polynomials and give an explicit description of them. We also give an upper bound on the order type of the set of key polynomials.
\end{abstract}

\medskip

\section{Introduction}
\label{In}

Let $\iota:K\hookrightarrow L\cong K(x)$ be a simple transcendental
extension of valued fields, where $K$ is equipped with a valuation $\nu$ of rank 1. That is, we assume given a rank 1 valuation $\nu$ of $K$ and its extension $\nu'$ to $L$. Let $(R_\nu,M_\nu,k_\nu)$ denote the valuation ring of $\nu$. The purpose of this paper is to present a refined version of MacLane's theory of key polynomials \cite{57,58}, similar to those considered by M. Vaqui\'e \cite{72}, and reminiscent of related objects studied by Abhyankar and Moh (approximate roots \cite{5}, \cite{6}) and T.C. Kuo \cite{50}, \cite{51}.

Namely, we associate to $\iota$ a countable well ordered set
$$
\mathbf{Q}=\{Q_i\}_{i\in\Lambda}\subset K[x];
$$
the $Q_i$ are called {\bf key polynomials}. Key polynomials $Q_i$ which have no immediate predecessor are called {\bf limit key polynomials}. Let $\beta_i=\nu'(Q_i)$.

We give an explicit description of the limit key polynomials (which may be viewed as a generalization of the Artin--Schreier polynomials). We also give an upper bound on the order type of the set of key polynomials. Namely, we show that if $\ch\ k_\nu=0$ then the set of key polynomials has order type at most $\omega$, while in the case $\ch\ k_\nu=p>0$ this order type is bounded above by $\omega\times\omega$, where $\omega$ stands for the first infinite ordinal.

Let $\g$ (resp. $\g'$) denote the value group of $\nu$ (resp. $\nu'$). Let $\g'_1$ denote the smallest non-zero isolated subgroup of $\g'$ (it may happen that $\g'_1=\g'$).

The main application of this theory that we have in mind is proving the local uniformization theorem for quasi-excellent noetherian schemes in positive and mixed characteristic. In Chapter 3 of his Ph.D. thesis (Institut de Math\'ematiques de Toulouse, 2013) J.-C. San Satrunino reduced the local uniformization theorem in the case of positive characteristic to the problem of the monomialization of the first limit key polynomial of a certain explicitly defined simple field extension $K\hookrightarrow L$. In Chapter 4 he proved a similar reduction for local uniformization in the case of mixed characteristic, but under some additional hypotheses. For the purposes of local uniformization, we will be mainly interested in key polynomials whose values lie in $\g'_1$. As soon as our algorithm produces a key polynomial whose value does not lie in $\g'_1$, we stop. Chapter 3 of the Ph.D. thesis of W. Mahboub (Institut de Math\'ematiques de Toulouse, 2013) develops the theory of key polynomials for valuations of arbitrary rank; here we limit ourselves to the minimum necessary for local uniformization.

The well ordered set $\mathbf{Q}=\{Q_i\}_{i\in\Lambda}$ of key polynomials of $\nu'$
will be defined recursively in $i$.

\medskip

\noindent{\bf Notation.} We will use the notation $\mathbb{N}$ for the set of strictly positive integers and $\mathbb{N}_0$ for the set of non-negative integers.

For an element $\ell\in\Lambda$, we will denote by $\ell +1$ the immediate successor of $\ell$ in $\Lambda$. The immediate predecessor of $\ell$, when it exists, will be denoted by $\ell -1$. For a positive
integer $t$, $\ell +t$ will denote the immediate successor of $\ell +(t-1)$. For an element $\ell\in\Lambda$, the initial segment $\{Q_i\}_{i<\ell}$ of the set of key polynomials will be denoted by $\mathbf{Q}_\ell $. For the rest of this paper, we let $p=\ch\ k_\nu$ if $\ch\ k_\nu>0$ and $p=1$ if $char\ k_\nu=0$. For an element $\beta\in\Gamma'$, let
$$
\begin{array}{rcl}
\mathbf{P}'_\beta&=\left\{y\in L\ \left|\ \nu'(y)\ge\beta\right.\right\}\cup\{0\}\\
\mathbf{P}'_{\beta+}&=\left\{y\in L\ \left|\ \nu'(y)>\beta\right.\right\}\cup\{0\}.
\end{array}
$$
Put $G_{\nu'}=\bigoplus\limits_{\beta\in\Gamma'}\frac{\mathbf{P}'_\beta}{\mathbf{P}'_{\beta+}}$ and $G_{\nu'1}=
\bigoplus\limits_{\beta\in\Gamma'_1}\frac{\mathbf{P}'_\beta}{\mathbf{P}'_{\beta+}}$.

\medskip

For an element $\beta'\in\g'$, let $P'_{\beta'}$ denote the $R_\nu$-submodule of
$K[x]$ consisting of all the polynomials of value greater than or equal to $\beta'$.
A set of key polynomials is said to be {\bf complete} if for every
$\beta'\in\g'$ the additive group $P'_{\beta'}$ is generated by the
products of the form $c\prod\limits_{j=1}^sQ_{i_j}^{\gamma_j}$, where $c\in K$,
$i_j\in\Lambda$ and $\gamma_j\in\mathbb{N}$, contained in $P'_{\beta'}$ (in particular, the valuation $\nu'$ is completely determined by the data $\{Q_i,\nu'(Q_i)\}$; see Definition \ref{de9.1} below). It is said to be 1-{\bf complete} if the above condition holds only for $\beta'\in\g'_1$, in other words, if for all $\beta\in\g'_1$ any polynomial $f\in K[x]$ with $\nu'(f)=\beta$ belongs to the additive group generated by products of the form $a\prod\limits_{j=1}^sQ_{i_j}^{\gamma_j}$, $a\in K$, such that $\sum\limits_{j=1}^s\gamma_j\nu'(Q_{i_j})+\nu(a)\ge\beta$.

We will use the following multi-index notation: $\bar\gamma_{\ell +1}=\{\gamma_i\}_{i\le\ell }$, where the $\gamma_i$ are non-negative integers, all but finitely many of which are equal to 0, and
\begin{equation}
\mathbf{Q}_{\ell +1}^{{\bar\gamma}_{\ell +1}}=\prod\limits_{i\le\ell }Q_i^{\gamma_i}.\label{tag1-7}
\end{equation}
An $\ell${\bf-standard monomial} in $\mathbf{Q}_{\ell +1}$ is a product of the form
\begin{equation}
c_{\bar\gamma_{\ell +1}}\mathbf{Q}_{\ell +1}^{\bar\gamma_{\ell +1}},\label{tag1-8}
\end{equation}
where $c_{{\bar\gamma}_{\ell +1}}\in K$ and the multiindex ${\bar\gamma}_{\ell +1}$ satisfies certain additional conditions to ensure a form of uniqueness (see Definition \ref{de9.9}). An $\ell$-{\bf standard expansion} is a finite sum of $\ell$-standard monomials. In \S\ref{Section3} we will show that for any $\ell\in\Lambda$ and any $f\in K[x]$ the element $f$ admits an $\ell$-standard expansion
\begin{equation}
f=\sum\limits_{j=0}^{s_\ell }c_{j\ell}Q_\ell ^j,\label{tag1-9}
\end{equation}
where each $c_{j\ell}$ is an $\ell$-standard expansion not involving $Q_\ell $. We
define an auxiliary valuation $\nu_\ell $ of $\ell$ by putting $\nu_\ell (f)=\min\limits_{0\le j\le s_\ell }\{\nu'(c_{j\ell})+j\beta_\ell \}$ for each $f\in K[x]$. By the axioms for valuations, we have
\begin{equation}
\nu'(f)\ge\nu_\ell (f)\label{tag1-10}
\end{equation}
for all $f\in K[x]$. Then the statement that $\mathbf{Q}$ is a complete set of key
polynomials can be expressed as follows: for any $f\in K[x]$ there exists
$\ell\in\Lambda$ such that equality holds in (\ref{tag1-10}).

In \S\ref{Section3} we will fix an ordinal $\ell$ and assume that the key polynomials $\mathbf{Q}_{\ell +1}$ are already defined. We will then define the next key polynomial $Q_{\ell +1}$. Roughly speaking, $Q_{\ell +1}$ will be defined to be the lifting to $K[x]$ of the monic minimal polynomial, satisfied by $\ini_{\nu'}Q_\ell $ over the graded algebra $G_\nu\left[\ini_{\nu'}\mathbf{Q}_\ell \right]$, where $\ini_{\nu'}Q_\ell$ denotes the natural image of $Q_\ell$ in $G_{\nu'}$.

In \S4 we study the effect of differential operators $\frac1{j!}\frac{\partial^j}{\partial x^j}$ on key polynomials and standard expansions. Let $\partial_j$ denote the differential operator $\frac1{j!}\frac{\partial^j}{\partial x^j}$. Let $j$ denote the element of $\mathbb{N}$ which maximizes the quantity
$\frac{\beta_i-\nu'\left(\partial_jQ_i\right)}j$. We show that $j$ is of the form
\begin{equation}
j=p^{e_i}\quad\text{ for some }e_i\in\mathbb{N}_0.\label{tag1-11}
\end{equation}
The non-negative integers $e_i$, $i\in\Lambda$, are important numerical
characters of the extension $\iota$ of valued fields. Most importantly, given an $\ell$-standard monomial
$c_{\bar\gamma_{\ell +1}}\mathbf{Q}_{\ell +1}^{\bar\gamma_{\ell +1}}$, we derive an explicit formula for the quantity
$$\nu'\left(\partial_{p^b}c_{\bar\gamma_{\ell +1}}\mathbf{Q}_{\ell +1}^{\bar\gamma_{\ell +1}}\right)=
\nu_\ell \left(\partial_{p^b}c_{\bar\gamma_{\ell +1}}\mathbf{Q}_{\ell +1}^{\bar\gamma_{\ell +1}}\right),
$$
for integers $b\ge e_i$, and under certain additional conditions. Also, for any $\ell$-standard expansion $f$ and an integer $b\ge e_i$, we derive a formula for $\nu_\ell (\partial_{p^b}f)$. We give a necessary condition for the equality $\nu'(\partial_{p^b}f)=\nu_\ell (\partial_{p^b}f)$ to hold.

The importance of this type of explicit formulae can be explained as follows. The importance of differential operators for resolution of singularities is well known. One difficulty with dealing with differential operators up to now has been the fact that they obey no simple transformation law under blowing up. Since key polynomials become coordinates after blowing up, the above formulae can be viewed as comparison results for derivatives of the defining equations of a singularity before and after blowing up.

In \S5 we associate to each $h\in K[x]$ and each ordinal $i$ for which $Q_i$ is defined, a pair $(\delta_i(h),\epsilon_i(h))$ of positive integer numerical characters of the Newton polygon $\Delta_i(h)$. We prove that the pair $(\delta_i(h),\epsilon_i(h))$ is non-increasing in the lexicographical ordering, and hence must stabilize for $i\gg0$. We also show that the equality
$$
(\delta_i(h),\epsilon_i(h))=(\delta_{i+1}(h),\epsilon_{i+1}(h))
$$
imposes strong restrictions on $h$. The numerical character $(\delta_i(h),\epsilon_i(h))$ helps analyze infinite ascending sequences $\{Q_i\}_{i\in\Lambda}$ in \S6.

In \S6 we use the above numerical characters to study the situation when our
recursive algorithm does not stop after finitely many steps, that is, when it gives
rise to an infinite sequence $\{Q_{\ell +t}\}_{t\in\mathbb{N}}$ of key polynomials.
This will end the construction of key polynomials in the case $\ch\ k_\nu=0$.
We then use the results of \S4 to show that the stable value
$\delta_i(f)$ must be of the form $\delta_i(f)=p^e$ for some $e\in\mathbb{N}_0$.

 In particular, (Proposition 6.6) that if $\ch\ k_\nu=0$ then there are no limit key polynomials $Q_i$ such that $\beta_i\in\g\otimes_{\mathbb{Z}}\mathbb{Q}$. By definition, we will have $\beta_i\in\g\otimes_{\mathbb{Z}}\mathbb{Q}$ whenever $i$ is not a maximal element of $\Lambda$. The set $\Lambda$
contains a maximal element $\lambda$ if and only if it contains an element $\lambda$ such that $\ini_\nu Q_\lambda$ is transcendental over $k_{\nu}[\ini_\nu\mathbf{Q}_\lambda]$, where $\mathbf{Q}_\lambda=\{Q_i\}_{i<\lambda}$.

In \S7 we assume that $\ch\ k_\nu=p>0$ and consider an ordinal $\ell$
which does not have an immediate predecessor. We assume that the key
polynomials $\mathbf{Q}_\ell $ are already defined and define the next key
polynomial $Q_\ell $. We show that this case can occur at most $\omega$
times.

We also give an explicit description of limit key polynomials; we show that every limit key polynomial $Q_\ell $ can be written in the form
\begin{equation}
Q_\ell =Q_i^{p^{e_{n\ell}}}+\sum\limits_{j=0}^{e_{n\ell}-1}c_{p^j\ell}Q_i^{p^j}+c_{0\ell},\label{tag1-12}
\end{equation}
where $i<\ell$ and $c_{0\ell}$ and $c_{p^j\ell}$ are $i$-standard expansions not involving $Q_i$. Moreover, for each element $i'\in\Lambda$ satisfying $i<i'<\ell$ the key polynomial $Q_{i'}$ is of the form
\begin{equation}
Q_{i'}=Q_i-h_{i'}\label{tag1-13}
\end{equation}
where $h_{i'}$ is an $i$-standard expansion not involving $Q_i$.

In \S7 we prove the main property of key polynomials $\{Q_i\}$: they form a complete set
of key polynomials. As a Corollary we will obtain that the images of the key polynomials in $G_{\nu'}$ generate the field of fractions of $G_{\nu'}$ over the field of fractions of $G_\nu$ (Theorem \ref{th13.10}).

The results of this paper are related to those contained in the paper \cite{36} (see also \cite{72}).  However, there are some important differences, which we now explain. We chose to rewrite the whole theory from scratch for several reasons:
\begin{enumerate}
\item In \cite{36} we work with an algebraic extension $\iota$ while for local
uniformization we need to consider purely transcendental extensions. We note that the case of algebraic extensions can easily be reduced to that of transcendental ones using composition of valuations, so the theory presented here can be viewed as a generalization of \cite{36}.
\item Our main interest in \cite{36} was to classify all the possible
extensions $\nu'$ of a given $\nu$; in the present paper we content
ourselves with a fixed $\nu'$.
\item The crucial formulae for $\nu_\ell (\partial_{p^b}f)$ were not
made explicit in \cite{36}.
\item We take this opportunity to correct numerous mistakes which, unfortunately, made their way into the paper \cite{36}: an inaccuracy in the definition of complete set of key polynomials, the failure to take into account the case of mixed characteristic, a mistake in the definition of the numerical characters $e_i$ and many others which made the paper \cite{36} unreadable.
\end{enumerate}

\section{Algebras graded by ordered semigroups}
\label{S2}

Graded algebras associated to valuations will play a crucial role in this paper. In this section, we give some basic definitions and prove several easy results about graded algebras. Throughout this paper, a ``graded algebra'' will mean ``an
algebra without zero divisors, graded by an ordered semigroup''. As
usual, for a graded algebra $G$, $\ord$ will denote the natural valuation of
$G$, given by the grading.

\begin{definition}{\label{de4-1}} Let $G$ be a graded algebra without zero
divisors. The {\bf saturation} of $G$, denoted by $G^*$, is the
graded algebra
$$
G^*=\left\{\left.\frac gh\ \right| \ g,h\in G,\
h\text{ homogeneous},\ h\ne0\right\}.
$$
$G$ is said to be {\bf saturated} if $G=G^*$.
\end{definition}

Of course, we have $G^*=(G^*)^*$ for any graded algebra $G$, so that
$G^*$ is always saturated.

\begin{example}{\label{Example4-2}} Let $R$ be a ring and $\nu:R\rightarrow \g\cup\{\infty\}$ a valuation, centered at a prime ideal of $R$. Let $\h=\nu(R\setminus\{0\})$. For each
$\alpha\in\h$, consider the ideals
\begin{equation}
\begin{aligned}
P_\alpha:&=\{x\in R\ |\ \nu(x)\ge\alpha\}\quad\text{and}\\
P_{\alpha+}:&=\{x\in R\ |\ \nu(x)>\alpha\}.
\end{aligned}\label{tag3.1}
\end{equation}
$P_\alpha$ is called the $\nu$-{\bf ideal} of $R$ of value $\alpha$.

If $\alpha_1>\alpha_2>\dots$ is an infinite descending
sequence of elements of $\h$ then $P_{\alpha_1}\subsetneqq
P_{\alpha_2}\subsetneqq\dots$ is an infinite ascending chain of ideals of
$R$. Thus if $R$ is noetherian then the ordered set $\nu(R)$ contains no
infinite descending sequences, that is, $\nu(R)$ is well ordered.

If $I$ is an ideal in a noetherian ring $R$ and $\nu$ a valuation of $R$, $\nu(I)$ will denote
$$\min\{\nu(x)\ |\ x\in I\}.$$

We now define certain natural graded algebras, associated to
valuations. Let $R$, $\nu$ and $\h$ be as above. For $\alpha\in\h$,
let $P_\alpha$ and $P_{\alpha+}$ be as in (\ref{tag3.1}). We define
$$
\gr_\nu R=\bigoplus_{\alpha\in\h}\frac{P_\alpha}{P_{\alpha+}}.
$$
The algebra $\gr_\nu R$ is an integral domain. For any element $x\in R$ with
$\nu(x)=\alpha$, we may consider the natural image of $x$ in
$\frac{P_\alpha}{P_{\alpha+}}\subset\gr_\nu R$. This image is a
homogeneous element of $\gr_\nu R$ of degree $\alpha$, which we will denote by
$\ini_\nu x$. The grading induces an obvious valuation on $\gr_\nu R$
with values in $\h$; this valuation will be denoted by $\ord$.

Next, suppose that $(R,M,k)$ is a local domain and $\nu$ is a valuation with value group $\g$,
centered at $R$. Let $K$ denote the field of fractions of $R$. Let $(R_\nu,M_\nu,k_\nu)$ denote the valuation
ring of $\nu$. For $\alpha\in\g$, consider the following
$R_\nu$-submodules of $K$:
\begin{equation}
\begin{aligned}
\mathbf{P}_\alpha&=\{x\in K\ |\ \nu(x)\ge\alpha\},\\
\mathbf{P}_{\alpha+}&=\{x\in K\ |\ \nu(x)>\alpha\}.
\end{aligned}\label{tag3.2}
\end{equation}
We define
$$
G_\nu=\bigoplus_{\alpha\in\g}\frac{\mathbf{P}_\alpha}{\mathbf{P}_{\alpha+}}.
$$
Again, given $x\in K$, we may speak of the natural image of $x$ in
$G_\nu$, also denoted by $\ini_\nu x$ (since $\gr_\nu R$ is naturally a graded subalgebra of $G_\nu$, there is no danger of
confusion). Then $\ord$ is a valuation of the common field of fractions
of $\gr_\nu R$ and $G_\nu$, with values in $\g$.

We have $G_\nu=(\gr_\nu R)^*$; in particular,
$G_\nu$ is saturated.
\end{example}

\begin{remark}{\label{Remark 2.3}} Let $G,G'$ be two graded algebras without zero
divisors, with $G\subset G'$. Let $x$ be a homogeneous element of
$G'$, satisfying an algebraic dependence relation
\begin{equation}
a_0x^\alpha+a_1x^{\alpha-1}+\dots+a_\alpha=0\label{tag2.3}
\end{equation}
over $G$ (here $a_j\in G$ for $0\le j\le\alpha$). Without loss of
generality, we may assume that (\ref{tag2.3}) is homogeneous (that is, the
quantity $j\ \ord\ x+\ord\ a_j$ is constant for $0\le j\le\alpha$; this is
achieved by replacing (\ref{tag2.3}) by the sum of those terms $a_jx^j$ for which the
quantity $j\ \ord\ x+\ord\ a_j$ is minimal), and that the integer
$\alpha$ is the smallest possible. Dividing (\ref{tag2.3}) by $a_0$, we see that $x$
satisfies an {\it integral} homogeneous relation over $G^*$ of degree
$\alpha$ and no algebraic relation of degree less than $\alpha$. In
other words, $x$ is {\it algebraic} over $G$ if and only if it is {\it
integral} over $G^*$; the conditions of being ``algebraic over $G^*$'' and
``integral over $G^*$'' are one and the same thing.
\end{remark}

Let $G\subset G'$, $x$ be as above and let $G[x]$ denote the graded
subalgebra of $G'$, generated by $x$ over $G$. By Remark \ref{Remark 2.3}, we may
assume that $x$ satisfies a homogeneous integral relation
\begin{equation}
x^\alpha+a_1x^{\alpha-1}+\dots+a_\alpha=0\label{tag4.2}
\end{equation}
over $G^*$ and no algebraic relations over $G^*$ of degree less than $\alpha$.

\begin{lemma}{\label{el4.4}} Every element of $(G[x])^*$ can be written uniquely as a polynomial in $x$ with coefficients in $G^*$, of
degree strictly less than $\alpha$.
\end{lemma}

\begin{proof} Let $y$ be a homogeneous element of $G[x]$. Since $x$ is integral over $G^*$, so is $y$. Let
\begin{equation}
y^\gamma+b_1y^{\gamma-1}+\dots+b_\gamma=0\label{tag4.3}
\end{equation}
with $b_j\in G^*$, be a homogeneous integral dependence relation of $y$ over $G^*$, with $b_\gamma\ne0$. By (\ref{tag4.3}),
$$
\frac1y=-\frac1{b_\gamma}(y^{\gamma-1}+b_1y^{\gamma-2}+\dots+b_{\gamma-1}).
$$
Thus, for any $z\in G[x]$, we have
\begin{equation}
\frac zy\in G^*[x].\label{tag4.4}
\end{equation}
Since $y$ was an arbitrary homogeneous element of $G[x]$, we have
proved that
$$
(G[x])^*=G^*[x].
$$
Now, for every element $y\in G^*[x]$ we can add a multiple of (\ref{tag4.2})
to $y$ so as to express $y$ as a polynomial in $x$ of degree less than
$\alpha$. Moreover, this expression is unique because $x$ does not
satisfy any algebraic relation over $G^*$ of degree less than $\alpha$.
\end{proof}

\begin{notation} If $\Delta\subset\Delta'$ are ordered
semigroups and $\beta$ is an element of $\Delta'$, $\Delta:\beta$ will denote
the positive integer defined by
$$
\Delta:\beta=\min\{\alpha\in\mathbb{N}\ |\ \alpha\beta\in\Delta\}
$$
If the set on the right hand side is empty, we take $\Delta:\beta=\infty$.\\
(Note that if $\beta=0$ then $\Delta:\beta=1$).
\end{notation}

\begin{lemma}{\label{el4.5}} Let $G$, $G'$ be as in Remark \ref{Remark 2.3} and $x$ a homogeneous element of $G'$. Assume that the
degree 0 part of $G$ contains a field $k$ and that $G$ is generated
as a $k$-algebra by homogeneous elements $w_1\do w_r$. Let
$\beta_j=\ord\ w_j$, $1\le j\le r$, and let $\Delta$ denote the group
$\Delta=\{\ord\ y\ |\ y\in
G^*\}\equiv\left\{\left.\sum\limits_{j=1}^r\alpha_j\beta_j\ \right|\
\alpha_j\in\mathbb{Z}\right\}$. Assume that the following two conditions
hold:
\begin{enumerate}
\item[(1)] $\Delta:(\ord\ x)<\infty$
\item[(2)] Let $\bar\alpha:=\Delta:\ord\ x$. Let $\alpha_1\do\alpha_r\in\mathbb{Z}$
be such that
\begin{equation}
\bar\alpha\ \ord\ x=\sum\limits_{j=1}^r\alpha_j\beta_j.\label{tag4.5}
\end{equation}
Let $y=\prod\limits_{j=1}^rw_j^{\alpha_j}$. We require that the
element
\begin{equation}
z:=\frac{x^{\bar\alpha}}y\in(G')^*\label{tag2.8}
\end{equation}
be algebraic over $k$.
\end{enumerate}
Then $x$ is integral over $G^*$. An integral dependence relation of
$x$ over $G^*$ can be described as follows. Let $z$ be as in (\ref{tag2.8}). Let
$Z$ be an independent variable and let
\begin{equation}
\lambda(Z)=Z^d+\sum\limits_{i=0}^{d-1}c_iZ^i=0\label{tag4.7}
\end{equation}
denote the minimal polynomial of $z$ over $k$. Then $x$ satisfies the
integral dependence relation
\begin{equation}
x^{d\bar\alpha}+\sum\limits_{i=0}^{d-1}c_iy^{d-i}x^{i\bar\alpha}=0.\label{tag2.10}
\end{equation}
Conversely, suppose $x$ is integral over $G^*$. Then (1) holds.
Suppose, furthermore, that $\beta_1\do\beta_r$ are $\mathbb{Z}$-linearly
independent. Then (2) also holds. In this case, (\ref{tag2.10}) is the minimal
polynomial of $x$ over $G^*$. In particular, the degree $\alpha$ of
the minimal polynomial of $x$ over $G^*$ is given by
\begin{equation}
\alpha=d\bar\alpha.\label{tag4.9}
\end{equation}
\end{lemma}

\begin{proof} If (1) and (2) hold, $x$ is integral over $G^*$ because it
satisfies the integral dependence relation (\ref{tag2.10}) (this is verified
immediately by substituting (\ref{tag2.8}) for $Z$ in (\ref{tag4.7}) and multiplying
through by $y^d$). In particular, if $\alpha$ denotes the degree of $x$ over
$G^*$, (\ref{tag2.10}) shows that
\begin{equation}
\alpha\le d\bar\alpha.\label{tag4.10}
\end{equation}
Conversely, suppose $x$ is integral over $G^*$. Then $x$ satisfies a
homogeneous integral relation of the form (\ref{tag4.2}). Since (\ref{tag4.2}) is
homogeneous, we have the equality
$$
i\ \ord\ x+\ord\ a_i=j\ \ord\ x+\ord\ a_j\text{ for some }i,j\text{
such that}\ 0\le i<j\le\alpha.
$$
Hence
\begin{equation}
(j-i)\ord\ x=\ord\ a_i-\ord\ a_j.\label{tag4.11}
\end{equation}
Now, $\frac{a_i}{a_j}\in G^*$ so that
\begin{equation}
\ord\ a_i-\ord\ a_j=\ord\frac{a_i}{a_j}\in\Delta .\label{tag4.12}
\end{equation}
Putting together (\ref{tag4.11}) and (\ref{tag4.12}), we obtain (1) of the Lemma.

Now, assume that $\beta_1\do\beta_r$ are $\mathbb{Z}$-linearly
independent. We wish to prove (2). Since $\beta_1\do\beta_r$ are $\mathbb{Z}$-linearly
independent, all the monomials $w_1^{\gamma_1}\dots w_r^{\gamma_r}$,
$\gamma_j\in\mathbb{Z}$, have different values with respect to ord. Since
(\ref{tag4.2}) is homogeneous with respect to $\ord$, each $a_i$ must be a {\it
monomial} in the $w_j$ with (not necessarily positive) integer exponents. Also
by the $\mathbb{Z}$-linear independence of $\beta_1\do\beta_r$, the coefficients
$\alpha_1\do\alpha_r$ in (\ref{tag4.5}) are uniquely determined. Moreover, any
relation of the form
\begin{equation}
i\ \ord\ x-\sum\limits_{j=1}^r\alpha'_j\beta_j=0,\quad i\in\mathbb{N},\
\alpha'_1\do\alpha'_r\in\mathbb{Z}\label{tag4.13}
\end{equation}
is a positive integer multiple of the relation
\begin{equation}
\bar\alpha\ \ord\ x-\sum\limits_{j=1}^r\alpha_j\beta_j=0.\label{tag4.14}
\end{equation}
This proves that $x^i$ may appear in (\ref{tag4.2}) only if $\bar\alpha\ |\
i$; in particular, $\bar\alpha\ |\ \alpha$. Let
$d':=\frac\alpha{\bar\alpha}$. Let $0\le i<d'$. To find the coefficient $a_{i\bar\alpha}$ in (\ref{tag4.2}), note
that
$$
\alpha\ \ord\ x=d'\ \bar\alpha\ \ord\ x=i\ \bar\alpha\ \ord\ x+\ord\
a_{i\bar\alpha},
$$
so that
\begin{equation}
(d'-i)\ \bar\alpha\ \ord\ x=\ord\ a_{i\bar\alpha}.\label{tag4.15}
\end{equation}
Since $a_{i\bar\alpha}$ is a monomial in $w_1\do w_r$, (\ref{tag4.15}) gives rise to a $\mathbb{Z}$-linear dependence relation of the form (\ref{tag4.13}), which therefore must be equal to (\ref{tag4.14}) multiplied by $d'-i$. This determines the monomial $a_{i\bar\alpha}$ uniquely up to multiplication by an element of $k$: we must have $a_{i\bar\alpha}=c_iy^{d'-i}$, where $c_i\in k$. Then $z\equiv\frac{x^{\bar\alpha}}y$ satisfies the algebraic dependence relation
\begin{equation}
z^{d'}+\sum\limits_{i=0}^{d'-1}c_iz^i=0.\label{tag4.16}
\end{equation}
This proves (2) of the Lemma. Now, we have shown that, under the hypothesis of linear independence of the $\beta_j$, if $x$ has degree $\alpha$ over $G^*$ then $\bar\alpha\ |\ \alpha$ and $z$ satisfies a polynomial of degree
$d'=\frac\alpha{\bar\alpha}$. Letting $d$ denote the degree of $z$ over $k$, as above, we obtain
\begin{equation}
d'\equiv\frac\alpha{\bar\alpha}\ge d.\label{tag4.17}
\end{equation}
Combining (\ref{tag4.17}) with (\ref{tag4.10}), we obtain (\ref{tag4.9}); in particular, (\ref{tag2.10}) is the minimal polynomial of $x$ over $G$. This completes the proof of Lemma \ref{el4.5}.
\end{proof}

\begin{corollary}{\label{Corollary4.6}} Let $G$, $w_1\do w_r$ and $\beta_1\do\beta_r$ be as in lemma \ref{el4.5}. If $\beta_1\do\beta_r$ are $\mathbb{Z}$-linearly independent in $\Delta$ then $w_1\do w_r$ are algebraically independent over $k$.
\end{corollary}

\begin{proof} Induction on $r$. For $r=1$ there is nothing to prove. For
the induction step, assume that the Corollary is true for $r=i$. If
$w_{i+1}$ were algebraic over $k[w_1\do w_i]$, we would have
\begin{equation}
(\beta_1\do\beta_i):\beta_{i+1}<\infty\label{tag4.18}
\end{equation}
by lemma \ref{el4.5}, applied to the graded algebra $k[w_1\do w_i]$ and the element
$w_{i+1}$. (\ref{tag4.18}) contradicts the linear independence of $\beta_1\do\beta_r$,
and we are done. Alternatively, the Corollary can be proved by observing that
by linear independence of $\beta_1\do\beta_r$, all the monomials in $w_1\do w_r$ have
different degrees, thus any polynomial in $w_1\do w_r$ over $k$ contains a unique
monomial of smallest degree. Hence it cannot vanish.
\end{proof}

\begin{definition}{\label{de4.7}} Let $G$ be a graded algebra and
$x_\Lambda:=\{x_\lambda\}_{\lambda\in\Lambda}$ a collection of elements of
$G$. Let $k$ be a field, contained in the degree 0 part of $G$. Let
$k[x_\Lambda]$ denote the $k$-subalgebra of $G$, generated by $x_\Lambda$. We
say that $x_\Lambda$ {\bf rationally generate} $G$ if $G^*=k[x_\Lambda]^*$.
\end{definition}

The following result is an immediate consequence of definitions:
\begin{proposition}{\label{Proposition4.8}} Let $G_\nu$ be the graded algebra associated to a valuation
$\nu:K\rightarrow\Gamma$, as above. Consider a sum of the form
$y=\sum\limits_{i=1}^sy_i$, with $y_i\in K$. Let $\beta=\min\limits_{1\le i\le
s}\nu(y_i)$ and
$$
S=\left\{\left.i\in\{1,\dots,n\}\ \right|\ \nu(y_i)=\beta\right\}.
$$
The following two conditions are equivalent:
\begin{enumerate}
\item $\nu(y)=\beta$
\item $\sum\limits_{i\in S}\ini_\nu y_i\ne0$.
\end{enumerate}
\end{proposition}

\section{Key polynomials in simple transcendental extensions of valued fields}\label{Section3}

Let $K\rightarrow L\cong K(x)$ be a simple transcendental field extension, $\nu'$ a
valuation of $L$ and $\nu$ the restriction of $\nu'$ to $K$. We will assume that
$\rk\ \nu=1$ and that
\begin{equation}
\nu'(x)>0.\label{tag9.1}
\end{equation}

\begin{definition}{\label{de9.1}} A {\bf complete set of key polynomials} for $\nu'$ is a well
ordered collection $\mathbf{Q}=\{Q_i\}_{i\in\Lambda}$ of elements of
$K[x]$ such that for each $\beta\in\Gamma'$ the additive group $\mathbf{P}'_\beta\cap K[x]$ is generated by products of the form
$a\prod\limits_{j=1}^sQ_{i_j}^{\gamma_j}$, $a\in K$, such that
$\sum\limits_{j=1}^s\gamma_j\nu'(Q_{i_j})+\nu(a)\ge\beta$. The
collection $\mathbf{Q}=\{Q_i\}_{i\in\Lambda}$ is said to be 1-{\bf
  complete} if for all $\beta\in\g'_1$ any polynomial $f\in
K[x]$ with $\nu'(f)=\beta$ belongs to the additive group generated by
products of the form $a\prod\limits_{j=1}^sQ_{i_j}^{\gamma_j}$, $a\in
K$, such that $\sum\limits_{j=1}^s\gamma_j\nu'(Q_{i_j})+\nu(a)\ge\beta$.
\end{definition}

Note, in particular, that if $\mathbf{Q}$ is a complete set of key polynomials
then their images $\ini_{\nu'}Q_i\in G_{\nu'}$ rationally generate $G_{\nu'}$
over $G_\nu$; if $\mathbf{Q}$ is a 1-complete set of key polynomials
then their images $\ini_{\nu'}Q_i\in G_{\nu'}$ rationally generate $G_{\nu'1}$
over $G_\nu$. Furthermore, we want to make the set $\Lambda$ as small
as possible, that is, to minimize the order type of $\Lambda$.

Our algorithm amounts to successively and explicitly constructing key
polynomials until the resulting set of key polynomials becomes
complete for $\nu'$. For an axiomatic definition of key polynomials
see \cite{57,58,59} and \cite{72}.

Take a polynomial $h=\sum\limits_{i=0}^sd_ix^i\in K[x]$, $d_i\in K$.

\begin{definition}{\label{de9.2}} The first {\bf Newton polygon} of $h$ with respect
to $\nu$ is the convex hull $\Delta_1(h)$ of the set
$\bigcup\limits_{i=0}^s\left(\left(\nu(d_i),i\right)+
\left(\Gamma_+\oplus\mathbb{Q}_+\right)\right)$ in $\Gamma\oplus\mathbb{Q}$.
\end{definition}

To an element $\beta_1\in\Gamma'_+$, we associate the following valuation
$\nu_1$ of $L$: for a polynomial $h=\sum\limits_{i=0}^sd_ix^i$, we put
$$
\nu_1(h)=\min\left\{\left.\nu(d_i)+i\beta_1\ \right|\ 0\le i\le s\right\}.
$$
Consider an element $\beta_1\in\Gamma'_+$.

\begin{definition}{\label{de9.3}} We say that $\beta_1$ {\bf determines a side} of $\Delta_1(h)$
if the following condition holds. Let
$$
S_1(h,\beta_1)=\left\{\left.i\in\{0,\dots,s\}\ \right|\
i\beta_1+\nu(d_i)=\nu_1(h)\right\}.
$$
We require that $\#S_1(h,\beta_1)\ge2$.
\end{definition}

Let $\beta_1=\nu'(x)$. Then for any $h\in K[x]$ we have
\begin{equation}
\nu_1(h)\le\nu'(h)\label{tag9.2}
\end{equation}
by the axioms for valuations. If equality holds in (\ref{tag9.2}) for all $h\in K[x]$, we put $\Lambda=\{1\}$, $x=Q_1$ and stop. The
definition of key polynomials is complete. From now on, assume that there exists a polynomial $h\in K[x]$ such that
$\nu_1(h)<\nu'(h)$.

\begin{proposition}{\label{vanish}}
Take a polynomial $h=\sum\limits_{i=0}^sd_ix^i\in
K[x]$ such that
\begin{equation}
\nu_1(h)<\nu'(h).\label{tag9.3}
\end{equation}
Then
$$
\sum\limits_{i\in S(h,\beta_1)}\ini_\nu d_i\ini_{\nu'}x^i=0.
$$
\end{proposition}

\begin{proof} We have
$$
\sum\limits_{i\in S(h,\beta_1)}d_ix^i=h(x)-\sum\limits_{i\in\{0,\dots,s\}\setminus
S(h,\beta_1)}d_ix^i,
$$
hence
$$
\nu'\left(\sum\limits_{i\in S(h,\beta_1)}d_ix^i\right)>\nu_1(h).
$$
Then $\sum\limits_{i\in S_1(h,\beta_1)}\ini_\nu d_i\ini_{\nu'}x^i=0$ in $\frac{\mathbf{P}'_{\nu_1(h)}}{\mathbf{P}'_{\nu_1(h)}+}\subset G_{\nu'}$ by
Proposition \ref{Proposition4.8}.
\end{proof}

\begin{corollary}{\label{Corollary9.5}} Take a polynomial $h\in K[x]$ such that $\nu_1(h)<\nu '(h)$. Then
$\beta_1$ determines a side of $\Delta_1(h)$.
\end{corollary}

\begin{proof} If $S_1(h,\beta_1)$ consisted of a single element $i$, we would have
$$
\ini_\nu d_i\ini_{\nu'}x^i\ne0,
$$
contradicting Proposition \ref{vanish}.
\end{proof}

\noindent{\bf Notation.} Let $X$ be a new variable. Take a polynomial
$h$ as above. We denote
$$
\ini_1h:=\sum\limits_{i\in S_1(h,\beta_1)}\ini_\nu d_iX^i.
$$
The polynomial $\ini_1h$ is quasi-homogeneous in $G_\nu[X]$, where the
weight assigned to $X$ is $\beta_1$. Let
\begin{equation}
\ini_1h=v\prod\limits_{j=1}^tg_j^{\gamma_j}\label{tag9.4}
\end{equation}
be the factorization of $\ini_1h$ into irreducible factors in $G_\nu[X]$. Here $v\in
G_\nu$ and the $g_j$ are monic polynomials in $G_\nu[X]$ (to be precise, we first
factor $\ini_1h$ over the field of fractions of $G_\nu$ and then observe that all
the factors are quasi-homogeneous and therefore lie in $G_\nu[X]$).

\begin{proposition}{\label{minimal}}
\begin{enumerate}
\item[(1)] The element $\ini_{\nu'}x$ is integral over $G_\nu$.

\item[(2)] The minimal polynomial of $\ini_{\nu'}x$ over $G_\nu$ is one of the
    irreducible factors $g_j$ of (\ref{tag9.4}).
\end{enumerate}
\end{proposition}

\begin{proof} Both (1) and (2) of the Proposition follow from the fact
that $\ini_{\nu'}x$ is a root of the polynomial $\ini_1h$ (Proposition \ref{vanish}).
\end{proof}

Now let $g_1$ be the minimal polynomial of $\ini_{\nu'}x$ over
$G_\nu$. Let $\alpha_2=\deg_Xg_1$. Write
$g_1=\sum\limits_{i=0}^{\alpha_2}\bar b_iX^i$, where $\bar
b_{\alpha_2}=1$. For each $i$, $0\le i\le\alpha_2$, choose a representative
$b_i$ of $\bar b_i$ in $R_\nu$ (that is, an element of $R_\nu$ such that
$\ini_\nu b_i=\bar b_i$; in particular, we take $b_{\alpha_2}=1$). Put
$Q_2=\sum\limits_{i=0}^{\alpha_2}b_ix^i$.

\begin{definition}{\label{de9.7}} The elements $Q_1$ and $Q_2$ are called, respectively,
{\bf the first and second key polynomials} of $\nu'$.
\end{definition}

Now, every element $y$ of $K[x]$ can be written uniquely as a finite sum of the
form
\begin{equation}
y=\sum_{\substack{0\le\gamma_1<\alpha_2\\0\le\gamma_2}}
b_{\gamma_1\gamma_2}Q_1^{\gamma_1}Q_2^{\gamma_2}\label{tag9.5}
\end{equation}
where $b_{\gamma_1\gamma_2}\in K$ (this is proved by Euclidean division by the
monic polynomial $Q_2$). The expression (\ref{tag9.5})
is called {\bf the second standard expansion of }$y$.

Now, take an ordinal number greater than or equal to 3 which has an immediate
predecessor; denote this ordinal by $\ell+1$. If $\nu(\mathbb{N})=0$, assume that $\ell\in\mathbb{N}_0$. Assume, inductively, that key polynomials $\mathbf{Q}_{\ell +1}$ and positive integers
${\mathbf{\alpha}}_{\ell +1}=\{\alpha_i\}_{i\le\ell }$ are already
constructed, that $\nu'(Q_i)\in\g'_1$ for $i\le\ell $ and that all but finitely many of
the $\alpha_i$ are equal to 1. We want to define the key polynomial $Q_{\ell +1}$.

We will use the following multi-index notation:
$\bar\gamma_{\ell +1}=\{\gamma_i\}_{i\le\ell }$, where all but finitely
many $\gamma_i$ are equal to 0, $\mathbf{Q}_{\ell +1}^{{\bar\gamma}_{\ell +1}}=\prod\limits_{i\le
l}Q_i^{\gamma_i}$. Let $\beta_i=\nu'(Q_i)$.

\begin{definition}{\label{de9.8}} An index $i<\ell$ is said to be $\ell$-{\bf essential} if there
exists a positive integer $t$ such that either $i+t=\ell$ or $i+t<\ell$ and
$\alpha_{i+t}>1$; otherwise $i$ is called $\ell$-{\bf inessential}.
\end{definition}

In other words, $i$ is $\ell$-inessential if and only if $i+\omega\le\ell $ and
$\alpha_{i+t}=1$ for all $t\in\mathbb{N}_0$.

\noindent{\bf Notation.} For $i<\ell$, let
\begin{align*}
i+&=i+1\qquad\,\text{if }i\text{ is $\ell$-essential}\\
&=i+\omega\qquad\text{otherwise}.
\end{align*}

\begin{definition}{\label{de9.9}}
A multiindex ${\bar\gamma}_{\ell +1}$ is said to be {\bf standard with respect to}
${\mathbf{\alpha}}_{\ell +1}$ if
\begin{equation}
0\le\gamma_i<\alpha_{i+}\text{ for }i\le\ell ,\label{tag9.6}
\end{equation}
and if $i$ is $\ell$-inessential then the set $\{j<i+\ |\ j+=i+\text{ and
}\gamma_j\ne0\}$ has cardinality at most one. An $\ell${\bf-standard monomial in}
$\mathbf{Q}_{\ell +1}$ (resp. an $\ell${\bf-standard monomial in} $\ini_{\nu'}\mathbf{Q}_{\ell +1}$)
is a product of the form $c_{{\bar\gamma}_{\ell +1}}\mathbf{Q}_{\ell +1}^{{\bar\gamma}_{\ell +1}}$,
(resp. $c_{{\bar\gamma}_{\ell +1}}\ini_{\nu'}\mathbf{Q}_{\ell +1}^{{\bar\gamma}_{\ell +1}}$) where
$c_{{\bar\gamma}_{\ell +1}}\in K$ (resp. $c_{{\bar\gamma}_{\ell +1}}\in G_\nu$) and the
multiindex ${\bar\gamma}_{\ell +1}$ is standard with respect to ${\mathbf{\alpha}}_{\ell +1}$.
\end{definition}

\begin{remark}{\label{Remark9.10}} In the case when $i$ is $\ell$-essential, the
condition (\ref{tag9.6}) amounts to saying that $0\le\gamma_i<\alpha_{i+1}$.
\end{remark}

\begin{definition}{\label{de9.11}} An $\ell${\bf-standard expansion not involving }$Q_\ell $ is a finite
sum $S$ of $\ell$-standard monomials, not involving $Q_\ell $, having the following property.
Write $S=\sum\limits_\beta S_\beta$, where $\beta$ ranges over a certain finite
subset of $\Gamma_+$ and
\begin{equation}
S_\beta=\sum\limits_jd_{\beta j}\label{tag9.7}
\end{equation}
is a sum of standard monomials $d_{\beta j}$ of value $\beta$. We require that
\begin{equation}
\sum\limits_j\ini_{\nu'}d_{\beta j}\ne0\label{tag9.8}
\end{equation}
for each $\beta$ appearing in (\ref{tag9.7}).
\end{definition}

In the special case when $\ell\in\mathbb{N}$, (\ref{tag9.8})
holds automatically for any sum of $\ell$-standard monomials not involving $Q_\ell $ (this
follows from Proposition \ref{Proposition9.26} (2) below).

\begin{proposition}{\label{Proposition9.12}} Let $i$ be an ordinal and $t$ a positive integer. Assume that $i+t+1\le\ell $, so that the key
polynomials $\mathbf{Q}_{i+t+1}$ are defined, and that $\alpha_i=\dots=\alpha_{i+t}=1$. Then any
$(i+t)$-standard expansion does not involve any $Q_q$ with $i\le q<i+t$. In
particular, an $i$-standard expansion not involving $Q_i$ is the same thing as an
$(i+t)$-standard expansion, not involving $Q_{i+t}$.
\end{proposition}

\begin{proof} (\ref{tag9.6})
implies that for $i\le q\le i+t$, $Q_q$ cannot appear in an $(i+t)$-standard
expansion with a positive exponent.
\end{proof}

We will frequently use this fact in the sequel without mentioning it explicitly.

\begin{definition}{\label{de9.13}}
For an element $g\in K[x]$, an expression of the form
$g=\sum\limits_{j=0}^sc_jQ_\ell ^j$, where each $c_j$ is an $\ell$-standard expansion not
involving $Q_\ell $, will be called an $\ell$-{\bf standard expansion of }$g$.
\end{definition}

\begin{definition}{\label{de9.14}} Let $\sum\limits_{{\bar\gamma}}\bar
c_{{\bar\gamma}}\ini_{\nu'}\mathbf{Q}_{\ell +1}^{{\bar\gamma}}$ be an $\ell$-standard
expansion, where $\bar c_{{\bar\gamma}}\in G_\nu$. A {\bf lifting} of
$\sum\limits_{{\bar\gamma}}\bar c_{{\bar\gamma}}\ini_{\nu'}\mathbf{Q}_{\ell +1}^{{\bar\gamma}}$ to $K[x]$ is an $\ell$-standard expansion
$\sum\limits_{{\bar\gamma}}c_{{\bar\gamma}}\mathbf{Q}_{\ell +1}^{{\bar\gamma}}$, where
$c_{{\bar\gamma}}$ is a representative of $\bar c_{{\bar\gamma}}$ in $K$.
\end{definition}

\begin{definition}{\label{de9.15}} Assume that $\ch\ k_\nu=p>0$. An $\ell$-standard expansion
  $\sum\limits_jc_jQ_\ell ^j$, where each $c_j$ is an $\ell$-standard expansion not
  involving $Q_\ell $, is said to be {\bf weakly affine} if $c_j=0$ whenever
  $j>0$ and $j$ is not of the form $p^e$ for some $e\in\mathbb{N}_0$.
\end{definition}

Assume, inductively, that for each ordinal $i\le\ell $, every element $h$ of $K[x]$
admits an $i$-standard expansion. Furthermore, assume that for each $i\le\ell $, the
$i$-th key polynomial $Q_i$ admits an $i_0$-standard expansion, with $i=i_0+$,
having the following additional properties.

If $i$ has an immediate predecessor $i-1$ in $\Lambda$ (such is always the
case if $\ch\ k_\nu=0$), the $(i-1)$-st standard expansion of $Q_i$ has the form
\begin{equation}
Q_i=Q_{i-1}^{\alpha_i}+\sum\limits_{j=0}^{\alpha_i-1}
\left(\sum\limits_{{\bar\gamma}_{i-1}}
c_{ji{\bar\gamma}_{i-1}}\mathbf{Q}_{i-1}^{{\bar\gamma}_{i-1}}\right)Q_{i-1}^j,\label{tag9.9}
\end{equation}
where:

\noindent (1) each $c_{ji{\bar\gamma}_{i-1}}\mathbf{Q}_{i-1}^{{\bar\gamma}_{i-1}}$ is an $(i-1)$-standard monomial, not involving
$Q_{i-1}$

\noindent (2) the quantity
$\nu\left(c_{ji{\bar\gamma}_{i-1}}\right)+j\beta_{i-1}+
\sum\limits_{q<i-1}\gamma_q\beta_q$ is constant for all the monomials
$$
\left(c_{ji{\bar\gamma}_{i-1}}\mathbf{Q}_{i-1}^{{\bar\gamma}_{i-1}}\right)Q_{i-1}^j
$$
appearing on the right hand side of (\ref{tag9.9})

\noindent (3) the equation
\begin{equation}
\ini_{\nu'}Q_{i-1}^{\alpha_i}+\sum\limits_{j=0}^{\alpha_i-1}
\left(\sum\limits_{{\bar\gamma}_{i-1}}\ini_\nu
c_{ji{\bar\gamma}_{i-1}}\ini_{\nu'}\mathbf{Q}_{i-1}^{{\bar\gamma}_{i-1}}\right)
\ini_{\nu'}Q_{i-1}^j=0\label{tag9.10}
\end{equation}
is the minimal algebraic relation satisfied by $\ini_{\nu'}Q_{i-1}$ over
$G_\nu[\ini_{\nu'}\mathbf{Q}_{i-1}]^*$.

Finally, if $\ch\ k_\nu=p>0$ and $i$ does not have an immediate predecessor in
$\Lambda$ then there exist an $i$-inessential index $i_0$ and a strictly
positive integer $e_i$ such that $i=i_0+$ and
\begin{equation}
Q_i=c_{0i_0}+\sum\limits_{j=0}^{e_i}c_{p^ji_0}Q_{i_0}^{p^j}\label{tag9.11}
\end{equation}
is a weakly affine monic $i_0$-standard expansion of degree $\alpha_i=p^{e_i}$ in
$Q_{i_0}$, where each $c_{qi_0}$ is an $i_0$-standard expansion not involving
$Q_{i_0}$. Moreover, there exists a positive element $\bar\beta_i\in\Gamma'_{1}\otimes_{\mathbb{Z}}\mathbb{Q}$ such that
\begin{align}
\bar\beta_i&>\beta_q\qquad\text{ for all }q<i,\label{tag9.12}\\
\beta_i&\ge p^{e_i}\bar\beta_i\quad\text{ and}\label{tag9.13}\\
p^j\bar\beta_i+\nu(c_{p^ji_0})&=p^{e_i}\bar\beta_i\quad\text{ for }0\le j\le
e_i.\label{tag9.14}
\end{align}
If $i\in\mathbb{N}_0$, we assume, inductively, that the $i$-standard expansion is unique. If $\ch\ k_\nu>0$ and $h=\sum\limits_{j=0}^{s_i}d_{ji}Q_i^j$ is an $i$-standard expansion of $h$ (where
$h\in K[x]$), we assume that the elements $d_{ji}\in K[x]$ are uniquely determined
by $h$ (strictly speaking, this does not mean that the $i$-standard expansion is
unique: for example, if $i$ is a limit ordinal, $d_{ji}$ admits an $i_0$-standard
expansion for each $i_0<i$ such that $i=i_0+$, but there may be countably many
choices of $i_0$ for which such an $i_0$-standard expansion is an $i_0$-standard
expansion, not involving $Q_{i_0}$ in the sense of Definition \ref{de9.11}).

For each ordinal $i\le\ell $ we define a valuation $\nu_i$ of $L$
as follows. Given an $i$-standard expansion $h=\sum\limits_{j=0}^{s_i}d_{ji}Q_i^j$, put
\begin{equation}
\nu_i(h)=\min\limits_{0\le j\le s_i}\{j\beta_i+\nu'(d_{ji})\}.\label{tag9.15}
\end{equation}
The valuation $\nu_i$ will be called the $i$-{\bf truncation} of $\nu$.
Note that even though in the case when $\ch\ k_\nu>0$ the standard
expansions of the elements $d_{ji}$ are not, in general, unique, the elements
$d_{ji}\in K[x]$ themselves are unique by Euclidean division, so $\nu_i$ is well
defined. That $\nu_i$ is, in fact, a valuation, rather than a
pseudo-valuation, follows from the definition of standard expansion,
particularly, from (\ref{tag9.8}). We always have
\begin{equation}
\nu_i(h)\le\nu'(h).\label{tag9.16}
\end{equation}
For $b\in\mathbb{N}_0$, let $\partial_b$ denote the differential operator $\frac1{b!}\frac{\partial^b}{\partial x^b}$.
If $\ch\ k_\nu=p>0$ and $i$ does not have an immediate predecessor, we assume, inductively, that for all $b\in\mathbb{N}$,
\begin{equation}
\nu_{i_0}(\partial_bQ_i)=\nu'(\partial_bQ_i)\label{tag9.17}
\end{equation}
(where the notation is as in (\ref{tag9.11})).

\begin{remark}{\label{Remark9.16}} If $i+1\le\ell $ is an ordinal having an immediate predecessor, it is also true that
$\nu_i(\partial_bQ_{i+1})=\nu'(\partial_bQ_{i+1})$ for all $b\in\mathbb{N}$, but, as we will see below (Proposition \ref{Proposition9.26})
this follows automatically from definitions; we do not need to make it into a separate assumption.
\end{remark}

\begin{proposition}{\label{Proposition9.17}}
\begin{enumerate}
\item[(1)] The polynomial $Q_i$ is monic in $x$; we have
\begin{equation}
\deg_xQ_i=\prod\limits_{j\le i}\alpha_j.\label{tag9.18}
\end{equation}
\item[(2)] Let $z$ be an $i$-standard expansion, not involving $Q_i$. Then
\begin{equation}
\deg_xz<\deg_xQ_i.\label{tag9.19}
\end{equation}
\end{enumerate}
\end{proposition}

\begin{proof} (\ref{tag9.18}) and (\ref{tag9.19}) are proved simultaneously by transfinite induction on $i$, using (\ref{tag9.9}), (\ref{tag9.11})
and (\ref{tag9.6}) repeatedly to calculate and bound the degree in $x$ of any standard monomial (recall
that by assumption all but finitely many of the $\alpha_i$ are equal to 1).
\end{proof}

\begin{proposition}{\label{Proposition9.18}}
\begin{enumerate}
\item[(1)] For a pair of ordinals $i_0<i\le\ell $ such that $i=i_0+$ we have
$\beta_{i_0}\alpha_i<\beta_i$.
\item[(2)] The quantity $\frac{\beta_i}{\deg_xQ_i}$ is a strictly
  increasing function of $i$.
\end{enumerate}
\end{proposition}

\begin{proof} To prove (1), we distinguish the cases when $i$ does or
does not admit an immediate predecessor. If $i$ admits an immediate
predecessor then $i_0=i-1$. In this case (1) follows from (\ref{tag9.9}) and
(\ref{tag9.10}). If $i$ does not have an immediate predecessor then (1) follows
from (\ref{tag9.12}) and (\ref{tag9.13}), since $\alpha_i=p^{e_i}$.

(2) follows from (1) and (\ref{tag9.18}) by transfinite induction on $i$.
\end{proof}

\begin{corollary}{\label{Corollary9.19}} Take an ordinal $i\le\ell $. If $i$ does not admit an immediate
predecessor, let $i_0$ be as in (\ref{tag9.11}); otherwise, put $i_0=i-1$. Consider the
$i_0$-standard expansion (\ref{tag9.9}) (resp. (\ref{tag9.11})), depending on whether or not $i$
admits an immediate predecessor. Let $\left(c_{ji_0{\bar\gamma}_{i_0}}\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}\right)Q_{i_0}^j$, with
\begin{equation}
0\le j<\alpha_i,\label{tag9.20}
\end{equation}
be an $i_0$-standard monomial, appearing in one of these standard
expansions. Then
\begin{equation}
\nu(c_{ji_0{\bar\gamma}_{i_0}})>0.\label{tag9.21}
\end{equation}
\end{corollary}

\begin{proof} Since, by definitions,
$\nu'\left(\left(c_{ji_0{\bar\gamma}_{i_0}}\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}\right)Q_{i_0}^j\right)\ge\nu'(Q_{i_0}^{\alpha_i})$
and in view of (\ref{tag9.20}), it is sufficient to prove that
\begin{equation}
\nu'\left(\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}\right)<\beta_{i_0}.\label{tag9.22}
\end{equation}
Write $\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}=\prod\limits_qQ_q^{\gamma_q}$.
Using Proposition \ref{Proposition9.18} (2), we see that
$$
\begin{aligned}
\nu'\left(\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}\right)=\sum\limits_q\gamma_q\beta_q&=
\sum\limits_q\gamma_q\deg_xQ_q\frac{\beta_q}{\deg_xQ_q}<\\
&<\frac{\beta_{i_0}}{\deg_xQ_{i_0}}\sum\limits_q\gamma_q\deg_xQ_q=
\frac{\beta_{i_0}}{\deg_xQ_{i_0}}\deg_x\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}.
\end{aligned}
$$
Since $\mathbf{Q}_{i_0}^{{\bar\gamma}_{i_0}}$ is an $i_0$-standard monomial,
not involving $Q_{i_0}$, (\ref{tag9.22}) now follows from Proposition \ref{Proposition9.17} (2). This
completes the proof.
\end{proof}

The rest of this section is devoted to the definition of $Q_{\ell +1}$. Take any
element $h\in K[x]$ and let
\begin{equation}
h=\sum\limits_{j=0}^{s_\ell }d_{j\ell}Q_\ell ^j\label{tag9.23}
\end{equation}
be an $\ell$-standard expansion of $h$, where each $d_{j\ell}$ is an $\ell$-standard
expansion, not involving $Q_\ell $.

\begin{definition}{\label{de9.20}} The $\ell$-th Newton polygon of $h$ with respect to $\nu$ is the convex hull $\Delta_\ell (h)$ of the set
$\bigcup\limits_{j=0}^{s_\ell }\left(\left(\nu'(d_{j\ell}),j\right)+
\left(\Gamma'_{1+}\oplus\mathbb{Q}_+\right)\right)$ in $\Gamma'_{1}\oplus\mathbb{Q}$.
\end{definition}

Consider the valuation $\nu_\ell $, defined in (\ref{tag9.15}).
If equality holds in (\ref{tag9.16}) for all $h\in K[x]$, put $\Lambda=\ell +1$ and stop. In this
case, the definition of key polynomials is complete. From now on, assume that strict
inequality holds in (\ref{tag9.16}) for some $h\in K[x]$.

\medskip

\noindent{\bf Notation.} Let $\bar Q_\ell $ be a new variable and let $h$ be as
above. We denote
\begin{align}
S_\ell (h,\beta_\ell ):&=\left\{j\in\{0,\dots,s_\ell \}\ \left|\
j\beta_\ell +\nu'(d_{j\ell})=\nu_\ell (h)\right.\right\}.\label{tag9.24}\\
\ini_\ell h:&=\sum\limits_{j\in
S_\ell (h,\beta_\ell )}\ini_{\nu'}d_{j\ell}\bar Q_\ell ^j;\label{tag9.25}
\end{align}
The polynomial $\ini_\ell h$ is quasi-homogeneous in $G\left[\ini_{\nu'}\mathbf{Q}_\ell ,\bar
Q_\ell \right]$, where the weight assigned to $\bar Q_\ell $ is $\beta_\ell $.

\medskip

Take a polynomial $h$ such that
\begin{equation}
\nu_\ell (h)<\nu'(h).\label{tag9.26}
\end{equation}

\begin{proposition}{\label{Proposition9.21}} We have $\sum\limits_{j\in S_\ell (h,\beta_\ell )}\ini_{\nu'}\left(d_{j\ell}Q_\ell ^j\right)=0$ in
$\frac{\mathbf{P}'_{\nu_\ell (h)}}{\mathbf{P}'_{\nu_\ell (h)+}}\subset G_{\nu'}$.
\end{proposition}

\begin{proof} This follows immediately from (\ref{tag9.26}), the fact that
$$
\sum\limits_{j\in S_\ell (h,\beta_\ell )}d_{j\ell}Q_\ell ^j=h-\sum\limits_{j\in
S_\ell (h,\beta_\ell )\setminus\{0,\dots,s\}}d_{j\ell}Q_\ell ^j
$$
and Proposition \ref{Proposition4.8}.
\end{proof}

Let $\beta_\ell $ be a non-negative element of $\Gamma'$.

\begin{definition}{\label{de9.22}} We say that $\beta_\ell $ {\bf determines a side} of $\Delta_\ell (h)$
if $\#S_\ell (h,\beta_\ell )\ge2$.
\end{definition}

\begin{corollary}{\label{Corollary9.23}} Let $\beta_\ell =\nu'(Q_\ell )$. Then $\beta_\ell $ determines a side of $\Delta_\ell (h)$.
\end{corollary}

\begin{proof} Suppose not. Then the sum $\sum\limits_{j\in
S_\ell (h,\beta_\ell )}\ini_{\nu'}\left(d_{j\ell}Q_\ell ^j\right)$
consists of only one term and hence cannot be 0. This contradicts Proposition
\ref{Proposition9.21}; Corollary \ref{Corollary9.23} is proved.
\end{proof}

Let
\begin{equation}
\ini_\ell h=v_\ell \prod\limits_{j=1}^tg_{j\ell}^{\gamma_{j\ell}}\label{tag9.27}
\end{equation}
be the factorization of $\ini_\ell h$ into (monic) irreducible
factors in $G_\nu\left[\ini_{\nu'}\mathbf{Q}_\ell \right]\left[\bar
Q_\ell \right]$ (to be precise, we first factor $\ini_\ell h$ over the
field of fractions of $G_\nu\left[\ini_{\nu'}\mathbf{Q}_\ell \right]$
and then observe that all the factors are quasi-homogeneous and
therefore lie in $G_\nu\left[\ini_{\nu'}\mathbf{Q}_\ell \right]\left[\bar Q_\ell \right]$).

\begin{corollary}{\label{Corollary9.24}} The element $\ini_{\nu'}Q_\ell $ is integral over $G_\nu[\ini_{\nu'}\mathbf{Q}_\ell ]$. Its
minimal polynomial over $G_\nu[\ini_{\nu'}\mathbf{Q}_\ell ]$ is one of the irreducible factors $g_{j\ell}$ of
(\ref{tag9.27}).
\end{corollary}

Let $\alpha_{\ell +1}$ denote the degree of $\ini_{\nu'}Q_\ell $ over
$G_\nu[\ini_{\nu'}\mathbf{Q}_\ell ]$. Renumbering the factors in (\ref{tag9.27}),
if necessary, we may assume that $g_{1\ell }$ is the minimal
polynomial of $\ini_{\nu'}Q_\ell $ over $G_\nu\left[\ini_{\nu'}\mathbf{Q}_\ell \right]$, so that
\begin{equation}
\alpha_{\ell +1}=\deg_{\bar Q_\ell }g_{1l}.\label{tag9.28}
\end{equation}
Write
\begin{equation}
g_{1\ell}=\bar Q_\ell ^{\alpha_{\ell +1}}+\sum\limits_{j=0}^{\alpha_{\ell +1}-1}
\left(\sum\limits_{{\bar\gamma}_\ell }\bar
c_{\ell +1,j{\bar\gamma}_\ell }\ini_{\nu'}\mathbf{Q}_\ell ^{{\bar\gamma}_\ell }\right) \bar Q_\ell ^j,\label{tag9.29}
\end{equation}
Define {\bf the $(\ell +1)$-st key polynomial} of $\nu'$ to be a lifting
\begin{equation}
Q_{\ell +1}=Q_\ell ^{\alpha_{\ell +1}}+\sum\limits_{j=0}^{\alpha_{\ell +1}-1}
\left(\sum\limits_{{\bar\gamma}_\ell }
c_{\ell +1,j{\bar\gamma}_\ell }\mathbf{Q}_\ell ^{{\bar\gamma}_\ell }\right)Q_\ell ^j\label{tag9.30}
\end{equation}
of (\ref{tag9.29}) to $K[x]$. In the special case when $\alpha_{\ell +1}=1$,
some additional conditions must be imposed on the lifting (\ref{tag9.30}).
In fact, in this case we will define several consecutive key polynomials at the same
time. We will now explain what these additional conditions are, after making some general remarks.

\begin{remark}{\label{Remark9.25}} Since $g_{1\ell}$ is an irreducible polynomial in $\bar Q_\ell $ by
definition, the key polynomial $Q_{\ell +1}$ is also irreducible (for a non-trivial
factorization of $Q_{\ell +1}$ would give rise to a non-trivial factorization
of $g_{1\ell}$).
\end{remark}

\begin{proposition}{\label{Proposition9.26}} Take an element $h$ of $K[x]$ and an ordinal $i\le\ell $. Assume that one of the following conditions holds:
\begin{enumerate}
\item[(1)]
\begin{equation}
\nu'(h)<\beta_i\label{tag9.31}
\end{equation}
and $h$ admits an $i$-standard expansion
\begin{equation}
h=\sum\limits_{j=0}^sc_jQ_i^j,\label{tag9.32}
\end{equation}
such that
\begin{equation}
\nu'(c_j)\ge0\quad\text{ for all }j.\label{tag9.33}
\end{equation}
\item[(2)] $\deg_xh<\deg_xQ_{i+1}=\prod\limits_{q=0}^{i+1}\alpha_q$.
\end{enumerate}
Then $\nu'(h)=\nu_i(h)$.
\end{proposition}

\begin{proof} Let (\ref{tag9.32}) be an $i$-standard expansion of $h$, where in case (1) we assume that (\ref{tag9.33}) holds. By definition of
standard expansion, each $c_i$ in (\ref{tag9.32}) is an $i$-standard expansion not involving $Q_i$. Then $c_j$ is a sum of monomials
in $\mathbf{Q}_i$, which does not vanish in $G_{\nu'}$ (\ref{tag9.8}),
hence all the monomials appearing in $c_j$ have value at least
$\nu'(c_j)$ (in other words, $\nu_i(c_j)=\nu'(c_j)$).
\begin{enumerate}
\item[(1)] By (\ref{tag9.31}) and (\ref{tag9.33}),
\begin{equation}
\nu'\left(c_jQ_i^j\right)=\nu_i\left(c_jQ_i^j\right)>\nu'(h)\qquad\text{ for }j>0.\label{tag9.34}
\end{equation}
(\ref{tag9.32}) and (\ref{tag9.34}) imply that $\nu'(h)=\nu'(c_0)$. Thus $h$ is a sum of monomials in $\mathbf{Q}_{i+1}$
of value at least $\nu'(h)$, as desired.
\item[(2)] Let $S(h,\beta_i)$ be as in (\ref{tag9.24}). Let $\bar c_j:=\ini_{\nu'}c_j$. Since the degree of $\ini_{\nu'}Q_i$ over
$G_\nu[\ini_{\nu'}\mathbf{Q}_i]^*$ is $\alpha_{i+1}$, we see, using the assumption on
$\deg_xh$, that $\sum\limits_{j=0}^s\bar c_j\ini_{\nu'}Q_i^j\ne0$ in
$G_{\nu'}$. The result now follows from Proposition \ref{Proposition4.8}.
\end{enumerate}
\end{proof}

We will now describe the additional conditions we impose on the lifting (\ref{tag9.30}) in the case when $\alpha_{\ell +1}=1$.
Assume that $\alpha_{\ell +1}=1$. In what follows, we will consider $\ell$-standard expansions of the form
\begin{equation}
Q'=Q_\ell +z_\ell +\dots+z_i,\label{tag9.35}
\end{equation}
where each $z_j$ is a homogeneous $\ell$-standard expansion, not involving $Q_\ell $, such
that
\begin{equation}
\beta_\ell =\nu'(z_\ell )<\nu'(z_{\ell +1})<\dots<\nu'(z_i).\label{tag9.36}
\end{equation}

\begin{remark}{\label{Remark9.27}} Note that by (\ref{tag9.19}), we have $\deg_xz_q<\deg_xQ_\ell $ for all $q$.
\end{remark}

Let $T$ denote the set of all the $\ell$-standard expansions of the form (\ref{tag9.35}),
where each $z_j$ is a homogeneous $\ell$-standard expansion, not involving $Q_\ell $, such
that the inequalities (\ref{tag9.36}) hold and $\nu'(z_i)<\nu'(Q')$.

We impose the following partial ordering on $T$. Given an element
$$
Q'=Q_\ell +z_\ell +\dots+z_i\in T
$$
with $i>\ell$, we declare its immediate predecessor in $T$ to be the element
$Q_\ell +z_\ell +\dots+z_{i-1}$. By definition, our partial ordering is the coarsest
one among those in which $Q_\ell +z_\ell +\dots+z_{i-1}$ precedes $Q_\ell +z_\ell +\dots+z_i$ for
all the elements $Q'$ as above.

\begin{remark}{\label{Remark9.28}} Take an element $Q':=Q_\ell +z_\ell +\dots+z_i\in T$.
For each ordinal $j$ with $\ell\le j\le i$, we have
\begin{equation}
\ini_{\nu'}(Q_\ell +z_\ell +\dots+z_{j-1})=-\ini_{\nu'}z_j;\label{tag9.37}
\end{equation}
in particular, $\nu'(Q_\ell +z_\ell +\dots+z_{j-1})=\nu'(z_j)$.
\end{remark}

\begin{proposition}{\label{Proposition9.29}} Consider two elements
$$
Q'=Q_\ell +z'_\ell +\dots+z'_{i'},Q''=Q_\ell +z''_\ell +\dots+z''_{i''}\in T.
$$
Assume that
$$
\nu'(Q')<\nu'(Q'').
$$
Then there exists a standard expansion
$$
Q''':=Q_\ell +z'_\ell +\dots+z'_{i'}+z_{i'+1}+\dots+z_{i'''}\in T
$$
such that $Q'''>Q'$ and $Q'''=Q''$.
\end{proposition}

\begin{proof} Let $w=Q''-Q'$. We have
$$
\nu'(w)=\nu'(Q')<\nu'(Q'').
$$
Since $\deg\ w<\deg Q_\ell $, the $\ell$-standard expansion of $w$ does not
involve $Q_\ell $. Let
\begin{equation}
w=z_{i'+1}+\dots+z_{i'''}\label{tag9.38}
\end{equation}
be the $\ell$-standard expansion of $w$, where
$z_{i'+1}$, \dots, $z_{i'''}$ are homogeneous $\ell$-standard expansions, not
involving $Q_\ell $. Put
$$
Q'''=Q_\ell +z'_\ell +\dots+z'_{i'}+z_{i'+1}+\dots+z_{i'''}.
$$
Then
$$
Q'''=Q''
$$
and the Proposition follows immediately.
\end{proof}

To define $Q_{\ell +1}$ in the special case when
\begin{equation}
\alpha_{\ell +1}=1,\label{tag9.39}
\end{equation}
consider two cases:

\noindent{\bf Case 1.} The set $T$ contains a maximal element. Let
$Q'=Q_l+z_\ell +z_{\ell +1}+\dots+z_{s-1}$ be such a maximal element, where each $z_i$ is a
homogeneous $\ell$-standard expansion, not involving $Q_\ell $, and $s$ is an ordinal of
the form $s=\ell +t$, $t\in\mathbb{N}_0$. Define
$$
Q_i=Q_\ell +z_\ell +\dots+z_{i-1}\qquad\text{ for }\ell +1\le i\le s.
$$

\noindent{\bf Case 2.} The set $T$ does not contain a maximal element. Let
$$
\bar\beta=\sup\{\nu'(Q')\ |\ Q'\in T\}
$$
(here we allow the possibility $\bar\beta=\infty$, which means that the set $\{\nu'(Q')\ |\ Q'\in T\}$ is unbounded in
$\g'_1$). In this case, Proposition \ref{Proposition9.29} shows that there exists an infinite sequence $z_\ell ,z_{\ell +1},\dots$ of homogeneous $\ell$-standard expansions, not involving $Q_\ell $, such that for each $t\in\mathbb{N}_0$ we
have
\begin{equation}
Q_\ell +z_\ell +\dots+z_{\ell +t}\in T\label{tag9.40}
\end{equation}
and $\lim\limits_{t\to\infty}\nu'(Q_\ell +z_\ell +\dots+z_{\ell +t})=\bar\beta$; pick and fix one
such sequence. Define
$$
Q_{\ell +t}=Q_\ell +z_\ell +z_{\ell +1}+\dots+z_{\ell +t-1}\qquad\text{ for }t\in\mathbb{N}_0.
$$
Note that (\ref{tag9.36}) and Remark \ref{Remark9.28} imply that the sequence $\{\nu'(Q_\ell +z_\ell +\dots+z_{\ell +t})\}_{t\in\mathbb{N}_0}$ is strictly
increasing.

For future reference, it will be convenient to distinguish two subcases of
Case 2:

\noindent{\bf Case 2a.} $\bar\beta=\infty$, that is, the sequence
$\{\beta_{\ell +t}\}_{t\in\mathbb{N}_0}$ is unbounded in $\Gamma'_1$.

\noindent{\bf Case 2b.} The set $\{\nu'(Q')\ |\ Q'\in T\}$ has a least upper bound
$\bar\beta<\infty$ (but no maximum) in $\Gamma'_1$.

Now, take any polynomial $h\in K[x]$. The $(\ell +1)$-standard expansion
$$
h=\sum\limits_{j=0}^sc_jQ_{\ell +1}^j
$$
is constructed from the $\ell$-th one by Euclidean division by the polynomial
$Q_{\ell +1}$. Condition $\nu_\ell (c_j)=\nu'(c_j)$ required in the definition of standard
expansion (cf. Definition \ref{de9.13} and (\ref{tag9.8})) follows immediately from Propositions \ref{Proposition9.26} and \ref{Proposition9.17} (2).

By induction on $t$, this defines key polynomials $Q_{\ell +t}$ for $t\in\mathbb{N}_0$. If
for some $t\in\mathbb{N}_0$ we obtain
\begin{equation}
\nu'(Q_{l+t})\notin\g'_1,\label{tag9.41}
\end{equation}
put $\Lambda=\ell+t+1$ and stop. Below we will show that $\mathbf{Q}_{\ell+t+1}$ is a complete set of key polynomials for $\nu'$. Assume that
\begin{equation}
\nu'(Q_{\ell+t})\in\g'_1\quad\text{ for all }t\in\mathbb{N}_0.\label{tag9.42}
\end{equation}
In this case we obtain an infinite sequence
$\{Q_{\ell+t}\}$ of key polynomials. We denote the resulting set of key
polynomials by $\mathbf{Q}_{\ell+\omega}$. If $\mathbf{Q}_{\ell+\omega}$ is a
complete set of key polynomials, stop. The definition of the key
polynomials $\{Q_i\}_i$ is complete.

Assume that $\mathbf{Q}_{\ell+\omega}$ is not complete. Then there exists a
monic polynomial $h$ such that
\begin{equation}
\nu_{\ell+t}(h)<\nu(h)\label{tag9.43}
\end{equation}
for all $t\in\mathbb{N}$. Now, $\mathbf{Q}_{\ell+\omega}$ is 1-complete if and only if
\begin{equation}
\nu(h)\notin\g'_1\label{tag9.44}
\end{equation}
for all $h$ satisfying (\ref{tag9.43}). In this case, define $Q_{\ell+\omega}$ to
be the smallest degree monic polynomial $h$ satisfying (\ref{tag9.43}). The
construction of key polynomials stops here. In \S6 we will study
further properties of $Q_{\ell+\omega}$ (see Propositions \ref{Proposition12.5} and \ref{Proposition12.8}
and Remark \ref{Remark12.6}). If $\mathbf{Q}_{\ell+\omega}$ is not 1-complete (that is,
if (\ref{tag9.44}) does not hold) then $Q_{\ell+\omega}$ will also be defined as
the smallest degree monic polynomial $h$ satisfying (\ref{tag9.43}), but we
will require it to satisfy some additional conditions. A detailed
definition will be given in \S7.

\begin{proposition}{\label{Proposition9.30}} If (\ref{tag9.42}) holds and
\begin{equation}
\lim\limits_{t\to\infty}\beta_{\ell+t}=\infty,\label{tag9.45}
\end{equation}
the set $\mathbf{Q}_{\ell+\omega}$ of key polynomials defined above is 1-complete.
In other words, for any element $\beta\in(\Gamma'_1)_+$ any polynomial $f\in
K[x]$ with $\nu'(f)=\beta$ belongs to the additive subgroup
of $\mathbf{P}'_\beta\cap K[x]$ generated by all the monomials in the
$Q_i$ of value $\beta$ or higher, multiplied by elements of $K$.
\end{proposition}

\begin{proof} To prove Proposition \ref{Proposition9.30}, it is sufficient to show that
for every positive $\beta\in\Gamma'_1$ and every $h\in K[x]$ such
that $\nu'(h)=\beta$, $h$ belongs to the $R_\nu$-submodule of $K[x]$
generated by all the monomials $c\mathbf{Q}^{{\bar\gamma}}$ such that
$\nu'\left(c\mathbf{Q}^{{\bar\gamma}}\right)\ge\beta$.

Take any element $h\in K[x]$. Without loss of generality, we may
assume that, writing $h=\sum\limits_{j=0}^sd_jx^j$, we have
\begin{equation}
\nu(d_j)\ge0\quad\text{for all }j\label{tag9.46}
\end{equation}
(otherwise, multiply $h$ by a suitable element of $K$).

By (\ref{tag9.45}), there exists $i$ of the form $i=\ell+t$, $t\in\mathbb{N}_0$, such that
\begin{equation}
\beta_i>\nu'(h).\label{tag9.47}
\end{equation}
Let
\begin{equation}
h=\sum\limits_{j=0}^{s_i}c_jQ_i^j\label{tag9.48}
\end{equation}
be the $i$-standard expansion of $h$. By (\ref{tag9.46}), Corollary \ref{Corollary9.19}, and
since (\ref{tag9.48}) is obtained from $h$ by Euclidean division by $Q_i$, the
standard expansion (\ref{tag9.48}) satisfies the hypotheses of Proposition \ref{Proposition9.26}
(1). Now, Proposition \ref{Proposition9.26} says that
$$
\nu_i(h)=\nu'(h).
$$
This means, by definition, that $h$ can be written as a sum of
monomials in $\mathbf{Q}_{i+1}$ of value at least $\nu'(h)$, hence it
belongs to the ideal generated by all such monomials. This completes
the proof.
\end{proof}

Below (at the end of \S7), we will see that the above construction produces a
complete set of key polynomials whenever one of the following three
conditions is satisfied:
\begin{enumerate}
\item[(1)] (\ref{tag9.41}) holds for some $t\in\mathbb{N}_0$
\item[(2)] (\ref{tag9.42}) holds and
\begin{equation}
\#\{\alpha_{\ell+t}\ |\ \alpha_{\ell+t}>1\}=\infty\label{tag9.49}
\end{equation}
\item[(3)] $\mathbf{Q}_{\ell+\omega}$ is 1-complete.
\end{enumerate}

Moreover, we will see that (\ref{tag9.45}) always holds whenever
\begin{equation}
char\ k_\nu=0.\label{tag9.50}
\end{equation}
If $\mathbf{Q}_{\ell+\omega}$ is not a 1-complete set of key polynomials (in particular, $\ch\ k_\nu=p>0$, $\alpha_{\ell+t}=1$ for $t\gg0$ and $\lim\limits_{t\to\infty}\beta_{\ell+t}<\infty$), we must continue the
construction and define $Q_{\ell+\omega},Q_{\ell+\omega+1}$, etc. This will be
accomplished in \S7.

In the next four sections, we analyze the case when the above construction gives rise to an infinite sequence
$\{Q_{\ell+t}\}_{t\in\mathbb{N}_0}$ of key polynomials.

\section{Key polynomials and differential operators}

This section is devoted to proving some basic results about the effect of differential operators on key polynomials.
Here and below, for a non-negative integer $b$, $\partial_b$ will denote
the differential operator $\frac1{b!}\frac{\partial^b}{\partial x^b}$. Given an $\ell$-standard expansion $h$, we are
interested in proving lower bounds on (and, in some cases, exact formulae for) the
quantities $\nu'(\partial_bh)$ and $\nu_\ell (\partial_bh)$ and the elements $\ini_{\nu'}\partial_bh$ and
$\ini_\ell \partial_bh$. In particular, we will give sufficient conditions for the element $\partial_bh$ to be
non-zero.

Take an ordinal $i\le\ell $ having an immediate predecessor, so that the key polynomials $\mathbf{Q}_{i+1}$ are defined. Let $b_i$
denote the smallest positive integer which maximizes the quantity
$\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i}$ (later in this section, we will show that $b_i$ is necessarily of the
form $p^{e_i}$, for some $e_i\in\mathbb{N}_0$ and, in particular, that $b_i=1$ if $char\ k_\nu=0$).

Let $h$ be any element of $K[x]$. One of our main tasks in this section is
studying the quantities $\nu'\left(\partial_bh\right)$ and
$\nu_i\left(\partial_bh\right)$. We use the following convention for
binomial coefficients: if $s<t$, the binomial coefficient $\binom st$ is considered to be 0. We may view the binomial
coefficients as elements of $K$ via the natural map $\mathbb{Z}\rightarrow K$.

\noindent{\bf Notation.} If $p>1$, for an integer $a$ we shall denote by $\nu_p(a)$ the $p$-adic value of $a$, that is, the greatest power of $p$ which divides $a$. If $p=1$, we adopt the convention $\nu_p(a)=1$ for all non-zero $a$ and $\nu_p(0)=\infty$.

\begin{proposition}{\label{Proposition10.1}} Take an element $h\in K[x]$.
\begin{enumerate}
\item[(1)] We have for any $b\in \mathbb{N}_0$
\begin{equation}
\nu_i(h)-\nu_i\left(\partial_bh\right)\le\frac b{b_i}\left(\beta_i-\nu'(\partial_{b_i}Q_i)\right).\label{tag10.1}
\end{equation}
\item[(2)] Let $h=\sum\limits_{j=0}^sd_{ji}Q_i^j$ be the $i$-standard expansion of $h$. Assume that $s>0$. Let $d_{ji}Q_i^j$ denote the term in the $i$-standard expansion of $h$ which minimizes the triple $\left(\nu_i\left(d_{ji}Q_i^j\right),\nu_p(j),j\right)$ in the lexicographical ordering. Let $e=\nu_p(j)$ and
       $b(i,h)=b_ip^e$. Then equality holds in (\ref{tag10.1}) for $b=b(i,h)$.
\end{enumerate}
\end{proposition}

\begin{remark}{\label{Remark10.2}} Let $i_0=i-1$ if $i$ admits an immediate predecessor and let $i_0$ be as in (\ref{tag9.11}) otherwise.
We have
\begin{equation}
\nu'(\partial_{b_i}Q_i)=\nu_{i_0}(\partial_{b_i}Q_i);\label{tag10.2}
\end{equation}
this holds by the induction assumption if $i$ is a limit ordinal and by Proposition \ref{Proposition9.26} (2) otherwise. Thus replacing
$\nu'(\partial_{b_i}Q_i)$ by $\nu_{i_0}(\partial_{b_i}Q_i)$
in (\ref{tag10.1}) gives rise to an equivalent inequality. Also, $\nu_i\left(\partial_bh\right)\le\nu'\left(\partial_bh\right)$, so
replacing $\nu_i\left(\partial_bh\right)$ by $\nu'\left(\partial_bh\right)$ in (\ref{tag10.1}) gives rise to a true, but an a priori
weaker inequality.
\end{remark}

\begin{proof}[Proof of Proposition \ref{Proposition10.1}] We start with a lemma.

\begin{lemma}{\label{el10.3}} For any ordinal $i'$ such that $Q_{i'}$ is defined and any $q\in\mathbb{N}$, we have
$\nu'(\partial_qQ_{i'})\ge0$.
\end{lemma}

\begin{proof} This follows from Corollary \ref{Corollary9.19} by transfinite induction on $i'$.
\end{proof}

We prove Proposition \ref{Proposition10.1} by transfinite induction. For $i=1$ we have $b_i=1$ and the result is obvious.
Assume that $i>1$ and that the result is known for all the ordinals strictly smaller than $i$.

\begin{lemma}{\label{el10.4}} Consider a pair of ordinals $i',i''$ such that $i'<i''\le i$. Then
\begin{equation}
\frac{\beta_{i'}-\nu'(\partial_{b_{i'}}Q_{i'})}{b_{i'}}<\frac{\beta_{i''}-\nu'(\partial_{b_{i''}}Q_{i''})}{b_{i''}}.
\label{tag10.3}
\end{equation}
\end{lemma}

\begin{proof} By transfinite induction on the ordinal $i''-i'$, we may assume that $i''=i'+$, and that $Q_{i''}$ admits an $i'$-standard expansion of the form (\ref{tag9.9}) or (\ref{tag9.11}), depending on whether or not $i''$ is a limit ordinal. By definition of $b_{i''}$, it is sufficient to prove that there exists a strictly positive integer $\tilde b$ such that (\ref{tag10.3}) holds with $b_{i''}$ replaced by $\tilde b$.

We take $\tilde b:=b\left(i',Q_{i''}\right)$. We have:
$$
\begin{aligned}
\beta_{i''}-\nu'(\partial_{\tilde b}Q_{i''})&>\alpha_{i''}\beta_{i'}-\nu'(\partial_{\tilde b}Q_{i''})=
\nu_{i'}(Q_{i''})-\nu_{i'}(\partial_{\tilde b}Q_{i''})=\\
&=\frac{\tilde b}{b_{i'}}(\beta_{i'}-\nu'(\partial_{b_{i'}}Q_{i'})).
\end{aligned}
$$
Here the first inequality is given by Proposition \ref{Proposition9.18} (1), the first equality by Remark \ref{Remark10.2} and the second equality
by Proposition \ref{Proposition10.1} (2) applied to $i'<i$, which we are allowed to use by the induction assumption. This completes the
proof of the Lemma.
\end{proof}

To prove Proposition \ref{Proposition10.1} (1), it is sufficient to prove it for each $i$-standard monomial appearing in the $i$-standard expansion of $h$. Let $\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}$ be such an $i$-standard monomial.
Let $\bar\gamma_{i+1}=\{\gamma_j\ |\ j\le i\}$ and write $\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}=
\mathbf{Q}_i^{\bar\gamma_i}Q_i^{\gamma_i}$. Then
\begin{equation}
\partial_b\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}=\sum\limits_{\substack{j_0+j_1+\dots+j_q=b\\q\le\gamma_i}} C(j_1\do
j_q)Q_i^{\gamma_i-q}\left(\partial_{j_0}\mathbf{Q}_i^{{\bar\gamma}_i}\right)\prod\limits_{t=1}^q\left(\partial_{j_t}Q_i\right),\label{tag10.4}
\end{equation}
where $0<j_1\le\dots \le j_q$ and $C(j_1\do j_q)$ stands for the number of distinct maps
$$
\phi:\{j_1\do j_q\}\rightarrow 2^{\{1\do\gamma_i\}},
$$
having the following properties:
\begin{enumerate}
\item[(1)] for each $t\in\{1\do q\}$, we have $\#\{\phi(j_t)\}=\#\left\{t'\in\{1\do q\}\ \left|\ j_t=j_{t'}\right.\right\}$
\item[(2)] if $j_t\ne j_{t'}$ then $\phi(j_t)\cap\phi(j_{t'})=\emptyset$.
\end{enumerate}
For future reference, we give explicit formulae for $C(j_1\do j_q)$.
Let $\{j_{c_1}\do j_{c_\ell }\}$ with
$c_1<c_2<\dots<c_\ell$
denote the set of {\it distinct} natural numbers appearing among $\{j_1\do j_q\}$. For $1\le s\le\ell $, let $a_s=\#\{t\in\{1\do q\}\ |\ j_t\le j_{c_s}\}$.
Then
\begin{equation}
\begin{aligned}
C(j_1\do j_q)=&\binom{\gamma_i}{a_1}\binom{\gamma_i-a_1}{a_2-a_1}\dots\binom{\gamma_i-a_{l-1}}{a_\ell -a_{\ell-1}}=\\
&=\frac{\gamma_i!}{a_1!(a_2-a_1)!\dots(a_\ell -a_{\ell-1})!(\gamma_i-a_\ell )!}.
\end{aligned}\label{tag10.5}
\end{equation}
We have
\begin{equation}
\beta_i-\nu_i(\partial_{j_t}Q_i)=\beta_i-\nu'(\partial_{j_t}Q_i)\le\frac{j_t}{b_i}(\beta_i-\nu'(\partial_{b_i}Q_i))\label{tag10.6}
\end{equation}
by Remark \ref{Remark10.2} and definition of $b_i$ and
\begin{equation}
\nu_i\left(\mathbf{Q}_i^{{\bar\gamma}_i}\right)-\nu_i\left(\partial_{j_0}\mathbf{Q}_i^{{\bar\gamma}_i}\right)=
\nu_{i-1}\left(\mathbf{Q}_i^{{\bar\gamma}_i}\right)-\nu_{i-1}\left(\partial_{j_0}\mathbf{Q}_i^{{\bar\gamma}_i}\right)
<\frac{j_0}{b_i}(\beta_i-\nu'(\partial_{b_i}Q_i)))\label{tag10.7}
\end{equation}
where the equality holds because $Q_i$ does not appear in $\mathbf{Q}_i^{{\bar\gamma}_i}$ and by Remark \ref{Remark10.2}, and the
inequality by the induction assumption and in view of Lemma \ref{el10.4}. Adding the inequalities (\ref{tag10.6}) for $1\le t\le q$ and (\ref{tag10.7}), we obtain:
\begin{equation}
\begin{aligned}
&\nu_i\left(\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}\right)-\nu_i\left(Q_i^{\gamma_i-q}\left(\partial_{j_0}\mathbf{Q}_i^{{\bar\gamma}_i}\right)\prod\limits_{t=1}^q\left(\partial_{j_t}Q_i\right)\right)\le\\
&\le\frac{j_0+j_1+\dots+j_q}{b_i}(\beta_i-\nu'(\partial_{b_i}Q_i))=\frac b{b_i}(\beta_i-\nu'(\partial_{b_i}Q_i)).
\end{aligned}\label{tag10.8}
\end{equation}
By (\ref{tag10.4}) and (\ref{tag10.8}),
\begin{equation}
\begin{aligned}
&\nu_i\left(\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}\right)-\nu_i\left(\partial_b\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}\right)\le\\
&\le\nu_i\left(\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}\right)-\min\limits_{(j_0\do j_q)}\left\{\nu_i\left(Q_i^{\gamma_i-q}
\left(\partial_{j_0}\mathbf{Q}_i^{{\bar\gamma}_i}\right)\prod\limits_{t=1}^q\left(\partial_{j_t}Q_i\right)\right)\right\}\le
\frac b{b_i}(\beta_i-\nu'(\partial_{b_i}Q_i)),
\end{aligned}\label{tag10.9}
\end{equation}
as desired. Proposition \ref{Proposition10.1} (1) is proved.

Now let the notation be as in Proposition \ref{Proposition10.1} (2). We can write $b=\sum\limits_{t=1}^q\gamma_t $, where $q=p^e$ and $\gamma_t=b_i$ for all $t$. For each $i$-standard monomial $\mathbf{Q}_i^{{\bar\gamma}_i}$ not involving $Q_i$, appearing in $d_{ji}$, the corresponding term in (\ref{tag10.4}) is $\binom j{p^e}Q_i^{j-p^e}\mathbf{Q}_i^{{\bar\gamma}_i}\left(\partial_{b_i}Q_i\right)^{p^e}$. Using the definition of $b$ and the above explicit calculations of $\partial_b$ applied to each generalized monomial in the $i$-standard expansion of $h$, we see that the $i$-standard expansion of $\partial_bh$ contains a term of the form $dQ_i^{j-p^e}$ with $\nu'(d)=\nu'(\left(\partial_{b_i}Q_i\right)^{p^e}d_{ji})$, and all the other terms $d'Q_i^{j'}$ appearing in the $i$-standard expansion of $\partial_bh$ satisfy either $j'\neq{j-p^e}$ or $\nu_i(d'Q_i^{j'})>\nu_i(dQ_i^{j-p^e})$. This proves that $\nu_{i}(\partial_bh)=\nu'(dQ_i^{j-p^e})$.
\end{proof}

\begin{remark}{\label{Remark10.5}} Let
\begin{equation}
I_{i,max}=\left\{\tilde b_i\in\mathbb{N}_0\ \left|\
\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i}=\frac{\beta_i-\nu'(\partial_{\tilde b_i}Q_i)}{\tilde b_i}\right.\right\}.
\label{tag10.10}
\end{equation}
By definitions, we have $b_i=\min\ I_{i,max}$. Of course, Proposition \ref{Proposition10.1} holds equally well with $b_i$ replaced by $\tilde b_i$. Similarly, Lemma \ref{el10.4} holds if the pair $(b_{i'},b_{i''})$ is replaced by $(\tilde b_{i'},\tilde b_{i''})$ with $\tilde b_{i'}\in\mathbb{N}$, $\tilde b_{i''}\in I_{i'',max}$.
\end{remark}

\begin{corollary}{\label{Corollary10.6}} For each ordinal $i\le\ell $, each $\tilde b_i\in I_{i,max}$ is of the form $\tilde b_i=p^{\tilde
e_i}$ for some $\tilde e_i\in\mathbb{N}_0$. In particular, $b_i=p^{e_i}$ for some $e_i\in\mathbb{N}_0$. In the special case when
$\ch\ k_\nu=0$ we have $p=1$ and so $I_{i,max}=\{b_i\}=\{1\}$.
\end{corollary}

\begin{proof} Write $\tilde b_i=p^{\tilde e_i}u$, where $p\ \not|\ u$ if $\ch\ k_\nu=p>0$, and $p^{\tilde e_i}=1$ if
$\ch\ k_\nu=0$. We want to prove that $u=1$. We argue by contradiction. Assume that $u>1$. Then
$\partial_{\tilde b_i}$ can be written as
\begin{equation}
\partial_{\tilde b_i}=\frac{b'!b''!}{\tilde b_i!}\partial_{b'}\circ\partial_{b''},\label{tag10.11}
\end{equation}
where $b',b''$ are strictly positive integers such that
\begin{equation}
b'+b''=\tilde b_i\label{tag10.12}
\end{equation}
and
\begin{equation}
\nu\left(\frac{b'!b''!}{\tilde b_i!}\right)=0\label{tag10.13}
\end{equation}
(as usual, we view $\frac{b'!b''!}{\tilde b_i!}$ as an element of $K$ via the natural map $\mathbb{N}\rightarrow K$). Let
$i_0=i-1$ if $i$ admits an immediate predecessor and let $i_0$ be as in (\ref{tag9.11}) otherwise. We have
\begin{equation}
\beta_i-\nu'(\partial_{\tilde
b_i}Q_i)=(\beta_i-\nu'(\partial_{b''}Q_i))+(\nu_{i_0}(\partial_{b''}Q_i)-\nu_{i_0}(\partial_{\tilde b_i}Q_i))\label{tag10.14}
\end{equation}
by (\ref{tag10.2}). By (\ref{tag10.11}), we have $\partial_{\tilde b_i}Q_i=\frac{b'!b''!}{\tilde b_i!}\partial_{b'}(\partial_{b''}Q_i)$. Hence
\begin{equation}
\nu_{i_0}\left(\partial_{b''}Q_i\right)-\nu_{i_0}\left(\partial_{\tilde
b_i}Q_i\right)\le\frac{b'}{b_{i_0}}\left(\beta_{i_0}-\nu'\left(\partial_{\tilde
b_{i_0}}Q_{i_0}\right)\right)<\frac{b'}{\tilde b_i}\left(\beta_i-\nu'\left(\partial_{\tilde
b_i}Q_i\right)\right)\label{tag10.15}
\end{equation}
by (\ref{tag10.13}), Proposition \ref{Proposition10.1} and Lemma \ref{el10.4}. From (\ref{tag10.14})--(\ref{tag10.15}) we obtain
$$
\beta_i-\nu'(\partial_{b''}Q_i)>\left(1-\frac{b'}{\tilde b_i}\right)\left(\beta_i-\nu'(\partial_{\tilde b_i}Q_i)\right)=
\frac{b''}{\tilde b_i}\left(\beta_i-\nu'(\partial_{\tilde b_i}Q_i)\right)
$$
which contradicts the fact that $\tilde b_i\in I_{i,max}$. Corollary \ref{Corollary10.6} is proved.
\end{proof}

Next, we investigate further the case of equality in (\ref{tag10.1}). We give a necessary condition on $h$ and $b$ for the equality to hold in (\ref{tag10.1}) and prove that this condition is sufficient under some additional assumptions. Finally, we derive a formula for $\ini_ih$ in the case when this criterion for equality in (\ref{tag10.1}) holds. We start with the case when $h$ is a single $i$-standard monomial.

\begin{proposition}{\label{Proposition10.7}} Consider an $i$-standard monomial $h=\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}$. Write
\begin{align}
&b_i=p^{e_i}\qquad\text{ and}\label{tag10.16}\\
&\gamma_i=p^eu,\quad\ \text{ where }p\ \not|\ u\text{ if }\ch\ k_\nu=p>0.\label{tag10.17}
\end{align}
\begin{enumerate}
\item[(1)] If equality holds in (\ref{tag10.1}) then
\begin{equation}
\left.p^{e+e_i}\ \right|\ b.\label{tag10.18}
\end{equation}
\item[(2)] We have the following partial converse to (1). Assume that (\ref{tag10.18}) holds and that
\begin{equation}
\text{either}\quad b=p^{e+e_i}\quad\text{or}\quad I_{i,max}=\{b_i\}.\label{tag10.19}
\end{equation}
Then equality holds in (\ref{tag10.1}) if and only if
\begin{equation}
\nu\left(\binom u{b/p^{e+e_i}}\right)=0.\label{tag10.20}
\end{equation}
\item[(3)] Assume that (\ref{tag10.18})--(\ref{tag10.20}) hold. Then
\begin{equation}
\ini_i\partial_b\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}=\binom u{b/p^{e+e_i}}\,\ini_i\left(\mathbf{Q}_i^{{\bar\gamma}_i}Q_i^{\gamma_i-\frac b{b_i}}\left(\partial_{b_i}Q_i
\right)^{\frac b{b_i}}\right);\label{tag10.21}
\end{equation}
in particular, $\partial_b\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}\not\equiv0$.
\end{enumerate}
\end{proposition}

\begin{remark}{\label{Remark10.8}} If $b=p^{e+e_i}$ holds in Proposition \ref{Proposition10.7} (2) then $\frac b{p^{e+e_i}}=1$ and $\binom u{b/p^{e+e_i}}=u$, so (\ref{tag10.20}) holds automatically in this case.
\end{remark}

\begin{proof}[Proof of Proposition \ref{Proposition10.7}] We go through the proof of Proposition \ref{Proposition10.1} and analyze the case of equality at each step. We start with a
general remark about binomial coefficients in positive and mixed characteristic.

\begin{remark}{\label{Remark10.9}} If $\ch\ k_\nu=0$, we have
\begin{equation}
\nu\left(\binom\gamma j\right)=0\label{tag10.22}
\end{equation}
for any non-negative integers $j\le\gamma$; this implies that $\nu(C(j_1\do j_q))=0$ for any $q$-tuple $(j_1\do j_q)$ as in
(\ref{tag10.4}). If $\ch\ k_\nu=p>0$, the following is a well known characterization of the equality (\ref{tag10.22}).
Let $\gamma=k_0+pk_1+\dots+p^sk_s$ and $j=t_0+pt_1+\dots+p^st_s$, with $k_0,\dots,k_s,t_0\do t_s\in\{0,1,\dots,p-1\}$,
denote the respective $p$-adic expansions of $\gamma$ and $j$ (where we allow one of the $(s+1)$-tuples $(k_0\do k_s)$ and
$(t_0\do t_s)$ to end in zeroes). Then (\ref{tag10.22}) holds if and only if
\begin{equation}
k_j\ge t_j\quad\text{ for all }j\in\{0\do q\}.\label{tag10.23}
\end{equation}
Below, we will be particularly interested in the following special cases of (\ref{tag10.23}):
\begin{enumerate}
\item[(1)] If
\begin{equation}
\gamma=p^eu\quad\text{ with }p\not|\ u\label{tag10.24}
\end{equation}
then (\ref{tag10.22}) implies that $p^e\ |\ j$.
\item[(2)] We have the following partial converse to (1): if $\gamma$ is as in (\ref{tag10.24}) and $j=p^e$ then (\ref{tag10.23}) holds. In this
case $\binom\gamma j=\binom{p^eu}{p^e}=u\ \md\ m_\nu$.
\end{enumerate}
This is the main situation in which Proposition \ref{Proposition10.7} will be applied in this paper.
\end{remark}

\begin{lemma}{\label{el10.10}}
\begin{enumerate}
\item[(1)] The inequality in (\ref{tag10.6}) is strict unless $j_t\in I_{i,max}$.
\item[(2)] Let $\gamma_i$ and $b_i$ be as in (\ref{tag10.16})--(\ref{tag10.17}). Assume that $j_0=0$, and
\begin{equation}
j_t\in I_{i,max}\quad\text{ for }1\le t\le q.\label{tag10.25}
\end{equation}
If
\begin{equation}
\nu(C(j_1\do j_q))=0\label{tag10.26}
\end{equation}
then
\begin{equation}
\left.p^{e+e_i}\ \right|\ b.\label{tag10.27}
\end{equation}
\item[(3)] Let the assumptions be as in (2) and assume, in addition, that
$b=p^{e+e_i}$. Then (\ref{tag10.26}) holds if and only if $q=p^e$ and $j_1=\dots=j_q=b_i$.
\end{enumerate}
\end{lemma}

\begin{proof}
\begin{enumerate}
\item[(1)] is immediate from definitions.
\item[(2)] Let $\{p^{c_1}\do p^{c_\ell }\}\subset I_{i,max}$ with
\begin{equation}
e_i\le c_1<c_2<\dots<c_\ell \label{tag10.28}
\end{equation}
denote the set of {\it distinct} natural numbers appearing among $\{j_1\do j_q\}$
(cf. (\ref{tag10.25}) and Corollary \ref{Corollary10.6}). For $1\le j\le\ell $, let $a_j=\#\{t\in\{1\do q\}\ |\ j_t\le p^{c_j}\}$; let $a_0=0$.
Then
\begin{equation}
b=\sum\limits_{j=1}^\ell(a_j-a_{j-1})p^{c_j}.\label{tag10.29}
\end{equation}
Assume that (\ref{tag10.26}) holds. By (\ref{tag10.5}) and Remark \ref{Remark10.9} (1), we have
\begin{equation}
\left.p^e\ \right|\ a_j\quad\text{ for }1\le j\le\ell. \label{tag10.30}
\end{equation}
(\ref{tag10.28})--(\ref{tag10.30}) imply (\ref{tag10.27}), as desired.
\item[(3)] Assume, in addition, that $b=p^{e+e_i}$.

``Only if''. From (\ref{tag10.28})--(\ref{tag10.30}), we see that $\ell=1$ and $a_1=p^e$; the result follows immediately.

``If''. By assumptions, we have $\ell=1=q$ and $a_1=p^e$. By (\ref{tag10.5}) and Remark  \ref{Remark10.9} (2), we have
$$
C(j_1\do j_q)=C(\underset{p^e}{\underbrace{b_i\do b_i}})=\binom{\gamma_i}{p^e}=u\ \mod\ m_\nu
$$
and the result follows.
\end{enumerate}
\end{proof}

We can now finish the proof of Proposition \ref{Proposition10.7}.

By (\ref{tag10.7}) and Lemma \ref{el10.10} (1), the inequality in (\ref{tag10.8}) is strict unless $j_0=0$, and
\begin{equation}
j_t\in I_{i,max}.\label{tag10.31}
\end{equation}
Hence, by Lemma \ref{el10.10} (2), the first inequality in (\ref{tag10.9}) is strict unless $j_0=0$ and $\left.p^{e+e_i}\ \right|\ b$. This proves
(1) of the Proposition.

(2) Assume that (\ref{tag10.18}) holds. If $b=p^{e+e_i}$, by Lemma \ref{el10.10} (3) there is exactly one term on the right hand side of (\ref{tag10.4}) for which equality holds in (\ref{tag10.8}), namely, the term with $q=p^e$ and $j_1=\dots=j_q=b_i$. If $I_{i,max}=\{b_i\}$, then by Lemma \ref{el10.10} (1) there is at most one term on the right hand side of (\ref{tag10.4}) for which equality holds in (\ref{tag10.8}); if such a term exists, it is the term with $q=\frac b{b_i}$ and $j_1=\dots=j_q=b_i$. Moreover, this term satisfies equality in (\ref{tag10.8}) if and only if $\nu(C(\underset{b/b_i}{\underbrace{b_i\do b_i}}))=\nu\left(\binom{\gamma_i}{b/b_i}\right)=\nu\left(\binom u{b/p^{e+e_i}}\right)=0$. In either case, there is at most one term on the right hand side of (10.4) for which equality holds in (\ref{tag10.8}), and there is exactly one such term if and only if $\nu\left(\binom u{b/p^{e+e_i}}\right)=0$. This proves (2).

(3) of the Proposition follows from (2) and (\ref{tag10.4}).
\end{proof}

In the notation of Proposition \ref{Proposition10.7}, assume that (\ref{tag10.18}) holds. Let
$$
\gamma_i=k_0+pk_1+\dots+p^sk_s,
$$
with $k_0,\dots,k_s\in\{0,1,\dots,p-1\}$, denote the $p$-adic expansion of $\gamma_i$. Take integer $s'\in\{0\do s\}$, $k'_{s'}\in\{0\do k_{s'}\}$. Let $b=(k_0+pk_1+\dots+p^{s'-1}k_{s'-1}+p^{s'}k'_{s'})b_{i}$.

\begin{corollary}{\label{Corollary10.11}} Equality holds in (\ref{tag10.1}) for the generalized monomial $h=\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}$. The element $\ini_i\partial_b\mathbf{Q}_{i+1}^{{\bar\gamma}_{i+1}}$ is given by the formula (\ref{tag10.21}).
\end{corollary}

\begin{proof} Repeated application of Proposition \ref{Proposition10.7} (2) and (3), first $k_0$ times with $b$ replaced by 1, then $k_1$ times with $b$ replaced by $p$, and so on.
\end{proof}

Let $h=\sum\limits_{j=0}^sd_{ji}Q_i^j$ be an $i$-standard expansion. Let $S_i=S_i(h,\beta_i)$, where the notation is as in (\ref{tag9.24}). Write $\ini_ih=\sum\limits_{j\in S_i}\ini_i\left(d_{ji}Q_i^j\right)$. Write $b_i=p^{e_i}$, as above. Let $e$ be the greatest non-negative integer such that for all $j\in S_i$ we have $\left.p^e\ \right|\ j$.

\begin{proposition}{\label{Proposition10.12}}
\begin{enumerate}
\item[(1)] If equality holds in (\ref{tag10.1}) then
\begin{equation}
\left.p^{e+e_i}\ \right|\ b.\label{tag10.32}
\end{equation}
\item[(2)] Assume that
\begin{equation}
b=p^{e+e_i}.\label{tag10.33}
\end{equation}
Then equality holds in (\ref{tag10.1}). In particular, we have $\partial_bh\not\equiv0$.
\item[(3)] Assume that (\ref{tag10.33}) holds. Let $S_{bi}=\left\{j\in S_i\ \left|\ p^{e+1}\text{ does not divide }j\right.\right\}$ Then
$$
\ini_i\partial_bh=\sum\limits_{j\in S_{bi}}\ini_i\left(\binom j{p^e}d_{ji}Q_i^{j-p^e}\left(\partial_{b_i}Q_i
\right)^{p^e}\right).
$$
\end{enumerate}
\end{proposition}

\begin{proof} (1), (2) and (3) of Proposition \ref{Proposition10.12} follow, respectively, from (1), (2) and (3) of Proposition \ref{Proposition10.7}.
\end{proof}

\begin{corollary}{\label{Corollary10.13}} In the notation of Proposition \ref{Proposition10.12}, we have
\begin{equation}
h\notin K\left[x^{p^{e+e_i+1}}\right].\label{tag10.34}
\end{equation}
\end{corollary}

\begin{proof} Take $b$ as in (\ref{tag10.33}). Now the result follows from Proposition \ref{Proposition10.12} (2).
\end{proof}

Let the notation be as in Proposition \ref{Proposition10.12}.

\begin{proposition}{\label{Proposition10.14}} Take an element $j\in S_i$. Write $j=p^eu$, where
$$
\text{if }\quad\ch\ k_\nu=p>0\quad\text{ then }\quad p\ \not|\ u.
$$
Assume that
\begin{equation}
\left.p^{e+1}\ \right|\ j'\quad\text{ for all }j'\in S_i,j'<j.\label{tag10.35}
\end{equation}
Let $u=t_0+t_1p+\dots+t_sp^s$ be the $p$-adic expansion of $u$. Then
\begin{equation}
\nu_i(\partial_{jb_i}h)=\nu_i(h)-j(\beta_i-\nu'(\partial_{b_i}Q_i)),\label{tag10.36}
\end{equation}
\begin{equation}
\ini_i\partial_{jb_i}h=\left(\prod_{q=1}^st_q!\right)d_{ji}\left(\ini_i\partial_{b_i}Q_i\right)^j+\text{ terms involving }\ini_iQ_i.\label{tag10.37}
\end{equation}
For any $j'\ne j$ we have
\begin{equation}
\frac{\nu_i(h)-\nu_i(\partial_{j'b_i}h)}{j'}\le\frac{\nu_i(h)-\nu_i(\partial_{jb_i}h)}j,\label{tag10.38}
\end{equation}
and the inequality is strict whenever $j'\notin S_i$ or $j'<j$.
\end{proposition}

\begin{proof} By (\ref{tag10.35}) and Proposition \ref{Proposition10.7} (1), terms of the form $d_{j'i}Q_i^{j'}$ with
$$
j'\in S_i,j'<j
$$
satisfy strict inequality in (\ref{tag10.1}) with $b=jb_i$. Thus replacing $h$ by $\sum\limits_{j'=j}^sd_{j'i}Q_i^{j'}$ does not change the problem. Now apply Proposition \ref{Proposition10.12} repeatedly $t_0+t_1+\dots+t_s$ times. By (2) of Proposition \ref{Proposition10.12},
\begin{equation}
\nu_i\left(\partial_{jb_i}\left(d_{ji}Q_i^j\right)\right)=
\nu_i\left(d_{ji}Q_i^j\right)-j(\beta_i-\nu'(\partial_{b_i}Q_i))\label{tag10.39}
\end{equation}
and
\begin{equation}
\nu_i(\partial_{jb_i}h)=\nu_i(h)-j(\beta_i-\nu'(\partial_{b_i}Q_i)),\label{tag10.40}
\end{equation}
this proves (\ref{tag10.36}). (\ref{tag10.37}) follows from Proposition \ref{Proposition10.12} (3), by induction on $u$. Finally, the
last statement of the Proposition follows from Proposition \ref{Proposition10.12} (1) and (3), by induction on $u$.
\end{proof}

\begin{remark}{\label{Remark10.15}} Here is an alternative, more explicit explanation of (\ref{tag10.37}). Take $j'\in\{j\do s\}$ and apply (\ref{tag10.4}) to one of the generalized monomials appearing in $d_{j'i}Q_i^{j'}$ (we take $\gamma_i=j'$ and $b=jb_i$ in (\ref{tag10.4})), in order to decide which values of $j'$ and which decompositions $j_0+\dots+j_q=b$ contribute to $\ini_i\partial_bh$.

If either $j'>j$, $q\ne j$, $j_0\ne0$ or $j_t\ne b_i$ for some $t\in\{1\do j\}$ then, by definition of $b_i$, the corresponding term in (\ref{tag10.4}) is either divisible by $Q_i$ or has $\nu_i$-value strictly greater than $\nu_i\left(d_{ji}Q_i^j\right)-j(\beta_i-\nu'(\partial_{b_i}Q_i))$. This proves (\ref{tag10.37}).

Let $\sum\limits_qc_{qi}Q_i^q$ denote the $i$-standard expansion of $\partial_{jb_i}h$. The above considerations prove that $c_{0i}$ coincides with the coefficient of $Q_i^0$ in the $i$-standard expansion of $d_{ji}\left(\partial_{b_i}Q_i\right)^j$ modulo an element of higher $\nu_i$-value.
In particular, $c_{0i}\ne0$ and
\begin{equation}
\nu'(c_{0i})=\nu_i(c_{0i}).\label{tag10.41}
\end{equation}
We have
\begin{equation}
\nu'(c_{0i})=\nu_i(\partial_{jb_i}h)=\nu_i\left(\partial_{jb_i}\left(d_{ji}Q_i^j\right)\right)=
\nu_i\left(d_{ji}Q_i^j\right)-j(\beta_i-\nu'(\partial_{b_i}Q_i)).\label{tag10.42}
\end{equation}
\end{remark}

\begin{corollary}{\label{Corollary10.16}} We have
\begin{equation}
\nu_i(h)=\min\limits_{0\le j\le s}\{\nu_i(\partial_{jb_i}h)+j(\beta_i-\nu'(\partial_{b_i}Q_i))\}\label{tag10.43}
\end{equation}
and the minimum in (\ref{tag10.43}) is attained for all $j\in S_i$, satisfying (\ref{tag10.35}).
\end{corollary}

\section{The numerical characters $\delta_i(h)$ and $\epsilon_i(h)$}

Let $i$ be an ordinal such that $Q_i$ is defined, and $h$ an element of $K[x]$. Recall the definition of $\ini_i(h)$
((\ref{tag9.24})--(\ref{tag9.25})). In this section we define two numerical
characters, $\delta_i(h)$ and $\epsilon_i(h)$, which will play a crucial role in the rest of the paper. We prove that
the pair $(\delta_i(h),\epsilon_i(h))$ does not increase with $i$ with respect to the lexicographical ordering. We also
show that the equality $(\delta_i(h),\epsilon_i(h))=(\delta_{i+1}(h),\epsilon_{i+1}(h))$ imposes strong restrictions on
$\ini_ih$. Decreasing $(\delta_i(f),\epsilon_i(h))$
strictly ensures that the algorithm stops after a finite number of steps.

Let $h=\sum\limits_{i=0}^{s_i}d_{ji}Q_i^j$ be an $i$-standard expansion of $h$, where
each $d_{ji}$ is an $i$-standard expansion, not involving $Q_i$. The main definition of this section is: let
\begin{equation}
\delta_i(h)=\deg_{\bar Q_i}\ini_ih\label{tag11.1}
\end{equation}
in the notation of (\ref{tag9.24})--(\ref{tag9.25}).

\begin{definition}{\label{de11.1}} The vertex
$\left(\nu'\left(d_{\delta_i(h),i}\right),\delta_i(h)\right)$ of the
Newton polygon $\Delta_i(h)$ is called the {\bf pivotal vertex} of $\Delta_i(h)$.
\end{definition}

Let
\begin{equation}
\nu_i^+(h)=\min\left\{\left.\nu'\left(d_{ji}Q_i^j\right)\ \right|\ \delta_i(h)<j\le
s_i\right\}\label{tag11.2}
\end{equation}
and
$$
S'_i(h)=\left\{j\in\{\delta_i(h)+1,\dots,s_i\}\ \left|\
\nu'\left(d_{ji}Q_i^j\right)=\nu_i^+(h)\right.\right\}.
$$
Let $\epsilon_i(h)=\max\ S'_i(h)$ (if the set on the right hand side of (\ref{tag11.2})
is empty, we adopt the convention that $\nu_i^+(h)=\epsilon_i(h)=\infty$). It
follows from definitions that $\epsilon_i(h)>\delta_i(h)\ge0$. Furthermore, $\delta_i(h)>0$ whenever $\nu_i(h)<\nu'(h)$.

Take an ordinal $i$ such that $Q_i$ and $Q_{i+1}$ are defined. The fact that
$Q_{i+1}$ is defined means, by construction, that there exists a polynomial
$h\in K[x]$ such that $\nu_i(h)<\nu'(h)$ (if $\nu_i(h)=\nu'(h)$ for all $h\in K[x]$,
the algorithm stops at $Q_i$). Take a polynomial $h$ such that $\nu_i(h)<\nu'(h)$.
Consider the $i$-th Newton polygon of $h$. Let $S_i(h,\beta_i)$ be as in (\ref{tag9.24}).

The next Proposition shows that the pair
$(\delta_i(h),\epsilon_i(h))$ is non-increasing with $i$ (in the lexicographical
ordering) and that the equality $\delta_{i+1}(h)=\delta_i(h)$ imposes strong
restrictions on $\ini_ih$.

\begin{proposition}{\label{Proposition11.2}}
\begin{enumerate}
\item[(1)] We have
\begin{equation}
\alpha_{i+1}\delta_{i+1}(h)\le\delta_i(h).\label{tag11.3}
\end{equation}
\item[(2)] If $\delta_{i+1}(h)=\delta_i(h)$ then
\begin{align}
&\epsilon_{i+1}(h)\le\epsilon_i(h)\quad\text{and}\label{tag11.4}\\
&\ini_ih=\ini_{\nu'}d_{\delta_i(h),i}\left(\bar
Q_i+\ini_{\nu'}z_i\right)^{\delta_i(h)},\label{tag11.5}
\end{align}
where $z_i$ is some $i$-standard expansion not involving $Q_i$, and $\ini_{i+1}h$
contains a monomial of the form $\ini_{\nu'}d_{\delta_i(h),i}\bar
Q_{i+1}^{\delta_i(h)}$; in particular,
\begin{equation}
\ini_{\nu'}d_{\delta_i(h),i}=\ini_{\nu'}d_{\delta_i(h),i+1}.\label{tag11.6}
\end{equation}
\item[(3)] If
\begin{equation}
(\delta_i(h),\epsilon_i(h))=(\delta_{i+1}(h),\epsilon_{i+1}(h))\label{tag11.7}
\end{equation}
then
\begin{equation}
\nu'(d_{\epsilon_i(h),i})=\nu'(d_{\epsilon_i(h),i+1}).\label{tag11.8}
\end{equation}
\end{enumerate}
\end{proposition}

\begin{proof} We start with three Lemmas. First, consider the
$(i+1)$-standard expansion of $h$:
\begin{equation}
h=\sum\limits_{j=0}^sd_{j,i+1}Q_{i+1}^j,\label{tag11.9}
\end{equation}
where the $d_{j,i+1}$ are $(i+1)$-standard expansions, not involving $Q_{i+1}$.

\begin{lemma}{\label{el11.3}}
\begin{enumerate}
\item[(1)] We have
$$
\nu_i(h)=\min\limits_{0\le j\le
s}\nu_i\left(d_{j,i+1}Q_{i+1}^j\right)=\min\limits_{0\le j\le
s}\{\nu'(d_{j,i+1})+j\alpha_{i+1}\beta_i\}.
$$
\item[(2)] Let
$$
S_{i,i+1}=\left\{j\in\{0,\dots,s\}\ \left|\
\nu_i\left(d_{j,i+1}Q_{i+1}^j\right)=\nu_i(h)\right.\right\}
$$
and $j_0=\max\ S_{i,i+1}$. Then $\delta_i(h)=\alpha_{i+1}j_0+\delta_i(d_{j_0,i+1})$.
\end{enumerate}
\end{lemma}
\begin{proof} (1) Provisionally, let
$$
\mu=\min\limits_{0\le j\le s}\nu_i\left(d_{j,i+1}Q_{i+1}^j\right)=\min\limits_{0\le
j\le s}\{\nu'(d_{j,i+1})+j\alpha_{i+1}\beta_i\},
$$
$$
S'_{i,i+1}=\left\{j\in\{0,\dots,s\}\ \left|\
\nu_i\left(d_{j,i+1}Q_{i+1}^j\right)=\mu\right.\right\},
$$
$j'=\max\ S'_{i,i+1}$ and $\delta'=\alpha_{i+1}j'+\delta_i(d_{j',i+1})$. We want to
show that $\mu=\nu_i(h)$, $S'_{i,i+1}=S_{i,i+1}$, $j'=j_0$ and
$\delta_i(h)=\delta'$.

Let $\bar h=\sum\limits_{j\in S'_{i,i+1}}d_{j,i+1}Q_{i+1}^j$. Then
$\nu_i(h-\bar h)>\mu$ by definition, so to prove that $\nu_i(h)=\mu$ it is
sufficient to prove that $\nu_i(\bar h)=\mu$.

The $i$-standard expansions of both $\bar h$ and $d_{j',i+1}Q_{i+1}^{j'}$ contain a
monomial of the form $dQ_i^{\delta'}$, with $\deg_xd<\deg_xQ_i$, and all the other monomials in both $i$-standard expansions either have value strictly greater than $\nu_i\left(dQ_i^{\delta'}\right)$ or have degree in $x$ strictly smaller than $\deg_xdQ_i^{\delta'}$. Thus
$$
\nu_i\left(\bar h\right)\le\nu_i\left(dQ_i^{\delta'}\right)=\nu_i\left(d_{j',i+1}Q_{i+1}^{j'}\right)=\mu,
$$
so
$\nu_i(h)\le\mu$. The opposite inequality is trivial and (1) is proved. (2)
follows immediately from this.
\end{proof}

\begin{lemma}{\label{el11.4}} Consider two terms of the form $dQ_{i+1}^j$ and $d'Q_{i+1}^{j'}$
(where $j,j'\in\mathbb{N}_0$ and $d$ and $d'$ are $i$-standard expansions not involving
$Q_i$). Assume that
\begin{equation}
\nu_i\left(dQ_{i+1}^j\right)\le\nu_i\left(d'Q_{i+1}^{j'}\right)\label{tag11.10}
\end{equation}
and
\begin{equation}
\nu'\left(dQ_{i+1}^j\right)\ge\nu'\left(d'Q_{i+1}^{j'}\right).\label{tag11.11}
\end{equation}
Then $j\ge j'$. If at least one of the inequalities (\ref{tag11.10}), (\ref{tag11.11}) is strict then $j>j'$.
\end{lemma}

\begin{proof} Subtract (\ref{tag11.10}) from (\ref{tag11.11}) and use the definition of $\nu_i$ and the facts that
$$
\nu_i(Q_{i+1})=\alpha_{i+1}\beta_i<\beta_{i+1},
$$
$\nu_i(d)=\nu'(d)$ and $\nu_i(d')=\nu'(d')$.
\end{proof}

In the notation of Lemma \ref{el11.3}, let $\theta_{i+1}(h)=\min\ S_{i,i+1}$.

\begin{definition}{\label{de11.5}} The vertex $(\nu(d_{\theta_{i+1}(h),i+1}),\theta_{i+1}(h))$ is called the
{\bf characteristic vertex} of $\Delta_{i+1}(h)$.
\end{definition}

Let
\begin{equation}
\ini_ih=\ini_{\nu'}d_{\delta i}\prod\limits_{j=1}^tg_{ji}^{\gamma_{ji}}\label{tag11.12}
\end{equation}
be the factorization of $\ini_ih$ into (monic) irreducible
factors in $G_\nu\left[\ini_{\nu'}\mathbf{Q}_i\right]\left[\bar Q_i\right]$, where
$\delta=\delta_i(h)$ and $g_{1i}$ is the minimal polynomial of $\ini_{\nu'}Q_i$ over
$G_\nu\left[\ini_{\nu'}\mathbf{Q}_i\right]$.

\begin{lemma}{\label{el11.6}} We have
\begin{equation}
\gamma_{1i}=\theta_{i+1}(h)\label{tag11.13}
\end{equation}
(in particular, $d_{\gamma_{1i},i+1}\ne0$) and
\begin{equation}
\ini_{\nu'}d_{\theta_{i+1}(h),i+1}=
\ini_{\nu'}d_{\delta i}\prod\limits_{j=2}^tg_{ji}^{\gamma_{ji}}(\ini_{\nu'}Q_i).\label{tag11.14}
\end{equation}
\end{lemma}

\begin{proof} Write
$$
h=\sum\limits_{q\in
S_{i,i+1}}d_{q,i+1}Q_{i+1}^q+\sum\limits_{q\in\{0,\dots,s\}\setminus
S_{i,i+1}}d_{q,i+1}Q_{i+1}^q.
$$
By Lemma \ref{el11.3},
\begin{equation}
\ini_ih=\sum\limits_{q\in S_{i,i+1}}\ini_id_{q,i+1}\ini_iQ_{i+1}^q.\label{tag11.15}
\end{equation}
By definition of $\theta_{i+1}(h)$, $\ini_iQ_{i+1}^{\theta_{i+1}(h)}$ is the
highest power of $\ini_iQ_{i+1}$ dividing
$$\sum\limits_{q\in
S_{i,i+1}}\ini_id_{q,i+1}\ini_iQ_{i+1}^q.$$
Also by definition, we have
\begin{equation}
\ini_iQ_{i+1}=g_{1i}.\label{tag11.16}
\end{equation}
Now (\ref{tag11.13}) follows from (\ref{tag11.15}). Also from (\ref{tag11.15}),
we see that $\ini_{\nu'}d_{\theta_{i+1}(h),i+1}$ is obtained by substituting
$\ini_{\nu'}Q_i$ into $\frac{\ini_ih}{\ini_iQ_{i+1}^{\gamma_{1i}}}$, and (\ref{tag11.14}) follows.
\end{proof}

Now, apply Lemma \ref{el11.4} to the monomials $d_{\theta_{i+1}(h),i+1}Q_{i+1}^{\theta_{i+1}(h)}$ and $d_{\delta_{i+1}(h),i+1}Q_{i+1}^{\delta_{i+1}(h)}$. We have
\begin{equation}
\nu'\left(d_{\delta_{i+1}(h),i+1}Q_{i+1}^{\delta_{i+1}(h)}\right)\le
\nu'\left(d_{\theta_{i+1}(h),i+1}Q_{i+1}^{\theta_{i+1}(h)}\right)\label{tag11.17}
\end{equation}
by definition of $\delta_{i+1}$ and
\begin{equation}
\nu_i\left(d_{\theta_{i+1}(h),i+1}Q_{i+1}^{\theta_{i+1}(h)}\right)=\nu_i(h)\le
\nu_i\left(d_{\delta_{i+1}(h),i+1}Q_{i+1}^{\delta_{i+1}(h)}\right)\label{tag11.18}
\end{equation}
by Lemma \ref{el11.3}, so the hypotheses of Lemma \ref{el11.4} are satisfied. By Lemma \ref{el11.4}
\begin{equation}
\theta_{i+1}(h)\ge\delta_{i+1}(h).\label{tag11.19}
\end{equation}
Since
\begin{equation}
\alpha_{i+1}\theta_{i+1}(h)=\alpha_{i+1}\gamma_{1i}\le\deg_{\bar
Q_i}\ini_ih=\delta_i(h)\label{tag11.20}
\end{equation}
by Lemma \ref{el11.6} and (\ref{tag11.12}), (1) of the Proposition follows.

(2) and (3). Assume that $\delta_{i+1}(h)=\delta_i(h)$. Then the above two monomials
coincide and
\begin{equation}
\alpha_{i+1}=1.\label{tag11.21}
\end{equation}
Furthermore, we have equality in (\ref{tag11.20}), so $\ini_ih=\ini_{\nu'}d_{\delta_i(h),i}g_{1i}^{\delta_i(h)}$.
Combined with (\ref{tag11.21}), this proves (\ref{tag11.5}).

To prove (\ref{tag11.4}), we use (\ref{tag11.5}) and (\ref{tag11.21}). Let us compare the $i$-standard expansion
\begin{equation}
 h=\sum\limits_{j=0}^sd_{ji}Q_i^j\label{tag11.22}
\end{equation}
 and the $(i+1)$-standard expansion (\ref{tag11.9}) of $h$. Terms in (\ref{tag11.22}) whose degree in $Q_i$ is strictly less than $\epsilon_i(h)$ do not affect the monomial $d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}$. We claim that the contribution to $d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}$ of terms $d_{ji}Q_i^j$ in (\ref{tag11.22}) satisfying $j>\epsilon_i(h)$, and hence
\begin{equation}
 \nu'\left(d_{ji}Q_i^j\right)>\nu_i^+(h),\label{tag11.23}
\end{equation}
 is of the form $dQ_{i+1}^{\epsilon_i(h)}$ where $d$ is an $(i+1)$-standard expansion, not involving $Q_{i+1}$, with $$
 \nu'(d)>\nu'\left(d_{\epsilon_i(h),i}\right).
 $$
 Indeed, substitute $Q_{i+1}-z_i$ into $d_{ji}Q_i^j$. The contribution $dQ_{i+1}^{\epsilon_i(h)}$ of $d_{ji}Q_i^j$ to $d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}$ has the property $\nu'(d)\ge\nu'\left(d_{ji}z_i^{j-\epsilon_i(h)}\right)=\nu'\left(d_{ji}Q_i^j\right)-\epsilon_i(h)\beta_i>
 \nu'\left(d_{\epsilon_i(h),i}\right)$ by (\ref{tag11.23}).

Next, consider $j=\epsilon_i(h)$. Write
$$
d_{\epsilon_i(h),i}Q_i^{\epsilon_i(h)}=d_{\epsilon_i(h),i}\left(Q_{i+1}-z_i\right)^{\epsilon_i(h)}=
d_{\epsilon_i(h),i}Q_{i+1}^{\epsilon_i(h)}+
d_{\epsilon_i(h),i}\sum\limits_{j=1}^{\epsilon_i(h)}\binom{\epsilon_i(h)}jQ_{i+1}^{\epsilon_i(h)-j}z_i^j.
$$
After Euclidean division by $Q_{i+1}$, the terms in
$d_{\epsilon_i(h),i}\sum\limits_{j=1}^{\epsilon_i(h)}\binom{\epsilon_i(h)}jQ_{i+1}^{\epsilon_i(h)-j}z_i^j$ may contribute to
$d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}$, but this has the effect of modifying $d_{\epsilon_i(h),i}$ by a polynomial of the same value but of \textit{strictly} smaller degree.

 Hence
\begin{equation}
\nu'(d_{\epsilon_i(h),i+1})=\nu'(d_{\epsilon_i(h),i})\label{eq:equality}
\end{equation}
and, in particular, $d_{\epsilon_i(h),i+1}\ne0$. We now prove
(\ref{tag11.4}) by contradiction. Assume that $\epsilon_{i+1}(h)>\epsilon_i(h)$. By definitions,
 $$
 \nu'\left(d_{\epsilon_{i+1}(h),i+1}Q_{i+1}^{\epsilon_{i+1}(h)}\right)\le
 \nu'\left(d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}\right),
 $$
 so by Lemma \ref{el11.4} we have
 $$
 \nu_i\left(d_{\epsilon_{i+1}(h),i+1}Q_{i+1}^{\epsilon_{i+1}(h)}\right)\le
 \nu_i\left(d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}\right).
 $$
 Applying Lemma \ref{el11.3} to the polynomial
 $$
h':=\sum\limits_{j=\epsilon_{i+1}(h)}^sd_{j,i+1}Q_{i+1}^j,
$$
we see that its $i$-standard expansion contains a monomial $d'_{ji}Q_i^j$ with
\begin{equation}
\nu_i\left(d'_{ji}Q_i^j\right)\le\nu_i
\left(d_{\epsilon_i(h),i+1}Q_{i+1}^{\epsilon_i(h)}\right)\label{tag11.24}
\end{equation}
and
\begin{equation}
j\ge\epsilon_{i+1}(h)>\epsilon_i(h).\label{tag11.25}
\end{equation}
Since $\deg_{Q_i}(h-h')<\epsilon_{i+1}(h)$ we have $d'_{ji}=d_{ji}$, so (\ref{tag11.24})--(\ref{tag11.25}) hold also for $d_{ji}Q_i^j$. This contradicts the definition of $\epsilon_i(h)$ and (\ref{tag11.4}) is proved.

The equality (\ref{tag11.6}) follows from (\ref{tag11.14}) and the fact that $\theta_{i+1}(h)=\delta_{i+1}(h)$. (\ref{tag11.8})
(assuming (\ref{tag11.7})) follows immediately from (\ref{eq:equality}). This completes the proof of the Proposition.
\end{proof}

\begin{remark}{\label{Remark11.7}} One way of interpreting Lemma \ref{el11.4}, together with the inequalities (\ref{tag11.17})--(\ref{tag11.19})
is that the characteristic vertex $(\nu'(d_{\theta_{i+1}(h),i+1}),\theta_{i+1}(h))$
of $\Delta_{i+1}(h)$ always lies above its pivotal vertex
$(\nu'(d_{\delta_{i+1}(h),i+1}),\delta_{i+1}(h))$.
\end{remark}

Now, assume that $\mathbf{Q}_{\ell +1}$ is defined for a certain ordinal number $\ell$ and that $\omega$ iterations of the algorithm of \S3 produce an infinite sequence $\{Q_{\ell+t}\}_{t\in\mathbb{N}_0}$.

\begin{corollary}[of Proposition \ref{Proposition11.2}]{\label{Corollary11.8}}
Assume that the set $\{t\in\mathbb{N}\ |\ \alpha_{\ell+t}>1\}$ is
infinite. Then the set $\mathbf{Q}_{\ell+\omega}$ of key polynomials
constructed in \S3 is complete.
\end{corollary}

\begin{proof} Take any element $h\in K[x]$. It is sufficient to show that
$\nu_i(h)=\nu'(h)$ for some $i$ of the form $\ell+t$, $t\in\mathbb{N}$. Proposition \ref{Proposition11.2} (1) says that
\begin{equation}
\delta_{i+1}(h)<\delta_i(h)\label{tag11.26}
\end{equation}
whenever $\delta_i(h)>0$ and $\alpha_{i+1}>0$. Since the set
$\{t\in\mathbb{N}\ |\ \alpha_{\ell+t}>1\}$ is infinite, and the inequality
cannot occur infinitely many times, we have $\delta_i(h)=0$ for some
$i=\ell+t$, $t\in\mathbb{N}$. Then $\ini_ih$ does not involve $\bar Q_i$,
hence $\nu_i(h)=\nu'(h)$.
\end{proof}

\section{Infinite sequences of key polynomials}

In this section, we assume that $\mathbf{Q}_{\ell +1}$ is defined for a
certain ordinal number $\ell$, that $\omega$ iterations of the algorithm
of \S3 produce an infinite sequence $\{Q_{\ell+t}\}_{t\in\mathbb{N}_0}$ and
that $\alpha_{\ell+t}=1$ for $t\gg0$. Take an element $h\in
K[x]$. Proposition \ref{Proposition11.2} (1) implies that $\delta_{\ell+t}(h)$ stabilizes
for $t$ sufficiently large. Let $\delta(h)$ denote this stable value
of $\delta_{\ell+t}(h)$. For a positive integer $t$, we have
$$
\delta_{\ell+t}(h)=0\implies\nu'(h)=\nu_{\ell+t}(h)\implies\delta_{\ell+t+1}(h)=0.
$$
Assume that there exists $h\in K[x]$ such that $\nu'(h)>\nu_{\ell+t}(h)$
for all $t\in\mathbb{N}$ (in other words, $\delta_{\ell+t}(h)>0$ for all
$t\in\mathbb{N}$), and fix one such $h$. One of the two main results of
this section is that if $h$ is chosen to have the smallest possible degree
then $\delta(h)$ has the form $p^e$ for some $e\in\mathbb{N}_0$ (in
particular, $\delta(h)=1$ if $\ch\ k_\nu=0$). To prove this, we use
the results of \S4 on differential operators. The second main result
is the statement that if either $\ch\ k_\nu=0$ or $p\ \not|\
\delta(h)$ then the sequences $\{\beta_{\ell+t}\}_{t\in\mathbb{N}}$ and
$\nu_{\ell+t}(h)$ are unbounded in $\g'_1$; in particular, the set $\mathbf{Q}_{\ell+\omega}$ of key polynomials is 1-complete by Proposition \ref{Proposition9.30}.

Keep the above notation and assumptions. Replacing $\ell$ by $\ell+t$ for a
sufficiently large $t$, we may assume that $\alpha_{\ell+t}=1$ for all
(strictly) positive integers $t$. Below the ordinal $i$ will run over
the set $\{\ell+t\ |\ t\in\mathbb{N}_0\}$.
By definition, for all such $i$ we have
\begin{equation}
Q_{i+1}=Q_i+z_i,\label{tag12.1}
\end{equation}
where $z_i$ is a homogeneous $\ell$-standard expansion of value
$\beta_i$, not involving $Q_\ell $ (cf. Proposition \ref{Proposition9.12}). By Proposition
\ref{Proposition9.17} (2), we have
\begin{equation}
\deg_xz_i<\deg_xQ_i.\label{tag12.2}
\end{equation}
Finally,
\begin{equation}
\ini_{\nu'}Q_i=-\ini_{\nu'}z_i\label{tag12.3}
\end{equation}
by (\ref{tag9.37}).

As before, let
$$
h=\sum\limits_{j=0}^{s_i}d_{ji}Q_i^j
$$
be an $i$-standard expansion of $h$ for $i\ge\ell$, where each $d_{ji}$
is an $\ell$-standard expansion, not involving $Q_\ell $. Note that since
$\alpha_{\ell+t}=1$ for $t\in\mathbb{N}_0$, we have
$$
\deg_xQ_i=\prod\limits_{j=2}^{\alpha_i}\alpha_j=
\prod\limits_{j=2}^{\alpha_\ell }\alpha_j=\deg_xQ_\ell
$$
and so
\begin{equation}
s_i=\left[\frac{\deg_xh}{\deg_xQ_i}\right]=
\left[\frac{\deg_xh}{\deg_xQ_\ell }\right]=s_\ell .\label{tag12.4}
\end{equation}

\begin{proposition}{\label{Proposition12.1}} For each $i$ of the form $i=\ell+t$, $t\in\mathbb{N}$,
we have $b_{i+1}\le b_i$.
\end{proposition}

\begin{proof} Write $Q_{i+1}=Q_i+z_i$, as above.

\begin{lemma}{\label{el12.2}} For any $b\in\mathbb{N}$ we have
\begin{equation}
\frac{\beta_i-\nu'(\partial_bz_i)}b<\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i}.
\label{tag12.5}
\end{equation}
If, in addition, $b\ge b_i$, then
\begin{equation}
\frac{\beta_{i+1}-\nu'(\partial_bz_i)}b<
\frac{\beta_{i+1}-\nu'(\partial_{b_i}Q_i)}{b_i}.\label{tag12.6}
\end{equation}
\end{lemma}

\begin{proof} Let $i'$ denote the smallest ordinal such that
\begin{equation}
\nu_{i'}(z_i)=\nu'(z_i);\label{tag12.7}
\end{equation}
by Proposition \ref{Proposition9.26} (2), $i'<i$. Let
$z_i=\sum\limits_{j=0}^{s_{i'}}c_{ji'}Q_{i'}^j$ be the $i'$-standard
expansion of $z_i$. By Lemma \ref{el10.4} we have
\begin{equation}
\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i}>
\frac{\beta_{i'}-\nu'(\partial_{b_{i'}}Q_{i'})}{b_{i'}}.\label{tag12.8}
\end{equation}
Combining (\ref{tag12.8}) with (\ref{tag10.1}), we obtain
\begin{equation}
\frac{\nu_{i'}(z_i)-\nu_{i'}(\partial_bz_i)}b\le
\frac{\beta_{i'}-\nu_{i'}(\partial_{b_{i'}}Q_{i'})}{b_{i'}}<
\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i},\label{tag12.10}
\end{equation}
which gives the inequality (\ref{tag12.5}). If $b\ge b_i$, (\ref{tag12.6}) follows
immediately by adding the inequality
$\frac{\beta_{i+1}-\beta_i}b\le\frac{\beta_{i+1}-\beta_i}{b_i}$ to
(\ref{tag12.5}).
\end{proof}

\begin{corollary}{\label{Corollary12.3}} We have
\begin{equation}
\nu'(\partial_{b_i}z_i)>\nu'(\partial_{b_i}Q_i)=\nu'(\partial_{b_i}Q_{i+1}).
\label{tag12.11}
\end{equation}
\end{corollary}

\begin{proof} The inequality in (\ref{tag12.11}) is a special case of (\ref{tag12.5}) when
$b=b_i$. The equality in (\ref{tag12.11}) follows immediately
from the inequality.
\end{proof}

To prove Proposition \ref{Proposition12.1}, we argue by contradiction. Suppose that
\begin{equation}
b_{i+1}>b_i.\label{tag12.12}
\end{equation}
Letting $b=b_{i+1}$ in Lemma \ref{el12.2}, we obtain
\begin{equation}
\frac{\beta_{i+1}-\nu'(\partial_{b_{i+1}}z_i)}{b_{i+1}}<
\frac{\beta_{i+1}-\nu'(\partial_{b_i}Q_i)}{b_i}.\label{tag12.13}
\end{equation}
We have
\begin{equation}
\frac{\beta_i-\nu'(\partial_{b_{i+1}}Q_i)}{b_{i+1}}\le
\frac{\beta_i-\nu'(\partial_{b_i}Q_i)}{b_i}\label{tag12.14}
\end{equation}
by definition of $b_i$. Combining (\ref{tag12.14}) with (\ref{tag12.12}), we obtain
\begin{equation}
\frac{\beta_{i+1}-\nu'(\partial_{b_{i+1}}Q_i)}{b_{i+1}}<
\frac{\beta_{i+1}-\nu'(\partial_{b_i}Q_i)}{b_i}.\label{tag12.15}
\end{equation}
We can rewrite (\ref{tag12.13}) and (\ref{tag12.15}) as
\begin{equation}
\min\{\nu'(\partial_{b_{i+1}}Q_i),\nu'(\partial_{b_{i+1}}z_i)\}>
\beta_{i+1}-\frac{b_{i+1}}{b_i}\left(\beta_{i+1}-\nu'(\partial_{b_i}Q_i)\right).
\label{tag12.16}
\end{equation}
Since
$\partial_{b_{i+1}}Q_{i+1}=\partial_{b_{i+1}}Q_i+\partial_{b_{i+1}}z_i$,
(\ref{tag12.16}) shows that
$$
\nu'(\partial_{b_{i+1}}Q_{i+1})>\beta_{i+1}-\frac{b_{i+1}}{b_i}
\left(\beta_{i+1}-\nu'(\partial_{b_i}Q_i)\right),
$$
which contradicts the definition of $b_{i+1}$. This completes the
proof of Proposition \ref{Proposition12.1}.
\end{proof}

By Proposition \ref{Proposition11.2} (1), $\delta_i(h)$ is constant for all $i\gg \ell$. Let
$\delta=\delta_i(h)$ for $i\gg \ell$. Write $\delta=p^eu$, where if $p>1$
then $p\not|u$.

First, assume that $char\ k_\nu=0$. Equations (\ref{tag9.27}) and (\ref{tag11.5})
imply that $d_{\delta-1,\ell}\ne0$ and
\begin{equation}
g_{1\ell}=\bar Q_\ell +\ini_{\nu'}\frac{d_{\delta-1,\ell}}{\delta\
d_{\delta\ell}}.\label{tag12.17}
\end{equation}
Next, suppose $\ch\ k_\nu=p>0$. Then, according to Proposition \ref{Proposition11.2}
(2) and using the notation of (\ref{tag9.24}), we see that for $i\ge\ell$
\begin{equation}
\delta-p^e\in S_i(h,\beta_i)\label{tag12.18}
\end{equation}
(in particular, $d_{\delta-p^e,i}\ne0$) and that
\begin{equation}
\ini_iz_i=\left(\frac{\ini_id_{\delta-p^e,i}}{u\ \ini_id_{\delta
      i}}\right)^{\frac1{p^e}}\label{tag12.19}
\end{equation}
Let $\delta=\delta_i(h)$. We have $v_\ell =\ini_{\nu'}d_{\delta \ell}$ and (\ref{tag9.27})
rewrites as
\begin{equation}
\ini_\ell h=\ini_{\nu'}d_{\delta \ell}g_{1\ell}^\delta.\label{tag12.20}
\end{equation}
Next, we prove a comparison result which expresses the coefficients
$d_{ji}$ in terms of $d_{j\ell}$ for $\delta-p^e\le j\le\delta$, modulo
terms of sufficiently high value.

\begin{proposition}{\label{Proposition12.4}} Take an integer $t>0$ and let $\ell_1=\ell+t$, $\ell_1<i$. Assume that
\begin{equation}
\delta_{i+1}(h)=\delta_\ell (h)=\delta.\label{tag12.21}
\end{equation}
Take an integer $v\in\{\delta-p^e,\delta-p^e+1,\dots,\delta\}$.
We have
\begin{equation}
\begin{aligned}
d_{vi}&\equiv\sum\limits_{j=0}^{\delta-v}(-1)^j\binom{v+j}jd_{v+j,\ell_1}
(z_{\ell_1}+\dots+z_{i-1})^j\\
&\mod\ \mathbf{P'}_{(\nu_{\ell_1}(h)-v\beta_{\ell_1})+\min\{\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),\beta_i-\beta_\ell \}}.
\end{aligned}\label{tag12.22}
\end{equation}
In particular, letting $v=\delta-p^e$ and $v=\delta$ in (\ref{tag12.22}) we obtain
\begin{equation}
\begin{aligned}
d_{\delta-p^e,i}&\equiv\sum\limits_{j=0}^{p^e}(-1)^j\binom{\delta-p^e+j}jd_{\delta-p^e+j,\ell_1}
(z_{\ell_1}+\dots+z_{i-1})^j\\
&\mod\ \mathbf{P'}_{\nu'(d_{\delta-p^e,\ell_1})+\min\{\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),\beta_i-\beta_\ell \}}.
\end{aligned}\label{tag12.23}
\end{equation}
and
\begin{equation}
d_{\delta i}\equiv d_{\delta l_1}\ \mod\
\mathbf{P'}_{\nu'(d_{\delta \ell_1})+\min\{\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),\beta_i-\beta_\ell \}},\label{tag12.24}
\end{equation}
respectively. If $p^e=1$ (in particular, whenever $char\ k_\nu=0$), (\ref{tag12.23})
reduces to
\begin{equation}
d_{\delta-1,i}\equiv d_{\delta-1,\ell_1}-\delta\ d_{\delta \ell_1}(z_{\ell_1}+\dots+z_{i-1})\ \mod\
\mathbf{P'}_{\nu'(d_{\delta-1,\ell_1})+\min\{\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),\beta_i-\beta_\ell \}}.
\label{tag12.25}
\end{equation}
\end{proposition}

\begin{proof} By definitions, we have $Q_i=Q_{\ell_1}+z_{\ell_1}+\dots+z_{i-1}$.
First, we will compare the $\ell$-standard expansion of $h$ with the $i$-standard one. To
this end, we substitute $Q_{\ell_1}=Q_i-z_{\ell_1}-\dots-z_{i-1}$ into the $\ell_1$-standard expansion of
$h$. We obtain
\begin{equation}
h=\sum\limits_{j=0}^{s_{l_1}}d_{j\ell_1}(Q_i-z_{l_1}-\dots-z_{i-1})^j=
\sum\limits_{j=0}^{s_{l_1}}d_{ji}Q_i^j.\label{tag12.26}
\end{equation}
We want to derive information about $\ini_ih$ from (\ref{tag12.26}). First note that for each
$q\in\{0,\dots,s_{\ell_1}-1\}$ we have $\deg_x\sum\limits_{j=0}^qd_{j\ell_1}(Q_i-z_{\ell_1}-\dots-z_{i-1})^j<(q+1)
\deg_xQ_i$. Hence $d_{q+1,i}$ is completely determined by
$d_{q+1,\ell_1},d_{q+2,\ell_1},\dots,d_{s_{\ell_1}\ell_1}$. Next, for
$$
\delta-v<j\le s_{\ell_1}-v
$$
and $\ell_1\le s\le i-1$, note that
\begin{equation}
\nu'\left(d_{v+j,\ell_1}z_s^j\right)\ge j\beta_{\ell_1}+\nu'(d_{v+j,\ell_1})\ge
\nu_{\ell_1}^+(h)-v\beta_{\ell_1},\label{tag12.27}
\end{equation}
so for $\delta-v<j\le s_{\ell_1}-v$ the terms $d_{v+j,\ell_1}Q_{\ell_1}^{v+j}$ in (\ref{tag12.26})
contribute nothing to
$$
d_{vi}\mod\
\mathbf{P'}_{(\nu_{\ell_1}(h)-v\beta_{\ell_1})+\min\{\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),\beta_i-\beta_\ell \}}.
$$
Now, the coefficients $d_{vi}$ in (\ref{tag12.26}) are obtained from
$\sum\limits_{j=0}^{s_{\ell_1}}d_{j\ell_1}(Q_i-z_{\ell_1}-\dots-z_{i-1})^j$ by opening the parentheses (using Newton's Binomial Theorem) and then applying Euclidean division by $Q_i$; such a Euclidean division may change the coefficients $d_{vi}$ by adding terms of value at least $\nu'(d_{v+j,l_1})-(v-k)\beta_{i}+(v+j-k)\beta_{l_1}$ with $0\le k\le v+j$. Using the definition of $\delta$ we observe that for $v$ and $j$ as in (\ref{tag12.22}) we have
$\nu'(d_{v+j,\ell_1})\ge\nu'(d_{\delta\ell_1})+(\delta-v-j)\beta_{\ell_1}=\nu_{\ell_1}(h)-(v+j)\beta_{\ell_1}$. This completes the
proof of (\ref{tag12.22}).

(\ref{tag12.23}) and (\ref{tag12.24}) follow from (\ref{tag12.22}), after observing that
$$
\nu_{\ell_1}(h)=\nu'(d_{\delta \ell_1})+\delta\beta_{\ell_1}=\nu'(d_{\delta-p^e,\ell_1})+(\delta-p^e)\beta_{\ell_1}
$$
by (\ref{tag11.5}). (\ref{tag12.25}) is obtained from (\ref{tag12.23}) by substituting $p^e=1$. The Proposition is proved.
\end{proof}

\begin{proposition}{\label{Proposition12.5}} Assume that there exists $h\in K[x]$ such that
\begin{equation}
\nu_i(h)<\nu'(h)\quad\text{ for all }i\text{ of the form }i=\ell+t,t\in\mathbb{N}_0.\label{tag12.28}
\end{equation}
Take such an $h$ which has the smallest degree. Then the integer $\delta$ is of the form $\delta=p^e$ for
some $e\in\mathbb{N}_0$ (in particular, $\delta=1$ whenever $\ch\ k_\nu=0$).
\end{proposition}

\begin{proof} We give a proof by contradiction. Write
\begin{equation}
\delta=p^ev,\quad\text{ where if }\ch\ k_\nu=p>0\text{ then }p\ \not|\ v.\label{tag12.29}
\end{equation}
Suppose that $v>1$. By Proposition \ref{Proposition12.1}, the sequence $\{b_i\}$ is non-increasing with $t$ and hence stabilizes for $t$ sufficiently large. Let $b_\infty$ denote the stable value of $b_i$. Write $b_\infty=p^{e_\infty}$.
Let $b=p^{e+e_\infty}$ and let $g=\partial_bh$. By Proposition \ref{Proposition11.2} (2), $\ini_ih$ has the form (\ref{tag11.5}) for
$i=\ell+t$, as $t$ runs over $\mathbb{N}_0$. Hence $h$ and $b$ satisfy the hypotheses of Proposition \ref{Proposition10.12}. By Proposition \ref{Proposition10.12} and (\ref{tag11.5}), $g\not\equiv0$ and, for $t$ sufficiently large we have $\ini_ig=v\
\ini_{\nu'}\left(d_{\delta i}\partial_{b_{i}}Q_{i}\right)^{p^{e}}\left(\bar
Q_i+\ini_{\nu'}z_i\right)^{\delta-p^e}$. In particular,
$$
\nu'(g)>\nu'\left(\left(d_{\delta i}\partial_{b_{i}}Q_{i}\right)^{p^{e}}\right)+\delta\beta_{\ell+t}-p^e\beta_{\ell+t}=
\nu'\left(\left(d_{\delta i}\partial_{b_{i}}Q_{i}\right)^{p^{e}}\right)+p^e(v-1)\beta_{\ell+t}=\nu_i(g)
$$
(here is where we are using $v>1$), which contradicts the fact that $h$ has minimal degree among all the polynomials
satisfying $\nu'(h)>\nu_i(h)$.
\end{proof}

\begin{remark}{\label{Remark12.6}} Let the notation be as in Proposition \ref{Proposition12.5}. Assume, in addition, that the sequence
$\left\{\beta_{\ell+t}\right\}$ is unbounded in $\g'_1$. Then for any $h$ satisfying (\ref{tag12.28}) we have  $\nu'(h)\notin\g'_1$. Recall ((\ref{tag9.43})--(\ref{tag9.44})) that, by definition, $Q_{\ell+\omega}$ is the monic polynomial of smallest degree
$\alpha_{\ell+\omega}$, satisfying (\ref{tag12.28}). Let $e_{\ell+\omega}$ be the integer $e$ of Proposition \ref{Proposition12.5} and put $\tilde\alpha_{\ell+\omega}=\frac{\alpha_{\ell+\omega}}{p^{e_{\ell+\omega}}}$.

Assume that $char\ k_\nu=char\ K$ and
\begin{equation}
l=1\quad\text{and}\quad\alpha_t=1\label{tag12.30}
\end{equation}
for all $t\in\mathbb{N}$. In particular, $b_t=1$ for all $t\in\mathbb{N}$, $b_\infty=1$ and $b=p^{e_\omega}$. Then we claim that for all $t\in\mathbb{N}$ the $t$-standard expansion of $Q_\omega$ has the form
\begin{equation}
Q_\omega=\sum\limits_{j=0}^{\tilde\alpha_\omega}c_{jp^{e_\omega},t}Q_t^{jp^{e_\omega}}
\label{tag12.31}
\end{equation}
and for any $b'<b$ we have
\begin{equation}
\partial_{b'}Q_\omega=0.\label{tag12.32}
\end{equation}
Clearly (\ref{tag12.31}) implies (\ref{tag12.32}). We prove (\ref{tag12.31}) by contradiction. Assume the contrary. Let $e'$ denote the greatest non-negative integer such that $Q_\omega\in K\left[x^{p^{e'}}\right]$; by assumption, $e'<e_\omega$. Then $\deg_x\partial_{p^{e'}}Q_\omega<\deg_xQ_\omega$, so there exists $t_0\in\mathbb N$ such that
\begin{equation}
\nu_{t_0}\left(\partial_{p^{e'}}Q_\omega\right)=\nu'\left(\partial_{p^{e'}}Q_\omega\right).\label{eq:stablet}
\end{equation}
Take an integer $t>t_0$. Let $\sum\limits_{p^{e'+1}\ \not|\ j}c_{jt}Q_t^j$ denote the sum of all those monomials appearing in the $t$-standard expansion of $Q_\omega$ whose exponent $j$ is not divisible by $p^{e'+1}$. The operator $\partial_{p^{e'}}$ annihilates all the monomials whose exponents are divisible by $p^{e'+1}$. Thus
\begin{equation}\label{eq:derivativepeprime}
\partial_{p^{e'}}Q_\omega=\partial_{p^{e'}}\left(\sum\limits_{p^{e'+1}\ \not|\ j}c_{jt}Q_t^j\right)=\sum\limits_{p^{e'+1}\ \not|\ j}c_{jt}\binom{j}{p^{e'}}Q_t^{j-p^{e'}}.
\end{equation}
Formulas (\ref{eq:stablet}) and (\ref{eq:derivativepeprime}) imply that the $t$-standard expansion of $Q_\omega$ contains a monomial of the form $c_{p^{e'},t}Q_t^{p^{e'}}$ and that for each $j$ with $p^{e'+1}\ \not|\ j$ we have
$$
\nu_{t_0}\left(c_{jt}Q_t^j\right)\ge\nu'\left(c_{p^{e'},t}Q_t^{p^{e'}}\right).
$$
Then for each $j$ with $p^{e'+1}\ \not|\ j$ and $j>p^{e'}$ we have
$\nu_t\left(c_{jt}Q_t^j\right)>\nu_t\left(c_{p^{e'},t}Q_t^{p^{e'}}\right)$. Hence
\begin{equation}
\nu'\left(c_{jt}Q_t^j\right)>\nu'\left(c_{p^{e'},t}Q_t^{p^{e'}}\right)\text{ for all }j\text{ with }p^{e'+1}\ \not|\ j\text{ and }j>p^{e'}.\label{eq:greatervalue}
\end{equation}
We obtain that for all $t$ sufficiently large the $t$-standard expansion of $Q_\omega$ contains a monomial of the form $c_{p^{e'},t}Q_t^{p^{e'}}$ and all the other monomials not divisible by $Q_t^{p^{e'+1}}$ have values strictly greater than $\nu'\left(c_{p^{e'},t}Q_t^{p^{e'}}\right)$.

Then for all $t'>t$ we have $\nu\left(c_{p^{e'},t}\right)=\nu\left(c_{p^{e'},t'}\right)$. Choosing $t'$ sufficiently large, we obtain $\nu'\left(c_{p^{e'},t'}Q_{t'}^{p^{e'}}\right)<\nu'\left(c_{\delta,t'}Q_{t'}^\delta\right)$, which contradicts the definition of $\delta$. This completes the proof of (\ref{tag12.31}) and (\ref{tag12.32}).

Equation (\ref{tag12.32}) implies that for all the monomials $Q_t^a$ appearing
in $Q_\omega$ with non-zero coefficients, we have $\left.p^{e_\omega}\ \right|\
a$ (in fact, by a similar argument this statement can be proved not
only for $Q_\omega$, but for any $h$ satisfying (\ref{tag12.28})).
\end{remark}

\begin{remark}{\label{Remark12.7}} Keep the assumption that
$\left\{\beta_{\ell+t}\right\}$ is unbounded in $\g'_1$, as well as
(\ref{tag12.30}), but now assume that $char\ K=0$ and $char\ k_\nu=p>0$. By
studying the coefficient of $Q_t^{\delta-1}$ in the $t$-standard
expansion of $Q_\omega$ for different $t$, one can prove that
$\delta=p^e=1$.
\end{remark}

\begin{proposition}{\label{Proposition12.8}} Assume that the sequence $\{Q_i\}$ is infinite
and that there exists $h\in K[x]$, satisfying (\ref{tag12.28}). Take
one such $h$, whether or not it has the smallest degree. Assume that
$p^e=1$ in the notation of (\ref{tag12.29}) (in other words, either $\ch\
k_\nu=0$ or $\ch\ k_\nu=p>0$ and $p\ \not|\ \delta$). Then the
sequences
\begin{equation}
\nu_i(h)\label{tag12.34}
\end{equation}
and
\begin{equation}
\{\beta_i\}_{t\in\mathbb{N}}\label{tag12.35}
\end{equation}
are unbounded in $\g'_1$ (recall that we are assuming $rk\ \nu=1$).
\end{proposition}

\begin{proof} Proposition \ref{Proposition11.2} (2) implies that
$\nu_i(h)=\delta\beta_i+\nu'(d_{\delta i})$ and that $\nu'(d_{\delta i})$ is independent of $i$. Thus to show that the sequence
(\ref{tag12.34}) is unbounded in $\g'_1$ it is sufficient to show that (\ref{tag12.35}) is unbounded in $\g'_1$.

Moreover, to prove that (\ref{tag12.35}) is unbounded, it is sufficient to show that the set $\nu'(T)$ itself is unbounded in $\g'_1$.

To prove the unboundedness of $\nu'(T)$, let $\ell_1=\ell+1$. Let $d^*_{\delta \ell_1}\in K[x]$ denote the
unique polynomial of degree strictly less than $\deg_x Q_\ell =\deg_x
Q_{\ell_1}$ such that $d^*_{\delta \ell_1}d_{\delta \ell_1}-1$ is divisible by
$Q_{\ell_1}$ in $K[x]$. We have $\nu_{\ell_1}(d^*_{\delta
  \ell_1})=\nu'(d^*_{\delta \ell_1})$ by Proposition \ref{Proposition9.26} (2), hence
$\nu_i(d^*_{\delta \ell_1})=\nu'(d^*_{\delta \ell_1})$ for all $i\ge
\ell_1$. Multiplying $h$ by $d^*_{\delta \ell_1}$ does not affect
$\delta$. Thus multiplying $h$ by $d^*_{\delta \ell_1}$ does not change
the problem. Therefore we may assume that
\begin{equation}
\ini_{\nu'}d_{\delta i}=\ini_id_{\delta i}=1\text{ for all }i\text{ of the form }\ell+t,\ t\in\mathbb{N}.\label{eq:ddelta=1}
\end{equation}
Clearly, the result of the Proposition does not depend on the choice of $z_{\ell+t}$ and $Q_{\ell+t}$ which was made in
\S\ref{Section3}. We will now modify our choice of $z_{\ell+t}$ and $Q_{\ell+t}$ in such a way as to make the unboundedness $\nu'(T)$ obvious.

In view of (\ref{eq:ddelta=1}), we have
\begin{equation}
\ini_{\ell_1}h=\ini_{\ell_1}\left(Q_{\ell_1}+z_{\ell_1}\right)^\delta=\sum\limits_{j=1}^\delta\ini_\nu d_j\ini_{\ell_1}Q_\ell^j.
\label{eq:binomial}
\end{equation}
Comparing the coefficients of $\ini_\ell Q_\ell^{\delta-1}$ on the right and the left hand side of (\ref{eq:binomial}), we obtain
\begin{equation}
\ini_{\nu'}z_{\ell_1}=\ini_{\nu'}\frac{d_{\delta-1,\ell_1}}\delta;\label{eq:iniequal}
\end{equation}
In particular,
\begin{equation}
\nu'(Q_{\ell_1})<\nu'\left(Q_{\ell_1}+\frac{d_{\delta-1,\ell_1}}\delta\right);\label{tag12.39}
\end{equation}
By (\ref{tag12.39}), $Q_{\ell_1}+\frac{d_{\delta-1,\ell_1}}\delta\in T$. Replace $z_{\ell_1}$ by $\frac{d_{\delta-1,\ell_1}}\delta$, in other words, put
$$
z_{\ell_1}:=\frac{d_{\delta-1,\ell_1}}\delta.
$$
and $Q_{\ell+2}=Q_{\ell_1}+\frac{d_{\delta-1,\ell_1}}\delta$. We now iterate the procedure. Precisely, assume that
$z_{\ell+1},\dots z_{\ell+t}$ and $Q_i$ for $i\le\ell+t+1$ are already constructed. Put
$$
z_{\ell+t+1}:=\frac{d_{\delta-1,\ell+t}}\delta
$$
and $Q_{\ell+t+2}=Q_{\ell+t+1}+z_{\ell+t+1}$. This completes the recursive construction. Notice that all the elements $z_{\ell+t}$ and
$Q_{\ell+t}$ lie in a fixed noetherian ring $A$, namely, the $\mathbb Z\left[\frac1\delta\right]$-subalgebra of $K[x]$, generated by $x$ and the finitely many coefficients of the polynomial $Q_\ell$.
\begin{lemma}\label{noboundedsequences} Let $\mu$ be a rank one valuation with value group $\Gamma_1$, centered in a
local noetherian domain $(R,M,k)$ (that is, non-negative on $R$ and strictly positive
on $M$). Let
$$
\Phi=\mu(R\setminus\{0\})\subset\g_1.
$$
Then $\Phi$ contains no infinite bounded sequences.
\end{lemma}
\begin{proof} An infinite ascending sequence $\alpha_1<\alpha_2<\dots$ in
$\Phi$, bounded above by an element $\beta\in\Phi$, would give rise to an
infinite descending chain of ideals in $\frac R{I_\beta}$, where $I_\beta$ denotes the $\mu$-ideal of $R$ of value $\beta$. Thus it is
sufficient to prove that $\frac R{I_\beta}$ has finite length.

Let $\delta:=\mu(M)\equiv\min(\Phi\setminus\{0\})$. Since $\mu$ is of rank one, there exists $n\in\mathbb N$ such that $\beta\le
n\delta$. Then $M^n\subset I_\beta$, so that there is a surjective map $\frac
R{M^n}\twoheadrightarrow\frac R{I_\beta}$. Thus $\frac R{I_\beta}$ has
finite length, as desired.
\end{proof}
Coming back to the proof of the Proposition, let
$H=\{a\in A\ |\ \nu'(a)\notin\Gamma'_1\}$ and $M=\{a\in A\ |\ \nu'(a)>0\}$. Applying Lemma \ref{noboundedsequences} to the local noetherian ring $\frac{A_M}{HA_M}$ and using the fact that the sequence $\beta_i$ is strictly increasing with $i$, we obtain that
$\{\beta_i\}$ is unbounded in $\Gamma'_1$, as desired.
\end{proof}

\section{Sequences of key polynomials with bounded values in fields of positive characteristic}\label{Section7}

In this section, we assume that $\ch\ k_\nu=p>0$. Let $\ell$ be an ordinal number
and assume that the key polynomials $\mathbf{Q}_\ell \cup\{Q_{\ell+t}\}_{t\in\mathbb{N}_0}$ are already defined. Moreover, assume that we are in Case 2b of \S3 (in other words,
the sequence $\{\beta_{\ell+t}\}_{t\in\mathbb{N}_0}$ has an upper bound $\bar\beta$ but no maximum in $\Gamma'_1$; this is the only case which remains to be treated to complete the definition of the $Q_i$). If for every $h\in K[x]$ there exists $t\in\mathbb{N}$ such that $\nu_{\ell+t}(h)=\nu'(h)$; there is nothing more to do: the set $\mathbf{Q}_{\ell+\omega}$ is already defined and is complete. Assume that there exists $f\in K[x]$ such that
\begin{equation}
\nu_{\ell+t}(f)<\nu'(f)\quad\text{ for all }t\in\mathbb{N}.\label{tag13.1}
\end{equation}
By Proposition \ref{Proposition11.2} and Corollary \ref{Corollary11.8}, there exists $t_0\in\mathbb{N}_0$ such that
\begin{equation}
\alpha_{\ell+t}=1\ \text{ and }\ \delta_{\ell+t}(f)=\delta_{\ell+t_0}(f)\ \text{ for all }\ t\ge t_0.\label{tag13.2}
\end{equation}
Let $\delta(f)$ denote the stable value $\delta_{\ell+t}(f)$ for large $t$. Among such polynomials $f$, pick one which
minimizes $\delta(f)$. By Proposition \ref{Proposition12.5}, $\delta(f)$ is of the form
$\delta(f)=p^{e_0}$ for some $e_0\in\mathbb{N}_0$. Moreover, we have $e_0>0$ for, by Proposition \ref{Proposition12.8} $\delta=1$ is
incompatible with Case 2b.

Replacing $\ell$ by $\ell+s$ for a suitable positive integer $s$, we may
assume that $\alpha_{\ell+t}=1$ for all strictly positive $t$.
In what follows, the index $i$ will run over the set $\{\ell+t\}_{t\in\mathbb{N}_0}$. As
usual, let $\delta=\delta(f)$.

\begin{proposition}{\label{Proposition13.1}} There exist $i\in\{\ell+t\}_{t\in\mathbb{N}_0}$ and a weakly affine $i$-standard expansion
$Q_{\ell+\omega}$, monic of degree $p^{e_0}$ in $Q_i$, such that
\begin{equation}
\bar\beta\le\frac1{p^{e_0}}\nu\left(Q_{\ell+\omega}\right).\label{tag13.3}
\end{equation}
\end{proposition}

Of course, the inequality (\ref{tag13.3}) is equivalent to saying that
\begin{equation}
\nu'\left(Q_{\ell+\omega}\right)>p^{e_0}\nu'\left(Q_\ell +z_\ell +\dots+z_{\ell+t}\right)\label{tag13.4}
\end{equation}
for all $t\in\mathbb{N}_0$.

\begin{proof} The idea is to gradually modify the polynomial $f$ until we arrive at $g=Q_{\ell+\omega}$ satisfying the conclusion of the Proposition.

For $i$ of the form $\ell+t$, $t\in\mathbb{N}$, let
\begin{equation}
f=\sum\limits_{j=0}^{n_i}a_{ji}Q_i^j\label{tag13.5}
\end{equation}
be the $\ell$-standard expansion of $f$. Let $a^*$ be an $\ell$-standard expansion, not involving $Q_\ell $, such that
\begin{equation}
a^*a_{\delta \ell}\equiv 1\ \md\ Q_\ell .\label{tag13.6}
\end{equation}
Note that
\begin{equation}
\ini_{\nu'}a_{\delta \ell}=\ini_{\nu'}a_{\delta i}\quad\text{ for all }i\ge \ell\label{tag13.7}
\end{equation}
by Proposition \ref{Proposition11.2} (2).

Let $\tilde f=a^*f$. By Proposition \ref{Proposition11.2} (2), for all $i\ge \ell$ we have
$$
\ini_if=\ini_{\nu'}a_{\delta i}(\bar Q_i+\ini_{\nu'}z_i)^\delta,
$$
hence in view of (\ref{tag13.6})--(\ref{tag13.7}) we have $\ini_i\tilde f=(\bar Q_i+\ini_{\nu'}z_i)^\delta$. In particular,
\begin{equation}
\nu'(\tilde f)>\nu_i(\tilde f)\quad\text{ for all }i.\label{tag13.8}
\end{equation}
Multiplying by $a^*$ does not affect $\delta$. Thus, replacing $f$ by $\tilde f$, we may assume that
$\ini_{\nu'}a_{\delta i}=1$ for all $i$.

As noted in the previous section (\ref{tag12.4}), since $\alpha_i=1$ for all $i$, all the $i$-standard
expansions of $f$ have the same degree $n_\ell$ in $Q_i$.

Let
\begin{equation}
\theta(i)=\min\{\nu_i^+(h)-\nu_i(h),\beta_i-\beta_\ell \};\label{tag12.36}
\end{equation}
we have $\theta(i)>0$.
\begin{lemma}{\label{el12.9}} We have
\begin{equation}
\nu_{l_2}^+(h)-\nu_{l_2}(h)\ge\nu_{l_1}^+(h)-\nu_{l_1}(h).\label{tag12.41}
\end{equation}
\end{lemma}

\begin{proof} By Proposition \ref{Proposition11.2}, $\nu'(d_{\delta \ell_2})=\nu'(d_{\delta \ell_1})$ and
$\nu'(d_{\epsilon \ell_2})=\nu'(d_{\epsilon \ell_1})$. Hence
\begin{align*}
\nu_{\ell_2}^+(h)-\nu_{\ell_2}(h)&=\nu'(d_{\epsilon 	\ell_2})-\nu'(d_{\delta \ell_2})+(\epsilon-\delta)\beta_{\ell_2}\ge\\
&\ge\nu'(d_{\epsilon \ell_1})-\nu'(d_{\delta \ell_1})+(\epsilon-\delta)\beta_{\ell_1}=\nu_{\ell_1}^+(h)-\nu_{\ell_1}(h),
\end{align*}
and the Lemma is proved.
\end{proof}

By Lemma \ref{el12.9} the quantity $\nu_i^+(f)-\nu_i(f)$ is increasing with $i$ and hence so is
$\theta_i(f)$. Taking into account the fact that $\bar\beta=\lim\limits_{i\to\infty}\beta_i$, we have, for $i$ sufficiently large,
\begin{equation}
\nu'(a_{i\delta})+\delta\bar\beta-\nu_i(f)=\delta(\bar\beta-\beta_i)<\theta_i(f).
\label{tag13.9}
\end{equation}
By choosing $\ell_1>\ell$ sufficiently large, we may assume that (\ref{tag13.9}) holds for $i\ge \ell_1$.

Next, write $a_{\delta i}=1+a_i^\dag$ with $\nu'\left(a_i^\dag\right)>0$. Write
$$
f=\bar f+\tilde f,
$$
where
$$
\bar f=Q_{\ell_1}^\delta+\sum\limits_{j=0}^{\delta-1}a_{j\ell_1}Q_{\ell_1}^j
$$
and
$$
\tilde f=a_{\ell_1}^\dag Q_{\ell_1}^\delta+\sum\limits_{j=\delta+1}^{n_\ell }a_{j\ell_1}Q_{\ell_1}^j.
$$
(\ref{tag13.9}) implies that for all $j$ with $\delta<j\le n_\ell $, and all $i$, we have
$$
\nu_i\left(a_{j\ell_1}Q_{\ell_1}^j\right)\ge\nu_{\ell_1}\left(a_{j\ell_1}Q_{\ell_1}^j
\right)\ge\nu_{\ell_1}^+(f)>\delta\bar\beta>\delta\beta_i=\nu_i(f).
$$
Also from (\ref{tag13.9}), we see that
$$
\nu_i\left(a^\dag_{\ell_1}Q_{\ell_1}^\delta\right)\ge\nu_{\ell_1}
\left(a^\dag_{\ell_1}Q_{\ell_1}^\delta\right)=
\nu_{\ell_1}\left(a^\dag_{\ell_1}\right)+\delta\beta_{\ell_1}>\delta\bar\beta>\nu_i(f).
$$
Hence, for all $i$, $\nu'(\tilde f)\ge\nu_i(\tilde f)>\nu_i(\bar f)$ which implies that $\nu_i(\bar f)=\nu_i\left(\bar
f\right)<\nu'\left(\bar f\right)$; we have $\ini_if=\ini_i\bar f$. Thus, replacing $f$ by $\bar f$, we may assume that the polynomial $f$ is monic of degree $\delta\deg_xQ_\ell $. None of the subsequent transformations
$$
Q_i=Q_{\ell_1}+z_{\ell_1}+\dots+z_{i-1}
$$
affect the coefficient $a_{\delta \ell_1}=1$, so $a_{\delta i}=1$ for all $i$.

Choose $i_0\ge \ell_1$ sufficiently large so that
\begin{equation}
\beta_{i_0}-\alpha_\ell \beta_{\ell-1}>2p^{e_0}(\bar\beta-\beta_{i_0}).\label{tag13.10}
\end{equation}

\begin{remark}{\label{Remark13.2}} Assume that there exist $i\ge i_0$ and $j$, $1\le j<p^{e_0}$, such that
$$
\nu'(a_{ji})+j\bar\beta\ge2p^{e_0}\bar\beta-p^{e_0}\beta_i.
$$
Then for any $i'\ge i$ we have
$$
\nu_{i'}\left(a_{ji}Q_i^j\right)=\nu'\left(a_{ji}Q_i^j\right)>2p^{e_0}\bar\beta-p^{e_0}\beta_i+j\beta_i-j\bar\beta>p^{e_0}\bar\beta>
p^{e_0}\beta_{i'}.
$$
Hence $\ini_{i'}\left(f-a_{ji}Q_i^j\right)=\ini_{i'}f$ and
$$
\nu_{i'}\left(f-a_{ji}Q_i^j\right)<\nu'\left(f-a_{ji}Q_i^j\right).
$$
Thus we are free to replace $f$ by $f-a_{ji}Q_i^j$.
\end{remark}
\begin{definition}{\label{de13.3}} Take an $i\ge i_0$. Consider an $i$-standard expansion (\ref{tag13.5}) of $f$ and let $a_{ji}Q_j^i$ be a non-zero monomial appearing in this expansion. We say that $a_{ji}Q_j^i$ is {\bf bad} if
\begin{equation}
\nu'(a_{ji})+j\bar\beta<2p^{e_0}\bar\beta-p^{e_0}\beta_i.\label{tag13.11}
\end{equation}
and at least one of the following three conditions holds:
\begin{enumerate}
\item[(1)]
\begin{equation}
\nu'(a_{ji})<(p^{e_0}-j)\bar\beta\label{tag13.12}
\end{equation}
\item[(2)] $j$ is not a power of $p$
\item[(3)]
\begin{equation}
\nu'(a_{ji})>(p^{e_0}-j)\bar\beta.\label{tag13.13}
\end{equation}
\end{enumerate}
\end{definition}

In view of Remark \ref{Remark13.2}, to say that the $i$-standard expansion (\ref{tag13.5}) satisfies the conclusion of Proposition \ref{Proposition13.1} is equivalent to saying that it contains no bad monomials, in which case there is nothing more to do. Assume that there exists at least one bad monomial. Let $j(i)$ denote the greatest $j\in\{1,...,p^{e_0}-1\}$ such that the monomial $a_{ji}Q_j^i$ is bad. Let $j^\bullet(i)$ denote the element $j\in\{1,...,p^{e_0}-1\}$ which minimizes the pair $(\nu'(a_{ji})+j\beta_i,-j)$ in the lexicographical ordering among all the elements of $\{1,...,p^{e_0}-1\}$ such that the monomial $a_{ji}Q_j^i$ is bad.

Take $i\ge i_0$. To finish the proof of Proposition \ref{Proposition13.1}, we will first prove the following three Lemmas:

\begin{lemma}{\label{el13.4}} We have
\begin{equation}
j(i+1)\le j(i)\label{tag13.14}
\end{equation}
and
\begin{equation}
j^\bullet(i+1)\le j^\bullet(i).\label{tag13.15}
\end{equation}
If $j\in\{j(i),j^\bullet(i)\}$ then
\begin{equation}
\ini_{\nu'}a_{j,i+1}=\ini_{\nu'}a_{ji}.\label{tag13.16}
\end{equation}
\end{lemma}

\begin{lemma}{\label{el13.5}} If $j\in\{j(i),j^\bullet(i)\}$ then (\ref{tag13.12}) does not hold.
\end{lemma}

\begin{lemma}{\label{el13.6}} If $j=j(i)$ then (\ref{tag13.13}) holds.
\end{lemma}

According to Lemmas \ref{el13.5} and \ref{el13.6}, if $j=j(i)$ then (\ref{tag13.13}) must
hold. In that case, we will prove that increasing $i$, if necessary,
and replacing $f$ by $f-a_{ji}Q_j^i$ preserves the strict inequality
(\ref{tag13.1}) for all $t$ and either eliminates the last bad monomial or
strictly decreases $j(i)$.

At that point the proof of Proposition \ref{Proposition13.1} will be finished by
induction on $j(i)$.

\begin{proof}[Proof of Lemma \ref{el13.4}] First, suppose $j=j(i)$. Since $j$ is the
greatest element of $\{1,...,p^{e_0}-1\}$ satisfying (\ref{tag13.11}), and one
of the conditions (1)--(3) of Definition \ref{de13.3}, any $j'\in\{j+1\do p^{e_0}-1\}$
satisfying (\ref{tag13.11}) is a power of $p$ and
\begin{equation}
\nu(a_{j'i})=(p^{e_0}-j')\bar\beta.\label{tag13.17}
\end{equation}
We want to analyze the monomial $a_{j,i+1}Q_{i+1}^j$ in the
$(i+1)$-standard expansion of $f$. To do that, write
\begin{equation}
f=\sum\limits_{j'=0}^{\delta}a_{j'i}(Q_{i+1}-z_i)^{j'}.\label{tag13.18}
\end{equation}
Now, terms in (\ref{tag13.18}) with $j'<j$ do not affect the statement of the
Lemma. We claim that the same is true of the terms with
$j'>j$. Indeed, take a
$$
j'\in\{j+1\do \delta\}.
$$
Write $j'=p^{e'}$. Then
\begin{equation}
a_{j'i}(Q_{i+1}-z_i)^{j'}=a_{j'i}Q_{i+1}^{p^{e'}}-a_{j'i}z_i^{p^{e'}}.\label{tag13.19}
\end{equation}
In general, the right hand side of (\ref{tag13.19}) need not be an
$(i+1)$-standard expansion, since $\deg_xa_{j'i}z_i^{p^{e'}}$ may be
quite large, even as large or larger than
$\deg_xQ_{i+1}^{p^{e'}}$. However, the $(i+1)$-standard expansion of
$a_{j'i}(Q_{i+1}-z_i)^{p^{e'}}$ is obtained from it by iterating
Euclidean division by $Q_{i+1}$. The first Euclidean division we
perform consists of writing $a_{j'i}z_i^{p^{e'}}=Q_{i+1}g+h$ with
$\deg_xh<\deg_xQ_{i+1}$. We have
$$
\nu_{\ell-1}\left(a_{j'i}z_i^{p^{e'}}\right)=\nu'\left(a_{j'i}z_i^{p^{e'}}\right)=
\nu_{i+1}\left(a_{j'i}z_i^{p^{e'}}\right),
$$
$$
\nu_{\ell-1}(h)=\nu'(h)=\nu_{i+1}(h)
$$
and
$$
\nu_{i+1}(Q_{i+1}g)-\nu_{\ell-1}(Q_{i+1}g)\ge\nu_{i+1}(Q_{i+1})-\nu_{\ell-1}(Q_{i+1})=
\beta_{i+1}-\alpha_\ell \beta_{\ell-1}.
$$
Hence $\nu_{i+1}(Q_{i+1}g)-(\beta_{i+1}-
\alpha_\ell \beta_{\ell-1})\ge\nu_{i+1}\left(a_{j'i}z_i^{p^{e'}}\right)=\nu_{i+1}(h)\ge
p^{e_0}\beta_i$. This implies that all the new monomials appearing
after all the subsequent Euclidean divisions have $\nu_{i+1}$-value
greater than or equal to
$p^{e_0}\beta_i+(\beta_{i+1}-\alpha_\ell \beta_{\ell-1})$, and hence, in view
of (\ref{tag13.10})-(\ref{tag13.11}), strictly greater than
$\nu'(a_{ji})+j\beta_{i+1}$. In particular, if such a new monomial is
of the form $dQ_{i+1}^j$, with $d$ and $(i+1)$-standard expansion not
involving $Q_{i+1}$, we have $\nu'(d)>\nu'(a_{ji})$. This proves that
the passage to an $(i+1)$-standard expansion does not affect
$\ini_{\nu'}a_{ji}$, and (\ref{tag13.16}) holds for $j=j(i)$.

The fact that all the new monomials arising from iterated Euclidean
divisions of
$$
a_{j'i}(Q_{i+1}-z_i)^{p^{e'}},\qquad j'>j,
$$
have $\nu_{i+1}$-value greater than or equal to
$$
p^{e_0}\beta_i+(\beta_{i+1}-\alpha_\ell \beta_{\ell-1}),
$$
together with (\ref{tag13.10})--(\ref{tag13.11}) also shows that after the passage to
the $(i+1)$-standard expansion, no new bad monomials
$a_{j',i+1}Q_{i+1}^{j'}$ are produced with $j'>j$ (the monomial
$a_{j,i+1}Q_{i+1}^j$ may or may not be bad). This proves (\ref{tag13.14}).

The proof of the Lemma in the case $j=j^\bullet(i)$ is very similar to
that of $j=j(i)$, except for the following minor change. We can no longer assert that $j'$ is a power of $p$. On the other hand, $j'$ satisfies $\nu(a_{j'i})+j'\beta_i>\nu_i(f)$, which allows us to use similar arguments as in the $j=j(i)$ case. This completes the proof of Lemma \ref{el13.4}.
\end{proof}

\begin{proof}[Proof of Lemma \ref{el13.5}] We give a proof by contradiction. Suppose that
$j=j(i)$ and that (\ref{tag13.12}) holds for this $j$. (\ref{tag13.12}) can be rewritten
as $\nu'(a_{ji})+j\bar\beta<p^{e_0}\bar\beta$. Combining this with
(\ref{tag13.16}) we obtain that (\ref{tag13.12}) holds with $i$ replaced by $i+1$,
\begin{equation}
\nu'(a_{j,i+1})+j\bar\beta<2p^{e_0}\bar\beta-p^{e_0}\beta_{i+1}.\label{tag13.20}
\end{equation}
so the monomial $a_{j,i+1}Q_{i+1}^j$ is also bad and $j(i+1)=j(i)$. By
induction on $i'\ge i$ we see that $j(i')$ is independent of $i'$, so
the $i'$-standard expansion of $f$ contains a monomial
$a_{ji'}Q_{i'}^j$ with
$$
\nu'\left(a_{ji'}Q_{i'}^j\right)=\nu'(a_{ji'})+j\beta_{i'}=
\nu'(a_{ji})+j\beta_{i'}<\nu'(a_{ji})+j\bar\beta.
$$
Then
$p^{e_0}\beta_{i'}=\nu_{i'}(f)<\nu'(a_{ji})+j\bar\beta<p^{e_0}\bar\beta$
for all $i'$, hence the least upper bound of $\beta_{i'}$ is bounded
above by $\frac1{p^{e_0}}\nu'(a_{ji})+j\bar\beta$ and hence is
strictly less than $\bar\beta$. This contradicts the definition of $\bar\beta$.

The proof in the case $j=j^\bullet(i)$ is similar to that with
$j=j(i)$ and we omit it.
\end{proof}

\begin{proof}[Proof of Lemma \ref{el13.6}] We argue by contradiction. Assume that $j=j(i)$
and that (\ref{tag13.13}) does not hold. In view of Lemma \ref{el13.5} this implies that
\begin{equation}
\nu'(a_{ji})+j\bar\beta=p^{e_0}\bar\beta.\label{tag13.21}
\end{equation}
Then, by definition of $j(i)$, $j$ is not a $p$-power. Write $j=p^eu$, $u\ge2$ and $p\ \not|\ u$, and
$$
Q_{i+1}=Q_i+z_i.
$$
Lemma \ref{el13.5}, applied to $j^\bullet(i)$, implies that
\begin{equation}
\nu'(a_{j'i})+j'\bar\beta\ge p^{e_0}\bar\beta\qquad\text{for all }j'\in\{1,\dots,p^{e_0}\}.\label{tag13.21bis}
\end{equation}
Arguing as in the proof of Lemma \ref{el13.4}, we can show that $j(i')$ remains unchanged as $i'$ increases. Take $i'\ge i$ sufficiently large so that $\nu_{i'}\left(\partial_{p^e(u-1)}f\right)=\nu'\left(\partial_{p^e(u-1)}f\right)$. Arguing as in Remark \ref{Remark12.6} (specifically, in the proof of (\ref{tag12.31})), we show that the
$(i'+1)$-standard expansion of $f$ contains a monomial of the form $a_{p^e,i'+1}Q_{i'+1}^{p^e}$ with
$\nu'(a_{p^e,i'+1})+p^e\beta_{i'+1}<\nu'(a_{j,i'+1})+j\beta_{i'+1}$. Then
$\nu'(a_{p^e,i'+1})+p^e\bar\beta<\nu'(a_{j,i'+1})+j\bar\beta$, which contradicts (\ref{tag13.21}) and (\ref{tag13.21bis}).

This completes the proof of Lemma \ref{el13.6}.
\end{proof}

Let $j=j(i)$. By Lemmas \ref{el13.5} and \ref{el13.6} the inequality (\ref{tag13.13}) holds for $j$.

By Lemma \ref{el13.4} (\ref{tag13.16}), $\ini_{\nu'}a_{ji}$ cannot be affected by any subsequent coordinate changes of the form
$$
Q_{i'}=Q_i+z_i+\dots+z_{i'-1}.
$$
Since $\bar\beta-\beta_{i'}$ can be made arbitrarily small as $t\to\infty$, by (\ref{tag13.13}), taking $i_1$ sufficiently large, we can ensure that
\begin{equation}
\nu'\left(a_{ji}Q_{i_1}^j\right)>2p^{e_0}\bar\beta-p^{e_0}\beta_{i_1}.\label{tag13.27}
\end{equation}
Take the smallest $i_1$ satisfying (\ref{tag13.27}). By the minimality of $i_1$, Lemma \ref{el13.4} (\ref{tag13.16}) and induction on
$i'$, $i\le i'\le i_1$, we see that the monomial $a_{ji'}Q_{i'}^j$ remains bad for $i\le i'<i_1$ and that
\begin{equation}
\nu'\left(a_{ji}\right)=\nu'\left(a_{ji_1}\right).\label{tag13.28}
\end{equation}
From (\ref{tag13.27})--(\ref{tag13.28}) we obtain
\begin{equation}
\nu'\left(a_{ji_1}Q_{i_1}^j\right)>2p^{e_0}\bar\beta-p^{e_0}\beta_{i_1}.\label{tag13.29}
\end{equation}
Replace $f$ by $f-a_{ji_1}Q_{i_1}^j$; Remark \ref{Remark13.2} says that strict inequality (\ref{tag13.1}) is satisfied with $f$ replaced by $f-a_{i_1j}Q_{i_1}^j$. This procedure strictly decreases the integer $j(i)$. Hence after finitely many repetitions of this procedure we obtain a polynomial $f$ containing no bad monomials. The non-existence of bad monomials is preserved as we pass from $i$ to $i+1$. Thus, by choosing $i$ sufficiently large, we may assume that $f$ contains no bad monomials; we will make this assumption from now on.

If $Q_{\ell+\omega}=f$ satisfies the conclusion of Proposition \ref{Proposition13.1} there is nothing more to prove.

Otherwise, there exists $j\in\{1,\dots,p^e-1\}$ such that
\begin{equation}
\nu(a_{ji})+j\bar\beta>2p^{e_0}\bar\beta-p^{e_0}\beta_i.\label{tag13.30}
\end{equation}
Let ${\mathcal A}$ denote the set of all such $j$. Replace $f$ by $f-\sum\limits_{j\in{\mathcal A}}a_{ji}Q_i^j$. Remark \ref{Remark13.2}
says that strict inequality (\ref{tag13.1}) is satisfied for this new $f$. In this way, we obtain a polynomial $f$ such that $Q_{\ell+\omega}=f$ satisfies the conclusion of Proposition \ref{Proposition13.1}. This completes the proof of Proposition \ref{Proposition13.1}.
\end{proof}

\begin{remark}{\label{Remark13.7}} By a reasoning similar to that of Lemma \ref{el13.4}, the sets
$$
{\mathcal S}:=\left\{\ j\in\{1,...,p^{e_0}\}\left|\ a_{ji}\ne0\text{ and }\nu(a_{ji})=(p^{e_0}-j)\bar\beta\right.\right\}
$$
and $\left\{\left.\ini_{\nu'}a_{ji} \right|\ j\in{\mathcal S}\right\}$ are independent of $i$ for $i\ge i_0$.
\end{remark}

\begin{remark}{\label{Remark13.8}} We do not claim that the property that $f$ is a weakly affine expansion in $Q_i$ is preserved when we pass from $i$ to some other ordinal $i'>i$. However, the above results show that for any $i'\ge i$ of the form $i'=\ell+t$, $t\in\mathbb{N}_0$, $f$ is a sum of a weakly affine expansion in $Q_{i'}$ all of whose monomials $a_{ji'}Q_{i'}^j$ for $j>0$ lie on the critical line $\nu'(a_{ji})=(p^{e_0}-j)\bar\beta$ and another standard expansion of degree strictly less than $p^{e_0}$ in $Q_i$, all of whose monomials have value greater than or equal to
$2p^{e_0}\bar\beta-p^{e_0}\beta_{i'}$.
\end{remark}
We define $Q_{\ell+\omega}$ to be a weakly affine standard expansion satisfying the conclusion of Proposition \ref{Proposition13.1}. By
construction, this $Q_{\ell+\omega}$ minimizes the integer $e_0$ among all the polynomials $f$ satisfying (\ref{tag13.1}) (so that
$\alpha_{\ell+\omega}=p^{e_0}$). This completes the definition of the $Q_i$.

Let $\theta_{\ell+\omega}(f)=\frac\delta{\alpha_{\ell+\omega}}$. It is easy to see, by the same argument as in Lemma
\ref{el11.4}, that the Newton polygon $\Delta_{\ell+\omega}(f)$ contains a vertex
$(\nu'(a_{\theta_{\ell+\omega}(f)}),\theta_{\ell+\omega}(f))$,
and that this vertex lies above the pivotal vertex $(\nu'(a_{\delta_{\ell+\omega}(f)}),\delta_{\ell+\omega}(f))$. The vertex
$(\nu'(a_{\theta_{\ell+\omega}(f)}),\theta_{\ell+\omega}(f))$ will be called the {\bf characteristic vertex} of
$\Delta_{\ell+\omega}(f)$.

\begin{remark}{\label{Remark13.9}} By construction, we have $\alpha_{\ell+\omega}=p^{e_0}\ge p$.
\end{remark}

\subsection*{Proof that $\{Q_i\}$ is a complete set of key polynomials}

\begin{theorem}{\label{th13.10}} The well ordered set $\mathbf{Q}:=\{Q_i\}$ defined above is a complete set of key polynomials.
In other words, for any element $\beta\in\Gamma'_+$ the $R_\nu$-module $\mathbf{P'}_\beta\cap K[x]$ is generated as an
additive group by all the monomials in the $Q_i$ of value $\beta$ or higher, multiplied by elements of $K$. In particular, we have
$$
\bigoplus\limits_{\beta\in\Gamma'}\frac{\mathbf{P'}_\beta}{\mathbf{P'}_{\beta+}}=G_\nu[\ini_{\nu'}\mathbf{Q}]^*.
$$
\end{theorem}

\begin{proof} Take an element $\beta\in\g'$. To prove the Theorem, it is sufficient to show
that for every $h\in K[x]$ such that $\nu'(h)=\beta$, $h$ belongs to the additive
group generated by all the monomials $c\mathbf{Q}^{{\bar\gamma}}$ such that
$\nu'\left(c\mathbf{Q}^{{\bar\gamma}}\right)\ge\beta$.

We go through all the possible ways in which the construction of $\mathbf{Q}$ can end
and prove the Theorem in each case. If $\Lambda$ does not contain a maximal element
then $\mathbf{Q}$ is complete by construction. Assume that $\Lambda$ contains a
maximal element $\lambda$. If $\beta_\lambda\in\g'_1$ or if $\lambda$ has an
immediate predecessor, again $\mathbf{Q}$ is complete
by definition. Suppose that $\lambda$ is a limit ordinal and
\begin{equation}
\beta_\lambda\notin\g'_1.\label{tag13.31}
\end{equation}
Then  the 1-completeness
of $\mathbf{Q}$ is given by Proposition \ref{Proposition9.26} (1), applied with $i=\lambda$.

By definition, $Q_\lambda$ is monic. Take any element $h\in K[x]$. Let
$h=\sum\limits_{j=0}^{s_\lambda}c_{j\lambda}Q_\lambda^j$ be the $\lambda$-standard
expansion of $h$ (here we are using the fact $Q_\lambda$
is monic and so the $\lambda$-standard expansion is well defined). Let
$\mu=\min\{j\in\{1\do s_\ell \}\ |\ c_{j\lambda}\ne0\}$. By (\ref{tag13.31}) we have
$$
\nu_\lambda(h)=\nu_\lambda\left(c_{\mu\lambda}Q_\lambda^\mu\right)=
\nu'\left(c_{\mu\lambda}Q_\lambda^\mu\right)=\nu'(h).
$$
This proves that $\mathbf{Q}$ is a complete set of key polynomials. Theorem \ref{th13.10} is proved.
\end{proof}

\begin{remark}{\label{Remark13.11}} Take an ordinal $\ell\in\Lambda$ such that
$\ell+\omega\in\Lambda$ (in other words, such that the limit key
polynomial $Q_{\ell+\omega}$ is defined). If $\ch\ k_\nu=0$, we have
$\nu'(Q_{\ell+\omega})\notin\g'_1$ by Proposition \ref{Proposition12.8}. Then
$\ell+\omega=\omega$ and the construction of key polynomials is
complete. If $\ch\ k_\nu=p>0$, by Remark \ref{Remark13.9} we have
$\alpha_{\ell+\omega}\ge p>1$. Hence after at most $\omega$ iterations of
this procedure we arrive at the situation when (\ref{tag13.31}) holds and thus
the resulting set of key polynomials is complete. This proves that, in
any case, we have $\lambda\le\omega\times\omega$.
\end{remark}

config: arxiv