Solvability by radicals is in polynomial time
type: Item
instance of: scholarly article
title: Solvability by radicals is in polynomial time
zbMATH Open document ID: 0586.12002
DOI: 10.1016/0022-0000(85)90013-3
author: Susan Landau
author: Gary L. Miller
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11Y40
Mathematics Subject Classification ID: 11R32
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 68Q40
zbMATH DE Number: 3939444
zbMATH Keywords: Lenstra-Lenstra-Lovász algorithm
zbMATH Keywords: solvable Galois group
zbMATH Keywords: polynomial
zbMATH Keywords: solvable in radicals
zbMATH Keywords: polynomial time
Wikidata QID: Q55967929
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90013-3
OpenAlex ID: W1976456789
cites work: An Algorithm for Finding the Blocks of a Permutation Group
cites work: Finite Permutation Groups and Finite Simple Groups
cites work: Systems of distinct representatives and linear algebra
cites work: Q3313943
cites work: Factoring Polynomials over Algebraic Number Fields
cites work: Factoring polynomials with rational coefficients
cites work: Some Remarks on Computing Galois Groups
cites work: Q5833980
cites work: A polynomial bound for the orders of primitive solvable groups
cites work: Q5617749
cites work: The Determination of Galois Groups
cites work: Q3963106
cites work: Zur pythagoreischen Algebra: Quadratwurzel und Kubikwurzel
cites work: Q5512231
cites work: Factoring Polynomials Over Algebraic Number Fields
cites work: Q5659661
DBLP publication ID: journals/jcss/LandauM85
description: scientific article; zbMATH DE number 3939444