Additive systems for $\mathbb{Z}$ are undecidable

1. Problématique

Le papier s'intéresse aux systèmes additifs sur l'ensemble des entiers relatifs $\mathbb{Z}$. Un système additif est défini comme une collection de sous-ensembles $A = \{A_0, A_1, \dots\}$ d'un monoïde commutatif $M$ (ici $\mathbb{Z}$) telle que tout élément $n \in M$ possède une et une seule représentation sous la forme d'une somme finie $n = a_0 + a_1 + \dots$ où $a_i \in A_i$.

• Contexte connu : Pour les entiers naturels $\mathbb{N}_0$, la structure de ces systèmes est entièrement caractérisée par le théorème de de Bruijn (1956), qui établit que tout système additif pour $\mathbb{N}_0$ est une contraction d'un « système de nombres britannique » (généralisation des systèmes de numération à base variable).
• Le défi : Le cas de $\mathbb{Z}$ est notoirement difficile. Contrairement à $\mathbb{N}_0$, il n'existe pas de théorème de caractérisation simple. La question centrale du papier est la suivante : Étant donnée une collection canonique (une classe naturelle de candidats pour $\mathbb{Z}$), peut-on déterminer algorithmiquement si elle forme un système additif complet pour $\mathbb{Z}$ ?

2. Méthodologie

L'auteur adopte une approche interdisciplinaire combinant la combinatoire additive et la théorie des systèmes dynamiques.

A. Définition des collections canoniques

L'auteur introduit la notion de collection canonique, définie par deux suites :

1. Une suite de bases $(b_i)_{i \in \mathbb{N}_0}$ avec $b_i > 1$.
2. Une suite de systèmes de résidus complets $(T_i)_{i \in \mathbb{N}_0}$ modulo $b_i$, contenant 0.

La collection est formée des ensembles $A_i = (b_0 b_1 \dots b_{i-1}) T_i$.

• La somme directe de ces ensembles est toujours unique (par construction inductive des résidus).
• La collection est dite complète si sa somme directe couvre l'ensemble entier $\mathbb{Z}$.

B. Traduction en systèmes dynamiques

Le cœur de la méthodologie réside dans la traduction du problème de complétude en un problème de dynamique.
Pour un entier $n$, on définit une trajectoire via une suite de fonctions $f_i : \mathbb{Z} \to \mathbb{Z}$ :
$$f_i(n) = \frac{n - t_i(n)}{b_i}$$
où $t_i(n)$ est l'élément unique de $T_i$ congru à $n$ modulo $b_i$.

• Proposition clé : Une collection canonique est complète si et seulement si, pour tout $n \in \mathbb{Z}$, la trajectoire $(n, f_0(n), f_1(f_0(n)), \dots)$ atteint finalement la valeur 0 et y reste (s'annule).
• Cela transforme le problème combinatoire en un problème de convergence de systèmes dynamiques non autonomes.

C. Réduction aux problèmes indécidables

L'auteur construit des collections canoniques spécifiques dont la dynamique reproduit le comportement d'autres problèmes mathématiques célèbres :

1. Conjecture de Collatz : En choisissant judicieusement les bases $b_i$ et les ensembles $T_i$, la trajectoire de la collection canonique simule la suite de Collatz.
2. Programmes Fractran : En utilisant le langage de programmation esotérique Fractran (introduit par Conway, universel et Turing-complet), l'auteur définit une famille de collections « de type Fractran ». La dynamique de ces collections simule l'exécution d'un programme Fractran.

3. Résultats Principaux

Le papier établit des équivalences formelles entre la complétude des systèmes additifs et des problèmes indécidables :

• Théorème 1 (Équivalence avec Collatz) : Il existe une collection canonique $A_C$ telle que $A_C$ est un système additif complet pour $\mathbb{Z}$ si et seulement si la conjecture de Collatz est vraie.

  • Implication : Déterminer si une collection canonique donnée est complète est aussi difficile que de résoudre la conjecture de Collatz.

• Théorème 2 (Équivalence avec Fractran) : Pour tout programme Fractran $F$, on peut construire une collection canonique $A_F$ (de type Fractran) telle que $A_F$ est complète si et seulement si le programme $F$ s'arrête pour toutes les entrées (problème de l'arrêt universel).

• Corollaire 2 (Indécidabilité) : Le problème de décider si une collection canonique de type Fractran donnée est complète est indécidable.

  • Puisque le problème de l'arrêt universel pour Fractran est indécidable (aucun algorithme ne peut résoudre ce problème pour tous les programmes), il n'existe aucun algorithme général pour déterminer si une collection canonique forme un système additif pour $\mathbb{Z}$.

4. Contributions Clés

1. Généralisation naturelle : Introduction des « collections canoniques » qui généralisent à la fois les systèmes de numération pour $\mathbb{N}_0$ (systèmes britanniques) et les exemples classiques pour $\mathbb{Z}$ (comme le système binaire négatif ou la ternaire équilibrée).
2. Changement de paradigme : Passage d'une perspective de combinatoire additive à une perspective de systèmes dynamiques pour analyser la structure des systèmes additifs sur $\mathbb{Z}$.
3. Preuve d'indécidabilité : Démonstration que la question de la complétude pour les systèmes additifs sur $\mathbb{Z}$ n'est pas seulement difficile, mais fondamentalement indécidable, en reliant ce problème à la théorie de la calculabilité (via Fractran).
4. Lien avec la conjecture de Collatz : Établissement d'un lien direct entre un problème de théorie des nombres ouvert (Collatz) et la structure des systèmes additifs, suggérant que la résolution de l'un pourrait éclairer l'autre.

5. Signification et Impact

Ce travail a une importance significative pour plusieurs domaines :

• Théorie des nombres et Combinatoire : Il clarifie la complexité inhérente aux systèmes additifs sur $\mathbb{Z}$, montrant qu'ils ne peuvent pas être caractérisés par un théorème simple analogue à celui de de Bruijn pour $\mathbb{N}_0$. Il montre que l'absence de structure prévisible (« no structure should be expected ») pour les ensembles infinis est enracinée dans l'indécidabilité algorithmique.
• Systèmes Dynamiques : Le papier enrichit le champ des systèmes dynamiques non autonomes en y intégrant des problèmes de théorie des nombres et de calculabilité.
• Calculabilité : Il fournit un nouvel exemple naturel d'un problème mathématique « concret » (concernant des ensembles d'entiers et des sommes) qui est indécidable, renforçant la compréhension de la frontière entre les problèmes résolubles et non résolubles en mathématiques pures.

En résumé, Zabolotskii démontre que la question de savoir si une collection naturelle d'ensembles d'entiers forme un système de représentation unique pour tous les entiers relatifs est un problème aussi profond et potentiellement insoluble que la conjecture de Collatz ou le problème de l'arrêt de Turing.