Improved algorithms for the Tits alternative (Q2759619)

Let \(F\) be an algebraic number field, and \(G\) a subgroup of \(\text{GL}(n,F)\). The so-called Tits alternative says that either \(G\) has a solvable normal subgroup of finite index, or \(G\) contains a non-Abelian free subgroup. This dichotomy is intimately related to computability. In an earlier paper, the author [J. Comput. Syst. Sci. 58, No. 2, 260-279 (1999; Zbl 0922.68064)] gave a polynomial time algorithm to determine, given a set of generators of \(G\), whether or not \(G\) is solvable-by-finite. This algorithm is unfortunately impractical since it involves solving systems of linear equations with \(n^4\) unknowns. In this paper, the author provides a new algorithm which performs all computations in the original dimension (or smaller).NEWLINENEWLINEFor the entire collection see [Zbl 0959.00030].