Notes of Urs Lang’s lecture nr 1


Injective hulls

They are used in computer science, in the reconstruction of phylogenetic trees, but not so well known by mathematicians.

Today, I give an expository talk with definitions but no proofs. Proofs will come later on.


1. Injective metric spaces


1.1. Definition


Definition 1 A metric space is injective if every for every metric space {B} and every {A\subset B}, every {1}-Lipschitz map {f:A\rightarrow X} has a {1}-Lipschitz extension {\bar{f}:B\rightarrow X}.


Example 1 The real line is injective.

An observation of Mc Shane and Whitney in 1934. Put {\bar{f}(x)=\inf_{a\in A}f(a)+d(a,b)}.

Example 2 {\ell_{\infty}(I)} is injective for every set {I}.


Example 3 Metric trees are injective.


1.2. Elementary properties


If {X} is injective, then

  1. {X} is complete.
  2. {X} is geodesic.
  3. {X} is contractible. In fact, {X} has a geodesic bicombing, i.e. a family of geodesics {\gamma_{xy}:[0,1]\rightarrow X} such that\displaystyle  \begin{array}{rcl}  d(\gamma_{xy}(t),\gamma_{x'y'}(t))\leq (1-t)d(x,x')+td(y,y'). \end{array}

    (use the Kuratowski embedding, and the distance decreasing retraction of {\ell_{\infty}(X)} onto {X}).

  4. Every triple {x,y,z} spans a geodesic tripod.
  5. {X} admits isoperimetric inequalities of Euclidean type for integral cycles in any dimension (Gromov, Wenger).

Property 3. reminds us of nonpositive curvature. Property 4. sound like strong negative curvature, but with strong non uniqueness of geodesics.


1.3. Elementary characterizations


Proposition 2 (Aronszajn, Panitchpakdi) The following are equivalent:

  1. {X} is injective
  2. {X} is an absolute {1}-Lipschitz retract.
  3. {X} is hyperconvex, i.e. for every collection {B(x_i ,r_i)} such that all {d(x_i ,x_j)\leq r_i +r_j}, the intersection {\bigcap B(x_i ,r_i)} is non empty.


It follows that intersections of balls in injective metrics spaces are injective.


2. Injective hulls


J. R. Isbell 1964, rediscovered by A. Dress in 1984, under the name of tight spans (aka injective injective envelopes,…), [I].


2.1. Definition


Theorem 3 (Isbell, Dress) For every metric space {X}, there exists an injective metric space {E(X)} and an isometric embedding {X\rightarrow E(X)} with the following universal property: every isometric embedding of {X} in a injective metric space {Y} factors via {X\rightarrow E(X)}. Let us call it the injective hull of {X}.


Proof: The proof provides an explicit construction. Let {\Delta(X)} be the space of functions {f:X\rightarrow {\mathbb R}} such that {f(x)+f(y)\geq d(x,y)}. Distances to points belong to {\delta(X)}. Let {E(X)} be the set of minimal elements of the partially ordered set {\Delta(X)} (akaextremal functions). Every {f\in E(X)} is {1}-Lipschitz. If {f}, {g\in E(X)}, then {|f-g|} is bounded, so {\sup|f-g|} defines a metric {d_{\infty}} on {E(X)}. Distances to points belong to {E(X)} and this gives the isometric embedding of {X} in {E(X)}. Note that {d_{\infty}(f,d_y)=f(y)} so one can think of extremal functions are distance functions to themselves, i.e. points which do not belong to {X}. \Box

Example 4 If {X} has two points, {E(X)} is an interval.


Example 5 If {X} has three points, {E(X)} is a tripod.


Example 6 If {X} has four points, {E(X)} is a rectangle sitting diagonally in {\ell_{\infty}^{2}} with antennas sticking out.


Example 7 If {X} is finite, {E(X)} is a polyhedron made of finitely many cells isometric to polytopes of {\ell_{\infty}^{k}}, of various dimensions {k\leq |X|/2}.


Example 8 If {X} is the {n}-cycle, {\mathrm{dim}\,E(X)=\lfloor \frac{n}{2} \rfloor}.


2.2. Injective hulls and phylogenetic trees


Start be a finite simplicial tree. One can reconstruct the tree from the metric induced on terminal vertices. Indeed, the tree is the injective hull of its leaves. Assume a metric is given on a finite set. This metric is expected to arise from a tree, with some noise. Compute the {1}-skeleton of the injective hull, this is a good approximation of a tree (Andreas Dress and collaborators).


3. Hyperbolic spaces and groups


Definition 4 (Gromov) Let {X} be a geodesic metric space. {X} is {\delta}-hyperbolic if every triangle has a map to a tripod such that inverse images of points have diameters {\leq \delta}.


Theorem 5 (Lang 2004) If {X} is {\delta}-hyperbolic, then {E(X)} is a {\delta}-neighborhood of {X}. In particular, {E(X)} is hyperbolic.

By contrast, the injective hull of Euclidean plane is {\ell_{\infty}}.

Let {\Gamma} be a finitely generated group. Fix a word metric {d_S}. Then {\Gamma} acts isometrically on {E(\Gamma_S)}. The actions is proper in the following weak sense: for every bounded set {B\subset E(\Gamma_S)}, the set of {\gamma\in\Gamma} such that {\gamma B\cap B\not=\emptyset} is finite. It is co-bounded.

Theorem 6 (Lang, Moezzi 2010) Let {\Gamma} be a hyperbolic group. Then {E(\Gamma_S)} is a locally finite polyhedral complex with finitely many isometry types of {\ell_{\infty}^{k}} celles, and {\Gamma} acts properly and cocompactly on {E(\Gamma_S)} by cellular isometries.

In other words, there is a nice model of {K(\Gamma,1)}. It has nonpositive curvature features, but it is not CAT{(0)}. If it is {2}-dimensional, it can be remetrized to be CAT{(0)}.

Proof: For {p\in \Gamma}, define

\displaystyle  \begin{array}{rcl}  cone(p)\leq\{p'\in \Gamma\,;\, d_S (p,e)+d_S (e,p')=d_S (p,p')\}. \end{array}

Cannon discovered that hyperbolic groups have finitely many cones. This gives the upper bound {\mathrm{dim}\,E(\Gamma_S)\leq \frac{1}{2}|B(z,2\delta +1)|}. I believe that the injective hull has dimension smaller that Rips’ complex (by a factor of {2}). \Box


4. Fixed point theorems


Theorem 7 (Lang) Let {X} be an injective metric space. Let {\Lambda} be a group of isometries of {X}.

  1. If {\Lambda} has bounded orbits, then {Fix(\Lambda)} is non empty.
  2. If {Fix(\Lambda)} is non empty, {Fix(\Lambda)} is injective and hence contractible.


Corollary 8 Let {E(\Gamma_S)^1} be the first barycentric subdivision of {E(\Gamma_S)}. If {\Gamma} is a hyperbolic group, then {E(\Gamma_S)^1} is a model for the classifying space {\underline{E}\Gamma} for proper actions of {\Gamma}.


Next time, I will give more details and tell more about injective hulls of discrete metric spaces.

Krauthgamer: how does injective hull behave with respect to quasiisometries ? Answer: It is {4}-Lipschitz with respect to Gromov-Hausdorff distance.

Krauthgamer: what about the endpoint set of a tree ?




[I] Isbell, J. R.; Six theorems about injective metric spaces. Comment. Math. Helv. 39 (1964) 65–76.



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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s