La Séquence Auto-Génératrice de Cloitre

Informations Fondamentales

• ID de l'article: 2501.00784
• Titre: La Séquence Auto-Génératrice de Cloitre
• Auteur: Jeffrey Shallit (Université de Waterloo)
• Classification: math.CO cs.DM cs.FL math.NT
• Date de publication: 3 janvier 2025
• Lien de l'article: https://arxiv.org/abs/2501.00784

Résumé

En 2009, Benoit Cloitre a introduit une séquence auto-génératrice particulière $(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots$ possédant la propriété suivante : la somme de tous les termes du $n$-ième bloc (run) est égale au double du $n$-ième terme de la séquence. Cet article établit un lien entre cette séquence et la séquence du pliage de papier, et prouve la conjecture de Cloitre concernant la densité des chiffres 1 dans la séquence.

Contexte et Motivation de la Recherche

Problématique de Recherche

La problématique centrale de cet article concerne l'analyse des propriétés structurelles de la séquence auto-génératrice de Cloitre, en particulier :

1. La relation entre cette séquence et les objets mathématiques connus (séquence du pliage de papier)
2. Le problème de la densité asymptotique des chiffres 1 dans la séquence

Importance du Problème

Les séquences auto-génératrices occupent une place importante en mathématiques combinatoires, révélant des propriétés structurelles complexes tout en étant liées à plusieurs branches des mathématiques. L'étude de la séquence de Cloitre présente l'intérêt suivant :

• Approfondir la compréhension des propriétés des séquences auto-génératrices
• Établir de nouveaux liens avec des séquences classiques telles que la séquence du pliage de papier
• Fournir de nouveaux cas d'application de la théorie des automates dans l'analyse des séquences

Limitations de la Recherche Existante

Les recherches existantes sur des séquences similaires (comme la séquence d'Oldenburger-Kolakoski) indiquent que les propriétés asymptotiques de ces séquences sont souvent difficiles à analyser. Par exemple, pour la séquence d'Oldenburger-Kolakoski, la question de savoir si la densité des 1 est égale à 1/2 reste une conjecture non résolue.

Motivation de la Recherche

Cloitre a proposé dans l'entrée OEIS A157196 une conjecture selon laquelle la densité des 1 dans cette séquence serait égale à 2/3, ce qui fournit un objectif explicite pour cette recherche.

Contributions Principales

1. Établissement de nouveaux liens entre séquences : Découverte pour la première fois d'un lien profond entre la séquence auto-génératrice de Cloitre et la séquence régulière du pliage de papier
2. Preuve de la conjecture de densité : Preuve rigoureuse de la conjecture de Cloitre selon laquelle la densité des 1 dans la séquence est égale à 2/3
3. Fourniture de bornes précises : Preuve que $0 \leq 3g_n - 2n \leq 4$, où $g_n$ est le nombre de 1 parmi les $n$ premiers termes
4. Développement d'une méthode automatiste : Utilisation d'automates finis et du logiciel Walnut pour fournir un cadre de vérification computationnelle pour l'analyse des séquences
5. Extension au cas général : Généralisation des résultats à des séquences de pliage de papier arbitraires

Explication Détaillée des Méthodes

Définition de la Tâche

Étude de la séquence de Cloitre $(a_n)_{n\geq 1}$ définie par la règle auto-génératrice suivante :

• La séquence prend des valeurs dans l'alphabet {1,2}
• Elle commence par $a_1 = 1$
• La somme de tous les éléments du $n$-ième bloc est égale à $2a_n$

Architecture de la Méthode Principale

1. Chaîne de Construction de Séquences

L'article construit une série de séquences interconnectées :

• Séquence régulière du pliage de papier $(p_n)$
• Version binaire $(q_n)$ satisfaisant $p_n = (-1)^{q_n}$
• Séquence des différences du premier ordre $(d_n)$
• Séquence des valeurs absolues $(d'_n)$
• Positions de fin de bloc $(e'_n)$
• Obtention finale de $(b_n) = (a_n)$

2. Représentation par Automate

Chaque séquence peut être représentée par un automate fini :

• DFAO (Automate Fini Déterministe avec Sortie) : pour les séquences prenant des valeurs finies
• Automates Synchrones : pour les séquences prenant des valeurs entières
• Tous les automates utilisent la représentation binaire avec le bit le moins significatif en premier

3. Cadre de Vérification Walnut

Utilisation du logiciel Walnut pour la vérification formelle :

eval q_test "?lsd_2 An (Q[2*n]=Q[n] & Q[4*n+1]=@0 & Q[4*n+3]=@1)":

Points d'Innovation Technique

1. Connexion avec la Séquence du Pliage de Papier

Découverte innovante du lien entre la séquence de Cloitre et la séquence du pliage de papier : $q_{2n} = q_n, \quad q_{4n+1} = 0, \quad q_{4n+3} = 1$

2. Stratégie de Conjecture-Vérification

Pour les séquences complexes (comme les positions de fin de bloc), adoption d'une stratégie de « conjecture d'automate puis vérification », qui est une méthode efficace pour traiter les séquences automatiques.

3. Analyse Multi-Niveaux de Séquences

Décomposition de la propriété auto-génératrice complexe en calculs automatiques traitables par la construction de plusieurs séquences intermédiaires.

Configuration Expérimentale

Outils de Calcul

• Logiciel Walnut : pour les calculs automatiques et la vérification formelle
• Automates Finis : toutes les séquences sont représentées et calculées via des automates
• Base de Données OEIS : pour la vérification et la comparaison des séquences

Méthodes de Vérification

1. Vérification de la Correction des Automates : vérification de la correction des automates par plusieurs conditions
2. Vérification des Relations de Récurrence : vérification que les séquences satisfont les relations de récurrence
3. Vérification des Conditions aux Limites : vérification des conditions initiales et des cas particuliers

Détails d'Implémentation

• Utilisation de la représentation binaire avec le bit le moins significatif en premier
• Nombre d'états des automates variant de 4 à 32
• Tous les calculs sont vérifiés formellement par Walnut

Résultats Expérimentaux

Preuve des Théorèmes Principaux

Théorème 2 : Soit $g_n$ le nombre de 1 dans la séquence $a_1a_2\cdots a_n$, alors : $0 \leq 3g_n - 2n \leq 4$ Par conséquent, $\lim_{n\to\infty} g_n/n = 2/3$.

Résultats de Vérification Clés

1. Cohérence des Séquences : vérification que $b_n = a_n$, c'est-à-dire que la séquence construite est effectivement la séquence de Cloitre
2. Propriété Auto-Génératrice : vérification que $\sigma_n = 2b_n$, où $\sigma_n$ est la somme du $n$-ième bloc
3. Longueur des Blocs : preuve que la longueur des blocs ne peut être que 1, 2 ou 4
4. Bornes de Densité : vérification des bornes de densité via un automate à 16 états

Découvertes Supplémentaires

Preuve que la séquence $w_n = \min\{t \geq 1 : e'_t \geq n\}$ est la séquence OEIS A091960, satisfaisant :

• $w_1 = 1$
• $w_{2n} = w_{2n-1} + (w_n \bmod 2)$
• $w_{2n+1} = w_{2n} + 1$

Travaux Connexes

Séquences Connexes Principales

1. Séquence d'Oldenburger-Kolakoski : $k := 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, \ldots$
   • Le $n$-ième terme est égal à la longueur du $n$-ième bloc
   • Le problème de la densité des 1 reste non résolu
2. Séquence de Dekking : $1, 3, 3, 3, 1, 1, 1, 3, 3, 3, \ldots$
   • La séquence des longueurs de blocs est égale à la séquence elle-même
   • Peut être comprise comme le point fixe d'une morphologie
3. Séquence du Pliage de Papier : séquence produite par le pliage itératif de papier
   • Lien profond avec la représentation binaire
   • Calculable par automate fini

Unicité de la Contribution de cet Article

La séquence de Cloitre est plus facile à traiter que la séquence d'Oldenburger-Kolakoski car elle possède un lien subtil mais explicite avec la représentation binaire, ce qui rend la méthode automatiste particulièrement efficace.

Conclusion et Discussion

Conclusions Principales

1. Théorème de Densité : preuve rigoureuse que la densité des 1 dans la séquence de Cloitre est égale à 2/3
2. Liens Structurels : établissement d'un lien profond avec la séquence du pliage de papier
3. Cadre Computationnel : démonstration de la puissance de la méthode automatiste dans l'analyse des séquences

Universalité de la Méthode

La section 7 de l'article montre que tous les résultats peuvent être généralisés à des séquences de pliage de papier arbitraires, bien que dans le cas général, il n'existe pas d'analogue évident de la propriété auto-génératrice.

Directions Futures

1. Étude des liens entre d'autres séquences auto-génératrices et des séquences classiques
2. Développement d'un cadre automatiste plus général pour l'analyse
3. Exploration des applications dans d'autres branches des mathématiques

Évaluation Approfondie

Points Forts

1. Innovation Méthodologique : combinaison ingénieuse de la théorie des automates et de l'analyse des séquences
2. Rigueur : tous les résultats sont vérifiés formellement
3. Complétude : non seulement la conjecture principale est prouvée, mais des propriétés structurelles supplémentaires sont découvertes
4. Extensibilité : la méthode peut être généralisée à une classe plus large de séquences

Points Techniques Remarquables

1. Stratégie de Conjecture-Vérification : fournit une méthode pratique pour l'analyse de séquences automatiques complexes
2. Construction Multi-Niveaux de Séquences : simplification de l'analyse de propriétés complexes par des séquences intermédiaires
3. Vérification Computationnelle : l'utilisation du logiciel Walnut garantit la fiabilité des résultats

Limitations

1. Complexité Computationnelle : certains automates possèdent un nombre d'états relativement élevé, ce qui peut limiter l'analyse de séquences plus complexes
2. Dépendance à la Conjecture : certains automates nécessitent une conjecture préalable suivie d'une vérification, manquant d'une méthode de construction systématique
3. Restrictions de Généralisation : bien que généralisable à des séquences de pliage de papier arbitraires, la propriété auto-génératrice est perdue

Impact

1. Contribution Théorique : fournit de nouveaux outils d'analyse pour la recherche sur les séquences auto-génératrices
2. Valeur Méthodologique : démontre l'application de la preuve assistée par ordinateur en mathématiques combinatoires
3. Praticité : fournit un modèle pour la recherche sur les séquences connexes dans l'OEIS

Scénarios d'Application

Cette méthode est particulièrement adaptée à :

• L'analyse de séquences liées à la représentation binaire
• L'étude de séquences automatiques possédant une structure récursive
• L'analyse de densité précise de séquences combinatoires

Références Bibliographiques

L'article cite 14 références importantes couvrant la théorie des séquences automatiques, les séquences du pliage de papier, la séquence de Kolakoski et d'autres domaines connexes, fournissant une base théorique solide pour la recherche.