The braid semigroup W+(M)W^+(M), i.e. the positive Artin monoid of a Coxeter matrix MM, is the monoid on the generators of MM subject only to the braid relations m(s,s′)=m(s′,s)m(s,s')=m(s',s), with no involutions. For type AnA_n the Gröbner–Shirshov basis of the braid semigroup in the Artin generators under the deg-lex order was computed by Bokut, Fong, Ke and Shiao; it is an infinite but finitely parametrized family of relations, not a finite basis, and finite Gröbner–Shirshov bases for type AnA_n are known only in the other generating sets mentioned below. Bokut, Fong, Ke and Shiao formulated a general hypothesis predicting the shape of such a basis for a braid semigroup of arbitrary Coxeter type. The hypothesis is verified only for type AnA_n, the shape of a Gröbner–Shirshov basis is known for the braid semigroup of no other Coxeter type, and no criterion is known that, from the Coxeter matrix and the chosen monomial order, describes the result of Shirshov's completion algorithm. The problem asks for the completed basis in general (or a refutation of the predicted shape); whether a finite basis always exists is a separate question, since the predicted shape is an infinite family.

Background

A Coxeter matrix M=(mss′)M=(m_{ss'}) on a finite set SS is a symmetric matrix with mss=1m_{ss}=1 and mss′∈{2,3,… }∪{∞}m_{ss'}\in\{2,3,\dots\}\cup\{\infty\}; the associated Coxeter group W(M)W(M) is generated by SS with relations s2=1s^2=1 and (ss′)mss′=1(ss')^{m_{ss'}}=1. Deleting the involutions s2=1s^2=1 and keeping only the braid relations gives the Artin group, and its positive part — the monoid with generators SS and relations m(s,s′)=m(s′,s)m(s,s')=m(s',s) for s>s′s>s' with mss′<∞m_{ss'}<\infty, where m(s,s′)m(s,s') denotes the alternating word of length mss′m_{ss'} — is the braid semigroup or positive Artin monoid W+(M)W^+(M) studied by Bokut–Fong–Ke–Shiao. For MM of type AnA_n this is the classical positive braid monoid Bn+1+B^+_{n+1} with relations aiai+1ai=ai+1aiai+1a_ia_{i+1}a_i=a_{i+1}a_ia_{i+1} and aiaj=ajaia_ia_j=a_ja_i for ∣i−j∣≥2|i-j|\ge 2. Artin monoids are known to embed into their Artin groups (Paris 2002), and they have solvable word problems and normal forms in general via the theory initiated by Brieskorn and Saito; by contrast, the word problem for Artin groups is open in general.

A Gröbner–Shirshov (GS) basis is the noncommutative analogue of a Gröbner basis: fix a monomial well order (a well order on words compatible with concatenation; the standard example is the deg-lex order, which first compares word length and then lexicographically) on the free monoid S∗S^*; a set of monic relations (relations whose leading word has coefficient 1) is a GS basis when all its compositions — overlap of two relations on a common part of their leading words (intersection compositions) or containment of one leading word inside another (inclusion compositions) — reduce to zero modulo the set itself. By the Composition–Diamond Lemma (going back to Shirshov, Newman's Diamond Lemma, and Buchberger's theorem), a GS basis yields a linear basis of irreducible words (standard monomials) for the presented algebra or semigroup, analogous to the Poincaré–Birkhoff–Witt (PBW) monomial basis of a universal enveloping algebra — equivalently, reading relations left-to-right, a confluent and terminating rewriting system that computes unique normal forms. Shirshov's completion algorithm (the noncommutative Buchberger algorithm) iteratively adjoins nontrivial compositions; the process need not terminate, and the completed basis need not be finite, depending on the presentation and the chosen order.

For type AnA_n, Bokut–Fong–Ke–Shiao computed the minimal GS basis of Bn+1+B^+_{n+1} in the Artin generators under deg-lex and formulated a general Hypothesis for the braid semigroup of an arbitrary Coxeter matrix: the GS basis should consist of the initial braid relations plus relations of an explicit predicted shape (alternating chains of prefixes of braid words, of their images under the commuting relations, and of compositions built from them by positive and negative chains). Supporting type-AA results exist in other generating sets: the Adyan–Thurston generators, also called band generators, aij=aiai+1⋯aj−1ajaj−1⋯aia_{ij}=a_i a_{i+1}\cdots a_{j-1}a_j a_{j-1}\cdots a_i, which transport one strand around a block of its neighbours; the Artin–Garside generators, obtained by adjoining the Garside fundamental braid Δ\Delta; and the Birman–Ko–Lee generators, a band-style alternative generating set introduced by Birman, Ko and Lee (Bokut–Vesnin; Chen–Zhong; Bokut). For the analogous question on Coxeter groups themselves, the Bokut–Shiao conjecture on the shape of the basis was refuted by Chen–Liu, who exhibited a Coxeter group whose completion forces relations outside the conjectured families; the finite Coxeter groups have since been treated completely, case by case and largely by hand (types G2,F4,E6,E7,E8G_2,F_4,E_6,E_7,E_8 by Pang–Wang, and the non-crystallographic types H2,H3,H4H_2,H_3,H_4 by Lee–Lee, whose H4H_4 computation involves 11,400 standard monomials). On the rewriting side, Gaussent–Guiraud–Malbos proved that every Artin monoid admits convergent (terminating and confluent) presentations obtained by homotopical completion — a Knuth–Bendix-type completion enriched with coherence three-cells — of Garside's presentation, the presentation built from the simple elements (left divisors of the fundamental braid Δ\Delta of Garside's 1969 theory) — but these presentations are infinite, so they do not answer the finiteness question. Whether a finite GS basis exists for the braid semigroup of any non-AA Coxeter type remains without a general answer (in the Artin generators the type-AnA_n basis is itself the infinite family above).

Problem Statement

Let M=(mss′)M=(m_{ss'}) be an arbitrary Coxeter matrix on a finite linearly ordered set SS, let W+(M)W^+(M) be the associated braid semigroup (positive Artin monoid), and fix an arbitrary but fixed monomial well order on the free monoid S∗S^* (the deg-lex order being the standard choice); the two questions below are asked relative to this chosen order. First, is the Bokut–Fong–Ke–Shiao Hypothesis correct: is the Gröbner–Shirshov basis of W+(M)W^+(M) obtained by completing the initial braid relations with exactly the relations of their predicted shape (families (3.3)–(3.4) and their equivalents under the commuting relations) — an infinite but finitely parametrized family of relations — for every Coxeter matrix MM? The first question is resolved either by a proof that for every W+(M)W^+(M) the completion of the initial braid relations yields exactly the predicted relations or by exhibiting an MM whose completion forces a relation outside families (3.3)–(3.4); a proof of the Hypothesis establishes the predicted shape only and does not by itself produce a finite basis. Second, does every W+(M)W^+(M) admit a finite Gröbner–Shirshov basis — equivalently, a finite confluent and terminating rewriting system yielding unique normal forms and a standard-monomial basis — in at least one of the standard generating sets, namely the Artin generators, the Adyan–Thurston (band) generators, the Artin–Garside generators, and the Birman–Ko–Lee generators (the band-style generators introduced by Birman, Ko and Lee as a classical alternative to the Artin generators), the generating set being allowed to depend on MM? The second question is resolved either by a proof that for every MM some generating set in this class admits a finite Gröbner–Shirshov basis or by an explicit Coxeter matrix MM for which none of them does. The first question is proven only for type AnA_n, where the Artin-generator basis is the infinite family above; the second question is open for types other than AnA_n (for type AnA_n, finite bases have been obtained in generating sets other than the Artin generators, as recorded in the Background).

References

  1. L. A. Bokut, Y. Fong, W.-F. Ke, L.-S. Shiao, Gröbner–Shirshov basis for the braid semigroup, 2008, arXiv:0806.1118, https://arxiv.org/abs/0806.1118
  2. L. A. Bokut, L.-S. Shiao, Gröbner–Shirshov bases for Coxeter groups, Communications in Algebra 29 (2001), DOI 10.1081/AGB-100106002, https://doi.org/10.1081/AGB-100106002
  3. Y. Chen, C. Liu, Gröbner–Shirshov bases for Coxeter groups I, 2009, arXiv:0910.0096, https://arxiv.org/abs/0910.0096
  4. J.-Y. Lee, D.-I. Lee, Gröbner–Shirshov bases for non-crystallographic Coxeter groups, Acta Crystallographica Section A 75 (2019) 584–592, DOI 10.1107/S2053273319002092, https://arxiv.org/abs/1809.08419
  5. X. Pang, J. Wang, Gröbner–Shirshov bases for the Coxeter groups of the types G2, F4, E6, E7 and E8, 2020 (v2 2026), arXiv:2002.07369, https://arxiv.org/abs/2002.07369
  6. L. A. Bokut, A. Vesnin, Gröbner–Shirshov bases for some braid groups, Journal of Symbolic Computation 41 (2006) 357–371, DOI 10.1016/j.jsc.2005.09.009, https://doi.org/10.1016/j.jsc.2005.09.009
  7. Y. Chen, C. Zhong, Gröbner–Shirshov bases for braid groups in Adyan–Thurston generators, 2009, arXiv:0909.3639 (also Algebra Colloquium 20 (2013), DOI 10.1142/S1005386713000278), https://arxiv.org/abs/0909.3639
  8. S. Gaussent, Y. Guiraud, P. Malbos, Coherent presentations of Artin monoids, Compositio Mathematica 151 (2015), DOI 10.1112/S0010437X14007842, https://arxiv.org/abs/1203.5358
  9. L. Paris, Artin monoids inject in their groups, Commentarii Mathematici Helvetici 77 (2002), DOI 10.1007/s00014-002-8353-z, https://doi.org/10.1007/s00014-002-8353-z
  10. E. Brieskorn, K. Saito, Artin-Gruppen und Coxeter-Gruppen, Inventiones Mathematicae 17 (1972) 245–271, DOI 10.1007/BF01406235, https://doi.org/10.1007/BF01406235
  11. R. Boyd, R. Charney, R. Morris-Wright, S. Rees, The Artin monoid Cayley graph, 2023, arXiv:2303.09504, https://arxiv.org/abs/2303.09504