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 am wondering if there are any algorithms to factor polynomials in multiple variables, when you know that the factors are other polynomials with rational or integer coefficients.

I know you have the rational root theorem, which helps out a lot, but it isn't always obvious how to apply this. Suppose we have the expression $$ 2y^6 - 5x^6 + x^5y^5 - 10xy $$

(I deliberately choose factors with x and y in high powers, to avoid the solutions being solving by completing the square, Cardano's formula, or Ferrari's formula)

This case might be doable: the powers in the terms suggest terms of $x^5$ and $y^5$ and $x$ and $y$, so with a little inspection one might expect the factorization to be of the form $(ax^5+by)(cy^5+dx)$. The term $x^5y^5$ suggests $a=c=1$ and from there it's almost trivial (you can use the rational root theorem, but I don't think that is even necessary).

It seems to be doable in this case, which makes it plausible that there is an algorithm who does something like this. Also, I was wondering about another specific case, in just one variable: $$ (x - a)(x - b)(x - c) $$

With $a, b, c$ integers with a very large absolute value. You can't use Cardano for this (casus irreducibilis), and in order to use the rational root theorem, you need to factorize abc, a very large number (which is very slow).

Besides, using the rational root theorem would not make use of the information that the values $a + b + c$ and $bc + ac + ab$ are also known (because they are coefficients in the polynomial).

One trivial algorithm I can come up with is to enumerate all polynomials (we do this by enumerating their coefficients, and integers and rationals are countable, so we can do this) with powers equal to or lower than the powers in the original polynomial, and try if long division yields a rest term (if not, we found a factor). Of course, this is too slow to be practical, but this and the fact that Wolfram Alpha can usually find the factorization of complicated polynomials (though I haven't tried this thoroughly), suggests there is at least one algorithm to do this in a more or less practical way.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

There are algorithms for factoring univariate polynomials with integer coefficients like the Zassenhaus algorithm that reduces the problem modulo small primes and then uses Hensel-lifting to probe for the integer factors, and for which modular factors have to be combined. Or the LLL based factorization algorithm that looks for the minimal polynomial of a numerically with high precision computed root.

So chose a random small to medium integer $m$ to replace $y$, perform univariate factorization and apply Hensel lifting modulo powers of $(y-m)$ to the factors. Again, if after the lifting there remain factors with too high a degree, look for combinations of them that are proper factors.

share|improve this answer
    
First line on wikipedia page: ``In computational algebra, the Cantor–Zassenhaus algorithm is a well known method...'' I guess I have a little reading-up to do! Thank you! –  Mon Kee Poo Mar 9 at 4:27

You can view $2y^6−5x^6+x^5y^5−10xy$ as a polynomial in $y$. So write it as $$2y^6+x^5y^5-10xy−5x^6$$ This polynomial in $y$ has coefficients in $\mathbb{Z}[x]$. The constant term (with respect to the variable $y$) is $-5x^6$ If the polynomial is not irreducible it hast at least one factor of degree 1,2 or 3 with respect ot the variable y. if it has a factor of degree 1 this factot has the form $y-f(x)$ with $f(x) in \mathbb{Q}[x]$. But we know even more about $f(x)$ it must have the structure $f(x)=\frac{p(x)}{q(x)}$ with $p(x) \in \mathbb{Z}[x]$ and $q(x) \in \mathbb{Z}[x]$ and and $p(x)$ is a divisor of the constant term $-5x^6$ of the polynomial and $q(x)$ is a divisor of the coefficient $2$ of the leading term of the polynomial. So $p(x)$ must be form the set $\{ a x^k, a \in \{\pm 1, \pm 5\}, k \in \{0,1,2,3,4,5\}\}$. Actually $-\frac{x^5}{2}$ is a zero of the polynomial so $2y+x^5$ is a factor and we have $$(2y+x^5)(y^5-5x)$$ Checking with the same method the factor $y^5-5x$ one will see that it has no zero and therefore no linear factors. But maybe it has higher degree factors.

Some details can be found in Factorize the polynomial x3+y3+z3−3xyz. Another example calculated with this method is Factoring multivariate polynomial

share|improve this answer

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.