$u_{k}\xrightarrow{d^{\prime}_{k}}u_{k+1}$ for all $k\in[s]$, where
$s=|d^{\prime}|$. Define
$v^{\prime}=(v_{1},\ldots,v_{m},u_{1},\ldots,u_{s},v_{m+1},\ldots,v_{n})$. Let
$k\in\\{1,2,\ldots,|d^{\prime\prime}|\\}$. There are five cases to consider.

  1. –

If $k<m$, then $v^{\prime}_{k}=v_{k}$, $v^{\prime}_{k+1}=v_{k+1}$, and
$d^{\prime\prime}_{k}=\delta_{k}=d_{k}$. Then
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$.

  2. –

If $k=m$, then $v^{\prime}_{k}=v_{m}$, $v^{\prime}_{k+1}=u_{1}=v_{m+1}$, and
$d^{\prime\prime}_{k}=\delta_{k}$. Then
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$.

  3. –

If $m<k<m+s$, then $v^{\prime}_{k}=u_{k-m}$, $v^{\prime}_{k+1}=u_{k-m+1}$, and
$d^{\prime\prime}_{k}=d^{\prime}_{k-m}$. Then
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$.

  4. –

If $k=m+s$, then $v^{\prime}_{k}=u_{s}$, $v^{\prime}_{k+1}=v_{m+1}=u_{s+1}$,
and $d^{\prime\prime}_{k}=d^{\prime}_{s}$. Then
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$.

  5. –

If $k>m+s$, then $v^{\prime}_{k}=u_{k-s}$, $v^{\prime}_{k+1}=u_{k+1-s}$, and
$d^{\prime\prime}_{k}=\delta^{\prime}_{k-m-s}$. Then
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$.

In each case,
$v^{\prime}_{k}\xrightarrow{d^{\prime\prime}_{k}}v^{\prime}_{k+1}$. Since $k$
was arbitrary, then $(\ell,d^{\prime\prime})$ is valid. Then $P[\ell\mapsto
d^{\prime\prime}]$ is a proof by Lemma B.20. ∎

######  Lemma B.22.

Let $P$ be a proof for $\langle\Sigma\mid R\rangle$. If $(\ell,\ell^{\prime})$
is a maximal path rooted at $\ell$ in $\Gamma_{D}(P)$, then there exists a
$\hat{d}\in(L(\Sigma)\cup R)^{*}$ such that $P^{\prime}=P[\ell\mapsto\hat{d}]$
is a proof for $\langle\Sigma\mid R\rangle$ and $\ell$ has one less child in
$\Gamma_{D}(P^{\prime})$.

###### Proof.

Let $f:(L(\Sigma)\cup R)^{*}\to\mathbb{N}$ count the number of occurrences of
$\ell^{\prime}$ in a derivation. Given a proof $Q$ for $\langle\Sigma\mid
R\rangle$, let $C_{Q}:L(\Sigma)\to\mathcal{P}(L)$ map each $\ell\in L(\Sigma)$
to its children in $\Gamma_{D}(Q)$. Since $(\ell,\ell^{\prime})$ is a maximal
path, then $\ell^{\prime}$ has no children in $\Gamma_{D}(P)$. The proof
follows by induction on the number of occurrences of $\ell^{\prime}$ in the
derivation.

  1. –

Base Case. Let $\hat{d}\in(L(\Sigma)\cup R)^{*}$ with
$P^{\prime}=P[\ell\mapsto\hat{d}]$ a proof for $\langle\Sigma\mid R\rangle$
and $C_{P}(\ell)=C_{P^{\prime}}(\ell)\cup\\{\ell^{\prime}\\}$. Assume that
$f(\hat{d})=0$. Then $\hat{d}_{j}\neq\ell^{\prime}$ for all $k\in[n]$, where
$n=|\hat{d}|$. Then $(\ell,\ell^{\prime})\not\in\Gamma_{D}(P^{\prime})$. Then
$\ell^{\prime}\not\in C_{P^{\prime}}(\ell)$. Then
$C_{P^{\prime}}(\ell)=C_{P}(\ell)\setminus\\{\ell^{\prime}\\}$. Since
$\ell^{\prime}\in C_{P}(\ell)$, then $|C_{P^{\prime}}(\ell)|=|C_{P}(\ell)|-1$.

  2. –

Inductive Hypothesis. Let $d^{\prime}\in(L(\Sigma)\cup R)^{*}$ such that
$P^{\prime}=P[\ell\mapsto d^{\prime}]$ a proof for $\langle\Sigma\mid
R\rangle$ and $C_{P}(\ell)=C_{P^{\prime}}(\ell)\cup\\{\ell^{\prime}\\}$.
Assume that for some $k\in\mathbb{N}$, if $f(d^{\prime})=k$, then exists a
$\hat{d}\in(L(\Sigma)\cup R)^{*}$ such that
$P^{\prime\prime}=P[\ell\mapsto\hat{d}]$ is a proof for $\langle\Sigma\mid
R\rangle$ and $|C_{P^{\prime\prime}}(\ell)|=|C_{P}(\ell)|-1$.

  3. –

Inductive Step. Under the conditions of the inductive hypothesis, assume that
$f(d^{\prime})=k+1$. Then there exists some
$\delta,\delta^{\prime}\in(L(\Sigma)\cup R)^{*}$ such that
$d^{\prime}=\delta\cdot\ell^{\prime}\cdot\delta^{\prime}$. Since
$\ell^{\prime}$ is a vertex in $\Gamma_{D}(P)$, then there exists some
$d^{\prime\prime}\in(L(\Sigma)\cup R)^{*}$ such that
$(\ell,d^{\prime\prime})\in P$. Define $\hat{d}=\delta\cdot
d^{\prime\prime}\cdot\delta^{\prime}$. By Lemma B.21,
$P^{\prime\prime}=P[l\mapsto\hat{d}]$ is a proof for $\langle\Sigma\mid
R\rangle$. Let $\ell^{\prime\prime}\in
C_{P}(\ell)\setminus\\{\ell^{\prime}\\}$. Then there exists some
$k\in\\{1,2,\ldots,|\delta|\\}$ such that $d_{k}=\ell^{\prime\prime}$. Since
$\ell^{\prime\prime}\neq\ell$, then without loss of generality $k\leq|\delta|$
and $\hat{d}_{k}=\delta_{k}=\ell^{\prime\prime}$. Then $\ell^{\prime\prime}\in
C_{P^{\prime\prime}}(\ell)$. Since $\ell^{\prime\prime}$ was arbitrary, then
$C_{P}(\ell)\setminus\\{\ell^{\prime}\\}\subseteq C_{P^{\prime\prime}}(\ell)$.
Next, let $\ell^{\prime\prime}\in C_{P^{\prime\prime}}(\ell)$. Then there
exists some $k\in\\{1,2,\ldots,|\hat{d}|\\}$ such that
$\hat{d}_{k}=\ell^{\prime\prime}$. Since $d\in(R^{*})$, then without loss of
generality $k\leq|\delta|$ and $\delta_{k}=\hat{h}_{k}=\ell^{\prime\prime}$.
Then $\ell^{\prime\prime}\in C_{P}(\ell)$. Since $\ell^{\prime\prime}$ was
arbitrary, then $C_{P^{\prime\prime}}(\ell)\subseteq C_{P}(\ell)$. Then
$C_{P}(\ell)=C_{P^{\prime\prime}}(\ell)\cup\\{\ell^{\prime}\\}$. Since
$k+1=f(d^{\prime})=f(\delta)+1+f(\delta^{\prime})$, then
$f(\hat{d})=f(\delta)+f(\delta^{\prime})=k$. Then by the inductive hypothesis,
there exists some $\hat{d}^{\prime}\in(L(\Sigma)\cup R)^{*}$ such that
$Q=P^{\prime}[\ell\mapsto\hat{d}^{\prime}]$ is a proof for $\langle\Sigma\mid
R\rangle$ and $|C_{Q}(\ell)|=|C_{P^{\prime}}(\ell)|-1=|C_{P}(\ell)|-1$. Since
$Q=P[\ell\mapsto\hat{d}^{\prime}]$ by definition, then the inductive step
holds.

It follows by definition that $d\in(L(\Sigma)\cup R)^{*}$ and $P=P[\ell\mapsto
d]$. Then by the principle of induction, there exists a
$\hat{d}\in(L(\Sigma)\cup R)^{*}$ such that $P^{\prime}=P[\ell\mapsto\hat{d}]$
is a proof for $\langle\Sigma\mid R\rangle$ and
$|C_{P^{\prime\prime}}(\ell)|=|C_{P}(\ell)|-1$. ∎

######  Lemma B.23.

Let $P$ be a proof for $\langle\Sigma\mid R\rangle$. If $(\ell,d)\in P$ and
all paths rooted at $\ell$ in $\Gamma_{D}(P)$ have length at most one, then
there exists a $\hat{d}\in R^{*}$ such that $P[\ell\mapsto\hat{d}]$ is a proof
for $\langle\Sigma\mid R\rangle$.

###### Proof.

Let $\Gamma_{D}(P)=(V,E)$. Since $|V|=|P|$ and all paths rooted at $\ell$ have
length at most one, then the number of paths rooted at $\ell$ in
$\Gamma_{D}(P)$ is finite. The proof follows by induction on the number of
paths rooted at $\ell$ in $\Gamma_{D}(P)$.

  1. –

Base Case. Assume that $\Gamma_{D}(P)$ has zero paths rooted at $\ell$. Then
$d\in R^{*}$ by Lemma B.17. Then $P=P[l\mapsto d]$ with $d\in R^{*}$.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if
$\Gamma_{D}(P)$ has $k$ paths rooted at $\ell$, then there exists a
$\hat{d}\in R^{*}$ such that $P[\ell\mapsto\hat{d}]$ is a proof for
$\langle\Sigma\mid R\rangle$.

  3. –

Inductive Step. Assume that $\Gamma_{D}(P)$ has $k+1$ paths rooted at $\ell$.
Then there exists at least one path rooted at $\ell$ in $\Gamma_{D}(P)$. Since
all paths rooted at $\ell$ in $\Gamma_{D}(P)$ have length one, then there
exists some path $(\ell,\ell^{\prime})$ in $\Gamma_{D}(P)$ such that
$\ell^{\prime}$ has no children in $\Gamma_{D}(P)$. Then by Lemma B.22, there
exists some $d^{\prime}\in(L(\Sigma)\cup R)^{*}$ such that
$P^{\prime}=P[\ell\mapsto d^{\prime}]$ is a proof for $\langle\Sigma\mid
R\rangle$ and $\ell$ has $k$ children in $\Gamma_{D}(P^{\prime})$. Since all
paths rooted at $\ell$ have length one, then $\Gamma_{D}(P^{\prime})$ has $k$
paths rooted at $\ell$. Then by the inductive hypothesis, then there exists a
$\hat{d}\in R^{*}$ such that $P[\ell\mapsto\hat{d}]$ is a proof for
$\langle\Sigma\mid R\rangle$. Then the inductive step holds.

Then by the principle of induction, there exists a $\hat{d}\in R^{*}$ such
that $P[\ell\mapsto\hat{d}]$ is a proof for $\langle\Sigma\mid R\rangle$. ∎

######  Lemma B.24.

Let $P$ be a finite proof for $\langle\Sigma\mid R^{\prime}\rangle$ with
$R^{\prime}\subseteq R\subseteq\Sigma^{*}\times\Sigma^{*}$. If $P\models R$
and $\Gamma_{D}(P)$ is acyclic, then there exists a proof $P^{\prime}$ for
$\langle\Sigma\mid R^{\prime}\rangle$ such that $|P^{\prime}|=|P|$,
$P^{\prime}\models R$, and $d\in(R^{\prime})^{*}$ for all $(\ell,d)\in
P^{\prime}$.

###### Proof.

Let $f:L(\Sigma)\times(L(\Sigma)\cup R^{\prime})^{*}\to\mathbb{N}$ count the
number of vertices with children in the derivation graph of a proof. Since
$\Gamma_{D}(P)$ has $|P|$ vertices, then $f(P)\leq|P|$. Since $P$ is finite,
then $f(P)$ is also finite. The proof follows by induction on $f(P)$.

  1. –

Base Case. Assume that $f(P)=0$. Then there are no edges in $\Gamma_{D}(P)$.
Then by Lemma B.18, $d\in(R^{\prime})^{*}$ for all $(\ell,d)\in P$.

  2. –

Inductive Hypothesis Let $Q$ be a proof for $\langle\Sigma\mid
R^{\prime}\rangle$. Assume that for some $k\in\mathbb{N}$, if $f(Q)=k$ with
$P\models R$ and $\Gamma_{D}(Q)$ is acyclic, then there exists a proof
$P^{\prime}$ for $\langle\Sigma\mid R\rangle$ such that $|P^{\prime}|=|Q|$,
$P^{\prime}\models R$, and $d\in(R^{\prime})^{*}$ for all $(\ell,d)\in
P^{\prime}$.

  3. –

Inductive Step. Let $Q$ be a proof for $\langle\Sigma\mid R^{\prime}\rangle$.
Assume that $f(Q)=k+1$ with $Q\models R$ and $\Gamma_{D}(Q)$ acyclic. Since
$f(Q)>0$, then there exists at least one edge $(\ell,\ell^{\prime})$ in
$\Gamma_{D}(Q)$. By Lemma B.1, there exists some path
$(\ell_{0},\ldots,\ell_{n})$ in $\Gamma_{D}(Q)$ such that $\ell_{0}=\ell$
every path rooted at $\ell$ has length at most $n$. Since
$(\ell,\ell^{\prime})$ is a path of length one in $\Gamma_{D}(Q)$ rooted at
$\ell$, then $n\geq 1$. Assume for the intent of contradiction that there
exists a path of length at least $2$ rooted at $\ell_{n-1}$. Then there exists
a path $(\ell_{n-1},x,y)$ in $\Gamma_{D}(Q)$. Then
$(\ell_{0},\ldots,\ell_{n-1},x,y)$ is a path of length $n+1$ in
$\Gamma_{D}(Q)$ rooted at $\ell$. However, all paths rooted at $\ell$ have
length at most $n$. Therefore, all paths rooted at $\ell_{n-1}$ have length at
most one. Since $\ell_{n-1}$ is a vertex in $\Gamma_{D}(Q)$, then there exists
some $d\in(L(\Sigma)\cup R^{\prime})^{*}$ such that $(\ell_{n-1},d)\in Q$.
Then by Lemma B.23, there exists some $d^{\prime}\in(R^{\prime})^{*}$ such
that $P^{\prime}=Q[\ell_{n-1}\mapsto d^{\prime}]$ is a proof for
$\langle\Sigma\mid R^{\prime}\rangle$. Let $(z_{n-1},r_{n-1})=\ell_{n-1}$.
Since $Q\models R$ with respect to $\langle\Sigma\mid R^{\prime}\rangle$, it
follows that $R\subseteq R^{\prime}\cup\\{r\mid((m,r),d)\in P\\}$. Then,

$R\subseteq R^{\prime}\cup\\{r\mid((z,r),d)\in
P\setminus\\{\ell_{n-1},d)\\}\cup\\{r_{n-1}\\}\subseteq
R^{\prime}\cup\\{r\mid((m,r),d)\in P^{\prime}\\}.$

Then $P^{\prime}\models R$ with respect to $\langle\Sigma\mid
R^{\prime}\rangle$. By Lemma B.19, $\Gamma_{D}(P^{\prime})$ is also a subgraph
of $\Gamma_{D}(Q)$ with $f(P^{\prime})=f(Q)-1=k$. Since
$\Gamma_{D}(P^{\prime})$ is a subgraph of $\Gamma_{D}(Q)$ with $\Gamma_{D}(Q)$
acyclic, then $\Gamma_{D}(P^{\prime})$ is also acyclic. Then by the inductive
hypothesis, there exists a proof $P^{\prime\prime}$ for $\langle\Sigma\mid
R\rangle$ such that $|P^{\prime\prime}|=|P^{\prime}|$,
$P^{\prime\prime}\models R$, and $d\in(R^{\prime})^{*}$ for all $(\ell,d)\in
P^{\prime\prime}$. Then $|P^{\prime\prime}|=(|Q|-1)+1=|Q|$, since $Q$ is
indexed. Then the inductive step holds.

Then by the principle of induction, there exists a proof $P^{\prime}$ for
$\langle\Sigma\mid R\rangle$ such that $|P^{\prime}|=|P|$, $P^{\prime}\models
R$, and $d\in(R^{\prime})^{*}$ for all $(\ell,d)\in P$. ∎

######  Theorem B.25.

Let $P$ be a finite proof for $\langle\Sigma\mid R^{\prime}\rangle$ with
$R^{\prime}\subseteq R\subseteq\Sigma^{*}\times\Sigma^{*}$. If $P\models R$
and $\Gamma_{D}(P)$ is acyclic, then there exists a length $|R\setminus
R^{\prime}|$ sequence of Rel($+$) transformations between $\langle\Sigma\mid
R^{\prime}\rangle$ and $\langle\Sigma\mid R\rangle$.

###### Proof.

By Lemma B.24, there exists a proof $P^{\prime}$ for $\langle\Sigma\mid
R^{\prime}\rangle$ with $P^{\prime}\models R$ and $d\in(R^{\prime})^{*}$ for
all $(\ell,d)\in P$. The proof follows by induction on $|R\setminus
R^{\prime}|$.

  1. –

Base Case. If $|R\setminus R^{\prime}|=0$, then $R\subseteq
R^{\prime}\subseteq R$. Then $R=R^{\prime}$ and $\langle\Sigma\mid
R\rangle=\langle\Sigma\mid R^{\prime}\rangle$. Then there exists a length zero
sequence of Rel($+$) transformations between $\langle\Sigma\mid
R^{\prime}\rangle$ and $\langle\Sigma\mid R\rangle$.

  2. –

Inductive Hypothesis. Let $P^{\prime}$ be a proof with respect to
$\langle\Sigma\mid Q\rangle$ with $Q\subseteq R$ and $P^{\prime}\models R$.
Assume that for some $k\in\mathbb{N}$, if $|R\setminus R^{\prime}|=k$, then
there exists a length $k$ sequence of Rel($+$) transformations between
$\langle\Sigma\mid Q\rangle$ and $\langle\Sigma\mid R\rangle$.

  3. –

Inductive Step. Under the conditions of the inductive hypothesis, assume that
$|R\setminus R^{\prime}|=k+1$. Then there exists some $r\in R\setminus
R^{\prime}$, say $(w,w^{\prime})=r$. Since $P^{\prime}\models R$ and $r\not\in
R^{\prime}$, then there exists some $x\in\mathbb{N}$ and $d\in(L(\Sigma)\cup
R^{\prime})^{*}$ such that $((x,r),d)\in P^{\prime}$. Since
$d\in(R^{\prime})^{*}$, then $w\sim_{R^{\prime}}w^{\prime}$ by validity of
$P^{\prime}$. Let $Q=R^{\prime}\cup\\{r\\}$. Then $\langle\Sigma\mid
R^{\prime}\rangle\cong\langle\Sigma\mid Q\rangle$ by Rel($+$). Since
$R^{\prime}\subseteq Q$ and $P^{\prime}\models R$ with respect to
$\langle\Sigma\mid R^{\prime}\rangle$, then

$R\subseteq R^{\prime}\cup\\{r\mid((n,r),d)\in P^{\prime}\\}\subseteq
Q\cup\\{r\mid((n,r),d)\in P^{\prime}\\}.$

Then $P^{\prime}\models R$ with respect to $\langle\Sigma\mid Q\rangle$. Since
$r\in R\setminus R^{\prime}$, then $|R\setminus Q|=|R\setminus
R^{\prime}|-1=k$. Then by the inductive hypothesis, there exists a length $k$
sequence of Rel($+$) transformations between $\langle\Sigma\mid Q\rangle$ and
$\langle\Sigma\mid R\rangle$. Then there exists a length $k+1$ sequence of
Rel($+$) transformations between $\langle\Sigma\mid R^{\prime}\rangle$ and
$\langle\Sigma\mid R\rangle$. Then the inductive step holds.

Then by the principle of induction, there exists a length $|R\setminus
R^{\prime}|$ sequence of Rel($+$) transformations between $\langle\Sigma\mid
R^{\prime}\rangle$ and $\langle\Sigma\mid R\rangle$. ∎

##  Appendix C Circuit Decompositions of Coxeter Generators

In Section 4.1, the Coxeter generator $r_{3}$ was decomposed into a circuit
over $\Sigma_{D}$. In this section, the remaining $7$ Coxeter generators are
decomposed into circuits over $\Sigma_{D}$. Scalar multiples of the normal
vectors are used freely. Recall that ${CC{X}}_{{0},{1}}$ is a reflection about
the normal vector $\ket{\hat{b}}=\ket{1}\otimes\ket{1}\otimes\ket{-}$.
Similarly, ${C{X}}_{{1},{2}}$ is a reflection about the normal vector
$\ket{\overline{b}}=\ket{-}\otimes\ket{1}\otimes\ket{1}$.

  1. $r_{1}$.

This generator is defined by the normal vector
$\ket{b_{1}}=\ket{0}\otimes\ket{0}\otimes\ket{-}$. Since
$({X}_{0}\circ{X}_{1})\ket{\hat{b}}=\ket{b_{1}}$ with
$({X}_{0}\circ{X}_{1})^{-1}={X}_{1}\circ{X}_{0}$, then
$r_{1}={X}_{0}\circ{X}_{1}\circ{CC{X}}_{{0},{1}}\circ{X}_{1}\circ{X}_{0}$.

  2. $r_{2}$.

This generator is defined by the normal vector
$\ket{b_{2}}=\ket{0}\otimes\left(\ket{1}\otimes\ket{0}-\ket{0}\otimes\ket{1}\right)/\sqrt{2}$.
Since $\ket{b_{2}}$ and $-\ket{b_{2}}$ define the same hyperplane, then
$-\ket{b_{2}}$ also defines the same generator. Recall that $r_{3}$ is a
reflection about the normal vector
$\ket{b_{3}}=\ket{0}\otimes\ket{1}\otimes\ket{-}$. Then
$\left({C{X}}_{{2},{1}}\right)\ket{b_{3}}=-\ket{b_{2}}$. Since
${C{X}}_{{2},{1}}$ is self-inverse, then $r_{2}={C{X}}_{{2},{1}}\circ
r_{3}\circ{C{X}}_{{2},{1}}$. Since
$r_{3}={X}_{0}\circ{CC{X}}_{{0},{1}}\circ{X}_{0}$ with ${X}_{0}$ and
${C{X}}_{{2},{1}}$ commuting, then
$r_{2}={X}_{0}\circ{C{X}}_{{2},{1}}\circ{CC{X}}_{{0},{1}}\circ{C{X}}_{{2},{1}}\circ{X}_{0}$.

  3. $r_{4}$.

This generator is defined by the normal vector
$\ket{b_{4}}=\left(\ket{0}\otimes\ket{1}\otimes\ket{1}-\ket{1}\otimes\ket{0}\otimes\ket{0}\right)/\sqrt{2}$.
Since
$\ket{\overline{b}}=\left(\ket{0}\otimes\ket{1}\otimes\ket{1}-\ket{1}\otimes\ket{1}\otimes\ket{1}\right)/\sqrt{2}$,
then
$\left({C{X}}_{{0},{1}}\circ{C{X}}_{{0},{2}}\right)\ket{\overline{b}}=\ket{b_{4}}$.
Furthermore, since
$\left({C{X}}_{{0},{1}}\circ{C{X}}_{{0},{2}}\right)^{-1}={C{X}}_{{0},{2}}\circ{C{X}}_{{0},{1}}$,
then
$r_{4}={C{X}}_{{0},{1}}\circ{C{X}}_{{0},{2}}\circ{CC{X}}_{{1},{2}}\circ{C{X}}_{{0},{2}}\circ{C{X}}_{{0},{1}}$.

  4. $r_{5}$.

This generator is defined by the normal vector
$\ket{b_{5}}=\ket{1}\otimes\ket{0}\otimes\ket{-}$. Since
$({X}_{1})\ket{\hat{b}}=\ket{b_{5}}$ with ${X}_{1}$ self-inverse, then
$r_{5}={X}_{1}\circ{CC{X}}_{{0},{1}}\circ{X}_{1}$.

  5. $r_{6}$.

This generator is defined by the normal vector
$\ket{b_{6}}=\ket{1}\otimes\left(\ket{0}\otimes\ket{1}-\ket{1}\otimes\ket{0}\right)/\sqrt{2}$.
Since $\left({C{X}}_{{2},{1}}\right)\ket{\hat{b}}=\ket{b_{6}}$ with
${C{X}}_{{2},{1}}$ self-inverse, then
$r_{6}={C{X}}_{{2},{1}}\circ{CC{X}}_{{0},{1}}\circ{C{X}}_{{2},{1}}$.

  6. $r_{7}$.

This generator is defined by the normal vector
$\ket{b_{7}}=\ket{1}\otimes\left(\ket{0}\otimes\ket{1}+\ket{1}\otimes\ket{0}\right)/\sqrt{2}$.
Recall that $r_{6}$ is a reflection about the normal vector
$\ket{b_{6}}=\ket{1}\otimes\left(\ket{0}\otimes\ket{1}-\ket{1}\otimes\ket{0}\right)/\sqrt{2}$.
It follows that $\left({C{Z}}_{{0},{1}}\right)\ket{b_{6}}=\ket{b_{7}}$. Since
${C{Z}}_{{0},{1}}$ is self-inverse, then $r_{7}={C{Z}}_{{0},{1}}\circ
r_{6}\circ{C{Z}}_{{0},{1}}$. Furthermore, since
$r_{6}={C{X}}_{{2},{1}}\circ{CC{X}}_{{0},{1}}\circ{C{X}}_{{2},{1}}$, then
$r_{7}={C{Z}}_{{0},{1}}\circ{C{X}}_{{2},{1}}\circ{CC{X}}_{{0},{1}}\circ{C{X}}_{{2},{1}}\circ{C{Z}}_{{0},{1}}$.

  7. $r_{8}$.

The generator is defined by the normal vector
$\ket{b_{8}}=\ket{+}\otimes\ket{+}\otimes\ket{+}$. First, define the operator
$M=K_{1,2}\circ{X}_{1}\circ{X}_{2}\circ{C{Z}}_{{0},{2}}$. Clearly,
$M^{-1}={C{Z}}_{{0},{2}}\circ{X}_{2}\circ{X}_{1}\circ K_{1,2}$. Furthermore,

$M\ket{\overline{b}}=\left(K_{1,2}\circ{X}_{1}\circ{X}_{2}\right)\left(\ket{+}\otimes\ket{1}\otimes\ket{1}\right)=K_{1,2}\left(\ket{+}\otimes\ket{0}\otimes\ket{0}\right)=\ket{b_{8}}.$

Therefore,
$r_{8}=K_{1,2}\circ{X}_{1}\circ{X}_{2}\circ{C{Z}}_{{0},{2}}\circ{CC{X}}_{{1},{2}}\circ{C{Z}}_{{0},{2}}\circ{X}_{2}\circ{X}_{1}\circ
K_{1,2}$.

This establishes all decompositions of the $\Sigma_{E8}$ in terms of
$\Sigma_{D}$.

##  Appendix D Constructing the Generators for $W(E_{8})$

The section walks through the construction of ${X}_{0}$, ${C{X}}_{{0},{1}}$,
${CC{X}}_{{1},{2}}$, and ${K}_{1,2}$ using the Coxeter generators for
$W(E_{8})$. As suggested in Section 4.1, this construction begins by deriving
several diagonal matrices over $(\pm 1)$.

$\displaystyle w_{1}$ $\displaystyle=r_{6}\cdot r_{7}$ $\displaystyle w_{2}$
$\displaystyle=r_{6}\cdot r_{5}\cdot w_{1}\cdot r_{5}\cdot r_{6}$
$\displaystyle w_{3}$ $\displaystyle=r_{5}\cdot r_{4}\cdot w_{2}\cdot
r_{4}\cdot r_{5}$ $\displaystyle w_{4}$ $\displaystyle=r_{4}\cdot r_{3}\cdot
w_{3}\cdot r_{3}\cdot r_{4}$ $\displaystyle w_{5}$ $\displaystyle=r_{3}\cdot
r_{2}\cdot w_{4}\cdot r_{2}\cdot r_{3}$ $\displaystyle w_{6}$
$\displaystyle=r_{2}\cdot r_{1}\cdot w_{5}\cdot r_{1}\cdot r_{2}$

For example, $[\\![w_{1}]\\!]^{*}_{E8}={C{Z}}_{{0},{1}}\circ{C{Z}}_{{0},{2}}$.
It is then possible to derive ${CC{X}}_{{0},{1}}$ and ${X}_{2}$.

$\displaystyle w_{7}$ $\displaystyle=r_{7}\cdot r_{8}\cdot r_{6}\cdot
w_{6}\cdot w_{4}\cdot w_{2}\cdot r_{8}\cdot w_{6}\cdot w_{4}\cdot w_{2}\cdot
r_{6}\cdot r_{8}\cdot r_{7}$ $\displaystyle w_{8}$ $\displaystyle=r_{1}\cdot
r_{3}\cdot r_{5}\cdot w_{7}$

Then $[\\![w_{7}]\\!]^{*}_{E8}={CC{X}}_{{0},{1}}$ and
$[\\![w_{8}]\\!]^{*}_{E8}={X}_{2}$. Using ${CC{X}}_{{0},{1}}$, it is then
possible to derive $K_{1,2}$.

$\displaystyle w_{9}$ $\displaystyle=r_{6}\cdot w_{7}\cdot w_{1}\cdot
w_{7}\cdot r_{6}$ $\displaystyle w_{10}$ $\displaystyle=r_{2}\cdot r_{6}\cdot
w_{5}\cdot w_{3}\cdot w_{2}\cdot r_{8}\cdot w_{9}\cdot r_{8}\cdot w_{5}\cdot
w_{3}\cdot w_{2}\cdot w_{9}$

Then $[\\![w_{9}]\\!]^{*}_{E8}$ is a diagonal matrix over $(\pm 1)$ and
$[\\![w_{10}]\\!]^{*}_{E8}=K_{1,2}$. Next, the permutations are derived.

$\displaystyle w_{11}$ $\displaystyle=w_{10}\cdot r_{4}\cdot w_{8}\cdot
r_{4}\cdot w_{10}\cdot w_{8}$ $\displaystyle w_{12}$ $\displaystyle=r_{2}\cdot
r_{6}$ $\displaystyle w_{13}$ $\displaystyle=w_{11}\cdot w_{12}\cdot w_{11}$

It can be validated that $[\\![w_{11}]\\!]^{*}_{E8}=\sigma_{1,2}$,
$[\\![w_{12}]\\!]^{*}_{E8}=\sigma_{0,1}$, and
$[\\![w_{13}]\\!]^{*}_{E8}=\sigma_{0,2}$. As an immediate consequence,
$[\\![w_{13}\cdot w_{7}\cdot w_{13}]\\!]^{*}_{E8}={CC{X}}_{{1},{2}}$ and
$[\\![w_{13}\cdot w_{8}\cdot w_{13}]\\!]^{*}_{E8}={X}_{0}$. Then by three
applications of Gen($+$), the generators $K_{1,2}$, ${CC{X}}_{{1},{2}}$, and
${X}_{0}$ are introduced, alongside the following relations.

$\displaystyle K_{1,2}$ $\displaystyle\approx w_{10}$
$\displaystyle{CC{X}}_{{1},{2}}$ $\displaystyle\approx w_{13}\cdot w_{7}\cdot
w_{13}$ $\displaystyle{X}_{0}$ $\displaystyle\approx w_{13}\cdot w_{8}\cdot
w_{13}$

Next, define $w_{14}=w_{12}\cdot{X}_{0}\cdot w_{10}\cdot{X}_{0}\cdot w_{12}$.
It can be validated directly that
$[\\![w_{14}]\\!]^{*}_{E8}={C{X}}_{{0},{1}}$. Then by application of Gen($+$),
the generator ${C{X}}_{{0},{1}}$ is introduced, alongside the relation
${C{X}}_{{0},{1}}\approx w_{14}$.

##  Appendix E Establishing the Minimality of $W(E_{8})$ and
$\mathrm{O}(8,\mathbb{D})$ Generators

This section establishes the minimality of certain generating sets for
$W(E_{8})$ and $\mathrm{O}(8,\mathbb{D})$. First, a general result about
minimal generating sets is established. This result is then applied to the
generating sets of interest, to prove their minimality.

###  E.1 Two Results on Minimal Generating Sets

######  Theorem E.1.

Let $G$ be a group with $\Sigma^{\prime}\subseteq\Sigma\subseteq G$. If there
exists a $g\in G$ such that $g$ commutes with the elements of
$\Sigma^{\prime}$ and $g$ does not commute with the elements of $\Sigma$, then
$\langle\Sigma^{\prime}\rangle$ is a proper subgroup of
$\langle\Sigma\rangle$.

###### Proof.

Assume that $g\in G$, $g$ commutes with every element of $\Sigma^{\prime}$,
and $\langle\Sigma^{\prime}\rangle=\langle\Sigma\rangle$. It follows by
induction on the length of an element in $\langle\Sigma^{\prime}\rangle$, that
$g$ commutes with every element in $\langle\Sigma^{\prime}\rangle$. As a base
case, if $h\in\langle\Sigma^{\prime}\rangle$ corresponds to a word of length
$0$, then $h$ is the identity and $g\circ h=g=h\circ g$. As an inductive
hypothesis, assume that for some $n\in\mathbb{N}$, if
$h_{1},h_{2},\ldots,h_{n}\in\Sigma^{\prime}$ and $h=h_{1}\circ
h_{2}\circ\cdots\circ h_{n}$, then $g\circ h=h\circ g$. To show that the
inductive step holds, let $h_{1},h_{2},\ldots,h_{n},h_{n+1}\in\Sigma^{\prime}$
and $h=h_{1}\circ h_{2}\circ\cdots h_{n+1}$. By the inductive hypothesis,
$g\circ h^{\prime}=h^{\prime}\circ g$ where $h^{\prime}=h_{1}\circ
h_{2}\circ\cdots\circ h_{n}$. Then $g\circ h=g\circ h^{\prime}\circ
h_{n+1}=h^{\prime}\circ g\circ h_{n+1}=h^{\prime}\circ h_{n+1}\circ g=h\circ
g$. Then the inductive step holds, and $g$ commutes with every element of
$\langle\Sigma^{\prime}\rangle$. In particular, $g$ commutes with $\Sigma$. By
the contrapositive, if $g$ does not commute with $\Sigma$, then
$\langle\Sigma^{\prime}\rangle\neq\langle\Sigma\rangle$. However,
$\langle\Sigma^{\prime}\rangle\leq\langle\Sigma\rangle$ since
$\Sigma^{\prime}\subseteq\Sigma$. Therefore, $\langle\Sigma^{\prime}\rangle$
is a proper subgroup of $\langle\Sigma\rangle$. ∎

######  Lemma E.2.

Let $G$ be a group with $\Sigma\subseteq G$. If for every maximal proper
subset $\Sigma^{\prime}$ of $\Sigma$, $\langle\Sigma^{\prime}\rangle$ is a
proper subgroup of $\langle\Sigma\rangle$, then $\Sigma$ is a minimal
generating set for $\langle\Sigma\rangle$.

###### Proof.

Let $\Sigma^{\prime}$ be a proper subset of $\Sigma$. Then there exists some
maximal proper subset $\Pi$ of $\Sigma$ such that
$\Sigma^{\prime}\subseteq\Pi\subseteq\Sigma$. Then
$\langle\Sigma^{\prime}\rangle\leq\langle\Pi\rangle\leq\langle\Sigma\rangle$.
Since $\Pi$ is maximal, then by assumption, $\langle\Pi\rangle$ is a proper
subgroup of $\langle\Sigma\rangle$. Consequently,
$\langle\Sigma^{\prime}\rangle$ is a proper subgroup of
$\langle\Sigma\rangle$. Since $\Sigma^{\prime}$ was arbitrary, then $\Sigma$
is a minimal generating set for $\langle\Sigma\rangle$. ∎

###  E.2 Minimality for $W(E_{8})$

It must be shown that for every maximal proper subset $\Sigma^{\prime}$ of
$\Sigma_{0}$, there exists some $8\times 8$ dyadic matrix $M$ such that $M$
commutes with $\Sigma^{\prime}$ but does not commute with $\Sigma_{0}$. The
first three cases can be solved by inspection. In fact, these matrices follow
from well-known circuit relations.

  1. 1.

${Z}_{2}$ commutes with $\\{{X}_{0},{C{X}}_{{0},{1}},{CC{X}}_{{1},{2}}\\}$ but
does not commute with $K_{1,2}$.

  2. 2.

${H}_{2}$ commutes with $\\{{X}_{0},{C{X}}_{{0},{1}},K_{1,2}\\}$ but does not
commute with ${CC{X}}_{{1},{2}}$.

  3. 3.

${X}_{0}$ commutes with $\\{{X}_{0},{CC{X}}_{{1},{2}},K_{1,2}\\}$ but does not
commute with ${C{X}}_{{0},{1}}$.

The final case is less obvious, but can be reduced to solving a linear integer
program. Assume that there exists such a matrix $M$. Since $M$ is dyadic, then
there exists some integer matrix $N$ and integer $k$ such that $M=N/2^{k}$.
Clearly, $M$ and $N$ commute with the same matrices. Then $M$ is characterized
by the following four equations.

$\displaystyle{X}_{0}\circ N$ $\displaystyle\neq N\circ{X}_{0}$
$\displaystyle{C{X}}_{{0},{1}}\circ N$ $\displaystyle=N\circ{C{X}}_{{0},{1}}$
$\displaystyle{CC{X}}_{{1},{2}}\circ N$
$\displaystyle=N\circ{CC{X}}_{{1},{2}}$ $\displaystyle K_{1,2}\circ N$
$\displaystyle=N\circ K_{1,2}$

Without loss of generality, $K_{1,2}$ can be replaced by its integral scalar
multiple $2\cdot K_{1,2}$. Then the entries of $N$ can be thought of as $64$
integer variables, with each equation yielding $64$ linear constraints. Using
Z3 [21] as a solver, the following solution is obtained.

$N_{0,0}=\begin{bmatrix}4&2&2&0\\\ 2&1&1&0\\\ 2&1&1&0\\\
0&0&0&0\end{bmatrix}\qquad N_{0,1}=N_{1,0}=N_{1,1}=\begin{bmatrix}0&0&0&0\\\
0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\end{bmatrix}\qquad
N=\begin{bmatrix}N_{0,0}&M_{0,1}\\\ N_{1,0}&M_{1,1}\end{bmatrix}$

This establishes Theorem 4.4.

###  E.3 Minimality of $\Sigma_{K}$ for $\mathrm{O}(8,\mathbb{D})$

First, it will be shown that $\Sigma_{K}$ is a minimal generating set for
$\mathrm{O}(8,\mathbb{D})$. To see that $\Sigma_{K}$ generates
$\mathrm{O}(8,\mathbb{D})$ simply note that $\Sigma_{K}\cup\\{{K}_{1,2}\\}$
generates $\mathrm{O}(8,\mathbb{D})$ with
${K}_{1,2}={K}{}_{[0,1,2,3]}\circ{X}_{0}\circ{K}{}_{[0,1,2,3]}\circ{X}_{0}$.
It remains to be shown that for every maximal proper subset $\Sigma^{\prime}$
of $\Sigma_{K}$, there exists some $8\times 8$ dyadic matrix $M$ such that $M$
commutes with $\Sigma^{\prime}$ but does not commute with $\Sigma_{K}$. The
first three cases are also solved by inspection, using well-known circuit
relations.

  1. 1.

${Z}_{2}$ commutes with
$\left\\{{X}_{0},{C{X}}_{{0},{1}},{CC{X}}_{{1},{2}}\right\\}$ but does not
commute with ${K}{}_{[0,1,2,3]}$.

  2. 2.

${H}_{2}$ commutes with
$\left\\{{X}_{0},{C{X}}_{{0},{1}},{K}{}_{[0,1,2,3]}\right\\}$ but does not
commute with ${CC{X}}_{{1},{2}}$.

  3. 3.

${X}_{2}\circ{C{Z}}_{{0},{2}}\circ{X}_{2}$ commutes with
$\left\\{{C{X}}_{{0},{1}},{CC{X}}_{{1},{2}},{K}{}_{[0,1,2,3]}\right\\}$ but
does not commute with ${X}_{0}$.

Using Z3 as in the $W(E_{8})$, it is then possible to find an integer matrix
$L$ such that $L$ commutes with
$\left\\{{X}_{0},{CC{X}}_{{1},{2}},{K}{}_{[0,1,2,3]}\right\\}$ but does not
commute with ${C{X}}_{{0},{1}}$. The solution is as follows.

$L_{0}=\begin{bmatrix}1&2&2&0\\\ 2&0&-1&0\\\ 2&-1&0&0\\\ 0&0&0&-3\\\
\end{bmatrix}\qquad L_{1}=\begin{bmatrix}0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{bmatrix}\qquad L=\begin{bmatrix}L_{0}&L_{1}\\\
L_{1}&L_{0}\end{bmatrix}$

This establishes the first claim of Theorem 5.3.

###  E.4 Minimality of $\Sigma_{Z}$ for $\mathrm{O}(8,\mathbb{D})$

The proof the $\Sigma_{Z}$ is minimal proves more challenging. However, the
minimality of $\Sigma_{K}$ can be used to simplify this argument
significantly. Clearly, $\Sigma_{D}=\Sigma_{Z}\setminus\\{CCZ\\}$ does not
generate $\mathrm{O}(8,\mathbb{D})$, since
$\langle\Sigma_{D}\rangle=W(E_{8})<\mathrm{O}(8,\mathbb{D})$. Three of the
remaining four cases can be solved by inspection.

  1. 1.

Recall $N$ from Section E.2. By construction, this matrix commutes with
$\left\\{{C{X}}_{{0},{1}},{CC{X}}_{{1},{2}},{K}_{1,2}\right\\}$ and does not
commute with ${X}_{0}$. Furthermore, $CCZ\circ N=N\circ CCZ$, since the $8$-th
row and $8$-th column of $N$ contain only zeros.

  2. 2.

$\sigma_{1,2}$ commutes with
$\left\\{{X}_{0},{CC{X}}_{{1},{2}},{K}_{1,2},CCZ\right\\}$ but does not
commute with ${C{X}}_{{0},{1}}$.

  3. 3.

${Z}_{2}$ commutes with
$\left\\{{X}_{0},{C{X}}_{{0},{1}},{CC{X}}_{{1},{2}},CCZ\right\\}$ but does not
commute with ${K}_{1,2}$.

The case of ${CC{X}}_{{1},{2}}$ requires more care. There is no obvious
operation which commutes with all generators except for ${CC{X}}_{{1},{2}}$.
Furthermore, Z3 fails to find an solution to the corresponding integer
program. Instead, consider the automorphism $f:M\mapsto{H}_{2}\circ
M\circ{H}_{2}$ of $\mathrm{O}(8,\mathbb{D})$. Since $f$ fixes
$\left\\{{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2,}\right\\}$ and maps $CCZ$ to
${CC{X}}_{{0},{1}}$, then $f$ induces an isomorphism between the subgroups
$\langle{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2},CCZ\rangle$ and
$\langle{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2},{CC{X}}_{{0},{1}}\rangle$ of
$\mathrm{O}(8,\mathbb{D})$. Since ${X}_{0},{C{X}}_{{0},{1}}$,
${K}_{1,2,},{CC{X}}_{{0},{1}}\in W(E_{8})$ with $W(E_{8})$ finite, then

$\left|\langle{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2},CCZ\rangle\right|=\left|\langle{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2},{CC{X}}_{{1},{2}}\rangle\right|\leq|W(E_{8})|<\infty.$

Since $\mathrm{O}(8,\mathbb{D})$ is an infinite group, then
$\langle{X}_{0},{C{X}}_{{0},{1}},{K}_{1,2},CCZ\rangle<\mathrm{O}(8,\mathbb{D})$.
This establishes the second claim of Theorem 5.3.

##  Appendix F Proof Details for a Presentation of $\mathrm{O}(8,\mathbb{D})$

In Section 5, many informal claims were made about the relations in
$\mathcal{G}_{n}$, and the derivations that are possible using these
relations. This section restates each claim as a lemma or theorem, provides a
proof for each claim, and then explains how these claims establish the lemmas
and theorems in Section 5.

###  F.1 Counting the Relations in $\mathcal{R}_{n}$

This section validates the claim that $\mathcal{G}_{8}$ contains $2039$
relations. We say that two relations $(q,r)\in\mathcal{G}_{8}$ and
$(q^{\prime},r^{\prime})\in\mathcal{G}_{8}$ are distinct if $q\neq q^{\prime}$
or $r\neq r^{\prime}$. This means, for example, that the relations
${K}{}_{[0,1,2,3]}\cdot{K}{}_{[4,5,6,7]}\approx{K}{}_{[4,5,6,7]}\cdot{K}{}_{[4,5,6,7]}$
and
${K}{}_{[4,5,6,7]}\cdot{K}{}_{[0,1,2,3]}\approx{K}{}_{[0,1,2,3]}\cdot{K}{}_{[4,5,6,7]}$
are distinct The techniques used in this section can be generalized to count
the number of relations in $\mathcal{G}_{n}$.

First, consider the relations whose parameters are linearly ordered. If a
relation schema $r$ has $m$ linearly ordered parameters, then each choice of
$m$ distinct numbers in $[n]$ corresponds to a unique instance of $r$. It
follows that a relation schema with $m$ linearly ordered parameters
corresponds to $\binom{n}{m}$ unique relations. For each choice of $m$, we
compute $\binom{8}{m}$ and count the number of relations with $m$ linearly
ordered parameters.

  1. –

If $m=1$, then there are $\binom{8}{1}=8$ instances. The only relation with a
single parameter is Relation 48. Then this case contributes $8$ relations.

  2. –

If $m=2$, then there are $\binom{8}{2}=28$ instances. The only relations with
two parameters, all linearly ordered, are Relations 47 and 58. Then this case
contributes $56$ relations.

  3. –

If $m=3$, then there are $\binom{8}{3}=56$ instances. The only relations with
three parameters, all linearly ordered, are Relations 56 and 57. Then this
case contributes $102$ relations.

  4. –

If $m=4$, then there are $\binom{8}{4}=70$ instances. The relations Relations
49, 63, 64 and 65 all have exactly four parameters, which are all linearly
ordered. Then this case contributes $280$ relations.

  5. –

If $m=5$, then there are $\binom{8}{5}=56$ instances. The relations Relations
59, 60, 61 and 62 all have exactly five parameters, which are all linearly
ordered. This this case contributes $224$ relations.

  6. –

If $m=6$, then there are $\binom{8}{6}=28$ instances. The only relation with a
six parameters is Relation 66. Then this case contributes $28$ relations.

  7. –

If $m=8$, then there are $\binom{8}{8}=1$ instances. The only relation with
eight parameters is Relation 67. Then this case contributes $1$ relations.

In total, the relation schemata with linearly ordered parameters contribute
$699$ instances.

The remaining six schemata induce a partial order on the parameters. For
example, in Relation 55, the term ${K}{}_{[a,b,c,d]}\cdot{K}{}_{[e,f,g,h]}$
indicates that $a<b<c<d$ and $e<f<g<h$. However, the choices of $(a,b,c,d)$
are independent from the choices of $(e,f,g,h)$, except that all choices must
be distinct. In this example, there are $\binom{n}{4}$ ways to select the four
indices in the first order. Then $n-m$ indices remain, from which there are
$\binom{n-4}{4}$ choices. In general, for two independent linear orders with
$m$ and $k$ parameters respectively, there will be
$\binom{n}{m}\cdot\binom{n-m}{k}$ choices. The six schemata are described
below.

  1. –

In Relation 54, $m=1$ and $k=1$, resulting in
$\binom{8}{1}\cdot\binom{7}{1}=56$ choices.

  2. –

In Relation 51, $m=1$ and $k=2$, resulting in
$\binom{8}{1}\cdot\binom{7}{2}=168$ choices.

  3. –

In Relation 53, $m=1$ and $k=4$, resulting in
$\binom{8}{1}\cdot\binom{7}{4}=280$ choices.

  4. –

In Relation 50, $m=2$ and $k=2$, resulting in
$\binom{8}{2}\cdot\binom{6}{2}=420$ choices.

  5. –

In Relation 52, $m=2$ and $k=4$, resulting in
$\binom{8}{2}\cdot\binom{6}{4}=420$ choices.

  6. –

In Relation 55, $m=4$ and $k=4$, resulting in
$\binom{8}{4}\cdot\binom{4}{4}=70$ choices

In total, the relations partially ordered parameters contribute $1414$
instances. Then $|\mathcal{R}_{8}|=2113$.

###  F.2 Correctness of Relation Reindexing

This section justifies the reindexing of relations via permutations. First,
recall that every permutation on $[n]$ can be represented by a permutation of
the basis vectors in $\mathbb{R}^{8}$, with $\tau_{a,b}$ corresponding to
${X}{}_{[a,b]}$. The intuition is that every $\sigma$ can be represented by a
word $w$ over generators of type $X$, and that conjugation by $w$ corresponds
to formal reindexing when $\sigma$ is valid.

First, a subset $\mathcal{R}_{n}^{B}$ of $\mathcal{R}_{n}$ is identified, for
which all of the order and braiding relations for generators of type $X$ hold.
Consequently, $\mathcal{R}_{n}^{B}$ is complete for words over generators of
type $X$. Then $\mathcal{R}_{n}^{B}$ is extended to a subset
$\mathcal{R}_{n}^{\sigma}$ of $\mathcal{R}_{n}$ for which all formal
reindexings are derivable. The result is proven first, for individual
generators, and then extended to entire words.

####  F.2.1 Deriving the Braiding Relations

First, define the set of relations,

$\mathcal{R}_{n}^{\tau}=\left\\{{X}{}_{[a,a+1]}{}^{2}\approx\epsilon\mid
a\in\mathbb{Z}\right\\}\cup\left\\{{X}{}_{[a,a+1]}\cdot{X}{}_{[a,b]}\approx{X}{}_{[a+1,b]}\cdot{X}{}_{[a,a+1]}\mid
a,b\in\mathbb{Z}\text{ with }a+1<b\right\\}.$

This set is sufficient to decompose all swaps into transpositions, as proven
in Lemma F.1. Of interest in this section is the following extension of
$\mathcal{R}_{n}^{\tau}$,

$\mathcal{R}_{n}^{B}=\mathcal{R}_{n}^{\tau}\cup\left\\{{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}\approx{X}{}_{[a,a+2]}\cdot{X}{}_{[a+1,a+2]}\mid
a\in\mathbb{Z}\right\\}.$

The relations in $\mathcal{R}_{n}^{B}$ entail the braiding and order relations
for $S(n)$, as shown in Lemma F.2, and are therefore complete for equality of
words over generators of type $X$. Of important note is that
$\mathcal{R}_{n}^{B}\subseteq\mathcal{R}_{n}$.

######  Lemma F.1.

Let $R$ be a set of relations over $\mathcal{G}_{n}$ which contains all well-
formed relations in $\mathcal{R}_{n}^{\tau}$. If $v$ is a word over two-level
operators of type $X$, then there exists a word $u$ over transpositions such
that $v\sim_{R}u$.

###### Proof.

Consider a valid two-level operator ${X}{}_{[a,b]}$. The proof follows by
induction on $b-a>0$.

  1. –

Base Case. If $b-a=1$, then ${X}{}_{[a,b]}={X}{}_{[a,a+1]}$.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}_{>0}$, if $b-a=k$,
then there exists a word $w$

  3. –

Inductive Step. Assume that $b-a=k+1$. Since $k>0$, then $a+1\neq b$, and the
following derivation holds.

${X}{}_{[a,b]}\leftarrow{X}{}_{[a,a+1]}{}^{2}\cdot{X}{}_{[a,b]}\rightarrow{X}{}_{[a,a+1]}\cdot{X}{}_{[a+1,b]}\cdot{X}{}_{[a,a+1]}$

Since $b-(a+1)=k$, then by the inductive hypothesis, there exists a word $w$
over transpositions such that ${X}{}_{[a+1,b]}\sim_{R}w$. Then
${X}{}_{[a,b]}\sim_{R}{X}{}_{[a,a+1]}\cdot w\cdot{X}{}_{[a,a+1]}$. Since
${X}{}_{[a,a+1]}\cdot w\cdot{X}{}_{[a,a+1]}$ is a word over transpositions,
then the inductive hypothesis holds.

Then for each symbol $M$ in $w$, there exists a decomposition of $M$ into
transpositions. Then by Section B.2, there exists a word $v$ over
transpositions such that $w\sim_{R}v$. ∎

######  Lemma F.2.

Let $R$ be a set of relations over $\mathcal{G}_{n}$ which contains all well-
formed relations in $\mathcal{R}_{n}^{B}$. If $v$ and $w$ are words over two-
level operators of type $X$ and $[\\![v]\\!]_{O}^{*}=[\\![w]\\!]_{O}^{*}$,
then $v\sim_{\mathcal{R}_{\sigma}}w$.

###### Proof.

Since $v$ and $w$ are words over two-level operators of type $X$ with
$\mathcal{R}_{n}^{\tau}\subseteq\mathcal{R}_{n}^{B}$, then by Lemma F.1 there
exists words $\hat{v}$ and $\hat{w}$ over transpositions such that
$\hat{v}\sim\hat{w}$. Then $\hat{v}$ and $\hat{w}$ are words in the braid
representation of $\mathrm{S}(n)$. If $R$ contains all order and braiding
relations for the transpositions in $\mathcal{G}_{n}$, then $R$ is complete
for words over the transpositions in $\mathcal{G}_{n}$. Let $a\in[n-2]$. Then
the following derivation holds using the relations in $\mathcal{R}_{n}^{B}$.

$\displaystyle{X}{}_{[a,a+1]}\cdot{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}\leftarrow{X}{}_{[a,a+1]}{}^{2}\cdot{X}{}_{[a,a+2]}\rightarrow{X}{}_{[a,a+2]}\leftarrow{X}{}_{[a,a+2]}\cdot{X}{}_{[a+1,a+2]}{}^{2}\leftarrow{X}{}_{[a+1,a+2]}{}\cdot{X}{}_{[a,a+1]}\cdot{X}{}_{[a+1,a+2]}$

Then
${X}{}_{[a,a+1]}\cdot{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}\sim_{R}{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}\cdot{X}{}_{[a+1,a+2]}$.
Since $a$ was arbitrary, then $R$ is complete for $\mathrm{S}(n)$. Since
$v\sim_{R}\hat{v}$ and $w\sim_{R}\hat{w}$, then
$[\\![v]\\!]_{O}^{*}=[\\![\hat{v}]\\!]_{O}^{*}$ and
$[\\![w]\\!]_{O}^{*}=[\\![\hat{w}]\\!]_{O}^{*}$. Then
$[\\![\hat{v}]\\!]_{O}^{*}=[\\![\hat{w}]\\!]_{O}^{*}$. Then
$\hat{v}\sim_{R}\hat{w}$ by the completeness of $R$. Then $v\sim_{R}w$ by the
transitivity of $(\sim_{R})$. ∎

####  F.2.2 Formal Inverses for Self-Inverse Generators

For each $w=w_{1}\cdot w_{2}\cdots w_{n}$ over $\mathcal{G}_{n}$, define
$\overline{w}=w_{n}\cdots w_{2}\cdot w_{1}$. Since each element in
$\mathcal{G}_{n}$ is self-inverse, then $[\\![\overline{w}]\\!]_{O}^{*}$ is
the inverse of $[\\![w]\\!]_{O}^{*}$ in $\mathrm{O}(8,\mathbb{D})$. One can
prove that given a complete set of relations, both $u\cdot\overline{u}$ and
$\overline{u}\cdot u$ always derive to $\epsilon$. For the purposes of this
proof, only the case for $X$-type generators is necessary.

######  Lemma F.3.

Let $R$ be a set of relations over $\mathcal{G}_{n}$ which contains all well-
formed relations in the set below.

$\displaystyle\left\\{{X}{}_{[a,a+1]}{}^{2}\approx\epsilon\mid
a\in\mathbb{Z}\right\\}\cup\left\\{{X}{}_{[a,a+1]}\cdot{X}{}_{[a,b]}\approx{X}{}_{[a+1,b]}\cdot{X}{}_{[a,a+1]}\mid
a,b\in\mathbb{Z}\right\\}\cup\left\\{{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}\approx{X}{}_{[a,a+@]}\cdot{X}{}_{[a+1,a+2]}\mid
a\in\mathbb{Z}\right\\}$

If $u$ is a word over two-level operators of type $X$, then
$u\cdot\overline{u}\sim_{R}\epsilon$ and $\overline{u}\cdot
u\sim_{R}\epsilon$. Furthermore, if $v$ is a word over two-level operators of
type $X$ and $u\sim_{R}v$, then $\overline{u}\sim_{R}\overline{v}$.

###### Proof.

Since $[\\![\cdot]\\!]_{O}^{*}$ maps each generator in $\mathcal{G}_{n}$ to a
self-inverse matrix, then $[\\![\overline{u}]\\!]_{O}^{*}$ is the inverse to
$[\\![u]\\!]_{O}^{*}$. Then $[\\![\overline{u}\cdot
u]\\!]_{O}^{*}=[\\![\epsilon]\\!]_{O}^{*}=[\\![u\cdot\overline{u}]\\!]_{O}^{*}$.
Since $u$ is a word over two-level operators of type $X$, then
$u\cdot\overline{u}\sim_{R}\epsilon$ and $\overline{u}\cdot u\sim_{R}\epsilon$
by Lemma F.2. Now assume that $v$ is a word over two-level operators of type
$X$ with $u\sim_{R}v$. Then $[\\![u]\\!]_{O}^{*}=[\\![v]\\!]_{O}^{*}$. Since
$\overline{u}$ is the inverse to $u$ and $\overline{v}$ is the inverse to $v$,
then $[\\![\overline{u}]\\!]_{O}^{*}=[\\![\overline{v}]\\!]_{O}^{*}$. Then
$\overline{u}\sim_{R}\overline{v}$ by Lemma F.2. ∎

####  F.2.3 Permuting the Indices in Multi-Level Operators

######  Theorem F.4.

If $\sigma\in\mathrm{S}(n)$ is a valid reindexing for a two-level operator $M$
of type $X$, then there exists a word $v$ over the two-level operators of type
$X$, such that $[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

###### Proof.

Since $M$ is a two-level operator of type $X$, then there exists an increasing
sequence $(a,b)$ over $[n]$ such that $M={X}{}_{[a,b]}$. Let
$\sigma_{1}\circ\sigma_{2}\circ\cdots\circ\sigma_{m}$ be the decomposition of
$\sigma$ into a sequence of transpositions. Then define
$v=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{m}]\\!]_{S}$.
Clearly $v$ is a word over two-level operators of type $X$ satisfying
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. Furthermore,
$[\\![\sigma(M)]\\!]_{O}^{*}=[\\![\tau_{\sigma(a),\sigma(b)}]\\!]_{S}=[\\![\sigma\cdot\tau_{a,b}\cdot\sigma^{-1}]\\!]_{S}^{*}=[\\![v\cdot
M\cdot\overline{v}]\\!]_{O}^{*}$. Since $\sigma(M)$ and $\overline{v}\cdot
M\cdot v$ are words over two-level operators of type $X$, then
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$ by Lemma F.2.
∎

######  Theorem F.5.

If $\sigma\in\mathrm{S}(n)$ and $M$ is a one-level operator of type $(-1)$,
then there exists a word $v$ of transpositions, such that
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

###### Proof.

Since $M$ is a one-level operator of type $(-1)$, then there exists an
$a\in[a]$ such that $M={(-1)}{}_{[a]}$. Let $v$ Let
$\sigma_{1}\circ\sigma_{2}\circ\cdots\circ\sigma_{m}$ be the decomposition of
$\sigma$ into a sequence of transpositions. Then define
$v=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{m}]\\!]_{S}$.
It follows by induction on $m$ that
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

  1. –

Base Case. Assume that $m=0$. Then $v=\overline{v}=\epsilon$ and
$\sigma(M)=M$. Then $\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$ by the reflexivity of $(\sim_{\mathcal{R}_{\sigma}})$.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $m=k$, then
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

  3. –

Inductive Step. Assume that $m=k+1$ and define
$u=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{k}]\\!]_{S}$.
Then by the inductive hypothesis
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}u\cdot\sigma_{m}(M)\cdot\overline{u}$.
Since $\sigma_{m}$ is a transposition, then there exists some $j\in[n-1]$ such
that $\sigma_{m}=\tau_{j,j+1}$. Furthermore,
$[\\![\sigma_{m}]\\!]_{S}={X}{}_{[j,j+1]}$. If $j=a$, then
$\sigma_{m}(M)={(-1)}{}_{[a+1]}$ then the following derivation holds using
only Relations 47 and 58.

${(-1)}{}_{[a+1]}\leftarrow{(-1)}{}_{[a+1]}\cdot{X}{}_{[j,j+1]}{}^{2}\leftarrow{X}{}_{[j,j+1]}\cdot{(-1)}{}_{[a]}\cdot{X}{}_{[j+1]}$

The case when $j+1=a$ follows symmetrically. When $j\neq a$ and $j+1\neq a$,
then $\sigma_{m}(M)=M$ and the following derivation holds using only Relations
47 and 51.

${(-1)}{}_{[a]}\leftarrow{(-1)}{}_{[a]}\cdot{X}{}_{[j,j+1]}{}^{2}\leftarrow{X}{}_{[j,j+1]}\cdot{(-1)}{}_{[a]}\cdot{X}{}_{[j+1]}$

In either case,
$\sigma_{m}(M)\sim_{\mathcal{R}_{\sigma}}[\\![\sigma_{m}]\\!]_{S}\cdot
M\cdot[\\![\sigma_{m}]\\!]_{S}$. Then
$\sigma_{m}(M)\sim_{\mathcal{R}_{\sigma}}u\cdot\sigma_{m}(M)\cdot\overline{u}\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$ and the inductive step is established.

Then by the principle of induction,
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$. Clearly
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. ∎

######  Lemma F.6.

For each four-level operator $M$ of type $K$, there exists a valid reindexing
$\sigma$ for $M$ and a word $v$ over two-level operators of type $X$, such
that $[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
${K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

###### Proof.

Since $M$ is a four-level operator of type $K$, then there exists an
increasing sequence $(a_{0},a_{1},a_{2},a_{3})$ over $[n]$ such that
$M={(-1)}{}_{[a_{0},a_{1},a_{2},a_{3}]}$. Since $(a_{0},a_{1},a_{3},a_{4})$ is
increasing, then $k\leq a_{k}$ for $k\in[4]$. Then for each $k\in[4]$, define
$\sigma_{k}$ to be $\tau_{k,a_{k}}$ if $k\neq a_{k}$, or identity otherwise.
Then the following equations hold.

$\displaystyle\sigma_{0}(M)$ $\displaystyle={(-1)}{}_{[0,a_{1},a_{2},a_{3}]}$
$\displaystyle\sigma_{1}(\sigma_{0}(M))$
$\displaystyle={(-1)}{}_{[0,1,a_{2},a_{3}]}$
$\displaystyle\sigma_{2}(\sigma_{1}(\sigma_{0}(M)))$
$\displaystyle={(-1)}{}_{[0,1,2,a_{3}]}$
$\displaystyle\sigma_{3}(\sigma_{2}(\sigma_{1}(\sigma_{0}(M))))$
$\displaystyle={(-1)}{}_{[0,1,2,3]}$

Let
$v=[\\![\sigma_{3}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdot[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{0}]\\!]_{S}$.
Then the following derivations hold by Relations 47, 59, 60, 61 and 62. We
assume that each $\sigma_{k}$ is not the identity, else the derivation is
trivial.

$\displaystyle\sigma_{0}(M)$
$\displaystyle\leftarrow{X}{}_{[0,a_{0}]}{}^{2}\cdot{K}{}_{[0,a_{1},a_{2},a_{3}]}\rightarrow{X}{}_{[0,a_{0}]}\cdot{K}{}_{[a_{0},a_{1},a_{2},a_{3}]}\cdot{X}{}_{[0,a_{0}]}$
$\displaystyle\sigma_{1}(\sigma_{0}(M))$
$\displaystyle\leftarrow{X}{}_{[1,a_{1}]}{}^{2}\cdot{K}{}_{[0,1,a_{2},a_{3}]}\rightarrow{X}{}_{[1,a_{1}]}\cdot{K}{}_{[0,a_{1},a_{2},a_{3}]}\cdot{X}{}_{[1,a_{1}]}={X}{}_{[1,a_{1}]}\cdot\sigma_{0}(M)\cdot{X}{}_{[1,a_{1}]}$
$\displaystyle\sigma_{2}(\sigma_{1}(\sigma_{0}(M)))$
$\displaystyle\leftarrow{X}{}_{[2,a_{2}]}{}^{2}\cdot{K}{}_{[0,1,2,a_{3}]}\rightarrow{X}{}_{[2,a_{2}]}\cdot{K}{}_{[0,1,a_{2},a_{3}]}\cdot{X}{}_{[2,a_{2}]}={X}{}_{[2,a_{2}]}\cdot\sigma_{1}(\sigma_{0}(M))\cdot{X}{}_{[2,a_{2}]}$
$\displaystyle\sigma_{3}(\sigma_{2}(\sigma_{1}(\sigma_{0}(M))))$
$\displaystyle\leftarrow{X}{}_{[3,a_{3}]}{}^{2}\cdot{K}{}_{[0,1,2,3]}\rightarrow{X}{}_{[3,a_{3}]}\cdot{K}{}_{[0,1,2,a_{3}]}\cdot{X}{}_{[3,a_{3}]}={X}{}_{[3,a_{3}]}\cdot\sigma_{1}(\sigma_{0}(M))\cdot{X}{}_{[3,a_{3}]}$

It follows that $\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$ where
$\sigma=\sigma_{3}\cdot\sigma_{2}\cdot\sigma_{1}\cdot\sigma_{0}$. Clearly
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. ∎

######  Lemma F.7.

Let $M={K}{}_{[0,1,2,3]}$ be a four-level operator of dimension $n$. For any
increasing sequence $(a_{0},a_{1},a_{2},a_{3})$ over $[n]$, there exists a
valid reindexing $\sigma$ for $M$ and a word $v$ over two-level operators of
type $X$, such that $\sigma(M)={K}{}_{[a_{0},a_{1},a_{2},a_{3}]}$,
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$, and
${K}{}_{[a_{0},a_{1},a_{2},a_{3}]}\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$.

###### Proof.

Since $(a_{0},a_{1},a_{3},a_{4})$ is increasing, then $k\leq a_{k}$ for
$k\in[4]$. Then for each $k\in[4]$, define $\sigma_{k}$ to be $\tau_{k,a_{k}}$
if $k\neq a_{k}$, or identity otherwise. Then the following equations hold.

$\displaystyle\sigma_{3}(M)$ $\displaystyle={(-1)}{}_{[0,1,2,a_{3}]}$
$\displaystyle\sigma_{2}(\sigma_{3}(M))$
$\displaystyle={(-1)}{}_{[0,1,a_{2},a_{3}]}$
$\displaystyle\sigma_{1}(\sigma_{2}(\sigma_{3}(M)))$
$\displaystyle={(-1)}{}_{[0,a_{1},a_{2},a_{3}]}$
$\displaystyle\sigma_{0}(\sigma_{1}(\sigma_{2}(\sigma_{3}(M))))$
$\displaystyle={(-1)}{}_{[a_{0},a_{2},a_{3},a_{4}]}$

Let
$v=[\\![\sigma_{0}]\\!]_{S}\cdot[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdot[\\![\sigma_{3}]\\!]_{S}$.
Then the following derivations hold by Relations 47, 59, 60, 61 and 62. We
assume that each $\sigma_{k}$ is not the identity, else the derivation is
trivial.

$\displaystyle\sigma_{3}(M)$
$\displaystyle\leftarrow{K}{}_{[0,1,2,3]}\cdot{X}{}_{[3,a_{3}]}{}^{2}\leftarrow{X}{}_{[3,a_{3}]}\cdot{K}{}_{[0,1,2,a_{3}]}\cdot{X}{}_{[3,a_{3}]}$
$\displaystyle\sigma_{2}(\sigma_{3}(M))$
$\displaystyle\leftarrow{K}{}_{[0,1,a_{2},a_{3}]}\cdot{X}{}_{[2,a_{2}]}{}^{2}\leftarrow{X}{}_{[2,a_{2}]}\cdot{K}{}_{[0,1,2,a_{3}]}\cdot{X}{}_{[2,a_{2}]}={X}{}_{[2,a_{2}]}\cdot\sigma_{3}(M)\cdot{X}{}_{[2,a_{2}]}$
$\displaystyle\sigma_{1}(\sigma_{2}(\sigma_{3}(M)))$
$\displaystyle\leftarrow{K}{}_{[0,a_{1},a_{2},a_{3}]}\cdot{X}{}_{[1,a_{1}]}{}^{2}\leftarrow{X}{}_{[1,a_{1}]}\cdot{K}{}_{[0,1,a_{2},a_{3}]}\cdot{X}{}_{[1,a_{1}]}={X}{}_{[1,a_{1}]}\cdot\sigma_{2}(\sigma_{3}(M))\cdot{X}{}_{[1,a_{1}]}$
$\displaystyle\sigma_{0}(\sigma_{1}(\sigma_{2}(\sigma_{3}(M))))$
$\displaystyle\leftarrow{K}{}_{[a_{0},a_{1},a_{2},a_{3}]}\cdot{X}{}_{[0,a_{0}]}{}^{2}\leftarrow{X}{}_{[0,a_{0}]}\cdot{K}{}_{[0,a_{1},a_{2},a_{3}]}\cdot{X}{}_{[0,a_{0}]}={X}{}_{[0,a_{0}]}\cdot\sigma_{1}(\sigma_{2}(\sigma_{3}(M)))\cdot{X}{}_{[0,a_{0}]}$

It follows that $\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$ where
$\sigma=\sigma_{0}\cdot\sigma_{1}\cdot\sigma_{2}\cdot\sigma_{3}$. Clearly
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. ∎

######  Lemma F.8.

If $\sigma\in\mathrm{S}(n)$ is a valid reindexing for a four-level operator
$M$ of type $K$ and $\sigma(M)=M$, then there exists a word $v$ over the two-
level operators of type $X$, such that
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
$M\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

###### Proof.

Since $M$ is a four-level operator of type $K$, then there exists an
increasing sequence $(a,b,c,d)$ over $[n]$ such that $M={(-1)}{}_{[a,b,c,d]}$.
Since $\sigma(M)=M$, then $\sigma$ fixes $\\{a,b,c,d\\}$. Then $\sigma$
restricts to a permutation on $[n]\setminus\\{a,b,c,d\\}$. Decompose this
restriction of $\sigma$ into a sequence of transpositions
$\sigma_{1}\circ\sigma_{2}\circ\cdots\circ\sigma_{m}$ on
$[n]\setminus\\{a,b,c,d\\}$. Since $\sigma$ fixes $\\{a,b,c,d\\}$, then
$\sigma=\sigma_{1}\circ\sigma_{2}\circ\cdots\circ\sigma_{m}$ when viewing each
$\sigma_{j}$ as a permutation on $[n]$. Define
$v=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{m}]\\!]_{S}$.
It follows by induction on $m$ that $M\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$.

  1. –

Base Case. If $m=0$, then $v=\overline{v}=\epsilon$. Then
$M\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$ by the reflexivity of
$(\sim_{\mathcal{R}_{\sigma}})$.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $m=k$, then
$M\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

  3. –

Inductive Step. Assume that $m=k+1$ and define
$u=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{k}]\\!]_{S}$.
Then by the inductive hypothesis $M\sim_{\mathcal{R}_{\sigma}}u\cdot
M\cdot\overline{u}$. Since $\sigma_{m}$ is a transposition of elements in
$[n]\setminus\\{a,b,c,d\\}$, then there exists some
$j,l\in[n]\setminus\\{a,b,c,d\\}$ such that $\sigma_{m}=\tau_{j,l}$.
Furthermore, $[\\![\sigma_{m}]\\!]_{S}={X}{}_{[j,l]}$. Since
$j,l\not\in\\{a,b,c,d\\}$, then the following derivation holds by Relations 47
and 52.

${K}{}_{[a,b,c,d]}\leftarrow{X}{}_{[j,k]}^{2}\cdot{K}{}_{[a,b,c,d]}\rightarrow{X}{}_{[j,l]}\cdot{K}{}_{[a,b,c,d]}\cdot{X}{}_{[j,l]}$

Then $M\sim_{\mathcal{R}_{\sigma}}[\\![\sigma_{m}]\\!]_{S}\cdot
M\cdot[\\![\sigma_{m}]\\!]_{S}$. Then $M\ \sim_{\mathcal{R}_{\sigma}}u\cdot
M\cdot\overline{u}\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

Then by the principle of induction, $M\sim_{\mathcal{R}_{\sigma}}v\cdot
M\cdot\overline{v}$. Clearly $[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. ∎

######  Theorem F.9.

If $\sigma\in\mathrm{S}(n)$ is a valid reindexing for a four-level operator
$M$ of type $K$, then there exists a word $v$ over the two-level operators of
type $X$, such that $[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$.

###### Proof.

Since $M$ is a four-level operator of type $K$, then there exists an
increasing sequence $(a_{0},a_{1},a_{2},a_{3})$ over $[n]$ such that
$M={(-1)}{}_{[a_{0},a_{1},a_{2},a_{3}]}$. By Lemma F.6, there exists a word
$u$ over two-level operators of type $X$, and a permutation $\sigma_{1}$ such
that $\sigma_{1}(M)={(-1)}{}_{[0,1,2,3]}$,
$[\\![\sigma_{1}]\\!]_{S}=[\\![u]\\!]_{S}^{*}$, and
$\sigma_{1}(M)\sim_{\mathcal{R}_{\sigma}}u\cdot M\cdot\overline{u}$. By Lemma
F.7, there exists a word $v$ over two-level operators of type $X$, and a
permutation $\sigma_{2}$ such that
$\sigma_{2}(\sigma_{1}(M))={(-1)}{}_{[\sigma(a),\sigma(b),\sigma(b),\sigma(c)]}=\sigma(M)$,
$[\\![\sigma_{2}]\\!]_{S}=[\\![v]\\!]_{S}^{*}$, and
$\sigma_{2}(\sigma_{1}(M))\sim_{\mathcal{R}_{\sigma}}v\cdot\sigma_{1}(M)\cdot\overline{v}$.
Then define $\sigma_{3}=\sigma\circ\sigma_{1}^{-1}\circ\sigma_{2}^{-1}$. Then
$\sigma_{3}(\sigma(a_{k}))=\sigma(\sigma_{1}^{-1}(\sigma_{2}^{-1}(\sigma(a_{k}))))=\sigma(\sigma_{1}^{-1}(k))=\sigma(a_{k})$
for all $k\in[4]$. Then $\sigma_{3}$ is a valid reindexing for $M$ with
$\sigma_{3}(\sigma_{2}(\sigma_{1}(M)))=M$. By Lemma F.8, there exists a word
$w$ over two-level operators of type $X$, such that
$[\\![\sigma_{3}]\\!]_{S}=[\\![w]\\!]_{S}^{*}$ and
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}w\cdot\sigma_{2}(\sigma_{1}(M))\cdot\overline{w}$.
It follows that
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}w\cdot\sigma_{2}(\sigma_{1}(M))\overline{w}\sim_{\mathcal{R}_{\sigma}}w\cdot
u\cdot\sigma_{1}(M)\cdot\overline{w\cdot u}\sim_{\mathcal{R}_{\sigma}}w\cdot
u\cdot v\cdot M\cdot\overline{w\cdot u\cdot v}$. Moreover, $[\\![w\cdot u\cdot
v]\\!]_{O}^{*}=[\\![w]\\!]_{O}^{*}\circ[\\![u]\\!]_{O}^{*}\circ[\\![v]\\!]=[\\![\sigma_{3}]\\!]_{S}\circ[\\![\sigma_{2}]\\!]_{S}\circ[\\![\sigma_{1}]\\!]_{S}=[\\![\sigma]\\!]_{S}$.
∎

####  F.2.4 Permuting the Indices in Relations Over Multi-Level Operators

######  Theorem F.10.

For each $\sigma\in\mathrm{S}(n)$, there exits a set of words $L_{\sigma}$
with the following properties.

  1. 1.

If $v_{1}\in L_{\sigma}$ and $v_{2}\in L_{\sigma}$, then
$v_{1}\sim_{\mathcal{R}_{\sigma}}v_{2}$.

  2. 2.

If $\sigma$ is a valid reindexing for $w$, then there exists a $v\in
L_{\sigma}$ such that $\sigma(w)\sim_{\mathcal{G}_{\sigma}}v\cdot
w\cdot\overline{v}$.

###### Proof.

Let $L_{\sigma}$ be the set of all words $v$ over the two-level operators of
type $X$, such that $[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$. Let $v_{1}\in
L_{\sigma}$ and $v_{2}\in L_{\sigma}$. Then
$[\\![v_{1}]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}=[\\![v_{2}]\\!]_{O}^{*}$. Then
$v_{1}\sim_{\mathcal{G}_{\sigma}}v_{2}$. Since $v_{1}$ and $v_{2}$ were
arbitrary, then Property (1) holds. Now assume that $\sigma$ is a valid
reindexing for $w$. Property (2) follows by induction on the length of $w$.

  1. –

Base Case. If $|w|=0$, then $\sigma(w)=w$. Let
$\sigma_{1}\circ\sigma_{2}\circ\cdots\circ\sigma_{m}$ be a decomposition of
$\sigma$ into transpositions. Define
$v=[\\![\sigma_{1}]\\!]_{S}\cdot[\\![\sigma_{2}]\\!]_{S}\cdots[\\![\sigma_{m}]\\!]$.
Then $[\\![\overline{v}]\\!]_{O}^{*}=[\\![\sigma^{-1}]\\!]_{S}$ since
$\overline{v}$ is the inverse to $v$. Since $v\cdot w\cdot\overline{v}$, then
$\sigma(w)\sim_{\mathcal{R}_{\sigma}}v\cdot w\cdot\overline{v}$ by Lemma F.3.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $|w|=k$, then
there exists a $v\in L_{\sigma}$ such that
$\sigma(w)\sim_{\mathcal{G}_{\sigma}}v\cdot w\cdot\overline{v}$.

  3. –

Inductive Step. Assume that $|w|=k+1$. Then there exists some word $\hat{w}$
over $\mathcal{G}_{n}$ and some $M\in\mathcal{G}_{n}$ such that
$w=\hat{w}\cdot M$ with $|\hat{w}|=k$. Clearly, $M$ is either of type $X$,
type $(-1)$, or type $K$. In any case, there exists a word $v$ over the two-
level operators of type $X$ such that
$[\\![v]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}$ and
$\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot M\cdot\overline{v}$. Then $v\in
L_{\sigma}$. By the inductive hypothesis, there exists a $u\in L_{\sigma}$
such that
$\sigma(\hat{w})\sim_{\mathcal{R}_{\sigma}}u\cdot\hat{w}\cdot\overline{u}$.
Since $u\in L_{\sigma}$ and $v\in L_{\sigma}$, then
$u\sim_{\mathcal{R}_{\sigma}}v$ by Property (1). Furthermore
$\overline{v}\cdot v\sim_{\mathcal{R}_{\sigma}}\epsilon$ by Lemma F.3. Then
$\overline{v}\cdot u\sim_{\mathcal{R}_{\sigma}}\overline{v}\cdot
v\sim_{\mathcal{R}_{\sigma}}\epsilon$. Since
$\sigma(w)=\sigma(\hat{w})\cdot\sigma(M)$, then it follows
$\sigma(w)\sim_{\mathcal{R}_{\sigma}}v\cdot\hat{w}\cdot\overline{v}\cdot\sigma(M)\sim_{\mathcal{R}_{\sigma}}v\cdot\hat{w}\cdot\overline{v}\cdot
u\cdot M\cdot\overline{u}\sim_{\mathcal{R}_{\sigma}}v\cdot\hat{w}\cdot
M\cdot\overline{u}\sim_{\mathcal{R}_{\sigma}}u\cdot w\cdot\overline{u}$ and
the inductive step is established.

Then by the principle of induction, Property (2) holds. ∎

######  Corollary F.11.

Let $v$ and $w$ be words over $\mathcal{G}_{n}$. If $\sigma$ is a valid
reindexing for $u$ and $w$, then $\sigma(w)$ is derivable from $\sigma(u)$
using $\mathcal{R}_{\sigma}\cup\\{u\approx w\\}$.

###### Proof.

Let $Q=\mathcal{R}_{\sigma}\cup\\{u\approx w\\}$. By Theorem F.10, there
exists words $v_{1}$ and $v_{2}$ over two-level operators of type $X$, such
that $v_{1}\sim_{Q}v_{2}$, $\sigma(u)\sim_{Q}v_{1}\cdot
u\cdot\overline{v}_{1}$ and $\sigma(w)\sim_{Q}v_{2}\cdot
w\cdot\overline{v}_{2}$. Since $v_{1}\sim_{Q}v_{2}$, then
$[\\![v_{1}]\\!]_{O}^{*}=[\\![v_{2}]\\!]_{O}^{*}$. Then
$[\\![\overline{v}_{1}]\\!]_{O}^{*}=[\\![\overline{v}_{2}]\\!]_{O}^{*}$. Since
$\overline{v}_{1}$ and $\overline{v}_{2}$ are words over two-level operators
of type $X$, then $\overline{v}_{1}\sim_{Q}\overline{v}_{2}$ by Lemma F.2.
Then the following derivation holds over $Q$.

$\displaystyle\sigma(u)\rightarrow v_{1}\cdot
u\cdot\overline{v}_{1}\rightarrow v_{2}\cdot u\cdot\overline{v}_{1}\rightarrow
v_{2}\cdot w\cdot\overline{v}_{1}\rightarrow v_{2}\cdot
w\cdot\overline{v}_{2}\rightarrow\sigma(w)$

Then $\sigma(w)$ is derivable from $\sigma(w)$ using $Q$. ∎

###  F.3 The Set of Representative Relations

$\displaystyle{X}{}_{[a,b]}{}^{2}$ $\displaystyle\,\approx\,\epsilon$ (109)
$\displaystyle{(-1)}{}_{[0]}{}^{2}$ $\displaystyle\,\approx\,\epsilon$ (110)
$\displaystyle{K}{}_{[0,1,2,3]}{}^{2}$ $\displaystyle\,\approx\,\epsilon$
(111) $\displaystyle{X}{}_{[a,b]}\cdot{X}{}_{[c,d]}$
$\displaystyle\,\approx\,{X}{}_{[c,d]}\cdot{X}{}_{[a,b]}$ (112)
$\displaystyle{X}{}_{[a,b]}\cdot{(-1)}{}_{[c]}$
$\displaystyle\,\approx\,{(-1)}{}_{[c]}\cdot{X}{}_{[a,b]}$ (113)
$\displaystyle{X}{}_{[a,b]}\cdot{K}{}_{[c,d,e,f]}$
$\displaystyle\,\approx\,{K}{}_{[c,d,e,f]}\cdot{X}{}_{[a,b]}$ (114)
$\displaystyle{(-1)}{}_{[4]}\cdot{K}{}_{[0,1,2,3]}$
$\displaystyle\,\approx\,{K}{}_{[0,1,2,3]}\cdot{(-1)}{}_{[4]}$ (115)
$\displaystyle{(-1)}{}_{[0]}\cdot{(-1)}{}_{[4]}$
$\displaystyle\,\approx\,{(-1)}{}_{[4]}\cdot{(-1)}{}_{[0]}$ (116)
$\displaystyle{K}{}_{[0,1,2,3]}\cdot{K}{}_{[4,5,6,7]}$
$\displaystyle\,\approx\,{K}{}_{[4,5,6,7]}\cdot{K}{}_{[0,1,2,3]}$ (117)
$\displaystyle{X}{}_{[a,a+2]}\cdot{X}{}_{[a,a+1]}$
$\displaystyle\,\approx\,{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+2]}$ (118)

$\displaystyle{X}{}_{[a+1,a+2]}\cdot{X}{}_{[a,a+1]}$
$\displaystyle\,\approx\,{X}{}_{[a,a+2]}\cdot{X}{}_{[a+1,a+2]}$ (119)
$\displaystyle{X}{}_{[a,b]}\cdot{(-1)}{}_{[a]}$
$\displaystyle\,\approx\,{(-1)}{}_{[b]}\cdot{X}{}_{[a,b]}$ (120)
$\displaystyle{X}{}_{[a,e]}\cdot{K}{}_{[a,b,c,d]}$
$\displaystyle\,\approx\,{K}{}_{[e,b,c,d]}\cdot{X}{}_{[a,e]}$ (121)
$\displaystyle{X}{}_{[b,e]}\cdot{K}{}_{[a,b,c,d]}$
$\displaystyle\,\approx\,{K}{}_{[a,e,c,d]}\cdot{X}{}_{[b,e]}$ (122)
$\displaystyle{X}{}_{[c,e]}\cdot{K}{}_{[a,b,c,d]}$
$\displaystyle\,\approx\,{K}{}_{[a,b,e,d]}\cdot{X}{}_{[c,e]}$ (123)
$\displaystyle{X}{}_{[d,e]}\cdot{K}{}_{[a,b,c,d]}$
$\displaystyle\,\approx\,{K}{}_{[a,b,c,e]}\cdot{X}{}_{[d,e]}$ (124)
$\displaystyle{X}{}_{[0,1]}\cdot{K}{}_{[0,1,2,3]}$
$\displaystyle\,\approx\,{K}{}_{[0,1,2,3]}\cdot{X}{}_{[0,1]}\cdot{(-1)}{}_{[1]}\cdot{(-1)}{}_{[3]}$
(125) $\displaystyle{X}{}_{[1,2]}\cdot{K}{}_{[0,1,2,3]}$
$\displaystyle\,\approx\,{(-1)}{}_{[0]}\cdot{K}{}_{[0,1,2,3]}\cdot{(-1)}{}_{[0]}\cdot{K}{}_{[0,1,2,3]}\cdot{(-1)}{}_{[0]}$
(126) $\displaystyle{X}{}_{[2,3]}\cdot{K}{}_{[0,1,2,3]}$
$\displaystyle\,\approx\,{K}{}_{[0,1,2,3]}\cdot{X}{}_{[1,3]}$ (127)
$\displaystyle{K}{}_{[0,1,2,3]}\cdot{K}{}_{[1,3,4,5]}$
$\displaystyle\,\approx\,{K}{}_{[1,3,4,5]}\cdot{K}{}_{[0,1,2,3]}$ (128)
$\displaystyle{(-1)}{}_{[0]}\cdot{(-1)}{}_{[4]}\cdot{X}{}_{[0,4]}\cdot\rho$
$\displaystyle\,\approx\,\rho\cdot{X}{}_{[0,4]}\cdot{(-1)}{}_{[4]}\cdot{(-1)}{}_{[0]}$
(129)

Figure 10: The representative relations in $\mathcal{R}_{n}^{1}$, for all
valid choices of $a,b,c,d,e,f\in\mathbb{Z}$. We write $\rho$ for the substring
${K}{}_{[4,5,6,7]}\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[3,4]}\cdot{K}{}_{[0,1,2,3]}\cdot{K}{}_{[4,5,6,7]}\cdot{X}{}_{[0,4]}$.

In Section 5.2, a set of representative relations were selected from
$\mathcal{R}_{n}$. These relations are illustrated in Figure 10. In some
sense, the choice of representative relations were arbitrary, since all
choices are equivalent up to permutation. However, preference was given to the
parameters $[0]$, $[4]$, $[0,1,2,3]$, $[4,5,6,7]$, since these correspond well
to controlled qubit operators.

###  F.4 Proving the Redundant Relations are Derivable

This section makes use of the braiding relations and the inverse relations, to
derive several bifunctoriality and commutator relations. Each proof follows
the same structure. First, the special case is proven where all generators of
type $(-1)$ or $K$ have consecutive indices starting from $0$. In all other
cases, there is a generator of type $(-1)$ or $K$ conjugated by a permutation.
The braiding relations are used to obtain a convenient decomposition for each
permutation. The commutativity and bifunctoriality follow immediately from
these decompositions.

######  Lemma F.12.

If $(0,a,b)$ is an increasing sequence over $[n]$, then
${X}{}_{[a,b]}\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot{X}{}_{[a,b]}$.

###### Proof.

Let $\sigma=\tau_{a,b}$. Since $3<a<b$, then there exists a decomposition
$\tau_{c_{1},c_{1}+1}\circ\tau_{c_{2},c_{2}+1}\circ\cdots\tau_{c_{m},c_{m}+1}$
of $\sigma$ into transpositions such that $0<c_{k}$ for all $k\in[n]$. Define
$u={X}{}_{[c_{1},c_{1}+1]}\cdot{X}{}_{[c_{2},c_{2}+1]}\cdots{X}{}_{[c_{m},c_{m}+1]}$.
Then
$[\\![{X}{}_{[a,b]}]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}=[\\![u]\\!]_{O}^{*}$.
Then ${X}{}_{[a,b]}\sim_{\mathcal{R}_{n}^{3}}u$ by Lemma F.2. The proof
follows by induction on $m$.

  1. –

Base Case. If $|u|=0$, then $u\cdot{(-1)}{}_{[0]}={(-1)}{}_{[0]}\cdot u$. Then
$u\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot u$ by
reflexivity.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $|u|=k$, then
$u\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot u$.

  3. –

Inductive Step. Assume that $m=k+1$. Define
$v={X}{}_{[c_{1},c_{1}+1]}\cdot{X}{}_{[c_{2},c_{2}+1]}\cdots{X}{}_{[c_{k},c_{k}+1]}$.
Then by definition $u=v\cdot{X}{}_{[c_{m},c_{m}+1]}$. Since $c_{m}>0$, then
$u\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}v\cdot{(-1)}{}_{[0]}\cdot{X}{}_{[c_{m},c_{m}+1]}$
by the relation
${X}{}_{[c_{m},c_{m}+1]}\cdot{(-1)}{}_{[0]}\approx_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot{X}{}_{[c_{m},c_{m}+1]}$.
Furthermore, since $|v|=k$, then by the inductive hypothesis
$v\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot v$. Then
$v\cdot{(-1)}{}_{[0]}\cdot{X}{}_{[c_{m},c_{m}+1]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot
u$. Then by the transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$,
$u\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot u$ and the
inductive step is established.

Then $u\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot u$ by
the principle of induction. Since
${X}{}_{[a,b]}\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}u\cdot{(-1)}{}_{[0]}$
and ${(-1)}{}_{[0]}\cdot
u\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot{X}{}_{[a,b]}$, then
${X}{}_{[a,b]}\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot{X}{}_{[a,b]}$
by the transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$. ∎

######  Theorem F.13.

All instances of Relation 51 are derivable from $\mathcal{R}_{n}^{3}$.

###### Proof.

Let $\\{a,b,c\\}\in[n]$. Define $\sigma\in\mathrm{S}(n)$ such that $\sigma$ is
$\tau_{k,c_{k}}$ if $c>0$, or identity otherwise. Likewise, define $u$ to be
${X}{}_{[0,c]}$ if $c>0$, or $\epsilon$ otherwise. Clearly
$\tau_{a,b}\circ\sigma=\sigma\circ\tau_{\sigma(a),\sigma(b)}$. Then,

$[\\![{X}{}_{[a,b]}\cdot
u]\\!]_{O}^{*}=[\\![\tau_{a,b}\circ\sigma]\\!]_{S}=[\\![\sigma\circ\tau_{\sigma(a),\sigma(b)}]\\!]_{S}=[\\![u\cdot{X}{}_{[\sigma(a),\sigma(b)]}]\\!]_{O}^{*}.$

Then ${X}{}_{[a,b]}\cdot
u\sim_{\mathcal{R}_{n}^{3}}u\cdot{X}{}_{[\sigma(a),\sigma(b)]}$ by Lemma F.2.
Likewise,
${X}{}_{[\sigma(a),\sigma(b)]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}\overline{u}\cdot{X}{}_{[a,b]}$
by Lemma F.3. Since $\\{a,b,c\\}$ are distinct, then $\sigma(a)>0$ and
$\sigma(b)>0$. Then
${X}{}_{[\sigma{a},\sigma{b}]}\cdot{(-1)}{}_{[0]}\sim_{\mathcal{R}_{n}^{3}}{(-1)}{}_{[0]}\cdot{X}{}_{[\sigma{a},\sigma{b}]}$
by Lemma F.12. Then the following derivation holds.

${X}{}_{[a,b]}\cdot
u\cdot{(-1)}{}_{[0]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{X}{}_{[\sigma(a),\sigma(b)]}\cdot{(-1)}{}_{[0]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{(-1)}{}_{[0]}\cdot{X}{}_{[\sigma(a),\sigma(b)]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{(-1)}{}_{[0]}\cdot\overline{u}\cdot{X}{}_{[a,b]}$

Since $\\{a,b,c\\}$ were arbitrary, then all instances of Relation 51 are
derivable from $\mathcal{R}_{n}^{3}$. ∎

######  Lemma F.14.

If $(3,a,b)$ is an increasing sequence over $[n]$, then
${X}{}_{[a,b]}\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a,b]}$.

###### Proof.

Let $\sigma=\tau_{a,b}$. Since $3<a<b$, then there exists a decomposition
$\tau_{c_{1},c_{1}+1}\circ\tau_{c_{2},c_{2}+1}\circ\cdots\tau_{c_{m},c_{m}+1}$
of $\sigma$ into transpositions such that $3<c_{k}$ for all $k\in[n]$. Define
$u={X}{}_{[c_{1},c_{1}+1]}\cdot{X}{}_{[c_{2},c_{2}+1]}\cdots{X}{}_{[c_{m},c_{m}+1]}$.
Then
$[\\![{X}{}_{[a,b]}]\\!]_{O}^{*}=[\\![\sigma]\\!]_{S}=[\\![u]\\!]_{O}^{*}$.
Then ${X}{}_{[a,b]}\sim_{\mathcal{R}_{n}^{3}}u$ by Lemma F.2. The proof
follows by induction on $m$.

  1. –

Base Case. If $|u|=0$, then
$u\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot u$ by
reflexivity.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $|u|=k$, then
$u\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot u$.

  3. –

Inductive Step. Assume that $m=k+1$. Define
$v={X}{}_{[c_{1},c_{1}+1]}\cdot{X}{}_{[c_{2},c_{2}+1]}\cdots{X}{}_{[c_{k},c_{k}+1]}$.
Then by definition $u=v\cdot{X}{}_{[c_{m},c_{m}+1]}$. Since $c_{m}>3$, then
$u\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}v\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[c_{m},c_{m}+1]}$
by the relation
${X}{}_{[c_{m},c_{m}+1]}\cdot{K}{}_{[0,1,2,3]}\approx_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[c_{m},c_{m}+1]}$.
Since $|v|=k$, then by the inductive hypothesis
$v\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot v$.
Then
$v\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[c_{m},c_{m}+1]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot
u$. Then by the transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$,
$u\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot u$
and the inductive step is established.

Then $u\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot
u$ by the principle of induction. Since
${X}{}_{[a,b]}\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}u\cdot{K}{}_{[0,1,2,3]}$
and ${K}{}_{[0,1,2,3]}\cdot
u\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a,b]}$, then
${X}{}_{[a,b]}\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a,b]}$
by the transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$. ∎

######  Theorem F.15.

All instances of Relation 52 are derivable from $\mathcal{R}_{n}^{3}$.

###### Proof.

Let $(c_{0},c_{1},c_{2},c_{3})$ an increasing sequence over $[n]$. Since
$(c_{0},c_{1},c_{2},c_{3})$ is increasing, then $k\leq c_{k}$ for $k\in[4]$.
Then for each $k\in[4]$, define $\sigma_{k}$ to be $\tau_{k,c_{k}}$ if $k\neq
c_{k}$, or identity otherwise, and define
$\sigma=\sigma_{0}\circ\sigma_{1}\circ\sigma_{2}\circ\sigma_{3}$. Likewise,
for each $k\in[4]$, define $u_{k}$ to be ${X}{}_{[k,c_{k}]}$ if $k\neq c_{k}$,
or $\epsilon$ otherwise, and let $u=u_{0}\cdot u_{1}\cdot u_{2}\cdot u_{3}$.
Clearly $\tau_{a,b}\circ\sigma=\sigma\circ\tau_{\sigma(a),\sigma(b)}$. Then,

$[\\![{X}{}_{[a,b]}\cdot
u]\\!]_{O}^{*}=[\\![\tau_{a,b}\circ\sigma]\\!]_{S}=[\\![\sigma\circ\tau_{\sigma(a),\sigma(b)}]\\!]_{S}=[\\![u\cdot{X}{}_{[\sigma(a),\sigma(b)]}]\\!]_{O}^{*}.$

Then ${X}{}_{[a,b]}\cdot
u\sim_{\mathcal{R}_{n}^{3}}u\cdot{X}{}_{[\sigma(a),\sigma(b)]}$ by Lemma F.2.
Likewise,
${X}{}_{[\sigma(a),\sigma(b)]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}\overline{u}\cdot{X}{}_{[a,b]}$
by Lemma F.3. Since $a,b\not\in\\{c_{0},c_{1},c_{2},c_{3}\\}$, then
$\sigma(a)>3$ and $\sigma(b)>3$. Then
${X}{}_{[\sigma{a},\sigma{b}]}\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[\sigma{a},\sigma{b}]}$
by Lemma F.14. Then the following derivation holds.

${X}{}_{[a,b]}\cdot
u\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{X}{}_{[\sigma(a),\sigma(b)]}\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[\sigma(a),\sigma(b)]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}u\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\cdot{X}{}_{[a,b]}$

Since $\\{a,b,c_{0},c_{1},c_{2},c_{3}\\}$ were arbitrary, then all instances
of Relation 52 are derivable from $\mathcal{R}_{n}^{3}$. ∎

######  Lemma F.16.

Let $(c_{0},a,c_{1},c_{2},c_{3})$ be an increasing sequence over $[n]$. For
each $k\in[4]$, define $\sigma_{k}$ to be $\tau_{k,c_{k}}$ if $k\neq c_{k}$,
or identity otherwise. If
$\sigma=\sigma_{0}\cdot\sigma_{1}\cdot\sigma_{2}\cdot\sigma_{3}$ and
$\rho=\tau_{0,a}\cdot\sigma_{1}\cdot\sigma_{2}\cdot\sigma_{3}$, then there
exists an $\alpha\in\mathrm{S}(n)$ such that
$\tau_{c_{0},a}\circ\sigma=\rho\circ\alpha$ with $\alpha$ fixing $[4]$.

###### Proof.

By definition, $\rho(0)=a=\tau_{c_{0},a}(\sigma(0))$,
$\rho(1)=c_{1}=\tau_{c_{0},a}(\sigma(0))$,
$\rho(1)=c_{2}=\tau_{c_{0},a}(\sigma(0))$, and
$\rho(2)=c_{2}=\tau_{c_{0},a}(\sigma(0))$. Since $\mathrm{S}(n)$ is a group,
then there exists an $\alpha\in\mathrm{S}(n)$ such that
$\tau_{c_{0},a}\circ\sigma=\rho\circ\alpha$. Assume that there exists a
$k\in[4]$ such that $\alpha(k)\neq k$. Then
$(\tau_{c_{0},a}\circ\sigma)(\alpha(k))\neq(\tau_{c_{0},a}\circ\sigma)(k)=\rho(k)$.
Then by contradiction, $\alpha$ fixes $[4]$. Then $\alpha$ decomposes into a
sequence of transpositions over $[n]\setminus[4]$. ∎

######  Lemma F.17.

Let
$w={X}{}_{[a_{0},b_{0}]}\cdot{X}{}_{[a_{1},b_{1}]}\cdots{X}{}_{[a_{m},b_{m}]}$
such that $a_{k}>3$ and $b_{k}>3$ for all $k\in[m+1]$. Then
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot w$.

###### Proof.

Let proof follows by induction on $|w|$.

  1. –

Base Case. If $|w|=0$, then $w=\epsilon$ and
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot w$ by
the transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$.

  2. –

Inductive Hypothesis. Assume that for some $k\in\mathbb{N}$, if $|w|=k$, then
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot w$

  3. –

Inductive Step. Assume that $|w|=k+1$. Define
$v={X}{}_{[a_{0},b_{0}]}\cdot{X}{}_{[a_{1},b_{1}]}\cdots{X}{}_{[a_{k},b_{k}]}$.
Then by definition $w=v\cdot{X}{}_{[a_{m},b_{m}]}$. Since $a_{m}>3$ and
$b_{m}>3$, then
${X}{}_{[a_{m},b_{m}]}\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a_{m},b_{m}]}$
by Lemma F.14. As a result,
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}v\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a_{m},b_{m}]}$.
Then by the inductive hypothesis,
$v\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot v$.
As a result,
$v\cdot{K}{}_{[0,1,2,3]}\cdot{X}{}_{[a_{m},b_{m}]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot
w$. Then $w\cdot{K}{}_{[0,1,2,3]}\sim{K}{}_{[0,1,2,3]}\cdot w$ by the
transitivity of $(\sim_{\mathcal{R}_{n}^{3}})$ and the inductive step is
established.

Then by the principle of induction,
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot w$. ∎

######  Theorem F.18.

All instances of Relations 59, 60, 61 and 62 are derivable from
$\mathcal{R}_{n}^{3}$.

###### Proof.

Let be $(c_{0},a,c_{1},c_{2},c_{3})$ an increasing sequence. For each
$k\in[4]$, define $\sigma_{k}$ to be $\tau_{k,c_{k}}$ if $k\neq c_{k}$, or
identity otherwise. Then define
$\sigma=\sigma_{0}\circ\sigma_{1}\circ\sigma_{2}\circ\sigma_{3}$ and
$\rho=\tau_{0,a}\cdot\sigma_{1}\cdot\sigma_{2}\cdot\sigma_{3}$. By Lemma F.16,
there exists a sequence of transpositions
$\alpha=\alpha_{0}\circ\alpha_{1}\circ\cdots\alpha_{m}$ such that
$\tau_{c_{0},a}\circ\sigma=\rho\circ\alpha$. Then define
$w=[\\![\alpha_{0}]\\!]_{S}\cdot[\\![\alpha_{1}]\\!]_{S}\cdots[\\![\alpha_{m}]\\!]_{S}$.
Next, for each $k\in[4]$, define $u_{k}$ to be ${X}{}_{[k,c_{k}]}$ if $k\neq
c_{k}$, or $\epsilon$ otherwise. Then define $u=u_{0}\cdot u_{1}\cdot
u_{2}\cdot u_{3}$, $v={X}{}_{[c_{0},a]}\cdot u_{1}\cdot u_{2}\cdot u_{3}$, and
$w=[\\![\alpha_{0}]\\!]_{S}\cdot[\\![\alpha_{1}]\\!]_{S}\cdots[\\![\alpha_{m}]\\!]_{S}$.
It follows that
$[\\![u]\\!]_{O}^{*}=[\\![\tau_{c_{0},a}\circ\sigma]\\!]_{S}=[\\![\rho\circ\alpha]\\!]_{S}=[\\![v\cdot
w]\\!]$. Since $u$, $v$, and $w$ are words over two-level operators of type
$X$, then ${X}{}_{[c_{0},a]}\cdot u\sim_{\mathcal{R}_{n}^{3}}v\cdot w$.
Likewise, by Lemma F.3,
$\overline{u}\cdot{X}{}_{[c_{0},a]}\sim_{\mathcal{R}_{n}^{3}}\overline{w}\cdot\overline{v}$.
Then ${X}{}_{[c_{0},a]}\cdot u$ acts by conjugation on ${K}{}_{[0,1,2,3]}$ as
follows.

${X}{}_{[c_{0},a]}\cdot
u\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\cdot{X}{}_{[c_{0},1]}\sim_{\mathcal{R}_{n}^{3}}v\cdot
w\cdot{K}{}_{[0,1,2,3]}\overline{u}\cdot{X}{}_{[c_{0},1]}\sim_{\mathcal{R}_{n}^{3}}v\cdot
w\cdot{K}{}_{[0,1,2,3]}\cdot\overline{w}\cdot\overline{v}$

Then by Lemma F.17,
$w\cdot{K}{}_{[0,1,2,3]}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot w$.
Furthermore, $w\cdot\overline{w}\sim_{\mathcal{R}_{n}^{3}}\epsilon$ Lemma F.3.
Then $w$ acts by conjugation on ${K}{}_{[0,1,2,3]}$ as follows.

$w\cdot{K}{}_{[0,1,2,3]}\cdot\overline{w}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}\cdot
w\cdot\overline{w}\sim_{\mathcal{R}_{n}^{3}}{K}{}_{[0,1,2,3]}$

Since ${X}{}_{[c_{0},a]}{}^{2}\sim_{\mathcal{R}_{n}^{3}}\epsilon$ by Lemma
F.2, then the following derivation also holds.

${X}{}_{[c_{0},a]}\cdot
u\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\sim_{\mathcal{R}_{n}^{3}}{X}{}_{[c_{0},a]}\cdot
u\cdot{K}{}_{[0,1,2,3]}\cdot\overline{u}\cdot{X}{}_{[c_{0},1]}{}^{2}\sim_{\mathcal{R}_{n}^{3}}v\cdot
w\cdot{K}{}_{[0,1,2,3]}\cdot\overline{w}\cdot\overline{v}\cdot{X}{}_{[c_{0},1]}\sim_{\mathcal{R}_{n}^{3}}v\cdot{K}{}_{[0,1,2,3]}\cdot\overline{v}\cdot{X}{}_{[c_{0},1]}$

Since $\\{a,b,c_{0},c_{1},c_{2},c_{3}\\}$ were all arbitrary, then all
instances of Relation 59 holds. The cases of Relations 60, 61 and 62 follow
symmetrically. ∎