Computing irreducible representations of finite groups
HTML articles powered by AMS MathViewer
- by László Babai and Lajos Rónyai PDF
- Math. Comp. 55 (1990), 705-722 Request permission
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.References
- M. D. Atkinson, The complexity of group algebra computations, Theoret. Comput. Sci. 5 (1977/78), no. 2, 205–209. MR 483650, DOI 10.1016/0304-3975(77)90007-X
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 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 10.1016/0304-3975(87)90041-7
- Richard Brauer, Applications of induced characters, Amer. J. Math. 69 (1947), 709–716. MR 22851, DOI 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 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 10.1137/0218040
- Michael Clausen, Fast generalized Fourier transforms, Theoret. Comput. Sci. 67 (1989), no. 1, 55–63. MR 1015084, DOI 10.1016/0304-3975(89)90021-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 10.1007/BF02162877
- John D. Dixon, Computing irreducible representations of groups, Math. Comp. 24 (1970), 707–712. MR 280611, DOI 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 10.1137/0214015
- A. K. Lenstra, Factoring multivariate integral polynomials, Theoret. Comput. Sci. 34 (1984), no. 1-2, 207–213. MR 774045, DOI 10.1016/0304-3975(84)90117-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 10.1007/BF01457454
- Richard S. Pierce, Associative algebras, Studies in the History of Modern Science, vol. 9, Springer-Verlag, New York-Berlin, 1982. 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 10.1016/0196-6774(88)90014-4
- Lajos Rónyai, Computing the structure of finite algebras, J. Symbolic Comput. 9 (1990), no. 3, 355–373. MR 1056632, DOI 10.1016/S0747-7171(08)80017-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 10.1145/322217.322225
Additional Information
- © Copyright 1990 American Mathematical Society
- 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