Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
A test for rational square root shol dnot be that bad. A rational $\frac ab$ (in shortest terms) is a square iff both $a$ and $b$ are square integers. A positive integer is square (without prime factorization) iff it is the square of $\lfloor \sqrt n+\frac12\rfloor$ (which allows rounding error in the square root - but the floating point data type must have precision enough to accomodate integers the sie of $\sqrt n$ comfortably. –  Hagen von Eitzen Jun 23 '13 at 21:51
    
Part of my concerns are alleviated when I realized that since I am starting with integer coefficients, discriminants will be integer, and checking for squareness won't be hard. –  alex.jordan Jun 23 '13 at 21:53

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
    
+1 OK, thanks. Just curious: is it your opinion that I'm going about this the right way, or should I switch over to recording everything with a rational number data type instead of a real? Personally I am starting to think that the lack of efficiency from primefactoring combined with iterating through so many combinations might make it worth the effort up front. –  alex.jordan Jun 23 '13 at 18:52
    
@alex.jordan I do not see that you need use real numbers for anything. Then again, I have never done anything where integer factoring would be regarded as slowing down the computation, so i am not familiar with your concerns. I suppose you may need to allow a rational multiplier in front of the two quadratics; but there are results about factoring over $\mathbb Q$ if and only if over $\mathbb Z.$ I will try to remember. –  Will Jagy Jun 23 '13 at 19:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.