Symbolic Dynamics of (−β)-Expansions

K. Dajani and S. D. Ramawadh Department of Mathematics Utrecht University Postbus 80.010 3508 TA Utrecht The Netherlands

                        k.dajani1@uu.nl
                      S.D.Ramawadh@uu.nl

Abstract

We study shift spaces associated with a family of transformations generating expansions in base −β, with β > 1. We give a complete characterization when these shift spaces are sofic or even shifts of finite type.

1 Introduction

In 1957, Rényi studied the expansions of numbers in base β > 1. He only considered the numbers in [0, 1), and only considered one specific rule, the β-transformation, with which we could find these expansions [12]. Many other mathematicians have studied these expansions since then, of which the most famous result is a paper by Parry [10], in which he gave quite an extensive description of both ergodic and symbolic properties of the β-transformation posed by Rényi. Later on several others looked at other types of β-expansions. Erdős [6], for example, studied lazy β-expansions (the opposite, the greedy β-expansions were studied by Rényi). Dajani and Kraaikamp studied a whole class of β-expansions [2] and also random β-expansions [3, 4].

In 2009, Ito and Sadahiro [8] studied (−β)-expansions in base −β, β > 1. They introduced a transformation, the (−β)-transformation, which allowed them to find an expansion of the form

x = ∑_{n=1}^{∞} \frac{x_{n}}{(−β)^{n}} , x_{n} ∈ \{0, 1, …, ⌊β⌋\}  (1)

of any number x ∈ I := [−\frac{β}{β+1}, \frac{1}{β+1}). After having introduced this dynamical system, they continued their study of these expansions by introducing an order on the set of expansions and studying the resulting (−β)-shift. This approach was later continued by Frougny and Lai [7], who gave a detailed description of the symbolic properties of the (−β)-shift. Recently, others have considered different transformations generating (−β)-expansions. Dombek, Masáková and Pelantová [5] considered a generalization of the aforementioned approach. Dajani and Kalle [1], took an even more general approach by studying a whole class of transformations generating (−β)-expansions for 1 < β < 2.

The aim of this paper is to study shift spaces associated with various transformations generating (−β)-expansions and to give a complete characterization when these shift spaces are sofic or shifts of finite type.

2 The dynamical system

Let β > 1 be given. The set of numbers x ∈ ℝ that satisfy (1) for certain coefficients x_{n} ∈ {0, 1, …, ⌊β⌋} is contained in the interval

I_{−β} := [−\frac{β · ⌊β⌋}{β^{2} − 1}, \frac{⌊β⌋}{β^{2} − 1}] .

We call the set A := {0, 1, …, ⌊β⌋} the canonical alphabet. If x has an expansion of the form (1), then we may refer to the right-hand side of (1) as a (−β)-expansion of x. Moreover, we can refer to the digits of the expansion explicitly as follows:

d_{−β}(x) := (x_{1}, x_{2}, …) and d_{−β}(x, n) := x_{n}.

We may also write x = (.x_{1}x_{2} ⋯)_{−β}. Moreover, if a part is periodic we can show this by overlining it. For example, (1, \overline{0, 2}) = (1, 0, 2, 0, 2, 0, 2, …). If a sequence consists of only a periodic part, we will call it purely periodic. If it consists of a pre-periodic and a periodic part, we will call it eventually periodic. Now, suppose that x ∈ I_{−β} with expansion d_{−β}(x) = (x_{1}, x_{2}, …). It follows that

−βx − x_{1} = ∑_{n=1}^{∞} \frac{x_{n+1}}{(−β)^{n}} .

In particular, we see that −βx − x_{1} ∈ I_{−β} as the right-hand side is another (−β)-expansion. Therefore, one should look at the family of maps −βx−a, a ∈ A, on the interval I_{−β}. Figure 1 shows what happens for a specific choice for β. Notice that there is a small subinterval for which there is more than one possibility for a such that −βx−a remains in I_{−β} for all points in this subinterval. Such a subinterval will be called a choice region. Other subintervals, where there is only one choice for a ∈ A, are called uniqueness regions. Note that this behaviour is not restricted to this specific base −β; in fact, it happens for all non-integer base −β. This is a consequence of our alphabet A.

In any case, we need to specify a function d : I_{−β} → A, the digit function, such that for any x ∈ I_{−β} it follows that also −βx − d(x) ∈ I_{−β}. Henceforth, we will work with the following assumptions:

−1 −\frac{1}{β^{2}} \frac{1}{β}

Figure 1: The maps −βx − a with a ∈ A on I_{−β} for β = \frac{1+\sqrt{5}}{2}.

Assumption 1. The digit function d : I_{−β} → A satisfies the following properties:

i. d(x) is such that x ∈ I_{−β} ⇒ −βx − d(x) ∈ I_{−β},

ii. d is either left- or right-continuous everywhere,

iii. d is nonincreasing on I_{−β}.

The idea behind the assumptions on the digit function is that it divides the interval I_{−β} into at most ⌊β⌋ + 1 smaller intervals, where the intervals are all either left- or right-closed and each of the intervals has a digit from the alphabet A assigned to them. These digits are assigned in such a way that, from left to right, these digits are decreasing. This implies that all digits of A are actually used.

Property i of Assumption 2.1 is worth considering more carefully. As a consequence of our choice of alphabet A, we have that for any β > 1 and any x ∈ I_{−β} there is at least one a ∈ A such that −βx − a ∈ I_{−β}. To see why, fix x ∈ I_{−β} and consider the set S(x) = \{−βx − a : a ∈ A\}. The smallest element of S(x) cannot be greater than \frac{⌊β⌋}{β^{2}−1} and the largest element of S(x) cannot be smaller than −\frac{β·⌊β⌋}{β^{2}−1}. Moreover, I_{−β} has length strictly greater than 1, whereas the difference between two consecutive digits in A is 1. These observations imply that S(x) ∩ I_{−β} ≠ ∅.

The points where d is discontinuous are called cut points. The cut points always lie in choice regions, and the cut points divide these regions into smaller regions on which the digit function dictates which map −βx − a to choose.

Using this digit function, we can finally pose our dynamical system. We define, for a given digit function d, the map

T_{−β}(x) := −βx − d(x)

on I_{−β}. If we want to emphasize whether the underlying digit function is left- or rightcontinuous, we may write T_{L,−β}(x) and T_{R,−β}(x) respectively.

Proposition 2. Let x ∈ I_{−β} be arbitrary and let x_{n} := d (T_{−β}^{n−1}(x)). Then we have x = (.x_{1}x_{2} …)_{−β}.

Proof. We show, by induction on n, that for all n ≥ 1 we have

x = \frac{T_{−β}^{n}(x)}{(−β)^{n}} + ∑_{k=1}^{n} \frac{x_{k}}{(−β)^{k}} .

By definition, we have T_{−β}(x) = −βx − x_{1}, which in turn is equivalent to x = \frac{T_{−β}(x)}{−β} + \frac{x_{1}}{−β}. Hence, the statement holds for n = 1.

Now assume that the statement is true for some positive integer m − 1. Since we know that T_{−β}^{m}(x) = −βT_{−β}^{m−1}(x) − x_{m}, we also have

T_{−β}^{m−1}(x) = \frac{x_{m}}{−β} + \frac{T^{m}(x)}{−β}

and hence

x = \frac{T_{−β}^{m−1}(x)}{(−β)^{m−1}} + ∑_{k=1}^{m−1} \frac{x_{k}}{(−β)^{k}}

= \frac{\frac{x_{m}}{−β} + \frac{T^{m}(x)}{−β}}{(−β)^{m−1}} + ∑_{k=1}^{m−1} \frac{x_{k}}{(−β)^{k}}

= \frac{T_{−β}^{m}(x)}{(−β)^{m}} + ∑_{k=1}^{m} \frac{x_{k}}{(−β)^{k}} .

We see that the statement is true for m as well. The proof is finished by noting that \frac{T_{−β}^{m}(x)}{(−β)^{m}} → 0 as m → ∞.

The following example shows that the original (−β)-transformation posed by Ito and Sadahiro [8] can be viewed as restrictions of our maps.

Example 3. Let the base be given by β = \frac{1+\sqrt{5}}{2} and consider the map T_{L,−β} with cut point 2 − \sqrt{5}. This map is shown in Figure 2. The smaller box in Figure 2 is the (−β)-

\begin{matrix}−1 \\ 0 \\ β − 1 \end{matrix}

Figure 2: The map T_{L,−β} from Example 3. transformation as defined by Ito and Sadahiro. Hence, for this particular β and choice of cut point, our map T_{L,−β} is an extension of their (−β)-transformation.

Finding (−β)-expansions using this map T_{L,−β} can be done using Proposition 2. For example, we find −\frac{1}{2} = (.\overline{100})_{−β}, which agrees with the result of Ito and Sadahiro. However, we can also find −\frac{3}{4} = (.1\overline{011110})_{−β}; a result that cannot be found using the original (−β)- transformation.

3 Admissibility and shift spaces

Henceforth, whenever we refer to the map T_{−β}, we assume that it has been fixed beforehand. A sequence (x_{1}, x_{2}, …) ∈ A^{ℕ} is called T_{−β}-admissible if we have d_{−β}(x) = (x_{1}, x_{2}, …) for some x ∈ I_{−β} and, moreover, the (−β)-expansion of x generated by the map T_{−β} (see Proposition 2) has coefficients x_{1}, x_{2}, … A finite block is called T_{−β}-admissible if it appears in a T_{−β}-admissible sequence.

In order to nicely characterize the T_{−β}-admissible sequences, we introduce an order on the set of T_{−β}-admissible sequences: the alternate (lexicographical) order. We write (x_{1}, x_{2}, …) ≺ (y_{1}, y_{2}, …) if and only if there exists some integer k ≥ 1 such that x_{i} = y_{i} for all i < k and (−1)^{k}(x_{k} − y_{k}) < 0. Also, (x_{1}, x_{2}, …) ⪯ (y_{1}, y_{2}, …) means that either (x_{1}, x_{2}, …) ≺ (y_{1}, y_{2}, …) or (x_{1}, x_{2}, …) = (y_{1}, y_{2}, …) holds.

Proposition 4. Let T_{−β} be given. Let x, y ∈ I_{−β} with x ≠ y be arbitrary and let d_{−β}(x) and d_{−β}(y) be the (−β)-expansions of respectively x and y generated by T_{−β}. Then x < y if and only if d_{−β}(x) ≺ d_{−β}(y).

Proof. This has been shown in [1, Lemma 3.1] for 1 < β < 2. We give the proof here for completeness. Write d_{−β}(x) = (x_{1}, x_{2}, …) and d_{−β}(y) = (y_{1}, y_{2}, …). Let k ≥ 1 be the smallest integer for which x_{k} ≠ y_{k}. Then we have

x = \frac{T_{−β}^{k−1}(x)}{(−β)^{k−1}} + ∑_{i=1}^{k−1} \frac{x_{i}}{(−β)^{i}} < \frac{T_{−β}^{k−1}(y)}{(−β)^{k−1}} + ∑_{i=1}^{k−1} \frac{y_{i}}{(−β)^{i}} = y

if and only if

\frac{T_{−β}^{k−1}(x)}{(−β)^{k−1}} < \frac{T_{−β}^{k−1}(y)}{(−β)^{k−1}} .

This latter inequality is, regardless of the parity of k, equivalent to the inequality

(−1)^{k} (x_{k} − y_{k}) < 0,

since x_{k} = d (T_{−β}^{k−1}(x)) (similar for y_{k}). The statement now follows.

We see that the alternate order respects the natural order on ℝ (as long as we compare (−β)-expansions generated by the same map T_{−β}). The behaviour of the map T_{−β}, and hence the generated (−β)-expansions, are determined by our choice for the cut points; two maps with the same base β but different cut points will produce different (−β)-expansions for at least one point x ∈ I_{−β}. Therefore, we should pay extra attention to our cut points. Let c be any cut point of a given map T_{−β}, then we define d_{L,−β}(c) to be (−β)-expansion generated by the left-continuous version of T_{−β}, regardless of the continuity of T_{−β} itself (we define d_{R,−β}(c) similarly).

Example 5. We continue Example 3. Our cut point is 2 − \sqrt{5}, and the (−β)-expansion of this point generated by the map is 2 − \sqrt{5} = (.11\overline{0})_{−β}. Since the map in Example 3 is leftcontinuous, we know that d_{L,−β}(2 − \sqrt{5}) = (1, 1, \overline{0}). To determine d_{R,−β}(2 − \sqrt{5}) we modify the map in Example 3 such that it is right-continuous at 2 − \sqrt{5} (all other points remain unchanged). The (−β)-expansion of 2 − \sqrt{5} generated by this new map is d_{R,−β}(2 − \sqrt{5}). The reader is invited to verify that d_{R,−β}(2 − \sqrt{5}) = (0, 0, 1, \overline{0}).

In order to state the following characterization of T_{−β}-admissible sequences neatly, we introduce a little more notation. Recall that the digit function divides I_{−β} into smaller subintervals. A subinterval on which the digit function is constant with value a will be denoted by I_{a}. Its left and right endpoint will be denoted by respectively ℓ_{a} and r_{a}. We can now characterize T_{−β}-admissible sequences as follows:

Proposition 6. The following hold:

(a) If (x_{1}, x_{2}, …) is T_{L,−β}-admissible, then for all n ≥ 1:

– if x_{n} = ⌊β⌋, then d_{−β}(ℓ_{⌊β⌋}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{⌊β⌋});

– if x_{n} = a ≠ ⌊β⌋, then d_{R,−β}(ℓ_{a}) ≺ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{a}).

(b) If (x_{1}, x_{2}, …) is T_{R,−β}-admissible, then for all n ≥ 1:

– if x_{n} = 0, then d_{R,−β}(ℓ_{0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{−β}(r_{0});

– if x_{n} = a ≠ 0, then d_{R,−β}(ℓ_{a}) ⪯ (x_{n}, x_{n+1}, …) ≺ d_{L,−β}(r_{a}).

Proof. We will only prove (a), since the proof of (b) is similar. If x_{n} = ⌊β⌋, the result follows from Proposition 4.

Now, suppose that x_{n} = a ≠ ⌊β⌋. Then, by Proposition 4 we only need to show that d_{R,−β}(ℓ_{a}) ≺ (x_{n}, x_{n+1}, …). Since the map is left-continuous, we know that d_{L,−β}(ℓ_{a}, 1) ≠ a and hence ℓ_{a} < T_{L,−β}^{n−1}(x). Hence, there is a smallest integer k ≥ 1 such that d_{R,−β}(ℓ_{a}, k) ≠ d_{R,−β}(T_{L,−β}^{n−1}(x), k). Regardless of the parity of k, it follows that

(−1)^{k} (d_{R,−β}(ℓ_{a}, k) − d_{R,−β}(T_{L,−β}^{n−1}(x)), k) < 0,

which proves d_{R,−β}(ℓ_{a}) ≺ (x_{n}, x_{n+1}, …).

The converse of Proposition 6 is not generally true. It is true in the case of Example 3 (we will see this later). We present the following Example in which the converse is not true.

Example 7. Consider the map T_{L,−β} with β = \frac{1+\sqrt{5}}{2} and cut point 0, that is, the map T_{L,−β} on I_{−β} = [−1, β − 1] given by:

T_{L,−β}(x) = \begin{cases}−βx − 1, & if −1 ≤ x ≤ 0; \\ −βx, & if 0 < x < β − 1. \end{cases}

Then, according to Proposition 6, a sequence (x_{1}, x_{2}, …) is T_{L,−β}-admissible if

(\overline{1, 0}) ⪯ (x_{n}, x_{n+1} …) ⪯ (1, \overline{1, 0}) or (\overline{0}) ≺ (x_{n}, x_{n+1}, …) ⪯ (\overline{0, 1})

holds for all n ≥ 1. The sequence (0, 1, \overline{1, 0}) also satisfies this condition, but it is not T_{L,−β}- admissible. To see this, note that (.01\overline{10})_{−β} = 0, whereas the (−β)-expansion of 0 generated by the map T_{L,−β} is d_{−β}(0) = (1, \overline{1, 0}).

Hence, the set of sequences that satisfy the series of inequalities in Proposition 6 might be a bit larger than the set of T_{−β}-admissible sequences. The problem arises whenever a cut point gets mapped onto some (not necessarily different) cut point after an odd amount of applications of the map T_{−β}.

Let T_{−β} be given and let c be any cut point of T_{−β}. We define

d_{L,−β}^{∗}(c) := lim_{x↑c} d_{−β}(x) and d_{R,−β}^{∗}(c) := lim_{x↓c} d_{−β}(x).

Notice that the definition of d_{L,−β}^{∗}(c) does not require that the underlying map is leftcontinuous (similar for d_{R,−β}^{∗}(c)). Instead, these sequences should be thought of as “improvements” of respectively d_{L,−β}(c) and d_{R,−β}(c). The improvement follows from the following lemma:

Lemma 8. Let T_{−β} be given and let c be any cut point of T_{−β}. The following hold:

(a) There exists no T_{L,−β}-admissible sequence (x_{1}, x_{2}, …) such that we have d_{R,−β}(c) ≺ (x_{1}, x_{2}, …) ≺ d_{R,−β}^{∗}(c).

(b) There exists no T_{R,−β}-admissible sequence (x_{1}, x_{2}, …) such that we have d_{L,−β}^{∗}(c) ≺ (x_{1}, x_{2}, …) ≺ d_{L,−β}(c).

Proof. We only prove (a), since the proof of (b) is similar. Suppose that the statement is false and let (x_{1}, x_{2}, …) be a T_{L,−β}-admissible sequence satisfying d_{R,−β}(c) ≺ (x_{1}, x_{2}, …) ≺ d_{R,−β}^{∗}(c) and x = (.x_{1}x_{2} ⋯)_{−β}. By assumption, we have x_{1} = d_{R,−β}(c, 1), and hence x > c.

Let (x^{n})_{n=1}^{∞} be a decreasing sequence for which d_{−β}(x^{n}, 1) = d_{R,−β}^{∗}(c, 1) for all n ≥ 1, where d_{−β}(x^{n}) is the (−β)-expansion of x^{n} generated by T_{−β}. For all m, n ≥ 1 with m < n we have d_{−β}(x^{n}) ≺ d_{−β}(x^{m}) by Proposition 4. It follows that d_{R,−β}^{∗}(c) ⪯ d_{−β}(x^{n}) for all n ≥ 1. Moreover, the sequence converges to c and hence for some k ≥ 1 we have x^{k} < x and d_{R,−β}^{∗}(c) ⪯ d_{−β}(x^{k}) ≺ d_{−β}(x). This latter is, however, a contradiction and hence the sequence (x_{1}, x_{2}, …) cannot exist.

For any given map T_{−β}, computing the sequences d_{L,−β}^{∗}(c) and d_{R,−β}^{∗}(c), where c is a cut point, is not hard. Fix c and suppose we want to find d_{L,−β}^{∗}(c). We present the following algorithm:

1. Start with k := 1, T̂_{1} := T_{L,−β} and c_{0} := c.

2. Compute c_{k} := T̂_{k}(c_{k−1}) and set

d_{L,−β}^{∗}(c, k) := \begin{cases}d^{L}(c_{k−1}), & if T̂_{k} = T_{L,−β}; \\ d^{R}(c_{k−1}), & if T̂_{k} = T_{R,−β}; \end{cases}

where d^{L} and d^{R} are the digit functions of T_{L,−β} and T_{R,−β} respectively.

3. Let m := max{0 ≤ i < k : c_{i} is a cut point}. If c_{k} is a cut point and if k − m is odd, then:

• if T̂_{k} = T_{L,−β}, then T̂_{k+1} := T_{R,−β};

• if T̂_{k} = T_{R,−β}, then T̂_{k+1} := T_{L,−β};

and else T̂_{k+1} := T̂_{k}.

4. Increase k by one and go back to step 2.

If we wish to find d_{R,−β}^{∗}(c) instead, all that changes is that we should start with T̂_{1} := T_{R,−β}.

Proposition 9. The method described above for finding d_{L,−β}^{∗}(c) and d_{R,−β}^{∗}(c) is correct.

Proof. We only prove correctness for d_{L,−β}^{∗}(c). Call the sequence obtained by the algorithm above s_{L,−β}(c), then we need to show that s_{L,−β}(c) = lim_{x↑c} d_{−β}(x). For any integer n ≥ 1, define (recall that ℓ_{s_{L,−β}(c,k)} denotes the left endpoint of the subinterval on which the digit function equals the kth digit of s_{L,−β}(c)):

ϵ_{n} := \frac{1}{β^{n−1}} min (\{|c_{k} − ℓ_{s_{L,−β}(c,k+1)}| : 0 ≤ k ≤ n, k even\}
∪ {|c_{k} − r_{s_{L,−β}(c,k+1)}| : 0 ≤ k ≤ n, k odd}) .

It follows that any x ∈ (c − ϵ_{n}, c) satisfies d_{L,−β}(x, i) = s_{L,−β}(c, i) for all i ≤ n. It suffices to show that ϵ_{n} ≠ 0 for all n ≥ 1. Suppose that k ≥ 1 is the smallest integer such that ϵ_{k} = 0 and assume that k is odd (the proof is similar for k even). It follows that c_{k} = r_{s_{L,−β}(c,k+1)}, and, since T̂_{k+1} = T_{R,−β}, we must hit r_{−β} after an odd number of iterations (it cannot be any other cut point since that would imply c_{k} = ℓ_{s_{L,−β(c,k+1)}} ≠ r_{s_{L,−β}(c,k+1)}). It follows that c_{k−1} is either a cut point or −\frac{β·⌊β⌋}{β^{2}−1}. By iterating this argument it follows that c must be an endpoint of I_{−β}. We have reached a contradiction since the endpoints are no cut points. It follows that ϵ_{n} > 0 for all n ≥ 1.

Example 10. We continue Example 7. Since the orbit of 0 never hits 0 again under T_{L,−β}, we conclude that d_{L,−β}^{∗}(0) = d_{L,−β}(0) = (1, \overline{1, 0}). Under T_{R,−β}, however, 0 hits itself after one iteration. Hence, we have d_{R,−β}^{∗}(0, 1) = 0 and continue iterating T_{L,−β}. At this point, we know the orbit of 0 under T_{L,−β} and therefore d_{R,−β}^{∗}(0) is the concatenation of the single-digit block (0) with (1, \overline{1, 0}): d_{R,−β}^{∗}(0) = (0, 1, \overline{1, 0}).

Example 11. We continue Example 5. Since the orbit of 2−\sqrt{5} never hits itself under both T_{L,−β} and T_{R,−β}, we have d_{L,−β}^{∗}(2 − \sqrt{5}) = d_{L,−β}(2 − \sqrt{5}) = (1, 1, \overline{0}) and d_{R,−β}^{∗}(2 − \sqrt{5}) = d_{R,−β}(2 − \sqrt{5}) = (0, 0, 1, \overline{0}).

Remark 12. The sequences d_{L,−β}^{∗}(c) and d_{R,−β}^{∗}(c) are concatenations of blocks of sequences of the form d_{L,−β}(ℓ_{a}), d_{R,−β}(ℓ_{a}), d_{L,−β}(r_{a}) and d_{R,−β}(r_{a}) where a ∈ A.

The following lemma is very important:

Lemma 13. Let (x_{1}, x_{2}, …) ∈ A^{ℕ}. The following hold:

(a) If for all n ≥ 1 we have

d_{R,−β}^{∗}(ℓ_{x_{n}}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{x_{n}}),

then every finite subblock of (x_{1}, x_{2}, …) is T_{L,−β}-admissible.

(b) If for all n ≥ 1 we have

d_{R,−β}(ℓ_{x_{n}}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}^{∗}(r_{x_{n}}),

then every finite subblock of (x_{1}, x_{2}, …) is T_{R,−β}-admissible.

Proof. We only prove (a), as the proof of (b) is similar. Suppose that (x_{1}, x_{2}, …) satisfies the given condition and define x^{(k)} := ∑_{n=k}^{∞} \frac{x_{n}}{(−β)^{n−k+1}} . Assume that there exist integers s(k), t(k) > k such that:

x_{k} ⋯ x_{s(k)−1} = d_{R,−β}^{∗}(ℓ_{x_{k}}, 1) ⋯ d_{R,−β}^{∗}(ℓ_{x_{k}}, s(k) − k),
(−1)^{s(k)−k+1} (d_{R,−β}^{∗}(ℓ_{x_{k}}, s(k) − k + 1) − x_{s(k)}) < 0,

and

x_{k} ⋯ x_{t(k)−1} = d_{L,−β}(r_{x_{k}}, 1) ⋯ d_{L,−β}(r_{x_{k}}, t(k) − k),
(−1)^{t(k)−k+1} (x_{t(k)} − d_{L,−β}(r_{x_{k}}, t(k) − k + 1)) < 0.

If either s(k) or t(k) does not exist, then there is nothing to prove. Let y be a point such that d_{L,−β}(y, i) = d_{R,−β}^{∗}(ℓ_{x_{k}}, i) for 1 ≤ i ≤ s(k) − k + 1, then

x^{(k)} − ℓ_{x_{k}} > x^{(k)} − y
= ∑_{n=s(k)}^{∞} \frac{x_{n}}{(−β)^{n−k+1}} − \frac{T_{L,−β}^{s(k)−k}(y)}{(−β)^{s(k)−k}}

> \frac{1}{(−β)^{s(k)−k}} (x^{s(k)} − T_{L,−β}^{s(k)−k}(y)) ,

from which it follows that

x^{(k)} − ℓ_{x_{k}} > \begin{cases}\frac{x^{s(k)}−ℓ_{x_{s(k)}}}{(−β)^{s(k)−k+1}} , & if s(k) − k + 1 is odd; \\ \frac{x^{s(k)}−r_{x_{s(k)}}}{(−β)^{s(k)−k+1}} , & if s(k) − k + 1 is even. \end{cases}  (2)

Similarly, one can show that

r_{x_{k}} − x^{(k)} > \begin{cases}\frac{r_{x_{t(k)}}−x^{t(k)}}{(−β)^{t(k)−k+1}} , & if t(k) − k + 1 is odd; \\ \frac{ℓ_{x_{t(k)}}−x^{t(k)}}{(−β)^{t(k)−k+1}} , & if t(k) − k + 1 is even. \end{cases}  (3)

By iteratively applying the bounds in (2) and (3) we get a sequence of bounds that approach zero (as the numerator is bounded and the denominator goes to infinity). It follows that l_{x_{k}} < x^{(k)} < r_{x_{k}} for all k ≥ 1, which implies d_{L,−β} (x^{(1)}) = (x_{1}, x_{2}, …).

Using these new objects, we can make the inequalities in Proposition 6 more strict and obtain an equivalence.

Theorem 14. The following hold:

(a) The sequence (x_{1}, x_{2}, …) is T_{L,−β}-admissible if and only if for all n ≥ 1:

– if x_{n} = ⌊β⌋, then d_{−β}(ℓ_{⌊β⌋}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{⌊β⌋});

– if x_{n} = a ≠ ⌊β⌋, then d_{R,−β}^{∗}(ℓ_{a}) ≺ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{a}).

(b) The sequence (x_{1}, x_{2}, …) is T_{R,−β}-admissible if and only if for all n ≥ 1:

– if x_{n} = 0, then d_{R,−β}(ℓ_{0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{−β}(r_{0});

– if x_{n} = a ≠ 0, then d_{R,−β}(ℓ_{a}) ⪯ (x_{n}, x_{n+1}, …) ≺ d_{L,−β}^{∗}(r_{a}).

Proof. This has been proven for 1 < β < 2 in [1, Theorem 3.1]. We give the proof for completeness. We only prove (a), since the proof of (b) is similar. The ”only if” part follows from Proposition 6 and Lemma 8.

To prove the ”if” part, suppose that (x_{1}, x_{2}, …) satisfies the given inequalities. From Lemma 13 it follows that every finite subblock (x_{n}, …, x_{n+k}) is T_{L,−β}-admissible. It is sufficient to check that (x_{n}, x_{n+1}, …) ≠ d_{R,−β}^{∗}(ℓ_{x_{n}}) for all n ≥ 1 such that x_{n} ≠ ⌊β⌋. However, this follows directly from the given inequalities.

Let T_{−β} be a (−β)-transformation such that T_{−β} restricted to the interval [−\frac{β}{β+1}, \frac{1}{β+1}) is the Ito-Sadahiro transformation. While our condition in Theorem 14 is different from the condition found by Ito and Sadahiro [8, Theorem 10], the two actually agree. This is because their transformation implicitly specifies the cut points. Moreover, these cut points are all mapped to −\frac{β}{β+1}. The following example illustrates this:

Example 15. Consider the map of Example 3 restricted to the interval [−\frac{β}{β+1}, \frac{1}{β+1}). Our condition in Theorem 14(a), when restricted to this interval, becomes:

(1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (1, 1, \overline{0}) ∨ (0, 0, 1, \overline{0}) ≺ (x_{n}, x_{n+1}, …) ≺ (0, 1, \overline{0})  (4)

for all n ≥ 1. On the other hand, by Ito and Sadahiro [8, Theorem 10] we have:

(1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …) ≺ (0, 1, \overline{0})

for all n ≥ 1, which suggests that the sequences corresponding to the cut point are redundant. To see why this is the case, suppose that (x_{1}, x_{2}, …) satisfies (4) for all n ≥ 1. Fix k ≥ 1 and assume for now that x_{k} = 1, then we have (x_{k}, x_{k+1}, …) ⪯ (1, 1, \overline{0}) from which it follows that (1, \overline{0}) ⪯ (x_{k+1}, x_{k+2}, …). This condition, however, is already satisfied which means that we can reduce the first part of (4) to (1, \overline{0}) ⪯ (x_{k}, x_{k+1}, …). Similarly, we can reduce the second part of (4) whenever x_{k} = 0 and get

\begin{cases}(1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …), & whenever x_{n} = 1; \\ (x_{n}, x_{n+1}, …) ≺ (0, 1, \overline{0}), & whenever x_{n} = 0, \end{cases}

which in turn can be neatly written as

(1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …) ≺ (0, 1, \overline{0}),

which is the result by Ito and Sadahiro.

4 Shifts and graphs

In Theorem 14 we gave a characterization of the shift-invariant set of T_{−β}-admissible sequences. This set will be denoted with S_{T}. In order to turn S_{T} into a shift space, we need to consider its closure. This closure will be called the (−β)-shift (for the underlying map T_{−β}) and will be denoted by S_{−β}. The context should make it clear what the underlying map T_{−β} is. If we wish to emphasize whether T_{−β} is left- or right-continuous, we may write S_{L,−β} and S_{R,−β} respectively. The most straightforward characterization of the (−β)-shift is the following.

Lemma 16. Let T_{−β} be given and let x ∈ A^{ℕ}. Then x ∈ S_{−β} if and only if (x_{p}, …, x_{q}) is T_{−β}-admissible for all 1 ≤ p ≤ q.

We use this lemma to prove the following much more useful characterization.

Theorem 17. Let T_{−β} be given and let x ∈ A^{ℕ}. The following hold:

(a) We have x ∈ S_{L,−β} if and only if d_{R,−β}^{∗}(ℓ_{x_{n}}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}(r_{x_{n}}) for all n ≥ 1.

(b) We have x ∈ S_{R,−β} if and only if d_{R,−β}(ℓ_{x_{n}}) ⪯ (x_{n}, x_{n+1}, …) ⪯ d_{L,−β}^{∗}(r_{x_{n}}) for all n ≥ 1.

Proof. We only prove (a), as the proof of (b) is similar. The ”if” part follows from Lemma 13 and Lemma 16. Let N ≥ 1 be arbitrary and fixed. If (x_{N}, x_{N+1}, …) is T_{L,−β}-admissible, Theorem 14 applies. Thus, assume it is not T_{L,−β}-admissible. By Lemma 16, every finite subblock (x_{N}, …, x_{N+k}), where k ≥ 1, is T_{L,−β}-admissible. Hence, we have

(x_{N}, …, x_{N+k}) ⪯ (d_{L,−β}(r_{x_{N}} , 1), …, d_{L,−β}(r_{x_{N}} , k + 1))

which follows immediately and, by Lemma 8, we also have

(d_{R,−β}^{∗}(ℓ_{x_{N}} , 1), …, d_{R,−β}^{∗}(ℓ_{x_{N}} , k + 1)) ⪯ (x_{N}, …, x_{N+k}).

This proves the theorem.

Based on this theorem, we can classify the shift space S_{−β}. The behaviour of these shift spaces depend on the sequences d_{R,−β}^{∗}(ℓ_{a}) and d_{L,−β}(r_{a}) (where a ∈ A) if the underlying map is left-continuous and d_{R,−β}(ℓ_{a}) and d_{L,−β}^{∗}(r_{a}) if the underlying map is right-continuous. The sequences will be called boundary sequences.

The next theorem states that eventually periodic boundary sequences are a necessary and sufficient condition for the shift space to be sofic. In order to prove this, we will give an algorithm, based on the algorithm in [8], that construct a labeled graph recognizing the shift. For now, we will assume that all boundary sequences are eventually periodic.

Assume that our shift space has a left-continuous underlying map. The shift space has at most 2(⌊β⌋ + 1) boundary sequences, two for each a ∈ A used by the underlying digit function: one corresponding to ℓ_{a} and the other to r_{a}. In what follows we will assume that all digits in A are used. Hence, we will need two sets for each digit, m_{a}^{ℓ} and m_{a}^{r}, which are subsets of ℤ_{≥0}. These sets keep track of the (finite) memory of a machine that reads the sequence (x_{1}, x_{2}, …) one digit at a time. The meaning of k ∈ m_{a}^{ℓ} is that the current memory contains a finite subblock starting with a that equals the prefix of the boundary sequence corresponding to ℓ_{a} and where the next digit needs to be matched against the (k + 1)-th digit of the boundary sequence corresponding to ℓ_{a} (similarly for m_{a}^{r}). In fact, we can give an upper bound for each of these memory sets by using the fact that all boundary sequences are eventually periodic. Let the boundary sequence be eventually periodic with pre-periodic part of length q ≥ 0 and periodic part of length p ≥ 1, then the upper bounds, denoted by U_{a}^{ℓ} and U_{a}^{r} respectively, are equal to

2p,  if q = 0;
2p + q − 1, if q ≠ 0 and p is odd;
p + q − 1, if q ≠ 0 and p is even.

These upper bounds tell us how many different prefixes we may expect.

Next, assume that we read a new digit of the sequence (x_{1}, x_{2}, …), say d. Our memory has now changed and hence we need to update our memory sets. If k ∈ m_{a}^{ℓ} and we read the digit d, we change the index k into another index m_{a}^{ℓ}(k/d), which is defined as:

m_{a}^{ℓ}(k/d) := \begin{cases}k + 1, & if k < U_{a}^{ℓ} and d = d_{R,−β}^{∗}(ℓ_{a}, k + 1); \\ 1, & if k = U_{a}^{ℓ}, d = d_{R,−β}^{∗}(ℓ_{a}, k + 1) and q = 0; \\ q, & if k = U_{a}^{ℓ}, d = d_{R,−β}^{∗}(ℓ_{a}, k + 1) and q ≠ 0; \\ 0, & if k ≠ 0 and (−1)^{k+1} (d_{R,−β}^{∗}(ℓ_{a}, k + 1) − d) < 0; \\ 0, & if k = 0 and d ≠ a; \\ 1, & if k = 0 and d = a; \\ F, & otherwise. \end{cases}  (5)

Let us shortly explain what each of these seven cases mean. If our memory contains a subblock matching the prefix of the boundary sequence of ℓ_{a} but does not contain one complete period, then we check digit d against the next digit of the prefix (case 1). If the boundary sequence is purely periodic and if our memory contains two complete periods (we need two complete periods in the case p is odd), then move back to the beginning (case 2). If the boundary sequence is eventually periodic and our memory contains the maximum number of complete periods (one if p is even, otherwise two), then return to the beginning of the periodic part (case 3). If our memory contains a subblock that, together with the digit d, can be accepted bacause of Theorem 17, then accept it and ”forget” about this block (case 4). If our memory does not contain the digit a and if the new digit also is not a, do absolutely nothing (case 5). On the other hand, if the new digit equals a, we have a subblock of length 1 matching the prefix of equal length of the boundary sequence ℓ_{a} (case 6). If none of the above happens, then we are neither undecided (cases 1,2,3,5 and 6) nor can we accept any subblock (case 4), and hence we must reject it (case 7).

Similarly, we define

m_{a}^{r}(k/d) := \begin{cases}k + 1, & if k < U_{a}^{r} and d = d_{L,−β}(r_{a}, k + 1); \\ 1, & if k = U_{a}^{r}, d = d_{L,−β}(r_{a}, k + 1) and q = 0; \\ q, & if k = U_{a}^{r}, d = d_{L,−β}(r_{a}, k + 1) and q ≠ 0; \\ 0, & if k ≠ 0 and (−1)^{k+1} (d − d_{L,−β}(r_{a}, k + 1)) < 0; \\ 0, & if k = 0 and d ≠ a; \\ 1, & if k = 0 and d = a; \\ F, & otherwise. \end{cases}  (6)

We state the following result, which follows directly from equations (5) and (6):

Corollary 18. Let (z_{1}, …, z_{n}) be our current memory containing no forbidden blocks. Then for some a ∈ A and i ≤ U_{a}^{ℓ} (or U_{a}^{r}) either m_{a}^{ℓ}(i/d) or m_{a}^{r}(i/d) equals F if and only if (z_{1}, …, z_{n}, d) contains a forbidden block.

To construct a labeled graph recognizing the shift S_{L,−β} whose boundary sequences are all eventually periodic, we perform the following steps:

1. Let V be the set of vertices where each vertex v ∈ V is labeled (m_{0}^{ℓ}, m_{0}^{r}, …, m_{⌊β⌋}^{ℓ}, m_{⌊β⌋}^{r}) such that m_{a}^{ℓ} is a nonempty subset of {0, 1, …, U_{a}^{ℓ}} and m_{a}^{r} is a nonempty subset of {0, 1, …, U_{a}^{r}}.

2. For each vertex v ∈ V and d ∈ A draw an edge with label d from vertex v to vertex w = (w_{1}, w_{2}, …, w_{2⌊β⌋+2}), where

w_{k} = \begin{cases}φ_{ℓ,(k−1)/2}(m_{(k−1)/2}^{ℓ}, d), & if k is odd; \\ φ_{ℓ,(k−2)/2}(m_{(k−2)/2}^{r}, d), & if k is even; \end{cases}

and the maps φ_{ℓ,a} and φ_{r,a} are defined as

φ_{ℓ,a}(v, d) := \begin{cases}F, & if F ∈ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\}; \\ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\} \ \{0\}, & if \{0\} ⊊ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\} \\ & and F ∉ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\}; \\ \{1\} ∪ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\} \ \{0\}, & if 1, F ∉ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\} \\ & and d = a; \\ ⋃_{i∈v} \{m_{a}^{ℓ}(i/d)\} , & otherwise. \end{cases} (7)

The definition of φ_{r,a} is nearly identical; simply replaces all instances of ℓ in (7) with r.

3. The connected component (i.e., each vertex has at least one outgoing edge) containing the zero vertex is the labeled graph recognizing S_{L,−β}.

Since our memory sets may contain more than one digit, we need to keep track of the way each of these indices react to the new digit d and, should they arise, remove any inconsistencies. This is the job of φ_{ℓ,a} and φ_{r,a}. Let us explain the four cases in (7) in more detail. If, because of the new digit d, our memory contains a forbidden subblock, automatically reject it (case 1). If we cannot reject it, then suppose our memory contains at least two subblocks on which we are undecided, but can accept some (not all) of them after we read the new digit d. In that case adding a 0 to the memory set would be redundant (case 2). If the new digit equals a, then add 1 to the memory set, as we have a new subblock (of length 1) starting with a (case 3). If none of these three cases apply, there are no inconsistencies (case 4).

In practice, one starts with the zero vertex and adds vertices along the way. Since none of the vertices carry the label F, we do not draw an edge if the update rule in (7) implies that the edge should point towards such a vertex.

Theorem 19. The shift space S_{−β} is sofic if and only if its boundary sequences are all eventually periodic.

Proof. Assume, without loss of generality, that the underlying map is left-continuous (in the remainder of the proof we will write S_{L,−β}). Let G be a right-resolving labeled graph recognizing S_{L,−β} (recall [9, Theorem 3.3.2]) and let L be the labeling. Fix a ∈ A and consider d_{R,−β}^{∗}(ℓ_{a}) (the argument is similar for d_{L,−β}(r_{a})). There exists a path ξ = e_{1}e_{2} ⋯ in G such that (L(e_{1}), L(e_{2}), …) = d_{R,−β}^{∗}(ℓ_{a}). By Theorem 17, d_{R,−β}^{∗}(ℓ_{a}) is the smallest sequence with respect to the order ≺ starting with a and hence ξ is the path that first chooses the edge with label a and then the edge with the smallest possible label (with respect to ≺). Since G is finite, the path ξ passes some vertex v infinitely often. Hence, ξ contains a loop of even length, which implies that for some k, n ≥ 1 we have L(e_{i}) = L(e_{i+2k}). It follows that d_{R,−β}^{∗}(ℓ_{a}) is eventualy periodic.

Conversely, let S_{L,−β} be given, G the labeled graph that follows from our construction and let L_{S} and L_{G} be the language of the shift space S_{L,−β} and the edge shift on G respectively. By Corollary 18 and the construction of G it immediately follows that L_{S} ⊂ L_{G}. If (a_{1}, …, a_{n}, d) ∉ L_{S} and (a_{1}, …, a_{n}) ∈ L_{S} (we may assume this without loss of generality), then from Corollary 18 it follows that either m_{a}^{ℓ}(i/d) or m_{a}^{r}(i/d) equals F for some i and a. Hence, by construction, there is a finite path ζ = (e_{1}, …, e_{n}) such that L(e_{i}) = a_{i}. Say the path ζ ends at vertex v, then there is no outgoing edge from v with label d. For if it did exist, it would point to a vertex with label F as one of its coordinates by (7). Such vertices, however, do not exist (recall step 1 of the construction). It follows that L_{S} = L_{G}.

Remark 20. The construction of the labeled graph is also valid if at least one boundary sequence is not eventually periodic. In this case, the upper bound U_{a}^{ℓ} or U_{a}^{r} corresponding to this boundary sequence, as well as p for this specific boundary sequence, should be equal to ∞ (as there is no periodicity to exploit). Using our construction, the number of vertices in the labeled graphs of these shifts might be countably infinite.

Let us illustrate the results of this section with two examples.

Example 21. We continue the case of Example 3. In Examples 5 and 11 we determined the boundary sequences and hence, by Theorem 4.2, a sequence belongs to the shift space S_{−β} if and only if

(\overline{1, 0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (1, 1, \overline{0}) ∨ (0, 0, 1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (\overline{0, 1})

holds for all n ≥ 1. We can simplify this as

(x_{n}, x_{n+1}, …) ⪯ (1, 1, \overline{0}) ∨ (0, 0, 1, \overline{0}) ⪯ (x_{n}, x_{n+1}, …),  (8)

since the other two inequalities are always satisfied, as (\overline{1, 0}) and (\overline{0, 1}) are the smallest and the greatest sequences with respect to the alternate order respectively. It is useful to create tables stating all possible outcomes of m_{a}^{ℓ}(i/d) and m_{a}^{r}(i/d) for all a, d ∈ A and all allowed indices i. In this specific case, we find:

\begin{matrix}m_{0}^{ℓ}(i/d) & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 2 & 0 \\ 2 & 0 & 3 \\ 3 & 4 & 0 \\ 4 & 3 & F \end{matrix}  \begin{matrix}m_{1}^{r}(i/d) & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 2 \\ 2 & 3 & 0 \\ 3 & 2 & F \end{matrix}

The entries labeled F correspond to forbidden blocks, though not all forbidden blocks can be found explicitly this way. We see that m_{0}^{ℓ}(4/1) = F, which means we can find a forbidden block by taking the prefix of length 4 of d_{R,−β}^{∗}(2 − \sqrt{5}) and adding a fifth digit to it, in this case 1. So, (0, 0, 1, 0, 1) is a forbidden block, which is clear from (8). Similarly, m_{1}^{r}(3/1) = F tells us that (1, 1, 0, 1) is a forbidden block. Figure 3 shows the labeled graph recognizing the shift space.

Example 22. Now consider the map given in Example 7. By Example 10, d_{R,−β}^{∗}(0) = (0, 1, \overline{1, 0}), and thus a sequence belongs to the shift space generated by this map if and only if

(x_{n}, x_{n+1}, …) ⪯ (1, \overline{1, 0}) ∨ (0, 1, \overline{1, 0}) ⪯ (x_{n}, x_{n+1}, …)  (9)

holds for all n ≥ 1. Once again, we omitted two inequalities since they are redundant. We can proceed as in the previous example and create the following tables:

\begin{matrix}m_{0}^{ℓ}(i/d) & 0 & 1 \\ 0 & 1 & 0 \\ 1 & F & 2 \\ 2 & 0 & 3 \\ 3 & 2 & 0 \end{matrix}  \begin{matrix}m_{1}^{r}(i/d) & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 2 \\ 2 & 1 & 0 \end{matrix}

The tables now only reveal one forbidden block: (0, 0). As we will see in a later section, this is the only forbidden block. For the moment, assume we are not aware of this. We construct a labeled graph that recognizes the shift based on our lengthy exposition earlier. This graph is shown in Figure 4.

{0 \atop 0} {1 \atop 0} {0 \atop 1} {1,2 \atop 0} {3 \atop 1} {1,4 \atop 0} {1,2,3 \atop 0} {1,2,4 \atop 0} {0 \atop 1,2} {1 \atop 3} {1,2 \atop 2} {1,2 \atop 3} 01010101010010010010

Figure 3: A labeled graph recognizing the shift space given by (8).

As in the case of expansions in positive base, whenever β is Pisot we can improve Theorem 19 a little. Recall that a Pisot number is a positive algebraic integer whose other conjugates lie in the unit circle in the complex plane. The following theorem shows why Pisot bases are nice to work with.

Theorem 23. Let β be Pisot, x ∈ I_{−β} and T_{−β} be given and let d_{−β}(x) be the (−β)-expansion of x generated by T_{−β}. If x ∈ ℚ(β), then d_{−β}(x) is eventually periodic.

Proof. We will not give the complete proof here, as it is nearly identical to the proof of [5, Theorem 24]. In our case, replace [l, r) with I_{−β} and note that we have the bound |r_{n}| < \frac{β·⌊β⌋}{β^{2}−1}.

As an immediate corollary, we have:

Theorem 24. Let β be Pisot and S_{−β} be given. Then S_{−β} is sofic if and only if the cut points of the underlying map T_{−β} all lie in ℚ(β).

5 Forbidden blocks

Example 22 showed that, while technically correct, our construction of the labeled graph can yield us quite large graphs. However, by carefully looking at Examples 21 and 22 we see why the first one is only sofic and the latter is actually a shift of finite type. In the first example, the forbidden blocks contain both a part of the pre-periodic and a part of the periodic part of the boundary sequence, where in the second example the forbidden block only contained part of the pre-periodic part. This observation quickly leads us to a conjecture: a shift space of the form given in Theorem 17 is a shift of finite type if and only if its forbidden blocks only contain part of either pre-periodic or periodic parts of boundary sequences, but not both. Indeed, if the latter does happen, we can abuse the periodicity of the boundary sequences

{0 \atop 0} {1 \atop 0} {0 \atop 1} {0 \atop 1,2} {1 \atop 1} {2 \atop 1} {2 \atop 1,2} {3 \atop 1,2} {1,2 \atop 1} {2,3 \atop 1,2} 01101011010101101

Figure 4: A labeled graph recognizing the shift space given by (9).

to generate infinitely many forbidden blocks that cannot be covered by a finite set (because of the pre-periodic part). Based on these observations, we state the following

Theorem 25. Let S_{−β} be a sofic shift. Then S_{−β} is a shift of finite type if and only if the periodic part of every eventually periodic boundary sequence is a purely periodic boundary sequence.

Proof. Once again, we assume that the underlying map is left-continuous and write S_{L,−β} instead of S_{−β}. Let S_{L,−β} be a shift of finite type. Every shift of finite type is sofic and hence by Theorem 19 we conclude that all boundary sequences are eventually periodic. Assume that there exists a left-boundary sequence (the proof is similar for right-boundary sequences) (a_{1}, …, a_{k}, \overline{a_{k+1}, …, a_{k+p}}), where k, p ≥ 1, whose periodic part does not equal some other boundary sequence. Moreover, assume that k is odd (the proof is similar for k even). By assumption, there exists a smallest integer 1 ≤ j ≤ p such that there exists some b ∈ A for which we have (−1)^{k+j}(b−a_{k+j}) < 0. It follows that the block (a_{1}, …, a_{k+j−1}, b) is forbidden. Moreover, the blocks w^{(n)} := a_{1} ⋯ a_{k}(a_{k+1} ⋯ a_{k+p})^{2n}a_{k+1} ⋯ a_{k+j−1}b are forbidden for all n ≥ 0.

Suppose that there exists some 1 ≤ i ≤ j − 1 such that the subblock a_{k+i} ⋯ b of length at most j is forbidden. Then the blocks (a_{k+1} ⋯ a_{k+p})^{2n}a_{k+1} ⋯ a_{k+j−1}b are forbidden for all n ≥ 0 and thus we conclude that

(\overline{a_{k+1} ⋯ a_{k+p}}) ≺ (a_{k+1} ⋯ a_{k+p})^{2n}a_{k+1} ⋯ a_{k+j−1}b

holds for all n ≥ 1. This, however, implies that (\overline{a_{k+1}, …, a_{k+p}}) is a right-boundary sequence, which contradicts our initial assumption. Hence, there exists some integer 1 ≤ m ≤ k such that the blocks a_{m} ⋯ a_{k}(a_{k+1} ⋯ a_{k+p})^{2n}a_{k+1} ⋯ a_{k+j−1}b are forbidden for all n ≥ 0, but any of their subblocks are admissible. Hence, S_{−β} is not a shift of finite type.

Next, assume that all boundary sequences satisfy the property given in Theorem 25 and let (a_{1}, a_{2}, …) be an arbitrary but fixed left-boundary sequence (the proof is similar for right-boundary sequences). If it is purely periodic with period p, then the forbidden blocks are given by

{(x_{1}, …, x_{2p}) ∈ A^{2p} : (x_{1}, …, x_{2p}) ≺ (a_{1}, …, a_{2p}) ∧ x_{1} = a_{1}} .  (10)

If it is eventually periodic with pre-periodic part of length q and period p, then the set

{(x_{1}, …, x_{q+1}) ∈ A^{q+1} : (x_{1}, …, x_{q+1}) ≺ (a_{1}, …, a_{q+1}) ∧ x_{1} = a_{1}}  (11)

is sufficient. To see why, let (y_{1}, y_{2}, …) be a sequence such that y_{1} = a_{1} and (y_{1}, y_{2}, …) ≺ (a_{1}, a_{2}, …). Let m be the smallest integer such that y_{i} = a_{i} for i < m and (−1)^{m}(y_{m}−a_{m}) < 0 and assume that m > q + 1. Moreover, assume that q is odd (the argument is similar for q even). Then y_{1} ⋯ y_{q+1} = a_{1} ⋯ a_{q+1} and

(\overline{a_{q+1}, …, a_{q+p}}) ≺ (y_{k+1}, y_{k+2}, …).

Since the purely periodic sequence on the left-hand side is another boundary sequence, it follows that the forbidden blocks of (y_{1}, y_{2}, …) are contained within the subsequence (y_{q+1}, y_{q+2}, …). But these forbidden blocks are already covered by a set of the form (10). Hence, it is sufficient to consider forbidden blocks of the form in (11). Since there are finitely many boundary sequences and since each of these boundary sequences only have a finite number of forbidden blocks, the shift space is a shift of finite type.

We can use the result of this theorem to reduce our graphs quite a bit as follows. Consider any boundary sequence. If its periodic part is a boundary sequence of the same shift space, then remove this periodic part. If our memory contains the whole pre-periodic part of this boundary sequence, then accept it and forget about it (i.e., the new memory index in this specific case would be a zero). The following two examples illustrate this.

Example 26. Reconsider Example 22. Since (\overline{1, 0}) is a boundary sequence (the smallest with respect to ≺), we can forget about this periodic part. Moreover, this turns (1, \overline{1, 0}) into the single digit boundary block (1), which itself is redundant, and hence we are left with the following condition:

(0, 1) ⪯ (x_{n}, x_{n+1})

for all n ≥ 1 such that x_{n} = 0. Although not necessary at this point, we still fill in the table:

\begin{matrix}m_{0}^{ℓ}(i/d) & 0 & 1 \\ 0 & 1 & 0 \\ 1 & F & 0 \end{matrix}

The resulting graph is shown in Figure 5.

The same approach can be applied to any shift space of the form in Theorem 17 as long as at least one eventually periodic boundary sequence has a periodic part equal to a periodic boundary sequence.

0 1 1 0 1

Figure 5: Another labeled graph recognizing the shift space of Example 22.

Example 27. Let β = 2 and consider the left-continuous map with cut points −\frac{5}{6} and −\frac{1}{6}. Theorem 17 tells us that (x_{1}, x_{2}, …) ∈ S_{−β} if and only if for all n ≥ 1 we have:

(\overline{2, 0}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (2, \overline{1}),
(1, \overline{0, 2}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (1, \overline{1, 0}),
or (0, \overline{0, 1}) ⪯ (x_{n}, x_{n+1}, …) ⪯ (\overline{0, 2}).

Careful inspection reveals that the boundary sequences (\overline{2, 0}) and (\overline{0, 2}) are redundant (the smallest and largest possible sequence with respect to ≺). Moreover, we may reduce (1, \overline{0, 2}) to the single digit block (1), which is once again redundant. We are left with:

\begin{cases}(x_{n}, x_{n+1}, …) ⪯ (2, \overline{1}), & whenever x_{n} = 2; \\ (x_{n}, x_{n+1}, …) ⪯ (1, \overline{1, 0}), & whenever x_{n} = 1; \\ (0, \overline{0, 1}) ⪯ (x_{n}, x_{n+1}, …), & whenever x_{n} = 0. \end{cases}  (12)

We create tables one more time:

\begin{matrix}m_{0}^{ℓ}(i/d) & 0 & 1 & 2 \\ 0 & 1 & 0 & 0 \\ 1 & 2 & 0 & 0 \\ 2 & 0 & 1 & F \end{matrix} \begin{matrix}m_{1}^{r}(i/d) & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 2 & F \\ 2 & 1 & 0 & 0 \end{matrix} \begin{matrix}m_{2}^{r}(i/d) & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 2 & F \\ 2 & F & 1 & 0 \end{matrix}

and use these to produce the labeled graph in Figure 6.

6 Discussion

Our goal was to consider a large class of (−β)-transformations and to prove statements analogous to what Ito and Sadahiro for their (−β)-transformation. Our class of (−β)- transformations include transformations that, when restricted to the interval [−\frac{β}{β+1}, \frac{1}{β+1}), are the Ito-Sadahiro transformation. As to be expected, our results agree with results on their transformation (compare Theorem 14 and 19 with [8, Theorem 10 & 12] and Theorem 25 with [7, Theorem 4]). While we only considered the canonical alphabet, there are many other alphabets to be considered. In fact, there is a rather large class of alphabets satisfying property i of Assumption 1 (compare with [11, Proposition 2.1]) of which we assume the results in this paper will carry over.

Of the many open problems surrounding (−β)-expansions we want to highlight two. The first problem is based on the examples in sections 4 and 5 illustrating the output of our algorithm. Can this algorithm be improved upon? The second problem follows from [8]: given two sequences x, y ∈ A^{ℕ} (or any other alphabet), is there a (−β)-transformation such that x and y are boundary sequences of this transformation?

References

[1] K. Dajani and C. Kalle, Transformations generating negative β-expansions, Integers 11B (2011).

[2] K. Dajani and C. Kraaikamp, From greedy to lazy expansions and their driving dynamics, Expo. Math. 20 (2002), 315–327.

[3] K. Dajani and C. Kraaikamp, Random β-expansions, Ergodic Theory Dynam. Systems 23 (2003), 461–479.

[4] K. Dajani and M. de Vries, Measures of maximal entropy for random β-expansions, J. Eur. Math. Soc. (JEMS) 7 (2005), 51–68.

[5] D. Dombek, Z. Masáková, and E. Pelantová, Number representation using generalized (−β)-transformation, Theoret. Comput. Sci. 412 (2011), 6653–6665.

[6] P. Erdős and I. Joó, On the expansion 1 = ∑ q^{−n_{i}}, Period. Math. Hungar. 23 (1991), 27–30.

[7] C. Frougny and A. C. Lai, On negative bases, in Proc. DLT 09, Lecture Notes in Comp. Sci., Vol. 5583, Springer, 2009, pp. 252–263.

[8] S. Ito and T. Sadahiro, Beta-expansions with negative bases, Integers 9 (2009), 239–259.

[9] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.

[10] W. Parry, On the β-expansions of real numbers, Acta. Math. Acad. Sci. Hung. 11 (1960), 401–416.

[11] M. Pedicini, Greedy expansions and sets with deleted digits, Theoret. Comput. Sci. 332 (2005), 313–336.

[12] A. Rényi, Representations for real numbers and their ergodic properties, Acta. Math. Acad. Sci. Hung. 8 (1957), 477–493.

2010 Mathematics Subject Classification: Primary 37B10; Secondary 11A63. Keywords: (−β)-expansions, sofic shift, shift of finite type.

Received October 10 2011; revised version received January 11 2012. Published in Journal of Integer Sequences, January 14 2012.

Return to Journal of Integer Sequences home page.

0 0 0 0 1 0 1 0 0 0 0 1 0 1 2 \begin{matrix}0 \\ 1, 2 \\ 2 \end{matrix} \begin{matrix}0 \\ 1, 2 \\ 1 \end{matrix} \begin{matrix}0 \\ 1, 2 \\ 0 \end{matrix} \begin{matrix}1, 2 \\ 0 \\ 0 \end{matrix} 1 1 0 01210011201011011010

Figure 6: A labeled graph recognizing the shift from Example 27.