Notes of Urs Lang’s lecture nr 3

1. Polyhedral structure on ${E(X)}$

From now on, we concentrate on metric spaces whose metric is integer valued (a preparation for the case of finitely generated groups). For simplicity, assume that ${X}$ is countable.

1.1. An approximation to ${E(X)}$

Recall that the equality graph of an extremal function ${f}$ has vertex set ${X}$ and edge set

$\displaystyle \begin{array}{rcl} \mathcal{E}(f)=\{\{x,y\}\,;\, f(x)+f(y)=d(x,y)\}. \end{array}$

Define

$\displaystyle \begin{array}{rcl} E'(X)=\{f\in\Delta(X)\,;\,\forall x,\,\exists y \textrm{ such that }\{x,y\}\in\mathcal{E}(f)\} \end{array}$

For finite metric spaces, ${E(X)=E'(X)}$, but when ${X}$ is infinite, possibly ${E'(f)}$ is a proper subset of ${E(X)}$. Also ${E'(f)}$ need not be injective.

Proposition 1 For all extremal function ${f\in E(X)}$, and all ${m\in{\mathbb N}}$, there exists ${f'\in E'(X)}$ with values in ${\frac{1}{m}{\mathbb Z}}$ such that ${\|f-f'\|_{\infty}\leq\frac{1}{2m}}$.

The strategy is to study ${E'(X)}$, show that it is complete, and conclude that ${E'(X)=E(X)}$.

Proof: By rounding. Define ${f_0}$ as the largest function which is ${\leq f+\frac{1}{2m}}$ with values in ${\frac{1}{m}{\mathbb Z}}$. Then ${f_0 >f-\frac{1}{2m}}$. Check that ${f_0 \in\Delta(X)}$: since

$\displaystyle \begin{array}{rcl} f_0 (x) +f_0 (y)

and ${f_0 (x) +f_0 (y)\in\frac{1}{m}{\mathbb Z}}$, ${f_0 (x) +f_0 (y)\geq d(x,y)}$.

Next idea is to decrease ${f_0 (x)}$ at some points ${x}$ where ${f_0 (x)=f(x)+\frac{1}{2m}}$ to make ${f_0}$ extremal. At other points, ${f_0 (x). By minimality of ${f}$, there exists ${y}$ such that

$\displaystyle \begin{array}{rcl} d(x,y)-f(y)>f_0 (x)-\frac{1}{2m}, \end{array}$

so

$\displaystyle \begin{array}{rcl} f_0 (x) +f_0 (y) \leq f_0 (x) +f(y)+\frac{1}{2m}

so ${f_0 (x) +f_0 (y) \leq d(x,y)}$, i.e. ${\{x,y\}\in\mathcal{E}(f_0)}$.

Next assume that ${f_0 (x_1)=f(x)+\frac{1}{2m}}$ and ${\{x,y\}\notin\mathcal{E}(f_0)}$. Then ${f_0 (x) +f_0 (y) > d(x,y)}$ for all ${y}$, so ${f_0 (x_1) +f_0 (y) \leq d(x,y)+\frac{1}{m}}$. So there is room to decrease ${f_0}$ at ${x_1}$: define

$\displaystyle \begin{array}{rcl} f_1 (x_1):=f_0 (x_1)-\frac{1}{m}=f(x_1)-\frac{1}{2m}, \end{array}$

and, at all other points, ${f_1 (y)=f_0 (y)}$. ${f_1}$ still belongs to ${\Delta(X)}$. As above, it follows that if ${f_1(x), there exists ${y}$ such that ${\{x_1 ,y\}\in\mathcal{E}(f_1)}$. So ${x_1 \in\bigcup \mathcal{E}(f_1)}$.

Iterate the procedure, eventually transfinitely, to get the required approximation. $\Box$

1.2. The cells of ${\mathcal{E}'(X)}$

Definition 2 Call a graph ${G=(X,\mathcal{E})}$ admissible if there exists ${f\in E'(X)}$ such that the equality graph ${G(f)}$ of ${f}$ equals ${G}$. For ${G}$ an admissible graph, define the affine subspace

$\displaystyle \begin{array}{rcl} H(G)=\{g\in {\mathbb R}^X \,;\,G(f) \textrm{ contains }G,\textrm{ i.e. }g(x)+g(y)=d(x,y)\,\forall\{x,y\}\in\mathcal{E}\} \end{array}$

and the convex subset

$\displaystyle \begin{array}{rcl} P(G):=\Delta(X)\cap H(G)=\{g\in H(G)\,;\,g(x)+g(y)\geq d(x,y)\,\forall\{x,y\}\notin\mathcal{E}\} \end{array}$

Note that ${f\in P(G(f))}$.

Recall that if ${g}$, ${h\in H(G)}$, and ${x}$, ${y}$ are connected by a path of length ${L}$ in ${G}$, then g(y)-h(y)=(-1)^L (g(x)-h(x)). (we saw this during the informal description last time, but it follows readily from the definition). It follows that if ${G}$ contains an odd cycle, ${g=h}$. Otherwise, there is one degree of freedom.

Definition 3 The rank ${rk(G)}$ of an admissible graph is the number of even components of ${G}$ (i.e. connected components containing no odd cycle). If ${rk(G)<\infty}$, then ${\|g-h\|_{\infty}}$ is a metric on ${H(G)}$.

Proposition 4 Let ${G}$ be an admissible graph of finite rank ${rk(G)\geq 1}$. Then

1. There exists an affine isometry ${I:H(G)\rightarrow\ell_{\infty}^{n}}$ such that ${I(P(G))}$ is an ${n}$-dimensional compact polytope.
2. The interior of ${P(G)}$ relative to its affine carrier ${H(G)}$ is ${\{g\in E'(X)\,;\, G(g)=G\}}$.
3. The face structure of ${P(G)}$ is the family of all ${P(G')}$ with ${G'}$ admissible and ${G'}$ contains ${G}$.

Proof: 1. Fix an extremal function ${f}$ such that ${G=G(f)}$. Exploit the fact that even components are bipartite. Fix ${x_1 ,\ldots,x_n}$ representing the vertex sets ${[x_1],\ldots,[x_n]}$ of the even components. For every ${k}$, there is a partition ${[x_k]=[x_{k}]_{1} \cup [x_{k}]_{-1}}$ where a point ${y}$ belongs to ${[x_{k}]_{-1}}$ iff there exists a path of odd length from ${x_k}$ to ${y}$. If ${y\in[x_{k}]_{\sigma}}$, ${\sigma=\pm 1}$, then ${f(y)\in{\mathbb Z} +\sigma f(x_k)}$. If ${y}$ belongs to an odd component, then ${f(y)\in{\mathbb Z}-f(y)}$ thus ${f(y)\in\frac{1}{2}{\mathbb Z}}$. Define ${I:H(G)\rightarrow\ell_{\infty}^{n}}$ by

$\displaystyle \begin{array}{rcl} I(g)=(g(x_1)-f(x_1),\ldots,g(x_n)-f(x_n)). \end{array}$

Identity (1) implies that

$\displaystyle \begin{array}{rcl} \|g-f\|_{\infty}=\|I(g)-I(f)\|_{\infty} \end{array}$

so ${I}$ is an isometry.

2. To describe ${I(P(G))}$, define constants

$\displaystyle \begin{array}{rcl} C_{k,\sigma}=\sup\{\frac{d(x,y)-f(y)-f(y)}{2}\,;\,x,\,y\in[x_k]_{\sigma}\}. \end{array}$

For ${x}$, ${y\in [x_k]_{\sigma}}$, ${\{x,y\}\notin\mathcal{E}(f)}$ so ${0>d(x,y)-f(y)-f(y)}$. This number belongs to the discrete set ${{\mathbb Z}-2\sigma f(x_k)}$, so the ${\sup}$ is negative as well. If ${y}$ belongs to an odd cycle, set

$\displaystyle \begin{array}{rcl} \tilde{C}_{k,\sigma}=\sup\{d(x,y)-f(y)-f(y)\,;\,x\in[x_k]_{\sigma},\,y\in\textrm{ odd cycle}\}. \end{array}$

If there are no odd cycles whatsoever, put ${\bar{C}_{k,\sigma}=C_{k,\sigma}}$. Otherwise, set

$\displaystyle \begin{array}{rcl} \bar{C}_{k,\sigma}=\max\{C_{k,\sigma},\tilde{C}_{k,\sigma}\}. \end{array}$

If ${n\geq 2}$, then for ${1\leq k,\ell\leq n}$ and ${\sigma}$, ${\tau\in\pm 1}$,

$\displaystyle \begin{array}{rcl} C^{\ell,\tau}_{k,\sigma}=.... \end{array}$

Claim: ${I(P(G))}$ is the set of all ${f\in\ell_{\infty}^{n}}$ such that

$\displaystyle \begin{array}{rcl} \sigma f_k &\geq& \bar{C}_{k,\sigma}\\ \sigma f_k +\tau f_{\ell}&\geq& C^{\ell,\tau}_{k,\sigma}.\\ \end{array}$

So the number of faces of our polytope is atmost ${2n+\begin{pmatrix}n\\ 2\end{pmatrix}=2n^2}$ faces. I do not know if this upper bound is sometimes achieved.

Proof: of Claim.

$\displaystyle \begin{array}{rcl} 2\sigma f_k = \end{array}$

so ${\sigma f_k \geq C_{k,\sigma}}$ iff ${g(x)+g(y)\geq d(x,y)}$ for all such pairs. And so on… $\Box$

Thats all for the proof of Proposition 4. $\Box$

Now suppose that ${rk(G)}$ is finite for all admissible graphs. It follows that ${\mathcal{P}=\{P(G)\}_{G\,\mathrm{admissible}}}$ is a polyhedral structure on ${E'(X)}$, with ${P(G')}$ a face of ${P(G)}$ iff ${G\subset G'}$.

If ${f\in E'(X)}$ is a vertex of ${\mathcal{P}}$, then ${rk(G(f))=0}$, so ${f(X)\in\frac{1}{2}{\mathbb Z}}$. In particular, edges of ${\mathcal{P}}$ have length in ${\frac{1}{2}{\mathbb Z}}$.

Proposition 5 Suppose in addition that ${X}$ is discretely geodesic, i.e. there is an isometric embedding of an integer interval joining any two points. Then every edge of ${\mathcal{P}}$ has length at most ${2}$ and for every ${n}$, ${\mathcal{P}}$ has only finitely many isometry types of ${n}$-cells.

Proof: Suppose ${G}$ is an admissible graph of rank ${1}$. Let ${x_1}$ be a representative of the only even cycle ${[x_1]}$. Since ${X}$ is discretely geodesic, there exist ${x}$, ${y\in X}$ with ${d(x,y)=1}$ such that ${x\in[x_1]_1}$ and either ${y\in[x_1]_{-1}}$ or ${y}$ does not belong to ${[x_1]}$. Let ${g}$, ${h\in P(G)}$. Then, by (1),

$\displaystyle \begin{array}{rcl} \|g-h\|_{\infty}=|g(x)-h(x)|. \end{array}$

If ${y\in[x_1]_{-1}}$, ${2|g(x)-h(x)|=|g(x)-h(x)-g(y)+h(y)|\leq 2}$. Else ${y\notin[x_1]}$, and it goes similarly. The bound ${2}$ is optimal, as seen from the suspension of a three point set with no edges. $\Box$

1.3. Why do we need such detailed information ?

To deal with hyperbolic groups. The fact that only finitely many configurations occur for cones types guarantees that admissible graphs have finite rank, and so ${E'(X)=E(X)}$.

The cone type trick applies to ${{\mathbb Z}^n}$ as well, and yields the upper bound ${rk(G)\leq 2^{n-1}}$. In fact, ${E({\mathbb Z}^n)=E(\ell_{1}^{n})=\ell_{\infty}^{2^{n-1}}}$.

More generally, the injective hull of a Banach space is again a Banach space, but in an unobvious way. In case of polyhedral norms, one stays within finite dimensional Banach spaces, but not in general. For instance, ${E(\ell_{2}^{n})=L_{\infty}({\mathbb N})}$.