On a perturbed Hofstadter $Q$-recursion

Cet article démontre que la variante perturbée par la parité $\widetilde{Q}$ de la suite de Hofstadter est bien définie pour tout $n$ et présente une auto-similarité dyadique exacte, permettant d'établir des bornes asymptotiques précises sur son comportement grâce à l'utilisation des nombres de Catalan.

L'essentiel

Le titre : Quand le chaos devient une danse ordonnée

Imaginez que vous essayez de prédire la position d'une balle qui rebondit sur un sol très irrégulier. C'est un peu comme la suite de Hofstadter Q, une célèbre énigme mathématique vieille de plusieurs décennies. Dans cette suite, chaque nombre dépend de deux nombres précédents, mais pas n'importe lesquels : il faut regarder en arrière d'une quantité qui dépend elle-même des nombres que l'on vient de calculer. C'est un système en boucle fermée, un peu comme un écho qui s'auto-alimente.

Résultat ? C'est le chaos total. Personne ne sait si cette suite fonctionne pour tous les nombres, ni si elle suit une règle simple. C'est comme essayer de deviner la météo dans un ouragan : imprévisible et effrayant.

L'ingrédient secret : Le "perturbateur"

En 2026, un chercheur nommé Mantovanelli a eu une idée géniale. Il a pris cette recette chaotique et y a ajouté un petit ingrédient bizarre : $(-1)^n$.
En termes simples, il a ajouté un petit "tic" qui alterne entre +1 et -1 à chaque étape. C'est comme si, au lieu de laisser la balle rebondir au hasard, on lui donnait un petit coup de pied rythmé à chaque saut.

Le miracle : Ce petit coup de pied a transformé le chaos en une danse parfaitement ordonnée. Au lieu d'un ouragan, on obtient une structure qui se répète elle-même à l'infini, comme un flocon de neige ou un fractal. C'est ce que l'auteur appelle l'auto-similarité dyadique.

La découverte principale : Une règle cachée

L'auteur, Benoît Cloitre, a prouvé deux choses fondamentales sur cette nouvelle suite (appelée $\tilde{Q}$) :

1. Elle fonctionne toujours : Contrairement à la suite originale qui pourrait "casser" un jour, celle-ci est bien définie pour tous les nombres.
2. Elle suit une ligne droite (presque) : Si vous tracez le rapport entre le nombre calculé et son rang ($n$), vous voyez que cela oscille autour de 0,5 (la moitié).
   • Imaginez une corde qui oscille de gauche à droite autour d'une ligne centrale.
   • L'auteur a prouvé que plus on avance dans le temps (plus $n$ est grand), plus les oscillations deviennent petites.
   • La vitesse à laquelle elles se calmement est très précise : elles diminuent comme $1/\sqrt{\log n}$. C'est une façon mathématique de dire : "Ça se calme, mais très lentement, comme une tasse de café qui refroidit."

L'analogie des "Arches" et des "Catalans"

Pour comprendre comment ça marche, l'auteur utilise une image magnifique : les arches.

• Les vagues : La suite ne monte pas tout droit. Elle forme des vagues successives, des "arches" qui montent et descendent.
• Le rythme des vagues : La taille et la forme de ces arches ne sont pas aléatoires. Elles suivent une règle très stricte liée aux nombres de Catalan.
  • Qui sont les nombres de Catalan ? Imaginez que vous voulez compter de combien de façons différentes vous pouvez faire des parenthèses équilibrées (()) ou des chemins dans une grille sans jamais descendre en dessous de la ligne de départ. Ces nombres apparaissent partout en mathématiques discrètes. Ici, ils dictent exactement la hauteur des vagues de notre suite.
• La machine à tisser : L'auteur a découvert que cette suite fonctionne comme une machine à tisser qui prend deux bandes de données passées et les entrelace (les mélange) pour créer le futur. C'est comme si le passé se "repliait" sur lui-même pour créer un motif symétrique parfait.

Pourquoi c'est important ?

Ce papier est une fenêtre ouverte sur le mystère de la suite originale de Hofstadter.

• La suite originale ($Q$) est comme un labyrinthe sombre où l'on ne voit rien.
• La suite perturbée ($\tilde{Q}$) est comme si l'on avait allumé une lumière dans ce labyrinthe.

Les expériences numériques suggèrent que la différence entre la suite chaotique originale et cette version ordonnée est très petite. Si l'on arrive à prouver que cette différence reste contrôlée, cela pourrait enfin nous permettre de résoudre le mystère de la suite originale : savoir si elle fonctionne pour toujours et si elle tend vers 0,5.

En résumé

Ce papier raconte l'histoire d'un chercheur qui a pris un problème mathématique insoluble (le chaos de Hofstadter), y a ajouté un petit rythme régulier (le perturbateur), et a découvert que ce chaos se transformait en une structure fractale magnifique, régie par des nombres anciens (Catalan) et une symétrie parfaite.

C'est comme si l'on découvrait que derrière le bruit d'une foule en panique, il y a en réalité une chorégraphie de ballet parfaitement synchronisée, attendue depuis des décennies.

Résumé technique

1. Problématique et Contexte

L'article s'intéresse à la séquence de Hofstadter Q, définie par la récurrence imbriquée chaotique :
$$Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), \quad Q(1)=Q(2)=1$$
Malgré des décennies d'études, il reste une question ouverte fondamentale : la suite $Q(n)$ est-elle définie pour tout $n$ ? De plus, la convergence du rapport $Q(n)/n$ vers $1/2$ n'est pas prouvée rigoureusement, bien que les données numériques suggèrent un comportement chaotique autour de cette valeur.

En 2026, Mantovanelli a introduit une version perturbée par la parité, notée $\tilde{Q}$ (ou $eQ$ dans le texte), en ajoutant un terme $(-1)^n$ à la récurrence :
$$\tilde{Q}(n) = \tilde{Q}(n - \tilde{Q}(n-1)) + \tilde{Q}(n - \tilde{Q}(n-2)) + (-1)^n, \quad \tilde{Q}(1)=\tilde{Q}(2)=1$$
Contrairement à la version originale, cette perturbation semble régulariser le comportement, remplaçant le chaos par une auto-similarité dyadique exacte. L'objectif de l'article est de prouver rigoureusement que cette suite est bien définie pour tout $n$, d'établir sa convergence vers $n/2$, et de déterminer le taux de convergence et la constante d'enveloppe exacte.

2. Méthodologie

L'auteur développe une analyse structurelle profonde basée sur la décomposition de la suite en sous-suites et l'utilisation d'un transducteur d'entrelacement (interleave transducer).

A. Décomposition Parité et Modes

L'auteur pose $R(n) = (\tilde{Q}(n)+1)/2$ (toutes les valeurs de $\tilde{Q}$ étant impaires). En séparant les indices pairs et impairs, il définit deux sous-suites $A(m)$ et $B(m)$, et deux modes :

• $\sigma(m) = A(m) + B(m) - m$ (mode symétrique)
• $\delta(m) = B(m) - A(m)$ (mode différence)

La convergence de $\tilde{Q}(n)/n$ vers $1/2$ équivaut à montrer que $\sigma(m) = o(m)$ et $\delta(m) = o(m)$.

B. Décomposition en "Arches"

La suite $\delta(m)$ oscille entre valeurs positives et négatives. Ses zéros définissent une décomposition naturelle en arches alternées (positives et négatives).

• Les arches positives correspondent à des excursions où $\delta \ge 0$.
• L'auteur identifie une structure fractale : chaque arche de niveau $r$ est construite à partir des données de l'arche précédente via des opérations d'entrelacement.

C. Le Transducteur d'Entrelacement

C'est la découverte structurelle clé. Les récurrences couplées pour $A$ et $B$ peuvent être réécrites comme une machine déterministe lisant deux bandes binaires alternativement.

• On définit des mots d'étape ($P_r$ pour les arches positives, $N_r$ pour les négatives) qui codent les différences $\Delta A$ et $\Delta B$.
• Le mot d'étape d'un niveau $r+1$ est obtenu par une opération d'entrelacement (Interleave) des mots du niveau précédent.
• Cette opération préserve des propriétés combinatoires cruciales : équilibrage (nombre égal de 0 et de 1), anti-palindromie, et transport des longueurs de runs.

D. Deux Voies d'Analyse

L'article utilise deux approches complémentaires pour prouver les résultats :

1. Voie B (Fréquences) - Inconditionnelle : Analyse de la distribution des multiplicités de visites des valeurs par $A$ et $B$ sur des blocs dyadiques. Cela conduit à une loi de fréquence géométrique gouvernée par des coefficients binomiaux centraux.
2. Voie A (Amplitudes) - Conditionnelle : Analyse directe des amplitudes des arches ($V^+(r)$). Cette voie repose sur deux conjectures vérifiées numériquement (Observations 9.4 et 9.10) concernant l'alignement des têtes de lecture du transducteur au moment du maximum global.

3. Résultats Principaux

A. Bien-définition et Convergence Inconditionnelle

Le théorème principal (Théorème 1.1(a)) établit que :

1. La suite $\tilde{Q}(n)$ est bien définie pour tout $n \ge 1$.
2. Elle satisfait $1 \le \tilde{Q}(n) \le n$.
3. La convergence vers $1/2$ est prouvée avec un taux de convergence :
   $$\left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| = O\left( \frac{1}{\sqrt{\log n}} \right)$$
   Ce résultat est inconditionnel et repose sur la Voie B (analyse des fréquences). La preuve utilise une inversion monotone de la fonction de comptage des visites, où l'asymétrie entre les visites de $A$ et $B$ est contrôlée par les coefficients binomiaux centraux $\binom{2k+2}{k+1}$.

B. Constante d'Enveloppe Exacte (Conditionnelle)

Sous l'hypothèse de deux propriétés combinatoires vérifiées pour les premiers niveaux (Observations 9.4 et 9.10), l'auteur affine le résultat asymptotique (Théorème 1.1(b)) :
$$\limsup_{n \to \infty} \left| \frac{\tilde{Q}(n)}{n} - \frac{1}{2} \right| \sqrt{\log_2 n} = \frac{1}{3\sqrt{2\pi}}$$
Ce résultat découle de l'analyse des amplitudes des arches. Les incréments d'amplitude $W_r$ suivent une loi gouvernée par les nombres de Catalan : $W_r = \binom{2r+1}{r}$. L'amplitude totale croît comme $V^+(r) \sim \frac{8}{3\sqrt{\pi}} \frac{4^r}{\sqrt{r}}$.

C. Structure Combinatoire

L'analyse révèle que la séquence est gouvernée par une dualité Catalan :

• Le côté fréquence utilise des coefficients binomiaux centraux (liés à un arbre binaire, similaire à la suite de Conway-Mallows).
• Le côté amplitude utilise des coefficients liés aux nombres de Catalan (liés à une forêt de méta-Fibonacci).
• Ces deux aspects sont unifiés par une équation de noyau unique : $1 - z + xz^2 = 0$.

4. Signification et Perspectives

• Proxy pour Hofstadter Q : Les expériences numériques suggèrent que la différence entre la suite originale chaotique $Q(n)$ et la suite perturbée $\tilde{Q}(n)$ est bornée par $O(n/\sqrt{\log n})$. Si cela est prouvé, cela impliquerait que $Q(n)$ est bien définie pour tout $n$ et converge vers $n/2$, résolvant ainsi un problème ouvert majeur.
• Régularisation par Perturbation : L'article démontre qu'une simple perturbation de parité peut transformer un système récursif chaotique en un système auto-similaire exact, offrant un modèle tractable pour étudier les propriétés des récurrences imbriquées.
• Nouveaux Liens : L'article établit des connexions profondes entre les suites de Hofstadter, les nombres de Catalan, les transducteurs d'entrelacement et la combinatoire analytique (méthode du noyau).

En résumé, Benoît Cloitre fournit une preuve rigoureuse de la régularité d'une variante de la suite de Hofstadter, en exploitant une structure fractale cachée révélée par la perturbation, et propose des conjectures fortes pour la suite originale.