L'indécidabilité du 10ème problème de HILBERT
a été établie par Youri MATIIASSEVITCH


David Hilbert

Yuri Matiiassewitch

résumé d'une leçon donnée à l'Athénée Gatti de Gamond
par Jean Drabbe
professeur émérite ULB

1. PRELIMINAIRES

Le cadre du 10ème problème de Hilbert est limité à l'ensemble Z des entiers

Z = {... -3 , -2 , -1 , 0 , 1 , 2 , 3 , ... }

Un polynôme P(x , y , z , ...) est dit diophantien si et seulement si tous ses coefficients sont dans Z .
Une équation diophantienne est une équation de la forme P(x , y, z , ...) = 0 où P est un polynôme diophantien. Une équation diophantienne peut donc faire intervenir plusieurs inconnues.

Intuitivement, un algorithme est un ensemble de règles qui permet de résoudre mécaniquement des problèmes ou d'effectuer mécaniquement des opérations.
Mécaniquement exclut toute initiative, toute réflexion lors de l'exécution. Seule une application aveugle des règles est tolérée. Le travail doit pouvoir être exécuté à la manière d'un automate, d'un programme d'ordinateur.
L'image couramment employée par les mathématiciens est celle d'une boîte noire recevant des données à partir desquelles elle fournit un résultat par application de seules règles de fonctionnement, spécifiques, strictes et impératives.
L'enseignement de l'arithmétique à l'école primaire est consacré principalement (si pas totalement) à l'apprentissage d'algorithmes. On y décrit des méthodes de calcul (somme, produit, quotient, pgcd, ppcm) et de résolution de questions telles un nombre donné est-il premier ?
Durant les années 30, Kurt GÖDEL, Alonzo CHURCH, Alan TURING et d'autres logiciens fournirent une formulation rigoureuse de la notion d'algorithme.
Ultérieurement, une nouvelle formulation fut apportée par Andrei MARKOV Jr (1903 - 1979), fils de Andrei MARKOV (1856 - 1922) auquel on doit de nombreuses contributions au calcul des probabilités.

Andrei Markov Jr




2. Le 10ème PROBLEME DE HILBERT

Lors du Congrès International des Mathématiciens de Paris (1900), David HILBERT a énoncé 23 problèmes qu'il estimait important pour le développement ultérieur des mathématiques.


Le 10ème problème de Hilbert
Existe-t-il un algorithme général permettant de déterminer si une équation diophantienne quelconque P(x , y , z , ...) = 0 admet une solution en nombres entiers ?



Le problème a été résolu par Yuri Matiiassevitch en 1970.
La réponse est NEGATIVE.


3. REMARQUES

Comme l'a montré Matiiassevitch, c'est la généralité imposée par le dixième problème qui conduit à sa solution négative. Il n'est pas possible de traiter toutes les équations diophantiennes par un algorithme.
Le problème de Hilbert admet cependant une solution positive pour certains classes d'équations diophantiennes.
Voici deux exemples.

(A) Il existe un algorithme permettant de déterminer si un polynôme diophantien à une seule variable admet une racine entière.

Vérification : Considérons le polynôme :
anxn + an-1xn-1 + . . . + a1x + a0

de degré > 0 . Si a0 = 0 , alors 0 est une racine. Nous pouvons donc supposer a0 différent de 0 . Si b est une racine, alors b divise a0 . Comme a0 n'admet qu'un ensemble fini de diviseurs (que l'on peut déterminer de manième algorithmique), il suffit de rechercher si l'un d'eux convient.


(B) Le deuxième exemple est choisi afin de rappeler le théorème de FERMAT (qui n'a été démontré qu'en 1993/1994 par Andrew WILES, soit plus de 300 ans après sa formulation) et un résultat dû à LAGRANGE .

Le théorème de FERMAT
Pour tout n > 2 , l'équation
xn + yn = zn
n'admet pas de solution en nombres entiers tous > 0
Un théorème de LAGRANGE

Tout nombre naturel est somme de quatre carrés (d'entiers).


Notons que pour n = 1,2 , l'équation xn + yn = zn admet une infinité de solutions en nombres entiers > 0 .

En vertu du théorème de Fermat, un entier x est donc > 0 ssi il existe des entiers x1 , x2 , x3 , x4 tels que x - 1 = x12 + x22 + x32 + x42 .

Comme une somme de carrés est nulle, il existe un algorithme permettant de déterminer pour tout n > 0 si l'équation diophantienne

(x -x12 - x22 - x32 - x42 - 1)2 + (y -y12 - y22 - y32 - y42 - 1)2 + (z -z12 - z22 - z32 - z42 - 1)2 + (xn + yn - zn)2 = 0

en les 15 variables x , y , z , x1 , x2 , x3 , x4 , y1 , ... , z3 , z4 admet une solution entière. Il suffit de répondre oui lorsque n = 1 ou 2 , non lorsque n > 2 .


4. REDUCTION DU PROBLEME DE HILBERT AUX EQUATIONS DEGRE 4

Montrons que pour tout polynôme diophantien P, il existe un polynôme diophantien Q de degré inférieur ou égal à 4 tel que l'équation P = 0 a une solution entière si et seulement si l'équation Q = 0 a une solution entière. Il en résultera immédiatement que la solution du problème de Hilbert limité aux équations de degré inférieur ou égal à 4 est aussi négative. La technique utilisée est très simple. Aussi, plutôt que de décrire une vérification générale, au prix de notations lourdes, nous nous limiterons à traiter un exemple.
Considérons le polynôme diophantien P de degré 6
xy3z2 + 6xy + 3

Introduisons les nouvelles variables variables u1 , u2 , u3 , u4 et les équations suivantes
  • u1 - xy = 0
  • u2 - u1y = 0
  • u3 - u2y = 0
  • u4 - u3z = 0
  • u4z + 6xy + 3 = 0
Ce système de 5 équations diophantiennes admet une solution entière
si et seulement si
il en est ainsi pour l'équation P = 0 .
Par conséquent P = 0 a une solution entière si et seulement si l'équation diophantienne suivante de degré 4 en possède une

(u1 - xy)2 + (u2 - u1y)2 + (u3 - u2y)2 + (u4 - u3z)2 + (u4z + 6xy + 3)2 = 0


Problème ouvert :
La solution du problème de Hilbert restreint aux équations diophantiennes de degré 3 est-elle négative ?



5. NOTE HISTORIQUE

David HILBERT prononça sa fameuse conférence intitulée Mathematische Probleme en allemand. Voici la première traduction française, faite vers 1900 et revue par Hilbert, de l'énoncé du dixième problème :

10. DE LA POSSIBILITE DE RESOUDRE UNE EQUATION 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.



Retour à la page d'accueil de MATHEMA