Deciding finiteness of matrix groups in Las Vegas polynomial time

ABSTRACT

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 r eport failure.)

REFERENCES

• Alo: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• Ba1: L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
• Ba2: László Babai, Bounded round interactive proofs in finite groups, SIAM Journal on Discrete Mathematics, v.5 n.1, p.88-111, Feb. 1992 [doi>10.1137/0405008]
• Ba3: László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
• Ba4: L. Bahai: Computational complexity in finite groups, Proc. International Congress of Mathematicians, Kyoto 1990, Springer, to appear
• BCFS: László Babai , Gene Cooperman , Larry Finkelstein , Ákos Seress, Nearly linear time algorithms for permutation groups with a small base, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.200-209, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120724]
• BCFLS: László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.90-100, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103435]
• BKL: L. BabaJ, S. Kannan, E. M. Luks: Boundedround interactive proofs for nonisomorphism of finite groups, in preparation
• BR: L. BabaJ, L. R6nyai: Computing irreducible representations of finite groups, Mathematics of Computation 55 (1990), pp. 705-722. (Preliminary version: 30th FOCS, 1989, pp. 93- 98.)
• BSz: L. Babai, E. Szemer~di: On the complexity of matrix group problems I, in: Proc. 25th IEEE FOCS, Palm Beach FL, 1984, pp. 229- 240.
• CR: C. W. Curtis, I. Reiner: Representation Theory of Finite Groups and Associative Algebras, Wiley, 1966.
• Dia: P. Diaconis: Group Roprosontations in Probability and Statistics, Inst. Math. Stat. Hayward CA 1988.
• Dix: J. Dixon: Computing irreducible representations of groups, Math. Comp. 24 (1970), 446- 450.
• Eb: Wayne Michael Eberly , J. Von Gathen, Computations for algebras and group representations, 1989
• FR: K Friedl , L Rónyai, Polynomial time solutions of some problems of computational algebra, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.153-162, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22162]
• GL: G. H. Golub, C. F. Van Loan: Matrix Computations, Johns Hopkins Univ. Press, Baltimore 1989.
• Ha: P. Halmos: Finite-dimensional Vector Spaces, Van Nostrand, Princeton 1958.
• KL: W. M. Kantor , E. M. Luks, Computing in quotient groups, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.524-534, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100290]
• Kn: D. E. Knuth: Efficient representation of perm groups, Combinatorica 11 (1991), 57-68.
• LS: R. C. Lyndon, P. E. Schupp: Combinatorial Group Theory, Springer, New York 1977.
• Mi: K. A. Mihailova: The occurrence problem for direct products of groups (in Russian), Dokl. Akad. Nauk SSSR 119 (1958), 1103-1105, and Mat. Sb. (N. S.) 70 (112) (1966), 241-251.
• Ro: L. Ronyai, Simple algebras are difficult, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.398-408, January 1987, New York, New York, United States [doi>10.1145/28395.28438]
• Sa: I. N. Sanov: A property of a representation of a free group, Dokl. Akad. Nauk SSSR 57 (1947), 057-659.
• Si: C. C. Sims, Some group theoretic algorithms, in: Lecture Notes in Math. 697 (1978), pp. 108-124.
• Sp: A. Speiser: Die Theorie der Grappen yon endlicher Ordnung, Dritte Aufiage, Dover, N.Y. 1937.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  C. Computer Systems Organization

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory, Verification