Deciding finiteness of matrix groups in Las Vegas polynomial time
László Babai · Symposium on Discrete Algorithms · 1992
Let G be a group of matrices with integer entries, given by a list of generators. It is known that membership in such a group is undecidable, even for 4 x 4 integral matrices [Mi]. In this paper we show that one can decide whether or not G is finite, in Las Vegas polynomial time. The key estimate derived makes the entire “black box group” theory ([BSz], [BCFLS], [Ba2], [BKL]) applicable to the finite groups of integral matrices. In particular it follows that in this case, structural properties such as solvability and nilpotence are decidable in Monte Carlo polynomial time; and membership, order, isomorphism, and a host of other problems are in the relatively low complexity class AM ? coAM [Ba1]. We give two algorithms. The simpler one (Monte Carlo but not Las Vegas) employs a refinement of the random walk technique over groups, developed in [Ba3] (applied here to infinite groups). The termination rule rests on a new estimate on the bit-size of the elements of finite groups G, obtained via polynomial time symbolic manipulation of representations over algebraic number fields using results of [BR]. This symbolic manipulation technique is the basis of the Las Vegas algorithm. (A Las Vegas algorithm is a rnadomized algorithm which never errs; but with small probability, it may report failure.)