💻 computer science

On the Decidability of Monadic Theories of Arithmetic Predicates

Cet article établit de nouveaux résultats de décidabilité, inconditionnels ou conditionnels, concernant la théorie monadique du second ordre de structures arithmétiques combinant l'ordre naturel avec des prédicats issus de suites de récurrence linéaire, de puissances fixes et de puissances entières, en exploitant des techniques issues de la théorie des systèmes dynamiques, de la théorie des nombres et de la théorie des automates.

Auteurs originaux : Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell

Publié 2026-03-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell

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

🕵️‍♂️ Le Grand Jeu de la Décision : Quand les Nombres Racontent une Histoire

Imaginez que vous êtes un détective chargé de vérifier si une histoire est vraie ou fausse. Dans le monde des mathématiques, cette "histoire" est une formule logique (une phrase complexe) et le "monde" dans lequel elle se déroule est une suite infinie de nombres.

Le papier de recherche de Valérie Berthé et de ses collègues s'intéresse à un jeu très spécifique : Peut-on toujours savoir si une phrase logique est vraie ou fausse dans un monde peuplé de nombres particuliers ?

Pour répondre à cette question, les chercheurs ont dû créer un pont entre trois mondes qui semblent très différents : la logique, les machines à calculer (automates) et la physique des mouvements (systèmes dynamiques).

Voici comment ils ont fait, étape par étape, avec des images simples.

1. Le Problème : Une Ville aux Règles Mystérieuses

Imaginez une ville infinie appelée $\mathbb{N}$ (les nombres 0, 1, 2, 3...). Dans cette ville, il y a une règle de base : les maisons sont numérotées dans l'ordre. C'est simple.

Mais, certains chercheurs ont ajouté des "quartiers spéciaux" dans cette ville.

Le quartier $2\mathbb{N}$ : toutes les maisons paires (2, 4, 6...).
Le quartier Fib : les maisons de la suite de Fibonacci (0, 1, 2, 3, 5, 8...).
Le quartier $\mathbb{N}^2$ : les maisons carrées (1, 4, 9, 16...).

La question est la suivante : Si je vous donne une phrase complexe comme "Il existe un nombre pair qui est aussi un carré et qui est plus grand que 100", pouvez-vous toujours trouver une réponse définitive (Vrai ou Faux) en utilisant un algorithme ?

Pour une seule règle (ex: juste les nombres pairs), c'est facile.
Pour plusieurs règles mélangées (ex: les pairs ET les carrés), c'est souvent un cauchemar. Les interactions entre ces règles peuvent devenir si complexes que la réponse semble impossible à trouver.

2. La Solution : Transformer le Texte en Musique

Les chercheurs ont eu une idée brillante : au lieu de lire les nombres un par un, transformons-les en musique (ou en un code binaire).

Imaginez que vous marchez dans la ville. À chaque numéro de maison, vous jouez une note :

Si la maison est dans le quartier "Pair", vous jouez un Do.
Si elle est dans le quartier "Carré", vous jouez un Ré.
Si elle est dans les deux, vous jouez les deux notes.

Vous obtenez ainsi une partition infinie (une suite de notes). Le problème de logique devient alors : "Cette partition infinie est-elle acceptée par un certain type de machine musicale ?"

C'est ici qu'intervient la première astuce : la compression.
Au lieu de regarder chaque note, les chercheurs regardent seulement l'ordre dans lequel les quartiers apparaissent. C'est comme si on enlevait les silences de la musique pour ne garder que la mélodie principale. Cela simplifie énormément le problème.

3. Le Secret : La Danse sur un Tapis Roulant (Systèmes Dynamiques)

Une fois qu'on a cette "mélodie" simplifiée, les chercheurs ont fait le lien avec la physique. Ils ont découvert que l'apparition de ces nombres suit les mêmes règles qu'un billard ou un tapis roulant.

L'analogie du Billard : Imaginez une bille qui roule sur une table de billard carrée. Elle rebondit sur les bords. Si vous tracez le chemin de la bille, vous obtenez une séquence de rebonds (gauche, haut, droite, bas...).
Les chercheurs ont prouvé que la façon dont les nombres (comme les puissances de 2 et les puissances de 3) s'entremêlent est exactement la même que la trajectoire d'une bille sur une table de billard multidimensionnelle.

Pourquoi est-ce utile ? Parce que les physiciens et les mathématiciens connaissent déjà très bien le comportement de ces billes ! Ils savent si la bille va visiter tous les coins de la table ou si elle va rester coincée dans un coin.

4. Les Résultats Magiques

En utilisant cette "bille mathématique", l'équipe a pu résoudre plusieurs énigmes qui étaient jusque-là des mystères :

✅ Le Duo Puissant : Ils ont prouvé qu'on peut décider la vérité pour le mélange des nombres pairs ( $2^N$ ) et de la suite de Fibonacci. C'est comme si on avait réussi à prédire la trajectoire d'une bille qui rebondit sur deux murs différents.
✅ Le Trio Puissant : Ils ont fait de même pour les puissances de 2, 3 et 6.
⚠️ Le Cas Spécifique (La Conjecture de Schanuel) : Pour les puissances de 2, 3 et 5, ils ont trouvé une solution, mais elle dépend d'une hypothèse mathématique non encore prouvée (la conjecture de Schanuel). C'est comme dire : "Si la physique de l'univers fonctionne exactement comme nous le pensons, alors oui, on peut résoudre ce problème."
✅ Les Racines Carrées : Ils ont lié le problème des nombres carrés ( $N^2$ ) et des puissances de 2 à la façon dont on écrit le nombre $\sqrt{2}$ en binaire (0 et 1). Si l'écriture de $\sqrt{2}$ est "aléatoire" (ce qu'on croit), alors le problème est résoluble.

5. Pourquoi c'est important ?

Ce papier est une victoire de l'ingéniosité. Il montre que pour résoudre des problèmes de logique pure (est-ce que cette phrase est vraie ?), il faut parfois sortir de la logique et aller voir du côté de la physique (comment bouge une bille ?) et de la théorie des nombres (comment les nombres se comportent ?).

En résumé :
Les chercheurs ont construit un pont entre des mondes séparés. Ils ont transformé une question de logique abstraite en un problème de mouvement physique. En comprenant comment "bougent" les nombres, ils ont pu dire "Oui, on peut toujours trouver la réponse" pour une grande classe de problèmes mathématiques qui semblaient insolubles.

C'est comme si, au lieu de chercher une aiguille dans une botte de foin, ils avaient découvert que la botte de foin était en fait un tapis roulant qui amenait l'aiguille directement à vous, à condition de savoir comment régler la vitesse du tapis !

1. Problématique

L'article s'attaque à un problème fondamental en logique mathématique et en théorie des automates : la décidabilité de la théorie du second ordre monadique (MSO) de structures de la forme $\langle \mathbb{N}; <, P_1, \dots, P_d \rangle$ , où $<$ est l'ordre usuel sur les entiers naturels et $P_1, \dots, P_d$ sont des prédicats unaires (ensembles d'entiers).

Contexte historique : La décidabilité de $\langle \mathbb{N}; < \rangle$ a été établie par Büchi (1962). La décidabilité de $\langle \mathbb{N}; <, P \rangle$ pour un seul prédicats "arithmétique" simple (comme les puissances $k^\mathbb{N}$ ou les $k$ -ièmes puissances $\mathbb{N}^k$ ) a été prouvée par Elgot et Rabin (1966) via la méthode de contraction.
Le défi : La difficulté majeure réside dans l'ajout de plusieurs prédicats simultanément. Les interactions complexes entre différents ensembles arithmétiques (par exemple, les puissances de 2 et les puissances de 3) créent des motifs d'ordre qui échappent aux techniques d'automates classiques.
Objectif : Déterminer si la théorie MSO est décidable pour des structures combinant plusieurs prédicats issus de la théorie des nombres, notamment :
- Les ensembles de termes de suites récurrentes linéaires (LRS) à racine dominante unique (ex: $k^\mathbb{N}$ , Fibonacci).
- Les ensembles de puissances et de puissances entières (ex: $\mathbb{N}^2$ et $2^\mathbb{N}$ ).

2. Méthodologie

Les auteurs développent une approche hybride combinant la théorie des automates, la théorie des nombres et la dynamique symbolique.

A. Réduction aux mots caractéristiques et mots d'ordre

Mots caractéristiques : Pour un ensemble de prédicats, on définit un mot infini $\alpha$ (mots caractéristiques) où chaque lettre encode la présence ou l'absence des éléments dans chaque prédicat à une position donnée.
Problème d'acceptation : La décidabilité de la théorie MSO est équivalente au problème d'acceptation d'un automate fini déterministe sur ce mot infini $\alpha$ (Théorème de Büchi).
Mots d'ordre (Order Words) : Les auteurs introduisent une compression du mot caractéristique en un mot d'ordre $\beta$ $β$ , qui ne conserve que l'ordre d'apparition des éléments des prédicats, en ignorant les "gaps" (les zéros).
- Ils prouvent que pour des prédicats effectivement procycliques (comportement périodique modulo $m$ ) et effectivement clairsemés (les écarts entre les prédicats divergent), le problème d'acceptation sur $\alpha$ est équivalent à celui sur $\beta$ (Théorème 3.12).

B. Modélisation par des systèmes dynamiques

Une fois réduits aux mots d'ordre, les auteurs modélisent la génération de ces mots via des systèmes dynamiques :

Cas des suites récurrentes (LRS) : L'ordre d'apparition des termes de suites comme $a_i \rho_i^n$ est modélisé par des translations sur un tore $\mathbb{T}^d$ (dynamique de Kronecker). La position des points sur le tore détermine quel prédicat apparaît en premier.
Cas des puissances et puissances entières : Pour des structures comme $\langle \mathbb{N}; <, \mathbb{N}^d, b^\mathbb{N} \rangle$ , la dynamique est liée aux développements en base $b$ de nombres algébriques (système de transformation $x \mapsto \{bx\}$ ).

C. Utilisation de conjectures et théorèmes profonds

Théorème de Baker : Utilisé pour établir des bornes effectives sur les différences entre termes de suites, garantissant la "clairesemence" et l'absence de collisions fréquentes.
Conjecture de Schanuel : Utilisée de manière conditionnelle pour traiter les dépendances linéaires entre les logarithmes des bases (ex: $\log 2, \log 3, \log 5$ ). Les auteurs montrent que la conjecture n'est nécessaire que pour la terminaison de l'algorithme, pas pour sa correction.

3. Contributions Clés et Résultats Principaux

Les résultats sont divisés en deux catégories principales : les suites récurrentes linéaires et les structures mixtes (puissances/puissances entières).

A. Suites Récurrentes Linéaires (LRS) à racine dominante unique

Soit $P_i = \{ a_i \rho_i^n : n \in \mathbb{N} \}$ .

Résultat inconditionnel (Théorème 4.4) : Si les nombres $1/\log(\rho_1), \dots, 1/\log(\rho_d)$ $1/ lo g (ρ_{1}), \dots, 1/ lo g (ρ_{d})$ sont linéairement indépendants sur $\mathbb{Q}$ $Q$ , la théorie MSO de $\langle \mathbb{N}; <, P_1, \dots, P_d \rangle$ $⟨ N; <, P_{1}, \dots, P_{d} ⟩$ est décidable.
- Exemple : $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N} \rangle$ est décidable.
Résultat conditionnel (Théorème 4.5) : En supposant la conjecture de Schanuel, la décidabilité est garantie même si les logarithmes sont dépendants, pourvu que les suites ne coïncident que finiment souvent (condition B).
- Exemple : $\langle \mathbb{N}; <, 2^\mathbb{N}, 3^\mathbb{N}, 5^\mathbb{N} \rangle$ est décidable sous Schanuel.
Décidabilité non uniforme (Théorème 4.9) : Pour des prédicats fixes (ex: $2^\mathbb{N}$ et $3^\mathbb{N}$ ), il existe un algorithme de décision qui "connaît" les relations polynomiales entre les logarithmes. Bien que non uniforme (l'algorithme dépend des constantes), cela prouve l'existence d'une procédure de décision.

B. Structures Mixtes : Puissances et Puissances Entières

Pour $P_1 = \{ q n^d \}$ et $P_2 = \{ p b^n \}$ .

Équivalence Turing (Théorème 5.1) : La théorie MSO de $\langle \mathbb{N}; <, P_1, P_2 \rangle$ est équivalente à celle de la structure engendrée par les développements en base $b$ de certains nombres algébriques (liés à $\sqrt[d]{p/q}$ ).
Cas spécifiques :
- $\langle \mathbb{N}; <, \mathbb{N}^2, 2^\mathbb{N} \rangle$ est équivalent à la théorie MSO du développement binaire de $\sqrt{2}-1$ .
- Si le développement binaire de $\sqrt{2}$ est normal (conjecture largement admise), alors la théorie est décidable.
- $\langle \mathbb{N}; <, 4^\mathbb{N}, \mathbb{N}^2 \rangle$ est décidable (car les développements sont périodiques).

C. Outils Théoriques

Introduction de la notion de mots uniformément récurrents et de leur lien avec les séquences de découpe (cutting sequences) sur un tore.
Démonstration que les mots d'ordre générés par ces suites sont des séquences de découpe, permettant d'appliquer des résultats de complexité de facteurs (Bédaride, Baryshnikov) pour prouver la décidabilité.

4. Signification et Impact

Avancée théorique : Ce travail résout des cas ouverts depuis des décennies concernant la combinaison de prédicats arithmétiques. Il démontre que la complexité de l'interaction entre plusieurs prédicats peut être maîtrisée par la modélisation dynamique.
Frontière de la décidabilité : L'article établit une frontière claire entre ce qui est décidable (sous des hypothèses standards ou la conjecture de Schanuel) et ce qui reste ouvert (problèmes liés aux suites récurrentes non-diagonalisables ou à des prédicats comme les factorielles).
Lien Interdisciplinaire : Il renforce les connexions entre la logique, la théorie des nombres (théorème de Baker, conjecture de Schanuel, nombres normaux) et la théorie des automates.
Limites et Ouvertures :
- La décidabilité de la théorie MSO de $\langle \mathbb{N}; <, \text{Fibonacci}, 2^\mathbb{N} \rangle$ est prouvée.
- Cependant, des problèmes comme la décidabilité de $\langle \mathbb{N}; <, \{n!\}, \mathbb{N}^2 \rangle$ restent liés à des problèmes ouverts profonds (ex: problème de Brocard-Ramanujan) et ne sont pas résolus ici.
- La dépendance à la conjecture de Schanuel pour certains cas (comme $2^\mathbb{N}, 3^\mathbb{N}, 5^\mathbb{N}$ ) montre que la décidabilité absolue de ces structures dépend de conjectures non résolues en théorie des nombres transcendantale.

En résumé, cet article fournit un cadre robuste et puissant pour analyser la décidabilité de structures arithmétiques complexes, en transformant des problèmes logiques en problèmes de dynamique sur les tores et de propriétés de développements numériques.