The extended interleaving distance
Definition
Let C be any category and F G : OpenInterval ⥤ C precosheaves on the interval category.
The interleaving distance is the extended infimum
interleavingDistance F G = ⨅ (ε : ℝ≥0) (_ : Nonempty (Interleaving ε F G)), (ε : ℝ≥0∞)
of the nonnegative parameters admitting an ε-interleaving, with values in [0, ∞]. The
infimum of the empty set is ⊤, so the distance is ⊤ exactly when no interleaving exists at
any parameter (interleavingDistance_eq_top_iff). An explicit ε-interleaving bounds the
distance by ε (Interleaving.interleavingDistance_le, interleavingDistance_le_of_nonempty).
The infimum is characterized by its lower-envelope property (le_interleavingDistance_iff) and
by approximation from above (interleavingDistance_lt_iff), without assuming that it is
attained.
The distance is a plain function. No EDist, PseudoEMetricSpace or MetricSpace instance
is installed on OpenInterval ⥤ C.
Laws
- Zero. A
0-interleaving gives distance0(Interleaving.interleavingDistance_eq_zero). HenceinterleavingDistance F F = 0(interleavingDistance_self), and isomorphic precosheaves are at distance0(interleavingDistance_eq_zero_of_iso). - Symmetry.
interleavingDistance_comm, sinceInterleaving.symmswaps the witnesses. - Triangle inequality.
interleavingDistance_triangle. Anε-interleaving ofF, Gand aδ-interleaving ofG, Hcompose to an(ε + δ)-interleaving ofF, H, so the distance ofF, His at most the double infimum ofε + δover witnessed pairs. Addition distributes over infima inℝ≥0∞for every index type, including an empty one, where both sides are⊤. No case split on infinite summands and no attainment are needed. - Isomorphism invariance.
interleavingDistance_congr: natural isomorphismsF ≅ F'andG ≅ G'giveinterleavingDistance F G = interleavingDistance F' G'. Each isomorphism is a0-interleaving, and composing with it does not increase the parameter. - Zero distance.
interleavingDistance_eq_zero_iff: the distance is0exactly when anε-interleaving exists for everyε > 0. In general this does not give a0-interleaving, so zero distance does not imply isomorphism (point_closure_distance). - Smoothing. Smoothing is nonexpansive: the distance of
(smoothing ε).obj Fand(smoothing ε).obj Gis at most that ofF, G(interleavingDistance_smoothing_le), since an interleaving ofF, Gsmooths to one of the same parameter. A precosheaf is withinεof its smoothing (interleavingDistance_smoothing_self_le).
Uniform perturbation
For continuous f g : C(X, ℝ) on the same space with ∀ x, |f x - g x| ≤ ε, the explicit
perturbationInterleaving gives
interleavingDistance (intervalComponents f) (intervalComponents g) ≤ ε
(interleavingDistance_intervalComponents_le). By nonexpansiveness the same bound holds after
smoothing both sides by any δ (interleavingDistance_smoothing_intervalComponents_le). These
two theorems take the pointwise hypothesis and form no supremum of |f - g|; the bound by the
supremum distance itself is stated in the next section. These corollaries live in a separate
module, so the distance core depends only on the interleaving and smoothing API.
Supremum distance
For arbitrary f g : X → ℝ, the supremum distance ‖f − g‖_∞ is mathlib's extended distance
on the type X →ᵤ ℝ of functions with the uniform structure. Its real-valued presentation is
edist (UniformFun.ofFun f) (UniformFun.ofFun g) = ⨆ x, ENNReal.ofReal |f x - g x|
(edist_uniformFun_ofFun_eq_iSup), with values in [0, ∞]. An unbounded difference has
distance ⊤ (for example edist_id_twiceId_eq_top); no boundedness is assumed and no finite
real supremum is formed. The zero, symmetry and triangle laws are those of mathlib's
PseudoEMetricSpace (X →ᵤ ℝ) instance; the library adds no wrapper, structure or instance.
For ε : ℝ≥0 the distance is at most ε exactly when ∀ x, |f x - g x| ≤ ε
(edist_uniformFun_ofFun_le_coe_iff).
For continuous f g : C(X, ℝ) on any topological space X,
interleavingDistance (intervalComponents f) (intervalComponents g) ≤
edist (UniformFun.ofFun ⇑f) (UniformFun.ofFun ⇑g)
(interleavingDistance_intervalComponents_le_edist). No compactness, boundedness, finiteness or
nonemptiness of X is assumed. If the right side is ⊤ the bound is trivial. Otherwise the
right side is the coercion of its toNNReal, and the finite-bound characterization turns it
into the pointwise hypothesis of interleavingDistance_intervalComponents_le. The same bound
holds after smoothing both sides by any δ
(interleavingDistance_smoothing_intervalComponents_le_edist). These theorems live in their own
module, which adds the import of mathlib's uniform-convergence distance.
The fixtures cover four cases.
- Empty domain. Both sides are
0: the supremum over an empty domain is0, and the left side follows from the theorem (stability_of_isEmpty). - Unbounded difference. For
idandx ↦ 2xonℝthe supremum distance is⊤(edist_id_twiceId_eq_top), so the theorem is the trivial bound, and noε : ℝ≥0satisfies the pointwise hypothesis. - Constant translation. For
x ↦ f x + cthe theorem gives distance at most|c|on every domain (interleavingDistance_heightShift_le). The supremum distance is exactly|c|on a nonempty domain (edist_heightShift). For the constant functions0andcon a one-point domain both sides equal|c|, by the sharpness of the constant translation (stability_const_eq). No optimality of the bound on other domains is claimed. - Equal heights. Both sides are
0(stability_self).
Fixtures
All fixtures are at C := Type.
- Zero distance without isomorphism. The precosheaves
I ↦ {0 ∈ I}andI ↦ {0 ∈ closure I}areε-interleaved for everyε > 0, so their distance is0. They are not0-interleaved and hence not isomorphic (point_closure_distance). - Infinite distance. The constant empty precosheaf and the constant one-point precosheaf
admit no interleaving: a reverse witness would send the point to the empty set at the whole
line. Their distance is
⊤(const_empty_const_unit_distance). - Exact finite distance. The point precosheaves
I ↦ {0 ∈ I}andI ↦ {1 ∈ I}are at distance exactly1(point_distance_eq_one). The upper bound is the explicit1-interleaving. Forε < 1andr = (1 - ε) / 2, a witness would send0 ∈ (-r, r)intothicken ε (-r, r) = (-r - ε, r + ε), which does not contain1becauser + ε = (1 + ε) / 2 < 1.
Cardinality obstructions
For F G : OpenInterval ⥤ Type v, an ε-interleaving i and an interval I, the restriction
F(I) → F(T_ε T_ε I) equals ψ_(T_ε I) ∘ φ_I. Its range therefore lies in the range of
ψ_(T_ε I) (Interleaving.range_map_subset_range_ψ), and
Nat.card (range (F.map (I ⟶ T_ε T_ε I))) ≤ Nat.card (G.obj (T_ε I))
when G(T_ε I) is finite (Interleaving.card_range_map_le; card_range_map_add_le for the
restriction to T_(ε+ε) I). If the restriction is injective, then φ_I is injective
(Interleaving.φ_app_injective), F(I) is finite and Nat.card (F I) ≤ Nat.card (G (T_ε I))
(Interleaving.finite_of_injective, Interleaving.card_le_of_injective).
A strict reverse inequality excludes every ε-interleaving: in the range form
(Interleaving.isEmpty_of_card_lt_card_range) and in the injective form
(Interleaving.isEmpty_of_injective_of_card_lt). If for every ε with ε < r some I has an
injective restriction, a finite value G(T_ε I) and Nat.card (G (T_ε I)) < Nat.card (F I), then
r ≤ interleavingDistance F G (le_interleavingDistance_of_forall_exists_card_lt);
le_interleavingDistance_of_forall_exists_card_lt_symm places the obstruction on the second
argument. At ⊤, every interleaving gives F(⊤) ≃ G(⊤) (Interleaving.topEquiv), so
Nat.card (F ⊤) ≠ Nat.card (G ⊤) gives distance ⊤ (interleavingDistance_eq_top_of_card_ne;
RGraph.geometricInterleavingDistance_eq_top_of_card_ne for graph objects).
Nat.card of an infinite type is 0, so these bounds assume finiteness of the target value where
they use it, and the ⊤ form gives nothing when both top values are infinite. The injectivity
hypothesis cannot be dropped from the injective form; the Merge-height change paragraph of
reeb-graph-pl.md § Source correspondence has a graph-PL pair with the counts 2 and 1 and an
interleaving (mergeY_injective_needed in TDA/Mapper/GraphPLReebMergeHeightExamples.lean).
The fixtures in TDA/Reeb/InterleavingCardinalityExamples.lean recover the distance 1 of the
point precosheaves at 0 and 1 from the counts 1 and 0 (point_distance_eq_one_of_card),
the nonempty-against-empty obstruction for finite F(I) from the range form
(isEmpty_of_nonempty_of_isEmpty_of_finite), and the distance ⊤ between an empty and a
nonempty graph object with finitely many top components
(geometricInterleavingDistance_eq_top_of_isEmpty_of_nonempty_of_card). These are library
statements; no numbered result of de Silva, Munch and Patel states them.
Source correspondence
de Silva, Munch and Patel, Categorified Reeb Graphs, Definition 4.4, define the interleaving
distance of set-valued pre-cosheaves on Int as the infimum of the parameters admitting an
interleaving, with the infimum of the empty set equal to ∞. Proposition 4.5 states that it is
an extended pseudometric with values in [0, ∞]: symmetric, satisfying the triangle inequality,
and zero on equal arguments. Its proof composes witnesses for the triangle inequality.
Theorem 4.6(i) bounds the distance of the component cosheaves of (X, f) and (X, g) by
‖f − g‖_∞, and Proposition 4.17 states that smoothing is a contraction.
interleavingDistanceis Definition 4.4 for an arbitrary target categoryC; the source's case isC := Type. Admitting∅, rays andℝas intervals and takingε : ℝ≥0are choices of the library.- The pseudometric laws of Proposition 4.5 are
interleavingDistance_self,interleavingDistance_commandinterleavingDistance_triangle. Isomorphism invariance is stated separately. interleavingDistance_intervalComponents_le_edistis Theorem 4.6(i) in its literal form, with‖f − g‖_∞mathlib's extended supremum distance, which may be∞.interleavingDistance_intervalComponents_leis the same theorem with the pointwise hypothesis, which is equivalent to‖f − g‖_∞ ≤ ε(edist_uniformFun_ofFun_le_coe_iff). Theorem 4.6(ii) is not addressed.- Proposition 4.8 of the source states that zero Reeb distance implies isomorphism for ℝ-graphs, through their constructible cosheaves. No such inference is made here for arbitrary precosheaves.
Source: de Silva, Munch and Patel, Categorified Reeb Graphs.