13
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 9
    $\begingroup$ Presumably the context is eigenvalue/eigenvector decomposition, and "algorithm [for factoring polynomials]" is intended to mean "algorithm for solving in radicals". $\endgroup$
    – Noam D. Elkies
    Commented Nov 3, 2011 at 3:05
  • $\begingroup$ Noam, what privileged role does computing with radicals have within linear algebra? $\endgroup$
    – David Feldman
    Commented Nov 3, 2011 at 3:40
  • 2
    $\begingroup$ I just wrote Weintraub, maybe you could have done it too. $\endgroup$
    – Felipe Voloch
    Commented Nov 3, 2011 at 15:13
  • 2
    $\begingroup$ @David: It hasn't. It is just that the majority (or at least a substantial part) of non-algebraists seems to think that the essence of galois theory is a general "You cannot solve polynomial equations of degree greater four in any way". Hence it is likely that the only way to salvage these overly general statements of the form "XYZ is not possible because Galois said so" is the reformulation "XYZ is not possible if radicals and basic arithmetic are the only things you are allowed to use". $\endgroup$
    – Johannes Hahn
    Commented Nov 3, 2011 at 21:24
  • $\begingroup$ Thanks, Felipe, I take your point, but I didn't mean here to pick a bone with the author. Rather I wanted input from anyone who knows about recursion and complexity as to whether Galois theory has interpretations or ramifications concerning the mere existence of factoring algorithms---regardless of what Weintraub has in mind. $\endgroup$
    – David Feldman
    Commented Nov 4, 2011 at 2:49

5 Answers 5

Reset to default
13
$\begingroup$

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).

Improve this answer
$\endgroup$
12
$\begingroup$

As Noam Elkies wrote, this statement was made in the context of finding eigenvalues. The full paragraph reads "We not only show the existence of the Jordan canonical form, but also derive an algorithm for finding the Jordan canonical form of T as well as finding a Jordan basis of V, assuming we can factor the characteristic polynomial c_T(x). (Of course, there is no algorithm for factoring polynomials, as we know from Galois theory.)" Thus, from the context it is clear that what was meant by factoring was factoring into a product of linear factors over an arbitrary field F.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I am glad that my answer said "as stated", since clearly "in context", I would have been wrong! But it gave me an opportunity to publicize Mark van Hoeij's fantastic work, so that part was useful. $\endgroup$
    – Jacques Carette
    Commented Nov 3, 2011 at 20:45
  • 4
    $\begingroup$ Perhaps I missunderstand the point completely, but then what has this to do with Galois theory? $\endgroup$
    – user9072
    Commented Nov 3, 2011 at 20:47
  • $\begingroup$ Thanks. With quid above, I also still don't understand the connection to Galois theory. I can think of fields where one has no factoring algorithm...the field of fractions of a countable nonstandard model of PA...but there one can't even ever have an algorithm for the field addition or multiplication. But typically one doesn't discuss the existence/non-existence of algorithms unless one has the details of the problem instance presented effectively. $\endgroup$
    – David Feldman
    Commented Nov 4, 2011 at 2:49
  • $\begingroup$ To say just a little more, I do believe that recursive (necessarily countable) fields have recursive algebraic closures, and one can factor polynomials algorithmically, in the algebraic closure, lacking any better way, by exhaustively trying every possible linear factor. $\endgroup$
    – David Feldman
    Commented Nov 4, 2011 at 3:26
  • $\begingroup$ As no additional explanation was given, I now downvoted this answer. There are two interpretations of the statement I can think of; neither has much to do with Galois theory. So, to me this is a non-answer. $\endgroup$
    – user9072
    Commented Nov 5, 2011 at 15:52
7
$\begingroup$

When I was a graduate student, I fell into conversation with a professor from another university who was chortling over a paper that presented an algorithm for solving quintic polynomials. (The algorithm did not purport to find a solution in radicals.) He was sure the author must be a fool for not realizing that in light of Galois, there can be no such algorithm. When I expressed something like surprise/doubt, it quickly became apparent that this full professor of mathematics didn't have a clue what Galois had or had not proved --- and had no interest in finding out. But he persisted in his belief that "by Galois" there can be no such algorithm.

My guess is that Weintraub (like all of us from time to time) made a mental slip from which he (unlike my professor friend) would immediately retreat if it were pointed out.

This probably should have been a comment but it was too long to fit.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! If Weintraub hadn't himself written a book on Galois theory (already in its 2nd edition) I too would have immediately taken this for sloppy talk and not worried that he had something in mind I wasn't seeing. He even repeats this "slip" elsewhere in the book! Everyone makes mistakes - no big deal - but it makes me wonder if publishers even bother with readers and fact checkers anymore. $\endgroup$
    – David Feldman
    Commented Nov 3, 2011 at 2:33
5
$\begingroup$

The roots of any polynomial with complex coefficients can in fact be given in terms of generalized hypergeometric functions or theta constants. There is an appendix of Mumford's "Lectures on Theta" by Umemura, where the later is explained in some detail. On the other hand the Jordan canonical form is numerically unstable, so that description is not really useful.

Improve this answer
$\endgroup$
2
$\begingroup$

Hermite ca 1858 in Comptes Rendus, solved the general 5-ic using the j-function and the modular polynomial Phi_5(j(z), j(5z)).

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .