Key polynomials for simple extensions of valued fields

Journal of Singularities Volume 25 (2022), 197-267 Proc. of 16th International Workshop on Singularities, S˜ao Carlos, 2020 DOI: 10.5427/jsing.2022.25k KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Dedicated to the memory of Roberto Callejas Bedregal Abstract. In this paper we present a refined version of MacLane’s theory of key polynomials, similar to those considered by M. Vaqui´e and reminiscent of approximate roots of Abhyankar and Moh. Given a simple transcendental extension of valued fields, we associate to it a countable well-ordered set of polynomials called key polynomials. We define limit key polynomials and give explicit formulae for them. We give an explicit bound on the order type of the set of key polynomials. 1. Introduction Let ι: (K, νK),→(K(x), ν) be a simple transcendental extension of valued fields such that rank νK= 1. In the case when νis discrete (that is, the value group of νis Z), S. Mac Lane described all such extensions in the nineteen thirties. His description was based on the theory of key polynomials associated to ιthat he introduced for that purpose ([24]–[26]). This seminal work of Mac Lane is connected to the resolution of fundamental arithmetic– geometric problems like the computation of prime ideal decomposition in number fields or the design of polynomial factorization algorithms over henselian fields. On the geometric side, limit key polynomials are linked to the defect of the extensions of valued fields, which is a well-known obstacle for the solution of the local uniformization problem in positive characteristic. Let (RνK, MνK, kνK) denote the valuation ring of νK. The purpose of this paper is to present a refined version of MacLane’s theory of key polynomials [24], [25], similar to those considered by M. Vaqui´e [36]–[39], and reminiscent of related objects studied by M. Lejeune-Jalabert [23], Abhyankar and Moh (approximate roots [1], [2]) and T.C. Kuo [21], [22]. Related questions were studied by Ron Brown [7]–[8], Alexandru–Popescu–Zaharescu [4]–[5], S. K. Khanduja [16], [17], F.-V. Kuhlmann [18] and Moyls [27]. The study of key polynomials continues to be a vibrant subject and since the first version of the present paper appeared on the arχiv in 2014 several other works on the topic were published by various authors: [3], [10], [11], [12], [13], [28], [29], [30], [33]. Precisely, we associate to ιa countable well-ordered set Q={Qi}i∈Λ⊂K[x], where Λ is an index set whose order type will be explicitly bounded later in the paper; the Qiare called key polynomials. Key polynomials Qithat have no immediate predecessor are called limit key polynomials We consider the main achievements of this paper compared to the earlier works on the subject to be the following. The third and fourth authors are partially supported by PID2020-114613GB-I00 (MCIN/AEI/10.13039/501100011033) and P20-01056 (Junta de Andaluc´ıa and ERDF). 198 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY (1) Explicit formulae for each key polynomial Qi, particularly for limit key polynomials (Proposition 9.2), in terms of the key polynomials preceding Qi. If there exists an infinite sequence of linear key polynomials then the first limit key polynomial (if it exists) can always be chosen to be a p-polynomial in Kaplansky’s terminology (p-polynomials may be viewed as a generalization of Artin–Schreier polynomials). (2) An upper bound on the order type of the set of key polynomials. Namely, we show that the order type of the set of key polynomials is bounded by ω×ω, where ωstands for the first infinite ordinal. If char kνK= 0, the order type is bounded by ω+ 1. If char kνK= 0 and rank ν= 1, the set of key polynomials has order type at most ω. The results comparing the value of a polynomial f∈K[x] with the values of its Hasse derivative ∂bf(the definition of ∂bis recalled later in the Introduction) proved in §7led to an axiomatic characterization of key polynomials in [12]. As well, this approach was used in [33] to obtain another proof of the existence of a complete set of key polynomials. The main application of the theory of key polynomials (particularly, of point (1) above) that we have in mind is proving the local uniformization theorem for quasi-excellent noetherian schemes in positive and mixed characteristic. It has been shown recently that to prove the local uniformization theorem in the positive equicharacteristic case, assuming local uniformization in lower dimensions, it is sufficient to monomialize the first limit key polynomial of a certain explicitly defined simple field extension K ,→K(x) (see [34], Chapter IV, [35], Theorem 6.5 and S. D. Cutkosky–H. Mourtada [9]). In Chapter V of his Ph.D. thesis ([34], Institut de Math´ematiques de Toulouse, 2013), J.-C. San Saturnino proved a similar reduction for local uniformization in the case of mixed characteristic, but under somewhat restrictive additional hypotheses. Chapter 3 of the Ph.D. thesis of W. Mahboub (Institut de Math´ematiques de Toulouse, 2013) develops the theory of key polynomials for valuations of arbitrary rank. Here we limit ourselves to the case rank νK= 1. The particular importance of the case rank νK= 1 is witnessed by a theorem of Novacoski– Spivakovsky that says that local uniformization along rank one valuations implies local uniformization in its full generality [31]–[32]. Let Γ0(resp. Γ) denote the value group of νK(resp. ν). Let ˜ Γ0:= Γ0⊗ZQ(the group ˜ Γ0 is called the divisible hull of Γ0). Fix an embedding ˜ Γ0,→Ronce and for all. In this sense, we will talk about the supremum of a certain subset of ˜ Γ0(the supremum can be either a real number or infinity) or about a certain sequence of elements of ˜ Γ0tending to infinity. For an ordered abelian group ∆, the notation ∆+will stand for the semigroup formed by all the non-negative elements of ∆. The well-ordered set Q={Qi}i∈Λof key polynomials of νwill be defined recursively in i. Notation. We will use the notation Nfor the set of strictly positive integers and N0for the set of non-negative integers. For an element ℓ∈Λ, we will denote by ℓ+1 the immediate successor of ℓin Λ. The immediate predecessor of ℓ, when it exists, will be denoted by ℓ−1. For a strictly positive integer t,ℓ+t will denote the immediate successor of ℓ+ (t−1). For an element ℓ∈Λ, the initial segment {Qi}i<ℓ of the set of key polynomials will be denoted by Qℓ. For the rest of this paper, we let p= char kνKif char kνK>0 and p= 1 if char kνK= 0. For an element β∈Γ∪˜ Γ0, let Pβ={y∈K(x)|ν(y)≥β}∪{0} Pβ+={y∈K(x)|ν(y)> β }∪{0}. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 199 Put (1.1) Gν=M β∈Γ Pβ Pβ+ and (1.2) ˜ Gν=M β∈˜ Γ0 Pβ Pβ+ . We regard Gνand ˜ Gνas kν-algebras. Note that even though ˜ Γ0need not be contained in Γ, we have ˜ Gν⊂Gνsince for each β∈˜ Γ0\Γ the corresponding summand in (1.2) is 0. For y∈K(x)∗, let inνydenote the natural image of yin Pβ Pβ+⊂Gν, where β=ν(y). Let ∆xbe an independent variable. For f∈K[x] and j∈Nlet ∂jfdenote the j-th formal (or Hasse) derivative of fwith respect to x. The polynomials ∂jfare, by definition, the coefficients appearing in the Taylor expansion of f:f(x+ ∆x) = P j ∂jf(x)∆xj. In papers on local uniformization the Hasse derivatives ∂jare often denoted by 1 j! ∂j ∂xj; this notation is regarded as one indivisible symbol; its parts such as 1 j!do not make sense on their own. Details about Hasse derivatives can be found in [19], Chapter 24.10, starting on p. 701, as well as in [20]. For an ordinal ℓ∈Λ we will use the following multi-index notation: ¯γℓ+1 = (γi)i≤ℓ, where the γiare non-negative integers, all but finitely many of which are equal to 0, and (1.3) Q¯γℓ+1 ℓ+1 =Y i≤ℓ Qγi i. An ℓ-standard monomial in Qℓ+1 is a product of the form (1.4) c¯γℓ+1 Q¯γℓ+1 ℓ+1 , where c¯γℓ+1 ∈Kand the multiindex ¯γℓ+1 satisfies certain additional conditions to ensure a form of uniqueness (see Definition 3.4). An ℓ-standard expansion is a finite sum of ℓ-standard monomials satisfying a mild additional condition. A Qℓ-expansion is an expression of the form (1.5) sℓ X j=0 cj,ℓQj ℓ, where cj,ℓ ∈K[x] and degxcj,ℓ <degxQℓfor all j. Note. Starting with an ℓ-standard expansion and grouping together all the terms involving Qj ℓ for each exponent jproduces a Qℓ-expansion. Iterating Euclidean division of fby Qℓ, it is easy to see that every f∈K[x] admits a unique Qℓ-expansion (1.6) f= sℓ X j=0 cj,ℓQj ℓ. In §3we will show that for all ℓ∈Λ and all f∈K[x] the element fadmits an ℓ-standard expansion. Let βi=ν(Qi). 200 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY A product of the form a s Q j=1 Qγj ij, where a∈K,ij∈Λ and γj∈Nis said to be a standard monomial if it is ℓ-standard for some ℓ∈Λ. A set of key polynomials is said to be complete if for every β∈Γ the additive group Pβ∩K[x] is generated by standard monomials, contained in Pβ∩K[x]. It is said to be ˜ Γ0-complete if the above condition holds for all β∈˜ Γ0, in other words, if for all β∈˜ Γ0every polynomial f∈K[x] with ν(f) = βbelongs to the additive group generated by standard monomials a s Q j=1 Qγj ijsuch that s P j=1 γjβij+νK(a)≥β. Remark 1.1.If Q={Qi}i∈Λis a complete set of key polynomials, the data {Qi, βi}completely determines the ideals Pβfor all β∈Γ, hence also all the ideals Pβ+, since Pβ+=S ˜ β>β P˜ β. For an element y∈K(x) we have ν(y) = βif and only if y∈Pβ\Pβ+. Thus the valuation νis completely determined by the data {Qi, βi}. We define the ℓ-truncation νℓof νby νℓ(f) = min 0≤j≤sℓ {ν(cj,ℓ) + jβℓ}for each f∈K[x] with Qℓ-expansion (1.6). By the ultrametric triangle law, we have (1.7) ν(f)≥νℓ(f) for all f∈K[x]. Then the statement that Qis a complete set of key polynomials can be expressed as follows: for all f∈K[x] there exists ℓ∈Λ such that equality holds in (1.7); see Remark 3.34 for details. The paper is organized as follows. §2is devoted to generalities on algebras, graded by ordered semigroups. There we define the notion of the saturation G∗of a graded algebra G(Definition 2.3). We consider an extension G⊂G′of graded algebras and a homogeneous element x∈G′. We study the condition that xbe algebraic over G. We note that xis algebraic over Gif and only if it is integral over G∗. We show that if xis algebraic over Gthen the algebra G∗[x] is saturated (Lemma 2.6). Finally, we prove the simple but useful characterization of the strict inequality νÅs P i=1 yiã>min 1≤i≤s{ν(yi)}in terms of the elements inνyi. In §3we define the notion of a set of key polynomials (not necessarily complete) and study its properties. By definition, letting Q0=x, the one element set {x}={Q0}is a set of key polynomials. We remark that if a set of key polynomials is complete then the images of the key polynomials in Gνgenerate the field of fractions of Gνover the field of fractions of GνK. The element inνQℓis algebraic over GνK[inνQℓ], where Qℓ={Qi}i<ℓ (in particular, βi∈˜ Γ0) whenever iis not a maximal element of Λ (Propositions 3.35 and 3.36). In §4we associate to each pair h∈K[x], i∈Λ, a positive integer numerical character δi(h)≤degxh degxQito be used in later sections and study its properties. Among other things we prove that (1.8) δi(h)≥δi′(h) whenever i≤i′; in particular, δi(h) stabilizes for isufficiently large. We also show that the equality in (1.8) imposes strong restrictions on h. The numerical character δi(h) helps analyze infinite ascending sequences of key polynomials in §§8–9and is crucial for applications to Local Uniformization. The main step of our recursive construction of sets of key polynomials is carried out in §5. Namely, we start with a set {Qi}i∈Λof key polynomials that is not complete and enlarge it to a strictly greater set {Qi}i∈Λ+of key polynomials. The well-ordered set Λ+is a union of Λ with KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 201 a sequence that may be finite or infinite, depending on the situation. Roughly speaking, Qℓ+1 is defined to be a lifting to K[x] of the monic minimal polynomial, satisfied by inνQℓover the graded algebra GνK[inνQℓ]. This gives rise to explicit formulae describing each non-limit key polynomial in terms of the preceding key polynomials. In §6we iterate the procedure of §5until the resulting set of key polynomials is complete. Namely, we start our recursive construction of the Qiby putting Q0:= x. We assume, inductively, that a set Q={Qℓ}ℓ∈Λof key polynomials is already defined. If the set Qof key polynomials is complete, the algorithm stops here. In particular, this occurs whenever our algorithm produces a key polynomial Qiwhose value does not lie in ˜ Γ0or, more generally, such that inνQiis transcendental over GνK[inνQi] (Propositions 3.35 and 3.36). If Qis not complete, we replace it by the set {Qi}i∈Λ+constructed in §5and repeat the procedure. We remark (Remark 6.1) that the well-ordered set ¯ Λ resulting from this construction has order type at most ω×ω. The set ¯ Λ contains a maximal element ℓif and only if it contains an element ℓsuch that inνQℓis transcendental over GνK[inνQℓ], where Qℓ={Qi}i<ℓ (Propositions 3.35 and 3.36). §7is auxiliary, to be used in §§8–9. We study the effect of Hasse derivatives ∂jon key polynomials and standard expansions. Let bidenote the smallest element bof Nwhich maximizes the quantity βi−ν(∂bQi) b. We show that biis of the form (1.9) bi=peifor some ei∈N0 (Corollary 7.9). The non-negative integers ei,i∈Λ, are important numerical characters of the extension ι: (K, νK),→(K(x), ν) of valued fields. Most importantly, given an ℓ-standard monomial c¯γℓ+1 Q¯γℓ+1 ℓ+1 , we prove the equality (1.10) νÄ∂pec¯γℓ+1 Q¯γℓ+1 ℓ+1 ä=νℓÄ∂pec¯γℓ+1 Q¯γℓ+1 ℓ+1 ä, and derive an explicit formula for the quantity νÄ∂pec¯γℓ+1 Q¯γℓ+1 ℓ+1 ä, for integers e≥ei, and under certain additional conditions. Also, for every ℓ-standard expansion fand every integer e≥ei, we derive a formula for νℓ(∂pef) (Proposition 7.2). The importance of this type of explicit formulae can be explained as follows. The importance of differential operators for resolution of singularities is well known. One difficulty with dealing with differential operators up to now has been the fact that they obey no simple transformation law under blowing up. Since key polynomials become coordinates after blowing up, formulae (1.10) can be viewed as comparison results for derivatives of the defining equations of a singularity before and after blowing up. The main subject of study of §§8–9are infinite sequences {Qℓ+t}t∈Nof key polynomials of a fixed degree and the corresponding limit key polynomials Qℓ+ω. In §8we let δdenote the stable value of δℓ+t(Qℓ+ω) for a sufficiently large positive integer t (such a stable value exists by (1.8)). We use the results of §7to show that δmust be of the form δ=pefor some e∈N0(Propositon 8.6). Next, we assume that char kν= char K, that the sequence {ν(Qt)}t∈Nis unbounded in ˜ Γ0 and that degxQt= 1 for all t∈N. We show that Qω∈Kxδ(Remark 8.7). The third set of main results of §8starts with Proposition 8.10 which asserts that if char kν= 0, then for an infinite sequence {Qt}t∈N0the sequence {βt}t∈N0of their values is unbounded in ˜ Γ0. In particular, there are no limit key polynomials Qisuch that βi∈˜ Γ0. This explains why ¯ Λ≤ω+ 1 whenever char kν= 0. The main goal of §9is to derive explicit formulae for limit key polynomials in terms of the preceding key polynomials. We assume that char kν=p > 0 and consider a limit ordinal 202 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY ℓ+ω∈¯ Λ. We assume that the sequence {ν(Qℓ+t)}t∈Nis bounded in ˜ Γ0. We prove that Qℓ+ω can be chosen in such a way that for some t∈Nthe Qℓ+t-standard expansion of Qℓ+ωis weakly affine. By definition, this means that (1.11) Qℓ+ω=Qpeℓ+ω i+ eℓ+ω−1 X j=0 cpj,iQpj i+c0i, where i=ℓ+tand c0,i and cpj,i are Qi-free i-standard expansions (See Definition 3.5 for the notion of “Qi-free”). The results of this paper are related to those contained in the paper [14] (see also [39]). However, there are some important differences, which we now explain. We chose to rewrite the whole theory from scratch for the following reasons. (1) In [14] we work with an algebraic extension ιwhile for local uniformization we need to consider purely transcendental extensions. We note that the case of algebraic extensions can easily be reduced to that of transcendental ones using composition of valuations. Indeed, let ι−: (K, νK),→(K(x), ν) be a simple algebraic extension of valued fields. Write K(x) = K[X] (f), where fis the minimal polynomial of xover K. Let νfdenote the (f)-adic valuation of K[X] and put ν∗:= νf◦ν(the composition of νfwith ν). Complete sets {Qi}i∈Λof key polynomials of the transcendental extension ι: (K, νK)→(K(X), ν∗) constructed in the present paper are very closely related to complete sets {Q− i}i∈Λ−of key polynomials of the algebraic extension (K, νK)→(K(x), ν), constructed in [14]. Namely, we have Λ = Λ−∪ {Λ−}(extension by one element), Q− iis the image of Qi under the natural map K[X]→K(x) and QΛ−=f. In other words, a complete set {Qi}of key polynomials for ιcan be obtained from that of ι−by lifting each key polynomial Q− ito K[X] and then adding one final key polynomial f. In this sense the theory presented here can be viewed as a generalization of [14]. (2) Our main interest in [14] was to classify all the possible extensions νof a given νK; in the present paper we content ourselves with a fixed ν. (3) The crucial formulae for νℓ(∂pbf) were not made explicit in [14]. (4) We take this opportunity to correct numerous mistakes which, unfortunately, made their way into the paper [14]: an inaccuracy in the definition of complete set of key polynomials, the failure to take into account the case of mixed characteristic, a mistake in the definition of the numerical characters eiand many others which made the paper [14] unreadable. Acknowledgements. We thank Anna Blaszczok, Julie Decaup, Franz-Viktor Kuhlmann, G´erard Leloup and all the anonymous referees of the earlier versions of the paper for many useful comments and suggestions and for pointing out errors. 2. Algebras graded by ordered semigroups Graded algebras associated to valuations will play a crucial role in this paper. In this section, we give some basic definitions and prove several easy results about graded algebras. Throughout this paper, a “graded algebra” will mean “an algebra without zero divisors, graded by an ordered semigroup”. As usual, for a graded algebra G, ord will denote the natural valuation of G, given by the grading. Let G=L α∈Γ Gαbe a graded algebra, where Γ is an ordered abelian semigroup. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 203 Definition 2.1. An element x∈Gis said to be homogeneous if there exists α∈Γ such that x∈Gα. For a homogeneous element x∈Gα⊂Gwe will write ord x=α. Now let Xbe an independent variable and consider the ring G[X]. Fix a polynomial f= d X i=0 aiXi∈G[X] such that aiis a homogeneous element of Gfor all i∈ {0, . . . , d}. Fix an element β∈Γ. Definition 2.2. We say that fis quasi-homogeneous with w(X) = βif for all i, j ∈ {0, . . . , d} we have iβ+ord ai=jβ+ord aj. In this situation we will also say that βis the weight assigned to X. Definition 2.3. Let Gbe a graded algebra without zero divisors. The saturation of G, denoted by G∗, is the graded algebra G∗=ng hg, h ∈G, h homogeneous, h = 0o. Gis said to be saturated if G=G∗. An element g h∈G∗is homogeneous in G∗if and only if gis homogeneous in G. If f1=g1 h1 and f2=g2 h2are two non-zero elements of G∗, where h1, h2, g1, g2are non-zero elements of G with h1, h2, g2homogeneous, then f1 f2=g1h2 g2h1∈G∗. Thus G∗= (G∗)∗for any graded algebra G, so that G∗is always saturated. Example 2.4. The main example of graded algebras we are interested in this paper are graded algebras associated to valuations, centered in prime ideals of integral domains. Namely, let R be a domain, Kits field of fractions and ν:K∗→Γ a valuation of K, centered at a prime ideal Pof R(this means, by definition, that R⊂Rνand P=Mν∩R, where (Rν, Mν) denotes the valuation ring of ν). Let Φ = ν(R\ {0}). For each β∈Φ, consider the ideals (2.1) Iβ: = {x∈R|ν(x)≥β}∪{0}and Iβ+: = {x∈R|ν(x)> β}∪{0}. Iβis called the ν-ideal of Rof value β. If β1> β2> . . . is an infinite descending sequence of elements of Φ then Iβ1⫋Iβ2⫋. . . is an infinite ascending chain of ideals of R. Thus if Ris noetherian then the ordered set ν(R) contains no infinite descending sequences, that is, ν(R) is well-ordered. If Iis an ideal in a noetherian ring Rand νa valuation of R,ν(I) will denote min{ν(x)|x∈I}. We can now define the graded algebra, associated to the valuation ν. Let R,νand Φ be as above. For β∈Φ, let Iβand Iβ+be as in (2.1). We define grνR=M β∈Φ Iβ Iβ+ . The algebra grνRis an integral domain. For any element x∈Rwith ν(x) = β, we may consider the natural image of xin Pβ Pβ+⊂grνR. This image is a homogeneous element of grνRof degree β, which we will denote by inνx. The grading induces an obvious valuation on grνRwith values in Φ; this valuation will be denoted by ord. 204 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Next, suppose that (R, M, k) is a local domain and νis a valuation with value group Γ, centered at R. Let Kdenote the field of fractions of R. Let (Rν, Mν, kν) denote the valuation ring of ν. For β∈Γ, consider the following Rν-submodules of K: (2.2) Iβ={x∈K|ν(x)≥β}, Iβ+={x∈K|ν(x)> β}. We define Gν=M β∈Γ Iβ Iβ+ . Again, given x∈K, we may speak of the natural image of xin Gν, also denoted by inνx(since grνRis naturally a graded subalgebra of Gν, there is no danger of confusion). Then ord is a valuation of the common field of fractions of grνRand Gν, with values in Γ. We have Gν= (grνR)∗; in particular, Gνis saturated. Remark 2.5.Let G, G′be two graded algebras without zero divisors, with G⊂G′. Let xbe a homogeneous element of G′, satisfying an algebraic dependence relation (2.3) a0xn+a1xn−1+· · · +an= 0 over G(here aj∈Gfor 0 ≤j≤n). Without loss of generality, we may assume that the integer nis the smallest possible. Claim. Without loss of generality, we may further assume that (2.3) is homogeneous (that is, all the ajare homogeneous and the quantity jord x+ ord ajis constant for 0 ≤j≤nsuch that aj= 0). Proof of Claim. Let µ:= min 0≤j≤n{jord x+ ord aj}. Then each ajcan be written as a finite sum of homogeneous elements of G, all of orders greater than or equal to µ−jord x. For j∈ {0, . . . , n}write aj=a0j+ ˜aj, where a0j= 0 or ord a0j=µ−jord x, and ˜ajis a sum of homogeneous elements of Gof orders strictly greater than µ−jord x(note that there exist at least two different values of jfor which a0j= 0). Now, xsatisfies the equation (2.4) a00xn+a01xn−1+· · · +a0n= 0. This proves the Claim. From now on we will always take the coefficients ajto be homogeneous without mentioning it explicitly. Dividing (2.3) by a0, we see that xsatisfies a monic homogeneous relation over G∗of degree n and no algebraic relation of degree less than n. In other words, xis algebraic over Gif and only if it is integral over G∗; the conditions of being “algebraic over G∗” and “integral over G∗” are one and the same thing (as usual, “integral” means “satisfying a monic polynomial relation”). Let G⊂G′, let xbe as above and let G[x] denote the graded subalgebra of G′, generated by xover G. By Remark 2.5, we may assume that xsatisfies a homogeneous integral relation (2.5) xn+a1xn−1+· · · +an= 0 over G∗and no algebraic relations over G∗of degree smaller than n. Lemma 2.6. Every element of (G[x])∗can be written uniquely as a polynomial in xwith coefficients in G∗, of degree strictly less than n. Proof. Let ybe a homogeneous element of G[x]. Since xis integral over G∗, so is y([6], p. 59, Proposition 5.1, implications (i) ⇐⇒ (ii) ⇐⇒ (iii)). Let (2.6) ym+b1ym−1+· · · +bm= 0 KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 205 with bj∈G∗, be an integral dependence relation of yover G∗, with bjhomogeneous elements of G∗,bm= 0, where jord y+ ord bjis constant for all jsuch that bj= 0. By (2.6), 1 y=−1 bm (ym−1+b1ym−2+· · · +bm−1). Thus, for any z∈G[x], we have (2.7) z y∈G∗[x]. Since ywas an arbitrary homogeneous element of G[x], we have proved that (G[x])∗=G∗[x]. Now, for every element y∈G∗[x] we can add a multiple of (2.5) to yso as to express yas a polynomial in xof degree strictly less than n. Moreover, this expression is unique because x does not satisfy any algebraic relation over G∗of degree smaller than n.□ Notation. If ∆ ⊂∆′are ordered semigroups and βis an element of ∆′, then ∆ : βwill denote the positive integer defined by ∆ : β= min{n∈N|nβ ∈∆}. If the set on the right-hand side is empty, we put ∆ : β=∞. Note that β∈∆ if and only if ∆ : β= 1. Lemma 2.7. Let G,G′be as in Remark 2.5 and xa homogeneous element of G′. Assume that the degree 0 part of G(that is, the subring of Gconsisting of all the elements of degree 0) contains a field kand that Gis generated as a k-algebra by homogeneous elements w1, . . . , wr. Let βj= ord wj,1≤j≤r, and let ∆denote the group ∆ = {ord y|y∈G∗}=®r P j=1 njβj nj∈Z´. Assume that the following two conditions hold: (1) ∆ : (ord x)<∞ (2) Let ˜n:= ∆ : (ord x). Let n1, . . . , nr∈Zbe such that (2.8) ˜nord x= r X j=1 njβj. Let y= r Q j=1 wnj j. Assume that the element (2.9) z:= x˜n y∈(G′)∗ is algebraic over k. Then xis integral over G∗. An integral dependence relation of xover G∗can be described as follows. Let zbe as in (2.9). Let Zbe an independent variable and let (2.10) f(Z) = Zd+ d−1 X i=0 ciZi 212 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Proposition 3.14. For each i∈Λwe have: (1) If sup {βq|q < i}<∞(in particular, whenever i= max Λ) then (3.16) ¯αi=Y j≤i αj. (2) Take an element z∈K[x]. Assume that zadmits a Qi-free i-standard expansion. Then (3.17) degxz < ¯αi. Proof. We use transfinite induction on i. For the base of the induction, consider the case i= 0. (3.16) says that (3.18) ¯α0= degxx=α0= 1; this follows immediately from (3.2) and (3.3). By (3.18) and (3.4), every monomial appearing in the 0-standard expansion zis of degree strictly less than 1 = ¯α0, that is, is an element of K. This proves (3.17) in the case i= 0. Assume given an ordinal i > 0. Assume that (3.16) and (3.17) are known for some ordinal i0 such that i0+ = i. If i=i0+ωthen i0is inessential, so αi0+t= 1 for all t∈N0by Definition 3.1. Thus in all the cases we have (3.19) ¯αi0=Y j<i αj. By assumption, (3.13) holds, hence so does (3.14) by condition (c) of Definition 3.11. Thus by (3.9), (3.11) and (3.17) applied to i0instead of i, the term Qαi i0in the i0-standard expansion of Qihas strictly greater degree than all the other terms. Hence (3.20) ¯αi= degxQαi i0=αi¯αi0. We obtain ¯αi=αi¯αi0=αiY j<i αj=Y j≤i αj, which proves (3.16). Let zbe as in part (2) of the Proposition. Fix a Qi-free i-standard expansion of zand let i0denote the greatest ordinal such that Qi0appears in this expansion (by definition of Qi-free, we have i0< i): z= αi−1 P j=0 dj,iQj i0, where each dj,i is a Qi0-free i0-standard expansion. By the induction assumption, we have degxdj,i <¯αi0for all j. Combining this with (3.20), we obtain degxz < max 0≤j<αi−1{(j+ 1)¯αi0} ≤ αi¯αi0= ¯αi, as desired. □ Corollary 3.15. Let fbe an i-standard expansion of an element of K[x]. Then fis Qi-free if and only if degxf < ¯αi. Proof. Straightforward transfinite induction on i.□ Remark 3.16.Assume that i∈Λ is a limit ordinal and take an i0∈Λ such that i=i0+. Since αi0+1 = 1 by definition, we have Qi0+1 =Qi0+z, where inνz=−inνQi0and degxz < ¯αi0. Hence (3.21) GνK[inνQi]⊂G<¯αi0. Below (Proposition 3.31) we will show that this inclusion is, in fact, an equality. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 213 Remark 3.17.In §9we will show, assuming that iis a limit ordinal and that the set {ν(Qi0)}i=i0+ is bounded in ˜ Γ0, that we can choose i0and Qiso that Qiis a weakly affine monic i0-standard expansion of degree αi=peifor a certain integer eiand, moreover, that there exists a positive element ¯ βi∈Rsuch that ¯ βi> βqfor all q < i,(3.22) βi≥αi¯ βiand(3.23) pj¯ βi+νcpj,i0=αi¯ βifor 0 ≤j≤ei.(3.24) Remark 3.18.Take an element h∈K[x]. Then hadmits a unique Qi-expansion (3.25) h= si X j=0 dj,iQj i. This can be shown by induction on degxh. Indeed, let h=qQi+rbe the Euclidean division of hby Qi. Then d0,i =rand for j > 0 the coefficients dj,i are nothing but the coefficients of powers of Qiin the Qi-expansion of q. Proposition 3.19. Assume that the set {βq|q < i}is bounded in ˜ Γ0(so that the hypothesis of Proposition 3.14 (1) is satisfied). Every coefficient dj,i in (3.25) admits a Qi-free i-standard expansion. Writing each coefficient dj,i in this way produces an i-standard expansion of h. In particular, every element of K[x]admits an i-standard expansion. Proof. We use transfinite induction on i. For i= 0 the result is obvious. Assume that i > 0 and that the Proposition holds for all i′< i. By definition of Qi-expansion we have (3.26) degxdj,i <¯αifor all j. Take an ordinal i0such that i=i0+. By the induction assumption applied to i0the Qi0- expansion of (3.27) dj,i =X q dq,j,iQq i0 can be made into an i0-standard expansion by writing out a Qi0-free i0-standard expansion of each coefficient dq,j,i. Moreover, by Proposition 3.14 (1) and (3.26), all the monomials Qj i0 appearing in (3.27) satisfy j < αi. This makes (3.27) into a Qi-free i-standard expansion of dj,i, so (3.25) can be made into an i-standard expansion of h, as desired. □ Remark 3.20.The i-standard expansions (3.27) of the dj,i need not, in general, be unique. For example, if iis a limit ordinal, dj,i admits an i0-standard expansion (3.27) for each (3.28) i0< i such that i=i0+, but there are countably many choices of i0satisfying (3.28). If i∈N0, then the i-standard expansion of his unique. This follows from Remark 3.18 by induction on i. Part of the point of Remarks 3.18 and 3.20 and Proposition 3.19 is that an i-standard expansion is a Qi-expansion together with an additional set of data, namely, a Qi-free i-standard expansion of the coefficients dj,i. For each i∈Λ we define a map νi:K(x)∗→Γ as follows. Given a Qi-expansion (3.29) f= si X j=0 dj,iQj i, 214 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY put (3.30) νi(f) = min 0≤j≤si {jβi+ν(dj,i)}. By Remark 3.18, the elements dj,i ∈K[x] are uniquely determined by f, so νiis well defined. We extend νito all of K(x) by additivity. Remark 3.21.We have (3.31) νi(f)≤ν(f) by the ultrametric triangle law. Remark 3.22.It is clear from the definition that the map νisatisfies the ultrametric triangle law. Below, we will show that it is, in fact, a valuation. Next, we give criteria for when the inequality (3.31) is strict and when it is an equality. Remark 3.23.If degxf < degxQithen we have si= 0 in the i-standard expansion (3.30), so νi(f) = ν(d0,i) = ν(f). Remark 3.24.Consider ordinals i0< i and t∈N0such that i=i0+, i+t∈Λ and for each ordinal i′such that i<i′≤i+twe have (3.32) αi′= 1. (1) If (3.13) holds, we have νi0(Qi) = αiβi0by (4) of Definition 3.11 (b) and (3.15) (recall that (3.13) can only fail if i= max Λ). (2) By (3.9), (3.32) and induction on t, (3.33) Qi+t=Qi+ t−1 X q=0 zi+q,where deg zi+q<¯αi. Hence every i0-standard expansion of Qi+tcontains the term Qαi i0. We obtain νi0(Qi+t)≤αiβi0. Below (Corollary 3.42) we will see that under a mild additional hypothesis on i0the last inequality is, in fact, an equality. Remark 3.25.Consider ordinals i, ℓ ∈Λ, i < ℓ. Then νℓ(Qi) = νi(Qi) = ν(Qi). Indeed, if ¯αi<¯αℓour statement holds by definition of νℓ. Assume that ¯αi= ¯αℓ. Then (3.34) Qℓ=Qi+z where degxz < ¯αiand ν(z) = βi< βℓ. Now, Qi=Qℓ−zis an ℓ-expansion of Qi, so νℓ(Qi) = min{βi, ν(z)}=ν(z) = βi, as desired. Proposition 3.26. For a pair of ordinals i0< i such that i=i0+we have (3.35) νi0(Qi)< βi. Proof. Let (3.36) Qi= αi X j=0 cj,i0Qj i0 be the i0-standard expansion of Qi. If i0=i−1 is the immediate predecessor of ithen by (3.9)– (3.10) the quantity ν(Qi) = νi(Qi) is strictly greater than the common value of νÄcj,i0Qj i0ä (cf. (4) of Definition 3.11), where jranges over the elements of {0, . . . , αi}for which cj,i0= 0. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 215 This common value is, by definition, νi0(Qi). If idoes not admit an immediate predecessor, the desired strict inequality is nothing but (3.12). □ Corollary 3.27. If i∈Λis not the maximal element of Λ, then there exists f∈K[x]such that νi(f)< ν(f). Proposition 3.28. Fix an ordinal i∈Λand let θ=Q¯γi ibe a Qi-free i-standard monomial. Then (3.37) ν(θ)< βi. Proof. If (3.13) does not hold, we have βi>˜ Γ0and the result follows immediately. Therefore we may assume that (3.13) holds. We proceed by transfinite induction on i. If i= 0 then θ= 1 and β0=ν(x)>0, so the result holds. Assume that i > 0 and the Proposition holds for all the ordinals i′< i. Let i0be the smallest ordinal such that i0+ = iand γi′= 0 for all i′such that i0< i′< i. Write θ=Q¯γi0 i0Qγi0 i0where (3.38) γi0< αi and Q¯γi0 i0is a Qi0-free i0-standard monomial. By the induction assumption, νÄQ¯γi0 i0ä< βi0. Combining this with (3.38), Remark 3.24 and Proposition 3.26, we obtain ν(θ)< βi0+γi0βi0≤αiβi0< βi, as desired. □ Proposition 3.29. Take an ordinal i∈Λand assume that (3.13) holds. Then Qi∈RνK[x]. Proof. We use transfinite induction on i. For i= 0 we have Q0=xand the result is clear. Assume that i > 0 and the Proposition holds for all the ordinals i′< i. Take an ordinal i0such that i=i0+ and let (3.39) Qi=Qαi i0+ αi−1 X j=0 ÑX ¯γi0 cj,i,¯γi0Q¯γi0 i0éQj i0, be an i0-standard expansion of Qi. By the induction assumption, it is enough to prove that (3.40) νcj,i,¯γi0≥0 for all the choices of j, i, ¯γi0. Fix j, i, ¯γi0appearing in one of the terms in (3.39). We have (3.41) νÑÑX ¯γi0 cj,i,¯γi0Q¯γi0 i0éQj i0é≥νQαi i0 by Definition 3.11 (b) (4) and (3.15) and νÄQ¯γi0 i0ä< βi0by Proposition 3.28 with ireplaced by i0. Combining the last inequality with (3.41), we obtain νcj,i,¯γi0≥αiβi0−(j+ 1)βi0≥0, as desired. □ Let β∗be a non-negative element of Γ. Keep the notation of (3.29). We denote Si(β∗, f) := ßj∈ {0, . . . , si}jβ∗+ν(dj,i) = min 0≤k≤si {kβ∗+ν(dk,i)}™. Let ¯ Qibe a new variable. 216 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Notation: Si(f):=Si(βi, f).(3.42) δi(f) : = max Si(f)(3.43) inif: = X j∈Si(f) inνdj,i ¯ Qj i;(3.44) the polynomial inifis quasi-homogeneous in GνKinνQi,¯ Qi, where the weight assigned to ¯ Qi is βi. Remark 3.30.If δi(f) = 0 then ν(d0,i)< ν Ädj,iQj iäfor j > 0, so ν(f) = ν(d0,i) = νi(f), where the first equality holds by the ultrametric triangle law. Proposition 3.31. (1) For each ordinal i∈Λwe have (3.45) G<¯αi=GνK[inνQi]. (2) The elements inνf,degxf < ¯αi, generate G<¯αias a GνK-module. Proof. We use transfinite induction on i. For i= 0 we have ¯α0= 1, both sides of (3.45) coincide with GνKand all the statements are clear. Assume that i > 0 and that the result is known for all the ordinals strictly smaller than i. To prove that (3.46) GνK[inνQi]⊂G<¯αi, we distinguish two cases. If iis a limit ordinal, (3.46) follows immediately from (3.21). Suppose that iis not a limit ordinal. We have GνK[inνQi] = GνK[inνQi−1] [inνQi−1]∼ =G<¯αi−1[inνQi−1], where the last isomorphism is given by the induction assumption. Since αi−1is the degree of the minimal polynomial of inνQi−1over GνK[inνQi−1] (Definition 3.11 (b) (5)), every element of G<¯αi−1[inνQi−1] admits an (i−1) standard expansion with all the exponents of Qi−1strictly smaller than αi−1(by Lemma 2.6, with inνQi−1playing the role of x). Such an element is represented by a polynomial f∈K[x] admitting a Qi-free i-standard expansion, that is, a polynomial such that degxf < ¯αi(Corollary 3.15). This proves the inclusion (3.46). To prove the opposite inclusion, take f∈K[x] with (3.47) degxf < ¯αi. By Corollary 3.15 fadmits a Qi-free i-standard expansion f= t P j=1 ηj, where η1, . . . , ηtare Qi-free i-standard monomials. Let β= min j{ν(ηj)}and {θ1, . . . , θs}={ηj|j∈ {1, . . . , t}, ν(ηj) = β}. If iis not a limit ordinal, αiis the degree of the minimal polynomial of inνQi−1over GνK[inνQi−1] (Definition 3.11 (b) (5)). By (3.47) we have P j inνθj= 0 in Gν(otherwise we would have an algebraic relation satisfied by inνQi−1over GνK[inνQi−1] of degree strictly less than αi), hence ν(f) = ν(θj) (for all j) and P j inνθj= inνf(see Proposition 2.10). If iis a limit ordinal, by Definition 3.11 (c) there exists an ordinal i0satisfying i0+ = isuch that, letting f= si P j=0 cj,i0Qj i0be an i0-standard expansion of f(where si< αi), we have (3.48) ν(f) = min 0≤j≤si¶νÄcj,i0Qj i0ä©, KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 217 so (3.49) inνf=X j∈Si0(f) inνÄcj,i0Qj i0ä by Proposition 2.10. In both cases we have proved that the left-hand side of (3.45) is contained in the right-hand side. To prove (2) of the Proposition, first assume that iis not a limit ordinal. By the induction assumption elements of the form inxg,g∈K[x], degxg < ¯αi−1, generate G<¯αi−1as a GνK-module. Elements inνf, degxf < ¯αiare precisely those that admit homogeneous i-standard expansions where Qi−1appears with exponents strictly smaller than αi. By part (1) of this Proposition such standard expansions generate G<¯αias a GνK-algebra, hence also as a GνK-module by Lemma 2.6 (since αiis the degree of the minimal polynomial of inνQi−1over GνK[inνQi−1]). It remains to consider the case when iis a limit ordinal. Take an ordinal i0such that i=i0+. We have (3.50) GνK[inνQi]⊂G<¯αi0⊂G<¯αi, by Remark 3.16; hence both inclusions are equalities by part (1) of this Proposition. By the induction assumption, elements of the form inxg,g∈K[x], degxg < ¯αi−1, generate G<¯αi0=G<¯αias a GνK-module, which completes the proof of (2). □ Proposition 3.32. Take an element hof K[x]and an ordinal i∈Λ\ {0}. Assume that (3.51) degxh < ¯αi. Then there exists an ordinal i0such that i∈ {i0+ 1, i0+}and ν(h) = νi0(h). Proof. For an ordinal i0< i we will denote by (3.52) h= s X j=0 cj,i0Qj i0, the i0-standard expansion of h. Let Si0(h) be as defined in (3.42). First, assume that iis not a limit ordinal; put i0=i−1. By (3.51) we have s<αiin (3.52). Since the degree of inνQi−1 over GνK[inνQi−1]∗is αiby (3.10) and P j∈Si−1(h) inνcj,i−1¯ Qj i−1is a polynomial of degree strictly less than αiin ¯ Qi−1, we see that P j∈Si−1(h) inνcj,i−1inνQj i−1= 0 in Gν. The result now follows from Proposition 2.10. If iis a limit ordinal, the results follows immediately from the fact that, by Definition 3.11, Qiis of the smallest degree among those polynomials that satisfy (3.12). □ Definition 3.33. Let {Qi}i∈Λbe a set of key polynomials. We say that {Qi}i∈Λis complete for ν(or that {Qi}i∈Λis a complete set of key polynomials for ν) if for each β∈Γ the additive group Pβ∩K[x] is generated by standard monomials of the form a s Q j=1 Qγj ij,a∈K, such that s P j=1 γjν(Qij) + νK(a)≥β. The collection Q={Qi}i∈Λis said to be ˜ Γ0-complete if for all β∈˜ Γ0every polynomial f∈K[x] with ν(f) = βbelongs to the additive group generated by standard monomials of the form a s Q j=1 Qγj ij,a∈K, such that s P j=1 γjν(Qij) + νK(a)≥β. 218 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Note, in particular, that if Qis a complete set of key polynomials then their images inνQi∈Gν rationally generate Gνover GνK; if Qis a ˜ Γ0-complete set of key polynomials then their images inνQi∈Gνrationally generate ˜ Gνover GνK(see page 3 for the definition of ˜ Gν). Remark 3.34.The set Qis a complete set of key polynomials if and only if for each polynomial f∈K[x] there exists an ordinal ℓsuch that ν(f) = νℓ(f). Indeed, assume that such an ordinal exists for all f. Take any β∈Γ and let f∈Pβ∩K[x]. Put β′=ν(f) and let ℓbe such that β′=ν(f) = νℓ(f). Write f= sℓ P j=0 dj,ℓQj ℓ, where each dj,ℓQj ℓ∈Pβ′∩K[x]⊂Pβ∩K[x]. Conversely, take f∈K[x]. Let β=ν(f). Write fas a finite sum (3.53) f=X γ dγQγdγ∈K, of standard monomials with ν(dγQγ)≥βfor all γsuch that dγ= 0. Let ℓdenote the greatest ordinal such that Qℓappears in one of the monomials dγQγ. Then (3.53) can be rewritten as f= s P j=0 djQj ℓ, where each djis a Qℓ-free ℓ-standard expansion; in particular, degxdj<¯αℓ. We obtain β=ν(f)≥νℓ(f) = min j¶νÄdjQj ℓä©≥min γ{ν(dγQγ)} ≥ β. This also shows that if Qis a complete set of key polynomials then Qis not strictly contained as an initial segment in any other set of key polynomials; in other words, the construction of key polynomials cannot be continued beyond Q. Proposition 3.35. If Λhas a maximal element iand (3.54) βi/∈˜ Γ0, then inνQiis transcendental over GνK[inνQi]. Proof. Take a non-zero polynomial F(¯ Qi) = s P j=0 ¯cj¯ Qj i∈GνK[inνQi][ ¯ Qi]. By (3.54) the terms in the expression F(inνQi) = s P j=0 ¯cjinνQj ihave different orders for different j(where, by definition, ord ¯ Qi=βi); in particular, there exists a unique jmin ∈ {0, . . . , s}that minimizes ord ¯cjinνQj i. By the ultrametric triangle inequality, we have F(inνQi)= 0, as desired. □ Proposition 3.36. Take an ordinal i∈Λ. Assume that inνQiis transcendental over GνK[inνQi]. Then the set {Qℓ}ℓ∈Λ={Qℓ}ℓ≤iof key polynomials is complete for ν. Proof. Take an element h∈K[x]. Let (3.55) h= s X j=0 cj,iQj i be the Qi-expansion of h. We want to prove that νi(h) = ν(h). Replacing hby P j∈Si(h) cj,iQj idoes not change the problem. Thus we may assume that all the terms cj,iQj iappearing in (3.55) have value νi(h). Since inνQiis transcendental over GνK[inνQi], we have P j inν(cj,iQj i)= 0. The Proposition now follows from Proposition 2.10.□ KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 219 Proposition 3.37. Take an element hof K[x]and an ordinal i∈Λ. Assume that at least one of the following conditions holds: (1) (3.56) ν(h)< βi and (3.57) h∈RνK[x] or (2) (3.58) sup {βi′|i′< i}=∞. Then ν(h) = νi(h). Proof. Let (3.59) h= s X j=0 cjQj i, be an i-standard expansion of h. First, assume that {βi′|i′< i}is unbounded in ˜ Γ0; in particular, (3.60) βi>˜ Γ0. Then the Proposition holds by Propositions 3.35 and 3.36. Next, suppose that (3.56)–(3.57) hold and sup {βi′|i′< i}<∞. Since (3.59) is obtained from hby iterating Euclidean division by Qiwhich is monic, and in view of Proposition 3.29, we have (3.61) ν(cj)≥0 for all j∈ {0, . . . , s}. By definition of standard expansion, each cjin (3.59) is a Qi-free i-standard expansion. Then νi(cj) = ν(cj) for 0 ≤j≤s. By (3.56) and (3.61), (3.62) νÄcjQj iä=ν(cj) + jβi> ν(h) for j > 0. so (3.63) ν(c0) = ν(h)< ν(cj) + jβi=νi(cj) + jβifor all j > 0. In other words, in the sum (3.59) the νi-value (resp. the ν-value) νi(c0) = ν(c0) of c0is strictly smaller than the νi-values (resp. the ν-values) νi(cjQj i) = ν(cjQj i) of all the other terms. It is well known and follows easily from the ultrametric triangle law that in this situation we have νi(h) = νi(c0) = ν(c0) = ν(h), as desired. □ For b∈N0, let ∂bdenote the b-th Hasse derivative with respect to x. Proposition 3.38. For all b∈Nand all i∈Λ, there exists an ordinal i0< i such that i∈ {i0+ 1, i0+} and (3.64) νi0(∂bQi) = ν(∂bQi). 220 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Proof. If iis not a limit ordinal, put i0=i−1. If iis a limit ordinal, take i0such that (3.65) i=i0+. The result now follows from the fact that degx∂bQi<degxQi, where in the case when iis a limit ordinal we must take i0sufficiently large subject to (3.65). □ Proposition 3.39. (1) The map νiis a valuation. (2) For every ordinal q < i and every f∈K[x]we have νq(f)≤νi(f)≤ν(f). Proof. It is obvious that νisatisfies the ultrametric triangle law. To prove (1) of the Proposition, we must prove the equality (3.66) νi(fg) = νi(f) + νi(g). For an ordinal i′∈Λ let (1)i′and (2)i′denote, respectively, (1) and (2) of the Proposition with ireplaced by i′. We proceed by transfinite induction on i. (1)0is easy to prove and (2)0is vacuously true. Assume that (1)i′and (2)i′hold for all ordinals i′< i. To prove (1)iand (2)i, we start with some preliminary lemmas. For future reference we state some of the lemmas in slightly greater generality than needed for the proof of Proposition 3.39. Consider an ordinal i0< i and t∈N0such that i=i0+, i+t∈Λ and for each ordinal i′ such that i<i′≤i+twe have (3.67) αi′= 1. Lemma 3.40. Consider two terms of the form dQj i+tand d′Qj′ i+t, where j, j′∈N0and dand d′are Qi+t-free (i+t)-standard expansions. Assume that (3.68) νi0ÄdQj i+tä≤νi0Äd′Qj′ i+tä, (3.69) νÄdQj i+tä≥νÄd′Qj′ i+tä, (3.70) νi0(d) = ν(d) and (3.71) νi0(d′) = ν(d′) Then j≥j′. If at least one of the inequalities (3.68), (3.69) is strict then j > j′. Remark 3.41.If i=i0+1 then assumptions (3.70) and (3.71) hold automatically by Corollary 3.15 and the definition of νi0. In the general case, Proposition 3.32 and (2)qfor q < i imply that there exists i0such that i0+ = iand (3.70) and (3.71) hold. Proof of Lemma 3.40.We have (3.72) νi0(Qi+t)≤αiβi0< βi+t by Remark 3.24 and Proposition 3.26. Since νi0is a valuation by (1)i0, the inequalities (3.68)– (3.69) can be rewritten as (3.73) ν(d) + jνi0(Qi+t)≤ν(d′) + j′νi0(Qi+t) and (3.74) ν(d) + jβi+t≥ν(d′) + j′βi+t Subtract (3.73) from (3.74) and use (3.72). The result follows. □ KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 221 Corollary 3.42. Keep the notation of the last lemma. Assume that (3.75) νi0 t−1 X q=0 zi+q!=ν t−1 X q=0 zi+q! in the notation of (3.33) (note that by Proposition 3.32 such an i0always exists). We have (3.76) νi0(Qi+t) = αiβi0 Proof. By Proposition 3.19 we may assume that (3.33) is an i0-standard expansion of Qi+t. The leading term of this i0-standard expansion is Qαi i0. We have αiβi0=νi0Qαi i0. Now Lemma 3.40, applied with t=j= 0 and j′= 1, implies that νi0Qαi i0< νi0Çt−1 P q=0 zi+qå. This completes the proof. □ Keep the above notation. Let fbe a non-zero element of K[x]. Let (3.77) f= si0 X j=0 dj,i0Qj i0 be an i0-standard expansion of f, where each dj,i0is a Qi0-free i0-standard expansion. Consider an (i+t)-standard expansion of f: (3.78) f= si+t X j=0 dj,i+tQj i+t, where the dj,i+tare Qi+t-free standard expansions. Let δ=δi0(f). Let µ= min 0≤j≤si+t νi0Ädj,i+tQj i+tä and Si0,i+t=nj∈ {0, . . . , si+t}νi0Ädj,i+tQj i+tä=µo. Assume that (3.75) holds and that νi0(dj,i+t) = ν(dj,i+t) for all j∈Si0,i+t(note that by Proposition 3.32 and (2)q,q < i, this holds for all sufficiently large ordinals i0such that i0+ = i). Lemma 3.43. (1) We have νi0(f) = µ= min 0≤j≤si+t {ν(dj,i+t) + jαiβi0}. (2) Let j0= max Si0,i+t. Then δ=αij0+δi0(dj0,i+t). Proof. (1) The second equality in (1) of the Lemma is given by Corollary 3.42 and (1)i0. Let θ= min Si0,i+t. Let ¯ f=P j∈Si0,i+t dj,i+tQj i+t. Then νi0f−¯ f> µ, so to prove that νi0(f) = µit is sufficient to prove that (3.79) νi0¯ f=µ. The equality (3.79) holds if and only if (3.80) νi0ÄQ−θ i+t¯ fä=µ−θαiβi0. 228 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Now, the left-hand side of (4.24) is a polynomial of degree δin ¯ Qi, while the right-hand side is divisible by the non-constant polynomial gδ 1,i. This implies that (4.25) t= 1, t Y j=2 gγj,i j,i = 1, and inih= inνdδ,igδ 1,i. (4.10) now follows from (4.9) and (4.17). The equality (4.11) follows from (4.15), (4.25) and the fact that θi+1(h) = δi+1(h) = δ. (3) Assume that δi+1(h) = δ. Fix an integer j > δ. The Qi+1-expansion (4.13) of his obtained from its Qi-expansion (4.1) by making the substitution Qi=Qi+1 −ziand performing repeated Euclidean divisions by Qi+1 to turn the result into a Qi+1-expansion. For j′< j, monomials of the form dj′,iQj′ ihave degrees strictly less than j¯αi+1. Hence they contribute nothing to dj,i+1Qj i+1; in other words, the coefficient dj,i+1 is completely determined by si P j′=j dj,′iQj′ i. Fix an integer j′∈ {j, . . . , si}. Write (4.26) dj′,iQj′ i=dj′,i (Qi+1 −zi)j′ =dj′,i j′ X k=0 Çj′ kå(−1)kQk i+1zj′−k i, where ziis a Qi-free i-standard expansion. Again, the terms on the right-hand side of (4.26) with k > j contribute nothing to dj,i+1Qj i+1. For k≤j, let dj′,k,i denote the coefficient of Qj i+1 in the (i+ 1)-standard expansion of dj′,iQk i+1zj′−k i. To prove (3), it is sufficient to prove that for all j′∈ {j, . . . , si}and all k∈ {0, . . . , j}we have (4.27) νÄdj′,k,iQj i+1ä−νi+1(h)≥ν+ i(h)−νi(h). To prove (4.27), we start out by noting that (4.9) is an i-standard expansion of Qi+1. Hence (4.28) νi(Qi+1) = βi=ν(zi), where the last equality holds by Definition 3.11 (4). By Lemma 3.43,νiÄdj′,iQk i+1zj′−k iäequals the minimum of the νi-values of the terms appearing in its (i+ 1)-standard expansion, so νiÄdj′,iQk i+1zj′−k iä≤νiÄdj′,k,iQj i+1ä. Combining this with (4.28) and with Proposition 3.32 applied to dj′,k,i and the ordinal i+ 1, we obtain (4.29) ν(dj′,k,i) = νi(dj′,k,i)≥(j′−j)βi+ν(dj′,i). By definition of δi+1(h), since δi+1(h) = δand in view of (4.11), we have νi+1(h) = ν(dδ,i+1) + δβi+1 Combining this with (4.29) and using (4.11) again, we obtain νÄdj′,k,iQj i+1ä−νi+1(h) = ν(dj′,k,i)−ν(dδ,i+1)+(j−δ)βi+1 ≥(j′−j)βi+ν(dj′,i)−ν(dδ,i+1)+(j−δ)βi=νÄdj′,iQj′ iä−νdδ,iQδ i≥ν+ i(h)−νi(h), (4.30) as desired. This completes the proof of the Proposition. □ Corollary 4.11. For as long as the character δi(h)remains constant (that is, does not strictly decrease), the quantity ν+ i(h)−νi(h)is non-decreasing with i. Proof. Take the minimum over all jon the left-hand side of (4.12). □ KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 229 Remark 4.12.One way of interpreting Lemma 3.40, together with the inequalities (4.19)–(4.21) is that the characteristic vertex νdθi+1(h),i+1, θi+1(h)of ∆i+1(h) always lies above its pivotal vertex νdδi+1(h),i+1, δi+1(h). Corollary 4.13 (of Proposition 4.7).Assume that the set {i∈Λ|αi>1}is infinite. Then {Qi}i∈Λis a complete set of key polynomials. Proof. Take an element h∈K[x] and an index i∈Λ. If νi(h) = ν(h), there is nothing to prove. Assume that ν(h)> νi(h). Then δi(h)>0 by Remark 3.30. Proposition 4.7 (1) says that (4.31) δi+1(h)< δi(h) whenever αi+1 >1. Since the set {i∈Λ|αi>1}is infinite and the strict inequality (4.31) can occur for at most finitely many values of i, we have δi(h) = 0 for some i∈Λ. Then νi(h) = ν(h) by Remark 3.30.□ 5. Augmenting sets of key polynomials Suppose we are given a set of key polynomials {Qi}i∈Λthat is not complete for ν. In this section, we will construct a set {Qi}i∈Λ+where Λ+is a well-ordered set of order type less than ω×ω, and Λ ⫋Λ+. 5.1. Sets of key polynomials having a maximal element. Suppose first that Λ has a maximal element ℓ. Since {Qi}i∈Λis not complete, there exists h∈K[x] such that (5.1) νℓ(h)< ν(h). Let ¯ Qℓbe a new variable. Take a polynomial hsatisfying (5.1). By Proposition 4.4, we have (5.2) X j∈Sℓ(h) inνÄdj,ℓQj ℓä= 0 in Pνℓ(h) Pνℓ(h)+ ⊂Gν. By Corollary 4.6 the element βℓdetermines a side of ∆ℓ(h). Let (5.3) inνℓh=inνℓdδ,ℓ t Y j=1 gγj,ℓ j,ℓ , where δ=δℓ(h), be the factorization of inℓhinto monic, quasi-homogeneous irreducible factors in GνK[inνQℓ]¯ Qℓ(such a factorization exists and is unique by Remark 2.13). By (5.2), the element inνQℓis integral over GνK[inνQℓ]. Its minimal polynomial over GνK[inνQℓ] is one of the irreducible factors gj,ℓ of (5.3). Let αℓ+1 denote the degree of inνQℓover GνK[inνQℓ]. Renumbering the factors in (5.3), if necessary, we may assume that g1,ℓ is the minimal polynomial of inνQℓover GνK[inνQℓ], so that (5.4) αℓ+1 = deg ¯ Qℓg1,ℓ. Let (5.5) g1,ℓ =¯ Qαℓ+1 ℓ+ αℓ+1−1 X j=0 X ¯γℓ ¯cℓ+1,j,¯γℓinνQ¯γℓ ℓ!¯ Qj ℓ be an ℓ-standard expansion of g1,ℓ. Let Xbe a new variable, and consider a lifting of the righthand side of (5.5) to K[X], that is, a polynomial of the form 230 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Xαℓ+1 + αℓ+1−1 P j=0 ÇP ¯γℓ cℓ+1,j,¯γℓQ¯γℓ ℓåXj, where inνcℓ+1,j,¯γℓ= ¯cℓ+1,j,¯γℓfor all the choices of ℓ,j, and ¯γℓ. Define the (ℓ+ 1)-st key polynomial of νto be (5.6) Qℓ+1 =Qαℓ+1 ℓ+ αℓ+1−1 X j=0 X ¯γℓ cℓ+1,j¯γℓQ¯γℓ ℓ!Qj ℓ. Let Λ+= Λ ∪ {ℓ+ 1}. By definition Qℓ+1 has the form (3.9). The set {Qi}i∈Λ+satisfies Definition 3.11: it is a set of key polynomials. In the special case when (5.7) αℓ+1 = 1 we will define several consecutive key polynomials at the same time. Assume that αℓ+1 = 1. Let Tdenote the set of all the polynomials of the form Q′=Qℓ+w, where degxw < ¯αℓ= degxQℓ. To define Qℓ+1, consider two cases: Case 1. The set ν(T) contains a maximal element. Let Q′=Qℓ+wbe an element of Tfor which the maximum is attained. Write w= s P t=0 zℓ+t+ ˜w, where s∈N0, for each t∈ {0, . . . , s} the expression zℓ+tis a homogeneous Qℓ-free ℓ-standard expansion, such that (5.8) βℓ=ν(zℓ)< ν(zℓ+1)<· · · < ν(zℓ+s)< ν (Q′) and ˜wis a Qℓ-free ℓ-standard expansion all of whose terms have value greater than or equal to ν(Q′). Put Λ+= Λ ∪ {ℓ+ 1, . . . , s + 1}and Qi=Qℓ+zℓ+· · · +zi−1for ℓ+ 1 ≤i≤ℓ+s+ 1. Case 2. The set ν(T) does not contain a maximal element. Let Ę Qℓ+t=Qℓ+ ˜wtät∈N0 be a sequence of elements of Tsuch that the sequence ÄνĘ Qℓ+täät∈N0 is strictly increasing and cofinal in ν(T). We will now define, recursively in q, an infinite sequence (5.9) (zℓ+q)q∈N0 of homogeneous Qℓ-free ℓ-standard expansions of strictly increasing values and a sequence (wt)t≥−1consisting of certain partial sums of the sequence (5.9). We adopt the convention that zℓ−1=w−1= 0. Assume that for certain integers t0, q0the finite sequences (zℓ+q)q≤q0and (wt)t≤t0are already defined, that wt0= q0 P q=0 zℓ+qand ν(zℓ+q)< ν Ę Qℓ+t0äfor all q≤q0. Write ˜wt0+1 −wt0= q1 P q=q0+1 zℓ+q+w′ t0+1, where each zℓ+qis a homogeneous Qℓ-free ℓ-standard expansion, ν(zℓ+q0+1)<· · · < ν(zℓ+q1)< ν Ę Qℓ+t0+1äand w′ t0+1 is a Qℓ-free ℓ-standard expansion, each of whose terms has value greater than or equal to νĘ Qℓ+t0+1ä. Put wt0+1 := wt0+ q1 X q=q0+1 zℓ+q. This completes the recursive definition of the infinite sequences (zℓ+q)q∈N0and (wt)t≥−1. Define αℓ+t= 1, Qℓ+t=Qℓ+zℓ+zℓ+1 +· · · +zℓ+t−1for t∈N, KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 231 and put Λ+= Λ ∪ {ℓ+t}t∈N. In both Cases 1 and 2, for each tunder consideration we have ν(Qℓ+t) = ν(zℓ+t)< ν(Qℓ+t+1) = ν(zℓ+t+1). Thus, by the choice of the sequences ÄνĘ Qℓ+täät∈N0 , (zℓ+q)q∈N0and (wt)t≥−1, conditions (a)–(d) of Definition 3.11 are satisfied for all the ordinals iof the form i=ℓ+t,t∈N0. Therefore in all cases the set {Qi}i∈Λ+is a set of key polynomials for ν. Remark 5.1.We claim that Qℓ+1 is an irreducible polynomial in x. Indeed, consider a factorization Qℓ+1 =fg in K[x]. Passing to the natural images of Qℓ+1,fand gin GνK[inνQℓ]¯ Qℓ∼ =Gνℓ, we obtain g1,ℓ = inℓfinℓg. Since g1,ℓ is an irreducible polynomial in ¯ Qℓby definition, we have, up to interchanging fand g, (5.10) deg ¯ Qℓinℓf=αℓ+1. Then (5.11) degxf≥αℓ+1 degxQℓ= degxQℓ+1, where the equality holds since g1ℓhas the form (5.5). We must have equality in (5.11) and degxg= 0. Thus g∈K; this completes the proof of the irreducibility of Qℓ+1 in K[x]. Similarly, in the case when (5.7) holds, Qℓ+tis irreducible for all t∈Nfor which Qℓ+tis defined. This follows from the above argument by induction on t. 5.2. Augmenting sets of key polynomials without maximal elements. Suppose that the set Λ does not have a maximal element. Since the set {Qi}i∈Λof key polynomials is not complete, by Corollary 4.13 the degrees of the polynomials Qi,i∈Λ, are bounded in N. Hence there exists ℓsuch that for each i∈Λ, i>ℓ, we have i=ℓ+tand αℓ+t= 1 for t∈N. Since this set of key polynomials is not complete for ν, there exists a monic polynomial hsuch that (5.12) νℓ+t(h)< ν(h) for all t∈N. In this case, define Qℓ+ωto be a smallest degree monic polynomial hsatisfying (5.12). Remark 5.2.The inequality (5.12) implies that (5.13) degxQℓ+ω≥degxQℓ= degxQℓ+tfor all t∈N. by Proposition 3.32. If the inequality in (5.13) were an equality, we would have a contradiction with the condition (d) of Definition 3.11. Thus, degxQℓ+ω>degxQℓ= degxQℓ+t,t∈N. For each t∈N, the expression Qℓ+t=Qℓ+t+1 −zℓ+tis an (ℓ+t+ 1)-expansion of Qℓ+t. Thus, in view of Proposition 3.29,h=Qℓ+tsatisfies the hypotheses of Proposition 3.37 (1) with i=ℓ+t+ 1. We obtain νℓ+t+1 (Qℓ+t) = ν(Qℓ+t). To summarize, we have (5.14) ν(Qℓ+t+1) = νℓ+t+1(Qℓ+t+1)> νℓ+t+1(Qℓ+t) = ν(Qℓ+t). Let ¯ β= sup {ν(Qℓ+t)|t∈N}. (here we allow the possibility ¯ β=∞, which means that the set {ν(Q′)|Q′∈T}is unbounded in ˜ Γ0). 232 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY We put Λ+= Λ ∪ {Qℓ+ω}. By Remark 3.18 and Proposition 3.19, for every t∈N0the polynomial Qℓ+ωadmits an (ℓ+t)-standard expansion (3.11): (5.15) Qℓ+ω= αℓ+ω X j=0 cj,ℓ+tQj ℓ+t. By (5.12), the inequality (3.12) holds for i=ℓ+ωand i0=ℓ+t. To complete the proof that {Qi}i∈Λ+is a set of key polynomials for ν, it remains to prove (3.14) and (3.15), assuming (3.13) (with ireplaced by ℓ+ωand i0replaced by ℓ+t,t∈N). Therefore, assume that the sequence (βℓ+t)t∈Nhas an upper bound (but no maximum) in ˜ Γ0. To simplify the notation, for the purposes of the next Proposition we will denote Qℓ+ωby f. We have (5.16) degQℓf:= ïdegxf degxQℓò≥δℓ(f). By Proposition 4.7 there exists t0∈Nsuch that (5.17) δℓ+t(f) = δℓ+t0(f) for all t≥t0 (in fact, (5.17) holds already for t0= 1, but we have not proved that yet). Let δdenote the stable value of δℓ+t(f) for large t. The inequality (5.16) implies that (5.18) degQℓf≥δ. The next Proposition says that equality holds in (5.18). In what follows, the index iwill run over the set {ℓ+t}t∈N0. Proposition 5.3. For each i∈ {ℓ+t}t∈N0 we have (5.19) degxf=δdegxQi and (5.20) ¯ β≤1 δν(f). Proof. By (5.12) for all t∈N0we have ν(f)> νℓ+t(f) = δν(Qℓ+t). This proves (5.20). The main point is to prove (5.19). Our strategy for doing this consists in gradually modifying fwhile preserving the numerical character δi(f) and the condition (5.21) νi(f)< ν(f) for all iof the form i=ℓ+t, t ∈N though possibly changing degxfin the process, until we arrive at a polynomial of degree δ¯αi. Since αi= 1 for all i, degxQiis independent of i, so all the i-standard expansions of fhave the same degree αℓ+ωin Qi. For each i, let (5.22) f= αℓ+ω X j=0 aj,iQj i be an i-standard expansion of f. Lemma 5.4. There exists a polynomial a∗∈K[x]of degree strictly less than degxQℓsuch that (5.23) inνa∗inνaδ,ℓ = 1 in Gν. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 233 Proof. Let ℓ−denote the smallest ordinal such that ¯αℓ−= ¯αℓ. By Proposition 3.32 (applied to h=aδ,ℓ), there exists an ordinal ℓ0< ℓ−such that ℓ−=ℓ0+ and (5.24) νℓ0(aδ,ℓ) = ν(aδ,ℓ). By (5.24) and Proposition 3.49 (4) we have inνaδ,ℓ ∈GνK[inνQℓ0+1] = GνK[inνQℓ0] [inνQℓ0]. By Definition 3.11, inνQℓ0is integral over GνK[inνQℓ0+1] of degree αℓ0+1. By Lemma 2.6 and transfinite induction on ℓ0, the graded algebras (5.25) GνK[inνQℓ0]⊂GνK[inνQℓ0] [inνQℓ0] are saturated. Hence the homogeneous element inνaδ,ℓ ∈GνK[inνQℓ0] [inνQℓ0] has a multiplicative inverse ¯a∗∈GνK[inνQℓ0] [inνQℓ0]. Again by Lemma 2.6, ¯a∗admits an ℓ0-standard expansion whose degree in inνQℓ0is strictly less than αℓ0+1. A lifting of this ℓ0-standard expansion to K[x] is the desired element a∗.□ Note that by Proposition 4.7 (2) and transfinite induction on i, for all i≥ℓ (5.26) inνaδ,ℓ = inνaδ,i and inif= inνaδ,i(¯ Qi+ inνzi)δ. Hence, in view of (5.23) and (5.26), we have (5.27) ini(a∗f)=(¯ Qi+ inνzi)δ. Now, ¯ Qi+ inνziis the minimal algebraic relation satisfied by inνQiover GνK[Qi], so this polynomial maps to 0 under the homomorphism ϕof Proposition 3.49 (2). Therefore ¯ Qi+ inνziδ∈Ker ϕ. Together with (5.27) and Proposition 3.49 (3)–(4) this implies that (5.28) ν(a∗f)> νi(a∗f) for all i. We claim that (5.29) δi(a∗f) = δfor all i. Indeed, applying Lemma 3.47 with s= 2 to the pairs of polynomials (f1, f2) = (aδ,i, a∗) and (f1, f2) = (aδ−1,i, a∗), we see that after multiplying fby a∗and applying Euclidean division of a∗fby Qito obtain the i-standard expansion of a∗f, only the remainders in the Euclidean division contribute to ini(a∗f). This means that the powers of ¯ Qithat appear in ini(a∗f) with non-zero coefficients are exactly the same as those appearing in inifand (5.29) follows. Thus, replacing fby a∗f, we may assume that inνaδ,i = 1 for all i. Let (5.30) θ(i) = 1 2min ν+ i(f)−νi(f), βi−βℓ; we have θ(i)>0. By Corollary 4.11 the quantity ν+ i(f)−νi(f) is non-decreasing with iand hence so is θ(i). Taking into account the fact that ¯ β= lim i→∞ βi, we have, for isufficiently large, (5.31) ν(aδ,i) + δ¯ β−νi(f) = δ(¯ β−βi)< θ(i). By choosing ℓ1> ℓ sufficiently large, we may assume that (5.31) holds for i≥ℓ1. 234 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY For each i≥ℓ1, write aδ,i = 1 + a† iwith (5.32) νÄa† iä>0. Write f=¯ fi+˜ fi, where ¯ fi=Qδ i+ δ−1 X j=0 aj,iQj i and ˜ fi=a† iQδ i+ ni X j=δ+1 aj,iQj i. We want to compare the ℓ1-standard expansion of fwith its i-standard expansion for i > ℓ1 and, in particular, to study the dependence on iof aδ,i and a† i:= aδ,i −1. First of all, for all jwith δ < j ≤nℓ1and all i≥ℓ1we have (5.33) νiÄaj,ℓ1Qj ℓ1ä−δβi≥νℓ1Äaj,ℓ1Qj ℓ1ä−δβℓ1−δ(βi−βℓ1)≥ν+ ℓ1(f)−νℓ1(f)−δ(¯ β−βℓ1)> θ(ℓ1), where: the first inequality holds by Proposition 3.39 (2) the second inequality holds by the definitions of ν+ ℓ1(f) and of ¯ βand the third inequality holds by (5.30)–(5.31). For i>ℓ1, write Qi=Qℓ1+wi, where wiis a Qi-free i-standard expansion (in particular, degxwi<¯αi= ¯αℓ1. To compute the coefficient ai,δ in the i-standard expansion of f=¯ fℓ1+˜ fℓ1, we must consider the expressions (5.34) Qδ ℓ1+ δ−1 X j=0 aj,ℓ1Qj ℓ1= (Qi−wi)δ+ δ−1 X j=0 aj,ℓ1(Qi−wi)j and a† ℓ1Qδ ℓ1+ nℓ1 X j=δ+1 aj,ℓ1Qj ℓ1=a† ℓ1(Qi−wi)δ+ nℓ1 X j=δ+1 aj,ℓ1(Qi−wi)j, open the parentheses and perform the appropriate Euclidean divisions by Qi. We have degx δ−1 X j=0 aj,ℓ1(Qi−wi)j< δ¯αi. As well, every term in the Newton binomial expansion of (Qi−wi)δexcept for Qδ ihas degree strictly smaller than δ¯αi. Therefore no terms in (5.34) contribute anything to a† i. By (5.33), all the contributions to a† iby terms of the form aj,ℓ1Qℓ1,j > δ, have νi-value strictly greater than θ(ℓ1). It remains to study the contribution to a† ifrom a† ℓ1(Qi−wi)δ= δ P j=0 δ ja† ℓ1wj iQδ−j i. For j= 0 this contribution equals a† ℓ1. For each j∈ {1, . . . , δ}this contribution is nothing but the coefficient djof Qj iin the i-standard expansion of a† ℓ1wj i. We have ν(dj)≥νi(dj)≥βi−βℓ−j(βi−βℓ1)> θ(ℓ1), KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 235 where the second inequality follows from Lemma 3.47, applied with s=j+ 1, f1=a† ℓ1, f2=· · · =fs=wi, i+treplaced by iand i0replaced by ℓ. Putting together all of the above information, we obtain (5.35) νiÄa† iä≥min ¶θ(ℓ1), ν Äa† ℓ1ä©. Take an ordinal ℓ2of the form ℓ2=ℓ1+t1,t1∈N, such that ¯ β−βℓ2< ν Äa† ℓ1ä. Since for all i≥ℓ2we have νÄa† iä>0 and in view of the definition of δ, every term in the Qi-expansion of ˜ fihas value strictly greater than δβi. Hence νĘ fℓ2ä≥νiĘ fℓ2ä> νi¯ fℓ2 which implies that νi¯ fℓ2=νi(f)<min ¶ν(f), ν Ę fℓ2ä©≤νÄf−˜ fℓ2ä=ν¯ fℓ2. Since degx¯ fℓ2=δdegxQℓ≤degxfand fwas chosen of minimal degree subject to inequality (5.21), we must have degxf= degx¯ fℓ2=δdegxQℓ.□ Corollary 5.5. We have equalities (3.14) and (3.15) (with ireplaced by ℓ+ωand i0replaced by ℓ+t,t∈N). In particular, the set {Qi}i∈Λ+is a set of key polynomials for ν. Proof. This follows immediately from (5.19) and Proposition 4.7 (2) (specifically, the equality (4.10)). □ Below, in Proposition 8.6, we will show that δ(f) is of the form δ(f) = pe0for some e0∈N0. Together with Remark 5.2 this will prove that, under the assumptions of this section, we have char kν>0 and e0>0. Proposition 5.6. If ν(Qℓ+t)∈˜ Γ0for all t∈N0and the sequence (βℓ+t)t∈N0is cofinal in ˜ Γ0, then the set Qℓ+ωof key polynomials defined above is ˜ Γ0-complete. In other words, for every element β∈˜ Γ0+ every polynomial h∈K[x]with ν(h) = βbelongs to the additive subgroup of Pβ∩K[x]generated by all the standard monomials in Qℓ+ω, multiplied by elements of K, of value βor higher. Proof. Take an element h∈K[x]. Without loss of generality, we may assume that, writing h= s P j=0 djxj, we have (5.36) νK(dj)≥0 for all j (otherwise, multiply hby a suitable element of K). In other words, we may assume that h∈RνK[x]. Since the sequence {βℓ+t}t∈N0is cofinal in ˜ Γ0, there exists iof the form i=ℓ+t, t∈N0, such that (5.37) βi> ν(h). Then hsatisfies the hypotheses of Proposition 3.37. Now, Proposition 3.37 says that νi(h) = ν(h). This means, by definition, that hcan be written as a sum of standard monomials in Qi+1 of value at least ν(h), hence it belongs to the additive abelian group generated by all such monomials. This completes the proof. □ 236 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY 6. Constructing a complete set of key polynomials In this section we will recursively construct a complete set of key polynomials. First, consider the set {Qi}i∈Λ, with Q0=xand Λ = {0}. It is a set of key polynomials. Next, assume that a set {Qi}i∈Λof key polynomials is constructed and that Λ < ω ×ω. If Λ does not have a maximal element then there exists and ordinal ℓsuch that {ℓ+t|t∈N0}is a subset of Λ, cofinal in Λ. If the set {Qi}i∈Λis complete for ν, put ¯ Λ := Λ and stop. Otherwise, consider the set {Qi}i∈Λ+of key polynomials constructed in the previous section. If the set {Qi}i∈Λ+of key polynomials is complete, put ¯ Λ := Λ+and stop here. Otherwise, replace {Qi}i∈Λby {Qi}i∈Λ+ and repeat the procedure. Remark 6.1.If Q={Qi}i∈Λis a set of key polynomials, i0, i ∈Λ, iis a limit ordinal and i0+ = i then (6.1) ¯αi>¯αi0 by Remark 5.2. Therefore, if as a result of the above recursive procedure we arrive at a set of key polynomials with Λ = ω×ω, since Λ contains infinitely many limit ordinals, such a set of key polynomials must have unbounded degrees and is therefore complete by Proposition 3.14 (1) and Corollary 4.13. This proves that the aobve recursive procedure produces a complete set of key polynomials after at most ω×ωsteps. In other words, ¯ Λ≤ω×ω. We have proved the following: Theorem 6.2. The well-ordered set Q:= {Qi}i∈¯ Λconstructed above is a complete set of key polynomials. In other words, for every element β∈Γthe Rν-module Pβ∩K[x]is generated as an additive group by all the monomials in the Qiof value βor higher, multiplied by elements of K. In particular, we have M β∈Γ Pβ Pβ+ =GνK[inνQ]∗. In §8we will fix an ordinal ℓsuch that ℓ+ω∈¯ Λ and will study further properties of Qℓ+ω. Among other things, we will show (Propositions 8.6 and 8.10 and Remark 8.7) that: (a) if char kν= 0 then our construction gives a complete set of key polynomials that is of order type at most ω+ 1. (b) if, in addition, rank ν= 1 then the construction produces a complete set of key polynomials that is of order type at most ω. In the next section we study the effect of differential operators on the polynomials Qiin order to give a more precise description of the form of limit key polynomials. 7. Key polynomials and differential operators This section is devoted to proving some basic results about the effect of differential operators on key polynomials. Here and below, for a non-negative integer b,∂bwill denote the b-th Hasse (or formal) derivative, defined in the Introduction. Given an ℓ-standard expansion h, we are interested in proving lower bounds on (and, in some cases, exact formulae for) the quantities ν(∂bh) and νℓ(∂bh) and in computing the elements inν∂bhand inℓ∂bh. In particular, we will give sufficient conditions for the element ∂bhto be non-zero. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 237 Assume given a complete set Q:= {Qi}i∈¯ Λof key polynomials. Take an ordinal i∈¯ Λ. Let bidenote the smallest positive integer which maximizes the quantity (7.1) βi−ν(∂biQi) bi (later in this section, we will show that biis necessarily of the form peifor some ei∈N0and, in particular, that bi= 1 if char kν= 0). Let hbe an element of K[x]. We use the following convention for binomial coefficients: if s<t, the binomial coefficient s tis considered to be 0. We view the binomial coefficients as elements of Kvia the natural map Z→K. Notation: Let pbe as defined in the Introduction. If p > 1, for an integer awe shall denote by ν(p)(a) the p-adic value of a, that is, the greatest power of pthat divides a. If p= 1, we adopt the convention ν(p)(a) = 1 for all non-zero aand ν(p)(0) = ∞. Remark 7.1.Consider e, b, b′∈Nsuch that b | pe(this holds, in particular, whenever b < pe) and pe|b′. Then (x+ ∆x)b′∈Kxpe,∆xpe, so ∂bxb′= 0. Proposition 7.2. Take an element h∈K[x]\ {0}. (1) For all b∈N0we have (7.2) νi(h)−νi(∂bh)≤b bi (βi−ν(∂biQi)) . (2) Let h= s P j=0 dj,iQj ibe an i-standard expansion of h. Assume that nj∈ {0, . . . , s}νÄdj,iQj iä=νi(h)o={0} (in particular, we have s > 0). Let dj,iQj idenote the term in the i-standard expansion of hwhich minimizes the triple ÄνiÄdj,iQj iä, ν(p)(j), jäin the lexicographical ordering. Let e=ν(p)(j)and b(i, h) = bipe. Then equality holds in (7.2) for b=b(i, h). Remark 7.3.For all b∈Nwe have degx∂bQi<¯αi. By Proposition 3.32 there exists an ordinal i0such that i0+ = iand (7.3) ν(∂bQi) = νi0(∂bQi). In particular ν(∂biQi) = νi0(∂biQi). Thus replacing ν(∂biQi) by νi0(∂biQi) in (7.2) gives rise to an equivalent inequality. Also, νi(∂bh)≤ν(∂bh), so replacing νi(∂bh) by ν(∂bh) in (7.2) gives rise to a true, but an a priori weaker inequality. Proof of Proposition 7.2.We prove Proposition 7.2 by transfinite induction. For i= 0 we have Qi=x,bi= 1 and b=pe. Write h= s P j=0 dj,0xj. For b= 0 and for b>s, (7.2) is trivially true. Assume that 0 < b ≤s. There exists j, 0 ≤j≤s, such that ν0(∂bh) = νÇÇj bådj,0xj−bå≥ν(dj,0)+(j−b)β0≥ν0(h)−bβ0, which gives (7.2). 244 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY (1) If equality holds in (7.2) then (7.33) pe+eib. (2) We have the following partial converse to (1). Assume that (7.33) holds and that (7.34) either b=pe+eior Ii,max ={bi}. Then equality holds in (7.2) if and only if (7.35) νÇÇ u b/pe+eiåå= 0. (3) Assume that (7.33)–(7.35) hold. Then (7.36) inνi∂bQ¯γi+1 i+1 =Çu b/pe+eiåinνiÅQ¯γi iQγi−b bi i(∂biQi)b biã; in particular, ∂bQ¯γi+1 i+1 ≡ 0. Remark 7.11.If b=pe+eiholds in Proposition 7.10 (2) then b pe+ei= 1 and u b/pe+ei=u, so (7.35) holds automatically in this case. Proof of Proposition 7.10.We go through the proof of Proposition 7.2 and analyze the case of equality at each step. We start with a general remark about binomial coefficients in positive and mixed characteristic. Remark 7.12.If char kν= 0, we have (7.37) νÇÇγ jåå= 0 for all non-negative integers j≤γ; similarly, ν(Cγi(j1, . . . , jq)) = 0 for every γiand every qtuple (j1, . . . , jq) as in (7.18). If char kν=p > 0, the following is a well known characterization of the equality (7.37). Let γ=k0+pk1+· · · +psksand j=t0+pt1+· · · +psts, with k0, . . . , ks, t0, . . . , ts∈ {0,1, . . . , p−1}, denote the respective p-adic expansions of γand j(where we allow one of the (s+ 1)-tuples (k0, . . . , ks) and (t0, . . . , ts) to end in zeroes). Then (7.37) holds if and only if (7.38) kj≥tjfor all j∈ {0, . . . , s}. We recall the proof for the reader’s convenience. For a positive integer n, recall that ν(p)(n!) denotes the p-adic value of n!. If n=n0+pn1+· · · +psnsis the p-adic expansion of n, we have ν(p)(n!) = n1+p2−1 p−1n2+· · · +ps−1 p−1ns. Let γ−j=l0+pl1+· · · +pslsbe the p-adic expansion of γ−j. First, suppose that (7.38) holds. Then kj=tj+ljfor all j. We have ν(p)(γ!) = k1+p2−1 p−1k2+· · · +ps−1 p−1ks,(7.39) ν(p)(j!) = t1+p2−1 p−1t2+· · · +ps−1 p−1ts,(7.40) ν(p)((γ−j)!) = l1+p2−1 p−1l2+· · · +ps−1 p−1ls (7.41) Thus ν(p)(γ!) = ν(p)(j!) + ν(p)((γ−j)!) and (7.37) holds. Conversely, assume that (7.38) is not true. Let (7.42) (j0, j0+ 1, . . . , j1−1, j1) KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 245 be a maximal subsequence of (1, . . . , s) consisting of consecutive integers such that kj=tj+lj for j0≤j≤j1. Then kj0=tj0+lj0−p,kj=tj+lj−p+1 for j0< j < j1and kj1=tj1+lj1+1. Thus the total contribution of (7.42) to ν(p)(γ!) −ν(p)(j!) −ν(p)((γ−j)!) is pj1−1 p−1− j1−1 X j=j0+1 (pj−1) −ppj0−1 p−1=j1−j0≥1. The quantity ν(p)(γ!) −ν(p)(j!) −ν(p)((γ−j)!) is obtained by summing the contributions of all the subsequences of the form (7.42), hence it is strictly positive, as desired. More generally, consider a finite set of positive integers d1, . . . , dasuch that a P ℓ=1 dℓ=γ. For ℓ∈ {1, . . . , a}, let dℓ=dℓ,0+pdℓ,1+· · · +psdℓ,s, with dℓ,j ∈ {0,1, . . . , p −1}, denote the p-adic expansions of dℓ(again, we allow the s-tuple (dℓ,0, dℓ,1, . . . , dℓ,s) to end in zeroes in order to be able to compare tuples of different lengths). Then (7.43) νÅγ! d1!·. . . ·da!ã= 0 if and only if a X ℓ=1 dℓ,j < p for all j∈ {0, . . . , s}. This is proved by induction on a, the case a= 2 having been treated above. This gives a helpful necessary and sufficient condition for the equality ν(Cγi(j1, . . . , jq)) = 0 which will be used in the sequel. One consequence of the equivalent conditions stated in (7.43) is (7.44) dℓ,j ≤kjfor all ℓ∈ {1, . . . , a}and j∈ {0, . . . , s}. Below, we will be particularly interested in the following special cases of (7.38): (1) If (7.45) γ=peuwith p | u then (7.37) implies that pe|j. (2) We have the following partial converse to (1): if γis as in (7.45) and j=pethen (7.38) holds. Indeed, we have te= 1, tj= 0 for j=eand ke≥1. In this case Çγ jå=Çpeu peå=peu(peu−1) ·. . . ·(peu−pe+ 1) pe!≡umod mν since peu−j pe−j≡1 mod mνfor all j∈ {1, . . . , pe−1}. This is the main situation in which Proposition 7.10 will be applied in this paper. In the next Lemma, let j0, . . . , jtbe as in the proof of Proposition 7.2. Lemma 7.13. (1) The inequality in (7.19) is strict unless jt∈Ii,max. (2) Let γiand bibe as in (7.31)–(7.32). Assume that j0= 0, and (7.46) jt∈Ii,max for 1≤t≤q. If (7.47) ν(Cγi(j1, . . . , jq)) = 0 then (7.48) pe+eib. (3) Let the assumptions be as in (2) and assume, in addition, that b=pe+ei. Then (7.47) holds if and only if q=peand j1=· · · =jq=bi. Proof. (1) is immediate from definitions. 246 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY (2) Let {pc1, . . . , pcℓ} ⊂ Ii,max with (7.49) ei≤c1< c2<· · · < cℓ denote the set of distinct natural numbers appearing among {j1, . . . , jq}(cf. (7.46) and Corollary 7.9). For 1 ≤j≤ℓ, let aj= #{t∈ {1, . . . , q} | jt≤pcj}; let a0= 0. Then (7.50) b= ℓ X j=1 (aj−aj−1)pcj. Assume that (7.47) holds. Apply Remark 7.12 (specifically, (7.44)), with aj−aj−1 playing the role of dj. By definition of e, we have pe|γi, so the first eentries in the p-adic expansion of γiare 0. By (7.44), the same must be true of each of aj−aj−1. In other words, (7.51) pe|ajfor 1 ≤j≤ℓ. (7.49)–(7.51) imply (7.48), as desired. (3) Assume, in addition, that b=pe+ei. “Only if”. From (7.49)–(7.51), we see that ℓ= 1 and a1=pe; the result follows immediately. “If”. By assumptions, we have ℓ=1=qand a1=pe. By (7.16) and Remark 7.12 (2), we have Cγi(j1, . . . , jq) = Cγi(bi, . . . , bi | {z } pe ) = Çγi peå=umod mν and the result follows. □ We can now finish the proof of Proposition 7.10. By (7.20) and Lemma 7.13 (1), the inequality in (7.21) is strict unless j0= 0, and (7.52) jt∈Ii,max. By Lemma 7.13 (3), equality (7.47) holds, so we may apply Lemma 7.13 (2). By Lemma 7.13 (2), the first inequality in (7.22) is strict unless j0= 0 and pe+ei|b. This proves (1) of the Proposition. (2) Assume that (7.33) holds. If b=pe+ei, by Lemma 7.13 (3) there is exactly one term on the right-hand side of (7.18) for which equality holds in (7.21), namely, the term with q=pe and j1=· · · =jq=bi. If Ii,max ={bi}, then by Lemma 7.13 (1) there is at most one term on the right-hand side of (7.18) for which equality holds in (7.21); if such a term exists, it is the term with q=b biand j1=· · · =jq=bi. Moreover, this term satisfies equality in (7.21) if and only if ν(C(bi, . . . , bi | {z } b/bi )) = νÄγi b/biä=νÄu b/pe+eiä= 0, where the second equality follows from Remark 7.12. In either case, there is at most one term on the right-hand side of (7.18) for which equality holds in (7.21), and there is exactly one such term if and only if νÄu b/pe+eiä= 0. This proves (2). (3) of the Proposition follows from (2) and (7.18). □ Let γi=k0+pk1+· · · +psks, KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 247 with k0, . . . , ks∈ {0,1, . . . , p−1}, denote the p-adic expansion of γi. Take integers s′∈ {0, . . . , s}, k′ s′∈ {0, . . . , ks′}. Let b= (k0+pk1+· · · +ps′−1ks′−1+ps′k′ s′)bi. Corollary 7.14. For this b, equality holds in (7.2) for the monomial h=Q¯γi+1 i+1 . The element ini∂bQ¯γi+1 i+1 is given by the formula (7.36). Proof. Repeated application of Proposition 7.10 (2) and (3), first k0times with breplaced by 1, then k1times with breplaced by p, and so on. □ Let h= s P j=0 dj,iQj ibe an i-standard expansion. Let Si=Si(h), where the notation is as in (3.42). Write inih=P j∈Si iniÄdj,iQj iä. Write bi=pei, as above. Let ebe the greatest non-negative integer such that for all j∈Siwe have pe|j. Proposition 7.15. (1) If equality holds in (7.2) then (7.53) pe+eib. (2) Assume that (7.54) b=pe+ei. Then equality holds in (7.2). In particular, we have ∂bh≡ 0. (3) Assume that (7.54) holds. Let Sb i=j∈Sipe+1 does not divide j. Then inνi∂bh=X j∈Sb i inνiÇÇj peådj,iQj−pe i(∂biQi)peå. Proof. (1), (2) and (3) of Proposition 7.15 follow, respectively, from (1), (2) and (3) of Proposition 7.10.□ Corollary 7.16. In the notation of Proposition 7.15, assume that (7.54) holds. We have (7.55) h /∈Kîxpe+ei+1 ó. Proof. Take bas in (7.54). Now the result follows from Proposition 7.15 (2). □ Let the notation be as in Proposition 7.15. Proposition 7.17. Take an element j∈Si. Write j=peu, where p | uif char kν=p > 0. Assume that (7.56) pe+1 j′for all j′∈Si, j′< j. Let u=t0+t1p+· · · +tspsbe the p-adic expansion of u. Then (7.57) νi(∂jbih) = νi(h)−j(βi−ν(∂biQi)), (7.58) inνi∂jbih= s Y q=1 tq!!inνidj,i (inνi∂biQi)j+terms involving inνiQi. For every j′=jwe have (7.59) νi(h)−νi(∂j′bih) j′≤νi(h)−νi(∂jbih) j, and the inequality is strict whenever j′/∈Sior j′< j. 248 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Proof. By (7.56) and Proposition 7.10 (1), terms of the form dj′,iQj′ iwith j′∈Si, j′< j satisfy strict inequality in (7.2) with b=jbi. Thus replacing hby s P j′=j dj′,iQj′ idoes not affect any of the statements of the Proposition. Apply Proposition 7.15 repeatedly t0+t1+· · · +ts times. By (2) of Proposition 7.15, (7.60) νiÄ∂jbiÄdj,iQj iää=νiÄdj,iQj iä−j(βi−ν(∂biQi)) and (7.61) νi(∂jbih) = νi(h)−j(βi−ν(∂biQi)); this proves (7.57). (7.58) follows from Proposition 7.15 (3), by induction on u. Finally, the last statement of the Proposition follows from Proposition 7.15 (1) and (3), by induction on u.□ Remark 7.18.Here is an alternative, more explicit explanation of (7.58). Take j′∈ {j, . . . , s} and apply (7.18) to one of the monomials appearing in dj′,iQj′ i(we take γi=j′and b=jbi in (7.18)), in order to decide which values of j′and which decompositions j0+· · · +jq=b contribute to ini∂bh. If either j′> j,q=j,j0= 0 or jt=bifor some t∈ {1, . . . , j}then, by definition of bi, the corresponding term in (7.18) is either divisible by Qior has νi-value strictly greater than νiÄdj,iQj iä−j(βi−ν(∂biQi)). This proves (7.58). Let P q cq,iQq idenote the i-standard expansion of ∂jbih. The above considerations prove that c0,i coincides with the coefficient of Q0 iin the i-standard expansion of dj,i (∂biQi)jmodulo an element of higher νi-value. In particular, c0,i = 0 and (7.62) ν(c0,i) = νi(c0,i). We have (7.63) ν(c0,i) = νi(∂jbih) = νiÄ∂jbiÄdj,iQj iää=νiÄdj,iQj iä−j(βi−ν(∂biQi)). Corollary 7.19. We have (7.64) νi(h) = min 0≤j≤s{νi(∂jbih) + j(βi−ν(∂biQi))} and the minimum in (7.64) is attained for all j∈Si, satisfying (7.56). 8. Infinite sequences of key polynomials In this section, we take an ordinal ℓsuch that ℓ+t∈¯ Λ and αℓ+t= 1 for all t∈N. Take an element h∈K[x]. Proposition 4.7 (1) implies that δℓ+t(h) stabilizes for tsufficiently large. Let δ(h) denote this stable value of δℓ+t(h). For a positive integer twe have δℓ+t(h) = 0 =⇒ν(h) = νℓ+t(h) =⇒δℓ+t+1(h)=0. Thus saying that ν(h) = νℓ+t(h) for all tsufficiently large is equivalent to saying that δℓ+t(h) = 0 for all tsufficiently large. Assume that there exists h∈K[x] such that (8.1) ν(h)> νℓ+t(h) for all t∈N (in other words, δℓ+t(h)>0 for all t∈Nand ℓ+ω∈¯ Λ); put h=Qℓ+ω. One of the three main results of this section says that δ(h) has the form pefor some e∈N0(in particular, δ(h) = 1 if char kν= 0). To prove this, we use differential operators and their properties derived in §7. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 249 The second main result of this section is the statement that if either char kν= 0 or p | δ(h) then the sequences (βℓ+t)t∈Nand (νℓ+t(h))t∈Nare unbounded in ˜ Γ0(this is precisely the situation of Proposition 5.6 of subsection 5.2); in particular, the set Qℓ+ωof key polynomials is ˜ Γ0-complete by Proposition 5.6. Finally, in Remark 8.7 we take ℓ= 1 and assume that αt= 1 for all t∈N and that the sequence {βt}t∈Nis unbounded in ˜ Γ0. We show that h∈Kxδ(h). Replacing ℓby ℓ+tfor a sufficiently large t, we may assume that δℓ+t(h) = δ(h) for all positive integers t. Below the ordinal iwill run over the set {ℓ+t|t∈N0}. By definition, for all such iwe have (8.2) Qi+1 =Qi+zi, where ziis a homogeneous Qℓ-free standard expansion of value βi(cf. Proposition 3.13). By Proposition 3.14 (2), we have (8.3) degxzi<degxQi. Finally, (8.4) inνQi=−inνzi by (5.14). As before, let h= si X j=0 dj,iQj i be an i-standard expansion of hfor i≥ℓ, where each dj,i is a Qℓ-free i-standard expansion. Note that since αℓ+t= 1 for t∈N0, we have degxQi= i Y j=2 αj= ℓ Y j=2 αj= degxQℓ and so (8.5) si=ïdegxh degxQiò=ïdegxh degxQℓò=sℓ. Proposition 8.1. For each iof the form i=ℓ+t,t∈N, we have bi+1 ≤bi. Proof. Write Qi+1 =Qi+zi, as above. Lemma 8.2. For each b∈Nwe have (8.6) βi−ν(∂bzi) b<βi−ν(∂biQi) bi . If, in addition, b≥bi, then (8.7) βi+1 −ν(∂bzi) b<βi+1 −ν(∂biQi) bi . Proof. Let i′denote the smallest ordinal such that (8.8) νi′(zi) = ν(zi) and νi′(∂bzi) = ν(∂bzi); by Proposition 3.32 and (8.3), i′< i. Let zi= si′ P j=0 cj,i′Qj i′be an i′-standard expansion of zi. By Lemma 7.4 we have (8.9) βi−ν(∂biQi) bi >βi′−ν(∂bi′Qi′) bi′ . 250 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Combining (8.9) with (7.2), we obtain (8.10) νi′(zi)−νi′(∂bzi) b≤βi′−ν(∂bi′Qi′) bi′ <βi−ν(∂biQi) bi , which gives the inequality (8.6). If b≥bi, (8.7) follows immediately by adding the inequality βi+1−βi b≤βi+1−βi bito (8.6). □ Corollary 8.3. We have (8.11) ν(∂bizi)> ν(∂biQi) = ν(∂biQi+1). Proof. The inequality in (8.11) is a special case of (8.6) when b=bi. The equality in (8.11) follows immediately from the inequality by the ultrametric triangle law. □ To prove Proposition 8.1, we argue by contradiction. Suppose that (8.12) bi+1 > bi. Letting b=bi+1 in Lemma 8.2, we obtain (8.13) βi+1 −ν(∂bi+1 zi) bi+1 <βi+1 −ν(∂biQi) bi . We have (8.14) βi−ν(∂bi+1 Qi) bi+1 ≤βi−ν(∂biQi) bi by definition of bi. Combining (8.14) with (8.12), we obtain (8.15) βi+1 −ν(∂bi+1 Qi) bi+1 <βi+1 −ν(∂biQi) bi . We can rewrite (8.13) and (8.15) as (8.16) min{ν(∂bi+1 Qi), ν(∂bi+1 zi)}> βi+1 −bi+1 bi (βi+1 −ν(∂biQi)) . Since ∂bi+1 Qi+1 =∂bi+1 Qi+∂bi+1 zi, (8.16) shows that ν(∂bi+1 Qi+1)> βi+1 −bi+1 bi (βi+1 −ν(∂biQi)) , which contradicts the definition of bi+1. This completes the proof of Proposition 8.1.□ Corollary 8.4. Keep the above notation. Assume that bi+1 =bi. Then Ii+1,max ={bi+1}. Proof. Take an integer (8.17) b > bi+1 =bi. Then (8.18) βi+1 −βi b<βi+1 −βi bi . By definition of bi, we have (8.19) βi−ν(∂bQi) b≤βi−ν(∂biQi) bi . Adding up (8.18) and (8.19) and using Corollary 8.3, we obtain βi+1 −ν(∂bQi+1) b<βi+1 −ν(∂bi+1 Qi+1) bi+1 , KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 251 so b /∈Ii+1,max. This proves the Corollary. □ Recall that δ(h) denotes the stable value of δℓ+t(h) for all sufficiently large integers t. Set δ:= δ(h). Replacing ℓby ℓ+tfor a suitable integer t, we may assume that δℓ+t(h) = δfor all t∈N. Write δ=peu, where p | uif p > 1. If char kν= 0, equations (5.3) and (4.10) imply that dδ−1,ℓ = 0 and (8.20) g1,ℓ =¯ Qℓ+ inν dδ−1,ℓ δ dδ,ℓ . If char kν=p > 0 then, according to Proposition 4.7 (2) and using the notation of (3.42), we see that for i=ℓ+t,t∈N0, (8.21) δ−pe∈Si(h) (in particular, dδ−pe,i = 0) and (8.22) inizi=Åinidδ−pe,i uinidδ,i ã1 pe . The equation (4.10) rewrites as (8.23) inℓh= inνdδ,ℓgδ 1,ℓ. Take ordinals iand ℓ1such that ℓ < ℓ1< i < ℓ+ω. Next, we prove a comparison result showing that the coefficient dδ,i agrees with dδ,ℓ1modulo terms of sufficiently high value. Proposition 8.5. Assume that (8.24) δi+1(h) = δℓ(h) = δ. We have (8.25) dδ,i ≡dδ,ℓ1mod Pν(dδ,ℓ1)+min¶ν+ ℓ1(h)−νℓ1(h),βℓ1−βℓ©. Proof. By definitions, we have Qi=Qℓ1+zℓ1+· · · +zi−1, where the ziare homogeneous Qifree i-standard expansions. For simplicity, write z:= zℓ1+· · · +zi−1. We will compare the ℓ1-standard expansion of hwith the i-standard one. To this end, we substitute Qi=Qℓ1+z into the i-standard expansion of h. We obtain (8.26) h= si X j=0 dj,iQj i= si X j=0 dj,i(Qℓ1+z)j. First note that degx δ−1 P j=0 dj,i (Qℓ1+z)j< δ degxQi. Hence dδ,ℓ1is completely determined by dδ,i, dδ+1,i, . . . , dsi,i. Next, by (4.29) in the proof of Proposition 4.7 (3), for 0< j ≤si−δ the coefficient dδ+j,i is a sum of terms of the form dj′,k,ℓ1with j′≥j+δsatisfying ν(dj′,k,ℓ1) = νℓ1(dj′,k,ℓ1)≥(j′−j−δ)βℓ1+ν(dj′,ℓ1). Hence (8.27) νℓ1Ädδ+j,iQδ+j iä≥ν+ ℓ1(h), so for 0 < j ≤si−δthe terms dδ+j,iQδ+j iin (8.26) contribute nothing to (8.28) dδ,ℓ1mod P(νℓ1(h)−δβℓ1)+min{ν+ ℓ1(h)−νℓ1(h),βℓ1−βℓ}. 252 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Therefore, the only term on the left-hand side of (8.26) that affects the element (8.28) is dδ,i(Qℓ1+z)δ. We have dδ,iQδ i=dδ,i δ X j=0 Çδ jåQδ−j ℓ1zj. For j < δ, the coefficient of Qj ℓ1in the ℓ1-standard expansion of dδ,izjcontributes to dδ,ℓ1. Let us denote this coefficient by d′ j. We have νℓ(z) = ν(z) and νℓ(dδ,i) = ν(dδ,i). By Lemma 3.43 (1), the quantity νℓ(dδ,izj) is the minimum of the νℓ-values of the summands appearing in the ℓ1-standard expansion of dδ,izj. Thus νℓdδ,izj=νdδ,izj≤νℓÄd′ jQj ℓ1ä. Hence νÄd′ jQj ℓ1ä=νℓÄd′ jQj ℓ1ä+j(βℓ1−βℓ)≥νdδ,izj+j(βℓ1−βℓ) = ν(dδ,i)+2jβℓ1−jβℓ. This shows that ν(d′ j)≥ν(dδ,i) + j(βℓ1−βℓ)≥ν(dδ,i) + (βℓ1−βℓ), so for j > 0 the term d′ jQj ℓ1 does not affect the element (8.28). This completes the proof. □ Proposition 8.6. The integer δis of the form δ=pefor some e∈N0(in particular, δ= 1 whenever char kν= 0). Proof. We give a proof by contradiction. Write (8.29) δ=pev, where p | vif char kν=p > 0. Suppose that v > 1. By Proposition 8.1, the sequence {bi}is non-increasing with tand hence stabilizes for tsufficiently large. Let b∞denote the stable value of bi. Write b∞=pe∞. Let b=pe+e∞and g=∂bh. By Proposition 4.7 (2), inihhas the form (4.10) for i=ℓ+t, as truns over N0, in particular, Si(h) = {0, pe,2pe, . . . , vpe}and is independent of i. Thus peis the same as in Proposition 7.15. Hence hand bsatisfy the hypotheses of Proposition 7.15. By Proposition 7.15 (3) and (4.10), g≡ 0 and, for tsufficiently large, we have inνig=vinνiÄdδ,i (∂biQi)pe(Qi+zi)δ−peä. In particular, ν(g)> ν Ädδ,i (∂biQi)peä+δβℓ+t−peβℓ+t=νÄdδ,i (∂biQi)peä+pe(v−1)βℓ+t=νi(g) (here is where we are using v > 1). Now, hwas defined as h=Qℓ+ω, in other words, his assumed to have minimal degree among all the polynomials satisfying ν(h)> νi(h). This is a contradiction. The Proposition is proved. □ Remark 8.7.Let the notation be as in Proposition 8.6. Assume, in addition, that the sequence {βℓ+t}is unbounded in ˜ Γ0. Then ν(h)/∈˜ Γ0. Assume that char kν=char K, (8.30) ℓ= 1 and αt= 1 for all t∈N. In particular, bt= 1 for all t∈Nand b∞= 1. Let eωbe the integer eof Proposition 8.6. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 253 We have peω=δ. We claim that (8.31) h∈Kxδ; in particular, for all strictly positive integers b′< δ we have (8.32) ∂b′h= 0. by Remark 7.1. We prove (8.31) by contradiction. Assume the contrary. Let e′denote the greatest non-negative integer such that h∈Khxpe′i; by assumption, e′< eω. Then hinvolves at least one monomial xjsuch that jis of the form j=upe′where uis not divisible by p. We have degx∂pe′h < degxh, so there exists t0∈Nsuch that (8.33) νt0Ä∂pe′hä=νÄ∂pe′hä. Take an integer t > t0. Let P pe′+1  | j cj,tQj tdenote the sum of all those monomials appearing in the t-standard expansion of hwhose exponent jis not divisible by pe′+1. Note that by (8.30) we have cj,t ∈Kfor all pairs (j, t). By Remark 7.1, the operator ∂pe′annihilates all the monomials whose exponents are divisible by pe′+1. Thus (8.34) ∂pe′h=∂pe′ÑX pe′+1  | j cj,tQj té=X pe′+1  | j cj,tÇj pe′åQj−pe′ t. Formulas (8.33) and (8.34) imply that the t-standard expansion of hcontains a monomial of the form cpe′,tQpe′ tand that for each jwith pe′+1  | jwe have νt0Äcj,tQj tä≥νÅcpe′,tQpe′ tã. Hence (8.35) νÄcj,tQj tä> ν Åcpe′,tQpe′ tãfor all jwith pe′+1  | jand j > pe′. We obtain that for all tsufficiently large the t-standard expansion of hcontains a monomial of the form cpe′,tQpe′ tand all the other monomials not divisible by Qpe′+1 thave values strictly greater than νÅcpe′,tQpe′ tã. Then for all t′> t we have νÄcpe′,tä=νÄcpe′,t′ä. Choosing t′sufficiently large, we obtain νÅcpe′,t′Qpe′ t′ã< ν cδ,t′Qδ t′, which contradicts the definition of δ. This completes the proof of (8.31) and (8.32). In fact, by a similar argument this statement can be proved not only for h, but for any polynomial satisfying the strict inequalities (8.1). Remark 8.8.Keep the assumption that {βℓ+t}is unbounded in ˜ Γ0, as well as (8.30), but now assume that char K = 0 and char kν=p > 0. By studying the coefficient of Qδ−1 tin the t-standard expansion of hfor different t, one can prove that δ=pe= 1. Remark 8.9.It was pointed out to us by the referee that the result of Remark 8.7 was generalized in [3], Theorem 4.11. For every valued field (K, ν) and every continuous family of iterated augmentations on K[x] such that {βℓ+t}is unbounded, all the limit key polynomials of the family belong to Kxδb∞. 260 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY By Remark 9.10 (specifically, (9.18)), (9.5) and the fact that aj,iQj iis not i-superfluous, all the monomials dQs i+1,s > 0, appearing in the Qi+1-expansion of aj′,izpe′ isatisfy νdQs i+1> ν(aj,i) + jβi+1. In particular, if such a monomial is of the form dQj i+1, with degxd < ¯αi+1, we have ν(d)> ν(aj,i). This proves that (9.15) holds for j=j(i). The fact that all the new monomials with strictly positive exponents arising from the Euclidean division of aj′,izpe′ i, j′> j, are (i+ 1)-superfluous also shows that no bad monomials aj′′ ,i+1Qj′′ i+1 with j′′ > j appear in the Qi+1-expansion of f. This proves (9.13). The proof of the Lemma in the case j=j•(i) is very similar to that of j=j(i), except for the following minor change. We can no longer assert that j′is a power of p. On the other hand, j′satisfies ν(aj′,i) + j′βi> νi(f), which allows us to use similar arguments as in the j=j(i) case. This completes the proof of Lemma 9.7.□ Proof of Lemma 9.8.We argue by contradiction. Suppose that j=j(i) and that (9.11) holds for this j. (9.11) can be rewritten as ν(aj,i) + j¯ β < pe0¯ β. Combining this with (9.15) we obtain that (9.11) holds with ireplaced by i+ 1 and (9.21) ν(aj,i+1) + j¯ β < 2pe0¯ β−pe0βi+1, so the monomial aj,i+1Qj i+1 is also bad and j(i+ 1) = j(i) in view of (9.13). By induction on i′≥iwe see that j(i′) is independent of i′, so the Qi′-expansion of fcontains a monomial aj,i′Qj i′with νÄaj,i′Qj i′ä=ν(aj,i′) + jβi′=ν(aj,i) + jβi′< ν(aj,i) + j¯ β. Then pe0βi′=νi′(fi′)< ν(aj,i) + j¯ β < pe0¯ βfor all i′≥i, where the equality holds because pe0=δ∈Si′(f). Therefore the least upper bound of {βi′}i≤i′<ℓ+ωis bounded above by 1 pe0(ν(aj,i) + j¯ β) and hence is strictly less than ¯ β. This contradicts the definition of ¯ β. The proof in the case j=j•(i) is similar to that with j=j(i) and we omit it. □ Proof of Lemma 9.9.We argue by contradiction. Assume that j=j(i) and that (9.12) does not hold. In view of Lemma 9.8 this implies that (9.22) ν(aj,i) + j¯ β=pe0¯ β. Then, by definition of j(i), jis not a power of p. Write j=peu,u≥2 and p | u, and Qi+1 =Qi+zi. Lemma 9.8, applied to j•(i), implies that (9.23) ν(aj′,i) + j′¯ β≥pe0¯ βfor all j′∈ {1, . . . , pe0}. Let b=peb∞. Arguing as in the proof of Lemma 9.7, we can show that j(i) and ν(aj,i) remain unchanged as iincreases. Moreover, after suitably increasing ℓand i, we may assume that bℓ=bi=b∞(by Proposition 8.1) and degxQℓ= degxQi. Let us denote the common value of degxQℓand degxQiby ¯α∞. By Corollary 8.4 there is at most one value of i=ℓ+t,t∈N, for which #Ii,max >1. Hence, increasing ℓand i, we may assume, in addition, that (9.24) Ii′,max ={b∞}for all i′≥ℓ. KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 261 Finally, increasing ℓand iagain, if necessary, and using (9.24), we may assume that (9.25) βi−βℓ> δb∞(¯ β−βi). We continue to use the notation of (9.10) for the i-expansion of fi. For each polynomial awith (9.26) degxa < degxQi by Proposition 3.32 (applied separately to iand then to ireplaced by ℓand using the fact that neither ℓnor iare limit ordinals), we have νℓ(a) = νi(a) = ν(a). For each b′∈Nand each i′, ℓ<i′< ℓ +ω, we have ν(∂b′a) = νℓ(∂b′a)≥ν(a)−b′ b∞ (βℓ−ν(∂b∞Qℓ)) =ν(a)−b′ b∞ (βi′−ν(∂b∞Qi′)) + b′ b∞ (βi′−βℓ) > ν(a)−b′ b∞ (βi′−ν(∂b∞Qi′)) + 2pe0b′ b∞ (¯ β−βi′) (9.27) by Proposition 7.2. Remark 9.11.For i′=ℓ+t′,t′∈N(the integer t′is strictly positive here), we trivially have (9.28) ν(∂b∞Qi′) = ν(Qi′)−(βi′−ν(∂b∞Qi′)) . Combining this with (9.27), applied to a=zℓ+· · · +zi′−1and b′=b∞, we obtain (9.29) ν(∂b∞Qi′) = ν(∂b∞Qℓ). In particular, the quantity ν(∂b∞Qℓ+t′) is independent of t′∈N. Remark 9.12.By (9.24), for all i′> ℓ and all b′∈ {1, . . . , b}\{b∞}we have (9.30) βi′−ν(∂b∞Qi′) b∞ >βi′−ν(∂b′Qi′) b′. Assume that (9.31) βi′−ν(∂b∞Qi′) b∞ −βi′−ν(∂b′Qi′) b′<1 b∞ (βi′−βℓ). Combining this with (9.27), applied to a=zℓ+· · · +zi′−1, we obtain (9.32) ν(∂b′Qi′) = ν(∂b′Qℓ). In particular, the quantity ν(∂b′Qi′) is the same for all those i′that satisfy (9.31). In this way, we have generalized Remark 9.11 from the case of the pair (b∞, i′) to the case of every pair (b′, i′) satisfying (9.31). By Lemma 7.7, for all s, t′∈N, letting i′=ℓ+t′, we have (9.33) ∂b(as,i′Qs i′) = X 0≤q≤s j0+···+jq=b 0<j1≤···≤jq Cs(j1, . . . , jq)Qs−q i′(∂j0as,i′) q Y t=1 (∂jtQi′), so (9.34) ∂bf= δ X s=0 X 0≤q≤s j0+···+jq=b 0<j1≤···≤jq Cs(j1, . . . , jq)Qs−q i′(∂j0as,i′) q Y t=1 (∂jtQi′)!. 262 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Remark 9.13.(1) Consider an integer s∈ {1, . . . , j −1} ∪ Supj,i′. We have (9.35) νÄaj,i′Qj i′ä< ν (as,i′Qs i′). Indeed, (9.35) holds for s∈ {1, . . . , j −1}by (9.22)–(9.23), with ireplaced by i′, since βi′<¯ β. It holds for s∈Supj,i′since, by (9.9) (with ireplaced by i′), each i′-superfluous monomial has value strictly greater than pe0¯ β > ν Äaj,i′Qj i′ä. (2) By definition of j=j(i) = j(i′), every s∈NSj,i′(f) is of the form s=pe′. Since s > j, we have e′> e. By (7.12), we have Cs(j1, . . . , jq) = 0 unless j0= 0, q=s=pe′(in particular, s≤b) and j1=· · · =jq=b pe′. (3) By (1) and (2), for every non-zero term Cs(j1, . . . , jq)Qs−q i′(∂j0as,i′) q Q t=1 (∂jtQi′) on the righthand side of (9.34), at least one of the following three conditions holds: (a)i′(9.35) (b)i′s=pe′, where pe< pe′≤band {j0, j1, . . . , jq}=0,b pe′,..., b pe′ | {z } pe′ (c)i′j0>0 (this condition holds whenever s= 0) (d)i′s=upe=jand {j0, j1, . . . , jq}=Å0, b∞, . . . , b∞ |{z } peã. Claim. There exists a strictly increasing infinite sequence (tr)r∈N⊂Nand s∈ ∞ T r=1 Sj,ir(where ir=i+tr) such that, for all r∈N, the term Cj(b∞, . . . , b∞ |{z } pe )aj,irQj−pe ir(∂b∞Qir)pehas strictly smaller value than all the other terms in the sum on the right-hand side of (9.34). Proof of Claim. We have Cj(b∞, . . . , b∞ | {z } pe ) = j! pe!=(upe)! pe!=u, so ν(Cj(b∞, . . . , b∞ | {z } pe )) = 0. Hence, for all i′of the form i′=i+t′,t′∈N, we have (9.36) νÖCj(b∞, . . . , b∞ | {z } pe )aj,i′Qj−pe i′(∂b∞Qi′)peè=νÄaj,i′Qj i′ä−pe(βi′−ν(∂b∞Qi′)) (recall that ν(aj,i′) and ν(∂b∞Qi′) are independent of i′). KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 263 First, let us prove that all the terms on the right-hand side of (9.34) satisfying (a)i′or (c)i′ have values strictly greater than νÄaj,i′Qj i′ä−pe(βi′−ν(∂b∞Qi′)). Consider a non-zero term Cs(j1, . . . , jq)Qs−q i′(∂j0as,i′) q Q t=1 (∂jtQi′) appearing on the right-hand side of (9.34). For all positive integers sand b′, we have (9.37) ν(∂b′Qs i′)≥ν(Qs i′)−b′ b∞ (βi′−ν(∂b∞Qi′)) . by Proposition 7.2 (1). Combining this with (9.27), we obtain (9.38) ν Qs−q i′(∂j0as,i′) q Y t=1 (∂jtQi′)!= (s−q)βi′+ν(∂j0as,i′) + q X t=1 ν(∂jtQi′) ≥ν(as,i′Qs i′)−j0 b∞ (βi′−ν(∂b∞Qi′)) + j0 b∞ (βi′−βℓ)− q X t=1 jt b∞ (βi′−ν(∂b∞Qi′)) =ν(as,i′Qs i′)−pe(βi′−ν(∂b∞Qi)) + j0 b∞ (βi′−βℓ). If (9.35) holds, we obtain (9.39) ν Qs−q i′(∂j0as,i′) q Y t=1 (∂jtQi′)!> νiÄaj,′iQj i′ä−pe(βi′−ν(∂b∞Qi′)) . If (c)i′is satisfied, that is, j0>0, (9.39) holds again. This shows that in order to prove the Claim it is sufficient to restrict attention to the terms on the right-hand side of (9.34) satisfying (b)i′. Next, choose a strictly increasing sequence (tr)r∈N⊂Nsuch that for each s∈ {j+ 1, . . . , δ} one of the following conditions holds for all r∈N: (1) s∈Sj,irand (9.31) holds with i′=ir (2) either s∈Supj,iror (9.31) does not hold with i′=ir We obtain a decomposition {j+ 1, . . . , δ}=J1`J2, where (1) holds for s∈J1and (2) holds for s∈J2. We have j∈J1; in particular, J1=∅. The set J2is non-empty since it contains all the non-powers of pin the set {j+ 1, . . . , δ}. We will now show that for s∈J2and r≫0 the strict inequality (9.39) holds with i′=ir. For s∈Supj,irthis has already been shown (and does not require rto be large). Assume that s∈Sj,irand (9.31) does not hold with i′=ir. Consider a non-zero term Cs(j1, . . . , jq)Qs−q ir(∂j0as,ir) q Y t=1 (∂jtQir) appearing on the right-hand side of (9.34). This term satisfies condition (b)ir(in particular, it is the uniqe term with the given s). Using the notation of (b)ir, we have (9.40) νÑas,irÅ∂b pe′Qirãpe′é=ν(as,ir) + pe′νÅ∂b pe′Qirã =νas,irQs ir−pe′Åβir−νÅ∂b pe′Qirãã. 264 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY Further, by (9.22) and (9.23), applied to irinstead of i, we have (9.41) νÄaj,irQj irä−νas,irQs ir≤(s−j)(¯ β−βir)< δ(¯ β−βir). Combining (9.25), the negation of (9.31) and (9.40)–(9.41), we obtain (9.42) νÑas,irÅ∂b pe′Qirãpe′é≥νas,irQs ir−pe(βir−ν(∂b∞Qi)) + pe(βir−βℓ) ≥νÄaj,irQj irä−pe(βir−ν(∂b∞Qi)) + pe(βir−βℓ)−δb ¯ β−βir > ν Äaj,irQj irä−pe(βir−ν(∂b∞Qir)) = νÄQj−pe iraj,ir(∂b∞Qir)peä. This shows that to prove the Claim it is sufficient to restrict attention to the terms Cs(j1, . . . , jq)Qs−q ir(∂j0as,ir) q Q t=1 (∂jtQir) appearing on the right-hand side of (9.34) such that s∈J1. Consider one such term. It must satisfy condition (b)ir, so it is completely determined by sand we can write it as as,irÅ∂b pe′Qirãpe′ . By (9.31), Remark 9.12 applies to ∂b pe′Qir, in other words, νÅ∂b pe′Qirãdoes not depend on r∈N. Therefore, νÑas,irÅ∂b pe′Qirãpe′éis independent of r. We will use the formulae (9.40) and (9.41) which are valid for all s∈ {0, . . . , δ}. Let us take the limit as rtends to ∞separately of each summand on the right-hand side of (9.40). By (9.41), we have lim r→∞ νÄaj,irQj irä≤lim r→∞ νas,irQs ir. Applying (9.30) with i′=irfor each r∈Nand passing to the limit as rgoes to infinity, we obtain lim r→∞ pe(βir−ν(∂b∞Qir)) ≥lim r→∞ pe′Åβir−νÅ∂b pe′Qirãã. Thus (9.43) νÑas,irÅ∂b pe′Qirãpe′é= lim r→∞ νÑas,irÅ∂b pe′Qirãpe′é = lim r→∞ Åνas,irQs ir−pe′Åβir−νÅ∂b pe′Qirããã ≥lim r→∞ ÄνÄaj,irQj irä−pe(βir−ν(∂b∞Qir))ä= lim r→∞ νÄQj−pe iraj,ir(∂b∞Qir)peä. Since νÑas,irÅ∂b pe′Qirãpe′éis independent of rand νÄQj−pe iraj,ir(∂b∞Qir)peäis a strictly KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 265 increasing linear function of r, we have νÑas,irÅ∂b pe′Qirãpe′é> ν ÄQj−pe iraj,ir(∂b∞Qir)peäfor all r∈N. This completes the proof of the Claim. By the Claim, for all r∈Nwe have ν(∂bf) = νÄQj−pe iraj,ir(∂b∞Qir)peäwith the left-hand side independent of rand the right-hand side — a strictly increasing linear function of r, which gives the desired contradiction. This completes the proof of Lemma 9.9.□ Let j=j(i). By Lemma 9.9 the inequality (9.12) holds for j. By Lemma 9.7 (cf. (9.15)), inνaj,i is independent of i≥i0. Since ¯ β−βican be made arbitrarily small as i→i0+ = ℓ+ω, by (9.12), taking i1sufficiently large, we can ensure that (9.44) ν(aj,i) + j¯ β≥2pe0¯ β−pe0βi1. Take the smallest i1satisfying (9.44). By the minimality of i1, Lemma 9.7 (specifically, (9.15)) and induction on i′,i≤i′< i1, we see that the monomial aj,i′Qj i′remains bad for i≤i′< i1 and that (9.45) ν(aj,i) = ν(aj,i1). From (9.44)–(9.45) we obtain (9.46) ν(aj,i1) + j¯ β≥2pe0¯ β−pe0βi1. Thus the monomial aj,i1Qj i1is i1-superfluous. Therefore (9.47) j(i1)< j(i′) for all i′< i1. Since the strict inequality (9.47) can occur for at most finitely many values of i1, there exists i2< ℓ +ωsuch that fcontaining no bad monomials. Let Qℓ+ωbe equal to fminus the sum of all the i2-superfluous monomials of f. Now, Qℓ+ωis monic of degree pe0¯αiand satisfies (9.1). It contains no i2-superfluous or bad monomials, hence it satisfies (9.2); in particular, it is weakly affine. The polynomial Qℓ+ωsatisfies (9.3) and so is a limit key polynomial by Remark 9.5. This completes the proof of Proposition 9.2.□ Remark 9.14.The property that the i2-standard expansion of Qℓ+ωis weakly affine is not preserved when we pass from i2to some other ordinal i2+t,t∈N. However, the above results show that for all i′of the form i′=i+t,t∈N0,Qℓ+ωis a sum of a weakly affine expansion in Qi′all of whose monomials aj,i′Qj i′for j > 0 lie on the critical line ν(aj,i′)=(pe0−j)¯ β and another i′-standard expansion of degree strictly less than pe0¯αℓ, all of whose monomials are i′-superfluous. References [1] S. Abhyankar and T.T. Moh, Newton–Puiseux expansion and generalized Tschirnhausen transformation I, Reine Agew. Math. 260 (1973) 47–83 DOI: 10.1515/crll.1973.260.47 [2] S. Abhyankar and T.T. Moh, Newton–Puiseux expansion and generalized Tschirnhausen transformation II, Reine Agew. Math. 261 (1973) 29–54 DOI: 10.1515/crll.1973.261.29 [3] M. Alberich-Carrami˜nana, Alberto F. Boix, J. Fern´andez, J. Gu`ardia, E. Nart, J. Ro´e, Of limit key polynomials, Illinois J. Math. 65, No.1 (2021), 201-229 [4] V. Alexandru, N. Popescu and A. Zaharescu, Minimal pairs of definition of a residual transcendental extension of a valuation, J. of Math. Kyoto Univ. 30 (1990), 207-225 MR 92b:12014 DOI: 10.1215/kjm/1250520067 [5] V. Alexandru, N. Popescu and A. Zaharescu, All valuations on K(X), J. of Math. Kyoto Univ. 30 (1990), 281-296 MR 92c:12011 DOI: 10.1215/kjm/1250520072 266 F. J. HERRERA GOVANTES, W. MAHBOUB, M. A. OLALLA ACOSTA, AND M. SPIVAKOVSKY [6] M.F. Atiyah and I.G. Macdonald, Introduction to Commutative Algebra (1969), Addison–Wesley, Reading, MA [7] R. Brown, Valuations, primes and irreducibility in polynomial rings and rational function fields, Trans. Amer. Math. Soc. 174 (1972), 451–488 DOI: 10.1090/s0002-9947-1972-0371872-1 [8] R. Brown, Roots of Irreducible Polynomials in Tame Henselian Extension Fields, Comm. Algebra 37 (2009), no. 7, 2169–2183 DOI: 10.1080/00927870802467197 [9] S.D. Cutkosky and H. Mourtada, Defect and Local Uniformization, (2017). arχiv: 1711.02726 [10] S.D. Cutkosky, H. Mourtada and B. Teissier, On the construction of valuations and generating sequences on hypersurface singularities, Alg. Geom. 8 (6) (2021) 705-748. DOI: 10.14231/ag-2021-022 [11] M. de Moraes and J. Novacoski, Limit key polynomials as p-polynomials, (2021). arχiv: 2009.04349 [12] J. Decaup, W. Mahboub and M. Spivakovsky Abstract key polynomials and comparison theorems with the key polynomials of Mac Lane – Vaqui´e, Illinois J. Math. 62(1–4): 253-270 (2018) DOI: 10.1215/ijm/1552442662 [13] M. dos Santos Barnab´e, J. Novacoski Generating sequences and key polynomials, (2021). arχiv: 2007.12293 [14] J. Herrera, M.A. Olalla, M. Spivakovsky, Valuations in algebraic field extensions, J. Algebra 312 (2007), no. 2, 1033–1074 DOI: 10.1016/j.jalgebra.2007.02.022 [15] I. Kaplansky, Maximal Fields with valuations I, Duke Math. J. 9 (1942), 303–321 DOI: 10.1215/s0012-7094-42-00922-0 [16] S.K. Khanduja, On valuations of K(x), Proc. Edinburgh Math. Soc. 35 (1992), 419–426 [17] S.K. Khanduja, N. Popescu and K.W. Roggenkamp, On minimal pairs and residually transcendental extensions of valuations, Mathematika 49 (2002), no. 1-2, 93–106 (2004) DOI: 10.1112/s0025579300016090 [18] F.-V. Kuhlmann, Value groups, residue fields, and bad places of rational function fields, Trans. Amer. Math. Soc. 356 (2004), 4559-4600 DOI: 10.1090/s0002-9947-04-03463-4 [19] F.-V. Kuhlmann, Book on Valuation Theory, in preparation, bookch24.pdf [20] F.-V. Kuhlmann, I. Vlahu, The relative approximation degree in valued function fields, Mathematische Zeitschrift, Volume 276 (2014), Issue 1, 203–235 DOI: 10.1007/s00209-013-1194-1 [21] T.C. Kuo, Generalized Newton–Puiseux theory and Hensel’s lemma in C[[x,y]], Canadian J. Math. 41 (1989) 1101–1116 DOI: 10.4153/cjm-1989-048-7 [22] T.C. Kuo, A simple algorithm for deciding primes in C[[x,y]], Canadian J. Math. 47 (1995) 801–816 DOI: 10.4153/cjm-1995-041-9 [23] M. Lejeune-Jalabert, Contributions `a l’´etude des singularit´es du point de vue du polygone de Newton, Th´ese d’Etat, Universit´e Paris 7 (1973) [24] S. Mac Lane, A construction for prime ideals as absolute values of an algebraic field, Duke Math. J. 2 (1936) 492–510 DOI: 10.1215/s0012-7094-36-00243-0 [25] S. Mac Lane, A construction for absolute values in polynomial rings, Transactions of the AMS 40 (1936) 363–395 DOI: 10.1090/s0002-9947-1936-1501879-8 [26] S. Mac Lane and O.F.G Schilling, Zero-dimensional branches of rank one on algebraic varieties, Ann. of Math. 40 (1939) 507–520 DOI: 10.2307/1968935 [27] Moyls, B. N. The structure of valuations of the rational function field K(x), Trans. Amer. Math. Soc. 71, (1951) 102–112 DOI: 10.1090/s0002-9947-1951-0041838-6 [28] E. Nart, Key polynomials over valued fields, Publ. Mat. 64 (2020), 195-232 DOI: 10.5565/publmat6412009 [29] E. Nart, MacLane-Vaqui´e chains of valuations on a polynomial ring, Pacific J. Math. 311-1 (2021), 165-195 DOI: 10.2140/pjm.2021.311.165 [30] J. Novacoski On MacLane-Vaqui´e key polynomials, Journal of Pure and Applied Algebra 225 (8):106644 (2021) DOI: 10.1016/j.jpaa.2020.106644 [31] J. Novacoski and M. Spivakovsky, Reduction of local uniformization to the rank one case, Valuation Theory in Interaction, EMS Series of Congress Reports, European Mathematical Society, (2014) 404-431 DOI: 10.4171/149-1/20 [32] J. Novacoski and M. Spivakovsky, On the local uniformization problem, Algebra, Logic and Number Theory, Banach Center Publ. 108 (2016) 231-238 DOI: 10.4064/bc108-0-17 [33] J. Novacoski and M. Spivakovsky, Key polynomials and pseudo-convergent sequences, Journal of Algebra 495 199–219 arXiv:1611.05679 (2018) DOI: 10.1016/j.jalgebra.2017.11.006 [34] J.-C. San Saturnino, Th´eor`eme de Kaplansky effectif et uniformisation locale des sch´emas quasi-excellents, Th`ese de Doctorat, Institut de Math´ematiques de Toulouse, July 2013. DOI: 10.5802/aif.2877 [35] J.-C. San Saturnino, Defect of an extension, key polynomials and local uniformization, (2014). arχiv: 1412.7697 [36] M. Vaqui´e, Famille admise associ´ee `a une valuation de K[x], Singularit´es Franco-Japonaises, S´eminaires et Congr`es 10, Soci´et´e Math´ematique de France, Paris (2005), Actes du colloque franco-japonais, juillet 2002, ´edit´e par Jean-Paul Brasselet et Tatsuo Suwa, 391–428 DOI: 10.1515/9783111676517.76 KEY POLYNOMIALS FOR SIMPLE EXTENSIONS OF VALUED FIELDS 267 [37] M. Vaqui´e, Alg`ebre gradu´ee associ´ee `a une valuation de K[x], Singularities in Geometry and Topology 2004, Advanced Studies in Pure Mathematics 46 (2007), Actes du Troisi`eme Congr`es Franco-Japonais sur les Singularit´es en G´eom´etrie et Topologie, Sapporo, Japon, septembre 2004, ´edit´es par J.-P. Brasselet et T. Suwa, 259–271 DOI: 10.2969/aspm/04610259 [38] M. Vaqui´e, Extension d’une valuation, Transactions of the American Mathematical Society 359 (2007), 3439–3481 DOI: 10.1090/s0002-9947-07-04184-0 [39] M. Vaqui´e, Famille admissible de valuations et d´efaut d’une extension, J. Algebra 311 (2007), no. 2, 859–876 DOI: 10.1016/j.jalgebra.2007.02.038 J. Herrera Govantes, Departamento de ´ Algebra, Facultad de Matem´ aticas, Avda. Reina Mercedes, s/n, Universidad de Sevilla, 41012 Sevilla, Spain Email address:[email protected] W. Mahboub, Institut de Math´ ematiques de Toulouse, UMR 5219 du CNRS, Universit´ e Paul Sabatier, 118, route de Narbonne, 31062 Toulouse cedex 9, France Email address:[email protected] M. A. Olalla Acosta, Departamento de ´ Algebra, Facultad de Matem´ aticas, Avda. Reina Mercedes, s/n, Universidad de Sevilla, 41012 Sevilla, Spain Email address:[email protected] M. Spivakovsky, Institut de Math´ ematiques de Toulouse, UMR 5219 du CNRS, Universit´ e Paul Sabatier, 118, route de Narbonne, 31062 Toulouse cedex 9, France, and UMI CNRS 2001 LaSol, UNAM Email address:[email protected]