The Shirshov completion algorithm — the noncommutative, string-rewriting counterpart of Knuth–Bendix completion — is not guaranteed to terminate or to return a finite Gröbner–Shirshov basis. Pang and Wang (arXiv:2002.07369), who completed the Gröbner–Shirshov bases of the last missing finite Coxeter types G2,F4,E6,E7,E8G_2,F_4,E_6,E_7,E_8 by rearranging and marking generators on the Coxeter–Dynkin diagram, state this limitation explicitly but pose no question about it. The unrestricted form of the issue is classically settled in the negative: Squier-type monoids admit no finite convergent rewriting system under any order, and uniform termination of rewriting is undecidable, so no criterion for arbitrary presentations can exist. Within the Coxeter family, however, the question is open: every irreducible finite type has a finite Gröbner–Shirshov basis under some exhibited ordering, the Bokut–Shiao uniform hypothesis was refuted by explicit counterexamples, the affine types are settled only case-by-case (A~n,C~n,B~n,D~n\widetilde{A}_n,\widetilde{C}_n,\widetilde{B}_n,\widetilde{D}_n), and no published work characterizes which monomial orders or diagram markings make completion terminate. The problem asks for a termination criterion for Coxeter-family ordered presentations: a proven characterization of exactly which monomial orders and diagram markings make Shirshov completion terminate with a finite Gröbner–Shirshov basis.

Background

A Coxeter group is a group with a presentation W=⟨s1,…,sn∣(sisj)mij=1⟩W=\langle s_1,\dots,s_n\mid (s_is_j)^{m_{ij}}=1\rangle on involutive generators, where the mijm_{ij} are recorded as edge labels on the Coxeter–Dynkin diagram, the graph whose vertices are the generators and whose edges join the pairs with mij≥3m_{ij}\ge 3. The finite Coxeter groups were classified by Coxeter in 1935; the irreducible finite types are An,Bn,Dn,G2,F4,E6,E7,E8A_n,B_n,D_n,G_2,F_4,E_6,E_7,E_8 (the crystallographic types, whose labels mij∈{2,3,4,6}m_{ij}\in\{2,3,4,6\} are compatible with a root system and a semisimple Lie algebra) and H3,H4,I2(m)H_3,H_4,I_2(m) (non-crystallographic). A Gröbner–Shirshov basis is the noncommutative analogue of a Gröbner basis: given a set SS of monic polynomials in the free associative algebra K⟨X⟩K\langle X\rangle (for a group presentation, relations ui=viu_i=v_i encoded as ui−viu_i-v_i), SS is a Gröbner–Shirshov basis if every composition — an overlap or inclusion between the leading words of two elements, generalizing an SS-polynomial — reduces to zero modulo SS; by the Composition–Diamond Lemma (the noncommutative counterpart of Buchberger's criterion, which makes the irreducible words a linear basis of the quotient algebra) this yields irreducible-word normal forms and a solution of the word problem, the algorithmic problem of deciding whether two words represent the same group element. The Shirshov algorithm (the string-rewriting counterpart of Knuth–Bendix completion, which adjoins rewrite rules until the system becomes confluent) iteratively adjoins non-reducible compositions until a Gröbner–Shirshov basis is reached, always under a fixed monomial (well) order on words such as the deg-lex order, which first compares word length and then lexicographically. Bokut and Shiao (2001) computed Gröbner–Shirshov bases for the types An,Bn,DnA_n,B_n,D_n and formulated a general hypothesis covering all Coxeter groups; Denis Lee (2008) handled E6,E7E_6,E_7; Chen and Liu (2009) refuted the Bokut–Shiao hypothesis with an explicit counterexample, showing that the outcome of completion genuinely depends on the chosen presentation and ordering; Lee and Lee (2018) treated the non-crystallographic HH types. Pang and Wang (arXiv:2002.07369, v1 2020, v2 2026) then simplified the E6,E7E_6,E_7 bases and gave the first Gröbner–Shirshov basis for E8E_8 by rearranging generators and marking them on the Coxeter–Dynkin diagram — a marking is an assignment of the ordered labels x1,…,xnx_1,\dots,x_n to the diagram's vertices, which fixes the ordered generating set handed to completion — while remarking that completion 'is not always finite' and that the output GB(A)GB(A) 'is not always a finite set'. In parallel, the program extends to affine Coxeter groups, the infinite Euclidean reflection groups denoted X~n\widetilde{X}_n obtained by enlarging a finite Dynkin diagram by one node: the affine Weyl group A~n\widetilde{A}_n (Özel–Kılıçman–Yılmaz 2010; Yılmaz–Özel–Ustaoğlu 2012), C~n\widetilde{C}_n (Ustaoğlu–Yılmaz 2022), and B~n,D~n\widetilde{B}_n,\widetilde{D}_n (Ustaoğlu 2024); Pang–Wang's Remark 3.5 observes that their EnE_n presentation at n=9n=9 describes the affine group E~8\widetilde{E}_8, whose Gröbner–Shirshov basis could be computed the same way but is not carried out. Independently, general rewriting theory sets hard limits: Squier (1987) exhibited finitely presented monoids with solvable word problem that admit no finite convergent rewriting system (no finite system of rewrite rules that is both terminating and confluent, i.e. with all critical pairs resolvable) under any order, and uniform termination of rewriting is undecidable (Dershowitz 1987; Book–Otto 1993).

Problem Statement

For a Coxeter group given by its standard Coxeter presentation, under which choices of monomial order on the generators and which markings — orderings of the generators on the Coxeter–Dynkin diagram, each of which fixes a different ordered presentation — does Shirshov completion (the iterative adjunction of non-reducible compositions of the relations, under the fixed order) terminate with a finite Gröbner–Shirshov basis; and is there a criterion identifying exactly those orderings and markings? Two scope facts bound any answer. First, the unrestricted form — termination or finiteness for arbitrary finitely presented groups or semigroups — is settled in the negative: Squier-type monoids admit no finite convergent presentation under any order, and uniform termination of rewriting is undecidable, so no general criterion can exist; only Coxeter-family (or comparably structured) presentations are in scope. Second, within the Coxeter family every irreducible finite type has an explicitly computed finite Gröbner–Shirshov basis under exhibited orderings, but Bokut–Shiao's uniform hypothesis was refuted, and the affine types are settled only case-by-case (A~n,C~n,B~n,D~n\widetilde{A}_n,\widetilde{C}_n,\widetilde{B}_n,\widetilde{D}_n), with the affine E~n\widetilde{E}_n types outstanding; Pang–Wang's Remark 3.5 flags only the n=9n=9 case, E~8\widetilde{E}_8, as computable by the same presentation. The target is a proven characterization of exactly which ordered presentations of Coxeter groups, finite or affine, admit terminating completion with a finite Gröbner–Shirshov basis. The task is resolved equally by a proof that no such criterion exists, that is, a proof establishing that the termination question admits no effective criterion even within the Coxeter family (for example, by showing that deciding terminating completion with a finite Gröbner–Shirshov basis is undecidable there). A proof that some Coxeter presentation and monomial ordering forces non-termination, or the Gröbner–Shirshov basis of the affine type E~8\widetilde{E}_8 suggested by Pang–Wang's Remark 3.5, would constitute partial progress toward this characterization but would not by itself answer the criterion question. The further component raised by the source limitation — which of the terminating orderings yield minimal or efficiently computable bases — has no agreed formal measure in this literature and is not part of this task's required deliverable.

References

  1. Xiaowei Pang and Jun Wang, "Gröbner-Shirshov bases for the Coxeter groups of the types G2,F4,E6,E7G_2,F_4,E_6,E_7 and E8E_8", arXiv:2002.07369 (v1 2020, v2 2026), https://arxiv.org/abs/2002.07369
  2. 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
  3. Yuqun Chen and Cihua Liu, "Gröbner-Shirshov bases for Coxeter groups I", arXiv:0910.0096 (2009), https://arxiv.org/abs/0910.0096
  4. Denis Lee, "Gröbner–Shirshov bases and normal forms for the Coxeter groups E6E_6 and E7E_7", in Advances in Algebra and Combinatorics, World Scientific (2008), pp. 243–255, DOI 10.1142/9789812790019_0016, https://doi.org/10.1142/9789812790019_0016
  5. Jeong-Yup Lee and Dong-il Lee, "Gröbner-Shirshov bases for non-crystallographic Coxeter groups", arXiv:1809.08419 (2018), https://arxiv.org/abs/1809.08419
  6. Cenap Özel, Adem Kılıçman and Erol Yılmaz, "Note on the Calculation of Groebner-Shirshov Bases for Affine Weyl Groups", arXiv:1002.4678 (2010), https://arxiv.org/abs/1002.4678
  7. Erol Yılmaz, Cenap Özel and Uğur Ustaoğlu, "Grobner-Shirshov Basis for affine Weyl Group An~\widetilde{A_n}", arXiv:1203.6531 (2012), https://arxiv.org/abs/1203.6531
  8. Uğur Ustaoğlu and Erol Yılmaz, "Gröbner-Shirshov basis and normal forms for the infinite Coxeter group of type C~n\widetilde{C}_n", Advanced Studies: Euro-Tbilisi Mathematical Journal 15 (2022), DOI 10.32513/asetmj/19322008218, https://doi.org/10.32513/asetmj/19322008218
  9. Uğur Ustaoğlu, "Gröbner-Shirshov Bases and Normal Forms for The Infinite Coxeter Groups of Types B~n\widetilde{B}_{n} and D~n\widetilde{D}_n", Journal of Universal Mathematics (2024), DOI 10.33773/jum.1562793, https://doi.org/10.33773/jum.1562793
  10. Craig C. Squier, "Word problems and a homological finiteness condition for monoids", Journal of Pure and Applied Algebra 49 (1987) 201–217, DOI 10.1016/0022-4049(87)90129-0, https://doi.org/10.1016/0022-4049(87)90129-0
  11. Nachum Dershowitz, "Termination of rewriting", Journal of Symbolic Computation 3 (1987) 69–115, DOI 10.1016/S0747-7171(87)80022-6, https://doi.org/10.1016/S0747-7171(87)80022-6
  12. Ronald V. Book and Friedrich Otto, "String-Rewriting Systems", Springer, New York (1993), DOI 10.1007/978-1-4613-9771-7, https://doi.org/10.1007/978-1-4613-9771-7
  13. Uğur Ustaoğlu and Erol Yılmaz, "Gröbner-Shirshov bases and normal forms of some Coxeter groups", JP Journal of Algebra, Number Theory and Applications 40 (2018) 701–723, DOI 10.17654/NT040050701, https://doi.org/10.17654/NT040050701