Artin groups emerged in the 1960s (thanks to mathematician Jacques Tits) as generalizations of braid groups and modifications of Coxeter reflection groups involving the removal of the involution relation inherent in reflections, thus creating groups that project onto Coxeter groups. For example, braid groups with n strands project onto the symmetric group of n elements. Therefore, Artin groups have a very simple presentation: they are groups generated by a finite set of generators S and relations written as sts · · · = tst . . . for s, t ∈ S, where both words in the equality have the same length. However, groups so simple to define do not admit many common techniques that allow obtaining global results for any Artin group, making them highly enigmatic groups. 

To this day, classic problems like the word problem still do not have a general solution. The work we are going to discuss focuses precisely on the word problem. The long-term project began in December 2020 and ended in the summer of 2023, providing a programmable and quadratic solution to the word problem in Artin groups without relations of length 3 (3-free Artin groups). This work greatly benefited from my participation in the Braids Semester Program, which took place at ICERM in the spring of 2022 and allowed me to work in person with Dr. Rose Morris-Wright (Middlebury College) in verifying and writing the main proofs of our paper.

Our techniques, based on rewriting systems, find their origin in theoretical computer science. If the word problem consists of determining whether a word in the generators of a group represents the trivial element, the perspective of rewriting systems is simple to state: can we find a set of rules to apply the group relations that provide us with such an algorithm? This approach has two advantages. On one hand, it makes the proofs largely self-contained, not dependent on major results and black boxes. On the other hand, as they do not contain geometric content, it makes the algorithms easily translatable to programming code.

In [MM06], the authors create a method to detect geodesic words in dihedral Artin groups (groups with only two generators), comparing the length of the group relation with the lengths of subwords of the form stst . . . or s⁻¹t⁻¹s⁻¹t⁻¹ . . . . With this idea, Derek Holt (University of Warwick) and Sarah Rees (Newcastle University) ([HR12], [HR13]) create the concept of a critical word in two generators, which can be seen in Figure 1. Thus, their idea is to create a new set of relations and rules that allow, using only transformations of critical words and elimination of subwords of the type a⁻¹a (reduction), to obtain a geodesic representative from any word. They achieve this result for dihedral groups, large groups (relations greater than 2), and sufficiently large groups (a generalization with rigidity conditions on the commutations that can be allowed). The relations they use are the so-called Ƭ-moves that can be found in Figure 2.

In our work [BCM22], we generalize the notion of a critical word to introduce commutations of all kinds, in exchange for relinquishing length 3 relations. We now consider words (pseudo 2-generated) that don’t necessarily have to be generated by two generators; it is enough that, using commutations, one can ”push” letters left and right until obtaining a critical 2-generated word in the middle (Figure 3), then applying the Ƭ-movement to this critical word. What we demonstrate is that, in 3-free Artin groups, a non-geodesic word always has a sequence of Ƭ-movements that end in a reduction. We call this sequence a Rightward Reducing Sequence, and it consists of detecting a suitable pseudo 2-generated word, applying commutations until obtaining the critical word in the middle, applying the Ƭ-movement, passing some of the last letters of the obtained word to the right, and repeating the process until reaching some commutations (which may not exist) and a reduction. A visualization of the definition and an example can be found in the video [C24]. In this video, the uᵢ’s of the definition are the pseudo 2-generated critical words and, in the example, we have a word on generators a, b, c, d, where abab = baba, bcbcb = cbcbc, and the other pairs of generators commute.

Moreover, we prove that there is a canonical choice for Rightward Reducing Sequences. In this way, we can systematically reduce a word that represents the trivial element to the trivial word, solving the word problem. Moreover, we demonstrate that this process can be done recursively and that the complexity is quadratic in the length of the word. The proofs consist of case-by-case verifications of all the possibilities we can encounter when applying our rules to a word. The programmed algorithm in SAGEMath can be found in [C23].

References

[BCM22] Blasco-García, R., Cumplido, M., & Morris-Wright, R. 2022. The Word Problem is solvable for 3-free Artin groups in quadratic time. Preprint. arXiv:2204.03523.

[C23] Cumplido, M. 2023. GitHub Gist WordProblem3freeArtin.ipynb. https://gist.github.com/cumplido/7bac9f786e5300010723030e9d3c5c3d.

[C24] Cumplido, M. 2024. “Definition and example of Rightward Reduction System." YouTube, www.youtube.com/watch?v=5VMpcDtl11c.

[HR12] Holt, D. F., & Rees, S. 2012. Artin groups of large type are shortlex automatic with regular geodesics. Proceedings of the London Mathematical Society, 104(Mar), 486—-512.

[HR13] Holt, D. F., & Rees, S. 2013. Shortlex automaticity and geodesic regularity in Artin groups. Groups - Complexity - Cryptology, 5(1), 1–23.

[MM06] Mairesse, J., & Mathéus, F. 2006. Growth series for Artin groups of dihedral type. International Journal of Algebra and Computation, 16(6), 1087–1107.