Ultrametric

☆ Save On Wikipedia ↗

In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to d ( x , z ) ≤ max { d ( x , y ) , d ( y , z ) } {\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}} {\displaystyle d(x,z)\leq \max \left\{d(x,y),d(y,z)\right\}} for all x {\displaystyle x} {\displaystyle x}, y {\displaystyle y} {\displaystyle y}, and z {\displaystyle z} {\displaystyle z}. Sometimes the associated metric is also called a non-Archimedean metric or super-metric.

Formal definition

An ultrametric on a set M {\displaystyle M} {\displaystyle M} is a real-valued function

d : M × M → R {\displaystyle d\colon M\times M\rightarrow \mathbb {R} } {\displaystyle d\colon M\times M\rightarrow \mathbb {R} }

(where R {\displaystyle \mathbb {R} } {\displaystyle \mathbb {R} } denotes the real numbers), such that for all x , y , z ∈ M {\displaystyle x,y,z\in M} {\displaystyle x,y,z\in M}:

  1. d ( x , y ) ≥ 0 {\displaystyle d(x,y)\geq 0} {\displaystyle d(x,y)\geq 0} with equality if and only if x = y {\displaystyle x=y} {\displaystyle x=y} (non-degeneracy)
  2. d ( x , y ) = d ( y , x ) {\displaystyle d(x,y)=d(y,x)} {\displaystyle d(x,y)=d(y,x)} (symmetry)
  3. d ( x , z ) ≤ max { d ( x , y ) , d ( y , z ) } {\displaystyle d(x,z)\leq \max\{d(x,y),d(y,z)\}} {\displaystyle d(x,z)\leq \max\{d(x,y),d(y,z)\}} (strong triangle inequality or ultrametric inequality).

An ultrametric space is a pair ( M , d ) {\displaystyle (M,d)} {\displaystyle (M,d)} consisting of a set M {\displaystyle M} {\displaystyle M} together with an ultrametric d {\displaystyle d} {\displaystyle d} on M {\displaystyle M} {\displaystyle M}, which is called the space's associated distance function (also called a metric).

If d {\displaystyle d} {\displaystyle d} satisfies all of the conditions but the "if and only if" in condition 1 is weakened to "if", then d {\displaystyle d} {\displaystyle d} is called an ultrapseudometric on M {\displaystyle M} {\displaystyle M}. An ultrapseudometric space is a pair ( M , d ) {\displaystyle (M,d)} {\displaystyle (M,d)} consisting of a set M {\displaystyle M} {\displaystyle M} and an ultrapseudometric d {\displaystyle d} {\displaystyle d} on M {\displaystyle M} {\displaystyle M}.[1]

In the case when M {\displaystyle M} {\displaystyle M} is an Abelian group (written additively) and d {\displaystyle d} {\displaystyle d} is generated by a length function ‖ ⋅ ‖ {\displaystyle \|\cdot \|} {\displaystyle \|\cdot \|} (so that d ( x , y ) = ‖ x − y ‖ {\displaystyle d(x,y)=\|x-y\|} {\displaystyle d(x,y)=\|x-y\|}), the last property can be made stronger using the Krull sharpening to:

‖ x + y ‖ ≤ max { ‖ x ‖ , ‖ y ‖ } {\displaystyle \|x+y\|\leq \max \left\{\|x\|,\|y\|\right\}} {\displaystyle \|x+y\|\leq \max \left\{\|x\|,\|y\|\right\}} with equality if ‖ x ‖ ≠ ‖ y ‖ {\displaystyle \|x\|\neq \|y\|} {\displaystyle \|x\|\neq \|y\|}.

We want to prove that if ‖ x + y ‖ ≤ max { ‖ x ‖ , ‖ y ‖ } {\displaystyle \|x+y\|\leq \max \left\{\|x\|,\|y\|\right\}} {\displaystyle \|x+y\|\leq \max \left\{\|x\|,\|y\|\right\}}, then the equality occurs if ‖ x ‖ ≠ ‖ y ‖ {\displaystyle \|x\|\neq \|y\|} {\displaystyle \|x\|\neq \|y\|}. Without loss of generality, let us assume that ‖ x ‖ > ‖ y ‖ . {\displaystyle \|x\|>\|y\|.} {\displaystyle \|x\|>\|y\|.} This implies that ‖ x + y ‖ ≤ ‖ x ‖ {\displaystyle \|x+y\|\leq \|x\|} {\displaystyle \|x+y\|\leq \|x\|}. But we can also compute ‖ x ‖ = ‖ ( x + y ) − y ‖ ≤ max { ‖ x + y ‖ , ‖ y ‖ } {\displaystyle \|x\|=\|(x+y)-y\|\leq \max \left\{\|x+y\|,\|y\|\right\}} {\displaystyle \|x\|=\|(x+y)-y\|\leq \max \left\{\|x+y\|,\|y\|\right\}}. Now, the value of max { ‖ x + y ‖ , ‖ y ‖ } {\displaystyle \max \left\{\|x+y\|,\|y\|\right\}} {\displaystyle \max \left\{\|x+y\|,\|y\|\right\}} cannot be ‖ y ‖ {\displaystyle \|y\|} {\displaystyle \|y\|}, for if that is the case, we have ‖ x ‖ ≤ ‖ y ‖ {\displaystyle \|x\|\leq \|y\|} {\displaystyle \|x\|\leq \|y\|} contrary to the initial assumption. Thus, max { ‖ x + y ‖ , ‖ y ‖ } = ‖ x + y ‖ {\displaystyle \max \left\{\|x+y\|,\|y\|\right\}=\|x+y\|} {\displaystyle \max \left\{\|x+y\|,\|y\|\right\}=\|x+y\|}, and ‖ x ‖ ≤ ‖ x + y ‖ {\displaystyle \|x\|\leq \|x+y\|} {\displaystyle \|x\|\leq \|x+y\|}. Using the initial inequality, we have ‖ x ‖ ≤ ‖ x + y ‖ ≤ ‖ x ‖ {\displaystyle \|x\|\leq \|x+y\|\leq \|x\|} {\displaystyle \|x\|\leq \|x+y\|\leq \|x\|} and therefore ‖ x + y ‖ = ‖ x ‖ {\displaystyle \|x+y\|=\|x\|} {\displaystyle \|x+y\|=\|x\|}.

Properties

In the triangle on the right, the two bottom points x and y violate the condition d(x, y) ≤ max{d(x, z), d(y, z)}.

From the above definition, one can conclude several typical properties of ultrametrics. For example, for all x , y , z ∈ M {\displaystyle x,y,z\in M} {\displaystyle x,y,z\in M}, at least one of the three equalities d ( x , y ) = d ( y , z ) {\displaystyle d(x,y)=d(y,z)} {\displaystyle d(x,y)=d(y,z)} or d ( x , z ) = d ( y , z ) {\displaystyle d(x,z)=d(y,z)} {\displaystyle d(x,z)=d(y,z)} or d ( x , y ) = d ( z , x ) {\displaystyle d(x,y)=d(z,x)} {\displaystyle d(x,y)=d(z,x)} holds. That is, every triple of points in the space forms an isosceles triangle, so the whole space is an isosceles set.

Defining the (open) ball of radius r > 0 {\displaystyle r>0} {\displaystyle r>0} centred at x ∈ M {\displaystyle x\in M} {\displaystyle x\in M} as B ( x ; r ) := { y ∈ M ∣ d ( x , y ) < r } {\displaystyle B(x;r):=\{y\in M\mid d(x,y)<r\}} {\displaystyle B(x;r):=\{y\in M\mid d(x,y)<r\}}, we have the following properties:

  • Every point inside a ball is one of its centers, i.e. if d ( x , y ) < r {\displaystyle d(x,y)<r} {\displaystyle d(x,y)<r} then B ( x ; r ) = B ( y ; r ) {\displaystyle B(x;r)=B(y;r)} {\displaystyle B(x;r)=B(y;r)}.
  • Intersecting balls are contained in each other, i.e. if B ( x ; r ) ∩ B ( y ; s ) {\displaystyle B(x;r)\cap B(y;s)} {\displaystyle B(x;r)\cap B(y;s)} is non-empty then either B ( x ; r ) ⊆ B ( y ; s ) {\displaystyle B(x;r)\subseteq B(y;s)} {\displaystyle B(x;r)\subseteq B(y;s)} or B ( y ; s ) ⊆ B ( x ; r ) {\displaystyle B(y;s)\subseteq B(x;r)} {\displaystyle B(y;s)\subseteq B(x;r)}.
  • All balls of strictly positive radius are both open and closed sets in the induced topology. That is, open balls are also closed, and closed balls (replace < {\displaystyle <} {\displaystyle <} with ≤ {\displaystyle \leq } {\displaystyle \leq }) are also open.
  • The set of all open balls with radius r {\displaystyle r} {\displaystyle r} and center in a closed ball of radius r > 0 {\displaystyle r>0} {\displaystyle r>0} forms a partition of the latter, and the mutual distance of two distinct open balls is (greater or) equal to r {\displaystyle r} {\displaystyle r}.

Proving these statements is an instructive exercise.[2] 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.

Examples

  • The discrete metric is an ultrametric.
  • The p-adic numbers form a complete ultrametric space.
  • Consider the set of words of arbitrary length (finite or infinite), Σ ∗ {\displaystyle \Sigma ^{*}} {\displaystyle \Sigma ^{*}}, over some alphabet Σ {\displaystyle \Sigma } {\displaystyle \Sigma }. Define the distance between two different words to be 2 − n {\displaystyle 2^{-n}} {\displaystyle 2^{-n}}, where n {\displaystyle n} {\displaystyle 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 length n {\displaystyle n} {\displaystyle n} over some alphabet Σ {\displaystyle \Sigma } {\displaystyle \Sigma } is an ultrametric space with respect to the p-close distance. Two words x {\displaystyle x} {\displaystyle x} and y {\displaystyle y} {\displaystyle y} are p-close if any substring of p consecutive letters ( p < n {\displaystyle p<n} {\displaystyle p<n}) appears the same number of times (which could also be zero) both in x {\displaystyle x} {\displaystyle x} and y {\displaystyle y} {\displaystyle y}.[3]
  • If r = ( r n ) {\displaystyle r=(r_{n})} {\displaystyle r=(r_{n})} is a sequence of real numbers decreasing to zero, then | x | r := lim sup n → ∞ | x n | r n {\displaystyle |x|_{r}:=\limsup _{n\rightarrow \infty }|x_{n}|^{r_{n}}} {\displaystyle |x|_{r}:=\limsup _{n\rightarrow \infty }|x_{n}|^{r_{n}}} induces an ultrametric on the space of all complex sequences for which it is finite. (Note that this is not a seminorm since it lacks homogeneity — If the r n {\displaystyle r_{n}} {\displaystyle r_{n}} are allowed to be zero, one should use here the rather unusual convention that 0 0 = 0 {\displaystyle 0^{0}=0} {\displaystyle 0^{0}=0} (Zero to the power of zero).
  • If G {\displaystyle G} {\displaystyle G} is an edge-weighted undirected graph, all edge weights are positive, and d ( u , v ) {\displaystyle d(u,v)} {\displaystyle d(u,v)} is the weight of the minimax path between u {\displaystyle u} {\displaystyle u} and v {\displaystyle v} {\displaystyle v} (that is, the largest weight of an edge, on a path chosen to minimize this largest weight), then the vertices of the graph, with distance measured by d {\displaystyle d} {\displaystyle d}, form an ultrametric space, and all finite ultrametric spaces may be represented in this way.[4]

Applications

References

  1. Narici & Beckenstein 2011, pp. 1–18.
  2. "Ultrametric Triangle Inequality". Stack Exchange.
  3. Osipov, Gutkin (2013), "Clustering of periodic orbits in chaotic systems", Nonlinearity, 26 (26): 177–200, Bibcode:2013Nonli..26..177G, doi:10.1088/0951-7715/26/1/177.
  4. Leclerc, Bruno (1981), "Description combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (in French) (73): 5–37, 127, MR 0623034.
  5. Mezard, M; Parisi, G; and Virasoro, M: SPIN GLASS THEORY AND BEYOND, World Scientific, 1986. ISBN 978-9971-5-0116-7
  6. Rammal, R.; Toulouse, G.; Virasoro, M. (1986). "Ultrametricity for physicists". Reviews of Modern Physics. 58 (3): 765–788. Bibcode:1986RvMP...58..765R. doi:10.1103/RevModPhys.58.765. Retrieved 20 June 2011.
  7. Legendre, P. and Legendre, L. 1998. Numerical Ecology. Second English Edition. Developments in Environmental Modelling 20. Elsevier, Amsterdam.
  8. Benzi, R.; Biferale, L.; Trovatore, E. (1997). "Ultrametric Structure of Multiscale Energy Correlations in Turbulent Models". Physical Review Letters. 79 (9): 1670–1674. arXiv:chao-dyn/9705018. Bibcode:1997PhRvL..79.1670B. doi:10.1103/PhysRevLett.79.1670. S2CID 53120932.
  9. Papadimitriou, Fivos (2013). "Mathematical modelling of land use and landscape complexity with ultrametric topology". Journal of Land Use Science. 8 (2): 234–254. doi:10.1080/1747423x.2011.637136. ISSN 1747-423X. S2CID 121927387.

Bibliography

Further reading