Hilberts tionde problem - Hilbert's tenth problem

Hilberts tionde problem är det tionde på listan över matematiska problem som den tyska matematikern David Hilbert ställde 1900. Det är utmaningen att tillhandahålla en allmän algoritm som för en given Diofantin-ekvation (en polynomekvation med heltalskoefficienter och ett begränsat antal okända), kan avgöra om ekvationen har en lösning där alla okända tar heltal.

Till exempel diofantiska ekvationen har ett heltal lösning: . Däremot har den diofantiska ekvationen ingen sådan lösning. ${\ displaystyle 3x ^ {2} -2xy-y ^ {2} z-7 = 0}$ ${\ displaystyle x = 1, \ y = 2, \ z = -2}$ ${\ displaystyle x ^ {2} + y ^ {2} + 1 = 0}$

Hilberts tionde problem har lösts och det har ett negativt svar: en sådan allmän algoritm finns inte. Detta är resultatet av ett kombinerat arbete av Martin Davis , Yuri Matiyasevich , Hilary Putnam och Julia Robinson som sträcker sig över 21 år, med Matiyasevich som slutförde satsen 1970. Satsen är nu känd som Matiyasevichs sats eller MRDP-satsen.

Bakgrund

Originalformulering

Hilbert formulerade problemet enligt följande:

Givet en diofantin ekvation med valfritt antal okända mängder och med rationella integrala numeriska koefficienter: Att utforma en process enligt vilken det kan bestämmas i ett begränsat antal operationer om ekvationen är lösbar i rationella heltal.

Orden "process" och "begränsat antal operationer" har förstått att Hilbert frågade efter en algoritm . Termen "rationellt heltal" hänvisar helt enkelt till heltal, positiva, negativa eller noll: 0, ± 1, ± 2, .... Så Hilbert bad om en allmän algoritm för att avgöra om en given polynom Diophantine-ekvation med heltalskoefficienter har en lösning i heltal.

Hilberts problem handlar inte om att hitta lösningarna. Den frågar bara om vi i allmänhet kan avgöra om det finns en eller flera lösningar. Svaret på denna fråga är negativt, i den meningen att ingen "process kan utformas" för att svara på den frågan. I moderna termer är Hilberts 10: e problem ett obeslutbart problem . Även om det är osannolikt att Hilbert hade tänkt på en sådan möjlighet, men innan han fortsatte med att lista upp problemen, påpekade han förut:

Ibland händer det att vi söker lösningen under otillräckliga hypoteser eller i felaktig mening och av den anledningen inte lyckas. Problemet uppstår då: att visa att lösningen är omöjlig under givna hypoteser eller i den mening som avses.

Att bevisa det 10: e problemet oavgörligt är då ett giltigt svar även i Hilberts termer, eftersom det är ett bevis på "omöjligheten till lösningen".

Diofantinuppsättningar

I en Diophantine-ekvation finns det två typer av variabler: parametrarna och de okända. Diophantine-uppsättningen består av de parametertilldelningar som Diophantine-ekvationen är lösbar för. Ett typiskt exempel är den linjära Diophantine-ekvationen i två okända,

{\ displaystyle a_ {1} x_ {1} + a_ {2} x_ {2} = a_ {3}}

,

där ekvationen är lösbar när den största gemensamma delaren av delar . Värdena som uppfyller denna begränsning är en Diophantine-uppsättning och ekvationen ovan är dess Diophantine-definition. ${\ displaystyle a_ {1}, a_ {2}}$ ${\ displaystyle a_ {3}}$ ${\ displaystyle a_ {1}, a_ {2}, a_ {3}}$

Diofantindefinitioner kan tillhandahållas av samtidiga ekvationssystem såväl som av individuella ekvationer eftersom systemet

{\ displaystyle p_ {1} = 0, \ ldots, p_ {k} = 0}

motsvarar den enskilda ekvationen

{\ displaystyle p_ {1} ^ {2} + \ cdots + p_ {k} ^ {2} = 0.}

Uppsättningar av naturliga tal, av par av naturliga tal (eller till och med av n- fyrtor av naturliga tal) som har diofantindefinitioner kallas diofantinuppsättningar . I dessa termer frågar Hilberts tionde problem om det finns en algoritm för att avgöra om en given Diophantine-uppsättning inte är tom.

Arbetet med problemet har varit i termer av lösningar i naturligt antal (förstås som icke-negativa heltal) snarare än godtyckliga heltal. De två problemen är ekvivalenta: vilken allmän algoritm som kan avgöra om en given Diophantine-ekvation har en heltalslösning kan modifieras till en algoritm som avgör om en given Diophantine-ekvation har en naturlig tallösning och vice versa. Detta kan ses på följande sätt: Kravet på att lösningar ska vara naturliga tal kan uttryckas med hjälp av Lagranges fyra-kvadratiska teorem : varje naturligt tal är summan av kvadraten på fyra heltal, så vi ersätter helt enkelt varje parameter med summan av rutor med fyra extra parametrar. På samma sätt, eftersom varje heltal kan skrivas som skillnaden mellan två naturliga tal, kan vi ersätta varje parameter som sträcker sig i heltal med skillnaden mellan två parametrar som sträcker sig i naturliga tal.

Rekursivt uppräkbara uppsättningar

En rekursivt uppräkningsbar uppsättning kan karakteriseras som en för vilken det finns en algoritm som slutligen kommer att stoppa när en medlem i uppsättningen tillhandahålls som ingång, men kan fortsätta på obestämd tid när ingången är en icke-medlem. Det var utvecklingen av beräknbarhetsteori (även känd som rekursionsteori) som gav en exakt beskrivning av den intuitiva uppfattningen om algoritmisk beräknbarhet, vilket gjorde uppfattningen om rekursiv uppräkbarhet helt rigorös. Det är uppenbart att Diophantine-uppsättningar är rekursivt uppräknade. Detta beror på att man kan ordna alla möjliga värden på de okända värdena i en sekvens och sedan, för ett givet värde av parametern / parametrarna, testa dessa tuples, en efter en, för att se om de är lösningar av motsvarande ekvation. Oupplösbarheten av Hilberts tionde problem är en följd av det överraskande faktum att det motsatta är sant:

Varje rekursivt räknas uppsättning är Diophantine.

Detta resultat är olika känt som Matiyasevichs sats (för att han tillhandahöll det avgörande steget som fullbordade beviset) och MRDP-satsen (för Yuri Matiyasevich , Julia Robinson , Martin Davis och Hilary Putnam ). Eftersom det finns en rekursivt uppräkningsbar uppsättning som inte kan beräknas, är lösbarheten i Hilberts tionde problem en omedelbar konsekvens. I själva verket kan mer sägas: det finns ett polynom

{\ displaystyle p (a, x_ {1}, \ ldots, x_ {n})}

med heltalskoefficienter så att den uppsättning värden för vilka ekvationen ${\ displaystyle a}$

{\ displaystyle p (a, x_ {1}, \ ldots, x_ {n}) = 0}

har lösningar i naturligt antal inte kan beräknas. Så det finns inte bara någon allmän algoritm för testning av diofantiska ekvationer för lösbarhet, inte ens för den här parameterfamiljen av ekvationer, det finns ingen algoritm.

Historia

År	evenemang
1944	Emil Leon Post förklarar att Hilberts tionde problem "ber om ett olösligt bevis".
1949	Martin Davis använder Kurt Gödels metod för att tillämpa den kinesiska restsatsen som ett kodningstrick för att få sin normala form för rekursivt uppräkbara uppsättningar: ${\ displaystyle \ left \ {a \ mid \ existerar y \ forall k \ leqslant y \ existerar x_ {1}, \ ldots, x_ {n}: p \ left (a, k, y, x_ {1}, \ ldots, x_ {n} \ right) = 0 \ right \}}$ var är ett polynom med heltalskoefficienter. Rent formellt är det bara den avgränsade universella kvantifieraren som står i vägen för att detta är en diofantisk definition. ${\ displaystyle p}$ Med hjälp av ett icke-konstruktivt men enkelt bevis, härleder han som en följd av denna normala form att uppsättningen Diophantine-uppsättningar inte är stängd under komplement, genom att visa att det finns en Diophantine-uppsättning vars komplement inte är Diophantine. Eftersom de rekursivt uppräknade uppsättningarna inte heller är stängda under komplement, antar han att de två klasserna är identiska.
1950	Julia Robinson , som inte är medveten om Davis arbete, undersöker kopplingen av den exponentiella funktionen till problemet och försöker bevisa att EXP, den uppsättning av tripletter för vilka , är Diophantine. Inte lyckas, hon gör följande hypotes (senare kallad JR): ${\ displaystyle (a, b, c)}$ ${\ displaystyle a = b ^ {c}}$ Det finns en Diophantine uppsättning par så att och för varje positivt det finns ett sådant sätt att ${\ displaystyle D}$ ${\ displaystyle (a, b)}$ ${\ displaystyle (a, b) \ i D \ Rightarrow b <a ^ {a}}$ ${\ displaystyle k,}$ ${\ displaystyle (a, b) \ i D}$ ${\ displaystyle b> a ^ {k}.}$ Med hjälp av egenskaperna för Pell-ekvationen, bevisar hon att JR antyder att EXP är diofantin, liksom binomialkoefficienter, faktoria och primtal.
1959	Genom att arbeta tillsammans studerar Davis och Putnam exponentiella Diophantine-uppsättningar : uppsättningar som kan definieras med Diophantine-ekvationer där några av exponenterna kan vara okända. Med Davis normala form tillsammans med Robinsons metoder och under antagande av den då obevisade antagandet att det finns godtyckligt långa aritmetiska framsteg bestående av primtal , bevisar de att varje rekursivt uppräkningsbart uppsättning är exponentiell diofantin. De bevisar också som en följd att JR antyder att varje rekursivt räknas uppsättning är Diophantine, vilket i sin tur innebär att Hilberts tionde problem är olösligt.
1960	Robinson förenklar beviset för det villkorliga resultatet för exponentiella Diophantine-uppsättningar och gör det oberoende av antagandet om primtal och därmed en formell sats. Detta gör JR-hypotesen till ett tillräckligt villkor för att Hilberts tionde problem inte kan lösas. Men många tvivlar på att JR är sant.
1961–1969	Under denna period hittar Davis och Putnam olika förslag som antyder att JR, och Robinson, som tidigare visat att JR antyder att uppsättningen av primtal är en diofantisk uppsättning, visar att detta är ett om och bara om villkor. Yuri Matiyasevich publicerar några minskningar av Hilberts tionde problem.
1970	Med tanke på det nyligen publicerade arbetet av Nikolai Vorob'ev om Fibonacci-nummer visar Matiyasevich att uppsättningen där är det n: ^eFibonacci-numret , är Diophantine och uppvisar exponentiell tillväxt. Detta bevisar JR-hypotesen, som då hade varit en öppen fråga i 20 år. Att kombinera JR med satsen att varje rekursivt uppräkningsbart uppsättning är exponentiell diofantin, visar att rekursivt uppräkbara uppsättningar är diofantin. Detta gör Hilberts tionde problem olösligt. ${\ displaystyle P = \ {(a, b) \| a> 0, b = F_ {2a} \},}$ ${\ displaystyle F_ {n}}$

Applikationer

Matiyasevich / MRDP-satsen relaterar till två begrepp - en från beräkbarhetsteori, den andra från talteori - och har några överraskande konsekvenser. Det kanske mest överraskande är förekomsten av en universell diofantin ekvation:

Det finns ett polynom så att, med tanke på varje Diophantine-uppsättning, finns det ett sådant tal som

{\ displaystyle p (a, n, x_ {1}, \ ldots, x_ {k})}

{\ displaystyle S}

{\ displaystyle n_ {0}}

{\ displaystyle S = \ {\, a \ mid \ existerar x_ {1}, \ ldots, x_ {k} [p (a, n_ {0}, x_ {1}, \ ldots, x_ {k}) = 0] \, \}.}

Detta stämmer helt enkelt för att diofantiska uppsättningar, lika med rekursivt uppräkbara uppsättningar, också är lika med Turing-maskiner . Det är en välkänd egenskap hos Turing-maskiner att det finns universella Turing-maskiner som kan utföra vilken algoritm som helst.

Hilary Putnam har påpekat att för varje Diophantine-uppsättning positiva heltal finns det ett polynom ${\ displaystyle S}$

{\ displaystyle q (x_ {0}, x_ {1}, \ ldots, x_ {n})}

sådana som består av exakt de positiva siffrorna bland de värden som antas som variablerna ${\ displaystyle S}$ ${\ displaystyle q}$

{\ displaystyle x_ {0}, x_ {1}, \ ldots, x_ {n}}

räckvidd över alla naturliga tal. Detta kan ses på följande sätt: Om

{\ displaystyle p (a, y_ {1}, \ ldots, y_ {n}) = 0}

ger en Diophantine-definition av , då räcker det att ställa in ${\ displaystyle S}$

{\ displaystyle q (x_ {0}, x_ {1}, \ ldots, x_ {n}) = x_ {0} [1-p (x_ {0}, x_ {1}, \ ldots, x_ {n} ) ^ {2}].}

Så till exempel finns det ett polynom för vilket den positiva delen av dess intervall är exakt primtalen. (Å andra sidan kan inget polynom bara ta på sig primärvärden.) Samma sak gäller för andra rekursivt uppräkbara uppsättningar av naturliga tal: faktoria, binomialkoefficienter, Fibonacci-tal etc.

Andra applikationer gäller vad logiker kallar propositioner, ibland även kallade propositioner av Goldbach-typ . Dessa är som Goldbachs gissningar , när de säger att alla naturliga tal har en viss egenskap som är algoritmiskt kontrollerbar för varje enskilt nummer. Matiyasevich / MRDP-satsen antyder att varje sådant förslag motsvarar ett uttalande som hävdar att någon viss diofantisk ekvation inte har några naturliga lösningar. Ett antal viktiga och berömda problem är av denna form: i synnerhet Fermats sista sats , Riemann-hypotesen och fyrfärgssatsen . Dessutom kan påståendet att vissa formella system som Peano-aritmetik eller ZFC är konsekvent uttrycks som meningar. Tanken är att följa Kurt Gödel i kodning av bevis med naturliga tal på ett sådant sätt att egenskapen att vara det nummer som representerar ett bevis är algoritmiskt kontrollerbar. ${\ displaystyle \ Pi _ {1} ^ {0}}$ ${\ displaystyle \ Pi _ {1} ^ {0}}$

${\ displaystyle \ Pi _ {1} ^ {0}}$ meningar har den speciella egenskapen att om de är falska, kan detta faktum vara bevisbart i något av de vanliga formella systemen. Detta beror på att falskheten motsvarar existensen av ett motexempel som kan verifieras med enkel aritmetik. Så om en mening är sådan att varken den eller dess negation är bevisbar i något av dessa system, måste den meningen vara sant. ${\ displaystyle \ Pi _ {1} ^ {0}}$

En särskilt slående form av Gödels ofullständighetssats är också en konsekvens av Matiyasevich / MRDP-satsen:

Låta

${\ displaystyle p (a, x_ {1}, \ ldots, x_ {k}) = 0}$

tillhandahålla en Diophantine-definition av en icke-beräknbar uppsättning. Låta vara en algoritm som matar ut en sekvens av naturliga tal så att motsvarande ekvation ${\ displaystyle A}$ ${\ displaystyle n}$

${\ displaystyle p (n, x_ {1}, \ ldots, x_ {k}) = 0}$

har inga lösningar i naturligt antal. Sedan finns det ett tal som inte matas ut samtidigt som ekvationen faktiskt är ${\ displaystyle n_ {0}}$ ${\ displaystyle A}$

${\ displaystyle p (n_ {0}, x_ {1}, \ ldots, x_ {k}) = 0}$

har inga lösningar i naturligt antal.

För att se att satsen är sant räcker det med att lägga märke till att om det inte fanns något sådant nummer , kunde man algoritmiskt testa medlemskap i ett nummer i denna icke-beräknbara uppsättning genom att samtidigt köra algoritmen för att se om matas ut samtidigt som man kontrollerar allt möjligt - tappar av naturliga tal som söker en lösning av ekvationen ${\ displaystyle n_ {0}}$ ${\ displaystyle n}$ ${\ displaystyle A}$ ${\ displaystyle n}$ ${\ displaystyle k}$

{\ displaystyle p (n, x_ {1}, \ ldots, x_ {k}) = 0.}

Vi kan associera en algoritm med något av de vanliga formella systemen som Peano-aritmetik eller ZFC genom att låta den systematiskt generera konsekvenser av axiomerna och sedan mata ut ett tal närhelst en mening i formen ${\ displaystyle A}$ ${\ displaystyle n}$

{\ displaystyle \ neg \ existerar x_ {1}, \ ldots, x_ {k} [p (n, x_ {1}, \ ldots, x_ {k}) = 0]}

genereras. Då berättar satsen att antingen ett falskt uttalande av denna form bevisas eller att ett sant förblir obevisat i systemet i fråga.

Ytterligare resultat

Vi kan tala om graden av en Diophantine-uppsättning som den minsta graden av ett polynom i en ekvation som definierar den uppsättningen. På samma sätt kan vi kalla dimensionen hos en sådan uppsättning för få okända i en definierande ekvation. På grund av förekomsten av en universell Diophantine-ekvation är det uppenbart att det finns absoluta övre gränser för båda dessa kvantiteter, och det har funnits stort intresse för att bestämma dessa gränser.

Redan på 1920-talet visade Thoralf Skolem att någon Diophantine-ekvation motsvarar en av grad 4 eller mindre. Hans trick var att införa nya okända genom ekvationer som satte dem lika med kvadraten för en okänd eller produkten av två okända. Upprepning av denna process resulterar i ett system av andra grads ekvationer; sedan erhålls en ekvation av grad 4 genom att summera rutorna. Så varje Diophantine-uppsättning är triviellt av grad 4 eller mindre. Det är inte känt om detta resultat är bäst möjligt.

Julia Robinson och Yuri Matiyasevich visade att varje Diophantine-uppsättning har en dimension som inte är större än 13. Senare skärpte Matiyasevich sina metoder för att visa att 9 okända räcker. Även om det mycket väl kan vara att detta resultat inte är det bästa möjliga, har inga ytterligare framsteg gjorts. Så i synnerhet finns det ingen algoritm för att testa Diophantine-ekvationer med 9 eller färre okända för löslighet i naturliga tal. När det gäller rationella heltalslösningar (som Hilbert ursprungligen hade formulerat det) visar tricket med fyra kvadrater att det inte finns någon algoritm för ekvationer med högst 36 okända. Men Zhi Wei Sun visade att problemet för heltal är olösligt även för ekvationer med högst 11 okända.

Martin Davis studerade algoritmiska frågor som involverade antalet lösningar i en Diophantine-ekvation. Hilberts tionde problem frågar om det talet är 0. Låt och låt vara en riktig icke-tom delmängd av . Davis bevisade att det inte finns någon algoritm för att testa en given Diophantine-ekvation för att avgöra om antalet lösningar är medlem i uppsättningen . Det finns alltså ingen algoritm för att avgöra om antalet lösningar i en Diophantine-ekvation är ändligt, udda, en perfekt kvadrat, en prim, etc. ${\ displaystyle A = \ {0,1,2,3, \ ldots, \ aleph _ {0} \}}$ ${\ displaystyle C}$ ${\ displaystyle A}$ ${\ displaystyle C}$

Beviset för MRDP-satsen har formaliserats i Coq .

Utvidgningar av Hilberts tionde problem

Alexandra Shlapentokh (mitten) 2003

Även om Hilbert utgjorde problemet för de rationella heltalen, kan det lika gärna begäras många ringar (i synnerhet för alla ringar vars antal element räknas ). Tydliga exempel är ringar av heltal av algebraiska talfält liksom rationella tal .

Det har varit mycket arbete med Hilberts tionde problem för ringar av heltal av algebraiska talfält. Baserat på tidigare arbete av Jan Denef och Leonard Lipschitz och med hjälp av klassfältteori kunde Harold N. Shapiro och Alexandra Shlapentokh bevisa:

Hilberts tionde problem är olösligt för ringen av heltal i något algebraiskt talfält vars Galois-grupp över rationella är abelisk .

Shlapentokh och Thanases Pheidas (oberoende av varandra) erhöll samma resultat för algebraiska nummerfält som medger exakt ett par komplexa konjugerade inbäddningar.

Problemet för ringen av heltal av andra algebraiska nummerfält än de som täcks av resultaten ovan förblir öppna. Trots mycket intresse är problemet för ekvationer över rationella fortfarande öppet. Barry Mazur har antagit att den topologiska stängningen i realiteten av lösningen för alla variationer över rationaliseringarna endast har många komponenter. Denna antagande innebär att heltal inte är diofantin över rationella och så om denna antagande är sant skulle ett negativt svar på Hilberts tionde problem kräva ett annat tillvägagångssätt än det som används för andra ringar.

Anteckningar

Referenser

Hilbert, David (1901). "Mathematische Probleme". Archiv der Mathematik und Physik . 3: e serien (på tyska). 1 : 44–63, 213–247.
Hilbert, David (juli 1902). "Matematiska problem" . Tjur. Amer. Matematik. Soc . 8 (10): 437–479.
Yuri V. Matiyasevich , Hilberts tionde problem , MIT Press, Cambridge, Massachusetts, 1993.
Davis, Martin ; Matiyasevich, Yuri ; Robinson, Julia (1976). "Hilberts tionde problem: Diofantiska ekvationer: Positiva aspekter av en negativ lösning". I Felix E. Browder (red.). Matematisk utveckling som härrör från problem med Hilbert . Proceedings of Symposia in Pure Mathematics . XXVIII.2. American Mathematical Society . s. 323–378. ISBN 0-8218-1428-1. Zbl 0346.02026 . Omtryckt i The Collected Works av Julia Robinson , Solomon Feferman , redaktör, s. 269–378, American Mathematical Society 1996.
Martin Davis , "Hilberts tionde problem är olösligt," American Mathematical Monthly , vol. 80 (1973), s. 233–269; omtryckt som en bilaga i Martin Davis, Computability and Unsolvability , Dover reprint 1982.
Davis, Martin ; Hersh, Reuben (1973). "Hilberts 10: e problem". Scientific American . 229 : 84–91. doi : 10.1038 / Scientificamerican1173-84 .
Jan Denef , Leonard Lipschitz, Thanases Pheidas, Jan van Geel, redaktörer, "Hilberts tionde problem: Workshop vid Ghent University, Belgien, 2–5 november 1999." Contemporary Mathematics vol. 270 (2000), American Mathematical Society.
M. Ram Murty och Brandon Fodden: "Hilberts tionde problem: En introduktion till logik, talteori och beräkningsbarhet", Americal Mathematical Society, ISBN 978-1-4704-4399-3 (juni, 2019).

Vidare läsning

Shlapentokh, Alexandra (2007). Hilberts tionde problem. Diofantinklasser och tillägg till globala fält . Nya matematiska monografier. 7 . Cambridge: Cambridge University Press . ISBN 0-521-83360-4. Zbl 1196.11166 .

Languages

In other projects