# Cup Product Persistence and Its Efficient Computation

Tamal K. Dey
<EMAIL_ADDRESS>Abhishek Rathod
<EMAIL_ADDRESS>
###### Abstract

It is well-known that cohomology has a richer structure than homology.
However, so far, in practice, the use of cohomology in persistence setting has
been limited to speeding up of barcode computations. Some of the recently
introduced invariants, namely, persistent cup-length [13], persistent cup
modules [14] and persistent Steenrod modules [21], to some extent, fill this
gap. When added to the standard persistence barcode, they lead to invariants
that are more discriminative than the standard persistence barcode. In this
work, we devise an $O(dn^{4})$ algorithm for computing the persistent $k$-cup
modules for all $k\in\\{2,\dots,d\\}$, where $d$ denotes the dimension of the
filtered complex, and $n$ denotes its size. Moreover, we note that since the
persistent cup length can be obtained as a byproduct of our computations, this
leads to a faster algorithm for computing it.

##  1 Introduction

Persistent homology is one of the principal tools in the fast growing field of
topological data analysis. A solid algebraic framework [29], a well-
established theory of stability [10, 9] along with fast algorithms and
software [1, 2, 6, 3, 22] to compute complete invariants called barcodes of
filtrations have led to the successful adoption of single parameter persistent
homology as a data analysis tool [16, 17]. This standard persistence framework
operates in each (co)homology degree separately and thus cannot capture the
interactions across degrees in an apparent way. To achieve this, one may endow
a cohomology vector space with the well-known _cup product_ forming a graded
algebra. Then, the isomorphism type of such graded algebras can reveal
information including interactions across degrees. However, even the best
known algorithms for determining isomorphism of graded algebras run in
exponential time in the worst case [7]. So it is not immediately clear how one
may extract new (persistent) invariants from the product structure efficiently
in practice.

Cohomology has already shown to be useful in speeding up persistence
computations before[2, 1, 6]. It has also been noted that additional
structures on cohomology provide an avenue to extract rich topological
information[28, 21, 20, 5, 13]. To this end, in a recent study, the authors of
[13] introduced the notion of (the persistent version of) an invariant called
the _cup length_ , which is the maximum number of cocycles with a nonzero
product. In another version [14], the authors of [13] introduced an invariant
called _barcodes of persistent $k$-cup modules_ which are stable, and can add
more discriminating ability (Figure 1). Computing this invariant allows us to
capture interactions among degrees with the help of the cup product. In
Section 3 and 4, we show how to compute these barcodes efficiently. Moreover,
since the persistent cup length of a filtration can be obtained as a byproduct
of barcodes of persistent $k$-cup modules as observed in [13], we get an
efficient algorithm to compute this invariant as well.

Our approach for computing barcodes of persistent $k$-cup modules involves
computing the image persistence of the cup product viewed as a map from the
tensor product of the cohomology vector space to the cohomology vector space
itself. This approach requires careful bookkeeping of restrictions of
(product) cocycles as one processes the simplices in the reverse filtration
order. Algorithms for computing image persistence have been studied earlier by
Cohen-Steiner et al. [12] and recently by Bauer and Schmahl [4]. However, the
algorithms in [12, 4] work only for monomorphisms of filtrations making them
inapplicable to our setting.

In Example 1.1, we provide simple examples for which persistent cup modules
can disambiguate filtered spaces where ordinary persistence and persistent
cup-length fail. Notice that for a $d$-dimensional filtered complex
$\mathsf{K}$, the persistent $k$-cup modules for $k\in\\{2,\dots,d\\}$ may not
be a strictly finer invariant on its own compared to ordinary persistent
(co)homology. It can however add more information as Example 1.1 illustrates.

######  Example 1.1.

See Figure 1. Let $\mathsf{K}_{1}$ be a cell complex obtained by taking a
wedge of four circles and two $2$-spheres filtered as follows: the basepoint
arrives at index $1$, the four circles arrive at index $2$ and the two
$2$-spheres arrive at index $3$. Let $\mathsf{K}_{2}$ be a cell complex
obtained by taking a wedge of two circles, a sphere and a $2$-torus filtered
as follows: the basepoint arrives at index $1$, the two circles and the two
loops of the torus arrive at index $2$ and the sphere and the $2$-cell of the
torus arrive at index $3$. Let $\mathsf{K}_{3}$ be a cell complex obtained by
taking a wedge of two tori filtered as follows: the basepoint arrives at index
$1$, the four loops of the two tori arrive at index $2$ and the two $2$-cells
of the two tori arrive at index $3$.

Standard persistence cannot tell apart $\mathsf{K}_{1}$, $\mathsf{K}_{2}$ and
$\mathsf{K}_{3}$ as the barcode for three filtrations are the same. Persistent
cup length cannot distinguish $\mathsf{K}_{2}$ from $\mathsf{K}_{3}$ (both are
$2$), whereas the barcodes for persistent cup modules for $\mathsf{K}_{1}$,
$\mathsf{K}_{2}$ and $\mathsf{K}_{3}$ are all different (see Figure 1).

We refer the reader to Appendix C for other examples.

##  2 Background and preliminaries

Througout, we use $n$ to denote the size of the filtered complex $\mathsf{K}$,
$[n]$ to denote the set $\\{1,2,\dots,n\\}$ and $I$ to denote the set
$\\{0,1,2,\dots,n\\}$.

###  2.1 Persistent cohomology

We briefly recall some of the topological preliminaries in Appendix A. For an
in-depth study, we refer the reader to [18, 19]. We focus on
$\mathbb{Z}_{2}$-cohomology rather than $\mathbb{Z}_{2}$-homology because
cohomology is equipped with a product structure. Let $P$ denote a poset
category such as $\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{R}$, and
$\mathbf{Simp}$ denote the category of simplicial complexes.

Figure 1: Example 1 Persistent cup modules distinguishes all three cellular
filtrations.

A _$P$ -indexed filtration_ is a functor $\mathcal{F}:P\to\mathbf{Simp}$ such
that $\mathcal{F}_{s}\subseteq\mathcal{F}_{t}$ whenever $s\leq t$.

A $P$-indexed _persistence module_ $V_{\bullet}$ is a functor from a poset
category $P$ to the category of (graded) vector spaces. The morphisms
$V_{s}\to V_{t}$ for $s\leq t$ are referred to as _structure maps_. We assume
it to be of _finite type_ , that is, $V_{\bullet}$ is pointwise finite
dimensional and all morphisms $V_{s}\to V_{t}$ for $s\leq t$ are isomorphisms
outside a finite subset of $P$.

A persistence module $V_{\bullet}$ defined on a totally ordered set such as
$\mathbb{N}$, $\mathbb{Z}$, or $\mathbb{R}$ decomposes uniquely up to
isomorphism into simple modules called _interval modules_ whose structure maps
are identity and the vector spaces have dimension one. The support of these
interval modules collectively constitute what is called the barcode of
$V_{\bullet}$ and denoted by $B(V_{\bullet})$.

When we have a filtration $\mathcal{F}$ on $P$ where the complexes change only
at a finite set of values $a_{1}<a_{2}<\ldots<a_{n}$, we can reindex the
filtration with integers, and refine it so that only one simplex is added at
every index. Reindexing and refining in this manner one can obtain a simplex-
wise filtration of the final simplicial complex $\mathsf{K}$ defined on an
indexing set with integers. For the remainder of the paper, we assume that the
original filtration on $P$ is simplex-wise to begin with. This only simplifies
our presentation, and we do not lose generality. With this assumption, we
obtain a filtration indexed on $I$ after writing
$\mathsf{K}_{a_{i}}=\mathsf{K}_{i}$,

$\mathsf{K}_{\bullet}:\emptyset=\mathsf{K}_{0}\hookrightarrow\mathsf{K}_{1}\hookrightarrow\dots\hookrightarrow\mathsf{K}_{n}=\mathsf{K}.$

Applying the appropriate functors, we obtain a persistence module
$\mathsf{C}^{\ast}(\mathsf{K}_{\bullet})$ of cochain complexes whose structure
maps are cochain maps (see Appendix A) defined by restrictions (induced from
inclusions $\mathsf{K}_{i}\supseteq\mathsf{K}_{i-1}$):

$\mathsf{C}^{\ast}(\mathsf{K}_{\bullet}):\mathsf{C}^{\ast}(\mathsf{K}_{n})\to\mathsf{C}^{\ast}(\mathsf{K}_{n-1})\to\dots\to\mathsf{C}^{\ast}(\mathsf{K}_{0}),$

and a persistence module $\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ of graded
cohomology vector spaces whose structure maps are linear maps induced by the
above-mentioned restrictions

$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}):\mathsf{H}^{\ast}(\mathsf{K}_{n})\to\mathsf{H}^{\ast}(\mathsf{K}_{n-1})\to\dots\to\mathsf{H}^{\ast}(\mathsf{K}_{0}).$

For simplifying the description of the algorithm, we work with
$I^{\operatorname*{op}}$-indexed modules
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ and
$\mathsf{C}^{\ast}(\mathsf{K}_{\bullet})$. The barcode $B(M)$ (see section
2.5) of a finite-type $P^{\operatorname*{op}}$-module $M$ can be obtained from
the barcode $B(N)$ of its associated $I^{\operatorname*{op}}$-module $N$ by
writing the interval $(j,i]\in B(N)$ for $j<i<n$ as $[a_{j+1},a_{i+1})\in
B(M)$, and the interval $(j,n]\in B(N)$ as $[a_{j+1},\infty)\in B(M)$. In this
convention, we refer to $i$ (or $n$) as a _birth index_ , $j$ as a _death
index_ , and intervals of the form $(j,n]$ as _essential bars_.

######  Definition 2.1 (Restriction of cocycles).

For a filtration $\mathsf{K}_{\bullet}$, if $\zeta$ is a cocycle in complex
$\mathsf{K}_{b}$, but ceases to be a cocycle at $\mathsf{K}_{b+1}$, then
$\zeta^{i}$ is defined as
$\zeta^{i}=\zeta\cap\mathsf{C}^{\ast}(\mathsf{K}_{i})$ for $i\leq b$, and in
this case, we say that $\zeta^{i}$ is the restriction of $\zeta$ to index $i$.
For $i>b$ , $\zeta^{i}$ is set to the zero cocycle.

######  Definition 2.2 (Persistent cohomology basis).

Let $\Omega_{\mathsf{K}}=\left\\{\zeta_{\mathbf{i}}\mid\mathbf{i}\in
B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))\right\\}$ be a set of cocycles,
where for every $\mathbf{i}=(d_{i},b_{i}]$, $\zeta_{\mathbf{i}}$ is a cocycle
in $\mathsf{K}_{b_{i}}$ but no more a cocycle in $\mathsf{K}_{b_{i}+1}$. If
for every index $j\in[n]$, the cocycle classes
$\left\\{[\zeta_{\mathbf{i}}^{j}]\mid\zeta_{\mathbf{i}}\in\Omega_{\mathsf{K}}\right\\}$
form a basis for $\mathsf{H}^{\ast}(\mathsf{K}_{j})$, then we say that
$\Omega_{\mathsf{K}}$ is a persistent cohomology basis for
$\mathsf{K}_{\bullet}$, and the cocycle $\zeta_{\mathbf{i}}$ is called a
representative cocycle for the interval $\mathbf{i}$. If $b_{i}=n$,
$[\zeta_{\mathbf{i}}]$ is called an _essential class_.

###  2.2 Image persistence

The category of persistence module is abelian since the indexing category $P$
is small and the category of vector spaces is abelian. Therefore, kernels,
cokernels, and direct sums are all well-defined. Persistence modules obtained
as images, kernels and cokernels of morphisms were first studied by Cohen-
Steiner et al. [12]. In this section, we provide a brief overview of image
persistence modules.

Let $\mathsf{C}_{\bullet}$ and $\mathsf{D}_{\bullet}$ be two persistence
modules of cochain complexes:

$\mathsf{C}^{\ast}_{n}\xrightarrow{\varphi_{n}}\mathsf{C}^{\ast}_{n-1}\xrightarrow{\varphi_{n-1}}\dots\xrightarrow{\varphi_{1}}\mathsf{C}^{\ast}_{0}\quad\quad
and\quad\quad\mathsf{D}^{\ast}_{n}\xrightarrow{\psi_{n}}\mathsf{D}^{\ast}_{n-1}\xrightarrow{\psi_{n-1}}\dots\xrightarrow{\psi_{1}}\mathsf{D}^{\ast}_{0},$

such that for $0\leq i\leq n$ the graded vector spaces $\mathsf{C}^{*}_{i}$
and $\mathsf{D}^{*}_{i}$ (along with the respective coboundary maps) are
cochain complexes, and the structure maps
$\\{\varphi_{i}:\mathsf{C}^{*}_{i}\to\mathsf{C}^{*}_{i-1}\mid i\in[n]\\}$ and
$\\{\psi_{i}:\mathsf{D}^{*}_{i}\to\mathsf{D}^{*}_{i-1}\mid i\in[n]\\}$ are
cochain maps. Let $G_{\bullet}:\mathsf{C}_{\bullet}\to\mathsf{D}_{\bullet}$ be
a _morphism of persistence modules of cochain complexes_ , that is, there
exists a set of cochain maps $G_{i}:\mathsf{C}^{*}_{i}\to\mathsf{D}^{*}_{i}$
for every integer $i$ between $0$ and $n$, and the following diagram commutes
for every $i\in[n]$.

${{\mathsf{C}^{*}_{i}}}$${{\mathsf{D}^{*}_{i}}}$${{\mathsf{C}^{*}_{i-1}}}$${{\mathsf{D}^{*}_{i-1}}}$$\scriptstyle{G_{i}}$$\scriptstyle{\varphi_{i}}$$\scriptstyle{G_{i-1}}$$\scriptstyle{\psi_{i}}$

Applying the cohomology functor $\mathsf{H}^{*}$ to the morphism
$G_{\bullet}\colon\mathsf{C}_{\bullet}\to\mathsf{D}_{\bullet}$ induces another
morphism of persistence modules, namely,
$\mathsf{H}^{*}(G_{\bullet})\colon\mathsf{H}^{*}(\mathsf{C}_{\bullet})\to\mathsf{H}^{*}(\mathsf{D}_{\bullet})$.
Moreover, the image $\operatorname{im}\mathsf{H}^{*}(G_{\bullet})$ is a
persistence module. Like any other single-parameter persistence module, an
image persistence module decomposes uniquely (up to isomorphism) into
intervals called its _barcode_ [29].

As noted in [4], the most natural strategy for computing the image of
$\mathsf{H}^{*}(G_{\bullet})$ is to first write it as

$\operatorname{im}\mathsf{H}^{*}(G_{\bullet})\cong\frac{G_{\bullet}(\mathsf{Z}^{*}(\mathsf{C}_{\bullet}))}{G_{\bullet}(\mathsf{Z}^{*}(\mathsf{C}_{\bullet}))\cap\mathsf{B}^{*}(\mathsf{D}_{\bullet})},$

where the $i$-th terms for the expressions in the numerator and the
denominator are given respectively by

$(G_{\bullet}(\mathsf{Z}^{*}(\mathsf{C}_{\bullet})))_{i}=G_{i}(\mathsf{Z}^{*}(\mathsf{C}_{i}))\mbox{
and
}(G_{\bullet}(\mathsf{Z}^{*}(\mathsf{C}_{\bullet}))\cap\mathsf{B}^{*}(\mathsf{D}_{\bullet}))_{i}=G_{i}(\mathsf{Z}^{*}(\mathsf{C}_{i}))\cap\mathsf{B}^{*}(\mathsf{D}_{i}).$

###  2.3 Tensor products

Given two vector spaces $U$ and $V$ with basis $B_{U}$ and $B_{V}$
respectively, the tensor product $U\otimes V$ is the vector space with the set
of all formal products $u\otimes v$, $u\in B_{U}$, $v\in B_{V}$, as a basis.
One may view $u\otimes v$ as the function sending $(u,v)\in B_{U}\times B_{V}$
to $1$ and all other elements to $0$, and $U\otimes V$ as the space of all
bilinear functions defined on $U\times V$. One may extend the definition of
the tensor product to cochain complexes viewed as graded vector spaces. Given
two cochain complexes $A$ and $B$ (whose respective coboundary maps are both
denoted by $\delta$), the _tensor product_ $A\otimes B$ is the cochain complex
whose degree-$p$ group is

$\left(A\otimes B\right)^{p}=\bigoplus_{i+j=p}A^{i}\otimes B^{j},$

where $A^{i}\otimes B^{j}$ is the tensor product of $\mathbb{Z}_{2}$-vector
spaces, and whose coboundary map is given by the Leibniz rule (specialized to
$\mathbb{Z}_{2}$-vector spaces).

$\delta(a\otimes b)=\delta a\otimes b+a\otimes\delta b,\text{\quad where $a$
and $b$ are vectors in $A^{i}$ and $B^{j}$, respectively.}$

###  2.4 Simplicial cup product

Simplicial cup products connect cohomology groups across degrees. Let $\prec$
be an arbitrary but fixed total order on the vertex set of $\mathsf{K}$. Let
$\xi$ and $\zeta$ be cocycles of degrees $p$ and $q$ respectively. The cup
product of $\xi$ and $\zeta$ is the $(p+q)$-cocycle $\xi\smile\zeta$ whose
evaluation on any $(p+q)$-simplex $\sigma=\\{v_{0},\dots,v_{p+q}\\}$ is given
by

$(\xi\smile\zeta)(\sigma)=\xi(\left\\{{v_{0},...,v_{p}}\right\\})\cdot\zeta(\left\\{{v_{p},\dots,v_{p+q}}\right\\}).$
(1)

This defines a map
$\smile:\mathsf{C}^{p}(\mathsf{K})\times\mathsf{C}^{q}(\mathsf{K})\to\mathsf{C}^{p+q}(\mathsf{K})$,
which assembles to give a map
$\smile:\mathsf{C}^{\ast}(\mathsf{K})\times\mathsf{C}^{\ast}(\mathsf{K})\to\mathsf{C}^{\ast}(\mathsf{K})$.
Using the fact that
$\delta(\zeta\smile\xi)=\delta\xi\smile\zeta+\xi\smile\delta\zeta$, it follows
that $\smile$ induces a map
$\smile:\mathsf{H}^{\ast}(\mathsf{K})\times\mathsf{H}^{\ast}(\mathsf{K})\to\mathsf{H}^{\ast}(\mathsf{K})$.
It can be shown that the map $\smile$ is independent of the ordering $\prec$.

Moreover, using the universal property for tensor products and linearity, the
bilinear maps for

$\smile:\mathsf{C}^{p}(\mathsf{K})\times\mathsf{C}^{q}(\mathsf{K})\to\mathsf{C}^{p+q}(\mathsf{K})\text{
\,\, assemble to give a linear map
\,\,}\smile:\mathsf{C}^{*}(\mathsf{K})\otimes\mathsf{C}^{*}(\mathsf{K})\to\mathsf{C}^{*}(\mathsf{K}).$

and the bilinear maps for

$\smile:\mathsf{H}^{p}(\mathsf{K})\times\mathsf{H}^{q}(\mathsf{K})\to\mathsf{H}^{p+q}(\mathsf{K})\text{
\,\, assemble to give a linear map
\,\,}\smile:\mathsf{H}^{*}(\mathsf{K})\otimes\mathsf{H}^{*}(\mathsf{K})\to\mathsf{H}^{*}(\mathsf{K}).$

Finally, we state two well-known facts about cup products that are used
throughout this paper.

######  Theorem 2.1 ([19]).

The cup product with $\mathbb{Z}_{2}$ coefficients is commutative, that is,
$[\xi]\smile[\zeta]=[\zeta]\smile[\xi]$ for all
$[\xi],[\zeta]\in\mathsf{H}^{\ast}(\mathsf{K})$.

######  Theorem 2.2 (Naturality of the cup product [19]).

Let $f:\mathsf{K}\to\mathsf{L}$ be a simplicial map and let
$f^{\ast}:\mathsf{H}^{\ast}(\mathsf{L})\to\mathsf{H}^{\ast}(\mathsf{K})$ be
the induced map on cohomology. Then,
$f^{\ast}([\xi]\smile[\zeta])=f^{\ast}([\xi])\smile f^{\ast}([\zeta])$ for all
$[\xi],[\zeta]\in\mathsf{H}^{\ast}(\mathsf{K})$.

#### Graded algebra structure.

For a simplicial complex $\mathsf{K}$, since the cup product defines a
bilinear map
$\smile:\mathsf{H}^{p}(\mathsf{K})\times\mathsf{H}^{q}(\mathsf{K})\to\mathsf{H}^{p+q}(\mathsf{K})$
of vector spaces it turns the total cohomology vector space
$\mathsf{H}^{*}(\mathsf{K}):=\bigoplus_{p\in\mathbb{N}}\mathsf{H}^{p}(\mathsf{K})$
into a graded algebra $(\mathsf{H}^{*}(\mathsf{K}),+,\smile)$. The map
$\mathsf{K}\mapsto\mathsf{H}^{*}(\mathsf{K})$ defines a contravariant functor
from the category of simplicial complexes to the category of graded algebras.

#### Tensor product image persistence.

Observe that the tensor product of persistence modules is a persistence
modules; see [26, Section 2.2] and [8, Section 3.2] for details. Now, consider
the following homomorphism given by cup products:

$\smile_{\bullet}:\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\mathsf{C}^{*}(\mathsf{K}_{\bullet})\to\mathsf{C}^{*}(\mathsf{K}_{\bullet}).$
(2)

Taking $G_{\bullet}=\smile_{\bullet}$ in the definition of image persistence
module, we get a persistence module, denoted by
$\operatorname{im}\mathsf{H}^{*}(\smile_{\bullet})$, which is the same as the
persistent cup module introduced in [14]. Our aim is to compute its barcode
denoted by $B(\operatorname{im}\mathsf{H}^{*}(\smile_{\bullet}))$.

###  2.5 Barcodes

Let $\mathsf{K}_{\bullet}$ denote a simplicial filtration on the index set
$I=\\{0,1,\ldots,n\\}$. Assume that the filtration is simplex-wise, that is,
$\mathsf{K}_{i}\setminus\mathsf{K}_{i-1}$ is a single simplex. Consider the
persistence module $\mathsf{H}^{\ast}_{\bullet}$ obtained by applying the
cohomology functor $\mathsf{H}^{\ast}$ on the filtration
$\mathsf{K}_{\bullet}$, that is,
$\mathsf{H}^{\ast}_{i}=\mathsf{H}^{\ast}(\mathsf{K}_{i})$. The structure maps
$\\{\varphi^{\ast}_{i}:\mathsf{H}^{\ast}(\mathsf{K}_{i})\to\mathsf{H}^{\ast}(\mathsf{K}_{i-1})\mid
i\in[n]\\}$ for this module are induced by the cochain maps
$\\{\varphi_{i}:\mathsf{C}^{*}(\mathsf{K}_{i})\to\mathsf{C}^{*}(\mathsf{K}_{i-1})\mid
i\in[n]\\}$. Because of the assumption that $\mathsf{K}_{\bullet}$ is simplex-
wise, each linear map $\varphi^{\ast}_{i}$ is either injective with a cokernel
of dimension one, or surjective with a kernel of dimension one, but not both.
Such a persistence module $\mathsf{H}^{\ast}_{\bullet}$ decomposes into
interval modules supported on a unique set of open-closed intervals, namely
the barcode of $\mathsf{H}^{\ast}_{\bullet}$ written as
$B(\mathsf{H}^{\ast}_{\bullet})=\\{(d_{i},b_{i}]\,|\,b_{i}\geq
d_{i},b_{i},d_{i}\in I\\}$. Notice that since $I$ is the indexing poset of
$\mathsf{K}^{\ast}_{\bullet}$, $I^{\operatorname*{op}}$ is the indexing poset
of $\mathsf{H}^{\ast}_{\bullet}$. For $r>s$, we define
$\varphi^{\ast}_{r,s}=\varphi^{\ast}_{s+1}\circ\cdots\circ\varphi^{\ast}_{r-1}\circ\varphi^{\ast}_{r}$
and
$\varphi_{r,s}=\varphi_{s+1}\circ\cdots\circ\varphi_{r-1}\circ\varphi_{r}$.

######  Proposition 2.1.

Let
$\\{\varphi^{\ast}_{i}\colon\mathsf{H}^{\ast}(\mathsf{K}^{*}_{i})\to\mathsf{H}^{\ast}(\mathsf{K}^{*}_{i-1})\mid
i\in[n]\\}$ denote the structure map of the module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$. The structure map for the
persistent cup module $\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet})$
is the restriction of $\varphi^{\ast}_{\bullet}$ to the image of
$\smile_{\bullet}$.

###### Proof.

Recall that $\varphi^{\ast}_{i}$ denotes the induced map on cohomology
$\mathsf{H}^{*}(\mathsf{K}_{i})\to\mathsf{H}^{*}(\mathsf{K}_{i-1})$. Let
$\varphi_{i}^{\otimes}$ denote the tensor product of the map
$\varphi^{\ast}_{i}$ with itself.

Applying the cohomology functor to the map

$\smile_{\bullet}\colon\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\mathsf{C}^{*}(\mathsf{K}_{\bullet})\to\mathsf{C}^{*}(\mathsf{K}_{\bullet}),$
(3)

and using the Künneth theorem for cohomology over fields,
$\mathsf{H}^{\ast}(\mathsf{C}^{*}\otimes\mathsf{D}^{*})\cong\mathsf{H}^{\ast}(\mathsf{C}^{*})\otimes\mathsf{H}^{\ast}(\mathsf{D}^{*})$111The
tensor product on the right hand side is a tensor product of graded vector
spaces., we obtain the following commutative diagram:

${{\mathsf{H}^{\ast}(\mathsf{K}_{i})\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i-1})\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i-1})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i-1})}}$$\scriptstyle{\varphi_{i}^{\otimes}}$$\scriptstyle{\smile}$$\scriptstyle{\smile}$$\scriptstyle{\varphi^{\ast}_{i}}$

For cocycle classes $[\alpha],[\beta]\in\mathsf{H}^{\ast}(\mathsf{K})$, by the
naturality of the cup product,
$\varphi^{\ast}_{i}([\alpha])\smile\varphi^{\ast}_{i}([\beta])=\varphi^{\ast}_{i}([\alpha]\smile[\beta])$.
Since,
$[\alpha]\smile[\beta]\in\operatorname{im}\mathsf{H}^{\ast}(\smile_{i})$ is
mapped to an element in $\operatorname{im}\mathsf{H}^{\ast}(\smile_{i-1})$,
the structure map for the persistent cup module
$\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet})$ is the restriction of
$\varphi^{\ast}_{\bullet}$ to the image of $\smile_{\bullet}$. ∎

######  Definition 2.3.

For any $i\in\\{0,\dots,n\\}$, a nontrivial cocycle
$\zeta\in\mathsf{Z}^{\ast}(\mathsf{K}_{i})$ is said to be a _product cocycle
of $\mathsf{K}_{i}$_ if
$[\zeta]\in\operatorname{im}\mathsf{H}^{*}(\smile_{i})$.

######  Proposition 2.2.

For a filtration $\mathcal{F}$ of simplicial complex $\mathsf{K}$, the birth
indices of $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ are a
subset of the birth indices of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$,
and the death indices of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ are a subset of the
death indices of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$.

###### Proof.

Let $(d_{i},b_{i}]$ and $(d_{j},b_{j}]$ be (not necessarily distinct)
intervals in $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, where $b_{j}\geq
b_{i}$. Let $\xi_{i}$ be a representative for $(d_{i},b_{i}]$ and $\xi_{j}$ be
a representative for $(d_{j},b_{j}]$. If $\xi_{i}\smile\xi_{j}^{b_{i}}$ is
trivial, then by the naturality of cup product,
$\varphi_{b_{i},r}(\xi_{i}\smile\xi_{j}^{b_{i}})=\varphi_{b_{i},r}(\xi_{i})\smile\varphi_{b_{i},r}(\xi_{j}^{b^{i}})=\xi_{i}^{r}\smile\xi_{j}^{r}$
is trivial $\forall r<b_{i}$. Writing contrapositively, if $\exists r<b_{i}$
for which $\xi_{i}^{r}\smile\xi_{j}^{r}$ is nontrivial, then
$\xi_{i}\smile\xi_{j}^{b_{i}}$ is nontrivial. Noting that
$\operatorname{im}\mathsf{H}^{*}(\smile_{\ell})$ for any
$\ell\in\\{0,\dots,n\\}$ is generated by
$\\{[\xi_{i}^{\ell}]\smile[\xi_{j}^{\ell}]\mid\xi_{i},\xi_{j}\in\Omega_{\mathsf{K}}\\}$,
it follows that an index $b$ is the birth index of an interval in
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ only if it is the
birth index of an interval in $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$,
proving the first claim.

Let $\Omega^{\prime}_{j+1}=\\{[\tau_{1}],\dots,[\tau_{k}]\\}$ be a basis for
$\operatorname{im}\mathsf{H}^{*}(\smile_{j+1})$. Then, $\Omega^{\prime}_{j+1}$
extends to a basis $\Omega_{j+1}$ of $\mathsf{H}^{\ast}(\mathsf{K}_{j+1})$. If
$j$ is not a death index of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, then
$\varphi_{j+1}(\tau_{1}),\dots,\varphi_{j+1}(\tau_{k})$ are all nontrivial and
linearly independent. Using Proposition 2.1, it follows that $j$ is not a
death index of $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$,
proving the second claim. ∎

######  Corollary 2.1.

If $d$ is a death index of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$, then at most one
bar of $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ has death
index $d$.

###### Proof.

Using the fact that if the rank of a linear map $f:V_{1}\to V_{2}$ is $\dim
V_{1}-1$, then the rank of $f|_{W_{1}}$ for a subspace $W_{1}\subset V_{1}$ is
at least $\dim W_{1}-1$, from Proposition 2.1 it follows that if
$\dim\mathsf{H}^{*}(\mathsf{K}_{d})=\dim\mathsf{H}^{*}(\mathsf{K}_{d+1})-1$,
then

$\dim(\operatorname{im}\mathsf{H}^{*}(\smile_{d}))+1\geq\dim(\operatorname{im}\mathsf{H}^{*}(\smile_{d+1}))\geq\dim(\operatorname{im}\mathsf{H}^{*}(\smile_{d}))\quad\text{
proving the claim.}\qed$

######  Remark 1.

The persistent cup module is a submodule of the original persistence module.
Let $\dim(\operatorname{im}\mathsf{H}^{p}_{i})$ denote
$\dim(\operatorname{im}\mathsf{H}^{p}(\smile_{i}))$. In the barcode
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$, if
$\mathsf{K}_{i}=\mathsf{K}_{i-1}\cup\\{\sigma^{p}\\}$, then either (i)
$\dim(\operatorname{im}\mathsf{H}^{p}_{i})>\dim(\operatorname{im}\mathsf{H}^{p}_{i-1})$,
or (ii)
$\dim(\operatorname{im}\mathsf{H}^{p-1}_{i})<\dim(\operatorname{im}\mathsf{H}^{p-1}_{i-1})$,
or (iii) there is no change:
$\dim(\operatorname{im}\mathsf{H}^{p}_{i})=\dim(\operatorname{im}\mathsf{H}^{p}_{i-1})$
and
$\dim(\operatorname{im}\mathsf{H}^{p-1}_{i})=\dim(\operatorname{im}\mathsf{H}^{p-1}_{i-1})$.
The decrease (increase) in persistent cup modules happens only if there is a
decrease (increase) in ordinary cohomology. Multiple bars of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ may have the same
birth index. But, if $i$ is a death index, then Corollary 2.1 says that it can
be so for at most one bar in
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$.

##  3 Algorithm for computing the barcode of persistent cup module

Our goal is to compute the barcode of the persistent cup module
$\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet})$, which being an image
module is a submodule of the cohomology persistence module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$. The vector space
$\operatorname{im}\mathsf{H}^{\ast}(\smile_{i})$ is a subspace of the
cohomology vector space $\mathsf{H}^{\ast}(\mathsf{K}_{i})$. Let us call this
subspace the _cup space_ of $\mathsf{H}^{\ast}(\mathsf{K}_{i})$. Our algorithm
keeps track of a basis of this cup space as it processes the filtration in the
reverse order. This backward processing is needed because the structure maps
between the cup spaces are induced by restrictions
$\varphi_{j,i}\colon\mathsf{C}^{*}(\mathsf{K}_{j})\to\mathsf{C}^{*}(\mathsf{K}_{i})$
that are, in turn, induced by inclusions
$\mathsf{K}_{j}\supseteq\mathsf{K}_{i}$, $i\leq j$. In particular, a
cocycle/coboundary in $\mathsf{K}_{j}$ is taken to its restriction in
$\mathsf{K}_{i}$ for $i\leq j$. Owing to Proposition 2.1, our algorithm keeps
track of the birth and death of the cocycle classes in the cup spaces as it
proceeds through the restrictions in the reverse filtration order. We maintain
a basis of nontrivial product cocycles in a matrix $\mathbf{S}$ whose classes
$S$ form a basis for the cup spaces. In particular, cocycles in $\mathbf{S}$
get born and die with birth and death of the elements in cup spaces.

A cocycle class from $\mathsf{H}^{\ast}(\mathsf{K}_{i})$ may enter the cup
space $\operatorname{im}\mathsf{H}^{\ast}(\smile_{i})$ signalling a birth or
may leave (becomes zero) the cohomology vector space and hence the cup space
signalling a death. Interestingly, multiple births may happen, meaning that
multiple independent cocycle classes may enter the cup space, whereas at most
a single class can die because of Corollary 2.1. To determine which class from
the cohomology vector space enters the cup space and which one leaves it, we
make use of the barcode of the module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$. However, the classes of the the
bases maintained in $\mathbf{H}$ do not directly provide bases for the cup
spaces. Hence, we need to compute and maintain $\mathbf{S}$ separately, of
course, with the help of $\mathbf{H}$.

Let us consider the case of birth first. Suppose that a cocycle $\xi$ at
degree $p$ is born at index $k=b_{i}$ for
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$. With $\xi$, a set of product
cocycles are born in some of the degrees $p+q$ for $q\geq 1$. To detect them,
we first compute a set of candidate cocycles by taking the cup product of
cocycles $\xi\smile\zeta$, for all cocycles $\zeta\in\mathbf{H}$ at $b_{i}$
which can potentially augment the basis maintained in $\mathbf{S}$. The ones
among the candidate cocycles whose classes are independent w.r.t. the current
basis maintained in $\mathbf{S}$ are determined to be born at $b_{i}$. Next,
consider the case of death. A product cocycle $\zeta$ in degree $r$ ceases to
exist if it becomes linearly dependent of other product cocycles. This can
happen only if the dimension of $\mathsf{H}^{r}(\mathsf{K}_{\bullet})$ itself
has reduced under the structure map going from $k+1$ to $k$. It suffices to
check if any of the nontrivial cocycles in $\mathbf{S}$ have become linearly
dependent or trivial after applying restrictions. In what follows, we use
$\deg(\zeta)$ to denote the degree of a cocycle $\zeta$.

Algorithm CupPers ($\mathsf{K}_{\bullet}$)

  * •

Step 1. Compute barcode $B(\mathcal{F})=\\{(d_{i},b_{i}]\\}$ of
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ with representative cocycles
$\xi_{i}$; Let $\mathbf{H}=\\{\xi_{i}\mid[\xi_{i}]\text{ essential and
}\deg(\xi_{i})>0\\}$; Initialize $\mathbf{S}$ with the coboundary matrix
$\partial^{\perp}$ obtained by taking transpose of the boundary matrix
$\partial$;

  * •

Step 2. For $k:=n$ to $1$ do

    * –

Restrict the cocycles in $\mathbf{S}$ and $\mathbf{H}$ to index $k$;

    * –

Step 2.1 If $k=b_{i}$ ($k$ is a birth-index) for some $i$ and
$\deg(\xi_{i})>0$ then

      * *

Step 2.1.1 If $k\not=n$, update $\mathbf{H}:=[\mathbf{H}\mid\xi_{i}]$

      * *

Step 2.1.2 For every $\xi_{j}\in\mathbf{H}$

        1. i.

If $(\zeta\leftarrow\xi_{i}\smile\xi_{j})\not=0$ and $\zeta$ is independent in
$\mathbf{S}$, then $\mathbf{S}:=[\mathbf{S}\mid\zeta]$ with column $\zeta$
annotated as $\zeta\cdot{\rm birth}:=k$ and $\zeta\cdot{\rm rep@birth}:=\zeta$

    * –

Step 2.2 If $k=d_{i}$ ($k$ is a death-index) for some $i$ and
$\deg(\xi_{i})>0$ then

      * *

Step 2.2.1 Reduce $\mathbf{S}$ with left-to-right column additions

      * *

Step 2.2.2 If a nontrivial cocycle $\zeta$ is zeroed out, remove $\zeta$ from
$\mathbf{S}$, generate the bar-representative pair $\\{(k,\zeta\cdot{\rm
birth}],\zeta\cdot{\rm rep@birth}\\}$

      * *

Step 2.2.3 Update $\mathbf{H}$ by removing the column $\xi_{i}$

Algorithm CupPers describes this algorithm with a pseudocode. First, in step
1, we compute the barcode of the cohomology persistence module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ along with a persistent cohomology
basis. This can be achieved in $O(n^{3})$ time using either the annotation
algorithm [6, 16] or the pCoH algorithm [15]. The basis $H$ is maintained with
the matrix $\mathbf{H}$ whose columns are cocycles represented as the support
vectors on simplices. The matrix $\mathbf{H}$ is initialized with all cocycles
$\xi_{i}$ that are computed as representatives of the bars $(d_{i},b_{i}]$ for
the module $\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ which get born at the
first (w.r.t. reverse order) complex $\mathsf{K}_{n}=\mathsf{K}$. The matrix
$\mathbf{S}$ is initialized with the coboundary matrix $\partial^{\perp}$ with
standard cochain basis. Subsequently, nontrivial cocycle vectors are added to
$\mathbf{S}$. The classes of the nontrivial cocycles in matrix $\mathbf{S}$
form a basis $S$ for the cup space at any point in the course of the
algorithm.

In step 2, we process cocycles in the reverse filtration order. At each index
$k$, we do the following. If $k$ is a birth index for a bar $(-,b_{i}]$ (Step
2.1), that is, $k=b_{i}$ for a bar with representative $\xi_{i}$ in the
barcode of $\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$, first we augment
$\mathbf{H}$ with $\xi_{i}$ to keep it current as a basis for the vector space
$\mathsf{H}^{\ast}(\mathsf{K}_{k})$ (Step 2.2.1). Now, a new bar for the
persistent cup module can potentially be born at $k$. To determine this, we
take the cup product of $\xi_{i}$ with all cocycles in $\mathbf{H}$ and check
if the cup product cocycle is non-trivial and is independent of the cocycles
in $\mathbf{S}$. If so, a product cocycle is born at $k$ that is added to
$\mathbf{S}$ (step 2.1.2). To check this independence, we need $\mathbf{S}$ to
have current coboundary basis along with current nontrivial product cocycle
basis $S$ that are both updated with restrictions.

######  Remark 2.

Restrictions in $\mathbf{H}$ and $\mathbf{S}$ are implemented by zeroing out
the corresponding row associated to the simplex $\sigma_{i}$ when we go from
$\mathsf{K}_{i}$ to $\mathsf{K}_{i-1}$ and
$\mathsf{K}_{i}\setminus\mathsf{K}_{i-1}=\\{\sigma_{i}\\}$.

If $k$ is a death index (Step 2.2), potentially the class of a product cocycle
from $\mathbf{S}$ can be a linear combination of the classes of other product
cocycles after $\mathbf{S}$ has been updated with restriction. We reduce
$\mathbf{S}$ with left-to-right column additions and detect the column that is
zeroed out (Step 2.2.1). If the column $\zeta$ is zeroed out, the class
$[\zeta]$ dies at $k$ and we generate a bar for the persistent cup module with
death index $k$ and birth index equal to the index when $\zeta$ was born (Step
2.2.2). Finally, we update $\mathbf{H}$ by removing the column for $\xi_{i}$
(Step 2.2.3).

###  3.1 Rank functions and barcodes

Let $P\subseteq\mathbb{Z}$ be a finite set with induced poset structure from
$\mathbb{Z}$. Let $\mathbf{Int}(P)$ denote the set of all intervals in $P$.
Recall that $P^{\operatorname*{op}}$ denotes the opposite poset category.
Given a $P^{\operatorname*{op}}$-indexed persistence module $V_{\bullet}$, the
rank function $\mathsf{rk}_{V_{\bullet}}:\mathbf{Int}(P)\rightarrow\mathbb{Z}$
assigns to each interval $I=[a,b]\in\mathbf{Int}(P)$ the rank of the linear
map $V_{b}\rightarrow V_{a}$. It is well known that (see [11, 17]) the barcode
of $V_{\bullet}$ viewed as a function
$\mathsf{Dgm}_{V_{\bullet}}:\mathbf{Int}(P)\rightarrow\mathbb{Z}$ can be
obtained from the rank function by the inclusion-exclusion formula:

$\mathsf{Dgm}_{V_{\bullet}}([a,b])=\mathsf{rk}_{V_{\bullet}}[a,b]-\mathsf{rk}_{V_{\bullet}}[a-1,b]+\mathsf{rk}_{V_{\bullet}}[a,b+1]-\mathsf{rk}_{V_{\bullet}}[a-1,b+1]$
(4)

To prove the correctness of Algorithm CupPers, we use the following elementary
fact.

######  Fact 1.

A class that is born at an index greater than or equal to $b$ dies at $a$ if
and only if
$\mathsf{rk}_{V_{\bullet}}([a,b])<\mathsf{rk}_{V_{\bullet}}([a+1,b])$.

###  3.2 Correctness of Algorithm CupPers

######  Theorem 3.1.

Algorithm CupPers correctly computes the barcode of the persistent cup module.

###### Proof.

In what follows, we abuse notation by denoting the restriction at index $k$ of
a cocycle $\zeta$ born at $b$ also by the symbol $\zeta$. That is, index-wise
restrictions are always performed, but not always explicitly mentioned. We use
$\\{\xi_{i}\\}$ to denote cocycles in the persistent cohomology basis computed
in Step 1. To prove the theorem, we use induction to show that for an
arbitrary birth index $b$ in $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, if
all bars for the persistent cup module with birth indices $b^{\prime}>b$ are
correctly computed, then the bars beginning with $b$ are also correctly
computed.

To begin with we note that in Algorithm CupPers, as a consequence of
Proposition 2.2, we need to check if an index $k$ is a birth (death) index of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ only when it is a
birth (death) index of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$. Also,
from Corollary 2.1, we know that at most one cycle dies at a death index of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}))$ (justifying Step
2.2.2).

We now introduce some notation. In what follows, we denote the persistent cup
module by $V_{\bullet}$. For a birth index $b$, let $S_{b}$ be the cup space
at index $b$. Let $C_{b}$ be the vector space of the product cocycle classes
created at index $b$. In particular, the classes in $C_{b}$ are linearly
independent of classes in $S_{b+1}$. For a birth index $b<n$, $S_{b}$ can be
written as a direct sum $S_{b}=S_{b+1}\oplus C_{b}$. For index $n$, we set
$S_{n}=C_{n}$. Then, for a birth index $b\in\\{0,\dots,n\\}$, $C_{b}$ is a
subspace of $\mathsf{H}^{\ast}(\mathsf{K}_{b})$. $C_{b}$ can be written as:

$C_{b}=\begin{cases}\langle[\xi_{i}]\smile[\xi_{j}]\mid\xi_{i},\xi_{j}\text{
are essential cocycles of
}\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})\rangle&\text{ if }b=n\\\
\langle[\xi_{i}]\smile[\xi_{j}]\mid\xi_{i}\text{ is born at $b$,}\text{ and
}\xi_{j}\text{ is born at an index }\geq b\rangle&\text{ if }b<n\end{cases}$

For a birth index $b$, let $\mathbf{C}_{b}$ be the submatrix of $\mathbf{S}$
formed by representatives whose classes generate $C_{b}$, which augments
$\mathbf{S}$ in Step 2.1.2 (i) when $k=b$ in the for loop. The cocycles in
$\mathbf{C}_{b}$ are maintained for $k\in\\{b,\dots,1\\}$ via subsequent
restrictions to index $k$. Let $\mathbf{S}_{b}$ be the submatrix of
$\mathbf{S}$ containing representative product cocycles that are born at index
$\geq b$. Clearly, $\mathbf{C}_{b}$ is a submatrix of $\mathbf{S}_{b}$ for
$b<n$, and $\mathbf{C}_{n}=\mathbf{S}_{n}$.

Let $\operatorname*{DP}_{b}$ be the set of filtration indices for which the
cocycles in $\mathbf{C}_{b}$ become successively linearly dependent to other
cocycles in $\mathbf{S}_{b}$. That is, $d\in\operatorname*{DP}_{b}$ if and
only if there exists a cocycle $\zeta$ in $\mathbf{C}_{b}$ such that $\zeta$
is independent of all cocycles to its left in matrix $\mathbf{S}$ at index
$d+1$, but $\zeta$ is either trivial or a linear combination of cocycles to
its left at index $d$.

For the base case, we show that the death indices of the essential bars are
correctly computed. First, we observe that for all
$d\in\operatorname*{DP}_{n}$,
$\mathsf{rk}_{V_{\bullet}}([d,n])=\mathsf{rk}_{V_{\bullet}}([d+1,n])-1$. Using
Fact 1, it follows that the algorithm computes the correct barcode for
persistent cup module only if the indices in $\operatorname*{DP}_{n}$ are the
respective death indices for the essential bars. Since the leftmost columns of
$\mathbf{S}$ are coboundaries from $\partial^{\perp}$ followed by cocycles
from $\mathbf{C}_{n}$, and since we perform only left-to-right column
additions in Step 2.2.1 to zero out cocycles in $\mathbf{C}_{n}$, the base
case holds true. By (another) simple inductive argument, it follows that the
computation of indices in $\operatorname*{DP}_{n}$ does not depend on the
specific ordering of representatives within $\mathbf{C}_{n}$.

Let $b<n$ be a birth index in $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$.
For our induction hypothesis we assume that for every birth index
$b^{\prime}>b$ the indices in $\operatorname*{DP}_{b^{\prime}}$ are the
respective death indices of the bars of the persistent cup module barcode born
at $b^{\prime}$.

By construction, the cocycles $\\{\zeta_{1},\zeta_{2},\dots\\}$ in
$\mathbf{S}$ are sequentially arranged by the following rule: If $\zeta_{i}$
and $\zeta_{j}$ are two representative product cocycles in $\mathbf{S}$, then
$i<j$ if the birth index $b_{i}$ of the interval represented by $\zeta_{i}$ is
greater than the birth index $b_{j}$ of the interval represented by
$\zeta_{j}$. Then, as a consequence of the induction hypothesis, for a cocycle
$\zeta\in\mathbf{C}_{b}\setminus\mathbf{S}_{b}$, we assign the correct birth
index to the interval represented by $\zeta$ only if $\zeta$ can be written as
a linear combination of cocycles to its left in matrix $\mathbf{S}$.

Now, suppose that at some index $d\in\operatorname*{DP}_{b}$ we can write a
cocycle $\zeta$ in submatrix $\mathbf{C}_{b}$ as a linear combination of
cocycles to its left in $\mathbf{S}$. For such a $d\in\operatorname*{DP}_{b}$,
$\mathsf{rk}_{V_{\bullet}}([d,b])=\mathsf{rk}_{V_{\bullet}}([d+1,b])-1$.
Hence, using Fact 1, a birth index $\geq b$ must be paired with $d$.

However, since
$\operatorname*{DP}_{b}\cap\operatorname*{DP}_{b^{\prime}}=\emptyset$ for
$b<b^{\prime}$, it follows from the inductive hypothesis that the only birth
index that can be paired to $d$ is $b$. Moreover, since we take restrictions
of cocycles in $\mathbf{S}$, all cocycles in $\mathbf{C}_{b}$ eventually
become trivial or linearly dependent on cocycles to its left in $\mathbf{S}$.
So, $\operatorname*{DP}_{b}$ has the same cardinality as the number of cocycle
vectors in $\mathbf{C}_{b}$, and all the bars that are born at $b$ must die at
some index in $\operatorname*{DP}_{b}$. As a final remark, it is easy to check
that the computation of indices in $\operatorname*{DP}_{b}$ is independent of
the specific ordering of representatives within $\mathbf{S}_{b}$ by a simple
inductive argument. ∎

#### Time complexity of CupPers.

Let the input simplex-wise filtration have $n$ additions and hence the complex
$\mathsf{K}$ have $n$ simplices. Step 1 of CupPers can be executed in
$O(n^{3})$ time using algorithms in [6, 15]. The outer loop in step 2 runs
$O(n)$ times. For each death index in Step 2.2, we perform left-to-right
column additions as done in the standard persistence algorithm to bring the
matrix in reduced form. Hence, for each death index, Step 2.2 can be performed
in $O(n^{3})$ time. Since there are at most $O(n)$ death indices, the total
cost for Step 2.2 in the course of the algorithm is $O(n^{4})$.

Step 2.1 apparently incurs higher cost than Step 2.2. This is because at each
birth point, we have to test the product of multiple pairs of cocycles stored
in $\mathbf{H}$. However, we observe that there are at most $O(n^{2})$
products of pairs of representative cocycles that are each computed and tested
for linear independence at most once. In particular, if $\xi_{i}$ represents
$(d_{i},b_{i}]$ and $\xi_{j}$ represents $(d_{j},b_{j}]$ with $b_{i}\leq
b_{j}$, then the product $\xi_{i}\smile\xi_{j}$ is computed and tested for
independence if and only if $b_{i}>d_{j}$ and the test happens at index
$b_{i}$. Using Equation 1, computing $\xi_{i}\smile\xi_{j}$ takes linear time.
So the cost of computing the $O(n^{2})$ products is $O(n^{3})$. Moreover,
since each independence test takes $O(n^{2})$ time with the assumption that
$\mathbf{S}$ is kept reduced all the time, Step 2.1 can be implemented to run
in $O(n^{4})$ time over the entire algorithm.

Finally, since restrictions of cocycles in $\mathbf{S}$ and $\mathbf{H}$ are
computed by zeroing out corresponding rows, the total time to compute
restrictions over the course of the algorithm is $O(n^{2})$. Combining all
costs, we get an $O(n^{4})$ complexity bound for CupPers.

##  4 Algorithm for computing the barcode of persistent $k$-cup modules

While considering the persistent $1$-cup modules is the natural first step, it
must be noted that the persistent invariants thus computed can still be
enriched by considering persistent $k$-cup modules. As a next step to more
refined computation from the cup product structure, we consider image
persistence of the $k$-fold tensor products.

### Image persistence of $k$-fold tensor product.

Here, one computes the image persistence of the map

$\smile_{\bullet}^{k}:\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\dots\otimes\mathsf{C}^{*}\to\mathsf{C}^{*}(\mathsf{K}_{\bullet})$
(5)

where the tensor product is taken $k$ times. Taking
$G_{\bullet}\,\,=\,\,\smile_{\bullet}^{k}$ in the definition of image
persistence module, we get the persistence module
$\operatorname{im}\mathsf{H}^{*}(\smile_{\bullet}^{k})$ which is same as the
persistent $k$-cup module introduced in [14]. Our aim is to compute its
barcode $B(\operatorname{im}\mathsf{H}^{*}(\smile_{\bullet}^{k}))$. The image
persistence of maps $\smile_{\bullet}^{k}$ for $k\in[N]$ efficiently recovers
the information in the persistent cup-length in a mathematically principled
manner.

######  Definition 4.1.

For any $i\in\\{0,\dots,n\\}$, a nontrivial cocycle
$\zeta\in\mathsf{Z}^{\ast}(\mathsf{K}_{i})$ is said to be an _order- $k$
product cocycle of $\mathsf{K}_{i}$_ if
$[\zeta]\in\operatorname{im}\mathsf{H}^{*}(\smile_{i}^{k})$.

###  4.1 Computing barcode of persistent $k$-cup modules

The order-$k$ product cocycles can be viewed recursively as cup products of
order-$(k-1)$ product cocycles with another cocycle. This suggests a recursive
algorithm for computing the barcode of persistent $k$-cup module: compute the
barcode of persistent $(k-1)$-cup module recursively and then using the birth
and death of the bars thus computed, compute the barcode of persistent $k$-cup
module just like the way we computed order-$2$ product persistence using the
bars for ordinary cohomology persistence. In the algorithm OrderkCupPers, we
assume that the barcode with representatives for the cohomology module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$ has been already computed which is
denoted by the pair of sets $(\\{(d_{i,1},b_{i,1}],\\{\xi_{i,1}\\})$. For
simplicity in description, we assume that this pair is accessed by the
recursive algorithm as a global variable and thus is not passed at each
recursion level. At each recursion level $k$, the algorithm computes the
barcode-representative pair denoted as
$(\\{(d_{i,k},b_{i,k}],\\{\xi_{i,k}\\})$. Here, the cocycles $\xi_{i,k}$ are
the initial cocycle representatives (before restrictions) for the bars
$(d_{i,k},b_{i,k}]$. At the time of their respective births $b_{i,k}$, they
are stored in the field $\xi_{i,k}\cdot{\rm rep@birth}$.

Algorithm OrderkCupPers ($\mathsf{K}_{\bullet}$,$k$)

  * •

Step 1. If $k=2$, return the barcode with representatives
$\\{(d_{i,2},b_{i,2}],\xi_{i,2}\\}$ computed by CupPers on
$\mathsf{K}_{\bullet}$
else $\\{(d_{i,k-1},b_{i,k-1}],\xi_{i,k-1}\\}$ $\leftarrow$
OrderkCupPers($\mathsf{K}_{\bullet}$, $k-1$)
Let $\mathbf{H}=\\{\xi_{i,1}\mid[\xi_{i,1}]\text{ essential and
}\deg(\xi_{i,1})>0\\}$; $\mathbf{R}:=\\{\xi_{i,k-1}\mid b_{i,k-1}=n\\}$;
$\mathbf{S}:=\partial^{\perp}$;

  * •

Step 2. For $\ell:=n$ to $1$ do

    * –

Restrict the cocycles in $\mathbf{S}$, $\mathbf{R}$, and $\mathbf{H}$ to index
$\ell$;

    * –

Step 2.1 If $\ell=b_{r,1}$ (i.e., $\ell$ is a birth-index) and
$\deg(\xi_{r,1})>0$ for some $r$ then

      * *

Step 2.1.1 If $\ell\not=n$, update $\mathbf{H}:=[\mathbf{H}\mid\xi_{r,1}]$

      * *

Step 2.1.2 For every $\xi_{j,k-1}\in\mathbf{R}$

        1. i.

If $(\zeta\leftarrow\xi_{r,1}\smile\xi_{j,k-1})\not=0$ and $\zeta$ is
independent in $\mathbf{S}$, then $\mathbf{S}:=[\mathbf{S}\mid\zeta]$ with
column $\zeta$ annotated as $\zeta\cdot{\rm birth}:=\ell$ and $\zeta\cdot{\rm
rep@birth}:=\zeta$

    * –

Step 2.2 For all $s$ such that $\ell=b_{s,k-1}$

      * *

Step 2.2.1 If $\ell\not=n$, update $\mathbf{R}:=[\mathbf{R}\mid\xi_{s,k-1}]$

      * *

Step 2.2.2 For every $\xi_{i,1}\in\mathbf{H}$

        1. i.

If $(\zeta\leftarrow\xi_{s,k-1}\smile\xi_{i,1})\not=0$ and $\zeta$ is
independent in $\mathbf{S}$, then $\mathbf{S}:=[\mathbf{S}\mid\zeta]$ with
column $\zeta$ annotated as $\zeta\cdot{\rm birth}:=\ell$ and $\zeta\cdot{\rm
rep@birth}:=\zeta$

    * –

Step 2.3 If $\ell=d_{i,1}$ (i.e. $\ell$ is a death-index) and
$\deg(\xi_{i,1})>0$ for some $i$ then

      * *

Step 2.3.1 Reduce $\mathbf{S}$ with left-to-right column additions

      * *

Step 2.3.2 If a nontrivial cocycle $\zeta$ is zeroed out, remove $\zeta$ from
$\mathbf{S}$, generate the bar-representative pair $\\{(\ell,\zeta\cdot{\rm
birth}],\zeta\cdot{\rm rep@birth}\\}$

      * *

Step 2.3.3 Remove the column $\xi_{i,1}$ from $\mathbf{H}$

      * *

Step 2.3.4 Remove the column $\xi_{j,k-1}$ from $\mathbf{R}$ if
$d_{j,k-1}=\ell$ for some $j$

A high-level pseudocode for computing the barcode of persistent $k$-cup module
is given by algorithm OrderkCupPers. First, we call itself recursively to
generate the sets of bar-representative pairs for the persistent $(k-1)$-cup
module. By a similar logic as for the persistent $2$-cup modules, birth and
death of every order-$k$ product cocycle class coincide with a birth and death
respectively for an ordinary cohomology class. Therefore, as before, at each
birth index of the cohomology module, we check if the cup product of a
representative cocycle (maintained in matrix $\mathbf{H}$) with a
representative for persistent $(k-1)$-cup module (maintained in matrix
$\mathbf{R}$) generates a new cocycle in the barcode for persistent $k$-cup
module (Steps 2.1.2(i) and 2.2.2(i)). If so, we note this birth with the
respective cocycle (by annotating the column) and add it to the matrix
$\mathbf{S}$ that maintains a basis for live order-$k$ product cocycles. At
each death point, we check if an order-$k$ product cocycle dies by checking if
the matrix $\mathbf{S}$ loses a rank through restriction (Step 2.3.1). If so,
the cocycle in $\mathbf{S}$ that becomes dependent to other cocycles through a
left-to-right reduction is designated to be killed (Step 2.3.2) and we note
the death of a bar in the $k$-cup module barcode. We update $\mathbf{H}$,
$\mathbf{R}$ appropriately (Step 2.3.3). At a high level, this algorithm is
similar to CupPers with the role of $\mathbf{H}$ played by both $\mathbf{H}$
and $\mathbf{R}$ as they host the cocycles whose products are to be checked
during the birth and the role of $\mathbf{S}$ in both algorithms remains the
same, that is, check if a product cocycle dies or not.

#### Correctness and complexity of OrderkCupPers

Correctness can be established the same way we proved it for CupPers. We
sketch a correctness proof in Appendix D. For complexity, observe that we
incur a cost from recursive calling in step 1 and $O(n^{4})$ cost from step 2
with a similar analysis we did for CupPers while noting that there are once
again a total of $O(n^{2})$ order-$k$ product cocycles to be checked for
independence at birth (Steps 2.1 and 2.2). Then, we get a recurrence for time
complexity as $T(n,k)=T(n,k-1)+O(n^{4})$ and $T(n,2)=O(n^{4})$ which solves to
$T(n,k)=O(kn^{4})$. Observe that $k\leq d$, the dimension of $\mathsf{K}$.
This gives an $O(dn^{4})$ algorithm for computing the persistent $k$-cup
modules for all $k\in\\{2,\dots,d\\}$.

###  4.2 Computing persistent cup-length

The _cup length_ of a ring is defined as the maximum number of multiplicands
that together give a nonzero product in the ring. Let $\mathbf{Int}_{\ast}$
denote the set of all closed intervals of $\mathbb{R}$. Let $\mathcal{F}$ be
an $\mathbb{R}$-indexed filtration of simplicial complexes. The _persistent
cup-length function_
$\mathbf{cuplength}_{\bullet}:\mathbf{Int}_{\ast}\to\mathbb{N}$ is defined as
a function from the set of closed intervals to the set of non-negative
integers, which assigns to each interval $[a,b]$, the cup-length of the image
ring $\operatorname{im}\big{(}\mathsf{H}^{*}(\mathsf{K})[a,b]\big{)}$, which
is the ring
$\operatorname{im}\big{(}\mathsf{H}^{*}(\mathsf{K}_{b})\to\mathsf{H}^{*}(\mathsf{K}_{a})\big{)}$.

Given a $P$-indexed filtration $\mathcal{F}$ of a $d$-dimensional complex
$\mathsf{K}$ of size $n$, let $V^{k}_{\bullet}$ denote its persistent $k$-cup
module. Leveraging the fact that $\mathbf{cuplength}_{\bullet}([a,b])={\rm
argmax}\\{k\mid\mathsf{rk}_{V^{k}_{\bullet}}([a,b])\not=0\\}$ (see Proposition
5.9 in [14]), the algorithm described in Section 4 can be used to compute the
persistent cup-length of a filtration in $O(dn^{4})$ time, whereas
$O(n^{d+2})$ is a coarse estimate for the runtime of the algorithm described
in [13]. Thus, for $d\geq 3$, our complexity bound for computing the
persistent cup length is strictly better than the coarse upper bound known
from Contessoto et al. in [13, 14]. We refer the reader to Appendix B for
further details.

##  5 Conclusion

Within the mathematics literature, it is well-known that cohomology has a more
refined structure than homology, as cohomology comes equipped with the so-
called _cohomology operations_. The cup product is one such operation giving
the graded cohomology vector spaces the structure of a graded ring [18]. One
could also use other operations such as Massey products and Steenrod squares
[24, 23, 27]. Recently, Lupo et al. [21] introduced invariants called Steenrod
barcodes and devised algorithms for their computation, which were implemented
in the software steenroder. Our work complements the the results in Lupo et
al. [21], Contessoto et al.[13, 14] and Mémoli et al. [25]. While Contessoto
et al.[14] introduced persistent cup modules and established stability, in
this work we devise an efficient algorithm to compute them. We believe that
the combined advantages of a fast algorithm and favorable stability properties
make persistent cup modules an attractive addition to the topological data
analysis pipeline.

## Acknowledgments

The second author acknowledges helpful initial discussions with Ulrich Bauer
and Fabian Lenzen. This work is partially supported by the NSF grant CCF
2049010.

## References

  * [1] Ulrich Bauer.  Ripser: efficient computation of Vietoris–Rips persistence barcodes.  Journal of Applied and Computational Topology, 5(3):391–423, 2021\.
  * [2] Ulrich Bauer, Michael Kerber, and Jan Reininghaus.  Clear and compress: Computing persistent homology in chunks.  In Topological methods in data analysis and visualization III, pages 103–117. Springer, 2014.
  * [3] Ulrich Bauer, Michael Kerber, Jan Reininghaus, and Hubert Wagner.  Phat – persistent homology algorithms toolbox.  Journal of Symbolic Computation, 78:76–90, 2017.
  * [4] Ulrich Bauer and Maximilian Schmahl.  Efficient computation of image persistence.  arXiv preprint arXiv:2201.04170, 2022.
  * [5] Francisco Belchí and Anastasios Stefanou.  A-infinity persistent homology estimates detailed topology from point cloud datasets.  Discrete & Computational Geometry, pages 1–24, 2021.
  * [6] Jean-Daniel Boissonnat, Tamal K Dey, and Clément Maria.  The compressed annotation matrix: An efficient data structure for computing persistent cohomology.  In European Symposium on Algorithms, pages 695–706. Springer, 2013\.
  * [7] Peter Brooksbank, E O’Brien, and James Wilson.  Testing isomorphism of graded algebras.  Transactions of the American Mathematical Society, 372(11):8067–8090, 2019.
  * [8] Peter Bubenik and Nikola Milićević.  Homological algebra for persistence modules.  Foundations of Computational Mathematics, 21(5):1233–1278, 2021\.
  * [9] Frédéric Chazal, Vin De Silva, and Steve Oudot.  Persistence stability for geometric complexes.  Geometriae Dedicata, 173(1):193–214, 2014.
  * [10] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.  Stability of persistence diagrams.  In Proceedings of the twenty-first annual symposium on Computational geometry, pages 263–271, 2005.
  * [11] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer.  Stability of persistence diagrams.  Discrete Comput. Geom., 37(1):103–120, Jan 2007.  doi:10.1007/s00454-006-1276-5.
  * [12] David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov.  Persistent homology for kernels, images, and cokernels.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1011–1020. SIAM, 2009.
  * [13] Marco Contessoto, Facundo Mémoli, Anastasios Stefanou, and Ling Zhou.  Persistent cup-length.  In 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [14] Marco Contessoto, Facundo Mémoli, Anastasios Stefanou, and Ling Zhou.  Persistent cup-length, 2021.  URL: https://arxiv.org/abs/2107.01553v3, doi:10.48550/ARXIV.2107.01553.
  * [15] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson.  Dualities in persistent (co) homology.  Inverse Problems, 27(12):124003, 2011.
  * [16] Tamal K. Dey and Yusu Wang.  Computational Topology for Data Analysis.  Cambridge University Press, 2022.
  * [17] Herbert Edelsbrunner and John Harer.  Computational Topology: An Introduction.  Applied Mathematics. American Mathematical Society, 2010.
  * [18] Allen Hatcher.  Algebraic topology.  Cambridge University Press, Cambridge, 2002.
  * [19] Jean-Claude Hausmann.  Mod two homology and cohomology, volume 10.  Springer, 2014.
  * [20] Estanislao Herscovich.  A higher homotopic extension of persistent (co)homology.  Journal of Homotopy and Related Structures, 13(3):599–633, 2018\.
  * [21] Umberto Lupo, Anibal M. Medina-Mardones, and Guillaume Tauzin.  Persistence steenrod modules.  Journal of Applied and Computational Topology, 6(4):475–502, 2022\.
  * [22] Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, and Mariette Yvinec.  The gudhi library: Simplicial complexes and persistent homology.  In Hoon Hong and Chee Yap, editors, Mathematical Software – ICMS 2014, pages 167–174, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * [23] William S. Massey.  Higher order linking numbers.  Journal of Knot Theory and Its Ramifications, 7:393–414, 1998.
  * [24] Robert E. Mosher and Martin C. Tangora.  Cohomology operations and applications in homotopy theory.  Courier Corporation, 2008.
  * [25] Facundo Mémoli, Anastasios Stefanou, and Ling Zhou.  Persistent cup product structures and related invariants, 2022.  URL: https://arxiv.org/abs/2211.16642, doi:10.48550/ARXIV.2211.16642.
  * [26] Leonid Polterovich, Egor Shelukhin, and Vukašin Stojisavljević.  Persistence modules with operators in morse and floer theory.  Moscow Mathematical Journal, 17(4):757–786, 2017.
  * [27] Norman E Steenrod.  Products of cocycles and extensions of mappings.  Annals of Mathematics, pages 290–320, 1947.
  * [28] Andrew Yarmola.  Persistence and computation of the cup product.  Undergraduate honors thesis, Stanford University, 2010.
  * [29] Afra Zomorodian and Gunnar Carlsson.  Computing persistent homology.  In Proceedings of the twentieth annual symposium on Computational geometry, pages 347–356, 2004.

##  Appendix A Mod-2 (co)homology

Given a simplicial complex $\mathsf{K}$, let $\mathsf{K}^{(p)}$ denote the set
of $p$-simplices of $\mathsf{K}$. A $p$-cochain of $\mathsf{K}$ is a function
$\zeta:\mathsf{K}^{(p)}\to\mathbb{Z}_{2}$ with finite support. Equivalently, a
$p$-cochain is a subset of $\mathsf{K}^{(p)}$. Since cochains can be added to
each other with $\mathbb{Z}_{2}$ additions, they form a
$\mathbb{Z}_{2}$-vector space called the cochain group, denoted by
$\mathsf{C}^{p}(\mathsf{K})$.

The _coboundary of a $p$-simplex_ is a $(p+1)$-cochain that corresponds to the
set of its $(p+1)$-cofaces. The coboundary map is linearly extended from
$p$-simplices to $p$-cochains, where the _coboundary of a cochain_ is the
$\mathbb{Z}_{2}$-sum of the coboundaries of its elements. This extension is
known as the _coboundary homomorphism_ , and is denoted by
$\delta_{p}:\mathsf{C}^{p}(\mathsf{K})\to\mathsf{C}^{p+1}(\mathsf{K})$. A
cochain $\zeta\in\mathsf{C}^{p}(\mathsf{K})$ is called a _$p$ -cocycle_ if
$\delta_{p}\zeta=0$, that is, $\zeta\in\ker\delta_{p}$. The collection of
$p$-cocycles forms the $p$-th cocycle group of $\mathsf{K}$, denoted by
$\mathsf{Z}^{p}(\mathsf{K})$, which is also a vector space under
$\mathbb{Z}_{2}$ addition. A cochain $\eta\in\mathsf{C}^{p}(\mathsf{K})$ is
said to be a $p$-coboundary if $\eta=\delta_{p-1}\xi$ for some cochain
$\xi\in\mathsf{C}^{p-1}(\mathsf{K})$, that is,
$\eta\in\operatorname{im}\delta_{p-1}$. The collection of $p$-coboundaries
forms the $p$-th coboundary group of $\mathsf{K}$, denoted by
$\mathsf{B}^{p}(\mathsf{K})$ which is also a vector space under
$\mathbb{Z}_{2}$ addition. The three vector spaces are related as follows:
$\mathsf{B}^{p}(\mathsf{K})\subset\mathsf{Z}^{p}(\mathsf{K})\subset\mathsf{C}^{p}(\mathsf{K})$.
Therefore, we can define the quotient space
$\mathsf{H}^{p}(\mathsf{K})=\mathsf{Z}^{p}(\mathsf{K})/\mathsf{B}^{p}(\mathsf{K})$,
which is called the $p$-th cohomology group of $\mathsf{K}$. The elements of
the vector space $\mathsf{H}^{p}(\mathsf{K})$, known as the $p$-th _cohomology
group_ of $\mathsf{K}$, are equivalence classes of $p$-cocycles, where
$p$-cocycles are equivalent if their $\mathbb{Z}_{2}$-difference is a
$p$-coboundary. Equivalent cocycles are said to be _cohomologous_. For a
$p$-cocycle $\zeta$, its corresponding cohomology class is denoted by
$[\zeta]$. The $p$-th _Betti number_ of $\mathsf{K}$, denoted by
$\beta^{p}(\mathsf{K})$ is defined as
$\beta^{p}(\mathsf{K})=\dim\mathsf{H}^{p}(\mathsf{K})$. For a cocycle $\eta$
and a simplex $\sigma$, the evaluation map $\langle\eta,\sigma\rangle$ is
defined as follows: $\langle\eta,\sigma\rangle=1$ if $\sigma$ is in the
support of $\eta$, and $0$ otherwise.

A vector space $V$ is said to be graded with an index set $I$ if
$V=\oplus_{i\in I}V_{i}$. Cochain and cohomology groups form graded vector
spaces, where the grading is achieved with degree. Specifically, we work with
graded cochain and cohomology vector spaces
$\mathsf{C}^{\ast}(\mathsf{K})=\bigoplus_{p\in\mathbb{N}}\mathsf{C}^{p}(\mathsf{K})$,
and
$\mathsf{H}^{\ast}(\mathsf{K})=\bigoplus_{p\in\mathbb{N}}\mathsf{H}^{p}(\mathsf{K})$,
respectively.

A _cochain complex_ is a pair $(\mathsf{C}^{\ast},\delta)$ where
$\mathsf{C}^{\ast}$ is a graded vector space and $\delta$ is a linear map
satisfying $\delta(\mathsf{C}^{p})\subset\mathsf{C}^{p+1}$ and
$\delta\circ\delta=0$. Observe that $(\mathsf{C}^{\ast},\delta)$ is graded in
the increasing order of degrees. For instance, for a simplicial complex, the
simplicial cochain groups along with the respective coboundary maps assemble
to give a cochain complex.

Given two cochain complexes $(\mathsf{C}^{\ast},\delta_{C})$ and
$(\mathsf{D}^{\ast},\delta_{D})$, a linear map
$\psi:\mathsf{D}^{\ast}\rightarrow\mathsf{C}^{\ast}$ satisfying
$\psi(\mathsf{D}^{p})\subset\mathsf{C}^{p}$ for all $p$ is a _cochain map_ if
$\psi\circ\delta_{D}=\delta_{C}\circ\psi$. For every $p\in\\{0,1,2,\dots\\}$,
applying the cohomology functor $\mathsf{H}^{p}$ to a cochain complex
$(\mathsf{C}^{\ast},\delta)$, gives its $p$-th cohomology group, which is the
quotient space
$\mathsf{H}^{p}(\mathsf{C}^{\ast})=\frac{\ker(\delta:\mathsf{C}^{p}\to\mathsf{C}^{p+1})}{\operatorname{im}(\delta:\mathsf{C}^{p-1}\to\mathsf{C}^{p})}$,
and applying it to a cochain map
$\psi:\mathsf{D}^{\ast}\rightarrow\mathsf{C}^{\ast}$ induces a linear map
$\mathsf{H}^{p}(\psi):\mathsf{H}^{p}(\mathsf{D}^{\ast})\to\mathsf{H}^{p}(\mathsf{C}^{\ast})$.

##  Appendix B Computing persistent cup-length

This section expands the section 4.2. The _cup length_ of a ring is defined as
the maximum number of multiplicands that together give a nonzero product in
the ring. Let $\mathbf{Int}_{\ast}$ denote the set of all closed intervals of
$\mathbb{R}$, and let $\mathbf{Int}_{\circ}$ denote the set of all the open-
closed intervals of $\mathbb{R}$ of the form $(a,b]$. Let $\mathcal{F}$ be an
$\mathbb{R}$-indexed filtration of simplicial complexes. The _persistent cup-
length function_
$\mathbf{cuplength}_{\bullet}:\mathbf{Int}_{\ast}\to\mathbb{N}$ (introduced in
[13, 14]) is defined as the function from the set of closed intervals to the
set of non-negative integers.222For simplicity and without loss of generality,
we define persistent cup-length only for intervals in $\mathbf{Int}_{\ast}$,
and persistent cup-length diagram only for intervals in
$\mathbf{Int}_{\circ}$. Specifically, it assigns to each interval $[a,b]$, the
cup-length of the image ring
$\operatorname{im}\big{(}\mathsf{H}^{*}(\mathsf{K})[a,b]\big{)}$, which is the
ring
$\operatorname{im}\big{(}\mathsf{H}^{*}(\mathsf{K}_{b})\to\mathsf{H}^{*}(\mathsf{K}_{a})\big{)}$.

Let the restriction of a cocycle $\xi$ to index $k$ be $\xi^{k}$. We say that
a cocycle $\zeta$ is defined at $p$ if there exists a cocycle $\xi$ in
$\mathsf{K}_{q}$ for $q\geq p$ and $\zeta=\xi^{p}$.

For a persistent cohomology basis $\Omega$, we say that $[d,b)$ is _a
supported interval of length $k$ for $\Omega$_ if there exists cocycles
$\xi_{1},\dots,\xi_{k}\in\Omega$ such that the product cocycle
$\eta^{s}=\xi_{1}^{s}\smile\dots\smile\xi_{k}^{s}$ is nontrivial for every
$s\in[d,b)$ and $\eta^{s}$ either does not exist or is trivial outside of
$[d,b)$. In this case, we say that $[d,b)$ _is supported by_
$\\{\xi_{1},\dots,\xi_{k}\\}$. The max-length of a supported interval $[d,b)$,
denoted by $\ell_{\Omega}([d,b))$, is defined as

$\ell_{\Omega}([d,b))=\max\\{k\in\mathbb{N}\mid\exists\xi_{1},\dots,\xi_{k}\in\Omega\text{
such that }(d,b]\text{ is supported by }\\{\xi_{1},\dots,\xi_{k}\\}\\}.$

Let $\mathbf{Int}_{\Omega}$ be the set of supported intervals of $\Omega$. In
order to compute the persistent cup-length function, Contessoto et al. [13]
define a notion called the _persistent cup-length diagram_ , which is a
function $\mathbf{dgm}^{\smile}_{\Omega}:\mathbf{Int}_{\circ}\to\mathbb{N}$,
that assigns to every interval $[d,b)$ in
$\mathbf{Int}_{\Omega}\subset\mathbf{Int}_{\circ}$ its max-length
$\ell_{\Omega}([d,b))$, and assigns zero to every interval in
$\mathbf{Int}_{\circ}\setminus\mathbf{Int}_{\Omega}$.

It is worth noting that unlike the order-$k$ product persistence modules, the
persistent cup-length diagram is not a topological invariant as it depends on
the choice of representative cocycles. While the persistent cup-length diagram
is not useful on its own, in Contessoto et al. [13], it serves as an
intermediate in computing the persistent cup-length (a stable topological
invariant) due to the following theorem.

######  Theorem B.1 (Contessoto et al. [13]).

Let $\mathcal{F}$ be a filtered simplicial complex, and let $\Omega$ be a
persistent cohomology basis for $\mathcal{F}$. The persistent cup-length
function $\mathbf{cuplength}_{\bullet}$ can be retrieved from the persistent
cup-length diagram $\mathbf{dgm}_{\Omega}^{\smile}$ for any
$(a,b]\in\mathbf{Int}_{\circ}$ as follows.

$\mathbf{cuplength}_{\bullet}([a,b])=\max_{(c,d]\supset[a,b]}\mathbf{dgm}_{\Omega}^{\smile}((c,d]).$
(6)

Given a $P$-indexed filtration $\mathcal{F}$, let $V^{k}_{\bullet}$ denote its
persistent $k$-cup module. The following result appears as Proposition 5.9 in
[14]. We provide a short proof in our notation for the sake of completeness.

######  Proposition B.1 (Contessoto et al. [14]).

$\mathbf{cuplength}_{\bullet}([a,b])={\rm
argmax}\\{k\mid\mathsf{rk}_{V^{k}_{\bullet}}([a,b])\not=0\\}$.

###### Proof.

$\mathbf{cuplength}_{\bullet}([a,b])=k\quad\Longleftrightarrow\quad$ 1. There
exists a set of cocycles $\\{\xi_{1},\dots,\xi_{k}\\}$ that are defined at $b$
and $\xi_{1}^{s}\smile\dots\smile\xi_{k}^{s}$ is nontrivial for all
$s\in[a,b]$ 2. For any set of $k+1$ cocycles
$\\{\zeta_{1},\dots,\zeta_{k+1}\\}$ that are defined at $b$, the product
$\zeta_{1}^{s}\smile\dots\smile\zeta_{k+1}^{s}$ is zero for some $s\in[a,b]$.
$\quad\Longleftrightarrow\quad$ $\mathsf{rk}_{V^{k}_{\bullet}}([a,b])\not=0$
and $\mathsf{rk}_{V^{k+1}_{\bullet}}([a,b])=0$. ∎

Given a filtered complex
$\mathsf{K}_{\bullet}:\mathsf{K}_{1}\hookrightarrow\mathsf{K}_{2}\hookrightarrow\dots$,
Contessoto et al. [13] define its $p$-truncation as the filtration
$\mathsf{K}_{\bullet}^{p}:\mathsf{K}_{1}^{p}\hookrightarrow\mathsf{K}_{2}^{p}\hookrightarrow\dots$,
where for all $i$, $\mathsf{K}_{i}^{p}$ denotes the $p$-skeleton of
$\mathsf{K}_{i}$. We now compare the complexities of computing the persistent
cup-length using the algorithm described in Contessoto et al. [13] against
computing it with our approach.

Assume that $\mathsf{K}$ is a $d$-dimensional complex of size $n$, and let
$n_{p}$ denote the number of simplices in the $p$-skeleton of $\mathsf{K}$.
Let $\mathcal{F}$ be a filtration of $\mathsf{K}$ and let $\mathcal{F}_{p}$ be
the $p$-truncation of $\mathcal{F}$. Then, according to Theorem 20 in
Contessoto et al. [13], using the persistent cup-length diagram,  1. the
persistent cup-length of $\mathcal{F}$ can be computed in $O(n^{d+2})$ time,
2. the persistent cup-length of $\mathcal{F}_{p}$ can be computed in
$O(n_{p}^{p+2})$ time.

In contrast, as noted in Section 3, the barcodes of all the persistent $k$-cup
modules for $k\in\\{2,\dots,p\\}$ can be computed in $O(p\,n^{4})$ time. Note
that $\mathsf{rk}_{V^{k}_{\bullet}}([a,b])\not=0$ if and only if there exists
an interval $(x,y]$ in $B(V^{k}_{\bullet})$ such that $(x,y]\supset[a,b]$.
This suggests a simple algorithm to compute $\mathbf{cuplength}_{\bullet}$
from the barcodes of order-$k$ product persistence modules for $k\in[n]$, that
is, one finds the largest $k$ for which there exists an interval $(x,y]\in
B(V^{k}_{\bullet})$ such that $(x,y]\supset[a,b]$. Since the size of
$B(V^{k}_{\bullet})$, for every $k\in[n]$, is $O(n)$, the algorithm for
extracting the persistent cup-length from the barcode of persistent $k$-cup
modules for $k\in\\{2,\dots,d\\}$ runs in $O(n^{2})$ time. Thus, using the
algorithms described in Section 4, the persistent cup-length of a
($p$-truncated) filtration can be computed in $O(dn^{4})$ ($O(pn^{4})$) time,
which is strictly better than the coarse bound for the algorithm in [13] for
$d\geq 3$.

##  Appendix C Additional Example

In this section, we provide an additional example that highlights the
discriminating power of product persistence.

#### Filtered real projective space.

The real projective space $\mathbb{RP}^{n}$ is the space of lines through the
origin in $\mathbb{R}^{n+1}$. It is homeomorphic to the quotient space
${S^{n}}/{(u\simeq-u)}$ obtained by identifying the antipodal points of a
sphere, which in turn is homeomorphic to ${D^{n}}/{(v\simeq-v)}$ for
$v\in\partial D^{n}$. Since ${S^{n-1}}/{(u\simeq-u)}\cong\mathbb{RP}^{n-1}$,
$\mathbb{RP}^{n}$ can be obtained from $\mathbb{RP}^{n-1}$ by attaching a cell
$D^{n}$ using the projection $\wp_{n}:{S^{n-1}}\to\mathbb{RP}^{n-1}$ Thus,
$\mathbb{RP}^{n}$ is a CW complex wih one cell in every dimension from $0$ to
$n$. This gives rise to a natural cellular filtration
$\mathbb{RP}^{n}_{\bullet}$ for $\mathbb{RP}^{n}$ where cells of successively
higher dimension are introduced with attaching maps $\wp_{i}$ for $i\in[n]$
described above. Finally, the cohomology algebra of $\mathbb{RP}^{n}$ is given
by $\mathbb{Z}_{2}[x]/(x^{n+1})$, where $x\in\mathsf{H}^{1}(\mathbb{RP}^{n})$
[19, pg. 146].

#### Filtered complex projective space.

The complex projective space $\mathbb{CP}^{n}$ is the space of complex lines
through the origin in $\mathbb{C}^{n+1}$. It is homeomorphic to the quotient
space $S^{2n+1}/S^{1}\cong S^{2n+1}/(u\simeq\lambda u)$, which in turn can be
shown to be homeomorphic to $D^{2n}/(v\simeq\lambda v)$ for $v\in\partial
D^{2n}$ for all $\lambda\in\mathbb{C}$, $|\lambda|=1$. Therefore,
$\mathbb{CP}^{n}$ is obtained from $\mathbb{CP}^{n-1}$ by attaching a
$2n$-dimensional cell $D^{2n}$ using the projection
$\wp^{\prime}_{2n}:S^{2n-1}\to\mathbb{CP}^{n-1}$.Thus, $\mathbb{CP}^{n}$ is a
CW complex with one cell in every even dimension from $0$ to $2n$. This yields
a natural cellular filtration $\mathbb{CP}^{n}_{\bullet}$ for
$\mathbb{CP}^{n}$ where a cell of dimension $2i$ is added to the CW complex
for $i\in[n]$ with the attaching maps $\wp^{\prime}_{2i}$ for $i\in[n]$
described above. The cohomology algebra of $\mathbb{CP}^{n}$ is given by
$\mathbb{Z}_{2}[y]/(y^{n+1})$, where $y\in\mathsf{H}^{2}(\mathbb{CP}^{n})$
[19, pg. 241].

#### Filtered wedge of spheres.

Let $\mathsf{L}^{n}=S^{1}\vee\dots\vee S^{n}$ be a wedge of spheres of
increasing dimensions. Let $p$ be the basepoint of $\mathsf{L}^{n}$. The
filtration $\mathsf{L}^{n}_{\bullet}$ can be described as follows:
$\mathsf{L}^{n}_{0}=p$, and for $i\in\\{1,\dots,n\\}$,
$\mathsf{L}^{n}_{i}=S^{1}\vee\dots\vee S^{i}$, where for each index $i$, a
cell of dimension $i$ is added with the attaching map that takes the boundary
of the $i$-cell to the basepoint $p$. The cohomology algebra of
$\mathsf{L}^{n}$ is trivial in the sense that $x\smile y=0$ for all
$x,y\in\mathsf{H}^{\ast}(\mathsf{L})$.

Standard persistence cannot distinguish $\mathsf{L}^{n}_{\bullet}$ from
$\mathbb{RP}^{n}_{\bullet}$ since they have the same standard persistence
barcode. Persistent cup length for $\mathbb{RP}^{n}_{\bullet}$ and
$\mathbb{CP}^{n}_{\bullet}$ for all intervals $[i,j]$ with $i\geq 2$ is equal
to $\lfloor i\rfloor$, and hence persistent cup length cannot disambiguate
these filtrations.

Finally, persistent cup modules can tell apart $\mathsf{L}^{n}_{\bullet}$,
$\mathbb{RP}^{n}_{\bullet}$ and $\mathbb{CP}^{n}_{\bullet}$ as their cup
module barcodes are different. This follows from the fact that the degrees of
the generator of the cohomology algebras of $\mathbb{RP}^{n}_{\bullet}$ and
$\mathbb{CP}^{n}_{\bullet}$ are different.

##  Appendix D Correctness of OrderkCupPers

In this section, we provide a brief sketch of correctness of OrderkCupPers.
The statements of lemmas and their proofs are analogous to the case when $k=2$
treated in the main body of the paper.

######  Proposition D.1.

Let
$\\{\varphi^{\ast}_{i}:\mathsf{H}^{\ast}(\mathsf{K}^{*}_{i})\to\mathsf{H}^{\ast}(\mathsf{K}^{*}_{i-1})\mid
i\in[n]\\}$ denote the structure map of the module
$\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})$. The structure map for the $k$-cup
persistence module $\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k})$
is the restriction of $\varphi^{\ast}_{\bullet}$ to the image of
$\smile_{\bullet}^{k}$.

###### Proof.

Recall that $\varphi^{\ast}_{i}$ denotes the induced map on cohomology
$\mathsf{H}^{*}(\mathsf{K}_{i})\to\mathsf{H}^{*}(\mathsf{K}_{i-1})$. Let
$\varphi_{i}^{k\times\otimes}$ denote the tensor product of the map
$\varphi^{\ast}_{i}$ with itself taken $k$ times.

Applying the cohomology functor to the map

$\smile_{\bullet}^{k}:\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\mathsf{C}^{*}(\mathsf{K}_{\bullet})\otimes\dots\otimes\mathsf{C}^{*}\to\mathsf{C}^{*}(\mathsf{K}_{\bullet})$
(7)

and using the Künneth theorem for cohomology over fields, we obtain the
following diagram:

${{\mathsf{H}^{\ast}(\mathsf{K}_{i})\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i})\otimes\dots\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i-1})\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i-1})\otimes\dots\otimes\mathsf{H}^{\ast}(\mathsf{K}_{i-1})}}$${{\mathsf{H}^{\ast}(\mathsf{K}_{i-1})}}$$\scriptstyle{\varphi_{i}^{k\times\otimes}}$$\scriptstyle{\smile}$$\scriptstyle{\smile}$$\scriptstyle{\varphi^{\ast}_{i}}$

For cocycle classes
$[\alpha_{1}],\dots,[\alpha_{k}]\in\mathsf{H}^{\ast}(\mathsf{K})$, by the
naturality of the cup product,
$\varphi^{\ast}_{i}([\alpha_{1}])\smile\dots\smile\varphi^{\ast}_{i}([\alpha_{k}])=\varphi^{\ast}_{i}([\alpha_{1}]\smile\dots[\alpha_{k}])$.
Since,
$[\alpha_{1}]\smile\dots\smile[\alpha_{k}]\in\operatorname{im}\mathsf{H}^{\ast}(\smile_{i}^{k})$
is mapped to an element in
$\operatorname{im}\mathsf{H}^{\ast}(\smile_{i-1}^{k})$, the structure map for
the product persistence module
$\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k})$ is the restriction
of $\varphi^{\ast}_{\bullet}$ to the image of $\smile_{\bullet}^{k}$. ∎

######  Definition D.1.

For any $i\in\\{0,\dots,n\\}$, a nontrivial cocycle
$\zeta\in\mathsf{Z}^{\ast}(\mathsf{K}_{i})$ is said to be an _order- $k$
product cocycle of $\mathsf{K}_{i}$_ if
$[\zeta]\in\operatorname{im}\mathsf{H}^{*}(\smile_{i}^{k})$.

######  Proposition D.2.

For a filtration $\mathcal{F}$ of simplicial complex $\mathsf{K}$, the birth
points of $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$ are a
subset of the birth points of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$,
and the death points of
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$ are a subset of
the death points of $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$.

###### Proof.

Let $\\{(d_{i_{j}},b_{i_{j}}]\mid j\in[k]\\}$ be (not necessarily distinct)
intervals in $B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, where
$b_{i_{j+1}}\geq b_{i_{j}}$ for $j\in[k-1]$. Let $\xi_{i_{j}}$ be a
representative for $(d_{i_{j}},b_{i_{j}}]$ for $j\in[k]$.

If
$\xi_{i_{1}}\smile\xi_{i_{2}}^{b_{i_{1}}}\smile\dots\smile\xi_{i_{k}}^{b_{i_{1}}}$
is trivial, then by the naturality of cup product,

$\displaystyle\varphi_{b_{i_{1}},r}(\xi_{i_{1}}\smile\xi_{i_{2}}^{b_{i_{1}}}\smile\dots\smile\xi_{i_{k}}^{b_{i_{1}}})$
$\displaystyle=\varphi_{b_{i_{1}},r}(\xi_{i_{1}})\smile\varphi_{b_{i_{1}},r}(\xi_{i_{2}}^{b_{i_{1}}})\smile\dots\smile\varphi_{b_{i_{1}},r}(\xi_{i_{k}}^{b_{i_{1}}})$
$\displaystyle=\xi_{i_{1}}^{r}\smile\xi_{i_{2}}^{r}\smile\dots\smile\xi_{i_{k}}^{r}$

is trivial $\forall r<b_{i_{1}}$. Writing contrapositively, if $\exists
r<b_{i_{1}}$ for which
$\xi_{i_{1}}^{r}\smile\xi_{i_{2}}^{r}\smile\dots\smile\xi_{i_{k}}^{r}$ is
nontrivial, then
$\xi_{i_{1}}\smile\xi_{i_{2}}^{b_{i_{1}}}\smile\dots\smile\xi_{j}^{b_{i_{1}}}$
is nontrivial. Noting that
$\operatorname{im}\mathsf{H}^{*}(\smile_{\ell}^{k})$ for any
$\ell\in\\{0,\dots,n\\}$ is generated by
$\\{[\xi_{i_{1}}^{\ell}]\smile\\{[\xi_{i_{2}}^{\ell}]\smile\dots\smile[\xi_{i_{k}}^{\ell}]\mid\xi_{i_{j}}\in\Omega_{\mathsf{K}}\text{
for }j\in[k]\\}$, it follows that $b$ is the birth point of an interval in
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$ only if it is
the birth point of an interval in
$B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, proving the first claim.

Let $\Omega^{\prime}_{j+1}=\\{[\tau_{1}],\dots,[\tau_{\ell}]\\}$ be a basis
for $\operatorname{im}\mathsf{H}^{*}(\smile_{j+1}^{k})$. Then,
$\Omega^{\prime}_{j+1}$ extends to a basis $\Omega_{j+1}$ of
$\mathsf{H}^{\ast}(\mathsf{K}_{j+1})$. If $j$ is not a death index in
$B(\mathsf{H}^{\ast}(\mathsf{K}_{\bullet}))$, then
$\varphi_{j+1}(\tau_{1}),\dots,\varphi_{j+1}(\tau_{\ell})$ are all nontrivial
and linearly independent. Using Proposition 2.1, it follows that $j$ is not a
death index in $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$,
proving the second claim. ∎

######  Corollary D.1.

If $d$ is a death index in
$B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$, then at most
one bar of $B(\operatorname{im}\mathsf{H}^{\ast}(\smile_{\bullet}^{k}))$ has
death index $d$.

###### Proof.

The proof is identical to Corollary 2.1. ∎

Let $C_{b}$ be the vector space of order-$k$ product cocycle classes created
at index $b$. We note that for a birth index $b\in\\{0,\dots,n\\}$, $C_{b}$ is
a subspace of $\mathsf{H}^{\ast}(\mathsf{K}_{b})$ which can be written as

$C_{b}=\begin{cases}\langle[\xi_{i_{1}}]\smile\dots\smile[\xi_{i_{k}}]\mid\xi_{i_{j}}\text{
for }j\in[k]\text{ are essential cocycles of
}\mathsf{H}^{\ast}(\mathsf{K}_{\bullet})\rangle&\text{ if }b=n\\\
\langle[\xi_{i_{1}}]\smile\dots\smile\ [\xi_{i_{k}}^{b}]\mid\xi_{i_{1}}\text{
is born at $b$}\,\,\&\,\,\xi_{i_{j}}\text{ for }j\neq 1\text{ is born at
index}\geq b\rangle&\text{ if }b<n\end{cases}$ (8)

For a birth index $b$, let $\mathbf{C}_{b}$ be the submatrix of $\mathbf{S}$
formed by representatives whose classes generate $C_{b}$, augmented to
$\mathbf{S}$ in Steps 2.1.2 (i) and 2.2.2 (i) when $k=b$ in the outer for loop
of Step 2.

######  Theorem D.1.

Algorithm OrderkCupPers correctly computes the barcode of order-$k$ product
persistence.

###### Proof.

The proof is nearly identical to Theorem 3.1. The key difference (from Theorem
3.1) is in how the submatrix $\mathbf{C}_{b}$ of $\mathbf{S}$ that stores the
linearly independent order-$k$ product cocycles born at $\ell=b$ in Steps 2.1
and 2.2 is built. It is easy to check that the classes of the cocycle vectors
in $\mathbf{C}_{b}$ augmented to $\mathbf{S}$ in Steps 2.1 and 2.2 generate
the space $C_{b}$ described in Equation 8. ∎