(Page en perpétuelle construction...)

Soit κ le mot de Kolakoski (qui a été défini antérieurement par R. Oldenburger[1]), i.e. la séquence A000002 de l’OEIS.

1 Quelques résultats

Soit T le transducteur suivant.

κ est un point fixe de T. L’autre point fixe est κ′, avec κ = 1κ′. Les transducteurs peuvent aisément se composer. Voici par exemple T² et T³.

(T⁴ est ici.)

κ est également un point fixe de Tⁿ pour tout n > 0. Plus généralement, tout mot infini lisse est l’image d’un mot infini lisse par Tⁿ. On peut noter que Tⁿ, pour n > 1, a d’autres points fixes que κ et κ′.

Conjectures

On peut émettre beaucoup de conjectures sur les transducteurs Tⁿ.

Un chemin (fini ou non) dans un transducteur est valide s’il est induit par un mot lisse (fini ou non).

Dans le cas du mot de Kolakoski sur l’alphabet {a,b}, avec a et b impair, ces conjectures sont trivialement fausses: Tⁿ est une union de 2^n-1 composante connexe de taille 2. Ceci peut expliquer pourquoi l’analyse est plus simple dans ces cas. Quand a et b sont pair, tous les cycles (et plus généralement, tous les arcs) dans T² sont de poids 1∕2, ce qui donne directement la limite de 1∕2 pour les fréquences de a et b.

1.1 Bornes supérieures sur la densité de 1/2 par Tⁿ

Tout mot infini lisse (dont κ) est un chemin infini dans Tⁿ. Le “cycles moyen maximum” (mean cycle) de Tⁿ est donc d’une borne supérieure pour la densité du nombre de 1 dans κ, et dans tout mot lisse infini. Le tableau suivant donne les cycles moyens maximums dans Tⁿ. (On peut noter qu’il y a une involution η entre les sommets de Tⁿ telle que (x,w,y) ∈ E ssi (η(x),w,η(y)) ∈ E pour tout x,y ∈ V (Tⁿ) et w ∈{1,2}^*. Ceci explique que la borne obtenue est une borne supérieure pour la densité de 1 et de 2.)

La différence entre le cycle moyen maximum et 1∕2 semble être en O((2∕3)^n∕2) = O(0.816497ⁿ). Voici les rapports entre les cycles moyen maximum de deux transducteurs successifs.

Il existe donc une constante c telle que pour tout i > c,

Rapport avec les graphes de Chvátal

Afficher/cacher

Multiplication par des codes

Soit W un code sur {1,2} , et T_W le transducteur à un état, et qui associe w à w pour tout w ∈ W. On note T * W le transducteur T * T_w.

Soit T un transducteur. Un mot est un mot de retour vers l’état v si le chemin partant de v et induit par w se termine sur v. Un mot est un mot de retour pour T s’il est un mot de retour pour tous les etats de T. L’ensemble des mots de retour lisses est naturelment un code préfixe maximal pour les mots lisses.

Le code suivant est l’ensemble des mots de retour dans T : W₁ = {11,12,21,22}. T *W₁ possède donc 2 composantes connexes d’un etat chacune, et pour tout n > 0, (Tⁿ) * W₁ a deux composantes connexes de taile 2^n-1.

Pour T², on a le code suivant (de taille 10) : W₂ = {11, 121121, 12112212, 1212, 1221, 2112, 2121, 21221121, 212212, 22}. Pour T³, on a le code suivant (de taille 44) : W₃ = {112112, 1121221121, 11212212, 11221211211221, 11221211212211, 1122121121221221, 11221221, 121121, 1211221211, 121122122112, 12112212212112112212, 12112212212112122112, 1211221221211221, 1212, 12211211212211, 12211211212212112212, 1221121121221221, 122112112212, 12211212212112112212, 1221121221211221, 1221121221221121, 12212112, 12212211, 1221221211211221, 1221221211212211, 12212212112212, 211211, 21121221, 2112212112112212, 2112212112122112, 21122121121221221121, 211221221121, 2112212212, 2121, 2122112112122112, 21221121121221211221, 21221121121221221121, 212211211221, 21221121221211211221, 212211212212112212, 21221121221221, 21221211, 2122122112, 22}. Pour tout n > 0, (Tⁿ) * W₂ a quatre composantes connexes de taile 2^n-2, et (Tⁿ) * W₃ a huit composantes connexes de taile 2^n-3.

Les avantages de multiplier par un code sont les suivants :

• Le transducteur a autant de sommets que le transducteur initial, et peuvent être composés de plusieurs composantes connexes (si on choisi un bon code). L’algorithme pour les cycles moyens peut donc se faire en plusieurs fois.
• Vu que certaines portion de chemins deviennent interdits, car ils ne sont pas lisses, le cycle moyen maximum peut (des fois) être plus petit.

Le désavantage c’est que le nombre d’arcs partant d’un sommet est la taille du code. L’espace utilisé pour stocker le graphe devient beaucoup plus important, ou alors le temps pour calculer un arc explose, si on calcule les arcs à la volée.

Voici par exemple les cycles moyens maximums de Tⁿ * W₃ :

Dans le cas particulier du mot de Kolakoski, on peut obtenir d’encore meilleurs bornes; sachant que le mot est un chemin infini partant de l’état 1…1, il suffit de regarder uniquement la composante connexe de Tⁿ * W₃ contenant cet état.

Afficher/cacher

1.2 Codes bifixes

Soit C^∞ l’ensemble des mots lisses finis. Soit (C^∞) l’ensemble des mots lisses bi-infinis.

Les codes préfixes, suffixes, bifixes (maximaux ou non) de C^∞ sont définis naturellement. (Ensembles finis ou non de mots finis dans C^∞).

Soit f : C^∞→ ℝ⁺ la mesure de Dekking. On voit directement que :

Soit X un code. Soit d(X) = ∑ _w∈X|w|f(w).

(note: les mots de retour de taille 0 modk sont aussi des codes bifixes, mais on a plus forcement un degré 2^x.)

Les codes de retour de T, T² et T³ sont respectivement W₁, W₂ et W₃, et sont respectivement de degrés 2, 4 et 8. Les codes de retour des état de T (resp. T², T³) sont tous les mêmes, et tous égaux à W₁ (resp. W₂, W₃). Ceci n’est plus vrai pour T⁴. Le code de retour de T⁴ est de degré 32, et est de taille 2810, tandis qu’il y a deux codes de retours différents pour les états de T⁴, tous deux de degré 16 et de taille 228. Le code de retour de T⁵ est de degré 256, et est de taille 720074. Il y a quatre codes de retours différents pour les états de T⁵, tous de degré 32, et de taille 1678 ou 1768.

Le code de retour vers un état v1 (resp. v2) dans Tⁿ⁺¹ est construit depuis le code de retour vers v dans Tⁿ avec l’opération suivante.

Definition 1. Let W be a code and x ∈{1,2}. Then:

Idée de preuve (si on construit W′à partir de W): on regarde W′ comme des mots sur l’alphabet W. Pour w ∈ W, soit g(w) = ∑ _w′∈W′|w′|_wf(w′). Il faut montrer que g(w) = 2 pour tout w ∈ W (ce qui montre la conjecture). Le degré du code bifixe W′ sur l’alphabet W est de 2, car il existe deux parses possibles (car il y a 2 états possibles). Mais l’égalité average length = nombre de parses n’est pas prouvé, car on a pas la récurrence pour pouvoir appliqué les résultats connus.

(C’est peut être plus facile à voir avec les mots de retour dans les transducteurs qu’avec la définition directe.)

Si on montre qu’un code bifixe de degré fini est fini, on montre que tout chemin infini valide dans un Tⁿ est uniformément récurent. (Mais je ne n’ai pas d’intuition sur le fait que tout code de degré fini est fini.)

Si on montre que tous les mots de retours sont finis, on montre la récurrence du mot de Kolakosi. Soit v un facteur f apparaissant dans κ. Soit n tel que v apparaisse dans u_n. κ sera induit par une suite infinie de chemins de retour dans Tⁿ. Donc v apparaîtra (au moins) à chaque re-passage à o.

À vérifier: soit w un mot de retour dans T^k+1. Alors F^k(w) répond à la question précédente. Montrer que le code bifixe de retour d’un Tⁿ est de degré 2ⁿ répond par l’affirmative à la question précédente pour tout k.

1.3 Nombre de 1 dans les 10^x premières lettres de κ

L’utilisation de Tⁿ peut servir à avancer rapidement dans la génération du mot.

Voici le nombre de 1 dans les 10^x premières lettres de κ (séquence A195206 de l’OEIS).

Plus de valeurs ici. Si vous voulez encore plus de valeurs, essayez le Kolakotor (si l’ordinateur maître est disponible).

1.4 Représentation de la différence

Les graphes des différences jusqu’à 10^x, 3 ≤ x ≤ 18 ici.

Sur une échelle logarithmique

1.5 Nombre maximum de 1 dans un mot lisse de taille n

Un mot w est lisse (smooth) si pour tout k ∈ ℕ, δ^k(w) est dérivable. Soit C^∞ l’ensemble des mots lisses.

Soit f(n) = max_{w∈C^∞:|w|=n}|w|₁.

A. Carpi conjecture[2] que f(n) - n∕2 = O().

Voici les valeurs de 2 ⋅ f(n) - n pour 0 < n ≤ 66704 : 66704.txt.

References