On low-complexity bi-infinite words and their factors

Heinis, Alex 

Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 2, pp. 421-442

Abstract (VO)

In this paper we study bi-infinite words on two letters. We say that such a word has stiffness $k$ if the number of different subwords of length $n$ equals $n+k$ for all $n$ sufficiently large. The word is called $k$-balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most $k$. In the present paper we give a complete description of the class of bi-infinite words of stiffness $k$ and show that the number of subwords of length $n$ from this class has growth order $n^3$. In the case $k=1$ we give an exact formula. We also consider the class of $k$-balanced bi-infinite words. It is well-known that the number of subwords of length $n$ from this class has growth order $n^3$ if $k=1$. In contrast, we show that the number is $\ge 2^{n/2}$ when $k\ge 2$.

Résumé

Dans cet article on étudie des mots bi-infinis sur deux symboles. On dit qu’un tel mot est de rigidité $k$ si le nombre de facteurs différents de longueur $n$ est égal à $n+k$ pour $n$ grand. Un tel mot est appelé $k$-balancé si le nombre d’occurrences du symbole $a$ dans deux facteurs quelconques de même longueur peuvent différer au plus de $k$. Dans cet article on donne une description complète de la classe des mots bi-infinis de rigidité $k$ et on montre que le nombre de facteurs de longueur $n$ de cette classe est de l’ordre de $n^3$. Dans le cas $k=1$ on donne une formule exacte. On considère aussi la classe des mots bi-infinis $k$-balancés. Il est bien connu que le nombre de facteurs de longueur $n$ est de l’ordre de $n^3$ si $k=1$. En revanche, on montre que ce nombre est $\ge 2^{n/2}$ si $k\ge 2$.