Boshernitzan’s condition, factor complexity, and an application

Abstract

Boshernitzan gave a decay condition on the measure of cylinder sets that implies unique ergodicity for minimal subshifts. Interest in the properties of subshifts satisfying this condition has grown recently, due to a connection with discrete Schrödinger operators, and of particular interest is how restrictive the Boshernitzan condition is. While it implies zero topological entropy, our main theorem shows how to construct minimal subshifts satisfying the condition, and whose factor complexity grows faster than any pre-assigned subexponential rate. As an application, via a theorem of Damanik and Lenz, we show that there is no subexponentially growing sequence for which the spectra of all discrete Schrödinger operators associated with subshifts whose complexity grows faster than the given sequence have only finitely many gaps.

1. Boshernitzan’s complexity conditions

For a symbolic dynamical system $(X,\sigma )$, many of the isomorphism invariants we have are statements about the growth rate of the word complexity function $P_X(n)$, which counts the number of distinct cylinder sets determined by words of length $n$ having nonempty intersection with $X$. For example, the exponential growth of $P_X(n)$ is the topological entropy of $(X,\sigma )$, while the linear growth rate of $P_X(n)$ gives an invariant to begin distinguishing between zero entropy systems. Of course there are different senses in which the growth of $P_X(n)$ could be said to be linear and different invariants arise from them. For example, one can consider systems with linear limit inferior growth, meaning $\liminf _{n\to \infty }P_X(n)/n < \infty$, or the stronger condition of linear limit superior growth, meaning $\limsup _{n\to \infty }P_X(n)/n < \infty$. (There exist systems satisfying the first condition but not satisfying the second.)

Under the assumption of linear limit inferior growth, and with a further hypothesis that the system $(X,\sigma )$ is minimal, Boshernitzan 2 showed that the system only supports finitely many $\sigma$-invariant ergodic probability measures. Boshernitzan also considered another version of linear complexity on a minimal shift, studying linear measure growth, also referred to in the literature (see for example 7) as condition (B): if $\mu$ is a $\sigma$-invariant Borel probability measure on $X$, assume that there exists a sequence of integers $n_k \to \infty$ such that

$$\begin{equation*} \inf _k \min _{|w|=n_k} n_k\mu ([w]) > 0, \end{equation*}$$

where $\mu ([w])$ denotes the measure of the cylinder set determined by the word $w$ and $|w|$ denotes the length of the word $w$. Boshernitzan showed that linear measure growth implies that the minimal subshift $(X,\sigma )$ is uniquely ergodic. Another consequence of linear measure growth, for word complexity, is that $\liminf _{n\to \infty }P_X(n)/n$ is finite.

Each of these three linear complexity assumptions, linear limit inferior growth, linear limit superior growth, and linear measure growth, immediately implies that the associated system has zero topological entropy. It is natural to ask which of these conditions imply any of the others. One of our main results is that while linear measure growth implies linear limit inferior growth, it does not imply linear limit superior growth. In fact, we show linear measure growth is flexible enough that examples satisfying it can be constructed with limit superior growth faster than any pre-assigned subexponential growth rate.

A second motivation for the construction we give comes from a question on the spectra of discrete Schrödinger operators that arise from a subshift. If $(X,\sigma )$ is a shift, then each $x = (x_n)_{n\in \mathbb{Z}}\in X$ defines a discrete Schrödinger operator $H_x\colon \ell ^2(\mathbb{Z})\to \ell ^2(\mathbb{Z})$ by

$$\begin{equation*} (H_xu)(n)\coloneq u(n+1)+u(n-1)+x_nu(n) \end{equation*}$$

(and $x$ is called the potential function for this operator). Characterizing the spectra of discrete Schrödinger operators is an active field of study (e.g., 147) and we refer the reader to 56 for excellent surveys on the theory of discrete Schrödinger operators associated with symbolic systems. For operators built in this way, the dynamical properties of $(X,\sigma )$ can influence the spectral properties of $H_x$ for any $x\in X$. When $(X,\sigma )$ is minimal, Damanik (personal communication) asked whether the condition that $h_{top}(X)>0$ implies that the spectrum of $H_x$ can have only finitely many gaps. Our example shows that the assumption of positive entropy in this question cannot be relaxed to just ask that $P_X(n)$ grow “nearly exponentially” infinitely often: for any subexponential rate $\{a_n\}_{n=1}^{\infty }$ our example, via a theorem of Damanik and Lenz 7, gives a Schrödinger operator whose spectrum has infinitely many gaps and whose complexity is larger than $\{a_n\}_{n=1}^{\infty }$ infinitely often.

We turn to stating our main theorem. For a word $w$ in the language of a subshift $(X, \sigma )$, we denote the cylinder set starting at zero it determines by $[w]_0^+$ and we denote the words of length $n$ in the language of the subshift by $\mathcal{L}_n(X)$ (for further discussion of the definitions, see Section 2.1):

Theorem 1.1.

Let $\{a_n\}_{n=1}^{\infty }$ be a sequence of positive integers satisfying

$$\begin{equation} \limsup _{n\to \infty }\frac{1}{n}\log a_n=0. {\tag{1}} \end{equation}$$

There exists a minimal and uniquely ergodic subshift $(Y, \sigma )$ such that

$$\begin{equation*} \limsup _{n\to \infty }\frac{P_Y(n)}{a_n}=\infty \end{equation*}$$

and such that the unique invariant measure $\mu$ has the property that there is a sequence $\{n_k\}_{k=1}^{\infty }$ satisfying

$$\begin{equation} \liminf _{k\to \infty }\min \left\{\mu ([w]_0^+)\cdot n_k\colon w\in \mathcal{L}_{n_k}(Y)\right\}>0. {\tag{2}} \end{equation}$$

The hypothesis in this theorem is a type of subexponential growth on the sequence $\{a_n\}_{n=1}^{\infty }$ and the constructed system is a zero entropy system satisfying the Boshernitzan condition while the factor complexity grows faster than the given sequence. To prove the theorem, it suffices to show that the system $(Y, \sigma )$ supports a measure $\mu$ satisfying the property 2, as it then follows from Boshernitzan 3, Theorem 1.2 that the system is uniquely ergodic.

An immediate corollary of Theorem 1.1, combined with a theorem of Damanik and Lenz 7, Theorem 2, is the following:

Corollary 1.2.

Let $\{a_n\}_{n=1}^{\infty }$ be a sequence of positive integers which grows subexponentially in the sense of 1. There exists a Cantor set $\Sigma \subset \mathbb{R}$, of Lebesgue measure zero, and a minimal subshift $(Y,\sigma )$ such that

$$\begin{equation*} \limsup _{n\to \infty }\frac{P_Y(n)}{a_n}=\infty \end{equation*}$$

and for every $y\in Y$ the discrete Schrödinger operator $H_y\colon \ell ^2(\mathbb{Z})\to \ell ^2(\mathbb{Z})$ given by

$$\begin{equation*} (H_yu)(n)\coloneq u(n-1)+u(n+1)+y_nu(n) \end{equation*}$$

has spectrum exactly $\Sigma$.

2. Background

2.1. Symbolic systems

We work over the alphabet $\mathcal{A} = \{0,1\}\subset \mathbb{R}$ and consider $\mathcal{A}^\mathbb{Z}$. We denote $x\in \mathcal{A}^\mathbb{Z}$ as $x = (x_n)_{n\in \mathbb{Z}}$ and we endow $\mathcal{A}^\mathbb{Z}$ with the topology induced by the metric $d(x, y) = 2^{-\inf \{|i|\colon x_i \neq y_i\}}$. The left shift $\sigma \colon \mathcal{A}^\mathbb{Z}\to \mathcal{A}^\mathbb{Z}$ is defined by $(\sigma x)_n = x_{n+1}$ for all $n\in \mathbb{Z}$. If $X\subset \mathcal{A}^\mathbb{Z}$ is closed and $\sigma$-invariant, then $(X, \sigma )$ is a subshift.

If $w = (a_{-n}, \ldots , a_0, \ldots , a_n)\in \mathcal{A}^{2n+1}$, then the central cylinder set $[w]_0$ determined by $w$ is defined to be

$$\begin{equation*} \{x\in X\colon x_j = a_j \text{ for } j=-n, \ldots , n\}. \end{equation*}$$

If $w = (a_0,a_1,\dots ,a_n)\in \mathcal{A}^{n+1}$, then the one-sided cylinder set $[w]_0^+$ determined by $w$ is defined to be

$$\begin{equation*} \{x\in X\colon x_j = a_j \text{ for } j=0, \ldots , n\}. \end{equation*}$$

If $(X, \sigma )$ is a subshift and $n\in \mathbb{N}$, the words $\mathcal{L}_n(X)$ of length $n$ are defined to be the collection of all $w\in \mathcal{A}^n$ such that $[w]_0^+\neq \emptyset$, and the language $\mathcal{L}(X)$ of the subshift is the union of all the words:

$$\begin{equation*} \mathcal{L}(X) = \bigcup _{n=1}^\infty \mathcal{L}_n(X). \end{equation*}$$

If $w\in \mathcal{L}(X)$ is a word, we say that $u\in \mathcal{L}(X)$ is a subword of $w$ if $w = w_1uw_2$ for some (possibly empty) words $w_1, w_2\in \mathcal{L}(X)$.

For a subshift $(X, \sigma )$, the word complexity $P_X(n)\colon \mathbb{N}\to \mathbb{N}$ is defined to be the number of words of length $n$ in the language:

$$\begin{equation*} P_X(n) = |\mathcal{L}_n(X)|. \end{equation*}$$

2.2. Well approximable irrationals

A key ingredient in our construction is Theorem 2.1 of V. Sos 9 (formerly known as the Steinhaus Conjecture).

Theorem 2.1 (Three Gap Theorem).

Assume $\alpha \in \mathbb{R}\setminus \mathbb{Q}$ and $n\in \mathbb{N}$, the partition of the unit circle $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ determined by the points $\{0, \alpha , 2\alpha , \ldots , (n-1)\alpha \}$, with all points taken $\pmod 1$. Then the subintervals determined by this partition have at most three distinct lengths, and when there are three distinct lengths, the largest length is the sum of the other two.

Given an integer $n\geq 1$ and irrational $\alpha$, we refer to the partition determined by the points $\{0, \alpha , 2\alpha , \ldots , (n-1)\alpha \}$ of the unit circle as the $n$-step partition, and make use of it for well chosen $\alpha$. An irrational real number $\alpha$ is well approximable if there exists a sequence $\{n_k\}_{k=1}^{\infty }$ of integers such that for each $n_k$, the associated $n_k$-step partition in the Three Gap Theorem has three distinct lengths and the ratio of the smallest to the largest length in such a partition tends to zero as $k\to \infty$, and without loss of generality we can assume that shortest length in the $n_k$-step partition is not present in the $n_{k-1}$-step partition. (This sequence is obtained as the denominators in the regular continued fraction expansion of $\alpha$, and this can be rephrased as unbounded partial quotients.) Furthermore, we can choose the sequence $\{n_k\}_{k=1}^{\infty }$ such that the smallest length present in the $n_k$-step partition is not present for in the $(n_k-1)$-step partition.

An irrational that is not well approximable is said to be badly approximable, and the set of badly approximable reals has Lebesgue measure zero. Notice that if $\alpha$ is well approximable and $\{n_k\}_{k=1}^{\infty }$ is the associated sequence, then the $(n_k-1)$-step partition in the Three Gap Theorem has only two distinct lengths and the ratio of their lengths tends to $1$ as $k\to \infty$.

2.3. Sturmian systems

To make use of the approximations determined by the Three Gap Theorem, we use Sturmian sequences. To define this notion, let $\alpha$ be an irrational real number and consider the partition $\mathcal{P}=\{[0,\alpha ),[\alpha ,1)\}$ of $[0,1)$ and let $T_\alpha$ denote the rotation $T(x) = x+\alpha \pmod 1$. For any $x\in [0,1)$ and each $n\in \mathbb{Z}$, define

$$\begin{equation*} c_n(x)=\begin{cases} 0 & \text{if $x+n\alpha \pmod 1 \in [0, \alpha )$;} \\ 1 & \text{otherwise}. \end{cases} \end{equation*}$$

Let $X_{\alpha }\subseteq \{0,1\}^{\mathbb{Z}}$ be closure of the set of all sequences of the form

$$\begin{equation*} (\dots ,c_{-2}(x),c_{-1}(x),c_0(x),c_1(x),c_2(x),\dots ). \end{equation*}$$

Then $X_{\alpha }$ is called the Sturmian shift with rotation angle $\alpha$. A classical fact is that the system $(X_{\alpha }, \sigma )$ is minimal, uniquely ergodic, and $P_{X_{\alpha }}(n)=n+1$ for all $n\in \mathbb{N}$.

Moreover, words $w\in \mathcal{L}_{X_{\alpha }}(X)$ correspond to the cells of $\bigvee _{i=0}^{|w|-1}T_\alpha ^{-i}\mathcal{P}$, and with respect to the unique invariant measure $\nu _{\alpha }$, the measure of the cylinder set $[w]_0^+$ is the Lebesgue measure $\lambda$ of the cell of $\bigvee _{i=0}^{|w|-1}T_\alpha ^{-i}\mathcal{P}$ corresponding to $w$. In other words, there is a bijection

$$\begin{equation} \varphi _{n}\colon \mathcal{L}_n(X_{\alpha })\to \mathcal{P}_{n} {\tag{3}} \end{equation}$$

such that for any word $w\in \mathcal{L}_n(X)$, we have

$$\begin{equation*} \nu _i([w]_0^+)=\lambda (\varphi _{n}(w)). \end{equation*}$$

In view of the discussion in Section 2.2, if $\alpha$ is well approximable, there exists a sequence $\{n_k\}_{k=1}^{\infty }$ such that

$$\begin{equation} \lim _{k\to \infty }\frac{\min \{\nu _{\alpha }([w]_0^+)\colon w\in \mathcal{L}_{n_k-1}(X_{\alpha })\}}{\max \{\nu _{\alpha }([w]_0^+)\colon w\in \mathcal{L}_{n_k-1}(X_{\alpha })\}}=1. {\tag{4}} \end{equation}$$

Recall that $(X, \sigma )$ is uniquely ergodic if there exists a unique Borel probability $\sigma$-invariant measure on $X$. Recasting this definition in terms of the language, the subshift $(X, \sigma )$ is uniquely ergodic if and only if for any $w\in \mathcal{L}(X)$, there exists $\delta \geq 0$ such that for any $\varepsilon >0$ there is an integer $N\geq 1$ with the property that for all $u\in \mathcal{L}(X)$ with $|u|\geq N$, we have

$$\begin{equation*} \left|\frac{\#\text{ of occurrences of $w$ as a subword of $u$}}{|u|}-\delta \right|<\varepsilon . \end{equation*}$$

In this case, $\delta$ is the measure of the cylinder set $[w]_0^+$ with respect to the unique invariant measure on $X$.

3. The construction

We construct a minimal subshift $X\subseteq \{0,1\}^{\mathbb{Z}}$ such that

$$\begin{equation} \limsup _{n\to \infty }\frac{P_X(n)}{n}=\infty {\tag{5}} \end{equation}$$

and for which there exists an invariant measure $\mu$ supported on $X$ and a sequence $\{n_k\}_{k=1}^{\infty }$ satisfying

$$\begin{equation} \liminf _{k\to \infty }\min \left\{\mu ([w]_0^+)\cdot n_k\colon w\in \mathcal{L}_{n_k}(X)\right\}>0. {\tag{6}} \end{equation}$$

3.1. Setup

We fix $\varepsilon = 1/8$ (any value $\leq 1/8$ suffices) and choose a well approximable real number $\alpha$ satisfying

$$\begin{equation} \left|\frac{1}{2}-\alpha \right|<\varepsilon . {\tag{7}} \end{equation}$$

Let $X_{\alpha }$ denote the Sturmian shift with rotation angle $\alpha$ and let $\nu$ denote the (unique) invariant measure supported on $X_{\alpha }$ (see Section 2.3). For each $n\in \mathbb{N}$, let $\mathcal{P}_{n}$ denote the partition of $[0,1)$ into subintervals whose endpoints are given by the set

$$\begin{equation*} \{0,\alpha ,2\alpha , \dots ,(n-1)\alpha \}, \end{equation*}$$

where, as usual, all points are taken in $[0,1)$, meaning modulo $1$.

Using 4 derived from the well approximability of $\alpha$, there exists $n\in \mathbb{N}$ satisfying

$$\begin{equation} \frac{\lambda (\text{shortest subinterval in }\mathcal{P}_{n})}{\lambda (\text{longest subinterval in }\mathcal{P}_{n})}>1-\varepsilon {\tag{8}} \end{equation}$$

(in fact there exist infinitely many such $n$). The partition $\mathcal{P}_{n}$ is obtained from the partition $\mathcal{P}_{n-1}$ by subdividing one of the subintervals in $\mathcal{P}_{n-1}$ into two pieces. Thus the length of the longest subinterval in $\mathcal{P}_{n-1}$ is at most twice the length of the longest subinterval in $\mathcal{P}_{n}$. Similarly the length of the shortest subinterval in $\mathcal{P}_{n-1}$ is at least as long as the length of the shortest subinterval in $\mathcal{P}_{n}$. Therefore we also have

$$\begin{equation*} \frac{\lambda (\text{shortest subinterval in }\mathcal{P}_{n-1})}{\lambda (\text{longest subinterval in }\mathcal{P}_{n-1})}\geq \frac{\lambda (\text{shortest subinterval in }\mathcal{P}_{n})}{2\cdot \lambda (\text{longest subinterval in }\mathcal{P}_{n})}>\frac{1}{2}-\frac{\varepsilon }{2}. \end{equation*}$$

We are now ready to begin our construction.

$$\begin{equation} \text{Fix some $n$ satisfying \xhref[disp-formula]{#texmlid4}{8}} {\tag{9}} \end{equation}$$

and let $\varphi _{n-1}\colon \mathcal{L}_{n-1}(X_{\alpha })\to \mathcal{P}_{n-1}$ and $\varphi _{n}\colon \mathcal{L}_{n}(X_{\alpha })\to \mathcal{P}_{n}$ denote the bijections defined in 3. Then

$$\begin{equation} \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(X_{\alpha })\}}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(X_{\alpha })\}}>1-\varepsilon {\tag{10}} \end{equation}$$

and

$$\begin{equation} \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(X_{\alpha })\}}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(X_{\alpha })\}}>\frac{1}{2}-\frac{\varepsilon }{2}. {\tag{11}} \end{equation}$$

Since $X_{\alpha }$ is uniquely ergodic, we can choose $N\in \mathbb{N}$ such that for any $m\geq N$ and any word $w\in \mathcal{L}_{n-1}(X_{\alpha })\cup \mathcal{L}_{n}(X_{\alpha })$ and any word $u\in \mathcal{L}_m(X_{\alpha })$, we have

$$\begin{equation} \left|\frac{\#\text{ of occurrences of $w$ as a subword of $u$}}{|u|}-\nu ([w]_0^+)\right|<\varepsilon \cdot \nu ([w])/3 {\tag{12}} \end{equation}$$

(here we use the fact that $X_{\alpha }$ is minimal and so $\nu ([w])>0$). Since $X_{\alpha }$ is Sturmian, we have $P_{X_{\alpha }}(\ell )=\ell +1$ for all $\ell \in \mathbb{N}$. Equivalently, this means that $P_{X_{\alpha }}(\ell +1)=P_{X_{\alpha }}(\ell )+1$ for all $\ell \in \mathbb{N}$. In particular, for all $\ell$ there is a unique word $w_{\ell }\in \mathcal{L}_{\ell }(X_{\alpha })$ for which both $w_{\ell }0$ and $w_{\ell }1$ are elements of $\mathcal{L}_{\ell +1}(X_{\alpha })$. Let $w\in \mathcal{L}_{n}(X_{\alpha })$ be the unique word of length $n$ with this property and let $\tilde{w}\in \mathcal{L}_N(X_{\alpha })$ be the unique word of length $N$ with this property. Note that for any $m\geq N$, the unique word $u\in \mathcal{L}_m(X_{\alpha })$ with this property has $w$ as its rightmost subword of length $n$ and $\tilde{w}$ as its rightmost subword of length $N$. (Note that we refer to subwords as being right or left in another word, where this is meant in the natural sense of ordering: a subword $a$ is the rightmost subword of the word $b$ if $b=ca$ for some word $c$, with the analogous interpretation for other directional indicators.)

Since $X_{\alpha }$ is minimal and not periodic, all sufficiently long words in $\mathcal{L}(X_{\alpha })$ contain every word of length $|\tilde{w}|+1$ (which is $N+1$) as a subword and there is a uniform gap $g$ (which depends only on $N$) between consecutive occurrences of any word in $\mathcal{L}_{N+1}(X_{\alpha })$, and by assuming that we consider sufficiently long words, we can also assume that none of the words has period at most $|\tilde{w}|$. Let $m\geq N(1+\varepsilon )+3g+3|\tilde{w}|$ be sufficiently large such that this holds (thus we have a uniform gap between occurrences of any word in $\mathcal{L}_{N+1}(X_{\alpha })$ and no words of length $m$ have period at most $|\tilde{w}|$) and such that the unique word $u\in \mathcal{L}_m(X_{\alpha })$ for which both $u0$ and $u1$ are in $\mathcal{L}_{m+1}(X_{\alpha })$ has this property. Then the rightmost subword of $u$ of length $|\tilde{w}|$ is $\tilde{w}$ and there is an occurrence of $\tilde{w}0$ within distance $g$ of the left edge of $u$. Define $a$ to be the subword of $u$ that begins with the leftmost occurrence of $\tilde{w}0$ and ends just before the rightmost occurrence of $\tilde{w}$ (meaning we remove the rightmost $N=|\tilde{w}|$ letters of $u$ to obtain the end of the word $a$). Note that $|a|\geq \max \{2g+2|\tilde{w}|,N(1+\varepsilon )\}\geq \max \{2g+2|\tilde{w}|,N\}$ and so 12 holds for all words in $\mathcal{L}_{|\tilde{w}|}(X_{\alpha })$ and $u=a$ (because its length is at least $N$). Since $|a|\geq 2g+2|\tilde{w}|\geq 2g$, every word in $\mathcal{L}_{|\tilde{w}|}(X_{\alpha })$ occurs as a subword of $a$. Moreover every subword of $aa$ of length $|\tilde{w}|$ is an element of $\mathcal{L}(X_{\alpha })$, since $a\tilde{w}0\in \mathcal{L}_{|a\tilde{w}0|}(X_{\alpha })$ and the leftmost subword of length $|\tilde{w}0|$ in $a$ is $\tilde{w}0$. Since $X_{\alpha }$ is aperiodic, there exists an integer $e$ such that

$$\begin{equation*} \underbrace{aa\cdots a}_{e\text{ times}}\notin \mathcal{L}(X_{\alpha }), \end{equation*}$$

and assume that $e$ is sufficiently large such that no word of length $|a|$ can be concatenated with itself $e$ times and still be in $\mathcal{L}(X_{\alpha })$. Set

$$\begin{equation*} A\coloneq \underbrace{aa\cdots a}_{2e+1\text{ times}}. \end{equation*}$$

Let $k \geq 3|A|+3g+3|\tilde{w}|$ and let $v\in \mathcal{L}_{k}(X_{\alpha })$ be the unique word for which both $v0$ and $v1$ are elements of $\mathcal{L}_{k+1}(X_{\alpha })$. Since $k\geq 2g+|\tilde{w}|$, every element of $\mathcal{L}_{|\tilde{w}|+1}(X_\alpha )$ occurs as a subword of $v$. Let $b$ be the subword of $v$ that begins at the leftmost occurrence of $\tilde{w}1$ and ends just before the rightmost occurrence of $\tilde{w}$. Then $|b|\geq \max \{2g+2|\tilde{w}|,3|A|\}\geq \max \{2g+2|\tilde{w}|,N(1+\varepsilon )\}\geq \max \{2g+2|\tilde{w}|,N\}$ and so 12 holds for the word $w$ when taking $u=b$. Since $|b|\geq |g|+|\tilde{w}|$, every word in $\mathcal{L}_{N}(X_{\alpha })$ occurs as a subword of $b$, Moreover, every subword of length $N$ that occurs in $ab$, $ba$, and $bb$ is in $\mathcal{L}_{N}(X_{\alpha })$, since $a\tilde{w}1,b\tilde{w}0, b\tilde{w}1\in \mathcal{L}(X_{\alpha })$, the leftmost subword of $a$ is $\tilde{w}0$, and the leftmost subword of $b$ is $\tilde{w}1$. Finally we define two words:

$$\begin{eqnarray*} x&\coloneq &\underbrace{AA\cdots A}_{|b|\text{ times}}, \\ y&\coloneq &\underbrace{bb\cdots b}_{|A|\text{ times}}. \end{eqnarray*}$$

By construction both of these words are periodic and we let $p$ denote the minimal period of $x$ and let $q$ denote the minimal period of $y$. These words have the following properties:

(1)

$|x|=|y|$;

(2)

$A$ does not occur as a subword of $y$. Namely since $b\in \mathcal{L}(X_{\alpha })$, $|b|>|A|$, and so an occurrence of $A$ would occur as a subword of $bb$. Since the word $A = aa\cdots a$ repeated $2e+1$ times and so an occurrence of $A$ in $bb$ would force the word $aa\cdots a$ (repeated $e$ times) to occur as a subword of $b$, contradicting the fact that $aa\cdots a$ (repeated $e$ times) is not in $\mathcal{L}(X_\alpha )$;

(3)

$x$ does not occur as a subword of $yy$ (because $|y|\geq 3|A|$ and if $x$ occurred in $yy$ it would force an occurrence of $A$ in $y$);

(4)

$y$ does not occur as a subword of $xx$ (again because such an occurrence would force an occurrence of $A$ in $y$);

(5)

$x$ occurs exactly once as a subword of $xy$. To check this, note that $x$ cannot overlap $y$ by $|A|$, or more, symbols without forcing an occurrence of $A$ in $y$. So an occurrence of $x$ (the word) must overlap $x$ (the leftmost subword of $xy$) on more than $|A|\geq 2p$ symbols. This means that the occurrence of $x$ (the word) has to be offset from the beginning of $xy$ by a multiple of $p$. If this occurrence of $x$ overlaps $y$ by at least $|\tilde{w}0|$ many symbols, then since $|x|$ is a multiple of $p$ (where $|x|$ is the length of the leftmost $x$ in $xy$), and $x$ (now the hypothetical nontrivial occurrence of $x$ in $xy$) is offset from the beginning of $xy$ by a multiple of $p$, this implies that the leftmost $|\tilde{w}0|$ letters of $y$ must agree with the leftmost $|\tilde{w}0|$ letters of $x$. But $x$ begins with the word $\tilde{w}0$ and $y$ begins with the word $\tilde{w}1$, a contradiction. This means that $x$ (the subword) overlaps $y$ on at most $|\tilde{w}|$ symbols. and so this occurrence of $x$ is offset from the beginning of $xy$ by at most $|\tilde{w}|$ symbols, which implies that $p\leq |\tilde{w}|$. But $x$ is the concatenation of copies of $a$ and the length $|a|>2|\tilde{w}|$, and so $a$ has period bounded by the length $|\tilde{w}|$. Since $a\in \mathcal{L}_m(X_\alpha )$, we have a contradiction since no word this long in this language (by definition of $m$) has period less than or equal to the length $|\tilde{w}|$.

Thus we cannot have both $\tilde{w}0$ and $\tilde{w}1$ occurring as subwords of $x$, contradicting the fact that $A$ is a subword of $x$, $a$ is a subword of $A$, and every word in $\mathcal{L}_{|\tilde{w}|+1}(X_\alpha )$ occurs as a subword of $a$.

Next we define two more words, $s$ and $t$, as follows:

$$\begin{eqnarray*} s&\coloneq &xxyxx; \\ t&\coloneq &xxyyx. \end{eqnarray*}$$

Note that all of the words $ss$, $st$, $ts$, and $tt$ contain $xxxy$ at least once as a subword. Consider where such a subword could occur:

$$\begin{eqnarray*} ss&\coloneq &xxyxxxxyxx; \\ st&\coloneq &xxyxxxxyyx; \\ ts&\coloneq &xxyyxxxyxx; \\ tt&\coloneq &xxyyxxxyyx. \end{eqnarray*}$$

We analyze where it can occur in $ss$, and the analysis for the other three cases is similar. Since $y$ does not occur as a subword of $xx$, the prefix $xxx$ (in $xxxy$) cannot completely overlap the leftmost $y$ in $ss$. This means that the farthest to the left that this prefix can occur is if it begins one letter after the beginning of the leftmost $y$ in $ss$. But since the word $y$ in $xxxy$ cannot be completely contained in the central $xxxx$ of $ss$, the farthest to the left $xxxy$ can occur in $ss$ is to have the $y$ at least partially overlap the rightmost $y$ in $ss$. Also, since the only place in $xy$ that $x$ can occur is at the leftmost edge, the $y$ in $xxxy$ cannot occur anywhere farther to the right in $ss$ than the rightmost $y$ (otherwise it would force an occurrence of $x$ in $xy$ which would guarantee that one of the subwords $xx$ in $xxxy$ exactly overlaps the rightmost $xy$ in $ss$, which is impossible since $x\neq y$). Therefore any occurrence of $xxxy$ in $ss$ must have the $y$ in $xxxy$ partially overlap the rightmost $y$ in $ss$, but not extend any farther to the right than this occurrence of $y$. If it did not exactly overlap the rightmost $y$ in $ss$, then the $x$ immediately preceding the rightmost $y$ (in $ss$) occurs in a nontrivial place within the rightmost $xy$ in $xxxy$, a contradiction.

Lemma 3.1.

Any element $z\in \{0,1\}^{\mathbb{Z}}$ that can be written as a bi-infinite concatenation of the words $s$ and $t$ can be written in a unique way as such a concatenation.

A shift with this property is sometimes known as a uniquely decipherable coded shift.

Proof.

Note that $s$ and $t$ have the same length and are not the same word. We have already noted that the word $xxxy$ occurs in each of $ss$, $st$, $ts$, and $tt$ and, moreover, it occurs exactly once in each such word. If $z$ can be written as a bi-infinite concatenation of the words $s$ and $t$, then there must be an occurrence of $xxxy$ within distance $|ss|$ of the origin. Choose a way to write $z$ as a concatenation of $s$ and $t$ and mark the locations in $\mathbb{Z}$ where this choice places the beginnings of these words. Find an occurrence of $xxxy$ within distance $|ss|$ of the origin. Since $|xxxy|<|s|=|t|$, this occurrence must be contained in one of the words $ss$, $st$, $ts$, or $tt$ that begins from our marked set of integers. But $xxxy$ occurs exactly once in any such word and its location is always exactly $4|x|$ symbols from where the word started. This allows us to determine where the marked integers in this occurrence of $ss$, $st$, $ts$, or $tt$ are located. In turn, this means that we can read off the sequence of words $s$ and $t$ that were concatenated to produce $z$ by starting from one of the marked integers and looking at blocks of size $|s|$ moving to the right and left.

Thus, once we find an occurrence of $xxxy$ within distance $|ss|$ of the origin in $z$, the locations (in $\mathbb{Z}$) where the words $s$ and $t$ begin are determined, and once these locations are determined, the bi-infinite sequence of $s$ and $t$ is also determined. In other words, there is a unique way to write $z$ as such a bi-infinite concatenation.

■

Lemma 3.2.

Let $Y\subseteq \{0,1\}^{\mathbb{Z}}$ be the subshift consisting of all elements of $\{0,1\}^{\mathbb{Z}}$ that can be written as bi-infinite concatenations of the words $s$ and $t$. Let $Z\subseteq Y$ be any subshift of $Y$ and let $\mu$ be any $\sigma$-invariant probability measure on $Z$. Recall that $n\in \mathbb{N}$ is defined in 9 and $N$ is fixed to guarantee that 12 holds. Then for any $k\leq N$ we have $\mathcal{L}_k(Z)=\mathcal{L}_k(X_{\alpha })$ and we have

$$\begin{equation*} \frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}>1-2\varepsilon \end{equation*}$$

and

$$\begin{equation*} \frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}}>\frac{1}{2}-\varepsilon . \end{equation*}$$

Proof.

By construction of the words $a$ and $b$ (from which $s$ and $t$ are built), the claim about equality of the languages holds because $|a|,|b|>n$ and every subword of length $N$ that occurs in any of $aa$, $ab$, $ba$, or $bb$ is in the language $\mathcal{L}_N(X_{\alpha })$. To see the claim about measure, by the ergodic decomposition theorem it suffices to show the analogous claim holds when $\mu$ is replaced by any ergodic measure supported on $Z$. Let $c\in \mathcal{L}_n(Z)\cup \mathcal{L}_{n-1}(Z)=\mathcal{L}_n(X_{\alpha })\cup \mathcal{L}_{n-1}(X_{\alpha })$ be fixed. Fix an ergodic measure $\zeta \in \mathcal{M}(Z)$ and fix a generic element $z\in Z$. Let $\mathbf{1}_{[c]}(\cdot )$ denote the indicator function of the cylinder set determined by $c$. Then for all sufficiently large $S$, we have

$$\begin{equation} \left|\zeta ([c])-\frac{1}{2S+1}\sum _{k=-S}^{S}\mathbf{1}_{[c]}(\sigma ^kz)\right|<\frac{\varepsilon }{3}\cdot \nu ([c]). {\tag{13}} \end{equation}$$

We know that $z$ can be parsed into an infinite concatenation of the words $a$ and $b$. Fixing $S$, there exists a subword $z_{-S}z_{-S+1}\cdots z_{S-1}z_S$ of $z$ whose length is at least $2S+1-2|a|$ that is a concatenation of the words $a$ and $b$. Let $i<j$ be the indices where this subword starts and ends. Then

$$\begin{multline*} \frac{1}{2S+1}\sum _{k=-S}^{S}\mathbf{1}_{[c]}(\sigma ^kz)= \\ \frac{1}{2S+1}\sum _{k=i}^j\mathbf{1}_{[c]}(\sigma ^kz)+\frac{1}{2S+1}\sum _{k=-S}^{i-1}\mathbf{1}_{[c]}(\sigma ^kz)+\frac{1}{2S+1}\sum _{k=j}^{S}\mathbf{1}_{[c]}(\sigma ^kz). \end{multline*}$$

The second and third of these averages tend to zero as $S\to \infty$, and so for sufficiently large $S$ we can assume they are both at most $\varepsilon \cdot \nu ([c])/12$. The first average can be rewritten as:

$$\begin{equation*} \frac{1}{2S+1}\sum _{k=i}^j\mathbf{1}_{[c]}(\sigma ^kz)=\frac{1}{2S+1}\sum _{\ell =0}^{(j-i)/|a|-1}\sum _{m=0}^{|a|-1}\mathbf{1}_{[c]}(\sigma ^{i+\ell |a|+m}z). \end{equation*}$$

Since $|a|\geq N$, $c\in \mathcal{L}_n(X_{\alpha })\cup \mathcal{L}_{n-1}(X_{\alpha })=\mathcal{L}_n(Z)\cup \mathcal{L}_{n-1}(Z)$, and since any subword of length $N$ that occurs in any of $aa$, $ab$, $ba$, and $bb$ is in the language $\mathcal{L}_N(X_{\alpha })$, then for each fixed $\ell$ we have

$$\begin{equation*} \left|\frac{1}{|a|}\sum _{m=0}^{|a|-1}\mathbf{1}_{[c]}(\sigma ^{\ell |a|+m}z)-\nu ([c])\right|<\frac{\varepsilon }{3}\cdot \nu ([c]) \end{equation*}$$

by 12. Therefore, recalling that $S$ is sufficiently large, we have that

$$\begin{equation*} \left|\frac{1}{2S+1}\sum _{k=-S}^S\mathbf{1}_{[c]}(\sigma ^kz)-\nu ([c])\right|<\frac{\varepsilon }{3}\cdot \nu ([c])+\frac{\varepsilon }{6}\cdot \nu ([c]). \end{equation*}$$

Combining this with 13, it follows that

$$\begin{equation*} |\zeta ([c])-\nu ([c])|<\frac{5\varepsilon }{6}\cdot \nu ([c]). \end{equation*}$$

By 10 and 11 we know that

$$\begin{equation*} \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}>1-\varepsilon \end{equation*}$$

and

$$\begin{equation*} \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}}>\frac{1}{2}-2\varepsilon . \end{equation*}$$

Thus we have

$$\begin{equation*} \frac{\min \{\zeta ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}{\max \{\zeta ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}}\geq \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}\cdot (1-5\varepsilon /6)}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n}(Z)\}\cdot (1+5\varepsilon /6)}>1-2\varepsilon \end{equation*}$$

since $\varepsilon <1/8$. Similarly,

$$\begin{multline*} \frac{\min \{\zeta ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}}{\max \{\zeta ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}} \\ \geq \frac{\min \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}\cdot (1-5\varepsilon /6)}{\max \{\nu ([w]_0^+)\colon w\in \mathcal{L}_{n-1}(Z)\}\cdot (1+5\varepsilon /6)}>\frac{1}{2}-\frac{\varepsilon }{2}. \quad \end{multline*}$$■

Lemma 3.3.

The shift $(Y, \sigma )$ defined in Lemma 3.2 satisfies

$$\begin{equation*} h_{top}(Y)=\log (2)/|s|>0. \end{equation*}$$

Proof.

The number of distinct words whose length $n$ is any particular multiple of $2|s|$ is at least $|s|\cdot 2^{n/|s|}$ and at most $4|s|\cdot 2^{n/|s|}$: as a word of this length must contain an occurrence of $xxxy$, this identifies how this word is parsed as a subword in the concatenation of the words $s$ and $t$ (other than perhaps the leftmost and rightmost words in the concatenation).

■

We fix a subexponentially growing sequence $\{a_n\}_{n=1}^{\infty }$. It follows from Lemma 3.3 that

$$\begin{equation} P_{Y}(m)>a_m {\tag{14}} \end{equation}$$

for all but finitely many $m\in \mathbb{N}$. Thus,

$$\begin{equation} \text{given the subexponentially growing sequence $\{a_m\}_{m=1}^{\infty }$ and a bound $B\geq |s|$,} {\tag{15}} \end{equation}$$

we can choose some $m>B$ such that $P_Y(m)>a_m$, and then fix two (distinct) words $u,v\in \mathcal{L}(Y)$, of equal length, that each contain every element of $\mathcal{L}_{m}(Y)$ as a subword and which can be written as a concatenation of the words $s$ and $t$. Finally define

$$\begin{eqnarray} 0_*&\coloneq &uuvuuvuuvvvvuuvuuvuuv{\tag{16}}\\ 1_*&\coloneq &uuvuuvuuvvvvvvvuuvuuv. {\tag{17}} \end{eqnarray}$$

Arguing as with words that can be written as bi-infinite concatenations of $s$ and $t$, observe that any element of $\{0,1\}^{\mathbb{Z}}$ that can be written as a bi-infinite concatenation of $0_*$ and $1_*$ can be written in a unique way as such a concatenation. Let $Z$ be the subshift consisting of all elements of $\{0,1\}^{\mathbb{Z}}$ that can be written as a bi-infinite concatenation of the word $0_*$ and $1_*$. Then $Z\subseteq Y$, meaning Lemma 3.2 applies to any $\sigma$-invariant probability measure on $Z$. Furthermore, by 14, we have that

$$\begin{equation} P_{Z}(|0_*|)>a_{|0_*|}. {\tag{18}} \end{equation}$$

3.2. Inflated subshifts

The subshift $Z$ constructed in the last paragraph of Section 3.1 and satisfying 18 consists of all bi-infinite concatenations of the words $0_*$ and $1_*$. In this way we can think of $Z$ has being a “full shift” on the “symbols” $0_*$ and $1_*$. Since $0_*$ and $1_*$ are actually words, rather than symbols, we prove two lemmas that show $Z$ nevertheless does have some properties that a full shift would have, such as a unique representation of every element of $Z$ as a concatenation of $0_*$ and $1_*$. In what follows, we abstract the construction so that it can then be applied in an inductive construction. Note that if the words $u$ and $v$ in Lemma 3.4 are taken to be the words $u$ and $v$ from Section 3.1, then $\beta _0$ and $\beta _1$ would be exactly the words $0_*$ and $1_*$ defined in 16 and 17.

Lemma 3.4.

Assume that $u,v\in \{0,1\}^*$ are two distinct words of equal length. Let

$$\begin{eqnarray*} \beta _0&\coloneq &uuvuuvuuvvvvuuvuuvuuv; \\ \beta _1&\coloneq &uuvuuvuuvvvvvvvuuvuuv. \end{eqnarray*}$$

Then for any $x\in \{0,1\}^{\mathbb{Z}}$ that can be written as a bi-infinite concatenation of the words $\beta _0$ and $\beta _1$, there is a unique way to write it as such a concatenation. Furthermore, for such an $x\in \{0,1\}^{\mathbb{Z}}$ and for $i\in \{0,1\}$, whenever $\beta _i$ occurs as a subword of $x$, there exists a sequence …, $j_{-2}$, $j_{-1}$, $j_0$, $j_1$, $j_2$, … such that $x$ is (a finite shift of) the sequence

$$\begin{equation} \cdots \beta _{j_{-2}}\beta _{j_{-1}}\beta _i\beta _{j_0}\beta _{j_1}\beta _{j_2}\cdots . {\tag{19}} \end{equation}$$

Proof.

Let $x\in \{0,1\}^{\mathbb{Z}}$ be such that it can be written as a bi-infinite concatenation of the words $\beta _0$ and $\beta _1$; choose some way to do this. Since $\beta _0$ and $\beta _1$ have equal length, there exists $k\in \{0,1,\dots ,|\beta _0|-1\}$ such that, when $x$ is written as a bi-infinite concatenation of $\beta _0$ and $\beta _1$, all of the concatenated words begin at indices of $x$ that are congruent to $k$ modulo $|\beta _0|$. Now fix $i\in \{0,1\}$ and suppose $\beta _i$ occurs as a subword of $x$, beginning at index $m\in \mathbb{Z}$.

If $m\equiv k\pmod {|\beta _0|}$, then we have already found the decomposition appearing in 19. We aim to show it is not possible that $m\not \equiv k\pmod {|\beta _0|}$, which implies the uniqueness of the decomposition of $x$ into a bi-infinite concatenation of $\beta _0$ and $\beta _1$ and also provides the decomposition appearing in 19. Note that our chosen way to write $x$ as a bi-infinite concatenation of $\beta _0$ and $\beta _1$ implies that there exist $m_1,m_2\in \{0,1\}$ such that $\beta _i$ arises as a subword of $\beta _{m_1}\beta _{m_2}$ in a location that is neither the leftmost nor the rightmost.

Let $p\in \{0,1\}^{\mathbb{Z}}$ be the periodic word

$$\begin{equation*} p\coloneq \cdots uuvuuvuuvuuvuuv\cdots . \end{equation*}$$

Then $|uuv|$ is a period of $p$. We claim it is the minimal period of $p$. To see this, note that the minimal period of $p$ must divide $|uuv|$. If the minimal period of $p$ is $\frac{1}{2}|uuv|$, then the leftmost subword of length $\frac{1}{2}|u|$ occurring in $u$ is equal to the rightmost subword of $u$ and the period of $p$ implies that $u=v$, a contradiction. If the minimal period of $p$ is $\frac{1}{3}|uuv|$, then it is immediate that $u=v$ and again we have a contradiction. Therefore the minimal period of $p$ is at most $\frac{1}{4}|uuv|$. The minimal period of $p$ is also a period of the word $uu$, but since $|u|$ is also a period of $uu$, the Fine-Wilf Theorem 8 implies that the minimal period of $p$ divides $|u|$. Therefore $u=v$ and we have a contradiction. Thus, the minimal period of $p$ is $|uuv|$.

Now, $\beta _i$ occurs as a subword of $\beta _{m_1}\beta _{m_2}$ in a location that is neither the leftmost nor the rightmost. This occurrence of $\beta _i$ overlaps at least one of $\beta _{m_1}$ and $\beta _{m_2}$ (in their obvious positions within $\beta _{m_1}\beta _{m_2}$) on at least $\frac{1}{2}|\beta _0|$ letters. We analyze the case when $\beta _i$ overlaps $\beta _{m_1}$ on at least $\frac{1}{2}|\beta _0|$ of its letters (the other case is similar). Note that $\beta _0$ and $\beta _1$ are both comprised of seven blocks of length $|uuv|$ and both start with $uuvuuvuuv$ and end with $uuvuuv$. In between these common prefixes and suffixes, $\beta _0$ has the block $vvv$ followed by $uuv$ and $\beta _1$ has the block $vvvvvv$. In both of these words, we refer to the word $vvv$ and $vvvvvv$, respectively, as their “block of $v$’s.” Note that the word $\beta _{m_1}\beta _{m_2}$ contains the word $(uuv)^5$ ($uuv$ self-concatenated five times) beginning to the right of the block of $v$’s in $\beta _{m_1}$. The block of $v$’s in $\beta _i$ does not occur as a subword of $(uuv)^5$: namely, since we have shown that the minimal period of $(uuv)^5$ is $|uuv|=|vvv|$, and since the minimal period of $vvv$ is $|v|$ which is a proper divisor of $|uuv|$, the word $vvv$ cannot occur as a subword of $(uuv)^5$. In fact, in the case that $i=1$, the rightmost $vvv$ in $vvvvvv$ does not occur in $(uuv)^5$ and so the location where $\beta _i$ occurs in $\beta _{m_1}\beta _{m_2}$ is far enough to the left that the block of $v$’s in $\beta _i$ extends by at most $|vvv|-1$ to the right of the block of $v$’s in $\beta _{m_1}$. This means the suffix $uuvuuv$ in $\beta _i$ completely overlaps (meaning it contains the occurrence of) the suffix $uuvuuv$ in $\beta _{m_1}$. Since the minimal period of $uuvuuv$ is $|uuv|$, this guarantees that the word $\beta _i$ appears in $\beta _{m_1}\beta _{m_2}$ a multiple of $|uuv|$ letters from the left. If it appears exactly $|uuv|$ letters from the left, then the leftmost $vvv$ in the block of $v$’s of $\beta _{m_1}$ overlaps the word $uuv$ in $\beta _i$, implying that $u=v$ and we have a contradiction. Otherwise the leftmost $vvv$ in the block of $v$’s of $\beta _i$ appears as a subword of $(uuv)^5$ in $\beta _{m_1}\beta _{m_2}$, again implying that $u=v$ and a contradiction. Therefore $\beta _i$ cannot have occurred in $\beta _{m_1}\beta _{m_2}$ in any location other than the leftmost or the rightmost.

■

Lemma 3.5 shows that if we pick a subshift $W\subseteq \{0,1\}^{\mathbb{Z}}$ which has desirable ergodic properties, and “inflate” it by making the replacements $0\mapsto 0_*$, $1\mapsto 1_*$ and taking the orbit closure of all elements of $\{0,1\}^{\mathbb{Z}}$ obtained in this way, then the “inflated” shift also has desirable ergodic properties.

Lemma 3.5.

Let $W\subseteq \{0,1\}^{\mathbb{Z}}$ be a subshift. Assume there exist an integer $m>3$ and a positive constant $C_1$ such that for any ergodic measure $\eta$ supported on $W$, we have

$$\begin{equation} C_1<\frac{\min \{\eta ([w]_0^+)\colon w\in \mathcal{L}_m(W)\}}{\max \{\eta ([w]_0^+)\colon w\in \mathcal{L}_m(W)\}}. {\tag{20}} \end{equation}$$

Assume that $u,v\in \{0,1\}^*$ are two distinct words of equal length and set

$$\begin{eqnarray*} \beta _0&\coloneq &uuvuuvuuvvvvuuvuuvuuv; \\ \beta _1&\coloneq &uuvuuvuuvvvvvvvuuvuuv. \end{eqnarray*}$$

Let $X\subseteq \{0,1\}^{\mathbb{Z}}$ be the subshift consisting of all elements of $\{0,1\}^{\mathbb{Z}}$ that can be written as a bi-infinite concatenation

$$\begin{equation*} \cdots \beta _{i_{-2}}\beta _{i_{-1}}\beta _{i_0}\beta _{i_1}\beta _{i_2}\cdots , \end{equation*}$$

where $(\dots ,i_{-2},i_{-1},i_0,i_1,i_2,\dots )\in W$. If $\mu$ is any ergodic measure supported on $X$, then

$$\begin{equation*} \frac{C_1^2}{4}<\frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{|\beta _0|\cdot (m-1)}(X)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{|\beta _0|\cdot (m-1)}(X)\}}. \end{equation*}$$

Proof.

Let $z\in W$ be any fixed element and let $w\in \mathcal{L}_m(W)$. Then

$$\begin{eqnarray} \frac{C_1}{P_W(m)}&\leq &\min \{\eta ([w]_0^+)\colon \eta \text{ is an ergodic measure supported on $W$}\} \\ &=&\min \{\eta ([w]_0^+)\colon \eta \text{ is an invariant measure supported on $W$}\} \\ &\leq &\liminf _{n\to \infty }\frac{1}{n}\sum _{k=0}^{n-1}1_{[w]_0^+}(\sigma ^kz). {\tag{21}} \end{eqnarray}$$

Let $\mu$ be an ergodic measure supported on $X$ and let $x\in X$ be a generic point for the measure $\mu$. Choose $u_1,u_2\in \mathcal{L}_{(m-1)|\beta _0|}(X)$ such that

$$\begin{equation*} \mu ([u_1]_0^+)=\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{(m-1)|\beta _0|}(X)\} \end{equation*}$$

and

$$\begin{equation*} \mu ([u_2]_0^+)=\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{(m-1)|\beta _0|}(X)\}. \end{equation*}$$

Since $\mu$ is ergodic,

$$\begin{equation*} \mu ([u_1]_0^+)=\lim _{n\to \infty }\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{1}_{[u_1]_0^+}(\sigma ^kx) \end{equation*}$$

and

$$\begin{equation*} \mu ([u_2]_0^+)=\lim _{n\to \infty }\frac{1}{n}\sum _{k=0}^{n-1}\mathbf{1}_{[u_2]_0^+}(\sigma ^kx). \end{equation*}$$

We analyze occurrences of $u_1$ in $x$, noting that the same analysis applies for occurrences of $u_2$. Any occurrence of $u_1$ in $x$ occurs in a concatenation of the words $\beta _0$ and $\beta _1$, some number of times. Since $m\geq 4$ and $|u_1|=(m-1)|\beta _0|$, whenever $u_1$ occurs it must completely contain at least one of the words $\beta _0\beta _0$, $\beta _0\beta _1$, $\beta _1\beta _0$, or $\beta _1\beta _1$ as a subword.

Any occurrence of $u_1$ in $x$ occurs in a concatenation of $m$ words which are all $\beta _0$ and $\beta _1$. Since $m\geq 4$, at least two of these concatenated words occur as a subword of $u_1$ and so the location of $u_1$ in the concatenation the words $\beta _0$ and $\beta _1$ is uniquely determined by Lemma 3.4. Thus each occurrence of $u_1$ occurs either as an exact concatenation of $m-1$ many of the words $\beta _0$ and $\beta _1$, or as a subword of a concatenation of exactly $m$ of the words $\beta _0$ and $\beta _1$ (which is neither the leftmost nor rightmost subword of length $|u_1|$) and all but (perhaps) the first and last of the words $\beta _0$ and $\beta _1$ can be determined from the word $u_1$. In the first case, when $u_1$ is itself an exact concatenation of $m-1$ of the words $\beta _0$ and $\beta _1$, we adopt the convention of viewing it as a subword of the concatenation of $m$ many of $\beta _0$ and $\beta _1$ by appending the extra $\beta _0$ or $\beta _1$ onto its right when it occurs. Therefore there are at most four ways to concatenate the words $\beta _0$ and $\beta _1$ such that $u_1$ occurs as a subword, corresponding to the ambiguity of the edge (first and last) concatenated words and that there are at most two choices for each of these edge words, or the ambiguity of the rightmost word when $u_1$ is an exact concatenation of $m-1$ of the words $\beta _0$ and $\beta _1$. This means that the asymptotic frequency with which $u_1$ occurs as a subword of $x$ is $1/|\beta _0|$ times the sum of the measures of the cylinder sets of length $m$ (in the shift $W$) that determine occurrences of $u_1$ in $X$. But by 21, the frequency with which this cylinder set of length $m$ occurs (in $W$) is at most $1/C_1P_W(m)$. Therefore

$$\begin{equation*} \mu ([u_1]_0^+)\leq 4/(C_1P_W(m)\cdot |\beta _0|). \end{equation*}$$

Similarly we have

$$\begin{equation*} \mu ([u_2]_0^+)\geq C_1/(P_W(m)\cdot |\beta _0|), \end{equation*}$$

where this time there is at least one word which is a concatenation of exactly $m$ many of the words $\beta _0$ and $\beta _1$ that imply an occurrence of $u_2$. Therefore, we have

$$\begin{equation*} \frac{C_1^2}{4}<\frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{|\beta _0|\cdot (m-1)}(X)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{|\beta _0|\cdot (m-1)}(X)\}}.\quad \end{equation*}$$■

3.3. Induction

Let $\{a_m\}_{m=1}^{\infty }$ be a subexponentially growing sequence of positive integers, meaning

$$\begin{equation*} \limsup _{m\to \infty }\frac{1}{m}\log a_m=0. \end{equation*}$$

We inductively construct a sequence of shifts $U_1$, $U_2$, $U_3$, …and ultimately define our subshift $Y$ from Theorem 1.1. Let $n_1\in \mathbb{N}$ be the smallest integer that satisfies 8 and let, by taking $n=n_1$ in 9, $U_1\subseteq \{0,1\}^{\mathbb{Z}}$ be the subshift constructed at the end of Section 3.1 (where it was called $Z$). Let $N$ be the parameter arising in Section 3.1 and let $0_1$ and $1_1$ be the words defined in Equations 16 and 17 constructed from the sequence $\{m\cdot a_m\}_{m=1}^{\infty }$ and $B\geq N$ in 15 and let $N_1\geq B$ be the parameter $m$ in the sentence following 15. Then we have $P_{U_1}(N_1)>N_1\cdot a_{N_1}$.

Now suppose we have constructed a nested sequence of subshifts

$$\begin{equation*} U_1\supseteq U_2\supseteq U_3\supseteq \cdots \supseteq U_k, \end{equation*}$$

a sequence of positive integers $n_1<N_1<n_2<N_2<\cdots <n_k<N_k$, and a sequence of words $0_1$, $1_1$, $0_2$, $1_2$, …, $0_k$, $1_k$ where $0_i$, $1_i\in \mathcal{L}(U_i)$ are two distinct words of equal length (and this common length is at least $N_k$). We suppose that for each $i\leq k$, $U_i$ is the subshift obtained by taking all possible bi-infinite concatenations of the words $0_i$ and $1_i$. Suppose further that for any $i\leq k$ and any $j\leq i$ we have $P_{U_i}(N_j)>N_j\cdot a_{N_j}$ and

$$\begin{equation*} \frac{1}{16}<\frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(U_i)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(U_i)\}}<1 \end{equation*}$$

for any ergodic measure $\mu$ supported on $U_i$. Take $n_{k+1}>|0_k|$ to be an integer satisfying 8 and let $N_{k+1} = |0_*|$ when $n$ is chosen to be $n_{k+1}$ in 9. We produce the subshift $Z$, constructed in Section 3.1 and the words $0_*$ and $1_*$ with this choice of $n$. Next, we apply Lemma 3.5 with $W=Z$, $m=n_{k+1}$, $C_1=1/4$, $u=0_k$, and $v=1_k$ to produce a new subshift $X$. Note that since $Z$ consisted of all possible concatenations of $0_*$ and $1_*$, it follows that $X$ consists of all possible concatenations of the “inflated” versions of the words $0_*$ and $1_*$, where $0\mapsto 0_k$ and $1\mapsto 1_k$. We define $0_{k+1}$ and $1_{k+1}$ to be the words $0_*$ and $1_*$ after this replacement is applied. Note that every element of $U_{k+1}$ can be written as a bi-infinite concatenation of $0_k$ and $1_k$, and so $U_{k+1}\subseteq U_k$.

Note that since $N_{k+1} = |0_*|$, by Equation 18 and taking $b_n =na_n$, we have guaranteed that $P_{X_{k+1}}(N_j)\geq N_ja_{N_j}$ for all $j\leq k+1$. Finally, by Lemmas 3.2 and 3.5, we have

$$\begin{equation*} \frac{1}{64}<\frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(U_{k+1})\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(U_{k+1})\}} \end{equation*}$$

for all $j\leq k+1$.

Finally, define

$$\begin{equation*} Y\coloneq \bigcap _{k=1}^{\infty } U_k. \end{equation*}$$

Then since the subshifts are nested, $Y$ is nonempty. Since each pattern occurs syndetically, the system $Y$ is minimal. Finally, by construction, we obtain a subshift satisfying $P_Y(N_j)>N_ja_{N_j}$ for all $j\in \mathbb{N}$, in particular

$$\begin{equation*} \limsup _{n\to \infty }\frac{P_Y(n)}{a_n}=\infty , \end{equation*}$$

and such that

$$\begin{equation*} \frac{1}{64}<\frac{\min \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(Y)\}}{\max \{\mu ([w]_0^+)\colon w\in \mathcal{L}_{n_j}(Y)\}} \end{equation*}$$

for all $j\in \mathbb{N}$. This concludes the proof of Theorem 1.1.