💻 computer science

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

Cet article établit la décidabilité des expansions à une seule variable de l'arithmétique de Presburger pour les puissances fixes parfaites et les polynômes cubiques en s'appuyant sur des résultats concernant les équations diophantiennes hyperelliptiques et les courbes algébriques de genre faible, tout en démontrant que le relèvement de ces restrictions conduit à l'indécidabilité par le biais de codages de problèmes diophantiens ouverts.

Auteurs originaux : Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, Emil Rugaard Wieser

Publié 2026-05-19

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, Emil Rugaard Wieser

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

Imaginez que vous soyez un détective essayant de résoudre un immense puzzle. Ce puzzle est un ensemble de règles mathématiques concernant les nombres entiers (comme 1, 2, 3, -5, etc.). Votre objectif est de déterminer si une affirmation spécifique concernant ces nombres est vraie ou fausse.

Dans le monde des mathématiques, cela s'appelle l'arithmétique de Presburger. C'est comme un jeu avec des règles strictes : vous pouvez additionner, soustraire, comparer les tailles et vérifier si les nombres sont pairs ou impairs. Pendant longtemps, nous savions que ce jeu était « décidable » (résoluble) — ce qui signifie qu'il existe une méthode garantie pour répondre à toute question que vous posez, même si cela prend beaucoup de temps.

Cependant, l'article dont vous parlez explore ce qui se passe lorsque nous ajoutons de nouvelles règles, astucieuses, à ce jeu. Plus précisément, nous ajoutons des règles concernant les polynômes (expressions mathématiques comme $x^2$ , $x^3$ , ou $2n^3 - 5n + 3$ ).

Le Grand Problème : Le Piège des « Trop de Variables »

Les auteurs expliquent que si vous laissez le puzzle devenir trop compliqué — spécifiquement, si vous permettez à de nombreux nombres différents (variables) d'interagir avec ces nouvelles règles polynomiales — le jeu devient insoluble. C'est comme essayer de trouver une aiguille dans une botte de foin qui ne cesse de grandir indéfiniment ; aucun ordinateur, aussi puissant soit-il, ne peut garantir une réponse.

Cela est dû au fait que ces nouvelles règles sont suffisamment puissantes pour encoder le célèbre « Dixième Problème de Hilbert », qui a été prouvé impossible à résoudre dans le cas général.

La Solution : La Ruse de la « Variable Unique »

La découverte principale des auteurs est une astuce ingénieuse. Ils se demandent : Et si nous limitions le jeu à n'utiliser qu'une seule variable à la fois ?

Imaginez que vous essayiez de trouver un nombre spécifique $x$ qui satisfait une liste de conditions. Même si les conditions impliquent des formes complexes (polynômes), si vous ne cherchez qu'un seul nombre, le problème redevient résoluble.

L'article démontre que pour les puzzles à variable unique, nous pouvons décider de la réponse dans deux scénarios spécifiques :

Le Cas des « Puissances Parfaites » :
Imaginez que vous cherchiez des nombres qui sont des carrés parfaits ($1, 4, 9, 16...$), des cubes parfaits ($1, 8, 27...$), ou toute puissance fixe. Les auteurs montrent que si votre puzzle n'implique que ces formes de « puissances parfaites », vous pouvez le résoudre. Ils utilisent des mathématiques profondes sur les « équations hyperelliptiques » (des courbes sophistiquées) pour prouver que les solutions sont soit finies, soit suivent un motif prévisible qu'un ordinateur peut vérifier.
Le Cas des « Formes Simples » :
Imaginez que les formes soient limitées à des courbes simples : des lignes (degré 1), des paraboles (degré 2) ou des courbes cubiques (degré 3). Les auteurs prouvent que si votre puzzle n'utilise que ces formes simples, il est également résoluble. Ils s'appuient sur le fait que ces formes ne se « tordent » pas assez pour créer un chaos infini et insoluble.

Comment Ils Font : L'Astuce de la « Densité »

Les auteurs utilisent une stratégie brillante pour gérer les règles « négatives » (par exemple, « Trouvez un nombre qui n'est PAS un carré parfait »).

Les Règles Positives : D'abord, ils trouvent tous les nombres qui correspondent aux règles « positives » (par exemple, les nombres qui sont des carrés parfaits). Parfois, il y en a une infinité.
Les Règles Négatives : Ensuite, ils appliquent les règles « négatives ». Ils prouvent que même si vous devez exclure des nombres, les nombres que vous excluez sont si rares (comme trouver quelques grains de sable spécifiques sur une plage) qu'ils n'effacent pas toute la plage.
La Conclusion : Si la liste « positive » est infinie, et que les règles « négatives » n'enlèvent qu'une fraction minuscule et insignifiante, alors il reste encore une infinité de nombres. L'ordinateur peut dire : « Oui, une solution existe ! » sans avoir besoin de trouver le nombre exact.

Exemples du Monde Réel Tirés de l'Article

Les auteurs montrent que cette logique peut résoudre de célèbres énigmes mathématiques historiques, à condition qu'elles soient formulées comme des puzzles à variable unique :

Les Nombres Triangulaires de Fermat : Prouver qu'il n'existe aucun nombre triangulaire (comme 1, 3, 6, 10) supérieur à 1 qui soit aussi un cube parfait.
Les Cubes de Fibonacci : Prouver que 8 est le plus grand cube dans la suite de Fibonacci.
La Conjecture de Catalan : Vérifier si 9 et 8 sont les seules puissances parfaites ayant une différence exactement égale à 1.

La Limite : Quand Deux Variables Brisent le Jeu

L'article trace également une ligne dure. Si vous permettez deux variables (chercher deux nombres, $x$ et $y$ , qui fonctionnent ensemble), le jeu redevient insoluble, même si vous n'utilisez que des carrés parfaits.

Ils illustrent cela avec le problème du « Parfait Brick d'Euler » : Pouvez-vous construire un pavé droit où tous les côtés et toutes les diagonales sont des nombres entiers ? C'est un problème à trois variables. Les auteurs montrent que si nous pouvions résoudre notre jeu à variable unique pour deux variables, nous pourrions résoudre ce problème du pavé. Puisque le problème du pavé reste un mystère non résolu après 300 ans, notre jeu à deux variables doit également être insoluble.

Résumé

La Bonne Nouvelle : Si vous restreignez vos puzzles mathématiques à une variable et utilisez soit des « puissances parfaites », soit des « courbes simples » (jusqu'au degré 3), vous pouvez toujours écrire un programme informatique pour vous dire si une solution existe.
La Mauvaise Nouvelle : Dès que vous ajoutez une deuxième variable ou utilisez des courbes plus complexes, le puzzle devient impossible à résoudre dans le cas général.
La Méthode : Ils utilisent un mélange de théorie des nombres ancienne (équations diophantiennes) et de géométrie moderne pour prouver que les « bons » puzzles ont des motifs que nous pouvons exploiter, tandis que les « mauvais » sont trop chaotiques.

Cet article ne construit pas une nouvelle application ni ne guérit une maladie ; il se contente de cartographier les limites de ce qui est calculable dans le monde des nombres, nous montrant exactement où la « magie » de la résolubilité prend fin et où le « chaos » de l'inconnu commence.

Résumé technique : Sur les expansions non linéaires bornées en variables de l'arithmétique de Presburger

Énoncé du problème
L'arithmétique de Presburger, la théorie du premier ordre des entiers avec l'addition et l'ordre, est décidable. Cependant, son expansion par des prédicats non linéaires, tels que l'ensemble des carrés parfaits ( $Z^2$ ) ou les images de polynômes généraux, est connue pour être indécidable dans le cas général. Cette indécidabilité découle de la capacité à encoder la multiplication au sein de ces théories. Bien que la décidabilité du fragment existentiel de telles expansions reste un problème majeur ouvert (par exemple, la conjecture de Büchi concernant les carrés parfaits), cet article explore une voie différente pour retrouver la décidabilité : la restriction du nombre de variables.

Les auteurs se concentrent sur les expansions de l'arithmétique de Presburger bornées en variables avec des familles de prédicats polynomiaux monadiques. Plus précisément, ils examinent des fragments où le nombre de variables distinctes est borné par une constante $k$ (notés $FO_k$ , $\exists FO_k$ et $SMT_k$ ). Le défi central est que, même pour une seule variable ( $k=1$ ), la décidabilité de l'intersection de deux prédicats polynomiaux (par exemple, $f(u) = g(v)$ ) constitue un cas sévèrement restreint du dixième problème de Hilbert, qui est généralement ouvert.

Méthodologie
L'article emploie une combinaison de techniques de théorie des nombres, de géométrie algébrique et de théorie de la mesure pour analyser les ensembles de solutions des contraintes au sein de ces fragments à variables bornées.

Prétraitement et réduction : La procédure de décision commence par la réduction de sentences arbitraires à un problème de satisfiabilité impliquant une conjonction de contraintes. Ces contraintes incluent des inégalités linéaires ( $x > c$ ), de l'arithmétique modulaire ( $x \equiv_m c$ ) et des prédicats polynomiaux de la forme $R(ax+b)$ ou leurs négations $\neg R(ax+b)$ . Les auteurs utilisent le théorème des restes chinois pour consolider les contraintes modulaires et effectuent une analyse de cas pour éliminer les intervalles bornés, réduisant ainsi le problème à la détermination de la satisfiabilité de contraintes sur un domaine non borné.
Traitement des contraintes positives : Le cœur de la méthodologie consiste à caractériser les ensembles de solutions de systèmes de contraintes polynomiales positives.
- Pour les puissances fixes (par exemple, $Z_k = \{n^k\}$ ), les auteurs exploitent des résultats sur les équations diophantiennes hyperelliptiques. Ils montrent que l'intersection de deux telles contraintes produit un ensemble fini (si les degrés sont suffisamment élevés) ou un ensemble paramétré par des suites de récurrence linéaire (SRL) si les degrés sont 2.
- Pour les polynômes généraux de degré au plus 3, l'analyse repose sur le genre des courbes algébriques résultantes. Les systèmes impliquant des polynômes cubiques conduisent souvent à des courbes de genre 1 (courbes elliptiques) ou supérieures, qui possèdent un nombre fini de points entiers d'après le théorème de Siegel ou les bornes de Baker. Les systèmes impliquant des polynômes quadratiques sont liés aux équations de Pell, dont les solutions forment des SRL réversibles.
Traitement des contraintes négatives (arguments de densité) : Une insight cruciale est que lorsque l'ensemble de solutions des contraintes positives est infini, l'ensemble des solutions violant une contrainte négative (c'est-à-dire satisfaisant la version positive du prédicat nié) a une densité relative nulle au sein de l'ensemble de solutions original.
- Pour les images polynomiales, le taux de croissance de l'image est polynomial, tandis que l'ensemble « interdit » (s'il provient d'un polynôme différent) croît souvent à un rythme différent ou est épars.
- Dans les cas où l'ensemble de solutions est une SRL, les auteurs prouvent que les indices des solutions « interdites » forment des progressions arithmétiques. Cela permet une vérification effective pour déterminer si des solutions subsistent après l'exclusion du sous-ensemble de densité nulle.
Redondance et coalescence : Les auteurs définissent des notions de contraintes « redondantes » et « similaires ». Les contraintes redondantes peuvent être écartées, tandis que les contraintes similaires peuvent être fusionnées en une seule contrainte en utilisant les valuations $p$ -adiques et le théorème des restes chinois, simplifiant ainsi le système avant l'application des arguments de densité.

Contributions et résultats clés

L'article établit deux résultats principaux de décidabilité pour les théories à variable unique ( $k=1$ ) :

Décidabilité avec des puissances fixes : La théorie $FO_1\langle \mathbb{Z}; 0, 1, +, -, <, (\equiv_m)_{m\ge 2}, (Z_k)_{k\ge 2} \rangle$ est décidable. Ce résultat repose sur la résolubilité des équations diophantiennes hyperelliptiques ( $w^k - nz^j = N$ ) et sur le fait que les systèmes de telles équations ont un nombre fini de solutions ou des solutions paramétrées par des SRL.
Décidabilité avec des polynômes de faible degré : La théorie $FO_1\langle \mathbb{Z}; 0, 1, +, -, <, (\equiv_m)_{m\ge 2}, (R_i)_i \rangle$ est décidable, où chaque $R_i$ correspond à l'image d'un polynôme à valeurs entières de degré au plus 3. Ce résultat utilise le faible genre des courbes algébriques associées (genre 0 ou 1) et la structure des solutions des équations de Pell simultanées.

Résultats d'indécidabilité
Pour délimiter les frontières de ces résultats positifs, l'article fournit des preuves d'indécidabilité lorsque la borne en variables est levée ou que des prédicats spécifiques sont combinés :

Le fragment existentiel $SMT_2\langle \mathbb{Z}; 0, 1, +, -, Z^2 \rangle$ est indécidable. Cela est démontré en encodant la négation de la conjecture de Büchi, ce qui permet de définir la multiplication en utilisant un nombre limité de variables.
En utilisant les équations diophantiennes universelles de Jones et la preuve récente de Xiao de la conjecture de Büchi, les auteurs établissent que les théories avec des nombres de variables significativement plus élevés (par exemple, $SMT_{600}$ ou $SMT_{2200}$ avec $Z^2$ ) sont indécidables.

Signification
La signification de l'article réside dans l'identification de frontières précises où la décidabilité peut être retrouvée dans les expansions non linéaires de l'arithmétique de Presburger. En restreignant le nombre de variables à une seule, les auteurs démontrent que des résultats profonds de la géométrie diophantienne (tels que la finitude des points entiers sur les courbes de genre $\ge 2$ ) et la théorie des suites de récurrence linéaire suffisent à construire des procédures de décision.

L'ouvrage met en lumière une dichotomie : tandis que les expansions non linéaires générales sont indécidables, et que même le fragment existentiel avec deux variables et les carrés parfaits est indécidable, le cas à variable unique reste traitable pour de vastes familles de prédicats. Les auteurs notent que l'extension de ces résultats à deux ou trois variables est entravée par des problèmes ouverts célèbres, tels que l'existence de briques d'Euler parfaites (nécessitant 3 variables et $Z^2$ ) et le problème de la somme de trois cubes (nécessitant 2 variables et $Z^3$ ). Ainsi, l'article fournit un cadre rigoureux pour comprendre la complexité computationnelle des théories arithmétiques contraintes par des bornes en variables.