# 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]).