HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a ...
is an equation of the form ''P''(''x''1, ..., ''x''''j'', ''y''1, ..., ''y''''k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer
coefficient In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
s, where ''x''1, ..., ''x''''j'' indicate parameters and ''y''1, ..., ''y''''k'' indicate unknowns. A Diophantine set is a
subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
''S'' of \mathbb^j, the set of all ''j''-tuples of natural numbers, so that for some
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a ...
''P''(', ') = 0, :\bar \in S \iff (\exists \bar \in \mathbb^)(P(\bar,\bar)=0) . That is, a parameter value is in the Diophantine set ''S''
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
the associated Diophantine equation is
satisfiable In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable ove ...
under that parameter value. The use of natural numbers both in ''S'' and the existential quantification merely reflects the usual applications in computability and model theory. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine set are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers. Also it is sufficient to assume ''P'' is a polynomial over \mathbb and multiply ''P'' by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem. The MRDP theorem (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is
computably enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
. A set of integers ''S'' is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of ''S'' and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
, can be taken rather in logical or recursion-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled
Hilbert's tenth problem 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 which, for any given Diophantine equation (a polynomial equ ...
. Hilbert's tenth problem was to find a general
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
which can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
with a total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.


Examples

In the following examples, the natural numbers refer to the set of positive integers. The equation :x = (y_1 + 1)(y_2 + 1) is an example of a Diophantine equation with a parameter ''x'' and unknowns ''y''1 and ''y''2. The equation has a solution in ''y''1 and ''y''2 precisely when ''x'' can be expressed as a product of two integers greater than 1, in other words ''x'' is a
composite number A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor In mathematics, a divisor of an integer n, also called a factor ...
. Namely, this equation provides a Diophantine definition of the set : consisting of the composite numbers. Other examples of Diophantine definitions are as follows: * The equation x = y_1^2 + y_2^2 with parameter ''x'' and unknowns ''y''1, ''y''2 only has solutions in \mathbb when ''x'' is a sum of two perfect squares. The Diophantine set of the equation is . * The equation y_1^2 - xy_2^2 = 1 with parameter ''x'' and unknowns ''y''1, ''y''2. This is a Pell equation, meaning it only has solutions in \mathbb when ''x'' is not a perfect square. The Diophantine set is . * The equation x_1 + y = x_2 is a Diophantine equation with two parameters ''x''1, ''x''2 and an unknown ''y'', which defines the set of pairs (''x''1, ''x''2) such that ''x''1 < ''x''2.


Matiyasevich's theorem

Matiyasevich's theorem, also called the MatiyasevichRobinson
Davis Davis may refer to: Places Antarctica * Mount Davis (Antarctica) * Davis Island (Palmer Archipelago) * Davis Valley, Queen Elizabeth Land Canada * Davis, Saskatchewan, an unincorporated community * Davis Strait, between Nunavut and Gre ...
Putnam or MRDP theorem, says: :Every
computably enumerable set In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
is Diophantine, and the converse. A set ''S'' of integers is
computably enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
if there is an algorithm such that: For each integer input ''n'', if ''n'' is a member of ''S'', then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of ''S''. A set ''S'' is Diophantine precisely if there is some
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
with integer coefficients ''f''(''n'', ''x''1, ..., ''x''''k'') such that an integer ''n'' is in ''S'' if and only if there exist some integers ''x''1, ..., ''x''''k'' such that ''f''(''n'', ''x''1, ..., ''x''''k'') = 0. Conversely, every Diophantine set is
computably enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
: consider a Diophantine equation ''f''(''n'', ''x''1, ..., ''x''''k'') = 0. Now we make an algorithm which simply tries all possible values for ''n'', ''x''1, ..., ''x''''k'' (in, say, some simple order consistent with the increasing order of the sum of their absolute values), and prints ''n'' every time ''f''(''n'', ''x''1, ..., ''x''''k'') = 0. This algorithm will obviously run forever and will list exactly the ''n'' for which ''f''(''n'', ''x''1, ..., ''x''''k'') = 0 has a solution in ''x''1, ..., ''x''''k''.


Proof technique

Yuri Matiyasevich utilized a method involving
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s, which grow exponentially, in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by
Julia Robinson Julia Hall Bowman Robinson (December 8, 1919July 30, 1985) was an American mathematician noted for her contributions to the fields of computability theory and computational complexity theory—most notably in decision problems. Her work on Hilber ...
, Martin Davis and
Hilary Putnam Hilary Whitehall Putnam (; July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, and computer scientist, and a major figure in analytic philosophy in the second half of the 20th century. He made significant contributions ...
– hence, MRDP – had shown that this suffices to show that every
computably enumerable set In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
is Diophantine.


Application to Hilbert's tenth problem

Hilbert's tenth problem 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 which, for any given Diophantine equation (a polynomial equ ...
asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's result with the fact that most recursively enumerable languages are not decidable implies that a solution to Hilbert's tenth problem is impossible.


Refinements

Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (
Zhi Wei Sun Sun Zhiwei (, born October 16, 1965) is a Chinese mathematician, working primarily in number theory, combinatorics, and group theory. He is a professor at Nanjing University. Biography Sun Zhiwei was born in Huai'an, Jiangsu. Sun and his ...
, 1992).


Further applications

Matiyasevich's theorem has since been used to prove that many problems from
calculus Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizati ...
and
differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, ...
s are unsolvable. One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result: :''Corresponding to any given consistent axiomatization of number theory,More precisely, given a \Sigma^0_1-formula representing the set of Gödel numbers of
sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the '' sententiae'' ...
which recursively axiomatize a consistent
theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may ...
extending
Robinson arithmetic In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q i ...
.
one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.'' According to the
incompleteness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...
s, a powerful-enough consistent axiomatic theory is incomplete, meaning the truth of some of its propositions cannot be established within its formalism. The statement above says that this incompleteness must include the solvability of a diophantine equation, assuming that the theory in question is a number theory.


Notes


References

* English translation in ''Soviet Mathematics'' 11 (2), pp. 354–357. * * * * {{cite journal , author=Sun Zhi-Wei , url=http://math.nju.edu.cn/~zwsun/12d.pdf , title=Reduction of unknowns in Diophantine representations , journal=Science China Mathematics , volume=35 , number=3 , year=1992 , pages=257–269 , zbl=0773.11077


External links


Matiyasevich theorem
article on
Scholarpedia ''Scholarpedia'' is an English-language wiki-based online encyclopedia with features commonly associated with open-access online academic journals, which aims to have quality content in science and medicine. ''Scholarpedia'' articles are writ ...
.
Diophantine Set
article on PlanetMath. Diophantine equations Hilbert's problems fr:Diophantien it:Teorema di Matiyasevich he:הבעיה העשירית של הילברט pt:Teorema de Matiyasevich ru:Диофантово множество