On the structure of sequences with minimal maximal pattern complexity

Abstract In 2002, Kamae and Zamboni [ Ergod. Th. & Dynam. Sys. 22 (4) (2002), 1191–1199] introduced maximal pattern complexity and determined that any aperiodic sequence must have maximal pattern complexity at least $2k$ . In 2006, Kamae and Rao [ European J. Combin. 27 (1) (2006), 125–137] examined the maximal pattern complexity of sequences over larger alphabets and showed that sequences which have maximal pattern complexity less than $\ell k$ , for $\ell $ the size of the alphabet, must have some periodic structure. In this paper, we investigate the structure of sequences of low maximal pattern complexity over $\ell $ letters, where $\liminf _{k \to \infty } p_{\alpha }^*(k) - 3k = -\infty $ . In addition, we show that the minimal maximal pattern complexity of an aperiodic sequence which uses all $\ell $ letters is $p_{\alpha }^*(k) = 2k + \ell -2$ and give an exact structure for aperiodic sequences with this maximal pattern complexity.