Dixième problème de Hilbert

Le dixième problème de Hilbert demande de trouver une méthode algorithmique générale pour la recherche des solutions entières des équations diophantiennes à plusieurs inconnues, c'est-à-dire des équations polynômiales à coefficients entiers. Il fait partie d'une célèbre liste de problèmes dressée par David Hilbert en 1900 lors de sa conférence au congrès international des mathématiciens de Paris. Le théorème de Matiiassevitch, démontré par ce dernier en 1970, établit que les ensembles diophantiens, qui sont les ensembles de solutions entières positives ou nulles d'une équation diophantienne avec paramètres, sont exactement tous les ensembles récursivement énumérables, ce qui entraîne qu'un tel algorithme ne peut exister : le dixième problème de Hilbert n'a pas de solution.

David Hilbert avait posé la question comme suit :

De la possibilité de résoudre une équation diophantienne. Soit la donnée d'une équation diophantienne à un nombre quelconque d'inconnues et à coefficients entiers rationnels : on doit trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra décider si l'équation est résoluble en nombres entiers rationnels.

Il s'agit du seul des problèmes de Hilbert qui est ce que l'on appelle aujourd'hui un problème de décision : il existe une infinité dénombrable d'équations diophantiennes, mais la solution du dixième problème demande de trouver une méthode universelle qui permette de résoudre n'importe quelle équation diophantienne. Il existe de fait des méthodes très diverses et utilisant des techniques mathématiques très variées pour résoudre des équations diophantiennes. Par exemple le théorème de Fermat-Wiles résout une famille d'équations diophantiennes à trois inconnues.

Hilbert n'emploie pas le mot « algorithme », mais il n'y a aucun doute que c'est cela qu'il entend. À son époque, il n'existe pas de définition précise de ce qu'est un algorithme, ce qui n'aurait pas été gênant si la solution du problème avait été positive. Pour pouvoir envisager une solution négative, il fallait en donner une définition mathématique, qui est le fruit de travaux des années 1930, et repose sur la thèse de Church, formulée en 1936.

Un exemple de système d'équations diophantiennes est le suivant :

La question qui se pose s'énonce ainsi: existe-t-il des nombres entiers x, y et z qui satisfont simultanément les deux équations? Cette question est équivalente à celle de savoir si une équation diophantienne unique à plusieurs variables admet une solution dans les entiers naturels. Par exemple, le système ci-dessus a une solution entière si et seulement si l'équation suivante a une solution dans les entiers naturels :

(3(x₁ − x₂)(y₁ − y₂) − 7(y₁ − y₂)(z₁ − z₂) − 18) + ( − 7(y₁ − y₂) + 8(z₁ − z₂)) = 0

Youri Matiiassevitch a utilisé une astuce impliquant les nombres de Fibonacci afin d'exhiber une équation diophantienne dont les solutions se développent exponentiellement. Les premiers travaux sur ce sujet sont dus à Julia Robinson, Martin Davis et Hilary Putnam; ils avaient démontré qu'il suffit de ce résultat pour qu'il n'existe aucun algorithme général décidant l'existence de solutions pour les équations diophantiennes.

Des travaux postérieurs ont montré que la question de l'existence de solutions d'une équation diophantienne est indécidable même si l'équation a seulement 9 variables naturelles (Matiyasevich, 1977) ou 11 variables entières (Zhi Wei Sun, 1992).

Le théorème de Matiiassevitch lui-même est beaucoup plus fort que l'insolubilité du dixième problème. Il affirme que :

Un ensemble est récursivement énumérable si et seulement s’il est diophantien.

Un ensemble S de nombres entiers est dit récursivement énumérable s’il y a un algorithme qui se comporte comme suit : on donne comme entrée à l'algorithme un nombre entier n, si n appartient à S, alors l'algorithme s'arrête tôt ou tard ; sinon il s'exécute indéfiniment. Cela revient à dire qu'il existe un algorithme qui s'exécute indéfiniment et produit tous les membres de S. D'autre part, un ensemble S d'entiers est dit diophantien s'il existe un polynôme à coefficients entiers P tel que n appartient à S si et seulement s'il existe des entiers x₁,…, x_k tels que P(n,x₁,…, x_k) = 0.

Il n'est pas difficile de voir que chaque ensemble diophantien est récursivement énumérable. Pour cela considérons une équation diophantienne f(n, x1,…, xk) = 0 et imaginons un algorithme qui parcourt toutes les valeurs possibles pour n, x1,…, xk, dans l'ordre croissant de la somme de leurs valeurs absolues, et retourne n chaque fois que f(n, x1,…, xk) = 0. Évidemment cet algorithme s'exécutera sans fin et énumérera les n pour lesquels f(n, x1,…, xk) = 0 a une solution.

La conjonction du théorème de Youri Matiiassevitch avec un résultat découvert dans les années 1930 implique qu'il n'y a pas de solution au dixième problème de Hilbert. Ce résultat découvert par plusieurs logiciens affirme qu'il existe des ensembles récursivement énumérables non récursifs. Dans ce contexte, un ensemble S de nombres entiers s'appelle « récursif » s'il y a un algorithme qui, étant donné un nombre entier n, renvoie une réponse oui ou non à la question n appartient-il à S? Il s'ensuit qu'il y a des équations diophantiennes qui ne peuvent être résolues par aucun algorithme.

Le théorème de Youri Matiiassevitch a été depuis employé pour démontrer l'indécidabilité de nombreux problèmes liés à l'arithmétique, de même, on peut également dériver la forme plus forte suivante du premier théorème d'incomplétude de Gödel :

Soit une axiomatisation quelconque de l'arithmétique, on peut construire une équation diophantienne qui n'a aucune solution, mais telle que ce fait ne puisse pas être démontré dans l'axiomatisation en question.