Weak convergence in a Hilbert space is defined as pointwise convergence of functionals associated to the elements of the space. Specifically, weakly if the associated functionals converge to pointwise.
How could this idea be extended to metric spaces without linear structure? To begin with, could be replaced with , since this agrees with original up to some constant terms. Also, here could be for any fixed ; to avoid introducing another variable here, let’s use for the purpose of fixed reference point . Now we have a metric space version of the weak convergence: the functions
must converge pointwise to
The triangle inequality shows that strong convergence implies weak convergence, as expected. And the converse is not necessarily true, as the example of a Hilbert space shows.
Aside: the above is not the only way to define weak convergence in metric spaces. Another approach is to think of in terms of projection onto a line through . A metric space version of this concept is the nearest-point projection onto a geodesic curve. This is a useful approach, but it is only viable for metric spaces with additional properties (geodesic, nonpositive curvature).
Also, both of these approaches take the Hilbert space case as the point of departure, and do not necessarily capture weak convergence in other normed spaces.
Let’s try this out in with the standard basis sequence . Here . Is there an element such that
for all ?
Considering both sides as functions of one variable , for a fixed , shows that for , because the left hand side is non-differentiable at while the right hand side is non-differentiable at . Then the desired identity simplifies to which is false. Oh well, that sequence wasn’t weakly convergent to begin with: by Schur’s theorem, every weakly convergent sequence in also converges strongly.
This example also shows that not every bounded sequence in a metric space has a weakly convergent subsequence, unlike the way it works in Hilbert spaces.
An isometry is a map between two metric spaces which preserves all distances: for all . (After typing a bunch of such formulas, one tends to prefer shorter notation: , with the metric inferred from contexts.) It’s a popular exercise to prove that every isometry from a compact metric space into itself is surjective.
A rough isometry allows additive distortion of distances: . (As contrasted with bi-Lipschitz maps, which allow multiplicative distortion). Rough isometries ignore small-scale features (in particular, they need not be continuous), but accurately capture the large scale structure of a space. This makes them convenient for studying hyperbolic spaces (trees and their relatives), where the large-scale structure is of interest.
If is an -rough isometry, then the Gromov-Hausdorff distance between and is at most . This follows from a convenient characterization of : it is equal to where the infimum is taken over all subsets that project surjectively onto each factor, and .
Since small-scale features are ignored, it is not quite natural to talk about rough isometries being surjective. A natural concept for them is -surjectivity, meaning that every point of is within distance of . When this happens, we can conclude that , because the Hausdorff distance between and is at most .
Recalling that an isometry of a compact metric space into is automatically onto, it is natural to ask whether -rough isometries of into are -surjective. This, however, turns out to be false in general.
First example, a finite space: with the metric (when ). Consider the backward shift (and ). By construction, this is a rough isometry with . Yet, the point is within distance from .
The above metric can be thought of a the distance one has to travel from to with a mandatory visit to . This makes it similar to the second example.
Second example, a geodesic space: is the graph shown below, a subset of with the intrinsic (path) metric, i.e., the length of shortest path within the set.
Define where means the positive part. Again, this is a -rough isometry. The omitted part, shown in red below, contains a ball of radius centered at . Of course, can be replaced by any positive integer.
Both of these examples are intrinsically high-dimensional: they cannot be accurately embedded into for low (using the restriction metric rather than the path metric). This raises a question: does there exist such that for every compact subset , equipped with the restriction metric, every -rough isometry is -surjective?
A metric space has the binary intersection property if every collection of closed balls has nonempty intersection unless there is a trivial obstruction: the distance between centers of two balls exceeds the sum of their radii. In other words, for every family of points and numbers such that for all there exists such that for all .
For example, has this property: works. But does not:
The space of bounded sequences has the binary intersection property, and so does the space of all bounded functions with the supremum norm. Indeed, the construction for generalizes: given a family of bounded functions and numbers as in the definition, let .
The better known space of continuous functions has the finite version of binary intersection property, because for a finite family, the construction produces a continuous function. However, the property fails without finiteness, as the following example shows.
Example. Let be a function such that for , for , and is linear in between.
Since for all , we can choose for all . But if a function is such that for all , then for and for . There is no continuous function that does that.
More precisely, for every we have because in a small neighborhood of , while change from to in the same neighborhood when is large.
Given a discontinuous function, one can approximate it with a continuous function in some way: typically, using a mollifier. But such approximations tend to change the function even if it was continuous to begin with. Let’s try to not fix what isn’t broken: look for a retraction of onto , that is a map such that for all .
The failure of binary intersection property, as demonstrated by the sequence above, implies that cannot be a contraction. Indeed, let . This is a discontinuous function such that for all . Since , it follows that cannot be -Lipschitz with a constant .
The space of continuous functions (say, on ) is usually given the uniform metric: . In other words, this is the smallest number such that from every point of the graph of one function we can jump to the graph of another function by moving at distance in vertical direction.
Now that I put it this way, why don’t we drop “in vertical direction”? It’ll still be a metric, namely the Hausdorff metric between the graphs of and . It’s natural to call it the graphical metric, denoted ; from the definition it’s clear that .
Some interesting things happen when the space of continuous functions is equipped with . For one thing, it’s no longer a complete space: the sequence is Cauchy in but has no limit.
On the other hand, the bounded subsets of are totally bounded. Indeed, given and we can cover the rectangle with a rectangular mesh of diameter at most . For each function with , consider the set of rectangles that its graph visits. There are finitely many possibilities for the sets of visited rectangles. And two functions that share the same set of visited rectangles are at graphical distance at most from each other.
Thus, the completion of in the graphical metric should be a nice space: bounded closed subsets will be compact in it. What is this completion, concretely?
Here is a partial answer: if is a graphically Cauchy sequence, its limit is the compact set where
(the infimum taken over all sequences converging to ), and
It’s not hard to see that is upper semicontinuous and is lower semicontinuous. Of course, . It seems that the set of such pairs indeed describes the graphical completion of continuous functions.
For example, the limit of is described by the pair , . Geometrically, it’s a broken line with horizontal and vertical segments
For another example, the limit of is described by the pair , . Geometrically, it’s a square.
In the novella Flatland by Edwin A. Abbott, the Sphere leads the Square “downward to the lowest depth of existence, even to the realm of Pointland, the Abyss of No dimensions”:
I caught these words, “Infinite beatitude of existence! It is; and there is nothing else beside It.” […] “It fills all Space,” continued the little soliloquizing Creature, “and what It fills, It is. What It thinks, that It utters; and what It utters, that It hears; and It itself is Thinker, Utterer, Hearer, Thought, Word, Audition; it is the One, and yet the All in All. Ah, the happiness, ah, the happiness of Being!”
Indeed, Pointland (a one-point space) is zero-dimensional by every concept of dimension that I know of. Yet there is something smaller: Nothingland — empty space, — whose non-existent inhabitants must be perpetually enjoying the happiness of Non-Being.
What is the dimension of Nothingland?
In topology, the empty set has dimension . This fits the inductive definition of topological dimension, which is the smallest number such that the space can be minced by removing a subset of dimension . (Let’s say a space has been minced if what’s left has no connected subsets other than points.)
Thus, a nonempty finite (or countable) set has dimension : it’s minced already, so we remove nothing, a set of dimension . A line or a curve is one-dimensional: they can be minced by removing a zero-dimensional subset, like rational numbers.
The Flatland itself can be minced by removing a one-dimensional subset (e.g., circles with rational radius and rational coordinates of the center), so it is two-dimensional. And so on.
The convention , helpful in the definition, gets in the way later. For example, the topological dimension is subadditive under products: … unless both and are empty, because then is false. So the case must be excluded from the product theorem. We would not have to do this if was defined to be .
Next, consider the Hausdorff dimension. Its definition is not inductive, but one has to introduce other concepts first. First, define the -dimensional premeasure on scale :
where the infimum is taken over all covers of by nonempty subsets with . Requiring to be nonempty avoids the need to define the diameter of Nothingland, which would be another story. The empty space can be covered by empty family of nonempty subsets. The sum of empty set of numbers is , and so .
Then we define the -dimensional Hausdorff measure:
If in this last infimum we require , the result is . But why make this restriction? The -dimensional pre-measures and measures make sense for all real . It’s just that for nonempty , we are raising some small (or even zero) numbers to negative power, getting something large as a result. Consequently, every nonempty space has for all .
But , from the sum of empty collection of numbers being zero. Hence, for all real , and this leads to .
To have is also convenient because the Hausdorff dimension is superadditive under products: . This inequality was proved for general metric spaces as recently as 1995, by John Howroyd. If we don’t have , then both factors and must be assumed nonempty.
So… should Nothingland have topological dimension and Hausdorff dimension ? But that would violate the inequality which holds for every other separable metric space. In fact, for such spaces the topological dimension is simply the infimum of the Hausdorff dimension over all metrics compatible with the topology.
I am inclined to let the dimension of Nothingland be for every concept of dimension.
(Related to previous post but can be read independently). The triangle inequality, one of the axioms of a metric space, can be visualized by coloring the vertices of a triangle by red and blue.
The inequality says that the sum of monochromatic distances must not exceed the sum of dichromatic distances. That is, for every assignment of the vertices to points in the space, the sum of all red-red and blue-blue distances does not exceed the sum of red-blue distances. An assignment is just a map from the set of vertices to the metric space ; it need not be injective.
But why stop at the triangle? We can take any number of points (vertices), color them in some way, and require the same polygonal inequality:
Already for the square we have two distinct plausible colorings to explore: even red-blue split
and predominantly red square
But it turns out that the second coloring is useless: the inequality it defines fails in every metric space with more than one point. More generally, suppose we have red points and blue ones, and . Pick two distinct points . Assign one red point to and all others to . The sum of monochromatic distances is while the sum of dichromatic distances is , which is strictly less.
So, we are limited to nearly-even colorings: those with . For even numbers of vertices this means even split, while odd numbers should be divided as evenly as possible: like 3+2 for the pentagon.
The inequalities turn out to be related. For every , the -gonal inequality implies the -gonal inequality, because if we assign two opposite-colored vertices to the same point, their contributions cancel out. More interestingly: when is odd, the -gonal inequality implies the -gonal inequality. Indeed, suppose we have points, evenly colored. Add an arbitrary th point. Whether the added point is blue or red, the -gonal inequality holds. Averaging these two inequalities, we see the effect of the added points canceling out.
So, if the -gonal inequality holds for all odd , it holds for all . This property is exactly the hypermetric property from the previous post. Except it was stated there in a different form:
for every finite sequence of points and every choice of integers such that . But if the point is repeated times, we can replace by . Then represent +1 as blue and -1 as red.
The hypermetric inequalities were introduced by John B. Kelly (a student of William Ted Martin) in late 1960s. He showed they are necessary for the space to be embeddable into the space . It would be great if they were also sufficient (and for some classes of spaces they are), but this is not so: a counterexample was given by Patrice Assouad in 1977.
It is also interesting to consider the -gonal inequalities for even only. By repetition of vertices, they are equivalent to requiring
for every finite sequence of points and every choice of integers such that . But of course then we have (1) for rational (just clear the denominators), hence for all real (by approximation), as long as they sum to . So, the requirement amounts to the matrix being negative semidefinite on the subspace . Such metrics are called metrics of negative type.
Their relation to embeddability of the space is well-known: is of negative type if and only if the “snowflake” isometrically embeds into a Hilbert space. In other words, we can “draw” any finite metric space of negative type in a Euclidean space, with the understanding that Euclidean distances represent the square roots of the actual distances. This embedding result is a 1935 theorem of Isaac Schoenberg who is also known for connecting dots naturally (introducing splines).
The Wikipedia article Metric (mathematics) offers a plenty of flavors of metrics, from common to obscure: ultrametric, pseudometric, quasimetric, semimetric, premetric, hemimetric and pseudoquasimetric (I kid you not).
One flavor it does not mention is a hypermetric. This is a metric on a set such that the inequality
holds for every finite sequence of points and every choice of integers such that . The requirement that be integers gives some combinatorial meaning to (1); this is not just some quadratic form being negative semidefinite.
As a warm-up, observe that (1) contains in it the triangle inequality: with and we get . But it appears that (1) says something about “polygons” with more vertices too.
To make (1) worth thinking about, it should be satisfied by some important metric space. Such as the real line , for example. It is not quite obvious that the inequality
holds for all reals and all integers adding up to . It helps to order the numbers: and focus on the contribution of a particular gap to the sum (2). The amount it contributes is multiplied by
because for every integer . This proves (2).
Now that we have one hypermetric space, , other such spaces can be created easily. If is any set and any function, consider , the pullback pseudometric on . By applying (2) to the numbers , we see that satisfies the hypermetric inequality. Since (1) is additive in , we can take any family of functions and add together the corresponding pseudometrics. Or even integrate them against a positive measure: .
For example, the plane is a hypermetric space, because the distance between two points and , besides the familiar form
can also be represented as an integral of the aforementioned pullbacks:
A similar integral representation holds in all dimensions; thus, all Euclidean spaces are hypermetric.
Okay, what is not a hypermetric then? For example, the cube distance induced by the norm is not, in dimensions 3 and higher. Specifically, (1) fails as the five-point inequality with . I’ll call it the pentagram inequality:
It says that for any five points in the space the sum of monochromatic distances does not exceed the sum of all bi-chromatic (red-blue) distances.
The pentagram inequality fails when are the columns of the matrix
(first three columns blue, the last two red). Indeed, the sum of monochromatic distances is while the sum of bichromatic distances is .
If the above example does not look conceptual enough, it’s because I found it via computer search. I don’t have much intuition for the pentagram inequality.
Anyway, the example delivers another proof that taking the maximum of three numbers is hard. More precisely, there is no isometric embedding of with the maximum metric into . Unlike the earlier proof, this one does not assume the embedding is linear.
A good reference for hypermetric inequalities is the book Geometry of cuts and metrics by Deza and Laurent.
My third-grade son came home a few weeks ago with similar homework questions:
How many faces, edges and vertices do the following
Like most mathematicians, my first reaction was that for the latter objects the question would need a precise definition of face, edge and vertex, and isn’t really sensible without such definitions.
But after talking about the problem with numerous people, conducting a kind of social/mathematical experiment, I observed something intriguing. What I observed was that none of my non-mathematical friends and acquaintances had any problem with using an intuitive geometric concept here, and they all agreed completely that the answers should be
cube: 6 faces, 12 edges, 8 vertices
cylinder: 3 faces, 2 edges, 0 vertices
cone: 2 faces, 1 edge, 1 vertex
sphere: 1 face, 0 edges, 0 vertices
Indeed, these were also the answers desired by my son’s teacher (who is a truly outstanding teacher). Meanwhile, all of my mathematical colleagues hemmed and hawed about how we can’t really answer, and what does “face” mean in this context anyway, and so on; most of them wanted ultimately to say that a sphere has infinitely many faces and infinitely many vertices and so on. For the homework, my son wrote an explanation giving the answers above, but also explaining that there was a sense in which some of the answers were infinite, depending on what was meant.
At a party this past weekend full of mathematicians and philosophers, it was a fun game to first ask a mathematician the question, who invariably made various objections and refusals and and said it made no sense and so on, and then the non-mathematical spouse would forthrightly give a completely clear account. There were many friendly disputes about it that evening.
Let’s track down this intuitive geometric concept that non-mathematicians possess. We are given a set and a point , and try to figure out whether is a vertex, a part of an edge, or a part of a face. The answer should depend only on the shape of the set near .
It is natural to say that a vector is tangent to at if going along we stay close to the set. Formally, the condition is . Notice that the limit is one-sided: if is tangent, may or may not be tangent.
The set of all tangent vectors to at is denoted by and is called the tangent cone. It is indeed a cone in the sense of being invariant under scaling. This set contains the zero vector, but need not be a linear space. Let’s say that the rank of point is if contains a linear space of dimension but no linear space of dimension .
Finally, define a rank stratum of as a connected component of the set of all points of rank .
If is the surface of a polyhedron, we get the familiar concepts of vertices (rank 0 strata), edges (rank 1) and faces (rank 2). For each of the homework solids the answer agrees with the opinion of non-mathematical crowd. Take the cone as an example:
At the vertex the tangent cone to the cone is… a cone. It contains no nontrivial linear space, hence the rank is 0. This is indeed a vertex.
Along the edge of the base the tangent cone is the union of two halfplanes:
Here the rank is 1: the tangent cone contains a line, but no planes.
Finally, at every point of smoothness the tangent cone is the tangent plane, so the rank is 2. The set of such points has two connected components, separated by the circular edge.
So much for the cone. As for the circle mentioned in the title, I regrettably find myself in agreement with Travis.
More seriously: the surface of a convex body is a classical example of an Alexandrov space (metric space of curvature bounded below in the triangle comparison sense). Perelman proved that any Alexandrov space can be stratified into topological manifolds. Lacking an ambient vector space, one obtains tangent cones by taking the Gromov-Hausdorff limit of blown-up neighborhoods of . The tangent cone has no linear structure either — it is also a metric space — but it may be isometric to the product of with another metric space. The maximal for which the tangent cone splits off becomes the rank of .
Recently, Colding and Naber showed that the above approach breaks down for spaces which have only Ricci curvature bounds instead of triangle-comparison curvature. More precisely, their examples are metric spaces that arise as a noncollapsed limit of manifolds with a uniform lower Ricci bound. In this setting tangent cones are no longer uniquely determined by , and they show that different cones at the same point may have different ranks.
The definition of a metric space guarantees that if we pick three points from it, we can draw a triangle in the Euclidean plane, with vertices labeled so that the side lengths are equal to the corresponding distances in the metric space. In other words, we can represent any triple of points as vertices of a triangle.
The above paragraph is from Tight spans and Gromov hyperbolicity, but here the similarity ends. Moving on to four points we find that it is possible to draw a quadrilateral with side lengths equal to the corresponding distances
Except for the degenerate case (one length equal to the sum of three others), the quadrilateral is not rigid: one can change the angles while keeping the sidelengths the same.
Since the quadrilateral has one degree of freedom, we cannot hope to have the correct lengths of both diagonals and . One of two diagonals can be made to match the metric space distance, just be drawing two triangles and gluing them together. But this is not so interesting.
There is an interesting class of metric spaces for which one can always draw a Euclidean quadrilateral as above so that neither diagonal is too short (they are allowed to be too long). These are called CAT(0) spaces, and they generalize the concept of a Riemannian manifold of nonpositive sectional curvature (more on this later). Every Euclidean space is CAT(0) for obvious reasons.
For example, if a CAT(0) space contains four points with pairwise distances , , then . Indeed, any Euclidean quadrilateral with these sidelengths is a parallelogram, in which the sum of squares of the diagonals is . (It never pays to draw with self-intersections, because that only makes the “diagonals” shorter).
For a non-parallelogram example, take , , ,and . The diagonal lengths and are allowed by the axioms of a metric space, but not by the CAT(0) condition.
This can be checked using a bunch of cosine formulas:
where the last computation is simpler because is isosceles. Since , the addition law of cosines yields a contradiction.
Let’s see what CAT(0) has to do with curvature. First, a closed curve with intrinsic metric is not a CAT(0) space. Indeed, one can find four points on the curve that are equally spaced at distances , where is the length of the curve. Then the corresponding Euclidean quadrilateral must be a rhombus of sidelength . One of its diagonals will be at most , which is less than required by the intrinsic metric of the curve.
As a corollary, a CAT(0) space does not have closed geodesics. One can object that compact negatively curved manifolds (e.g., double torus) have plenty of closed geodesics. The answer is that to actually characterize nonnegatively curved spaces, one must impose the CAT(0) condition only locally.
The standard definitions of a CAT(0) space require any two points to be connected by a geodesic, and are stated in terms of geodesics. Here is one of them: for any geodesic and for any fixed point the function
is convex. (Here is the square of the distance.)
The condition (1) may look contrived, until one realizes that in a Euclidean space is always an affine function. Thus, the definition says that the distance function in a CAT(0) space is at least as convex as in a Euclidean space. By the way, (1) indeed implies that is a convex function. I leave this as an exercise.
The definition of a metric space guarantees that if we pick three points from it, we can draw a triangle in the Euclidean plane, with vertices labeled , so that the side lengths are equal to the corresponding distances . In other words, we can represent any triple of points as vertices of a triangle.
There is another, perhaps less obvious representation: as vertices of a tripod. Specifically, we can draw a graph of the form shown below and assign length to each edge so that is equal to the length of the shortest path from to , etc.
Indeed, we have the system of linear equations
with a unique solution
The numbers are clearly nonnegative; if a number is zero, the corresponding edge can be contracted to a point. Simple as they are, these formulas have a name: is called the Gromov product of and with respect to , and is denoted .
The more geometric way to arrive at tripod representation is to inscribe a circle in the triangle shown above, and note how the points of tangency divide the sides of the triangle:
Next question: can we represent four points in a similar way? The first approach fails: in general there is no Euclidean quadrilateral in which the sides and diagonals represent the distances between these four points. For example, if and , then any Euclidean representation must place both and in the midpoint between and , which contradicts being nonzero. Let’s try the metric graph approach.
By analogy with the tripod, we might hope at first for something like
but this does not work in general. Indeed, four points determine six distances, and the graph has only five degrees of freedom. We can add one more degree of freedom by thickening the connecting edge to a rectangle:
Does this work? Can we really find the required nonnegative numbers ? Yes! Writing and solving a system of six linear equations is tedious but can be done. A better way is to recognize that we have four tripods here, such as the tripod with vertices and the edge lengths , , . This immediately tells us that . Similarly, , and . The remaining lengths and can now be found directly. But in fact, we can find independently of the other four lengths by considering the perfect matchings between the points . Namely,
From here we get nonnegative and if and only if is the longest matching of vertices (or one of the longest). In other words, we must consider the lengths of matchings before marking on the graph. But once they are marked correctly, the rest is now clear: the numbers and are the amounts by which the longest matching exceeds the other two. In particular, the rectangle collapses into an edge precisely when the two longest matchings have the same length.
What we have here are examples of tight spans of metric spaces: the tripod is the tight span of 3-point space , and the six-edge graph is the 1-skeleton of the tight span of . (The rectangle should have been filled in to form a 2-cell; in general the tight span of points is a polyhedral complex of dimension up to .)
By definition, a metric space is Gromov hyperbolic if there exists a constant such that the tight span of any 4-point subset satisfies ; that is, the rectangle in the middle is not too fat. Informally, this means the space is (contained in) a uniformly thickened metric tree. In terms of distances, the definition says that the lengths of the two longest matchings of differ by at most . Out of several equivalent definitions of Gromov hyperbolicity, this is the most elementary one; it does not require the consideration of geodesics.
However, the real power of Gromov hyperbolicity transpires in the setting of geodesic spaces, where any two points are connected by an isometric image
of a line segment. To begin with, in geodesic spaces it suffices to consider the case when lies on the geodesic from to (otherwise we replace
with a nearby point on the geodesic). The hyperbolicity condition now says that in the geodesic triangle each point on the side is within distance of one of two other sides. Informally, all geodesic triangles in a Gromov hyperbolic space are uniformly thin.
This is indeed the case in the hyperbolic plane . Indeed, a direct computation shows that the area of any geodesic triangle in is less than (it is minus the sum of the angles). On the other hand, the area of a hyperbolic disk of radius grows indefinitely as , since the total area of is infinite. It follows that in there is a uniform upper bound on the radius of a circle that can be inscribed into a triangle; the Gromov hyperbolicity of follows at once.
Even more immediately, is Gromov hyperbolic, with . But is not, as it contains arbitrarily fat triangles (also, the perfect matchings of the points have lengths , contradicting the four-point condition). Similarly, the graph of with metric induced by restriction contains four-point configurations and therefore is not Gromov hyperbolic. Since this graph is bi-Lipschitz equivalent to a line, we see that in general metric spaces Gromov hyperbolicity is not a bi-Lipschitz invariant. How could we expect it to be? bi-Lipschitz maps introduce multiplicative distortion of distances , while Gromov hyperbolicity requires an additive bound.
Yet, if two geodesic metric spaces are bi-Lipschitz equivalent, then either both are Gromov hyperbolic, or neither. One can even replace bi-Lipschitz equivalence with a coarser notion of quasi-isometry, which requires (and need not be surjective; it should only cover some -net in the codomain). The quasi-isometric invariance is what makes it possible to discuss hyperbolicity of finitely generated groups… but that topic will have to wait for another day.