Solvability by radicals is in polynomial time (Q1071803): Difference between revisions

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.