Décimo problema de Hilbert

O Décimo Problema de Hilbert é um dos 23 problemas propostos pelo matemático alemão David Hilbert em 1900. A declaração consiste no seguinte:

Descrever, em um número finito de operações, se uma dada equação diofantina tem raíz(es) inteira(s)

Uma equação diofantina é uma equação da forma:

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

onde P é um polinômio com coeficientes inteiros. Levou anos até o problema ser resolvido com uma resposta negativa. Hoje, sabe-se que não existe tal algoritmo. O resultado é uma combinação do trabalho realização por Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson.

Formulação

As palavras "processo" e "número finito de operações" significam que Hilbert estava buscando um algoritmo. O termo "raízes inteiras" refereces aos números inteiros, positivos, negativos ou zero:  0, ±1, ±2, ... . Então Hilbert estava pedindo por algoritmo geral para decidir se uma dada equação diofantina polinomial com coeficientes inteiros possui solução nos inteiros. A resposta para o problema é negativa: não existe tal algoritmo.

O trabalho se deu em termos de soluções nos naturais, ao invés de inteiros. Mas é simples de ver que um algoritmo em qualquer um dos casos poderia ser usado para obter um algoritmo para o outro. Se um algoritmo determinasse a possivel solução nos números naturais, então este poderia ser usado para determinar se uma equação em $n$ incógnitas,

$p(x_{1},x_{2},\ldots ,x_{n})=0;\,$

tem solução inteiro aplicando o suposto algoritmo nas 2ⁿ equações

$p(\pm x_{1},\pm x_{2},\ldots ,\pm x_{n})=0.\,$

Ao mesmo tempo que um algoritmo pode testar a solubilidade em inteiros, este pode ser usado para testar a solubilidade de uma dada equação nos naturais aplicando o suposto algoritmo na equação obtida a partir da equação dada substituindo cada incógnita pela soma dos quadrados das quatro novas incógnitas. Isso funciona por causa do Teorema de Fermat-Lagrange, que afirma que todo numero natural pode ser escrito como uma soma de quatro números quadráticos.

Aplicações

O Teorema de Matiyasevich relaciona duas noções — uma da teoria da computabilidade, outra da teoria dos números — e tem consequencias surpreendentes. Talvez a maior surpresa é a existencia de uma equação diofantina universal:

Existe um polinômio $p(a,n,x_{1},\ldots ,x_{k})$ tal que, dado qualquer conjunto diofantino $S$ existe um número $n_{0}$ tal que ::$S=\{\,a\mid \exists x_{1},\ldots ,x_{k}[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.$

Isso pode ser provado verdade simplesmente porque existem máquinas de Turing Universais, capazes de executar qualquer algoritmo. Essa implicação de Julia Robinson pareceu improvável. Hilary Putnam apontou que para qualquer conjunto diofantino $S$ de inteiros positivos, existe um polinômio

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

tal que $S$ consiste de exatamente os numeros positivos entre os valores assumidos por $q$ enquanto as variáveis

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

variam ao longo de todos os números naturais. Isso pode ser visto a seguir. Se

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

provê uma definição diofantina de $S$, entao isso é suficiente para definir

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

Então, por exemplo, existe um polinômio tal que a parte positiva da sua variação é exatamente os números primos. (Por outro lado, nenhum polinômio pode assumir somente valores primos.)

Outros resultados

Podemos falar do grau no conjunto diofantino como sendo o menor grau de um polinômio numa equação que define o conjunto. Da mesma forma, podemos chamar a dimensão de tal conjunto o menor número de incógnitas em uma equação. Devido à existência de uma equação universal diofantina, é evidente que existem limites superiores absolutos para ambas estas quantidades, e tem havido muito interesse em determinar esses limites.

Já na década de 1920 Thoralf Skolem mostrou que qualquer equação diofantina é equivalente a uma de grau 4 ou menos. O truque consistia em introduzir novas incógnitas por equações fixando-lhes valores igual ao quadrado de uma incógnita ou o produto de duas incógnitas. A repetição deste processo resulta em um sistema de equações de segundo grau e, depois, uma equação de grau 4 é obtida pela soma dos quadrados. Assim, cada conjunto diofantino é trivialmente de grau 4 ou menos. Não se sabe se este resultado é o melhor possível.

Julia Robinson e Yuri Matiyasevich mostraram que todo conjunto diofantino tem dimensão não superior a 13. Mais tarde, Matiyasevich aperfeiçoou seus métodos para mostrar que 9 incógnitas são suficientes. Embora este resultado possa não ser o melhor possível, não houve progresso. Assim, não há nenhum algoritmo para testar equações diofantinas com 9 ou menos incógnitas de solubilidade em números naturais. Para o caso de raízes inteiras (conforme Hilbert tinha originalmente colocado), o truque dos 4 quadrados mostra que não há algoritmo para equações com não mais do que 36 incógnitas. Mas Zhi Wei Sun mostrou que o problema é insolúvel para inteiros mesmo para equações com não mais de 11 incógnitas.

Martin Davis estudou questões algorítmicas envolvendo o número de soluções de uma equação diofantina. O décimo problema de Hilbert pergunta se sim ou não o número é 0. Supomos um subconjunto não vazio adequado. Davis provou que não existe algoritmo para testar uma equação diofantina para determinar se o número de suas soluções é um membro do conjunto. Assim, não há algoritmo para determinar se o número de soluções de uma equação diofantina é finito, ímpar, um quadrado perfeito, um número primo, etc.

Referências

• Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.
• Davis, Martin; Matiyasevich, Yuri; Robinson, Julia (1976). «Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution». In: Felix E. Browder. Mathematical Developments Arising from Hilbert Problems. Col: Proceedings of Symposia in Pure Mathematics. XXVIII.2. [S.l.]: American Mathematical Society. pp. 323–378. ISBN 0-8218-1428-1  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.
• Martin Davis and Reuben Hersh, "Hilbert's 10th Problem", Scientific American, vol. 229 (1973), pp. 84–91.
• 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.

Ver também

• Problemas de Hilbert