\documentclass[11pt]{amsart}
%\usepackage{amsfonts,amssymb,amscd,amsmath,enumerate,verbatim,calc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd}

%------    GENERAL MACROS    -----
\def\NZQ{\mathbf}               % the font for N,Z,Q,R,C
\def\NN{{\NZQ N}}
\def\QQ{{\NZQ Q}}
\def\ZZ{{\NZQ Z}}
\def\RR{{\NZQ R}}
\def\CC{{\NZQ C}}
\def\AA{{\NZQ A}}
\def\BB{{\NZQ B}}
\def\PP{{\NZQ P}}
\def\FF{{\NZQ F}}
\def\GG{{\NZQ G}}
\def\HH{{\NZQ H}}
\def\P{\mathcal P}
\def\R{{\mathbf R}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
%\newtheorem{Remark}[theorem]{Remarks}
\renewcommand{\qedsymbol}{$\square$}


%------------------------------------------------
% Direct and inverse limits
%
%\opn\dirlim{\underrightarrow{\lim}}
%\opn\inivlim{\underleftarrow{\lim}}
%
%
% Names with a meaning
%
\let\union=\cup
\let\sect=\cap
\let\dirsum=\oplus
\let\tensor=\otimes
\let\iso=\cong
\let\Union=\bigcup
\let\Sect=\bigcap
\let\Dirsum=\bigoplus
\let\Tensor=\bigotimes

\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Remarks}[Theorem]{Remarks}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Examples}[Theorem]{Examples}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Problem}[Theorem]{}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Question}[Theorem]{Question}
%
% We like the var forms of some greek letters (as taught in German schools)
%
\let\epsilon\varepsilon
\let\phi=\varphi
\let\kappa=\varkappa
%
%           We print on A4 paper
%
\textwidth=15cm \textheight=22cm \topmargin=0.5cm
\oddsidemargin=0.5cm \evensidemargin=0.5cm \pagestyle{plain}
% ------    END OF GENERAL MACROS    -------

\begin{document}

\title{Semigroups of valuations on local rings, II}

\author{Steven Dale Cutkosky, Bernard Teissier}
\thanks{The first author was partially supported by NSF and by the University Paris 7-Denis Diderot}



\maketitle



Let $(R,m_R)$ be a local domain, with quotient field $K$. Suppose that $\nu$ is a valuation of $K$
with valuation ring $(V,m_V)$. Suppose that $\nu$ dominates $R$; that is, $R\subset V$ and $m_V\cap
R=m_R$. The value groups $\Gamma$ of $\nu$ which can appear when $K$ is an algebraic function field have been extensively studied and classified,
including in the papers MacLane \cite{M}, MacLane and Schilling \cite{MS}, Zariski and Samuel
\cite{ZS}, and Kuhlmann \cite{K}. The most basic fact is that there is an order preserving
embedding of $\Gamma$ into $\RR^n$ with the lex order, where $n$ is the dimension of $R$. The
semigroups
$$
S^R(\nu)=\{\nu(f)\mid f\in m_R-\{0\}|
$$
which can appear when $R$ is a noetherian domain with fraction field $K$ dominated by $\nu$, however, are not well understood, although they are known to encode important information about the  ideal theory of $R$ and the
geometry and resolution of singularities of $\hbox{\rm Spec}R$.

In Zariski and Samuel's classic book on Commutative Algebra \cite{ZS}, two general facts about
semigroups $S^R(\nu)$ of valuations on noetherian local domains are proven (in Appendix 3 to Volume II).
\begin{enumerate}
\item[1.] For any valuation $\nu$ of $K$ which is non negative on $R$, the semigroup $S^R(\nu)$ is a well ordered subset of the positive part of the value group $\Gamma$ of
$\nu$ of ordinal type at most $\omega^h$, where $\omega$ is the ordinal type of the well ordered
set $\NN$, and $h$ is the rank of the valuation. \item[2.] If $\nu$ dominates $R$, the rational rank of $\nu$ plus the
transcendence degree of $V/m_V$ over $R/m_R$ is less than or equal to the dimension of $R$.
\end{enumerate}
The second condition is the Abhyankar inequality \cite{Ab}.

Prior to this paper, no other general constraints were known on the value semigroup semigroups
$S^R(\nu)$. In fact, it was even unknown if the above conditions 1 and 2 characterize value
semigroups.

In this paper, we construct an example of a well ordered subsemigroup of $\QQ_+$ of ordinal type
$\omega$, which is not a value semigroup of a local domain. This shows that the above conditions 1
and 2 do not characterize value semigroups on  local domains. We construct this in Corollary
\ref{Corollary3} by finding a new constraint, Theorem \ref{Theorem1}, on a semigroup being a value
semigroup of a local domain of dimension $n$. In Corollary \ref{Corollary2}, we give a stronger
constraint on regular local rings.

In \cite{CT}, Teissier and the author give some examples showing that some surprising semigroups of
rank $>1$ can occur as   semigroups of valuations on noetherian domains, and raise the general
question of finding new constraints on value semigroups and classifying semigroups which occur as
value semigroups.

The only semigroups which are realized by a valuation on a one dimensional regular local ring are
isomorphic to the natural numbers. The semigroups which are realized by a valuation on a regular
local ring of dimension 2 with algebraically closed residue field are much more complicated, but
are completely classified by Spivakovsky in \cite{S}. A different proof is given by Favre and
Jonsson in \cite{FJ}, and the theorem is formulated in the context of semigroups by Cutkosky and
Teissier \cite{CT}. However, very little is known in higher dimensions. The classification of
semigroups of valuations on regular local rings of dimension two does suggest that there may be
constraints on the rate of growth of the number of new generators on semigroups of valuations
dominating a noetherian domain. We prove that there is such a constraint, giving a new necessary
condition for a semigroup to be a value semigroup. This is accomplished in Theorem \ref{Theorem1}
and Corollaries \ref{Corollary1} and \ref{Corollary2}. The constraint is sufficiently strong to
allow us to give a very simple example, Corollary \ref{Corollary3}, of a well ordered subgroup $S$
of $\QQ_+$ of ordinal type $\omega$ which is not the semigroup of a valuation dominating an
 local domain.


\section{Asymptotic growth of value semigroups}
If $R$ is a local ring, $m_R$ will denote its maximal ideal, and   $\ell(N)$ will denote the length
of an $R$ module $N$.\par
Given a valuation $\nu$ which is non negative on $R$ and an element $\phi$ of its value group, we will denote by $\P_\phi(R)$ the ideal $\{x\in R\vert \nu(x)\geq \phi\}$ and by $\P^+_\phi(R)$ the ideal $\{x\in R\vert \nu(x)> \phi\}$. When no confusion on the ring is possible we will write $\P_\phi, \P^+_\phi$.We note that $\P_{\phi}(R)/\P_{\phi}^+(R)=0$ if $\phi\notin S^R( \nu)\cup\{0\}$.\par  
Suppose that $\Gamma$ is a totally ordered abelian group, and $a,b\in\Gamma$. We set
$$
[a,b]=\{x\in\Gamma\mid a\leq x\leq b\}\ \hbox{\rm and}\ [a,b[=\{x\in\Gamma\mid a\leq x< b\}
$$
Let $\nu_1$ and $\nu_2$ be valuations on the noetherian local domain $(R,m)$, with centers $p_2\subset_{\ne} p_1$ and such that $\nu_1$ is composed with $\nu_2$ and their ranks differ by one. Let $\lambda\colon \Gamma_1\to \Gamma_2$ be the corresponding map of value groups.  Set $t_1=\nu_1 (p_1), t_2=\nu_2(p_2)$.
\begin{definition}Given $\phi_2\in \Gamma_2$, denote by $\tilde\phi_2\in \Gamma_1$ the minimum of $\{\nu_1 (f); f\in R,\ \nu_2(f)=\phi_2\}$. This minimum exists since the semigroup $\nu_1(R\setminus\{0\})$ is well ordered. 
\end{definition}\par\noindent
Note that $\lambda(\tilde \phi_2)=\phi_2$ and that $t_1\in \hbox{\rm Ker}\lambda$.
\par\medskip

We remark that for $\phi_1\in [\tilde \phi_2,\tilde\phi_2+y_1t_1]$ we have the inclusions:\par\noindent
$$p_1^{y_1}\P_{\phi_2}\subset \P_{\phi_1}\subset \P_{\phi_2},$$ 
$\P_{\phi_2}=\P_{\tilde \phi_2}$ and since the valuation $\overline\nu_1$ which is the image of $\nu_1$ in $R/p_2$ is of rank one, the number of elements of $\nu_1(R\setminus\{0\})$ in the interval $ [\tilde \phi_2,\tilde\phi_2+y_1t_1]$ is finite (see \cite{ZS}, \textit{loc. cit.}).\par
\begin{theorem}\label{basic} For any function $A$ on $R$-modules with values in $\R$ which is additive on short exact sequences we have:
$$
\sum_{\phi_1\in[\tilde \phi_2,\tilde\phi_2+y_1t_1[}A(\P_{\phi_1}/\P_{\phi_1}^+)\leq A(M_{\phi_2}/p_1^{y_1}M_{\phi_2}),\leqno(1)
$$ 
where $M_{\phi_2}= \P_{\phi_2}/ \P^+_{\phi_2},$ a finitely generated torsion free $R/p_2$-module.\end{theorem}
\begin{proof} We note that $\P^+_{\phi_2}\subseteq p_1^{y_1} \P_{\phi_2}$. The $R$-module $\P_{\phi_2}/\P_{\tilde \phi_2+t_1y_1}$ is a quotient of $\P_{\phi_2}/ p_1^{y_1} \P_{\phi_2}=M_{\phi_2}/p_1^{y_1}M_{\phi_2}$, and by the additivity of $A$ we have $$A(\P_{\phi_2}/\P_{\tilde \phi_2+t_1y_1})=\sum_{\phi_1\in[\tilde \phi_2,\tilde\phi_2+y_1t_1[}A(\P_{\phi_1}/\P_{\phi_1}^+).$$
The result follows, since the value of $A$ can only decrease when passing to a quotient.\end{proof}
In the special case where $\nu_1$ is a valuation of rank one and $\nu_2$ is the trivial valuation, we have $\Gamma_2=0$, $\tilde \phi_2=0\in \Gamma_1$ and, writing $\phi$ for $\phi_1$, $p$ for $p_1$, etc.,  the inequality reduces to:
$$\sum_{\phi\in[0,yt[}A(\P_{\phi}/\P_{\phi}^+)\leq A(R/p_1^{y}R),\leqno(2)$$
\par\noindent
\textbf{Remark}
The $R$ modules $\P_{\phi_1}/\P_{\phi_1}^+$ and $M_{\phi_2}/p_1^{y_1}M_{\phi_2}$ have $p_1$ as their unique minimal prime.\par\noindent

We can take as additive function $A$ on $R$-modules of dimension $=\hbox{\rm dim}R/p_1$ the multiplicity $e_m$  with respect to the maximal ideal of $R$.  The inequality $(1)$ then becomes 
\begin{corollary} We have the inequalities
$$\sum_{\phi_1\in[\tilde \phi_2,\tilde\phi_2+y_1t_1[}e_m(\P_{\phi_1}/\P_{\phi_1}^+)\leq e_m(M_{\phi_2}/p_1^{y_1}M_{\phi_2}).\leqno(3)$$
\end{corollary}
It is now possible to evaluate the right hand side thanks to ([B], \S7, No.1, Prop 3), which says this: given a finitely generated $R$-module $M$ of dimension $d\geq 0$, denote by $B$ the set of minimal prime ideals of $\hbox{\rm Supp}(M)$ such that $\hbox{\rm dim}(R/p)=d$. Let $q$ be an ideal of $R$ contained in its radical and such that $M/qM$ has finite length. Then we have 
$$e_q(M)=\sum_{p\in B}\hbox{\rm length}_{R_p}  (M_p)e_q(R/p).$$ If we apply this to $M_{\phi_2}/p_1^{y_1}M_{\phi_2}$ we get:\par\noindent
$$
e_m(M_{\phi_2}/p_1^{y_1}M_{\phi_2})= \hbox{\rm length}_{R_{p_1}}\bigl((M_{\phi_2})_{p_1}/m^{y_1}_1(M_{\phi_2})_{p_1}\bigr)e_m(R/p_1),
\leqno(4)
$$
where $m_1=p_1R_{p_1}$ and the support of the $R$-module $M_{\phi_2}$ is the ideal $p_2$.\par\noindent
By the main result on Hilbert-Samuel polynomials, in view of the fact that the support of $(M_{\phi_2})_{p_1}$ is the ideal $p_2R_{p_1}$, we have an asymptotic estimate:
$$\hbox{\rm length}_{R_{p_1}}\bigl((M_{\phi_2})_{p_1}/m^{y_1}_1(M_{\phi_2})_{p_1}\bigr)\asymp \frac{e_{m_1}\bigl((M_{\phi_2})_{p_1})\bigr)}{(\hbox{\rm dim}(R_{p_1}/p_2R_{p_1})!}y_1^{\hbox{\rm dim}(R_{p_1}/p_2R_{p_1})}.\leqno(5)$$
%--------------------------------------------------------------
Let us now consider a valuation $\nu$ of rank $n$.\par\noindent
Let $$(0)=p_{n+1}\subset p_n\subset p_{n-1}\subset \cdots \subset p_1$$
be the sequence of the centers of valuations $\nu_i$ with which a given valuation $\nu$ of rank $n$ on a noetherian local domain $(R,m)$ is composed. We assume that the centers are distinct prime ideals.

Let $p_0$ be a prime ideal of $R$ containing the center $p_1$ of $\nu=
\nu_1$ ($p_0$ could be equal to $p_1$).
Then
\begin{theorem}
The sum
$$\sum_{\phi_n\in [0,t_ny_n[}\sum_{\phi_{n-1}\in [
\tilde\phi_n,\tilde\phi_n+t_{n-1}y_{n-1}[}\cdots \sum_{\phi_1\in [
\tilde\phi_{2},\tilde\phi_{2}+t_1y_1[}e_{m_0}((\P_{\phi_1}/\P^+_{\phi_1})_{p_0})$$
is bounded for $y_1,\ldots ,y_n$ large enough by a function which behaves asymptotically as
$$\frac{\Pi_{i=0}^n e_{m_i}((R/p_{i+1})_{p_i})}{\Pi_{i=1}^n(\hbox{\rm dim}(R/p_{i+1})_{p_i})!} \Pi_{i=1}^ny_i^{\hbox{\rm dim }(R/p_{i+1})_{p_i}},$$
where $m_i=p_iR_{p_i}$ for $0\le i\le n$. We  take
$y_1\gg y_2\gg \cdots\gg y_n$ to obtain this asymptotic behavior.\par\noindent
\end{theorem}
\begin{proof} The proof of this formula is by induction on $n$. We first prove the formula in the case when $n=1$. We apply formulas $(2)$ and $(3)$ - $(5)$ to the ring $R_{p_0}$, observe that for 
$\phi_1\in\Gamma_1$,
$$
(\P_{\phi_1})_{p_0}=\{f\in R_{p_0}\mid \nu(f)\ge \phi_1\},
$$
and that $(R_{p_0})_{p_1R_{p_0}}\cong R_{p_1}$, to obtain
$$
\sum_{\phi_1\in [0,t_1y_1[}e_{m_0}((\P_{\phi_1}/\P_{\phi_1}^+)_{p_0})
\asymp
\frac{e_{m_1}(R_{p_1})e_{m_0}((R/p_1)_{p_0})}{(\mbox{dim }R_{p_1})!}y_1^{\mbox{dim }R_{p_1}},
$$
which is the formula for $n=1$.

We now assume that the formula is true for valuations of rank $<n$. We will derive the formula for a rank $n$ valuation $\nu$.   We apply the formula to the rank $n-1$ valuation $\nu_2$ which $\nu$ is composite with, and the chain of prime ideals
$$
(0)=q_n\subset q_{n-1}\subset \cdots\subset q_1\subset q_0
$$
where $q_{n-1}=p_{n},\ldots,q_1=p_2$ are the centers on $R$ of the successive valuations
$\nu_n,\ldots,\nu_2$ with which $\nu_2$ is composite, and   $q_0=p_1$, to obtain
$$
\sum_{\phi_n\in[0,t_ny_n[}\cdots\sum_{\phi_2\in [\tilde \phi_3+t_2y_2[}
e_{m_1}((\P_{\phi_2}/\P_{\phi_2^+})_{p_1})\asymp
\frac{\prod_{i=1}^ne_{m_i}((R/p_{i+1})_{p_i})}
{\prod_{i=2}^n(\mbox{dim }(R/p_{i+1})_{p_i})!}
\prod_{i=2}^ny_i^{\mbox{dim }(R/p_{i+1})_{p_i}}.\leqno(6)
$$
We now apply formulas $(1)$, and $(3)-(5)$ to the ring $R_{p_0}$ and the valuation $\nu=\nu_1$, to obtain
$$
\sum_{\phi_1\in[\tilde\phi_2,\tilde\phi_2+y_1t_1[}e_{m_0}((\P_{\phi_1}/\P_{\phi_1}^+)_{p_0})
\asymp
\frac{e_{m_1}((\P_{\phi_2}/\P_{\phi_2}^+)_{p_1})e_{m_0}((R/p_1)_{p_0})}
{(\mbox{dim }(R/p_2)_{p_1})!}
y_1^{\mbox{dim }(R/p_2)_{p_1}}.\leqno(7)
$$
Finally, we  sum over $(7)$ and $(6)$ to obtain the desired formula for $\nu$.
\end{proof}
\section{Amalgamation of valuations}
\begin{Theorem}\label{Theoremg1}
Suppose that $P_i\in K[X,Y]$ are defined for $i\in \NN$ by $P_0=X$ $P_1=Y$,
$$
P_{i+1}= \lambda_i P_i^{m_i}-\lambda_{i,0}M_i-\sum_{\ell_i'}\lambda_{i,\ell_i'}M_{i,\ell_i'}
$$
for $i\ge 1$, where $\ell_i'=(\ell_{i,0}',\ldots,\ell_{i,i}')$,
$M_i=\prod_{i'=0}^{i-1} P_{i'}^{\ell_{i,i'}}$, 
$M_{i,\ell_i'}=\prod_{i'=0}^{i} P_{i'}^{\ell_{i,i'}'}$
with $0\le \ell_{i,i'},\ell_{i,i'}<m_{i'}$ for $1\le i'\le i$, $\ell_{i,0},\ell_{i,0}'\ge 0$
arbitrary, and $\lambda_i, \lambda_{i,0},\lambda_{\ell_i'}\in K$ with $\lambda_i, \lambda_{i,0}\ne 0$.

Define $\gamma_0=1$ and by induction on $i$, $\gamma_i=\frac{1}{m_i}\sum_{i'=0}^{i-1}\ell_{i,i'}\gamma_{i'}$.
Let $\Gamma_i =< \{{\gamma_{i'}}\}_{0\le i'\le i}>$ be the group generated by
$\gamma_{i'}$ for $0\le i'\le i$. Suppose that
\begin {enumerate}
 \item $\sum_{i'=0}^{i-1}\ell_{i,i'}\gamma_{i'}$ has
 order $m_i$ in $\frac{\Gamma_{i-1}}{m_i\Gamma_{i-1}}$ for all $i\ge 1$,
\item $\gamma_{i+1}>m_i\gamma_i$ for all $i\ge 1$, and
\item $\sum_{i'=0}^{i}\ell_{i,i'}'\gamma_{i'}>m_i\gamma_i$ for all $\ell_i'$.
\end {enumerate}

Then
\begin{enumerate}
 \item  Suppose that $f\in K[X,Y]$ and $\ell$ is such that $\mbox{deg}_y f<\prod_{j=1}^
{l-1}m_i$. Then $f$ has a unique finite expansion
\begin{equation}\label{g1}
f= \sum_{\alpha}a_{\alpha}\prod_{i=0}^{\ell}P_i^{\alpha_i}
\end{equation}
with all $\alpha=(\alpha_0,\ldots,\alpha_{\ell})\in \NN^{\ell+1}$, $0\le \alpha_i<m_i$ for $1\le i$ and
$a_{\alpha}\in K$,
\item
In the expansion $(\ref{g1})$, The numbers
$\sum_{i=0}^{\ell}\alpha_i\gamma_i$ are distinct for distinct $\alpha$,
\item The rule
$$
\nu_1(f)=\mbox{min}_{\alpha} \sum_{i=0}^{\ell}\alpha_i\gamma_i
$$
where the minimum is computed for the expansion (\ref{g1}), determines a nondiscrete
rational rank 1 valuation $\nu_1$ of $K(X,Y)$, dominating the local ring $K[X,Y]_{(X,Y)}$.
\end{enumerate}


\end{Theorem}

\begin{Theorem}\label{Theoremg2} Suppose that $R$ is a local  domain with quotient field $K$ and  $\overline \nu$ is a valuation of $K$ which dominates $R$, with value group $\overline\Gamma$. Suppose that $\{P_i\}$ is a sequence of polynomials in $K(X,Y)$ satisfying the assumptions of Theorem \ref{Theoremg1}. Define by induction on $i$,
$\tau_0=0$, and 
$$
\tau_i=\frac{1}{m_i}\sum_{i'=0}^{i-1}\ell_{i,i'}\tau_{i'}+\overline\nu(\lambda_{i,0})
-\overline\nu(\lambda_i)
\in \overline\Gamma_{\QQ}=\overline\Gamma\otimes_{\bf \ZZ}{\bf \QQ}.
$$
For $f\in K[X,Y]$, define from the expansion (\ref{g1}),
$$
\nu(f) =\mbox{min}_{\alpha}\{ \sum_{i=0}^{\ell}\alpha_i(\gamma_i,\tau_i)+(0,\mbox{ord}_z(a(z))\}\in (\QQ\times \overline\Gamma_{\QQ})_{\mbox{lex}}.
$$
Then $\nu$ defines a rank 2 valuation on $K(X,Y)$ which is the composition of $\nu_1$ and $\overline \nu$. Further, $\nu$ dominates the local ring $A=R[X,Y]_{m_RR[X,Y]+(X,Y)}$,
and the center of $\nu_1$ on $A$ is the prime ideal $(X,Y)$.


\end{Theorem}


\begin{Theorem}\label{Theoremg3} Suppose that $R$ is a local  domain with quotient field $K$ and  $\overline \nu$ is a valuation of $K$ which dominates $R$, with value group $\overline\Gamma$. Suppose that $\{P_i\}$ is a sequence of polynomials in $K(X,Y)$ satisfying the assumptions of Theorem \ref{Theoremg1} and
$\{Q_i\}$ is a sequence of polynomials in $K(U,V)$ satisfying the assumptions of Theorem \ref{Theoremg1}, where 
$$
P_{i+1}= \lambda_i P_i^{m_i}-\lambda_{i,0}M_i-\sum_{\ell_i'}\lambda_{i,\ell_i'}M_{i,\ell_i'}
$$
and
$$
Q_{i+1}= \mu_i Q_i^{n_i}-\mu_{i,0}N_i-\sum_{\ell_i'}\mu_{i,\ell_i'}N_{i,\ell_i'}
$$

Let $\nu_1$ be the valuation on $K(X,Y)$ defined by the $\{P_i\}$, with  $\nu_1(P_i)=\gamma_i$, and let 
$\nu_2$ be the valuation on $K(U,V)$ defined by the $\{Q_i\}$, with  $\nu_2(Q_i)=\delta_i$.



Define by induction on $i$,
$\tau_0=0$, and 
$$
\tau_i=\frac{1}{m_i}\sum_{i'=0}^{i-1}\ell_{i,i'}\tau_{i'}+\overline\nu(\lambda_{i,0})
-\overline\nu(\lambda_i)
\in \overline\Gamma_{\QQ}=\overline\Gamma\otimes_{\bf \ZZ}{\bf \QQ},
$$
$\zeta_0=0$, and 
$$
\zeta_i=\frac{1}{n_i}\sum_{i'=0}^{i-1}\ell_{i,i'}\zeta_{i'}+\overline\nu(\mu_{i,0})
-\overline\nu(\mu_i)
\in \overline\Gamma_{\QQ}=\overline\Gamma\otimes_{\bf \ZZ}{\bf \QQ}.
$$



Then
\begin{enumerate}
 \item Suppose that $f\in K[X,Y,U,V]$, with $\mbox{deg}_Yf<\prod_{j=1}^{\ell-1}m_i$
and $\mbox{deg}_Vf<\prod_{j=1}^{m-1}n_i$. 
Then $f$ has a unique finite expansion
\begin{equation}\label{g2}
f= \sum_{\alpha,\beta}a_{\alpha,\beta}\prod_{i=0}^{\ell}P_i^{\alpha_i}
\prod_{i=0}^{m}Q_i^{\beta_i}
\end{equation}
with all $\alpha=(\alpha_0,\ldots,\alpha_{\ell})\in \NN^{\ell+1}$, $0\le \alpha_i<m_i$ for $1\le i$,  all $\beta=(\beta_0,\ldots,\beta_m)\in \NN^{m+1}$, $0\le \beta_i<n_i$ for $1\le i$, and
$a_{\alpha,\beta}\in K$.
\item Suppose that $G$ is a totally ordered abelian group, and $h_1:\QQ\rightarrow G$ and $h_2:\QQ\rightarrow G$ are order preserving embeddings.
For $f\in K[X,Y,U,V]$, define from the expansion (\ref{g2}),
$$
\nu(f) =\mbox{min}_{\alpha,\beta}\{ \sum_{i=0}^{\ell}\alpha_i(h_1(\gamma_i),\tau_i)
+\sum_{i=0}^{m}\beta_i(h_2(\delta_i),\zeta_i)
+(0,\mbox{ord}_z(a(z))\}
\in (G\times \overline\Gamma_{\QQ})_{\mbox{lex}}.
$$
Then $\nu$ defines a  valuation on $K(X,Y)$ which is  composite with $\overline \nu$.
$\nu$ has rank 2 or 3, depending on if the  rank
  of $h_1(\QQ)+h_2(\QQ)$ is 1 or 2. Further, $\nu$ dominates the local ring
 $A=R[X,Y,U,V]_{m_RR[X,Y,U,V]+(X,Y,U,V)}$.


\end{enumerate}




\end{Theorem}



\section{Wild behavior of the tilde function}

\begin{Theorem}\label{Theoremg4}
 Given any decreasing function $f:\NN\rightarrow \ZZ$, there exists a valuation $\nu$
with value group $(\frac{1}{2^\infty}\ZZ\times \ZZ)_{\mbox{lex}}$ which dominates a local ring
$R$ of dimension 3, such that for any valuation $v$ equivalent to $\nu$, with value group $(\frac{1}{2^\infty}\ZZ\times \ZZ)_{\mbox{lex}}$, we have that for all sufficiently large $n\in\NN$, there exists $\lambda\in \frac{1}{2^\infty}\ZZ\cap [0,n]$ such that
 $\pi_2(\tilde\lambda)<f(n)$.
\end{Theorem}

\begin{Theorem}\label{Theoremg5}
 Given any increasing function $g:\NN\rightarrow \ZZ$, there exists a valuation $\omega$
with value group $(\frac{1}{2^\infty}\ZZ\times \ZZ)_{\mbox{lex}}$ which dominates a local ring
$R$ of dimension 3, such that for any valuation $w$ equivalent to $\omega$, with value group $(\frac{1}{2^\infty}\ZZ\times \ZZ)_{\mbox{lex}}$, we have that for all sufficiently large $n\in\NN$, there exists $\lambda\in \frac{1}{2^\infty}\ZZ\cap [0,n]$ such that
 $\pi_2(\tilde\lambda)>g(n)$.
\end{Theorem}

\begin{Theorem}\label{Theoremg6}
 Suppose that $f:\NN\rightarrow \ZZ$ is a decreasing function and 
 $g:\NN\rightarrow \ZZ$ is an increasing function. Then there exists a valuation $\mu$
with value group $((\frac{1}{2^\infty}\ZZ+\frac{1}{2^\infty}\ZZ\sqrt{2})\times \ZZ)_{\mbox{lex}}$ which dominates a local ring
$A$ of dimension 5, such that for any valuation $m$ equivalent to $\mu$, with value group $((\frac{1}{2^\infty}\ZZ+\frac{1}{2^\infty}\ZZ\sqrt{2})\times \ZZ)_{\mbox{lex}}$, we have that for all sufficiently large $n\in\NN$, there exists $\lambda_1\in (\frac{1}{2^\infty}\ZZ+\frac{1}{2^\infty}\ZZ\sqrt{2})\cap [0,n]$ such that
 $\pi_2(\tilde\lambda_1)>f(n)$, and
there exists $\lambda_2\in (\frac{1}{2^\infty}\ZZ+\frac{1}{2^\infty}\ZZ\sqrt{2})\cap [0,n]$ such that
 $\pi_2(\tilde\lambda_2)<g(n)$.
\end{Theorem}



\begin{thebibliography}{}
\bibitem{Ab1} Abhyankar, S., {\em Desingularization of plane curves},
AMS Proceedings of Symp. in Pure Math. 40, Part I (1883), 1-45.
\bibitem{Ab2} Abhyankar, S., {\em On the valuations centered in a local domain}, Amer. J. Math. 78 (1956), 321 - 348.
\bibitem{Ab3} Abhyankar, S., {\em On the ramification of algebraic functions}, Amer. J. math. 77 (1955), 575 - 592.
\bibitem{Ab4} Abhyankar, S., {\em Two notes on formal power series}, Proc. Amer. Math. Soc. 7 (1956), 903-905.
\bibitem{B} N. Bourbaki, Commutative Algebra, Chap. 8.
\bibitem{Be} Benhessi, A., {\em La Cl\^oture alg\'ebrique du corps des s\'eries formelles}, Ann. Math. Blaise Pascal 2 (1995), 1-14.
\bibitem{BK} Brieskorn, E. and Kn\"orrer, H. {\em Plane algebraic curves},
Birkhauser, Basel, 1986.
\bibitem{Ch} Chevalley, C. {\em Introduction to the theory of
algebraic functions of one variable}, AMS, Mathematical Surveys 6, Amer. math. Soc., NY, 1951.
\bibitem{C} Cutkosky, S.D., {\em Resolution of Singularities}, Graduate Studies in Math. 63, AMS, Providence, Rhode Island, 2004.
\bibitem{CG} Cutkosky, S.D. and  Ghezzi, L., {\em Completions of valuation rings},
Cont. math. 386 (2005), 13 - 34.
\bibitem{G-P} Gonz\'alez-P\'erez. P.D., {\em Decomposition in bunches of the critical locus of a quasi-ordinary map}, Compos. math. 141 (2005) 461 -486.
\bibitem{GM} Grothendieck, A. and  Murre, J., {\em The tame fundamental group of a formal neighbourhood of a divisor with normal crossings on a scheme}, Lect. Notes in Math. 208, Springer Verlag, Heidelberg, Berlin, New York, 1971.
\bibitem{Ha} Hahn, H., {\em "Uber die nichtarchimedische Gro\"ossensysteme}, in Gesammelte Abhandlungen I, Springer, Vienna, 1995.
\bibitem{HS} Heinzer, W. and Sally, J., {\em Extensions of valuations to
the completion of a local domain}, Journal of Pure and Applied
Algebra 71 (1991), 175 - 185.
\bibitem{HRS} Heinzer, W., Rotthaus, C. and Wiegand, S., {\em Generic fiber rings of mixed power series/ polynomial rings}, J. Algebra 298 (2006) 248 - 272.
\bibitem{Hu} Huang, M.F., Phd Thesis, Purdue University, 1968.
\bibitem{K} Kaplansky, I., {\em Maximal fields with valuations}, Duke Math. J. 8 (1942), 303 -321.
\bibitem{Ke} Kedlaya, K., {\em The algebraic closure of the power series field
in positive characteristic}, Proc. Amer. Math. Soc. 129, (2001) 3461 - 3470.
\bibitem{L} Lipman, J. {\em Desingularization of 2-dimensional schemes},
Annals of Math. 107 (1978), 115 - 207.
\bibitem{L2} Lipman, J. {\em Quasi-ordinary singularities of surfaces in $\CC^3$}, Singularities Part 2 (Arcata, Calif., 1981), 161-172, Proc. Sympos. Pure Math., 40, Amer. math. Soc., Providence, RI 1983.
\bibitem{N} Nagata, M., {\em Local Rings}, Interscience 1962.
\bibitem{O} Orbanz, U., {\em Embedded resolution of algebraic surfaces
after Abhyankar}, in Cossart V., Giraud J. and Orbanz U., Resolution of surface singularities, Lect. Notes in Math., 1101, Springer Verlag, Heidelberg, Berlin, New York, 1984.
\bibitem{Po} Poonen, B., {\em Maximally complete fields}, Enseign. Math. 39 (1993), 87-106.
\bibitem{Ra} Rayner, F., {\em An algebraically closed field}, Glasgow J. Math
9 (1968), 146-151.
\bibitem{R} Ribenboim, P., {\em Fields: Algebraically closed and others},
Man. math. 175 (1992), 115-150.
\bibitem{RVdD} Ribenboim, P. and Van den Dries, L.,
{\em The absolute Galois group of a rational function field in characteristic zero is a semi-direct product}, Can. Math. Bull. 27 (1984), 313-315.
\bibitem{Ro} Rotthaus, C., {\em Nicht Ausgezeichnete, Universell Japonische Ringe}, Math. Z. 152 (1977) 107 - 125.
\bibitem{St} Stefanescu, D., {\em On meromorphic formal power series}, Bull. Math. Soc. Sci. Math. R.S. Roumanie 27 (1983), 169-178.
\bibitem{S} Spivakovsky, M., {\em Valuations in function fields of surfaces},
Amer. J. Math. 112 (1990), 107 - 156.
\bibitem{Te} B. Teissier, {\em Valuations, deformations, and toric geometry},  Proceedings of the Saskatoon Conference
and Workshop on valuation theory (second volume), F-V. Kuhlmann, S. Kuhlmann, M. Marshall, editors,  Fields Institute
Communications, {\bf 33}, 2003, 361-459.
\bibitem{V} Vaidya, S., {\em Generalized Puiseux expansions and their Galois groups}, Illinois J. Math 41 (1997) 129 - 141.
\bibitem{Z} Zariski, O., {\em The reduction of the singularities of an algebraic surface}, Annals of Math. 40 (1939), 639 - 689.
\bibitem{ZS} Zariski, O. and Samuel, P., {\em Commutative Algebra Volume II}, D. Van Nostrand, Princeton, 1960.
\end{thebibliography}

\end{document}
%------------------------------------------------------------------------
%------------------------------------------------------------------------
\begin{Corollary}\label{Corollary1} Suppose that $R$ is a  local domain of dimension $d$ which is dominated by a valuation
$\nu$. Let $S=\nu(m_R-\{0\})$ be the value semigroup of $\nu$ on $R$, and suppose that $s_0$ is the
smallest element of $S$. Then
\begin{enumerate}
\item[1.] For $n\gg 0$, $|S\cap (0,ns_0)|<P_R(n)$. \item[2.] There exists $c>0$ such that $|S\cap
(0,ns_0)|<cn^d$ for all $n$.
\end{enumerate}
\end{Corollary}

\begin{Corollary}\label{Corollary2}  Suppose that $R$ is a regular local ring of dimension $d$ which is dominated by a  valuation
$\nu$.  Let $S=\nu(m_R-\{0\})$ be the value semigroup of $\nu$ on $R$, and suppose that $s_0$ is
the smallest element of $S$. Then
$$
|S\cap (0,ns_0)|<\binom{d-1+n}{d}
$$
for all  $n\in \NN$.
\end{Corollary}

\begin{Corollary}\label{Corollary3} There exists a well ordered subsemigroup $U$ of $\QQ_+$ such that $U$ has ordinal
type $\omega$ and $U\ne \nu(m_R-\{0\})$ for any valuation $\nu$ dominating a local domain $R$.
\end{Corollary}

\begin{proof} Take any subset $T$ of $\QQ_+$ such that 1 is the smallest element of $S$ and $n^n\le |T\cap
(0,n)|<\infty$ for all $n\in\NN$. For all positive integers $r$, let
$$
rT=\{a_1+\cdots+a_r\mid a_1,\ldots,a_r\in T\}.
$$
Let $U=\omega T=\cup_{r=1}^{\infty}rT$ be the semigroup generated by $T$. By our constraints,
$|U\cap(0,r)|<\infty$ for all $r\in\NN$. Thus $U$ is well ordered and has ordinal type $\omega$. By
2 of Corollary \ref{Corollary1}, $U$ cannot be the semigroup of a valuation dominating a local
domain.
\end{proof}
\section{Asymptotic growth of value semigroups}

Suppose that $\Gamma$ is a totally ordered abelian group of rank 1, and $S$ is a well ordered
subsemigroup of ordinal type $\omega$, consisting of positive elements of $S$.  Let $s_0$ be the
smallest element of $S$. For $n\in \NN$, let
$$
\phi(n)=|S\cap (0,ns_0)|.
$$


Theorem \ref{Theorem1}  gives a necessary condition for a well ordered  semigroup $S$ of rank 1
consisting of positive elements to be the semigroup $\nu(m_R-\{0\})$ of a valuation $\nu$
dominating a {\it fixed} local domain $R$. Let $s_0$ be the smallest element of $S$.  We must have
\begin{equation}\label{eq1}
\phi(n)=|S\cap(0,ns_0)|<\ell(R/m_R^n)
\end{equation}
for all $n\in\NN$.



\begin{Example}\label{Example1}
The necessary condition (\ref{eq1})  is not sufficient.    Sufficiency fails for the case of two
dimensional regular local rings \end{Example}

\begin{proof} Let $S$ be the subsemigroup of $\QQ_+$
which is generated by 1, 3/2 and 9/4. Then
$$
S=\{1,\frac{3}{2},2,\frac{9}{4}, \frac{10}{4},3,\frac{13}{4},\frac{14}{4},\frac{15}{4},4,\ldots\}.
$$
Define $\phi(n)=|S\cap (0,n)|$. We have that $\phi(2)=2$ and $\phi(n)=4n-7$ for $n\ge 3$. We have
$$
\phi(n)=|S\cap (0,n)|<\frac{(1+n)n}{2}=\binom{1+n}{2}=\ell(R/m_R^{n})
$$
for all $n$. Thus $S$ satisfies the  bound (\ref{eq1}).  We will show now that $S$ is not the
semigroup of a valuation dominating a regular local ring $R$ of dimension 2. Suppose that there
exists a valuation $\nu$  dominating a regular local ring $R$ of dimension 2 such that
$S=\nu(m_R-\{0\})$. We will derive a contradiction. Let $x,y$ be regular parameters in $R$. After
possibly interchanging $x$ and $y$, we may assume that $\nu(x)=1$. There exists $f\in m_R$ such
that $\nu(f)=\frac{3}{2}$. Write $f=\alpha_1x+\alpha_2y$ with $\alpha_1,\alpha_2\in R$. We have
$$
\mbox{min}\{\nu(\alpha_1)+\nu(x),\nu(\alpha_2)+\nu(y)\}\le \nu(f)=\frac{3}{2}
$$
with a strict inequality only if $\nu(\alpha_1)+\nu(x)=\nu(\alpha_2)+\nu(y)$. By the restriction
that all values are in $S$, we either have that $\nu(y)=\frac{3}{2}$, or $\nu(y)=1$ and $\alpha_2$
is a unit, so that we can make a change of variables, replacing $y$ with $f$ to assume that
$\nu(x)=1$ and $\nu(y)=\frac{3}{2}$. There exists $g\in m_R$ such that $\nu(g)=\frac{9}{4}$. Expand
$$
g=\alpha_1x+\alpha_2y+\alpha_3x^2+\alpha_4xy+\alpha_5y^2+h
$$
with $\alpha_1,\ldots,\alpha_5\in R$ and $h\in m_R^3$, and such that $\alpha_i$ are all either 0 or
have nonzero residue in $R/m_R$. With the convention that $\nu(0)=\infty$, we have
$$
\mbox{min}\{\nu(\alpha_1)+\nu(x),\nu(\alpha_2)+\nu(y),\ldots,\nu(\alpha_5)+2\nu(y),\nu(h)\}\le\nu(g)=\frac{9}{4},
$$
with a strict inequality only if at least two of the terms have the minimal value. Since all of
these values are in $S$, and $\nu(h)\ge 3$, this is impossible.
\end{proof}


It is worth noting that the necessary condition (\ref{eq1}) is sufficient for regular local rings
$R$ of dimension 1. In this case the bound is
$$
|S\cap (0,ns_0)|\le\binom{n}{1}-1=n-1
$$
for all $n\in\NN$. Since $s_0\NN_+\subset S$, we then have that $S=s_0\NN_+$. Let $\mu$ be the
$m_R$-adic valuation, and let $\nu$ be the equivalent valuation $s_0\mu$. Then $S=\nu(m_R-\{0\})$.

In the case of regular local rings $R$ of dimension 1, we see that the bound
$$
|S\cap (0,ns_0)|=\ell(R/m_R^n)-1
$$
is  achieved for all $n\in\NN$. This bound is not achievable for all $n$ however on a regular local
ring $R$ of dimension $\ge 2$. This can be seen as follows. Suppose that there is a valuation $\nu$
dominating a regular local ring $R$ of dimension $d\ge 2$  such that $\phi(n)=|\nu(m_R-\{0\})\cap
(0,ns_0)|=\ell(R/m_R^n)-1$ for all $n$. Then $\phi(2)=\ell(R/m_R^2)-1\ge 2$. Thus there exists a
regular system of parameters $x,y,\ldots$ in $R$ such that $\nu(x)=s_0$ and $\nu(y)=s_1$ with
$s_0<s_1<2s_0$. There exists $a\in\NN$ such that $\frac{a}{a-1}s_0<s_1$. We have
$\nu(y^{a-1})>as_0$. For $n\ge a$,  $y^{a-1}m_R^{n-a}$ generates a submodule $G_n$ of $R/m_R^n$ of
length $\binom{d-1+n-a}{d-1}$.  Since $\nu(f)>ns_0$ if $f\in y^{a-1}m_R^{n-a}$, we must have that
$$
\phi(n)\le \ell(R/m_R^n)-1-\binom{d-1-a+n}{d-1}<\ell(R/m_R^n)-1
$$
for all $n\ge a$; in fact, $\binom{d-1+n-a}{d-1}$ grows like $n^{d-1}$, a contradiction.

We can easily achieve growth of $\phi(n)$ which is asymptotic to $n^d$ on a regular local ring of
dimension $d$. Choose $d$ rationally independent real positive real numbers
$\gamma_1,\ldots,\gamma_d$, a regular system of parameters $x_1,\ldots, x_d$ of $R$ and prescribe
that $\nu(x_i)=\gamma_i$ for all $i$. It is an interesting question to determine the exact possible
asymptotic behavior of $\phi(n)$ which is achievable on a local domain. Is it possible to achieve
exotic asymptotic growth, such as $n\mbox{ log }n$?
















Corollary \ref{Corollary1} gives a necessary condition for a rank 1 well ordered semigroup $S$
consisting of positive elements to be the value semigroup $\nu(m_R-\{0\})$ of a valuation
dominating some local domain $R$ of dimension $d$. The condition is:
\begin{equation}\label{eq2}
\mbox{There exists $c>0$ such that $|S\cap (0,ns_0)|<cn^d$ for all $n$}
\end{equation}
where $s_0$ is the smallest element of $S$. An interesting question is if (\ref{eq2}) is in fact
sufficient. (\ref{eq2}) is  sufficient in the case when $d=1$, as we now show. Suppose that
$S\subset \RR_+$ is a semigroup consisting of positive elements which contains a smallest element
$s_0$. Suppose that there exists $c>0$  such that
\begin{equation}\label{eq12}
|S\cap [(0,ns_0)|<cn
\end{equation}
for all $n\in\NN$. By Lemma \ref{Lemma2} below, we may assume that $S\subset \QQ_+$ is finitely
generated by some elements $\lambda_1,\ldots,\lambda_r$. There exists $\alpha\in\QQ_+$ such that
there exists $a_i\in\NN_+$ with $\lambda_i=\alpha a_i$ for $1\le i\le r$, and
$\mbox{gcd}(a_1,\ldots,a_r)=1$. Let $k[t]$ be a polynomial ring over a field $k$. Let
$\nu(f(t))=\alpha\mbox{ord}(f(t))$ for $f(t)\in k[t]$. $\nu$ is a valuation of $k(t)$. Let $R$ be
the one dimensional local domain
$$
R=k[t^{a_1},\ldots,t^{a_r}]_{(t^{a_1},\ldots,t^{a_r})}.
$$
The quotient field of $R$ is $k(t)$, and $\nu$ dominates $R$. We have that $S=\nu(R-m_R)$.





\begin{Lemma}\label{Lemma1} Suppose that $S\subset \RR_+$ is a semigroup consisting of positive elements which contains a smallest element
$s_0$. Suppose that there exists $c>0$ and $d\in\NN_+$ such that
\begin{equation}\label{eq11}
|S\cap (0,ns_0)|<cn^d
\end{equation}
for all $n\in\NN$. Then $S$ is well ordered of ordinal type $\omega$ and has rational rank $\le d$.
\end{Lemma}

\begin{proof} The fact that $S$ is well ordered of ordinal type $\omega$ is immediate from
(\ref{eq11}).

We will prove that the rational rank of $S$ is $\le d$. After rescaling $S$ by multiplying by
$\frac{1}{s_0}$, we may assume that $s_0=1$. Suppose that $t\in\NN$ and $S$ has rational rank $\ge
t$. Then there exist $\gamma_1,\ldots,\gamma_t\in S$ which are rationally independent. Let
$b\in\NN$ be such that $\mbox{max}\{\gamma_1,\ldots,\gamma_t\}<b$. For $e\in \RR_+$, we have
$$
\begin{array}{lll}
|S\cap(0,e)|&\ge&|\{a_1\gamma_1+\cdots+a_t\gamma_t\mid a_1,\ldots,a_t\in\NN\mbox{ and
}a_1\gamma_1+\cdots+a_t\gamma_t<e\}|-1\\
&\ge&|\{a_1\gamma_1+\cdots+a_t\gamma_t\mid a_i\in\NN\mbox{ and }0\le a_i<\frac{e}{tb}\mbox{ for
}1\le
i\le t\}|-1\\
&=&|\{(a_1,\ldots,a_t)\in\NN^t\mid 0\le a_i<\frac{e}{tb}\mbox{ for }1\le i<t\}|-1
\end{array}
$$
since $\gamma_1,\ldots,\gamma_t$ are rationally independent.

For $a\in\NN$ let $n=abt$. Then we see that
$$
|S\cap(0,(n+1))|\ge a^t-1=\left(\frac{1}{bt}\right)^tn^t-1.
$$
By (\ref{eq11}), we see that $t\le d$.
\end{proof}

\begin{Lemma}\label{Lemma2} Suppose that $S\subset \RR_+$ is a semigroup consisting of positive elements which contains a smallest element
$s_0$. Suppose that there exists $c>0$  such that
\begin{equation}\label{eq12}
|S\cap (0,ns_0)|<cn
\end{equation}
for all $n\in\NN$. Then $S$ is finitely generated, and the group generated by $S$ is isomorphic to
$\ZZ$.
\end{Lemma}
\begin{proof}
By Lemma \ref{Lemma1}, $S$ has rational rank 1, so we may assume that $S$ is contained in $\QQ_+$.
We may further assume that $s_0=1$. Suppose that $S$ is not finitely generated. Then for $e\in\NN$,
we can find $\lambda_1,\ldots,\lambda_e\in S$ such that $\lambda_i=\frac{a_i}{b_i}$ with
$a_i,b_i\in\NN_+$, $b_i>1$ for all $i$, $\mbox{gcd}(a_i,b_i)=1$ for all $i$ and $b_1,\ldots,b_e$
all distinct.

There exist $m_i,n_i\in\ZZ$ such that $m_ia_i+n_ib_i=1$ for $1\le i\le e$. Either $m_i>0$ and
$n_i<0$, or $m_i<0$ and $n_i>0$.  If $m_i>0$, then $|m_i|\lambda_i=|n_i|+\frac{1}{b_i}$. If
$m_i<0$, then $|m_i|\lambda_i=|n_i|-\frac{1}{b_i}$. Let $n_0=\mbox{max}\{|n_i|+1\mid 1\le i\le
i\}$. For $n\ge n_0$, we have that $n+\frac{1}{b_i}\in S\cap(n,n+1)$ if $m_i>0$, and
$(n+1)-\frac{1}{b_i}\in S\cap (n,n+1)$ if $m_i<0$. Thus $|S\cap (n,n+1)|\ge e$ for $n\ge n_0$,
which implies that
$$
|S\cap (n,n+1)|\ge en-en_0
$$
for $n\ge n_0$. For $e>c$, we have a contradiction to (\ref{eq12}).
\end{proof}





\begin{thebibliography}{}
\bibitem{Ab} S. Abhyankar, {\em On the valuations centered in a local domain}, Amer. J. Math. 78
(1956), 321 - 348.
\bibitem{C} S.D. Cutkosky, {\em Local factorization and monomialization of morphisms}, Ast/'erisque
260, 1999.
\bibitem{CG} S.D. Cutkosky and L. Ghezzi, {\em Completions of valuation rings}, Contemp. Math. 386
(2005), 13 -34.
\bibitem{CT} S.D. Cutkosky and B. Teissier, {\em Semigroups of valuations on local rings}, to appear in Mich. Math. J.
\bibitem{FJ} C. Favre and M. Jonsson, {\em The valuative tree}, Lecture Notes in Math 1853, Springr
Verlag, Berlin, Heidelberg, New York, 2004.
\bibitem{HS} W. Heinzer and J. Sally, {\em Extensions of valuations to the completion of a local
domain}, Journal of Pure and Applied Algebra 71 (1991), 175 - 185.
\bibitem{K} F.-V. Kuhlmann, {\em Value groups, residue fields, and bad plcaes of algebraic function
fields}, Trans. Amer. Math. Soc. 40 (1936), 363 - 395.
\bibitem{M} S. MacLane, {\em A construction for absolute values in polynomial rings}, Trans. Amer.
Math. Soc. 40 (1936), 363 - 395.
\bibitem{MS} S. MacLane and O. Schilling, {\em Zero-dimensional branches of rank 1 on algebraic
varieties}, Annals of Math. 40 (1939), 507 - 520.
\bibitem{S} M. Spivakovsky, {\em Valuations in function fields of surfaces}, Amer. J. Math. 112
(1990), 107 - 156.
\bibitem{T} B. Teissier, {\em Valuations, deformations, and toric geometry}, Proceedings of the
Saskatoon Conference and Workshop on valuation theory (second volume), F.-V. Kuhlmann, S. Kuhlmann,
M. Marshall, editors, Fields Institute Communications, 33, 2003, 361 - 459.
\bibitem{ZS} O. Zariski and P. Samuel, {\em Commutative Algebra Volume II}, D. Van Nostrnad,
Princeton, 1960.
%\bibitem{Ne} B.H. Neumann, {\em On ordered division rings}, Trans. Amer. Math. %Soc., 66 (1949), 202-252.
\end{thebibliography}


\end{document}


%\begin{abstract}
%\end{abstract}
Let $(R,m_R)$ be an equicharacteristic local domain, with quotient field $K$. Suppose that $\nu$ is
a valuation of $K$ with valuation ring $(V,m_V)$. Suppose that $\nu$ dominates $R$; that is,
$R\subset V$ and $m_V\cap R=m_R$. The possible value groups $\Gamma$ of $\nu$ have been extensively
studied and classified, including in the papers MacLane \cite{M}, MacLane and Schilling \cite{MS},
Zariski and Samuel \cite{ZS}, and Kuhlmann \cite{K}. The most basic fact is that there is an order
preserving embedding of $\Gamma$ into $\RR^n$ with the lex order, where $n$ is the dimension of
$R$. The semigroup
$$
S^R(\nu)=\{\nu(f)\mid f\in m_R-\{0\}|
$$
is however not well understood, although it is known to encode important information about the
topology, resolution of singularities and ideal theory of $R$.

In Zariski and Samuel's classic book on Commutative Algebra \cite{ZS}, two general facts about the
semigroup $S^R(\nu)$ are proven (in Appendix 3 to Volume II).
\begin{enumerate}
\item[1.] $S^R(\nu)$ is a well ordered subset of the positive part of the value group $\Gamma$ of
$\nu$ of ordinal type at most $\omega^h$, where $\omega$ is the ordinal type of the well ordered
set $\NN$, and $h$ is the rank of the valuation. \item[2.] The rational rank of $\nu$ plus the
transcendence degree of $V/m_V$ over $R/m_R$ is less than or equal to the dimension of $R$.
\end{enumerate}
The second condition is the Abhyankar inequality \cite{Ab}.

Prior to this paper, no other general constraints were known on the value semigroup semigroups
$S^R(\nu)$. In fact, it was even unknown if the above conditions 1 and 2 characterize value
semigroups.

In this paper, we construct an example of a well ordered subsemigroup of $\QQ_+$ of ordinal type
$\omega$, which is not a value semigroup of an equicharacteristic noetherian local domain. This
shows that the above conditions 1 and 2 do not characterize value semigroups on equicharacteristic
noetherian local domains. We construct this in Example \ref{Example2} by finding a new constraint,
Theorem \ref{Theorem1}, on a semigroup being a value semigroup of an equidimensional noetherian
local domain of dimension $n$. In Corollary \ref{Corollary1}, we give a stronger constraint on
regular local rings.

In \cite{CT}, Teissier and the author give some examples showing that some surprising semigroups of
rank $>1$ can occur as   semigroups of valuations on noetherian domains, and raise the general
question of finding new constraints on value semigroups and classifying semigroups which occur as
value semigroups.

The only semigroups which are realized by a valuation on a one dimensional regular local ring are
isomorphic to the natural numbers. The semigroups which are realized by a valuation on a regular
local ring of dimension 2 with algebraically closed residue field are much more complicated, but
are completely classified by Spivakovsky in \cite{S}. A different proof is given by Favre and
Jonsson in \cite{FJ}, and the theorem is formulated in the context of semigroups by Cutkosky and
Teissier \cite{CT}. However, very little is known in higher dimensions. The classification of
semigroups of valuations on regular local rings of dimension two does suggest that there may be
constraints on the rate of growth of the number of new generators on semigroups of valuations
dominating a noetherian domain. We prove that there is such a constraint, giving a new necessary
condition for a semigroup to be a value semigroup. This is accomplished in Theorem \ref{Theorem1}
and Corollary \ref{Corollary1}. The constraint is however far from sharp, even for one dimensional
regular local rings. The criterion of Theorem \ref{Theorem1} is however sufficiently strong to
allow us to give a very simple example, Example \ref{Example2}, of a well ordered subgroup $S$ of
$\QQ_+$ of ordinal type $\omega$ which is not the semigroup of a valuation dominating an
equidimensional noetherian local domain.



\section{Semigroups of valuations dominating polynomial rings}
Given a set $T$, $|T|$ will denote the cardinality of $T$. If $S$ is an ordered abelian semigroup,
$S_+$ will denote the set of positive elements of $S$.

Let $k$ be a field, $n$ be a positive integer, and $A_n=k[x_1,\ldots,x_n]$ be a polynomial ring in
$n$ variables. Let $m_n$ be the maximal ideal $m_n=(x_1,\ldots,x_n)$ of $A_n$. $A_n$ is naturally a
$k$ vector space. Let $F_{n,d}$ be the $k$ subspace of $m_n$ of polynomials of degree $\le d$ with
0 constant term.

 Suppose that $\nu$ is a valuation  of the quotient field of $A_n$
with valuation ring $V$. Suppose $A_n\subset V$ and $m_V\cap A_n= m_n$. Let $\Gamma$ be the value
group of $\nu$. Let $\Psi$ be the convex subgroup of real rank 1 of $\Gamma$, so that $\Psi$ is
order isomorphic to a subroup of $\RR$. Let $S(\nu)=\nu(m_n-\{0\})\cap \Psi$.




If $S(\nu)\ne \emptyset$, then $S(\nu)$ is a well ordered semigroup of ordinal type $\omega$, by
the first condition stated in the introduction, since $S(\nu)$ is a value semigroup on the quotient
$A/\{f in A\mid \nu(f)\not\in\Psi\}$. Let the smallest element of $S(\nu)$ be $s_0$. Let
$S_d(\nu)=\nu(F_{d,n}-\{0\})$.
\begin{Lemma}\label{Lemma1} The upper bound
$$
|S_d(\nu)|< \binom{n+d}{n}
$$
holds for all $d\in\NN$.
\end{Lemma}
\begin{proof}
For $\lambda\in \Gamma$, the set $C_{\lambda}=\{f\in F_{d,n}\mid \nu(f)> \lambda\}$ is a $k$
subspace of $F_{d,n}$. Since $S_d(\nu)$ is well ordered and $\mbox{dim}_kF_{d,n}=\binom{n+d}{d}-1$,
the lemma follows.
\end{proof}

For $a,b\in\Psi$, let $[a,b)=\{c\in \Psi\mid a\le c <b\}$.

\begin{Lemma}\label{Lemma2}
For all $d\in \NN$,
$$
|S(\nu)\cap [0,(d+1)s_0)|<\binom{n+d}{n}.
$$
\end{Lemma}

\begin{proof}
Since every element of $m_n$ has value $\ge s_0$, every element of $m_n^{d+1}$ has value $\ge
(d+1)s_0$. For $f\in m_n$, we have an expression $f=g+h$ with $g\in F_{d,n}$ and $h\in m_n^{d+1}$.
If $\nu(f)<(d+1)s_0$, we must have $\nu(f)=\nu(g)$. Thus $S(\nu)\cap [0,(d+1)s_0)=S_d(\nu)\cap
[0,(d+1)s_0)$.
\end{proof}




\begin{Example}\label{Example1} There exists a well ordered subsemigroup $U$ of $\QQ_+$
such that $U$  has ordinal type $\omega$ and $U\ne S(\nu)$ for any valuation $\nu$  as above.
\end{Example}

\begin{proof}  Let $T$ be any subset of $\QQ_+$ such that
1 is the smallest element of $T$ and
$$
|T\cap [n,n+1)|  = \binom{2n}{n}
$$
 for all $n\ge 1$.  For all positive integers $r$, let
$rT=\{a_1+\cdots+a_r\mid a_1,\ldots,a_r\in T\}$.
Let
$U=\omega T=\cup_{r=1}^{\infty}rT$ be the semigroup generated by $T$.
By our construction, $|U\cap [0,r)|<\infty$ for all $r\in N$. Thus
$U$ is well ordered and has ordinal type $\omega$.

Suppose that there exists a field $k$, a positive integer $n$, and a valuation $\nu$ such that
$S(\nu)=U$. By Lemma \ref{Lemma2},
$$
\binom{2n}{n}= |T\cap [n,n+1)|\le |U\cap[n,n+1)|\le |U\cap[0,n+1)|\le\binom{2n}{n}-1,
$$
which is a contradiction.
\end{proof}

\section{Semigroups of valuations dominating local domains}

Let $\nu$ be a valuation of a field $K$. Let $V$ be the valuation ring of $\nu$, and let $m_V$ be
the maximal ideal of $V$. Suppose that $R$ is a noetherian local domain with quotient field $K$
such that $\nu$ dominates $R$; that is, $R\subset V$ and $m_V\cap R=m_R$ is the maximal ideal of
$R$.  Let $\Gamma$ be the value group of $\nu$. $\Gamma$ has finite rank, since $\nu$ dominates the
noetherian local domain $R$, and by the second condition stated in the introduction. Let $\Psi$ be
the convex subgroup of real rank 1 of $\Gamma$. Define a semigroup of real rank 1 by
$$
S^R(\nu)=\nu(m_R-\{0\})\cap \Psi.
$$
For $a,b\in\Psi$, let $[a,b)=\{c\in\Psi\mid a\le c<b\}$.

 Let $\hat R$ be the $m_R$-adic completion
of $R$, which naturally contains $R$.  Then there exists a prime ideal $Q$ of $\hat R$ such that
  the valuation $\nu$ induces  uniquely  a valuation
$\overline \nu$ of the quotient field of $\hat R/Q$ which dominates $\hat R/Q$, $\overline \nu$ has
rank 1, $S^{\hat R/Q}(\overline \nu)=S^R(\nu)$, and $s_0=\mbox{min}\{\overline \nu(f)\mid f\in
m_{\hat R/Q}\}$. We will call $Q$ the prime ideal of elements of $\hat A$ of infinite value. The
construction of $Q$ and related considerations are discussed in Spivakovsky \cite{S}, Heinzer and
Sally \cite{HS}, Cutkosky \cite{C}, Cutkosky and Ghezzi \cite{CG} and Teissier \cite{T}. We will
outline the construction of $Q$ in the following paragraph.

Let $\alpha=\mbox{min}\{\nu(g)\mid g\in m_R\}$.  Suppose that $f\in \hat R$. Then for any Cauchy
sequence $\{g_i\}$ in  $R$ which converges to $f$, exactly one of the following two conditions must
hold.
\begin{enumerate}
\item[1)] There exists $n\in\NN$ such that $\nu(g_i)\le n\alpha$ for all $i\gg 0$ or

\item[2)] For all $n\in \NN$, there exists $i\in\NN$ such that $\nu(g_i)>n\alpha$.
\end{enumerate}
Moreover, either condition 1) holds for all Cauchy sequences $\{g_i\}$ in $R$ which converge to $f$
or condition 2) hold for all Cauchy sequences $\{g_i\}$ in $R$ which converge to $f$. If condition
1) holds for $f$, then there exists $\lambda\in S^R(\nu)$ such that for any Cauchy sequence
$\{g_i\}$ in $R$ which converges to $f$, there exists $n\in\NN$ (which depends on the Cauchy
sequence) such that $\nu(g_i)=\lambda$ for all $i\ge n$. In this, way may extend $\nu$ to a
function on $\hat R$, defining for $f\in \hat R$, $\nu(f)=\lambda$ if 1) holds, and $\nu(f)=\infty$
if 2) holds. Let
$$
Q=\{f\in\hat R\mid \nu(f)=\infty\}.
$$
$Q$ is a prime ideal in $\hat R$.  We extend $\nu$ to a valuation $\overline \nu$ of the quotient
field of $\hat R/Q$ with the desired properties by defining $\overline\nu(f+Q)=\nu(f)$ for $f\in
\hat R$. If $\Gamma$ has rank 1, we have $Q\cap R=(0)$, and we have an inclusion $R\rightarrow \hat
R/Q$.



\begin{Theorem}\label{Theorem1} Suppose that $A$ is an equicharacteristic local domain, and $\nu$ is a valuation
which dominates $A$. Let $s_0=\mbox{min}\{\nu(f)\mid f\in m_A\}$ and
$n=\mbox{dim}_{A/m_A}m_A/m_A^2$. Then
\begin{equation}\label{eq6}
|S^A(\nu)\cap [0,(d+1)s_0)|<\binom{n+d}{n}
\end{equation}
for all $d\in\NN$.
\end{Theorem}

\begin{proof}
Let $\hat A$ be the $m_A$-adic completion of $A$, with natural inclusion $A\rightarrow \hat A$. Let
$Q$ be the prime ideal of elements of $\hat A$ of infinite value, and let $\overline\nu$ be the
valuation of  the quotient field of $\hat A/Q$ induced by $\nu$ which dominates $\hat A/Q$, so that
$S^{\hat A/Q}(\overline\nu)=S^A(\nu)$, and $s_0=\mbox{min}\{\overline\nu(f)\mid f\in m_{\hat
A/Q}\}$. Let $k$ be a coefficient field of $\hat A/Q$. There exists a power series  ring
$R=k[[x_1,\ldots,x_n]]$, and a surjective $k$-algebra homomorphism $\phi:R\rightarrow \hat A/Q$.
Let $P$ be the kernel of $\phi$, so that $R/P\cong \hat A/Q$. We may thus identify $\overline \nu$
with  a rank 1 valuation of the quotient field of $R/P$ dominating $R/P$ such that
$S^{R/P}(\overline\nu)=S^{\hat A/Q}(\overline\nu)$, and $s_0=\mbox{min}\{\overline\nu(f)\mid f\in
m_{R/P}\}$.

Let $\nu_1$ be  a valuation of the quotient field of $R$ which dominates $R_P$, and let $\mu$ be
the composite valuation of $\nu_1$ and $\overline \nu$.  For $f\in R$, we have that $\nu_1(f)=0$ if
and only if $f\not\in P$, and
$$
S^R(\mu)=\mu(m_R-P)=\overline \nu(m_{R/P}-\{0\})=S^{R/P}(\overline\nu).
 $$
 We
 also have that $s_0=\mbox{min}\{\mu(f)\mid f\in m_R\}$.

$R$ contains the polynomial ring $A_n=k[x_1,\ldots,x_n]$. Suppose that $f\in m_R-P$. There exists a
Cauchy sequence $\{g_i\}$ in $A_n$ (for the $m_R$-adic topology) that converges to $f$. Since
$\overline\nu$ has rank 1, and $\nu_1(f)=0$, there exists $l\in\NN$ such that $\mu(h)>\mu(f)$
whenever $h\in m_R^l$. Further, since $\{g_i\}$ is a Cauchy sequence, there exists $e\in\NN$ such
that $f-g_i\in m_R^l$ whenever $i\ge e$.  Thus $\mu(f)=\mu(g_e)$.  It follows that
$S^{(A_n)_{m_n}}(\mu')=S^R(\mu)=S^A(\nu)$ where $\mu'$ is the restriction of $\mu$ to $A_n$, and
$s_0=\mbox{min}\{\mu(f)\mid f\in m_n\}$. The conclusions of the theorem now follow from Lemma
\ref{Lemma2}.
\end{proof}

 When $\nu$ has
rank 1, $S^A(\nu)=\nu(m_A-\{0\})$ is the semigroup of $\nu$ on $A$.  Thus (\ref{eq6}) gives us a
necessary condition for a subsemigroup $S$ of $\RR_+$ to be the  semigroup of a valuation on an
equicharacteristic local domain $R$.

When $A$ is a regular local ring, the $n$ in the theorem   is the dimension of $A$. Thus we have
the following Corollary, which gives a necessary condition for a subsemigroup of $\RR_+$ to be the
subsemigroup of a valution on a equidimensional regular local ring.

\begin{Corollary}\label{Corollary1} Suppose that $A$ is an equicharacteristic regular local ring of dimension $n$,
and $\nu$ is a rank 1 valuation which dominates $A$. Let $s_0=\mbox{min}\{\nu(f)\mid f\in m_ A\}$.
Then \begin{equation}\label{eq5}
 |\nu(m_A-\{0\})\cap[0,(d+1)s_0)|<\binom{n+d}{n}
\end{equation}
for all $d\in \NN$.
\end{Corollary}


The necessary condition  (\ref{eq5}) is  far from giving  a sufficient condition for a subsemigroup
of $\RR_+$ to be the  semigroup of a valuation on an equidimensional  regular local ring  $A$, even
in the case when $A$ has dimension $n=1$.  Suppose that $\nu$ is a valuation dominating an
equidimensional  regular local ring $A$ of dimension $n=1$. $\nu$ must then be equivalent to the
$m_A$-adic valuation of $A$, and we thus have that $\nu(m_A-\{0\})=s_0\NN$. Thus
$$
|\nu(m_A-\{0\})\cap[0,(d+1)s_0)|=d
$$
for all $d\ge 1$, which is significantly less than the bound $\binom{1+d}{1}=d^2+d$ of the
corollary.



The criterion of the theorem is strong enough to give us a simple method of constructing well
ordered semigroups of ordinal type $\omega$ which are not value semigroups. The existence of such
examples was not previously known.


\begin{Example}\label{Example2} There exists a well ordered subsemigroup $U$ of $\QQ_+$ such that $U$ has ordinal type $\omega$ and $U\ne\nu(m_A-\{0\})$
 for any valuation $\nu$ dominating an equicharacteristic  noetherian local domain $A$.
\end{Example}

\begin{proof} Let $U$ be the semigroup constructed in Example \ref{Example1}. By Theorem
\ref{Theorem1} and the proof of Example \ref{Example1}, $U$ cannot be a semigroup of a valuation
dominating an equicharacteristic local domain.
\end{proof}



\begin{thebibliography}{}
\bibitem{Ab} S. Abhyankar, {\em On the valuations centered in a local domain}, Amer. J. Math. 78
(1956), 321 - 348.
\bibitem{C} S.D. Cutkosky, {\em Local factorization and monomialization of morphisms}, Ast/'erisque
260, 1999.
\bibitem{CG} S.D. Cutkosky and L. Ghezzi, {\em Completions of valuation rings}, Contemp. Math. 386
(2005), 13 -34.
\bibitem{CT} S.D. Cutkosky and B. Teissier, {\em Semigroups of valuations on local rings}, to appear in Mich. Math. J.
\bibitem{FJ} C. Favre and M. Jonsson, {\em The valuative tree}, Lecture Notes in Math 1853, Springr
Verlag, Berlin, Heidelberg, New York, 2004.
\bibitem{HS} W. Heinzer and J. Sally, {\em Extensions of valuations to the completion of a local
domain}, Journal of Pure and Applied Algebra 71 (1991), 175 - 185.
\bibitem{K} F.-V. Kuhlmann, {\em Value groups, residue fields, and bad plcaes of algebraic function
fields}, Trans. Amer. Math. Soc. 40 (1936), 363 - 395.
\bibitem{M} S. MacLane, {\em A construction for absolute values in polynomial rings}, Trans. Amer.
Math. Soc. 40 (1936), 363 - 395.
\bibitem{MS} S. MacLane and O. Schilling, {\em Zero-dimensional branches of rank 1 on algebraic
varieties}, Annals of Math. 40 (1939), 507 - 520.
\bibitem{S} M. Spivakovsky, {\em Valuations in function fields of surfaces}, Amer. J. Math. 112
(1990), 107 - 156.
\bibitem{T} B. Teissier, {\em Valuations, deformations, and toric geometry}, Proceedings of the
Saskatoon Conference and Workshop on valuation theory (second volume), F.-V. Kuhlmann, S. Kuhlmann,
M. Marshall, editors, Fields Institute Communications, 33, 2003, 361 - 459.
\bibitem{ZS} O. Zariski and P. Samuel, {\em Commutative Algebra Volume II}, D. Van Nostrnad,
Princeton, 1960.
%\bibitem{Ne} B.H. Neumann, {\em On ordered division rings}, Trans. Amer. Math. %Soc., 66 (1949), 202-252.
\end{thebibliography}


\end{document}
\section{Generalized Power Series Fields}


Let $K$ be a field, with algebraic closure $\overline K$, and let $K((t^{\QQ}))$ be the generalized power series
in the variable $t$. An element of $K((t^{\QQ}))$ is a series (eq1)
\begin{equation}\label{eq1}
f(t)=\sum_{i\in A}\alpha_it^i
\end{equation}
where $A$ is a well order subset of $\QQ$, and $\alpha_i\in K$ for all $i\in A$.
$K((t^{\QQ}))$ is a field (cf Section 4 \cite{Ne}).

Let $\QQ^+$ be the set of positive rational numbers.
Suppose that $S,T\subset \QQ^+$ are well ordered subsets.
We state for the readers convenience a few properties
 from Section 3 of \cite{Ne} that  are necessary to conclude that
natural algebraic manipulations of generalized power series, such as
multiplication and  inversion. We will tacitly make use of these properties in this paper.

\begin{enumerate}
\item[1.] $S+T$ is a well ordered subset of $\QQ^+$.
\item[2.] For any $u\in S+T$, there are only finitely many solutions
$u=s+t$ with $s\in S$ and $t\in T$.
\item[3.] Let $\omega S=\cup_{n=1}^{\infty}nS$ be the semigroup generated by $S$.
Then $\omega S$ is a well ordered subset of $\QQ^+$, and any element of
$\omega S$ lies in only a finite number of the sets $S, 2S, 3S, \ldots$.
\end{enumerate}

There is a natural valuation $\nu_t$ defined on $K((t^{\QQ}))$ by
$\nu_t(f(t))= j$ if $j\in A$ is the smallest element of $A$
 such that $\alpha_j\ne 0$. The valuation ring of $\nu_t$ is the ring $K[[t^{\QQ^{\ge 0}}]]$ of generalized power series (\ref{eq1}) such that $A$ is ocntained in the nonnegative rational numbers $\QQ_{\ge 0}=\QQ^+\cup\{0\}$.

Suppose that $\tilde t\in K((t^{\QQ}))$ is such that $\nu_t(\tilde t)>0$.
Then every element of $K((t^{\QQ}))$ has an expansion in terms of $\tilde t$,
and we have a natural identification of $K[[t^{\QQ_{\ge 0}}]]$ and $K[[\tilde t^{\QQ_{\ge 0}})]]$. In particular, the valuations $\nu_t$ and $\nu_{\tilde t}$ are equivalent.




\section{Birational Extensions and Generalized Power Series Fields}

Suppose that $x,y\in \overline K((t^{\QQ}))$ are such that
$$
\begin{array}{lll}
x&=& \beta t\\
y&=& \sum_{i\in S}d_it^i
\end{array}
$$
where $S$ is a well ordered subset of $\QQ^+$, $\beta\in \overline K$
and $d_i\in \overline K$ for all $i$.

We will define a birational transformation of $x$ and $y$ as in \cite{Z}.
Let $i_0$ be the smallest element of $S$. Without loss of generality, we
may assume that $d_{i_0}\ne 0$. Write $i_0=\frac{m}{n}$ where
$m,n$ are relatively prime positive integers. It follows from Euclidean divison that
there exist nonnegative integers $m'$ and $n'$ such that $nm'-mn'=1$.
Let $\alpha_1=d_{i_0}^n\beta^{-m}\in \overline K$. Define
$$
x_1=\frac{x^{m'}}{y^{n'}},
y_1=\frac{y^n}{x^m}-\alpha_1.
$$
Inverting these expressions, we have
$$
x=x_1^n(y_1+\alpha_1)^{n'},
y=x_1^m(y_1+\alpha_1)^{m'}.
$$

\begin{Theorem}
Let
$$
U=\left\{i-i_0\mid i\in S\setminus\{i_0\}\right\},
$$
and $S_1=\omega U$, a well ordered subset of $\QQ^{+}$.
Then there exists an element $t_1\in \overline K((t^{\QQ}))$ such that
 $\nu_t(t_1)=\frac{1}{n}$ and
$$
\begin{array}{lll}
x_1&=&\beta_1 t_1\\
y_1&=& \sum_{i\in S_1} d_{1,i}t_1^i
\end{array}
$$
where $\beta_1\in \overline K$ and $d_{1,i}\in \overline K$ for all $i\in S_1$.
Further, we have
$$
K(d_{i_0})(\{d_{1,i}\mid i\in S_1\})=K(\{d_i\mid i\in S\}).
$$
\end{Theorem}

\begin{proof}
We have an expansion
$$
y=t^{i_0}d_{i_0}(1+\sum_{i\in U}\frac{d_{i+i_0}}{d_{i_0}}t^i).
$$
For $i\in U$, let $e_i=\frac{d_{i+i_0}}{d_{i_0}}$.
Define generalized power series
$z(t)=\sum_{i\in U}e_it^i$ and $\epsilon(t)=1+z(t)$.
We have
$$
\begin{array}{lll}
x_1&=& \frac{x^{m'}}{y^{n'}}=\beta^{m'}t^{m'}t^{-\frac{mn'}{n}}
d_{i_0}^{-n'}\epsilon(t)^{-n'}\\
&=& \beta^{m'}t^{\frac{m'n-mn'}{n}}d_{i_0}^{-n'}\epsilon(t)^{-n'}\\
&=& t^{\frac{1}{n}}\beta^{m'}d_{i_0}^{-n'}\epsilon(t)^{-n'},
\end{array}
$$
$$
\begin{array}{lll}
y_1&=&\frac{t^m}{t^m}d_{i_0}^n\epsilon(t)^n-d_{i_0}^n\\
&=&d_{i_0}^n(nz(t)+\binom{n}{2}z(t)^2+\cdots+z(t)^n).
\end{array}
$$
Set $\tilde t=t^{\frac{1}{n}}\epsilon(t)^{-n'}$. Then
$$
\begin{array}{lll}
t&=&\tilde t^n\epsilon(t){nn'}\\
&=&\tilde t^n(1+z(t))^{nn'}\\
&=&\tilde t^n(1+nn'z(t)+\binom{nn'}{2}z(t)^2+\cdots+z(t)^{nn'})\\
&=&\tilde t^n\left[1+nn'\left(\sum_{\lambda\in U}e_{\lambda}t^{\lambda}\right)
+\binom{nn'}{2}\sum_{\lambda\in 2U}\left(\sum_{\begin{array}{l} j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}
e_{j_1}e_{j_2}\right)t^{\lambda}\right.\\
&&\left.+\cdots+\sum_{\lambda\in nn'U}\left(\sum_{\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}}e_{j_1}\cdots e_{j_n}\right)t^{\lambda}\right]
\end{array}
$$
Set
$$
\begin{array}{lll}
\Lambda&=&nn'\left(\sum_{\lambda\in U}e_{\lambda}t^{\lambda}\right)
+\binom{nn'}{2}\sum_{\lambda\in 2U}\left(\sum_{\begin{array}{l} j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}
e_{j_1}e_{j_2}\right)t^{\lambda}\\
&&+\cdots+\sum_{\lambda\in nn'U}\left(\sum_{\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}}e_{j_1}\cdots e_{j_n}\right)t^{\lambda},
\end{array}
$$
so that (eq2)
\begin{equation}\label{eq2}
t=\tilde t^n(1+\Lambda).
\end{equation}
We have (eq3)
\begin{equation}\label{eq3}
x_1=\beta^{m'}d_{i_0}^{-n'}\tilde t.
\end{equation}



Suppose that $0\ne \tau \in \QQ$. We then have an expansion (eq4)
\begin{equation}\label{eq4}
\begin{array}{lll}
(1+\Lambda)^{\tau}&=& 1+\binom{\tau}{1}\Lambda+\binom{\tau}{2}\Lambda^2+\cdots+\binom{\tau}{2}\Lambda^n+\cdots\\
&=&1+\sum_{j=1}^{\infty}\binom{\tau}{j}\Lambda^j\\
&=& 1+\sum_{\lambda\in\omega U}f_{\lambda}^{\tau} t^{\tau}
\end{array}
\end{equation}
where $f_{\lambda}^{\tau}\in K(\{e_i\mid i\in U, i\le \lambda\})$.
We expand
$$
\begin{array}{lll}
\frac{y_1}{d_{i_0}}&=&nz(t)+\binom{n}{2}z(t)^2+\cdots+z(t)^n\\
&=&\sum_{\lambda\in U}ne_{\lambda}t^{\lambda}+\binom{n}{2}\sum_{\lambda\in 2U}\left(
\sum_{\begin{array}{l}j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}e_{j_1}e_{j_2}\right)t^{\lambda}\\
&&+\cdots+\sum_{\lambda\in nU}\left(\sum_{
\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}} e_{j_1}\cdots e_{j_n}\right)t^{\lambda}\\
&=& \sum_{\lambda\in U}ne_{\lambda}[\tilde t^n(1+\Lambda)]^{\lambda}+\binom{n}{2}\sum_{\lambda\in 2U}\left(
\sum_{\begin{array}{l}j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}e_{j_1}e_{j_2}\right)[\tilde t^n(1+\Lambda)]^{\lambda}\\
&&+\cdots+\sum_{\lambda\in nU}\left(\sum_{
\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}} e_{j_1}\cdots e_{j_n}\right)[\tilde t^n(1+\Lambda)]^{\lambda}\\
&=& \sum_{\lambda\in U}ne_{\lambda}(1+\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu})\tilde t^{n\lambda}
+\binom{n}{2}\sum_{\lambda\in 2U}\left(
\sum_{\begin{array}{l}j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}e_{j_1}e_{j_2}\right)(1+\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu})\tilde t^{n\lambda}\\
&&+\cdots+\sum_{\lambda\in nU}\left(\sum_{
\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}} e_{j_1}\cdots e_{j_n}\right)(1+\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu})\tilde t^{n\lambda}
\end{array}
$$
Set
$$
\begin{array}{lll}
a_0(\tilde t)&=&\sum_{\lambda\in U}ne_{\lambda}\tilde t^{n\lambda}+\binom{n}{2}\sum_{\lambda\in 2U}\left(
\sum_{\begin{array}{l}j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}e_{j_1}e_{j_2}\right)\tilde t^{n\lambda}\\
&&+\cdots+\sum_{\lambda\in nU}\left(\sum_{
\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}} e_{j_1}\cdots e_{j_n}\right)\tilde t^{n\lambda},
\end{array}
$$
and
$$
\begin{array}{lll}
h_{0,\lambda}^1(t)&=& ne_{\lambda}(\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu}),\\
h_{0,\lambda}^2(t)&=& \binom{n}{2}\left(
\sum_{\begin{array}{l}j_1+j_2=\lambda\\j_1,j_2\in U\end{array}}e_{j_1}e_{j_2}\right)(\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu})\\
&\vdots&\\
h_{0,\lambda}^n(t)&=&\left(\sum_{
\begin{array}{l} j_1+\cdots+j_n=\lambda\\
j_1,\ldots,j_n\in U\end{array}} e_{j_1}\cdots e_{j_n}\right)(\sum_{\nu\in \omega U}f_{\nu}^{\lambda}t^{\nu}),
\end{array}
$$
so that
$$
\frac{y_1}{d_{i_0}^n}= a_0(\tilde t)+\sum_{\lambda\in U}h^1_{0,\lambda}(t)\tilde t^{n\lambda}
+\sum_{\lambda\in 2U}h_{0,\lambda}^2(t)\tilde t^{n\lambda}+\cdots+
\sum_{\lambda\in nU}h_{0,\lambda}^n(t)\tilde t^{n\lambda}.
$$
Set $\gamma_0(\tilde t)=a_0(\tilde t)$. Expand
$$
\gamma_0(\tilde t)=\sum_{\lambda\in\omega U}\delta_{\lambda}^0\tilde t^{n\lambda}.
$$
We have $\delta_{\lambda}^0\in K(\{e_i\mid i\le \lambda\})$, and if $\lambda\in U$, then
$\delta_0^{\lambda}=ne_{\lambda}+\omega_{\lambda}^0$ with $\omega_{\lambda}^0\in K(\{e_i\mid i< \lambda\})$.

We have
$$
\frac{y_1}{d_{i_0}^n}-\gamma_0(\tilde t)=\sum_{\alpha\in \cup_{i=1}^niU}g_{\alpha}^0(t)\tilde t^{n\alpha}
$$
where
$g_{\alpha}^0(t)=\sum_{\alpha\in iU}h_{0,\alpha}^i(t)$.
Expand
$$
g_{\alpha}^0(t)=\sum_{\nu\in\omega U}b_{0,\nu}^{\alpha}t^{\nu}
$$
with $b_{\nu}^{\alpha}\in K(\{e_i\mid i\in U, i\le \mbox{max}\{\nu,\alpha\}\})$.
Let
$$
i_1=\mbox{min}\{i\in U\}.
$$
Set
$$
V_1=\{\lambda-i_1\mid \lambda\in \omega U\setminus \{i_1\}\}.
$$
Expand
$$
\begin{array}{lll}
g_{\alpha}^0(t)&=&t^{i_1}\left(b_{0,i_1}^{\alpha}+\sum_{\nu\in V_1}b_{0,\nu+i_1}^{\alpha}t^{\nu}\right)\\
&=&t^{i_1}\left(b_{0,i_1}^{\alpha}+\sum_{\nu\in V_1}c_{0,\nu}^{\alpha}t^{\nu}\right)
\end{array}
$$
where $c_{0,\nu}^{\alpha}=b_{0,\nu+i_1}^{\alpha}\in K(\{e_i\mid i\in U, i\le \mbox{max}\{\nu-i_1,\alpha\}\})$.
We have, substituting (\ref{eq2}) and (\ref{eq4}),
$$
\begin{array}{lll}
\frac{y_1}{d_{i_0}^n}-\gamma_0(\tilde t)&=&
\sum_{\alpha\in \cup_{i=1}^niU}g_{\alpha}^0(t)\tilde t^{n\alpha}\\
&=&\sum_{\alpha\in \cup_{i=1}^niU}t^{i_1}\left(b_{0,i_1}^{\alpha}+\sum_{\nu\in V_1}c_{0,\nu}^{\alpha}t^{\nu}\right)
\tilde t^{n\alpha}\\
&=&\sum_{\alpha\in \cup_{i=1}^niU}\left(b_{0,i_1}^{\alpha}+\sum_{\nu\in V_1}c_{0,\nu}^{\alpha}t^{\nu}\right)
\tilde t^{n\alpha}\tilde t^{ni_1}(1+\Lambda)^{i_1}\\
&=&\sum_{\alpha\in \cup_{i=1}^niU}\left(b_{0,i_1}^{\alpha}+\sum_{\nu\in V_1}c_{0,\nu}^{\alpha}t^{\nu}\right)
\tilde t^{n\alpha}\tilde t^{ni_1}(1+\sum_{\lambda\in \omega U}f_{\lambda}^{i_1}t^{\lambda})\\
&=& \tilde t^{n i_1}\sum_{\alpha\in\cup_{i=1}^niU}\left[ b_{0,i_1}^{\alpha}+\sum_{\tau\in\omega U}b_{0,i_1}^{\alpha}f_{\tau}^{i_1}t^{\tau}\right.\\
&&\left.+\sum_{\tau\in V_1+\omega U}\left(\sum_{\begin{array}{l}\tau=\nu+\lambda\\ \nu\in V_1, \lambda\in \omega U
\end{array}}c_{0,\nu}^{\alpha}f_{\lambda}^{i_1}\right)t^{\tau}\right]\tilde t^{n\alpha}.
\end{array}
$$
Set
$$
a_1(\tilde t)=\left(\sum_{\alpha\in\cup_{i=1}^niU}b_{0,i_1}^{\alpha}\tilde t^{n\alpha}\right)
$$
and
$$
\begin{array}{lll}
h_{1,\alpha}^1(t)&=&\sum_{\tau\in\omega U}b_{0,i_1}^{\alpha}f_{\tau}^{i_1}t^{\tau},\\
h_{1,\alpha}^2(t)&=&\sum_{\tau\in V_1+\omega U}\left(\sum_{\begin{array}{l}\tau=\nu+\lambda\\ \nu\in V_1, \lambda\in \omega U
\end{array}}c_{0,\nu}^{\alpha}f_{\lambda}^{i_1}\right)t^{\tau}.
\end{array}
$$
We have
$$
\frac{y_1}{d_{i_0}^n}-a_0(\tilde t)-a_1(\tilde t)\tilde t^{ni_1}=\tilde t^{ni_1}\left(\sum_{\alpha\in\cup_{i=1}^niU}
g_{\alpha}^1(t)\tilde t^{n\alpha}\right)
$$
where
$$
g_{\alpha}^1(t)=h_{1,\alpha}(t)+h_{1,\alpha}^2(t)=\sum_{\tau\in\omega U\cup(V_1+\omega U)}b_{1,\tau}^{\alpha}t^{\tau}
$$
with $b_{1,\tau}^{\alpha}\in K(\{e_i\mid i\in U, i\le \mbox{max}\{\tau,\alpha\}\})$.

We have
$$
a_1(\tilde t)=\sum_{\alpha\in \cup_{i=1}^n iU}b_{0,i_1}^{\alpha}\tilde t^{n\alpha}
$$
with $b_{0,i_1}^{\alpha}\in K(\{e_i\mid i\in U, i\le \mbox{max}\{i_1,\alpha\}\le \alpha\})$. Thus
$$
\tilde t^{ni_1}a_1(\tilde t)=\sum_{\alpha\in\cup_{i=1}^n iU}b_{0,i_1}^{\alpha}\tilde t^{n(\alpha+i_1)},
$$
and if $\alpha+i_1\in U$, we have $b_{0,i_1}^{\alpha}\in K(\{\alpha_i\mid i\in U, i\le \alpha<\alpha+i_1\})$.
Set
$$
\gamma_1(\tilde t)=a_0(\tilde t)+\tilde t^{ni_1}a_1(\tilde t).
$$
Expanding $\gamma_1(\tilde t)$, we have
$$
\gamma_1(\tilde t)=\sum_{\lambda\in\omega U}\delta_{\lambda}^1\tilde t^{n\lambda},
$$
with $\delta_{\lambda}^1\in K(\{e_i\mid i\le \lambda\})$ and if $\lambda\in U$, then
$\delta_{\lambda_1}=ne_{\lambda}+\omega_{\lambda}^1$ with $\omega_{\lambda}^1\in K(\{e_i\mid i< \lambda\})$.
$$
\sum_{\alpha\in\cup_{i=1}^niU}g_{\alpha}^1(t)\tilde t^{n\alpha}=\sum_{\alpha\in\cup_{i=1}^niU}\left(\sum_{\tau\in\omega U\cup (V_1+\omega U)}b_{1,\tau}^{\alpha}t^{\tau}\right)
$$
with $b_{1,\tau}^{\alpha}\in K(\{e_i\mid i\in U, i\le\mbox{max}\{\tau,\alpha\}\})$.

Now $i_1$ is the smallest element of $\omega U\cup (V_1+\omega U)$. Set
$$
V_2=\{\lambda-i_1\mid \lambda\in \left(\omega U\cup (V_1+\omega U)\right)\setminus {i_1}\}.
$$
We expand
$$
\begin{array}{lll}
g_{\alpha}^1(t)&=& t^{i_1}\left(b_{1,i_1}^{\alpha}+\sum_{\nu\in V_2}b_{1,\nu+i_1}^{\alpha}t^{\nu}\right)\\
&=& t^{i_1}\left(b_{1,i_1}^{\alpha}+\sum_{\nu\in V_2}C_{1,\nu}^{\alpha}t^{\nu}\right)
\end{array}
$$
where
$c_{1,\nu}^{\alpha}\in K(\{e_i\mid i\le\mbox{max}\{\nu-i_1,\alpha\}\})$.
We have, substituting (\ref{eq2}) and (\ref{eq4}),
$$
\begin{array}{lll}
\frac{y_1}{d_{i_0}^n}-\gamma_1(\tilde t)&=&\tilde t^{ni_1}\sum_{\alpha\in \cup_{i=1}^niU}g_{\alpha}^1(t)\tilde t^{n\alpha}\\
&=& \tilde t^{ni_1}\left(\sum_{\alpha\in \cup_{i=1}^niU}t^{i_1}\left(
b_{1,i_1}^{\alpha}+\sum_{\nu\in V_2}c_{1,\nu}^{\alpha}t^{\nu}\right)\tilde t^{n\alpha}\right)\\
&=&\tilde t^{ni_1}\left(\sum_{\alpha\in \cup_{i=1}^niU}\left(b_{1,i_1}^{\alpha}+\sum_{\nu\in V_2}c_{1,\nu}^{\alpha}t^{\nu}\right)\tilde t^{n\alpha}\tilde t^{ni_1}(1+\Lambda)^{i_1}\right)\\
&=&\tilde t^{ni_1}\left(\sum_{\alpha\in \cup_{i=1}^niU}\left(b_{1,i_1}^{\alpha}+\sum_{\nu\in V_2}c_{1,\nu}^{\alpha}t^{\nu}\right)\tilde t^{n\alpha}\tilde t^{ni_1}(1+\sum_{\lambda\in\omega U}f_{\lambda}^{i_1}t^{\lambda})\right)\\
&=&\tilde t^{n2i_1}\left(\sum_{\alpha\in \cup_{i=1}^niU}\left(b_{1,i_1}^{\alpha}
+\sum_{\tau\in\omega U}b_{1,i_1}^{\alpha}f_{\tau}^{i_1}t^{\tau}\right.\right.\\
&&\left.\left.+\sum_{\tau\in V_2+\omega U}\left(\sum_{\begin{array}{l} \tau=\nu+\lambda\\ \nu\in V_2, \lambda\in\omega U\end{array}}
c_{1,\nu}^{\alpha}f_{\lambda}^{i_1}\right)t^{\tau}\right)\tilde t^{n\alpha}\right).
\end{array}
$$
Set
$$
a_2(\tilde t)=\sum_{\alpha\in \cup_{i=1}^niU}b_{1,i_1}^{\alpha}\tilde t^{n\alpha}
$$
and
$$
\begin{array}{lll}
h_{2,\alpha}^1(t)&=&\sum_{\tau\in\omega U}b_{1,i_1}^{\alpha}f_{\tau}^{i_1}t^{\tau},\\
h_{2,\alpha}^2(t)&=& \sum_{\tau\in V_2+\omega U}\left(\sum_{\begin{array}{l} \tau=\nu+\lambda\\ \nu\in V_2, \lambda\in\omega U\end{array}}
c_{1,\nu}^{\alpha}f_{\lambda}^{i_1}\right)t^{\tau}.
\end{array}
$$
Set
$$
\gamma_2(\tilde t)=a_0(\tilde t)+a_1(\tilde t)\tilde t^{ni_1}+a_2(\tilde t)\tilde t^{n2i_1}.
$$
We have an expansion
$$
\gamma_2(\tilde t)=\sum_{\lambda\in\omega U}\delta_{\lambda}^2\tilde t^{n\lambda}
$$
with
$\delta_{\lambda}^2\in K(\{e_i\mid i\le \lambda\})$, and if $\lambda\in U$,
then $\delta_{\lambda}^2=ne_{\lambda}+\omega_{\lambda}^2$ with $\omega_{\lambda}^2\in K(\{e_i\mid i< \lambda\})$.

We have
$$
\frac{y_1}{d_{i_0}^n}-\gamma_2(\tilde t)=\tilde t^{n2i_1}\left(
\sum_{\alpha\in \cup_{i=1}^n iU}g_{\alpha}^2(t)\tilde t^{n\alpha}\right),
$$
where
$$
g_{\alpha}^2(t)=h_{2,\alpha}^1(t)+h_{2,\alpha}^2(t)=\sum_{\tau\in \omega
U\cup(V_2+\omega U)}b_{2,\tau}^{\alpha}t^{\tau},
$$
with $b_{2,\tau}^{\alpha}\in K(\{e_i\mid i\in U, i\le \mbox{max}\{\tau,\alpha\}\})$.

We iterate to construct for $m\in \NN$, generalized power series
$$
\gamma_m(\tilde t)=\sum_{\lambda\in\omega U}\delta_{\lambda}^m\tilde t^{n\lambda},
$$
such that for all $m$,
$$
\nu_{\tilde t}\left(\frac{y_1}{d_{i_0}^n}-\gamma_m(\tilde t)\right)\ge m i_1,
$$
and
$\delta_{\lambda}^m\in K(\{e_i\mid i\le\lambda\})$, and if $\lambda\in U$,
then $\delta_{\lambda}^m=ne_{\lambda}+\omega_{\lambda}^m$ with $\omega_{\lambda}^m\in K(\{e_i\mid i<\lambda\})$.

Thus there exists a generalized series $\gamma(\tilde t)\in \overline K[[\tilde t^{\QQ_+}]]$, such that
$$
y_1=d_{i_0}^n\gamma(\tilde t),
$$
with
$$
\gamma(\tilde t)=\sum_{\lambda\in\omega U}\delta_{\lambda}\tilde t^{n\lambda},
$$
for all $\lambda$, $\delta_{\lambda}\in K(\{e_i\mid i\le\lambda\})$, and if $\lambda\in U$, then
$\delta_{\lambda}=ne_{\lambda}+\omega_{\lambda}$ with $\omega_{\lambda}\in
K\{e_i\mid i<\lambda\})$.


Set $\beta_1=\beta^{m'}\delta_{i_0}^{-n'}$, $t_1=\tilde t$, $S_1=\omega S$,
and
$$
d_{1,i}=\left\{\begin{array}{ll}
d_{i_0}^n\delta_{\frac{i}{n}}&\mbox{ if $\frac{i}{n}\in\omega U$,}\\
0&\mbox{ otherwise}.
\end{array}
\right.
$$
Then, using (\ref{eq3}) for the expression of $x_1$, we have
$$
\begin{array}{lll}
x_1&=&\beta_1t_1\\
y_1&=& \sum_{i\in S_1}d_{1,i}t_1^i
\end{array}
$$
with $K(d_{i_0})(\{d_{1,i}\mid i\in S_1\})=K(\{d_i\mid i\in S\})$.
Thus the conclusions of the theorem hold.


\end{proof}




\end{document}

\section{Introduction}


Suppose that $k$ is an arbitrary field. Consider the field
$k((x_1,\ldots,x_n))$, which is the quotient field of the  ring
$k[[x_1,\ldots,x_n]]$ of formal power series  in the variables
$x_1,\ldots,x_n$, with coefficients in $k$. Suppose that
$\overline k$ is an algebraic closure of $k$, and $\sigma\in
\overline k[[x_1,\ldots,x_n]]$ is a formal power series. In this
paper, we give a very simple necessary and sufficient condition
for $\sigma$ to be algebraic over $k((x_1,\ldots,x_n))$. We  prove the following theorem, which is restated in an equivalent formulation in Theorem  \ref{multi}.


\begin{Theorem}\label{varfin} Suppose that $k$ is a field of characteristic $p\ge0$,
with algebraic closure $\overline k$.  Suppose that
$$
\sigma(x_1,\ldots,x_n)=\sum_{i_1,\ldots,i_n\in\NN}\alpha_{i_1,\ldots,i_n}
x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}\in \overline k[[x_1,\ldots,x_n]]
$$
where  $\alpha_{i_1,\ldots,i_n}\in \overline k$ for all $i$. Let
$$
L= k(\{\alpha_{i_1,\ldots,i_n}\mid i_1,\ldots,i_n\in\NN\})
$$
 be the extension field of $k$
generated by the coefficients of $\sigma(x_1,\ldots,x_n)$. Then
$\sigma(x_1,\ldots,x_n)$ is algebraic over $k((x_1,\ldots,x_n))$
if and only if there exists $r\in\NN$ such that
$[kL^{p^r}:k]<\infty$, where $kL^{p^r}$ is the compositum of $k$
and $L^{p^r}$ in $\overline k$.

\end{Theorem}

In the case that $L$ is separable over $k$ (Corollary \ref{2}), or  that $k$ is a finitely
generated extension field of a perfect field (Corollary \ref{1}), we have a stronger condition. In these cases, $\sigma$ is algebraic
if and only if  $[L:k]<\infty$. The finiteness condition $[L:k]<\infty$ does not characterize algebraic series over arbitrary base fields $k$ of positive characteristic. To illustrate this, we give a simple example, in Example \ref{example}, of an algebraic series in one variable
for which $[L:k]=\infty$.



 In Section 2, we prove Theorem \ref{varfin}
in the case $n=1$. The most difficult part of the proof arises when $k$ is not perfect. Our proof uses the theorem of resolution of singularities of
a germ of a plane curve singularity over an arbitrary field (c.f. \cite{Ab1}, \cite{O}, \cite{C}). In Section 3, we prove Theorem \ref{varfin} for
any number of variables $n$. The proof  involves induction on the number of variables, and uses the result for one variable proven in Section 2.




In the case when $k$ has characteristic zero and $n=1$, the conclusions
of Theorem \ref{varfin} are classical. We recall the very strong known results,
under the assumption that $k$ has characteristic zero, and there is only one variable ($n=1$).
The algebraic
closure of the field of formal meromorphic power series $k((x))$ in the variable $x$  is
\begin{equation}\label{eqI1}
\overline{k((x))}=\cup_F\cup_{n=1}^{\infty}F((x^{\frac{1}{n}}))
\end{equation}
where $F$ is any finite field extension of $k$ contained in the algebraic
closure $\overline k$ of $k$.  The equality (\ref{eqI1}) is stated and proven  in Ribenboim and Van den Dries' article \cite{RVdD}.
A proof can also be deduced from Abhyankar's Theorem (\cite{Ab3} or Section 2.3 of \cite{GM}).
The equality (\ref{eqI1}) already follows for an algebraically closed field $k$ of characteristic zero
from a classical algorithm of Newton \cite{BK}, \cite{C}.

If $k$ has characteristic $p>0$, then the algebraic closure of
$k((x))$ is much more complicated, even when $k$ is algebraically closed,
because of the existence of Artin Schreier extensions, as  is shown in
Chevalley's book \cite{Ch}. In fact,  the series
\begin{equation}\label{eqC}
\sigma(x)=\sum_{i=1}^{\infty}x^{1-\frac{1}{p^i}},
\end{equation}
considered by Abhyankar in \cite{Ab4},
is algebraic over $k((x))$, as it satisfies the relation
$$
\sigma^p-x^{p-1}\sigma-x^{p-1}=0.
$$
When $k$ is an algebraically closed field of arbitrary characteristic, the
 ``generalized power series'' field $k((x^{\QQ}))$ is algebraically closed, as is shown by Ribenboim
in  \cite{R}. The approach of studying the algebraic closure of $k((x))$
through generalized power series is developed by Benhessi \cite{Be},
Hahn \cite{Ha}, Huang, \cite{Hu}, Poonen \cite{Po}, Rayner \cite{Ra}, Stefanescu \cite{St} and Vaidya \cite{V}. A complete solution when $k$ is a perfect field
is given by Kedlaya in \cite{Ke}. He shows that the algebraic closure of $k((x))$ consists of all ``twist recurrent series'' $u=\sum\alpha_ix^i$
in $\overline k((x^{\QQ}))$
such that all $\alpha_i$ lie in a common finite extension of $k$.

When $n>1$, the algebraic closure of $k((x_1,\ldots,x_n))$ is known to be extremely complicated, even when $k$ is algebraically closed of characteristic
0. In this case,  difficulties occur when the ramification locus of
a finite extension is very singular. There is a good understanding in some
important cases, such as when the ramification locus is a simple normal crossings divisor and the characteristic of $k$ is 0 or the ramification is
tame (Abhyankar \cite{Ab3}, Grothendieck and Murre \cite{GM}) and for quasi-ordinary singularities (Lipman \cite{L2}, Gonz\'alez-P\'erez \cite{G-P}).

More generally, subrings of a power series ring can be very
complex, and are a source of many extraordinary examples, such as
\cite{N}, \cite{Ro}, \cite{HRS}.


As an application of our methods, we give a characterization of valuation rings $V$ which dominate
an excellent, Noetherian local domain $R$ of dimension two, and such that  the rank increases after
passing to the completion of a birational extension of $R$. The characterization is   known
when  the residue field of $R$ is algebraically closed (Spivakovsky \cite{S}).
In this case ($R/m_R$ algebraically closed) the rank increases under completion if and only if $\mbox{dim}_R(V)=0$ ($V/m_V$ is
algebraic over $R/m_R$) and $V$ is discrete of rank 1.


However, the characterization is more subtle over non closed fields.
In Theorem \ref{TheoremV2}, we show that the condition that the rank  increases
under completion is characterized by the two conditions that the residue field of $V$ is finite  over the residue field of $R$, and that $V$ is  discrete of rank 1. The case when the residue field of $V$ is infinite algebraic over the residue field of  $R$ and the value group is discrete of rank 1 can occur,
and the rank of such a valuation does not increase when passing to completion.
In Corollary \ref{Cor}, we show that there exists a valuation ring $V$
dominating $R$ whose value group is discrete of rank 1 with $\mbox{dim}_R(V)=0$ such that
the rank of $V$ does not increase under completion if and only if the algebraic closure
of $R/m_R$ has infinite degree over $R/m_R$.

We point out the contrast of the  conclusions of
Theorem \ref{varfin} with the results of Section 4.  The finiteness condition
$[L:k]<\infty$ of the coefficient field of a series over a base field $k$
does not characterize algebraicity of a series in positive characteristic,
while the corresponding finiteness condition on residue field extensions does
characterize algebraicity (the increase of rank) in the case of valuations dominating a local ring of Theorem \ref{TheoremV2}. We illustrate this distinction in Example \ref{example2} by constructing the valuation ring determined by the series of
Example \ref{example}. We conclude by showing a simple standard power series representation of the valuation associated to the algebraic series of (\ref{eqC}), whose
exponents do not have bounded denominators.

The concept of the rank increasing when passing to the completion already
appears implicitely in Zariski's paper \cite{Z}. Some papers where the concept is developed
are \cite{S}, \cite{HS} and \cite{CG}.

If $R$ is a local (or quasi local) ring, we will denote its maximal ideal by $m_R$.
%\vfill\eject

\section{Series in one variable}

\begin{Lemma}\label{Lemma1}
Suppose that $R$ is a 2 dimensional regular local ring, and $x\in m_R$ is part of a regular system of parameters.

Suppose that $k_0$ is a coefficient field of $\hat R$ and $y\in \hat R$ is such that $x,y$ are regular parameters in $\hat R$. This determinines an isomorphism
$$
\hat R\stackrel{\lambda_0}{\rightarrow} k_0[[x,y]]
$$
of $\hat R$ with a power series ring.
Suppose that $\alpha$ is separably algebraic over $k_0$. Let $y_1=\frac{y}{x}-\alpha$.
Then there exists a maximal ideal $n\subset R[\frac{m_R}{x}]$ and an isomorphism
$$
\widehat{R[\frac{m_R}{x}]_n}\stackrel{\lambda_1}{\rightarrow} k_0(\alpha)[[x,y_1]]
$$
which makes the diagram
$$
\begin{array}{ccc}
\hat R&\stackrel{\lambda_0}{\rightarrow}&k_0[[x,y]]\\
\downarrow&&\downarrow\\
\widehat{R[\frac{m_R}{x}]_n}&\stackrel{\lambda_1}{\rightarrow} &k_0(\alpha)[[x,y_1]]
\end{array}
$$
commute, where the vertical arrows are the natural maps.
\end{Lemma}

\begin{proof} There exists $\tilde y\in R$ such that $\tilde y
=y+h$ where $h\in m_R^3\hat R$. We have
$$
\frac{\tilde y}{x}-\alpha=y_1+\frac{h(x,x(y_1+\alpha))}{x}
=y_1+h_1(x_1,y_1)
$$
where $h_1\in k_0(\alpha)[[x,y_1]]$ is a series of order $\ge 2$.
Thus we have natural change of variables
$k_0[[x,y]]=k_0[[x,\tilde y]]$ and $k_0(\alpha)[[x,y_1]]=k_0(\alpha)[[x,\frac{\tilde y}{x}-\alpha]]$.
We may thus assume that $y\in R$.

We have a natural inclusion induced by $\lambda_0$,
$$
R[\frac{y}{x}]\subset \hat R[\frac{y}{x}]\subset k_0(\alpha)[[x,y_1]].
$$
Let $n=(x,y_1)\cap R[\frac{y}{x}]$.

Let $h(t)$ be the minimal polynomial of $\alpha$ over $k_0$, and $f\in R[\frac{y}{x}]$ be a lift of
$$
h(\frac{y}{x})\in k_0[\frac{y}{x}]\cong R[\frac{y}{x}]/xR[\frac{y}{x}].
$$
Then $n=(x,f)$ and we see that $R[\frac{y}{x}]/n\cong k_0(\alpha)$.
Now the conclusions of the lemma follow from Hensel's Lemma (c.f. Lemma 3.5 \cite{C}).



\end{proof}




\begin{Theorem}\label{main} Suppose that $k$ is a  field, with algebraic closure
$\overline k$. Let $\overline k((x))$ be the field  of formal Laurent series
in a variable $x$  with coefficients in $\overline k$. Suppose that
$$
\sigma(x)=\sum_{i=d}^{\infty}\alpha_ix^i\in \overline k((x))
$$
where  $d\in \ZZ$ and $\alpha_i\in \overline k$ for all $i$. Let $L=k(\{\alpha_i\mid i\in \NN\})$,
and suppose that $L$ is separable over $k$.  Then $\sigma(x)$ is algebraic over $k((x))$ if and
only if
$$
[L:k]<\infty.
$$
\end{Theorem}

\begin{proof} We reduce to the case where $d\ge 1$, by observing that
$\sigma$ is algebraic over $k((x))$ if and only if $x^{1-d}\sigma$ is.

First suppose that $[L:k]<\infty$. Let $M$ be a finite Galois extension of $k$ which contains $L$.
Let $G$ be the Galois group of $M$ over $k$. $G$ acts naturally by $k$ algebra isomorphisms on
$M[[x]]$, and the invariant ring of the action is $k[[x]]$. Let $f(y)=\prod_{\tau\in
G}(y-\tau(\sigma))\in M[[x]][y]$. Since $f$ is invariant under the action of $G$, $f(y)\in
k[[x]][y]$. Since $f(\sigma)=0$, we have that $\sigma$ is algebraic over $k((x))$.


Now suppose that $\sigma(x)=\sum_{i=1}^\infty\alpha_ix^i$ is algebraic over $k((x))$.  Then there
exists
$$
g(x,y)=a_0(x)y^n+a_1(x)y^{n-1}+\cdots +a_n(x)\in k[[x]][y]
$$
such that $a_0(x)\ne 0$, $n\ge 1$, $g$ is irreducible and $g(x,\sigma(x))=0$.

Let
$$
y_0=y, y_1=\frac{y}{x}-\alpha_1,y_2=\frac{y_1}{x}-\alpha_2,\ldots,
y_i=\frac{y_{i-1}}{x}-\alpha_{i},\cdots
$$
and define
$$
S_0=k[[x,y]], S_1=k(\alpha_1)[[x,y_1]], \cdots S_i=k(\alpha_1,\ldots,\alpha_i)[[x,y_i]],\ldots
$$
We have natural inclusions
$$
S_0\rightarrow S_1\rightarrow\cdots \rightarrow S_i\rightarrow \cdots
$$
By Lemma \ref{Lemma1}, there exists a sequence of inclusions
\begin{equation}\label{eq2}
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_i\rightarrow \cdots
\end{equation}
where $R_0=k[[x]][y]_{(x,y)}$ and each $R_i$ is a localization at a maximal ideal of the
blow up of the maximal ideal $m_{R_{i-1}}$ of $R_{i-1}$,
and we have a commutative diagram of homomorphisms
$$
\begin{array}{lllllllll}
S_0&\rightarrow &S_1&\rightarrow&\cdots&\rightarrow&S_i&\rightarrow&\cdots\\
\uparrow&&\uparrow&&&&\uparrow&&\\
R_0&\rightarrow &R_1&\rightarrow&\cdots&\rightarrow&R_i&\rightarrow&\cdots
\end{array}
$$
where the vertical arrows induce isomorphisms of the $m_{R_i}$-adic completions
$\hat R_i$ of $R_i$ with $S_i$.
We further have that $x$ is part of a
regular system of parameters in $R_i$ for all $i$, and $m_{R_{i-1}}R_i=xR_i$ for all $i$.

By our construction, we have that
\begin{equation}\label{eq3}
R_i/m_{R_i}\cong k(\alpha_1,\ldots,\alpha_{i})
\end{equation}
for all $i$.

For all $i$, write $g=x^{b_i}g_i$ where $g_i\in R_i$ and $x$ does not divide $g_i$ in $R_i$.

In $\overline k[[x,y_i]]$, we have a factorization
$$
y-\sigma=x^i(y_i-\sum_{j={i+1}}^{\infty}\alpha_jx^{j-i}).
$$
Since $y-\sigma$ divides $g$ in $\overline k[[x,y]]$, we have that
$y_i-\sum_{j={i+1}}^{\infty}\alpha_jx^{j-i}$ divides $g_i$ in
$\overline k[[x,y_i]]$. Thus $g_i$ is not a unit in $\overline k[[x,y_i]]$,
and is thus not a unit in $R_i$.

Let $C$ be the curve germ $g=0$ in the germ $\mbox{Spec}(R_0)$
of a nonsingular surface. The sequence (\ref{eq2}) is obtained by blowing up
the closed point in  $\mbox{Spec}(R_i)$, and localizing at a point
which is on the strict transform of $C$. $g_i=0$ is a local equation of
the strict transform of $C$ in $\mbox{Spec}(R_i)$. By embedded resolution
of plane curve singularities (\cite{Ab1}, \cite{O} or a simple generalization
of Theorem 3.15 and Exercise 3.13 of \cite{C}) we obtain that there exists $i_0$
such that the total transform of $C$ in $\mbox{Spec}(R_i)$ is a simple normal crossings divisor  for all $i\ge i_0$. Since $x^{b_i}g_i=g=0$ is a local
equation of the total transform of $C$ in $\mbox{Spec}(R_i)$, we have  that
$x,g_i$ are regular parameters in $R_i$ for all $i\ge i_0$.
Thus $g_{i_0}=x^{i-i_0}g_i$ for all $i\ge i_0$, and
$R_i=R_{i-1}[\frac{g_{i-1}}{x}]_{(x,g_i)}$ for all $i\ge i_0+1$.


We thus have that $R_i/m_{R_i}\cong R_{i_0}/m_{R_{i_0}}$ for all $i\ge i_0$,
and we see that
$$
L=\cup_{i\ge 0}R_i/m_{R_i}=R_{i_0}/m_{R_{i_0}} =k(\alpha_1,\ldots,\alpha_{i_0}).
$$
Thus $[L:k]<\infty$.

\end{proof}

\begin{Example}\label{example}  The conclusions of Theorem \ref{main} may fail if $L$ is not separable over $k$.
\end{Example}

\begin{proof} Let $p$ be a prime and $\{t_i\mid i\in\NN\}$ be algebraically independent over
the finite field $\ZZ_p$. Let $k=\ZZ_p(\{t_i\mid i\in\NN\})$. Define
$$
\sigma(x)=\sum_{i=1}^{\infty}t_i^{\frac{1}{p}}x^i\in \overline k[[x]].
$$
Let
$$
f(y)=y^p-\sum_{i=1}^{\infty}t_ix^{ip}\in k[[x]][y].
$$
$\sigma(x)$ is algebraic over $k[[x]]$ since
$$
f(\sigma(x))=(\sigma(x))^p-\sum_{i=1}^{\infty}t_ix^{ip}=0.
$$
However,
$$
[k(\{t_i^{\frac{1}{p}}\mid i\in\NN\}):k]=\infty.
$$
\end{proof}

Suppose that $k$ is a field of characteristic $p>0$ and $L$ is an extension
field of $k$. For $n\in \NN$, let
$$
L^{p^n}=\{f^{p^n}\mid f\in L\}.
$$
If $k$ has characteristic $p=0$, we take $L^{p^n}=L$ for all $n$.

\begin{Theorem}\label{insep} Suppose that $k$ is a field of characteristic $p>0$,
with algebraic closure
$\overline k$. Let $\overline k((x))$ be the field  of formal Laurent series
in the variable $x$ with coefficients in $\overline k$. Suppose that
$$
\sigma(x)=\sum_{i=d}^{\infty}\alpha_ix^i\in \overline k((x))
$$
where  $d\in \ZZ$ and $\alpha_i\in \overline k$ for all $i$.
Let $L= k(\{\alpha_i\mid i\in \NN\})$, and assume that $L$ is purely inseparable over $k$.           Then $\sigma(x)$ is algebraic over $k((x))$ if and only if
there exists $n\in\NN$ such that  $L^{p^n}\subset k$.

\end{Theorem}

\begin{proof} As in the proof of Theorem \ref{main}, we may assume that $d\ge 1$.

First suppose that  $L^{p^n}\subset k$ for some $n$. Then $\tau(x)=\sigma(x)^{p^n}\in k[[x]]$, and $\sigma(x)$ is the root of $y^{p^n}-\tau(x)=0$. Thus $\sigma$ is algebraic over $k((x))$.


Now suppose that
$\sigma(x)=\sum_{i=1}^\infty\alpha_ix^i\in \overline k[[x]]$ is algebraic over
$k((x))$.  Then there exists
$$
g(x,y)=a_0(x)y^n+a_1(x)y^{n-1}+\cdots +a_n(x)\in k[[x]][y]
$$
such that $a_0(x)\ne 0$, $n\ge 1$, $g$ is irreducible and $g(x,\sigma(x))=0$.


Let $K$ be the quotient field of $\overline k[[x]][y]$, and let $R_0:=S_0:=k[[x]][y]_{(x,y)}$. We
will first construct a series of subrings $S_i$ of $K$.

 Define a local $k$-algebra homomorphism $\pi_0:S_0\rightarrow \overline k[[x]]$
by prescribing that $\pi_0(x)=x$ and $\pi_0(y)=\sigma(x)$. The kernel of $\pi_0$ is the prime ideal $gS_0$.
$$
\frac{y}{x}=\sum_{i=0}^{\infty}\alpha_{i+1}x^i \in \overline k[[x]]
$$
defines a $k$-algebra homomorphism
$S_0[\frac{y}{x}]\rightarrow \overline k[[x]]$ which extends $\pi_0$. Let $\lambda(1)\in\NN$ be the
smallest natural number such that $\alpha_1^{p^{\lambda(1)}}\in k$. Then
the maximal ideal $x\overline k[[x]]$ of $\overline k[[x]]$ contracts to
$$
x\overline k[[x]]\cap S_0[\frac{y}{x}]=(x,\left(\frac{y}{x}\right)^{p^{\lambda(1)}}-\alpha_1^{p^{\lambda(1)}}).
$$
Set $y_1=\left(\frac{y}{x}\right)^{p^{\lambda(1)}}-\alpha_1^{p^{\lambda(1)}}$.
Let
$$
S_1=S_0[\frac{y}{x}]_{(x,y_1)}.
$$
Let $\pi_1:S_1\rightarrow \overline k[[x]]$ be the local $k$-algebra homomorphism
 induced by $\pi_0$.


We have that $x,y_1$ is a regular system of parameters in $S_1$, with
$$
y_1=\sum_{i=1}^{\infty}\alpha_{i+1}^{p^{\lambda(1)}}x^{ip^{\lambda(1)}}.
$$
$S_1/m_{S_1}\cong k(\alpha_1)$ and
$$
[S_1/m_{S_1}: S_0/m_{S_0}]=[k(\alpha_1):k]=p^{\lambda(1)}.
$$

Let $\lambda(2)\in\NN$ be the
smallest  natural number such that $\alpha_2^{p^{\lambda(1)+\lambda(2)}}\in k(\alpha_1)$.
Let
$$
y_2=\left(\frac{y_1}{x^{p^{\lambda(1)}}}\right)^{p^{\lambda(2)}}
-\alpha_2^{p^{\lambda(1)+\lambda(2)}}.
$$
Then there is an expansion in $\overline k[[x]]$
$$
y_2=\sum_{i=1}^{\infty}\alpha_{i+2}^{p^{\lambda(1)+\lambda(2)}}x^{ip^{\lambda(1)+\lambda(2)}}.
$$
Let $S_2=S_1[\frac{y_1}{x^{p^{\lambda(1)}}},\alpha_1]_{(x,y_2)}\subset K$. We have a  local $k$-algebra
homomorphism $\pi_2:S_2\rightarrow \overline k[[x]]$ which extends $\pi_1$.  We have
$S_2/m_{S_2}\cong k(\alpha_1,\alpha_2^{p^{\lambda(1)}})$, so that
$$
[S_2/m_{S_2}:S_1/m_{S_1}]=[ k(\alpha_1,\alpha_2^{p^{\lambda(1)}}):k(\alpha_1)]=p^{\lambda(2)}.
$$
We iterate the above construction, defining for $i\ge 2$,
$$
\begin{array}{lll}
y_i&=&\left(\frac{y_{i-1}}{x^{p^{\lambda(1)+\cdots+\lambda(i-1)}}}\right)^{p^{\lambda(i)}}-\alpha_i^{p^{\lambda(1)+\cdots+\lambda(i)}}\\
&=&\sum_{j=1}^{\infty}\alpha_{j+i}^{p^{\lambda(1)+\cdots+\lambda(i)}}
x^{jp^{\lambda(1)+\cdots+\lambda(i)}}
\end{array}
$$
where $p^{\lambda(i)}\in \NN$ is the smallest natural number   such that
$$
\alpha_i^{p^{\lambda(1)+\cdots+\lambda(i)}}\in k(\alpha_1,\alpha_2^{p^{\lambda(1)}},\ldots,\alpha_{i-1}^{p^{\lambda(1)+\cdots+\lambda(i-2)}}).
$$
Define
$$
S_i=S_{i-1}\left[\frac{y_{i-1}}{x^{p^{\lambda(1)+\cdots+\lambda(i-1)}}},
\alpha_{i-1}^{p^{\lambda(1)+\cdots+\lambda(i-2)}}\right]
_{(x,y_i)},
$$
to construct an infinite commutative diagram of regular local rings, which are contained in $K$,
$$
\begin{array}{lllllllll}
S_0&\rightarrow&S_1&\rightarrow&\cdots&\rightarrow&S_i&\rightarrow&\cdots\\
\pi_0\downarrow&&\pi_1\downarrow&&&&\pi_i\downarrow&&\\
\overline k[[x]]&=&\overline k[[x]]&=&\cdots&=&\overline k[[x]]&=&\cdots
\end{array}
$$
We have
\begin{equation}\label{eq30}
S_i/m_{S_i}\cong S_{i-1}/m_{S_{i-1}}[\alpha_i^{p^{\lambda(1)+\cdots+\lambda(i-1)}}]
\end{equation}
and
$$
[S_i/m_{S_i}:S_{i-1}/m_{S_{i-1}}]=p^{\lambda(i)}.
$$


For all $i$, the field
$$
k_i:=k(\alpha_1,\alpha_2^{p^{\lambda(1)}},
\ldots,\alpha_{i-1}^{p^{\lambda(1)+\cdots+\lambda(i-2)}})\subset S_i,
$$
and
$$
S_i/m_{S_i}\cong k_i[\alpha_i^{p^{\lambda(1)+\cdots+\lambda(i-1)}}].
$$
We now construct a sequence
$$
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_i\rightarrow\cdots
$$
of birationally equivalent regular local rings such that there is
a commutative diagram of local $k$-algebra homomorphisms
$$
\begin{array}{lllllllll}
R_0&\rightarrow &R_1&\rightarrow &\cdots&\rightarrow&R_i&\rightarrow&\cdots\\
\downarrow&&\downarrow&&&&\downarrow&&\\
S_0&\rightarrow &S_1&\rightarrow &\cdots&\rightarrow&S_i&\rightarrow&\cdots
\end{array}
$$
satisfying
$$
m_{R_i}S_i=m_{S_i}\text{ and }S_i/m_{S_i}\cong R_i/m_{R_i}
$$
for all $i$. The vertical arrows are inclusions.

This is certainly the case for $R_0=S_0$, so we suppose that we have constructed the sequence
out to $R_i\rightarrow S_i$, and show that we may extend it to
$R_{i+1}\rightarrow S_{i+1}$.

We have
$$
\alpha_{i+1}^{p^{\lambda(1)+\cdots+\lambda(i+1)}}\in
k(\alpha_1,\alpha_2^{p^{\lambda(1)}},\ldots,\alpha_i^{p^{\lambda(1)+\cdots+\lambda(i-1)}})\cong R_i/m_{R_i}.
$$
Thus there exists $\phi\in R_i$ such that the class  of $\phi$ in $R_i/m_{R_i}$ is
$$
[\phi]=\alpha_{i+1}^{p^{\lambda(1)+\cdots+\lambda(i+1)}}.
$$
Our assumptions $m_{R_i}S_i=m_{S_i}$ and $S_i/m_{S_i}\cong R_i/m_{R_i}$ imply that
\begin{equation}\label{eqz}
m_{R_i}^n/m_{R_i}^{n+1}\cong m_{S_i}^n/m_{S_i}^{n+1}
\end{equation}
as $R_i/m_{R_i}$ vector spaces for all $n\in \NN$.




By (\ref{eqz}), there exists $z_i\in R_i$ such that
$$
z_i=y_i+h
$$
with $h\in m_{S_i}^{2+p^{\lambda(1)+\cdots+\lambda(i)}}$. We then have that $m_{R_i}=(x,z_i)$, since $m_{R_i}/m_{R_i}^2\cong m_{S_i}/m_{S_i}^2$ as $R_i/m_{R_i}$ vector spaces, and by
Nakayama's Lemma. Now

$$
\begin{array}{lll}
\left(\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}
&=&\left(\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}
+\left(\frac{h}
{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}\\
&=&\left(\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}+xh'
\end{array}
$$
for some $h'\in S_i[\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}]$.
$$
\left(\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}
-\phi\in
R_i\left[\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]\subset
S_i\left[\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]
$$

has residue
$$
\left(\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}-\alpha_{i+1}^{p^{\lambda(1)+\cdots+\lambda(i+1)}}
$$
in $S_{i+1}/xS_{i+1}\cong
S_i/m_{S_i}\left[\frac{y_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]$. Thus

$$
m_{S_{i+1}}\cap
R_i\left[\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]
=(x,\left(\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}-\phi).
$$
Let
$$
R_{i+1}=R_i\left[\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]_{(x,\left(\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right)^{p^{\lambda(i+1)}}-\phi)}.
$$

We have $m_{R_{i+1}}S_{i+1}=m_{S_{i+1}}$ (by Nakayama's Lemma) and $R_{i+1}/m_{R_{i+1}}\cong S_{i+1}/m_{S_{i+1}}$.

 We have  factorizations $g(x,y)=x^{\beta_i}g_i$ where $\beta_i\in\NN$ and
$g_i\in R_i$ is either irreducible or a unit. $g_i$ is a strict transform of $g$ in
$R_i$. Since $\pi_i(x)\ne 0$, we have that $g_i$ is contained in the kernel of the map
$R_i\rightarrow S_i\stackrel{\pi}{\rightarrow} \overline k[[x]]$,
 and thus the ideal $(g_i)$ is the (nontrivial) kernel of $R_i\rightarrow \overline k[[x]]$. In particular, $g_i\in M_{R_i}$ for all $i$.

Each  extension $R_i\rightarrow R_{i+1}$ can be factored as a sequence of $p^{\lambda(1)+\cdots+\lambda(i)}$ birationally equivalent regular local rings,
each of which is a quadratic transform (the blow up of the maximal ideal followed by localization). The $j$-th local ring with $j<p^{\lambda(1)+\cdots+\lambda(i)}$, has the maximal ideal $(x,\frac{z_i}{x^j})$.

By embedded resolution of plane curve singularities (\cite{Ab1}, \cite{C}, \cite{O}), we obtain that there exists $i_0$ such that $g=0$ is a simple normal crossings divisor in $\mbox{Spec}(R_i)$ for all $i\ge i_0$, so that
$x,g_i$ is  a regular system of parameters in $R_i$ for all $i\ge i_0$. Thus
$$
R_{i+1}=R_i\left[\frac{z_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}}\right]_{(x,\frac{g_i}{x^{p^{\lambda(1)+\cdots+\lambda(i)}}})}
$$
for all $i\ge i_0$, and
$$
S_{i+1}/m_{S_{i+1}}\cong R_{i+1}/m_{R_{i+1}}\cong R_i/m_{R_i}\cong S_i/m_{S_i}
$$
for all $i\ge i_0$. Thus $\lambda(i)=0$
for all $i\ge i_0+1$.

Let $$
M=k(\alpha_1,\alpha_2^{p^{\lambda(1)}},\ldots,\alpha_{i_0}^{p^{\lambda(1)+\cdots+\lambda(i_0-1)}})\cong S_{i_0}/m_{S_{i_0}}.
$$
From (\ref{eq30}), we see that $L^{p^{\lambda(1)+\cdots+\lambda(i_0)}}\subset M$. Since $M$ is a finitely generated  purely inseparable extension of $k$, there exists $r\in\NN$ such that $M^{p^r}\subset k$. Thus
$L^{p^{\lambda(1)+\cdots+\lambda(i_0)+r}}\subset k$.


\end{proof}



\begin{Theorem}\label{fin} Suppose that $k$ is a field of characteristic $p\ge0$,
with algebraic closure
$\overline k$. Let $\overline k((x))$ be the field  of formal Laurent series with coefficients in $\overline k$. Suppose that
$$
\sigma(x)=\sum_{i=d}^{\infty}\alpha_ix^i\in \overline k((x))
$$
where  $d\in \ZZ$ and $\alpha_i\in \overline k$ for all $i$.
Let $L= k(\{\alpha_i\mid i\in \NN\})$.       Then $\sigma(x)$ is algebraic over $k((x))$ if and only if
there exists $n\in\NN$ such that  $[kL^{p^n}:k]<\infty$, where $kL^{p^n}$
is the compositum of $k$ and $L^{p^n}$ in $\overline k$.

\end{Theorem}

\begin{proof}
First suppose that $[kL^{p^n}:k]<\infty$ for some $n$. After possibly replacing
$n$ with a larger value of $n$, we may assume that $kL^{p^n}$ is separable over $k$.
Then $\sigma(x)^{p^n}$
is algebraic over $k((x))$ by Theorem \ref{main}, and thus $\sigma(x)$ is algebraic over $k((x))$.


Now suppose that $\sigma(x)$ is algebraic over $k((x))$. Let $M$
be the separable closure of $k$ in $L$. Then $\sigma(x)$ is
algebraic over $M((x))$. Since $L$ is a purely inseparable
extension of $M$, it follows from Theorem \ref{insep} that
$\tau(x)=\sigma(x)^{p^n}\in M[[x]]$ for some $n\in\NN$. Since
$\tau(x)$ is algebraic over $k((x))$, we have that
$[kL^{p^n}:k]<\infty$ by Theorem \ref{main}.
\end{proof}



\begin{Corollary} Suppose that $k$ is a  field of characteristic $p\ge 0$ such that $k$ is a finitely generated extension of a perfect field, with algebraic closure
$\overline k$. Let $\overline k((x))$ be the field  of formal Laurent series with coefficients in $\overline k$. Suppose that
$$
\sigma(x)=\sum_{i=d}^{\infty}\alpha_ix^i\in \overline k((x))
$$
where  $d\in \ZZ$ and $\alpha_i\in \overline k$ for all $i$. Let $L=k(\{\alpha_i\mid i\in \NN\})$.  Then $\sigma(x)$ is algebraic over $k((x))$ if and
only if
$$
[L:k]<\infty.
$$
\end{Corollary}

\begin{proof}
If $[L:k]<\infty$, then $\sigma(x)$ is algebraic over $k((x))$ by Theorem
\ref{fin}.

Suppose that $\sigma(x)$ is algebraic over $k((x))$. By
assumption, there exists a perfect field $F$ and $s_1,\ldots,
s_r\in k$ such that $k=F(s_1,\ldots,s_r)$. By Theorem \ref{fin},
there exists $n$ such that $[kL^{p^n}:k]<\infty$. Thus
$kL^{p^n}=F(s_1,\ldots,s_r,\beta_1,\ldots,\beta_s)$ where
$\beta_1,\ldots,\beta_s\in kL^{p^n}$ are algebraic over $k$. Thus
$$
L\subset F(s_1^{\frac{1}{p^n}},\ldots,s_r^{\frac{1}{p^n}},\beta_1^{\frac{1}{p^n}},
\ldots,\beta_s^{\frac{1}{p^n}}).
$$
Now
$$
[F(s_1^{\frac{1}{p^n}},\ldots,s_r^{\frac{1}{p^n}}):F(s_1,\ldots,s_r)]<\infty
$$
and since $\beta_1,\ldots,\beta_s$ are algebraic over $F(s_1,\ldots,s_r)$,
$$
[F(s_1^{\frac{1}{p^n}},\ldots,s_r^{\frac{1}{p^n}},\beta_1^{\frac{1}{p^n}},
\ldots,\beta_s^{\frac{1}{p^n}}):
F(s_1^{\frac{1}{p^n}},\ldots,s_r^{\frac{1}{p^n}})]<\infty.
$$
Thus
$$
[L:k]\le [F(s_1^{\frac{1}{p^n}},\ldots,s_r^{\frac{1}{p^n}},\beta_1^{\frac{1}{p^n}},
\ldots,\beta_s^{\frac{1}{p^n}}):k]<\infty.
$$
\end{proof}


\section{Series in several variables}

%%%%%%%%% induction for higher dimensions

We will now generalize theorem \ref{fin} to higher dimensions.

Denote by $X$ an $n$-dimensional indeterminate vector
$(x_1,x_2,\dots,x_n)$ and by $I$ an $n$-dimensional exponent vector
$(i_1,i_2,\dots,i_n)\in\mathbb{N}^n$. Then for $1\le l\le n$ write
$X_l=(x_1,x_2,\dots,x_l)$, $I_l=(i_1,i_2,\dots,i_l)$ and
$X^I_l=X_l^{I_l}=x_1^{i_1}x_2^{i_2}\cdots x_l^{i_l}$. If $E$ is a
field denote by $E[[X]]$ the formal power series ring in $n$
variables with coefficients in $E$ and by $E((X))$ the quotient
field of $E[[X]]$. Also denote by $E^c$ the perfect closure of $E$
and by $\overline{E}$ the algebraic closure of $E$.

\begin{Lemma}\label{separation}
Suppose that $E$ is a field and $F$ is a field extension of $E$. Let
$$
\s=\sum_{I\in\mathbb{N}^n}\a_IX^I\in F[[X]], {\text{ with }} \a_I\in
F,
$$
be a formal power series in $n$ variables with coefficients in $F$.
For any $1\le l\le n$ and $I\in\mathbb{N}^n$ define the following
power series in 1 variable with coefficients in $F$
$$
a_{I,l}=\sum_{j=0}^{\infty}\a_Jx_l^j, {\text{ where }}
J=(i_1,i_2,\dots,i_{l-1},j,i_{l+1},\dots,i_n).
$$
Then $\s$ is algebraic over $E((X))$ implies $a_{I,l}$ is algebraic
over $E((x_l))$.
\end{Lemma}

\begin{proof}
We use induction on the number of variables. If $n=1$ the
statement is trivial. Suppose that $n>1$. After possibly permuting
the variables we may assume that $l=1$. Write
$X_{n-1}=(x_1,\dots,x_{n-1})$ and for all $m\in\mathbb{N}$
consider the power series in $n-1$ variables
$$
\d_m=\sum_{R\in\mathbb{N}^n,\,r_n=m}\a_RX^R_{n-1}=
\sum_{R\in\mathbb{N}^n,\,r_n=m}\a_Rx_1^{r_1}x_2^{r_2}\cdots
x_{n-1}^{r_{n-1}}.
$$
If $\d_{i_n}$ is algebraic over $E((X_{n-1}))$ it will follow from
the inductive hypothesis that $a_{I,1}$ is algebraic over
$E((x_1))$. We will show that $\d_m$ is algebraic over
$E((X_{n-1}))$ for all $m\in\mathbb{N}$.

Consider the algebraic dependency relation for $\s$ over $E((X))$
$$
c_t(X)\s^t+c_{t-1}(X)\s^{t-1}+\dots+c_1(X)\s+c_0(X)=0.
$$
By clearing the denominators we may assume that $c_j\in E[[X]]$ for
all $0\le j\le t$. Let $g$ be the highest power of $x_n$ that
divides $c_j$ for all $j$. Set
$c'_j=(x_n^{-g}c_j)(x_1,x_2,\dots,x_{n-1},0)$. Then $c'_j\in
E[[X_{n-1}]]$ and the following equation holds
$$
c'_t(X_{n-1})\d^t_0+c'_{t-1}(X_{n-1})\d^{t-1}_0+\dots+c'_1(X_{n-1})\d_0+c'_0(X_{n-1})=0,
$$
where $c'_j\neq 0$ for some $0\le j\le t$. Thus $\d_0$ is algebraic
over $E((X_{n-1}))$.

Set $\s_1=x_{n}^{-1}(\s-\d_0)$. Then $\s_1\in F[[X]]$ and it is
algebraic over $E((X))$. Arguing as above we get that $\d_1$ is
algebraic over $E((X_{n-1}))$. In general we define
$\s_m=x_n^{-1}(\s_{m-1}-\d_{m-1})$ recursively for all
$m\in\mathbb{N}$ and use $\s_m$ to prove that $\d_m$ is algebraic
over $E((X_{n-1}))$.
\end{proof}



\begin{Theorem}\label{multi}
Suppose that $k$ is a field of characteristic $p\ge 0$. Suppose
that
$$
\s=\sum_{I\in\mathbb{N}^n}\alpha_I X^I\in \overline k[[X]],
{\text{ with }} \a_I\in\overline{k}
$$
is a formal power series in $n$ variables with coefficients in
$\overline{k}$. Let $L=k(\{\alpha_I\mid I\in\mathbb{N}^n\})$ be
the extension field of $k$ generated by the coefficients of $\s$.
Then $\s$ is algebraic over $k((X))$ if and only if there exists
$r\in\mathbb{N}$ such that $[kL^{p^r}:k]<\infty$, where $kL^{p^r}$
is the compositum of $k$ and $L^{p^r}$ in $\overline k$.
\end{Theorem}

\begin{proof}
First suppose that there exists $r\in\mathbb{N}$ such that
$[kL^{p^r}:k]<\infty$. After possibly increasing $r$ we may assume
that $kL^{p^r}$ is a separable extension of $k$. Let $M$ be a
finite Galois extension of $k$ which contains $kL^{p^r}$. Notice
that $kL^{p^r}=k(\{\a_I^{p^r}\mid I\in\mathbb{N}^n\})$ and,
therefore $\s^{p^r}\in M[[X]]$. Let $G$ be the Galois group of $M$
over $k$. $G$ acts naturally by $k$ algebra isomorphisms on
$M[[X]]$, and the invariant ring of the action is $k[[X]]$. Let
$f(y)=\prod_{\tau\in G}(y-\tau(\s^{p^r}))\in M[[X]][y]$. Since $f$
is invariant under the action of $G$, $f(y)\in k[[X]][y]$. Since
$f(\s^{p^r})=0$, we have that $\s$ is algebraic over $k[[X]]$.

To prove the other implication we use induction on the number of
variables. When $n=1$ the statement follows from theorem
\ref{fin}. Assume that $n>1$.

For all $I\in\mathbb{N}^n$ let
$$
a_I=\sum_{j=0}^{\infty}\a_Jx_n^j, {\text { with }}
J=(i_1,i_2,\dots,i_{n-1},j),
$$
be a power series in 1 variable with coefficients in
$\overline{k}$. If $K=k((x_n))$ then by lemma \ref{separation}
$a_I$ is algebraic over $K$ for all $I\in\mathbb{N}^n$. Then
$$
\s=\sum_{\{I\in\mathbb{N}^n\,\mid\, i_n=0\}}a_IX^I_{n-1}
$$
is a series in $n-1$ variables with coefficients in
$\overline{K}$. By the inductive hypothesis there exists
$N\in\mathbb{N}$ and $r\in\mathbb{N}$ such that $K(\{a_I^{p^r}\mid
I\in\mathbb{N}^n\})=K(a^{p^r}_{I_1},a^{p^r}_{I_2},\dots,a^{p^r}_{I_N})$.
Thus, for all $I\in\mathbb{N}^n$ we have $a_I^{p^r}$ is a
polynomial in $a^{p^r}_{I_1},a^{p^r}_{I_2},\dots,a^{p^r}_{I_N}$
with coefficients in $K$.

Fix $I\in\mathbb{N}$, if $j\in\mathbb{N}$ set
$J=(i_1,i_2,\dots,i_{n-1},j)$ and write
$$
\sum_{j=0}^{\infty}\a_J^{p_r}x_n^{jp^r}=
a^{p^r}_I=\sum_{S\in\{0,1,\dots,T\}^N}(\sum_{m=-M_S}^{\infty}\g_{S,m}x_n^m)
(a_{I_1}^{p^r})^{s_1}(a_{I_2}^{p^r})^{s_2}\cdots
(a_{I_N}^{p^r})^{s_N},
$$
where $T\in\mathbb{N}$, $S=(s_1,s_2,\dots,s_N)$ is an index
vector, $M_S\in\mathbb{N}$ and $\g_{S,m}\in k$ for all $S$ and
$m$. This implies that for all $I\in\mathbb{N}$ and
$j\in\mathbb{N}$, $\a_J^{p^r}$ is a polynomial in the coefficients
of power series $a_{I_1}^{p^r},a_{I_2}^{p^r},\dots,a_{I_N}^{p^r}$
over $k$. Moreover, for all $r'\ge r$ we also have $\a_J^{p^{r'}}$
is a polynomial in the coefficients of power series
$a_{I_1}^{p^{r'}},a_{I_2}^{p^{r'}},\dots,a_{I_N}^{p^{r'}}$ over
$k$. Thus $kL^{p^{r'}}$ is the field extension of $k$ generated by
the coefficients of power series
$a_{I_1}^{p^{r'}},a_{I_2}^{p^{r'}},\dots,a_{I_N}^{p^{r'}}$.

Applying theorem \ref{fin} to each of the series
$a_{I_1},a_{I_2},\dots,a_{I_N}$ we see that there exists
$R\in\mathbb{N}$ such that $kL^{p^R}$ is finitely generated over
$k$.

\end{proof}

Similarly to the case of one variable we deduce the following
corollary

\begin{Corollary}\label{1}
Suppose that $k$ is a field of characteristic $p\ge 0$ such that
$k$ is a finitely generated extension of a perfect field. Suppose
that
$$
\s=\sum_{I\in\mathbb{N}^n}\alpha_I X^I\in \overline k[[X]],
{\text{ with }} \a_I\in\overline{k}
$$
is a formal power series in $n$ variables with coefficient in
$\overline{k}$. Let $L=k(\{\alpha_I\mid I\in\mathbb{N}^n\})$ be
the extension field of $k$ generated by the coefficients of $\s$.
Then $\s$ is algebraic over $k((X))$ if and only if
$[L:k]<\infty$.
\end{Corollary}

Also notice that if $E$ is a field of characteristic $p\ge 0$ and
$a$ is separable algebraic over $E$ then for all $r\in\mathbb{N}$
we have $E[a^{p^r}]=E[a]$. Thus if $F$ is a separable extension of
$E$, $EF^{p^r}=F$ for all $r\in\mathbb{N}$. So we have the
following statement in case of separable extensions.

\begin{Corollary}\label{2}
Suppose that $k$ is a field of characteristic $p\ge 0$. Suppose
that
$$
\s=\sum_{I\in\mathbb{N}^n}\alpha_I X^I\in \overline k[[X]],
{\text{ with }} \a_I\in\overline{k}
$$
is a formal power series in $n$ variables with coefficient in
$\overline{k}$. Let $L=k(\{\alpha_I\mid I\in\mathbb{N}^n\})$ be
the extension field of $k$ generated by the coefficients of $\s$.
Suppose that $L$ is separable over $k$. Then $\s$ is algebraic
over $k((X))$ if and only if $[L:k]<\infty$.
\end{Corollary}

\section{Valuations whose rank increases under completion}

Suppose that $K$ is a field and $V$ is a valuation ring of $K$. We will say that
{\it the rank of $V$ increases under completion} if there exists an analytically normal local domain $T$ with quotient field $K$ such that $V$ dominates $T$
and there exists an extension of $V$ to a valuation ring of the quotient field of $\hat T$
which dominates $\hat T$ which has higher rank than the rank of $V$.

Suppose that $V$ dominates an excellent local ring $R$ of dimension 2. Then
by resolution of surface singularities \cite{L}, there exists a regular local ring $R_0$ and a birational extension
$R\rightarrow R_0$ such that $V$ dominates $R_0$. Let
\begin{equation}\label{eq1}
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_n\rightarrow\cdots
\end{equation}
be the infinite sequence of regular local rings obtained by blowing up
the maximal ideal of $R_i$ and localizing at the center of $V$.
Since $R$ has dimension 2, we have that $V=\cup_{i=0}^{\infty}R_i$ (as is shown in \cite{Ab2}), and
thus $V/m_V=\cup_{i=0}^{\infty}R_i/m_{R_i}$. We see that $V/m_V$ is countably generated over $R/m_R$.

Suppose that the rank of $V$ increases under completion. Then there exists $n$
such that for all $i\ge n$, there exists a valuation ring $V_1$ of the quotient field of the regular
local ring $\hat R_i$ which extends $V$, dominates $\hat R_i$, and has rank larger than 1. By the Abhyankar inequality (\cite{Ab2} or Proposition 3 of Appendix 2 \cite{ZS}),
we have that $R_i$ has dimension 2, $V_1$ is discrete of rank 2, and
$V_1/m_{V_1}$ is algebraic over $\hat R_i/m_{\hat R_i}$. Thus $V/m_V$ is algebraic over $R/m_R$ and $V$ is discrete of rank 1.

  It was shown by Spivakovsky \cite{S} in the case that $R/m$ is algebraically closed that the converse holds, giving
the following simple characterization.

\begin{Theorem}\label{TheoremV1}(Spivakovsky \cite{S})
Suppose that $V$ dominates an excellent two dimensional  local ring $R$ who residue field
$R/m_R$ is algebraically closed. Then the rank of $V$ increases under completion
if and only if $\mbox{dim}_R(V)=0$ and $V$ is discrete of rank 1.
\end{Theorem}


The condition that the transcendence degree $\mbox{dim}_R(V)$ of $V/m_V$ over
$R/m_R$ is zero is just the statement that $V/m_V$ is algebraic over $R/m_R$.
In the case that $R/m_R$ is algebraically closed, $\mbox{dim}_R(V)=0$
if and only if $V/m_V=R/m_R$.

Using a similar method to that used in the proof of our algebraicity theorem on power series, Theorem \ref{main}, we prove the
following extension of Theorem \ref{TheoremV1}.

\begin{Theorem}\label{TheoremV2}
Suppose that $V$ is a valuation ring of a field $K$, and $V$ dominates an excellent two dimensional  local domain $R$ whose quotient field is $K$. Then the rank of $V$ increases under completion
if and only if $V/m_V$ is finite over $R/m_R$ and $V$ is discrete of rank 1.
\end{Theorem}

\begin{proof}
First assume that the rank of $V$ increases under completion.
Consider the sequence (\ref{eq1}).
We observed above after (\ref{eq1}) that $V/m_V$ is algebraic over $R/m_R$
and $V$ is discrete of rank 1. Further, there exists $R_i$ and a valuation
$V_1$ of the quotient field  of $\hat R_i$ which dominates $\hat R_i$ whose intersection with the quotient field $K$ of $R$ is $V$, and the rank of $V_1$ is 2. Without loss of generality, we may assume that $R_i=R_0$.









For $i\ge 0$, let $p(R_i)_{\infty}$ be the (nontrivial) prime ideal in $\hat R_i$ of cauchy sequences whose value is greater than $n$ for any $n\in\NN$
(Section 5 of \cite{CG}). Since $\hat R_i$ is a two dimensional regular local ring, $p(R_i)_{\infty}$ is generated by an irreducible element in $\hat R_i$ for all $i$. Let $f$ be a generator of $p(R_0)_{\infty}$. By resolution of plane curve singularities (\cite{Ab1}, \cite{C}, \cite{O}), there exists $i$ in the sequence (\ref{eq1}) such that
$f=h_if_i$, where  $h_i\in R_i$ is such that $h_i=0$ is supported on the
exceptional locus of  $\mbox{Spec}(R_i)\rightarrow \mbox{Spec}(R)$,
and $f_i\in \hat R_i$ is such that $\hat R_i/f_i\hat R_i$ is a regular local ring.
We necessarily have that $p(R_i)_{\infty}=f_i\hat R_i$. Again, without loss of generality, we may assume that $i=0$. Let $T_0=\hat R_0$, and let
$$
T_0\rightarrow T_1\rightarrow \cdots \rightarrow T_n\rightarrow\cdots
$$
be the infinite sequence of regular local rings obtained by blowing up the maximal ideal of the regular local ring $T_i$ and localizing at the center of $V_1$.  We then have a commutative diagram
\begin{equation}\label{eq5}
\begin{array}{lllllllllll}
R_0&\rightarrow &R_1&\rightarrow&\cdots&\rightarrow &R_i&\rightarrow&\cdots\\
\downarrow&&\downarrow&&&&\downarrow&&\\
T_0&\rightarrow &T_1&\rightarrow&\cdots&\rightarrow &T_i&\rightarrow&\cdots\\
\downarrow&&\downarrow&&&&\downarrow&&\\
\hat R_0&\rightarrow &\hat R_1&\rightarrow&\cdots&\rightarrow &\hat R_i&\rightarrow&\cdots\\
\end{array}
\end{equation}

There exists $x\in R_0$ such that $x,f_0$ is a regular system of parameters in $T_0$.  Thus $T_1=T_0[\frac{f_0}{x}]_{(x,\frac{f_0}{x})}$. Define
$f_i=\frac{f_0}{x^i}$ for $i\ge 1$. Then $T_i=T_0[f_i]_{(x,f_i)}$ and
$p(R_i)_{\infty}=f_i\hat R_i$ for all $i\ge 0$. Thus $R_i/m_{R_i}\cong T_i/m_{T_i}\cong
T_0/(x,f_0)\cong R_0/m_{R_0}$ for all $i$. Since $V/m_V=\cup_{i\ge 0} R_i/m_{R_i}
=R_0/m_{R_0}$ and $R_0/m_{R_0}$ is finite over $R/m_R$, we have the conclusions of
the theorem.


Now assume that $V/m_V$ is finite over $R/m_R$ and $V$ is discrete of rank 1.
Consider the sequence (\ref{eq1}). There exists $i$ such that $R_i/m_{R_i}=V/m_V$. Without loss of generality, we may assume that $R=R_i$.
Let $\nu$ be  a valuation of $K$ such that $V$ is the valuation ring of $\nu$.
We may also assume that there are regular parameters $x,y$ in $R$ such that
$\nu(x)=1$ generates the value group $\ZZ$ of $\nu$.  Let $\pi:R\rightarrow R/m_R=V/m_V$ be the residue map. Let $y_0=y$.
There exists $n_0\in\NN$ such that $\nu(y)=n_0$. Let $\alpha_0\in R$ be such that $\pi(\alpha_0)=[\frac{y}{x^{n_0}}]\in V/m_V$. Let $y_1=y-\alpha_0x^{n_0}$,
and let $n_1=\nu(y_1)$. We have $n_1>n_0$. Iterate, to construct $y_i\in R$
and $n_i\in \NN$ with $\nu(y_i)=n_i$ for
$i\in \NN$ by choosing $\alpha_i\in R$ such that $y_{i+1}=y_i-\alpha_ix^{n_i}$
satisfies $n_{i+1}>n_i$. Thus $\{y_i\}$ is a Cauchy sequence in $R$. Let $\sigma$ be the limit of $\{y_i\}$ in $\hat R$.  Let $\hat \nu$ be an extension of $\nu$ to the quotient field of $\hat R$ which dominates $\hat R$.
Then $\hat\nu(\sigma)>n$ for all $n\in\NN$, so that $\hat \nu$ has rank $2>1$,
and we see that the rank of $V$ increases under completion.
\end{proof}



We see that the condition that $V/m_V$ is finite over $R/m_R$ thus divides the
class of discrete rank 1  valuation rings with $\mbox{dim}_R(V)=0$ into two subclasses, those
whose rank increases under completion ($[V/m_V:R/mR]<\infty$), and those whose rank does not increase ($[V/m_V:R/mR]=\infty$). We have the following precise
characterization of when this division into subclasses is nontrivial.








\begin{Corollary}\label{Cor} Suppose that $R$ is an excellent two dimensional local ring.
Then there exists a rank 1 discrete valuation ring $V$ of the quotient field of $R$ which dominates
$R$ such that $\mbox{dim}_R(V)=0$ and the rank of $V$ does not increase under completion if and
only if $[\overline k:k]=\infty$, where $\overline k$ is the algebraic closure of $k=R/m_R$.
\end{Corollary}

\begin{proof} Suppose that  $[\overline k:k]<\infty$, and $V$ is a rank 1 discrete
 valuation ring  of the quotient field of $R$
which dominates $R$ such that $\mbox{dim}_R(V)=0$. Then
$$
[V/m_V:k]\le [\overline k:k]<\infty.
$$
Thus the rank of $V$ must increase under completion by Theorem \ref{TheoremV2}.

Now suppose that $[\overline k:k]=\infty$. We will construct a rank 1 discrete
valuation ring $V$ of the quotient field of $R$ which dominates $R$ such that
$\mbox{dim}_R(V)=0$ and the rank of $V$ does not increase under completion.

There exists a two dimensional regular local ring $R_0$ which birationally
dominates $R$. We have $[\overline k:R_0/m_{R_0}]=\infty$.
Let $x,y_0$ be a regular system of parameters in $R_0$. We will inductively construct an infinite birational sequence of regular local rings
$$
R_0\rightarrow R_1\rightarrow\cdots\rightarrow R_i\rightarrow\cdots
$$
such that $R_i$ has a regular system of parameters $x,y_i$ and
$[R_i/m_{R_i}:R_{i-1}/m_{R_{i-1}}]>1$ for all $i$.
Suppose that we have defined the sequence out to $R_i$. Choose
$\alpha_{i+1}\in\overline k-R_i/m_{R_i}$. Let $h_{i+1}(t)$ be the minimal polynomial of $\alpha_{i+1}$ in the polynomial ring $R_i/m_{R_i}[t]$.
We have an isomorphism
$$
R_i\left[\frac{m_{R_i}}{x}\right]/x R_i\left[\frac{m_{R_i}}{x}\right]
\cong R_i/m_{R_i}\left[\frac{y_i}{x}\right].
$$
Let $y_{i+1}$ be a lift of $h_{i+1}(\frac{y_i}{x})$ to $R_i\left[\frac{m_{R_i}}{x}\right]$. Let
$$
R_{i+1}=R_i\left[\frac{m_{R_i}}{x}\right]_{(x,y_{i+1})}.
$$
We have that $R_{i+1}/m_{R_{i+1}}\cong R_i/m_{R_i}(\alpha_{i+1})$.

Let $V=\cup_{i=0}^{\infty}R_i$. $V$ is a valuation ring which dominates $R$
(as is shown in \cite{Ab2}).
$V/m_V=\cup_{i=0}^{\infty}R_i/m_{R_i}$ so that $\mbox{dim}_R(V)=0$
and $[V/m_V:k]=\infty$.

$V$ must have rank 1 since $[V/m_V:k]=\infty$ (for instance by the Abhyankar inequality, \cite{Ab2} or  Proposition 3 \cite{ZS}). By our construction, $\nu(x)\le\nu(f)$ for
any $f\in m_V=\cup_{i=1}^{\infty}m_{R_i}$. Thus the value group of $V$ is
discrete. Since $[V/m_V:k]=\infty$, by  Theorem \ref{TheoremV2} the rank of $V$ does not increase under completion.
\end{proof}



When a valuation ring $V$ with quotient field $K$ is equicharacteristic and  discrete of rank 1, it can be  explicitly
described by a representation in a power series ring in one variable over
the residue field of $V$. In fact, since $V$ is discrete of rank 1, it is
Noetherian (Theorem 16, Section 10, Chapter VI \cite{ZS}). As $V$ is equicharacteristic, the $m_V$-adic completion $\hat V$ of $V$ has a coefficient
field $L$ by Cohen's theorem, and thus $\hat V\cong L[[t]]$ is a power series ring in one variable over $L\cong V/m_V$. We have $V=K\cap \hat V$. The subtlety of this statement is that if $k$ is a subfield of $K$ contained in $V$ such that
$V/m_V$ is not separably generated over $k$, then there may not exist a
coefficient field $L$ of $\hat V$ which contains $k$.

Although the completion of a rank 1 valuation ring is a power series ring,
in positive characteristic,
the  valuation determined by  associating to a system of parameters specific  power series may not be easily recognizable from a series representation of the valuation ring. This can be seen from
 the contrast of the  conclusions of
Theorem \ref{varfin} with the results of this section.  The finiteness condition
$[L:k]<\infty$ of the coefficient field of a series over a base field $k$
does not characterize algebraicity of a series in positive characteristic,
while the corresponding finiteness condition on residue field extensions does
characterize algebraicity in the case of valuations dominating a local ring of Theorem \ref{TheoremV2}. We illustrate this distinction in the following example.

\begin{Example}\label{example2} The valuation induced by the series of
Example \ref{example}, whose coefficient field is infinitely
algebraic over the base field $k$, has a residue field which is
finite over $k$.
\end{Example}

\begin{proof} With notation of Example \ref{example},
we have a $k$-algebra homomorphism
$$
R=k[u,v]_{(u,v)}\stackrel{\pi}{\rightarrow} \overline k[[x]]
$$
defined by the substitutions
$$
u=x, v=\sigma(x)=\sum_{i=1}^{\infty} t_i^{\frac{1}{p}}x^i.
$$
$\pi$ is 1-1 since $x,y$ and the $t_i^{\frac{1}{p}}$ are algebraically independent over $k$. The order valuation  on $\overline k[[x]]$
induces a rank 1 valuation $\nu$ on the quotient field of $R$.
Let $v_1=(\frac{v}{u})^p-t_1$.

$R_1=R[\frac{v}{u}]_{(u,v_1)}$ is dominated by $\nu$.
From the expansion
$$
v_1=\sum_{i=1}^{\infty}t_{i+1}x^{ip},
$$
we inductively define
$$
v_{j+1}=\frac{v_j}{u^p}-t_{j+1}=\sum_{i=1}^{\infty}t_{i+j}x^{ip}
$$
 and
$$
R_{j+1}=R_i[\frac{v_j}{u^p}]_{(u,v_{j+1})}
$$
for $j\ge 1$.
The $R_j$ are dominated by $\nu$ for all $j$, so that $V=\cup_{j\ge 1}R_j$
is the valuation ring of $\nu$.   We have that the residue field of $V$ is $V/m_V=R_1/m_{R_1}=k(t_1^{\frac{1}{p}})$. This is a finite extension of $k$,
in contrast to the fact that the field of coefficients $L=k(\{t_i^{\frac{1}{p}}\mid i\in\NN\})$ of $\sigma(x)$
has infinite degree over $k$.
\end{proof}

An especially strange representation  of a rank 2 discrete valuation is
given by the example (\ref{eqC}) of a power series whose exponents have  unbounded denominators.

 Let $k$ be a field of characteristic $p>0$, and consider the series
\begin{equation}\label{strseries}
\sigma=\sum_{i=1}^{\infty}x^{1-\frac{1}{p^i}}
\end{equation}
of (\ref{eqC}). $\sigma$ is algebraic over $k(x)$, with irreducible relation $\sigma^p-x^{p-1}\sigma-x^{p-1}=0$.

Consider the two dimensional regular local ring
$R_0=k[x,y]_{(x,y)}$. $x$ and $y$ are regular parameters in $R_0$. Let $y=\sigma(x)$. We see from (\ref{strseries}) that $y$ does not have a
fractional power series representation in terms of $x$. However, by expanding $x$ in terms of $y$, we have an expansion
\begin{equation}\label{eqseries}
x=y^{\frac{p}{p-1}}(1+y)^{-\frac{1}{p-1}}
\end{equation}
which represents $x$ as a  fractional power series in $y$ with bounded denominators.





Let $g=y^p-x^{p-1}y-x^{p-1}\in R_0$.  $g=0$
has a singularity of order $p-1$ in $R$. Let
$$
R_1=R[\frac{x}{y},y]_{(\frac{x}{y},y)}.
$$
$x_1=\frac{x}{y}$ and $y$ are regular parameters in $R_1$. $g=y^{p-1}g_1$, where
$$
g_1=y-x_1^{p-1}y-x_1^{p-1}
$$
is a strict transform of $g$ in $R_1$. $g_1=0$ is nonsingular.
From the equation $g_1=0$ we deduce that
$$
\begin{array}{lll}
y&=&x_1^{p-1}(1-x_1^{p-1})^{-1}\\
&=&x_1^{p-1}(1+x_1^{p-1}+x_1^{2(p-1)}+\cdots)\\
&=&\sum_{i=1}^{\infty}x_1^{i(p-1)},
\end{array}
$$
obtaining a standard power series expansion of $y$ in terms of $x$.

We obtain a fractional power series of $x_1$ in terms of $y$ with bounded denominators either from the equation
$g_1=0$, or by substitution in (\ref{eqseries}).





\begin{thebibliography}{}
\bibitem{Ab1} Abhyankar, S., {\em Desingularization of plane curves},
AMS Proceedings of Symp. in Pure Math. 40, Part I (1883), 1-45.
\bibitem{Ab2} Abhyankar, S., {\em On the valuations centered in a local domain}, Amer. J. Math. 78 (1956), 321 - 348.
\bibitem{Ab3} Abhyankar, S., {\em On the ramification of algebraic functions}, Amer. J. math. 77 (1955), 575 - 592.
\bibitem{Ab4} Abhyankar, S., {\em Two notes on formal power series}, Proc. Amer. Math. Soc. 7 (1956), 903-905.
\bibitem{B} N. Bourbaki, Commutative Algebra, Chap. 8.
\bibitem{Be} Benhessi, A., {\em La Cl\^oture alg\'ebrique du corps des s\'eries formelles}, Ann. Math. Blaise Pascal 2 (1995), 1-14.
\bibitem{BK} Brieskorn, E. and Kn\"orrer, H. {\em Plane algebraic curves},
Birkhauser, Basel, 1986.
\bibitem{Ch} Chevalley, C. {\em Introduction to the theory of
algebraic functions of one variable}, AMS, Mathematical Surveys 6, Amer. math. Soc., NY, 1951.
\bibitem{C} Cutkosky, S.D., {\em Resolution of Singularities}, Graduate Studies in Math. 63, AMS, Providence, Rhode Island, 2004.
\bibitem{CG} Cutkosky, S.D. and  Ghezzi, L., {\em Completions of valuation rings},
Cont. math. 386 (2005), 13 - 34.
\bibitem{G-P} Gonz\'alez-P\'erez. P.D., {\em Decomposition in bunches of the critical locus of a quasi-ordinary map}, Compos. math. 141 (2005) 461 -486.
\bibitem{GM} Grothendieck, A. and  Murre, J., {\em The tame fundamental group of a formal neighbourhood of a divisor with normal crossings on a scheme}, Lect. Notes in Math. 208, Springer Verlag, Heidelberg, Berlin, New York, 1971.
\bibitem{Ha} Hahn, H., {\em "Uber die nichtarchimedische Gro\"ossensysteme}, in Gesammelte Abhandlungen I, Springer, Vienna, 1995.
\bibitem{HS} Heinzer, W. and Sally, J., {\em Extensions of valuations to
the completion of a local domain}, Journal of Pure and Applied
Algebra 71 (1991), 175 - 185.
\bibitem{HRS} Heinzer, W., Rotthaus, C. and Wiegand, S., {\em Generic fiber rings of mixed power series/ polynomial rings}, J. Algebra 298 (2006) 248 - 272.
\bibitem{Hu} Huang, M.F., Phd Thesis, Purdue University, 1968.
\bibitem{K} Kaplansky, I., {\em Maximal fields with valuations}, Duke Math. J. 8 (1942), 303 -321.
\bibitem{Ke} Kedlaya, K., {\em The algebraic closure of the power series field
in positive characteristic}, Proc. Amer. Math. Soc. 129, (2001) 3461 - 3470.
\bibitem{L} Lipman, J. {\em Desingularization of 2-dimensional schemes},
Annals of Math. 107 (1978), 115 - 207.
\bibitem{L2} Lipman, J. {\em Quasi-ordinary singularities of surfaces in $\CC^3$}, Singularities Part 2 (Arcata, Calif., 1981), 161-172, Proc. Sympos. Pure Math., 40, Amer. math. Soc., Providence, RI 1983.
\bibitem{N} Nagata, M., {\em Local Rings}, Interscience 1962.
\bibitem{O} Orbanz, U., {\em Embedded resolution of algebraic surfaces
after Abhyankar}, in Cossart V., Giraud J. and Orbanz U., Resolution of surface singularities, Lect. Notes in Math., 1101, Springer Verlag, Heidelberg, Berlin, New York, 1984.
\bibitem{Po} Poonen, B., {\em Maximally complete fields}, Enseign. Math. 39 (1993), 87-106.
\bibitem{Ra} Rayner, F., {\em An algebraically closed field}, Glasgow J. Math
9 (1968), 146-151.
\bibitem{R} Ribenboim, P., {\em Fields: Algebraically closed and others},
Man. math. 175 (1992), 115-150.
\bibitem{RVdD} Ribenboim, P. and Van den Dries, L.,
{\em The absolute Galois group of a rational function field in characteristic zero is a semi-direct product}, Can. Math. Bull. 27 (1984), 313-315.
\bibitem{Ro} Rotthaus, C., {\em Nicht Ausgezeichnete, Universell Japonische Ringe}, Math. Z. 152 (1977) 107 - 125.
\bibitem{St} Stefanescu, D., {\em On meromorphic formal power series}, Bull. Math. Soc. Sci. Math. R.S. Roumanie 27 (1983), 169-178.
\bibitem{S} Spivakovsky, M., {\em Valuations in function fields of surfaces},
Amer. J. Math. 112 (1990), 107 - 156.
\bibitem{Te} B. Teissier, {\em Valuations, deformations, and toric geometry},  Proceedings of the Saskatoon Conference
and Workshop on valuation theory (second volume), F-V. Kuhlmann, S. Kuhlmann, M. Marshall, editors,  Fields Institute
Communications, {\bf 33}, 2003, 361-459.
\bibitem{V} Vaidya, S., {\em Generalized Puiseux expansions and their Galois groups}, Illinois J. Math 41 (1997) 129 - 141.
\bibitem{Z} Zariski, O., {\em The reduction of the singularities of an algebraic surface}, Annals of Math. 40 (1939), 639 - 689.
\bibitem{ZS} Zariski, O. and Samuel, P., {\em Commutative Algebra Volume II}, D. Van Nostrand, Princeton, 1960.
\end{thebibliography}
\par\vskip.5truecm\noindent
Steven Dale Cutkosky,  \hfill Olga Kashcheyeva,\par\noindent Dept.
Math.\hfill Dept. Math.\par\noindent University of Missouri,\hfill
University of Illinois, Chicago\par\noindent Columbia, MO 65211
USA\hfill Chicago, IL 60607 \par\noindent
cutkoskys@missouri.edu\hfill olga@math.uic.edu\par\noindent


\end{document}

The proof is by descending induction on $j$. The first step of the induction concerns the valuation $\nu_n$, which is of rank one and is given by
%-----------
\par\noindent
Define $ t_j=  \nu_j(p_j)\in \Gamma_j$ for each $j$ and remark that it is in the kernel of the map $\Gamma_j\to \Gamma_{j+1}$, which is of rank one. We can therefore think of it as a real number.\par\noindent 
Lemma: For each $j$ we have $p_j^{y_j}\P_{\phi_{j-1}}\subset \P_{\tilde\phi_{j-1}+t_jy_j}$ and the interval $[\tilde\phi_{j-1},\tilde\phi_{j-1}+t_jy_j]$ is finite.\par\noindent

Assume that the result is known for $j$ and prove it for $j-1$. Let us apply the result above to \par
In view of the lemma, we have the inequality
$$\sum_{\phi_j\in [\tilde\phi_{j+1},\tilde\phi_{j+1}+t_jy_j]}e_m(\P_{\phi_j}/\P_{\phi_j}^+)\leq e_m(M_{\phi_{j+1}}/p_j^{y_j}M_{\phi_{j+1}}).$$
Now we apply the formula ([B], \S7, No.1, Prop 3) $$e_m(M_{\phi_{j+1}}/p_j^{y_j}M_{\phi_{j+1}})\asymp \frac{e_{m_j}((M_{\phi_{j+1}})_{p_j})}{(\hbox{\rm dim}R_{p_j}/p_{j-1}R_{p_j})!}y_j^{\hbox{\rm dim}R_{p_j}/p_{j-1}R_{p_j}},$$
so that for each $\phi_{j+1}\in \Gamma_{j+1}$ we have for any $\epsilon>0$ for $y_j$ sufficiently large (in a way which depends on $\epsilon$ and $\phi_j$) an inequality
$$\sum_{\phi_j\in [\tilde\phi_{j+1},\tilde\phi_{j+1}+t_jy_j]}e_m(\P_{\phi_{j+1}}/\P_{\phi_j}^+)\leq (1+\epsilon)\frac{e_{m_j}(M_{\phi_j)}}{(\hbox{\rm dim}R_{p_j}/p_{j-1}R_{p_j})!}y_j^{\hbox{\rm dim}R_{p_j}/p_{j-1}R_{p_j}} .$$

Summing up over the $\phi_{j+1}\in [\tilde\phi_{j+2},\tilde\phi_{j+2}+t_{j+1}y_{j+1}] $, which are finite in number, then over the $\phi_{j+2}\in [\tilde\phi_{j+3},\tilde\phi_{j+3}+t_{j+2}y_{j+2}] $ and so on, we obtain the statement.
  




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
