pith. sign in

arxiv: 2509.24233 · v2 · submitted 2025-09-29 · 🧮 math.AT · cs.CG

Interleaving Distance as a Galois-Edit Distance

Woojin Kim , Won Seong This is my paper

Pith reviewed 2026-05-18 13:04 UTC · model grok-4.3

classification 🧮 math.AT cs.CG
keywords interleaving distanceGalois-edit distancepersistence modulesmulti-parameter persistencefree presentationsbottleneck stabilitypersistent homologytopological data analysis
0
0 comments X

The pith

The interleaving distance on persistence modules equals a Galois-edit distance via free presentations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the interleaving distance between finitely presented single- and multi-parameter persistence modules can be rewritten as a Galois-edit distance. It does so by linking the interleaving distance to free presentations of the modules and then using the resulting Galois connection to define the edit operations. A reader would care because this gives a concrete way to import ideas from string comparison into topological data analysis and supplies a fresh proof of the bottleneck stability theorem for persistence modules.

Core claim

The interleaving distance on finitely presented single- and multi-parameter persistence modules can be formulated as a Galois-edit distance. The key lies in clarifying a connection between the Galois connection and the interleaving distance, via the established relation between the interleaving distance and free presentations of persistence modules. As an application of the Galois-edit formulation, an alternative proof of the bottleneck stability theorem is presented.

What carries the argument

The Galois-edit distance, obtained by combining the Galois connection induced by free presentations of persistence modules with edit operations that measure the cost of interleaving shifts.

If this is right

  • New perspectives on the interleaving distance become available through the language of edit distances.
  • Stability properties of invariants for multi-parameter persistence modules can be studied using the Galois-edit formulation.
  • An alternative proof of the bottleneck stability theorem is obtained directly from the Galois-edit representation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Algorithms developed for computing string edit distances might be adapted to calculate interleaving distances in practice.
  • The reformulation could suggest new ways to compare multi-parameter modules that avoid direct computation of interleavings.
  • Connections between persistence theory and classical metric geometry on posets may become easier to explore.

Load-bearing premise

The known relation between interleaving distance and free presentations of persistence modules continues to hold and can be used to define a Galois connection.

What would settle it

A pair of finitely presented persistence modules whose interleaving distance differs from the Galois-edit distance computed from their free presentations.

read the original abstract

The concept of edit distance, which dates back to the 1960s in the context of comparing word strings, has since found numerous applications with various adaptations in computer science, computational biology, and applied topology. By contrast, the interleaving distance, introduced in the 2000s within the study of persistent homology, has become a foundational metric in topological data analysis. In this work, we show that the interleaving distance on finitely presented single- and multi-parameter persistence modules can be formulated as a so-called Galois-edit distance. The key lies in clarifying a connection between the Galois connection and the interleaving distance, via the established relation between the interleaving distance and free presentations of persistence modules. In addition to offering new perspectives on the interleaving distance, we expect that our findings will facilitate the study of stability properties of invariants for multi-parameter persistence modules. As an application of the Galois-edit formulation of the interleaving distance, we present an alternative proof of the well-known bottleneck stability theorem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims that the interleaving distance on finitely presented single- and multi-parameter persistence modules equals a Galois-edit distance. This equivalence is obtained by using the known relation between interleaving distance and free presentations of persistence modules to induce a Galois-edit distance whose value coincides with the interleaving distance. An alternative proof of the bottleneck stability theorem is then derived directly from the Galois-edit formulation.

Significance. If the central equivalence holds, the work supplies a new perspective on the interleaving distance by connecting it to edit-distance concepts via Galois connections. This may help clarify stability questions for multi-parameter persistence invariants. The alternative proof of the bottleneck theorem avoids circular appeal to the original stability result and rests on an established prior correspondence rather than new parameters or ad-hoc constructions; these are genuine strengths.

minor comments (2)
  1. The abstract introduces the term 'Galois-edit distance' without a one-sentence definition or forward reference to its precise definition in the text; a brief clarifying phrase would improve readability for readers outside the immediate subfield.
  2. The manuscript should add an explicit sentence in the introduction or the section containing the main theorem stating that the Galois-edit distance is shown to coincide with the interleaving distance by direct comparison of their definitions on free presentations.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of the manuscript, as well as for recommending minor revision. We are pleased that the referee highlights the new perspective on interleaving distance via Galois connections and the non-circular alternative proof of the bottleneck stability theorem as genuine strengths. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation rests on external established relation

full rationale

The manuscript's central construction formulates the interleaving distance as a Galois-edit distance by invoking the established (prior) relation between interleaving distance and free presentations of finitely presented persistence modules, then showing that this induces a Galois-edit distance whose value coincides with the interleaving distance. The alternative proof of the bottleneck stability theorem is obtained directly from the Galois-edit formulation without circular appeal to the original stability result. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided derivation chain; the argument is self-contained against the cited external correspondence.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes standard background results from persistent homology and order theory but does not introduce new free parameters, invented entities, or ad-hoc axioms beyond those already established in the field.

axioms (2)
  • standard math The interleaving distance is related to free presentations of persistence modules
    This relation is cited as already established in prior work on persistence modules.
  • domain assumption Galois connections can be used to define an edit distance on the relevant category
    The paper assumes this connection can be clarified from the free-presentation relation.

pith-pipeline@v0.9.0 · 5699 in / 1264 out tokens · 47337 ms · 2026-05-18T13:04:52.196126+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 3 internal anchors

  1. [1]

    Quasi-universality of reeb graph distances

    Ulrich Bauer, H ˚avard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-universality of reeb graph distances. In38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl–Leibniz-Zentrum f¨ur Informatik, 2022

    work page 2022

  2. [2]

    Tight quasi-universality of reeb graph distances.Journal of Applied and Computational Topology, 9(1):7, 2025

    Ulrich Bauer, H ˚avard Bakke Bjerkevik, and Benedikt Fluhr. Tight quasi-universality of reeb graph distances.Journal of Applied and Computational Topology, 9(1):7, 2025. 17

    work page 2025

  3. [3]

    An edit distance for reeb graphs

    Ulrich Bauer, Barbara Di Fabio, Claudia Landi, et al. An edit distance for reeb graphs. InEuro- graphics Workshop on 3D Object Retrieval, pages 27–34. Eurographics Association, 2016

    work page 2016

  4. [4]

    The reeb graph edit distance is universal

    Ulrich Bauer, Claudia Landi, and Facundo M ´emoli. The reeb graph edit distance is universal. Foundations of Computational Mathematics, 21(5):1441–1464, 2021

    work page 2021

  5. [5]

    Induced matchings and the algebraic stability of persistence barcodes.Journal of Computational Geometry, 6(2):162–191, 2015

    Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes.Journal of Computational Geometry, 6(2):162–191, 2015

    work page 2015

  6. [6]

    Computing the interleav- ing distance is NP-hard.Foundations of Computational Mathematics, 20(5):1237–1271, 2020

    H ˚avard Bakke Bjerkevik, Magnus Bakke Botnan, and Michael Kerber. Computing the interleav- ing distance is NP-hard.Foundations of Computational Mathematics, 20(5):1237–1271, 2020

    work page 2020

  7. [7]

    H ˚avard Bakke Bjerkevik and Michael Lesnick.ℓp-distances on multiparameter persistence mod- ules.arXiv preprint arXiv:2106.13589, 2021

    work page arXiv 2021

  8. [8]

    A relative theory of interleavings

    Magnus Bakke Botnan, Justin Curry, and Elizabeth Munch. A relative theory of interleavings. arXiv preprint arXiv:2004.14286, 2020

    work page arXiv 2004

  9. [9]

    Metrics for generalized persistence modules

    Peter Bubenik, Vin De Silva, and Jonathan Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 15(6):1501–1531, 2015

    work page 2015

  10. [10]

    Interleaving and Gromov-Hausdorff distance

    Peter Bubenik, Vin de Silva, and Jonathan Scott. Interleaving and Gromov-Hausdorff distance. arXiv:1707.06288, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  11. [11]

    The theory of multidimensional persistence.Discrete & Computational Geometry, 42(1):71–93, 2009

    Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence.Discrete & Computational Geometry, 42(1):71–93, 2009

    work page 2009

  12. [12]

    Prox- imity of persistence modules and their diagrams

    Fr ´ed´eric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J Guibas, and Steve Y Oudot. Prox- imity of persistence modules and their diagrams. InProceedings of the twenty-fifth annual sympo- sium on Computational geometry, pages 237–246, 2009

    work page 2009

  13. [13]

    Springer, 2016

    Fr ´ed´eric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot.The structure and stability of persis- tence modules, volume 10. Springer, 2016

    work page 2016

  14. [14]

    The Generalized Rank Invariant: M ¨obius invertibility, Discriminating power, and Connection to Other Invariants.arXiv preprint arXiv:2207.11591v5, 2024

    Nate Clause, Woojin Kim, and Facundo Memoli. The Generalized Rank Invariant: M ¨obius invertibility, Discriminating power, and Connection to Other Invariants.arXiv preprint arXiv:2207.11591v5, 2024

    work page arXiv 2024

  15. [15]

    Stability of persistence diagrams

    David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & computational geometry, 37(1):103–120, 2007

    work page 2007

  16. [16]

    Decomposition of pointwise finite-dimensional persistence modules

    William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications, 14(05):1550066, 2015

    work page 2015

  17. [17]

    Categorified reeb graphs.Discrete & Computa- tional Geometry, 55(4):854–906, 2016

    Vin De Silva, Elizabeth Munch, and Amit Patel. Categorified reeb graphs.Discrete & Computa- tional Geometry, 55(4):854–906, 2016

    work page 2016

  18. [18]

    Theory of interleavings on categories with a flow.Theory and Applications of Categories, 33(21):583–607, 2018

    Vin De Silva, Elizabeth Munch, and Anastasios Stefanou. Theory of interleavings on categories with a flow.Theory and Applications of Categories, 33(21):583–607, 2018

    work page 2018

  19. [19]

    Reeb graphs of curves are stable under function perturba- tions.Mathematical Methods in the Applied Sciences, 35(12):1456–1471, 2012

    Barbara Di Fabio and Claudia Landi. Reeb graphs of curves are stable under function perturba- tions.Mathematical Methods in the Applied Sciences, 35(12):1456–1471, 2012

    work page 2012

  20. [20]

    The edit distance for reeb graphs of surfaces.Discrete & Computational Geometry, 55(2):423–461, 2016

    Barbara Di Fabio and Claudia Landi. The edit distance for reeb graphs of surfaces.Discrete & Computational Geometry, 55(2):423–461, 2016

    work page 2016

  21. [21]

    Galois Connections in Persistent Homology

    Aziz Burak G ¨ulen and Alexander McCleary. Galois connections in persistent homology.arXiv preprint arXiv:2201.06650, 2022. 18

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  22. [22]

    Interleaving by parts: Join decomposi- tions of interleavings and join-assemblage of geodesics.Order, 41(2):497–537, 2024

    Woojin Kim, Facundo M´emoli, and Anastasios Stefanou. Interleaving by parts: Join decomposi- tions of interleavings and join-assemblage of geodesics.Order, 41(2):497–537, 2024

    work page 2024

  23. [23]

    Enhanced stability for generalized persistence diagrams

    Woojin Kim and Won Seong. Enhanced stability for generalized persistence diagrams. 2025+

    work page 2025

  24. [24]

    Binary coors capable or ‘correcting deletions, insertions, and reversals

    VI Lcvenshtcin. Binary coors capable or ‘correcting deletions, insertions, and reversals. InSoviet physics-doklady, volume 10, 1966

    work page 1966

  25. [25]

    The theory of the interleaving distance on multidimensional persistence mod- ules.Foundations of Computational Mathematics, 15(3):613–650, 2015

    Michael Lesnick. The theory of the interleaving distance on multidimensional persistence mod- ules.Foundations of Computational Mathematics, 15(3):613–650, 2015

    work page 2015

  26. [26]

    Interactive Visualization of 2-D Persistence Modules

    Michael Lesnick and Matthew Wright. Interactive visualization of 2d persistence modules.arXiv preprint arXiv:1512.00180, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  27. [27]

    Springer Science & Busi- ness Media, 2013

    Saunders Mac Lane.Categories for the working mathematician, volume 5. Springer Science & Busi- ness Media, 2013

    work page 2013

  28. [28]

    Edit distance and persistence diagrams over lattices.SIAM Journal on Applied Algebra and Geometry, 6(2):134–155, 2022

    Alexander McCleary and Amit Patel. Edit distance and persistence diagrams over lattices.SIAM Journal on Applied Algebra and Geometry, 6(2):134–155, 2022

    work page 2022

  29. [29]

    Homological algebra of modules over posets.SIAM Journal on Applied Algebra and Geometry, 9(3):483–524, 2025

    Ezra Miller. Homological algebra of modules over posets.SIAM Journal on Applied Algebra and Geometry, 9(3):483–524, 2025

    work page 2025

  30. [30]

    A guided tour to approximate string matching.ACM computing surveys (CSUR), 33(1):31–88, 2001

    Gonzalo Navarro. A guided tour to approximate string matching.ACM computing surveys (CSUR), 33(1):31–88, 2001

    work page 2001

  31. [31]

    Courier Dover Publications, 2017

    Emily Riehl.Category theory in context. Courier Dover Publications, 2017

    work page 2017

  32. [32]

    On the foundations of combinatorial theory I: Theory of M ¨obius functions

    Gian-Carlo Rota. On the foundations of combinatorial theory I: Theory of M ¨obius functions. Zeitschrift f¨ur Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(4):340–368, 1964

    work page 1964

  33. [33]

    The tree-to-tree correction problem.Journal of the ACM (JACM), 26(3):422–433, 1979

    Kuo-Chung Tai. The tree-to-tree correction problem.Journal of the ACM (JACM), 26(3):422–433, 1979

    work page 1979

  34. [34]

    An extension of the string-to-string correction problem

    Robert A Wagner and Roy Lowrance. An extension of the string-to-string correction problem. Journal of the ACM (JACM), 22(2):177–183, 1975. 19

    work page 1975