# 4-strand Burau is unfaithful modulo $5$

Joel Gibson  J. Gibson: Sydney, Australia<EMAIL_ADDRESS>,  Geordie
Williamson  G. Williamson: School of Mathematics and Statistics, University of
Sydney, Australia<EMAIL_ADDRESS>and  Oded Yacobi  O. Yacobi:
School of Mathematics and Statistics, University of Sydney, Australia
<EMAIL_ADDRESS>
###### Abstract.

We introduce a new algorithm for finding kernel elements in the Burau
representation. Our algorithm applies reservoir sampling to a statistic on
matrices which is closely correlated with Garside length. Using this we
exhibit an explicit kernel element in the Burau representation on 4-strands
reduced modulo 5.

##  1\. Introduction

The Burau representation of the $n$-strand braid group
$\pi_{n}:B_{n}\to\mathrm{GL}_{n-1}(\mathbb{Z}[v,v^{-1}])$, plays a prominent
role in many applications of braid groups, including to geometry, topology and
mathematical physics [3]. A key question underlying many of these developments
is determining when $\pi_{n}$ is faithful.

It is not difficult to prove that $\pi_{3}$ is faithful (cf. Propostion 3.3),
but despite intensive study, there wasn’t substantial progress on this
question until 1991, when Moody proved that $\pi_{n}$ is not faithful for
$n\geq 9$ [11]. His work was developed further by Long and Paton to show
unfaithfulness for $n\geq 6$ [10]. Bigelow extended this also to $n=5$ [2].

The case $n=4$ remains open, and has attracted considerable attention. One
reason for this is that a negative answer provides a non-trivial knot with
trivial Jones polynomial, answering a central question in knot theory [1, 9].

Henceforth we set $\pi=\pi_{4}$. Cooper and Long approached the faithfulness
of $\pi$ by reducing modulo primes. That is, they considered the composition
of $\pi$ with the natural map
$\mathrm{GL}_{3}(\mathbb{Z}[v,v^{-1}])\to\mathrm{GL}_{3}(\mathbb{F}_{p}[v,v^{-1}])$,
where $\mathbb{F}_{p}$ is the field with $p$ elements [5]. Following their
work, we denote this representation $\pi\otimes\mathbb{F}_{p}$. The study of
the faithfulness of $\pi\otimes\mathbb{F}_{p}$ is interesting for several
reasons:

  1. (1)

Examples when $\pi\otimes\mathbb{F}_{p}$ is unfaithful can give insights into
the difficulty of establishing the faithfulness of $\pi$.

  2. (2)

It might be the case that $\pi\otimes\mathbb{F}_{p}$ is unfaithful modulo all
primes, yet $\pi$ is faithful. Controlling the kernel modulo infinitely many
primes might provide a route to establishing faithfulness of $\pi$.

One of the main results in [5] is that $\pi\otimes\mathbb{F}_{2}$ is not
faithful. In [6] the same authors extended their methods to show that
$\pi\otimes\mathbb{F}_{3}$ is also not faithful. They noted their program runs
into obstacles at $p=5$: “This case remains open and has some features which
suggest it may be different to the first two primes.” Our main result resolves
this case.

######  Theorem 1.1.

The representation $\pi\otimes\mathbb{F}_{5}$ is not faithful.

Some remarks on our main theorem:

  1. (1)

Our approach, which we discuss in the next section, is heavily computational
and is quite different from the existing methods. A complete implementation of
our algorithm (in Python) is available on github [8].

  2. (2)

We discover several kernel elements modulo $5$, the smallest of which is of
Garside length 54111see §2 for the definition of Garside length. We note that
a straightforward computation shows that there are $10^{40}$ elements of this
Garside length, thus finding this element by brute force search is not
feasible.

  3. (3)

We have made extensive searches with our algorithm to try to discover a kernel
element of $\pi\otimes\mathbb{F}_{7}$, without success. We are also unable to
rediscover Bigelow’s (integral) kernel elements for $n=5$ and $n=6$, which
indicates the limitations of our algorithm.

  4. (4)

Recently, Datta proved that $\pi$ is “generically faithful”, in the sense that
almost all braids are not in the kernel of $\pi$ as their length tends to
infinity [7]. Datta also proves that this property extends to
$\pi\otimes\mathbb{F}_{p}$ for $p>3$. Combined with our work,
$\pi\otimes\mathbb{F}_{5}$ therefore provides an example of a generically
faithful representation which is not faithful.

Our original goal was to use Machine Learning techniques to attack this
problem. Thus far we have not been able to get anything along these lines to
work—we outline our attempts in §6.3. We do believe though that this is an
excellent hard test case for Machine Learning methods in pure mathematics. Our
implementation [8] is intended to make it as straightforward as possible for
interested researchers to try Machine Learning techniques on this problem.

###  1.1. Acknowledgements

The observation that Garside length is closely correlated with
$\mathsf{projlen}$ (cf. (3.1)) was made in joint work of the third author with
Nicolas Libedinsky. (It has likely also been noticed by other researchers.) We
would also like to thank Robert Bryant, Giles Gardem, Libedinsky and Nolan
Wallach for useful discussions. The second two authors are supported by the
Australian Research Council under the grant DP230100654.

##  2\. Recollections

We recall some basic facts about the braid group. A presentation of $B_{n}$ in
terms of the Artin generators is given by

$B_{n}=\Big{\langle}\sigma_{1},\ldots,\sigma_{n-1}\;|\;\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}\text{
if }|i-j|>1\text{ and
}\sigma_{i}\sigma_{j}\sigma_{i}=\sigma_{j}\sigma_{i}\sigma_{j}\text{ if
}|i-j|=1\Big{\rangle}.$

On these generators, the (reduced) Burau representation
$\pi_{n}:B_{n}\to\mathrm{GL}_{n-1}(\mathbb{Z}[v,v^{-1}])$ is defined as
follows:

$\displaystyle\sigma_{1}\mapsto\begin{pmatrix}-v^{2}&-v\\\
0&1\end{pmatrix}\oplus$ $\displaystyle I_{n-3},\;\;\;\sigma_{n-1}\mapsto
I_{n-3}\oplus\begin{pmatrix}1&0\\\ -v&-v^{2}\end{pmatrix}$
$\displaystyle\sigma_{i}\mapsto I_{i-1}\oplus$
$\displaystyle\begin{pmatrix}1&0&0\\\ -v&-v^{2}&-v\\\ 0&0&1\end{pmatrix}\oplus
I_{n-i-3}$

for $1<i<n-1$. We call $\pi_{n}(\sigma)$ the Burau matrix of $\sigma$, and its
reduction modulo a prime $p$, its $p$-Burau matrix.

Let $S_{n}$ denote the symmetric group with simple generators
$s_{1},\ldots,s_{n-1}$. For $w\in S_{n}$ write $\widetilde{w}\in B_{n}$ for
the corresponding positive lift in the braid group. Explicitly, if
$w=s_{i_{1}}s_{i_{2}}\cdots$ is a reduced expression, then
$\widetilde{w}=\sigma_{i_{1}}\sigma_{i_{2}}\cdots$. For the longest element we
write $\Delta=\widetilde{w_{0}}$. Note that

$\displaystyle\pi_{n}(\Delta)=(-1)^{n+1}\begin{pmatrix}0&&v^{n}\\\
&\mathinner{\mkern 1.0mu\raise 1.0pt\vbox{\kern 7.0pt\hbox{.}}\mkern
2.0mu\raise 4.0pt\hbox{.}\mkern 2.0mu\raise 7.0pt\hbox{.}\mkern 1.0mu}&\\\
v^{n}&&0\end{pmatrix}$ (2.1)

Let $\mathscr{R}(w)$ (respectively $\mathscr{L}(w)$) denote the right
(respectively left) descent set of $w\in S_{n}$.

A braid $\sigma\in B_{n}$ has a Garside normal form (GNF)

$\displaystyle\sigma=\Delta^{d}\widetilde{w_{1}}\cdots\widetilde{w_{\ell}},$
(2.2)

where $d\in\mathbb{Z}$, $w_{1}\neq w_{0}$, $w_{\ell}\neq e$, and for every
$k$, $\mathscr{R}(w_{k})\supseteq\mathscr{L}(w_{k+1})$. This expression is
unique, and $\ell_{G}(\sigma):=\ell$ is the Garside length of $\sigma$. For
$k\leq\ell$ we’ll be interested in the associated Garside prefix of $\sigma$:
$\Delta^{d}\widetilde{w_{1}}\cdots\widetilde{w_{k}}$. A simple but useful
observation: if $u\in S_{n}$ satisfies
$\mathscr{R}(w_{\ell})\supseteq\mathscr{L}(u)$, then the GNF of
$\sigma\widetilde{u}$ is obtained by concatenation:

$\displaystyle\sigma\widetilde{u}=\Delta^{d}\widetilde{w_{1}}\cdots\widetilde{w_{\ell}}\widetilde{u}.$

We term $\widetilde{u}$ a Garside suffix of $\sigma$.

##  3\. Basic idea

Suppose one can find a statistic on matrices which detects Garside length. In
other words, we have a function
$\mathsf{p}:\mathrm{GL}_{n-1}(\mathbb{Z}[v,v^{-1}])\to\mathbb{N}$ such that
$\mathsf{p}(\pi_{n}(\sigma))=C\cdot\ell_{G}(\sigma)$ for some constant
$C{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}>}0$. Then
this implies the faithfulness of $\pi_{n}$:

$\pi_{n}(\sigma)=\mathrm{Id}\;\Longrightarrow\;\mathsf{p}(\pi_{n}(\sigma))=0\;\Longrightarrow\;\ell_{G}(\sigma)=0\;\Longrightarrow\;\sigma=\Delta^{d}$

for some $d\in\mathbb{Z}$, and $\pi_{n}(\Delta^{d})=\mathrm{Id}$ if and only
if $d=0$.

On the other hand, if $\mathsf{p}$ is correlated with $\ell_{G}$ only for
generic braids, then one can try to use $\mathsf{p}$ as an ansatz to find
kernel elements: braids with surprisingly low $\mathsf{p}$-value might point
towards elements in the kernel. We explain both of these situations, beginning
with the simple case of the $3$-strand Burau representation.

First we define the statistic which we’ll be using throughout. Given $A$, a
non-zero $r\times s$ array with entries in Laurent polynomials in $v$, let
$\deg(A)$ be the highest power of $v$ that occurs in an entry of $A$, and let
$\text{val}(A)$ be the lowest power. We set

$\displaystyle\mathsf{projlen}(A)=\deg(A)-\text{val}(A).$ (3.1)

Note that multiplication of a Burau matrix by $\Delta$ does not affect
$\mathsf{projlen}$:

$\displaystyle\mathsf{projlen}(\pi_{n}(\sigma))=\mathsf{projlen}(\pi_{n}(\sigma)\Delta)=\mathsf{projlen}(\Delta\pi_{n}(\sigma)).$
(3.2)

######  Proposition 3.3.

For any $\sigma\in B_{3}$ we have
$\mathsf{projlen}(\pi_{3}(\sigma))=2\ell_{G}(\sigma)$. Hence, the $3$-strand
Burau representation is faithful.

###### Proof.

Let $\sigma\in B_{3}$ have GNF given by (2.2) and let
$\pi_{3}(\sigma)=[c_{1},c_{2}]$, where $c_{i}$ are the column vectors in the
matrix. Then the following trichotomy holds:

  1. (1)

$\deg(c_{1})=\deg(c_{2}),\text{val}(c_{1})=\text{val}(c_{2})$, and
$\sigma=\Delta^{d}$ for some $d\in\mathbb{Z}$.

  2. (2)

$\deg(c_{1})>\deg(c_{2}),\text{val}(c_{1})>\text{val}(c_{2})$, and
$\mathscr{R}(\sigma)=\\{s_{1}\\}$.

  3. (3)

$\deg(c_{1})<\deg(c_{2}),\text{val}(c_{1})<\text{val}(c_{2})$, and
$\mathscr{R}(\sigma)=\\{s_{2}\\}$.

Moreover, in each case $\mathsf{projlen}(\pi_{3}(\sigma))=2\ell_{G}(\sigma)$.

To see this, we induct on $\ell=\ell_{G}(\sigma)$. If $\ell=0$ then we are in
the first case of the trichotomy. Note that in this case
$0=\mathsf{projlen}(\pi_{3}(\sigma))=2\ell_{G}(\sigma)$. Now let $\ell\geq 1$,
and suppose that
$\sigma^{\prime}:=\Delta^{d}\widetilde{w_{1}}\cdots\widetilde{w_{\ell-1}}$
falls into the second case of the trichotomy. Setting
$\pi_{3}(\sigma^{\prime})=[c_{1}^{\prime},c_{2}^{\prime}]$, we then have that
$\deg(c^{\prime}_{1})>\deg(c^{\prime}_{2}),\text{val}(c^{\prime}_{1})>\text{val}(c^{\prime}_{2})$,
$\mathscr{R}(\sigma^{\prime})=\\{s_{1}\\}$, and
$\mathsf{projlen}(\pi_{3}(\sigma^{\prime}))=2\ell_{G}(\sigma^{\prime})$. The
condition
$\mathscr{R}(\widetilde{w_{\ell-1}})\supseteq\mathscr{R}(\widetilde{w_{\ell}})$
forces $w_{\ell}=s_{1}$ or $w_{\ell}=s_{1}s_{2}$. If $w_{\ell}=s_{1}$ then
$[c_{1},c_{2}]=[-v^{2}c_{1}^{\prime},-vc^{\prime}_{1}+c^{\prime}_{2}],$ and we
are in case (2). Otherwise, $w_{\ell}=s_{1}s_{2}$ and
$[c_{1},c_{2}]=[-vc_{2}^{\prime},v^{3}c^{\prime}_{1}-v^{2}c^{\prime}_{2}],$ so
we are in case (3). Either way we have the equality
$\mathsf{projlen}(\pi_{3}(\sigma))=2\ell_{G}(\sigma)$. The other cases follow
similarly. ∎

Moving onto the $4$-strand braid group, it is easy to see that a
straightforward analogue of Proposition 3.3 does not hold. For instance,
taking $\sigma=\widetilde{u}$, where $u=s_{1}s_{2}s_{1}s_{3}$ we have that

$\displaystyle\pi_{4}(\sigma)=\begin{pmatrix}0&0&-v^{4}\\\
v^{3}&v^{2}&v^{3}\\\ 0&-v&-v^{2}\end{pmatrix}$

We see that $\mathsf{projlen}(\pi_{4}(\sigma))=3$ is not even, and one cannot
read off $\mathscr{R}(u)=\\{s_{1},s_{3}\\}$ directly from the columns
achieving $\deg(\pi_{4}(\sigma))$. Nevertheless, we can ask whether
generically $\mathsf{projlen}$ is a good heuristic for Garside length.

The following table shows the result of sampling $1000$ random braids in
$B_{4}$ of each Garside length, up to $50$. Each braid is depicted by a blue
dot in the plane, where the $x$-axis is labelled by the Garside length of the
braid, and the $y$-axis is labelled by $\frac{1}{2}\mathsf{projlen}$. The
$y=x$ line is drawn in red.

We see that it is almost always the case that $\frac{1}{2}\mathsf{projlen}$ is
larger than the Garside length. Moreover, there appears to be a strong linear
correlation between these two statistics for generic braids. However, there
are a few exceptions corresponding to blue dots below the red line.

Now consider an element

$\sigma=\Delta^{d}\widetilde{w_{1}}\cdots\widetilde{w_{\ell}}$

in the kernel of some Burau representation. Because $\mathsf{projlen}$ of a
kernel element is zero and $\mathsf{projlen}$ is unaffected by multiplication
by $\Delta$ (3.2) we have

$0=\mathsf{projlen}(\sigma)=\mathsf{projlen}(\widetilde{w_{1}}\cdots\widetilde{w_{\ell}})$

It is now reasonable to suspect that the projlens of Garside prefixes of
$\widetilde{w_{1}}\cdots\widetilde{w_{\ell}}$:

$\displaystyle\mathsf{projlen}(\widetilde{w_{1}}),\mathsf{projlen}(\widetilde{w_{1}}\widetilde{w_{2}}),\dots,\mathsf{projlen}(\widetilde{w_{1}}\cdots\widetilde{w_{\ell-1}}),\mathsf{projlen}(\widetilde{w_{1}}\cdots\widetilde{w_{\ell}})=0.$
(3.4)

are typically smaller than those of a generic braid of the same length. Thus
searching for GNFs with low projlen might point us in the direction of kernel
elements.

##  4\. The algorithm

We’ll now describe our algorithm for sampling braids with low
$\mathsf{projlen}$. We picture the set-up for our search as placing a “bucket”
at each point in $\mathbb{Z}_{\geq 0}\times\mathbb{Z}_{\geq 0}$. Initially,
these buckets are empty and over time they will be filled with Garside normal
forms of $4$-strand braids, and their Burau matrices. The bucket
$\mathsf{B}_{(\ell,m)}$ at the point $(\ell,m)$ will only contain braids
$\sigma$ such that $\ell_{G}(\sigma)=\ell$ and
$\mathsf{projlen}(\pi(\sigma))=m$.

The method by which we fill the buckets is called reservoir sampling [12].
This is a well-known algorithm which selects a random sample of $k$ elements
without repetition from a set of $N$ elements which arrive sequentially, and
where the value of $N$ is unknown in advance. Typically, $N$ is enormous. Thus
it is not possible to store all elements seen and the sampling is done in one
pass. At any point in time, the selection of $k$ elements, i.e. the
“reservoir”, should be uniformly distributed among all elements seen thus far.

We recall the idea in more detail since it is so fundamental to our approach.
Suppose we’re sampling elements from a set $X$ and that the elements arrive as
a sequence $x_{1},x_{2},\dots,x_{N}$.

Let us first consider the case $k=1$. Our reservoir then consists of a single
element, which at the $i$-th step we will denote $r_{i}$. At the first step we
let $r_{1}=x_{1}$. In the second step, we replace $r_{1}$ with $x_{2}$ with
probability $\frac{1}{2}$, otherwise $r_{2}=r_{1}$. In the third step we
replace $r_{2}$ with $x_{3}$ with probability $\frac{1}{3}$, otherwise
$r_{3}=r_{2}$. Note that indeed, for every $i$, $r_{i}$ is uniformly
distributed among $x_{1},\ldots,x_{i}$.

If $k>1$, then the reservoir is a $k$-subset of $X$, which at the $i$-th step
we will denote $R_{i}=\\{r_{1}^{i},\ldots,r_{k}^{i}\\}$. First we just fill
the reservoir: $r_{j}^{1}=x_{j}$ for $j\leq k$. At the next step we randomly
generate a number $j\in\\{1,\ldots,k+1\\}$, and if $j\leq k$ replace the
$j$-th element of $R_{1}$ by $x_{k+1}$:

$\displaystyle r_{q}^{2}:=\begin{cases}x_{k+1}\text{ if }q=j,\\\
r_{q}^{1}\text{ otherwise. }\end{cases}$

Otherwise, $R_{2}=R_{1}$. Next, randomly generate a number
$j\in\\{1,\ldots,k+2\\}$, and if $j\leq k$ replace the $j$-th element of
$R_{2}$ by $x_{k+2}$, and so on. At the $i$-th step, we have that $R_{i}$ is a
uniformly distributed $k$-subset of $\\{x_{1},\ldots,x_{i+k-1}\\}$.

Going back to our set-up, we will now describe an adaptation of the above
ideas to place braids in appropriate buckets. At the $\ell$-th step in our
algorithm, we will be placing braids in buckets at points $(\ell,m)$ for
various $m$. We fix ahead of time an upper bound $k$, which is the maximum
number of braids contained in a single bucket. Set
$\mathsf{B}_{\ell}=\bigcup_{m\geq 0}\mathsf{B}_{(\ell,m)}$.

To begin place the identity $e\in B_{4}$ in $\mathsf{B}_{(0,0)}$. Now let
$\ell>0$, and at the $\ell$-th step proceed as follows:

Set $N_{m}=0$ for every $m$ $\triangleright$ Counts how many braids we’ve
tried to place in $\mathsf{B}_{(\ell,m)}$

for $\sigma\in\mathsf{B}_{\ell-1}$ do

for $\widetilde{u}$ a Garside suffix of $\sigma$ do

$m=\mathsf{projlen}(\sigma\widetilde{u})$

$M=|\mathsf{B}_{(\ell,m)}|$

if $M<k$ then

place $\sigma\widetilde{u}$ and its Burau matrix in $\mathsf{B}_{(\ell,m)}$

else randomly generate a number $j\in\\{1,\ldots,N_{m}\\}$

if $j<k$ then

replace $j$-th element of $\mathsf{B}_{(\ell,m)}$ by $\sigma\widetilde{u}$ and
its Burau matrix

else discard $\sigma\widetilde{u}$

end if

end if

Set $N_{m}:=N_{m}+1$

end for

end for

Note that since we are storing the Burau matrices along the way, it is easy
for us to compute $\mathsf{projlen}(\sigma\widetilde{u})$. Also, we can easily
modify this algorithm to study the Burau representation modulo primes (we
simply remember the $p$-Burau matrices instead).

##  5\. Main result

We’ll now describe the most interesting output of our algorithm: in the case
$p=5$ we obtained several elements in the kernel of
$\pi\otimes\mathbb{F}_{5}$. We stress that these are the first known kernel
elements in Burau representations $\pi\otimes\mathbb{F}_{p}$ with $p>3$, and
this represents the first explicit progress on this question in 25 years!

The smallest we found, $\kappa$, has Garside length $54$. We have

$\kappa=\Delta^{-27}*\sigma$

where $\Delta$ denotes the Garside element and $\sigma$ is the following word
in the Artin generators:

$\displaystyle
1,3,1,3,1,3,2,2,1,3,3,2,2,1,3,3,2,2,2,1,3,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,2,1,3,3,$
$\displaystyle
2,2,1,3,3,2,2,1,3,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,1,3,2,2,1,3,2,2,2,1,$
$\displaystyle
3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,2,3,2,1,1,3,2,2,1,3,3,2,$
$\displaystyle
2,1,3,3,2,2,2,1,3,2,2,1,3,1,2,3,2,2,1,3,1,2,3,2,2,1,3,1,2,3,2,1$

The length of $\sigma$ in the Artin generators is 162.

The following plot depicts the journey of $\sigma$ through the various
buckets, as described in (3.4):

The $x$-axis is labelled by Garside length, the $y$-axis by
$\mathsf{projlen}$222It’s actually labelled by $\mathsf{projlen}+1$ but we
ignore this technicality., and each blue dot represents a bucket which
contains a Garside prefix of $\kappa$.

The rightmost dot corresponds to the bucket containing $\sigma$. It’s
interesting to note that this trajectory follows a generic path until about
Garside length $30$, where suddenly the reservoir sampling starts finding
elements with smaller than expected $\mathsf{projlen}$. Around length $40$,
the algorithm hits a “point of no return”, and makes a beeline for $\sigma$.

In case the reader is interested, here is the Garside normal form of $\kappa$:

$\displaystyle\kappa=(\Delta^{-27};s_{0}s_{2},s_{0}s_{2},s_{0}s_{2}s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1},s_{1}s_{0}s_{2},s_{0}s_{2}s_{1}s_{0},s_{1}s_{0}s_{2},$
$\displaystyle
s_{0}s_{2}s_{1}s_{0},s_{1}s_{0}s_{2},s_{0}s_{2}s_{1},s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1}s_{0}s_{2},s_{0}s_{2},s_{0}s_{1}s_{2}s_{1}s_{0},s_{0}s_{2}s_{1}s_{0},$
$\displaystyle
s_{1}s_{0}s_{2},s_{0}s_{2}s_{1}s_{0},s_{1}s_{0}s_{2},s_{0}s_{2}s_{1},s_{1}s_{0}s_{2}s_{1},s_{1}s_{0}s_{2}s_{1},s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},s_{1}s_{0}s_{2},$
$\displaystyle
s_{0}s_{1}s_{2}s_{1}s_{0},s_{0}s_{2}s_{1}s_{0},s_{1}s_{0}s_{2},s_{0}s_{2}s_{1}s_{0},s_{1}s_{0}s_{2},s_{0}s_{1}s_{2}s_{1}s_{0},s_{0}s_{2}s_{1},s_{1}s_{0}s_{2},s_{2}s_{1},$
$\displaystyle
s_{1}s_{0}s_{2},s_{2}s_{1},s_{1},s_{1}s_{0}s_{2}s_{1},s_{1}s_{0}s_{2},s_{0}s_{1}s_{2}s_{1},s_{1}s_{0}s_{2},s_{0}s_{1}s_{2}s_{1},s_{1}s_{0}s_{2},s_{0}s_{1}s_{2}s_{1}s_{0})$

Since randomness is built into the algorithm, every time we run it we get
different outcomes. About $20\%$ of the time we actually find a kernel
element, and this takes about a couple of hours on a standard personal
computer.

Other runs of our algorithm discovered two other elements in the kernel of
Garside lengths 59 and 65 respectively. They are

$\kappa_{1}=\Delta^{-29}\sigma_{1}\quad\text{and}\quad\kappa_{2}=\Delta^{-33}\sigma_{2}$

where $\sigma_{1}$ and $\sigma_{2}$ are given by the following words in the
Artin generators, of lengths 174 and 198 respectively:

$\displaystyle\sigma_{1}={\scriptstyle(1,2,1,3,2,2,1,3,1,3,2,2,2,1,3,1,2,2,1,3,1,2,2,1,3,1,3,1,2,3,2,1,1,2,3,2,2,1,3,1,2,3,2,2,1,3,1,3,2,2,2,1,3,1,2,2,1,3,1,}$
$\displaystyle{\scriptstyle
2,2,2,1,3,1,2,3,2,2,1,3,1,2,3,2,2,1,3,1,2,3,2,1,1,3,1,3,1,3,2,2,1,3,1,2,2,1,3,1,2,2,2,1,3,2,2,1,3,1,3,2,1,2,1,3,1,3,2,1,2,1,}$
$\displaystyle{\scriptstyle
3,1,2,3,2,1,1,3,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,1,3,2,2,2,1,3,1)}$
$\displaystyle\sigma_{2}={\scriptstyle(1,3,1,3,1,3,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,}$
$\displaystyle{\scriptstyle
1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,}$
$\displaystyle{\scriptstyle
2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,2,1,3,3,2,2,1,3,3,2,2,1,3,1,2,3,2,1,1,3,2,1,2,1,3,1,3,2,1,2,1,3,1,3,2,2,1,3,2,2,1,3,2,2,1,3,2)}$

Here are the trajectories of $\sigma_{1}$ and $\sigma_{2}$ through the
buckets:

######  Remark 5.1.

The reader wishing to explore more can experiment with the notebook “p=5
kernel elements” available at [8]. We have also implemented a check of our
results in Magma in the file “Magma check.m” which is also available at [8].
It should be easy to modify the Magma file to suit any computer algebra
system.

##  6\. How good is our algorithm?

We regard the fact that our algorithm is able to discover a kernel element
nearly 25 years after the last discovery of a kernel element (for $p=3$ in
[6]) as some evidence that our approach is interesting. On the other hand, it
is interesting to ask: can our algorithm rediscover known kernel elements?

###  6.1. n=4

Here we see a plot Garside of length ($x$-axis) against the minimal projlens
found ($y$-axis), over several runs of our algorithms modulo various integers
$m=2,3,4,5,6,7$:

It immediately finds many kernel elements modulo $2$ and $3$. It also finds
kernel elements modulo $4$. Note also the jagged red line: during these runs
the algorithm found an element of Garside length around 65 with low projlen,
but did not find a kernel element of this length. It did, however find a
kernel element of Garside length around 105 (where the red line finally
touches the $x$-axis). Finally, note that although we know that kernel
elements exist modulo $6$, our algorithm didn’t find them. (The purple line.)

###  6.2. n=5,6

Despite several attempts we have not been able to recover Bigelow’s (integral)
kernel elements for $n=5$ and $n=6$. How close are we to finding these
elements?

It turns out that there is a beautiful and simple idea that allows us to
accurately answer this question. For concreteness, let us take $n=6$ in which
case Bigelow’s kernel element is of Garside length $16$:

$\beta=\Delta^{d}\widetilde{w_{1}}\widetilde{w_{2}}\cdots\widetilde{w_{16}}.$

Now we can modify our code slightly to force it to add each of the Garside
divisors

$\beta_{1}=\widetilde{w_{1}},\quad\beta_{2}=\widetilde{w_{1}}\widetilde{w_{2}},\quad\dots,\quad\beta_{16}=\widetilde{w_{1}}\widetilde{w_{2}}\cdots\widetilde{w_{16}}$

to their appropriate buckets during the reservoir search. In other words, we
peform the reservoir sampling as usual, however we force it to successfully
find $\beta$:

Now for each reservoir containing $\beta_{i}$ we can compute the probability
that a random sample would contain $\beta_{i}$. If we denote this probability
by $P(\beta_{i})$, then

$P(\beta)=\prod_{i=1}^{16}P(\beta_{i})=\prod_{i=1}^{16}\frac{k}{\max(r(\beta_{i}),k)}$

where $k$ denotes the bucket size as above, and $r(\beta_{i})$ denotes the
total number of elements seen by the bucket containing $\beta_{i}$.

With $k=500$ this probability is smaller than $10^{-6}$. Increasing the bucket
size to $10^{5}$ decreased this probability to around $0.0005$. At this point
it is believable that algorithmic improvements (or simply a bigger computer
and bigger buckets!) new kernel elements for $n=6$ might be found. A similar
analysis for $n=5$ shows that this case is considerably harder.

###  6.3. Future Directions

We briefly comment on three avenues which we believe warrant further
exploration.

####  6.3.1. Monte Carlo methods

The task of searching through Garside normal forms in order to find kernel
elements is a textbook example of tree search. This problem features
prominently in computer Chess and Go. In Go, major progress was made in the
1990s and 2000s by employing Monte Carlo evaluation strategies [4]: in order
to decide the strength of a board position, one randomly finishes the game
5000 times and sees how often one wins. We tried a similar method here:

  1. (1)

A database $D$ of promising nodes (with score) is initiated with the identity
element.

  2. (2)

At each step, $\sigma$ is sampled from $D$ (randomly with weighting based on
the score). We then do reservoir sampling starting from each Garside suffix
$\sigma\widetilde{u}$ for $N$ steps. Each suffix is then added to $D$, with
score based on the lowest $\mathsf{projlen}$ seen.

(Thus, we regard exploring the tree of all possible Garside normal forms as a
one-player game, where the goal is to find kernel elements, and a “move”
consists of replacing the current element by a Garside successor.)

We implemented this algorithm and it consistently found kernel elements for
$p=5$. We did several long runs in other settings (e.g. $(n=4,p=7)$,
$(n=5,p=41)$ etc.) without finding kernel elements. In this setting there are
several design choices (e.g. how to implement score and select based upon it,
how to choose $N$, …) which have a big impact on performance. This is worth
investigating systematically and could lead to a much better algorithm.

####  6.3.2. Machine learning methods

We begun this project with the aim of employing machine learning methods. We
outline here one unsuccessful attempt to use vanilla supervised learning to
improve our sampling. Many other experiments are possible, and we hope that
our software can provide a good basis for further experiments.

Consider all elements of Garside length $\ell$. Imagine an oracle $O$ which
takes as input the matrix of an element of Garside length $\ell$ and tells us
the minimum $\mathsf{projlen}$ amongst all Garside successors of Garside
length $\ell+k$ for some value of $k$ (e.g. $k=5$). Then it seems intuitive
that using the oracle $O$ to weight reservoir sampling (i.e. elements with low
projlen in $k$ further steps are more likely to be kept in a bucket) would
lead to better results.

With this motivation in mind, we tried to train a vanilla neural network which
takes as input the matrix of $\sigma$, and attempts to predict the minimal
$\mathsf{projlen}$ in $k$ steps time. Our models attained reasonable training
accuracy ($\sim 80\%$), but seemed to make no difference at all to the long-
term performance of the algorithm.333Some further details on our algorithm: We
encode a matrix $M$ of Laurent polynomials as a list of matrices encoding the
coefficients of $v^{i}$. Because we only care about our matrices up to scalar
multiple, we can assume that the non-zero matrices range from 0 to the
$\mathsf{projlen}$: $M_{0},M_{1},\dots,M_{\mathsf{projlen}(M)}$. Now, after
multiplying $M$ by all Garside successors of length $k$, it is easy to see
that the resulting $\mathsf{projlen}$s only depends on the first and last
$k^{\prime}$ matrices in our list, i.e. on
$M_{0},M_{1},\dots,M_{k^{\prime}},M_{\mathsf{projlen}(M)-k^{\prime}+1},\dots
M_{\mathsf{projlen}(M)}$ for some small value of $k^{\prime}$. We further
simplified our dataset by remembering only
$M_{0}^{\prime},M_{1}^{\prime},\dots,M_{k^{\prime}}^{\prime},M_{\mathsf{projlen}(M)-k^{\prime}+1}^{\prime},\dots
M_{\mathsf{projlen}(M)}^{\prime}$ where $M_{i}^{\prime}$ is a zero-one matrix
whose entries record which entries in $M_{i}^{\prime}$ are non-zero. This list
was then serialized and used as input to a vanilla neural network. In other
words, adding the neural network made no discernable difference to the
smallest $\mathsf{projlen}$ found for large Garside lengths. Thus, our attempt
to use neural networks to spot patterns in Burau matrices was unsuccessful.
This suggests that such patterns are either not there, or are difficult to
detect.444One can also imagine that a drop in $\mathsf{projlen}$ is a rare
event, which is too rare to be picked up by the neural network.

####  6.3.3. Commutators

It is striking that all kernel elements found in [5, 6, 2] are commutators. It
is tempting to try to modify our search regime to use this fact as a prior. It
is not clear how to do so, but a reasonable proposal could lead to better
results. We have not tried to express the elements that we have found as
(close relatives of) commutators.

## References

  * [1] Stephen Bigelow  “Does the Jones polynomial detect the unknot?” Knots 2000 Korea, Vol. 2 (Yongpyong)  In _J. Knot Theory Ramifications_ 11.4, 2002, pp. 493–505
  * [2] Stephen Bigelow  “The Burau representation is not faithful for $n=5$”  In _Geom. Topol._ 3, 1999, pp. 397–404
  * [3] Joan S. Birman  “Braids, links, and mapping class groups” No. 82, Annals of Mathematics Studies  Princeton University Press, Princeton, NJ; University of Tokyo Press, Tokyo, 1974, pp. ix+228
  * [4] Bruno Bouzy and Bernard Helmstetter  “Monte-carlo go developments”  In _Advances in Computer Games: Many Games, Many Challenges_ Springer, 2004, pp. 159–174
  * [5] D. Cooper and D. D. Long  “A presentation for the image of ${\rm Burau}(4)\otimes Z_{2}$”  In _Invent. Math._ 127.3, 1997, pp. 535–570
  * [6] D. Cooper and D. D. Long  “On the Burau representation modulo a small prime”  In _The Epstein birthday schrift_ 1, Geom. Topol. Monogr.  Geom. Topol. Publ., Coventry, 1998, pp. 127–138
  * [7] Amitesh Datta  “A strong characterization of the entries of the Burau matrices of $4$-braids: The Burau representation of the braid group $B_{4}$ is faithful almost everywhere”, 2022  arXiv:2209.10826
  * [8] Joel Gibson, Geordie Williamson and Oded Yacobi  “Software for braids and their quantum representations” Accessed: 2023-10-03, https://github.com/geordw/braids-project
  * [9] Tetsuya Ito  “A kernel of a braid group representation yields a knot with trivial knot polynomials”  In _Math. Z._ 280.1-2, 2015, pp. 347–353
  * [10] D. D. Long and M. Paton  “The Burau representation is not faithful for $n\geq 6$”  In _Topology_ 32.2, 1993, pp. 439–447
  * [11] John Atwell Moody  “The Burau representation of the braid group $B_{n}$ is unfaithful for large $n$”  In _Bull. Amer. Math. Soc. (N.S.)_ 25.2, 1991, pp. 379–384
  * [12] Jeffrey Scott Vitter  “Random sampling with a reservoir”  In _ACM Trans. Math. Software_ 11.1, 1985, pp. 37–57