Computation of cubical homology, cohomology, and (co)homological operations via chain contraction (Q2017610)

The authors introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the techique based on a chain contraction from the original chain complex to a reduced one that represents its homology. An implementation in C++ of introduced algorithms is available at \texttt{http://www.pawelpilarczyk.com/chaincon/} together with examples. Let \(C = (C_q, \partial_q)_{q\in {\mathbb Z}}\) be a chain complex of free finitely generated abelian groups \(C_q\) and homomorphisms \(\partial_q: C_q\to C_{q-1}\) for all \(q\in {\mathbb Z}\). There are two approaches to homology computation. In the \textit{differential approach}, the matrices of the boundary homomorphisms \(\partial_q\) are reduced to the Smith Normal Form (SNF), from which the homology groups are determined. In the \textit{integral approach}, the homomorphisms \(\phi_q: C_q \to C_{q+1}\) are constructed, which record the information on a chain contraction of the entire chain complex \(C\) to a reduced chain complex that represents its homology. The main aim of this work is to develop the second approach to (co)homology algorithms for the cubical structure. A \textit{Euclidean} domain \(R\) is a principal ideal domain equipped with the function \(\delta_R: R\to \mathbb{Z}\) that assigns a non-negative integer to each element of the ring, such that for every \(a,b\in R\), \(b\not=0\), there exists \(q,r\in R\) for which \(a = qb+r\) and \(\delta_R(r)< \delta_R(b)\). Let \(K\) be an \(n\)-dimensional cell complex, also called a CW complex in the sense of [\textit{A. Hatcher}, Algebraic topology, Cambridge: Cambridge University Press (2002; Zbl 1044.55001), Ch.0]. In this paper, the number of all cells in the complex is assumed to be finite. The set of \(q\)-dimensional cells is denoted by \(K^{(q)}\). The corresponding \textit{chain complex} \((C_q(K), \partial_q)_{q \in \mathbb{Z}}\) over \(R\) consists of the free \(R\)-modules of \(q\)-chains \(C_q\), whose elements are formal combinations of the cells in \(K^{(q)}\) with coefficients in \(R\), and a family of homomorphisms \(\partial_q: C_q\to C_{q-1}\) such that \(\partial_{q-1}\partial_q=0\) and \(\partial_q(\sigma)\) is a combination of \((q-1)\)-dimensional cells that appear in the boundary of \(\sigma\) with coefficients corresponding to the orientation and multiplicity of these cells. Note that \(C_q(K)=0\) whenever \(q<0\) or \(q>n\). If \(R=\mathbb{Z}\) then each \(C_q\) is a free abelian group. If \(R\) is a field then each \(C_q\) is a vector space over \(R\). Since the number of cells in \(K\) is finite, all the \(R\)-modules under consideration are finitely generated. Recall the definition of an elementary cube. An \textit{elementary interval} in the set of reals \(\mathbb{R}\) is an interval of the form \([k, k+1]\) (the \textit{non-degenerate} case) or a set \([k,k]=\{k\}\) also denoted by \([k]\) (the \textit{degenerate} case), where \(k\in \mathbb{Z}\). An \textit{elementary cube} in \(\mathbb{R}^n\) is the Cartesian product of \(n\) elementary intervals, and the number of non-degenerate intervals in this product is its \textit{dimension}. A \textit{cubical cell complex} is a union of elementary cubes. For the construction of its cubical complex, we consider an arbitrary elementary cube \(\sigma= I_1\times \cdots \times I_n \in K^{(q)}\), where \(I_j= [a^0_j, a^1_j]\) (possibly) \(a^0_j= a^1_j\). Let \(I_{k_j}=[a^0_{k_j}, a^1_{k_j}]\) be \(j\)th non-degenerate intervals where \(j\in \{1, \ldots, q\}\). For \(\varepsilon \in \{0,1\}\), define \[ \lambda^{\varepsilon}_j(\sigma)= I_1\times \cdots \times I_{k_j-1} \times \{a^{\varepsilon}_{k_j}\}\times I_{k_j+1}\times \cdots \times I_n\,. \] The \textit{cubical complex} consists of free \(R\)-modules \(C_q(K)\) generated by \(K^{(q)}\) with the boundary of \(\sigma\in K^{(q)}\) defined as \(\partial_q(\sigma)=\sum\limits^q_{j=1}(-1)^j(\lambda^0_j\sigma-\lambda^1_j\sigma)\) if \(q>0\) and \(\partial_q=0\) for \(q\geq 0\). For chain complexes \(C_*= (C_q, \partial_q)\) and \(C'_*= (C'_q, \partial'_q)\), a \textit{chain map} \(f_*: C_*\to C'_*\) is a family of homomorphisms \((f_q: C_q\to C'_q)_{q\in \mathbb{Z}}\) such that \(\partial'_q f_q= f_{q-1}\partial_q\). A \textit{chain contraction} from \(C_*\) to \(C'_*\) is a triple \((f,g,\phi)\) of chain maps \(f: C_*\to C'_*\), \(g: C'_*\to C_*\), and \(\phi: C_*\to C_{*+1}\) that satisfy the following conditions: \[ (a)~ Id_C -gf = \partial\phi+ \phi \partial; ~ (b)~ fg=Id_{C'};~ (c)~ f\phi=0;~ (d)~ \phi g=0;~ (e)~ \phi\phi=0. \] In this case, the homology modules of \(C_*\) and \(C'_*\) are isomorphic. A homomorphism \(\phi: C_*\to C_{*+1}\) is called a \textit{homology gradient vector field} if the following conditions hold: \[ (a)~ \phi\phi=0; ~ (b)~ \partial \phi \partial= \partial; ~ (c)~ \phi\partial \phi = \phi. \] A chain contraction in which \(\phi\) is a homology gradient vector field is called \textit{integral chain contraction}. An \textit{algebraic-topological model}, or an \textit{AT model} for short, of a cell complex \(K\), is a homology integral chain contraction from \(C_*(K)\) to some free chain complex \(M_*\) with null differential (Definition 1). An \textit{algebraic minimal model}, or an \textit{AM model} for short, of a cell complex \(K\) is a chain contraction from \(C_*(K)\) to a chain complex \((M,d)\) such that each \(M_q\) is a free \(R\)-module and all the non-zero elements in the SNF of each matrix \(d_q\) are non-invertible in \(R\) (Definition 2). The explicit algorithms for the computation of AT models (Algorithm 1) and AM models (Algorithm 2) for a cell complex are provided. Section 4 is devoted to the method for selecting the homologous information from the AT models and AM models, such as (co)homology generators. In Section 5, the authors use this approach to compute the cup product based on formulas at chain level for cubical complexes. In Section 6, certain additional constructions and variants are disscused, like relative (co)homology or reduced (co)homology, which used machinery is capable of handling with very little additional effort. Section 7 contains a brief description of the prototype software and selected examples that have been made available at the project's website, which concludes the paper.