Editing Ultrametric space

{{Short description|Type of metric space}}
In [[mathematics]], an '''ultrametric space''' is a [[metric space]] in which the [[triangle inequality]] is strengthened to <math>d(x,z)\leq\max\left\{d(x,y),d(y,z)\right\}</math> for all <math>x</math>, <math>y</math>, and <math>z</math>. Sometimes the associated metric is also called a '''non-Archimedean metric''' or '''super-metric'''.

== Formal definition ==

An '''ultrametric''' on a [[Set (mathematics)|set]] {{mvar|M}} is a [[Real number|real]]-valued function
:<math>d\colon M \times M \rightarrow \mathbb{R}</math>
(where {{math|ℝ}} denote the [[real number]]s), such that for all {{math|''x'', ''y'', ''z'' &isin; ''M''}}:
# {{math|''d''(''x'', ''y'') &ge; 0}};
# {{math|1=''d''(''x'', ''y'') = ''d''(''y'', ''x'')}} (''symmetry'');
# {{math|1=''d''(''x'', ''x'') = 0}};
# if {{math|1=''d''(''x'', ''y'') = 0}} then {{math|1=''x'' = ''y''}};
# {{math|1=''d''(''x'', ''z'') &le; max {''d''(''x'', ''y''), ''d''(''y'', ''z'') }}} ('''strong triangle inequality''' or '''ultrametric inequality''').

An '''ultrametric space''' is a pair {{math|(''M'', ''d'')}} consisting of a set {{mvar|M}} together with an ultrametric {{mvar|d}} on {{mvar|M}}, which is called the space's associated distance function (also called a [[metric (mathematics)|metric]]). 

If {{mvar|d}} satisfies all of the conditions except possibly condition 4, then {{mvar|d}} is called an '''ultrapseudometric''' on {{mvar|M}}. An '''ultrapseudometric space''' is a pair {{math|(''M'', ''d'')}} consisting of a set {{mvar|M}} and an ultrapseudometric {{mvar|d}} on {{mvar|M}}.{{sfn | Narici|Beckenstein | 2011 | pp=1-18}} 

In the case when {{mvar|M}} is an Abelian group (written additively) and {{mvar|d}} is generated by a [[length function]] <math>\|\cdot\|</math>  (so that <math>d(x,y) = \|x - y\|</math>), the last property can be made stronger using the [[Wolfgang Krull|Krull]] sharpening to:
: <math>\|x+y\|\le \max \left\{ \|x\|, \|y\| \right\}</math> with equality if <math>\|x\| \ne \|y\|</math>.

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

== Properties ==
[[File:Strong_triangle_ineq.svg|thumb|upright=1.25|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 <math>x,y,z \in M</math>, at least one of the three equalities <math>d(x,y) = d(y,z)</math> or <math>d(x,z) = d(y,z)</math> or <math>d(x,y) = d(z,x)</math> 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|(open) ball]] of radius <math>r > 0</math> centred at <math>x \in M</math> as <math>B(x;r) := \{y \in M \mid d(x,y) < r\}</math>, we have the following properties:
* Every point inside a ball is its center, i.e. if <math>d(x,y)<r</math> then <math>B(x;r)=B(y;r)</math>.
* Intersecting balls are contained in each other, i.e. if <math>B(x;r)\cap B(y;s)</math> is [[Empty set|non-empty]] then either <math>B(x;r) \subseteq B(y;s)</math> or <math>B(y;s) \subseteq B(x;r)</math>.
* All balls of strictly positive radius are both [[Open set|open]] and [[closed set]]s in the induced [[topology]]. That is, open balls are also closed, and closed balls (replace <math><</math> with <math>\leq</math>) are also open.
* The set of all open balls with radius <math>r</math> and center in a closed ball of radius <math>r>0</math> forms a [[partition of a set|partition]] of the latter, and the mutual distance of two distinct open balls is (greater or) equal to <math>r</math>.

Proving these statements is an instructive exercise.<ref>{{cite web |work=Stack Exchange |url=https://math.stackexchange.com/q/1141731 |title=Ultrametric Triangle Inequality }}</ref> 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|''p''-adic numbers]] form a complete ultrametric space.
* Consider the [[Formal language|set of words]] of arbitrary length (finite or infinite), Σ<sup>*</sup>, over some alphabet Σ. Define the distance between two different words to be 2<sup>−''n''</sup>, where ''n'' is the first place at which the words differ. The resulting metric is an ultrametric.
* The [[Formal language|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''.<ref>{{citation
 | last = Osipov | first = Gutkin
 | issue = 26
 | journal = Nonlinearity
 | volume = 26
 | pages = 177–200
 | title = Clustering of periodic orbits in chaotic systems
 | doi=10.1088/0951-7715/26/1/177
 | year = 2013| bibcode = 2013Nonli..26..177G
 }}.</ref>
* If ''r'' = (''r<sub>n</sub>'') is a sequence of [[real number]]s decreasing to zero, then |''x''|<sub>''r''</sub> := [[lim sup]]<sub>''n''→∞</sub> |''x<sub>n</sub>''|<sup>''r<sub>n</sub>''</sup> 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 [[homogeneous function|homogeneity]] &mdash; If the ''r<sub>n</sub>'' are allowed to be zero, one should use here the rather unusual convention that [[Zero to the power of zero|0<sup>0</sup>]]&nbsp;=&nbsp;0.)
* If ''G'' is an edge-weighted [[undirected graph]], all edge weights are positive, and ''d''(''u'',''v'') is the weight of the [[widest path problem|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.<ref>{{citation
 | last = Leclerc | first = Bruno
 | mr = 623034
 | issue = 73
 | journal = Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines
 | language = fr
 | pages = 5–37, 127
 | title = Description combinatoire des ultramétriques
 | year = 1981}}.</ref>

== Applications ==
* A [[contraction mapping]] may then be thought of as a way of approximating the final result of a computation (which can be guaranteed to exist by the [[Banach fixed-point theorem]]). Similar ideas can be found in [[domain theory]]. [[p-adic analysis|''p''-adic analysis]] makes heavy use of the ultrametric nature of the [[p-adic number|''p''-adic metric]].
* In [[condensed matter physics]], the [[self-averaging]] overlap between spins in the [[Spin glass#Sherrington–Kirkpatrick model|SK Model]] of [[spin glasses]] exhibits an ultrametric structure, with the solution given by the full replica symmetry breaking procedure first outlined by [[Giorgio Parisi]] and coworkers.<ref>Mezard, M; Parisi, G; and Virasoro, M: ''SPIN GLASS THEORY AND BEYOND'', World Scientific, 1986. {{ISBN|978-9971-5-0116-7}}</ref> Ultrametricity also appears in the theory of aperiodic solids.<ref name=physics_apps>{{cite journal |last1=Rammal |first1=R. |last2=Toulouse |first2=G. |last3=Virasoro |first3=M. |title=Ultrametricity for physicists |journal=Reviews of Modern Physics |year=1986 |volume=58 |issue=3 |pages=765–788 |doi=10.1103/RevModPhys.58.765 |url=http://rmp.aps.org/abstract/RMP/v58/i3/p765_1 |access-date=20 June 2011|bibcode=1986RvMP...58..765R }}</ref>
* In [[Taxonomy (biology)|taxonomy]] and [[phylogenetic tree]] construction, ultrametric distances are also utilized by the [[UPGMA]] and [[WPGMA]] methods.<ref>Legendre, P. and Legendre, L. 1998. Numerical Ecology. Second English Edition. Developments in Environmental Modelling 20. Elsevier, Amsterdam.</ref> 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 dimensional [[turbulence]] of fluids make use of so-called cascades, and in discrete models of dyadic cascades, which have an ultrametric structure.<ref> {{cite journal |last1=Benzi|first1=R. |last2=Biferale |first2=L. |last3=Trovatore |first3=E. |title=Ultrametric Structure of Multiscale Energy Correlations in Turbulent Models |journal=Physical Review Letters |year=1997 |volume=79 |issue=9 |pages=1670–1674 |doi=10.1103/PhysRevLett.79.1670 |arxiv=chao-dyn/9705018 |bibcode=1997PhRvL..79.1670B |s2cid=53120932 }}</ref>
* 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.<ref>{{Cite journal|last=Papadimitriou|first=Fivos|year=2013|title=Mathematical modelling of land use and landscape complexity with ultrametric topology|journal=Journal of Land Use Science|language=en|volume=8|issue=2|pages=234–254|doi=10.1080/1747423x.2011.637136|s2cid=121927387|issn=1747-423X|doi-access=free}}</ref>

== References ==
{{Reflist|2}}

== Bibliography ==
* {{Narici Beckenstein Topological Vector Spaces|edition=2}} <!-- {{sfn | Narici | 2011 | p=}} -->
* {{Schaefer Wolff Topological Vector Spaces|edition=2}} <!-- {{sfn | Schaefer | 1999 | p=}} -->

== Further reading ==
* {{citation | last = Kaplansky | first = I. | author-link = Irving Kaplansky | isbn = 978-0-8218-2694-2  | publisher = AMS Chelsea Publishing | title = Set Theory and Metric Spaces | year = 1977}}.

==External links==
* {{cci}}

[[Category:Metric geometry]]
[[Category:Metric spaces]]