wu :: forums
wu :: forums - Fourth Degree Polynomials

Welcome, Guest. Please Login or Register.
Apr 18th, 2024, 2:45pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   putnam exam (pure math)
(Moderators: william wu, Grimbal, Eigenray, towr, Icarus, SMQ)
   Fourth Degree Polynomials
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Fourth Degree Polynomials  (Read 815 times)
Pietro K.C.
Full Member

115936899 115936899    

Gender: male
Posts: 213
Fourth Degree Polynomials  
« on: Nov 12th, 2002, 3:35pm »
Quote Quote Modify 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/200Cool

   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! Smiley
   By the way, VERY cool problem. Much unlike most things I'd encountered previously.
« Last Edit: May 21st, 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)
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board