2009/07/29 by Volker Diekert, Diekert, Volker, Jürn Laun +1
Computer Science · Mathematics · #20-04 #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis #math.GR #msc:20-04
paper · pdf · doi:10.48550/arxiv.0907.5114
openalex publication_date 2009/07/29 · arxiv created 2009/08/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-1v 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.