How to divide polynomials with multiple variables ? More precisely, let f be a polynomial of the form :
$f= \sum_{p1=0}^{n1} \sum_{p2=0}^{n2} \sum_{p3=0}^{n3} a_{p1,p2,p3}.x^{p1}.y^{p2}.z^{p3} = \prod_{j=1}^n (1+x^{a_j}.y^{b_j}.z^{c_j})$
where the exponents $a, b$ and $c$ are vectors of strictly positive integers,
and g is given by
$g= (1+x^{a_i}.y^{b_i}.z^{c_i})$
I am looking for expressing the quotient $q=f/g$ using only $a_{p1,p2,p3}$.
I was able to divide polynomials similar to $f$ with unique variable using synthetic division. Can synthetic division be used to divide polynomials with more than one variable?
Thanks.
Best Answer
In general, synthetic division in multiple variables is not well defined since the notion of remainder is not unique. In Gröbner basis theory, one defines for that purpose a "monomial order" that then allows to reduce multivariate polynomials like univariate polynomials and to determine minimal generating sets for ideals.
If one knows the remainder, which is zero here, and the final degree structure, as in this case, one can use one of Schönhages tricks, division by multiplication. To divide $f$ by $g=1+x^ay^bz^c$, multiply successively f by $1-x^ay^bz^c$, $1+(x^ay^bz^c)^2$, $1+(x^ay^bz^c)^4$, $1+(x^ay^bz^c)^8$ etc. until the degree of $(x^ay^bz^c)^{2^k}$ is outside of the degree range of the quotient. Then the lower degree terms of this product form the quotient.