\documentclass{book}
%\usepackage{color}
\usepackage{amsthm,amsmath,amssymb,amscd}
\usepackage[greek,english]{babel}
\usepackage{graphicx}
\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$}
\def \findem{\smallskip\hfill\vrule width 5 pt height 7 pt depth - 2 pt\smallskip}
\def\Par{{\par\noindent}}
\def\A{{\mathbf A}}
\def\Aa{{\cal A}}
\def\P{{\mathbf P}}
\def\Pp{{\cal P}}
\def\Q{{\mathbf Q}}
\def\Qq{{\cal Q}}
\def\Rr{{\cal R}}
\def\R{{\mathbf R}}
\def\B{{\cal B}}
\def\Ss{{\cal S}}
\def\C{{\mathbf C}}
\def\N{{\mathbf N}}
\def\Z{{\mathbf Z}}
\def\O{{\cal O}}
\def\og{{\omega}}
\def\G{{\Gamma}}
%\def\Pp{{\Par\medskip\noindent}}
\def\limproj{\mathop{\oalign{lim\cr\hidewidth$\longleftarrow$\hidewidth\cr}}}
\def\limind{\mathop{\oalign{lim\cr\hidewidth$\longrightarrow$\hidewidth\cr}}}
\def\elem(#1,#2){  \{ \frac{#1}{\overline{\ #2\ }}\}  } 
\def\dessin#1#2#3{\vbox to #2%
  {\vfill\special{picture #3}\hrule width#1 height 0pt depth 0pt}}
\begin{document}
\pagestyle{myheadings}
\markboth{\rm Bernard Teissier}{ A course on valuations}

  \begin{center}
   {\bf A COURSE ON VALUATIONS} \end{center}  
\Par\medskip
\begin{center} Bernard TEISSIER
\end{center}  
\begin{center}
 (Institut math\'ematique de Jussieu, CNRS)
  \end{center} 
\small
\begin{center}
Summary\end{center}\Par\noindent
This is an introductory course on valuation theory, prepared with the intention to try to present the tradition initiated by Hensel and the geometric tradition initiated by Dedekind and Weber in the same package. \large
\begin{chapter}{A little history} 
\begin{section}{Dedekind-Weber and Hensel-K\"ursch\'ak} Valuation theory has at least two origins. One usually ascribes its origin to reflexions on the work of Hensel by K\"ursch\'ak in 1912. This gave birth to the ``henselian'' tradition in valuation theory, which revolutionized number theory essentially by proving the existence of roots of polynomials in suitable completions of number fields thanks to ``Hensel's lemma'', and also produced an important body of work in model theory, by way of an effort to understand and classify from a logical viewpoint the stucture of henselian valued fields. The beginning of this theory (up to Krull's 1928 paper) is beautifully explained and organized in the paper [] of P. Roquette. \par 
One can also say, but only in hindsight, that an origin of valuations is in the notion of a ''place''
introduced by Dedekind and Weber in 1882 in the study of algebraic
curves. Their purpose was to define algebraically the Riemann surface of a
field of algebraic functions of one variable, e.g the field of rational
functions on an affine plane algebraic curve, which may of course have
singularities. The Riemann surface being by definition compact and non
singular, we find here the source of two basic themes of valuation theory:
compactify and desingularize.\Par
So we seek to associate to the field $K$ a set of points $X$ such that $K$ is
a field of functions on $X$ (possibly not everywhere defined). Over the
complex numbers, the idea is that since, given a point $x$, one may
associate to ''many'' functions in $K$ a value $f(x)\in \C$, and since the
rational functions defined at a point $x$ form a subring $K_x$ of $K$ having
$K$ as field of fractions, we are going to define our set $X$ as a set of
homomorphisms $K_{\cal P}\to \C$, where $K_{\cal P}$ satisfies certain axioms. More
precisely one defines generally a {\it place} of a field
$K$ with values in another field $L$ as a ring homomorphism:\Par
$${\cal P}\colon K_{{\cal P}}\to L$$
where $K_{\Pp}$ is a subring of $K$ such that :\Par
1) If $a\in K\setminus K_{\Pp}$, then $a^{-1}\in K_{\Pp}$ and
$\Pp(a^{-1})=0$.\Par
2) There exists $a\in K_\Pp$ such that $\Pp(a)\neq 0$.\Par
Remark that condition 1) is equivalent to saying that the homomorphism
$\Pp$ cannot be extended to a subring larger than $K_\Pp$. Another way
to define a place (see [B]) is to define for any field
$L$ a new set $\tilde L =L\cup \infty$, and extend to $\tilde L$ the sum
and product in the usual way, with $-\infty =\infty$, $0^{-1}=\infty$, etc...
A place of $K$ with values in
$\Delta$ is then nothing but a homomorphism
$$\tilde \Pp\colon \tilde K\to \tilde \Delta ,$$
and $K_\Pp$ is just the set of elements with finite image. If $K$ and
$\Delta$ are extensions of a ''base field'' $k$, we say that
$\Pp$ is a $k$-place if $\tilde\Pp (c)=c$ for all $c\in k$, and in particular
$k\subset K_\Pp$.\Par
Now we may note that the set $m_\Pp$ of elements of $a\in K_\Pp$ such
that $\Pp(a)=0$ is an ideal with the property that if $b\in
K_\Pp\setminus m_\Pp$, then by axiom 1) we have $b^{-1}\in K_\Pp$. This
shows that $K_\Pp$ is a local ring with maximal ideal $m_\Pp$.
You can also see this by the maximality of $K_\Pp$; if $m_\Pp$
was not maximal, since it is in any case a prime ideal, the
homomorphism $\Pp$ could be extended to the localization
$(K_\Pp)_{m_\Pp}$. Moreover, still by axiom 1), given two elements
$(a,b)\in K_\Pp$, if
$a^{-1}b$ is not in $K_\Pp$, then $b^{-1}a\in K_\Pp$, so that the ideal $(a,b)$
of $K_\Pp$ is always principal, generated by either $a$ or $b$. From this
follows that every ideal $I=(a_1,\ldots ,a_r)K_\Pp$ generated by finitely
many elements is in fact principal and generated by one of these
elements.\Par Let us agree to call any integral domain with this property a
{\it valuation ring}; to each place of a field $K$ we have thus associated a
valuation ring having $K$ as field of fractions.
\Par Conversely, let $V$ be a valuation ring with field of fractions $K$; we
are going to associate to $V$ a place of $K$. For this let us remark that $V$
is necessarily a local ring: it suffices to show that non-invertible elements
form an ideal, and since if $ab$ is invertible, $a$ and $b$ both are, the only
thing to prove is that the set of non-invertible elements is stable by
addition . But if $V$ is a valuation ring, $a+b$ is either $a(1+b')$ or
$(a'+1)b$, and if it is invertible, at least one of $a$ and $b$ must be.
So $V$ is a local ring with maximal ideal $m_V$, and the natural map
$h_V\colon V\to V/m_V$ is a place of $K$ as one immediately
checks.\Par Conversely, given a place of $K$ with values in a field $L$,
there exist a valuation ring $V$ of $K$ and a morphism $j\colon \kappa
(V)=V/m_V\to L$ such that $\Pp=j\circ h_V$. These conditions
uniquely determine $V$ and $j$. The valuation ring
$V$ is the ring $K_\Pp$ of elements of $K$ with finite image, and its
maximal ideal is the set of elements of $a\in K_\Pp$ such that $\Pp (a)=0$.
The homomorphism $j$ is obtained from $\Pp$ by passing to the
quotient by $m_V$.\Par
This result reduces the study of places of $K$ to that of valuation rings $V$
with field of fractions equal to $K$ and morphisms of fields $\kappa (V)\to L$. \Par
Given a valuation ring $V$, we may associate to it a commutative group with
a total order, as follows:\Par
Define an preorder on $V$ by saying that $a\leq b$ means that the ideal
$(a,b)$ may be generated by the element $a$. Since $V$ is a valuation
ring, this is a total preorder. The corresponding equivalence relation is that
$a\cong b$ means that
$(a,b)=aV=bV$. This equivalence relation is clearly compatible with the
product of $V$. The element $0$ of $V$ is clearly greater than any nonzero
element, so if we denote by
$\Phi_+\cup\infty$ the quotient $V/\cong$, we have a natural map
$$\nu\colon V\to (V/\cong )=\Phi_+\cup \infty$$
which is a morphism from the multiplicative semigroup of $V$ to an ordered
semigroup, which we note additively, and $\Phi_+$ is an additive
totally ordered semigroup, satisfying the usual relations with respect to
$\infty$. so we setting $\nu (0)=\infty$, we have:\Par
i) $\nu (ab)=\nu (a)+\nu (b)$\Par
and because  $a+b=a(1+b') \ \hbox {\rm or}\
(a'+1)b$ as we saw above, we have:\Par
ii) $\nu (a+b)\geq \hbox{\rm inf}(\nu (a),\nu (b))$, with equality if the two
valuations are different since then $1+b'$ (resp. $a'+1$) is not in the maximal
ideal, hence is invertible.\Par
This map $\nu$ may be extended to $K$ by setting $\nu (\frac{a}{b})=\nu
(a)-\nu (b)$ if we consider the (totally) ordered abelian group $\Phi$
determined by
$\Phi_+$; it is the smallest group containing $\Phi_+$, its symetrization. It is sometimes written $\Phi=\Phi_+- \Phi_+$ to mark the fact that its elements are differences of elements of $\Phi_+$. Sometimes $\{0\}$ is not considered to be in $\Phi_+$, but here it is. The ordering on $\Phi_+$ gives a total ordering on $\Phi$ and hence a decomposition
$$\Phi=\Phi_-\cup\Phi_+\ \hbox{\rm with}\ \Phi_-=-\Phi_+, \ \Phi_-\cap
\Phi_+=\{0\}$$ and we have a map
$$\nu\colon K^*\to \Phi$$
satisfying i) and ii) above, which satisfies also $\nu (1)=0$ and can be
extended to $K$ by adding to $\Phi$ an element $\infty$ greater than all the
elements of $\Phi$ and setting
$\nu (0)=\infty$, so it is is a valuation according to the usual definition.\Par
Conversely, given a valuation $\nu \colon K^*\to \Phi$ with values in an
ordered group $\Phi$, we may define a subring $$V=\{0\}\cup\{a\in K^*/\nu
(a)\geq 0\}\subset K,$$ and I leave it as an exercise to check that $V$ is a
valuation ring of $K$ with maximal ideal $m_V= \{0\}\cup\{a\in K^*/\nu
(a)>0\}$.\Par
 If we assume that $K$ contains a field $k$, we say that $\nu$ is a
$k$-valuation if $\nu (c)=0$ for all $c\in k^*$. It means
that $k\subset V$ and we have $m_V\cap k=\{0\}$ in $K$, so that
the inclusion $k\subset K$ gives rise to an inclusion $k\subset \kappa
(V)=V/m_V$, and $\kappa (V)$ is an extension of $k$.\Par
So the second avatar of the notion of a place is that of a valuation.\Par Now in
each avatar there is a natural relation between objects: for places it is
specialization, for valuation rings, it is inclusion, and for valuations it is
composition. Before we can see that they are essentially the same, we have to
define precisely these relations.\Par
If we think of $K_\Pp$ as the ring of rational functions which do not have a
pole at a certain point $\Pp$, and $\Pp'$ is a specialization of $\Pp$, by
definition of what specialization means, we must have 
$$K_{\Pp'}\subset K_\Pp\ \hbox{\rm and}\ \ m_{\Pp'}\subset m_\Pp $$
and conversely. \Par
So we say that a place $\Pp'$ is a specialization of another place $\Pp$ if these
inclusions holds. Of course this is also an inclusion of valuation rings as local rings. Now let
us translate this into the language of valuations.\Par
Let $V'\subset V$ be two valuation rings of the field $K$. If $a\cong b$ in
$V'$, we also have $a\cong b$ in $V$, since $a\cong b$ in $V'$ means that
$b=au$ where $u$ is invertible in $V'$, and therefore also in $V$. From this
follows that the inclusion $V'\subset V$ induces an ordered map of
groups $\lambda\colon\Phi'\to \Phi$, which is surjective since an element of
$V$ is of the form $ab^{-1}$ with $a,b\in V'$, and  $\nu (ab^{-1})=\lambda
(\nu' (a)-\nu' (b)) $. The kernel of $\lambda$ consists of the images in
$\Phi'$ of the elements of $V'$ which are not invertible in $V'$ but become
invertible in $V$.\Par
Conversely, suppose that we are given a valuation ring $V'$ of $K$ and a
surjective homomorphism of ordered groups $\lambda \colon\Phi'\to \Phi$,
where $\Phi'$ is $(V\setminus\{0\})/\cong$. Consider the map $\nu'\colon
K^*\to\Phi'$ and set $\nu=\lambda\circ\nu'$. It is immediate to check that
$\nu$ is also a valuation of $K$, and that the valuation ring $V$ of $\nu$
contains $V'$. \Par In this case we says that the valuation $\nu'$ is a
specialization of $\nu$, in accordance with what happens for places. \Par
Now the situation becomes more interesting: since every element of $V'$
invertible in $V'$ is invertible in $V$, we have the inclusion $m_V\cap
V'\subset m_{V'}$, and so an injection
$$V'/m_V\cap V'\subset V/m_V\ =\kappa (V)$$
The first ring is an integral domain, and every ideal of finite type is principal
since it is a quotient of a ring with that property. Note that if 
\small
$$\hbox{\rm{specialization of places}}\leftrightarrow\hbox{\rm{inclusion of
valuation rings}}\leftrightarrow\hbox{\rm{composition of valuations}}.$$\large
From the fact that a valuation ring is associated to a place it is an exercize to check that a valuation ring is a maximal subring of its field of fractions for the relation of \textit{birational domination}: the local ring $(B,n)$ birationally dominates the local ring $(A,m)$ if we have $A\subset B$, they have the same field of fractions and $n\cap A=m$.\par From the definition of a valuation ring one deduces that:
\begin{proposition}a) The set of ideals of a valuation ring is totally ordered by inclusion.\par\noindent
b) This set of ideals is well ordered.\end{proposition}
To prove a), let $I$ and $J$ be two ideals of the valuation ring $V$, and assume that $I\not\subset J$. Let $x\in I\setminus J$. For any $y\in J$, we have that $Vx\not\subseteq Vy$, which means $Vy\subseteq Vx$ since $V$ is a valuation ring. This shows that $J$ is contained in $I$, and the result. Assertion b) follows from the fact that an intersection of ideals is an ideal.\par
\begin{definition} The \textit{rank}, also called the \textit{height} of a valuation is the ordinal type of the sequence of prime ideals of its valuation ring $V$. When it is finite, it is the Krull dimension of the local ring $V$.\par
Let $V$ be a valuation ring with field of fractions $K$. If a valuation ring $V'$ contains $V$, it is a localization of $V$ at one of its prime ideals.
\end{definition}
The Henselian tradition:
\end{section}
\end{chapter}
\begin{chapter}{The Riemann-Zariski manifold of a field}\label{R-Z}
\begin{section}{The definition}
Zariski generalized to arbitrary dimensions the Dedekind-Weber construction of the Riemann surface of a field of algebraic functions of one variable. The result, however is very far from being an algebraic variety  when the dimension is $>1$. \end{section}\Par


\begin{section}{Valuations and series}
An ordered set is artinian in the sense of \cite{R} if it contains
no infinite strictly decreasing sequences and it is narrow if it
does not contain infinite sets of incomparable elements. According
to {\it loc.cit.}, we can define the $k$-algebra of formal power
series $k[[X^{\mathbb{Q}^d_{\geq 0}}]]$ where
$X=(X_1,\ldots,X_d)$, as follows:\par  It is the set of maps
$c\colon \mathbb{Q}^d_{\geq 0}\to k$ which are such that
$c^{-1}(k^*)$ is artinian and narrow, equipped with the addition
coming from the addition of $k$ and the convolution product
$c*c'(\lambda)=\Sigma_{\mu +\sigma=\lambda}c(\mu)c'(\sigma)$. The
elements of $k[[X^{\mathbb{Q}^d_{\geq 0}}]]$ can be thought of as
formal sums $\Sigma c_\lambda X^\lambda$ with
$c_\lambda=c(\lambda)$ or, writing in a less condensed form as the
algebra  of formal sums $\Sigma
c_{\lambda^1,\ldots,\lambda^d}X_1^{\lambda^1}\ldots
X_d^{\lambda^d}$ where $\lambda=(\lambda^1,\ldots ,\lambda^d)$
with artinian and narrow sets of exponents in $\mathbb{Q}^d_{\leq
0}$. The properties just quoted imply that this product is well
defined.\par  One can also define the algebra of formal power
series with sets of exponents which are well ordered in
$\mathbb{Q}^d_{\succcurlyeq 0}$ with respect to the total order
$\preccurlyeq$. We will denote it by $k[[X^{\mathbb{Q}^d_{
 \succcurlyeq 0}} ]]$. \par A remark which
 will be useful in the sequel is that for any compatible total ordering $\preccurlyeq$ on $\mathbb{Q}^d$ we have, setting
  $X^{\frac{1}{m}}=(X_1^{\frac{1}{m }},\ldots,X_d^{\frac{1}{m }})$, the strict inclusions:

$$k[[X]]\subset \widetilde{k[[X]]}:=\bigcup_{N\geq 1} k[[X^{\frac{1}{N}}]]\subset k[[X^{\mathbb{Q}^d_{
 \geq 0}} ]]\subset k[[X^{\mathbb{Q}^d_{
 \succcurlyeq 0}} ]].$$
Since $\preccurlyeq$ is a total order and we we consider series with well ordered exponent sets, the smallest exponent of a series in $k[[X^{\mathbb{Q}^d_{
 \succcurlyeq 0}} ]]$ is well defined. Since $k$ is an integral domain this defines a valuation on the field of fractions of $k[[X^{\mathbb{Q}^d_{
 \succcurlyeq 0}} ]]$, with values in $(\mathbb{Q}^d, \preccurlyeq)$.
 \par\medskip
 This construction, which goes back to Krull, makes sense for any totally ordered abelian group. This means that for any totally ordered abelian group $\Phi$ and any field $k$ we can define the $k$-algebra $k[[t^{\Phi_+}]]$, which is endowed with a natural $k$-valuation with values in $\Phi$. \par\medskip\noindent
 The next result tells us that the field of fractions of $k[[t^{\Phi_+}]]$ is the set of power series with a well ordered set of exponents in $\Phi$. \par
 The result goes back to Hahn ([]) , and we give here a proof due to B.H. Neumann ([]). He actually proves the generalization to non commutative groups. There are also a generalizations to partially ordered groups (see [],[]).  \par
 \begin{theorem} The ring $k[[t^{\Phi}]]$ of series with coefficients in $k$ and exponents forming a well-ordered set in $\Phi$ is a field.
 \end{theorem}
 \begin{proposition}Let $E\subset \Phi_+$ be a well ordered subset of the positive part of a totally ordered group $\Phi$. Then the semigroup $\langle E\rangle$ generated by $E$ is well ordered.
 \end{proposition}
 \begin{proof} Assume the contrary; there exists an infinite strictly decreasing sequence $f_1>f_2>\cdots $ of elements of $\langle E\rangle$. Let us write them:
 $$
 \begin{array}{lr}
 f_1&=e_{11}+e_{12}+\ldots +e_{1,\lambda(1)}\\
 f_2&=e_{21}+e_{22}+\ldots +e_{2,\lambda(2)}\\
 \vdots&=\ \ \ \ \ \vdots\\
 f_\mu&=e_{\mu1}+e_{\mu2}+\ldots +e_{\mu,\lambda(2)}\\
 \vdots&=\  \vdots\\
 \end{array}$$
 For each $\mu$ denote by $E_\mu$ the largest of the elements appearing in that line. If we denote by $\Psi(\phi)$ the smallest convex subgroup of $\Phi$ such that $\phi\in \Psi (\phi)$, we have $\Psi(E_\mu)=\Psi(f_\mu)$. The sequence of the $\Psi(u_\mu)$ is decreasing and since the sequence of convex subgroups is well ordered, there is a least element. Different sequences can give us different least elements, but among those, there is a smallest. \par
 So we may assume that our sequence $(u_\mu)$ is such that the smallest convex subgroup to which its elements ultimately belong is as small as possible. \par
 Forgetting finitely elements of the sequence we may assume that all $u_\mu$ are in a certain convex subgroup $\Psi$, and not in a smaller one. Let us denote by $\Psi_+$ the largest convex subgroup of $\Phi$ strictly contained in $\Psi$. The set $\Psi\setminus \Psi_+$ contains elements of $E$, for example the $E_\mu$; we can denote by $\psi (E)$ the smallest element of $E$ which is in $\Psi\setminus \Psi_+$ and we have in the quotient $\Psi/\Psi_+$, denoting the images in the usual way:
 $$\overline {u_1}\geq \overline E_1\geq \overline\psi (E)>0.$$
 But $\Psi/\Psi_+$ is archimedian so that for some integer $q$ we have $q\overline\psi (E)\geq \overline {u_1}$ Note that $q\geq 2$ since $\overline {u_1}\geq \overline\psi (E)$. We have then $\overline {u_\mu}<\overline {u_1}\leq q\overline\psi (E)$ and if we have chosen $q$ as small as possible we may assume $\overline {u_\mu}>(q-1)\overline {\psi (E)}$. Let us assume that we have chosen the sequence $(u_\mu)$ so that $q$ is as small as possible.\par
 Now $\overline {u_\mu}$ has to be of the form $\overline {u_\mu}=\overline {u'_\mu}+\overline {E_\mu}$. Only finitely many of the $\overline {u'_\mu}$ can be non zero since otherwise the $E_\mu$, which are elements of $S$, would form an infinite decreasing sequence. Then among the $u'_\mu$ there must be an infinite decreasing sequence. But since by definition $E_\mu\geq \psi (E)$ we must have $\overline {u'_\mu}<(q-1)\overline\psi (E)$, and so we have found an infinite decreasing sequence for which either $\Psi$ is smaller or $q$ is smaller, contrary to our choices. This provides the desired contradiction.\end{proof}
 \begin{corollary} An element of $\langle E\rangle$ lies in only finitely many of the sets $E, E+E, E+E+E,\ldots$.
  \end{corollary}
  \begin{proof} Let $M$ be the set of elements of $\langle E\rangle$ which can be represented by arbitrarily long sums of elements of $E$. We want to prove that the set $M$ is empty. Assume that it is not. Then, since $\langle E\rangle$ is well ordered, it has a smallest element, say $f$. By construction, $f$ can be written 
  $$\begin{array}{lr}f=e_{1,1}+\cdots +e_{1, \lambda(1)}=e_{2,1}+\cdots +e_{1, \lambda(2)}\\
  =\cdots =e_{i,1}+\cdots +e_{i, \lambda(i)}=\cdots\end{array}$$
  with $\lambda(1)<\lambda(2)<\cdots $ and all $e_{i,j}$ non zero.\par
  Set $g_i=f-e_{i,1}$. Since $E$ is well ordered, the sequence $(e_{i,1})_{i\geq 1}$ contains a nondecreasing subsequence, and so the sequence $(g_i)_{i\geq 1}$ contains a non increasing subsequence of elements of $\langle E\rangle$. Since $\langle E\rangle$ is well ordered, this subsequence is eventually constant, say equal to $g\in \langle E\rangle$. By construction we have $g\in S$ and $g<f$. This provides the desired contradiction.
  \end{proof}
 \end{section} 
\begin{section}{The transcendental hypersurface and its approximations}\label{section:trans}{
Generalizing the classical definition of the quasi-ordinary hypersurface singularities (see  the paragraph before definition
 \ref{definition:quasipoly} below and \cite{LP1}, \cite{LPthes} )
we define a
transcendental quasi-ordinary hypersurface singularity in the following manner:

\begin{definition}\label{definition:element}
{\rm An element $\mathbf{\zeta}(X)=\sum c_{\lambda}X^{\lambda}\in k[[X^{\mathbb{Q}^d_{
 \geq 0}} ]]$ is called a generalized quasi-ordinary series if there exists a totally ordered sequence $0=\lambda_0< \lambda_1<
 \ldots <\lambda_i<\lambda_{i+1}<\ldots$ of elements of $(\mathbb{Q}^d,\leq)$ with respect to which $\mathbf{\zeta}(X)$  satisfies the following conditions:
 \begin{itemize}
 \item{ $c_{\lambda_i}\neq 0$ for all $i\in \mathbb{N}$.}
 \item {Setting $Q_0=\mathbb{Z}^d$ and $Q_i=\mathbb{Z}^d+\Sigma_{k=1}^i\mathbb{Z}\lambda_k\subset \mathbb{Q}^d$, we have
 that  if $c_\lambda\neq 0$, then $\lambda\in \bigcup_{j=0}^\infty Q_j$.}
 \item{For each $\lambda$ such that $c_\lambda\neq 0$ we have the equality
 $$\hbox{\rm min}\{i/\lambda\in Q_i\}=\hbox{\rm max}\{j/\lambda_j\leq \lambda\}.$$
 We will denote this number by $\kappa(\lambda)$.}
 \item{For all $j\geq 0$ we have $\kappa (\lambda_j)=j$.}
 \end{itemize}
 Note that if these conditions are satisfied, $\kappa(\lambda)=i$ implies that $\lambda_i\leq \lambda$ so that one can write:
$\mathbf{\zeta}(X)=\sum_{i=0}^{\infty}p_{i}, \
p_{i} \in k[[X^{\mathbb{Q}^d_{
 \geq 0}} ]]$
where  $p_i=\Sigma_{\kappa(\lambda) =i}c_\lambda X^\lambda.$

Given a generalized quasi-ordinary series $\mathbf{\zeta}(X)$, one checks by induction that a minimal system of $\lambda_i$ satisfying
 the conditions above is unique and the $\lambda_i$ are then called distinguished exponents of the series. This terminology is
justified in Definition \ref{definition:quasipoly}, in which we
define for any $i \in \mathbb{N},$  irreducible quasi-ordinary
hypersurfaces (see   \cite{GP1} or \cite{LP1} ) which are
parametrized by $X=X, Y=\zeta^{(i)}(X)$ where $\zeta^{(i)}(X)$ is
a fractional power series with distinguished exponents
$\lambda_1, \ldots,\lambda_i.$ 
\end{definition}
\begin{definition} \label{definition:nn}
{\rm  Given a generalized quasi-ordinary series as above, we define inductively the integers $n_j=[Q_j:Q_{j-1}]$ and
 $m^{(0)}=1, \ m^{(i)}=n_1 \cdots n_i .$ Note that by construction we have $n_j>1$ for all $j$, so that the $m^{(i)}$ are
integers
which tend to infinity with $i$. \par}
 \end{definition}
 One then checks by induction that in the decomposition $\mathbf{\zeta}(X)=\Sigma_{i=0}^\infty p_i$, we have
 $p_i\in k[[X^{\frac{1}{m^{(i)}}}]]$. This is due to the fact that a series in $X$ or $X^{\frac{1}{N}}$ whose set of exponents is
  artinian and narrow is a formal power series in the usual sense (see \cite{R}, Example 3).\par

The definitions just given are a generalization of  \cite{Te1},
subsection 4.4,  where a ''natural valuation'' is attached to a
''transcendental plane curve'',    studied through a series of
examples from different perspectives:  the sequence of point blow
ups, the semigroup, the  graded valuation ring, $\ldots.$
Moreover, the relations between these approaches are studied.
 In this text we follow  the same approach.

\begin{proposition} \label{proposition:hard} If the sequence of distinguished exponents of a generalized quasi-ordinary series
$\mathbf{\zeta}(X)$ is infinite, the element $\mathbf{\zeta}(X)$
is  transcendental over the subring $k[X]\subset
k[[X^{\mathbb{Q}^d_{\geq 0}} ]].$
 In other
words, the morphism of $k-$algebras
\begin{center}
\begin{tabular}{rrll}
$\Theta_{\zeta}\colon$ &$k[X,Y]$&$\to $&$ k[[X^{\mathbb{Q}^d_{
 \geq 0}} ]]$\\
&$X$&$\mapsto$& $X$\\
&$Y$&$\mapsto$& $\zeta(X)$
\end{tabular}
\end{center}
is injective.
\end{proposition}

\noindent
{\bf Proof. }Assume the contrary and  let $\zeta(X)$ be the root of an
irreducible polynomial $f\in k[X,Y].$ Consider the algebraically
closed
 field $k((X^{\mathbb{Q}^d_{ \succcurlyeq 0}})),$ (see \cite{Bour56}, Chap. 6, Section 3, $n^{\circ}$ 4, Exemple 6).
 We have
 $\zeta(X)\in k((X^{\mathbb{Q}^d_{\succcurlyeq 0}})).$ In the sequence $\lambda_r$ of the distinguished exponents the
 denominators tend to infinity. Therefore, there is an index $i$ such that the denominators of   $\lambda_{r,i}$ tend to
 infinity with $r.$ We can assume
  that this index is $d.$ Consider the algebraically closed field $k'=k((X^{'\mathbb{Q}^{d-1}_{ \succcurlyeq 0}})),$
  where
  $X^{'}=(X_1,\ldots,X_{d-1}).$ We can regard $f(X,Y)$ as a polynomial in the ring $k'[X_d,Y]$ and $\zeta(X)$ as an element
of the ring $k'[[X_d^{\mathbb{Q}_{ \succcurlyeq 0}}]].$ By the
Newton-Puiseux theorem (here we use the fact that $k$ is of characteristic zero) all the roots of $f(X,Y)$ are in the ring
 $\widetilde{k'[[X_d]]}.$ It implies that $\zeta(X)\in \widetilde{k'[[X_d]]}$ which is absurd. $\hfill\square$\\

A variant of this  proof   gives us the following statement: Given
any $f\in k[X,Y],$ there does not exist  a root $\eta(X)\in
k[[X^{\mathbb{Q}^d_{ \succcurlyeq 0}}]]$ of $f,$ such that  the
denominators of the  terms of $\eta$ tend to infinity (By
denominator of a term
$c_{ \beta}X^{\beta}$ of $\eta$ we mean:  the least natural number $n$ such that $n.\beta\in\mathbb{N}^{d}$). \\

We introduce  a sequence of  quasi-ordinary hypersurfaces
$f^{(i)},$ which   approximates the original element $
\mathbf{\zeta}(X).$

Recall, see (\cite{LP2}), that a polynomial $P(X,Y)\in k[[X]]Y]]$
is said to define a (formal germ of) quasi-ordinary hypersurface
if its discriminant with respect to $Y$ is of the form $X^\delta
\hbox{\rm u}(X)$ where $\delta\in \mathbb{N}$ and $\hbox{\rm u}(X)$ is a unit in $k[[X]]$.
When $k$ is algebraically closed of characteristic zero this is
known (Abhyankar-Jung Theorem) to imply that the roots of the
polynomial can be expressed as power series in $X^{\frac{1}{m}}$
for some $m$, and these series are quasi-ordinary in the sense of
Definition \ref{definition:element}, with a finite set of
distinguished exponents.

\begin{definition} \label{definition:approxroot}
Let $\zeta(X)$ be a generalized quasi-ordinary series with distinguished exponents $\lambda_1,\ldots \lambda_i,\ldots$. For each integer $i$ we define, using the notations introduced in definition \ref{definition:element}, the $i$-th approximation 
$$\zeta^{(i)}(X)=\sum^{i}_{j=1}p_j.$$
It is a quasi-ordinary series in the sense we have just recalled. As we saw, it is an element of $k[[X^{\frac{1}{m^{(i)}}}]]$. Note that $\zeta(X)-\zeta^{(i)}(X)$ is of the form $X^{\lambda_{i+1}}\times \hbox{\rm unit}$ and also that for $0\leq j< i,$ the difference $\zeta^{(i)}(X)-\zeta^{(j)}(X)$ is of the form $X^{\lambda_{j+1}}\times \hbox{\rm unit}$ .
\end{definition}
Since $\zeta^{(i)}(X)\in k[[X^{\frac{1}{m^{(i)}}}]]$ is algebraic over $k((X))$ we can now introduce the irreducible polynomials having $\zeta^{(i)}(X)$ as a root:
\begin{definition}\label{definition:quasipoly}

 {\rm Set $f^{(0)}(X, Y)=Y,$  and  for any $i\in \mathbb{N}$ define an irreducible quasi-ordinary polynomial
  $f^{(i)}(X, Y)\in
 k[[X]][Y]$ as the unitary minimal polynomial of $\zeta^{(i)}(X)$ over $k((X))$. It is shown in \cite{GP1} that it a polynomial of degree $m^{(i)}$ in $Y$ dividing the polynomial
 $$\Pi_{\omega\in (\mathbb{\mu}_{m^{(i)}})^d}(Y-\zeta^{(i)}(\omega X).$$
 Here $\mathbb{\mu}_{m^{(i)}}$ is the group of roots of unity and $\omega X=(\omega_1 X_1,\ldots ,\omega_d X_d)$.
}
\end{definition}

%In the Remark \ref{remark:haalgiri}, following the ideas of  \cite{Te2}, we  give a way to compute the equations  of  these quasi-ordinary hypersurfaces.



\begin{definition} \label{definition:deg}
{\rm Using the notations of Definition \ref{definition:nn}, it can
be proved that $m^{(i)}=\mathrm{deg}_Y(f^{(i)}) $  (see \cite{GP1}
or \cite{LP1}). Moreover, we define the following vectors
(originally defined and studied in \cite{GP2}):
$$ \gamma_{1}=\lambda_{1},\  \gamma_{j}=n_{j-1}\gamma_{j-1}+\lambda_{j}-\lambda_{j-1}, \ j>1.$$
}\end{definition}
\begin{remark}\label{sbgrps} The subgroups of $\mathbb{Q}^d$ generated by $(\gamma_1\ldots ,\gamma_j)$ and $(\lambda_1,\ldots ,\lambda_j)$ are equal.\end{remark}

By $R(f),$ for a quasi-ordinary $f,$ we mean the set of the  roots of  $f$ in $\widetilde{k[[X]]}.$ Following
 \cite{PP}, we define the
notion of the intersection index of two ''comparable'' quasi-ordinary  hypersurfaces.

In the case where the process terminates after finitely many steps, we make use of the following lemma, which shows that any finite truncation of a quasi-ordinary series, corresponding to a finite initial set of generators $(\gamma_1,\ldots ,\gamma_i)$ of the associated semigroup, can be viewed as a truncation of a transcendental quasi-ordinary series whose associated semigroup is generated by $(\gamma_1,\ldots ,\gamma_i)$.
\begin{lemma}\footnote{This lemma and its proof were given by Bernard
Teissier}\label{transcendence} Let $\gamma_1,\ldots ,\gamma_i$ be
an increasing sequence of elements of $\mathbb{Q}^d_{\geq
0}$ satisfying the conditions of Lemma \ref{lemma:yek} and
generating a subgroup $G_i\subset \mathbb{Q}^d$. Let
$\lambda_1,\ldots, \lambda_i$ be the increasing sequence of
elements of $\mathbb{Q}^d_{\geq 0}$ corresponding as in
definition \ref{definition:deg} to the $\gamma_j.$ Given a finite
sum
$$\zeta_F (X)=\Sigma_{\lambda\in F}c_\lambda X^{\lambda}$$ having
$\lambda_1,\ldots, \lambda_i$ as distinguished exponents in the
sense of Definition \ref{definition:element}, there exists a
series of the form
$$\zeta(X)=\zeta_F(X)+ \sum c_{\tilde\lambda} X^{\tilde\lambda}$$
which is transcendental over $k(X)$ and such that $\zeta_F(X)$ is
a finite truncation of $\zeta(X)$ and the group of the valuation associated to
$\zeta(X)$ by a choice of a compatible order on $\mathbb{Q}^d$ is $G_i$.\end{lemma}

\noindent {\bf Proof. } Without loss of generality we may assume
that $G_i$ is not contained in any coordinate hyperplane of
$\mathbb{Q}^d.$ Let us take an infinite increasing sequence of
exponents $(\tilde\lambda_j)_{j\geq 1}$ tending to $\infty$ in
$(\mathbb{Q}^d,\leq),$ with $\tilde\lambda_1$ larger than
all the exponents of $\zeta_F,$ and with $\tilde\lambda_1$ and
$\tilde\lambda_j-\tilde \lambda_{j-1}$ in the semigroup generated
by the $(\gamma_k)_{k\leq i}$ for all $j>1.$ In addition we ask
the following ''large gaps'' condition:\par\noindent 1)
$\tilde\lambda_{j+1}>(j+1)\tilde\lambda_j$ for all
$j$\par\noindent and remark that  because we assume that the
$(\tilde\lambda_j)$ increase and tend to $\infty$ in
$(\mathbb{Q}^d,\leq)$ we have:\par\noindent 2) for any
positive integer $s$ we have $\tilde\lambda_\ell>s{\bf 1}$ for
sufficiently large $\ell,$ where ${\bf 1}=(1,\ldots ,1)\in
\mathbb{Q}^d_{\succcurlyeq 0}.$ \par\noindent Now the claim is
that for arbitrary nonzero coefficients $c_{\tilde\lambda_j}$ the
series
$$\zeta(X)= \zeta_F(X)+\Sigma_{j=i+1}^\infty
c_{\tilde\lambda_j}X^{\tilde\lambda_j}\in
k[[X^{\mathbb{Q}^d_{\geq 0}}]]$$ satisfies the conditions of the Lemma.
 \par\noindent By construction, $\zeta_F(X)$ is a finite truncation of $\zeta(X)$.  To check the transcendance, let $Q(X,Y)$ be a polynomial of degree $\leq s$ in
$Y$ and of total degree $\leq s$ in the $X_k;$ by our assumptions
we can choose an $\ell$ such that $\ell>s$ and $\tilde\lambda_\ell>s{\bf
1}.$ Set $u=\zeta_F(X)+\Sigma_{j=1}^\ell
c_{\tilde\lambda_j}X^{\tilde\lambda_j}$ and
$v=\Sigma_{j=\ell+1}^\infty
c_{\tilde\lambda_j}X^{\tilde\lambda_j};$ we have $\zeta(X)=u+v$ in
$k[[X^{\mathbb{Q}_{\succcurlyeq 0}^d}]]$ and the equality:

$$Q(X,u+v)=Q(X,u)+vA_1(X)+v^2A_2(X)+\cdots $$ with $A_k(X)\in
k[[X^{\mathbb{Q}_{\geq 0}^d}]]$ and therefore by our
choice of $\tilde\lambda_j,$ denoting by $\nu$ the $X$-adic order,
we have:
$$\nu (vA_1(X)+v^2A_2(X)+\cdots )\geq\nu (v)= \tilde\lambda_{\ell
+1}>(\ell +1)\tilde\lambda_\ell.$$ On the other hand, since we
consider finite sums, we can speak of the degree in $X$ of a
polynomial such as $Q(X,u)=Q_0(X)+Q_1(X)u+Q_2(X)u^2+\cdots
+Q_m(X)u^m,$ with $m\leq s$ and $Q_m(X)\neq 0;$ this degree is an
element of $\mathbb{Q}^d_{\geq 0}.$ \par\noindent Since if
$\Sigma _1^da_i\leq s$ we have the inequality $(a_1,\ldots
,a_d)\leq s{\bf 1}<\tilde\lambda_\ell,$ for $i<m,$ the degree of
$Q_i(X)u^i$ is $\leq s{\bf 1}+i\tilde\lambda_\ell <
(i+1)\tilde\lambda_\ell \leq m\tilde\lambda_\ell.$ On the other
hand, the degree of the last term $Q_m(X)u^m$ is $\geq
m\tilde\lambda_\ell.$

This shows that $Q(X,u)$ is not zero and since its $X$-adic order
cannot exceed the highest power of $X$ which appears, applying to
$Q_m(X)u^m$ the same argument as for $i<m,$ we see that it is
$<(m+1)\tilde\lambda_\ell.$

So $Q(X,u+v)=Q(X,\zeta(X))$ is the sum of a polynomial with
fractional exponents of $X$-adic order
$< (m+1)\tilde\lambda_\ell\leq (s+1)\tilde\lambda_\ell$ and a
series of $X$-adic order  $>(\ell
+1)\tilde\lambda_\ell>(s+1)\tilde\lambda_\ell$. It follows that
$Q(X,\zeta(X))$ is of $X$-adic order $< (s+1)\tilde\lambda_\ell$
whenever $\ell$ satisfies the conditions stated above with respect
to the degree of the polynomial $Q(X,Y) $. This proves that the
series $\zeta(X)$ is not algebraic over $k(X)$. Moreover by construction $\zeta(X)$ is a quasi-ordinary series with distinguished exponents $\lambda_1,\ldots ,\lambda_i$ so that one checks using proposition %\ref{proposition:gval}
?? that the value group is $G_i.$\par \hfill $\square$
\end{section}
\begin{section}{Key polynomials and the valuative tree of Favre-Jonsson}
\end{section}
\begin{section}{Key polynomials and the work of Vaqui\'e}
\end{section}
\begin{section}{Key polynomials and toric geometry}
We need to approximate graded algebras of the form $\hbox{\rm gr}_\nu R_\nu$ by polynomial rings. The key ingredient is the Jacobi-Parron algorithm.\par
Let $(\tau_1.\ldots ,\tau_m)$ be $m$ rationally independent positive real numbers. The algorithm consists in
writing $$\tau_1=\tau_m^{(1)} ,\tau_2=\tau_1^{(1)}+a_2^{(0)}\tau_m^{(1)},\ldots
,\tau_m=\tau_{m-1}^{(1)}+a_m^{(0)}\tau_m^{(1)},$$ where $$a_j^{(0)}=[\tau_j/\tau_1],\ \ \
j=2,\ldots ,m,$$ and repeating this operation after replacing $(\tau_1,\ldots ,\tau_m)$ by
$(\tau_1^{(1)},\ldots ,\tau_m^{(1)})$, and so on. \par
One checks that the $(\tau_1^{(j)},\ldots ,\tau_m^{(j)})$ are also rationally independant and positive. Moreover, since $$\frac{\tau^{(1)}_i}{\tau^{(1)}_m}=\frac{\tau_{i+1}}{\tau_1}-[\tau_{i+1}/\tau_1],$$
we see that $\tau^{(1)}_i<\tau^{(1)}_m$.
After $h$ steps, one has written

$$\tau_i=A_i^{(h)}\tau_1^{(h)}+\cdots +A_i^{(h+m-1)}\tau_m^{(h)}$$ or,  if we denote by $w$ the
(weight) vector $(\tau_1,\ldots ,\tau_m)\in {\mathbf R}^m$ and by $A^{(h)}$ the vector 
$(A_1^{(h)},\ldots ,A_m^{(h)})$, $$w=\tau_1^{(h)}A^{(h)}+\tau_2^{(h)}A^{(h+1)}+\cdots
+\tau_m^{(h)}A^{(h+m-1)}$$ where the $\tau^{(h)}_j$ are positive, the coefficients $A^{(j)}_i$ are
non negative integers, and the matrix of the vectors $$A^{(h)},A^{(h+1)},\ldots ,A^{(h+m-1)}$$
has determinant $(-1)^{h(m-1)}$. Moreover, as $h$ grows the directions in ${\mathbf P}^{m-1}({\mathbf R})$ of the
vectors $A^{(h)}$ tend to the direction of $w$.\par\noindent

The details of the proof can be found in [H-P], Vol. III.\par


 So we have a sequence of vectors $A^{(h)}$ with
positive integral coordinates whose directions in ${\mathbf
P}^{m-1}({\mathbf R})$ spiral to the direction of $w$ and such that any consecutive $m$ of them as
above form a basis of the integral lattice such that $w$ is contained in the convex cone
$\sigma^{(h)}=\langle A^{(h)},A^{(h+1)},\ldots ,A^{(h+m-1)}\rangle$ which they generate. The
convex dual $\check\sigma^{(h)}$ of $\sigma^{(h)}$ (see [Cox], \S 2, [E], V, 2, p. 149) is contained
in the half space $\sum_{i=1}^ma_i\tau_i\geq 0$, the integral points of which form the
semigroup $\Phi_+$. The algebra of the semigroup $\check \sigma^{(h)}\cap \Z^m$ is a
polynomial algebra $k[x_1^{(h)}, \ldots,x_m^{(h)}]$ ({\it loc.cit.}, VI,2) contained in
$k[t^{\Phi_+}]$, and since by assumption there are no integral points on the hyperplane 
$\sum_{i=1}^ma_i\tau_i= 0$ except the origin, the semigroup $\Phi_+$ is the union of the
$\check \sigma^{(h)}\cap \Z^m$ as $h\rightarrow \infty$. This proves that $k[t^{\Phi_+}]$ is the
union, or direct limit, of these polynomial subalgebras.\par Note that by construction we have
for each $h\geq 1$ the equality  $$A^{(h)}-A^{(h+m)}+a_2^{(h)}A^{(h+1)}+\cdots
+a_m^{(h)}A^{(h+m-1)}=0,$$ which shows, since the $a_j^{(h)}=[\tau_j^{(h)}/\tau_1^{(h)}]$ are
non-negative, that we have $$A^{(h+m)}\in\sigma^{(h)}=\ \langle A^{(h)},\ldots
,A^{(h+m-1)}\rangle$$ and therefore $\sigma^{(h+1)}\subset\sigma^{(h)}$, that is $\check
\sigma^{(h)}\subset \check\sigma^{(h+1)}$ and $$ k[x_1^{(h)}, \ldots,x_m^{(h)}]\subset
k[x_1^{(h+1)}, \ldots,x_m^{(h+1)}],$$ so that our direct system is in fact a nested sequence of
polynomial subalgebras. The morphisms between these polynomial algebras correspond by duality to the expressions 
of the $A^{(h+m)}$ as linear combinations with non negative integral coefficients of $(A^{(h)},\ldots
,A^{(h+m-1)})$ and are therefore monomial as announced.\par If we now consider
a group  with one more generator
$\tau_{m+1}>0$ which is rationally dependent on $\tau_1,\ldots ,\tau_m$, Zariski shows in ([Z1], B. I, p. 862) that the new weight vector 
$w=(\tau_1,\ldots ,\tau_m ,\tau_{m+1})\in {\mathbf R}^{m+1}$ is contained in a rational simplicial  cone $\sigma \subset {\mathbf R}^{m+1}$
generated by $m$ integral vectors $v_1,\ldots ,v_m$ of the first quadrant  forming part of a basis of the integral lattice.
Indeed $w$ is contained in a unique rational hyperplane. The dual cone $\check
\sigma\subset\check {\mathbf R}^{m+1}$  is the product of an $m$ dimensional strictly convex cone generated by vectors $e_1,\ldots, e_m$ by a
1-dimensional vector space (see [E], V, 2), generated by a primitive integral vector $e_{m+1}$, which is the dual of the rational hyperplane containing $w$.
The vectors $e_1,\ldots, e_{m+1}$ are a basis of the integral lattice, and correspond to the variables $x_1,\ldots ,x_{m+1}$ generating a polynomial ring. Note
that the map
$f:
\Z^{m+1}\rightarrow {\mathbf R}$ defined by $(a_1,\ldots ,a_{m+1})\mapsto \sum_{i=1}^{m+1}a_i\tau_i$ is no longer injective; 
the primitive vector $e_{m+1}$ corresponding to the variable $x_{m+1}$ is in the kernel. Let us set
$\widetilde{\Phi_+}=f^{-1}(\Phi_+\cup\{ 0\})$. By refining as above by the Perron algorithm for
$w$ inside the linear span $<\sigma >$ of $\sigma$, starting with the coordinates of
$w$ in $\sigma$,
 we find a sequence of regular simplicial cones $\sigma^{(h)}\subset \sigma $ whose duals
$\check
\sigma^{(h)}\subset \widetilde{\Phi_+}$ correspond ([E], VI, Th. 2.12) to algebras of the
form $k[x_1^{(h)}, \ldots ,x_m^{(h)}, x_{m+1}^{\pm 1}]\subset k[t^{\widetilde{\Phi_+}}]$.  
The free semigroups $\check \sigma^{(h)}\cap \Z^{m+1}$ fill up $\widetilde{\Phi_+}$ as
$h\rightarrow \infty$ since the only  rational points of the hyperplane
$\sum_{i=1}^{m+1}a_i\tau_i=0$ are on the dual of the hyperplane containing $w$, which is
contained in all the $\check\sigma^{(h)}$. So the direct limit of the images of the maps
$k[t^f]\colon k[x_1^{(h)},
\ldots ,x_m^{(h)}, x_{m+1}^{\pm 1}]\rightarrow k[t^{\Phi_+}]$ is $k[t^{\Phi_+}]$. But these images
are isomorphic to $ k[x_1^{(h)},
\ldots ,x_m^{(h)}, x_{m+1}^{\pm 1}]/(x_{m+1}-1)$ so that they are again polynomial rings
 $k[x_1^{(h)}, \ldots,x_m^{(h)}]$. If we have more generators rationally dependent on
$\tau_1,\ldots ,\tau_m$, we can repeat the argument after taking as new generators the
coordinates of the weight vector with respect to the $m$ primitive vectors of
$\sigma$. In both examples, the fact that $k$ is a field plays no role, so we have
proved:
%----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\begin{lemma} Let $\Phi$ be a totally ordered finitely generated
group of height one (i.e., archimedian), or
$\Z^d$ with the lexicographic order. For any commutative ring $A$ the semigroup algebra
$A[t^{\Phi_+}]$ of $\Phi_+$ with coefficients in $A$ is the direct limit of a direct system of graded
subalgebras which are polynomial algebras $A[x_1,\ldots ,x_m]$ over $A$ with
$m=\hbox{\rm r} (\Phi)$.
\par In addition, the maps between these algebras are toric maps,  i.e., each variable of
one is sent to a monomial in the variables of the other, and there is a cofinal subsystem which is
a chain of nested subalgebras.
\end{lemma}
%----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\begin{Remark} 1) In both cases, the smooth
subalgebras  are produced by an algorithm. \par\noindent 2) The result, especially in view of its
algorithmic nature, is much more useful than its consequence that $\hbox{\rm
Spec}A[t^{\Phi_+}]$ is a pro-object in the category of smooth affine toric schemes over
$\hbox{\rm Spec}A$ with toric maps. \par\noindent 3) The proof also shows that the semigroup
algebra of the semigroup  $$\widetilde{\Phi_+}=
\{(a_1,\ldots ,a_m,a_{m+1},\ldots ,a_{m+r})\in \Z^{m+r}\mid \sum_{i=1}^{m+r}a_i\tau_i\geq
0\},$$ where 
$\tau_1,\ldots ,\tau_m$ are rationally independent and the others are rationally dependent upon
them, is a toric direct limit of toric subalgebras of the form 
$$A[x_1,\ldots ,x_m,x_{m+1}^{\pm 1},\ldots ,x_{m+r}^{\pm 1}].$$\par\noindent  4)  The result for
subgroups of ${\mathbf R}$ holds without the finiteness assumption provided the rational rank is finite, since any abelian group
 is a direct limit of its subgroups of finite type.  If we allow
$m$ to vary, even that last assumption is unnecessary.
\end{Remark}
\par\medskip Let now $\Phi$ be a totally ordered group of finite height $h>1$. We have a
surjective monotone non-decreasing map
$\lambda\colon \Phi\rightarrow \Phi_1$ where $\Phi_1$ is of height $h-1$, and the kernel
$\Psi$ of $\lambda$ is of height $1$. By induction on the height we may assume that
$\Phi_{1+}$ is the union of sub-semigroups isomorphic to $\N^m$, and we know from the lemma
above that the same is true for $\Psi_+$. \par Let us denote the free semigroups that fill $\Phi_{1+}$
by $F_i$, and let $\tilde F_i\subset \Phi_+$ be the subsemigroup generated by elements $e_1,
\ldots ,e_{r_i}$ which lift to $\Phi_+\setminus\Psi$ the generators of $F_i$. Similarly let us denote by
$G_j\subset \Psi_+$ free semigroups which fill
$\Psi_+$, generated say by
$f_1,\ldots ,f_{s_j}$. Note that for $\phi\in \Phi_+\setminus\Psi,\ \psi\in \Psi,\ \phi +\psi\in \Phi_+$,  and consider for $r_is_j$-tuples
$n=(n_{s,t},1\leq s\leq r_i,\ 1\leq t\leq s_j)$ of non negative integers, the free semigroups 
$\tilde F_i(n)\subset \Phi_+\cup \{ 0\}$ generated by $e_1-\sum_tn_{1t}f_t,\ldots
,e_{r_i}-\sum_t n_{r_it}f_t$.  Let us check that the direct sums of free semigroups
$ \tilde F_i(n)\oplus G_j$ fill up $\Phi_+$; the proof generalizes that given in the case of the
lexicographic $\Z^d$. Given $\phi \in \Phi_+$, there exists an index $i$ and a $\phi_1\in \tilde
F_i$ such that $\phi-\phi_1\in \Psi$. If we have $\phi -\phi_1\in \Psi_+$, there exists an index
$j$ such that $\phi -\phi_1\in G_j$ so that indeed $\phi \in \tilde F_i\oplus G_j$. This
happens in particular if $\phi\in \Psi$. If
$\phi -\phi_1\in \Psi_-$, there exists an index $j$ such that we can write:
$$\phi=\sum_{s=1}^{r_i}k_se_s-\sum_{t=1}^{s_j}\ell_tf_t\ \hbox{\rm with non negative
integers}\ k_s,\ \ell_t\ \hbox{\rm and}\ f_t\in G_j.$$\noindent  Since $\phi\notin \Psi$, at least one of the $k_s$ is not zero,
say $k_1$. Choosing positive integers $\tilde \ell_t$ such that $k_1\tilde\ell_t >\ell_t$, we may
rewrite $\phi$ as follows
$$\phi=k_1(e_1-\sum_{t=1}^{s_j}\tilde\ell_tf_t)+\sum_{s=2}^{r_i}k_se_s+\sum_{t=1}^{s_j}(k_1\tilde\ell_t-\ell_t)f_t.$$
This shows that $\phi$ is indeed in $ \tilde F_i(n)\oplus G_j$ with $n=\tilde \ell$.\par
Now if we assume, as we may by induction, that the $F_i$ and $G_j$ are nested sequences, and
choose $n(i)$ given by
$(n_{s,t}=i,1\leq s\leq r_i,\ 1\leq t\leq s_j)$, we see that the corresponding groups $ \tilde
F_i(n(i))\oplus G_i$ form a nested sequence which is cofinal in the direct system. So we
have:
%-----------------------------------------------------
\begin{proposition}\label{smgrpapp} For any totally ordered group $\Phi$ of finite height, and
any commutative ring $A$, the  semigroup algebra $A[t^{\Phi_+}]$ is a direct limit of a direct
system of graded polynomial subalgebras over $A$ with monomial maps, and there are cofinal
nested subsystems of such polynomial subalgebras.
 If $\Phi$ is of finite rational rank
$\hbox{\rm r}(\Phi)$, all the polynomial subalgebras may be chosen isomorphic to
$A[x_1,\ldots ,x_{\hbox{\rm r}(\Phi)}]$.
\end{proposition} 
%---------------------------------------------------------
\begin{proof} There remains only to prove the last
sentence. This is done by induction on the height; we have shown above that the result is true for
valuations of height one. Assume that the result is true for $\Psi$ and $\Phi_1$, and so the rank
of the free monoid
$\tilde F_i(n)\oplus G_j$ is the sum of the rational ranks of $\Psi$ and $\Phi_1$. But since the
rational rank is additive in an exact sequence because $\Qq$ is a flat $\Z$-module, this is the
rational rank of $\Phi$. 
\end{proof}

 %------------------------------------------------
\begin{corollary}\label{goodeq}If the rational rank of $\Phi$ is finite, the semigroup algebra
$A[t^{\Phi_+}]$ endowed with its natural grading is a quotient of a polynomial ring over $A$ in countably
 many indeterminates $A[(V_j)_{j\in J}]$ graded by $\Phi_+$ by a homogeneous binomial ideal of the form 
$$(V_j- V^{m(j)})_{j\in J'},$$\noindent where $J'$ is a subset of $J$ and $\vert m(j)\vert\geq 2$ for $j\in J'$.
\end{corollary}
%---------------------------------------------
\begin{proof} We may choose as a system of homogeneous generators of the
$A$-algebra $A[t^{\Phi_+}]$, the union of the generators of the polynomial subalgebras
of which $A[t^{\Phi_+}]$ is the direct limit. The only relations between these generators are those
corresponding to the toric inclusions
$A[x_1,\ldots , x_r]\to A[y_1,\ldots ,y_r]$, and they are of the announced type after we discard
the trivial relations $x_i=y_j$ by removing some generators. 
\end{proof}
%-------------------------------------------------------------------------------------------
\begin{Remark} 1) There is in general no minimal system of generators for $A[t^{\Phi_+}]$ and we can of course discard an arbitrary number of those
generators which appear as $V_j$ in a relation $V_j- V^{m(j)}=0$. For example consider $\Phi=\Z^2_{lex}$. \par\noindent 2) We can apply this to
the subalgebra
$k[v^{\Phi_+}]$ of
$\A_\nu (R)$, and view the $v^\phi$ as coordinates for $\hbox{\rm
Spec}k[v^{\Phi_+}]$ subjected to the binomial relations described in this Corollary.
\end{Remark}
%-------------------------------------------------------------
 \begin{proposition}\label{grapp} Given the ring $R_\nu$ of a
valuation of finite rational rank $r(\nu )$:\par\noindent a) the graded
$k_\nu$-algebra  $\hbox{\rm gr}_\nu R_\nu$ is a quotient of a polynomial ring
$k_\nu[(V_j)_{j\in J}]$ in countably many indeterminates over the residue field
$k_\nu$, graded by $\Phi_+$, by a\break homogeneous binomial ideal of the form  $$(V_j-\lambda_j V^{m(j)})_{j\in J'}\ ,\
\lambda_j\in k_\nu^*$$\noindent where $J'$ is a subset of $J$ and $\vert m(j)\vert\geq 2$ for $j\in J'$.\par\noindent  b) The graded $k_\nu$-algebra 
$\hbox{\rm gr}_\nu R_\nu$ is the union of a nested sequence of graded polynomial subalgebras $k_\nu[x^{(h)}_1,\ldots
,x^{(h)}_{\hbox{\rm r}(\nu )}]$, where the inclusions are given by maps sending each variable
$x^{(h)}_i$ to a constant times a monomial in the $x^{(h+1)}_j,\ 1\leq j\leq \hbox{\rm
r}(\nu )$. \end{proposition}
%--------------------------------------------------------
 \begin{proof}
See Proposition \ref{smgrpapp} and the previous Corollary. We have seen in Proposition
\ref{binomialideal} that $\hbox{\rm gr}_\nu R_\nu$ is isomorphic to a quotient of a
polynomial algebra $k[(V_i)_{i\in I}]$ by a binomial ideal whose generators are of the form
$V^m-\lambda_{mn}V^n$. Setting all the constants $\lambda_{mn}$ equal to one gives the
semigroup algebra $k[t^{\Phi_+}]$, hence assertion a). Assertion b)
follows from this and the correspondence between the direct
system of polynomial subalgebras and the binomial equations
exhibited in the proof of the Corollary to Proposition \ref{smgrpapp}.
\end{proof}
%------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
\begin{corollary} Given any finite set of homogeneous elements $\overline x_1,\overline x_2,\cdots ,\overline x_s$ in 
$\hbox{\rm gr}_\nu R_\nu$ and a cofinal nested system of polynomial subalgebras as above, there is an algebra in our nested system such that not
only do we have
$\overline x_i\in A[x^{(h)}_1,\ldots ,x^{(h)}_{\hbox{\rm r}(\Phi)}]$
 for $1\leq i\leq s$, but the element of least degree divides all the others in this subalgebra.\end{corollary}\par\noindent
\end{section}
\end{chapter}
\begin{chapter}{Completion}
\begin{section}{The case of height one valuations}
\end{section}
\begin{section}{The case of valuations of finite height}
\end{section}
\begin{section}{Pseudo-Cauchy sequences}
\end{section}
\end{chapter}
\begin{chapter}{Applications}
\begin{section}{Valuations and growth conditions}
\end{section}
\begin{section}{Valuations and non oscillating trajectories}
\end{section}
\begin{section}{Valuations and arc spaces}
\end{section}
\end{chapter}
\end{document}

