## Solvability by radicals is in polynomial time.(English)Zbl 0586.12002

The authors present an algorithm to prove that a given polynomial $$f$$ over the integers is solvable in radicals, and one to write a zero of a solvable polynomial $$f$$ in radicals. Both algorithms are in polynomial time in the size of $$f$$. The determination whether $$f$$ is solvable in radicals is equivalent to the determination whether the Galois group $$G$$ of $$f$$ is solvable. The algorithm does not compute $$G$$, nor does it give the order of it or a set of generators. The algorithm uses the Lenstra, Lenstra and Lovász algorithm to factor polynomials over the integers in polynomial time. It also uses a result of Pálfy that the order of a primitive solvable group acting on $$n$$ elements is bounded above by $$24^{-1/3}n^{3.243999...}$$.
Let $$\alpha_1,\ldots,\alpha_n$$ be the zeros of $$f$$. The Galois group of $$f$$ is defined to be the Galois group of $$\mathbb Q(\alpha_1,\ldots,\alpha_n)/\mathbb Q$$. In order to determine whether $$G$$ is solvable the extension $$\mathbb Q(\alpha_1,\ldots,\alpha_n)/\mathbb Q$$ will be split up into several small parts of which it is easy to check whether they are solvable. These parts are defined recursively to be the normal closure of some subfield of $$\mathbb Q(\alpha_1)$$ that is defined to be the field of fixpoints of all elements of $$G$$ that leave a special set (block) of zeros of $$f$$ fixed. Using the result of Pálfy, it will then be determined whether the upper extension is solvable, and for the lower extension the problem will be solved recursively.

### MSC:

 11Y40 Algebraic number theory computations 11R32 Galois theory 11Y05 Factorization
Full Text:

### References:

  Artin, E., Galois theory, (1971), Univ. of Notre Dame Press Notre Dame, Ind  Atkinson, M., An algorithm for finding the blocks of a permutation group, Math. comp., 911-913, (July 1975)  Cameron, P.J., Finite permutation groups and finite simple groups, Bull. London math. soc., 13, 1-22, (1981) · Zbl 0463.20003  Edmonds, J., Systems of distinct representations and linear algebra, J. nat. bur. stand. ser. B, 71, No.4, 241-245, (1967) · Zbl 0178.03002  Edwards, H., Galois theory, (1984), Springer-Verlag New York · Zbl 0532.12001  Furst, M.; Hopcroft, J.; Luks, E., Polynomial time algorithms for permutation groups, (), 36-41  Galois, E., Oeuvres mathematiques, (1897), Gauthier-Villars Paris · JFM 28.0011.01  Lagrange, J.L., Réfexions sur la resolution algebraique des equations, (1770), Prussian Academy  Landau, S., Factoring polynomials over algebraic number fields, SIAM J. comput., 14, No.1, 184-195, (1985) · Zbl 0565.12002  {\scS. Landau}, “On Computing Galois Groups, and its Application to Solvability by Radicals,” Tech. Report TR-288, Laboratory for Computer Science, M.I.T.  Lang, S., Algebra, (1971), Addison-Wesley Reading, Mass  Lenstra, A.K.; Lenstra, H.W.; Lovasz, L., Factoring polynomials with rational coefficients, Mathematische annelan, 261, 513-534, (1982) · Zbl 0488.12001  McKay, J., Some remarks on computing Galois groups, SIAM J. comput., 8, No.3, 344-347, (1979) · Zbl 0426.12015  {\scG. Miller}, Constructing field extensions without using primitive elements, in preparation.  Neugebaur, O.; Sachs, A., Mathematical cuneiform texts, (1945), Amer. Orient. Soc New Haven, Conn · Zbl 0060.00401  Palfy, P., A polynomial bound for the orders of primitive solvable groups, J. algebra, 127-137, (July 1982)  Sims, C., Computational methods in the study of permutation groups, () · Zbl 0215.10002  Staduhar, R.P., The determination of Galois groups, Math. comp., 27, 981-996, (1973) · Zbl 0282.12004  {\scB. Trager}, Algebraic factoring and rational function integration, in “Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation,” pp. 219-226. · Zbl 0498.12005  Van Der Waerden, B.L., Modern algebra, (1941), Ungar New York · Zbl 0025.38502  Wielandt, H., Finite permutation groups, (1964), Academic Press New York · Zbl 0138.02501  Weinberger, P.; Rothschild, L., Factoring polynomials over algebraic number fields, J. assoc. comput. Mach., 335-350, (Dec. 1976)  Zassenhaus, H., On the group of an equation, (), 69-88
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.