Dixième problème de Hilbert

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.

Sommaire

L'énoncé du problème

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[1].

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

Article détaillé : Équation diophantienne.

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[4].

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

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

\begin{cases}3x^2y - 7y^2z^3=18\\ -7y^2 + 8z^2 = 0 \end{cases}


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(x1 − x2)2(y1 − y2) − 7(y1 − y2)2(z1 − z2)3 − 18)2 + ( − 7(y1 − y2)2 + 8(z1 − z2)2)2 = 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 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 x1,…, xk tels que 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

  1. ↑ (de)Entscheidung der Lösbarkeit einer diophantischen Gleichung. Eine diophantische Gleichung mit irgendwelchen Unbekannten und mit ganzen rationalen Zahlkoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchen sich mittels einer endlichen Anzahl von Operationen entscheiden lässt, ob die Gleichung in ganzen rationalen Zahlen lösbar ist, citation reprise de la Hilbert's Tenth Problem page (cf. bibliographie), http://logic.pdmi.ras.ru/Hilbert10/stat/stat.html.
  2. ↑ Matiiassevitch 1996, article cité en bibliographie, p 2.
  3. ↑ Chaque exposant détermine une équation diophantienne, mais l'équation de Fermat, en tant qu'équation à 4 inconnues ne l'est pas.
  4. ↑ Matiyasevich 1996, p 5.

Bibliographie

Voir aussi


v · 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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Dixième problème de Hilbert de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Troisieme probleme de Hilbert — Troisième problème de Hilbert Le troisième problème de Hilbert est l un des 23 problèmes de Hilbert. Considéré comme le plus facile, il traite de la géométrie des polyèdres. Étant donnés deux polyèdres d égal volume, est il possible de découper… …   Wikipédia en Français

  • Troisième problème de Hilbert — Le troisième problème de Hilbert est l un des 23 problèmes de Hilbert. Considéré comme le plus facile, il traite de la géométrie des polyèdres. Étant donnés deux polyèdres d égal volume, est il possible de découper le premier polyèdre en des… …   Wikipédia en Français

  • Troisième problème de hilbert — Le troisième problème de Hilbert est l un des 23 problèmes de Hilbert. Considéré comme le plus facile, il traite de la géométrie des polyèdres. Étant donnés deux polyèdres d égal volume, est il possible de découper le premier polyèdre en des… …   Wikipédia en Français

  • Neuvieme probleme de Hilbert — Neuvième problème de Hilbert Le neuvième problème de Hilbert est l un des vingt trois problèmes ouverts proposés comme défis du XXe siècle par David Hilbert au second congrès international de mathématiques en 1900. Il consiste à généraliser… …   Wikipédia en Français

  • Neuvième Problème De Hilbert — Le neuvième problème de Hilbert est l un des vingt trois problèmes ouverts proposés comme défis du XXe siècle par David Hilbert au second congrès international de mathématiques en 1900. Il consiste à généraliser la loi de réciprocité… …   Wikipédia en Français

  • Neuvième problème de hilbert — Le neuvième problème de Hilbert est l un des vingt trois problèmes ouverts proposés comme défis du XXe siècle par David Hilbert au second congrès international de mathématiques en 1900. Il consiste à généraliser la loi de réciprocité… …   Wikipédia en Français

  • Seizième problème de Hilbert — Le seizième problème de Hilbert est l un des 23 problèmes de Hilbert. Il comporte deux parties. La première concerne le nombre de branches réelles (ovales) d une courbe algébrique, et leur disposition ; de nombreux résultats modernes… …   Wikipédia en Français

  • Septieme probleme de Hilbert — Septième problème de Hilbert Le septième problème de Hilbert concerne l irrationalité et la transcendance de certains nombres (Irrationalität und Transzendenz bestimmter Zahlen). Dans sa formulation géométrique, il demande quand l assertion… …   Wikipédia en Français

  • Septième problème de hilbert — Le septième problème de Hilbert concerne l irrationalité et la transcendance de certains nombres (Irrationalität und Transzendenz bestimmter Zahlen). Dans sa formulation géométrique, il demande quand l assertion suivante est démontrable :… …   Wikipédia en Français

  • Huitième problème de Hilbert — Hypothèse de Riemann Représentation de la valeur absolue de la fonction zêta de Riemann. L hypothèse de Riemann est une conjecture formulée en 1859 par le mathématicien Bernhard Riemann. Elle dit que les zéros non triviaux de la fonction zêta de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”