arXiv:1611.05679v1 [] 17 Nov 2016

KEY POLYNOMIALS AND PSEUDO-CONVERGENT
SEQUENCES
JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY
Abstract. In this paper we introduce a new concept of key polynomials for
a given valuation ν on K[x]. We prove that such polynomials have many
of the expected properties of key polynomials as those defined by MacLane
and Vaquié, for instance, that they are irreducible and that the truncation
of ν associated to each key polynomial is a valuation. Moreover, we prove
that every valuation ν on K[x] admits a sequence of key polynomials that
completely determines ν (in the sense which we make precise in the paper).
We also establish the relation between these key polynomials and pseudoconvergent sequences defined by Kaplansky.

1. Introduction
Given a valuation ν of a field K, it is important to understand what are the
possible extensions of ν to K[x]. Many different theories have been developed in
order to understand such extensions. For instance, in [3], MacLane develops the
theory of key polynomials. He proves that given a discrete valuation ν of K, every
extention of ν to K[x] is uniquely determined by a sequence (with order type at
most ω) of key polynomials. Recently, M. Vaquié developed a more general theory
of key polynomials (see [9]), which extends the results of MacLane for a general
valued field (that is, the given valuation of K is no longer assumed to be discrete).
At the same time, F.H. Herrera Govantes, W. Mahboub, M.A. Olalla Acosta and
M. Spivakovsky developed another definition of key polynomials (see [5]). This
definition is an adaptation of the concept of generating sequences introduced by
Spivakovsky in [7]. A comparison between this two definitions of key polynomials
is presented in [4].
Roughly speaking, for a given valuation µ of K[x], a MacLane – Vaquié key
polynomial φ ∈ K[x] for µ is a polynomial that allows us to obtain a new valuation
µ1 of K[x] with µ1 (φ) = γ1 > µ(φ) and µ(p) = µ1 (p) for every p ∈ K[x] with
deg(p) < deg(φ) (in this case we denote µ1 by [µ; µ1 (φ) = γ1 ]). Then, for any valuation ν of K[x] one tries to obtain a sequence of valuations µ0 , µ1 , . . . , µn , . . . with
µ0 a monomial valuation and µi+1 = [µi ; µi+1 (φi+1 ) = γi+1 ] for a key polynomial
φi+1 for µi , such that
(1)

ν = lim µi

2010 Mathematics Subject Classification. Primary 13A18.
Key words and phrases. Key polynomials, Pseudo-convergent sequences, Valuations.
1

2

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

(in the sense that will be defined precisely below). This process does not work
in general, that is, the equality (1) may not hold even after one constructs an
infinite sequence {µi }. This leads one to introduce the concept of “limit key polynomial”. It is known that valuations which admit limit key polynomials are more
difficult to handle. For instance, it was proved by J.-C. San Saturnino (see Theorem 6.5 of [6]), that if a valuation ν is centered on a noetherian local domain and ν
does not admit limit key polynomials (on any sub-extension R′ ⊆ R′ [x] ⊆ R with
dim R′ = dim R − 1), then it has the local uniformization property (where we
assume, inductively, that local uniformization holds for R′ ).
In this paper, we introduce a new concept of key polynomials. Let K be a field
and ν a valuation on K[x]. Let Γ denote the value group of K and Γ′ the value
∂b
group of K[x]. For a positive integer b, let ∂b := b!1 ∂x
b (this differential operator
of order b is sometiems called the b-th formal derivative). For a polynomial
f ∈ K[x] let


ν(f ) − ν(∂b f )
.
ǫ(f ) = max
b∈N
b
A monic polynomial Q ∈ K[x] is said to be a key polynomial (of level ǫ(Q)) if
for every f ∈ K[x] if ǫ(f ) ≥ ǫ(Q), then deg(f ) ≥ deg(Q).
This new definition offers many advantages. For instance, it gives a criterion to
determine, for a given valuation ν of K[x], whether any given polynomial is a key
polynomial for ν. This has a different meaning than in the approach of MacLaneVaquié. In their approach, a key polynomial allows us to “extend the given valuation” and here a key polynomial allows us to “truncate the given valuation”.
For instance, our definition of key polynomials treats the limit key polynomials on
the same footing as the non-limit ones. Moreover, we present a characterization
of key polynomial (Theorem 2.12) which allows us to determine whether a given
key polynomial is a limit key polynomial. A more precise comparison between the
concept of key polynomial introduced here and that of MacLane – Vaquié will be
explored in a forthcoming paper by Decoup, Mahboub and Spivakovsky.
Given two polynomials f, q ∈ K[x] with q monic, we call the q-standard expansion of f the expression
f (x) = f0 (x) + f1 (x)q(x) + . . . + fn (x)q n (x)
where for each i, 0 ≤ i ≤ n, fi = 0 or deg(fi ) < deg(q). For a polynomial
q(x) ∈ K[x], the q-truncation of ν is defined as
νq (f ) := min {ν(fi q i )}
0≤i≤n

n

where f = f0 + f1 q + . . . + fn q is the q-standard expansion of f . In Section 2, we
present an example that shows that νq does need to be a valuation. We also prove
(Theorem 2.6) that if Q is a key polynomial, then νQ is a valuation. A set Λ of key
polynomials is said to be a complete set of key polynomials for ν if for every
f ∈ K[x], there exists Q ∈ Λ such that νQ (f ) = ν(f ). One of the main results of
this paper is the following:

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

3

Theorem 1.1. Every valuation ν on K[x] admits a complete set of key polynomials.
Another way of describing extensions of valuations from K to K[x] is the theory
of pseudo-convergent sequences developed by Kaplansky in [1]. He uses this theory
to determine whether a maximal immediate extension of the valued field (K, ν)
is unique (up to isomorphism). For a valued field (K, ν), a pseudo-convergent
sequence is a well-ordered subset {aρ }ρ<λ of K, without last element, such that
ν(aσ − aρ ) < ν(aτ − aσ ) for all ρ < σ < τ < λ.
For a given pseudo-convergent sequence {aρ }ρ<λ it is easy to show that either
ν(aρ ) < ν(aσ ) for all ρ < σ < λ or there is ρ < λ such that ν(aσ ) = ν(aρ ) for every
ρ < σ < λ. If we set γρ := ν(aρ+1 − aρ ), then ν(aσ − aρ ) = γρ for every ρ < σ < λ.
Hence, the sequence {γρ }ρ<λ is an increasing subset of Γ. An element a ∈ K is
said to be a limit of the pseudo-convergent sequence {aρ }ρ<λ if ν(a − aρ ) = γρ for
every ρ < λ.
One can prove that for every polynomial f (x) ∈ K[x], there exists ρf < λ such
that either
(2)

ν(f (aσ )) = ν(f (aρf )) for every ρf ≤ σ < λ,

or
(3)

ν(f (aσ )) > ν(f (aρ )) for every ρf ≤ ρ < σ < λ.

If case (2) happens, we say that the value of f is fixed by {aρ }ρ<λ (or that {aρ }ρ<λ
fixes the value of f ). A pseudo-convergent sequence {aρ }ρ<λ is said to be of transcendental type if for every polynomial f (x) ∈ K[x] the condition (2) holds.
Otherwise, {aρ }ρ<λ is said to be of algebraic type, i.e., if there exists at least one
polynomial for which condition (3) holds.
The concept of key polynomials appears in the approach to local uniformization
by Spivakovsky. On the other hand, the concept of pseudo-convergent sequence
plays an important role in the work of Knaf and Kuhlmann (see [2]) on the local
uniformization problem. In this paper, we present a comparison between the concepts of key polynomials and pseudo-convergent sequences. More specifically, we
prove the following:
Theorem 1.2. Let ν be a valuation on K[x] and let {aρ }ρ<λ ⊂ K be a pseudoconvergent sequence, without a limit in K, for which x is a limit. If {aρ }ρ<λ is of
transcendental type, then Λ := {x − aρ | ρ < λ} is a complete set of key polynomials
for ν. On the other hand, if {aρ }ρ<λ is of algebraic type, then every polynomial
q(x) of minimal degree among the polynomials not fixed by {aρ }ρ<λ is a limit key
polynomial for ν.
2. Key polynomials
We will assume throughout this paper that K is a field, ν a valuation of K[x],
non-trivial on K with ν(x) ≥ 0. We begin by making some remarks.

4

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

Remark 2.1.
(i): Every linear polynomial x − a is a key polynomial (of level
ǫ(x − a) = ν(x − a)).
(ii): Take a polynomial f (x) ∈ K[x] of degree greater than one and assume
that there exists a ∈ K such that ν(∂b f (a)) = ν(∂b f (x)) for every b ∈ N
(note that such an a always exists if the assumptions of Theorem 1.2 hold
and the pseudo-convergent sequence is transcendental or is algebraic and
deg(f ) ≤ deg(q)). Write
f (x) = f (a) +

n
X

∂i f (a)(x − a)i

i=1

and take h ∈ {1, . . . , n} such that

ν(∂h f (x)) + hν(x − a) = min {ν(∂i f (x)) + iν(x − a)}.
1≤i≤n

If ν(f (a)) < ν(∂h f (x)) + hν(x − a), then ν(f (x)) = ν(f (a)) and hence
ν(f (x)) − ν(∂i f (x))
< ν(x − a)
i
for every i, 1 ≤ i ≤ n. Consequently, ǫ(f ) < ν(x − a) = ǫ(x − a) and hence
f is not a key polynomial. On the other hand, if
ν(∂h f (x)) + hν(x − a) ≤ ν(f (a)),
then
ν(f (x)) ≥ ν(∂h f (x)) + hν(x − a)

(4)

and if the equality holds in (4), then
ν(f (x)) − ν(∂h f (x))
= ν(x − a) = ǫ(x − a)
h
and hence f is not a key polynomial. In other words, the only situation
when f may be a key polynomial is when
ǫ(f ) =

f (x) > min {f (a), ν(∂i f (x)) + iν(x − a)}.
1≤i≤n

Remark 2.2. We observe that if Q is a key polynomial of level ǫ := ǫ(Q), then for
every polynomial f ∈ K[x] with deg(f ) < deg(Q) and every b ∈ N we have
ν(∂b (f )) > ν(f ) − bǫ.

(5)

Indeed, from the definition of key polynomial we have that ǫ > ǫ(f ). Hence, for
every b ∈ N we have
ν(f ) − ν(∂b (f ))
≤ ǫ(f ) < ǫ
b
and this implies (5).
Let
I(f ) =
and b(f ) = min I(f ).



ν(f ) − ν(∂b f )
b∈N
= ǫ(f )
b



KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

5

Lemma 2.3. Let Q be a key polynomial and take f, g ∈ K[x] such that
deg(f ) < deg(Q)
and
deg(g) < deg(Q).
Then for ǫ := ǫ(Q) and any b ∈ N we have the following:
(i): ν(∂b (f g)) > ν(f g) − bǫ
(ii): If νQ (f Q+g) < ν(f Q+g) and b ∈ I(Q), then ν(∂b (f Q+g)) = ν(f Q)−bǫ;
(iii): If h1 , . . . , hs are polynomials such that deg(hi ) < deg(Q) for every i =
s
Y
hi = qQ + r with deg(r) < deg(Q), then
1, . . . , s and
i=1

ν(r) = ν

s
Y

hi

i=1

!

< ν(qQ).

Proof. (i) Since deg(f ) < deg(Q) and deg(g) < deg(Q), for each j ∈ N, we have
ν(∂j f ) > ν(f ) − jǫ and ν(∂j g) > ν(g) − jǫ.
This, and the fact that
∂b (f g) =

b
X

∂j f ∂b−j g,

j=0

imply that

ν(∂b (f g)) ≥ min {ν(∂j f ) + ν(∂b−j g)} > ν(f g) − bǫ.
0≤j≤b

(ii) If νQ (f Q + g) < ν(f Q + g), then ν(f Q) = ν(g). Hence,
ν(∂b g) > ν(g) − bǫ = ν(f Q) − bǫ.
Moreover, for every j ∈ N, we have
ν(∂j f ∂b−j Q) = ν(∂j f ) + ν(∂b−j Q) > ν(f ) − jǫ + ν(Q) − (b − j)ǫ = ν(f Q) − bǫ.
Therefore,


ν(∂b (f Q + g)) = ν f ∂b Q +

b
X
j=1



∂j f ∂b−j Q + ∂b g  = ν(f Q) − bǫ.

(iii) We proceed by induction on s. If s = 1, then h1 = qQ + r with
deg(h1 ) < deg(Q),

which implies that h1 = r and q = 0. Our result follows immediately.
Next, consider the case s = 2. Take f, g ∈ K[x] such that deg(f ) < deg(Q),
deg(g) < deg(Q) and write f g = qQ + r with deg(r) < deg(Q). Then
deg(q) < deg(Q)

6

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

and for b ∈ I(Q) we have


ν (∂b (qQ)) = ν 

This and part (i) imply that
ν(qQ) − bǫ

b
X
j=0



∂j q∂b−j Q = ν(qQ) − bǫ.

= ν (∂b (qQ)) = ν(∂b (f g) − ∂b (r))
≥ min{ν (∂b (f g)) , ν (∂b (r))}
> min{ν(f g), ν(r)} − bǫ.

and consequently
(6)

ν(r) = ν(f g) < ν(qQ).

Assume now that s > 2 and define h :=

s−1
Y

hi . Write h = q1 Q + r1 with

i=1

deg(r1 ) < deg(Q). Then by the induction hypothesis we have
ν(r1 ) = ν(h) < ν(q1 Q)
and hence
ν

s
Y

i=1

hi

!

= ν(r1 hs ) < ν(q1 hs Q).

Write r1 hs = q2 Q + r2 . Then, by equation (6) we have
ν(r2 ) = ν(r1 hs ) < ν(q2 Q).
If

s
Y

hi = qQ + r with deg(r) < deg(Q), then

i=1

qQ + r =

s
Y

hi = hhs = (q1 Q + r1 )hs = q1 hs Q + r1 hs = q1 hs Q + q2 Q + r2

i=1

and hence q = q1 hs + q2 and r = r2 . Therefore,
ν(qQ) ≥ min{ν(q1 hs Q), ν(q2 Q)} > ν(r1 hs ) = ν(r) = ν

s
Y

i=1

This is what we wanted to prove.

hi

!

.


We denote by p the exponent characteristic of K, that is, p = 1 if char(K) = 0
and p = char(K) if char(K) > 0.
Proposition 2.4. Let Q ∈ K[x] be a key polynomial and set ǫ := ǫ(Q). Then the
following hold:
(i): Every element in I(Q) is a power of p;
(ii): Q is irreducible.

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

7

Proof. (i) Take b ∈ I(Q) and assume, aiming for contradiction, that b is not a

power of p. Write b = pt r where r > 1 is prime to p. Then, by Lemma 6 of [1], pbt


is prime to p and hence ν pbt = 0. Since pbt ∂b = ∂pt ◦ ∂b′ for b′ = b − pt , we have
ν(∂b′ Q) − ν(∂b Q) = ν(∂b′ Q) − ν(∂pt (∂b′ Q)) ≤ pt ǫ(∂b′ (Q)) < pt ǫ

because deg(∂b′ Q) < deg(Q) and Q is a key polynomial. Hence,
bǫ = ν(Q) − ν(∂b Q) = ν(Q) − ν(∂b′ Q) + ν(∂b′ Q) − ν(∂b Q) < b′ ǫ + pt ǫ = bǫ,
which gives the desired contradiction.
(ii) If Q = gh for non-constant polynomials g, h ∈ K[x], then by Lemma 2.3 (i),
we would have for b ∈ I(Q) that
ν(∂b Q) > ν(Q) − bǫ,
which is a contradiction to the definition of b and ǫ.



We present an example to show that νq does not need to be a valuation for a
general polynomial q(x) ∈ K[x].
Example 2.5. Consider a valuation ν in K[x] such that ν(x) = ν(a) = 1 for some
a ∈ K. Take q(x) = x2 + 1 (which can be irreducible, for instance, if K = R or
K = Fp and −1 is not a quadratic residue mod p). Since x2 −a2 = (x2 +1)−(a2 +1)
we have
νq (x2 − a2 ) = min{ν(x2 + 1), ν(a2 + 1)} = 0.
On the other hand, νq (x + a) = ν(x + a) ≥ min{ν(a), ν(x)} = 1 (and the same
holds for νq (x − a)). Hence
νq (x2 − a2 ) = 0 < 1 + 1 ≤ νq (x − a) + νq (x + a)
which shows that νq is not a valuation.
If f = f0 + f1 q + . . . + fn q n is the q-standard decomposition of f we set
Sq (f ) := {i ∈ {0, . . . , n} | ν(fi q i ) = νq (f )} and δq (f ) = max Sq (f ).
Proposition 2.6. If Q is a key polynomial, then νQ is a valuation of K[x].
Proof. One can easily see that νQ (f +g) ≥ min{νQ (f ), νQ (g)} for every f, g ∈ K[x].
It remains to prove that νQ (f g) = νQ (f )+νQ (g) for every f, g ∈ K[x]. Assume first
that deg(f ) < deg(Q) and deg(g) < deg(Q) and let f g = aQ + c be the Q-standard
expansion of f g. By Lemma 2.3 (iii) we have
ν(f g) = ν(c) < ν(aQ)
and hence
νQ (f g) = min{ν(aQ), ν(c)} = ν(c) = ν(f g) = ν(f ) + ν(g) = νQ (f ) + νQ (g).
Now assume that f, g ∈ K[x] are any polynomials and consider the Q-expansions
f = f0 + . . . + fn Qn and g = g0 + . . . + gm Qm

8

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

of f and g. Then, using the first part of the proof, we obtain
νQ (f g) ≥ min{νQ (fi gj Qi+j )} = min{νQ (fi Qi ) + νQ (gj Qj )} = νQ (f ) + νQ (g).
i,j

i,j

For each i ∈ {0, . . . , n} and j ∈ {0, . . . , m}, let fi gj = aij Q + cij be the Q-standard
expansion of fi gj . Then, by Lemma 2.3 (iii), we have
ν(fi Qi ) + ν(gj Qj ) = ν(fi gj ) + ν(Qi+j ) = ν(cij ) + ν(Qi+j ) = ν(cij Qi+j ).
Let
i0 = min{i | νQ (f ) = ν(fi Qi )} and j0 = min{j | νQ (g) = ν(gj Qj )},
and set k0 := i0 + j0 . Then for every i < i0 or j < j0 we have

(7)
min ν(aij Qi+j+1 ), ν(cij Qi+j ) = ν(fi Qi ) + ν(gj Qj ) > ν(ci0 j0 Qk0 ).
Let f g = a0 + a1 Q + . . . + ar Qr be the Q-standard expansion of f g. Then
X
X
cij .
aij +
ak0 =
i+j=k0

i+j+1=k0

This and equation (7) give us that
ν(ak0 Qk0 ) = ν(ci0 j0 Qk0 ) = ν(fi0 Qi0 ) + ν(gj0 Qj0 ) = νQ (f ) + νQ (g).
Therefore,
νQ (f g) = min {ν(ak Qk )} ≤ νQ (f ) + νQ (g),
0≤k≤r

which completes the proof.

Proposition 2.7. Let Q ∈ K[x] be a key polynomial and set ǫ := ǫ(Q). For any
f ∈ K[x] the following hold:
(i): For any b ∈ N we have
(8)

νQ (f ) − νQ (∂b f )
≤ ǫ;
b
(ii): If SQ (f ) 6= {0}, then the equality in (8) holds for some b ∈ N;
(iii): If for some b ∈ N, the equality in (8) holds and νQ (∂b f ) = ν(∂b f ), then
ǫ(f ) ≥ ǫ. If in addition, ν(f ) > νQ (f ), then ǫ(f ) > ǫ.

Fix a key polynomial Q and h ∈ K[x] with deg(h) < deg(Q). Then, for every
b ∈ N the Leibnitz rule for derivation gives us that
X
(9)
∂b (hQn ) =
Tb (b0 , . . . , br )
b0 +...+br =b

where
Tb (b0 , . . . , br ) := ∂b0 h

r
Y

i=1

!

∂bi Q Qn−r .

In order to prove Proposition 2.7, we will need the following result:

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

9

Lemma 2.8. Let Q be a key polynomial, h ∈ K[x] with deg(h) < deg(Q) and set
ǫ := ǫ(Q). For any b ∈ N we have
νQ (Tb (b0 , . . . , br )) ≥ ν(hQn ) − bǫ.
Moreover, if either b0 > 0 or bi ∈
/ I(Q) for some i = 1, . . . , r, then
νQ (Tb (b0 , . . . , br )) > ν(hQn ) − bǫ.
Proof. Since deg(h) < deg(Q) and Q is a key polynomial we have ǫ(h) < ǫ. Hence,
if b0 > 0 we have
ν(∂b0 h) ≥ ν(h) − b0 ǫ(h) > ν(h) − b0 ǫ.
On the other hand, for every i = 1, . . . , r, by definition of ǫ we have
ν(∂bi Q) ≥ ν(Q) − bi ǫ,
and if bi ∈
/ I(Q) we have
ν(∂bi Q) > ν(Q) − bi ǫ.
Since νQ (∂b0 h) = ν(∂b0 h) and νQ (∂bi Q) = ν(∂bi Q), we have
!
!
r
Y
n−r
∂bi Q Q
νQ (Tb (b0 , . . . , br )) = νQ ∂b0 h
=
≥

νQ (∂b0 h) +

i=1
r
X

νQ (∂bi Q) + (n − r)νQ (Q)

i=1
r
X

ν(h) − b0 ǫ +

(ν(Q) − bi ǫ) + (n − r)ν(Q)

i=1

≥

ν(hQn ) − bǫ.

Moreover, if b0 > 0 or bi ∈
/ I(Q) for some i = 1, . . . , r, then the inequality above is
strict.

Corollary 2.9. For every b ∈ N we have νQ (∂b (aQn )) ≥ ν(aQn ) − bǫ.
Proof of Proposition 2.7. (i) Take any f ∈ K[x] and consider its Q-standard expansion f = f0 + f1 Q + . . . + fn Qn . For each i = 0, . . . , n, Corollary 2.9 gives us
that

νQ ∂b (fi Qi ) ≥ ν(fi Qi ) − bǫ.
Hence,

νQ (∂b (f )) ≥ min {νQ (fi Qi )} ≥ min {ν(fi Qi ) − bǫ} = νQ (f ) − bǫ.
0≤i≤n

0≤i≤n

(ii) Assume that SQ (f ) 6= {0} and set j0 = min SQ (f ). Then j0 = pe r for some
e ∈ N ∪ {0} and some r ∈ N with (r, p) = 1. We set b := pe b(Q) and will prove that
νQ (∂b (f )) = νQ (f ) − bǫ.
Write
pe
= rQ + h
fj0 ∂b(Q) Q

10

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

for some r, h ∈ K[x] and deg(h) < deg(Q) (note that h 6= 0 because Q is irreducible
and Q ∤ fj0 and Q ∤ ∂b(Q) Q). Then Lemma 2.3 (iii) gives us that


e
ν(h) = ν fj0 (∂b(Q) Q)p .
This implies that



e
ν hQj0 −p = νQ (f ) − bǫ.

(10)
Indeed, we have
e

ν hQj0 −p



=
=
=
=
=

e
e
e
ν(h) + ν Qj0 −p = ν fj0 (∂b(Q) Q)p + ν Qj0 −p

ν(fj0 ) + pe ν ∂b(Q) Q + (j0 − pe )ν(Q)
ν(fj0 ) + pe (ν (Q) − b(Q)ǫ) + (j0 − pe )ν(Q)
ν(fj0 ) + j0 ν(Q) − pe b(Q)ǫ
ν(fj0 Qj0 ) − pe b(Q)ǫ = νQ (f ) − bǫ.

Since f = f0 +f1 Q+. . .+fn Qn , we have ∂b (f ) = ∂b (f0 )+∂b (f1 Q) . . .+∂b (fn Qn ).
For each j = 0, . . . , n, if j ∈
/ SQ (f ), then

νQ ∂b (fj Qj ) ≥ νQ (fj Qj ) − bǫ > νQ (f ) − bǫ.
We set

h1 =

X

fj Qj .

j ∈S
/ Q (f )

Then νQ (h1 ) > νQ (f ) − bǫ.
For each j ∈ SQ (f ) the term ∂b (fj Qj ) can be written as a sum of terms of the
form Tb (b0 , . . . , br ). For each Tb (b0 , . . . , br ) we have the following cases:
Case 1: b0 > 0 or bi ∈
/ I(Q) for some i.
In this case, by Lemma 2.8 we have νQ (Tb (b0 , . . . , br )) > νQ (f ) − bǫ. In particular,
if h2 is the sum of all these terms, then νQ (h2 ) > νQ (f ) − bǫ.
Case 2: b0 = 0 and bi ∈ I(Q) for every i = 1, . . . , r but bi0 6= b(Q) for some
i0 = 1, . . . , r.
This implies, in particular, that j ≥ j0 and since b = pe b(Q) we must have r < pe .
Hence
!
r
Y
e
∂bi Q Qj−r = sQj0 −p +1
Tb (b0 , b1 , . . . , br ) = ∂b0 fj
i=1

for some s ∈ K[x].
Case 3: b0 = 0, j > j0 and bi = b(Q) for every i = 1, . . . , r.
r
X
bi = b we must have r = pe . Hence
Since b = pe b(Q), bi = b(Q) and
i=1

Tb (b0 , b1 , . . . , br ) = fj ∂b(Q) Q
for some s′ ∈ K[x].

pe

e

e

Qj−p = s′ Qj0 −p

+1

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

11

Case 4: b0 = 0, j = j0 and bi = b(Q) for every i = 1, . . . , r.
In this case we have
pe
e
Tb (b0 , b1 , . . . , br ) = fj0 ∂b(Q) Q Qj0 −p
e
(11)
= (h − rQ) Qj0 −p
e
e
= hQj0 −p − rQj0 −p +1 .
Observe that the number of times that the term (11) appears in ∂b (fj0 Qj0 ) is

j0
e
pe , that is, the number of ways that one can choose a subset with p elements in
a set of j0 elements.
Therefore, we can write

  
 
e
j0
j0
j0 −pe
′
r Qj0 −p +1 + h1 + h2
hQ
+
s
+
s
−
∂b (f ) =
e
e
p
p

j0
Since p ∤ pe the equation (10) gives us that

 
j0
j0 −pe
= νQ (f ) − bǫ.
hQ
ν
pe
Then

νQ



  
 
j0
j0
j0 −pe +1
j0 −pe
′
≤ νQ (f ) − bǫ.
r
Q
hQ
+
s
+
s
−
pe
pe

This and the fact that νQ (h1 + h2 ) > νQ (f )− bǫ imply that νQ (∂b (f )) ≤ νQ (f )− bǫ.
This concludes the proof of (ii).
(iii) The assumptions on b give us
νQ (f ) − νQ (∂b f )
=ǫ
b
and
νQ (∂b f ) = ν(∂b f ).
Consequently,
νQ (f ) − νQ (∂b f )
ν(f ) − ν(∂b f )
≥
= ǫ.
b
b
In the inequality above, one can see that if ν(f ) > νQ (f ), then ǫ(f ) > ǫ.
ǫ(f ) ≥


Proposition 2.10. For two key polynomials Q, Q′ ∈ K[x] we have the following:
(i): If deg(Q) < deg(Q′ ), then ǫ(Q) < ǫ(Q′ );
(ii): If ǫ(Q) < ǫ(Q′ ), then νQ (Q′ ) < ν(Q′ );
(iii): If deg(Q) = deg(Q′ ), then
(12)

ν(Q) < ν(Q′ ) ⇐⇒ νQ (Q′ ) < ν(Q′ ) ⇐⇒ ǫ(Q) < ǫ(Q′ ).

Proof. Item (i) follows immediately from the the definition of key polynomial (in
fact, the same holds if we substitute Q for any f ∈ K[x]).
In order to prove (ii) we set ǫ := ǫ(Q) and b′ := b(Q′ ). By (i) of Proposition
2.7, we have
νQ (Q′ ) ≤ νQ (∂b′ Q′ ) + b′ ǫ.

12

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

Since ǫ(Q) < ǫ(Q′ ), we also have
ν(∂b′ Q′ ) + b′ ǫ < ν(∂b′ Q′ ) + b′ ǫ(Q′ ) = ν(Q′ ).
This, and the fact that νQ (∂b′ Q′ ) ≤ ν(∂b′ Q′ ), imply that νQ (Q′ ) < ν(Q′ ).
Now assume that deg(Q) = deg(Q′ ) and let us prove (12). Since
deg(Q) = deg(Q′ )
and both Q and Q′ are monic, the Q-standard expansion of Q′ is given by
Q′ = Q + (Q − Q′ ).
Hence
νQ (Q′ ) = min{ν(Q), ν(Q − Q′ )}.
The first equivalence follows immediately from this. In view of part (ii), it remains
to prove that if νQ (Q′ ) < ν(Q′ ), then ǫ(Q) < ǫ(Q′ ). Since νQ (Q′ ) < ν(Q′ ) we have
SQ (Q′ ) 6= {0}. Hence, by Proposition 2.7 (ii), the equality holds in (8) (for f = Q′ )
for some b ∈ N. Moreover, since deg(Q) = deg(Q′ ), we have deg(∂b Q′ ) < deg(Q)
and consequently νQ (∂b Q′ ) = ν(∂b Q′ ). Then Proposition 2.7 (iii) implies that
ǫ(Q) < ǫ(Q′ ).

For a key polynomial Q ∈ K[x], let
α(Q) := min{deg(f ) | νQ (f ) < ν(f )}
(if νQ = ν, then set α(Q) = ∞) and
Ψ(Q) := {f ∈ K[x] | f is monic, νQ (f ) < ν(f ) and α(Q) = deg(f )}.
Lemma 2.11. If Q is a key polynomial, then every element Q′ ∈ Ψ(Q) is also a
key polynomial. Moreover, ǫ(Q) < ǫ(Q′ ).
Proof. By assumption, we have νQ (Q′ ) < ν(Q′ ), hence SQ (Q′ ) 6= {0}. This implies,
by Proposition 2.7 (ii), that there exists b ∈ N such that
νQ (Q′ ) − νQ (∂b Q′ ) = bǫ(Q).
Since deg(∂b Q′ ) < deg(Q′ ) = α(Q), we have νQ (∂b Q′ ) = ν(∂b Q′ ). Consequently,
by Proposition 2.7 (iii), ǫ(Q) < ǫ(Q′ ).
Now take any polynomial f ∈ K[x] such that deg(f ) < deg(Q′ ) = α(Q). In
particular, νQ (f ) = ν(f ). Moreover, for every b ∈ N, deg(∂b f ) < deg(Q′ ) = α(Q)
which implies that νQ (∂b f ) = ν(∂b f ). Then, for every b ∈ N,
ν(f ) − ν(∂b f )
νQ (f ) − νQ (∂b f )
=
≤ ǫ(Q) < ǫ(Q′ ).
b
b
This implies that ǫ(f ) < ǫ(Q′ ), which shows that Q′ is a key polynomial.

Theorem 2.12. A polynomial Q is a key polynomial if and only if there exists a
key polynomial Q− ∈ K[x] such that Q ∈ Ψ(Q− ) or the following conditions hold:
(K1): α(Q− ) = deg(Q− )

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

13

(K2): the set {ν(Q′ ) | Q′ ∈ Ψ(Q− )} does not contain a maximal element
(K3): νQ′ (Q) < ν(Q) for every Q′ ∈ Ψ(Q− )
(K4): Q has the smallest degree among polynomials satisfying (K3).
Proof. We will prove first that if such Q− exists, then Q is a key polynomial.
The case when Q ∈ Ψ(Q− ) follows from Lemma 2.11. Assume now that (K1)
- (K4) hold. Take f ∈ K[x] such that deg(f ) < deg(Q). This implies that
deg(∂b Q) < deg(Q) and deg(∂b f ) < deg(Q) for every b ∈ N. Hence, by (K4), there
exists Q′ ∈ Ψ(Q− ) such that
νQ′ (f ) = ν(f ), νQ′ (∂b f ) = ν(∂b f ) and νQ′ (∂b Q) = ν(∂b Q) for every b ∈ N.
We claim that ǫ(Q′ ) < ǫ(Q). If not, by Proposition 2.10 (i), we would have
deg(Q) ≤ deg(Q′ ). Since νQ′ (Q) < ν(Q), this implies that deg(Q) = deg(Q′ ).
This and Proposition 2.10 (iii) give us that ǫ(Q′ ) < ǫ(Q) which is a contradiction.
Now,
νQ′ (f ) − νQ′ (∂b f )
ν(f ) − ν(∂b f )
=
≤ ǫ(Q′ ) < ǫ(Q).
b
b
Hence Q is a key polynomial.
For the converse, take a key polynomial Q ∈ K[x] and consider the set
ǫ(f ) ≤

S := {Q′ ∈ K[x] | Q′ is a key polynomial and νQ′ (Q) < ν(Q)}.
Observe that S =
6 ∅. Indeed, if deg(Q) > 1, then every key polynomial x − a ∈ S.
If Q = x − a, then there exits b ∈ K such that ν(b) < min{ν(a), ν(x)}. Therefore,
x − b ∈ S.
If there exists a key polynomial Q− ∈ S such that deg(Q) = deg(Q− ) , then we
have Q ∈ Ψ(Q− ) and we are done. Hence, assume that every polynomial Q′ ∈ S
has degree smaller that deg(Q).
Assume that there exists Q− ∈ S such that for every Q′ ∈ S we have
(13)

(deg(Q− ), ν(Q− )) ≥ ((deg(Q′ ), ν(Q′ ))

in the lexicographical ordering. We claim that Q ∈ Ψ(Q− ). If not, there would
exist a key polynomial Q′′ such that νQ− (Q′′ ) < ν(Q′′ ) and deg(Q′′ ) < deg(Q).
Since deg(Q′′ ) < deg(Q) Proposition 2.10 (i) and (ii) give us that νQ′′ (Q) < ν(Q).
Hence Q′′ ∈ S. The inequality (13) gives us that deg(Q′′ ) ≤ deg(Q− ). On the
other hand, since νQ− (Q′′ ) < ν(Q′′ ) we must have deg(Q− ) = deg(Q′′ ). Hence,
Proposition 2.10 (iii) gives us that ν(Q− ) < ν(Q′′ ) and this is a contradiction to
the inequality (13).
Now assume that for every Q′ ∈ S, there exists Q′′ ∈ S such that
(14)

(deg(Q′ ), ν(Q′ )) < (deg(Q′′ ), ν(Q′′ ))

in the lexicographical ordering. Take Q− ∈ S such that deg(Q− ) ≥ deg(Q′ ) for
every Q′ ∈ S. We will show that the conditions (K1) - (K4) are satisfied. By
(14), there exists Q′′ ∈ S such that
(15)

(deg(Q− ), ν(Q− )) < (deg(Q′′ ), ν(Q′′ )).

14

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

In particular, deg(Q− ) = deg(Q′′ ) and ν(Q− ) < ν(Q′′ ). Proposition 2.10 (iii) gives
us that νQ− (Q′′ ) < ν(Q′′ ). Hence α(Q− ) = deg(Q− ) and we have proved (K1). If
Q′ ∈ Ψ(Q− ), then deg(Q′ ) = deg(Q− ) < deg(Q) and hence νQ′ (Q) < ν(Q). This
implies that Q′ ∈ S. The equation (15) tells us that {ν(Q′ ) | Q′ ∈ Ψ(Q− )} has no
maximum, so we have proved (K2). Now take any element Q′ ∈ Ψ(Q− ). Then
deg(Q′ ) < deg(Q) and Proposition 2.10 (i) and (ii) give us that νQ′ (Q) < ν(Q).
e with νQ′ (Q)
e < ν(Q)
e for every Q′ ∈ Ψ(Q− )
This proves (K3). Take a polynomial Q
e = deg(Q). Assume,
with minimal degree possible. We want to prove that deg(Q)
e < deg(Q). The first part of the proof
aiming for a contradiction, that deg(Q)
e < ν(Q)
e and
e
gives us that Q is a key polynomial. Fix Q′ ∈ Ψ(Q− ). Then νQ′ (Q)
′
′
e = deg(Q ) = deg(Q− ). Therefore ν(Q ) < ν(Q)
e for every
consequently deg(Q)
′
Q ∈ Ψ(Q− ), which is a contradiction to (14). This concludes our proof.

Definition 2.13. When conditions (K1) - (K4) of Theorem 2.12 are satisfied, we
say that Q is a limit key polynomial.
Remark 2.14. Observe that as a consequence of the proof we obtain that
ǫ(Q− ) < ǫ(Q).
Proof of Theorem 1.1. Consider the set
Γ0 := {ν(x − a) | a ∈ K}.
We have two possibilities:
• Γ0 has a maximal element
Set Q0 := x − a0 where a0 ∈ K is such that ν(x − a0 ) is a maximum of Γ0 . If
ν = νQ0 we are done, so assume that ν 6= νQ0 . If the set
{ν(Q) | Q ∈ Ψ(Q0 )}
has a maximum, choose Q1 ∈ Ψ(Q0 ) such that ν(Q1 ) is this maximum. If not,
choose Q1 as any polynomial in Ψ(Q0 ). Set Λ1 := {Q0 , Q1 } (ordered by Q0 < Q1 ).
• Γ0 does not have a maximal element
For every γ ∈ Γ0 set Qγ := x − aγ for some aγ ∈ K such that ν(x − aγ ) = γ. If
for every f ∈ K[x], there exists γ ∈ Γ0 such that ν(f ) = νQγ (f ) we are done. If
not, let Q be a polynomial of minimal degree among all the polynomials for which
νQγ (Q) < ν(Q) for every γ ∈ Γ0 . If α(Q) = deg(Q) and the set {ν(Q′ ) | Q′ ∈ Ψ(Q)}
contains a maximal element, choose Q1 ∈ Ψ(Q) such that ν(Q1 ) ≥ ν(Q′ ) for every
Q′ ∈ Ψ(Q). If not, set Q1 := Q. Set Λ1 := {Qγ | γ ∈ Γ0 } ∪ {Q1 } (ordered by
Q1 > Qγ for every γ ∈ Γ and Qγ > Qγ ′ if γ > γ ′ ).
Observe that in either case, deg(Q1 ) > deg(Q0 ) and for Q, Q′ ∈ Λ1 , Q < Q′ if
and only if ǫ(Q) < ǫ(Q′ ). Moreover, if α(Q1 ) = deg(Q1 ), then {ν(Q) | Q ∈ Ψ(Q1 )}
does not have a maximum.
Assume that for some i ∈ N, there exists a totally ordered set Λi consisting of
key polynomials with the following properties:

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

15

(i): there exist Q0 , Q1 , . . . , Qi ∈ Λi such that Qi is the last element of Λi and
deg(Q0 ) < deg(Q1 ) < . . . < deg(Qi ).
(ii): if α(Qi ) = deg(Qi ), then Γi := {ν(Q) | Q ∈ Ψ(Qi )} does not have a
maximum.
(iii): for Q, Q′ ∈ Λi , Q < Q′ if and only if ǫ(Q) < ǫ(Q′ ).
If νQi 6= ν, then we will construct a set Λi+1 of key polynomials having the same
properties (changing i by i + 1).
Since νQi 6= ν, the set Ψ(Qi ) is not empty. We have two cases:
• α(Qi ) > deg(Qi ).
If Γi has a maximum, take Qi+1 ∈ Ψ(Qi ) such that ν(Qi+1 ) ≥ Γi . Otherwise,
choose Qi+1 to be any element of Ψ(Qi ). Observe that if α(Qi+1 ) = deg(Qi+1 ),
then Γi+1 does not have a maximum. Set Λi+1 = Λi ∪ {Qi+1 } with the extension
of the order in Λi obtained by setting Qi+1 > Q for every Q ∈ Λi .
• α(Qi ) = deg(Qi ).
By assumption, the set Γi does not have a maximum. For each γ ∈ Γi , choose
a polynomial Qγ ∈ Ψ(Qi ) such that ν(Qγ ) = γ. If for every f ∈ K[x], there
exists γ ∈ Γi such that νQγ (f ) = ν(f ), then we are done. Otherwise, choose a
monic polynomial Q, of smallest degree possible, such that νQ′ (Q) < ν(Q) for
every Q′ ∈ Ψ(Qi ). If α(Q) = deg(Q) and {ν(Q′ ) | Q′ ∈ Ψ(Q)} has a maximum,
we choose Qi+1 such that ν(Qi+1 ) ≥ {ν(Q′ ) | Q′ ∈ Ψ(Q)}. Otherwise we set
Qi+1 = Q. Then set
Λi+1 := Λi ∪ {Qγ | γ ∈ Γi } ∪ {Qi+1 },
with the extension of the order of Λi given by
Qi+1 > Q′ for every Q′ ∈ Λi+1 \ {Qi+1 },
Qγ > Q′ for every γ ∈ Γi and Q′ ∈ Λi and Qγ > Qγ ′ for γ, γ ′ ∈ Γi with γ > γ ′ .
In all cases, the set Λi+1 has the properties (i), (ii) and (iii).
Assume now that for every i ∈ N the sets Λi and Λi+1 can be constructed. Then
we can construct a set
∞
[
Λi
Λ∞ :=
i=1

of key polynomials having the property that for Q, Q′ ∈ Λ∞ , Q < Q′ if and only if
ǫ(Q) < ǫ(Q′ ) and there are polynomials Q0 , . . . , Qi , . . . ∈ Λ∞ such that
deg(Qi+1 ) > deg(Qi )
for every i ∈ N. This means that for every f ∈ K[x] there exists i ∈ N such that
deg(f ) < deg(Qi ), which implies that νQi (f ) = ν(f ). Therefore, Λ∞ is a complete
set of key polynomials for ν.

Observe that at each stage, the same construction would work if we replaced Γi
by any cofinal set Γ′i of Γi . Hence, if the rank of ν is equal to 1, then we can choose

16

JOSNEI NOVACOSKI AND MARK SPIVAKOVSKY

Γ′i to have order type at most ω. Then, from the construction of the sets Λi and
Λ∞ , we can conclude the following:
Corollary 2.15. If the rank of ν is equal to one, then there exists a complete
sequence of key polynomials of ν with order type at most ω × ω.
3. Pseudo-convergent sequences
The next two theorems justify the definitions of algebraic and transcendental
pseudo-convergent sequences.
Theorem 3.1 (Theorem 2 of [1]). If {aρ }ρ<λ is a pseudo-convergent sequence of
transcendental type, without a limit in K, then there exists an immediate transcendental extension K(z) of K defined by setting ν(f (z)) to be the value ν(f (aρf )) as
in condition (2). Moreover, for every valuation µ in some extension K(u) of K, if
u is a pseudo-limit of {aρ }ρ<λ , then there exists a value preserving K-isomorphism
from K(u) to K(z) taking u to z.
Theorem 3.2 (Theorem 3 of [1]). Let {aρ }ρ<λ be a pseudo-convergent sequence of
algebraic type, without a limit in K, q(x) a polynomial of smallest degree for which
(3) holds and z a root of q(x). Then there exists an immediate algebraic extension of
K to K(z) defined as follows: for every polynomial f (x) ∈ K[x], with deg f < deg q
we set ν(f (z)) to be the value ν(f (aρf )) as in condition (2). Moreover, if u is a root
of q(x) and µ is some extension K(u) of K making u a pseudo-limit of {aρ }ρ<λ ,
then there exists a value preserving K-isomorphism from K(u) to K(z) taking u to
z.
For the rest of this paper, let {aρ }ρ<λ be a pseudo-convergent sequence for the
valued field (K, ν), without a limit in K. For each ρ < λ, we denote νρ = νx−aρ .
For a polynomial f (x) ∈ K[x] and a ∈ K we consider the Taylor expansion of f at
a given by
f (x) = f (a) + ∂1 f (a)(x − a) + . . . + ∂n f (a)(x − a)n .
Assume that {aρ }ρ<λ fixes the value of the polynomials ∂i f (x) for every 1 ≤ i ≤ n.
We denote by βi this fixed value.
Lemma 3.3 (Lemma 8 of [1]). There is an integer h, which is a power of p, such
that for sufficiently large ρ
βi + iγρ > βh + hγρ whenever i 6= h and ν(f (aρ )) = βh + hγρ .
Corollary 3.4. If {aρ }ρ<λ fixes the value of f (x), then νρ (f (x)) = ν(f (x)). On
the other hand, if {aρ }ρ<λ does not fix the value of f (x), then νρ (f (x)) < ν(f (x))
for every ρ < λ.
Proof. By definition of νρ we have
νρ (f (x)) = min {ν(∂i f (aρ )(x − aρ )i )} = min {βi + iγρ },
0≤i≤n

0≤i≤n

KEY POLYNOMIALS AND PSEUDO-CONVERGENT SEQUENCES

17

where β0 := ν(f (aρ )). This implies, using the lemma above, that
νρ (f (x)) = ν(f (aρ )).
If {aρ }ρ<λ fixes the value of f (x), then ν(f (aρ )) = ν(f (x)) for ρ sufficiently large.
Thus νρ (f (x)) = ν(f (x)). On the other hand, if {aρ }ρ<λ does not fix the value of
f (x), then ν(f (x)) > ν(f (aρ )) = νρ (f (x)) for every ρ < λ.

Proof of Theorem 1.2. If {aρ }ρ<λ is of transcendental type it fixes, for any polynomial f (x) ∈ K[x], the values of the polynomials ∂i f (x) for every 0 ≤ i ≤ n (here
∂0 f := f ). Hence, Corollary 3.4 implies that νρ (f (x)) = ν(f (x)) for sufficiently
large ρ < λ, which is what we wanted to prove.
Now assume that {aρ }ρ<λ is of algebraic type. Take ρ < λ such that
ν(q(aτ )) > ν(q(aσ ))
for every ρ < σ < τ < λ and set Q− = x − aρ . Then
νQ− (x − aσ ) = νQ− (x − aρ + aρ − aσ ) = ν(x − aρ ) < ν(x − aσ )
for every ρ < σ < λ. This implies that α(Q−) = 1 and then α(Q− ) = deg(Q− ).
Consequently, (K1) is satisfied. Moreover,
Ψ(Q− ) = {x − a | νQ− (x − a) < ν(x − a)}.
In order to prove (K2) assume, aiming for a contradiction, that ν(Ψ(Q− )) has a
maximum, let us say ν(x − a). Then, in particular, ν(x − a) > ν(x − aσ ) for every
ρ < σ < λ. This implies that a ∈ K is a limit of {aρ }ρ<λ , which is a contradiction.
Condition (K3) and (K4) follow immediately from Corollary 3.4 and the fact that
{ν(x − aρ ) | ρ < λ} is cofinal in ν(Ψ(Q− )).

References
[1] I. Kaplansky, Maximal fields with valuations I, Duke Math. Journ. 9 (1942), 303–321.
[2] H. Knaf e F.-V. Kuhlmann, Every place admits local uniformization in a finite extension of
the function field, Adv. Math. 221 no. 2 (2009), 428–453.
[3] S. MacLane, A construction for absolute values in polynomial rings, Trans. Amer. Math.
Soc. 40 (1936), 363 – 395.
[4] W. Mahboub, Key Polynomials, J. Pure Appl. Algebra 217 (2013), 989–1006.
[5] F. J. Herrera Govantes, W. Mahboub, M. A. Olalla Acosta and M. Spivakovsky, Key polynomials for simple extensions of valued fields, preprint, arXiv:1406.0657, 2016.
[6] J.-C. San Saturnino, Defect of an extension, key polynomials and local uniformization,
preprint, arXiv:1412.7697, 2014.
[7] M. Spivakovsky, Valuations in function fields of surfaces, Amer. J. Math. 112 no. 1 (1990),
107–156.
[8] B. Teissier, Valuations, deformations, and toric geometry, Valuation theory and its applications, Vol. II (Saskatoon, SK, 1999), 361 – 459, Fields Inst. Commun. 33, (2003).
[9] M. Vaquie, Extension d’une valuation, Trans. Amer. Math. Soc. 359 no. 7 (2007), 3439 –
3481.

