On rectangle-decomposable 2-parameter persistence modules (Q2105322)

A \textit{persistence module} \(M\) is a set of modules indexed by a subset of \(\mathbb{R}^d\) (or more generally by a poset) and of linear maps between pairs of modules. The \textit{rank invariant} of \(M\) is the function that maps each pair of indices to the dimension of the image of the corresponding linear map. If \(d=1\), the rank invariant completely characterizes \(M\) up to isomorphism [\textit{G. Carlsson} and \textit{A. Zomorodian}, Discrete Comput. Geom. 42, No. 1, 71--93 (2009; Zbl 1187.55004)]; the proof relies on the decomposition of \(M\) into elementary persistence modules, the identifiers of intervals, which are represented as the bars of the \textit{barcode} of \(M\). In the multi-parameter case \(d>1\), the rank invariant is no more a complete invariant, as is shown also in the present paper by simple examples. The rank invariant is a practical fingerprint of objects of interest in persistent homology [\textit{H. Edelsbrunner} and \textit{J. Harer}, Contemp. Math. 453, 257--282 (2008; Zbl 1145.55007)] (as \textit{persistent Betti number function}) and has several applications in topological data analysis, so it is important to spot classes of multi-parameter persistence modules for which it actually is complete. The present article deals with 2-parameter persistence modules. A previous paper [\textit{J. Cochoy} and \textit{S. Oudot}, Discrete Comput. Geom. 63, No. 2, 255--293 (2020; Zbl 1435.62453)] defined a notion of \textit{strong exactness} and recognized it as equivalent to the decomposability of \(M\) into so-called \textit{blocks}. Here the strategy is refined by the definition of \textit{weak exactness}. The authors prove that \(M\) is weakly exact if and only if it is decomposable into a direct sum of indicator modules of rectangles, i.e. products of intervals (Theorems 1.7, 4.2). The advantage is that the rank invariant is complete for such a persistence module (Theorem 2.1); so to say, rectangles play the role of intervals in the 1-dimensional case. The key ingredient of the proof is an inclusion-exclusion formula inspired by the multiplicity in a persistence diagram. The authors adapt an argument from \textit{D. Morozov}'s Ph.D. thesis [``Homological Illusions of Persistence and Stability'', PhD Thesis, Duke University, Durham (2008; \url{https://mrzv.org/publications/thesis/})] to prove Corollary 3.2: Computing the decomposition of a rectangle-decomposable module induced in homology by a 2-parameter filtration with \(n\) simplices can be done in \(O(n^4)\) time. An algorithm for checking rectangle decomposability is given in Section 5, and is proven to be of \(O(n^{2+\omega})\) complexity, where \(\omega\) is the exponent for matrix multiplication. Section 6 shows that wider classes of decompositions cannot be checked locally. Section 7 finally applies Theorem 4.2 to the decomposability of the pyramid construction of [\textit{G. Carlsson} et al., in: Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8--10, 2009. New York, NY: Association for Computing Machinery (ACM). 247--256 (2009; Zbl 1380.68385)].