What Makes a Metric an Ultrametric?
A metric measures the distance between pairs of points and requires the triangle inequality. An ultrametric imposes a stronger condition: the distance between two points cannot exceed the larger of their distances to a third point. This changes the possible geometry of triples. In particular, among three pairwise distances, the largest cannot occur only once.
As with metrics, the set \(X\) may be empty: the conditions are then vacuously satisfied by the unique function from \(X\times X\) to \([0,\infty)\). The interesting examples below have points. For nonnegative numbers \(a,b\), \(\max\{a,b\}\leq a+b\); therefore, if an ultrametric has points, its strong triangle inequality implies the ordinary triangle inequality.
Proof. Let \(d\) be an ultrametric on \(X\). Its nonnegativity, identity condition, and symmetry are part of the definition of an ultrametric. For any \(x,y,z\in X\), the strong triangle inequality and nonnegativity give $$ d(x,z)\leq\max\{d(x,y),d(y,z)\}\leq d(x,y)+d(y,z). $$ The last inequality holds because each of the two nonnegative terms is at most their sum. Thus \(d\) satisfies the ordinary triangle inequality as well, so it is a metric. \(\square\)
The Distances in a Triple
The strong triangle inequality gives a sharper conclusion than the ordinary triangle inequality. It does not say that all three distances are equal, but it rules out a uniquely largest distance.
Proof. Write \(a=d(x,y)\), \(b=d(y,z)\), and \(c=d(x,z)\). The strong triangle inequality applied to the three choices of endpoint gives $$ a\leq\max\{b,c\},\qquad b\leq\max\{a,c\},\qquad c\leq\max\{a,b\}. $$ If the maximum of \(a,b,c\) were attained only by \(a\), then \(a>\max\{b,c\}\), contradicting the first inequality. If it were attained only by \(b\), the second inequality would be contradicted; if only by \(c\), the third inequality would be contradicted. Hence the maximum occurs at least twice. Now suppose, for example, \(a>b\). The first inequality gives \(a\leq\max\{b,c\}\). Since \(b<a\), this forces \(c\geq a\). But the third inequality gives \(c\leq\max\{a,b\}=a\), so \(c=a\). The same argument applies whichever two unequal distances are considered. \(\square\)
This is a useful test: if a proposed distance has a triple with one uniquely largest distance, that distance cannot be an ultrametric. The converse is also useful in finite computations: once the metric conditions are checked, verifying the triple-distance rule for every triple verifies the strong triangle inequality.
Worked Example: An Ultrametric on Four Points
Let \(X=\{a,b,c,d\}\). Define \(d(x,x)=0\), and assign distances between distinct points by $$ d(a,b)=\frac14,\quad d(a,c)=d(b,c)=\frac12,\quad d(a,d)=d(b,d)=d(c,d)=1. $$ Symmetry defines the distances in the reverse order. We verify that this is an ultrametric.
All distances are nonnegative. The distance between distinct points is one of \(\frac14,\frac12,1\), so it is positive; the distance is zero exactly when the two points are equal. Symmetry holds by definition.
For triples of distinct points, there are exactly four possibilities. For \(\{a,b,c\}\), the three distances are \(\frac14,\frac12,\frac12\), so the maximum \(\frac12\) occurs twice. For \(\{a,b,d\}\), they are \(\frac14,1,1\), with maximum \(1\) twice. For \(\{a,c,d\}\), they are \(\frac12,1,1\); for \(\{b,c,d\}\), they are also \(\frac12,1,1\). In both cases the maximum is again \(1\), attained twice.
For each triple of distinct points, the largest distance is therefore no greater than the maximum of the other two distances. This is exactly the strong triangle inequality for each choice of the left-hand distance. If a triple has repeated points, the inequality also holds: a distance from a point to itself is \(0\), and the other two distances are equal. Thus all triples satisfy the strong triangle inequality.
Check: for the triple \((a,c,d)\), \(d(a,d)=1\), while \(d(a,c)=\frac12\) and \(d(c,d)=1\). The inequality reads \(1\leq\max\{\frac12,1\}=1\), as required. The assigned distances therefore define an ultrametric, and hence a metric.
A Distance from Shared Initial Entries
Infinite binary sequences give a natural example in which distance records how soon two sequences begin to differ. Indices start at \(1\), so the first differing index is not the number of matching initial entries.
Worked Example: Infinite Binary Sequences
Let \(X=\{0,1\}^{\mathbb{N}}\), the set of all infinite sequences whose entries are \(0\) or \(1\). For distinct \(x,y\in X\), let \(k(x,y)\) be the least positive integer \(k\) for which \(x_k\ne y_k\). Define $$ d(x,y)= \begin{cases} 0,&x=y,\\ 2^{-k(x,y)},&x\ne y. \end{cases} $$ We verify the strong triangle inequality, including the case of equal sequences.
For any \(x,y,z\in X\), put \(m=\min\{k(x,y),k(y,z)\}\), using \(k(u,v)=\infty\) when \(u=v\). If \(m\) is finite, then \(x\) and \(y\) agree at every index less than \(m\), and \(y\) and \(z\) agree at every index less than \(m\). Thus \(x\) and \(z\) agree at every index less than \(m\). If \(x\ne z\), this means \(k(x,z)\geq m\), so $$ d(x,z)=2^{-k(x,z)}\leq 2^{-m} =\max\{2^{-k(x,y)},2^{-k(y,z)}\} =\max\{d(x,y),d(y,z)\}. $$ If \(x=z\), then \(d(x,z)=0\), and the same inequality holds because the right-hand side is nonnegative. If \(m=\infty\), then \(x=y=z\), and all three distances are \(0\). This proves the strong triangle inequality in every case. Symmetry follows because the first differing index is unchanged when the two sequences are exchanged, and the distance is zero exactly for equal sequences. So \(d\) is an ultrametric.
For a specific calculation, take \(x=000\ldots\), \(y=0011\ldots\), and \(z=0111\ldots\). The sequences \(x,y\) first differ at index \(3\), so \(d(x,y)=2^{-3}=\frac18\). The sequences \(x,z\) first differ at index \(2\), so \(d(x,z)=2^{-2}=\frac14\). The sequences \(y,z\) also first differ at index \(2\), so \(d(y,z)=2^{-2}=\frac14\). The largest distance is \(\frac14\), and it occurs twice.
Check: for the triple in the order \((x,y,z)\), \(d(x,z)=\frac14\), while \(d(x,y)=\frac18\) and \(d(y,z)=\frac14\). Hence \(\frac14\leq\max\{\frac18,\frac14\}=\frac14\). This agrees with the general proof.
Distance Thresholds Give Equivalence Relations
For each fixed nonnegative threshold, an ultrametric groups together points whose mutual distance does not exceed that threshold. The strong triangle inequality is precisely what ensures that this grouping is transitive.
Proof. First suppose \(d\) is an ultrametric. For every \(x\in X\), \(d(x,x)=0\leq r\), so \(\sim_r\) is reflexive. Symmetry of \(d\) makes the relation symmetric. If \(x\sim_r y\) and \(y\sim_r z\), then \(d(x,y)\leq r\) and \(d(y,z)\leq r\). The strong triangle inequality gives $$ d(x,z)\leq\max\{d(x,y),d(y,z)\}\leq r, $$ so \(x\sim_r z\). Thus the relation is transitive and is an equivalence relation.
Conversely, suppose \(\sim_r\) is an equivalence relation for every \(r\geq0\). Take any \(x,y,z\in X\), and set \(r=\max\{d(x,y),d(y,z)\}\), which is nonnegative. Then \(x\sim_r y\) and \(y\sim_r z\). Transitivity gives \(x\sim_r z\), meaning \(d(x,z)\leq r=\max\{d(x,y),d(y,z)\}\). This is the strong triangle inequality, so \(d\) is an ultrametric. \(\square\)
Worked Example: The Discrete Metric Is an Ultrametric
Let \(X\) be any set, with the discrete metric \(d(x,y)=0\) when \(x=y\) and \(d(x,y)=1\) when \(x\ne y\). It is symmetric and nonnegative, and its distance is zero exactly for equal points. To check the strong triangle inequality, fix \(x,y,z\in X\). If \(x=z\), then \(d(x,z)=0\), which is at most the nonnegative right-hand side. If \(x\ne z\), then \(d(x,z)=1\). It is not possible for both \(d(x,y)\) and \(d(y,z)\) to be \(0\), since that would imply \(x=y=z\). At least one of them is therefore \(1\), and \(\max\{d(x,y),d(y,z)\}=1\). In either case, the strong triangle inequality holds.
When \(x,y,z\) are all distinct, the three distances are \(1,1,1\). If two points coincide, the distances have the form \(0,1,1\); if all coincide, they are \(0,0,0\). Each case agrees with the triple-distance rule.
Check: for three distinct points, \(d(x,z)=1\) and \(\max\{d(x,y),d(y,z)\}=\max\{1,1\}=1\). Thus the inequality holds with equality. This computation also covers every distinct-point triple, since all its pairwise distances are \(1\).
A Common Pitfall
Common pitfall: the ordinary triangle inequality does not imply the strong triangle inequality. For example, on \(\mathbb{R}\) with its standard metric \(d(x,y)=|x-y|\), take \(x=0\), \(y=1\), and \(z=2\). Then \(d(0,2)=|0-2|=2\), whereas \(d(0,1)=|0-1|=1\) and \(d(1,2)=|1-2|=1\). The ordinary triangle inequality holds because \(2\leq1+1=2\), but the strong triangle inequality would require \(2\leq\max\{1,1\}=1\), which is false. The correction is not to replace the maximum by a sum: the maximum is the defining, stronger condition, and this familiar metric on the real line does not satisfy it.
Ultrametrics are useful whenever distance is meant to express a hierarchy of closeness: a pair that remains close at a given threshold belongs to the same threshold class, and transitivity forces those classes to be consistent. The triple-distance rule is a compact way to recognize this structure, while the threshold relation provides a direct way to verify it.
Check Your Understanding
Use the definition and the proved triple-distance rule to check your reasoning.
- Explain why every ultrametric satisfies the ordinary triangle inequality.
- In an ultrametric, suppose \(d(x,y)=3\) and \(d(y,z)=5\). What must \(d(x,z)\) be?
- For three distinct binary sequences whose first differing indices are \(2,4,2\), respectively, compute their three distances and identify the maximum.
- Show that the usual metric on \(\mathbb{R}\) is not an ultrametric by choosing a suitable triple.
- For an ultrametric and a fixed \(r\geq0\), explain why \(d(x,y)\leq r\) and \(d(y,z)\leq r\) imply \(d(x,z)\leq r\).