Autour du mot de Kolakoski

et de la combinatoire des mots

Pista negra El 17 abril 2021  - Escrito por  Jules Flin, Irène Marcovici Ver los comentarios

$\pi=3,141 592 653 589 793\ldots$ Voilà un nombre bien familier quand on fait un peu de mathématiques ! Et pourtant, même si on dispose de nombreux outils pour calculer une valeur approchée de $\pi$ aussi précise qu’on le souhaite, les décimales de $\pi$ recèlent encore bien des mystères. Par exemple, on ne sait pas dire si tous les chiffres de $0$ à $9$ apparaissent aussi souvent les uns que les autres, même si tout laisse penser que c’est le cas.

Dans cet article, nous allons nous intéresser à une autre suite de chiffres, la suite de Kolakoski :

\[\mathbf{K}=12211212212211211221211212211\ldots\]

Cette suite de chiffres est encore plus facile à écrire que les décimales de $\pi$, puisqu’on verra qu’on peut déterminer très simplement les chiffres successifs qui la composent, sans faire le moindre calcul. Là aussi, on peut par exemple se demander si les chiffres $1$ et $2$ apparaissent avec la même fréquence dans cette suite. À nouveau, cette question n’a pas trouvé de réponse à l’heure actuelle, malgré les outils développés dans ce champ de recherche, qui relève de ce qu’on appelle la combinatoire des mots.

La combinatoire des mots

Existe-t-il un mot plus long qu’«anticonstitutionnellement» ? Dans les dictionnaires français usuels, non. Mais en mathématiques, on peut s’autoriser des mots arbitrairement grands, voire des mots de longueur infinie. Au croisement entre mathématiques et informatique théorique, l’étude des propriétés de mots (finis ou infinis) s’inscrit dans un domaine qu’on nomme combinatoire des mots.

Mathématiquement, un mot n’est rien de plus qu’une suite de lettres, choisies dans un alphabet. Jusqu’ici, tout va bien. Pour se donner un premier exemple intuitif, le lecteur ou la lectrice pourra évidemment penser à l’alphabet
\[ \{A,B,C,...,X,Y,Z\}. \]
Sur ce dernier, on peut construire le mot «$IMAGES$». Cette définition générale confère à la combinatoire des mots un intérêt dans de nombreux domaines de recherche : en génétique, par exemple, on a plutôt l’habitude de raisonner sur l’alphabet
\[ \{A,C,G,T\}, \]
où chacune des lettres encode respectivement les molécules d’adénine, cytosine, guanine et thymine, entrant dans la composition de l’ADN. Un brin peut alors être vu comme un mot long (mais fini) sur cet alphabet.

La double hélice d’ADN, deux mots sur $\{A,C,G,T\}$.

Du côté de l’informatique, on utilise souvent l’alphabet binaire $\mathcal{A}=\{0,1\}$. Dans le disque dur d’un ordinateur, le mot «sciences» peut, par exemple, être mémorisé sous la forme
\[ 01110011\;01100011\; 01101001\; 01100101\; 01101110\; 01100011\; 01100101\; 01110011, \]
ce qui correspond bien à un mot sur $\mathcal{A}$ (il s’agit ici de ce qu’on appelle un codage ASCII binaire). Que ce soit pour étudier les nucléotides d’un brin d’ADN ou pour encoder un fichier informatique volumineux, le nombre de lettres dans ces mots dépasse largement le milliard, ce qui justifie l’intérêt des mathématiciens et mathématiciennes pour les mots infinis.

Pour construire un mot infini, il suffit de partir d’un mot initial et de lui ajouter des lettres, sans s’arrêter. Par exemple, le mot
\[m_\infty = ABABABABABAB...\]
sur l’alphabet $\{A,B\}$, est la limite de la suite de mots définie par
\[m_1=AB\quad m_2=ABAB\quad ... \quad m_{n+1} = m_{n}AB.\]

L’opération consistant à accoler deux mots, que nous réalisons ici, s’appelle la concaténation. Dans la suite, on la notera, soit par le point central $\cdot$, soit simplement en juxtaposant les deux mots. À partir de maintenant, nous allons nous focaliser sur un mot infini particulier : le mot de Kolakoski.

Le mot de Kolakoski, et comment le générer

Lorsqu’on a un mot défini sur un alphabet quelconque, on peut lui appliquer l’opération de codage par plages (run-length encoding en anglais) qui consiste à découper le mot en blocs constitués de mêmes lettres, et à renvoyer le mot obtenu en concaténant les longueurs de ces blocs. Par exemple, le codage par plages de $112223221333$ est $231213$. On notera $\mathcal{C}(m)$ le codage par plages du mot $m$. Ainsi, notre exemple se reformule
\[\mathcal{C}(112223221333)=231213\]
Remarquons qu’en général, rien n’impose qu’un mot sur l’alphabet $\{1,2,3\}$ soit codé sur ce même alphabet (par exemple, $\mathcal{C}(1111)=4$). Nous avons désormais tous les outils pour comprendre ce qu’est le mot de Kolakoski : c’est un mot infini $\mathbf{K}$ sur l’alphabet $\{1,2\}$ qui (i) est son propre codage par plages (c’est-à-dire que $\mathcal{C}(\mathbf{K})=\mathbf{K}$), et (ii) dont la première lettre est un $1$. Le mot $\mathbf{K}$ peut ainsi être considéré comme un mot infini auto-décrit [1].

Illustration de la relation $\mathcal{C}(\mathbf{K})=\mathbf{K}$.

Pour pouvoir étudier ce mot, nous aimerions le construire, autrement dit nous voulons écrire un programme qui, quel que soit l’entier naturel $n$ que nous nous donnons, renvoie les $n$ premières lettres de $\mathbf{K}$ (c’est-à-dire, le préfixe de $\mathbf{K}$ de longueur $n$).
Une méthode astucieuse pour élaborer une telle procédure consiste à lire l’animation ci-dessus à l’envers ! En effet, si l’on dispose d’un préfixe de $\mathbf{K}$, on peut le voir comme le codage par plage d’un préfixe plus long, et comme on en connaît la première lettre, on peut déterminer sans ambiguïté ce nouveau préfixe. Formalisons cette intuition : étant donné un préfixe $m$ de $\mathbf{K}$ (dont la longueur sera discutée dans un instant), on peut obtenir un préfixe plus long $m'$, en lisant $m$ de gauche à droite : à chaque symbole de $m$ correspond alors une plage de $m'$. Cet argument permet donc de connaître la « structure » de $m'$. Il ne nous reste alors plus qu’à remplir les cases « vides » du mot $m'$, en commençant par un $1$, puis en alternant entre les deux lettres disponibles :

Illustration de la construction d’un préfixe de $\mathbf{K}$ à partir d’un préfixe plus court.

La question est donc de trouver un premier préfixe $m_0$ auquel appliquer ce processus. Puisqu’on sait que $\mathbf{K}$ doit commencer par un $1$, essayons de partir de $m_0=1$. Malheureusement, ce préfixe ne nous donne pas assez d’information, car avec la démarche esquissée ci-dessus, le préfixe suivant obtenu est à nouveau $m_1=1$, et réappliquer cette opération n’y changera strictement rien. Il nous faut donc chercher un autre point de départ, et par conséquent, le prochain candidat est le préfixe de longueur 2 de $\mathbf{K}$. On est donc amené à répondre à une nouvelle question : quelle est la deuxième lettre de $\mathbf{K}$ ? Il n’y a que deux possibilités : soit c’est un $1$, soit c’est un $2$. Commençons par supposer que c’est un $1$ ou, de manière équivalente, que $\mathbf{K}$ commence par $11$. Une contradiction surgit alors, car la première lettre du codage par plages ne pourra être un $1$ (ce qui contredit la définition de $\mathbf{K}$). On en conclut donc que la deuxième lettre de $\mathbf{K}$ est un $2$. Cette fois-ci, en appliquant la procédure décrite ci-dessus un nombre suffisant de fois au mot $m_0=12$, on réussit à atteindre la longueur escomptée. Voyons comment fonctionne cet algorithme sur l’exemple $n=11$, c’est-à-dire pour construire les $11$ premières lettres de $\mathbf{K}$. En appliquant un première fois notre protocole, on obtient le nouveau préfixe
\[m_1=122\]
qui vérifie bien $\mathcal{C}(m_1)=m_0$ et dont la première lettre est $1$. Mais ce préfixe est trop court. On applique la méthode une seconde fois,
\[m_2=12211\]
Ce nouveau mot vérifie à nouveau $\mathcal{C}(m_2)=m_1$ et sa première lettre est bien un $1$. Tant que la longueur des nouveaux préfixes $m_i$ est inférieure à 11, on calcule le préfixe suivant. Aux trois itérations suivantes, l’algorithme nous renvoie
\[m_3=1221121 \quad\quad\quad m_4=1221121221\quad\quad\quad m_5=122112122122112\]
À ce moment-là, le programme s’arrête, car la longueur de $m_5$ est supérieure à 11. Si on veut précisément les onze premières lettres de $\mathbf{K}$, on se contente de tronquer $m_5$. Au passage, cette construction nous assure l’existence et l’unicité d’un mot infini vérifiant les propriétés (i) et (ii).

Dans un mot fini, on peut s’intéresser aux fréquences des lettres, c’est-à-dire à leurs proportions respectives dans le mot. Quand le mot est infini, la fréquence n’est plus une notion évidente. Toutefois, on se ramène naturellement au cas fini en observant la proportion du caractère qui nous intéresse dans des préfixes de plus en plus longs. Par exemple, la fréquence de la lettre $A$ dans le mot $m_\infty$ présenté en introduction existe et vaut $\frac{1}{2}$.

La fréquence d’apparition de $A$ dans $m_\infty$ existe et vaut $\frac{1}{2}$.

Comme on peut le voir sur le graphe des fréquences d’apparition de $A$ dans ses préfixes, la fréquence d’apparition de la lettre $A$ dans $m_\infty$ semble exister et valoir $\frac12$. Un raisonnement faisant intervenir la notion de sous-suite permettrait de la prouver rigoureusement.

Graphe des fréquences d’apparition de $A$ dans les préfixes de longueur $n$ de $m_\infty$, pour $n$ variant de $1$ à $40$.

La fréquence d’apparition d’un caractère pourrait-elle ne pas exister ?

Quand on ne s’intéresse qu’à des mots finis, la fréquence d’un caractère $a$ dans un mot $M$ existe toujours : c’est le rapport entre le nombre de $a$ dans $M$ et la longueur du mot $M$. Dans le cas infini, il s’agit de trouver le nombre $a_n$ d’apparitions de ce caractère parmi les $n$ premières lettres, puis d’étudier le comportement, pour des entiers $n$ de plus en plus grands, de la suite définie par
\[ u_n=\frac{a_n}{n}. \]
En particulier, on cherche à savoir si les termes de la suite se rapprochent de plus en plus d’une certaine valeur, qu’on appelle alors la limite de la suite. Mais cette limite n’a aucune raison d’exister. C’est un fait général qu’il est utile de garder à l’esprit en mathématique : prudence est mère de sûreté lorsque l’on manipule des limites. Illustrons cette mise en garde avec le mot infini suivant, construit sur l’alphabet binaire $\{0,1\}$ :
\[ M=0\;1\;0\;0\;1\;1\;0\;0\;0\;0\;1\;1\;1\;1\;1\;0\;... \]
En observant les longueurs des blocs, on comprend vite la règle qui permet de générer $M$ : c’est une suite de blocs de $0$ et de $1$ dont les longueurs sont des puissances de $2$ croissantes. À première vue, on est tenté d’affirmer qu’il y a « autant de $0$ que de $1$ » dans $M$, et donc que la fréquence de $0$ dans ce mot vaut $\frac{1}{2}$. Mais nous allons voir que cette intuition est un peu trompeuse.

Notons $u_n$ le nombre de $0$ dans les $n$ premières lettres de $M$. Les premières valeurs de $u_n$ sont données par le tableau suivant, et le graphe ci-dessous représente $u_n$ en fonction de $n$, pour $n$ allant de $1$ à $4000$.

$n$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$
$u_n$ $1$ $\displaystyle\frac{1}{2}$ $\displaystyle\frac{2}{3}$ $\displaystyle\frac{3}{4}$ $\displaystyle\frac{3}{5}$ $\displaystyle\frac{1}{2}$ $\displaystyle\frac{4}{7}$ $\displaystyle\frac{5}{8}$ $\displaystyle\frac{2}{3}$ $\displaystyle\frac{7}{10}$ $\displaystyle\frac{7}{11}$ $\displaystyle\frac{7}{12}$

Graphe des fréquences d’apparition de $0$ dans les préfixes de longueur $n$ de $M$, pour $n$ variant de $1$ à $4000$.

Comme le laisse deviner le graphe ci-dessus, on peut montrer que les valeurs de la suite oscillent indéfiniment entre $\frac{1}{2}$ et $\frac{2}{3}$, de sorte qu’il n’y a pas de limite.

Pour la suite $\mathbf{K}$, les simulations numériques laissent penser que les fréquences des lettres $1$ et $2$ existent et sont toutes les deux égales à $1/2$ [2]. Mais on ne sait pas le démontrer... C’est donc pour le moment une conjecture (résultat mathématique attendant d’être démontré ou réfuté). Pour en comprendre l’étendue, revenons sur l’histoire qui se cache derrière cette suite.

La conjecture de Keane

Le mot de Kolakoski apparaît pour la première fois en 1939, dans l’article Exponent trajectories in symbolic dynamics de Rufus Oldenburger, un mathématicien et ingénieur américain [3]. Dans cet article, il s’intéressait aux propriétés générales de l’opération de codage par plages, et montrait en particulier que sur l’alphabet $\{1,2\}$, une seule suite était sa propre image par cette opération.

Des années plus tard, l’artiste (et mathématicien à ses heures perdues) William Kolakoski redécouvrait cette suite, en proposant en 1965 l’énigme suivante aux lecteurs de l’American Mathematical Monthly :

« Décrire une règle simple permettant de construire la suite
\[1\; 2\; 2\; 1\; 1\; 2\; 1\; 2\; 2\; 1\; 2\; 2\; 1\; 1\; 2\; 1\; 1\; 2\; 2\; 1\; 2\; 1\; 1\; 2\; 1\; 2\; 2\; 1\; 1\; 2\; 1\; 1\; 2\; 1\; 2\; 2\; 1\; 2\; 2\; 1\; 1\;...\]
Quel est son $n$-ième terme ? Est-elle périodique ? »

Un mot est périodique si, à la manière d’un papier peint, un motif se répète à intervalle régulier. Cette question a vite été traitée (nous laissons le soin aux lecteurs et lectrices d’Images des Mathématiques d’y répondre aussi !), mais le mot a continué à attirer la curiosité, et le nom de suite de Kolakoski s’est vite imposé, même si suite d’Oldenburger aurait été plus légitime. Kolakoski voyait en ce mot un signe de l’univers : une règle simple le décrit parfaitement, et pourtant, on peut observer de grandes irrégularités dans la distribution des lettres qui le composent. Ce sont ces irrégularités qui rendent si compliquée la preuve (ou la réfutation) de la conjecture suivante, formulée explicitement par Keane en 1991 :

Conjecture de Keane :

La fréquence d’apparition de la lettre $1$ dans le mot infini $\,\mathbf{K}\,$ existe et vaut $\frac{1}{2}$.

À l’aide de la théorie des automates, différents travaux dans la lignée de ceux de Chvátal [4] ont permis de montrer que les oscillations des fréquences restent confinées dans l’intervalle
\[I=[0.49992,0.50008].\]
En substance, l’idée consiste à écrire plusieurs copies de la suite de Kolakoski, sur des lignes consécutives, en alignant les chiffres d’une manière judicieuse. En lisant de gauche à droite l’ensemble de ces lignes, et en étudiant les transitions possibles entre une colonne de chiffres et la suivante, on peut alors obtenir des bornes sur les nombres de $1$ et de $2$, qui sont d’autant plus précises que le nombre de lignes est grand... Mais les calculs deviennent aussi de plus en plus compliqués ! Les valeurs ci-dessus ont été obtenues par Nilsson [5], à l’aide d’idées développées par Rao, en travaillant sur le graphe des transitions correspondant à 34 copies de la suite de Kolakoski.

Ces résultats vont dans le sens de la conjecture de Keane, mais le problème reste ouvert. Dans la suite de cet article, nous allons étudier une variante du mot de Kolakoski, pour laquelle on peut montrer que la fréquence de chaque symbole existe et même calculer leur valeur. Cela nous permettra de présenter différents outils utiles pour résoudre ce type de questions.

Une variante de $\mathbf{K}$

La règle de construction de $\mathbf{K}$ est sans ambiguïté... Il ne devrait donc pas être si compliqué d’étudier comment se comportent les nombres respectifs de $1$ et de $2$ qui le composent. Et pourtant, la conjecture de Keane résiste toujours aux efforts des mathématiciennes et mathématiciens.

Mais comme souvent en mathématiques, quand on ne sait pas résoudre un problème, il peut être intéressant de faire un pas de côté pour s’intéresser à un problème voisin ! Étudions donc un proche cousin de $\mathbf{K}$, qu’on notera $\mathbf{K}'$, dont les premières lettres sont données par
\[\mathbf{K}'=3\;3\;3\; 1 \;1 \;1 \;3 \;3 \;3 \;1 \;3 \;1 \;3 \; 3 \;3 \; 1 \; 1 \; 1 ... \]
Ce mot infini est analogue à $\mathbf{K}$ dans le sens où il est également point fixe de l’opérateur de codage par plages (c’est même l’unique mot écrit avec des $1$ et des $3$ et commençant par un $3$ ayant cette propriété). À nouveau, il est naturel de se demander si la fréquence $f$ de $1$ dans $\mathbf{K}'$ existe, et cette fois, on peut répondre par l’affirmative, et même la calculer $f$.

La première étape consiste à grouper les lettres deux par deux, afin de considérer $\mathbf{K}'$ comme un mot sur l’alphabet $\{33,31,11,13\}$ :
\[\mathbf{K}'=33\;31 \;11 \;33 \;31 \;31 \;33 \;31 \; 11 ...\]
Pour y voir un peu plus clair, on note $A=33$, $B=31$, $C=11$ et $D=13$, de sorte que
\[\mathbf{K}'=A\; B \; C\; A \; B\; B \; A\; B \; C\; ...\]
Il semblerait que la lettre $D$ n’apparaisse pas parmi les premières lettres. C’est en réalité un fait général : $\mathbf{K}'$ est construit sur $\{A,B,C\}$. On jongle à présent avec deux alphabets : $\{1,3\}$ et $\{A,B,C\}$.

On peut prouver que, si dans $\mathbf{K}'$, on remplace tous les $A$ par $ABC$, les $B$ par $AB$ et les $C$ par des $B$, on retombe sur $\mathbf{K}'$ (on pourra déjà s’en convaincre sur le préfixe donné ci-dessus). En combinatoire des mots, cette opération est appelée une substitution, et elle va nous permettre de générer la variante de $\mathbf{K}$. En effet, en notant $\sigma$ cette substitution, et en l’appliquant récursivement au mot $m_0=A$, on obtient une suite de préfixes de plus en plus grands de $\mathbf{K}'$ :

$m_1=\sigma(m_0)=A\;B\;C$

$m_2=\sigma(m_1)=A\;B\;C\;A\;B\;B$

$m_3=\sigma(m_2)=A\;B\;C\;A\;B\;B\;A\;B\;C\;A\;B\;A\;B$

$\dots$

Le problème se ramène maintenant à compter les nombres de $A$, de $B$ et de $C$ dans $m_n$ (qu’on notera respectivement $a_n$, $b_n$ et $c_n$), et ce pour tout entier $n$. Par construction de la suite, on a les relations de récurrence :

\[\left\{\begin{array}{ccccccc} a_{n+1} & = & a_n & + & b_n & & \\ b_{n+1} & = & a_n & + & b_n & + & c_n \\ c_{n+1} & = & a_n \end{array}\right.\]

Comme expliqué dans l’encart suivant, il est possible de « résoudre » ce système pour des grandes valeurs de $n$ (plus précisément, on trouve des équivalents de ces suites, quand $n$ tend vers $+\infty$). La valeur de $f$, donnée par
\[f=\lim_{n\to +\infty}\frac{\text{nombre de }1\text{ dans }m_n}{\text{longueur de }m_n}=\lim_{n\to +\infty}\frac{b_n+2c_n}{2a_n+2b_n+2c_n},\]
peut alors être calculée explicitement.

Calcul de $f$.

On se ramène ici à un problème d’algèbre linéaire, en écrivant les relations entre les $a_n$, $b_n$ et $c_n$, et terme de matrices et de vecteurs : en posant
\[A=\left( \begin{matrix}1&1&0\\1&1&1\\1&0&0\end{matrix}\right)\text{ et }X_n=\left(\begin{array}{c} a_n \\ b_n \\ c_n \end{array}\right)\]

pour tout entier naturel $n$, on obtient l’équation de récurrence $X_{n+1}=AX_n$ :

Au-delà de la concision qu’apporte cette écriture, on peut maintenant utiliser des outils empruntés à l’algèbre linéaire. Remarquons d’abord qu’en appliquant successivement la formule précédente, on trouve que, pour tout $n$,
\[X_n=A^nX_0\text{ où }X_0=\left(\begin{array}{c} 1 \\ 0 \\ 0 \end{array}\right)\]

En calculant explicitement $A^n$ pour tout entier $n$, on pourra donc en déduire une formule pour $X_n$. Mais, en général, calculer les puissances d’une matrice n’est pas une mince affaire. Il existe toutefois des matrices dont on sait calculer les puissances sans difficultés : les matrices diagonales (dont les coefficients qui ne sont pas sur la diagonale sont tous nuls). Essayons de nous en convaincre sur un exemple simple
\[\left(\begin{array}{ccc} 3 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 2 \end{array}\right)^2=\left(\begin{array}{ccc} 3 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 2 \end{array}\right)\left(\begin{array}{ccc} 3 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 2 \end{array}\right)=\left(\begin{array}{ccc} 3^2 & 0 & 0 \\ 0 & (-1)^2 & 0 \\ 0 & 0 & 2^2 \end{array}\right)\]
Pour calculer la puissance $n$-ème d’une matrice diagonale $D$, il suffit donc d’élever chacun des coefficients à la puissance $n$. Dans certains cas, on peut se ramener à cette situation, en utilisant ce qu’on appelle une méthode de diagonalisation, permettant de trouver deux matrices $P$ et $P^{-1}$ inverses l’une de l’autre, et une matrice diagonale $D$, telles que
\[A=PDP^{-1}.\]

Notons que pour des raisons techniques, $P, P^{-1}$ et $D$ sont des matrices à coefficients dans l’ensemble $\mathbb{C}$ des nombres complexes. Cette nouvelle relation nous permet de calculer plus efficacement les puissances de $A$. En effet, nous laissons le soin aux lecteurs et lectrices de prouver que, pour tout entier $n$,
\[A^n=PD^nP^{-1}\]
Ici, la matrice $A$ possède une propriété particulière, qui va nous aider à poursuivre notre raisonnement : en notant
\[D=\left(\begin{array}{ccc} x & 0 & 0 \\ 0 & y & 0 \\ 0 & 0 & z \end{array}\right)\]
la matrice diagonale obtenue dans la décomposition ci-dessus, les calculs montrent que $x$ est un nombre réel strictement supérieur à $1$, et qu’en plaçant $y$ et $z$ sur le plan complexe, ils se retrouvent à l’intérieur du cercle de centre $0$ et de rayon $1$. Ainsi, en élevant $D$ à la puissance $n$, le coefficient $x^n$ va continuer de croître à mesure que $n$ grandit, et les coefficients $y^n$ et $z^n$ vont se rapprocher très rapidement de 0, si bien qu’on pourra les négliger dans nos calculs :

$x^n$ reste sur la droite des réels, en devenant très grand avec $n$, tandis que $y^n$ et $z^n$ se rapprochent de l’origine.

Or, pour tout entier $n$, $a_n$ s’exprime sous la forme
\[a_n=\alpha x+\beta y +\gamma z\]
où les lettres grecques $\alpha$ (alpha), $\beta$ (beta) et $\gamma$ (gamma) sont des constantes (qui ne dépendent pas de $n$), qu’on peut calculer explicitement en utilisant les valeurs de $a_n$ pour $n=0, 1, 2$. Donc finalement, comme $y$ et $z$ seront négligeables devant $x$, pour $n$ suffisamment grand, $a_n$ sera très proche de $\alpha x^n$ (ici $\alpha\approx 0,4607$). On procède de la même manière pour $b_n$ et $c_n$ : quand $n$ tend vers $+\infty$, $b_n$ sera bien approximé par $(0,5554\ldots)\cdot x^n$ et $c_n$ par $(0,2088\ldots)\cdot x^n$. D’où :

$f=\displaystyle\lim_{n\to +\infty}\displaystyle\frac{b_n+2c_n}{2a_n+2b_n+2c_n}$
$\;\;\,\,=\displaystyle\lim_{n\to +\infty}\displaystyle\frac{(0,5554\ldots)\cdot x^n+2\cdot (0,2088\ldots)\cdot x^n}{2\cdot (0,4607\ldots) \cdot x^n+2\cdot (0,5554\ldots)\cdot x^n +2\cdot (0,2088\ldots)\cdot x^n}$
$\;\;\,\,=\displaystyle\frac{(0,5554\ldots)+2\cdot (0,2088\ldots)}{2\cdot (0,4607\ldots)+2\cdot (0,5554\ldots)+2\cdot (0,2088\ldots)}\approx 0,3972$

En travaillant un peu plus, on peut également montrer que $f$ est l’unique racine réelle du polynôme
\[P(x)=4x^3-14x^2+15x-4.\]
Une valeur approchée de $f$ est donnée par $f\approx 0,3972,$ et on obtient au passage la fréquence $f'$ de $3$ dans $\mathbf{K}'$ :
\[f'=1-f\approx 0,6028.\]

Quid de la conjecture de Keane

Qu’avons-nous appris ? Nous avons calculé les fréquences pour la suite $\mathbf{K}'$, dont la définition semble bien proche de celle de $\mathbf{K}$. Cependant, les outils d’algèbre linéaire utilisés pour $\mathbf{K}'$ ne suffisent pas à traiter la suite $\mathbf{K}$. Des avancées récentes permettent de donner un encadrement des fréquences pour $\mathbf{K}$, avec une précision de moins d’un millième, comme nous l’avons évoqué plus haut. Mais cela ne répond pas complètement à la conjecture de Keane, qui reste donc ouverte pour le moment. Elle a peut-être encore de beaux jours devant elle...

Post-scriptum :

Les auteurs remercient Jérôme Buzzi et Laurent Bartholdi pour leurs encouragements et leurs conseils dans la rédaction de cet article. Ils remercient également les relecteurs d’Images des mathématiques dont les noms ou pseudonymes sont les suivants : Pierre Lescanne, Laurent Théry, Cidrolin, Olivier, pour l’attention qu’ils ont portée à cet article et pour leurs suggestions d’amélioration.

Article édité par Laurent Bartholdi

Notas

[1La suite de Kolakoski figure sur l’OEIS. Sloane a répertorié quelques autres exemples de suites auto-décrites, comme la suite de Golomb.

[2Cette observation peut être rapprochée du fait que la longueur du préfixe renvoyé par l’algorithme au bout de $n$ étapes semble être de l’ordre de $(3/2)^n$.

[3La référence plus précise de l’article est la suivante : Oldenburger R. (1939). Exponent Trajectories in Symbolic Dynamics. Transactions of the American Mathematical Society, 46(3), 453. doi.org/10.1090/S0002-9947-1939-0000352-9.

[5Nilsson J. (2014). Letter frequencies in the Kolakoski sequence. Acta Physica Polonica A, 126(2), p. 549-552. doi.org/10.12693/APhysPolA.126.549.

Comparte este artículo

Para citar este artículo:

Jules Flin, Irène Marcovici — «Autour du mot de Kolakoski» — Images des Mathématiques, CNRS, 2021

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.