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
];