Fields Institute Communications Volume 00, 0000

Ultrametric Fixed Point Theorems and Applications

Erwin Schörner

Mathematisches Institut der LMU München, Theresienstraße 39, D–80333 München

                                   schoerner@lmu.de

Abstract. In this expository paper, we give an overview over the ultrametric fixed point theorems and related results, entering also into their applications in various areas.

In the beginning, let us quote the following well-known result, which has a considerable number of applications:

Classical Banach’s Fixed Point Theorem Let (X, d) be a complete metric space. Then every contracting mapping f : X → X, i.e., there exists an α ∈ ℝ with 0 < α < 1 such that d(f(x), f(y)) ≤ α · d(x, y) holds for all x, y ∈ X, has a (uniquely determined) fixed point.

Prieß-Crampe transferred this classical result to the concept of ultrametric spaces; this was an impulse for various authors to develop some very general ultrametric fixed point theorems with many interesting applications. Since it is impossible to present the whole variety of these recent results, this expository paper can only contain a selection of them. Moreover, we will not always give the most general version of a theorem, if the underlying ideas are better revealed by a more suggestive form. As a compensation, we give a rather detailed list of references at the end of this paper.

First, we want to recall the notions of ultrametric spaces which will be needed in the following. For more details, we refer to the papers [8], [9] and [10] by Prieß-Crampe and Ribenboim.

Let X be a non-empty set, Γ a partially ordered set and Γ_{0} = Γ ∪ {0} with 0 < γ for all γ ∈ Γ. A mapping d : X × X → Γ_{0} is called an ultrametric distance, if the following properties hold for all x, y, z ∈ X and γ ∈ Γ. (D_{1}) d(x, y) = 0 if and only if x = y. (D_{2}) d(x, y) = d(y, x). (D_{3}) d(x, y) ≤ γ and d(y, z) ≤ γ imply d(x, z) ≤ γ. Then (X, d, Γ_{0}) or simply X is called an ultrametric space. In the (very important) special case that Γ is totally ordered, the condition (D_{3}) is equivalent to the ultrametric triangle inequality d(x, z) ≤ Max{d(x, y), d(y, z)} for all x, y, z ∈ X.

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

1991 Mathematics Subject Classification. 54E99, 54H25, 12J10.

The most important examples of ultrametric spaces are induced by valued and semi-valued algebraic structures (K, v, Γ) by defining d(x, y) = v(x − y) for all x, y ∈ K. We remind the reader of the classical concept of a valued field (K, v, Γ), where (Γ, ·, 1, ≤) is a (totally) ordered abelian group with 0 · γ = 0 = γ · 0 for all γ ∈ Γ and v : K → Γ_{0} is a mapping satisfying the following conditions for all x, y ∈ K: (V_{1}) v(x) = 0 if and only if x = 0. (V_{2}) v(x y) = v(x) · v(y). (V_{3}) v(x + y) ≤ Max{v(x), v(y)}. More examples of ultrametric spaces can be found in [8]. We should mention here that it is also very common to consider the value set Γ endowed with the dual order ≤_{d}, i.e., we have x ≤_{d} y if and only if y ≤ x holds; in particular, if (Γ, ≤_{d}) is totally ordered, then (D_{3}) is of the form d(x, z) ≥_{d} Min{d(x, y), d(y, z)}.

For x ∈ X and γ ∈ Γ, the set B_{γ}(x) = {y ∈ X | d(x, y) ≤ γ} is called the ball with centre x and radius γ. For all γ, δ ∈ Γ with γ ≤ δ and x, y ∈ X with x ∈ B_{δ}(y), we have B_{γ}(x) ⊆ B_{δ}(y). In particular, every point of a ball can be regarded as its centre. An ultrametric space (X, d, Γ_{0}) is called spherically complete, if every chain of balls (totally ordered by inclusion) has a non-empty intersection. By [10], an ultrametric space (X, d, Γ_{0}) with totally ordered value set Γ is spherically complete if and only if every pseudoconvergent sequence of (X, d, Γ_{0}) has a pseudolimit in X. More concepts of completeness were discussed by Heckmanns in [1].

A self-mapping f : X → X of an ultrametric space (X, d, Γ_{0}) is said to be strictly contracting, if d(f(x), f(y)) < d(x, y) holds for every x, y ∈ X with x ≠ y.

Now we can state Banach’s Fixed Point Theorem in the version given by Prieß-Crampe, and for the convenience of the reader we will also give a proof of it:

Banach’s Fixed Point Theorem (Prieß-Crampe [6, Satz 3]) An ultrametric space (X, d, Γ_{0}) with totally ordered value set Γ_{0} is spherically complete if and only if every strictly contracting mapping f : X → X has a (uniquely determined) fixed point.

Proof First, let (X, d, Γ_{0}) be a spherically complete ultrametric space and assume that there is a strictly contracting mapping f : X → X without a fixed point. Thus, for all x ∈ X we have π_{x} = d(x, f(x)) ∈ Γ. By Zorn’s lemma, there exists a maximal chain ℭ (with respect to inclusion) in the set of all balls B_{x} = B_{π_{x}}(x) with x ∈ X. Due to the spherical completeness of (X, d, Γ_{0}), there is a z ∈ ⋂ ℭ, and we have B_{z} ⊆ B_{x} for all B_{x} ∈ ℭ, since d(f(x), f(z)) ≤ d(x, z) ≤ π_{x} = d(x, f(x)) implies π_{z} ≤ π_{x} by (D_{3}). Moreover, the maximality of ℭ yields B_{z} = Min ℭ. But π_{f(z)} = d(f(z), ff(z)) < d(z, f(z)) = π_{z} implies B_{f(z)} ⊂ B_{z}, which is a contradiction to the maximality of ℭ. Therefore, f has a fixed point; the uniqueness is an immediate consequence of the contraction property.

Now, let every strictly contracting mapping have a fixed point and assume that (X, d, Γ_{0}) is not spherically complete. Then there exists a strictly decreasing sequence (B_{ϱ})_{ϱ<λ} of balls with ⋂_{ϱ<λ} B_{ϱ} = ∅, where λ denotes a limit ordinal, and B_{ϱ} = B_{π_{ϱ}}(a_{ϱ}) with π_{ϱ} ∈ Γ and a_{ϱ} ∈ X\B_{ϱ+1} for all ϱ < λ. For x ∈ X, there exists a minimal ϱ_{x} < λ such that x ∉ B_{ϱ_{x}}; we put f(x) = a_{ϱ_{x}}; hence by definition, f : X → X is a mapping without any fixed point. But for all x, y ∈ X with x ≠ y and ϱ_{x} < ϱ_{y} we have x ∉ B_{ϱ_{x}} and y ∈ B_{ϱ_{x}} and therefore, since Γ is totally ordered, also d(x, y) > π_{ϱ_{x}} ≥ d(a_{ϱ_{x}}, a_{ϱ_{y}}) = d(f(x), f(y)); thus, f is strictly contracting, which is a contradiction. Therefore, (X, d, Γ_{0}) is spherically complete.

Analyzing this proof, we realize that the existence of a fixed point of a mapping f : X → X, where (X, d, Γ_{0}) is a spherically complete ultrametric space, is already ensured by weaker properties than strict contraction: we only have to assume that f satisfies the following conditions: (C_{1}) f is contracting, i.e., d(f(x), f(y)) ≤ d(x, y) holds for all x, y ∈ X. (C_{2}) f is strictly contracting on orbits, i.e., d(f(x), ff(x)) < d(x, f(x)) holds for

all x ∈ X with x ≠ f(x). Moreover, it is sufficient to consider the order of Γ to be partial.

Fixed Point Theorem (Prieß-Crampe and Ribenboim [7, Theorem 1]) Let (X, d, Γ_{0}) be a spherically complete ultrametric space. If the mapping f : X → X is contracting and strictly contracting on orbits, then f has a fixed point.

In [6], Prieß-Crampe gave an alternative proof of the classical Hensel’s Lemma by means of the Banach’s Fixed Point Theorem. To show that every maximally valued field (K, v, Γ) is henselian, it has to be verified that for every (monic) polynomial p ∈ A[X] and every a ∈ A with p(a) ∈ M and p′(a) ∉ M there exists a b ∈ A satisfying p(b) = 0 and b − a ∈ M; here, A is the valuation ring and M is the valuation ideal of (K, v, Γ), and p′ denotes the (formal) derivative of p. For all x ∈ a + M we have v(p′(x)) = 1, and f(x) = x − \frac{p(x)}{p′(x)} defines a strictly contracting self-mapping of the subset a + M of K. Since (K, v, Γ) is maximal, the induced ultrametric space (K, d_{v}, Γ_{0}) and also (a + M, d_{v}, Γ_{0}) are spherically complete; therefore, the Banach’s Fixed Point Theorem yields a fixed point b ∈ a + M of f, and we have b ∈ A with p(b) = 0 and b − a ∈ M.

In [12], Prieß-Crampe and Ribenboim applied the Fixed Point Theorem to give also a proof of a multi-dimensional Hensel’s Lemma for several polynomials in several indeterminates, which we want to cite in the following form. Again let (K, v, Γ) be a maximally valued field, and let p_{1}, …, p_{n} ∈ A[X_{1}, …, X_{n}] be n polynomials in the n indeterminates X_{1}, …, X_{n} for some n ∈ ℕ. We now assume that there exist a_{1}, …, a_{n} ∈ A such that p_{i}(a_{1}, …, a_{n}) ∈ M holds for all 1 ≤ i ≤ n and det (\frac{∂p_{i}}{∂X_{j}} (a_{1}, …, a_{n}))_{1≤i,j≤n} is a unit in A, where \frac{∂p_{i}}{∂X_{j}} denotes the (formal)

partial derivative of p_{i} with respect to X_{j}. Then [12, Theorem 2] ensures the existence of b_{1}, …, b_{n} ∈ A satisfying p_{i}(b_{1}, …, b_{n}) = 0 for all 1 ≤ i ≤ n and b_{j} − a_{j} ∈ M for all 1 ≤ j ≤ n. Obviously, for n = 1, this is the classical Hensel’s Lemma again.

In the following, we want to mention two important generalizations of the Fixed Point Theorem: the Multi-Valued Fixed Point Theorem and the Common Point Theorem.

First, let f be a multi-valued mapping of an ultrametric space (X, d, Γ_{0}), i.e., a mapping f : X → 𝔓(X), where 𝔓(X) denotes the power set of X. For any x ∈ X, let Π_{x} be the set {d(x, y) | y ∈ f(x)}, and let Min Π_{x} denote the set of all minimal elements of Π_{x}. We consider the following properties for f: (C′_{1}) f is contracting, i.e., for all x, y ∈ X and a ∈ f(x) there is some b ∈ f(y)

such that d(a, b) ≤ d(x, y). (C′_{2}) f is strictly contracting on orbits, i.e., for all x ∈ X and x ≠ a ∈ f(x) there

is some b ∈ f(a) such that d(a, b) < d(x, a).

An element x ∈ X with x ∈ f(x) is called a fixed point of f. Any single-valued mapping φ : X → X can be regarded as a multi-valued mapping by putting f(x) = {φ(x)}. Then, f has the properties (C′_{1}) and (C′_{2}) if and only if φ satisfies the conditions (C_{1}) and (C_{2}), respectively; the fixed points of f and φ coincide. Moreover, for all x ∈ X, the set Π_{x} only consists of the single element d(x, φ(x)). Therefore, the Multi-Valued Fixed Point Theorem is a generalization of the (single-valued) Fixed Point Theorem.

Multi-Valued Fixed Point Theorem (Prieß-Crampe and Ribenboim [7, Theorem 3.1]) Let (X, d, Γ_{0}) be a spherically complete ultrametric space, and let f : X → 𝔓(X) with f ≢ ∅ be a mapping which is contracting and strictly contracting on orbits. Assume that for all x ∈ X the set Min Π_{x} is finite and that very element of Π_{x} has a lower bound in Min Π_{x}. Then f has a fixed point.

Applications of the Multi-Valued Fixed Point Theorem to Logic Programming are presented in the paper [2] of Hitzler and Seda.

A fixed point x of a mapping f : X → X can be regarded as a common point of f and the identity mapping id_{X}. Let us now replace id_{X} by any surjective mapping g : X → X, where f and g satisfy the following conditions: (C_{1}^{∗}) d(f(x), f(y)) ≤ d(g(x), g(y)) holds for all x, y ∈ X. (C_{2}^{∗}) d(f(x), f(y)) < d(g(x), g(y)) holds for all x, y ∈ X with g(x) ≠ f(x) = g(y). An x ∈ X with f(x) = g(x) is called a common point of f and g. Thus in the special case of g = id_{X}, the properties (C_{1}^{∗}) and (C_{2}^{∗}) are equivalent to (C_{1}) and (C_{2}), respectively, and the common points of f and g are exactly the fixed points of f. Hence, also the Common Point Theorem generalizes the Fixed Point Theorem.

Common Point Theorem (Prieß-Crampe and Ribenboim [11, Theorem 6]) Let (X, d, Γ_{0}) be a spherically complete ultrametric space. If the mappings f and g : X → X, where g is surjective, satisfy (C_{1}^{∗}) and (C_{2}^{∗}), then f and g have a common point.

The advantage of the Common Point Theorem is especially revealed in the context of the Hahn structures of formal power series with coefficients in rather weak algebraic objects, e.g. ternary fields, which play an important role as the most general coordinatizing structures of projective planes. In the classical situation, for a field K and a (totally) ordered abelian group (Γ, ·, 1, ≤) we consider the set H of all mappings f : Γ → K with dually well-ordered support supp(f) = {γ ∈ Γ | f(γ) ≠ 0} with the ultrametric distance d(f, g) = Max{γ ∈ Γ | f(γ) ≠ g(γ)} for all f, g ∈ H and we define addition and multiplication on H by setting (f + g)(γ) = f(γ) + g(γ) and (f · g)(γ) = ∑_{α·β=γ} f(α) · g(β) for all f, g ∈ H and γ ∈ Γ, respectively. Due to the algebraic properties of the (commutative) ring (H, +, ·) we only have to verify that the elements of the form 1 + m with v(m) < 1 are units; according to [6], we consider the strictly contracting self-mapping f of the spherical complete ultrametric space (H, d, Γ) defined by f(x) = 1 − x · m, and the Banach’s Fixed Point Theorem yields a (unique) fixed point x_{0} of f, which is the inverse of 1 + m.

In [20], we constructed Hahn ternary fields of formal power series with coefficients in a ternary field (K, S) and exponents in a (totally) ordered loop (Γ, ·, 1, ≤), where d induces a uniform valuation of H in the sense of Kalhoff [3]. Instead of addition and multiplication, we now have to define a ternary operation T on H, where the equation T (m, x, c) = y can geometrically be interpreted as the incidence of the point (x, y) and the line [m, c] with slope m and ordinate c. Furthermore, instead of verifying the existence of an inverse for every non-zero element, we now have to show that for all m, n, c, d ∈ H with m ≠ n there is a unique x ∈ H with T (m, x, c) = T (n, x, d), geometrically spoken, that two lines with different slope have a unique intersection point. Due to the lack of appropriate algebraic properties of H, this cannot canonically be transformed into a fixed point problem; nevertheless, applying the Common Point Theorem we obtain the (uniquely determined) solution x ∈ H of the equation T (m, x, c) = T (n, x, d).

Prieß-Crampe and Ribenboim also proved a Strong Fixed Point Theorem [12, Theorem 1] and, as a corollary of this result, they derived the Attractor Theorem [12, Theorem 2], which will be presented in the sequel.

Let f : X → X′ be a mapping between the ultrametric spaces (X, d, Γ_{0}) and (X′, d′, Γ′_{0}). An element y′_{0} ∈ X′ is called an attractor for f, if there exists a mapping g : X → X such that the following properties hold for all x, t ∈ X with f(x) ≠ y′_{0} and f(t) ≠ y′_{0}: (A_{1}) d′(f(g(x)), y′_{0}) < d′(f(x), y′_{0}). (A_{2}) f(B_{d(x,g(x))}(x)) ⊆ B_{d′(f(x),y′_{0})}(y′_{0}). (A_{3}) If B_{d(x,g(x))}(x) ∩ B_{d(t,g(t))}(t) ≠ ∅, then d′(f(x), y′_{0}) < d′(f(t), y′_{0}) implies

d(x, g(x)) < d(t, g(t)). We shall give a short interpretation of the mapping g. According to (A_{1}), for

any x ∈ X with f(x) ≠ y′_{0} the element f(g(x)) is a better approximation of y′_{0} than f(x); in particular, x is not a fixed point of g. The conditions (A_{2}) and (A_{3}) ensure a certain uniformity of the approximation given by g. Finally, if we want y′_{0} to be contained in the image f(X), we shall assume (X, d, Γ_{0}) to be spherically complete.

Attractor Theorem (Prieß-Crampe and Ribenboim [12, Theorem 2]) Let (X, d, Γ_{0}) be a spherically complete ultrametric space. If y′_{0} is an attractor for the mapping f : X → X′, then y′_{0} ∈ f(X).

Prieß-Crampe and Ribenboim gave an alternative proof of the “crucial step” of Kaplansky’s uniqueness theorem [4, Theorem 5] for the maximal immediate extensions of a valued field in [12, Lemma 10], where the process of transfinite induction is replaced by an application of the Attractor Theorem. For any maximal valued field (K, v, Γ) and any pseudo-convergent sequence ℘ = (a_{ϱ})_{ϱ<λ} of algebraic type with minimal polynomial q ∈ K[X], we have to show the existence of a pseudolimit z of ℘ with q(z) = 0. Taking into account that the maximality of (K, v, Γ) yields the spherical completeness of the set L of all pseudolimits of ℘, it suffices to show that 0 is an attractor for the mapping q|_{L} : L → K.

In [5], F.-V. Kuhlmann studied the Attractor Theorem for mappings f : X → X′ between ultrametric spaces (X, d, Γ_{0}) and (X′, d′, Γ′_{0}) with totally ordered value sets Γ_{0} and Γ′_{0}; again, (X, d, Γ_{0}) is assumed to be spherically complete. In [5, Theorem 1], he was able to show that in this situation an element y′_{0} ∈ X′ is contained in the image f(X), if for every x ∈ X with f(x) ≠ y′_{0}, there is an element u ∈ X satisfying the following conditions: (A_{1}^{∗}) d′(f(u), y′_{0}) < d′(f(x), y′_{0}). (A_{2}^{∗}) f(B_{d(x,u)}(x)) ⊆ B_{d′(f(x),y′_{0})}(y′_{0}).

Hence, in this context we can dispense with the technical condition (A_{3}).

In the following, we cite the Theorem of Immediate Mappings, one of the main results in [5]. The mapping f : X → X′ is called immediate if every y′_{0} ∈ X′ satisfies the conditions (A_{1}^{∗}) and (A_{2}^{∗}). Furthermore, a (generalized) ball is the union of any non-empty family of balls with a common centre.

Theorem on Immediate Mappings (F.-V. Kuhlmann [5, Theorem 2]) Let Γ_{0} and Γ′_{0} be totally ordered and let f : X → X′ be an immediate mapping, where (X, d, Γ_{0}) is a spherically complete ultrametric space. Then f is surjective and also (X′, d′, Γ′_{0}) is spherically complete. Moreover, for every x ∈ X and every (generalized) ball B′ in X′ containing f(x), there is a (generalized) ball B in X containing x with f(B) = B′.

This theorem shows that the immediateness is the appropriate concept to transfer spherical completeness from one ultrametric space to another; moreover, every (generalized) ball in X′ can be regarded as the image of a (generalized) ball in X. In [5], Kuhlmann applied the theorem to integration in differential power series fields. We consider a differential field (K, ∂) endowed with a differential valuation v in the sense of Rosenlicht [15], i.e., v is a valuation of K satisfying the following conditions:

• The field of constants C = {x ∈ K | ∂x = 0} of (K, ∂) is a field of representatives of the residue field of (K, v).

• v (\frac{y∂x}{∂y}) < 1 holds for all x, y ∈ K \ \{0\} with v(x) ≤ 1 and v(y) < 1.

In this situation, for all x, y ∈ K \ {0} with v(x) ≠ 1 and v(y) ≠ 1, the inequalities v(x) ≤ v(y) and v(∂x) ≤ v(∂y) are equivalent. (K, ∂) is said to admit integration if ∂ is surjective; furthermore, (K, ∂, v) is said to admit asymptotic integration if for all y ∈ K \ {0} there exists an x ∈ K such that v(y − ∂x) < v(y) holds, i.e., y has an approximation by the derivative ∂x of x. Obviously, if (K, ∂) admits integration then (K, ∂, v) admits asymptotic integration. Conversely, if (K, ∂, v) admits asymptotic integration then ∂ : (K, d_{v}, Γ_{0}) → (K, d_{v}, Γ_{0}) is an immediate mapping; therefore, under the further assumption that (K, v, Γ) is spherically complete, the Theorem on Immediate Mappings yields that ∂ is surjective, i.e., (K, ∂) admits integration (cf. [5, Theorem 12]). Kuhlmann also applied the Theorem on Immediate Mappings to give an alternative proof of the (multi-dimensional) Hensel’s Lemma (see [5, Theorem 28 and Theorem 29]). Furthermore, applications of this theorem to D-fields are given (see [5, Theorem 10 and Theorem 11]); in this context, we also refer to the papers [17], [18] and [19] by Scanlon.

References

[1] Heckmanns, U. Aspects of Ultrametric Spaces. Queen’s Papers in Pure and Applied Math., Queen’s Univ. Kingston, 1998.

[2] Hitzler, P. and Seda, A. The Fixed-Point Theorem of Priess-Crampe and Ribenboim in Logic Programming. In: Valuation Theory and its Applications. Fields Institute Communications Series.

[3] Kalhoff, F. Uniform Valuations on Planar Ternary Rings. Geom. Dedicata 28 (1988), 337– 348.

[4] Kaplansky, I. Maximal Fields with Valuations. Duke Math. J. 9 (1942), 303–321.

[5] Kuhlmann, F.-V. Maps on ultrametric spaces, Hensel’s Lemma, and differential equations over valued fields. Submitted.

[6] Prieß-Crampe, S. Der Banachsche Fixpunktsatz für ultrametrische Räume. Results in Math. 19 (1990), 178–186.

[7] Prieß-Crampe, S. and Ribenboim, P. Fixed Points, Combs and Generalized Power Series. Abh. Math. Sem. Univ. Hamburg 63 (1993), 227–244.

[8] Prieß-Crampe, S. and Ribenboim, P. Generalized Ultrametric Spaces I. Abh. Math. Sem. Univ. Hamburg 66 (1996), 55–73.

[9] Prieß-Crampe, S. and Ribenboim, P. Homogeneous Ultrametric Spaces J. Algebra 186 (1996), 401–435.

[10] Prieß-Crampe, S. and Ribenboim, P. Generalized Ultrametric Spaces II. Abh. Math. Sem. Univ. Hamburg 67 (1997), 19–31.

[11] Prieß-Crampe, S. and Ribenboim, P. The Common Point Theorem for Ultrametric Spaces. Geom. Dedicata 72 (1998), 105–110.

[12] Prieß-Crampe, S. and Ribenboim, P. Fixed Point and Attractor Theorems for Ultrametric Spaces. Forum Math. 12 (2000), 53–64.

[13] Prieß-Crampe, S. and Ribenboim, P. Ultrametric Spaces and Logic Programming. The Journal of Logic Programming 42 (2000), 59–70.

[14] Prieß-Crampe, S. and Ribenboim, P. A General Hensel’s Lemma. J. Algebra 232 (2000), 269–281.

[15] Rosenlicht, M. Differential Valuations. Pacific J. Math. 86 (1980), 301–319.

[16] Schörner, E. On Immediate Extensions of Ultrametric Spaces. Results in Math. 29 (1996), 361–370.

[17] Scanlon, T. Model theory of valued D-fields. Ph.D. thesis, Harvard University (1997).

[18] Scanlon, T. A model complete theory of valued D-fields. J. Symb. Logic 65 (2000), 1758–1784 [19] Scanlon, T. Quantifier Elimination for the Relative Frobenius, this volume.

[20] Schörner, E. Zur Konstruktion der Hahn-Ternärkörper als Ternärkörper formaler Potenzreihen. Geom. Dedicata 80 (2000), 157–171.