Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation (a polynomial equation with integer coefficients and a finite number of unknowns), can decide whether the equation has a solution with all unknowns taking integer values.

For example, the Diophantine equation ${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$ has an integer solution: ${\displaystyle x=1,\ y=2,\ z=-2}$. By contrast, the Diophantine equation ${\displaystyle x^{2}+y^{2}+1=0}$ has no such solution.

Hilbert's tenth problem has been solved, and it has a negative answer: such a general algorithm cannot exist. This is the result of combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson that spans 21 years, with Matiyasevich completing the theorem in 1970.^[1] The theorem is now known as Matiyasevich's theorem or the MRDP theorem (an initialism for the surnames of the four principal contributors to its solution).

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 ${\displaystyle {\overline {HSI}}.}$^[2]

Background

Original formulation

Hilbert formulated the problem as follows:^[3]

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, ... . So Hilbert was asking for a general algorithm to decide whether a given polynomial Diophantine equation with integer coefficients has a solution in integers.

Hilbert's problem is not concerned with finding the solutions. It only asks whether, in general, we can decide whether one or more solutions exist. The answer to this question is negative, in the sense that no "process can be devised" for answering that question. In modern terms, Hilbert's 10th problem is an undecidable problem.

Diophantine sets

In a Diophantine equation, there are two kinds of variables: the parameters and the unknowns. The Diophantine set consists of the parameter assignments for which the Diophantine equation is solvable. A typical example is the linear Diophantine equation in two unknowns,

${\displaystyle a_{1}x+a_{2}y=a_{3}}$,

where the equation is solvable if and only if the greatest common divisor ${\displaystyle \gcd(a_{1},a_{2})}$ evenly divides ${\displaystyle a_{3}}$. The set of all ordered triples ${\displaystyle (a_{1},a_{2},a_{3})}$ satisfying this restriction is called the Diophantine set defined by ${\displaystyle a_{1}x+a_{2}y=a_{3}}$. 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.

The problem is generally understood in terms of the natural numbers (that is, the non-negative integers) rather than arbitrary integers. 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. By Lagrange's four-square theorem, every natural number is the sum of the squares of four integers, so we could rewrite every natural-valued parameter in terms of the sum of the squares of four new integer-valued parameters. Similarly, since every integer is the difference of two natural numbers, we could rewrite every integer parameter as the difference of two natural parameters.^[4] Furthermore, we can always rewrite a system of simultaneous equations ${\displaystyle p_{1}=0,\ldots ,p_{k}=0}$ (where each ${\displaystyle p_{i}}$ is a polynomial) as a single equation ${\displaystyle p_{1}^{\,2}+\cdots +p_{k}^{\,2}=0}$.

Recursively enumerable sets

A recursively enumerable set can be characterized as one for which there exists an algorithm that will ultimately halt when a member of the set is provided as input, but may continue indefinitely when the input is a non-member. 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. It is evident that Diophantine sets are recursively enumerable (also known as semi-decidable). This is because one can arrange all possible tuples of values of the unknowns in a sequence and then, for a given value of the parameter(s), test these tuples, one after another, to see whether they are solutions of the corresponding equation. 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. In fact, more can be said: there is a polynomial

${\displaystyle p(a,x_{1},\ldots ,x_{n})}$

with integer coefficients such that the set of values of ${\displaystyle a}$ for which the equation

${\displaystyle p(a,x_{1},\ldots ,x_{n})=0}$

has solutions in natural numbers is not computable. So, not only is there no general algorithm for testing Diophantine equations for solvability, even for this one parameter family of equations, there is no algorithm.

History

Year	Events
1944	Emil Leon Post declares that Hilbert's tenth problem "begs for an unsolvability proof".
1949	Martin Davis uses Kurt Gödel's method for applying the Chinese remainder theorem as a coding trick to obtain his normal form for recursively enumerable sets: ${\displaystyle \left\{a\mid \exists y\forall k\leqslant y\exists x_{1},\ldots ,x_{n}:p\left(a,k,y,x_{1},\ldots ,x_{n}\right)=0\right\}}$ where ${\displaystyle p}$ is a polynomial with integer coefficients. Purely formally, it is only the bounded universal quantifier that stands in the way of this being a definition of a Diophantine set. Using a non-constructive but easy proof, he derives as a corollary to this normal form that the set of Diophantine sets is not closed under complementation, by showing that there exists a Diophantine set whose complement is not Diophantine. Because the recursively enumerable sets also are not closed under complementation, he conjectures that the two classes are identical.
1950	Julia Robinson, unaware of Davis's work, investigates the connection of the exponential function to the problem, and attempts to prove that EXP, the set of triplets ${\displaystyle (a,b,c)}$ for which ${\displaystyle a=b^{c}}$, is Diophantine. Not succeeding, she makes the following hypothesis (later called J.R.): There is a Diophantine set ${\displaystyle D}$ of pairs ${\displaystyle (a,b)}$ such that ${\displaystyle (a,b)\in D\Rightarrow b<a^{a}}$ and for every positive ${\displaystyle k,}$ there exists ${\displaystyle (a,b)\in D}$ such that ${\displaystyle b>a^{k}.}$ 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.
1959	Working together, Davis and Putnam study exponential Diophantine sets: sets definable by Diophantine equations in which some of the exponents may be unknowns. Using the Davis normal form together with Robinson's methods, and assuming the then unproved conjecture that there are arbitrarily long arithmetic progressions consisting of prime numbers, they prove that every recursively enumerable set is exponential Diophantine. They also prove as a corollary that J.R. implies that every recursively enumerable set is Diophantine, which in turn implies that Hilbert's tenth problem is unsolvable.
1960	Robinson simplifies the proof of the conditional result for exponential Diophantine sets and makes it independent from the conjecture about primes and thus a formal theorem. This makes the J.R. hypothesis a sufficient condition for the unsolvability of Hilbert's tenth problem. However, many doubt that J.R. is true.[5]
1961–1969	During this period, Davis and Putnam find various propositions that imply J.R., and Robinson, having previously shown that J.R. implies that the set of primes is a Diophantine set, proves that this is an if and only if condition. Yuri Matiyasevich publishes some reductions of Hilbert's tenth problem.
1970	Drawing from the recently published work of Nikolai Vorob'ev on Fibonacci numbers,[6] Matiyasevich proves that the set ${\displaystyle P=\{(a,b)|a>0,b=F_{2a}\},}$ where ${\displaystyle F_{n}}$ is the nth Fibonacci number, is Diophantine and exhibits exponential growth.[7] This proves the J.R. hypothesis, which by then had been an open question for 20 years. Combining J.R. with the theorem that every recursively enumerable set is exponential Diophantine, proves that recursively enumerable sets are Diophantine. This makes Hilbert's tenth problem unsolvable.

Applications

The Matiyasevich/MRDP theorem relates two notions—one from computability theory, the other from number theory—and has some surprising consequences. Perhaps the most surprising is the existence of a universal Diophantine equation:

There exists a polynomial ${\displaystyle p(a,n,x_1,\dots <!--\; \dots \; -->,x_k)}$Zdroj:https://en.wikipedia.org?pojem=Hilbert's_tenth_problem
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---