Runs in Paperfolding Sequences

Cet article démontre que la suite des longueurs de runs et les positions de départ et d'arrivée des runs dans les suites de pliage de papier sont 2-synchronisées, ce qui permet de les calculer via un automate fini et d'obtenir de nouveaux résultats sur leur exposant critique et leur complexité factorielle.

L'essentiel

📄 Le Pliage de Papier et les Séquences Magiques : Une Histoire de Motifs

Imaginez que vous prenez une longue bande de papier. Vous la pliez en deux, puis encore en deux, et encore. À chaque pli, vous créez soit une "colline" (le papier monte), soit une "vallée" (le papier descend). Si vous dépliez tout cela, vous obtenez une séquence infinie de montagnes et de vallées. C'est ce qu'on appelle une séquence de pliage de papier.

Le chercheur Jeffrey Shallit, dans cet article, ne s'intéresse pas seulement au papier lui-même, mais à la façon dont les motifs se répètent dans ce papier.

1. Le Jeu des "Blocs" (Les Runs)

Imaginez que vous regardez votre papier déplié. Vous voyez des blocs de collines consécutives, puis des blocs de vallées, puis encore des collines.

• Un "bloc" (ou run en anglais), c'est une série de collines qui se suivent sans interruption.
• La longueur du bloc, c'est combien de plis il y a dans cette série.

Shallit se demande : "Si je note la longueur de chaque bloc de collines et de vallées, est-ce que cette nouvelle liste de nombres suit une règle simple ?"

2. Le Robot Détective (L'Automate Fini)

En mathématiques, on utilise souvent des "automates" pour décrire des règles. Imaginez un petit robot très bête, mais très rapide. Il ne peut pas faire de calculs complexes, mais il peut lire une suite de nombres et dire : "Oui, c'est correct" ou "Non, c'est faux".

Le résultat principal de l'article est une surprise :

Le robot peut prédire tout !

Même si la séquence de pliage est infinie et semble très compliquée, la liste des longueurs des blocs (1, 2, 3, 1, 2...) est si bien organisée qu'un petit robot simple suffit à la générer. Cela signifie que cette séquence est calculable et prévisible.

De plus, le robot peut aussi dire exactement où commence et où finit chaque bloc. C'est comme si le robot avait une carte au trésor qui lui disait : "Le 5ème bloc de collines commence au pli numéro 12 et finit au numéro 14".

3. Les Règles du Jeu (Ce que le robot a découvert)

En utilisant un logiciel puissant appelé Walnut (qui agit comme un détective mathématique capable de vérifier des millions de cas en une seconde), l'auteur a prouvé plusieurs choses amusantes sur ces longueurs de blocs :

• Pas de trop grands blocs : Les blocs ne sont jamais très longs. Ils font toujours 1, 2 ou 3 plis. Jamais 4, jamais 100. C'est comme si le papier refusait de faire de trop longues suites identiques.
• Pas de répétitions bizarres : Si vous cherchez des motifs qui se chevauchent étrangement (comme "ababa"), vous ne les trouverez pas. Le papier évite ces répétitions trop proches.
• Les carrés parfaits : Parfois, un motif se répète exactement (comme "22" ou "123123"). Le robot a trouvé que seules certaines répétitions très spécifiques sont autorisées. C'est comme si le papier avait une grammaire stricte : il accepte certaines phrases, mais en rejette d'autres.

4. Le Cas Spécial : Le Pliage "Régulier"

Il existe une séquence de pliage très célèbre, où l'on plie toujours dans le même sens (toujours une colline, toujours une colline...). C'est le "pliage régulier".
Les chercheurs précédents avaient déjà étudié ce cas précis. Shallit montre ici que ses découvertes s'appliquent non seulement à ce cas unique, mais à toutes les façons possibles de plier le papier (il y en a une infinité !).

C'est comme si on avait découvert que la loi de la gravité s'applique non seulement à une pomme, mais à toutes les pommes, oranges et poires de l'univers.

5. Le Lien Mystérieux avec les Fractions

La partie la plus magique de l'article relie ces plis de papier à un autre concept mathématique : les fractions continues (une façon d'écrire des nombres décimaux infinis).

L'auteur prouve qu'il existe un lien direct entre la façon dont on plie le papier et la structure des nombres décimaux de certains nombres très étranges (appelés nombres transcendants).

• L'analogie : Imaginez que chaque fois que vous pliez le papier, vous ajoutez une pièce à un puzzle mathématique. La façon dont les blocs de plis s'organisent dicte exactement comment les chiffres d'un nombre infini s'alignent.

En Résumé

Ce papier nous dit que derrière l'apparent chaos d'un papier plié mille fois, il se cache une ordre parfait et simple.

1. Les longueurs des blocs de plis suivent une règle que même un petit robot peut comprendre.
2. Il y a des limites strictes à la façon dont ces blocs peuvent se répéter.
3. Cette structure simple est la clé pour comprendre la nature de certains nombres infinis très complexes.

C'est une belle démonstration que, même dans les processus les plus infinis, la nature (ou les mathématiques) aime la simplicité et les motifs répétitifs.

Résumé technique

Voici un résumé technique détaillé de l'article « Runs in Paperfolding Sequences » de Jeffrey Shallit, rédigé en français.

Titre : Runs in Paperfolding Sequences (Séquences de pliage de papier)

Auteur : Jeffrey Shallit (Université de Waterloo)
Date : 3 janvier 2025

---

1. Problématique et Contexte

Les séquences de pliage de papier (paperfolding sequences) forment une classe non dénombrable de suites infinies sur l'alphabet $\{-1, 1\}$. Elles sont générées par un processus itératif de pliage d'une feuille de papier, où chaque pli crée une crête (+1) ou une vallée (-1). Ces suites sont définies formellement à partir d'une séquence d'instructions de dépliement $f$.

Bien que les propriétés des séquences de pliage elles-mêmes soient bien étudiées, l'article se concentre sur une propriété dérivée : la séquence des longueurs de runs (blocs consécutifs de valeurs identiques) et les positions de début et de fin de ces runs.

• Problème central : Déterminer la nature calculatoire de ces séquences dérivées (longueurs de runs, positions) et généraliser des résultats récents obtenus spécifiquement pour la séquence de pliage régulière (où toutes les instructions sont identiques) à l'ensemble des séquences de pliage.
• Contexte antérieur : Bunder, Bates et Arnold [6] avaient récemment étudié les longueurs de runs de la séquence régulière, prouvant des théorèmes sur leurs propriétés et leur lien avec les fractions continues. Cependant, leur approche était spécifique à ce cas particulier.

2. Méthodologie

L'auteur utilise une approche basée sur la théorie des automates finis et la logique du premier ordre, assistée par un outil de preuve automatique appelé Walnut.

• Automates synchronisés : L'objectif est de prouver que les séquences de longueurs de runs ($R_f$), ainsi que les séquences de positions de début ($S_f$) et de fin ($E_f$), sont 2-synchronisées. Cela signifie qu'il existe un automate fini capable de lire en parallèle l'index $n$ (en base 2) et la valeur $x$ (la position ou la longueur) pour accepter la paire $(n, x)$ si et seulement si $x$ est la valeur correcte pour l'index $n$.
• Utilisation de Walnut : L'auteur formule des assertions en logique du premier ordre décrivant les propriétés des séquences. Walnut vérifie rigoureusement la validité de ces assertions en construisant et en testant des automates.
• Induction et conjecture : La méthode implique de deviner la structure des automates (via des procédures de type Myhill-Nerode) et de les vérifier formellement. Une fois les automates validés, ils servent de base pour prouver des théorèmes sur la complexité, les facteurs (sous-mots) et les propriétés algébriques.

3. Contributions et Résultats Clés

A. Automates pour les positions de runs

• Théorème 3 : Il existe un automate synchronisé de 17 états ($sp$) calculant les positions de début $S_f[n]$ et un automate de 13 états ($ep$) calculant les positions de fin $E_f[n]$ pour toutes les séquences de pliage simultanément.
• Théorème 4 : Une relation précise est établie entre la position de fin du $n$-ième run et l'index $n$ : $E_f[n] + \epsilon_n = 2^n$, où $\epsilon_n \in \{0, 1\}$ dépend d'une séquence de pliage dérivée $g$ liée à $f$.

B. Propriétés des longueurs de runs

• Proposition 5 : Pour toute séquence de pliage (finie ou infinie), les seules longueurs de runs possibles sont 1, 2 ou 3.
• Théorème 7 : La séquence des longueurs de runs est sans chevauchement (overlap-free). Elle ne contient aucun facteur de la forme $axaxa$ (où $a$ est un symbole et $x$ une chaîne).
• Théorème 8 : Les seuls carrés (facteurs de la forme $zz$) possibles dans les longueurs de runs sont : $22$,$123123$et$321321$.
• Théorème 10 : Les seuls palindromes possibles sont : $1, 2, 3, 22, 212, 232, 12321, 32123$.
• Théorème 11 (Complexité sous-mots) : La complexité sous-mots (nombre de facteurs distincts de longueur $n$) de la séquence des longueurs de runs pour une séquence infinie est donnée par la formule linéaire **$4n + 4$** pour$n \ge 6$.

C. Cas de la séquence régulière

L'article spécialise ces résultats pour la séquence de pliage régulière (instructions $1^\omega$).

• L'auteur reconstruit et généralise les résultats de Bunder et al. [6] concernant les suites $g(n)$ (longueurs) et $h(n)$ (positions de fin).
• Théorème 12 : Une propriété de somme conjecturée par Hendriks est prouvée, reliant les valeurs de la séquence de longueurs aux entiers qui ne sont pas des positions de fin de runs augmentées de 1.

D. Lien avec les fractions continues

• Théorème 13 (Résultat majeur) : L'auteur établit un lien fondamental entre les séquences de pliage et les fractions continues d'un nombre non dénombrable d'irrationnels.
  Pour une séquence de signes $\epsilon_i \in \{-1, 1\}$, le nombre réel défini par $\alpha = \frac{1}{2} + \frac{1}{4} + \sum \epsilon_i 2^{-2i}$ possède une fraction continue dont les termes sont directement déterminés par la séquence des longueurs de runs associée aux instructions de pliage.
  Plus précisément, la fraction continue de $\alpha$ est $[0, 1, (2R_{1, \epsilon_2, \dots, \epsilon_n})']$, où le prime indique que le dernier terme est augmenté de 1.
  Cela généralise le résultat de Bunder et al. (qui ne traitait que le cas régulier) à une infinité non dénombrable de nombres.

4. Signification et Impact

• Généralisation : Ce travail démontre que les propriétés observées par Bunder et al. sur la séquence régulière ne sont pas des anomalies, mais des caractéristiques structurelles de toute la classe des séquences de pliage.
• Méthodologique : L'article illustre la puissance de l'approche automatique (Walnut) pour prouver des théorèmes complexes sur les suites combinatoires, en particulier pour des classes non dénombrables de suites où une preuve manuelle directe serait extrêmement difficile.
• Théorie des nombres : La connexion établie entre les séquences de pliage (un objet combinatoire) et les fractions continues (un objet d'analyse et de théorie des nombres) ouvre de nouvelles perspectives pour l'étude de la transcendance et des propriétés arithmétiques de ces nombres (comme les nombres de Kempner).
• Complexité : La détermination exacte de la complexité sous-mots ($4n+4$) fournit une caractérisation fine de la régularité de ces séquences dérivées.

En résumé, cet article transforme une observation spécifique sur une séquence particulière en une théorie unifiée et rigoureuse pour toute une classe de suites, en utilisant la puissance de la logique automatique et des automates finis.