Solving random equations in Garside groups using length functions

Original · EN

We give a systematic exposition of memory-length algorithms for solving equations in noncommutative groups. This exposition clarifies some points untouched in earlier expositions. We then focus on the main ingredient in these attacks: Length functions. After a self-contained introduction to Garside groups, we describe length functions induced by the greedy normal form and by the rational normal form in these groups, and compare their worst-case performances. Our main concern is Artin's braid groups, with their two known Garside presentations, due to Artin and due to Birman-Ko-Lee (BKL). We show that in B₃ equipped with the BKL presentation, the (efficiently computable) rational normal form of each element is a geodesic, i.e., is a representative of minimal length for that element. (For Artin's presentation of B₃, Berger supplied in 1994 a method to obtain geodesic representatives in B₃.) For an arbitrary number of strands, finding the geodesic length of an element is NP-hard, by a 1991 result of by Paterson and Razborov. We show that a good estimation of the geodesic length of a braid in Artin's presentation is measuring the length of its rational form in the BKL presentation. This is proved theoretically for the worst case, and experimental evidence is provided for the generic case.