# Matijasevic's polynomial

Euler noticed that *x*^{2}+*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(z_{1},z_{2}, ...,z_{k}) with complex coefficients, which takes only primes values at nonnegative integers, must be constant. (The same is true for algebraic functions f(z_{1},z_{2}, ...,z_{k}).)

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-f^{2}]^{2}- [e^{3}(e+2)(a+1)^{2}+1-o^{2}]^{2}- [(a^{2}-1)y^{2}+1-x^{2}]^{2}- [16r^{2}y^{4}(a^{2}-1)+1-u^{2}]^{2}- [((a+u^{2}(u^{2}-a))^{2 }-1)(n+4dy)^{2}+ 1 - (x+cu)^{2}]^{2}- [n+l+v-y]^{2}- [(a^{2}-1)l^{2}+1-m^{2}]^{2}- [ai+k+1-l-i]^{2}- [p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m]^{2}- [q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x]^{2}- [z+pl(a-p)+t(2ap-p^{2}-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^{.}10^{45}
[Matijasevic77]).

**See Also:** FormulasForPrimes

**References:**

- JSWW76
J. P. Jones,D. Sato,H. WadaandD. 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.]