Polynomial time solutions of some problems of computational algebra

ABSTRACT

The first structure theory in abstract algebra was that of finite dimensional Lie algebras (Cartan-Killing), followed by the structure theory of associative algebras (Wedderburn-Artin). These theories determine, in a non-constructive way, the basic building blocks of the respective algebras (the radical and the simple components of the factor by the radical). In view of the extensive computations done in such algebras, it seems important to design efficient algorithms to find these building blocks. We find polynomial time solutions to a substantial part of these problems. We restrict our attention to algebras over finite fields and over algebraic number fields. We succeed in determining the radical (the “bad part” of the algebra) in polynomial time, using (in the case of prime characteristic) some new algebraic results developed in this paper. For associative algebras we are able to determine the simple components as well. This latter result generalizes factorization of polynomials over the given field. Correspondingly, our algorithm over finite fields is Las Vegas. Some of the results generalize to fields given by oracles. Some fundamental problems remain open. An example: decide whether or not a given rational algebra is a noncommutative field.

REFERENCES

• 1: L. Bahai, W. M. Kaator, E. M. Luks, Computational eomplezittl lad the eldssificatiop o! }?nit~ simple groups, Proc. 24th IEEE Syrup. Found. Camp. $ci., Tuc.son, Arizona, 1983, 162-171.
• 2: R.E. Beck, B. Kolman, I. N. Stewart, Computing the structure o! o Lie algebra, Computers in nonassociarve rings and algebras, Academic Press, New 'fork-San Francisco- London, 1077, 167-188.
• 3: E. R, Bcrlekamp, Factoring polynomials over large finite/ields, Math. Camp. 24 (1070), 713-715.
• 4: A Borodin , S Cook , N Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, v.58 n.1-3, p.113-136, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80060-6]
• 5: A.L. Chistov, D. Yu. Grigoryev, Pollmomid-time/he. taring o! the multlvgriable polgnomiale o~cr i global field, LOMI preprint, Leningrad 17~2. (to appeaz in J. of Symbolic Computation)
• 6: L.E. Dickson, Algebras and their srlthmctics, University of Chicago, 1923.
• 7: I.N. Hcrsteia, Nonco;nmutative rings, Math. Assoc. of America, 1968.
• 8: N. Jacobson, Lie a/;ebras, John Wiley, New York- London, 1962.
• 9: D. E',. Kauth, TAe art o! computer prograraming, Vol. t, Seminstmerical algorithms, Addison-Wesley, Reading, 1981.
• 10: S. Landau, Factoring pollmornials o~er 41itebs'aie number fields is in polynomial time, SIAM J. Cor~p., 1085, to appear
• 11: Arjen K. Lenstra, Factoring polynominals over algebraic number fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.245-254, March 28-30, 1983
• 12: A.K. Leastra, H. W. Lenstra, L. I,ov~z, Factoring polynomials with rational cocfficicnts, Math. Ann. 261 (1982), 515-534.
• 13: M.O. Rabid, Probabilistic algorithms in .finitt ji~lda, SIAM J. Camp. 9 (1980), 273-280.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory, Verification