# On Reflection Representations of Coxeter Groups over Non-Commutative Rings
II

Annette Pilkington  Department of Mathematics
University of Notre Dame
Room 255 Hurley Building
Notre Dame, Indiana, 46556<EMAIL_ADDRESS>
###### Abstract.

This paper generalizes an isomorphism between certain quotients of path
algebras and matrix rings over free products, used in the first paper in this
sequence. Applications of the isomorphism to certain path algebras associated
to Coxeter groups and to Cohn path algebras are given.

###### Key words and phrases:

Path Algebras, Domain, Coxeter Groups

##  1\. Introduction

Representations of a Coxeter system, $(W,S)$, over a number of quotients of a
path algebra related to the Coxeter graph, $\Gamma_{W,S}$, of the system are
studied in Dyer [17]. In Pilkington [27], we studied one of these quotient
algebras, $R_{W,S}$, in detail. We showed that in the case of a Coxeter group
of infinite rank, $R_{W,S}$ is the direct limit of the corresponding algebras
defined on the finite rank parabolic subgroups. In that paper, we answered in
the affirmative a question posed in Dyer [17] about its multiplicative
properties. In the course of that proof, we used an imbedding of the quotient
algebra, $R_{W,S}$, for a Coxeter system of finite rank $N$, into the ring of
$(N+1)\times(N+1)$ matrices over a free product of rings, related to the edges
of the Coxeter graph. These rings are either field extensions of $\mathbb{Q}$,
rings of Laurent polynomials over $\mathbb{Q}$ or rings of polynomials in two
non-commuting variables over $\mathbb{Q}$.

The above imbedding uses a special case of an isomorphism between the path
algebra $\hat{R}_{W,S}=R_{W,S}\otimes_{\mathbb{Z}}\mathbb{Q}$ and the $N\times
N$ matrices over such a free product of rings, where $N$ is the rank of the
system. This imbedding exists for graphs $\Gamma_{W,S}$ with a spanning tree
where the edges of the spanning tree are associated to finite entries in the
Coxeter Matrix. This applies in the case of the Weyl groups and many commonly
studied examples. In this paper, we present this more general isomorphism.
Since the imbedding is applicable to a wider range of path algebras, we pull
out the general principles and demonstrate applications to both Coxeter
systems and Cohn path algebras (see Abrahms et al. [1]).

Let $(W,S=\\{s_{i}\\}_{1\leq i\leq N})$ be a Coxeter system of finite rank
with Coxeter matrix $(m_{ij})_{1\leq i,j\leq N}$. The Coxeter graph
$\Gamma_{W,S}=(S,Y)$ has vertices $S$ and edges
$Y=\\{y_{ij}=[s_{i}s_{j}],1\leq i\leq N,3\leq m_{ij}\leq\infty\\}$. The
associated path algebra $\mathbb{Q}\Gamma_{W,S}$ and its quotient
$\hat{R}_{W,S}$ are fully described in Section 5 of this paper. Let $K_{n}$
denote the field extension of $\mathbb{Q}$ obtained by adjoining
$4\cos^{2}\frac{\pi}{n}$. Let $\mathbb{Q}[x_{ij},x_{ij}^{-1}]$ be the ring of
Laurent polynomials over $\mathbb{Q}$ and $\mathbb{Q}[x_{ij},\bar{x}_{ij}]$ be
the polynomial ring in the non-commuting variables $x_{ij}$ and
$\bar{x}_{ij}$. We show the following:

######  Theorem 1.1.

Let $(W,S)$ be a finite rank Coxeter system, with Coxeter graph $\Gamma_{W,S}$
as described above. Let $Y_{1}=\\{y_{ij}\in Y|3\leq m_{ij}<\infty\\}$. Let $T$
be a spanning tree for $\Gamma_{W,S}$, whose edges are denoted by $Y^{T}$,
with the property that $Y^{T}\subseteq Y_{1}$. Then we have a unital ring
isomorphism

$\hat{R}_{W,S}\otimes_{\mathbb{Z}}\mathbb{Q}\equiv M_{N}(Q),$

where $Q$ is isomorphic to the free product of the following rings;

$\begin{matrix}K_{m_{ij}},&3\leq m_{ij}<\infty,&i<j,\\\
\mathbb{Q}[y_{ij},y_{ij}^{-1}],&y_{ij}\in Y\backslash Y_{T},&3\leq
m_{ij}<\infty,i<j\\\ \mathbb{Q}[x_{ij},\bar{x}_{ij}],&y_{ij}\in Y\backslash
Y_{T},&m_{ij}=\infty,i<j\\\ \end{matrix}$

To demonstrate the wider applicability of the imbedding described above, we
apply the imbedding to the Cohn path algebras. In [2], Abrahms and Kanuni show
that a Cohn path algebra has the IBN property. We give an alternative proof of
this, in fact we show that a Cohn path algebra has a stronger property, namely
the UGN property or in more modern terms; it satisfies the rank condition. In
section 6 we show:

######  Theorem 1.2.

A Cohn path algebra has the UGN property.

##  2\. general Notation and Definitions

### 2.1.

The notation $X=\\{a,b,c\\}$ will be used to denote that $X$ is a set with
elements $a,b$ and $c$ and $Y\subset X$ will indicate that $Y$ is a subset of
$X$. The set $X\backslash Y$ will be the set of all elements in $X$ but not in
$Y$ and the set $X\bigcupdot Z$ will denote the disjoint union of the sets $X$
and $Z$.

Unless otherwise stated, all rings considered have an identity (are unital).
If $R$ is a ring, we will denote the identity of $R$ by $1_{R}$ in situations
where the ring in question may not be clear from the context. The group of
multiplicative units of $R$ will be denoted by $R^{*}$. If $\phi:R_{1}\to
R_{2}$ is a homomorphism of rings and $S\subset R_{1}$ is a subring of
$R_{1}$, we let $\phi|_{S}$ denote the restriction of $\phi$ to $S$. If
$\psi:R_{2}\to R_{3}$ is a homomorphism from $R_{2}$ to the ring $R_{3}$, we
let $\psi\circ\phi$ denote the composition map. We will use the notation
$R_{1}\cong R_{2}$ to indicate that the rings $R_{1}$ and $R_{2}$ are
isomorphic.

If $X$ is a subset of a ring $R$, the two sided ideal of $R$ generated by the
set $X$ will be denoted by $\langle X\rangle$. If $I$ is an ideal of a ring
$R$, we write $r_{1}\equiv r_{2}\mod I$ when $r_{1}-r_{2}\in I$. We denote the
ring of $n\times n$ matrices over a ring $R$ by $M_{n}(R)$ and we will denote
the set of $m\times n$ matrices by $M_{m\times n}(R)$ where $m$ is possibly
not equal to $n$. We will also use the notation $\langle x\in X|r\in R\rangle$
to denote a group with generators in the set $X$ and relations in the set $R$.
In cases where the meaning of the notation is not clear from the context, we
will add clarification.

The symbol $\mathbb{N}$ will be used to denote the non-negative integers,
$\\{0,1,2,3,\dots\\}$, and the symbol $\mathbb{N}_{\geq k}$ will be used to
denote the subset of $\mathbb{N}$ consisting of numbers greater than or equal
to $k$. We let $[k]$ denote the set $\\{1,\dots,k\\}$. The integers will be
denoted by $\mathbb{Z}$, and the rational numbers by $\mathbb{Q}$. Polynomial
rings $\mathbb{Q}[\\{x_{i}\\}_{i\in I}]$ will have non-commuting variables
$\\{x_{i}\\}_{i\in I}$ unless stated otherwise.

Let $A$ be a commutative unital ring. An (associative, possibly non-unital)
$A$-algebra is a (possibly non-unital, associative) ring $B$ with an
additional structure of unital $A$-module for which the multiplication map
$B\times B\to B$ is $A$-bilinear (i.e.
$(\alpha_{1}b_{1}+\alpha_{2}b_{2})(\alpha_{3}b_{3}+\alpha_{4}b_{4})=\displaystyle\sum_{i=1}^{2}\sum_{j=1}^{2}\alpha_{i}\alpha_{j}b_{i}b_{j},$
for all $\alpha_{i}\in A,b_{j}\in B$). Morphisms of $A$-algebras are
$A$-linear ring homomorphisms. We call $A$ the coefficient ring of the
$A$-algebra $B$. We regard rings as $\mathbb{Z}$-algebras. We say $B_{1}$ is a
sub-(A)-algebra of the $A$-algebra $B$ if $B_{1}$ is a subring of $B$ which
inherits its $A$-algebra structure from $B$.

##  3\. Graphs and Spanning Trees

As in Pilkington [27], we use the notation and terminology of Serre [28] for
graphs and trees.

######  Definition 1.

A graph $\Gamma=(S,Y)$ consists of a set of vertices $S=\mbox{vert}\ \Gamma$,
a set of edges $Y=\mbox{edge}\ \Gamma$ and two maps

$Y\to S\times S,\ \ y\to(o(y),t(y))$

and

$Y\to Y,\ \ y\to\bar{y},$

which satisfy the following condition: for each $y\in Y$, we have
$\bar{\bar{y}}=y,\bar{y}\not=y$ and $o(y)=t(\bar{y})$.

Each $s\in S$ is called a vertex of $\Gamma$ and each $y\in Y$ is called an
edge of $\Gamma$. If $y\in Y$, $o(y)$ is called the origin of $y$ and $t(y)$
is called the terminus of $y$, together $o(y)$ and $t(y)$ are called the
extremities  of $y$. We say that two vertices are adjacent if they are the
extremities of some edge. If $S=\\{s_{i}\\}_{i\in I}$ and $y\in Y$, we let
$o^{\prime}(y)=i$, when $o(y)=s_{i}$, and we let $t^{\prime}(y)=j$ when
$t(y)=s_{j}$.

######  Definition 2.

An orientation of a graph $\Gamma$ is a subset $Y_{+}$ of $Y=\mbox{edge}\
\Gamma$ such that $Y$ is the disjoint union
$Y=Y_{+}\bigcupdot\overline{Y_{+}}$

###  3.1. Paths

A path of length $n\geq 1$ in a graph $\Gamma$ is a sequence of edges
$p=(y_{1},\dots,y_{n})$ such that $t(y_{i})=o(y_{i+1})$, $1\leq i\leq n-1$. We
will denote such a path in what follows as $p=y_{1}\dots y_{n}$. Paths of
length zero are just single vertices and will be denoted by $p=[s]$ for $s\in
S$. The length of a path $p$ will be denoted by $\ell(p)$. Let $\mathfrak{P}$
denote the set of all paths in $\Gamma$, we can extend the maps $o$ and $t$ to
$\mathfrak{P}$ by letting $o(y_{1},\dots,y_{n})=o(y_{1})=s_{0}$ and
$t(y_{1},\dots,y_{n})=t(y_{n})=s_{n}$ and $o([s])=s=t([s])$. If
$s_{i}=t(y_{i})$ and $s_{i-1}=o(y_{i})$, we say that $p$ is a path from
$s_{0}$ to $s_{n}$ and that $s_{0}$ and $s_{n}$ are the extremities of the
path.

A graph is connected if any two vertices are the extremities of at least one
path. If $p=y_{1}\dots y_{n}$ and $y_{i+1}=\bar{y}$ for some $1\leq i\leq
n-1$, then the pair $(y_{i},y_{i+1})$ is called a backtracking. A path $p$ is
a circuit if it is a path without backtracking such that $o(p)=t(p)$ and
$\ell(p)\geq 1$. A circuit of length one is called a loop. A graph $\Gamma$ is
called combinatorial if it has no circuit of length less than or equal to two.
If a graph $\Gamma$ is combinatorial, a path $p=y_{1}\dots y_{n}$ is
determined by the extremities of its edges and can be characterized and
denoted by its vertices as

$p=y_{1}\dots y_{n}=[s_{0}s_{1}\dots s_{n}],\ \mbox{where}\
s_{i}=t(y_{i}),s_{i-1}=o(y_{i}).$

A geometric edge of a combinatorial graph, $\Gamma$, is a set
$\\{s_{1},s_{2}\\}$ of extremities of an edge in $\Gamma$. Each such geometric
edge corresponds to a pair of edges $\\{y,\bar{y}\\}$ in the edge set of
$\Gamma$. A combinatorial graph is determined by its vertices and geometric
edges.

###  3.2. Trees

If $T\not=\emptyset$ is a connected graph without circuits, $T$ is called a
tree. It is a combinatorial graph. A geodesic in a tree is a path without
backtracking. By Proposition 8, Serre [28], if $s_{1}$ and $s_{2}$ are two
vertices in a tree, $T$, there is exactly one geodesic from $s_{1}$ to $s_{2}$
and it has distinct vertices. The length of the geodesic from $s_{1}$ to
$s_{2}$ is called the distance from $s_{1}$ to $s_{2}$ and we will denote it
by $d_{T}(s_{1},s_{2})$.

Given a non-empty connected graph $\Gamma$, the set of subgraphs (defined in
the obvious way) which are trees are ordered by inclusion. The union of a
chain of trees is a tree and hence the set has a maximal element, by Zorn’s
lemma. Such a maximal element is called a maximal tree  of $\Gamma$. By
Proposition 11, Serre [28], if $T$ is a maximal tree of a connected non-empty
graph $\Gamma$, then $T$ contains all of the vertices of $\Gamma$.
Furthermore, if $\Gamma$ has a finite number of vertices with Card($S$) = $s$,
then the number of edges of the spanning tree $2(s-1)$ (the number of
geometric edges is $s-1$). If the graph $\Gamma$ is not a tree, then, adding
an edge (from the edge set of $\Gamma$) to $T$, creates a cycle, called a
fundamental cycle. There are $e-s+1$ distinct fundamental cycles in $\Gamma$
where $e$ is the number of edges in $\Gamma$.

###  3.3. Path Algebras

Let $\Gamma=(S,Y)$ be a graph with vertices $S=\\{s_{i}\\}_{i\in I}$, edges
$Y$ and paths $\mathfrak{P}$. Given a commutative ring $A$ with identity, the
path algebra of $\Gamma$ over $A$, denoted $A\Gamma$, is an associative
$A$-algebra, with an $A$-basis of paths in $\mathfrak{P}$. Multiplication of
paths is given by concatenation ;

$(y_{1}y_{2}\dots y_{n})(y^{\prime}_{1}y^{\prime}_{2}\dots
y^{\prime}_{m})=\begin{cases}0&\mbox{if}\ t(y_{n})\not=o(y^{\prime}_{1})\\\
y_{1}y_{2}\dots y_{n}y^{\prime}_{1}y^{\prime}_{2}\dots
y^{\prime}_{m}&\mbox{if}\ t(y_{n})=o(y^{\prime}_{1})\\\ \end{cases}$

The paths of length $0$, $\\{[s_{i}]\\}_{s_{i}\in S}$ form a set of orthogonal
idempotents with this multiplication and if $S$ is finite, $A\Gamma$ has an
identity given by

$1=\sum_{s\in S}[s].$

Let $\mathfrak{F}_{\Gamma}=\\{f_{y}(t)\\}_{y\in Y_{1}}$ be a set of
polynomials in the polynomial ring $A[t]$ indexed by $Y_{1}\subseteq Y$.

######  Definition 3.1.

We say that $\mathfrak{F}_{\Gamma}$ has property F if the following conditions
are satisfied:

$\overline{Y_{1}}=Y_{1}$ and for each $y\in Y_{1}$, $f_{y}$ is non-constant,
$f_{y}=f_{\bar{y}}$ and the constant term of $f_{y}$ is a unit in $A$.

In what follows, if $f\in A[t]$ and $y\in Y$, we let $f(y\bar{y})$ denote the
element of the subring $[o(y)]A\Gamma[o(y)]\subset A\Gamma$ (where the
imbedding is non-unital) that we get by replacing $t$ by $y\bar{y}$ and
$1_{A}$ by $[o(y)]$ in the polynomial $f$ (this is $f$ evaluated at $y\bar{y}$
in the subring $[o(y)]A\Gamma[o(y)]$). We let $I_{\mathfrak{F}_{\Gamma}}$
denote the two sided ideal of $A\Gamma$ generated by the set of elements
$\\{f_{y}(y\bar{y})|y\in Y_{1}\\}$, and we let $R_{\mathfrak{F}_{\Gamma}}$
denote the quotient algebra

$R_{\mathfrak{F}_{\Gamma}}=A\Gamma/I_{\mathfrak{F}_{\Gamma}}.$

Note that each pair $\\{y,\bar{y}\\}\subset Y_{1}$ gives two relations in
$R_{\mathfrak{F}_{\Gamma}}$, namely $f_{y}(y\bar{y})=0$ and
$f_{\bar{y}}(\bar{y}y)=f_{y}(\bar{y}y)=0$. If $x\in A\Gamma$, we let
$\tilde{x}$ denote the element $x+I_{\mathfrak{F}_{\Gamma}}$ of
$R_{\mathfrak{F}_{\Gamma}}$, and if $X\subset A\Gamma$, we let
$\widetilde{X}=\\{\tilde{x}|x\in X\\}$.

Using the above notation, we have the following:

######  Lemma 3.2.

Let $A$ be a commutative ring and $\Gamma=(S,Y)$ a graph. Let
$\mathfrak{F}_{\Gamma}=\\{f_{y}(t)|y\in Y_{1}\subset Y\\}$ be a set of
polynomials in $A[t]$ with property F. For each $y\in Y_{1}$, there exists
$y^{\vee}\in[t(y)]A\Gamma[o(y)]$ such that
$\widetilde{yy^{\vee}}=\widetilde{[o(y)]}$ and
$\widetilde{y^{\vee}y}=\widetilde{[t(y)]}$.

###### Proof.

Since $f_{y}(t)$ is non-constant and has a non-zero invertible constant term,
it is of the form $f_{y}(t)=f_{\bar{y}}(t)=th(t)-\kappa$, for some $h(t)\in
A[t]$ and $\kappa\in A^{*}$. I claim that
$y^{\vee}=\frac{1}{\kappa}\bar{y}h(y\bar{y})$ satisfies the equalities given
in the statement of the lemma. Since

$yy^{\vee}=\frac{1}{\kappa}y\bar{y}h(y\bar{y})=\frac{1}{\kappa}f_{y}(y\bar{y})+[o(y)],$

we see that $\widetilde{(yy^{\vee})}=\widetilde{[o(y)]}$. Likewise,

$y^{\vee}y=\frac{1}{\kappa}\bar{y}h(y\bar{y})y=\frac{1}{\kappa}\bar{y}yh(\bar{y}y)=\frac{1}{\kappa}f_{y}(\bar{y}y)+[t(y)]=\frac{1}{\kappa}f_{\bar{y}}(\bar{y}y)+[t(y)].$

Therefore $\widetilde{(y^{\vee}y)}=\widetilde{[t(y)]}$ and this proves the
lemma. ∎

##  4\. A faithful Representation of $R_{\mathfrak{F}_{\Gamma}}$.

We restrict our attention to a graph with a finite number of vertices and a
finite number of edges. Let $\Gamma=(S,Y)$ be a connected graph with vertices
$S=\\{s_{1},\dots,s_{N}\\}$ edges $Y$, where $Y$ is finite. Let $K$ be a field
and let $\mathfrak{F}_{\Gamma}=\\{f_{y}\\}_{y\in Y_{1}}\subset K[t]$ be a set
of polynomials with property F. We assume that $\Gamma$ has a maximal tree
$T=(S,Y^{T})$, where the edges $Y^{T}$ of $Y$ have the property that
$Y^{T}\subseteq Y_{1}$.

### 4.1.

Fixing such a maximal tree $T$ with the above property, we choose a fixed
vertex $r\in S$ and define an orientation on $T$ by letting

$Y^{T}_{+}=\\{y\in Y^{T}|d_{T}(r,o(y))<d_{T}(r,t(y))\\}.$

Clearly $Y^{T}={Y}{{}^{T}_{+}}\bigcupdot\overline{{Y}{{}^{T}_{+}}}$. We extend
this to an orientation on $\Gamma$ by choosing an orientation on the edges
associated to the fundamental cycles $B=Y\backslash
Y^{T}=\\{b_{1},\dots,b_{m},\overline{b_{1}},\dots,\overline{b_{m}}\\}$ for
some choice of $B_{+}=\\{b_{1},\dots,b_{m}\\}$. Letting $Y_{+}=Y^{T}_{+}\cup
B_{+}$ we get an orientation of $\Gamma$; $Y=Y_{+}\bigcupdot\overline{Y_{+}}$.

### 4.2.

As defined in the previous section, $R_{\mathfrak{F}_{\Gamma}}$ denotes the
quotient of the path algebra $K\Gamma$ associated to the set of polynomials
$\mathfrak{F}_{\Gamma}$. We define a special set of elements of
$R_{\mathfrak{F}_{\Gamma}}$ associated to the geodesics in $T$, which will
help us to define an isomorphism between $R_{\mathfrak{F}_{\Gamma}}$ and a
matrix ring over a non-commutative ring.

let $\displaystyle{G}_{s_{i}}^{s_{j}}$, denote the geodesic in $T$ starting at
$s_{i}$ and ending at $s_{j}$ for $s_{i},s_{j}\in S$. If $i\not=j$ and
$\displaystyle{G}_{s_{i}}^{s_{j}}=y_{1}y_{2}\dots y_{n}$, we let
$P_{s_{i}}^{s_{j}}=\alpha(y_{1})\alpha(y_{2})\dots\alpha(y_{n})\in KT$, where
$\alpha:Y^{T}\to KT$ is given by

$\alpha(y)=\begin{cases}y&\mbox{if}\ y\in{Y}{{}^{T}_{+}}\\\
\bar{y}^{\vee}&\mbox{if}\ y\in\overline{{Y}{{}^{T}_{+}}}\end{cases}$

We let $P_{s_{i}}^{s_{i}}=[s_{i}]$. Note that by Lemma 3.2
$\alpha(y)\in[o(y)]K\Gamma[t(y)]$ for all $y\in Y^{T}$.

######  Lemma 4.1.

We have the following identities in $K\Gamma$, where
$s_{i},s_{j},s_{k},s_{l}\in S$:

$\displaystyle P_{s_{i}}^{s_{i}}$ $\displaystyle=[s_{i}]$ $\displaystyle
P_{s_{i}}^{s_{j}}P_{s_{k}}^{s_{l}}$ $\displaystyle=0\ $
$\displaystyle\mbox{if}\ j\not=k$ $\displaystyle
P_{s_{i}}^{s_{j}}P_{s_{k}}^{s_{l}}$ $\displaystyle\equiv P_{s_{i}}^{s_{l}}\mod
I_{\mathfrak{F}_{\Gamma}}\ $ $\displaystyle\mbox{if}\ j=k$

###### Proof.

By definition, $P_{s_{i}}^{s_{i}}=[s_{i}]$. Suppose that $i\not=j$ and
$k\not=l$, with $G_{s_{i}}^{s_{j}}=y_{1}y_{2}\dots y_{n}$ and
$G_{s_{k}}^{s_{l}}=y^{\prime}_{1}y^{\prime}_{2}\dots y^{\prime}_{m}$, where
$y_{i},y^{\prime}_{j}\in Y^{T}$, $1\leq i\leq n,1\leq j\leq m$. Clearly, if
$j\not=k$, then $P_{s_{i}}^{s_{j}}\in[s_{i}]K\Gamma[s_{j}]$ and
$P_{s_{k}}^{s_{l}}\in[s_{k}]K\Gamma[s_{l}]$, hence
$P_{s_{i}}^{s_{j}}P_{s_{k}}^{s_{l}}=0$. It is also clear that
$P_{s_{i}}^{s_{j}}P_{s_{k}}^{s_{l}}=0$ if $j\not=k$ and either $i=j$ or $k=l$,
we leave the details to the reader.

To show that $P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}\equiv P_{s_{i}}^{s_{l}}\mod
I_{\mathfrak{F}_{\Gamma}}$, we proceed by induction on
$\ell(G_{s_{i}}^{s_{j}})+\ell(G_{s_{j}}^{s_{l}})=n+m$. Suppose first that
$n+m=0$, then we must have $i=j=l$ and
$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}=[s_{i}]=P_{s_{i}}^{s_{l}}$. If $n+m=1$,
then either $n=0$ or $m=0$. If $n=0$, then $i=j$ and
$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}=[s_{i}]P_{s_{i}}^{s_{l}}=P_{s_{i}}^{s_{l}}$.
The argument is similar if $m=0$. Now suppose that
$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}\equiv P_{s_{i}}^{s_{l}}\mod
I_{\mathfrak{F}_{\Gamma}}$ if
$\ell(G_{s_{i}}^{s_{j}})+\ell(G_{s_{j}}^{s_{l}})<n+m$ and consider a product
$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}$, where
$\ell(G_{s_{i}}^{s_{j}})+\ell(G_{s_{j}}^{s_{l}})=n+m$. If the path
$G_{s_{i}}^{s_{j}}G_{s_{j}}^{s_{l}}=y_{1}y_{2}\dots
y_{n}y^{\prime}_{1}y^{\prime}_{2}\dots y^{\prime}_{m}$ in $T$ has no
backtracking, it is the geodesic from $s_{i}$ to $s_{l}$ in $T$. In that case,
we have
$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}=\alpha(y_{1})\alpha(y_{2})\dots\alpha(y_{n})\alpha(y^{\prime}_{1})\alpha(y^{\prime}_{2})\dots\alpha(y^{\prime}_{n})=P_{s_{i}}^{s_{l}}$.
If the path $G_{s_{i}}^{s_{j}}G_{s_{j}}^{s_{l}}=y_{1}y_{2}\dots
y_{n}y^{\prime}_{1}y^{\prime}_{2}\dots y^{\prime}_{m}$ has a backtracking, it
must be $(y_{n},y^{\prime}_{1})$, since neither $G_{s_{i}}^{s_{j}}$ nor
$G_{s_{j}}^{s_{l}}$ have backtracking. Thus,
$\alpha(y_{n})\alpha(y^{\prime}_{1})=\bar{y}_{n}^{\vee}\bar{y}_{n}$ or
$y_{n}y_{n}^{\vee}$. By Lemma 3.2, we have
$\alpha(y_{n})\alpha(y^{\prime}_{1})\equiv[o(y_{n})]\mod
I_{\mathfrak{F}_{\Gamma}}$ and

$P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}\equiv\alpha(y_{1})\alpha(y_{2})\dots\alpha(y_{n-1})\alpha(y^{\prime}_{2})\dots\alpha(y^{\prime}_{m})\mod
I_{\mathfrak{F}_{\Gamma}}.$

Since $y_{1}y_{2}\dots y_{n-1}$ and $y^{\prime}_{2}y^{\prime}_{3}\dots
y^{\prime}_{m}$ have no backtracking and their edges are in $T$, they must be
equal to $G_{s_{i}}^{s_{t}}$ and $G_{s_{t}}^{s_{l}}$ respectively, where
$s_{t}=t(y_{n-1})=o(y^{\prime}_{2})$. Now
$\ell(G_{s_{i}}^{s_{t}})+\ell(G_{s_{t}}^{s_{l}})=n+m-2<n+m$, therefore, by
induction, $P_{s_{i}}^{s_{j}}P_{s_{j}}^{s_{l}}\equiv
P_{s_{i}}^{s_{t}}P_{s_{t}}^{s_{l}}\equiv P_{s_{i}}^{s_{l}}\mod
I_{\mathfrak{F}_{\Gamma}}$. ∎

### 4.3.

Using the orientation $Y=Y_{+}\bigcupdot\overline{Y_{+}}$ defined above, we
can define an algebra $Q$ associated to our graph $\Gamma$ and set of
polynomials $\mathfrak{F}_{\Gamma}=\\{f_{y}|y\in Y_{1}\\}$. We let

$Q=K[\\{t_{y}\\}_{y\in Y^{T}_{+}},\ \\{x_{y},\bar{x}_{y}\\}_{y\in B_{+}}]/J,$

where $Q_{1}=K[\\{t_{y}\\}_{y\in Y^{T}_{+}},\ \\{x_{y},\bar{x}_{y}\\}_{y\in
B_{+}}]$ denotes the free $K$-algebra generated by the non-commuting variables
$\\{\\{t_{y}\\}_{y\in Y^{T}_{+}},\ \\{x_{y},\bar{x}_{y}\\}_{y\in B_{+}}\\}$
and $J$ is the ideal of $Q_{1}$ generated by the polynomials

$\left\\{\\{f_{y}(t_{y})\\}_{y\in
Y^{T}_{+}},\\{f_{y}(x_{y}\bar{x}_{y}),f_{y}(\bar{x}_{y}x_{y})\\}_{y\in
B_{+}\cap Y_{1}}\right\\}.$

### 4.4.

Since $Q_{1}$ is a free $K$-algebra on the generators $\\{\\{t_{y}\\}_{y\in
Y^{T}_{+}},\ \\{x_{y},\bar{x}_{y}\\}_{y\in B_{+}}\\}$, for each $i,1\leq i\leq
N$, there is a unique homomorphism of $K$-algebras,
$\hat{\psi}_{i}:Q_{1}\to[s_{i}]K\Gamma[s_{i}]\subset K\Gamma$, such that

$\displaystyle\hat{\psi}_{i}(1_{Q_{1}})$ $\displaystyle=[s_{i}],$
$\displaystyle\hat{\psi}_{i}(t_{y})$
$\displaystyle={P}_{s_{i}}^{o(y)}y\bar{y}{P}_{o(y)}^{s_{i}},$ $\displaystyle
y\in Y^{T}_{+},$ $\displaystyle\hat{\psi}_{i}(x_{y})$
$\displaystyle={P}_{s_{i}}^{o(y)}y{P}_{t(y)}^{s_{i}},$ $\displaystyle y\in
B^{+},$ $\displaystyle\hat{\psi}_{i}(\bar{x}_{y})$
$\displaystyle={P}_{s_{i}}^{t(y)}\bar{y}{P}_{o(y)}^{s_{i}},$ $\displaystyle
y\in B^{+}.$

######  Lemma 4.2.

Let $\hat{\psi}_{i}:Q_{1}\to K\Gamma$ be as described above. Then
$\hat{\psi}_{i}(J)\subseteq I_{\mathfrak{F}_{\Gamma}}$ and $\hat{\psi}_{i}$
gives a well defined (non-unital) $K$-algebra homomorphism from $\psi_{i}:Q\to
R_{\mathfrak{F}_{\Gamma}}$.

###### Proof.

It suffices to show that $\hat{\psi}_{i}$ sends the generators of $J$ to
$I_{\mathfrak{F}_{\Gamma}}$. Let $y\in Y^{T}_{+}$, then

$\displaystyle\hat{\psi}_{i}(f_{y}(t_{y}))$
$\displaystyle=[s_{i}]f_{y}(\hat{\psi}_{i}(t_{y}))[s_{i}]$
$\displaystyle=[s_{i}]f_{y}(P_{s_{i}}^{o(y)}(y\bar{y})P_{o(y)}^{s_{i}})[s_{i}]$
$\displaystyle=P_{s_{i}}^{o(y)}f_{y}(y\bar{y})P_{o(y)}^{s_{i}}\in
I_{\mathfrak{F}_{\Gamma}}.$

For $y\in B_{+}$, note that

$\displaystyle\hat{\psi}_{i}(x_{y}\bar{x}_{{y}})=\hat{\psi}_{i}(x_{y})\hat{\psi}_{i}(\bar{x}_{{y}})$
$\displaystyle=P_{s_{i}}^{o(y)}yP_{t(y)}^{s_{i}}P_{s_{i}}^{t(y)}\bar{y}P_{o(y)}^{s_{i}}$
$\displaystyle\equiv P_{s_{i}}^{o(y)}y[t(y)]\bar{y}P_{o(y)}^{s_{i}}\mod
I_{\mathfrak{F}_{\Gamma}}$ $\displaystyle\equiv
P_{s_{i}}^{o(y)}y\bar{y}P_{o(y)}^{s_{i}}\mod I_{\mathfrak{F}_{\Gamma}}.$

Thus, we have

$\displaystyle\hat{\psi}_{i}(f_{y}(x_{y}\bar{x}_{y}))$
$\displaystyle=[s_{i}]f_{y}(\hat{\psi}_{i}(x_{y}\bar{x}_{y}))[s_{i}]$
$\displaystyle=[s_{i}]f_{y}(P_{s_{i}}^{o(y)}(y\bar{y})P_{o(y)}^{s_{i}})[s_{i}]$
$\displaystyle\equiv P_{s_{i}}^{o(y)}f_{y}(y\bar{y})P_{o(y)}^{s_{i}}\mod
I_{\mathfrak{F}_{\Gamma}}.$

Since $f_{y}(y\bar{y})\in I_{\mathfrak{F}_{\Gamma}}$, we have
$\hat{\psi}_{i}(f_{y}(x_{y}\bar{x}_{y}))\in I_{\mathfrak{F}_{\Gamma}}$.
Similarly

$\hat{\psi}_{i}(\bar{x}_{{y}}x_{y})\equiv
P_{s_{i}}^{t(y)}\bar{y}yP_{t(y)}^{s_{i}}\mod I_{\mathfrak{F}_{\Gamma}}$

and

$\hat{\psi}_{i}(f_{y}(\bar{x}_{y}x_{y}))\equiv
P_{s_{i}}^{t(y)}f_{y}(\bar{y}y)P_{t(y)}^{s_{i}}\mod
I_{\mathfrak{F}_{\Gamma}},$

giving $\hat{\psi}_{i}(f_{y}(\bar{x}_{y}x_{y}))\in I_{\mathfrak{F}_{\Gamma}}$.
This proves the lemma. ∎

Thus, for each $i$, $1\leq i\leq N$, we have a well defined homomorphism of
the quotient rings $\psi_{i}:Q\to R_{\mathfrak{F}_{\Gamma}}$, given by

$\psi_{i}(q+J)=\hat{\psi}(q)+I_{\mathfrak{F}_{\Gamma}},\ q\in Q_{1}.$

######  Lemma 4.3.

For $1\leq i,j\leq N$ and $q\in Q$, we have

$\psi_{j}(q)=\widetilde{P_{s_{j}}^{s_{i}}}\psi_{i}(q)\widetilde{P_{s_{i}}^{s_{j}}}.$

###### Proof.

It is enough to show that this is true on the generators of $Q$. Using Lemma
4.1 and the definition of $\psi_{i}$, it is easy to check that for each

$g\in\\{\\{t_{y}\\}_{y\in Y^{T}_{+}},\ \\{x_{y},\bar{x}_{y}\\}_{y\in
B_{+}}\\},$

we have
$\widetilde{P_{s_{j}}^{s_{i}}}\psi_{i}(g)\widetilde{P_{s_{i}}^{s_{j}}}=\psi_{j}(g)$.
The details are left to the reader. ∎

### 4.5.

Let $\Psi:M_{N}(Q)\to R_{\mathfrak{F}_{\Gamma}}$ be the homomorphism of $K$
vector spaces from the matrix ring $M_{N}(Q)$ to $R_{\mathfrak{F}_{\Gamma}}$
which acts on basis elements of $M_{N}(Q)$ of the form $qe_{ij}$ as follows:

$\Psi(qe_{ij})=\psi_{i}(q)\widetilde{P_{s_{i}}^{s_{j}}},q\in Q,$

where $e_{ij}$ is the $N\times N$ matrix with $1$ in the $(i,j)$ position and
zeros elsewhere.

######  Lemma 4.4.

The map $\Psi:M_{N}(Q)\to R_{\mathfrak{F}_{\Gamma}}$ defined above is a
homomorphism of rings.

###### Proof.

It suffices to check that
$\Psi\left((q_{1}e_{ij})(q_{2}e_{kl})\right)=\Psi(q_{1}e_{ij})\Psi(q_{2}e_{kl})$,
$q_{1},q_{2}\in Q,1\leq i,j,k,l\leq N$.

If $j\not=k$, $\Psi\left((q_{1}e_{ij})(q_{2}e_{kl})\right)=\Psi(O)=0$, where
$O$ denotes the $N\times N$ zero matrix. On the other hand,
$\Psi(q_{1}e_{ij})\Psi(q_{2}e_{kl})=\psi_{i}(q_{1})\widetilde{P_{s_{i}}^{s_{j}}}\psi_{k}(q_{2})\widetilde{P_{s_{k}}^{s_{l}}}=0,$
since
$\psi_{k}(q_{2})\in\widetilde{[s_{k}]}R_{\mathfrak{F}_{\Gamma}}\widetilde{[s_{k}]}$.

If $j=k$, we have

$\displaystyle\Psi\left((q_{1}e_{ij})(q_{2}e_{jl})\right)$
$\displaystyle=\Psi\left((q_{1}q_{2}e_{il})\right)$
$\displaystyle=\psi_{i}(q_{1}q_{2})\widetilde{P_{s_{i}}^{s_{l}}}$
$\displaystyle=\psi_{i}(q_{1})\psi_{i}(q_{2})\widetilde{P_{s_{i}}^{s_{l}}}$
$\displaystyle=\psi_{i}(q_{1})\widetilde{P_{s_{i}}^{s_{j}}}\widetilde{P_{s_{j}}^{s_{i}}}\psi_{i}(q_{2})\widetilde{P_{s_{i}}^{s_{j}}}\widetilde{P_{s_{j}}^{s_{i}}}\widetilde{P_{s_{i}}^{s_{l}}}$
$\displaystyle=\psi_{i}(q_{1})\widetilde{P_{s_{i}}^{s_{j}}}\psi_{j}(q_{2})\widetilde{P_{s_{j}}^{s_{l}}},$

by lemmas 4.1 and 4.3. Thus
$\Psi\left((q_{1}e_{ij})(q_{2}e_{jl})\right)=\Psi(q_{1}e_{ij})\Psi(q_{2}e_{jl})$.

∎

To show that $\Psi$ is an isomorphism, we construct an inverse homomorphism
$\Phi:R_{\mathfrak{F}_{\Gamma}}\to M_{N}(Q)$. Let $\phi:K\Gamma\to M_{N}(Q)$
be defined as follows on the vertices and edges of $\Gamma$ (which generate
$K\Gamma$ as a $K$-algebra):

$\displaystyle\phi([s_{i}])$ $\displaystyle=e_{ii},s_{i}\in S$
$\displaystyle\phi(y)$
$\displaystyle=\begin{cases}e_{o^{\prime}(y)t^{\prime}(y)},&y\in Y^{T}_{+}\\\
t_{\bar{y}}e_{o^{\prime}(y)t^{\prime}(y)},&y\in\overline{Y}^{T}_{+}\\\
x_{y}e_{o^{\prime}(y)t^{\prime}(y)},&y\in B_{+}\\\
\bar{x}_{\bar{y}}e_{o^{\prime}(y)t^{\prime}(y)},&y\in\overline{B}_{+}\\\
\end{cases}$

Since $e_{ij}e_{kl}\not=0$ if and only if $j=k$, It is not difficult to see
that $\phi$ can be extended to a well defined homomorphism of $K$-algebras:

$\phi:K\Gamma\to M_{N}(Q).$

######  Lemma 4.5.

Let $\phi:K\Gamma\to M_{N}(Q)$ be the $K$-algebra homomorphism defined above,
then $I_{\mathfrak{F}_{\Gamma}}\subseteq\ker\phi$.

###### Proof.

It is enough to show that the generators of $I_{\mathfrak{F}_{\Gamma}}$,
$\\{f_{y}(y\bar{y}),y\in Y_{1}\\}$, are in $\ker\phi$. If $y\in Y^{T}\subseteq
Y_{1}$, then $\phi(y\bar{y})=\phi(y)\phi(\bar{y})$ is either
$t_{y}e_{o^{\prime}(y)o^{\prime}(y)}$ or
$t_{\bar{y}}e_{o^{\prime}(y)o^{\prime}(y)}$. Thus
$\phi\left(f_{y}(y\bar{y})\right)=f_{y}(t_{y})e_{o^{\prime}(y)o^{\prime}(y)}=O$
or
$\phi\left(f_{y}(y\bar{y})\right)=f_{y}(t_{\bar{y}})e_{o^{\prime}(y)o^{\prime}(y)}=f_{\bar{y}}(t_{\bar{y}})e_{o^{\prime}(y)o^{\prime}(y)}=O$
where $O$ is the zero matrix in $M_{N}(Q)$.

If $y\in B_{+}\cap Y_{1}$, then

$\phi(y\bar{y})=x_{y}e_{o^{\prime}(y)t^{\prime}(y)}\bar{x}_{y}e_{t^{\prime}(y)o^{\prime}(y)}=x_{y}\bar{x}_{y}e_{o^{\prime}(y)o^{\prime}(y)}.$

Thus, as before,
$\phi\left(f_{y}(y\bar{y})\right)=f_{y}(x_{y}\bar{x}_{y})e_{o^{\prime}(y)o^{\prime}(y)}=O$
where $O$ is the zero matrix in $M_{N}(Q)$.

For $y\in\overline{B}_{+}\cap Y_{1},$ we have

$\displaystyle\phi(y\bar{y})$
$\displaystyle=\bar{x}_{\bar{y}}x_{\bar{y}}e_{o^{\prime}(y)t^{\prime}(y)}e_{t^{\prime}(y)o^{\prime}(y)}$
$\displaystyle=\bar{x}_{\bar{y}}x_{\bar{y}y}e_{o^{\prime}(y)o^{\prime}(y)}.$

Thus
$\phi\left(f_{y}(y\bar{y})\right)=f_{y}(x_{y}\bar{x}_{y})e_{o^{\prime}(y)o^{\prime}(y)}=O$,
where $O$ is the zero matrix in $M_{N}(Q)$.

∎

By the above lemma, the quotient map

$\Phi:R_{\mathfrak{F}_{\Gamma}}\to M_{N}(Q)$

is a well defined ring homomorphism, with $\Phi(\tilde{p})=\phi(p)$, for $p\in
K\Gamma$.

We now show that $\Phi=\Psi^{-1}$ and thus we have that
$R_{\mathfrak{F}_{\Gamma}}$ is isomorphic to $M_{N}(Q)$ as a $K$-algebra.

######  Lemma 4.6.

Let $\phi:K\Gamma\to M_{N}(Q)$ be as defined above and let $y\in Y^{T}_{+}$.
Then $\phi(y^{\vee})=e_{t^{\prime}(y)o^{\prime}(y)}$ and
$\phi(P_{s_{k}}^{s_{l}})=e_{kl},1\leq k,l\leq N$

###### Proof.

If $y\in Y^{T}_{+}$, then (as pointed out in the proof of Lemma 3.2),
$f_{y}(t)=th(t)-\kappa$ for some $\kappa\not=0\in K$ and $h(t)\in K[t]$. We
had $y^{\vee}=\frac{1}{\kappa}\bar{y}h(y\bar{y})$. Thus,

$\phi(y^{\vee})=\frac{1}{\kappa}t_{y}h(t_{y})e_{t^{\prime}(y)o^{\prime}(y)}=\frac{1}{\kappa}\left(f_{y}(t_{y})+\kappa\right)e_{t^{\prime}(y)o^{\prime}(y)}=1_{Q}e_{t^{\prime}(y)o^{\prime}(y)}=e_{t^{\prime}(y)o^{\prime}(y)}.$

Recall that for $1\leq i,j\leq N$,
$P_{s_{i}}^{s_{j}}=\alpha(y_{1})\alpha(y_{2})\dots\alpha(y_{n})$, where
$y_{1}y_{2}\dots y_{n}$ is the geodesic in $T$ from $s_{i}$ to $s_{j}$. Now
$\alpha(y_{k})=y_{k}$, if $y_{k}\in Y_{+}^{T}$ and
$\alpha(y_{k})=\bar{y}_{k}^{\vee}$ if $y_{k}\in\overline{Y}_{+}^{T}$. Thus
since $\phi(y)=e_{o^{\prime}(y)t^{\prime}(y)}$ and
$\phi({y}^{\vee})=e_{t^{\prime}(y)o^{\prime}(y)}$ for $y\in Y_{+}^{T}$, the
result follows. ∎

######  Lemma 4.7.

Let $\Phi:R_{\mathfrak{F}_{\Gamma}}\to M_{N}(Q)$ and $\Psi:M_{N}(Q)\to
R_{\mathfrak{F}_{\Gamma}}$ be as defined above. Then, the composition
$\Phi\circ\Psi$ is the identity map on $M_{N}(Q)$.

###### Proof.

It suffices to show that $\Phi\circ\Psi$ is the identity on the following set
of generators of $M_{N}(Q)$:

$\left\\{e_{ij}\right\\}_{1\leq i,j\leq
N}\bigcup\left\\{t_{y}e_{ij}\right\\}_{y\in
Y^{T}_{+}}\bigcup\left\\{x_{y}e_{ij},\ \bar{x}_{y}e_{ij}\right\\}_{y\in
B_{+}}.$

We have
$\Phi(\Psi(e_{ij}))=\Phi\left(\psi_{i}(1_{Q})\widetilde{P_{s_{i}}^{s_{j}}}\right)=\Phi(\widetilde{[s_{i}]})e_{ij}=e_{ii}e_{ij}=e_{ij}$
for $1\leq i,j,\leq N$.

Next consider $t_{y}e_{ij}$ where $y\in Y^{T}_{+}$ and $1\leq i,j\leq N$. In
this case, we have

$\displaystyle\Phi(\Psi(t_{y}e_{ij}))$
$\displaystyle=\Phi\left(\psi_{i}(t_{y})\widetilde{P_{s_{i}}^{s_{j}}}\right)$
$\displaystyle=\Phi\left(\widetilde{P_{s_{i}}^{o(y)}}\widetilde{y\bar{y}}\widetilde{P_{o(y)}^{s_{i}}}\widetilde{P_{s_{i}}^{s_{j}}}\right)$
$\displaystyle=\Phi(\widetilde{P_{s_{i}}^{o(y)}}\widetilde{y\bar{y}}\widetilde{P_{o(y)}^{s_{j}}})$
$\displaystyle=e_{io^{\prime}(y)}\Phi(\widetilde{y\bar{y}})e_{o^{\prime}(y)j}$
$\displaystyle=e_{io^{\prime}(y)}e_{o^{\prime}(y)t^{\prime}(y)}t_{y}e_{t^{\prime}(y)o^{\prime}(y)}e_{o^{\prime}(y)j}$
$\displaystyle=t_{y}e_{ij}.$

If $y\in B_{+}$, then

$\displaystyle\Phi(\Psi(x_{y}e_{ij}))$
$\displaystyle=\Phi\left(\psi_{i}(x_{y})\widetilde{P_{s_{i}}^{s_{j}}}\right)=\Phi\left(\widetilde{P_{s_{i}}^{o(y)}}\tilde{y}\widetilde{P_{t(y)}^{s_{i}}}\widetilde{P_{s_{i}}^{s_{j}}}\right)=\Phi\left(\widetilde{P_{s_{i}}^{o(y)}}\tilde{y}\widetilde{P_{t(y)}^{s_{j}}}\right)$
$\displaystyle=e_{io^{\prime}(y)}\Phi(\tilde{y})e_{t^{\prime}(y)j}=e_{io^{\prime}(y)}x_{y}e_{o^{\prime}(y)t^{\prime}(y)}e_{t^{\prime}(y)j}=x_{y}e_{ij}.$

Finally, if $y\in B_{+}$, we have

$\displaystyle\Phi(\Psi(\bar{x}_{y}e_{ij}))$
$\displaystyle=\Phi\left(\psi_{i}(\bar{x}_{y})\widetilde{P_{s_{i}}^{s_{j}}}\right)=\Phi\left(\widetilde{P_{s_{i}}^{t(y)}}\tilde{\bar{y}}\widetilde{P_{o(y)}^{s_{i}}}\widetilde{P_{s_{i}}^{s_{j}}}\right)=\Phi\left(\widetilde{P_{s_{i}}^{t(y)}}\tilde{\bar{y}}\widetilde{P_{o(y)}^{s_{j}}}\right)$
$\displaystyle=e_{it^{\prime}(y)}\Phi(\tilde{\bar{y}})e_{o^{\prime}(y)j}=e_{it^{\prime}(y)}\bar{x}_{y}e_{t^{\prime}(y)o^{\prime}(y)}e_{o^{\prime}(y)j}=\bar{x}_{y}e_{ij}$

This completes the proof of the lemma. ∎

######  Lemma 4.8.

Let $\Phi:R_{\mathfrak{F}_{\Gamma}}\to M_{N}(Q)$ and $\Psi:M_{N}(Q)\to
R_{\mathfrak{F}_{\Gamma}}$ be as defined above. Then, then composition
$\Psi\circ\Phi$ is the identity map on $R_{\mathfrak{F}_{\Gamma}}$.

###### Proof.

It is enough to demonstrate that this is true on the generators of the algebra
$R_{\mathfrak{F}_{\Gamma}}$, $\\{\widetilde{[s_{i}]}\\}_{1\leq i\leq N}$ and
$\\{\tilde{y}\\}_{y\in Y}$. First, we look at the paths of length $0$. Let
$s_{i}\in S$, then

$\Psi\left(\Phi(\widetilde{[s_{i}]})\right)=\Psi(e_{ii})=\psi_{i}(1_{Q})\widetilde{P_{s_{i}}^{s_{i}}}=\widetilde{[s_{i}]}\widetilde{[s_{i}]}=\widetilde{[s_{i}]}.$

For $y\in Y_{+}^{T}$,
$\Psi\left(\Phi(\tilde{y})\right)=\Psi(e_{o^{\prime}(y)t^{\prime}(y)})=\psi_{o^{\prime}(y)}(1_{Q})\widetilde{P_{o(y)}^{t(y)}}=\widetilde{[s_{o^{\prime}(y)}]}\tilde{y}=\tilde{y}.$

When $y\in\overline{Y_{+}^{T}}$, we have

$\Psi\left(\Phi(\tilde{y})\right)=\Psi\left(t_{\bar{y}}e_{o^{\prime}(y)t^{\prime}(y)}\right)=\psi_{o^{\prime}(y)}(t_{\bar{y}})\widetilde{P_{o(y)}^{t(y)}}=\widetilde{P_{o(y)}^{t(y)}}\tilde{\bar{y}}\tilde{y}\widetilde{P_{t(y)}^{o(y)}}\widetilde{P_{o(y)}^{t(y)}}=\widetilde{P_{o(y)}^{t(y)}}\tilde{\bar{y}}\tilde{y}=\widetilde{{\bar{y}}}^{\vee}\tilde{\bar{y}}\tilde{y}=\tilde{y},$

by Lemma 3.2 and the definition of $P_{s_{i}}^{s_{j}}$.

Next we consider the case when $y\in B_{+}$. Here we have

$\Psi\left(\Phi(\tilde{y})\right)=\Psi(x_{y}e_{o^{\prime}(y)t^{\prime}(y)})=\psi_{o^{\prime}(y)}(x_{y})\widetilde{P_{o(y)}^{t(y)}}=\widetilde{P_{o(y)}^{o(y)}}\tilde{y}\widetilde{P_{t(y)}^{o(y)}}\widetilde{P_{o(y)}^{t(y)}}=\widetilde{[o(y)]}\tilde{y}\widetilde{[t(y)]}=\tilde{y}.$

Finally, we let $y\in\overline{B}_{+}$. In this case we get

$\displaystyle\Psi\left(\Phi(\tilde{y})\right)$
$\displaystyle=\Psi\left(\bar{x}_{\bar{y}}e_{o^{\prime}(y)t^{\prime}(y)}\right)$
$\displaystyle=\psi_{o^{\prime}(y)}\left(\bar{x}_{\bar{y}}\right)\widetilde{P_{o(y)}^{t(y)}}$
$\displaystyle=\widetilde{P_{o(y)}^{o(y)}}\tilde{\bar{\bar{y}}}\widetilde{P_{t(y)}^{o(y)}}\widetilde{P_{o(y)}^{t(y)}}$
$\displaystyle=\widetilde{[o(y)]}\tilde{y}\widetilde{[t(y)]}=\tilde{y}.$

This concludes the proof of the lemma. ∎

######  Definition 4.9.

(Cohn [8], Section 3) let $K$ is a field. The $K$-algebra $R$ is said to be
the free product of the $K$-algebras $\\{R_{i}\\}_{i\in I}$ (over $K$) if
$\\{R_{i}\\}_{i\in I}$ forms a family of $R$ such that

  1. (i)

$R_{i}\cap R_{j}=K$ for $i\not=j$,

  2. (ii)

if $X_{i}$ is a set of generators of $R_{i}$, $i\in I$, then
$\bigcup_{I}X_{i}$ is a set of generators of $R$,

  3. (iii)

If $C_{i}$ is a set of defining relations of $R_{i},i\in I$ (in terms of the
set of generators $X_{i}$) then $\bigcup_{I}C_{i}$ is a set of defining
relations of $R$ (in terms of the set of generators $\bigcup_{I}X_{i}$).

We summarize the results of the above discussion in the following Theorem:

######  Theorem 4.10.

Let $K$ be a field and let $\Gamma=(S,Y)$ be a graph with a finite number of
vertices and edges. Let $\mathfrak{F}_{\Gamma}=\\{f_{y}(t)\\}_{y\in
Y_{1}\subseteq Y}$ be a set of polynomials in $K[t]$ with property F. If
$\Gamma$ has a spanning tree $T=(S,Y^{T})$ with edges $Y^{T}\subseteq Y_{1}$,
then we can define an orientation, $Y=Y^{+}\bigcupdot\overline{Y^{+}}$ on
$\Gamma$, such that $R_{\mathfrak{F}_{\Gamma}}$ is isomorphic to the matrix
ring $M_{N}(Q)$, where $N$ is the cardinality of $S$ and $Q$ is the free
product of the following rings:

$\begin{cases}K[t]/f_{y}(t)&y\in Y_{T}\cap Y^{+}\\\
K[x_{y},\overline{x_{y}}]/\langle
f_{y}(x_{y}\overline{x_{y}}),f_{y}(\overline{x_{y}}x_{y})\rangle&y\in(Y_{1}\cap
Y^{+})\backslash(Y_{T}\cap Y^{+})\\\ K[x_{y},\overline{x_{y}}]&y\in
Y^{+}\backslash(Y_{1}\cap Y^{+})\\\ \end{cases}$

The proof of the following lemma is identical to the proof of Theorem 6.6 in
Pilkington [27], where a proof is given for the field $\mathbb{Q}$:

######  Lemma 4.11.

let $K$ be a field and let $f(t)$ be a non-constant polynomial in $K[t]$ with
a non-zero constant term. Let $K[x\overline{x}]$ be the ring of polynomials
over $K$ in the non-commuting variables $x$ and $\overline{x}$. Let $R_{f}$
denote the quotient ring

$R_{f}=K[x,\overline{x}]/\langle f(x\overline{x}),f(\overline{x}x)\rangle.$

Then $R_{f}$ is isomorphic to a free product

$K[z,z^{-1}]\ast_{K}K^{f},$

where $K^{f}$ is the ring extension $K[t]/\langle f(t)\rangle$ of $K$.

Lemma 4.11 and Theorem 4.10 give us the following:

######  Corollary 4.12.

Let $K$ be a field and let $\Gamma=(S,Y)$ be an undirected graph with a finite
number of vertices and edges. Let $\mathfrak{F}_{\Gamma}=\\{f_{y}(t)\\}_{y\in
Y_{1}\subseteq Y}$ be a set of polynomials in $K[t]$ with property F. If
$\Gamma$ has a spanning tree $T=(S,Y^{T})$ with edges $Y^{T}\subseteq Y_{1}$,
then we can define an orientation, $Y=Y^{+}\bigcupdot\overline{Y^{+}}$ on
$\Gamma$, such that $R_{\mathfrak{F}_{\Gamma}}$ is isomorphic to the matrix
ring $M_{N}(Q)$, where $N$ is the cardinality of $S$ and $Q$ is the free
product of the following rings:

$\begin{cases}K[t]/f_{y}(t)&y\in Y_{1}\cap Y^{+}\\\
K[z_{y},{z_{y}}^{-1}]&y\in(Y_{1}\cap Y^{+})\backslash(Y_{T}\cap Y^{+})\\\
K[x_{y},\overline{x_{y}}]&y\in Y^{+}\backslash(Y_{1}\cap Y^{+})\\\
\end{cases}$

Note that Corollary 4.12 tells us that the free product $Q$ is independent of
the spanning tree chosen. In particular, the free product $Q$ has one factor
of the form $K[t]/f_{y}(t)$ where $y$ is a geometric edge in $Y_{1}$ and one
ring corresponding to each fundamental loop (the number of which is an
invariant). The ring corresponding to each fundamental loop is either a ring
of Laurent polynomials or a ring of polynomials over two non-commuting
indeterminates, depending on whether the edge defining it in in $Y_{1}$ or
not. Since all edges which are not in $Y_{1}$, determine a fundamental loop,
the number of polynomial rings is determined and the tree we choose does not
affect the outcome.

##  5\. Coxeter Systems and Associated Path Algebras

In this section, we will apply the results of our previous section to finite
rank Coxeter Systems. In many cases of interest, including the irreducible
Weyl groups, we will show that some of the algebras studied in Dyer [17] and
Pilkington [27], are isomorphic to matrix rings over free products of rings.

### 5.1.

A finite rank Coxeter matrix is a matrix $M=(m_{ij})_{1\leq i,j\leq N}$, with
$m_{ii}=1$ and $m_{ij}=m_{ji}\in\mathbb{N}_{\geq 2}\cup\\{\infty\\}$, $1\leq
i,j\leq N$, $i\not=j$. For $S=\\{s_{i}\\}_{1\leq i\leq N}$, the corresponding
Coxeter group is the group with presentation

$W=\langle s_{i}(1\leq i\leq N)|(s_{k}s_{l})^{m_{kl}}=1\ \mbox{for}\
s_{k},s_{l}\in S\ \mbox{with}\ m_{kl}\not=\infty\rangle.$

The pair $(W,S)$ is called a Coxeter system with Coxeter matrix $M$.

We can associate to a Coxeter system $(W,S)$ a graph $\Gamma_{W,S}=(S,Y)$ with
vertices $s_{i}\in S$ and edges $Y=\left\\{y_{ij}=[s_{i}s_{j}]|\ i\not=j\
\mbox{and}\ m_{ij}\geq 3\right\\}$. We let $\mathfrak{P}_{W,S}$ denote the set
of paths in $\Gamma_{W,S}$. Since this graph does not have loops or multiple
edges, one can describe edges and paths in the graph uniquely by the sequence
of vertices that they pass through. We will also frequently use $y_{ij}$ to
denote the edge $[s_{i},s_{j}]\in Y$. Let $\hat{P}_{W,S}$ denote the path
algebra $\mathbb{Q}\Gamma_{W,S}$.

For $m\in\mathbb{Z},m\geq 3$, let $C_{m}(t)$ denote the minimum polynomial of
$\displaystyle 4\cos^{2}\frac{\pi}{m}$ in $\mathbb{Z}[t]$. We have

$C_{3}(t)=t-1,\ C_{4}(t)=t-2,\ C_{5}(t)=t^{2}-3t+1,\ C_{6}(t)=t-3,\dots.$

Let $Y_{1}=\\{y_{ij}\in Y|3\leq m_{ij}<\infty\\}\subseteq Y$. Then
$\overline{Y_{1}}=Y_{1}$. We let
$\mathfrak{F}_{\Gamma_{W,S}}=\\{C_{y_{ij}}(t)=C_{m_{ij}}(t)|y_{ij}\in
Y_{1}\\}\subset\mathbb{Q}[t]$. Since $C_{y}(t)=C_{\bar{y}}(t)$ for all $y\in
Y_{1}$ and each polynomial in non-constant and has a non-zero constant term,
$\mathfrak{F}_{\Gamma_{W,S}}$ has property $F$. The definition of
${R}_{\mathfrak{F}_{\Gamma_{W,S}}}$ (as a $\mathbb{Q}$-algebra) coincides with
the definition of $\hat{R}_{W,S}$ studied in Pilkington [27] and Dyer [17].

######  Definition 5.1.

we let $K_{m}=\mathbb{Q}[t]/\langle C_{m}(t)\rangle$, denote the field
extension
$\displaystyle\mathbb{Q}\left[4\cos^{2}\left(\frac{\pi}{m}\right)\right]$ of
$\mathbb{Q}$.

Applying the results of the previous section as summarized in Theorem 4.10 and
Corollary 4.12, we get

######  Theorem 5.2.

Let $(W,S)$ be a finite rank Coxeter system, with Coxeter graph $\Gamma_{W,S}$
as described above. Let $Y_{1}=\\{y_{ij}\in Y|3\leq m_{ij}<\infty\\}$. Suppose
that there exists a spanning tree, $T$, for $\Gamma_{W,S}$, whose geometric
edges are denoted by $Y^{T}$, with the property that $Y^{T}\subseteq Y_{1}$.
Then we have a unital ring isomorphism

$\hat{R}_{W,S}\cong M_{N}(Q),$

where $Q$ is isomorphic to the free product of the following rings;

$\begin{matrix}K_{m_{ij}},&3\leq m_{ij}<\infty,&i<j,\\\
\mathbb{Q}[y_{ij},y_{ij}^{-1}],&y_{ij}\in Y\backslash Y_{T},&m_{ij}<\infty,\\\
\mathbb{Q}[x_{ij},\bar{x}_{ij}],&y_{ij}\in Y\backslash
Y_{T},&m_{ij}=\infty.\\\ \end{matrix}$

######  Example 1.

Let $(W,S)$ be the Coxeter system with Coxeter matrix

$\left(\begin{array}[]{ccccc}1&3&2&4&2\\\ 3&1&5&2&2\\\ 2&5&1&6&5\\\
4&2&6&1&\infty\\\ 2&2&5&\infty&1\end{array}\right),$

then $(W,S)$ be a Coxeter system with generators
$S=\\{s_{1}=r,s_{2}=s,s_{3}=t,s_{4}=u,s_{5}=v\\}$ and relations

$r^{2}=s^{2}=t^{2}=u^{2}=v^{2}=1=(rs)^{3}=(st)^{5}=(tu)^{6}=(tv)^{5}=(ru)^{4}=(rt)^{2}=(su)^{2}=(vr)^{2}=(vs)^{2}.$

Let $\Gamma_{W,S}=(S,Y)$ be the associated graph. Below, on the right, we show
the geometric edges of $\Gamma_{W,S}$, each geometric edge $\\{s_{i},s_{j}\\}$
is labelled with corresponding $m_{ij}$. On the left we label a set of
directed edges
$Y^{+}=\\{y_{\alpha},y_{\beta},y_{\gamma},y_{\delta},y_{\epsilon},y_{\zeta}\\}$.
Clearly $Y=Y^{+}\bigcupdot\overline{Y^{+}}$.

|
---|---
$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{y_{\epsilon}}$$\textstyle{t\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{y_{\zeta}}$$\textstyle{v}$$\textstyle{{r}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{y_{\alpha}}$$\scriptstyle{y_{\gamma}}$$\textstyle{{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{y_{\beta}}$$\scriptstyle{y_{\delta}}$ |
---|---
$\textstyle{s\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{5}$$\textstyle{t\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{5}$$\textstyle{v}$$\textstyle{{r}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{3}$$\scriptstyle{4}$$\textstyle{{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{6}$$\scriptstyle{\infty}$

With $Y_{1}=\\{y_{ij}|3\leq
m_{ij}<\infty\\}=Y\backslash\\{y_{\delta},\overline{y_{\delta}}\\}$, we have
$\mathfrak{F}_{\Gamma_{W,S}}=\\{C_{m_{ij}}(t)|y_{ij}\in
Y_{1}\\}\subset\mathbb{Q}[t]$.

Thus
$R_{\mathfrak{F}_{\Gamma_{W,S}}}=\mathbb{Q}\Gamma_{W,S}/I_{\mathfrak{F}_{\Gamma_{W,S}}}$,
where $I_{\mathfrak{F}_{\Gamma_{W,S}}}$ is the two sided ideal of
$\mathbb{Q}\Gamma_{W,S}$ generated by the following

$\begin{array}[]{lll}C_{3}({y_{\alpha}}\overline{y_{\alpha}})=[rsr]-[r],&C_{4}({{y}_{\gamma}}\overline{y_{\gamma}})=[rur]-2[r],&C_{6}({{y}_{\beta}}\overline{y_{\beta}})=[utu]-3[u],\\\\[10.00002pt]
C_{3}({\overline{y_{\alpha}}}y_{\alpha})=[srs]-[s],&C_{4}({\overline{y_{\gamma}}{y}_{\gamma}})=[uru]-2[u],&C_{6}(\overline{y_{\beta}}y_{\beta})=[tut]-3[t]\\\\[10.00002pt]
C_{5}({{y}_{\epsilon}}\overline{y_{\epsilon}})=[ststs]-3[sts]+[s],&C_{5}({{y}_{\zeta}}\overline{y_{\zeta}})=[tvtvt]-3[tvt]+[t],&\\\\[10.00002pt]
C_{5}({\overline{y_{\epsilon}}}y_{\epsilon})=[tstst]-3[tst]+[t],&C_{5}(\overline{y_{\zeta}}y_{\zeta})=[vtvtv]-3[vtv]+[v].&\\\\[10.00002pt]
\end{array}$

Below, we show a maximal tree $T=(S,Y^{T})$ where
$Y^{T}=Y\backslash\\{y_{\delta},\overline{y_{\delta}},y_{\epsilon},\overline{y_{\epsilon}}\\}$.

|
---|---
$\textstyle{s}$$\textstyle{t\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{5}$$\textstyle{v}$$\textstyle{{r}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{3}$$\scriptstyle{4}$$\textstyle{{u}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{6}$

Clearly $Y^{T}\subset Y_{1}$, hence, we can apply Corollary 4.12 to get
$R_{\mathfrak{F}_{\Gamma_{W,S}}}\cong M_{5}(Q)$, where $Q$ is a free product
of the following rings over $\mathbb{Q}$:

$K_{3}\cong\mathbb{Q},K_{4}\cong\mathbb{Q},K_{5},K_{5},K_{6}\cong\mathbb{Q},\mathbb{Q}[x_{y_{\epsilon}},x_{y_{\epsilon}}^{-1}],\mathbb{Q}[x_{y_{\delta}},\overline{x_{y_{\delta}}}]\\}$

##  6\. Cohn Path Algebras

In this section, we give an application of Theorem 4.10 by giving a proof of
the fact that Cohn path algebras. satisfy the rank condition. This implies
that they have invariant basis number, which has already been proven in
Abrahms and Kanuni [2]. Cohn path algebras are normally defined on directed
graphs, we adapt the definition to the situation where we have an oriented
graph. Let $\Gamma=(S,Y)$ be a connected graph with a finite vertex set $S$
and a finite set of edges $Y$. Let $Y^{+}\bigcup\overline{Y^{+}}$ be an
orientation on $\Gamma$.

######  Definition 6.1.

The Cohn Path algebra $C(\Gamma)$(relative to the orientation
$Y=Y^{+}\bigcup\overline{Y^{+}}$ over a field $K$ is defined as the quotient
of the path algebra $K\Gamma$ by the ideal generated by the set
$\\{\bar{y}y-[t(y)]|y\in Y^{+}\\}$.

It can be shown that for each such Cohn path algebra of a graph $\Gamma$,
there exists a graph $\Gamma^{\prime}$ such that the Leavitt Path Algebra of
$\Gamma^{\prime}$ is $C(\Gamma)$, see Abrahms et al. [1].

Consider the set of polynomials
$\mathfrak{F}_{\Gamma}=\\{f_{y}(t)=t^{2}-1|y\in Y\\}\subset K[t]$. It is not
difficult to see that $\mathfrak{F}$ has property $F$. We see also that
$R_{\mathfrak{F}_{\Gamma}}$ is the quotient of $C(\Gamma)$ by the ideal
generated by $\\{\bar{y}y-[t(y)]|y\in\overline{Y^{+}}\\}$.

######  Theorem 6.2.

Let $\Gamma=(S,Y)$ be a finite graph with an orientation
$Y=Y^{+}\bigcup\overline{Y^{+}}$. Let $K$ be a field and let
$\mathfrak{F}_{\Gamma}=\\{f_{y}(t)=t^{2}-1|y\in Y\\}\subset K[t]$. Then
$R_{\mathfrak{F}_{\Gamma}}$ is isomorphic to $M_{N}(Q)$ where $Q$ is a free
product of Laurent polynomial rings over $K$, and $N$ is the cardinality of
$S$.

###### Proof.

Since any maximal spanning tree of $\Gamma$ must have edges in $Y_{1}=Y$, we
can apply Theorem 4.10 and Corollary 4.12 for any such tree $T=(S,Y^{T})$.
Thus we have that $R_{\mathfrak{F}_{\Gamma}}$ is isomorphic to $M_{N}(Q)$
where $N$ is the cardinality of $S$ and $Q$ is a free product over $K$ of the
following rings:

$\begin{matrix}K_{y}=K[t]/\langle t-1\rangle,&y\in Y\cap Y^{+}=Y^{+}\\\
K[x_{y},x_{y}^{-1}],&y\in Y^{+}\backslash(Y^{T}\cap Y^{+})\\\ \end{matrix}$

Since $K_{y}=K[t]/\langle t-1\rangle\cong K$, $Q$ is just the free product of
rings of Laurent polynomials over $K$. ∎

Below, we give definitions of three successively stronger ring conditions. See
Cohn [10], section 0.2 for more details.

######  Definition 6.3.

A ring $R$ is said to have the invariant basis number (IBN) property if every
free $R$ module has unique rank.

The following are Equivalent:

  * •

$R$ has the IBN property,

  * •

For all $m,n\in\mathbb{N}_{>0}$, $R^{n}\cong R^{m}$ implies $m=n$,

  * •

if $A\in M_{n\times m}(R)$ and $B\in M_{m\times n}(R)$ with $AB=I_{n}$ and
$BA=I_{m}$, then $m=n$.

######  Definition 6.4.

A ring $R$ is said to have the unbounded generator number property (UGN) (or
satisfies the rank condition) if for every $n\in\mathbb{N}_{>0}$ there is a
finitely generated left $R$ module which cannot be generated by $n$ elements.

The following are Equivalent:

  * •

$R$ has the UGN property,

  * •

If $R^{n}\cong R^{m}\oplus K$, for some $R$ module $K$, we must have $n\geq
m$,

  * •

For any $A\in M_{m\times n}(R),B\in M_{n\times m}(R)$, if $AB=I_{m}$, then
$n\geq m$.

######  Definition 6.5.

A ring $R$ is said to be weakly $n$-finite if every generating set of $n$
elements in $R^{n}$ is free. If this holds for all $n\in\mathbb{N}_{>0}$, then
$R$ is said to be weakly finite (WF) (also called stably finite).

The following are Equivalent:

  * •

$R$ is weakly finite,

  * •

If $R^{n}\cong R^{n}\oplus K$, for some $R$ module $K$, we must have $K=0$,

  * •

For any $A,B\in M_{n\times n}(R)$, if $AB=I_{n}$, then $BA=I_{n}$.

######  Definition 6.6.

Cohn [10] (Sections 1.1 and 1.2) A free right ideal ring is an integral domain
$R$ with invariant basis number, such that all right ideals of $R$ are free
$R-modules$. A free left ideal ring is defined similarly and a free ideal ring
(fir) is a ring which is both a left and a right free ideal ring. A ring $R$
is a semifir if $R$ has IBN and every finitely generated left ideal is free
(equivalently every finitely generated right ideal is free). Every fir is a
semifir.

By Cohn [10], Corollary 1.2, If $R$ is a semifir, then $R$ is weakly finite.

######  Theorem 6.7.

A Cohn path algebra has the UGN property, that is; it satisfies the rank
condition.

###### Proof.

Let $\Gamma=(S,Y)$ be a graph with a finite number of vertices and edges and
$K$ a field. Let $C(\Gamma)$ be Cohn path algebra defined over $K$ with
respect to a given orientation on $\Gamma$. From Theorem 6.2 and the
observations made prior to it, we have a surjective homomorphism
$f:C(\Gamma)\to M_{n}(Q)$ where $Q$ is a free product of rings of Laurent
polynomials of the form $K[x,x^{-1}]$. By Cohn [9] Corollary 3 to Theorem 4.3,
$Q$ is a free ideal ring and hence is weakly finite. Thus $M_{n}(Q)$ is also
weakly finite by the matrix characterization of the property. By Proposition
0.2.2 in Cohn [10], if a ring $R$ has a homomorphic image which is weakly
finite, then it has the UGN property. This concludes the proof. ∎

## References

  * [1] Abrams, Gene and Ara, Pere and Siles Molina, Mercedes,  Leavitt Path Algebras,  Springer, 2017, isbn = 978-1-4471-7343-4
  * [2] Abrahms, G., Kanuni, M.  Cohn path Algebras have Invariant Basis Number.  Communications in Algebra, 44:1, 371-380 (2016)
  * [3] Bergman, G.  The Diamond Lemma for Ring Theory.  Advances in Mathematics 29,178-218 (1978)
  * [4] Björner, Anders and Brenti, Francesco,  Combinatorics of Coxeter groups,  Graduate Texts in Mathematics, Vol. 231,  Springer, New York, 2005
  * [5] N. Bourbaki.  Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines.  Actualités Scientifiques et Industrielles, No. 1337. Hermann, Paris, 1968.
  * [6] C. W. Curtis, N. Iwahori, and R. Kilmoyer.  Hecke algebras and characters of parabolic type of finite groups with $(B,$ $N)$-pairs.  Inst. Hautes Études Sci. Publ. Math., (40):81–116, 1971.
  * [7] Cohn, P. M.  Some remarks on the Invariant Basis Property.  Topology Vol. 5, pp. 215-228 (1966)
  * [8] Cohn, P. M.  On The Free Product of Associative Rings.  Math. Zeitschr. 71, 380-398 (1959)
  * [9] Cohn, P. M.  Free Ideal Rings.  Journal of Algebra I, 47-69 (1964)
  * [10] Cohn, P. M.  Free Rings and Their Relations (2nd edn),  LMS Monographs, No.19, Academic Press, New York (1985).
  * [11] Cohn, P. M.  On The Free Product of Associative Rings II, The Case of (Skew) Fields.  Math. Zeitschr. 73, 433-456 (1960)
  * [12] Cohn, P. M.  Introduction to Ring Theory.  Springer Undergraduate Mathematics Series, 2004.
  * [13] Dyer, M.  Hecke Algebras and Reflections in Coxeter Groups.  PhD thesis, Univ. of Sydney, 1987.
  * [14] Dyer, M.,  On conjugacy of abstract root bases of root systems of Coxeter groups,  Rocky Mountain J. Math., Vol. 48, No. 7, (2018) 2223-2287,
  * [15] Dyer, M.  Embeddings of root systems. I. Root systems over commutative rings.  J. Algebra, 321(11):3226–3248, 2009.
  * [16] Dyer, M.  Embeddings of root systems. II. Permutation root systems.  J. Algebra, 321(3):953–981, 2009.
  * [17] Dyer, M.  Root systems over non-commutative rings  Preprint, 2020
  * [18] Fu, Xiang,  Nonorthogonal geometric realizations of Coxeter groups.  J. Aust. Math. Soc., 97(2):180–211, 2014.
  * [19] Fu, Xiang,  On paired root systems of Coxeter groups,  J. Aust. Math. Soc., Vol. 105, No. 3 (2018) 347-365.
  * [20] Green E.L. (1999)  Noncommutative Gröbner Bases, and Projective Resolutions. In: Dräxler P., Ringel C.M., Michler G.O. (eds) Computational Methods for Representations of Groups and Algebras.  Progress in Mathematics, vol 173. Birkhäuser, Basel
  * [21] Green, E.L., Hille, L. & Schroll, S.  Algebras and Varieties. Algebras and Representation Theory (2020)
  * [22] Hée, Jean-Yves  Systèmes de racines sur un anneau commutatif totalement ordonné.  Geom. Ded., 37:65–102, 1991.
  * [23] Humphreys, James E.,  Reflection groups and Coxeter groups,  Cambridge Studies in Advanced Mathematics, 1990, Vol. 29  Cambridge University Press,  Cambridge
  * [24] Victor G. Kac.  Infinite-dimensional Lie algebras.  Cambridge University Press, Cambridge, 1990.
  * [25] Leamer M.J.  Gröbner finite path algebras. Journal of Symbolic Computation 41 (2006) 98-111
  * [26] Lusztig, G.,  Hecke algebras with unequal parameters,  CRM Monograph Series, 18 (2003),  American Mathematical Society, Providence, RI,
  * [27] Pilkington, A.,  On Reflection Representations of Coxeter Groups over Non-Commutative Rings,  Preprint (2021),  arXiv:2107.01530v1 [math.RT]
  * [28] Serre, J. P., translated by John Stillwell.  Trees.  Springer Verlag, 1980.
  * [29] Xu, Tianyuan,  On the subregular $J$-rings of Coxeter systems,  Algebr. Represent. Theory Vol. 22, No. 6 (2019) 1479-1512
  * [30] È. B. Vinberg.  Discrete linear groups that are generated by reflections.  Izv. Akad. Nauk SSSR Ser. Mat., 35:1072–1112, 1971.


# Exact Probabilities for Three and Four Dice in the Balanced Uniform Model of
3-Sided Dice

Kent E. Morrison  American Institute of Mathematics, 600 East Brokaw Road, San
Jose, CA 95112<EMAIL_ADDRESS>
(Date: March 8, 2023)

###### Abstract.

We determine the exact probabilities of the different isomorphism classes of
tournaments that result from random sets of three and four independent dice
drawn from the balanced uniform model of $3$-sided dice.

##  1\. Background and Results

By now it is well-recognized that various models of generalized dice exhibit
surprisingly high rates of intransitivity for randomly chosen dice. Given two
dice $A$ and $B$, where $A$ has face values $a_{1},\ldots,a_{n}$ and $B$ has
face values $b_{1},\ldots,b_{m}$, we say that $A$ dominates $B$, denoted by
$A\succ B$, if it is more likely for $A$ to show a higher value than $B$, that
is

$\sum_{i,j}\mbox{sgn}(a_{i}-b_{j})>0.$

If the sum is $0$, then neither die dominates the other and we say that the
result is a tie. In this article we will always be working with dice with the
same number of faces; i. e., $m=n$.

In 2016 Conrey, Gabbard, Grant, Liu, and Morrison [1] considered $n$-sided
dice as integer multisets of size $n$ with elements in $\\{1,2,\ldots,n\\}$
and satisfying $\sum a_{i}=n(n+1)/2$. We made two conjectures about random
sets of three $n$-sided dice as $n\rightarrow\infty$.

  * •

The probability of any ties goes to zero.

  * •

The probability of an intransitive triple goes to $1/4$.

For three dice $A,B,C$ and in the absence of ties there are $2^{3}$ possible
configurations for the relations between the three pairs $(A,B)$, $(B,C)$, and
$(A,C)$. Two of the eight configurations represent the intransitive cycles
$A\succ B\succ C\succ A$ and $A\succ C\succ B\succ A$. The other six
configurations are transitive chains. Evidence for the conjecture was provided
by Monte Carlo simulations showing that the probabilities of all eight
configurations appear to approach $1/8$, and so the probability of an
intransitive triple approaches $1/4$ and the probability of a transitive
triple approaches $3/4$. We also made much more speculative generalized
conjectures concerning $k$ random dice for any fixed positive integer $k$.
First, the probability that there is a tie between any of the $k$ dice goes to
$0$. With no ties there are $2^{\binom{k}{2}}$ outcomes for all pairwise
comparison, and each of these outcomes is represented by a complete directed
graph on $k$ vertices, i.e., a _tournament_. The second generalized conjecture
is that in the limit all the tournaments are equally probable.

A few years later these conjectures became the topic of a Polymath project. An
alternative model was introduced, the _balanced sequence model_ , in which an
$n$-sided die is a sequence $A=(a_{1},\ldots,a_{n})$ of elements in
$\\{1,2,\ldots,n\\}$ with total $n(n+1)/2$. The balanced sequence model is
easier to work than the multiset model. For example, a random die is now a
sequence of $n$ iid random variables uniform in $\\{1,\ldots,n\\}$ and
conditioned on the sum being $n(n+1)/2$. The main results in [3] are that the
conjectures for three dice hold for the balanced sequence model. Thus, the
questions for three dice in the multiset model are still open, but it would be
a surprise if they turn out to be false.

At the same time the Polymath project spurred some other work, and there is
strong computational evidence that the generalized conjecture about
tournaments fails with four dice. If the $2^{\binom{4}{2}}$ tournaments were
all equally probable, then the probability of a transitive chain and the
probability of an intransitive cycle would both have limit $3/8=0.375$, but
several independent simulations done for both the multiset and the sequence
models produce data with the experimental probabilities somewhat greater than
$0.38$.

Further evidence appears in the results of Cornacchia and Hązła [2] for four
dice in the balanced uniform model. In this model a random $n$-sided die is a
point $(a_{1},\ldots,a_{n})\in[0,1]^{n}$ chosen uniformly and conditioned on
$\sum_{i}a_{i}=n/2$. They prove that there exists $\varepsilon>0$ such that
for $n$ sufficiently large, the probability is greater than $3/8+\varepsilon$
that four random dice have a transitive tournament. In the same paper they
prove that, in fact, the conjectures do hold for three dice in the balanced
uniform model. That is, as $n\rightarrow\infty$, the probability that three
$n$-sided dice form an intransitive triple approaches $1/4$, and the
probability that they form a transitive chain approaches $3/4$.

In this note we consider random sets of three dice and four dice at the other
extreme with $n=3$, which is the least number of sides of any interest. With
three dice there are eight tournaments in two isomorphism classes. One
isomorphism class consists of the six transitive chains and the other class
contains the two intransitive cycles. We find the the transitive probability
is exactly $973/1230=0.76015625$ and the intransitive probability is exactly
$307/1280=0.23984375$. With four dice the 64 tournaments fall into four
different isomorphism classes: the 24 completely transitive chains, the 24
intransitive cycles, the 8 tournaments with an overall winner and a 3-cyle,
and the 8 tournaments with an overall loser and a 3-cycle. We find the
probabilities are:

$\displaystyle\text{transitive}\quad\frac{110413771}{25804800}$
$\displaystyle\approx 0.42788$
$\displaystyle\text{intransitive}\quad\frac{99930571}{25804800}$
$\displaystyle\approx 0.38726$ $\displaystyle\text{winner +
3-cycle}\quad\frac{23851829}{25804800}$ $\displaystyle\approx 0.09243$
$\displaystyle\text{loser + 3-cycle}\quad\frac{23851829}{25804800}$
$\displaystyle\approx 0.09243$

##  2\. Three Dice

The dominance relation between $A$ and $B$ is invariant under permutations of
the coordinates, and so we can assume that $a_{1}\leq a_{2}\leq a_{3}$. We
also have $a_{1}+a_{2}+a_{3}=3/2$. The sample space for a single die is the
polygonal region in the $a_{1}a_{2}$-plane defined by the inequalities

$0\leq a_{1},\quad a_{1}\leq a_{2},\quad 1\leq 2a_{1}+2a_{2},\quad
2a_{1}+4a_{2}\leq 3.$

The third and fourth inequalities come from $a_{3}\leq 1$ and $a_{2}\leq
a_{3}$ by replacing $a_{3}$ with $3/2-a_{1}-a_{2}$. Call this region $Q$. Its
boundary is a quadrilateral within the unit square and it has area $1/8$. The
probability measure on $Q$ is the normalized area. See Figure 1.

Figure 1. The sample space $Q$ for a single random die

The sample space for three dice $(A,B,C)$ is the six-dimensional polytope
$Q^{3}\subset[0,1]^{6}$. It is defined by $12$ linear inequalities, four for
each of the three dice. The volume of $Q^{3}$ is $1/8^{3}=1/512$. We use the
coordinates $(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2})$ for points in $Q^{3}$.

Our goal is to compute the volume of the subset of $Q^{3}$ defined by $A\succ
B\succ C\succ A$. Let’s first consider the inequalities that define $A\succ
B$. It is not necessary to check all 9 comparisons between each $a_{i}$ and
$b_{j}$. It is sufficient to simply compare $a_{i}$ with $b_{i}$.

######  Lemma 1.

There are three different configurations for which $A\succ B$. They are

$\displaystyle(\succ_{1}):a_{1}<b_{1},\quad a_{2}>b_{2},\quad a_{3}>b_{3}$
$\displaystyle(\succ_{2}):a_{1}>b_{1},\quad a_{2}<b_{2},\quad a_{3}>b_{3}$
$\displaystyle(\succ_{3}):a_{1}>b_{1},\quad a_{2}>b_{2},\quad a_{3}<b_{3}$

###### Proof.

If $a_{i}>b_{i}$ for all $i=1,2,3$, then $\sum a_{i}>\sum b_{i}$, which is
impossible. However, if any two of the three hold, then $A$ dominates $B$. The
configurations are labeled $\succ_{i}$ according to which inequality
$a_{i}>b_{i}$ fails to hold. ∎

######  Lemma 2.

If $A\succ_{i}B$ and $B\succ_{i}C$, then $A\succ_{i}C$. (That is, the
relations $\succ_{i}$ are transitive.)

###### Proof.

Straightforward. Just write down the inequalities. ∎

######  Lemma 3.

If $A,B,C$ form an intransitive triple with $A\succ B\succ C\succ A$, then
$A\succ_{i}B\succ_{j}C\succ_{k}A$ where $\\{i,j,k\\}=\\{1,2,3\\}$.

###### Proof.

Assume that the three relations are not distinct. By relabeling, if necessary,
we can assume that $i=j$. Then $A\succ_{i}B$ and $B\succ_{i}C$, and therefore
$A\succ_{i}C$, which is a contradiction. ∎

For a permutation $\sigma=\sigma_{1}\sigma_{2}\sigma_{3}$ define $E_{\sigma}$
to be both the event

$A\succ_{\sigma_{1}}B\succ_{\sigma_{2}}C\succ_{\sigma_{3}}A$

and the subset of $Q^{3}$ representing the event. Each $E_{\sigma}$ is a
polytope defined by nine additional inequalities, three for each of the three
relations. The union $E=\bigcup E_{\sigma}$ is the event that $A\succ B\succ
C\succ A$, and $\mathrm{P}(E)=\mathrm{vol}(E)/\mathrm{vol}(Q^{3})$. Also,
$\mathrm{vol}(E)=\sum_{\sigma}\mathrm{vol}(E_{\sigma})$. The volumes of the
$E_{\sigma}$ are computed using the SageMath interface to LattE integrale.

######  Lemma 4.

$\displaystyle\mathrm{P}(E_{\sigma})$
$\displaystyle=\begin{cases}\displaystyle\frac{23}{1800}&\text{if
$\sigma=123,231,312$}\\\ &\\\ \displaystyle\frac{3133}{115200}&\text{if
$\sigma=132,213,312$}\end{cases}$ $\displaystyle\mathrm{P}(E)$
$\displaystyle=\frac{307}{2560}$

###### Proof.

See Section 4 for the code. Note that it suffices to compute the volumes of
$E_{123}$ and $E_{132}$ because $E_{\sigma}$ and $E_{\sigma^{\prime}}$ have
the same volume if $\sigma^{\prime}$ is a cyclic permutation of $\sigma$. The
reason is that the cyclic permutation $(A,B,C)\mapsto(B,C,A)$ is volume
preserving and maps $E_{\sigma_{1}\sigma_{2}\sigma_{3}}$ to
$E_{\sigma_{2}\sigma_{3}\sigma_{1}}$.

∎

######  Theorem 5.

The probability that $A,B,C$ form an intransitive triple is
$307/1280=0.23984375$. The probability that they form a transitive chain is
$973/1280=0.76015625$.

###### Proof.

By symmetry $\mathrm{P}(A\succ B\succ C\succ A)=\mathrm{P}(A\prec B\prec
C\prec A)$, which is $\mathrm{P}(E)$, and so the probability of an
intransitive triple is $2\mathrm{P}(E)$. The transitive probability is the
complementary probability $1-2\mathrm{P}(E)$. ∎

##  3\. Four Dice

The sample space for four dice $(A,B,C.\,D)$ is the eight-dimensional polytope
$Q^{4}\subset[0,1]^{8}$. It is defined by $16$ linear inequalities, four for
each of the four dice. The volume of $Q^{4}$ is $1/8^{4}=1/4096$. We use the
coordinates $(a_{1},a_{2},b_{1},b_{2},c_{1},c_{2},d_{1},d_{2})$ for points in
$Q^{4}$.

The main computation that we need to do is to find the probability that
$A\succ B\succ C\succ D\succ A$. Then using symmetry and the results already
computed for three dice we will have enough to determine the probabilities of
the four different tournament types. To see how that works, we introduce the
following notation for the probabilities of the different isomorphism classes
for three and four dice.

transitive 3-chain | $P_{3\text{-line}}$
---|---
intransitive 3-cycle | $P_{\bigtriangleup}$
transitive 4-chain | $P_{4\text{-line}}$
intransitive 4-cycle | $P_{\square}$
winner + 3-cycle | $P_{1\rightarrow\bigtriangleup}$
loser + 3-cycle | $P_{1\leftarrow\bigtriangleup}$

Generating a random set of four dice and then deleting one of them at random
gives a random set of three dice. If the four dice are a transitive chain,
then the remaining three dice will be transitive. If the four dice are a
4-cycle, then removing one of them results in a 3-cycle or a 3-chain, with two
possibilities for each. If the four dice are a 3-cycle plus winner/loser, then
the result is a 3-cycle when the winner/loser is removed or a 3-chain if one
of the other three dice is removed. Therefore,

$\displaystyle P_{3\text{-line}}$
$\displaystyle=P_{4\text{-line}}+\frac{1}{2}P_{\square}+\frac{3}{4}\big{(}P_{1\rightarrow\bigtriangleup}+P_{1\leftarrow\bigtriangleup}\big{)}$
$\displaystyle P_{\bigtriangleup}$
$\displaystyle=\frac{1}{2}P_{\square}+\frac{1}{4}\big{(}P_{1\rightarrow\bigtriangleup}+P_{1\leftarrow\bigtriangleup}\big{)}$

Furthermore, $P_{1\rightarrow\bigtriangleup}=P_{1\leftarrow\bigtriangleup}$,
because the transformation

$A=(a_{1},a_{2},a_{3})\mapsto A^{*}=(1-a_{3},1-a_{2},1-a_{1})$

reverses the relation between dice, and so the tournament associated to
$(A^{*},B^{*},C^{*},D^{*})$ is the result of reversing all the edges in the
tournament of $(A,B,C,D)$. Therefore, once we have found $P_{\square}$, we use
it and the already known $P_{3\text{-line}}$ and $P_{\bigtriangleup}$ to solve
for the remaining probabilities.

######  Lemma 6.

$P_{\square}=6\,\mathrm{P}(A\succ B\succ C\succ D\succ A).$

###### Proof.

There are six ways to label the vertices of a 4-cycle. ∎

A priori, there are 81 different polytopes in $Q^{4}$ to consider because each
of the four relations in the cycle $A\succ B\succ C\succ D\succ A$ is
$\succ_{1},\succ_{2}$, or $\succ_{3}$. For
$\sigma=\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}$, where
$\sigma_{i}\in\\{1,2,3\\}$, let $G_{\sigma}$ be the event
$A\succ_{\sigma_{1}}B\succ_{\sigma_{2}}C\succ_{\sigma_{3}}D\succ_{\sigma_{4}}A$
as well as the corresponding subset of $Q^{4}$. The union $G=\bigcup
G_{\sigma}$ corresponds to the event $A\succ B\succ C\succ D\succ A$, and
$\mathrm{P}(G)=\sum\mathrm{P}(G_{\sigma})$. Fortunately, we can reduce the
number of $G_{\sigma}$ whose volumes need to be computed.

######  Lemma 7.

If $\sigma^{\prime}$ is a cyclic permutation of $\sigma$, then
$\mathrm{vol}(G_{\sigma^{\prime}})=\mathrm{vol}(G_{\sigma})$.

###### Proof.

The map $Q^{4}\rightarrow Q^{4}:(A,B,C,D)\mapsto(B,C,D,A)$ is an isometry and
maps $G_{\sigma}$ to $G_{\sigma^{\prime}}$ where
$\sigma=(\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4})$ and
$\sigma^{\prime}=(\sigma_{2},\sigma_{3},\sigma_{4},\sigma_{1})$. ∎

######  Lemma 8.

If $\sigma$ has one or two distinct entries, then $G_{\sigma}=\emptyset$.

###### Proof.

The $\sigma$ in question are the following and all cyclic permutations of
them:

$\displaystyle(iiii):1111,2222,3333$
$\displaystyle(iiij):1112,1113,2221,2223,3331,3332$
$\displaystyle(iijj):1122,1133,2233$ $\displaystyle(ijij):1212,1313,2323$

For $\sigma$ in the first group the chain of inequalities obviously leads to a
contradiction. Now let $\sigma=1112$, which means that
$a_{1}<b_{1}<c_{1}<d_{1}$ and $d_{2}<a_{2}$. But we also have
$a_{2}>b_{2}>c_{2}>d_{2}$, which is a contradiction. The remaining five
$\sigma$ in the second group are disposed of similarly. From the third group
we use the fact that the $\succ_{i}$ are transitive. If $\sigma=iijj$ then
$G_{\sigma}$ is the event $A\succ_{i}B\succ_{i}C\succ_{j}D\succ_{j}A$, and
this implies that $A\succ_{i}C$ and $C\succ_{j}A$, which is impossible.
Finally for $\sigma=ijij$ we consider
$A\succ_{i}B\succ_{j}C\succ_{i}D\succ_{j}A$. Then for $k\neq i,j$ we have
$a_{k}>b_{k}>c_{k}>d_{k}>a_{k}$, which is impossible. ∎

######  Lemma 9.

There are 36 different $\sigma$ for which $\mathrm{P}(G_{\sigma})>0$. Each is
a cyclic permutation of one of the nine on the list below. If
$\sigma^{\prime}$ is a cyclic permutation of $\sigma$, then
$\mathrm{P}(G_{\sigma^{\prime}})=\mathrm{P}(G_{\sigma})$.

$\sigma$ | $\mathrm{P}(G_{\sigma})$
---|---
$1123$ | $229/322560$
$1132$ | $691507/294912000$
$1213$ | $40913/15482880$
$1223$ | $5431/8064000$
$1232$ | $32299/16515072$
$1322$ | $38929/18432000$
$1233$ | $229/322560$
$1323$ | $40913/15482880$
$1332$ | $691507/294912000$

###### Proof.

See the Appendix for the Sage code to compute the volumes and probabilities. ∎

Notice that $\mathrm{P}(G_{1123})=\mathrm{P}(G_{1233})$,
$\mathrm{P}(G_{1132})=\mathrm{P}(G_{1332})$, and
$\mathrm{P}(G_{1213})=\mathrm{P}(G_{1323})$. Consider the event $G_{1123}$,
which means that $A\succ_{1}B\succ_{1}C\succ_{2}D\succ_{3}A$. Apply the star
operator to each die and verify that verify
$A^{*}\succ_{1}D^{*}\succ_{2}C^{*}\succ_{3}B^{*}\succ_{3}A^{*}$. That is,
$\succ_{1}$ reverses direction and changes to $\succ_{3}$, while $\succ_{3}$
reverses and changes to $\succ_{1}$, and $\succ_{2}$ only reverses direction.
Thus, the isometry

$Q^{4}\rightarrow Q^{4}:(A,B,C,D)\mapsto(A^{*},D^{*},C^{*},B^{*})$

maps $G_{1123}$ onto $G_{1233}$. It also maps $G_{1132}$ onto $G_{2133}$,
which has the same volume as $G_{1332}$ because $2133$ and $1332$ are
cyclically related. And it maps $G_{1213}$ onto $G_{1323}$.

######  Lemma 10.

$\mathrm{P}(A\succ B\succ C\succ D\succ
A)=\mathrm{P}(G)=\displaystyle\frac{99930571}{1548288000}$

###### Proof.

There are four cyclic permutations of each $\sigma$ in Lemma 9. So summing
them and multiplying by four gives $\mathrm{P}(G)$. ∎

######  Theorem 11.

With four 3-sided dice in the balanced uniform model, the probabilities of the
four isomorphism classes of tournaments are the following:

$\displaystyle P_{4\text{-line}}$
$\displaystyle=\frac{110413771}{258048000}\approx
0.42788\quad\text{(transitive chain)}$ $\displaystyle P_{\square}$
$\displaystyle=\frac{99930571}{258048000}\approx
0.38726\quad\text{(intransitive 4-cycle)}$ $\displaystyle
P_{1\rightarrow\bigtriangleup}$
$\displaystyle=\frac{23851829}{258048000}\approx 0.09243\quad\text{(winner +
3-cycle)}$ $\displaystyle P_{1\leftarrow\bigtriangleup}$
$\displaystyle=\frac{23851829}{258048000}\approx 0.09243\quad\text{(loser +
3-cycle)}$

###### Proof.

With four vertices there are six different 4-cycles. From Lemma 9 we know
$\mathrm{P}(G)$, the probability of one particular 4-cycle, and so

$P_{\square}=6\,\mathrm{P}(G)=6\,\bigg{(}\frac{99930571}{1548288000}\bigg{)}=\frac{99930571}{258048000}.$

We also know $P_{3\text{-line}}=973/1280$ and $P_{\bigtriangleup}=307/1280$
from Theorem 5, so that we can solve for $P_{4\text{-line}}$,
$P_{1\rightarrow\bigtriangleup}$, and $P_{1\leftarrow\bigtriangleup}$ using
the equations

$\displaystyle P_{3\text{-line}}$
$\displaystyle=P_{4\text{-line}}+\frac{1}{2}P_{\square}+\frac{3}{4}\big{(}P_{1\rightarrow\bigtriangleup}+P_{1\leftarrow\bigtriangleup}\big{)}$
$\displaystyle P_{\bigtriangleup}$
$\displaystyle=\frac{1}{2}P_{\square}+\frac{1}{4}\big{(}P_{1\rightarrow\bigtriangleup}+P_{1\leftarrow\bigtriangleup}\big{)}$
$\displaystyle P_{1\rightarrow\bigtriangleup}$
$\displaystyle=P_{1\leftarrow\bigtriangleup}$

∎

##  4\. Sage Computation: Three Dice

We define the polytopes (or “polyhedra” ) in Sage using the half-space
representation [4], which is a system of linear inequalities of the form

$0\leq\beta+\alpha_{1}x_{1}+\alpha_{2}x_{2}+\cdots+\alpha_{n}x_{n}.$

This inequality is represented by
$(\beta,\alpha_{1},\alpha_{2},\ldots,\alpha_{n})$, a tuple of length $n+1$.
Our variables are $a_{1},a_{2},b_{1},b_{2},c_{1},c_{2}$, so that, for example,
the inequality $2a_{1}+4a_{2}\leq 3$ is represented by the $7$-tuple
$(3,-2,-4,0,0,0,0)$. The twelve inequalities defining $Q^{3}$ and their Sage
representations are the following:

$\displaystyle 0$ $\displaystyle\leq a_{1},$ $\displaystyle a_{1}$
$\displaystyle\leq a_{2},$ $\displaystyle 1$ $\displaystyle\leq
2a_{1}+2a_{2},$ $\displaystyle 2a_{1}+4a_{2}$ $\displaystyle\leq 3,$
$\displaystyle 0$ $\displaystyle\leq b_{1},$ $\displaystyle b_{1}$
$\displaystyle\leq b_{2},$ $\displaystyle 1$ $\displaystyle\leq
2b_{1}+2b_{2},$ $\displaystyle 2b_{1}+4b_{2}$ $\displaystyle\leq 3,$
$\displaystyle 0$ $\displaystyle\leq c_{1},$ $\displaystyle c_{1}$
$\displaystyle\leq c_{2},$ $\displaystyle 1$ $\displaystyle\leq
2c_{1}+2c_{2},$ $\displaystyle 2c_{1}+4c_{2}$ $\displaystyle\leq 3.$
$\displaystyle(0,1,0,0,0,0,0),\quad(0,-1,1,0,0,0,0),\quad(-1,2,2,0,0,0,0),\quad(3,-2,-4,0,0,0,0),$
$\displaystyle(0,0,0,1,0,0,0),\quad(0,0,0,-1,1,0,0),\quad(-1,0,0,2,2,0,0),\quad(3,0,0,-2,-4,0,0),$
$\displaystyle(0,0,0,0,0,1,0),\quad(0,0,0,0,0,-1,1),\quad(-1,0,0,0,0,2,2),\quad(3,0,0,0,0,-2,-4).$

To define $E_{123}$ corresponding to $A\succ_{1}B\succ_{2}C\succ_{3}A$ there
are nine additional inequalities.

$\displaystyle a_{1}<b_{1},\quad a_{2}>b_{2},\quad a_{3}>b_{3}\Leftrightarrow
a_{1}+a_{2}<b_{1}+b_{2},$ $\displaystyle b_{1}>c_{1},\quad b_{2}<c_{2},\quad
b_{3}>c_{3}\Leftrightarrow b_{1}+b_{2}<c_{1}+c_{2},$ $\displaystyle
c_{1}>a_{1},\quad c_{2}>a_{2},\quad c_{3}<a_{3}\Leftrightarrow
c_{1}+c_{2}>a_{1}+a_{2}.$

The Sage representations are

$\displaystyle(0,-1,0,1,0,0,0),$
$\displaystyle\quad(0,0,1,0,-1,0,0),\quad(0,-1,-1,1,1,0,0),$
$\displaystyle(0,0,0,1,0,-1,0),$
$\displaystyle\quad(0,0,0,0,-1,0,1),\quad(0,0,0,-1,-1,1,1),$
$\displaystyle(0,-1,0,0,0,1,0),$
$\displaystyle\quad(0,0,-1,0,0,0,1),\quad(0,-1,-1,0,0,1,1).$

The polytope $E_{132}$ corresponding to $A\succ_{1}B\succ_{3}C\succ_{2}A$ has
the additional inequalities represented by

$\displaystyle(0,-1,0,1,0,0,0),$
$\displaystyle\quad(0,0,1,0,-1,0,0),\quad(0,-1,-1,1,1,0,0),$
$\displaystyle(0,0,0,1,0,-1,0),$
$\displaystyle\quad(0,0,0,0,1,0,-1),\quad(0,0,0,1,1,-1,-1),$
$\displaystyle(0,-1,0,0,0,1,0),$
$\displaystyle\quad(0,0,1,0,0,0,-1),\quad(0,1,1,0,0,-1,-1).$

For the volume computations we call the integrate function in _LattE
integrale_ using the Sage interface [5].

Sage input  from sage.interfaces.latte import integrate Q3_ieqs =
[(0,1,0,0,0,0,0),(-1,2,2,0,0,0,0),(0,-1,1,0,0,0,0),
(3,-2,-4,0,0,0,0),(0,0,0,1,0,0,0),(-1,0,0,2,2,0,0),
(0,0,0,-1,1,0,0),(3,0,0,-2,-4,0,0),(0,0,0,0,0,1,0),
(-1,0,0,0,0,2,2),(0,0,0,0,0,-1,1),(3,0,0,0,0,-2,-4)] Q3 = Polyhedron(ieqs =
Q3_ieqs) vol_Q3 = integrate(Q3.cdd_Hrepresentation(),cdd=True) E123_ieqs =
[(0,-1,0,1,0,0,0),(0,0,1,0,-1,0,0),(0,-1,-1,1,1,0,0),
(0,0,0,1,0,-1,0),(0,0,0,0,-1,0,1),(0,0,0,-1,-1,1,1),
(0,-1,0,0,0,1,0),(0,0,-1,0,0,0,1),(0,-1,-1,0,0,1,1)] E123 = Polyhedron(ieqs =
Q3_ieqs + E123_ieqs ) vol_E123 = integrate(E123.cdd_Hrepresentation(),
cdd=True) prob_E123 = vol_E123/vol_Q3 E213_ieqs =
[(0,-1,0,1,0,0,0),(0,0,1,0,-1,0,0),(0,-1,-1,1,1,0,0),
(0,0,0,1,0,-1,0),(0,0,0,0,1,0,-1),(0,0,0,1,1,-1,-1),
(0,-1,0,0,0,1,0),(0,0,1,0,0,0,-1),(0,1,1,0,0,-1,-1)] E213 = Polyhedron(ieqs =
Q3_ieqs + E213_ieqs) vol_E213 = integrate(E213.cdd_Hrepresentation(),
cdd=True) prob_E213 = vol_E213/vol_Q3 prob_E = 3*prob_E123 + 3*prob_E213
print("vol(Q3) =",vol_Q3) print("P(E123)
=",prob_E123,"=",n(prob_E123,digits=9)) print("P(E213)
=",prob_E213,"=",n(prob_E213,digits=9)) print("P(A>B>C>A) = P(E)
=",prob_E,"=",n(prob_E,digits=9)) print("P(intransitive)
=",2*prob_E,"=",n(2*prob_E,digits=9))

Output  vol(Q3) = 1/512 P(E123) = 23/1800 = 0.0127777778 P(E213) = 3133/115200
= 0.0271961806 P(A>B>C>A) = P(E) = 307/2560 = 0.119921875 P(intransitive) =
307/1280 = 0.239843750

##  5\. Sage Computation: Four Dice

There are 16 inequalties needed to define $Q^{4}$ in Sage. Each is represented
by a tuple of length 9. They are straightforward extensions of those used to
define $Q^{3}$.

To define $G_{\sigma}$ where $\sigma=ijkl$ we use the function G(i,j,k,l)
which returns the Sage polyhedron. This requires the inequalities for $Q^{4}$
and the inequalities for the four relations.

For $m=1,2,3,4$ and $i=1,2,3$ the function g(m,i) returns a list of three
tuples asserting that the $m$th dominance relation is $\succ_{i}$. For
example, $g(3,2)$ returns the tuples for $C\succ_{2}D$ since the third
relation is the one between $C$ and $D$. Then $G(i,j,k,l)$ simply concatenates
the inequalities for $Q^{4}$ with those coming from g(1,i),g(2,j),g(3,k), and
g(4,l), a total of 28 inequalties. The definition of g(m,i) uses vectors
$\texttt{a1,a2,a3},\ldots,\texttt{d1,d2,d3}$ so that an inequality such as
$a_{2}>b_{2}$ is represented by a2-b2. The vector a3 is actually -a1-a2 and
likewise for b3,c3,d3, because an inequality such as $a_{3}>b_{3}$ is
equivalent to $-a_{1}-a_{2}>-b_{1}-b_{2}$.

The function pr(i,j,k,l) returns the probability of $G_{ijkl}$. First it finds
the dimension of G(i,j,k,l). If the dimension is less than eight, then the
polytope has zero volume and the probability is zero. If the dimension is
eight, then the function uses the integrate function from _LattE integrale_ to
find the volume and multiplies by $4096$ to get the probability. It is
necessary to check the dimension first, because the integrate function does
not return zero on polytopes of less than the full dimension.

Sage input  from sage.interfaces.latte import integrate Q4_ieqs =
[(0,1,0,0,0,0,0,0,0),(-1,2,2,0,0,0,0,0,0),
(0,-1,1,0,0,0,0,0,0),(3,-2,-4,0,0,0,0,0,0),
(0,0,0,1,0,0,0,0,0),(-1,0,0,2,2,0,0,0,0),
(0,0,0,-1,1,0,0,0,0),(3,0,0,-2,-4,0,0,0,0),
(0,0,0,0,0,1,0,0,0),(-1,0,0,0,0,2,2,0,0),
(0,0,0,0,0,-1,1,0,0),(3,0,0,0,0,-2,-4,0,0),
(0,0,0,0,0,0,0,1,0),(-1,0,0,0,0,0,0,2,2),
(0,0,0,0,0,0,0,-1,1),(3,0,0,0,0,0,0,-2,-4)] Q4 = Polyhedron(ieqs = Q4_ieqs)
vol_Q4 = integrate(Q4.cdd_Hrepresentation(),cdd=True)
a1=vector((0,1,0,0,0,0,0,0,0)); a2=vector((0,0,1,0,0,0,0,0,0));
a3=vector((0,-1,-1,0,0,0,0,0,0)); b1=vector((0,0,0,1,0,0,0,0,0));
b2=vector((0,0,0,0,1,0,0,0,0)); b3=vector((0,0,0,-1,-1,0,0,0,0));
c1=vector((0,0,0,0,0,1,0,0,0)); c2=vector((0,0,0,0,0,0,1,0,0));
c3=vector((0,0,0,0,0,-1,-1,0,0)); d1=vector((0,0,0,0,0,0,0,1,0));
d2=vector((0,0,0,0,0,0,0,0,1)); d3=vector((0,0,0,0,0,0,0,-1,-1)); def g(m,i):
s = ((-1,1,1),(1,-1,1),(1,1,-1)) if m==1: return
[s[i-1][0]*(a1-b1),s[i-1][1]*(a2-b2), s[i-1][2]*(a3-b3)] elif m==2: return
[s[i-1][0]*(b1-c1),s[i-1][1]*(b2-c2), s[i-1][2]*(b3-c3)] elif m==3: return
[s[i-1][0]*(c1-d1),s[i-1][1]*(c2-d2), s[i-1][2]*(c3-d3)] elif m==4: return
[s[i-1][0]*(d1-a1),s[i-1][1]*(d2-a2), s[i-1][2]*(d3-a3)] end

Sage input  def G(i,j,k,l): return Polyhedron(ieqs =
Q4_ieqs+g(1,i)+g(2,j)+g(3,k)+g(4,l)) end def pr(i,j,k,l): event = G(i,j,k,l)
if event.dim() < 8: eturn 0 else: return
4096*integrate(event.cdd_Hrepresentation(),cdd=True) end print(" Event
Probability") print("G(1,1,2,3) ",pr(1,1,2,3)) print("G(1,1,3,2)
",pr(1,1,3,2)) print("G(1,2,1,3) ",pr(1,2,1,3)) print("G(1,2,2,3)
",pr(1,2,2,3)) print("G(1,2,3,2) ",pr(1,2,3,2)) print("G(1,3,2,2)
",pr(1,3,2,2)) print("G(1,2,3,3) ",pr(1,2,3,3)) print("G(1,3,2,3)
",pr(1,3,2,3)) print("G(1,3,2,2) ",pr(1,3,2,2))

Output  Event Probability G(1,1,2,3) 229/322560 G(1,1,3,2) 691507/294912000
G(1,2,1,3) 40913/15482880 G(1,2,2,3) 5431/8064000 G(1,2,3,2) 32299/16515072
G(1,3,2,2) 38929/18432000 G(1,2,3,3) 229/322560 G(1,3,2,3) 40913/15482880
G(1,3,2,2) 38929/18432000

## References

  * [1] B. Conrey, J. Gabbard, K. Grant, A. Liu, and K. E. Morrison. Intransitive dice. _Mathematics Magazine_ , 89(2):133–143, 2016.
  * [2] E. Cornacchia and J. Hązła. Intransitive dice tournament is not quasirandom. arXiv:2011.10067, 19 Nov 2020.
  * [3] D. H. J. Polymath, The probability that a random triple of dice is intransitive. arXiv:2211.16156, 29 Nov 2022.
  * [4] Polyhedra, Sage 9.7 Reference Manual, https://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/polyhedron/constructor.html
  * [5] Interface to LattE integrale programs, Sage 9.7 Reference Manual, https://doc.sagemath.org/html/en/reference/interfaces/sage/interfaces/latte.html