Mathematics – Group Theory
Scientific paper
2006-11-29
Mathematics
Group Theory
Scientific paper
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.
Höck Martin
Tsaban Boaz
No associations
LandOfFree
Solving random equations in Garside groups using length functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving random equations in Garside groups using length functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving random equations in Garside groups using length functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-373286