Hilbertův desátý problém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. října 2021; ověření vyžaduje 1 úpravu .

Hilbertův desátý problém  je jedním z 23 problémů , které David Hilbert navrhl 8. srpna 1900 na II. mezinárodním kongresu matematiků . Spočívá v nalezení univerzální metody pro určení řešitelnosti libovolné algebraické diofantické rovnice . Důkaz algoritmické neřešitelnosti tohoto problému trval asi dvacet let a dokončil jej Yuri Matiyasevich v roce 1970 [1] [2] .

Prohlášení o problému

V Hilbertově zprávě je formulace desátého problému ze všech nejkratší:

Nechť je dána diofantická rovnice s libovolnými neznámými a celočíselnými racionálními numerickými koeficienty. Uveďte metodu, pomocí které je možné po konečném počtu operací zjistit, zda je tato rovnice řešitelná v celých racionálních číslech [3] .

Původní text  (německy)[ zobrazitskrýt] Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen reasonen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren anngeben, nach welchem ​​​​sich mittelst einer endlichen Anzahl von Operationen entscheiden , l4läßen länchen

Formálně mluvíme o celočíselném [5] řešení rovnic tvaru

kde  je polynom s celočíselnými koeficienty a celočíselnými exponenty [6] . Stupeň rovnice se rovná stupni polynomu .

Ze všech 23 problémů je to jediný problém řešitelnosti [7] . Hilbert očividně věřil, že požadovaná metoda existuje a bude dříve nebo později nalezena [8] . Otázka, že by taková metoda v principu nemusela existovat, v Hilbertově době nevznikla [9] [10] .

Pozadí

Celočíselné řešení algebraických rovnic bylo předmětem zájmu matematiků již od starověku . Velká pozornost byla věnována například rovnici : pokud by jejím řešením byla množina přirozených čísel , pak by bylo možné pomocí věty inverzní k Pythagorově větě získat ze segmentů délky pravoúhlý trojúhelník [11] . Euclid dal vzorce pro nalezení všech celočíselných řešení této rovnice [12] . Některými typy rovnic druhého stupně a jejich soustavami se zabýval Diophantus z Alexandrie [13] , jeho díla později použili Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss a další matematici zabývající se teorií čísel . Zejména Fermat předložil svou slavnou hypotézu . V roce 1768 Lagrange plně prozkoumal otázku celočíselných řešení jakékoli rovnice druhého stupně ve dvou neznámých [14] .

Během 19. století se mnoho matematiků, kteří řešili Fermatovu poslední větu , pokoušelo studovat diofantické rovnice stupně vyššího než druhý. Problém řešení takových rovnic však zůstal otevřený : nebyla získána žádná obecná metoda, byly nalezeny pouze speciální metody pro rovnice určitých typů. S největší pravděpodobností Hilbert tušil, že další výzkum v této oblasti povede k vytvoření podrobných a hlubokých teorií, neomezujících se na diofantické rovnice, a to ho přimělo, aby vyjmenoval problém pro svou zprávu [9] .

Historie řešení

Hledat algoritmus

Až do 40. let 20. století probíhal výzkum desátého problému ve směru nalezení požadovaného algoritmu pro alespoň některé třídy diofantických rovnic. Několik let po Hilbertově zprávě, v roce 1908, Axel Thue ukázal, že Thueova rovnice pro dvě neznámé nemůže mít nekonečně mnoho celočíselných řešení [15] . V roce 1938 Turalf Skolem publikoval metodu pro studium diofantických rovnic tvaru kde  je neúplný rozložitelný tvar ( ireducibilní polynom , který expanduje v oboru racionálních čísel na součin lineárních faktorů, ), který splňuje určité podmínky [16] . Navzdory Thueovu výsledku i rovnice se dvěma neznámými vzdorovaly jakékoli snaze matematiků (algoritmus pro řešení rovnic s jednou neznámou vyplývá z Bézoutova teorému ).

V polovině 30. let byl pojem algoritmus formalizován a objevily se také první příklady algoritmicky nerozhodnutelných množin v matematické logice . Důležitým momentem byl důkaz Andreje Markova a Emila Posta (nezávisle na sobě) o neřešitelnosti problému Thue v roce 1947 [17] [18] . To byl první důkaz neřešitelnosti algebraického problému. To, stejně jako potíže, kterým čelí výzkumníci diofantických rovnic, vedlo k předpokladu, že algoritmus požadovaný Hilbertem neexistuje. O něco dříve, v roce 1944, Emil Post již v jednom ze svých článků napsal, že desátý problém „ prosí o důkaz neřešitelnosti“ [ 19] . 

Davisova hypotéza

Postova slova inspirovala studenta Martina Davise k hledání důkazu, že desátý problém je neřešitelný. Davis přešel od formulace v celých číslech k formulaci v přirozených číslech , která je přirozenější pro teorii algoritmů [20] . Jsou to dva různé úkoly, ale každý z nich se scvrkává na druhý. V roce 1953 publikoval článek, ve kterém nastínil způsob řešení desátého problému v přirozených číslech [21] .

Davis spolu s klasickými diofanskými rovnicemi zvažoval jejich parametrickou verzi:

kde polynom s celočíselnými koeficienty lze rozdělit na dvě části - parametry a proměnné.Pro jednu sadu hodnot parametrů může mít rovnice řešení, pro jinou řešení nemusí existovat. Davies vybral sadu , která obsahuje všechny sady hodnot parametrů ( -s), pro které má rovnice řešení:

Nazval takovou notaci diofanskou reprezentací množiny a množina samotná se také nazývala diofantina . K prokázání neřešitelnosti desátého problému bylo potřeba pouze ukázat, že jakákoliv spočetná množina je diofantina , tedy ukázat možnost sestrojit rovnici, která by měla přirozené kořeny pouze pro všechny patřící do této spočetné množiny: jelikož mezi spočetné množiny existují neřešitelné množiny , pak, vezmeme-li za základ neřešitelnou množinu, nebylo by možné získat obecnou metodu, která by jednu po druhé určila, zda má rovnice přirozené kořeny na této množině. To vše vedlo Davise k následující hypotéze:

Pojmy diofantina a nesčetné množiny se shodují. To znamená, že množina je diofantická právě tehdy, když je spočetná.

Davis také udělal první krok - dokázal, že jakákoliv spočetná množina může být reprezentována jako:

Tato reprezentace se nazývá "Davisova normální forma". Tehdy se mu nepodařilo prokázat svou domněnku zbavením se univerzálního kvantifikátoru .

Robinsonova hypotéza

Nezávisle na Davisovi začala Julia Robinsonová ve stejných letech pracovat na desátém problému . Zpočátku se snažila dokázat domněnku Alfreda Tarského , že množina všech mocnin dvou není diofantina, ale neuspěla [22] . Poté Robinson přešel ke zkoumání otázky, zda soubor skládající se z trojic je Diophantine . Nepodařilo se jí najít diofantinskou reprezentaci pro operaci umocňování, ale přesto ve své práci [23] ukázala dostatečnou podmínku pro její existenci:

navíc:

Robinson nazval vztah mezi a „ exponenciální růstová závislost “, ale později se tato závislost začala nazývat na její počest – „Robinsonova závislost“, „Robinsonovy predikáty“ nebo jednoduše „JR“.

Spojení sil

V roce 1958 Martin Davis a Hilary Putnam publikovali [24] , ve kterém na základě Robinsonova výsledku uvažovali o třídě exponenciálně-diofantických rovnic, které mají tvar:

kde a  jsou exponenciální polynomy, to znamená výrazy získané z proměnných a racionálních čísel pomocí operací sčítání , násobení a umocňování , a také ukázaly diofantinskou reprezentaci pro takové rovnice. Důkaz Davise a Putnama však obsahoval mezeru – použili domněnku o existenci libovolně dlouhých aritmetických posloupností skládajících se pouze z prvočísel ( Green-Tao teorém ), která byla prokázána až v roce 2004.

V roce 1961 se Julii Robinsonovi podařilo tuto mezeru zaplnit . V jejich společné práci [25] byla získána exponenciální diofantická reprezentace pro jakoukoli spočetnou množinu:

Jedním z důsledků práce byla možnost redukce jakékoli exponenciální diofantické rovnice na exponenciální diofantinskou rovnici s pevným počtem proměnných (alespoň tři [26] ).

Aby bylo možné přenést výsledek Daviese, Putnama a Robinsona do „obyčejných“ diofantinských rovnic, bylo třeba dokázat, že množina skládající se z trojic je diofantina. Pak by bylo možné, za cenu zavedení dalších neznámých, převést exponenciálně diofantinskou reprezentaci na diofantinskou reprezentaci:

Jinými slovy, k úplnému prokázání Davisovy domněnky bylo nutné dokázat pouze jeden její konkrétní případ, přesněji dokázat Robinsonovu domněnku (nalézt polynom , který splňuje všechny podmínky).

Přes hluboké studium dvouparametrových diofantických rovnic již od dob samotného Diofanta nebyla v té době známa rovnice vyjadřující závislost exponenciálního růstu. Pokusy o jeho umělou konstrukci také selhaly.


Vliv

Poznámky

  1. ↑ Yu.V. Matiyaševič . Diofantní vlastnost spočetných souborů // Zprávy Akademie věd SSSR. - 1970. - T. 191 , č. 2 . - S. 279-282 .
  2. ↑ Yu.V. Matiyaševič . Hilbertův desátý problém . - M. : Nauka: Fyzikální a matematická literatura, 1993. - 223 s. — (Matematická logika a základy matematiky; Vydání č. 26). — ISBN 502014326X .  (nedostupný odkaz)
  3. ↑ Překlad Hilbertovy zprávy z němčiny - M. G. Shestopal a A. V. Dorofeev , publikované v knize Hilbertovy problémy / ed. P. S. Alexandrova . - M. : Nauka, 1969. - S. 39. - 240 s. — 10 700 výtisků. Archivovaná kopie (nedostupný odkaz) . Získáno 13. listopadu 2009. Archivováno z originálu 17. října 2011. 
  4. ↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900  (německy) . — Text zprávy, kterou četl Hilbert 8. srpna 1900 na II. mezinárodním kongresu matematiků v Paříži. Získáno 27. srpna 2009. Archivováno z originálu dne 8. dubna 2012.
  5. ↑ „Rational Integer“ je synonymem pro „integer“, viz Weisstein, Eric W. Rational Integer  (anglicky) na webu Wolfram MathWorld .
  6. ↑ V. I. Igošin. § 36. Neřešitelné algoritmické problémy // Matematická logika a teorie algoritmů. - M . : Akademie, 2004. - S. 375. - 448 s. - 5100 výtisků.  — ISBN 5-7695-1363-2 .
  7. ↑ Jurij Matijaševič. Hilbertův desátý problém : Co můžeme dělat s diofantickými rovnicemi  . Získáno 27. srpna 2009. Archivováno z originálu 10. dubna 2012.
  8. ↑ Svědčí o tom i samotná formulace úkolu v pozitivním slova smyslu: „man soll ein Verfahren angeben“ („uveďte postup“, a nikoli např. „uveďte, zda existuje postup“).
  9. ↑ 1 2 Yu. I. Chmelevskij. K desátému problému Hilberta // Problémy Hilberta / ed. P. S. Alexandrova . - M .: Nauka, 1969. - S. 141-153. — 240 s. — 10 700 výtisků. Archivovaná kopie (nedostupný odkaz) . Získáno 13. listopadu 2009. Archivováno z originálu 17. října 2011. 
  10. ↑ F. P. Varpakhovsky, A. N. Kolmogorov . K řešení Hilbertova desátého problému  // Kvant . - 1970. - č. 7 . - S. 38-44 .
  11. ↑ A. A. Bolibrukh . Hilbertův desátý problém: Diofantické rovnice // Hilbertovy problémy (o 100 let později) . - M. : MTSNMO , 1999. - 24 s. - ( Knihovna "Matematická výchova" , číslo 2). - 3000 výtisků.
  12. ↑ Simon Singh. Příloha 5. Euklidův důkaz existence nekonečného počtu pythagorejských trojic // Fermatova poslední věta = Fermatova poslední věta / přel. z angličtiny. Yu. A. Danilova. — MTsNMO , 2000.
  13. ↑ Diophantus Alexandrijský . Aritmetika a kniha o polygonálních číslech / per. s jinými Řeky Yu. N. Veselovský. - M. : Nauka, 1974. - 328 s. - 17 500 výtisků. Archivovaná kopie (nedostupný odkaz) . Získáno 13. listopadu 2009. Archivováno z originálu 25. prosince 2009. 
  14. ↑ Leonard Eugene Dickson. Historie teorie čísel . - 1920. - Svazek II: Diofantinová analýza.  (Angličtina)
  15. ↑ A. čtvrtek . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. třída. - 1908. - č. 3 . - S. 1-34 .
  16. ↑ Thoralf Skolem. Diofantische Gleichungen. - Berlín: Springer, 1938. - 128 s.
  17. ↑ Markovův článek - A. A. Markov . Nemožnost některých algoritmů v teorii asociativních systémů // Zprávy Akademie věd SSSR. - M. , 1947. - T. 55 , čís. 7 . - S. 587-590 . , viz též monografie A. A. Markova . Teorie algoritmů  // Sborník Matematického ústavu Akademie věd SSSR. V. A. Šteklová. - M. - L .: Nakladatelství Akademie věd SSSR, 1954. - T. 42 . - S. 3-375 .
  18. ↑ Výsledek Postu byl publikován v článku EL Post . Rekurzivní neřešitelnost problému Thue  //  The Journal of Symbolic Logic. - 1947. - Sv. 12 , č. 1 . - str. 1-11 .
  19. ↑ Emil Leon Post . Rekurzivně vyčíslitelné množiny kladných celých čísel a jejich rozhodovací problémy  //  Bulletin Americké matematické společnosti. - 1944. - Sv. 50 , iss. 5 . - str. 284-316 .
  20. ↑ V americké matematické tradici je 0 přirozené číslo.
  21. ↑ Martin Davis. Aritmetické problémy a rekurzivně vyčíslitelné predikáty  //  The Journal of Symbolic Logic. - 1953. - Sv. 18 , č. 1 . - str. 33-41 .
  22. ↑ Yu. V. Matiyaševič . Hilbertův desátý problém: Diophantine Equations in Twentieth Century // Matematické události dvacátého století = Matematické události XX století / ed. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinaj . - Berlin: Springer , 2006. - S. 185-214. — 545 str. — ISBN 3-540-23235-4 .  (Angličtina)
  23. ↑ Julia Robinsonová. Existenciální definovatelnost v aritmetice  //  Transactions of the American Mathematical Society. - 1952. - Sv. 72 , č. 3 . - str. 437-449 .
  24. ↑ Martin Davis, Hilary Putnam. Redukce Hilbertova desátého problému  //  The Journal of Symbolic Logic. - 1958. - Sv. 23 , č. 2 . - S. 183-187 .
  25. ↑ Martin Davis, Hilary Putnam, Julia Robinson. Rozhodovací problém pro exponenciální diofantické rovnice  //  Annals of Mathematics. - 1961. - Sv. 74 , č. 3 . - str. 425-436 .
  26. ↑ Yu.V. Matiyaševič . Algoritmická neřešitelnost exponenciálně-diofantických rovnic se třemi neznámými // Studie z teorie algoritmů a matematické logiky / ed. A. A. Markov a V. I. Khomich. - M .: Nauka, 1979. - Vydání. 3 . - S. 69-78 .
  27. ↑ "Julia Robinsonová a Hilbertův desátý problém  " . — ZALA Films. Získáno 27. srpna 2009. Archivováno z originálu 10. dubna 2012.
  28. ↑ Carol Woodová. Recenze filmu: Julia Robinsonová a Hilbertův desátý problém  //  Upozornění Americké matematické společnosti. - 2008. - Sv. 55 , č. 5 . - str. 573-575 . — ISSN 00029920 .
  29. ↑ Margaret A. M. Murrayová. Vlastní film  //  College Mathematics Journal. — Washington, DC: Mathematical Association of America , 2009. — Vol. 40 , č. 4 . - str. 306-310 . — ISSN 07468342 .

Literatura

Odkazy

 Hilbertovy problémy