In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to. Sometimes the associated metric is also called a non-Archimedean metric or super-metric. Although some of the theorems for ultrametric spaces may seem strange at a first glance, they appear naturally in many applications.
In the case when is a group and is generated by a length function , the last property can be made stronger using the Krull sharpening to: We want to prove that if, then the equality occurs if. Without loss of generality, let us assume that. This implies that. But we can also compute. Now, the value of cannot be, for if that is the case, we have contrary to the initial assumption. Thus,, and. Using the initial inequality, we have and therefore.
Properties
From the above definition, one can conclude several typical properties of ultrametrics. For example, for all, at least one of the three equalities or or holds. That is, every triple of points in the space forms an isosceles triangle, so the whole space is an isosceles set. Defining the ball of radius centred at as, we have the following properties:
Every point inside a ball is its center, i.e. if then.
Intersecting balls are contained in each other, i.e. if is non-empty then either or.
The set of all open balls with radius and center in a closed ball of radius forms a partition of the latter, and the mutual distance of two distinct open balls is equal to.
Proving these statements is an instructive exercise. All directly derive from the ultrametric triangle inequality. Note that, by the second statement, a ball may have several center points that have non-zero distance. The intuition behind such seemingly strange effects is that, due to the strong triangle inequality, distances in ultrametrics do not add up.
The p-adic numbers form a complete ultrametric space.
Consider the set of words of arbitrary length, Σ*, over some alphabet Σ. Define the distance between two different words to be 2−n, where n is the first place at which the words differ. The resulting metric is an ultrametric.
The set of words with glued ends of the lengthn over some alphabet Σ is an ultrametric space with respect to the p-close distance. Two words x and y are p-close if any substring of p consecutive letters appears the same number of times both in x and y.
If r = is a sequence of real numbers decreasing to zero, then |x|r := lim supn→∞ |xn|rn induces an ultrametric on the space of all complex sequences for which it is finite.
If G is an edge-weighted undirected graph, all edge weights are positive, and d is the weight of the minimax path between u and v, then the vertices of the graph, with distance measured by d, form an ultrametric space, and all finite ultrametric spaces may be represented in this way.
Applications
A contraction mapping may then be thought of as a way of approximating the final result of a computation. Similar ideas can be found in domain theory. p-adic analysis makes heavy use of the ultrametric nature of the p-adic metric.
In taxonomy and phylogenetic tree construction, ultrametric distances are also utilized by the UPGMA and WPGMA methods. These algorithms require a constant-rate assumption and produce trees in which the distances from the root to every branch tip are equal. When DNA, RNA and protein data are analyzed, the ultrametricity assumption is called the molecular clock.
Models of intermittency in three dimensionalturbulence of fluids make use of so-called cascades, and in discrete models of dyadic cascades, which have an ultrametric structure.
In geography and landscape ecology, ultrametric distances have been applied to measure landscape complexity and to assess the extent to which one landscape function is more important than another.
