Séminaire Lotharingien de Combinatoire 47 (2002), Article B47e

Ensembles inévitables

Guo-Niu Han^{1} et Dominique Perrin^{2}

1IRMA, CNRS et Université Louis-Pasteur, 7, rue René-Descartes F-67084 Strasbourg

2Institut Gaspard Monge, Université de Marne-la-Vallée, 5, boulevard Descartes, Champs sur Marne, F-77454 Marne la Vallee

Résumé. Un ensemble de mots X sur un alphabet A est dit inévitable si tout mot infini sur A a un facteur dans X. Nous discutons ici sans la résoudre une conjecture^{1} suivant laquelle, pour chaque entier n, il existe un système de représentants des classes circulaires de mots de longueur n qui est aussi un ensemble inévitable. Dans cette Note, nous étudions des problèmes directement liés à cette conjecture : les classes permutativement circulaires, la conjecture dans les cas des petits n et l’extension aux systèmes de type fini.

1 Introduction

Un ensemble de mots X sur un alphabet A est dit inévitable si tout mot infini sur A a un facteur dans X. Par exemple, {aa, b} est un ensemble inévitable sur deux lettres, mais {aa, bb} ne l’est pas. On pourra se reporter à [5] (Chapitre 1, Section 6) pour des références sur cette notion et sur les sources antérieures.

Les ensembles inévitables formés de mots de même longueur ont été étudiés par M.-P. Schützengberger dans [6], qui a étudié en particulier le cardinal minimal des ensembles inévitables de mots de longueur n à k lettres.

1Cette conjecture vient d’être résolue par Georges Hansel et Jean-Marc Champarnaud.

On note s_{n}(k) (resp. q_{n}(k)) le nombre de classes de conjugués de mots (resp. de mots primitifs) de longueur n sur un alphabet à k lettres. On a s_{n}(k) = ∑_{d|n} q_{d}(k). De plus, comme cela est bien connu [5]

q_{n}(k) = \frac{1}{n} ∑_{d|n} μ(n/d)k^{d}

où μ désigne la fonction de Möbius, et aussi

s_{n}(k) = \frac{1}{n} ∑_{d|n} φ(n/d)k^{d}

où φ désigne la fonction d’Euler. Ceci permet un calcul direct des s_{n}. Pour k = 2, les valeurs de q_{n}(2) et s_{n}(2) pour n ≤ 13 sont données ci-dessous.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ q_{n}(2) & 2 & 1 & 2 & 3 & 6 & 9 & 18 & 30 & 56 & 99 & 186 & 335 & 630 \\ s_{n}(2) & 2 & 3 & 4 & 6 & 8 & 14 & 20 & 36 & 60 & 108 & 188 & 352 & 632 \end{matrix}

Pour k = 3, on obtient

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ q_{n}(3) & 3 & 3 & 8 & 18 & 48 & 116 & 312 & 810 & 2184 & 5880 & 16104 \\ s_{n}(3) & 3 & 6 & 11 & 24 & 51 & 130 & 315 & 834 & 2195 & 5934 & 16107 \end{matrix}

A partir d’un mot de longueur n, on peut fabriquer un mot infini dont tous les facteurs de longueur n sont dans une même classe circulaire. On a ainsi :

Proposition 1 Un ensemble inévitable de mots de longueur n sur un alphabet à k lettres rencontre chaque classe de conjugués de mots de longueur n. Par conséquent, on a α(k, n) ≥ s_{n}(k).

Le résultat suivant a été démontré par Schützenberger [6].

Proposition 2

lim_{n→∞} α(k, n)/s_{n}(k) = 1.

Nous allons montrer, dans la section 3, qu’il existe un ensemble inévitable de mots binaires de longueur n avec exactement s_{n}(2) éléments pour n ≤ 9. Ceci plaide en faveur de la conjecture suivante.

Conjecture 1 Pour tout entier n ≥ 1, il existe un ensemble inévitable de s_{n}(k) mots de longueur n sur k lettres, i.e., α(k, n) = s_{n}(k).

Cette Note est organisée comme suit : Dans la section 2, nous introduissons la notion de classes permutativement circulaires, qui généralise la notion de classe circulaire classique. Nous indiquons le lien avec les ensembles inévitables. Des formules pour calculer les nombres de classes permutativement circulaires sont également fournies. Dans la section 3, nous présentons les différents cas particulier pour vérifier la conjecture 1. Enfin, nous étudions le problème des ensembles inévitables pour les systèmes de type fini.

2 Classes permutativement circulaires

Soient A un alphabet fini et σ une permutation sur A, qui envoie la lettre a en a′ = σ(a). Pour tout mot w = x_{1}x_{2}x_{3} ⋯ x_{n−1}x_{n} de longueur n, on pose w′ = x_{2}x_{3}x_{4} ⋯ x_{n}x′_{1}. On dit que w′ est le permutativement circulaire de w. Cet opérateur permutativement circulaire définit bien une relation d’équivalence, associée à σ, sur l’ensemble des mots de A de longueur n. On peut donc former les classes d’équivalence permutativement circulaires.

En particulier, dans le cas des mots binaires, il existe deux permutations d’ordre 2, ainsi deux classes permutativement circulaires. Celle associée à la permutation identique (a)(b) est simplement la classe circulaire classique. La seconde, qui est associée à la permutation (ab), est appelée aussi la classe anti-circulaire.

Par exemple, pour n = 5, il y a 8 classes circulaires classiques

\begin{matrix}0 & aaaaa \\ 1 & aaaab, aaaba, aabaa, abaaa, baaaa \\ 2 & aaabb, aabba, abbaa, baaab, bbaaa \\ 3 & aabab, abaab, ababa, baaba, babaa \\ 4 & aabbb, abbba, baabb, bbaab, bbbaa \\ 5 & ababb, abbab, babab, babba, bbaba \\ 6 & abbbb, babbb, bbabb, bbbab, bbbba \\ 7 & bbbbb \end{matrix}

et 4 classes anti-circulaire :

\begin{matrix}anti0 & aaaaa, aaaab, aaabb, aabbb, abbbb, bbbbb, baaaa, bbaaa, bbbaa, bbbba \\ anti1 & aaaba, abaaa, baaab, aabab, babaa, abbba, ababb, bbaba, babbb, bbbab \\ anti2 & aabaa, aabba, abbaa, abaab, baaba, baabb, bbaab, abbab, babba, bbabb \\ anti3 & ababa, babab \end{matrix}

Soit w = x_{1}x_{2} ⋯ x_{n} un mot de longueur n. On note σ(w) = x′_{1}x′_{2} ⋯ x′_{n}. Alors tous les facteurs du mot infini ⋯ σ^{−2}(w) · σ^{−1}(w) · w · σ(w) · σ^{2}(w) ⋯ sont permutativement circulaires associé à σ. On obtient ainsi le résultat suivant :

Proposition 3 Pour toute permutation σ sur A, tout ensemble inévitable de mots de longueur n sur A rencontre chaque classe permutativement circulaire associée à σ de mots de longueur n.

Par exemple, pour les mots binaires de longueur n = 5, l’ensemble inévitable suivant (représenté en gras) rencontre à la fois chaque classe circulaire et anti-circulaire.

anti0  anti1  anti2  anti3
0  aaaaa
1 aaaab, baaaa aaaba, abaaa  aabaa
2 aaabb, bbaaa baaab aabba, abbaa
3  aabab, babaa abaab, baaba ababa
4 aabbb, bbbaa abbba baabb, bbaab
5  ababb, bbaba abbab, babba babab
6 abbbb, bbbba babbb, bbbab  bbabb
7  bbbbb

Pour toute permutation σ sur A, on note s_{n}(σ) le nombre des classes permutativement circulaires de mots de longueur n, associées à σ. En utilisant la théorie de Pólya, en particulier, le lemme de Cauchy-Frobenius-Burnside (voir par exemple [2]), nous obtenons la formule suivante pour calculer s_{n}(σ).

Proposition 4 Soit σ une permutation d’ordre k ayant c_{1} cycles de longueur 1, c_{2} cycles de longueur 2, …, c_{k} cycles de longueur k. Alors le nombre s_{n}(σ) des classes permutativement conjuguées associées à la permutation σ est donné par la formule suivante :

s_{n}(σ) = \frac{1}{mn} ∑_{d|n} ∑_{{j=0 \atop gcd(j,d)=1}}^{md−1}(∑_{r|j} rc_{r})^{n/d},

où m est le plus petit entier tel que σ^{m} = id.

Nous ne reproduisons pas la démonstration de cette Proposition. Dans le cas classique, σ est la permutation identique; on retrouve immédiatement la formule s_{n}(k). Nous allons étudier un autre cas spécial, lorsque σ est une permutation circulaire (123 ⋯ k).

Corollaire 1 Soit σ la permutation circulaire (123 ⋯ k) d’ordre k. Alors le nombre s_{n}(σ) des classes permutativement conjuguées associées à la permutation σ est donné par la formule suivante :

s_{n}(σ) = \frac{1}{kn} ∑_{{d|n \atop gcd(n/d,k)=1}} φ(n/d)k^{d}.

3 Les cas des petits entiers n

Nous présentons dans cette section les différents cas pour les petites valeurs de n (n ≤ 9) et de k (2 ≤ k ≤ 4). On verra que dans tous les cas pour k = 2 on trouve un ensemble inévitable de cardinal minimal s_{n}(k). Pour k = 3, on n’est parvenu à atteindre que les valeurs n ≤ 4.

3.1 Les cas n ≤ 4

Pour n = 1, il y a un seul ensemble inévitable qui est l’alphabet lui-même. Pour n = 2, sur A = {a_{0}, a_{1}, …, a_{k−1}}, on a un ensemble inévitable de s_{2}(k) = k(k + 1)/2 éléments

X = {a_{i}a_{j} | i ≤ j}.

Pour n = 3, 4, on a s_{3}(k) = (k^{3} + 2k)/3 et s_{4}(k) = (k^{4} + k^{2} + 2k)/4.

Sur deux lettres, on a les ensembles suivants. Chaque mot est donné en regard de la puissance de mot de Lyndon correspondante.

Lyndon Inévitable
0 aaa  aaa
1 aab  aba
2 abb  abb
3 bbb  bbb

Lyndon Inévitable
0 aaaa  aaaa
1 aaab  aaab
2 aabb  baab
3 abab  baba
4 abbb  bbab
5 bbbb  bbbb

Le nombre d’ensembles inévitables des mots binaires est donné par le tableau ci-dessous.

\begin{aligned}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ & 1 & 2 & 4 & 30 & 28 & 68288 & ≥ 6643 & ≥ 8223 & ≥ 1 \end{aligned}

Pour n = 3 et k = 3, 4 , on a les ensembles inévitables suivants.

Lyndon Inévitable
0 aaa  aaa
1 aab  aab
2 aac  caa
3  abb  bab
4  abc  cab
5  acb  acb
6  acc  cac
7  bbb  bbb
8  bbc  bcb
9  bcc  ccb
10 ccc  ccc

Lyndon Inévit.  Lyndon Inévit.
0 aaa  aaa 12 add  dad
1 aab  aba 13 bbb  bbb
2 aac  caa 14 bbc  cbb
3 aad  daa 15 bbd  dbb
4  abb  abb 16 bcc  cbc
5  abc  cab 17 bcd  dbc
6 abd  dab 18 bdc  cbd
7  acb  cba 19 bdc  dbd
8  acc  cac 20 ccc  ccc
9 acd  cda 21 ccd  cdc
10 adb  dba 22 cdd  cdd
11 adc  cad 23 ddd  ddd

Pour n = 4, on trouve

Lyndon Inévitable  Lyndon Inévitable
0 aaaa  aaaa  12 abcc  ccab
1 aaab  aaab  13 acac  caca
2 aaac  acaa  14 acbb  cbba
3 aabb  baab  15 acbc  acbc
4 aabc  caab  16 accb  ccba
5 aacb  acba  17 accc  cacc
6 aacc  aacc  18 bbbb  bbbb
7 abab  baba  19 bbbc  cbbb
8 abac  acab  20 bbcc  cbbc
9 abbb  babb  21 bcbc  cbcb
10 abbc  bcab  22 bccc  cbcc
11 abcb  bcba  23 cccc  cccc

3.2 Le cas n = 5

Pour n = 5, on a l’ensemble suivant, dû à Christopher Saker (communication personnelle, juin 2000).

Lyndon Inévitable
0 aaaaa  aaaaa
1 aaaab  aaaab
2 aaabb  baaab
3 aabab  abaab
4 aabbb  bbaab
5 ababb  babab
6 abbbb  bbabb
7 bbbbb  bbbbb

Il contredit l’affirmation donnée dans Lothaire ([4], Exercise 6.2 page 99) suivant laquelle 9 mots sont nécéssaires. Il n’est jamais trop tard pour s’amender. Il y a en fait 28 ensembles inévitables pour n = 5.

3.3 Le cas n = 6

Pour n = 6, Christopher Saker (communication personnelle, septembre 2000, [1]) a trouvé l’ensemble figurant dans la seconde colonne ci-dessous.

Une énumération systématique de tous les choix possibles de 6^{9} ×3^{2} ×2 ≈ 10^{8} pour conjuguer les puissances de mots de Lyndon permet d’obtenir la troisième colonne après ≈ 3 × 10^{6} itérations (quelques minutes).

Un tirage au hasard des 14 entiers donne la troisième colonne en moins de 10^{3} essais (instantané).

Lyndon Saker Enum Random
0 aaaaaa aaaaaa aaaaaa aaaaaa
1 aaaaab aaaaba aaaaab abaaaa
2 aaaabb aaaabb baaaab abbaaa
3 aaabab baaaba abaaab abaaab
4 aaabbb baaabb bbaaab aabbba
5 aabaab abaaba abaaba abaaba
6 aababb bbaaba aababb abbaab
7 aabbab abaabb abaabb bbabaa
8 aabbbb bbaabb bbaabb abbbba
9 ababab bababa ababab bababa
10 ababbb bababb abbbab babbba
11 abbabb bbabba babbab babbab
12 abbbbb bbabbb babbbb abbbbb
13 bbbbbb bbbbbb bbbbbb bbbbbb

Le nombre total de systèmes de représentants des classes circulaires est 6^{9}×3^{2}×2 ≈ 10^{8}. Le nombre d’ensembles inévitables minimaux est 68288. La densité des ensembles inévitables par rapport au nombre total de systèmes de représentants des classes circulaires pour n ≤ 6 est donnée ci-dessous.

n 1 2 3 4  5  6
1 1 0, 4 0, 2 10^{−2} 6 × 10^{−3}

3.4 Le cas n = 7

Le nombre total de systèmes de représentants des classes circulaires est 7^{18} ≈ 10^{15}. Nous avons obtenu l’ensemble ci-dessous par une méthode mixte énumération/tirage au hasard. Le nombre de tirages porte sur ≈ 10^{6} ensembles (exécution en moins d’une heure). L’énumération consiste à choisir les mots de petite période. Par exemple, le mot de période 2 doit être un conjugué du mot de Lyndon d’indice 10 ou 15 (avec une seule possibilité pour chacun). L’énumération pure peut tourner pendant plusieurs heures sans résultat.

Lyndon Inévitable  Lyndon Inévitable
0 aaaaaaa aaaaaaa 10 aababab abababa
1 aaaaaab aaabaaa 11 aababbb abbbaab
2 aaaaabb aaabbaa 12 aabbabb abbabba
3 aaaabab aababaa 13 aabbbab abbbaba
4 aaaabbb abbbaaa 14 aabbbbb bbbbaab
5 aaabaab aabaaba 15 abababb babbaba
6 aaababb ababbaa 16 ababbbb bbbbaba
7 aaabbab aabbaba 17 abbabbb bbbabba
8 aaabbbb bbbbaaa 18 abbbbbb bbbabbb
9 aabaabb baabbaa 19 bbbbbbb bbbbbbb

3.5 Les cas n = 8, 9

Pour n = 8, 9 sur deux lettres, des ensembles inévitables minimaux contiennent 36 et 60 mots respectivement. Dans le cas n = 8, le nombre total de systèmes de représentants de classes circulaires est

1^{2} · 2^{2} · 4^{3} · 8^{30} ≈ 1, 58 × 10^{29}.

Dans le cas n = 9, le nombre total de systèmes de représentants des classes circulaires est

1^{2} · 3^{2} · 9^{56} ≈ 2, 46 × 10^{54}.

Comme la densité des ensembles inévitables est de plus en plus faible (Y a-t-il une démonstration mathématique?), pour trouver les quelques ensembles inévitables parmi une quantité astronomique d’ensembles possibles, nous utilisons le fait suivant :

Fait: Soit A un ensemble inévitable de longueur n. On construit un ensemble B par enlèvement de la dernière lettre des mots dans A. Alors B est un ensemble inévitable de longueur n − 1.

En effet, on doit utiliser l’inverse du fait précédent, qui n’est plus un fait, mais plutôt une prévoyance :

Prévoyance: Soit B un ensemble inévitable de longueur n − 1. On construit une famille d’ensembles A_{1}, A_{2}, … par ajout d’une dernière lettre (soit a, soit b) dans les mots de B. Alors il y a beaucoup de chances de trouver un ensemble inévitable de longueur n parmi les ensembles A_{i}.

Pour utiliser cette méthode, nous avons d’abord énuméré tous les ensembles inévitables de longueur 6. Il y en a 68288. A partir de cette famille d’ensemble, nous avons trouvé 6643 ensembles inévitables de longueur 7, 8223 ensembles inévitables de longueur 8, 1 ensemble inévitable de longueur 9. La liste des ensembles peut être consulté sur le web :

        http://www-irma.u-strasbg.fr/~guoniu/papers/set

4 Systèmes de type fini

Soit S un système de type fini, c’est à dire un ensemble de mots infinis dans lequel on interdit l’apparition d’un nombre fini de mots. (voir [3] pour la définition précise de ce terme). On note s_{n} = s_{n}(S) le nombre d’orbites de points de période n dans S (aussi appelées colliers de longueur n). On note p_{n} = p_{n}(S) le nombre de points de période n et q_{n} = q_{n}(S) le nombre d’orbites de période exatement n. On pose

ζ(S) = exp ∑_{n≥1} \frac{p_{n}}{n} z^{n} = \frac{1}{1 − ∑_{n≥1} u_{n}z^{n}} .

On a alors pour tout n ≥ 1

p_{n} = nu_{n} + ∑_{1≤i≤n−1} p_{i}u_{n−i}

et

p_{n} = ∑_{d|n} dq_{d}.

Comme s_{n} = ∑_{d|n} q_{d} ces formules permettent de calculer s_{n} en fonction des p_{n} et donc des u_{n}. De plus, on a

s_{n} = \frac{1}{n} ∑_{d|n} φ(n/d)p_{d}

où φ désigne la fonction d’Euler. Ceci permet un calcul direct des s_{n}.

Si S est une partie de A^{Z} et X une partie de A^{∗}, on dit que X est inévitable dans S si tout élément de S a un facteur dans X.

Proposition 5 Soit S un système de type fini sur l’alphabet A et n ≥ 0 un entier. Si X est un ensemble inévitable de mots de longueur n, il contient au moins un représentant de chaque collier de période d pour d|n. On a donc Card(X) ≥ s_{n}(S).

Démonstration. Soit s = w^{ζ} un mot de période n de S. Comme X est inévitable, il existe un facteur de s qui est dans X. Ainsi, X contient un conjugué de w.

Problème 1 Soit S un systeme de type fini. Pour quels entiers n existe-t-il un ensemble inévitable de s_{n}(S) mots de longueur n?

La réponse n’est pas toujours positive. En effet, si S = (ab)^{ζ}, un tel ensemble n’existe que pour n pair (on a s_{n} = 0 pour n impair).

4.1 Pas de bb

Si S est le système S_{bb} des mots qui évitent bb sur deux lettres, on a

ζ(S) = \frac{1}{1 − z − z^{2}} .

On en déduit les valeurs suivantes.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ p_{n} & 1 & 3 & 4 & 7 & 11 & 18 & 29 & 47 & 76 & 123 & 199 & 322 & 521 \\ q_{n} & 1 & 1 & 1 & 1 & 2 & 2 & 4 & 5 & 8 & 11 & 18 & 25 & 40 \\ s_{n} & 1 & 2 & 2 & 3 & 3 & 5 & 5 & 8 & 10 & 15 & 19 & 31 & 41 \end{matrix}

Pour S_{bb}, on a les ensembles inévitables minimaux suivants pour n ≤ 9.

1 2 3  4  5  6  7  8  9
0 a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa
1  ab aba aaba aabaa aaaaba aaabaaa aaaabaaa aaaabaaaa
2  baba ababa abaaab aababaa ababaaaa aababaaaa
3  abaaba aabaaba aabaabaa aaaabaaba
4  bababa abababa abaaabaa aabaaabaa
5  ababaaab aabababaa
6  ababaaba aababaaab
7  abababab aababaaba
8  baabaabaa
9  ababababa

Sur 3 lettres, on a pour le système S_{aa} des mots qui évitent aa sur 3 lettres a, b, c tout d’abord ζ(S) = \frac{1}{1−2z−2z^{2}} . On en déduit les valeurs suivantes.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 \\ p_{n} & 2 & 8 & 20 & 56 & 152 \\ q_{n} & 2 & 3 & 6 & 12 & 30 \\ s_{n} & 2 & 5 & 8 & 17 & 32 \end{matrix}

Pour n ≤ 4, on obtient les ensembles inévitables suivants.

n 1 2 3 4
b ab bab abab
c ac bca abac
bb bac bbab
bc cac bcab
cc bbb abcb
bcb abcc
bcc acac
ccc bbac
bcac
cbac
ccac
bbbb
bbcb
bbcc
cbcb
ccbc
cccc

4.2 Pas de bbb

Pour S_{bbb}, on a

ζ(z) = \frac{1}{1 − z − z^{2} − z^{3}} .

On en déduit les valeurs suivantes.

n 1 2 3 4 5 6 7 8 9 10 11 12 13
p_{n} 1 3 7 11 21 39 71 131 241 443 2757
q_{n} 1 1 2 2 4 5 10 15 26 42 74 121 212
s_{n} 1 2 3 4 5 9 11 19 29 48 75 132 213

On a pour n ≤ 7 les ensembles inévitables minimaux suivants.

1 2 3  4  5  6  7
0 a aa aaa aaaa aaaaa aaaaaa aaaaaaa
1  ab aab aaba aabaa aaaaba aaabaaa
2  bab abba aabba abaaab aababaa
3  abab ababa abaaba aabaaba
4  babba bababa abababa
5  bbabba abbabba
6  ababba aababba
7  baabba aabbaba
8  aaabba aabbaaa
9  bababba
10  aabbaab

4.3 Autres systèmes

Le problème peut se présenter differemment pour des systèmes de type finis isomorphes. Ainsi, pour S = (a+bc)^{ζ} qui est isomorphe a (a+ba)^{ζ}, on a tout d’abord pas d’ensemble inévitable de s_{n} mots de longueur n pour n impair. En effet, le mot (bc)^{ζ} n’a pas de facteur répétable de longueur impaire. Les ensembles suivants sont inévitables pour n = 2, 4, 6.

n 2 4  6
aa aaaa aaaaaa
bc abca bcbcbc
bcbc aabcaa
abcbca
bcabca

Pour n = 8, il n’existe pas d’ensemble inévitable de 8 mots de longueur 8. En effet, le seul facteur répétable de longueur 8 de (abc)^{ζ} est w = bcabcabc. Mais les seuls facteurs répétables de longueur 8 du mot (abcbc)^{ζ} sont abcbcabc et bcabcbca qui sont conjugués de w.

5 Emboitements

On peut imaginer construire des ensembles inévitables pour le système plein en complétant progressivement des ensembles inévitables pour des systèmes de type fini plus petits.

Plus précisément, on peut construire un ensemble inévitable minimal X = {aaaa, baba, aaba, abba, bbba, bbbb} pour n = 4 de la façon suivante. On considère la suite

∅ ⊂ S_{b} ⊂ S_{bb} ⊂ S_{bbb}.

et aussi

X_{3} ⊂ X_{2} ⊂ X_{1} ⊂ X,

où X_{3} ={bbbb, bbba}, X_{2} ={bbbb, bbba, abba}, X_{1} ={bbbb, bbba, abba, aaba, baba}. On a

S_{bbb} = S_{X_{3}}
S_{bb} = S_{X_{2}}
S_{b} = S_{X_{1}}
∅ = S_{X}

On peut compléter un ensemble inévitable du système S_{bb} en un ensemble inévitable du système S_{bbb} en construisant un ensemble inévitable pour les mots qui ont le facteur bb mais pas le facteur bbb.

Les résultats pour n ≤ 8 sont représentés ci-dessous.

1 2 3 4  5  6  7  8
0  bb abb abba abbaa abbaaa aaabbaa abbaaaaa
1  abbab abbaab aababba abbaaaab
2  abbaba baabbaa abbaaaba
3  abbabb abbabba abbaaabb
4  aabbaba abbaabaa
5  bababba abbaabab
6  abbaabba
7  aaabbaba
8  ababbaba
9  abaabbab
10  abbabbab

Pour le système plein sur deux lettres S = {a, b}^{Z}, on parvient à construire pour chaque n ≤ 7 un ensemble inévitable par emboitement des systèmes S_{b^{i}} pour i ≤ n.

1 2 3  4  5  6  7
0 a aa aaa aaaa aaaaa aaaaaa aaaaaaa
1 b ab aba aaba aabaa aaaaba aaabaaa
2  bb abb baba ababa abaaab aababaa
3  bbb abba abbaa abaaba aabaaba
4  bbba abbab bababa abababa
5  bbbb abbba abbaaa aaabbaa
6  bbbba abbaab aababba
7  bbbbb abbaba baabbaa
8  abbabb abbabba
9  abbbaa aabbaba
10  abbbab bababba
11  abbbba abbbaaa
12  abbbbb abbbaab
13  bbbbbb abbbaba
14  abbbabb
15  abbbbaa
16  abbbbab
17  abbbbba
18  bbbbbba
19  bbbbbbb

On obtient donc ainsi une méthode de construction d’ensembles inévitables minimaux. Nous ne savons pas si cette construction est toujours possible.

References

[1] Peter M. Higgins and Christopher J. Saker. Unvoidable sets of words of uniform length. Technical report, University of Essex, 2001.

[2] Adalbert Kerber. Algebraic combinatorics via finite group actions. Wissenschaftsverlag, 1991.

[3] Douglas Lind and Brian H. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge, 1995.

[4] M. Lothaire. Combinatorics on words. Cambridge University Press, Cambridge, 1997.

[5] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, 2001. à paraître, disponible sur

http://www-igm.univ-mlv.fr/~berstel/Lothaire/index.html.

[6] Marcel-Paul Schützenberger. On the synchronizing properties of certain prefix codes. Inform. and Control, 7:23–36, 1964.