I wish to simplify multivariate rational fractions to a canonical form.

Thanks to some very helpful mathematically inclined people who verified that my understanding of Wikipedia was correct, I'm now confident that:

  1. GCD of multivariate polynomials over a UFD is unique up to the multiplication by a unit of the UFD.
  2. Multivariate rational fractions over a UFD have a simplified form that is unique up to the multiplication of the numerator and denominator by a unit of the UFD. By requiring that the denominator is a primitive polynomial, it can be made unique up to the multiplication of the numerator and denominator by -1. By also fixing the monomial order and fixing the sign of a leading monomial, it can be made completely unique.
  3. While multivariate polynomial division over a UFD is not unique in general, it's unique if there's no remainder.

As far as I can see, it follows that the unique simplified form for multivariate rational fractions can be acquired the same way as for univariate rational fractions: By dividing the numerator and denominator by their GCD. (And fiddling with the result a bit)

The question then becomes: How to calculate multivariate polynomial GCD, and division when there's no remainder? (In a conceptually simple way, without having to resort to Gröbner bases)

From Wikipedia:

A polynomial in n variables may be considered as a univariate polynomial over the ring of polynomials in (n − 1) variables. Thus a recursion on the number of variables shows that if GCDs exists and may be computed in R, then they exist and may be computed in every multivariate polynomial ring over R. In particular, if R is either the ring of the integers or a field, then GCDs exist in R[x1,...,xn], and what precedes provides an algorithm to compute them.

Does this mean that the multivariate polynomial GCD can be calculated with Euclid's algorithm? Euclid's algorithm uses Euclidean division; Does this mean you can use it with multivariate polynomials by thinking of them as univariate polynomials over polynomials with (n - 1) variables? Does this give the correct answer in general when used in Euclid's algorithm and also in cases when there's no remainder?

As far as I can see, you'll end up with rational fractions as the coefficients when you do the division of the leading coefficients in Euclidean division (and recurse to the next level of polynomials to simplify the fraction), but at the end you can multiply the numerator and denominator at each level by the LCM of the denominators of the terms' coefficients so that you'll be left with a rational fraction only at the outermost level. Is there something wrong with this? Is there a simpler way to do this?

And finally: Although the approach of recursion on the number of variables is conceptually simple (assuming it works in general), dealing with levels upon levels of rational fractions isn't going to be fun. Does there exist an algorithm that can be used to do the division directly with multivariate polynomials, that gives the correct answer in general? (ie. the remainders it gives work for Euclid's algorithm and it gives the correct answer when there's no remainder)

One way I've considered is using the univariate algorithm with lexicographical monomial ordering and allowing negative exponents during the algorithm, then at the end multiplying the numerator and denominator by such a monomial that all the exponents become non-negative. Could this work?

Explicit counter-examples would be very much appreciated if there's a mistake somewhere; As someone else once so eloquently put it, "I'm not a mathematician, so please type slowly :-)"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.