Retraction by contraction

The Euclidean space {\mathbb R^n} has a nice property: every closed convex subset {C\subset \mathbb R^n} is the image of the whole space under a map {f} that is simultaneously:

  • a contraction, meaning {\|f(a)-f(b)\|\le \|a-b\|} for all {a,b\in\mathbb R^n};
  • a retraction, meaning {f(a)=a} for all {a\in C}.

Indeed, we can simply define {f(x)} to be the (unique) nearest point of {C} to {x}; it takes a bit of work to verify that {f} is a contraction, but not much.

In other normed spaces, this nearest point projection does not work that well. For example, take {X=\ell_1^2}, the two-dimensional space with the Manhattan metric. Consider the line {C=\{(2t,t)\colon t\in\mathbb R\}} which is a closed and convex set. The nearest point of {C} to {(2,0)} is {(2,1)}: moving straight up, since changing the first coordinate doesn’t pay off. Since {(0,0)} remains fixed, the nearest point projection increases some pairwise distances, in this case from {2} to {3}.

However, there is a contractive retraction onto this line, given by the formuls {T(x_1,x_2) =    \left(\frac23(x_1+x_2), \frac13(x_1+x_2)\right)}. Indeed, this is a linear map that fixes the line {x_1=2x_2} pointwise and has norm {1} because

\displaystyle \|T(x)\|_1 = |x_1+x_2|\le \|x\|_1

More generally, in every normed plane, every closed convex subset admits a contractive retraction. To prove this, it suffices to consider closed halfplanes, since a closed convex set is an intersection of such, and contractions form a semigroup. Furthermore, it suffices to consider lines, because having a contractive retraction onto a line, we can redefine it to be the identity map on one side of the line, and get a contractive retraction onto a halfplane.

Such a retraction onto a line, which is a linear map, is illustrated below.

Every line in a normed plane is 1-complemented
Every line in a normed plane is 1-complemented

Given the unit circle (black) and a line (blue), draw supporting lines (red) to the unit circle at the points where it meets the line. Project onto the blue line along the red ones. By construction, the image of the unit disk under this projection is contained in the unit disk. This precisely means that the map has operator norm {1}.

In spaces of dimensions {3} or higher, there are closed convex subsets without a contractive retraction. For example, consider the plane in {\ell_\infty^3} passing through the points {A = (2,2,0)}, {B= (2,0,2)}, and {C= (0,2,2)}. This plane has equation {x_1+x_2+x_3=4}. The point {D=(1,1,1)} is at distance {1} from each of A,B,C, and it does not lie on the plane. For any point E other than D, at least one of the distances AE, BE, CE exceeds 1. More precisely, the best place to project D is {(4/3, 4/3, 4/3)} which is at distance {4/3} from A, B, and C.

Two natural questions: (a) is there a nice characterization of normed spaces that admit a contractive retraction onto every closed convex subset? (b) what is the smallest constant {L=L(n)} such that every {n}-dimensional normed space admits an {L}-Lipschitz retraction onto every closed convex subset?

(The answers may well be known, but not to me at present.)

Interpolating between a cone and a cylinder

This post is inspired by James Tanton’s video which is summarized in bulleted items below. For convenience normalize all solids to height {1}.

  • Parallel cross-sections of a cylinder have constant area. Therefore its volume is {\int_0^1 A z^0\,dz =Ah}, where {A} is the area of the base.
  • Parallel cross-sections of a cone are scaled in both directions by the {z}-coordinate. This multiplies the sectional area by {z^2} and therefore the volume is {\int_0^1 A z^2\,dz =\frac{1}{3}Ah}.
  • There is something in between: we can scale cross-sections in one direction only. Then the sectional area is multiplied by {z} and the volume is {\int_0^1 A z\,dz =\frac{1}{2}Ah}.

Taking the base to be a circle, we get this shape:

Pinched in one direction
Pinched in one direction

It looks… odd. Not even convex:

Convexity is lost
Convexity is lost

But cones and cylinders are convex whenever the base is a convex region. Can we interpolate between them within the class of convex sets?

The answer is: yes, if we use the Minkowski sum. Given two convex bodies {A_0} and {A_1} in {{\mathbb R}^3}, for {0< t<1} define

\displaystyle  A_t =(1-t)A_0+tA_1 = \{(1-t)a_0+ta_1 : a_0\in A_0, a_1\in A_1\}

Each {A_t} is convex. If the sets {A_0} and {A_1} are cone and cylinder of equal height and with the same convex base {B}, then all {A_t} have the same base and the same height.

Finding the volume of a convex body in Calculus II/III can be a tiresome exercise with trigonometric substitutions and whatnot. It may come as a surprise that the volume of {A_t} is always a cubic polynomial in {t}, even if the convex sets {A_0, A_1} are defined by some transcendental functions. I still do not find this fact intuitive.

Let’s check it on the example of {A_0} and {A_1} being a cone and a cylinder of height {1} and radius {r}. Obviously, every {A_t} is a solid of revolution. Its profile is the Minkowski sum of appropriately scaled triangle and rectangle. This is how I imagine it:

  • Mark a point on the rectangle, for example the midpoint of the bottom edge.
  • Move the rectangle around so that the marked point stays within the triangle.
  • The region swept is the Minkowski sum.
Minkowski sum
Minkowski sum

The volume can now be computed directly. I used the venerable method of cylindrical shells to find the volume of {A_1\setminus A_t}:

\displaystyle 2\pi \int_{tr}^t x(x/r-t)\,dx = \frac{\pi r^2}{3}(2-3t+t^3)


\displaystyle  \mathrm{Vol}\, (A_t) = \frac{\pi r^2}{3}(1+3t-t^3)

It so happens that {\mathrm{Vol}\,(A_t)} is a concave function in this example, although in general only its cubic root is guaranteed to be concave, by the Brunn-Minkowski inequality.

When {t\approx 0.168}, the volume of {A_t} is equal to {\pi r^2/2}, same as the volume of James Tanton’s solid. Since {t} is pretty small, the shape looks much like a cone.

1/2 of area*height
Half of Area*Height

When {t\approx 0.347}, the volume of {A_t} is equal to {2\pi r^2/3}, which is exactly halfway between the volumes of cone and cylinder. The solid exhibits harmonious balance of both shapes.

2/3 of area*height
2/3 of area*height

Löwner-John ellipsoids

So far, everything was composed of definitions and trivial generalities. Now comes something deceptively simple but more substantial.

This is how Gromov introduces the maximal volume ellipsoid in his paper “Hilbert volume in metric spaces I”. The result is easy to state: for every origin-symmetric convex body K\subset \mathbb R^n there exists a unique ellipsoid E of maximal volume among the ellipsoids contained in K, and it satisfies E\subset K\subset \sqrt{n}E. The constant \sqrt{n} is sharp: it is attained, for example, when K is a cube.

The story of the maximum-volume ellipsoid is presented by Martin Henk in “Löwner-John ellipsoids”. In my experience, the name of Charles Loewner is not attached to this concept as often as Fritz John’s. From my undergraduate years I associated Loewner only with the parametric method of representing conformal maps, which he used to prove |c_3|\le 3, the first hard case of Bieberbach’s conjecture |c_n|\le n.

Charles Loewner in 1963, from Wikipedia

Henk mentions Loewner’s stay at Syracuse University, but does not specify the term, which was 1946–1951. A longtime chair of Syracuse math department Donald Kibbey recalled in 1980:

Loewner went to Stanford, Bers went to NYU and then Columbia, Gelbart went to Yeshiva, Cairns to Illinois, Milgram to Minnesota, Rosenbloom to Minnesota and then Columbia, Lorentz to Texas, Chung to Stanford, Greub to Toronto, Gilchrist to IBM, Rheinboldt to Maryland, Mostow to Hopkins and then Yale, Rosskopf to Columbia, Robert Davis to Illinois, Donald Austin and Mark Mahowald to Northwestern, Kleinfeld to Iowa, Ryser to Cal Tech, and Selberg to the Institute for Advanced Study, and Erdős to the world…. It’s too bad we didn’t keep some of them, I of course had my druthers, some people in there—some were magnificent. But think how much we helped the other places, Stanford, in particular, two of the finest.