Computing irreducible representations of finite groups
Authors:
László Babai and Lajos Rónyai
Journal:
Math. Comp. 55 (1990), 705-722
MSC:
Primary 68Q40; Secondary 11R33, 20C40
DOI:
https://doi.org/10.1090/S0025-5718-1990-1035925-1
MathSciNet review:
1035925
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: We consider the bit-complexity of the problem stated in the title. Exact computations in algebraic number fields are performed symbolically. We present a polynomial-time algorithm to find a complete set of nonequivalent irreducible representations over the field of complex numbers of a finite group given by its multiplication table. In particular, it follows that some representative of each equivalence class of irreducible representations admits a polynomial-size description. We also consider the problem of decomposing a given representation $\mathcal {V}$ of the finite group G over an algebraic number field F into absolutely irreducible constituents. We are able to do this in deterministic polynomial time if $\mathcal {V}$ is given by the list of matrices $\{ \mathcal {V}(g);g \in G\}$; and in randomized (Las Vegas) polynomial time under the more concise input $\{ \mathcal {V}(g);g \in S\}$, where S is a set of generators of G.
- M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977/78), no. 2, 205–209. MR 483650, DOI https://doi.org/10.1016/0304-3975%2877%2990007-X
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI https://doi.org/10.1090/S0025-5718-1970-0276200-X M. Ben-Or, Probabilistic algorithms in finite fields, Proc. 22nd IEEE FOCS, 1981, pp. 394-398.
- Thomas Beth, On the computational complexity of the general discrete Fourier transform, Theoret. Comput. Sci. 51 (1987), no. 3, 331–339. MR 909461, DOI https://doi.org/10.1016/0304-3975%2887%2990041-7
- Richard Brauer, Applications of induced characters, Amer. J. Math. 69 (1947), 709–716. MR 22851, DOI https://doi.org/10.2307/2371795
- C. Brott and J. Neubüser, A programme for the calculation of characters and representations of finite groups, Computational problems in abstract algebra (Proc. Conf., Oxford, 1967), Pergamon, Oxford, 1970, pp. 101–110. MR 0291309
- Richard Brauer and John Tate, On the characters of finite groups, Ann. of Math. (2) 62 (1955), 1–7. MR 69825, DOI https://doi.org/10.2307/2007097
- W. Burnside, Theory of groups of finite order, Dover Publications, Inc., New York, 1955. 2d ed. MR 0069818
- A. L. Chistov, Calculation of the Galois group over a function field of characteristic zero with an algebraically closed constant field in polynomial time, Mathematical methods for constructing and analyzing algorithms (Russian), “Nauka” Leningrad. Otdel., Leningrad, 1990, pp. 200–232, 237 (Russian). MR 1082380
- Michael Clausen, Fast Fourier transforms for metabelian groups, SIAM J. Comput. 18 (1989), no. 3, 584–593. MR 996838, DOI https://doi.org/10.1137/0218040
- Michael Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), no. 1, 55–63. MR 1015084, DOI https://doi.org/10.1016/0304-3975%2889%2990021-2
- Charles W. Curtis and Irving Reiner, Representation theory of finite groups and associative algebras, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1988. Reprint of the 1962 original; A Wiley-Interscience Publication. MR 1013113 P. Diaconis, Spectral analysis for ranked data, Ann. Statist. (to appear).
- Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069 P. Diaconis and D. Rockmore, Efficient computation of the Fourier transform on finite groups, manuscript, 1988.
- John D. Dixon, High speed computation of group characters, Numer. Math. 10 (1967), 446–450. MR 224726, DOI https://doi.org/10.1007/BF02162877
- John D. Dixon, Computing irreducible representations of groups, Math. Comp. 24 (1970), 707–712. MR 280611, DOI https://doi.org/10.1090/S0025-5718-1970-0280611-6 W. Eberly, Computations for algebras and group representations, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1989.
- Walter Feit, Characters of finite groups, W. A. Benjamin, Inc., New York-Amsterdam, 1967. MR 0219636 K. Friedl and L. Rónyai, Polynomial time solutions of some problems in computational algebra, Proc. 17th ACM Sympos. on Theory of Computing, 1985, pp. 153-162.
- Susan Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), no. 1, 184–195. MR 774938, DOI https://doi.org/10.1137/0214015
- A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI https://doi.org/10.1016/0304-3975%2884%2990117-8
- A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, DOI https://doi.org/10.1007/BF01457454
- Richard S. Pierce, Associative algebras, Graduate Texts in Mathematics, vol. 88, Springer-Verlag, New York-Berlin, 1982. Studies in the History of Modern Science, 9. MR 674652 L. Rónyai, Simple algebras are difficult, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 398-408.
- Lajos Rónyai, Zero divisors in quaternion algebras, J. Algorithms 9 (1988), no. 4, 494–506. MR 970191, DOI https://doi.org/10.1016/0196-6774%2888%2990014-4
- Lajos Rónyai, Computing the structure of finite algebras, J. Symbolic Comput. 9 (1990), no. 3, 355–373. MR 1056632, DOI https://doi.org/10.1016/S0747-7171%2808%2980017-X
- J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), no. 4, 701–717. MR 594695, DOI https://doi.org/10.1145/322217.322225
Retrieve articles in Mathematics of Computation with MSC: 68Q40, 11R33, 20C40
Retrieve articles in all journals with MSC: 68Q40, 11R33, 20C40
Additional Information
Article copyright:
© Copyright 1990
American Mathematical Society