Julien Bernat
email: bernat@iml.univ-mrs.fr

Arithmetics in β-numeration

Keywords: β-numeration, β-integers, arithmetic automaton, quasicrystals

The β-numeration, born with the works of Rényi and Parry, provides a generalization of the notions of integers, decimal numbers and rational numbers by expanding real numbers in base β, where β > 1 is not an integer. One of the main differences with the case of numeration in integral base is that the sets which play the role of integers, decimal numbers and rational numbers in base β are not stable under addition or multiplication. In particular, a fractional part may appear when one adds or multiplies two integers in base β. When β is a Pisot number, which corresponds to the most studied case, the lengths of the finite fractional parts that may appear when one adds or multiplies two integers in base β are bounded by constants which only depend on β.

We prove that, for any Perron number β, the set of finite or ultimately periodic fractional parts of the sum, or the product, of two integers in base β is finite. Additionally, we prove that it is possible to compute this set for the case of addition when β is a Parry number. As a consequence, we deduce that, when β is a Perron number, there exist bounds, which only depend on β, for the lengths of the finite fractional parts that may appear when one adds or multiplies two integers in base β. Moreover, when β is a Parry number, the bound associated with the case of addition can be explicitly computed.

Introduction

The β-numeration, born in the late 50's with the works of Renyi [START_REF] Rényi | Representations for real numbers and their ergodic properties[END_REF] and Parry [START_REF] Parry | On the β-expansions of real numbers[END_REF], is a generalization of numeration in a non-integer base which enables a modelling of quasicrystals [START_REF] Shechtman | Metalic phase with with long-range orientational order and no translational symmetry[END_REF]. The number systems defined by the β-numeration are also closely related to canonical number systems [START_REF] Akiyama | On canonical number systems[END_REF][START_REF] Scheicher | Canonical number systems, counting automata and fractals[END_REF][START_REF] Akiyama | Generalized radix representations and dynamical systems[END_REF], number systems generated by iterated function systems [START_REF] Sirvent | Self-affine tiling via substitution dynamical systems and Rauzy fractals[END_REF] or by substitutive systems of Pisot type [START_REF] Canterini | Geometric representation of substitutions of Pisot type[END_REF]. A common feature between these fields is the property of self-similarity, which yields results in number theory [START_REF] Akiyama | A certain finiteness property of Pisot number systems[END_REF], geometry [START_REF] Ito | On Rauzy fractal[END_REF], topology [START_REF] Akiyama | A survey on topological properties of tiles related to number systems[END_REF][START_REF] Canterini | Connectedness of geometric representation of substitutions of Pisot type[END_REF], dynamical systems [START_REF] Solomyak | Substitutions, adic transformations, and beta-expansions[END_REF][START_REF] Rauzy | Nombres algébriques et substitutions[END_REF][START_REF] Rauzy | Rotations sur les groupes, nombres algébriques et substitutions[END_REF], combinatorics on words [START_REF] Fabre | Substitutions et β-systèmes de numération[END_REF] and theoretical computer science [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. We focus with this article on applications in computer arithmetics.

Let β > 1 be an algebraic integer, with β / ∈ N. In the same way as in the case of integral bases, it is possible to expand x ∈ [0, 1] as x = i∈N * u i β -i , where the sequence (u i ) i∈N * , called expansion of x in base β, takes values in the alphabet A β = {0, . . . , ⌊β⌋}. Among the expansions of x in base β, the lexicographically greatest of them is called β-expansion of x, and denoted by d β (x). This expansion can be computed by the greedy algorithm, that is, d β (x) = 0.u 1 . . . u n . . ., with for all i ∈ N * , u i = ⌊βT k-1 β (x)⌋, where T β : [0, 1] -→ [0, 1[, x -→ {βx}. The notion of β-expansion was historically introduced by Rényi in [START_REF] Rényi | Representations for real numbers and their ergodic properties[END_REF]. Parry produced in [START_REF] Parry | On the β-expansions of real numbers[END_REF] many interesting results concerning the β-numeration, creating and studying among others the dynamical system ([0, 1], T β ) associated with this numeration system. Note that d β may be extended to positive real numbers by shifting i + 1 times the β-expansion of xβ -(i+1) , where x > 1 and i ∈ N is such that

xβ -(i+1) ∈ [0, 1[. The map d β is increasing if A Z
β is endowed with 1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France the lexicographical order [START_REF] Lothaire | Algebraic Combinatorics On Words[END_REF]. Note that the definition of β-expansion may be extended to negative real numbers as well, by introducing a minus sign, that is, d β (x) = -d β (-x) for any x ∈ R * -. When d β (1) is either finite or ultimately periodic, β is said to be a Parry number. As we see in the following, Parry numbers satisfy particular arithmetic properties.

Remark 1.1 For any β > 1, a natural expansion of 1 in base β is 1. However, defining d β (1) as the sequence computed by the greedy algorithm provides useful informations on β. This is why d β (1) is not defined as 1; in particular, d β (1) has a non-empty fractional part.

Another interesting expansion of 1 in base β is the greatest sequence for the lexicographical order among those which are infinite, that is, they do not end with 0's. This expansion, denoted by d * β [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF], is an improper expansion of 1 in base β; actually, d * β (1) = d β (1) when d β (1) is not finite. At the opposite of the case of numeration in integral base, d * β (1) plays a key role in the construction and the study of the associated arithmetical language L β , defined as the set of the factors of the sequences (u i ) i∈N * ∈ A N * β which satisfy the Parry condition ( [START_REF] Parry | On the β-expansions of real numbers[END_REF]):

for all k ∈ N, (u i+k ) i∈N * < lex d * β (1). In the following, we say that (v i ) i∈N * is admissible (with respect to β) if it satisfies the Parry condition. This notion of admissibility is naturally extended to words and two-sided sequences.

Let x > 1. There exists n ∈ N such that d β (x) = u -n . . . u 0 .u 1 . . .; the numbers n i=0 u -i β i and i∈N * u i β -i are respectively called β-integer part of x, denoted by ⌊x⌋ β , and β-fractional part of x, denoted by {x} β = x -⌊x⌋ β . This allows the following generalization for the definition of integers in base β. Definition 1.2 We define the set of non-negative β-integers, denoted by Z + β , as the set of real numbers x ≥ 0 such that x = ⌊x⌋ β . We define the set of β-integers as Z β = ±Z + β . The following sets generalize the framework of numeration systems with a non-integral base. They play respectively the role of decimal numbers and rational numbers in base β. Definition 1. [START_REF] Akiyama | On the boundary of self affine tilings generated by Pisot numbers[END_REF] We denote by FinF in(β) the set of real numbers whose β-fractional part is finite, that is,

Fin(β) = {x ∈ R; d β (x) is finite}.
We denote by Per(β) the set of real numbers whose β-fractional part is ultimately periodic, that is,

Per(β) = {x ∈ R; d β (x) is ultimately periodic}. Remark 1.4 One has Fin(β) = i∈N β -i Z β = i∈Z β -i Z β .
The sets Z β and Fin(β) are not stable under usual operations like addition and multiplication. Indeed, one has Fin(β) ⊂ Z[β -1 ] and Per(β) ⊂ Q(β), and the cases of equalities define numeration systems that are well fitted for performing arithmetics. Bertrand [START_REF] Bertrand | Développement en base de Pisot et répartition modulo 1[END_REF] and Schmidt [START_REF] Schmidt | On periodic expansions of Pisot numbers and Salem numbers[END_REF] have independently proven that for any Pisot number β, one has Per(β) = Q(β).

The relation Fin

(β) = Z[β -1 ], introduced in [24]
, is known as the finiteness property, denoted by (F).

Whereas not yet fully characterized, classes of numbers satisfying the finiteness property have already been extensively studied; see for instance [START_REF] Frougny | Finite beta-expansions[END_REF][START_REF] Hollander | Linear numeration systems, finite β-expansions, and discrete spectrum of substitution dynamical systems[END_REF][START_REF] Akiyama | Generalized radix representations and dynamical systems[END_REF]. Indeed, the finiteness property provides topologic and geometric properties for the geometrical realization of the associated dynamical system known as the Rauzy fractal, defined in Section 2.2. For instance, due to Akiyama [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF], the finiteness property implies that 0 is an exclusive inner point of the Rauzy fractal T under the additional condition that β is a unit. Also, Theorem 3 of the same article provides a characterization of numbers such that T is arcwise connected.

Example 1.5 Let β be the golden ratio φ = 1+ √ 5

2 . Since φ is the positive root of X 2 -X -1, one has φ -1 + φ -2 = 1; d φ (1) = 0.11, and the set of admissible words consists of words defined on the alphabet {0, 1} which do not contain two consecutive occurences of 1.

The numeration system associated with the Fibonacci number is the most studied non-standard numeration system. Actually,

1+ √ 5 2
is the only quadratic Pisot number which belongs to ]1, 2[, hence it defines from an algebraic point of view the simplest case of numeration in a non-integer base. See for instance [START_REF] Lothaire | Algebraic Combinatorics On Words[END_REF] for a study of the main properties of this numeration system. Since 1 + 1 = 2 = φ + φ -2 , one has d φ (2) = 10.01, hence Z φ is not stable under addition.

Example 1.6 Let β be the positive root of the polynomial X 4 -2X 3 -X -1. Then d β (1) = 0.2011; since ⌊β⌋ = 2, the integers 1 and 2 belong to Z β , and one has d β (3) = 10.111(00012) ∞ . Hence the finiteness property does not hold for this numeration system.

In order to perform arithmetics on β-integers, say for instance to compute the addition of two β-integers, one must be able to renormalize expansions in base β of real numbers obtained after adding β-integers. The renormalization step is performed by transducers, see for instance [START_REF] Frougny | On-line addition in real base[END_REF]. Another method consists in applying the greedy algorithm to the real number obtained after adding or multiplying β-integers, which produces its β-expansion. However, if the β-expansion of the sum of two β-integers is neither finite nor ultimately periodic, its computation requires an infinite number of steps. The following notations, L ⊕ and L ⊙ , are introduced in [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF]. They represent the maximal possible length of the β-fractional part which may appear when one adds or multiplies two β-integers, in the case where this β-fractional part is finite. For any x ∈ Fin(β) with d β (x) = u -N . . . u 0 .u 1 . . . u N ′ , we define the β-integer length of x as l int (x) = N + 1, and the β-fractional length of x as l f rac (x) = N ′ . Definition 1.7 We define L ⊕ as min n∈N {n; ∀x, y ∈ Z β , x + y ∈ Fin(β) ⇒ l f rac (x + y) ≤ n} when this set is not empty, +∞ otherwise.

We define L ⊙ as min

n∈N {n; ∀x, y ∈ Z β , xy ∈ Fin(β) ⇒ l f rac (x + y) ≤ n} when this set is not empty, +∞ otherwise.
The computation of L ⊕ and L ⊙ gives an idea of the difficulty of performing arithmetics on Z β . Frougny and Solomyak have proven in [START_REF] Frougny | Finite beta-expansions[END_REF] that L ⊕ and L ⊙ are finite when β is a Pisot number. The computation of these values is however not so easy, especially for L ⊙ . The value of L ⊕ has been computed for quadratic Pisot numbers, in [START_REF] Burdík | Beta-integers as natural counting systems for quasicrystals[END_REF] when β is a unit and in [START_REF] Guimond | Arithmetics of beta-expansions[END_REF] for the non-unit case. However, when β is of higher degree, it is a difficult problem to compute the exact value of L ⊕ or L ⊙ , and even to compute upper and lower bounds for these two constants. Several examples are studied in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], where a method is described in order to compute upper bounds of L ⊕ and L ⊙ for Pisot numbers satisfying additional algebraic properties. Also, we perform the computation of L ⊕ for several cases of cubic Pisot numbers in [START_REF] Bernat | Computation of L ⊕ for several cases of cubic Pisot numbers[END_REF], where we use algebraic inequalities as well but we do not construct any automaton. Another class of β-numbers is studied in [START_REF] Ambrož | Addition and multiplication of β-expansions in generalised Tribonacci base[END_REF], where upper and lower bounds for L ⊕ and L ⊙ are computed.

The aim of this paper is to define an algorithmic process for the computation of L ⊕ under algebraic conditions on β. More precisely, we have the following result, where the algebraic integer β is said to be hyperbolic when any of its algebraic conjugates α satisfies |α| = 1.

Theorem 1.8 Let β be a hyperbolic Perron number. Then L ⊕ and L ⊙ are finite. Furthermore, when β is a Parry number, it is possible to compute explicitly L ⊕ .

As a consequence of Theorem 1.8 we deduce that there exist two finite sets F + and F × which satisfy:

(Z β + Z β ) ∩ Fin(β) ⊂ (Z β + F + ) and (Z β • Z β ) ∩ Fin(β) ⊂ (Z β + F × ), (1)
by taking

F + = ∪ x,y∈Z β {{x + y} β } ∩ Fin(β) and F × = ∪ x,y∈Z β {{xy} β } ∩ Fin(β).
When the finiteness condition (F) holds, the set F + can be explicitly computed.

When Z β is a Meyer set (see Section 2.1), a method which enables the computation of a minimal finite set F satisfying (Z β + Z β ) ⊂ (Z β + F ) is presented in [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF], where the problem of recognizing the language constituted by sums or differences of positive β-integers is studied as well. On the other hand, Z β is not a Meyer set when β is neither a Pisot nor a Salem number ( [START_REF] Meyer | Quasicrystals, Diophantine approximation and algebraic numbers[END_REF]).

Let us observe that there is no reason for the cardinality of the finite sets F 0 and G 0 , constructed by the automaton described in Section 2, to be minimal among the sets F and G which satisfy

(Z β -Z β ) ∩ Fin(β) ⊂ (Z β + F ) and (Z β Z β ) ∩ Fin(β) ⊂ (Z β + G).
Therefore, the study performed in this article does not solve the problem of finding minimal sets satisfying these relations, which is studied in [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF]. See also [START_REF] Meyer | Algebraic numbers and harmonic analysis[END_REF][START_REF] Gazeau | Geometric study of the set of β-integers for a Perron number and mathematical quasicrystals[END_REF] for more details. This article is structured in the following way. Section 2 gathers definitions and notation that are introduced in the framework of β-numeration. In Section 3, we consider expansions of 0 in base β taking values on a finite alphabet. We prove in Section 3.1 that, when β is a hyperbolic Perron number, one can define a geometrical interpretation of these expansions (Lemma 3.1), and that they satisfy several algebraic relations (Lemma 3.3). Actually, these geometrical representation of expansions are contained in a bounded subset of R d , where d is the degree of β. In Section 3.2, we make the connection between β-fractional parts of the sum of two β-integers, and expansions of 0 in base β that are defined on a finite alphabet. In order to characterize such expansions, we construct an automaton G inspired by the arithmetic automaton defined by Rauzy [START_REF] Rauzy | Rotations sur les groupes, nombres algébriques et substitutions[END_REF] and studied by Siegel [START_REF] Siegel | Pure discrete spectrum dynamical system and periodic tiling associated with a substitution[END_REF], whose states belong to Z d . We prove that the automaton G is finite when β is a hyperbolic Perron number (Lemma 3.5) and that the paths in G are associated with expansions of 0 in base β (Proposition 3.9). In particular, the set of paths in G contains the finite and ultimately periodic paths which correspond to the sum of two β-integers (Proposition 3.11).

In Section 4.1, we define an algorithmic process which reduces G. We obtain thereby an automaton G + β , whose edges are labelled by letters of the alphabet A β -A β -A β = {-2⌊β⌋, . . . , ⌊β⌋}. We prove in Section 4.2 that any sum x + y of two β-integers can be represented by a path in G + β , whose labels define an expansion of 0 in base β (Theorem 4.4). Then, we study the case of multiplication of two β-integers in Section 4.3 (Proposition 4.6). We deduce the finiteness of L ⊕ and L ⊙ for any Perron number in Section 4.4 (Theorem 4.8).

Finally, in Section 5, we study several questions related to the finiteness of L ⊕ . Section 5.1 deals with formal power series in β that are ultimately periodic. We prove that these formal power series are characterized by paths in G ′ β , an automaton that we obtain similarly as G + β by reverting the sense of the edges. In Section 5.2, we retrieve an algebraic construction that was initially given by Thurston [START_REF] Thurston | Groups, tilings and finite state automata[END_REF] in the framework of automata theory. In Section 5.3, we focus on the particular Tribonacci case: we explicitly construct G ′ β , which admits G + β (with reverted edges) as a subgraph.

Definitions and notation

We mainly refer to [START_REF] Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF] and [START_REF] Lothaire | Algebraic Combinatorics On Words[END_REF] for the notations introduced in the sequel.

Generalities

The sets N and N * denote the sets of non-negative and positive integers respectively. We denote by

[[i, j]] the set of integers k such that i ≤ k ≤ j.

Expansions

We consider in this article sequences taking values in alphabets which consist of integers. For convenience, we identify the notions of expansions . . . u 0 .u 1 . . . and sequences (u n ) n∈Z . We may also identify words and sequences that admit only finitely many non-zero entries; in this case, (u i ) i≥N is said to be finite. In particular, since 0 ∈ A β for any β > 1, we identify (u i ) i∈E and (u i ) i∈Z for any E ⊂ Z, setting the missing terms to 0. For any sequence (u i ) i∈Z , we define u + as the right-sided sequence (u i ) i∈N * . For any alphabet A, one may define the shift map S :

A Z → A Z , (u i ) i∈Z -→ (u i+1 ) i∈Z .
The shift map may be defined as the corresponding shift action on A N * as well. We say that (u i ) i≥N is ultimately periodic if there exists n ∈ Z such that (S n (u)) + is periodic.

β-numeration and algebraic numbers

Let β be an algebraic integer of degree d. We denote by {α j } j∈[ [1,r+s]] the set of algebraic conjugates which differ from β and have a non-negative imaginary part. There are among them r real numbers and s complex numbers (hence d -1 = r + 2s). For convenience, we set J = [[1, r + s]]. Let z ∈ C and j ∈ J. We call α j -expansion of z any admissible sequence (u i ) i≥-N such that z = i≥-N u i α i j . Note that there exist complex numbers having at least two associated different α j -expansions.

A Pisot (resp. Salem, Perron) number is an algebraic integer β > 1 such that max

j∈J |α j | < 1 (resp. max j∈J |α j | = 1, max j∈J |α j | < β).
Pisot numbers are Parry numbers [START_REF] Bertrand | Développement en base de Pisot et répartition modulo 1[END_REF][START_REF] Schmidt | On periodic expansions of Pisot numbers and Salem numbers[END_REF], and Parry numbers are Perron numbers [START_REF] Denker | Ergodic theory on compact spaces[END_REF][START_REF] Lind | The entropies of topological Markov shifts and a related class of algebraic integers[END_REF]. Note that this latter result was already proven by Parry in [START_REF] Parry | On the β-expansions of real numbers[END_REF] for numbers β > 2. Despite a deep research on Salem numbers ( [START_REF] Boyd | Salem numbers of degree four have periodic expansions[END_REF][START_REF] Boyd | On the beta expansion for Salem numbers of degree 6[END_REF][START_REF] Boyd | The beta expansion for Salem numbers[END_REF]), it is not yet known whether all Salem numbers are Parry numbers.

It is known that {x} β ∈ [0, 1[ for any β > 1, and for any positive real number x. This implies that the set Z β is relatively dense, that is, the distance between a real number and the closest β-integer is uniformly bounded. Moreover, Z β is a discrete subset of R for any β > 1, and it is uniformly discrete when β is a Parry number, that is, the difference between two β-integers cannot be arbitrarily small. The set of numbers such that Z β is uniformly discrete is introduced in [START_REF] Blanchard | β-expansions and symbolic dynamics[END_REF] as the class of specified subshifts, denoted by C 3 . According to Schmeling [START_REF] Schmeling | Symbolic dynamics for β-shifts and self-normal numbers[END_REF], this class has Hausdorff dimension 1, Lebesgue measure 0, and is dense and meager in ]1, +∞[.

The property of having uniformly bounded strings of 0's in d β (1) is equivalent to the uniform discreteness of Z β , and therefore to the fact that Z β is a Delone set, that is, a set which is both uniformly bounded and relatively dense. Any Delone set E for which there exists a finite set F such that E -E ⊂ E + F is said to be a Meyer set. The problem to determine for which algebraic numbers is Z β a Delone or a Meyer set is not totally solved at the moment; however several significant results are known. For instance, Z β is a Meyer set when β is a Pisot number ( [START_REF] Burdík | Beta-integers as natural counting systems for quasicrystals[END_REF]).

It is stated as a conjecture in [START_REF] Verger-Gaugry | On lacunary Rényi β-expansions of 1 with β > 1 a real algebraic number, perron numbers and a classification problem[END_REF] that, for any Perron number β, the lengths of the strings of consecutives 0's which occur in d β (1) are uniformly bounded. However, we believe thanks to numerical evidence and arguments of Diophantine approximation that there exist Perron numbers such that the orbit of 1 under the map

T β : x -→ {βx} is dense in [0, 1].

Automata and paths

We say that G = (V, E) is an automaton if there exists an alphabet A such that E ⊂ V × V × A. In this case, V consists of states, and E consists of edges. Let e = (s, s ′ , i) be an edge. We say that s is the initial state of e, that s ′ is the terminal state of e, and that e is labelled by i.

We call finite path any sequence of edges

(e i ) i∈[[1,n]] = ((s i , s i+1 , u i )) i∈[[1,n]] in G,
where n ∈ N * , and infinite path any sequence of edges (e i ) i∈N * = ((s i , s i+1 , u i )) i∈N * in G. The state s 1 is the initial state of these paths. If there exist n, p ∈ N * such that for all i ≥ n, s i = s i+p , (e i ) i∈N * is said to be ultimately periodic. If moreover one may choose n = 1, (e i ) i∈N * is said to be a loop. We say that a ultimately periodic path or a loop is irreducible when p is minimal in the corresponding definition.

Generalized Rauzy fractal

We recall here the notion of generalized Rauzy fractal [START_REF] Rauzy | Nombres algébriques et substitutions[END_REF], which will be useful in the construction of the automaton defined in Section 3.2. Rauzy fractals were first introduced by Rauzy in [START_REF] Rauzy | Nombres algébriques et substitutions[END_REF][START_REF] Rauzy | Rotations sur les groupes, nombres algébriques et substitutions[END_REF], then by Thurston in [START_REF] Thurston | Groups, tilings and finite state automata[END_REF]. They provide a geometrical representation of the dynamical system associated with a substitution. In the framework of numeration, they are called central tiles by Akiyama [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF][START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF][START_REF] Akiyama | On the boundary of self affine tilings generated by Pisot numbers[END_REF].

Let β be a hyperbolic Perron number of degree d, and let µ β (X) = X dd i=1 a i X d-i be the minimal polynomial of β over Z. Let M β be the companion matrix of µ β , defined as follows:

M β =        
        .
Naturally, R d is the direct sum of the eigenspaces associated with β and its algebraic conjugates {α j } j∈J , that we denote by D and H j respectively. Note that H j ≃ R when α j ∈ R, H j ≃ C otherwise. There exists -→ w ∈ D and a base of H = ⊕ j∈J H j constituted by r + 2s complex eigenvectors ( -→ v j ) j∈[ [1,r+2s]] , which can be chosen such that the following equalities hold:

-→ e 1 = r+2s j=1 -→ v j + -→ w , ∀j ∈ [[1, s]], ∀i ∈ [[1, d]], v r+j [i] = v r+s+j [i],
where -→ e 1 denotes the first vector in the canonical basis of

Z d , v k [i] denotes the i-th coordinate of -→ v k ∈ C d
and z -→ z is the standard conjugacy on C. These relations allow us to define the projections { --→ p Hj } j∈J and -→ p D on each associated subspace along the direct sum of the others, and the coordinates {p Hj } j∈J and p D which satisfy for all Y ∈ R d :

--→ p Hj (Y ) = p Hj (Y ) -→ v j for all j ∈ [[1, r]], --→ p Hj (Y ) = 2Re(p Hj (Y ) -→ v j ) for all j ∈ [[r + 1, r + s]].
For all j ∈ J, we define τ j as the field morphism: Q(β) → Q(α j ), β -→ α j . We denote by τ the map:

Q(β) → R r × C s ≃ R d-1 , x -→ (τ 1 (x), . . . , τ r+s (x)).
The map Φ : A Z β -→ R d is defined by the following relations, where u = . . . u 0 .u 1 . . . ∈ A Z β :

p Hj (Φ(u)) = i∈N u -i α i j when |α j | < 1, p Hj (Φ(u)) = - i∈N * u i α -i j when |α j | > 1, p D (Φ(u)) = - i∈N * u i β -i .
We explain in Remark 3.2 the reason for the minus sign.

Let X + β , X - β and X β denote the sets which consist of right-sided, left-sided and two-sided admissible sequences respectively. Remark 2.1 The notation X β usually denotes a compact metric space. This is not the case here, since X β does not contain 0 ∞ .d * β (1). For any hyperbolic Perron number β, the set Example 2.3 The generalized Rauzy fractal defined by the Fibonacci numeration is depicted in Figure 1.

u∈X β {Φ(u)} is a bounded subset of R d .
One has R β ≃ [-1, φ -1 ] × [-1, 0] ∪ [φ -1 , φ] × [-φ -1 , 0].
In the particular case where β is a Pisot number, the set

u∈X - β {Φ(u)} is a compact set. Definition 2.4 Let β be a Pisot number. The set T β = u∈X - β {Φ(u)} is called Rauzy fractal or central tile. Note that, for any Pisot number β, T β is a subset of H ≃ R d-1 ≃ R r × C s , whereas R β is a subset of R d . Remark 2.5 For any Pisot number β, T β is the projection of R β on ⊕ j∈J H j along D. Hence T β = {τ (Z + β )}.
Example 2.6 The Rauzy fractal defined by d β (1) = 0.111, known as the Tribonacci fractal, is depicted in Figure 2; In this section, we focus on expansions of 0 in base β, that is, sequences (u i ) i≥N for some N ∈ Z, taking values in a finite subset of Z, which satisfy

T β is the closure of { i∈N u i α i ; u i ∈ {0, 1}, u i u i+1 u i+2 = 111 for any i ∈ N}.
i≥N u i β -i = 0.
Let us recall that we may set missing terms to 0, considering that sequences are actually elements of A Z β . First, we give in Section 3.1 a geometric representation of two-sided sequences due to Lemma 3.1. Indeed, these representations belong to a bounded subset of R d (Lemma 3.3). In Section 3.2, we construct a finite automaton G. We see in Section 3.3 that expansions of 0 in base β defined on

A ′ β = [[-2⌊β⌋
, ⌊β⌋]] are represented by paths and loops in G.

Representation of sequences in R d

From now on, we assume that β is a hyperbolic Perron number, except explicit mention of an opposite hypothesis. We denote by

X ′ β the set {(w i -u i -v i ) i∈Z ; (u i ) i∈Z , (v i ) i∈Z , (w i ) i∈Z ∈ X β },
and by L ′ β the language which consists of factors of elements in X ′ β . Let x and y be two positive β-integers. Let (u i ) i∈Z , (v i ) i∈Z and (w i ) i∈Z be the β-expansions of x, y and x + y respectively, setting the value 0 to the missing digits. The sequence (u ′ i ) i∈Z , defined by

u ′ i = w i -u i -v i for all i ∈ Z, belongs to X ′ β . Moreover, (u ′ i ) i∈Z is an expansion of 0 in base β defined on the alphabet A ′ β = [[-2⌊β⌋, ⌊β⌋]], with u ′ i = 0 for any i ≤ -l int (x + y). If d β (x + y) is finite, then (u ′ i )
i∈Z consists of only finitely many non-zero elements. Hence

i∈Z u ′ i α -i j
is defined for all j ∈ J and equals 0 (since τ j (0) = 0). We deduce that the following relations hold when

d β (x + y) is finite: i∈Z u ′ i β -i = 0, (2)
i∈Z u ′ i α -i j = 0, for all j ∈ J.

If (u ′ i ) i∈N * is ultimately periodic, of preperiod n and of period p, we consider the rational fraction R(X)

= n i=-lint(x+y) u ′ i X -i + X p X p -1 ( n+p i=n+1 u ′ i X -i ).
Clearly, R admits β and any of its algebraic conjugate α j as roots. Therefore (2) also holds, and we obtain using the rational fraction R a corresponding relation for [START_REF] Akiyama | On the boundary of self affine tilings generated by Pisot numbers[END_REF].

Let f i be the map defined as follows for any i ∈ Z.

f i : R d → R d , X -→ M β X + i -→ e 1 . ( 4
) Lemma 3.1 Let u = (u i ) i∈Z be a two-sided sequence taking values in A ′ β . Then Φ(S(u)) = f u1 (Φ(u)).
Proof: Let us recall that A ′ β is the finite alphabet [[-2⌊β⌋, ⌊β⌋]], and that S, the shift map naturally defined on A N * β , can be defined on any alphabet and extended to two-sided sequences. Let u = (u i ) i∈Z be a twosided sequence taking values in A ′ β . Let Y 1 = Φ(u). We have the following relations:

p Hj (Y 1 ) = i∈N u -i α i j when H j is contracting, p Hj (Y 1 ) = - i∈N * u i α -i j when H j is expanding, p D (Y 1 ) = - i∈N * u i β -i .
Let Y 2 = Φ(S(u)). We get:

p Hj (Y 2 ) = i∈N u -i+1 α i j when H j is contracting, p Hj (Y 2 ) = - i∈N * u i+1 α -i j when H j is expanding, p D (Y 2 ) = - i∈N * u i+1 β -i .
We deduce the following relations between Y 1 and Y 2 :

p Hj (Y 2 ) = g j (p Hj (Y 1 )), p D (Y 2 ) = h(p D (Y 1 )),
where for any j ∈ J, g j is the affine map: C -→ C, x -→ α j x + u 1 , and h the affine map:

C -→ C, x -→ βx + u 1 . Hence Y 2 = f u1 (Φ(u))
, which ends the proof. Note that the alphabet A ′ β does not play a particular role, and can be replaced by any finite subset of Z. ✷

Let us note that, for any j ∈ J, Z[α j ] is stable under g j , and that Z[β] is stable under h. u i α -i j for any j ∈ J, then the relation between Y 1 = Φ(u) and Y 2 = Φ(S(u)) would be p Hj (Y 2 ) = α j p Hj (Y 1 ) -u 1 when |α j | > 1. Hence the relation τ j • h = g j • τ j would not hold for any j ∈ J, and it would not be possible to define an affine map on R d for which Y 2 is the image of Y 1 . Secondly, let u be a finite expansion of 0 in base β; one has

i∈N u -i β i = - i∈N * u i β -i . Since p Hj (Φ(u)) = - i∈N * u i α -i
j when H j is expanding, we have p Hj (Φ(u)) = i∈N u -i α i j . Hence we do not have to separate the two cases of expanding or contracting eigenvalues, since p Hj (Φ(u)) = τ j (p D (Φ(u))) for all j ∈ J.

The following lemma allows us to represent two-sided sequences defined on A ′ β as elements which belong to a compact subset of R d . Lemma 3.3 Let u = (u i ) i∈Z be a two-sided sequence defined on A ′ β . We then have the following relations:

if |α j | > 1, then | i∈N * u i α -i j | is bounded by 2⌊β⌋ |α j | -1 , (5)
if |α j | < 1, then | i∈N u -i α i j | is bounded by 2⌊β⌋ 1 -|α j | . ( 6
)
Proof: First, since (u i ) i∈Z takes values in the alphabet A ′ β , we have

|u i | ≤ 2⌊β⌋ for all i ∈ Z. If |α j | > 1, then i∈N * u i α -i j is well defined and satisfies | i∈N * u i α -i j | ≤ 2⌊β⌋ i∈N * |α j | -i , hence | i∈N * u i α -i j | ≤ 2⌊β⌋|αj | -1 1-|αj | -1 . If |α j | < 1, then i∈N u -i α i j satisfies | i∈N u -i α i j | ≤ 2⌊β⌋ i∈N |α j | i . ✷ Remark 3.4
Relations that occur in Lemma 3.3 provide inequalities satisfied by images under Φ of sequences defined on A ′ β . If we are looking for inequalities satisfied by images under Φ of elements of X ′ β , better upper bounds than those of relations ( 5) and ( 6) can be computed since one has actually Φ(u) ∈ R ′ β , where R ′ β = {z -x -y; x, y, z ∈ R β }. The use of more accurate inequalities improves the algorithmic process of the construction of the arithmetic graph that we define in Section 3.2; for more details, see [START_REF] Bernat | Computation of L ⊕ for several cases of cubic Pisot numbers[END_REF].

Automaton of expansions of 0 in base β

Under the assumption that β is a hyperbolic Perron number, we will see that it is possible to compute the set of the β-fractional parts of sums of two β-integers, using a slightly modified arithmetic automaton. The notion of arithmetic automaton is introduced by Rauzy [START_REF] Rauzy | Rotations sur les groupes, nombres algébriques et substitutions[END_REF] and studied by Siegel [START_REF] Siegel | Pure discrete spectrum dynamical system and periodic tiling associated with a substitution[END_REF]. Roughly speaking, an arithmetic automaton is defined for a unimodular substitution of Pisot type σ. The states of this automaton can be denoted by elements of Z[β -1 ]. Each edge of the automaton represents the action of an affine map, and is labelled by a digit that belongs to the alphabet [[-⌊β⌋, ⌊β⌋]], where β is the dominant eigenvalue of M σ , the incidence matrix of σ. The loops and ultimately periodic paths in this automaton are labelled by expansions of 0 whose letters belong to the alphabet [[-⌊β⌋, ⌊β⌋]].

If we add the Parry condition on infinite paths in an arithmetic automaton, we obtain an automaton called injectivity automaton. This automaton enables the determination of elements in R d-1 which belong to the fractal boundary of at least two tiles in the periodic tiling of R d-1 defined by T β , in the case where such a tiling exists.

Figure 3 shows the arithmetic automaton for the Tribonacci case, constructed in [START_REF] Messaoudi | Frontière du fractal de Rauzy et système de numération complexe[END_REF].

Let us see how to adapt the construction of the arithmetic automaton, in order to characterize the βfractional parts that may appear when one adds two β-integers as paths in an automaton. Starting from V 0 = {0} ⊂ Z d , we define the sequence (V n ) n∈N of subsets of Z d by the following rule. Let us recall that the maps f i are defined in [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF].

For all n ∈ N, V n+1 = ∪ i∈A ′ β f i (V n ) ∪ V n ∩ R ′ β . (7)
Lemma 3.5 The sequence (V n ) n∈N is stationary.

Proof: By construction, for any n ∈ N, V n is a subset of Z d and is included in R ′ β , which is a bounded subset of R d . However, Z d ∩ R ′
β is finite as the intersection of a bounded set and a discrete set. Since (V n ) n∈N is an increasing sequence for the inclusion, there exists R ∈ N such that V R = V R+1 , hence

V n = V R for all n ≥ R. ✷ Definition 3.6
We define the automaton of expansions in base

β on A ′ β as G = (V R , E), with E = V R × V R × A ′
β , where (s, s ′ , i) ∈ E if and only if s ′ = f i (s). Note that, since the restriction of p D to Z d is one-to-one, the relation p D (s ′ ) = βp D (s) + i is equivalent to s ′ = M β s + i -→ e 1 for all states s, s ′ ∈ Z d . Remark 3.7 The states in G are elements of Z d which belong to a bounded set defined by relations of Lemma 3.3. Thanks to these relations, we may compute an upper bound for N states , the number of states in G. Additionally, since G is deterministic by construction, and since the labels of E take values in [[-2⌊β⌋, ⌊β⌋]], the number of edges in G is less than (3⌊β⌋ + 1)N states . See [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF] for remarks concerning the order of growth of N .

Ultimately periodic paths and loops

Let us see now the connection between β-fractional parts, either finite or ultimately periodic, that occur as the sum of two β-integers, and expansions of 0 defined on the alphabet A ′ β = [[-2⌊β⌋, ⌊β⌋]] which are either finite or ultimately periodic. [1,n]] be a finite path in G. Then, one has p D (s n+1 ) =

Proposition 3.8 Let n ∈ N * . Let ((s i , s i+1 , u i )) i∈[
β n p D (s 1 ) + n i=1 u i β n-i . Proof: By construction, for any i ∈ [[1, n]], (s i , s i+1 , u i ) is an edge in G if and only if s i+1 = f ui (s i ). Hence, s i+1 = f un • . . . • f u1 (s 1
), and we get:

s n+1 = M n β s 1 + n i=1 u i M n-i β -→ e 1 . (8)
Since for all Let us recall that, by construction of V R , any state s in G may be obtained as the image of 0 under the composition of finitely many maps (f i ) i∈A ′ β . Hence, as a particular case of Proposition 3.8, if the state {s} ∈ V R is obtained as the image of the state {0} under the action of f un • . . . • f u1 , one has

i ∈ [[1, n]], u i M n-i β ∈ M d (Z),
p D (s) = n i=1 u i β n-i .
We make the connection between the search of expansions of 0 in base β and the determination of loops or ultimately periodic paths in G thanks to Propositions 3.9 and 3.11. Proposition 3.9 Let ((s i , s i+1 , u i )) i∈N * be an infinite path in G. Then (-u i ) i∈N * is an expansion of p D (s 1 ) in base β.

Proof: Let ((s i , s i+1 , u i )) i∈N * be an infinite path in G. According to Proposition 3.8, one has for any n ∈ N * :

p D (s 1 ) = β -n p D (s n+1 ) - n i=1 u i β -i .
Since G admits only finitely many states, there exists C > 0 such that |p D (s)| < C for any state s. Hence

|p D (s 1 ) + n i=1 u i β -i | < Cβ -n for any n ∈ N * and p D (s 1 ) = lim n→+∞ n i=1 (-u i )β -i , that is, (-u i ) i∈N * is an expansion of p D (s 1 ) in base β. ✷
As a particular case, we obtain the following corollary.

((s i , s i+1 , u i )) i∈N * in G such that (u i ) i∈N * is admissible. If this path exists, it is ultimately periodic. Proof: Let s 1 = s ′
1 be a state in G. Suppose that there exist two infinite paths ((s i , s i+1 , u i )) i∈N * and ((s ′ i , s ′ i+1 , v i )) i∈N * in G, such that (u i ) i∈N * and (v i ) i∈N * are admissible. If these paths are distinct, then there exists n ∈ N such that s n = s ′ n and s n+1 = s ′ n+1 , hence u n = v n . Due to Proposition 3.9, one has

p D (-s 1 ) = i∈N * u i β -i = i∈N * v i β -i , that is, (u i ) i∈N * and (v i ) i∈N * are distincts β-expansions of p D (-s 1 ),
which is absurd. Now, suppose that the path ((s i , s i+1 , u i )) i∈N * in G, where (u i ) i∈N * is an admissible sequence, is aperiodic. Since there are finitely many states in G, there exists integers n and p such that s n = s n+p . Then p D (s n ) = p D (s n+p ), and due to Proposition 3.9, we have (u i+n ) i∈N * = (u i+n+p ) i∈N * , which is absurd. ✷

The study of ultimately periodic paths and loops which occur in G allows us to determine the finite and ultimately periodic expansions of 0 in base β on A ′ β , thanks to the following proposition. Let us recall that, for x ∈ Fin(β) with d β (x) = u -N . . . u 0 .u 1 . . . u N , l int (x) and l f rac (x) respectively denote the lengths of the β-integer part and the length of the β-fractional part of x, that is, and(w i ) i∈Z be the β-expansions of x, y and x + y respectively. Let (u ′ i ) i∈Z be defined by u ′ i+lint(x+y) = w i -u i -v i for all i ∈ Z. Then (u ′ i ) i∈N labels a path in G starting from the state {0}. Moreover, if x + y ∈ Per(β), this path is ultimately periodic; if x + y ∈ Fin(β), this path may be represented by a loop.

l int (x) = N + 1 and l f rac (x) = M . Proposition 3.11 Let x, y ∈ Z + β . Set N = l int (x + y) and N ′ = l f rac (x + y). Let (u i ) i∈Z , (v i ) i∈Z
Proof: Let x, y ∈ Z + β . Set N = l int (x + y) and N ′ = l f rac (x + y). Let (u i ) i∈Z , (v i )
i∈Z and (w i ) i∈Z be the β-expansions of x, y and x + y respectively. Let (u ′ i ) i∈Z be defined by u ′ i+N = w i -u i -v i for all i ∈ Z. Since the β-expansions of x and y are finite, and since x + y ≥ max(x, y), one has w i -u i -v i = 0 for any i ≤ -N . As a consequence, the left-sided part of u ′ consists of zeros, that is, Φ(S -k (u ′ )) = 0 for any k ∈ N; due to Proposition 3.9, (u ′ i ) i∈N * is an expansion of 0 in base β. Therefore we can assume that expansions of 0 are represented in the automaton G by paths whose starting point is the fixed point of f 0 , that is, the state {0}.

Due to [START_REF] Akiyama | A certain finiteness property of Pisot number systems[END_REF], one has

Φ(S i (u ′ )) ∈ V i for all i ∈ N, hence (u ′ i ) i∈N * labels a path in G starting from the state {0}. Clearly, if x + y ∈ Per(β), then (u ′ i ) i∈Z is ultimately periodic. If x + y ∈ Fin(β), one has u ′ k = 0
for any k ≥ l f rac (x + y) + 1, hence s k = 0 for any k ≥ 2 + l int (x + y) + l f rac (x + y), and we obtain a loop of length 1 + l int (x + y) + l f rac (x + y). ✷

4 Finiteness of ultimately periodic β-fractional parts for sums or products of two β-integers

The automaton G previously constructed contains states and edges that are not used in order to characterize finite or ultimately periodic expansions of 0 in base β. Therefore we define in Section 4.1 an algorithmic method of reduction for G. Actually, this method is not needed in our study, but it may improve in a significant way the algorithmic construction of β-fractional parts of sums of β-integers. Then, we consider the case of the addition of two positive β-integers in Section 4.2, and the case of the product of two βintegers in Section 4.3. Finally, we prove in Section 4.4 the finiteness of L ⊕ and L ⊙ .

Reduction of G

Due to Proposition 3.11, expansions of finite or ultimately periodic β-fractional parts of the sum of two β-integers label loops and ultimately periodic paths in G. However, we are only interested in loops and ultimately periodic paths which are labelled by sequences in X ′ β . Indeed, only these sequences may provide expansions in base β on the alphabet A ′ β , constructed digit by digit, for z -x -y, with x, y ∈ Fin(β) and z ∈ Per(β). The algorithm G defined in Section 3.2 may compute an automaton with useless states and edges, in the sense that G may contain states and edges that are not used by any loop or ultimately periodic path which starts from {0}. Let us see how to prune G.

First, we remove recursively the states of G which are not the initial state of any edge, and the edges which admit those removed states as terminal state. This rule removes recursively the states of G which are never reached by an infinite path starting from the state {0}. We obtain at this point G 0 , the connected component of G which contains the state {0}. We denote by (R 1 ) the rule which consists in extracting the connected component of a subgraph of G which contains {0}.

We do not have used any admissibility condition in the construction of G so far. Therefore we need now to define a computational rule in order to remove the states and the edges that are only used by ultimately periodic paths or loops which are not labelled by elements of L ′ β , the language of factors of elements in X ′ β . Bertrand has proven in [START_REF] Bertrand-Mathis | Développement en base θ; répartition modulo un de la suite (xθ n ) n≥0 ; langages codés et θ-shift[END_REF] that β is a Parry number if and only if L β is recognizable by a finite automaton. In this case, L ′ β is recognizable by the triple cartesian product automaton which recognizes L β , and it is possible to determine whether a ultimately periodic path or a loop in G 0 belong to L ′ β . When β is a hyperbolic Perron number that is not a Parry number, we cannot recognize L ′ β by a finite automaton. In this case, it is not possible to compute effectively the ultimately periodic paths in G 0 .

The rule which consists of removing edges and states that are not elements of any loop or ultimately periodic path labelled by a sequence of L ′ β , that we denote by (R 2 ), can be performed by an algorithmic process when β is a Parry number. The graph G 1 that we obtain after having applied (R 2 ) to G 0 is connected, since for any edge (s, s ′ , i) of G 1 , there exists a ultimately periodic path or a loop which contains (s, s ′ , i).

Definition 4.1 We define G +

β as the connected component of G containing {0}, such that, for any edge (s, s ′ , l), there exist an infinite path ((s i , s i+1 , u i )) i∈N in G and i ∈ N * such that (s, s ′ , l) = (s i , s i+1 , u i ).

Note that if we want to consider only finite expansions of 0 in base β, we have to consider the strongly connected component, instead of the connected component, of G + β which contains {0}, and whose loops are labelled by elements of L ′ β .

Remark 4.2 In order to construct the reduced automaton G + β , we can commute the order of application of the rules (R 2 ) and (R 1 ) to G. However, since the admissibility condition associated with L ′ β is difficult to compute, it is more convenient from a practical point of view to perform first (R 1 ).

the states and the edges (s, s ′ , i) corresponds to s ′ = f i (s) whenever i ∈ [ [-⌊β⌋, 2⌊β⌋]]. Easily, we obtain similar versions for Propositions 3.8, 3.9, 3.11 and 4.3. ✷

Multiplication of two β-integers

In this section, we study the β-fractional parts of the product of two β-integers.

Proposition 4.6 Let β be a hyperbolic Perron number. Then the set of finite or ultimately periodic βfractional parts of the product of two β-integers is finite.

Proof: We may suppose without loss of generality that x, y ∈ Z + β . Let d β (x) = (u i ) i∈Z , d β (y) = (v i ) i∈Z and d β (xy) = (w i ) i∈Z . Suppose moreover that d β (xy) is either finite or ultimately periodic. We have for any j ∈ J the relation:

k∈Z (w k -w ′ k )α -k j = 0,
where the sequence

(w ′ k ) k∈Z is defined by w ′ -k = k i=0 u -i v i-k if k ∈ N, w ′ k = 0
otherwise. Note that, unlike the case of addition, the sequence (w ′ i ) i∈Z does not take values on a finite alphabet. However, since (u i ) i∈Z and (v i ) i∈Z take values in A β , we have w ′ -i ∈ [[0, (i + 1)⌊β⌋ 2 ]] for all i ∈ N. This means that, for any α j an algebraic conjugate of β such that |α j | > 1, the series i∈N w ′ -i α i j is absolutely convergent, since the main term of this series is bounded in modulus by the product of a polynomial term and a geometric term of modulus less than 1. Hence for all j ∈ J, there exists

B j ∈ R * + such that i∈N w ′ -i |α j | i < B j .
We retrieve an equation which provides a connection between the β-integer part and the β-fractional part of xy, which is

i∈N (w -i -w ′ -i )M i β -→ e 1 = - i∈N * w i M -i β -→ e 1 . (9)
Since (w -i ) i∈N and (w ′ -i ) i∈N contain finitely many non-zero elements, the right hand side of (9) belongs to Z d , and we get the following relations:

if |α j | > 1, then | i∈N * w i α -i j | < ⌊β⌋ |α j | -1 , if |α j | < 1, then | i∈N (w -i -w ′ -i )α i j | < B j + ⌊β⌋ 1 -|α j | .
As in the case of addition, the finite or ultimately periodic β-fractional parts of the product of two βintegers label loops in an automaton with states that belong to the discrete lattice Z d and a bounded set B ⊂ R d defined by the previous inequalities. It follows that there are only finitely many finite β-fractional parts of products of two β-integers. ✷ Remark 4.7 As mentioned in the proof, the only noteworthy difference with the case of addition is that, since (w ′ -i ) i∈N may take infinitely many distinct values, it is not possible to compute the set {z : z = {xy} β for some x, y ∈ Z + β , d β (x + y) is finite or ultimately periodic}.

Finiteness of L ⊕ and L ⊙

In [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], it has been asked whether there exists a Perron number β such that L ⊕ or L ⊙ are not finite. The following theorem answers this question. Proof: Let β be a Perron number. If β is hyperbolic, the result is a consequence of Theorem 4.4 and Proposition 4.6. Now, suppose that β is not hyperbolic, that is, there exists an algebraic conjugate α j of β such that |α j | = 1. Since µ β (α -1 ) = µ β (α j ) = 0, µ β is a reciprocal polynomial, hence µ β (β -1 ) = 0.

First, let us consider the case of the addition of two β-integers. Let us recall that l f rac (x) denotes the length of the β-fractional part of x ∈ Fin(β). Suppose that L ⊕ is not finite. This implies that there exists a countable subset I of N * such that, for any k ∈ I, there exist x, y ∈ Z + β such that l f rac (x + y) = k. Note that, in this case, l f rac (β l (x + y)) = k -l for any l < k. Hence for any k ∈ N * , there exist x k , y k ∈ Z + β such that l f rac (x k + y k ) = k. We deduce that there exist a sequence (u

(n) ) n∈N * , with u (n) = (u (n) i ) i∈N * for all n ∈ N * , such that, for any n ∈ N * : 1. (u (n) i ) i∈Z ∈ X ′ β and (u (n) i ) i∈N * ∈ X + β , 2. (u (n) i ) i∈Z is a finite expansion of 0 in base β, 3. there exists x n > 0 such that d β (x n ) = (u (n) i ) i∈N * and l f rac (x n ) = n. Let n ∈ N * . Since (u (n)
i ) i∈Z contains finitely many non-zero digits for any n ∈ N * , it defines an expansion of 0 in base β, that is,

i∈Z u (n) i β -i = 0. However, because β -1 is an algebraic conjugate of β, one has i∈Z u (n) i β i = 0 as well, which is equivalent to i∈N * u (n) i β i = - i∈N u (n) -i β -i . Since l f rac (x n ) = n implies u (n)
n ≥ 1, the left-hand side of the previous equality is greater than β n . On the other hand, since (u

(n) i ) i∈N *
takes values in A β , the right-hand side of the equality is bounded. We deduce that L ⊕ is finite when β is a non-hyperbolic Perron number.

Assume now that L ⊙ is not finite. The only difference with the case of addition is that (u

i ) i∈Z does not take values in a finite alphabet. However, using the same argument as in Proposition 4.6, and using the fact that β -1 is an algebraic conjugate of β by hypothesis, we obtain the same contradiction as in the case of addition if we suppose that for any k ∈ N * , there exist x, y ∈ Z + β such that l f rac (xy) = k. Hence L ⊙ is finite. ✷ Remark 4.9 If β is not a Parry number, we do not know whether the algorithmic construction of the set of finite β-fractional parts of the sum of two β-integers terminates.

Other related questions

In Section 5.1, we consider formal power series in β when β is a Pisot number. Since they define converging series when we replace β by any of its algebraic conjugate, we construct in the same way as in Section 4 an automaton G ′ β , which characterizes formal power series in β whose sequences of coefficients are both admissible and ultimately periodic. Then, in Section 5.2, we give an explicit algebraic construction of Thurston's automaton, introduced at first in [START_REF] Thurston | Groups, tilings and finite state automata[END_REF]. Finally, we construct in Section 5.3 the automaton G ′ β for the Tribonacci case.

Formal power series in β

In [START_REF] Bernat | Computation of L ⊕ for several cases of cubic Pisot numbers[END_REF], we studied the computation of L ⊕ in the particular case of Tribonacci. We have proven that the sum of two β-integers has a β-fractional part of length less than or equal to 5, and that there exist two elements of the associated Rauzy fractal T such that their sum admits an α-expansion of length 6. This can be seen as a limit case, in the sense that, for any z ∈ T , there exists a sequence of β-integers (b i ) i∈N such that (z i ) i∈N , the sequence of elements in T which satisfy p Hj (z i ) = τ j (b i ) for all j ∈ J, tends to z. We see here that the study of limit cases is related to the study of formal power series in β whose sequences of coefficients consist of ultimately periodic sequences that are admissible. In the framework of graphs, this is related to the study of an automaton G ′ β , defined below, similarly generated as in Section 3.2 but where the sense of the edges are reverted.

In Section 4, we have constructed an automaton which recognizes finite or ultimately periodic expansions of 0 in base β which are defined on the alphabet A ′ β . Since β > 1, non-finite expansions of 0 in base β define formal power series in β that do not represent real numbers. However, when β is a Pisot number, we obtain well defined converging series if we replace β by any of its algebraic conjugates α j . In the case of a ultimately periodic expansion, this can be done using the field morphism τ j , since ultimately periodic expansions of 0 in base β characterize the elements of Q(β) in the Pisot case ( [START_REF] Bertrand | Développement en base de Pisot et répartition modulo 1[END_REF][START_REF] Schmidt | On periodic expansions of Pisot numbers and Salem numbers[END_REF]). This is why we consider mainly ultimately periodic expansions from now on. We will see that the limit cases in the computation of L ⊕ can be computed in an algorithmic way.

Assume now that β is a Pisot number of algebraic degree d. If we revert the sense of the edges in G, the mirror image of (u i ) i∈N * , where (u i ) i∈N * labels a path in G, belongs to a compact subset of A N * β . The sequence (x k ) k∈N * of elements of R d defined by p Hj (x k ) = k i=0 d i+1 α i j is a sequence taking values in the Rauzy fractal T β . Moreover, since β is a Pisot number, p Hj (x k ) admits a limit for any j. Since T β is closed, any formal power series in β whose coefficients are the terms of a ultimately periodic sequence which belongs to X β can be represented in R d-1 as an element which belongs to the associated Rauzy fractal T β . In order to compute the limit cases, that is, the β-fractional parts of sums of two ultimately periodic formal power series in β whose coefficients satisfy the admissibility condition, we have to revert the edges in the construction of G. We want here to obtain two-sided expansions of 0 with only finitely many nonzero terms to the right, whereas we studied in Section 3 two-sided expansions of 0 with only finitely many non-zero terms to the left. More precisely, since we revert the sense of reading, the algorithmic construction of the automaton G ′ is the following, with V ′ 0 = {0}:

for all n ∈ N, V ′ n+1 = ∪ k∈[[-2⌊β⌋,⌊β⌋]] f -1 k (V ′ n ) ∩ Z d ∩ 3R ′ β . (10)
Remark 5.1 Note that β is a unit if and only if f -1 i (Z d ) ⊂ Z d for any i ∈ Z. In this case, the definition of V ′ n+1 in [START_REF] Ambrož | Addition and multiplication of β-expansions in generalised Tribonacci base[END_REF] does not require the intersection with Z d . This intersection is however needed in the nonunit case, since f -1 u0 (Z d ) ⊂ Q d is not sufficient to deduce anything about the finiteness of the constructed automaton. We do not need to distinguish the two cases of a unit and a non-unit number in [START_REF] Akiyama | A certain finiteness property of Pisot number systems[END_REF].

The automaton G ′ can be pruned following the steps of reduction that are described in Section 4.1; we obtain in the same way a reduced automaton G ′ + β . The loops of G ′ + β are exactly the loops of G + β labelled by the mirror image of admissible words v, since the strongly connected component which contains {0} in G does not change if we revert the sense of reading. However, since the sense of reading is significant in the definition of the connected component of G which contains {0}, there is no connection between the ultimately periodic paths in G + β and those in G ′ + β . Then, we find the set of limit cases by finding the finite number of ultimately periodic paths in G ′ + β , that can be done following the results described in Section 4. We detail in Section 5.3 the example of Tribonacci.

An effective construction of Thurston's automaton

We retrieve here the known result that a Pisot number is a Parry number, see [START_REF] Bertrand | Développement en base de Pisot et répartition modulo 1[END_REF][START_REF] Schmidt | On periodic expansions of Pisot numbers and Salem numbers[END_REF]. We give an algebraic construction of an automaton which is originally introduced by Thurston in [START_REF] Thurston | Groups, tilings and finite state automata[END_REF].

We assume in this section that β is a Pisot number. As we have previously seen for the more general case of Perron numbers of degree d, we can describe R d as D ⊕ j∈J H j . We recall that the map Φ : A Z β → R d is defined as follows. For an admissible sequence u = (u i ) i∈Z , we have p D (Φ(u)) = -i∈N u i β -i , and p Hj (Φ(u)) = i∈N * u i α i j for all j ∈ J. Additionally, Φ • S(u) = f ui • Φ(u) as we have seen in Lemma 3.1, and the coordinates of Φ are bounded both on D and on H j for all j ∈ J. This implies that there exists a compact set K ⊂ R d such that for any u, Φ(u) ∈ K.

Let β be a Pisot number of degree d. Let d β (1) = (u i ) i∈N * . Let v = (v i ) i∈N * be the sequence defined by v 1 = -1 and v i+1 = u i for any i ∈ N * . The elements of (Φ(S k (v))) k∈N * are the images of 1 under finitely

a 1 .

 1 . . . . . . . . a d 1 0 . . . . . . 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . 0 1 0

Definition 2 . 2

 22 Let β be a hyperbolic Perron number. The set u∈X β {Φ(u)}, denoted by R β , is called generalized Rauzy fractal.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Generalized Rauzy fractal for the Fibonacci number

Remark 3 . 2

 32 There are two reasons for the minus sign which occurs in the definition of p Hj when |α j | > 1, and p D , and in the definition of R β as well. First, if we had defined p Hj (Φ(u)) = i∈N *

Fig. 3 :

 3 Fig. 3: Arithmetic automaton for the Tribonacci number

  and since the restriction of p D to Z d is one-to-one, this relation is equivalent to: p D (s n+1 ) = β n p D (s 1 ) + n i=1 u i β n-i . ✷

Fig. 4 :

 4 Fig. 4: An example of a loop in G for the Tribonacci case

Theorem 4 . 8

 48 Let β be a Perron number. Then L ⊕ and L ⊙ are finite. If additionally β is a Parry number, L ⊕ is effectively computable.

Fig. 5 :

 5 Fig. 5: Graph G ′+ β in the Tribonacci case

Acknowledgements

I am indebted to Pierre Arnoux and Valérie Berthé for their advices and corrections, and to Anne Siegel and Christiane Frougny for many interesting remarks and comments. I warmly thank the referees for their corrections and suggestions.

Addition of two positive β-integers

We characterize in this section the β-fractional parts of the addition of two β-integers. If z ∈ Fin(β), then there exist x, y ∈ Z + β such that z = {x + y} β if and only if there exist a loop ((s i , s i+1 , w ′ i )) i∈[ [1,n]] in G + β starting from {0} and k ∈ N * such that, for all i ∈ [ [1, n]], w ′ i+k = w i . If z ∈ Per(β), then there exist x, y ∈ Z + β such that z = {x + y} β if and only if there exist a ultimately periodic path ((s i , s i+1 , w ′ i )) i∈N * in G + β starting from {0}, and k ∈ N such that for all i ∈ N * , w ′ i+k = w i .

Proof: We reduce the proof to the case where {x + y} β is ultimately periodic, since the finite case is a particular subcase and does not require any additional argument. As usual, let x, y ∈ Z + β and

On the other hand, let ((s i , s i+1 , w ′ i )) i∈N * be a path in G + β starting from {0}. Assume that there exists k ∈ N such that for all i ∈ N * , w ′ i+k = w i . Due to Proposition 3.9, (w ′ i ) i∈N * is an expansion of 0 in base β. By construction of G + β , any factor of (w ′ i ) i∈N * belongs to L ′ β . As a consequence, there exist three admissible sequences (u i ) i∈Z , (v i ) i∈Z and (w i ) i∈Z such that w ′ i+k = w i -u i -v i for all i ∈ Z. Moreover, since w ′ i+k = w i for all i ∈ N * , one has u i + v i = 0 for all i ∈ N * . Since (u i ) i∈Z and (v i ) i∈Z take values in A β , which contains only non-negative elements, we get u i = v i = 0 for all i ∈ N * . Hence (u i ) i∈Z and (v i ) i∈Z are β-expansions of β-integers x and y, and (w i ) i∈Z is the β-expansion of x + y; since (w i ) i∈N * is defined as the β-expansion of z, one gets z = {x + y} β . ✷ Theorem 4.4 Let β be a hyperbolic Perron number. The set {z : z = {x + y} β for some x, y ∈ Z + β , d β (x + y) is finite or ultimately periodic} is finite. Furthermore, it is possible to compute effectively this set when β is a Parry number.

Proof: Let ((s i , s i+1 , u i )) i∈N * be an infinite path in G ′ β . Then, for any k ∈ N * , (-u k+i ) i∈N is an expansion of p D (s k ) in base β as seen in Proposition 3.9.

Due to Corollary 3.10, for any state s i in G ′ β , there exists at most one infinite path ((s k , s k+1 , u k )) k≥i in G ′ β such that (u k ) k≥i satisfies the Parry condition. Moreover, in the case of such a path exists, it is necessarily ultimately periodic, and the period is bounded by the number of states in G ′ β . Hence there are finitely many irreducible ultimately periodic paths in G ′ β that are labelled by an admissible word. We may check for each of these paths whether the hypothesis introduced in Proposition 4.3 holds. This provides only finitely many possible numbers which can be described as the β-fractional parts of the sum of two positive β-integers.

Suppose additionally that β is a Parry number. Then the automaton which define the admissibility condition is finite; the triple cartesian product of this automaton contains the automaton

Hence A ′ is finite; as a consequence, one may effectively compute the loops that satisfy the hypothesis of Proposition 4.3. ✷

In order to compute L ⊕ , we have to determine as well the possible paths which correspond to the subtraction of two positive β-integers x and y, with x > y.

Proposition 4.5 Let β be a hyperbolic Perron number. The set {z : z = {x -y} β for some x, y ∈ Z + β , x > y, d β (x + y) is finite or ultimately periodic} is finite. Furthermore, it is possible to compute effectively this set when β is a Parry number.

Proof: Let us see that the case of subtraction of two non-negative β-integers is essentially the same case as the addition, and does not require additional ideas. Let x, y ∈ Z + β , with x > y. Let z = x -y, and let (u i ) i∈Z , (v i ) i∈Z and (w i ) i∈Z be the respective β-expansions of x, y and z. Then (w i + v i -u i ) i∈Z is an expansion of 0 in base β, and

Actually, we have to replace A ′ β by [[-⌊β⌋, 2⌊β⌋]] in [START_REF] Akiyama | A certain finiteness property of Pisot number systems[END_REF] to obtain a sequence of finite sets (V ′ i ) i∈N * , which is increasing for the inclusion and stationary as well. We construct then an automaton, where V ′ R are many maps (f i ) i∈A β ; there exists an infinite path ((s i , s i+1 , v i )) i∈N * in G, with s i = Φ(S i (v)) for any i ∈ N * . Since G + β is finite, there exist n, p ∈ N such that s n = s n+p . However, since d β (1) = (u i ) i∈N * , (u i+k ) i∈N * is admissible for any k ∈ N. Due to Proposition 3.8, one gets p D (s i+1 ) = T i β (1) for all i ∈ N * . This implies that T n (1) = T n+p (1). Hence (u i ) i∈N * is ultimately periodic, that is, β is a Parry number.

Construction of G ′ + β in the case of Tribonacci

Let us recall that the Tribonacci numeration system, introduced in Example 2.6, is defined by the positive root of the polynomial X 3 -X 2 -X -1. The finiteness property holds for this number system; as a consequence, the connected component of G + β which contains the state {0} is strongly connected, and G + β with inverted arrows is a subgraph of G ′ + β . Figure 5 represents the associated graph G ′ + β . There exists a ultimately periodic path in G ′ + β which starts from the state {0} and reaches the state {0.100011}. However, the state {0.100011} does not belong to the strong connected component of G ′ + β which contains the state {0}. Let us give an interpretation of this fact. The two-sided sequence ∞ (11(-2))100011.0 ∞ is an expansion of 0 in base α j , although the sum is not defined in base β, and it belongs to X ′ β . Indeed, there exists a loop of length 3 in G ′ + β which is labelled by the word 11(-2) ∈ L ′ β ; the states of this loops, among which {β -1 + β -5 + β -6 }, do not belong to the strongly connected component of G + β which contains the state {0}. We deduce that the real number z = β -1 + β -5 + β -6 is a limit case: it cannot be the β-fractional part of the sum of two β-integers, however there exist two elements x and y, which belong in fact to the boundary of the associated Rauzy fractal, such that, among the possible α j -expansions of their sum, one of them admits τ j (z) = α -1 j + α -5 j + α -6 j as its α j -fractional part. We check that, if we take x = y = 1 1-α 3 , then x belongs to T β , and x+x admits three different α j -expansions; among these α j -expansions, one of them admits 100011 as its α j -fractional part. See [START_REF] Bernat | Computation of L ⊕ for several cases of cubic Pisot numbers[END_REF] for more details.

If we remove the states {0.0011}, {0.00011}, {0.100011} and {-0.10101} in G ′ + β , we check that the remaining graph is strongly connected, that is, we obtain G + β . The states s such that p D (s) ≥ 0 define the possible β-fractional parts of the sum of two positive β-integers, which are:

We obtain thanks to a similar computation the set of β-fractional parts of the difference of two positive β-integers. Note that, for any vertex of G ′ + β (or G + β with reverted arrows), there exists a loop using this vertex starting from the state {0}, but the edge having for initial state {-β} and for final state {-1 -β -1 } cannot be used in any loop starting from the state {0}.

Remark 5.2

Similarly to what happens for the state {β -1 + β -5 + β -6 }, the state {-β -1 -β -3 -β -5 } belongs to G ′ + β , but it does not belong to G + β with reverted arrows. This means that β -1 +β -3 +β -5 cannot be the β-fractional part of the difference of two positive integers. However there exists (x, y) ∈ T 2 such that, among the α-expansions of x -y, one of them has 0.10101 as its α-fractional part. By computation, we find that, when x = 1+α 1-α 3 and y = α 2 1-α 3 , then (x, y) ∈ T 2 and x -y = y + α -1 + α -3 + α -5 .