[Math] Galois theory and algorithms

galois-theory

Steven Weintraub's book {\em A Guide to Advanced Linear Algebra} includes the following remark:

"Of course, there is no algorithm for factoring polynomials, as we know from Galois theory."

I can't make sense of this. I feel confident that Galois theory doesn't speak to the question of algorithms, and confident that there do exist algorithms for factoring integer polynomials over the integers (after Kronecker), and strategies for computing in the field of algebraic numbers that make tautological the question of factoring polynomials irreducible over the rationals.

Have I missed some way to salvage this remark?

Best Answer

You are absolutely correct, this statement as stated does not make much sense. Over the integers (or any algebraic extension thereof), there are known algorithms for factoring multivariate polynomials. Any textbook on Computer Algebra will list some of them.

This has been an area of research with ups and downs, with a recent resurgence. The work of Mark van Hoeij (scroll down to the section on polynomials) is especially impressive. He has the fastest currently known algorithms, in theory and in practice, for the problem.

There are even algorithms for absolute factorization, i.e. finding the exact algebraic extension needed of the base field for a (univariate) polynomial to split into linear factors. Most CASes have implementations (see ?evala,AFactor in Maple, for example).

Related Question