A CERTAIN FINITENESS PROPERTY OF PISOT NUMBER SYSTEMS

SHIGEKI AKIYAMA, HUI RAO AND WOLFGANG STEINER

Abstract. In the study of substitutative dynamical systems and Pisot number systems, an algebraic condition, which we call ‘weak finiteness’, plays a fundamental role. It is expected that all Pisot numbers would have this property. In this paper, we prove some basic facts about ‘weak finiteness’. We show that this property is valid for cubic Pisot units and for Pisot numbers of higher degree under a dominant condition.

1. Introduction

Let β > 1 be a real number. The β-transformation is a piecewise linear transformation on [0, 1) defined by

T_{β} : x ⟶ βx − ⌊βx⌋,

where ⌊ξ⌋ is the largest integer not exceeding ξ. By iterating this map and considering its trajectory

x ⟶^{x_{1}} T_{β}(x) ⟶^{x_{2}} T_{β}^{2}(x) ⟶^{x_{3}} …

with x_{i} = ⌊βT_{β}^{i−1}(x)⌋, we obtain the greedy expansion of x:

x = \frac{x_{1}}{β} + \frac{x_{2}}{β^{2}} + \frac{x_{3}}{β^{3}} ⋯ = .x_{1}x_{2}x_{3} ….

For any real number x > 0, there is an m > 0 such that β^{−m−1}x ∈ [0, 1). Thus we can express each x in the form

x = x_{−m}β^{m} + ⋯ + x_{−1}β + x_{0} + \frac{x_{1}}{β} + ⋯ = x_{−m} … x_{−1}x_{0}.x_{1}x_{2}x_{3} …,

which is called the beta expansion. If there is an integer k such that x_{i} = 0 for i > k, then we say that the β-expansion of x is finite and we occasionally omit writing zeros in the tail like: x = x_{−m}x_{−m+1} … x_{k−1}x_{k}.

Formally we may consider the trajectory of 1:

1 ⟶^{a_{1}} T_{β}(1) ⟶^{a_{2}} T_{β}^{2}(1) ⟶^{a_{3}} ….

Date: October 6, 2003.

Key words and phrases. Pisot number, Beta expansion, Weak finiteness.

The first author is supported by the Japanese Ministry of Education, Culture, Sports, Science and Technology, Grand-in Aid for fundamental research, 14540015, 2002–2004.

The third author was supported by the Austrian Science Fund FWF, grant S8302-MAT.

We call a_{1}a_{2}a_{3} … the expansion of one and denote it by d_{β}(1). Define

d_{β}^{∗}(1) = \begin{cases}d_{β}(1) & if d_{β}(1) is not finite \\ \overline{a_{1} … a_{d−1}(a_{d} − 1)} & if d_{β}(1) = a_{1} … a_{d} with a_{d} ≠ 0, \end{cases}

where \overline{x_{1} … x_{k}} stands for the periodic expansion x_{1} … x_{k}x_{1} … x_{k} . . .. Then a sequence (finite or infinite) over the alphabet {0, 1, 2, … } is said to be admissible if all its right truncations are lexicographically less than d_{β}^{∗}(1). A sequence is the β-expansion of some real number if and only if it is admissible. (See Parry [18] and Ito-Takahashi [17] for details). Let Fin(β) be the set of non-negative real numbers with finite β-expansion. Denote by ℤ[β] the minimal ring containing ℤ and β and by ℤ[β]_{≥0} the nonnegative elements of ℤ[β]. We say that the number β has the finiteness property or the property (F) if

(F): Fin(β) = ℤ[1/β]_{≥0} holds. This property was introduced by Frougny-Solomyak [14]. They showed that it implies that β is a Pisot number, i.e. a real algebraic integer greater than 1 with all conjugates lying strictly inside the unit circle, and they found the following class of Pisot numbers satisfying this property. Here a root of a polynomial is called dominant, if it has the maximal modulus of all roots.

Theorem A. (Frougny-Solomyak [14]) If β is the dominant root of the polynomial x^{d}−b_{1}x^{d−1}−b_{2}x^{d−2}−⋯−b_{d} ∈ ℤ[x] with b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{d} > 0, then β is a Pisot number and has the property (F).

Another class of Pisot numbers with (F) was found by Hollander.

Theorem B. (Hollander ([15]) If β is the dominant root of the polynomial x^{d} − b_{1}x^{d−1} − b_{2}x^{d−2} − ⋯ − b_{d} ∈ ℤ[x] with b_{1} > ∑_{i=2}^{d} b_{i} and b_{i} ≥ 0 (1 ≤ i ≤ d), then β is a Pisot number and has the property (F).

An alternative proof of Theorem B is given in §6. Of particular interest are Pisot units, which are Pisot numbers as well as algebraic units. Akiyama-Sadahiro [5] and Akiyama [1] used Pisot units β with the property (F) to construct tilings of ℝ^{d−1} (where d is the degree of β). Praggastis [19] showed that such tiling gives rise to a Markov partition of the torus when β satisfies (F). The idea of these constructions is due to Thurston [27]. Note that a tiling close to these was originally obtained by Rauzy [20] in connection with substitutative dynamical systems. Arnoux-Ito [6] gave a further generalization of this ‘Rauzy fractal’ and described the relation with Markov partitions of toral automorphisms. A lot of applications of this theory are found (cf. Ito-Rao [13], Steiner [26]).

Note that there are Pisot numbers without the property (F), in particular all numbers with infinite expansions of one. A classification of cubic Pisot units with (F) was established in Akiyama [2] (see also Proposition 1).

The first author [3] also showed that the origin is an ‘exclusive’ inner point of the central tile if and only if (F) holds. For the tiling property, he showed that the condition (F) can be relaxed. Namely, for a Pisot unit β, Thurston’s construction gives a tiling if and only if

(W): For any x ∈ ℤ[1/β]_{≥0} and any positive ε, there exist y, z ∈

Fin(β) that x = y − z and z < ε. holds. We call this condition weak finiteness property or (W) in this paper.

This property was first studied by Hollander [15]. He tried to show that a substitutative dynamical system associated to beta expansions has purely discrete spectrum by reducing this problem to showing (W). Sidorov [24] used this property to construct an almost conjugacy between the beta shift and a related toral automorphism. He also found another application of (W) for Bernoulli convolutions [25].

To study the tilings rising from Rauzy fractal, Ito-Rao [16] introduced the super-coincidence condition of a substitution. (W) is equivalent to the super-coincidence condition if we restrict to substitutions coming from β-numeration systems (see Ei-Ito-Rao [12]).

The present paper is devoted to the study of the property (W).

A Salem number is a real algebraic integer greater than 1 such that all its conjugates lie inside the closed unit disk and at least one conjugate lies on the unit circle. First we show

Theorem 1. If β has the property (W), then it must be a Pisot or a Salem number.

However, we are not able to prove (W) for any Salem number. Second, we derive an easier criterion for the property (W).

Theorem 2. The property (W) is equivalent to:

(W’): For any x ∈ ℤ[1/β] ∩ [0, 1), there exist y, z ∈ Fin(β) such that x = y − z with y < β and z < 1.

This will be used to prove Theorem 4 in §5 and Proposition 3 in §6. It is easy to show that quadratic Pisot numbers β satisfy this weakly finiteness (see §2). In [3] it is conjectured that the property (W) holds for all Pisot units, in [25] that it should hold even for all Pisot numbers. We give partial answers to this conjecture.

Theorem 3. If β is a cubic Pisot unit, then β satisfies (W).

We do not know whether all cubic Pisot numbers satisfy (W).

Theorem 4. Let β be the dominant root of x^{d}−b_{1}x^{d−1}−⋯−b_{d} ∈ ℤ[x]. If b_{1} > ∑_{j=2}^{d} |b_{j}| (and (b_{1}, b_{2}) ≠ (2, −1)), then β satisfies (W).

Hereafter we refer to the inequality b_{1} > ∑_{j=2}^{d} |b_{j}| as dominant condition.

The paper is organized as follows. In §2, we review known results and also prove Theorems 1 and 2. If we knew the set P of purely periodic orbits of T_{β}, then we could show (W) without difficulty. In §3 the set P is given for cubic Pisot units by using an idea of [15]. Thus we can show Theorem 3 in §4. In §5, we prove Theorem 4. In §6, we discuss an alternative approach by using a branching beta expansion. This gives an efficient algorithm to confirm (F) or (W) in practice.

2. General criteria for weak finiteness

First we prove the necessary condition for numbers satisfying (W) given in Theorem 1.

Proof of Theorem 1. (W) implies that β is an algebraic integer, since we have an expression β − ⌊β⌋ = y − z with y, z ∈ Fin(β) and z < y < 1. Assume that there is a conjugate γ of β with |γ| > 1. Take a positive integer m. From (W) we infer

β^{m} − ⌊β^{m}⌋ = ∑_{i=1}^{ℓ} c_{i}β^{−i}

with c_{i} ∈ (−β, β) ∩ ℤ. Thus we have

γ^{m} − ⌊β^{m}⌋ = ∑_{i=1}^{ℓ} c_{i}γ^{−i} ≤ \frac{⌊β⌋}{1 − |γ|}.

This is absurd since the left side is not bounded when m → ∞. □

Now we turn to sufficient conditions for (W). It is obvious that (F) implies (W). In [3], it is shown that the Pisot numbers with the following property satisfy (W):

(PF): For each polynomial P (x) with non negative integer coef-

ficients, P (β) ∈ Fin(β). This condition was studied in [14] and proved for β where the expansion of one a_{1}a_{2}a_{3} … has decreasing digits. Quadratic Pisot numbers satisfy either (F) by Theorem A or (PF) by the above criterion. Hence each quadratic Pisot number has the property (W).

For Pisot numbers, it is sufficient to test a finite set of ℤ[1/β]:

Bertrand [9] and Schmidt [23] proved independently that every element of ℚ(β), so in particular every element of ℤ[1/β], has eventually periodic β-expansion if β is a Pisot number. (For Salem numbers, this is unknown.) Therefore we study the set

P = {x ∈ ℤ[β]_{≥0} | T_{β}^{m}(x) = x for some m > 0}.

(The periodic points of ℤ[1/β] are always in ℤ[β], since we can choose n large such that x = β^{n}x − P (β), and both β^{n}x and P (β) belong to ℤ[β].) It is easily seen that P is a finite set and gives the set of all possible periodic tails of beta expansions (cf. [3] Lemma 2). Therefore for Pisot numbers, (W) is equivalent to

(P): For any x ∈ P and any positive ε, there exist y, z ∈ Fin(β)

such that x = y − z and z < ε. Furthermore, in [15], it is implicitly noted that

Lemma 1. The property (W) is equivalent to

(H): For any x ∈ P, there exist y, z ∈ Fin(β) such that x = y − z with y < 1 and z < 1.

For the convenience of the reader, we give the proof due to Hollander.

Proof. For each x ∈ ℤ[1/β] and for a sufficiently large n, we have the beta expansion

x = x_{−m} … x_{−1}x_{0}.x_{1} … x_{n} + β^{−n−1}τ

with τ = .\overline{c_{1} … c_{ℓ}} ∈ P. We may assume that τ ≠ 0. Since this expansion is less than d_{β}(1) at any starting point, there exists n so that x_{−m} … x_{−1}x_{0}.x_{1} … x_{n−1}(x_{n} + 1) is admissible. Express τ = y − z by (H). Then, as finite words, the beta expansion of x_{−m} … x_{n}+β^{−n−1}y coincides with the concatenation of x_{−m} … x_{n} and the beta expansion of y. This means

x = (x_{−m} … x_{−1}x_{0}.x_{1} … x_{n} + β^{−n−1}y) − β^{−n−1}z

gives a desired expression. Thus β has the property (W). □

Now we turn to the equivalent condition for (W) which is needed in §5 and §6. Although we do not have any example, the following proof is valid even for Salem numbers.

Proof of Theorem 2. Clearly, (W) implies (W’). We are going to prove the other direction.

Let d_{β}^{∗}(1) = a_{1}^{∗}a_{2}^{∗} … be the infinite representation of 1. Pick x ∈ ℤ[1/β] with infinite greedy expansion x = .x_{1}x_{2} … and let x = .B_{1}B_{2} … be its free block decomposition, which is recursively given by B_{1} = x_{1} … x_{k_{1}} such that x_{1} … x_{k_{1}−1} = a_{1}^{∗} … a_{k_{1}−1}^{∗} and x_{k_{1}} < a_{k_{1}}^{∗}, B_{2} = x_{k_{1}+1} … x_{k_{2}} such that x_{k_{1}+1} … x_{k_{2}−1} = a_{1}^{∗} … a_{k_{2}−k_{1}−1}^{∗} and x_{k_{2}} < a_{k_{2}−k_{1}}^{∗} and so on.

We distinguish four cases:

i) There exists arbitrarily large j such that x_{k_{j}} < a_{k_{j}−k_{j−1}}^{∗} − 1. In this case, we consider

η = x − .x_{1} … x_{k_{j}} ∈ ℤ[β^{−1}] ∩ [0, β^{−k_{j}}).

Then β^{k_{j}}η is in ℤ[β^{−1}] ∩ [0, 1) and has, by assumption (W’), a representation

β^{k_{j}}η = y_{0}.y_{1}y_{2} … y_{J} − .z_{1}z_{2} … z_{J}

with y_{0} ∈ {0, 1}. Hence

x = .x_{1} … x_{k_{j}−1}(x_{k_{j}} + y_{0})y_{1} … y_{J} − .0^{k_{j}}z_{1}z_{2} … z_{J}
= y − z,

where y, z ∈ Fin(β) and z < β^{−k_{j}}. Since k_{j} can be arbitrarily large, we get the desired representation.

ii) There exists arbitrarily large j such that k_{j+1} − k_{j} > k_{j} − k_{j−1}. Then we first claim that

x_{k_{j−1}+1} … x_{k_{j}−1}(x_{k_{j}} + 1)0^{k_{j+1}−k_{j}−2}1

is admissible. By the definition of the free block decomposition, x_{k_{j−1}+1} … x_{k_{j}−1}(x_{k_{j}} + 1) is admissible. Hence the only possibility that the claim is false would be

x_{k_{j−1}+1} … x_{k_{j}−1}(x_{k_{j}} + 1)0^{k_{j+1}−k_{j}−1} = a_{1}^{∗} … a_{k_{j+1}−k_{j−1}−1}^{∗},

hence a_{k_{j}−k_{j−1}+1}^{∗} = ⋯ = a_{k_{j+1}−k_{j−1}−1}^{∗} = 0, in particular a_{k_{j+1}−k_{j}}^{∗} = 0, but this contradicts a_{k_{j+1}−k_{j}}^{∗} > x_{k_{j+1}} and the claim is proved. So set

η = .x_{1} … x_{k_{j}−1}(x_{k_{j}} + 1) − x
< .x_{1} … x_{k_{j}−1}(x_{k_{j}} + 1) − .x_{1} … x_{k_{j}}a_{1}^{∗} … a_{k_{j+1}−k_{j}−1}^{∗}
< β^{−k_{j}} − a_{1}^{∗}β^{−k_{j}−1} − ⋯ − a_{k_{j+1}−k_{j}−1}^{∗}β^{−k_{j+1}+1} < β^{−k_{j+1}+1},

By assumption (W’), we get

β^{k_{j+1}−1}η = y_{0}.y_{1}y_{2} … y_{J} − .z_{1}z_{2} … z_{J}

and thus

x = .x_{1} … x_{k_{j}−1}(x_{k_{j}} + 1)0^{k_{j+1}−k_{j}−1}z_{1}z_{2} … z_{J} − .0^{k_{j+1}−2}y_{0}y_{1} … y_{J}
= y − z,

where y, z ∈ Fin(β) and z < β^{−k_{j+1}+2}.

It remains to deal with the case k_{j+1} − k_{j} = k_{j} − k_{j−1} = ℓ for all sufficiently large j where the assumption of i) fails, i.e. x is eventually periodic with period a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1).

iii) Let x = .\overline{a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1)}.

Let κ ≥ 0 be the integer such that d_{β}^{∗}(1) = .a_{1}^{∗} … a_{ℓ}^{∗}0^{κ}a_{ℓ+κ+1}^{∗} … and a_{ℓ+κ+1}^{∗} > 0. Let, for arbitrary j > 0,

η = .(a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1))^{j−1}a_{1}^{∗} … a_{ℓ}^{∗} − x

= β^{−jℓ} − \frac{(a_{1}^{∗}β^{−1} + ⋯ + a_{ℓ−1}^{∗}β^{−ℓ+1} + (a_{ℓ}^{∗} − 1)β^{−ℓ})β^{−jℓ}}{1 − β^{−ℓ}}

= \frac{a_{ℓ+κ+1}^{∗}β^{−ℓ−κ−1} + a_{ℓ+κ+2}^{∗}β^{−ℓ−κ−2} + ⋯}{1 − β^{−ℓ}}β^{−jℓ} < \frac{β^{−jℓ−ℓ−κ}}{1 − β^{−ℓ}} . (1)

From a_{ℓ}^{∗} > 0 we infer that d_{β}^{∗}(1) is lexicographically larger than 10^{ℓ−2}1. Hence 1 > β^{−1} + β^{−ℓ} and (1 − β^{−ℓ})^{−1} < β. This together with (1) implies η < β^{−jℓ−ℓ−κ+1}.

If ℓ > 1, then η < β^{−jℓ−κ−1}, hence

η = .0^{jℓ+κ}y_{0}y_{1} … y_{J} − .0^{jℓ+κ+1}z_{1} … z_{J}

and

x = .(a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1))^{k−1}a_{1}^{∗} … a_{ℓ}^{∗}0^{κ+1}z_{1} … z_{J} − .0^{jℓ+κ}y_{0}y_{1} … y_{J}

gives the desired representation.

The case ℓ = 1, i.e. x = .\overline{(a_{1}^{∗} − 1)} (with a_{1}^{∗} ≥ 2) is more complicated. The formula (1) becomes

(2)  η = \frac{a_{κ+2}^{∗}β^{−1} + a_{κ+3}^{∗}β^{−2} + ⋯}{1 − β^{−1}}β^{−j−κ−1}

and thus η < β^{−j−κ}. If η < β^{−j−κ−1}, then the argument for ℓ > 1 still works here. So we may assume β^{−j−κ−1} < η < β^{−j−κ}. From (W’), we have

η = .0^{j+κ−1}y_{0}y_{1} … y_{J} − .0^{j+κ}z_{1} … z_{J}.

Hence

x = .(a_{1}^{∗} − 1)^{j−1}a_{1}^{∗}0^{κ}z_{1} … z_{J} − .0^{j+κ−1}y_{0}y_{1} … y_{J}.

If .z_{1}z_{2} … < .a_{κ+2}^{∗}a_{κ+3}^{∗} …, then we already have the desired representation. So we assume

(3)  .z_{1}z_{2} … > .a_{κ+2}^{∗}a_{κ+3}^{∗} ….

We are going to show

(4)  η < (1 + β^{−1})β^{−j−κ−1}.

If this holds, then we have η − β^{−j−κ−1} ∈ (0, β^{−j−κ−2}). Hence

η − β^{−j−κ−1} = .0^{j+κ+1}y′_{0}y′_{1} … y′_{J′} − .0^{j+κ+2}z′_{1} … z′_{J′},

and

x = .(a_{1}^{∗} − 1)^{j−1}a_{1}^{∗}0^{κ+2}z′_{1} … z′_{J′} − .0^{j+κ}1y′_{0}y′_{1} … y′_{J′}

is a desired representation.

We may assume y_{1} = 0 because of z_{1} > 0. (Otherwise, decrease both y_{1} and z_{1}.) Hence we have

y_{0}.y_{1} … < 1.0a_{1}^{∗}a_{2}^{∗} … = 1 + β^{−1}.

This together with (3) implies

η < (1 + β^{−1} − a_{κ+2}^{∗}β^{−1} − a_{κ+3}^{∗}β^{−2} − …)β^{−j−κ}.

Substituting η by its expression in (2), we get

\frac{a_{κ+2}^{∗}β^{−2} + a_{κ+3}^{∗}β^{−3} + …}{1 − β^{−1}} < 1 + β^{−1} − a_{κ+2}^{∗}β^{−1} − a_{κ+3}^{∗}β^{−2} + …,

thus

a_{κ+2}^{∗}β^{−1} + a_{κ+3}^{∗}β^{−2} + ⋯ < (1 + β^{−1})(1 − β^{−1}).

Using (2) once again, we get (4).

iv) Finally we consider x = .x_{1} … x_{m}\overline{a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1)}. By iii), there exist .y_{1} … y_{J} and .z_{1} … z_{J} ∈ Fin(β) such that

.\overline{a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1)} = .y_{1} … y_{J} − .z_{1} … z_{J}.

Hence for any j,

x = .x_{1} … x_{m}(a_{1}^{∗} … a_{ℓ−1}^{∗}(a_{ℓ}^{∗} − 1))^{j}y_{1} … y_{J} − .0^{m+jℓ}z_{1} … z_{J}

is a desired representation. This completes the proof of the theorem.

□

3. Purely periodic orbits

In this section, we determine the set P, the purely periodic expansions in ℤ[β] for cubic Pisot units. Geometrically this set P corresponds to dual tiles sharing the origin (cf. [3]).

We first review briefly the idea of [15] to interpret T_{β} as a shift on a symbolic space. Let β > 1 be an algebraic integer. Let 1 = 0.b_{1}b_{2} … b_{d} be an arbitrary expression of 1 in base β, where b_{i} are integers. (We do not consider the admissibility and also allow b_{i} to be negative.) Let

r_{i} = 0.b_{i+1} … b_{d}, 0 ≤ i ≤ d − 1.

It is easy to check that {r_{0}, r_{1}, …, r_{d−1}} spans ℤ[β]. Hence for any x ∈ ℤ[β] ∩ [0, 1), there are integers z_{1}, z_{2}, …, z_{d} such that

x = z_{1}r_{d−1} + z_{2}r_{d−2} + ⋯ + z_{d}r_{0}

and a sequence (z_{d+1}, z_{d+2}, …), such that for each i ≥ 1,

(5)  0 ≤ z_{i}r_{d−1} + z_{i+1}r_{d−2} + ⋯ + z_{i+d−1}r_{0} < 1.

Then the sequence in the above formula is uniquely determined by initial values z_{1}, z_{2}, …, z_{d−1} and we call it a carry sequence of x. Let x_{i} = b_{1}z_{d+i−1} + ⋯ + b_{d}z_{i}, then it is easy to check that the β-expansion of x is 0.x_{1}x_{2} . . .. Hence

Lemma 2. ([15]) Let x ∈ ℤ[β] ∩ [0, 1). Then x ∈ P if and only if a carry sequence of x is purely periodic.

Let β > 1 be the dominant root of the polynomial

f(x) = x^{3} − ax^{2} − bx − c.

Then β is a Pisot number if and only if

|b − c| < a + c and c^{2} − b < sgn(c)(1 + ac)

holds. When c = 1, β is a Pisot number if and only if −a+1 ≤ b ≤ a+1. When c = −1, β is a Pisot number if and only if −a + 3 ≤ b ≤ a − 1. (cf. [2])

Proposition 1. Let β be a cubic Pisot unit. Then the set P is given by the following table.

c = 1 a = 1  b = 0, 1, 2  0
a ≥ 2 −1 ≤ b ≤ a + 1  0
a ≥ 3 −a + 1 ≤ b ≤ −2 \overline{(va + vb)}, v ≥ 0, admissible
c = −1 a ≥ 3 b = a − 1 0, \overline{(a − 1)(b − 1)}, \overline{(b − 1)(a − 1)},
\overline{a(b − 2)}, \overline{(b − 2)a}
a ≥ 4 2 ≤ b ≤ a − 2 0, \overline{(a − 1)(b − 1)}, \overline{(b − 1)(a − 1)}
a ≥ 2 b = 1 0, \overline{(a − 1)0}, \overline{0(a − 1)}, \overline{(a − 1)}
a ≥ 3 −a + 3 ≤ b ≤ 0 \overline{(av + bv − 2v)}, v ≥ 0, admissible

Proof. For a ≤ 6, this is checked by a theoretic bound on P (cf. [3], Lemma 2). In the following, we assume a ≥ 6. Let r_{0} = 1, r_{1} = \frac{b}{β} + \frac{c}{β^{2}} and r_{2} = \frac{c}{β}. Then \{r_{0}, r_{1}, r_{2}\} is a basis of ℤ[β]. Suppose (z_{i})_{i≥1} is a purely periodic carry sequence other than 0. Then

(6)  0 ≤ z_{i}r_{2} + z_{i+1}r_{1} + z_{i+2} < 1.

We denote

z_{min} = min{0, min_{z_{i}≤0} z_{i}}, z_{max} = max{0, max_{z_{i}≥0} z_{i}}.

i) c=1, b=a+1.

This case has been treated by [2]. Here we give a simpler proof. Let θ and θ′ (assume θ > θ′) be the roots of

r_{2}X^{2} + r_{1}X + 1 = 0.

Then θ′ < θ < −1. Let y_{i} = z_{i} − θz_{i+1} for i ≥ 0, then we have

z_{i}r_{2} + z_{i+1}r_{1} + z_{i+2} = y_{i}r_{2} + y_{i+1}(r_{1} + θr_{2}).

Since r_{1} + θr_{2} > 0 and r_{2} > 0, by (6) we have

y_{min}r_{2} + y_{max}(r_{1} + θr_{2}) < 1,
0 < y_{max}r_{2} + y_{min}(r_{1} + θr_{2}).

These two formulas imply that

−\frac{r_{2}}{(r_{1} + θr_{2})^{2} − r_{2}^{2}} < y_{min} ≤ y_{max} < \frac{r_{1} + θr_{2}}{(r_{1} + θr_{2})^{2} − r_{2}^{2}} .

When a ≥ 6, we have r_{1} > 1, r_{2} < \frac{1}{6} and −\frac{4}{3} < θ < −1. Hence from the above formula we have −\frac{1}{3} < y_{min} < y_{max} < \frac{4}{3}. So for any i > 1, −\frac{1}{3} < z_{i−1} − θz_{i} < \frac{4}{3} holds.

First we claim that z_{i} ≤ 0 implies z_{i−1} ≥ |z_{i}|. Since −\frac{1}{3} < z_{i−1} − θz_{i} and θ < −1, we have z_{i−1} > θz_{i} − \frac{1}{3} ≥ |z_{i}| − \frac{1}{3}. Hence the claim is true because z_{i} are integers.

Second, we assert that z_{i−1} ≤ −z_{i} when z_{i} > 0. From z_{i} > 0 we infer z_{i−1} ≤ 0, since we had z_{i−1} − θz_{i} > 1 − θ > \frac{4}{3} otherwise. Moreover, this implies z_{i−2} ≥ −z_{i−1}(≥ 0) by the above claim. Suppose our assertion is false, i.e. −z_{i} + 1 ≤ z_{i−1} ≤ 0. This together with z_{i−2} ≥ −z_{i−1} implies

z_{i−2}r_{2} + z_{i−1}r_{1} + z_{i}
≥ −z_{i−1}r_{2} + z_{i−1}r_{1} + (1 − z_{i−1})
≥ −z_{i−1}(r_{2} − r_{1} + 1) + 1 ≥ 1.

This contradicts (6) and establishes our assertion. Hence in any case we have |z_{i−1}| ≥ |z_{i}|. Since (z_{i}) is purely periodic, so (z_{i}) = \overline{z(−z)} for some constant z ≥ 0. Now by the left side of (6) we have 0 ≤ z(−r_{2} +r_{1} −1), which implies z = 0. Therefore the only element of P is 0.

ii) c = 1, 1 ≤ b ≤ a.

This case follows from Theorem A.

iii) c = 1, b = 0.

This case has follows from Theorem B.

iv) c = 1, −a + 2 ≤ b ≤ −1.

In this case r_{1} < 0 and r_{2} > 0. It is easy to check that

(7)  |r_{1}| + |r_{2}| < 1.

We assert that

(8)  |z_{min}| ≤ |z_{max}| − 1

holds. Setting z_{i} = z_{min} in r_{2}z_{i−2} + r_{1}z_{i−1} + z_{i} < 1, we get

0 ≤ r_{2}z_{i−2} + r_{1}z_{i−1} + z_{min} ≤ z_{max}r_{2} + z_{min}r_{1} + z_{min}.

Hence (z_{max} − z_{min})r_{2} ≥ z_{min}(r_{2} − r_{1} − 1). So no matter z_{min} = 0 or not, we have (8).

We claim that z_{i} = z_{max} implies z_{i−1} = z_{max}. Otherwise, setting z_{i} = z_{max} in r_{2}z_{i−2} + r_{1}z_{i−1} + z_{i} < 1, we get

r_{2}z_{min} + r_{1}(z_{max} − 1) + z_{max} ≤ r_{2}z_{i−2} + r_{1}z_{i−1} + z_{max} < 1.

This together with (8) implies (z_{max} − 1)(−r_{2} + r_{1} + 1) < 0. Hence z_{max} = 0 and z_{i} = 0 for any i. This is a contradiction and our claim is proved. Hence (z_{i} = z) is a constant word, and the β-expansion of x is 0.x_{1}x_{2} … with x_{i} = z(a + b) for any i ≥ 1. The proposition is proved in this case.

v) c = 1, b = −a + 1.

Let θ > θ′ be the roots of r_{2}X^{2} + r_{1}X + 1 = 0. Then θ > 1 > θ′ > 0. Using the same argument as in i), we have

y_{i}r_{2} + y_{i+1}(r_{1} + θr_{2}) < 1

where y_{i} = z_{i} − θz_{i+1}. When a ≥ 6 we have r_{1} + θr_{2} < 0. So setting y_{i+1} = y_{min} we get

y_{min}r_{2} + y_{min}(r_{1} + θr_{2}) < 1,

which implies z_{i} − θz_{i+1} > y_{min} > \frac{1}{r_{1}+(θ+1)r_{2}} > −\frac{3}{2} when a ≥ 6.

If z_{i} < −1, then clearly z_{i+1} < 0 by the above inequality. If z_{i} = −1, then z_{i+1} ≤ 0, but z_{i+1} = 0 will lead to z_{k} = 1 for k ≥ i + 2 by direct calculation and hence is impossible. So we conclude that z_{i} < 0 implies z_{i+1} < 0. From (6), it is easy to show that there is at least one z_{i} such that z_{i} ≥ 0. Hence we conclude that z_{i} ≥ 0 for any i.

Setting z_{i} = z_{max} in r_{2}z_{i−2} + r_{1}z_{i−1} + z_{i} < 1, it is clear that z_{i−1} must be z_{max} also. Hence z_{i} is a constant sequence and this case is settled.

vi) c = −1, 1 ≤ b ≤ a − 1.

In this case r_{1} > 0 and r_{2} < 0. Since |r_{1}| + |r_{2}| < 1, we have |z_{min}| ≤ z_{max} − 1 by the same argument as in (iv). Setting z_{i+2} = z_{max} in (6), we get

1 > z_{i}r_{2} + z_{i+1}r_{1} + z_{max}
> z_{max}r_{2} + z_{min}r_{1} + z_{max}
≥ z_{max}r_{2} − (z_{max} − 1)r_{1} + z_{max}.

Hence

(9)  z_{max} < 1 + \frac{−r_{2}}{1 − r_{1} + r_{2}} .

vi-1) b = a − 1. In this case z_{max} ≤ 2 by (9) when a ≥ 6. So z_{i} ∈ {−1, 0, 1, 2}. If z_{0} = −1 and z_{1} = −1, then by (6) we have z_{2} = 1, z_{3} = 0, z_{4} = 1, z_{5} = 0. Hence it has purely periodic tail \overline{10}, which means that a purely periodic carry sequence cannot start with (−1)(−1). By checking all the possibilities of z_{0} and z_{1}, one can show that the purely periodic carry sequences are \overline{0}, \overline{10}, \overline{01}, \overline{2(−1)}, \overline{(−1)2}. Hence P is determined.

vi-2) 2 ≤ b ≤ a − 2. In this case z_{max} = 1 and hence z_{i} ∈ {0, 1}. Calculations show that the purely periodic carry sequences are \overline{0}, \overline{01}, \overline{10}.

vi-3) b = 1. In this case z_{max} ≤ 1 and z_{i} ∈ {0, 1}. The purely periodic carry sequences are \overline{0}, \overline{10}, \overline{10}, \overline{1}.

vii) c = −1, −a + 3 ≤ b ≤ 0.

In this case r_{1} < 0, r_{2} < 0 and |r_{1}| + |r_{2}| < 1.

If (z_{i}) is a purely periodic carry sequence with z_{max} = 1, then it is easy to check that (z_{i}) = \overline{1}.

Assume that z_{max} ≥ 2. We claim that z_{i} = z_{max} implies z_{i−1} = z_{max}. Otherwise, setting z_{i} = z_{max} in r_{2}z_{i−2} + r_{1}z_{i−1} + z_{i} < 1, we get

z_{max}r_{2} + (z_{max} − 1)r_{1} + z_{max} < 1,

which implies z_{max} < \frac{1+r_{1}}{1+r_{1}+r_{2}} < 2 when a ≥ 6. This contradicts our assumption and the claim is proved. Hence (z_{i}) is a constant sequence. This settles vii). □

4. Weak finiteness of cubic Pisot units

We wish to show Theorem 3 by using the result in the previous section. Let us give an example to illustrate the idea. Set a = 3, b = −2, c = 1. Then by Proposition 1, we have .\overline{1} = .111 … ∈ P. As d_{β}(1) = .20111 …, we have

.111 … = .111 … − .(−1)20111 … = .2(−1)1 = (2β^{−1} + β^{−3}) − β^{−2},

which shows (H). The following result is due to [2] and Bassino [7].

Lemma 3. The expansions of one for cubic Pisot units are given by the following table.

c = 1
b  d_{β}(1)
−a + 1 ≤ b ≤ −2 (a − 1)(a + b − 1)\overline{(a + b)}
b = −1  (a − 1)(a − 1) 0 1
0 ≤ b ≤ a  a b 1
b = a + 1  (a + 1) 0 0 a 1
c = −1
b  d_{β}(1)
−a + 3 ≤ b ≤ 0 (a − 1)(a + b − 1)\overline{(a + b − 2)}
1 ≤ b ≤ a − 1  a \overline{(b − 1)(a − 1)}

Proof of Theorem 3. If P = {0} then the stronger condition (F) holds and we have nothing to prove. We will prove that the property (H) holds for those β with P ≠ {0}.

i) c = 1 and −a + 1 ≤ b ≤ −2.

Let v be an integer such that \overline{(v(a + b))} belongs to P. Then v(a+b) < a − 1 as it has to be less than the expansion of one. First consider the case v = 1. Lemma 3 shows:

.\overline{(a + b)} = β^{2} − (a − 1)β − (a + b − 1) = 1 0 0. − (a − 1)(a + b − 1).

Therefore

.\overline{(a + b)} = .(a + b)(a + b)(a + b) + .0 0 0 \overline{(a + b)}
= .(a + b + 1)(a + b)(a + b) − .0 (a − 1)(a + b − 1)
= .(a + b + 1)(a + b − 1) 1 − .0 (a − 2),

which gives a desired expression. We do induction on v. If v(a+b)+1 < a − 1 then by adding the expansion of one, we see

.\overline{(v(a + b))} = .(v(a+b)+1)(v(a+b))((v−1)(a+b)+1) \overline{((v − 1)(a + b))}−.0 (a−1)

thus the problem is reduced to \overline{((v − 1)(a + b))}. Similarly if v(a + b) + 1 = a − 1 and a + b > 1, then the same expression gives

.\overline{(v(a + b))} = .(v(a + b) + 1) 0 ((v − 1)(a + b) + 1) \overline{((v − 1)(a + b))} − .0 1

as desired. It remains to consider the case v(a + b) + 1 = a − 1 and a + b = 1 with v ≥ 2. This implies a ≥ 4. In this case, d_{β}(1) = .(a − 1) 0 \overline{1}. Adding two expansions of one after shifting, we have

.\overline{(a − 2)} = .\overline{(a − 2)} + .1 (−a + 1) 0 \overline{(−1)} + .0 1 (−a + 1) 0 \overline{(−1)}
= .(a − 1) 0 0 (a − 3) \overline{(a − 4)} − .0 0 1.

This reduces the problem to \overline{(a − 4)} which was discussed already. We finished this case.

ii) c = −1, 1 ≤ b ≤ a − 1

In this case there are \overline{(a − 1)(b − 1)} and \overline{(b − 1)(a − 1)} in P. Thus

\overline{(b − 1)(a − 1)} = .(b − 1)(a − 1)\overline{(b − 1)(a − 1)}
= bβ^{−1} − β^{−2} = .b − .0 1

and

\overline{(a − 1)(b − 1)} = .(a − 1) \overline{(b − 1)(a − 1)}
= .(a − 1) b − .0 0 1

hold and we have done. When b = 1 and b = a − 1 there are some other elements in P, which will be treated in iii) and iv).

iii) c = −1 and b = 1

In this case, we additionally have \overline{(a − 1)} ∈ P. Using ii), we have

\overline{0 (a − 1)} = .1 − .0 1 and \overline{(a − 1) 0} = .(a − 1) 1 − .0 0 1.

So \overline{(a − 1)} = .a 1 − .0 1 1 = .a − .0 0 1

iv) c = −1 and b = a − 1

Adding three expansions of one after shifting, we have the formal expression

0 = .(−1) a \overline{(a − 2)(a − 1)} − .0 (−1) a \overline{(a − 2) (a − 1)}
+.0 0 (−1) a \overline{(a − 2) (a − 1)}
= .(−1) (a + 1) (−3) (a + 1) \overline{(a − 3) a}.

Thus

.\overline{(a − 3) a} = .(a − 3) a (a − 3) a \overline{(a − 3) a}
= .(a − 2) (−1) a (−1) = .(a − 2) 0 a − .0 1 0 1

and

.\overline{a (a − 3)} = .a (a − 2) 0 a − .0 0 1 0 1

give the required expressions.

v) c = −1 and −a + 3 ≤ b ≤ 0

Set κ = a + b − 2. Let v be an integer that \overline{(vκ)} is admissible. Using the expansion of one, we see

.\overline{κ} = .κ κ κ \overline{κ} = .(a + b − 1) − .0 (1 − b) 1,

which shows the case v = 1. We proceed in the same manner as in i). As \overline{(vκ)} is admissible, we have vκ < a − 1. By using

.\overline{(vκ)}
= .\overline{(vκ)} − .(−1) (a − 1) (a + b − 1) \overline{κ}
= .(vκ + 1) 0 ((v − 1)κ − 1) \overline{((v − 1)κ)} − .0 (a − 1 − vκ),

we can reduce the case to \overline{((v − 1)κ)} and have confirmed all cases. □

5. Dominant condition

We shall proof Theorem 4 in this section. The essential idea is to use the sum of digits as in [14].

Let

χ(x) = x^{d} − b_{1}x^{d−1} − b_{2}x^{d−2} − ⋯ − b_{d}

and set b_{j} = 0 for all j > d. Let β be the dominant root of χ(x), and let d_{β}(1) = a_{1}a_{2} … when β > 1. We need the following lemma for the proof of Theorem 4.

Lemma 4. Let β > 1 be the dominant root of χ(x) with b_{1} > ∑_{j=2}^{d} |b_{j}|. If, for some ℓ > 0, a_{j} = b_{1} + b_{2} + ⋯ + b_{j} − 1 for all j < ℓ, then a_{ℓ} ∈ {b_{1} + b_{2} + ⋯ + b_{ℓ} − 1, b_{1} + b_{2} + ⋯ + b_{ℓ}}.

Proof. i) For ℓ = 1, we have to show a_{1} = ⌊β⌋ ∈ {b_{1} −1, b_{1}}. This holds because we have χ(b_{1}−1) < 0 and χ(b_{1}+1) > 0, hence β ∈ (b_{1} − 1, b_{1} + 1).

ii) For 1 < ℓ ≤ d, consider the following addition, where all lines are zero:

(−1) b_{1} … b_{ℓ−1} .  b_{ℓ}  …  b_{d}
... ... ... .  ...  ...  ...  ...
(−1) b_{1} .  b_{2}  …  b_{d−ℓ} … b_{d}
(−1).  b_{1}  … b_{d−ℓ−1} . . . . . . b_{d}
(−1)a_{1} … a_{ℓ−1} .(b_{1} + ⋯ + b_{ℓ}) … (b_{d−ℓ−1} + ⋯ + b_{d}) … b_{d}

Hence

a_{ℓ} = ⌊(b_{1} + ⋯ + b_{ℓ}).(b_{2} + ⋯ + b_{ℓ+1}) … (b_{d−ℓ−1} + ⋯ + b_{d}) … b_{d}⌋.

By the dominant condition b_{1} > ∑_{j=2}^{d} |b_{j}|, we have (10) |b_{2} +⋯+b_{ℓ+1}| ≤ b_{1} −1, …, |b_{d−ℓ−1} +⋯+b_{d}| ≤ b_{1} −1, …, |b_{d}| ≤ b_{1} −1.

If one of these inequalities is an equality, then ∑_{j=2}^{d} |b_{j}| = b_{1} − 1 and all b_{j} must have the same sign. If all b_{j} are positive, then β > b_{1}, which contradicts the assumption a_{1} = b_{1} − 1. So all b_{j} are negative and − ∑_{j=2}^{d} b_{j} = b_{1} − 1. Hence we can factorize χ(x) as

χ(x) = (x−1)(x^{d−1}−(b_{1}−1)x^{d−1}−(b_{1}+b_{2}−1)x^{d−2}−⋯−(b_{1}+⋯+b_{d−1}−1)).

Clearly b_{1} − 1 ≥ b_{1} + b_{2} − 1 ≥ ⋯ ≥ b_{1} + ⋯ + b_{d−1} − 1 > 0 and hence d_{β}(1) = (b_{1} − 1)(b_{1} + b_{2} − 1) … (b_{1} + ⋯ + b_{d−1} − 1). The lemma is proved in this case.

If all the inequalities in (10) are strict, then

|.(b_{2} + ⋯ + b_{ℓ+1}) … b_{d}| ≤ \frac{b_{1} − 2}{β} + ⋯ + \frac{b_{1} − 2}{β^{d−1}} < \frac{b_{1} − 2}{β − 1} < 1

and a_{ℓ} ∈ {b_{1} + ⋯ + b_{ℓ} − 1, b_{1} + ⋯ + b_{ℓ}}.

iii) ℓ > d means that a_{j} = b_{1} +b_{2} +⋯+b_{j} −1 holds for all 1 ≤ j ≤ d. Then it is easy to check that

d_{β}(1) = (b_{1} − 1)(b_{1} + b_{2} − 1) … (b_{1} + ⋯ + b_{d−1} − 1)\overline{(b_{1} + ⋯ + b_{d} − 1)}

and again the lemma holds. □

Proof of Theorem 4. By Theorem 2, it suffices to show (W’). As we have shown in the proof of Lemma 4, in case −1 + b_{1} + ⋯ + b_{d} = 0 and (b_{1}, b_{2}) ≠ (2, −1), the conditions of Theorem A are satisfied and β has the property (F). We have to exclude (b_{1}, b_{2}) = (2, −1) because this means χ(x) = x^{2} − 2x + 1 and β = 1. So in the following we assume −1 + b_{1} + ⋯ + b_{d} > 0.

Consider x ∈ ℤ[1/β] ∩ [0, 1). This means that x has a representation x = .x_{1}x_{2} … x_{J} where x_{i} may be negative. Set x_{k}^{+} = max(x_{k}, 0), x_{k}^{−} = max(−x_{k}, 0). Then

x = .x_{1}^{+}x_{2}^{+} … x_{J}^{+} − .x_{1}^{−}x_{2}^{−} … x_{J}^{−}.

We extend the notion of admissibility to integer sequences y_{1}y_{2} … with possibly negative entries by calling y_{1}y_{2} … admissible if and only if y_{1}^{+}y_{2}^{+} … and y_{1}^{−}y_{2}^{−} … are admissible.

If x_{1}x_{2} … x_{J} is admissible, then we are done. If x_{1}x_{2} … x_{J} is not admissible, we define an algorithm which changes it to a new representation x = x′_{0}.x′_{1}x′_{2} … x′_{J′}. The idea is to decrease ∑_{j=0}^{∞} |x_{j}| by adding or subtracting digitwisely .0^{k−1}1(−b_{1}) … (−b_{d}) for some k ≥ 0. Then, we show that after a finite number of iterations, we obtain an admissible (finite) representation of x.

Algorithm. Assume, w.l.o.g, that k is the smallest integer such that

x_{k+1}^{+}x_{k+2}^{+} … ≥ a_{1}a_{2} ….

If x_{k+1} ≥ b_{1}, which is always the case if a_{1} = b_{1}, we digitwisely add .0^{k−1}1(−b_{1}) … (−b_{d}) to .x_{1}x_{2} … x_{J} and we obtain a new representation of x in the form

x′_{0}.x′_{1}x′_{2} … = 0.x_{1} … x_{k−1}(x_{k} + 1)(x_{k+1} − b_{1}) … (x_{k+d} − b_{d})x_{k+d+1} ….

(For k = 0, read x′_{0}.x′_{1}x′_{2} … = 1.(x_{1} − b_{1}) … (x_{d} − b_{d})x_{d+1} …). By the dominant condition, we have

∑_{j≥0}^{∞} |x′_{j}| − ∑_{j≥0}^{∞} |x_{j}| ≤ 1 − b_{1} + ∑_{j=2}^{d} |b_{j}| ≤ 0.

The construction is finished. We remark that the left side of the above formula is strictly less than 0 in case x_{k} < 0.

If x_{k+1} = b_{1} − 1, then necessarily a_{1} = b_{1} − 1 and x_{k+2}^{+}x_{k+3}^{+} … ≥ a_{2}a_{3} . . .. Moreover, Lemma 4 gives a_{2} ∈ {b_{1} + b_{2} − 1, b_{1} + b_{2}}.

If x_{k+2} ≥ b_{1} +b_{2}, which is always the case if a_{2} = b_{1} +b_{2}, then we add .0^{k−1}1(−b_{1}) … (−b_{d}) and .0^{k}1(−b_{1}) … (−b_{d}) to x_{1}x_{2} … x_{J} and obtain

x′_{0}.x′_{1}x′_{2} … = 0.x_{1} … x_{k−1}(x_{k} + 1)(x_{k+1} + 1 − b_{1})(x_{k+2} − b_{1} − b_{2}) (x_{k+3} − b_{2} − b_{3}) … (x_{k+d} − b_{d−1} − b_{d})(x_{k+d+1} − b_{d})x_{k+d+2} …

and hence

∑_{j=0}^{∞} |x′_{j}| − ∑_{j=0}^{∞} |x_{j}| ≤ 1 + 1 − b_{1} − b_{1} − b_{2} + ∑_{j=2}^{d} |b_{j}| + ∑_{j=3}^{d} |b_{j}| ≤ 0.

In general, we look for the positive integer ℓ such that x_{k+j} = b_{1} + ⋯ + b_{j} − 1 for all j < ℓ and x_{k+ℓ} ≥ b_{1} + ⋯ + b_{ℓ}. We claim that such an ℓ always exists under the assumption −1 + b_{1} + ⋯ + b_{d} > 0. Otherwise, x_{k+1}^{+}x_{k+2}^{+} ⋯ ≥ a_{1}a_{2} … and Lemma 4 imply recursively x_{k+j} = a_{j} = b_{1} + ⋯ + b_{j} − 1 > 0 for all j ≥ 1, but this contradicts that x_{1}x_{2} … x_{J} is finite and the claim is proved.

Now, add .0^{k−2+j}1(−b_{1}) … (−b_{d}) to x_{1}x_{2} … x_{J} for 1 ≤ j ≤ ℓ. We obtain x = x′_{0}.x′_{1}x′_{2} … of the form

0.x_{1} … x_{k−1}(x_{k} + 1)(x_{k+1} + 1 − b_{1}) … (x_{k+ℓ−1} + 1 − b_{1} − ⋯ − b_{k+ℓ−1}) (x_{k+ℓ} − b_{1} − ⋯ − b_{ℓ})(x_{k+ℓ+1} − b_{2} − ⋯ − b_{ℓ+1}) …

and

∑_{j=0}^{∞} |x′_{j}| − ∑_{j=0}^{∞} |x_{j}| ≤

1 + (1 − b_{1}) + ⋯ + (1 − b_{1} − ⋯ − b_{ℓ−1}) − (b_{1} + ⋯ + b_{ℓ}) + ∑_{i=2}^{ℓ} ∑_{j=i}^{ℓ} |b_{j}|

≤ ℓ − ℓb_{1} + ℓ ∑_{j=2}^{d} |b_{j}| ≤ 0.

The construction is finished.

Hence we always obtain a new representation of x with ∑_{j=0}^{∞} |x′_{j}| ≤ ∑_{j=0}^{∞} |x_{j}|. If x_{k+1}^{−}x_{k+2}^{−} … ≥ a_{1}a_{2} …, a similar argument works by adding .0^{k−1}(−1)b_{1} … b_{d} to .x_{1}x_{2} . . .. Furthermore, ∑_{j=0}^{∞} |x′_{j}| = ∑_{j=0}^{∞} |x_{j}| is possible only for x_{k} ≥ 0 if x_{k+1}^{+}x_{k+2}^{+} … ≥ a_{1}a_{2} … (and x_{k} ≤ 0 if x_{k+1}^{−}x_{k+2}^{−} … ≥ a_{1}a_{2} …).

Starting with x_{0}^{(0)}.x_{1}^{(0)}x_{2}^{(0)} … = 0.x_{1}x_{2} …, construct iteratively x_{0}^{(i+1)}.x_{1}^{(i+1)} … from x_{0}^{(i)}.x_{1}^{(i)} … as above by using the minimal k ≥ 0 such that x_{k+1}^{(i) +}x_{k+2}^{(i) +} … ≥ a_{1}a_{2} … or x_{k+1}^{(i) −}x_{k+2}^{(i) −} … ≥ a_{1}a_{2} … and denote this k by k_{i}. We have

∑_{j=0}^{∞} |x_{j}^{(1)}| ≥ ∑_{j=0}^{∞} |x_{j}^{(2)}| ≥ ∑_{j=0}^{∞} |x_{j}^{(3)}| ≥ …

Our algorithm terminates once we get an admissible sequence x_{1}^{(i)}x_{2}^{(i)} . . .. The admissibility implies |.x_{1}^{(i)}x_{2}^{(i)} … | < 1 and x_{0}^{(i)} ∈ {0, 1} because of x ∈ [0, 1). Hence x_{0}^{(i)}x_{1}^{(i)}x_{2}^{(i)} … is admissible if β > 2. The only possibility for β < 2 is b_{1} … b_{d} = 20^{d−2}(−1), but this is excluded by the assumption −1+b_{1}+⋯+b_{d} > 0. Therefore x_{0}^{(i)}x_{1}^{(i)}x_{2}^{(i)} … is admissible and we have a representation x = y − z with y, z ∈ Fin(β), y < β and z < 1.

Suppose that the algorithm does not terminate in finitely many steps. Then ∑_{j=0}^{∞} |x_{j}| becomes a constant after some iterations. We take this sequence as the starting seqence and show that the {x_{0}^{(i)}.x_{1}^{(i)}x_{2}^{(i)} …} converges to an infinite sequence.

Let L = min_{i≥0} k_{i} and h be the smallest number such that k_{h} = L.

Assume, w.l.o.g., (x_{L+1}^{(h)})^{+} (x_{L+2}^{(h)})^{+} … ≥ a_{1}a_{2} . . ..

First we argue that x_{L}^{(h)} ≥ 0, for otherwise ∑_{j≥0} |x_{j}^{(h+1)}| < ∑_{j≥0} |x_{j}^{(h)}|. Second, the next time we come back to L, we cannot come back with a different sign. For if h′ is the next time of coming back with

(x_{L+1}^{(h′)})^{−} (x_{L+2}^{(h′)})^{−} …

non-admissible, then x_{L}^{(h′)} > 0 and thus ∑_{j=0}^{∞} |x_{j}^{(h+1)}| < ∑_{j=0}^{∞} |x_{j}^{(h)}|. Hence we can return to L at most ⌊β⌋ times.

By repeating the above argument, we have proved that x_{0}^{(i)}.x_{1}^{(i)}x_{2}^{(i)} … converges to an infinite sequence, which contradicts that ∑_{j=0}^{∞} |x_{j}| is a constant. Therefore our algorithm terminates and gives us an admissible representation of x. □

6. Branching beta expansion

There is another way to access this weak finiteness problem. The result in this section gives a practical way to show the property (F) or (W) for a fixed β. Before introducing the branching algorithm, we begin with an easier case, the property (F). Denote by T_{+} = T_{β} and define T_{−}(x) = T_{β}(x) − 1 = βx − ⌊βx + 1⌋. Of course T_{−}(x) ∈ [−1, 0).

We say that an element x ∈ ℤ[β] is β-finite if there is a positive integer ℓ that T_{β}^{ℓ}(x) = 0. This means that x can be expanded in the form:

x = ∑_{i=1}^{ℓ} x_{i}β^{−i} = .x_{1}x_{2} … x_{ℓ},

with x_{i} = ⌊βT_{β}^{i−1}(x)⌋. Note that the first digit x_{1} = ⌊βx⌋ is an integer without restriction but the remaining expansion .0 x_{2}x_{3} … is the beta expansion of x − x_{1}/β.

Proposition 2. Assume that there exists a subset E of ℤ[β] which satisfies

• 0 ∈ E

• T_{+}(E) ∪ T_{−}(E) ⊂ E.

• Each element of E is β-finite. Then β has the property (F).

Originally this type of method was introduced by Brunotte [11] and Scheicher-Thuswaldner [22] independently for canonical number systems. The next proof is an analogy to Lemma 4.1 in [4].

Proof. Assume that ξ is β-finite and η ∈ E. We wish to show that ξ +η is β-finite. Note that

T_{β}(ξ + η) − T_{β}(ξ) ≡ T_{β}(η) (mod ℤ).

Thus if T_{β}(ξ + η) − T_{β}(ξ) ∈ [0, 1) then we have

T_{β}(ξ + η) = T_{β}(ξ) + T_{+}(η)

and if T_{β}(ξ + η) − T_{β}(ξ) ∈ [−1, 0) then

T_{β}(ξ + η) = T_{β}(ξ) + T_{−}(η).

Thus we have shown that there exists an η′ ∈ E such that

T_{β}(ξ + η) = T_{β}(ξ) + η′.

Repeating this argument, we see that there exists an ℓ such that

T_{β}^{ℓ}(ξ + η) = T_{β}^{ℓ}(ξ) + η′′ = η′′

with η′′ ∈ E. Using the assumption of the proposition, we have shown that ξ + η is β-finite.

Since T_{−}(0) = −1, it is easy to see that T_{−}^{i}(0) (i = 1, 2, …, d) forms a basis of ℤ[β] as ℤ-module, where d is the degree of β. Hence E contains a basis of ℤ[β]. Using the additivity, each element of ℤ[β] is β-finite. Let x be an element of ℤ[1/β] and take a positive integer N that β^{N}x ∈ ℤ[β]. Then T_{β}^{N}(x) ∈ ℤ[β] ∩ [0, 1). This shows that x is β-finite. Reviewing the definition of the beta expansion, this also proves that each element x ∈ ℤ[β]_{≥0} has finite beta expansion. □

Assume that β > 1 is the dominant root of the polynomial x^{d} − b_{1}x^{d−1} − b_{2}x^{d−2} − ⋯ − b_{d}. Let r_{i} = .b_{i+1}b_{i+2} … b_{d} = ∑_{k=1}^{d−i} b_{i+k}β^{−k} for i = 0, 1, … d − 1. Assume that ∑_{i=1}^{d−1} |r_{i}| < 1. Then we show that the set

E = {∑_{i=0}^{d−1} z_{d−i}r_{i} | z_{i} ∈ {−1, 0, 1}}

satisfies first the first two conditions of Proposition 2. The first condition is clear. Using the carry sequence explained in §3, we have

T_{±} (∑_{i=0}^{d−1} z_{d−1−i}r_{i}) = ∑_{i=0}^{d−1} z_{d−i}r_{i}

and z_{d} has two choices to satisfy

(11)  −1 ≤ z_{1}r_{d−1} + z_{2}r_{d−2} + ⋯ + z_{d}r_{0} < 1.

Thus to show the 2nd condition of Lemma 2, it suffices to show that if z_{i} ∈ {−1, 0, 1} for i = 1, … d − 1 then z_{d} ∈ {−1, 0, 1}. But this is clear from the condition ∑_{i=1}^{d−1} |r_{i}| < 1. Now we give an alternative proof of the results in [15].

The following corollary can be found implicity in [15].

Corollary 1. If r_{1}, r_{2}, … r_{d−1} > 0 and ∑_{i=1}^{d−1} r_{i} < 1 then β has the property (F).

Proof. We only need to show that each element x of E has finite beta expansion. Recalling (5), z_{i+d−1} is determined from z_{i}, z_{i+1}, … z_{i+d−2} by T_{β}. Suppose that x does not have finite beta expansion. Then we may assume x ∈ P. Using periodicity, the associated carry sequence (z_{i}) cannot take the value −1 since z_{i+d−1} = −1 causes a contradiction in (5). Thus z_{i} must be 0 or 1. This implies z_{i+d−1} = z_{i+d} = ⋯ = 0 and thus the carry sequence falls into the 0 cycle. This is absurd. □

From this, Theorem B is easily shown, since r_{1} + ⋯ + r_{d−1} equals

(b_{2} + b_{3} + ⋯ + b_{d})β^{−1} + (b_{3} + b_{4} + ⋯ + b_{d})β^{−2} + ⋯ + b_{d}β^{−d+1},

which is easily seen to be less than 1.

Now, let us introduce the ‘branching’ beta expansion. Assume that x can be transformed by one of two maps T_{±}:

x = ξ_{1} ⟶^{x_{1}} ξ_{2} ⟶^{x_{2}} ξ_{3} ⟶^{x_{3}} …

where x_{i} = βξ_{i} − T_{m_{i}}(ξ_{i}) and m_{i} ∈ {+, −}. Then we can expand x by

(12)  x = ∑_{i=1}^{∞} x_{i}β^{−i} = .x_{1}x_{2} …

Take an integer q < β. We say that x is q-expansible if |T_{m_{k}}(ξ_{k})| < q/β for all k, and x is q-finite if additionally T_{m_{ℓ}}(ξ_{ℓ}) = 0 for some ℓ. If x is q-expansible, then x is expanded in a form (12) with |x_{i}| ≤ q for i ≥ 2. Note that x_{1} may be large. The largest digit |x_{i}| = q (i ≥ 2) appears only when we change the ‘branching direction’, i.e., the signs m_{i−1} and m_{i} are different.

Conversely, if we have an expression (12) of x with |x_{i}| ≤ q − 1 for i ≥ 2 then one will see that x is q-expansible. In fact, taking m_{i} appropriately, we have

T_{m_{k}}(ξ_{k}) = ∑_{i=k+1}^{∞} x_{i}β^{k−i}

with

|T_{m_{k}}(ξ_{k}) |≤ \frac{q − 1}{β − 1} < \frac{q}{β} ,

where we used the assumption q < β.

If q > β/2, then each x ∈ ℝ is q-expansible. This fact is seen by the central beta transformation:

U_{β}(x) = βx − ⌊βx + \frac{1}{2}⌋

which acts on [−1/2, 1/2) ⊂ (−q/β, q/β). This gives digits x_{i} ∈ (−(β+ 1)/2, (β + 1)/2) ∩ ℤ for i ≥ 2. This is a deterministic algorithm and U_{β} coincides with T_{+} or T_{−} depending on the applied value. In general, the above branching expansion is indeterministic and we have one or two choices of digits.

Proposition 3. Assume that there exists a subset E of ℤ[β] which satisfies

• 0 ∈ E

• T_{+}(E) ∪ T_{−}(E) ⊂ E

• There exists β/2 < q < β that each x ∈ E is q-finite. Then each element of ℤ[1/β] is q-finite. If q < ⌊β⌋ then β satisfies the property (W). The last inequality can be replaced by q ≤ ⌊β⌋ when a_{2} = ⌊βT_{β}(1)⌋ > 0.

Proof. Assume that ξ is q-finite and η ∈ E. We aim for showing that ξ + η is q-finite. By the assumption,

ξ = ξ_{1} ⟶^{x_{1}} ξ_{2} ⟶^{x_{2}} ξ_{3} ⟶^{x_{3}} ⋯ ⟶^{x_{ℓ−1}} ξ_{ℓ} ⟶^{x_{ℓ}} 0

where x_{i} = βξ_{i} − T_{m_{i}}(ξ_{i}) and m_{i} ∈ {+, −} and |T_{m_{k}}(ξ_{k})| < q/β for all k. We claim that there exists an η′ ∈ E and k_{1} ∈ {+, −} such that

T_{k_{1}}(ξ + η) = T_{m_{1}}(ξ) + η′ with |T_{k_{1}}(ξ + η) |< \frac{q}{β} .

Note that

T_{m_{1}}(ξ + η) − T_{m_{1}}(ξ) = T_{+}(ξ + η) − T_{+}(ξ) ≡ T_{+}(η) (mod ℤ).

Thus if T_{+}(ξ + η) − T_{+}(ξ) ∈ [0, 1) then we have

T_{m_{1}}(ξ + η) = T_{m_{1}}(ξ) + T_{+}(η)

and if T_{+}(ξ + η) − T_{+}(ξ) ∈ [−1, 0) then

T_{m_{1}}(ξ + η) = T_{m_{1}}(ξ) + T_{−}(η).

Thus if |T_{m_{1}}(ξ + η)| < q/β, then we take k_{1} = m_{1} and η′ = T_{±}(η) ∈ E. Assume that T_{m_{1}}(ξ + η) ∈ [−1, −q/β]. Then we see m_{1} = ‘−’. As |T_{m_{1}}(ξ)| < q/β, the value T_{±}(η) must be negative. So we have

T_{−}(ξ + η) = T_{−}(ξ) + T_{−}(η)

and thus

T_{+}(ξ + η) = T_{−}(ξ) + T_{+}(η)

and T_{+}(ξ + η) ∈ [0, 1 − q/β] ⊂ (−q/β, q/β). This shows that we can take k_{1} = ‘+’ and η′ = T_{+}(η). The case T_{m_{1}}(ξ + η) ∈ [q/β, 1) is done the same way and we have shown the claim.

Repeating this argument, we see that there exist k_{i} (i = 1, …, ℓ) such that

T_{k_{ℓ}}T_{k_{ℓ−1}} … T_{k_{2}}T_{k_{1}}(ξ + η) = T_{m_{ℓ}}T_{m_{ℓ−1}} … T_{m_{2}}T_{m_{1}}(ξ) + η′′ = η′′

with η′′ ∈ E and |T_{k_{i}}T_{k_{i−1}} … T_{k_{1}}(ξ + η)| < q/β for each i. Using the assumption of the proposition, we have shown that ξ + η is q-finite.

As in the proof of the previous proposition, E contains a basis of ℤ[β] and therefore each element of ℤ[β] is q-finite. Let x be an element of ℤ[1/β] and take a positive integer N such that β^{N}x ∈ ℤ[β]. Iterating the central beta expansion we have U_{β}^{N}(x) ∈ ℤ[β] ∩ [−1/2, 1/2) which is q-finite. This shows that x is q-finite.

Suppose q < ⌊β⌋. As each element x of ℤ[1/β] ∩ [−1/2, 1/2) is qfinite, we have x = x_{1} … x_{ℓ} = x_{1}^{+} … x_{ℓ}^{+} − x_{1}^{−} … x_{ℓ}^{−} with |x_{i}| ≤ q ≤ ⌊β⌋ − 1. Note that x_{1}^{+} … x_{ℓ}^{+} and x_{1}^{−} … x_{ℓ}^{−} are admissible since we do not use the digit ⌊β⌋. Take an element x ∈ ℤ[1/β] ∩ [0, 1). Then x or 1 − x is contained in [−1/2, 1/2). In the latter case, the relation 1 − x = .x_{1}^{+} … x_{ℓ}^{+} − .x_{1}^{−} … x_{ℓ}^{−}, shows x = 1.x_{1}^{−} … x_{ℓ}^{−} − .x_{1}^{+} … x_{ℓ}^{+}. This shows that β has the property (W) by Proposition 2. If a_{2} > 0, then one can take q = ⌊β⌋ in the above proof since x_{i}^{m} = ⌊β⌋ implies x_{i+1}^{m} = 0 where m ∈ {+, −}. Indeed the crucial digit ⌊β⌋ appears only when we change the sign m_{i} in the branching beta expansion (12). □

Propositions 2 and 3 give us an efficient way to show the properties (F) or (W) for a fixed β. Namely

(a): Let E_{1} = {0}.

(b): Define inductively E_{n} = E_{n−1} ∪ T_{+}(E_{n−1}) ∪ T_{−}(E_{n−1}).

(c): If E_{n} = E_{n−1} then go to (d) otherwise go to (b).

(d): For each element x of E_{n}, confirm that x is β-finite. If it is

true, then β has the property (F). (e): If there exists x ∈ E_{n} which is not β-finite, i.e., x gives an eventually periodic expansion, then we start over again and try to show that all elements of E_{n} are q-finite.

The emerging process (b) will terminate in a finite number of steps when β is a Pisot number. This is easily proved since E_{n} ⊂ ℤ[β] and by each Galois conjugate map, the image of E_{n} is bounded. Thus this gives an efficient algorithm to confirm that the property (F) holds or not. The process (e) is executed in the following way. Let G be a directed graph of vertices E_{n} and draw edges a → b between a, b ∈ E_{n} when T_{±}(a) = b and |b| < q/β. If we can walk along this G from each vertex to 0, then all elements of E_{n} are q-finite. However at this moment, this is not an established algorithm for (W). It is not known that each x in E_{n} must be q-finite even if β > 2 satisfies (W). By using Proposition 3, we can also give a sufficient condition of (W).

Corollary 2. Let

q = \begin{cases}⌊β⌋ & if a_{2} > 0 \\ ⌊β⌋ − 1 & if a_{2} = 0 \end{cases} .

If ∑_{i=1}^{d−1} |r_{i}| < q/β then β has the property (W).

Proof. As ∑_{i=1}^{d−1} |r_{i}| < q/β < 1, the set E = { ∑_{i=0}^{d−1} z_{d−i}r_{i} | z_{i} ∈ {−1, 0, 1}} satisfies the first two conditions of Proposition 3. It remains to show that each element of E is q-finite. As | ∑_{i=1}^{d−1} z_{d−i}r_{i}| ≤ ∑_{i=1}^{d−1} |r_{i}| < q/β, one can take z_{d} = 0 in the branching beta expansion keeping the qexpansible property. Continuing the same argument, we are able to take z_{d} = z_{d+1} = ⋯ = 0 and thus each element of E is q-finite. □

This assertion is close to Theorem 4. In fact, ∑_{i=1}^{d−1} |r_{i}| < (b_{1} − 1)/β implies the dominant condition b_{1} > ∑_{i=2}^{d} |b_{i}| and conversely b_{1} > 1 + ∑_{i=2}^{d} |b_{i}| implies ∑_{i=1}^{d−1} |r_{i}| < (b_{1} − 1)/β. However Corollary 2 occasionally exceeds Theorem 4. For example, the dominant root of x^{3} − 3x^{2} − 2x + 1 satisfies the inequality ∑_{i=1}^{d−1} |r_{i}| < q/β with q = 3 but does not satisfy the dominant condition.

References

[1] S. Akiyama, Self affine tiling and Pisot numeration system, ‘Number Theory and its Applications’, ed. by K. Györy and S. Kanemitsu, 7–17 Kluwer 1999.

[2] S. Akiyama, Cubic Pisot units with finite beta expansions, ‘Algebraic Number Theory and Diophantine Analysis’, ed. F.Halter-Koch and R.F.Tichy, 11–26, de Gruyter 2000.

[3] S. Akiyama, On the boundary of self affine tilings generated by Pisot numbers, J. Math. Soc. Japan, vol. 54, no. 2 (2002) 283-308.

[4] S. Akiyama and H. Rao, New criteria for canonical number systems, to appear in Acta Arithmetica.

[5] S. Akiyama and T. Sadahiro, A self-similar tiling generated by the minimal Pisot number, Acta Math. Info. Univ. Ostraviensis 6 (1998) 9–26.

[6] P. Arnoux and Sh. Ito, Pisot substitutions and Rauzy fractals, Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000), Bull. Belg. Math. Soc. Simon Stevin 8 (2001), no. 2, 181–207.

[7] F. Bassino, Beta-expansions for cubic Pisot numbers, in LATIN’02, volume 2286 in LNCS, p. 141-152, Springer 2002.

[8] M.J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse and J.P. Schreiber, Pisot and Salem numbers, Birkhäuser Verlag, Basel-Boston-Berlin 1992.

[9] A. Bertrand, Dévelopment en base de Pisot et répartition modulo 1, C.R.Acad.Sc., Paris 385 (1977) 419–421.

[10] F. Blanchard, β-expansion and symbolic dynamics, Theor. Comp. Sci. 65 (1989) 131–141.

[11] H. Brunotte, On trinomial basis of Radix Representations of Algebraic Integers, Acta Sci. Math. (Szeged) 67 (2001) 407–413.

[12] H. Ei, Sh. Ito and H. Rao, Atomic surfaces, tilings and coincidence III: βtilings, Preprint 2003.

[13] H. Ei, Sh. Ito and H. Rao, Purely periodic β-expansion with Pisot unit base, Preprint 2003.

[14] C. Frougny and B. Solomyak, Finite beta-expansions, Ergod. Th. and Dynam. Sys. 12 (1992) 713–723.

[15] M. Hollander, Linear Numeration systems, Finite Beta Expansions, and Discrete Spectrum of Substitution Dynamical Systems, Ph.D. thesis, University of Washington, 1996.

[16] Sh. Ito and H. Rao, Atomic surfaces, tilings and coincidence I: Irreducible case, Preprint 2002.

[17] Sh. Ito and Y. Takahashi, Markov subshifts and realization of β-expansions, J. Math. Soc. Japan 26 (1974) no. 1, 33–55.

[18] W. Parry, On the β-expansions of real numbers, Acta Math. Hungar. 11 (1960) 269–278.

[19] B. Praggastis, Markov partition for hyperbolic toral automorphism, Ph.D. thesis, University of Washington, 1992.

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

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

[22] K. Scheicher and J.M. Thuswaldner, On the characterization of Canonical number system, to appear in Osaka J. Math.

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

[24] N. Sidorov, Bijective and general arithmetic codings for Pisot toral automorphisms, J. Dynam. Control Systems 7 (2001), no. 4, 447–472.

[25] N. Sidorov, Ergodic-theoretic properties of certain Bernoulli convolutions, to appear in Acta Math. Hungar.

[26] W. Steiner, Parry expansions of polynomial sequences, Integers 2 (2002), A14.

[27] W.P. Thurston, Groups, Tilings and Finite state automata, AMS Colloquium lectures, 1989.

(Shigeki Akiyama) Department of Mathematics, Faculty of Science, Niigata University, Ikarashi-2, 8050, Niigata 950-2181, Japan

E-mail address: akiyama@math.sc.niigata-u.ac.jp

(Hui Rao) Department of Mathematics, Faculty of Science, Wuhan University, 430072, Wuhan, P.R. China

E-mail address: myhacone@yahoo.com

(Wolfgang Steiner) Institut für Geometrie, TU Wien, Wiedner Hauptstrase 8-10/113, 1040 Wien, Austria

E-mail address: steiner@geometrie.tuwien.ac.at