Properties of Interleavings

Now let \(\mathbf{C}\) be a strict \(D\)-category with smoothing functor \(\mathcal{S}\) and let \(A\) and \(B\) be objects of \(\mathbf{C}\). We aim to provide some useful properties about interleavings in \(\mathbf{C}\).

  • Lemma (Monotonicity). For \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) let \(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and \(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) be an \((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\). Now suppose we have \(\mathbf{c} \in D\) with \(\mathbf{a} \preceq \mathbf{c}\). Then \(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B \circ \varphi\) and \(\psi\) form an \((\mathbf{c}, \mathbf{b})\)-interleaving of \(A\) and \(B\). Completely analogously \(\mathcal{S}(\mathbf{b} \preceq \mathbf{d})_A \circ \psi\) and \(\varphi\) yield an \((\mathbf{a}, \mathbf{d})\)-interleaving for any \(\mathbf{d} \in D\) with \(\mathbf{b} \preceq \mathbf{d}\).

  • Proof. We consider the diagram \[ \xymatrix@C+=6pc@R+=4pc{ A \ar[r]_{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_A} \ar[dr]_{\varphi} \ar@/^2pc/[rr]^{ \mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{b})_A } & \mathcal{S}(\mathbf{a} + \mathbf{b})(A) \ar[r]_{ \mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b})_A } & \mathcal{S}(\mathbf{c} + \mathbf{b})(A) \\ & \mathcal{S}(\mathbf{a})(B) \ar[u]_{\mathcal{S}(\mathbf{a})(\psi)} \ar[r]_{\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B} & \mathcal{S}(\mathbf{c})(B) . \ar[u]_{\mathcal{S}(\mathbf{c})(\psi)} } \] The upper triangle commutes because \(\mathcal{S}\) is a functor and the triangle on the left commutes by assumption. Further we have \(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{c}) \circ \mathcal{S}(\mathbf{b})\), since \(\mathcal{S}\) is strict monoidal and thus the square commutes as \(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})\) is a natural transformation. Since all the inner triangles and the square commute in the above diagram, the outer triangle commutes as well. The other triangle, for \(\mathcal{S}(\mathbf{a} \preceq \mathbf{c})_B \circ \varphi\) and \(\psi\) to be an interleaving, also commutes, because we have \(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{c} + \mathbf{b})_B \circ \mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_B = \mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{b})_B\).

  1. Corollary. Let \(\mathcal{I}\) be the set of all \((\mathbf{a}, \mathbf{b}) \in \mathcal{D}\) such that \(A\) and \(B\) are \((\mathbf{a}, \mathbf{b})\)-interleaved. Further let \(\mathcal{I}' := \mathcal{I} \cap \triangledown\) and \(\mathcal{I}'' := \mathcal{I} \cap \blacktriangledown\). Then we have \(\mu_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}')\) and \(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma)(\mathcal{I}') = \inf \epsilon (\mathcal{I}'')\).

  • Proof. First we note that \(\mathcal{I}' \subseteq \delta(\mathcal{I})\), since \(\delta |_{\triangledown} = {\operatorname{id}}_{\triangledown}\). By the previous lemma we also have \(\mathcal{I}' \supseteq \delta(\mathcal{I})\), hence \(\mathcal{I}' = \delta(\mathcal{I})\). This implies \(\mu_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}')\) and \(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma)(\mathcal{I}')\). Similarly we have \(\mathcal{I}'' = \gamma(\mathcal{I}')\) and thus \(M_{\mathcal{S}} (A, B) = \inf \epsilon (\mathcal{I}'')\).

We will now use this corollary to give more concise descriptions of the interleaving distances. The reason we didn’t define the interleaving distances with these more concise descriptions in the first place is that we believe, having those additional interleavings around, can help with the computation of the interleaving distances. Now suppose \((a, b; c, d) \in \triangledown\), then \((a, b; c, d) = (-d, b; -b, d)\). Thus we have the bijection \[ \Phi \colon \triangledown \rightarrow D^{\perp}, (a, b; c, d) \mapsto (d, b) \] with inverse \[ \Psi \colon D^{\perp} \rightarrow \triangledown, (a, b) \mapsto (-a, b; -b, a) . \]

  • Definition. For \((a, b) \in D^{\perp}\) an \((a, b)\)-interleaving of \(A\) and \(B\) is a \((-a, b; -b, a)\)-interleaving of \(A\) and \(B\).

    If there is an \((a, b)\)-interleaving of \(A\) and \(B\), we say \(A\) and \(B\) are \((a, b)\)-interleaved.

With this definition we get a corollary to the previous corollary.

  1. Corollary. Let \(\mathcal{J}\) be the set of all \((a, b) \in D^{\perp}\) such that \(A\) and \(B\) are \((a, b)\)-interleaved, then \(\mu_{\mathcal{S}} (A, B) = \inf \epsilon' (\mathcal{J})\) and \(M_{\mathcal{S}} (A, B) = \inf \epsilon'' (\mathcal{J})\).

  • Proof. Let \(\mathcal{I}'\) be as in the previous corollary. By the above observations we have \(\mathcal{I}' = \Psi(J)\), thus in conjunction with the previous corollary \(\mu_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \Psi)(\mathcal{J})\) and \(M_{\mathcal{S}} (A, B) = \inf (\epsilon \circ \gamma \circ \Psi)(\mathcal{J})\). Now let \((a, b) \in D^{\perp}\) and \(\varepsilon = \max \{a, b\}\), then we have \((\epsilon \circ \Psi)((a, b)) = \epsilon (-a, b; -b, a) = \frac{1}{2}(b + a) = \epsilon' (a, b)\) and \[ \begin{split} (\epsilon \circ \gamma \circ \Psi)(a, b) & = (\epsilon \circ \gamma)(-a, b; -b, a) \\ & = \epsilon (-\varepsilon, \varepsilon; -\varepsilon, \varepsilon) \\ & = \varepsilon = \max \{a, b\} = \epsilon'' (a, b) . \end{split} \]

We further simplify the absolute interleaving distance of \(A\) and \(B\).

  • Defintion (\(\varepsilon\)-Interleaving). For \(\varepsilon \geq 0\) an \(\varepsilon\)-interleaving of \(A\) and \(B\) is an \((\varepsilon, \varepsilon)\)-interleaving of \(A\) and \(B\).

    If there is an \(\varepsilon\)-interleaving of \(A\) and \(B\), we say \(A\) and \(B\) are \(\varepsilon\)-interleaved.

Now an \((\varepsilon, \varepsilon)\)-interleaving of \(A\) and \(B\) is just a \((-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)\)-interleaving. Further we have \(\epsilon ((-\varepsilon, \varepsilon; -\varepsilon, \varepsilon)) = \varepsilon\). And as noted earlier \(\epsilon |_{\blacktriangledown}\) is a bijection. Thus we have yet another corollary to corollary 11.

  1. Corollary. Let \(\mathcal{V}\) be the set of all \(\varepsilon \geq 0\) such that \(A\) and \(B\) are \(\varepsilon\)-interleaved. Then \(M_{\mathcal{S}} (A, B) = \inf \mathcal{V}\).

  • Proof. Let \(\mathcal{I}''\) be as in the corollary 11. By the above observations we have \(\mathcal{I}'' = (\epsilon |_{\blacktriangledown})^{-1} (\mathcal{V})\). In conjunction with the corollary 11 we get \(M_{\mathcal{S}} (A, B) = \inf \epsilon \big((\epsilon |_{\blacktriangledown})^{-1} (\mathcal{V})\big) = \inf \mathcal{V} .\)

Next we proof a type of triangle inequality for both interleaving distances. To this end let \(C\) be another object of \(\mathbf{C}\).

  • Lemma. Let \((\mathbf{a}, \mathbf{b}), (\mathbf{c}, \mathbf{d}) \in \mathcal{D}\). Further let \(\varphi \colon A \rightarrow \mathcal{S}(\mathbf{a})(B)\) and \(\psi \colon B \rightarrow \mathcal{S}(\mathbf{b})(A)\) be an \((\mathbf{a}, \mathbf{b})\)-interleaving of \(A\) and \(B\) and let \(\varphi' \colon B \rightarrow \mathcal{S}(\mathbf{c})(C)\) and \(\psi' \colon C \rightarrow \mathcal{S}(\mathbf{d})(B)\) be a \((\mathbf{c}, \mathbf{d})\)-interleaving of \(B\) and \(C\). Then \(\mathcal{S}(\mathbf{a})(\varphi') \circ \varphi\) and \(\mathcal{S}(\mathbf{d})(\psi) \circ \psi'\) form an \((\mathbf{a} + \mathbf{c}, \mathbf{b} + \mathbf{d})\)-interleaving of \(A\) and \(C\).

  • Proof. We consider the diagram \[ \xymatrix@C+=6pc@R+=4pc{ A \ar[r]_{\mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b})_A} \ar[dr]_{\varphi} \ar@/^2pc/[rr]^{ \mathcal{S}(\mathbf{o} \preceq \mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})_A } & \mathcal{S}(\mathbf{a} + \mathbf{b})(A) \ar[r]_{ \mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})_A \quad } & \mathcal{S}(\mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d})(A) \\ & \mathcal{S}(\mathbf{a})(B) \ar[u]_{\mathcal{S}(\mathbf{a})(\psi)} \ar[r]_{ \mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d})_B \quad } \ar[dr]_{\mathcal{S}(\mathbf{a})(\varphi')} & \mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(B) \ar[u]_{\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(\psi)} \\ & & \mathcal{S}(\mathbf{a} + \mathbf{c})(C) . \ar[u]_{\mathcal{S}(\mathbf{a} + \mathbf{c})(\psi')} } \] Now the upper triangle commute because \(\mathcal{S}\) is a functor and the triangle on the left commutes by assumption. Further we have \(\mathcal{S}(\mathbf{a}) \circ \mathcal{S}(\mathbf{o} \preceq \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d})\), since \(\mathcal{S}\) is strict monoidal and thus the lower triangle commutes. For the square to commute, we observe that \(\mathcal{S}(\mathbf{a} + \mathbf{b} \preceq \mathbf{a} + \mathbf{b} + \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} \preceq \mathbf{a} + \mathbf{c} + \mathbf{d}) \circ \mathcal{S}(\mathbf{b})\), again because \(\mathcal{S}\) is strict monoidal. Since all inner triangles and the square commute in the above diagram, the outer triangle commutes as well. Now \(\mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d}) = \mathcal{S}(\mathbf{a} + \mathbf{c}) \circ \mathcal{S}(\mathbf{d})\) once again because \(\mathcal{S}\) is strict monoidal, hence \[ \begin{split} \mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}( \mathbf{d})(\psi) \circ \psi' ) & = \mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\mathbf{d})(\psi)) \circ \mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\psi') \\ & = \mathcal{S}(\mathbf{a} + \mathbf{c} + \mathbf{d})(\psi) \circ \mathcal{S}(\mathbf{a} + \mathbf{c})(\mathcal{S}(\psi') . \end{split} \] If we now consider the large triangle on it’s own and we substitute the two vertical maps on the right with the left hand side of the previous equation, then we obtain the first of the two triangles for \(\mathcal{S}(\mathbf{a})(\varphi') \circ \varphi\) and \(\mathcal{S}(\mathbf{d})(\psi) \circ \psi'\) to be an interleaving. The proof that the second triangle commutes is completely analogous.

  1. Corollary (Triangle Inequality). We have \[ M_{\mathcal{S}} (A, C) \leq M_{\mathcal{S}} (A, B) + M_{\mathcal{S}} (B, C) \] and \[ \mu_{\mathcal{S}} (A, C) \leq \mu_{\mathcal{S}} (A, B) + \mu_{\mathcal{S}} (B, C) . \]