Algorithm to simplify division of two multivariate polynomials

Question

I'm looking for al algorithm to try to implement simplification of a fraction of two multivariate polynomials. Here's an example of one:

$$\frac{(3xy^2+x^2y^2+7yx^2+21xy+2y^2+12x^2+14y+36x+24) }{(4xy^2+x^2y^2+6yx^2+24xy+3y^2+8x^2+18y+32x+24)}$$

This can be simplified to:

$$\frac{(xy+3x+2y+6) }{(xy+2x+3y+6)}$$

Because the shared factors of the numerator and denominator in the example are $(x+1)$ and $(y+4)$, in other words the gcd is $(xy + y + 4x + 4)$.

So the numerator and denominoator can both be divided through $(xy + y + 4x + 4)$ to get the above simplified form.

Of course I constructed this example myself by on purpose multiplying $(x+1)$, $(y+4)$ and other such factors together to create the numerator and denominator with the shared factors in there on purpose. But I'd like to find the simplification for arbitrary multivariate polynomials with an algorithm.

This is just an example, I'd also like it to support more variables, higher powers than the 2 in this example, etc..., any random polynomials you could type, if they happen to have a gcd, simplify it. Also, the coefficients can be any complex numbers, doesn't have to be restricted to integers.

But to implement this as an algorithm requires two things:

1. find the $\gcd$ of two multivariate polynomials

2. implement division (with remainder that's know to be zero, so we don't need to support getting the remainder) of the numerator, and denominator, through this gcd, to get the simplified result.

When I search for how to do the $\gcd$ and especially division of multivariate polynomials, the answer points to using groebner basis, but I've not found anything that says how to actually do the division of two multivariate polynomials with groebner basis.

If I try it in wolfram alpha, and if I type in there the two involved polynomials of the example:

groebnerbasis[{3*x*y^2+x^2*y^2+7*y*x^2+21*x*y+2*y^2+12*x^2+14*y+36*x+24,4*x*y^2+x^2*y^2+6*y*x^2+24*x*y+3*y^2+8*x^2+18*y+32*x+24},{x,y}]

It outputs:

{x y^3 + 9 x y^2 + 26 x y + 24 x + y^3 + 9 y^2 + 26 y + 24, x^2 y + 4 x^2 - x y^2 - 3 x y + 4 x - y^2 - 4 y}

So it outputs two polynomials:

1. $xy^3 + 9xy^2 + 26xy + 24x + y^3 + 9y^2 + 26y + 24$

2. $x^2y + 4x^2 - xy^2 - 3xy + 4x - y^2 - 4y$

And neither of these two polynomials looks either like the gcd $(xy + y + 4x + 4)$, nor like the simplified result of $(xy+3x+2y+6) / (xy+2x+3y+6)$.

So how can I use this groebner basis for the desired purpose? Does this bring one any closer to the desired solution of simplifying the two input polynomials? Is there an algorithm that operates on this groebner basis result?

What's the correct algorithm to look for (with or without groebner basis) to do the gcd, and divisions with known remainder zero, to do what I want?

Also, separate from that, I have a few questions about groebner basis too:

1. most examples involving polynomial division and groebner basis (including other questions here on stackoverflow, and wikipedia), is dividing a polynomial through multiple polynomials at the same time. Why this focus on dividing through multiple polynomials? That seems to be for a different application than my simplification example above, why is dividing though multiple polynomials so common and dividing through a single one not findable in any examples?

2. the term "ideal" and "generator" come up all the time in information about the groebner basis. In my example above with the two big polynomials getting divided and simplified, what are the ideal and generator there exactly, or is this not relevant here?

3. I saw some explanation on groebner basis that said there'd always be one polynomial in them with only one variable. Is that correct? In the wolfram alpha above, both have x and y in it. What could have gone wrong here?

Thanks!

Answer 1

If $R$ is the polynomial ring, and $p, q \in R$ are the polynomials in question, then consider the morphism of $R$-modules $R^2 \to R$ defined by $e_1 \mapsto p$, $e_2 \mapsto q$. Then the kernel of this morphism will be generated by $(-q/g, p/g)$ where $g = \gcd(p, q)$ in the UFD $R$. From this, it will be trivial to extract $p/g$ and $q/g$ which are the numerator and denominator of $p/q$ in lowest terms. The calculation of this kernel, in turn, can be done using Groebner bases.

For the example from one of the comments, I used this sequence of commands in Singular:

ring R=QQ,(x,y,z),(c,lp);
module M=[6yx6+6zx5+15yx4+5xy2+5yz+18x9,1,0],[2xyz+6zx4+yx4+zx3+3x7+2z2,0,1];
groebner(M);
==>
_[1]=[0,x3+2z,-6x5-5y]
_[2]=[375x4y3-20736x4z5+125xy4-6912xyz5+125y3z-6912z6,60x2yz-288xz3+25y2,-360x4yz+1728x3z3-150x2y2+720xyz2-3456z4]
_[3]=[864x5z3+75x4y2+288x2yz3+25xy3+288xz4+25y2z,12x2z+5y,-72x4z-30x2y+144xz2]
_[4]=[15x5y+72x4z2+5x2y2+24xyz2+5xyz+24z3,x,-6x3+12z]
_[5]=[36x6z-15x4y+12x3yz+12x2z2-5xy2-5yz,-1,6x2]
_[6]=[3x7+x4y+6x4z+x3z+2xyz+2z2,0,1]

Here, you can read off the kernel from the first entry (in more general situations with more generators, the kernel could be read off from the entries with 0 in the first coordinate(s)).

Of course, as you can see, the intermediate calculation could potentially end up being fairly expensive in larger examples with higher degree and/or more variables. I'm not sure whether there's a more efficient way to do the calculation.

Answer 2

Here is a different approach which does not require Groebner bases.

As an analogy, let us think of how we would calculate the gcd of two polynomials in $\mathbb{Z}[x]$, which is also not a UFD. The procedure here would be: first, treat the two polynomials as polynomials in $\mathbb{Q}[x]$, and use the Euclidean algorithm to find the gcd in $\mathbb{Q}[x]$. This will possibly have some denominators; however, then you can reduce all the coefficients to fractions in lowest terms, and then calculate the lcm of all the denominators, and finally multiply through by that lcm.

By an argument along the lines of Gauss' lemma and the proof that $R$ being a UFD implies $R[x]$ is a UFD, then, the gcd of the two original polynomials in $\mathbb{Z}[x]$ will be this polynomial, times the gcd in $\mathbb{Z}$ of all the coefficients of the two original polynomials.

In fact, this same calculation will work for any UFD in place of $\mathbb{Z}$. In the case of multivariate polynomials $f, g \in F[x_1, \ldots, x_n]$ for some field $F$, the resulting algorithm will look like:

• Use the Euclidean algorithm to calculate $\gcd(f, g)$ in $F(x_1, \ldots, x_{n-1}) [x_n]$.
• Recursively use the gcd algorithm for $F[x_1, \ldots, x_{n-1}]$ to reduce each coefficient of this gcd to lowest terms; find the lcm of the denominators; and multiply through by this lcm.
• Recursively use the gcd algorithm for $F[x_1, \ldots, x_{n-1}]$ to find the gcd of all coefficients of $f$ and $g$ in $F[x_1, \ldots, x_{n-1}]$.
• Multiply the results of the previous two steps.

(Note that the second step above does require some exact division of polynomials in $F[x_1, \ldots, x_n]$. This can be done via the reduction algorithm which is mentioned in a comment by dxiv: https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis#Reduction .)