Local matching from finite box counts
A finite family of persistence points records occurrences, so equal point values can appear more than once. If distinct source points are sufficiently separated, two-sided box-count inequalities produce a matching of these occurrences with controlled cost.
Write x : I → ℝ × ℝ and y : J → ℝ × ℝ, where I and J are finite,
and let ε ≥ 0. The function finiteBoxCount x p r counts occurrences in the
closed square of radius r about p, using the maximum metric. Assume that both
families satisfy
whenever r > 0 and the expanded square lies strictly above the diagonal:
2(r+ε) < p₂−p₁. These are counting hypotheses, not assumptions that a matching
exists. The theorem finiteBoxCount_box_le proves the same inequalities for
r = 0 by finite-support stabilization of a shrinking positive radius.
exists_matching_of_separated_box_bounds assumes in addition:
- every source lifetime is greater than 4ε;
- distinct source point values have maximum distance greater than 2ε;
- every target point has birth at most death.
It constructs an OccurrenceMatching I J PEmpty PEmpty of cost at most ε,
matching every source occurrence. Repeated points need no separation from their
other copies. Target occurrences outside the matching have lifetime at most 2ε
and hence diagonal cost at most ε.
For a source value p, the radius-zero forward bound and radius-ε reverse bound show that the target ε-square contains exactly the multiplicity of p. Source separation makes these squares disjoint. Summing their cardinalities gives Hall's inequality for every subset of source occurrences, from which mathlib's finite Hall theorem supplies an injection. Equality of cluster cardinalities forces that injection to cover every target cluster. Finally, the reverse radius-zero bound puts every target of lifetime greater than 2ε in a source cluster. This proves the claimed bound for unmatched targets.
The fixture duplicated_shift_with_short_target checks the box inequalities
directly for two copies of (0,10), two target copies of (1,11), and the extra
target (0,1), with ε = 1. It tests multiplicity, nonzero displacement, and an
additional short interval.
This is the finite local step of Chazal–de Silva–Glisse–Oudot,
The structure and stability of persistence modules, arXiv:1207.3674v3,
Theorem 4.25, Part 2(ii), §4.7. Example 4.26 shows why one pair of box
inequalities does not imply a general matching theorem without these local
hypotheses. The one-parameter family used in Theorem 4.25, the passage from
module rectangle measures to these closed-square
occurrence counts, essential points, and the locally finite extension are not part of
this local theorem. The global result, qTame_bottleneck_le_of_realInterleaving, is proved by a
different route through PersistenceMeasureWindowMatching and finite saturation (see
Rips metric stability); this local theorem by itself asserts
neither full algebraic stability nor a Rips bottleneck bound.
The canonical distance-form theorem,
LocallyFiniteDecoratedDiagram.qTame_bottleneck_le_realInterleavingDistance, takes the
infimum of these finite-saturation bounds over all actual interleavings.