SUBSTITUTIONS, ABSTRACT NUMBER SYSTEMS AND THE SPACE FILLING PROPERTY

CLEMENS FUCHS^{∗} AND ROBERT TIJDEMAN

Abstract. In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function mod 1 and that it can be decided whether the resulting word is space filling or not. The proof uses continued lattices and the abstract number system associated with the substitution.

2000 Mathematics Subject Classification: Primary: 11A63, 68R15, 37B10; Secondary: 05A05, 05B25, 52C07, 52C22, 68Q45, 11K16. Keywords: substitutions, limit word, discretisation of the hyperplane, lattices, automata, abstract number systems

1. Introduction

In 1982 Rauzy [32] introduced the Rauzy fractal as a closure of an infinite sequence of points. He proved that the three parts composing it have disjoint interiors with area 1 and that it forms a tile of ℝ^{2} with very nice properties. Since then many researchers have studied the corresponding structures for other substitutions, with quite diverse outcomes (cf. [2, 5, 37, 41, 15, 4, 17, 39, 23, 44]), but a general rule for deciding when a substitution leads to simple tiling of a space is still wanted, especially, because these structures turned out to be useful in the mathematical theory of quasicrystals (for details see [38, 7, 22, 9]). The authors want to reveal some of the underlying principles and thereby to pave the way to a satisfying answer.

The present paper is a generalization of some phenomena which were observed in the special case of the Tribonacci substitution σ : {0, 1, 2} → {0, 1, 2} given by σ(0) = 01, σ(1) = 02, σ(2) = 0 by Rosema and Tijdeman [35]. The repeated application of the substitution σ with as start value 0 and concatenation as operation yields a sequence of finite words: u^{(0)} = 0, u^{(1)} = 01, u^{(2)} = 0102, u^{(3)} = 0102010, u^{(4)} = 0102010010201, …. The limit word U := 010201001020101020100102010201001020101 … is called the fixed point of σ. An important role in the analysis is played by the incidence matrix M_{σ} of σ, the row vectors of which are the incidence vectors of σ(0), σ(1), σ(2), respectively, hence in the present case (1, 1, 0), (1, 0, 1) and (1, 0, 0). Its characteristic polynomial equals x^{3} − x^{2} − x − 1. It has one real root β with modulus greater than one and two complex roots with modulus smaller than 1. The eigenvectors corresponding to the eigenvalue β of M_{σ} equal ℝ(β^{2}, β, 1). From the word U a sequence of points in ℤ^{3} is constructed by putting P_{0} = 0 and P_{m+1} = P_{m} + e⃗_{i} for m = 0, 1, 2, … if and only if the letter of U at the position m equals i where e⃗_{i} denotes the i-th unit vector. So P_{1} = (1, 0, 0), P_{2} = (1, 1, 0), P_{3} = (2, 1, 0), P_{4} = (2, 1, 1), P_{5} = (3, 1, 1), …. These points approximate the line ℝ(β^{2}, β, 1) very well. If the points P_{m} (m = 0, 1, …) are projected parallel to this line on a plane, then the famous Rauzy fractal is formed [32]. Instead Rosema and Tijdeman projected the points P_{m} generated by each word u^{(n)} parallel to the line through the starting point P_{0} and the end point P_{m}, where m is equal to the length of u^{(n)}, on the (y, z)-plane. This leads to a sequence of structures which have the Rauzy fractal as a limit. However, by applying a suitable linear transformation depending on n to the n-th structure, an increasing sequence of two-dimensional words (w^{(n)})_{n≥0} was obtained. It was shown that the derived limit word has the full lattice ℤ^{2} as domain (so it was space-filling) (cf. [35, Theorem 4.7]). Moreover, the normalized value of the word at some lattice point is determined by a linear function modulo 1 (cf. [35, Theorem 4.7]) and the development of the projected words is fully reflected by some two-dimensional representation of the Tribonacci number system (cf. [35, Lemma 4.6]).

Date: August 31, 2005.

∗The first author was supported by the Austrian Science Foundation FWF, grant J2407-N12.

The present paper deals with an arbitrary given substitution σ mapping {0, 1, …, k} to finite words in these letters. We assume that σ has an invariant word starting with 0. In Section 2 we define the incidence matrix M_{σ}, we derive recurrence relations for its entries and show that the growth order of these entries is determined by the eigenvalues with largest modulus. We make the assumption that M_{σ} has a dominant eigenvalue β and that all the components of the corresponding eigenvector are positive. Finally, we define the corresponding broken halfline in ℝ^{k+1}. The results in this section are based on the classical Perron-Frobenius theorem.

In Section 3 we define the projection of the integer points on the broken halfline to some hyperplane. We leave the subsequent linear transformation free, but mention some natural choices. One of them, called canonical, leads to simplified formulas. We make the further assumption that the incidence matrix M_{σ} is unimodular. Theorems 2 and 3 describe the structure of the projected word w^{(n)}. We define the normalized word ŵ^{(n)} and show in Theorem 4 that the limit word Ŵ has a linear structure mod 1. The method in this section is taken from Berthé and Tijdeman [10].

In Section 4 we define the automaton, the language and the number system associated to σ. We make a further assumption that β > 1. We show that the corresponding eigenvector plays a fundamental role in the description of the number system. We present an algorithm to compute the representation of an arbitrary number from [0, 1) in this number system. Theorem 4 shows that we have a bijection between the half-open interval [0, 1) and the infinite words in the associated language. Theorem 5 gives a certain finiteness criterion, provided that β is a Pisot number and states on the other hand that if all elements in ℤ[β^{−1}] ∩ [0, 1) have a finite expansion, then β is a Pisot number or a Salem number. It is remarkable that this criterion (in the Pisot case) is finite and can be checked effectively. In our analysis of associated number systems we rely on results of Frougny and Solomyak [20] and Akiyama [1].

The results from Sections 2, 3 and 4 are combined in Section 5. Theorem 6 describes the relation between the word w^{(n)} and the number system associated with σ. It turns out that w^{(n)} consists exactly of the words in the associated language of length at most n. Theorem 7 gives a criterion for the limit word Ŵ to be space filling. As before the criterion is decidable if β is a Pisot number. If Ŵ is space filling, then the dimension of the space filling word Ŵ equals degβ − 1.

In the final Section 6, we give five examples. Example 1 concerns a substitution on three letters leading to a two-dimensional space filling word. Example 2 deals with the flipped Tribonacci substitution which yields a word which is not space filling. Example 3 treats a substitution on three letters with a dominant root of degree 2 and a resulting space filling word of dimension 1. Example 4 shows how a substitution on five letters with a dominant root of degree 3 and two roots of modulus 1 generates a space filling word of dimension 2. Finally, Example 5 is concerned with a substitution on four letters with a dominant Pisot root of degree 2 and two other roots, one outside and one inside the unit circle, that generates a one-dimensional word which is not space filling.

Finally we note that some of the made assumptions are just for convenience, but that this is not the case for the assumptions that M_{σ} is unimodular and has a dominant root β > 1 and that all components of the corresponding eigenvector are positive.

2. Limit word and discretisation of the hyperplane

Let Σ be a finite set. By Σ^{∗} we denote the set of finite words over the alphabet Σ including the empty word ε. A substitution is a map σ : Σ → Σ^{∗}\{ε}. This map can be extended to a map σ : Σ^{∗} → Σ^{∗} by letting σ(ε) = ε and σ(ws) = σ(w)σ(s) for w ∈ Σ^{∗}, s ∈ Σ where as usual the operation is the concatenation of words. (With this operation the set Σ^{∗} is a free monoid with identity ε generated by Σ.) We denote by |w| the length of the word w ∈ Σ^{∗}, i.e. |w| = n if w ∈ Σ^{n}. Moreover, we set |w|_{s} for w ∈ Σ^{∗}, s ∈ Σ to be the number of occurrences of letter s in the word w. Hence ∑_{s∈Σ} |w|_{s} = |w|. The column vector w⃗ whose components are the quantities |w|_{s} for s ∈ Σ is called the incidence vector of the word w. In the paper the vectors are defined as column vectors and row vectors are presented as transposed vectors. Transposition is denoted by a left superscript t.

Let ℕ denote the non-negative integers and Σ^{ω} the set of right-infinite words over the alphabet Σ, i.e. the set of sequences of letters from Σ indexed by non-negative integers. We equip Σ^{ω} with the usual discrete product metric: for V, W ∈ Σ^{ω} we set d(V, W) = 2^{−i}, where i is the smallest integer such that V_{i} ≠ W_{i} (V = (V_{n})_{n∈ℕ}, W = (W_{n})_{n∈ℕ}) if such an index exists and i = ∞ if V = W. Convergence of sequences is considered with respect to this metric. Observe that any finite word w ∈ Σ^{∗} can be viewed as an infinite word wζ^{ω} ∈ (Σ ∪ {ζ})^{ω} for some ζ ∉ Σ. So a sequence (w^{(n)})_{n≥0} of finite words converges to an infinite word W if and only if for every l ∈ ℕ there exists an N_{l} ∈ ℕ such that the first l letters of W and w^{(n)} coincide for every n ≥ N_{l}. We denote by (w)_{i} the letter at position i in the finite or infinite word w.

We can extend σ to W = (W_{n})_{n∈ℕ} in Σ^{ω} by putting σ(W) = (σ(W_{n}))_{n∈ℕ} and applying infinite concatenation. Observe that if (w^{(n)})_{n≥0} converges to W ∈ Σ^{ω} then (σ(w^{(n)}))_{n≥0} converges to σ(W). We say that a finite or infinite word w is a fixed point of the substitution σ if σ(w) = w.

In the sequel we will always assume Σ = {0, 1, …, k} and consider the sequence (u^{(n)})_{n≥0} given by

u^{(n)} = σ^{n}(0) (n = 0, 1, …).

Suppose the sequence u = (u^{(n)})_{n≥0} converges to a limit word U = (U_{n})_{n∈ℕ} which is a fixed point of the substitution σ. By relabeling the alphabet Σ we may assume that U_{0} = 0. Since by definition there exists a N_{1} such that U_{0} = (u^{(n)})_{0} for all n ≥ N_{1}, it follows that (σ((u^{(n)})_{0}))_{0} = (u^{(n+1)})_{0}. Therefore, we have that

(A1)  σ(0) = 0v, v ∈ Σ^{∗}.

For the sake of simplicity we will always assume that the substitution σ satisfies (A1). Therefore U := lim_{n→∞} u^{(n)} is a well-defined infinite word U_{0}U_{1}U_{2} ⋯ with U_{0} = 0.

Let

u⃗_{n} = ^{t}(|σ^{n}(0)|_{0}, …, |σ^{n}(0)|_{k})

be the so-called incidence vector of u^{(n)} = σ^{n}(0) and

v⃗_{n} = ^{t}(|σ^{n}(0)|, …, |σ^{n}(k)|).

Of special interest is the first coordinate of v⃗_{n}, which generates the sequence of lengths (|u^{(n)}|)_{n∈ℕ} of the sequence (u^{(n)})_{n≥0}. Put s^{(n)} = |u_{n}| for n ∈ ℕ. We will discuss the convergence of the vectors u⃗_{n}/|u^{(n)}|. Define the incidence matrix M_{σ} of the substitution σ by

M_{σ} = (|σ(i)|_{j})_{i=0,...,k;j=0,...,k} ∈ ℕ^{(k+1)×(k+1)}.

The incidence matrix contains the global information (the numbers of each letter) of the substitution σ, but not the local information (the precise order). Let x^{k+1} − g_{k}x^{k} − ⋯ − g_{0} be the characteristic equation of M_{σ}. Then M_{σ}^{k+1} = g_{k}M_{σ}^{k} + ⋯ + g_{0}M_{σ}^{0} where g_{k}, …, g_{0} are rational integers.

It is easy to see that both sequences u⃗_{n} and v⃗_{n} satisfy a linear recurrence relation where M_{σ} is involved. We have

(1)  ^{t}u⃗_{n}M_{σ} = ^{t}u⃗_{n+1} and M_{σ}v⃗_{n} = v⃗_{n+1},

respectively. Hence

u⃗_{n+k+1} = g_{k}u⃗_{n+k} + ⋯ + g_{0}u⃗_{n}

and similarly for v⃗_{n}. Therefore the components of the vectors u⃗_{n}, v⃗_{n} satisfy the linear recurrence relation. In particular, s^{(n+k+1)} = g_{k}s^{(n+k)} + ⋯ + g_{0}s^{(n)} (n = 0, 1, …). Denoting by e_{0}^{(k+1)}, …, e_{k}^{(k+1)} the unit column vectors in ℝ^{k+1}, it follows by induction on n that ^{t}M_{σ}^{n}e_{0}^{(k+1)} is the incidence vector of u^{(n)}, hence s^{(n)} is the sum of the entries in the row with index 0 of M_{σ}^{n}. More generally we have

Lemma 1. Let n ≥ 0 and i ∈ {0, 1, …, k}. Then the i-th row vector of M_{σ}^{n} equals

(|σ^{n}(i)|_{0}, |σ^{n}(i)|_{1}, …, |σ^{n}(i)|_{k})

and the vector of the row sums of M_{σ}^{n} equals v⃗_{n}.

Proof. The assertion holds by definition for n = 0. Suppose the statement holds for n. Then the i-th row vector of M_{σ}^{n+1} equals

te_{i}^{(k+1)}M_{σ}^{n+1} = ^{t}e_{i}^{(k+1)}M_{σ}^{n}M_{σ} = ∑_{j=0}^{k} |σ^{n}(i) |_{j} ^{t}e_{j}^{(k+1)}M_{σ}

= (∑_{j=0}^{k} |σ^{n}(i)|_{j}|σ(j)|_{0}, …, ∑_{j=0}^{k} |σ^{n}(i)|_{j}|σ(j)|_{k})
= (|σ^{n+1}(i)|_{0}, …, |σ^{n+1}(i)|_{k}).

A similar argument proves the second part of the lemma. □

Furthermore, we have the following lemma (where as usual we use the notation f(x) = o(g(x)) for f(x)/g(x) → 0 if x → ∞).

Lemma 2. There exist an algebraic integer β ≥ 1, a p ∈ ℕ and vectors P⃗_{j}, Q⃗_{j} (j = 0, 1, …, p − 1) with entries from ℚ(βξ_{p})[x] such that

u⃗_{n} = ∑_{j=0}^{p−1} P⃗_{j}(n)(ξ_{p}^{j}β)^{n} + o (β^{n}) , v⃗_{n} = ∑_{j=0}^{p−1} Q⃗_{j}(n)(ξ_{p}^{j}β)^{n} + o (β^{n}) ,

where ξ_{p} denotes a primitive p-th root of unity.

Proof. The result follows immediately from the Perron-Frobenius Theorem [8, Theorem 1.4.4] if the incidence matrix M_{σ} is irreducible (cf. [8, p. 2]). If M_{σ} is not irreducible, we can write it (after a relabeling of the alphabet not involving 0) as an upper diagonal block matrix. We denote the square blocks along the diagonal by M_{1}, …, M_{r} with M_{1}, …, M_{r} irreducible. Since the characteristic polynomial of such a block matrix is given by the product of the characteristic polynomials of the M_{k}, it suffices to consider them. Observe that since all the matrices M_{k} have non-negative integral entries it follows that the characteristic roots are algebraic integers and therefore at least one of the characteristic roots is ≥ 1. Now by the Perron-Frobenius Theorem for irreducible non-negative matrices [8, Theorem 1.4.4] it follows that all the characteristic roots of maximum modulus of the matrices M_{k} are given by ξ_{p_{k}}^{h}β_{k} (h = 0, …, p_{k} − 1) for some p_{k} ∈ ℕ and real algebraic integers β_{k} ≥ 1. By the theory on recurrences, u⃗_{n} and v⃗_{n} can be expressed as an exponential polynomial with the roots of the characteristic polynomial as base variables. Put β = max{β_{k} : k = 1, …, r} and p = ∏_{|β_{k}|=β} p_{k}. Then all the terms in the expressions for u⃗_{n} and v⃗_{n} are absorbed in the error term o(β^{n}) except for the base values of the form ξ_{p}^{h}β. The fact that the components of the coefficient-vectors P⃗_{j}, Q⃗_{j} are in the field generated by βξ_{p} over ℚ follows by considering the generating functions of the components, which leads to rational functions with integer coefficients since the vectors u⃗_{n} and v⃗_{n} have integral components, and by using the partial fractal decomposition afterwards. □

Observe that the result recovers part of a result of Lind [24, 25] who characterized for which matrices with entries in ℕ the spectral radii are Perron numbers. (A Perron number is a real algebraic integer which is larger than all its conjugates.)

From the lemma it follows that if we split the sequence (u^{(n)})_{n≥0} according to the arithmetic progressions n = mp + j with j = 0, …, p − 1, then the incidence matrix M_{σ} for each progression has a dominant root β^{p} ≥ 1. Moreover, there exists a monic polynomial P (x) ∈ ℚ(β)[x] such that the limits

(2)  lim_{n→∞} \frac{|σ^{np+i}(j)|}{P (np + i)β^{np+i}} =: a_{j}(i)

exist for all j = 0, …, k; i = 0, …, p − 1. Furthermore, we get that

lim_{n→∞} \frac{u⃗_{np+i}}{|u_{np+i}|} =: b⃗(i)

exist for all i = 0, …, p − 1. Observe that this need not hold if we replace p with 1, e.g. it does not for a substitution with incidence matrix

( \begin{matrix}1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{matrix} ) ,

which has the characteristic equation

β^{5} − β^{4} − β^{3} + β^{2} − β + 1 = (β − 1)(β^{2} − ρ^{2})(β^{2} − ρ^{−2}) = 0

where ρ = (1 + \sqrt{5})/2.

We simplify the formulas by studying the arithmetic progressions with difference p separately. In the sequel we will assume that

(A2)  M_{σ} has a dominant eigenvalue β,

so p = 1. We denote a_{j}(0), b⃗(0) by a_{j}, b⃗, respectively.

Fig. 1: Broken halfline segment associated to u^{(4)}= 0120001010120 for the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0.

It is clear that the vector a⃗ := ^{t}(a_{0}, …, a_{k}) is an eigenvector of M_{σ} and the vector b⃗ is an eigenvector of ^{t}M_{σ}, both to the eigenvalue β. In particular the sequence u^{(n)}/|u^{(n)}| of normed incidence vectors converges to b⃗.

We remove all letters from Σ which do not appear in the limit word U, since they do not play a role in the further investigations. (This will lead to a trim automaton associated to σ in Section 4.) Moreover, we remove all letters j for which a_{j} = 0. Observe that such letters can appear infinitely often in U, as e.g. the letter 2 in σ(0) = 012, σ(1) = 111, σ(2) = 2. We assume that

(A3)  a_{j} > 0 for all j = 0, …, k.

This implies that all sequences (|σ^{n}(j)|)_{n≥0} have the same growth order.

The limit word U of the sequence (u^{(n)})_{n≥0} = (σ^{n}(0))_{n≥0} generates a broken halfline in ℝ^{k+1} in the following way: we start in 0 and for n = 0, 1, … go 1 in the direction of the x_{i}-axis when U_{n} = i. (See Fig. 1.) It follows from the convergence of the incidence vectors of u^{(n)} that the broken halfline approximates the halfline ℝ_{≥0}b⃗.

We will study the projection of the integer points on the broken halfline to some hyperplane not containing ℝb⃗. (Since we ignore linear transformations, we are free in our choice.) The integer points P_{m} for m ∈ ℕ on this line are given by

P_{0} = 0, P_{m+1} = P_{m} + e_{U_{m}}^{(k+1)},

We project each integer point parallel to the halfline ℝ_{≥0}b⃗ to the hyperplane and want to understand the structure of the projections. In general this problem is hard, because the projections form fractals (e.g. the Rauzy-fractal [32] in case we start with the Tribonacci substitution). As in [35] in the Tribonacci case we first investigate the local behaviour by considering for every n ∈ ℕ the projections along the broken line segment through 0 and P_{m} = u⃗_{n} where m = s^{(n)}. In the next section we will show that if we use a suitable transformation after applying the projection, then the images lie in the lattice ℤ^{k}.

3. Continued lattices

We start by defining a linear mapping Φ_{n} which projects the integer points on the broken halfline segment associated to u^{(n)} to some hyperplane not containing the incidence vector u⃗_{n}. Recall that u⃗_{n} = ^{t}M_{σ}^{n}e_{0}^{(k+1)} by Lemma 1 (see the shaded line in Fig. 1). Hence

(3)  Φ_{n}(P_{s^{(n)}}) = Φ_{n} (^{t}M_{σ}^{n}e_{0}^{(k+1)}) := 0.

Let c⃗_{1}, … c⃗_{k} be such that the vectors ^{t}M_{σ}^{k}e_{0}^{(k+1)}, c⃗_{1}, …, c⃗_{k} form a basis of the lattice ℤ^{k+1}. Then we define, for n ≥ k,

(4)  Φ_{n} (^{t}M_{σ}^{n−k}c⃗_{i}) := e_{i}^{(k)} (i = 1, …, k),

where e_{i}^{(k)} denotes the i-th k-dimensional unit vector.

By assuming that

(A4)  M_{σ} is unimodular,

we secure that ^{t}M_{σ}^{n}e_{0}^{(k+1)},^{t}M_{σ}^{n−k}c⃗_{1}, …,^{t}M_{σ}^{n−k}c⃗_{k} form a basis of ℤ^{k+1} for every n ∈ ℕ. We will hold on this assumption for the rest of the paper.

6 8

10 1 5

7

9 0 4
11 2
12 3

Fig. 2: Result of the projection of the integer points on the broken halfline segment along u^{(4)} to the (x_{1}, x_{2})-plane for the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0 on the left-hand side and the image in ℤ^{2} after applying Φ_{4} with c⃗_{1} = u⃗_{0} = ^{t}(1, 0, 0), c⃗_{2} = u⃗_{1} = ^{t}(1, 1, 0) on the right-hand side.

Since we have determined the images of Φ_{n} on a basis of the lattice ℤ^{k+1} and Φ_{n} is linear, it is defined everywhere and the definition for Φ_{n} makes sense for all n ≥ 0. For short, we will call Φ_{n} itself a projection.

We may take the vectors c⃗_{i} from the points of the broken halfline corresponding to u^{(k)}. In fact we can take c⃗_{1} = e_{0}^{(k+1)}, c⃗_{2} the first point on the broken halfline, which corresponds to the place where the first letter different from 0 in u^{(k)} appears, and so forth. This is clearly valid as all k + 1 letters have to appear in u^{(k)}, since we have removed all letters which do not appear in the limit word from our alphabet. So it is possible to choose the vectors c⃗_{i} such that they are linearly independent over ℤ. The image of the broken halfline segment associated with u^{(n)} is now a subset of ℤ^{k} (cf. Fig. 2).

Observe that in general it is not possible to take

c⃗_{i} = ^{t}M_{σ}^{i−1}e_{0}^{(k+1)} = u⃗_{i−1}

for i = 1, …, k, even if M_{σ} is unimodular. E.g. the substitution σ(0) = 0112, σ(1) = 1, σ(2) = 2 has a unimodular incidence matrix, but no three consecutive vectors in the sequence u⃗_{n} are a basis of ℤ^{3}.

10 8 6

1

11 9 7 5
2 0

4 12

3

Fig. 3: Result of the projection of the broken halfline segment associated to u^{(4)} in the canonical case for the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0.

Another useful choice is

(5)  c⃗_{i} = ^{t}M_{σ}^{k}e_{i}^{(k+1)} (i = 0, 1, …, k).

In this case we can explicitly describe the corresponding projection which we will call the canonical projection Φ_{n}^{∗}. For x⃗ ∈ ℤ^{k+1} we have

(6)  Φ_{n}^{∗}(x⃗) := Π(^{t}M_{σ}^{−n}x⃗),

where Π is the projection along e_{0}^{(k+1)} and therefore means deletion of the zeroth entry. When we use this special basis, we say that we are in the canonical case. We remark that the map Φ_{n}^{∗} can be seen as a result of changing the order of projection and transformation: we can as well first apply a linear transformation and then project; as the transformation we choose left multiplication by ^{t}M_{σ}^{−n} and we project along the unit vector e_{0}^{(k+1)}.

We define

(7)  a_{i}^{(n)} := Φ_{n} (e_{i}^{(k+1)})

for i = 0, 1, …, k and call them transition vectors corresponding to u^{(n)}. Observe that these vectors tell which step we have to make in ℤ^{k} to get to the next projected point.

In the canonical case we have

(8)  a_{i}^{(n)} = Φ_{n}^{∗} (e_{i}^{(k+1)}) = Π (^{t}M_{σ}^{−n}e_{i}^{(k+1)})

and therefore the transition vectors in this case are obtained as the row vectors of M_{σ}^{−n} after deletion of their zeroth entries. In general we have the following formula to calculate them.

Lemma 3. We have

(a_{0}^{(n+1)}, …, a_{k}^{(n+1)}) = (a_{0}^{(n)}, …, a_{k}^{(n)}) ^{t}M_{σ}^{−1}

for all n ≥ 0.

Proof. By the substitution σ each jump a_{q}^{(n)} in w^{(n)} is replaced by a series of jumps a_{(σ(q))_{i}}^{(n+1)} according to the word σ(q). Therefore we get

a_{q}^{(n)} = ∑_{i=0}^{|σ(q)|−1} a_{(σ(q))_{i}}^{(n+1)} = a_{0}^{(n+1)}(σ(q))_{0} + a_{1}^{(n+1)}(σ(q))_{1} + ⋯ + a_{k}^{(n+1)}(σ(q))_{k}.

Thus, the recurrence follows from Lemma 1. □

Let P_{1}, …, P_{m} with m = s^{(n)} be the integer points on the broken halfline segment. We will define a new k-dimensional word using the projections of these points.

A k-dimensional word is a map from a subset of ℤ^{k} to some alphabet. If we have a sequence (w^{(n)})_{n≥0} of k-dimensional words, then we say that this sequence converges on A to a k-dimensional word W if for every x⃗ ∈ A there exists an integer N such that w^{(n)}(x⃗) = W (x⃗) for all n ≥ N. Observe, that words used up to now are 1-dimensional words defined on {0, 1, …, n − 1} if the word is of length n, and on the non-negative integers if it is infinite.

Now, we define w^{(n)} by setting its value at position Φ_{n}(P_{i}) equal to i for i = 0, …, m − 1. Hence w^{(n)} is a k-dimensional word with letters from ℕ, i.e.

w^{(n)} : Φ_{n}(A_{n}) ⟶ ℕ
Φ_{n}(P_{i}) ⟼ i

for i = 0, …, s^{(n)} − 1 where A_{n} consists of the integer points on the broken line segment from 0 to u⃗_{n}. Put L = ∑_{q∈Σ}{|σ(q)|−1}. We have the following

Theorem 1. The sequence of words w = (w^{(n)})_{n∈ℕ} is well-defined. The domain of w^{(n+1)} is contained in the union of the domain of w^{(n)} and at most L translates of the domain of w^{(n)}. Moreover, in the canonical case the projections of P_{m} in w^{(n)} will be the projections of ^{t}M_{σ}P_{m} in w^{(n+1)} for m = 0, 1, …, s^{(n)}−1 and σ^{n+1}(0)−σ^{n}(0) new points are added.

Proof. Suppose Φ_{n}(P_{i}) = Φ_{n}(P_{j}). By the linearity of Φ_{n} it follows that P_{i} − P_{j} ∈ ℝu⃗_{n}. Recall that u⃗_{0} = e_{0}^{(k+1)} and M_{σ} is unimodular. By induction on n it follows from (1) that the entries of u⃗_{n} are relatively prime. Since P_{i} and P_{j} have integral coordinates, we obtain that P_{i} − P_{j} ∈ ℤu⃗_{n}. But this implies i = j, since i, j ∈ {0, 1, …, s^{(n)} − 1}, whence |P_{i} − P_{j}| < |u⃗_{n}|.

If x⃗ = (x_{1}, …, x_{k}) ∈ ℤ^{k} is in the domain of w^{(n)}, then, by (4),

x⃗ = ∑_{i=1}^{k} x_{i}Φ_{n}(^{t}M^{n−k}c⃗_{i}).

When applying σ to the word u^{(n)} to obtain u^{(n+1)}, we apply ^{t}M_{σ} to the broken line segment corresponding to u^{(n)} to obtain the broken line segment corresponding to u^{(n+1)} and therefore Φ_{n+1}^{t}M_{σ} to get the projections. If P is the integer point on the broken halfline corresponding to u^{(n)} which is projected to x⃗, then

P ∈ ∑_{i=1}^{k} x_{i} ^{t}M_{σ}^{n−k}c⃗_{i} + ℝ ^{t}M_{σ}^{n}e_{0}^{(k+1)}.

Applying ^{t}M_{σ} on the left we obtain

tM_{σ}P ∈ ∑_{i=1}^{k} x_{i}^{t}M_{σ}^{n+1−k}c⃗_{i} + ℝ ^{t}M_{σ}^{n+1}e_{0}^{(k+1)}.

If we apply Φ_{n+1}, we get that the image of x⃗ equals

∑_{i=1}^{k} x_{i}Φ_{n+1}(^{t}M_{σ}^{n+1−k}c⃗_{i}).

Thus the vector x⃗ is also in the domain of w^{(n+1)}. Suppose that the broken halfline leaves x⃗ by a step e_{q}^{(k+1)}. Then the subsequent integer points on the broken halfline associated with u^{(n+1)} are obtained by following the letters of the word σ(q) and thus by the projections

y⃗_{s_{q}} = x⃗ + ∑_{i=1}^{s_{q}} a_{(σ(q))_{i}}^{(n+1)},

where s_{q} ∈ {1, …, |σ(q)| − 1}. It follows that the projections are contained in the union of the domain of w^{(n)} and s_{q} translates of it. This argument is valid for q = 0, 1, …, k. Thus we have proved the second assertion.

Now assume that we are in the canonical case. Since P_{m} = t(|u_{0} ⋯ u_{m−1}|_{0}, …, |u_{0} ⋯ u_{m−1}|_{k}) and by σ each letter j is replaced with |σ(j)|_{0} zeros, |σ(j)|_{1} ones, and so forth up to |σ(j)|_{k} letters k, P_{m} is mapped to P_{l} where

P_{l} = ∑_{j=0}^{k} |u_{0} ⋯ u_{m−1}|_{j} ^{t}(|σ(j)|_{0}, …, |σ(j)|_{k}).

Observe that

tM_{σ}P_{m} = ∑_{j=0}^{k} |u_{0} ⋯ u_{m−1}|_{j} ^{t}(|σ(j)|_{0}, …, |σ(j)|_{k}) = P_{l}.

Hence Φ_{n}^{∗}(P_{m}) = Π(^{t}M_{σ}^{−n}P_{m}) = Π(^{t}M_{σ}^{−(n+1)}P_{l}) = Φ_{n+1}^{∗}(P_{l}). Consequently, when going from σ^{n}(0) to σ^{n+1}(0), the projections of the transformations of P_{0}, …, P_{s^{(n)}} remain in the domain of w^{(n)} and σ^{n+1}(0) − σ^{n}(0) new projected points are added. This proves the third statement. □

Observe that the projected points 0, Φ_{n}(P_{1}), …, Φ_{n}(P_{m−1}), Φ_{n}(P_{m}) = 0 with m = s^{(n)}, which make up the domain of w^{(n)}, set up a roundwalk (see [10] for a more general setting of this topic), that is a sequence of vectors from ℤ^{k} with starting point equal to endpoint and with the property that Φ_{n}(P_{i+1}) − Φ_{n}(P_{i}) ∈ {a_{0}^{(n)}, …, a_{k}^{(n)}} for i = 0, …, m − 1. Moreover, the coding of this roundwalk, that is the finite word w_{0} ⋯ w_{m} over the alphabet {0, 1, …, k} defined by w_{i} = j if Φ_{n}(P_{i+1})−Φ_{n}(P_{i}) = a_{j}^{(n)} for 0 ≤ i ≤ m−1, is exactly the word u^{(n)}. Clearly, given the transition vectors, the roundwalk is perfectly determined by its coding.

We define, for i = 1, …, k,

(9)  b_{i}^{(n)} := ^{t}c⃗_{i}v⃗_{n−k} = ∑_{j=0}^{k} c_{i,j}|σ^{n−k}(j)|

where c⃗_{i} = ^{t}(c_{i,0}, …, c_{i,k}) are the vectors in the definition of Φ_{n}. Observe that if we divide through by s^{(n)} = |u^{(n)}| and let n go to infinity, then, by (2) and the convention after (A2),

(10) \frac{b_{i}^{(n)}}{s^{(n)}} = ∑_{j=0}^{k} c_{i,j} \frac{\frac{|σ^{n−k}(j)|}{P (n − k)β^{n−k}}}{\frac{|σ^{n}(0)|}{P (n)β^{n}}} \frac{P (n − k)β^{n−k}}{P (n)β^{n}} ⟶ ∑_{j=0}^{k} c_{i,j} \frac{a_{j}}{a_{0}} β^{−k} =: b_{i},

for n → ∞, which will be important later. We remark that by (5) in the canonical case

b_{i}^{(n)} = ^{t}e_{i}^{(k+1)}M_{σ}^{k}v⃗_{n−k} = ^{t}e_{i}^{(k+1)}v⃗_{n} = |σ^{n}(i)|

and therefore b_{i} = \frac{a_{i}}{a_{0}} . Put b_{0} = 1.

We now use the general theory of roundwalks developed in [40] and [10]. The following result displays some properties of a_{i}^{(n)} and b_{i}^{(n)}.

Theorem 2. The domain of w^{(n)} is a fundamental domain of the lattice

Λ^{(n)} := ℤ (a_{1}^{(n)} − a_{0}^{(n)}) + … + ℤ (a_{k}^{(n)} − a_{0}^{(n)}) .

If d_{0}a_{0}^{(n)} + d_{1}a_{1}^{(n)} + … + d_{k}a_{k}^{(n)} = 0 for integers d_{0}, d_{1}, …, d_{k} ∈ ℤ, then

d_{0} = t · |det (a_{1}^{(n)}, …, a_{k}^{(n)})| and
d_{i} = t · |det (a_{1}^{(n)}, …, a_{i−1}^{(n)}, −a_{0}^{(n)}, a_{i+1}^{(n)}, …, a_{k}^{(n)})|

for i = 1, …, k and some integer t. Moreover, the number m at position x⃗ = (x_{1}, …, x_{k}) ∈ ℤ^{k} in w^{(n)} is congruent to

∑_{i=1}^{k} x_{i}b_{i}^{(n)} (mod s^{(n)})

and x⃗ is congruent to ma_{0}^{(n)} (mod Λ^{(n)}).

Proof. The first and second part of the theorem follow immediately from the much more general theory in [10] (cf. also [35, Lemma 4.2]). For the last part we only have to show that the value of the unit vectors e_{i}^{(k)}(i = 1, …, k) in w^{(n)} are given by b_{i}^{(n)} for every n ∈ ℕ. The rest follows immediately from the fact that g^{(n)}, which extends w^{(n)} to ℤ^{k} by being constant on cosets of Λ^{(n)}, is a linear function (see [10, p. 181]).

By (4) the value at e_{i}^{(k)} is equal to ∥^{t}M_{σ}^{n−k}c⃗_{i}∥_{1} where ∥ · ∥_{1} denotes as usual the sum of the components of the vector. We have, by Lemma 1 and (9),

∥^{t}M_{σ}^{n−k}c⃗_{i}∥_{1} = ∥∑_{j=0}^{k} c_{i,j}^{t}M_{σ}^{n−k}e_{j}^{(k)}∥_{1} = ∑_{j=0}^{k} c_{i,j} ∥^{t}M_{σ}^{n−k}e_{j}^{(k)}∥_{1}

= ∑_{j=0}^{k} c_{i,j}|σ^{n−k}(j)| = b_{i}^{(n)}.

Observe that the same calculation with ^{t}M_{σ}^{n}e_{0}^{(k+1)} instead of ^{t}M_{σ}^{n−k}c⃗_{i} gives the identity s^{(n)} = |u^{(n)}|. □

The sequence of lattices Λ^{(n)} from the last theorem is called a continued lattice (they first appeared in [40] by generalising the continued fraction algorithm). In the canonical case we have some additional properties:

Theorem 3. Assume that we are in the canonical case and let n ≥ 0. Then (i) Λ^{(n)} is a lattice with lattice determinant s^{(n)}. (ii) For i = 1, …, k the vector e_{i}^{(k)} is in the same coset of Λ^{(n)} as

|σ^{n}(i)| a_{0}^{(n)}.

(iii) For m = 1, …, s^{(n)} we have

Φ_{n}^{∗}(P_{m}) ≡ ma_{0}^{(n)} (mod Λ^{(n)}).

Proof. We start with (i). It follows from (8) that

(a_{0}^{(n)}, a_{1}^{(n)}, …, (i), …, a_{k}^{(n)}) ,

where (i) indicates that a_{i}^{(n)} is omitted, is the minor of M_{σ}^{−n} corresponding with the entry |σ^{n}(0)|_{i} of M_{σ}^{n}. Since det(M_{σ}) = ±1 by (A4), we obtain from linear algebra and Lemma 1 that, for a fixed choice of the ±-sign,

(−1)^{i} det (a_{0}^{(n)}, a_{1}^{(n)}, …, (i), …, a_{k}^{(n)}) = ±|σ^{n}(0)|_{i}

for i = 0, 1, …, k. Hence

|det (Λ^{(n)})| = |∑_{i=0}^{k}(−1)^{i} det (a_{0}^{(n)}, a_{1}^{(n)}, …, (i), …, a_{k}^{(n)})|

= ∑_{i=0}^{k} |σ^{n}(0)|_{i} = |σ^{n}(0)| = s^{(n)}

and therefore (i) holds.

Next (ii). Let i ∈ {1, …, k}. The vector ^{t}M_{σ}^{n}e_{i}^{(k+1)} in ℤ^{k+1} is transformed to the vector e_{i}^{(k+1)} in ℤ^{k+1} and then projected to e_{i}^{(k)} in ℤ^{k}. By Lemma 1 we have ^{t}e_{i}^{(k+1)}M_{σ}^{n} = (|σ^{n}(i)|_{0}, …, |σ^{n}(i)|_{k}). Hence the point (|σ^{n}(i)|_{0}, …, |σ^{n}(i)|_{k}) is transformed and subsequently projected to ∑_{j=0}^{k} |σ^{n}(i)|_{j}a_{j}^{(n)}. Thus, by the definition of Λ^{(n)},

e_{i}^{(k)} = ∑_{j=0}^{k} |σ^{n}(i)|_{j}a_{j}^{(n)} ≡ ∑_{j=0}^{k} |σ^{n}(i)|_{j}a_{0}^{(n)} = |σ^{n}(i)|a_{0}^{(n)} (mod Λ^{(n)}).

Finally (iii). We know that P_{m} is the sum of m unit vectors, the unit vector e_{i}^{(k+1)} is mapped to a_{i}^{(n)} and a_{i}^{(n)} ≡ a_{0}^{(n)} (mod Λ^{(n)}) for i = 0, 1, …, k. Therefore the statement is valid. □

We now define a sequence of new words ŵ = (ŵ^{(n)})_{n≥0}, which is closely related to the original sequence. In contrast to w^{(n)} the word ŵ^{(n)} will be a k-dimensional word defined over the (infinite) alphabet [0, 1). The domain of ŵ^{(n)} is the same as the domain of w^{(n)}, i.e. equal to Φ_{n}(A_{n}). For x⃗ in the domain of w^{(n)} we define

(11)  ŵ^{(n)} \binom{}{x} := \{∑_{i=1}^{k} x_{i} \frac{b_{i}^{(n)}}{s^{(n)}} \} ,

where {z} denotes the fractional part of z, i.e. {z} = z mod 1 (see Fig. 4 and observe that Theorem 2 is the motivation for this definition).

\begin{matrix}w^{(4)} & ŵ^{(4)} \\ 6_{1} 8_{1} 10_{1} 1_{1} 5_{0} 7_{0} 9_{0} 0_{0} 4_{0} 11_{2} 2_{2} 12_{0} 3_{0} & \frac{6}{13} \frac{8}{13} \frac{10}{13} \frac{1}{13} \frac{5}{13} \frac{7}{13} \frac{9}{13} 0 \frac{4}{13} \frac{11}{13} \frac{2}{13} \frac{12}{13} \frac{3}{13} \end{matrix}

Fig. 4: The roundwalk w^{(4)} (the subscript indicates the next jump) and its normalization ŵ^{(4)} for the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0.

The sequence ŵ^{(n)} converges to some k-dimensional limit word Ŵ := lim_{n→∞} ŵ^{(n)} over the alphabet [0, 1) defined on a certain subset of ℤ^{k} in the following way: the domain of Ŵ is the union of all domains Φ_{n}(A_{n}) of ŵ^{(n)}, i.e. domŴ := ⋃_{n=0}^{∞} Φ_{n}(A_{n}) = lim_{n→∞} Φ_{n}(A_{n}), and if x⃗ ∈ domŴ then

Ŵ \binom{}{x} := lim_{n→∞} ŵ^{(n)}(x⃗).

We have the following result:

Theorem 4. The word Ŵ is well-defined on domŴ and

(12)  Ŵ \binom{}{x} = \{∑_{i=1}^{k} x_{i}b_{i}\} .

Proof. The statement is trivially true for x⃗ = 0. Since ŵ^{(n)} is defined by (11) the existence of lim_{n→∞} ŵ^{(n)}(x⃗) follows at once from (10). For the second part we have to show that Ŵ (x⃗) < 1; the result then follows from the definition and (10). For x⃗ ∈ domŴ there exists n_{0} ∈ ℕ such that x⃗ ∈ domŵ^{(n)} for all n ≥ n_{0}. By Theorem 1 it follows that 1 − ŵ^{(n)}(x⃗) can be bounded from below by

\frac{|σ^{k}(l)|}{s^{(n_{0}+k)}} = \frac{\frac{|σ^{k}(l)|}{P (k)β^{k}}}{\frac{|σ^{n_{0}+k}(0)|}{P (n_{0} + k)β^{n_{0}+k}}} \frac{P (k)}{P (n_{0} + k)β^{n_{0}}} ⟶ \frac{a_{l}}{a_{0}β^{n_{0}}} > 0,

for k = n−n_{0} → ∞, where l is the jump to get from w^{(n_{0})}(x⃗) to w^{(n_{0})}(x⃗)+1 and where we have used that all a_{j} > 0, i.e. assumption (A3). □

Thus the limit word is the restriction of the linear function ℤ^{k} ⟶ [0, 1) defined by x⃗ = ^{t}(x_{1}, …, x_{k}) ↦ x_{1}b_{1} + … + x_{k}b_{k} mod 1 to domŴ.

Observe that if x⃗ ∈ domŴ, then there is a minimal n_{0} such that x⃗ is in domŵ^{(n_{0})} and it follows that

w^{(n)} \binom{}{x} = ∑_{i=1}^{k} x_{i}b_{i}^{(n)} (mod s^{(n)})

for all n ≥ n_{0}.

It is easy to show that it may happen that the domain of Ŵ is not ℤ^{k} (see Example 2 in Section 6). Our aim is (and that will be the main result of this paper) to clarify where the limit Ŵ exists and, especially, when it is defined everywhere on some submodule of ℤ^{k}. If the latter is the case, we will say that Ŵ is space filling (has the space filling property).

4. Abstract number systems

In this section we describe how to a given substitution σ : Σ → Σ^{∗}, where Σ = {0, 1, …, k}, a number system can be associated. It is well-known (cf. [26]) that a substitution σ defines an automaton in the following way:

(i) the set of states Q is equal to letters of the alphabet Σ, (ii) a transition from state a to state b (a, b ∈ Σ) labeled i is added if b

occurs in σ(a) at position i, (iv) q_{0} = 0 is the initial state and finally

(v) all states are final states.

So, the associated automaton is given by M = (Q, q_{0}, Δ, δ, F), where Δ = {0, 1, …, l} with l := max{|σ(q)| − 1 : q ∈ Q} is the set of labels, δ : Q × Δ → Δ is the transition function and F = Q denotes the set of final states. As above we denote by Δ^{∗} the free monoid generated by Δ for the concatenation product. The neutral element is ε and the the length of a word w ∈ Δ^{∗} is denoted by |w|. The function δ is naturally extended to Q × Δ^{∗} by δ(q, ε) = q and δ(q, dw) = δ(δ(q, d), w) where q ∈ Q, d ∈ Δ and w ∈ Δ^{∗}.

Fig. 5: Automaton associated to the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0.

The language L associated to the substitution is the language of the associated automaton M, that is the collection of strings accepted by the automaton (all paths in the automaton from the initial state to a final state), i.e.

L = {w ∈ Δ^{∗} : δ(q_{0}, w) ∈ F }.

Moreover, if q ∈ Q, we denote by L_{q} the language accepted in M in case q is the initial state, i.e.

L_{q} = {w ∈ Δ^{∗} : δ(q, w) ∈ F }.

In particular, L_{q_{0}} = L_{0} = L. Observe that from our conditions on the substitution σ the automaton is trim, i.e. accessible and coaccessible, finite and deterministic (for more information on automata we refer to [18]) and therefore the languages L_{q} are regular languages. For q ∈ Q and n ∈ ℕ, we denote by u_{q}(n) the number of words of length n accepted from q in M, i.e.

u_{q}(n) = #{w ∈ Δ^{n} : δ(q, w) ∈ F }.

The genealogical ordering (also known as radix ordering or military ordering) is defined as follows: if u and v are words over Δ, then we define u < v, if either |u| < |v| or |u| = |v| and there exist p, u′, v′ ∈ Δ^{∗}, d, e ∈ Δ such that u = pdu′, v = pev′ and d < e. This ordering is naturally extended to the set Δ^{ω} of all the infinite words over Δ according to the lexicographical ordering. The triple S = (L, Δ, <) is called an abstract number system (or abstract numeration system), since the words of L can be enumerated by increasing genealogical ordering leading to a one-to-one correspondence between ℕ and L (cf. [27]). It is well-known (and easy to prove) that the i-th letter in σ^{n}(0) is the state the automaton M will be in after it is fed with the i-th word of length n of its ordered input language L. Thus we have for the limit word U = (U_{n})_{n∈ℕ} = lim_{n→∞} σ^{n}(0) that U_{i} is the state the automaton M will be in after it is fed with the i-th word of the language L if we ignore the words with leading zeroes. For details we refer to [26, Chapter 7].

Next we show that under suitable conditions every real number in the interval [0, 1) can be represented by a unique word from L_{∞} where L_{∞} is the set of infinite words which are limit of a converging sequence of words in L using the usual infinite product topology on Δ^{ω}.

Let β be the dominant root of the incidence matrix M_{σ} of σ (cf. assumption (A2)) and assume additionally that

(A5)  the dominant root β is > 1.

Put τ = β^{−1}. We remark that under the made conditions β has to be irrational: if β ∈ ℚ, then it would be a rational integer, because β is an algebraic integer, and consequently, we would have β = 1, since M_{σ} is unimodular. Thus β ∉ ℚ by (A5).

Observe that, by remarks made above, M_{σ} is the adjacency matrix of the automaton, i.e. M_{σ} = (#{d ∈ Δ : δ(p, d) = q})_{p,q∈Q}. We have the following simple lemma (cf. (2)).

Lemma 4. There is a monic polynomial P (x) ∈ ℚ(β)[x] such that the limit

a_{q} := lim_{n→∞} \frac{u_{q}(n)}{P (n)β^{n}}

exists for every q ∈ Q. Moreover, a_{q} ∈ ℚ[τ], a_{q} ≥ 0.

Proof. We just have to observe that u_{q}(n) = |σ^{n}(q)|. This follows by induction on n. Trivially, u_{q}(1) = |σ(q)|. Clearly, we have that

(13)  u_{p}(n) = ∑_{q∈Q} #{d ∈ Δ : δ(p, d) = q} u_{q}(n − 1)

for all n ≥ 1 and p ∈ Q. Hence the vector u(n) = ^{t}(u_{q_{0}}(n), …, u_{q_{l}}(n)) satisfies the linear recurrence relation u(n) = M_{σ}u(n − 1) and therefore the same as the vector v⃗_{n} = ^{t}(|σ^{n}(0)|, …, |σ^{n}(k)|) considered in Section 2. Since β is the dominant root of M_{σ}, Lemma 4 follows from Lemma 2 with p = 1. Here we use that the minimal polynomial of β is monic and has constant ±1 so that β ∈ ℚ[τ]. (For a_{q} ∈ ℚ[τ] compare with [34, Lemma 4.1].) □

The monicity of P in Lemma 4 is rather arbitrary. In fact, if we replace P (n) by \frac{τ}{a_{q_{0}}} P (n), the limits also exist and lie in ℚ[τ]. Thus, dropping the monicity of P, we may assume that

(A6)  a_{q_{0}} = τ

and we will do so for the rest of the paper. Observe that

(14)  βa_{q} = ∑_{{d∈Δ \atop (q,d)∈domδ}} a_{δ(q,d)},

where domδ denotes the domain of the partial function δ. This means that the vector a⃗ = ^{t}(a_{q_{0}}, …, a_{q_{k}}) is an eigenvector of M_{σ} to the eigenvalue β, i.e. the above relation can be rewritten as

(15)  M_{σ}a⃗ = βa⃗.

For q ∈ Q, t ∈ Δ we define

α_{q}(t) := ∑_{q′∈Q} (a_{q′} · #{d < t : δ(q, d) = q′}) .

Moreover, we set

α_{q} := α_{q}(l + 1) = ∑_{q′∈Q} (a_{q′} · #{d ∈ Δ : δ(q, d) = q′}) .

We remark that α_{q} = (M_{σ}a⃗)_{q} = βa_{q} and in particular α_{0} := α_{q_{0}} = βa_{q_{0}} = 1. Set

A_{q} := [0, α_{q}) = ⋃_{d=0}^{l} \underbrace{[α_{q}(d), α_{q}(d + 1))}_{=:A_{q,d}} .

We have A_{q_{0}} = [0, 1). We will use the following algorithm: Let x ∈ (0, 1) and set w ← ε, q ← q_{0}. Then iterate the operations

1. Find d ∈ Δ such that x ∈ A_{q,d}

2. w ← wd
3. x ← β (x − α_{q}(d))
4. q ← (σ(q))_{d}

The output of the algorithm is the word w which we call the σ-representation of x. Conversely we say that x is the numerical value of w. If x = 0 at some stage, then it remains 0 and we say that x has a finite σ-representation where we stop after the last non-zero value of q. The σ-representation of 0 is by definition 0. Observe that the length of A_{q,d} is a_{q′} for q′ = (σ(q))_{d}. Hence, the new x is in A_{q′}. That is why the algorithm works correctly. The next theorem states that the algorithm induces a bijection between [0, 1) and the words in L_{∞}.

Theorem 5. Every number x ∈ [0, 1) has a unique σ-representation (d_{j})_{j=1}^{∞} in L_{∞} such that

x = ∑_{j=1}^{∞} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1}

with d_{0} = ε. Conversely, for every (d_{j})_{j=1}^{∞} in L_{∞} the above equation gives a unique element x in [0, 1).

Proof. This follows immediately from the construction above. □

We remark that this result is not new. It can be found in [16, 3.2 Théorème] in the context of substitutions with a primitive incidence matrix M_{σ}. Moreover, such number systems were studied extensively for arbitrary regular languages satisfying the conclusion of Lemma 4 in recent years in [28, 29, 21, 34]. To our knowledge our formulation is new, but we tried to be as close as possible to the notation of the mentioned papers.

We consider two important classes of numbers, namely those with periodic and those with finite σ-representations. We say that an element x ∈ ℚ(β) ∩ [0, 1) has an ultimately periodic σ-representation if and only if when applying the algorithm we find (ω, x, q) and (ω′, x′, q′) such that x = x′ and q = q′ (compare with [29, Theorem 27]). We call an algebraic integer β a Pisot number if all conjugates other than itself have modulus less than one and a Salem number if the modulus of all the conjugates other than itself is less than or equal to one and at least one is equal to one. Recently, Rigo and Steiner [34] showed that if β > 1 is a Pisot number, then the set of real numbers in [0, 1) with finite or ultimately periodic σ-representation equals ℚ(β) ∩ [0, 1). This generalized the well-known result on Rényi’s classical βexpansion [33, 31] by Bertrand [14] and Schmidt [42] and a first attempt in [29] for abstract number systems. Moreover, they showed that if β is neither a Pisot nor a Salem number, then there exists at least one point in ℚ(β) ∩ [0, 1) which has an infinite σ-representation which is not ultimately periodic.

We denote by Fin(β) the set of all numbers x ∈ [0, 1) whose σrepresentation is finite. We claim that

(16)  Fin(β) ⊆ ℤa_{q_{0}} + ℤa_{q_{1}} + … + ℤa_{q_{k}}.

Indeed, by the theorem every element in Fin(β) is a finite linear combination of terms of the form a_{q}τ^{n−1}. Since this is one of the coordinates of the vector τ^{n−1}a⃗ = M_{σ}^{−k}a⃗ and M_{σ}^{−1} has integral entries by (A4), it follows that a_{q}τ^{n−1} ∈ ℤa_{q_{0}} + ℤa_{q_{1}} + … + ℤa_{q_{k}}. This proves (16). By a_{q_{0}} = τ, we especially have ℤ[τ] ⊆ ℤa_{q_{0}} + ℤa_{q_{1}} + … + ℤa_{q_{k}} =: Ω. The following lemma gives information about Ω.

Lemma 5. Let Ω = ℤa_{q_{0}} + ℤa_{q_{1}} + … + ℤa_{q_{k}}. Then (i) Ω is a ℤ-module that is not necessarily free. (ii) If Ω is free, then dim Ω = deg β and therefore

ℤ[τ] ⊆ Ω ≅ ℤ[τ] ≅ ℤ^{deg β}

as ℤ-modules. In this case we can choose a basis from a_{q_{0}}, …, a_{q_{k}}. (iii) If u⃗_{0}, …, u⃗_{k−1} are linearly independent over ℤ, then Ω = ℤ[τ].

Proof. Clearly, Ω is a ℤ-module. For a substitution with incidence matrix

( \begin{matrix}1 & 3 & 2 \\ 0 & 2 & 5 \\ 0 & 1 & 3 \end{matrix} )

we have

(a_{0}, a_{1}, a_{2}) = (τ, −\frac{19}{47}τ + \frac{13}{47}, \frac{5}{47}τ + \frac{4}{47}) ,

where τ^{2} − 5τ + 1 = 0. Hence Ω is not necessarily free.

Next (ii). Since ℤ[τ] ⊆ Ω, the dimension is at least deg β. On the other hand, from a_{q} ∈ ℚ[τ] it follows that a_{i}, 1, τ, …, τ^{deg β−1} are linearly dependent over ℤ for i = 0, 1, …, k. If Ω is free and therefore has a basis, its dimension is equal to deg β. Obviously, the basis can be chosen from the set of generators.

Finally (iii). We already observed above that τ^{n} ∈ Ω for every n ∈ ℕ, because of the zeroth coordinate in the equation τa⃗ = M_{σ}^{−1}a⃗. Hence Ω = ℤ[τ] if the zeroth row vectors of M_{σ}, M_{σ}^{0}, M_{σ}^{−1}, …, M_{σ}^{2−k} are linearly independent over ℤ. Since M_{σ} is unimodular, this is equivalent with the zeroth row vectors of M_{σ}^{k−1}, M_{σ}^{k−2}, …, M_{σ}, M_{σ}^{0} being linearly independent over ℤ, which is the same as u⃗_{0}, …, u⃗_{k−1} being linearly independent over ℤ. □

Observe that it is easy to decide whether Ω is free or not, since we only have to pick a basis from a_{q_{0}}, …, a_{q_{k}} (so that all the other elements are linear combinations of them with integer coefficients).

As in the classical case of β-expansions (e.g. in [1, 3, 20]) we consider the condition

(F)  Fin(β) = (ℤa_{q_{0}} + ℤa_{q_{1}} + … + ℤa_{q_{k}}) ∩ [0, 1).

This condition says that all possible candidates indeed have a finite σrepresentation. We denote the conjugates of x, a_{q}, β in ℚ(β) by x^{(j)}, a_{q}^{(j)}, β^{(j)} for j = 0, 1, …, degβ − 1, q ∈ Q with the convention that x^{(0)} = x, a_{q}^{(0)} = a_{q}, β^{(0)} = β. By using the methods from [1, 3, 20] we prove

Theorem 6.

(a) Let β be a Pisot number. Then β has the property (F) if and only if every element of the finite set

{x ∈ Ω : |x^{(j)}| ≤ M_{j} (j ≥ 0)} ,

where M_{0} = max{α_{q} : q ∈ Q} and, for j = 1, …, degβ − 1,

M_{j} = \frac{max \{|a_{q}^{(j)}| : q ∈ Q\} · #Δ · #Σ}{1 − |β^{(j)}|}

has a finite σ-representation in every language L_{q} (with q ∈ Q). Moreover, this can be checked effectively.

(b) If ℤ[τ]∩[0, 1) ⊆ Fin(β), then β is a Pisot number or a Salem number.

Proof. We first prove (a). We show that the validity of (F) can be decided by checking only the finitely many elements x in the displayed set. First let x ∈ Ω ∩ [0, 1) with expansion

x = ∑_{j=0}^{∞} ∑_{q∈Q} a_{q}ε_{q,j}τ^{j},

where ε_{q,j} = #{s < d_{j} : δ(δ(q_{0}, d_{0} ⋯ d_{j−1}), s) = q} are integers and d_{0}d_{1} ⋯ is the σ-representation of x, and a_{q} ∈ ℚ[τ]. Let ϵ > 0 and m so large that

|x^{(j)}| (|β^{(j)}|)^{m} < ϵ

for j = 1, …, degβ − 1. We consider

(17)  y := xβ^{m} − ∑_{j=0}^{m−1} ∑_{q∈Q} a_{q}ε_{q,j}τ^{j−m} = ∑_{j=0}^{∞} ∑_{q∈Q} a_{q}ε_{q,m+j}τ^{j}.

Obviously, we have y ∈ Ω, 0 ≤ y < α_{q} for some q ∈ Q and |y^{(j)}| < ϵ + M_{j} for j > 0. Therefore, since ϵ > 0 is arbitrary, it suffices to check whether or not all expressions in the set

(18)  {y ∈ Ω : |y^{(j)}| ≤ M_{j} for j = 0, 1, …, degβ − 1}

have a finite σ-representation in all languages L_{q} with q ∈ Q. Equivalently, we may consider all the elements contained in

{x ∈ ℤ[τ] : |x^{(j)}| ≤ b_{j}} ,

where b_{j} = M_{j} · min{n ∈ ℕ : na_{q_{i}} ∈ ℤ[τ] for i = 1, …, k} (j = 0, 1, …, deg β − 1). It is now easy to compute these numbers effectively, since we can solve the equations Bx⃗ = z⃗ where

B = ( \begin{matrix}1 & τ & ⋯ & τ^{deg β−1} \\ 1 & τ^{(1)} & ⋯ & (τ^{(1)})^{deg β−1} \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & τ^{(deg β−1)} & ⋯ & (τ^{(deg β−1)})^{deg β−1} \end{matrix} ) ,

x⃗ ∈ ℤ^{deg β} are the coordinates of x in the basis 1, …, τ^{deg β−1}, and with ∥z⃗∥_{∞} ≤ max{b_{j} : j = 0, …, deg β − 1} and where ∥ ∥_{∞} denotes the usual maximum norm. Since 1, τ, …, τ^{deg β−1} is a basis of ℚ(β), the determinant of B, which is equal to the discriminant of the number field, is different from zero. Therefore, we get

∥x⃗∥_{∞} = ∥B^{−1}z⃗∥_{∞} ≤ ∥B^{−1}∥_{∞} · ∥z⃗∥_{∞}

≤ max_{j=0,...,deg β−1} { ∑_{i=0}^{deg β−1} |(B^{−1})_{i,j}|} · max_{j=0,...,deg β−1}{b_{j}},

where (B^{−1})_{i,j} is the element at position (i, j) in B^{−1}. Thus we have an effective bound for ∥x⃗∥_{∞} and it suffices to show that all elements in (18) obtained by such x⃗ have a finite σ-representation.

To conclude the first part, we only have to point out that when applying the expansion algorithm to one of the elements in the set in (18), we remain in the same set, since this just means to increase m by 1 in (17), and therefore the possible period (observe that by the result in [34] all elements have an ultimately periodic σ-representation) is bounded by the cardinality of this set.

Next (b). Suppose ℤ[τ] ∩ [0, 1) ⊆ Fin(β). Assume that β has a conjugate γ = β^{(j)} with γ ≠ β, |γ| > 1. Let η = max{β^{−1}, |γ|^{−1}}. Take x := [β^{m}] − β^{m} + 1, where [z] is the largest integer less than or equal to z. It is plain that 0 < x < 1. By assumption x has a finite expansion

x = ∑_{j=0}^{k} ∑_{q∈Q} a_{q}ε_{q,j}τ^{j}.

Taking conjugates we get

[β^{m}] − γ^{m} + 1 = ∑_{j=0}^{k} ∑_{q∈Q} a_{q}^{(j)}ε_{q,j}γ^{−j}.

Subtracting the two expansions we end up with

γ^{m} − β^{m} = ∑_{j=0}^{k} ∑_{q∈Q} ε_{q,j}(a_{q}τ^{j} − a_{q}^{(j)}γ^{−j})

and by observing that 0 ≤ ε_{q,j} ≤ l we see that the right-hand side is bounded by

2 max {|a_{q}^{(j)}| : q ∈ Q, j = 0, …, deg β − 1} · #Δ · #Σ · (1 − η)^{−1},

whereas the left-hand side of the equation is unbounded. This contradiction shows that β is a Pisot number or a Salem number. □

An alternative proof that the set (17) is finite follows from the fact that all these elements are contained in the set of solutions of the norm form inequality N_{ℚ(β)/ℚ}(z) ≤ b_{0}b_{2} ⋯ b_{deg β−1}, which has finitely many solutions by Schmidt’s famous result on norm form equations [43, Satz 2, p. 5] (see also [19]). However, this method is ineffective.

The second statement of Theorem 6 implies that from (F) we can conclude that β is a Pisot number or a Salem number. Moreover, we remark that the statement holds not only in the case of number systems associated to the underlying substitution, which is considered throughout this paper, but in the context of abstract number systems as well.

It follows from our proof that if an element of Ω ∩ [0, 1) does not have a finite expansion, then its expansion is ultimately periodic (this follows also from a result of Rigo and Steiner [34]). If so, from the proof of Theorem 6(a) we can deduce an upper bound for the preperiod depending on the input x (using the ϵ-condition) and an upper bound for the period (viz. the cardinality of the set (18)). In particular, only finitely many distinct periods can occur.

Finally, we point out that the condition in the first part of the theorem can be simplified if the automaton has the property that

(19)  δ(q_{0}, w) = q_{0} infinitely often as |w| → ∞.

This is the case e.g. for the Tribonacci expansion considered in [35] and more generally for all so-called β-substitutions, that are substitutions of the form σ(0) = 0^{n_{0}}1, σ(1) = 0^{n_{1}}2, …, σ(k − 1) = 0^{n_{k−1}}k, σ(k) = 0^{n_{k}}, where n_{0}, n_{k} > 0 and n_{i} ≥ 0 (i = 1, …, k − 1). Then the abstract number system associated to it generates the usual β-expansion and the incidence matrix has the form

( \begin{matrix}n_{0} & 1 & 0 & ⋯ & 0 \\ n_{1} & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & & ... & ⋮ \\ n_{k−1} & 0 & 0 & ⋯ & 1 \\ n_{k} & 0 & 0 & ⋯ & 0 \end{matrix} )

(cf. [29]).

If we have the additional property (19), it suffices to check whether or not all elements in

{x ∈ Ω ∩ [0, 1) : |x^{(j)}| ≤ M_{j} (j ≥ 1)}

have a finite expansion in the language L. (It is not necessary to check all languages L_{q} as above.) This follows from the proof of Theorem 6(a), since we can choose some large m such that δ(q_{0}, d_{0} ⋯ d_{m−1}) = q_{0}.

5. The space filling property

In this section we will link the number system associated to the substitution introduced in the previous section with the words ŵ^{(n)} and show that the question whether this word converges to a word that is space filling or not can be decided by means of the first part of Theorem 6. From now on we write a_{0}, a_{1}, …, a_{k} instead of a_{q_{0}}, a_{q_{1}}, …, a_{q_{k}}.

Write C for the matrix with column vectors ^{t}M_{σ}^{k}e_{0}^{(k+1)}, c⃗_{1}, …, c⃗_{k} introduced in Section 3. We mention that in the canonical case C = ^{t}M_{σ}^{k}. Put a⃗ = ^{t}(a_{0}, …, a_{k}) and b⃗ = ^{t}(b_{0}, …, b_{k}), where the b_{i} are defined in (10). We derive the following important relation between b⃗ and a⃗.

Lemma 6. For all n ∈ ℕ we have

(20)  b⃗ = τ^{n−1} ^{t}CM_{σ}^{n−k}a⃗.

Proof. By (15), (A6) and (10) we have

τ^{n−1} ^{t}CM_{σ}^{n−k}a⃗ = β^{1−n} ^{t}Cβ^{n−k}a⃗ = β^{1−k} ^{t}Ca⃗ = b⃗.

Thus we have proved the assertion. □

In case that c⃗_{i} equals the incidence vector u⃗_{i} = ^{t}M_{σ}^{i}e_{0}^{(k+1)} of u^{(i)} for i = 1, …, k we get

b_{i} = τ^{k−1} ^{t}c⃗_{i}a⃗ = τ^{k−1} ^{t}e_{0}^{(k+1)}M_{σ}^{i}a⃗ = τ^{k−1} ^{t}e_{0}^{(k+1)}β^{i}a⃗ = τ^{k−i−1}a_{0} = τ^{k−i}

for i = 1, …, k.

By (20) with n = 1 we have

ℤ + ℤb_{1} + … + ℤb_{k} = ℤa_{0} + … + ℤa_{k} = Ω.

In case c⃗_{i} = u⃗_{i} for i = 1, …, k this implies Ω = ℤ[τ] by Lemma 5(iii).

In Section 3 we also introduced the projections Π : ℤ^{k+1} → ℤ^{k} and Φ_{n} : ℤ^{k+1} → ℤ^{k} and the transition vectors a_{i}^{(n)} (i = 0, 1, …, k). The identity (20) has the following consequence.

Lemma 7. For all n ∈ ℕ and i = 0, 1, …, k we have

(21)  (b_{1}, …, b_{k}) · a_{i}^{(n)} ≡ a_{i}τ^{n−1} (mod 1).

Proof. Let the inverse matrix of M_{σ}^{(n−k)}C have respective column vectors x_{0}^{(n)}, …, x_{k}^{(n)}, hence M_{σ}^{(n−k)}Cx_{i}^{(n)} = e_{i}^{(k+1)} for i = 0, 1, …, k. Then, for i = 1, …, k, by (7) and the definition and linearity of Φ_{n},

a_{i}^{(n)} = Φ_{n}(e_{i}^{(k+1)}) = Φ_{n}(M_{σ}^{(n−k)}Cx_{i}^{(n)})

= x_{i0}^{(n)}Φ_{n}(^{t}M_{σ}^{n}e_{0}^{(k+1)}) + ∑_{j=1}^{k} x_{ij}^{(n)}Φ_{n}(^{t}M_{σ}^{(n−k)}c⃗_{j}) = ∑_{j=1}^{k} x_{ij}^{(n)}e_{j}^{(k)} = Πx_{i}^{(n)},

where x_{i}^{(n)} = ^{t}(x_{i0}^{(n)}, …, x_{ik}^{(n)}) ∈ ℤ^{k+1} (i = 0, …, k) by the unimodularity of M_{σ} and C. We obtain, by (20) and (15),

(b_{1}, …, b_{k}) · a_{i}^{(n)} = τ^{n−1}Π(^{t}a⃗ ^{t}M_{σ}^{(n−k)}C) Π(x_{i}^{(n)})

= τ^{n−1} ^{t}a⃗ ^{t}M_{σ}^{(n−k)}Cx_{i}^{(n)} − τ^{n−1} ^{t}a⃗ ^{t}M_{σ}^{(n)}e_{0}^{(k+1)}x_{i0}^{(n)}

= τ^{n−1} ^{t}a⃗e_{i}^{(k+1)} − τ^{n−1} x_{i0}^{(n)}β^{n}a_{0} = τ^{n−1}a_{i} − x_{i0}^{(n)} ≡ τ^{n−1}a_{i} (mod 1),

since x_{i0}^{(n)} ∈ ℤ. □

From the proof of Lemma 7 it follows that

Φ_{n}(x⃗) = Π (C^{−1} ^{t}M_{σ}^{k−n}x⃗)

for all x⃗ ∈ ℤ^{k+1} (compare with (6) for Φ_{n}^{∗}). Especially, this means that the transition vectors are equal to the columns of C^{−1} after deletion of the zeroth entries.

We now define a function f from ℤ^{k} to (ℤa_{0} + … + ℤa_{k}) ∩ [0, 1) by

f(x⃗) := f(x_{1}, …, x_{k}) := (b_{1}, …, b_{k}) · x⃗ (mod 1) = {∑_{i=1}^{k} x_{i}b_{i}}

where x⃗ = ^{t}(x_{1}, …, x_{k}). This function is linear modulo 1. Further, by (21),

(22)  f(a_{i}^{(n)}) ≡ a_{i}τ^{n−1} (mod 1).

Moreover, if a_{0}, …, a_{k} is a basis of the ℤ-module Ω = ℤa_{0} + … + ℤa_{k}, then it is bijective and by (21) we have, provided that a_{i}τ^{n−1} < 1,

a_{i}^{(n)} = f^{−1} (a_{i}τ^{n−1}) .

Generally, f is an epimorphism of ℤ-modules. By (12) the limit word Ŵ is the restriction of f on its domain, i.e. for all x⃗ ∈ domŴ we have f(x⃗) = Ŵ (x⃗). Therefore, studying f results in getting information on Ŵ.

Using these facts together with Theorem 1 we will characterize the domain of the words ŵ^{(n)}.

Theorem 7. If x⃗ ∈ ℤ^{k} is in the domain of ŵ^{(n)}, then f(x⃗) has a finite σ-representation d_{1} … d_{n} of length at most n, i.e.

f(x⃗) = ∑_{j=1}^{n} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1}

with d_{0} = ε. Conversely, for all elements x⃗ in the domain of ŵ^{(n)} the σrepresentations of f(x⃗) are different and all words in L of length at most n appear.

Moreover, if the σ-representation of f(x⃗) for x⃗ in the domain of ŵ^{(n−1)} is d_{0} ⋯ d_{n−1}, q = δ(q_{0}, d_{0} ⋯ d_{n−1}) and w^{(n)}(x) = m, then

w^{(n)} (x⃗ + ∑_{i=1}^{s} a_{(σ(q))_{i}}^{(n)}) = m + s

and the (m + s)-th letter in u^{(n)} is (σ(q))_{s} for s = 1, …, |σ(q)|, whereas

x⃗ + ∑_{i=1}^{|σ(q)|} a_{(σ(q))_{i}}^{(n)} = x⃗ + a_{q}^{(n−1)}

is in the domain of w^{(n−1)}.

Proof. We prove the assertion by induction on n.

For n = 0, 1 the statement is trivially true. Observe that δ(q_{0}, d_{0}) = 0, which gives the second part of the statement, namely the jumps we have to make with the transition vectors when going from the origin (the only point in the domain of ŵ^{(0)}) to the points in domŵ^{(1)} obtained from u^{(1)} = σ(0).

Suppose x⃗ ∈ ℤ^{k} is in the domain of ŵ^{(n−1)} and has the σ-representation d_{0}d_{1} ⋯ d_{n−1}. Then, by the induction hypothesis,

f \binom{}{x} = ∑_{j=1}^{n−1} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1}.

Let δ(q_{0}, d_{0}d_{1} ⋯ d_{n−1}) = q. Then x⃗ is also in the domain of ŵ^{(n)} and the new elements in ŵ^{(n)} which originate from x⃗ are given by

y⃗_{s} := x⃗ + ∑_{i=1}^{s} a_{(σ(q))_{i}}^{(n)} (s = 1, …, |σ(q)| − 1).

For s = |σ(q)| we get the successor of x⃗ in w^{(n−1)} according to (14). We have, by (22),

f (x⃗ + ∑_{i=1}^{s} a_{(σ(q))_{i}}^{(n)}) ≡ f \binom{}{x} + ∑_{i=1}^{s} f (a_{(σ(q))_{i}}^{(n)})

≡ ∑_{j=1}^{n−1} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1} + ∑_{i=1}^{s} a_{(σ(q))_{i}}τ^{n−1}

= ∑_{j=1}^{n} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1} (mod 1),

where d_{n} = s, because, by the previous section,

α_{δ(q_{0},d_{0}···d_{n−1})}(d_{n}) = α_{q}(s)

= ∑_{q′∈Q} (a_{q′} · #{t < s : δ(q, t) = q′}) = ∑_{i=1}^{s} a_{(σ(q))_{i}}. (23)

By the second part of Theorem 5, ∑_{j=1}^{n} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1} is the σrepresentation of some number in [0, 1). It follows that the congruence is in fact an equality. Moreover, since the value of w^{(n)} is uniquely determined by the word d_{0}d_{1} ⋯ d_{n}, we conclude (by Theorem 5) that this is really the representation of f(y⃗_{s}) which proves the assertion. Obviously, all representations are different and all words in L of length at most n appear.

The second part of the theorem follows at once from the consideration above together with Theorem 1. □

We need still another lemma (which is implicitly contained in the last theorem) to characterize the space filling property of the word Ŵ.

Lemma 8. If x⃗ ∈ ℤ^{k} is in the domain of ŵ^{(n)}, then

(x⃗ + ker f) ∩ domŵ^{(n)} = {x⃗},

where ker f denotes the kernel of the map f.

Proof. We prove the statement by induction on n. For n = 0 the result is trivial. Assume now that x⃗, y⃗ ∈ domŵ^{(n)} and x⃗ − y⃗ ∈ ker f, i.e. f(x⃗) = f(y⃗). It follows from the proof of Theorem 1 that we can write

x⃗ = x⃗_{0} + ∑_{i=1}^{s} a_{(σ(q))_{i}}^{(n)}, y⃗ = y⃗_{0} + ∑_{i=1}^{s′} a_{(σ(q′))_{i}}^{(n)},

for certain x⃗_{0}, y⃗_{0} ∈ domŵ^{(n−1)} and s, s′, q, q′ ∈ Σ. Therefore,

f(x⃗_{0}) + ∑_{i=1}^{s} a_{(σ(q))_{i}}τ^{i−1} ≡ f(x⃗) = f(y⃗) ≡ f(y⃗_{0}) + ∑_{i=1}^{s′} a_{(σ(q′))_{i}}τ^{i−1}

modulo 1 by (22), and we have equality by the same argument as at the end of the proof of the theorem above. Since the representation of a number in Ω ∩ [0, 1) is unique, it follows that s = s′, q = q′ and f(x⃗_{0}) = f(y⃗_{0}), but the latter equality contradicts to the induction hypothesis, unless x⃗_{0} = y⃗_{0} and therefore x⃗ = y⃗. □

The next result shows that all elements in the domain are completely determined by their σ-representations and the transition vectors.

Corollary 1. If x⃗ ∈ domŴ with σ-representation d_{1} ⋯ d_{n} of length n, then

x⃗ = ∑_{j=1}^{n} ∑_{i=1}^{d_{j}} a_{(σ(δ(q_{0},d_{1}d_{1}···d_{j−1})))_{i}}^{(j)}.

Proof. By Theorem 7, (23) and (21) we have

f(x⃗) = ∑_{j=1}^{n} α_{δ(q_{0},d_{0}···d_{j−1})}(d_{j})τ^{j−1} = ∑_{j=1}^{n} ∑_{i=1}^{d_{j}} a_{(σ(δ(q_{0},d_{0}···d_{j−1})))_{i}}τ^{j−1}

≡ (b_{1}, …, b_{k}) · (∑_{j=1}^{n} ∑_{i=1}^{d_{j}} a_{(σ(δ(q_{0},d_{1}d_{1}···d_{j−1})))_{i}}^{(j)}) (mod 1).

The vector in brackets is in the domain of Ŵ by Theorem 1. Furthermore we recall f(x⃗) = (b_{1}, …, b_{k}) · x⃗ mod 1. The assertion now follows from Lemma 8. □

We remark that it follows from Theorem 7 and its corollary that the Rauzy color of w^{(n)} at position x⃗ ∈ domw^{(n)}, that is the index of the transition vector to make the jump from w^{(n)}(x⃗) to w^{(n)}(x⃗) + 1, is equal to the state δ(q_{0}, d_{0} ⋯ d_{n}) the automaton M is in after it is fed with the representation d_{0} ⋯ d_{n}. (If x⃗ ∈ domw^{(h)} for some h < n we read d_{0} ⋯ d_{n} as d_{0} ⋯ d_{h}0 ⋯ 0.)

00011  1101  1001 0111  0100001 0001111001
100001 011001  0001 1111001 110011 100011
000001 111 11 1 011 0011001 000011
010001 001  ε
111101 01 111111
001101  1111 11001 10001 01101
1101111 1001111 0111111  0011  00001

Fig. 6: All finite σ-representations of f(x⃗), i.e. all elements of Ŵ (x⃗), where x⃗ = (x_{1}, x_{2}) has max{|x_{1}|, |x_{2}|} ≤ 3 in the canonical case for the flipped Tribonacci substitution σ(0) = 01, σ(1) = 20, σ(2) = 0 (compare with Fig. 3).

From Lemma 8 we see that if we factor out the kernel of f, we get a well defined isomorphism of ℤ-modules given by

f^{∗} : ℤ^{k}/ ker f ⟶ (ℤa_{0} + … + ℤa_{k}) ∩ [0, 1) = Ω ∩ [0, 1)
x⃗ + ker f ⟼ f(x⃗).

Observe that by Lemma 5(i) the ℤ-module ℤ^{k}/(ker f) is not always isomorphic to some sublattice of ℤ^{k}. If Ω is free, then we can map ŵ^{(n)} to some sublattice of ℤ^{k} of dimension deg β − 1 by a projection Ψ along the kernel of f as follows. Let 1, b_{i_{1}}, …, b_{i_{deg β−1}} be a basis of Ω. Then each b_{i} with i ∉ {i_{1}, …, i_{deg β−1}} can be expressed as a linear combination in this basis. We denote the corresponding vector by x⃗_{i} ∈ ℤ^{k}, where we have removed the zeroth coordinate, hence f(x⃗_{i}) = 0 and x⃗_{i} has an entry 1 in position i and 0 at every position j ∉ {i_{1}, …, i_{deg β−1}, i}. Now the map Ψ can be described by a linear combination of such vectors x⃗_{i} for any given point in the domain of ŵ^{(n)} such that all the coordinates at positions i with i ∉ {i_{1}, …, i_{deg β−1}} become 0. Thus

Ψ (ℤ^{k}/ ker f) = ⨁_{i∈{i_{1},...,i_{deg β−1}}} ℤe_{i}^{(k)} ≅ ℤ^{deg β−1}

and especially we have

domΨ(Ŵ ) = Ψ (domŴ ) = ⨁_{i∈{i_{1},...,i_{deg β−1}}} ℤe_{i}^{(k)}.

In other words, if x⃗ is in the domain of ŵ^{(n)}, then there is a representative in the same coset mod ker f which is in this sublattice of ℤ^{k}.

If Ω is free, then Ψ maps ŵ^{(n)} onto the above sublattice of ℤ^{k}. By combining Theorems 6 and 7 we get the following result concerning the space filling property of the the limit word Ŵ = lim_{n→∞} ŵ^{(n)}. This answers the question whether the limit word fills the submodule ℤ^{k}/(ker f), that is the corresponding sublattice of ℤ^{k} if Ω is a free ℤ-module.

Theorem 8. The limit word Ŵ is space filling if and only if the associated number system has the finiteness property (F). If β is a Pisot number, then the space filling property is decidable.

Proof. By Theorem 7 the domain of the limit word Ŵ is in bijection with Fin(β) by sending x⃗ ∈domŴ to f(x⃗). Therefore Lemma 8 shows that the domain of Ŵ consists exactly of all elements x⃗ ∈ ℤ^{k} for which f(x⃗) is in Fin(β). The first statement now follows from the observation that the domain of f equals (ℤa_{0} + … + ℤa_{k}) ∩ [0, 1). Since by part (a) of Theorem 6 property (F) is decidable if β is Pisot, the space filling property is decidable in this case. This completes the proof. □

Observe that in the Pisot case the space filling property of Ŵ can therefore be decided effectively by checking if all elements from the finite set given in Theorem 6 admit only finite representations in all languages L_{q} (q ∈ Q).

The above mentioned space filling properties carry over without any troubles to the BV-words v (see [11, 12, 13]) studied in [10] and [45].

6. Examples

In this section we will give five examples illustrating the theory developed in the previous sections. The first example is a substitution on three letters which gives a limit word that is space filling everywhere in ℤ^{2}. The second example is the flipped Tribonacci substitution that was already mentioned at some previous occasions in this paper and which leads to a word that is not space filling. The next two examples give words that are space filling in a 1- and 2-dimensional submodule that can be projected to a line and a plane, respectively. The last example gives a word on four letters that is in a 1-dimensional submodule which projects to a line but is not space filling. We hope that these examples will give a better insight to the reader.

Example 1.

As a first example we consider the substitution

(E1)  σ(0) = 0001, σ(1) = 02, σ(2) = 0

with incidence matrix and its inverse given by

M_{σ} = ( \begin{matrix}3 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} )

and

M_{σ}^{−1} = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & −3 \\ 0 & 1 & −1 \end{matrix} ) .

The characteristic polynomial of M_{σ} is x^{3} − 3x^{2} − x − 1 and therefore M_{σ} has a dominant eigenvalue β ≈ 3.383 and τ = β^{−1} ≈ 0.296. By calculating the normalized eigenvector of M_{σ} to the eigenvalue β we get

a⃗ = (a_{0}, a_{1}, a_{2}) = (τ, τ^{2} + τ^{3}, τ^{2}).

Hence, the ℤ-module Ω equals ℤ[τ].

By using M_{σ}^{−1} it is easy to compute the transition vectors for the canonical projection Φ_{n}^{∗}. We have

\begin{matrix}n & a_{0}^{(n)} & a_{1}^{(n)} & a_{2}^{(n)} \\ 1 & ^{t}(0, 1) & ^{t}(0, −3) & ^{t}(1, −1) \\ 2 & ^{t}(1, −1) & ^{t}(−3, 4) & ^{t}(−1, −2) \\ 3 & ^{t}(−1, −2) & ^{t}(4, 5) & ^{t}(−2, 6) \end{matrix}

The automaton associated to σ is given by:

The associated number system scheme as described in the algorithm in Section 4 is given by

Therefore, we get the following projections of u^{(1)} = 0001, u^{(2)} = 0001000 1000102, u^{(3)} = 00010001000102000100010001020001000100010200010 for n = 1, 2, 3 in the canonical case:

\begin{matrix}w^{(1)} & w^{(2)} & w^{(3)} \\ 3 2 1 0 & 12 8 13 4 9 0 5 10 1 6 11 2 7 3 & 42 28 46 43 14 32 29 0 18 36 44 15 33 4 22 40 30 1 19 37 8 26 45 16 34 5 23 41 12 31 2 20 38 9 27 17 35 6 24 13 3 21 39 10 7 25 11 \end{matrix}

From the three images above we would expect that the limit word Ŵ will be space filling. Indeed that is the case since the associated number system has property (F). This follows either by applying Theorem 6, where we have to check whether all elements of the form x_{0} + x_{1}τ + x_{2}τ^{2} with ∥(x_{0}, x_{1}, x_{2})∥_{∞} ≤ 162 have a finite expansion in the language L (since the remark after Theorem 6 applies), or by applying the criterion in [1]. The latter is allowed since β is a cubic Pisot unit and the number system is the usual β-expansion of a number (cf. the end of Section 4).

Since Ω is free with full dimension and (b_{0}, b_{1}, b_{2}) = (1, τ + τ^{2}, τ), we have f(x_{1}, x_{2}) = x_{1}(τ + τ^{2}) + x_{2}τ mod 1. This follows from the fact that we are in the canonical case and thus the b_{i}’s are obtained from the a_{i}’s by dividing them by τ. The table below gives the expansions of all f(x_{1}, x_{2}) with −3 ≤ x_{1} ≤ 3, −8 ≤ x_{2} ≤ 3:

\begin{matrix}2121 & 0111 & 1211 & 3 & 0301 & 20211 & 00111 \\ 1121 & 2221 & 0211 & 2 & 31 & 10211 & 21211 \\ 0121 & 1221 & 301 & 1 & 21 & 00211 & 11211 \\ 2231 & 0221 & 201 & ε & 11 & 22 & 01211 \\ 1231 & 302 & 101 & 211 & 01 & 12 & 23 \\ 02231 & 202 & 001 & 111 & 221 & 02 & 13 \\ 303 & 102 & 212 & 011 & 121 & 231 & 03 \\ 203 & 002 & 112 & 222 & 021 & 131 & 30301 \\ 103 & 213 & 012 & 122 & 300211 & 031 & 20301 \\ 003 & 113 & 223 & 022 & 200211 & 310211 & 10301 \\ 220201 & 013 & 123 & 301211 & 100211 & 210211 & 00301 \\ 120201 & 230201 & 023 & 201211 & 000211 & 110211 & 220211 \end{matrix}

Observe that the expansions of length at most 3, which are the bold entries in the table above, are at the positions given by the domain of w^{(3)} above. Moreover, the values of these entries are precisely the σ-representations of the corresponding values of w^{(3)} with zeros added on the right to complete to three digits and, conversely, when we order the bold face numbers in the table lexicographically, their rank numbers are presented in w^{(3)}.

Example 2.

As second example we consider the flipped Tribonacci substitution

(E2)  σ(0) = 01, σ(1) = 20, σ(2) = 0.

The incidence matrix and its inverse are given by

M_{σ} = ( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , M_{σ}^{−1} = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & −1 \\ 0 & 1 & −1 \end{matrix} ) .

The characteristic polynomial is x^{3} − x^{2} − x − 1 and therefore M_{σ} has the dominant eigenvalue β ≈ 1.839 and τ = β^{−1} ≈ 0.544. The normalized eigenvector of β is again given by a⃗ = (a_{0}, a_{1}, a_{2}) = (τ, τ^{2} + τ^{3}, τ^{2}), and therefore we have Ω = ℤ[τ]. By using M_{σ}^{−1} it is easy to produce the following list of transition vectors when we take c⃗_{1} = ^{t}(1, 0, 0), c⃗_{2} = ^{t}(1, 1, 0) (compare with Fig. 2)

\begin{matrix}n & a_{0}^{(n)} & a_{1}^{(n)} & a_{2}^{(n)} \\ 1 & ^{t}(1, 0) & ^{t}(−1, 1) & ^{t}(−1, −1) \\ 2 & ^{t}(−1, −1) & ^{t}(2, 1) & ^{t}(0, 2) \\ 3 & ^{t}(0, 2) & ^{t}(−1, −3) & ^{t}(2, −1) \\ 4 & ^{t}(2, −1) & ^{t}(−2, 3) & ^{t}(−3, −2) \\ 5 & ^{t}(−3, −2) & ^{t}(5, 1) & ^{t}(1, 5) \end{matrix}

The associated automaton is already given in Fig. 5 and the number system scheme is given by

We have already seen some projected words in Fig. 4, so we discuss whether the projection of the fixed point is space filling. This time we cannot argue with the criterion from [1] since the number system is not the usual β-expansion, which would be the usual Tribonacci expansion. According to Theorem 6 we have to check if all elements x_{0} + x_{1}τ + x_{2}τ^{2} with ∥(x_{0}, x_{1}, x_{2})∥_{∞} ≤ 53, where we have

∥B^{−1}∥_{∞} ≤ 1.111 and M_{1} = M_{2} ≤ \frac{2.094 · 2 · 3}{0.262} ≤ 47.954,

have a finite expansion in L (observe that the remark after Theorem 6 applies and therefore we have only to check the expansions in the language L). But already when we consider 1 − τ (cf. table below) and apply the algorithm we get the expansion (011)^{ω}:

1−τ = τ^{2}+τ^{3} = τ(τ +τ^{2}) = τ^{2}+(τ^{2}+(τ^{2}+τ^{4}))τ^{2} = τ ·τ +τ^{2}·τ^{2}+(τ^{2}+τ^{3})·τ^{3}

and we are back in the starting position. Hence the projected fixed point will not be space filling (compare with Fig. 6). Below we give a table of all expansions of f(x_{1}, x_{2}) = x_{1}(τ + τ^{2}) + x_{2}τ mod 1 for −3 ≤ x_{1} ≤ 3, −3 ≤ x_{2} ≤ 3 (in the upper part of the table we have the values for −3 ≤ x_{1} ≤ 1 and the in the lower part the values for 2 ≤ x_{1} ≤ 3):

\begin{matrix}00011 & 1111(011)^{ω} & 1101 & 1001 & 0111 \\ 100001 & 011001 & 0(011)^{ω} & 0001 & 1111001 \\ 000001 & 111 & 11 & 1 & 011 \\ 011100(011)^{ω} & 010001 & 001 & ε & 11(011)^{ω} & → \\ 111101 & 110(011)^{ω} & 100(011)^{ω} & (011)^{ω} & 01 \\ 011000(011)^{ω} & 001101 & 000(011)^{ω} & 1111 & 11001 \\ 1101111 & 1001111 & 0111111 & 010(011)^{ω} & 0011 \end{matrix} ; \begin{aligned}& 0100001 & 0001111001 \\ & 110011 & 100011 \\ & 0011001 & 000011 \\ → & 10(011)^{ω} & 01111(011)^{ω} \\ & 00(011)^{ω} & 111111 \\ & 10001 & 01101 \\ & 00001 & 11100(011)^{ω} \end{aligned}

We remark that it is clear from the main result in [34] that only ultimately periodic expansions appear (since the dominant root of M_{σ} is a Pisot number and Ω ⊆ ℚ[τ]). It can be shown that (011)^{ω} is the only period which appears in this case.

Example 3.

Let the substitution σ be given by

(E3)  σ(0) = 01, σ(1) = 0002, σ(2) = 0.

The incidence matrix and its inverse are

M_{σ} = ( \begin{matrix}1 & 1 & 0 \\ 3 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) , M_{σ}^{−1} = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & −1 \\ 0 & 1 & −3 \end{matrix} ) .

The characteristic polynomial is x^{3} − x^{2} − 3x − 1 = (x^{2} − 2x − 1)(x + 1) and therefore M_{σ} has a dominant eigenvalue β = 1 + \sqrt{2}. Thus τ = β^{−1} = \frac{1}{5}(1 − \sqrt{2}) and τ^{2} + 2τ = 1. The eigenvector of M_{σ} to β is given by a⃗ = (a_{0}, a_{1}, a_{2}) = (τ, τ + τ^{2}, τ). Thus Ω = ℤ[τ], but degβ = 1 < k = 2. Using M_{σ}^{−1} we get the following list of transition vectors in the canonical case:

\begin{matrix}n & a_{0}^{(n)} & a_{1}^{(n)} & a_{2}^{(n)} \\ 1 & ^{t}(0, 1) & ^{t}(0, −1) & ^{t}(1, −3) \\ 2 & ^{t}(1, −3) & ^{t}(−1, 4) & ^{t}(−3, 8) \\ 3 & ^{t}(−3, 8) & ^{t}(4, −11) & ^{t}(8, −20) \\ 4 & ^{t}(8, −20) & ^{t}(−11, 28) & ^{t}(−20, 49) \end{matrix}

The associated automaton is given by

and the associated number system scheme reads

Again the number system has the property (F), since it is the usual βexpansion and Akiyama’s criterion [1] applies. Thus σ is space filling. In the canonical case we have (b_{0}, b_{1}, b_{2}) = (1, 1 + τ, τ). Consequently f(x_{1}, x_{2}) = x_{1}(1+τ)+x_{2}τ mod 1. We take b_{0} = 1, b_{1} = 1+τ as a basis for Ω. The kernel of f is therefore generated by x⃗_{2} = ^{t}(x_{1}, x_{2}) = ^{t}(−1, 1), since b_{2} = b_{1} − b_{0}.

Therefore, the projected fixed point of σ completely fills Ψ (ℤ^{2}/ ker f) = ℤe_{1}^{(2)} which is therefore the domain of Ψ(Ŵ).

We give a list of the expansions of f(x_{1}, 0) = x_{1}(1 + τ) mod 1 for −5 ≤ x_{1} ≤ 8, i.e. the σ-representations of the corresponding numbers above:

13 0111 12 01 11 ε 1 121 011 111 001 101 12121 012

For the canonical projections of the words u^{(1)} = 01, u^{(2)} = 010002 in thin letter type and their Ψ-images in bold letter type we get

\begin{matrix}w^{(1)} & w^{(2)} \\ 1 0 1 & 2 5 4 1 3 0 2 3 1 4 5 \end{matrix}

and for u^{(3)} = 0100020101010 we get

w^{(3)} ; 4 7 1 9 3 4 6 12  10 2 8 0 6 11 3 9 1 7  4 8 2 10 12

Observe that the expansions of length at most 3 (the bold entries in the table above) are exactly those that appear in the domain of Ψ(w^{(3)}).

Example 4.

We consider the substitution defined by

(E4)  σ(0) = 01, σ(1) = 2, σ(2) = 3, σ(3) = 4, σ(4) = 0.

We have taken this example from [9, p. 21]. The incidence matrix is

M_{σ} = ( \begin{matrix}1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{matrix} ) .

The characteristic polynomial of M_{σ} is equal to x^{5} − x^{4} − 1 = (x^{3} − x − 1)(x^{2} − x + 1). Thus, there is a dominant root β ≈ 1.325 which is a cubic Pisot unit, and a quadratic factor the roots of which have absolute value equal to 1. We have τ = β^{−1} ≈ 0.755 and τ^{3} + τ^{2} = 1. The eigenvalue of M_{σ} to β is

a⃗ = (a_{0}, a_{1}, a_{2}, a_{3}, a_{4}) = (τ, τ^{5}, τ^{4}, τ^{3}, τ^{2}).

Therefore, Ω = ℤ[τ]. The associated automaton is

and the associated number system scheme By using

M_{σ}^{−1} = ( \begin{matrix}0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & −1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{matrix} )

it is easy to get the transition vectors. E.g. we have for n = 11 that

u^{(11)} = 0123400101201230123401234001234001

and

(a_{0}^{(11)}, a_{1}^{(11)}, a_{2}^{(11)}, a_{3}^{(11)}, a_{4}^{(11)}) = ( \begin{matrix}0 & 0 & 1 & −2 & 1 \\ 1 & −1 & 0 & 1 & −2 \\ −2 & 3 & −1 & 0 & 1 \\ 1 & −3 & 3 & −1 & 0 \end{matrix} ) .

In the canonical case (b_{0}, b_{1}, b_{2}, b_{3}, b_{4}) = (1, τ^{4}, τ^{3}, τ^{2}, τ). We pick b_{0} = 1, b_{3} = τ^{2}, b_{4} = τ as a basis for Ω. Since b_{1} = −b_{0} + b_{3} + b_{4} and b_{2} = b_{0} − b_{3}, the projection Ψ is given by the vectors x⃗_{1} = ^{t}(1, 0, −1, −1), x⃗_{2} = ^{t}(0, 1, 1, 0). In fact

domΨ(Ŵ ) = Ψ (ℤ^{4}/ ker f) = ℤe_{3}^{(4)} + ℤe_{4}^{(4)},

since the associated number system has the finiteness property. This follows again by the criterion in [1], since the number system gives the usual βexpansion. We get

Ψ (w^{(11)}) ; 33 29 14 7 27 12 32 18 3 23 16 1 21 6 26 11 31 9 30 15 0 20 5 25 19 4 24 8 28 13 17 2 22 10

This roundwalk can be obtained by using the images of the transition vectors in the (x_{3}, x_{4})-plane, which are given by

Ψ (a_{0}^{(11)}) = ( \begin{matrix}0 \\ 0 \\ −3 \\ 1 \end{matrix} ) , Ψ (a_{1}^{(11)}) = ( \begin{matrix}0 \\ 0 \\ 4 \\ −3 \end{matrix} ) , Ψ (a_{2}^{(11)}) = ( \begin{matrix}0 \\ 0 \\ 0 \\ 4 \end{matrix} ) ,

Ψ (a_{3}^{(11)}) = ( \begin{matrix}0 \\ 0 \\ −3 \\ −3 \end{matrix} ) , Ψ (a_{4}^{(11)}) = ( \begin{matrix}0 \\ 0 \\ 4 \\ 1 \end{matrix} ) .

It can clearly be seen how the plane is filled up. Since (b_{0}, b_{1}, b_{2}, b_{3}, b_{4}) = (1, τ^{4}, τ^{3}, τ^{2}, τ), the corresponding list of expansions of f(0, 0, x_{3}, x_{4}) = x_{3}τ^{2} + x_{4}τ mod 1 is given by the following table, where all finite σrepresentations of f(x⃗) = x_{3}τ^{2} + x_{4}τ mod 1 with x⃗ = (0, 0, x_{3}, x_{4}) and −4 ≤ x_{3} ≤ 4, −3 ≤ x_{4} ≤ 3 are shown (the upper part of the table contains the expansions for −4 ≤ x_{3} ≤ −2, the middle part the expansion for −1 ≤ x_{3} ≤ 1 and the lower part for 2 ≤ x_{3} ≤ 4):

10000100001  00100001000001 00000001000001
00000100001  10000000001 00010000001
00100000001  00000000001 10000001
0100001000000001 00001000001 10000001  →
1000010000001 00100001 00000001
0000010000001  1000000000001 0001000000001
0010000000001  0000000000001 0100000000001
01000001000001 00001000000001 100000001
100001  0010000001  000000001
000001  1  0001
→ 001  ε  01  ⇒
01000001  00001  1000000001
1000001000001 0010000001  1000000001
0000001000001 0100001000001 0000100001
000100001  100001000001  00100001000000001
010000001  000001000001  100000000001
1000001  001000000001  000000000001
⇒ 0000001  0100001  000010000001
0001000001  100001000000001 001000001000001
0100000001  000001000000001 100000000000001
100000010000001 001000000000001 000000000000001

It can be seen that the expansions of length at most 11, which are again the bold entries, are exactly at the places of domΨ(w^{(11)}).

Example 5.

Finally let the substitution be defined by

(E5)  σ(0) = 02111111, σ(1) = 30, σ(2) = 1000000, σ(3) = 0.

The incidence matrix and its inverse are given by

M_{σ} = ( \begin{matrix}1 & 6 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 6 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ) , M_{σ}^{−1} = ( \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 0 & 1 & −6 \\ 1 & 0 & −6 & 35 \\ 0 & 1 & 0 & −1 \end{matrix} ) .

The characteristic polynomial is equal to x^{4} − x^{3} − 12x^{2} − 7x − 1 = (x^{2} − 4x − 1)(x^{2} + 3x + 1) and therefore it has a dominant Pisot root given by β = 2 + \sqrt{5} and τ = \sqrt{5} − 2. The two roots of the other polynomial are −\frac{1}{2}(3 ∓ \sqrt{5}), which lie on both sides of the unit circle. The eigenvalue of M_{σ} to β is

(a_{0}, a_{1}, a_{2}, a_{3}) = (τ, τ^{2} + τ^{3}, 6τ^{2} + τ^{3} + τ^{4}, τ^{2}).

The associated automaton is

and the number system scheme reads

We have (b_{0}, b_{1}, b_{2}, b_{3}) = (1, τ +τ^{2}, 6τ +τ^{2}+τ^{3}, τ) and by choosing b_{0}, b_{3} as a basis we get x⃗_{1} = (1, 0, 3), x⃗_{2} = (0, 1, −19) for the description of the map Ψ. E.g. the word u^{(2)} = 021111111000000303030303030 and the transition vectors in the canoncial case are given by

(a_{0}^{(2)}, a_{1}^{(2)}, a_{2}^{(2)}, a_{3}^{(2)}) = ( \begin{matrix}1 & −6 & 35 & −1 \\ 0 & −6 & 36 & 1 \\ −1 & 41 & −244 & −5 \end{matrix} )

and their projections are

(Ψ (a_{0}^{(2)}) , Ψ (a_{1}^{(2)}) , Ψ (a_{2}^{(2)}) , Ψ (a_{3}^{(2)})) = ( \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ −4 & −55 & 335 & 17 \end{matrix} ) .

We give a list of σ-expansions of f(0, x_{2}) = τx_{2} mod 1 for 10 ≤ x_{2} ≤ 10 (in the upper part the values −10 ≤ x_{2} ≤ −3, in the middle part −2 ≤ x_{2} ≤ 5 and in the lower part the remaining values are shown):

2(13)^{ω} 61 01471 123(13)^{ω} 1671 511 01 1(13)^{ω} →

→ 1571 411471 ε 1 1471 3(13)^{ω} 71 0411471 ⇒

⇒ 1371 2171 611 01571 1271

Indeed the expansions of length at most 2 are at the positions where the above roundwalk passes. Note that −3τ corresponds to 1(13)^{ω}, since

1 − 3τ = τ · 1 + (τ^{2} + τ^{3})τ + (3τ)τ^{2}
= τ · 1 + (τ^{2} + τ^{3})τ + (τ + 7τ^{2} + 2τ^{3} + τ^{4})τ^{2} + τ^{2}τ^{3} + (3τ)τ^{4}

and we are back in state 0. Since there are values which have an infinite expansion, the limit word Ŵ is not space filling.

References

[1] S. Akiyama, Cubic Pisot units with finite beta expansion, Algebraic number theory and Diophantine analysis (Graz, 1998), pp. 11-26, de Gruyter, Berlin, 2000.

[2] S. Akiyama, Self affine tilings and Pisot numeration system, Number Theory and its Applications (Kyoto, 1997), pp. 7-17, Kluwer Acad. Publ., Dordrecht, 1999.

[3] S. Akiyama, Pisot numbers and greedy algorithm, Number Theory: Diophantine, Computational and Algebraic Aspects (K. Győry, A. Pethő and V.T. Sós eds.), pp. 9-21, de Gruyter, 1998.

[4] S. Akiyama and J.M. Thuswaldner, A survey on topological properties of tiles related to number systems, Geom. Dedicata 109 (2004), 89-105.

[5] P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin 8 (2001), 181-207.

[6] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1, Bull. Soc. Math. France 119 (1991), 199-215.

[7] M. Baake and R.V. Moody, Directions in mathematical quasicrystals, CRM Monograph Series 13, AMS, Providence, RI, 2000.

[8] R.B. Bapat and T.E.S. Raghavan, Nonnegative matrices and applications, Encyclopedia of Mathematics and its Applications 64, Cambridge Univ. Press, Cambridge, 1997.

[9] V. Berthé and A. Siegel, Tilings associated with beta-numeration and substitutions, Integers: Electronic J. of Comb. Number Theory, to appear.

[10] V. Berthé and R. Tijdeman, Lattices and multi-dimensional words, Theoret. Comput. Sci. 319 (2004), 177-202.

[11] V. Berthé and L. Vuillon, Tillings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math. 223 (2000), 27-53.

[12] V. Berthé and L. Vuillon, Suites doubles de basse complexité, J. Théor. Nombres Bordeaux 12 (2000), 179-208.

[13] V. Berthé and L. Vuillon, Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb. 6 (2001), 121-138.

[14] A. Bertrand, Dévelopements en base de Pisot et répartition modulo 1, C. R. Acad. Sci. Paris 285 (1977), 419-421.

[15] V. Canterini, Connectedness of geometric representation of substitutions of Pisot type, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 77-89.

[16] J.-M. Dumont and A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci. 65 (1989), 153-169.

[17] H. Ei and S. Ito, Tilings from some non-irreducible, Pisot substitutions, Discrete Math. Theor. Comput. Sci. 7 (2005), 81-122.

[18] S. Eilenberg, Automata, languages, and machines, Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press, New York, 1974.

[19] J.-H. Evertse, On the norm form inequality |F (x)| ≤ m, Publ. Math. Debrecen 56 (2000), 337-374.

[20] C. Frougny and B. Solomyak, Finite beta-expansions, Ergodic Theory Dynam. Systems 12 (1992), 713-723.

[21] P.J. Grabner and M. Rigo, Additive functions with respect to numeration systems on regular languages, Monatsh. Math. 139 (2003), 205-219.

[22] J.C. Lagarias and Y. Wang, Substitution Delone sets, Discrete Comput. Geom. 29 (2003), 175-209.

[23] S. Ito and H. Rao, Atomic surfaces, tilings and coincidence I. Irreducible case, Israel J. Math., to appear.

[24] D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems 4 (1984), 283-300.

[25] D. Lind, Matrices of Perron Numbers, J. Number Theory 40 (1992), 211-217.

[26] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002.

[27] P. Lecomte and M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001), 27-44.

[28] P. Lecomte and M. Rigo, On the representation of real numbers using regular languages, Theory Comput. Syst. 35 (2002), 13-38.

[29] P. Lecomte and M. Rigo, Real numbers having ultimately periodic representations in abstract numeration systems, Inform. and Comput. 192 (2004), 57-83.

[30] M. Morse and G.A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), 815-866.

[31] W. Parry, On the β-expansion of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 269-278.

[32] G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France 110 (1982), 147-178.

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

[34] M. Rigo and W. Steiner, Abstract β-expansions and ultimately periodic representations, J. Théor. Nombres Bordeaux 17 (2005), 283-299.

[35] S. Rosema and R. Tijdeman, On the Tribonacci substitution, Integers: Electronic J. of Comb. Number Theory, to appear.

[36] R. Salem, Algebraic Numbers and Fourier Analysis, D.C. Heath & Co.: Boston, 1963.

[37] Y. Sano, P. Arnoux, and S. Ito, Higher dimensional extensions of substitutions and their dual maps, J. Anal. Math. 83 (2001), 183-206.

[38] M. Senechal, Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995.

[39] A. Siegel, Pure discrete spectrum dynamical system and periodic tiling associated with a substitution, Ann. Inst. Fourier (Grenoble) 54 (2004), 288-299.

[40] R.J. Simpson and R. Tijdeman, Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester, Proc. Amer. Math. Soc. 131 (2003), 1661-1667.

[41] V.F. Sirvent and B. Solomyak, Pure discrete spectrum for one-dimensional substitution systems of Pisot type, Canad. Math. Bull. 45 (2002), 697-710.

[42] K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math. Soc. 12 (1980), 269-278.

[43] W.M. Schmidt, Linearformen mit algebraischen Koeffizienten II, Math. Ann. 191 (1971), 1-20.

[44] J.M. Thuswaldner, Unimodular substitions and their associated tiles, J. Théor. Nombres Bordeaux, to appear.

[45] R. Tijdeman, Rauzy substitutions and multi-dimensional words, Theoret. Comput. Sci., to appear.

Clemens Fuchs Technische Universität Graz Institut für Mathematik Steyrergasse 30, 8010 Graz (Austria) e-mail: clemens.fuchs@tugraz.at

Robert Tijdeman Universiteit Leiden Mathematisch Instituut

SUBSTITUTIONS AND THE SPACE FILLING PROPERTY 43

Niels Bohrweg 1, 2300 RA Leiden (The Netherlands) e-mail: tijdeman@math.leidenuniv.nl