Mot de Toeplitz

En combinatoire, et spécialement en combinatoire des mots, un mot de Toeplitz est un mot infini obtenu par un processus itératif qui est décrit par une suite d'une ou plusieurs règles d'interclassement dits « motifs de Toeplitz ». Les plus connues de ces mots sont la suite des suite de pliage de papier et la suite chorale de Stewart.

Description

Un motif de Toeplitz est un mot fini sur un alphabet $A\cup ?$ , où $A$ est un alphabet fini et $?$ est un symbole distingué, considéré comme figurant un « trou ».

On construit un mot de Toeplitz comme suit :

On part d'un motif de Toeplitz $t_{1}$ , répété infiniment, ce qui donne le mot infini $t_{1}^{\omega }=t_{1}t_{1}t_{1}\cdots$ ;
dans ce mot, on remplace les occurrences du trou $?$ consécutivement par les symboles d'un deuxième motif de Toeplitz répété infiniment ;
on répète cette opération une infinité de fois.

Le résultat est le par définition un mot de Toeplitz.

Plus formellement, on considère un motif $w\in A(A\cup ?)^{*}$ , et on pose

T_{0}(w)=?^{\omega },\quad T_{i+1}(w)=F_{w}(T_{i}(w))

où $F_{w}(z)$ , pour tout $z\in (A\cup ?)^{\omega }$ , est le mot obtenu à partir du mot infini $w^{\omega }$ en remplaçant la suite de toutes les occurrences de ? par $z$ . Le mot de Toeplitz déterminé par le motif $w$ est la limite

T(w)=\lim _{i\to \infty }T_{i}(w)\in A^{\omega }

Exemples

Pliage de papier

On prend un seul motif qui est 0?1?. On remplace, dans le mot

0?1?0?1?0?1?0?1?...

les symboles ? par ceux du motif (en rouge 0?1? pour plus de clarté) répété infiniment :

001?011?001?011?...

Dans ce cas, un symbole $?$ sur deux est remplacé par 0 ou par 1, les autres laissé inchangés. La deuxième étape donne donc :

001?011?001?011?001?011?...

On itère ce processus :

0010011?0011011?00100011?...

Le symbole ? étant remplacé par 0 ou 1 une fois sur deux, le préfixe sans ? est de plus en plus long. La limite est le suite de pliage de papier : On peut voir la construction comme un remplissage de trous : On commence par une suite alternée de 0 et de 1, séparée par des « trous ». Dans un deuxième temps, ces trous sont remplis, à leur tour, par une suite alternée de 0 et de 1 lacunaire, etc. La suite résultante est la suite de pliage :

0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 .  
  0   .   1   .   0   .   1   .   0   .   1   .   0   .   1   .   0   .   1   .
      0       .       1       .       0       .       1       .  
              0               .               1

d'où la suite totale :

0 0 1 0 0 1 1 0 0 0 1 1 0 1 1...

Un mot périodique

Le mot périodique $(112)^{\omega }$ peut être obtenu de diverses façon comme mot de Toeplitz. On a^[1] :

(112)^{\omega }=T(112??????)=T(112?12?1?)=T(1?21?211????)

En effet, pour la première formulation, les trois premières étapes sont :

1 1 2 . . . . . . 1 1 2 . . . . . .
      1 1 2 . . .       1 1 2 . . .
            1 1 2             1 1 2

Un mot sans cube

Le motif 12? détermine le mot dont le début est :

1 2 . 1 2 . 1 2 . 1 2 . 1 2
    1     2     .     1

soit le mot

121122121112112...

qui est le point fixe du morphisme

h:1\mapsto 121,2\mapsto 122

Ce mot infini est sans cube, même s'il contient une infinité de facteurs de la forme $uauau$ , avec $a$ une lettre.

La suite chorale de Stewart

Le motif 0?1 détermine un mot $s$ appelé la suite chorale de Stewart^[2]. La suite est le point fixe du morphisme :

0\mapsto 001,1\mapsto 011

Elle commence par :

s = 001001011001001011001011011...

On a la description explicite suivante : $s(3n)=0,s(3n-1)=1,s(3n+1)=a(n)$ . La suite est sans cube, et c'est un mot de Lyndon infini^[2].

Suites de Stewart

Fici et Shallit (2022) étudient une famille plus large de mots de Toeplitz obtenue en utilisant au choix plusieurs règles d'interclassement. Il existe 6 motifs de Toeplitz ternaires de longueur 3 contenant un trou ; ce sont, avec les notations des auteurs :

a = 01? b= 10? c= 0?1 d= 1?0 e= ?01 f= ?10

En utilisant une suite infinie de motifs parmi ces six, on obtient une famille infinie de mots de Toeplitz. En particulier :

la suite définie par ${\mathsf {c}}^{\omega }={\mathsf {cccc}}\cdots$ est la suite chorale de Stewart (suite A116178 de l'OEIS) ;
la suite définie par $({\mathsf {ab}})^{\omega }={\mathsf {ababab}}\cdots$ est le mot du tracé du triangle de Sierpiński (suite A156595 de l'OEIS) ;
Les mots de Stewart généralisés de Joel Reyes Noche^[3] sont les mots définis par les suites de motifs :

{\mathsf {a}}^{\omega },{\mathsf {b}}^{\omega },{\mathsf {c}}^{\omega },{\mathsf {d}}^{\omega },{\mathsf {e}}^{\omega },{\mathsf {f}}^{\omega }

Parmi les résultats démontrés par les auteurs, il y a notamment :

Tout mot infini engendré par une suite de motifs de Stewart est sans cube, et il contient une facteur d’exposant arbitrairement proche de 3.

Ces résultats sont prouvés en formulant des énoncés vérifiés à l'aide d'un logiciel appelé Walnut.

Mots de Toeplitz et morphismes itérés

Les mots de Toeplitz peuvent souvent être représentés comme points fixes d'un morphisme. La description précise utilise la classification suivante des motifs : un motif de Toeplitz est de type $(p,q)$ s'il est de longueur $p$ et contient $q$ occurrences du symbole '?'. On a les cas suivants :

Théorème —

Si le motif est de type $(p,1)$ , le mot est engendré par un morphisme uniforme ;
si $q$ divise $p$ , le mot engendré est l'image, par un morphisme préservant la longueur, d'un mot engendré par un morphisme uniforme ;
sinon, le mot est engendré en itérant périodiquement $q$ morphismes^[1].

Notes et références

↑ ^{a et b} Cassaigne et Karhumaki 1997
↑ ^{a et b} suite A116178 de l'OEIS.
↑ Reyes Noches (2008).

Bibliographie

Cassaigne, Julien et Karhumäki, Juhani, « Toeplitz words, generalized periodicity and periodically iterated morphisms », Journal européen de combinatoire, vol. 18, n^o 5,‎ 1997, p. 497-510 (zbMATH 0881.68065).
Allouche, Jean-Paul et Bacher, Roland, « Toeplitz sequences, paperfolding, towers of Hanoi and progression-free sequences of integers », Enseign. Math. II. Sér., vol. 38, n^os 3-4,‎ 1992, p. 315-327 (zbMATH 0784.11008).
Fici, Gabriele et Shallit, Jeffrey, « Properties of a class of Toeplitz words », Theoretical Computer Science, vol. 922,‎ 2022, p. 1-12 (DOI https://doi.org/10.1016/j.tcs.2022.04.006, arXiv 2112.12125).
Boccuto, Antonio et Carpi, Arturo, « Repetitions in Toeplitz words and the Thue threshold », dans Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (éditeurs), Beyond the Horizon of Computability. CiE 2020, Springer Cham, coll. « Lecture Notes in Computer Science » (n^o 12098), 2020 (DOI https://doi.org/10.1007/978-3-030-51466-2_23), p. 264–276.
Jacobs, Konrad et Keane, Michael, « 0–1-sequences of Toeplitz type », Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 13,‎ 1969, p. 123–131.
Reyes Noche, Joel, « Generalized choral sequences », Matimy ́as Matematika, Journal of the Mathematical Society of the Philippines, vol. 31, n^os 1-3,‎ 2008, p. 25-28 (ISSN 0115-6926, lire en ligne).
Stewart, Ian, How to cut a cake. And other mathematical conundrums, Oxford University Press, 2006, xi + 231 (ISBN 978-0-19-920590-5, zbMATH 1210.00016), Chapitre 6. Traduction française : Stewart, Ian (trad. Véronique Bordellès, avec la collaboration scientifique de Dominique Roux), Ta moitié est plus grande que la mienne ! : comment couper équitablement un gâteau, et 19 autres énigmes mathématiques, Paris, Dunod, 2007, xv + 236 (ISBN 978-2-10-051266-9, SUDOC 119415313).