# Factoring polynomials to factors involving complex coefficients

I've run into some problems using Factor on polynomials with complex coefficient factors. Reading the documentation it looks like it only factors over the Integers by default. So I've found I can factor some polynomials with complex factors using this:

Factor[ poly, Extension -> I ]


For example, the polynomial $$x^2+1$$ won't factor with just Factor[x^2+1], however it does factor properly when I add the imaginary unit extension.

The unexpected problem I experienced is that another polynomial such as $$8x^3-7x^2+10x-5$$ still won't be factorized - even with the imaginary extension added!

What am I missing here? How do I simply get Mathematica to completely factor any polynomial with complex factors I give it?

-
The specific output I am after is a product of first degree polynomials. For example $x^2+1$ factors into (x-i)(x+i). Another Example: $4x^3-8x^2-x+2$ factors as $(x-2)(2x-1)(2x+1)$ –  jcelios Jul 12 '12 at 21:44
@Artes Ok, I added it back. –  rm -rf Jul 12 '12 at 22:55
The associated math.SE question. –  Ｊ. Ｍ. Jul 13 '12 at 0:29
@jcelios To addres the question this answer includes the issues (implicitly present here) which could be also interesting for you : mathematica.stackexchange.com/questions/6740/… –  Artes Jul 13 '12 at 0:34
@J.M. This link is interesting purely on the mathematical layer, however to discuss in the greater extent the algorithmic layer we need more specific information. –  Artes Jul 13 '12 at 0:40

By default Mathematica can factorize polynomials to lower order ones in terms of integers if it's possible. Extension serves factorization over the rationals extended by a finite set of algebraic numbers, i.e. any element of the extension is a finite combination of rationals and algebraics $(a_1, a_2,...,a_n)$. The fundamental theorem of algebra states that in principle one can always factorize any polynomial of one variable by finding its roots, nevertheless there are fundamental limitations (Galois theorem, Abel's impossibility theorem, etc.) as well as technical problems (simplifying roots in terms of nested radicals, efficency, etc.).

This polynomial :

p[x_] := 8 x^3 - 7 x^2 + 10 x - 5


has three complex roots (only one real) :

 s = Solve[ p[x] == 0, x]


involving irrational numbers and therefore it cannot be factorized by default nor using Extension->I. The roots are algebraic numbers since p[x] is a polynomial with integer coefficients :

Element[#, Algebraics] & /@ s[[All, 1, 2]]

{True, True, True}


so it implies we can factorize p[x] using an appropriate Extension. In order to factor p[x] completely one should use the field of the rationals numbers extended by the roots of the polynomial e.g.

Factor[ p[x],  Extension -> {Root[p[x], 1], Root[p[x], 2], Root[p[x], 3]}]


However since this expression produces the output in terms of Root objects, one would prefer it in terms of radicals, e.g.

Factor[ p[x], Extension -> ToRadicals @ {Root[p[x], 1], Root[p[x], 2], Root[p[x], 3]}] //


We could also proceed along a different route, taking only terms that cause the roots are not rational numbers. Therefore we select these numbers : {(2143 + 72 Sqrt[2230])^(1/3), Sqrt[3], I}. We included I because two of the roots are complex.

Factor[ p[x], Extension -> {(2143 + 72 Sqrt[2230])^(1/3), Sqrt[3], I}] // Together


There is yet another (a bit more involved) way to factorize this polynomial using FactorList, which results in this case in the simplest form :

Times @@ Simplify /@ Power @@@
FactorList[ p[x],
Extension -> ToRadicals @ { Root[p[x], 1], Root[p[x], 2], Root[p[x], 3]}]//


FactorList made possible simplifying every factor instead of using Simplify to the result of Factor which produced expanded form of the polylomial. Although the last factorization is not much simpler than appropriate multiplying terms like (x - ToRadicals @ Root[ p[x], i] @ ), there is an aspect which makes functions like Factor really useful, e.g. when one encounters the problem of expressing roots in terms of radicals, consider a very simple example :

FullSimplify @ Solve[ MinimalPolynomial[Sqrt[3] + Sqrt[5]][x] == 0, x]


To overcome this problem one could use e.g. an appropriate ComplexityFunction to simplify completely the radicals, but in general this is far from being obvious how one should proceed. Nevertheless if we know what the Extension should be, then the answer is simple, e.g.

Factor[ 4 - 16 #1^2 + #1^4 &[x], Extension -> {Sqrt[3], Sqrt[5]}]


or

Factor[ -  27 Sqrt[3] + 189 x - 189 Sqrt[3] x^2 + 315 x^3
- 105 Sqrt[3] x^4 + 63 x^5 - 7 Sqrt[3] x^6 + x^7,   Extension -> Automatic]


-
Thanks, but that is not the output form I'm looking for (See the comment on the original post). I've always been under the impression that fully factoring a polynomial meant putting it into the form of a product of first degree and/or constant polynomials. $$(Ax+a)(Bx+b)(Cx+c)...$$ Since the results you've posted contain at least one second degree polynomial (I see an x^2 for example) I'm not sure why it's considered a properly factored output. But perhaps there is a semantic or notational confusion issue. –  jcelios Jul 12 '12 at 22:05
As well is it simply not possible to tell mathematica to factor over the set of complex numbers rather then just the rationals + some specific given algebraic numbers? Or does this lead into issues with Non-Computable Transcendental Numbers? If so I should think it would be possible to simply factor over all Computable Algebraic Numbers (given enough computing power of course). –  jcelios Jul 12 '12 at 22:14
You had an integer coefficient polynomial, so its roots are algebraic numbers. The edit of my post should clarify your doubts. I factorized p[x] to three first order polynomials taking an appropriate extension field. –  Artes Jul 12 '12 at 22:20
@jcelios Facorizatoion over all algebraic numbers is not possible. You can only take a finite number of algebraics to proceed with factorization of polynomials. –  Artes Jul 12 '12 at 22:29
This may be too far beyond the scope of my original question (or this site for that matter) but why isn't it possible? It's not that I don't believe you, I'm just curious. –  jcelios Jul 12 '12 at 22:35

More concise, but same idea as in Artes' approach (which I upvoted, but I'm adding this anyway because it won't squeeze into a comment).

factorCompletely[poly_, x_] := Module[
{solns, lcoeff},
solns = Solve[poly == 0, x, Cubics -> False, Quartics -> False];
lcoeff = Coefficient[poly, x^Exponent[poly, x]];
lcoeff*(Times @@ (x - (x /. solns)))
]


Examples:

p[x_] := 8 x^3 - 7 x^2 + 10 x - 5

factorCompletely[p[x], x]

(* Out[66]= 8 (x - Root[-5 + 10 #1 - 7 #1^2 + 8 #1^3 & , 1])
(x - Root[-5 + 10 #1 - 7 #1^2 + 8 #1^3 & , 2])
(x - Root[-5 + 10 #1 - 7 #1^2 + 8 #1^3 & , 3]) *)

factorCompletely[ 4 x^3 - 8 x^2 - x + 2, x]

(* Out[67]= 4 (-2 + x) (-(1/2) + x) (1/2 + x) *)

-

For a polynomial of arbitrary degree > 4, of course in general Mathematica, and nobody, may be able to factor it in any reasonable way because its roots may not be expressible in terms of radicals. But for degree <= 4, and in various higher-degree special cases, you could exploit Solve. E.g.,

p[x_]:=8 x^3-7 x^2+10 x-5
Times @@ (x - y /. (Solve[p[x] == 0, x] /. x -> y))

-
Factor is advantageous, to see it try e.g. Times @@ (x - y /. (Solve[4 - 16 #1^2 + #1^4 &[x] == 0, x] /. x -> y)) and Factor[4 - 16 #1^2 + #1^4 &[x], Extension -> {Sqrt[3], Sqrt[5]}]. –  Artes Jul 13 '12 at 3:23
No doubt using Factor with specified extensions can provide a simpler result. But doing so requires already knowing which quadratic, or other, extensions to use! –  murray Jul 13 '12 at 14:00
 fullFactor[f_, x_] := Roots[f == 0, x] /. Equal -> ((#1 - #2) &) /. Or -> Times
fullFactor[x^5 - 1, x]
(* (-1 + x) ((-1)^(1/5) + x) (-(-1)^(2/5) + x) ((-1)^(3/5) + x) (-(-1)^(4/5) + x) *)

-