From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: find a positive value for a dificult polynomial Date: 18 Aug 1999 22:18:47 GMT Newsgroups: sci.math.num-analysis Keywords: Find values for the 26-variable integer polynomial yielding primes In article <7ffvoc30ku4k@forum.swarthmore.edu>, manuel wrote: > This a kind of global optimization problem: > >I have a polynomial with 26 variables and degree 25 and I want to find >a positive value when we substitute the 26 variables by non-negative >integers. In article <7pc323$mnu$1@gannett.math.niu.edu>, I followed up with a pointer to the fact that this polynomial (and some proofs...) shows that the set of natural primes is "algebraic", that is, the proposition "n is prime" is equivalent to the first-order statement in Peano arithmetic "There exist natural numbers x_1, ..., x_25 such that 0=P1(n,x)=P2(n,x)=..." which was a celebrated result in mathematical logic three decades ago. (For comparison, the proposition "n is composite" is equivalent to the much simpler first-order statement "There exist natural numbers x1, x2 such that 0 = n - (x1 + 2 )*(x2 + 2)" ) The original poster was curious about actual values of these integers x_i for some prime n. Without turning back to Matijasevich's original papers, I have to say I don't remember any examples, but I will say the x_i are certainly not guaranteed to be small even when n is (indeed, it's provable that they cannot be, in some precise sense). Since this is sci.math.num-analysis and since the original poster did suggest treating this as a non-integral question, I thought I'd take a quick look at the actual polynomials. The positivity of the original function f is equivalent among integers, and is implied whenever k > -2, by the vanishing of 14 polynomials in 26 variables. I didn't work at this very hard, and I didn't find a solution with all variables being positive integers. But I did manage to solve them in _rational numbers_, including 19 positive integers, three other integers, and another positive number. (Only b,d, and g are neither positive nor integer; I did at least get them to be rational though.) Here's how: The variable v can be directly eliminated (v = y-n-l ), reducing the number of variables and equations by 1 each. But that seems contrary to the original situation, so there might be a typo. Until I can dig up the correct equations I'll just let that stand. We can use 7 more equations to solve for the linearly-occuring variables b,g,h,i,s,t,z and substitute into the other 6 equations; this makes j,p,q,w drop out too. This leaves 6 equations in 14 variables. If we can solve them in positive integers, we get a solution to the original problem in rational numbers. Four of the remaining equations now have the form (a variable appearing nowhere else)^2 = (a polynomial in several variable) which we can more or less take as the definitions of m, r, f, and o respectively on the left hand side; another equation is a bit messier (the left side is a more general quadratic in d ) but may be solved for d if its discriminant is a square, so it's more or less of the same flavor. Again, I'm departing from the true spirit of these equations: solving them in integers, or even rational numbers, is rather difficult (this is where the large integer values will come in) although the solutions of these "Pell equations" and "elliptic curves" are quite well studied. But as I say, I'm just solving the poster's "global optimization problem", so I only need the expressions for m^2, r^2, etc. to be positive. When we eliminate m,r,f,o,d in this way, we drop c,l,k,e,n,u too, leaving just one equation also of the last type, namely x^2=..., which we may solve for x in terms of the other variables. (Indeed, this one IS easily solved integrally; it's the Pell equation x^2 - (a^2-1) y^2 = 1 which has solutions such as y=1 and x=a.) Working back from there, I can now produce values of the 26 variables all lying in a suitable extension field of the rationals, either taking the "missing" variables j,p,q,w,c,l,k,e,n,u as ten "parameters" or, as I did with y and a, assigning them some arbitrary values. Let me do the latter (I use a little number theory to choose them to make several of the variables integral). Then I compute these values in turn: y=1 (picked. Note this choice practically forces v =y-n-l to be negative) a=4 (picked) x=4 l=8 (picked) m=31 u=31 (picked) r=2 k=1 (picked -- note original problem requires k+2 prime) i=2 n=244 (picked) f=4801 v= -251 e= -3 (picked -- I don't think I can make both e and o positive integers) o=26 c=29667 (picked -- I didn't try to hard to make d be positive integral) d= -243/4 p=7 (picked) b= -976/29033 q=9 (picked) z= -507 t= 446/3 s=1 j=515 (picked) w=1 (picked) h=1 g= -385/387 I feel compelled to reiterate that the really fascinating part of this polynomial is that there are _positive integer_ solutions for a through z IFF k+2 is prime, so these values are quite boring, requiring little number theory even to make them be rational. The point of this analysis is to show that if really viewed from the perspective of THIS newsgroup, the problem is rather trivial. dave ============================================================================== (k+2)*(1- (w*z+h+j-q)^2- ((g*k+2*g+k+1)*(h+j)+h-z)^2- (2*n+p+q+z-e)^2- (16*(k+1)^3*(k+2)*(n+1)^2+1-f^2)^2- (e^3*(e+2)*(a+1)^2+1-o^2)^2- ((a^2-1)*y^2+1-x^2)^2- (16*r^2*y^4*(a^2-1)+1-u^2)^2- (((a+u^2*(u^2-a))^2-1)*(n+4*d*y)^2+1-(x+c*u)^2)^2- (n+l+v-y)^2- ((a^2-1)*l^2+1-m^2)^2- (a*i+k+1-l-i)^2- (p+l*(a-n-1)+b*(2*a*n+2*a-n^2-2*n-2)-m)^2- (q+y*(a-p-1)+s*(2*a*p+2*a-p^2-2*p-2)-x)^2- (z+p*l*(a-p)+t*(2*a*p-p^2-1)-p*m)^2 ); [ w*z+h+j-q, (g*k+2*g+k+1)*(h+j)+h-z, 2*n+p+q+z-e, 16*(k+1)^3*(k+2)*(n+1)^2+1-f^2, e^3*(e+2)*(a+1)^2+1-o^2, (a^2-1)*y^2+1-x^2, 16*r^2*y^4*(a^2-1)+1-u^2, ((a+u^2*(u^2-a))^2-1)*(n+4*d*y)^2+1-(x+c*u)^2, n+l+v-y, (a^2-1)*l^2+1-m^2, a*i+k+1-l-i, p+l*(a-n-1)+b*(2*a*n+2*a-n^2-2*n-2)-m, q+y*(a-p-1)+s*(2*a*p+2*a-p^2-2*p-2)-x, z+p*l*(a-p)+t*(2*a*p-p^2-1)-p*m ];