Hilbert's 23 Problems (#10)

Definition: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.

What this basically says is that is there a way for us to give a boolean answer to whether any such equation is solvable or not without necessarily knowing the solution?

The answer turns out to be no. Get the book Hilbert's Tenth Problem by Yuri V. Matiyasevich to understand why.

Although I've started reading this book, I must say that it is a little above my level of understanding. I've already read the first chapter twice just to get some basic understanding of his definitions. However, the commentary at the end of Chapter 3 was absolutely remarkable.

In my number theory and abstract algebra classes in college (university doesn't have that nice ring to it), we learned that there does not exist any polynomial that returns only primes for all integer arguments, but rather only for some (Euler's $f(x) = x^2 + x + 41$).

Julia Robinson proved in 1952 that the binomial coefficients and the factorial are exponential Diophantine, and gave an exponential Diophantine representation for the set of all prime numbers. In 1960, Putnam noted that a Diophantine set is the positive part of the range of a polynomial. Thus, it became clear (to someone) that if exponentiation were established to be Diophantine, it would become possible to construct a polynomial such that the positive values it assumed would coincide precisely with the prime numbers. In 1971a, Matiyasevich gave the first upper bound of 24 variables in his Russian article, which was later reduced to 21 in the appendix of the English translation.

In 1976, Jones, Sato, Wada and Wiens exhibited the following polynomial:

$(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$ - $[n + l + v - y]^2$ - $[((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2]^2$ - $[(a^2 - 1)t^2 + 1 - m^2]^2$ - $[q + y(a - p -1) + s(2ap + 2a - p^2 - 2p - 2) - x]^2$ - $[z + pl(a - p) + t(2ap - p^2 - 1) - p\m]^2$ - $[ai + k + 1 - l -i]^2$ - $[p + l(a - n - 1) + b(2an +2a - n^2 - 2n - 2) - m]^2\}$

This polynomial contains 26 variables (all the letters of the English alphabet), and the set of its positive values is exactly the set of all prime numbers. Note: The polynomial written above, representing only primes, is itself the product of two polynomials.

Later, the bound was further reduced to 12 variables by Wada in 1975, and by Jones, Sato, Wada and Wiens in 1976. Currently, the record is at 10 variables, achieved by Matiyasevich in 1977a.