Author 
Topic: Fourth Degree Polynomials (Read 815 times) 

Pietro K.C.
Full Member
Gender:
Posts: 213


Fourth Degree Polynomials
« on: Nov 12^{th}, 2002, 3:35pm » 
Quote Modify

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/200 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(x_{1}, ... , x_{N}) = P(X) = 0. An arbitrary term of that equation will be of the form C_{a1...aN}*x_{1}^{a1}...x_{N}^{aN}, where C_{a1...aN} is a constant. Now we turn each product x_{1}^{a1}...x_{N}^{aN} into a new variable, u_{a1...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 viceversa, one might say! And one would indeed be correct. We need some way of insuring that the values we attribute to each u_{a1...aN} is indeed the product of the corresponding powers of x_{i}'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 f_{1}(x) = g_{1}(x) ... f_{m}(x) = g_{m}(x), in the reals, is equivalent to the single equation (f_{1}(x)  g_{1}(x))^{2} + ... + (f_{m}(x)  g_{m}(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 u_{a1...aN}, one that expresses, in a stepwise fashion, that u_{a1...aN} is the product of some of the x_{i}. We do this in the following way. For every u_{a1...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 u_{a1...aJ...aN} = x_{J}*u_{a1...(aJ1)...aN} u_{0...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 fourthdegree 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 C_{a1...aN}*u_{a1...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 (xyz)^{2} = x^{2}  2xyz + y^{2}z^{2}, 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 fourthdegree 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.

« Last Edit: May 21^{st}, 2008, 3:08pm by william wu » 
IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



