Ultrametrics

An ultrametric is a metric d defined on a set X that satisfies the ultrametric inequality: for all x, y, z in X, d(x, z) ≤ max{ d(x, y), d(y, z) }. This strong form of the triangle inequality implies several distinctive geometric and topological features.

One consequence is that every triangle in an ultrametric space is isosceles with the two largest sides equal; in particular, if two of the pairwise distances are unequal, the third distance equals the larger of the two. Balls behave unusually: open balls are also closed, and the intersection of two balls is a ball. Moreover, any two balls are either disjoint or one contains the other. These properties yield a totally disconnected topology and a hierarchical structure that naturally encodes clustering relationships.

Examples and constructions: the canonical example comes from p-adic numbers. The p-adic metric d_p(x, y) := p^{-v_p(x − y)} is an ultrametric, arising from a non-Archimedean valuation. More generally, ultrametrics arise from rooted trees: if leaves represent points and each edge has a length, the distance between two leaves can be defined as the height (or total length) of their least common ancestor; such a distance is ultrametric. Finite ultrametric spaces correspond to finite rooted trees or dendrograms used in hierarchical clustering.

Applications and relevance: ultrametrics underpin models in biology (phylogenetics), linguistics, and information science. They are used to represent hierarchical relationships and to facilitate efficient data analysis, such as rapid nearest-neighbor searches and robust clustering. Not every metric is ultrametric; the ultrametric condition captures a strong form of closeness that emphasizes shared ancestry or common structure.