Théorème de Youri Matiiassevitch

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 de mathématiques 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.

Sommaire 1 L'énoncé du problème 2 Réponse au dixième théorème de Hilbert 3 Généralisation 4 Notes et références 5 Bibliographie 6 Voir aussi

L'énoncé du problème

David Hilbert avait posé la question précisément comme suit :

De la possibilité de résoudre une équation diophantienne. On donne une équation de Diophante à un nombre quelconque d'inconnues et à coefficients entiers rationnels : on demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers rationnels.^[1]

Il est essentiel, dans l'énoncé du problème, que la méthode demandée soit générale et puisse s'appliquer à 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 les équations diophantiennes. Par exemple le théorème de Fermat-Wiles résout une famille d'équations diophantiennes.

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^[2].

Réponse au dixième théorème de Hilbert

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).

Généralisation

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 récursivement énumérable si et seulement 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 est diophantien si par définition il existe un polynôme à coefficients entiers P tel que n appartient à S si et seulement si P(n, x1,…, xk) = 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.

Notes et références

Bibliographie

• Youri Matiiassevitch Le dixième problème de Hilbert: Son indécidabilité, Masson, (1995), ISBN : 2225848351
• Hilbert's Tenth Problem page!, page web du 10ième problème de Hilbert au Steklov Institute of Mathematics, Maxim Vsemirnov (sous la supervision de Yuri Matiyasevich).
• Yuri Matiyasevich 1996, Hilbert's Tenth Problem: What can we do with Diophantine equations.

Voir aussi

• Diophantien

• Portail de la logique
• Portail des mathématiques

Problèmes de Hilbert

Premier problème - Deuxième problème - Troisième problème - Quatrième problème - Cinquième problème - Sixième problème - Septième problème - Huitième problème - Neuvième problème - Dixième problème - Onzième problème - Douzième problème - Treizième problème - Quatorzième problème - Quinzième problème - Seizième problème - Dix-septième problème - Dix-huitième problème - Dix-neuvième problème - Vingtième problème - Vingt-et-unième problème - Vingt-deuxième problème - Vingt-troisième problème