Hilbert's tenth problem

Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist.

When all coefficients and variables are restricted to be positive integers, the related problem of polynomial identity testing becomes a decidable (exponentiation-free) variation of Tarski's high school algebra problem, sometimes denoted

[4] Hilbert formulated the problem as follows:[5] 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 in a finite number of operations whether the equation is solvable in rational integers.The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm.

The term "rational integral" simply refers to the integers, positive, negative or zero: 0, ±1, ±2, ... .

In these terms, Hilbert's tenth problem asks whether there is an algorithm to determine if the Diophantine set corresponding to an arbitrary polynomial is non-empty.

However, the two problems are equivalent: any general algorithm that can decide whether a given Diophantine equation has an integer solution could be modified into an algorithm that decides whether a given Diophantine equation has a natural-number solution, and vice versa.

It was the development of computability theory (also known as recursion theory) that provided a precise explication of the intuitive notion of algorithmic computability, thus making the notion of recursive enumerability perfectly rigorous.

The unsolvability of Hilbert's tenth problem is a consequence of the surprising fact that the converse is true: Every recursively enumerable set is Diophantine.This result is variously known as Matiyasevich's theorem (because he provided the crucial step that completed the proof) and the MRDP theorem (for Yuri Matiyasevich, Julia Robinson, Martin Davis, and Hilary Putnam).

Because there exists a recursively enumerable set that is not computable, the unsolvability of Hilbert's tenth problem is an immediate consequence.

Purely formally, it is only the bounded universal quantifier that stands in the way of this being a definition of a Diophantine set.

Because the recursively enumerable sets also are not closed under complementation, he conjectures that the two classes are identical.

Using properties of the Pell equation, she proves that J.R. implies that EXP is Diophantine, as well as the binomial coefficients, the factorial, and the primes.

, then it suffices to set So, for example, there is a polynomial for which the positive part of its range is exactly the prime numbers.

[c] The Matiyasevich/MRDP theorem implies that each such proposition is equivalent to a statement that asserts that some particular Diophantine equation has no solutions in natural numbers.

In addition the assertion that particular formal systems such as Peano arithmetic or ZFC are consistent can be expressed as

sentences have the special property that if they are false, that fact will be provable in any of the usual formal systems.

with any of the usual formal systems such as Peano arithmetic or ZFC by letting it systematically generate consequences of the axioms and then output a number

Then the theorem tells us that either a false statement of this form is proved or a true one remains unproved in the system in question.

Similarly, we can call the dimension of such a set the fewest unknowns in a defining equation.

Julia Robinson and Yuri Matiyasevich showed that every Diophantine set has dimension no greater than 13.

[e] So, in particular, there is no algorithm for testing Diophantine equations with 9 or fewer unknowns for solvability in natural numbers.

For the case of rational integer solutions (as Hilbert had originally posed it), the 4-squares trick shows that there is no algorithm for equations with no more than 36 unknowns.

But Zhi Wei Sun showed that the problem for integers is unsolvable even for equations with no more than 11 unknowns.

Martin Davis studied algorithmic questions involving the number of solutions of a Diophantine equation.

Davis proved that there is no algorithm to test a given Diophantine equation to determine whether the number of its solutions is a member of the set

Thus there is no algorithm to determine whether the number of solutions of a Diophantine equation is finite, odd, a perfect square, a prime, etc.

There has been much work on Hilbert's tenth problem for the rings of integers of algebraic number fields.

Basing themselves on earlier work by Jan Denef and Leonard Lipschitz and using class field theory, Harold N. Shapiro and Alexandra Shlapentokh were able to prove: Hilbert's tenth problem is unsolvable for the ring of integers of any algebraic number field whose Galois group over the rationals is abelian.Shlapentokh and Thanases Pheidas (independently of one another) obtained the same result for algebraic number fields admitting exactly one pair of complex conjugate embeddings.

The problem for the ring of integers of algebraic number fields other than those covered by the results above remains open.

Barry Mazur has conjectured that for any variety over the rationals, the topological closure over the reals of the set of solutions has only finitely many components.