On the character of words of sublinear complexity
Volume 184 / 2018
Abstract
Let $\mathbb A^*$ denote the free monoid generated by a finite non-empty set $\mathbb A$. For each infinite word $x=x_0x_1x_2\cdots \in\mathbb A^\omega$, the factor complexity $p_x(n)$ counts the number of distinct blocks $x_ix_{i+1}\cdots x_{i+n-1}$ of length $n$ occurring in $x$. In other words, the factor complexity of $x$ is the complexity of the language of its factors $\operatorname{Fac}_x=\{x_ix_{i+1}\cdots x_{j}: 0\leq i\leq j\}$. Our starting point in this paper is the following characterisation of infinite words of sublinear factor complexity obtained recently by the author together with J. Cassaigne, A. Frid and S. Puzynina: Let $x\in \mathbb A^\omega$. Then $p_x(n)=O(n)$ if and only if $\operatorname{Fac}_{x} \subseteq S^2$ for some $S\subseteq \mathbb A^*$ with $\limsup p_S(n) \lt \infty$. In other words, $p_x(n)\leq Cn$ for some constant $C$ if and only if there exists a set $S$ of bounded complexity such that every factor $w$ of $x$ can be factored as $w=uv$ with $u,v \in S$. Given an infinite word $x\in \mathbb A^\omega$, we define its character, denoted $\chi(x)$, to be the least value of $\limsup p_S(n)$ over all languages $S$ such that $\operatorname{Fac}_x\subseteq S^2$. Clearly $\chi(x) \in [1, \infty]$, and it follows from the above characterisation that $p_x(n)=O(n)$ if and only if $\chi(x) \lt \infty$. We prove that $\chi(x)=1$ if and only if $x$ is ultimately periodic, and that $\chi(x)=2$ whenever $x$ is a Sturmian word.
