Dècim problema de Hilbert

El dècim problema de Hilbert és un dels coneguts com vintitrés Problemes de Hilbert, publicats en 1900 pel matemàtic alemà David Hilbert. El seu enunciat original és:

Donada una equació diofántica en qualsevol número d'incògnites i en coeficients numèrics racionals sancers: Idear un procés d'acort en el qual puga determinar-se, en un número finito d'operacions, si l'equació és resoluble en número racional sancers.

En térmens de programació informàtica, Hilbert solicitava als seus colegues del futur un algoritme capaç d'admetre com a entrada (input) una equació diofántica qualsevol, i de tornar SÍ com a resultat (output) si l'equació processada tenia solucions en número entero o NO si l'equació processada caria de solucions en número entero.

El problema no es va resoldre fins a 70 anys despuix, i en sentit negatiu. En 1970 Yuri Matiyasévich va culminar més de vint anys de treball de varis matemàtics, entre ells Martin Davis, Julia Robinson i Hilary Putnam, en la demostració d'impossibilitat del dècim problema: cap algoritme és capaç de determinar la resolubilidad de qualsevol equació diofántica. El plantejament, desenroll i demostració del problema tenen gran interés en matemàtica moderna, perque en ells participen conceptes de teoria de números i de llògica matemàtica, i s'òbrin nous camps d'investigació en abdós disciplines.

Formulació

Les paraules «processe» i «número finito d'operacions» del seu enunciat original sugerixen clarament que Hilbert demanava un algoritme. El terme «racional sancer» es referix simplement als número entero, positius, negatius o zero: $0,\pm 1,\pm 2,\dots$. Per tant, Hilbert estava demanant un algoritme general que decidira si un polinomi donat de coeficients sancers —una equació diofántica— tenia solució en el domini dels sancers.

Hui sabem que la resposta és negativa: no existix tal algoritme general.

Pot ser que el propi Hilbert no confiara en la seua existència. Abans de presentar la llista de problemes, semblava presagiar l'absència de solució, dient:

En ocasions ocorre que perseguim la solució basant-nos en hipòtesis insuficients, o en un sentit incorrecte, i per això fracassem. Llavors sorgix el problema: demostrar l'impossibilitat d'obtindre una solució en tals hipòtesis o en el sentit contemplat.

Uns atres opinen que la «solució de insolubilidad» a la que es va aplegar sèt décades despuix no solament haguera sorprés a l'auditori que va assistir en 1900 en la Sorbona a la presentació de Hilbert, sino possiblement inclús al propi Hilbert, ya que s'esperava obtindre un conjunt d'instruccions que definiren un procediment, i a lo que es va aplegar finalment va ser a una demostració de l'inexistència de tal conjunt d'instruccions.

Equivalència del problema en ℕ i en ℤ

Els treballs de solució del problema casi sempre s'han plantejat en térmens de sancers no negatius o número natural, $\mathbb{N}=\{0,1,2,3\dots \}$, més que en número entero. És irrellevant, perque pot demostrar-se que si existira un algoritme que detectara l'existència de solució en $\mathbb{N}$, podria usar-se també per a detectar l'existència de solució en $\mathbb{Z}$.

• En efecte: conegut un algoritme que detecte la resolubilidad en $\mathbb{N}$, podríem usar-ho per a detectar si l'equació de $n$ incògnites,

$p(x_1,x_2,\dots ,x_n)=0,$

té solució sancera, aplicant l'hipotètic algoritme a les $2^n$ equacions

$p(\pm x_1,\pm x_2,\dots ,\pm x_n)=0.$

• Inversament, un algoritme capaç de detectar la resolubilidad en $\mathbb{Z}$ pot usar-se per a determinar si una equació donada és resoluble en $\mathbb{N}$, sense més que substituir cada incògnita de l'equació per la suma dels quadrats de quatre noves variables sanceres. El teorema de Lagrange dels quatre quadrats garantisa que qualsevol número natural pot igualar-se a la suma dels quadrats d'un màxim de quatre número entero.

Conjunts diofánticos

Es denomina conjunts diofánticos als conjunts d'número natural, de parells d'número natural, o de forma més general de $n$-tuplas d'número natural, que tenen definicions diofánticas. Tant un sistema d'equacions diofánticas simultànees com una equació diofántica individual poden definir un conjunt diofántico, perque el sistema

$p_1=0,\dots ,p_k=0$

és equivalent a l'equació individual

$p_1^2+\dots +p_k^2=0.$

Dit d'un atre modo, si existix una equació (o sistema) diofántica la solució del qual siga el conjunt de $n$-tuplas d'número natural $C$, llavors $C$ és un conjunt diofántico.

Un conjunt és diofántico si i solament si és recursivamente enumerable

Es definix un conjunt recursivamente enumerable com un conjunt per al que existix un algoritme que es detindrà si la seua entrada és un element del conjunt, pero seguirà corrent indefinidament si la seua entrada no pertany al conjunt. El concepte de enumerabilidad recursiva pertany a l'àmbit de la teoria de la computabilidad, també cridada teoria de la recursión, el desenroll de la qual va aportar una explicació precisa de la noció intuïtiva de computabilidad algorítmica, donant ple rigor al concepte de enumerabilidad recursiva.

Resulta evident que els conjunts diofánticos són, per definició, recursivamente enumerables. Donada una equació o sistema diofántico, poden formar-se secuencialment totes les tuplas possibles de valors de les incògnites i despuix, per a un valor donat dels paràmetros, comprovar una despuix d'una atra les tuplas, per a detectar si són o no solució de l'equació o sistema. Després la pròpia equació o sistema que definix el conjunt diofántico definix l'algoritme que avala la enumerabilidad recursiva del conjunt. L'impossibilitat de resoldre el dècim problema de Hilbert és conseqüència de que l'invers també és cert:

Tot conjunt recursivamente enumerable és diofántico.

Este resultat es coneix de dos formes: com Teorema de Matiyasevich, perque va ser Yuri Matiyasévich el que va conseguir el desenroll final que va permetre demostrar la teorema, i com Teorema MRDP, nom que agrupa als matemàtics que varen conseguir el desenroll complet, escomençant pel citat Matiyasevich, per a continuar per Julia Robinson, Martin Davis i Hilary Putnam. Ya que existix un conjunt recursivamente enumerable que no és computable, la irresolubilidad del dècim problema de Hilbert és una conseqüència immediata. De fet, pot dir-se més. Existix un polinomi

$p(a,x_1,\dots ,x_n)$

en coeficients sancers, tal que el conjunt de valors de $a$ per al que l'equació

$p(a,x_1,\dots ,x_n)=0$

té solucions en els número natural no és computable. Aixina que, no solament no existix un algoritme general per a detectar la resolubilidad de les equacions diofánticas, sino que també pot demostrar-se que ni tan sols existix un algoritme particular per a la família d'equacions en un únic paràmetro.

Història

Any	Successos
1944	Emil Leon Post declara que el dècim problema de Hilbert «està implorando una prova de irresolubilidad».
1949	Martin Davis utilisa el método de Kurt Gödel per a aplicar el teorema chinenca del residu com a truc de codificació per a obtindre en la seua forma normal conjunts recursivamente enumerables: $\{a\mid \mathrm{\exists }y\mathrm{\forall }k\le y\mathrm{\exists }{x}_1,\dots ,x_n[p(a,k,y,x_1,\dots ,x_n)=0]\}$ a on $p$ és un polinomi en coeficients sancers. Formalment, solament el quantificador universal torba per a que es considere açò com una definició diofántica de conjunts. Usant una prova no constructiva, pero molt senzilla, Davis va notar que hi ha un conjunt diofántico que el seu complementari no és diofántico. Ya que els conjunts recursivamente enumerables tampoc són tancats per al complement, Davis conjeturó l'identitat d'abdós classes.
1950	Julia Robinson no coneixia el treball de Davis, pero sospitant que la funció exponencial era d'importància clau, intentava demostrar que EXP, el conjunt de triplets $(a,b,c)$ per als quals $a=b^c$ és diofántico. No va tindre èxit, lo que la va conduir a la seua hipòtesis (després cridada $J.R.$): Existix un conjunt diofántico $D$ de parells $(a,b)$ tal que $(a,b)\in D\Rightarrow b<a^a$ pero per a cada $k>0$, $\mathrm{\exists }(a,b)\in D$ tal que $b>a^k.$ Usant algunes propietats de l'equació de Pell, Robinson va demostrar que $J.R.$ implica que EXP és diofántico. I finalment va demostrar que si EXP és diofántico, llavors també ho són els coeficients binomiales, el factorial i els cosins.
1959	Treballant junts, Davis i Putnam varen estudiar els conjunts diofánticos exponencials, és dir, els conjunts definibles per equacions diofánticas en els que alguns dels exponents poden ser incògnites. Usant la forma normal de Davis junt en els métodos de Robinson, pero suponent la llavors indemostrada conjectura de que hi ha progressions aritmètiques arbitrariamente llargues compostes d'número primo varen demostrar que tot conjunt recursivamente enumerable és un conjunt exponencial diofántico, i que com a conseqüència, $J.R.$ implicava que tot conjunt recursivamente enumerable és diofántico, i que el dècim problema de Hilbert és irresoluble.
1960	Robinson va mostrar com evitar l'us de la indemostrada conjectura dels número primo en progressions aritmètiques, i va simplificar notablement la demostració. $J.R.$ es revelava com la clau per a seguir alvançant, encara que molts dubtaven de la seua veracitat.
1961-1969	Davis i Putnam varen trobar algunes proposicions que implicaven $J.R.$ Matiyasevich va publicar algunes reduccions del dècim problema de Hilbert. Robinson va demostrar que l'existència d'un conjunt diofántico infinit de cosins bastaria per a demostrar $J.R.$
1970	Matiyasevich va presentar un sistema de 10 equacions simultànees de primer i segon grau que aportava una definició diofántica del conjunt de parells $(a,b)$ tal que $b=F_{2a}$ a on $F_n$ és el n-simo número de Fibonacci. En açò quedava demostrat $J.R.$, completant-se per tant la prova de que tots els conjunts recursivamente enumerables són diofánticos, lo que implica que el dècim problema de Hilbert és irresoluble.

Aplicacions

La teorema de Matiyasevich/MRDP relaciona dos conceptes, un de procedent de la teoria de la computabilidad, i l'atre de la teoria de números, i té algunes conseqüències inesperades. Potser la més sorprenent siga l'existència d'una equació diofántica universal.

Existix un polinomi $p(a,n,x_1,\dots ,x_k)$ tal que, donat qualsevol conjunt diofántico $S$, hi ha un número $n_0$ tal que

$S=\{a\mid \mathrm{\exists }{x}_1,\dots ,x_k[p(a,n_0,x_1,\dots ,x_k)=0]\}$

Pot vore's que açò és cert simplement perque hi ha màquines universals de Turing capaces d'eixecutar qualsevol algoritme. Precisament esta conseqüència de $J.R.$ és la que havia despertat més suspicàcies, fent dubtar de la veracitat de l'hipòtesis de Julia Robinson.

Hilary Putnam ha fet notar que per a cada conjunt diofántico $S$ de sancers positius existix un polinomi

$q(x_0,x_1,\dots ,x_n)$

tal que $S$ està format precisament pels números positius entre els valors suposts per $q$ com les variables

$x_0,x_1,\dots ,x_n$

recorren tots els número natural. Açò pot vore's com seguix: si

$p(a,y_1,\dots ,y_n)=0$

proporciona una definició diofántica de $S$, llavors això basta per a fixar

$q(x_0,x_1,\dots ,x_n)=x_0[1-p(x_0,x_1,\dots ,x_n{)}^2].$

Aixina, per eixemple, hi ha un polinomi per al qual la part positiva d'este interval són exactament els número primo (per un atre costat, no obstant, no existix cap polinomi que torne sol número primo).

Atres aplicacions tenen que vore en lo que els llògics denominen proposicions ${\Pi }_1^0$, cridades també a voltes proposicions de tipo Goldbach Estes són com la conjectura de Goldbach, propostes que assignen a tot número natural una propietat que és comprobable algorítmicamente per a cada número en particular La teorema de Matiyasevich/MRDP implica que cada una de tals proposicions és equivalent a un enunciat que afirma que existix una equació diofántica particular que carix de solució en els número natural. Cert número de problemes importants i be coneguts tenen esta forma, entre ells l'última teorema de Fermat, la hipòtesis de Riemann i el teorema dels quatre colors. Ademés, l'afirmació de que alguns sistemes formals, tals com l'aritmètica de Peano o el sistema ZFC són consistents pot expressar-se com a sentències ${\Pi }_1^0$. L'idea és seguir l'estratègia de Kurt Gödel de codificació per mig d'número natural de forma tal que la propietat de ser el número que representa a una demostració siga algorítmicamente comprobable.

Els enunciats ${\Pi }_1^0$ tenen la propietat de que en el cas de ser falsos, tal falsetat serà sempre demostradora en qualsevol dels sistemes formals en us. Açò es deu a que la falsetat determina l'existència d'un contraeixemple que pot ser verificat per aritmètica simple. Aixina, si en un d'estos sistemes formals no poden provar-se ni la proposició ${\Pi }_1^0$ ni la seua negació, eixa proposició deu ser verdadera.

Una forma particularment impactant del teorema de incompletitud de Gödel és aixina mateix conseqüència de la teorema de Matiyasevich/MRDP.

Siga

$p(a,x_1,\dots ,x_k)=0$

una definició diofántica d'un conjunt no computable.

Siga $A$ un algoritme que torna una successió d'número natural $n$ tal que l'equació corresponent

$p(n,x_1,\dots ,x_k)=0$

carix de solucions en els número natural. Llavors existix un número $n_0$ que no és tornat per $A$, mentres que, de fet, l'equació

$p(n_0,x_1,\dots ,x_k)=0$

carix de solucions en els número natural.

Per a donar-se conte de que la teorema és certa, n'hi ha prou en observar que si no existira tal número $n_0$, es podria testar algorítmicamente la pertinença d'un número $n$ a eixe conjunt no-computable, fent córrer simultàneament l'algoritme $A$ per a comprovar si torna $n$, a l'hora que es comproven totes les possibles $k$-tuplas d'número natural buscant una solució de l'equació

$p(n,x_1,\dots ,x_k)=0.$

Podem associar un algoritme $A$ en qualsevol dels sistemes formals en us, tals com l'Aritmètica de Peano o ZFC, deixant que l'algoritme genere sistemàticament conseqüències dels axioma i torne un número $n$ cada volta que es genere una proposició de la forma

$\mathrm{\neg }\mathrm{\exists }{x}_1,\dots ,x_k[p(n,x_1,\dots ,x_k)=0]$

Llavors la teorema nos diu que o be una proposició falsa del sistema serà demostrada d'esta forma, o be una verdadera quedarà sense demostrar en el sistema en qüestió, lo que demostra la incompletitud del sistema.

Resultats adicionals

Podem aludir al grau d'un conjunt diofántico, com el mínim grau d'un polinomi en l'equació que definixca el conjunt. De forma similar, podem cridar dimensió d'un conjunt diofántico al menor número d'incògnites d'una equació que ho definixca. Ya que existix una equació diofántica universal, està clar que abdós cantitats, grau i dimensió, tenen cotes superiors absolutes. Determinar estos valors màxims ha despertat molt interés en els matemàtics.

Ya en els anys 1920, Thoralf Skolem va mostrar que qualsevol equació diofántica és equivalent a una de grau 4 o inferior. La seua estratègia va ser introduir noves incògnites afegint equacions que les igualaven al quadrat d'una incògnita, o al producte de dos. Repetint este procés s'obté un sistema d'equacions de segon grau, i sumant després els quadrats es passa a una atra de grau 4. Aixina que, una equació diofántica és de grau 4 o inferior, si be es desconeix si este resultat és l'òptim.

Julia Robinson i Yuri Matiyasevich varen mostrar que tot conjunt diofántico té dimensió menor o igual que 13. Despuix, Matiyasevich va refinar el método per a demostrar que bastava en 9 incògnites. Encara que ningú imagina que este sorprenent resultat siga el millor possible, no hi ha hagut progressos posteriors Aixina que, en particular, no existix cap algoritme que puga provar la resolubilidad en els sancers positius d'equacions diofánticas de 9 incògnites o menys. Per al cas d'número entero (com Hilbert havia plantejat inicialment), el truc dels quatre quadrats mostra que no hi ha algoritme per a equacions que no tinguen més de 36 incògnites. Pero Zhi Wei Sun va demostrar que, tractant-se d'número entero, el problema és irresoluble inclús per a equacions que no excedixquen les 11 incògnites.

Martin Davis va estudiar problemes algorítmics relacionats en el número de solucions d'una equació diofántica. El dècim problema de Hilbert reclama un algoritme que decidixca si el número de solucions és $0$ o distint de $0$. Supongam que $A=\{0,1,2,3,\dots ,{\mathrm{\aleph }}_0\}$ i siga $C$ un subconjunt estricte i no buit de $A$. Davis va demostrar que no existix algoritme que puga decidir si una equació diofántica donada té un número de solucions que siga element del conjunt $C$. Per tant, no existix cap algoritme que puga determinar si el número de solucions és finito o infinit, parell o impar, primer o compost, quadrat perfecte, etc.

Extensions del dècim problema de Hilbert

Encara que Hilbert va propondre el problema per al cas dels racionals sancers, és clar que la pregunta pot fer-se per a molts anells. Eixemples obvis són els anells de sancers de cossos numèrics algebraics, aixina com els número racional. Segurament Hilbert era conscient de que un algoritme com el que estava reclamant podria estendre's a eixes estructures. Per eixemple, l'equació

$p(x_1,\dots ,x_k)=0$

a on $p$ és un polinomi de grau $d$ és resoluble en els número racional negatius si i solament si

$(z+1{)}^{d}p(\frac{x_1}{z+1},\dots ,\frac{x_k}{z+1})=0$

és resoluble en els número natural (si es té un algoritme per a determinar la resolubilidad en racionals no negatius, podrà usar-se fàcilment per a determinar la resolubilidad en els racionals). No obstant, el coneiximent de que no existix l'algoritme que reclamava Hilbert no nos aporta cap informació sobre atres estructures. Pot existir o no per a elles.

S'ha treballat molt en l'aplicació del dècim problema de Hilbert als anells de sancers de cossos algebraics de números. Basant-se en treballs anteriors de Jan Denef i Leonard Lipschitz, i usant la teoria de classes, Harold N. Shapiro i Alexandra Shlapentokh varen conseguir demostrar:

El dècim problema de Hilbert és irresoluble per a l'anell d'integritat de qualsevol cos numèric algebraic el grup del qual de Galois sobre els racionals siga abeliano.

Shlapentokh i Thanases Pheidas (treballant independentment) varen obtindre el mateix resultat per a cossos algebraics de números que admeten exactament un parell d'encaixos complexos conjugats.

El problema de l'anell d'integritat dels cossos numèrics algebraics distints dels coberts pels resultats anteriors seguix estant sense resoldre. Aixina mateix, i pese a despertar molt interés, el problema seguix també obert per a les equacions sobre els racionals.

Bibliografia

De l'artícul original en anglés

• Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
• Martin Davis, Yuri Matiyasevich, and Julia Robinson, "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution," Proceedings of Symposia in Pure Mathematics, vol.28(1976), pp. 323-378; reprinted in The Collected Works of Julia Robinson, Solomon Feferman, editor, pp.269-378, American Mathematical Society 1996.
• Martin Davis, "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233-269; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
• Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2-5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.

Vore també

• Problemes de Hilbert