1. S-gap shifts
S-gap shifts are a useful example for studying dynamics of shift spaces that are not subshifts of finite type but still exhibit some strong mixing properties. They are defined as follows: given , let be the set of all words on two symbols of the form — that is, 0s followed by a single 1. (Edit 8/2/15: As Steve Kass pointed out in his comment, we need to specify here that .) Then let be the set of all bi-infinite sequences of 0s and 1s that can be written as an infinite concatenation of words in , and let be the smallest closed shift-invariant set containing .
Equivalently, is the collection of bi-infinite sequences for which every subword of the form has . If is finite then is a shift of finite type. We are usually most interested in the case where is infinite — for example, in this paper (arXiv) where Dan Thompson and I considered questions of uniqueness of the measure of maximal entropy. For purposes of this post, may be finite or infinite, it will not matter.
Recall that if denotes the set of words of length that appear somewhere in the shift , then the topological entropy of is . The following result is well-known and often quoted.
Note that when , the -gap shift is the full shift on two symbols, and the equation has solution .
Despite the fact that Theorem 1 is well-known, I am not aware of a complete proof written anywhere in the literature. In a slightly different language, this result already appears in B. Weiss’ 1970 paper “Intrinsically ergodic systems” [Bull. AMS 76, 1266–1269] as example 3.(3), but no details of the proof are given. It is exercise 4.3.7 in Lind and Marcus’ book “Symbolic dynamics and coding”, and the section preceding it gives ideas as to how the proof may proceed. Finally, a more detailed proof appears in Spandl’s “Computing the topological entropy of subshifts” [Math. Log. Quart. 53 (2007), 493–510], but there is a gap in the proof. The goal of this post is to explain where the gap in Spandl’s proof is, and then to give two other proofs of Theorem 1, one more combinatorial, the other more ergodic theoretic.
2. An incomplete proof
Moreover, every is either or is of the form for some , so . With a little more work, one can use this together with (1) to get
Writing , Spandl now says that is asymptotically proportional to , and so for each the ratio inside the sum converges to as . Since is subexponential, this would prove Theorem 1.
The problem is that the ratio may not converge as . Indeed, taking it is not hard to show that when is even, the limit taken along odd values of differs from the limit taken along even values of .
One might observe that in this specific example, the terms where is even do not contribute to the sum in (2), since contains no even numbers. Thus it is plausible to make the following conjecture.
Conjecture. For any , let and let be the topological entropy of the corresponding -gap shift. Then for every the limit
exists. In particular, if then
If the conjecture is true, this would complete Spandl’s proof of Theorem 1. I expect that the conjecture is true but do not know how to prove it. In general, any shift space with entropy has the property that . There are examples of shift spaces where is not bounded above; however, it can be shown that every -gap shift admits an upper bound, so that is bounded away from 0 and (this is done in my paper with Dan Thompson). I don’t see how those techniques can extend to a proof of the conjecture.
So instead of patching the hole in this proof, we investigate two others.
3. A combinatorial proof
Given a shift space with language , let be the number of words of length . Consider the following generating function:
(This is similar to the dynamical zeta function but is somewhat different since we consider all words of length and not just ones that represent periodic orbits of period .) Observe that the radius of convergence of is . Indeed, for we can put and observe that the quantity decays exponentially; similarly, for the terms in the sum grow exponentially.
Now fix an -gap shift and consider the function
Our goal is to find a relationship between and allowing us to show that the radius of convergence of is given by the positive solution to .
First recall the set . Given integers , let be the number of words in that can be written as a concatenation of exactly words from . Note that , so that
More generally, we consider the power series
A little thought reveals that , since the coefficient of in is given by
which is equal to (here represents the location where the th element of ends). In particular, we get
At this point, the natural thing to do is to say that and hence . However, this is not quite correct because includes words that are not complete concatenations of words from and so are not counted by any . We return to this in a moment, but first point out that if this were true then we would have , and so converges if and diverges if , which was our goal.
To make this precise, we observe that every word in is either or is of the form where for some . Thus we have the bounds
Writing , we note that for every we have and so converges if and only if converges. Thus and have the same radius of convergence; in particular, the radius of convergence of is the unique such that , and by the earlier discussion we have , proving Theorem 1.
4. An ergodic theory proof
Now we sketch a proof that goes via the variational principle, relating an -gap shift (on the finite alphabet ) to a full shift on a (possibly countable) alphabet. The combinatorial proof above is elementary and requires little advanced machinery; this proof, on the other hand, requires a number of (rather deep) results from ergodic theory and thermodynamic formalism, but has the advantage of illuminating various aspects of the structure of -gap shifts.
Let be an -gap shift and let be the set of sequences which contain the symbol 1 infinitely often both forwards and backwards. By the Poincaré recurrence theorem, for every ergodic measure other than the delta-measure on the fixed point . Note that is -invariant but not compact (unless is finite).
Let , and let be the first return map. Thus for all . Note that is topologically conjugate to the full shift on the alphabet , which we allow to be finite or countable. The conjugacy is given by that takes to .
Given an ergodic -invariant probability measure on with , let be the induced -invariant measure on . Then by Abramov’s formula, we have
Associate to each the shift-invariant measure on given by . Then we have
Our goal is to relate the topological entropy on to the topological pressure of a suitable function on . Let be the function taking to , and observe that if and are identified as above, we have , so that
At this point we elide some technical details regarding Gurevich pressure, etc., and simply remark that for we have
while by the variational principle
Let be such that the right-hand side is equal to 0; to prove Theorem 1 we need to prove that . First observe that for every we have , thus . For the other inequality, let be the Bernoulli measure on that assigns weight to the symbol . Then is an equilibrium state for on , and by our choice of , we have
so that in particular the left hand side of (4) vanishes and we get for the measure that corresponds to . This shows that and completes the proof of the theorem.
We note that this proof has the advantage of giving an explicit description of the MME. With a little more work it can be used to show that the MME is unique and has good statistical properties (central limit theorem, etc.).