Fields Institute Communications Volume 00, 0000

Dynamic computations inside the algebraic closure of a valued field

Franz-Viktor Kuhlmann

Mathematical Sciences Group, University of Saskatchewan, 106 Wiggins Road, Saskatoon, SK, S7N 5E6, Canada.

                                  fvk@math.usask.ca

Henri Lombardi

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

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

                             lombardi@math.univ-fcomte.fr

Hervé Perdry

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

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

                              perdry@math.univ-fcomte.fr

Abstract. We explain how to compute in the algebraic closure of a valued field. These computations heavily rely on the Newton Polygon Algorithm. They are made in the same spirit as the dynamic algebraic closure of a field. They give a concrete content to the theorem saying that a valued field does have an algebraically closed valued extension. The algorithms created for that purpose can be used to perform an effective quantifier elimination for algebraically closed valued fields, which relies on a very natural geometric idea.

Contents

Introduction 2 1. Basic material 3 2. Dynamic computations in the algebraic closure 6 3. Quantifier elimination 14 References 24

2000 Mathematics Subject Classification. Primary: 12J10, 12J20, 12Y05, 03C10; Secondary: 13P05, 68W30.

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

Introduction

We consider a valued field K with V its valuation ring and S a subring of V such that K is the quotient field of S. We assume that S is an explicit ring and that divisibility inside V can be tested, for any two elements of S. By explicit ring we mean a ring where algebraic operations and equality test are explicit. These are our minimal assumptions of computability. If we want more assumptions in certain cases we shall explicitly state them.

We let K^{ac} denote the algebraic closure of K with V^{ac} a valuation ring that extends V. Our general purpose is the discussion of computational problems in (K^{ac}, V^{ac}) under our computability assumptions on (K, V).

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. Algorithms with the above minimal computability assumptions work uniformly. This means that some computations are made that give polynomials of ℤ[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 the way the answers to these tests are made. We may imagine these answers given either by some oracles or by some algorithms.

We shall denote the unit group by U_{V} or V^{×}, M_{V} = V \ U_{V} will be the maximal ideal and U_{V}^{1} = 1 + M_{V} is the group of units whose residue is equal to 1. We denote the value group K^{×}/U_{V} by Γ_{K}. We consider Γ_{K^{ac}} as the divisible hull Γ_{K}^{dh} of Γ_{K}, and the valuation v_{K^{ac}} as an extension of v_{K}. We shall denote the residue field V/M_{V} of (K, V) by \overline{K} . By convention, v(0) = ∞ (this is not an element of Γ_{K}).

We say that the value of some element x belonging to K^{ac} is well determined if we know an integer m and two elements F and G of ℤ[C_{1}, …, C_{n}] such that, setting f = F (c_{1}, …, c_{n}), with f ≠ 0, and g = G(c_{1}, …, c_{n}), there exists a unit u in V^{ac} such that:

fx^{m} = ug

(a particular case is given by infinite value, i.e., when x = 0.)

We call v(x) the value of x and we read the previous formula as:

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

We shall use the notation x ⪯ y for v(x) ≤ v(y).

Example 0.1 Let us for example explain the computations that are necessary to compare 3v(x_{1}) + 2v(x_{2}) to 7v(x_{3}) when the values 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) .

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 that

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 asumptions on the ring S.

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

The constructive meaning of the existence of an algebraic closure (K^{ac}, V^{ac}) of (K, V) is that computations inside (K^{ac}, V^{ac}) never produce contradictions. The constructive proof of this constructive meaning can be obtained by considering classical proofs (of the existence of an algebraic closure) from the viewpoint of dynamical theories (see [2]).

The present paper can be read from a classical point of view as well as from a constructive one. Our results give a uniform way for computing inside (K^{ac}, V^{ac}) when we know how to compute inside (K, V).

In the first section we give some basic material for computation inside algebraically closed valued fields. The most important is the Newton Polygon Algorithm.

In section 2, we explain how the Newton Polygon Algorithm can be used in order to make explicit computations inside the algebraic closure of a valued field, even in the case where there is no factorization algorithm for one variable polynomials. It is sufficient to take the point of view of dynamic evaluations as in [3].

To conclude the paper, we give in section 3 a new quantifier elimination algorithm for the theory of algebraically closed valued fields (with fixed characteristic and residue field characteristic). The geometric idea for this algorithm is simple. It can be easily implemented after the work done in section 2.

1 Basic material

1.1 Multisets. A multiset is a set with (nonnegative) multiplicities, or equivalently, a list defined up to permutation. In particular, the roots of a polynomial P (X) 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.

We shall use the natural (associative commutative) additive notation for “disjoint unions” of multisets, e.g.,

[b, a, c, b, b, a, b, d, a, c, b] = 3[a, b] + [b, b, d] + 2[c] = 3[a] + 5[b] + 2[c] + [d] .

We call a pairing between two multisets what remains of a bijection between two corresponding lists when one forgets the ordering of the lists. E.g., if we consider the two lists

(a, a, a, a′, a′, a′, a′′) = (a_{i})_{i=1,... ,7} and (b, b, b′, b′, b′′, b′′, b′′) = (b_{i})_{i=1,... ,7}

corresponding to the multisets

3[a] + 3[a′] + [a′′] and 2[b] + 2[b′] + 3[b′′] ,

and the bijection

a_{1} ↦ b_{3}, a_{2} ↦ b_{4}, a_{3} ↦ b_{1}, a_{4} ↦ b_{6}, a_{5} ↦ b_{5}, a_{6} ↦ b_{7}, a_{7} ↦ b_{2} ,

then what remains can be described as

2[a ↦ b′] + [a ↦ b] + 3[a′ ↦ b′′] + [a′′ ↦ b] ,

or equivalently as

2[(a, b′)] + [(a, b)] + 3[(a′, b′′)] + [(a′′, b)] .

This is a multiset of pairs that gives by the canonical projections the initial multisets 3[a] + 3[a′] + [a′′] and 2[b] + 2[b′] + 3[b′′].

This notion can be extended to r multisets M_{1}, …, M_{r} with same cardinality k: a pairing between the M_{i}’s is a multiset of r-tuples that gives by the canonical projections the initial multisets M_{1}, …, M_{r}.

The notion of multisets is a natural one when dealing with roots of a polynomial in an abstract setting. Multiplicity is relevant, but in general there is no canonical ordering of the roots.

Dynamic evaluation in [3, 4] can be understood as a way of computing with root multisets.

1.2 The Newton Polygon. Here we recall the well known Newton Polygon Algorithm.

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)

Let P (X) = p_{d} ∏_{i=1}^{d}(X − x_{i}) in K^{ac}[X]. 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 zeros of P in K^{ac} whose value in Γ_{K}^{dh} equals (v(p_{i}) − v(p_{j}))/(j − i) form a multiset with cardinality j − i .

Proof Order the x_{i}’s in non-decreasing order of the values v(x_{i}). We give the proof for an example. Assume for instance that

ν_{1} = v(x_{1}) = v(x_{2}) < ν_{3} = v(x_{3}) = v(x_{4}) = v(x_{5}) < ν_{6} = v(x_{6}) ⋯

Let us express p_{d−j}/p_{d} as a symmetric function of the roots. We see immediately that

\begin{aligned}v(p_{d−1}) & ≥ & v(p_{d}) + ν_{1} \\ v(p_{d−2}) & = & v(p_{d}) + 2ν_{1} \\ v(p_{d−3}) & ≥ & v(p_{d}) + 2ν_{1} + ν_{3} > v(p_{d}) + 3ν_{1} \\ v(p_{d−4}) & ≥ & v(p_{d}) + 2ν_{1} + 2ν_{3} \\ v(p_{d−5}) & = & v(p_{d}) + 2ν_{1} + 3ν_{3} \\ v(p_{d−6}) & ≥ & v(p_{d}) + 2ν_{1} + 3ν_{3} + ν_{6} > v(p_{d}) + 2ν_{1} + 4ν_{3} \end{aligned}

So the two last edges of the Newton polygon are ((d − 2, v(p_{d−2})), (d, v(p_{d}))) with slope −2ν_{1} and ((d−5, v(p_{d−5})), (d−2, v(p_{d−2}))) with slope −3ν_{3}, giving the wanted result.

Now we can give an answer to the following problem.

Computational problem 1.1 (Multiset of values of roots of polynomials) Input: A polynomial P ∈ K[X] 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}.

This problem is solved by the following algorithm, which is widely used in the sequel.

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

1.3 Generalized Tschirnhaus transformation. We recall a well known way of computing in algebraic extensions, which we will use freely in our paper. We call this method the generalized Tschirnhaus transformation.

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

P_{j}(X) = (X − ξ_{j,1}) · . . . · (X − ξ_{j,d_{j}})

their factorizations in K^{ac}[X]. Take Q(X_{1}, …, X_{r}) ∈ K[X_{1}, …, X_{r}], and let d = d_{1} ⋯ d_{r}. We claim that the polynomial

T_{Q}(Z) = (Z − Q(ξ_{1,1}, …, ξ_{r,1})) · . . . · (Z − Q(ξ_{1,d_{1}}, …, ξ_{r,d_{r}}))

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

K[x] := K[X_{1}, …, X_{r}]/ ⟨P_{1}(X_{1}), …, P_{r}(X_{r})⟩ .

We give a proof of this well known fact, for which we found no reference. We prove a slightly more general result, which deals with roots of so-called triangular systems. Moreover, the computation works in arbitrary commutative rings.

Definition 1.2 Let A ⊂ B be commutative rings.

1. Take a system of polynomials

\overline{P} = (P_{1}, …, P_{r}) where P_{1}(X_{1}) ∈ A[X_{1}],

P_{2}(X_{1}, X_{2}) ∈ A[X_{1}, X_{2}], …, P_{r}(X_{1}, …, X_{r}) ∈ A[X_{1}, …, X_{r}] .

This system is called a triangular system if each P_{i} is monic w.r.t. X_{i}.

2. The quotient algebra is A[X_{1}, …, X_{r}]/ ⟨P_{1}, …, P_{r}⟩ = A[x_{1}, …, x_{r}] where x_{i} is the class of X_{i}. We denote it by A\overline{P}. Let d_{i} = deg_{X_{i}}(P_{i}). Then A\overline{P} is a free A-module of rank d_{1}d_{2} ⋯ d_{r} with “monomial basis” (x_{1}^{μ_{1}} ⋯ x_{r}^{μ_{r}})_{μ_{i}<d_{i}}. Note that we may assume w.l.o.g. that deg_{X_{j}}(P_{k}) < d_{j} for k > j.

3. A vector α = (α_{1}, …, α_{k}) ∈ B^{r} is called a root vector of \overline{P} (or a solution of \overline{P}) if

P_{1}(α_{1}) = P_{2}(α_{1}, α_{2}) = … = P_{k}(α_{1}, …, α_{r}) = 0 .

4. Assume for simplicity that r = 3. We say that the system \overline{P} fully splits in B if B contains elements ξ_{i} (i ≤ d_{1}), ξ_{i,j} (i ≤ d_{1}, j ≤ d_{2}), and ξ_{i,j,k} (i ≤ d_{1}, j ≤ d_{2}, k ≤ d_{3}) such that

\begin{matrix}P_{1}(X) & = & ∏_{i≤d_{1}}(X − ξ_{i}) \\ P_{2}(ξ_{i}, Y) & = & ∏_{j≤d_{2}}(Y − ξ_{i,j}) & (i ≤ d_{1}) \\ P_{3}(ξ_{i}, ξ_{i,j}, Z) & = & ∏_{k≤d_{3}}(Z − ξ_{i,j,k}) & (i ≤ d_{1}, j ≤ d_{2}) \end{matrix} \}  (1)

5. When A = K and B = K^{ac}, two systems with the same variables are called coprime systems if they have no common root vector.

In order to simplify notations, we give our result for the case r = 3.

Proposition 1.3 Let A ⊂ B be commutative rings and \overline{P} = (P_{1}, P_{2}, P_{3}) a triangular system over A which fully splits in B with equations (1). Let Q(x_{1}, x_{2}, x_{3}) ∈ A\overline{P}, μ_{Q} be the A-linear endomorphism of A\overline{P} representing multiplication by Q, and C_{Q}(Z) the characteristic polynomial of μ_{Q}. Then we have

C_{Q}(Z) = ∏_{i≤d_{1}, j≤d_{2}, k≤d_{3}}(Z − Q(ξ_{i}, ξ_{i,j}, ξ_{i,j,k}))  (2)

Proof Note that we could have chosen Q ∈ A[X_{1}, X_{2}, X_{3}]. But if (α, β, γ) is a root vector of \overline{P} in an extension of A, it is clear that Q(α, β, γ) depends only of the class of Q in A\overline{P}, so equation (2) is meaningful.

By Cayley-Hamilton C_{Q}(μ_{Q}) = 0 and since μ_{Q}(1) = Q, C_{Q}(Q) = 0. This implies that C_{Q}(Q(α, β, γ)) = 0 each time we have a root vector (α, β, γ) of \overline{P} in an extension of A since A[α, β, γ] is a homomorphic image of A\overline{P}.

So the proposition is proved in the “good case” where B is a domain and all the root vectors in (1) give distinct values for Q(ξ_{i}, ξ_{i,j}, ξ_{i,j,k}): the RHS and LHS in (2) are monic univariate polynomials with the same roots, all being distinct.

Now we give the proof for the “generic case” where the ξ_{i}, ξ_{i,j}, ξ_{i,j,k} and the coefficients q_{i,j,k} of Q are indeterminates. This means that B can be replaced by a ring generated over ℤ by these indeterminates, and A can be replaced by the subring of B generated by the coefficients of Q and by the coefficients of P_{1}, P_{2}, P_{3} which are defined by equations (1). In this generic case, B is an integral domain and all the Q(ξ_{i}, ξ_{i,j}, ξ_{i,j,k}) are distinct. So the generic case is a good case and we are done.

Finally, note that all non-generic cases are homomorphic images of the generic case.

We give another slight generalization, which can be proved in a similar way. Let Q, R ∈ A[X_{1}, …, X_{r}] with R(ξ) invertible in B for all the root vectors in (1). Let F = Q/R. Then A_{R} is an invertible matrix (over B) and the polynomial

T_{F} (Z) = ∏_{i≤d_{1}, j≤d_{2}, k≤d_{3}}(Z − F (ξ_{i}, ξ_{i,j}, ξ_{i,j,k}))

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

2 Dynamic computations in the algebraic closure

Dynamic computations in the algebraic closure of a valued field are an extension of dynamic computations in the algebraic closure of a field as explained in [3, 4]. First let us recall these ones.

2.1 Dynamic algebraic closure. The following algorithms tell us how to compute dynamically in the algebraic closure of K when we do not want to (or we cannot) use factorization algorithms in K[X].

First we examine the problem of adding one root of a monic polynomial without factorization algorithm. If we are able to compute in the field so created, then we are able to compute recursively in any finite extension given by adding one after the other roots of several polynomials. In fact, since there is a priori an ambiguity about what root we have introduced (distinct roots give in general non-isomorphic fields), we have to compute all possible cases.

Computational problem 2.1 (computational problem à la D5) Input: Let P (of degree ≥ 2) and Q be polynomials in K[X]. Output: Give correct answers to the following questions:

(1) Is Q zero at each root of P in K^{ac}?

(2) Is Q nonzero at each root of P in K^{ac}?

(3) If the two answers are “No”, compute two factors P_{1} and P_{2} of P and two polynomials U_{1}, U_{2} such that:

— Q is zero at each root of P_{1} in K^{ac},

— Q is nonzero at each root of P_{2} in K^{ac},

— P_{1} and P_{2} are coprime, P_{1}U_{1} + P_{2}U_{2} = 1,

— each root of P in K^{ac} is a root of P_{1}P_{2}.

We give two natural solutions of the previous problem.

Algorithm SquarefreeD5 (solving computational problem 2.1 when P is a squarefree polynomial) Assume that P is squarefree. Compute the monic GCD P_{1} of P and Q. If P_{1} = 1 then answer “Yes” to the second question;

else if lc(P)P_{1} = P then answer “Yes” to the first question; else return P_{1}, P_{2} := P/P_{1} and polynomials U_{1}, U_{2} s.t. P_{1}U_{1}+P_{2}U_{2} = 1.

Algorithm BasicD5 (solving computational problem 2.1) Compute the monic GCD P_{1} of P and Q. If P_{1} = 1 then answer “Yes” to the second question;

else compute the monic polynomial P_{2} such that:

P_{2} divides P, GCD(P_{1}, P_{2}) = 1 and P divides P_{1}^{m}P_{2} (for some m);

if P_{2} = 1 then answer “Yes” to the first question, and replace P by P_{1}; else return P_{1}, P_{2} and polynomials U_{1}, U_{2} s.t. P_{1}U_{1} + P_{2}U_{2} = 1.

The replacement of P by P_{1} is not used in the algorithm itself, but is meant for use by subsequent algorithms because if P_{2} = 1 then P_{1} has the same roots as P but possibly smaller degree.

Remark 2.2 Observe that P_{2} = P/ gcd(P_{1}^{k}, P) = P/ gcd(Q^{k}, P) where k = 1 + deg(P) − deg(P_{1}). We can also get P_{2} by iteration of the process: start with R = P; replace R by R/ gcd(R, Q) (here gcd(R, Q) means the monic GCD of R and Q), until the GCD is 1.

If P is monic and the ring S is normal then P_{1} and P_{2} are in S[X], but it is not always easy to make this result explicit. Nevertheless we can always compute P_{1} and P_{2} using coefficients in the quotient field of S: the GCD computation may use pseudo divisions instead of divisions. The use of subresultant polynomials may improve the efficacity of the algorithm.

We can understand the previous algorithms as breaking the set of roots of a polynomial in distinct subsets anytime that some objective distinction may be done between the roots. Their stupendous simplicity is certainly the main reason explaining their non-universal use in the literature about algebraic extensions of fields.

Remark 2.3 If we see the roots of P as a multiset, and if we want to keep the information concerning multiplicities, the output

• (P_{1}, P_{2}) with P_{1}, P_{2} coprime and each root of P in K^{ac} is a root of P_{1}P_{2}. is not the good one. We need in this case one of the two following outputs:

• (P_{1}, P_{2}) with P_{1}, P_{2} coprime and P_{1}P_{2} = P. or in a more economic way for future computations:

• (P_{1}, P_{2}) with P_{1}, P_{2} coprime, P_{1}P_{2} = P and a decomposition of each P_{i} as

a product of powers of coprime polynomials. The computational problem corresponding to the first output can be solved by the following slight variant of BasicD5.

Algorithm MultisetD5 (solving a multiset variant of computational problem 2.1). Input: Let P (of degree ≥ 2) and Q be polynomials in K[X]. Output: (P_{1}, P_{2}) with P_{1}, P_{2} coprime, P_{1}P_{2} = P, Q is zero at each root of P_{1} in K^{ac}, Q is nonzero at each root of P_{2} in K^{ac}. Compute the monic GCD R_{1} of P and Q. If R_{1} = 1 then return P_{1} = 1, P_{2} = P

else compute the monic polynomial P_{2} such that:

P_{2} divides P, GCD(R_{1}, P_{2}) = 1 and P divides R_{1}^{m}P_{2} (for some m). return P_{2}, P_{1} = P/P_{2} and polynomials U_{1}, U_{2} such that P_{1}U_{1} + P_{2}U_{2} = 1.

We now explain the recursive use of algorithms SquarefreeD5 and BasicD5. Note that root vectors of a triangular system \overline{P} as in definition 1.2 form a multiset of cardinality d = ∏_{i} deg_{X_{i}}(P_{i}).

Computational problem 2.4 (computing in extensions generated by several successive algebraic elements) Input:

• A triangular system of polynomials \overline{P} = (P_{1}, …, P_{n}):

P_{1}(X_{1}) ∈ K[X_{1}], P_{2}(X_{1}, X_{2}) ∈ K[X_{1}, X_{2}], …, P_{k}(X_{1}, …, X_{k}) ∈ K[X_{1}, …, X_{k}] .

• A finite list of polynomials Q_{1}, …, Q_{r} in K[X_{1}, …, X_{k}].

Output:

• A list of coprime triangular systems \overline{S^{(1)}}, …, \overline{S^{(ℓ)}} whose root vectors form a partition of the set of all solutions of the initial triangular system \overline{P}, such that for each j, the r-tuple of signs for the tuple (Q_{1}(\overline{x}), …, Q_{r}(\overline{x})) (the sign of y is either 0 if y = 0 or 1 if y ≠ 0), is the same for every root vector \overline{x} = (x_{1}, …, x_{k}) of \overline{S^{(j)}} .

• For each triangular system \overline{S^{(j)}}, this fixed r-tuple of signs.

In the general case, we can solve the previous problem in the following way.

Algorithm TriangularBasicD5 (solving computational problem 2.4) Use BasicD5 recursively. More precisely, consider that Q and P_{k} are polynomials in the variable X_{k} with parameters (x_{1}, …, x_{k−1}). When making the computations of BasicD5 we have to solve some tests

“ Is R(x_{1}, …, x_{k−1}) equal to zero or not ? ” for some polynomials R given by the computation. So we have to solve the same kind of problem with one variable less. Hence, a recursive computation will produce the answer.

In the case of a perfect field, we can use SquarefreeD5 recursively. To see why this works, we have to recall how to compute the squarefree part of a polynomial in one variable in this case.

Algorithm SquarefreePart (compute the squarefree part of a polynomial in one variable in the case of a perfect field) We assume that K is a perfect field. In the characteristic p case we assume that getting p-th roots is explicit inside S. Input: A polynomial P ∈ S[X] . Output: P_{1} the squarefree part of P. If the characteristic is zero then P_{1} = P/ gcd(P, P′). If the characteristic is p then let P_{1} = 1 and: Iterate the following process:

Beginning with R = P iterate the following process:

If R = Q(X^{p}) then replace R by R^{1/p} else replace R by R/ gcd(R, R′) until you find gcd(R, R′) = 1. Replace P_{1} by P_{1} · R Iterate the following process: Replace P by P/ gcd(P, R)

until you find gcd(P, R) = 1 until P = 1.

We suggest that the reader apply the algorithm to a polynomial of the form Q_{1}(X^{p})^{2}Q_{2}(X^{p^{2}}) with p ≠ 2, in order to see why the loops in this algorithm are necessary.

AlgorithmPerfectTriangularD5 (solving computational problem 2.4 in the case of a perfect field) We assume that K is a perfect field. In the characteristic p case we assume that getting p-th roots is explicit inside S. In a first big step we replace the initial system by a disjunction of coprime systems that are “squarefree”. For each polynomial in the triangular system, we use SquarefreePart and (recursively) SquarefreeD5 to replace it by a “squarefree” polynomial. More precisely, first we replace P_{1} by its squarefree part S_{1}. Then we try to apply SquarefreePart to the polynomial P_{2} as if the quotient algebra K[X_{1}]/S_{1}(X_{1}) were a field. If this is not possible, SquarefreeD5 produces a splitting of S_{1}. In each branch so created the computation is possible and we can replace P_{2} by its squarefree part. For example, we may get three branches with the following properties. In the first one, the squarefree polynomial P_{1,1} replaces P_{1} , and P_{2} is already squarefree, so that P_{2,1} = P_{2} . In the second one, the squarefree polynomial P_{1,2} replaces P_{1} , and the squarefree part of P_{2} is given by P_{2,2} with degree deg(P_{2}) − 1. In the third one, P_{1,3} replaces P_{1} and the squarefree part of P_{2} is given by P_{2,3} with degree deg(P_{2}) − 4. Then we introduce P_{3} in every branch previously created and try to apply SquarefreePart to the polynomial P_{3} as if the corresponding quotient algebra K[X_{1}, X_{2}]/ ⟨P_{1,i}(X_{1}), P_{2,i}(X_{1}, X_{2})⟩ were a field. If this is not possible, SquarefreeD5 produces a splitting of P_{1,i} or P_{2,i}. And so on. When we have introduced all P_{i}’s, we get a tree. Each leaf of the tree corresponds to a new triangular system where all successive polynomials replacing the P_{i}’s are “strongly squarefree” (the squarefreeness is certified by a Bezout identity in the suitable quotient algebra). Distinct leaves correspond to coprime triangular systems. So the set of root vectors of \overline{P} is partitioned into distinct subsets, each one corresponding to a leaf of the tree. Now we describe the second “big step”. At each leaf of the tree we search for the signs of the Q_{j}’s using SquarefreeD5 as if the corresponding quotient algebra were a field. If this is not possible, new splittings are produced.

Remark 2.5 Slight variants of the above algorithms give a partition of the multiset of solutions of the triangular system \overline{P} in disjoint multisets that are defined by coprime triangular systems \overline{S′^{(j)}}, each Q_{i} having a constant sign at the zeros of each \overline{S′^{(j)}}.

Remark 2.6 The above algorithms can be generalized in order to search systematically for solutions of any system of sign conditions: equalities need not be in a triangular form. So they can be seen as quantifier elimination algorithms in the first order theory of algebraically closed extensions of some explicitly given field K.

In the following subsection we show that the same kind of computations are possible in the case of valued fields.

2.2 Dynamic algebraic closure of a valued field.

Roots of one polynomial. The valued algebraic closure of (K, V) is well determined up to isomorphism. So the following computational problem makes sense.

Computational problem 2.7 (Simultaneous values) Input: polynomials P (monic) and Q_{1}, …, Q_{r} in K[X]. Call [x_{1}, …, x_{d}] the multiset of roots of P in K^{ac}. Output: The multiset [(v(x_{i}), v(Q_{1}(x_{i})), …, v(Q_{r}(x_{i})))]_{i=1,... ,d} of (r + 1)-tuples of values.

This problem is solved by the following algorithm.

Algorithm SimVal (solving computational problem 2.7) We start with the case r = 1. Assume w.l.o.g. that P (0) ≠ 0. The multiset [ν_{i}]_{i=1,... ,d} of (finite) values of the x_{i}’s is given by the Newton Polygon Algorithm for P. For m, n ∈ ℕ, the polynomial

S_{m,n}(X) = (X − x_{1}^{m}Q_{1}(x_{1})^{n}) · . . . · (X − x_{d}^{m}Q_{1}(x_{d})^{n})

is the characteristic polynomial of the matrix A^{m}(Q_{1}(A))^{n} where A is the companion matrix of P. So, using the Newton polygon of S_{m,n} we know the multiset

[m v(x_{i}) + n v(Q_{1}(x_{i}))]_{i=1,... ,d} = [m ν_{i} + n ν_{1,i}]_{i=1,... ,d}

for any (m, n). We compute first the multiset [ν_{1,i}]_{i=1,... ,d} .

We want to compute the correct pairing between the two multisets [ν_{i}]_{i=1,... ,d} and [ν_{1,i}]_{i=1,... ,d} . Assume first that no ν_{1,i} is infinite. Let us call a bad coincidence for n_{1} an equality

ν_{i} + n_{1} ν_{1,h} = ν_{j} + n_{1} ν_{1,k} with ν_{i} ≠ ν_{j}, i, j, h, k ∈ {1, …, d} .

If there is no bad coincidence for some n_{1} then we can state this fact by considering the two sets {ν_{i} : i = 1, …, d} and {ν_{1,i} : i = 1, …, d}. Note also that there are at most (d(d−1)/2)^{2} “bad values” of n_{1}. So we can find a “good” n_{1} by a finite number of computations. Fix a “good” n_{1}. From the multisets [ν_{i}]_{i=1,... ,d} and [ν_{1,i}]_{i=1,... ,d} we deduce the multiset [ν_{i} + n_{1} ν_{1,j}]_{i=1,... ,d,j=1,... ,d}. Now, n_{1} being “good”, the multiset [ν_{i} + n_{1} ν_{1,i}]_{i=1,... ,d} (obtained by the Newton Polygon Algorithm applied to S_{1,n_{1}}) can be read as a submultiset of [ν_{i} + n_{1} ν_{1,j}]_{i=1,... ,d,j=1,... ,d}. This gives us the pairing between the multisets [ν_{i}]_{i=1,... ,d} and [ν_{1,i}]_{i=1,... ,d}. For example, assume that

[ν_{i}]_{i=1,... ,9} = 3[α_{1}] + 4[α_{2}] + 2[α_{3}], [ν_{1,i}]_{i=1,... ,9} = 2[β_{1}] + 2[β_{2}] + 2[β_{3}] + 3[β_{4}]

and that the number 5 is good, i.e., the twelve values α_{i} + 5β_{k} are distinct. Computing the multiset [ν_{i} + 5 ν_{1,i}]_{i=1,... ,9}, we find, e.g.,

\begin{matrix}[α_{1} + 5β_{1}] + 2[α_{1} + 5β_{4}] + [α_{2} + 5β_{4}] + 2[α_{2} + 5β_{2}]+ \\ +[α_{2} + 5β_{3}] + [α_{3} + 5β_{1}] + [α_{3} + 5β_{3}], \end{matrix}

and we get the pairing

[(α_{1}, β_{1})] + 2[(α_{1}, β_{4})] + [(α_{2}, β_{4})] + 2[(α_{2}, β_{2})] + [(α_{2}, β_{3})] + [(α_{3}, β_{1})] + [(α_{3}, β_{3})] .

Comment: the multiset [x_{i}]_{i=1,... ,d} is, as a root multiset, made of “indiscernible elements”. The knowledge of the multiset [ν_{i}]_{i=1,... ,d} introduces some distinction between the roots (if the ν_{i}’s are not all equal). The knowledge of the multiset [ν_{i} + n_{1} ν_{1,i}]_{i=1,... ,d} (with a “good” n_{1}) induces a finer distinction between the roots. We remark that the case where some Q_{1}(x_{i})’s equal zero can also be done correctly by a slight modification of the previous algorithm. Nevertheless, when such a case appears, it seems more natural to use the technique of dynamical evaluation (see [3] and section 2.1). If not all Q_{1}(x_{i})’s equal zero (which is a trivial case), then one can compute a factorization of P in a product of two coprime polynomials P_{1} and P_{2} by applying algorithm BasicD5 to P and Q_{1}. Then we can study separately the roots of these two polynomials. Moreover, the following steps of the algorithm are clearer if all Q_{1}(x_{i})’s are distinct from zero. Next we show that analogous arguments work for the general case. It will be sufficient to show how the case r = 2 works. Set ν_{2,i} = v(Q_{2}(x_{i})). We have computed the correct pairing [(ν_{1}, ν_{1,1}), (ν_{2}, ν_{1,2}), …, (ν_{d}, ν_{1,d})] between the multisets [ν_{i}]_{i=1,... ,d} and [ν_{1,i}]_{i=1,... ,d}. We know also a “good” integer n_{1}. We can assume w.l.o.g. that all ν_{1,i}’s and ν_{2,i}’s are finite. We compute first the multiset [ν_{2,i}]_{i=1,... ,d}. Let us call a bad coincidence for n_{2} an equality

ν_{i} + n_{1} ν_{1,i} + n_{2} ν_{2,h} = ν_{j} + n_{1} ν_{1,j} + n_{2} ν_{2,k} with ν_{i} + n_{1} ν_{1,i} ≠ ν_{j} + n_{1} ν_{1,j} .

If there is no bad coincidence for some n_{2} then we can state this fact by considering the two sets {ν_{i} + n_{1} ν_{1,i} : i = 1, …, d} and {ν_{2,i} : i = 1, …, d}. We choose such an integer n_{2}. And so on.

Remark 2.8 Assume that P is a squarefree polynomial, so the x_{i}’s are in the separable closure K^{sep} of (K, V). Assume that algorithm SimVal has shown that some list of values (ν_{i}, ν_{1,i}, …, ν_{r,i}) corresponds to only one root of P. It is clear from the abstract definition of the henselization that such a “discernible” element over (K, V) is inside the henselization K^{h} of (K, V). A perhaps surprising computational consequence is that, since the henselization is an immediate extension, when algorithm SimVal isolates (or discerns) some root of P, then the corresponding list of values is made only of “integer values”, i.e., values of elements of K “without integer denominator”. We can prove this constructively: First, using computations in the henselization K^{h} as defined in [5], one can prove (cf. [6]) the following lemma:

Lemma 2.9 If the polynomial P ∈ K^{h}[X] has roots x_{1}, …, x_{d} and if the d-tuple [v(Q(x_{1})), …, v(Q(x_{d}))] (provided by SimVal applied to P, Q or by any other way) is equal to d_{1}[α_{1}] + ⋯ + d_{k}[α_{k}], with α_{i} ≠ α_{j} (for i ≠ j), then one can factorize P = P_{1} … P_{k} in K^{h}[X] (deg P_{i} = d_{i}), such that, if the roots of P_{i} are y_{1}, …, y_{d_{i}} the d_{i}-tuple [v(Q(y_{1}), …, v(Q(y_{d_{i}}))] is equal to d_{i}[α_{i}].

Then if some list of values (ν_{i}, ν_{1,i}, …, ν_{r,i}) corresponds to only one root of P, we let n_{0} = #{j : ν_{j} = ν_{i}}, n_{1} = #{j : ν_{j} = ν_{i} and ν_{1,j} = ν_{1,i}}, … n_{r} = #{j : ν_{j} = ν_{i} and ν_{k,j} = ν_{k,i} k = 1, …, r} = 1

The previous result applied to P (X) and Q(X) = X provides a factor P_{0} of P, with degree n_{0}; then applied to P_{0}(X) and Q_{1}(X), it provides a factor P_{1} with degree n_{1}, and so on. Finally, we obtain a factor P_{r} of degree n_{r} = 1. So the corresponding root is in K^{h}. The computations in K^{h} prove that the list of values is made only of “integer values”; one can compute explicitly elements of K having the same value. More precisely, one can compute z_{0}, z_{1}, …, z_{r} ∈ K, such that x_{i} = z_{0}(1 + ν_{0}), Q_{1}(x_{i}) = z_{1}(1 + ν_{1}), …, Q_{r}(x_{i}) = z_{r}(1 + ν_{r}), with v(ν_{i}) > 0 for all i.

Root vectors of triangular systems. Algorithm SimVal says that “we can compute in K[x]” where x is a root of P satisfying certain “compatible value conditions”. We know how many roots of P correspond to a system of compatible value conditions. Computing in K[x] means that we can get “any brute information concerning the valuation in this field”, more precisely, we can decide, for any new polynomial Q, if the value of Q(x) is well determined or not. And we can compute the value(s). When several possibilities for v(Q(x)) appear, choosing one possible value, we refine our description of K[x].

So even if K[x] is not a priori a completely well determined valued field, we can nevertheless always do as if it was completely well determined. And we get recursively the following computations, exactly as in section 2.1.

More precisely, our computational problem is the following.

Computational problem 2.10 (computing in extensions generated by several successive algebraic elements) Input:

• A triangular system of polynomials \overline{P} = (P_{1}, …, P_{n}):

P_{1}(X_{1}) ∈ K[X_{1}], P_{2}(X_{1}, X_{2}) ∈ K[X_{1}, X_{2}], …, P_{k}(X_{1}, …, X_{k}) ∈ K[X_{1}, …, X_{k}] .

• A finite list of polynomials Q_{1}, …, Q_{r} in K[X_{1}, …, X_{k}].

Output:

• The multiset of (k + r)-tuples of values

[(v(x_{1}), …, v(x_{k}), v(Q_{1}(\overline{x})), …, v(Q_{r}(\overline{x})))]_{\overline{x}=(x_{1},... ,x_{k})∈R}

where R is the multiset of root vectors of \overline{P} (this multiset has cardinality d = ∏_{i} deg_{X_{i}}(P_{i})).

This problem is solved by the following algorithm.

Algorithm TriangularSimVal Use recursively algorithm SimVal.

Graph of roots. The following algorithm can be seen as a particular case of the previous one. We denote by μ(P, a) the multiplicity of a as root of the univariate polynomial P (if P (a) ≠ 0 we let μ(P, a) = 0).

Computational problem 2.11 (computing the ultrametric graph of roots of a family of univariate polynomials) Input:

• A finite family of univariate polynomials \overline{P} = (P_{1}, …, P_{s}) in K[X]. Output:

• The number N of distinct roots of P_{1} ⋯ P_{n}.

• For some ordering (x_{1}, …, x_{N}) of these roots the finite family

((μ(P_{i}, x_{j}))_{i∈[1,s],j∈[1,N]}, (v(x_{j} − x_{ℓ}))_{1≤j<ℓ≤N}) .

Note that there are many possible answers, by changing the order of the roots. All correct answers are isomorphic.

Algorithm GraphRoots First a recursive use of BasicD5 allows to find a finite multiset of pairwise coprime polynomials (R_{1}, …, R_{r}) such that each P_{i} is a product of some R_{k}’s. So we can assume w.l.o.g. that the P_{i}’s are pairwise coprime. If deg(P_{i}) = n_{i} we introduce the roots x_{i,1}, …, x_{i,n_{i}} of P_{i} through the triangular system

\begin{aligned}P_{i,1}(X_{i,1}) & = & P_{i}(X_{i,1}) \\ P_{i,2}(X_{i,1}, X_{i,2}) & = & \frac{P_{i,1}(X_{i,2})−P_{i,1}(X_{i,1})}{X_{i,2}−X_{i,1}} \\ P_{i,3}(X_{i,1}, X_{i,2}, X_{i,3}) & = & \frac{P_{i,2}(X_{i,1},X_{i,3})−P_{i,2}(X_{i,1},X_{i,2})}{X_{i,3}−X_{i,2}} \\ ⋮ & ⋮ & ⋮ \\ P_{i,n_{i}}(X_{i,1}, …, X_{i,n_{i}}) & = & \frac{P_{i,n_{i}−1}(X_{i,1},... ,X_{i,n_{i}−2},X_{i,n_{i}})−P_{i,n_{i}−1}(X_{i,1},... ,X_{i,n_{i}−2},X_{i,n_{i}−1})}{X_{i,n_{i}} −X_{i,n_{i}−1}} \\ P_{i,1}(x_{i,1}) & = & 0 \\ P_{i,2}(x_{i,1}, x_{i,2}) & = & 0 \\ P_{i,3}(x_{i,1}, x_{i,2}, x_{i,3}) & = & 0 \\ ⋮ & ⋮ & ⋮ \\ P_{i,n}(x_{i,1}, …, x_{i,n_{i}}) & = & 0 \end{aligned}

The P_{i,k}’s give all together a triangular system and we can apply TriangularSimVal for finding the values v(x_{i,k} − x_{i′,k′}). We remark that we can use a simplified form of TriangularSimVal since all possible results are isomorphic and we need only one of these results. E.g., in the first step we compute the multiset [(v(x_{1,k} − x_{1,k′})_{1≤k<k′≤n_{1}}] but we select arbitrarily one value as the good one w.r.t. some ordering of the roots, and so on.

Remark 2.12 There are probably some shortcuts allowing to give this ultrametric graph in a quicker way: for example, for a single polynomial, it is easy to compute the multiset of values [v(x_{i} − x_{j})]_{i≠j} without knowing exactly to which edge each value corresponds; there might be a way (at least in a great number of cases) to reconstruct the graph (up to isomorphism).

3 Quantifier elimination

The aim of this section is to give a transparent proof of the following well known theorem (cf. [8]).

Theorem 3.1 The theory of algebraically closed valued fileds (with fixed characteristics) admits quantifier elimination.

First we give a sketch of the proof of this theorem. Our algorithm is a kind of “cylindric algebraic decomposition” (in the real closed case see, e.g., [1]). Given a finite set of multivariate polynomials, we choose a variable as being the main variable and we consider the other ones as parameters.

We settle in subsection 3.2 an existential decision procedure for a quantifier free formula with only one variable: given a finite set S of univariate polynomials, we give a complete description of the “valued line K^{ac}” w.r.t. S.

More precisely, we give first a formal name to each root of each polynomial in S, and we compute the ultrametric distance between each pair of these roots. We compute also the multiplicities of these roots and all the values v(P_{i}(x_{j})) for each root x_{j} and each polynomial P_{i}. This job is done by algorithm GraphRoots.

Next, from these datas, we are able to test if a given conjunction of elementary assertions concerning the v(P_{i}(ξ))’s is realizable by some ξ of the line K^{ac}. In order to make this test we need a key geometric lemma, concerning ultrametric graphs. We explain this lemma in section 3.1.

The structure of our existential univariate decision procedure is very simple. This implies a kind of uniformity in such a way that the algorithm can be performed “with parameters”, exactly as BasicTriangularD5 is nothing but a parametrized version of Basic D5. This gives a good way for eliminating the quantifier in a formula with only one existential quantifier. So the work done in our final section 3.3 will be a careful verification of uniformity for the algorithms used in section 3.2.

Finally, the general elimination procedure follows by usual tricks.

We now give general explanations about notations and technical tools needed in the algorithms.

As in [8] we use a two-sorted language, L = (L_{F} , L_{Γ}, v). The language of fields L_{F} = {0, 1, +, −, .} is the F -sort. The language L_{Γ} is the Γ-sort. There is one more symbol, v, which is a function symbol for the valuation. The language L_{Γ} consists of the language L′_{Γ} = {0, ∞, +, −, <} of ordered Abelian groups with last element ∞ together with a family of symbols \{\frac{·}{q} : q ∈ ℕ^{∗}\}.

By convention a − ∞ = 0 for all a ∈ Γ. But there are some ambiguities as a − (b − c) may not be equal to a − b + c. In fact, it is possible to avoid the sign − for Γ-formulas, using case distinctions. For example, we can replace a − b = c by (b = ∞ ∧ c = 0) ∨ a = b + c. So any quantifier free formula Φ is equivalent to a formula written without the Γ-sign −. In the sequel we assume w.l.o.g. that Γ-terms are always written without using the Γ-sign −.

Note also that we have no function symbol for the inverse of a nonzero element inside the field. This is not a restriction. The introduction of this function symbol would imply some trouble as the necessity of some strange convention as x/0 = 0 for any x.

The theory of algebraically closed non-trivial valued fields is ACVF(L). Recall that the formal theory specifies the characteristic of the field and of the residue field. In our formulas there are F -variables and Γ-variables, F -terms and Γ-terms, and, more important, F -quantifiers and Γ-quantifiers.

The rules of building terms are the natural ones. We see that the F -terms are formal polynomials in ℤ[x_{1}, ⋯, x_{n}]. For the Γ-terms, we avoid the Γ-sign −. Take r_{1}, …, r_{k} ∈ ℚ^{>0}, and let f_{1}, …, f_{ℓ} (with ℓ ≤ k) be F -terms; then

r_{1} · v(f_{1}) + ⋯ + r_{ℓ} · v(f_{ℓ}) + r_{ℓ+1} · a_{ℓ+1} + ⋯ + r_{k} · a_{k}  (3)

(where each a_{i} is a Γ-variable or a Γ-constant) is a general Γ-term. Moreover we remark that such a Γ-term can be easily rewritten as

\frac{1}{N} (v(f) + s_{ℓ+1} · a_{ℓ+1} + ⋯ + s_{k} · a_{k})

where N, s_{j} ∈ ℤ^{>0}.

When we want to make computations inside the algebraic closure of some explicitly given valued field (K, V) we have to use the theory ACVF(K, V) where the elements of K and Γ_{K} are added as constants and the diagram of the valued field (K, V) is added as a set of axioms.

The theory DOAG_{∞} of divisible ordered Abelian groups with last element ∞ admits quantifier elimination; hence it is sufficient to eliminate the F -quantifiers from an L-formula ϕ: we obtain an F -quantifier free L-formula ϕ′ (most of the time, this formula has more Γ-quantifiers than ϕ), and we can conclude using the quantifier elimination of DOAG_{∞}.

This strategy allows us to get a new algorithmic proof of theorem 3.1, which is the topic of the third section of [8]: The theory ACVF(L) admits quantifier elimination.

3.1 Ultrametric Graphs. To prove theorem 3.1, we will need a lemma about ultrametric graphs. Let Γ be the divisible ordered Abelian group Γ_{K^{ac}}. A graph of vertices p_{1}, …, p_{n} is a subset G of {p_{1}, …, p_{n}}^{2} such that if (p_{i}, p_{j}) ∈ G, then (p_{j}, p_{i}) ∈ G. If (p_{i}, p_{j}) ∈ G, then it is an edge of G. The graph will be called complete if every pair (p_{i}, p_{j}) is an edge.

We consider graphs labeled by elements of Γ ∪ {∞}: to each edge (p_{i}, p_{j}) we associate an element ε_{ij} ∈ Γ ∪ {∞}, and we impose that ε_{ij} = ε_{ji}. Such a graph is called ultrametric if every triangle in it is an ultrametric triangle, that is, has two vertices labeled by the same element of Γ, and the third one is labeled by a greater or equal element. We can put ε_{ii} = ∞ as a convention, so that degenerated triangles are ultrametric.

If we define

t(ε_{ij}, ε_{ik}, ε_{jk}) :⇔ (ε_{ij} = ε_{ik}) ∧ (ε_{ij} ≤ ε_{jk}) ,

then

T (ε_{ij}, ε_{ik}, ε_{jk}) :⇔ t(ε_{ij}, ε_{ik}, ε_{jk}) ∨ t(ε_{ik}, ε_{jk}, ε_{ij}) ∨ t(ε_{jk}, ε_{ij}, ε_{ik})

is the formula asserting that (p_{i}, p_{j}, p_{k}) is an ultrametric triangle inside the graph G.

The complete graph of vertices p_{1}, …, p_{n} with edges labeled by ε_{ij} is ultrametric if the following formula is true:

⋀_{i<j<k} T (ε_{ij}, ε_{ik}, ε_{jk}) .

In an algebraically closed valued field, let a_{1}, …, a_{n} be fixed elements. Let ε_{ij} = v(a_{i} − a_{j}). Then the complete graph of vertices a_{1}, …, a_{n} and of edges (a_{i}, a_{j}) labeled by ε_{ij} is ultrametric.

Lemma 3.2 (Ultrametric graphs) In any formal theory of valued fields implying that the residue field is infinite, the assertion

∃_{F} x ⋀_{i=1,...,n} v(x − a_{i}) = β_{i}

is equivalent to the formula expressing that the complete graph of vertices a_{1}, …, a_{n} and x, with edges (a_{i}, x) labeled by β_{i}, is ultrametric. The triangles (a_{i}, a_{j}, a_{k}) being ultrametric, this is equivalent to ⋀_{i<j} T_{ij} where T_{ij} is T (ε_{ij}, β_{i}, β_{j}).

Proof Let S_{i}(x) be the formula v(x − a_{i}) = β_{i}. We prove that

(∃_{F} x ⋀_{i} S_{i}(x)) ⟺ ⋀_{i<j} T_{ij} .

The implication ⟹ is clear. For the reverse implication ⟸, we first note that

(T_{ij} ∧ (β_{j} < β_{i})) ⟹ β_{j} = ε_{ij} ,

and that

(β_{j} = ε_{ij} ∧ (β_{j} < β_{i}) ∧ S_{i}(x)) ⟹ S_{j}(x) .

Thus we have the following implication:

(T_{ij} ∧ (β_{j} < β_{i}) ∧ S_{i}(x)) ⟹ S_{j}(x) .  (4)

Hence we need to keep only those indices i for which β_{i} is maximal among β_{1}, …, β_{n}. Let β = max{β_{1}, …, β_{n}} and I_{1} = {i ∈ {1, …, n} : β_{i} = β}. Assume w.l.o.g. that 1 ∈ I_{1}. We have

⋀_{i<j} T_{ij} ∧ ⋀_{i∈I_{1}} S_{i}(x) ⟹ ⋀_{1=1,...,n} S_{i}(x)

Note that for i, j ∈ I_{1}, T_{ij} is equivalent to ε_{ij} ≥ β, and that S_{i}(x) is the formula v(x − a_{i}) = β. We show that

⋀_{i<j, i,j∈I_{1}} T_{ij} ⟹ ∃_{F} x ⋀_{i∈I_{1}} v(x − a_{i}) = β .

If β = ∞, we have T_{ij} ⟹ (a_{i} = a_{j}) for all i, j ∈ I_{1}, and in this case we take x = a_{i} for any i ∈ I_{1}. Now assume that β < ∞. If ε_{ij} > β, we obtain (S_{i}(x) ∧ T_{ij}) ⟹ S_{j}(x). We consider the following case distinction:

• If ε_{ij} > β for all i, j ∈ I_{1} then (⋀_{i<j i,j∈I_{1}} T_{ij} ∧ S_{1}(x)) ⟹ ⋀_{i∈I_{1}} S_{i}(x). The formula ∃_{F} x S_{1}(x) being always true, we have ⋀_{i<j} T_{ij} ⟹ ∃_{F} x ⋀_{i} S_{i}(x).

• Else, we take in I_{1} a subset I_{2} which is maximal for the property that ε_{ij} = β for all indices i, j ∈ I_{2}. It suffices to show that ∃_{F} x ⋀_{i∈I_{2}} S_{i}(x), since from the definition of I_{2} we have

( ⋀_{i<j, i,j∈I_{1}} T_{ij} ∧ ⋀_{i∈I_{2}} S_{i}(x)) ⟹ ⋀_{i∈I_{1}} S_{i}(x) .

We can assume w.l.o.g. that 1 ∈ I_{2}. We denote the natural map from V^{ac} to V^{ac}/M_{V^{ac}} = \overline{K^{ac}} by x ↦ res x. We fix z ∈ K^{ac} such that v(z) = β. The field \overline{K^{ac}} is infinite since it is algebraically closed; thus we can choose x ∈ K^{ac} such that

⋀_{i∈I_{2}} res (\frac{x − a_{1}}{z} ) ≠ res (\frac{a_{i} − a_{1}}{z} ) .

This x verifies v(x − a_{i}) = β, for all i ∈ I_{2} . This concludes the proof.

Remark 3.3 We can give a geometric description of the set

S = {x ∈ K^{ac} : ⋀_{i=1,...,n} v(x − a_{i}) = β_{i}} .

We use the notations of the proof. Set C_{β}(a) = {x : v(x − a) = β}. We have

S = ⋂_{i=1,...,n} C_{β_{i}}(a_{i}) = ⋂_{i∈I_{1}} C_{β}(a_{i}) .

If β = ∞, S is reduced to one element in K. Now suppose β < ∞. If ε_{ij} > β for all i, j ∈ I_{1}, then S = C_{β_{i}}(a_{i}) for all i ∈ I_{1}. If for some i, j ∈ I_{1}, ε_{ij} = β, take I_{2} as in the proof. We have S = ⋂_{i∈I_{2}} C_{β}(a_{i}). Suppose that 1 ∈ I_{2}. The set C_{β}(a_{1}) is an infinite disjoint union of open disks B_{β}^{∘}(ζ) = {x : v(x − ζ) > β}, where v(ζ − a_{1}) = β. There is a bijection between the disks B_{β}^{∘}(ζ) and the residue field of K^{ac}, given by

B_{β}^{∘}(ζ) ↦ f(ζ) = res (\frac{ζ − a_{1}}{z} ) .

We have the following equality:

S = ⋂_{i∈I_{2}} C_{β}(a_{i}) = ⋃_{{v(ζ−a_{1})=β \atop ∀i∈I_{2}\\{1\} f(ζ)≠f(a_{i})}} B_{β}^{∘}(ζ) .

This union is nonempty because there are infinitely many values possible for f(ζ), but only finitely many for f(a_{i}).

Remark 3.4 Another formulation of lemma 3.2 is that we have a quantifier elimination for linear formulas in ACVF(L): given a formula

∃_{F} x ⋀_{i} v(x − x_{i}) = β_{i}

we put ε_{ij} = v(x_{i} − x_{j}), and the above formula is equivalent to

⋀_{i<j} T (ε_{ij}, β_{i}, β_{j}) .

An easy consequence is the following lemma:

Lemma 3.5 Take any complete ultrametric graph of vertices p_{1}, …, p_{n}, with edges labeled by ε_{ij} ∈ Γ ∪ {∞}, and elements x_{1}, …, x_{l} ∈ K^{ac} (with l < n), such that v(x_{i} − x_{j}) = ε_{ij} for all i, j ≤ l. Then there exist x_{l+1}, …, x_{n} ∈ K^{ac} such that v(x_{i} − x_{j}) = ε_{ij} for all i, j.

3.2 Univariate existential decision procedure. We are going to prove that existential problems in a single variable x can be solved in (K^{ac}, V^{ac}).

Definition 3.6 We define univariate F -conditions by

(i) For any P (X) ∈ K[X], the condition Φ(x) :⇔ P (x) = 0 is a univariate F -condition.

(ii) Take any γ, δ ∈ Γ_{K}, q, r ∈ ℚ^{>0}, and any P (X), Q(X) ∈ K[X]. The condition Φ(x) :⇔ v(P (x)) + q · γ □ v(Q(x)) + r · δ, where □ is either = or <, is a univariate F -condition.

(iii) Take any P (X) ∈ K[X]. The condition Φ(x) :⇔ v(P (x)) < ∞ is a uni-

variate F -condition. (iv) If Φ(x), Ψ(x) are univariate F -conditions, then Φ(x)∧Ψ(x) and Φ(x)∨Ψ(x)

are univariate F -conditions. Conditions of the form (i), (ii) and (iii) are called atomic F -conditions.

Definition 3.7 We define Γ-conditions by

(i) For any δ ∈ Γ_{K} ∪ {∞}, q_{1}, …, q_{n} ∈ ℚ^{>0}, r ∈ {1, n}, the condition Φ(\overline{a}) :⇔ q_{1} · a_{1} + ⋯ + q_{r} · a_{r} □ q_{r+1} · a_{r+1} + ⋯ + q_{n} · a_{n} + δ, where □ is either =, > or <, is a Γ-condition on \overline{a}.

(ii) If Φ(\overline{a}), Ψ(\overline{a}) are Γ-conditions on \overline{a}, then so are Φ(\overline{a})∧Ψ(\overline{a}) and Φ(\overline{a})∨Ψ(\overline{a}). Conditions of the form (i) are called atomic Γ-conditions.

It is well known that such conditions are equivalent to some condition of the following form, which is by definition a disjunctive normal form:

⋁_{i=1}^{n} ⋀_{j=1}^{m_{i}} Φ_{ij} ,

where the Φ_{ij} are atomic conditions. Moreover, given any univariate condition Φ(x), there is an algorithm which computes a disjunctive normal form for Φ(x).

We say that ξ ∈ K^{ac} satisfies a univariate F -condition Φ(x) if Φ(ξ) holds in K^{ac}, and that α_{1}, …, α_{n} ∈ Γ_{K^{ac}} satisfy a Γ-condition Φ(\overline{a}) if Φ(\overline{α}) holds in Γ_{K^{ac}}.

We recall the following result without proof. See Theorem 5.6 in [2] or Corollary 3.1.17 in [7].

Proposition 3.8 (Existential Decision Procedure in DOAG_{∞}) Let Φ(\overline{a}) be a Γ-condition. Then there is an algorithm to decide whether there are some α_{1}, …, α_{n} ∈ Γ_{K^{ac}} satisfying Φ(\overline{a}) or not. If the answer is yes, the algorithm provides such a n-tuple. We call it a witness of the condition.

We now prove the following theorem:

Theorem 3.9 (Univariate Existential Decision Procedure in ACVF) Let Φ(x) be a univariate condition. Then we have an algorithm to decide whether there is some ξ ∈ K^{ac} satisfying Φ(x) or not. If the answer is yes, the algorithm gives a description of a witness ξ ∈ K^{ac} such that Φ(ξ) holds; the algorithm decides whether ξ is unique or not, and if this is the case then ξ is in K^{h}.

Proof We give an existential decision procedure for a conjunction

Φ(x) : ⋀_{i=1}^{n} Φ_{i}(x)

where the Φ_{i}’s are atomic conditions. It suffices to use it several times to obtain an existential decision procedure for a univariate condition put in a disjunctive normal form, and hence for every univariate condition.

• First case: One of the Φ_{i}(x) (let’s say Φ_{1}(x)) is of the form P (x) = 0. Let k = deg P, and ξ_{1}, …, ξ_{k} be the roots of P. Let Q_{1}(x), …, Q_{r}(x) ∈ K[x] be the polynomials appearing in the other Φ_{i}(x)’s. We can use SimVal to obtain the multiset of (r + 1)-tuples of values [(v(ξ_{i}), v(Q_{1}(ξ_{i})), …, v(Q_{r}(ξ_{i})))]_{i=1,...,k}.

It suffices now to check, for each (ν, ν_{1}, …, ν_{r}) in this list, whether the conditions Φ_{1}, …, Φ_{n} are verified:

• for a Φ_{k} of the form Q_{i}(x) = 0, test whether ν_{i} = ∞,

• for a Φ_{k} of the form v(Q_{i}(x))+q·γ □ v(Q_{j}(x))+r·δ, test whether ν_{i} +q·γ □

ν_{j} + r · δ (where □ is either =, > or <).
• for a Φ_{k} of the form v(Q_{i}(x)) < ∞, test whether ν_{i} < ∞.

If there are no (r + 1)-tuples in this multiset such that these conditions are verified, then there is no ξ ∈ K^{ac} satisfying Φ(x); if there are m ≤ k of these multisets satisfying these conditions, we know that m of the roots of P can be chosen for ξ.

If m = 1, then remark 2.8 shows that the corresponding root of P is in K^{h}.

• Second case: Assume now that there is no condition Φ_{i}(x) of the form P (x) = 0 among the Φ_{i}(x). For each i, let P_{i}(x) and Q_{i}(x) be the polynomials appearing in atomic formulas Φ_{i} : v(P_{i}(x)) + q_{i} · γ_{i} □_{i} v(Q_{i}(x)) + r_{i} · δ_{i} (where □_{i} is either =, > or <), and Φ_{i} : v(P_{i}(x)) < ∞ (in that case, set Q_{i} = 1, q_{i} = r_{1} = 1, γ_{i} = 0 and δ_{i} = ∞ for the sequel).

We construct the following formulas:

Φ′(x, \overline{c}, \overline{d}) : (⋀_{i=1}^{n} v(P_{i}(x)) = c_{i} ∧ v(Q_{i}(x)) = d_{i})

Φ′′(\overline{c}, \overline{d}) : (⋀_{i=1}^{n} c_{i} + q_{i} · γ_{i} □_{i} d_{i} + r_{i} · δ_{i}) .

The variables \overline{c} = c_{1}, …, c_{n} and \overline{d} = d_{1}, …, d_{n} stand for elements of Γ_{K^{ac}}. We have

∃x ∈ K^{ac} Φ(x) ⟺ ∃\overline{c}, \overline{d} ∈ Γ_{K^{ac}} ∃x ∈ K^{ac} Φ′(x, \overline{c}, \overline{d}) ∧ Φ′′(\overline{c}, \overline{d}) .

Consider a problem of the following form:

Ψ(x, \overline{b}) : ∃x ∈ K^{ac} ⋀_{i=1}^{m} v(R_{i}(x)) = b_{i} ,

where each R_{i}(X) is a polynomial of K[x], and the b_{i}’s are indeterminates.

We introduce all the roots r_{1}, …, r_{N} of the polynomials R_{1}, …, R_{m}. We can compute N with the algorithm GraphRoots, as well as the values ε_{ij} = v(r_{i} −r_{j}), for all i, j, and the multiplicity μ_{jk} of r_{k} as a root of R_{j}. We have an equivalence

Ψ(x, \overline{b}) ⟺ ∃ x ∈ K^{ac} ∃a_{1} ⋯ a_{N} ∈ Γ_{K^{ac}} ⋀_{i=1}^{N} v(x − r_{i}) = a_{i} ∧ Ψ_{1}(\overline{a}, \overline{b}) ,

where Ψ_{1} is a conjuction of formulas of the form b_{j} = ∑_{k} μ_{jk} · a_{k}.

From the ultrametric graph lemma we have

∃x ∈ K^{ac} ⋀_{i=1}^{N} v(x − r_{i}) = a_{i} ⟺ ⋀_{i<j} T (ε_{ij}, a_{i}, a_{j}) .

Hence we can write that Ψ(x, \overline{b}) is equivalent to a problem in Γ_{K^{ac}} :

Ψ(x, \overline{b}) ⟺ ∃\overline{a} ∈ Γ_{K^{ac}} ⋀_{i<j} T (ε_{ij}, a_{i}, a_{j}) ∧ Ψ_{1}(\overline{a}, \overline{b}) .

Now we can do that for Ψ = Φ′. We obtain that ∃x ∈ K^{ac} Φ′(x, \overline{c}, \overline{d}) is equivalent to ∃\overline{a} ∈ Γ_{K^{ac}} Φ′′′(\overline{a}, \overline{c}, \overline{d}), where Φ′′′(\overline{a}, \overline{c}, \overline{d}) is a Γ-condition. We have proved

∃x ∈ K^{ac} Φ(x) ⟺ ∃\overline{a}, \overline{c}, \overline{d} ∈ Γ_{K^{ac}} Φ′′′(\overline{a}, \overline{c}, \overline{d}) ∧ Φ′′(\overline{c}, \overline{d}) .

We can apply the existential decision procedure for DOAG_{∞} to this formula. If there is no solution, then there is no ξ ∈ K^{ac} satisfying Φ(x). If there is a solution, we can use it together with lemma 3.2 to describe an element ξ ∈ K^{ac} satisfying Φ(x). Of course, there is no unicity in that case.

Remark 3.10 The first case of our proof can in fact be treated as a particular case of the second, replacing P (x) = 0 by v(P (x)) = ∞: in that case the existential decision procedure in DOAG_{∞} will give a_{i} = ∞ for some i, and then v(x−r_{i}) = ∞ implies ξ = r_{i}. However, the proof is clearer with this distinction. Moreover, it would be less easy to show that in the case of unicity, the witness is in K^{h}.

3.3 Quantifier Elimination. Quantifier elimination algorithms very often come from existential decision procedures in the one variable case. If such a decision procedure is “uniform” it can be performed “with parameters”. This gives a good way for eliminating the quantifier in a formula with only one existential quantifier. For the real algebraic case see, e.g., [1] chapter 1. In the present section, we will treat the case of algebraically closed valued fields.

Definition 3.11 Take n ∈ ℕ, and denote by \overline{y} an n-tuple (y_{1}, …, y_{n}) of F - variables. Let C_{1}(\overline{y}), …, C_{m}(\overline{y}) be atomic L-formulas with y_{1}, …, y_{n} as the only free variables.

1. We say that ⋁_{i} C_{i}(\overline{y}) is a finite exclusive disjunction if

∀_{F} \overline{y} ⋁_{i=1}^{m} C_{i}(\overline{y}) ∧ ⋀_{i≠j} ¬C_{i}(\overline{y}) ∨ ¬C_{j}(\overline{y})

holds. In that case we write

ℭ_{i} = \{\overline{y} ∈ K^{n} : C_{i}(\overline{y})\} .

Then K^{n} is the disjoint union of ℭ_{1}, …, ℭ_{m}. The family ℭ_{i} is a definable partition of the space K^{n}. Note that we allow that some ℭ_{i} may be empty.

2. Let D_{ij}(\overline{y}), for i = 1, …, m and j = 1, …, ℓ_{i}, be atomic L-formulas such that ⋁_{ij} D_{ij}(\overline{y}) is a finite exclusive disjunction. We say that ⋁_{ij} D_{ij} is a refinement of ⋁_{i} C_{i} if for all i, we have

C_{i}(\overline{y}) ⟺ ⋁_{j=1}^{ℓ_{i}} D_{ij}(\overline{y}) ,

or, equivalently

ℭ_{i} = ⋃_{j=1}^{ℓ_{i}} 𝔇_{ij} ,

where 𝔇_{ij} = \{\overline{y} ∈ K^{n} : D_{ij}(\overline{y})\}. Note that this union is a disjoint union.

We denote by \overline{Y} an n-tuple of indeterminates Y_{1}, …, Y_{n}. The ring K [\overline{Y} ] is K[Y_{1}, …, Y_{n}]. We can apply the algorithms given in the previous section to polynomials with parameters. Consider P (\overline{Y} , X) ∈ K [\overline{Y} , X] as a polynomial in X with parameters \overline{Y}.

Proposition 3.12 (Algorithms with parameters)

1. The Newton Polygon Algorithm applied to P provides (i) a finite exclusive disjunction ⋁_{i} C_{i}(\overline{y}), (ii) for each i, an integer k_{i} and a multiset [t_{1}(\overline{y}), …, t_{k_{i}}(\overline{y})], where each t_{j}(\overline{y})

is an L_{Γ}-term, such that for all \overline{y} ∈ ℭ_{i}, k_{i} = deg_{X} P (\overline{y}, X), and if [ξ_{1}, … ξ_{k_{i}}] denotes the multiset of roots of P (\overline{y}, X), then [t_{1}(\overline{y}), …, t_{k_{i}}(\overline{y})] is [v(ξ_{1}), …, v(ξ_{k_{i}})]. In other words, in each case of the above exclusive disjunction, the algorithm computes the values of the roots of P (\overline{y}, X).

2. Keep the notation of the previous statement. Let Q_{1}, …, Q_{r} ∈ K [\overline{Y} , X] be polynomials in X with parameters \overline{Y}. The algorithm SimVal applied to P, Q_{1}, …, Q_{r} provides

(i) a refinement ⋁_{ij} D_{ij}(\overline{y}) of ⋁_{i} C_{i}(\overline{y}), (ii) for each case i, j (with j ∈ {1, …, ℓ_{i}}) a multiset of (r+1)-tuples of L_{Γ}-terms

[(t_{s}(\overline{y}), u_{s}^{1}(\overline{y}), …, u_{s}^{r}(\overline{y}))]_{s=1,...,k_{i}},

such that for all \overline{y} ∈ 𝔇_{ij}, if [ξ_{1}, … ξ_{k_{i}}] is the multiset of roots of P (\overline{y}, X), then [(t_{s}(\overline{y}), u_{s}^{1}(\overline{y}), …, u_{s}^{r}(\overline{y}))]_{s=1,...,k_{i}} is [(v(ξ_{s}), v(Q_{1}(ξ_{s}), …, v(Q_{r}(ξ_{s})))]_{s=1,...,k_{i}}.

3. Take P_{1}, …, P_{s} ∈ K [\overline{Y} , X]. The algorithm GraphRoots applied to P_{1}, …, P_{s} provides

(i) a finite exclusive disjunction ⋁_{i} C_{i}(\overline{y}), (ii) for each i, an integer N_{i} and a finite family

((μ_{jk})_{j∈[1,s],k∈[1,N_{i}]}, (t_{k,ℓ}(\overline{y}))_{1≤j<ℓ≤N}), where the μ_{jk} are integers and the t_{k,ℓ}(\overline{y}) are L_{Γ}-terms,

such that for all \overline{y} ∈ ℭ_{i}, N_{i} is the number of roots of P_{1} · · · · · P_{s}, and for some ordering (ξ_{1}, …, ξ_{N_{i}}) of these roots, μ_{jk} is the multiplicity of ξ_{k} as a root of P_{j}, and t_{k,ℓ}(\overline{y}) is v(ξ_{k} − ξ_{ℓ}).

Proof For the first statement, write P (\overline{Y} , X) = q_{n}(\overline{y}) · X^{n} + ⋯ + q_{0}(\overline{y}). Consider the exclusive disjunction

(q_{0}(\overline{y}) = … = q_{n}(\overline{y}) = 0) ∨ ⋁_{i=0}^{n} (v(q_{i}(\overline{y})) < ∞ ∧ ⋀_{j=i+1}^{n} q_{n−j}(\overline{y}) = 0) .

In each case of this disjunction the degree in X of P (\overline{y}, X) is fixed. We are going to refine it to obtain the desired disjunction. Apply the Newton Polygon Algorithm in any fixed case of this disjunction: its result depends naturally on a new disjunction, each case of it expressing a different shape for the Newton Polygon of P. More precisely, if m > 0 is deg_{X} P (\overline{y}, X), for each ℓ ≤ m + 1 and each ℓ-tuple (k_{1}, …, k_{ℓ}) of non-negative integers such that 0 = k_{1} < ⋯ < k_{ℓ} = m, we can write a formula C_{m,ℓ,k_{1},...,k_{ℓ}}(\overline{y}) expressing that (k_{1}, v(q_{k_{1}}(\overline{y}))), …, (k_{ℓ}, v(q_{k_{e}ll}(\overline{y}))) are the consecutive vertices of the Newton Polygon of P. In each fixed case C_{m,ℓ,k_{1},...,k_{ℓ}}, the values of the roots are the L_{Γ}-terms \frac{1}{k_{i+1}−k_{i}} (v(q_{k_{i}}(\overline{y})) − v(q_{k_{i+1}}(\overline{y}))).

Example: Set R(\overline{Y} , X) = a(\overline{Y})X^{2} + b(\overline{Y})X + c(\overline{Y}); we omit the parameters \overline{Y} in the sequel: a stands for a(\overline{Y}), and so on.

• If v(a) < ∞, and 2v(b) ≥ v(a) + v(c), then ξ_{1}, ξ_{2} ∈ K^{ac}, the roots of R considered as a polynomial in X, both have value \frac{1}{2}(v(c) − v(a)).

• If v(a) < ∞, and 2v(b) < v(a) + v(c), then there is one root of value v(b) − v(a) and the other of value v(c) − v(b).

• If a = 0 and v(b) < ∞, then there is a single root, of value v(c) − v(b).

• If a = 0 and b = 0 and v(c) < ∞, then there is no root.

• If a = b = c = 0, then ∀x ∈ K^{ac}, R(\overline{y}, x) = 0.

Now we turn to the second statement. The algorithm SimVal applies the Newton Polygon Algorithm to P: this is our first disjunction. Then it computes some Tschirnhaus transformation of P. The degree of P being fixed in each case of the disjunction, this can be done without refining it. The results of this computations are new polynomials in K [\overline{Y} , X]. We apply the Newton Polygon Algorithm to each of these polynomials, after refining the disjunction. We obtain some lists of L_{Γ}-terms, from which we can construct the list we want, under a few conditions to eliminate “bad coincidences” (cf. 2.7); these conditions give rise to a new refinement of the disjunction.

For the third statement, just note that GraphRoots uses SimVal iteratedly; then the result comes from the second statement.

Now we are able to prove theorem 3.1.

Proof of theorem 3.1 We recall that there are classical and easy arguments ([8]) showing that it suffices to eliminate an F -quantifier ∃_{F} x in a formula such as ∃_{F} x ⋀_{k=1,...,n} Φ_{k}(\overline{y}, x), where each Φ_{k}(\overline{y}, x) is either an atomic F -formula like P (\overline{y}, x) = 0 with P (\overline{y}, x) ∈ ℤ[\overline{y}, x], or an atomic Γ-formula. Note that an atomic F -formula P (\overline{y}, x) ≠ 0 can be replaced by the Γ-formula v(P (\overline{y}, x)) < ∞. So we are done if we prove the following proposition.

Proposition 3.13 There is an algorithmic procedure that computes, from a formula ∃_{F} x ⋀_{k=1,...,n} Φ_{k}(\overline{y}, x) (where each Φ_{k}(\overline{y}, x) is either an atomic F -formula like P (\overline{y}, x) = 0 with P (\overline{y}, x) ∈ ℤ[\overline{y}, x], or an atomic Γ-formula), an equivalent quantifier free formula Ψ(\overline{y}).

A geometric form of this proposition is the following (for the real algebraic case see, e.g., theorem 2.2.1 of [1]). Let K be a subfield of L. A basic v-constructible set defined over K in L^{n} is a set of the form \{\overline{x} ∈ L^{n} : Φ(\overline{x})\} where Φ(\overline{x}) is either an atomic F -formula like P (\overline{x}) = 0 with P (\overline{x}) ∈ K[\overline{x}], or an atomic Γ-formula (which is built by using only constants in K and v(K)). A v-constructible set defined over K in L^{n} is any boolean combination of basic v-constructible sets defined over K.

Proposition 3.14 Let L be an algebraically closed valued field, and K a subfield. Then the image π(S) of a v-constructible set S defined over K under the canonical projection from L^{n} onto L^{n−1} is again a v-constructible set defined over K. Moreover, there is an algorithmic procedure that uses only computations inside K to get a description of π(S) from a description of S.

Proof of proposition 3.13 We can apply our univariate decision procedure (theorem 3.9) with parameters in order to eliminate x. This procedure uses Sim-Val and GraphRoots with parameters: it will provide an exclusive disjunction ⋁_{i} C_{i}(\overline{y}), and in each case of this exclusive disjunction, a formula Ψ_{i}(\overline{y}) without F -quantifiers (but perhaps with some new Γ-quantifiers if for \overline{y} ∈ ℭ_{i} we are in the second case of the proof of 3.9) such that

∀\overline{y} ∈ ℭ_{i}, ∃_{F} x ⋀_{k=1,...,n} Φ_{k}(\overline{y}, x) ⟺ Ψ_{i}(\overline{y}) .

Thus we have

∃_{F} x ⋀_{k=1,...,n} Φ_{k}(\overline{y}, x) ⟺ ⋁_{i} C_{i}(\overline{y}) ∧ Ψ_{i}(\overline{y}) .

This concludes the proof.

Remark 3.15 The strategy used in [8] was first to give an elimination for linear formulas, and then a procedure which decreases the degrees of polynomials. There was no geometric idea at first sight, although there may be a geometric content hidden in the proof. We believe that the two procedures are in fact different.

When we use this quantifier elimination with the theory ACVF(K, V) we get as a particular case a decision procedure for a closed formula with coefficients in a valued field K given as in the introduction.

Theorem 3.16 Take a formula

Θ(\overline{y}) : Q_{F}^{1} x_{1} … Q_{F}^{n} x_{n} Φ(\overline{α}, \overline{y}, \overline{x})

where each Q_{F}^{i} is ∀_{F} or ∃_{F} and \overline{α} = α_{1}, …, α_{m} are elements of K. We have an algorithm for computing a quantifier free formula Ψ(\overline{y}) equivalent to Θ(\overline{y}). As a particular case, when \overline{y} is the empty sequence, we can decide whether the formula Θ(\overline{y}) is true in K^{ac} or not. Moreover, if the formula is purely existential, i.e., Q_{F}^{1} , …, Q_{F}^{n} are existential quantifiers ∃_{F}, then the algorithm provides a witness \overline{ξ} ∈ (K^{ac})^{n} such that Φ(\overline{ξ}) is true. If we have a result of unicity such as

∀_{F} \overline{x}, \overline{y} (Φ(\overline{α}, \overline{x}) ∧ (Φ(\overline{α}, \overline{y}) ⟹ \overline{x} = \overline{y}) ,

then this witness is in (K^{h})^{n}.

Proof Let us explain how we get the test point. We apply the quantifier elimination procedure to

Q_{F}^{1} x_{1} … Q_{F}^{n} x_{n} Φ(\overline{a}, \overline{x})

obtained after replacement of each α_{i} by a new indeterminate a_{i}. The result is a quantifier-free formula Ψ(\overline{a}), such that

Q_{F}^{1} x_{1} … Q_{F}^{n} x_{n} Φ(\overline{a}, \overline{x}) ⟺ Ψ(\overline{a}) .

It suffices to test whether Ψ(\overline{α}) is true or not.

If all quantifiers Q_{F}^{i} are existential, we can find formulas Ψ_{k}(\overline{a}, x_{1}, …, x_{k}) for k = 1 to n − 1, such that

∃_{F} x_{1} … ∃_{F} x_{n} Φ(\overline{a}, x_{1}, …, x_{n})
⟺ ∃_{F} x_{1} … ∃_{F} x_{n−1} Ψ_{n−1}(\overline{a}, x_{1}, …, x_{n−1})
⋮  ⋮
⟺  ∃_{F} x_{1} Ψ_{1}(\overline{a}, x_{1})
⟺  Ψ(\overline{a})

If Ψ(\overline{α}) is true and we apply the decision procedure of theorem 3.9 to the sentence ∃_{F} x_{1} Ψ_{1}(\overline{α}, x_{1}), we find ξ_{1} ∈ K^{ac} such that Ψ_{1}(\overline{α}, ξ_{1}) holds. We apply again the decision procedure to ∃_{F} x_{2} Ψ_{2}(\overline{α}, ξ_{1}, x_{2}) and we find ξ_{2} ∈ K^{ac} such that Ψ_{2}(\overline{α}, ξ_{1}, ξ_{2}) holds, and so on. In this way, we find ξ_{1}, …, ξ_{n} ∈ K^{ac} such that Φ(\overline{α}, ξ_{1}, …, ξ_{n}) holds.

If the n-tuple (ξ_{1}, …, ξ_{n}) satisfying Φ(\overline{α}, x_{1}, …, x_{n}) is unique, then ξ_{1} satisfying Ψ_{1}(\overline{α}, x_{1}) is unique and theorem 3.9 shows that ξ_{1} ∈ K^{h}. Repeating this argument n times, we conclude that, in this case, ξ_{1}, …, ξ_{n} ∈ K^{h}.

References

[1] J. Bochnak, M. Coste, M.-F. Roy: Géométrie algébrique réelle, Springer (1987)

[2] M. Coste, H. Lombardi, M.-F. Roy: Dynamical method in algebra: Effective Nullstellensätze, Annals of Pure and Applied Logic 111 (2001), 203–256

[3] J. Della Dora, C. Dicrescenzo, D. Duval: About a new method for computing in algebraic number fields, in: Proceedings Eurocal’85, Springer Lecture Notes in Computer Science 204 (1985), 289–290

[4] C. Dicrescenzo, D. Duval: Algebraic extensions and algebraic closure in Scratchpad, in: Symbolic and algebraic computation (ISSAC 88), Springer Lecture Notes in Computer Science 358 (1989), 440–446

[5] F.-V. Kuhlmann, H. Lombardi: Construction du hensélisé d’un corps valué, Journal of Algebra 228 (2000), 624–632

[6] H. Perdry: Aspects constructifs de la théorie des corps valués, Thèse de doctorat en Mathématiques et Applications de l’Université de Franche-Comté (2001)

[7] D. Marker: Model Theory: An Introduction, Graduate Texts in Mathematics 217, Springer (2002)

[8] V. Weispfenning: Quantifier elimination and decision procedure for valued fields, in: Models and sets, Springer Lecture Notes in Math. 1103 (1984), 419–472