µ±Ç°Î»ÖÃ£ºÊ×Ò³ >> >> 3. Existential Definability of Weierstrass Data.............. 125

# 3. Existential Definability of Weierstrass Data.............. 125

MODEL COMPLETENESS AND SUBANALYTIC SETS
by

Leonard Lipshitz & Zachary Robinson

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 2. Existentially De ned Analytic Functions . . . . . . . . . . . . . . . . 121 3. Existential De nability of Weierstrass Data . . . . . . . . . . . . . . 125 4. The Elimination Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5. Subanalytic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

Contents

The class of real subanalytic sets was de ned by Gabrielov 2], where he proved that the class is closed under complementation. Real subanalytic sets have attracted extensive study; in particular, Hironaka 7] proved uniformization and rectilinearization theorems for real subanalytic sets. In 1], Denef and van den Dries introduced the class of p-adic subanalytic sets and showed how to develop both the real and p-adic theories from a suitable analytic quantier elimination theorem. In 9] an analogous quanti er elimination theorem was proved for K an algebraically closed eld, complete with respect to a non-Archimedean absolute value, using the functions of S = m;n Sm;n. (See below.) That paper developed a theory of subanalytic sets (termed rigid subanalytic sets). This theory was developed further in 10], 11] and 12]. In
Supported in part by the NSF. The authors also thank MSRI for its support and hospitality during part of the preparation of this paper, and Judy Mitchell for her patience in typing several versions of the manuscript.

1. Introduction

120

LEONARD LIPSHITZ & ZACHARY ROBINSON

strongly subanalytic), over such elds. This theory used a class of functions somewhat smaller than T = Tm . (The Tm are the Tate rings of strictly convergent power series over K .) In this paper we prove a quanti er elimination theorem (Theorem 4.2) for algebraically closed extension elds of K in language LE , the language of valued rings augmented with function symbols for the members of E , where E = E (H) is a class of analytic (partial) functions obtained from H S by closing up with respect to \di erentiation" and existential de nition (see below for precise de nitions). For suitable choice of E = E (T ) this gives a quanti er elimination theorem (Corollary 4.4) in LE (T ) (or a quanti er simpli cation theorem, Corollary 4.5, in LT , the language of valued rings augmented with function symbols for the members of T ) suitable for developing the theory of subanalytic sets based on T , which we term K -a noid (Corollaries 5.4 and 5.5). These results have been used by Gardener and Schoutens in their proof, 3], 4], and 22], of a quanti er elimination theorem in the language LD T (= LT enriched by \restricted division" (see below)). Section 2 contains precise de nitions of what we mean by \closed under di erentiation and existential de nitions", in all characteristics. Section 3 gives the Weierstrass Preparation and Division Theorems for these classes of functions that we need for all the Elimination Theorems in Section 4. Section 5 contains the application of the Elimination Theorems to the theory of Subanalytic Sets. We recall some of the basic de nitions. K is a eld complete with respect to a non-Archimedean absolute value j j : K ! R+ . We do not assume that K is algebraically closed. K = fx 2 K : jxj 1g is the valuation ring of K , and K = fx 2 K : jxj < 1g is the maximal ideal of K . Tm = Tm (K ) is the (Tate) ring of strictly convergent power series over K and Sm;n = Sm;n (E; K ) is a ring of separated power series over K (see 13, De nition 2.1.1]). Recall that Tm+n Sm;n and that elements of Sm;n represent analytic functions (K )m (K )n ! K . The language of multiplicatively valued rings is

17]{ 21], Schoutens developed a theory of subanalytic sets (which he termed

L = (0; 1; +; ; j j; 0; 1; ; <):
The symbols 0, 1, +, denote the obvious elements and operations on the eld; 0, 1, denote the obvious elements and multiplication on the value group f0g; j j denotes the valuation and < the order relation on the value group f0g. Section 0 of 1] provides all the background about rst order languages that we will need. A structure F (for a language L0 ) has elimination of quanti ers if every subset of F m de ned by an L0 -formula is in fact de ned by a quanti er free L0 formula. We say that F has quanti er simpli cation (or is model complete) if

MODEL COMPLETENESS AND SUBANALYTIC SETS

121

every subset of F m de ned by an L0 formula is in fact de ned by an existential L0-formula. In 13] we de ned certain open domains in K m which we termed R-domains ( 13, De nition 5.3.3]) and showed that each R-domain U carries a canonical ring of functions denoted O(U ); R-domains generalize the Rational Domains of A noid geometry. As usual K is a complete non-Archimedean valued eld. Let F be a complete eld extending K and let Falg be its algebraic closure. In general Falg will not be complete. However if F 0 Falg is a nitely generated extension of F , then F 0 is complete and hence the power series f 2 Sm;n actually de ne analytic functions (Falg )m (Falg )n ! Falg . By the Nullstellensatz ( 13, Theorem 4.1.1]) there is a map m m : (Falg ) ! Max Tm (F ): Since Tm (K ) Tm (F ) we may therefore regard any R-domain U Max Tm (K ) as a subset of (Falg )m . In this section we set up the formalism for the quanti er elimination theorem. The (not necessarily algebraically closed) eld K will be the eld over which the functions in our language are de ned in the sense that these functions will all be elements of generalized rings of fractions (see below) de ned over K . Formulas in the language de ne subsets of (Falg )m . The Quanti er Elimination Theorem (Theorem 4.2) is uniform in the sense that if ' is de ned over K then there is a quanti er-free formula ' , also de ned over K , such that for each complete F with K F , ' and ' de ne the same subset of (Falg )m . In 1] and 9] the quanti er elimination takes place in a language LD an which has symbols for all functions built up from a suitable class of analytic functions and \restricted division" D, where D(x; y) = x=y if jxj jyj 6= 0 and D(x; y) = 0 otherwise. In this paper the use of \restricted division" is replaced by that of generalized rings of fractions (see de nition below). This is necessary for us because Theorems 3.1 and 3.3 give de nitions of the Weierstrass data in terms of functions, but do not in general produce representations of the Weierstrass data by (de nable) D-terms. (In the special case that H = S , de nability issues drop away and the treatment in this paper is easily seen to be equivalent to the treatment of 9] using restricted division. See Corollary 4.3). De nition 2.1. | (cf. 13, De nition 5.3.1].) We de ne the generalized rings of fractions over Tm inductively as follows: Tm is a generalized ring of fractions, and if A is generalized ring of fractions and f; g 2 A then both Ahf=gi and A f=g] s are generalized rings of fractions.

2. Existentially De ned Analytic Functions

122

LEONARD LIPSHITZ & ZACHARY ROBINSON
m+1 ; : : : ; m+n ] s

is a generalized ring of fractions over Tm+n . De nition 2.2. | Let ' : Tm ! A be a generalized ring of fractions and let : Max A ! Max Tm be the induced map. We de ne the domain of A, Dom A Max Tm, by saying that x 2 Dom A i there is a quasi-rational subdomain U (see 13, De nition 5.3.3]) of Max Tm with x 2 U , such that ?1 (U ) ! U is bijective. Remark 2.3. | (i) The set Dom A does not depend on the representation of the generalized ring of fractions A as a quasi-a noid Tm -algebra. Suppose that ' : Tm ! A and : Tm ! B are isomorphic quasi-a noid Tm -algebras, i.e. there is a K -algebra isomorphism such that

Sm;n = Tm;n

A

@ I@ ' @@

commutes. By the Nullstellensatz 13, Theorem 4.1.1] X := Max Tm \ Max A = Max Tm \ Max B: Let x 2 X and suppose there is a quasi-rational subdomain x 2 U X such that ?1 (U ) ! U is bijective, where : Max A ! Max Tm corresponds to ' (as in De nition 2.2). Let correspond to . Since is an isomorphism, ?1 (U ) ! U is bijective. Since the argument is symmetric in A and B , this shows that Dom A is independent of the presentation of A as a Tm -algebra. (Note however that Dom A is not in general a quasi-a noid subdomain in the sense of 13, De nition 5.3.4] (ii) Let ' : Tm ! A be a generalized ring of fractions. It follows from the Nullstellensatz, ( 13, Theorem 4.1.1]), that Dom Ahf=gi = fx 2 Dom A : jf (x)j jg(x)j 6= 0g; and Dom A f=g] s = fx 2 Dom A : jf (x)j < jg(s)jg: (iii) Let ' : Tm ! A be a generalized ring of fractions. By ground eld extension ( 13, De nition 5.4.9 and Proposition 5.4.10]) A A0 = S0;0 (E; F ) s 0;0 (E;K ) A and we may regard Dom A as a subset of (Falg )m and S each f 2 A as determining an analytic function Dom A ! Falg . In fact, given x 2 Dom A, there is a unique power series f 2 K ] and a rational polydisc x 2 U Dom A such that f (y ? x) converges on U and f (y) = f (y ? x) for all y 2 U .

Tm

-B ?? ??

MODEL COMPLETENESS AND SUBANALYTIC SETS

123

(iv) As we noted in the discussion before De nition 2.1, in this paper we work with generalized rings of fractions instead of with D-functions. Any element f of a generalized ring of fractions A over Tm de nes a partial function on Dom A Max Tm . We may regard f as a total function by assigning f (x) = 0 for x 2 Max Tm n Dom A. It is a consequence of (ii) above that such functions are represented by D-terms in the sense of 9, Section 3.2], and conversely. We will see below that the Weierstrass data of a power series are existentially de nable from f and its partial derivatives. In characteristic p 6= 0, \partial derivatives" must be interpreted as Hasse derivatives which we de ne next. De nition 2.4. | Let f 2 R 1; : : : ; m ] , R a commutative ring, and let t = (t1 ; : : : ; tm ). The Hasse Derivatives of f , denoted D f 2 R ] , = ( 1 ; : : : ; m ) 2 N m , are de ned by the equation X f ( + t) = (D f )( )t : (See 5] or 6, Section 3].) Remark 2.5. | (i) In characteristic zero the Hasse derivatives are constant multiples of the usual partial derivatives. In fact
2Nm

free de nable from each other (cf. De nition 2.7). The following facts are not hard to prove. Proofs can be found in 5] or 6, Section 3]. (ii) In characteristic p 6= 0 the situation is more complicated. If = (0; : : : ; 0; pn ; 0 : : : ; 0) with pn in the ith position denote D by Din. Then the whole family of Hasse derivatives is generated by the Din under composition. n n In particular Dim Dj = Dj Dim and D = D11 D22 : : : Dmm . (iii) Suppose the characteristic is p 6= 0 and let f 2 R 1 ; : : : ; m ] . Fix i; 1 i m, and write

@ j j f = ! : : : !D f: 1 m @ 1 1 : : : @ mm Hence the partial derivatives of f and the Hasse derivatives of f are quanti er

f=

p?1 X j =0

fj ( 1 ; : : : ; i?1 ; ip ;

j i+1 ; : : : ; m ) i :

The power series fj are uniquely determined by this equation, so we may de ne i ;j (f ) := fj : If f converges on a rational polydisc 0 2 U (Falg )m , so do the i ;j (f ). We call the i ;j (f ) the p-components of f . By induction, we de ne the

124

LEONARD LIPSHITZ & ZACHARY ROBINSON
i ;j (g ), 

p+1 -components of f to be the
Thus,

where g is a p-component of f .
j i+1 ; : : : ; m ) i ;

f=

p ?1 X j =0

fj ( 1 ; : : : ; i?1 ; ip ;

where the fj are p -components of f with respect to i . It is not hard to show that the D are existentially de nable from the i ;j and conversely. Indeed the D are linear combinations of compositions of the i ;j with polynomial coe cients, and conversely. (iv) The following properties of the D follow easily from the de nition (a) D0 = id (b) D c = 0 for c 2 R, 6= 0 (c) D (f + g) = D f + D g ? ? Q ? (d) D D = + D + , where + = i i + i i P (e) D (f g) = + 0 = (D f )(D 0 g). (f) a chain rule (see 5]).

the Hasse derivatives.

De nition 2.6. | Let ' : Tm ! A be a generalized ring of fractions and let f 2 A. Using Remark 2.3 we de ne (f ) to be the collection of functions Dom A ! Falg determined by the D f , 2 N m . In other words (f ) is the smallest collection of functions Dom A ! Falg containing f and closed under

De nition 2.7. | Let H m;nSm;n be any collection such that (H) H. (In the most important application H = T = mTm ; another possibility is H = (f1; : : : ; fn).) Let LH := L(0; 1; +; ; ff gf 2H ; j j; 0; 1; ; <)

be the rst-order language of multiplicatively valued rings, augmented by symbols for the functions of H. A subset X (Falg )m is said to be de nable (respectively, existentially de nable, quanti er-free de nable) in LH i there is an LH -formula (respectively, an existential LH -formula, quanti er-free LH -formula) '( 1 ; : : : ; m ) such that (a1 ; : : : ; am ) 2 X , '(a1 ; : : : ; am ) is true. A partial function f : X ! Falg is said to be de nable (respectively, existentially de nable, quanti er-free de nable) in LH i its graph (and domain) are. The H-subanalytic sets discussed in Section 5 are exactly the sets existentially de nable in LH . A function f is quanti er free (respectively, existentially) de nable from functions g1 ; : : : ; g if there is a quanti er-free (respectively,

MODEL COMPLETENESS AND SUBANALYTIC SETS

125

existential) formula ' in the language L of multiplicatively valued rings, such that y = f (x) , '(x; y; g1 (x); : : : ; g (x)): We next de ne the class of functions E (H) all of whose \derivatives" are existentially de nable from H. The Quanti er Elimination Theorem (Theorem 4.2) applies to the language LE (H) where H = (H). Since all functions of E (H) are existentially de nable in LH a corresponding quanti er simpli cation theorem for the language LH follows. De nition 2.8. | The collection E (H) consists of all functions f : X ! Falg such that f 2 A and X = Dom A for some generalized ring of fractions ' : Tm ! A, and such that the members of (f ) are all existentially de nable in LH . We de ne the language LE in analogy to De nition 2.7, i.e., LE is the language of multiplicatively valued rings augmented by symbols for the functions of E (H). The languages LH (or LE (H) ) are three-sorted languages. The three sorts are F , F and jF j. (See 9, Sections 3.1{3.7].) We shall use the following in Section 3. Remark 2.9. | (i) Let Char K = p 6= 0, let f (y) be a convergent power series in y, let y 2 K su ciently near 0, and let  2 N . There is a polynomial f (y) such that f (y) f (y) mod (y ? y)p and f is existentially de nable from the p-components of f with respect to y. To see this write

f=
Pp ?1

p ?1 X j =0

fj (yp )yj

and let f = j =0 fj (y )yj . By Remark 2.5(iii), f is existentially de nable from f . P (ii) If f (x; y) 2 E (H) and f = fi (x)yi then each fi 2 E (H).

p

3. Existential De nability of Weierstrass Data Let A be a generalized ring of fractions over T and let f; g 2 Ah i ] s with f regular of degree s in y (where y is either m or n ). By the Weierstrass Division and Preparation Theorems ( 13, Theorem 2.3.8 and Corollary 2.3.9])
we can write

f = uP

and g = qf + r

126

LEONARD LIPSHITZ & ZACHARY ROBINSON

where u, P , q and r are as described in those theorems. In this section we show that all the members of (u) and (P ) are existentially de nable from (f ) and all the members of (q) and (r) are existentially de nable from (f ) and (g). These results are needed for the Elimination Theorem (Theorem 4.2). Analogous questions in the real case are considered in 23]. For completeness, we include proofs below not only in characteristic p but also in characteristic zero.

Theorem 3.1. | (Weierstrass Preparation for E ) Let ' : Tm ! A be a generalized ring of fractions and let f 2 Ah i ] s . Suppose f is regular of degree s in M (respectively, in N ) in the sense of 13, De nition 2.3.7]. By 13, Corollary 2.3.9], there exist a uniquely determined polynomial P 2 Ah 0 i ] s M ] (respectively, P 2 Ah i 0 ] s N ]) monic and regular of degree s and a unit u 2 Ah i ] s such that
f = u P:
(Here 0 := ( 1 ; : : : ; M ?1 ) and 0 := ( 1 ; : : : ; N ?1 ).) Each member of (u) and (P ) is existentially de nable in L (f ) . Hence if f 2 E (H), then u; P 2 E (H). Proof. | Let y denote the variable (either M or N ) in which f is regular and let x denote the other variables. With this notation the above equation becomes

f (x; y) = u(x; y) ys + as?1 (x)ys?1 +

+ a0 (x)]:

We must show that each member of (u) and (aj ) j = 0; : : : ; s ? 1 is existentially de nable in L (f ) , i.e. from (f ). For each x 2 Dom Ah 0 i ] s (respectively Dom Ah i 0 ] s ), let y1 (x); : : : ; ys (x) be the s roots of the equation f (x; y) = 0 with jyj 1 (respectively < 1). Then the aj (x) are symmetric functions of the yi (x), say aj (x) = j (y 1 (x); : : : ; ys (x)). We consider the cases Char K = 0 and Char K = p 6= 0 separately.

Case (A). | Characteristic K = 0.
By Remark 2.5(i) we may work with the usual partial derivatives instead of the Hasse derivatives.

MODEL COMPLETENESS AND SUBANALYTIC SETS

127

For each partition P : s = s1 + s2 + formula !
s ^ i=1

+ sm , with the si 1, let 'P be the = ys1 +s2 ) ^ : : :

jyij 1 ^ (y1 = y2 =

= ys1 ) ^ (ys1 +1 =

: : : ^ (ys1 +

+sm?1 +1 =

where is < or depending on whether y is a M or N . Hence 'P expresses the fact that y1 is a root of f = 0 of multiplicity s1 , ys1+1 is a root of multiplicity s2 , etc. For each j = 0; : : : ; s ? 1, let 'j (x; wj ) be the formula 9y1 : : : 9ys WP 'P ^ wj = j (y1 ; : : : ; ys)]. Then 'j is an existential de nition of aj (x). We must further show that u and the derivatives of the aj (x) are existentially de nable. Notice that the yi (x) may not be di erentiable even at points where the aj (x) are analytic. Let P (x; y) = ys + as?1 (x)ys?1 + + a0 (x). Then (3.1) f (x; y) = u(x; y)P (x; y): Next we show that u(x; y) is existentially de nable. This is obvious from (3.1) except perhaps when y = yi (x) for some i (i.e. when P (x; y) = 0). Note that 2 s P , @P , @ P , : : : @ P = s! 6= 0 are all existentially de nable. It is now easy @y @y2 @ys to see that if y is an si-fold root of f (x; y) = 0 then u(x; y ) is de ned by @ si f (x; y) = u(x; y) @ si P (x; y). Iterating, we see that @u , @ 2 u ; : : : are all @ysi @ysi @y @y2 existentially de nable from (f ). Di erentiating (3.1) with respect to x1 we get

sm ?1 j ^ @ f ^ ::: ^ (ys1 + +sm?1 +1 ) = 0 ^ (ys1 + +si j j =0 @y i6=j

s^1 j 1? @ f (y ) = 0 ^ : : : = ys ) ^ j 1 j =0 @y

6= ys1+ +sj );

@as?1 s?1 @P @u @a0 @f @u @x1 = @x1 P + u @x1 = @x1 P + u @x1 y + + @x1 : So, if y1 ; : : : ; ys satisfy P (x; y) = 0, then @f u?1 (x; yi ) @x (x; y i ) = a0s?1 yis?1 + + a00 ; (3.2) 1 @a where we write a0j for @xj . If the roots y1 ; : : : ; ys of P = 0 are distinct then 1 the equations (3.2) uniquely determine the a0j . (The coe cient matrix of the
system of linear equations (3.2) is the Vandermonde matrix with determinant Q i<j (yi ? yj ) 6= 0).

128

LEONARD LIPSHITZ & ZACHARY ROBINSON

If yi is a root of P = 0 of multiplicity si we replace the si identical equations in (3.2) by the subsystem

@f @P u?1 (x; yi) @x (x; y i ) = @x (x; y i); 1 1 @2f @2P @P u?1 (x; yi ) @y@x (x; y i ) = @y@x (x; y i) + u?1 (x; yi ) @u (x; y i ) @x (x; y i); @y 1 1 1

We follow the same general outline as in Case A and indicate the necessary k changes. In characteristic zero we used the derivatives @ f (y) to detect the @yk multiplicity of a root y of f = 0. In Characteristic p we use the device of Remark 2.9(i). If we choose p > s then the multiplicity of y as a root of f = 0 is the same as the multiplicity of y as a root of f (y) = 0, and since f is a polynomial in y, the multiplicity of y as a zero of f is existentially de nable from the coe cients of f , which are by Remark 2.9(i) existentially de nable from the p components of f . Hence P is existentially de nable from the pcomponents of f with respect to y and hence from the Hasse derivatives D f for = (0; : : : ; 0; i), i = 0; : : : ; p ? 1. Next we must show that u and all its Hasse derivatives with respect to y are existentially de nable. From the equation f = uP; u is existentially de nable, except when P = 0, i.e. except when y = yi for some i. If y is a zero of P of order s then u(y) is (existentially) de ned using f (y) u(y)P mod (y ? y) +1 where f is the polynomial as in Remark 2.9(i) and p > s. In fact, for any 2 N we can existentially de ne a polynomial u such that u u mod (y ? y) by considering the congruence f uP mod (y ? y) + .

@u and the higher derivatives of the a and u are obtained by iterating. j @x1 Case (B). | Characteristic K = p 6= 0.

to obtain a system of equations that we denote (3.2)0 . The coe cient matrix of the resulting system of equations is nonsingular (see Remark 3.2 below) and @a hence the new system of equations de nes the @xj . Existential de nitions of
1

si @ si P u?1 (x; y i) @ys@?1f@x (x; y i ) = @ysi ?1 @x (x; yi ) + : : : : i 1 1

MODEL COMPLETENESS AND SUBANALYTIC SETS
i Let Dy denote D(0;:::;0;i) . Then i Dy f =

129

X

j +k=i

j k Dy uDy P

i (see Remark 2.5(iv)(e)). Since P is a polynomial in y the Dy P are all quanti er free de nable. We proceed inductively 1 1 1 Dy f = (Dy u)P + uDy P: 1 This de nes (Dy u) except when y = y is a zero of P . But for such y we consider a congruence of the form 1 1 1 Dy f (Dy u)P + uDy P mod (y ? y) : By Remark 2.9(i), for any 2 N we can existentially de ne a polynomial 1 congruent to Dy f mod (y ? y) . We saw above that we can existentially de ne a polynomial u(y) u(y) mod (y ? y) . Hence we can existentially 1 de ne Dy u modulo (y ? y) for any . From this, for large enough, an 1 existential de nition of (Dy u)(y) follows. Next we use 2 2 1 1 2 Dy f = (Dy u)P + (Dy u)(Dy P ) + u(Dy P ) 2 and the same argument to see that we can existentially de ne Dy u mod (y ? y) for any . The same devices allow us to obtain existential de nition of the other Hasse derivative of u and P . We do an example that will convince 2 1 2 1 the reader, and show that Dx1 Dy u and Dx1 Dy P are existentially de nable. i i j (Here Dx1 = D(i;0;:::;0) ). Observe also that Dx1 Dy = D(i;0;:::;0;j ).) We again start with the equation f = uP: Thus 1 1 1 Dx1 f = (Dx1 u)P + u(Dx1 P ): (3.3) Let the distinct zeros of P be y1 ; : : : ; yd and let yi have multiplicity i . Then 1 Dx1 P , which is a polynomial in y of degree s ? 1 is determined by the congruences 1 1 Dx1 f u(y i )(Dx1 P ) mod (y ? yi ) i ; i = 1; : : : ; d: 1 Dx1 u is determined by equation (3.3), except where y = yi for some i. But 1 as above Dx1 u mod (y ? yi ) can be existentially de ned by looking at (3.3) 1 mod (y ? yi )p for large enough  and using the fact that Dx1 f mod (y ? yi )p  j 1 j and u mod (y ? y)p are existentially de nable from the Dy Dx1 f and Dy f .

130

LEONARD LIPSHITZ & ZACHARY ROBINSON

2 To obtain the \second derivative" with respect to x1 we apply Dx1 to the equation f = uP : 2 2 1 1 2 (3.4) Dx1 f = (Dx1 u)P + (Dx1 u)(Dx1 P ) + u(Dx1 P ): Looking at this equation modulo the (y ? yi ) i and using the facts that P 0 mod (y ? yi ) i and that we have existentially de ned polynomials congruent 1 to (Dx1 u) and u modulo (y ? yi ) i , gives an existential de nition of (the 2 2 polynomial in y) Dx1 P . Then Dx1 u is determined when y is di erent from all 2 u mod (y ? y ) (for any ) is determined by looking the yi by (3.4) and Dx1 i at (3.4) modulo a high enough power of y ? yi and using the facts that we 1 have existentially de ned polynomials congruent to Dx1 u and u modulo any 1 to (3.3): speci ed power of y ? yi . Next apply Dy 1 1 1 1 1 1 1 1 )+ (3.5) Dy Dx1 f = (Dy Dx1 u)P + (Dx1 u)(Dy P ) + (Dy u)(Dx1 Pu(D1 D1 P ): y x1 1 D1 P by looking at this equation mod (y ? y ) i As above, rst determine Dy x1 i 1 1 1 1 and then determine Dy Dx1 u for y 6= yi , i = 1; : : : ; d and Dy Dx1 u mod (y ? 1 yi ) for any . Finally apply Dy to (3.4) to obtain 1 2 1 2 2 1 1 1 1 Dy Dx1 f = (Dy Dx1 u)P + (Dx1 u)(Dy P ) + (Dy Dx1 u)(Dx1 P ) 1 1 1 1 2 1 2 +(Dx1 u)(Dy Dx1 P ) + (Dy u)(Dx1 P ) + u(Dy Dx1 P ): 1 2 1 2 Exactly as above, rst determine Dy Dx1 P and then Dy Dx1 u for y 6= yi , 1 2 i = 1; : : : ; d, and nally Dy Dx1 u mod (y ? yi ) for any . Remark 3.2. | Assume the characteristic of K is zero. Let s1 + s2 + + sm = s and let the Yij be variables i = 1; : : : ; m; j = 1; : : : ; si. 2 3 s s Y11?1 Y11?2 : : : Y11 1 6 .. .. . . . .. .. 7 6 . . . . 7 6 7 6 Y s?1 Y s?2 : : : Y1s Y 17 1 1s1 6 1s1 7 det 6 .. (Yij ? Yst ) .. . . . .. .. 7 = 6 . . . . 7 (i;j )<(s;t) 6 6 7 .. .. . . . .. .. 7 4 . . . . 5 s?2 s?1 Ymsm Ymsm : : : Ymsm 1 where < is the lexicographic ordering. For each i and j , di erentiate j ? 1 times with respect to Yij . Then set all the Yij = Yi (a new variable) for each i = 1; : : : ; m. The resulting determinant is a nonzero constant times a product of powers of (Yi ? Yj ), i 6= j . Call this function V (Y1 ; : : : ; Ym ). Then the determinant of the coe cient matrix of the system of equations (3.2)0 occurring in the proof of Theorem 3.1 is V (y1 ; : : : ; ym ) 6= 0 where

MODEL COMPLETENESS AND SUBANALYTIC SETS

131

by 13, Theorem 2.3.8] there exist unique elements r 2 Ah 0 i ] s M ] (respectively, r 2 Ah i 0 ] s N ]) of degree s ? 1 and q 2 Ah i ] s such that g = qf + r: 0 := ( 1 ; : : : ; M ?1 ) and 0 := ( 1 ; : : : ; N ?1 ).) Furthermore, each (Here member of (q) and (r) is existentially de nable in L (f ) (g) . Hence if f; g 2 E (H) then q; r 2 E (H). Proof. | We follow the same notational convention as in the proof of Theorem 3.1 | i.e. we let y denote M (respectively N ) and let x denote the P ?1 other variables. Let r = is=1 ri (x)yi , and let y1 (x); : : : ; ys (x) be the roots of f (x; y) = 0. Then

y1 ; : : : ; ym are the distinct roots of f (x; y) = 0, and yi is a root of multiplicity si . Theorem 3.3. | (Weierstrass Division for E ) Let ' : Tm ! A be a generalized ring of fractions and let f; g 2 Ah i ] s . Suppose f is regular of degree s in M (respectively, N ) in the sense of 13, De nition 2.3.7]. Then

(3.6)

g(x; y i) =

s?1 X j =0

rj (x)yj : i

Again in this case we may consider the usual derivatives. If the yi are all distinct then (3.6) has coe cient matrix the Vandermonde matrix and (3.6) determines the rj (x). If yi is a root of f = 0 of multiplicity si , replace the corresponding si identical equations in (3.6) by the equations The resulting system again has nonsingular coe cient matrix (see Remark 3.2) and hence determines the rj (x). Existential de nitions of the derivatives of the rj are obtained in a way similar to that employed in the proof of Theorem 3.1 to obtain those for the derivative of the aj . The same arguments also give existential de nitions of q and its derivatives from (f ) (g). Case (B). | Characteristic K = p 6= 0. We proceed in a way entirely analogous to the characteristic p case of the proof of Theorem 3.1.

Case (A). | Characteristic K = 0.

@  g (x; y ) = @  r (x; y ); @y i @y i

= 0; : : : ; si ? 1:

132

LEONARD LIPSHITZ & ZACHARY ROBINSON

We prove an elimination theorem that both generalizes that of 9] and provides a basis for the theory of a noid subanalytic sets (i.e., the images of a noid maps) as the elimination theorem of 9] provided a basis for the theory of quasi-a noid subanalytic sets. We follow the strategy of 1], rst using parameterized Weierstrass Preparation (and Division) to reduce to the case that some variable occurs polynomially and then using an algebraic elimination theorem. Where 1] used Macintyre's elimination theorem 16] we use the elimination theorem of 24]. To obtain parametrized Weierstrass division from the usual one, 1] used restricted division by coe cients (with parameters). The fact that functions are not canonically represented by terms in a rst order language leads to difculties in our situation, since we have extra de nability conditions to satisfy. It turns out that the generalized rings of fractions (see De nition 2.1) allow us to carry out the necessary divisions while retaining de nability properties in a natural way. Furthermore, 1] works over discretely valued elds K , where multiplication by a uniformizing parameter for the maximal ideal of K can be used to witness strict inequalities. As in 9], we use variables ranging over Falg to witness strict inequalities: our elds Falg are never discretely valued, being algebraically closed. As we remarked in 13, Example 2.3.5], the class of Weierstrass automorphism for the resulting rings of analytic functions is not large enough to transform every nonzero function to one that is regular. Thus we employ Weierstrass Preparation and Division and the double induction of 9] to reduce to an application of the algebraic elimination theorem for algebraically closed valued elds of 24]. Let A be a quasi-a noid algebra. Recall that we showed in 13, Section 5.2] that Ah i ] s A ; ] , so we may write

4. The Elimination Theorem

f=
for any f 2 Ah i ] s .

X

f

; f 2 A;

Lemma 4.1. | Let A be a generalized ring of fractions over T , and let f = P f 2 Ah i ] s . Then there are: c 2 N , A-algebras A , j j + j j c, each a generalized ring of fractions, and elements g 2 A h i ] s such that (i) f (x)g (x; ; ) = f (x; ; ) for every x 2 Dom A , (ii) each g is preregular of degree ( ; ) in the sense of 13, De nition 2.3.7], and S (iii) Dom A = Z (f ) j j+j j c A , where Z (f ) := fx 2 Dom A : f (x; ; ) 0g. If f 2 E , then Z (f ) is quanti erfree de nable in LE and each g 2 E .

MODEL COMPLETENESS AND SUBANALYTIC SETS

133

Proof. | Writing A as a quotient of a ring of separated power series and applying 13, Lemma 3.1.6] to a preimage of f , we obtain a c 2 N and elements h 2 Ah i ] s such that P f = j j+j j c f (1 + h ) and jh (y)j < 1 for all y 2 Max Ah i ] s : (Hence each 1 + h is a unit of Ah i ] s .) For each ( 0 ; 0 ) 2 N m N n with j 0 j + j 0 j c, we de ne the generalized ring of fractions A 0 0 from A in the obvious way so that the inequalities jf 0 0 (x)j jf (x)j for all j j + j j c; jf 0 0 (x)j > jf (x)j for all < 0 and j j + j j c; jf 0 0 (x)j > jf 0 (x)j for all > 0 and j j + j 0j c hold for all x 2 Dom A 0 0 . Indeed, A 0 0 , so de ned, has the property that x 2 Dom A 0 0 if, and only if, f 0 0 (x) 6= 0 and the above inequalities hold. Now, for j j + j j c, f =f 0 0 2 A 0 0 , so we may put

g

0 0

:=

0

0

(1 + h

0 0

)+

X

Finally, suppose f 2 E . Since f (x) 6= 0 for x 2 Dom A , and f (x) 2 E by Remark 2.9(ii), condition (i) implies that g 2 E . To see this inductively, apply D 0 to (i), use the product formula of Remark 2.5(iv)(e) and solve for D 0 g . Furthermore, Z (f ) = fx 2 Dom A : f (x) = 0; j j + j j cg; which is a quanti er-free LE -de nition. Theorem 4.2. | (Quanti er Elimination Theorem) Let H S with H = (H), let E := E (H), and let be an LE -formula. Then there is a quanti er-free LE -formula such that for every complete eld F extending K , Falg \$ ; i.e., and de ne the same subset of (Falg )m . Proof. | Recall that LE (H) is a three-sorted language. We shall use the following convention which will greatly simplify notation. The i will denote variables of the rst sort (that range over F ) and the j will denote variables of the second sort (that range over F ); x will denote a string of variables of sorts one and two. Observe that a quanti ed variable of the third sort (that ranges over jF j) can always be replaced by a quanti ed variable of the rst sort | if v is a variable of the third sort replace it by j j where is a variable of the rst sort. Hence we need only eliminate quanti ed variables of sorts one and two. (Alternatively, a quanti ed variable of the third sort can be eliminated by a direct application of the quanti er elimination theorem

j j+j j c; ( ; )6=( 0 ; 0 )

f f00

(1 + h ); j 0 j + j 0 j c:

134

LEONARD LIPSHITZ & ZACHARY ROBINSON

of 24]). After routine manipulations we may assume that is of the form 9 '(v; x; ; ), where ' is a conjunction of atomic formulas; i.e., formulas of the form t1 (v) jf (x; ; )j t2 (v) jg(x; ; )j; where is either < or =; f; g 2 Ah i ] s \E for some xed generalized ring of fractions over T ; v denotes a string of variables of the third sort and the ti are terms of the third sort containing no variables of sorts one or two. (Observe that the negation of such a formula is a disjunction of such formulas.) For such formulas ', we may de ne (') to be the number of functions in the formula that actually depend on ( ; ). Writing = ( 1 ; : : : ; m ) and = ( 1 ; : : : ; n ); we induct on the triples (m; n; ), ordered lexicographically. Let f1 ; : : : ; f be the functions that occur in ' and depend on ( ; ). Write X X fi = fi = fi 2 Ah i ] s \ E ; where fi 2 A \ E and fi 2 Ah i \ E . Applying Lemma 4.1 to f = f1 yields rings A and elements g 2 A h i ] s preregular of degree ( ; ). Consider the formulas '0 := x 2 Z (f ) ^ ' and ' := x 2 Dom A ^ ': By Lemma 4.1(iii), is equivalent to the disjunction _ 9 '0( ; ) _ 9 ' ( ; ): Let '00 result from '0 by replacing f by 0 and let '0 result from ' by replacing f by f g . Note that ('00 ) < (') and ('0 ) = ('). By induction, we may assume that is of the form 9 '0 . Iterating this procedure reduces us to the case that is of the form 9 ', where the functions occurring in ' are ai (x) fi (x; ; ), and each fi (x; ; ) is preregular of degree ( i ; i ) with fi i i = 1, 1 i . Consider the LE -formulas

'0 := ' ^

 ^

Clearly, is equivalent to the disjunction _ 9 '0 ( ; ) _ 9 'i( ; ); and we may consider the disjuncts separately. Case (A). | = 9 'i( ; ).

i=1

jfi i (x; )j = 1 and 'i := ' ^ jfi i (x; )j < 1:

MODEL COMPLETENESS AND SUBANALYTIC SETS

135

We have that

is equivalent to

Observe that fi i ? Hence, after a Weierstrass automorphism involving only the 's, we may assume that fi i ? n+1 is regular in m . (Recall that Weierstrass automorphisms preserve membership in E .) After applying Weierstrass Preparation (Theorem 3.1) to fi i ? n+1 and Weierstrass Division (Theorem 3.3) with divisor fi i ? n+1 to the other functions in , we may assume that all the functions occurring in are polynomials in m . We may now apply the algebraic elimination theorem of 24] to nd a formula = 9 1 : : : m?1 n+1 equivalent to . Since (m ? 1; n + 1; ( )) < (m; n; (')), we are done by induction. Case (B). | = 9 '0 ( ; ). We have that is equivalent to := 9 m+1 ' ^
Q

n+1' ^ jfi i ? n+1 j = 0: n+1 is preregular of degree ( i ; 0).

9

Y i=1

fi i

!

m+1 ? 1

= 0:
P

Observe that h = ( =1 fi i ) m+1 ? 1 is preregular of degree ( i ; 1; 0). i Hence after a Weierstrass automorphism involving only 1 ; : : : ; m+1 we may assume that h is regular in m+1 . Let fi0 result from fi by multiplying by Q Q ( j 6=i fj j ) m+1 and replacing the coe cient (  =1 fj i ) m+1 (of i ) by 1. j Then each fi0 is preregular of degree (0; i ). Let 0 result from by replacing each fi by fi0 . Then is equivalent to 0 . After a Weierstrass automorphism among the 's we may assume that each fi0 in 0 is regular in n . Applying Weierstrass Preparation (Theorem 3.1) to each fi0 with respect to n and to h with respect to m+1 , and then Weierstrass Division (Theorem 3.3) with divisor h, we may assume that each function occurring in 0 is a polynomial in both n and m+1 . We may now apply the algebraic elimination theorem of 24] to nd a formula 00 = 9 1; : : : ; m ; 1 ; : : : ; n?1 equivalent to . Since (m; n?1; ( )) < (m; n; (')), we are done by induction. Taking H = S (E; K ) = Sm;n (E; K ) we obtain the following strengthened version of the elimination theorem of 9]. Observe that in this case every (partial) function of E (S (E; K )) is represented by a D-term (i.e., a function in the language LD of 9]), and conversely, as in Remark 2.3(iv). an

136

LEONARD LIPSHITZ & ZACHARY ROBINSON

Corollary 4.3. | Falg admits elimination of quanti ers in the language
theorem.

LS(E;K ). The elimination is uniform in F and depends only on S (E; K ). Taking H = T (K ) = Tm (K ) we obtain the following quanti er elimination F and depends only on K .
ination of quanti ers in the language LE (T (K )) . The elimination is uniform in

Corollary 4.4. | (Quanti er Elimination over E (T )) Falg admits elimObserving that every member of E (T ) is existentially de nable over T gives us the following quanti er simpli cation (model completeness) theorem, which provides the basis of the theory of a noid subanalytic sets discussed in Section 5. Corollary 4.5. | (Quanti er Simpli cation over T ) (i) Falg is model complete in the language LT (K ) . (ii) Every subset of (Falg )m de nable by an LT (K ) -formula is de nable by an existential LT (K ) -formula. In this section we explain how the basic properties of subanalytic sets based on the functions in T = Tm (or on any set of functions H S , with H = (H)) follow from Corollary 4.5. De nition 5.1. | Let K be a complete, non-Archimedean valued eld and let H S = m;nSm;n (E; K ). Let F be a complete eld extending K and let Falg be its algebraic closure. A subset X (Falg )m is called globally H-semianalytic i X is de ned by a quanti er-free LH-formula. A subset X (Falg )m is called H-subanalytic i it is the projection of a globally H-semianalytic set (or equivalently is de ned by an existential LH formula). When H = T (K ) we use the terms K -a noid semianalytic and K -a noid subanalytic and when H = S (E; K ) we use the terms (E; K )quasi-a noid-semianalytic and (E; K )-quasi-a noid-subanalytic. The following is a restatement of Theorem 4.2 (the Elimination Theorem). Theorem 5.2. | Let H S (E; K ) with H = (H). The H-subanalytic sets are exactly the LH -de nable sets. In particular, the class of H-subanalytic sets is closed under complementation and (metric) closure. The following can be proved by a small modi cation of the arguments of 9, Section 5] in characteristic zero. The characteristic p 6= 0 case requires a larger modi cation. Details are given in 14].

5. Subanalytic Sets

MODEL COMPLETENESS AND SUBANALYTIC SETS

137

Corollary 5.3. | Every H-subanalytic set is a nite disjoint union of Falg analytic, H-subanalytic submanifolds. We restate the above results in the special case that H = T (K ). Corollary 5.4. | The class of K -a noid-subanalytic sets is closed under

complementation and closure. Corollary 5.5. | Each K -a noid-subanalytic set is a nite disjoint union of K -a noid-subanalytic sets which are also Falg -analytic submanifolds. If X is such a set, this allows us to de ne the dimension of X , dim X , to be the maximum dimension of an Falg -analytic submanifold that occurs in a smooth subanalytic strati cation, or equivalently, the maximum dimension of an Falg analytic submanifold of X . Remark 5.6. | (i) The theory of subanalytic sets developed in 9] (and there termed rigid) is the special case of Theorem 5.2 with H = S . (ii) The Lojasiewicz inequalities proved in 9] for S -subanalytic sets also hold for H-subanalytic sets. This is immediate since H S .

138

LEONARD LIPSHITZ & ZACHARY ROBINSON

1] J. Denef and L. van den Dries. | p-adic and real subanalytic sets. Ann. Math., 128, (1988) 79-138. 2] A. M. Gabrielov. | Projections of semi-analytic sets. Funktsionalnyi Analiz eigo prilozheniya, 2 (1968) 18-30 (Russian). English translation: Funct. Anal. and its Appl., 2 (1968) 282-291. 3] T. Gardener. | Local attening in rigid analytic geometry. Preprint. 4] T. Gardener and H. Schoutens. | Flattening and subanalytic sets in rigid analytic geometry. Preprint. 5] H. Hasse and F. K. Schmidt. Noch eine Begrundung der Theorie der hoheren Di erentialquotienten in einem algebraischen, Funktionenkorper einer Unbestimmten. J. reine agnew. Math., 177 (1937) 215-237. 6] A. Hefez. | Non-re exive curves. Compositio Math., 69 (1989) 3-35. 7] H. Hironaka. | Subanalytic Sets, in Number Theory, Algebraic Geometry and Commutative Algebra in honor of Y. Akizuki. Kinokuniya, 1973, 453-493. 8] L. Lipshitz. | Isolated points on bers of a noid varieties. J. reine angew. Math., 384 (1988) 208-220. 9] L. Lipshitz. | Rigid subanalytic sets. Amer. J. Math., 115 (1993) 77-108. 10] L. Lipshitz and Z. Robinson. | Rigid subanalytic subsets of the line and the plane. Amer. J. Math., 118 (1996) 493-527. 11] L. Lipshitz and Z. Robinson. | Rigid subanalytic subsets of curves and surfaces. To appear in J. London Math. Soc. 12] L. Lipshitz and Z. Robinson. | One-dimensional bers of rigid subanalytic sets. J. Symbolic Logic, 63 (1998) 83{88. 13] L. Lipshitz and Z. Robinson. | Rings of separated power series. This volume. 14] L. Lipshitz and Z. Robinson. | Dimension theory and smooth strati cation of rigid subanalytic sets. In Logic Conference '98, S. Buss, P. Hajek and P. Pudlak, eds. Springer Verlag. To appear. 15] L. Lipshitz and Z. Robinson. | Quasi-a noid varieties. This volume. 16] A. Macintyre. | On de nable subsets of p-adic elds. J. Symbolic Logic, 41 (1976) 605-610. 17] H. Schoutens. | Rigid subanalytic sets. Comp. Math., 94 (1994) 269-295. 18] H. Schoutens. | Rigid subanalytic sets in the plane. J. Algebra, 170 (1994) 266-276. 19] H. Schoutens. | Uniformization of rigid subanalytic sets. Comp. Math., 94 (1994) 227-245. 20] H. Schoutens. | Blowing up in rigid analytic geometry. Bull. Belg. Math. Soc., 2 (1995) 399-417. 21] H. Schoutens. | Closure of rigid semianalytic sets. J. Algebra, 198 (1997) 120-134. 22] H. Schoutens. | Rigid analytic ati cators. Preprint. 23] L. van den Dries. | On the elementary theory of restricted elementary functions. J. Symbolic Logic. 53 (1988) 796-808.

References

MODEL COMPLETENESS AND SUBANALYTIC SETS

139

24] V. Weispfenning. | Quanti er Elimination and Decision Procedures for Valued Fields. In Models and Sets, Aachen, 1983. Lecture Notes in Math., 1103 (1984) 419-472. Springer-Verlag.
Leonard Lipshitz, Department of Mathematics, Purdue University, West Lafayette, IN Zachary Robinson, Department of Mathematics, East Carolina University, Greenville,

47907-1395 USA E-mail : lipshitz@math.purdue.edu

NC 27858-4353 USA E-mail : robinson@math.ecu.edu

¸ü¶àÏà¹ØÎÄµµ: