On the complexity function for sequences which are not uniformly recurrent

Abstract

We prove that every non-minimal transitive subshift $X$ satisfying a mild aperiodicity condition satisfies $\mathrm{limsup}{c}_n(X)-1.5n=\infty$, and give a class of examples which shows that the threshold of $1.5n$ cannot be increased. As a corollary, we show that any transitive $X$ satisfying $\mathrm{limsup}{c}_n(X)-n=\infty$ and $\mathrm{limsup}{c}_n(X)-1.5n<\infty$ must be minimal. We also prove some restrictions on the structure of transitive non-minimal $X$ satisfying $\mathrm{liminf}{c}_n(X)-2n=-\infty$, which imply unique ergodicity (for a periodic measure) as a corollary, which extends a result of Boshernitzan from the minimal case to the more general transitive case.

12 pages