Fields Institute Communications Volume 00, 0000

Generalized Taylor formulae, computations in real closed valued fields and quantifier elimination

Mari-Emi Alonso

Universitad Complutense, Madrid, España

                                 M_{−}Alonso@Mat.UCM.Es

Henri Lombardi

Laboratoire de Mathématiques, (UMR CNRS 6623), UFR des Sciences et Techniques, Université

de Franche-Comté, 25030 BESANÇON cedex, France.

                             lombardi@math.univ-fcomte.fr

Abstract. We use generalized Taylor formulae in order to give some simple constructions in the real closure of an ordered valued field. We deduce a new, simple quantifier elimination algorithm for real closed valued fields and some theorems about constructible subsets of real valuative affine space.

Introduction

In this work, we consider the real closure of an ordered valued field and search for simple computations giving a constructive content to this real closure. We don’t try to give sophisticated algorithms which would allow better complexity.

We consider an ordered valued field (K, V, P) with V its valuation ring and P its positive cone. Recall that this means that the following properties hold

V + V ⊆ V, V × V ⊆ V, ∃x ∈ K \ V,
∀x, y ∈ K (xy = 1 ⇒ x ∈ V ∨ y ∈ V),
P × P ⊆ P, P + P ⊆ P, ∃x ∈ K \ P,
∀x, y ∈ K (x + y = 0 ⇒ x ∈ P ∨ y ∈ P),
∀x, y ∈ K [(x + y ∈ V, x ∈ P, y ∈ P) ⇒ x ∈ V].

For a, b in K, we write a ≤ b if and only if b − a is in P. We shall use freely in the sequel some well known features of ordered valued fields: ℚ ⊆ V, elements of V bounded from below by some positive rational are units in V, and the non-units in V are the infinitesimal elements of K.

\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society

1991 Mathematics Subject Classification. 14P10, 12J10, 12L05, 12Y05, 03F65, 03C10.

Partially supported by: PB95/0563-A.

Let S be a subring of V such that K is the fraction field of S. We assume that S is an explicit ordered ring and that divisibility inside V is testable for two arbitrary elements of S. These are our minimal assumptions of computability. If we want more assumptions in certain cases we shall make them explicit.

We denote the real closure of (K, P) by (K^{rc}, P^{rc}), and we write V^{rc} for the convex hull of V inside K^{rc}; then V^{rc} is the unique order-compatible valuation ring extending V. We call (K^{rc}, V^{rc}, P^{rc}) the real closure of (K, V, P).

In sections 1 and 2 our general purpose is to discuss computational problems in (K^{rc}, V^{rc}, P^{rc}) under our computability assumptions on (K, V, P).

Each computational problem we shall consider has as input a finite family (c_{i})_{i=1,... ,n} of parameters in the ring S. We call them the coefficients of our computational problem. Our algorithms with the previous minimal computability assumptions work uniformly. This means that some computations are made that give polynomials in ℤ[C_{1}, …, C_{n}], and that all our tests are of the two following types:

Is P (c_{1}, …, c_{n}) ≥ 0? Does Q(c_{1}, …, c_{n}) divide P (c_{1}, …, c_{n}) in V?

We are not interested in how the answers to these tests are found. We may imagine these answers given either by some oracles or by some algorithms.

Let us state precisely some other notations. We shall denote the unit group of V by U_{V}, and M_{V} = V \ U_{V} will be the maximal ideal.

We shall denote the residue field V/M_{V} of (K, V) by \overline{K}, and the value group, K^{×}/U_{V}, by Γ_{K}. We use freely the value group’s usual additive notation as well as its usual group-ordering (also denoted by ≤). Recall that Γ_{K^{rc}} is the divisible hull Γ_{K}^{dh} of Γ_{K}. For x ∈ K we write v(x) or v_{K}(x) the valuation of x in Γ_{K} ∪ {+∞}. So

v(0) = +∞, v(xy) = v(x) + v(y), (x ≥ 0, y ≥ 0) ⇒ v(x + y) = min(v(x), v(y)),

and

∀x ∈ K ((v(x) ≥ 0 ⇔ x ∈ V) ∧ (v(x) > 0 ⇔ x ∈ M_{V})).

We write K^{ac} = K^{rc}[\sqrt{−1}] and we denote by V^{ac} the natural valuation ring of K^{ac} extending V^{rc}: for a, b ∈ K^{rc}, v(a + b\sqrt{−1}) = (1/2)v(a^{2} + b^{2}).

In fact elements of Γ_{K}^{dh} ∪ {+∞} are always defined through elements of S in the following form. We say that the valuation of some element x belonging to K^{ac} is well determined if we know integers m and n, elements c_{1}, ..., c_{n} in S, and two elements F and G of ℤ[C_{1}, ..., C_{n}], such that, setting f = F (c_{1}, …, c_{n}) (f ≠ 0) and g = G(c_{1}, …, c_{n}), there exists a unit u in V^{ac} with:

fx^{m} = ug

(in particular, v(0) is well determined).

We read the previous formula as:

m v_{K^{ac}}(x) = v_{K}(g) − v_{K}(f),

or more simply as:

m v(x) = v(g) − v(f).

For x, y ∈ K^{ac}, we shall use the notation x ⪯ y for v(x) ≤ v(y) (i.e., y = x = 0 ∨ (x ≠ 0 ∧ y/x ∈ V^{ac})).

Example. Let us explain the computations that are necessary to compare 3v(x_{1})+ 2v(x_{2}) to 7v(x_{3}) when the valuations are given by

f_{1}x_{1}^{m_{1}} = u_{1}g_{1}, f_{2}x_{2}^{m_{2}} = u_{2}g_{2}, f_{3}x_{3}^{m_{3}} = u_{3}g_{3} (g_{1}, g_{2}, g_{3} ≠ 0).

Generalized Taylor formulae … quantifier elimination 3

We consider the LCM m = m_{1}n_{1} = m_{2}n_{2} = m_{3}n_{3} of m_{1}, m_{2}, m_{3}. We have

f_{1}^{n_{1}}x_{1}^{m} = u_{1}^{n_{1}}g_{1}^{n_{1}}, f_{2}^{n_{2}}x_{2}^{m} = u_{2}^{n_{2}}g_{2}^{n_{2}}, f_{3}^{n_{3}}x_{3}^{m} = u_{3}^{n_{3}}g_{3}^{n_{3}}.

So 3v(x_{1}) + 2v(x_{2}) ≤ 7v(x_{3}) iff g_{1}^{3n_{1}}g_{2}^{2n_{2}}f_{3}^{7n_{3}} ⪯ f_{1}^{3n_{1}}f_{2}^{2n_{2}}g_{3}^{7n_{3}}.

The reader can easily verify that computations we shall run in the value group are always meaningful under our computability assumptions on the ring S.

In the same way, elements of the residue field will in general be defined from elements of V. So computations inside the residue field are given by computations inside S.

We now give an outline of the paper.

In section 1 we give some basic tools used in the rest of the paper. First we recall the Newton Polygon Algorithm and the Generalized Tschirnhaus Transformation. Then we insist on Generalized Taylor formulae, which are formulae giving P (x) on a Thom interval as a sum of terms all having the same sign. This feature allows us to give a good description for v(P (x)) with the crucial Theorem 1.3.6. This allows us to give a nice description for “constructible” subsets of the real line in the context of real closed valued fields (cf. Theorem 1.4.4).

In section 2 we settle three basic computational problems in the real closure of an ordered valued field. We solve the first problem by a simple trick (subsection 2.3). The consequence is that when we know how to compute in a given ordered valued field, we know how to compute in its real closure. This can be seen as a not too difficult extension of basic algorithms in real closed fields. Solving the second problem is possible by using our first algorithm, but we prefer to develop another algorithm, similar to the Cohen-Hörmander algorithm for ordered fields. We get in this way nice uniform results describing precisely some generalizations of the complete tableau of signs in the real closed case (Theorems 2.4.5 and 2.5.2).

In section 3 we give parametrized versions of previous algorithms (Theorems 3.1.1 and 3.1.3), and we apply these results to quantifier elimination in real closed valued fields. We consider the first order theory of real closed valued fields based on the language of ordered fields (0, 1, +, −, ×, =, ≤) to which we add the predicate x ⪯ y. So, all constants and variables represent elements in K (this corresponds to our previously explained computability assumptions). We get the following theorem.

Theorem 3.2.1 Let Φ(\underline{a}, \underline{x}) be a quantifier free formula in the first order theory of real closed valued fields. We view the a_{i}’s as parameters and the x_{j}’s as variables.

Then one can give a quantifier free formula Ψ(\underline{a}) such that the two formulae ∃\underline{x} Φ(\underline{a}, \underline{x}) and Ψ(\underline{a}) are equivalent in the formal theory. (The terms appearing in the formulae Φ and Ψ are ℤ–polynomials in the parameters, and, in the case of Φ, also in the variables.)

We think we have given here a rather simple proof of this fundamental, well known result (see e.g., [2]).

We also get the following abstract form of the previous theorem.

Theorem 3.3.2 Let us denote the real-valuative spectrum of a commutative ring A by SpervA. Then the canonical mapping from SpervA[X] to SpervA transforms any constructible subset into a constructible subset.

In section 4 we apply the parametrized algorithms in order to study constructible subsets (in the meaning of real closed valued fields). First, we get the analogue of the Tarski-Seidenberg principle.

Theorem 4.1.1 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let π be the canonical projection from R^{n+r} onto R^{n}. Let S ⊆ R^{n+r} be any (≤, ⪯)–constructible set defined over (K, V, P). Assume that the sign test and the divisibility test are explicit inside the ring generated by the coefficients of the polynomials that appear in the definition of S. Then a description of the projection π(S) ⊆ R^{n} can be computed in a uniform way by an algorithm that uses only rational computations, sign tests and divisibility tests.

In particular, the complexity of a description of π(S) is explicitly bounded in terms of the complexity of a description of S.

Finally we construct a kind of stratification for (≤, ⪯)–constructible sets, that we call stratification à la Cohen Hormander because it is a further development of the same notion for semialgebraic sets (c.f. [1] chapter 9), and we finish the paper with the following cell-decomposition theorem (for a precise definition of ℚ-semilinear functions see definition 2.4.4).

Theorem 4.2.5 (Cell decomposition theorem) Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let g_{1}, …, g_{s} be nonzero polynomials in K[x_{1}, …, x_{n}]. Consider a linear change of variables together with a family (f_{i,j})_{i=1,... ,n;j=1,... ,ℓ_{i}} that give a stratification for (g_{1}, …, g_{s}). Assume that this stratification is constructed à la Cohen-Hörmander. Consider any kdimensional stratum C_{ε} corresponding to this stratification. Then there is a Nash isomorphism

h : (R^{+})^{k} ⟶ C_{ε}, (t_{1}, …, t_{k}) ⟼ h(t_{1}, …, t_{k})

with the following property.

If S is any (≤, ⪯)–constructible subset described from g_{1}, …, g_{s}, then S ∩ C_{ε} is a finite union of cells h(L_{i}), where each L_{i} can be defined as

{(t_{1}, …, t_{k}) ∈ (R^{+})^{k} : ⋀_{ℓ} a_{ℓ}(τ) = α_{ℓ} ∧ ⋀_{m} b_{m}(τ) > β_{m}} ,

where τ = (τ_{1}, …, τ_{k}) = (v(t_{1}), …, v(t_{k}), the a_{ℓ}’s and b_{m}’s are ℤ-linear forms w.r.t. τ, and α_{ℓ}, β_{m} ∈ Γ_{K}^{dh}.

Moreover, each τ_{i} is a ℚ-semilinear function in some v(F_{j}(x_{1}, …, x_{n}))’s (with F_{j} explicitly computable in K[x_{1}, …, x_{n}]).

1 Basic material

1.1 The Newton Polygon. Here we recall the well known Newton Polygon algorithm.

A multiset is a set with (nonnegative) multiplicities, or equivalently a list defined up to permutation. E.g., the roots of a polynomial P (X) repeated according to multiplicities form a multiset in the algebraic closure of the base field. We shall use the notation [x_{1}, …, x_{d}] for the multiset corresponding to the list (x_{1}, …, x_{d}). The cardinality of a multiset is the length of a corresponding list, i.e., the sum of multiplicities occurring in the multiset.

The Newton polygon of a polynomial P (X) = ∑_{i=0,... ,d} p_{i}X^{i} ∈ K[X] (where p_{d} ≠ 0) is obtained from the list of pairs in ℕ × (Γ_{K} ∪ {+∞})

((0, v(p_{0})), (1, v(p_{1})), …, (d, v(p_{d}))).

The Newton polygon is “the bottom convex hull” of this list. It can be formally defined as the extracted list ((0, v(p_{0})), …, (d, v(p_{d}))) verifying: two pairs (i, v(p_{i})) and (j, v(p_{j})) are two consecutive vertices of the Newton polygon iff:

if 0 ≤ k < i then (v(p_{j}) − v(p_{i}))/(j − i) > (v(p_{i}) − v(p_{k})/(i − k))

if i < k < j then (v(p_{k}) − v(p_{i}))/(k − i) ≥ (v(p_{j}) − v(p_{i}))/(j − i)
if j < k ≤ d then (v(p_{k}) − v(p_{j}))/(k − j) > (v(p_{j}) − v(p_{i}))/(j − i)

It is easily shown that if (i, v(p_{i})) and (j, v(p_{j})) are two consecutive vertices in the Newton polygon of the polynomial P, then the zeroes of P in K^{ac} whose valuation in Γ_{K}^{dh} equals (v(p_{i}) − v(p_{j}))/(j − i) form a multiset with cardinality j − i.

Computational problem 0 (Multiset of valuations of roots of polynomials) Input: Let P ∈ K[X] be a polynomial over a valued field (K, V). Output: The multiset [v(x_{1}), …, v(x_{n})] where [x_{1}, …, x_{n}] is the multiset of roots of P in K^{ac}.

Newton Polygon algorithm The number n_{∞} of roots equal to 0 (i.e., with infinite valuation) is read on P. Let P_{0} := P/X^{n_{∞}}. Compute the Newton polygon of P_{0}, compute the slopes and output the answer.

1.2 Generalized Tschirnhaus transformation. We recall here the well known (generalized) Tschirnhaus transformation, which we will use freely in our computations.

Let K be a field, (P_{j})_{j=1,... ,m} be a family of monic polynomials in K[X], and

P_{j}(X) = (X − x_{j,1}) × ⋯ × (X − x_{j,d_{j}})

their decompositions in K^{ac}. Let Q(Y_{1}, …, Y_{m}) be a polynomial in K[Y_{1}, …, Y_{m}]. Then the polynomial

T_{Q}(Z) = (Z − Q(x_{1,1}, …, x_{m,1})) × ⋯ × (Z − Q(x_{1,d_{1}}, …, x_{m,d_{m}}))

is the characteristic polynomial of A_{Q} where A_{Q} is the matrix of the multiplication by Q(y_{1}, …, y_{m}) inside the d-dimensional K-algebra

K[y_{1}, …, y_{m}] := K[Y_{1}, …, Y_{m}]/ ⟨P_{1}(Y_{1}), …, P_{m}(Y_{m})⟩

(d = d_{1} ⋯ d_{m}, and y_{i} is the class of Y_{i} modulo ⟨P_{1}, …, P_{m}⟩).

Now let R ∈ K[Y_{1}, …, Y_{m}] with R(\underline{x}) ≠ 0 for all m-tuples \underline{x} = (x_{1,r_{1}}, …, x_{m,r_{m}}). So A_{R} is an invertible matrix. Let F = Q/R, then the polynomial

T_{F} (Z) = (Z − F (x_{1,1}, …, x_{m,1})) × ⋯ × (Z − F (x_{1,d_{1}}, …, x_{m,d_{m}}))

is the characteristic polynomial of A_{Q}(A_{R})^{−1}.

1.3 Generalized Taylor Formulas.

Using the usual Taylor formula for computing valuations in Γ_{K}^{dh}. For P ∈ K[X] we denote P^{[k]} = P^{(k)}/k!, where P^{(k)} is the k-th derivative of

P. Let t = x − a, and assume deg(P) = d, the usual Taylor formula at the point a is

P (x) = P (a) + P^{[1]}(a)t + P^{[2]}(a)t^{2} + ⋯ + P^{[d−1]}(a)t^{d−1} + P^{[d]}t^{d}.

Now assume that P^{[d]} > 0. Let a_{0} be the greatest real root of the product P P^{[1]} ⋯ P^{[d−1]}. If a ≥ a_{0} we see that all P^{[k]}(a) are ≥ 0 and we get the following expression for the valuation v(P (x)) when x > a

v(P (x)) = min(ν_{0}, ν_{1} + τ, ν_{2} + 2τ, …, ν_{d} + dτ)

where τ = v(t) and ν_{j} = v(P^{[j]}(a)) (some ν_{j}’s may be infinite). So, w.r.t. the variable τ the valuation of P (x) in Γ_{K}^{dh} is piecewise linear and increasing. Note that τ decreases from +∞ to −∞ when t increases from 0 to +∞.

In the following paragraphs, we see that generalized Taylor formulae allow us to give a similar description of the valuation v(P (x)) when x is inside a Thom interval.

What are generalized Taylor formulae?

A fundamental example of algebraic evidence for a sign is given by generalized Taylor formulae, which make explicit some consequences of Thom’s lemma in terms of algebraic identities.

Thom’s lemma implies that the set of points where a real polynomial and its successive derivatives have fixed signs is an interval. An easy proof, by induction on the degree of the polynomial, is based on the mean value theorem. We can translate this geometric fact under the form of algebraic identities called Generalized Taylor Formulas (GTF for short).

Let us see an example where deg(P) ≤ 4.

Example 1.3.1 Consider the general polynomial of degree 4

P (X) = c_{0}X^{4} + c_{1}X^{3} + c_{2}X^{2} + c_{3}X + c_{4},

consider the following system of sign conditions for the polynomial P and its successive derivatives with respect to the variable X:

H(X) : P (X) > 0, P^{[1]}(X) < 0, P^{[2]}(X) < 0, P^{[3]}(X) < 0, P^{[4]} > 0.

Consider also the system of sign conditions obtained by relaxing all the inequalities, except one of them, e.g., the last one:

H′(X) : P (X) ≥ 0, P^{[1]}(X) ≤ 0, P^{[2]}(X) ≤ 0, P^{[3]}(X) ≤ 0, P^{[4]} > 0.

Thom’s lemma implies that:

[ H′(a), H′(b), a < x < b] ⟹ H(x).

Put e_{1} = x−a, e_{2} = b−x. Consider the following algebraic identity in ℤ[c_{0}, …, c_{4}, a, b, x]

P (x) = P (b) − e_{2} P^{[1]}(a) − (2e_{1}e_{2} + e_{2}^{2}) P^{[2]}(a)
−(3e_{1}^{2}e_{2} + 3e_{1}e_{2}^{2} + e_{2}^{3}) P^{[3]}(b)
+(8e_{1}^{3}e_{2} + 12e_{1}^{2}e_{2}^{2} + 12e_{1}e_{2}^{3} + 3e_{2}^{4}) P^{[4]}.

This gives clearly an evidence that, when P ∈ K[X] where K is an ordered field,

[ H′(a), H′(b), a < x < b] ⟹ P (x) > 0.

One can find more information about mixed and generalized Taylor formulae in [6, 10, 11]. The important thing is that for any fixed degree, and any combination of signs for P and its derivatives (which are assumed to be fixed on the interval), there exists a corresponding GTF. We state a general result giving the existence of GTF’s.

Proposition 1.3.2 (see [10]) Let P be a polynomial of degree d in K[X] and a, b, x three variables. Let e_{1} = x − a, e_{2} = b − x. Let ε = (ϵ_{1}, …, ϵ_{d}) be any sequence in {−1, +1}. Let ϵ_{0} = 1. Then there exists an algebraic identity

P (x) = P (a_{0}) + ∑_{k=1}^{d−1} ϵ_{k}H_{k,ε}(e_{1}, e_{2})P^{[k]}(a_{k}) + ϵ_{d}H_{d,ε}(e_{1}, e_{2})P^{[d]}

where each polynomial H_{k,ε} is homogeneous of degree k with nonnegative integer coefficients, a_{k} = a if ϵ_{k}ϵ_{k+1} = 1, and a_{k} = b if ϵ_{k}ϵ_{k+1} = −1.

Moreover, if ϵ_{1} = 1, then e_{1} divides all the H_{k,ε}’s, and the coefficient of e_{1}^{k} in H_{k,ε} is nonzero. In a similar way if ϵ_{1} = −1, then e_{2} divides all the H_{k,ε}’s, and the coefficient of e_{2}^{k} in H_{k,ε} is nonzero.

Remark 1.3.3 Let P be a polynomial of degree d in K[X] and let a < b ∈ K^{rc} be such that P^{[k]}(a)P^{[k]}(b) ≥ 0 for k = 0, …, d. This gives a system of signs (σ_{0}, σ_{1}, …, σ_{d}) (σ_{i} = ±1) (σ_{k} is the sign of P^{[k]}(x) on the open interval ]a, b[ ). Let ϵ_{i} = σ_{0}σ_{i}, ε = (ϵ_{1}, …, ϵ_{d}). Then the corresponding GTF gives an algebraic certificate for the fact that sign(P (x)) = σ_{0} when a < x < b.

We now give four GTF’s in degree 3, those beginning by P (a) + e_{1}P^{[1]} · · ·. Each formula is given also with e_{1} in factor in the second part.

\begin{matrix}P (x) = & P (a) + e_{1}P^{[1]}(a) + e_{1}^{2}P^{[2]}(a) + e_{1}^{3}P^{[3]} \\ = & P (a) + e_{1} (P^{[1]}(a) + e_{1}P^{[2]}(a) + e_{1}^{2}P^{[3]}) \\ = & P (a) + e_{1}P^{[1]}(a) + e_{1}^{2}P^{[2]}(b) − (2e_{1}^{3} + e_{1}^{2}e_{2}) P^{[3]} \\ = & P (a) + e_{1} (P^{[1]}(a) + e_{1}P^{[2]}(b) − (2e_{1}^{2} + e_{1}e_{2}) P^{[3]}) \\ = & P (a) + e_{1}P^{[1]}(b) − (e_{1}^{2} + 2e_{1}e_{2}) P^{[2]}(a) − (2e_{1}^{3} + 6e_{1}^{2}e_{2} + 3e_{1}e_{2}^{2}) P^{[3]} \\ = & P (a) + e_{1} (P^{[1]}(b) − (e_{1} + 2e_{2}) P^{[2]}(a) − (2e_{1}^{2} + 6e_{1}e_{2} + 3e_{2}^{2}) P^{[3]}) \\ = & P (a) + e_{1}P^{[1]}(b) − (e_{1}^{2} + 2e_{1}e_{2}) P^{[2]}(b) + (e_{1}^{3} + 3e_{1}^{2}e_{2} + 3e_{1}e_{2}^{2}) P^{[3]} \\ = & P (a) + e_{1} (P^{[1]}(b) − (e_{1} + 2e_{2}) P^{[2]}(b) + (e_{1}^{2} + 3e_{1}e_{2} + 3e_{2}^{2}) P^{[3]}) . \end{matrix}

There are also four other GTF’s beginning by P (b) − e_{2}.P^{[1]} · · ·. They can be obtained from the first ones by swapping a and b, and replacing e_{1} and e_{2} by −e_{2} and −e_{1}

\begin{matrix}P (x) = & P (b) − e_{2}P^{[1]}(b) + e_{2}^{2}P^{[2]}(b) − e_{2}^{3}P^{[3]} \\ = & P (b) − e_{2} (P^{[1]}(b) − e_{2}P^{[2]}(b) + e_{2}^{2}P^{[3]}) \\ = & P (b) − e_{2}P^{[1]}(b) + e_{2}^{2}P^{[2]}(a) + (2e_{2}^{3} + e_{2}^{2}e_{1}) P^{[3]} \\ = & P (b) − e_{2} (P^{[1]}(b) − e_{2}P^{[2]}(a) − (2e_{2}^{2} + e_{2}e_{1}) P^{[3]}) \\ = & P (b) − e_{2}P^{[1]}(a) − (e_{2}^{2} + 2e_{2}e_{1}) P^{[2]}(b) + (2e_{2}^{3} + 6e_{2}^{2}e_{1} + 3e_{2}e_{1}^{2}) P^{[3]} \\ = & P (b) − e_{2} (P^{[1]}(a) + (e_{2} + 2e_{1}) P^{[2]}(b) − (2e_{2}^{2} + 6e_{2}e_{1} + 3e_{1}^{2}) P^{[3]}) \\ = & P (b) − e_{2}P^{[1]}(a) − (e_{2}^{2} + 2e_{2}e_{1}) P^{[2]}(a) + (e_{2}^{3} − 3e_{2}^{2}e_{1} + 3e_{2}e_{1}^{2}) P^{[3]} \\ = & P (b) − e_{2} (P^{[1]}(a) + (e_{2} + 2e_{1}) P^{[2]}(a) + (e_{2}^{2} + 3e_{2}e_{1} + 3e_{1}^{2}) P^{[3]}) . \end{matrix}

Using generalized Taylor formulae for computing the variations of the valuation v(P (x)).

Now let us see in the case of an ordered valued field how these formulae can be used in order to describe the variations of v(P (x)) when x is on the real line K^{rc}.

Example 1.3.4 Let a, b ∈ K^{rc} and assume that the signs of the derivatives of a polynomial P of degree 4 are the same in a and b, as in Example 1.3.1. If x ∈ [a, b] let x = a + t_{1}(b − a), e = b − a, e_{1} = t_{1}e, e_{2} = t_{2}e (so t_{2} = 1 − t_{1}), δ = v(e), τ_{1} = v(t_{1}), τ_{2} = v(t_{2}), ν_{0} = v(P (b)), ν_{1} = v(P^{[1]}(a)), ν_{2} = v(P^{[2]}(a)), ν_{3} = v(P^{[3]}(b)), ν_{4} = v(P^{[4]}). We rewrite the GTF as

P (x) = P (b) − e t_{2} P^{[1]}(a) − e^{2}(2t_{1}t_{2} + t_{2}^{2}) P^{[2]}(a)
−e^{3}(3t_{1}^{2}t_{2} + 3t_{1}t_{2}^{2} + t_{2}^{3}) P^{[3]}(b)
+e^{4}(8t_{1}^{3}t_{2} + 12t_{1}^{2}t_{2}^{2} + 12t_{1}t_{2}^{3} + 3t_{2}^{4}) P^{[4]}.

In the above GTF, since all terms of the sum are ≥ 0, the valuation of the sum is the minimum of valuations of the terms, so we get:

(1) If t_{1} and t_{2} are units, then τ_{1} = τ_{2} = 0 and v(P (x)) is constant equal to

v(P (x)) = min(ν_{0}, ν_{1} + δ, ν_{2} + 2δ, ν_{3} + 3δ, ν_{4} + 4δ).

(2) If t_{1} is infinitely close to 0, then τ_{1} > 0 (decreasing as t_{1} increases), τ_{2} = 0, and v(P (x)) is a priori increasing “piecewise linearly w.r.t. τ_{1}”, but in our case constant

v(P (x)) = min(ν_{0}, ν_{1} + δ, ν_{2} + 2δ, ν_{3} + 3δ, ν_{4} + 4δ).

(3) If t_{1} is infinitely close to 1, then τ_{1} = 0, τ_{2} > 0 (increasing as t_{1} increases), and v(P (x)) is increasing “piecewise linearly w.r.t. τ_{2}”

v(P (x)) = min(ν_{0}, ν_{1} + δ + τ_{2}, ν_{2} + 2δ + τ_{2}, ν_{3} + 3δ + τ_{2}, ν_{4} + 4δ + τ_{2}).

In fact here we see that this formula is true in the three cases and that only two slopes (w.r.t. the variable τ_{2}) can appear since

v(P (x)) = min(ν_{0}, min(ν_{1} + δ, ν_{2} + 2δ, ν_{3} + 3δ, ν_{4} + 4δ) + τ_{2}).

Example 1.3.5 In a similar way let us see what is given by the second GTF in degree 3

P (x) = P (a) + e_{1} P^{[1]}(a) + e_{1}^{2} P^{[2]}(b) − (2e_{1}^{3} + e_{1}^{2}e_{2}) P^{[3]}.

We assume P (a) ≥ 0, P^{[1]}(a) ≥ 0, P^{[2]}(b) ≥ 0, P^{[3]} < 0, x = a+t_{1}(b−a), e = b−a, e_{1} = t_{1}e, e_{2} = t_{2}e (t_{2} = 1 − t_{1}), δ = v(e), τ_{1} = v(t_{1}), τ_{2} = v(t_{2}), ν_{0} = v(P (a)), ν_{1} = v(P^{[1]}(a)), ν_{2} = v(P^{[2]}(b)), ν_{3} = v(P^{[3]}), and we get

P (x) = P (a) + e t_{1} P^{[1]}(a) + e^{2}t_{1}^{2} P^{[2]}(b) − e^{3} (t_{1}^{3} + t_{1}^{2}t_{2}) P^{[3]}.

(1) If t_{1} and t_{2} are units, then τ_{1} = τ_{2} = 0 and v(P (x)) is constant equal to

v(P (x)) = min(ν_{0}, ν_{1} + δ, ν_{2} + 2δ, ν_{3} + 3δ).

(2) If t_{1} is infinitely close to 1, then τ_{1} = 0, τ_{2} > 0 (increasing as t_{1} increases), and v(P (x)) is increasing “piecewise linearly w.r.t. τ_{2}”, but in our case constant

v(P (x)) = min(ν_{0}, ν_{1} + δ, ν_{2} + 2δ, ν_{3} + 3δ).

(3) If t_{1} is infinitely close to 0, then τ_{1} > 0 (decreasing as t_{1} increases), τ_{2} = 0, and v(P (x)) is increasing “piecewise linearly w.r.t. τ_{1}”,

v(P (x)) = min(ν_{0}, ν_{1} + δ + τ_{1}, ν_{2} + 2δ + 2τ_{1}, ν_{3} + 3δ + 2τ_{1}).

In fact here we see that this formula is true in the three cases and that only three slopes (w.r.t. the variable τ_{1}) can appear since

v(P (x)) = min(ν_{0}, (ν_{1} + δ) + τ_{1}, min(ν_{2} + 2δ, ν_{3} + 3δ) + 2τ_{1}).

What we have seen on our two Examples 1.3.4 and 1.3.5 is a general result, that we immediately get as a corollary of Proposition 1.3.2.

Theorem 1.3.6 Let P be a polynomial of degree d in K[X] and a < b ∈ K^{rc} such that P^{[k]}(a)P^{[k]}(b) ≥ 0 for k = 0, …, d. Let (σ_{0}, σ_{1}, …, σ_{d}) be the signs of P, P^{[1]}, …, P^{[d]} in the interval ]a, b[ (σ_{i} = ±1). Let ϵ_{i} = σ_{0}σ_{i}, ε = (ϵ_{1}, …, ϵ_{d}). Let us consider the corresponding GTF as in Proposition 1.3.2, and let us follow the notation there. Let ν_{k} = v(P^{[k]}(a_{k})) for k = 0, …, d. Recall that a_{k} = a if ϵ_{k}ϵ_{k+1} = 1, and a_{k} = b if ϵ_{k}ϵ_{k+1} = −1. Note also that ν_{k} may be infinite if k < d. If x ∈ [a, b] let x = a + t_{1}(b − a), e = b − a, t_{2} = 1 − t_{1}, δ = v(e), τ_{1} = v(t_{1}), τ_{2} = v(t_{2}).

Then for x ∈ [a, b] the valuation v(P (x)) is monotonic w.r.t. t_{1} and more precisely can be described in the following way.

(a) – If ϵ_{1} = 1 we can extract from the GTF integers k_{2}, …, k_{d} such that 1 ≤ k_{j} ≤ j and

v(P (x)) = min(ν_{0}, ν_{1} + δ + τ_{1}, ν_{2} + 2δ + k_{2}τ_{1}, …, ν_{d} + dδ + k_{d}τ_{1}).

– If ϵ_{1} = −1 we can extract from the GTF integers k_{2}, …, k_{d} such that

1 ≤ k_{j} ≤ j and

v(P (x)) = min(ν_{0}, ν_{1} + δ + τ_{2}, ν_{2} + 2δ + k_{2}τ_{2}, …, ν_{d} + dδ + k_{d}τ_{2}).

(b) So in any case the valuation v(P (x)) is – either constant (if v(P (a)) = v(P (b))),

– or increasing piecewise linearly w.r.t. τ_{1} = v(\frac{x−a}{b−a}) (if v(P (a)) > v(P (b))),

– or increasing piecewise linearly w.r.t. τ_{2} = v(\frac{b−x}{b−a}), (if v(P (a)) <

v(P (b))).

(c) Introducing

τ = τ_{1} − τ_{2} = v (\frac{t_{1}}{1 − t_{1}} )

we also get: τ_{1} = max(τ, 0) = τ^{+}, τ_{2} = max(−τ, 0) = τ^{−}, and the value v(P (x)) is monotone and piecewise linear w.r.t. τ. More precisely, we can extract from the GTF integers k_{2}, …, k_{d} such that 1 ≤ k_{j} ≤ j and

v(P (x)) = min(ν_{0}, ν_{1} + δ + τ′, ν_{2} + 2δ + k_{2}τ′, …, ν_{d} + dδ + k_{d}τ′)

where τ′ = max(ϵ_{1}τ, 0).

1.4 Constructible subsets of the real line. We introduce here the notion of (≤, ⪯)–constructible sets in the real valuative affine space. This notion corresponds to sets that are definable in the language of ordered valued fields. These sets are analogous to Zariski-constructible sets in algebraic geometry and to semialgebraic sets in real algebraic geometry.

Definition 1.4.1 Let (K, V, P) be an ordered valued field, and consider a finite family (x_{j})_{j=1,... ,m} of elements of K^{rc}. Let us call a valued sign condition (a vsc for short) for the family any condition of the following type

⋀_{j∈J} sign(x_{j}) = σ_{j} ∧ ⋀_{ℓ∈L} sign ( ∑_{j∈J, σ_{j}≠0} ℓ_{j}v(x_{j})) = σ′_{ℓ}

where J ⊆ {1, …, m}, ℓ ∈ L (L is a finite subset of ℤ^{{j : j∈J, σ_{j}≠0}}) and σ_{j}, σ′_{ℓ} ∈ {−1, 0, 1}.

Let N be a positive integer. We call an N-complete system of valued sign conditions on the family (x_{j})_{j=1,... ,m} a system of vsc’s that gives all the signs sign(x_{j}) and all the signs sign (∑_{x_{j}≠0} ℓ_{j}v(x_{j})) for all ℓ ∈ {−N, …, 0, …, N}^{{j : 1≤j≤m, x_{j}≠0}}.

An alternative definition could use sign (∑_{j∈J,} ℓ_{j}v(x_{j})) even when v(x_{j}) = ∞ for some j’s. But there should be no natural way to give a sign to an expression containing ∞ − ∞.

Definition 1.4.2 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}), and consider a finite family (P_{j})_{j=1,... ,m} of polynomials in K[X_{1}, …, X_{n}].

• The subset of R^{n} made of the \underline{x} = (x_{1}, …, x_{n}) such that the P_{j}(\underline{x})’s verify some given system of vsc’s is called a basic (≤, ⪯)–constructible set defined over (K, V, P).

• A (general) (≤, ⪯)–constructible set defined over (K, V, P) is any boolean combination S of basic (≤, ⪯)–constructible sets defined over (K, V, P). If (P_{j})_{j=1,... ,m} is a family of polynomials such that any basic component of S is defined as in the first item, we say that S is described from (P_{j})_{j=1,... ,m}.

• Let S ⊆ R^{n} be a (≤, ⪯)–constructible set. A map f : S → R^{p} is called a (≤, ⪯)–constructible map if its graph is a (≤, ⪯)–constructible subset of R^{n+p}.

Let us recall that the order topology and the valued topology are identical in a real closed valued field.

Notation 1.4.3 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). We shall use the following notations for some convex open (≤, ⪯)–constructible subsets of the real line. They are basic (≤, ⪯)–constructible sets defined over (K^{rc}, V^{rc}, P^{rc}).

𝕀^{+}(a, α) = {x ∈ R : x = a + t, 0 < t, v(t) = α}
with a ∈ K^{rc}, α ∈ Γ_{K}^{dh}.
𝕀^{−}(a, α) = {x ∈ R : x = a − t, 0 < t, v(t) = α}
with a ∈ K^{rc}, α ∈ Γ_{K}^{dh}.
𝕀^{+}(a, α, β) = {x ∈ R : x = a + t, 0 < t, α < v(t) < β}
with a ∈ K^{rc}, α < β in Γ_{K}^{dh} ∪ {±∞}.
𝕀^{−}(a, α, β) = {x ∈ R : x = a − t, 0 < t, α < v(t) < β}
with a ∈ K^{rc}, α < β in Γ_{K}^{dh} ∪ {±∞}.
𝕁^{+}(a, b, α) = {x ∈ R : x = a + t(b − a), 0 < t, v(t) = α}
with a < b ∈ K^{rc}, 0 < α ∈ Γ_{K}^{dh}.
𝕁^{−}(a, b, α) = {x ∈ R : x = b − t(b − a), 0 < t, v(t) = α}
with a < b ∈ K^{rc}, 0 < α ∈ Γ_{K}^{dh}.
𝕁^{+}(a, b, α, β) = {x ∈ R : x = a + t(b − a), 0 < t, α < v(t) < β}
with a < b ∈ K^{rc}, 0 ≤ α < β ∈ Γ_{K}^{dh} ∪ {+∞}.
𝕁^{−}(a, b, α, β) = {x ∈ R : x = b − t(b − a), 0 < t, α < v(t) < β}
with a < b ∈ K^{rc}, 0 ≤ α < β ∈ Γ_{K}^{dh} ∪ {+∞}.
𝕁(a, b) = {x ∈ R : x = a + t(b − a), 0 < t < 1, v(t) = v(1 − t) = 0}
with a < b ∈ K^{rc}.

These subsets will be called (<, ⪯)–intervals defined over (K, V, P).

Some remarks.

• The subsets of R given in definition 1.4.2 are a priori basic (≤, ⪯)–constructible sets defined over (K^{rc}, V^{rc}, P^{rc}). But they are also general (≤, ⪯)– constructible sets defined over (K, V, P): this is a consequence of Remark 3.1.2 (2).

• In 𝕁^{+}(a, b, α), 𝕁^{−}(a, b, α), 𝕁^{+}(a, b, α, β) and 𝕁^{−}(a, b, α, β) we have 0 < t < 1 (in fact t < any positive rational number) since t > 0 and v(t) > 0.

• Except when β = ∞, any (<, ⪯)–interval is closed.

• We have

\begin{aligned}]a, ∞[ & = & 𝕀^{+}(a, −∞, ∞), \\ ]a, b[ & = & 𝕁^{+}(a, b, 0, ∞) ∪ 𝕁(a, b) ∪ 𝕁^{−}(a, b, 0, ∞), \\ 𝕀^{+}(a, α, γ) & = & 𝕀^{+}(a, α, β) ∪ 𝕀^{+}(a, β) ∪ 𝕀^{+}(a, β, γ) if α < β < γ, \end{aligned}

and similar results with 𝕀^{−}, 𝕁^{+} and 𝕁^{−}.

• When t > 0, α < β ∈ Γ_{K}^{dh} ∪ {+∞}, c > 0 ∈ K and v(c) = α + β we have the following equivalences

\begin{aligned}α < v(t) < β & ⟺ & α < min(v(t), v(c/t)) & ⟺ \\ α < v(t + c/t) & ⟺ & α + v(t) < v(t^{2} + c). \end{aligned}

• Concerning 𝕁(a, b) we have

𝕁(a, b) = {x ∈ R : x = a + t(b − a), 0 < t(1 − t), v(t(1 − t)) = 0} .

• All 𝕁’s could be considered as particular cases of 𝕀’s, e.g., 𝕁^{+}(a, b, α, β) = 𝕀^{+}(a, α′, β′) with α′ = α + v(b − a) and β′ = β + v(b − a).

• We could introduce

𝕁(a, b, α) = {x ∈ R : x = a + t(b − a), 0 < t < 1, v(t/(1 − t)) = α}
with a < b ∈ K^{rc}, α ∈ Γ_{K}^{dh},
𝕁(a, b, α, β) = {x ∈ R : x = a + t(b − a), 0 < t < 1, α < v(t/(1 − t)) < β}
with a < b ∈ K^{rc}, α < β in Γ_{K}^{dh} ∪ {±∞}.

We should have 𝕁^{+}(a, b, α) = 𝕁(a, b, α), 𝕁^{−}(a, b, α) = 𝕁(a, b, −α), 𝕁^{+}(a, b, α, β) = 𝕁(a, b, α, β), 𝕁^{−}(a, b, α, β) = 𝕁(a, b, −β, −α) and 𝕁(a, b) = 𝕁(a, b, 0). An easy corollary of Theorem 1.3.6 is the following description of (≤, ⪯)–cons-

tructible subsets of the real line.

Theorem 1.4.4 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Any (≤, ⪯)–constructible set of R defined over (K, V, P) is a finite disjoint union of points in K^{rc} and of (<, ⪯)–intervals defined over (K, V, P) as in Notations 1.4.3.

Proof We give a sketch of the proof on an example. Assume that the (≤, ⪯)– constructible set S is defined from vsc’s on 3 polynomials P_{1}, P_{2}, P_{3} of degrees 5, introduce all real roots of these polynomials and of all their derivatives. Consider two consecutive roots a, b. We want to understand what S ∩]a, b[ is.

First let us see what S ∩ 𝕁^{+}(a, b, 0, ∞) looks like. We know that each sign(P_{j}(x)) is constant on ]a, b[ . Concerning the valuations v(P_{j}(x)), we know from Examples 1.3.4 and 1.3.5 and Theorem 1.3.6 that they are piecewise linear functions of τ_{1} = v(x − a)/v(b − a), e.g., of the following forms

v(P_{1}(x)) = min(μ_{0}, μ_{1} + τ_{1}, μ_{2} + 2τ_{1}),
v(P_{2}(x)) = min(η_{0}, η_{1} + τ_{1}, η_{3} + 3τ_{1}),
v(P_{3}(x)) = min(λ_{0}, λ_{1} + τ_{1}, λ_{2} + 2τ_{1}, λ_{4} + 4τ_{1}).

Note that τ_{1} varies on ]0, +∞[ . These piecewise linear functions have polygonal graphs inside (Γ_{K}^{dh}∩]0, +∞[ ) × Γ_{K}^{dh}. It is possible to compute the vertices of these three polygonal graphs. E.g., if λ_{4} < λ_{1} < λ_{0} and 3λ_{2} > 2λ_{1} + λ_{4} we have two vertices on the polygonal graph of v(P_{3}) at the points with coordinates

\begin{matrix}τ_{1,1} = β_{1} = (λ_{1} − λ_{4})/3, & v(P_{3}(x)) = λ_{1} + β_{1} = λ_{4} + 4β_{1}, \\ τ_{1,2} = β_{2} = λ_{0} − λ_{1}, & v(P_{3}(x)) = λ_{0} = λ_{1} + β_{2}. \end{matrix}

All these vertices give a finite number of valuations for τ_{1}: α_{1} < ⋯ < α_{n}. Let α_{0} = 0, α_{n+1} = ∞. On each 𝕁^{+}(a, b, α_{i}, α_{i+1}) (0 ≤ i ≤ n) and on each 𝕁^{+}(a, b, α_{i}) (1 ≤ i ≤ n), we know that each v(P_{j}(x)) (1 ≤ j ≤ 3) is a fixed “affine function” of τ_{1}. So, the same is true for any linear combination

ℓ_{1}v(P_{1}(x)) + ℓ_{2}v(P_{2}(x)) + ℓ_{3}v(P_{3}(x)),

and we can compute the valuation τ_{1} for which such an expression changes sign.

So the intersection S ∩ 𝕁^{+}(a, b, 0, ∞) is a finite disjoint union of 𝕁^{+}(a, b, α, β) and 𝕁^{+}(a, b, α) subsets.

In a similar way S ∩ 𝕁(a, b) is either empty or equal to 𝕁(a, b), and S ∩ 𝕁^{−}(a, b, 0, ∞) is a finite disjoint union of 𝕁^{−}(a, b, α, β) and 𝕁^{−}(a, b, α) subsets.

Finally the intersection of S with the final (resp. initial) open interval is computed in a similar way as a finite union of 𝕀^{+} (resp. 𝕀^{−}) intervals.

2 Computing in the real closure of an ordered valued field

2.1 Codes à la Thom and valuations in the value group. The real closure K^{rc} of an ordered field (K, P) is unique up to unique (K, P)–isomorphism. This fact allows us to give an explicit construction of the real closure K^{rc} (this is “well-known” from Tarski or even from Sturm and Sylvester, for a fully constructive proof see [7]).

E.g., it is possible to describe any element x of K^{rc} by a so-called code à la Thom (see [3, 4]):

Definition 2.1.1 A pair (P, σ) where P ∈ K[X] is a monic polynomial of degree d and σ = (σ_{1}, …, σ_{d−1}) ∈ {1, −1}^{d−1} codes the root x of P in K^{rc} when one has

P (x) = 0  and  σ_{i} · P^{(i)}(x) ≥ 0 for i = 1, …, d − 1.

The pair (P, σ) is called a code à la Thom (over K) for x.

There are algorithms that use only the algebraic structure of (K, P) and give the codes à la Thom corresponding to the roots of P in K^{rc}. It is possible to make explicit algebraic computations and sign’s tests for such elements that are coded à la Thom. See e.g., [3, 4] or Proposition 2.4.2.

On the other hand, the Newton polygon algorithm allows us to determine the valuation v(x) for any x in the algebraic closure of K. How can we match these algorithms?

2.2 Three basic computational problems in the real closure of an ordered valued field. Consider an ordered valued field (K, V, P). Since its real closure (with valuation) is determined up to unique (K, V, P)-isomorphism, the following computational problems makes sense:

Computational Problem 1 Let (K, V, P) be an ordered valued field. Input: A code à la Thom (P, σ) over K for an element x of K^{rc}. Output: The valuation v(x) of x in Γ_{K}^{dh} ∪ {+∞}. More precisely, compute some a ∈ K and a positive integer n such that n × v(x) = v(a).

Remark 2.2.1 Assume that the leading coefficient of P ∈ V[X] is a unit. The real zeroes of P are in V^{rc}. Let us denote by \overline{x} the residue in \overline{K^{rc}} of the zero x and by \overline{P} the residue in \overline{K}[X] of the polynomial P. Then it is clear that (\overline{P} , σ) is a code à la Thom over \overline{K} for \overline{x} since the residual field \overline{K^{rc}} can be identified with the real closure \overline{K}^{rc} of \overline{K}.

More generally, we can ask for algorithms solving general existential problems.

Computational Problem 2 Let (K, V, P) be an ordered valued field, and consider a finite family of polynomials, (F_{j})_{j=1,... ,m} in K[X]. Let (x_{h})_{h=1,... ,p} be the ordered family of the zeroes of the (F_{j})’s in K^{rc}. Recall that the number p and all the signs sign(F_{j}(x)), for x equal to some x_{h} or inside some corresponding open interval, can be determined by computations in the ordered field (K, P). Input: The family (F_{j})_{j=1,... ,m}. Output: All the valuations v(F_{j}(x_{h})) (h = 1, …, p) and v(x_{h+1} − x_{h}) (h = 1, …, p − 1) in Γ_{K}^{dh} ∪ {+∞}.

Computational Problem 3 Let (K, V, P) be an ordered valued field. Input: A finite family (F_{j})_{j=1,... ,m} in K[X]. A finite family (ℓ_{k})_{k=1,... ,r} of elements of ℤ^{m}. Output: All occurring systems of valued sign conditions of the following type for the family (F_{j}(x))_{j=1,... ,m} when x ∈ K^{rc}:

((sign(F_{j}(x)))_{j=1,... ,m}, (sign ( ∑_{j∈{1,... ,m}, F_{j}(x)≠0} ℓ_{k,j} v(F_{j}(x))))_{k=1,... ,r}) .

Remark 2.2.2 Assume that the family is stable under derivation. From Theorem 1.3.6 (see e.g., the proof of Theorem 1.4.4) it is clear that Computational Problem 3 can be solved by using the solution of Computational Problem 2. In fact we can describe in a finite way all occurring lists

( (sign(F_{j}(x)))_{j=1,... ,m}, (v(F_{j}(x)))_{j=1,... ,m} )

when x ∈ K^{rc}: for x on any (<, ⪯)–interval I used in the proof of Theorem 1.4.4 we have v(F_{j}(x)) = μ_{I,j} + m_{I,j}v(t) where t is either (x − x_{h})/(x_{h+1} − x_{h}), or (x_{h+1} − x)/(x_{h+1} − x_{h}), or x_{1} − x or x − x_{p}.

2.3 Solving the first problem.

Algorithm RCVF1 solving Problem 1. Recall that (P, σ) is a code à la Thom for a root x of P ∈ K[X]. We can assume w.l.o.g. that P (0) ≠ 0, x > 0 (else replace P by P (−X)) and that P is monic. Let (x_{i})_{i=1,... ,d} be the roots of P in K^{ac}. Using the Newton Polygon algorithm, we compute the multiset [ v(x_{i}) | i = 1, …, n]. So we can express the set of valuations v(x_{i}) as (v(c_{j})/n_{j})_{j=1,... ,r} for some r-tuple (c_{j}, n_{j})_{j=1,... ,r} with c_{j} > 0 in K, n_{j} ∈ ℕ and v(c_{j})/n_{j} < v(c_{j+1})/n_{j+1} for j = 1, …, r − 1.

Consider the LCM n of denominators n_{j} and “replace each x_{i} by z_{i} = x_{i}^{n}”: i.e., compute Q(X) = ∏_{i}(X − z_{i}) and compute a code à la Thom (Q, σ′) for z = x^{n}. Let b_{j} = c_{j}^{n/n_{j}}. Then v(b_{j}) = (n/n_{j})v(c_{j}) for j = 1, …, r and

v(b_{1}) < ⋯ < v(b_{r}).

So we have also

b_{1} > ⋯ > b_{r} > 0.

By rational computations in (K, P) we can settle one of the three following inequalities in K^{rc}

z ≥ b_{1},
b_{j} ≥ z ≥ b_{j+1} with some j ∈ {1, …, r − 1},
b_{r} ≥ z > 0.

In the first case we conclude that v(z) = v(b_{1}). In the last case v(z) = v(b_{r}). In the remaining case we know that

v(b_{j}) ≤ v(z) ≤ v(b_{j+1}) so v(z) = v(b_{j}) or v(z) = v(b_{j+1}).

We have to find the exact valuation. Consider c ∈ P verifying

0 < v(c) ≤ min (v (\frac{b_{j}}{b_{j−1}} ) , v (\frac{b_{j+1}}{b_{j}} )) if j > 1

0 < v(c) = v (\frac{b_{2}}{b_{1}} ) if j = 1

(if j > 1, c can be chosen as b_{j}/b_{j−1} or b_{j+1}/b_{j}). Next consider the linear fractional change of variable

y ⟼ φ(y) = \frac{y}{1 + cy^{2}}

We have

— If v(y) ≥ 0 then v(φ(y)) = v(y).

— If v(y) ≤ −v(c) then, letting y′ = 1/y we get

v(y′) ≥ v(c) > 0, φ(y) = \frac{y′}{c + y′^{2}} and v(φ(y)) = v(y′) − v(c) ≥ 0.

So the monic polynomial

R(Y) = ∏_{i} (Y − φ (\frac{z_{i}}{b_{j}} ))

has coefficients in V. Moreover v(z/b_{j}) ≥ 0, so φ(z/b_{j}) is a unit iff v(b_{j}) = v(z) since v(φ(z/b_{j})) = v(z/b_{j}).

We can compute a code à la Thom (R, σ′′) for φ(z/b_{j}). This gives a code à la Thom (\overline{R}, σ′′) for \overline{φ(z/b_{j})} (i.e., φ(z/b_{j}) considered as an element of \overline{K}^{rc}). Finally we test whether this code is verified by \overline{0} (which is a root of \overline{R}). In case of negative answer then v(z) = v(b_{j}). Otherwise v(z) = v(b_{j+1}).

Remarks 2.3.1

1) In a more explicit view, we should ask for computing two nonnegative elements a and b of K and an integer n such that a ≤ |x|^{n} ≤ b and v(a) = v(b).

2) Clearly algorithm RCVF1 allows us to run sure computations inside (K^{rc}, V^{rc}, P^{rc}) when we know how to compute inside (K, V, P).

2.4 Solving the second problem. First we recall the Cohen-Hörmander algorithm for ordered fields (see e.g., [1] chapter 1).

Definition 2.4.1 Let (K, P) be an ordered field and (F_{j}) a finite family of univariate polynomials in K[X]. A complete tableau of signs for the family (F_{j}) is the following discrete data T:

• The ordered list (x_{k})_{k=1,... ,r} of all the roots of all the F_{j}’s in K^{rc}.

• The signs (∈ {−1, 0, +1}) of all the F_{j}’s at all the x_{k}’s.

• The signs of all the F_{j}’s in each interval ]−∞, x_{1}[ , ]x_{k}, x_{k+1}[ (1 ≤ k ≤ r−1)

and ]x_{r}, +∞[ .

We call an x_{k} a point of the tableau T. Similarly an interval ] − ∞, x_{1}[ or ]x_{k}, x_{k+1}[ or ]x_{r}, +∞[ is called an interval of the tableau T.

In this tableau x_{k} is merely a name for the corresponding root, it may be coded by the number k or in another way.

Proposition 2.4.2 (Cohen-Hörmander’s algorithm for computing the complete tableau of signs for a finite family of univariate polynomials) Let (K, P) be an ordered subfield of a real closed field (R, P_{R}). Let L = (F_{1}, …, F_{k}) be a list of polynomials in K[Y]. Let L′ be the family of polynomials generated by the elements of L and by the operations P ↦ P′ and (P, Q) ↦ Rem(P, Q) for deg(P) ≥ deg(Q) ≥ 1. Then L′ is finite and one can compute the complete tableau of signs for L′ in terms of the following data:

• the degree of each polynomial in the family L′,

• the diagrams of operations P ↦ P′ and (P, Q) ↦ Rem(P, Q),

• the signs of constants ∈ L′.

Proof Let us remark that in this algorithm the zero polynomial can appear in L′ as a remainder Rem(P, Q) where deg(P) ≥ deg(Q) ≥ 1. The degree of the zero polynomial is −1.

The list L′ is finite: one makes systematically the operation “derivation of every previously obtained polynomial” and “remainders of all previously obtained couple of polynomials”, and one gets a finite family at the end since degrees are decreasing.

Let us number the polynomials in L′ with an order compatible with the order on the degrees. Let L′_{m} be the subfamily of L′ made of polynomials numbered from 1 to m. This family is obviously stable under the operations “derivation” and “remainder by a division” which decrease strictly the degrees. Denote lastly by T_{m} the corresponding complete tableau of signs.

We are going to prove, by induction on m, that the complete tableau of signs of the polynomials in the family L′_{m} can be obtained by using only the authorized informations. As long as polynomials are of degree 0, this is clear. Suppose it is true up to m. Let P be the polynomial of number m + 1 in L′. On each interval of T_{m}, the polynomial P is strictly monotonic. Every point a of T_{m} is either +∞, or −∞, or a root of a certain polynomial Q with number ≤ m, and in this case, if R = Rem(P, Q), we have P (a) = R(a). The sign of P (a) is hence known in every case from the authorized informations. This allows us to know on which open intervals of T_{m} the polynomial P has a root in R. Let x be such a root of P on one of these open intervals I = ]a, b[ . If Q is a polynomial of number ≤ m in P, its sign on the interval I is known. This means we know its sign at the point x, and on intervals ]a, x[ and ]x, b[. With respect to P, its signs on ]a, x[ and on ]x, b[ are also known since P is strictly monotonic on the interval. The complete tableau of signs for L′_{m+1} is thus known from the authorized informations and the complete tableau of signs for L′_{m}.

In this algorithm we remark that each zero of the tableau is obtained with a Thom’s encoding.

An extension of previous algorithm will solve Problem 2. First we give a valued version for the complete tableau of signs.

Definition 2.4.3 Let (K, V, P) be an ordered valued field and (F_{j})_{j∈J} a finite family of univariate polynomials in K[X]. A complete tableau of vsc’s for the family (F_{j}) is the following data T:

• The ordered list (x_{k})_{k=1,... ,r} of all the roots of all the F_{j}’s in K^{rc}.

• The complete tableau of signs for the family (F_{j})_{j∈J}.

• All the valuations v(x_{k+1} − x_{k}) (k = 1, …, r − 1).

• All the valuations v(F_{j}(x_{k})) (j ∈ J, k = 1, …, r).

Algorithm RCVF2 solving Problem 2. A first possibility is to use algorithm RCVF1. We think that it is interesting to indicate another possibility which goes in the same spirit as the Cohen-Hörmander algorithm for ordered fields. This gives us also simple proofs for theorems in sections 3 and 4. Call (P_{j}) the list L′ in Proposition 2.4.2. Call (x_{m,k})_{k=1,... ,r_{m}} the ordered list of all roots of L′_{m} = (P_{j})_{j=1,... ,m}. We replace in the proof of Proposition 2.4.2 the complete tableau of signs T_{m} of L′ by S_{m} = T_{m} ∪ V_{m} where V_{m} collects the valuations v(P_{j}(x_{m,k})) (j ∈ {1, …, m}, k ∈ {1, …, r_{m}}) and v(x_{m,k+1} − x_{m,k}) (k ∈ {1, …, r_{m} − 1}.)

Suppose we have done the job up to m. Let P = P_{m+1} be the polynomial of index m + 1 in L′. The tableau T_{m+1} is computed as in Proposition 2.4.2. It remains to compute missing informations in V_{m+1}.

At every root a = x_{m,k} of a polynomial Q = P_{ℓ} with index ℓ ≤ m, if R = Rem(P, Q), we have P (a) = R(a) and R is in L′_{m}, so the valuation v(P (a)) is known from V_{m}.

Let x = a+t_{1}(b−a) be a root of P on an open interval I = ]x_{m,k}, x_{m,k+1}[ = ]a, b[ of T_{m}. In order to compute all the v(P_{j}(x))_{j=1,... ,m} it is sufficient to compute v(t_{1}) = τ_{1} and v(t_{2}) = τ_{2} (t_{2} = 1 − t_{1}): Theorem 1.3.6 says us how to get the valuations v(P_{j}(x))_{j=1,... ,m} from V_{m}, τ_{1} and τ_{2}.

In order to compute τ_{1} = v(t_{1}) we use a GTF that expresses P (x) = P (a + t_{1}(b − a)) = 0 as

P (a) + t_{1} · (∑_{j=1}^{d} ϵ_{j} · e^{j} · G_{j,ε}(t_{1}, t_{2}) · P^{[j]}(a_{j})) (a_{j} = a or b)

where e = b − a, t_{1} · G_{j,ε}(t_{1}, t_{2}) = H_{j,ε}(t_{1}, t_{2}) and

sign(ϵ_{j}P^{[j]}(a_{j})) = sign(−P (a)) (1 ≤ j ≤ d).

Moreover, the valuations v(P (a) = ν, v(P^{[j]}(a_{j})) = ν_{j} and δ = v(b − a) are known. From the properties of H_{j,ε}, we know that G_{j,ε}(t_{1}, t_{2}) is a unit if τ_{1} = 0, so its valuation in Γ_{K}^{dh} ∪ {+∞} depends only on τ_{1}. So we get

v(P (a)) = ν = min(ν_{1} + δ + τ_{1}, ν_{2} + 2δ + k_{2}τ_{1}, …, ν_{d} + dδ + k_{d}τ_{1})

(τ_{1} ≥ 0, and some ν_{k}’s may be infinite). The right hand side is an increasing piecewise linear function of τ_{1} so we have a unique and explicit solution τ_{1}. With μ_{i} = ν_{i} + iδ we precisely get

τ_{1} = max (ν − μ_{1}, \frac{ν − μ_{2}}{k_{2}} , …, \frac{ν − μ_{d}}{k_{d}} ) .

Finally τ_{2} is computed analogously and we can fill up V_{m+1}.

Remark also that if x is on the last interval ]x_{m,r_{m}}, +∞[ = ]a, +∞[ of T_{m}, we can compute v(x − a) in a similar way by using the usual Taylor formula.

Definition 2.4.4 In an additive divisible ordered group G we consider terms built from variables α_{j} by ℚ-linear combinations and by using the operations min and max. We call such a term a ℚ-semilinear term. The function defined by such a term is called a ℚ-semilinear function of the α_{j}’s.

We get the following theorem, similar to Proposition 2.4.2.

Theorem 2.4.5 (An algorithm à la Cohen-Hörmander for computing the complete tableau of vsc’s for a finite family of univariate polynomials) Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let L = (F_{1}, …, F_{k}) be a list of polynomials in K[Y]. Let L′ be the (finite) family of polynomials generated by the elements of L and by the operations P ↦ P′ and (P, Q) ↦ Rem(P, Q) for deg(P) ≥ deg(Q) ≥ 1. Call (c_{j}) the list of constants ∈ L′.

Then one can compute the complete tableau of vsc’s for L′ in terms of the following data:

• the degree of each polynomial in the family,

• the diagrams of operations P ↦ P′ and (P, Q) ↦ Rem(P, Q) in L′,

• the signs sign(c_{j}),

• the valuations v(c_{j}). Moreover, all the valuations v(x_{k+1} −x_{k}) and all the valuations v(P_{j}(x_{k})) are given as fixed ℚ-semilinear functions of the v(c_{j})’s: each such ℚ-semilinear function is a fixed ℚ-semilinear term (in the “variables” v(c_{j})’s) that depends only on the complete tableau of signs of L′.

Proof This theorem is an extension of Proposition 2.4.2. The proof is similar. In fact we get all results by a close inspection of Algorithm RCVF2.

2.5 Solving the third problem.

Algorithm RCVF3 solving Problem 3. We run Algorithm RCVF2 and we apply Theorem 1.3.6: see Remark 2.2.2.

Definition 2.5.1 Let (F_{j})_{j∈J} be a finite family of univariate polynomials in K[X] (where (K, V, P) is an ordered valued field). We assume the family to be stable under derivation. Let M be a positive integer.

An M-complete tableau of vsc’s for the family (F_{j}) is the following discrete data T:

• The ordered list (x_{k})_{k=1,... ,r} of all the roots of all the F_{j}’s in K^{rc}.

• For each k = 1, …, r, the M-complete system of vsc’s (see Definition 1.4.1) for the family (F_{j}(x_{k}))_{j∈J}.

• For each k = 1, …, r − 1 – The M-complete system of vsc’s for the family (F_{j}(x))_{j∈J} for x ∈

𝕁(x_{k}, x_{k+1}).

– A partition of 𝕁^{+}(x_{k}, x_{k+1}, 0, ∞) as a finite union of 2n_{k} +1 (<, ⪯)– intervals

⋃_{i=0,n_{k}} 𝕁^{+}(x_{k}, x_{k+1}, α_{k,i}, α_{k,i+1}) ∪ ⋃_{i=1,n_{k}} 𝕁^{+}(x_{k}, x_{k+1}, α_{k,i}),

(where α_{k,0} = 0 and α_{k,n_{k}+1} = ∞) and for each (<, ⪯)–interval A of this partition, the M-complete system of vsc’s for the family (F_{j}(x))_{j∈J} which is the same one for any x ∈ A.

– A similar data concerning 𝕁^{−}(x_{k}, x_{k+1}, 0, ∞).

• Similar data concerning 𝕀^{−}(x_{1}, −∞, ∞) and 𝕀^{+}(x_{r}, −∞, ∞).

In this tableau the α_{k,i}’s (0 < α_{k,1} < ⋯ < α_{k,n_{k}} < ∞) are purely formal and n_{k} is the only relevant information concerning α_{k,1}, …, α_{k,n_{k}}.

We now state a result that precises the output of Algorithm RCVF3.

Theorem 2.5.2 (An algorithm à la Cohen-Hörmander for computing an Mcomplete tableau of vsc’s for a finite family of univariate polynomials) Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let M be a positive integer. Let L = (F_{1}, …, F_{k}) be a list of polynomials in K[Y]. Let L′ be the family of polynomials generated by the elements of L and by the operations P ↦ P′ and (P, Q) ↦ Rem(P, Q) for deg(P) ≥ deg(Q) ≥ 1. Call (c_{j}) the list of constants ∈ L′.

Then one can compute the M-complete tableau of vsc’s for L′ in terms of the following data:

• the degree of each polynomial in the family,

• the diagrams of operations P ↦ P′ and (P, Q) ↦ Rem(P, Q) in L′,

• the N-complete system of vsc’s for the family (c_{j}), where N is an integer depending only on M and on the list of degrees in L.

3 Quantifier elimination algorithms

3.1 Parametrized computations. Algorithms RCVF2 and RCVF3 are uniform: they can be run when coefficients in the initial data are polynomials in other variables which are called parameters (instead of being in the base field).

A case by case discussion appears, and the straight-line algorithm is replaced by a branching one.

We describe this situation as a parametrized algorithm dealing with parametrized univariate polynomials.

Theorem 3.1.1 (parametrized version of Theorem 2.4.5) Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let L = (F_{1}, …, F_{k}) be a list of parametrized univariate polynomials of degrees d_{1}, …, d_{k} in some variable X. Let us run the algorithm RCVF2 and let us open two branches in the computation any time we have to know if a given element is zero or nonzero when computing a remainder. Moreover, replace remainders by pseudoremainders in order to avoid denominators.

Consider the family (c_{j}) of all “constants” in all L′’s that appear at the leaves of the tree (these constants are K–polynomials in the parameters).

Finally consider that the computed valuations v(x_{k+1} − x_{k}) and v(P_{j}(x_{k})) at any leave of the tree are given as ℚ-semilinear functions of the “variables” v(c_{j})’s.

Then this global parametrized algorithm is finite and therefore gives a finite number of possibilities for its output: the complete tableau of vsc’s for L.

More precisely when the signs of the “constants” c_{j}’s are known, the complete tableau of signs is known and all the valuations v(x_{k+1} − x_{k}) and v(P_{j}(x_{k})) are given as explicit ℚ-semilinear functions in the “variables” v(c_{j})’s.

Proof The proof of Proposition 2.4.2 (Cohen-Hörmander algorithm) works as well in the parametrized case. In each branch so created, the proof of Theorem 2.4.5 works as well.

Remarks 3.1.2

1) An important case is obtained when all coefficients of the F_{i}’s are independent parameters and (K, V, P) = (ℚ, ℚ, ℚ^{≥0}). This “generic case” gives the complete description of all situations occurring with a fixed number of polynomials of known degrees.

2) Another interesting particular case is the following one, with only one parameter subject to certain constraints. We start with a list of polynomials L = (F_{1}, …, F_{k}) in K[Y]^{n}, we get an extended list L′ and the complete tableau of signs. Let a and b be two consecutive roots in this tableau. Now we want to make computations with an element x of the interval ]a, b[ . Consider x as a parameter verifying some sign constraints, namely the Thom’s sign conditions that define ]a, b[ . We add the polynomial Y − x to L and we run the parametrized version of RCVF2. Only one root is added: x. The new polynomials appearing are only “constants” of the form Q(x) (where Q is in L′). The process go on only trough one branch. We get the following result: the valuations v(x − a) and v(b − x) are given as ℚ-semilinear functions of some v(Q(x))’s. From this we also get a similar result concerning v(x − x_{j}) where x_{j} is any root in the tableau. Naturally, there is also a parametrized version for this result.

Similarly we have a parametrized version of Theorem 2.5.2.

Theorem 3.1.3 (parametrized version of Theorem 2.5.2) Let L = (F_{1}, …, F_{k}) be a list of parametrized univariate polynomials of degrees d_{1}, …, d_{k} in some variable X. Let M be a positive integer. Let us run the algorithm RCVF2 and let us open two branches in the computation any time we have to know if a given element is zero or nonzero when computing a remainder. Moreover, replace remainders by pseudoremainders in order to avoid denominators. Let us call (c_{j}) the family of all “constants” in all L′’s that appear at the leaves of the tree (these constants are K–polynomials in the parameters).

Finally when applying Theorem 1.3.6 in order to get the output of RCVF3 from the one of RCVF2, we open three branches any time we have to know the sign of some ℤ-linear combination of v(c_{j})’s.

Then this global parametrized algorithm is finite and therefore gives a finite number of possibilities for its output: the M-complete tableau of vsc’s for L.

Moreover, these outputs depend on the following data:

• the signs of the “constants” c_{j}’s,

• the sign test inside a finite subset of the subgroup generated by the v(c_{j})’s; which are exactly divisibility tests between monomials in the c_{j}’s).

Remark 3.1.4 Since the computation in the previous theorem is purely formal, certain systems of conditions corresponding to the data given by the two last items may be impossible. If we want to know what are these impossible systems, we have to use the quantifier elimination algorithm given in Theorem 3.2.2. Nevertheless, one can verify that there is no circular argument.

3.2 Quantifier elimination. We now give some corollaries of previous computations for quantifier elimination. We recall that these results are well known, see e.g., [2].

We consider the first order theory of real closed valued fields based on the language of ordered fields (0, 1, +, −, ×, =, ≤) to which we add the predicate x ⪯ y. So, all constants and variables represent elements in K (this corresponds to our previously explained computability assumptions).

Here is a corollary of Theorem 3.1.3.

Theorem 3.2.1 Let Φ(\underline{a}, \underline{x}) be a quantifier free formula in the first order theory of real closed valued fields. We view the a_{i}’s as parameters and the x_{j}’s as variables. Then one can give a quantifier free formula Ψ(\underline{a}) such that the two formulae ∃\underline{x} Φ(\underline{a}, \underline{x}) and Ψ(\underline{a}) are equivalent in the formal theory. (The terms appearing in the formulae Φ and Ψ are ℤ–polynomials in the parameters, and, in the case of Φ, also in the variables.)

Proof Use recursively Theorem 3.1.3 and eliminate the x_{j}’s one after the other.

We also get the following corollary.

Theorem 3.2.2 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Assume that the sign test and the divisibility test are explicit inside (K, V, P). Then there is a uniform quantifier elimination algorithm for the first order theory of real closed valued fields extending (K, V, P).

3.3 An abstract form of quantifier elimination. An abstract form of Theorem 3.1.3 is the following theorem, that was given the first time by M.J. De la Puente in [9].

First, we need some definitions of the abstract objects.

Definition 3.3.1 Let us denote the real-valuative spectrum of a commutative ring A by SpervA: an element of SpervA is given by a ring homomorphism φ from A to a real closed valued field K, and two such homomorphisms φ, φ′ define the same element of SpervA iff there exists an isomorphism of ordered valued fields ψ : R → R′ such that ψ ∘ φ = φ′, where R and R′ are the real closed valued fields generated by φ(A) and φ′(A). Alternatively, an element of SpervA is given by a prime ideal Q of A and a structure of ordered valued field upon the fraction field of A/Q. A constructible subset of SpervA is by definition a boolean combination of elementary constructible subsets U_{x} := {φ ∈ SpervA : φ(x) > 0} and V_{x,y} := {φ ∈ SpervA : φ(x) ⪯ φ(y)}, where x, y ∈ A.

Theorem 3.3.2 The canonical mapping from SpervA[X] to SpervA transforms any (≤, ⪯)–constructible subset into a (≤, ⪯)–constructible subset.

Proof A (≤, ⪯)–constructible subset in Sperv(B) is a finite union of basic (≤, ⪯)–constructible subsets, that are defined as

\begin{matrix}\{φ ∈ Sperv(B) : \\ ⋀_{i} φ(a_{i}) = 0 ∧ ⋀_{j} φ(b_{j}) > 0 ∧ ⋀_{k} v(φ(c_{k})) = v(φ(d_{k})) ∧ ⋀_{ℓ} v(φ(e_{ℓ})) > v(φ(f_{ℓ}))\} \end{matrix}

where conjunctions are finite and all elements are in B. Searching the canonical image of a basic constructible subset S of SpervA[X] (defined by elements a_{i}, b_{j}, c_{k}, d_{k}, e_{ℓ}, f_{ℓ} in A[X]) inside SpervA, is the same thing that analyzing the conditions on the coefficients of the polynomials a_{i}, b_{j}, c_{k}, d_{k}, e_{ℓ}, f_{ℓ} allowing the existence of an x where the defining conditions of S are verified. So Theorem 3.1.3 gives the answer.

Another consequence of Theorem 3.1.3 is a relativized version of Theorem 3.3.2. This generalization is obtained by giving some constraints on the ring homomorphism φ from A to a real closed valued field K. We give e.g., a subring B of A, an ideal M of B, a multiplicative monoid S in A and a semi ring P in A (P + P ⊆ P, P × P ⊆ P). We want to allow only homomorphisms ϕ (from A or A[X] to a real closed valued field) verifying that ϕ(B) is in the valuation ring, ϕ(M) is in the maximal ideal, elements of ϕ(S) are nonzero and elements of ϕ(P) are nonnegative. If we write C the constraints (B, M, S, P) and if we write Sperv(A, C) the part of SpervA satisfying the constraints, we get: the canonical mapping from Sperv(A[X], C) to Sperv(A, C) transforms any (≤, ⪯)–constructible subset in a (≤, ⪯)–constructible subset.

In [9] the relativized version is settled with one constraint B.

4 Constructible subsets in the real valuative affine space

4.1 Tarski-Seidenberg-Chevalley. We now give a geometric form for Theorems 3.1.3 and 3.2.2.

Theorem 4.1.1 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let π the canonical projection from R^{n+r} onto R^{n}. Let S ⊆ R^{n+r} be any (≤, ⪯)–constructible set defined over (K, V, P). Assume that the sign test and the divisibility test are explicit inside the ring generated by the coefficients of the polynomials that appear in the definition of S. Then a description of the projection π(S) ⊆ R^{n} can be computed in a uniform way by an algorithm that uses only rational computations, sign tests and divisibility tests.

In particular, the complexity of a description of π(S) is explicitly bounded in terms of the complexity of a description of S.

Here rational computations mean computations in the ring generated by the coefficients of the polynomials occurring in the description of S. A description of S is a quantifier free formula in disjunctive normal form describing S. The complexity of such a description of S can be defined as a 5-tuple (n, d, k, ℓ, m) where n is the number of variables, d is the maximum of the degrees, k is the number of polynomials, ℓ is the number of ∨ and m is the bound for the numbers of ∧ inside a disjunct.

Corollary 4.1.2 Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let S ⊆ R^{n} be a (≤, ⪯)–constructible set and let f : S → R^{p} be a (≤, ⪯)–constructible map.

• The interior and the adherence of S inside R^{n} for the order topology are (≤, ⪯)–constructible sets.

• f(S) ⊆ R^{p} is a (≤, ⪯)–constructible set.

• Let T be a (≤, ⪯)–constructible set containing f(S) and let g : T → R^{q} be a (≤, ⪯)–constructible map. Then g ∘ f is a (≤, ⪯)–constructible map.

• Let T′ ⊆ R^{p} be a (≤, ⪯)–constructible set. Then f^{−1}(T′) ⊆ R^{n} is a (≤, ⪯)– constructible set.

4.2 Stratifications and applications. We think that the results of this section could allow to get most of the results obtained by Frank Mausz in his Doctoral dissertation [8] with a different approach.

Łojaziewicz stratification à la Cohen-Hörmander

We recall here a result about stratifying families ([1] chapter 9).

Definition and notation 4.2.1 Consider a general monic polynomial of degree d as a point of R^{d}. Let σ = (σ_{1}, …, σ_{d}) ∈ {−1, +1}^{d}. Let

U_{σ} = {P ∈ R^{d} : ∃x ∈ R (P (x) = 0 ∧ ⋀_{i=1}^{d} sign(P^{(i)}(x)) = σ_{i})} .

It is easily seen that U_{σ} is a connected open semialgebraic subset of R^{d} (see e.g., [5]) and that

\overline{U_{σ}} = \{P ∈ R^{d} : ∃x ∈ R (P (x) = 0 ∧ ⋀_{i=1}^{d} sign(P^{(i)}(x)) ∈ \{σ_{i}, 0\})\} .

For P ∈ U_{σ} we call ρ_{σ}(P) the zero which is coded à la Thom by (P, σ). Then P ↦ ρ_{σ}(P) is Nash on U_{σ} and admits a continuous semialgebraic extension on \overline{U_{σ}}, that we note also by ρ_{σ}. Such a function will be called a Thom’s root function, or simply a root function.

More generally, if φ : R^{k−1} → R^{d} is a polynomial function, we can consider ρ_{σ} ∘ φ as defined over φ^{−1}(\overline{U_{σ}}). We also call such a function a root function. This function is Nash over φ^{−1}(U_{σ}). If f(x_{1}, …, x_{k}) = φ(x_{1}, …, x_{k−1})(x_{k}) is the corresponding monic polynomial in k variables, we denote ρ_{σ} ∘ φ by ρ_{σ}(f).

Finally if a polynomial g ∈ K[x_{1}, …, x_{k}] = K[x_{1}, …, x_{k−1}][x_{k}] has a leading coefficient w.r.t. x_{k} which is a nonzero element c of K, we say that g is quasi monic in x_{k}, and we let ρ_{σ}(g) = ρ_{σ}(g/c).

For more details about root functions see [5].

Theorem 4.2.2 ([1] chap. 9) Let (K, P) be an ordered subfield of a real closed field (R, P_{R}). Let g_{1}, …, g_{s} be nonzero polynomials in K[x_{1}, …, x_{n}]. After a suitable linear change of variables there exists a family of polynomials

(f_{i,j})_{i=1,... ,n;j=1,... ,ℓ_{i}}

with the following properties (we will continue denoting the new variables by x_{i}).

(1) First we have – (g_{1}, …, g_{s}) ⊆ (f_{n,j})_{j=1,... ,ℓ_{n}}

– Each f_{k,j} is a nonzero polynomial in K[x_{1}, …, x_{k}] which is quasimonic in x_{k}.

– For each index k the family (f_{k,j})_{j=1,... ,ℓ_{k}} is stable under derivation w.r.t. x_{k} (excluding the zero derivative).

(2) Let us denote I_{k} = {(i, j) : i = 1, …, k; j = 1, …, ℓ_{i}}. Call C_{k} the family of nonempty semialgebraic subsets of R^{k} that can be defined as some

C_{ε} = {(ξ_{1}, …, ξ_{k}) ∈ R^{k} ; ⋀_{(i,j)∈I_{k}} sign(f_{i,j}(ξ_{1}, …, ξ_{k})) = ϵ_{i,j}} ≠ ∅

(where ε = (ϵ_{i,j})_{(i,j)∈I_{k}} is any family in {−1, 0, +1}). It is clear that the C_{ε}’s in C_{k} give a partition of R^{k}. We have

(a) The canonical projection π_{k}(C_{ε}) of any element C_{ε} ∈ C_{k} on R^{k−1} is an element of C_{k−1}: it is obtained as C_{ε′} where ε′ is the restriction of the family ε to I_{k−1}.

(b) The adherence \overline{C_{ε}} of C_{ε} (recall we assume C_{ε} ≠ ∅) is a union of elements of C_{k}, it is obtained by relaxing strict inequalities in the definition of C_{ε}.

(c) If in the definition of C_{ε} ∈ C_{k} there is one equality f_{k,i}(ξ_{1}, …, ξ_{k}) = 0 then C_{ε} is the graph of a root function ρ_{σ}(f_{k,j}) (here f_{k,j} is seen as a polynomial in x_{k}, it is equal to f_{k,i} or to some f_{k,i}^{(ℓ)} and σ is extracted from ε) which is Nash over π_{k}(C_{ε}). Moreover, ρ_{σ}(f_{k,i}) is defined over \overline{π_{k}(C_{ε})} and the graph of this root function is \overline{C_{ε}}.

(d) Call π_{n,k} the canonical projection R^{n} → R^{k}. Let E be a k dimensional semialgebraic subset of R^{n} defined from the polynomials g_{1}, …, g_{s}. Then for any C_{ε} ∈ C_{n} which is contained in E, π_{n,k} maps homeomorphically \overline{C_{ε}} on its image.

Definition 4.2.3 Such a change of variables together with such a family (f_{i,j}) will be called a stratification for (g_{1}, …, g_{s}) and for any semialgebraic subset of R^{n} defined from this family. The family (f_{i,j})_{i=1,... ,n;j=1,... ,ℓ_{i}} will be called a stratifying family for the initial family (g_{1}, …, g_{s}). The semialgebraic subsets C_{ε} are called the strata of the stratification.

We shall precisely consider the following way of constructing a stratifying family, à la Cohen-Hörmander (it is the one suggested in [1].) First we make a linear change of variables in order to make g_{1}, …, g_{s} quasi monic in the new variable x_{n}. We add all the derivatives of each g_{i} w.r.t. x_{n}. This gives us the family (f_{n,j})_{j=1,... ,ℓ_{n}}.

We apply Cohen-Hormander’s algorithm to this family and we call h_{1}, …, h_{ℓ} the “constants” given by this algorithm (these constants are polynomials in (x_{1}, …, x_{n−1})).

We make a new linear change of variables on (x_{1}, …, x_{n−1}) in order to make h_{1}, …, h_{ℓ} quasi monic in the new variable x_{n−1}. We make the same linear change of variables inside (f_{n,j})_{j=1,... ,ℓ_{n}}: this family remains quasimonic in x_{n} and stable under derivation w.r.t. x_{n}, and h_{1}, …, h_{ℓ} remain the “constants” given by the Cohen-Hormander’s algorithm when applied to this family.

We add all the derivatives of each h_{i} w.r.t. x_{n−1}. This gives us the family (f_{n−1,j})_{j=1,... ,ℓ_{n−1}}. And so on.

With this kind of stratifying family, we can apply recursively Theorem 3.1.3. So we get a precise description of the variation of the valuations v(f_{k,j}(x_{1}, …, x_{k})) when (x_{1}, …, x_{k}) ∈ C_{ε} for any k and any C_{ε} ∈ C_{k}. Let us see an example.

Example 4.2.4 Assume n = 3. Consider a cell C ∈ C_{3}. Assume that C′′ = π_{3,1}(C) is an interval ]a, b[ , that C′ = π_{3,2}(C) is the graph of a root function h_{1} = ρ_{σ}(f_{2,1}) defined on [a, b], and that C is the part of C′ × R between two root functions h_{2} = ρ_{σ′}(f_{3,1}) and h_{3} = ρ_{σ′′}(f_{3,2}), so

\begin{aligned}C & = & \{(x, y, z) : a < x < b, y = h_{1}(x), h_{2}(x, y) < z < h_{3}(x, y)\} \\ & = & \{(x, y, z) : a < x < b, y = h_{1}(x), h′_{2}(x) < z < h′_{3}(x)\} . \end{aligned}

We consider for (x, y, z) ∈ C, the parameters t = (x − a)/(b − x), τ = v(t), t′ = (z − h′_{2}(x))/(h′_{3}(x) − z) and τ′ = v(t′). We get:

• The map h : (t, t′) ↦ (x, y, z) ∈ C is a Nash isomorphism from (R^{+})^{2} onto C.

• For any f_{k,j} in the stratifying family v(f_{k,j}(x, y, z)) = φ_{k,j}(τ, τ′) is a ℚsemilinear function of τ, τ′ (here we use recursively Theorem 3.1.3).

• So, if we look at C ∩ S where S is any (≤, ⪯)–constructible subset described from the f_{k,j}’s, we find that C ∩ S is a finite union of sets h(L_{i}) where each L_{i} is defined as

{(t, t′) ∈ (R^{+})^{2} : ⋀_{ℓ} a_{ℓ}(τ, τ′) = α_{ℓ} ∧ ⋀_{m} b_{m}(τ, τ′) > β_{m}}

where a_{ℓ}’s and b_{m}’s are ℤ-linear forms and α_{ℓ}, β_{m} ∈ Γ_{K}^{dh}.

• Now we should like to have some rational expression of τ and τ′ that uses only polynomials in (x, y, z). This is possible in the following way, as in Remark 3.1.2. Consider that the formal variables are X, Y, Z and that x, y, z are three parameters. Add to the list g_{i} the three polynomials X − x, Y − y, Z−z and reconstruct the stratification, using the information that (x, y, z) is in the semialgebraic set C. You get that τ and τ′ are fixed ℚ-semilinear functions in the v(c_{j})’s and in some v(F_{j}(x, y, z))’s: the c_{j}’s are the old constants, and the F_{j}(x, y, z) are the new “constants” that are constructed by the algorithm (F_{j}(x, y, z) ∈ K[x, y, z]).

The following “cell decomposition theorem” is merely the generalization of what we have seen on this example. It is obtained by applying Theorem 1.3.6 to a stratification à la Cohen-Hörmander. The last assertion is obtained as in Remark 3.1.2.

Theorem 4.2.5 (Cell decomposition theorem) Let (K, V, P) be an ordered valued subfield of a real closed valued field (R, V_{R}, P_{R}). Let g_{1}, …, g_{s} be nonzero polynomials in K[x_{1}, …, x_{n}]. Consider a linear change of variables together with a family (f_{i,j})_{i=1,... ,n;j=1,... ,ℓ_{i}} that give a stratification for (g_{1}, …, g_{s}). Assume that this stratification is constructed à la Cohen-Hörmander, as explained above (after Definition 4.2.3). Consider any k-dimensional stratum C_{ε} corresponding to this stratification (see Theorem 4.2.2). Then there is a Nash isomorphism

h : (R^{+})^{k} ⟶ C_{ε}, (t_{1}, …, t_{k}) ⟼ h(t_{1}, …, t_{k})

with the following property.

If S is any (≤, ⪯)–constructible subset described from g_{1}, …, g_{s}, then S ∩ C_{ε} is a finite union of cells h(L_{i}), where each L_{i} can be defined as

{(t_{1}, …, t_{k}) ∈ (R^{+})^{k} : ⋀_{ℓ} a_{ℓ}(τ) = α_{ℓ} ∧ ⋀_{m} b_{m}(τ) > β_{m}}

where τ = (τ_{1}, …, τ_{k}) = (v(t_{1}), …, v(t_{k}), the a_{ℓ}’s and b_{m}’s are ℤ-linear forms w.r.t. τ, and α_{ℓ}, β_{m} ∈ Γ_{K}^{dh}.

Moreover, each τ_{i} is a ℚ-semilinear function in some v(F_{j}(x_{1}, …, x_{n}))’s (with F_{j}’s explicitly computable elements of K[x_{1}, …, x_{n}]).

References

[1] Bochnak J., Coste M., Roy M.-F. Géométrie algébrique réelle. Springer-Verlag (1987). English version Real Algebraic Geometry. Springer-Verlag (1998)

[2] Cherlin, Dickmann M. A., Real closed rings II. Model Theory. Ann. of Pure and Applied Logic 25, (1993) 213–231.

[3] Cohen A., Cuypers H., Sterk H. (eds) Some Tapas of Computer Algebra. Springer Verlag (1999).

[4] Coste M., Roy M.-F. Thom’s Lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. J. of Symbolic Computation 5 (1988), 121-129.

[5] González-Vega L., Lombardi H., Mahé L. Virtual roots of real polynomials. J. of Pure and Applied Algebra 124, (1998) 147–166.

[6] Lombardi H. Une borne sur les degrés pour le Théorème des zéros réel effectif. in: Real Algebraic Geometry. Lecture Notes in Math. n^{o}1524. Eds.: Coste M., Mahé L., Roy M.-F.. Springer-Verlag, (1992), pp. 323–345.

[7] Lombardi H., Roy M.-F. Constructive elementary theory of ordered fields. in Effective Methods in Algebraic Geometry. Eds.: Mora T., Traverso C.. Birkhäuser. Basel. 1991. Progress in Math. n^{o}94. pp. 249–262.

[8] Mausz F. Definierbare Mengen über bewerteten reel abgeschlossenen Körpen, Doctoral Dissertation, Univ. Köln, 1995.

[9] De la Puente M.J. Specializations and a local homeomorphism theorem for real Riemann surfaces of rings. Pacific J. of Math. 176 (2), (1996) 427–442.

[10] Warou H. An algorithm and bounds for the real effective Nullstellensatz in one variable. Progress in Math. n^{o}143, Birkhäuser. Basel. 1996. pp. 373–387.

[11] Warou H. Formules de Taylor Généralisées et applications. Preprint Université de Niamey