Solving random equations in Garside groups using length functions
<|reference_start|>Solving random equations in Garside groups using length functions: 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_3$ 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_3$, Berger supplied in 1994 a method to obtain geodesic representatives in $B_3$.)   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 \emph{BKL} presentation. This is proved theoretically for the worst case, and experimental evidence is provided for the generic case.<|reference_end|>
@article{hock2006solving,
    title={Solving random equations in Garside groups using length functions},
    author={Martin Hock and Boaz Tsaban},
    journal={arXiv preprint arXiv:math/0611918},
    year={2006},
    archivePrefix={arXiv},
    eprint={math/0611918},
    primaryClass={math.GR cs.CR math.AG}
}