### Wrestling with Tight Spans

#### Posted by Tom Leinster

I’ve been spending some time with Simon Willerton’s paper Tight spans, Isbell completions and semi-tropical modules. In particular, I’ve been trying to understand tight spans.

The tight span of a metric space $A$ is another metric space $T(A)$, in which $A$ naturally embeds. For instance, the tight span of a two-point space is a line segment containing the original two points as its endpoints. Similarly, the tight span of a three-point space is a space shaped like the letter Y, with the original three points at its tips. Because of examples like this, some people like to think of the tight span as a kind of abstract convex hull.

Simon’s paper puts the tight span construction into the context of a categorical construction, Isbell conjugacy. I now understand these things better than I did, but there’s still a lot I don’t get. Here goes.

Simon wrote a blog post summarizing the main points of his paper, but I want to draw attention to slightly different aspects of it than he does. So, much as I recommend that post of his, I’ll make this self-contained.

We begin with Isbell conjugacy. For any small category $A$, there’s an adjunction

$\check{\,\,}: [A^{op}, Set] \leftrightarrows [A, Set]^{op}: \hat{\,\,}$

defined for $F: A^{op} \to Set$$and$b \in A$by</p> <p>$$\check{F}(b) = Hom(F, A(-, b))$$</p> <p>and for$G: A \to Set$and$a \in A$by</p> <p>$$\hat{G}(a) = Hom(G, A(a, -)).$$</p> <p>We call$\check{F}$the <b>(Isbell) conjugate</b> of$F$, and similarly$\hat{G}$the (Isbell) conjugate of$G$. </p> <p>Like any adjunction, it restricts to an equivalence of categories in a canonical way. Specifically, it's an equivalence between</p> <blockquote> <p>the full subcategory of$[A^{op}, Set]$consisting of those objects$F$such that the canonical map$F \to \hat{\check{F}}$is an isomorphism</p> </blockquote> <p>and</p> <blockquote> <p>the full subcategory of$[A, Set]^{op}$consisting of those objects$G$such that the canonical map$G \to \check{\hat{G}}$is an isomorphism.</p> </blockquote> <p>I'll call either of these equivalent categories the <b>reflexive completion</b>$R(A)$of$A$. (Simon called it the Isbell completion, possibly with my encouragement, but "reflexive completion" is more descriptive and I prefer it now.) So, the reflexive completion of a category consists of all the "reflexive" presheaves on it — those canonically isomorphic to their double conjugate.</p> <p>All of this categorical stuff generalizes seamlessly to an enriched context, at least if we work over a complete symmetric monoidal closed category. </p> <p>For example, suppose we take our base category to be the category$Ab$of abelian groups. Let$k$be a field, viewed as a one-object$Ab$-category. Both$[k^{op}, Ab]$and$[k, Ab]$are the category of$k$-vector spaces, and both$\check{\,\,}$and$\hat{\,\,}$are the dual vector space construction. The reflexive completion$R(k)$of$k$is the category of$k$-vector spaces$V$for which the canonical map$V \to V^{\ast\ast}$is an isomorphism — in other words, the finite-dimensional vector spaces.</p> <p>But that's not the example that will matter to us here.</p> <p>We'll be thinking primarily about the case where the base category is the poset$([0, \infty], \geq)$(the reverse of the usual order!) with monoidal structure given by addition. As Lawvere observed long ago, a$[0, \infty]$-category is then a "generalized metric space": a set$A$of points together with a distance function</p> <p>$$d: A \times A \to [0, \infty]$$</p> <p>satisfying the triangle inequality$d(a, b) + d(b, c) \geq d(a, c)$and the equaiton$d(a, a) = 0$. These are looser structures than classical metric spaces, mainly because of the absence of the symmetry axiom$d(a, b) = d(b, a)$. </p> <p>The enriched <i>functors</i> are distance-decreasing maps between metric spaces: those functions$f: A \to B$satisfying$d_B(f(a_1), f(a_2)) \leq d_A(a_1, a_2)$. I'll just call these "maps" of metric spaces.</p> <p>If you work through the details, you'll find that Isbell conjugacy for metric spaces works as follows. Let$A$be a generalized metric space. The conjugate of a map$f: A^{op} \to [0, \infty]$is the map$\check{f}: A \to [0, \infty]$defined by</p> <p>$$\check{f}(b) = sup_{a \in A} max \{ d(a, b) - f(a), 0 \}$$</p> <p>and the conjugate of a map$g: A \to [0, \infty]$is the map$\hat{g}: A^{op} \to [0, \infty]$defined by</p> <p>$$\hat{g}(a) = sup_{b \in A} max \{ d(a, b) - g(b), 0 \}.$$</p> <p>We always have$f \geq \hat{\check{f}}$, and the reflexive completion$R(A)$of$A$consists of all maps$f: A^{op} \to [0, \infty]$such that$f = \hat{\check{f}}$. (Although you could write out an explicit formula for that, I'm not convinced it's much help.) The metric on$R(A)$is the sup metric.</p> <p>All that comes out of the general categorical machinery. </p> <p>However, we can say something more that only makes sense because of the particular base category we're using. </p> <p>As we all know, <i>symmetric</i> metric spaces — the ones we're most used to — are particular interesting. For a symmetric metric space$A$, the distinction between covariant and contravariant functors on$A$vanishes. The two kinds of conjugate,$\hat{\,\,}$and$\check{\,\,}$, are also the same. I'll write${}^\ast$for them both. </p> <p>The reflexive completion$R(A)$consists of the functions$A \to [0, \infty]$that are equal to their <i>double</i> conjugate. But because there is no distinction between covariant and contravariant, we can also consider the functions$A \to [0, \infty]$equal to their <i>single</i> conjugate.</p> <p>The set of such functions is — by definition, if you like — the <b>tight span</b>$T(A)$of$A$. So </p> <p>$$T(A) = \{ f : A \to [0, \infty] \,|\, f = f^\ast \},$$</p> <p>while</p> <p>$$R(A) = \{ f: A \to [0, \infty] \,|\, f = f^{\ast\ast} \}.$$</p> <p>Both come equipped with the sup metric, and both contain$A$as a subspace, via the Yoneda embedding$a \mapsto d(-, a)$. So$A \subseteq T(A) \subseteq R(A)$.</p> <blockquote> <p><b>Example</b> Let$A$be the symmetric metric space consisting of two points distance$D$apart. Its reflexive completion$R(A)$is the set$[0, D] \times [0, D]$with metric$$d((s_1, s_2), (t_1, t_2)) = max \{ t_1 - s_1, t_2 - s_2, 0 \}.$$The Yoneda embedding identifies the two points of$A$with the points$(0, D)$and$(D, 0)$of$R(A)$. The tight span$T(A)$is the straight line between these two points of$R(A)$(a diagonal of the square), which is isometric to the ordinary Euclidean line segment$[0, D]$. </p> </blockquote> <p>As that example shows, the reflexive completion of a space needn't be symmetric, even if the original space was symmetric. On the other hand, it's not too hard to show that the tight span of a space <i>is</i> always symmetric. Simon's <a href="http://www.tac.mta.ca/tac/volumes/28/22/28-22abs.html">Theorem 4.1.1</a> slots everything into place: </p> <blockquote> <p><b>Theorem</b> (Willerton) Let$A$be a symmetric metric space. Then the tight span$T(A)$is the largest symmetric subspace of$R(A)$containing$A$. </p> </blockquote> <p>Here "largest" means that if$B$is another symmetric subspace of$R(A)$containing$A$then$B \subseteq T(A)$. It's not even obvious that there <i>is</i> a largest one. For instance, given any non-symmetric metric space$C$, what's the largest symmetric subspace of$C$? There isn't one, just because every singleton subset of$C$is symmetric. </p> <p>Simon's told the following story before, but I can't resist telling it again. Tight spans have been discovered independently many times over. The first time they were discovered, they were called by the less catchy name of "injective envelope" (because$T(A)$is the smallest injective metric space containing$A$). And the person who made that first discovery? Isbell — who, as far as anyone knows, never noticed that this had anything to do with Isbell conjugacy.</p> <p>Let me finish with something I don't quite understand. </p> <p>Simon's <a href="http://www.tac.mta.ca/tac/volumes/28/22/28-22abs.html">Theorem 3.1.4</a> says the following. Let$A$be a symmetric metric space. (He doesn't assume symmetry, but I will.) Then for any$a \in A$,$p \in R(A)$and$\varepsilon \gt 0$, there exists$b \in A$such that</p> <p>$$d(a, p) + d(p, b) \leq d(a, b) + \varepsilon.$$</p> <p>In other words,$a$,$p$and$b$are almost collinear.</p> <p>A <i>loose</i> paraphrasing of this is that every point in the reflexive completion of$A$is close to being on a geodesic between points of$A$. The theorem does imply this, but it says a lot more. Look at the quantification. We get to <i>choose</i> one end$a$of the not-quite-geodesic, as well as the point$p$in the reflexive completion, and we're guaranteed that if we continue the not-quite-geodesic from$a$on through$p$, then we'll eventually meet another point of$A$(or nearly).</p> <p>Let's get rid of those "not quite"s, and at the same time focus attention on the tight span rather than the reflexive completion. Back in Isbell's original 1964 paper (cited by Simon, in case you want to look it up), it's shown that if$A$is compact then so is its tight span$T(A)$. Of course, Simon's Theorem 3.1.4 applies in particular when$p \in T(A)$. But then compactness of$T(A)$means that we can drop the$\varepsilon$.</p> <p>In other words: let$A$be a compact symmetric metric space. Then for any$a \in A$and$p \in T(A)$, there exists$b \in A$such that</p> <p>$$d(a, p) + d(p, b) = d(a, b).$$</p> <p>So, if you place your pencil at a point of$A$, draw a straight line from it to a point of$T(A)$, and keep going, you'll eventually meet another point of$A$.</p> <p>This leaves me wondering what tight spans of common geometric figures actually look like. </p> <p>For example, take an arc$A$of a circle — any size arc, as long as it's not the whole circle. Embed it in the plane and give it the Euclidean metric. I said originally that the tight span is sometimes thought of as a sort of abstract convex hull, and indeed, the introduction to Simon's paper says that some authors have actually used this name instead of "tight span". But the result I just stated makes this seem highly misleading. It implies that the tight span of$A$is <i>not</i> its convex hull, and indeed, can't be <i>any</i> subspace of the Euclidean plane (unless, perhaps, it's$A$ itself, which I suspect is not the case). But what is it?

A lot of people who use tight spans are doing so in contexts such as combinatorial optimization and phylogenetic analysis where the metric spaces that they start with are finite. So they don’t treat examples such as arcs, circles, triangles, etc. Has anyone ever computed the tight spans of common geometric shapes?

## Re: Wrestling with Tight Spans

There is a passing resemblance between the formula for the Isbell conjugate and the Legendre transform ($f^*(p) = \sup(p\cdot x - f(x))$). Is there anything more than a passing resemblance? The Legendre transform is a certain tropicalization of the Fourier transform, and Simon has discussed connections between the tight span and tropical geometry, so another way to pose my question is whether any of the players has a more-than-passing resemblance to the Fourier transform.