Hilbert's tenth problem

related topics
{math, number, function}
{theory, work, human}

Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:

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.

A Diophantine equation is an equation of the form

where p is a polynomial with integer coefficients. It took many years for the problem to be solved with a negative answer. Today, it is known that no such algorithm exists in the general case. This result is the combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson.[1]

Contents

Formulation

The words "process" and "finite number of operations" have been taken to mean that Hilbert was asking for an algorithm. The term "rational integer" 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. The answer to the problem is now known to be in the negative: no such general algorithm can exist. Although it is unlikely that Hilbert had conceived of such a possibility, before going on to list the problems, he did presciently remark:

"Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated."

The work on the problem has been in terms of solutions in natural numbers[2] rather than arbitrary integers. But it is easy to see that an algorithm in either case could be used to obtain one for the other. If one possessed an algorithm to determine solvability in natural numbers, it could be used to determine whether an equation in n unknowns,

has an integer solution by applying the supposed algorithm to the 2n equations

Conversely, an algorithm to test for solvability in arbitrary integers could be used to test a given equation for solvability in natural numbers by applying that supposed algorithm to the equation obtained from the given equation by replacing each unknown by the sum of the squares of four new unknowns. This works because of Lagrange's four-square theorem, to the effect that every natural number can be written as the sum of four squares.

Diophantine sets

Full article ▸

related documents
Dedekind domain
Orthogonal matrix
Logarithm
Algebraic geometry
Combinatorics
Fast Fourier transform
Closure (computer science)
Continued fraction
Class (computer science)
Axiom of choice
Singleton pattern
Lie group
Tensor product
Adjoint functors
Riemann integral
Variable
Μ-recursive function
Functional programming
Original proof of Gödel's completeness theorem
Kolmogorov complexity
Scheme (programming language)
Fourier series
Pythagorean triple
Group theory
Grothendieck topology
Discrete cosine transform
Binomial coefficient
Travelling salesman problem
Design Patterns
Numeral system