Diophantien

L'adjectif diophantien (du nom de Diophante d'Alexandrie) s'applique à tout ce qui concerne les équations polynomiales à coefficients entiers, également appelées équations diophantiennes. Les notions qui suivent ont été développées pour venir à bout du dixième problème de Hilbert. Il s'agit de savoir s'il existe un algorithme général permettant de dire si, oui ou non, il existe une solution à une équation diophantienne. Le théorème de Matiyasevich prouve l'impossibilité de l'existence d'un tel algorithme.

Un ensemble M inclus dans ${\mathbb{N}}^n$ est diophantien, ou est représenté par l'équation diophantienne D si :

a ∈ M ⇔ il existe x tel que D(a, x) = 0

Ci-dessus, D est un polynôme à coefficients entiers de n+p variables, et x est un paramètre élément de ${\mathbb{N}}^p$.

Exemple

• 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

Si M est un ensemble diophantien, inclus dans $\mathbb{N}$, représenté par l'équation D, on a :

a ∈ M ⇔ il existe x, D(a, x) = 0 ⇔ il existe x dans ${\mathbb{N}}^p$ et y dans $\mathbb{N}$ tels que (y+1)(1 – D(y,x)) – 1 = a

donc M est l'ensemble des valeurs positives d'un polynôme à coefficients entiers, pour des valeurs positives des variables. Par exemple, l'ensemble des nombres de Fibonacci est constitué des valeurs positives du polynôme y(2 – (x + xy – y)).

Réunion et intersection d'ensembles diophantiens

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.

Une propriété P est diophantienne, représentée par l'équation diophantienne D si :

P(a) ⇔ il existe x tel que D(a,x) = 0

Il est équivalent de dire que l'ensemble des a vérifiant la propriété P est un ensemble diophantien. La conjonction ou la disjonction de propriétés diophantiennes est diophantienne. Par contre, la négation ou l'implication ne conserve pas le caractère diophantien.

On définit de proche en proche des propriétés diophantiennes de plus en plus compliquées, par exemple, le fait qu'un entier soit un nombre premier.

Une fonction F de $\mathbb{N}$ dans $\mathbb{N}$, ou plus généralement de ${\mathbb{N}}^n$ dans ${\mathbb{N}}^m$, est diophantienne si son graphe est diophantien. Autrement dit :

a = F(b) ⇔ il existe x, D(a, b, x) = 0

Les applications polynomiales sont évidemment diophantiennes. Mais on montre également que l'exponentielle est diophantienne, autrement dit, il existe un polynôme D tel que :

a = b ⇔ il existe x, D(a, b, n, x) = 0

Nous soulignons bien que l'expression de gauche a = b possède les trois variables a, b et n et est donc une relation exponentielle, et non une simple relation polynomiale telle que a = b, où n s'est vu fixer la valeur 3. Il est absolument remarquable qu'une expression exponentielle puisse être caractérisée uniquement par des relations polynomiales. Cette propriété, démontrée par Matiyasevich, est un point clé de la réponse négative apportée au 10ème problème de Hilbert. On peut utiliser pour cela le fait que des suites de solutions d'équations diophantiennes peuvent croître exponentiellement. Ainsi, b est quasiment égal à a_n où (a_n) est la suite définie par :

a₀ = 0, a₁ = 1, a_n+2 = ba_n+1 – a_n

et que :

il existe n, x = a_n et y = a_n+1 ⇔ x – bxy + y = 1

Ou bien, en utilisant un codage passant par l'intermédiaire de solutions d'équations de Pell-Fermat, on montre qu'il y a équivalence entre a = b et :

il existe (f,g,h,k,l,m,s,t,u,v,w,x,y,z) entiers strictement positifs tels que :

m – (w – 1)(w – 1)z = 1

w = b + h = n + l

a + g = 2mb – b – 1

(x – y(m – b) – a) = (f – 1)(2mb – b – 1)

x – (m – 1)y = 1

u – (m – 1)v = 1

s – (k – 1)t = 1

v = ry

k = 1 + 4py = m + qu

s = x + cu

t = n + 4(d – 1)y

y = n + e – 1

On montre que les coefficients binomiaux sont diophantiens en les considérant comme coefficients dans une base b assez grande de (b+1). Il en est de même des factorielles et des nombres premiers.

Le dixième problème de Hilbert consiste à définir un algorithme acceptant comme paramètre une équation diophantienne D et donnant comme réponse le fait que D admette ou non des solutions. En 1970, Matiyasevic montra qu'il était impossible qu'un tel algorithme existe.

On montre en effet qu'il y a équivalence entre les ensembles diophantiens et les ensembles reconnaissables par machine de Turing (ensembles également dits récursivement énumérables ou semi-calculables). Une machine de Turing modélise un programme donné sur un calculateur universel sans limitation de mémoire. Un ensemble récursivement énumérable E est un ensemble pour lequel il existe un algorithme tel que, si on donne comme paramètre à l'algorithme un élément a de E, alors l'algorithme s'arrête en fournissant une réponse positive, alors que si on donne comme paramètre un élément a n'appartenant pas à E, ou bien l'algorithme s'arrête en donnant une réponse négative, ou bien il boucle indéfiniment. Un ensemble récursivement énumérable est un ensemble dont on peut lister un à un les éléments. On peut être dans l'impossibilité de lister les éléments de son complémentaire.

Tout ensemble diophantien est récursivement énumérable

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 $\mathbb{N}$. Si x doit décrire ${\mathbb{N}}^p$, il convient de remplacer l'énumération des éléments de $\mathbb{N}$ par une énumération des éléments de ${\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.

Tout ensemble récursivement énumérable est diophantien

La réciproque est extrêmement délicate et constitue le nœud du théorème de Matiyasevich. Elle se prouve en codant les configurations d'une machine de Turing par des entiers et en montrant que la fonction qui, à une configuration de la machine au cours du calcul, associe la configuration suivante, est une fonction diophantienne. 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, en 1976, Jones a-t-il explicité un polynôme de degré 25 et des 26 variables a, b, ..., z, dont l'ensemble des valeurs positives coïncide avec l'ensemble des nombres premiers. Le voici :

(k+2)[1 – (wz+h+j–q) – [(gk+2g+k+1)(h+j) + h – z]

– (2n+p+q+z–e) – [16(k+1)(k+2)(n+1) + 1 – f]

– [e(e+2)(a+1) + 1 – o] – [(a–1)y + 1 – x]

– [16ry(a–1) + 1 – u]

– [((a+u(u–a))–1)(n+4dy) + 1 – (x+cu)] – [n+l+v–y]

– [(a–1)l + 1 – m] – [ai+k+1–l–i]

– [p + l(a–n–1) + b(2an+2a–n–2n–2) – m]

– [q+ y(a–p–1) + s(2ap + 2a – p – 2p – 2) – x]

– [z + pl(a–p) + t(2ap – p – 1) – pm]]

Impossibilité du dixième problème de Hilbert

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.