# Graph presentation of Lexicographic shifts

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 speciﬁcation: $\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$.

• I've expanded the answer to give a better idea of the construction - I hope it's clear now. – Vaughn Climenhaga Apr 9 '14 at 1:41
• 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. – Rafael Alcaraz Barrera Apr 9 '14 at 5:58