G Érard Leloup

Gérard Leloup

KEY POLYNOMIALS, SEPARATE AND IMMEDIATE VALUATIONS, AND SIMPLE EXTENSIONS OF VALUED FIELDS

Keywords: Mathematics Subject Classification. 12J10, 12J20, 12F99 simple extension, valuation, key polynomial

We give a first-order definition of key polynomials, we show the links with previous definitions, that it is relevant to study key degrees, and to use a kind of valuations that we call partially multiplicative. We also prove or reprove several properties.

We have changed definitions from the first version of this paper, in order to make them consistent with those of other papers. Some computational and tedious proofs have been omitted in this new version. The reader can find them in versions 1 and 2 of this paper.

Valuations occur in different areas of mathematics, for example in algebraic geometry. In particular, some authors studied the extension of a valuation ν, defined on a field K, to K [ χ ]. For this purpose, they construct K-module valuations which converges to ν. These K-module valuations are defined using polynomials which are called key polynomials. For his part, the author of the present article has studied the first order properties of extensions of valued fields. In this context, vs defecless extensions, immediate extensions and the initial segments ν(l -K) (l / ∈ K) play an important role. Now, there are similarities between these two types of studies. We found interesting to revisit the key polynomials and the associated valuations in the light of another background. The approach of the present paper relies on euclidean division of polynomials, bases of vector spaces or modules, and the notions of vs defectless and immediate extensions (Definitions 1.1 and 1.4). Indeed, vs defectless (or separate) and immediate extensions play a crucial role in the study of the first-order theory of extensions of valued fields ( [2], [3], [START_REF] Delon | Extensions séparées et immédiates de corps valués[END_REF], [START_REF] Delon | Indécidabilité de la théorie des paires de corps valués henseliens[END_REF], [START_REF] Leloup | Théories complètes de paires de corps valués henseliens[END_REF], [START_REF] Leloup | Properties of extensions of algebraically maximal fields[END_REF]).

Let (K, ν) be a valued field and χ be algebraic or transcendental over K. Key polynomials were introduced to approximate an extension of ν to the field K( χ ) by K-module valuations. In particular, this study uses K-module valuations such that there exists a monic polynomial Φ of degree d such that the family (Φ n ) (n ≥ 0) is separated over the K-module K d-1 [ χ ] of polynomials of degree at most d -1 (they are also called augmented valuations or truncated mappings). Here we denote them by ν Φ . In the case where χ is algebraic over K, these K-module valuations cannot be valuations of fields since they do not satisfy the rule ν(f g) = ν(f ) + ν(g). However, they can satisfy this rule if deg(f ) + deg(g) < [K( χ ) : K]. If this holds, then we call them pm valuations. In fact, ν Φ is a pm valuation if Φ is what we call here a weak key polynomial (in short w key polynomial). These w key polynomials are related to the key polynomials defined by MacLane (we show that Φ being a w key polynomial for ν is equivalent to being a MacLane key polynomial for ν Φ ), but we do not require to define families of w key polynomials by induction.

In order to construct families of pm valuations which approximate ν on K( χ ), we can restrict to a subfamily of w key polynomials whose definition differs slightly. We call them key polynomials, because we prove that these polynomials are the key polynomials defined in [START_REF] Novakoski | Key polynomials and pseudo-convergent sequences[END_REF], [START_REF] Decaup | Abstract key polynomials and comparision theorems with the key polynomials of Mac Lane-Vaquié[END_REF] and [START_REF] Novakoski | Key polynomials and minimal pairs[END_REF] (in [START_REF] Decaup | Abstract key polynomials and comparision theorems with the key polynomials of Mac Lane-Vaquié[END_REF] they are called abstract key polynomials). Here, we do not restrict to transcendental extensions and we give a characterization of key polynomials by means of first order formulas (in the language of valued fields together with a predicate interpreted by the generator of the simple extension).

We classify the key polynomials according to their degrees, that we call key degrees. On the one hand, key degrees d such that the set ν( χ d -K d-1 [ χ ]) has a greatest element, on the other hand key degrees d such that the set ν( χ d -K d-1 [ χ ]) has a no greatest element. This already appeared in the works of S. MacLane and of M. Vaquié. They construct the key polynomials by induction, starting from the degree 1 key polynomials, and two cases arise: the set ν( χ d -K d-1 [ χ ]) having or not a greatest element. We will show that in the first case we have a vs defectless subextension, which is generated by a valuation independent element, and in the last one this subextension is immediate. So in the first case we say that d is an independent key degree, and in the latter case we say that it is an immediate key degree. In the construction of key polynomials by induction on the degree, some authors introduced the definition of limit key polynomials. In fact, a key polynomial is a limit key polynomial if, and only if, the preceding key degree is an immediate one.

In the present paper we do not require the reader having any previous knowledge of key polynomials. As much as possible, we try to use only elementary properties of valuations. However, we use the graded algebra associated to a valuation in two proofs. Indeed, these graded algebras are a good tool for providing nice proofs of some properties of vs defectless extensions. With exception of Section 5, this paper is self-contained.

General properties.

A valuation on a field K is a morphism ν from the multiplicative group (K * , •) to an abelian linearly ordered group (νK, +) called the valuation group, which enjoys an additional property. We add an element ∞ to νK (∞ > νK), we set ν(0) := ∞, and we assume that ν(x + y) ≥ min(ν(x), ν(y)), for every x, y in K. It follows that if ν(x) = ν(y), then ν(x+y) = min(ν(x), ν(y)). If ν(x) = ν(y), then ν(x + y) can be arbitrarily large. The set {x ∈ K | ν(x) ≥ 0} is a local domain and {x ∈ K | ν(x) > 0} is its maximal ideal, they are called respectively the valuation ring and the maximal ideal of the valued field. The quotient of the valuation ring by the maximal ideal is a field which is denoted by K ν , and is called the residue field of the valued field. The residue characteristic of (K, ν) is the characteristic of K ν . We have char K ν = 0 ⇒ char K = 0. For x in the valuation ring of (K, ν), its class modulo the maximal ideal will be denoted by x ν . For every subset M of K we denote by ν(M ), or νM , the set {ν(x) | x ∈ M }\{∞}.

condition that the sets ν( χ n -K n-1 [ χ ]) haves greatest element (Proposition 1.15). Then we recall definitions and properties of the graded algebras associated to valuations. In particular, we note that in the case of a generalized power series field, this graded algebra is isomorphic to the ring of generalized polynomials. Furthermore, we prove that a family is separated if, and only if, its image in the graded algebra is linearly independent (Proposition 1.16). In Section 2 we characterize w key polynomials, key polynomials and key degrees. In particular, we note that if Φ is an irreducible polynomial, then it is a w key polynomial if, and only if, the quotient field K[ χ ]/(Φ) is a valued field. We define the vs defectless K-module valuations ν φ . We deduce other characterizations of w key polynomials. These characterizations will be used in latter sections. In Section 3 we compare the definition of w key polynomials with the definition of S. MacLane and M. Vaquié (Proposition 2.12). We set properties of key degrees in Section 4. We show that in the case where ν( χ d -K d-1 [ χ ]) has a maximum, we only need to look at monic polynomials with maximal valuations. We characterize key degrees, that we call valuational, by means of the value group (Proposition 4.3). We also focus on conditions for existing only a finite number of key degrees, since this makes simpler the constructions of families of pm valuations which approximate ν. We look at the case of a dense key degree, that is immediate key degrees d such that ν( χ d -K d-1 [ χ ]) is equal to ν(K [ χ ])\{∞} (Proposition 4.8). We also give characterizations of the successor of a given key degree (Theorems 4.9 and 4.10). These characterizations will be useful for proving the equivalence of our definition and the definition of abstract key polynomials. In Subsection 4.4 we give a construction of a family of pm valuations which approximate ν (defined by a family of key polynomials), without proceeding by induction on the degree (Theorem 4.12). In Section 5 we show that the key polynomials defined in [START_REF] Novakoski | Key polynomials and pseudo-convergent sequences[END_REF], [START_REF] Decaup | Abstract key polynomials and comparision theorems with the key polynomials of Mac Lane-Vaquié[END_REF] and [START_REF] Novakoski | Key polynomials and minimal pairs[END_REF] are the same as the key polynomials defined here (Corollaries 5.3 and 5.5).

Before starting, let us set some notations. Let l ∈ L and M be a K-submodule of L. We denote by ν(l -M ) the subset {ν(l -x) | x ∈ M }\{∞} of νL. For any polynomial f , we denote by

ν(f (M )), or νf (M ), the subset {ν(f (x)) | x ∈ M }\{∞}.
Note that ν(l -M ) ∩ νM is an initial segment of νM .

Immediate and vs defectless extensions

In order to show the importance of vs defectless and immediate extensions of valued fields as well of the initial segments ν(l -K), we start by stating some results of model theory of extensions of valued fields. A valued field (K, ν) is said to be algebraically maximal if no extension of ν to an algebraic extension of K is immediate. If the residue characteristic is 0, then being algebraically maximal is equivalent to being henselian, i.e. ν having a unique extension to any agebraic extension of K. A famous theorem of J. Ax, S. Kochen and Y. Ershov ( [1]) says that the elementary theory of a henselian valued field (K, ν) of residue characteristic 0 is determined by the elementary theory of its residue field and the elementary theory of its value group. Next, this result was extended to other families of algebraically maximal valued fields. The aim is to get similar results in the case of extensions of valued fields. Now, in [START_REF] Delon | Indécidabilité de la théorie des paires de corps valués henseliens[END_REF] F. Delon proved that given a theory T F of fields of characteristic 0 and a theory T V of non trivial linearly ordered abelian groups, the theory of immediate henselian extensions (L|K, ν), where K ν is a model of T F and νK is a model of T V , is indecidable and admits 2 ℵ0 completions. This theory also depends at least on the family of all initial segments ν(l-K), with l ∈ L\K. Now, if K, L are henselian, charK ν = 0, and (L|K, ν) is vs defectless, then the first-order theory of the extension is determined by the theories of the residual extension and of the extension of valued groups. The same holds if (L|K, ν) is an extension of algebraically maximal Kaplansky fields or of real-closed fields (see [2], [3], [START_REF] Leloup | Théories complètes de paires de corps valués henseliens[END_REF], [START_REF] Leloup | Properties of extensions of algebraically maximal fields[END_REF]). Furthermore, we have similar results with dense extensions. In the case where (L|K, ν) is an extension of valued fields of residue characteristic 0, there exists a henselian subfield H, K ⊆ H ⊆ L, such that (H|K, ν) is vs defectless and (L|H, ν) is immediate (see [START_REF] Delon | Extensions séparées et immédiates de corps valués[END_REF]). This shows that it can be interesting to focus on vs defectless and immediate extensions.

In this section, L|K is an extension of fields and ν is a K-module valuation on L.

1.1. Immediate extensions. If M is a K-module, then we assume that νM has no greatest element. This holds if νK is not trivial. Indeed, for every x ∈ K with ν(x) > 0 and y ∈ M , we have xy ∈ M and ν(xy) = ν(x) + ν(y) > ν(y). Definitions 1.1. Let M ⊆ N be K-submodules of L, and l ∈ L.

We say that l is pseudo-limit over (M, ν) if ν(l -M ) ⊆ νM , and ν(l -M ) has no maximal element.

We say that l is limit over (M, ν) if ν(l -M ) = νM . The extension (N |M, ν) is said to be immediate if every element of N is pseudo-limit over (M, ν).

The extension (N |M, ν) is said to be dense if every element of N is limit over M .

It follows that if (N |M, ν) is dense, then it is immediate. The proof of the following is left to the reader (see for example [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF]). Let l ∈ L and M be a K-submodule of L. The element l is pseudo-limit over (M, ν) if, and only if, for every x ∈ M there exists y ∈ M such that ν(l -y) > ν(l -x).

Notations 1.2. For γ in νL and M a K-submodule of L, let M γ,ν be the

K ν -module {x ∈ M | ν(x) ≥ γ}/{x ∈ M | ν(x) > γ}.
In the case where γ = 0, we often write M ν instead od M 0,ν . For f ∈ M with ν(f ) ≥ γ, we denote by f γ,ν the class of f modulo {g ∈ M | ν(g) > γ}. Proof. Left to the reader (see for example [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF]).

1.2. Vs defectless extensions.

Definitions 1.4. ( [2], [3], [START_REF] Blaszczok | On valuation independence and defectless extensions of valued fields[END_REF]). Let M be a K-submodule of L. 1) A sequence (l 1 , . . . , l n ) of L is said to be separated over M (or ν-separated if necessary) if for every x 1 , . . . , x n in M , we have:

ν(x 1 l 1 + • • • + x n l n ) = min 1≤i≤n ν(x i l i ). If M = K,
then we say separated instead of separated over K. An infinite sequence is called separated if every finite subsequence is separated.

2) The extension (L|K, ν) is said to be vs defectless if every finitely generated K-submodule of L admits a basis which is separated over K. If this holds, then we say that ν is vs defectless (or vs defectless over K).

Note that if (l 1 , . . . , l n ) is separated, then l 1 , . . . , l n are linearely independent over K.

In [2] and [3] Baur introduces the terms separated families and separated extensions. The authors of [START_REF] Blaszczok | On valuation independence and defectless extensions of valued fields[END_REF] noted that the word separated can bring confusion in algebraic geometry (for example with separable extension). So they prefer use the terms valuation independent sets and vs defectless extensions. Following these authors we use the term vs defectless extension instead of separated extension. Concerning Baur's separated families, there is a slight difference with the definition of valuation independent families. A valuation independent set is separated, but if B is valuation independent, then B ∪ {1} remains separated.

Example 1.5. Let (K, ν) be a valued field. Pick some x in K, some γ in an extension of νK, and, for every

x 0 , x 1 , . . . , x n in K, set ν (x n ( χ -x) n +• • •+x 1 ( χ -x)+x 0 ) := min(ν(x n )+nγ, . . . , ν(x 1 )+ γ, ν(x 0 )).
Then one can check that ν defines a pm valuation on the ring K [ χ ]. The pm valuation ν is vs defectless and 1, ( χ -x), . . . , ( χ -x) n , . . . is a separated basis of (K[ χ ], ν ).

Note that if ν is another K-module valuation on K [ χ ] which extends ν and such that ν( χ -x) = γ, then, for every

f in K[ χ ], ν (f ) ≤ ν (f ).
The following properties provide other examples of vs defectless extensions.

• If (K, ν) is a maximal valued field, then every multiplicative extension of (K, ν) is vs defectless ([2, Lemma 3]).

• Assume that ν is multiplicative on L, that the residue characteristic of (K, ν) is 0 and that (K, ν) is henselian that is, ν admits a unique extension to every algebraic extension of K. Then any algebraic extension of (K, ν) is vs defectless ([6, Corollaire 7]).

• Assume that L is a finite algebraic extension of K. Then (L|K, ν) is vs defectless if, and only if, the K-module L admits a separated basis. This is an immediate consequence of the following lemma.

Lemma 1.6. ([6, Lemma 5]). Let M ⊆ N be two K-submodules of L such that M is finitely generated and N admits a separated basis. Then M admits a separated basis.

The remainder of this subsection is dedicated to properties which make clear the difference between immediate and vs defectless extensions.

Assume that ν is multiplicative on L and that (K, ν) is henselian of residue characteristic 0. Then (L|K, ν) is vs defectless if, and only if, L is linearly disjoint over K from every immediate extension of (K, ν) ([6, p. 421]).

Theorem 1.7. ([6, p. 421], [START_REF] Blaszczok | On valuation independence and defectless extensions of valued fields[END_REF]) Let N be a K-submodule of L. Then, (N |K, ν) is a vs defectless extension if, and only if, for every finitely generated K-submodule M of N and l ∈ N \M , the set ν(l -M ) has a maximal element.

This theorem has been stated in [6, p. 421], assuming that (K, ν) is henselian and char(K ν ) = 0. A general proof has been given independently in [START_REF] Blaszczok | On valuation independence and defectless extensions of valued fields[END_REF] and [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF].

We know that if L|K is finite and ν is multiplicative, then 1 ≤ [L ν : K ν ](νL : νK) ≤ [L : K]. Furthermore, by Remark 1.3, (L|K, ν) is immediate if, and only if, 1 = [L ν : K ν ](νL : νK). The following theorem shows that (L|K, ν) being vs defectless can be seen as the opposite case. It has been proved independently in [START_REF] Blaszczok | On valuation independence and defectless extensions of valued fields[END_REF] and [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF].

Theorem 1.8. Assume that L|K is a finite algebraic extension of fields and that ν is multiplicative on L. Then (L|K, ν) is vs defectless if, and only if,

[L : K] = [L ν : K ν ](νL : νK).
Let (L|K, ν) be a finite extension of valued fields (where ν is multiplicative). We say that

(L|K, ν) is defectless if [L : K] [L ν : K ν ](νL : νK)
is equal to the number of extensions of ν |K to L.

As a corollary of Theorem 1.8 we get that if (K, ν) is henselian, then every defectless finite algebraic extension of (K, ν) is vs defectless. 1.3. Extensions generated by one element. In this subsection χ is algebraic or transcendental over K. Recall that if d is a non-negative integer, then K d [ χ ] denotes the K-module of polynomials of degree at most d. Note that K 0 [ χ ] = K and in the transcendental case we let

K ∞ [ χ ] = K[ χ ]. Proposition 1.9. Let d < d in N ∪ {∞} such that if χ is algebraic over K, then d < [K[ χ ] : K]. 1) (K d [ χ ]|K d [ χ ], ν) is immediate if,
and only if, for every integer n ∈ {d + 1, . . . , d }, ν( χ n -K n-1 [ χ ]) has no maximal element. 2) Assume that ν is a pm valuation and that νK d [ χ ] is a subgroup of ν(K [ χ ]). Then the extension

(K d [ χ ]|K d [ χ ], ν) is dense if, and only if, for every integer n ∈ {d + 1, . . . , d }, ν( χ n -K n-1 [ χ ]) = νK d [ χ ]. Proof. 1) ⇒. Assume that, for some integer n ∈ {d + 1, . . . , d }, ν( χ n -K n-1 [ χ ]) has a greatest element ν(f ). If ν(f ) is not in νK d [ χ ], then νK d [ χ ] = νK d [ χ ]
, and, by Remark 1.3 1), the extension is not immediate. Suppose that ν(f

) ∈ νK d [ χ ], say ν(f ) = γ. For every g ∈ K d [ χ ] we have ν(f -g) ≤ ν(f ), hence f γ,ν = g γ,ν . It follows that (K d [ χ ]) γ,ν = (K d [ χ ]) γ,ν , so the extension is not immediate. ⇐. Assume that (K d [ χ ]|K d [ χ ], ν)
is not immediate, and let n be the smallest integer such that, for some polynomial f of degree n, either ν(f

) / ∈ νK d [ χ ] or, for every g ∈ K d [ χ ], f γ,ν = g γ,ν
, where γ = ν(f ). Note that, by dividing f by an element of K, we can assume that f is a monic polynomial of degree n.

First assume that γ / ∈ νK d [ χ ], and let g be a monic polynomial of degree n.

Then deg(f -g) < n, hence, by minimality of n, ν(f -g) ∈ νK d [ χ ]. So ν(f -g) = ν(f ). It follows: ν(g) = min(ν(g - f ), ν(f )) ≤ ν(f ), which proves that ν(f ) is the greatest element of ν( χ n -K n-1 [ χ ]). Assume that γ = ν(f ) ∈ νK d [ χ ]
, and, for every

g ∈ K d [ χ ], f γ,ν = g γ,ν . Let g be a monic polynomial of degree n. If ν(g -f ) = γ, then ν(g) = min(ν(g -f ), ν(f )) ≤ ν(f ). Now, assume that ν(g -f ) = γ. We have deg(f -g) < n, hence, by minimality of n, (g -f ) γ,ν = h γ,ν for some h ∈ K d [ χ ]. Therefore we have f γ,ν = (g-f ) γ,ν . So ν(g) = ν(g-f +f ) = min(ν(g-f ), ν(f )) ≤ ν(f ). Consequently, ν(f ) is the greatest element of ν( χ n -K n-1 [ χ ]). 2) If (K d [ χ ]|K d [ χ ], ν) is dense, then it is immediate. Hence for every integer n ∈ {d + 1, . . . , d } we have: ν( χ n -K n-1 [ χ ]) ⊆ νK d [ χ ]. Furthermore: ν( χ d+1 -K d [ χ ]) = νK d [ χ ]. Now, for every integer n ∈ {d + 2, . . . , d } we have ν( χ n -K n-1 [ χ ]) ⊇ ν( χ n -χ n-(d+1) K d [ χ ]) = (n -(d + 1))ν( χ ) + ν( χ d+1 -K d [ χ ]) = νK d [ χ ] (since νK d [ χ ] is a subgroup). It follows: ν( χ n -K n-1 [ χ ]) = νK d [ χ ].
Conversely, assume that for every integer n ∈ {d+1, . . . , d } we have ν(

χ n -K n-1 [ χ ]) = νK d [ χ ]
. Then in particular it has no greatest element. So by a)

(K d [ χ ]|K d [ χ ], ν) is immediate. Let f ∈ K d [ χ ]
, n be its degree and x n be the coefficient of χ n in f . Without loss of generality we can assume that the integer n belongs to {d + 1, . . . , d }. We show that for every γ ∈ νK d [ χ ] there is

g ∈ K d [ χ ] such that ν(f -g) > γ. For every g n-1 ∈ K n-1 [ χ ] we have f /x n -g/x n ∈ χ n -K n-1 [ χ ]. Hence since ν( χ n -K n-1 [ χ ]) = νK d [ χ ] which is a subgroup, we can choose g n-1 ∈ K n-1 [ χ ] such that ν((f /x n )-(g n-1 /x n )) > γ -ν(x n ). Hence ν(f -g n-1 ) > γ. In the same way, for d ≤ j ≤ n-2 we get g j ∈ K j [ χ ] such that ν(g j+1 -g j ) > γ. Therefore ν(f -g d ) = ν(f -g n-1 + • • • + g d+1 -g d ) ≥ min(ν(f -g n-1 ), . . . , ν(g d+1 -g d )) > γ. So every element of K d [ χ ] is limit over K d [ χ ]. This implies that (K d [ χ ]|K d [ χ ], ν) is dense.
We turn to vs defectless extensions, and we start with properties of separated sequences.

Lemma 1.10. ([3, p. 676]) Let (l 1 , . . . , l n ) be a separated sequence of elements of L, y in L\{0} and k 1 , . . . , k n in K\{0}. The following holds. Every subsequence of (l 1 , . . . , l n ) is separated. The sequence

(k 1 l 1 , . . . , k n l n ) is separated. If ν is multiplicative on L, then the sequence (yl 1 , . . . , yl n ) is separated. Lemma 1.11. ([2], [3, (S4), p. 676]) Let (l 1 , . . . , l n ) be a sequence of elements of L such that: ∀i, 1 ≤ i ≤ n, ν(l i ) = 0. Then (l 1 , . . . , l n ) is separated if,
and only if, (l 1 ) ν , . . . , (l n ) ν are linearly independent over K ν . This can be generalized in the following way.

If ν(l 1 ) = • • • = ν(l n ) = g, then (l 1 , . . . , l n ) is separated if, and only if, for every x 1 , . . . , x n in {x ∈ K | ν(x) = 0} ∪ {0}, either ν(x 1 l 1 + • • • + x n l n ) = g or x 1 = • • • = x n = 0.
Proposition 1.12. Let l i1 , . . . , l ini , 1 ≤ i ≤ p, be sequences which satisfy:

∀i, 1 ≤ i ≤ p, ∀j, 1 ≤ j ≤ n i , ν(l ij ) = ν(l i1 ) < ∞
and the ν(l i1 ) are pairwise non-congruent modulo νK. The following assertions are equivalent. The sequence l 11 , . . . , l 1n1 , l 21 , . . . , l 2n2 , . . . , l p1 , . . . , l pnp is separated. For every i in {1, . . . , p}, l i1 , l i2 , . . . , l ini is separated. If ν is multiplicative on L then this condition is equivalent to: for every i in {1, . . . , p}, 1, (l i2 l -1 i1 ) ν , . . . , (l ini l -1 i1 ) ν are linearly independent over K ν . Proof. Assume that the sequence is separated. Then by Lemma 1.10, for 1 ≤ i ≤ p, the sequence l i1 , l i2 , . . . , l ini is separated.

Conversely, let x 11 , . . . , x 1n1 , x 21 , . . . , x 2n2 , . . . , x p1 , . . . , x pnp in K. For 1

≤ i ≤ p, set y i = x i1 l i1 + • • • + x ini l ini . Since l i1 , . . . , l ini is separated, we have: ν(y i ) = min{ν(x ij ) + ν(l ij ) | 1 ≤ j ≤ n i }.
Therefore, the ν(y i )'s are pairwise non-congruent modulo νK. In particular, they are pairwise distinct, and ν(y

1 + • • • + y p ) = min{ν(y i ) | 1 ≤ i ≤ p}.
This proves that the sequence l 11 , . . . , l 1n1 , l 21 , . . . , l 2n2 , . . . , l p1 , . . . , l pnp is separated.

If ν is multiplicative on L, then

l i1 , l i2 , . . . , l ini is separated if, and only if, 1, (l i2 l -1 i1 ), . . . , (l ini l -1 i1 ) is separated. By Lemma 1.11, this in turn is equivalent to 1, (l i2 l -1 i1 ) ν , . . . , (l ini l -1 i1 ) ν are linearly independent over K ν .
Lemma 1.13. Assume that (L|K, ν) is vs defectless. Let M be a finite K-submodule of L and l ∈ L\M . Then every separated basis of M extends to a separated basis of the K-submodule generated by M and l.

Proof. The proof is left to the reader (see for example [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF]).

Proposition 1.14. Let d ∈ N ∪ {∞} such that 0 < d and if χ is algebraic over K, then d < [K[ χ ] : K]. Then (K d [ χ ]|K, ν
) is vs defectless if, and only if, the K-module K d [ χ ] admits a separated basis. Furthermore, we can assume that every polynomial of this basis is monic and that the mapping f → deg(f ), from this basis onto N, is one-to-one. Assume that χ is transcendental over K, and that ν is multiplicative on K( χ ). Then (K( χ )|K, ν) is vs defectless if, and only if, the K-module K [ χ ] admits a separated basis. (⇒ holds even if ν is not multiplicative).

Proof. Assume that (K d [ χ ]|K, ν) is vs defectless. By Lemma 1.13, the separated basis 1 of K extends to a separated basis of the module generated by 1 and χ . Necessarily, the second element of this basis has degree 1. Let n ≥ 1 and assume that the K-module K n [ χ ] of polynomials of degree at most n has a separated basis of (n + 1) elements of respective degrees 0, 1, . . . , n. By Lemma 1.13, this separated basis can be completed in a separated basis of K n+1 [ χ ], and the degree of the new element is n + 1. So we get the required separated basis by induction. By Lemma 1.10 we can assume that every polynomial of this basis is monic.

Conversely, assume that K d [ χ ] contains a separated basis, and let M be a finitely generated K-submodule. By Lemma 1.6, M has a separated basis. Hence (K( χ )|K, ν) is vs defectless.

We turn to the case where χ is transcendental over K. It follows from the definition (Definition

1.4 2)) that if (K( χ )|K, ν) is vs defectless, then so is (K[ χ ]|K, ν). Now we assume that (K[ χ ]|K, ν)
is vs defectless and that ν is multiplicative on K( χ ). Let M be a finitely generated submodule of K( χ ). Then there is a polynomial f = 0 such that f •M ⊆ K [ χ ]. We take a separated basis of f •M , and we divide all its elements by f so that, since ν is multiplicative, by Lemma 1.10, we get a separated basis of M .

We state a refinement of Theorem 1.7, which characterizes vs defectless extensions by means of initial segments. This proposition completes Proposition 1.9.

Proposition 1.15. Let d ∈ N ∪ {∞} such that 0 < d and if χ is algebraic over K, then d < [K[ χ ] : K]. The extension (K d [ χ ]|K, ν) is vs defectless if, and only if, for every integer n, 1 ≤ n ≤ d, ν( χ n -K n-1 [ χ ]
) has a maximal element. Assume that χ is transcendental over K, and that ν is multiplicative on K( χ ). Then (K( χ )|K, ν) is vs defectless if, and only if, for every n ∈ N\{0}, ν( χ n -K n-1 [ χ ]) has a maximal element.

Proof. In both equivalences, ⇒ follows from Theorem 1.7. In order to prove the converse, we construct by induction a separated basis such that the mapping f → deg(f ) is one-to-one. Then, by Proposition 1.14, (K d [ χ ]|K, ν) is vs defectless. The case where χ is transcendental also follows from Proposition 1.14. Trivially, 1 is a separated basis of K 0 [ χ ] = K. Assume that we have a separated basis (f 0 , . . . , f n-1 ) of K n-1 [ χ ]. Let f n be a monic polynomial such that ν(

f n ) = max(ν( χ n - K n-1 [ χ ])). Since the degree of f n is n, (f 0 , . . . , f n-1 , f n ) is a basis of K n [ χ ]. Let f := x n f n + • • • + x 0 f 0 in K n [ χ ]. If x n = 0, then by induction hypothesis ν(f ) = min 0≤i≤n-1 ν(x i f i ) = min 0≤i≤n ν(x i f i ). Now we assume: x n = 0. Since ν(f n ) is maximal, we have ν f x n ≤ ν(f n ). If ν f xn -f n < ν(f n ), then ν f x n -f n = ν f x n . So: ν(f ) = ν(x n ) + ν f x n = ν(x n ) + ν f x n -f n = ν(x n ) + ν x n-1 f n-1 x n + • • • + x 0 f 0 x n = = ν(x n ) + min 0≤i≤n-1 ν x i f i x n = min 0≤i≤n-1 ν(x i f i ) = min 0≤i≤n ν(x i f i ). If ν f x n -f n ≥ ν(f n ), then min 0≤i≤n-1 ν(x i f i ) ≥ ν(x n f n ) ≥ ν(f ) ≥ min 0≤i≤n ν(x i f i ). Therefore: ν(f ) = min 0≤i≤n ν(x i f i ).
1.4. Graded algebra associated to a valuation. In the proofs of Proposition 4.7 and Theorem 4.10 we will introduce the graded algebra associated to a valuation. Now, we review some observations. Let (K, ν) be a valued field. Recall that, for every γ ∈ νK, K γ,ν denotes the

K ν -module {x ∈ K | ν(x) ≥ γ}/{x ∈ K | ν(x) > γ}. Now, let G ν (K) be the graded algebra G ν (K) = γ∈νK K γ,ν .
In the case where K is the valued field k((Γ)) of generalized formal power series with coefficients in a field k and exponents in a linearly ordered abelian group Γ:

k((Γ)) =    γ∈Λ x γ X γ | Λ is a well-ordered subset of Γ, and ∀γ ∈ Λ x γ ∈ k    , then G ν (K) is isomorphic to the ring of generalized polynomials k[Γ],
the subring of all elements of k((Γ)) with finite support. Note that if k 1 |k 0 is an extension of fields and Γ 1 |Γ 0 is an extension of groups, then

k 1 [Γ 1 ] is a k 0 [Γ 0 ]-module. Its dimension is finite if, and only if, both of [k 1 : k 0 ] and (Γ 1 : Γ 0 ) are finite. If this holds, then this dimension is [k 1 : k 0 ](Γ 1 : Γ 0 ).
More generally, let γ ∈ νK and pick an element x 0 of valuation γ. Then the mapping

x ν(x),ν → (xx -1 0 ) ν induces a K ν -module isomorphism between {x ∈ K | ν(x) ≥ γ}/{x ∈ K | ν(x) > γ} and K ν . Hence, the K ν -module G ν (K) is isomorphic to the K ν -module K ν [νK]
of polynomials with coefficients in K ν and exponents in νK. If K contains a lifting of νK, then we can assume that these graded algebras are isomorphic. In particular, if νK = Z, then they are isomorphic. If (K , ν ) is an ℵ 1 -saturated elementary extension of (K, ν), then it contains a lifting of its value group (see [START_REF] Kochen | The model theory of local fields, Logic Conference[END_REF]). Hence G ν (K ) is isomorphic to the ring of polynomials K ν [ν K ]. Therefore every graded algebra G ν (K) embeds in a ring of polynomials. If (K, ν) contains a lifting K 0 of its residue field and a lifting Γ of νK, then it contains the algebra K 0 [Γ], which is isomorphic to G ν (K). Now, if (K, ν) is henselian and char(K ν ) = 0, then we know that it admits a lifting of K ν . It follows that every valued field (K, ν) of residue characteristic 0 admits an extension (K , ν ) which contains a subalgebra which is isomorphic to G ν (K). Furthermore, (K , ν ) embeds in the power series field K 0 ((ν K )) equipped with the canonical valuation.

For every x ∈ K, let in ν (x) := x ν(x),ν be the image of x in K ν(x),ν , which is also its image in G ν (K). In the case of a subfield of a power series field, we have

in ν   γ∈Λ x γ X γ   = x γ0 X γ0 ,
where γ 0 is the smallest element of the support of the series (i.e. the well ordered subset Λ of νK such that x γ0 = 0). In general, for every x, y in K, we have in ν (x)in ν (y) = in ν (xy). Assume that ν(x) = ν(y). If in ν (x) = -in ν (y), then ν(x + y) > ν(x) and ν(x + y) can be arbitrarily large, so we have

in ν (x + y) = 0. Otherwise, in ν (x + y) = in ν (x) + in ν (y). An element of G ν (K)
(L) = G ν (K).
Now we turn to the vs defectless case.

Proposition 1.16. Let (L|K, ν) be an extension of valued fields, and l 1 , . . . , l n in L. The family (l 1 , . . . , l n ) is separated over (K, ν) if, and only if, in ν (l 1 ), . . . , in ν (l n ) are linearly independent over G ν (K).

If (l 1 , . . . , l n ) is a maximal separated family, then (in ν (l 1 ), . . . , in ν (l n )) is a basis of G ν (L). Assume that L|K is finite. Then (L|K, ν) is vs defectless if, and only if, G ν (L) is a G ν (K)-module of dimension [L : K].
Proof. Recall that the family (l 1 , . . . , l n ) is separated over (K, ν) if, and only if, for every x 1 , . . . , x n in K, ν(x

1 l 1 +• • •+x n l n ) = min(ν(x 1 l 1 ), . . . , ν(x n l n ))
. Now, this equivalent to saying that for every x 1 , . . . , x n in K with ν(x

1 l 1 ) = • • • = ν(x n l n ), we have ν(x 1 l 1 + • • • + x n l n ) = ν(x 1 l 1 ). This last equality is equivalent to in ν (x 1 )in ν (l 1 ) + • • • + in ν (x n )in ν (l n ) = 0. So, if in ν (l 1 ), . . . , in ν (l n ) are linearly independent in the G ν (K)-module G ν (L)
, then the family (l 1 , . . . , l n ) is separated. Now, assume that for every x 1 , . . . , x n in K with ν(x

1 l 1 ) = • • • = ν(x n l n ), we have ν(x 1 l 1 + • • • + x n l n ) = ν(x 1 l 1 )
. Let y 1 , . . . , y n in G ν (K). Every y j can be written as a finite sum of homogeneous elements:

y j = in ν (x j,1 ) + • • • + in ν (x j,ij ). It follows that y 1 in ν (l 1 ) + • • • + y n in ν (l n ) can be written as a sum of in ν (x 1,k1 )in ν (l 1 ) + • • • + in ν (x n,kn )in ν (l n )'s
, where the non-zero in ν (x j,kj )in ν (l j ) have the same valuation. Therefore, y 1 in ν (l 1 ) + • • • + y n in ν (l n ) = 0. Consequently, the family (l 1 , . . . , l n ) is separated over (K, ν) if, and only if, in ν (l 1 ), . . . , in ν (l n ) are linearly independent over G ν (K). Furthermore, if (l 1 , . . . , l n ) is a maximal separated family, then (in ν (l 1 ), . . . , in

ν (l n )) is a basis of G ν (L). Now, if [L : K] is finite, then the dimension of the G ν (K)-module G ν (L) is [L ν : K ν ]•(νL : νK).
Hence, by Theorem 1.8, (L|K, ν) is vs defectless if, and only if,

G ν (L) is a G ν (K)-module of dimension [L : K].
The following lemma shows that if, for l ∈ L, in ν (l) satisfies a relation of algebraic dependence over G ν (K), then we can define its irreducible polynomial.

Lemma 1.17. Let (L|K, ν) be an extension of valued fields, and l ∈ L. Assume that in ν (l) satisfies a relation of algebraic dependence over G ν (K), and let n be the smallest degree such that in ν (l) satisfies a relation of algebraic dependence of degree n. Then, in ν (l) satisfies a relation of the form in ν (l

) n + in ν (x n-1 )in ν (l) n-1 + • • • + in ν (x 0 ) = 0, where x 0 , . . . , x n-1 belong to K and ν(x 0 ) = • • • = ν(x n-1 l n-1 ) = ν(l n ).
Proof. See for example [START_REF] Herrera Govantes | Valuations in algebraic field extensions[END_REF].

Key polynomials

In this section, χ is algebraic or transcendental over the field K and ν is a K-module valuation on K( χ ).

2.1. Definitions. Notation 2.1. Let Φ be a monic polynomial of degree d ≥ 1. For f , g in K d-1 [ χ ], we will denote by q Φ (f, g) and r Φ (f, g) respectively (in short q(f, g) and r(f, g)) the quotient and the remainder of the euclidean division of f g by Φ. In other words, q(f, g) and r(f, g) belong to K d-1 [ χ ] and f g = Φ•q(f, g) + r(f, g). Definitions 2.2. Let Φ be a monic polynomial of degree d ≥ 1. We say that Φ is a weak key polynomial for ν (or a w key polynomial for ν) if, for every f , g in

K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K], we have ν(f g) = ν(r(f, g)).
We say that Φ is a key polynomial for ν if, for every f ,

g in K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K], we have ν(f g) = ν(r(f, g)) < ν(q(f, g)•Φ).
Let d be a positive integer. We say that d is a key degree of (K( χ )|K, ν) if there exists a key polynomial of degree d. Assume that d is a key degree. If ν( χ d -K d-1 [ χ ]) has no maximal element, then we say that d is an immediate key degree. Otherwise, we say that d is an independent key degree. If this maximum does not belong to νK d-1 [ χ ], then we say that d is a valuational key degree. If this maximum belongs to νK d-1 [ χ ], then we say that d is a residual key degree.

Let d be a key degree. Then, by Proposition 1.9, d is an immediate key degree if, and only if, the extension [ χ ], ν) is vs defectless. However, we prefer to say that these degrees are independent because this word is easier to pronounce than vs defectless. We will see after Lemma 2.4 that this makes sense. Proposition 2.3. 1) The integer 1 is a key degree. Furthermore, every monic polynomial of degree 1 is a key polynomial.

(K d [ χ ]|K d-1 [ χ ],
2) Every w key polynomial is irreducible.

3) If ν is partially multiplicative and Φ is a w key polynomial (resp. a key polynomial) for ν of degree d, then, for every pm valuation ν such that the restriction of ν to K d-1 [ χ ] is equal to the restriction of ν and ν (Φ) ≥ ν(Φ), Φ is a w key polynomial (resp. a key polynomial) for ν . 4) Assume that ν is partially multiplicative. If Φ is a w key polynomial, then ν(Φ) ≥ {ν(r(f, g))ν(q(f, g))

| f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]}. If Φ is a monic polynomial, then Φ is a key polynomial if, and only if, ν(Φ) > {ν(r(f, g)) -ν(q(f, g)) | f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]}.
Proof. 1) and 3) are trivial.

2) Assume that there exist two polynomials f , g in K d-1 [ χ ] such that f g = Φ, then r(f, g) = 0, and ν(r(f, g)) = ∞ > ν(f g). Hence Φ is not a w key polynomial for ν.

4) Clearly, if Φ is a w key polynomial (resp. a key polynomial), then ν(Φ) ≥ {ν(r(f, g)) -

ν(q(f, g)) | f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]} (resp. ν(Φ) > {ν(r(f, g)) - ν(q(f, g)) | f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]}). Now, if ν(Φ) > ν(r(f, g)) - ν(q(f, g)), then ν(q(f, g)Φ) > ν(r(f, g)) = ν(f g -q(f, g)Φ). Hence ν(r(f, g)) = ν(f g).
The following lemma explains the distinction that we make between the valuational and the residual key degrees.

Lemma 2.4. Let d be a positive integer and Φ be a monic polynomial of degree d. Then ν(Φ) is the maximum of ν( χ [ χ ] we have ν(Φ + g) = min(ν(Φ), ν(g)). So the word independent key degree makes sense.

d -K d-1 [ χ ]) if, and only if, either ν(Φ) / ∈ νK d-1 [ χ ], or Φ ν(Φ),ν / ∈ (K d-1 [ χ ]) ν(Φ),ν . Proof. Assume that ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]) and ν(Φ) ∈ νK d-1 [ χ ]. Then, for every f ∈ K d-1 [ χ ] such that ν(f ) = ν(Φ) we have ν(Φ -f ) = ν(Φ) = ν(f ). Hence (Φ) ν(Φ),ν = f ν(Φ),ν . It follows that Φ ν(Φ),ν / ∈ (K d-1 [ χ ]) ν(Φ),ν . Conversely, assume that ν(Φ) / ∈ νK d-1 [ χ ], or Φ ν(Φ),ν / ∈ (K d-1 [ χ ]) ν(Φ),ν . Then for every g ∈ K d-1 [ χ ] we have ν(Φ-g) = min(ν(Φ), ν(g)) ≤ ν(Φ). Hence ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]). It follows that if (K d [ χ ]|K d-1 [ χ ], ν) is vs defectless, then any monic polynomial Φ, such that ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]), is valuation independent over K d-1 [ χ ] (i.e. for every g ∈ K d-1
Let Φ be a monic irreducible polynomial of K[X] of degree d ≥ 1 (K[X], the ring of formal polynomials with coefficients in K). Then K[X]/(Φ) is a field, such that the canonical epimorphism ρ

: K[X] → K[X]/(Φ) is an isomorphism from the K-module K d-1 [X] onto the K-module K[X]/(Φ). Now, for f, g in K d-1 [X],
we set f * g := r(f, g). Then ρ(f * g) = ρ(r(f, g)) = ρ(f g). Hence (K d-1 [X], +, * ) is a field which is isomorphic to K[X]/(Φ). The same operation can be defined in K [ χ ] whenever d ≤ [K( χ ) : K]/2. The field (K d-1 [ χ ], +, * ) will be denoted by K Φ . Note that if ν is a pm valuation on the field K( χ ), then its restriction to K d-1 [ χ ] induces a valuation of the K-modules K Φ and K[X]/(Φ). If Y is a root of Φ(X) in some algebraic extension, then the fields K Φ and K[Y] are isomorphic. Proposition 2.5. Let Φ be an irreducible monic polynomial of degree d, 1 ≤ d ≤ [K( χ ) : K]/2, and assume that ν is a pm valuation on K( χ ). Then Φ is a w key polynomial for ν if, and only if, the valued K-module

(K Φ , ν) is a valued field. Proof. Let f, g in K d-1 [ χ ]. Then ν(f * g) = ν(r(f, g)) and ν(f g) = ν(f ) + ν(g). Hence (K Φ , ν
) is a valued field if, and only if, for every f, g in K d-1 [ χ ] we have: ν(r(f, g)) = ν(f g). This in turn is equivalent to saying that Φ is a w key polynomial.

Corollary 2.6. Assume that ν is a pm valuation on K( χ ) and let Φ be a w key polynomial of degree d,

1 ≤ d ≤ [K( χ ) : K]/2. Then νK d-1 [ χ ] is a subgroup of νK( χ ).
Proof. Indeed, if Φ is a w key polynomial, then by Proposition 2.5 νK d-1 [ χ ] = νK Φ is a subgroup of νK( χ ).

Remark 2.7. Let Φ be a monic polynomial of degree d, 1 ≤ d ≤ [K( χ ) : K]/2, and assume that ν is a pm valuation on K( χ ).

1) The polynomial Φ is a key polynomial if, and only if, for every f , g in

K d-1 [ χ ], ν(f g) = ν(r Φ (f, g)) and (f g) ν(f g),ν = (r Φ (f, g)) ν(f g),ν . Indeed, if ν(f g) = ν(r Φ (f, g)), then ν(f g - r Φ (f, g)) > ν(f g) is equivalent to (f g) ν(f g),ν = (r Φ (f, g)) ν(f g),ν .
2) If Φ is a key polynomial, then the group

G ν (K d-1 [ χ ]) is a subalgebra of G ν (K( χ )). In- deed, if Φ is irreducible, then the group G ν (K d-1 [ χ ]) is isomorphic to the group G ν (K Φ ). Since (f g) ν(f g),ν = f ν(f ),ν g ν(g),ν
, Φ is a key polynomial if, and only if, for every f , g in

K d-1 [ χ ], (f * g) ν(f g),ν = f ν(f ),ν g ν(g),ν . Therefore, the group G ν (K Φ ) is a subalgebra of G ν (K( χ )).
3) It follows from 1) and Proposition 2.5 that if Φ is a key polynomial, then

K d-1 [ χ ] ν is a subfield of K( χ ) ν .
2.2. Pseudo-valuations. In [19], χ is transcendental over K and ν is a valuation or a pseudovaluation. A pseudo-valuation ν of K[ χ ] is a mapping from K[ χ ] onto a linearly ordered group ν(K [ χ ]) together with an element ∞ which shares the properties of multiplicative valuations except ν(f ) = ∞ ⇒ f = 0. In this case the set

I := {f ∈ K[ χ ] | ν(f ) = ∞} is a prime ideal of K[ χ ].
Then ν induces a pm valuation on the integral domain K[ χ ]/I. So, the case of algebraic extensions is obtained by means of a pseudo-valuation, by considering the quotient of K [ χ ] by the ideal

I := {f ∈ K[ χ ] : ν(f ) = ∞}.
Let Π be the monic polynomial which generates I. Since I is prime, Π is irreducible. If Φ is another irreducible polynomial, then Φ and Π are coprime. Hence there exist polynomials a and b in K [ χ ] such that deg(a) < deg(Φ), deg(b) < deg(Π) and aΠ -bΦ = 1. Then aΠ = bΦ + 1, with ν(aΠ) = ∞, hence ν(bΦ) = ν(1) = 0 < ν(aΠ). It follows that if deg(Π) < deg(Φ), then Φ is not a w key polynomial. Now, Π satisfies the properties of Definitions 2.2, but since the aim is to study the quotient K[ χ ]/I, we can restrict to polynomial of degrees less that deg(Π).

We generalize Definitions 2.2 to the case where ν is a pseudo-valuation by adding the hypothesis that d = deg(Π) < deg(Φ). In the case where ν is a pseudo-valuation, we also assume that χ is transcendental. The restriction of ν to K d-1 [ χ ] is a valuation, hence Proposition 2.3 remains true. In Lemma 2.4 we can also assume that ν is a pseudo-valuation by adding the condition ν(Φ) < ∞. The same holds for the other properties of Subsection 2.1, we only require that d < deg(Π).

More generally, all properties of Section 2 remain true with pseudo-valuations. Then we assume that the degrees are bounded by deg(Π) -1. In general, we replace d < [K [ χ ] : K] by d < deg(Π).

2.3.

Vs defectless valuations defined by key polynomials. Assume that Φ is a monic irreducible polynomial of degree d, and let γ be an element of an extension of νK ( χ ).

For every

f := f 0 + f 1 Φ + • • • + f m Φ m in K[ χ ] (with f 0 , f 1 , . . . , f m in K d-1 [ χ ] and deg(f m ) + dm < [K[ χ ] : K]), set ν (f ) = min 0≤i≤m ν(f i ) + iγ.
Assume that ν is a pm valuation on K( χ ) and that Φ is a w key polynomial for ν of degree d. We saw in Proposition 2.3 4) that the set {ν(r(f, g)) -ν(q(f, g))

| f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]} is bounded above by ν(Φ).
We extend the addition of elements of νK to the addition of Dedekind cuts in the usual way. Proposition 2.8. Let Φ be a monic irreducible polynomial of degree d, γ be an element of an extension of νK( χ ), and ν be defined as above.

1) The application ν is a K-module valuation and the family

(Φ m ) (dm < [K[ χ ] : K]) is separated over K d-1 [ χ ].
2) Assume that ν is a pm valuation and that Φ is a w key polynomial for ν. Denote by β the upperbound of the set {ν(r(f, g)

) -ν(q(f, g)) | f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]} in a Dedekind completion of νK, and assume that γ ≥ β. a) For every f = f m Φ m + • • • + f 1 Φ + f 0 , g = g m Φ m + • • • + g 1 Φ + g 0 , with f 0 , . . . , f m , g 0 , . . . , g m in K d-1 [ χ ] such that deg(f ) + deg(g) < [K[ χ ] : K] we have: ν (f g) = ν   2m j=0 j i=0 r(f i , g j-i ) Φ j   ≤ ν   f g - 2m j=0 j i=0 r(f i , g j-i ) Φ j   -(γ -β).
(Here if i > m, then we let f i = g i = 0.) In particular, ν is a pm valuation. b) The polynomial Φ is a w key polynomial such that the sequence [ χ ]. Furthermore it is a key polynomial if, and only if, γ > β or β is not a maximum.

(Φ m ) (md < [K( χ ) : K]) is ν -separated over K d-1
Proof. The proof is left to the reader (see for example [START_REF] Leloup | Key polynomials, separate and immediate valuations, and simple extensions of valued fields[END_REF]).

Notations 2.9. The K-module valuation ν defined in Proposition 2.8 will be denoted by ν Φ,γ . We set ν Φ = ν Φ,ν(Φ) . If Φ 1 and Φ 2 are irreducible polynomials such that deg(Φ 1 ) < deg(Φ 2 ), then we denote by ν Φ1,Φ2 the K-module valuation (ν Φ1,ν(Φ1) ) Φ2,ν(Φ2) . By induction, for every irreducible polynomials Φ 1 , . . . , Φ n , with deg(Φ 1 ) < • • • < deg(Φ n ), we define the K-module valuation ν Φ1,...,Φn .

These valuations ν Φ generalize the augmented valuations of S. MacLane ( [START_REF] Maclane | A construction for absolute values in polynomials rings[END_REF] and [15]).

If the degree of Φ is 1, then for every f ,

g in K d-1 [ χ ] = K, we have q(f, g) = 0. Hence the set {ν(r(f, g)) -ν(q(f, g)) | f ∈ K d-1 [ χ ], g ∈ K d-1 [ χ ], deg(f ) + deg(g) < [K[ χ ] : K]} is equal to {-∞}
and is bounded above by any element. Hence Proposition 2.8 proves the fact that the valuations defined in Example 1.5 are pm valuations.

Proposition 2.10. Let Φ be a monic polynomial of degree d < [K( χ ) : K] and assume that ν is a pm valuation on K [ χ ]. Then Φ is a w key polynomial for ν if, and only if, there exists a pm valuation ν of K [ χ ], such that its restriction to K d-1 [ χ ] is equal to the restriction of ν, and ν (Φ) > ν(Φ). If this holds, then for every γ ≥ ν(Φ) in an extension of νK [ χ ], ν Φ,γ is a pm valuation of K [ χ ] such that its restriction to K d-1 [ χ ] is equal to the restriction of ν, ν Φ,γ (Φ) = γ and Φ is a w key polynomial for ν Φ,γ such that the sequence

(Φ m ) (md < [K( χ ) : K]) is separated over K d-1 [ χ ].
Proof. Assume that ν is a pm valuation of K [ χ ] such that its restriction to K d-1 [ χ ] is equal to the restriction of ν, and

ν (Φ) > ν(Φ). Let f , g in K d-1 [ χ ] such that deg(f ) + deg(g) < [K[ χ ] : K],
q = q(f, g) and r = r(f, g). Without loss of generality we can assume that q = 0. We have ν(

f g) = ν(f ) + ν(g) = ν (f ) + ν (g) = ν (f g). Therefore, ν(qΦ + r) = ν (qΦ + r
) is greater or equal to both of min(ν(qΦ), ν(r)) and min(ν (qΦ), ν(r)), where ν(qΦ) = ν(q) + ν(Φ) < ν (q) + ν (Φ) = ν (qΦ). It follows that ν(f g) = ν(r) = ν(qΦ) < ν (qΦ). Now, if Φ is a w key polynomial for ν, then we can take ν as in Proposition 2.8 2).

The last assertion also follows from Proposition 2.8.

If ν and ν are K-module valuations on K( χ ), then we set ν ≤ ν if for every f ∈ K [ χ ] we have ν(f ) ≤ ν (f ).

Remark 2.11. 1) By the definition of ν Φ , for every K-module valuation ν such that the restrictions of ν and ν Φ to K d-1 [ χ ] are equal and ν (Φ) = ν φ (Φ), we have ν Φ ≤ ν . 2) Assume that χ is algebraic over K, that ν is multiplicative, and ν (f

) < ν(f ). If ν ≤ ν, then ν (1/f ) ≤ ν(1/f ) = -ν(f ) < -ν (f ). Hence ν (1/f ) = -ν (f ).
It follows that ν is not multiplicative. Hence we cannot improve the conclusion that ν is partially multiplicative in Proposition 2.8.

In valuation theory, we say that ν is finer than ν if ∀x ν (x) ≥ 0 ⇒ ν(x) ≥ 0 (see [18, p. 54]). Assume that χ is algebraic over K. Then K( χ ) = K [ χ ], so, if ν ≤ ν, then ν is finer than ν. Now, any two distinct extensions of a valuation to an algebraic extension are incomparable (see [START_REF] Ribenboim | Théorie des valuations L,es Presses de l'université de Montréal[END_REF]Corollaire 5,p. 158 ]). Therefore, this also proves that if ν = ν, then ν or ν is not multiplicative. In the case where χ is transcendental over K and ν, ν are valuations such that ν ≤ ν, then we cannot deduce that ν and ν are comparable in the sense of Ribenboim. Indeed, assume that

ν(f ) = ν (f ) = ν (g) < ν(g). Then, ν (f /g) = 0 > ν(f /g). Assume that ν (f ) < ν(f ) = ν(g) = ν (g). Then ν (f /g) < 0 = ν(f /g).
Proposition 2.12. Assume that ν is a pm valuation on K [ χ ], and let Φ be a non constant monic polynomial in

K[ χ ] of degree d < [K( χ ) : K].
Then Φ is a w key polynomial for ν if, and only if, there exists a pm valuation ν ≤ ν such that the restrictions of ν and ν to K d-1 [ χ ] are equal, and Φ is a w key polynomial for ν such that the sequence [ χ ]. Furthermore, we can take ν = ν Φ .

(Φ m ) (md < [K( χ ) : K]) is separated over K d-1
Proof. ⇐. If Φ is a w key polynomial for ν , then, by 3) of Proposition 2.3, it is a w key polynomial for ν.

⇒. By Proposition 2.10, ν Φ is a pm valuation such that Φ is a w key polynomial for ν Φ such that the sequence (Φ m ) (md < [K( χ ) : K]) is separated over K d-1 [ χ ]. By construction, the restrictions of ν and ν Φ to K d-1 [ χ ] are equal. By Remark 2.11 1) we have ν Φ ≤ ν.

Thanks to the mappings ν Φ we get useful criteria for being a w key polynomial or a key polynomial, as show the following propositions. We start with a lemma.

Lemma 2.13. Assume that ν is a pm valuation. Let d < [K[ χ ] : K] in N\{0}, d := [K[ χ ] : K] -d, Φ be a non constant monic polynomial in K[ χ ] of degree d. We also assume that for every f , g in K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K] and every h in K d -1 [ χ ], we have ν(f g + hΦ) = min(ν(f g), ν(hΦ)). Then Φ is a w key polynomial such that the sequence (Φ m ) (md < [K( χ ) : K]) is separated over K d-1 [ χ ]. In particular, ν = ν Φ . Proof. By setting h = -q Φ , we have ν(r Φ ) = ν(f g -q Φ Φ) = min(ν(f g), ν(q Φ Φ)) ≤ ν(f g). By setting f = r Φ , g = 1 and h = q Φ , we get ν(f g) = ν(r Φ + q Φ Φ) = min(ν(r Φ ), ν(q Φ Φ)) ≤ ν(r Φ ). Thefore ν(f g) = ν(r Φ ). Hence Φ is a w key polynomial. Now, let m ∈ N\{0} with dm < [K[ χ ] : K], f 0 , . . . , f m in K d-1 [ χ ]. We have: ν(f m Φ m + • • • + f 0 ) = min(ν((f m Φ m-1 + • • • + f 1 )Φ), ν(f 0 )), ν(f m Φ m-1 + • • • + f 1 ) = min(ν((f m Φ m-2 + • • • + f 2 )Φ), ν(f 1 )
), and so on. So by induction we have

ν(f m Φ m + • • • + f 0 ) = min(ν(f m Φ n-1 ), . . . , ν(f 0 )). Hence the family (Φ m ) (md < [K( χ ) : K]) is separated over K d-1 [ χ ].
Proposition 2.14. Let ν, ν be pm valuations on K( χ ), and Φ be a monic polynomial of degree

d, 1 ≤ d < [K( χ ) : K]. Assume that their restrictions to K d-1 [ χ ] are equal, that ν ≤ ν and ν (Φ) < ν(Φ). 1) Let f ∈ K[ χ ] and f = qΦ + r be the euclidean division of f by Φ. Then ν (f ) < ν (r) ⇔ ν (f ) < ν(f ) and ν (f ) = ν (r) ⇔ ν (f ) = ν(f ).
2) Φ is a w key polynomial for ν and a key polynomial for ν.

3) ν = ν Φ = ν Φ,ν (Φ) . Proof. 1) We have ν (r) = ν(r) and ν (qΦ) < ν(qΦ). Assume that ν (r) ≤ ν (qΦ). Then ν(f ) = min(ν(qΦ), ν(r)) = ν(r). Furthermore, ν(f ) ≥ ν (f ) ≥ min(ν (qΦ), ν(r)) ≥ ν(r) = ν(f ). Hence ν (f ) = ν(f ) = ν(r). Assume that ν (qΦ) < ν(r) < ν(qΦ). Hence ν (f ) = min(ν (qΦ), ν (r)) = ν (qΦ) < ν (r) = min(ν(qΦ), ν(r)) = ν(f ). Assume that ν(qΦ) ≤ ν(r).
Then ν (f ) = min(ν (qΦ), ν (r)) = ν (qΦ) < ν(qΦ) = min(ν(qΦ), ν(r)) ≤ ν(f ), and ν (f ) < ν (r).

2

) Let f , g in K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K]. Since deg(f ) < deg(Φ) and deg(g) < deg(Φ), we have: ν (f ) = ν(f ) and ν (g) = ν(g), therefore: ν (f g) = ν (f ) + ν (g) = ν(f ) + ν(g) = ν(f g). By 1) this implies ν (f g) = ν (r(f, g))
and Φ is a w key polynomial for ν . Since the restrictions of ν and ν to K d-1 [ χ ] are equal, it follows that Φ is also a w key polynomial for ν. Now, for f ,

g in K d-1 [ χ ] we have ν(r(f, g)) = ν (r(f, g)) ≤ ν (q(f, g)•Φ) < ν(q(f, g)•Φ).
Hence Φ is a key polynomial for ν.

3) First we prove that for every f ,

g in K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K] and h ∈ K[ χ ] such that deg(h) < [K[ χ ] : K] -d we have: ν (f g + hΦ) = min(ν (f g), ν (hΦ)). If ν (f g) = ν (hΦ),
then the result is trivial. Assume that ν (f g) = ν (hΦ), and let q = q(f, g), r = r(f, g). Since Φ is a w key polynomial for ν , we have ν

(f g) = ν (r). Hence ν (f g + hΦ) ≥ ν (r). Since ν ≤ ν, we have ν (f g + hΦ) ≤ ν(f g + hΦ). Note that f g + hΦ = (q + h)Φ + r. So by 1), ν ((q + h)Φ + r) < ν((q + h)Φ + r) ⇔ ν ((q + h)Φ + r) < ν (r): a contradiction. Hence ν (f g + hΦ) = ν(f g + hΦ). We have also ν(f g) = ν (f g) = ν (hΦ) < ν(hΦ), hence ν(f g + hΦ) = ν(f g) = ν (f g) = min(ν (f g), ν (hΦ))
. By Lemma 2.13 we have ν = ν Φ . Now, since ν and ν coincide on K d-1 [ χ ] we have ν Φ = ν Φ,ν (Φ) .

Remark 2.15. We deduce from Proposition 2.14 that if ν is a valuation on K( χ ), then every pm valuation ν ≤ ν, ν = ν, which coincide on K with ν, can be written as ν = ν Φ,ν (Φ) where Φ is a monic polynomial of minimal degree such that ν (Φ) < ν(Φ). This completes Proposition 2.10. Proposition 2.16. Let ν be a pm valuation on K( χ ), Φ be a w key polynomial for ν and Φ be a monic polynomial such that [ χ ]. Let q := q(f, g) and r := r(f, g); since f and g belong to K d-1 [ χ ], we have deg(q) < d, i.e. q ∈ K d-1 [ χ ]. We have: ν(f g + hΦ) = ν(h m Φ m+1 + • • • + h 1 Φ 2 + (q + h 0 )Φ + r) = min(ν(h n Φ m+1 ), . . . , ν(h 1 Φ 2 ), ν((q + h 0 )Φ), ν(r)). Since Φ is a w key polynomial, we have ν(f g) = ν(r) ≤ ν(qΦ). If ν(h 0 Φ) ≥ ν(r), then ν((q + h 0 )Φ) ≥ ν(r). Hence min(ν((q + h 0 )Φ), ν(r)) = ν(r) = min(ν(h 0 Φ), ν(r)). If ν(h 0 Φ) < ν(r), then min(ν((q + h 0 )Φ), ν(r)) = ν(h 0 Φ) = min(ν(h 0 Φ), ν(r)). Therefore: ν(f g + hΦ) = min(ν(h m Φ m+1 ), . . . , ν(h 1 Φ 2 ), ν(h 0 Φ), ν(f g)) = min(ν(hΦ), ν(f g)).

d = deg(Φ) < deg(Φ ) = d < [K( χ ) : K]. K d-1
We use the hypothesis "ν is a pm valuation" for proving 2) ⇒ 1). For proving 2) ⇒ 3) the condition "for every f ∈ K d -1 [ χ ], ν(Φf ) = ν(Φ) + ν(f )" is sufficient. The remainder of the proof remains true with a K-module valuation. Proposition 3.1 shows that the definition of MacLane is stronger than the definition of w key polynomials. Now, we extend the definition of S. MacLane to K-module valuations. Definition 3.2. Let Φ be a polynomial of degree d. We say that Φ is a ML key polynomial for ν if Φ is a w key polynomial such that the sequence (Φ m ) (md

< [K( χ ) : K]) is separated over K d-1 [ χ ].
If ν is a pm valuation, then it follows from Proposition 2.8 that Φ is a ML key polynomial for ν if, and only if, Φ is a w key polynomial for ν and ν = ν Φ . This shows the difference between w key polynomials and MacLane key polynomials.

Properties of key degrees

In this section, we list some properties of key degrees. In particular, we give sufficient conditions for existing a finite number of key degrees and a characterization of the successor of a key degree. This characterization takes place in the construction of complete families of key polynomials. In this construction, in the case of an independent key degree, we will choose monic polynomials with maximal valuation. However, the fact that the degree d of a key polynomial is independent does not imply that its valuation is maximal in ν( χ d -K d-1 [ χ ]). Indeed, we saw in Proposition 2.3 1) that every monic polynomial of degree 1 is a key polynomial. This holds whether 1 is an independent key degree or not.

Except for Proposition4.7, all properties of this section remain true if ν is a pseudo-valuation (and χ is transcendental). In this case we assume that the degrees are lower than the degree of a generator of the ideal {f ∈ K [ χ ] : ν(f ) = ∞} (in the settings, we can take d < [K [ χ ] : K] in place of d < deg(Π)).

4.1. Independent key degrees. We start this subsection with some observations about monic polynomials with maximal valuations. Proposition 4.1. Let d be an integer and ν be a pm valuation on K [ χ ]. 1) Let Φ be a w key polynomial of degree d. Then every monic polynomial Φ of degree d, such that ν(Φ ) > ν(Φ), is a key polynomial. Therefore, if d is not a key degree, then ν

(Φ) is maximal in ν( χ d -K d-1 [ χ ]).
2) Assume that d is an independent key degree and let Φ be a key polynomial of degree d. Then every monic polynomial Φ of degree d, such that ν(Φ ) ≥ ν(Φ), is a key polynomial. In particular, any monic polynomial

Φ of degree d, such that ν(Φ ) is maximal in ν( χ d -K d-1 [ χ ]), is a key polynomial.
This proposition is a consequence of the following lemma. Lemma 4.2. Let d be a positive integer, ν be a pm valuation on K [ χ ], Φ and Φ be monic polynomials of degree d such that Φ is a w key polynomial for ν. 1) If ν(Φ ) > ν(Φ), then Φ is a w key polynomial for ν Φ , a key polynomial for ν, and ν Φ ≤ ν Φ .

2) If ν(Φ ) = ν(Φ) and Φ is a key polynomial for ν, then Φ is a key polynomial for both of ν and ν Φ . Furthermore, ν Φ = ν Φ .

3) If ν(Φ ) = ν(Φ) and Φ, Φ are w key polynomials for ν, then ν Φ = ν Φ .

Proof. Set h = Φ -Φ. Assume that ν(Φ ) ≥ ν(Φ). Then we have ν(h) ≥ ν(Φ). Furthermore, Φ and Φ are monic polynomials, so the degree of h is lower than d.

Now, Φ = Φ + h, hence ν Φ (Φ ) = min(ν(Φ), ν(h)) = ν(Φ). Let f , g in K d-1 [ χ ] with deg(f ) + deg(g) < [K[ χ ] : K]. We have: ν Φ (f g) = ν Φ (f ) + ν Φ (g) = ν(f ) + ν(g) = ν(f g). Let r = r Φ (f, g), q = q Φ (f, g).
1) Since ν(Φ ) > ν(Φ), we have ν(h) = ν(Φ) (= ν Φ (Φ )). In order to get a contradiction, assume that ν Φ (q Φ ) < ν Φ (r ) (= ν(r )). Then ν Φ (f g) = ν Φ (q Φ + r ) = ν Φ (q Φ ) = ν(q Φ) = ν Φ (q Φ). Now, ν(q Φ ) > ν(q Φ) = ν(f g) and ν(r ) > ν Φ (q Φ ) = ν Φ (f g) = ν(f g). Hence ν(f g) ≥ min(ν(q Φ ), ν(r )) > ν(f g): a contradiction. Therefore, ν Φ (q Φ ) ≥ ν Φ (r ). Now, ν(r ) = ν Φ (r ) and ν Φ (q Φ ) = ν(q Φ) < ν(q Φ ). Hence Φ is a key polynomial for ν (so ν(f g) = ν(r )). Since ν Φ (f g) = ν(f g) = ν(r ) = ν Φ (r ), Φ is a w key polynomial for ν Φ . Furthermore, ν Φ and ν Φ are equal on K d-1 [ χ ], and

ν Φ (Φ) = ν Φ (Φ -h) = min(ν Φ (Φ ), ν Φ (h)) = min(ν(Φ ), ν(h)) = ν(h) = ν(Φ) = ν Φ (Φ). By Remark 2.11, we have ν Φ ≤ ν Φ .
2) We assume that ν(Φ ) = ν(Φ) and Φ is a key polynomial for ν. Let q 1 = q Φ (q , h) and r 1 = r Φ (q , h). Since Φ is a key polynomial for ν, we have ν(q 1 Φ) > ν(r 1 ) = ν(q h) ≥ ν(q Φ). Hence ν(q ) < ν(q 1 ) and ν(q + q 1 ) = ν(q ). We have: f g = q Φ + r = q Φ + q h + r = (q + q 1 )Φ + r + r 1 , hence q + q 1 = q Φ (f, g), r + r 1 = r Φ (f, g) and ν(f g) = ν(r + r 1 ) < ν((q + q 1 )Φ) = ν(q Φ) ≤ ν(r 1 ). It follows: ν(r + r 1 ) = ν(r ), so ν(f g) = ν(r ) < ν(q Φ) = ν(q Φ ). This proves that Φ is a key polynomial for ν. Now, ν Φ (f g) = ν(f g) = ν(r ) = ν Φ (r ) and ν Φ (q Φ ) = ν Φ (q Φ) = ν(q Φ) > ν(r ). Hence Φ is a key polynomial for ν Φ . In the same way as in 1), we have: ν Φ ≤ ν Φ . Now, since Φ is a key polynomial, we have in a symmetric way: ν Φ ≤ ν Φ .

3) We assume that ν(Φ ) = ν(Φ) and Φ, Φ are w key polynomials for ν. We have:

Φ = Φ + h, with ν(h) ≥ ν(Φ) and deg(h) < d. Hence ν Φ (Φ ) = min(ν(Φ), ν(h)) = ν(Φ) = ν(Φ ) = ν Φ (Φ ). So by Remark 2.11 we have: ν Φ ≤ ν Φ . In the same way, ν Φ ≤ ν Φ , hence ν Φ = ν Φ .
The following proposition gives a characterization of valuational key degrees by means of νK d-1 [ χ ].

if, νK d-1 [ χ ] is a group and νK d [ χ ] = νK d-1 [ χ ]. If this holds, then every monic polynomial Φ of degree d such that ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]) (which is equivalent to saying that ν(Φ) / ∈ νK d-1 [ χ ]
) is a key polynomial.

Proof. ⇒ follows from the definition and Corollary 2.6. Assume that νK d-1 [ χ ] is a group and νK d [ χ ] = νK d-1 [ χ ]. By hypothesis, there is a polynomial Φ of degree d such that ν(Φ) / ∈ νK d-1 [ χ ]. Since νK d-1 [ χ ] is a group, by dividing Φ by an element of K we can assume that Φ is a monic polynomial [ χ ]. Hence ν(f g) = ν(qΦ). So, ν(qΦ) > ν(r). This proves that Φ is a key polynomial. Since ν(φ) is the maximum of ν( χ d -K d-1 [ χ ]), d is an independent key degree. Therefore it is a valuational key degree.

. Let f ∈ K d-1 [ χ ]. Then ν(f ) = ν(Φ). Hence ν(Φ -f ) = min(ν(Φ), ν(f )) ≤ ν(Φ). Consequently, ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]). Let f , g in K d-1 [ χ ], q = q Φ (f, g) and r = r Φ (f, g). Since ν(qΦ) / ∈ νK d-1 [ χ ], we have that ν(qΦ) = ν(r). Hence ν(f g) = min(ν(qΦ), ν(r)). Now, since νK d-1 [ χ ] is a group, ν(f g) = ν(f ) + ν(g) ∈ νK d-1

4.2.

Maximal key degrees. If χ is algebraic over K, then there is a finite number of key degrees. We saw that if ν is a pseudo-valuation, then the degrees of the key polynomials are bounded by the degree of a generator of the ideal of elements with infinite valuation. We give sufficient conditions for a key degree being the maximal one. We start with a lemma. Lemma 4.5. Let ν be a pm valuation on K [ χ ] and Φ be a monic polynomial of degree d. Then,

ν = ν Φ on K d [ χ ] if, and only if, ν(Φ) = max ν( χ d -K d-1 [ χ ]).
1) d is an immediate key degree for ν, Φ is a w key polynomial for ν and ν , and ν = ν Φ .

2) The Φ i 's are key polynomials for ν, and for every f ∈ K [ χ ] the sequence (ν Φi (f )) is eventually equal to ν(f ).

3) The extension (K

[ χ ]|K d-1 [ χ ], ν) is dense. 4)
There is no key degree greater than d.

Proof. 1) By Proposition 2.14, Φ is a w key polynomial for ν , ν = ν Φ , and Φ is a key polynomial for ν. Hence d is a key degree for ν. Since ν( χ

d -K d-1 [ χ ]) = νK[ χ ], d is an immediate key degree. 2) Since deg(Φ i -Φ) < d, we have ν(Φ i -Φ) = ν (Φ i -Φ), and ν (Φ i ) = ν Φ (Φ i ) = ν Φ (Φ+Φ i -Φ) = min(ν (Φ), ν (Φ i -Φ)) = min(ν (Φ), ν(Φ i -Φ)) = min(ν (Φ), ν(Φ)) = ν (Φ) < ν(Φ) < ν(Φ i )
. By Proposition 2.14, Φ i is a key polynomial for ν. We have also: ν = ν Φi . Let f ∈ K [ χ ], k be the quotient of the euclidean division of deg(f ) by d, λ = ν (f ) -kν (Φ), and i be such that ν

(Φ i ) > max(ν(f ) -λ, ν(f )). Decompose f as f = f i,k Φ k i + • • • + f i,1 Φ i + f i,0 , where the f i,j 's belong to K d-1 [ χ ]. Then ν (f ) = ν Φi (f ) = min(ν (f i,j Φ j i ))
. Therefore, for every j we have:

ν(f i,j ) = ν (f i,j ) ≥ ν (f ) -jν (Φ i ) ≥ ν (f ) -kν (Φ i ) = ν (f ) -kν (Φ) = λ. Then for every j we have ν(f i,j Φ j i ) = ν(f i,j ) + jν(Φ i ) > λ + j max(ν(f ) -λ, ν(f )). If j ≥ 1, then ν(f i,j Φ j ) > ν(f ). It follows that ν(f ) = ν(f i,0 ) = ν Φi (f ). This proves that the sequence (ν Φi (f )) is eventually equal to ν(f ). 3) If ν(Φ i ) > max(ν(f ) -λ, ν(f )), then ν(f -f i,0 ) = ν   k j=1 f i,j Φ j i   ≥ min 1≤j≤k (ν(f i,j ) + jν(Φ i )) ≥ λ + ν(Φ i ) is cofinal in νK[ χ ], since the sequence (ν(Φ i )) is. It follows that (K[ χ ]|K d-1 [ χ ], ν) is dense. 4)
Let f be a monic polynomial of degree d > d. Then, there exists i such that ν(f ) = ν Φi (f ). By Proposition 2.16 1), f is not a key polynomial for ν. Hence d is not a key degree. 4.3. Successors of key degrees. The following two theorems characterize the successor of a key degree. They will be useful for proving the equivalence of the definitions of key polynomials and abstract key polynomials. They are also involved in the construction of complete families of key polynomials.

Theorem 4.9. Let ν be a pm valuation on K( χ ), d be an immediate key degree, and let (Φ i ) be a sequence of key polynomials of degree d such that the sequence (ν(Φ i )) is increasing and cofinal in ν( χ d -K d-1 [ χ ]). Then. 1) The sequence (ν Φi ) converges to ν on K d [ χ ] in the sense that for every f ∈ K d [ χ ] the sequence (ν Φi (f )) is eventually equal to ν(f ).

2) Let d be the smallest degree (if any) such that there exists a monic polynomial Φ of degree d satisfying ν Φi (Φ ) < ν(Φ ) for every i. Then, Φ is a key polynomial and d is the next key degree.

3) The extension

(K d -1 [ χ ]|K d-1 [ χ ], ν) is immediate.
Proof. 1) The family (ν Φi ) is increasing, and for every f ∈ K [ χ ] we have ν Φi (f ) ≤ ν(f ). Assume that f is a polynomial of degree d. Without loss of generality we can assume that f is monic. Since the sequence (ν

(Φ i )) is cofinal in ν( χ d -K d-1 [ χ ]), there is an i such that ν(Φ i ) > ν(f ). Now, for eve- ry i such that ν(Φ i ) > ν(f ) we have ν(f -Φ i ) = ν(f ), and ν Φi (f ) = min(ν(Φ i ), ν(f -Φ i )) = ν(f ). 2) Let f , g in K d -1 [ χ ] with deg(f ) + deg(g) < [K[ χ ]
: K] and q = q Φ (f, g), r = r Φ (f, g). By hypothesis there exists i such that ν Φi (f ) = ν(f ), ν Φi (g) = ν(g), ν Φi (q) = ν(q) and ν Φi (r) = ν(r). Then ν(qΦ + r) = ν(f g) = ν(f ) + ν(g) = ν Φi (f ) + ν Φi (g) = ν Φi (f g) = ν Φi (qΦ + r), with ν(qΦ ) > ν Φi (qΦ ). Assume that ν(qΦ ) ≤ ν(r). Hence ν Φi (qΦ ) < ν(r) = ν Φi (r), and ν(f g) = ν Φi (f g) = ν Φi (qΦ ) < ν(qΦ ) = min(ν(qΦ ), ν(r)) ≤ ν(f g): a contradiction. Hence ν(qΦ ) > ν(r), which proves that Φ is a key polynomial for ν. Let f be a monic polynomial of degree d < d . Then, there exists i such that ν(f ) = ν Φi (f ). By Proposition 2.16 1), f is not a key polynomial.

3) Let f be a monic polynomial of degree n, d < n ≤ d -1. We show that ν(f ) is not the maximum of ν( χ n -K n-1 [ χ ]). It will follow by Proposition 1.9 1) that the extension (K d -1 [ χ ]|K d-1 [ χ ], ν) is immediate. Let Φ i be a w key polynomial of degree d such that ν(f ) = ν Φi (f ), and let f be written as f = f k Φ k i + • • • + f 1 Φ i + f 0 , where f 0 , f 1 , . . . , f k belong to K d-1 [ χ ], f k is monic, and For every k, m 1 , . . . , m k , we let ν (m1,...,m k ) = ν Φ d 1,m 1 ,...,Φ d k,m k (see Notations 2.9 and Remark 4.11). Then F is a complete family of key polynomials. Furthermore, for every f , there are infinitely many (m 1 , . . . , m k )'s such that (ν (m1,...,m k ) (f )) = ν(f ).

Proof. Note that, for every k, m 1 , . . . , m k , we have ν (m1,...,m k ) ≤ ν. Let f ∈ K [ χ ] and d k be the greatest key degree such that the degree of f is at least equal to d k . By Theorems 4.10 and 4.9, there exists m k such that ν(f ) = ν Φ d k ,m k (f ). Furthermore, since the family (ν

Φ d k ,m k ) is increasing, we have m k ≥ m k ⇒ ν Φ d k ,m k (f ) = ν(f ). Let f = f j Φ j d k ,m k + • • • + f 1 Φ d k ,m k + f 0
, where f 0 , f 1 , . . . , f j belong to K d k -1 [ χ ]. We know that there is some m k-1 such that ν(f 0 ) = ν Φ d k-1 ,m k-1 (f 0 ), . . . , ν(f j ) = ν Φ d k-1 ,m k-1 (f j ). Then, ν(f ) = ν Φ d k-1 ,m k-1 ,Φ d k ,m k (f ). So by induction we get a k-uple (m 1 , . . . , m k ) such that ν(f ) = ν (m1,...,m k ) (f ). Now, we can do the same construction with any m k ≥ m k , which proves that there are infinitely many such k-uples.

Abstract key polynomials

In this section χ is assumed to be transcendental over K. The mapping ν is a valuation or a pseudo-valuation. If ν is a pseudo-valuation, then we assume that the degrees of Φ and Φ are lower than the degree of a generator of the ideal {f ∈ K [ χ ] : ν(f ) = ∞}. Our goal is to prove that our definition of key polynomials is equivalent to the definition of abstract key polynomials.

We start with some notations. Let f be a polynomial degree of n. For 1 ≤ i ≤ n, set f (i) = (1/i!) f (i) , where f (i) is the i-th formal derivative of f . If the characteristic of K is p > 0, then we do not replace p•x by 0; the simplification holds, if necessary, after the division by i!. For example, if f (X) = X p , then we have f (1) (X) = pX p-1 = 0, and f (p) (X) = (1/p!)•p! = 1.

For any polynomial f , let ε µ (f ) be the maximum of the set

ν(f ) -ν(f (i) ) i | i ∈ N\{0} .
We say that Φ is an abstract key polynomial (or a key polynomial) for ν if it is monic and for every f ∈ K [ χ ] such that ε ν (f ) ≥ ε ν (Φ) we have deg(f ) ≥ deg(Φ) ([5]). The converse is a consequence of the following theorem. In this theorem for a key polynomial Φ we let (Φ) := {f ∈ K[ χ ] | f is monic , ν Φ (f ) < ν(f )}, and (Φ) be the subset of elements of (Φ) with minimum degree.

Theorem 5.4. ([17, Theorem 2.12]) Let Φ be a monic polynomial. Then Φ is an abstract key polynomial if, and only if, there exists an abstract key polynomial Φ -such that: either a) Φ belongs to (Φ -), or b) i) the elements in (Φ -) have the same degree as Φ -, ii) the set of valuations of all elements in (Φ -) has no maximum element, iii) for every Φ in (Φ -), ν Φ (Φ) < ν(Φ), iv) the degree of Φ is minimum among the degrees of polynomials satisfying iii).

Corollary 5.5. The key polynomials as defined in Definitions 2.2 are abstract key polynomials.

Proof. We prove this by induction on the degrees. By Proposition 2.3 1) and Remark 5.1 this is true for polynomials of degree 1. Let Φ be a key polynomial of degree d > 1, and assume that every key polynomial of degree less that d is an abstract key polynomial. We denote by d te preceding key degree. If d is an independent key degree, then by a) of Theorem 5.4 and Theorem 4.10, Φ is an abstract key polynomial. If d is an immediate key degree, then by b) of Theorem 5.4 and Theorem 4.9, Φ is an abstract key polynomial.

Proposition 4 . 3 .

 43 Let ν be a pm valuation on K[ χ ] and d be a positive integer such that 1 ≤ d ≤ [K( χ ) : K]/2. Then, d is a valuational key degree if, and only

Corollary 4 . 4 .

 44 Let ν be a pm valuation on K[ χ ] and d be a positive integer. Assume that νK d-1[ χ ] is a group and let d be the smallest integer such that νK d [ χ ] = νK d-1[ χ ] (if any). Then d is a valuational key degree. In particular, the smallest degree d such that νK d[ χ ] = νK (if any) is a valuational key degree.

Theorem 4 . 12 .

 412 Let ν be a pm valuation on K( χ), 1 = d 1 < d 2 < • • • < d k < • • •be the sequence of key degrees of ν and F be a family of key polynomials for ν which satisfies the following properties for every k ≥ 1. If d k is an independent key degree, then F contains exactly one key polynomial Φ d k of degree d k , and ν(Φd k ) = max(ν( χ d k -K d k -1 [ χ ])). For notational convenience, for every integer m we setΦ d k ,m = Φ d k .If d k is an immediate key degree, then the key polynomials of degree d k of F form a sequence (Φ d k ,m ) such that the sequence (ν(Φ d k ,m )) is increasing, cofinal in ν( χ d k -K d k -1[ χ ]).

Remark 5 . 1 .

 51 [START_REF] Novakoski | Key polynomials and pseudo-convergent sequences[END_REF] Remark 2.1]) The monic polynomials of degree 1 are abstract key polynomials. Proposition 5.2. ([17, Lemma 2.3 (iii)]) Let Φ be an abstract key polynomial for ν, h 1 , . . . , h s be polynomials with degrees less than deg(Φ) and q be the quotient of the euclidean division of

Corollary 5 . 3 .

 53 The abstract key polynomials are key polynomials as defined in Definitions 2.2.

  |M, ν) is immediate if, and only if, νN = νM and, for every γ ∈ νM , N γ,ν = M γ,ν . 2) (N |K, ν) is immediate if, and only if, νN = νK and N ν = K ν .

	Remark 1.3. .
	1) (N

  ν) is immediate and by Proposition 1.15, d is a vs defectless key degree if, and only if, the extension (K d [ χ ]|K d-1

Proof. By the definition of ν Φ , ν and ν Φ are equal on K d-1 [ χ ]. Hence, we can consider polynomials of degree d. So, we let f be a polynomial of degree d. Without loss of generality we can assume that f is a monic polynomial. Hence f -Φ has degree less than Φ. Assume that ν(f ) = ν Φ (f ). Then ν(f ) = ν Φ (Φ + f -Φ) = min(ν(Φ), ν(f -Φ)) ≤ ν(Φ). This proves that ν(Φ) is the maximum of ν( χ d -K d-1 [ χ ]). Conversely, assume that ν(Φ) = max ν( χ d -K d-1 [ χ ]). We have ν(f -Φ) ≥ min(ν(f ), ν(Φ)) = ν(f ). Therefore, ν(f ) ≥ ν Φ (f ) = ν Φ (Φ + f -Φ) = min(ν(Φ), ν(f -Φ)) ≥ ν(f ). Hence ν Φ (f ) = ν(f ).

Remark 4.6. Let d be a positive integer, ν be a pm valuation on K [ χ ]. 1) It follows from Proposition 2.16 that if ν = ν Φ for some w key polynomial Φ, then there is no key degree greater than d.

2) Assume that d is an independent key degree such that there is no key degree greater than d, and Φ is a key polynomial of degree d, with ν(Φ) = max(ν( χ d -K d-1 [ χ ])). By Lemma 4.5, ν and ν Φ coincide on K d [ χ ]. Now, by Proposition 2.16, ν = ν Φ on K [ χ ].

Proposition 4.7. Let ν be a multiplicative valuation on K( χ ). If the rational rank of νK( χ ) over νK is 1, or the transcendence degree of K( χ ) ν over K ν is 1 (in other words, if χ is transcendental and Abhyankar's inequality is an equality), then there is a finite number of key degrees, and ν = ν Φ for some w key polynomial Φ.

Proof. Abhyankar's inequality states that the transcendence degree of K( χ )|K is at least equal to the sum of the transcendence degree of (K( χ )) ν |K ν and the rational rank of ν(K [ χ ])|νK. Assume that the rational rank of νK( χ ) over νK is 1. Let d be the smallest integer such that there exists a monic polynomial Φ of degree d such that ν(Φ) is not rational over νK. If d = 1, then we know that Φ is a key polynomial. Otherwise, clearly,

other cases lead to a contradiction). So Φ is a key polynomial for ν. Now, the elements ν(Φ k ) = kν(Φ) are pairwise non-congruent modulo νK d-1 [ χ ]. In the same way as in Proposition 1.12, this implies that the family (Φ k ) is separated over K d-1 [ χ ]. Therefore, ν = ν Φ . Now, by 1) of Remark 4.6, if d > d, then d is not a key degree. Now, assume that the transcendence degree of K( χ ) ν over K ν is 1. Let Φ be a polynomial such that ν(Φ) = 0. If in ν (Φ) is algebraic over G ν (K), then by Lemma 1.17 in ν (Φ) is algebraic over K ν (the converse is trivial). Consequently, in ν (Φ) is transcendental over K ν if, and only if, it transcendental over G ν (K). In particular, there is Φ in K [ χ ] such that in ν (Φ) is transcendental over G ν (K). Let d be the smallest integer such that there exists a polynomial Φ of degree d such that in ν (Φ) is transcendental over G ν (K). Without loss of generality we can assume that Φ is a monic polynomial. Let f , g in K d-1 [ χ ], q = q Φ (f, g), r = r Φ (f, g). We have:

Now we turn to a particular case of immediate key degrees that we can call dense key degrees. It follows that if a key degree is dense, then it is the greatest key degree. Proposition 4.8. Let d ≥ 2, ν ≤ ν be pm valuations on K [ χ ]. Assume that χ d is limit over

, that the restrictions of ν and ν to K d-1 [ χ ] are equal, and that there exists a monic polynomial Φ of degree d such that ν (Φ) < ν(Φ). Let (Φ i ) be a sequence of monic polynomials of degree d such that the sequence (ν(Φ i )) is increasing and cofinal in νK [ χ ], and ν(Φ) < ν(Φ i ). Then.

. Let Φ j be a w key polynomial of degree d such that ν(Φ j ) > ν(Φ i ), and set

Then g is a monic polynomial of degree n, and ν(g

we let Φ j be a w key polynomial of degree d such that ν(Φ j ) > ν(Φ i ), and

Recall that if M is a K-submodule of K( χ ), then we denote by G ν (M ) the additive group γ∈νM M γ,ν .

Theorem 4.10. Let ν be a pm valuation on K( χ ), d be an independent key degree, Φ be a monic polynomial of degree

Φ is a key polynomial, and d is the smallest degree such that there exists a monic polynomial Φ of degree d with ν Φ (Φ ) < ν(Φ ).

2) The restrictions of ν and ν Φ to

) is a graded algebra and the fraction d /d is equal to the dimension of the

and by letting Φ be the minimal polynomial of χ over K, we have ν(Φ ) = +∞ > ν Φ (Φ ). Hence the assertion remains true. It also remains true in the case where d = +∞.

2) Since ν Φ ≤ ν, by 1) the restrictions of ν and ν Φ to

). Then χ is transcendental over K, so [K( χ ) : K] is infinite. In the same way as in the proof of Propositions 1.12 and 4.7 the family (Φ n ) is separated over K d-1 [ χ ] and ν = ν Φ . Furthermore, the dimension of the G ν (K d-1 ( χ ))-module G ν (K( χ )) is also infinite. Assume that d = +∞. Then by 1) ν = ν Φ , the family (Φ n ) is separated over K d-1 [ χ ] and ν = ν Φ . So the dimension of the G ν (K d-1 ( χ ))-module G ν (K( χ )) is also infinite. Now we assume that d < +∞. By 1) ν = ν Φ on K d -1 [ χ ] and there exists a monic polynomial Φ of degree d such that ν Φ (Φ ) < ν(Φ).

Since Φ is a key polynomial, for every k we have ν

By properties of valuations we have

In the same way as above, we can replace f kj by 1 in such an equality, and since d is minimal we have n = k j . Therefore, we can assume that for k ∈ {0, . . . , n} we have either ν(

). This also shows that the group

). Hence its dimension is n. 4) By Proposition 1.15, it is sufficient to show that for every integer

) and for every pairwise distinct y 1 , . . . , y k in B, x 1 , . . . , x k in K set ν (x 1 y 1 + • • • + x k y k ) = min 1≤i≤k ν(x i )ν (y i ). Then ν is a vs defectless K-module valuation. If for every k ≥ 1 we have ν (Φ k ) = ν(Φ k ), then the K-module valuation ν defined above is the K-module valuation ν Φ d 1 ,...,Φ d k defined in Notations 2.9.

Let ν be a pm valuation on K( χ ), 1 = d 1 < d 2 < • • • < d k < • • • be the sequence of key degrees of ν. Let F be a family of key polynomials. We say that F is a complete family of key polynomials for ν if ν is the supremum of the family of the pm valuations ν Φ d 1 ,...,Φ d k , where k ∈ N\{0}, for 1 ≤ i ≤ k Φ di ∈ F, deg(Φ di ) = d i . This means that if f is a polynomial of degree d, then ν(f ) is equal to the maximum of the family ν Φ d 1 ,...,Φ d k (f ), where d k is the greatest key degree at most equal to d.

For every pm valuation on K [ χ ] there exists a complete family of key polynomials (see for example [START_REF] Novakoski | Key polynomials and pseudo-convergent sequences[END_REF], [START_REF] Decaup | Abstract key polynomials and comparision theorems with the key polynomials of Mac Lane-Vaquié[END_REF]). We complete this subsection by the construction of a complete family of key polynomials which does not require to be constructed by induction on the degree.