Test to see if a degree $\leq4$ polynomial is factorable

Question

I'm in the middle of a programming project and we'd like to have tests to determine if polynomials in $\mathbb{Z}[x]$ of degrees up to 4 are factorable over $\mathbb{Q}$. A test that computes the discriminant (or something similar) and then asks if that is a perfect square, perfect cube, etc. is hard to implement, because I don't know how to test if a given floating point real (like $\sqrt{\Delta}$) is rational. Not to mention that there could be rounding error.

So for degrees 2 and 3, what I've come up with is to apply the rational root theorem. This requires primefactoring the leading and constant coefficients and testing each ratio until a root is found. So if there are many prime factors, this is costly. But it works. Then again it's overkill, since it's actually factoring rather than just testing for factorability.

With degree 4, I'm not sure what to do.

Is there an out here? Should I instead focus on roots of discriminants? I could restructure the data type for coefficients to be rational numbers that separately keep track of numerators and denominators, and then checking to see if $\Delta$ is a perfect square would be easy. But is there something less intense?

Answer 1

First, by Gauss's lemma, it suffices to first remove the content, then factor the primitive part over the integers. That is, everything is integers and you need not worry about rationals at all.

Next, since you're prepared to factor integers to use the RRR, I recommend Kronecker's method. To summarize, evaluate the (primitive) polynomial at three values. Suppose $f(1)=3$. If $f(x)=f_1(x)f_2(x)$, we must have $f_1(x)|3$ and $f_2(x)|3$. This is not very many possibilities. Doing this at three places, we have three values for each of $f_1, f_2$, which specifies it uniquely (since it's quadratic). Test if they both have integer coefficients, and if their product is in fact $f(x)$. We do this for each combination; i.e. $f_1(1)=1, f_2(1)=3$, and again for $f_1(1)=-3, f_2(1)=-1$, etc.

Since you get to pick the three places, you can be selective. For example, if $f(1)$ is really big or has many factors, skip it and instead try $f(2)$.

Answer 2

In degree four, if there are no rational roots, you will have a workable program by just taking divisors (including negative) of the top coefficient $a_4$ and of the constant coefficient $a_0,$ writing $$ a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0 = (d_1 x^2 + e_1 x + f_1) \left( \frac{a_4}{d_1} x^2 + e_2 x + \frac{a_0}{f_1} \right) $$ and seeing how far you get. Without bounds, simultaneous polynomial equations are horrible (Grobner bases and so on) but this is very, very low degree and few remaining variables, i.e. two, $e_1,e_2$. Actually, I think the equations may be linear in the $e$'s.

It might be quicker to not factor $a_0$ and go strictly top down. Hard to predict.