\section{Introduction}
Topological data analysis (TDA) \citep{eh,carlsson} is, as the name suggests, the application of
topology to data analysis. Persistent homology \citep{elz,zc} is one of the most
important tools for TDA.
In persistent homology, by encoding information on length scales in filtrations,
we can capture characteristic geometric features with multiple length scales.
By using filtrations, persistent homology is also robust to noise.
Homology itself is translation and rotation invariant, and so
persistent homology is similarly invariant. These properties are
suitable for the analysis of shapes of data, and
persistent homology is applied in various practical data analysis contexts in domains such as
biology~\citep{virus}, image processing~\citep{Hu2019},
and materials science~\citep{Hiraoka28062016,granular,PhysRevE.95.012504,Kimura2018}.

To describe our problem, we first define persistent homology. Persistent homology
is defined on a filtration, an increasing sequence, of topological spaces.
We consider the following filtration:
\begin{align*}
  \mathbb{X} & = (X_t)_{t \in T}, \\
  X_t & \subset X_s \mbox{ if $t \leq s$}, \\
  X_0 &= \emptyset,
\end{align*}
where $T$ is $\{0, 1, \cdots, N\}$ or $\mathbb{R}_+$. 
The $q$th \emph{persistent homology} $H_q(\mathbb{X}; \Bbbk)$
with a coefficient ring $\Bbbk$ is defined as follows:
\begin{align*}
  H_q(\mathbb{X}; \Bbbk) &\mbox{ is a pair of } \\
                 & \{H_q(X_t; \Bbbk)\}_{t \in T}, \\
                 & \{\phi_s^t:H_q(X_s;\Bbbk) \to H_q(X_t; \Bbbk) \}_{s \leq t},
\end{align*}
where $\phi_s^t:H_q(X_s;\Bbbk) \to H_q(X_t; \Bbbk)$ is the homology map
induced by the inclusion map $X_s \hookrightarrow X_t$.
In standard homology theory, we use $\mathbb{Z}$ as a coefficient ring
since the universal coefficient theorem ensures
that $\mathbb{Z}$-homology provides the most information about homology.
However, in the theory of persistent homology a field is used instead of $\mathbb{Z}$ since
the interval decomposition described below is crucial for analysis of persistent homology
and the decomposition is guaranteed \emph{only when $\Bbbk$ is a field}.
Indeed, the structural theory of persistent homology ensures the existence and 
uniqueness of the following decomposition of $H_q(\mathbb{X}; \Bbbk)$ called 
the \emph{interval decomposition}
if $\Bbbk$ is a field:
\begin{align*}
  H_q(\mathbb{X}; \Bbbk) &= \bigoplus_{i=1}^L I(b_m, d_m), \\
  I(b, d) &= \{\varphi_s^t: U_s \to U_t\}_{s \leq t}, \\
  U_s &= \left\{
  \begin{array}{ll}
    \Bbbk & \mbox{ if $b \leq s < d$}, \\
    0 & \mbox{ otherwise},
  \end{array}\right. \\
  \varphi_s^t &= \left\{
  \begin{array}{ll}
    \mathrm{id} & \mbox{ if $b \leq s \leq t < d$}, \\
    0 & \mbox{ otherwise},
  \end{array}\right. 
\end{align*}
where $0 < b_m < d_m \leq \infty$.
This $I(b, d)$ is called an \emph{interval indecomposable}.
This theorem depends on the fact that $\Bbbk[z]$, the polynomial ring
with a field coefficient, is PID~\citep{zc}, and so this theorem does not hold
for $\Bbbk = \mathbb{Z}$.

When this interval decomposition is given, we define the $q$th
\emph{persistence diagram} (PD) $D_q(\mathbb{X}; \Bbbk)$ as a multiset of pairs of
endpoints of the intervals. That is, $D_q(\mathbb{X}; \Bbbk) = \{(b_m, d_m)\}_{i=1}^L$.
Each pair is called a \emph{birth-death pair}. Each $b_m and d_m$ are  \emph{birth time} and \emph{death time}, respectively, and
$d_m - b_m$ is called a \emph{lifetime}. Since a birth-death pair
with a long lifetime corresponds to a ``stable'' homological structure
in the filtration, we can use lifetimes to compare the significance of birth-death pairs.



Normally, we choose $\Bbbk$ as one of $\mathbb{R}, \mathbb{Q}$, and $\mathbb{Z}_p$ for a prime $p$.
$\mathbb{Z}_2$ is most often used since it is amenable to a fast algorithm
and an intuitive interpretation.
Here we face the problem of the choice of $\Bbbk$.
If any $\Bbbk$ gives the same PD, 
there is no problem. However, this is not practical, because the dimensions of homology vector spaces
for the same topological space are different when the $\mathbb{Z}$-homology group of the space has non-zero
torsion. If a Klein bottle appears in a filtration, the PDs 
for $\Bbbk = \mathbb{Z}_2$ and $\Bbbk = \mathbb{R}$ are clearly different.
For analysis of persistent homology with
torsions,
\cite{BJDMC} proposed
an efficient algorithm
to compute PD for multiple coefficient fields
by utilizing the Chinese remainder theorem.
Then, the following questions naturally arise.
\begin{itemize}
    \item What condition ensures the independence of the choice of the field $\Bbbk$?
    \item Is there an efficient algorithm to check the above condition?
    \item How often does $D_q(\mathbb{X}; \Bbbk)$ change as the field changes $\Bbbk$?
    \item When $D_q(\mathbb{X}; \Bbbk)$ changes depending of the choice of $\Bbbk$, how does $D_q(\mathbb{X}; \Bbbk)$ change?
\end{itemize}
In this paper, we offer complete
answers for the first and second questions, and partial answers
for the third and fourth questions. 

\subsection{Results}
To describe the results of the paper, we give some assumptions.
We always assume the finiteness of the filtration.
A filtration is \emph{finite}
if $X = \cup_t X_t$ is a finite simplicial/cell/cubical complex.
This condition ensures the existence and uniqueness of the interval
decomposition~\citep{zc}. This assumption is reasonable since
an infinite filtration cannot be represented on a computer and
we cannot use such a filtration in practical applications.
To consider field choice problems, we always restrict the
candidates of a field to $\mathbb{C}, \mathbb{R}, \mathbb{Q},$ and
$\mathbb{Z}_p$ for a prime $p$. 

\begin{question}\label{q:cond}
  When is $D_q(\mathbb{X}; \Bbbk)$ independent of the choice of the field $\Bbbk$?
\end{question}

To consider Question~\ref{q:cond}, 
it is desirable for the following proposition to hold since
$H_q(X_t; \mathbb{Z})$ is often free for every $t$ in practical cases.
\begin{proposition}[Incorrect!] 
  If $H_q(X_t; \mathbb{Z})$ is free for every $t \in T$,
  the persistent homology $H_q(\mathbb{X}; \Bbbk)$ has the same decomposition for any field
  $\Bbbk$.
\end{proposition}
However, we have a counterexample of this proposition (Fig.~\ref{fig:mobius}).
Let $M$ be a M\"obius strip
and $\partial M$ be its boundary. Both $H_1(\partial M; \mathbb{Z})$ and $H_1(M; \mathbb{Z})$ are
isomorphic to $\mathbb{Z}$, and the homomorphism
\begin{align*}
  H_1(\partial M; \mathbb{Z}) \to H_1(M; \mathbb{Z})
\end{align*}
is isomorphic to
\begin{align*}
  n \in \mathbb{Z} \mapsto 2n \in \mathbb{Z}
\end{align*}
and the interval decomposition on $\mathbb{R}$ and  $\mathbb{Z}_2$ gives
the different decomposition as follows:
\begin{align*}
  &\mathbb{X} : X_0 = \emptyset \subset X_1 = \partial M \subset X_2 = M, \\
  &H_1(\mathbb{X}; \mathbb{Z}_2) = I(1, 2) \oplus I(2, \infty), \\
  &H_1(\mathbb{X}; \mathbb{R}) = I(1, \infty). 
\end{align*}
In this example, both $H_1(\partial M; \mathbb{Z})$ and $H_1(M; \mathbb{Z})$
are free, but $H_1(M, \partial M; \mathbb{Z}) \simeq \mathbb{Z}_2$ and this is not free.
This fact is key to the different diagrams.
Section~\ref{sec:example} shows some other examples.

\begin{figure}[hbtp]
  \centering
  \includegraphics[width=0.7\hsize]{mobius.pdf}
  \caption{M\"obius strip and its boundary}
  \label{fig:mobius}
\end{figure}

We present the following theorem.
\begin{theorem}\label{thm:allfree}
  $D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of $\Bbbk$ if
  $H_q(X_n, X_m; \mathbb{Z})$ is free for any $0\leq m < n \in T$ and
  $H_{q-1}(X_n; \mathbb{Z})$ is free for any $n \in T$. 
\end{theorem}
This theorem yields the following corollaries.
\begin{corollary}\label{cor:M_0}
  $D_0(\mathbb{X}; \Bbbk)$ is always independent of the choice of $\Bbbk$.
\end{corollary}
\begin{corollary}\label{cor:M_munus_1}
  When $\mathbb{X}$ is a filtration of finite cell/simplicial/cubical complexes embedded
  in $\mathbb{R}^M$, the $(M-1)$th persistent homology gives the same
  PD among any fields $\Bbbk$.
\end{corollary}
Corollary~\ref{cor:M_0} derives from the fact that $H_{-1}(\cdot) = 0$ and $H_0(X_n, X_m; \mathbb{Z})$
is free for any $n > m$.
Corollary~\ref{cor:M_munus_1} is proved in Section~\ref{subsec:M_minus_1}.
The above two corollaries ensure that if a filtration is embedded in $\mathbb{R}^2$, 
all non-trivial persistence diagrams $D_0$ and $D_1$ do not depend on the choice of the 
coefficient field.

We also have the following theorem which provides the sufficient condition
for the freeness of $H_q(X_n, X_m; \mathbb{Z})$.
\begin{theorem}\label{thm:allfree2}
  For a given $q$, 
  $H_q(X_n, X_m; \mathbb{Z})$ are free for any $0\leq m < n \in T$ if
  $D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of $\Bbbk$ and
  $H_{q-1}(X_n; \mathbb{Z})$ is free for any $n \in T$.
\end{theorem}

From the above two theorems, we have the following corollary.
\begin{corollary}\label{cor:allfree3}
  Let $M$ be a non-negative integer.
  $D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of $\Bbbk$ for
  all $q = 0, \ldots, M$ if and only if
  $H_q(X_n, X_m; \mathbb{Z})$ are free for any $0\leq m < n \in T$, and $q = 0, \ldots, M$.
\end{corollary}

From the above discussion another question arises.
\begin{question}
  Is there an efficient algorithm for checking the condition of
  Corollary~\ref{cor:allfree3}?
\end{question}
Such an algorithm would be useful to provide information as to whether we should be concerned about field choice.
Of course, we can compute relative homology groups for all $m < n$ on a computer,
but that would be cumbersome and inefficient
because the number of possible pairs $(m, n)$ is $(N+1)N/2$.
The computation cost (time complexity)
is $O(N^2 G)$, where
$G$ is the average cost of computing $H_q(X_n, X_m; \mathbb{Z})$.
It is known that the time complexity of computing a PD is $O(G)$
\footnote{To compute the torsion subgroup of a homology group, we need to compute the Smith normal form of the boundary matrix, and the computational cost of the Smith normal form is $O(n^{\theta})$ in the worst case where $n$ is the number of simplices and $\theta \approx 2.376$ is a constant. The constant $\theta$ comes from the time complexity of the multiplication of two $n \times n$ matrices. The time complexity of persistent homology is also $O(n^{\theta})$ in the worst case. See \citep{Milosavljevic:2011:ZPH:1998196.1998229,Storjohann} for further details.}.

To describe the algorithm, we assume the following condition.
\begin{cond}\label{cond:finite}
  $X = \{\sigma_1, \sigma_2, \ldots, \sigma_N\}$ is a finite simplicial, cubical, or cell
  complex and the subset $X_k = \{\sigma_1, \ldots, \sigma_k\}$ is a sub-complex of
  $X$.
\end{cond}
With this setting, we consider the filtration of complexes
$\mathbb{X}: \emptyset = X_0 \subset X_1 \subset \cdots \subset X_N$.
Since the filtration is finite, we can transform the persistence decomposition problem
into the problem under Condition~\ref{cond:finite}. 

The following theorem is proved in Section~\ref{sec:algorithm}. 
\begin{theorem}\label{thm:allfreealg}
  There is an algorithm for judging the condition in Corollary~\ref{cor:allfree3}
  whose
  time complexity is the same as the algorithm for computing a PD.
\end{theorem}
The algorithm is shown in Algorithm~\ref{alg:allfree} in Section~\ref{sec:algorithm}.
In Section~\ref{sec:implementation}, we apply the algorithm to some examples shown in Section~\ref{sec:example} and demonstrate that
it performs well. A performance benchmark is also covered in that section.

We now pose the following additional question.
\begin{question}
  How often do we face filtrations with non-trivial torsion subgroups?
\end{question}
We can construct such an example by a M\"obius strip as shown above, but
would we often face such a filtration?
To demonstrate the probability of torsions
we conduct a numerical experiment for random data in $\mathbb{R}^3$.
From this experiment, we show that filtrations with non-trivial
torsion subgroups are very rare. This suggests that, in practical terms,
if the data is in $\mathbb{R}^3$,
we do not need to be particularly concerned about the torsion problem.
We also conduct another numerical experiment for random filtrations in high dimensional
simplex. The second experiment shows that the filtrations with non-trivial torsion subgroups
are usual when the space is high dimensional. 

The following question is also important.
\begin{question}
  When $D_q(\mathbb{X}; \Bbbk)$ changes depending of the choice of $\Bbbk$,
  how does $D_q(\mathbb{X}; \Bbbk)$ change?
\end{question}

In the above example about a M\"obius strip, a long interval $I(1, \infty)$ is
split into two shorter intervals, $ I(1, 2)$ and $I(2, \infty)$, when
$\Bbbk$ changes from $\mathbb{R}$ to $\mathbb{Z}_2$.
From the example, we expect that a long interval indecomposable tends to be split
into shorter intervals when $\Bbbk$ changes from $\mathbb{R}$ to $\mathbb{Z}_p$.
The following theorem proved in Section~\ref{sec:convex} partially answers the question.
\begin{theorem}\label{thm:r-wasserstein}
  Assume that $H_q(X_t; \mathbb{Z})$ and $H_{q-1}(X_t; \mathbb{Z})$
  are free for all $t$ and $H_q(\cup_t X_t) = 0$.
  Let $f$ be a $C^2$ convex function on $[0, \infty)$ with $f(0) = 0$.
  Then the following inequality holds:
  \begin{align*}
    \sum_{(b, d) \in D_q(\mathbb{X}; \mathbb{R})} f(d - b) \geq
    \sum_{(b, d) \in D_q(\mathbb{X}; \mathbb{Z}_p)} f(d - b).
  \end{align*}
  When $f$ is strictly convex, 
  the equality holds if and only if $D_q(\mathbb{X}; \mathbb{R}) = D_q(\mathbb{X}; \mathbb{Z}_p)$.
\end{theorem}
For $f(x) = x^r$ with $r > 1$, the inequality means
\begin{align*}
    W_r(D_q(\mathbb{X}; \mathbb{R}), \emptyset) \geq W_r(D_q(\mathbb{X}; \mathbb{Z}_p), \emptyset),
\end{align*}
where $W_r$ is the $r$-Wasserstein distance.
In some sense, the $r$-Wasserstein distance from the empty diagram indicates
the information richness of the diagram. Therefore, 
$D_q(\mathbb{X}; \mathbb{R})$ contains richer information than $D_q(\mathbb{X}; \mathbb{Z}_p)$ under the condition
of the theorem.

The remainder of the paper is organized as follows. 
Section~\ref{sec:ph} reviews the basic concepts of persistent homology.
Section~\ref{sec:example} shows some examples which exhibit the dependency of 
PDs to their coefficient fields.
Section~\ref{sec:proof-allfree} and Section~\ref{sec:proof-allfree2} prove 
Theorem~\ref{thm:allfree} and Theorem~\ref{thm:allfree2}.
Section~\ref{sec:algorithm} presents an algorithm which permits efficient judgement and the proof which testifies to the correctness of the algorithm.
Section~\ref{sec:implementation} introduces an implementation of the algorithm in HomCloud.
This section also shows the performance benchmark. Section~\ref{sec:probability} presents
numerical experiments to measure the probability of the appearance of non-trivial 
torsions in random filtrations.
Section~\ref{sec:convex} contains the proof of Theorem~\ref{thm:r-wasserstein} and, finally, conclusions are offered in Section~\ref{sec:conclusion}.

\section{Persistent homology}\label{sec:ph}
In this section, we prepare some fundamental concepts for persistent homology.

\subsection{Filtrations}

A filtration is an increasing sequence of topological spaces. One typical filtration is 
the union of $r$-balls constructed from a pointcloud in $\mathbb{R}^{M}$. For a pointcloud, a set of finite
points $\{x_i\}$, $X_r$ is defined as
\begin{equation}
    X_r = \cup_i B_{x_i}(r),
\end{equation}
where $B_{x}(r)$ is the closed ball whose center is $x$ and radius is $r$.
The sequence of $X_r$ parameterized by $r$,
$\{X_r\}_{r \geq 0}$, is obviously a filtration. This filtration is used to investigate
the shape formed by the pointcloud. 

For a practical application of persistent homology, we usually use finite simplicial or
cubical filtrations since such filtrations are practical to consider on a computer.
One well-known filtration is a \v{C}ech filtration. The \emph{\v{C}ech complex} $\mathrm{\v{C}ech}(P, r)$ of a pointcloud
$P = \{x_i\}$ with radius parameter $r \geq 0$ is defined as follows:
\begin{equation}
    \mathrm{\v{C}ech} (P, r) = \{ \{x_{i_1}, \ldots, x_{i_k}\} \subset P \mid 
    \bigcap_{n=1}^k B_{x_{i_n}}(r) \not = \emptyset \}.
\end{equation}
The filtration $\{\mathrm{\v{C}ech}(P, r)\}_{r \geq 0}$ is called a \emph{\v{C}ech filtration}. From the nerve theorem,
$\mathrm{\v{C}ech}(P, r)$ is homotopic to $\cup_i B_{x_i}(r)$ and we can use the \v{C}ech filtration to investigate
the union of $r$-balls. There are many simplices in a \v{C}ech complex for a large
pointcloud and we usually use an \emph{alpha complex} \citep{alphashape1,alphashape2}
instead since the alpha complex is
homotopic to the \v{C}ech complex and the number of simplices of the alpha complex
is much smaller than the \v{C}ech complex. The alpha complex has another advantage in that it can be embedded in $\mathbb{R}^M$ but such embedding is impossible for
the \v{C}ech complex.

When a filtration is finite, it is essentially time-discrete even if $T = \mathbb{R}_+$.
Therefore we assume $T = \{0, \ldots, N\}$ for the proofs of this paper
except Theorem~\ref{thm:r-wasserstein}. In addition, under this assumption,
it is straightforward to configure a filtration satisfying Condition~\ref{cond:finite} by ordering simplices
appropriately; hence, we can assume the condition without loss of generality.
Since Condition~\ref{cond:finite} is useful to describe algorithms, we sometimes 
assume this and consider the filtration
$X_0 \subset X_1 \subset \cdots \subset X_N$ where
$X_k = \{\sigma_1, \ldots, \sigma_k\}$.

\subsection{Computation of a persistence diagram}
Under Condition~\ref{cond:finite}, Algorithm~\ref{alg:pd} computes the PD of the filtration~\citep{elz,zc,Otter2017}. To simplify the algorithm,
all simplices of all dimensions are mixed and
in the output all birth-death pairs of all degrees are also mixed. In this algorithm,
$L_B(j)$ means
\begin{equation}
  L_B(j) = \left\{
    \begin{array}{ll}
      \max \{i \mid B_{ij} \not = 0\} & \text{if column $j$ of $B$ is nonzero},\\
      -\infty & \text{if column $j$ of $B$ is zero},
    \end{array}
  \right.
\end{equation}
where $B$ is a matrix and $j$ is an integer.

Furthermore, in this algorithm, matrix $B$ is reduced from left column to right column.
After terminating the algorithm, the PD is computed as follows:
\begin{equation}\label{eq:pd}
  \begin{aligned}
    D(\mathbb{X}) =& \{ (L_{\hat{B}}(j), j) \mid L_{\hat{B}}(j) \not = -\infty \} \\
    &\cup
    \{(j, \infty) \mid L_{\hat{B}}(j) = -\infty \text{ and } \forall i, L_{\hat{B}}(i) \not = j\}, 
  \end{aligned}
\end{equation}
where $\hat{B}$ is the matrix returned by the algorithm.
The $q$th PD is given from $D(\mathbb{X})$ as follows:
\begin{equation}
    D_q(\mathbb{X}) = \{(i, j) \in D(\mathbb{X}) \mid \dim \sigma_i = q\}.
\end{equation}

\begin{algorithm}[ht]
  \caption{Algorithm to compute persistence diagrams}\label{alg:pd}
  \begin{algorithmic}
    \State $B \leftarrow $ the boundary matrix with respect to the basis $\{\sigma_1, \ldots, \sigma_N\}$ 
    \For{$j=1, \ldots, N$}
      \While{there exists $i < j$ with $L_B(i) = L_B(j) \not = -\infty$ }
         \State let $s = B_{L_B(j), j} / B_{L_B(i), i}$  
         \State add $(-s) \times (\textrm{column}\  i)$ to column $j$ of $B$  \Comment left-to-right reduction
      \EndWhile
    \EndFor
    \State \Return B
  \end{algorithmic}
\end{algorithm}

Justification for the algorithm is provided in Appendix \ref{sec:proof-alg1}.
Indeed, Theorem~\ref{thm:allfreealg} shows that the algorithm for judging the condition of Corollary~\ref{cor:allfree3}
is given by restricting Algorithm~\ref{alg:pd} to integer coefficients. Therefore, the time complexity of the Theorem~\ref{thm:allfreealg} algorithm is as per  Algorithm~\ref{alg:pd}.

\subsection{Persistent Betti number}

From the definition of a PD, we have the following relationship
between the map $H_q(X_m; \Bbbk) \to H_q(X_n; \Bbbk)$ and a PD:
\begin{equation}\label{eq:persistence-betti-number}
  \begin{aligned}
    \beta_m^n(\Bbbk) :=& \rank\left(H_q(X_m; \Bbbk) \to H_q(X_n; \Bbbk)\right) \\
    =& \#\{ (b, d) \in D_q(\mathbb{X}; \Bbbk) \mid b \leq m \leq n < d \}.
  \end{aligned}
\end{equation}
This $\beta_m^n(\Bbbk)$ is called a \emph{persistent Betti number} or a \emph{rank invariant}. 
Hence, the following identity holds:
\begin{equation}\label{eq:multiplicity-1}
  (\text{multiplicity of $D_q(\mathbb{X}; \Bbbk)$ at $(b, d)$})
  = \beta^{d-1}_b(\Bbbk) - \beta^{d-1}_{b-1}(\Bbbk) - \beta^{d}_{b}(\Bbbk)
  + \beta^{d}_{b-1}(\Bbbk).
\end{equation}

When $d = \infty$, the following equation holds instead:
\begin{equation}\label{eq:multiplicity-2}
  (\text{multiplicity of $D_q(\mathbb{X}; \Bbbk)$ at $(b, \infty)$})
  = \beta^{N}_b(\Bbbk) - \beta^{N}_{b-1}(\Bbbk).
\end{equation}

The next lemma follows directly from the foregoing.
\begin{lemma}\label{lem:pbn}
  $D_q(\mathbb{X}, \Bbbk) = D_q(\mathbb{X}, \Bbbk')$ if and only if
  $\beta_m^n(\Bbbk) = \beta_m^n(\Bbbk')$ for all $0 \leq m \leq n \leq N$.
\end{lemma}

\subsection{Universal Coefficient Theorem}

The universal coefficient theorem is fundamental for homology theory
and plays an important role in this paper. We review the theorem here to foreground what follows.

The \emph{universal coefficient theorem for homology} is as follows~\citep{AT}.
\begin{theoremext}
  Let $X$ be a topological space, $\Bbbk$ a field, 
  and $q \geq 0$. The following sequence is a natural short
  exact sequence:
  \begin{equation}
      \begin{aligned}
        0 \to H_q(X; \mathbb{Z}) \otimes \Bbbk \to H_q(X; \Bbbk)  \to 
        \mathrm{Tor}(H_{q-1}(X; \mathbb{Z}), \Bbbk) \to 0.
      \end{aligned}
  \end{equation}
  Furthermore, this sequence splits, though not naturally.
\end{theoremext}

We use the above theorem in the following form.
\begin{theoremext}\label{thm:ucm}
Let $X$ and $Y$ be topological spaces, $f:X \to Y$ a continuous map, 
$\Bbbk$ a field, and $q \geq 0$.
If $H_{q-1}(X; \mathbb{Z})$ and $H_{q-1}(Y; \mathbb{Z})$ are free, the following commutative diagram holds:
\begin{equation}
 \vcenter{
 \xymatrix{
    H_q(X; \mathbb{Z})\otimes \Bbbk \ar[r]^{\simeq} \ar[d]_{f_*\otimes \mathrm{id}_{\Bbbk}} & H_q(X; \Bbbk) \ar[d]_{f_*} \\
    H_q(Y; \mathbb{Z})\otimes \Bbbk  \ar[r]^{\simeq} & H_q(Y; \Bbbk). \ar@{}[lu]|{\circlearrowright}
  }
  }
\end{equation}
\end{theoremext}
This theorem states that the induced map
$f_* : H_q(X; \Bbbk) \to H_q(Y; \Bbbk)$ is completely described by
$f_*\otimes \mathrm{id}_\Bbbk : H_q(X; \mathbb{Z}) \otimes \Bbbk \to H_q(Y; \mathbb{Z})\otimes \Bbbk$ if 
$H_{q-1}(X; \mathbb{Z})$ and $H_{q-1}(Y; \mathbb{Z})$ are free.
We use the theorem for an inclusion map between simplicial/cell/cubical complexes. 

\section{Examples of diagrammatic changes induced by coefficient field changes}\label{sec:example}

In this section, we will give some examples of persistent homology, whose interval decomposition depends on the choice of coefficient field.

\begin{example} \label{exm:bouquet}
Let $S^1$ be a circle.
We consider a filtration $\mathbb{X} : S^1 \xrightarrow{f} S^1 \vee S^1 \xrightarrow{g} S^1$, where $S^1 \vee S^1$ is a bouquet of $2$-circles, $f=\begin{pmatrix}1 \\ 1 \end{pmatrix}$ 
and $g=\begin{pmatrix}1&1 \end{pmatrix}$.
By taking the 1st homology of this filtration, 
we obtain the 1st persistent homology
$$
H_1 (\mathbb{X} ; \mathbb{Z})=
\xymatrix{
\mathbb{Z} \ar[r]^{\begin{pmatrix}1 \\ 1 \end{pmatrix}} & \mathbb{Z}^2 \ar[r]^{\begin{pmatrix}1&1 \end{pmatrix}} & \mathbb{Z},
}
$$
with a coefficient ring $\mathbb{Z}$.
Then $H_1 (\mathbb{X} ; \mathbb{Z}_2) = H_1(\mathbb{X} ; \mathbb{Z}) \otimes_\mathbb{Z} \mathbb{Z}_2$ has the interval decomposition $I(1,2) \oplus I(2,3)$.
On the other hand, $H_1 (\mathbb{X} ; \mathbb{R}) = H_1 (\mathbb{X} ; \mathbb{Z}) \otimes_\mathbb{Z}  \mathbb{R}$ has the interval decomposition  $I(1,3) \oplus I(2,2)$.
Thus, the interval decomposition of the 1st persistent homology of $\mathbb{X}$ depends on the choice of coefficient field.
\begin{figure}[h]
  \centering
  \includegraphics[width=1.0\hsize]{g3404.png} \\
  \caption{Visualization of $\mathbb{X} : S^1 \xrightarrow{f} S^1 \vee S^1 \xrightarrow{g} S^1$}
\end{figure}
\end{example}

Note that if we consider a bouquet of $p$-circles for a prime $p$, 
then we obtain the 1st persistent homology, which has different decompositions over $\mathbb{Z}_p$ and $\mathbb{R}$. 

By using Example \ref{exm:bouquet}, we can consider the 1st persistent homology, whose interval decomposition depends on the choice of characteristic $p>0$.

\begin{example} \label{exm:charp}
Let 
$$
M=
\xymatrix{
\mathbb{Z} \ar[r]^{\begin{pmatrix}1 \\ 1 \end{pmatrix}} & \mathbb{Z}^2 \ar[r]^{\begin{pmatrix}1&1 \end{pmatrix}} & \mathbb{Z} \ar[r]^{\begin{pmatrix}1 \\ 1 \\1 \end{pmatrix}}  & \mathbb{Z}^3 \ar[r]^{\begin{pmatrix}1 & 1 & 1 \end{pmatrix}} & \mathbb{Z}
}
$$
be the 1st persistent homology.  
Then $M$ has the following interval decomposition:
$$
M \cong \left\{
\begin{array}{cc}
I(1,2) \oplus I(2,5) \oplus I(4,4)^2     & \text{if } p=2 \\
I(1,4) \oplus I(2,2) \oplus I(4,4) \oplus I(4,5)     & \text{if }  p=3 \\
\end{array}\right.
.
$$
\begin{figure}[h]
  \centering
  \includegraphics[width=1.0\hsize]{g2655_2.png} \\
  \caption{Visualization of $\mathbb{X}$ with $M=H_1 (\mathbb{X})$}
\end{figure}
\end{example}

Other examples are double and triple loop pointclouds.
Figure~\ref{fig:doubletripleloop} (a) shows the double loop pointcloud. The pointcloud is located on the boundary
of a M\"obius strip. We compute the 1st PDs of the double loop pointcloud
with fields $\mathbb{Z}_2, \mathbb{Z}_3,$ and $\mathbb{Z}_5$. The alpha filtration of the pointcloud is used for the computation.
The diagrams are shown in Figure~\ref{fig:doubletripleloop} (b), (c), and (d). Note that  (c) and (d) are the same diagram. The difference between (b) and (c) is only two birth-death pairs.
Figure~\ref{fig:doubletripleloop} (e) shows the triple loop pointcloud and (f), (g), and (h) show
the 1st PDs of the triple loop pointcloud with fields $\mathbb{Z}_2, \mathbb{Z}_3,$ and $\mathbb{Z}_5$.
To be expected, (f) and (h) are the same diagram and (g) is different from (f) and (h).

\begin{figure}[h]
  \centering
  \includegraphics[width=1.0\hsize]{doubleloop.pdf} \\
  \includegraphics[width=1.0\hsize]{tripleloop.pdf} 
  \caption{1st PDs with various fields for double and triple loop pointclouds.
    (a) A double loop point cloud. (b) The PD of the double loop with $\mathbb{Z}_2$.
    (c) The PD of the double loop with $\mathbb{Z}_3$. (d) The PD of the double loop with $\mathbb{Z}_5$.
    (e) A triple loop point cloud. (f) The PD of the triple loop with $\mathbb{Z}_2$.
    (g) The PD of the triple loop with $\mathbb{Z}_3$. (h) The PD of the triple loop with $\mathbb{Z}_5$
  }
  \label{fig:doubletripleloop}
\end{figure}


\section{Proof of Theorem \ref{thm:allfree}}\label{sec:proof-allfree}

The following proposition is required to prove the theorem.

\begin{proposition}\label{prop:freefree}
  If $H_q(X_n, X_m; \mathbb{Z})$
  is free,
  $\coker(\phi_m^n: H_q(X_m; \mathbb{Z}) \to H_q(X_n; \mathbb{Z}))$ is also free.
\end{proposition}

\begin{proof}
  We have the following long exact sequence for the pair $(X_n, X_m)$:
  \begin{align}
    \cdots \to H_q(X_m; \mathbb{Z}) \xrightarrow{\phi_m^n} H_q(X_n; \mathbb{Z})
    \xrightarrow{\psi_m^n} H_q(X_n, X_m; \mathbb{Z}) \to \cdots,
  \end{align}
  where $\psi_m^n$ is induced by canonical projection.
  Therefore, we have the following relationship between
  $\coker(\phi_m^n)$ and $H_q(X_n, X_m; \mathbb{Z})$.
  \begin{align}
    \coker(\phi_m^n) = H_q(X_n; \mathbb{Z}) / \im \phi_m^n = H_q(X_n; \mathbb{Z}) / \ker \psi_m^n
    \simeq \im \psi_m^n \subset H_q(X_n, X_m; \mathbb{Z})
  \end{align}
  
  To complete the proof, we show that $\im \psi_m^n$ is free,  and this derives from the
  following well-known theorem.
  \begin{theoremext}\label{thmext:submodule}
    Any sub-module of a free $\mathbb{Z}$-module is also free.
  \end{theoremext}
  
\end{proof}

From the assumption of the theorem,  $H_q(X_m; \mathbb{Z}) = H_q(X_m, X_0; \mathbb{Z})$ is free for all $m$. Hence,
$\phi_m^n: H_q(X_m; \mathbb{Z}) \to H_q(X_n; \mathbb{Z})$ is a homomorphism between two finitely generated
free $\mathbb{Z}$-modules and the map has a Smith normal form (SNF).
That is, by taking an appropriate basis, $\phi_m^n$ can
be represented by the following $\mathbb{Z}$ matrix:
\begin{align}\label{eq:snf}
\begin{pmatrix}
  \alpha_1 & 0        & 0      & \cdots & 0        &  \\
  0        & \alpha_2 & 0      & \cdots & 0        &  \\
  0        & 0        & \ddots &        &          &\ \   O \ \ \\
  \vdots   & \vdots   &        & \ddots &          &  \\
  0        & 0        &        &        & \alpha_K & \\
  \\
  &          &    O   &        &          & \ \   O \ \ \\
  \\
\end{pmatrix},
\end{align}
where $0 < \alpha_k \in \mathbb{Z}$ and $\alpha_k \mid \alpha_{k+1}$ for any $k$. Then from Theorem~\ref{thm:ucm}, the following relationship holds:
\begin{equation}
    \begin{aligned}
    \beta_m^n(\Bbbk) & = \rank (\phi_m^n: H_q(X_m; \Bbbk) \to H_q(X_n; \Bbbk)) \\
    & = \rank (\phi_m^n \otimes \mathrm{id}_\Bbbk: H_q(X_m; \mathbb{Z}) \otimes \Bbbk \to H_q(X_n; \mathbb{Z}) \otimes \Bbbk).
    \end{aligned}\label{eq:beta-mn}
\end{equation}
From \eqref{eq:snf} and \eqref{eq:beta-mn}, we know that
$\beta_m^n(\Bbbk)$ is independent of the choice of $\Bbbk$
if and only if $\alpha_1 = \cdots = \alpha_K = 1$.
From SNF, we also have the following:
\begin{align*}
  \coker \phi_m^n \simeq &\bigoplus_{k=k_0}^K(\mathbb{Z} / \alpha_k\mathbb{Z}) \oplus \mathbb{Z}^{L - K}, \\
  \text{where } & k_0 = 1 + \max\{i \mid \alpha_m = 1\}, \\
  & L = \rank H_q(X_n; \mathbb{Z}).
\end{align*}
This means that $\alpha_1 = \cdots = \alpha_K = 1$ if and only if
$\coker(\phi_m^n)$ is free and the condition is shown
from Prop~\ref{prop:freefree} and the assumption of the theorem.

\subsection{Proof of Corollary~\ref{cor:M_munus_1}}\label{subsec:M_minus_1}
Standard homology theory~\citep[Corollary 3.46, pp. 256]{AT} 
shows that $H_{M-1}(X_n; \mathbb{Z})$ and 
$H_{M-2}(X_n; \mathbb{Z})$ are free under the condition of this corollary.
The above corollary is shown by using the Alexander duality.
$H_{M-1}(X_n, X_m; \mathbb{Z})$ is also free since this relative homology group
is isomorphic to a 0th relative cohomology group because of the Alexander duality.
Therefore, from Theorem~\ref{thm:allfree}, this can be applicable to the filtration.

\section{Proof of Theorem~\ref{thm:allfree2}}\label{sec:proof-allfree2}

The proof is similar to that of Theorem~\ref{thm:allfree}, but slightly more complex.
We prepare the following proposition.
\begin{proposition}\label{prop:quotfree}
  $H_q(X_n, X_m; \mathbb{Z})$ is free if
  $\coker(\phi_m^n: H_q(X_m; \mathbb{Z}) \to H_q(X_n; \mathbb{Z}))$ and
  $H_{q-1}(X_m; \mathbb{Z})$ are free.
\end{proposition}

\begin{proof}
  From the long exact sequence for the pair $(X_n, X_m)$,
  \begin{equation}
    \begin{aligned}
      \cdots \to H_q(X_m; \mathbb{Z}) \xrightarrow{\phi_m^n} H_q(X_n; \mathbb{Z})
      \xrightarrow{\psi_m^n} H_q(X_n, X_m; \mathbb{Z}) \xrightarrow{\partial}
      H_{q-1}(X_m; \mathbb{Z}) \to \cdots,
    \end{aligned}
  \end{equation}
  we have the
  following facts:
  \begin{equation}
    \begin{aligned}
      \coker(\phi_m^n) & \simeq \im \psi_m^n \subset H_q(X_n, X_m; \mathbb{Z}), \\
      \im \partial & \simeq H_q(X_n, X_m; \mathbb{Z}) / \im \psi_m^n .
    \end{aligned}
  \end{equation}
  $\im \partial$ is free since $H_{q-1}(X_m)$ is free.
  We complete the proof
  by the following theorem from standard algebra.
  \begin{theoremext}
    Let $M$ be a module over $\mathbb{Z}$ and $N$ be a sub-module of $M$.
    $M$ is finitely generated and free if $N$ and $M/N$ are
    finitely generated and free.
  \end{theoremext}
\end{proof}

\subsection{Proof of Theorem~\ref{thm:allfree2}}
We assume that $D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of
$\Bbbk$. Then from Lemma~\ref{lem:pbn},
$\beta_m^n(\Bbbk)$ is independent of $\Bbbk$ for any $m$ and $n$.
Especially, for any $n$ and $q$,
$\beta_n^n(\Bbbk) = \dim H_q(X_n; \Bbbk)$ is independent of
$\Bbbk$ and therefore $H_q(X_n; \mathbb{Z})$ is free
due to the universal coefficient theorem
since $H_{q-1}(X_n; \mathbb{Z})$ is free.
Then $\phi_m^n$ has SNF and $\coker \phi_m^n$ is free
because of the discussion of the proof of Theorem~\ref{thm:allfree}.
From the above fact and Proposition~\ref{prop:quotfree}, we conclude that
$H_q(X_n, X_m; \mathbb{Z})$ is free.

\subsection{Proof of Corollary~\ref{cor:allfree3}}

From Theorem~\ref{thm:allfree}, it is straightforward to show that 
$D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of $\Bbbk$ for all $q = 0, \ldots, M$ if
  $H_q(X_n, X_m; \mathbb{Z})$ are free for any $0\leq m < n \in T$, and $q = 0, \ldots, M$.

We can show the converse by induction on $q$.
For $q = 0$, it is trivial that $H_0(X_n, X_m; \mathbb{Z})$ is free and
the induction process proceeds by using Theorem~\ref{thm:allfree2}.

\section{Algorithm to determine the dependency of $D_q(\mathbb{X}; \Bbbk)$ on $\Bbbk$}\label{sec:algorithm}

In this section, we explore an algorithm to judge the existence of non-zero
torsion and prove Theorem~\ref{thm:allfreealg}. See Algorithm~\ref{alg:allfree}. Now we prove the following facts.
\begin{itemize}
\item If the algorithm returns ``independent'',
  the given filtration satisfies the condition of Corollary~\ref{cor:allfree3}.
  Therefore, $D_q(\mathbb{X}; \Bbbk)$ is independent of the choice of $\Bbbk$.
\item If the algorithm returns ``dependent'',
  the given filtration does not satisfy the condition of Corollary~\ref{cor:allfree3}.
  Therefore, $D_q(\mathbb{X}; \Bbbk)$ depends on the choice of $\Bbbk$.
\end{itemize}

\begin{algorithm}[ht]
  \caption{Algorithm to determine the dependency of $D_q(\mathbb{X}; \Bbbk)$ on $\Bbbk$}\label{alg:allfree}
  \begin{algorithmic}
    \State let $B$ be the matrix representation of the boundary operator 
    \For{$j=1, \ldots, N$} \Comment (OUTERLOOP)
      \While{there exists $i < j$ with $L_B(i) = L_B(j) \not = -\infty$} \Comment (INNERLOOP)
         \State let $s = - B_{L_B(j), j} / B_{L_B(i), i}$ \Comment (A)
         \State add $s \times (\textrm{column}\  i)$ to column $j$ of $B$
      \EndWhile
      \If{$L(j) \not = -\infty$ and $B_{L_{B}(j), j} \not \in \{\pm 1\}$} \Comment (B)
        \State print $|B_{L_B(j), j}|$
        \State \Return ``dependent''
      \EndIf
    \EndFor
    \State \Return ``independent''
  \end{algorithmic}
\end{algorithm}

We remark that $B_{L_{B}(i), i}$ in this algorithm is always $\pm 1$ at (A), so
the division at (A) always applies. This is because the condition is
checked at (B).

For the proof, we use ideas presented in the Appendix~\ref{sec:proof-alg1}.
We also use Notation~\ref{notation:appendix} in Appendix~\ref{sec:proof-alg1} and
check whether
$H(X_n, X_m; \mathbb{Z}) = \bigoplus_{q=0}^{M} H_q(X_n, X_m; \mathbb{Z})$
has a non-zero torsion subgroup for every $m < n$.
We assume that $\dim(\mathbb{X}) \leq M + 1$ by removing all simplices whose dimensions
exceed $M + 1$.

First we prove $T(H_q(X_n, X_m; \mathbb{Z})) = 0$ for every $m < n$
when the algorithm returns ``independent''.
Let $\hat{B}$ be the matrix $B$ just before returning ``independent''.
Since division is not used
in the proof of Fact~\ref{fact:algpd-basis} in Section~\ref{subsec:proof-algpd-basis},
the discussion can also apply to
$\mathbb{Z}$-homology and we can find a basis of 
$C(X_N; \mathbb{Z})$, $\{\tilde{\sigma}_1, \ldots, \tilde{\sigma}_N\}$, satisfying
Condition~\ref{cond:phbasis} (i), (ii), (iii), and (iv). We can explicitly write the bases of
$C(X_m; \mathbb{Z})$ and $C(X_n, X_m; \mathbb{Z}) $ as follows:
\begin{equation}
  \begin{aligned}
    &\{\tilde{\sigma}_{1}, \ldots, \tilde{\sigma}_{m} \}
    \text{ is a basis of } C(X_m; \mathbb{Z}), \\
    &\{\tilde{\sigma}_{m+1} + C(X_m;\mathbb{Z}), \ldots, \tilde{\sigma}_{n} + C(X_m;\mathbb{Z}) \}
    \text{ is a basis of } C(X_n, X_m; \mathbb{Z}). \\
  \end{aligned}
\end{equation}
Let $\partial_{n,m}: C(X_n, X_m; \mathbb{Z}) \to C(X_n, X_m; \mathbb{Z}) $ be
the boundary operator on relative chain complexes. 
From Condition~\ref{cond:phbasis} (ii), (iii), and (iv), 
$\ker \partial_{n,m}$ and $\im \partial_{n,m}$ are both $\mathbb{Z}$ free modules
and the bases are
\begin{equation}
  \begin{aligned}
    &\{\tilde{\sigma}_k + C(X_m; \mathbb{Z}) \mid  m < k \leq n, k \in D' \sqcup E\} \\
    \sqcup &\{\tilde{\sigma}_k + C(X_m; \mathbb{Z}) \mid  m < k \leq n, k \in D, L_{\hat{B}}(k) < m\},
  \end{aligned}
\end{equation}
and
\begin{equation}
  \begin{aligned}
    &\{\tilde{\sigma}_{L(k)} + C(X_m; \mathbb{Z}) \mid  m < k \leq n, k \in D, m < L_{\hat{B}}(k)\} \\
    =&\{\tilde{\sigma}_{k} + C(X_m; \mathbb{Z}) \mid  m < k \leq n, k \in D', L_{\hat{B}}^{-1}(k) \leq n \}.
  \end{aligned}
\end{equation}

Therefore, the basis of $H(X_n, X_m; \mathbb{Z}) = \ker \partial_{n,m} / \im \partial_{n,m}$
can be written as follows:
\begin{equation}
  \begin{aligned}
    & \{[\tilde{\sigma}_k + C(X_m; \mathbb{Z})] \mid
    m < k \leq n, k \in E \} \\
    \sqcup & \{[\tilde{\sigma}_k + C(X_m; \mathbb{Z})] \mid
    m < k \leq n, k \in D', n < L_{\hat{B}}^{-1}(k) \},
  \end{aligned}
\end{equation}
where $[z + C(X_m; \mathbb{Z})]$ is a homology class of $z + C(X_m; \mathbb{Z})$
in $H(X_n, X_m; \mathbb{Z})$.
Therefore, $H(X_n, X_m; \mathbb{Z})$ is a free $\mathbb{Z}$-module and
we complete the proof for the ``independent'' case.

Next we show that there is a pair $(m, n)$ such that
$T(H(X_n, X_m; \mathbb{Z})) \not = 0$ if the algorithm returns ``dependent''.
In that case, condition (B) in the algorithm is true for one $j$, so
let $n$ be that $j$ and $\hat{B}$ be the matrix $B$ at that time.
We consider the subfiltration $\mathbb{X}_n = \emptyset = X_0 \subset \cdots \subset X_{n-1}$.
Algorithm~\ref{alg:allfree} applies on the subfiltration, so we can
find a basis of $C(X_{n-1})$ satisfying Condition~\ref{cond:phbasis}(i)-(iv).
That is, there is a basis of $C(X_{n-1})$,
$\{\tilde{\sigma}_1, \ldots, \tilde{\sigma}_{n-1}\}$, and
a decomposition of $\{1, \ldots, n-1\}$, $D_n \sqcup D_n' \sqcup E_n$,
such that the following conditions hold.
\begin{enumerate}[(a)]
\item\label{enum:basis} $\{\tilde{\sigma}_1,\ldots, \tilde{\sigma}_k\}$ is a basis of $C(X_k; \mathbb{Z})$
  for any $1 \leq k < n$.
\item $\partial \tilde{\sigma}_j \not = 0$ for $j \in D_n$.
\item $L_{\hat{B}}$ is a bijection from $D_n$ to $D'_n$ and
  $\partial \tilde{\sigma}_j = \tilde{\sigma}_{L_{\hat{B}}(j)}$ for any $j \in D_n$.
\item $\partial \tilde{\sigma}_i = 0$ for $i \in D'_n \sqcup E_n$.
\end{enumerate}
Furthermore, since the loop (INNERLOOP) also terminates at $j = n$,
$L_{\hat{B}}(n)$ is not $-\infty$ and
there exists $\hat{\sigma}_n \in C(X_n; \mathbb{Z})$ such that the
following conditions hold:
\begin{equation}
  \begin{aligned}
    C(X_n) & = C(X_{n-1}) \oplus \left< \hat{\sigma}_n \right>, \\
    \partial \hat{\sigma}_n &= \hat{B}_{L_{\hat{B}}(n), n} \sigma_{L(n)} +
    \sum_{1 \leq i < L_{\hat{B}}(n)} \hat{B}_{ij} \sigma_i.
  \end{aligned}
\end{equation}
By the same discussion in Section~\ref{subsec:proof-algpd-basis},
there exist integers $\{\beta_i\}_{i=1}^{L_{\hat{B}}(n)-1}$ such that
\begin{equation}\label{eq:p-mult}
  \partial \hat{\sigma}_n = \hat{B}_{L_{\hat{B}}(n), n} \tilde{\sigma}_{L_{\hat{B}}(n)} +
  \sum_{1 \leq i < L_{\hat{B}}(n)} \beta_i \tilde{\sigma}_i,
\end{equation}
holds.
We can also show $\partial \sigma_{L_{\hat{B}}(n)} = 0 $ in the same manner as
in the proof of the claim in Appendix~\ref{subsec:proof-algpd-basis}. Therefore,
$L_{\hat{B}}(n) \in D'_n \sqcup E_n$, but since $L_{\hat{B}}(n) \not = L_{\hat{B}}(i)$
for any $1 \leq i < n$, $L_{\hat{B}}(n) \not \in D'_n$ and we have $L_{\hat{B}}(n) \in E_n$.
Now let $m := L_{\hat{B}}(n) - 1$.
From (a)-(d) and \eqref{eq:p-mult},
the bases of $\ker \partial_{n,m}$ and $\im \partial_{n,m}$ can be explicitly
written as follows:
\begin{equation}
  \begin{aligned}
    &\{\tilde{\sigma}_k + C(X_m; \mathbb{Z}) \mid  m < k < n, k \in D'_n \sqcup E_n\} \\
    \sqcup &\{\tilde{\sigma}_k + C(X_m; \mathbb{Z}) \mid  m < k < n, k \in D_n, L_{\hat{B}}(k) < m\},
  \end{aligned}
\end{equation}
and
\begin{equation}
  \begin{aligned}
    &\{\tilde{\sigma}_{L_{\hat{B}}(k)} + C(X_m; \mathbb{Z}) \mid  m < k < n, k \in D_n, m < L_{\hat{B}}(k)\} \\
    \sqcup & \{ p \tilde{\sigma}_{m+1} + C(X_m; \mathbb{Z}) \},
  \end{aligned}
\end{equation}
where $p = |\hat{B}_{m+1, n}|$. Using $m + 1 \in E_n$, finally we have
\begin{equation}
  \begin{aligned}
    H(X_n, X_m; \mathbb{Z}) =&
    \left< [\tilde{\sigma}_{k} + C(X_m; \mathbb{Z})] \mid
      m < k < n, k \in D'_n, L_{\hat{B}}^{-1}(k) \leq n \right> \\
    \oplus & \left< [\tilde{\sigma}_{k} + C(X_m; \mathbb{Z})] \mid
      m < k < n, k \in E_n\backslash\{ m + 1\}  \right> \\
    \oplus& \left< [\tilde{\sigma}_{m+1} + C(X_m; \mathbb{Z})] \right>
  \end{aligned}
\end{equation}
and
\begin{equation}
  \left< [\tilde{\sigma}_{m+1} + C(X_m; \mathbb{Z})] \right> \simeq \mathbb{Z}_p.
\end{equation}
The proof for the ``dependent'' case is completed.

Here, when the algorithm returns ``dependent'', the number $p$ is displayed. This facilitates understanding the dependency
of $D(\mathbb{X}; \mathbb{Z}_{p'})$ to a prime $p'$ which is a divisor of $p$.

\section{Algorithm implementation}\label{sec:implementation}
The judgement algorithm is implemented in HomCloud\footnote{\url{https://www.wpi-aimr.tohoku.ac.jp/hiraoka_labo/homcloud/index.en.html}}. 
The twist algorithm introduced by
\cite{Chen11persistenthomology} is used for faster
computations. The program correctly judges the existence of the torsion
for pointclouds shown in Fig.~\ref{fig:doubletripleloop} (a) and (e).

\subsection{Performance benchmark}

In this section, we explore the performance of Algorithm~\ref{alg:allfree}.
We compare the program implemented in HomCloud
and Phat \citep{phat}\footnote{\url{https://bitbucket.org/phat-code/phat/}}.
The Phat code is straightforward and efficient.
The input filtration for the performance comparison is 
an alpha filtration constructed from random 5000 and 50000 points in $\mathbb{R}^3$.
Five trials were undertaken and the average computation time is shown.
In Phat, we use twist-algorithm with \verb|bit_tree_pivot_column|, as recommended by
\cite{phat}. The benchmark is executed on a PC with a 1.5 GHz Intel(R) Core(TM) i7-8500Y CPU, 16 GB of memory, and the Debian 10.0 operating system.
Both programs run on a single core.
Results are shown in Table~\ref{tab:performance}.

\begin{table}[htbp]
  \centering
  \begin{tabular}{c|c|c} \hline
    & 5000 points & 50000 points \\ \hline
    Phat &  0.0282 sec & 0.446 sec \\ \hline
    HomCloud & 0.0323 sec & 0.550 sec \\ \hline
  \end{tabular}
  \caption{Performance benchmark results}
  \label{tab:performance}
\end{table}

According to the benchmark, our new program is c.~$\times$1.20 slower than Phat.
Phat uses $\mathbb{Z}_2$ as a coefficient field and implements
fast arithmetic operations by using bit-wise operations. The technique likely renders Phat faster and we conclude that the performance of 
our program is roughly as efficient as Phat.

\section{Probability of torsion appearance}\label{sec:probability}
Here we measured the probability of the appearance of torsions
of random filtrations by a numerical experiment.
Corollary~\ref{cor:M_0} and Corollary~\ref{cor:M_munus_1} already ensures
the independence of persistence diagrams from $\Bbbk$
for a filtration embedded in $\mathbb{R}^2$. Therefore we started from filtrations
in $\mathbb{R}^3$.

We generated a random filtration from a pointcloud sampled from 
a Poisson point process in $[0, 1]^3$.
The average number of points is 1000. 
Thus, a random number $k$ is sampled from the Poisson
distribution whose parameter is 1000 and $k$ points are uniformly randomly
sampled in $[0, 1]^3$. An alpha filtration was computed
from the generated pointcloud and the condition was judged by 
HomCloud. Here, 10000 trials were carried out.
Only one filtration had non-trivial torsion; thus, 9999 filtrations had trivial torsion\footnote{
 Run-time errors occurred two times in these 10000 trials.
  When an error occurred, we disposed of the input
  data and retried random sampling. The cause of the errors is probably
  the violation of the general position condition of
  the randomly generated pointcloud.
}. In sum, it can be stated that a filtration with non-trivial torsion is possible, but very rare.
This numerical experiment suggests that there is some mathematical
mechanism explaining why a random filtration with non-trivial torsion is quite
rare. Exploring this further here is beyond the scope of the current paper.

In contrast \cite{doi:10.1080/10586458.2018.1473821} experimentally showed that torsion subgroups often
appeared in random $d$-complex $Y \sim Y_d(n, p)$, introduced by \cite{Linial*2006}. 
We apply our algorithm to random filtrations used in the paper. Let $\bar{Y}(n)$ be a simplex on $n$ vertices and $Y_0$
the $(d-1)$-skeleton of $\bar{Y}(n)$.
$Y_k$ for $k=1, \ldots, m$ is randomly generated by adding a $d$-simplex to $Y_{k-1}$. The $d$-simplex
is uniformly randomly sampled from all $d$-simplices in $\bar{Y}(n) \backslash Y_{k-1}$. We apply the algorithm to the
filtration
$Y_0 \subset Y_1 \subset \cdots \subset Y_m$. We used $d=2, n=75, m=5000$. The number of random flirtations
was 10000. In the experiment we found that all 10000 random filtrations have non-trivial torsion.

The above two experiments are contrasting. We expect that the difference comes from the
dimension of the space. In the first experiment a filtration is embedded in $\mathbb{R}^3$ and
in the second experiment $\bar{Y}(75)$ can be embedded in $\mathbb{R}^{74}$. The above experiments
suggest that a random filtration embedded in a higher dimensional space has more non-trivial torsion subgroups
in the relative homology groups than a filtration embedded in a lower dimensional space.
Exploring the problem further here is also beyond the scope of the current paper.

Anyway,
the experiment also suggests that we do not need to 
be concerned about the coefficient field in most cases if the space is $\mathbb{R}^3$. Thus, if there are concerns about the field choice problem in future research contexts, our proposed algorithm would be helpful.


\section{Proof of Theorem~\ref{thm:r-wasserstein}}\label{sec:convex}

In this section, we assume the following conditions.
\begin{cond}
There exists $0 = r_0 < r_1 < \ldots < r_N < r_{N+1} = \infty$ such that
$r_k \leq r < r_{k+1}$ implies $X_r = X_{r_k}$.
\end{cond}
This means that the filtration is assumed to be right-continuous.
This condition is not essential and we can prove the theorem if
the filtration is left-continuous. We assume right-continuous for expository purposes.
From this condition and $H_q( \cup_t X_t) = 0$, all birth-death pairs can be
written as $(r_k, r_\ell)$ for $0 \leq k < \ell \leq N$.
Hence, using persistent Betti numbers, we have the following equation:
\begin{equation}
    \begin{aligned}
    & \sum_{(b, d) \in D_q(\mathbb{X}; \mathbb{R})} f(d - b) \\
    =& \sum_{0 \leq k < \ell \leq N}f(r_\ell - r_k)\left(
    \beta_{r_k}^{r_{\ell-1}}(\Bbbk) - \beta_{r_{k-1}}^{r_{\ell-1}}(\Bbbk)
    - \beta_{r_k}^{r_{\ell}}(\Bbbk) + \beta_{r_{k-1}}^{r_{\ell}}(\Bbbk)
    \right) \\
    =& \sum_{0 \leq k < \ell \leq N} \beta_{r_{k}}^{r_{\ell}}(\Bbbk)(
    f(r_{\ell+1} - r_{k}) - f(r_{\ell+1} - r_{k+1})
    - f(r_{\ell} - r_{k}) + f(r_{\ell} - r_{k+1}) ).
    \end{aligned}\label{eq:f_sum}
\end{equation}

Now we prove the following inequality:
\begin{equation}
f(r_{\ell+1} - r_{k}) - f(r_{\ell+1} - r_{k+1})
    - f(r_{\ell} - r_{k}) + f(r_{\ell} - r_{k+1}) ) \geq 0. \label{eq:f_convex}
\end{equation}
In addition, if $f$ is strictly convex, the left-hand side is
strictly positive.
First we prove \eqref{eq:f_convex} under the condition of
$r_{\ell+1} - r_{k+1} \geq r_{\ell} - r_{k}$. In this case,
\begin{equation}
    \begin{aligned}
    & f(r_{\ell+1} - r_{k}) - f(r_{\ell+1} - r_{k+1})
    - f(r_{\ell} - r_{k}) + f(r_{\ell} - r_{k+1}) \\
    = & \left( f(r_{\ell+1} - r_{k}) - f(r_{\ell+1} - r_{k+1}) \right)
    - \left( f(r_{\ell} - r_{k}) - f(r_{\ell} - r_{k+1}) \right) \\
    =& f'(\zeta_1) (r_{k+1} - r_{k}) - f'(\zeta_2)(r_{k+1} - r_{k}) \\
    =& (r_{k+1} - r_{k})(f'(\zeta_1) - f'(\zeta_2)),
    \end{aligned}
\end{equation}
where $r_{\ell+1} - r_{k+1} \leq \zeta_1 \leq r_{\ell+1} - r_{k}$ and
$r_{\ell} - r_{k+1} \leq \zeta_2 \leq r_{\ell} - r_{k}$. Here, 
from the assumption of $r_{\ell+1} - r_{k+1} \geq r_{\ell} - r_{k}$ and
the convexity of $f$, we have $f'(\zeta_1) - f'(\zeta_2) \geq 0$ and
the inequality \eqref{eq:f_convex}. The strict positivity from
strict convexity is trivial. When $r_{\ell+1} - r_{k+1} \leq r_{\ell} - r_{k}$,
we can prove the inequality in a similar way by exchanging the role
of $f(r_{\ell+1} - r_{k+1})$ and $f(r_{\ell} - r_{k})$ in the foregoing.


From the discussion in Section~\ref{sec:proof-allfree}, we have
\begin{equation}
\beta_{r_{k}}^{r_{\ell}}(\mathbb{R}) \geq \beta_{r_{k}}^{r_{\ell}}(\mathbb{Z}_p),
\label{eq:beta_ineq_1}
\end{equation}
for any $p$, $k$, and $\ell$. Furthermore,
 if $D_q(\mathbb{X}; \mathbb{R}) \not = D_q(\mathbb{X}; \mathbb{Z}_p)$, there exists $k < \ell$ such that
\begin{equation}
\beta_{r_{k}}^{r_{\ell}}(\mathbb{R}) > \beta_{r_{k}}^{r_{\ell}}(\mathbb{Z}_p)    
\label{eq:beta_ineq_2}
\end{equation}
holds. From \eqref{eq:f_sum}, \eqref{eq:f_convex}, \eqref{eq:beta_ineq_1}, 
and \eqref{eq:beta_ineq_2}, we complete the proof of the theorem.

\section{Conclusions}\label{sec:conclusion}


In this paper, we focus on mathematical phenomena concerning the change of
the coefficient field in persistent homology. We show that the torsion
of relative homology groups $H_q(X_n, X_m; \mathbb{Z})$ plays an essential role
for the phenomena. We also propose an algorithm to judge the independence
of the field change. The algorithm is implemented in software, HomCloud.

Using the algorithm, we show that the probability of persistence
diagrams changing as a result of field changes is not zero, but very low 
for random pointclouds in $\mathbb{R}^3$. This suggests that we do not need to be particularly concerned about
the choice of the field in most practical persistent homology contexts
if we approach persistence diagrams in statistical terms. To assuage researchers' future concerns about this issue, the  torsion condition can be checked by the algorithm.

Of course, where torsion structures are important, such as 
Klein bottles or M\"obius strip, the choice of the coefficient field is 
important. We also suggest that the choice of the coefficient field is 
important for high dimensional data by the numerical experiment on $\bar{Y}(75)$.
In such contexts, further study is required into the torsion
on the filtrations.

Further, the results herein suggest that the
``difficulty'' of computation of $D_q(\mathbb{X}; \Bbbk)$ depends on the torsion.
If all torsions are zero, $D_q(\mathbb{X}; \Bbbk)$ for any $\Bbbk$ is computable
by computing $D_q(\mathbb{X}; \Bbbk)$ for only one $\Bbbk$, for example, $\mathbb{Z}_2$.
If not, to compute $D_q(\mathbb{X}; \Bbbk)$ for many $\Bbbk$ is more onerous.
In that case, we can apply the algorithm in \cite{BJDMC} for faster computation;
however, that algorithm simultaneously computes $D_q(\mathbb{X}; \Bbbk)$ for multiple, but
not for all, $\Bbbk$. This phenomenon is not dissimilar to a theorem in \cite{optimal-Day}. Those authors proved that
the difficulty of computing a kind of
optimization problem on homology algebra depends on the existence of the non-zero torsion
subgroup of the relative homology group.
Integer programming on homology algebra can be solved by linear programming
if the torsion-free condition holds. Integer programming requires much more time
than linear programming in the sense of computational complexity theory.
Of course, our paper and \cite{optimal-Day} concern different problems,
but the results are similar because of the shared focus on the
torsions of relative homology. These results suggest that
the existence of non-trivial torsion subgroups in relative homology
renders the problems of
computational homology more difficult.




