A zecea problemă a lui Hilbert

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 octombrie 2021; verificarea necesită 1 editare .

A zecea problemă a lui Hilbert  este una dintre cele 23 de probleme pe care David Hilbert le-a propus la 8 august 1900 la al II-lea Congres Internațional al Matematicienilor . Constă în găsirea unei metode universale pentru determinarea solvabilității unei ecuații algebrice diofantine arbitrare . Dovada insolubilității algoritmice a acestei probleme a durat aproximativ douăzeci de ani și a fost finalizată de Yuri Matiyasevich în 1970 [1] [2] .

Enunțul problemei

În raportul lui Hilbert, formularea celei de-a zecea probleme este cea mai scurtă dintre toate:

Să fie dată o ecuație diofantică cu necunoscute arbitrare și coeficienți numerici raționali întregi. Indicați o metodă prin care este posibil, după un număr finit de operații, să se determine dacă această ecuație este rezolvabilă în numere întregi raționale [3] .

Text original  (germană)[ arataascunde] 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, ob die Gleicbarenh ganzen läßt 4 .

Formal, vorbim despre o soluție întreagă [5] a ecuațiilor de forma

unde  este un polinom cu coeficienți întregi și exponenți întregi [6] . Gradul ecuației este egal cu gradul polinomului .

Dintre toate cele 23 de probleme, este singura problemă de rezolvare [7] . Aparent, Hilbert credea că metoda dorită există și va fi găsită mai devreme sau mai târziu [8] . Întrebarea că o astfel de metodă ar putea să nu existe în principiu nu a apărut pe vremea lui Hilbert [9] [10] .

Fundal

Soluția întreagă a ecuațiilor algebrice a fost de interes pentru matematicieni încă din cele mai vechi timpuri. De exemplu, s-a acordat multă atenție ecuației : dacă soluția ei a fost o mulțime de numere naturale , atunci printr-o teoremă inversă teoremei lui Pitagora s-a putut obține un triunghi dreptunghic din segmente de lungime [11] . Euclid a dat formule pentru găsirea tuturor soluțiilor întregi ale acestei ecuații [12] . Unele tipuri de ecuații de gradul doi și sistemele lor au fost luate în considerare de Diophantus din Alexandria [13] , lucrările sale au fost ulterior folosite de Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss și alți matematicieni implicați în teoria numerelor . În special, Fermat a prezentat celebra sa ipoteză . Până în 1768, Lagrange explorase pe deplin problema soluțiilor întregi pentru orice ecuație de gradul doi în două necunoscute [14] .

În timpul secolului al XIX-lea, mulți matematicieni, rezolvând Ultima Teoremă a lui Fermat , au încercat să studieze ecuații diofante de grad mai mare decât al doilea. Cu toate acestea, problema rezolvării unor astfel de ecuații a rămas deschisă : nu s-a obținut o metodă generală, s-au găsit doar metode speciale pentru ecuații de anumite tipuri. Cel mai probabil, Hilbert a bănuit că cercetările ulterioare în acest domeniu ar duce la crearea unor teorii detaliate și profunde, fără a se limita la ecuațiile diofantine, iar acest lucru l-a determinat să enumere problema pentru raportul său [9] .

Istoricul soluției

Căutați un algoritm

Până în anii 1940, cercetările asupra celei de-a zecea probleme au fost efectuate în direcția găsirii algoritmului necesar pentru cel puțin unele clase de ecuații diofantine. La câțiva ani după raportul lui Hilbert, în 1908, Axel Thue a arătat că ecuația lui Thue pentru două necunoscute nu poate avea infinitate soluții întregi [15] . În 1938, Turalf Skolem a publicat o metodă de studiere a ecuațiilor diofantine de forma în care  este o formă descomponabilă incompletă ( un polinom ireductibil care se extinde în domeniul numerelor raționale într-un produs al factorilor liniari, ) care îndeplinește anumite condiții [16] . În ciuda rezultatului lui Thue, chiar și ecuațiile cu două necunoscute au sfidat orice efort al matematicienilor (algoritmul pentru rezolvarea ecuațiilor cu o necunoscută decurge din teorema lui Bézout ).

La mijlocul anilor 1930, noțiunea de algoritm a fost oficializată și au apărut și primele exemple de mulțimi indecidabile din punct de vedere algoritmic în logica matematică . Un moment important a fost demonstrarea de către Andrei Markov și Emil Post (independenți unul de celălalt) a insolubilității problemei Thue în 1947 [17] [18] . Aceasta a fost prima dovadă a insolubilității unei probleme algebrice . Ea, precum și dificultățile cu care se confruntă cercetătorii ecuațiilor diofantine, au condus la presupunerea că algoritmul cerut de Hilbert nu există. Puțin mai devreme, în 1944, Emil Post deja scria într-una dintre lucrările sale că a zecea problemă „ cersează o dovadă de insolubilitate” [ 19] . 

Ipoteza Davis

Cuvintele lui Post l-au inspirat pe studentul Martin Davis să caute o dovadă că a zecea problemă este indecidabilă. Davis a trecut de la formularea sa în numere întregi la o formulare în numere naturale , ceea ce este mai natural pentru teoria algoritmilor [20] . Acestea sunt două sarcini diferite, dar fiecare dintre ele se rezumă la cealaltă. În 1953, a publicat o lucrare în care a schițat o modalitate de a rezolva a zecea problemă în numere naturale [21] .

Davis, împreună cu ecuațiile diofantine clasice, au considerat versiunea lor parametrică:

unde un polinom cu coeficienți întregi poate fi împărțit în două părți - parametri și variabile.Pentru un set de valori ale parametrilor, ecuația poate avea o soluție, pentru altul, soluțiile pot să nu existe. Davies a evidențiat setul , care conține toate seturile de valori ale parametrilor ( -s) pentru care ecuația are o soluție:

El a numit o astfel de notație o reprezentare diofantină a unui set, iar setul în sine a fost numit și Diofantin . Pentru a demonstra insolubilitatea celei de-a zecea probleme, a fost nevoie doar să arătăm că orice mulțime enumerabilă este diofantină , adică să arătăm posibilitatea construirii unei ecuații care să aibă rădăcini naturale numai pentru toți aparținând acestei mulțimi enumerabile: întrucât dintre cele mulţimi enumerabile există multe nerezolvabile , atunci, luând ca bază mulţimea nerezolvabilă , ar fi imposibil să se obţină o metodă generală care să determine una câte una dacă o ecuaţie are rădăcini naturale pe această mulţime. Toate acestea l-au condus pe Davis la următoarea ipoteză:

Conceptele de multimi diofantine si enumerabile coincid. Aceasta înseamnă că un set este diofantin dacă și numai dacă este enumerabil.

Davis a făcut și primul pas - a demonstrat că orice set enumerabil poate fi reprezentat ca:

Această reprezentare se numește „forma normală Davis”. În acel moment, el nu a reușit să -și demonstreze conjectura scăpând de cuantificatorul universal .

Ipoteza lui Robinson

Independent de Davis, Julia Robinson a început să lucreze la a zecea problemă în aceiași ani . Inițial, ea a încercat să demonstreze conjectura lui Alfred Tarski că setul tuturor puterilor a doi nu este diofantin, dar nu a reușit [22] . După aceea, Robinson a continuat să investigheze întrebarea dacă un set format din triple este Diofantin . Ea nu a reușit să găsească o reprezentare diofantină pentru operația de exponențiere, dar cu toate acestea, în lucrarea sa [23] , ea a arătat o condiție suficientă pentru existența acesteia:

în plus:

Robinson a numit relația dintre și „dependență de creștere exponențială ”, dar mai târziu această dependență a început să fie numită în onoarea ei - „dependență Robinson”, „predicate Robinson” sau pur și simplu „JR”.

Unirea forțelor

În 1958, Martin Davis și Hilary Putnam au publicat [24] , în care, pe baza rezultatului lui Robinson, au considerat o clasă de ecuații exponențiale-diofantine care au forma:

unde și  sunt polinoame exponențiale, adică expresii obținute din variabile și numere raționale folosind operațiile de adunare , înmulțire și exponențiere și au prezentat, de asemenea, o reprezentare diofantină pentru astfel de ecuații. Cu toate acestea, dovada lui Davis și Putnam conținea un decalaj - au folosit conjectura despre existența unor progresii aritmetice arbitrar lungi constând numai din numere prime ( teorema Green-Tao ), care a fost demonstrată abia în 2004.

În 1961, Julia Robinson a reușit să umple acest gol . În lucrarea lor comună [25] , a fost obținută o reprezentare diofantină exponențială pentru orice set enumerabil:

Una dintre consecințele lucrării a fost posibilitatea reducerii oricărei ecuații diofantine exponențiale la o ecuație diofanțială exponențială cu un număr fix de variabile (cel puțin trei [26] ).

Pentru a transfera rezultatul lui Davies, Putnam și Robinson la ecuațiile diofantine „obișnuite”, a trebuit să demonstrăm că mulțimea formată din triple este diofantină. Atunci ar fi posibil, cu prețul introducerii unor necunoscute suplimentare, să traducem reprezentarea exponențial diofantină într-o reprezentare diofantină:

Cu alte cuvinte, pentru a demonstra pe deplin conjectura lui Davis, a fost necesar doar să se demonstreze un caz particular al acesteia sau, mai precis, să se demonstreze conjectura Robinson (pentru a găsi un polinom care să îndeplinească toate condițiile).

În ciuda studiului profund al ecuațiilor diofantine cu doi parametri încă de pe vremea lui Diophantus însuși, la acel moment nu exista o ecuație cunoscută care să exprimă dependența creșterii exponențiale. De asemenea, încercările de a-l construi artificial au eșuat.


Influență

Note

  1. ↑ Iu. V. Matiyasevici . Proprietatea diofantină a seturilor enumerabile // Rapoarte ale Academiei de Științe a URSS. - 1970. - T. 191 , nr 2 . - S. 279-282 .
  2. ↑ Iu. V. Matiyasevici . A zecea problemă a lui Hilbert . - M. : Nauka: Literatură fizică și matematică, 1993. - 223 p. — (Logica matematică și fundamentele matematicii; Numărul nr. 26). — ISBN 502014326X .  (link indisponibil)
  3. ↑ Traducerea raportului lui Hilbert din germană - M. G. Shestopal și A. V. Dorofeev , publicat în cartea Problemele lui Hilbert / ed. P. S. Alexandrova . - M. : Nauka, 1969. - S. 39. - 240 p. — 10.700 de exemplare. Copie arhivată (link indisponibil) . Consultat la 13 noiembrie 2009. Arhivat din original la 17 octombrie 2011. 
  4. ↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900  (germană) . — Textul raportului citit de Hilbert la 8 august 1900 la al II-lea Congres Internaţional al Matematicienilor de la Paris. Consultat la 27 august 2009. Arhivat din original la 8 aprilie 2012.
  5. ↑ „Rational Integer” este sinonim cu „integer”, vezi Weisstein, Eric W. Rational Integer  (engleză) pe site-ul Wolfram MathWorld .
  6. ↑ V. I. Igoshin. § 36. Probleme algoritmice nerezolvabile // Logica matematică şi teoria algoritmilor. - M . : Academia, 2004. - S. 375. - 448 p. - 5100 de exemplare.  — ISBN 5-7695-1363-2 .
  7. ↑ Yuri Matiyasevici. A zecea problemă a lui Hilbert : Ce putem face cu ecuațiile diofantine  . Consultat la 27 august 2009. Arhivat din original la 10 aprilie 2012.
  8. ↑ Acest lucru este evidențiat și de formularea însăși a sarcinii într-un mod pozitiv: „man soll ein Verfahren angeben” („indicați cursul acțiunii”, și nu, de exemplu, „indicați dacă există o procedură”).
  9. ↑ 1 2 Iu. I. Hmelevski. Despre a zecea problemă a lui Hilbert // Problems of Hilbert / ed. P. S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. — 240 s. — 10.700 de exemplare. Copie arhivată (link indisponibil) . Consultat la 13 noiembrie 2009. Arhivat din original la 17 octombrie 2011. 
  10. ↑ F. P. Varpakhovsky, A. N. Kolmogorov . Despre rezolvarea celei de-a zecea probleme a lui Hilbert  // Kvant . - 1970. - Nr 7 . - S. 38-44 .
  11. ↑ A. A. Bolibrukh . A zecea problemă a lui Hilbert: ecuații diofantine // Probleme Hilbert (100 de ani mai târziu) . - M. : MTSNMO , 1999. - 24 p. - ( Biblioteca „Educația matematică” , nr. 2). - 3000 de exemplare.
  12. ↑ Simon Singh. Anexa 5. Dovada lui Euclid a existenței unui număr infinit de triple pitagoreice // Ultima Teoremă a lui Fermat = Ultima teoremă a lui Fermat / trad. din engleza. Yu. A. Danilova. - MTsNMO , 2000.
  13. ↑ Diophantus din Alexandria . Aritmetică și o carte despre numere poligonale / per. cu alte greci Iu N. Veselovsky. - M. : Nauka, 1974. - 328 p. - 17.500 de exemplare. Copie arhivată (link indisponibil) . Consultat la 13 noiembrie 2009. Arhivat din original pe 25 decembrie 2009. 
  14. ↑ Leonard Eugene Dickson. Istoria teoriei numerelor . - 1920. - Vol. II: Analiza diofantină.  (Engleză)
  15. ↑ A. Thue . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. clasă. - 1908. - Nr 3 . - S. 1-34 .
  16. ↑ Thoralf Skolem. Diophantische Gleichungen. - Berlin: Springer, 1938. - 128 p.
  17. ↑ Articolul lui Markov - A. A. Markov . Imposibilitatea unor algoritmi în teoria sistemelor asociative // ​​Rapoarte ale Academiei de Științe a URSS. - M. , 1947. - T. 55 , nr. 7 . - S. 587-590 . , vezi şi monografia lui A. A. Markov . Teoria algoritmilor  // Proceedings of the Mathematical Institute of the URSS Academy of Sciences. V. A. Steklova. - M. - L .: Editura Academiei de Științe a URSS, 1954. - T. 42 . - S. 3-375 .
  18. ↑ Rezultatul Post a fost publicat într-un articol EL Post . Nerezolvarea recursive a unei probleme a lui Thue  //  Jurnalul de logică simbolică. - 1947. - Vol. 12 , nr. 1 . - P. 1-11 .
  19. ↑ Emil Leon Post . Seturi recursive enumerabile de numere întregi pozitive și problemele lor de decizie  //  Bulletin of the American Mathematical Society. - 1944. - Vol. 50 , iss. 5 . - P. 284-316 .
  20. ↑ În tradiția matematică americană, 0 este un număr natural.
  21. ↑ Martin Davis. Probleme aritmetice și predicate enumerabile recursiv  //  Jurnalul de logică simbolică. - 1953. - Vol. 18 , nr. 1 . - P. 33-41 .
  22. ↑ Yu. V. Matiyasevici . A zecea problemă a lui Hilbert: Ecuații diofantine în secolul XX // Evenimente matematice ale secolului XX = Evenimente matematice ale secolului XX / ed. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 p. — ISBN 3-540-23235-4 .  (Engleză)
  23. ↑ Julia Robinson. Definibilitate existențială în aritmetică  //  Tranzacții ale Societății Americane de Matematică. - 1952. - Vol. 72 , nr. 3 . - P. 437-449 .
  24. ↑ Martin Davis, Hilary Putnam. Reduceri ale celei de-a zecea probleme a lui Hilbert  //  The Journal of Symbolic Logic. - 1958. - Vol. 23 , nr. 2 . - P. 183-187 .
  25. ↑ Martin Davis, Hilary Putnam, Julia Robinson. Problema de decizie pentru ecuațiile exponențiale diofantine  //  Analele matematicii. - 1961. - Vol. 74 , nr. 3 . - P. 425-436 .
  26. ↑ Iu. V. Matiyasevici . Inrezolvabilitatea algoritmică a ecuațiilor exponențiale-diofantine cu trei necunoscute // Studii în teoria algoritmilor și a logicii matematice / ed. A. A. Markov și V. I. Homici. - M . : Nauka, 1979. - Numărul. 3 . - S. 69-78 .
  27. ↑ „A zecea problemă a lui Julia Robinson și Hilbert  ” . — ZALA Films. Consultat la 27 august 2009. Arhivat din original la 10 aprilie 2012.
  28. ↑ Carol Wood. Recenzie de film: Julia Robinson și a zecea problemă a lui Hilbert  //  Notices of the American Mathematical Society. - 2008. - Vol. 55 , nr. 5 . - P. 573-575 . — ISSN 00029920 .
  29. ↑ Margaret A. M. Murray. Un film propriu  //  College Mathematics Journal. — Washington, DC: Asociația Matematică din America , 2009. — Vol. 40 , nr. 4 . - P. 306-310 . — ISSN 07468342 .

Literatură

Link -uri

 Probleme Hilbert