wu :: forums « wu :: forums - Fourth Degree Polynomials » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 4:25pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, Icarus, SMQ, towr, william wu, Grimbal)    Fourth Degree Polynomials « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Fourth Degree Polynomials  (Read 778 times)
Pietro K.C.
Full Member

Gender:
Posts: 213
 Fourth Degree Polynomials   « on: Nov 12th, 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(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.
 « 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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