# Factorizing the Brauer monoid in polynomial time

Daniele Marchei  Computer Science, University of Camerino, Camerino, Italy
Emanuela Merelli  Computer Science, University of Camerino, Camerino, Italy
Andrew Francis  Centre for Research in Mathematics and Data Science, Western
Sydney University, Australia

###### Abstract

Finding a minimal factorization for a generic semigroup can be done by using
the Froidure-Pin Algorithm, which is not feasible for semigroups of large
sizes. On the other hand, if we restrict our attention to just a particular
semigroup, we could leverage its structure to obtain a much faster algorithm.
In particular, $\mathcal{O}(N^{2})$ algorithms are known for factorizing the
Symmetric group $S_{N}$ and the Temperley-Lieb monoid
$\mathcal{T}\mathcal{L}_{N}$, but none for their superset the Brauer monoid
$\mathcal{B}_{N}$. In this paper we hence propose a $\mathcal{O}(N^{4})$
factorization algorithm for $\mathcal{B}_{N}$. At each iteration, the
algorithm rewrites the input $X\in\mathcal{B}_{N}$ as $X=X^{\prime}\circ
p_{i}$ such that $\ell(X^{\prime})=\ell(X)-1$, where $p_{i}$ is a factor for
$X$ and $\ell$ is a length function that returns the minimal number of factors
needed to generate $X$.

##  1 Introduction

The Brauer monoid $\mathcal{B}_{N}$ is a diagram algebra introduced by Brauer
in 1937 [2], and later utilized by Kauffman and Magarshak in 1995 to define a
mapping between RNA secondary structures and elements of $\mathcal{B}_{N}$
(which they call “tangles”) [10]. The correspondence between properties of RNA
secondary structures, and properties of the factorizations of the tangles they
get mapped to, can then be studied [13]. But for this, factorization of Brauer
tangles is necessary, and this is the major topic of the present paper.

It can be easily proven that if there exists a length function for
$\mathcal{B}_{N}$ (i.e. a function that returns the minimal amount of factors
the input tangle is generated by) computable in polynomial time, then there
exists a polynomial time factorization algorithm (see Corollary 4). In this
paper we will find two length functions computable in quadratic time, one of
which is computable in linear time if we assume some precomputation steps are
already done. The key insight is that, since the length function for tangles
in the symmetric group $S_{N}$ (which is a submonoid of $\mathcal{B}_{N}$)
just involves counting the number of crossings they have, it would be
interesting to map every tangle in $\mathcal{B}_{N}$ with length $l$ to a
tangle in $S_{N}$ with exactly $l$ crossings. In this way, if this mapping
could be done in polynomial time, then we would have found our length
function.

The paper is divided in the following way. In Section 2 we begin by recalling
some related work. Section 3 is dedicated to giving some preliminaries on the
Brauer monoid, setting up the problem, illustrating a naive
$\mathcal{O}(N^{5})$ algorithm and we outline two assumptions we are basing
some proofs on. In Section 4 we go into more detail on the idea of defining a
mapping $\tau:\mathcal{B}_{N}\rightarrow S_{N}$, and some of its properties.
Section 5 will focus on just proving one theorem: i.e. that some edges in a
tangle “cannot come back” if they satisfy a particular property. This will be
the base for Section 6, in which we finally outline a quadratic time algorithm
for $\tau$. In Section 7 we will propose the two length functions that will
then be used in Section 8 to illustrate the final factorization algorithm with
$\mathcal{O}(N^{4})$ time complexity.

##  2 Related works

In a previous work [13] we proposed a factorization algorithm that uses a set
of polynomial-time heuristics for finding a possibly non-minimal
factorization, we then refine it by applying the axioms for the Brauer monoid
as a Term Rewriting System (TRS). This will eventually ensure minimality, but
since the TRS is not confluent the overall time complexity is difficult to
calculate and likely to be huge. This is because for the symmetric group, it
is known [17] that the maximal number of minimal factorizations is

$\frac{{N\choose 2}!}{1^{N-1}3^{N-2}\cdots(2N-3)^{1}}$

and the TRS will have to check all of them before deciding that there are no
more reductions possible.

The Froidure-Pin Algorithm can find the minimal factorization for any element
in a finite semigroup $S$ by performing $|S|+|A|-|G|-1$ operations, where $A$
is the set of axioms of $S$, and $G$ the set of generators [9]. For the Brauer
monoid the resulting time complexity lower-bound is therefore
$\Omega(|\mathcal{B}_{N}|)=\Omega((2N-1)!!)$111$(2N-1)!!$ is the “odd double
factorial”, defined as $(2N-1)!!=1\cdot 3\cdots(2N-3)\cdot(2N-1)$..

Algorithm 13 of “Computing with semigroups” [6] is capable of finding a
factorization, but it is not guaranteed to be minimal. It computes two sets
$\mathfrak{R}$ (the $\mathcal{R}$-classes of $\mathcal{B}_{N}$) and
$(\mathcal{B}_{N})\lambda$. The size of $\mathfrak{R}$ for $\mathcal{B}_{N}$
can be calculated by the following recurrence relation:

$\begin{array}[]{lll}a(0)&=&1\\\ a(1)&=&1\\\
a(N)&=&a(N-1)+(N-1)a(N-2)\end{array}$

which is the number of ways to partition a set of size $N$ into subsets of
size one or two [5]. This recurrent relation is clearly bounded below by $N!$.

The authors also say that for regular semigroups (as in the case for
$\mathcal{B}_{N}$), $|\mathfrak{R}|=|(\mathcal{B}_{N})\lambda|$, and that the
calculation for $\mathfrak{R}$ is redundant. This does not reduce the time
complexity because $(\mathcal{B}_{N})\lambda$ still needs to be computed.

Lastly, two submonoids of $\mathcal{B}_{N}$ can be factorized in quadratic
time. The symmetric group can be factorized by using the BubbleSort algorithm,
and the Temperley-Lieb monoid can be factorized by using the algorithm
proposed by Ernst et al. [8]. We will discuss these two algorithms in Appendix
A.

##  3 Preliminaries

Given $N\geq 0$, arrange $2N$ nodes in two rows of $N$ nodes each. Nodes in
the upper row are labelled with $[N]=\\{1,2,\cdots,N\\}$ while nodes in the
bottom row are labelled with
$[N^{\prime}]=\\{1^{\prime},2^{\prime},\cdots,N^{\prime}\\}$. A tangle is a
set of $N$ edges connecting any two distinct nodes in $[N]\cup[N^{\prime}]$
such that each node is in exactly one edge. We will represent edges as
$e=(x,y)$ in a canonical form in which $x<y$ if both $x$ and $y$ are nodes in
the same row, while in the case that $e$ connects nodes from in different
rows, $x\in[N]$ and $y\in[N^{\prime}]$.

Given two tangles $X$ and $Y$ we define their composition $X\circ Y$ by
stacking $X$ on top of $Y$ (matching the bottom row of $X$ with the top row of
$Y$) and then tracing the path of each edge (we will ignore internal loops in
our setup). The set of all tangles on $2N$ nodes under composition is called
the Brauer monoid $\mathcal{B}_{N}$ [2] and the identity tangle is
$I_{N}=(1,1^{\prime})(2,2^{\prime})\cdots(i,i^{\prime})\cdots(N,N^{\prime})$
(see Figure 1).

Figure 1: On the left a tangle $X=(1,3)(2,1^{\prime})(2^{\prime},3^{\prime})$
in $\mathcal{B}_{3}$, on the right its unique minimal factorization
$T_{1}\circ U_{2}$.

For our purposes, it will be useful to classify edges by where they are
connected. Tangles have two types of edges [4]:

  * •

hooks are edges in which both nodes are on the top or on the bottom row. The
former ones are called upper hooks and the latter lower hooks;

  * •

transversals are edges in which one node is on the top row while the other one
is on the bottom. We further classify transversal edges as:

    * –

positive transversal are in the form $x>y^{\prime}$

    * –

zero transversal are in the form $x=y^{\prime}$

    * –

negative transversal are in the form $x<y^{\prime}$

where $x$ is the upper node and $y^{\prime}$ is the lower node.

Given a tangle $X$, we say that two edges _cross_ if they intersect each other
in the diagrammatic representation of $X$ (assuming the edges are drawn in a
way that minimizes the number of crossings). The _size_ of an edge $e=(x,y)$
is defined as $|e|=|x-y|$ ($x$ and $y$ are arbitrary nodes).

Given a tangle $X$ with an upper hook $h=(i,i+1)$ of size one and another
distinct edge $e=(x,y)$, we say that we _merge $h$ with $e$_ by removing them
from $X$ and connecting their respective nodes such that the newly added edges
$e_{1}$ and $e_{2}$ do not cross (see Figure 2). In particular:

  * •

if $e$ is a upper hook such that $x<i$ and $i+1<y$, then $e_{1}=(x,i)$ and
$e_{2}=(i+1,y)$;

  * •

if $e$ is a lower hook such that $x\leq i$ and $i+1\leq y$, then $e_{1}=(i,x)$
and $e_{2}=(i+1,y)$;

  * •

if $e$ is a negative transversal such that $x<i$ and $i+1\leq y$, then
$e_{1}=(x,i)$ and $e_{2}=(i+1,y)$;

  * •

if $e$ is a positive transversal such that $x>i+1$ and $i\geq y$, then
$e_{1}=(i,y)$ and $e_{2}=(i+1,x)$;

  * •

for all other combinations, the merging of $h$ and $e$ is undefined, since it
will not be useful for our use case (at the end of Section 5 it will become
clear why).

(a)

(b)

(c)

(d)

Figure 2: The four cases for which we define the merge operation. In all
cases, $e=(x,y)$ and $h=(i,i+1)$. (a) $e$ is an upper hook. (b) $e$ is a lower
hook. (c) $e$ is a negative transversal. (d) $e$ is a positive transversal.

The Brauer monoid can also be defined as the set of tangles generated by the
composition of _prime_ tangles, which we call $T$-primes and $U$-primes,
defined as:

  * •

$T_{i}=(1,1^{\prime})(2,2^{\prime})\cdots(i,i^{\prime}+1)(i+1,i^{\prime})\cdots(N,N^{\prime})$;

  * •

$U_{i}=(1,1^{\prime})(2,2^{\prime})\cdots(i,i+1)(i^{\prime},i^{\prime}+1)\cdots(N,N^{\prime})$.

where $i$ is called the index of that prime tangle. These primes also satisfy
the axioms in Table 1. We classify these axioms into three types:

  * •

Delete rules: because they decrease the number of primes to be composed;

  * •

Braid rules: because they resemble the braid relation in the symmetric group;

  * •

Swap rules: because they allow to commute primes without changing the
resulting tangle.

We call a word $F\in\\{T_{i},U_{i}\\}^{*}$ a factorization (the empty word
coincides with the identity tangle $I_{N}$). If this factorization is reduced,
i.e. there is no other equivalent word of shorter length, then it is called
minimal.

Define
$\otimes:\mathcal{B}_{N}\times\mathcal{B}_{M}\rightarrow\mathcal{B}_{N+M}$ to
be the tensor product such that $Z=X\otimes Y$ is the tangle in which $Y$ is
placed on the right of $X$. We call $X$ and $Y$ the components of $Z$ [16]. If
we assume $F_{X}$ and $F_{Y}$ to be minimal factorizations for $X$ and $Y$,
then we have that $F_{Z}=F_{X}\circ F_{Y}$ is a minimal factorization for $Z$,
therefore we can factorize each component separately and, for the rest of the
paper, we will assume that every tangle has only one component.

Delete |  |  |
---|---|---|---
1. | $T_{i}\circ T_{i}$ | = | $I_{N}$
2. | $U_{i}\circ U_{i}$ | = | $U_{i}$
3. | $T_{i}\circ U_{i}$ | = | $U_{i}$
4. | $U_{i}\circ T_{i}$ | = | $U_{i}$
5. | $U_{i}\circ U_{j}\circ U_{i}$ | = | $U_{i}\iff|i-j|=1$
6. | $U_{i}\circ T_{j}\circ U_{i}$ | = | $U_{i}\iff|i-j|=1$
7. | $T_{i}\circ U_{j}\circ U_{i}$ | = | $T_{j}\circ U_{i}\iff|i-j|=1$
8. | $U_{i}\circ U_{j}\circ T_{i}$ | = | $U_{i}\circ T_{j}\iff|i-j|=1$
9. | $U_{i}\circ T_{j}\circ T_{i}$ | = | $U_{i}\circ U_{j}\iff|i-j|=1$
10. | $T_{i}\circ T_{j}\circ U_{i}$ | = | $U_{j}\circ U_{i}\iff|i-j|=1$
Braid |  |  |
11. | $T_{i}\circ T_{j}\circ T_{i}$ | = | $T_{j}\circ T_{i}\circ T_{j}\iff|i-j|=1$
12. | $T_{i}\circ U_{j}\circ T_{i}$ | = | $T_{j}\circ U_{i}\circ T_{j}\iff|i-j|=1$
Swap |  |  |
13. | $T_{i}\circ T_{j}$ | = | $T_{j}\circ T_{i}\iff|i-j|>1$
14. | $T_{i}\circ U_{j}$ | = | $U_{j}\circ T_{i}\iff|i-j|>1$
15. | $U_{i}\circ T_{j}$ | = | $T_{j}\circ U_{i}\iff|i-j|>1$
16. | $U_{i}\circ U_{j}$ | = | $U_{j}\circ U_{i}\iff|i-j|>1$
Table 1: Axioms for the Brauer monoid. Axioms from 1 to 10 are called delete
rules, 11 and 12 are braid rules and 13-16 are swap rules.

A length function $\ell(X):\mathcal{B}_{N}\rightarrow\mathbb{N}$ is a function
that returns the minimal number of prime factors required to compose the
tangle $X$, in other words, it returns the length of a minimal factorization
for $X$ (define $\ell(I_{N})=0$). If $\ell(X)$ can be computed in polynomial
time, say $t(N)$, then Algorithm 1 returns a minimal factorization in
$\mathcal{O}(N^{3}t(N))$ (see Corollary 4 for the proof).

Algorithm 1 Finds the minimal factorization for any tangle in
$\mathcal{B}_{N}$.

$X\in\mathcal{B}_{N}$

function Factorize $\mathcal{B}_{N}$($X$)

$l\leftarrow\ell(X)$

$F\leftarrow$ empty list

while $l\neq 0$ do

if $(i,i+1)\in X$ then

$h\leftarrow(i,i+1)$

for $e\in X,e\neq h$ do

$X^{\prime}\leftarrow$ merge $h$ with $e$ in $X$ (if defined)

if $\ell(X^{\prime})=l-1$ then

$X\leftarrow X^{\prime}$

Append $U_{i}$ to $F$

break

else

for $i\in[1\dots N-1]$ do

$X^{\prime}\leftarrow T_{i}\circ X$

if $\ell(X^{\prime})=l-1$ then

$X\leftarrow X^{\prime}$

Append $T_{i}$ to $F$

break

$l\leftarrow l-1$

return $F$

Lastly, we list two assumptions we believe are true but were not able to
prove. They will be useful for some proofs in the following Sections.

######  Assumption 1.

Every factorization in the Brauer monoid can be reduced to a minimal one by a
sequence of “delete”, “braid” and “swap” rules. In other words, we do not need
to increase the factorization length in order to find a shorter one.

######  Assumption 2.

If a tangle $X$ has $k$ crossings, then there exists a minimal factorization
$F$ with exactly $k$ $T$-primes and no other factorization with fewer
$T$-primes exists.

We empirically tested these assumptions, for the methodology we refer to
Appendix B.

##  4 Mapping $\mathcal{B}_{N}$ to $S_{N}$

Tangles in the symmetric groups $S_{N}$ are generated only by $T$-primes. This
implies that, given a tangle $X$ in $S_{N}$, calculating $\ell(X)$ will amount
to just counting its number of crossings, which can be done in
$\mathcal{O}(N^{2})$ time222There is a faster approach that brings down the
time complexity to $\mathcal{O}(N\log N)$ [11], but as we will see in Section
6, for our purposes it will be much more useful to have the actual
factorization for $X$, which cannot be done faster than $\mathcal{O}(N^{2})$..
With this in mind, it would be useful to have a function
$\tau:\mathcal{B}_{N}\rightarrow S_{N}$ that maps tangles
$X\in\mathcal{B}_{N}$ to tangles in $S_{N}$ such that $\ell(X)=\ell(\tau(X))$.
In this way, we could define $\ell(X)$ by just computing $\tau(X)$ and
counting its number of crossings. Therefore if $\tau$ can be computed in
polynomial time, then $\ell$ can be computed in polynomial time too. We now
proceed to define $\tau$.

######  Definition 1.

Given a factorization $F$ for a tangle $X\in\mathcal{B}_{N}$, we define $\tau$
as the function that maps each prime factor $p_{i}$ of $F$ to $T_{i}$. In
other words, $T_{i}\mapsto T_{i}$ and $U_{i}\mapsto T_{i}$ for each $T$ and
$U$ prime in $F$.

######  Theorem 1.

If $F$ is a minimal factorization, then $\tau(F)$ is minimal too.

###### Proof.

We prove this by contradiction (see Figure 3).

Let $F$ be a minimal factorization and assume $\tau(F)$ is not minimal.
Therefore it can be rewritten to contain the subword $T_{i}\circ T_{i}$ by
using Axioms 11 and 13 ([1], Theorem 3.3.1).

Let $s=r_{1}r_{2}\dots r_{k-1}$ be a sequence of rewritings for $\tau(F)$
using Axioms 11 or 13 and $r_{k}$ be a rewriting step using Axiom 1. For each
$r_{i}\in s$, there exists at least one rewriting $\bar{r}_{i}$ in the
preimage $\tau^{-1}(r_{i})$, meaning that $r_{i}$ applied to $\tau(F)$ maps to
a rewriting step $\bar{r}_{i}\in\tau^{-1}(r_{i})$, applied to $F$, that uses
Axioms 11 to 16.

This implies that there exists a sequence of rewritings
$\bar{s}=\bar{r}_{1}\bar{r}_{2}\dots\bar{r}_{k-1}$ for $F$ such that, after
$\bar{r}_{k-1}$, $F$ will contain one of the following subwords: $T_{i}\circ
T_{i}$, $U_{i}\circ U_{i}$, $T_{i}\circ U_{i}$ or $U_{i}\circ T_{i}$.
Therefore, $\bar{r}_{k}$ will use one of the Axioms from 13 to 16 to reduce
$F$ to a shorter factorization.

This implies that $F$ was not minimal, which is a contradiction.

∎

Figure 3: Diagram for the proof of Theorem 1. Assume $F$ is minimal and
$\tau(F)$ is not. Axioms 11 and 13 applied to $\tau(F)$ have preimage to
axioms 11-16 applied to $F$. In the end, $\tau(F)$ will contain a $T_{i}\circ
T_{i}$ because we assumed it was not minimal, which implies $F$ was not
minimal too and thus we have a contradiction.

######  Corollary 1.

Let $F$ be an arbitrary factorization. If $\tau(F)$ is not minimal, then $F$
is not minimal too.

###### Proof.

This is the contrapositive of Theorem 1. ∎

######  Corollary 2.

Assuming $F$ to be minimal, then $|F|=|\tau(F)|$.

Corollary 2 allows us to determine the maximal length a minimal factorization
in $\mathcal{B}_{N}$ can have.

######  Corollary 3.

The longest minimal factorization in $\mathcal{B}_{N}$ has length
$\frac{N(N-1)}{2}$.

###### Proof.

By Theorem 1 we know that every factorization $F$ has another factorization
$\tau(F)$ with the same length composed only by $T$-primes. Therefore we only
need to check the longest minimal factorization in $S_{N}$, which is well-
known to be $\frac{N(N-1)}{2}$. ∎

######  Corollary 4.

Algorithm 1 has time complexity $\mathcal{O}(N^{3}t(N))$, where $t(N)$ is the
time complexity for the length function $\ell$.

###### Proof.

In the case in which there exists edge $h=(i,i+1)$ in $X$, Algorithm 1
iterates through all edges, merges them with $h$ and then calculates $\ell$
for each of the resulting tangle. The overall complexity for this case is
therefore $\mathcal{O}(Nt(N))$. By Corollary 3 we know that the longest
factorization possible is quadratic and Algorithm 1 removes each of them one
at a time. Therefore the time complexity for Algorithm 1 is
$\mathcal{O}(N^{3}t(N))$. ∎

The function $\tau$ we defined can be generalized to operate on an arbitrary
subword of a factorization $F$.

######  Definition 2.

Let $F$ be a factorization for a tangle $X\in\mathcal{B}_{N}$, we define
$\tau^{*}$ be the function that applies $\tau$ to only a subword of $F$.

######  Theorem 2.

If $F$ is a minimal factorization, then $\tau^{*}(F)$ is minimal too.

###### Proof.

The proof is similar to the one for Theorem 1 but it requires 1 because
$\tau^{*}(F)$ can be any factorization in $\mathcal{B}_{N}$, and every
braid/swap $r$ applied to $\tau^{*}(F)$ has to correspond to a braid/swap in
$F$ that is in the preimage of $\tau^{*}(r)$. There are also more ways in
which $\tau^{*}(F)$ can be not minimal. See the following Hasse diagram:

The arrows represent the preimage of $\tau^{*}$, each element has also a self-
loop that was not drawn. For the proof of Theorem 1 only the left Hasse
Diagram was applicable, but now also the right one has to be taken into
consideration. Since we assumed that $\tau^{*}(F)$ was not minimal, then by 1
it can be rewritten by a sequence of swaps and braids to contain any element
in the above Hasse Diagram, but for all such elements there exists a preimage
that must be in $F$ and, since all preimages are not minimal, it implies that
$F$ was not minimal in the first place, hence we have a contradiction and
$\tau^{*}(F)$ must have been minimal too. ∎

######  Corollary 5.

Let $F$ be an arbitrary factorization. If $\tau^{*}(F)$ is not minimal, then
$F$ is not minimal too.

###### Proof.

This is the contrapositive of Theorem 2. ∎

Corollary 5 will be very helpful in Section 5, where we will use it to prove
that some undesirable factorizations are always not minimal.

We can now use the above theorems to find a (not very useful) length function
for $\mathcal{B}_{N}$. Given a tangle $X\in\mathcal{B}_{N}$, assume to have a
minimal factorization $F$ for $X$. Now compute $\tau(F)$, which corresponds to
another tangle $\tau(X)\in S_{N}$. By Corollary 2 we know that the number of
crossings of $\tau(X)=|F|$ so we just count them and we obtain the number of
factors for $X$. We can represent this mapping as the diagram in Figure 4.

Figure 4: From a tangle in $\mathcal{B}_{N}$ we obtain a minimal factorization
$F$, we then compute $\tau(F)$ which corresponds to a tangle in $S_{N}$.

Admittedly, this is not a very useful mapping because we are assuming to have
$F$ in the first place (which is what we are ultimately looking for). What we
would like to find now is a way to extend $\tau$ to arbitrary tangles, not
just factorizations (the dashed arrow in Figure 4). In this way, if we find a
polynomial time algorithm for finding a tangle $\tau(X)\in S_{N}$ such that
its number of crossings is equal to $\ell(X)$, we would then have a polynomial
time length function. We will present such an algorithm in Section 6.

##  5 Passing through and coming back

This Section is entirely dedicated to proving that if the number of $T$-primes
an edge $e$ “passes through” is greater or equal to $|e|$, then it does not
pass through any $U$-prime. This is a key property we will leverage in Section
6, where at the end of it, we will have all the necessary components for
computing $\tau(X)$ in polynomial time. In this Section we will also argue why
the merge operation presented in Section 3 is undefined for some edges.

######  Definition 3 (Passing through).

Given a factorization $F$ for a tangle $X$, a prime tangle $p_{i}\in F$ and an
edge $e\in X$, we say that $e$ “passes through” $p_{i}$ if $e$ is connected to
the node $i$ or $i^{\prime}$ of $p_{i}$. We indicate with $\\#T(e)$ and
$\\#U(e)$ the number of $T$-primes and $U$-primes respectively $e$ passes
through in $F$.

We will now define what “coming back” means. The goal for these definitions is
to prove that if $\\#U(e)>0$ then $e$ cannot come back. This will imply that
$\\#U(e)>0\implies\\#T(e)<|e|$ and therefore, by contraposition,
$\\#T(e)\geq|e|\implies\\#U(e)=0$, which is what we want to prove.

######  Definition 4 (Coming back at $p$).

Given a factorization $F$ for a tangle $X$, a prime tangle $p\in F$ and an
edge $e\in X$, we say that $e$ “comes back” at $p$ if $|e|$ decreases when
passing through $p$.

######  Definition 5 (Coming back in $F$).

Given a factorization $F$ for a tangle $X$ and an edge $e\in X$, we say that
$e$ “comes back” in $F$ if there exists a prime $p$ at which $e$ comes back.

See Figure 5 for an example.

Figure 5: A tangle along with one of its minimal factorizations $F=T_{1}\circ
U_{2}\circ U_{3}\circ T_{1}\circ T_{2}$. The edge $(1,3)$ passes through
$T_{1}$ and $U_{2}$, edge $(2,3^{\prime})$ passes through two $T_{1}$s and one
$T_{2}$, edge $(4,1^{\prime})$ passes through $U_{3},U_{2}$ and $T_{1}$ and
edge $(2^{\prime},4^{\prime})$ passes through $T_{2}$ and $U_{3}$. Edge
$(2,3^{\prime})$ comes back at the bottom-most $T_{1}$ because it decreases in
size, this also means that it comes back in $F$. Note also that
$(2,3^{\prime})$ is the only edge that passes through only $T$-primes and
satisfies the property $\\#T(e)\geq|e|$.

######  Theorem 3.

Let $X\in\mathcal{B}_{N}$, $e\in X$ and $F$ any minimal factorization for $X$.
Then $e$ comes back in $F$ if and only if $\\#T(e)+\\#U(e)>|e|$.

###### Proof.

Forward direction.

Assume $e$ comes back in $F$, then there exists a prime $p_{i}$ at which $e$
comes back, but if it comes back at $p_{i}$ it means $e$ passed through
another prime $p_{i}^{\prime}$ with the same index $i$, and since every edge
passes through at least $|e|$ distinct primes, it must be that
$\\#T(e)+\\#U(e)>|e|$.

The backward direction uses the same argument.

∎

We will now use Theorem 3 to prove that a tangle in $S_{N}$ has a pair of
edges $e$ and $e_{2}$ as in Figure 6a if and only if $e$ comes back. This
theorem will allow us to ignore these tangles in the following theorems,
because later on we will assume that a given edge does not come back.

######  Theorem 4.

Given $X\in S_{N}$ with a negative transversal $e_{1}=(x_{1},y_{1}^{\prime})$,
if there exists another edge $e_{2}=(x_{2},y_{2}^{\prime})$ such that
$x_{2}<x_{1}$ and $y_{2}^{\prime}>y_{1}^{\prime}$ then $e_{1}$ comes back in
any factorization for $X$.

###### Proof.

Let’s set some variables:

$\begin{array}[]{rcl}a&=&x_{2}-1\\\ b&=&x_{1}-x_{2}-1\\\ c&=&N-x_{1}\\\
a^{\prime}&=&y_{1}^{\prime}-1\\\
b^{\prime}&=&y_{2}^{\prime}-y_{1}^{\prime}-1\\\
c^{\prime}&=&N-y_{2}^{\prime}\end{array}$

where $a,b$ and $c$ are the number of nodes with indices less than $x_{2}$, in
between $x_{2}$ and $x_{1}$, and greater than $x_{1}$ respectively (same for
$a^{\prime},b^{\prime}$ and $c^{\prime}$). Therefore we have that

$a+b+c=a^{\prime}+b^{\prime}+c^{\prime}$

implying that

$a^{\prime}-a-b=c-b^{\prime}-c^{\prime}$

which counts the least amount of edges that have to cross $e$ from right to
left. Notice now that

$\begin{array}[]{ccl}x_{1}&=&b+x_{2}+1=b+a+2\\\
y_{1}^{\prime}&=&a^{\prime}+1\end{array}$

and therefore

$|e_{1}|=y_{1}^{\prime}-x_{1}=a^{\prime}+1-(b+a+2)=a^{\prime}-a-b-1$

By substitution, we can now obtain

$\begin{array}[]{ccc}a^{\prime}-a-b&=&c-b^{\prime}-c^{\prime}\\\
|e_{1}|+1&=&c-b^{\prime}-c^{\prime}\\\
|e_{1}|&<&c-b^{\prime}-c^{\prime}\end{array}$

which shows that the least amount of edges that have to cross $e_{1}$ is
bigger than $|e_{1}|$, which implies that $\\#T(e_{1})>|e_{1}|$ and therefore
that $e_{1}$ comes back in $F$ (Theorem 3).

Note that this proof is not dependent on the factorization chosen, therefore
$e_{1}$ comes back in all minimal factorization for $X$. ∎

(a)

(b)

Figure 6: (a) Illustration for Theorem 4. If a tangle $X$ in $S_{N}$ contains
an edge $e_{1}$ and an edge $e_{2}$ as shown, then $e_{1}$ will come back in
all minimal factorizations for $X$. (b) Illustration for Theorem 5. If $e_{1}$
comes back in a minimal factorization, then there exists another edge $e_{2}$
like in (a).

######  Theorem 5.

Given $X\in S_{N}$ with a negative transversal $e_{1}=(x_{1},y_{1}^{\prime})$
and minimal factorization $F$ for $X$, if $e_{1}$ comes back in $F$, then
there exists another edge $e_{2}=(x_{2},y_{2}^{\prime})$ such that
$x_{2}<x_{1}$ and $y_{2}^{\prime}>y_{1}^{\prime}$ (Figure 6b).

###### Proof.

Since $e_{1}$ comes back in $F$, then $\\#T(e_{1})>|e_{1}|$ (Theorem 3).
Therefore $\\#T(e_{1})=|e_{1}|+c$ where $c\geq 1$.

Let’s set some variables:

$\begin{array}[]{rcl}a&=&x_{1}-1\\\
a^{\prime}&=&y_{1}^{\prime}-1=a+|e_{1}|\end{array}$

Where $a$ is the number of nodes before $x_{1}$ and $a^{\prime}$ is the number
of nodes before $y^{\prime}$. Suppose now that there is no edge
$e_{2}=(x_{2},y_{2}^{\prime})$ such that $x_{2}<x_{1}$ and
$y_{2}^{\prime}>y_{1}^{\prime}$, therefore we are assuming that all
$|e_{1}|+c$ edges that cross $e_{1}$ connect nodes with indices greater than
$x_{1}$ to nodes with indices less than $y_{1}^{\prime}$.

The number of nodes with indices less than $y_{1}^{\prime}$ that do not cross
$e$ is therefore

$\begin{array}[]{rcl}a^{\prime}-(|e_{1}|+c)&=&\\\ a+|e_{1}|-|e_{1}|-c&=&\\\
a-c\end{array}$

Since we know that $c\geq 1$, we have that $a-c<a$, which implies that not all
nodes with indices less than $x_{1}$ can connect to lower nodes with indices
less than $y_{1}^{\prime}$. Therefore there must be another edge
$e_{2}=(x_{2},y_{2}^{\prime})$ that crosses $e_{1}$ with $x_{2}<x_{1}$ and
$y_{2}^{\prime}>y_{1}^{\prime}$.

∎

######  Corollary 6.

Given $X\in S_{N}$ with a negative transversal $e=(x_{1},y_{1}^{\prime})$,
then $e$ comes back in every minimal factorization for $X$ if and only if
there exists another edge $e_{2}=(x_{2},y_{2}^{\prime})$ such that
$x_{2}<x_{1}$ and $y_{2}^{\prime}>y_{1}^{\prime}$.

In light of Corollary 6, from now on we will just say that $e$ does not come
back in $X$, since it is independent of the factorization.

Assuming that we now have a tangle $X\in S_{N}$ with an edge $e$ that does not
come back, we can always decompose it as $X=L\circ Z\circ R$ (see Figure 7).
This decomposition will come in handy when we will have to prove that a
particular factorization is always not minimal, and it will turn out that the
two tangles $L$ and $R$ can be safely ignored, simplifying the proof.

######  Theorem 6 (LZR Decomposition).

Let $a,b\geq 0$ be natural integers. Let $a^{\prime},b^{\prime}\geq 0$ be
natural integers such that $a^{\prime}>a$ and $a+b=a^{\prime}+b^{\prime}$. Let
$X\in S_{a+b+1}$ be a tangle containing the edge $e=(a+1,a^{\prime}+1)$ that
does not come back. Then $X$ can be decomposed as a composition of three
tangles $L,Z,R\in S_{a+b+1}$, where $L=I_{a+1}\otimes\sigma$ with $\sigma\in
S_{b}$, $Z=T_{a+1}\circ T_{a+2}\circ\cdots T_{a+|e|}$ (containing the edge
$e$) and $R=\omega\otimes I_{b^{\prime}+1}$ with $\omega\in S_{a^{\prime}}$.
This decomposition satisfies the property $\ell(X)=\ell(L)+\ell(Z)+\ell(R)$.
In the special case in which $a^{\prime}+1=a+b+1$ then $L=I_{N}$.

###### Proof.

Suppose a minimal factorization $F$ for $X$ is given. Since we know that $e$
does not come back, then we also know that $\\#T(e)=|e|$. This implies that
$F$ contains the sub-word $Z=T_{a+1}\circ T_{a+2}\circ\cdots T_{a+|e|}$. Now
use the axioms to rewrite $F$ so that $F=L^{\prime}\circ Z\circ R^{\prime}$,
where $L^{\prime}$ and $R^{\prime}$ contain the rest of the factorization.
Finally, use Axiom 13 to move every prime $p_{i}$ in $L^{\prime}$ with $i<a$
into $R^{\prime}$ and move every prime $p_{i}$ in $R^{\prime}$ with
$i>a^{\prime}+1$ into $L^{\prime}$. Thus obtaining $F=L\circ Z\circ R$. This
obviously satisfies $\ell(X)=\ell(L)+\ell(Z)+\ell(R)$.

In the case in which $N=y^{\prime}=a+b+1$, we can construct $R$ by removing
edge $e$ from $X$, relabelling all upper nodes $d$ such that $a+2\leq d\leq N$
as $d-1$ and adding the edge $(N,N^{\prime})$. By construction, we have then
that $X=Z\circ R$ and therefore we can set $L=I_{N}$. ∎

(a)

(b)

Figure 7: (a) A tangle $X\in S_{N}$ with an edge $e=(x,y^{\prime})$ that does
not come back. (b) The LZR decomposition of $X$. $\sigma$ and $\omega$ are
tangles in $S_{b}$ and $S_{a^{\prime}}$, while $Z=T_{a+1}\circ
T_{a+2}\circ\cdots\circ T_{a+|e|}$.

Finally, we can now prove that if an edge $e$ passes through at least one
$U$-prime then it cannot come back (see Figure 8). We assume $U_{i}$ to be the
last $U$-prime edge $e$ passes through before passing through prime tangle
$p$. This is because in the case in which $e$ passed through another
$U$-prime, say $U_{j}$, in a different factorization, we could pick $U_{j}$ as
the focus of the proof. This implies that, after $U_{i}$, $e$ passes through
only $T$-primes, in a generic tangle $A$, before $p$. We will also assume that
it is the first time that $e$ comes back. This assumption also allows us to
say that, since $e$ cannot come back the first time, it can never come back.

Lastly, we prove only the case in which $e$ is a negative transversal in $A$
and $U_{i}$ is on top of $A$. This is because we can reflect $U_{i}\circ
A\circ T_{j}$ vertically or horizontally to cover any case, and since
reflecting a tangle does not change the length of its factorization, then if
one of them is not minimal, then all reflections are not minimal too. This
implies that an edge cannot come back if at any time it passes through a
$U$-prime.

Figure 8: The general case in which an edge $e$ “comes back”. $e$ passes
through a $U$-prime $U_{i}$, then, after a series of $T$-primes contained in a
tangle $A\in\mathcal{B}_{N}$, it passes through a prime tangle $p_{j}$ that
reduces it size. We would like to prove that the factorization $U_{i}\circ
F_{A}\circ p_{j}$ (where $F_{A}$ is a minimal factorization for $A$) is always
not minimal.

We now prove that the configuration seen in Figure 8 always results in a not
minimal factorization. By using Theorem 2 and Theorem 6 we can now reduce the
general case of Figure 8 to a simpler one, in which we prove the non-
minimality of the factorization $U_{i}\circ Z\circ Z^{\prime}\circ T_{j}$,
where $Z$ and $Z^{\prime}$ are the results of two LZR decompositions and thus
have the form $Z=T_{i+1}\circ T_{i+2}\circ\cdots\circ T_{j}$ and
$Z^{\prime}=T_{k}\circ T_{k+1}\circ\cdots\circ T_{j-1}$ for some $k<j$. Follow
Figure 9 for the steps of the proof.

Once we are in the case of Figure 9i we will have a factorization in this
form:

$U_{i}\circ\underbrace{T_{i+1}\circ T_{i+2}\circ\cdots\circ
T_{j}}_{Z}\circ\underbrace{T_{k}\circ T_{k+1}\circ\cdots\circ
T_{j-1}}_{Z^{\prime}}\circ T_{j}$

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

Figure 9: (a) The original tangle $X$, which is a composition of $U_{i}$, a
tangle $A\in\mathcal{B}_{N}$ and a prime tangle $p_{j}$. (b) Apply $\tau$ on
$A$ and $p_{j}$ (Theorem 2). Remember that $e$ passes through only $T$-primes,
therefore it is still present in $\tau(A)$. (c) Perform a LZR decomposition on
$\tau(A)$ in which $a=i$, $b=N-i-1$, $a^{\prime}=j$ and $b^{\prime}=N-j-1$.
(d) By Theorem 6, $L=I_{i+1}\otimes\sigma$ with $\sigma\in S_{b}$. This
implies that we can move $U_{i}$ to be under $L$. (e) Since $L$ no longer
affects edge $e$, we can delete it. (f) Since $R=\omega\otimes I_{N-j}$ with
$\omega\in S_{j}$, then there exists an edge $u=(k,j^{\prime})$ for some
$k<j$. The white circle and the dashed line indicate that we do not know where
$k$ lies on the top row. (g) Perform a LZR decomposition on $R$, but since we
have that $u$ is connected to $j$, we then have that $L^{\prime}$ is the
identity tangle and can be ignored (remember the special case for Theorem 6).
We thus now have $R=Z^{\prime}\circ R^{\prime}$. (h) As before, we can move
$T_{j}$ above $R^{\prime}$. (i) We can now delete $R^{\prime}$, and this is
the simplified case we will prove will always imply a not minimal
factorization.

We will go through all cases for $k$ and prove that this factorization is
always not minimal:

  * •

if $k>i$, then there are too many crossings (Figure 10):

    * –

the factorization $Z\circ Z^{\prime}\circ T_{j}$ has
$\ell(Z)+\ell(Z^{\prime})+1$ crossings, but edge $e$ and edge $u$ can be
redrawn so that they do not cross, thus obtaining the same tangle in $S_{N}$
but with fewer crossings. This implies that this factorization is not minimal;

  * •

if $k\leq i$, then the factorization contains $U_{i}\circ T_{i+1}\circ T_{i}$
(Figure 11):

    * –

every factor in $Z^{\prime}$ with index $k<i-1$ can be ignored because

$\begin{array}[]{cc}U_{i}\circ\underbrace{T_{i+1}\circ T_{i+2}\circ\cdots\circ
T_{j}}_{Z}\circ\underbrace{\overbrace{T_{k}\circ T_{k+1}\circ\cdots\circ
T_{i-2}}^{k<i-1}\circ T_{i-1}\circ T_{i}\circ T_{i+1}\circ\cdots\circ
T_{j-1}}_{Z^{\prime}}\circ T_{j}&=\\\ \overbrace{T_{k}\circ
T_{k+1}\circ\cdots\circ T_{i-2}}^{k<i-1}\circ U_{i}\circ T_{i+1}\circ
T_{i+2}\circ\cdots\circ T_{j}\circ T_{i-1}\circ T_{i}\circ
T_{i+1}\circ\cdots\circ T_{j-1}\circ T_{j}&\\\ \end{array}$

therefore reducing the factorization to

$U_{i}\circ\underbrace{T_{i+1}\circ T_{i+2}\circ\cdots\circ
T_{j}}_{Z}\circ\underbrace{T_{i-1}\circ T_{i}\circ T_{i+1}\circ\cdots\circ
T_{j-1}}_{Z^{\prime}}\circ T_{j}$

By construction, we have that $Z\circ Z^{\prime}\circ T_{j}$ will contain an
edge $e=(i-1,j^{\prime}+1)$, which falls into the special case of the LZR
decomposition. This implies that we can rewrite the above factorization as

$U_{i}\circ Z^{\prime\prime}\circ R$

where $Z^{\prime\prime}=T_{i-1}\circ T_{i}\circ\cdots\circ T_{j}$ and
$R=\omega\otimes I_{N-j}$, where $\omega\in S_{j}$. This is clearly not
minimal because

$\begin{array}[]{lc}U_{i}\circ Z^{\prime\prime}&=\\\ U_{i}\circ T_{i-1}\circ
T_{i}\circ\cdots&=\\\ U_{i}\circ U_{i-1}\circ\cdots\end{array}$

in both cases, we have shown that the factorization was not minimal.

(a)

(b)

Figure 10: Example for the case in which $k>i$. (a) The factorization
$U_{i}\circ Z\circ Z^{\prime}\circ T_{j}$ after LZR decomposition. There are
six crossings. (b) The tangle obtained by composing $Z$, $Z^{\prime}$ and
$T_{j}$. Edges $e$ and $u$ were drawn again so that they do not cross. Note
how the resulting tangle has only four crossings, meaning that the previous
one was not minimal.

(a)

(b)

(c)

(d)

(e)

Figure 11: Example for the case in which $k\leq i$. (a) The factorization
$U_{i}\circ Z\circ Z^{\prime}\circ T_{j}$ after LZR decomposition. (b) All
$T$-primes with an index less than $i-1$ are removed from their tangle. (c)
The $T$-primes are removed. (d) $Z$ and $Z^{\prime}$ are composed together. By
construction, there is an edge $e=(i-1,j^{\prime}+1)$. (e) Perform a LZR
decomposition (special case). By the structure of $Z^{\prime\prime}$, the
resulting factorization is not minimal because it contains $U_{i}\circ
T_{i-1}\circ T_{i}$.

There are two more special cases to address. The first one is when edge $e$ is
a zero transversal (Figure 12). In this case, the procedure is the same as in
Figure 8 but we perform the LZR decomposition only once.

(a)

(b)

(c)

(d)

Figure 12: The special case in which $e$ is a zero transversal. (a) Given a
tangle $A\in\mathcal{B}_{N}$ and a prime tangle $p_{N}$, apply $\tau$ to $A$
and $p$. In this case, the index for the $U$-prime is $N$. (b) LZR
decomposition of $\tau(A)$. (c) Move $R$ below $T_{N}$ and remove it. (d)
Proof that the factorization is not minimal.

The last special case is when not only $e$ is a zero transversal, but $A$ has
another zero transversal at $(N-1,N^{\prime}-1)$ (Figure 13). In this case, no
simplification step is required because the factorization is trivially not
minimal for any prime tangle $p$.

(a)

(b)

Figure 13: The factorization is not minimal because $U_{i}\circ p$ is not
minimal for any $p$.

This whole argument proves that $\\#U(e)>0\implies\\#T(e)<|e|$. This is
because if it was the case that if $\\#U(e)>0$ but $\\#T(e)\geq|e|$, then it
would imply that there are more $T$-primes than $|e|$ and therefore, at some
point, $e$ must come back, which we just proved is not possible given that
$\\#U(e)>0$. This actually proves that $\\#T(e)\geq|e|\implies\\#U(e)=0$ by
contraposition.

This also explains why the merge operation is undefined for some edges. If
$h=(i,i+1)$ is an upper hook of size one and $e$ is another distinct edge,
then $e$ can pass through $U_{i}$ only if it satisfies one of the conditions
presented in Section 3. If it doesn’t, then it must come back to pass through
$U_{i}$, but this would imply that that particular factorization is not
minimal, and therefore can be ignored.

##  6 Node polarity

In this Section we will prove that $\tau(X)$ is unique and computable in
polynomial time. To do this, we will introduce the concept of “node polarity”,
a property preserved by $\tau$.

Given a node $x$, we define the polarity of $x$ as follows:

  * •

if $x$ is connected to a transversal edge $e$, then $x$ is positive (+) if $e$
is positive transversal, negative (-) if it is negative transversal and zero
(0) if it is a zero transversal

  * •

if $x$ is connected to an upper hook $h$, then $x$ is negative (-) if it is
the left node of $h$ and positive (+) if it is its right node. The polarity is
reversed for lower hooks.

######  Theorem 7.

$\tau$ preserves node polarity.

###### Proof.

For all edges $e$ such that $\\#T(e)\geq|e|$ this is trivially true because
they are present in both in $X$ and $\tau(X)$, this includes all edges with
node polarity 0. Therefore we need to prove that $\tau$ preserves node
polarity for all nodes that are connected to edges $e$ such that $\\#U(e)>0$.

As we can see in the following diagram, after $\tau$ every node of every
factor in the factorization will be connected to another one with the same
polarity.

Since we are assuming that $\\#U(e)>0$, then it implies that $e$ does not come
back, and therefore node polarity is preserved. ∎

Polarity preservation is the first property that $\tau(X)$ must satisfy, but
it is not enough because there are many tangles in $S_{N}$ with the same
polarity as $X$. Lemma 1 and Theorem 8 will state that edges with the same
polarity in $\tau(X)$ do not cross, which will imply the uniqueness of
$\tau(X)$.

######  Lemma 1.

Let $\sigma$ be a permutation containing an inversion
($\sigma(i)$,$\sigma(j)$), with $i<j$. After swapping $i$ with $j$, the new
permutation will have fewer inversions than $\sigma$.

###### Proof.

For readability’s sake, we will define $y=\sigma(i)$ and $x=\sigma(j)$. We
also define the notation $\sigma_{I}$ for the set of elements in $\sigma$
having indices in the set $I$.

Let $L$, $C$ and $R$ be three disjoint sets of indices satisfying $i<L,C,R<j$.
Let’s also assume that

$\sigma_{L}>y>\sigma_{C}>x>\sigma_{R}$

meaning that the elements between $y$ and $x$ can take any value. We do not
need to check the elements outside the rage $[i,j]$ because their number of
inversions will stay fixed.

We can now observe what happens after swapping $y$ with $x$. Moving $y$ will
add $|\sigma_{L}|$ inversions because $y$ is smaller than every element in
$\sigma_{L}$, while it will remove $|\sigma_{C}|+|\sigma_{R}|$ inversions
because $y$ is bigger than the elements contained in $\sigma_{C}$ and
$\sigma_{R}$.

On the other hand, moving $x$ will remove $|\sigma_{L}|+|\sigma_{C}|$
inversions because they contain bigger elements, and it will add
$|\sigma_{R}|$ because it contains smaller elements.

Finally, swapping $y$ and $x$ will remove one inversion because we assumed
$y>x$.

By summing everything together we obtain that the new permutation will have a
different amount of inversions, i.e. :

$\displaystyle|\sigma_{L}|-|\sigma_{C}|-|\sigma_{R}|-|\sigma_{L}|-|\sigma_{C}|+|\sigma_{R}|-1$
$\displaystyle=-2|\sigma_{C}|-1$

We can see that the difference in the number of inversions is always negative,
and therefore the new permutation will have fewer inversions. ∎

######  Theorem 8.

Let $X$ be a tangle with minimal factorization $F$. If the nodes of two edges
$e_{1},e_{2}\in\tau(X)$ have the same polarity and $e_{1}$ and $e_{2}$ are not
edges of $X$ too, then they do not cross.

###### Proof.

We know that $\tau$ preserves node polarity and also that since $|\tau(F)|$ is
minimal, then it will have the minimal amount of $T$-primes and therefore the
minimal amount of crossings in $\tau(X)$. By Lemma 1 we know that two edges
that do not cross add fewer $T$-primes compared to edges that do cross.
Therefore $e_{1}$ and $e_{2}$ do not cross in $\tau(X)$. ∎

We can now finally prove that there exists only one $\tau(X)$.

######  Theorem 9.

Given a tangle $X$, there exists only one $\tau(X)$ that preserves node
polarity and minimizes the number of crossings.

###### Proof.

For the sake of brevity, we will assume all mentioned nodes are not connected
to edges in both $X$ and $\tau(X)$. We will also just focus on nodes with
negative polarity, because for positive polarity the argument is basically the
same.

Suppose two upper nodes $x_{1}<x_{2}$ have negative polarity. Assume also that
they are the last two upper nodes with negative polarity. Assume now the same
for two lower nodes $y_{1}^{\prime}<y_{2}^{\prime}$.

If we connect $x_{1}$ with $y_{2}^{\prime}$ then it must be the case that
$x_{2}$ has to be connected to $y_{1}^{\prime}$, thus introducing a crossing,
which is forbidden by Theorem 8. Therefore we have that $x_{2}$ must be
connected to $y_{2}^{\prime}$ in $\tau(X)$. We are now in a situation in which
$x_{1}$ and $y_{1}^{\prime}$ are the last nodes that are not connected, and by
the previous argument, they must form an edge in $\tau(X)$.

We can repeat this argument until there are no more edges to connect. Since at
each step there was only one possible connection to make, it implies that
$\tau(X)$ is unique.

∎

######  Corollary 7.

For all minimal factorizations $F$ and $F^{\prime}$ for $X$, the tangles
corresponding to $\tau(F)$ and $\tau(F^{\prime})$ are equal.

The proof for Theorem 9 gives also an idea of how $\tau$ could be computed. We
first start with calculating the node polarity for each node in $X$ from left
to right, but every time we find a node with a certain polarity, say “+”, we
will label that node with $+j$, where $j$ is a counter that keeps track of how
many nodes with polarity “+” we have encountered so far. We can then compute
$\tau(X)$ by adding every edge $e$ in $X$ such that $\\#T(e)\geq|e|$, and then
connecting nodes from top to bottom in $\tau(X)$ if and only if they have the
same node polarity label in $X$ (Algorithm 2). See Figure 14 for an example.
Algorithm 2 has therefore quadratic time complexity because we have to
calculate $\\#T(e)$ for each edge.

Now that we know that $\tau(X)$ is unique, it is not difficult to see that not
only we could count the number of crossings of $\tau(X)$ to find the number of
prime tangles for $X$, but we can also factorize $\tau(X)$ to find the indices
of those primes.

######  Theorem 10.

Given a tangle $X$ with minimal factorization $F_{X}$, then there exists a
minimal factorization $F_{Y}$ for $Y=\tau(X)$ such that $F_{Y}$ has $T$-primes
with the same indices in the same order as in $F_{X}$.

###### Proof.

Since $\tau$ does not change the indices, then this is a direct implication of
the fact that $\tau(X)$ is the tangle we obtain by composing the factors in
$\tau(F_{X})$. This factorization can be found by using Algorithm 4. ∎

(a)

(b)

Figure 14: (a) A tangle $X$ for which we have computed the node polarities
along with one of its minimal factorizations. Note that the edge
$(2,4^{\prime})$ is not considered because
$\\#T(2,4^{\prime})\geq|(2,4^{\prime})|$ and therefore passes through only
$T$-primes and it is not affected by $\tau$, therefore it is present in both
$X$ and $\tau(X)$. (b) The tangle corresponding to $\tau(X)$ and one of it
minimal factorizations. To compute it, add the edge $(2,4^{\prime})$ and
connect from top to bottom the nodes that in $X$ have the same node polarity
label. Note how the indices for both factorizations coincide. Algorithm 2
Compute $\tau(X)$

$X\in\mathcal{B}_{N}$

function $\tau$($X$)

Let $\rho(i)\in\\{+,-\\}$ be the polarity for node $i$ in $X$

$S\leftarrow$ all nodes from $1$ to $N$ connected to edge $e$ s.t.
$\\#T(e)<|e|$

$S^{\prime}\leftarrow$ all nodes from $1^{\prime}$ to $N^{\prime}$ connected
to edge $e$ s.t. $\\#T(e)<|e|$

For $i\in S$, label with “$\rho(i)j$” the $j$th node with polarity $\rho(i)$

For $i^{\prime}\in S^{\prime}$, label with “$\rho(i^{\prime})j$” the $j$th
node with polarity $\rho(i^{\prime})$

$Z\leftarrow$ empty tangle in $\mathcal{B}_{N}$

Add to $Z$ all edges in $X$ s.t. $\\#T(e)\geq|e|$

for nodes $x,y^{\prime}$ s.t. $x$ and $y^{\prime}$ have the same node polarity
label in $X$ do

Add to $Z$ the edge $(x,y^{\prime})$

return $Z$

##  7 Length function

We are now ready to define two length functions for the Brauer monoid. We will
use different subscripts to differentiate between them. The first one,
$\ell_{P}$, is trivially $\ell_{\tau}(X)=\ell(\tau(X))$, where $\ell(\tau(X))$
is just the number of crossings for $\tau(X)$. This function has quadratic
complexity because it has to calculate the node polarity first. But even if
node polarity could be computed faster, Theorem 10 tells us that we can obtain
the indices for a factorization of $X$ by factorizing $\tau(X)$ (which is very
useful information, as we will see in Section 8), and factorizing a tangle in
$S_{N}$ cannot be done faster than $\mathcal{O}(N^{2})$ (see Appendix A).

The second length function is a direct corollary of the fact that
$\\#T(e)\geq|e|\implies\\#U(e)=0$ that we proved in Section 5, because it
implies that $\\#U(e)>0\implies\\#T(e)<|e|$ and therefore
$\\#U(e)>0\implies\\#T(e)+\\#U(e)=|e|$. Let’s define the function $\\#P(e)$ to
be the number of prime tangles the edge $e$ passes through in a factorization
$F$.

Since if $\\#T(e)\geq|e|$ then $e$ passes through only $T$-primes, and
otherwise we have that $\\#T(e)+\\#U(e)=|e|$, we can define $\\#P(e)$ to be:

$\\#P(e)=\left\\{\begin{array}[]{cl}\\#T(e)&:\ \\#T(e)\geq|e|\\\ |e|&:\
otherwise\end{array}\right.=max(\\#T(e),|e|)$

Remember that $\\#T(e)$ is just the number of crossings edge $e$ has (2).
Since now both $\\#T(e)$ and $|e|$ are values that are independent of the
factorization considered, so is $\\#P(e)$. This allows us to use $\\#P(e)$ to
find a length function for the Brauer monoid by just summing crossings and
edge sizes. It is defined as follows:

$\ell_{P}(X)=\frac{1}{2}\sum_{e\in X}\\#P(e)$

Since $\\#P(e)$ counts the number of primes $e$ passes through, we have that
the sum will count every prime twice. We then have to divide by two to obtain
the minimal number of primes for the tangle $X$.

This function still has a quadratic time complexity, but if we assume we
already have calculated $\\#T(e)$ for all $e\in X$, then it can be computed in
linear time (see Section 8). We will use this trick in the following Section
to bring down the time complexity from $\mathcal{O}(N^{5})$ to
$\mathcal{O}(N^{4})$.

##  8 Factorization algorithm

As we have seen in the previous Section, every length function has to be
computed in quadratic time, therefore by Corollary 4 we have that Algorithm 1
runs in $\mathcal{O}(N^{5})$. It turns out however that we can do better.
Instead of calculating $\\#T(e)$ every time we have to compute $\ell_{P}$, we
can store the number of crossings for each edge at the beginning, and then we
can just update them every time we merge a lower hook or compose the tangle
with a $T$-prime. In this way, updating will have linear time complexity and
therefore $\ell_{P}$ will be linear, which brings the overall time complexity
to $\mathcal{O}(N^{4})$.

We update $\\#T(e)$ in different ways depending on if we composed with a
$T$-prime or merged two edges. In the first case, composing with $T_{i}$ will
modify just two edges, i.e. the ones connected to $i$ and $i+1$. In this case,
we just decrease $\\#T$ by one for each of them.

In the second case, let’s say we merged the lower hook $h$ of size one with
the edge $e$. Since we are going to remove them from $X$, we need to decrease
$\\#T$ for all edges that cross with $e$ (no edge will cross with $h$). Then,
after merging $h$ with $e$, two new edges will be in $X$, let’s call them
$e_{1}$ and $e_{2}$. At this point we iterate again through all edges of $X$,
and if another edge $d$ crosses with $e_{1}$, then we increase $\\#T(d)$ and
$\\#T(e_{1})$, we then do the same for $e_{2}$.

In both cases updating $\\#T$ takes at most linear time, therefore $\ell_{P}$
is computable in linear time and we have a $\mathcal{O}(N^{4})$ factorization
algorithm, we just have to compute $\\#T$ once at the beginning (Algorithm 3).
See Figure 15 for an example. A Python implementation can be found at
https://github.com/DanieleMarchei/BrauerMonoidFactorization.

Algorithm 3 $\mathcal{O}(N^{4})$ factorization

$X\in\mathcal{B}_{N}$

function Factorize $\mathcal{B}_{N}$($X$)

Calculate $\\#T(e)$ for all $e\in X$

$I\leftarrow$ factorization indices of $\tau(X)$ $\triangleright$ Algorithm 2
and Algorithm 4

$F\leftarrow$ empty list

for $i\in I$ do

$h\leftarrow(i,i+1)$

if $h\in X$ then

$l\leftarrow\ell_{P}(X)$

for $e\in X:e\neq h,\\#T(e)<|e|$ do

$X^{\prime}\leftarrow X$

for $d\in X^{\prime}:d\neq h,e$ do

if $d$ crosses $e$ then

$\\#T(d)\leftarrow\\#T(d)-1$

Merge $e$ and $h$ in $X^{\prime}$, creating edges $e_{1}$ and $e_{2}$

for $d\in X^{\prime}:d\neq e_{1}$ do

if $d$ crosses $e_{1}$ then

$\\#T(e_{1})\leftarrow\\#T(e_{1})+1$

$\\#T(d)\leftarrow\\#T(d)+1$

for $d\in X^{\prime}:d\neq e_{2}$ do

if $d$ crosses $e_{2}$ then

$\\#T(e_{2})\leftarrow\\#T(e_{2})+1$

$\\#T(d)\leftarrow\\#T(d)+1$

if $\ell_{P}(X^{\prime})=l-1$ then

Append $U_{i}$ to $F$

$X\leftarrow X^{\prime}$

break

else

$X\leftarrow T_{i}\circ X$

Append $T_{i}$ to $F$

Decrease the number of crossings for the two edges connected at $i$ and $i+1$

return $F$

Algorithm 3 could be altered to output a factorization that minimizes the
number of $T$-primes without affecting the time complexity by just keeping
track of the tangle with the least amount of crossings when merging $e$ and
$h$. However, the nested for-loops that search for the edge to merge $h$ with
are still the bottleneck of the algorithm. One way to bring down the
complexity to $\mathcal{O}(N^{3})$ could be finding a constant time decision
algorithm that determines if a particular edge passes through $U_{i}$. In this
way, finding the edges that can be merged would take linear time and hence
reach $\mathcal{O}(N^{3})$. We were not able to find such an algorithm, so we
leave it as a future research direction.

Figure 15: High level illustration for how Algorithm 3 works. On the left, we
have a tangle $X$ from which we have extracted its factorization indices. (a)
The first factor index is 1, therefore we look at upper nodes 1 and 2 of our
tangle and see that they are not connected. We record $T_{1}$ and compute
$T_{1}\circ X$ for the second step. (b) The second index is 2 and the upper
nodes 2 and 3 are connected, therefore we record $U_{2}$. For the next step,
we have to decide which edge we have to merge $(2,3)$ with. We have two
options: $(4,1^{\prime})$ and $(2^{\prime},4^{\prime})$ (edge $(1,3^{\prime})$
satisfies $\\#T(e)\geq|e|$ so it does not pass through a $U$-prime). If we
merge it with $(4,1^{\prime})$ we obtain a tangle with only three factors,
while the other will have four, therefore we select the first one for the next
step. (c) We are in the same situation of step (b) but now we can only merge
$(3,4)$ with $(2^{\prime},4^{\prime})$ and we record $U_{3}$. (d) Same
situation of step (a), we record $T_{1}$. (e) The factor index is 2 and the
upper nodes 2 and 3 are not connected, therefore we record $T_{2}$. (f) We
have reached the identity tangle so we stop the algorithm and output the
factorization $T_{1}\circ U_{2}\circ U_{3}\circ T_{1}\circ T_{2}$, which is
minimal. On the right we have drawn the factors we have found. It is easy to
check that indeed they compose the original tangle $X$.

##  9 Discussion

The Brauer monoid can be factorized in polynomial time, specifically, with a
time complexity of $\mathcal{O}(N^{4})$. To our knowledge, this is the first
polynomial time algorithm proposed to solve this problem. We are not sure if
it has an optimal running time, since there might be some room for
improvements we leave as further research directions. In parallel, we also
found two length functions that can be computed in quadratic time, one of
which can be computed in linear time assuming the crossing numbers are known.

Some proofs for this paper rely on two assumptions we were not able to prove
nor find in the literature, but their validity has been empirically checked
(see Appendix B). We leave their proof as another future research problem.

The factorization problem could also lead to some interesting combinatorial
problems. For example, what is the maximum amount of edges we can merge for a
tangle $X$ with a hook $h$ of size one, such that
$\ell(X)=\ell(X^{\prime})+1$, where $X^{\prime}$ is the tangle obtained after
the merge? This is important to ask because, as we already discussed, finding
the right edge to be merged is the bottleneck of Algorithm 3. By means of
enumeration, we obtained Table 2, and it seems the case that the above
questions is answered by $\lfloor\frac{N}{2}\rfloor$, while the number of
tangles that have that number of merges is much more difficult to count. For
example, the even entries match with the A132911333https://oeis.org/A132911
sequence of the OEIS [15], here we call it $C(k)$:

$C(k)=(k+1)\frac{(2k)!}{2^{k}}$

where $k$ starts from zero. To obtain an exact match with the even entries of
Table 2, we will call them $B(2k)$, we have to modify it as follows:

$B(2k)=C(k-1)=k!|\mathcal{B}_{k-1}|$

where $k$ starts from one.

$N$ | max amount of merges | n. tangles $B(N)$
---|---|---
2 | 1 | 1
3 | 1 | 6
4 | 2 | 2
5 | 2 | 46
6 | 3 | 18
7 | 3 | 900
8 | 4 | 360
9 | 4 | 31320
10 | 5 | 12600
Table 2: The maximum amount of possible merges in $\mathcal{B}_{N}$ and the
number of tangles $X$ with a hook $h$ of size one that can be merged with
other edges such that $\ell(X)=\ell(X^{\prime})+1$, where $X^{\prime}$ is the
tangle obtained after the merge.

Another question could be: how many tangles have length $k$ in
$\mathcal{B}_{N}$? Using the results presented, we enumerated all tangles up
to $\mathcal{B}_{10}$ and obtained Table 3, let’s call it $T(N,k)$. Some clear
pattern emerge, for example $T(N,1)=2(N-1)$ (as expected), or
$T(N,1)=T(N-2,\frac{N(N-1)}{2}-1)$ for $N\geq 5$, but we were unable to find a
general formula.

We don’t have a proof for any of the above statements, nor we have a candidate
formula for the odd entries. We leave these questions open as a further
research direction.

$k$ $N$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
1 |  | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18
2 |  |  | 8 | 20 | 36 | 56 | 80 | 108 | 140 | 176
3 |  |  | 2 | 36 | 102 | 208 | 362 | 572 | 846 | 1192
4 |  |  |  | 30 | 196 | 562 | 1224 | 2294 | 3900 | 6186
5 |  |  |  | 10 | 228 | 1110 | 3192 | 7266 | 14380 | 25870
6 |  |  |  | 2 | 212 | 1650 | 6620 | 18746 | 43764 | 90034
7 |  |  |  |  | 106 | 1966 | 11090 | 40166 | 112250 | 266462
8 |  |  |  |  | 42 | 1914 | 15890 | 73278 | 247494 | 682770
9 |  |  |  |  | 12 | 1440 | 19442 | 116996 | 477830 | 1538840
10 |  |  |  |  | 2 | 830 | 20910 | 166400 | 825422 | 3100160
11 |  |  |  |  |  | 414 | 18798 | 212250 | 1291638 | 5667090
12 |  |  |  |  |  | 162 | 15402 | 244730 | 1853554 | 9514646
13 |  |  |  |  |  | 56 | 10174 | 255188 | 2448214 | 14804426
14 |  |  |  |  |  | 14 | 6154 | 240828 | 3003652 | 21502064
15 |  |  |  |  |  | 2 | 3282 | 207968 | 3411904 | 29298972
16 |  |  |  |  |  |  | 1530 | 161844 | 3627806 | 37604566
17 |  |  |  |  |  |  | 648 | 113490 | 3585522 | 45596280
18 |  |  |  |  |  |  | 234 | 73978 | 3325568 | 52372154
19 |  |  |  |  |  |  | 72 | 44336 | 2856302 | 57069858
20 |  |  |  |  |  |  | 16 | 24354 | 2325126 | 59057576
21 |  |  |  |  |  |  | 2 | 12462 | 1741684 | 58153920
22 |  |  |  |  |  |  |  | 5848 | 1238988 | 54397782
23 |  |  |  |  |  |  |  | 2502 | 830378 | 48420890
24 |  |  |  |  |  |  |  | 972 | 523782 | 41150508
25 |  |  |  |  |  |  |  | 324 | 312886 | 33243338
26 |  |  |  |  |  |  |  | 90 | 176806 | 25585214
27 |  |  |  |  |  |  |  | 18 | 94362 | 18883774
28 |  |  |  |  |  |  |  | 2 | 47280 | 13337554
29 |  |  |  |  |  |  |  |  | 22294 | 9028454
30 |  |  |  |  |  |  |  |  | 9756 | 5856940
31 |  |  |  |  |  |  |  |  | 3908 | 3653772
32 |  |  |  |  |  |  |  |  | 1406 | 2186074
33 |  |  |  |  |  |  |  |  | 434 | 1253770
34 |  |  |  |  |  |  |  |  | 110 | 688446
35 |  |  |  |  |  |  |  |  | 20 | 361372
36 |  |  |  |  |  |  |  |  | 2 | 180488
37 |  |  |  |  |  |  |  |  |  | 85298
38 |  |  |  |  |  |  |  |  |  | 37930
39 |  |  |  |  |  |  |  |  |  | 15636
40 |  |  |  |  |  |  |  |  |  | 5880
41 |  |  |  |  |  |  |  |  |  | 1972
42 |  |  |  |  |  |  |  |  |  | 566
43 |  |  |  |  |  |  |  |  |  | 132
44 |  |  |  |  |  |  |  |  |  | 22
45 |  |  |  |  |  |  |  |  |  | 2
Table 3: The number of tangles in $\mathcal{B}_{N}$ with length $k$.

## Acknowledgements

We would like to thank James East, Matthias Fresacher, Alfilgen Sebandal and
Azeef Parayil Ajmal for their invaluable discussions and suggestions. We would
also like to thank James Mitchell for helping us with the time complexity for
Algorithm 13 of “Computing finite semigroups”.

## References

  * [1] Anders Björner and Francesco Brenti.  Combinatorics of Coxeter groups, volume 231.  Springer, 2005.
  * [2] Richard Brauer.  On algebras which are connected with the semisimple continuous groups.  Annals of Mathematics, pages 857–872, 1937.
  * [3] Manuel Clavel, Francisco Durán, Steven Eker, Santiago Escobar, Patrick Lincoln, Narciso Martı-Oliet, José Meseguer, Rubén Rubio, and Carolyn Talcott.  Maude Manual (Version 3.2.1).  The Maude System (https://maude.cs.illinois.edu/), 2022.
  * [4] Igor Dolinka and James East.  Twisted brauer monoids.  Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 148(4):731–750, 2018.
  * [5] Igor Dolinka, James East, and Robert D Gray.  Motzkin monoids and partial brauer monoids.  Journal of Algebra, 471:251–298, 2017.
  * [6] James East, Attila Egri-Nagy, James D Mitchell, and Yann Péresse.  Computing finite semigroups.  Journal of Symbolic Computation, 92:110–155, 2019.
  * [7] Jeff Erickson.  Algorithms.  Independently published (https://jeffe.cs.illinois.edu/teaching/algorithms/), 2023.
  * [8] Dana C Ernst, Michael G Hastings, and Sarah K Salmon.  Factorization of temperley–lieb diagrams.  Involve, a Journal of Mathematics, 10(1):89–108, 2016.
  * [9] Véronique Froidure and Jean-Eric Pin.  Algorithms for computing finite semigroups.  In Foundations of Computational Mathematics: Selected Papers of a Conference Held at Rio de Janeiro, January 1997, pages 112–126. Springer, 1997\.
  * [10] Louis Kauffman and Yuri Magarshak.  Vassiliev knot invariants and the structure of rna folding.  Knots and Applications, 03 1995.
  * [11] Jon Kleinberg and Eva Tardos.  Algorithm design.  Pearson Education India, 2006.
  * [12] Donald Knuth.  The art of Computer Programming: Volume 3: Sorting and Searching.  Addison-Wesley Professional, 1998.
  * [13] Daniele Marchei and Emanuela Merelli.  Rna secondary structure factorization in prime tangles.  BMC bioinformatics, 23(6):1–18, 2022.
  * [14] Edward F Moore.  The shortest path through a maze.  In Proc. of the International Symposium on the Theory of Switching - Part II, pages 285–292. Harvard University Press, 1959.
  * [15] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2024.  Published electronically at http://oeis.org.
  * [16] Arun Ram.  Characters of brauer’s centralizer algebras.  Pacific journal of Mathematics, 169(1):173–200, 1995.
  * [17] Richard P Stanley.  On the number of reduced decompositions of elements of coxeter groups.  European Journal of Combinatorics, 5(4):359–372, 1984.
  * [18] Harold NV Temperley and Elliott H Lieb.  Relations between the ‘percolation’and ‘colouring’problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the ‘percolation’problem.  Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 322(1549):251–280, 1971.
  * [19] Konrad Zuse.  Plankalkül.  Konrad Zuse Internet Archive (http://zuse.zib.de), 1946.

##  Appendix A Factorization algorithms for submonoids of $\mathcal{B}_{N}$

###  A.1 Factorization of $S_{N}$

Every element in $S_{N}$ can be uniquely described as a permutation of the
string $1,2,\cdots,N$. A simple isomorphism from a string permutation
$s_{1},s_{2},\cdots,s_{N}$ and a tangle in $S_{N}$ is to connect the upper
node $i$ to the lower node $s_{i}^{\prime}$. The identity permutation string
is therefore the one in which every element is in ascending order. In this
context, factorizing a tangle in $S_{N}$ is the same as finding the shortest
sequence of adjacent transpositions (i.e. $s_{i},s_{i+1}\rightarrow
s_{i+1},s_{i}$) such that the original string is reduced to the identity
string. In other words, we have to sort the string. This is a well-known
problem in Computer Science and there are numerous fast algorithms for solving
it. However, due to the constraint of using only adjacent transpositions, we
are bound to a quadratic time complexity since the longest minimal
factorization in $S_{N}$ has size $\frac{N(N-1)}{2}$. One such algorithm is
the BubbleSort [12], which specifically sorts strings using adjacent
transpositions, yielding the shortest possible sequence (see Algorithm 4).

Algorithm 4 Factorization algorithm for any tangle in $S_{N}$.

$X\in S_{N}$

function Factorize $S_{N}$($X$)

$s\leftarrow$ string permutation for $X$

$F\leftarrow$ empty list

for $j\in[N\dots 1]$ do

for $i\in[1\dots j-1]$ do

if $s_{i}>s_{i+1}$ then

Swap $s_{i}$ and $s_{i+1}$

Append $T_{i}$ to $F$

return $F$

###  A.2 Factorization of $\mathcal{T}\mathcal{L}_{N}$

The Temperley-Lieb monoid $\mathcal{T}\mathcal{L}_{N}$ [18] is a submonoid of
$\mathcal{B}_{N}$ in which only $U$-primes are taken as generators. Informally
speaking, $\mathcal{T}\mathcal{L}_{N}$ contains all tangles with no crossings.
A $\Omega(N^{2})$ factorization algorithm was first proposed by Ernst et. al
[8] and in this Section we will give a surface-level explanation of how it
works (see Figure 16).

(a)

(b)

(c)

Figure 16: (a) A tangle in $\mathcal{T}\mathcal{L}_{N}$. Drawing $N$ imaginary
edges $(i,i^{\prime})$ we see that the tangle is now divided into $N-1$
columns and each column is divided into regions, delimited by edges. (b)
Select the regions with odd depth. (c) If two regions are diagonally adjacent,
connect the top one with the bottom one, thus obtaining a Directed Acyclic
Graph. Label each node as $U_{i}$, where $i$ is the index of the columns it is
in. If we read this DAG from top to bottom and from left to right we obtain
the minimal factorization $U_{2}\circ U_{5}\circ U_{1}\circ U_{3}\circ
U_{2}\circ U_{4}\circ U_{3}$.

Given a tangle $X$ in $\mathcal{T}\mathcal{L}_{N}$, divide it into $N-1$
columns by adding a vertical line for each pair $(i,i^{\prime})$. Each column
now will be further divided into different regions delimited by the edges it
contains. Each region has a depth value indicated by how many other regions
there are above it. We will call regions with even depth 0-regions and regions
with odd depth 1-regions. Two regions, $R_{1}$ and $R_{2}$, in the same column
are vertically adjacent if $|depth(R_{1})-depth(R_{2})|=1$. Given two regions
$R_{1}$ and $R_{2}$ in adjacent columns and two points $p_{1}\in R_{1}$ and
$p_{2}\in R_{2}$, if we can draw a straight line between them without crossing
an edge in $X$, then we say that $R_{1}$ and $R_{2}$ are horizontally
adjacent. If there is a region $R^{\prime}$ vertically adjacent to $R_{1}$ and
horizontally adjacent to $R_{2}$, then $R_{1}$ and $R_{2}$ are diagonally
adjacent. We will $R_{1}\rightarrow R_{2}$ in the special case where
$R^{\prime}$ is below $R_{1}$.

Let $\mathfrak{R}$ be the set of all 1-regions. From here we construct a
Directed Acyclic Graph (DAG) $G$ such that every region $R\in\mathfrak{R}$ is
a vertex of $G$ and given two regions $R_{1}$ and $R_{2}$, if
$R_{1}\rightarrow R_{2}$, then $(R_{1},R_{2})$ is an edge of $G$. If a vertex
does not have incoming edges, then we call it a root of $G$. Finally, to
obtain the factorization for $X$ we traverse each vertex from top to bottom
and from left to right, i.e. we list all roots $r_{i},r_{j},\dots,r_{k}$ of
$G$, store $U_{i}\circ U_{j}\circ\cdots\circ U_{k}$ and delete the roots, now
other nodes will not have incoming edges, list them as the new roots
$r_{i}^{\prime},r_{j}^{\prime},\dots,r_{k}^{\prime}$, and so on until $G$ is
empty (Algorithm 5).

Algorithm 5 Factorizes tangle in $\mathcal{T}\mathcal{L}_{N}$

procedure Factorize $\mathcal{T}\mathcal{L}$($X$)

Divide $X$ in columns

$R\leftarrow$ regions of $X$

$\mathfrak{R}\leftarrow$ 1-regions of $R$

$G\leftarrow$ DAG from $\mathfrak{R}$ s.t. if $R_{1}\rightarrow R_{2}$, then
$(R_{1},R_{2})\in G$

$F\leftarrow$ empty list

while $G\neq\emptyset$ do

$S\leftarrow$ roots of $G$

for $s\in S$ do

$i\leftarrow$ column where $s$ lies in

Append $U_{i}$ to $F$

Remove nodes in $S$ from $G$

return $F$

The time complexity of this algorithm is bounded below by $\Omega(N^{2})$
because the number of 1-regions is the same as the number of nodes in $G$,
which is equal to the length of the factorization for the input tangle and, by
Corollary 3, we know it is quadratic. Assuming that retrieving the roots of
$G$ can be done in constant time, the while loop basically enumerates the
nodes of $G$, therefore it does not influence the time complexity. If we
assume that the number of total regions is still quadratic and they could be
enumerated in quadratic time as well, we have that Algorithm 5 has a time
complexity of $\mathcal{O}(N^{2})$.

##  Appendix B Testing the Assumptions

Here we present how methodology for empirically testing 1 and 2. The
interested reader can find the Python code in the GitHub repository
https://github.com/DanieleMarchei/BrauerMonoidFactorization.

###  B.1 Preparation

To test the two assumptions we need a database of minimal factorizations. We
cannot use Algorithm 3, as it would be circular reasoning. This is because its
correctness relies on them being true (it is used in Section 5 to partially
apply $\tau$ and in Section 7 to argue that $\ell_{P}$ is independent of the
factorization). Thus we decided to create this database by exploring the right
Cayley Graph of $\mathcal{B}_{N}$ using a Breadth First Search
(BFS)444According to [7], the BFS algorithm was first proposed in [19] and not
in [14], as it is often attributed. starting from the identity tangle. The BFS
algorithm has the nice property of always returning the shortest path in a
graph (which will be a minimal factorization in our case) and by instructing
it to first explore the edges labelled with a $U$-prime, and then all edges
labelled with a $T$-prime, every time we reach an unexplored tangle we know we
have obtained a minimal factorization that uses the least amount of
$T$-primes. We ran this procedure up to $\mathcal{B}_{8}$.

###  B.2 Assumption 1

1 stated that every factorization in the Brauer monoid can be reduced to a
minimal one by a sequence of “delete”, “braid” and “swap” rules. In other
words, we do not need to increase the factorization length in order to find a
shorter one.

To test this empirically, we implemented the axioms for $\mathcal{B}_{N}$
(Table 1) as a Term Rewriting System (TRS) using the Maude System [3]. The
approach is similar to what described in [13], but to have this paper self-
contained, we will give a high-level illustration of the procedure.

The TRS accepts in input a factorization and iteratively tries to apply as
many “delete” rules it can. Then, it tries to apply “braid” and “swap” rules
non-deterministically until a new delete rule is applicable, and at this point
the TRS starts again with the newly shortened factorization. This reduction
procedure stops when no delete rule is applicable after all move rules have
been applied.

The actual test for the assumption is performed as follows:

  1. 1.

generate a random factorization $F$ with length $|F|\in[2,s\frac{N(N-1)}{2}]$
and compute the corresponding tangle $X\in\mathcal{B}_{N}$;

     * •

if the factorization for $X$ stored in the database has the same length of
$F$, then repeat step 1. We only want to test non-minimal factorizations

  2. 2.

get the minimal factorization $F^{*}$ for $X$ in the database;

  3. 3.

reduce $F$ using the TRS, obtaining $\hat{F}$;

  4. 4.

if $|\hat{F}|\neq|F^{*}|$ we have found a counterexample, otherwise repeat
from step 1.

where $s$ is a scale factor that parametrizes the maximum length possible that
can be generated. To avoid spending too much time on this procedure, we keep
track of the tangles generated, effectively testing the assumption once for
each tangle. Since the probability of generating a tangle we haven’t already
generated decreases each time we find a new one, we implemented a “patience”
counter that is decreased each time we do not generate a new tangle. The
procedure stops when the patience reaches to zero or all tangles are tested.
In our test we set $s=2$ and the patience counter to $2000000$. Because this
procedure takes a long time to terminate, we ran it up to $N=6$ with the
results shown in Table 4. We never found a counterexample.

$N$ | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
$|\mathcal{B}_{N}|$ | 3 | 15 | 105 | 945 | 10395
n. tangles tested | 3 | 15 | 105 | 942 | 10043
Table 4: Test table for 1. We ran the test up to $\mathcal{B}_{6}$ and, among
all tangles tested, we never found a counterexample.

###  B.3 Assumption 2

2 stated that if a tangle $X$ has $k$ crossings, then there exists a minimal
factorization $F$ with exactly $k$ $T$-primes and no other factorization with
fewer $T$-primes exists.

This assumption is easier and faster to check:

  1. 1.

pick a tangle $X$ with minimal factorization $F$ from the database;

     * •

by construction, $F$ will have the minimal amount of $T$-primes.

  2. 2.

count the number of crossings $c$ in $X$;

  3. 3.

if $c\neq\\#T(F)$ then we have found a counterexample, otherwise repeat from
step 1.

We ran this procedure up to $N=8$ and never found a counterexample.