🔢 mathematics

An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

Cet article présente une preuve générée par IA démontrant que la résolubilité des équations diophantiennes sur les entiers de Gauss est indécidable avec seulement 18 variables, améliorant ainsi la limite précédente de 20 variables de Matiyasevich et Sun grâce à des techniques optimisées d'économie de variables.

Auteurs originaux : Yuchen Ding, Junfeng Li

Publié 2026-06-12

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yuchen Ding, Junfeng Li

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La vue d'ensemble : Le « puzzle insoluble »

Imaginez que vous avez une boîte à puzzle géante et magique. À l'intérieur se trouve une équation complexe (un problème mathématique) avec de nombreux nombres inconnus (variables). Votre objectif est de déterminer : « Cette équation possède-t-elle une solution ? »

Pendant longtemps, les mathématiciens savaient que si vous aviez assez de variables, cette question devenait impossible à répondre pour un programme informatique. C'est comme essayer d'écrire un livre de règles capable de dire si chaque labyrinthe possible possède une sortie ; finit par arriver un moment où les labyrinthes deviennent si tordus qu'aucun livre de règles ne peut tous les couvrir.

Cet article porte sur un type spécifique de boîte à puzzle appelé entiers de Gauss (des nombres qui ressemblent à $a + bi $, où$ i$ est la racine carrée de -1). Les auteurs, Yuchen Ding et Junfeng Li, ont utilisé une IA pour prouver que si votre boîte à puzzle possède 18 inconnues, il n'existe aucun programme informatique capable de dire systématiquement si une solution existe.

Le record précédent : 20 variables

Avant cet article, le meilleur résultat connu (établi par les mathématiciens Matiyasevich et Sun) était qu'il fallait 20 inconnues pour rendre le puzzle insoluble. Ils avaient une recette spécifique pour construire ces puzzles impossibles.

Les auteurs de cet article ont dit : « Nous pouvons le faire avec moins de pièces. » Ils ont réussi à réduire la recette de 20 pièces à 18.

Comment ils ont fait : Deux astuces ingénieuses

Pour comprendre comment ils ont économisé deux variables, imaginez que vous construisez une machine pour tester si un nombre est « réel » (un entier) dans un monde de nombres complexes.

Astuce 1 : La stratégie du « Pas de tasse supplémentaire »

L'ancienne méthode :
Imaginez que vous avez une recette qui nécessite de mélanger des ingrédients, mais que les instructions impliquent des fractions. Pour que les mathématiques fonctionnent sur un ordinateur, vous avez généralement besoin d'une tasse supplémentaire (une nouvelle variable) pour éliminer les dénominateurs (les nombres du bas des fractions) afin que tout devienne un nombre entier. Cette tasse supplémentaire occupe de l'espace dans votre limite de 20 variables.

La nouvelle méthode :
Les auteurs ont réalisé qu'ils n'avaient pas besoin de cette tasse supplémentaire. Au lieu d'ajouter une nouvelle variable pour nettoyer les fractions, ils ont simplement ajouté deux règles strictes aux ingrédients existants.

Analogie : Au lieu d'apporter un nouveau seau pour rattraper l'éclaboussure, ils ont simplement serré le couvercle des seaux existants pour que rien ne puisse déborder.
Résultat : Ils ont économisé une variable en forçant les mathématiques à rester « propres » sans avoir besoin d'une variable d'assistance.

Astuce 2 : Le gadget de la « Clé Magique »

L'ancienne méthode :
Dans l'ancienne recette, pour s'assurer qu'un nombre spécifique n'était pas zéro (ce qui est crucial pour que le puzzle fonctionne), ils avaient besoin de deux variables distinctes agissant comme une « vérification de sécurité ». C'était comme utiliser deux clés différentes pour déverrouiller une porte, juste pour s'assurer qu'elle n'est pas coincée.

La nouvelle méthode :
Les auteurs ont inventé un gadget spécial appelé « Clé Magique ». Ils ont créé une formule spécifique : $(2R + 1)(3R + 1)$ .

La Magie : Cette formule n'est jamais égale à zéro, peu importe le nombre que vous y injectez. Cependant, si vous avez n'importe quel nombre non nul que vous voulez « vérifier », vous pouvez trouver une valeur pour $R$ qui rend cette formule divisible par votre nombre.
L'économie : Comme cette seule formule effectue le travail de deux vérifications de sécurité distinctes, ils n'ont eu besoin que d'une seule variable ( $R$ ) au lieu de deux.
Résultat : Ils ont économisé la deuxième variable.

Le décompte final

En combinant ces deux astuces, ils ont réduit le nombre total d'inconnues nécessaires pour prouver que le puzzle est insoluble :

10 variables pour le puzzle principal (issu des travaux précédents).
3 variables pour le premier « test d'entier » (vérifier si les nombres sont entiers).
3 variables pour le second « test d'entier ».
1 variable pour l'étape de « combinaison ».
1 variable pour le gadget de la « Clé Magique ».
Total : 18 variables.

Ce que cela signifie

L'article prouve que pour tout programme informatique, il existe une limite au nombre de variables qu'il peut gérer avant que le problème ne devienne impossible à résoudre.

Avant : La limite était connue à 20.
Maintenant : La limite est prouvée à 18 (ou peut-être même moins, mais 18 est le nouveau seuil confirmé).

Les auteurs soulignent qu'ils n'ont pas trouvé le nombre le plus bas possible (peut-être est-ce 17 ou 16), mais qu'ils ont réussi à abaisser la barre de 20 à 18 en utilisant ces deux astuces spécifiques de « gain d'espace ».

Résumé

Voyez cela comme la préparation de bagages pour un voyage. L'ancienne règle disait : « Vous avez besoin de 20 valises pour transporter tous vos vêtements. » Ces auteurs ont regardé les vêtements, ont réalisé qu'ils pouvaient les plier plus serrés (Astuce 1) et utiliser un sac de compression (Astuce 2), et ont prouvé : « En fait, vous n'avez besoin que de 18 valises. »

Cela ne signifie pas que le voyage est plus facile ; cela signifie simplement que le seuil de l'« impossible » est atteint avec moins de ressources que nous ne le pensions.

Résumé technique : Une preuve par l'IA de l'indécidabilité à 18 variables des équations diophantiennes sur $\mathbb{Z}[i]$

Énoncé du problème
Cet article traite du dixième problème de Hilbert sur l'anneau des entiers de Gauss, $\mathbb{Z}[i]$ . Le problème consiste à déterminer s'il existe un algorithme pour décider si une équation polynomiale arbitraire sur un anneau donné possède une solution. Bien que l'indécidabilité de ce problème sur les entiers $\mathbb{Z}$ ait été établie par le théorème de Matiyasevich, Davis, Putnam et Robinson, un raffinement naturel concerne le nombre minimal d'inconnues requis pour maintenir l'indécidabilité. Les travaux antérieurs de Matiyasevich et Sun ont établi que l'indécidabilité est maintenue pour des équations à 20 inconnues sur $\mathbb{Z}[i]$ . Cet article présente une preuve réduisant cette borne à 18 inconnues.

Méthodologie et cadre
La preuve conserve le cadre général établi par Matiyasevich et Sun, qui repose sur trois composantes fondamentales :

Le théorème à variables fixes de Sun : Utilisation d'un ensemble récursivement énumérable mais non récursif $A \subseteq \mathbb{N}$ et d'un polynôme $P(Z_0, \dots, Z_{10})$ tel que l'appartenance à $A$ est équivalente à l'existence de solutions entières pour $P(a, z_1, \dots, z_{10}) = 0$ avec $z_{10} \neq 0$ .
Test diophantien pour les entiers rationnels : Utilisation d'un test polynomial spécifique (Lemme 3) pour déterminer si des éléments de $\mathbb{Z}[i]$ sont réellement des entiers rationnels.
Critère de rationalité : Application d'un critère (Lemme 4) sur $\mathbb{Q}(i)$ pour forcer les variables à être des entiers rationnels sur la base de la rationalité d'une somme spécifique construite.

Les auteurs parviennent à la réduction de 20 à 18 variables en introduisant deux modifications spécifiques à la construction précédente :

Contributions clés et modifications techniques

Élimination de la variable de suppression des dénominateurs :
Dans la construction à 20 variables, une variable auxiliaire était introduite pour supprimer les dénominateurs lors de l'application du critère de rationalité. Les auteurs remplacent cela par deux conditions d'entiers directes imposées aux variables $Z_1, \dots, Z_{10}$ .
Soit $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$ . Au lieu d'ajouter une variable pour supprimer les dénominateurs, la preuve impose les conditions :
$Y^{10} \in \mathbb{Z} \quad \text{et} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$
Puisque $Y \neq 0$ , ces conditions garantissent que la quantité $Y + \sum Z_k Y^{-k}$ est un nombre rationnel. Par le critère de rationalité, cela force tous les $Z_k$ à être des entiers rationnels. Cette modification économise une variable.
Absorption de la condition de non-nullité via un gadget à une variable :
La construction précédente nécessitait deux variables pour imposer une condition de non-nullité (spécifiquement pour le produit $Z_{10}V_0V_1$ ). Les auteurs introduisent un gadget polynomial à une variable $Q(R) = (2R + 1)(3R + 1)$ .

Propriétés : $Q(R)$ ne s'annule jamais sur $\mathbb{Z}[i]$ . De plus, pour tout entier non nul $n$ , il existe un entier $R$ tel que $n \mid Q(R)$ .
Application : Ce gadget est intégré dans le « lemme de combinaison de relations » (Lemme 2). Au lieu d'une équation séparée pour imposer la non-nullité, la condition est absorbée dans l'équation unique $f(C_0, C_1, N, Q(R), M) = 0$ . Si $N=0$ , l'équation se réduit à $Q(R)^4 = 0$ , ce qui est impossible. Ainsi, l'équation force implicitement $N \neq 0$ sans nécessiter de variable supplémentaire. Cette modification économise une seconde variable.

Répartition des variables
Le système résultant utilise exactement 18 variables :

$Z_1, \dots, Z_{10}$ : Les 10 variables de l'entrée à variables fixes de Sun.
$V_0, X_0, Y_0$ et $V_1, X_1, Y_1$ : Deux ensembles de 3 variables utilisés pour les tests d'entiers sur $U_0 = Y^{10}$ et $U_1 = W$ (où $W$ est dérivé de la somme).
$M$ : La variable de combinaison du lemme de combinaison de relations.
$R$ : La variable unique du gadget de non-nullité.
Total : $10 + 3 + 3 + 1 + 1 = 18$ .

Résultat principal
L'article prouve le Théorème 1 : Il n'existe pas d'algorithme pour décider si une équation polynomiale arbitraire $F(X_1, \dots, X_{18}) = 0$ avec des coefficients dans $\mathbb{Z}$ possède une solution dans $\mathbb{Z}[i]^{18}$ .

La preuve démontre que l'appartenance à l'ensemble non récursif $A$ peut être représentée par une seule équation polynomiale sur $\mathbb{Z}[i]$ en 18 inconnues. Selon le Lemme 1, le système fini d'équations dérivé de la construction peut être combiné en une seule équation polynomiale sans introduire de nouvelles variables, préservant ainsi les coefficients entiers.

Signification et revendications
Les auteurs affirment que ce résultat améliore le théorème de Matiyasevich et Sun sur les 20 inconnues en réduisant le nombre de variables de deux. L'article note explicitement qu'il ne prétend pas à l'optimalité absolue ; abaisser le compte plus bas (par exemple, à 17) nécessiterait des améliorations supplémentaires, telles qu'un test d'entier plus petit, un témoin partagé pour les conditions d'entiers, une entrée à variables fixes plus forte ou un mécanisme de combinaison différent. Ce travail sert de raffinement technique au sein du cadre établi de l'indécidabilité diophantienne sur les entiers de Gauss.