Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic order defined in $\Sigma_n$. Given $a, b \in \Sigma_n$ with $a \prec b$ it is possible to define the lexicographic subshift corresponding to $a,b$ by $$\Sigma_{a,b} = \{x \in \Sigma^n : a \preccurlyeq \sigma^{n}(x) \preccurlyeq b \hbox{ for every } n \geq 0\}.$$ Also, we ask that $a$ and $b$ satisfy:

  1. $a \prec \sigma^{n}(b) \preccurlyeq b$ for every $n \geq 0$;
  2. $a \preccurlyeq \sigma^{n}(a) \prec b$ for every $n \geq 0$.

A particular case of this kind of subshifts is when $a = 0^{\infty}$, which is a $\beta$-shift. For these cases, it is known that a $\beta$-shift can be represented by a countable state directed graph, and there is a construction of such graph. (See for example: V. Climenhaga and D. J. Thompson. Intrinsic ergodicity beyond specification: $\beta$-shifts, $S$-gap shifts, and their factors. Israel J. Math., 192:785–817, 2012).

Does there exist a similar construction for a lexicographic subshift? If so, can you provide me a reference for it? I tried to find a construction without success.


Just as the $\beta$-shift arises as the coding space for the transformation $x\mapsto \beta x$ (mod 1), so the shifts you describe arise as coding spaces for $x\mapsto \alpha + \beta x$ (mod 1). The characteristic sequences $a,b$ correspond to the codings of 0 and 1, respectively.

In particular, you can describe the subshift in terms of a graph -- this was done for arbitrary piecewise monotonic interval maps by Hofbauer, and the key references are:

F. Hofbauer, "On intrinsic ergodicity of piecewise monotonic transformations with positive entropy", Israel J. Math. 34 (1979), no. 3, 213-237, MR 0570882, and part II (same title and journal), 38 (1981), no. 1-2, 107-115.

There are also a couple papers by Hofbauer and Keller from 1982 that deal with these classes of transformations. Because the transformations they deal with are much more general than just $x\mapsto \alpha + \beta x$, it may take some work to extract the exact situation you want from what is shown there. I'll give a summary at the bottom of my understanding of the construction (without proofs).

Another paper that may be relevant is

B. Faller and C.-E. Pfister, "A point is normal for almost all maps $\beta x + \alpha$ mod 1 or generalized $\beta$-transformations", ETDS 29 (2009), no. 5, 1529-1547, MR2545016.

I don't have the actual paper there in front of me at the moment, so I don't remember whether or not they go into details about the graph that codes the shift.

Here's a quick summary of the construction that can be extracted from Hofbauer's work. Given a $\beta$-shift $\Sigma_\beta$, let $z$ be the $\beta$-expansion of $1$, so that the $\beta$-shift is all sequences for which every tail is lexicographically dominated by $z$. You build the graph for $\Sigma_\beta$ by putting a vertex at each $0,1,2,3,\dots$, labeling the edge from $n$ to $n+1$ with the symbol $z_n$, and labeling edges from $n$ to $0$ with the symbols $0,1,\dots,z_n -1$ (if $z_n>0$).

Now given an infinite sequence $x$, the way that you test whether $x\in \Sigma_\beta$ is to see whether $x$ codes a path starting at the origin. Let $k(n)$ denote the vertex which this path has reached after following the labels $x_0,x_1,\dots, x_n$. This can be interpreted as follows: $x_{n-k}\cdots x_n$ matches the first $k$ symbols of the characteristic sequence $z$, and so the remainder of $x$ needs to be tested starting at the vertex $k$, not the vertex $0$.

Now for $x\mapsto \alpha + \beta x$ mod 1, you can do the following. Take the vertex set $\mathbb{N}^2$ (instead of $\mathbb{N}$). As you follow a sequence $x$ to see whether it belongs to the shift space, we interpret "$x_1\cdots x_n$ ends at $(i,j)$" to mean that the last $i$ symbols of $x$ are the first $i$ symbols of $a$, and the last $j$ symbols of $x$ are the first $j$ symbols of $b$. Then you need to compare $x_{n+1}$ to $a_{i+1}$ and $b_{j+1}$. One of the following things happens.

  1. $x_{n+1} = a_{i+1} = b_{j+1}$. Then you move to $(i+1,j+1)$, and the edge connecting the two vertices is labeled with this common value $a_{i+1} = b_{j+1}$.

  2. $x_{n+1} = a_{i+1} < b_{j+1}$. Then the last $i+1$ symbols of $x_1\cdots x_{n+1}$ are the first $i+1$ symbols of $a$, but $x_1\cdots x_{n+1}$ doesn't end with any initial segment of $b$, so you move to $(i+1,0)$. Thus you get an edge from $(i,j)\to(i+1,0)$ labeled with $a_{i+1}$.

  3. $x_{n+1} = b_{j+1} > a_{i+1}$. As in the previous case, you get an edge $(i,j)\to (0,j+1)$ labeled with $b_{j+1}$.

  4. $a_{i+1} < x_{n+1} < b_{j+1}$. Then $x_1\cdots x_{n+1}$ doesn't end with any initial segment of either $a$ or $b$, so you're back to $(0,0)$. Thus you get an edge from $(i,j) \to (0,0)$ labeled with $x_{n+1}$.

Let's summarise all that. The vertices of the graph are elements of $\mathbb{N}^2$, and the outgoing edges from $(i,j)$ follow one of two patterns.

  1. If $a_i = b_j$, then there is a single outgoing edge from $(i,j)$, labeled with the common value, going to $(i+1,j+1)$.

  2. If $a_i < b_j$, then there is an edge $(i,j)\to (i+1,0)$ labeled with $a_i$, an edge $(i,j)\to (0,j+1)$ labeled with $b_j$, and for each $a_i < c < b_j$ there is an edge $(i,j)\to (0,0)$ labeled with $c$.

Note that not all vertices may be accessible from the original vertex $(0,0)$, and so you actually are only concerned with a subset of $\mathbb{N}^2$.

Note also that there are two "distinguished rays" in the graph. One of these corresponds to incrementing $i$ at every step, and is labeled with the sequence $a$. The other corresponds to incrementing $j$ at every step, and is labeled with the sequence $b$. This corresponds to the characteristic sequence $z$ that determines the $\beta$-shift and appears in the graph as a ray to $\infty$.

  • 1
    $\begingroup$ I've expanded the answer to give a better idea of the construction - I hope it's clear now. $\endgroup$ – Vaughn Climenhaga Apr 9 '14 at 1:41
  • $\begingroup$ Thanks a lot Vaughn. It is pretty clear indeed. Also, thanks for providing me the reference of Faller and Pfister's paper, I didn't knew about that. $\endgroup$ – Rafael Alcaraz Barrera Apr 9 '14 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.