A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids

The symmetric group ${\mathrm{\Sigma }}_n$ is the group of permutations of $n$ elements $\{1,\mathrm{\dots },n\}$. The group ${\mathrm{\Sigma }}_n$ is generated by the transpositions, i.e., the permutations $s_i$ of the two consecutive elements at index $i$ and $i+1$, for $1\le i\le n-1$. Every permutation $w\in {\mathrm{\Sigma }}_n$ can be represented either by a unique one-line word $w(1)w(2)\mathrm{\cdots }w(n)$, where $w(i)$ is the image of $i$ under the permutation $w$, or by a non-unique product of generators $w=s_{i_k}\mathrm{\cdots }{s}_{i_1}$.

An inversion in a permutation $w$ is a pair of indices $(i,j)$ such that and $w(i)>w(j)$. The (Coxeter) length of a permutation $w$, denoted by $\mathrm{\ell }(w)$, is its total number of inversions.

The Lehmer code $L(w)$ of a permutation $w=w(1)w(2)\mathrm{\cdots }w(n)$ is the sequence of positive integers $L(w):=(L{(w)}_1,\mathrm{\dots },L{(w)}_n)$ such that:

i.e., $L{(w)}_i$ counts the number of inversions happening to the right of index $i$. In particular, $0\le L{(w)}_i\le n-i$. Permutations are in bijection with their Lehmer code.

This last property allows us to represent a permutation with a single number, using the factorial number system. Specifically, given a sequence of numbers $𝐚=(a_1,\mathrm{\dots },a_n)$ such that $0\le a_i\le n-i$ for all $i$, one can write uniquely the sequence as a single positive integer:

In particular, the application $\mathrm{\Sigma }\to \{0,\mathrm{\dots },n!-1\}$ sending $w\mapsto F_{L(w)}$ is a bijection. In the following, we call the number $F_{L(w)}$ the index of the permutation $w$.

We prove, in the long version [29], the following basic facts about the encoding:

We consider $B_n$ the braid group on $n$ strands:

The generators ${\{{\sigma }_i^{\pm 1}\}}_i$ are called the Artin generators of the braid group. The monoid with the same presentation, i.e., generated by the ${\{{\sigma }_i^{+1}\}}_i$, is denoted by $B_n^{+}$.

For some of our applications, we are interested in producing braids that we want to make sure get more and more complicated. The notion of Garside structure is instrumental, by providing us with an algorithmic-friendly normal form. We very briefly review the most important aspects, but refer to [13] for details.

Let us denote $[1,\mathrm{\Delta }]$ the braids that realize positive lifts (that is, in $B_n^{+}$) of reduced words from the symmetric group. For example, $s_1{s}_2{s}_1=s_2{s}_1{s}_2\in {\mathrm{\Sigma }}_n$ lifts to ${\sigma }_1{\sigma }_2{\sigma }_1={\sigma }_2{\sigma }_1{\sigma }_2\in B_n$. It is a classical result that the map is well-defined (independent on the choice for the starting word). The half-twist $\mathrm{\Delta }={\sigma }_1\mathrm{\cdots }{\sigma }_{n-1}{\sigma }_1\mathrm{\cdots }{\sigma }_{n-2}\mathrm{\cdots }{\sigma }_1$ is the so-called Garside element. One has a lattice structure [17, 13] on $[1,\mathrm{\Delta }]$, extending to $B_n^{+}$, with left divisibility given by:

Similarly, one can define a notion of right divisibility, ${\le }_R$. We are now ready to obtain the normal form $b_k\mathrm{\cdots }{b}_1$ of a braid $b\in B_n^{+}$ by inductively defining:

If one adds the fact that any braid $b\in B_n$ can be written as ${\mathrm{\Delta }}^r{b}^{+}$ with $b^{+}\in B_n^{+}$, then one has a preferred expression for any braid.

At some point, we will be interested in using the Garside normal form to generate complicated braids. This will be made algorithmic thanks to the following lemma.

The divisibility in $[1,\mathrm{\Delta }]$ being controlled by ${\mathrm{\Sigma }}_n$, the computations can be made in the symmetric group. More details about the underlying automaton appear in Section 5.3.

The Hecke algebra is an ubiquitous object in representation theory. We introduce it as a quotient of the braid group, which makes it most natural for the computations we care about, and we refer to [29] and to Mathas’ book [30] for further details and context.

We denote by $\psi :B_n\to {\mathscr{H}}_n$ the natural induced map. We quickly review some useful basic properties of the Hecke algebra that will be instrumental to us.

The content of the above lemma is that the image of $s$ does not depend on the word chosen to write it. This is simply because the $T_s$ satisfy the same braiding relations as the elements in the symmetric group. To our eyes, the key property is that we have a basis indexed by permutations, which can be efficiently handled. For computation purposes, we also take advantage of the fact that the structure constants of this basis are quite simple, as expressed in the following classical lemmas [30, Theorem 1.11].

When we compute knot invariants, it is convenient to take braid closures of braids. Assuming that $P$ is a knot invariant, it is clear that $P(\widehat{b_1{b}_2})=P(\widehat{b_2{b}_1})$. This remark motivates the introduction of an intermediary object $\mathrm{Tr}({\mathscr{H}}_n)$ which is obtained from ${\mathscr{H}}_n$ by formally adding the relation $b_1{b}_2=b_2{b}_1$. This makes it possible to break the computation into a first step ${\mathscr{H}}_n\to \mathrm{Tr}({\mathscr{H}}_n)$, where elements are reduced as much as possible using the trace relation $b_1{b}_2=b_2{b}_1$, before using information about the specific invariant we want to compute to go from $\mathrm{Tr}({\mathscr{H}}_n)$ to $\mathbb{Z}[q^{\pm 1}]$. Note that because $\psi :B_n\to {\mathscr{H}}_n$ is a representation, for any two braids $b_1,b_2\in B_n$, we have $\mathrm{Tr}(\psi (b_1{b}_2)=\mathrm{Tr}(\psi (b_1)\psi (b_2))=\mathrm{Tr}(\psi (b_2)\psi (b_1))=\mathrm{Tr}(\psi (b_2{b}_1))$.

Finally, when searching for counterexamples, we measure how far an element of ${\mathscr{H}}_n$ is from the identity. We use the following notion, that we adapt from [18].

Most of the notions we have defined here enjoy similar definitions with $\mathbb{Z}/p\mathbb{Z}$ in place of $\mathbb{Z}$. We use this context in Section 5.

For a braid in $B_n$, we represent its image in ${\mathscr{H}}_n$ by an array of coordinates (Laurent polynomials) in the basis $\{T_w\}$. Specifically, a vector $x={\sum }_{w\in {\mathrm{\Sigma }}_n}{a}_w{T}_w\in {\mathscr{H}}_n$, with $a_w\in \mathbb{Z}[q^{\pm 1}]$, is represented by a length $n!$ array $\mathrm{𝚑𝚎𝚌𝚔𝚎}$, such that $\mathrm{𝚑𝚎𝚌𝚔𝚎}[j]=a_w$ whenever the permutation $w$ has index $F_{L(w)}=j$.

Recall that the one-line word $w(1)\mathrm{\cdots }w(n)$ of a permutation $w$, and its index $F_{L(w)}$ can be obtained from one another in $O(n\log n)$ operations. Note also that the maximal value $n!-1$ of an index is below $2^{64}$ when $n\le 20$, which will always be the case in this article ; permutation indices are stored as standard integers.

The image of ${\sigma }_{i_1}$ is $T_{s_{i_1}}\in {\mathscr{H}}_n$, and Lemma 8, shows that the image of ${\sigma }_{i_1}^{-1}$ is $q^{-2}{T}_{s_{i_1}}+(1-q^{-2})\in {\mathscr{H}}_n$. Consequently, if ${ϵ}_1=1$, at the initialization, only the coefficient corresponding to $s_{i_1}$ is $1$, all other ones being $0$. If ${ϵ}_1=-1$, then we have the coefficient $1-q^{-2}$ at index $0$, $q^{-2}$ at the index representing $s_{i_1}$, and $0$ elsewhere.

We suppose that at the beginning of step $j$ of the algorithm, $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ stores the coordinates of the image of ${\sigma }_{i_{j-1}}^{{ϵ}_{j-1}}\mathrm{\cdots }{\sigma }_{i_1}^{{ϵ}_1}$, that we update with the next generator ${\sigma }_{i_j}^{{ϵ}_j}$.

Since $\psi$ is a group homomorphism, we have $\psi (b_{(j)})=T_{{\sigma }_{i_j}}^{{ϵ}_j}\psi (b_{(j-1)})$. We consequently need to update the coordinates of $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ following the local relations described in Lemmas 7 and 8. We do so in the single pass through $\mathrm{𝚑𝚎𝚌𝚔𝚎}$, without allocating more than $O(1)$ Laurent polynomials in memory:

The correctness of the initialization phase is guaranteed by Lemmas 7 and 8. We focus on the inductive step. Consider any permutation $w\in \mathrm{\Sigma }$. According to Lemmas 7 and 8, both $T_{s_{i_j}}^{\pm 1}{T}_w$ and $T_{s_{i_j}}^{\pm 1}{T}_{s_{i_j}w}$ give linear combinations of $T_w$ and $T_{s_{i_j}w}$, because $s_{i_j}(s_{i_j}w)=w$. Additionally, for any permutation $w^{\prime }\notin \{w,s_{i_j}w\}$, the product $T_{s_{i_j}}^{\pm 1}{T}_{w^{\prime }}$ contains no term $T_w$ or $T_{s_{i_j}w}$. Thus the pair of coordinates of $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ corresponding to permutations $w$ and $s_{i_j}w$ can be updated independently from the rest of the array, and their new values is a combination of their previous values. We update them at once in the core of the (outer) if loop of Algorithm 1.

Finally, the condition of the (outer) if loop guarantees that we proceed to the update once. Indeed, the length $\mathrm{\ell }$ being the number of inversions, we have $\mathrm{\ell }(s_{i_j}w)\in \{\mathrm{\ell }(w)-1,\mathrm{\ell }(w)+1\}$. In consequence, considering the two permutations $w$ and $(s_{i_j}w)$, multiplying by $s_{i_j}$ exactly increases the length once and decreases the length once.

In light of the above, the induction algorithm does compute $\psi (b_{(j)})$ from $\psi (b_{(j-1)})$ and, at the end of the algorithm, we are left with $\psi (b)={\sum }_{w\in {\mathrm{\Sigma }}_n}{a}_w{T}_w$.

The HOMFLY-PT polynomial [15, 33] is a famous 2-variable knot invariant, that can be specialized to both the Jones polynomial and the Alexander polynomial. If one starts from a knot presented as a braid closure $\widehat{b}$ (see Figure 1), then, up to renormalization, the invariant is computed by taking a trace of the image of the braid $b$ in the Hecke algebra. We now make this more precise, and we refer to the long version [29] for another presentation of the invariant.

As in Section 3, we start from a braid $b={\sigma }_{i_c}^{{ϵ}_c}\mathrm{\cdots }{\sigma }_{i_1}^{{ϵ}_1}$, and pre-compute the array $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ encoding the Hecke representation $\psi (b)={\sum }_{w\in {\mathrm{\Sigma }}_n}{a}_w{T}_w$ with the algorithm of Theorem 10.

Our strategy is to simplify, in a single pass through $\mathrm{𝚑𝚎𝚌𝚔𝚎}$, the entries of the array, using the defining property of the trace, i.e., $\mathrm{Tr}(\psi (b{b}^{\prime }))=\mathrm{Tr}(\psi (b^{\prime }b))$ for $b,b^{\prime }$ braids in $B_n$. We do not simplify the array all the way down, but instead only keep entries corresponding to permutations $w$ with a simple form (called annularly reduced), and for which we know how to compute the participation to the final HOMFLY-PT polynomial.

Before describing the algorithm, we introduce some definitions and lemmas.

Our algorithm reduces braids to annularly reduced ones, using the following lemma.

The correctness of the algorithm is guaranteed by the diverse lemmas proved along the way.

We have compared our code with the advanced C++ library Regina [9], implementing Burton’s state of the art algorithm [7] for the HOMFLY-PT polynomial. We have run our experiments on an 8 cores, 32Gb RAM computer; parallel implementations use the library Intel::TBB. We restrict our attention to braids whose closures lead to knots. The computation of the Hecke representation, which largely dominates the timings for our computation of the HOMFLY-PT polynomial, can be implemented in parallel, as described in Remark 12, while Regina does not admit a parallel implementation and the algorithm it implements may not parallelize as naturally as ours.

We have generated $p$-strands torus braids $T_{p,q}$ and $p$-strands weaving braids $W_{p,q}$, in their standard form (see Figure 3), keeping only those parameters $q$ for which the closure is a knot. We have used them as is in our algorithm. Regina working with knot diagrams and treewidth, we have run simplification heuristics and the construction of the tree decomposition, before computing the HOMFLY-PT polynomial (and before starting the timer). However, for these knots, the braid presentation is expected to be minimal for both size and parameter.

In Figure 4 we compare the running time of our algorithm not using parallelism, against the algorithm from Regina for torus braids $T_{p,q}$ and weaving braids $W_{p,q}$, for and all values of $q=p+1,\mathrm{\dots },q_{\max }$, such that the closures of the braids lead to knots (i.e., $\gcd (p,q)=1$), with $q_{\max }$ picked such that the braids $T_{p,q_{\max }}$ and $W_{p,q_{\max }}$ have approximately $600$ crossings. The results are very similar for torus and weaving braids, highlighting the fact that the running times depends mostly on the combinatorics of the input diagrams, and not so much on the algebraic computations. Our implementation consistently outperforms Regina on braids with more than 4 strands, by a factor ranging from 3 (shorter braids) to 9 (longer braids) for braids on 4 strands, a factor ranging from 3 to 4 for 5-braids.

In Figure 4, Regina is faster on the smaller 3-strands examples, by a factor 3 on shorter braids, and a smaller factor 1.3 on the larger braids ; all these timings are below 0.3 seconds, and may be explained by a slower initialization of data on our side. The global tendency is that our algorithm, even on its non-parallel form, gets better on longer braids (the slopes $\alpha$ of interpolating lines is $0.78\le \alpha \le 0.8$ on all examples) and on braids with more strands.

On braids with $\ge$ 6 strands, Regina starts to swap due to excessive memory consumption, leading to impractical running times ; to the contrary, our implementation continues to be practical, Table 1 and see Figure 5 for much larger examples.

In Figure 5, we compare the performance of our implementation with and without parallelism. Recall that the parallelization is on the array $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ of length $n!$ (working with an $n$-strands braid). In consequence, we see the gain of parallelism increasing with the number of strands: first, the gain range from a factor $1.6$ to $2.4$ on 3-strands, from $3.3$ to $4.54$ 4-strands, and from $3.8$ to $6.25$ on 5-strands. On braids with $6,7,8$-strands, the gain ranges between a factor $5$ to $7.14$, near the optimal 8 (on 8 cores); see Figure 5.

Finally, the memory consumption of our implementation is much more frugal than Regina, and remains very applicable for large number of strands. The memory cost depends mostly on the number of strands; however, for a fixed number of strands, longer braids tend to consume slightly more memory because the Laurent polynomials stored in the array $\mathrm{𝚑𝚎𝚌𝚔𝚎}$ become more complicated; the memory consumption of longer braids is shown in Table 1).

In conclusion, our implementation is very competitive for knots represented by braids, even with a fairly large number of strands. It also combines very well with parallelism. We apply our parallel implementation in experimental mathematics in Section 5 to investigate algebraic properties of the Hecke algebra.

The decomposition of ${\mathscr{H}}_4$ into irreducible $B_4$ representations only contains the Burau representation as possibly faithful summand. The latter being not faithful at $p=2,3,5$ implies the same for the Hecke representation. We indeed found such counterexamples for $p=2$ and $3$, as well as with $p=4$, that we present in the long version [29].

The same search performed on $B_5$ with base ring $\mathbb{Z}/2\mathbb{Z}$ also yielded a counterexample to faithfulness. In this case, non-faithfulness follows by including the $B_4$ kernel into $B_5$. Here we could run a direct search in $B_5$ to find explicit counterexamples.

To generate braids, we use the following finite state automaton.

We create increasingly complicated braids by applying to a Garside normal form $b_k\mathrm{\cdots }{b}_1$ any (possibly randomly chosen) letter from $\mathrm{𝐆𝐚𝐫𝐬𝐢𝐝𝐞}(b_k)$. The construction of the automaton can be made very efficient thanks to the following observation.