Computation of orders and cycle lengths of automorphisms of finite solvable groups (Q2048160): Difference between revisions

The theory of polycyclic groups is a powerful tool for designing efficient algorithms for many computational problems on finite solvable groups. 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, algorithms for computing the order of \(\alpha \) are discussed as well as the cycle length of a given element of \(G\) under \(\alpha \). The aim of this paper is two-fold: 1. Natural algorithms for the basic tasks of computing the orders of elements of the group \(\Aut(G)\) are discussed (which are assumed to be given through their images of the presentation generators of \(G\), as is the case by default in The GAP Group (2019)) and the cycle length of a given element of \(G\) is determined under a given automorphism of \(G\). We will prove the correctness of these algorithms and provide a theoretical complexity analysis for them. Theorem 1.2.1. Algorithms 1 and 2, viewed as deterministic algorithms, are correct. Theorem 1.2.2. Algorithms 1 and 2, viewed as Las Vegas algorithms, both have expected running time subexponential in the input length. 2. A detailed complexity analysis for several classical algorithms on finite pc groups is given. Theorem 1.3.1. Let \(G\) be a finite solvable group, given via a refined consistent polycyclic presentation \(P=\left\langle X\mid R\right\rangle \). One can construct in \(O(l(P)^{8}Coll(P)+l(P)^{10})\) bit operations -- a pc group isomorphism from \(P\) to another refined consistent polycyclic presentation \(\left\langle Y\mid S\right\rangle \) of \(G\) such that \(Y\) refines the LG-series of \(G\), and -- the final weight function for \(Y\) with respect to the LG-series of \(G\). Along the way, a detailed complexity analyses of several classical algorithms on finite polycyclic groups is carried out.