Hilberts tiende problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. oktober 2021; verifikation kræver 1 redigering .

Hilberts tiende problem er et af 23 problemer , som David Hilbert foreslog den 8. august 1900 ved II International Congress of Mathematicians . Det består i at finde en universel metode til at bestemme solvabiliteten af en vilkårlig algebraisk diophantisk ligning . Beviset for den algoritmiske uløselighed af dette problem tog omkring tyve år og blev afsluttet af Yuri Matiyasevich i 1970 [1] [2] .

Udtalelse af problemet

I Hilberts rapport er formuleringen af det tiende problem den korteste af alle:

Lad en diofantligning være givet med vilkårlige ukendte og heltals rationelle numeriske koefficienter. Angiv en metode, hvormed det efter et begrænset antal operationer er muligt at bestemme, om denne ligning kan løses i rationelle heltal [3] .

Originaltekst (tysk)[ Visskjule] Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rational Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die Gleichung in ganzen rational Zahlen [4] lösbar ist .

Formelt taler vi om en heltal [5] løsning af formens ligninger

P(x_{1},x_{2},\ldots,x_{n})=0,

hvor er et polynomium med heltalskoefficienter og heltalseksponenter [6] . Graden af ligningen er lig med graden af polynomiet . $P$ $P$

Af alle de 23 problemer er det det eneste problem med løselighed [7] . Tilsyneladende troede Hilbert, at den ønskede metode eksisterer og vil blive fundet før eller siden [8] . Spørgsmålet om, at en sådan metode måske ikke eksisterede i princippet, opstod ikke på Hilberts tid [9] [10] .

Baggrund

Heltalsløsningen af algebraiske ligninger har været interessant for matematikere siden oldtiden . For eksempel blev der lagt stor vægt på ligningen : hvis dens løsning var et sæt naturlige tal , så kunne en retvinklet trekant opnås fra segmenter af længde [11] med en sætning omvendt til Pythagoras sætning . Euklid gav formler til at finde alle heltalsløsninger af denne ligning [12] . Nogle typer af ligninger af anden grad og deres systemer blev overvejet af Diophantus af Alexandria [13] , hans værker blev senere brugt af Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss og andre matematikere involveret i talteori . Især fremsatte Fermat sin berømte hypotese . I 1768 havde Lagrange fuldt ud undersøgt spørgsmålet om heltalsløsninger til enhver ligning af anden grad i to ubekendte [14] . $x^{2}+y^{2}=z^{2}$ $x_{0},y_{0},z_{0}$ $x_{0},y_{0},z_{0}$

I løbet af det 19. århundrede forsøgte mange matematikere, der løste Fermats sidste sætning , at studere diofantiske ligninger med højere grad end den anden. Ikke desto mindre forblev problemet med at løse sådanne ligninger åbent : ingen generel metode blev opnået, kun specielle metoder blev fundet for ligninger af visse typer. Mest sandsynligt havde Hilbert mistanke om, at yderligere forskning på dette område ville føre til skabelsen af detaljerede og dybe teorier, ikke begrænset til diophantiske ligninger, og dette fik ham til at liste problemet til sin rapport [9] .

Løsningshistorik

Søg efter en algoritme

Indtil 1940'erne blev der forsket i det tiende problem i retning af at finde den nødvendige algoritme for i det mindste nogle klasser af diofantiske ligninger. Få år efter Hilberts rapport, i 1908, viste Axel Thue , at Thue-ligningen for to ukendte ikke kan have uendeligt mange heltalsløsninger [15] . I 1938 udgav Turalf Skolem en metode til at studere diofantiske ligninger af formen hvor er en ufuldstændig nedbrydelig form ( et irreducerbart polynomium , der udvider sig i feltet af rationelle tal til et produkt af lineære faktorer ), som opfylder visse betingelser [16] . På trods af Thues resultat trodsede selv ligninger med to ukendte enhver anstrengelse fra matematikere (algoritmen til at løse ligninger med én ukendt følger af Bézouts sætning ). $P(x_{1},x_{2},\ldots,x_{n})=0,$ $P$ $m$ $m>n$

I midten af 1930'erne blev forestillingen om en algoritme formaliseret , og de første eksempler på algoritmisk uafgørelige mængder i matematisk logik dukkede også op . Et vigtigt øjeblik var Andrei Markovs og Emil Posts (uafhængigt af hinanden) bevis på Thue-problemets uløselighed i 1947 [17] [18] . Dette var det første bevis på uløseligheden af et algebraisk problem. Det, såvel som de vanskeligheder, forskere af diophantiske ligninger står over for, førte til den antagelse, at den algoritme, som Hilbert krævede, ikke eksisterer. Lidt tidligere, i 1944, skrev Emil Post allerede i et af sine papirer, at det tiende problem " beder om et uløselighedsbevis" [ 19] .

Davis hypotese

Posts ord inspirerede studerende Martin Davis til at lede efter et bevis på, at det tiende problem var uløseligt. Davis flyttede fra sin formulering i heltal til en formulering i naturlige tal , hvilket er mere naturligt for teorien om algoritmer [20] . Det er to forskellige opgaver, men hver af dem bunder i den anden. I 1953 udgav han et papir, hvori han skitserede en måde at løse det tiende problem i naturlige tal [21] .

Davis, sammen med de klassiske diophantiske ligninger, betragtede deres parametriske version:

P(a_{1},\ldots,a_{n},x_{1},\ldots,x_{m})=0,

hvor et polynomium med heltalskoefficienter kan opdeles i to dele - parametre og variabler For et sæt parameterværdier kan ligningen have en løsning, for en anden findes der måske ikke løsninger. Davies udpegede sættet , som indeholder alle sæt parameterværdier ( -s), som ligningen har en løsning til: $P$ $a_{1},\ldots ,a_{n}$ $x_{1},\ldots,x_{m}.$ $M$ $n$

\{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(a_{1},\ldots, a_{n},x_{1},\ldots,x_{m})=0.

Han kaldte en sådan notation for en diofantisk fremstilling af et sæt, og selve sættet blev også kaldt diofantisk . For at bevise uløseligheden af det tiende problem, var det kun nødvendigt at vise, at ethvert numerabelt sæt er Diophantine , det vil sige at vise muligheden for at konstruere en ligning, der kun ville have naturlige rødder for alle , der tilhørte denne numerable mængde: da blandt de talløse mængder, der er uløselige , så, hvis man tager det uløselige sæt som grundlag, ville det være umuligt at opnå en generel metode, der ville afgøre en efter en, om en ligning har naturlige rødder på dette sæt. Alt dette førte Davis til følgende hypotese: $x_{1},\ldots ,x_{m}$ $\{a_{1},\ldots ,a_{n}\}$ $M$ $n$

Begreberne Diophantine og talløse sæt falder sammen. Det betyder, at et sæt er diofant, hvis og kun hvis det er talbart.

Davis tog også det første skridt - han beviste, at ethvert utalligt sæt kan repræsenteres som: $M$

\{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists z\forall y<z\exists x_{1},\ldots ,x_{m}\colon P( a_{1},\ldots,a_{n},x_{1},\ldots,x_{m},y,z)=0.

Denne repræsentation kaldes "Davis normal form". På det tidspunkt lykkedes det ham ikke at bevise sin formodning ved at slippe af med den universelle kvantifier .

Robinsons hypotese

Uafhængigt af Davis begyndte Julia Robinson at arbejde på det tiende problem i de samme år . Indledningsvis forsøgte hun at bevise Alfred Tarskis formodning om, at sættet af alle magter af to ikke er diophantisk, men det lykkedes ikke [22] . Derefter gik Robinson videre til at undersøge spørgsmålet om, hvorvidt et sæt bestående af tripler er Diophantine . Det lykkedes ikke for hende at finde en diofantisk repræsentation for eksponentieringsoperationen, men ikke desto mindre viste hun i sit arbejde [23] en tilstrækkelig betingelse for dens eksistens: $\{a,b,c=a^{b}\}$

\{u,v\}\in R\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(u,v,x_{1},\ldots,x_{m}) =0,

i øvrigt:

hvis , så $\{u,v\}\in R$ $u<v^{v},$
for nogen der findes sådan, at og $k$ $u$ $v$ $\{u,v\}\in R$ $u>v^{k}.$

Robinson kaldte forholdet mellem og " eksponentiel vækstafhængighed ", men senere begyndte denne afhængighed at blive kaldt til hendes ære - "Robinson-afhængighed", "Robinson-prædikater" eller blot "JR". $u$ $v$

Forenede kræfter

I 1958 udgav Martin Davis og Hilary Putnam [24] , hvor de, baseret på Robinsons resultat, betragtede en klasse af eksponentiel-diofantiske ligninger, der har formen:

E_{L}(x_{1},\ldots,x_{m})=E_{R}(x_{1},\ldots,x_{m}),

hvor og er eksponentielle polynomier, det vil sige udtryk opnået fra variabler og rationelle tal ved hjælp af operationerne addition , multiplikation og eksponentiering , og viste også en diophantinsk repræsentation for sådanne ligninger. Beviset for Davis og Putnam indeholdt imidlertid et hul - de brugte formodningen om eksistensen af vilkårligt lange aritmetiske progressioner , der kun består af primtal ( Green-Tao-sætning ), som først blev bevist i 2004. $E_{L}$ $E_{R}$

I 1961 var Julia Robinson i stand til at udfylde dette hul . I deres fælles arbejde [25] blev en eksponentiel diophantinsk repræsentation opnået for ethvert utalligt sæt:

\{a_{1},\ldots ,a_{n}\}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon E_{L}(a_{1}, \ldots ,a_{n},x_{1},\ldots ,x_{m})=E_{R}(a_{1},\ldots,a_{n},x_{1},\ldots,x_{ m}).

En af konsekvenserne af arbejdet var muligheden for at reducere enhver eksponentiel diophantisk ligning til en eksponentiel diophantisk ligning med et fast antal variable (mindst tre [26] ).

For at overføre resultatet af Davies, Putnam og Robinson til de "almindelige" diophantinske ligninger, skulle man bevise, at mængden bestående af tripler er diophantinsk. Så ville det være muligt, på bekostning af at introducere yderligere ukendte, at oversætte den eksponentielt diophantinske repræsentation til en diophantinsk repræsentation: $\{a,b,c=a^{b}\}$

c=a^{b}\Longleftrightarrow \exists x_{1},\ldots ,x_{m}\colon P(a,b,c,x_{1},\ldots ,x_{m})= 0.

Med andre ord, for fuldt ud at bevise Davis-formodningen var det kun nødvendigt at bevise et bestemt tilfælde af den, eller mere præcist at bevise Robinson-formodningen (for at finde et polynomium , der opfylder alle betingelserne). $P(u,v,x_{1},\ldots,x_{m})$

På trods af den dybe undersøgelse af to-parameter Diophantine-ligninger siden Diophantus selvs tid, var der på det tidspunkt ingen kendt ligning, der udtrykte afhængigheden af eksponentiel vækst. Forsøg på kunstigt at konstruere det mislykkedes også.

Indflydelse

I 2008 havde Julia Robinson og Hilberts tiende problem , en timelang dokumentar instrueret af George Csicsery, premiere . Filmen er dedikeret til Julia Robinson og hendes bidrag til løsningen af det tiende problem [27] . Filmen modtog anmeldelser og anmeldelser fra amerikanske matematiske tidsskrifter og samfund [28] [29] .

Noter

↑ Yu. V. Matiyasevich . Diofantisk ejendom af utallige sæt // Rapporter fra USSR's Videnskabsakademi. - 1970. - T. 191 , nr. 2 . - S. 279-282 .
↑ Yu. V. Matiyasevich . Hilberts tiende problem . - M. : Nauka: Fysisk og matematisk litteratur, 1993. - 223 s. — (Matematisk logik og matematikkens grundlag; hæfte nr. 26). — ISBN 502014326X . (utilgængeligt link)
↑ Oversættelse af Hilberts rapport fra tysk - M. G. Shestopal og A. V. Dorofeev , udgivet i bogen Hilberts problemer / red. P.S. Alexandrova . - M. : Nauka, 1969. - S. 39. - 240 s. — 10.700 eksemplarer. Arkiveret kopi (ikke tilgængeligt link) . Hentet 13. november 2009. Arkiveret fra originalen 17. oktober 2011. (ubestemt)
↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900 (tysk) . — Tekst til rapporten læst af Hilbert den 8. august 1900 ved den II Internationale Mathematicians Congress i Paris. Hentet 27. august 2009. Arkiveret fra originalen 8. april 2012.
↑ "Rational Integer" er synonymt med "integer", se Weisstein, Eric W. Rational Integer (engelsk) på Wolfram MathWorld- webstedet .
↑ V. I. Igoshin. § 36. Uløselige algoritmiske problemer // Matematisk logik og teori om algoritmer. - M . : Akademiet, 2004. - S. 375. - 448 s. - 5100 eksemplarer. — ISBN 5-7695-1363-2 .
↑ Yuri Matiyasevich. Hilberts tiende problem : Hvad kan vi gøre med diofantiske ligninger . Hentet 27. august 2009. Arkiveret fra originalen 10. april 2012.
↑ Det vidner også selve opgavens ordlyd positivt om: "man soll ein Verfahren angeben" ("angiv handlingsforløbet", og ikke f.eks. "angiv, om der er en procedure").
↑ 1 2 Yu. I. Khmelevsky. Om det tiende problem af Hilbert // Problems of Hilbert / red. P.S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. - 240 sek. — 10.700 eksemplarer. Arkiveret kopi (ikke tilgængeligt link) . Hentet 13. november 2009. Arkiveret fra originalen 17. oktober 2011. (ubestemt)
↑ F. P. Varpakhovsky, A. N. Kolmogorov . Om løsningen af Hilberts tiende problem // Kvant . - 1970. - Nr. 7 . - S. 38-44 .
↑ A. A. Bolibrukh . Hilberts tiende problem: diofantiske ligninger // Hilbert-problemer (100 år senere) . - M .: MTSNMO , 1999. - 24 s. - ( Bibliotek "Matematisk Uddannelse" , hæfte nr. 2). - 3000 eksemplarer.
↑ Simon Singh. Bilag 5. Euklids bevis for eksistensen af et uendeligt antal pythagoræiske tripler // Fermats sidste sætning = Fermats sidste sætning / transl. fra engelsk. Yu. A. Danilova. — MTsNMO , 2000.
↑ Diophantus af Alexandria . Aritmetik og en bog om polygonale tal / pr. med andre græske Yu. N. Veselovsky. - M. : Nauka, 1974. - 328 s. - 17.500 eksemplarer. Arkiveret kopi (ikke tilgængeligt link) . Hentet 13. november 2009. Arkiveret fra originalen 25. december 2009. (ubestemt)
↑ Leonard Eugene Dickson. Talteoriens historie . - 1920. - Bind II: Diophantinanalyse. (Engelsk)
↑ A. Thue . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. klasse. - 1908. - Nr. 3 . - S. 1-34 .
↑ Thoralf Skolem. Diophantische Gleichungen. - Berlin: Springer, 1938. - 128 s.
↑ Markovs artikel - A. A. Markov . Umuligheden af nogle algoritmer i teorien om associative systemer // Rapporter fra USSR's Videnskabsakademi. - M. , 1947. - T. 55 , no. 7 . - S. 587-590 . , se også monografien af A. A. Markov . Teori om algoritmer // Proceedings 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 .
↑ Posts resultat blev offentliggjort i en EL Post -artikel . Rekursiv uløselighed af et problem af Thue // The Journal of Symbolic Logic. - 1947. - Bd. 12 , nr. 1 . - S. 1-11 .
↑ Emil Leon Post . Rekursivt talløse sæt positive heltal og deres beslutningsproblemer // Bulletin of the American Mathematical Society. - 1944. - Bd. 50 , iss. 5 . - S. 284-316 .
↑ I den amerikanske matematiske tradition er 0 et naturligt tal.
↑ Martin Davis. Aritmetiske problemer og rekursivt enumerable prædikater // The Journal of Symbolic Logic. - 1953. - Bd. 18 , nr. 1 . - S. 33-41 .
↑ Yu. V. Matiyasevich . Hilberts tiende problem: Diofantiske ligninger i det tyvende århundrede // Matematiske begivenheder i det tyvende århundrede = Matematiske begivenheder i det 20. århundrede / udg. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 s. — ISBN 3-540-23235-4 . (Engelsk)
↑ Julia Robinson. Eksistentiel definerbarhed i aritmetik // Transactions of the American Mathematical Society. - 1952. - Bd. 72 , nr. 3 . - S. 437-449 .
↑ Martin Davis, Hilary Putnam. Reduktioner af Hilberts tiende problem // The Journal of Symbolic Logic. - 1958. - Bd. 23 , nr. 2 . - S. 183-187 .
↑ Martin Davis, Hilary Putnam, Julia Robinson. Beslutningsproblemet for eksponentielle diophantiske ligninger // Annals of Mathematics. - 1961. - Bd. 74 , nr. 3 . - S. 425-436 .
↑ Yu. V. Matiyasevich . Algoritmisk uløselighed af eksponentiel-diofantiske ligninger med tre ubekendte // Studier i teorien om algoritmer og matematisk logik / red. A. A. Markov og V. I. Khomich. - M . : Nauka, 1979. - Udgave. 3 . - S. 69-78 .
↑ "Julia Robinson og Hilberts tiende problem " . — ZALA-film. Hentet 27. august 2009. Arkiveret fra originalen 10. april 2012.
↑ Carol Wood. Filmanmeldelse: Julia Robinson og Hilberts tiende problem // Notices of the American Mathematical Society. - 2008. - Bd. 55 , nr. 5 . - S. 573-575 . — ISSN 00029920 .
↑ Margaret A. M. Murray. En egen film // College Mathematics Journal. — Washington, DC: Mathematical Association of America , 2009. — Vol. 40 , nej. 4 . - S. 306-310 . — ISSN 07468342 .

Litteratur

Yu. V. Matiyasevich . Hilberts tiende problem . - M . : Nauka, 1993. - ISBN 502014326X . (utilgængeligt link)
F. P. Varpakhovsky, A. N. Kolmogorov . Om løsningen af Hilberts tiende problem // Kvant . - 1970. - Nr. 7 . - S. 38-44 .
Yu. I. Khmelevsky. Om det tiende problem af Hilbert // Problems of Hilbert / red. P.S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. - 240 sek. — 10.700 eksemplarer. Arkiveret 17. oktober 2011 på Wayback Machine
K. M. Podnieks. Kapitel 4. Hilberts tiende opgave // Omkring Gödels sætning . - Riga: Zinatne, 1992. - 191 s.
Yu. V. Matiyasevich . Hilberts tiende problem: Diofantiske ligninger i det tyvende århundrede // Matematiske begivenheder i det tyvende århundrede = Matematiske begivenheder i det 20. århundrede / udg. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 s. — ISBN 3-540-23235-4 . (Engelsk)
Hilberts tiende problem: forhold til aritmetisk og algebraisk geometri. Workshop om Hilberts tiende problem: relationer med aritmetisk og algebraisk geometri, 2-5 november 1999, Gent Universitet, Belgien / red. Jan Denef, Leonard Lipshitz, Thanases Pheidas, Jan Van Geel. — Samtidens matematik. - 2000. - T. 270. - 367 s. - ISBN 0-8218-2622-0 . (Engelsk)

Links

Maxim Vsemirnov, Yuri Matiyasevich. Hilberts tiende problemside . Hentet 27. august 2009. Arkiveret fra originalen 10. april 2012.
Hilberts 10. problem: A History of Mathematical Discovery (utilgængeligt link) . Hentet 27. august 2009. Arkiveret fra originalen 16. december 2010. (ubestemt)
Yuri Matiyasevich. Hilberts tiende problem : Hvad kan vi gøre med diofantiske ligninger . Hentet 27. august 2009. Arkiveret fra originalen 10. april 2012.
Zhi Wei Sun. Om Hilberts tiende problem og relaterede emner ( 14. april 2000). Hentet 29. august 2009. Arkiveret fra originalen 10. april 2012.
Panu Raatikainen. Problemet med den enkleste diofantiske repræsentation . Hentet 29. august 2009. Arkiveret fra originalen 10. april 2012.

Hilbert problemer
en 2 3 fire 5 6 7 otte 9 ti elleve 12 13 fjorten femten 16 17 atten 19 tyve 21 22 23 ( 24 )