Given , the interval map given by is naturally semi-conjugate to the -shift . The shift space admits a natural description in terms of the lexicographic order, and another in terms of a countable-state directed graph. These have been used to obtain a fairly complete description of the dynamics of the -transformation , including existence, uniqueness, and strong statistical properties of equilibrium states for Hölder potentials.
In this post I want to explain how one can give similar descriptions (both in terms of lexicographic order and in terms of a countable-state Markov structure) for the coding spaces associated to the interval map . Just as with the -shifts, these “– shifts” arise from piecewise expanding interval maps, and thus can be studied using the general machinery developed by Hofbauer, but I believe that they are worth studying a little more carefully as an intermediate case between the -shifts, where the fact that is a `safe symbol’ can be used to prove various results that are still open for – shifts, and the more general setting where the description of the shift space requires more bookkeeping and it can be harder to see what is going on.
1. Coding spaces for interval maps
We start by recalling the general notion of a coding space for a map of the interval. Say that a map is a piecewise expanding interval map if there is and a partition of into finitely many intervals such that is continuous on each and on the interior of each , with . Note that we do not care whether the intervals are closed, open, or half of each.
Let , and define a map by whenever . Let ; we say that is the coding space for the interval map relative to the partition . We can define a map by the condition that for all and is continuous. Then we have , so is a semiconjugacy between and .
Another way of interpreting this is the following: for each there is a unique map such that for all in the interior of . Note that is with . Given any set , write for convenience; note that if does not intersect . Given a finite word , let , where and is the length of . Roughly speaking, represents the set of points for which , , and so on. (This is not quite completely true because of problems at the endpoints of the intervals.)
The language of the shift is the set of all such that . Write for this collection of words; then , and we have for all . Let ; given , the interval has length , and since for every we have , we also have .
So far these considerations have been completely general, valid for any piecewise expanding interval map. Now we consider the specific transformations and , where and we assume without loss of generality that . These are piecewise expanding interval maps, where the natural partition to consider is the partition into maximal intervals of continuity. Thus for , we have , , and so on, with , where . For , we have , , and so on, with and . We write and for the coding spaces of these transformations relative to their natural partitions.
2. Description via lexicographic order
The full shift carries a natural lexicographic order inherited from the usual order on : given , let be minimal such that , and write if . Write if or . This is a total order on . The key observation for our purposes is that because and are order-preserving on each of their intervals of continuity, their coding maps are also order-preserving in the sense that if and only if . (Note that we must use non-strict inequalities because the coding maps are not 1-1.)
2.1. The -shifts
Fix and let . Let , where supremum is w.r.t. lexicographic order; the supremum exists because has the least upper bound property, and is in because the -shift is closed. Thus is the lexicographically maximal element of ; it would code the trajectory of the right endpoint of the unit interval if we replaced with the map , which agrees with everywhere except at the endpoints of the intervals of monotonicity. The points will play an important role in the following result.
To prove the converse direction, it suffices to show that every which satisfies (2) is contained in ; in other words, that for every such . Equivalently, we can work with the following object: consider for each the follower interval ; this can also be defined as the minimal interval with the property that . Note that whenever . Given and , observe that
be the length of the longest prefix of that appears as a suffix of .
Lemma 2 If satisfies (2), then .
Proof: We go by induction in the length of , using (so is the empty word and ) as the base case. Suppose we have some satisfying (2), and that the lemma has been proved for all words with length . Write where and . Let , so that for some word . By the inductive hypothesis, we have and hence . Then by (3), we have
There are two cases to consider.
Case one: . In this case we have and , and .
where the last inequality uses the fact that . We conclude that , which completes the proof of Lemma 2.
A historical note: the transformation was introduced by Rényi in 1957 to study representations of real numbers in non-integer bases. The lexicographic characterization of -shifts in Proposition 1 was given by Parry in 1960 (see Theorem 3 of that paper) using different methods than the proof here. This proof is essentially the same as the one given by Hofbauer in 1979 (see Theorem 2 there); Hofbauer’s approach has the advantage of dealing with all piecewise monotonic interval maps, and the argument given here for the -shift is actually just a special case of his general result.
2.2. The – shifts
Instead of describing the full generality of Hofbauer’s result here, we describe how Proposition 1 adapts to the – shifts. This family of examples already reveals some of the challenges that arise when we go from -shifts to more general piecewise expanding transformations.
As with the -shifts, these conditions are both necessary and sufficient for membership in and . The key to proving this is the following analogue of Lemma 2, whose proof we omit since it is similar to the proof there (with just a little more bookkeeping).
Lemma 3 Given satisfying (6), let
Then , where and agree with on the interiors of the intervals , and are defined at the endpoints by the condition that is continuous from the right and is continuous from the left.
3. A directed graph on
The lexicographic description of in Proposition 1 is appealing, but for many purposes it is more useful to have a description of the -shift in terms of a countable-state directed graph, which goes back to work of Takahashi in 1973 and Hofbauer in 1978.
Start by considering the notion of follower set in a shift space, which is analogous to the follower intervals considered in the previous part. Given a shift space with language , consider for each the follower set
One could also consider the set of words such that , but the definition in (8) will be more convenient for our purposes. It was shown by Weiss in 1973 that a shift can be represented via a labeled directed graph on finitely many vertices if and only if it has finitely many follower sets; that is, if is finite. Such shifts are called sofic. Similarly, can be represented via a labeled irreducible directed graph on countably many vertices if and only if it has countably many follower sets, and such shifts are called coded; see Fiebig and Fiebig 1992 and 2002.
Every -shift is characterized by a sequence with the property that for all : as we saw in Proposition 1, we have
Moreover, it follows from Lemma 2 that for every , the corresponding follower set in is
where is defined in (4) to be the length of the longest prefix of that appears as a suffix or . Thus is completely determined by , which can take countably many values, and since -shifts are transitive this implies that they are coded. Thus they can be presented by a countable-state graph which supports a countable-state topological Markov chain (the Fischer cover).
Given any coded shift, the vertex set of the Fischer cover is the set of follower sets: for some . A labeled edge is a triple , where and ; the labeled edge set of the Fischer cover is ; that is, there is an edge from to whenever and , and this edge is labeled with the symbol . Note that there may be multiple edges between two vertices, each with a different label.
Say that a sequence labels a walk on the graph if there is a sequence of edges such that for every ,
- is labeled with the symbol , and
- the target vertex of is the source vertex of .
Then if labels a walk on this graph, there is a word such that for all , and hence . Conversely, every labels a walk on the graph, so we can describe both and in terms of walks on the graph.
For the -shift, since the follower set is completely determined by , we can identify the vertex set of the Fischer cover with , and observe that the two cases in Lemma 2 give the following two types of edges.
- There is an edge from to whenever there are and such that , , and . This happens for every since we can take and , so the edge from to is labeled with the symbol .
- There is an edge from to whenever there are and such that , , and . This happens whenever , and so whenever there are edges from to labeled with the symbols .
For example, when , the first part of the graph looks like this:
The vertex labeled 0 can be thought of as the base vertex; it corresponds to the follower set , so every sequence labels a walk starting at this vertex. The vertex labeled 1 corresponds to the follower set ; a sequence labels a walk starting at this vertex if and only if . For a more typical sort of example, let . Then corresponds to the walk which starts at vertex 0, goes out to vertex 2 before returning to vertex 0 (thanks to the fact that ), then goes out to vertex 4 before returning to vertex 0 (because ), then goes out to vertex 3 and stops. We see that and that
4. A directed graph on
In order to give an analogous description of via a countable-state Markov shift, we first observe that is determined lexicographically by two sequences with the property that
Given such an and , the corresponding shift space and language are given by
From Lemma 3, the follower sets are given by
where are given by (7) and represent the lengths of the longest prefixes of and , respectively, that appear as suffixes of . Thus the follower set of is completely determined by and , and so we can represent by a graph whose vertices lie in . As we will see momentarily, not every pair corresponds to a follower set, so we will not use all such vertices in building the graph, but thinking of the integer lattice still provides a useful way to visualize that situation.
It is useful to look at a concrete example. Let and . Then some of the follower sets, together with their corresponding values of , are as follows:
In the graph for the -shifts, remember that the outgoing edges from vertex came in two types: from to with label for each , and from to with label for , depending on whether or . (We switch to using for a generic element of now that is in play.)
For the – shifts, there are more possibilities for and :
- , which happens if , and gives an edge from to labeled ;
- and , which happens if , and gives an edge from to labeled ;
- and , which happens if , and gives an edge from to labeled ;
- and , which happens if , and gives an edge from to labeled .
For our concrete example with and , the first part of the graph is as follows. Note that our coordinate conventions follow standard matrix notation (down, then right) instead of the usual cartesian coordinates, and that we write the vertices as instead of , and so on, in order to save space.
Observe that there are two types of vertices: on the one hand there are those such as , , , , with exactly one outgoing edge, which goes down and to the right; on the other hand there are vertices which have at least two outgoing edges, each of which `resets’ in either the horizontal or vertical directions (or both).
Let us conclude by formulating an open problem. In a previous post, I gave a proof of the (well-known) result that if is a shift space with the specification property, then every Hölder continuous potential has the property that every equilibrium state for has positive entropy (“every Hölder potential is hyperbolic”). The -shifts do not have specification in general (Schmeling showed in 1997 that the set of such that has specification is a null set for Lebesgue measure), but it turns out that they still have the property that every Hölder potential is hyperbolic; Dan Thompson and I showed this in a 2013 paper (arXiv:1106.3575).
Our argument there (see Proposition 3.1 and Section 6.1) relies on the fact that 0 is a `safe symbol’ for the -shifts; if and is obtained from by replacing a single symbol with 0, then as well. This is no longer true for , and so our proof does not generalize. It would be interesting to know whether still has the property that every Hölder potential is hyperbolic; so far as I know this question is wide open. Buzzi conjectured in 2004 that this property holds not just for the – shifts, but for every coding space of a piecewise monotonic interval map. Attacking this problem for the – shifts seems like a reasonable first step towards resolving this conjecture.