Solvability by radicals is in polynomial time.

*(English)*Zbl 0586.12002The 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.

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.

Reviewer: F. J. van der Linden (Eindhoven)

##### Keywords:

Lenstra-Lenstra-Lovász algorithm; solvable Galois group; polynomial; solvable in radicals; polynomial time
PDF
BibTeX
XML
Cite

\textit{S. Landau} and \textit{G. L. Miller}, J. Comput. Syst. Sci. 30, 179--208 (1985; Zbl 0586.12002)

Full Text:
DOI

##### References:

[1] | Artin, E., Galois theory, (1971), Univ. of Notre Dame Press Notre Dame, Ind |

[2] | Atkinson, M., An algorithm for finding the blocks of a permutation group, Math. comp., 911-913, (July 1975) |

[3] | Cameron, P.J., Finite permutation groups and finite simple groups, Bull. London math. soc., 13, 1-22, (1981) · Zbl 0463.20003 |

[4] | Edmonds, J., Systems of distinct representations and linear algebra, J. nat. bur. stand. ser. B, 71, No.4, 241-245, (1967) · Zbl 0178.03002 |

[5] | Edwards, H., Galois theory, (1984), Springer-Verlag New York · Zbl 0532.12001 |

[6] | Furst, M.; Hopcroft, J.; Luks, E., Polynomial time algorithms for permutation groups, (), 36-41 |

[7] | Galois, E., Oeuvres mathematiques, (1897), Gauthier-Villars Paris · JFM 28.0011.01 |

[8] | Lagrange, J.L., Réfexions sur la resolution algebraique des equations, (1770), Prussian Academy |

[9] | Landau, S., Factoring polynomials over algebraic number fields, SIAM J. comput., 14, No.1, 184-195, (1985) · Zbl 0565.12002 |

[10] | \scS. Landau, “On Computing Galois Groups, and its Application to Solvability by Radicals,” Tech. Report TR-288, Laboratory for Computer Science, M.I.T. |

[11] | Lang, S., Algebra, (1971), Addison-Wesley Reading, Mass |

[12] | Lenstra, A.K.; Lenstra, H.W.; Lovasz, L., Factoring polynomials with rational coefficients, Mathematische annelan, 261, 513-534, (1982) · Zbl 0488.12001 |

[13] | McKay, J., Some remarks on computing Galois groups, SIAM J. comput., 8, No.3, 344-347, (1979) · Zbl 0426.12015 |

[14] | \scG. Miller, Constructing field extensions without using primitive elements, in preparation. |

[15] | Neugebaur, O.; Sachs, A., Mathematical cuneiform texts, (1945), Amer. Orient. Soc New Haven, Conn · Zbl 0060.00401 |

[16] | Palfy, P., A polynomial bound for the orders of primitive solvable groups, J. algebra, 127-137, (July 1982) |

[17] | Sims, C., Computational methods in the study of permutation groups, () · Zbl 0215.10002 |

[18] | Staduhar, R.P., The determination of Galois groups, Math. comp., 27, 981-996, (1973) · Zbl 0282.12004 |

[19] | \scB. Trager, Algebraic factoring and rational function integration, in “Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation,” pp. 219-226. · Zbl 0498.12005 |

[20] | Van Der Waerden, B.L., Modern algebra, (1941), Ungar New York · Zbl 0025.38502 |

[21] | Wielandt, H., Finite permutation groups, (1964), Academic Press New York · Zbl 0138.02501 |

[22] | Weinberger, P.; Rothschild, L., Factoring polynomials over algebraic number fields, J. assoc. comput. Mach., 335-350, (Dec. 1976) |

[23] | 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.