Maximal pattern complexity for Toeplitz words

Abstract

The notion of the maximal pattern complexity of words was introduced by Kamae and Zamboni. In this paper, we obtain an almost exact formula for the maximal pattern complexity $p^*_\alpha(k)$ of Toeplitz words $\alpha$ on an alphabet ${\mathbb A}$ defined by a sequence of coding words $(\eta^{(n)})^\infty\in({\mathbb A}\cup\{?\})^{\mathbb N}(n=1,2,\dotsc)$ including just one ‘?’ in their cycles $\eta^{(n)}$. Using this formula, we characterize pattern Sturmian words (i.e. $p^*_\alpha(k)=2k$ (for all $k$)) in this class. Moreover, we give a characterization of simple Toeplitz words in the sense of Kamae and Zamboni in terms of pattern complexity. In the case where $\eta^{(1)}=\eta^{(2)}=\dotsb$, we obtain the value $\lim_{k\to\infty}p_\alpha^*(k)/k$. We construct a Toeplitz word $\alpha\in{\mathbb A}^{\mathbb N}$ with $\#\A=2$ such that $p^*_\alpha(k)=2^k~(k=1,2,\dotsc)$, while Toeplitz words in our sense always have discrete spectra.