Maximum of three numbers: it’s harder than it sounds

This simple identity hold for any two real numbers {x,y}:

\displaystyle   \max(|x|,|y|) = \frac12\,(|x+y|+|x-y|)   \ \ \ \ \  \ \ \ \ \ (1)

Indeed, if {|x|} realizes the maximum, then both {x+y} and {x-y} have the same sign as {x}. After opening the absolute value signs, we get {y} to cancel out.

So, (1) represents {\max(|x|,|y|)}, also known as the {\ell_\infty} norm, as the sum of absolute values of linear functions. Let’s try the same with {\max(|x|,|y|,|z|)}. Since the right hand side of (1) is just the average of {|\pm x \pm y|} over all possible choices of {\pm } signs, the natural thing to do is to average {|\pm x \pm y \pm z|} over all eight choices. The sign in front of {x} can be taken to be {+}, which simplifies the average to

\displaystyle    \frac14\,(|x+y+z|+|x+y-z|+|x-y+z|+|x-y-z|)    \ \ \ \ \  \ \ \ \ \ (2)

Does this formula give {\max(|x|,|y|,|z|)}? Instead of trying random numbers, let’s just plot the unit ball for the norm given by (2). If the identity works, it will be a cube. I used Maple:

with(plots): f:=(abs(x+y+z)+abs(x+y-z)+abs(x-y-z)+abs(x-y+z))/4:
implicitplot3d(f=1,x=-1/4..1/4,y=-1/4..1/4,z=-1/4..1/4,grid=[25,25,25]);
My precious!
My precious!

Close, but no cube. Luckily, this is my favorite Archimedean solid, the cuboctahedron.

Although all terms of (2) look exactly the same, the resulting shape has both triangular and square faces. Where does the difference of shapes come from?

More importantly, is (2) really the best we can do? Is there some other sum of moduli of linear functions that will produce {\max(|x|,|y|,|z|)}?

— No.

Even if negative coefficients are allowed?

— Even then. (But you can come arbitrarily close.)

What if we allow integrals with respect to an arbitrary (signed) measure, as in

\displaystyle    \iiint |\alpha x+\beta y+\gamma z|\,d \mu(\alpha, \beta, \gamma)    \ \ \ \ \  \ \ \ \ \ (3)

— Still no. But if {\mu} is allowed to be a distribution of higher order (an object more singular than a measure), then a representation exists (W. Weil, 1976). Yes, one needs the theory of distributions to write the maximum of three numbers as a combination of linear functions.

I’ll only prove that there is no identity of the form

\displaystyle  \max(|x|,|y|,|z|) = \sum_{i=1}^N |\alpha_i x+\beta_i y+ \gamma_i z|

Indeed, such an identity amounts to having an isometric embedding {T\colon \ell_\infty^3 \rightarrow \ell_1^N}. The adjoint operator {T^* \colon \ell_\infty^N \rightarrow \ell_1^3} is a submetry meaning that it maps the unit ball of {\ell_\infty^N } onto the unit ball {\ell_1^3}. The unit ball of {\ell_\infty^N } is just a cube; all of its faces are centrally symmetric, and this symmetry is preserved by linear maps. But {\ell_1^3} is an octahedron, with triangular faces. A contradiction. {\ \Box}

An aside: what if instead of averaging {|\pm x \pm y|} over all {\pm } choices (i.e., unimodular real coefficients) we take the average over all unimodular complex coefficients? This amounts to {\|(x,y)\| = \frac{1}{2\pi} \int_0^{2\pi} |x+e^{it}y|\,dt}. I expected something nice from this norm, but

Complex averaging in real space
Complex averaging in real space

it’s a strange shape whose equation involves the complete elliptic integral of second kind. Yuck.

Three weddings and a funeral

This is a continuation of the series on submetries. First, an example: the distance function to a closed convex set K\subset \mathbb R^n is a submetry from \mathbb R^n\setminus K onto (0,\infty). Note that the best regularity we can expect from such distance function is C^{1,1}, the Lipschitzness of first derivatives. The second derivative does not exist at the points where level curves make the transition from straight to circular.

Distance function is a submetry

Now back to an attempt to introduce duality between immetries (=isometric embeddings) and submetries. Recall that the Lipschitz dual X^\sharp of a pointed metric space X\ni 0 is the set of all Lipschitz functions \varphi\colon X\to\mathbb R such that f(0)=0. Given the Lipschitz norm, X^\sharp becomes a Banach space. Any closed ball B_r(a)\subset X can be written as
(*) B_r(a)=\lbrace x\in X\colon |\varphi(x)-\varphi(a)|\le r \text{ for all } \varphi\in X^\sharp \text{ such that }\|\varphi\|\le 1\rbrace.
Indeed, \subset is obvious, and the reverse inclusion follows by considering \varphi(x)=d(x,a)-d(0,a).

It’s natural to use (*) to relate immetries to submetries, because the former are defined by f^{-1}(B_r(f(x)))=B_r(x) and the latter by f(B_r(x))=B_r(f(x)).

In the previous post I considered four implications:

  1. If f is an immetry, then f^\sharp is a submetry
  2. If f is a submetry, then f^\sharp is an immetry
  3. If f^\sharp is an immetry, then f is a submetry
  4. If f^\sharp is a submetry, then f is an immetry

I proved (1) already. Implication (2) is also easy to prove: if f\colon Y\to X is a submetry, then \|\varphi\circ f\|=\|\varphi\| for every \varphi\in X^\sharp, because pairs of points that (almost) realize \|\varphi\| can be lifted through f.

Here is a proof of (4). If f^{\sharp}\colon X^\sharp\to Y^\sharp is a submetry, then \lbrace \varphi\in X^\sharp \colon \|\varphi\|\le 1\rbrace = \lbrace \psi\circ f\colon \psi\in Y^\sharp,  \|\psi\|\le 1\rbrace. We can use this in (*) to obtain, for any a\in X and r\ge 0,
B_r(a)=\lbrace x\in X\colon |\psi(f(x))-\psi(f(a))|\le r \text{ for all } \psi\in Y^\sharp \text{ such that }\|\psi\|\le 1\rbrace.
The latter set is nothing but \lbrace x\in X\colon f(x)\in B_r(f(a))\rbrace, which means f is an immetry.

I already noted that (3) fails for general metric spaces, the inclusion f\colon \mathbb Q\to \mathbb R being a counterexample. However, this counterexample is not impressive, because f(B_r(x)) is dense in B_r(f(x)). One could still hope that (3) holds for proper metric spaces. By definition, a metric space is proper if every closed ball is compact. (Or, equivalently, every bounded sequence has a convergent subsequence.) In metric geometry properness is a very common assumption which excludes incomplete spaces and infinite-dimensional spaces. Its relevance to submetries can be seen from their definition f(B_r(x))=B_r(f(x)). It requires the image f(B_r(x)) to be closed, which is not very likely to happen unless B_r(x) is compact. (No such issues arise on the immetry side, because f^{-1}(B_r(f(x))) is always closed.)

However, it turns out (3) is false even for compact spaces. The counterexample was already present on this blog:

These aren't the quotients I'm looking for

Indeed, the Lipschitz norm of a function \varphi defined on an interval is equal to the essential supremum of |\varphi'|. The composition with the metric quotient map given above preserves \mathrm{ess\,sup}\, |\varphi'|. Hence, the induced map [0,2]^\sharp\to [0,3]^\sharp is an immetry.

Lipschitz duality: immetries and submetries

Continuation of an earlier post that considered submetries, namely the maps f\colon Y\to X between metric spaces such that f(B_r(y))=B_r(f(y)) for all y\in Y and all r\ge 0. (Here and in what follows B_r is a closed ball.) The dual notion is an immetry: a map f\colon X\to Y such that f^{-1}(B_r(f(x)))=B_r(x) for all x\in X and all r\ge 0. Immetries can be characterized by the condition d(f(a),f(b))=d(a,b), which means they are nothing but isometric embeddings. I just made up the word to introduce symmetry between submetry and immetry. And then tried to look it up.

This has got me stumped

In what sense are these dual? Recall that reversal of arrows in a “categorical” definition of an immetry did not produce a submetry. Let’s try another approach. Let our metric spaces be pointed: they all contain the point 0 which is fixed by all maps under consideration. The Lipschitz dual X^\sharp of a metric space X consists of all Lipschitz maps \varphi\colon X\to \mathbb R. This is naturally a vector space. Moreover, it is a Banach space with the norm \displaystyle \|\varphi\|=\sup\frac{|\varphi(a)-\varphi(b)|}{d(a,b)} if we identify the functions that differ by a constant. A Lipschitz map f\colon X\to Y induces a bounded linear operator f^\sharp\colon Y^\sharp\to X^\sharp. If f is 1-Lipschitz, then so is f^\sharp (i.e., its operator norm is at most 1).

It would be nice to have the following:

  • f is an immetry iff f^\sharp is a submetry
  • f is a submetry iff f^\sharp is an immetry

but that’s too much to hope for. For example, the inclusion of \mathbb Q into \mathbb R is not a submetry, but it induces the identity map \mathbb R^\sharp\to\mathbb Q^\sharp. Let’s go through these one by one.

Suppose f\colon X\to Y is an immetry. Then we think of X as a subset of Y, and f^\sharp is simply the restriction operator. To prove that it’s a submetry, we should verify the 2-point lifting property: given any \varphi,\psi\in X^\sharp and any \Phi\in Y^\sharp that extends \varphi, we must find \Psi\in Y^\sharp that extends \psi and satisfies \|\Psi-\Phi\|=\|\psi-\varphi\|. This is easy: extend \psi-\varphi in a norm-preserving way (by McShane-Whitney) and add \Phi.

I also wrote down an (easy) proof that f being a submetry implies that f^\sharp is an immetry, but WP ate it. Specifically, having pressed “Save Draft”, I was asked to re-login (the cookie expired). Having done so, I was presented with a 10 min old draft.

We already know that f^\sharp being an immetry does not imply that f is a submetry. Whether f^\sharp being an submetry implies that f is an immetry is left as an exercise for the reader.

Injective:Surjective :: Isometric:?

I used this sort of title before, in “Continuous:Lipschitz :: Open:?“, but the topics are related anyway.

In some sense (formal or informal) the following classes of maps are dual to each other.

  • Injective : Surjective
  • Immersion : Submersion
  • Monomorphism : Epimorphism

An isometric embedding of metric space X into a metric space Y is a map f\colon X\to Y such that d_Y(f(a),f(b))=d_X(a,b) for all a,b\in X. This concept belongs to the left column of the table above. What should be its counterpart?

Candidate 1. Observe that a 1-Lipschitz map f\colon X\to Y is an isometric embedding iff it does not factor through any 1-Lipschitz surjection g\colon X\to Z (for any space Z) unless g is an isometric isomorphism. Reversing the order of arrows, we arrive at the following concept:

A 1-Lipschitz map f\colon Y\to X is a metric quotient map if it does not factor through any 1-Lipschitz injection g\colon Z\to X (for any space Z) unless g is an isometric isomorphism.

This can be reformulated as follows: \rho(a,b):=d_{X}(f(a),f(b)) is the greatest pseudo-metric on Y subject to

  1. \rho(a,b)\le d_{Y}(a,b)
  2. \rho(a,b)=0 if f(a)=f(b)

This seems reasonable: f does as little damage as possible, given the structure of its fibers. There is also a natural way to construct \rho for any reasonable fibering of Y: begin by defining \widetilde{d_Y}=d_Y for points in different fibers and 0 otherwise. Then force the triangle inequality by letting \rho(a,b)=\inf \sum_{j=1}^n \widetilde{d_Y}(y_j,y_{j-1}) subject to y_0=a and y_n=b. As long as the fibers stay at positive distance from one another, this \rho will be a metric. The corresponding metric quotient map sends each point of Y onto its fiber.

Here is a simple example, in which a part of an interval is mapped to a point.

These aren't the quotients I'm looking for

However, the above example made me unhappy. The only nontrivial fiber is the interval [1,2]. Both points 0 and 3 belong to trivial fibers, but the distance between them decreases from 3 to 2. This looks like a wrong kind of quotient to me.

Candidate 2 already appeared in my post on Lipschitz quotient, but wasn’t recognized at the time. It could be called (1,1)-Lipschitz quotient, but a better name is available. A map f\colon Y\to X is a submetry if f(B_Y(y,r))=B_X(f(y),r) where the balls are closed (using open balls yields something almost equivalent, but generally weaker). Such f need not be an isometry: consider orthogonal projections in a Euclidean space. It does have to be 1-Lipschitz. The additional property that distinguishes it from general 1-Lipschitz maps is the 2-point lifting property: for every x_0,x_1\in X and every y_0\in f^{-1}(x_0) there is y_1\in f^{-1}(x_1) such that d_{Y}(y_0,y_1)=d_X(x_0,x_1). Incidentally, this shows that x\mapsto f^{-1}(x) is an isometric embedding of X into the hyperspace \mathcal{H}(Y) which I covered earlier (“This ain’t like dusting crops, boy“).

The concept and the name were introduced by В.Н. Берестовский (V.N. Berestovskii) in his paper “Submetries of space-forms of nonnegative curvature” published in 1987 in Siberian Math. J. Among other things, he proved that a submetry between spheres (of any dimension) is an isometry. Of course, there are many submetries of S^{n-1} onto other spaces: take the quotient by a subgroup of O(n), which can be either discrete or continuous. Are there any submetries that are not quotients by isometries?

Yes, there are. I’ll describe a (modified) example given by Berestovskii and Guijarro (2000). Let \mathbb{H} be the hyperbolic plane realized as the upper half-plane with the metric \frac{dx^2+dy^2}{y^2}. Define f\colon \mathbb{H}\to\mathbb{R} by

\displaystyle f(x,y)=\begin{cases} \log y, \qquad x\le 0 \\ \log\frac{x^2+y^2}{y}, \qquad x\ge 0 \end{cases}

Don’t panic; this is just the signed distance function (in the metric of \mathbb H) to the fat green curve below. I also drew two other level sets of f, to the best of my Friday night line-drawing ability.

Weird submetry

To convince yourself that f is a submetry, first consider y\mapsto \log y for which the submetry property is clear (it’s the quotient by horizontal translation), and then note that the inversion in the unit circle exchanges horizontal lines (horocycles at infinity) with horocycles at 0. An interesting feature of this submetry that it is not very smooth: C^{1,1} but not C^2.