# Factoring a trivariate polynomial

I would appreciate some help with factoring a trivariate polynomial.

The polynomial in question is

$$p(x,y,z)=a_1 x^7+a_2 x^5y+a_3 x^3y^2+a_4 xy^3+a_5 x^4z+a_6 x^2yz+a_7 y^2z+a_8 xz^2,$$

where the coefficients are integers. I would like to assign values to these coefficients such that $p$ can be factored. For example, one possible factorization might be

$$p(x,y,z)=(x^3+b_1 xy+b_2 z)(b_3 x^4+b_4 x^2y+b_5 xz+b_6 y^2).$$

One can expand this factorization and equate the coefficients of the expansion with those of the above equation and hope that the system of equations can be solved for integers b's.

How can one find other possible factorizations? Is there an easy way?

-

Let us suppose first that all the coefficients in your polynomial $p$ are non-zero.

Consider the set of vectors of $\mathbb R^3$ given by the rows of the following matrix: $$\left( \begin{array}{ccc} 7 & 0 & 0 \\ 5 & 1 & 0 \\ 3 & 2 & 0 \\ 1 & 3 & 0 \\ 4 & 0 & 1 \\ 2 & 1 & 1 \\ 0 & 2 & 1 \\ 1 & 0 & 2 \end{array} \right)$$ which comes from the exponents which appear in the monomials in you polynomial $p$. All of them satisfy the equation $$(\Pi)\qquad\qquad x+2y+3z=7,$$ and this tells us that the convex hull of those eight points is actually a polygon contained in a plane. To be able to make pictures more easily, I will project down to one of the coordinate planes: the projection $\phi:\mathbb R^3\to \mathbb R^2$ on the last two coordinates is injective and affine on that plane (and «it corresponds to looking at $\mathbb R^3$ from above»). The image of our points under this projections are, of course, the rows of $$\left( \begin{array}{ccc} 0 & 0 \\ 1 & 0 \\ 2 & 0 \\ 3 & 0 \\ 0 & 1 \\ 1 & 1 \\ 2 & 1 \\ 0 & 2 \end{array} \right)$$ and the convex hull $P_p$ of these in the plane is the following polygon:

We can clearly do this construction from any polynomial $f$ whose exponent vectors lie on a plane parallel to $\Pi$ to obtain a polygon $P_f$.

Suppose now that $p=gh$ is a factorization of your polynomial. An easy consequence of the way polynomials are multiplied implies

Lemma. The exponent vectors of $g$ lie on a plane parallel to $\Pi$ and the same, of course, applies to $h$.

We therefore have two polygons $P_g$ and $P_h$. Now the key observation:

Lemma. We have $P_p=P_g+P_h$.

Here the sum is the so-called Minkowski sum of subsets of the plane.

This last lemma imposes very severe limitations on the shape of the polynomials $g$ and $h$ which can appear in a factorization of $p$.

Indeed, a little thinking will give you the list of all possible pairs of polygons $(A,B)$ whose vertices are points of the plane with non-negative integer coordinates and such that $P_p=A+B$. For each such pair, you get the form of the factos of a possible factorization of $p$.

Now, the factorization you proposed corresponds to the pair of polygons

and in fact this is the only decomposition of $P_p$ as a Minkowski sum (to see this, consider for example the possible heights and widths of the two summands, &c). It follows that assuming the coefficients of $x^7$, $xy^3$, $y^2z$ and $xz^2$ are non-zero, any possible factorization has the shape you found. If one of those coefficients vanishes, then the shape of $P_p$ would be different, and one has to consider more cases—notice that the vanishing of the coefficient of $x^3yz$ does not matter, if the other coefficients are non-zero, because it is in the interior of our polygon.

N.B.: It is easy to see that the polygons corresponding to the shapes of the two factors you found cannot be written as a Minkowski sum. From this it follows that (assuming their coefficients corresponding to the vertices of those polygons do not vanish—and in fact they can't if the same holds for $p$) the two factors you have found are irreducible.

-
There are several details missing before this can be considered an explanation... but hopefully the idea gets through :D –  Mariano Suárez-Alvarez Feb 1 '12 at 7:45
A keyword to find information of this type of construction is Newton polytopes. –  Mariano Suárez-Alvarez Feb 1 '12 at 7:48