Computing Projective Implicit Representations from Poset Towers

Florian Russold; Tamal K. Dey

REVIEW 1 major objections 4 minor 25 references

Computing Projective Implicit Representations from Poset Towers

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper shows that the persistent homology of any poset tower—simplicial complexes connected by arbitrary simplicial maps over a finite poset—can be represented by projective modules and graded matrices computed from graph-structured…

desk verdict Genuinely new and mostly sound algorithm for projective implicit representations of poset towers, but the Generator routine as written has a same-grade face-ordering bug that can break the boundary lift; fixable, but a revision is needed. read the letter →

arxiv 2505.08755 v2 pith:MBUXXDAK submitted 2025-05-13 math.AT cs.CG

Tamal K. Dey , Florian Russold This is my paper · ORCID

classification math.ATcs.CG MSC 55N3155U1006A07

keywords persistenthomologyposettowerprojectiveresolutionminimalpresentationP-gradedmatricessimplicialmapsmultiparameterpersistencegraphincidence

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Persistent homology is usually computed from filtrations, where each chain module is free and boundary maps are graded matrices. The paper treats poset towers—simplicial complexes linked by arbitrary simplicial maps over any finite poset—where chain modules can be non-projective and carry relations, so no such matrix representation exists. It claims that a short chain complex of projective modules and $P$-graded matrices, called a projective implicit representation (PiRep), can be built directly from the tower and has the same homology. The construction is combinatorial: simplex generators and the relations that identify or kill them are read off from a graph, and the paper gives algorithms whose complexity is near-quadratic in the tower size rather than cubic in the output matrices. If correct, this supplies the missing algebraic input that lets existing minimal-presentation algorithms run on arbitrary finite poset towers.

What carries the argument

The load-bearing object is a $P$-filtered graph whose vertices are the simplex generators plus one distinguished `graveyard' vertex $\Omega$, and whose edges are the relations: identifying two copies of a simplex, or killing a simplex that collapses to a lower dimension. Because every column of the presentation matrix $p^1_\ell$ has one or two non-zero entries, the matrix is the incidence matrix of this graph. Minimality of the presentation is enforced by adding an edge only when it closes no cycle, so the chosen relations form a spanning forest; cycles in the relation graph become the relations-of-relations matrix $p^2_\ell$. The same graph structure makes the correction maps $\gamma$ and $\vartheta$ computable by solving linear systems whose coefficient matrix is a graph incidence matrix, which the paper solves in linear time per system by leaf elimination on trees. This converts what would be cubic algebraic reduction into graph algorithms on forests.

What would settle it

Run the algorithm on the paper's own working example, the tower in Figure 11 where two copies of a vertex are identified at two grades and then the two relations become dependent, and compare grade by grade the homology of the PiRep with the direct homology of the simplicial complexes $H_\ell(K(x))$; any grade where $\ker d_\ell / \operatorname{im} d_{\ell+1}$ has the wrong dimension would refute Theorem 41. A second check is to verify that for a tower with two incomparable joins followed by a later join, every cycle-closing relation is omitted from $p^1_\ell$, so the number of columns equals the minimal number of relations.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that for every poset tower over a finite poset $P$, the homology $H_\ell(K)$ is isomorphic to the homology of a short chain complex of projective modules $D_{\ell-1} \xleftarrow{d_\ell} D_\ell \xleftarrow{d_{\ell+1}} D_{\ell+1}$ whose maps are represented by $P$-graded matrices (Theorem 41). The construction starts from minimal projective presentations of each chain module $C_\ell(K)$: generators are the simplex generators of the tower, relations are recorded in a matrix $p^1_\ell$ whose columns are edges of a $P$-filtered graph, and the second-level relations form $p^2_\ell$. The boundary maps of the simplicial chain complex are lifted to these resolutions, and two correction maps $\gamma$ and $\vartheta$ are added to repair the failure of the lifts to compose to zero. The result is a diagram that plays the role of the classical graded boundary matrix for one-parameter persistence, and it is computed in $O(n^2 t_0^2)$ time for a tower of size $n$ over a poset with $t_0$ elements.

Load-bearing premise

The whole construction is carried out over the two-element field $\mathbb{Z}_2$: a relation is encoded as a sum of two generator symbols, and the graph incidence picture relies on the fact that every column has one or two entries with signs collapsed.

Editorial extensions

If this is right

Any poset tower, including multifiltrations with multi-critical simplices, zigzag towers, and arbitrary simplicial maps, can be fed into existing minimal-presentation algorithms once a PiRep is computed.
The PiRep of $H_\ell$ has size governed by the first two Betti numbers of the resolution: $p^1_\ell$ has $O(n t_0)$ columns and $p^2_\ell$ has $O(n t_1)$ columns, so downstream presentation algorithms start from asymptotically minimal input.
The computation runs in $O(n^2 t_0^2)$ time dominated by the correction lifts, instead of the cubic-in-output time of general matrix reduction; the relation graph itself costs $O(n t \log n)$.
Over $\mathbb{Z}_2$, the algorithms are fully general over arbitrary finite posets, not restricted to grids or one-critical filtrations.
A computed PiRep can be converted to a minimal presentation of $H_\ell$ by an existing exactification routine, with only superfluous relations to remove.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The graph-forest viewpoint suggests that for structured posets such as $d$-dimensional grids or zigzag grids, the same relation cycles may be computable with specialized union-find or dynamic-connectivity data structures, potentially shaving the $t_0$ factors in the $O(n^2 t_0^2)$ bound.
If the method is adapted to finite fields of odd characteristic, the incidence-graph picture would need oriented edges and signed columns; the characteristic-$2$ symmetry that makes two-entry columns sufficient would break, so a different encoding of killing relations would be required.
The PiRep construction may also give a route to computing bigraded Betti numbers or other homological invariants of multiparameter persistence for towers with multi-critical simplices, not just presentations of homology, by reading ranks of the matrices at each grade.
Since the relation graph's spanning forest encodes a minimal set of simplex identifications, it could be reused across all dimensions: the $0$-dimensional relations determine vertex collapses that constrain higher-dimensional generators, which the paper exploits but does not fully develop into a single-pass multi-degree algorithm.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know about this paper. First, it is a genuine theoretical step forward: it gives the first fully general way to turn an arbitrary finite poset tower into a projective implicit representation (PiRep), which is what existing minimal-presentation algorithms need as input. The observation that the presentation matrix of Cℓ(K) is almost a P-filtered graph boundary matrix, and the use of graph incidence structure to solve lift equations in linear time per column, are clever and worth borrowing. Second, there is a real bug in the pseudocode. In the Generator routine, new generators at a grade x are added to the active set one by one, and Boundary for a simplex σ is called immediately. If a face τ of σ is also born at x, and the iteration over S reaches σ before τ, then τ is not yet in Lx_act. Boundary cannot find it, so fℓ(gx_σ) omits the boundary term. Proposition 21's proof assumes the needed representatives are active at the time of the call, but the algorithm as written does not guarantee this. This is not a coefficient-field nuance; it breaks the lift fℓ, and since the PiRep construction depends on fℓ, Theorem 41 is compromised on those inputs. The fix is straightforward—sort S by nondecreasing simplex dimension, or add all generators at x to Lx_act before computing boundaries—but the paper states neither. As written, the algorithm is underspecified and can produce an incorrect PiRep.

What the paper does well: it is self-contained, the algebraic framework over Z2 is cleanly set up, and the proofs of p1 minimality and p2 exactness are detailed. The linear-system solver for γ and ϑ via tree incidence matrices is a nice and nontrivial simplification. The complexity claims are explicit and plausible. The Z2-only scope is stated clearly and is acceptable for a theory paper, though it means the graph solver does not transfer to other fields.

Minor soft spots: no implementation, which is normal here, and the RelRel/Reduce complexity discussion is compressed but not obviously wrong. The generator-ordering issue is the load-bearing one.

Who this is for: researchers working on multiparameter, zigzag, or general poset persistence who need algebraic input for minimal-presentation algorithms. With the bug fixed, this is a solid contribution worth having. As it stands, I would not trust the algorithm on inputs where a simplex and a face are born at the same grade.

Recommendation: send to peer review, but ask the authors to fix the Generator ordering and re-prove Proposition 21 accordingly. I would want to see the revision before accepting.

Referee Report

1 major / 4 minor

Summary. The paper introduces a framework for computing a projective implicit representation (PiRep) of the persistent homology of a poset tower K:P->SCpx over a finite poset P and over the field Z2. It represents each chain module C_l(K) by a minimal presentation p1_l, lifts the boundary maps d_l to maps f_l on the projective generators, computes an asymptotically minimal second term p2_l via relations among relations, and then assembles a two-term PiRep using correction maps gamma and vartheta that are obtained by solving linear systems whose coefficient matrices have at most two non-zero entries per column. The main complexity claims are O(nt log n) for p1, O(n^2 t) for the construction of p2 via RelRel, and O(n^2 t0^2) for the full PiRep computation.

Significance. If the correctness issues are resolved, this is a substantive and original contribution. The graph-theoretic interpretation of presentations and the linear-time solver for multigraph incidence systems are elegant and likely to be useful beyond the specific setting of poset towers. The paper is largely self-contained, and the diagram-chasing proofs for Propositions 39-40 and Theorem 41 are detailed and credible. The authors are also explicit that the entire development is over Z2, which is a scope limitation but not a hidden flaw. However, the pseudocode has a load-bearing underspecification in the Generator/Boundary ordering that currently prevents the algorithm from being correct as written; this is fixable with a local modification.

major comments (1)

[Section 3, Algorithm Generator and Boundary; Section 4.1, Proposition 21] The iteration order in Generator step 1 is unspecified, but correctness of the boundary lift depends on it. The pseudocode adds each new generator (sigma,g^x_sigma) to L^x_act and immediately calls Boundary(x,sigma). If a face tau of sigma is also born at grade x, its representative (tau,g^x_tau) is added only when the loop reaches tau. In an arbitrary order with sigma before tau, Boundary(x,sigma) cannot find tau in L^x_act, so the column for g^x_sigma in f_l omits the boundary term tau. Proposition 21 asserts that Boundary finds active representatives of d_sigma, but no invariant or ordering in the algorithm guarantees this. This is load-bearing: f_l is the lift used in equations (5), (13), and Theorem 41, so on inputs where a simplex and a face share a birth grade, the computed PiRep can be wrong. The fix is local: insert all new generators into L^x_act before calling Boundary, or iterate S in nondecreasing simplex dimension; the existing proofs then apply.

minor comments (4)

[Proposition 19] Proposition 19 has a typo: the statement 'Let g^y_sigma in and y <= x in P' is missing the set S_l.
[Section 5.1] Section 5.1 refers to 'Appendix 5' for the proofs of the PiRep results; the proofs actually appear in Appendix A.
[Abstract and Section 2] The field Z2 is fixed only in Section 2, but the abstract describes vector spaces without specifying the field; since all incidence computations and projective-cover arguments are characteristic-2 specific, the abstract should state this scope.
[Algorithm Generator, step 2] The pseudocode for the pair loop in Generator step 2 should state explicitly whether the loop iterates over L^x_act as it is at entry or as it is updated by deletions; the worked example suggests a specific semantics, but the pseudocode as written is ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the PiRep construction is derived from definitions and proven against standard algebraic benchmarks.

full rationale

The paper's derivation chain is self-contained. The input is a poset tower specified by simplex generators and edge events; the output is a projective implicit representation assembled from minimal presentations p1_ℓ, second terms p2_ℓ, boundary lifts f_ℓ, and correction maps γ and ϑ. Each component is constructed by an explicit algorithm from the poset-tower data, and the correctness proofs are diagram chases using standard facts: α_ℓ is an epimorphism (Proposition 15), ker α_ℓ = im p1_ℓ (Proposition 20), ker p1_ℓ = im p2_ℓ (Propositions 35–36), and the lift equations p1_{ℓ-1}∘γ = f_ℓ∘p1_ℓ and p1_{ℓ-1}∘ϑ = f_ℓ∘f_{ℓ+1} are solved as linear systems whose solvability follows from projectivity and exactness, not assumed as outputs. The final PiRep of Theorem 41 is exactly the cokernel of the assembled block matrix, with Propositions 39–40 proving the required exactness. There is no fitted parameter renamed as a prediction and no central claim that reduces to a self-citation: references to prior work are contextual (simplicial towers, FiRep terminology, and the downstream use of [4] for computing presentations from a PiRep), and the authors' own prior results are not used as the load-bearing justification for the new construction. The skeptical concern about generator ordering in Boundary is a potential correctness/implementation issue, not a circularity. Overall, the derivation is independent of its conclusions and no circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No parameters are fitted. The algorithm depends on standard facts about projective modules over the incidence algebra of a finite poset and on the explicit Z2 coefficient field. The 'graveyard' vertex Ω is a bookkeeping device used to encode collapse relations as graph edges; it is proven to work and introduces no new independent assumption.

assumptions (4)

standard math Modules over the incidence algebra of a finite poset have projective resolutions whose projective objects are direct sums of Proj[x].
Used throughout Section 2.2 and in Definition 8; standard for finite poset persistence modules (e.g., Miller 2020).
domain assumption Homology is computed over the field Z2; all vector spaces are over Z2.
Stated in Section 2: 'We will use the notation Vec for the category of vector spaces over Z2.' The algorithms and proofs are specific to characteristic 2.
standard math A simplicial map is determined by its action on vertices.
Used in Proposition 4 to reconstruct the tower from simplex generators and edge events.
domain assumption The maximum simplex dimension is constant.
Assumed for the complexity analysis in Section 3.1; correctness does not depend on it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computing Projective Implicit Representations from Poset Towers." pith.science (2026). https://pith.science/paper/MBUXXDAK

@misc{pith2026250508755,
  author       = {Pith},
  title        = {Pith review of: Computing Projective Implicit Representations from Poset Towers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MBUXXDAK}},
  note         = {Machine review of arXiv:2505.08755}
}

abstract

A family of simplicial complexes connected by simplicial maps and indexed by a finite poset $P$ is called a poset tower. Poset towers subsume multi-parameter filtrations, zigzag filtrations, and one-parameter simplicial towers, while allowing arbitrary finite posets and simplicial maps. The homology of a poset tower is a $P$-persistence module. To compute it globally over $P$, we consider the chain complex segment of $P$-persistence modules $C_{\ell-1}\xleftarrow{\partial_{\ell}}C_\ell \xleftarrow{\partial_{\ell+1}}C_{\ell+1}$ induced by the simplices of the tower. Unlike in one-critical multi-filtrations, the chain modules $C_\ell$ need not be projective and may have a complicated structure. We address the problem of replacing this segment by projective modules and $P$-graded matrices while preserving homology. The resulting projective implicit representation (PiRep) plays the role of the graded boundary-matrix representation in the classical persistence algorithm: it converts simplicial data into algebraic input on which persistent homology can be computed globally over $P$. In particular, a PiRep can be used as input to algorithms for computing minimal presentations of persistent homology. We give an efficient algorithm to compute a PiRep from a poset tower. It constructs degreewise minimal presentations and asymptotically minimal second terms of projective resolutions of the chain modules $C_\ell$, lifts the boundary maps $\partial_\ell$ to these resolutions, and assembles the resulting data into a PiRep using an additional correction term. The method is tailored to chain complexes induced by poset towers and computes the required algebraic data combinatorially, exploiting their special structure and avoiding general-purpose algebraic reduction. In the context of poset towers, it is fully general and can serve as a foundation for efficient algorithms on specific posets.

Figures

Figures reproduced from arXiv: 2505.08755 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 19 canonical work pages

[1]

Efficient two-parameter persistence computation via cohomology

Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient two-parameter persistence computation via cohomology. In 39th International Symposium on Computational Geometry, SocG 2023 , volume 258 of LIPIcs , pages 15:1--15:17, 2023

work page 2023
[2]

Computing minimal presentations of multi-parameter persistent homology

Matías Bender, Oliver Gäfvert, and Michael Lesnick. Computing minimal presentations of multi-parameter persistent homology. https://www.tugraz.at/projekte/cpw/abstracts

work page
[3]

An introduction to multiparameter persistence, 2023

Magnus Bakke Botnan and Michael Lesnick. An introduction to multiparameter persistence, 2023. https://arxiv.org/abs/2203.14289

arXiv 2023
[4]

Discrete Microlocal Morse Theory

Adam Brown and Ondrej Draganov. Discrete microlocal morse theory, 2024. https://arxiv.org/abs/2209.14993

work page Pith review arXiv 2024
[5]

Zigzag persistence

Gunnar Carlsson and Vin De Silva. Zigzag persistence. Foundations of computational mathematics , 10:367--405, 2010

work page 2010
[6]

The theory of multidimensional persistence

Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. In Proceedings 23rd Annual Symposium on Computational Geometry , pages 184--193, 2007

work page 2007
[7]

Combinatorial presentation of multidimensional persistent homology

Wojciech Chach \'o lski, Martina Scolamiero, and Francesco Vaccarino. Combinatorial presentation of multidimensional persistent homology. Journal of Pure and Applied Algebra , 221(5):1055--1075, 2017

work page 2017
[8]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition . The MIT Press, 3rd edition, 2009

2009

Show all 25 references

[9]

Computing topological persistence for simplicial maps

Tamal K Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps. In Proceedings 30th Annual Symposium on Computational Geometry , pages 345--354, 2014

2014
[10]

Dey and Tao Hou

Tamal K. Dey and Tao Hou. Fast Computation of Zigzag Persistence . In Proceedings 30th Annual European Symposium on Algorithms (ESA 2022) , volume 244 of LIPIcs , pages 43:1--43:15, 2022

2022
[11]

Dey, Florian Russold, and Shreyas N

Tamal K. Dey, Florian Russold, and Shreyas N. Samaga. Efficient Algorithms for Complexes of Persistence Modules with Applications . In Proceedings 40th International Symposium on Computational Geometry (SoCG 2024) , volume 293 of LIPIcs , pages 51:1--51:18, 2024

2024
[12]

Dey and Shreyas N

Tamal K. Dey and Shreyas N. Samaga. Quasi zigzag persistence: A topological framework for analyzing time-varying data. CoRR , abs/2502.16049, 2025

2025
[13]

Dey and Yusu Wang

Tamal K. Dey and Yusu Wang. Computational Topology for Data Analysis . Computational Topology for Data Analysis. Cambridge University Press, 2022

2022
[14]

Topological persistence and simplification

Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry , 28:511--533, 2002

2002
[15]

Edelsbrunner and J

H. Edelsbrunner and J. Harer. Computational Topology: An Introduction . Applied Mathematics. American Mathematical Society, 2010

2010
[16]

Spatiotemporal persistence landscapes

Martina Flammer. Spatiotemporal persistence landscapes. Young Researchers Forum (CG:YRF) 2024, Booklet of Abstracts , 2024

2024
[17]

Chunk reduction for multi-parameter persistent homology

Ulderico Fugacci and Michael Kerber. Chunk reduction for multi-parameter persistent homology. In 35th International Symposium on Computational Geometry, SoCG 2019 , volume 129 of LIPIcs , pages 37:1--37:14, 2019

2019
[18]

DONUT : D atabase of O riginal & N on- T heoretical U ses of T opology, 2022

Barbara Giunti, J \=a nis Lazovskis, and Bastian Rieck. DONUT : D atabase of O riginal & N on- T heoretical U ses of T opology, 2022. https://donut.topology.rocks

2022
[19]

Fast minimal presentations of bi-graded persistence modules

Michael Kerber and Alexander Rolle. Fast minimal presentations of bi-graded persistence modules. In Workshop on Algorithm Engineering and Experimentation , 2020

2020
[20]

Barcodes of towers and a streaming algorithm for persistent homology

Michael Kerber and Hannah Schreiber. Barcodes of towers and a streaming algorithm for persistent homology. Discrete & Computational Geometry , 61:852--879, 2019

2019
[21]

Persistence over posets

Woojin Kim and Facundo M \'e moli. Persistence over posets. Notices of the American Mathematical Society , 70(08), 2023

2023
[22]

Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology

Michael Lesnick and Matthew Wright. Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology. SIAM Journal on Applied Algebra and Geometry , 6(2):267--298, 2022

2022
[23]

Homological algebra of modules over posets, 2020

Ezra Miller. Homological algebra of modules over posets, 2020. https://arxiv.org/abs/2008.00063

2020 arXiv
[24]

Computing betti tables and minimal presentations of zero-dimensional persistent homology

Dmitriy Morozov and Luis Scoccola. Computing betti tables and minimal presentations of zero-dimensional persistent homology. In Proceedings 41st International Symposium on Computational Geometry, SocG 2025 (to appear) , 2025. https://arxiv.org/abs/2410.22242

2025
[25]

Computing persistent homology

Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. In Proceedings 20th Annual Symposium on Computational Geometry , pages 347--356, 2004

2004

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Efficient two-parameter persistence computation via cohomology

Ulrich Bauer, Fabian Lenzen, and Michael Lesnick. Efficient two-parameter persistence computation via cohomology. In 39th International Symposium on Computational Geometry, SocG 2023 , volume 258 of LIPIcs , pages 15:1--15:17, 2023

work page 2023

[2] [2]

Computing minimal presentations of multi-parameter persistent homology

Matías Bender, Oliver Gäfvert, and Michael Lesnick. Computing minimal presentations of multi-parameter persistent homology. https://www.tugraz.at/projekte/cpw/abstracts

work page

[3] [3]

An introduction to multiparameter persistence, 2023

Magnus Bakke Botnan and Michael Lesnick. An introduction to multiparameter persistence, 2023. https://arxiv.org/abs/2203.14289

arXiv 2023

[4] [4]

Discrete Microlocal Morse Theory

Adam Brown and Ondrej Draganov. Discrete microlocal morse theory, 2024. https://arxiv.org/abs/2209.14993

work page Pith review arXiv 2024

[5] [5]

Zigzag persistence

Gunnar Carlsson and Vin De Silva. Zigzag persistence. Foundations of computational mathematics , 10:367--405, 2010

work page 2010

[6] [6]

The theory of multidimensional persistence

Gunnar Carlsson and Afra Zomorodian. The theory of multidimensional persistence. In Proceedings 23rd Annual Symposium on Computational Geometry , pages 184--193, 2007

work page 2007

[7] [7]

Combinatorial presentation of multidimensional persistent homology

Wojciech Chach \'o lski, Martina Scolamiero, and Francesco Vaccarino. Combinatorial presentation of multidimensional persistent homology. Journal of Pure and Applied Algebra , 221(5):1055--1075, 2017

work page 2017

[8] [8]

Cormen, Charles E

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition . The MIT Press, 3rd edition, 2009

2009