HOME

TheInfoList



OR:

In mathematics, an ultrametric space is a
metric space In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
in which the
triangle inequality In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. This statement permits the inclusion of degenerate triangles, bu ...
is strengthened to d(x,z)\leq\max\left\. Sometimes the associated metric is also called a non-Archimedean metric or super-metric. Although some of the theorems for ultrametric spaces may seem strange at a first glance, they appear naturally in many applications.


Formal definition

An ultrametric on a set is a real-valued function :d\colon M \times M \rightarrow \mathbb (where denote the
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s), such that for all : # ; # (''symmetry''); # ; # if then ; # (strong triangle inequality or ultrametric inequality). An ultrametric space is a pair consisting of a set together with an ultrametric on , which is called the space's associated distance function (also called a metric). If satisfies all of the conditions except possibly condition 4 then is called an ultrapseudometric on . An ultrapseudometric space is a pair consisting of a set and an ultrapseudometric on . In the case when is an Abelian group (written additively) and is generated by a length function \, \cdot\, (so that d(x,y) = \, x - y\, ), the last property can be made stronger using the Krull sharpening to: : \, x+y\, \le \max \left\ with equality if \, x\, \ne \, y\, . We want to prove that if \, x+y\, \le \max \left\, then the equality occurs if \, x\, \ne \, y\, . Without loss of generality, let us assume that \, x\, > \, y\, . This implies that \, x + y\, \le \, x\, . But we can also compute \, x\, =\, (x+y)-y\, \le \max \left\. Now, the value of \max \left\ cannot be \, y\, , for if that is the case, we have \, x\, \le \, y\, contrary to the initial assumption. Thus, \max \left\=\, x+y\, , and \, x\, \le \, x+y\, . Using the initial inequality, we have \, x\, \le \, x + y\, \le \, x\, and therefore \, x+y\, = \, x\, .


Properties

From the above definition, one can conclude several typical properties of ultrametrics. For example, for all x,y,z \in M, at least one of the three equalities d(x,y) = d(y,z) or d(x,z) = d(y,z) or d(x,y) = d(z,x) holds. That is, every triple of points in the space forms an
isosceles triangle In geometry, an isosceles triangle () is a triangle that has two sides of equal length. Sometimes it is specified as having ''exactly'' two sides of equal length, and sometimes as having ''at least'' two sides of equal length, the latter versio ...
, so the whole space is an isosceles set. Defining the (open) ball of radius r > 0 centred at x \in M as B(x;r) := \, we have the following properties: * Every point inside a ball is its center, i.e. if d(x,y) then B(x;r)=B(y;r). * Intersecting balls are contained in each other, i.e. if B(x;r)\cap B(y;s) is non-empty then either B(x;r) \subseteq B(y;s) or B(y;s) \subseteq B(x;r). * All balls of strictly positive radius are both open and
closed set In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric spac ...
s in the induced
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
. That is, open balls are also closed, and closed balls (replace < with \leq) are also open. * The set of all open balls with radius r and center in a closed ball of radius r>0 forms a partition of the latter, and the mutual distance of two distinct open balls is (greater or) equal to r. Proving these statements is an instructive exercise. 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), Σ*, over some alphabet Σ. Define the distance between two different words to be 2−''n'', 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''. * If ''r'' = (''rn'') is a sequence of
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s decreasing to zero, then , ''x'', ''r'' := lim sup''n''→∞ , ''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.


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 makes heavy use of the ultrametric nature of the ''p''-adic metric. * In
condensed matter physics Condensed matter physics is the field of physics that deals with the macroscopic and microscopic physical properties of matter, especially the solid and liquid phases which arise from electromagnetic forces between atoms. More generally, the s ...
, the self-averaging overlap between spins in the 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. Ultrametricity also appears in the theory of aperiodic solids. * In taxonomy and phylogenetic tree construction, ultrametric distances are also utilized by the UPGMA and WPGMA methods. 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 Ribonucleic acid (RNA) is a polymeric molecule essential in various biological roles in coding, decoding, regulation and expression of genes. RNA and deoxyribonucleic acid ( DNA) are nucleic acids. Along with lipids, proteins, and carbohydra ...
and
protein Proteins are large biomolecules and macromolecules that comprise one or more long chains of amino acid residues. Proteins perform a vast array of functions within organisms, including catalysing metabolic reactions, DNA replication, respon ...
data are analyzed, the ultrametricity assumption is called the
molecular clock The molecular clock is a figurative term for a technique that uses the mutation rate of biomolecules to deduce the time in prehistory when two or more life forms diverged. The biomolecular data used for such calculations are usually nucleo ...
. * Models of intermittency in three dimensional
turbulence In fluid dynamics, turbulence or turbulent flow is fluid motion characterized by chaotic changes in pressure and flow velocity. It is in contrast to a laminar flow, which occurs when a fluid flows in parallel layers, with no disruption between ...
of fluids make use of so-called cascades, and in discrete models of dyadic cascades, which have an ultrametric structure. * In
geography Geography (from Greek: , ''geographia''. Combination of Greek words ‘Geo’ (The Earth) and ‘Graphien’ (to describe), literally "earth description") is a field of science devoted to the study of the lands, features, inhabitants, a ...
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.


References


Bibliography

* *


Further reading

* . {{DEFAULTSORT:Ultrametric Space Metric geometry Metric spaces