Matijasevic's polynomial
Euler noticed that x2+x+41 takes on prime values for x = 0,1,2,3, ... , 39; so many have asked if it is possible to have a polynomial which produces only prime values. Sadly, it is easy to show that this is not the case (unless the polynomial is constant):
Theorem: A polynomial P(z1,z2, ..., zk) with complex coefficients, which takes only primes values at nonnegative integers, must be constant. (The same is true for algebraic functions f(z1,z2, ..., zk).)
There are several tacks we could take from here. We could ask what is the most primes we can get out of a given type of polynomial (e.g., a quadratic in one variable)? We will do that on another page (or see [Ribenboim95 chapter 3]). Another approach might be to ask if there is a non-constant polynomial all of whose positive values (as the variables range in the set of non-negative integers) are all primes. Matijasevic showed this was possible in 1971 [Matijasevic71], and in 1976 Jones, Sato, Wada and Wiens gave the following explicit example of such a polynomial with 26 variables (and degree 25).
(k+2){1 - [wz+h+j-q]2 - [(gk+2g+k+1)(h+j)+h-z]2 - [2n+p+q+z-e]2 - [16(k+1)3(k+2)(n+1)2+1-f2]2 - [e3(e+2)(a+1)2+1-o2]2 - [(a2-1)y2+1-x2]2 - [16r2y4(a2-1)+1-u2]2 - [((a+u2(u2-a))2 -1)(n+4dy)2 + 1 - (x+cu)2]2 - [n+l+v-y]2 - [(a2-1)l2+1-m2]2 - [ai+k+1-l-i]2 - [p+l(a-n-1)+b(2an+2a-n2-2n-2)-m]2 - [q+y(a-p-1)+s(2ap+2a-p2-2p-2)-x]2 - [z+pl(a-p)+t(2ap-p2-1)-pm]2}
Notice that this polynomial factors! Look at the special form of the second part: it is one minus a sum of squares, so the only way for it to be positive is for each of the squared terms to be zero (this is a trick of Putnam's).
Challenge: Can you find a values (a,b,c,d,...,z) (all non-negative) for which the polynomial above is positive?
The record for the lowest degree of such a polynomial is 5 (with 42 variables [JSWW76]), and the record for fewest variables is 10 (with degree about 1.6.1045 [Matijasevic77]).
See Also: FormulasForPrimes
References:
- JSWW76
- J. P. Jones, D. Sato, H. Wada and D. Wiens, "Diophantine representation of the set of prime numbers," Amer. Math. Monthly, 83 (1976) 449-464. MR 54:2615
- Matijasevic71
- Y. V.Matijasevic, "A Diophantine representation of the set of prime numbers (in Russian)," Dokl. Akad. Nauk SSSR, 196 (1971) 770--773. English translation by R. N. Goss, in Soviet Math. Dokl., 12, 1971, 249-254.. MR 43:1921
- Matijasevic77
- Y. V. Matijasevic, "Primes are enumerated by a polynomial in 10 variables (in Russian)," Zapiski Sem. Leningrad Mat. Inst. Steklov, 68 (1977) 62--82, 144--145. English translation by L. Guy and J. P. Jones, J. Soviet Math., 15, 1981, 33--44.. MR 58:21534
- Ribenboim95
- P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995. pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]