Matijasevic's polynomial (another Prime Pages' Glossary entries)
 Glossary: Prime Pages: Top 5000: The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. 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: FormulasForPrimesReferences: 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, 1995.  New York, NY, 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.] Chris K. Caldwell © 1999-2014 (all rights reserved)