What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

§1. A FORMULA FOR PRIMES

Many different polynomials that produce primes are now known. They add little to our knowledge of prime numbers; instead, they demonstrate that polynomials can have very strange properties.

In his celebrated address to the 1900 International Congress of Mathematicians, David Hilbert posed 23 problems whose solution he felt would be of the highest importance to the advancement of mathematics. Hilbert’s tenth problem is to find out whether there exists a general method—what we would now call an algorithm—for testing whether a Diophantine equation has a solution. In 1970, following earlier work by Martin Davis, Hilary Putnam, and Julia Robinson, the Russian mathematician Yuri Matijasevic proved that no such “decision algorithm” exists. Because the method effectively uses polynomials as a rather cumbersome “programming language” in which to simulate computer algorithms, the polynomials produced are absolutely enormous. James Jones discovered an explicit system of polynomial equations for which no decision algorithm exists: it comprises 18 equations in 33 variables with maximum degree 5⁶⁰.

An intriguing by-product of Matijasevic’s proof is that there exists a (similarly complicated) polynomial p(x₁,..., x₂₃) in 23 variables, whose positive values, for integer values of the variables, are precisely the primes. In 1976 J. P. Jones, D. Sato, H. Wada, and D. Wiens published a relatively simple polynomial in 26 variables with the same property. Let the variables be denoted a, b, c,..., x, y, z (it is coincidental, but typographically helpful, that the alphabet has 26 letters). Then their polynomial is:

The positive values of this expression, for integer values of a,..., z, are precisely the primes.

There is an apparent paradox: the expression clearly factorizes. Indeed it is of the form (k + 2) {1 – M). However, M is a sum of squares, so the expression is positive if and only if M = 0, and its value is then k + 2. So the polynomial M has to be constructed so that

M(k, other variables) = 0 if and only if k + 2 is prime.

This can be done using Matijasevic’s methods.

This result becomes slightly less intriguing when it becomes apparent that in this context there is nothing very special about the primes. They can be replaced by any “recursively enumerable” sequence of numbers—which means essentially an infinite sequence determined by a finite system of computable conditions—by devising an appropriate polynomial. The thrust of the discovery is that the concept of “computability” can be expressed in the language of polynomials, not that the theory of primes can be simplified by introducing an algebraic formula.