Diophantien

• L'ensemble des nombres pairs est diophantien car :

a pair ⇔ il existe x tel que a – 2x = 0

• L'ensemble des nombres non premiers est diophantien car :

a est non premier ⇔ il existe (x,y) tel que a - (x+2)(y+2) = 0

Une astuce simple due à Hilary Putnam[1] permet de montrer que si un ensemble M d'entiers naturels non nuls est diophantien, il est l'ensemble des valeurs strictement positives d'un polynôme à coefficients entiers, pour des valeurs positives des variables.

En reprenant la définition dans le cas où n = 1. Il existe un polynôme D à p + 1 variables et coefficients entiers relatifs tel que

a ∈ M ⇔ ∃ x ∈ ℕ^p, D(a, x) = 0.

On introduit alors le polynôme (1 – D(y,x)²) dont toutes les valeurs sont inférieures ou égales à 1.

En particulier la seule valeur strictement positive 1 est atteinte si et seulement si D(y,x) est nul et donc si et seulement si y ∈ M.

L'ensemble M est donc l'ensemble des valeurs strictement positives du polynôme y(1 – D(y,x)²) :

M = ℕ^* ∩ {y(1 – D(y,x)²) | x ∈ ℕ^p et y ∈ ℕ}

Par exemple, l'ensemble des nombres de Fibonacci est constitué des valeurs positives du polynôme y(2 – (x² + xy – y²)²).

Les paramètres x ont été choisis positifs, mais, tout entier naturel étant somme de 4 carrés, il est possible, en modifiant le polynôme, de prendre des paramètres dans ℤ.

On montre aisément que la réunion ou l'intersection de deux ensembles diophantiens est diophantien. En effet, si M₁ et M₂ sont diophantiens, représentés respectivement par les équations D₁ et D₂, alors :

a ∈ M₁ ∪ M₂ ⇔ il existe (x,y) tel que D₁(a,x)D₂(a,y) = 0.

M₁ ∪ M₂ est donc diophantien, représenté par D(a,x,y) = D₁(a,x)D₂(a,y).

De même, M₁ ∩ M₂ est diophantien, représenté par D(a,x,y) = D₁(a,x)² + D₂(a,y)².

Par contre, le complémentaire d'un ensemble diophantien n'est pas toujours diophantien.

Il est facile de montrer qu'un ensemble diophantien E défini par une équation D est récursivement énumérable. L'algorithme le reconnaissant est le suivant :

• lire en entrée la valeur du paramètre a
• donner à x la valeur 0
• tant que D(a,x) est différent de 0, augmenter x de 1 fin tant que

Cet algorithme est donné dans le cas où x décrit ${\displaystyle \mathbb {N} }$. Si x doit décrire ${\displaystyle \mathbb {N} ^{p}}$, il convient de remplacer l'énumération des éléments de ${\displaystyle \mathbb {N} }$ par une énumération des éléments de ${\displaystyle \mathbb {N} ^{p}}$.

Si a est élément de E, il existera un x tel que D(a,x) = 0. L'algorithme précédent finira par le trouver et s'arrêtera sur cette valeur de x. Par contre, si a n'est pas élément de E, aucun x ne convient, et l'algorithme bouclera indéfiniment. E est donc bien récursivement énumérable.

La réciproque est extrêmement délicate et constitue le nœud du théorème de Matiyasevich. Une façon de le prouver est de montrer que la fonction qui à une configuration d'une machine de Turing associe la configuration suivante, celle obtenue après une étape de calcul, est une fonction diophantienne, les configurations étant codées par des entiers. Si p est un nombre codant une configuration d'une machine de Turing, il existe un polynôme D tel que D(p, x₁, ..., x_n) possède une solution si et seulement si la Machine de Turing démarrant par la configuration p s'arrête. La reconnaissance des ensembles diophantiens est donc équivalent à celle des ensembles récursivement énumérables.

La méthode précédente permet explicitement d'associer un polynôme à un algorithme définissant un ensemble récursivement énumérable. Ainsi, Jones, Sato, Wada et Wiens ont explicité en 1976 un polynôme de degré 25 et des 26 variables dont l'ensemble des valeurs strictement positives, quand les variables parcourent les entiers naturels, coïncide avec l'ensemble des nombres premiers. Le polynôme est construit à partir de la représentation diophantienne de l'ensemble des nombres premiers en utilisant l'astuce de Putnam ci-dessus.

La théorie de la calculabilité a montré qu'il existe des ensembles récursivement énumérables dont le complémentaire n'est pas récursivement énumérable.

Plus précisément, à toute équation diophantienne D sans paramètre, définissons Card(D) comme étant le cardinal de son ensemble de solutions (éventuellement infini). Alors l'ensemble E = {D | Card(D) ≥ 1} est récursivement énumérable. Car si D appartient à un tel ensemble, il suffit d'énumérer les x les uns après les autres et de tester si D(x) est nul pour finir par un trouver un, ce qui permet de dire que D appartient à E. Si D n'admet pas de solution, l'algorithme précédent boucle indéfiniment. Et précisément, on montre que {D | Card(D) = 0} n'est pas récursivement énumérable. Cela signifie qu'il existe bien un algorithme général permettant de dire si une équation diophantienne D admet une solution, mais aucun algorithme permettant de dire si D n'en admet pas.

Le dixième problème de Hilbert n'admet donc pas de solution. La résolution générale des équations diophantiennes est un problème indécidable.