W Mahboub Cnam

Lebanon M Spivakovsky
email: mark.spivakovsky@math.univ-toulouse.fr

Key polynomials in dimension 2

published or not. The documents may come

Introduction

Throughout this paper all the rings considered will be commutative with 1. Let (R, m, k) be a regular local ring of dimension 2 and F the field of fractions of R. Consider the poset (V, ≤) of normalized valuations of F centered at R (see §2).

In [START_REF] Favre | The Valuative Tree[END_REF] C. Favre and M. Jonsson prove that (V, ≤) has the structure of a parametrized, rooted, non-metric tree when R = C[[x, y]], the ring of formal power series over the field of complex numbers. The proof of C. Favre and M. Jonsson is based on associating to each valuation in V a set of key polynomials, a concept introduced by S. MacLane in [START_REF] Maclane | A construction for prime ideals as absolute values of an algebraic field[END_REF] and [START_REF] Maclane | A construction for absolute values in polynomial rings[END_REF]. Below we will refer to this set as a complete set of key polynomials (see §4 for its definition and porperties).

In [START_REF] Granja | The valuative tree of a two-dimensional regular local ring[END_REF] A. Granja generalizes this result to the case when R is any two-dimensional regular local ring. A. Granja gives a proof based on associating to each valuation in V a sequence of point blowing ups.

In this paper we give a new proof of A. Granja's result when R is any two-dimensional regular local ring, using appropriate complete sequences of key polynomials, based on the work of M. Vaquié [17] for valuations of arbitrary rank, and the work of F. J. Herrera Govantes, W. Mahboub, M. A. Olalla Acosta and M. Spivakovsky ([6], [START_REF] Herrera Govantes | Key polynomials for simple extensions of valued fields[END_REF]) for valuations of rank 1 over fields of arbitrary characteristic.

We use the notion of key polynomials introduced in [3] and [START_REF] Novacoski | Key polynoimals and pseudo-convergent sequences[END_REF]. We give a simple construction of a complete set of key polynomials associated to a valuation of the field k(x, y) where k is the residue field of R and x, y are independent variables. For explicit constructions of key polynomials on particular cases, see [15], [START_REF] Favre | The Valuative Tree[END_REF], [8].

We start by stating in §2 the basic facts related to valuations needed in this paper. Then we establish, in §3, a natural order-preserving bijection between valuations of F centered at R and valuations of k(x, y) centered at k[x, y] (x,y) . This is the content of Theorem 3.12. It consists of describing a one-to-one correspondence between the set of valuations centered at R and the set of simple sequences of local point blowing ups (see Corollary 3.11).

In §4 we give the definition of key polynomials. We state the needed facts about key polynomials and construct a complete set of key polynomials associated to a valuation ν of k(x, y). This is our main tool for the proof of Theorem 6.4. We also define invariants of valuations centered in regular two-dimensional local rings.

Then we consider two comparable valuations, µ ≤ ν, and study the structure of their key polynomials sets and the relation between the invariants of those valuations. This is done in §5. Using this comparison, we prove that the infimum of any two elements of V exists (Theorem 5.8) and that any increasing sequence in V has a majorant in V (Theorem 5.9). We note that a more general version of the latter result -one for rings of arbitrary dimension -is given in Lemma 3.9 (i) of [START_REF] Novacoski | Valuations centered at a two-dimensional regular local ring: Infima and Topologies[END_REF].

Finally, in §6 we prove the main theorem of this paper, Theorem 6.4. This Theorem asserts that V has a tree structure.

We thank the referee for a very careful reading of the paper and for numerous useful comments that helped improve the exposition. We also thank Josnei Novacoski for very useful discussions and for sharing his insights.

Basics

Let R be a regular noetherian local ring of dimension 2. Denote by m its maximal ideal and let F be the quotient field of R.

A valuation of F is a function ν : F -→ R = R ∪ {∞} such that for all f, g ∈ F :

(V 1 ) ν(f + g) ≥ inf(ν(f ), ν(g)), (V 2 ) ν(f • g) = ν(f ) + ν(g).
It is an easy exercise to check that if ν is not constant, then axiom (V 2 ) implies

(V 3 ) ν(1) = 0.
Let Γ be a totally ordered abelian group. A Krull valuation of F is a function

ν : F -→ Γ ∪ {∞} satisfying (V 1 ), (V 2 ) and (V 3 ) such that ν -1 (∞) = 0.
If ν is a valuation or a Krull valuation of F , we say that ν is centered at R if ν is non-negative on R and strictly positive on m. We say that ν is

proper if ν(F \ {0}) = {0} and ν(m) = {∞}.
If ν and ν are two valuations of F , then we say that ν and ν are equivalent, and write ν ∼ ν , if there exists a non-zero real number c such that for all f ∈ F we have ν(f ) = cν (f ).

Let V = {ν | ν proper valuation centered at R}/ ∼. When working with an element of V, we will tacitly fix a valuation representing it, so in practice we will work with valuations instead of classes of valuations. We will consider only normalized valuations, in the sense that ν(m) := inf {ν(f ) | f ∈ m} = 1. Indeed, we can represent any element ν of V by a uniquely determined normalized valuation after multiplying all the values by 1 ν(m) .

For an element ν ∈ V we will denote by Γ ν the augmented value group of ν, that is,

Γ ν := ν(F ) ⊂ R.
If ν is a valuation (resp. a Krull valuation), the set

R ν := {f ∈ F | ν(f ) ≥ 0} ;
is a local ring called the valuation ring associated to ν, with maximal ideal

m ν := {f ∈ F | ν(f ) > 0} .
The rank of ν, denoted by rk(ν), is the Krull dimension of R ν . In our situation rk(ν) is at most 2 by Abhyankar's inequality.

Remark 2.1. We have rk(ν) = 1 if and only if ν(F \ {0}) ⊂ R (resp. the group ν(F \ {0}) can be embedded into the additive group R of real numbers).

If S is a ring contatined in R ν , the center of ν in S is the prime ideal m := m ν ∩ S. In this situation we also say that ν is centered at m. If (S, m) is a local domain, we will sometimes say that ν is centered at (S, m). Definition 2.2. For two local rings (R 1 , m 1 ) and (R 2 , m 2 ), we say that

R 2 dominates R 1 if R 1 ⊂ R 2 and m 1 = R 1 ∩ m 2 .
If, in addition, R 1 and R 2 are domains with the same field of fractions, we will say that R 2 birationally dominates R 1 Notation. In the above situation we will write (R

1 , m 1 ) < (R 2 , m 2 ) or simply R 1 < R 2 . Remark 2.3. Let (S, m) be a local domain, contained in F . A valuation ν of F is centered at m if and only if we have (S, m) < (R ν , m ν ). Remark 2.4. (1)
The valuation ν is uniquely determined by its valuation ring R ν . For a proof, see [16], Proposition 1.4.

(2) Consider a local domain (R, m) with field of fractions F . The following conditions are equivalent:

(a

) (R, m) is of the form (R ν , m ν ) for some valuation ν of F (b) for every f ∈ F either f ∈ R ν or f -1 ∈ R ν (or both) (c) the ring (R, m
) is maximal with respect to the relation of birational domination.

For a proof, see [16], Proposition 1.4 and [2], Chap. 6, §2, n 0 2, Théorème 1, page 85. Below we reprove the equivalence (a)⇐⇒(c) in the special case when R is a 2-dimensional regular local ring.

We will use the following partial order on the set of valuations of the field F , centered at R: For two valuations µ and µ centered at R, we will say that µ ≤ µ if µ(f ) ≤ µ (f ) for all f ∈ R.

We denote by νm the multiplicity valuation, that is, νm (f ) := max{i | f ∈ m i } for all f ∈ R. We note that νm is the smallest element of V. We say that the multiplicity of f at m is νm (f ).

If ν is a valuation centered at R then ν determines a Krull valuation ν , centered at R.

Furthermore, rk(ν ) = 2 if and only if ν -1 (∞) = {0}. Indeed, if ν -1 (∞) = {0}, then ν = ν is a Krull valuation of rank 1. Otherwise, if ν -1 (∞) = {0}, then ν -1 (∞) is a principal prime ideal of R generated by an irreducible element f ∈ R. For each g ∈ R -{0}, write g = f s h, where f does not divide h (that is, ν(h) < ∞). Define ν (g) = (s, ν(h)) ∈ Z ⊕ R. For G = g 1 g 2 ∈ F -{0}, put ν(G) = ν(g 1 ) -ν(g 2 ). It is clear that ν determines a Krull valuation on F , centered at R.
Conversely, if ν is a Krull valuation of F centered at R then ν determines a valuation on R. Indeed, let m ν be the maximal ideal of R ν . If rk(ν ) = 1, put ν = ν . Otherwise, let Γ 1 be the isolated subgroup of Γ of rank 1 (that is, the smallest non-zero isolated subgroup of Γ). Let P be the prime ideal of R ν associated to Γ 1 :

P = { f ∈ R ν | ν(f ) ∈ Γ \ Γ 1 } . Let P = P ∩ R. For each f ∈ R, if f ∈ P , put ν(f ) = ∞. Otherwise, put ν(f ) = ν (f ) ∈ Γ 1 .
Then ν is a valuation centered at R.

For an element β ∈ Γ ν , let

P β := {f ∈ F | ν(f ) ≥ β}, P β+ := {f ∈ F | ν(f ) > β}. Let gr ν F = β∈Γ 1 P β P β+ .
For an element β ∈ Γ 1 and an element f ∈ F such that ν(f ) = β, we will denote by in ν f the natural image of f in

P β P β+ .

Valuations and blowing ups

The aim of this section is to describe a natural order-preserving bijection between valuations of F centered at R and valuations of k(x, y) centered at k[x, y] (x,y) .

Remark 3.1. Throughout the paper we will commit the following abuse of notation. We will use the letters x, y to denote both the generators of the field k(x, y) over k and a regular system of parameters of R. Since in each case we will specify clearly with which ring we are working, this should cause no confusion.

A simple sequence π * of local point blowings up of Spec R is a sequence of the form (R, m)

π 1 -→ (R 1 , m 1 ) π 2 -→ . . . π i -→ (R i , m i ) π i+1 -→ . . . (3.1)
where π i is given by considering the blowing up Spec R i Let I(x, y, f ) denote the smallest monomial ideal containing f . (3.2) is equivalent to saying that y µ ∈ I(x, y, f ).

π * i -→ Spec R i-1 along m i-1 , picking a point ξ i ∈ π * i -1 (m i-1 ) and putting R i := O X i ,ξ i . Let Π(R)
Let e(x, y, f

) := min α µ-β x α y β ∈ I(x, y, f ), β < µ ∈ 1 µ! Z ∪ {∞},
where we adopt the convention that the minimum of the empty set is infinity. Definition 3.3. The first characteristic exponent of f at m is the supremum of e(x, y, f ), where (x, y) runs over all the regular systems of parameters of R satisfying (3.2).

Fix a real number e. For a real number ξ, let I ξ denote the monomial ideal of R generated by all the monomials x α y β such that α + eβ ≥ ξ. The following conditions are equivalent:

1. e < e 0 , 2. e is an integer, and there exists a regular system of parameters of the form (y -ux e , x), with u a unit of R, satisfying e(x, y, f ) < e(x, y -ux e , f ).

3. e is an integer and in νx,y,e f is the µ-th power of a linear form in in νx,y,e y and in νx,y,e x e ; more specifically, there exist c, d ∈ k such that in νx,y,e f = (in νx,y,e y -c in νx,y,e x e ) µ .

(3.3)

Proof. 1) =⇒ 2) Since e 0 > e, there exists a change of coordinates

x 1 = a 1 x + a 2 y l 1 , (3.4
)

y 1 = b 1 y + b 2 x l 2 (3.5) with a 1 , a 2 , b 1 , b 2 ∈ R * such that e 1 := e(x 1 , y 1 , f ) > e(x, y, f ). (3.6)
Replacing x by a -1 1 (x 1 -a 2 y l 1 ) does not change e, therefore, we may assume that x 1 = x. Since b 1 ∈ R * , we may assume that b 1 = 1. Now we will prove that e = l 2 .

Write

f = i+je 1 ≥µe 1 a ij x i y j 1 = i+je 1 ≥µe 1 a ij x i y + b 2 x l 2 j , (3.7)
where

a 0µ ∈ R * . Consider a monomial of the form a ij x i y j 1 with i + je 1 ≥ µe 1 . (3.8)
The element x i y j 1 belongs to the monomial ideal of R generated by the set

x i+sl 2 y j-s s ∈ {0, . . . , j} .

Let e = min{e 1 , l 2 }. (3.9)
Let us prove that e = e . Indeed, if i, j satislfy (3.8) then

i ≥ (µ -j)e 1 . (3.10)
If s ∈ {0, . . . , j} then, since l 2 ≥ e , we obtain

i + sl 2 ≥ (µ -j)e 1 + sl 2 ≥ (µ -(j -s))e . (3.11)
Thus e ≤ e. Combined with (3.6) and (3.9), this proves that e = l 2 < e 1 .

(3.12)

Combining (3.12) with (3.11), we obtain

i + sl 2 ≥ (µ -(j -s))l 2 (3.13)
and the inequality is strict unless i = 0 and j = µ. Thus

e = min α µ -β x α y β ∈ I(x, y, f ), β < µ = min sl 2 µ -(µ -s) s ∈ {1, . . . µ} = l 2 .
Therefore, e ∈ N and y 1 = y + ux e with u ∈ R * satisfies the conclusion of (2).

2) =⇒ 3) Let e = e(x, y-ux e , f ) and write f = (y-ux e ) µ + i + je ≥ µe (i, j) = (0, µ)

a ij x i (y-ux e ) j .
To prove 3) it is sufficient to prove that ν x,y,e

       i + je ≥ µe (i, j) = (0, µ) a ij x i (y -ux e ) j        > µe. Now, i + je ≥ µe (i, j) = (0, µ)
a ij x i (y -ux e ) j is contained in the monomial ideal (with respect to (x, y)), generated by monomials of the form j s a ij x i y j-s (ux e ) s with 0 ≤ s ≤ j, i + e j ≥ µe and if j = µ then i > 0. Now we have to prove that the quantity q = i + se + (j -s)e is strictly greater than µe. We have q = i + je. If j = µ, then i > 0 and q > µe. If j > µ then q > µe. If j < µ, then q = i + je ≥ e (µ -j) + je = µe -µe + e (µ -j) + je = µe + (µ -j)(e -e) > µe. This completes the proof of (3).

3) =⇒ 1) Choose u ∈ R * such that the natural image of u in k is c. We have f = (y -ux e ) µ + i,j a ij x i y j , with ν x,y,e
a ij x i y j > µe, that is i + je > µe for all the (i, j) appearing in the sum. Put y 1 = y -ux e . We will prove that e = e(x, y 1 , f ) > e.

We have f = y µ 1 + i,j j s=0 j s a ij x i+es y j-s with i + je > µe for each (i, j) in the sum.

Now we have e ≥ i+es µ-(j-s) > (µ-j)e+es µ-(j-s) = e whenever (j -s) < µ.

Remark 3.6. Let e denote the first characteristic exponent of f . If R is quasi-excellent, f is reduced and µ ≥ 2, we have

e ∈ 1 µ! N, (3.14)
that is, 1 ≤ e < ∞. Since in this paper we work with arbitrary regular two-dimensional local rings and not just the quasi-excellent ones, we will not use this fact in the sequel.

Fix a simple sequence of point blowings up as in (3.1). Let µ i (f ) and e i (f ) denote, respectively, the multiplicity and the first characteristic exponent of the strict transform of f in R i . Lemma 3.7. At least one of the following conditions holds:

(1)

(µ i+1 , e i+1 ) < lex (µ i , e i ) (2) e i (f ) = ∞.
Proof. To simplify the notation, we will consider the case when i = 0, so that R 0 = R. Assume that e i (f ) = ∞. Let f 1 be the strict transform of f in R 1 . We will follow the notation of ( [START_REF] Zariski | Commutative Algebra[END_REF],

Appendix 5, pagse 365-367). Namely, let ḡ denote the directional form of the local blowing up π 1 and f the natural image of f in gr m R.

Let µ = µ 0 denote the multiplicity of f at m. Since f is a homogeneous polynomial of degree µ, the greatest power of ḡ that could divide f is ḡµ . If ḡµ does not divide f , then by ( [START_REF] Zariski | Commutative Algebra[END_REF], Appendix 5, page 367, Proposition 2), we have µ 1 < µ and (1) of the Lemma holds.

Assume that ḡµ f . Then deg ḡ = 1 and there exists a regular system of parameters (x, y) such that ḡ = ȳ and

f = y µ + i+j>µ a ij x i y j ,
where the a ij are units of R. Let e = e 0 denote the first characteristic exponent of f and choose (x, y) in such a way that e = e(x, y, f

). Write f = y µ + i + je = µe (i, j) = (0, µ) a ij x i y j + i+je>µe a ij x i y j .
Since e < ∞, there exists (i, j) = (0, µ), with i + je = µe.

Now f 1 = y µ 1 + i + je = µe (i, j) = (0, µ) a ij x i+j-µ 1 y j 1 + i+je>µe a ij x i+j-µ 1 y j 1 .
Note that for each (i, j) with i + je = µe we have (i + j -µ) + j(e -1) = µ(e -1) and for each (i, j) with i + je > µe we have (i + j -µ) + j(e -1) > µ(e -1).

If s > e -1 then for (i, j) with i + je = µe we have (i + j -µ) = (µ -j)(e -1) < (µ -j)s, hence (i + j -µ) + js < µs.

If e -1 < 1 then µ 1 < µ. Otherwise, if e -1 ≥ 1, the above considerations prove that e(x 1 , y 1 , f 1 ) = e -1. By Proposition 3.5, in νx,y,e f is not a µ-th power of a linear form in in νx,y,e y and in νx,y,e x e . Hence in ν x 1 ,y 1 ,e-1 f 1 is not a µ-th power of a linear form in in ν x 1 ,y 1 ,e-1 y 1 and in ν x 1 ,y 1 ,e-1 x e 1 . Therefore e 1 = e(x 1 , y 1 , f 1 ) = e -1 < e. In all the cases (1) of the Lemma holds. Lemma 3.8. Let π * be an infinite sequence of local blowings up belonging to Π(R). Write π * as in (3.1). Take an element f ∈ R \ {0}.

(1) If f is a unit in R j 0 for some j 0 , then f is a unit in R j for all j ∈ N.

(2) At least one of the following conditions holds: (a) there exists i ∈ N such that f = x s i y t i u where x i and y i are regular parameters of R i , s and t are natural numbers and u is a unit of R i (b) there exists i 0 ∈ N such that e i (f ) = ∞ for all i ≥ i 0 .

Proof.

1. This follows directly from the fact that for all j ∈ N, we have m j = R j ∩ m j+1 .

2. First note that if x i and y i are regular parameters of R i , then either x i = x i+1 y i+1 and y i = y i+1 or x i = x i+1 and y i = y i x i x i+1 , with y i x i is either a unit in R i+1 or equal to y i+1 . Assume that condition (b) does not hold. From Lemma 3.7 we deduce that for each j ∈ N there exists j > j with µ j < µ j . Hence there exists j ∈ N with f j ∈ R * . Now by definition of f j , f j-1 = x µ j-1 f j , therefore, using the paragraph above and induction, we get the result.

For an element π * ∈ Π(R) we denote R = i R i . The ring R is an integral domain with quotient field F , dominating R and R i for each i ∈ N. Proposition 3.9. Assume that there exists f ∈ R, satisfying condition (2)(b) in Lemma 3.8. Then there exists a unique Krull valuation ν on F such that R ν dominates R.

Moreover, we have:

1. rk ν = 2.
2. The set of elements in R satisfying condition (2)(b) in Lemma 3.8 is a prime ideal generated by an irreducible element g.

3. let g i denote the strict transform of g in R i . Then ν is the composition of the g-adic valuation of F with the unique rank one Krull valuation, centered in the one-dimensional local rings R i (f i ) for each i ∈ N.

Proof. Since R is an integral domain with field of fractions F , there exists a valuation ring R ν dominating R.Let Γ denote the value group of this valuation. Now to prove the uniqueness of ν it is sufficient to prove the conditions (1), ( 2) and (3).

1. Let f i denote the strict transform of f in R i . We have µ i = µ i 0 > 0 for all i ≥ i 0 . Let (x i 0 , y i 0 ) be a regular system of parameters of R i 0 such that f i 0 = y µ i 0 i 0 + terms of higher degree. Since µ i = µ i 0 , we have x i 0 = x i 0 +1 . Now f i 0 +1 = y µ i 0 i 0 + terms of higher or equal degree. Repeating the same reasoning, we see that for each i ≥ i 0 we have x i = x i 0 and

f i = x µ i+1 i+1 f i+1 = x µ i 0 i 0 f i+1 . Thus f i 0 = x (i-i 0 )µ i 0 i 0 f i for each i > i 0 . Since f i ∈ R ν
for all i, we have ν(f i ) > 0 for all i. Hence ν(f i 0 ) > iµ i 0 ν(x i 0 ) for all i, so ν(f i 0 ) cannot belong to a subgroup of Γ of rank 1. Therefore rk(ν) = 2.

2. Let Γ 1 denote the isolated subgroup of Γ of rank 1 (that is, the unique proper non-trivial subgroup of Γ). Let P be the prime ideal of R ν associated to Γ 1 . Let P = P ∩ R. Then P is a prime ideal of height 1 in R, therefore it is generated by an irreducible element g. Now f = hg n with h / ∈ P , hence ν(h) ∈ Γ 1 . Therefore, by the proof of (1), there exists i such that h i the strict transform of h in R i is a unit. Now the strict transform of f in R i is h i .g n i . Therefore g must also satisfy condition (2)(b) in Lemma 3.8. An element of R satisfies condition (2)(b) in Lemma 3.8 if and only if it belongs to P .

3. This is a direct consequence of (1) and (2). Proposition 3.10. Let π * be an element of Π(R) and write π * as in (3.1). Suppose that R does not contain an element f satisfying condition (2) (b) of Lemma 3.8. The following statements hold.

(1) The ring R is a valuation ring with field of fractions F , dominating R and R i for each i ∈ N.

(2) Conversely, let R µ be a valuation ring with field of fractions F , dominating R and R i for each i ∈ N. Then R µ = R.

In other words, the simple blowing up sequence π * and the valuation µ determine each other uniquely; they are equivalent sets of data.

Proof. (1) Since R < R i < R j for all natural numbers i ≤ j, R is a domain with quotient field F , dominating R and R i for each i ∈ N. First, consider the case when the sequence

π * : (R, m) π 1 -→ (R 1 , m 1 ) π 2 -→ . . . πn -→ (R n , m n ) is finite. Then R = R n . By definition, m n is principal and (R n , m n ) is a discrete valuation ring.
Next, assume that π * is infinite. To prove that R is a valuation ring, consider an element f ∈ F * , and write

f = f 1 f 2 where f 1 , f 2 ∈ R \ {0}.
By Lemma 3.8 there exists i ∈ N such that f 1 = x s 1 i y t 1 i u 1 and f 2 = x s 2 i y t 2 i u 2 , where x i and y i are local parameters in R i , s 1 , t 1 , s 2 and t 2 are natural numbers and u 1 , u 2 are units in R i . Hence

f = x s i y t i u, (3.15)
where s and t are integers (not necessarily positive) and u is a unit in R i . If both s and t are non-negative then f ∈ R i ⊂ R, as desired. If both s and t are non-postive then 1 f ∈ R i ⊂ R, as desired. Otherwise assume, without loss of generality, that s > 0 and t < 0. Now after another blowing up, we have the following three possibilities:

f = x s i+1 y s+t i+1 u or (3.16) f = x s+t i+1 y t i+1 u or (3.17) f = y s+t i+1 v (3.18)
where x i+1 and y i+1 are local parameters in R i+1 and, in the last equation, v is a unit in R i+1 . If (3.18) holds and s+t ≥ 0 then f ∈ R i+1 ⊂ R. If (3.18) holds and s+t ≤ 0 then f -1 ∈ R i+1 ⊂ R. According to Remark 2.4 (2), R is a valuation ring. Finally, if either (3.16) or (3.17) holds, we notice that the blowing up π i+1 has strictly decreased the quantity |s| + |t|. Since this quantity cannot decrease indefinitely, after finitely many steps we will arrive either at (3.15) with s and t of the same sign or at (3.18), thus reducing the problem to one of the previous cases. Note also that if f is of the form (3.15) with s and t of the same sign then the blowing up π i+1 brings f to the form (3.18). This completes the proof of (1).

(2) Conversely, let R µ be a valuation ring such that R i < R µ for all i ∈ N. Taking the direct limit as i tends to infinity, we obtain R < R µ . Now part (2) follows from (1) and the implication (a)=⇒(c) of Remark 2.4 (2). However, we give below a direct proof of (2) for the sake of completeness.

If the sequence π * is finite, its last ring R n is a discrete valuation ring. Let x n be a local parameter of R n . We have µ(x n ) > 0 since µ is centered at m n . Now any element f of F * can be written as f = x s n u where s ∈ Z and u is a unit of R n (hence also a unit of R µ ) and therefore

f ∈ R n if and only if f ∈ R µ . If π * is infinite, let f ∈ F * .
As in the proof of part (1), there exists i such that f = x s i u or f = y s i u with x i and y i local parameters in R i , s ∈ Z and u is a unit in R i . Now since π * is infinite, we have ν(x i ) > 0 and ν(y i ) > 0 and u is also a unit of R µ since R i < R µ . Hence to say that f ∈ R is equivalent to saying that s ≥ 0, which is equivalent to saying that µ(f ) ≥ 0. Therefore R = R µ .

Corollary 3.11. The set of valuations of F centered at R is in a natural one-to-one correspondence with Π(R).

Proof. For the sake of completeness, we now give an explicit description of the element of Π(R), associated to a given valuation µ by the above bijection and vice versa.

Let µ be a valuation centered at R. The center of µ in R is ξ 0 := m. Consider the point blowing up π * 1 :

X 1 -→ Spec R along ξ 0 . The center of µ in X 1 is the unique point ξ 1 ∈ X 1 whose local ring O X 1 ,ξ 1 is dominated by R µ . Put R 1 := O X 1 ,ξ 1 ,
and let m 1 := m X 1 ,ξ 1 be its maximal ideal. If m 1 is principal, stop here. Otherwise, fix x 1 , y 1 ∈ R 1 such that m 1 = (x 1 , y 1 ). We have (R, m) < (R 1 , m 1 ) < (R µ , m µ ). Now repeat the same procedure with (R, m) replaced by (R 1 , m 1 ). Continuing in this way we obtain the simple sequence π * (µ) (finite or infinite) of local point blowings up of Spec R.

Now we have two cases:

Case 1: The ring R does not contain an element f satisfying condition (2) (b) in Lemma (3.8).

Letting R = lim i→∞ R i , we have R = R µ .

Conversely, take any element π * ∈ Π(R) and let R be as in Proposition 3.10. Let µ to be the valuation on F with valuation ring R. It is clear that π * (µ) described above is equal to π * . Recall that k denotes the residue field of R. Theorem 3.12. There is a natural order preserving bijection between valuations of F centered at R and valuations of k(x, y) centered at k[x, y] (x,y) .

Proof. By Proposition 3.10, the set of valuations of F centered at R is in a natural one-to-one correspondence with Π(R). Also by Proposition 3.10 applied to k[x, y] (x,y) , the set of valuations of k(x, y) centered at k[x, y] (x,y) is in a natural one-to-one correspondence with Π(k[x, y] (x,y) ). Finally, there is a natural one-to-one correspondence between Π(R) and Π(k[x, y] (x,y) ). Clearly all those correspondences fit together to give a natural order preserving bijection between valuations of F centered on R and valuations of k(x, y) centered on k[x, y] (x,y) .

A Complete Set of Key Polynomials

Let ν ∈ V. Fix local coordinates x and y such that ν(x) = 1. Let K = k(x). Let ν be the valuation of k(x, y) corresponding to ν under the bijection of Theorem 3.12.

The goal of this section is to construct a set of polynomials, complete for ν (the definition is given below). This set will be our main tool for constructing the valuative tree. Definition 4.1. Let Q be a monic polynomial in K[y], with ν(Q) ≥ ν(y). We say that Q is an abstract key polynomial for ν if for each polynomial f satisfying

Definition and Basic Properties of Key Polynomials

ν (f ) ≥ ν (Q), we have deg(f ) ≥ deg(Q).
For the rest of the paper, we will say key polynomial for abstract key polynomial.

For a monic polynomial Q in K[y] and a g ∈ K[y] we can write g in a unique way as

g = s j=0 g j Q j , (4.1)
with all the g j ∈ K[y] of degree strictly less than deg(Q).

Definition 4.2. For every monic polynomial Q and every polynomial g in K[y], we call the expression (4.1) the Q-expansion of g. We define ν Q (g) := min 0≤j≤s ν(g j Q j ). We call ν Q the truncation of ν with respect to Q.

Proposition 4.3. (Proposition 12 of [3]) If Q is a key polynomial for ν then ν Q is a valuation.
The following proposition is a direct consequence of Proposition 19 [3] that states that each key polynomial for ν is ν-irreducible. Proposition 4.4. If Q is a key polynomial for ν then Q is irreducible. Proposition 4.5. Every monic linear polynomial Q in K[y] is a key polynomial for ν.

Proof. For any monic linear polynomial Q ∈ K[y] and for any c ∈ K, we have

ν (Q) = ν(Q) > -∞ = ν (c).
The first part of the next proposition is Theorem 27 of [3] and the second part is obvious. Proposition 4.6. (1) Let µ be a valuation of K(y) such that µ < ν, and let Q be a monic polynomial of minimal degree in y such that µ(Q) < ν(Q). Then Q is a key polynomial for ν.

(2) Furthermore, we have µ < ν Q ≤ ν and the value group Γ Q of ν Q is equal to Γ µ + βZ where Γ µ is the value group of µ and β = ν(Q).

Let µ be a valuation of K(y) such that µ < ν, and let Q be a monic polynomial of minimal degree in y such that µ

(Q) < ν(Q). Let β ∈ R, with µ(Q) < β.
We define a new valuation µ in the following way:

For a polynomial g ∈ K[y], let g = s j=0 g j Q j be the Q-expansion of g. Put µ (g) := min 0≤j≤s {µ(g j ) + jβ}.
We call µ the augmented valuation constructed from µ, Q, and β, and we denote it by [µ, Q, β].

For further details on augmented valuations, see [17].

A Complete Set of Key Polynomials: the Definition

Let β 0 = ν(x) = 1 and β 1 = ν(y). Let Γ ν = ν(F ) ⊂ R denote the augmented value group of ν.
For an element β ∈ Γ ν , let P β be as defined at thte end of §2, but with F replaced by K(y):

P β = {f ∈ K(y) | ν(f ) ≥ β}.
Definition 4.7. A complete set of key polynomials for ν is a set

Q = {Q i } i∈I
where I is a well ordered set, each Q i is a key polynomial in K[y] for ν, and for each β ∈ Γ ν the additive group P β ∩ K[y] is generated by products of the form a

s j=1 Q γ j i j , a ∈ K, such that s j=1 γ j ν(Q i j ) + ν(a) ≥ β.
In [6] it is proved that every valuation ν admits a complete set Q = {Q i } i∈I of key polynomials.

Remark 4.8. If Q = {Q i } i∈I is a complete set of key polynomials for ν, we will always assume that the well ordering of I has the following property: for i < j in I, we have ν(Q i ) < ν(Q j ).

Basic Structure

Let µ be a valuation of K(y) with µ < ν. Suppose that the subset Γ µ+ of positive values of Γ µ = µ(K(y)) is a well ordered set (with the standard order relation in R). Note that this assumption is equivalent to saying that Γ µ ∼ = Z.

We will use the following notation:

1. Let d µ (ν) be the minimal degree of a monic polynomial f in K[y] satisfying µ(f ) < ν(f ).

Put Φ

µ (ν) := Q ∈ K[y] | Q is monic, deg y (Q) = d µ (ν), µ(Q) < ν(Q) . 3. Put Ψ µ (ν) := ν (Φ µ (ν)) = ν(Q) ∈ K[y] | Q is monic, deg y (Q) = d µ (ν), µ(Q) < ν(Q) . Write Q = Q + z, with deg y (z) < d µ (ν). Then f = a s (Q -z) s + • • • + a 0 , and the Q -expansion of f involves a s Q s . Therefore we have ν(a s Q s ) = ν Q (a s Q s ) ≥ ν Q (f ) > ν Q (f ) = ν(a s Q s ), which is a contradiction. Lemma 4.11. Let f ∈ K[y] be such that ν Q (f ) = µ(f ) (4.2)
and let f = qQ + r be the Euclidean division of f by

Q in K[y]. Then ν Q (f ) = ν Q (r) < ν Q (qQ).
Proof. By definition of ν Q , we have

ν Q (qQ) ≥ ν Q (f ). (4.3)
Suppose we have equality, aiming for contradiction:

ν Q (qQ) = ν Q (f ). (4.4) Then ν Q (r) ≥ ν Q (f ). (4.5) By definition of ν Q , we have µ(r) = ν Q (r). (4.6)
Combining (4.2), (4.5) and (4.6), we obtain µ(f ) ≤ µ(r). Then

µ(f ) ≤ µ(qQ). (4.7)
We have ν Q (qQ) > µ(qQ).

(qQ) > µ(qQ) ≥ µ(f ) = ν Q (f ) = ν Q (qQ),
which is a contradiction.

Proposition 4.12. (Theorem 9.4 [START_REF] Maclane | A construction for absolute values in polynomial rings[END_REF],Theorem 1.11 [17]) Let Q be a monic polynomial of minimal degree among those satisfying

ν Q (Q ) < ν(Q ). Then the Q-expansion of Q is given by Q = Q s + a s-1 Q s-1 • • • + a 0 with ν Q (Q ) = sβ µ (ν) = ν(a 0 ).
Proof. First, let Q = qQ + a 0 be the Euclidean division of Q by Q. We have

ν(Q ) > ν Q (Q ) = inf{ν Q (qQ), ν(a 0 )} by definition of ν Q . Hence ν(qQ) = ν(a 0 ) = ν Q (Q ).
Since deg y (a s ) < d µ (ν) and Q is irreducible in K[y] by Proposition 4.4, there exist g and h in K[y] with deg y (g) < d µ (ν) and ga s + hQ = 1. Now ga s = -hQ + 1, ν Q (a s ) = µ(a s ) and ν Q (g) = µ(g), therefore by Lemma 4.11 we have ν(ga s ) = ν(1) < ν(-hQ). Now for each j, 0 ≤ j ≤ s -1, let ga j = q j Q + r j be the Euclidean division of ga j by Q in K[y]. Since ν Q (a j ) = µ(a j ) and ν Q (g) = µ(g), by Lemma 4.11 we have ν(ga j ) = ν(r j ) < ν(q j Q).

Consider the polynomial

Q = Q s + r s-1 Q s-1 + • • • + r 0 . We have Q -gQ = (r s -ga s )Q s + (r s-1 -ga s-1 )Q s-1 + • • • + r 0 -ga 0 , with r s = 1. Therefore ν Q (Q -gQ ) ≥ inf 0≤j≤s {ν(r j -ga j ) + jβ µ (ν)} > inf 0≤j≤s {ν(r j ) + jβ µ (ν)} = ν Q (Q ) and ν Q (Q -gQ ) > ν Q (Q ) = ν Q (gQ ). If ν(Q ) = ν Q (Q ) then ν(Q -gQ ) ≥ ν Q (Q -gQ ) > ν Q (Q ) = ν(Q ) and we have ν(Q ) = ν(gQ ) > ν Q (gQ ) = ν Q (Q ), which is impossible. Hence ν(Q ) > ν Q (Q ).
Since Q is chosen of minimal degree we must have deg y (Q ) ≥ deg y (Q ), but this implies that deg y a s = 0 and a s = 1.

We still have to prove that ν

Q (Q ) = ν(Q s ). By definition of ν Q we have ν(Q s ) ≥ ν Q (Q ). Suppose that ν(Q s ) > ν Q (Q ), then ν Q (Q ) = ν Q (f ), where f = Q -Q s . But since deg y (f ) < deg y (Q ), we have ν Q (f ) = ν(f ). We obtain ν(Q s ) = ν Q (Q s ) > ν Q (Q ) = ν Q (f ) = ν(f ). This implies that ν(Q ) = ν(f ), which leads to ν(Q ) = ν Q (Q ), a contradiction. Corollary 4.13. If Q ∈ K[y] is monic with deg y (Q ) = d µ (ν) and ν(Q ) > ν Q (Q ) then ν Q (Q ) = β µ (ν).
Proof. This is a special case of Proposition 4.12 when deg y (Q ) = d µ (ν). Proposition 4.14. Let {Q i } i∈I be a set of key polynomials for ν, with I a well ordered set and deg y (Q i ) ≤ deg y (Q j ) for i < j in I. Let ν i := ν Q i be the truncation associated with each Q i . Then the set {Q i } i∈I is a complete set of key polynomials if and only if for each polynomial f ∈ K[y] there exists an element i ∈ I(ν) such that ν(f ) = ν i (f ) and deg y Q i ≤ deg y f . Proof. To say that {Q i } i∈I(ν) is a complete set of key polynomials is equivalent to saying that every f ∈ K[x] can be written in the form

f = γ a γ s j=1 Q γ j j , (4.9)
where s is a strictly positive integer, γ = (γ 1 , . . . , γ s ) ranges over a finite subset of N s , a γ ∈ K and

s j=1 γ j ν(Q j ) + ν(a) ≥ ν(f ).
Proof of "if ". Assume that for each f ∈ K[x] there exists an integer i as in the Proposition. We will construct the expression (4.9) recursively in deg y f . Assume that an expression of the form (4.9) exists for every polynomial of degree strictly less than deg y f . Put β = ν(f ) and let i be such that β = ν i (f ) and deg y

Q i ≤ deg y f . Write f = s i j=0 c j Q j i , (4.10)
where each c j Q j i ∈ P β and deg y c j < deg y Q i ≤ deg y f . By the induction assumption, each of the c j admits an expansion of the form (4.9). Substituting all of these expansions into (4.10), we obtain the desired expansion (4.9) of f . This completes the proof of "if".

Proof of "only if ". Conversely, take f ∈ K[y]. Let β = ν(f ). Write f in the form (4.9). Then

β = ν(f ) ≥ ν s (f ) ≥ min ν s c γ Q γ j j = min ν c γ Q γ j j ≥ β.
Thus all the inequalities in the above formula are equalities, so the natural number i := s satisfies the conclusion of "only if".

Construction of a Complete Set of Key Polynomials

First we put Q 1 := y and d 1 (ν) = 1. By Proposition 4.5, Q 1 is a key polynomial for ν. Consider the valuation ν 1 := ν Q 1 . We have ν 1 ≤ ν. If ν 1 = ν then the algorithm stops here, we put I(ν) = {1} and {Q i } i∈I(ν) = {Q 1 }. We will prove in Proposition 4.16 below that {Q i } i∈I(ν) is complete for ν. Now suppose that ν 1 < ν. Then we can apply the results of §4.

3 to µ = ν 1 . Put d 2 (ν) = d ν 1 (ν), Φ 1 (ν) = Φ ν 1 (ν), Ψ 1 (ν) = Ψ ν 1 (ν) and β 2 (ν) = β ν 1 (ν). Choose Q 2 ∈ Φ 1 (ν) such that ν(Q 2 ) = β 2 (ν) and let ν 2 := ν Q 2 .
We have ν 1 < ν 2 ≤ ν. If ν 2 = ν, then the algorithm stops here, we put I(ν) = {1, 2} and

{Q i } i∈I(ν) = {Q 1 , Q 2 }. By Proposition 4.16 below, {Q i } i∈I(ν) is complete for ν.
Otherwise, if ν 2 < ν, we can apply the results of §4.3 to µ = ν 1 and repeat the same process with ν 1 replaced by ν 2 .

Assume that for a certain natural number n ≥ 2 a set {Q i } i≥n has been constructed. If ν n = ν then, by Proposition 4.14 and Proposition 4.16 below, {Q i } i≥n is complete for ν. The construction stops here.

Otherwise, we have ν n < ν. Let us apply the results of §4.3 to µ = ν n . Put Choose Q n+1 ∈ Φ n (ν) such that ν(Q n+1 ) = β n+1 (ν) and let ν n+1 := ν Q n+1 . Repeating this process, there are two possibilities. The first is that we find valuations {ν i } i≤n and key polynomials {Q i } i≤n such that ν n = ν. The second is that we construct an infinite set {Q i } i∈N of key polynomials and valuations {ν i } i∈N . We will study this case after Proposition 4.16.

Since β i+2 (ν) > β i+1 (ν), we have Ψ i (ν) ∩ Ψ i+1 (ν) = ∅.

Next, suppose that β i+1 (ν) is not a maximal element in Ψ i (ν). Let β ∈ Ψ i (ν) \ {β i+1 (ν)}. Choose Q ∈ Φ i (ν) such that ν(Q) = β and write Q = Q i+1 + z. Since β > β i+1 (ν), we have ν(z) = β i+1 (ν) and ν i+1 (Q) = β i+1 (ν) < β = ν(Q). We have proved that Q ∈ Φ i+1 (ν), therefore d i+2 (ν) = d i+1 (ν) and β ∈ Ψ i+1 (ν). Thus Ψ i (ν) \ {β i+1 (ν)} ⊂ Ψ i+1 (ν). Now let β ∈ Ψ i+1 (ν). By Corollary 4.13, we have β > β i+1 (ν). Take an element

Q ∈ Φ i+1 (ν)
such that ν(Q) = β. We have deg y (Q) = d i+2 (ν) = d i+1 (ν), and ν(Q) > ν i+1 (Q) ≥ ν i (Q), hence Q ∈ Φ i (ν) and β ∈ Ψ i (ν) \ {β i+1 (ν)}.

Corollary 4.18. If Ψ i (ν) is infinite for some i ∈ I(ν), then Ψ i+1 (ν) is infinite and

Ψ i+1 (ν) ⊂ Ψ i (ν).
Corollary 4.19. Let i 0 = inf {i ∈ N | #Ψ i (ν) = ∞}, then for each i ≥ i 0 , the value group Γ i of ν i is equal to the value group Γ i 0 of ν i 0 .

Proof. This is a direct consequence of Proposition 4.9 (2) and Corollary 4.18.

First, suppose we are in Case 1: Proposition 4.20. The degrees d i (ν) are unbounded in N.

Proof. Take an element i ∈ I(ν). We will prove that there exists j ∈ I(ν) such that d j (ν) > d i+1 (ν).

Since Ψ i (ν) is finite, it admits a maximal element α. If β i+1 (ν) = α then, by Proposition 4.17, we have d i+2 (ν) > d i+1 (ν). Suppose that β i+1 (ν) is not maximal. By Proposition 4.17 we have Ψ i+1 (ν) = Ψ i (ν) \ {β i+1 (ν)}, therefore α is also the maximal element of Ψ i+1 (ν). Now repeat the same reasoning: if β i+2 (ν) = α, then d i+3 (ν) > d i+2 (ν) = d i+1 (ν), otherwise we have Ψ i+2 (ν) = Ψ i+1 (ν) \ {β i+2 (ν)} and α is the maximal element of Ψ i+2 (ν). The process must end since Ψ i (ν) is finite. 1. If ν -1 (∞) = {0} then the set {Q i } i∈I(ν) is complete for ν.

2. If ν -1 (∞) = {0} then there exists a key polynomial Q ω for ν, that generates the ideal ν -1 (∞) and it is of minimal degree such that ν i (Q ω ) < ν(Q ω ) for all i ∈ N. Moreover, the set {Q i } i∈I(ν) ∪ {Q ω } is complete for ν.

. 2 )

 2 denote the set of all the simple sequences (finite or infinite) of local point blowings up of Spec R. Fix an element f ∈ R \ {0}. Let µ denote the multiplicity of f at m. Assume that f / ∈ x, y µ+1 . (3Definition 3.2. A monomial ideal in a regular local ring A, with regular system of parameters (u 1 , . . . , u s ) is an ideal in A generated by monomials in (u 1 , . . . , u s ).

Definition 3 . 4 .Proposition 3 . 5 .

 3435 The monomial valuation ν x,y,e of R, associated to the data (x, y, e) is the valuation defned by ν x,y,e (g) = max{ξ ∈ R | g ∈ I ξ }.Let R * denote the set of units in R. Let e 0 be the first characteristic exponent of f at m. Let e = e(x, y, f ).

Case 2 :

 2 The ring R does contain an element f satisfying condition (2) (b) in Lemma (3.8) then by Proposition (3.9) the valuation ν is uniquely determined by π * .

For

  each strictly positive integer b, we write ∂ b := ∂ b b!∂y b , the b-th formal derivative with respect to y. For each polynomial P ∈ K[y], let ν (P ) := max b∈N ν(P )-ν(∂ b P ) b , I ν (P ) := b ∈ N ν(P ) -ν(∂ b P ) b = ν (P ) . and b ν (P ) := min I ν (P ).

(4. 8 )

 8 Combining (4.2), (4.4), (4.7) and (4.8), we get ν Q

d

  n+1 (ν) = d νn (ν), Φ n (ν) = Φ νn (ν), Ψ n (ν) = Ψ νn (ν) and β n+1 (ν) = β νn (ν).

Theorem 4 .

 4 21. The set of key polynomials {Q i } i∈I(ν) is complete for ν. Proof. Let f ∈ K[y]. By Proposition 4.20, there exists i ∈ I(ν) such that d i (ν) > deg y (f ). Now the result follows from Proposition 4.14 and Proposition 4.16. Suppose we are in Case 2.

Proposition 4.9. The set Ψ µ (ν) is contained in Γ µ+ or in Γ µ+ ∪ {α}, where α is a maximal element of Ψ µ (ν) if it exists. Moreover, Ψ µ (ν) is bounded below by dµ(y) ≥ 0.

Proof. Let d := d µ (ν). First we will show that Ψ µ (ν) is bounded below by d • µ(y). Let β ∈ Ψ µ (ν) and choose Q ∈ Φ µ (ν) such that ν(Q) = β. Suppose that β < dµ(y) and write Q = y d + g, with g ∈ K[y], deg y (g) < d. Since µ y d = dµ(y) > β = ν(Q) > µ(Q), we have µ(Q) = µ(g). Since ν(y d ) ≥ µ(y d ) = dµ(y) > β = ν(Q), we have ν(Q) = ν(g), but ν(g) = µ(g) by definition of d, therefore ν(Q) = µ(Q), which is a contradiction. Now we will prove that any element β ∈ Ψ µ (ν) which is not a maximal element must be in Γ µ .

Suppose that β and α are two elements of Ψ µ (ν) such that β < α.

Since α > β, we have ν(Q) = ν(z). But ν(z) = µ(z) by definition of d µ (ν). Hence β ∈ Γ µ .

From Proposition 4.9 we see that Ψ µ (ν) is well ordered. We will denote by β µ (ν) the smallest element of Ψ µ (ν).

Choose Q ∈ Φ µ (ν) such that ν(Q) = β µ (ν). By Proposition 4.6, Q is a key polynomial for ν, the truncation ν Q is a valuation with µ < ν Q ≤ ν, and the augmented value group Γ Q of ν Q is Γ µ + β µ (ν)Z. Hence the set Γ Q+ of positive values of Γ Q is a well ordered set.

If ν Q < ν, we can repeat the same process as above with µ replaced by ν Q .

Moreover, the valuation ν Q does not depend on the choice of Q, as we will prove in the following proposition. Proposition 4.10. With the notation as above, if

Proof. Fix a polynomial f ∈ K[y] such that ν(f ) < ∞. We have the following inequalities:

By Corollary 4.19, all those values belongs to the value group Γ i 0 of ν i 0 , where i 0 ∈ I(ν) is defined in Corollary 4. [START_REF] Vaquié | Famille admissible de valuations et défaut d'une extension[END_REF].

Now 1) follows from Proposition 4.14.

To prove 2), suppose that ν -1 (∞) = {0}. The set ν -1 (∞) is an ideal in K[y], it can be generated by one element. Choose Q ω to be a monic polynomial that generates ν -1 (∞). The polynomial Q ω has minimal degree among the polynomials in ν -1 (∞).

We have ν (Q ω ) = ∞, and Q ω of minimal degree with this property, hence Q ω is a key polynomial for ν.

We have ν = ν ω := ν Qω , and for any polynomial

, by the discussion at the beginning of the proof, there exists i ∈ I(ν) such that

For the rest of the paper if Q ω exists, we put I(ν) = N ∪ {ω}.

We denote:

1. D(ν) := max i∈I(ν) {d i (ν)}, if this maximum exists; otherwise, we put D(ν) = ∞.

2. N (ν) the maximal element of I(ν), if this maximum exists, otherwise, we put N (ν) = ∞. Remark 4.23. From the construction above we see that:

we are in the case where there exists i ∈ I(ν)

5 The order relation on V

Invariants of comparable valuations

Let μ and ν be two elements of V with μ < ν. Choose local coordinates x and y such that ν(x) = μ(x) = 1.

Put K = k(x) and let µ and ν be the valuations of K(y), corresponding to μ and ν, respectively.

Let {Q i } i∈I(ν) be a complete set of key polynomials associated to ν.

Lemma 5.1. There exists

Proof. Suppose that for all i ∈ I(ν) we have µ(

of minimal degree among the polynomials having this property.

Finally, we get ν(qy) = ν(r) = µ(r) = µ(qy). But ν(qy) = ν(q) + ν(y) > µ(q) + µ(y) = µ(qy), and we have a contradiction.

Take an integer i, 1 < i < i 0 (in particular i ∈ N), and suppose inductively that for all j, 1 ≤ j < i, we have ν j = µ j , β j (µ) = β j (ν) and d j (µ) = d j (ν).

We will first prove that

To prove the equality, we will prove that µ

In this case, we will have β i (µ) = µ(Q i ), and since by definition of i 0 , µ(Q) = ν(Q), we get the desired equality. Let f be such a polynomial. Write

Proposition 5.4. We have i 0 < ω. In other words, i 0 ∈ N.

Proof. Suppose that ω ∈ I(ν) and i 0 = ω. By Remark 4.23 (3) and Corollary 4.19, there exists

Let us show that

Indeed, assume that there exists i ∈ I(ν) \ {ω}, such that

This implies that ν(qQ i+1 ) > ν(r). Hence ν(Q ω ) = ν(r) and ν(r) = ∞, then r must be equal to 0 and q = 1, since ν -1 (∞) = (Q ω ). But Q i+1 = Q ω and we have a contradiction.

By Proposition 5.3 we have ν i = µ i , hence

We have a strictly increasing sequence in Γ i 1 , it most be unbouded in R, hence µ(Q ω ) = ∞. This contradicts the fact that µ(Q ω ) < ν(Q ω ).

Proposition 5.5. Either µ = ν i 0 -1 or µ = µ i 0 < ν i 0 .

Proof. As in the proof of Proposition 5.3, we have

. We will prove that in this case we have µ = ν i 0 -1 .

Suppose, aiming for contradiction, that there exists f ∈ K[y] such that µ(f ) > µ i 0 -1 (f ), and choose f of minimal degree among all the polynomials having this property. Since

Let f = qQ i 0 + r be the Euclidean division of f by Q i 0 . By the minimality of deg f , we have µ(q) = µ i 0 -1 (q) and µ(r) = µ i 0 -1 (r).

We have

Suppose first that ν i 0 and µ i 0 are comparable. Without loss of generality, we may assume that µ i 0 < ν i 0 . In this case put µ ∧ ν = µ i 0 . Clearly µ i 0 ≤ ν and µ i 0 ≤ ν.

Let ν be a valuation of k(x, y) such that ν ≤ µ and ν ≤ ν. Since ν ≤ ν, we have ν (x) = 1. We know from Remark 5.7 (1) that N (ν ) < N (µ) and N (ν ) < N (ν). Let {ν i } i≤N (ν ) be the truncations associated to ν . From Remark 5.7 (2) we know that for each i < N (ν ) we have ν i = µ i and ν i = ν i , therefore

Next, suppose that ν i 0 and µ i 0 are not comparable. In particular, we have i 0 > 1 (since µ 1 and ν 1 are always comparable). Put µ ∧ ν = µ i 0 -1 = ν i 0 -1 . Choose ν as in the paragraph above and let {ν i } i≤N (ν ) be the truncations associated to ν . By Remark 5.7 (3) the valuations ν and ν have the same set of N (ν ) key polynomials, and the valuations ν and µ have the same set of N (ν ) key polynomials. Therefore if, N (ν ) = i 0 , we would have

Theorem 5.9. Let S be a totally ordered convex subset of V. Then S has a majorant in V.

Remark 5.10. A short proof of a more general version of this result -one for rings of arbitrary dimension -is given in Lemma 3.9 (i) of [START_REF] Novacoski | Valuations centered at a two-dimensional regular local ring: Infima and Topologies[END_REF] using elementary properties.

Proof. Since we are searching for a majorant, we may assume that S contains νm . Since S is totally ordered, we can fix local coordinates x and y such that ν(y) ≥ ν(x) = 1 for all ν ∈ S. By Theorem 3.12, there exists a totally ordered convex subset S of the set of valuations over k(x, y), satisfying 1 = ν(x) ≤ ν(y) for all ν ∈ S, and such that S contains ν m . Also by Theorem 3.12 the set S has a majorant in V if and only if the set S has a majorant in the set of valuations over k(x, y), satisfying 1 = ν(x) ≤ ν(y).

By Corollary 5.6, if S contains an element ν with N (ν) = ∞ or it contains an element ν with β N (ν) (ν) = ∞ then S has a maximal element. Suppose that S does not contain a maximal element.

By Remark 5.7 (1), N (ν) and D(ν) define increasing functions on S.

We claim that there exists an initial segment I ⊂ N and a set of monic polynomials {Q i } i∈I(S) such that for every valuation ν ∈ S the set {Q i } i∈I(ν) is complete for ν (the fact that I ⊂ N follows from the fact that S does not contain a maximal element). Indeed, take ν ∈ S, N ∈ N and let {Q i } i≤N be a complete set of key polynomials for ν. Let ν ∈ S. If ν < ν, then by Remark 5.7 (3) the set {Q i } i≤N (ν ) is a complete set of key polynomials for ν . Otherwise, if ν > ν, then, again by Remark 5.7 (3), we can add to {Q i } i≤N the key polynomials {Q i } N <i≤N (ν) to obtain a complete set of key polynomials for ν . Suppose first that N (ν) is bounded from above. In this case there exists N ∈ N with I(S) = {1, . . . , N }, and a valuation ν ∈ S with N (ν) = N .

The set {β

Then µ is a majorant for S.

We have D(ν) < ∞ for all ν ∈ S since S does not contain a maximal element. Consider the set D(S) = {D(ν) | ν ∈ S}. Again, we have two cases, either D(S) has a maximal element D, or it is unbounded in N.

Suppose first that D(S) is unbounded in

Note first that this maximum is well defined. Indeed, let

For every ν ∈ S with ν ≤ ν we have ν(f ) = ν (f ). It is not difficult to verify that µ is a valuation on k(x, y) and that µ is a majorant for S. Now suppose that D(S) has a maximal element D. There exists a cofinal sequence

We claim that for every f ∈ K[y], if there exists i ∈ I(S) with ν i (f ) = ν i+1 (f ) then ν j (f ) = ν i (f ) for all j ∈ I(S), j ≥ i. Indeed, let i ∈ I(S) be such that ν i (f ) = ν i+1 (f ). By construction, we have

. Now for all j > i we have

If for all f ∈ K[y] there exists i ∈ I(S) with ν i (f ) = ν i+1 (f ), we put µ(f ) := max i∈I(S) {ν i (f )}.

(5.1)

Otherwise, if there exists f ∈ K[y] with

take f monic of minimal degree, satisfying (5.2). We have deg y (f ) > D by definition of the polynomials Q i and the valuations ν i . Put µ(f ) = ∞. For a polynomials g ∈ K[y], let g = qf +r be the Euclidean division of g by f , and put µ(g) = max i∈I(S) {ν i (r)}. Then µ is a valuation of k(x, y) which is a majorant for S.

6 Nonmetric Tree Structure on V

We will now define rooted non-metric trees. Definition 6.1. A rooted non-metric tree is a poset (T , ≤) such that:

(T1) Every set of the form I τ = {σ ∈ T | σ ≤ τ } is isomorphic (as an ordered set) to a real interval.

(T2) Every totally ordered convex subset of T is isomorphic to a real interval.

(T3) Every non-empty subset S of T has an infimum in T .

Let us consider the following special case of the condition (T3):

(T3 ) There exists a (unique) smallest element τ 0 ∈ T . Lemma 6.2. (Lemma 3.4 [START_REF] Novacoski | Valuations centered at a two-dimensional regular local ring: Infima and Topologies[END_REF]) Under the conditions (T1) and (T3 ), the following conditions are equivalent:

(T3) Every non-empty subset S ⊂ T has an infimum.

(T3 ) Given two elements τ , σ ∈ T , the set {τ, σ} has an infimum τ ∧ σ. Definition 6.3. A rooted nonmetric tree T is complete if every increasing sequence {τ i } i≥1 in T has a majorant, that is, an element τ ∞ , with τ i ≤ τ ∞ for every i.

Theorem 6.4. The valuation space V is a complete nonmetric tree rooted at νm .

Proof. (T3 ) It is clear that (V, ≤) is a partially ordered set with unique minimal element νm .

(T1) Fix ν in V, with ν > ν m . We will show that the set S = {μ ∈ V | ν m ≤ μ ≤ ν} is a totally ordered set isomorphic to an interval in R+ .

Choose local coordinates x and y such that 1 = ν(x) ≤ ν(y).

Let ν be the valuation of k(x, y) corresponding to ν and let {Q i } i∈I(ν) be a complete sequence of key polynomials for ν. The sequence β i (ν) d i (ν) is strictly increasing. If I(ν) has a maximal element , put I = 1, β (ν) d (ν) ⊂ R. Otherwise, put I = [1, ∞) ⊂ R. We will prove that S is isomorphic to I as an ordered set.

To each t ∈ I we will associate a valuation νt in S.

Let t ∈ I. If t = 1, put νt = νm . If I(ν) has a maximal element and t = β (ν) d (ν) , put νt = ν. Now suppose that 1 < t < β (ν) d (ν) . There exists a unique element u ∈ I(ν) such that β u-1 (ν) d u-1 (ν) < t ≤ βu(ν) du(ν) . Let ν t := [µ u-1 , Q u , td u ] and νt the corresponding valuation in V. That the resulting map is a bijection follows from Remark 5.7.

(T2) By Theorem 5.9, every totally ordered convex subset S of T has a majorant in T . With (T3 ) and (T1) this proves (T2). This also proves that T is complete.

(T3) is an immediate consequence of Theorem 5.8 and Lemma 6.2.

Remark 6.5. Let (R, m, k) and (R , m , k ) be two regular two-dimensional local rings such that the residue fields k and k have the same cardinality. Let ι : k ∼ = k be a bijection between the two fields (as sets, that is, ι need not be a homomorphism of fields). Using the results of this paper it can be shown that ι induces a homeomorphism of the respective valuative trees, associated to R and R . Thus, up to homeomorphism, a valuative tree associated to a regular local ring (R, ,k) depends only on the cardinality of the residue field k.


Frédéric Paletou

Christophe Peymirat

Éric Anterrieu

Torsten Böhm

An adaptive gaussian quadrature for the Voigt function

We evaluate an adaptive gaussian quadrature integration scheme that will be suitable for the numerical evaluation of generalized redistribution in frequency functions. The latter are indispensable ingredients for "full non-LTE" radiation transfer computations i.e., assuming potential deviations of the velocity distribution of massive particles from the usual Maxwell-Boltzmann distribution. A first validation is made with computations of the usual Voigt profile.

I. INTRODUCTION

Radiation transfer is, by essence, a difficult problem (e.g., Rutily & Chevallier 2006), as well as a question of very large relevance in astrophysics. It relies indeed on complex non-linear light-matter interactions (see e.g., Hubeny & Mihalas 2014, Rutten 2003).

At the very heart of the problem lays the issue of how photons may scatter on these moving massive particles constituting the atmosphere under study. The usual literature classify these processes as, either "complete" redistribution in frequency (CRD), or "partial" redistribution in frequency (PRD; see e.g., §10 of Hubeny & Mihalas 2014). The vast majority of astrophysical problems are solved, still, within the frame of CRD, for which further simplifications are the equality of emission and absorption profiles -the latter being also usually known a priori -, which also leads to the independence of the so-called source function vs. frequency.

Besides, and more generally, while non-equilibrium distributions of photons i.e., potential departures from the Planck law, have been routinely considered since the late 60's, a very limited number of studies tried to push further the description of the physical problem, by questioning to what extent the most often assumed Maxwell-Boltzmann velocity distribution of the massive particles onto which photons scatter may remain valid (see e.g., Oxenius & Simmonneau 1994, and references therein).

Non-maxwellian velocity distributions functions (hereafter vdf) have been studied (e.g., Scudder 1992 and further citations) or evidenced in natural plasma (see e.g., Jeffrey et al. 2017 for a recent study about solar flares). Such departures from Maxwell-Boltzmann vdf's have also been considered in the radiative modelling of spectral lines formed in neutral planetary exospheres (e.g., Chaufray & Leblanc 2013), where these authors introduced so-called κ vdf's into their photon scattering physical model.

However, such non-maxwellian vdf's are still known ab initio before solving the radiation transfer problem. The more general issue of computing self-consistent nonequilibrium distributions for both photons and massive particles -whose associated problem we coin "full non-LTE radiation transfer" -remains a quite open question in astrophysics, although a few studies have already been conducted in the past (see e.g., Borsenberger et al. 1986Borsenberger et al. , 1987)).

Hereafter, we provide a first numerical tool that will allow us to go further in this direction, enabling further computations of generalized redistribution functions. Moreover the numerical scheme we evaluated may also be of more general interest, for other topics of numerical (astro)physics.

II. REDISTRIBUTION IN FREQUENCY

As an illustrative but important example, we shall focus here on the case of coherent scattering in the atomic frame of reference, for a spectral line of central wavelength ν 0 . We shall also assume that only "natural" broadening is at play for the upper energy level of, typically, a resonance line with an infinitely sharp lower level.

Therefore, we shall consider an elementary frequency redistribution function r(ξ , ξ) such that:

r(ξ , ξ) = ϕ(ξ )δ(ξ -ξ) , (1)
where ξ and ξ are, respectively, the incoming and the outgoing frequencies of a photon, and δ is the usual Dirac distribution, together with:

ϕ(ξ ) = Γ π 1 (ξ -ν 0 ) 2 + Γ 2 . ( 2
)
The latter is a Lorentzian profile, with damping parameter Γ, resulting from the "natural width" of the upper atomic state of the transition at ν 0 .

If we assume that the angular redistribution associated with the scattering event is isotropic, such a case of radiation damping and coherence in the atom's frame refers to the standard case "II-A" in the nomenclature of Hummer (1962;see also Hubeny & Mihalas 2014).

Once the elementary scaterring process have been defined in the atomic frame of reference, we have to consider for a further practical implementation into a radiative transfer problem, the collective effects induced by the agitation of a pool of massive particles populating the atmosphere. This is precisely in this "jump" to the observer's frame of reference, because of Doppler shifts such as:

ν = ξ + ν 0 c n. v , ( 3
)
where ν is the observed frequency, n may be either the incoming or the outgoing direction of a photon, and v the velocity of the massive particle onto which the scattering takes place, that some assumption has to be made about the vdf of the massive atoms (or molecules) present in an atmosphere, under given physical conditions. Detailed derivations of R II-A can be found in the classical literature about redistribution functions, from Henyey (1940) 5 to Hummer (1962). Standard redistribution functions have been first derived assuming that the vdf of the atoms scattering light is a Maxwell-Boltzmann distribution. Then, but more generally, any macroscopic redistribution function in the observer's frame suitable for implementation into the numerical radiative transfer problem will result from the further integration along each velocity components u i (hereafter normalized to the most probable velocity v th. = 2kT /m) characterizing the movement of the scattering atoms and, therefore considering these changes of frequencies due to the associated Doppler shifts as expressed by Eq. ( 3). The latter phenomenon is usually refered to as Doppler, or thermal broadening.

III. THE NUMERICAL PROBLEM

We aim at generalizing computations of redistribution functions in order to be able to compute vdf's selfconsistently with the radiation field. Therefore we need a robust numerical approach to repeatedly perform numerical integrations like:

H 1 (x , x, γ) = +∞ -∞ f (u 1 )du 1 [( x+x 2 ) sec(γ/2) -u 1 ] 2 + [ a ∆ν D sec(γ/2)] 2 , (4)
where x and x are the usual incoming and outgoing reduced 15 frequencies in the observer's frame, ∆ν D the Doppler width defined as (ν 0 /c)v th. , and γ the diffusion angle between incoming and outgoing directions in the plane defined by u 1 and u 2 . For the Maxwell-Boltzmann case, we should indeed use:

f (u 1 ) = 1 √ π e -u 2 1 , (5)
but we shall need to consider f (u 1 ) to be non-analytic, and, at first, (slightly) departing from the maxwellian standard vdf. Indeed, physical conditions leading to small departures from a Gaussian vdf have already been identified and discussed by Oxenius (1986), and they would correspond to a non-LTE gas of moderate optical thickness. Note also that, for a preliminary study, we shall assume a self-consistent vdf solution of the problem that may still be decomposed as f 1 (u 1 )f 2 (u 2 )f 3 (u 3 ). However, before exploring potential departures from gaussianity, we need to adopt a robust enough numerical strategy in order to numerically evaluate integrals such as Eq. ( 4), a task which is notoriously difficult even with Maxwell-Boltzmann fdv's. It is very easy to verify that, for instance a standard Gauss-Hermite (GH) quadrature, even at high rank k, fails at computing properly a somewhat simpler expression like the Voigt 20 function given in Eq. ( 13). We display in Fig.

(1) the comparison between a GH integration and the new numerical scheme which is presented hereafter.

IV. ADAPTIVE GAUSSIAN QUADRATURE

We shall start following the scheme proposed by Liu & Pierce (1994), which is based on the classical Gauss-Hermite (GH) quadrature. The latter is indeed suitable for integrations of the kind:

I = +∞ -∞ f (y)e -y 2 dy . (6)
Then the GH quadrature is such that:

+∞ -∞ f (y)e -y 2 dy k i=1 w i f (y i ) (7) FIG.
1. The failure of a standard Gauss-Hermite quadrature of order k = 70 (green), as compared to the almost superimposed results from, respectively, the method using the Faddeeva complex function (dark) and our alternative double adaptive Gaussian quadrature scheme, for a normalized Voigt profile with a = 10 -2 .

where the nodes y i are the zeros of the k-th order Hermite polynomial, and w i the corresponding weights. Tabulated values of both nodes and weights can be found very easily, and they are also available for various programming language. We shall use numpy's (Oliphant 2006) function polynomial.hermite.hermgauss, and a GH of order k = 70 for all results presented hereafter.

The main drawback of such a standard quadrature is that function f shall be scanned at the very nodes y i irrespectively from the range where it may have its most significant variations.

However, Liu & Pierce (1994) proposed that, should a function g to be integrated, one may define:

h(y) = g(y) N (y; μ, σ) , ( 8
)
where N is the usual Gaussian function:

N (y; μ, σ) = 1 σ√ 2π e -1 2 ( y-μ σ ) 2 , ( 9
)
so that one can write:

+∞ -∞ g(y)dy = +∞ -∞ h(y)N (y; μ, σ)dy , (10)
and, finally: This adaptive Gaussian quadrature scheme (AGQ) allows to use the original nodes and weights of the GH quadrature, but somewhat zooms in these domains where function g has its most significant variations. The choice of μ and σ is of importance. Liu & Pierce (1994) suggested to adopt μ to be the mode of g, and σ = 1/ √ j, where:

+∞ -∞ g(y)dy k i=1 w i √ π h(μ + √ 2σy i ) . (11)
j = - ∂ 2 ∂y 2 log g(μ) . (12)
We shall come back on this choice in the following section, and show that a somewhat larger σ value is more suitable for the special case of the Voigt profile.

V. AGQ TESTS WITH THE VOIGT FUNCTION

Let us consider the normalized Voigt function hereafter defined as:

H(a, u) = 1 √ π a π +∞ -∞ e -y 2 dy (u -y) 2 + a 2 , ( 13
)
and which satisfies to:

+∞ -∞ H(a, u)du = 1 . ( 14
)
Note that several authors use H for the Voigt profile normalized to √ π, but U instead of our H normalized to unity though (see e.g., Hubeny & Mihalas 2014, their §8). We shall also use h(y; a, u) for the integrand of Eq. ( 13). For this numerical integration, three main regimes should be considered, depending on the values of u i.e., according to the respective amplitudes of the Gaussian and the Lorentzian components of the integrand. For the line core region such that |u| < 2, we use a slightly modified AGQ, for which we use a value of σ larger than the one suggested in the original article of Liu & Pierce (1994). We display in Fig. (2) the new quadrature nodes, marked with crosses, centered at the Lorentzian peak located at y ≈ 1.7, and using 3σ instead of the value suggested in the original prescription of Liu & Pierce (1994). The nodes of the standard GH quadrature (at the same order) are displayed as dots. They extend too far away, clearly "miss" the large amplitude Lorentzian peak and therefore the dominant contribution to the integral.

Second, we perform a double AGQ scheme for the near wing regions such that 2 < |u| < 4, and for which two discernable peaks of comparable amplitudes result from, respectively, the Lorentzian and the Gaussian components of the convolution (we shall hereafter refer to u 2 and u 4 for these two boundary values). In such a case, we use both the centering and integration range controls provided by the original AGQ for evaluating separately the contribution from each component of the integrand. For the Lorentzian component we therefore do as when |u| < 2, but we add to this part of the integral the contribution of the nearby Gaussian peak using another AGQ centered at 0, and of specific σG obviously adapted to the width of the known Gaussian component of the integrand (also, overlap with the nearby Lorentzian component should be avoided). The two distincts sets of nodes, based on the same original GH quadrature nodes, at same order, are displayed by crosses of different colors in Fig. (3).

Finally, for the far wing where |u| > u 4 , and when the Lorentzian peaks fade out, the usual Gauss-Hermite quadrature is satisfactory.

FIG. 4. Voigt profiles H(a, u) computed with our double AGQ scheme for, respectively, a = 0.001, 10 -4 , 10 -5 and 10 -6 (and decreasing wing values). Small discontinuities are still noticeable at the transitions values about 2 and 4. This should however not impair any standard scattering integral computation.

Results using our double AGQ quadrature scheme are displayed in Fig. ( 4), for different values of a ranging from 0.01 to 10 -4 , more likely regimes expected for our next computations. Maximum relative errors computations using the Faddeeva function method as a benchmark, and the scipy.special.wofz Python function, are at most of a few percents, as displayed in Fig. (5); note also that the latter was obtained using a u 4 value of 4.25, instead of the fiducial value of 4, indicating also in what direction a further fine-tuning could be worked out, if necessary, by considering u 2 and u 4 as slowly varying functions of a. Sometimes we can still notice small discontinuities at the changes of regimes, at u 2 and u 4 . We believe however that, should our procedure be used for Voigt profile computations and radiative modelling, such small and very local discontinuities will not impair further computations of these scattering integrals entering the equations of the statistical equilibrium.

This new numerical scheme is particularly efficient for small values of a, typically lower than 0.01, where other schemes may fail (see for instance the discussion in Schreier 2018 about the implementation of Voigt1D in the astropy package in Python, using the McLean et al. 1994 method). But first of all, it is certainely suitable for our next applications of such a numerical integration scheme, and for physical conditions leading to very sharp Lorentzian peaks. We could also test the sensitivity of our scheme to the order of the initial Gauss-Hermite quadrature. For instance, for a < 0.01 we could go down to orders 40 to 50 without any significant loss of accuracy.

For larger values of a, typically more than 0.1, we noticed that no intermediate scheme between the original Liu & Pierce (1994) at line core, and the Gauss-Hermite FIG. 5. Relative error between our computations with the double AGQ method, for a = 10 -4 , and a reference computation using the Faddeeva complex function.

in the wings appears necessary. However the transition value between the two regimes should be adapted to the value of a, in a 2 to 4 range.

VI. CONCLUSION

We have tested a suitable numerical strategy for our first step towards "fully non-LTE" radiative transfer calculations, and the computation of generalized frequency redistribution functions. We modified the original strat-egy of Liu & Pierce (1994), but also applied it to a nonunimodal distribution.

Our numerical scheme does not pretend to compete with these numerical methods implemented for the very accurate computation of the Voigt function (see e.g., Schreier 2018 and references therein) since our aim is elsewhere, i.e. to explore departures from Gaussian vdf's. It is however providing very good results as compared to reference computations, such as the one using the Faddeeva complex function. Relative errors down to a few percent are systematically reported in the near wing region, and we believe that further fine tuning could be achieved for reaching an even better accuracy. This is however not the scope of our study, which aims at computing generalized redistribution functions, after self-consistent computations of both massive particles and photons respective distributions under various physical conditions. In that respect, our main concern is well about a proper "capture" of the expected very sharp, and therefore very large amplitude Lorentzian peaks. And we believe that the principle of our numerical integration scheme should remain valid for the more easy to track contribution from the velocity distribution function, even for computed perturbations from a Gaussian shape.

As a final remark, we are also aware that computations with non-Gaussian functions convolved with a Lorentzian may also be doable, using a Fourier transform based method (e.g., Mendenhall 2007).

12 Oliphant, T.E., 2006, A guide to NumPy, Trelgol Publishing USA 13 Oxenius, J., 1986, Kinetic theory of particles and photons -Theoretical foundations of non-LTE plasma spectroscopy, Springer 14 Oxenius, J., Simonneau, E., 1994 F., 2018, JQSRT, 213, 13 19 Scudder, J.D., 1992, ApJ, 398, 299 20 The original article of W. Voigt (1912) published Sitz. Ber.

Bayer. Akad. München (in German) can be found on-line at http://publikationen.badw.de/de/003395768

FIG. 2 .

 2 FIG. 2. Example of distribution of nodes for an initial Gauss-Hermite quadrature of order k = 70 (dots), and for our adaptive Gaussian quadrature centered at the Lorentzian peak (crosses).

FIG. 3 .

 3 FIG. 3. Respective distributions of nodes, marked by crosses of different colors, from an initial Gauss-Hermite quadrature of order k = 70 when the Gaussian and Lorentzian peaks are of comparable amplitude, here for u around 3.

  , Annals of Physics, 234, 60 15 The usual reduced frequency x is the difference between frequency ν in the observer's frame and the central frequency ν0 of a spectral line, divided by the Doppler width ∆νD. 16 Rutily, B., Chevallier, L., 2006, EAS Pub. Series, 18, 1 17 Rutten, R.J., 2003, Radiative Transfer in Stellar Atmospheres, Lecture Notes Utrecht University (available online) 18 Schreier,

ACKNOWLEDGMENTS

Frédéric Paletou is grateful to his radiative transfer sensei, Dr. L.H. "Larry" Auer, with whom we started discussing about these issues long time ago.


Zhengyi Wang

Man Liang

Daniel Delahaye

Data-driven Conflict Detection Enhancement in Closest Point of Approach Problem

published or not. The documents may come   L'archive ouverte pluridisciplinaire


Jannick Trunkenwald
email: jannick.trunkenwald@yahoo.fr

Dominique Laval
email: dominique.laval@gmail.com

Algorithms as a discovery process in frequentist approach to prediction interval

Keywords: Algorithmic, Work Spaces, frequentist, probability, field

 are used to lead this study.

Introduction

In France, teaching of probability in upper school commences with a double approach: "combinatorial" and "frequentist". This makes it possible to connect the abstract notion of probability to "real" world, as it is perceived through our senses. The approach of frequency derives from binomial distribution with a deductive reasoning based upon random variables. The approach of probability is based on sampling fluctuation with empirical observations of frequencies. We choose to analyse the introduction to sampling fluctuation that empirically establishes the prediction interval principle, which is the only formalized rule taught at 10 th grade level. We make the choice to observe the work of teachers during a training course, by taking in account instrumental, semiotic and discursive dimensions. More particularly, this paper deals with existing interactions between fields such as probability and descriptive statistics, but also algorithmics during teacher's work.

Frequentist approach to sampling fluctuation

The 10th grade program in French school system leads to the discovery of sampling fluctuation with the following property: Let p be the probability of success, and let n be the number of repeated random experiments. Any frequency of success verifies with at least a 95% level of confidence. [START_REF] Nechache | La validation dans l'enseignement des probabilités au secondaire[END_REF] notices the absence in 10th grade of a probabilistic theoretical reference that would make it possible to approach this interval of fluctuation by deductive reasoning. The discovery process of this interval remains indeed at this stage, experimental and based on observation of samples which have the same size. Each frequency value corresponds to a sample obtained itself by repeating the considered random experiment. This is an empirical approach based on inductive reasoning. In addition, the "time cost" corresponding to the need of repeating the same experiment a large number of times entails a need for automation. And this idea is "facilitated" by using of computing which is based on a pseudo-random generator operation. Thus the "frequentist" approach requires consideration of three fields: probabilities, descriptive statistics and algorithmics.

A digital environment ("spreadsheet" or "programming software") makes possible to reduce the time spent on repeating the random experiment. Specific skills are needed to digital field (algorithmic, syntax of machine language, user interface…), and the lack of computing expertise could cause additional difficulties for students. It could also cause a meta-cognitive (or even cognitive) concern to teachers. Using digital field makes possible to automate an experimental protocol that requires the use of gestures, syntax, and specific modes of thinking. However, we can also question the specific contribution resulting from the use of a machine-implementable method, for a better comprehension of the frequentist approach (from a mathematical point of view). This question seems being even more important for teachers. Indeed, they are supposed to look closely at their practices. We can thus consider three main ways of exploiting a digital field to modelize the random experiment: -a spreadsheet; -the construction of "paper-and-pencil" algorithms and the actual implementation on the computer in order to test them; -the use of simulation algorithms or spreadsheet provided and already built. Each of these forms of use can be assimilated to an instrumentalization of computing or algorithmics artifacts to construct a "frequentist" approach in probabilistic or statistical fields.

We choose not to approach the spreadsheet case and to restrict the scope to algorithms. We believe that focusing on algorithms enables us to study the instrumental, semiotic and discursive dimensions which will be involved during mathematical and algorithmic work on sampling fluctuations. We thus seek to study the contribution of an algorithmic thought [START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF][START_REF] Modeste | Enseigner l'algorithme pour quoi? Quelles nouvelles questions pour les mathématiques? Quels apports pour l'apprentissage de la preuve?[END_REF] in the context of a mathematical work on probabilities and statistics. In particular, we think that writing the simulation algorithm corresponds to a higher stage of formalization for different involved statistical protocols, and that the role of "language" will take on particular importance in this sense.

Observations carried out in teacher training

Training on the simulation of sampling fluctuation at 10th grade level is conducted during an internship at the French High School in Algiers on May 2018. Five groups of three teachers (A, B, C, D, and E) have to solve the following problem: "What is the probability that the distance between two points randomly chosen along a line segment S, is more than half the length of the segment S?".

We build on existing work previously undertaken by [START_REF] Nechache | La validation dans l'enseignement des probabilités au secondaire[END_REF] and [START_REF] Trunkenwald | L'Espace de Travail Mathématique : Une respiration pour analyser la fluctuation d'une simulation d'échantillonnage[END_REF], to consider this task as being representative of institutional expectations for the "frequentist" approach. It is possible to explore sampling fluctuation with a real repetition of the random experiment (case of strings of twines cut with scissors), but considering this long process with randomization by a human being choice, our hypothesis is that teachers will use a numerical simulation operating with a pseudo-random generator (Alea()), which returns a random number between 0 and 1 simulating the position of a randomly selected point on the S-segment. The modelling work highlighting sampling fluctuation can find its formalized expression through a simulation algorithm. Indeed, the random experiment providing distance between two selected points can be simulated with |(Alea()-Alea())| as computing instruction which can be considered as a level 0 algorithm used for each simulation of the random experiment. Another level 1 algorithm can be constructed from the level 0 algorithm, by repeating the random experiment to obtain directly a simulated frequency of success (Figure 1). Running several times level 1 algorithm generates a list of frequencies, which can be represented as a cloud diagram (scatter plot). For this purpose, a third step can be envisaged in digital field: the level 2 algorithm (Figure 1) automating the layout of the cloud. Then level 2 algorithm is constructed from level 0 algorithm, by repeating the simulated frequency of success to draw directly the cloud.

The working groups do not have access to any pre-existing files to accomplish their task. But the algorithms they will design can be adapted for a later activity based on a roll of three dice. The groups manage more or less easily, with the help of the trainer when it is necessary, realizing a numerical model for the simulation of a frequency calculation. Only one group (the E) uses the spreadsheet, and only one group (the C) manages to finalize level 2 algorithm. Indeed, the transition from level 1 to level 2 corresponds to a tricky stage, especially the algorithmic writing of a statistical protocol that would consist in exploiting (on "paper") the results provided by level 1 algorithm. Our hypothesis is that it is an epistemological obstacle linked to the encapsulation of an algorithm in another (principle of a procedural subroutine), in order to automate the execution of the first one. Other difficulties at the interaction of statistical and algorithmic domains are identified during the training session. We present (Figure 2) an excerpt from the transcription of exchanges between the trainer and the group B, concerning the implementation in level 1 algorithm of a counter. In this excerpt the counter with its initialization, conditioned incrementation, and final exploitation appears as a complex construction. Its drafting is integrated into three levels of the algorithm script, with consideration of other instructions. Trainees try to locate a specific position which does not really exist for the counter... We observe a confusion between "success counter" and "simulation step counter".

Step counter is a "natural" process in statistics that becomes a difficulty in algorithmics. Finally, a similar difficulty appears in a confusion between the instructions "result value" provided by the counter, and "incrementation" of intermediate values used for its calculation. We can also observe a difficulty between probability and statistics fields: S2 speaks of "favorable case" instead of "success achieved".

In addition, transcripts of the session show difficulties related to the numerical modelling of the random experiment. Some difficulties appear in other groups, such as reluctance to use a pseudorandom generator, reference to the geometry field with consideration of lengths ratio as a probability, and lack of definition for abscissa. All these observations show us the importance of interactions between various fields, as probability and statistics, but also with algorithmics, when introducing the frequentist approach of the prediction interval. We believe that an analysis of the mathematical and algorithmic work in these various fields with their interactions, can help us to refine our understanding of some difficulties encountered by trainees.

The choice of theoretical framework and research question

Nilsson, Schindler, and Bakker (2017) presented a literature review of theoretical work apparent in Statistics Education Research (SER) over the past 11 years, encouraging educators and researchers to be explicit about their background theories and orienting: "in the reviewed articles there was no deeper theorization of computer assisted instruction in statistics. (…) In the 35 articles we found no theoretical attempts on a more specific level (…) such as guiding principles for designing tasks and sequencing tasks in a digital learning environment or frameworks for explaining and understanding the relationship between digital and analogue learning environments."

Activities that involve a mathematical task associated with multiple domains can be analysed by considering that entities involved in the task appear under different semiotic, instrumental, and discursive representations. Some researchers have developed frameworks to conduct studies of these activities according to the type of studied representations. [START_REF] Duval | Registres de représentation sémiotique et fonctionnement cognitif de la pensée[END_REF] named "registers" the representations organized in semiotic systems. Processes of handling and conversions are located inside and between these registers, and this description is also supplemented by the idea of "instruments" in the mathematical activity of students. Rabardel theorical framework (1995) focused on this "instrumental approach", and described the use of digital technologies to teach and learn mathematics in different contexts. Such a framework consisting of "objects" from mathematical fields with relationships between them, and different expressions or associated mental images, had already been addressed earlier by [START_REF] Douady | Jeux de cadres et dialectique outil-objet[END_REF]. However, some researchers have emphasized the inseparable development of instrument-related knowledge and mathematical knowledge, all in an instrumental genesis. An implementation of these issues for analysing articulation between the algorithmic and mathematical fields is presented in a didactic engineering of [START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF] based on the Work Spaces framework. And we wish to see taken into account the induced relations by instrumental and mathematical signs. Then we hypothesise that coordinating the activity in several fields could provide answers in this sense.

Indeed, in algorithmics the activity is located into an instrument for solving the mathematical task, with a specific system of signs for computer science. On the other hand, in mathematics the activity consists on solving the task from a mathematical point of view and using signs making it possible to understand and justify. Next, we have to choose an appropriate theorical framework that can give meaning to the learner's work during an activity involving several fields with their interactions, considering the semiotic, instrumental, and discursive dimensions specific to each field. We assume that articulations between Spaces of Specific Mathematical Work (MWSs) (Kuzniak & Richard, 2014) and Spaces of Algorithmic Work (AWS) [START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF], will allow to study the different geneses of the representamen and processes, from the point of view of the learners' MWSs and AWS, but also to approach the interactions between the probability/statistics and algorithmics. We briefly present this theoretical framework in the following section. Then the research question of this article is how this framework can analyse a learner's work involving computer programming in a frequentist approach to the prediction interval. French programs also emphasize a potential contribution of algorithmic work to the understanding of mathematical concepts, which raises the question of interactions between domains in learners' activity [START_REF] Lagrange | Connected working spaces: The case of computer programming in mathematics education[END_REF][START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF].

The working spaces MWSs AWS -First analyses

The methodological tools MWSs [START_REF] Kuzniak | Mathematical Working Spaces in schooling: an introduction[END_REF] and AWSs [START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF] help us to decompose intellectual perceptions at stake, during activity in mathematics and algorithmics fields. Three instrumental, semiotic, and discursive dimensions are considered, each generating a dynamic relationship between an epistemological plane and a cognitive plane (Figure 3). Technological (artifact), semiotic (representamen), and theoretical (referential) tools of epistemological plane can then be exploited using appropriate schemes. In this case, we respectively refer to instrumental, semiotic, and discursive genesis, which respectively produce constructs, visualizations, and proofs in the cognitive plane. The activation of two geneses can lead to a circulation between dimensions that carry them, which could sometimes be assimilated to the idea of modelling [START_REF] Laval | L'algorithmique au lycée entre développement de savoirs spécifiques et usage dans différents domaines mathématiques[END_REF]. We call "projection" of MWS s (or AWS) the restriction to a specific field of what we analyse in the Workspace. We write projections of the MWS on probability and statistic fields, as respectively MWS Prob and MWS Stat . In order to avoid visual overload, we present diagrams of these projections with a view from above. Points and bolded lines represent the different discursive (D), instrumental (I), and semiotic (S) geneses, as well as circulations in planes located between these geneses' axes.

The main interaction between MWS and AWS is related to the use of a pseudo-random generator. This artifact is first instrumentalized within AWS to build a simulation of the random experiment. The link between this construction and the associated formulation causes an I-D circulation and leads to a discursive genesis enriching the AWS referential. With reference to Laval (2015), algorithmic design work presents a triple instrumental, semiotic, and discursive dimension within AWS. We link this discursive dimension with the idea of "language". Indeed, level 0, 1, and 2 algorithms are formalized writes of experimental protocols. Algorithmic expressions in "natural" language, with their three encapsulated structures, then constitute an explicit formulation of the procedure to be followed in the statistical field to carry out a "frequentist approach" to the prediction interval. This explanation may be associated with the idea of proof. This consideration brings us back to discursive genesis which, according to Laval (2015), is confirmed when the program is able to run (at the first level of paradigm corresponding to an intuitive view of the algorithm).

It should be noted that this AWS discursive dimension tends to fade from "semiotico-instrumental" plan, when working with a spreadsheet tool, whose syntactic aspects are more related to nature of artifacts (even if discursive dimension is still activated from cognitive plane to mobilize tools of AWS referential). A complex construction with a spreadsheet can also reduce "intellectual visualization" of a phenomenon and thus semiotic dimension, to be limited to instrumental dimension. Finally, AWS loses all activity when the algorithm implemented in a digital environment is provided to learners to be executed and used without any modification work expected in its own structure. The algorithm is then reduced to an artifact ready to be instrumentalised in MWS projection on another field.

Simulation programs and dynamic tables are very active in the instrumental dimension of MWSs outside AWS. The "simulation programs" are instrumentalized as tools to build a statistical observation, within MWSstat (and within MWSprob if this construction shows properties resulting from chance).

Case of algorithms written in "pseudo-code" of levels 0, 1, and 2

The level 2 algorithm aims to resume the experimental protocol of drawing a cloud diagram. We expect that trainees automate the cloud diagram of frequencies by improving level 1 algorithm which gives the simulation of a frequency. Then implementation of level 2 algorithm makes it possible to observe different clouds, and to conjecture the property of prediction interval. Figures 4, 5 and 6 present the exploded diagram (top view of MWSs and AWS) corresponding to designs and executions of each algorithm level. More specifically as regards interactions between probability and statistics, a more detailed description is presented in [START_REF] Trunkenwald | L'Espace de Travail Mathématique : Une respiration pour analyser la fluctuation d'une simulation d'échantillonnage[END_REF] for the chosen task. At level 0, the algorithm is designed in an instrumental genesis of the random generator artefact in AWS, simulating a distance between two randomly selected points along the segment. This numerical modelization generates a discursive validation of the random experiment simulation, through a discursive genesis in AWS. This level 0 algorithm is then used as a technological tool in MWS Stat through an instrumental genesis in MWS Stat (activating the discursive dimension by mobilizing frequency, and the semiotic dimension by mobilizing a type of data management). An experimental protocol for calculating a frequency is then constructed by running the level 0 algorithm many times (Figure 4). At level 1 (Figure 5), the frequency simulation protocol is totally automated. This algorithmic work generates a complete circulation in AWS. And the level 1 algorithm (new frequency simulation algorithm) is then used as a technological tool in MWS stat through an instrumental genesis (activating the discursive dimension by mobilizing cartesian coordinate system). This protocol builds a frequency cloud diagram protocol by running the level 1 algorithm many times. This work generates a semiotic genesis in MWS Stat by visualizing the sample fluctuations. Supported by this new semiotic link between frequency and probability, this semiotic genesis in MWS Stat leads to a semiotic genesis in MWS prob ("intellectual visualization" of fluctuations of chance). Supported by this new discursive link between frequency and probability, discursive genesis in MWS Stat leads to a discursive genesis in MWS prob (understanding of the prediction interval formula meaning, in light of the frequentist approach of probability).

Conclusion

The three described phases allow us a construction by successive encapsulations of the simulation algorithm. These algorithmic steps also resonate with the experimental statistical protocol phases. And this semantic congruence finds its expression in a certain aspect of algorithmic work: the organization of in-blocks "subroutines" procedures.

The MWS S tool highlights interactions between the three considered domains: the level 0 algorithm designed in an interaction between the instrumental dimension of MWS and AWS. Then level 0 algorithm is executed in order to construct a new experimental protocol. The level 0 algorithm is then considered as a technological tool through an instrumental genesis in MWS Stat . Then level 0 algorithm, taken as theoretical tool in a discursive genesis of AWS, finalizes a new algorithmic object aiming to automate this new experimental protocol: the level 1 algorithm. Two new identical cycles of interactions between MWS Stat and AWS can successively generate the level 2 algorithm, which could establish a conjecture to frame the fluctuations. Then, this conjecture makes it possible to visualize in a semiotic genesis of MWS Prob the prediction interval, in order to activate the discursive dimension of MWS Prob to enrich the repository of the prediction interval property.

In addition, to highlight this dialectic of evolving interaction cycles between the three involved domains, our analysis can be used to design a prototype for teacher training session, or an activity for students, that avoid confronting learners with the simultaneous difficulties of different domains. Such a prototype can also be used as a remediation tool.

Figure 1 :

 1 Figure 1: Level 1 and level 2 algorithms written in pseudo-code.

Figure 2 :

 2 Figure 2: Excerpt of a 8'14''record with group B

Figure 3 :

 3 Figure 3: Case of Algorithmic Space Work (Laval, 2018)

Figure 4 :

 4 Figure 4: AWS, MWS Prob , and MWS Stat for level 0 algorithm (conception and exploitation).

Figure 5 :

 5 Figure 5: AWS, MWS Prob , and MWS Stat for level 1 algorithm (conception and exploitation).

Figure 6 :

 6 Figure 6: AWS, MWS Prob , and MWS Stat for level 2 algorithm (conception and exploitation) At level 2 (Figures 6 and 7), the cloud drawing protocol is totally automated. This algorithmic work generates again a complete circulation in AWS. And this level 2 algorithm (new cloud drawing algorithm) is then used as a technological tool in MWS stat through an instrumental genesis. This construction of a new protocol leads a complete circulation in MWS Stat to build a conjecture of the prediction interval formula by inductive reasoning. This work generates a discursive genesis in MWS Stat with this new understanding of the interval meaning, in light of sample fluctuations.

Figure 7 :

 7 Figure 7: Level 2 algorithm implemented on Algobox