Consider the braid group $B_n$ presented in terms of the usual Artin generators $\sigma_1,\ldots,\sigma_{n-1}$. Now add the additional relations $\sigma_i^k = 1$ for $i=1,\ldots,n-1$. For lack of a better name, I'll call the resulting group $B_n^{(k)}$. $B_n^{(2)}$ is just the symmetric group $S_n$. As discussed in this mathoverflow thread, $B_n^{(k)}$ is infinite unless $\frac{1}{n}+\frac{1}{k} > \frac{1}{2}$. $B_n$ is an automatic group and thus any word $w$ in the Artin generators can be reduced to a normal form that depends only on the group element in $O(|w|^2)$ time. My question is, for fixed $k > 2$, can one reduce a word $w$ in the generators of $B_n^{(k)}$ to a normal form in $\mathrm{poly}(n,|w|)$ time, too? (It appears to me that direct simpleminded adaptation of the algorithm for braid group normal form fails.)
2 Answers
The groups you are considering are a special class of Shephard groups, which are obtained from Artin groups by adding relators $\sigma_i^{k_i}=1$, $0\le k_i<\infty$ for every Artin generator. Biautomaticity of some of all these groups is conjectured in http://arxiv.org/abs/0901.0094 and this conjecture is verified in some cases. Unfortunately for you, the results in this paper require that the Artin graph contains no triangles with label 2, which will exclude quotients of classical braid groups. Nevertheless, you may want to read the paper to see if the methods could be useful in the context of your question.
Correction: The original answer was incorrect, since non-uniform complex hyperbolic lattices are not automatic
There are analogous groups where this does not hold. Thurston has examples of quotients of mapping class groups of the punctured sphere which are non-uniform complex hyperbolic orbifolds (I think with up to 12 punctures) where the braid generators have finite order. These groups are not automatic, since they are the fundamental groups of non-uniform complex hyperbolic lattices by a result of Farb. I'm not sure to what extent his examples generalize though.
-
$\begingroup$ Fundamental groups of complex-hyperbolic orbifold examples of Deligne-Mostow-Thurston-Hirzebruch-... are indeed quotients of braid groups by adding the relators of the type $\sigma_i^{k_k}=1$. However, in these examples you add other relators as well, so they do not answer OP's question. Incidentally, groups in OP's question are called "Shepherd groups". $\endgroup$– MishaNov 25, 2012 at 2:01
-
$\begingroup$ Ok, I thought the only relators came from powers of the generators, since one partially compactifies the moduli space of the n-punctured sphere by lower dimensional moduli where pairs of points collide, which is the 2-codim. strata. I'm not sure where the other relators come from. $\endgroup$– Ian AgolNov 25, 2012 at 6:20