|
||
|
Title: Fourth Degree Polynomials Post by Pietro K.C. on Nov 12th, 2002, 3:35pm Someone has claimed to have discovered an algorithm that determines which polynomial equations of total degree 4 in arbitrarily many variables with integer coefficients have integer solutions. Show how it could be used to determine which polynomial equations of arbitrary degree in arbitrarily many variables with integer coefficients have integer solutions. (modified post in order to reproduce problem statement at top - willywutang 5/21/2008) Hmmm, I think I've done it, but it wasn't so hard. Wasn't anyone else interested? My solution is as follows. Suppose you are given a polynomial equation P(x1, ... , xN) = P(X) = 0. An arbitrary term of that equation will be of the form Ca1...aN*x1a1...xNaN, where Ca1...aN is a constant. Now we turn each product x1a1...xNaN into a new variable, ua1...aN. Surely, if P(X) has integer roots, then so does the new P(U), because a product of integers is still an integer. But not vice-versa, one might say! And one would indeed be correct. We need some way of insuring that the values we attribute to each ua1...aN is indeed the product of the corresponding powers of xi's. So it is time for a little digression. Fear not, it is indeed little. It is just to state the following result: a system of equations f1(x) = g1(x) ... fm(x) = gm(x), in the reals, is equivalent to the single equation (f1(x) - g1(x))2 + ... + (fm(x) - gm(x))2 = 0. Not the most challenging result to grasp. By now it should be clear what we are about to do. In addition to the substitution X -> U indicated above, we append a system of equations corresponding to each ua1...aN, one that expresses, in a stepwise fashion, that ua1...aN is the product of some of the xi. We do this in the following way. For every ua1...aN (with the indices varying between 0...0 and the maximum values that each attains in the polynomial P(X)), let aJ be its smallest nonzero index. Then we append the equations ua1...aJ...aN = xJ*ua1...(aJ-1)...aN u0...0 = 1 to the system. It is clear that the whole set of these equations is enough to insure the consistency we require. In other words, this system will have integer solutions if and only if P(X) does, and they will be the same. It remains to be shown how to express this simultaneous system of equations as a fourth-degree polynomial. But this part is easy! From the above mentioned lemma, we can conver this system into a sum of squares. And, since there is one equation of the form SUM Ca1...aN*ua1...aN = 0, while the others are merely z = xy, we will have something of degree not exceeding 4. Because the square of the first equation will yield a polynomial of degree 2; while every equation of the second type will yield (x-yz)2 = x2 - 2xyz + y2z2, which is of degree exactly four! At last we uncover the reason for the strange given data. So there we have it, we've used the odd fourth-degree algorithm to solve an equation in arbitrarily many variables, of arbitrary degree. Yay! :) By the way, VERY cool problem. Much unlike most things I'd encountered previously. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |