Clever Geek Handbook
📜 ⬆️ ⬇️

Hilbert's tenth problem

Hilbert's tenth problem is one of 23 problems that David Hilbert proposed on August 8, 1900 at the II International Congress of Mathematicians . It consists in finding a universal method for determining the solvability of an arbitrary algebraic Diophantine equation . The proof of the algorithmic unsolvability of this problem took about twenty years and was completed by Yuri Matiyasevich in 1970 [1] [2] .

Content

  • 1 Problem statement
  • 2 Background
  • 3 Solution History
    • 3.1 Algorithm searches
    • 3.2 Davis hypothesis
    • 3.3 Hypothesis Robinson
    • 3.4 Joining forces
  • 4 Impact
  • 5 notes
  • 6 Literature
  • 7 References

Statement of the problem

In the Hilbert report, the statement of the tenth problem is the shortest of all:

Let a Diophantine equation with arbitrary unknowns and integer rational numerical coefficients be given. Indicate the method by which it is possible after a finite number of operations to establish whether this equation is solvable in rational integers [3] .

Original text (German)
Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem ​​sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt in ob die glenichten

Formally, we are talking about an integer [5] solution of equations of the form

P(xone,x2,...,xn)=0,{\ displaystyle P (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0,}  

WhereP {\ displaystyle P}   - polynomial with integer coefficients and integer exponents [6] . The degree of the equation is equal to the degree of the polynomialP {\ displaystyle P}   .

Of all 23 problems, the only one is the solvability problem [7] . Apparently, Hilbert believed that the method sought exists and will be found sooner or later. [8] There was no question that such a method could not exist in principle at the time of Hilbert. [9] [10]

Background

The integer solution of algebraic equations has interested mathematicians since ancient times. For example, much attention was paid to the equationx2+y2=z2 {\ displaystyle x ^ {2} + y ^ {2} = z ^ {2}}   : if his solution was a set of natural numbersx0,y0,z0 {\ displaystyle x_ {0}, y_ {0}, z_ {0}}   then by the theorem inverse to the Pythagorean theorem from segments of lengthx0,y0,z0 {\ displaystyle x_ {0}, y_ {0}, z_ {0}}   one could get a right triangle [11] . Euclid gave formulas for finding all integer solutions of this equation [12] . Some types of equations of the second degree and their systems were considered by Diophantus of Alexandria [13] ; his works were later used by Leonard Euler , Pierre Fermat , Joseph Louis Lagrange , Karl Friedrich Gauss and other mathematicians involved in number theory . In particular, Fermat put forward his famous hypothesis . By 1768, Lagrange had completely investigated the question of integer solutions to any equation of the second degree with two unknowns [14] .

During the 19th century, many mathematicians, solving Fermat's Great Theorem , attempted to study Diophantine equations of degree higher than the second. Nevertheless, the problem of solving such equations remained open : no general method was obtained, only special techniques were found for equations of certain types. Most likely, Hilbert suspected that further research in this area would lead to the creation of detailed and deep theories, not limited to Diophantine equations, and this prompted him to add the task to the list for his report [9] .

Solution History

Algorithm Searches

Until the 1940s, research on the tenth problem was carried out in the direction of searching for the required algorithm for at least some classes of Diophantine equations. A few years after Hilbert's report in 1908, Axel Thue showed that the Thue equation for two unknowns cannot have infinitely many integer solutions [15] . In 1938, Turalf Skulem published a method for studying diophantine equations of the formP(xone,x2,...,xn)=0, {\ displaystyle P (x_ {1}, x_ {2}, \ ldots, x_ {n}) = 0,}   WhereP {\ displaystyle P}   - incomplete decomposable form (irreducible polynomial decomposing in the expansion of the field of rational numbers into a productm {\ displaystyle m}   linear factorsm>n {\ displaystyle m> n}   ) satisfying certain conditions [16] . Despite the result of Thue, even equations with two unknowns did not succumb to any efforts of mathematicians (an algorithm for solving equations with one unknown follows from Bezout's theorem ).

In the mid-1930s, the concept of an algorithm was formalized, and the first examples of algorithmically unsolvable sets in mathematical logic appeared . An important point was the proof by Andrei Markov and Emil Post (independently of each other) of the unsolvability of the Thue problem in 1947 [17] [18] . This was the first proof of the unsolvability of an algebraic problem. It, as well as difficulties encountered by researchers of Diophantine equations, led to the assumption that the algorithm required by Hilbert does not exist. A little earlier, in 1944, Emil Post already wrote in one of his works that the tenth problem “begs for evidence of unsolvability” ( Eng. “Begs for an unsolvability proof” ) [19] .

Davis hypothesis

Post's words inspired student Martin Davis to search for evidence of the unsolvability of the tenth problem. Davis went from her formulation in integers to a more natural formulation in theory of algorithms in natural numbers [20] . These are two different tasks, but each of them comes down to the other. In 1953, he published a work in which he outlined the way to solve the tenth problem in natural numbers [21] .

Davis, along with the classical Diophantine equations, considered their parametric version:

P(aone,...,an,xone,...,xm)=0,{\ displaystyle P (a_ {1}, \ ldots, a_ {n}, x_ {1}, \ ldots, x_ {m}) = 0,}  

where is the polynomialP {\ displaystyle P}   with integer coefficients can be divided into two parts - parametersaone,...,an {\ displaystyle a_ {1}, \ ldots, a_ {n}}   and variablesxone,...,xm. {\ displaystyle x_ {1}, \ ldots, x_ {m}.}   With one set of parameter values, the equation may have a solution; with another, solutions may not exist. Davis singled out manyM {\ displaystyle M}   which contains all sets of parameter values ​​(n {\ displaystyle n}   -k), in which the equation has a solution:

haone,...,ani∈M⟺∃xone,...,xmfP(aone,...,an,xone,...,xm)=0g.{\ displaystyle {\ mathcal {h}} a_ {1}, \ ldots, a_ {n} {\ mathcal {i}} \ in M ​​\ Longleftrightarrow \ exists x_ {1}, \ ldots, x_ {m} {\ mathcal {f}} P (a_ {1}, \ ldots, a_ {n}, x_ {1}, \ ldots, x_ {m}) = 0 {\ mathcal {g}}.}  

He called such a record the Diophantine representation of the set, and the set itself also called the Diophantine representation. To prove the unsolvability of the tenth problem, it was only necessary to show the Diophantine nature of any enumerable set , that is, to show the possibility of constructing an equation that would have natural rootsxone,...,xm {\ displaystyle x_ {1}, \ ldots, x_ {m}}   only for allhaone,...,ani {\ displaystyle {\ mathcal {h}} a_ {1}, \ ldots, a_ {n} {\ mathcal {i}}}   belonging to this enumerable set: since among the enumerable sets there are unsolvable ones , then taking an unsolvable setM {\ displaystyle M}   as a basis, it would be impossible to get a general method that wouldn {\ displaystyle n}   -ke determined whether the equation has natural roots on this set. All this led Davis to the following hypothesis:

The concepts of diophantine and enumerated sets coincide. This means that a set is Diophantine if and only if it is enumerable.

Davis also took the first step - proved that any enumerable setM {\ displaystyle M}   can be represented as:

haone,...,ani∈M⟺∃z∀y<z∃xone,...,xmfP(aone,...,an,xone,...,xm,y,z)=0g.{\ displaystyle {\ mathcal {h}} a_ {1}, \ ldots, a_ {n} {\ mathcal {i}} \ in M ​​\ Longleftrightarrow \ exists z \ forall y <z \ exists x_ {1}, \ ldots, x_ {m} {\ mathcal {f}} P (a_ {1}, \ ldots, a_ {n}, x_ {1}, \ ldots, x_ {m}, y, z) = 0 {\ mathcal {g}}.}  

This view was called the "normal form of Davis." At that time he failed to prove his hypothesis by getting rid of the universal quantifier .

Hypothesis Robinson

Regardless of Davis, Julia Robinson began working on the tenth problem in the same year. Initially, she tried to prove Alfred Tarski 's hypothesis that the set of all degrees of the deuce is not Diophantine, but has not achieved success [22] . After that, Robinson went on to investigate whether the set consisting of triples is a Diophantine set.ha,b,c=abi {\ displaystyle {\ mathcal {h}} a, b, c = a ^ {b} {\ mathcal {i}}}   . She failed to find the Diophantine representation for the operation of raising to a power, but, nevertheless, in her work [23] she showed a sufficient condition for its existence:

hu,vi∈R⟺∃xone,...,xmfP(u,v,xone,...,xm)=0g,{\ displaystyle {\ mathcal {h}} u, v {\ mathcal {i}} \ in R \ Longleftrightarrow \ exists x_ {1}, \ ldots, x_ {m} {\ mathcal {f}} P (u, v, x_ {1}, \ ldots, x_ {m}) = 0 {\ mathcal {g}},}  

moreover:

  • ifhu,vi∈R {\ displaystyle {\ mathcal {h}} u, v {\ mathcal {i}} \ in R}   thenu<vv, {\ displaystyle u <v ^ {v},}  
  • for anyonek {\ displaystyle k}   existsu {\ displaystyle u}   andv {\ displaystyle v}   such thathu,vi∈R {\ displaystyle {\ mathcal {h}} u, v {\ mathcal {i}} \ in R}   andu>vk. {\ displaystyle u> v ^ {k}.}  

Connection betweenu {\ displaystyle u}   andv {\ displaystyle v}   Robinson called it “exponential growth dependency”, but later this dependence was called in her honor - “Robinson dependency”, “Robinson predicates” or simply “JR”.

Joining forces

In 1958, Martin Davis and Hilary Putnam published a paper [24] , in which, based on the result of Robinson, they considered a class of exponential diophantine equations of the form:

EL(xone,...,xm)=ER(xone,...,xm),{\ displaystyle E_ {L} (x_ {1}, \ ldots, x_ {m}) = E_ {R} (x_ {1}, \ ldots, x_ {m}),}  

WhereEL {\ displaystyle E_ {L}}   andER {\ displaystyle E_ {R}}   - exponential polynomials, that is, expressions obtained from variables and rational numbers using the operations of addition , multiplication and raising to a power , and also showed a Diophantine representation for such equations. However, the proof of Davis and Putnem contained a gap - they used the hypothesis of the existence of arbitrarily long arithmetic progressions consisting only of primes ( Green-Tao theorem ), which was proved only in 2004.

In 1961, Julia Robinson was able to fill this gap. In their joint work [25] , an exponentially Diophantine representation was obtained for any enumerable set:

haone,...,ani∈M⟺∃xone,...,xmEL(aone,...,an,xone,...,xm)=ER(aone,...,an,xone,...,xm).{\ displaystyle {\ mathcal {h}} a_ {1}, \ ldots, a_ {n} {\ mathcal {i}} \ in M ​​\ Longleftrightarrow \ exists x_ {1}, \ ldots, x_ {m} E_ { L} (a_ {1}, \ ldots, a_ {n}, x_ {1}, \ ldots, x_ {m}) = E_ {R} (a_ {1}, \ ldots, a_ {n}, x_ { 1}, \ ldots, x_ {m}).}  

One of the consequences of the work was the possibility of reducing any exponentially-Diophantine equation to an exponentially-Diophantine equation with a fixed number of variables (with at least three [26] ).

To transfer the result of Davis, Putnam and Robinson to the “ordinary” Diophantine equations, it was necessary to prove that the set consisting of triplesha,b,c=abi {\ displaystyle {\ mathcal {h}} a, b, c = a ^ {b} {\ mathcal {i}}}   is diophantine. Then it would be possible, at the cost of introducing additional unknowns, to translate the exponentially-Diophantine representation into the Diophantine representation:

a,b,c=ab⟺∃xone,...,xmfP(a,b,c,xone,...,xm)=0g.{\ displaystyle a, b, c = a ^ {b} \ Longleftrightarrow \ exists x_ {1}, \ ldots, x_ {m} {\ mathcal {f}} P (a, b, c, x_ {1}, \ ldots, x_ {m}) = 0 {\ mathcal {g}}.}  

In other words, to fully prove the Davis hypothesis, it was only necessary to prove one particular case of it, and more precisely, to prove the Robinson hypothesis (find the polynomialP(u,v,xone,...,xm) {\ displaystyle P (u, v, x_ {1}, \ ldots, x_ {m})}   satisfying all conditions).

Despite a deep study of two-parameter Diophantine equations from the time of Diophantus himself, at that time there was no known equation expressing the dependence of exponential growth. Attempts to artificially construct it also failed.


Impact

  • In 2008, the premiere of an hour-long documentary directed by George Csicsery, Julia Robinson and Hilbert's Tenth Problem, premiered. The film is dedicated to Julia Robinson and her contribution to solving the tenth problem [27] . The film received reviews and reviews from American mathematical journals and communities [28] [29] .

Notes

  1. ↑ Yu. V. Matiyasevich . Diophantine nature of enumerable sets // Reports of the USSR Academy of Sciences. - 1970. - T. 191 , No. 2 . - S. 279-282 .
  2. ↑ Yu. V. Matiyasevich . Hilbert's tenth problem . - M .: Science: Physics and mathematics, 1993. - 223 p. - (Mathematical logic and foundations of mathematics; Issue No. 26). - ISBN 502014326X . (inaccessible link)
  3. ↑ Translation of the Hilbert report from German - M. G. Shestopal and A. V. Dorofeev , published in the book Problems of Hilbert / ed. P.S. Aleksandrova . - M .: Nauka, 1969 .-- S. 39 .-- 240 p. - 10,700 copies. Archived on October 17, 2011. Archived October 17, 2011 on Wayback Machine
  4. ↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900 (German) . - The text of the report read by Hilbert on August 8, 1900 at the II International Congress of Mathematicians in Paris. Date of treatment August 27, 2009. Archived on April 8, 2012.
  5. ↑ “Rational whole” is synonymous with “whole,” see Weisstein, Eric W. Rational Integer ( Wolfram ) on Wolfram MathWorld .
  6. ↑ V.I. Igoshin. § 36. Insoluble algorithmic problems // Mathematical logic and theory of algorithms. - M .: Academy, 2004 .-- S. 375. - 448 p. - 5100 copies. - ISBN 5-7695-1363-2 .
  7. ↑ Yuri Matiyasevich. Hilbert's Tenth Problem: What can we do with Diophantine equations . Date of treatment August 27, 2009. Archived April 10, 2012.
  8. ↑ This is also evidenced by the very formulation of the problem in a positive way: “man soll ein Verfahren angeben” (“indicate the order of actions”, and not, for example, “indicate whether the order of actions”).
  9. ↑ 1 2 Yu. I. Khmelevsky. To the tenth Hilbert problem // Hilbert Problems / ed. P.S. Aleksandrova . - M .: Nauka, 1969 .-- S. 141-153. - 240 p. - 10,700 copies. Archived on October 17, 2011. Archived October 17, 2011 on Wayback Machine
  10. ↑ F.P. Varpakhovsky and A.N. Kolmogorov . On the solution of the tenth problem of Hilbert // Quantum . - 1970. - No. 7 . - S. 38-44 .
  11. ↑ A.A. Bolibrukh . Hilbert's Tenth Problem: Diophantine Equations // Hilbert Problems (100 years later) . - M .: ICMMO , 1999 .-- 24 p. - ( Library "Mathematical Education" , issue number 2). - 3000 copies.
  12. ↑ Simon Singh. Appendix 5. Proof of Euclidean existence of an infinite number of Pythagorean triples // Great Fermat's theorem = Fermat's last theorem / per. from English Yu.A. Danilova. - ICMMO , 2000.
  13. ↑ Diophantus of Alexandria . Arithmetic and a book on polygonal numbers / Per. with other Greek Yu. N. Veselovsky. - M .: Nauka, 1974 .-- 328 p. - 17,500 copies. Archived December 25, 2009. Archived December 25, 2009 by Wayback Machine
  14. ↑ Leonard Eugene Dickson. History of the Theory of Numbers . - 1920.- T. II: Diophantine Analysis. (eng.)
  15. ↑ A. Thue . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. Klasse. - 1908. - No. 3 . - S. 1—34 .
  16. ↑ Thoralf Skolem. Diophantische Gleichungen. - Berlin: Springer, 1938 .-- 128 p.
  17. ↑ Article of Markov - A. A. Markov . The impossibility of some algorithms in the theory of associative systems // Reports of the USSR Academy of Sciences. - M. , 1947. - T. 55 , no. 7 . - S. 587-590 . , see also monograph by A. A. Markov . Theory of Algorithms // Transactions of the Mathematical Institute of the USSR Academy of Sciences V.A. Steklova. - M. - L .: publishing house of the Academy of Sciences of the USSR, 1954. - T. 42 . - S. 3-375 .
  18. ↑ Post Result was published in an EL Post article . Recursive Unsolvability of a Problem of Thue (Eng.) // The Journal of Symbolic Logic. - 1947. - Vol. 12 , no. 1 . - P. 1-11 .
  19. ↑ Emil Leon Post . Recursively enumerable sets of positive integers and their decision problems (English) // Bulletin of the American Mathematical Society. - 1944. - Vol. 50 , iss. 5 . - P. 284-316 .
  20. ↑ In the American mathematical tradition, 0 is a natural number.
  21. ↑ Martin Davis. Arithmetical Problems and Recursively Enumerable Predicates // The Journal of Symbolic Logic. - 1953. - Vol. 18 , no. 1 . - P. 33-41 .
  22. ↑ Yu. V. Matiyasevich . Hilbert's Tenth Problem: Diophantine Equations in Twentieth Century // Mathematical Events of the Twentieth Century = Mathematical Events of the 20th Century / ed. AA Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006 .-- S. 185-214. - 545 s. - ISBN 3-540-23235-4 . (eng.)
  23. ↑ Julia Robinson. Existential definability in arithmetic (Eng.) // Transactions of the American Mathematical Society. - 1952. - Vol. 72 , no. 3 . - P. 437-449 .
  24. ↑ Martin Davis, Hilary Putnam. Reductions of Hilbert's tenth problem // The Journal of Symbolic Logic. - 1958. - Vol. 23 , no. 2 . - P. 183-187 .
  25. ↑ Martin Davis, Hilary Putnam, Julia Robinson. The decision problem for exponential Diophantine equations (Eng.) // Annals of Mathematics. - 1961. - Vol. 74 , no. 3 . - P. 425-436 .
  26. ↑ Yu. V. Matiyasevich . Algorithmic unsolvability of exponentially Diophantine equations with three unknowns // Studies in the theory of algorithms and mathematical logic / ed. A.A. Markov and V.I. Khomich. - M .: Nauka, 1979. - Vol. 3 . - S. 69-78 .
  27. ↑ “Julia Robinson and Hilbert's Tenth Problem” . - ZALA Films. Date of treatment August 27, 2009. Archived April 10, 2012.
  28. ↑ Carol Wood. Film Review: Julia Robinson and Hilbert's Tenth Problem (Eng.) // Notices of the American Mathematical Society. - 2008 .-- Vol. 55 , no. 5 . - P. 573-575 . - ISSN 00029920 .
  29. ↑ Margaret AM Murray. A Film of One's Own (Eng.) // College Mathematics Journal. - Washington, DC: Mathematical Association of America , 2009. - Vol. 40 , no. 4 . - P. 306-310 . - ISSN 07468342 .

Literature

  • Yu. V. Matiyasevich . Hilbert's tenth problem . - M .: Nauka, 1993 .-- ISBN 502014326X . (inaccessible link)
  • F.P. Varpakhovsky, A.N. Kolmogorov . On the solution of the tenth problem of Hilbert // Quantum . - 1970. - No. 7 . - S. 38-44 .
  • Yu. I. Khmelevsky. To the tenth Hilbert problem // Hilbert Problems / ed. P.S. Aleksandrova . - M .: Nauka, 1969 .-- S. 141-153. - 240 p. - 10,700 copies. Archived on October 17, 2011. Archived October 17, 2011 on Wayback Machine
  • K.M. Podnieks. Chapter 4. The tenth Hilbert problem // Around Godel's theorem . - Riga: Zinatne, 1992 .-- 191 p.
  • Yu. V. Matiyasevich . Hilbert's Tenth Problem: Diophantine Equations in Twentieth Century // Mathematical Events of the Twentieth Century = Mathematical Events of the 20th Century / ed. AA Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006 .-- S. 185-214. - 545 s. - ISBN 3-540-23235-4 . (eng.)
  • Hilbert's tenth problem: relations with arithmetic and algebraic geometry. Workshop on Hilbert's tenth problem: relations with arithmetic and algebraic geometry, november 2-5, 1999, Ghent University, Belgium / ed. Jan Denef, Leonard Lipshitz, Thanases Pheidas, Jan Van Geel. - Contemporary Mathematics. - 2000. - T. 270. - 367 p. - ISBN 0-8218-2622-0 . (eng.)

Links

  • Maxim Vsemirnov, Yuri Matiyasevich. Hilbert's Tenth Problem page . Date of treatment August 27, 2009. Archived April 10, 2012.
  • Hilbert's 10th problem: the history of mathematical discovery (neopr.) . Date of treatment August 27, 2009. Archived April 10, 2012.
  • Yuri Matiyasevich. Hilbert's Tenth Problem: What can we do with Diophantine equations . Date of treatment August 27, 2009. Archived April 10, 2012.
  • Zhi-Wei Sun. On Hilbert's tenth problem and related topics ( April 14, 2000). Date of treatment August 29, 2009. Archived April 10, 2012.
  • Panu Raatikainen. The problem of the simplest diophantine representation . Date of treatment August 29, 2009. Archived April 10, 2012.
Source - https://ru.wikipedia.org/w/index.php?title=Hilbert_Tenth_Problem&oldid=100333324


More articles:

  • Estonian Football Union
  • Harmonic Medium
  • Hopman Cup 2010. Asian Selection
  • Harley Quinn
  • Pietro Perugino
  • Retovsky's Woodcutter
  • Novodnistrovsk
  • Novoselitsa
  • Polyansky, Vitaliy Vladimirovich
  • Waigi

All articles

Clever Geek | 2019