Ultrametric space

(Redirected from Ultrametric)

In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to for all , , and . Sometimes the associated metric is also called a non-Archimedean metric or super-metric.

Formal definition

edit

An ultrametric on a set M is a real-valued function

 

(where denote the real numbers), such that for all x, y, zM:

  1. d(x, y) ≥ 0;
  2. d(x, y) = d(y, x) (symmetry);
  3. d(x, x) = 0;
  4. if d(x, y) = 0 then x = y;
  5. d(x, z) ≤ max {d(x, y), d(y, z)} (strong triangle inequality or ultrametric inequality).

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

If d satisfies all of the conditions except possibly condition 4 then d is called an ultrapseudometric on M. An ultrapseudometric space is a pair (M, d) consisting of a set M and an ultrapseudometric d on M.[1]

In the case when M is an Abelian group (written additively) and d is generated by a length function   (so that  ), the last property can be made stronger using the Krull sharpening to:

  with equality if  .

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

edit
 
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  , 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 (open) 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  .
  • 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   with  ) are also open.
  • 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 (greater or) equal to  .

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

edit
  • 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), Σ*, over some alphabet Σ. Define the distance between two different words to be 2n, 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 length n 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 (p < n) appears the same number of times (which could also be zero) both in x and y.[3]
  • If r = (rn) 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. (Note that this is not a seminorm since it lacks homogeneity — If the rn are allowed to be zero, one should use here the rather unusual convention that 00 = 0.)
  • If G is an edge-weighted undirected graph, all edge weights are positive, and d(u,v) is the weight of the minimax path between u and 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, form an ultrametric space, and all finite ultrametric spaces may be represented in this way.[4]

Applications

edit

References

edit
  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

edit

Further reading

edit
edit