Computation of orders and cycle lengths of automorphisms of finite solvable groups

Abstract

Let $G$ be a finite solvable group, given through a refined consistent polycyclic presentation, and $\alpha$ an automorphism of $G$, given through its images of the generators of $G$. In this paper, we discuss algorithms for computing the order of $\alpha$ as well as the cycle length of a given element of $G$ under $\alpha$. We give correctness proofs and discuss the theoretical complexity of these algorithms. Along the way, we carry out detailed complexity analyses of several classical algorithms on finite polycyclic groups.

27 pages, improved complexity bound in Theorem 1.2.3, some typos corrected, and various other small revisions to improve readability