Bokut and Shiao (2001) computed Gröbner–Shirshov bases for the finite Coxeter groups of types AnA_n, BnB_n, DnD_n and conjectured that a natural completion pattern works for every Coxeter group; Chen and Liu (2009) disproved this with an explicit rank-4 Coxeter matrix and recorded a revised conjecture of L. A. Bokut that the natural relation set is a pre-Gröbner–Shirshov basis of every Coxeter group. Since then, all Gröbner–Shirshov basis computations for Coxeter groups have been type-by-type (finite types completed by Pang–Wang in 2020; affine types A~n\tilde{A}_n, C~n\tilde{C}_n, B~n\tilde{B}_n, D~n\tilde{D}_n treated individually through 2024), and no uniform structural theorem — or refutation of one — covering an arbitrary Coxeter matrix is known. The problem is to settle Bokut's revised pre-Gröbner–Shirshov-basis conjecture and to formulate and establish (or disprove) a corrected uniform pattern describing which relations are forced, from which normal forms follow for every Coxeter group.

Background

A Coxeter group is the group W(M)W(M) presented by generators s1,…,sns_1,\dots,s_n subject to the involutive relations si2=1s_i^2=1 and the braid relations (sisj)mij=1(s_i s_j)^{m_{ij}}=1, where the Coxeter matrix M=(mij)M=(m_{ij}) is symmetric with mii=1m_{ii}=1 and mij∈{2,3,… }∪{∞}m_{ij}\in\{2,3,\dots\}\cup\{\infty\} for i≠ji\neq j; an entry mij=∞m_{ij}=\infty means no relation is imposed between sis_i and sjs_j. The finite irreducible Coxeter groups are classified by Coxeter graphs (types AnA_n, BnB_n, DnD_n, G2G_2, F4F_4, E6E_6, E7E_7, E8E_8, the dihedral types, and the non-crystallographic types H2H_2, H3H_3, H4H_4), and the affine Weyl groups (A~n\tilde{A}_n, B~n\tilde{B}_n, C~n\tilde{C}_n, D~n\tilde{D}_n, and the affine exceptional types) are their infinite crystallographic relatives.

A Gröbner–Shirshov (GS) basis is the noncommutative analogue of a Gröbner basis: a set of rewriting rules u=vu=v with leading (left) word uu under a fixed monomial order — here the degree-lexicographic (deg-lex) order on words in the sis_i with the fixed generator order s1<⋯<sns_1<\cdots<s_n, the convention of Chen–Liu — such that every composition, i.e. every ambiguity arising when the leading word of one rule overlaps the end of another (intersection composition) or contains another (inclusion composition), resolves to a common irreducible form. By Shirshov's Composition–Diamond Lemma, a GS basis yields a confluent rewriting system, so the irreducible words (standard monomials) give canonical normal forms and a linear basis of the group algebra; this solves the word problem and underpins computations in related braid and Hecke-type algebras. A set of relations SS is a pre-GS basis (the terminology of Chen–Liu) if there exists a set RR with Id(R)=Id(S)Id(R)=Id(S) such that RR is a GS basis and every r∈Rr\in R satisfies ∣rˉ∣=∣sˉ∣|\bar{r}|=|\bar{s}| for some s∈Ss\in S, with either r=sr=s or rr obtained from such an ss by a finite sequence of eliminations of leading words (ELW's) of relations from S∖{s}S\setminus\{s\}; for an effective set SS this still suffices for the solvability of the word problem.

The natural relation set for a Coxeter presentation consists of the involutive relations si2=1s_i^2=1, the commutation relations sjsi=sisjs_j s_i=s_i s_j for mij=2m_{ij}=2, the alternating braid relations sisjsi⋯=sjsisj⋯s_i s_j s_i\cdots=s_j s_i s_j\cdots (both sides of length mijm_{ij}) for finite mij≥3m_{ij}\ge 3, and the enlarged family (3)(3) of relations between products of alternating words described below. In the notation of Chen–Liu (arXiv:0910.0096), where m(s,s′)m(s,s') denotes the alternating word ss′s⋯ss's\cdots of length mss′m_{ss'} in s,s′s,s' and (m−i)(s,s′)(m-i)(s,s') the alternating word of length mss′−im_{ss'}-i starting with ss: (1)(1) is the set of involutive relations s2=1s^2=1; (2)(2) is the set of relations m(s,s′)=m(s′,s)m(s,s')=m(s',s) for s>s′s>s' and all finite mss′m_{ss'}, so that (2)(2) comprises both the commutation relations (mss′=2m_{ss'}=2) and the alternating braid relations (mss′≥3m_{ss'}\ge 3); (3)(3) is the enlarged family of relations between products of alternating words established in Bokut–Shiao's Lemma 3.1, (m−1)(s0,s0′)(m−1)(s1,s1′)⋯(m−1)(sk,sk′) m(sk+1,sk+1′)=m(s0′,s0)(m−1)(s1,s1′)⋯(m−1)(sk,sk′)(m−1)(sk+1,sk+1′),(m-1)(s_0,s_0')(m-1)(s_1,s_1')\cdots(m-1)(s_k,s_k')\,m(s_{k+1},s_{k+1}')=m(s_0',s_0)(m-1)(s_1,s_1')\cdots(m-1)(s_k,s_k')(m-1)(s_{k+1},s_{k+1}'), where k≥0k\ge 0 and si+1′s_{i+1}' equals si′s_i' if msisi′m_{s_i s_i'} is even and sis_i if msisi′m_{s_i s_i'} is odd; and (3′)(3') is the subset of (3)(3) satisfying Chen–Liu's extra conditions (4)–(5), namely s0>s0′s_0>s_0', si<si′s_i<s_i' for 1≤i≤k+11\le i\le k+1, and {si,si′}≠{si+1,si+1′}\{s_i,s_i'\}\neq\{s_{i+1},s_{i+1}'\} for 0≤i≤k0\le i\le k. Bokut and Shiao (2001) computed GS bases for types AnA_n, BnB_n, DnD_n and conjectured a general pattern: that for every Coxeter matrix, completing the set (1),(2),(3′)(1),(2),(3') to a GS basis requires only commutation-type additions. Chen and Liu (2009) disproved this: for the rank-4 Coxeter matrix with m12=m23=m24=∞m_{12}=m_{23}=m_{24}=\infty, m13=3m_{13}=3, m14=2m_{14}=2, m34=5m_{34}=5, the completion forces genuinely new braid-type relations. They classified the four possible nontrivial inclusion-composition patterns (C1–C4) for general matrices, proved that the set (1),(2),(3′)(1),(2),(3') is already a GS basis for all matrices avoiding these patterns (for example when all mij≥3m_{ij}\ge 3, when all mij∈{2,∞}m_{ij}\in\{2,\infty\}, and for one triangular family), and recorded a revised conjecture attributed to L. A. Bokut: the full natural set (1),(2),(3)(1),(2),(3) is a pre-GS basis of every Coxeter group.

All subsequent work has been type-by-type. The affine Weyl group A~n\tilde{A}_n was completed by Yilmaz–Özel–Ustaoğlu (2014), who also classified all reduced words (words of minimal generator length representing a group element) via integer partitions; the non-crystallographic types H2H_2, H3H_3, H4H_4 by Lee–Lee (2019); the exceptional finite types G2G_2, F4F_4, E6E_6, E7E_7, E8E_8 by Pang–Wang (2020), which completed the irreducible finite types; the affine type C~n\tilde{C}_n by Ustaoğlu–Yilmaz (2022) and B~n\tilde{B}_n, D~n\tilde{D}_n by Ustaoğlu (2024). No uniform theorem covering an arbitrary Coxeter matrix is known, and the affine exceptional types appear to have no computed GS bases in the indexed literature.

Problem Statement

Formulate and establish — or disprove — a uniform structural pattern for Gröbner–Shirshov bases of Coxeter groups of arbitrary type. Concretely, for a general Coxeter matrix MM: (i) settle the revised conjecture of L. A. Bokut (as recorded by Chen–Liu, 2009) that the natural relation set (1),(2),(3)(1),(2),(3) — the involutive relations (1)(1), the alternating relations (2)(2) for all finite mijm_{ij} (the commutations for mij=2m_{ij}=2 together with the braid relations for mij≥3m_{ij}\ge 3), and the enlarged family (3)(3) of relations between products of alternating words — is a pre-Gröbner–Shirshov basis of the Coxeter group W(M)W(M); and (ii) determine which additional relation patterns beyond the natural set are forced in general (in particular, which of the inclusion-composition patterns C1–C4 of Chen–Liu generate genuinely new braid-type relations), and give, if one exists, a uniform construction of a Gröbner–Shirshov basis of W(M)W(M) — possibly infinite, but with a structural description uniform in the matrix — from which normal forms follow for every Coxeter group. Any uniform pattern must specialize to the already-computed types (AnA_n, BnB_n, DnD_n, G2G_2, F4F_4, E6E_6–E8E_8, H2H_2–H4H_4, A~n\tilde{A}_n, B~n\tilde{B}_n, C~n\tilde{C}_n, D~n\tilde{D}_n).

References

  1. L. A. Bokut and L.-S. Shiao, “Gröbner–Shirshov bases for Coxeter groups”, Communications in Algebra 29 (2001) 4305–4319. DOI: 10.1081/AGB-100106002. https://doi.org/10.1081/AGB-100106002
  2. Yuqun Chen and Cihua Liu, “Gröbner-Shirshov bases for Coxeter groups I”, preprint (2009). arXiv:0910.0096. https://arxiv.org/abs/0910.0096
  3. Erol Yilmaz, Cenap Özel and Uğur Ustaoğlu, “Gröbner–Shirshov basis and reduced words for affine Weyl group A~n\tilde{A}_n”, Journal of Algebra and Its Applications 13 (2014) 1450005. DOI: 10.1142/S0219498814500054. https://doi.org/10.1142/S0219498814500054
  4. Jeong-Yup Lee and Dong-il Lee, “Gröbner–Shirshov bases for non-crystallographic Coxeter groups”, Acta Crystallographica Section A: Foundations and Advances 75 (2019) 584–592. DOI: 10.1107/S2053273319002092. https://doi.org/10.1107/S2053273319002092
  5. Xiaowei Pang and Jun Wang, “Gröbner-Shirshov bases for the Coxeter groups of the types G2G_2, F4F_4, E6E_6, E7E_7 and E8E_8”, preprint (2020; v2 revised 2026). arXiv:2002.07369. https://arxiv.org/abs/2002.07369
  6. Uğur Ustaoğlu and Erol Yilmaz, “Gröbner-Shirshov basis and normal forms for the infinite Coxeter group of type C~n\tilde{C}_n”, Advanced Studies: Euro-Tbilisi Mathematical Journal 15(2) (2022) 89–99. DOI: 10.32513/asetmj/19322008218. https://doi.org/10.32513/asetmj/19322008218
  7. Uğur Ustaoğlu, “Gröbner-Shirshov Bases and Normal Forms for The Infinite Coxeter Groups of Types B~n\tilde{B}_{n} and D~n\tilde{D}_n”, Journal of Universal Mathematics 7 (2024) 86–101. DOI: 10.33773/jum.1562793. https://doi.org/10.33773/jum.1562793
  8. Eylem Güzel Karpuz, Firat Ateş and A. Sinan Çevik, “Gröbner-Shirshov bases of some Weyl groups”, Rocky Mountain Journal of Mathematics 45(4) (2015) 1165–1175. DOI: 10.1216/rmj-2015-45-4-1165. https://doi.org/10.1216/rmj-2015-45-4-1165
  9. Leonid Bokut and Andrei 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
  10. Ben Elias, “A diamond lemma for Hecke-type algebras”, Transactions of the American Mathematical Society 375 (2021) 1883–1915. DOI: 10.1090/tran/8554. https://doi.org/10.1090/tran/8554