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 },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)=\underset{i\to \mathrm{\infty }}{\lim }{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 Modèle:Rouge pour plus de clarté) répété infiniment :

0Modèle:Rouge1Modèle:Rouge0Modèle:Rouge1Modèle:Rouge0Modèle:Rouge1Modèle:Rouge0Modèle:Rouge1Modèle:Rouge...

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 :

001Modèle:Rouge011Modèle:Rouge001Modèle:Rouge011Modèle:Rouge001Modèle:Rouge0011Modèle:Rouge...

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 :

$(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. 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.

Suites de Stewart

Modèle:Harvsp é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 ${𝖼}^{\omega }=𝖼𝖼𝖼𝖼\cdots$ est la suite chorale de Stewart (Modèle:OEIS) ;
• la suite définie par $(𝖺𝖻{)}^{\omega }=𝖺𝖻𝖺𝖻𝖺𝖻\cdots$ est le mot du tracé du triangle de Sierpiński (Modèle:OEIS) ;
• Les mots de Stewart généralisés de Joel Reyes NocheModèle:Sfnp sont les mots définis par les suites de motifs :

${𝖺}^{\omega },{𝖻}^{\omega },{𝖼}^{\omega },{𝖽}^{\omega },{𝖾}^{\omega },{𝖿}^{\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 : Modèle:Théorème

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage. Traduction française : Modèle:Ouvrage.