## Notes of Urs Lang’s lecture nr 2

Lee: If a space ${X}$ is an absolute ${C}$-Lipschitz retract, with ${C>1}$, can you say anything of its injective hull ? Answer: probably no. For instance, the injective hull of Euclidean ${{\mathbb R}^n}$ is ${\ell_{\infty}^{2^{n-1}}}$ which seems very far from ${{\mathbb R}^n}$ although ${{\mathbb R}^n}$ is an absolute ${\sqrt{n}}$-Lipschitz retract.

1. Injective hulls: basics

1.1. Extremal functions

Let ${X}$ be a metric space. Leopoldo Nachbin, in the 1950’s, already considered the set

$\displaystyle \begin{array}{rcl} \Delta(X)=\{f:X\rightarrow{\mathbb R}\,;\,f(x)+f(y)\geq d(x,y)\}. \end{array}$

Definition 1 The minimal elements of ${\Delta}$ are called extremal functions. The set of extremal functions is denoted by ${E(X)}$.

Note that if ${X}$ is compact, ${f\in\Delta(X)}$ is extremal iff for all ${x\in X}$, there exists ${y\in X}$ such that ${f(x)+f(y)=d(x,y)}$. In general,

${f\in\Delta(X)}$ is extremal iff for all ${x\in X}$, ${f(x)=\sup_{y\in X}d(x,y)-f(y)}$.

Note that all ${d_x :x'\mapsto d(x,x')}$ belong to ${E(X)}$. This yields a map ${e:X\rightarrow E(X)}$.

Lemma 2 Extremal functions are ${1}$-Lipschitz.

Proof: Given ${x\in X}$, define ${g:X\rightarrow{\mathbb R}}$ by ${g(y)=f(x)+d(x,y)}$ and ${g(x')=f(x')}$ for ${x'\not=y}$. Then ${g\in\Delta(X)}$, so

$\displaystyle \begin{array}{rcl} f(y)\leq g(y)=f(x)+d(x,y). \end{array}$

$\Box$

Let

$\displaystyle \begin{array}{rcl} \Delta_{1}(X)=\{f\in\Delta(X)\,;\, f\textrm{ is }1\textrm{-Lipschitz}\}. \end{array}$

Then the ${L_{\infty}}$-norm defines a metric on ${\Delta_1 (X)}$.

Proposition 3 (Dress) There is a map ${p:\Delta(X)\rightarrow E(X)}$ such that

1. ${p(f)\leq f}$.
2. ${\|p(f)-p(g)\|_{\infty}\leq \|f-g\|_{\infty}}$.

Proof: For ${f\in\Delta(X)}$, set ${f^{*}(x)=\sup_{y\in X}d(x,y)-f(y)}$, so ${f}$ is extremal iff ${f=f^*}$. Note that ${f^* \leq f}$. By definition, for all ${x}$, ${y\in X}$,

$\displaystyle \begin{array}{rcl} f^* (x)+f(y)\geq d(x,y), \quad f(x)+f^* (y)\geq d(x,y), \end{array}$

so ${q(f):=\frac{1}{2}(f+f^* \in\Delta(X)}$, and ${q(f)\leq f}$. For every ${g\in \Delta(X)}$,

$\displaystyle \begin{array}{rcl} g^* (x)\leq f^* (x)+\|f-g\|_{\infty}. \end{array}$

Thus

$\displaystyle \begin{array}{rcl} \|q(f)-q(g)\|_{\infty} &\leq& \frac{1}{2}\|f-g\|_{\infty}+\frac{1}{2}\|f^* -g^* \|_{\infty}\\ &\leq& \|f-g\|_{\infty} \end{array}$

Define ${p(f):=\lim_{n\rightarrow\infty}q^{n}(f)}$ (pointwise limit). Then ${p(f)\leq f}$. For all ${n}$, ${p(f)^*\geq q^n (f)^*}$, so

$\displaystyle \begin{array}{rcl} 0\leq p(f)-p(f)^* \leq q^n (f)-q^n (f)^* =2(q^n (f)-q^{n+1} (f)) \end{array}$

which tends to ${0}$, so ${p(f)=p(f)^*}$. $\Box$

Remark 1 If ${|X|\geq 3}$, an infinite iteration is indeed needed to obtain ${p}$.

1.2. Injectivity

Proposition 4 ${\Delta_1 (X)}$ is injective.

Proof: Let ${A\subset B}$ be metric spaces, let ${F:A\rightarrow \Delta_1 (X)}$ be ${1}$-Lipschitz. For ${b\in B}$, ${x\in X}$, put

$\displaystyle \begin{array}{rcl} f_b (x)=\inf_{a\in A}F(a)(x)+d(a,b). \end{array}$

Then ${f_b \geq 0}$. and ${f_b}$ is ${1}$-Lipschitz. For ${a\in A}$, ${f_a =F(a)}$. We have

$\displaystyle \begin{array}{rcl} f_b (x)+f_b (y)&\geq& \inf_{a,\,a'\in A}F(a)(x)+F(a')(y)+d(a,a')\\ &\geq& \inf_{a A}F(a)(x)+F(a)(y)\geq d(x,y) \end{array}$

thus ${f_b \in \Delta_1 (X)}$. Extend ${F}$ to ${B}$ by setting ${F(b)=f_b}$. Then the extended ${F}$ is ${1}$-Lipschitz. $\Box$

Theorem 5 (Isbell)

1. ${E(X)}$ is injective.
2. If ${f:E(X)\rightarrow E(X)}$ is ${1}$-Lipschitz, and fixes ${e(X)}$ pointwise, then ${F}$ is the identity.
3. If ${G:E(X)\rightarrow Y}$ is ${1}$-Lipschitz and ${G\circ e}$ is an isometric embedding, then ${G}$ is an isometric embedding.
4. If ${I:X\rightarrow Y}$ is an isometric embedding and ${Y}$ is injective, then there is an isometric embedding ${G:E(X)\rightarrow Y}$ such that ${G\circ e=I}$.

Proof: 2. ${F(f)(x)=\|F(f)-d_x \|_{\infty}\leq \|f-d_x \|_{\infty}=f(x)}$, so ${F(f)=f}$ by minimality. 3. follows from 2. and 4. follows from 3. $\Box$

2. First examples

2.1. Polyhedral structure on ${E(X)}$, ${X}$ finite

If ${X}$ is bounded, then ${diameter (E(X))\leq diameter(X)}$. If ${X}$ is compact, so is ${E(X)}$ (Arzela-Ascoli).

If ${X}$ is finite, ${E(X)}$ is a polyhedron in ${\ell_{\infty}(X)}$. Note that ${\Delta(X)}$ and ${\Delta_1 (X)}$ are convex, but ${E(X)}$ is not in general. The polyhedral structure can be detected by looking at “equality graphs”. For ${f\in\Delta(X)}$, let ${\mathcal{E}(f)}$ be the set of pairs ${\{x,y\}}$ such that ${f(x)+f(y)=d(x,y)}$. Then ${G(f)=(X,\mathcal{E}(f))}$ is a graph with loops: ${\{x,x\}\in\mathcal{E}(X)}$ iff ${f(x)=0}$. Also

${f\in E(X)}$ iff ${G(f)}$ has no isolated vertices.

Say a graph ${G=(X,\mathcal{E})}$ is admissible if there exists ${f\in E(X)}$ such that ${G=G(f)}$. Every admissible graph corresponds to a polyhedral cell ${P(G)}$ in ${E(X)}$, whose interior points are precisely the functions ${f\in E(X)}$ such that ${G(f)=G}$. ${P(G')}$ is a face of ${P(G)}$ iff ${G'}$ contains ${G}$.

2.2. Dimension of ${E(X)}$

If two functions ${f}$, ${g\in E(X)}$ have the same graph, then for all ${\{v,v'\}\in\mathcal{E}}$, ${f(v)+f(v')=d(v,v')=g(v)+g(v')}$, thus

$\displaystyle \begin{array}{rcl} f(v')-g(v')=-(f(v)-g(v)). \end{array}$

Hence, if there is a path from ${x}$ to ${y}$ in ${G}$ of length ${L}$, then

$\displaystyle \begin{array}{rcl} f(y)-g(y)=(-1)^{L}(f(x)-g(x)). \end{array}$

On connected components of ${G}$ containing an odd cycle, ${f}$ and ${g}$ coincide. On other (even) components, there is exactly one degree of freedom to vary ${f}$ without changing the graph.

Proposition 6 Define the rank ${rk(G)}$ as the number of even components. Then ${\mathrm{dim}(P(G))=rk(G)}$.

Example 1 ${X=K_2}$.

Then the possible graphs are an edge (rank one) and one edge with one loop (rank zero). This produces an interval.

Example 2 ${X=K_3}$.

Then ${E(X)}$ is a tripod. Indeed, admissible graphs of extremal functions can have at most one even component. The complete graph is admissible but odd, producing a vertex. Two-edge admissible graphs contribute three segments. Hinges with a loop contribute three vertices.

The tripod lies in ${\ell_{\infty}^{3}}$ on a triangular face (standard simplex) at the bottom of polyhedron ${\Delta_1}$. It takes infinitely many steps (iterates of ${q}$) to map a constant function ${1/2}$ to ${E(X)}$. It is a bit stupid.

Lee: why don’t you consider the optimal ${t}$ such that ${(1-t)f+tf^*}$ belongs to ${\Delta}$ ?

Example 3 ${X}$ has 4 points with one distance equal to ${2}$ and all other equal to ${1}$ or ${0}$.

The graph with two disjoint edges (one of length ${2}$) is admissible and has rank ${2}$, it contributes a ${2}$-cell, a square sitting diagonally in ${\ell_{\infty}^{2}}$. The resulting polyhedron is the union of the ${2}$-cell with two opposite protruding edges, each of length ${1/2}$.