How to perform a complicated change of variables for a polynomial (in Mathematica)

Question

I have an integer polynomial in four variables (w, x, y, and z) that I know can be written as an integer polynomial in these six variables:

• a = w z
• b = x y
• c = w^3 + z^3
• d = x + y
• e = w^3 x + y z^3
• f = w^3 y + x z^3

How can I use Mathematica (or maybe Java) to easily do this change of variables?

Philcox

Tyson Williams, welcome to StackOverflow. – Groyne

@Groyne Thank you. I especially feel welcome because I received such a great answer to my question. – Philcox

Answer 1

Such rewriting can be done by forming a Groebner basis of the replacement polynomials, with respect to a variable order that favors using a-f over w-z. Then use PolynomialReduce with respect to the same order to rewrite your polynomial.

Here is an example. I'll start with replacement rules so I can construct a polynomial such that we know the expected result.

reprules = {a -> w*z, b -> x*y, c -> (w^3 + z^3), 
 d -> (x + y), e -> (w^3*x + y*z^3), f -> (w^3*y + x*z^3)};

Now recast as polynomial relations.

reppolys = Apply[Subtract, reprules, 1];

Here we create an example.

poly = 
 a^2*b + 3*b^2*c^3 - 2*d*e*f + 11*b*f^2 - 5 a*d^2*e /. reprules // Expand

Out[11]= -2*w^6*x^2*y - 2*w^6*x*y^2 + 3*w^9*x^2*y^2 + 11*w^6*x*y^3 - 
  5*w^4*x^3*z - 10*w^4*x^2*y*z - 5*w^4*x*y^2*z + w^2*x*y*z^2 - 2*w^3*x^3*z^3 - 
  2*w^3*x^2*y*z^3 - 2*w^3*x*y^2*z^3 + 22*w^3*x^2*y^2*z^3 + 9*w^6*x^2*y^2*z^3 - 
  2*w^3*y^3*z^3 - 5*w*x^2*y*z^4 - 10*w*x*y^2*z^4 - 5*w*y^3*z^4 -
  2*x^2*y*z^6 + 11*x^3*y*z^6 - 2*x*y^2*z^6 + 9*w^3*x^2*y^2*z^6 + 3*x^2*y^2*z^9

Form the Groebner basis mentioned above.

gb = GroebnerBasis[reppolys, {w, x, y, z, a, b, c, d, e, f}];

Use it to reduce our input to recover the expected result.

PolynomialReduce[poly, 
  gb, {w, x, y, z, a, b, c, d, e, f}][[2]]

Out[12]= a^2*b + 3*b^2*c^3 - 5*a*d^2*e - 2*d*e*f + 11*b*f^2

---edit---

A comment asks about descriptions of Groebner bases. For my own take on the Mathematica functionality, there is an elderly TMJ article. Can be found at

http://library.wolfram.com/infocenter/Articles/2179/

Among the better books related to this topic there is the UTM series text

Ideals, Varieties, and Algorithms by Cox, Lottle, and O'Shea.

An Introduction to Gröbner Bases by Adams and Loustaunau (AMS) is also quite good.

---end edit---

Daniel Lichtblau

Strohben

@Daniel, I have tried on a couple of occasions to understand what exactly is a Groebner basis, but I have failed, thus far. Do you have any links to good/comprehensible descriptions? Thanks. – Rozalin

@Daniel Lichtblau This looks great, but not all examples are working as well as the one you picked. What if poly = a b (a - b)^4? Your transformation returns something much more complicated and Mathematica cannot figure out if the original poly and the final result are the same (that is, Reduce has been running for several minutes now without returning an answer). – Philcox

@ Tyson Williams Could change the variable order to {w, x, y, z, c, d, e, f, a, b}. But there is no general answer in cases where the result will not be unique. You may need to refine what it is you want to obtain e.g a polynomial with certain variables preferred to others, or one of minimal total degree, or maybe some other criterion. Depending on such details, there may (or may not) be a term ordering that will serve your purposes. – Strohben

@Daniel Lichtblau Yes, there is some redundancy that cannot be avoided in my application. Specifically, e + f = c d. Since I start and end with integer polynomials, using CoefficientDomain -> Integers in both GroebnerBasis and PolynomialReduce helps a lot (when the variable ordering is {w, x, y, z, a, b, c, d, e, f}) but not as much as changing the order as you suggested. If my preference of the variables is (a, b, c, d, e, f) (and of course I don't want to see any of w, x, y, or z), in what order should I specify the variables? {w, x, y, z, f, e, d, c, b, a}? – Philcox

By preference I assume you mean 'a' is most favored to appear, and 'f' least favored. In that case yes, reverse a-f in the variable ordering, as the last in the ordering is the most favored to appear in the result, etc. The ordering means favor rewriting higher, that is, earlier listed, in terms of later listed, so this also explains why w-z should be at the front, regardless of their relative order with respect to one another. I had also considered that CoefficientDomain setting but I don't think it will do what you want, at least not in any reliable way. – Strohben