The Bokut–Fong–Ke–Shiao hypothesis on Gröbner–Shirshov bases for braid semigroups beyond type $A_n$

For a Coxeter matrix $M=(m_{ss'})$ on a finite ordered set $S$, the associated braid semigroup (positive Artin–Tits monoid) $W^+$ is generated by $S$ subject to the braid relations $m(s,s')=m(s',s)$ for $s>s'$, where $m(s,s')$ is the alternating word of length $m_{ss'}$. Bokut, Fong, Ke and Shiao proved that for type $A_n$ (the classical positive braid semigroup in Artin generators) a Gröbner–Shirshov basis exists and yields an elimination-of-leading-words solution of the word problem, and they formulated a general hypothesis describing, by an explicit template of relations and a closure scheme, a Gröbner–Shirshov basis of $W^+$ for an arbitrary Coxeter matrix. The hypothesis is verified only for type $A_n$: no later work in the Gröbner–Shirshov literature proves or refutes it for any other type, while the companion question the same authors posed for the positive braid semigroup in Birman–Ko–Lee generators was later resolved at group level by Bokut and at monoid level by Ali, Iqbal and Nazir. The problem is to prove or disprove the hypothesis in its original generality, with the finite types $B_n$ and $D_n$ as the first open test cases.

Background

A Coxeter matrix on a finite set $S=\{s_1,\dots,s_l\}$ assigns to each pair $s\neq s'$ an integer $m_{ss'}\ge 2$ (with $m_{ss'}=m_{s's}$) describing the symmetry group of reflections in a hyperplane arrangement; the classical example is type $A_n$, where $S=\{s_1,\dots,s_n\}$, $m_{s_i s_{i+1}}=3$ and $m_{s_i s_j}=2$ whenever $|i-j|\ge 2$. Deleting the involutive relations $s^2=1$ from a Coxeter group presentation leaves the braid relations, which define two objects: the Artin–Tits group (for $S_n$ this is Artin's braid group $B_{n+1}$, generated by the Artin generators $\sigma_i$ with $\sigma_{i+1}\sigma_i\sigma_{i+1}=\sigma_i\sigma_{i+1}\sigma_i$ and $\sigma_i\sigma_j=\sigma_j\sigma_i$ for $|i-j|\ge 2$), and the braid semigroup or positive Artin–Tits monoid $W^+$, the monoid of positive words modulo the braid relations. Writing $m(s,s')$ for the alternating word $ss'ss'\cdots$ of length $m_{ss'}$, the braid semigroup of a Coxeter matrix $M$ is

$W^+=\mathrm{sgp}\langle s_1,\dots,s_l \mid m(s,s')=m(s',s),\ s>s',\ m_{ss'}<\infty\rangle.$

Positive braid monoids are central to braid theory because every braid factors into positive parts times a power of the Garside fundamental braid, the mechanism behind Garside's and Birman–Ko–Lee's solutions of the word problem (Garside 1969; Birman–Ko–Lee 1998 introduced a second generating system $a_{ts}$, the band generators, giving a different normal form). A Gröbner–Shirshov basis for a semigroup given by defining relations is, in rewriting language, a completion of the presentation: relative to a fixed monomial well order on words (here deg-lex, which first compares word length and then lexicographic order), every relation is oriented from its larger word to its smaller word, and the set is closed in the sense that every overlap (composition) between two leading words resolves to a common remainder. By the Composition–Diamond lemma of Shirshov and Bokut (equivalent to Newman's diamond lemma), such a set makes the rewriting rule "replace the leading word of a relation by its remainder" — the elimination of leading words (ELW) — terminating and confluent, so every element acquires a unique irreducible normal form and the word problem is solved by repeated ELW reduction. Bokut, Fong, Ke and Shiao (published 2003 in the volume Advances in Algebra; posted as arXiv:0806.1118) proved that for type $A_n$ the braid semigroup $B^+_{n+1}$ admits an explicit Gröbner–Shirshov basis of this kind, and they proposed a general hypothesis for arbitrary Coxeter matrices, obtained by modifying their earlier hypothesis for Coxeter groups (Bokut–Shiao 2001). The hypothesis asserts that a Gröbner–Shirshov basis of $W^+$ consists of the initial braid relations together with all relations obtained from a template family and a closure scheme, described in the problem statement below. The analogy is delicate: the Bokut–Shiao hypothesis for Coxeter groups (the groups $W$ with $s^2=1$) was later refuted in general by Chen and Liu, who exhibited a counterexample and proved it only for Coxeter groups without nontrivial inclusion compositions; since then the group case has been settled type by type (e.g., non-crystallographic types by Lee and Lee, and $G_2,F_4,E_6,E_7,E_8$ by Pang and Wang), but always for $W$, never for $W^+$. For monoids, the only general partial result in rewriting language is due to Bahls and Smith, who constructed a complete rewriting system for large-type Artin monoids (all $m_{ss'}\ge 3$, a class that excludes $B_n$ and $D_n$ because those types contain commuting generator pairs) using orderings of Burckel; this does not verify the specific hypothesis of Bokut–Fong–Ke–Shiao, and Garside theory covers only the spherical (finite Coxeter type) case. A 2014 survey by Bokut and Chen states that Gröbner–Shirshov bases for Artin–Tits groups are not known except for type $A_n$.

Problem Statement

Prove or disprove the hypothesis of Bokut–Fong–Ke–Shiao (Section 3 of 'Gröbner–Shirshov bases for the braid semigroup') for braid semigroups of Coxeter types other than $A_n$ — in its original generality, for the braid semigroup $W^+$ of an arbitrary Coxeter matrix $M$. Fix a linearly ordered finite set $S=\{s_1<\cdots<s_l\}$ with Coxeter matrix $(m_{ss'})$. Following Section 3 of the source, write $m(s,s')$ for the alternating word $ss'ss'\cdots$ of length $m_{ss'}$ beginning with $s$ (defined whenever $m_{ss'}$ is finite); write $(m-i)(s,s')$ for the prefix of $m(s,s')$ of length $m_{ss'}-i$, that is, the alternating word of length $m_{ss'}-i$ beginning with $s$; and write $(m,i)(s,s')$ for the suffix of $m(s,s')$ obtained by deleting its first $i$ letters, $1\le i\le m_{ss'}$. For example, if $m_{ss'}=3$, then $m(s,s')=ss's$, $(m-1)(s,s')=ss'$, $(m,1)(s,s')=s's$, and $(m,2)(s,s')=s$. The hypothesis asserts that, relative to the deg-lex order on words over $S$ (words are compared first by length, then lexicographically), a Gröbner–Shirshov basis $T$ of

$W^+=\mathrm{sgp}\langle s_1,\dots,s_l \mid m(s,s')=m(s',s),\ s>s',\ m_{ss'}<\infty\rangle$

consists of the initial relations of the display above together with all relations equivalent to the following ones in the free partially commutative semigroup, that is, modulo the commuting relations with $m_{ss'}=2$ (the template is displayed exactly as (3.3) of the source, where the letter $m$ abbreviates the Coxeter exponent of the generator pair to which it is attached):

$(m-i_0)(s,s')\,(m-i_1)(s_1,s_2)\cdots(m-i_k)(s_{2k-1},s_{2k})\,m(s_{2k+1},s_{2k+2})$ $=m(s',s)\,(m,i_0)(s_2,s_1)\,(m,i_1)(s_4,s_3)\cdots(m,i_{k-1})(s_{2k},s_{2k-1})\,(m,i_k)(s_{2k+2},s_{2k+1}),$

where $s>s'$, $s_1<s_2$, $\ldots$, $s_{2k-1}<s_{2k}$, $s_{2k+1}<s_{2k+2}$, each $i_j$ satisfies $1\le i_j\le m$, and, for every $j=0,1,\ldots,k$ (with the convention $(s_{-1},s_0)=(s,s')$), the side condition

$(m-i_j)(s_{2j-1},s_{2j})\,m(s_{2j+2},s_{2j+1})\doteq m(s_{2j-1},s_{2j})\,(m,i_j)(s_{2j+2},s_{2j+1})$

holds, where $\doteq$ means equality of literal words in the free semigroup, with no relations used; and together with all further relations $X=Y$ that are equivalent, in the free partially commutative semigroup, to relations obtained by the closure scheme (3.4): a rewrite $A\to B$ with $A=B$ of the displayed template form is called a positive chain and its reverse $B\to A$ a negative chain, and a relation $X=Y$ belongs to $T$ when $X$ goes over by a series of negative chains, performed in the free partially commutative semigroup, $X\to X_1\to\cdots\to X_r=X'=AY_1$, while $Y=BY_1$ with $A\to B$ a positive chain. The problem is to decide whether for every Coxeter matrix all compositions (intersections and inclusions) of relations of $T$ are trivial modulo $T$ — equivalently, whether the ELW rewriting by $T$ (elimination of leading words: repeatedly replace the leading word of a relation by its remainder) is confluent and gives unique irreducible normal forms for $W^+$ — or to exhibit a specific Coxeter type and an explicit nontrivial composition refuting the hypothesis, thereby disproving it in general. The hypothesis is proved for type $A_n$ (the source's Theorem 4.2); the first untested finite cases are types $B_n$ and $D_n$. The companion task the same authors posed — a Gröbner–Shirshov basis for the positive braid semigroup in Birman–Ko–Lee band generators $a_{ts}$, motivated partly by braid-group cryptography — is part of the same normal-form program but has since been resolved (Bokut 2009 at group level, Ali–Iqbal–Nazir 2011 at monoid level), so it is recorded as context rather than as part of the open target.

References

1. L. A. Bokut, Y. Fong, W.-F. Ke, L.-S. Shiao, Gröbner–Shirshov bases for the braid semigroup, in: Advances in Algebra (World Scientific, 2003), pp. 60–72; arXiv:0806.1118. DOI: 10.1142/9789812705808_0005, https://doi.org/10.1142/9789812705808_0005 (also inspected at https://arxiv.org/abs/0806.1118; the arXiv posting is titled "Groebner-Shirshov basis for the braid semigroup")
2. L. A. Bokut, Gröbner–Shirshov basis for the braid group in the Birman–Ko–Lee generators, Journal of Algebra 321 (2009) 361–376; arXiv:0806.1123. DOI: 10.1016/j.jalgebra.2008.10.007, https://doi.org/10.1016/j.jalgebra.2008.10.007
3. L. A. Bokut, Gröbner–Shirshov basis for the braid group in the Artin–Garside generators, Journal of Symbolic Computation 43 (2008) 397–405; arXiv:0806.1125. DOI: 10.1016/j.jsc.2007.02.003, https://doi.org/10.1016/j.jsc.2007.02.003
4. U. Ali, Z. Iqbal, S. Nazir, Canonical Forms and Infimum of Positive Braids, Algebra Colloquium 18 (2011) 1007–1016. DOI: 10.1142/S1005386711000885, https://doi.org/10.1142/S1005386711000885
5. Yuqun Chen, Chanyan Zhong, Gröbner–Shirshov bases for braid groups in Adyan–Thurston generators, Algebra Colloquium 20 (2013) 309–318; arXiv:0909.3639. DOI: 10.1142/S1005386713000278, https://doi.org/10.1142/S1005386713000278
6. Yuqun Chen, Cihua Liu, Gröbner–Shirshov bases for Coxeter groups I, preprint (2009), arXiv:0910.0096, https://arxiv.org/abs/0910.0096
7. L. A. Bokut, L.-S. Shiao, Gröbner–Shirshov bases for Coxeter groups, Communications in Algebra 29 (2001) 4305–4419. DOI: 10.1081/AGB-100106002, https://doi.org/10.1081/AGB-100106002
8. Patrick Bahls, Tyler Smith, Rewriting systems and orderings on Artin monoids, International Journal of Algebra and Computation 17 (2007) 61–75. DOI: 10.1142/S0218196707003482, https://doi.org/10.1142/S0218196707003482
9. L. A. Bokut, Yuqun Chen, Gröbner–Shirshov bases and their calculation, Bulletin of Mathematical Sciences 4 (2014) 325–395. DOI: 10.1007/s13373-014-0054-6, https://doi.org/10.1007/s13373-014-0054-6
10. Joan Birman, Ki Hyoung Ko, Sang Jin Lee, A new approach to the word and conjugacy problems in the braid groups, Advances in Mathematics 139 (1998) 322–353. DOI: 10.1006/aima.1998.1761, https://doi.org/10.1006/aima.1998.1761
11. Zaffar Iqbal, Shamaila Yousaf, Hilbert series of the braid monoid $MB_4$ in band generators, Turkish Journal of Mathematics 38 (2014) 977–984. DOI: 10.3906/mat-1401-58, https://doi.org/10.3906/mat-1401-58
12. Usman Ali, Barbu Berceanu, Canonical forms of positive braids, Journal of Algebra and Its Applications 14 (2015) 1450076. DOI: 10.1142/S0219498814500765, https://doi.org/10.1142/S0219498814500765
13. Xiaowei Pang, Jun Wang, Gröbner–Shirshov bases for the Coxeter groups of the types $G_2,F_4,E_6,E_7$ and $E_8$, preprint (2020), arXiv:2002.07369, https://arxiv.org/abs/2002.07369
14. Jeong-Yup Lee, Dong-il Lee, Gröbner–Shirshov bases for non-crystallographic Coxeter groups, Acta Crystallographica Section A 75 (2019) 584–592; arXiv:1809.08419. DOI: 10.1107/S2053273319002092, https://doi.org/10.1107/S2053273319002092
15. F. A. Garside, The braid group and other groups, The Quarterly Journal of Mathematics 20 (1969) 235–254. DOI: 10.1093/qmath/20.1.235, https://doi.org/10.1093/qmath/20.1.235
16. Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, Choonsik Park, New public-key cryptosystem using braid groups, in: Advances in Cryptology – CRYPTO 2000, Lecture Notes in Computer Science 1880, Springer (2000), pp. 166–183. DOI: 10.1007/3-540-44598-6_10, https://doi.org/10.1007/3-540-44598-6_10