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}



\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}


\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}.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s