Hilberts tionde problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 oktober 2021; verifiering kräver 1 redigering .

Hilberts tionde problem är ett av 23 problem som David Hilbert föreslog den 8 augusti 1900 vid II International Congress of Mathematicians . Det består i att hitta en universell metod för att bestämma lösbarheten av en godtycklig algebraisk diofantisk ekvation . Beviset på den algoritmiska olösligheten av detta problem tog cirka tjugo år och fullbordades av Jurij Matiyasevich 1970 [1] [2] .

Förklaring av problemet

I Hilberts rapport är formuleringen av det tionde problemet den kortaste av alla:

Låt en diofantisk ekvation ges med godtyckliga okända och heltalsrationella numeriska koefficienter. Ange en metod genom vilken det är möjligt, efter ett ändligt antal operationer, att avgöra om denna ekvation är lösbar i rationella heltal [3] .

Originaltext (tyska)[ visaDölj] 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 rationalen Zahlen [4] lösbar ist .

Formellt talar vi om en heltalslösning [5] av formens ekvationer

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

där är ett polynom med heltalskoefficienter och heltalsexponenter [6] . Graden av ekvationen är lika med graden av polynomet . $P$ $P$

Av alla 23 problem är det det enda problemet med lösbarhet [7] . Tydligen trodde Hilbert att den önskade metoden finns och kommer att hittas förr eller senare [8] . Frågan om att en sådan metod kanske inte existerade i princip uppstod inte på Hilberts tid [9] [10] .

Bakgrund

Heltalslösningen av algebraiska ekvationer har varit av intresse för matematiker sedan urminnes tider. Till exempel ägnades mycket uppmärksamhet åt ekvationen : om dess lösning var en uppsättning naturliga tal , så genom en sats omvänd till Pythagoras sats , kunde en rätvinklig triangel erhållas från längdsegment [11] . Euklid gav formler för att hitta alla heltalslösningar av denna ekvation [12] . Vissa typer av ekvationer av andra graden och deras system övervägdes av Diophantus av Alexandria [13] , hans verk användes senare av Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss och andra matematiker involverade i talteori . I synnerhet lade Fermat fram sin berömda hypotes . År 1768 hade Lagrange till fullo utforskat frågan om heltalslösningar till alla ekvationer av andra graden i två okända [14] . $x^{2}+y^{2}=z^{2}$ $x_{0},y_{0},z_{0}$ $x_{0},y_{0},z_{0}$

Under 1800-talet försökte många matematiker, som löste Fermats sista sats , att studera diofantiska ekvationer med högre grad än den andra. Ändå förblev problemet med att lösa sådana ekvationer öppet : ingen allmän metod erhölls, endast speciella metoder hittades för ekvationer av vissa typer. Mest troligt misstänkte Hilbert att ytterligare forskning inom detta område skulle leda till skapandet av detaljerade och djupa teorier, inte begränsade till diofantiska ekvationer, och detta fick honom att lista problemet för sin rapport [9] .

Lösningshistorik

Sök efter en algoritm

Fram till 1940-talet utfördes forskning på det tionde problemet i riktning mot att hitta den erforderliga algoritmen för åtminstone några klasser av diofantiska ekvationer. Några år efter Hilberts rapport, 1908, visade Axel Thue att Thue-ekvationen för två okända inte kan ha oändligt många heltalslösningar [15] . År 1938 publicerade Turalf Skolem en metod för att studera diofantiska ekvationer av formen där är en ofullständig nedbrytbar form ( ett irreducerbart polynom som expanderar inom området för rationella tal till en produkt av linjära faktorer, ) som uppfyller vissa villkor [16] . Trots Thues resultat trotsade även ekvationer med två okända alla ansträngningar av matematiker (algoritmen för att lösa ekvationer med en okänd följer av Bézouts teorem ). $P(x_{1},x_{2},\ldots,x_{n})=0,$ $P$ $m$ $m>n$

I mitten av 1930-talet formaliserades föreställningen om en algoritm , och de första exemplen på algoritmiskt obestämbara uppsättningar inom matematisk logik dök också upp . Ett viktigt ögonblick var beviset av Andrei Markov och Emil Post (oberoende av varandra) på Thue-problemets olöslighet 1947 [17] [18] . Detta var det första beviset på olösligheten av ett algebraiskt problem. Det, liksom de svårigheter som forskare av diofantiska ekvationer står inför, ledde till antagandet att den algoritm som Hilbert kräver inte existerar. Lite tidigare, 1944, skrev Emil Post redan i en av sina tidningar att det tionde problemet " begär ett olöslighetsbevis" [ 19] .

Davis hypotes

Posts ord inspirerade studenten Martin Davis att leta efter ett bevis på att det tionde problemet var oavgörbart. Davis flyttade från sin formulering i heltal till en formulering i naturliga tal , vilket är mer naturligt för teorin om algoritmer [20] . Det är två olika uppgifter, men var och en av dem kokar ner till den andra. 1953 publicerade han en artikel där han beskrev ett sätt att lösa det tionde problemet i naturliga tal [21] .

Davis, tillsammans med de klassiska diofantiska ekvationerna, ansåg deras parametriska version:

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

där ett polynom med heltalskoefficienter kan delas upp i två delar - parametrar och variabler. För en uppsättning parametervärden kan ekvationen ha en lösning, för en annan kanske lösningar inte existerar. Davies pekade ut uppsättningen , som innehåller alla uppsättningar av parametervärden ( -s) för vilka ekvationen har en lösning: $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 kallade en sådan notation för en diofantisk representation av en uppsättning, och själva uppsättningen kallades också för Diophantine . För att bevisa olösligheten av det tionde problemet var det bara nödvändigt att visa att varje uppräknad mängd är diofantin , det vill säga att visa möjligheten att konstruera en ekvation som endast skulle ha naturliga rötter för alla som tillhör denna uppräknbara mängd: eftersom bland numerera mängder det finns olösliga sådana , då, med den olösliga mängden som grund, skulle det vara omöjligt att få fram en generell metod som skulle avgöra en efter en om en ekvation har naturliga rötter på denna mängd. Allt detta ledde Davis till följande hypotes: $x_{1},\ldots ,x_{m}$ $\{a_{1},\ldots ,a_{n}\}$ $M$ $n$

Begreppen Diophantine och uppräknade uppsättningar sammanfaller. Det betyder att en uppsättning är diofantisk om och bara om den är uppräknad.

Davis tog också det första steget - han bevisade att vilken uppsättning som helst kan representeras 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.

Denna representation kallas "Davis normal form". Vid den tiden lyckades han inte bevisa sin gissning genom att bli av med den universella kvantifieraren .

Robinsons hypotes

Oberoende av Davis började Julia Robinson arbeta med det tionde problemet under samma år . Inledningsvis försökte hon bevisa Alfred Tarskis gissning att uppsättningen av alla krafter av två inte är diofantin, men lyckades inte [22] . Efter det gick Robinson vidare för att undersöka frågan om en uppsättning bestående av trippel är Diophantine . Hon lyckades inte hitta en diofantisk representation för exponentieringsoperationen, men ändå visade hon i sitt arbete [23] ett tillräckligt villkor för dess existens: $\{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,

dessutom:

om , då $\{u,v\}\in R$ $u<v^{v},$
för någon det finns sådana att och $k$ $u$ $v$ $\{u,v\}\in R$ $u>v^{k}.$

Robinson kallade förhållandet mellan och " exponentiellt tillväxtberoende ", men senare började detta beroende kallas till hennes ära - "Robinsonberoende", "Robinsonpredikat" eller helt enkelt "JR". $u$ $v$

Förenade krafter

År 1958 publicerade Martin Davis och Hilary Putnam [24] , där de, baserat på Robinsons resultat, ansåg en klass av exponentiell-diofantiska ekvationer som har formen:

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

där och är exponentiella polynom, det vill säga uttryck erhållna från variabler och rationella tal med hjälp av operationerna addition , multiplikation och exponentiering , och visade också en diofantisk representation för sådana ekvationer. Beviset för Davis och Putnam innehöll dock en lucka - de använde gissningen om existensen av godtyckligt långa aritmetiska progressioner som endast består av primtal ( Green-Tao theorem ), vilket bevisades först 2004. $E_{L}$ $E_{R}$

1961 kunde Julia Robinson fylla denna lucka . I deras gemensamma arbete [25] erhölls en exponentiell Diophantine-representation för vilken numerisk uppsättning som helst:

\{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 av konsekvenserna av arbetet var möjligheten att reducera valfri exponentiell diofantisk ekvation till en exponentiell diofantisk ekvation med ett fast antal variabler (minst tre [26] ).

För att föra över resultatet av Davies, Putnam och Robinson till de "vanliga" diofantiska ekvationerna var man tvungen att bevisa att uppsättningen som består av trippel är diofantisk. Då skulle det vara möjligt, till priset av att introducera ytterligare okända, att översätta den exponentiellt diofantiska representationen till en diofantisk representation: $\{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 andra ord, för att helt bevisa Davis-förmodan, var det bara nödvändigt att bevisa ett särskilt fall av den, eller, mer exakt, att bevisa Robinson-förmodan (för att hitta ett polynom som uppfyller alla villkor). $P(u,v,x_{1},\ldots,x_{m})$

Trots den djupa studien av tvåparameters diofantiska ekvationer sedan tiden för Diophantus själv, fanns det vid den tiden ingen känd ekvation som uttryckte beroendet av exponentiell tillväxt. Försöken att på konstgjord väg konstruera den misslyckades också.

Inflytande

2008 hade Julia Robinson och Hilberts tionde problem , en timslång dokumentär regisserad av George Csicsery, premiär . Filmen är tillägnad Julia Robinson och hennes bidrag till lösningen av det tionde problemet [27] . Filmen fick recensioner och recensioner från amerikanska matematiska tidskrifter och gemenskaper [28] [29] .

Anteckningar

↑ Yu. V. Matiyasevich . Diofantisk egendom av otaliga uppsättningar // Rapporter från USSR:s vetenskapsakademi. - 1970. - T. 191 , nr 2 . - S. 279-282 .
↑ Yu. V. Matiyasevich . Hilberts tionde problem . - M. : Nauka: Fysisk och matematisk litteratur, 1993. - 223 s. — (Matematisk logik och matematikens grunder; Nummer 26). — ISBN 502014326X . (inte tillgänglig länk)
↑ Översättning av Hilberts rapport från tyska - M. G. Shestopal och A. V. Dorofeev , publicerad i boken Hilberts problem / ed. P.S. Alexandrova . - M. : Nauka, 1969. - S. 39. - 240 sid. — 10 700 exemplar. Arkiverad kopia (inte tillgänglig länk) . Hämtad 13 november 2009. Arkiverad från originalet 17 oktober 2011. (obestämd)
↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900 (tyska) . — Text till rapporten läst av Hilbert den 8 augusti 1900 vid II International Congress of Mathematicians i Paris. Hämtad 27 augusti 2009. Arkiverad från originalet 8 april 2012.
↑ "Rational Integer" är synonymt med "integer", se Weisstein, Eric W. Rational Integer (engelska) på Wolfram MathWorld- webbplatsen .
↑ V. I. Igoshin. § 36. Olösbara algoritmiska problem // Matematisk logik och teori om algoritmer. - M . : Academy, 2004. - S. 375. - 448 sid. - 5100 exemplar. — ISBN 5-7695-1363-2 .
↑ Yuri Matiyasevich. Hilberts tionde problem : Vad kan vi göra med diofantiska ekvationer . Hämtad 27 augusti 2009. Arkiverad från originalet 10 april 2012.
↑ Detta bevisas också av själva formuleringen av uppgiften på ett positivt sätt: ”man soll ein Verfahren angeben” (”ange handlingsförloppet”, och inte t.ex. ”ange om det finns ett förfarande”).
↑ 1 2 Yu. I. Khmelevsky. På det tionde problemet av Hilbert // Problems of Hilbert / ed. P.S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. — 240 s. — 10 700 exemplar. Arkiverad kopia (inte tillgänglig länk) . Hämtad 13 november 2009. Arkiverad från originalet 17 oktober 2011. (obestämd)
↑ F. P. Varpakhovsky, A. N. Kolmogorov . Om lösningen av Hilberts tionde problem // Kvant . - 1970. - Nr 7 . - S. 38-44 .
↑ A. A. Bolibrukh . Hilberts tionde problem: diofantiska ekvationer // Hilbertproblem (100 år senare) . - M. : MTSNMO , 1999. - 24 sid. - ( Biblioteket "Mathematical Education" , nummer 2). - 3000 exemplar.
↑ Simon Singh. Appendix 5. Euklids bevis på att det finns ett oändligt antal Pythagoras trippel // Fermats sista sats = Fermats sista sats / transl. från engelska. Yu. A. Danilova. — MTsNMO , 2000.
↑ Diophantus av Alexandria . Aritmetik och en bok om polygonala tal / per. med andra greker Yu. N. Veselovsky. - M. : Nauka, 1974. - 328 sid. - 17 500 exemplar. Arkiverad kopia (inte tillgänglig länk) . Hämtad 13 november 2009. Arkiverad från originalet 25 december 2009. (obestämd)
↑ Leonard Eugene Dickson. Talteorin Historia . - 1920. - Volym II: Diophantine Analysis. (Engelsk)
↑ A. Thue . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. klass. - 1908. - Nr 3 . - S. 1-34 .
↑ Thoralf Skolem. Diophantische Gleichungen. - Berlin: Springer, 1938. - 128 sid.
↑ Markovs artikel - A. A. Markov . Omöjligheten av vissa algoritmer i teorin om associativa system // Rapporter från USSR:s vetenskapsakademi. - M. , 1947. - T. 55 , nr. 7 . - S. 587-590 . , se även monografi av A. A. Markov . Algoritmteori // 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 publicerades i en EL Post -artikel . Rekursiv olöslighet av ett problem av Thue // The Journal of Symbolic Logic. - 1947. - Vol. 12 , nr. 1 . - S. 1-11 .
↑ Emil Leon Post . Rekursivt uppräknade uppsättningar av positiva heltal och deras beslutsproblem // Bulletin of the American Mathematical Society. - 1944. - Vol. 50 , iss. 5 . - s. 284-316 .
↑ I den amerikanska matematiska traditionen är 0 ett naturligt tal.
↑ Martin Davis. Aritmetiska problem och rekursivt uppräknade predikat // The Journal of Symbolic Logic. - 1953. - Vol. 18 , nr. 1 . - S. 33-41 .
↑ Yu. V. Matiyasevich . Hilberts tionde problem: Diofantiska ekvationer under 1900-talet // Matematiska händelser under 1900-talet = XX-talets matematiska händelser / ed. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 sid. — ISBN 3-540-23235-4 . (Engelsk)
↑ Julia Robinson. Existentiell definierbarhet i aritmetik // Transactions of the American Mathematical Society. - 1952. - Vol. 72 , nr. 3 . - s. 437-449 .
↑ Martin Davis, Hilary Putnam. Reduktioner av Hilberts tionde problem // The Journal of Symbolic Logic. - 1958. - Vol. 23 , nr. 2 . - S. 183-187 .
↑ Martin Davis, Hilary Putnam, Julia Robinson. Beslutsproblemet för exponentiella diofantiska ekvationer // Annals of Mathematics. - 1961. - Vol. 74 , nr. 3 . - s. 425-436 .
↑ Yu. V. Matiyasevich . Algoritmisk olöslighet av exponentiell-diofantiska ekvationer med tre okända // Studier i teorin om algoritmer och matematisk logik / red. A.A. Markov och V.I. Khomich. - M . : Nauka, 1979. - Utgåva. 3 . - S. 69-78 .
↑ "Julia Robinson och Hilberts tionde problem " . — ZALA Films. Hämtad 27 augusti 2009. Arkiverad från originalet 10 april 2012.
↑ Carol Wood. Filmrecension: Julia Robinson och Hilberts tionde problem // Notices of the American Mathematical Society. - 2008. - Vol. 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 tionde problem . - M . : Nauka, 1993. - ISBN 502014326X . (inte tillgänglig länk)
F.P. Varpakhovsky, A.N. Kolmogorov . Om lösningen av Hilberts tionde problem // Kvant . - 1970. - Nr 7 . - S. 38-44 .
Yu. I. Khmelevsky. På det tionde problemet av Hilbert // Problems of Hilbert / ed. P.S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. — 240 s. — 10 700 exemplar. Arkiverad 17 oktober 2011 på Wayback Machine
K. M. Podnieks. Kapitel 4. Hilberts tionde problem // Runt Gödels sats . - Riga: Zinatne, 1992. - 191 sid.
Yu. V. Matiyasevich . Hilberts tionde problem: Diofantiska ekvationer under 1900-talet // Matematiska händelser under 1900-talet = XX-talets matematiska händelser / ed. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 sid. — ISBN 3-540-23235-4 . (Engelsk)
Hilberts tionde problem: samband med aritmetisk och algebraisk geometri. Workshop om Hilberts tionde problem: relationer med aritmetisk och algebraisk geometri, 2–5 november 1999, Ghent University, Belgien / red. Jan Denef, Leonard Lipshitz, Thanases Pheidas, Jan Van Geel. — Samtida matematik. - 2000. - T. 270. - 367 sid. - ISBN 0-8218-2622-0 . (Engelsk)

Länkar

Maxim Vsemirnov, Yuri Matiyasevich. Hilberts tionde problemsida . Hämtad 27 augusti 2009. Arkiverad från originalet 10 april 2012.
Hilberts 10:e problem: A History of Mathematical Discovery (inte tillgänglig länk) . Hämtad 27 augusti 2009. Arkiverad från originalet 16 december 2010. (obestämd)
Yuri Matiyasevich. Hilberts tionde problem : Vad kan vi göra med diofantiska ekvationer . Hämtad 27 augusti 2009. Arkiverad från originalet 10 april 2012.
Zhi Wei Sun. Om Hilberts tionde problem och relaterade ämnen ( 14 april 2000). Hämtad 29 augusti 2009. Arkiverad från originalet 10 april 2012.
Panu Raatikainen. Problemet med den enklaste diofantiska representationen . Hämtad 29 augusti 2009. Arkiverad från originalet 10 april 2012.

Hilbert problem
ett 2 3 fyra 5 6 7 åtta 9 tio elva 12 13 fjorton femton 16 17 arton 19 tjugo 21 22 23 ( 24 )