6.7 Hilbert's Tenth Problem


Hilbert's tenth problem

In 1900, David Hilbert challenged mathematicians with a list of 25 major unsolved questions. The tenth of those questions concerned diophantine equations.

A diophantine equation is an equation of the form p = 0 where p is a multivariate polynomial with integer coefficients. The question is whether the equation has any integer solutions.

For example, if the polynomial is 10x2y2 − 86, then there is a solution: x = 3 and y = 2.

It is easy to come up with diophantine equations, such as x2 − 2 = 0, that have no solutions.

Hilbert's tenth problem is to find an algorithm to solve arbitrary diophantine equations (or state that there is no solution), or to prove that no such algorithm exists.


Resolution of Hilbert's tenth problem

In about 1970, 70 years after Hilbert presented his list of problem, a Russian mathematician found the answer: there is no algorithm to solve arbitrary diophantine equations. The problem is uncomputable.

Curiously, if you modify the problem and instead ask for a real-valued solution or a complex-valued solution, there is an algorithm to solve it. Engineers use algorithms that find approximate zeroes of polynomials frequently.