\section{Introduction}

The study of compactness properties in topological groups has been carried on for more than 70 years. In a seminal paper by Halmos, \cite{halmos}, it was shown that the real line can be endowed with a compact group topology. We note that algebraically the real line is the sum of $\mathfrak c$ copies of the rationals, not only as an Abelian group but also as a $\mathbb Q$-vector space (a fact that is used in Halmos's result and in much of the subsequent work in the matter).

We recall that, given an ultrafilter $\mathcal U$ and a topological space $X$, a $\mathcal U$-\textit{limit} of a sequence $(x_n)_{n\in\omega}$ in $X$ is a $z\in X$ such that for every neighbourhood $A$ of $z$, $\{n\in\omega:x_n\in A\}\in\mathcal U$. A topological space $X$ is called $\mathcal U$-\textit{compact} if every sequence has a $\mathcal U$-limit.

In the paper \cite{castro-pereira&tomita2010}, Castro and Tomita obtained a consistent classification -- assuming some cardinal arithmetic and the existence of a selective ultrafilter $p$ -- of the Abelian torsion groups which admit a $p$-compact group topology. This proved the consistency of large countably compact torsion groups without non-trivial convergent sequences.

A more recent result, \cite{bellini&rodrigues&tomita2021.Qkappa}, showed that given a selective ultrafilter $p$, $\mathbb Q^{(\kappa)}$ can be endowed with a $p$-compact Hausdorff group topology without non-trivial convergent sequences, whenever $\kappa=\kappa^\omega$; this hypothesis implies that $\cf(\kappa)>\omega$. It remained open then whether such a result could consistently hold for cardinals of countable cofinality.

This article answers that question, using forcing to obtain a model where $\lambda$ is a cardinal whose cofinality is $\omega$ and such that $\mathbb Q^{(\lambda)}$ has a $\mathcal U$-compact Hausdorff group topology without non-trivial convergent sequences, where $\mathcal U$ is a given selective ultrafilter.

\section{Notation}

We shall fix throughout this article a cardinal $\lambda$ and a selective ultrafilter $\mathcal U$.

As usual, given $a\in\mathbb Q^\lambda$, its \textit{support} is $\supp a=\{\xi\in\lambda:a_\xi\ne0\}$.

Let $G$ be the Abelian group $\mathbb Q^{(\lambda)}=\{a\in\mathbb Q^\lambda:\supp a\text{ is finite}\}$ (considering coordinatewise addition as its operation).

If $E\subseteq\lambda$, we do a standard abuse of notation and consider $\mathbb Q^{(E)}=\{a\in G:\supp a\subseteq E\}$.

Given $\mu\in\lambda$, we define $\chi_\mu\in G$ by $\chi_\mu(\mu)=1$ and $\chi_\mu(\beta)=0$ for all $\beta\in\lambda$, $\beta\ne\mu$. Now, given $\zeta:\omega\to\lambda$, we define $\chi_\zeta:\omega\to G$ by $\chi_\zeta(n)=\chi_{\zeta(n)}$ for each $n\in\omega$. And given a $\mu\in\lambda$, we define $\vec\mu$ as the constant sequence of value $\mu$. Thus, $\chi_{\vec\mu}$ is the constant sequence of value $\chi_\mu$ (this will appear often in our work).

Since $\mathcal U$ is an ultrafilter on $\omega$, the \textit{ultrapower} of $G$ by $\mathcal U$, denoted $\Ult_\mathcal U(G)$, is the quotient of the set $G^\omega$ by the following equivalence relation: $g\sim h$ if and only if $\{n\in\omega:g(n)=h(n)\}\in\mathcal U$. We will make frequent use of the fact that $\Ult_\mathcal U(G)$ is a $\mathbb Q$-vector space with all operations defined naturally (that is via representatives). If $g\in G^\omega$, we will denote its class in $\Ult_\mathcal U(G)$ by $[g]_\mathcal U$.

We now fix $\mathcal H\subseteq G^\omega$ such that $([g]_\mathcal U:g\in\mathcal H)\cup([\chi_{\vec\mu}]_\mathcal U:\mu<\lambda)$ is a $\mathbb Q$-basis for $\Ult_\mathcal U(G)$.

\section{Forcing poset}

\begin{defin} \label{the.order}
We define $\mathcal P$ as the set of the tuples of the form  $(E, \alpha, \mathcal G, \xi, \phi)$ such that:

\begin{itemize}
    \item $E$ is a countable subset of $\lambda$ containing $\omega$,
    \item $\alpha < \mathfrak c$,
    \item $\mathcal G$ is a countable subset of $\mathcal H$,
    \item $\xi=(\xi_{g}: g \in \mathcal G$) is a family of elements of $\mathfrak c\cap E$,
    \item $\phi:\, \mathbb Q^{(E)}\to \mathbb T^\alpha$ is a homomorphism,
    \item $\mathcal U-\lim(\phi\circ g)=\phi(\chi_{\xi_g})$ for each $g\in\mathcal G$,

    \end{itemize}

We define $(E, \alpha, \mathcal G, \xi, \phi)\leq  (E', \alpha', \mathcal G', \xi', \phi')$
if:

\begin{enumerate}
    \item $E\supseteq E'$,
    \item $\alpha \geq \alpha'$,
    \item $\mathcal G \supseteq \mathcal G'$,
    \item $\xi_{g}=\xi'_{g}$ for each $g \in \mathcal G'$, and
    \item for every $\xi<\alpha'$ and $a \in \mathbb Q^{(E')}$, $\phi(a)(\xi)= \phi'(a)(\xi)$.
\end{enumerate}
 Given $p \in \mathcal P$, we may denote its components by $E^p$, $\alpha^p$, $\mathcal G^p$, $\xi^p$ and $\phi^p$.

 If $H$ is a generic filter over $\mathcal P$ then the generic homomorphism defined by $H$ is the mapping $\Phi$ of domain $\bigcup\{\dom(\phi^p): p \in H\}$ into $\mathbb T^\mathfrak c$ defined by $\Phi(\cdot)(\xi)=\bigcup\{\phi^p(\cdot)(\xi):p \in H,\xi<\alpha^p\}$. In other words, if $p \in H$, $a \in \mathbb Q^{(E^p)}$ and $\xi<\alpha_p$, then $\Phi(a)(\xi)=\phi^p(a)(\xi)$.
\end{defin}

Naturally, we must assure that such generic homomorphisms are well-defined and into $\mathbb T^\mathfrak c$. We will do so by showing that, assuming CH in the ground model, this forcing notion is $\omega_1$-closed and has the $\omega_2$-chain condition, and thus preserves cardinals and $\mathfrak c$.

\begin{prop}\label{denseopen.Hausdorff}
Let $e\in G\backslash\{0\}$. Then the set $\mathcal C_e=\{p\in\mathcal P:e\in\mathbb Q^{(E^p)}\text{ and }\phi^p(e)\ne0\}$ is open and dense in $\mathcal P$.
\end{prop}
\begin{proof}
Openness: suppose $p\in\mathcal C_e$ and $q\le p$. Then since $\phi^p(e)\ne0$, for some $\beta<\alpha^p$, $\phi^p(e)(\beta)\ne0$. By (2), $\beta<\alpha^p\le\alpha^q$, and by (1) $E^p\subseteq E^q$. It follows that $e\in\mathbb Q^{(E^q)}$ and, by (6), $\phi^q(e)(\beta)=\phi^p(e)(\beta)\ne0$. Thus, $q\in\mathcal C_e$ as well.

Denseness: now let $p\in\mathcal P$ be arbitrary. We shall produce a $q\le p$ such that $q\in\mathcal C_e$. First, take any $d_0,d_1\in G\backslash\{0\}$ such that $\supp e$, $\supp d_0$ and $\supp d_1$ are pariwise disjoint. Now take $C$ a countable subset of $\lambda$ such that $\omega\cup\supp e\cup\supp d_0\cup\supp d_1\cup\bigcup_{g\in\mathcal G,n\in\omega}\supp g(n)\subseteq C$.

The Main Lemma of \cite{bellini&rodrigues&tomita2021.Qkappa} (Lemma 3.4) tells us that there exists a homomorphism $\rho:\mathbb Q^{(C)}\to\mathbb T$ such that:
\begin{itemize}
    \item $\rho(e)\ne0$ and $\rho(d_0)\ne\rho(d_1)$;
    \item $\mathcal U-\lim(\rho\circ(\frac{1}{N}{g}))=\rho(\frac{1}{N}\chi_{\xi_g})$, for every $g\in\mathcal G$ and $N\in\omega$.
\end{itemize}

Define now $E^q:=E^p\cup C$ and extend $\phi^p:\mathbb Q^{(E^p)}\to\mathbb T^{\alpha^p}$ to a $\varphi:\mathbb Q^{(E^q)}\to\mathbb T^{\alpha^p}$ using the divisibility of the codomain. Also extend $\rho$ to a $\psi:\mathbb Q^{(E^q)}\to\mathbb T$. Define then $\alpha^q=\alpha^p+1$, $\mathcal G^q=\mathcal G^p$, $\xi^q=\xi^p$, and $\phi^q=\varphi^\frown\psi$.

It follows that $q\in\mathcal C_e$ and $q\le p$.
\end{proof}

\begin{prop}\label{denseopen.fullcodomain}
Let $\alpha<\mathfrak c$. Then the set $\mathcal A_\alpha=\{p\in\mathcal P:\alpha^p>\alpha\}$ is open and dense in $\mathcal P$.
\end{prop}
\begin{proof}
Openness: suppose $p\in\mathcal A_\alpha$ and $q\le p$. We have that $\alpha^p>\alpha$ and $\alpha^q\ge\alpha^p$, and so $q\in\mathcal A_\alpha$.

Denseness: let $p\in\mathcal P$. If $\alpha^p>\alpha$, then $p\in\mathcal A_\alpha$. Suppose now that $\alpha^p\le\alpha$. We define $q$ as follows: $E^q=E^p$, $\alpha^q=\alpha+1$, $\mathcal G^q=\mathcal G^p$, $\xi^q=\xi^p$, and $\phi^q={\phi^p}^\frown\psi$, where $\psi:\mathbb Q^{(E^q)}\to\mathbb T^{[\alpha^p,\alpha]}$ is the zero-homomorphism.

It follows that $q\in\mathcal A_\alpha$ and $q\le p$.
\end{proof}

\begin{prop}\label{denseopen.allbasicsequences}
Let $g\in\mathcal H$. Then the set $\mathcal S_g:=\{p\in\mathcal P:g\in\mathcal G^p\}$ is open and dense in $\mathcal P$.
\end{prop}
\begin{proof}
Openness: suppose $p\in\mathcal S_g$ and $q\le p$. Since $g\in\mathcal G^p$ and $\mathcal G^p\subseteq\mathcal G^q$, it follows that $g\in\mathcal G^q$ and thus $q\in\mathcal S_g$.

Denseness: Let $p\in\mathcal P$ be given. First, take $E$ a countable subset of $\lambda$ such that $\omega\cup E^p\subseteq E$ and $\bigcup_{k\in\omega}\supp g(k)\subseteq E$. Take any $\mu\in\mathfrak c\backslash E$.

Define now: $E^q=E\cup\{\mu\}$, $\alpha^q=\alpha^p$, $\mathcal G^q=\mathcal G^p\cup\{g\}$, and $\xi^q=\xi^p\cup\{(g,\mu)\}$.

Extend $\phi^p:\mathbb Q^{(E^p)}\to\mathbb T^{\alpha^p}$ to a $\psi:\mathbb Q^{(E)}\to\mathbb T^{\alpha^p}$ using divisibility. Now, since $\mathbb T^{\alpha^p}$ is a compact space, let $z=\mathcal U-\lim(\psi\circ g)$. Define then $\phi^q:\mathbb Q^{(E^q)}\to\mathbb T^{\alpha^q}$ as an extension of $\psi$, declaring that $\phi^q(\chi_\mu)=z$.

It follows that $q=(E^q,\alpha^q,\mathcal G^q,\xi^q,\phi^q)\in\mathcal S_g$ and $q\le p$.
\end{proof}

\begin{prop}\label{omega1closed}
$\mathcal P$ is $\omega_1$-closed.
\end{prop}
\begin{proof}
Let $(p_t:t\in\omega)$ be a decreasing sequence in $\mathcal P$. We shall produce an $r\in\mathcal P$ such that $r\le p_t$ for all $t\in\omega$.

Denote now $p_t=(E^t,\alpha^t,\mathcal G^t,\xi^t,\phi^t)$.

Define $E^r=\bigcup_{t\in\omega}E^t$, $\alpha^r=\sup_{t\in\omega}\alpha^t$, $\mathcal G^r=\bigcup_{t\in\omega}\mathcal G^t$ and given $g\in\mathcal G^r$, $\xi^r_g=\xi^t_g$ for any $t$ such that $g\in\mathcal G^t$ (this does not depend on such $t$'s).

Lastly, given $a\in\mathbb Q^{(E^r)}=\bigcup_{t\in\omega}\mathbb Q^{(E^t)}$ and $\xi<\alpha^r$, define $\phi^r(a)(\xi)=\phi^t(a)(\xi)$ for any $t$ such that $\xi<\alpha^t$ (again, this assignment does not depend on such $t$'s).
\end{proof}

We will now need a technical Lemma in order to guarantee the divergence of non-trivial sequences. This Lemma will require the use of the Main Lemma of \cite{bellini&rodrigues&tomita2021.Qkappa} and so for the sake of completeness we reproduce it here.

\begin{lem}[Main Lemma of \cite{bellini&rodrigues&tomita2021.Qkappa}]
		Fix a selective ultrafilter $\mathcal U$.
		Let $\mathcal F\subseteq G^\omega$ be a countable collection of distinct elements mod $\mathcal U$ such that $([f]_\mathcal U: f \in \mathcal F)\cup( [\chi_{\vec{\mu}}]_\mathcal U:\, \mu \in \lambda)$ is $\mathbb Q$-linearly independent in $\text{Ult}_\mathcal U(G)$.

		Let $d, d_0,d_1  \in G\setminus \{0\}$ with $\supp d$, $\supp d_0$, $\supp d_1$ pairwise disjoint, and $C$ be a countably infinite subset of $\lambda$ such that $\omega\cup \supp d\cup \supp d_0 \cup \supp d_1\cup \bigcup_{f \in \mathcal F, n \in \omega}\supp f(n) \subseteq C$. For each $f \in \mathcal F$, fix $\xi_f \in C$.

		Then there exists a homomorphism $\psi:\, {\mathbb Q}^{(C)}\longrightarrow {\mathbb T}$
		such that
		\begin{enumerate}[label=\alph*)]
			\item $\psi(d)\neq 0$, $\psi(d_0)\neq \psi(d_1)$, and
			\item $\mathcal U$-$\lim (\psi (\frac{1}{N}f))=\psi(\frac{1}{N}\chi_{\xi_f})$, for each $f \in \mathcal F$ and $N\in \omega$.\qed
		\end{enumerate}
	\end{lem}

\begin{lem} \label{not.converges.lemma}

Let $\mathcal G\subseteq\mathcal H$ be countable and $B\in \mathcal U$. Let $\mathcal H'$ be a finite subset of $\mathcal G$ and $(r_g:g\in\mathcal H')$ a family of rational numbers. Let $E\subseteq\lambda$ countably infinite such that $\omega\bigcup\cup_{g\in\mathcal G,n\in\omega}\supp g(n)\subseteq E$. Let $(\xi_g:g\in\mathcal G)$ be a family in $\mathfrak c\cap E$.

Then there exists a homomorphism $\phi:\, {\mathbb Q}^{(E)}\longrightarrow {\mathbb T}$
		such that
		\begin{enumerate}[label=\alph*)]

			\item $\mathcal U$-$\lim (\phi (\frac{1}{N}g))=\phi(\frac{1}{N}\chi_{\xi_g})$, for each $g\in\mathcal G$ and $N\in \omega$, and
			\item $(\phi(\sum_{g\in\mathcal H'}r_g g(n)):n\in B)$ does not converge.
		\end{enumerate}
	\end{lem}

	\begin{proof}  Let $B' \in \mathcal U$ be a subset of $B$ such that  $(\sum_{g\in\mathcal H'}r_g g(n):n\in B')$ is a one-to-one sequence, which is possible since the $g$'s are linearly independent mod $\mathcal U$ with the constant sequences and by the selectiveness of $\mathcal U$.

	Let ${\mathbb A}$ be an almost disjoint family on $B'$ of cardinality ${\mathfrak c}$ and $h_x:\, \omega \longrightarrow \{\sum_{g\in\mathcal H'}r_g g(n):\, n\in x\}$ be a bijection for each $x \in \mathbb A$. \\

		\textbf{Claim}: There exist $x_0,x_1 \in {\mathbb A}$ such that $\{ [g]_\mathcal U:\,g\in\mathcal G\} \cup \{ [\chi_{\vec{\mu}}]_\mathcal U:\, \mu \in \lambda \}\cup \{[h_{x_0}]_\mathcal U,[h_{x_1}]_\mathcal U\} $ is a linearly independent subset.\\

		\textbf{Proof of the claim:} Given $x_0, x_1 \in \mathbb A$, notice that $h_{x_0}(n)\neq h_{x_1}(n)$ for all but a finite numbers of $n$'s, so $[h_{x_0}]_\mathcal U\neq [h_{x_1}]_\mathcal U$. Since $\mathbb Q$ is countable, it follows that $\langle [h_{x}]_\mathcal U: x \in \mathbb A\rangle$ has cardinality $\mathfrak c$, so there is $J\subseteq\mathbb A$ such that $|J|=\mathfrak c$ and that $([h_x]_\mathcal U: x \in J)$ is linearly independent. Now notice that $\langle \mathcal G\rangle \oplus \langle\chi_{\vec\xi}: \xi \in E\rangle$ is countable, so there exist $x_0, x_1 \in J$ such that $\{ [g]_\mathcal U:\, g\in\mathcal G\} \cup \{ [\chi_{\vec{\mu}}]_\mathcal U:\, \mu \in E \}\cup \{[h_{x_0}]_\mathcal U,[h_{x_1}]_\mathcal U\} $ is linearly independent. Since all the supports of these elements are contained in $E$, it is straightforward to see that $\{ [g]_\mathcal U:\, g\in\mathcal G\} \cup \{ [\chi_{\vec{\mu}}]_\mathcal U:\, \mu \in \lambda \}\cup \{[h_{x_0}]_\mathcal U,[h_{x_1}]_\mathcal U\} $ is  linearly independent. \qed\\

		We will now apply Lemma 3.4 (the Main Lemma) of \cite{bellini&rodrigues&tomita2021.Qkappa} with ${\mathcal F}=\{ g:\,g\in\mathcal G\} \cup \{h_{x_0}, h_{x_1}\}$, $\xi _g=\xi_g$ for $g\in\mathcal G$, $\xi_{h_{x_0}}= 0$, $\xi_{h_{x_1}}= 1$, $d_0=\chi_0$, $d_1=\chi_1$, $d=\chi_2$ and $C=E$. Take $\psi:\mathbb Q^{(E)}\to\mathbb T$ given by the conclusion of the Lemma.

		Clearly condition a) of this Lemma is satisfied.

		Furthermore,
		$(\psi(h_{x_i}(k)):k\in \omega)$ has $\psi(\chi_i)$ as an accumulation point for $i<2$. Since these sequences are reorderings of a subsequence of
		$(\psi(\sum_{g\in\mathcal H'}r_g g(n)):n\in B)$ and  $\phi(\chi_0)\neq \phi(\chi_1)$, it follows that b) is satisfied.
	\end{proof}

\begin{prop}\label{not.converges}
Let $h\in G^\omega$ be a one-to-one sequence. Then the set $\mathcal E_h:=\{p\in\mathcal P:\text{there is }\beta<\alpha^p\text{ such that }(\phi^p(h(n))(\beta):n\in\omega)\text{ does not converge}\}$
\end{prop}
\begin{proof}
Openness: Suppose $p\in\mathcal E_h$ and $q\le p$. Then for some $\beta<\alpha^p$, $(\phi^p(h(n))(\beta):n\in\omega)$ does not converge. By (2), $\beta<\alpha^p\le\alpha^q$, and by (1) $E^p\subseteq E^q$. It follows that $h(n)\in\mathbb Q^{(E^q)}$ for all $n\in\omega$ and, by (6), $\phi^q(h(n))(\beta)=\phi^p(h(n))(\beta)$ for all $n\in\omega$. Since $(\phi^p(h(n))(\beta):n\in\omega)$ does not converge, then $(\phi^q(h(n))(\beta):n\in\omega)$ does not converge. Thus, $q\in\mathcal E_h$ as well.

Denseness: Let $p\in\mathcal P$ be given. Take $\mathcal H'\subseteq\mathcal H$ finite, $\mu_0,\ldots,\mu_{m-1}\in\lambda$ and $(r_g:g\in\mathcal H')$ and $(s_{\mu_j}:j<m)$ families of rational numbers such that $[h]_\mathcal U=\sum_{g\in\mathcal H'}r_g [g]_\mathcal U + \sum_{j<m}s_{\mu_j} [\chi_{\vec{\mu_j}}]_\mathcal U$.

We will define a decreasing sequence of conditions $(p_i:i\in\omega)$. First, we obtain $p_0\le p$ by applying Proposition \ref{denseopen.allbasicsequences} $|\mathcal H'|$ times in order to guarantee that $\mathcal H'\subseteq\mathcal G^{p_0}$.

Take an enumeration $(\gamma_k:k\ge1)$ of $\cup_{g\in\mathcal H', n\in\omega}\supp g(n)\bigcup\cup_{n\in\omega}\supp h(n)\bigcup\{\mu_j:j<m\}$.

Apply Proposition \ref{denseopen.Hausdorff} using $e=\chi_{{\gamma_1}}$ and obtain $p_1\le p_0$ such that $\chi_{{\gamma_1}}\in\mathbb Q^{(E^{p_1})}$, which implies $\gamma_1\in E^{p_1}$.

Now recursively apply Proposition \ref{denseopen.Hausdorff} for each $i>1$ using $e=\chi_{{\gamma_i}}$ and obtain $p_i\le p_{i-1}$ such that $\chi_{{\gamma_i}}\in\mathbb Q^{(E^{p_i})}$, which implies $\gamma_i\in E^{p_i}$.

Applying Proposition \ref{omega1closed}, we obtain a $p_\omega\le p_i$ for all $i\in\omega$.

We will now use Lemma \ref{not.converges.lemma} with $\mathcal G=\mathcal G^{p_\omega}$, $\mathcal H'=\mathcal H'$, $r_g=r_g$ for $g\in\mathcal H'$, $E=E^{p_\omega}$, $\xi_g=\xi^{p_\omega}_g$ for $g\in\mathcal G^{p_\omega}$ and $B\in\mathcal U$ such that $h(n)=\sum_{g\in\mathcal H'}r_g g(n) + \sum_{j<m}s_{\mu_j} \chi_{{\mu_j}}$ for all $n\in B$. We thus obtain a $\psi:\mathbb Q^{(E^{p_\omega})}\to\mathbb T$ such that
\begin{enumerate}[label=\alph*)]

			\item $\mathcal U$-$\lim (\psi (\frac{1}{N}g))=\psi(\frac{1}{N}\chi_{\xi_g})$, for each $g\in\mathcal G$ and $N\in \omega$, and
			\item $(\psi(\sum_{g\in\mathcal H'}r_g g(n)):n\in B)$ does not converge.
		\end{enumerate}

We define now a $q\le p_\omega$. Define $E^q=E^{p_\omega}$, $\alpha^q=\alpha^{p_\omega}+1$, $\mathcal G^q=\mathcal G^{p_\omega}$, $\xi^q=\xi^{p_\omega}$ and $\phi^q={\phi^{p_\omega}}^\frown\psi$.

Since $(\psi(\sum_{g\in\mathcal H'}r_g g(n)):n\in B)$ does not converge and $\sum_{j<m}s_{\mu_j} \chi_{\mu_j}$ is constant, it follows that $(\psi(h(n)):n\in B)$ does not converge, and so $(\psi(h(n)):n\in\omega)$ does not converge.

Let $\beta=\alpha^p$. The definition $\phi^q={\phi^{p_\omega}}^\frown\psi$ means that for all $x\in\mathbb Q^{(E^q)}$, $\phi^q(x)(\beta)=\psi(x)$. Thus,  $(\psi(h(n)):n\in\omega)$ does not converge means that $(\phi^q(h(n))(\beta):n\in\omega)$ does not converge, proving that $q\in\mathcal E_h$.

\end{proof}

\begin{prop}\label{omega2cc}
Assume CH. Then the partial order $\mathcal P$ has the $\omega_2$-chain condition.
\end{prop}
\begin{proof}
Since under CH, $\mathfrak c^+=\omega_2$, we will show that $\mathcal P$ has the $\mathfrak c^+$-c.c.. So let $\mathcal Q\subseteq\mathcal P$ of cardinality $\mathfrak c^+$. We will show that $\mathcal Q$ has a subset consisting of $\mathfrak c^+$ pairwise compatible elements.

First, take a $\mathcal Q_0\subseteq\mathcal Q$ of cardinality $\mathfrak c^+$ and an $\alpha<\mathfrak c$ such that $\alpha_q=\alpha$ for each $q\in\mathcal Q_0$.

Using the $\Delta$-system Lemma, take a $\mathcal Q_1\subseteq\mathcal Q_0$ of cardinality $\mathfrak c^+$ such that $\{E^q:q\in\mathcal Q_1\}$ is a $\Delta$-system of root $\tilde E$. Now, using CH, we have that $\left|{(\mathbb T^\alpha)}^{\mathbb Q^{(\tilde E)}}\right|=\mathfrak c$, and thus we may take a $\mathcal Q_2\subseteq\mathcal Q_1$ of cardinality $\mathfrak c^+$ such that ${\phi^q}|_{\mathbb Q^{(\tilde E)}}={\phi^p}|_{\mathbb Q^{(\tilde E)}}$ for all $q,p\in\mathcal Q_2$.

Using the $\Delta$-system Lemma again, take $\mathcal Q_3\subseteq\mathcal Q_2$ of cardinality $\mathfrak c^+$ such that $\{\mathcal G^q:q\in\mathcal Q_3\}$ is a $\Delta$-system of root $\tilde\mathcal G$. Now since for each $q\in\mathcal Q_3$, $(\xi^q_g:g\in\tilde\mathcal G)\in\mathfrak c^{\tilde\mathcal G}$ and $|\mathfrak c^{\tilde\mathcal G}|=\mathfrak c$, take $\mathcal Q_4\subseteq\mathcal Q_3$ of cardinality $\mathfrak c^+$ such that for all $q,p\in\mathcal Q_4$ and each $g\in\tilde\mathcal G$, $\xi^q_g=\xi^p_g$.

A common extension to $q,p\in\mathcal Q_4$ is an $r$ defined as follows: $E^r=E^q\cup E^p$; $\alpha^r=\alpha^q=\alpha^p$; $\mathcal G^r=\mathcal G^q\cup\mathcal G^p$; $\xi^r=\xi^q\cup\xi^p$.

To define $\phi^r$, notice that $\mathbb Q^{(E^r)}=\mathbb Q^{(E^q\backslash\tilde E)}\oplus\mathbb Q^{(\tilde E)}\oplus\mathbb Q^{(E^p\backslash\tilde E)}$. Then, let $\pi_0:\mathbb Q^{(E^r)}\to\mathbb Q^{(E^q\backslash\tilde E)}$, $\pi_1:\mathbb Q^{(E^r)}\to\mathbb Q^{(\tilde E)}$ and $\pi_2:\mathbb Q^{(E^r)}\to\mathbb Q^{(E^p\backslash\tilde E)}$ be the projections. Define $\phi^r=\phi^q\circ\pi_0+\phi^q\circ\pi_1+\phi^p\circ\pi_2=\phi^q\circ\pi_0+\phi^p\circ\pi_1+\phi^p\circ\pi_2$ and we are done.
\end{proof}

\begin{teo}\label{generic.monomorphism.theorem}
Assume CH. Then the forcing notion $\mathcal P$ preserves cofinalities and cardinals, preserves $\mathfrak c$ and does not add reals. Given $H$ a $\mathcal P$-generic filter, the associated $\Phi$ (as in \ref{the.order}) is a well-defined monomorphism from $G$ to $\mathbb T^\mathfrak c$. Also, given any $g\in\mathcal H$, there exists a $\xi\in\mathfrak c$ such that $\mathcal U-\lim(\Phi\circ g)=\Phi(\chi_\xi)$. Furthermore, given any one-to-one sequence $h\in G^\omega$, $\Phi\circ h$ does not converge.
\end{teo}
\begin{proof}
By Propositions \ref{omega1closed} and \ref{omega2cc}, $\mathcal P$ preserves cofinalities (and therefore cardinals), does not add reals and preserves $\mathfrak c$. Note that since being a basis for $\Ult_\mathcal U(G)$ is absolute for transitive models of ZFC, $\mathcal H$ is still a basis for $\Ult_\mathcal U(G)$ in the extension.

Let $H$ be a $\mathcal P$-generic filter and let $\Phi$ be its associated homomorphism.

First, let us see that $\Phi:G\to\mathbb T^\mathfrak c$ is well-defined. Let $q,p\in H$ and suppose $\xi<\min\{\alpha^q,\alpha^p\}$ and $e\in\mathbb Q^{(E^q\cap E^q)}$. We must see that $\phi^q(e)(\xi)=\phi^p(e)(\xi)$. Take $r\in H$ such that $r\le q,p$. Then $\xi<\alpha^r$ and $e\in\mathbb Q^{(E^r)}$, and by item (5) of Definition \ref{the.order}, $\phi^q(e)(\xi)=\phi^r(e)(\xi)=\phi^p(e)(\xi)$.

Now let $\alpha<\mathfrak c$ and $e\in\mathbb Q^{(\lambda)}$ such that $e\ne0$. Since $\mathcal C_e$ and $\mathcal A_\alpha$ are open and dense, let $p\in H$ such that $e\in\mathbb Q^{(E^p)}$, $\phi^p(e)\ne0$ and $\alpha^p>\alpha$. Since $\phi^p(e)\ne0$, there is a $\xi\le\alpha^p$ such that $\phi^p(e)(\xi)\ne0$, and therefore $\Phi(e)(\xi)\ne0$, so that $\Phi(e)\ne0$. And since $\alpha\subseteq\alpha^p\subseteq\dom\Phi(e)\subseteq\mathfrak c$, and $\alpha$ was arbitrary, it follows that $\dom\Phi(e)=\mathfrak c$.

We have thus seen that the domain of $\Phi$ is $\mathbb Q^{(\lambda)}$, the codomain is $\mathbb T^\mathfrak c$ and that $\Phi$ is injective.

Now we see that $\Phi$ is a homomorphism. Let $e,e'\in\mathbb Q^{(\lambda)}$. Since $\mathcal C_e$, $\mathcal C_{e'}$ and $\mathcal C_{e+e'}$ are dense and open, take $p\in H$ such that $e,e',e+e'\in\mathbb Q^{(E^p)}$. We know that $\phi^p$ is a homomorphism, and so $\Phi(e+e')=\phi^p(e+e')=\phi^p(e)+\phi^p(e')=\Phi(e)+\Phi(e')$.

Let now $g\in\mathcal H$. Since $\mathcal S_g$ is open and dense, let $p\in H$ such that $g\in\mathcal G^p$. We have then that $\mathcal U-\lim(\phi^p\circ g)=\phi^p(\xi_g)$. Let us see that $\mathcal U-\lim(\Phi\circ g)=\Phi(\xi_g)$. Let $F$ be a finite subset of $\mathfrak c$ and let $\alpha<\mathfrak c$ such that $F\subseteq\alpha$. Since $\mathcal A_\alpha$ is open and dense, and $p\in H$, let $q\in H$ such that $q\le p$ and $\alpha^q>\alpha$. We have then that $\mathcal U-\lim(\pi_F\circ\phi^q\circ g)=(\pi_F\circ\phi^q)(\xi_g)$. Since $\pi_F\circ\phi^q=\pi_F\circ\Phi$ (due to $\alpha^q\supseteq F$), it follows that $\mathcal U-\lim(\pi_F\circ\Phi\circ g)=(\pi_F\circ\Phi)(\xi_g)$, as we sought for.

Finally, let $h\in G^\omega$ be a one-to-one sequence. Since $\mathcal E_h$ is open and dense, let $p\in H\cap\mathcal E_h$. Take then a $\beta<\alpha^p$ such that $(\phi^p(h(n))(\beta):n\in\omega)$ does not converge. Since $\Phi(h(n))(\beta)=\phi^p(h(n))(\beta)$ for each $n\in\omega$, it follows that  $(\Phi(h(n))(\beta):n\in\omega)$ does not converge, which in turn implies that  $(\Phi(h(n)):n\in\omega)=\Phi\circ h$ does not converge.
\end{proof}

\begin{teo}
It is consistent with ZFC that given $\lambda$ a countably cofinal cardinal and $\mathcal U$ a selective ultrafilter, $G$ can be endowed with a $\mathcal U$-compact Hausdorff group topology without non-trivial convergent sequences.
\end{teo}
\begin{proof}
Consider the forcing model obtained via forcing with $\mathcal P$. We fix a generic monomorphism $\Phi$ as in \ref{generic.monomorphism.theorem}. Since we have that $\Phi$ is a monomorphism from $G$ to $\mathbb T^\mathfrak c$, then $\Phi$ induces a Hausdorff group topology in $G$ such that for any $g\in\mathcal H$, there exists a $\xi\in\mathfrak c$ such that $\mathcal U-\lim g=\chi_\xi$. Fix one such $\xi_g$ for each $g\in\mathcal H$.

Now let us see that such topology is indeed $\mathcal U$-compact. Let $f\in G^\omega$. Since $([g]_\mathcal U:g\in\mathcal H)\cup([\chi_{\vec\mu}]_\mathcal U:\mu<\lambda)$ is a $\mathbb Q$-basis for $\Ult_\mathcal U(G)$, there exist families $(r_g:g\in\mathcal H)$ and $(s_\mu:\mu<\lambda)$ of rational numbers, all but finitely many of which are 0, such that $[f]_\mathcal U=\sum_{g\in\mathcal H}r_g\cdot[g]_\mathcal U+\sum_{\mu<\lambda}s_\mu\cdot[\chi_{\vec\mu}]_\mathcal U$. It follows then that $\mathcal U-\lim f=\sum_{g\in\mathcal H}r_g\cdot(\mathcal U-\lim g)+\sum_{\mu<\lambda}s_\mu\cdot(\mathcal U-\lim\chi_{\vec\mu})=\sum_{g\in\mathcal H}r_g\cdot\chi_{\xi_g}+\sum_{\mu<\lambda}s_\mu\cdot\chi_\mu$ and $f$ has a $\mathcal U$-limit.

Finally, there are no non-trivial convergent sequences since for each $h\in G^\omega$ one-to-one, $\Phi\circ h$ does not converge, which means that in the induced topology on $G$, $h$ does not converge.
\end{proof}

\section{Questions}

The recent breakthrough by Hru\v s\' ak, Ramos, Shelah and van Mill (\cite{hrusakvanmillgarciashelah2020}) obtained a countably compact group without non-trivial convergent sequences in ZFC. Their construction is over a $\mathfrak c$-sized group of order 2. Shortly after Tomita and Trianon-Fraga (\cite{tomita&trianonfraga2022}) expanded this construction to obtain a countably compact group without non-trivial convergent sequences which has cardinality $2^\mathfrak c$ and order 2. It is noteworthy that these constructions did not yield so far a $\mathcal U$-compact group for any ultrafilter $\mathcal U$ and do not seem to be suitable for non-torsion groups. (We recall that such results also imply the existence of a countably compact group whose square is not countably compact; therefore, not all countably compact groups are $\mathcal U$-compact for some $\mathcal U$).

As such, the following questions remain open:

\begin{question}
Is there a countably compact non-torsion group without non-trivial convergent sequences in ZFC?
\end{question}

\begin{question}
How large can countably compact groups without non-trivial convergent sequences be in ZFC?
\end{question}

\begin{question}
Is there a $\mathcal U$-compact group without non-trivial convergent sequences in ZFC, for some ultrafilter $\mathcal U$?
\end{question}

It should be noted that a positive answer to the first question implies the negation of Wallace's conjecture, that is, it implies the existence of a countably compact semigroup with both-sided cancellation which is not a group.


\section*{Supplemental Material for \\ ``Crosslinker mobility governs fracture behavior of catch-bonded networks''}
\setcounter{equation}{0}
\setcounter{figure}{0}
\setcounter{table}{0}
\setcounter{section}{0}

\renewcommand\thefigure{S\arabic{figure}}
\noindent

\section{Simulation Methods}
\subsection{Network model}
We perform simulations of 2D triangular networks of $L\times L$ nodes interconnected by one-dimensional Hookean springs with stretching modulus $\mu$ and rest length $l_{0}$. Thus, the Hamiltonian $\mathcal{H}$ of the system is

\begin{equation}
\mathcal{H}=\frac{\mu}{2l_{0}}\sum_{\left\langle ij\right\rangle}\left(l_{ij}-l_{0}\right)^{2}
\end{equation}

\noindent where the sum is taken over all bonds $\left\langle ij\right\rangle$ with $l_{ij}$ the bond length. All bonds are harmonic springs with unit stiffness and unit rest length (so $\mu=1$ and $l_0=1$). We use periodic boundary conditions in the $x$-direction, while nodes on the top and bottom boundaries are fixed. After each deformation step or binding/unbinding event, the energy of the system is minimized by adjusting the positions of the nodes, using the FIRE algorithm~\cite{bitzek2006structural}. The maximum tolerance $F_{RMS}$ corresponds to the system root-mean-square force and it is set to be $10^{-5}$. Since we only consider potential energy, our system is under athermal conditions. Node pairs that have no bond connected do not interact at all. Uniaxial deformation of the network in the $y$-direction leads to a macroscopic  stress in the network $\sigma$. The stress is computed by the virial stress tensor defined as

\begin{equation}
    \sigma_{\alpha\beta}=\frac{1}{A}\sum_{\left\langle ij \right\rangle}f_{ij,\alpha}r_{ij,\beta}\,,
\end{equation}

\noindent where $\alpha$ and $\beta$ are the Cartesian axes. The  sum runs over all the bonded pairs of nodes $\left\langle ij\right\rangle$, $f_{ij,\alpha}$ is the force acting on the node $i$ due to $j$ in the $\alpha-$direction, $r_{ij,\beta}$ is the distance between the two nodes in the $\beta-$direction, and $A$ is the instantaneous area. We evaluate the $\sigma_{yy}$ tensor component. In our simulations,  we maintain a constant uniaxial stress $\sigma=\sigma_{yy}$ by adjusting the strain.

All quantities are expressed in reduced units, i.e. length scales are expressed in terms of $l_0$, forces in terms of $\mu$, and stresses in terms of $\mu/l_0^2$. Time is expressed in units of the rebinding time $1/k_0^b$ (which is the same for slip and catch bonds, see below).

\subsection{Unbinding and binding bonds}

Structural changes in the network due to binding and unbinding events are simulated by using a kinetic Monte Carlo scheme due to Gillespie~\cite{gillespie1976general}. At every step, we make a list of all possible unbinding and binding events. Based on the list we calculate the total reaction propensity $K_{tot}=\sum_{i}k_{i}$, where $k_{i}$ is the transition rate of a spring corresponding to an unbinding or binding event, as defined below. Which event is the next reaction to occur is drawn randomly, witch each event weighed with its actual reaction rate. The time interval to the next event is drawn also randomly, assuming exponentially distributed events, i.e. $\Delta\tilde{t}=-\textrm{ln}\left(\textrm{rand}\left(0,1\right) \right)/K_{tot}$, with the dimensionless time then given by $t=\tilde{t} k_{0}^{b}$.

All bonds in our networks are transient, reversible bonds with kinetics of binding and unbinding  that depend on the force acting on the bond, $f = \mu\left(l_{ij}-l_{0}\right)/l_{0}$. For the slip bonds, we assume an unbinding rate that decreases exponentially with the force, as predicted by the Bell model~\cite{bell1978models} :

\begin{equation}
k_{u}^{s}\left(f\right)=k_{0}^{s}\exp\left[\frac{f}{f_{e}^{s}}\right]\,,
\end{equation}

\noindent where $k_{0}^{s}$ is the unforced unbinding rate, and $f_{e}^{s}$ is the force where the off rate has fallen with a factor $1/e$. This is related to the activation length $\delta$ of the bond, as $f_{e}^{s}=k_BT/\delta^s$.
By contrast,  catch bond behavior is described by the two path-way model as~\cite{pereverzev2005two}

\begin{equation}
k_{u}^{c}\left(f\right)=k_{0,1}^{s}\exp\left[\frac{f}{f_{e,1}^{s}}\right]+k_{0,2}^{c}\exp\left[-\frac{f}{f_{e,2}^{c}}\right]\,.
\end{equation}

\noindent The first term, characterized by $k_{0,1}^{s}$ and $f_{e,1}^{s}$, captures the dissociation along a slip-like path at large pulling force $f$, while the second term, characterized by $k_{0,2}^{c}$ and $f_{e,2}^{c}$ describes dissociation along a catch-path decreasing the unbinding rate (and thus, increasing the lifetime) with force for small forces $f$. To mimic catch-bond behavior, it is necessary that $k_{0,1}^{c} > k_{0,2}^{c}$ and $f_{e,1}^{c} < f_{e,2}^{c}$~\cite{pereverzev2005two,van2020chemical}. In Fig. 1(a) in the main text, we show the bond lifetime $t_{u}=1/k_{u}$ as a function of $f$ for both slip and catch bonds. In particular, we decide to fix $\left[k_{0}^{s}, f_{e}^{s}\right] = \left[0.025, 0.6\right]$ for slip bonds, and $\left[k_{0,1}^{s}, f_{e,1}^{s}\right] = \left[0.005,0.6\right]$ and $\left[k_{0,2}^{c}, f_{e,2}^{c}\right] = \left[0.25,0.3\right]$ for catch bonds. Finally, we consider that the binding rate is also load-dependent and the same for both types of bonds, being expressed as:

\begin{equation}
k_{b}\left(f\right)=k_{0}^{b}exp\left[-\frac{f}{f_{e}^{b}}\right]\,.
\end{equation}

\noindent Thus, we assume that the binding rate between a pair $ij$ becomes smaller with increasing distance between the two nodes. Fig. 1(a) in the main text shows the binding lifetime $t_{b}=1/k_{b}$ for the set of values $\left[k_{0}^{b}, f_{e}^{b}\right] = \left[1,0.6\right]$.

\subsection{Immobile and mobile bonds}

Immobile bonds rebind between the same pair of nodes from which they are unbound, providing memory to the system of its initial structure. By contrast, mobile bonds can form in random new locations, involving thus any two nodes. To allow bonds to redistribute, we allow a new bond to form between a pair of nodes that is already linked by one bond, so that double bonds can form.  This implies that, while for immobile bonds the maximum local connectivity is $z^{\left(i \right)}_{max}=6$, for mobile bonds  this is $z^{\left(m \right)}_{max}=2z^{\left(i \right)}_{max}$. In all our simulations, we impose a maximum number of bonds that can be formed $N$, which is  equal to the number of bonds that is present in a network where every pair of neighbouring bonds is connected with exactly one bond. This means that new bonds can only form if there are unbound linkers available.

\newpage

\section{Additional results}

\subsection{Effective viscosity}

Fig.~\ref{fig:Viscosity} shows the effective elongational viscosity computed as $\eta=\sigma/\dot{\epsilon}$ for networks with slip and catch bonds. For networks with slip bonds, Fig.~\ref{fig:Viscosity}(a), we observe that $\eta$
decreases with increasing stress, indicating strain thinning. For immobile bonds $\eta$ is larger than for mobile bonds, which is in line with our finding that the network lifetime is larger for immobile bonds. In particular, for immobile bonds we observe that the viscosity diverges for low stress, which corresponds to the metastable regime.

By contrast, networks with catch bonds manifest strain thickening, Fig.~\ref{fig:Viscosity}(b). Furthermore, unlike what happens for slips bonds, $\eta$ is considerably larger when catch bonds are mobile. This opposite behavior between bonds as a function of mobility strongly suggests that mobility is needed to take advantage of the nature of catch bonds.

\begin{figure*}[!h]
\includegraphics[width=0.7\linewidth]{FigS1.pdf}
\caption{Effective viscosity $\eta=\sigma/\dot{\epsilon}$, for networks with (a) slip bonds and (b) catch bonds as a function of the stress $\sigma$ and the mobility. \textit{Inset}: Zoom on the viscosity for mobile slip bonds.}
\label{fig:Viscosity}
\end{figure*}

\subsection{Catch bond behaviour on the network}

\begin{figure*}[!h]
\includegraphics[width=0.45\linewidth]{FigS2.pdf}
\caption{Lifetime of a network with irreversible catch bonds  as a function of $\sigma$. Here, the rebinding rate $k_{b}$ is assumed to be zero.}
\label{fig:FigS1}
\end{figure*}

The lifetime of a network with catch bonds without rebinding transitions, i.e. $k_{b}=0$, is shown as a function of stress in Fig.~\ref{fig:FigS1}. We observe how a peak in $\tau_f$ develops at $\sigma\approx0.5$. The presence of this peak resembles the characteristic peak of an individual catch bond. However, it is less pronounced, probably because the stress distribution in the network is heterogeneous. Since  rebinding events promote bond formation at low stress, the echo from the catch bond behavior is shielded in transient networks with reversible bonds.

\subsection{Evolution of the total number of mobile bonds }

As mentioned in the main text, the total number of bonds $n_{b,1}+n_{b,2}$ for both mobile slip and catch bonds remains more or less constant, except close to the moment of fracture, when the network is destabilized and no more bonds can be bound close the cracks to postpone their propagation.

\begin{figure}[!h]
\includegraphics[width=0.9\linewidth]{FigS3.pdf}
\caption{Evolution of the total number of bonds, $n_{b,1}+n_{b,2}$ for (a) mobile slip bonds and (b) mobile catch bonds.}
\label{fig:nb1nb2}
\end{figure}

\subsection{Fraction of final bonds}
In Fig.~\ref{fig:Fractionfinal}(a) we report the fraction of bonds at the moment of fracture, $n_{f}=N_{f}/N$ as a function of stress for immobile bond networks. In particular, for slip bonds, we see a minimum at $\sigma\approx0.5$, i.e. close to the metastability. The presence of this minimum hints at a change in fracture scenario, from  fracture at subcritical stress at low $\sigma$, to fracture dominated by gradual degradation of the network at high $\sigma$. This minimum is shifted to $\sigma\approx0.22$ for immobile catch bonds, leading to a  metatable state at lower stress, and $n_{f}$ is a monotonic function of $\sigma$, indicating that the fracture becomes more brittle as the stress increases. We note furthermore that the fraction of bonds remaining in the network is much smaller for catch than for slip bonds, indicating much more diffuse damage in the case of catch bonds.

Fig.~\ref{fig:Fractionfinal}(b) shows the fraction of single $n_{f,1}$ and double $n_{f,2}$ bonds for networks with mobile slip and catch bonds. We observe that for intermediate stresses, $n_{f,2}$ is higher for catch bonds, indicating that the redistribution of bonds by the accumulation of double bonds proceeds more efficiently for catch bonds. This is caused by the fact that catch bond networks are stabilized by relocalizing bonds, while slip bond networks are destabilized,

\begin{figure}[!h]
\includegraphics[width=\linewidth]{FigS4.pdf}
\caption{(a) Fraction of the number of bonds at the moment of fracture, $n_{f}=N_{b}\left(t_{f}\right)/N$, for immobile slip and immobile catch bonds as a function of $\sigma$. The vertical dashed line indicates the onset of the metastability. (b) Fraction of final single $n_{f,1}$ and double $n_{f,2}$ bonds for networks with mobile slip and mobile catch bonds.}
\label{fig:Fractionfinal}
\end{figure}

\subsection{Unbinding and binding probability distribution}
We record the bond length associated to each binding/unbinding event during the simulation, and build the probability distribution that a bond will unbind $P_{u}$ or bind $P_{b}$ with length $l$. This information is shown in Fig.~\ref{fig:Prob} for the four different types of networks we have simulated here, for different $\sigma$. While the mobility of bonds strongly influences the probability distributions for slip bonds, for catch bonds they are quite similar. Indeed, we observe that both $P_{b}$ and $P_{u}$ for immobile slip bonds develop a double peak; the first placed at the bond rest length, whereas the second one shifts to higher bond length with $\sigma$. Because immobility limits the places where bonds can be formed, it is expected that slip bonds are forced to bind with $l_{ij}\gg l_{0}$. However, these strongly stretched bonds will also break rapidly due to their slip behaviour. When slip bonds are mobile, the second peak in $P_{b}$ disappears, and the distribution develops a long tail. Now, slip bonds can form wherever they want, and, since their lifetime is maximum at $l_{ij}\rightarrow l_{0}$ they will preferentially want to accumulate  in regions with lower local stress, as we have also observed in Fig. 3(e) in the main text where the distribution of double bonds around cracks is discussed. This has a direct impact on $P_{u}$, where the second peak at large bond length is reduced. As we have indicated above, the binding probability distribution for immobile and mobile catch bonds are similar.
The unbinding probabilities at higher force are much smaller for catch bonds than for slip bonds, clearly showing that catch bonds are stabilized in high stress regions.

\begin{figure*}[!h]
\includegraphics[width=0.9\linewidth]{FigS5.pdf}
\caption{Unbinding $P_{u}\left(l\right)$ and binding $P_{b}\left(l\right)$ probability distributions for different stress values $\sigma$. (a) Immobile slip bonds, (b) immobile catch bonds, (c) mobile slip bonds, and (d) mobile catch bonds.}
\label{fig:Prob}
\end{figure*}

\newpage

\subsection{Crack identification}

To identify crack and study crack propagation, we define on the undeformed network, i.e. the fully connected triangular lattice, centroid points of each triangular cell as shown in Fig.~\ref{fig:CrackId}(a). Unbinding and binding events are mapped on the undeformed network, schematically shown in Fig.~\ref{fig:CrackId}(b). Then, two centroid points are linked defining a crack when, during the deformation, the bond that splits them is broken (see Fig.~\ref{fig:CrackId}(c)). Furthermore, we define the crack surface as the lattice nodes or bonds around each crack, as we represent in Fig.~\ref{fig:CrackId}(d). Thus, we compute the crack size distribution $n_{c}$, which we discuss in the main text, as well as the crack surface size distribution $n_{s}$ shown  in Fig.~\ref{fig:SurfaceCrack}(a), exhibiting both the same trend. We also compute the distribution of double bonds around the cracks $P(N_{b,2})$ for different $\sigma$, represented in Fig. 3(e) in the main text.

\begin{figure}[!h]
\includegraphics[width=0.8\linewidth]{FigS6.pdf}
\caption{Sketch representing the crack identification procedure. (a) Undeformed triangular network, where centroid points of the triangles are represented. (b) Broken bonds are mapped on the undeformed network. (c) Once broken bonds are localized, centroid points are linked, defining a crack. (d) Surface nodes and surface bonds are highlighted around the crack defined on the undeformed network.}
\label{fig:CrackId}
\end{figure}

\subsection{Network evolution}
\subsubsection{Surface size distribution}
The crack surface area  distribution $P\left(s\right)$, shown in Fig.~\ref{fig:SurfaceCrack}(a) exhibits the same behaviour as the the crack size distribution represented in Fig. 3 in the main text. Indeed, $P\left(s\right)$ shows a power-law dependence at large crack sizes with an exponent $\alpha\approx-2.2$ just before the network fractures for networks with immobile slip, immobile catch and mobile catch bonds. This value is consistent with the random percolation value~\cite{torquato2002random,sciortino2005one}. In addition, both $P\left(c\right)$ and $P\left(s\right)$ evolve in the same way as a function of $t$.

\begin{figure}[!h]
\includegraphics[width=\linewidth]{FigS7.pdf}
\caption{Evolution of the surface size distribution $P\left(s\right)$ as a function of the network structure at stress $\sigma=0.36$. In each panel, the full line represents the function $P\left(s\right)\propto s^{-2.2}$. Here, $P\left(s\right)$ is represented at different $t$ in log scale. Only the distributions at early stage ($\left< t\right> \sim t_{ini}$) and close to fracture ($\left< t \right> \sim t_{f}$) are indicated by symbols, to highlight the structural changes.}
\label{fig:SurfaceCrack}
\end{figure}

\subsubsection{Network evolution at low stress}

In Fig.~\ref{fig:Cluster010} we show $P_{c}$ at $\sigma=0.10$ for networks with immobile slip bonds, immobile catch bonds and mobile catch bonds (note that networks with immobile slip bonds do not break at this stress). The distributions look similar to those at higher stress in Fig. 3 in the main text, albeit it that the distributions for catch bonds are even wider at this lower stress.

\begin{figure}[!h]
\includegraphics[width=0.8\linewidth]{FigS8.pdf}
\caption{Evolution of the crack size distribution $P\left(c\right)$ as a function of the network structure at stress $\sigma=0.10$, for immobile catch bonds, mobile slip bonds, and mobile catch bonds. In each panel, the full line represents the function $P\left(c\right)\propto c^{-2.2}$. Here, $P\left(c\right)$ is represented at different $t$ in log scale, although only at early stage ($\left< t\right> \sim t_{ini}$) and close to fracture ($\left< t \right> \sim t_{f}$) are indicated by symbols to highlight the structural changes.}
\label{fig:Cluster010}
\end{figure}

\subsubsection{Double bond distribution}

In Fig.~\ref{fig:DoubleBondsStress} we show the distribution of double bonds $P\left(N_{b,2}\right)$ computed on the crack surface for different $\sigma$ for networks with mobile slip and mobile catch bonds. In particular, for mobile slip bonds we can see that the distribution decays faster by increasing $\sigma$, revealing that bonds are less stable due to the high local stress on the crack surface. By contrast, the effect of stress on $P\left(N_{b,2}\right)$ is smaller for networks with catch bonds. We fit the tail of these distributions by considering $P\left(N_{b,2}\right)\propto N_{b,2}^{-\alpha}$. Te inset of Fig.~\ref{fig:DoubleBondsStress} clearly shows that the accumulation of catch bonds is more pronounced than for slip bonds. Thus, crack propagation is hindered more efficiently, postponing the fracture because there is an accumulation of bonds around the cracks.

\begin{figure}[!h]
\includegraphics[width=0.8\linewidth]{FigS9.pdf}
\caption{Distribution of double bonds $P\left(N_{b,2}\right)$ computed on the crack surface as a function of $\sigma$ close to the moment of fracture $t_{f}$, for networks with mobile slip bonds (blue) and mobile catch bonds (red). The right arrow highlights the stress direction. {\it Inset:} Exponent corresponding to the fitting $P\left(N_{b,2}\right)\propto N_{b,2}^{-\alpha}$ made to the tail of the distribution.}
\label{fig:DoubleBondsStress}
\end{figure}

\newpage

\subsubsection{Damage visualization}

The evolution discussed by computing $P\left(c\right)$ at $\sigma=0.40$ is represented by snapshots taken at different times for networks with immobile bonds in Fig.~\ref{fig:Evol_imm} and for networks with mobile bonds in Fig.~\ref{fig:Evol_mob}, where single bonds are shown in orange, and double slip and catch bonds are shown in blue and purple, respectively. Likewise, we also visualize the damage propagation on the network once the fracture has taken place, i.e. $t=t_{f}$.

\begin{figure*}[!h]
\includegraphics[width=0.8\linewidth]{FigS10.pdf}
\caption{Network evolution as a function of time $t$ with immobile bonds, for $\sigma=0.40$.}
\label{fig:Evol_imm}
\end{figure*}

\begin{figure*}[!h]
\includegraphics[width=0.8\linewidth]{FigS11.pdf}
\caption{Network evolution as a function of time $t$ with mobile bonds, for $\sigma=0.40$. Orange indicates single bonds, whereas blue and purple indicate double slip and catch bonds, respectively.}
\label{fig:Evol_mob}
\end{figure*}

\begin{figure*}[!h]
\includegraphics[width=\linewidth]{FigS12.pdf}
\caption{Visualization of the damage once the fracture has taken place, i.e. $t=t_{f}$, mapped on the undeformed network at $\sigma=0.10$ (top) and $\sigma=0.40$ (bottom). Here, broken bonds belonging to the percolated crack are highlighted in red color, whereas blue color indicates individual broken bonds. Note that the network with immobile slip bonds does not fracture for $\sigma=0.10$.}
\label{fig:Evol_imm2}
\end{figure*}

\clearpage
\bibliographystyle{unsrt}


\section{Beyond Optimality}\label{sec:beyond}

The algorithm presented in Sec.~\ref{sec:optimal} yields optimal linear contraction orders for tree tensor networks. In contrast, optimal \textit{general} contraction ordering for tree tensor networks is still open. This is also true for join ordering, where finding the optimal bushy plan (the equivalent of general order) for tree queries is also still open. Even so, we can obtain near-optimal orders, as shown in~\cite{adaptive}, where the key idea is to use the linear solutions as a starting point for the cubic DP. The main motivation is shown in the same work: If we obtain the linearization that gives the best general contraction order, then the cubic DP will find the optimal solution. This is also the insight discovered later in~\cite{cubic_dp_in_tensor} in the context of tensor networks. The main advantage of this approach is that, although we cannot find the optimal \textit{general} contraction order, we are at least optimal in the regime of \textit{linear} contraction orders. Therefore, we can ensure the robustness of the generated contraction orders.

Additionally, we can extend the idea to arbitrary tensor networks by applying the heuristic presented in~\cite{ik}: Since the IKKBZ algorithm requires tree-shaped graphs, we can first find a suitable spanning tree according to a greedy strategy and finally use it as input to IKKBZ. The heuristic selects the minimum spanning tree since the join result has size $s_{i,j}|R_i||R_j|$, where $|R_i|$ and $|R_j|$ are the relations to be joined and $s_{i,j}$ is the join \textit{selectivity}. Hence, the goal is to minimize the output size. For the context of tensor networks, we propose the use of the \textit{maximum} spanning tree, since we can rewrite the contraction cost of two tensors $T_1 \in \mathbb{C}^{p_1\times \ldots \times p_a \times q_1 \times \ldots \times q_b}$ and $T_2 \in \mathbb{C}^{q_1 \ldots \times q_b \times r_1 \times \ldots \times r_c}$ as $ \frac{|T_1||T_2|}{\prod_{i=1}^{b} q_i}$, which allows us to interpret the product of the common legs as the inverse of the selectivity.
\section{Conclusion}\label{sec:conclusion}

Contraction orders play a fundamental role in efficient simulations of quantum many-body systems and quantum circuits. Since the problem of finding optimal contraction orders for arbitrary tensor networks is NP-complete, previous research has focused on finding heuristic algorithms that are experimentally shown to output good orders. In this work, we have taken a more conservative approach and shown that tree tensor networks accept optimal linear contraction orders. The key idea comes from a decades-old algorithm from database join ordering. We also propose two other heuristics for near-optimal contraction orders by taking advantage of advanced research in join ordering~\cite{adaptive} and adapting them to the setting of tensor networks. In this way, we bring together two separate lines of research, both of which have an open problem: Can we find optimal \textit{general} contraction orders for tree tensor networks?
\section{Results}\label{sec:results}

In this section, we highlight the advantage of the polynomial-time algorithm compared to a standard dynamic programming algorithm for tree tensor networks that outputs the optimal linear contraction order. In the following, we will refer to the IKKBZ adapted for tensor networks as IKS.

\begin{figure}
\centering\includegraphics[width=7.5cm,height=7.5cm,keepaspectratio]{photo/output-16.png}
\caption{Polynomial-time advantage over exponential-time DP for small-sized tensor networks.}
\label{fig:plot1}
\end{figure}

\begin{figure}
\centering\includegraphics[width=7.5cm,height=7.5cm,keepaspectratio]{photo/output-64.png}
\caption{Polynomial-time advantage over exponential-time DP for larger tree tensor networks. We set a timeout of 10 seconds for each algorithm.}
\label{fig:plot2}
\end{figure}

To this end, we generate tree tensor networks of size 5 up to 64, each with 100 instances, as presented in~\cite{adaptive}. We run DP and IKS for each size and report the average execution time. Since DP inherently takes exponential time, we set a timeout of 10 seconds. To show the benefits of the polynomial-time algorithm, we first plot the results for small tree-tensor networks in Fig.~\ref{fig:plot1} and then for larger tree-tensor networks in Fig.~\ref{fig:plot2}, where DP fails after a certain size due to the exponential nature of the problem.
\section{Introduction}\label{sec:introduction}
In this work, we consider tensors to be multi-dimensional arrays and define them as $T \in \mathbb{C}^{n_1 \times \ldots \times n_k}$. Tensor networks can be intuitively understood from the example of matrix multiplication: Consider two matrices $A\in\mathbb{C}^{p \times q}$ and $B\in\mathbb{C}^{q \times r}$, the product of which is defined as $C_{ij} = (AB)_{ij} = \sum_{k}A_{ik}B_{kj}$, where $C \in \mathbb{C}^{p \times r}$. Thus, there is a common index over which we perform the multiplication. In tensor notation, this represents the \textit{contraction} over their common leg (dimension) and can be represented in a graphical notation as in Fig.~\ref{fig:example}.

\input{figures/example.tex}

For two tensors $T_1 \in \mathbb{C}^{p_1 \times \ldots \times p_a \times q_1 \times \ldots \times q_b}$ and $T_2 \in \mathbb{C}^{q_1 \times \ldots \times q_b \times r_1 \times \ldots \times r_c}$, the result of the contraction is a tensor $T_{1,2}\in \mathbb{C}^{p_1 \times \ldots \times p_a \times r_1 \times \ldots \times r_c}$, i.e., the common legs, $q_i$, disappear, while the others, $p_i$ and $r_i$, respectively, remain.

To systematically represent contractions of a set of tensors, i.e., a tensor network, we define $G := (V, E, f)$ to be an undirected weighted graph, where $V$ is the set of tensors and $E$ the edge set, where $\{T_u, T_v\} \in E$ means that tensors $T_u$ and $T_v$ need to be contracted over the common leg of size $f({T_u, T_v})$. For simplicity, we only consider tensor networks whose output is a scalar. The proposed algorithms are not affected by this assumption, rather it saves us from additional notations.

To see why contraction order matters, consider the multiplication of three matrices $A\in\mathbb{C}^{20\times 30}$, $B\in\mathbb{C}^{30\times 10}$, and $C\in\mathbb{C}^{10 \times 50}$. There are two ways they can be multiplied: $(i)$ $(AB)C$ and $(ii)$ $A(BC)$. The cost of a matrix multiplication is defined as the number of scalar multiplications performed. For two arbitrary matrices $M_1\in\mathbb{C}^{p \times q}$ and $M_2\in\mathbb{C}^{q\times r}$ this is equal to $pqr$. Thus, variant $(i)$ incurs a cost of $20 \cdot 30 \cdot 10 + 20 \cdot 10 \cdot 50 = 16000$, while variant $(ii)$ incurs a cost of $30 \cdot 10 \cdot 50 + 20 \cdot 30 \cdot 50 = 45000$. We conclude that $(AB)C$ is the order to be preferred. In the same way, this can be generalized to tensor networks, where the cost of contracting tensors $T_1 \in \mathbb{C}^{p_1\times \ldots \times p_a \times q_1 \times \ldots \times q_b}$ and $T_2 \in \mathbb{C}^{q_1 \times \ldots \times q_b \times r_1 \times \ldots \times r_c}$ is equal to $p_1 \cdot \ldots \cdot p_a \cdot q_1 \cdot \ldots \cdot q_b \cdot r_1 \cdot \ldots \cdot r_c$. Hence, our goal is to find the \textit{optimal} contraction order, i.e., the one which minimizes the total cost.

We additionally differentiate between \textit{linear} contraction orders and \textit{general} ones, as established in~\cite{contraction_trees}. A linear contraction order contracts tensors one by one (think of a multiplication chain), while a generalized contraction order does not have any such restrictions. In the case of matrix multiplication of four matrices $A, B, C$, and $D$, an example of a linear contraction order is $(((AB)C)D)$, while an example of a general one is $(AB)(CD)$.
\newpage
The main drawback is that the problem of finding optimal contraction orders, either general or linear, for arbitrary tensor networks is NP-complete~\cite{Lam1997OnOA}. This means that we cannot ensure optimal orders for large tensors networks. For this reason, there exists a number of heuristics which promise good contraction orders.

We argue that this is a defeatist position and show that we can indeed find optimal contraction orders for a more restrictive class of tensor networks. We take a step back from employing heuristics and ask ourselves the following question: For which class of tensor networks and for what kind of contraction orders, i.e., linear or general, can we ensure optimality? A simple answer is to consider chain tensor networks, where a general contraction order can be found in polynomial time using the same cubic dynamic programming (DP) as for the matrix chain ordering problem. The answer we give in this work considers a broader class, namely \textit{tree} tensor networks, for which we show that we can guarantee optimal \textit{linear} contraction orders.

Beyond the optimality results, we highlight two join ordering techniques that can build on our work to guarantee near-optimal orderings for arbitrary tensor networks.

The rest of the paper is organized as follows: Section~\ref{sec:related} summarizes related work, both in tensor networks and database join ordering. In section~\ref{sec:optimal} we outline the algorithm for optimal linear contraction orders for tree tensor networks. In section~\ref{sec:beyond}, inspired from recent research on join ordering~\cite{adaptive}, we discuss algorithms for near-optimal contraction orders on arbitrary tensor networks. We summarize the results in section~\ref{sec:results}. Finally, we draw conclusions and discuss future work.
\section{Motivation}\label{sec:motivation}
Let us first motivate why we need tensor networks. They are approximations of high-order tensors, hence easier to handle. For this reason, they have recently found application in physics~\cite{Schollw_ck_2005}, quantum chemistry~\cite{Nakatani_2013}, and machine learning~\cite{ml_tensor}. In particular, for quantum simulations, tensor networks can effortlessly simulate a quantum circuit classically, i.e., without quantum computation. This is indeed promising since we are still in the NISQ era~\cite{Preskill_2018}, where a large number of qubits represents a challenge.

However, while the contraction operation itself is trivial, its execution time depends heavily on the order in which the contractions are executed. In the following sections, we introduce the concepts and formulate the problem.
\section{Optimal Contraction Orders}\label{sec:optimal}

As stated in the previous sections, we can indeed provide optimal \textit{linear} contraction orders for \textit{tree} tensor networks. This relies on the IKKBZ algorithm~\cite{ik,kbz} which itself builds upon the solution to a well-known job ordering problem~\cite{Monma1979SequencingWS}.

Let $T_{a,b} := T_aT_b$ denote the contraction of two tensors $T_a$ and $T_b$ and $c(T_aT_b)$ their contraction cost, as presented in Sec.~\ref{sec:introduction}. Further, we do not consider outer products, i.e., contracting tensors which do not share a common leg. In join ordering, these are called cross products, and the original IKKBZ algorithm cannot guarantee optimality in their presence.

The problem statement of optimal linear contraction ordering can then be stated as finding the permutation $\pi$ of tensors which minimizes the contraction cost, i.e.,

\begin{equation}
\argmin_{\pi} \Gamma(\pi) = \sum_{i=2}^{N} c(T_{\pi_1,\ldots,\pi_{i-1}}T_{\pi_i}).
\label{eqn:cost}
\end{equation}

Furthermore, as we deal with \textit{tree-shaped} tensor networks, it can be rewritten as

\begin{equation}
\argmin_{\pi} \Gamma(\pi) = \sum_{i=2}^{N} \frac{|T_{\pi_1,\ldots,\pi_{i-1}}|| T_{\pi_i}|}{|e_{T_{\pi_j}, T_{\pi_i}}|},
\label{eqn:reformulated_cost}
\end{equation}

where $e_{T_{\pi_j}, T_{\pi_i}}$ is the \textit{unique} edge connecting $T_{\pi_i}$ to the already contracted tensor network $T_{\pi_1,\ldots,\pi_{j},\ldots,\pi_{i-1}}$. This uniqueness is implied by the fact that outer products are not allowed. We can ensure this constraint by introducing a partial order on the tensors, represented by a precedence graph:

\subsection{Precedence Graph}\label{sec:prec_graph}

One of the prerequisites for the optimality of the algorithm is the tree shape of the network. To achieve optimality, the algorithm roots the network in each tensor, solves the ordering problem for the obtained rooted tree, and picks the solution which leads to the minimum cost. The rooted tree is referred to as the precedence graph and describes the partial order of the contractions. An example for a precedence graph of a tree tensor network can be seen in Fig.~\ref{fig:precedence_graph}. In that example, the precedence graph specifies $T_4 \rightarrow T_3$ and $T_4 \rightarrow T_2$, i.e., $T_4$ should occur in the order \textit{before} $T_3$ and $T_2$, respectively.
\input{figures/precedence.tex}
\subsection{Rank Function}\label{subsec:rank}

The key idea behind the algorithm is that it allows global improvement based on local decisions. While this is not a novel idea in algorithmic design (see Kruskal's algorithm for the the minimum spanning tree~\cite{kruskal}), it is a powerful one. In our case, this is achieved through a $rank$ function. To illustrate the idea, let us consider the precedence graph depicted in Fig.~\ref{fig:example}, where $T_1\in\mathbb{C}^{p \times q}, T_2\in\mathbb{C}^{q \times r}, T_3\in\mathbb{C}^{r}$, and $T_4\in\mathbb{C}^{q}$.

\begin{figure}
\centering
\begin{tikzpicture}
\begin{scope}[auto, node distance=0.25cm,
   node_style/.style={align=center, circle,draw,inner sep=0pt, text centered,minimum size=0.5cm,
    font=\sffamily},
   edge_style/.style={draw=black}]

    \node[node_style,label={[xshift=0em, yshift=0.5em,font=\footnotesize,teal]}] (v1) at (1,5) {$T_1$};
    \node[node_style,label={[xshift=0em, yshift=0.5em,font=\footnotesize,teal]}] (v2) at (0.5,4.33) {$T_2$};
    \node[node_style,label={[xshift=0em, yshift=0.5em,font=\footnotesize,teal]}] (v3) at (1.5,4.33) {$T_3$};
    \node[node_style,label={[xshift=0em, yshift=-3.5em,font=\footnotesize,teal]}] (v4) at (0.5,3.5) {$T_4$};
    \draw[edge_style]  (v1) edge node{$p$} (v2);
    \draw[edge_style]  (v2) edge node{$q$} (v4);
    \draw[edge_style]  (v1) edge node{$r$} (v3);
    \end{scope}
\end{tikzpicture}
\caption[Rank Function]{Precedence graph of $T_1$, where $T_1\in\mathbb{C}^{p \times q}, T_2\in\mathbb{C}^{q \times r}, T_3\in\mathbb{C}^{r}$, and $T_4\in\mathbb{C}^{q}$}
\label{fig:example}
\end{figure}

Assume that we want to find out whether it is more advantageous to perform $(i)$ $T_1\begingroup\color{purple}T_2\endgroup \begingroup\color{cyan}T_4\endgroup T_3$ or $(ii)$ $T_1
 \begingroup\color{cyan}T_4\endgroup \begingroup\color{purple}T_2\endgroup T_3$, i.e., which tensor between $\begingroup\color{purple}T_2\endgroup$ and $\begingroup\color{cyan}T_4\endgroup$ to contract first. Let us calculate the cost of each order:

\begin{enumerate}[$(i)$]
    \item $c(T_1T_{\begingroup\color{purple}2\endgroup})=pqr$, $c(T_{1,\begingroup\color{purple}2\endgroup}T_{\begingroup\color{cyan}4\endgroup})=qr$, and $c(T_{1,\begingroup\color{purple}2\endgroup,\begingroup\color{cyan}4\endgroup}T_3)=r$, yielding a total cost of $pqr + qr + r$,
    \item $c(T_1T_{\begingroup\color{cyan}4\endgroup})=pq$, $c(T_{1,{\begingroup\color{cyan}4\endgroup}}T_{\begingroup\color{purple}2\endgroup})=pr$, and $c(T_{1,{\begingroup\color{cyan}4\endgroup},{\begingroup\color{purple}2\endgroup}}T_3)=r$, yielding a total cost of $pq + pr + r$.
\end{enumerate}
When comparing both costs, i.e.,
\begin{flalign*}
    &\qquad& pqr + qr + r &\leq pq + pr + r &&\\
    \iff&& pqr + qr &\leq pq + pr &&\\
    \iff&& pq(r - 1) &\leq r(p - q), &&\\

\end{flalign*}
\label{eq:naive} we observe an interesting pattern: the original inequality reduces to a simpler one that considers only the tensors $\begingroup\color{purple}T_2\endgroup$ and $\begingroup\color{cyan}T_4\endgroup$ to be compared. To see this, assume $r > 1$ and $p > q$. Then the inequality is equivalent to $\frac{pq}{p - q} \leq \frac{r}{r - 1}$. Hence, a local decision is enough to decide whether the order $T_1\begingroup\color{purple}T_2\endgroup \begingroup\color{cyan}T_4\endgroup T_3$ is better than $T_1\begingroup\color{cyan}T_4\endgroup \begingroup\color{purple}T_2\endgroup T_3$.

Indeed, this pattern is not arbitrary: it is the core idea behind the Adjacent Sequence Interchange (ASI) property~\cite{Monma1979SequencingWS}, employed by the IKKBZ algorithm:

\begin{definition}[ASI Property]\label{def:asi}
Let $A$ and $B$ be two sequences and $U$ and $V$ two non-empty sequences. We say a cost function $C$ has the adjacent sequence interchange (ASI) property, iff there exists a function $rank$ such that the following holds
\[
C(AUVB) \leq C(AVUB) \iff rank(U) \leq rank(V),
\]
if AUVB and AVUB satisfy the precedence constraints imposed by a given precedence graph.
\end{definition}

Thus, a cost function $C$ with ASI property allows us to use \emph{local} comparisons based on the rank function, i.e., $rank(U) \leq rank(V)$, to infer comparisons between \emph{global} costs, i.e., $C(AUVB) \leq C(AVUB)$. Our algorithm will therefore make extensive use of rank comparisons to find optimal linear contraction orders.

Let $T_S$ be the tensor represented by the sequence $S$, where the leg pointing to the parent is not taken into account. Then, using the reformulation from Eq.~\ref{eqn:reformulated_cost}, we can prove that $\Gamma$, the total contraction cost, has the ASI property:

\begin{lemma}
$\Gamma$ has the ASI property.
\end{lemma}
\begin{proof}
{\small
\begin{align*}
\qquad&\Gamma(AUVB) \leq \Gamma(AVUB) &&\\
\iff& \Gamma(AUV) + \frac{|T_{AUV}|}{|e_{AUV,B}|}\Gamma(B) \leq \Gamma(AVU) + \frac{|T_{AVU}|}{|e_{AVU,B}|}\Gamma(B) &&\\
\iff& \Gamma(AUV) \leq \Gamma(AVU) &&\\
\iff& \Gamma(AU) + \frac{|T_{AU}|}{|e_{AU,V}|}\Gamma(V) \leq \Gamma(AV) + \frac{|T_{AV}|}{|e_{AV,U}|}\Gamma(U) &&\\
\iff& \frac{|T_{A}|}{|e_{A,U}|}\Gamma(U) + \frac{|T_{AU}|}{|e_{AU,V}|}\Gamma(V) \leq \frac{|T_{A}|}{|e_{A,V}|}\Gamma(V) + \frac{|T_{AV}|}{|e_{AV,U}|}\Gamma(U) &&\\
\iff& \frac{\Gamma(U)}{|e_{A,U}|} + \frac{|T_{U}|}{|e_{A\begingroup\color{red}U\endgroup,V}||e_{A,U}|}\Gamma(V) \leq \frac{\Gamma(V)}{|e_{A,V}|} + \frac{|T_{V}|}{|e_{A\begingroup\color{red}V\endgroup,U}||e_{A,V}|}\Gamma(U) &&\\
\iff& \frac{\Gamma(U)}{|e_{A,U}|} + \frac{|T_{U}|}{|e_{A,V}||e_{A,U}|}\Gamma(V) \leq \frac{\Gamma(V)}{|e_{A,V}|} + \frac{|T_{V}|}{|e_{A,U}||e_{A,V}|}\Gamma(U) &&\\
\iff& \frac{\Gamma(U)}{|e_{A,U}|}(1 - \frac{|T_V|}{|e_{A,V}|}) \leq \frac{\Gamma(V)}{|e_{A,V}|}(1 - \frac{|T_{V}|}{|e_{A,U}|}) &&\\
\iff& \Gamma(U)(|e_{A,V}| - |T_V|) \leq \Gamma(V)(|e_{A,U}| - |T_{V}|) &&\\
\end{align*}
}
We can in principle define $rank(S) := \frac{\Gamma(S)}{|e_{S}| - |T_S|}$, but this is not allowed since in case the denominator is negative, the sign of the inequality is reversed. Therefore, we work directly with the fraction representing the $rank$ and let $d_S := \Gamma(S)$ and $n_S := |e_{S}| - |T_S|$ be the denominator and numerator, respectively. We will thus evaluate  $rank(U) \leq rank(V)$ as $d_U \cdot n_V \leq d_V \cdot n_U$ so that we can directly work with the original inequality.
\end{proof}

\subsection{Algorithm}

As mentioned in Sec.~\ref{sec:related}, we adapt the IKKBZ algorithm to the setting of tree tensor networks. This has already been achieved by defining the corresponding $rank$ function. Apart from that, the algorithm remains the same as formulated in~\cite{ik,kbz}. In the following, the algorithm is outlined.

The algorithm treats each tensor $T_i \in V$ separately, by executing two consecutive phases:

\textbf{First Phase:} Build the precedence graph of $T_i$, as described in Sec.~\ref{subsec:rank}.\par

\textbf{Second Phase:} Compute the optimal permutation, which reflects the order in which the tensors should be contracted. The process of transforming the precedence graph into a permutation is called linearization and can be regarded as a recursive method: once the subtrees of the children are linearized, we can obtain the linearization of the whole tree by interleaving (merging) the tensors according to their ranks.

To this end, the notion of contradictory or conflicting sequences comes into play: whenever the precedence graph requires $A \rightarrow B$, but $rank(A) \geq rank(B)$, we combine $A$ and $B$ into a new single node. This node represents a \textit{compound} tensor which includes all tensors in $A$ and $B$. This operation, called normalization, is applied after interleaving the linearizations and preserves the invariant that ranks of a linearization are in \textit{increasing} order (cf. Def.~\ref{def:asi}). Thus, the only contradictory sequences we might obtain are between the root of a subtree and the first (compound) tensors in the result of the merge step. In that case, several normalization steps are applied, until no contradictory sequence is due.

To see why normalization steps are required for optimality, consider the following Lemma:
\begin{lemma}\label{lemma:normalize}
Let $\{A,B\}$ be a compound tensor. If $A \rightarrow B$ and $rank(A) \geq rank(B)$, then we find an optimal sequence in which $B$ directly follows $A$.
\end{lemma}

\begin{proof}
Assume, by contradiction, that $B$ does not directly follow $A$. Since $A \rightarrow B$, any optimal sequence must be of the form $UAVBW$, with $V \neq \epsilon$.

\textit{Case} $rank(A) \geq rank(V)$: We can exchange $V$ and $A$ without increasing the costs.

\textit{Case} $rank(A) \leq rank(V)$: Since $rank(B) \leq rank(A)$, due to transitivity we have $rank(B) \leq rank(V)$. Thus, we can exchange $B$ and $V$ without increasing the costs. \qedhere
\end{proof}

At the end, the reverse operation, called denormalization, is performed on the linearization of the precedence graph, where each compound tensor is replaced by the sequence of tensors it contains. The obtained sequence of tensors represents exactly the optimal permutation for the given precedence graph.\par

Finally, after applying both phases for each tensor, the linearization with the lowest cost is the optimal solution.

As regards time complexity, the algorithm builds the solution in polynomial time. The first phase, in which the precedence graph is constructed, can be completed via Depth First Search (DFS) in linear time, starting from the root and directing the edges towards the unvisited nodes of the tree. In the second phase, while normalization is a cheap operation, requiring only linear time, linearization is the most expensive one. Interleaving $m$ linearizations of size $s$ each requires $\mathcal{O}(ms\log_2(m))$ operations. This can be done with a min-heap data structure of size $m$. The worst-case time complexity of each iteration is $\mathcal{O}(n\log_2(n))$, so $\mathcal{O}(n^2\log_2(n))$ in total, since the algorithm repeats the two phases for each of the $n$ tensors.

Later in~\cite{kbz}, the algorithm was also improved, its time complexity being reduced to $\mathcal{O}(n^2)$, by observing that linearizations of neighboring nodes are similar.

\subsection{Example}

\input{figures/IKKBZ.tex}

A sample algorithm execution can be visualized in Fig.~\ref{fig:iks_exec}. We are considering only the precedence graph of $T_4$, but the algorithm would have to consider all precedence graphs. In the first phase, the algorithm builds the precedence graph of $T_4$, which is equivalent to rooting the network in $T_4$. The subtree of $T_2$ is not yet linearized, thus the algorithm merges $T_1$ and $T_5$, by observing the rank monotonicity, i.e., $\cg{violet}{2}\:\cdot\:\cg{brown}{0} \leq \cg{violet}{1}\:\cdot\:\cg{brown}{2}$. After the merge step, a normalization step is required (step \fbox{\scriptsize 3}), since $T_2 \rightarrow T_1$, but $rank(T_2) \geq rank(T_1)$. The algorithm is then able to linearize $T_4$ and denormalize it (the compound tensor $T_2T_1$ is decomposed into individual tensors, as in step \fbox{\scriptsize 5}). Finally, we can build the linear contraction order from the denormalized linearization.
\section{Related Work}\label{sec:related}

As mentioned in the introduction, the problem of finding optimal contraction orders for arbitrary tensor networks is NP-complete. Therefore, one must settle for a mixture of exponential algorithms for small problems, e.g., $n \leq 20$, and otherwise hope for good contraction orders. For this reason, previous research has focused on the latter part, trying to find better heuristics. However, there has also been improvements for small-sized instances, for which novel dynamic programming techniques have been developed~\cite{Pfeifer_2014}.

In contrast, database join ordering has already benefited from these algorithms decades ago. Selinger presented the first dynamic programming algorithm for join ordering as early as 1970~\cite{selinger}. Later, the IKKBZ algorithm~\cite{ik,kbz}, which we adjust for tensor networks, adapted a well-known problem from job ordering~\cite{Monma1979SequencingWS} to provide optimal \textit{linear} plans for \textit{tree} queries. Similarly, we extend it to tensor networks to provide the same optimality guarantees for \textit{tree} tensor networks and \textit{linear} contraction orders. The challenge here, as it was decades ago with the IKKBZ algorithm, is to adapt the mathematical foundations to our setting.

In the field of tensor networks, we have seen DP algorithms that also emulate graph structure~\cite{Pfeifer_2014}; in join ordering there is~\cite{new_dp}. Several heuristics have been proposed~\cite{Gray_2021}, as was the case in join ordering~\cite{goo}. Interestingly, both research directions have recently used learned models to predict the orders~\cite{Marcus_2018,rl_tensor}. The work closest to ours is~\cite{ttn_poly}, which \textit{relaxes} the problem by using a different cost function: minimizing the most expensive contraction cost. In this way, one can actually find a polynomial-time algorithm for tree tensor networks. In contrast, our algorithm works directly with the original cost function.

We are not the first work to recognize the similarities between join ordering and contraction ordering. Dudek et al.~\cite{tensor_join_connection} have already highlighted this and used tree decompositions to solve the original problem, still relying on heuristic algorithms.

In the next sections we provide the modifications needed to enable the IKKBZ algorithm to work on tree tensor networks.