I'm trying to understand some things about quotients of braid groups, and particularly I'd like to solve the word problem for some elements of these quotients. I'm using MAGMA to try to access this, but I can't seem to find whether MAGMA's `GrpBrd` has a quotient construction. The more general finitely-presented group category `GrpFP` does not have an implementation for the word problem.


To be more specific about the groups considered, I'm looking at the quotients of the braid groups $B\_n(d)=B\_n/\langle \sigma\_i^d \rangle$ where each Artin generator has some fixed finite order. Do these things fit into any category of groups in MAGMA that has a word problem implementation? I don't care which category these land in, just that I can compute with them somehow.



Good algorithmic properties for quotients of braid groups
Patrick Dehornoy's handle reduction [1] technique that solves the word problem in the braid group can be modified so that it seems to solve the word problem in the groups of the form $B\_{n}(d)$. In practice, for all the braid words $w$ that I have tested that are in the normal subgroup generated by $\sigma\_{i}^{d}$, the algorithm is able to quickly show that $w$ is equivalent in $B\_{n}(d)$ to the identity $e$ by applying the braid group identities together with the identity $\sigma\_{i}^{d}=e$. If the algorithm gets stuck and is unable to reduce $w$ to $e$ after enough time, then we can be confident that $w$ is not equivalent to the identity $e$.


We say that a braid word is a $\sigma\_{i}$-handle if it is of the form
$\sigma\_{i}^{c}u\sigma\_{i}^{-c}$ where $u$ is a braid word that does not contain any instance of $\sigma\_{j}$ or $\sigma\_{j}^{-1}$ whenever $j\geq i$. A good $\sigma\_{i}$-handle is a $\sigma\_{i}$-handle that does not contain a subword that is a $\sigma\_{i-1}$-handle; equivalently, a good $\sigma\_{i}$-handle is a $\sigma\_{i}$-handle that either has no instance of $\sigma\_{i-1}$ or has no instance of $\sigma\_{i-1}^{-1}$.


Consider the following moves that relate braid words to other braid words.


Move 1: (handle reduction) Suppose that $z=u\sigma\_{i}^{r}v\sigma\_{i}^{-r}w$, $r\in\{-1,1\}$, and
$\sigma\_{i}^{r}v\sigma\_{i}^{-r}$ is a good $\sigma\_{i}$-handle where $r\in\{-1,1\}$. Then perform the replacement $z\mapsto uv'w$ where $v'$ is the word obtained from $v$ by replacing each instance of $\sigma\_{i-1}^{s}$ where $s\in\{-1,1\}$ with
$\sigma\_{i-1}^{-r}\sigma\_{i}^{s}\sigma\_{i-1}^{r}$. Observe that the resulting braid word obtained after applying this move represents the same braid.


Move 2: Replace each $\sigma\_{i}^{r}$ where $r\in\{1,-1\}$ with $\sigma\_{n-i-1}^{r}$. This move conjugates the braid with the half-twist $\Delta\_{n}$. This move together with Move 1 allows us to reduce right handles as well as left handles.


Move 3a: $u\sigma\_{i}^{r}v\mapsto u\sigma\_{i}^{d-r}v$ whenever $|d-r|\leq|r|$


Move 3b: $u\sigma\_{i}^{r}v\mapsto u\sigma\_{i}^{d+r}v$ whenever $|d+r|\leq|r|$


Observe that the resulting braid word obtained after applying Move 3 represents the same element in $B\_{n}(d)$. We observe that if we obtain the empty word from $w$ by applying Moves 1-3, then $w$ represents the identity in $B\_{n}(d)$.


Patrick Dehornoy has proven that the process of simply applying Move 1 (handle reduction) always terminates, and a braid word $w$ represents the trivial braid in $B\_{n}$ if and only if this process terminates with the identity braid. In practice, handle reduction solves the word problem for braid groups very quickly. Moves 1-2 are both applied in order to heuristically minimize the length of a braid word representing a braid, and this braid word minimization technique has been used to attack braid based cryptosystems [2].


In all the words $w$ that I have shown to be equivalent in $B\_{n}(d)$ to the identity, I was able to reduce $w$ to the identity simply by haphazardly applying Moves 1-3. Unfortunately, I do not know how to formally prove that one can solve the word problem in $B\_{n}(d)$ by demonstrating that Moves 1-3 always simplifies a word $w$ to the empty word in a reasonable amount of time whenever $w$ represents the identity in $B\_{n}(d)$.


[1] <https://www.lmno.cnrs.fr/archives/dehornoy/Surveys/Dhn.pdf>


[2] A practical attack on a braid group based cryptographic protocol. Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov. 2005
<https://iacr.org/archive/crypto2005/36210085/36210085.pdf>


