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 lineroot
– a point ofX
(default: None)children
– a list of Berkovich trees onX
(default = None)parent
– a Berkovich tree or None (default: None)
OUTPUT:
A Berkovich tree \(T\) on \(X\) with root
root
, childrenchildren
and parentparent
. \(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 ofself
.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 underlyingself
OUTPUT:
The subtree \(T\) of
self
with rootxi
, orNone
ifxi
is not a vertex ofself
.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
isTrue
, 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 treecheck
– a boolean (defaultFalse
)
We make the tree
new_child
a child ofself
. For this to make sense, two conditions have to be satisfied:- the root of
new_child
has to be strictly greater than the root ofself
- the root of
new_child
has to be incomparable to the roots of the already existing children ofself
These conditions are checked only if
check
istTrue
.Note:
This changes both trees
self
andnew_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 ofself
. Ifchild
is not in this list, an error is raised.Note:
This function changes both
self
andchild
.
-
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 linetest_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
isFalse
then it is assumed that \(\xi\) is greater or equal to the root ofself
. 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.