On a sequence of Kimberling and its relationship to the Tribonacci word

Cet article démontre les conjectures de Clark Kimberling concernant la séquence binaire définie par inflation, établit son lien avec le mot de Tribonacci infini, et détermine sa complexité factorielle ainsi que son exposant critique, en s'appuyant notamment sur le prouveur de théorèmes Walnut.

L'essentiel

Imaginez que vous êtes un architecte qui doit construire une ville infinie, brique par brique. Mais au lieu de briques ordinaires, vous avez des règles magiques pour transformer ces briques. C'est l'histoire de ce papier scientifique, qui ressemble un peu à un détective résolvant un mystère mathématique.

Voici l'explication de cette recherche, traduite en langage simple et imagé :

1. Le Mystère de la Séquence "Kimberling"

Tout commence avec un mathématicien nommé Clark Kimberling. En 2017, il a inventé une séquence de 0 et de 1 (comme un code binaire infini : 0100101100...).

Il a créé cette séquence avec une règle étrange, un peu comme un jeu de "transformation de Lego" :

• Si vous voyez un bloc 00, il se transforme en 0101.
• Si vous voyez un 1, il devient 10.
• Si vous voyez un 0 seul, il reste 0.

Kimberling a commencé avec 00, appliqué la règle, puis appliqué la règle au résultat, et ainsi de suite. Il a obtenu une suite infinie. Mais il s'est posé des questions :

• "Quelle est la longueur exacte de cette suite à chaque étape ?"
• "Y a-t-il des motifs cachés ?"
• "Est-ce que cette suite est équilibrée (autant de 0 que de 1) ?"

Il a fait des hypothèses (des conjectures), mais il n'avait pas la preuve formelle.

2. Les Détectives et leur Arme Secrète : Walnut

C'est là qu'interviennent les auteurs du papier (Lubomíra, Edita et Jeffrey). Ils sont comme des détectives modernes. Au lieu de faire des calculs à la main qui prendraient des siècles, ils utilisent un outil informatique très puissant appelé Walnut.

Imaginez Walnut comme un robot super-intelligent qui peut vérifier des milliards de cas en une seconde. Les chercheurs ont écrit un petit programme (un code) pour dire au robot : "Vérifie si mes hypothèses sont vraies pour tous les nombres possibles." Et le robot a répondu : VRAI. Ils ont ainsi prouvé mathématiquement que les idées de Kimberling étaient correctes.

3. Le Lien avec le "Mot de Tribonacci"

Le plus beau de l'histoire, c'est la découverte d'une parenté secrète.
Les chercheurs ont réalisé que la séquence de Kimberling n'est pas une île isolée. Elle est en fait un "déguisement" d'une séquence très célèbre appelée le Mot de Tribonacci.

• L'analogie : Imaginez le Mot de Tribonacci comme un arbre généalogique très ancien et complexe. La séquence de Kimberling est comme une photo de cet arbre, mais prise à travers un filtre spécial (une transformation mathématique).
• En utilisant ce filtre, les chercheurs ont pu voir que la structure de Kimberling est exactement la même que celle du Mot de Tribonacci, juste habillée différemment. C'est comme si on découvrait que deux personnes qui se ressemblent sont en fait des jumeaux séparés à la naissance.

4. La Complexité et le "Point de Rupture"

Une fois qu'ils ont compris la structure, ils ont voulu mesurer deux choses importantes :

• La Complexité des Facteurs (La diversité des motifs) :
  Combien de motifs différents de longueur n peut-on trouver dans cette suite ?

  • Résultat : C'est exactement 2n.
  • L'image : C'est comme si vous aviez un jeu de cartes où, pour chaque taille de main que vous choisissez, vous avez exactement le nombre maximum de combinaisons possibles sans jamais répéter. C'est un équilibre parfait, ni trop simple, ni trop chaotique.

• L'Exposant Critique (Le point de rupture) :
  À quel point cette suite peut-elle se répéter ? Si vous avez une phrase, pouvez-vous la répéter 3 fois de suite ? 3,5 fois ?

  • Résultat : La limite est d'environ 3,19.
  • L'image : Imaginez un élastique. Vous pouvez l'étirer jusqu'à un certain point avant qu'il ne casse. Ici, la séquence ne peut jamais contenir un motif répété plus de 3,19 fois de suite. C'est la limite de sa "résistance" à la répétition.

5. Pourquoi est-ce important ?

On pourrait se demander : "À quoi ça sert d'étudier une suite de 0 et de 1 ?"

1. La Méthode est la vraie star : Ce papier ne parle pas seulement de cette suite précise. Il montre comment utiliser des ordinateurs (Walnut) combinés à la logique humaine pour résoudre des problèmes complexes. C'est un manuel d'instruction pour les futurs mathématiciens.
2. La Beauté des Mathématiques : Cela montre comment des choses qui semblent différentes (la séquence de Kimberling et le Mot de Tribonacci) sont en réalité liées par des lois profondes et élégantes.
3. La Précision : Ils ont non seulement prouvé les idées de Kimberling, mais ils ont aussi donné des formules exactes pour prédire où se trouvent les 0 et les 1, utilisant un nombre spécial appelé la "constante de Tribonacci" (un peu comme le nombre Pi, mais pour cette suite).

En résumé

Ce papier, c'est l'histoire de trois chercheurs qui ont pris un casse-tête mathématique laissé par un ami, utilisé un robot informatique pour le résoudre, découvert qu'il était lié à un célèbre classique de la mathématique, et mesuré avec précision ses propriétés cachées. C'est une démonstration de la puissance de la collaboration entre l'intuition humaine et la puissance de calcul.

Résumé technique

Voici un résumé technique détaillé de l'article « On a sequence of Kimberling and its relationship to the Tribonacci word » en français.

1. Problématique

L'article se concentre sur l'analyse d'une suite binaire spécifique, notée $B$, définie par Clark Kimberling en 2017 (séquence A288462 dans l'OEIS). Cette suite est générée par un système de règles d'inflation (ou de substitution) non standard, plus complexe qu'un morphisme classique, appliqué itérativement à un mot initial $B_0 = 00$.

Les règles d'inflation sont définies comme suit :

• On factorise le mot actuel en blocs maximaux de la forme $00$,$0$et$1$.
• On applique les règles : $00 \mapsto 0101$,$0 \mapsto 0$,$1 \mapsto 10$.

Kimberling a émis plusieurs conjectures concernant cette suite, notamment :

1. La longueur des itérés $|B_i|$ suit une récurrence linéaire spécifique.
2. La suite $B$ est liée à la suite de Tribonacci.
3. Des propriétés asymptotiques concernant les indices des 0 et des 1 dans la suite.
4. La complexité factorielle et l'exposant critique de la suite.

L'objectif principal de l'article est de prouver rigoureusement ces conjectures et d'explorer la structure profonde de la suite $B$.

2. Méthodologie

Les auteurs combinent deux approches puissantes :

• Théorie des automates et logique du premier ordre : Utilisation de l'outil de preuve automatique Walnut. Cet outil permet de décider de la vérité de propositions exprimées en logique du premier ordre sur les suites automatiques, en particulier celles liées aux représentations numériques (ici, la représentation de Tribonacci).
• Théorie des mots et combinatoire : Utilisation de concepts avancés tels que les mots de retour, les facteurs bispeciaux, la complexité factorielle et les morphismes.

La méthodologie se déroule en plusieurs étapes :

1. Preuve des conjectures de longueurs : Démonstration par récurrence et analyse des blocs de la suite pour établir la relation de récurrence de la longueur.
2. Lien avec la suite de Tribonacci : Identification de la suite $B$ comme l'image d'un morphisme appliqué à la suite de Tribonacci infinie ($TR$).
3. Construction d'un automate : Développement d'un automate fini déterministe avec sortie (DFAO) capable de calculer le $n$-ième symbole de $B$ en utilisant la représentation de Tribonacci de $n$.
4. Preuves assistées par ordinateur : Utilisation de Walnut pour vérifier des propriétés globales (comme l'équilibre de la suite) et pour valider des bornes sur les indices des symboles.
5. Analyse théorique des facteurs bispeciaux : Pour déterminer la complexité factorielle et l'exposant critique, les auteurs analysent les facteurs bispeciaux (à la fois gauches et droits) de $B$ et leurs mots de retour, en s'appuyant sur la théorie des mots épisturmiens.

3. Contributions Clés et Résultats

A. Preuve des conjectures de Kimberling

Les auteurs prouvent que la longueur de l'itéré $i$, notée $|B_i|$, satisfait la récurrence $c_i = 2c_{i-1} - c_{i-4}$ pour $i \ge 4$, avec les conditions initiales données. Cela confirme la conjecture de Kimberling sur la croissance de la suite.

B. Relation avec la suite de Tribonacci

Le résultat central est l'identification de la structure de $B$. Les auteurs montrent que :
$$B = 0 \cdot f(TR)$$
où $TR$ est la suite de Tribonacci (point fixe du morphisme $0 \to 01, 1 \to 02, 2 \to 0$) et$f$est le morphisme défini par$0 \to 10, 1 \to 0, 2 \to 1$.
Cette relation permet de construire un automate efficace pour calculer $B[n]$ en utilisant la représentation de Tribonacci de $n$.

C. Propriétés d'équilibre

En utilisant Walnut, les auteurs démontrent que la suite $B$ est 3-équilibrée (la différence entre le nombre de 1 dans deux facteurs de même longueur est au plus 3), mais pas 2-équilibrée. La contre-exemple pour l'équilibre 2 apparaît à la longueur 47.

D. Indices des symboles

Les auteurs prouvent des versions précises des conjectures de Kimberling sur les indices des $n$-ièmes occurrences de 0 et de 1 :

• Pour l'indice $I_0(n)$ du $n$-ième 0 : $\lfloor \psi n \rfloor - 2 \le I_0(n) \le \lfloor \psi n \rfloor + 2$.
• Pour l'indice $I_1(n)$ du $n$-ième 1 : $\lfloor \gamma n \rfloor - 1 \le I_1(n) \le \lfloor \gamma n \rfloor + 3$.
  Ici, $\psi \approx 1.839286$ est la constante de Tribonacci (racine réelle de $x^3 - x^2 - x - 1$) et $\gamma = (\psi^2 + 1)/2 \approx 2.191487$.

E. Complexité Factorielle et Exposant Critique

• Complexité Factorielle : Les auteurs démontrent que la complexité factorielle de $B$ est $p(n) = 2n$ pour tout $n \ge 1$. Cela classe $B$ dans la catégorie des mots de Rote.
• Exposant Critique : L'exposant critique de $B$ (la borne supérieure des exposants des puissances contenues dans le mot) est calculé comme étant :
  $$ce(B) = 2 + \frac{1}{\psi - 1} \approx 3.19148788$$
  Ce résultat est obtenu en analysant le rapport entre la longueur des facteurs bispeciaux et celle de leurs mots de retour les plus courts, en s'appuyant sur la structure des facteurs bispeciaux de la suite de Tribonacci.

4. Signification et Impact

Ce travail est significatif à plusieurs titres :

1. Résolution de conjectures ouvertes : Il apporte une réponse définitive aux questions posées par Kimberling, transformant des observations empiriques en théorèmes rigoureux.
2. Démonstration de la puissance de l'approche hybride : L'article sert de modèle (ou de "primer") sur la manière de traiter des suites définies par des règles d'inflation complexes. Il montre comment combiner des preuves mathématiques traditionnelles (récurrence, analyse de morphismes) avec la vérification automatique via Walnut.
3. Lien structurel profond : Il établit un pont clair entre une suite définie par des règles d'inflation non morphiques et la célèbre suite de Tribonacci, révélant que la structure sous-jacente de $B$ est celle d'un mot épisturmien transformé.
4. Classification des suites : En prouvant que $B$ est un mot de Rote avec un exposant critique spécifique, l'article enrichit la classification des suites binaires et de leurs propriétés de répétition.

En résumé, cet article fournit une analyse complète d'une suite binaire intrigante, démontrant que des outils modernes de logique et d'automates peuvent résoudre des problèmes complexes de combinatoire sur les mots qui résistaient auparavant à une analyse purement manuelle.