Frequencies of subwords in words of linear subword complexity

Abstract

Using a method of Balková--Pelantová, we show that if $\mathbf{w}$ is a right-infinite word over a finite alphabet, then for each nonnegative integer $N$ there are at most $3(p_{\mathbf{w}}(N+1)-p_{\mathbf{w}}(N))+1$ distinct upper (and likewise lower and ordinary when they exist) frequencies for length-$(N+1)$ subwords of $\mathbf{w}$, where $p_{\mathbf{w}}(n)$ is the subword complexity function of $n$. In particular, this gives a uniform upper bound when $\mathbf{w}$ has linearly bounded subword complexity. We provide examples showing that whenever $f(n)$ is a weakly increasing function tending to infinity, there is a word $\mathbf{w}$ such that the number of subwords of length $n$ is $O(nf(n))$ and for which the limit supremum of the number of distinct upper frequencies of length-$N$ subwords of $\mathbf{w}$ as $N\to \infty$ is infinite.

11 pages

Topics & keywords