Mapping radii of metric spaces^{∗}

George M. Bergman

April 7, 2011

              This is the final preprint version of a paper which appeared at
      Pacific J. Math., 236 (2008) 223-261.  The published version is accessible to
   subscribers at  http://pjm.math.berkeley.edu/pjm/2008/236-2/pjm-v236-n2-p02-s.pdf .

Dedicated to the memory of David Gale

Abstract

It is known that every closed curve of length ≤ 4 in ℝ^{n} (n > 0) can be surrounded by a sphere of radius 1, and that this is the best bound. Letting S denote the circle of circumference 4, with the arc-length metric, we here express this fact by saying that the mapping radius of S in ℝ^{n} is 1.

Tools are developed for estimating the mapping radius of a metric space X in a metric space Y. In particular, it is shown that for X a bounded metric space, the supremum of the mapping radii of X in all convex subsets of normed metric spaces is equal to the infimum of the sup norms of all convex linear combinations of the functions d(x, −) : X → ℝ (x ∈ X).

Several explicit mapping radii are calculated, and open questions noted.

1 The definition, and three examples.

Definition 1. We will denote by Metr the category whose objects are metric spaces, and whose morphisms are nonexpansive maps. That is, for metric spaces X and Y we let

(1) Metr(X, Y) = {f : X → Y | (∀ x_{0}, x_{1} ∈ X) d(f(x_{0}), f(x_{1})) ≤ d(x_{0}, x_{1})}.

Throughout this note, a map of metric spaces will mean a morphism in Metr.

Given a nonempty subset A of a metric space Y, we define its radius by

(2) rad_{Y} (A) = inf_{y∈Y} sup_{a∈A} d(a, y),

a nonnegative real number or +∞. For metric spaces X and Y, we define the mapping radius of X in Y by

(3) map-rad(X, Y) = sup_{f∈Metr(X,Y)} rad_{Y} (f(X))

= sup_{f∈Metr(X,Y)} inf_{y∈Y} sup_{x∈X} d(f(x), y).

If X is a metric space and Y a class of metric spaces, we likewise define

(4) map-rad(X, Y) = sup_{Y ∈Y} map-rad(X, Y)

= sup_{Y ∈Y, f∈Metr(X,Y)} inf_{y∈Y} sup_{x∈X} d(f(x), y).

(The term “mapping radius” occurs occasionally in complex analysis with an unrelated meaning [15, Def. 7.11].) All vector spaces in this note will be over the field of real numbers unless the contrary is stated.

The result stated in the first sentence of the abstract has been discovered many times [5], [6], [18], [19], [25]. (Usually, the length of the closed curve is given as 1 and the radius of the sphere as 1/4, but the scaled-up version will be more convenient here.) Let us obtain it in somewhat greater generality.

∗2000 Mathematics Subject Classifications. Primary: 54E40. Secondary: 46B20, 46E15, 52A40.

Keywords: nonexpansive map between metric spaces, maximum radius of image, convex subset of a normed vector space.

Any updates, errata, related references etc., learned of after publication will be noted at http://math.berkeley.edu/ ∼ gbergman/papers/ .

Lemma 2. Let S denote the circle of circumference 4, with the arc-length metric. Then for any nonzero normed vector space V, we have map-rad(S, V) = 1.

Proof. In V, any 1-dimensional subspace U is isometric to the real line ℝ, and we can map S into ℝ, and hence into U, by “folding it flat”, getting for image an interval of length 2. Since this interval has points at distance 2 apart, its radius in V cannot be less than 1, so map-rad(S, V) ≥ 1.

For the reverse inequality, consider any map f : S → V. We wish to find a point y ∈ V having distance ≤ 1 from every point of f(S). Let p and q be any two antipodal points of S, and let

y = (f(p) + f(q))/2.

Every point x ∈ S lies on a length-2 arc between p and q in S, hence d(p, x) + d(q, x) = 2, hence d(f(p), f(x)) + d(f(q), f(x)) ≤ 2, i.e., (d(f(p), f(x)) + d(f(q), f(x)))/2 ≤ 1, so d((f(p) + f(q))/2, f(x)) ≤ 1, as claimed.

Let us make explicit the argument used at the very last step above. It is the c_{1} = c_{2} = 1/2 case of

(5) If c_{1}, …, c_{n} are nonnegative real numbers summing to 1, and v_{1}, …, v_{n} are elements of a normed vector space V, then for all w ∈ V, d(∑ c_{i} v_{i}, w) ≤ ∑ c_{i} d(v_{i}, w).

This can be seen by writing the left-hand side as ||(∑ c_{i} v_{i}) − w|| = || ∑ c_{i} (v_{i} − w)|| ≤ ∑ ||c_{i} (v_{i} − w)|| = ∑ c_{i} d(v_{i}, w).

Consider next the union X of two circles S_{0} and S_{1}, each of circumference 4, intersecting in a pair of points antipodal in each (e.g., take for S_{0} and S_{1} any two distinct great circles on a sphere of circumference 4), again with the arc-length metric. We can show that this X also has mapping radius ≤ 1 in V by the same argument as before, except that where we previously used an arbitrary pair of antipodal points, we are now forced to use precisely the pair at which our circles intersect. We are not so restricted in the example showing that radius 1 can actually be achieved – we can stretch one circle taut between any two antipodal points, and for most choices of those points, we have a great deal of freedom as to what to do with the other circle. In any case, we have

Lemma 3. Let X be the union of two circles S_{0} and S_{1}, each of circumference 4, intersecting in a pair of points antipodal in each, with the arc-length metric. Then for any nonzero normed vector space V, we have map-rad(X, V) = 1.

We could apply the same method to any number of circles joined at a common pair of antipodal points; but let us move in a different direction. Again picturing S_{0} and S_{1} as great circles on a sphere of circumference 4 in Euclidean 3-space, assume they meet at right angles, and call their points of intersection the north and south poles. Let us bring in a third circle, S_{2}, the equator, and let X = S_{0} ∪ S_{1} ∪ S_{2}, again with the arc length metric.

We no longer have a pair of antipodal points belonging to all three circles; rather, we have three pairs of points, S_{1} ∩ S_{2} = {p_{0}, q_{0}}, S_{2} ∩ S_{0} = {p_{1}, q_{1}}, and S_{0} ∩ S_{1} = {p_{2}, q_{2}}. Now given a normed vector space V and a map f : X → V in Metr, suppose we let

(6) y = (f(p_{0}) + f(q_{0}) + f(p_{1}) + f(q_{1}) + f(p_{2}) + f(q_{2}))/6.

What can we conclude about d(y, f(x)) for x ∈ X?

Say x ∈ S_{2}. Since both {p_{0}, q_{0}}, and {p_{1}, q_{1}} are pairs of antipodal points of S_{2}, we have d(p_{0}, x) + d(q_{0}, x) = d(p_{1}, x) + d(q_{1}, x) = 2. The same will not be true of d(p_{2}, x) and d(q_{2}, x). To determine how large these can get, let us take x ∈ S_{2} as far as possible (under our arclength metric) from the intersections of S_{2} with our two circles through the poles p_{2} and q_{2}. This happens when x is at the midpoint of any of the quadrants into which p_{0}, q_{0}, p_{1} and q_{1} divide S_{2}; in this situation, d(p_{2}, x) = d(q_{2}, x) = 3/2. (Each quadrant has arc-length 1, and one has to go a quadrant and a half to get from p_{2} or q_{2} to x.) We see, in fact, that for any x ∈ S_{2} we have d(p_{2}, x) = d(q_{2}, x) ≤ 3/2, hence d(p_{2}, x) + d(q_{2}, x) ≤ 3. Now applying any map f : X → V, and invoking (5) with all c_{i} = 1/6, we see that for y as in (6) we have d(y, f(x)) ≤ (2 + 2 + 3)/6 = 7/6. We have proved this for x ∈ S_{2}; by symmetry, it is also true for x lying on S_{0} or S_{1}. This allows us to conclude, not that map-rad(X, V) = 1 as in the preceding two cases, but that (7) map-rad(X, V) ≤ 7/6.

And in fact, there do exist maps f : X → V with rad_{V} (f(X)) > 1. To describe such a map, note that X can be identified with the 1-skeleton of a regular octahedron of edge 1. In the next few paragraphs, let us put aside our picture of X in terms of great circles on a sphere, and replace it with this (straight-edged) octahedral skeleton.

If we look at our octahedron in Euclidean 3-space from a direction perpendicular to one of its faces, we see that face and the opposite one as overlapping, oppositely oriented equilateral triangles, with vertices joined by the remaining 6 edges, which look like a regular hexagon. Now suppose we regard these two opposite triangular faces as made of stiff wire, and the other 6 edges as made of string. Then if we bring the planes of the two wire triangles closer to one another, the string edges will loosen. Suppose, however, that we rotate the top triangle clockwise as they approach one another, so that three of those strings are kept taut, while the other three become still looser. When the planes of our wire triangles meet, those wire triangles will coincide, and the three taut string edges will fall together with the three edges of that triangle, while the three loose ones become loops, hanging from the three vertices. Let us lock the two wire triangles together, and pull the three loops taut, radially away from the center of symmetry of the triangle.

What we then have is the image of a certain map f in Metr from our octahedral skeleton X into a plane, which we can identify with ℝ^{2}. We see that rad_{ℝ^{2}}(f(X)) will be the distance from the center of symmetry of our figure to each of the three points to which the drawn-out loops are stretched; i.e., the sum of the distance from the center of symmetry to each vertex of the triangle, and the length of the stretched loop attached thereto. The former distance is two thirds of the altitude of the triangle, (2/3)(\sqrt{3}/2) = 1/\sqrt{3} , and the latter length is 1/2 (since the loop doubles back), so

(8) rad_{ℝ^{2}}(f(X)) = 1/\sqrt{3} + 1/2. Hence, map-rad(X, ℝ^{2}) ≥ 1/\sqrt{3} + 1/2 > 1.

This shows that our three-circle space does indeed behave differently from the preceding one- and twocircle examples.

However 1/\sqrt{3} + 1/2 ≈ 1.0773, which falls well short of the upper bound 7/6 ≈ 1.1667 of (7).

We can overcome this deficiency by using a different norm on ℝ^{2}. Let V be ℝ^{2} with the norm whose unit disc is the region enclosed by a regular hexagon H of unit side. Note that the 6 sides of H are parallel to the 6 radii joining 0 to the vertices of H, hence these sides have length 1 in the new metric, just as in the Euclidean metric, and indeed, any line segment in one of those directions will have the same length in both metrics. Now let us map X, still pictured as the 1-skeleton of a regular octahedron of side 1 in Euclidean 3-space, into V so that, as before, two opposite triangles are embedded isometrically (now under the metric of V), and made to fall together with each other and with three of the other edges, while the remaining three edges form loops that are stretched radially outward as far as they will go. Let us moreover take the sides of our image-triangle to be parallel to three sides of H.

The map X → ℝ^{2} that does this is almost the same one as before. The 9 edges that end up parallel to edges of H are mapped exactly as before, since distances in those directions are the same in the two metrics. The three folded loops end up set-theoretically smaller than before, since the new metric is greater in their direction than is the Euclidean metric, and they go out a distance 1/2 in the new metric before turning back; but they still contribute the value 1/2 to the calculation of the radius of our image of X. The significant change in that calculation concerns the distance from the center of our triangle to its three vertices. Looking at our triangle as a translate of one of the 6 equilateral triangles into which H is decomposed by its radii, we see that the altitude of that triangle is equal to its side in this metric (since the midpoint of a side of H has the same distance, 1, from the origin as a vertex of H does). Hence the distance from the center to a vertex is 2/3. Adding to this the distance 1/2 from that vertex to the end of the loop attached to it, we get 2/3 + 1/2 = 7/6. Assuming that the center of our triangle is indeed the minimizing point defining the radius (i.e., is a value of y that yields the infimum (2); we will verify this in Lemma 5), this achieves the upper bound (7). Summarizing, and making a few supplementary observations, we have

Lemma 4. Let X be the 1-skeleton of a regular octahedron of side 1, under the arc-length metric. Then for any nonzero normed vector space V,

(9) 1 ≤ map-rad(X, V) ≤ 7/6.

The exact value of map-rad(X, V) is 1 if V is 1-dimensional, is ≥ 1/\sqrt{3} + 1/2 if V is ℝ^{n} (n ≥ 2) under the Euclidean norm, and is 7/6 if V is ℝ^{2} under the norm having for unit circle a regular hexagon.

Proof. The lower bound 1 in (9) is gotten as in the last full sentence before Lemma 3, by regarding X as S_{0} ∪ S_{1} ∪ S_{2}, straightening out one of these circles to cover a segment of length 2 in a 1-dimensional subspace of V, and letting the other two circles collapse into that line in any way. (Or for a construction that relies less on geometric intuition, pick any p ∈ S_{0}, map X into ℝ by the function d(p, −), note that this map sends p and the point antipodal to p on S_{0} to 0 and 2, respectively, and embed ℝ in V.) As before, such an image of X has points 2 units apart, and so has radius ≥ 1 in V by the triangle inequality. The upper bound 7/6 was obtained in (7).

To see that when V itself is 1-dimensional, the value 1 is not exceeded, note that the distance between any two points of X is ≤ 2. Hence the image of X under any map into such a V is a segment of length ≤ 2, hence of radius ≤ 1.

The lower bounds 1/\sqrt{3} + 1/2 and 7/6 for V = ℝ^{2} with the two indicated norms were obtained above by explicit mappings.

Let us now justify the assumption we made just before the statement of the above lemma, about the center from which we computed the radius.

Lemma 5. Let V be a normed vector space, A a nonempty subset of V, and G a finite group of isometries of V which carry A to itself. Then

(10) rad_{V} (A) = inf_{y∈V^{G}} sup_{a∈A} d(a, y),

where V^{G} is the fixed-point set of G.

In particular, if V^{G} is a singleton {v_{0}}, then

(11) rad_{V} (A) = sup_{a∈A} d(a, v_{0}).

Proof. Given v ∈ V, let

(12) y = |G|^{−1} ∑_{g∈G} gv,

and note that this point lies in V^{G}, and that for any a ∈ A,

(13) d(a, y) = d(a, |G|^{−1} ∑_{g∈G} gv) ≤ ∑_{g∈G} |G|^{−1}d(a, gv) = |G|^{−1} ∑_{g∈G} d(g^{−1}a, v)

≤ |G|^{−1} ∑_{g∈G} sup_{b∈A} d(b, v) = sup_{b∈A} d(b, v).

Here the first inequality holds by (5) and the second by considering b = g^{−1}a. Hence for y ∈ V^{G} defined by (12), sup_{a∈A} d(a, y) ≤ sup_{a∈A} d(a, v), from which (10) follows. The final assertion is a special case.

For V = ℝ^{2} with a regular hexagon as unit circle, the group G generated by a rotation by 2π/3 about any point is an isometry of V, and if we take that point to be the center of symmetry of the set f(X) we were looking at above, G preserves f(X) and has that center of symmetry as unique fixed point; so the above lemma justifies our description of the radius of f(X) in terms of distance from that point. In the earlier computation using the Euclidean metric on ℝ^{2}, we “saw” that the radius was measured from the center of symmetry; this is now likewise justified by Lemma 5.

Lemma 4 leaves open

Question 6. For V = ℝ^{2} under the Euclidean norm, and X the 1-skeleton of a regular octahedron of side 1, where does map-rad(X, V) lie within [1/\sqrt{3} + 1/2, 7/6] ?

For V = ℝ^{n}, again with the Euclidean norm, but n > 2, is the answer the same?

Having whetted our appetite with this example, let us prove some general results.

2 General properties of mapping radii.

Lemma 7. Let X, X′, Y, Y′ be nonempty metric spaces, and Y and Y′ classes of such metric spaces.

(i) If there exists a surjective map h : X → X′ (or more generally, a map X → X′ with dense image) in Metr, then map-rad(X′, Y) ≤ map-rad(X, Y).

(ii) If Y′ ⊆ Y, then for any nonempty subset A of Y′ we have rad_{Y′}(A) ≥ rad_{Y} (A). Here equality will hold if Y′ is a retract of Y; i.e., if the inclusion of Y′ in Y has a left inverse in Metr.

Hence if Y′ is a retract of Y, then map-rad(X, Y′) ≤ map-rad(X, Y). In particular, this is true if Y is a normed vector space (or more generally, a convex subset of such a space) and Y′ the fixed subspace (respectively, subset) of a finite group G of affine isometries of Y.

(iii) If Y′ ⊆ Y, then map-rad(X, Y′) ≤ map-rad(X, Y).

(iv) In contrast to (i) and (ii), for X′ ⊆ X, either of the numbers map-rad(X′, Y) and map-rad(X, Y) can be greater than the other, and if Y′ ⊆ Y, or if Y′ is a surjective image of Y in Metr, either of the numbers map-rad(X, Y′) and map-rad(X, Y) can be greater than the other.

Proof. (i) Suppose h : X → X′ has dense image. Then for any f : X′ → Y, fh(X) is dense in f(X′), hence rad_{Y} (fh(X)) = rad_{Y} (f(X′)), so the terms of the supremum defining map-rad(X, Y) include all the terms of the supremum defining map-rad(X′, Y), from which the asserted inequality follows.

(ii) The terms of the infimum defining rad_{Y} (A) include the terms of the infimum defining rad_{Y′}(A), giving the first inequality.

If there exists a retraction e of Y onto Y′, then for every y ∈ Y and a ∈ A we have d(a, e(y)) ≤ d(a, y), since e is nonexpansive and fixes points of A. Hence sup_{a∈A} d(a, e(y)) ≤ sup_{a∈A} d(a, y), and taking the infimum of this over y ∈ Y, we get rad_{Y′}(A) ≤ rad_{Y} (A). This and the previous inequality give the asserted equality. Since Metr(X, Y′) ⊆ Metr(X, Y), we also get map-rad(X, Y′) ≤ map-rad(X, Y), as claimed.

If Y is a convex subset of a normed vector space, and Y′ the fixed set of a finite group G as in the final assertion, note that the function e(v) = |G|^{−1} ∑_{g∈G} gv used in the proof of Lemma 5 is nonexpansive:

d(e(v), e(w)) = ||e(v) − e(w)|| = ||e(v − w)|| ≤ ||v − w|| = d(v, w),

and is a retraction of Y onto Y^{G}.

(iii) This is again a case of suprema of a smaller and a larger set of real numbers.

(iv) The assertion for X′ ⊆ X can be seen from the following mapping radii, where subsets of ℝ are given the induced metric:

map-rad({0}, {0, 2}) = 0, map-rad({0, 2}, {0, 2}) = 2, map-rad({0, 1, 2}, {0, 2}) = 0.

The assertion for Y′ ⊆ Y is shown by the observations

map-rad({0, 2}, {0}) = 0, map-rad({0, 2}, {0, 2}) = 2, map-rad({0, 2}, {0, 1, 2}) = 1.

Finally, to get the case where Y′ is a surjective image of Y, note that we have surjections {0, 3} → {0, 2} → {0, 1} in Metr, and that

map-rad({0, 2}, {0, 3}) = 0, map-rad({0, 2}, {0, 2}) = 2, map-rad({0, 2}, {0, 1}) = 1.

(With a bit more work, one can construct sets X, Y_{0}, Y_{1}, Y_{2} ⊆ ℝ such that each Y_{i+1} is both a subset and a surjective image of Y_{i}, and such that map-rad(X, Y_{0}) < map-rad(X, Y_{1}) > map-rad(X, Y_{2}).)

To state consequences of the above results, let us fix some notation.

Definition 8. For n ≥ 0, n-dimensional Euclidean space, i.e., ℝ^{n} with the Euclidean norm, will be denoted 𝔼^{n}. The class of all Euclidean spaces, {𝔼^{n} | n ≥ 0}, will be denoted Euc.

The class of all normed vector spaces, regarded as metric spaces, will be denoted NmV. The class of all convex subsets of normed vector spaces, regarded as metric spaces, will be denoted Conv.

The diameter of a metric space X will be defined by diam(X) = sup_{x,y∈X} d(x, y).

Corollary 9. If X is a nonempty metric space, then (14) map-rad(X, 𝔼^{1}) ≤ map-rad(X, 𝔼^{2}) ≤ … ≤ map-rad(X, 𝔼^{n}) ≤ …,

with supremum map-rad(X, Euc). Further,

(15) diam(X)/2 = map-rad(X, 𝔼^{1}) ≤ map-rad(X, Euc) ≤ map-rad(X, NmV)

≤ map-rad(X, Conv) ≤ map-rad(X, Metr) = rad_{X}(X) ≤ diam(X).

Proof. Since 𝔼^{n} is the fixed subspace of a reflection of 𝔼^{n+1}, the final assertion of Lemma 7(ii) gives (14). (We could have put “0 = map-rad(X, 𝔼^{0}) ≤” at the left end of (14); but this would complicate some references we will want to make to (14) later.) By definition, map-rad(X, Euc) is the supremum of these values.

To see the initial equality of (15), note on the one hand that under any nonexpansive map f : X → 𝔼^{1}, the images of any two points of X are ≤ diam(X) apart, hence f(X) must lie in an interval of length ≤ diam(X), and any interval in 𝔼^{1} has radius half its length, so map-rad(X, 𝔼^{1}) ≤ diam(X)/2. On the other hand, for x, y ∈ X, the function d(x, −) : X → 𝔼^{1} is nonexpansive, and the images of x and y under this map are d(x, y) apart, whence the radius of f(X) is at least half this value. Taking the supremum over all x and y, we get map-rad(X, 𝔼^{1}) ≥ diam(X)/2.

The next four steps, inequalities among mapping radii, are instances of Lemma 7(iii). In the equality following these, the direction “≤” simply says that nonexpansive maps are radius-nonincreasing, while “≥” holds because one of the maps in the supremum defining map-rad(X, Metr) is the identity map of X. The final inequality is immediate.

We note in passing some cases where these mapping radii are easy to evaluate.

Corollary 10. If a metric space X satisfies rad_{X}(X) = diam(X)/2, then all terms of (15) through rad_{X}(X) are equal (and hence also equal to all terms of (14)).

In particular, this is true whenever (i) X is a finite tree, with edges of arbitrary positive lengths, under the arc-length metric, or (ii) X has an isometry ρ with a fixed point 0 such that for every x ∈ X, d(x, ρ(x)) = 2 d(x, 0).

Proof. The first sentence is clear from (15). To get the two classes of examples, it suffices to show in each case that rad_{X}(X) ≤ diam(X)/2, since (15) gives the reverse inequality.

In case (i), X is compact, so we may choose x, y ∈ X with d(x, y) = diam(X). The unique non-self-intersecting path between x and y is isometric to a closed interval, and so has a midpoint p, satisfying d(x, p) = d(y, p) = diam(X)/2; it now suffices to show that d(z, p) ≤ diam(X)/2 for all z ∈ X. Consider the unique non-self-intersecting path from p to z. Because X is a tree, that path out of p cannot have nontrivial intersection with both the path from p to x and the path from p to y; assume it meets the latter only in p. Then the unique non-self-intersecting path from z to y is the union of the path from z to p and the path from p to y, and we know that it has length ≤ diam(X), so subtracting off diam(X)/2, the length of the path from p to y, we conclude that the length of the path from z to p is ≤ diam(X)/2, as required.

In case (ii), we have rad_{X}(X) ≤ sup_{x∈X} d(x, 0) = sup_{x∈X} d(x, ρ(x))/2 ≤ diam(X)/2.

Examples falling under case (ii) above include all centrally symmetric subsets of normed vector spaces containing 0, under the induced metric, and a hemisphere under the geodesic metric.

A less trivial result, now. Recall that in proving the upper bounds on the mapping radii of Lemmas 2, 3 and 4, we in effect chose formal weighted combinations of points of X, and used these to specify convex linear combinations of points of f(X) ⊆ V. We abstract this technique below. In the statement of the theorem, as a convenient way to express formal weighted combinations of points of X, we use probability measures on X with finite support. (Recall that a probability measure on X is a nonnegative-valued measure μ such that μ(X) = 1, and that μ is said to have support in a set X_{0} if it is zero on X − X_{0}. Apologies for the double use of “d” below, for the distance function of the metric space and the “d” of integration.)

Theorem 11. Let X be a nonempty metric space. Then

(16) map-rad(X, Conv) = inf_{μ} sup_{x∈X} ∫_{z∈X} d(x, z) dμ(z), where the infimum is over all probability measures μ on X with finite support.

Proof. We first prove “≤”, imitating the argument of Lemmas 2, 3 and 4. We must show, for any nonexpansive map f : X → C, where C is a convex subset of a normed vector-space V, and any probability measure μ on X with finite support, that

(17) rad_{C}(f(X)) ≤ sup_{x∈X} ∫_{z∈X} d(x, z) dμ(z).

For any point x of X, let μ_{x} denote the probability measure on X with singleton support {x}. Since the μ of (17) is a probability measure with finite support, it has the form c_{1} μ_{x_{1}} + ⋯ + c_{n} μ_{x_{n}}, where x_{1}, …, x_{n} are points of X, and c_{1}, …, c_{n} are nonnegative real numbers summing to 1. The point y = ∑ c_{i} f(x_{i}) lies in C, so by definition of the radius, the left-hand side of (17) is ≤ sup_{x∈X} d(y, f(x)) = sup_{x∈X} d(∑ c_{i} f(x_{i}), f(x)), which by (5) is ≤ sup_{x∈X} ∑_{i} c_{i} d(f(x_{i}), f(x)), which, because f is nonexpansive, is ≤ sup_{x∈X} ∑_{i} c_{i} d(x, x_{i}). The sum in this expression is the integral in (17), giving the desired inequality.

In proving the direction “≥” in (16), we may assume the metric space X is bounded, since otherwise it has infinite diameter, in which case (15) tells us that the left hand side of (16) is infinite. Assuming boundedness, we shall display a particular embedding e of X in a convex subset C of a normed vector space U, such that rad_{C}(e(X)) is greater than or equal to the right-hand side of (16).

Let U be the space of all continuous bounded real-valued functions on X, under the sup norm, let e : X → U take each x ∈ X to the function d(x, −) (this e is easily seen to be nonexpansive) and let C be the convex hull of e(X). Now for x ∈ X, its image e(x) = d(x, −) can be written y ↦ ∫_{z} d(y, z) dμ_{x}(z). Hence an arbitrary u ∈ C, i.e., a convex linear combination of these functions, will have the same form, but with μ_{x} replaced by a convex linear combination μ of the measures μ_{x}, i.e., a general probability measure μ on X with finite support. For such a function u, and any x ∈ X, the distance d(e(x), u) in C is the sup norm of u − e(x), which is at least the value of u − e(x) at x ∈ X, which is u(x) − 0 = ∫_{z} d(x, z) dμ(z). The radius of e(X) in C is thus at least the infimum over all μ of the supremum over all x of this integral, which is the right-hand side of (16).

Recall that when we obtained our bound (7) on the mapping radius of the 1-skeleton of an octahedron, analogy and good luck led us to the formal linear combination of points of X used in (6) (in effect, a probability measure μ), which turned out to give the optimal bound. In general we ask

Question 12. Let X be a finite graph with edges of possibly unequal lengths, under the arc-length metric. Must there be a probability measure μ on X with finite support that realizes the infimum of (16)?

Is there an algorithm for finding such a μ if it exists, or if not, for evaluating (16)?

We cannot expect in general that a measure of the desired sort will have support in the set of vertices of the graph X, as happened in Lemma 4. E.g., if X is isometric to a circle with arc-length metric, one can show that a measure μ realizes the infimum of (16) if and only if it gives equal weight to p and q whenever p and q are antipodal points; so if X is, say, an equilateral polygon with an odd number of vertices, μ cannot be concentrated in the vertices.

A class of examples generalizing our octahedral skeleton, which it would be of interest to examine, are the 1-skeleta of cross polytopes [7].

A situation simpler than that of Question 12 is that of a finite metric space X. Here the determination of the right-hand side of (16) is a problem in linear programming; whether it has an elegant solution I don’t know. The determination of map-rad(X, 𝔼^{n}) for such a space X is, similarly, in principle, a problem in calculus.

In Corollary 10, we saw that the mapping radius is easy to compute for a space that has “a robust center”. Using the preceding theorem, let us show the same for a space with a pair of “robust antipodes”.

Corollary 13. Suppose the metric space X has a pair of points p and q such that

(18) (∀ r ∈ X) d(p, r) + d(r, q) = d(p, q).

Then letting D = d(p, q), we have diam(X) = D, and map-rad(X, Conv) = D/2. Thus, the terms of (15) through map-rad(X, Conv) are all equal to D/2.

In particular, this is true if X is the 1-skeleton of a regular tetrahedron or of a parallelopiped (in particular, of a cube), with the arc-length metric, or is the 0-skeleton of any of the regular polyhedra other than the tetrahedron, with metric induced by the arc-length metric on the 1-skeleton of that polyhedron.

The property (18) is, of course, inherited by any subspace of X containing p and q.

Proof. For any two points r, r′ ∈ X, we have

2 d(r, r′) ≤ (d(r, p)+d(p, r′))+(d(r, q)+d(q, r′)) = (d(p, r)+d(r, q))+(d(p, r′)+d(r′, q)) = 2D,

so d(r, r′) ≤ D, whence diam(X) = D. Now let μ be the probability measure giving weight 1/2 to each of p and q. For this μ, the integral on the right-hand side of (16) has value D/2 for all x, hence the supremum of that integral over x is D/2, hence (16) shows that map-rad(X, Conv) ≤ D/2. Comparing with the first term of (15), we see that all the the terms of (15) through map-rad(X, Conv) (though not, as before, through map-rad(X, Metr)) are equal.

For X the 1-skeleton of a regular tetrahedron, we get (18) on taking for p and q the midpoints of two opposite edges. For X the 1-skeleton of a parallelopiped, we can use any two antipodal points (not necessarily vertices. In picturing this case, it may help to note that X is isometric to the 1-skeleton of a rectangular parallelopiped.) In the 0-skeleton cases, we use any pair of opposite vertices. In each case, the verification of (18) is not hard.

The final sentence is clear.

So, for instance, for the 1-skeleta of the tetrahedron and cube of edge 1, the 6-tuples of terms of (15) (not distinguishing terms shown connected by equals-signs) are (1, 1, 1, 1, 3/2, 2) and (3/2, 3/2, 3/2, 3/2, 3, 3) respectively. (The reason the last two numbers are equal for the cube, but distinct for the tetrahedron, is that for the cube, the function x ↦ sup_{y} d(x, y) is 3 for all x, while for the tetrahedron, it ranges from a maximum value 2 at the midpoints of the edges to a minimum value 3/2 at the vertices. In neither of these cases is the maximum twice the minimum, so neither of them falls under Corollary 10.)

Let us note a curious feature of the construction used in Theorem 11: it has what at first looks like a universal property (part (i) of the next result) but turns out not to be (part (ii)).

Corollary 14 (to proof of Theorem 11). Let X be a bounded metric space, let U be the space of continuous bounded real-valued functions on X under the sup norm (cf. second half of the proof of Theorem 11), and let e : X → U be the map taking each x ∈ X to the function d(x, −).

Now let f : X → V be any map (in Metr) from X into a normed vector space V. Then

(i) For every family of points x_{1}, …, x_{n} ∈ X, every family c_{1}, …, c_{n} of nonnegative real numbers summing to 1, and every x ∈ X, one has

(19) d(f(x), ∑_{i} c_{i} f(x_{i})) ≤ d(e(x), ∑_{i} c_{i} e(x_{i})).

However,

(ii) Given points x_{1}, …, x_{n} ∈ X, and two families of nonnegative real numbers b_{1}, …, b_{n} and c_{1}, …, c_{n}, each summing to 1, it is not necessarily true that

(20) d(∑_{i} b_{i} f(x_{i}), ∑_{i} c_{i} f(x_{i})) ≤ d(∑_{i} b_{i} e(x_{i}), ∑_{i} c_{i} e(x_{i})).

Thus, the convex hull of e(X) need not admit a map (in Metr) to the convex hull of f(X) making a commuting triangle with e and f.

Proof. (i) may be seen by combining the calculations of the last sentence of the proof of the “≤” direction of Theorem 11, which shows that d(f(x), ∑ c_{i} f(x_{i})) ≤ ∑_{i} c_{i} d(x, x_{i}), and the end of the proof of the “≥” direction, which, by evaluating e(x_{i}) and e(x) as elements of the function-space U at the point x, shows that d(e(x), ∑ c_{i} e(x_{i})) ≥ ∑_{i} c_{i} d(x, x_{i}).

To get (ii), let X again be a circle of circumference 4 with arc-length metric, and let x_{0}, x_{1}, x_{2}, x_{3} ∈ X be four points equally spaced around it. Note that for any u ∈ X, we have d(x_{0}, u) + d(x_{2}, u) = 2 = d(x_{1}, u)+d(x_{3}, u). Hence if we choose the b_{i} and c_{i} so that the right-hand-side of (20) is d((e(x_{0})+e(x_{2}))/2, (e(x_{1})+e(x_{3}))/2), we see that this value is 0. On the other hand, if we map X into 𝔼^{1} by f(x) = 1 − min(d(x_{0}, x), 1), then of the f(x_{i}), only f(x_{0}) is nonzero, so the left-hand side is not 0, so (20) fails.

There are, in fact, a different normed vector space U and mapping e : X → U for which the universal property of (20) does hold [23, Theorem 2.2.4]; we examine this construction in an appendix, §6.

3 Some explicit mapping radii.

A classical result of H. E. W. Jung is, in effect, an evaluation of the mapping radius in 𝔼^{n} of a very simple metric space.

Theorem 15 (after Jung [17]). Let D_{∞} denote an infinite metric space in which the distances between distinct points are all 1. (The cardinality does not matter as long as it is infinite.) Then the values of map-rad(D_{∞}, 𝔼^{n}) for n = 0, 1, 2, … are, respectively,

(21) 0 < 1/2 < 1/\sqrt{3} < \sqrt{3/8} < … < \sqrt{n/(2(n + 1))} < ….

Hence, map-rad(D_{∞}, Euc) = 1/\sqrt{2} .

Likewise, for any positive integer m, if we let D_{m} be an m-element metric space with all pairwise distances 1, then for every n ≥ 0,

(22) map-rad(D_{m}, 𝔼^{n}) = \sqrt{r/(2(r + 1))} , where r = min(m−1, n).

Hence, map-rad(D_{m}, Euc) = \sqrt{(m − 1)/(2m)} .

Summary of proof. The main result of [17] is that every subset of 𝔼^{n} of diameter ≤ 1 has radius ≤ \sqrt{n/(2(n + 1))} . This gives map-rad(D_{∞}, 𝔼^{n}) ≤ \sqrt{n/(2(n + 1))} . On the other hand, the n + 1 vertices of the n-simplex of edge 1 in 𝔼^{n} form a subset of radius exactly \sqrt{n/(2(n + 1))} , and clearly D_{∞} can be mapped onto that set, establishing equality. Taking the limit of this increasing sequence as n → ∞, one gets map-rad(D_{∞}, Euc) = 1/\sqrt{2} .

Clearly, the hypothesis m > n works as well as m = ∞ in concluding as above that map-rad(D_{m}, 𝔼^{n}) = \sqrt{n/(2(n + 1))} . For m ≤ n, on the other hand, any image of D_{m} in 𝔼^{n} lies in an affine subspace that can be identified with 𝔼^{m−1}, so in that case we get map-rad(D_{m}, 𝔼^{n}) = map-rad(D_{m}, 𝔼^{m−1}) = \sqrt{(m − 1)/(2m)} . Combining these results, we get (22) and the final conclusion.

The inequalities (21) show that each step of (14) can be strict. What about the steps of (15)? If we identify terms connected by equal-signs, then (15) lists six possibly distinct values, connected by five ≤-signs. Three of these ≤-signs are shown strict by the 3-point metric space D_{3} of the above theorem, for which, I claim, the 6-tuple of values is (1/2, 1/\sqrt{3} , 2/3, 2/3, 1, 1). The first of these values, and the last two, are clear, and the second comes from the above theorem (line after (22)). To evaluate the remaining two values, map-rad(D_{3}, NmV) and map-rad(D_{3}, Conv), consider the embedding e : D_{3} → U as in the last paragraph of the proof of Theorem 11. The space U used there can in this case be described as ℝ^{3} under the sup norm; let C be the convex hull in U of

(23) e(D_{3}) = {(0, 1, 1), (1, 0, 1), (1, 1, 0)}.

Then Lemma 7(ii) (in particular, the final sentence) tells us that rad_{C}(e(D_{3})) is the common distance of the three points of e(D_{3}) from the unique point of C invariant under cyclic permutation of the coordinates, namely (2/3, 2/3, 2/3). This common distance is 2/3 (since each member of e(D_{3}) has a zero coordinate), so rad_{C}(e(D_{3})) = 2/3, and by Theorem 11, this is map-rad(D_{3}, Conv). Since map-rad(D_{3}, NmV) ≤ map-rad(D_{3}, Conv), to show that map-rad(D_{3}, NmV) is also 2/3 it will suffice to obtain a nonexpansive map f of D_{3} into a vector space V such that rad_{V} (f(D_{3})) = 2/3. This may be done by using the same mapping as above, but translated by (−2/3, −2/3, −2/3), so that the affine span of its image becomes a vector subspace of ℝ^{3}, which, with its induced norm, we take as our V. The preceding argument now gives rad_{V} (f(D_{3})) = 2/3.

For a space showing strict inequality at the final step of (15), rad_{X}(X) ≤ diam(X), one can use any nontrivial instance of Corollary 10; for instance, the unit interval [0, 1], for which that corollary shows that the 6-tuple in question is (1/2, 1/2, 1/2, 1/2, 1/2, 1).

This leaves the step (24) map-rad(X, NmV) ≤ map-rad(X, Conv).

I thought at first that equality had to hold here: that for a C a convex subset of a normed vector space V and any A ⊆ C (in particular, the image of any map of a metric space into C), one had rad_{V} (A) = rad_{C}(A). However, this is not so: consider the untranslated case (23) of the above D_{3} example, and note that the point (1/2, 1/2, 1/2) ∈ U has distance 1/2 from each point of (23); so rad_{U}(e(D_{3})) ≤ 1/2 < 2/3 = rad_{C}(e(D_{3})).

Nonetheless we have seen that for X = D_{3}, equality holds in (24). Here, however, is an example (which it took attempts spread over many months to find) for which that inequality is strict.

Consider the graph with 7 vertices, x, y_{0}, y_{1}, y_{2}, z_{0}, z_{1}, z_{2}, and 9 edges: a length-1 edge from x to each of the y_{i}, and a length-2 edge from y_{i} to z_{j} whenever i ≠ j; and let X be the vertex-set of this graph, with arc-length metric. Thus, for all i ≠ j we have

(25) d(x, y_{i}) = 1, d(x, z_{i}) = 3, d(y_{i}, y_{j}) = 2,

d(y_{i}, z_{j}) = 2, d(y_{i}, z_{i}) = 4, d(z_{i}, z_{j}) = 4.

Let us first find map-rad(X, Conv), using Theorem 11. We must minimize the supremum in (16) over the convex linear combinations μ of μ_{x}, …, μ_{z_{2}}. By Lemma 5, it suffices to minimize that expression over points invariant under permutations of the subscripts; i.e., over convex linear combinations of

(26) μ_{x}, μ_{y} = (μ_{y_{1}} + μ_{y_{2}} + μ_{y_{3}})/3, μ_{z} = (μ_{z_{1}} + μ_{z_{2}} + μ_{z_{3}})/3.

Writing e_{x}, e_{y}, e_{z} respectively for the functions on X given by the integral in (16) for these three measures μ, we find that

(27) e_{x}(x) = 0, e_{x}(y_{i}) = 1, e_{x}(z_{i}) = 3,

e_{y}(x) = 1, e_{y}(y_{i}) = 4/3, e_{y}(z_{i}) = 8/3,

e_{z}(x) = 3, e_{z}(y_{i}) = 8/3, e_{z}(z_{i}) = 8/3.

Any convex linear combination of these three functions has value ≥ 8/3 at each z_{i}; so every value of the supremum in (16) is at least 8/3. Moreover, taking μ = μ_{y} (or more generally, μ = (1 − t)μ_{y} + tμ_{z} for any t ∈ [0, 5/6]), we see that this value 8/3 is attained; so

(28) map-rad(X, Conv) = 8/3.

The idea of our verification that map-rad(X, NmV) is strictly smaller than (28) will be to use the nonconvex affine combination (3e_{y} − e_{x})/2 of the functions (27), so as to reduce somewhat the highest values of e_{y}, those at the z_{i}, without bringing the values at other points up by too much. But since we don’t have the analog of Theorem 11 for non-convex combinations (and indeed, that analog is not true in general – if it were, then 2e_{y} − e_{x} would lead to a still better result, but it does not), we must calculate by hand rather than calling on such a theorem. So suppose f is a nonexpansive map of X into a normed vector space V, and let

(29) p = (f(y_{0}) + f(y_{1}) + f(y_{2}) − f(x))/2.

We need to bound the distances between p and the points of f(X). In view of the symmetry of (29), it will suffice to bound the distances to f(x), f(y_{0}) and f(z_{0}). We calculate

(30) d(p, f(x)) = || (f(y_{0}) + f(y_{1}) + f(y_{2}) − f(x) − 2f(x))/2 ||

≤ (||f(y_{0}) − f(x)|| + ||f(y_{1}) − f(x)|| + ||f(y_{2}) − f(x)||)/2 ≤ (1 + 1 + 1)/2 = 3/2.

d(p, f(y_{0})) = || (f(y_{0}) + f(y_{1}) + f(y_{2}) − f(x) − 2f(y_{0}))/2 ||

≤ (||f(y_{1}) − f(y_{0})|| + ||f(y_{2}) − f(x)||)/2 ≤ (2 + 1)/2 = 3/2.

d(p, f(z_{0})) = || (f(y_{0}) + f(y_{1}) + f(y_{2}) − f(x) − 2f(z_{0}))/2 ||

≤ (||f(y_{0}) − f(x)|| + ||f(y_{1}) − f(z_{0})|| + ||f(y_{2}) − f(z_{0})||)/2 ≤ (1 + 2 + 2)/2 = 5/2.

Taking the maximum of these values, we get (31) map-rad(X, NmV) ≤ 5/2 < 8/3 = map-rad(X, Conv),

a strict inequality, as claimed.

The above observations suggest the question: Which normed vector spaces V have the property that the radius of every subset X of V is the same whether evaluated in V, or in an arbitrary convex subset of V containing X? This is examined in an appendix, §7.

The example of (23) showed that the radius of a subset of a normed vector space could change when one passed to a larger normed vector space. Let us note a curious consequence.

Lemma 16. Let U be ℝ^{3} under the sup norm, and U_{0} ⊆ U be {(a, b, c) ∈ U | a + b + c = 0}. Then there is no isometric reflection U → U having U_{0} as its fixed subspace. In fact, no finite group of affine isometries of any normed vector space W containing U has U_{0} as its fixed subspace.

Proof. Let W be any normed vector space containing U, and let f : D_{3} → U_{0} be given by f(x) = e(x) − (2/3, 2/3, 2/3), for e as in the paragraph containing (23). The first sentence of Lemma 7(ii) gives rad_{W} (f(D_{3})) ≤ rad_{U}(f(D_{3})), which we saw is < rad_{U_{0}}(f(D_{3})). On the other hand, if W had a finite group G of affine isometries with fixed subspace U_{0}, then Lemma 5 would give rad_{W} (f(D_{3})) = rad_{U_{0}}(f(D_{3})).

Returning to (14) and (15), let us for simplicity reduce the number of independent values by “normalizing” to the case diam(X) = 2, and ask for more detailed information than those inequalities.

Question 17. Let X run over all metric spaces of diameter 2. What can one say about the geometry of the resulting sets of sequences

(32) {(map-rad(X, 𝔼^{1}), map-rad(X, 𝔼^{2}), …, map-rad(X, 𝔼^{n}), …)} ⊆ ℝ^{ℕ},

(33) {(map-rad(X, Euc), map-rad(X, NmV), map-rad(X, Conv), map-rad(X, Metr))} ⊆ ℝ^{4} ?

Can one describe them exactly? Are they convex; or do they become convex on replacing the entries by their logarithms, or under some other natural change of coordinates?

If two successive terms of a member of (32) are equal, is the sequence constant from that point on?

Another family of questions, suggested by Theorem 15, is

Question 18. For n ≥ 2, what can one say about the set of nonnegative real numbers that can be written map-rad(X, 𝔼^{n}) for finite metric spaces X in which all distances are integers?

Are all such real numbers “constructible”, i.e., obtainable from rational numbers by a finite sequence of square roots and ring operations?

Is this set well-ordered for each n? (It has a smallest element 0, and a next-to-smallest element 1/2.) Does this set change if “finite metric spaces X… ” is weakened to “bounded metric spaces X… ”? For m < n, can one assert any inclusion between the sets of mapping radii into 𝔼^{m}, and into 𝔼^{n}? Are

there values that occur as map-rad(X, Euc) for some X, but not as map-rad(X′, 𝔼^{n}) for any X′ and n? (E.g., can 1/\sqrt{2} be written in the latter form?)

We end this section with an observation made in [12] for the spaces 𝔼^{n}, which in fact holds for closed convex subsets of arbitrary finite-dimensional normed spaces.

Lemma 19 (cf. [12, Proposition 29, p.14, and second paragraph of p.46]). If C is a closed convex subset of a normed vector space V of finite dimension n, and A a subset of C with > n elements, then rad_{C}(A) = sup_{A_{0}} rad_{C}(A_{0}), where A_{0} runs over the n+1-element subsets of A.

Proof. “≥” is clear; so it suffices to show that if for some real number r, each A_{0} is contained in a closed ball of radius r centered at a point of C, then so is A. Now for each a ∈ A, the set of v ∈ C such that a lies in the closed ball in C of radius r about v is the closed ball in C of radius r about a, hence a compact convex subset of V. To say that a set A_{0} is contained in some closed ball of radius r centered at a point of C is to say that the intersection of these sets, as a runs over A_{0}, is nonempty. By Helly’s Theorem ([14], [8]), if a family of compact convex subsets of ℝ^{n} has the property that every system of n + 1 members of this family has nonempty intersection, then so does the whole family; which in this case means that all of A is contained in a ball of the indicated sort.

The above lemma does not imply the corresponding statement for mapping radii. For example, let X = {x, y_{0}, y_{1}, y_{2}}, where x has distance 1/2 from each of the y_{i}, and these have distance 1 from each other. The maximum of the mapping radii in 𝔼^{2} of 3-element subsets of X is map-rad({y_{0}, y_{1}, y_{2}}, 𝔼^{2}) = map-rad(D_{3}, 𝔼^{2}) = 1/\sqrt{3}. But map-rad(X, 𝔼^{2}) ≤ rad_{X}(X) = 1/2.

On the other hand, for this example, map-rad(X, 𝔼^{2}) can be described as the infimum over p ∈ X of the supremum of map-rad(X_{0}, 𝔼^{2}) over all 3-element subsets X_{0} of X containing p. So we ask

Question 20. Does there exist, for every positive integer n, a positive integer N and a formula which for every metric space X of ≥ N elements, and every normed vector space V of dimension n, expresses map-rad(X, V), using the operations of suprema and infima, in terms of the numbers map-rad(X_{0}, V), for N-element subsets X_{0} ⊆ X?

4 Realizability of mapping radii.

For a subset A of a metric space Y, let us say that rad_{Y} (A) is realized if the infimum in the definition (2) of that expression is attained, that is, if there exists y ∈ Y such that A is contained in the closed ball of radius rad_{Y} (A) about y.

Likewise, for metric spaces X and Y, let us say that map-rad(X, Y) is realized if the supremum in the definition of that expression is attained; that is, if there exists an f : X → Y such that rad_{Y} (f(X)) = map-rad(X, Y). (This does not presume that rad_{Y} (f(X)) is realized.)

Lemma 21. Let X and Y be nonempty metric spaces.

(i) If Y is compact, then for any subset A ⊆ Y, rad_{Y} (A) is realized.

(ii) If X and Y are both compact, then map-rad(X, Y) is realized.

However

(iii) For X compact and Y bounded and complete, or for X bounded and complete and Y compact, map-rad(X, Y) may fail to be realized.

Proof. (i) follows from the fact that for bounded A, sup_{a∈A} d(a, y) is a continuous function of y, hence assumes a minimum on Y.

To get (ii), we note that Metr(X, Y) is a closed subset of the function space Y^{X}, which is compact because Y is, so Metr(X, Y) is compact in the function topology. We would like to say that the real-valued map on this space given by f ↦ rad_{Y} (f(X)) is continuous, and hence assumes a maximum. For general X, this continuity does not hold, as will follow from the second statement of (iii); but I claim that it holds if X is compact. For given f ∈ Metr(X, Y) and ε > 0, compactness allows us to cover X by finitely many open balls of radius ε/3, say centered at x_{1}, …, x_{n}. Consider the neighborhood of f in Metr(X, Y) given by

U = {g ∈ Metr(X, Y) | d(f(x_{i}), g(x_{i})) < ε/3 (i = 1, …, n)}.

Taking any x ∈ X and y ∈ Y, note that there exists i such that d(x_{i}, x) < ε/3; hence for g ∈ U,

|d(f(x), y) − d(g(x), y)| ≤ d(f(x), g(x)) ≤ d(f(x), f(x_{i})) + d(f(x_{i}), g(x_{i})) + d(g(x_{i}), g(x))
≤ ε/3 + ε/3 + ε/3 = ε.

Thus, the two functions associating to every y ∈ Y the numbers sup_{x∈X} d(f(x), y) and sup_{x∈X} d(g(x), y) differ everywhere by ≤ ε, whence the infima of these functions, rad_{Y} (f(X)) and rad_{Y} (g(X)) differ by ≤ ε, giving continuity of f ↦ rad_{Y} (f(X)), which, as noted above, yields (ii).

(iii) For an example with X but not Y compact, let X = D_{2}, i.e., a space consisting of two points at distance 1 apart, and let Y = {y_{2}, y_{3}, …, y_{n}, … } ∪ {z}, with d(y_{m}, y_{n}) = 1 (m ≠ n) and d(y_{n}, z) = 1 − 1/n. Note that the radius in Y of a point-pair {z, y_{n}} or {y_{m}, y_{n}} with m < n is 1 − 1/n. Now Metr(X, Y) consists of all set-maps X → Y, and it follows from the above calculation that map-rad(X, Y) = sup_{n}(1 − 1/n) = 1, but that this value is not achieved. (If we had not specified that Y should be complete, we could have used the simpler example, X = D_{2}, Y = [0, 1).)

For an example with Y but not X compact, let X = {x_{2}, x_{3}, …, x_{n}, … }, with d(x_{2n}, x_{2n+1}) = 2−1/n, and all other pairs of distinct points having distance 1; and let Y = [0, 2] ⊆ 𝔼^{1}. Note that if a map X → Y is to have radius > 1/2, it must send some pair of points to values differing by > 1, and by our metric on X, these two points must have the forms x_{2n}, x_{2n+1}. Since all other points have distance 1 from these two, the images of all other points must fall within the interval between their images. Hence the image of our map falls within an interval of length ≤ 2 − 1/n for some positive n, i.e., of length < 2, and hence of radius < 1. But such images can have radii arbitrarily close to 1, again giving a mapping radius that is not realized.

Corollary 22. Suppose Y is a metric space in which every closed bounded subset is compact. Then

(i) For every bounded nonempty subset A ⊆ Y, rad_{Y} (A) is realized.

(ii) If the isometry group of Y is transitive, or more generally, if Y has a bounded subset which meets every orbit of that group, then for every compact nonempty metric space X, map-rad(X, Y) is realized.

Proof. (i) Let rad_{Y} (A) = r, choose any a_{0} ∈ A, and let Y′ be the closed ball of any radius r′ > diam(A) ≥ r about a_{0} in Y. By assumption Y′ is compact. We see that A ⊆ Y′, and that every point y ∈ Y with sup_{a∈A} d(a, y) ≤ r′ lies in Y′. Since inf_{y∈Y} sup_{a∈A} d(a, y) = r, the space Y contains points y for which sup_{a∈A} d(a, y) comes arbitrarily close to r; hence it will contain points for which that value is arbitrarily close to r and is ≤ r′. Points with this latter property lie in Y′, whence rad_{Y′}(A) is also equal to r, and applying part (i) of the preceding lemma with Y′ for Y gives the desired conclusion.

(ii) Suppose every orbit of the isometry group of Y meets the closed ball of radius c about y_{0} ∈ Y, and let x_{0} be any point of X. Then every f : X → Y may be adjusted by an isometry of Y (which will preserve the radius of f(X)) so that we get d(f(x_{0}), y_{0}) ≤ c, and after this adjustment, f(X) will lie in the closed ball of radius c + diam(X) about y_{0}. Letting Y′ denote the closed ball of any radius r′ > c + diam(X) about y_{0}, we see as in the proof of (i) that the radii of these image sets f(X) in Y′ will equal their radii within Y, and applying part (ii) of the preceding lemma with Y′ for Y, we get the desired conclusion.

5 Related literature (and one more question).

Lemma 2 above, determining the mapping radius of a circle in a normed vector space V, occurs frequently in the literature (with 𝔼^{3} or 𝔼^{n} for V) as an offshoot of the proof of Fenchel’s Theorem, the statement that the total curvature of a closed curve C in 𝔼^{3} is at least 2π, with equality only when C is planar and convex [9, Satz I]. To prove that theorem, Fenchel noted that this total curvature is the length of the curve in the unit sphere S^{2} traced by the unit tangent vector to C, and that that curve cannot lie wholly in an open hemisphere of S^{2} (nor in a closed hemisphere unless C is planar). He completed the proof by showing [9, Satz I′] that a closed curve of length < 2π (respectively, equal to 2π) in S^{2} must lie in an open hemisphere (respectively, must either lie in an open hemisphere or be a union of two great semicircles). In our language, this says that a circle of circumference < 2π, made a metric space using arc-length, has mapping radius < π/2 in S^{2} and (along with some additional information) that the circle of arc-length exactly 2π has mapping radius π/2.

Subsequent authors [5], [6, Lemma on p.30], [16], [19], [21], [22] gave simpler proofs of Fenchel’s Satz I′ (similar to our proof of Lemma 2), and/or generalized that result from S^{2} to S^{n}, and/or obtained the more precise result that the mapping radius of a circle of length L ≤ 2π in S^{n} is L/4, and/or noted that the same method also gives the analogous result with 𝔼^{n}, or indeed any of a large class of geometric structures, in place of S^{n}.

The last-mentioned generalizations were based on the observation that the concept of the midpoint of a pair of points can be defined, and behaves nicely, in many geometric contexts. I do not know whether more general convex linear combinations, such as we used in (5) and in the proof of Theorem 11, can be defined outside the context of vector spaces so as to behave nicely; hence the emphasis in this note on vector spaces and their convex subsets. A.Weinstein (personal communication) suggests that an approach to “averaging” of points introduced by Cartan and developed further by Weinstein in [24] might serve this function. J.Lott (personal communication) points similarly to the concepts of Hadamard space [2] and Busemann convex space [4].

The results on closed curves of length L in the unit sphere cited above all take L ≤ 2π. If we write S_{L}^{1} for a circle of circumference L with arc-length metric, and S^{n} for the unit n-sphere (of circumference 2π) with geodesic distance as metric, it is clear that the result map-rad(S_{L}^{1}, S^{n}) = L/4 cannot be expected to hold when L > 2π; but it would be interesting to investigate how that mapping radius does behave as a function of L. For all L, map-rad(S_{L}^{1}, S^{n}) < π, since a curve of fixed length cannot come arbitrarily close to every point of S^{n}, and if it misses the open disk of geodesic radius r about a point p, then it is contained in the closed disc of geodesic radius π − r about the antipodal point.

Many of the papers referred to above consider arcs as well as closed curves; i.e., also study map-rad([0, L], S^{n}), and prove that for L ≤ π, this equals L/2. Again, the case of larger L would be of interest. So we ask

Question 23. For fixed n > 1, how does map-rad(S_{L}^{1}, S^{n}) behave for L > 2π, and how does map-rad([0, L], S^{n}) behave for L > π, as functions of L?

For instance, are these two functions piecewise analytic?

It seems likely that there will be ranges of values of L in which different configurations of a closed curve or arc give maximum radius, and that the value of this radius will be an analytic function of L within each such range. (I conjecture that for all L between 2π and a value somewhat greater than 3π, map-rad(S_{L}^{1}, S^{2}) will be realized by a “3-peaked crown”, consisting of 6 arcs of great circles, with midpoints equally spaced along a common equator. For map-rad(S_{L}^{1}, S^{n}) with n > 2, I have no guesses.)

Many papers in this area also consider the smallest “box” – in various senses – into which one can fit all curves, or closed curves, of unit length [5] [13] [20], or all point-sets of unit diameter [10]. These do not translate into statements about our concept of mapping radius for two reasons. First, they deal with arc length in the Euclidean metric, but with “boxes” which, though they could in many cases be considered closed balls in another metric, are not balls in the Euclidean metric; and our formalism of mapping radius does not look at more than one metric on Y at a time. Second, they generally allow rotations as well as translations in fitting the box around the curve, while in looking at radii we only have one closed ball of each radius centered at a given point.

The intuitive interest of Question 23 above arises in part from a special property of the sphere: that a large open or closed ball, i.e., one that falls just short of covering S^{n}, has for complement a small closed or open ball. For spaces Y not having this property, the most natural analogs of those questions might be the corresponding questions about “mapping co-radii”, given by the definitions

(34) corad_{Y} (A) = sup_{y∈Y} inf_{a∈A} d(a, y) (A ⊆ Y),

(35) map-corad(X, Y) = inf_{f∈Metr(X,Y)} corad_{Y} (f(X))

= inf_{f∈Metr(X,Y)} sup_{y∈Y} inf_{x∈X} d(f(x), y)

(cf. (2) and (3)). So, for instance, one might ask about the values of map-corad([0, L], B^{2}) for B^{2} the closed unit disc in ℝ^{2}, as a function of L.

(I’m not sure that “co-radius” is a good choice of term: one could argue that that term would more appropriately apply either to rad_{Y} (Y −A), or to what in the notation of (34) would be written corad_{Y} (Y − A). So the above names are just suggestions, which others may choose to revise.)

6 Appendix: The Arens-Eells space of X.

At the end of §2, I mentioned that every metric space X admits an embedding in a normed vector space U having the universal property that Corollary 14(ii) showed that the embedding we were considering there did not have. The construction in question was introduced by Arens and Eells [1], and its universal property noted by Weaver [23, Theorem 2.2.4], who calls it the Arens-Eells space of X. Weaver is there most interested in this space as a pre-dual to the Banach space of Lipschitz functions on X. I will sketch below a motivation for the same object in terms of the universal property. My description will also make a couple of technical choices different from those of [1] and [23].

Essentially the same construction arises in mathematical economics, in the study of the “transportation problem” [11], cf. [23, §2.3]. What to us will be the norm of an element of the Arens-Eells space appears there as the minimum cost of transporting goods from a given set of sources to a given set of markets.

To lead up to the construction, let a metric space X be given, consider any map (as always, nonexpansive) f of X into a normed vector space V, and let us ask, as a sample question: If we know the distances among four points x_{1}, x_{2}, x_{3}, x_{4} ∈ X, what can we say about ||f(x_{1}) + f(x_{2}) − f(x_{3}) − f(x_{4})||?

Clearly, this will be bounded above by ||f(x_{1})−f(x_{3})|| + ||f(x_{2})−f(x_{4})|| ≤ d(x_{1}, x_{3}) + d(x_{2}, x_{4}). The other way of pairing terms of opposite sign similarly gives the bound d(x_{1}, x_{4}) + d(x_{2}, x_{3}). Hence

(36) ||f(x_{1}) + f(x_{2}) − f(x_{3}) − f(x_{4})|| ≤ min(d(x_{1}, x_{3}) + d(x_{2}, x_{4}), d(x_{1}, x_{4}) + d(x_{2}, x_{3})).

For a similar, but slightly less straightforward case, suppose we want to bound ||3f(x_{1}) + f(x_{2}) − 2f(x_{3}) − 2f(x_{4})||. We cannot, as before, pair off terms whose coefficients in this expression happen to be the same except for sign. There are, however, ways of breaking up that expression as a linear combination of differences; and a little experimentation shows that all ways of doing so are convex combinations of two extreme decompositions. These two cases lead to the bound

(37) ||3f(x_{1}) + f(x_{2}) − 2f(x_{3}) − 2f(x_{4})|| ≤

min(2d(x_{1}, x_{3})+d(x_{1}, x_{4})+d(x_{2}, x_{4}), 2d(x_{1}, x_{4})+d(x_{1}, x_{3})+d(x_{2}, x_{3})).

We will not stop here to prove that (36) and (37) are best bounds. Let us simply observe that these considerations suggest that the norm of such a linear combination of images of points of X under a universal map e : X → U should be given by an infimum of linear combinations of the numbers d(x, y) (x, y ∈ X) with nonnegative real coefficients, the infimum being taken over all such linear expressions which, when each d(x, y) is replaced by e(x) − e(y), give the required element.

An obvious problem is that the only elements we get in this way are those in which the sum of the coefficients of the members of e(X) is 0. This difficulty is intrinsic in the situation: There will not in fact exist a nonexpansive map of X into a normed vector space having the standard sort of universal mapping property with respect to such maps, because, though the condition of nonexpansivity bounds the distances among images of points of X, it does not bound the distances between such images and 0; so universality would force the images of points of X to have infinite norm.

What we can get, rather, is a set-map e of X into a vector space U, and a norm on the subspace U_{0} of linear combinations of images of points of X with coefficients summing to 0, such that for all x, y ∈ X, ||e(x) − e(y)|| ≤ d(x, y), and which has the universal property that given any nonexpansive map f of X into a normed vector space V, there exists a unique vector-space homomorphism g : U → V which satisfies f = ge, and is nonexpansive on U_{0}. Observe that the norm on U_{0} induces a metric on each coset of that subspace; in particular, on the coset U_{1} of elements in which the sum of all coefficients is 1, which is the affine span of the image of X. The map of X into that coset is nonexpansive, and the asserted universal property of e is easily seen to yield (20), the property that the construction of §2 failed to have.

Weaver’s answer to the same distance-to-0 problem is to use metric spaces with basepoint, and basepointrespecting maps, the basepoint of a vector space being 0. This has the advantage of giving a universal property in the conventional sense, with both U and V in the category of normed vector spaces. However, it requires one to make a possibly unnatural choice of basepoint in X; changes in that choice induce isometries on the universal space, which, though affine, are not linear. The approach I actually find most natural is to regard what I have called U_{1} as a “normed affine space”, that is, a set with a simply transitive group of “translation” maps by elements of a normed vector space, and to note that U_{1} has a genuine universal property in the category of normed affine spaces. However, the development of that concept would be an excessive excursion for this appendix. Still another approach would be to work with “normed” vector spaces where the norm is allowed to take on the value +∞. In any case, it is straightforward to verify that the Arens-Eells space of X as described in [23] and my U_{0} are isometrically isomorphic, so below I will quote results of Weaver’s, tacitly restated for my version of the construction.

The details, now: let U be the vector space of all real-valued (i.e., not necessarily nonnegative) measures μ on X with finite support, and, as before, for each x ∈ X let μ_{x} be the probability measure with support {x}. Thus, {μ_{x} | x ∈ X} is a basis of U. Let U_{0} ⊆ U denote the subspace of measures μ satisfying μ(X) = 0. Let W similarly denote the space of all real-valued measures on X × X with finite support; for each (x, y) ∈ X × X, let ν_{x,y} be the probability measure with support {(x, y)}, and let W_{+} ⊆ W be the cone of nonnegative linear combinations of the ν_{x,y}, i.e., the nonnegative-valued measures on X × X. Finally, let D : W → U be the linear map defined by the condition

(38) D(ν_{x,y}) = μ_{x} − μ_{y} for x, y ∈ X,

which clearly has image U_{0}. We now define the norm of any μ ∈ U_{0} by

(39) ||μ|| = inf_{ν∈W_{+}, D(ν)=μ} ∫_{(x,y)∈X×X} d(x, y) dν .

It is easy to verify that this indeed gives a norm with the desired universal property. The one verification that is not immediately obvious is that it is a norm rather than a pseudonorm; i.e., that it is nonzero for nonzero μ ∈ U_{0}. To get this, one first proves the desired universal property in the wider context of pseudonormed vector spaces, then notes that given any nonzero μ = ∑_{I} a_{i} μ_{x_{i}} ∈ U_{0} (I finite, all a_{i} nonzero), one can find a nonexpansive map f : X → ℝ which is zero at all but one of the x_{i}, say x_{i_{0}}, from which it follows by the universal property that ||μ|| ≥ | ∑ a_{i} f(x_{i})| = |a_{i_{0}} f(x_{i_{0}})| > 0.

Weaver [23, Theorem 2.3.7(b)] shows that the infimum in (39) is always attained, and in fact, by a ν whose “support” in X (the set of points which appear as x or y in terms ν_{x,y} having nonzero coefficient in the expression for ν) coincides with the support of μ (the set of x such that μ_{x} appears with nonzero coefficient in the expression for μ). Our next proposition strengthens this result a bit. For brevity, we will call on Weaver’s result in the proof, but I will sketch afterward how the argument can be made self-contained.

We will use the following notation and terminology. Given ν = ∑_{j∈J} b_{j} ν_{x_{j},y_{j}} ∈ W (where J is a finite set, the pairs (x_{j}, y_{j}) for j ∈ J are distinct, and all b_{j} ≠ 0), let Γ(ν) be the directed graph having for vertices all points of X, and for directed edges the finitely many pairs (x_{j}, y_{j}) (j ∈ J). Let us define the positive support of a directed graph Γ as the set of vertices which are initial points of its edges, and its negative support as the set of vertices which are terminal points. For ν ∈ W, we will call the positive and negative supports of Γ(ν) the positive and negative supports of ν. On the other hand, for μ = ∑_{I} a_{i} μ_{x_{i}} ∈ U_{0}, let us define its positive support to be {x_{i} | a_{i} > 0}, and its negative support to be {x_{i} | a_{i} < 0}. These are clearly disjoint. Note that when ν ∈ W_{+}, the positive support of D(ν) is contained in the positive support of ν, and contains all elements thereof that are not also in the negative support of ν, and that the negative support of D(ν) has the dual properties.

When we speak of a cycle in a directed graph, we shall mean a cycle in the corresponding undirected graph; we shall also understand that in a cycle no vertex is traversed more than once. Note that a cycle of length 1 in Γ(ν) can only arise when a term ν_{x,x} has nonzero coefficient in ν, while a cycle of length 2, i.e., the presence of two edges between x and y, can only occur if ν_{x,y} and ν_{y,x} both have nonzero coefficients. But a cycle of length n > 2 involving a given sequence of vertices may arise in any of 2^{n} ways, depending on the orientations of the edges.

We now prove

Proposition 24 (cf. [11, Theorem 3.3, p.84]). Let μ ∈ U_{0}. Then the infimum of (39) is attained by an element ν ∈ W_{+} (not necessarily unique) whose positive and negative supports coincide respectively with the positive and negative supports of μ, and whose graph Γ(ν) has no cycles.

Proof. As mentioned, Weaver proves the existence of a ν ∈ W_{+} with D(ν) = μ which achieves the infimum (39) and has the same support as μ. Let ν be chosen, first, to have these properties; second, among such elements, to minimize the total number of edges in Γ(ν), and finally, to minimize the sum of the coefficients of all the ν_{x,y} in its expression. This last condition is achievable because the set of elements of W_{+} which are linear combinations of a given finite family of the ν_{x,y}, and for which the coefficients of these elements are all ≤ some constant, is compact; so after finding some ν with D(ν) = μ which achieves the minimum (39), has the same support as μ, and minimizes the number of edges in Γ(ν), we may restrict our search for elements also minimizing the coefficient-sum to the compact set of elements having the preceding properties and having every coefficient less than or equal to the coefficient-sum of the element we have found.

Suppose, now, that Γ(ν) has a cycle. Thus, we may choose distinct vertices p_{1}, …, p_{k}, and for each j ∈ {1, …, k}, a term ν_{p_{j},p_{j+1}} or ν_{p_{j+1},p_{j}} occurring with positive coefficient in ν, where the subscripts j are taken modulo k. (If k > 2 and both ν_{p_{j},p_{j+1}} and ν_{p_{j+1},p_{j}} occur in ν, we choose one of these arbitrarily. If k = 2, we make sure that the terms we choose for j = 1, 2 are distinct, one being ν_{p_{1},p_{2}} and the other ν_{p_{2},p_{1}}.) For each j ∈ {1, …, k} let us now define ν′_{p_{j},p_{j+1}} to be ν_{p_{j},p_{j+1}} if that is the jth term in the list we have chosen, or −ν_{p_{j+1},p_{j}} if the jth term in that list is ν_{p_{j+1},p_{j}}, and let ν′ = ∑_{j} ν′_{p_{j},p_{j+1}} ∈ W. In general, ν′ ∉ W_{+}, but for all λ ∈ ℝ near enough to 0, we have ν + λν′ ∈ W_{+}, since the relevant coefficients in ν are strictly positive. Note that for each j, D(ν′_{p_{j},p_{j+1}}) = μ_{j} − μ_{j+1}, hence D(ν′) = 0, hence D(ν + λν′) = D(ν) = μ.

Clearly, ∫_{(x,y)∈X×X} d(x, y) d(ν+λν′) is an affine function of λ. Hence it must be constant, otherwise, using small λ of appropriate sign, we would get a contradiction to the assumption that ν achieves the minimum of (39); so all the elements ν + λν′ achieve this same minimum. Now some choice of λ will cause λν′ to exactly cancel the smallest among the coefficients of terms ν_{p_{j},p_{j+1}} or ν_{p_{j+1},p_{j}} in our cycle in Γ(ν). Thus, ν + λν′ contradicts the minimality assumption on the number of edges in Γ(ν). This contradiction shows that Γ(ν) has no cycles.

Next, let us compare the positive and negative supports of ν with those of μ. We have chosen ν so that its support, namely the union of its positive and negative supports, coincides with the support of μ; and since μ = D(ν), the positive and negative supports of ν will each contain the corresponding support of μ. So if these inclusions are not both equalities, we must have a vertex p which is both in the positive and the negative support of ν; i.e., such that there is an edge (q, p) of Γ(ν) leading into p, and an edge (p, r) leading out of it. Let ν′ = ν_{q,r} − ν_{q,p} − ν_{p,r}. Like the element denoted by that symbol in the preceding argument, this satisfies D(ν′) = 0. Let us again form ν + λ ν′, this time choosing the value λ > 0 which leads to the cancellation of the smaller of the coefficients of ν_{q,p} and ν_{p,r} in ν, or of both if these coefficients are equal. Since this does not reverse the sign of either of these coefficients, ν + λ ν′ still belongs to W_{+}. Note that ∫_{(x,y)∈X×X} d(x, y) d(ν+λν′) ≤ ∫_{(x,y)∈X×X} d(x, y) dν, since by the triangle inequality, d(q, r) ≤ d(q, p) + d(p, r); so the property of minimizing the latter integral among elements of W_{+} mapped to μ by D has not been lost. Also, Γ(ν + λν′) has dropped at least one edge that belonged to Γ(ν), since at least one coefficient was canceled, and has gained at most one edge, namely (q, r) (if that was not previously present); so the total number of edges has not increased. Finally, when we look at the sum of all the coefficients, we see that the coefficient of ν_{q,r} has increased by λ, while those of ν_{q,p} and ν_{p,r} have both decreased by λ, so there has been a net change of −λ < 0. Thus, we have a contradiction to our choice of ν as minimizing that sum. This completes the proof of the main assertion of the proposition.

Let us verify, finally, the parenthetical comment that the ν of the proposition may not be unique. Let X be a 4-point space {x_{1}, x_{2}, x_{3}, x_{4}} where the distance between every pair of distinct points is 1, and let μ = μ_{x_{1}} + μ_{x_{2}} − μ_{x_{3}} − μ_{x_{4}}. It is not hard to check that in this case, the only elements ν that can possibly satisfy the conditions of the proposition are ν_{x_{1},x_{3}} + ν_{x_{2},x_{4}} and ν_{x_{1},x_{4}} + ν_{x_{2},x_{3}}. Since these give the same value for the integral of (39), d(x_{1}, x_{3}) + d(x_{2}, x_{4}) = 2 = d(x_{1}, x_{4}) + d(x_{2}, x_{3}), each satisfies our conditions.

(Of course, for most choices of metric on this set X, one of these two values is smaller than the other, and we then get a unique ν satisfying the conditions of the proposition.)

To get a self-contained version of the above proof which includes the existence result we cited from [23], one may start by looking at any finite subset X_{0} of X containing the support of μ, verify by compactness as above that the infimum of (39) over elements ν with support contained in X_{0} is achieved, and that the other parameters mentioned above can then be minimized; and then note that any element in the support of ν but not in the support of μ must belong to both the positive and negative supports of ν, a situation excluded by the proof. Letting X_{0} then run over all finite subsets of X containing the support of μ, one sees that the infimum of (39) exists, and is simply the infimum with ν restricted to have support in the support of μ.

We remark that the final condition of the above proposition, that Γ(ν) have no cycles, is not entailed by the other conditions. E.g., returning to X = {x_{1}, x_{2}, x_{3}, x_{4}} with all distances 1, we see that every convex linear combination ν of the two elements that we found, ν_{x_{1},x_{3}} + ν_{x_{2},x_{4}} and ν_{x_{1},x_{4}} + ν_{x_{2},x_{3}}, still minimizes (39), and still has support X; but if ν is a proper convex combination of those two elements, then Γ(ν) = Γ(ν_{x_{1},x_{3}}+ ν_{x_{2},x_{4}}) ∪ Γ(ν_{x_{1},x_{4}}+ ν_{x_{2},x_{3}}), which contains (indeed, is) a cycle.

Let us now show, however, that when, as in the statement of the proposition, Γ(ν) is cycle-free, it uniquely determines ν. Thus, the calculation of the norm (39) reduces in principle to checking finitely many ν.

Lemma 25. Let μ ∈ U_{0}, and let Γ be a directed graph with vertex-set X and without cycles. Then there is at most one ν ∈ W (and so, a fortiori, at most one ν ∈ W_{+}) such that D(ν) = μ and Γ(ν) ⊆ Γ.

To characterize this element ν, consider any edge (x, y) in Γ. Let Γ_{x} (containing x) and Γ_{y} (containing y) be the connected components into which the connected component of Γ containing (x, y) separates when that edge is removed. Then the coefficient in ν of ν_{x,y} is the common value of ∫_{Γ_{x}} dμ and − ∫_{Γ_{y}} dμ, i.e., is both the sum of the coefficients of μ_{z} over z in Γ_{x}, and the negative of the corresponding sum over Γ_{y}.

Proof. We will prove the assertion of the second paragraph, from which that of the first clearly follows.

Writing μ = D(ν), the contributions to the expression ∫_{Γ_{x}} dμ from any term ν_{p,q} such that both p and q lie in Γ_{x} clearly cancel, while terms such that neither p nor q lies in Γ_{x} contribute nothing. This leaves the ν_{x,y} term, which contributes precisely its coefficient, leading to the first description of that coefficient. Likewise, this term contributes the negative of its coefficient to ∫_{Γ_{y}} dμ, yielding the second description.

Corollary 26. Suppose μ ∈ U_{0} is integer-valued, and let ν be an element of W_{+} with the properties that D(ν) = μ, that ν has the same positive and negative supports as μ, and that Γ(ν) has no cycles.

Then for every x ∈ X such that the coefficient of μ_{x} in μ is ±1, the vertex x is a leaf of Γ(ν).

Hence, if μ has the property that the coefficient of every μ_{x} is ±1, then ν is induced, in the obvious way, by a bijection between the positive support of μ and the negative support of μ. Thus, in that case, letting n be the common cardinality of these supports, there are exactly n! such ν ∈ W_{+}.

Proof. Consider any x such that μ_{x} has coefficient +1 in μ. Then x is in the positive support of Γ(ν), but not in the negative support. The latter condition says that ν involves no terms ν_{y,x} (y ∈ X), so +1 is the sum of the coefficients in ν of the terms ν_{x,y} (y ∈ X − {x}). Since ν ∈ W_{+}, these coefficients are nonnegative, and by Lemma 25 they are integers, so as they sum to 1, only one of them can be nonzero, making x a leaf. The same argument, mutatis mutandis, gives the case where the coefficient of μ_{x} is −1.

The assertion of the final paragraph clearly follows, since a directed graph in which every vertex is a leaf corresponds to a bijection between “source” and “sink” vertices.

As sample applications, recall the two computations at the beginning of this section, with which we motivated the construction of our universal embedding e : X → U_{0}. In our present notation, what we were doing was evaluating the norms in U_{0} of elements of the two forms μ_{x_{1}} + μ_{x_{2}} − μ_{x_{3}} − μ_{x_{4}} and 3μ_{x_{1}} + μ_{x_{2}} − 2μ_{x_{3}} − 2μ_{x_{4}}. In the first case, the last paragraph of the above corollary leads to just two graphs, and hence two values of ν one of which must achieve the infimum (39), namely ν_{x_{1},x_{3}} + ν_{x_{2},x_{4}} and ν_{x_{1},x_{4}} + ν_{x_{2},x_{3}}, showing that if f is our universal map e, equality holds in (36), and for general f, (36) is the best bound. (This also establishes the example that we said was “not hard to check” in the next-to-last paragraph of the proof of Proposition 24.)

In the case μ = 3μ_{x_{1}} + μ_{x_{2}} − 2μ_{x_{3}} − 2μ_{x_{4}}, Corollary 26 says that x_{2} is a leaf of Γ(ν). As it lies in the positive support of μ, the vertex it is attached to must lie in the negative support, i.e., must be either x_{3} or x_{4}. In the former case, subtracting ν_{x_{2},x_{3}} from ν will give an element ν′ ∈ W_{+} which is sent by D to 3μ_{x_{1}} − μ_{x_{3}} − 2μ_{x_{4}}. Since this ν′ has only one element, x_{1}, in its positive support, its graph is uniquely determined, giving ν′ = ν_{x_{1},x_{3}} + 2ν_{x_{1},x_{4}}, hence ν = ν_{x_{2},x_{3}} + ν_{x_{1},x_{3}} + 2ν_{x_{1},x_{4}}. The case where x_{2} is attached to x_{4} similarly gives ν = ν_{x_{2},x_{4}} + 2ν_{x_{1},x_{3}} + ν_{x_{1},x_{4}}, and these together show that (37) is a best bound.

I referred earlier to the mathematical economist’s “transportation problem”. There, our d(x, y) corresponds to the cost of transporting a unit quantity of goods from location x to location y; so our definition of ||μ|| describes the minimum cost of transporting goods produced and consumed at locations and in quantities specified by μ.

Incidentally, the first assertion of Corollary 26 does not remain true if we weaken “the coefficient of μ_{x} in μ is ±1” to “the coefficient of μ_{x} has least absolute value among the nonzero coefficients occurring in μ.” For instance, suppose μ has the form 3μ_{x_{1}} − 4μ_{x_{2}} + 2μ_{x_{3}} − 4μ_{x_{4}} + 3μ_{x_{5}}. Then one of the elements of W_{+} satisfying the conditions of Corollary 26 is ν = 3ν_{x_{1},x_{2}} + ν_{x_{3},x_{2}} + ν_{x_{3},x_{4}} + 3ν_{x_{5},x_{4}}. Here Γ(ν) has the form x_{1} → x_{2} ← x_{3} → x_{4} ← x_{5}, so x_{3}, despite having smallest coefficient in μ, is not a leaf.

Proposition 24 sheds some light on our earlier “partial universality” result, Corollary 14(i). Given any convex linear combination of points of our universal image of X, ∑_{I} a_{i} μ_{x_{i}} (a_{i} > 0, ∑ a_{i} = 1), and any point x ∈ X (which for simplicity we will assume is not one of the x_{i}, though the argument can be adjusted to the case where it is), the difference μ_{x} − ∑ a_{i} μ_{x_{i}} is an element of U_{0} with positive support {x} and negative support {x_{i} | i ∈ I}. For this situation, the conditions of Proposition 24 clearly lead to a unique Γ(ν), to wit, the tree whose edges are all pairs (x, x_{i}) (i ∈ I), and hence to the unique choice ν = ∑_{i} a_{i} ν_{x,x_{i}}. Thus, the right-hand side of (39) comes to ∑_{i} a_{i} d(x, x_{i}), which is equal to the right-hand side of (19). In contrast, when one considers the difference between two general convex linear combinations of elements μ_{x}, as in Corollary 14(ii), there may be many directed graphs satisfying the conditions of Proposition 24, so the norm of that difference doesn’t have a simple expression.

The universality of the Arens-Eells space U yields a formula for map-rad(X, NmV) analogous to our description (16) of map-rad(X, Conv); namely,

(40) map-rad(X, NmV) = inf_{μ∈U_{1}} sup_{x∈X} inf_{ν∈W_{+}, D(ν)=μ−μ_{x}} ∫_{y,z∈X} d(y, z) dν(y, z).

But this is cumbersome to use. E.g., the reader might try working through a verification, for the space described by (25), of the statement that the μ implicit in (29), (μ_{y_{0}} + μ_{y_{1}} + μ_{y_{2}} − μ_{x})/2, does indeed lead to the infimum of (40), showing that map-rad(X, NmV) = 5/2, and not a smaller value.

Given an element μ ∈ U_{0}, it would be interesting to look for bounds on the number of distinct graphs Γ(ν) corresponding to elements ν ∈ W_{+} as in the first sentence of Corollary 26. (This is simply a function of the coefficients occurring in μ, as a family of positive real numbers with multiplicities.) To start with, one might look for bounds in terms of the cardinalities of the positive and negative supports of μ.

Weaver [23] also gets a description of the universal nonexpanding map of X into a normed complex vector space, paralleling the description for the real case, but he notes [23, p.43, next-to-last paragraph of §2.2] that in the complex case it is no longer true that the infimum corresponding to (39) is always attained by a ν having the same support as μ. (In the complex version of (39), by the way, one must replace dν by |dν|, instead of restricting ν to a “positive cone” as above, since there is no natural analog of that cone. Weaver takes this approach for both the real and complex cases; my use of W_{+} for the real case is one of the different technical choices that I have made.) For instance, if X = {x, y_{0}, y_{1}, y_{2}} with d(x, y_{i}) = 1 and d(y_{i}, y_{j}) = 2 (i ≠ j), and if μ = μ_{y_{0}} + ωμ_{y_{1}} + ω^{2}μ_{y_{2}}, where ω is a primitive cube root of unity, then the minimizing ν is ν_{y_{0},x} + ων_{y_{1},x} + ω^{2}ν_{y_{2},x}, which makes that integral 3, while the best ν having support in the support of μ, \{y_{0}, y_{1}, y_{2}\}, is \frac{1}{3}(1 − ω)ν_{y_{0},y_{1}} + \frac{1}{3}(ω − ω^{2})ν_{y_{1},y_{2}} + \frac{1}{3}(ω^{2} − 1)ν_{y_{2},y_{0}}, of which each term contributes \frac{1}{3} · \sqrt{3} · 2 to that integral, giving a total of \sqrt{3} · 2 = \sqrt{12} > 3. If in this space we replace the point x by a sequence of points x_{1}, x_{2}, …, such that d(x_{m}, y_{i}) = 1 + 1/m and d(x_{m}, x_{n}) = |1/m − 1/n|, the above μ still has ||μ|| = 3, but the infimum defining that norm is not achieved.

7 Appendix: Translating convex sets to 0.

In §3, we saw that the radius of a subset X of a normed vector space V could be larger when measured within a convex subset C of V than within the whole space V. If we regard this as a pathology, we would like to know in which V it does not occur. We shall obtain partial results below, which, we will see, make it likely that for n > 2, the only norms on ℝ^{n} for which it does not happen are those giving a structure isomorphic to 𝔼^{n}.

Observe that the radius of X, whether within V or within a convex subset C, is determined by the set of closed balls containing X, and that these are all convex; hence that radius is a function of the convex hull of X. So our question reduces to the case where X is convex. Moreover, if X shows the above behavior with respect to one convex subset C of V, it will show it with respect to any smaller convex subset in which it lies; these two observations reduce our question to the case where C = X. This reduction is the equivalence of conditions (41) and (42) of the next lemma. Condition (43) then reformulates the problem.

(Note that in (43) and similar statements throughout this section, an expression such as “C − v” will denote the translate of the set C by the vector −v, in contrast to notations such as X −{x} for set-theoretic difference, used occasionally in earlier sections.)

Lemma 27. If V is a locally compact normed vector space, with closed unit ball B, then the following conditions are equivalent:

(41) For every nonempty subset X of V, and convex subset C of V containing X, one has rad_{V} (X) = rad_{C}(X).

(42) For every nonempty convex subset C of V, one has rad_{V} (C) = rad_{C}(C).

(43) Every nonempty closed convex subset C of B has a translate C − v which contains 0 and is again contained in B.

Proof. We have noted the equivalence of (41) and (42); let us prove (42) equivalent to (43).

(43) ⇒ (42): Dilating by arbitrary constants, we see that if (43) holds for B, then it holds for rB for all positive real numbers r. Moreover, the statement that C − v contains 0 and is contained in rB is equivalent to saying that v ∈ C and that v + rB contains C; i.e., that C is contained in the ball of radius r about v ∈ C. Thus (43) says that if a closed convex set C is contained in some closed ball about some point of V (taken without loss of generality to be 0), then it is contained in a ball of the same radius about one of its own points. This yields the case of (42) where C is closed. The facts that the convex hull of a finite subset of V is compact, hence closed, and that the radius in a locally compact space of any set is the supremum of the radii of its finite subsets, allow us to deduce the general case of (42) from the case of closed C.

(42) ⇒ (43): If C is a closed convex subset of V contained in B, then rad_{V} (C) ≤ 1, so by (42), rad_{C}(C) ≤ 1. Moreover, compactness of C implies that the set of radii of closed balls containing C and centered at points v ∈ C achieves this minimum rad_{C}(C) ≤ 1, so that C is contained in a translate v + B (v ∈ C), i.e., C − v ⊆ B.

Now (43) is a statement purely about the convex set B in the topological vector space V, so our question becomes that of which subsets B of a topological vector space V satisfy it. (In the statement of the lemma, the topology and the set B both arise from the normed structure on V; but that relation is not needed by the statement of (43) alone.) Here are some pieces of language, one ad hoc, the rest more or less familiar, that we will use in examining this question.

Definition 28. If C ⊆ B are convex subsets of a real vector space V, with 0 ∈ B, we shall call C parkable in B if there exists v ∈ C such that C − v ⊆ B. When clear from context, “in B” may be omitted.

If V is a real topological vector space, we will call sets of the form {x ∈ V | L(x) = a}, where L is a nonzero continuous linear functional on V and a ∈ ℝ, hyperplanes, while sets of the form {x ∈ V | L(x) ≥ a} will be called closed half-spaces.

A subset S of a vector space V will be called centrally symmetric if S = −S. A center of symmetry of a subset S of V will mean a point v ∈ V such that S − v is centrally symmetric; equivalently, such that S = 2v − S. (Note that a center of symmetry of a nonempty convex set belongs to that set.)

Lemma 29. Let B be a compact convex subset of ℝ^{n} containing 0. Then the following conditions are equivalent:

(44) The intersection of B with every hyperplane A that meets B is parkable.

(45) The intersection of B with every closed half-space H that meets B is parkable.

(46) Every nonempty closed convex subset C of B is parkable (= (43) above).

Proof. (46) ⇒ (44) is clear; we will show (44) ⇒ (45) ⇒ (46).

(44) ⇒ (45): Let H be a closed half-space in ℝ^{n}, bounded by a hyperplane A, and meeting B. If H ∩B contains 0 it is trivially parkable, so assume the contrary. Thus B meets both H and its complement, hence it meets their common boundary A, so by (44) there exists v ∈ A ∩ B such that (A ∩ B) − v ⊆ B. I claim that (H ∩ B) − v is also contained in B. Indeed, let p ∈ H ∩ B; we wish to show p − v ∈ B. Intersecting our sets with the subspace of V spanned by p and v, and taking appropriate coordinates, we may assume that n = 2, that A is the line {(x, y) | y = 1} ⊆ ℝ^{2}, and that v is the point (0, 1). H will be the closed half-plane {(x, y) | y ≥ 1}, so we can write p = (x_{p}, y_{p}) with y_{p} ≥ 1.

In this situation, A ∩ B will be a line segment (possibly degenerate) extending from a point (s, 1) to a point (t, 1) (s ≤ t). Since (A ∩ B) − v ⊆ B, B also contains the segment from (s, 0) to (t, 0). Note that if x_{p} were > t, then the point where the line segment from p = (x_{p}, y_{p}) ∈ B to (t, 0) ∈ B meets A would have x-coordinate > t, contradicting the assumption that A ∩ B terminates on the right at (t, 1); so x_{p} ≤ t. Similarly, x_{p} ≥ s. Thus, x_{p} ∈ [s, t], so (x_{p}, 0) ∈ B. Hence p − v = (x_{p}, y_{p}−1) lies on the line segment connecting p = (x_{p}, y_{p}) ∈ B with (x_{p}, 0) ∈ B, hence lies in B, as claimed.

(45) ⇒ (46): Suppose C is a nonempty closed convex subset of B which is not parkable. By compactness of B, among the translates of C contained in B there is (at least) one that minimizes its distance to 0 in the Euclidean norm on ℝ^{n}; let us assume C itself has this property. Let p be the point of C nearest to 0 in that norm, and let A be the hyperplane passing through p and perpendicular (again in the Euclidean norm) to p regarded as a vector. Then C will lie wholly in the half-space H bounded by A and not containing 0. (For if we had q ∈ C not lying in H, then points close to p on the line segment from p to q would be nearer to 0 than p is.) Assuming (45), H ∩ B is parkable; say v ∈ H ∩ B with (H ∩ B) − v ⊆ B. Since v ∈ H, if we write v as the sum ap + q of a scalar multiple of p and a vector q perpendicular to p, the coefficient a will be ≥ 1, and so in particular, positive. It follows that for sufficiently small positive c, the point p − cv will be closer to 0 than p is; moreover, if we take such a c that is ≤ 1, (H ∩ B) − cv will still be contained in B, since H ∩ B and (H ∩ B) − v are. Hence C − cv is contained in B, and has a point p − cv which is closer to 0 than p is, contradicting our minimality assumption on C and p.

(In the above result, we could have replaced ℝ^{n} by any real Hilbert space.)

Clearly, the closed Euclidean unit ball in ℝ^{n} satisfies (44), and hence (45) and (46); hence since those conditions are preserved by invertible linear transformations, so does the closed region enclosed by any ellipsoid centered at 0. On the other hand, our example in the paragraph containing (23), of a normed vector space in which (41) failed, had for its unit ball B a 3-cube centered at 0, showing that our properties fail for that B. To see geometrically the failure of (44) for that B, choose a vertex of that cube and pass a plane A through the three vertices adjacent thereto; it is not hard to see that A ∩ B is not parkable. One can similarly show that none of the regular polyhedra centered at 0 satisfy (44), nor a circular cylinder centered at 0, nor the solid obtained by attaching a hemisphere to the top and bottom of such a cylinder. In fact, for n > 2, I know of no compact convex subset of ℝ^{n} with nonempty interior that does satisfy that condition, other than the regions enclosed by ellipsoids centered at 0. The situation is different for n = 2, as shown by point (d) of the next result.

Lemma 30. Suppose B is a centrally symmetric convex subset of ℝ^{n}. Then

(a) Any nonempty convex subset C ⊆ B that has a center of symmetry is parkable in B.

Hence, assuming in the remaining points that B is also compact, we have

(b) If the intersection of B with every hyperplane A that meets B has a center of symmetry, then B satisfies the equivalent conditions (44)-(46).

In particular,

(c) If B is the closed region enclosed by an ellipsoid in ℝ^{n}, then B satisfies (44)-(46), and

(d) If n = 2, then without further restrictions, B satisfies (44)-(46).

Proof. Let C be as in (a), with center of symmetry z ∈ C. Then for every x ∈ C, 2z − x ∈ C ⊆ B, so by central symmetry of B, we have x − 2z ∈ B. Averaging x and x − 2z, we get x − z ∈ B. Thus C − z ⊆ B, so C is parkable.

It follows that any B as in (b) satisfies (44), hence by Lemma 29, all of (44)-(46).

In the situation of (c), the intersection of B with a hyperplane A, if nonempty, is either a point or the region enclosed by an ellipsoid in A, hence has a center of symmetry, while in (d) the intersection of B with every line in ℝ^{2} that meets B is a point or a closed line segment, hence has a center of symmetry; so in each case, (b) gives the asserted conclusion.

Question 31. Let n ≥ 3, and suppose B is a compact convex subset of ℝ^{n} having nonempty interior and containing 0. Of the implications (i) ⇒ (ii) ⇒ (iii), which we have noted hold among the conditions listed below, is either or both reversible?

(i) B is an ellipsoid centered at 0.

(ii) B is centrally symmetric, and for every hyperplane A meeting B, A ∩ B has a center of symmetry.

(iii) Every closed convex subset of B is parkable in B.

Branko Grünbaum has pointed out to me a similarity between this question and the result of W. Blaschke [3, pp.157–159] that if E is a smooth compact convex surface in ℝ^{3} with everywhere nonzero Gaussian curvature, such that when E is illuminated by parallel rays from any direction, the boundary curve of the bright side lies in a plane, then E is an ellipsoid. I believe that methods similar to Blaschke’s may indeed show that both implications of Question 31 are reversible. To see why, suppose B is a compact convex subset of ℝ^{3} with nonempty interior containing 0, which satisfies (iii) above, and whose boundary E is (as in Blaschke’s result) a smooth surface with everywhere nonzero Gaussian curvature. Let A be any plane through 0, and A′ the plane gotten by shifting A a small distance. Now the vectors that can possibly park A′ ∩ B are constrained by the directions of the tangent planes to E at the points of A′ ∩ E (which are well-defined because E is assumed smooth), and if we take A′ sufficiently close to A, these tangent planes become close to the corresponding tangent planes at the points of A ∩ E. Applying the above observations to planes A′ on both sides of A, one can deduce that all the tangent planes to E along A∩E must contain vectors in some common direction (I am grateful to Bjorn Poonen for this precise formulation of a rough idea I showed him); in other words, that A ∩ E is the boundary of the bright side when E is illuminated by parallel rays from that direction. By definition, A ∩ E lies in the plane A; so we have the situation that Blaschke considered, except that we have started with planarity and concluded that the curve is a boundary of illumination, rather than vice versa.

That last difference is probably not too hard to overcome. More serious is the smoothness assumption on E , used in both the above discussion and Blaschke’s argument. Finally, can the result be pushed from n = 3 to arbitrary n ≥ 3 ? I leave it to those more skilled than I in the subject to see whether these ideas can indeed be turned into a proof that (iii)⇒(i) in Question 31.

A related argument which can be extracted from a step in Blaschke’s development shows that a compact convex subset B of ℝ^{2} containing 0 and satisfying (46), whose boundary is a smooth curve containing no line segments, must be centrally symmetric. Again, one would hope to remove the conditions on the boundary.

One can ask about a converse to another of our observations:

Question 32. Suppose C is a compact convex subset of ℝ^{n} (n > 2) such that for every centrally symmetric compact convex subset B of ℝ^{n} containing a translate C′ of C, the set C′ is parkable in B. Must C have a center of symmetry?

Here the behavior of a given C can change depending on whether the dimension of the ambient vector space is 2 or – as in the above question – larger: a triangle C has the above property in ℝ^{2} by Lemma 30(d), but not in ℝ^{3}, as we saw in the example where B was a cube.

Returning to the “pathology” which motivated the considerations of this section, one important case is where the radius of a subset X of a normed vector space V decreases when V is embedded in a larger normed vector space W. The next lemma determines how far down the radius of a given X can go.

Lemma 33. Let V be a normed vector space, and X a bounded nonempty subset of V. Then

(47) inf_{W ⊇V} rad_{W} (X) = rad_{V} {(x − y)/2 | x, y ∈ X} = diam(X)/2,

where the W in the infimum ranges over all normed vector spaces containing V. Moreover, that infimum is realized by a W in which V has codimension 1.

Proof. Note first that {(x − y)/2 | x, y ∈ X} is centrally symmetric, hence by Lemma 5, its radius in V is the supremum of the distances of its points from 0, which is just the last term of (47). Moreover, the radius of X in any normed vector space containing it is at least half the distance between any two points of X, so the first term of (47) is ≥ those last two terms. It remains to prove the reverse inequality.

That inequality is trivial if the diameter of X is zero or infinite. Assuming it is neither, we may re-scale and suppose without loss of generality that the last two terms of (47) equal 1. Thus, {(x − y)/2 | x, y ∈ X} is contained in the closed unit ball B_{V} of V. Now let W = V ⊕ ℝ, let us identify V with V × {0} ⊆ W, and let us take for the closed unit ball B_{W} of W the closure of the convex hull of

(48) {(x, 1) | x ∈ X} ∪ B_{V} ∪ {(−x, −1) | x ∈ X}.

(We understand “closure” to mean “with respect to the product topology”, since we don’t have a norm until we have made the above definition.) It is easy to see that any point in the convex hull of (48) whose second coordinate is 0 is a convex linear combination of a point of B_{V} and a member of {(x − y)/2 | x, y ∈ X}.

But we have seen that the latter set is contained in B_{V}; so B_{W} ∩ V = B_{V} , proving that our norm on W extends that of V.

But B_{W} also contains a translate {(x, 1) | x ∈ X} of X. Hence X is contained in a closed ball of radius 1, so its radius in W is ≤ 1 = diam(X)/2, as required.

Even the case V = 𝔼^{n} is not immune to this phenomenon, since even in that case, the overspace W of the above construction is generally not Euclidean. For instance, if we take for X an equilateral triangle in 𝔼^{2} centered at the origin, it is not hard to see that {(x − y)/2 | x, y ∈ X} is a hexagon whose vertices are the midpoints of the edges of a regular hexagon with the same circumcircle as X; so the radius of X decreases in W by the ratio of the inradius to the circumradius of a regular hexagon, in other words, by \sqrt{3}/2.

This will not, of course, happen for a centrally symmetric X (cf. Lemma 30 or (47)). Other cases for which it cannot happen depend on the metric structure: if X is a right or obtuse triangle in 𝔼^{2}, or more generally, any bounded set containing a diameter of a closed ball in which it lies, its radius clearly cannot go down under extension of the ambient normed vector space (cf. Corollary 10).

8 Acknowledgements.

In addition to persons acknowledged above, I am indebted to W. Kahan for showing me an exercise he had given his Putnam-preparation class, of proving Lemma 2 in 𝔼^{3}, and for subsequently pointing out that my solution to that exercise worked in any normed vector space; to Nik Weaver for for much helpful discussion of the relation between the present material and that of [23], and to David Gale for pointing out the connection between the construction of §6 and results in mathematical economics.

References

[1] Richard F. Arens and James Eells, Jr., On embedding uniform and topological spaces, Pacific J. Math. 6 (1956) 397–403. MR 18, 406e.

[2] Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, v.319. Springer, 1999. MR 2000k:53038.

[3] Wilhelm Blaschke, Kreis und Kugel, Leipzig, 1916, reprinted by Chelsea Publishing Company, New York, 1949. MR 17, 887b.

[4] Herbert Busemann, Spaces with non-positive curvature, Acta Math. 80 (1948) 259–310. MR 10,623g.

[5] G. D. Chakerian and M. S. Klamkin, Minimal covers for closed curves, Math. Mag., 46 (1973) 55–61. MR 47#2496.

[6] S. S. Chern, Curves and surfaces in Euclidean space, Studies in Global Geometry and Analysis, pp.16-56, Math. Assoc. Amer., Studies in Math., v.4, 1967. MR 35#3610.

[7] H. S. M. Coxeter, Regular Polytopes, Methuen & Co.; Pitman, 1948; 1949. MR 10,261e, and for subsequent editions, MR 27#1856 and MR 51#6554.

[8] Ludwig Danzer, Branko Grünbaum and Victor Klee, Helly’s theorem and its relatives, Proc. Sympos. Pure Math., Vol. VII, pp. 101–180, Amer. Math. Soc., Providence, R.I., 1963. MR 28#524.

[9] Werner Fenchel, Über Krümmung und Windung geschlossener Raumkurven, Math. Ann., 101 (1929) 238–252.

[10] David Gale, On inscribing n-dimensional sets in a regular n-simplex, Proc. Amer. Math. Soc., 4 (1953) 222–225. MR 14,787b.

[11] David Gale, The theory of linear economic models, McGraw-Hill, 1960; University of Chicago Press, 1989. MR 22#6599.

[12] Hugo Hadwiger and Hans Debrunner, Combinatorial geometry in the plane, translated by Victor Klee, with a new chapter and other additional material supplied by the translator. Holt, Rinehart and Winston, New York 1964 vii + 113 pp. MR 29#1577.

[13] J. Håstad, S. Linusson and J. Wästlund A smaller sleeping bag for a baby snake, Discrete Comput. Geom., 26 (2001) 173–181. MR 2002b:52012.

[14] E. Helly, Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deutsch. Math.- Verein., 32 (1923) 175–176.

[15] Einar Hille, Analytic function theory, v. II, Ginn and Co., Boston, 1962. MR 34#1490.

[16] R. A. Horn, On Fenchel’s Theorem, Amer. Math. Monthly, 78 (1971) 380-381. MR 44#2142.

[17] Heinrich W. E. Jung, Über die kleinste Kugel, die eine räumliche Figur einschliesst, J. Reine Angew. Math., 123 (1901) 241–257.

[18] J. C. C. Nitsche, The smallest sphere containing a rectifiable curve, Amer. Math. Monthly, 78 (1971) 881–882. MR 45#480.

[19] H. Rutishauser and H. Samelson, Sur le rayon d’une sphére dont la surface contient une courbe fermée, C. R. Acad. Sci. Paris, 227 (1948) 755–757. MR 10, 321c; correction, MR 10, p.856.

[20] Jonathan Schaer and John E. Wetzel, Boxes for curves of constant length, Israel J. Math., 12 (1972) 257–265. MR 47#5726.

[21] B. Segre, Sui circoli geodetici di una superficie a curvatura totale constante, che contengono nell’interno una linea assegnata, Boll. Un. Mat. Ital., 13 (1934) 279–283. Zbl 10, 271.

[22] Philip C. Tonne, A simple closed curve on a hemisphere, Houston J. Math., 10 (1984) 585. MR 86b:53004.

[23] Nik Weaver, Lipschitz algebras, World Scientific Publishing, River Edge, NJ, 1999, xiv + 223 pp., ISBN: 981-02-3873-8. MR 2002g:46002.

[24] Alan Weinstein, Almost invariant submanifolds for compact group actions, J. Eur. Math. Soc. 2 (2000) 53–86. MR 2002d:53076.

[25] John E. Wetzel, Covering balls for curves of constant length, Enseignement Math., (2) 17 (1971) 275– 277. MR 48#12315.

George M. Bergman Department of Mathematics University of California Berkeley, CA 94720-3840 USA gbergman@math.berkeley.edu