Polynomial-time theory of matrix groups

ABSTRACT

We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even in the case of abelian groups it is not known how to answer these questions without solving hard number theoretic problems (factoring and discrete log); in fact, constructive membership testing in the case of 1 × 1 matrices is precisely the discrete log problem. So the reasonable question is whether these problems are solvable in randomized polynomial time using number theory oracles. Building on 25 years of work, including remarkable recent developments by several groups of authors, we are now able to determine the order of a matrix group over a finite field of odd characteristic, and to perform constructive membership testing in such groups, in randomized polynomial time, using oracles for factoring and discrete log. One of the new ingredients of this result is the following. A group is called semisimple if it has no abelian normal subgroups. For matrix groups over finite fields, we show that the order of the largest semisimple quotient can be determined in randomized polynomial time (no number theory oracles required and no restriction on parity). As a by-product, we obtain a natural problem that belongs to BPP and is not known to belong either to RP or to coRP. No such problem outside the area of matrix groups appears to be known. The problem is the decision version of the above: Given a list A of nonsingular d × d matrices over a finite field and an integer N, does the group generated by A have a semisimple quotient of order > N? We also make progress in the area of constructive recognition of simple groups, with the corollary that for a large class of matrix groups, our algorithms become Las Vegas.

REFERENCES

• 1: S. Aaronson and G. Kuperberg. Quantum versus classical proofs and advice. Theory of Computing, 3:129--157, 2007.
• 2: C. Altseimer and A. V. Borovik. Probabilistic recognition of orthogonal and symplectic groups. In Groups and Computation III, pages 1--20. deGruyter, 2001.
• 3: L. Babai. Monte Carlo algorithms in graph isomorphism testing. Universite de Montreal Tech. Rep., DMS 79--10:42 pages, 1979.
• 4: 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]
• 5: 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]
• 6: L. Babai and R. Beals. A polynomial-time theory of black-box groups I. In Groups St Andrews 1997 in Bath, I, pp. 30--64. London Math. Soc. Lect. Notes 260, 1999.
• 7: L. Babai, G. Cooperman, L. Finkelstein, E. M. Luks, and A. Seress. Fast Monte Carlo algorithms for permutation groups. J. Computer and System Sci., 50:296--308, 1995. (Prelim. 23rd STOC, 1991)
• 8: L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks, and P. P. Palfy. Short presentations for finite groups. J. Algebra, 194:79--112, 1997.
• 9: L. Babai, W. M. Kantor, P. P. Palfy, and A. Seress. Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory, 5:383--401, 2002.
• 10: L. Babai, P. P. Palfy, and J. Saxl. On the number of p-regular elements in simple groups. LMS J. Computation and Math., 2009, to appear.
• 11: L. Babai and A. Shalev. Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups. In Groups and Comp. III, pp. 39--62. deGruyter, 2001.
• 12: L. Babai , E. Szemeredi, On The Complexity Of Matrix Group Problems I, Proceedings of the 25th Annual Symposium onFoundations of Computer Science, 1984, p.229-240, October 24-26, 1984 [doi>10.1109/SFCS.1984.715919]
• 13: Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
• 14: R. Beals. Towards polynomial time algorithms for matrix groups. In Groups and Computation II, pp. 31--54. DIMACS, 1997.
• 15: R. Beals , L. Babai, Las Vegas algorithms for matrix groups, Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, p.427-436, November 03-05, 1993 [doi>10.1109/SFCS.1993.366844]
• 16: R. Beals, C. R. Leedham-Green, A. C. Niemeyer, C. E. Praeger, and A. Seress. A black-box group algorithm for recognizing finite symmetric and alternating groups. Trans. Amer. Math. Soc, 355:2097--2113, 2003.
• 17: J. Bray. An improved method for generating the centralizer of an involution. Arch. Math., 74:241--245, 2000.
• 18: P. A. Brooksbank. Fast constructive recognition of black-box unitary groups. LMS J. Comput. Math., 6:162--197, 2003.
• 19: P. A. Brooksbank. Fast constructive recognition of black-box symplectic groups. J. Algebra, 320:885--909, 2008.
• 20: P. A. Brooksbank and W. M. Kantor. On constructive recognition of a black box PSL(d, q). In Groups and Computation III, pp. 95--111. deGruyter, 2001.
• 21: P. A. Brooksbank and W. M. Kantor. Fast constructive recognition of black box orthogonal groups. J. Algebra, 300:256--288, 2006.
• 22: F. Celler, C. R. Leedham-Green, S. Murray, A. C. Niemeyer, and E. A. O'Brien. Generating random elements of a finite group. Comm. Alg., 23:4931--4948, 1995.
• 23: M. Conder, C. R. Leedham-Green, and E. A. O'Brien. Constructive recognition of PSL(2, q). Trans. Amer. Math. Soc., 358:1203--1221, 2006.
• 24: J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson: ATLAS of Finite Groups. Clarendon Press, Oxford, 1985.
• 25: J. D. Dixon. Generating random elements in finite groups. Electronic J. Combinatorics, 15/1:R94, 2008.
• 26: W. Feit and J. Tits. Projective representations of minimum degree of group extensions. Canad. J. Math., 30:1092--1102, 1978.
• 27: M. L. Furst, J. Hopcroft, and E. M. Luks. Polynomial-time algorithms for permutation groups. In Proc. 21st FOCS, pp. 36--41, IEEE C.S., 1980.
• 28: Alexander Gamburd , Igor Pak, Expansion Of Product Replacement Graphs, Combinatorica, v.26 n.4, p.411-429, August 2006 [doi>10.1007/s00493-006-0023-0]
• 29: P. E. Holmes, S. A. Linton, E. A. O'Brien, A. J. E. A. Ryba, and R. A. Wilson. Constructive membership in black-box groups. J. Group Theory, 11:747--763, 2008.
• 30: D. F. Holt and S. Rees. Testing modules for irreducibility. J. Austral. Math. Soc. Series A, 57:1--16, 1994.
• 31: A. Hulpke and A. Seress. Short presentations for three-dimensional unitary groups. J. Algebra, 245:719--729, 2001.
• 32: G. Ivanyos and K. Lux. Treating the exceptional cases of the MeatAxe. Experimental Mathematics, 9:373--381, 2000.
• 33: W. M. Kantor. Sylow's theorem in polynomial time. J. Computer Sys. Sci., 30:359--394, 1985.
• 34: W. M. Kantor and A. Seress. Black box classical groups. Mem. AMS, 149, Nr. 708:viii+168 pp., 2001.
• 35: W. M. Kantor and A. Seress. Computing with matrix groups. In Groups, Combinatorics, and Geometry (Durham 2001), pp. 123--137. World Scientific, 2003.
• 36: D. E. Knuth. Notes on efficient representation of perm groups. Combinatorica, 11:33--43, 1991.
• 37: V. Landazuri and G. M. Seitz. On the minimal degrees of projective representations of the finite Chevalley groups. J. Algebra, 32:418--443, 1974.
• 38: E. M. Luks. Lectures on polynomial-time computation in groups. Northeastern U. TR NU-CCS-90-16, 1990.
• 39: E. M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica, v.7 n.1, p.87-99, Jan. 1987 [doi>10.1007/BF02579204]
• 40: E. M. Luks, Computing in solvable matrix groups, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, p.111-120, October 24-27, 1992 [doi>10.1109/SFCS.1992.267813]
• 41: E. M. Luks. Permutation groups and polynomial-time computation. In Groups and Computation, pp. 139--175. DIMACS, 1993.
• 42: E. M. Luks and A. Seress. Computing the Fitting subgroup and solvable radical of small-base permutation groups in nearly linear time. In Groups and Computation II, pp. 169--181. DIMACS, 1997.
• 43: C. W. Parker and R. A. Wilson. Recognising simplicity of black-box groups. Manuscript, 2004.
• 44: Lajos Rónyai, Computing the structure of finite algebras, Journal of Symbolic Computation, v.9 n.3, p.355-373, March 1990 [doi>10.1016/S0747-7171(08)80017-X]
• 45: J. Rotman. An Introduction to the Theory of Groups. Springer, 1994.
• 46: G. Seitz and A. E. Zalesskii. On the minimal degrees of projective representations of the finite Chevalley groups, II. J. Algebra, 158:233--243, 1993.
• 47: A. Seress. Permutation Group Algorithms. Cambridge University Press, 2003.
• 48: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 49: C. C. Sims. Computational methods in the study of permutation groups. In Computational problems in abstract algebra (Oxford, 1967), pp. 169--183. Pergamon Press, 1970.
• 50: Charles C. Sims, Computation with permutation groups, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.23-28, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806264]
• 51: M. Suzuki. On a class of doubly transitive groups. Ann. Math., 75:105--145, 1962.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms

Keywords:
computational group theory, discrete log, matrix groups