🔢 mathematics

Meta-automatic Sequences

Cet article introduit le concept de séquences méta-automatiques, une combinaison naturelle des récurrences de Fibonacci méta et des séquences automatiques, en démontrant l'existence de telles séquences non dénestables et en établissant leurs évaluations par DFAO, leurs morphismes uniformes et leurs complexités en facteurs.

Auteurs originaux : John M. Campbell, Benoit Cloitre

Publié 2026-03-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : John M. Campbell, Benoit Cloitre

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

🧩 L'histoire des suites qui se regardent dans le miroir

Imaginez que vous avez deux types de règles pour créer une longue liste de nombres (une suite), comme une recette de cuisine infinie.

1. La recette "Miroir" (Les suites méta-Fibonacci)
C'est comme une recette où, pour savoir combien d'ingrédients vous devez mettre à l'étape 100, vous devez d'abord regarder combien vous en avez mis à l'étape 50, mais pas n'importe comment. Vous devez utiliser le résultat de l'étape 50 pour décider où aller chercher l'information suivante.

L'analogie : C'est comme un jeu de l'où oie où la case sur laquelle vous atterrisse dépend du nombre que vous venez de lancer. C'est très compliqué, parfois impossible à prédire, et les mathématiciens ne savent même pas si la recette fonctionne pour tous les nombres ! C'est ce qu'on appelle une suite "méta-Fibonacci".

2. La recette "Code-barres" (Les suites automatiques)
C'est une recette beaucoup plus simple et prévisible. Pour savoir ce qu'il faut faire à l'étape 100, vous regardez simplement les chiffres du nombre 100 (par exemple, en base 2 : 1100100). La règle dépend uniquement de ces chiffres, pas du résultat précédent.

L'analogie : C'est comme un code-barres sur un produit. Si vous scannez les barres (les chiffres), la machine sait exactement ce qu'il faut faire. C'est ce qu'on appelle une suite "automatique".

🚀 Le grand mélange : Les suites "Méta-Automatiques"

Les auteurs de cet article, John Campbell et Benoît Cloitre, se sont demandé : "Et si on mélangeait les deux ?"

Ils ont créé une nouvelle catégorie de suites qu'ils appellent "Méta-Automatiques".

Le concept : Imaginez une recette qui utilise le code-barres (comme les suites automatiques) pour décider de l'étape suivante, MAIS qui utilise aussi le résultat précédent pour modifier ce code-barres avant de l'appliquer.
L'analogie : C'est comme si vous lisiez un code-barres, mais que le lecteur changeait légèrement les lignes du code en fonction de ce qu'il a lu la fois précédente. C'est un mélange dangereux ! Normalement, ce genre de mélange crée un chaos imprévisible.

🛡️ Le secret : L'équilibre parfait (La "Balance")

Le génie de cet article réside dans une astuce spéciale. Les auteurs ont imposé une règle très stricte : l'équilibre.
Dans leurs suites, si vous prenez deux nombres consécutifs (un pair et l'impair), leur somme doit toujours faire 1 (donc un est 0, l'autre est 1). C'est comme une balance parfaite qui ne penche jamais d'un côté.

Pourquoi c'est magique ?
Normalement, mélanger les deux types de recettes crée un monstre imprévisible. Mais grâce à cette règle d'équilibre, les auteurs ont découvert que le chaos se transforme en ordre.
- L'analogie : Imaginez un danseur qui fait des pas de danse très compliqués et imprévisibles (méta-Fibonacci). S'il est obligé de toujours garder un équilibre parfait sur une corde raide (la règle d'équilibre), ses mouvements, bien que complexes, finissent par suivre un schéma répétitif et prévisible (automatique).

🔍 Ce qu'ils ont découvert (Les deux héros M1 et M2)

Les auteurs ont construit deux suites spécifiques, qu'ils appellent M1 et M2.

Elles sont "indénouables" : C'est-à-dire qu'on ne peut pas les simplifier en une simple recette de code-barres classique. Elles gardent leur âme "méta".
Elles sont pourtant prévisibles : Grâce à l'équilibre, on peut les calculer avec une machine simple (un automate à états finis), comme un petit robot qui suit un chemin précis.
La différence entre M1 et M2 :
- M1 est comme un labyrinthe avec un peu de magie : il suit une règle où le résultat précédent modifie le chemin.
- M2 est encore plus étrange : il ressemble à une version "filtrée" de la célèbre suite de Thue-Morse (une suite très connue en mathématiques). M2 est en fait la suite de Thue-Morse, mais avec certains bits (chiffres binaires) masqués ou effacés selon un motif précis.

📊 Pourquoi est-ce important ?

C'est comme si les auteurs avaient découvert un nouveau type de cristal.

D'un côté, ils ont des structures mathématiques qui devraient être chaotiques (les suites méta-Fibonacci).
De l'autre, ils ont montré que si on les force à respecter une règle d'équilibre, elles deviennent belles, ordonnées et prévisibles.

Ils ont même réussi à dessiner les "machines" (les diagrammes d'états) qui génèrent ces suites et à calculer exactement combien de motifs différents on peut trouver dans ces suites (la complexité factorielle).

En résumé

Cet article raconte l'histoire de deux mathématiciens qui ont pris des règles de cuisine très compliquées et imprévisibles, y ont ajouté une règle d'équilibre stricte, et ont découvert que cela créait de nouvelles suites fascinantes. Ces suites sont à la fois complexes (elles se regardent dans le miroir) et simples (elles peuvent être générées par une machine), prouvant que parfois, l'équilibre est la clé pour transformer le chaos en ordre.

1. Problématique et Contexte

L'article s'inscrit à l'intersection de la théorie des nombres et de la combinatoire, en cherchant à combiner deux classes de suites bien distinctes :

Les suites méta-Fibonacci (ou récurrences imbriquées) : Comme la suite $Q$ de Hofstadter, où le terme $a(n)$ dépend de valeurs antérieures dont les indices eux-mêmes dépendent de la suite (ex: $Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ ). Ces suites sont souvent mal comprises, avec des propriétés de définition et de régularité encore ouvertes.
Les suites automatiques : Définies par des récurrences basées sur les chiffres (digit-based), où $a(kn+j)$ est une fonction de valeurs antérieures $a(n), a(2n), \dots$ . Elles sont caractérisées par le fait que leur $k$ -noyau est fini et peuvent être générées par un automate fini déterministe à sortie (DFAO).

Le problème central : Existe-t-il une classe de suites qui combine la nature « imbriquée » des suites méta-Fibonacci avec la structure régulière des suites automatiques ? Les auteurs s'interrogent spécifiquement sur la possibilité de construire des suites méta-automatiques qui ne sont pas « dénestables » (c'est-à-dire qui ne peuvent pas être réduites à une simple récurrence basée sur les chiffres sans perte d'information structurelle).

2. Méthodologie

Les auteurs développent un cadre formel pour définir et analyser ces nouvelles suites :

Définition de la suite méta-automatique : Ils introduisent une définition formelle où le terme $U(q^{t+1}n + j)$ est déterminé par une fonction appliquée à un tuple contenant des termes de la suite et des « sélecteurs » méta-automatiques (des expressions où l'argument dépend de la valeur de la suite elle-même, ex: $U(qi_0 n + j_0 + S \cdot U(\dots))$ ).
Concept de « dénestabilité » (Denestability) : Une suite méta-automatique est dite dénestable si ses sélecteurs peuvent être réécrits sous forme de récurrences basées sur les chiffres (comme dans le critère d'Allouche-Shallit) sans augmenter la taille du noyau. L'objectif est de trouver des suites non-dénestables.
Contrainte d'équilibre (Balancedness) : L'étude se concentre sur les suites binaires équilibrées, satisfaisant $a(2n) + a(2n+1) = 1$ . Cette contrainte est cruciale car elle permet de linéariser les sélecteurs méta-automatiques via l'opération XOR ( $\oplus$ ) dans le corps fini $\mathbb{F}_2$ .
Passage à la base 4 : Les auteurs démontrent que pour éviter la périodicité ultime (qui survient en base 2 avec des sélecteurs simples), il faut travailler en base 4 tout en préservant la structure dyadique de l'équilibre.
Outils d'analyse : Utilisation d'automates finis déterministes à sortie (DFAO), de morphismes uniformes, et de l'analyse de la complexité des facteurs (nombre de sous-mots distincts de longueur $n$ ).

3. Contributions Clés

L'article présente deux nouvelles suites entières, notées M1 et M2, qui sont les premières constructions explicites de suites méta-automatiques non-dénestables.

A. Définition des suites M1 et M2

M1 (A392736) : Une suite « mixte » où une branche de la récurrence utilise un sélecteur méta-automatique ( $M1(4n+2) = M1(2n+1 - M1(n))$ ) et l'autre est standard.
M2 (A391614) : Une suite « pure » où les deux branches utilisent des sélecteurs méta-automatiques ( $M2(4n) = M2(2n + M2(n))$ et $M2(4n+2) = M2(2n+1 - M2(n))$ ).

B. Résultats Théoriques Principaux

Non-dénestabilité (Théorème 23) : Les auteurs prouvent que ni M1 ni M2 ne sont dénestables. Leurs noyaux 4-automatiques nécessitent un état « relevé » (lifted state) de dimension 2 (c'est-à-dire qu'il faut suivre non seulement $a(n)$ mais aussi une fonction auxiliaire dépendante de $a(n)$ ) pour être fermés. Cela les distingue des suites automatiques classiques.
Linéarisation $\mathbb{F}_2$ : Grâce à la contrainte d'équilibre, les sélecteurs non linéaires se transforment en applications affines sur $\mathbb{F}_2$ $F_{2}$ .
- Pour M1 : $M1(2n+1 - M1(n)) = M1(2n+1) \oplus M1(n)$ .
- Pour M2 : Des relations similaires permettent de définir un automate à 4 états.
Construction Automatique :
- Les deux suites sont 4-automatiques.
- Les auteurs construisent explicitement des DFAO à 4 états (MSB-first, base 4) pour M1 et M2.
- Ils fournissent des morphismes 4-uniformes dont les points fixes, codés par une application $\tau$ , génèrent ces suites.
Formules explicites :
- Pour M2, une formule explicite est donnée : $M2(n) = t(q(n))$ , où $t$ est la suite de Thue-Morse et $q$ est un opérateur de masquage de bits qui annule certains bits de la représentation binaire de $n$ selon leur position modulo 6.
- Pour M1, la structure est plus complexe, nécessitant un noyau de taille deux.
Complexité des Facteurs :
- Les auteurs analysent la fonction de complexité $p(n)$ (nombre de facteurs distincts de longueur $n$ ).
- Ils montrent que $p_{M1}(n)$ et $p_{M2}(n)$ sont de l'ordre de $\Theta(n)$ , ce qui est typique des suites générées par des morphismes primitifs.
- Des formules exactes et des comportements asymptotiques sont établis pour les longueurs dyadiques et les intervalles intermédiaires, révélant des différences structurelles marquées entre M1 et M2 malgré leur même taille d'automate (4 états).

4. Résultats et Signification

Preuve de concept : L'article démontre qu'il est possible de créer des suites qui sont intrinsèquement « méta » (leurs définitions dépendent de leurs propres valeurs) tout en restant automatiques (régulières et générables par automate).
Rôle de l'équilibre : La découverte clé est que la contrainte d'équilibre binaire agit comme un mécanisme de linéarisation. Elle transforme des récurrences non linéaires et potentiellement chaotiques en applications affines sur $\mathbb{F}_2$ , permettant ainsi l'application de la théorie des suites automatiques.
Distinction structurelle : Bien que M1 et M2 partagent la même taille d'automate (4 états), leur complexité structurelle diffère. M2 admet une factorisation simple via la suite de Thue-Morse, tandis que M1 nécessite une structure de noyau plus élevée, illustrant la richesse de la classe des suites méta-automatiques.
Ouverture vers d'autres bases : Les auteurs suggèrent que ce mécanisme pourrait s'étendre à d'autres contraintes d'équilibre (par exemple, ternaire avec une somme de 2 sur trois termes), ouvrant la voie à l'étude de suites 3-automatiques méta-automatiques.

En résumé, cet article établit un pont théorique solide entre les récurrences imbriquées complexes et la théorie des suites automatiques, en introduisant une nouvelle classe de suites qui échappent aux critères classiques de dénestabilité tout en conservant une structure algorithmique rigoureuse.