Polynomial rewriting question
Andrew Tamra
rest are constants.
(1) x*z-y*z, (2) x^2*w -2*x*y*w +y^2w + p, (3) 2*s+h+x-y
When we look closely at these, we notice that everywhere x and y
occur, they occur as "x-y". Suppose we let t= x-y, then we can rewrite
the above polynomials as (1) tz (2) t^2*w (3) 2*s+h+t.
How can I do this programmatically? i.e., given the above 3
polynomials and the set of variables as input, the algorithm should
output "x-y" and the 3 rewritten polynomials tz, t^2*w, 2*s+h+t.
Note that the above is an example. When I apply the program to any
arbitrary and large number of polynomials, in place of "x-y" above, I
would like to get the largest polynomial (maximum number of monomial
terms) with as many variables in it as possible.
I posted this in Mathematica forum and learnt that there are no
readily available functions to do this. The problem seemed to be
fairly "simple" and I am hoping someone would suggest a nice algorithm
for this.
Thanks a lot.
Andrew.
Robert Israel
It might or might not be "simple", depending on how you formulate it
precisely, which you haven't done.
Suppose you have a set of polynomials in x and y with coefficients in some
commutative ring (which can include whatever other variables you have). Can
you write them all as polynomials over the same ring in one new variable t
which is defined as a polynomial in x and y?
I'll use D_x and D_y for the partial derivative operators with respect to x
and y. If P(x,y) = f(t(x,y)), then by the Chain Rule
D_x (P(x,y)) = f'(t(x,y)) D_x (t(x,y)) and
D_y (P(x,y)) = f'(t(x,y)) D_y (t(x,y)).
So f'(t(x,y)) is a factor of gcd(D_x P(x,y), D_y P(x,y)), and
t can be reconstructed (up to a constant) from its partial derivatives.
You may have to consider several possible factors.
For example, with your second polynomial P = x^2*w -2*x*y*w +y^2w + p,
gcd(D_x P, D_y P) = 2 w (x - y). If we take f'(t) = 2 w (x-y)
we get D_x t = 1 and D_y t = -1, and thus t = x - y + c_1 for some constant
c_1. Then f'(t) = 2 w (t - c_1); integrate to get
f(t) = w t^2 - 2 w c_1 t + c_2, and compare that to P(x,y)
to get c_2 = p + w c_1^2.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Andrew Tamra
<isr...@math.MyUniversitysInitials.ca> wrote:
Thanks Robert, for your response. Thanks also for rephrasing my
question in very accurate mathematical form. In your response, you
wrote:
"If we take f'(t) = 2 w (x-y) . . . . . f'(t) = 2 w (t - c_1)"
A human mind can see the pattern "x-y" and understand that that if t =
x - y + c_1, then 2 w (x-y) can be rewritten as 2 w (t - c_1). But how
do we do this in an algorithmic way? I am feeling this is like the
original problem itself:
"How do we rewrite a factor of the gcd of 2 partial derivatives of the
original polynomial in terms of some known t(x,y) ?"
Of course, this problem is much better than the original problem,
where t(x,y) itself is not known (for the time being we will disregard
the unknown c_1 constant).
Am I missing something here?
Also want to point out that the original problem sought to find the
set {x,y} as well; Of course this is a minor issue, since one can
write a program that tries all possible combinations of variables and
then get the "largest t(S) and largest set of variables S in it".
Thanks a lot.
robert
> On Jul 8, 6:26 pm,Robert Israel
I think you are missing something. This can all be done
algorithmically. For the
simplest case, in Maple you could try this procedure:
> PolyInT:= proc(P,x,y)
local R, Dxt, Dyt, T;
uses VectorCalculus;
R:= gcd(diff(P,x), diff(P,y));
Dxt:= normal(diff(P,x)/R);
Dyt:= normal(diff(P,y)/R);
SetCoordinates(cartesian[x,y]);
T:= ScalarPotential(VectorField(<Dxt,Dyt>));
factor([simplify(P,{T=t}), t=T]);
end proc;
And then, for example,
> PolyInT(-8-18*x^2+58*y*x-29*y^2-29*x+95*w+11*x^4-44*y*x^3+66*y^2*x^2+22*x^3-44*y^3*x-44*y*x^2+11*y^4+22*x*y^2-49*w*x^2+98*w*y*x-49*w*y^2-49*w*x-47*w^2, x, y);
[-8+95*w-47*w^2+29*t+49*t*w+11*t^2, t = -x^2+2*y*x-x-y^2]