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 2 k $2k$ 2 k . 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 ℓ k $\ell k$ script l k , for ℓ $\ell $ script l 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 $ script l letters, where lim inf k → ∞ p α ∗ ( k ) − 3 k = − ∞ $\liminf _{k \to \infty } p_{\alpha }^*(k) - 3k = -\infty $ limit inf Underscript k right arrow infinity Endscripts p Subscript alpha Superscript asterisk Baseline left parenthesis k right parenthesis minus 3 k equals negative infinity . In addition, we show that the minimal maximal pattern complexity of an aperiodic sequence which uses all ℓ $\ell $ script l letters is p α ∗ ( k ) = 2 k + ℓ − 2 $p_{\alpha }^*(k) = 2k + \ell -2$