An Artin group is given by generators tied by braid relations encoded in a Coxeter diagram. A 2024 paper by Blasco-García, Cumplido, Holt, Morris-Wright and Rees proves that when the diagram contains no A3A_3 or B3B_3 subdiagram (no generators x,y,zx,y,z with xyx=yxyxyx=yxy, xz=zxxz=zx, (y,z)n=(z,y)n(y,z)^n=(z,y)^n for n=3n=3 or 44), a finite system of length-preserving rewrite rules together with free reduction reduces any word to a geodesic in quadratic time. The paper explicitly leaves open whether such rewrite solutions exist for groups whose diagrams do contain A3A_3 or B3B_3 subdiagrams — its theorem does not cover them, and its own rule family provably fails for some B3B_3 configurations (its Example 4.6) — and, more generally, whether every Artin group admits a word-problem solution by length-preserving rewrites plus free reduction.

Background

An Artin (or Artin–Tits) group is the group defined by a finite set SS of generators with one braid relation for each pair of generators whose label in an associated Coxeter diagram is finite: for x,y∈Sx,y\in S with 2≤mxy<∞2\le m_{xy}<\infty, the two alternating words of length mxym_{xy} are equal, (x,y)mxy=(y,x)mxy(x,y)^{m_{xy}}=(y,x)^{m_{xy}}, where (x,y)n(x,y)^n denotes the alternating string ⋯xyxy\cdots xyxy of length nn ending in yy, and the case mxy=2m_{xy}=2 is the commutation xy=yxxy=yx; a pair with mxy=∞m_{xy}=\infty is subject to no relation. Edges are drawn only for labels mxy≥3m_{xy}\ge 3, so two nodes not joined by an edge either commute (mxy=2m_{xy}=2) or satisfy no relation (mxy=∞m_{xy}=\infty). Artin groups interpolate between free groups (the case where every label is ∞\infty), braid groups, and right-angled Artin groups (the case where every label is 22 or ∞\infty, so each pair of generators either commutes or satisfies no relation), and the general word problem for them — deciding whether two words over SS represent the same group element — is a major open problem of geometric group theory, settled only for subclasses: spherical (finite) type, where the associated Coxeter group is finite and Garside theory (a normal-form theory built from the divisor lattice of a distinguished Garside element) applies; large type (all labels ≥3\ge 3) and sufficiently large type (whenever a triple of generators contains a commuting pair mxy=2m_{xy}=2, either the other two pairs both commute or at least one of them has label ∞\infty); FC type (every subdiagram whose nodes are pairwise joined by labels ≥3\ge 3 spans a spherical subgroup); and 3-free diagrams (no edge labelled 3), among others.

A word over S∪S−1S\cup S^{-1} is geodesic if no shorter word represents the same element; free reduction deletes adjacent inverse pairs xx−1xx^{-1}. Since braid relations equate words of equal length, ordinary length-reducing rewriting cannot solve the word problem directly, and the relevant tool is instead a finite system of length-preserving rewrite rules: local moves replacing a designated subword (a critical word) by another word of the same length, called a τ\tau-move. For Artin groups of large type, Holt and Rees (2012, 2013) built such systems from τ\tau-moves on 2-generator critical words (alternating words that are maximal alternating words within their two-generator subgroup), showing these groups are shortlex automatic (i.e., admit an automaton-based normal form sorting letters lexicographically, which yields a solvable word problem) with a regular geodesic language (the set of geodesic words is accepted by a finite automaton); Blasco-García, Cumplido and Morris-Wright (arXiv:2204.03523) extended the method to 3-free diagrams using pseudo 2-generator (P2G) critical words — words built on two alternating "pseudo-generators" a,ba,b such that every internal letter commutes with both aa and bb, and deleting those internal letters leaves a 2-generator critical word; Holt and Rees (arXiv:2310.14632) handled the rank-three type (2,3,n)(2,3,n) groups for n≥5n\ge 5. The paper at issue here (arXiv:2412.12195) introduces pseudo 3-generator (P3G) critical words — concatenations of two P2G words of types a,b{a,b} and b,c{b,c} sharing the letter bb — and proves, for diagrams with no A3A_3 or B3B_3 subdiagram — that is, containing no generators x,y,zx,y,z with xyx=yxyxyx=yxy, xz=zxxz=zx, (y,z)n=(z,y)n(y,z)^n=(z,y)^n for n=3n=3 or 44 — that a finite system of length-preserving rules plus free reduction reduces any word to a geodesic representative in quadratic time, and that any two geodesics for the same element are connected by two-generator rules. An A3A_3 subdiagram is a triangle labelled (2,3,3)(2,3,3) and a B3B_3 subdiagram a triangle labelled (2,3,4)(2,3,4), where a side labelled 2 means the corresponding pair of generators is not joined by an edge (they commute); these are exactly the small labelled triangles still excluded after all prior work. The Introduction of arXiv:2412.12195 frames the paper as addressing the general open question of whether all Artin groups have soluble word problem and, if so, whether it can always be solved by length-preserving rewrites together with free reduction; its Example 4.6 (in a B3B_3, i.e., n=4n=4, configuration) exhibits two words representing the same element, one of which admits a rightward reducing sequence (a chain of τ\tau-moves applied left to right across the word, ending in a free reduction) while the other admits none — so the specific rule family of the paper cannot extend to B3B_3-containing diagrams. Note that the groups A3A_3 and B3B_3 themselves are of spherical (finite) type, so their word problems are solvable by other methods (Garside normal forms, shortlex automaticity); what is at stake for A3/B3A_3/B_3-containing diagrams is the existence of this particular style of solution — a finite length-preserving rewrite system with geodesic output and quadratic running time — while for arbitrary Artin diagrams the question subsumes the still-open general word problem.

Problem Statement

The general open question posed in the Introduction of arXiv:2412.12195: does every Artin group admit a soluble (i.e., algorithmically decidable) word problem, and if so, can the word problem always be solved by a finite system of length-preserving rewrite rules over the standard generators which, together with free reduction, reduces any input word to a geodesic representative of the same group element? The concrete first obstruction left open by that paper is the case of diagrams that do contain an A3A_3 or B3B_3 subdiagram, i.e., generators x,y,zx,y,z with xyx=yxyxyx=yxy, xz=zxxz=zx, and (y,z)n=(z,y)n(y,z)^n=(z,y)^n for n=3n=3 or 44: the paper's Example 4.6 proves that its specific family of length-preserving moves (the τ\tau-moves on 2-generator, pseudo-2-generator, and pseudo-3-generator critical words) cannot yield such a solution for at least some B3B_3 configurations, and no replacement or additional family of length-preserving rules handling the A3A_3 or B3B_3 cases is currently known. The general question for all Artin groups is the objective, with the A3/B3A_3/B_3 case as the concrete first sub-target: that paper's theorem already settles every diagram without an A3A_3 or B3B_3 subdiagram, so a complete length-preserving-rewrite solution for the A3/B3A_3/B_3-containing diagrams would complete the general question.

References

  1. Rubén Blasco-García, María Cumplido, Derek F. Holt, Rose Morris-Wright, Sarah Rees, "Rewriting in Artin groups without A_3 or B_3 subdiagrams", arXiv:2412.12195 (2024), DOI 10.48550/arXiv.2412.12195, https://arxiv.org/abs/2412.12195
  2. Rubén Blasco-García, María Cumplido, Rose Morris-Wright, "The Word Problem is Solvable for 3-free Artin groups in Quadratic Time", arXiv:2204.03523 (2022), DOI 10.48550/arXiv.2204.03523, https://arxiv.org/abs/2204.03523
  3. D. F. Holt, S. Rees, "Artin groups of large type are shortlex automatic with regular geodesics", Proceedings of the London Mathematical Society 104(3):486–512 (2012), DOI 10.1112/plms/pdr035, https://doi.org/10.1112/plms/pdr035
  4. D. F. Holt, S. Rees, "Shortlex automaticity and geodesic regularity in Artin groups", Groups, Complexity, Cryptology 5(1):1–23 (2013), DOI 10.1515/gcc-2013-0001, https://doi.org/10.1515/gcc-2013-0001
  5. Derek F. Holt, Sarah Rees, "Artin groups of type (2,3,n)", arXiv:2310.14632 (2023), DOI 10.48550/arXiv.2310.14632, https://arxiv.org/abs/2310.14632
  6. Arye Juhász, "On the Isoperimetric functions of a class of Artin Groups", arXiv:2507.16770 (2025), DOI 10.48550/arXiv.2507.16770, https://arxiv.org/abs/2507.16770
  7. José Gálvez Mateos, Federica Gavazzi, Luis Paris, "Parabolic subgroups and word problem in virtual Artin groups", arXiv:2602.23819 (2026), DOI 10.48550/arXiv.2602.23819, https://arxiv.org/abs/2602.23819
  8. Robert D. Gray, Carl-Fredrik Nyberg-Brodda, "Membership problems in braid groups and Artin groups", Journal of the London Mathematical Society 112(4):e70326 (2025), DOI 10.1112/jlms.70326, arXiv:2409.11335, https://arxiv.org/abs/2409.11335
  9. Elisabeth Fink, "Learning the Word Problem: Geodesic Lengths and Cryptographic Applications", arXiv:2607.26241 (2026), DOI 10.48550/arXiv.2607.26241, https://arxiv.org/abs/2607.26241