Mathematics – Group Theory
Scientific paper
2009-07-29
Mathematics
Group Theory
Scientific paper
We introduce the peak normal form of elements of the Baumslag-Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element $u^{-1}v$ yields the shortest path between $u$ and $v$ in the Cayley graph. For horocyclic elements the peak normal form and the length-lexicographical normal form coincide. The main result of this paper is that we can compute the peak normal form in polynomial time if $p$ divides $q$. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in Elder et al. 2009, arXiv.org:0907.3258. For arbitrary $p$ and $q$ it is possible to compute the peak normal form (length-lexicolgraphical normal form resp.) also for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the $t$-sequence starts with $t^{-1}$ and ends with $t$. To solve the general case in polynomial time for arbitrary $p$ and $q$ remains a challenging open problem.
Diekert Volker
Laun Jürn
No associations
LandOfFree
On Computing Geodesics in Baumslag-Solitar Groups 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 On Computing Geodesics in Baumslag-Solitar Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Computing Geodesics in Baumslag-Solitar Groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-521620