4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ I guess I was trying to be more specific about the quotients considered, but more general in what I was asking to be true about them. I'll edit. $\endgroup$ Oct 25, 2021 at 17:35
  • 3
    $\begingroup$ Rather than asking about categories in Magma, you should perhaps start by asking whether there is any known algorithm for solving the word problem in these classes of groups. Do you know for certain that the groups $B_n(d)$ have solvable word problem? $\endgroup$
    – Derek Holt
    Oct 25, 2021 at 18:18
  • $\begingroup$ You can just write down a presentation for $B_n(d)$, then input this into GAP, which has some methods for solving the word problem. I wouldn’t be surprised if there are quotients of $B_n$ with undecidable word problem, though. Already for $B_5$ (and higher) the subgroup membership problem is undecidable, as proved by Makanina. $\endgroup$ Oct 25, 2021 at 18:21
  • 3
    $\begingroup$ @Carl-FredrikNybergBrodda: The pure braid group on at least 3 strands subjects onto $F_2$, and thus onto any $2$-generator group (in particular, ones with unsolvable word problem). Inducing these up to the whole braid group, we get quotients with unsolvable word problem. $\endgroup$ Oct 25, 2021 at 18:28
  • 1
    $\begingroup$ Notwithstanding @AndyPutman’s nice observation, the specific examples in the question probably do have solvable word problem. The case $d=2$ is the case of Coxeter groups. (Actually just finite symmetric groups in this case.) I wouldn’t be surprised if quotients with higher $d$ act properly and cocompactly on a CAT(0) complex, analogous to the Davis complex. $\endgroup$
    – HJRW
    Oct 26, 2021 at 7:04

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the detailed and well-researched answer! $\endgroup$ Oct 27, 2021 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.