Finite subtrees of the Berkovich line

Let \(K\) be a field and \(v_K\) a discrete valuation on \(K\). Let \(X=\mathbb{P^1_K}\) be the projective line over \(K\). Let \(X^{an}\) denote the \((K,v_K)\)-analytic space associated to \(X\). We call \(X^{an}\) the Berkovich line over \(K\).

Let \(\xi^g\) be the Gauss point on \(X^{an}\), corresponding to the Gauss valuation on the function field of \(X\) with respect to the canonical parameter \(x\). Then \(X^{an}\) has a natural partial ordering for which \(\xi^g\) is the smallest element. With respect to this partial ordering, any two elements have a unique infimum.

A Berkovich tree is a finite (nonempty) subset \(T\) with the property that for any two elements in \(T\) the infimum is also contained in \(T\). In particular, a \(T\) has a least element, called the root of the tree.

Given any finite subset \(S\) of \(X^{an}\), there is now a unique minimal subtree \(T\) contaning \(S\). We call \(T\) the tree spanned by \(S\).

This module realizes finite subtrees of \(X^{an}\) as combinatorial objects, more precisely as finite rooted combinatorial trees. So a tree consists of a root, and a list of children. If the tree is a subtree of another tree, then there is a link to its parent.

AUTHORS:

  • Stefan Wewers (2017-02-13): initial version

EXAMPLES:

<Lots and lots of examples>
class mclf.berkovich.berkovich_trees.BerkovichTree(X, root=None, children=None, parent=None)

Bases: SageObject

Create a new Berkovich tree \(T\).

INPUT:

  • X – a Berkovich line
  • root – a point of X (default: None)
  • children – a list of Berkovich trees on X (default = None)
  • parent – a Berkovich tree or None (default: None)

OUTPUT:

A Berkovich tree \(T\) on \(X\) with root root, children children and parent parent. \(T\) may be empty (no root and no children), but if there are children then there must be root.

EXAMPLES:

sage: from mclf import *
sage: v_2 = QQ.valuation(2)
sage: F.<x> = FunctionField(QQ)
sage: X = BerkovichLine(F, v_2)
sage: T = BerkovichTree(X); T
Berkovich tree with 0 vertices
sage: xi = X.gauss_point()
sage: T.find_point(xi)
adapt_to_function(f)

Add all zeroes and poles of \(f\) as leaves of the tree.

INPUT:

  • f – a rational function on \(X\)

OUTPUT:

the new tree obtained by adding all zeroes and poles of \(f\) as vertices to the old tree.

add_point(xi)

Return the tree spanned by self and the point xi.

INPUT:

  • xi – A point of type I or II on X

OUTPUT: \(T_1\), \(T_2\), where

  • \(T_1\) is the tree obtained from \(T_0\) as a vertex.
  • \(T_2\) is the subtree of \(T_1\) with root \(\xi\)

If \(T_0\) has a parent, then the root of \(T_0\) must be less than \(\xi\). Therefore, the parent of \(T_1\) will be the original parent of \(T_0\).

Note that this command may change the tree \(T_0\)! For instance, \(\xi\) may become the root of \(T_1\) and then \(T_0\) has \(T_1\) as new parent.

adjacent_vertices(xi0)

List all vertices of the tree adjacent to a given vertex.

berkovich_line()

Return the Berkovich line underlying this tree.

children()

Return the list of all children.

This is a deep copy of the internal list of children! Therefore, it cannot be used to change the tree.

copy()

Return a copy of self.

direction_from_parent()

Return the direction from the parent.

OUTPUT: the type V point \(\eta\) representing the direction from the root of the parent of self to the root of self.

If self has no parent, an error is raised.

direction_to_parent()

Return the direction to the parent.

OUTPUT: the type V point \(\eta\) representing the direction from the root of self to the root of its parent.

If self has no parent, an error is raised.

The direction is not well defined if the root of self is a point of type I. Therefore, an error is raised in this case.

find_point(xi)

Find subtree with root xi.

INPUT:

  • xi – a point on the Berkovich line underlying self

OUTPUT:

The subtree \(T\) of self with root xi, or None if xi is not a vertex of self.

EXAMPLES:

sage: from mclf import *
sage: v_2 = QQ.valuation(2)
sage: F.<x> = FunctionField(QQ)
sage: X = BerkovichLine(F, v_2)
sage: T = BerkovichTree(X); T
Berkovich tree with 0 vertices

Searching in the empty tree does not give an error anymore.:

sage: xi = X.gauss_point()
sage: T.find_point(xi)

sage: T.add_point(xi)
(Berkovich tree with 1 vertices, Berkovich tree with 1 vertices)
sage: T.find_point(xi)
Berkovich tree with 1 vertices
graph()

Return a graphical representation of self.

OUTPUT:

G, vert_dict,

where G is a graph object and vert_dict is a dictionary associating to a vertex of G the corresponding vertex of self.

has_parent()

Return True if self has a parent.

is_leaf()

Return True if self is a leaf.

leaves(subtrees=False)

Return the list of all leaves.

If subtrees is True, then we return the list of subtrees corresponding to the leaves.

make_child(new_child, check=True)

Make new_child a child of self.

INPUT:

  • new_child – a Berkovich tree
  • check – a boolean (default False)

We make the tree new_child a child of self. For this to make sense, two conditions have to be satisfied:

  • the root of new_child has to be strictly greater than the root of self
  • the root of new_child has to be incomparable to the roots of the already existing children of self

These conditions are checked only if check ist True.

Note:

This changes both trees self and new_child.

make_parent(parent)

add parent as parent of self.

parent()

Return the parent of self.

paths()

Return the list of all directed paths of the tree.

OUTPUT:

the list of all directed paths of the tree, as a list of pairs \((\xi_1,\xi_2)\), where \(\xi_2\) is a child of \(\xi_1\).

permanent_completion()

Return the permanent completion of self.

OUTPUT:

A Berkovich tree \(T_1\) which is the permanent completion of self.

A Berkovich tree tree \(T\) on a Berkovich line \(X\) over \((K,v_K)\) is called permanently complete if for all finite extensions \((L,v_L)\) of \((K,v_K)\), the inverse image of the set of vertices of \(T\) in \(X_L\) is again the set of vertices of a Berkovich tree. It is easy to see that for any Berkovich tree \(T\) there exists a minimal refinement \(T_1\) which is permanently complete. It is called the permanent completion of \(T\).

ALGORITHM:

Let \(\xi_0\) be the root and \(\xi_1,\ldots,\xi_n\) the leaves of \(T\). To compute \(T_1\) we consider, for \(i=1,\ldots,n\), the path \(\gamma = [\xi_0,\xi_n]\) and the function on \(\gamma\) which maps a point \(\xi\) to the number of geometric components of the discoid \(D_\xi\). We add the jumps of this function to \(T\). Having done this for all \(i\) we obtain the permant completion \(T_1\) of \(T\).

EXAMPLES:

sage: from mclf import *
sage: FX.<x> = FunctionField(QQ)
sage: v_2 = QQ.valuation(2)
sage: X = BerkovichLine(FX, v_2)
sage: xi0 = X.point_from_discoid(x^4+2, 5)
sage: T = BerkovichTree(X, xi0)
sage: T.permanent_completion()
Berkovich tree with 3 vertices
position(xi)

Find the position of xi in the tree T=self.

INPUT:

  • xi – a point on the Berkovich line underlying T

OUTPUT:

xi1, T1, T2, is_vertex,

where

  • xi1 is the image of xi under the retraction map onto the total space of T
  • T1 is the smallest subtree of T whose total space contains xi1
  • T2 is the child of T1 such that xi1 lies on the edge connecting T1 and T2 (or is equal to T1 if xi1 is the root of T1)
  • is_vertex is True if xi1 is a vertex of T (which is then the root of T1) or False otherwise
print_tree(depth=0)

Print the vertices of the tree, with identation corresponding to depth.

It would be nicer to plot the graph and then list the points corresponding to the vertices.

remove_child(child)

Remove child from list of children of self.

INPUT:

  • child – a Berkovich tree

We remove child from the list of children of self. If child is not in this list, an error is raised.

Note:

This function changes both self and child.

remove_point(xi, test_inequality=True)

Remove a point from the tree, if possible.

INPUT:

  • xi – a point of type I or II on the Berkovich line
  • test_inequality -- a boolean (default: ``True)

OUTPUT:

the tree obtained from self by removing, if possible, the vertex with root \(\xi\).

Removing the vertex with root \(\xi\) is possible if a vertex with root \(\xi\) exists, and if it has at most one child. Otherwise, nothing is changed.

Note that the vertex to be removed may be the root of this tree. If this is the case and there is no child, then an empty tree is return and the tree is remove as a child from its parent.

If test_inequality is False then it is assumed that \(\xi\) is greater or equal to the root of self. This saves us a test for inequality.

EXAMPLES:

sage: from mclf import *
sage: v_2 = QQ.valuation(2)
sage: F.<x> = FunctionField(QQ)
sage: X = BerkovichLine(F, v_2)
sage: T = BerkovichTree(X)
sage: T, _ = T.add_point(X.gauss_point())
sage: T = T.remove_point(X.gauss_point()); T
Berkovich tree with 0 vertices
sage: xi_list = [xi for xi, m in X.divisor(x*(x^2+2))]
sage: for xi in xi_list: T, _ = T.add_point(xi)
sage: T
Berkovich tree with 5 vertices
sage: T.remove_point(xi_list[0])
Berkovich tree with 4 vertices
root()

Return the root of the tree.

subtrees()

Return the list of all subtrees.

vertices()

Return the list of all vertices.

mclf.berkovich.berkovich_trees.component_jumps(xi0, xi1)

Helper function for permanent_completion.

mclf.berkovich.berkovich_trees.create_graph_recursive(T, G, vertex_dict, root_index)

Create recursively a graph from a Berkovich tree.

mclf.berkovich.berkovich_trees.replace_subtree(T1, T2)

Replace a subtree of a Berkovich tree by another tree.

INPUT:

  • T1, T2 - Berkovich trees with the same root

It is assumed that \(T_1\) has a parent, so it is a proper subtree of an affinoid tree \(T_0\). We replace the subtree \(T_1\) with \(T_2\).

NOTE:

This changes the tree `T_0`; therefore this function must be
used carefully.