{'fraction_non_alphanumeric': 0.06346123144058326, 'fraction_numerical': 0.011627906976744186, 'mean_word_length': 3.204329343326994, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 70, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Trees of definable sets over the p-adics

To a definable subset of Z_p^n (or to a scheme of finite type over Z_p) one can associate a tree in a natural way. It is known that the corresponding Poincare series P(X) = \sum_i N_i X^i is rational, where N_i is the number of nodes of the tree at depth i. This suggests that the trees themselves are far from arbitrary. We state a conjectural, purely combinatorial description of the class of possible trees and provide some evidence for it. We verify that any tree in our class indeed arises from a definable set, and we prove that the tree of a definable set (or of a scheme) lies in our class in three special cases: under weak smoothness assumptions, for definable subsets of Z_p^2, and for one-dimensional sets.


Introduction and results
Suppose that X ⊂ Q n p is a definable set in the language of fields. For λ ≥ 0, let X λ be the image of X ∩ Z n p under the projection Z n p ։ (Z/p λ Z) n . In [1], Denef proved that the associated Poincaré series is a rational function in Z. Now the disjoint union T(X) := λ≥0 X λ carries a tree structure defined by the projections (Z/p λ+1 Z) n ։ (Z/p λ Z) n , thus a natural question (which Loeser posed to me) is: can the result of Denef be refined to a result about the structure of the trees? In other words: does there exist a purely combinatorial description of the structure of trees which can arise from definable sets, which implies the above rationality?
The goal of this article is to conjecturally give such a description and to provide some evidence for it. More precisely, for any d ∈ N we define a class of "trees of level d". Our conjecture is then: p is a definable set. Then T(X) is a tree of level dim X.
Here, the dimension of a definable set X is the algebraic dimension of the Zariski closure of X in the algebraic closureQ n p ; see [2]. Whether the conjecture is interesting depends on how tight our definition of trees of level d is. In fact, we will show that it is as tight as possible: Theorem 1.2. For any tree T of level d without leaves, there exists a definable set X of dimension ≤ d such that T(X) ∼ = T .
The author was supported by the Fondation Sciences mathématiques de Paris. 1 The tree T(X) of a set never has leaves, so we might as well forbid leaves in our definition of trees of level d; however, for technical reasons it is better to allow them.
By Theorem 1.2, our definition of level d trees is clearly precise enough to imply rationality of the Poincaré series. However, we will also give an easy direct proof in Proposition 5.2.
The main results of this article are proofs of the conjecture in several special cases. Before stating these results, let us consider an algebraic variant of the trees. For any scheme V of finite type over Z p , we define a tree T(V ) as follows: the set of nodes at depth λ is the image of the map V (Z p ) → V (Z/p λ Z), and the tree structure is given by the maps V (Z/p λ+1 Z) → V (Z/p λ Z). Using this, we can state an algebraic variant of the conjecture: Conjecture 1.3. Suppose that V is a scheme of finite type over Z p . Then T(V ) is a tree of level dim V .
If V is an affine embedded scheme (in A n , say), then we have V (Q p ) ⊂ Q n p , and the two definitions yield the same tree: T(V ) ∼ = T(V (Q p )). Once the definition of a level d tree is given, it will be easy to verify that if the conjecture holds for each set of a finite cover of V , then it also holds for V itself (Proposition 4.5); thus Conjecture 1.1 implies Conjecture 1.3. Therefore in most of the article we will stick to the affine case and the first definition of trees.
From an algebraic point of view, it seems more natural to consider a treeT(V ) whose set of nodes at depth λ is the whole set V (Z/p λ Z), and not only the image of V (Z p ). Indeed, the Poincaré series (1) ∞ λ=0 #V (Z/p λ Z) · Z λ is rational, too, and at the end of this article, we will describe a variant of the conjecture which includes both kinds of trees (and much more). However, for now let us stick to the trees T(V ).
We now present the cases in which we will prove the conjecture. The first one is not very difficult to prove. Under rather weak smoothness assumptions, the tree of a scheme is particularly simple. Theorem 1.4. Suppose that V is a scheme of finite type over Z p , and suppose that for every Z p -valued point x : spec Z p → V , V is smooth at x(η), where η is the generic point of spec Z p . Then T(V ) consists of a finite tree, with copies of T(Z d p ), d ≤ dim V attached to its leaves (d may depend on the leaf ). In particular, T(V ) is a tree of level dim V .
More generally, if V is a non-smooth scheme, then the tree still looks like T(Z d p ) close to any smooth point. On the other hand, we will see on an example (Subsection 3.3) that close to singular points, the trees do get complicated. (In fact trees of definable sets are not essentially more complicated than trees of varieties.) Thus the information contained in a tree of a scheme describes its singularities; this should be closely related to the structure of arc spaces above singularities, as studied in [3].
The more interesting cases of the main conjecture which we will verify are the following. The present proofs of these results crucially rely on the theorem of Puiseux, which is valid only for curves. Thus to generalize them to higher dimension, one will need some new ideas.
Let me mention one more reason for which the trees seem interesting to me. Suppose X 1 and X 2 are two definable subsets of Z n p which are closed in p-adic topology. Then isometric bijections between X 1 and X 2 correspond exactly to isomorphisms of the corresponding trees (see Lemma 3.1). Thus one can interpret trees as a step towards classification of definable sets up to isometry. Indeed, if the main conjecture is true, then up to p-adic closure any definable set is isometric to a set of the form constructed in the proof of Theorem 1.2.
The remainder of this article is organized as follows.
In the next section, we fix our notation. In Section 3, we compute the first trees: we prove Theorem 1.4 and we give an example of a tree of a singular curve. To be able to do that, we first prove a key lemma (Corollary 3.3) which relates the tree of a set to the trees of its fibers.
The trees of Section 3 give an idea of how level d trees should look like; in Section 4, we will actually define them. We will give two versions of the definition: a restrictive one and a more relaxed one; then we will show that both are equivalent. At the end of this section, we will verify some first properties of level d trees.
In Section 5, we will prove statements about given trees of level d, namely Theorem 1.2 and the rationality of the Poincaré series of such a tree. Section 6 is devoted to the proof of the main conjecture for subsets of Q 2 p and for one-dimensional sets. The section starts with a sketch of the principal ideas; then we introduce the main tools we need, namely cell decomposition and a way to understand definable functions on small balls. In Subsection 6.5, we prove a parametrized version of the conjecture for subsets of Q p , and finally we finish the actual proofs.
To conclude, we will present some possible generalizations of the conjecture in Section 7.
2. Notation 2.1. Notation concerning model theory and Q p . We fix a prime p once and for all and work in Q p . We will use a two-sorted language, with one sort for Q p and one for the valuation group Γ. As usual, we take the ring language on Q p , the ordered group language on Γ and a valuation map v : Q p → Γ ∪ {∞}. Note that Γ and v are interpretable in the pure field language (see e.g. [4], Lemma 2.1), so using the two-sorted language is not really different from using the pure field language.
By "definable" we will always mean definable with parameters. We will sometimes identify Γ with Z. In particular, we will write 1 for the valuation of p, and we will often use the cross section Γ → Q × p , λ → p λ . For X ⊂ Q n p , we denote byX the closure of X in the p-adic topology. For x = (x 1 , . . . , x n ) ∈ Q n p and λ ∈ Γ, B(x, λ) := x + p λ Z n p denotes the ball around x of "radius" λ. Moreover, v(x) := min{v(x i ) | 1 ≤ i ≤ ℓ} is the minimum of the valuations of the coordinates. (In other words: v(x) ≥ λ ⇐⇒ x ∈ B(0, λ).) Note that for us a ball always has the same radius in each coordinate.
The following non-standard notation will be very handy: Occasionally, we will work in the algebraic closureQ p of Q p . WriteZ p for the valuation ring andΓ for the value group ofQ p . The definitions of v(x) and x ≈ δ x ′ also make sense in this context. 1 ∈Γ will still denote the valuation of p.
Let e ∈ N ≥1 . The e-th power residue of x ∈ Q × p is the set {y e · x | y ∈ Q × p }. The following statements are well known (and not difficult to prove): x 2 , then x 1 and x 2 have the same e-th power residue. (3) There are only finitely many different e-th power residues.
is either a linear function to Γ or constant ∞. We will use the partial order on the functions It is well known that any subset M ⊂ Γ m which is definable in our two-sorted structure is already definable in (Γ, 0, +, <). We will use the cell decomposition theorem for that structure (see e.g. [5], Theorem 1) to get hold of definable subsets of Γ m . To avoid the rather lengthy definition of cells, we only state an immediate consequence of the cell decomposition theorem.

Lemma 2.3.
(1) For any definable M ⊂ Γ m and any definable function ℓ : M → Γ, there exists a finite partition of M into definable subsets M ′ such that ℓ is linear on each part M ′ .
(2) Any definable subset N ⊂ Γ m × Γ can be written as a boolean combination of sets of the following forms: 3. Trees and Swiss cheese. There are different ways to define trees. Let me fix the variant I will use.

Definition 2.4.
A tree T is a set (of nodes), together with a binary is-child-of relation, which satisfies the usual axioms. However, we do allow trees to be empty. Define the root (if the tree is non-empty), the leaves and the depth depth(v) = depth T (v) of a node v ∈ T as usual.
The class of all trees will be denoted by {Trees}. Define isomorphisms of trees as usual. The product T 1 ×T 2 of two trees is defined layerwise.
If T and T ′ are two non-empty trees and v is a node of T , then we will sometimes construct a new tree by attaching T ′ to v. This means: take the disjoint union of the nodes and then identify the root of T ′ with v.
We already gave a definition of the tree of a set in the introduction. Here is a slight generalization.
with the tree structure induced by inclusion. Set T(X) := T Zp (X).
Example. The tree T({Pt}) of a one-point set is just one infinite path. T(Z n p ) is the infinite tree where each node has exactly p n children.
One technique to determine the tree T(X) of a definable set will be to cut out some balls B i on which X is particularly complicated, compute the trees T Bi (X) separately, compute the tree on the remainder, and then put everything together. We define notation suitable for this. Definition 2. 6. A slice of Swiss cheese (or a cheese, for short) is a set of the form S = B \ i∈I B i , where I is a finite index set and B and B i are balls in Z n p , satisfying B i ⊂ B and B i ∩ B j = ∅ for i = j. The set of balls B i (the "holes") is part of the cheese datum.
Definition 2.7. Let S = B 0 \ i∈I B i ⊂ Z n p be a cheese and X ⊂ Z n p a set. Then the tree T S (X) of X on S is the subtree of T B0 (X) consisting of those nodes B which are not a proper subset of any B i , i ∈ I.
We will only be interested in the tree T S (X) when none of the intersections X ∩ B i is empty. In that case, the balls B i are nodes of T S (X), and the total tree T B0 (X) can be obtained from T S (X) by attaching T Bi (X) to the node B i for each i ∈ I.

Computing the first trees
The definition of a tree of level d is rather involved, so let us first compute a few examples to motivate it. To this end, we first prove some basic lemmas on trees. In particular, we will check that in certain cases the tree of a set is determined (in an easy way) by the trees of its fibers; this is a key reason for trees of definable sets not being too complicated.
3.1. Lipschitz continuously varying fibers. Isomorphisms between the trees T(X) → T(X ′ ) of two sets X, X ′ ⊂ Z n p correspond to isometric bijections between the p-adic closuresX →X ′ . More precisely, the following Lemma holds.
Lemma 3.1. Suppose that X, X ′ ⊂ Q n p are two arbitrary sets and B = B(x 0 , λ), B ′ = B(x ′ 0 , λ ′ ) ⊂ Q n p are two balls. Then bijection φ : induces an isomorphism of trees where x ∈ B ∩X and µ ≥ λ. On the other hand, any isomorphism φ tree : Proof. (2) implies that φ tree is well-defined, and an inverse of φ induces an inverse of φ tree . For the other direction, note that B ∩X is in bijection to the set of infinite paths of T B (X) and define φ(x) as the only element in the intersection µ≥λ φ tree (B(x, µ)).
A crucial point in the whole analysis of trees is the following observation: if X ⊂ Z p × Z p is a set whose vertical fiber X x does not vary too quickly with x, then the tree T(X) is the same as if the fiber would not vary at all. A similar statement is true in higher dimensions. We formulate this as a lemma.
Lemma 3.2. Let X ⊂ Z m p × Z n p be any set and denote by X x := {y ∈ Z n p | (x, y) ∈ X} its fiber at x ∈ Z m p . Suppose that for any x 1 , x 2 ∈ Z m p , any y ∈ Z n p and any Remark. By rescaling, the lemma implies a similar statement for a subset X of any ball B ⊂ Q m p × Q n p .
Combining this lemma with Lemma 3.1, we get: p ×Z n p be any set and denote by X x := {y ∈ Z n p | (x, y) ∈ X} its fiber at x ∈ Z m p . Suppose that for any x 1 , x 2 ∈ Z m p there exists a bijective isometry φ : for any y ∈ Z n p and any λ ≤ v(x 2 − x 1 ). Thus Lemma 3.1 yields T y,λ (X x 1 ) ∼ = T y,λ (X x 2 ) and Lemma 3.2 applies.
Remark. Again, a similar statement holds for a subset X of any ball B ⊂ Q m p ×Q n p . If X satisfies the prerequisites of this corollary, we will say that the fiber X x varies Lipschitz continuously with x.
Remark. An isometry ψ : Z m p × Z n p → Z m p × Z n p fixing the first m coordinates preserves Lipschitz continuity of fibers.

3.2.
Trees of smooth schemes. We will now prove Theorem 1.4 (except for the "in particular" part), i.e. we will determine the tree of a scheme which is sufficiently smooth in the sense of the theorem. Let us first check how to reduce the computation of trees of general schemes of finite type to trees of affine schemes. Proof. Denote by s the special point of spec Z p and by η the generic one. For some given λ ≥ 1, write σ : spec F p → spec Z/p λ Z and π : spec Z/p λ Z → spec Z p for the canonical maps.
Suppose v ∈ V (F p ) is a child of the root of T(V ). Choose i such that V i contains the image of v. The preimage v ′ of v under the map V i (F p ) → V (F p ) is the child of the root of T(V i ) we are looking for; we have to verify that the whole tree below v already appears in T(V i ).
Suppose that w ∈ V (Z/p λ Z) is a node of T(V ) below v, i.e. w • σ = v, and there exists an x ∈ V (Z p ) such that w = x • π. It is clear that w has a preimage w ′ ∈ V i (Z/p λ Z). As V i is open and contains x(s), it also contains x(η), so im x ⊂ V i . Thus x has a preimage x ′ ∈ V i (Z p ), and w ′ = x ′ • π.
Proof of Theorem 1.4. Let V be a scheme as in the theorem. By Lemma 3.4, it suffices to consider affine V ; we fix an embedding V ֒→ A n and determine the tree of V (Q p ) ⊂ Q n p . Fix z ∈ V (Q p )∩Z n p , and suppose that the dimension of V at z is d. We determine the tree on a small ball B := B(z, λ) around z. Write B as a product B X ×B Y , with B X ⊂ Z d p and B Y ⊂ Z n−d p , and denote the coordinates by X 1 , . . . , X d , Y 1 , . . . , Y n−d . To simplify notation, suppose z = 0.
Let f 1 , . . . , f n−d ∈ Z p [X 1 , . . . , X d , Y 1 , . . . , Y n−d ] be generators of the ideal of V in the local ring at 0; regularity of that ring implies that indeed n − d polynomials suffice. Moreover, after possibly permuting coordinates, the matrix ( ∂fi ∂Yj (0)) 1≤i,j≤n−d is invertible over Q p . GL n (Z p ) acts on B by isometries, so by Lemma 3.1, applying such matrices does not change the tree of V (Z p ) on B. Thus by using the column transformations of the smith normal form, we may additionally suppose that ∂fi ∂Xj (0) = 0 for i ≤ n − d, j ≤ d.
Now we apply the implicit function theorem (see e.g. [6]). This yields a power series a with coefficients in Q p , from the variables X i to the variables Y j such that for λ ≫ 0, a converges on B X , and for (x, y) := (x 1 , . . . , x d , y 1 , . . . , y n−d ) ∈ B, we have (x, y) ∈ V (Q p ) if and only if y = a(x). As ∂fi ∂Xj (0) = 0, this power series has no linear term, so for λ sufficiently large and x, x ′ ∈ B X , we get (3), it varies Lipschitz continuously with x; hence Corollary 3.3 yields T B (V (Q p )) ∼ = T(Z d p ). As V (Q p ) ∩ Z n p is compact in p-adic topology, we can cover it by finitely many balls B satisfying T B (V (Q p )) ∼ = T(Z d p ) (possibly for different d, but all satisfying d ≤ dim V ). Moreover, in Z n p any two balls are either disjoint or contained in one another, so we may suppose that these balls B are all disjoint. Thus the total tree of V (Q p ) consists of a finite tree (the subtree of T(Z n p ) whose leaves are exactly the balls used in the cover), with a copy of T(Z d p ) attached to each leaf.
The "in particular" part of Theorem 1.4 will be a direct consequence of Lemma 4.3.

3.3.
Example: the cusp curve. Up to now, we only saw very simple trees. As a more complicated example, let us compute the tree of the cusp curve X = {(x, y) ∈ Z 2 p | x 3 = y 2 } when p = 2. This tree will already contain most of the aspects appearing in the general definition of level d trees.
We will need the following notation: let Y(κ) be the tree which starts with a path of length κ and then has a bifurcation into two infinite paths; in other words, Y(κ) is the tree of a two-point-set From the previous subsection, it is clear that T(X) might be complicated only close to (0, 0); thus we will determine the tree on squares which do not contain (0, 0) and then put them together. The largest squares not containing (0, 0) are of the form B = B((x 0 , y 0 ), κ + 1) with κ = v(x 0 , y 0 ). Fix such x 0 , y 0 , κ.
Write B as a product B X × B Y = B(x 0 , κ + 1) × B(y 0 , κ + 1), and let us analyse the fiber of X at some x ∈ B X . It is X  that there is a suitable choice of roots x 3 1 , x 3 2 such that In particular,

so we may apply Corollary 3.3 and get T
, and all other B Y ∩ X x are empty. Assembling our results, we get the total tree of X (see Figure 1): it consists of an infinite path (the nodes B(0, κ) for κ ≥ 0) with some side branch attached to it. The root has p − 1 additional children, and each of these children is the root of a copy of T(Z p ). (The number p − 1 comes from the fact that F p contains p−1 2 squares and each such square contributes two children.) Finally, for each κ ∈ 2Γ, κ ≥ 2, the node B(0, κ) has p−1 2 additional children, each of which is the root of a copy of T(Z p ) × Y( 1 2 κ − 1).

4.1.
Definition of trees of level d. We will now define a tree datum for a tree of level d and explain how to construct an actual tree out of it. By definition, an arbitrary tree is of level d if it is isomorphic to a tree constructed in this way. Such a tree of level d will consist of a "skeleton" which has only finitely many bifurcations, together with trees of level d − 1 attached to every node in some uniform way. For this uniformity to make sense, we need a parametrized version of these notions. A parametrized tree is a map T : A datum for a level 0 tree defined on M ⊂ Γ m consists of: • a finite tree S (possibly empty) • for each edgeẽ = (ṽ,ṽ ′ ) of S a linear function ℓẽ : M → Γ >0 ∪ {∞} (the "length ofẽ"); the value ∞ is only allowed ifṽ ′ is a leaf of S.
The nodes of S will be called joints; the edges will be called bones. An virtual joint is a leaf following a bone of infinite length; the other joints are real joints.
Note that a given level 0 tree T : M → {Trees} can be described by a tree datum in different ways. In particular, we may replace a bone of T by several bones (of appropriate lengths) with joints in between.
Before we describe level d + 1 trees, we need to describe how side branches of such trees look like. A datum for a side branch of level d (defined on M ) consists of: Now, a datum for a level d + 1 tree (defined on M ) is the following: • an element ρ ∈ Γ >0 • a datum (S, (ℓẽ)) for a level 0 tree (defined on M ), such that for any bonẽ e, the length ℓẽ(κ) mod ρ does not depend on κ; denote by T 0 the tree build out of (S, (ℓẽ)) • for each real jointṽ of T 0 , a side branch datum defining a side branch Bṽ : M → {Trees} of level d • for each boneẽ = (ṽ,ṽ ′ ) of T 0 and each congruence class Ξ ∈ Γ/ρΓ, a side branch datum defining a side branch Bẽ ,Ξ : The tree T (κ) is constructed as follows. Start with T 0 (κ), and to each node v ∈ T 0 (κ) attach a side branch: if v =ṽ(κ) for some jointṽ, then attach Bṽ(κ) to v.
Otherwise v ∈ẽ(κ) for some boneẽ, and depth(v) ∈ Ξ for some Ξ ∈ Γ/ρΓ. Attach Bẽ ,Ξ (κ, depth(v)) to v. T 0 will be called the skeleton of T , and the joints and bones of T are the joints and bones of T 0 . The trees of level d appearing in the side branch data will be called the side trees of T . (Note that it does not make sense to say that a side tree is a subtree: some side trees are not even parametrized by the same set.) An unparametrized tree of level d is a parametrized tree of level d defined on the one-point set M = Γ 0 .

Piecewise level d trees.
In the definition of the previous subsection, we tried to be as restrictive as possible. We will now show how one can weaken the conditions on parametrized level d trees without changing the notion of unparametrized trees. While our first definition is useful to deduce other statements about trees, the new definition will be more convenient to show that a given tree is of level d.
Define a generalized level d tree in the same way as an ordinary one, with the following modifications: given a boneẽ = (ṽ,ṽ ′ ), instead of cutting (5) Nẽ into subsets according to λ mod ρ, we allow Nẽ to be cut into finitely many arbitrary definable subsets N i and use a separate side branch datum Sẽ ,i for each such subset. Moreover, the condition on the length of the bones modulo ρ is removed, and the side trees of a generalized level d tree are also allowed to be generalized. In the proof of this lemma, we will use trees T : M → {Trees} which are only piecewise of level d (normal or generalized): there exists a finite partition of M into definable subsets M i , such that each restricted tree T ↾ Mi is of level d (normal or generalized). As "piecewise" only concerns parameters, Lemma 4.1 is a special case of the following lemma. Proof of Lemma 4.2. We use induction over the level. For d = 0, the statement is trivial.
Suppose now T is piecewise a generalized level d ≥ 1 tree. We have to show that T is also piecewise a normal level d tree. It is clear that for generalized trees, it does not make any difference whether we allow the side trees to be piecewise or not, so using the induction hypothesis, we may suppose the side trees of T to be ungeneralized of level d − 1.
Now consider a boneẽ of T and the corresponding decomposition of the set Nẽ into definable subsets N i (defined in (5) above). When working with ungeneralized trees, we are a priori only allowed to decompose Nẽ into sets of the form Nẽ∩(M ×Ξ) for Ξ ∈ Γ/ρΓ. But modifications of the tree also permit us to do some other cuts: as we are working with piecewise trees, we may intersect Nẽ with sets of the form M ′ × Γ for M ′ ⊂ M definable, and moreover, we may cut the boneẽ into several bones, thus intersecting Nẽ with sets of the form {(κ, λ) | λ ℓ(κ)}. By Lemma 2.3 any definable subset of Nẽ may be obtained in this way, if arbitrary ρ are allowed.
It remains to deal with the requirement to have one single ρ for the whole tree, and that the lengths of the bones have to be constant modulo ρ. But we may use the least common multiple of all ρ we need and then further cut M into definable subsets according to the congruence classes of the lengths of bones.
In this subsection, we introduced a lot of different kinds of trees of level d. In the remainder of the article, we will only use normal and generalized piecewise ones. Having Lemma 4.2 in mind, generalized piecewise trees will be just called piecewise trees.

First properties of level d trees.
To familiarize with level d trees, let us verify the following simple lemmas. (1) An unparametrized level 0 tree consists of a finite tree with finitely many infinite paths attached to it.
(2) Any (piecewise or not) level d tree is also a (piecewise or not) level d + 1 tree.
Suppose moreover thatṽ is a real joint of T 1 and that T 2 (κ) = ∅ for any κ ∈ M . Let T (κ) be the tree one gets by attaching Proof.
(2) By induction, it is enough to verify this for d = 0. A level 0 tree is a level 1 tree with side branches consisting only of the root.
(3) Let the skeleton of T(Z p ) × T consist only of the root, let the finite tree F in the side branch at the root also consist only of the root, and attach T(Z p ) × T to the only leaf of F .
If v lies on the skeleton or on the finite tree at the beginning of a side branch, then this is easy.
It is now easy to see that it suffices to understand trees of affine schemes to get trees of arbitrary schemes.
Proposition 4.5. Let V be an arbitrary scheme of finite type, and suppose that V has an affine covering Proof. Use Lemma 3.4, Lemma 4.4 (applied to the children of the roots of the trees T(X i )) and Lemma 4.3 (4).
We conclude this subsection by a lemma which enables us to decompose the computation of a tree into separate computations on a cheese and its holes. Lemma 4.6. Suppose we have, for each κ in some definable set M ⊂ Γ m , a set X κ ⊂ Z n p and a cheese S κ := Z n p \ i∈I B κ,i , where the index set I does not depend on κ. Suppose moreover that the following holds: Then the whole tree κ → T(X κ ) is piecewise of level d.
Proof. The third condition in particular implies X κ ∩ B κ,i = ∅, so T(X κ ) consists of T Sκ (X κ ) with T Bκ,i (X κ ) attached to it at the node B κ,i for each i ∈ I. Now use Lemma 4.3 (4).

5.
Results on trees of level d 5.1. Rationality of the Poincaré series. In the introduction we promised that level d trees would have rational Poincaré series. Let us now make this precise and verify it.
Definition 5.1. Suppose T is a tree which has only finitely many nodes at each depth. Then we define the Poincaré series of T as follows: The main ingredient to the proof of this proposition is the following lemma: This is, for example, a simplified version of Theorem 4.4.1 of [7].
Sketch of proof. Using cell decomposition in Γ m and by further refining the cells, one reduces the statement to sums of the form where the ℓ i are linear and non-constant, the β i are linear or ∞, and β i (κ 1 , . . . , κ i−1 ) ≥ 0 for all appearing tuples (κ 1 , . . . , κ i−1 ). Now use inductively that geometric series are rational.
Proof of Proposition 5.2. We inductively prove the following parametrized version of the proposition. Let M ⊂ Γ m ≥0 be a definable set and let T : M → {Trees} be a parametrized level d tree. Then the series If we define a level −1 tree to be one consisting only of the root, then we may view a level 0 tree as one having side branches of level −1 (and where additionally the finite trees F at the beginning of the side branches consist only of the root). Adopting this point of view, we start our induction at d = −1.
. Using this, rationality of level d trees implies rationality of level d side branches. Now consider a level d+1 tree T defined on M ⊂ Γ m−1 ≥0 . We may treat each joint and each bone separately. Moreover, on each bone we may treat the different congruence classes modulo ρ separately. The total Poincaré series P T (Z, Y 1 , . . . , Y m−1 ) is then the sum of all these parts.
Consider a boneẽ = (ṽ,ṽ ′ ) and a congruence class Ξ ∈ Γ/ρΓ. Let B be the tree in m parameters describing the side branches at nodes onẽ with depth in Ξ. The contribution of these side branches, including the corresponding nodes onẽ themselves, is Finally consider a (real) jointṽ with side branch B. We define M ′ := {(κ, depth(ṽ)(κ)) | κ ∈ M )} and apply the induction hypothesis to the "shifted" tree The contribution ofṽ and its side branch is

5.2.
Any level d tree appears. We now prove Theorem 1.2: any tree of level d without leaves is isomorphic to a tree of a definable set of dimension d. We introduce some additional notation only for this subsection. The coordinates of any m-tuple a will be denoted by a 1 , . . . , a m . Moreover, for x ∈ Q m p we will set v( The main ingredient to the proof is the following lemma.
Then there exists a definable function u ℓ : X → Z p with the following properties: x for the e-th root of x lying in p Γ · B(1, 1 + v(e)) (which exists by Lemma 2.2). Choose representatives r ν ∈ Z × p of the sets Z × p /B(1, µ). Using these choices, we define u ℓ as follows. First suppose 1 ≤ i ≤ m and 0 ≤ λ < v(e), and consider the definable set This satisfies both required conditions, so we may remove X i,λ from X. We do this successively for all i ≤ m and all λ < v(e) and henceforth suppose that for x ∈ X and all i.
; so the second condition is satisfied unless (7) and (8), we have δ > µ and in particular δ > 0. By In the main proof, we will use the following "Lipschitz union argument" several times: we will have two (or more) sets X, X ′ ⊂ Z m p × Z N p with Lipschitz continuous fibers in the first m variables and would like to infer that the union has Lipschitz continuous fibers, too. This is possible if for any x 1 , x 2 ∈ Z m p , the corresponding isometries φ : X x 1 → X x 2 and φ ′ : In particular, this is true if v(y − y ′ ) does not depend at all on x ∈ Z m p , y ∈ X x , y ′ ∈ X ′ x . Proof of Theorem 1.2. κ and µ will denote elements of Γ m . It will be useful to define κ 0 := µ 0 := 0. We will work inside Z m+N p for some large N ; (x, y) will be an element of Z m+N p , where x ∈ Z m p and y ∈ Z N p . Sometimes, we will also write y = (z,ŷ), with z ∈ Z p andŷ ∈ Z N −1 p . We will denote the fiber of a set X ⊂ Z m+N p at x ∈ Z m p by X x . Let us formulate a suitable parametrized version of the statement, which we will then prove by induction over the level of the tree. We start with the following data: a definable set M ⊂ Γ m , a tree T : M → {Trees} of level d without leaves, and a tuple µ ∈ Γ m >0 . We suppose that for any κ ∈ M , we have κ i−1 + µ i−1 ≤ κ i for i ∈ {1, . . . , m} (i.e. M is contained in an "upper triangle").
The claim we will prove by induction is the following. For N sufficiently large, there exists a definable set X = X(T , µ) ⊂ Z m+N p of dimension at most m + d such that the following holds: • For any κ ∈ M and any x ∈ G κ , T 0,λ(κ) (X x ) ∼ = T (κ).
• For any κ ∈ M , the fiber X x varies Lipschitz continuously with x ∈ G κ . If m = 0, then G = G κ is the one-point set, where κ is the empty tuple, λ(κ) = 0, and the statement becomes T(X) ∼ = T , which is our theorem.
Letṽ 0 , . . . ,ṽ r be the joints of T , including the virtual ones (i.e. the ones at depth infinity). We will start by constructing definable functions f 0 , . . . , f r : G → Z N p which yield the skeleton of T in the following sense. For κ ∈ M and x ∈ G κ , set Let X ′ be the union of the graphs of those functions f i which correspond to virtual joints; the tree T 0,λ(κ) (X ′ x ) is exactly the subtree of T x consisting of the infinite paths. Later, we will define a set X ′′ which yields the side branches of T : X ′′ will be a union such that for any x ∈ G κ , the fiber Z := (X ′′ κ,v ) x is contained in the corresponding node B := ψ x (v) of T x , its tree T B (Z) is isomorphic to the side branch of T (κ) at v, and the intersection of T B (Z) and T x consists only of B. We then set X := X ′ ∪X ′′ .
Thus T 0,λ(κ) (X x ) will have a side branch at B ∈ T x which is isomorphic to the corresponding one of T (κ), and as T (κ) has no leaves, T 0,λ(κ) (X x ) will contain the whole skeleton T x .
We will have to ensure that the fibers X x vary Lipschitz continuously with x ∈ G κ . Our functions f i will satisfy this implies Lipschitz continuity of the fibers of X ′ . We will also prove Lipschitz continuity for each set X ′′ κ,v . Then the Lipschitz union argument yields continuity for X. Now let us construct the functions f i . To get the isomorphism T (κ) ∼ = T x , it suffices to have where d i,j : M → Γ is the "separating depth" of the jointsṽ i andṽ j : the depth of the deepest common ancestor of both. Set f 0 (x) := 0 for all x ∈ G. For j ≥ 1, consider the maximum d max := max{d i,j | 0 ≤ i < j} under the partial order defined by pointwise comparison; note that for j fixed, all d i,j are comparable. Choose any i < j with d i,j = d max and define where u di,j+λ comes from Lemma 5.4. By definition of u di,j+λ , (11) implies (10) for those specific i, j. For other pairs i < j, (10) follows by induction on j. Moreover, (9) follows from the second property of the functions u di,j+λ .
It remains to define the sets X ′′ κ,v . We will show how to do this when v lies on a bone; for joints, a simplified version of the same argument will do. So fix a boneẽ = (ṽ i ,ṽ j ) of T and a congruence class Ξ ∈ Γ/ρΓ. Let N κ := {κ ′ ∈ Ξ | depth(ṽ i )(κ) < κ ′ < depth(ṽ j )(κ)} be the set depths of the corresponding side branches of T (κ), and set N : ). By applying the isometry (x, y) → (x, y − f j (x)) (which neither harms the trees of fibers, nor Lipschitz continuity), we may assume f j (x) = 0. Now notice that in (11), we did not use the first coordinate of Z N p at all, hence ). We will ensure that T x and T B ((X ′′ κ,v ) x ) only intersect in B by choosing Let F be the finite tree at the beginning of the side branch of T corresponding tõ e, Ξ, and for each leaf w of F , let T w : N → {Trees} be the corresponding side tree of level d − 1. Define a shifted setÑ := {(κ, λ(κ) + κ ′ ) | (κ, κ ′ ) ∈ N } and a shifted treẽ T w :Ñ → {Trees},T w (κ, λ(κ) + κ ′ ) = T w (κ, κ ′ ). We apply the induction hypothesis toT w using µ m+1 := depth F (w) (we may suppose depth F (w) > 0); denote by X w := X(T w , (µ 1 , . . . , µ m+1 )) the resulting definable set.
Fix κ ∈ M and x ∈ G κ . For z ∈ Q p , the fiber (X w ) (x,z) is non-empty if and only if z ∈ p λ(κ)+κ ′ B(1, µ m+1 ) for some κ ′ ∈ N κ , and if this is the case, then Now choose an embedding of F into T(Z N −1 p ) and let B(ŷ w , depth(w)) be the image of the leaf w. The map φ w (x, z,ŷ) := (x, z,ŷ + z ·ŷ w ) is an isometry sending G κ × B κ ′ to G κ × p λ(κ)+κ ′ B((1,ŷ w ), depth(w)). We claim that the set Y := w φ w (X w ) is the one we are looking for; more precisely, if κ ∈ M , v ∈ẽ(κ), κ ′ := depth(v) ∈ Ξ, then we claim The finite subtree of T B (Z N p ) with leaves B w is isomorphic to F , and the tree of is the right one. Finally, using Lipschitz continuity in x of the fibers of φ w (X w ∩(G κ ×B κ ′ )) and the Lipschitz union argument, we get Lipschitz continuity of the fibers of X ′′ κ,v . Note that dim X ′ ≤ m and by induction dim X ′′ ≤ (m + 1) + (d − 1); thus dim X ≤ m + d.

The main proofs
In this section we will prove the main conjecture in the interesting cases. We start by sketching the proofs; an overview over the remainder of the section will be given after that sketch.
6.1. Idea of proof. Suppose that X is a definable set of dimension d and that we want to check that T(X) is a level d tree. By compactness (as in the case of smooth varieties) it suffices to understand the tree on a neighborhood of each point ofX. To understand the tree near a given point-without loss 0-we proceed as in the example of the cusp curve: we compute it on balls B which are close to 0 but which do not contain 0; the largest such balls are of the form B = B(p κ x 0 , κ + 1) with v(x 0 ) = 0. The total tree will be of level d if the following two conditions hold: (1) The tree on each ball B looks like the tree of a side branch: after cutting B into finitely many smaller balls, it is of the form T(Z p ) × T , where T is of level d − 1.
(2) If we let κ go to infinity (i.e. the ball B approaches 0), then the trees on B are uniform in κ (in the way required by the definition of level d trees). Now suppose that X is one-dimensional. For simplicity, assume moreover X ⊂ Q 2 p . It is known that such a set X is a subset of an algebraic set V . By applying the theorem of Puiseux to V , close to (0, 0) we can write X as union of branches, each of which is the graph of series of the form f (x) = i a i e √ x i . Taking the e-th root is of course not unique, but as in the cusp example, on each ball B = B(p κ (x 0 , y 0 ), κ+1) we can choose roots in such a way that we get a continuous function f . (In fact, here we might need to replace κ + 1 by κ + µ for some fixed µ > 1.) Now suppose that v(x 0 ) = 0, i.e. B does not lie directly above or below (0, 0). Then for large κ, the graph of f will intersect B only if its derivative at 0 has non-negative valuation. Using this, we get Lipschitz continuity of f : . This will allow us to apply Corollary 3.3, which will finally imply condition (1). If on the other hand v(x 0 ) > 0, then v(y 0 ) = 0, and the same argument applies with coordinates exchanged. All this can be carried out uniformly in κ, and we will get the uniformity required in (2) by having a second look at the Puiseux series describing the branches. If i a i e √ x i is the difference of two such series, then for κ = v(x) ≫ 0, the valuation of this is equal to v(a ι ) + ι e v(x), where a ι is the first non-zero coefficient. This valuation corresponds to the depth of a joint of the side tree; as required, it is linear in κ.
To get a proof for two-dimensional definable subsets of Q 2 p , we use cell decomposition to understand X and then apply the Puiseux series arguments to the centers of cells (which are curves). Lipschitz continuity of these centers yields Lipschitz continuity of the whole fibers of the cells, so Corollary 3.3 implies that the tree on a ball B is of the form T(Z p ) × T , where T is the tree of one fiber.
Of course the tree of a fiber is of level 1 (as its dimension is at most 1), but we need uniformity in κ. To prove this, for each κ we will choose one fiber X κ in the corresponding ball. The cell decomposition of X yields a cell decomposition of each X κ which is "close to uniform"; for example, for κ ≫ 0 a cell center will be close to p ℓ(κ) · a for some fixed a ∈ Q p and some linear function ℓ. This uniformity will allow us to deduce that the parametrized tree κ → T(X κ ) is of level 1.
The remainder of this section is organized as follows. First, we recall cell decompositions; in the next two subsections, we introduce "garlands", which are the right sets to work on when one wants to carry out the above arguments concerning Puiseux series uniformly in κ. In Subsection 6.5, we introduce the close-to-uniform families of sets X κ and prove that they have uniform level 1 trees, and in the last two subsections, we carry out the remainder of the above arguments.
6.2. Cell decomposition. The following is almost the usual definition of a cell decomposition. The only difference is that we are a bit more restrictive on the conditions ⊳ and ⊳ ⊳ in a harmless way; this will save us a few clumsy case distinctions.
where D is a cell in Q n−1 p , α, β : D → Γ ∪ {∞} and c : D → Q p are definable functions, r ∈ Q × p , e ∈ N ≥1 , ⊳ is either ≤ or no condition and ⊳ ⊳ is either ≤ or <. Moreover, we suppose that the projection C → D is surjective and that if ⊳ ⊳ is <, then β = ∞.
We call D the base, c the center, α and β the lower and upper bound, e the exponent and r the residue of C.
(2) A cell decomposition of Q n p is a partition of Q n p into finitely many disjoint cells. If n > 0, then we additionally require that the set of bases of the cells is a cell decomposition of Q n−1 p . By fixing a cell decomposition, we will mean that we also fix the data D, c, α, β, . . . describing the cells.
The usual cell decomposition theorem is the following; see e.g. [2], Section 4.
Lemma 6.2. Let X ⊂ Q n p be a definable set. Then there exists a cell decomposition of Q n p such that X is a union of cells. The following easy fact about one-dimensional cells will be used quite often: Lemma 6.3. There exists a function δ : N ≥1 → Γ >0 such that the following holds.
(1) Let C ⊂ Q p be a cell with center c and exponent e, and suppose x 1 ∈ C and (2) Suppose that C 1 and C 2 are two disjoint cells with centers c 1 and c 2 and common exponent e, and suppose that x 1 ∈ C 1 and Proof. Set δ(e) := 2v(e) + 1. Then (1) follows from Lemma 2.2 (2). For (2), use (1) and the disjointness of C 1 and C 2 to get (for i = 1, 2) v(x 1 −x 2 ) < v(x 1 − c i ) + δ. Now apply the triangle inequality to c 1 , x 1 , c 2 .

Garlands and trees.
Suppose that X ⊂ Z n p , x 0 ∈ Z n p , B 0 = B(x 0 , λ), and B ⊂ B 0 is a ball not containing x 0 . As described in Subsection 6.1, we will try to understand T B (X) uniformly when B approaches x 0 . To be able to speak about uniformity, we have to determine the trees on a whole "garland" of balls approaching x 0 at once. In this subsection, we define these garlands and show that indeed knowing the trees on appropriate garlands suffices to get back the whole tree of X (Lemma 6.6).
The reason to work on garlands and not on the whole of B 0 is essentially that on a garland, it makes sense to speak of one specific branch of the e-th root function, whereas on the whole of B 0 it does not. In the next subsection, we will use this to infer a nice description of definable functions on garlands close to x 0 . Definition 6.4. Suppose we have x 0 ∈ Z n p , λ ∈ Γ ≥0 , and µ, ρ ∈ Γ >0 . A garland G corresponding to x 0 , λ, µ, ρ is a set of the form for some x G ∈ Z n p satisfying v(x G ) = 0 and some Ξ ∈ Γ/ρΓ. We will write M (G) := {κ ∈ Ξ | κ ≥ λ} for the set over which the union goes, and call the subsets G κ := x 0 + p κ B(x G , µ) for κ ∈ M the components of G.
Remark. G κ consists of exactly those x ∈ G which satisfy v(x − x 0 ) = κ.
Definition 6.5. Let X be a subset of Z n p and let G be a garland whose components are G κ , for κ ∈ M := M (G). The tree of X on G is the parametrized tree Lemma 6.6. Let X be a subset of Z n p . Suppose that for each x ∈ Z n p , there are λ, µ, ρ such that for each garland G (corresponding to x, λ, µ, ρ), the parametrized tree Proof. First, for each x ∈ Z n p \X we enlarge the corresponding λ such that B(x, λ)∩ X = ∅. As in the proof of Theorem 1.4 (Subsection 3.2), using compacity of Z n p it suffices to prove that the tree on each ball B(x, λ) is of level d + 1; the whole tree will then consist of a finite tree, with finitely many of the trees T x,λ (X) attached to it.
Now fix x ∈ Z n p , and let λ, µ, ρ be as in the prerequisites (possibly with λ enlarged); we compute the tree T x,λ (X). To simplify notation, suppose x = 0. If 0 / ∈X, then B(0, λ) ∩ X = ∅ and there is nothing to do, thus suppose now 0 ∈X. This implies B(0, κ) ∈ T 0,λ (X) for all κ ≥ λ. We take this as skeleton for T 0,λ (X), with a joint at B(0, λ) and then a single infinite bone. It remains to determine the side branches.
For each garland G, we have a finite partition of {κ ∈ Γ | κ ≥ λ} such that T G is of level d on each set of the partition. We choose a partition of {κ ∈ Γ | κ ≥ λ} such that for each part M , T G is of level d on M for all garlands G. Now we claim that there is a single side branch datum describing the side branch of T Bj (X) leaving the skeleton at B(0, κ) for all κ ∈ M .
Let F κ be the subtree of T 0,κ (X) consisting of those B = B(x, κ + ν) with 0 ≤ ν ≤ µ and 0 / ∈ B. Equivalently, F κ is the finite subtree of T 0,κ (Z n p ) whose leaves are exactly the components G κ of those garlands G satisfying G κ ∩ X = ∅. For G fixed, this non-emptiness does not depend on κ (as long as κ ∈ M ), so for two different κ, κ ′ ∈ M , the map Now the side branch of T Bj (X) at B(0, κ) consists of F κ , with T Gκ (X) attached to the leaf G κ ∈ F κ (for G κ ∩ X = ∅). As T Gκ (X) ∼ = T(Z p ) × T G (κ) with T G of level d, this proves the claim.
6.4. Definable functions on garlands. The main result of this subsection (Proposition 6.13) is that on sufficiently fine one-dimensional garlands, a definable function is given by a branch of a Puiseux series. We start by giving a meaning to a specific branch of the e-th root function. Definition 6.7. Suppose G ⊂ Q p is a garland for 0, λ, µ, ρ, and suppose e ∈ N ≥1 . We say that G is fine enough for e-th roots if µ ≥ 2v(e) + 1 and e | ρ. Suppose that this is the case. Then a uniform choice of e-th roots on G is a choice of e √ x ∈Q p for each x ∈ G such that for any x, . If G is fine enough for e-th roots, then uniform choices of e-th roots on G exist. For any x ∈ G choose any root e √ x. Then for any x ′ ∈ G we have x ′ x ∈ p e·ν · (1 + p 2v(e)+1 Z p ) for some ν ∈ Γ; thus by Lemma 2.2 (1), x ′ x has a root z ∈ p ν · (1 + p v(e)+1 Z p ). Set e √ x ′ := e √ x · z. By "choosing an e-th root on G", we will mean choosing e √ x uniformly as described above. When we ask a garland to be fine enough for e-th roots, we will often implicitly choose such a root.
If G converges to x 0 = 0, by choosing an e-th root on G we mean choosing e √ x − x 0 for x ∈ G in an analogous way. These uniformly chosen roots are Lipschitz continuous in the following sense: Lemma 6.8. Suppose e ∈ N ≥1 and G is a garland converging to 0 which is fine enough for e-th roots.
Note that if x, x ′ lie in the same component of G (and G is fine enough for e-th roots), we may always apply the lemma with We will need the following two results relating garlands and definable sets. Lemma 6.9.
(1) Garlands are definable. (2) If we chose an e-th root on a garland G ⊂ Z p and this root lies in Q p , then x → e √ x is definable.
Note that whether e √ x lies in Q p does not depend on the specific x ∈ G.
(2) We only need to specify in a definable way which of the roots we want to take. If z 0 is the root of one element of G, then the other ones are exactly the ones lying in z 0 · p Γ · B(1, p v(e)+1 ). This is definable by the same argument as for (1). Lemma 6.10. Let X ⊂ Q p be definable and x 0 ∈ Q p . Then there exist λ, µ, ρ such that any corresponding garland converging to x 0 lies either completely inside or completely outside of X.
Proof. It is enough to prove the statement when X is a cell. If x 0 is not equal to the center of the cell, or if the cell has an upper bound β < ∞, then a whole ball B(x 0 , λ) lies either completely inside or completely outside of X. Otherwise choose λ > α (the lower bound) and use that the e-th power residue on sufficiently fine garlands is constant.
The two principal ingredients to our description of definable functions on sufficiently fine garlands are a lemma of Scowcroft and van den Dries which will allow us to replace definable functions by branches of algebraic sets, and the theorem of Puiseux which will allow us to describe such branches in terms of branches of root functions.
Lemma 6.11 (Lemma 1.2 of [2] and comment following its proof). For any definable X ⊂ Q p and any definable function f : X → Q p , the graph of f is a subset of an algebraic curve. Lemma 6.12 (Theorem of Puiseux; see e.g. [8], III.1.6). Let V (Q p ) ⊂ Q 2 p be an algebraic curve. Then there exists λ ∈ Γ, a finite index set N , integers e ν ≥ 1 and coefficients a ν,i ∈Q p for i ∈ Z and ν ∈ N , such that the following holds.
(1) For each ν ∈ N , a ν,i = 0 for i ≪ 0, and the Laurent series Now here is the main result of this subsection.
Proposition 6.13. Let D ⊂ Q p \{0} be definable and let f : D → Q p be a definable function. Then there are e, λ, µ, ρ such that D ∩ B(0, λ) is a union of garlands corresponding to 0, λ, µ, ρ, and such that for each such garland G ⊂ D the following holds. G is fine enough for e-th roots, and f can be written as a convergent Laurent series in e √ x, with coefficients a i ∈Q p : Note that the specific choice of an e-th root on G does not matter; to compensate for a change of root, multiply each a i by an appropriate power of an e-th root of unity.
Proof. Choose λ, µ, ρ large enough such that D∩B(0, λ) is a union of corresponding garlands converging to 0 (use Lemma 6.10). Let V (Q p ) ⊂ Q 2 p be the algebraic curve containing the graph of f according to Lemma 6.11, and apply Lemma 6.12 to V . Enlarge λ such that the conclusion of Lemma 6.12 holds on B(0, λ). Then for any x ∈ D ∩ B(0, λ), there exists a ν ∈ N and an e ν -th root of x such that This statement remains true if we replace all e ν by their least common multiple and renumber the coefficients a ν,i accordingly. Now choose a primitive e-th root of unity ζ, enlarge µ and ρ such that corresponding garlands are fine enough for e-th roots, and choose an e-th root on each of them. Define the set of formal Laurent series x]] ν ∈ N, 0 ≤ j < e , and for G ⊂ D and s ∈ S, set A G,s := {x ∈ G | f (x) = s(x)}. The union of these sets is equal to D ∩ B(0, λ). We claim that after enlarging λ, we may suppose that they are definable and disjoint. For i be the corresponding truncated series, where ι is large enough such that s = s ′ implies s τ = s ′ τ for any s, s ′ ∈ S.
This condition is definable and implies disjointness. So now we have a finite definable partition (A G,s ) of D ∩ B(0, λ). To finish the proof, enlarge λ, µ, ρ again such that any of the finer garlands is completely contained in one of the sets A G,s ; on each of those finer garlands we have We will need an analogue of the previous proposition for definable functions going to Γ ∪ {∞}; we get it as a corollary of the previous proposition, although the heavy machinery of Proposition 6.13 is not really necessary. (It could, for example, also be deduced from Corollary 6.5 of [1] together with Lemma 6.10.) Corollary 6.14. Let D ⊂ Q p be a definable set and α : D → Γ ∪ {∞} a definable function. Then there are λ, µ, ρ such that on each garland G ⊂ D corresponding to 0, λ, µ, ρ, α(x) only depends on v(x), and the function Proof. Write α as v • f for some definable f : D → Q p . Apply Proposition 6.13 to get f (x) = i a i e √ x i , and let ι be minimal such that a ι = 0. If v(x) is sufficiently large, then v(f (x)) = v(a ι e √ x ι ) = v(a ι ) + ι e v(x), so choose λ accordingly.
To conclude this subsection, we prove to two general statements on Puiseux series which we will need later. Lemma 6.15. Suppose that G is a garland for 0, λ, µ, ρ which is fine enough for e-th roots and that the Laurent series ( for all x ∈ G, then there exists a λ ′ ≥ λ such that for all x ∈ Q p for any x, x ′ ∈ G, it suffices to check the claim for one single x ∈ G. Now suppose that ι is minimal such that a ι e √ x ι / ∈ Q p . For y ∈Q p , write dist Qp (y) := sup{v(y − y ′ ) | y ′ ∈ Q p } for the distance of y to Q p . As Q p is closed inQ p in the p-adic topology, we have dist Qp (a ι e √ x ι ) > 0.
some fixed d 0 ∈ Γ not depending on x ∈ G. Thus, for x sufficiently close to zero, (2) Suppose that a ι is the first non-zero coefficient of the series. The condition v(f (x)) ≥ v(x) (applied to sufficiently small x) implies that ι ≥ e, and if ι = e, then v(a ι ) ≥ 0.
Now suppose . This is true for v(x 1 ) ≫ 0, but we need a bound which is independent of i.
Choose any x 0 ∈ G and set λ 0 := v(x 0 ). Let i 0 ∈ Z be such that v(a i0 ) + i0 e λ 0 is minimal (a minimum exits by convergence of f (x 0 )). By supposing v( . Now everything is constant except for the last summand, so for v(x 1 ) sufficiently large, this is non-negative. 6.5. Parametrized subsets of Q p . For (one-dimensional) subsets of Q p , the main conjecture is not difficult to prove: Lemma 6.16. If X is a definable subset of Q p , then T(X) is of level 1.
Proof. By Lemma 6.10, trees on sufficiently fine garlands close to any given point are isomorphic either to κ → ∅ or to κ → T(Z p ), so in any case they are of the form κ → T(Z p ) × T (κ) where T is of level 0. Thus Lemma 6.6 yields that the total tree T(X) is of level 1.
To prove the conjecture for definable subsets of Q 2 p , we will need a parametrized version of this: if we have definable sets X κ ⊂ Q p parametrized by κ ∈ Γ in a suitable "uniform" way, then we should get a parametrized level 1 tree. To state this, we need a notion of "sufficient uniform maps" from Γ to Q p . Definition 6.17. Let δ ∈ Γ >0 , M ⊂ Γ ≥0 and c κ ∈ Q p for κ ∈ M . We say that κ → c κ is δ-uniform, if κ → v(c κ ) is linear and if there exists an a ∈ Z × p such that c κ ≈ δ p v(cκ) a for all κ ∈ M . Now here is a uniform version of Lemma 6.16. Proposition 6.18. Suppose that for each κ in a subset M ⊂ Γ ≥0 we are given a definable set X κ ⊂ Q p , and that these sets are uniform in κ in the following sense. Each X κ is the union of finitely many disjoint cells C κ,i , i ∈ I of the form We require that all exponents are equal and that none of the index set I, the exponent e, the residues r i and conditions ⊳ i , ⊳ ⊳ i depend on κ. Moreover set δ := δ(e) as in Lemma 6.3. We require that for each i, j ∈ I, the functions κ → α κ,i and κ → β κ,i are linear, and the functions κ → c κ,i and κ → c κ,i − c κ,j are δ-uniform.
Under these conditions on X κ , the tree M → {Trees}, κ → T(X κ ) is piecewise a parametrized level 1 tree.
Note that the requirement that the exponents of all cells are equal is not a real restriction: anyway cell decompositions can be refined such that all exponents become equal.
Before we start with the proof, let us state a variant as a corollary. Proof of the corollary. Define ψ κ (x) := p −σκ (x−b k ). Then T Bκ (X κ ) ∼ = T(ψ κ (X κ )), so it suffices to verify uniformity of the sets ψ κ (X κ ). Uniformity of the cell bounds and δ-uniformity of differences of centers carries over (by linearity of κ → σ κ ), and δ-uniformity of κ → c κ,i − b κ yields δ-uniformity of κ → ψ κ (c κ,i ). The exponent e and the conditions ⊳ i , ⊳ ⊳ i do not change, so it remains to consider the residues r i . They are replaced by p −σκ r i , which does depend on κ. However, as we only want to prove piecewise uniformity of the resulting trees, we may partition M according to σ κ modulo e; on these parts, the e-th power residue of p −σκ r i is constant, so we may replace p −σκ r i by one fixed value.
Proof of Proposition 6.18. We may suppose that M is infinite; otherwise the statement follows from Lemma 6.16. We will prove the statement inductively, starting from the leaves. We will cut the tree horizontally into slices. There will be some thin ones where "the things happen" and some thick and simple parts in between where the skeleton of the tree will only consist of long bones. Let us make this precise.
By "the involved linear functions" we mean the set of maps from M to Γ ∪ {∞} For two linear functions ℓ 1 , ℓ 2 : M → Γ ∪ {∞}, we write (If ℓ 1 and ℓ 2 both are constant ∞, we set ℓ 1 ≪ ℓ 2 .) By treating finitely many elements of M separately using Lemma 6.16, we may suppose that if ℓ 1 and ℓ 2 both are either involved or constant 0, then In particular, ≤ defines a total order on the involved functions and the zero function, and whether a cell center c κ,i lies in Z p is independent of κ.
By partitioning M into finitely many definable sets and treating each one separately, we may suppose that moreover for any i ∈ I, whether or not C κ,i ∩ Z p is empty is independent of κ. By removing cells not intersecting Z p , we may suppose C κ,i ∩ Z p = ∅ for any i ∈ I and any κ ∈ M .
Our induction will run over the number of involved functions ℓ satisfying ℓ ≫ 0. Thus by induction hypothesis, we can apply Corollary 6.19 to (X κ ) κ and a family of balls B κ = B(b κ , σ κ ), provided there is at least one involved function ℓ ≫ 0 such that ℓ − (κ → σ κ ) ≫ 0.
We will now first treat the special case where every lower bound α κ,i satisfies either α κ,i ≤ 0 or α κ,i ≫ 0, and every other involved function ℓ satisfies ℓ ≫ 0. This corresponds to the thick but simple slices in our tree. Afterwards we will reduce the general case to the first one; this reduction corresponds to the thin but complicated slices.
The tree T Sκ (X κ ) does not change if we replace all centers of cells c κ,i by 0: if ℓ 0 = ∞, there is nothing to do; otherwise this follows from Lemma 6.3 (1), using that for So for x ∈ S κ \ {0}, we get that x ∈ X κ if and only if there is an i ∈ I with α κ,i ≤ 0 such that x ri is an e-th power. Thus for λ < ℓ 0 (κ), the side branch of T(X κ ) at B(0, λ) only depends on λ modulo e and not on κ at all. Moreover, each side branch consists of a finite tree with copies of T(Z p ) attached to its leaves; hence κ → T Sκ (X κ ) is indeed of level 1.
The thin and complicated slices: (Reduction of the general case to the case where all involved ℓ satisfy ℓ ≫ 0, except for lower bounds α κ,i which may also be α κ,i ≤ 0.) Let us first have a look at cells whose centers c κ,i lie outside of Z p . If v(c κ,i ) < −δ and C κ,i ∩ Z p = ∅, then Lemma 6.3 yields Z p ⊂ C κ,i , so this case is trivial. If −δ ≤ v(c κ,i ) < 0, then v(c κ,i ) does not depend on κ by (14), and δ-uniformity of c κ,i yields c κ,i ≈ δ a ′ for some a ′ ∈ Q p not depending on κ. Thus for any two different κ, for all κ and all x ∈ Z p . This yields bijections for all κ, κ ′ ∈ M , which will be useful later. Now let λ be the maximum value of all constant involved functions. We will cut out holes of radius λ + δ around the centers of some of the cells, apply the thick and simple case to get the trees in these holes, compute the tree outside of the holes and then put everything together. Define B κ,i := B(c κ,i , λ + δ) for i ∈ I. We do not want to cut out all B κ,i , but only those in which X κ is complicated: define J ⊂ I in such a way that j ∈ J implies c κ,j ∈ Z p and C κ,j ∩ B κ,j = ∅. Moreover, if there are several i for which the balls B κ,i are equal, then put only one representative into J.
Let us first analyse the relative position of a cell C κ,i and a hole B κ,j (i ∈ I, j ∈ J). We claim that either c κ,i ∈ B κ,j or C κ,i ∩B κ,j = ∅, and that this does not depend on κ. Indeed, if v(c κ,i − c κ,j ) ≫ 0, then by (14) we have v(c κ,i − c κ,j ) ≥ λ+ 2δ for all κ ∈ M , so c κ,i ∈ B κ,j . If on the other hand v(c κ,i −c κ,j ) ≫ 0, then v(c κ,i −c κ,j ) ≤ λ for all κ ∈ M , and Lemma 6.3 (1) implies that B κ,j lies either completely inside or completely outside of C κ,i . As B κ,j ∩ C κ,j = ∅, the disjointness of C κ,i and C κ,j implies C κ,i ∩ B κ,j = ∅. Now fix j ∈ J. Computing the tree κ → T Bκ,j (X κ ) in the hole B κ,j can be done using the corollary version of the thick-and-simple case, after removing all cells not intersecting B κ,j . Indeed, the required uniformity in κ is clear, and the condition ℓ ≫ λ + δ for involved ℓ (or α κ,i ≤ λ + δ for lower bounds) follows from the fact that C κ,i ∩ B κ,j = ∅ implies v(c κ,i − c κ,j ) ≫ 0 and β κ,i ≫ 0.
By Lemma 4.6 we are left to compute the tree on the cheese S κ := Z p \ j∈J B κ,j . We will first check that for each κ separately, the tree T Sκ (X κ ) is of level 1 (with the nodes B κ,j being joints), and then we will find isomorphisms T Sκ (X κ ) ∼ = T Sκ (X κ ′ ) respecting the holes. This implies that κ → T Sκ (X κ ) is parametrized of level 1.
To prove that T Sκ (X κ ) is of level 1, it is enough to show that any ball B ⊂ S κ of radius λ + 2δ lies either completely inside or completely outside of X κ . So suppose x ∈ X κ ∩ S κ . Then x ∈ C κ,i for some i ∈ I, and our choice of holes ensures that v(x − c κ,i ) < λ + δ. Lemma 6.3 (1) implies that C κ,i (and therefore X κ ) contains B(x, λ + 2δ).
To get the isomorphisms T Sκ (X κ ) → T S κ ′ (X κ ′ ) we first replace (for each κ) X κ by a set Y κ which has the same tree on S κ , but which is simpler inside the holes. We ensure that T(Y κ ) contains the nodes B κ,j , j ∈ J, so that T Sκ (Y κ ) ⊂ T(Y κ ). Then we will use Lemma 3.1 to construct an isomorphism T(Y κ ) → T(Y κ ′ ) sending B κ,j to B κ ′ ,j ; this yields the desired isomorphism T Sκ ( , and the element c κ,j ensures that B κ,j is a node of T(Y κ ). It remains to define the bijective isometry φ : Y κ → Y κ ′ needed in Lemma 3.1. To this end, let us first adapt our cell decomposition to the sets Y κ : define Thus X κ ∩ S κ = Z p ∩ i∈I D κ,i . Our choice of J ensures that D κ,i = C κ,i \ B κ,i if c κ,i ∈ Z p and D κ,i = C κ,i otherwise, so D κ,i is a cell again, and moreover Next, we claim that the map x → x−c κ,i +c κ ′ ,i induces a bijection from D κ,i ∩Z p to D κ ′ ,i ∩ Z p . If c κ,i / ∈ Z p , then this has already been verified in (15). Otherwise, it follows from the fact that the bounds of D κ,i are either independent of κ or less than 0. Using this, we define the bijection φ : We may suppose i = j; otherwise, this is trivial. Now recall that c κ,i − c κ,j is δ-uniform in κ and that v(c κ,i − c κ,j ) is involved. Suppose first that v(c κ,i − c κ,j ) is constant. Then we get c κ,i − c κ,j ≈ δ c κ ′ ,i − c κ ′ ,j , so the right hand side of (16) is at least v(c κ,i − c κ,j ) + δ. If x 1 = c κ,i and x 2 = c κ,j , then this implies (16) trivially. If x 1 ∈ D κ,i and x 2 = c κ,j , then apply Lemma 6.3 (1). If x 1 ∈ D κ,i and x 2 ∈ D κ,j , then apply Lemma 6.3 (2).
If v(c κ,i − c κ,j ) is not constant, then by (14) both c κ,i − c κ,j and c κ ′ ,i − c κ ′ ,j have valuation at least λ + 2δ, so we have to check v(x 1 − x 2 ) < λ + 2δ. If x 1 = c κ,i , then this follows from x 2 / ∈ B κ,i . If x 1 ∈ D κ,i , then x 1 / ∈ B κ,i , i.e. v(x 1 − c κ,i ) < λ + δ, and the claim follows from Lemma 6.3 (1). 6.6. Proof for definable subsets of Q 2 p . We are now ready to prove that if X is a definable subset of Q 2 p , then the tree of X is of level 2. To finish the proof of Theorem 1.5 we moreover need that if dim X ≤ 1, then the tree is of level dim X; this is included in Theorem 1.6, which we will prove in the next subsection.
Proof for two-dimensional subsets of Q 2 p . Suppose that X ⊂ Q 2 p is definable. Our goal is to prove that T(X) is a tree of level 2. We use Lemma 6.6, i.e. it is enough to show that for any (x 0 , y 0 ) ∈ Z 2 p and for sufficiently large λ, µ, ρ, the trees on the corresponding garlands are piecewise of level 1. We suppose without loss (x 0 , y 0 ) = (0, 0).
For the remainder of the proof fix a garland G for (0, 0), λ, µ, ρ. At several places, we will suppose λ, µ, ρ to be sufficiently large; of course the meaning of "sufficient" must not depend on G (as augmenting µ and ρ augments the number of garlands). Indeed, λ, µ, ρ will only depend on two cell decompositions of X: a normal one and one with coordinates exchanged.
For κ ∈ M := M (G), let G κ be the corresponding component of G. Recall that We may suppose v(x G ) = 0; otherwise, exchange coordinates.
Denote by H the projection of G onto the first coordinate and by H κ = B(p κ x G , κ+ µ) the projections of the components G κ . As v(x G ) = 0, H is a garland with components H κ . Denote by B κ = B(p κ y G , κ + µ) the projection of G κ onto the second coordinate. For x ∈ H, let X x := {y ∈ Q p | (x, y) ∈ X} be the fiber of X at x.
Our goal is to compute T G (X). We will verify that Corollary 3.3 can be applied to each set G κ ∩X, yielding that T Gκ (X) is isomorphic to T(Z p )×T Bκ (X xκ ), where x κ := p κ x G ∈ H κ . We will moreover verify that Corollary 6.19 can be applied to the sets X xκ and the balls B κ (where κ runs through M ). This implies that the map κ → T Bκ (X xκ ) is piecewise a level 1 tree. Thus T G (X) satisfies the prerequisites of Lemma 6.6, and we are done.
Before we attack the prerequisites of the two corollaries, let us have a closer look at the set X and fix some notation. Choose a cell decomposition such that X is the union of cells. We may suppose that the exponents of all cells are equal to one single e 0 ∈ N. Fix once and for all δ := δ(e 0 ) as in Lemma 6.3. By Lemma 6.10, we may suppose that H is contained in one single base cell D 0 ⊂ Q p .
In the remainder of the proof, C will be a cell contained in X and having base D 0 ; we will denote its bounds and center by α, β and c, respectively, and its fiber at x ∈ H by C x . For any x ∈ H, these fibers C x form a cell decomposition of X x . Occasionally we will need a second cell C ′ (also contained in X and having base D 0 ), with bounds, center and fiber α ′ , β ′ , c ′ and C ′ x . We use Proposition 6.13 and Corollary 6.14 to control α, β and c: for λ, µ, ρ sufficiently large, the bounds α(x) and β(x) only depend on κ = v(x), and this dependence is linear. Moreover, we can choose an e-th root on H and write the center as a convergent series where c i = 0 for i ≪ 0, and where c i may lie inQ p , but c i e √ x i ∈ Q p for any x ∈ H and any i ∈ Z by Lemma 6.15 (1). We may suppose that e does not depend on the cell C; otherwise, take the least common multiple of all e. For the remainder of the proof, we keep an e-th root on H fixed. Let ι be minimal such that c ι = 0 in the above series. By further enlarging λ, we may suppose c(x) ≈ δ c ι e √ x ι for all x ∈ H. The same argument also applies to f (x) := c(x) − c ′ (x) and to f (x) := c(x) − yG xG x: we may assume that for each of the (finitely many) functions f mentioned here, there exist a ∈Q p and ι ∈ Z such that f (x) ≈ δ a e √ x ι ∈ Q p for all x ∈ H.
We now verify the prerequisites of Corollary 6.19, i.e. we have to verify that the cell decomposition C xκ of X xκ satisfies the uniformness properties in κ. It is clear that only the bounds and the centers depend on κ, and we already ensured that the bounds are linear in κ. It remains to verify that the functions κ → c(x κ ) − c ′ (x κ ) and κ → c(x κ ) − p κ y G are δ-uniform.
Choose a ∈Q p and ι ∈ Z such that c(x κ ) − c ′ (x κ ) ≈ δ a e √ x κ ι = a e √ p κ x G ι and fix any κ 0 ∈ M . Then we can write any κ ∈ M as κ = κ 0 + eν for some ν ∈ Γ. By uniformity of the choice of roots on H, we have a e √ p κ x G ι = p ιν a e √ p κ0 x G ι . As only ν depends on κ, this yields δ-uniformity of c(x κ ) − c ′ (x κ ). The same argument applies to c( The last remaining task is the verification of the prerequisites of Corollary 3.3. Fix κ ∈ M and suppose we are given x 1 , x 2 ∈ H κ . We have to find a bijective isometry φ : . We will define φ on each cell C x1 separately. However, first we have to get rid of some cells: we claim that we can suppose for all x ∈ H. As c(x) ≈ δ a e √ x ι for some a ∈ Q p , ι ∈ Z, we may enlarge λ such that (17) either holds for all x ∈ H or for no x ∈ H. Suppose that it does not hold. We prove that then C ∩ G κ is either empty or equal to G κ (i.e. either we may ignore C or T Gκ (X) is trivial). We have to check that for (x 1 , y 1 ), (x 2 , y 2 ) ∈ G κ , y 1 ∈ C x1 if and only if y 2 ∈ C x2 . The cell C x2 is just a shift of C x1 (the bounds α and β only depend on κ), so in view of Lemma 6.3 (1) it is enough to verify y 1 − c(x 1 ) ≈ δ y 2 − c(x 2 ).
suppose H ⊂ D 0 , so all relevant cells have the same final base D 0 , and moreover dim D 0 = 1. As C is 1-dimensional, it is the graph of a definable function c : D 0 → Q n−1 p . In this proof, by the "center" of C we shall mean this function c. By Proposition 6.13, we may enlarge λ, µ, ρ, choose an e-th root on H and then write the center as As Let c ′ be the center of a second cell C ′ . By Corollary 6.14 we may suppose that v(c(x) − c ′ (x)) only depends on κ = v(x) and is linear in κ. Let us call the induced functions v(x) → v(c(x) − c ′ (x)) the "involved functions".
To show that M → {Trees}, κ → T Bκ (X xκ ) is piecewise of level 0, we partition M into definable pieces M ′ in such a way that for any two involved functions ℓ 1 , ℓ 2 , the truth values of ℓ 1 ℓ 2 are constant on each piece M ′ . The tree T Bκ (X xκ ) has one infinite path for each center c(x κ ), and the depths of the bifurcations are given by v(c(x G ) − c ′ (x G )). The partition of M ensures that the overall structure of T Bκ (X xκ ) is constant on each piece M ′ , and linearity of the involved functions yields linearity of the lengths of the bones on each piece.
It remains to verify the prerequisites of Corollary 3.3. For κ ∈ M and x 1 , x 2 ∈ H κ , we use the bijection φ : X x1 ∩ B κ → X x2 ∩ B κ sending c(x 1 ) to c(x 2 ). This is an isometry as x → v(c(x) − c ′ (x)) is constant on H κ . To get v(c(x 2 ) − c(x 1 )) ≥ v(x 2 − x 1 ) we apply Lemma 6.15 (2) to each coordinate of c; the prerequisite v(c(x)) ≥ v(x) follows from c(x) ∈ B κ . 7. Possible generalizations 7.1. Skeletal cell decompositions of trees. The main conjecture can be generalized to a kind of cell decomposition of trees in the following sense. Consider T(Z n p ) as an imaginary sort of our language: T(Z n p ) = (Z n p × Γ) (x, λ) Then for any definable set X ⊂ Z n p , T(X) is a definable subset of T(Z n p ). Suppose we have an isomorphism between T(X) and a tree constructed out of a level d tree datum; I will call this an iterated skeleton for T(X). Now let us add more branches to this iterated skeleton in such a way that afterwards each node has exactly p n children: enlarge the finite trees F at the beginning of side branches, and add side branches to the iterated side trees which before were of level 0. The result is an iterated skeleton of level n for T(Z n p ) which is, in a certain sense, compatible to T(X). It seems plausible that such a compatible iterated skeleton of T(Z n p ) should exist for arbitrary definable sets Y ⊂ T(Z n p ). Let me make this more precise. Let D be a tree datum and let T be the tree constructed out of D. Suppose that F is the finite tree appearing in a side branch datum of D-either for side branches of T itself, or for side branches of an (iterated) side tree. Suppose moreover that w is a node of F . Then we define the set C F ,w ⊂ T of "nodes coming from w". We would like to say that every node of T lies in exactly one set C F ,w ; to achieve this, we slightly modify some definitions.
The only nodes of T which are not part of any set C F ,w are the ones on side trees of level 0. (Nodes on skeletons of trees of higher level are roots of side branches.) Thus we define a side branch of level −1 to be a finite tree F consisting only of a root, and we let a tree of level 0 be one with side branches of level −1 (as in Subsection 5.1). Now some nodes of T appear in two sets C F ,w : if w is a leaf of F and F belongs to a side branch of level ≥ 0, then the corresponding nodes of T also appear as root of the first side branch of the side tree attached to w; thus we forbid to take for w a leaf of F unless F is a side branch of level −1.
In this way, an iterated skeleton of a tree T yields a partition of its nodes; let us call such a partition a skeletal cell decomposition of T , and let us call the sets C F ,w skeletal cells. Now we can formulate a cell decomposition version of Conjecture 1.1: Then there exists a skeletal cell decomposition of T(Z n p ) such that Y is a union of skeletal cells. This conjecture does not yet imply Conjecture 1.1; one would like to have a notion of dimension for definable subsets of T(Z n p ) and then improve the statement to something like "Y is a union of skeletal cells of level at most dim Y ".
In the introduction, we mentioned a variantT(V ) of the tree of a variety V , where the set of nodes at depth λ consists of the whole set V (Z/p λ Z). These trees are definable, so they also fall in the scope of this version of the conjecture. Note that as for Conjecture 1.1, this directly implies rationality of the associated Poincaré series: the proof that trees of level d have rational Poincaré series directly generalizes to unions of skeletal cells, if one defines the Poincaré series of a subset Y ⊂ T(Z n p ) by #{v ∈ Y | depth T(Z n p ) (v) = λ} · Z λ .

7.2.
Trees over other Henselian fields. If K is any Henselian field, then one can define the tree of a definable subset of K n in an analogue way as over Q p (though one needs a generalized notion of tree if the valuation group is not discrete). One cannot expect to get a nice statement on such trees if the model theory of K is not understood, but there are several cases in which it is understood and where a variant of the main conjecture would be interesting: algebraically closed valued fields and Henselian fields of characteristic (0, 0). Moreover, if the model theory is not understood, one may still hope for a conjecture concerning trees of varieties. The reason I think algebraically closed fields are interesting is that there, trees should be simpler, and one might hope to first prove a version of the conjecture in this case, before going back to non-algebraically closed fields. Indeed, over Q p , we had different side branches depending on the depth modulo some ρ. The reason for this was that not all roots exist, so this phenomenon should disappear over algebraically closed fields.
Concerning Henselian fields K of characteristic (0, 0), a good version of the conjecture there should imply a uniform version of the conjecture over Q p for almost all p, which in turn should imply rationality of the Poincaré series "uniformly in p", probably in the same sense as it has been proven in [9]. Let me make this precise, describing the hopes I have in this case.
Over Q p , our trees were purely combinatorial; if the residue field is not finite, then most nodes will just have infinitely many children, so there is not much combinatorial information left. Thus it will be necessary to add some additional structure to the trees; probably the set of children of a node (or the appropriate equivalent if the value group is not discrete) should be a definable set over the residue field. A tree datum D in this setting should contain formulas χ(y) in the ring language, which describe the sets of children of some nodes; for any valued field K, one then gets an actual tree T D,K by interpreting the formulas χ(y) in the residue field of K.
Now suppose that for any Henselian field K of characteristic (0, 0) and any formula φ(x) (with x in the valued field sort), we do not only have a tree datum D describing T(φ(K)), but moreover we can say this in a first order way: there is a sentence ψ which holds in K and such that for any other valued field K ′ , K ′ |= ψ implies that D describes T(φ(K ′ )). Then for any given formula φ(x), by compactness there is a finite set D of tree data such that for any K Henselian of characteristic (0, 0), there is a D ∈ D describing T(φ(K)). If we restrict ourselves to fields with value group (elementarily equivalent to) Z, then by Ax-Kochen-Eršov D will only depend on the residue field. Thus we may unify all D ∈ D to one single tree datum D 0 which is valid for all K by incorporating the choice of D into the formula describing the children of the root. By applying this to ultraproducts of the fields Q p , we get that D 0 also describes T(φ(Q p )) for almost all p.