Fabio Burderi
email: burderi@math.unipa.it

Antonio Restivo
email: restivo@math.unipa.it

Coding Partitions †

Keywords: Codes, Unique Decipherability, Rational Languages, Variety of Codes

Motivated by the study of decipherability conditions for codes weaker than Unique Decipherability (UD), we introduce the notion of coding partition. Such a notion generalizes that of UD code and, for codes that are not UD, allows to recover the "unique decipherability" at the level of the classes of the partition. By tacking into account the natural order between the partitions, we define the characteristic partition of a code X as the finest coding partition of X. This leads to introduce the canonical decomposition of a code in at most one "unambiguous" component and other (if any) "totally ambiguous" components. In the case the code is finite, we give an algorithm for computing its canonical partition. This, in particular, allows to decide whether a given partition of a finite code X is a coding partition. This last problem is then approached in the case the code is a rational set. We prove its decidability under the hypothesis that the partition contains a finite number of classes and each class is a rational set. Moreover we conjecture that the canonical partition satisfies such a hypothesis. Finally we consider also some relationships between coding partitions and varieties of codes.

Introduction

The theory of uniquely decipherable (U D) codes, born in the context of information theory, plays a relevant role also in language theory and combinatorics on words (see [START_REF] Berstel | The Theory of Codes[END_REF]). In spite of their simple definition, the structure of U D codes is still for a large extent unknown.

In recent years some papers take into account codes that are not U D. The study of the corresponding ambiguities are, in certain cases, motivated by investigations on natural languages (see [START_REF] Del | Ambiguités irreductibles dans les monoides des mots[END_REF]). From another point of view, the classification of ambiguities is related to conditions of decipherability, weaker than U D, introduced to handle some special problems in information transmission (see [START_REF] Lempel | On multiset decipherable codes[END_REF][START_REF] Guzmán | Decipherability of codes[END_REF][START_REF] Restivo | A note on multiset decipherable code[END_REF][START_REF] Savelli | On numerically decipherable codes and their homophonic partitions[END_REF]). More generally, the study of ambiguities can help in understanding the structure of U D codes.

In this paper we introduce the notion of coding partition of a code X (here we call code an arbitrary set of words). Given a partition P = {X 1 , X 2 , . . .} of a code X, P is, roughly speaking, a coding partition of X if any word w ∈ X * has a unique factorization w = z 1 z 2 • • • z t , where each "block" z i is the concatenation of words from one class of P , and consecutive "blocks" are concatenations of words from different classes of P . The notion of coding partition generalizes that of U D code: indeed U D codes correspond to the extremal case in which each class contains exactly one element. In general, for codes that are not U D, the notion of coding partition allows to recover "unique decipherability" at the level of classes of the partition. In other words, such notion gives a tool to localize the ambiguities for a code that is not U D: indeed the ambiguities are bordered inside the individual classes of the partition and a sort of mutual unambiguity holds between the different classes.

By taking into account the natural ordering between the partitions of a set X, where finer is higher, we have that the coding partitions form a complete lattice. As a consequence, given a code X, we can define the finest coding partition P of X. It is called the characteristic partition of X and it is denoted by P (X).

The structure of P (X) gives useful information about coding properties of X. In particular, an extremal case (each class of P (X) contains only one element) corresponds to U D codes. The opposite extremal case (P (X) contains only one class) gives rise to the definition of totally ambiguous code. Such considerations leads to define a canonical decomposition of a code in at most one unambiguous component and in a set (possibly empty) of totally ambiguous components.

In Sec.3, we consider the case of a finite code X and we present an algorithm that gives the canonical decomposition of X. In particular, the algorithm allows also to decide: 1) given a partition P of X, whether P is a coding partition of X, and 2) given a code X, whether it is totally ambiguous.

In Sec.4, we take into account the rational case. We consider a partition P = {X 1 , X 2 , . . . , X n } of a rational code X in a finite number of classes and such that all classes X i are rational sets. We define a rational relation related to such a partition, and we prove that the partition is coding if and only if the rational relation is a function. This allows to decide whether the partition is coding.

In the last section, we consider the relationships between coding partitions and varieties of codes (see [START_REF] Guzmán | Decipherability of codes[END_REF]). We prove that, given a coding partition of a code X, if each class of the partition belongs to a given variety of codes, then X belongs to the same variety.

Partitions of a code

Let A be a finite alphabet. Let A * denotes the free monoid generated by A, i.e. the set of words over the alphabet A, and let A + = A * \{ε}.

A code X over A is a subset of A + . The words of X are called code words, the elements of X * messages, where X * denotes the submonoid of A * generated by X, i.e. the set of words obtained concatenating elements of X.

A code X is said to be uniquely decipherable (U D) if every message has a unique factorization into code words, i.e. the equality

x 1 x 2 • • • x n = y 1 y 2 • • • y m ,
x 1 , x 2 , . . . , x n , y 1 , y 2 , . . . , y m ∈ X, implies n = m and x 1 = y 1 , . . . , x n = y n .

The theory of U D codes has been widely developed, and it is closely related also to problems in automata theory, combinatorics on words, formal languages and semigroup theory. A complete treatment of such theory can be found in [START_REF] Berstel | The Theory of Codes[END_REF].

Remark 1 In literature, in general, the word code denotes a U D code (see [START_REF] Berstel | The Theory of Codes[END_REF]). In this paper we take also into account conditions of decipherability weaker than U D. This motivate the choice to call code an arbitrary subset of A + .

Let X be a code and let P = {X 1 , X 2 , . . . , X i , . . .}, be a partition of X i.e. : i≥1 X i = X and X i ∩ X j = ∅, for i = j.

We say that a partition P is concatenatively independent if, for i = j,

X + i ∩ X + j = ∅. Let P = {X 1 , X 2 , . . .} be a concatenatively independent partition of a code X. A P -f actorization of an element w ∈ X + is a factorization w = z 1 z 2 • • • z t , where • ∀i z i ∈ X + k , for some k ≥ 1 • if t > 1, z i ∈ X + k ⇒ z i+1 / ∈ X + k , for all 1 ≤ i ≤ t -1.
The partition P is called a coding partition if it is concatenatively independent and moreover any element w ∈ X + has a unique P -f actorization, i.e. if

w = z 1 z 2 • • • z s = u 1 u 2 • • • u t ,
where

z 1 z 2 • • • z s , u 1 u 2 • • • u t are P -f actorizations of w, then s = t and z i = u i for i = 1, . . . , s.
Remark 2 If P = {X 1 , X 2 , . . .} is a coding partition of X, in general neither X nor the sets X i are U D codes. On the other hand P may not be a coding partition though all X i are U D. This is shown by the following examples.

Example 1 P = {X 1 , X 2 , }, X 1 = {00, 000}, X 2 = {11, 111}. X 1 and X 2 are not U D but all the words of X + have a unique P -factorization.

Example 2 P = {X 1 , X 2 , }, X 1 = {0}, X 2 = {01, 10}. The sets X 1 , X 2 are U D but the word w = 010 ∈ X + has two P -factorizations : w = (0)(10) = (01)(0).
Remark 3 If X is a U D code then every partition of X is a coding partition. Therefore if e.g. X is a infinite U D code, it is possible to have coding partitions with infinitely many classes.

Let X be a code and let x 1 x 2 • • • x s = y 1 y 2 • • • y t be two factorizations into code words of a message w ∈ X + . In the sequel, when no confusion arises, sometimes we will denote by w both the "word" w and the relation x

1 x 2 • • • x s = y 1 y 2 • • • y t . We say that the relation x 1 x 2 • • • x s = y 1 y 2 • • • y t is prime if for all i < s and for all j < t one has x 1 x 2 • • • x i = y 1 y 2 • • • y j . Remark 4 A relation w = x 1 x 2 • • • x s = y 1 y 2 • • • y t can be uniquely factorized into prime rela- tions w = v 1 v 2 • • • v p , where v 1 = x 1 • • • x i2-1 = y 1 • • • y j2-1 ,
. . .

v p = x ip • • • x s = y jp • • • y t .
Remark 5 Let P = {X 1 , X 2 , . . .} be a partition of a code X and let w ∈ X + be a message. If there exists a unique factorization of w into code words then there exists a unique P -factorization of w: the consecutive words belonging to the same set of the partition will form a block. This means that if we have two distinct P -factorizations of a message w, we have at least two distinct factorizations of w into code words.

Theorem 1 Let P = {X 1 , X 2 , . . .} be a partition of a code X. The partition P is a coding partition of X iff for every prime relation

x 1 x 2 • • • x s = y 1 y 2 • • • y t
there exists an integer h such that for all i ≤ s and for all j ≤ t, x i , y j ∈ X h .

Proof:

⇒ Let w = x 1 x 2 • • • x s = y 1 y 2 • • • y t be a prime relation and let z 1 z 2 • • • z p be the unique P -factorization of w.
We prove that p = 1. If p > 1, by the uniqueness of the P -factorization, there exist l < s , m < t, such that

z 1 = x 1 x 2 • • • x l = y 1 y 2 • • • y m ;
but this contradicts the fact that the relation is prime. ⇐ We first prove that the sets X i are concatenatively independent. Suppose, by contradiction, that there exists a word w ∈

X + h ∩ X + k , with h = k and let w = x 1 x 2 • • • x s = y 1 y 2 • • • y t , with x i ∈ X h , 1 ≤ i ≤ s, and y j ∈ X k , 1 ≤ j ≤ t. From the Remark 4 we can factorize w into prime relations w = v 1 v 2 • • • v p and let v 1 = x 1 • • • x l = y 1 • • • y m , l ≤ s, m ≤ t. This contradicts the hypothesis, since x i ∈ X h , y j ∈ X k , h = k.
We will show now that every message has an unique P -factorization. Suppose, by contradiction, that w ∈ X + is a message with two distinct P -factorizations:

w = z 1 z 2 • • • z s = u 1 u 2 • • • u t .
Since the sets X i are concatenatively independent, we can assume that z 1 = u 1 . We can then suppose that |u 1 | < |z 1 | and so t ≥ 2. From the Remark 5 there exist at least two different factorizations of w into code words. Given two different factorizations of w, we have a relation that, by Remark 4, can be uniquely factorized as a product of prime relations:

w = v 1 v 2 • • • v p . Since t ≥ 2, there exist i, j ≥ 1 such that u 1 ∈ X + i , u 2 ∈ X + j , with i = j. Now since v h , 1 ≤ h ≤ p,
is a prime relation and u 1 and u 2 belong to different sets of the partition, we have from the hypothesis that p ≥ 2 and no factor v h can cross u 1 , i.e. v h cannot be factorized as v h = xy, with x suffix of u 1 and y prefix of u 2 . In particular

|v 1 | ≤ |u 1 | < |z 1 | and then v 1 is a prefix of both u 1 and z 1 . By hypothesis we obtain that z 1 ∈ X + i . Let u 1 = v 1 v 2 • • • v k , 1 ≤ k < p. Now if s > 1 or t > 2, v k+1 can cross neither u 2 nor z 1 so, in any case, v k+1 is a prefix of u 2 and a factor of z 1 . But u 2 ∈ X + j , z 1 ∈ X +
i and v k+1 is prime. So we have a contradiction and this concludes the proof. ✷

The partition P

= {X 1 , X 2 , . . .} of X is called trivial if |P | = 1. It is called the discrete partition if |X i | = 1 for i ≥ 1.

Remark 6

The trivial partition is a coding partition. Moreover X is a U D code if and only if the discrete partition of X is a coding partition. In this sense the notion of coding partition generalizes to the partitions of a set the notion of U D code.

Given a partition

P = {X 1 , X 2 , . . .} of a code X, a subset Y ⊆ X is a cross-section of P , if |Y ∩ X i | = 1, for i ≥ 1.
Theorem 2 If P is a coding partition of X, then any cross-section Y of P is a U D code.

Proof: Let Y ⊆ X be a cross section of P = {X 1 , X 2 , . . .} and let Y = {y 1 , y 2 , . . .}. Assume that Y is not U D, then there exists a word w ∈ Y + with two distinct factorizations w = y

1 y 2 • • • y s = y ′ 1 y ′ 2 • • • y ′ t , y i , y ′ j ∈ Y for 1 ≤ i ≤ s, 1 ≤ j ≤ t and we can assume that y 1 = y ′ 1 .
Of course w ∈ X + but these factorizations may be not P -factorizations because it's possible that y i = y i+1 for some 1 ≤ i ≤ s -1 or y ′ j = y ′ j+1 for some 1 ≤ j ≤ t -1. We obtain a P -factorizations if we turn the repetitions in a block, but we obtain two distinct P -factorizations: indeed, since

y 1 = y ′
1 and Y is a cross section, the first blocks are different. Since P is, by hypothesis, a coding partition, we have a contradiction and so Y must be a U D code. ✷

Remark 7

The converse of previous proposition does not hold in general, i.e. there exist noncoding partitions P of a code X, such that all the cross-sections of P are U D codes. This is shown by the partition in the Examples 2. As a consequence, in order to decide whether a partition P of a finite code X is coding, it does not suffice to test whether all cross-sections of P are U D codes. An algorithm to decide whether a partition is coding will be given in the next section.

Recall that there is a natural order between the partitions of a set X: if P 1 and P 2 are two partitions of X, P 1 ≤ P 2 if the elements of P 1 are unions of elements of P 2 .

Theorem 3 The set of the coding partitions of a code X is a complete lattice.

Proof: Let L(X) the set of all coding partitions of a set X and let F = {P i | P i ∈ L(X) , i ∈ I} be a family of coding partitions of X. Since the partitions of a set form a complete lattice, it is sufficient to prove that both the meet M = i≥1 P i and the join J = i≥1 P i belong to L(X). Let

x 1 x 2 • • • x s = x s+1 x s+2 • • • x t be
a prime relation between code words and let S = {x 1 , x 2 , . . . , x t }. By Theorem 1 there exists X hi ∈ P i , such that S ⊆ X hi , ∀i ∈ I. Since M ≤ P i ∀i ∈ I, there exists X k ∈ M such that S ⊆ X k ; from another hand since J is the least upper bound there exists X l ∈ J such that S ⊆ X l so, by the same theorem, we obtain the thesis. ✷

As a consequence of previous theorem, given a code X, we can define the finest coding partition P of X. It is called the characteristic partition of X and it is denoted by P (X).

Then, as remarked before, X is a U D code if and only if P (X) is the discrete partition. The opposite extremal case gives rise to the next definition.

A code X is called ambiguous if it is not U D. It is called totally ambiguous if |X| > 1 and P (X) is the trivial partition.

The code X = {01, 10, 1} is totally ambiguous, as the reader can easily verify using Theorem 1.

Remark 8

In [START_REF] Weber | The finest homophonic partition and related code concepts[END_REF], Weber and Head introduced the notion of numerically decipherable code: a code X is numerically decipherable (N D) if any two factorizations in code words of each message over X involve the same number of words. In the same paper the authors introduced the notion of homophonic partition of N D codes. The notion of coding partition is here introduced for any code, i.e. for an arbitrary set X of words, and differs from that of homophonic partition even in the case when X is a N D code. Indeed in [START_REF] Weber | The finest homophonic partition and related code concepts[END_REF] the authors show that {{0, 10, 101}, {111}} is the finest homophonic partition of the N D code X = {x 1 , x 2 , x 3 , x 4 } = {0, 10, 101, 111}. Since x 2 x 4 x 2 = x 3 x 4 x 1 is a prime relation, we have, according to Theorem 1, that P (X) is the trivial partition.

A less trivial example of totally ambiguous code is the code X = {000, 0010, 001, 10, 1}, that we will study in an example of the next section.

Theorem 4 Let P (X) = {X 1 , X 2 , . . .} be the characteristic partition of a code X.

If |X i | > 1
for some i ≥ 1, then X i is a totally ambiguous code.

Proof: Suppose, without loss of generality, that |X 1 | > 1. Suppose, by contradiction, that X 1 is not totally ambiguous, and let P (X 1 ) = {Y 1 , Y 2 , . . .} be the characteristic partition of X 1 , with |P (X 1 )| ≥ 2. If we consider now P ′ = {Y 1 , Y 2 , . . . , X 2 , . . .}, this is a coding partition of X with P (X) < P ′ . Since this contradicts the definition of P (X), X 1 must be totally ambiguous. ✷

The property that any proper subset Y of an ambiguous code X is a U D code, is related to the property of X to be totally ambiguous, as we can see from the next proposition.

Theorem 5 Let X be a code such that all proper subsets Y of X are U D codes. Then either X is a U D code or it is totally ambiguous.

Proof: Let X be a non U D code. Let P (X) = {X 1 , X 2 , . . .} be the characteristic partition of X and suppose, by contradiction, that X is not totally ambiguous. Then |P (X)| ≥ 2 and since X is not U D, there exists a X i , i ≥ 1 such that |X i | > 1. We have that X i X and that, by Theorem 4, it is totally ambiguous. This contradicts the hypothesis. ✷

The converse implication does not hold in general, as shown by the last example just given above: it is totally ambiguous, but its proper subset {000, 001, 10, 1} is not a U D code.

Let X be a code and let P (X) be the characteristic partition of X. Let X 0 be the union of all classes of P (X) having only one element, i.e. of all classes Z ∈ P (X) such that |Z| = 1. The code X 0 is a U D code and is called the unambiguous component of X. From P (X) one then derives another partition of X P C (X) = {X 0 , X 1 , . . .},

where |X i | > 1, for i ≥ 1.
The sets X i , with i ≥ 1, are, by Theorem 4, totally ambiguous. They are called the totally ambiguous components of X. The partition P C (X) is called the canonical partition of X: it defines a canonical decomposition of a code X in at most one unambiguous component and a (possibly empty) set of totally ambiguous components. Roughly speaking, if a code X is not U D, then its canonical decomposition, on one hand separates the unambiguous component of the code (if any), and, on the other, localizes the ambiguities inside the totally ambiguous components of the code. If, on the contrary, X is U D, then its canonical decomposition contains only the unambiguous component X 0 .

Computing the canonical partition of a finite code

In this section we present an algorithm that computes the canonical partition of a finite code.

The algorithm is very close to the Sardinas-Patterson algorithm testing whether a code is U D and to its variations like domino graph and simplified domino graph (see [START_REF] Head | Deciding multiset decipherability[END_REF][START_REF] Guzmán | Decipherability of codes[END_REF]). Informally, like in Sardinas-Patterson algorithm, at each step we construct a set of suffixes of code words by comparing the code words with the suffixes constructed in the previous step. Here, in addition, for each new suffix u generated by the procedure, we record in a set S (associated to the suffix u) the set of indices of code words involved in the generation of such a suffix. We then construct a sequence of sets, whose elements are pairs of the form (u, S), where u is a suffix of code words and S is a set of indices corresponding to the code words.

Let X = {x 1 , x 2 , . . . , x k } be a finite code. We construct a sequence (U i ) i≥1 , where each U i is a set of pairs of the form (u, S), with u ∈ A * and S ⊆ {1, 2, . . . , k}. The sequence (U i ) i≥1 is defined inductively as follows:

U 1 = {(u, {i, j})| x i u = x j , 1 ≤ i, j ≤ k, i = j, u ∈ A + },
and, for n ≥ 1,

U n+1 = {(z, S ∪ {i})| x i z = u or uz = x i , (u, S) ∈ U n , u = ε, 1 ≤ i ≤ k},
Consider now the family of subsets of the set {1, 2, . . . , k}

T X = {S| (ε, S) ∈ U i , i > 1},
and denote by S X the set

S X = S∈TX S ⊆ {1, 2, . . . , k}.
Let τ be the transitive closure of the relation ∽ defined in the set S X as follows:

r ∽ t ⇔ r, t ∈ S, S ∈ T X .
Set R 0 = {1, 2, . . . , k} \ S X and let R 1 , R 2 , . . . , R n be the equivalence classes of τ in S X . It is obvious that {R 0 , R 1 , . . . , R n } defines a partition of the set {1, 2, . . . , k}. Such a partition induces, in turns, a partition on the set X = {x 1 , x 2 , . . . , x k }:

X i = {x j ∈ X | j ∈ R i } , i = 0, 1, . . . , n.
We denote this partition produced by the algorithm, by R(X).

Remark 9 Since |X| = k, the elements of U i 's are pairs composed by a suffix of words in X and a subset of {1, 2, . . . , k}. Then the set of different elements in the sequence (U i ) i≥1 is finite. As a consequence, the partition R(X) can be effectively constructed.

Theorem 6 The partition R(X) is the canonical partition of the code X.

Proof:

Let P 0 = {{x j } : j ∈ R 0 } and let P (X) = P 0 ∪ {X 1 , X 2 , . . . X n }. By construction P (X) is a partition of X. Moreover for every prime relation v = x 1 x 2 • • • x s = x s+1 x s+2 • • • x t the
algorithm finds the pair (ε, S), where S = {1, 2, . . . t} and, starting from S, the algorithm creates the set of code words X h . By construction we have that x i ∈ X h , 1 ≤ i ≤ t and so, because of Theorem 1, P (X) is a coding partition. It is left to the reader to convince himself that P (X) is the characteristic partition of X so that R(X) become the canonical partition of the code X. ✷ Corollary 7 Let P = {X 1 , X 2 , . . . , X n } be a partition of a finite code X. There is an algorithm to decide whether P is a coding partition.

Proof: Using the algorithm we find the canonical partition of X, and we test after if P ≤ P C (X) just verifying if the classes of P are unions of classes of P C (X). ✷ Example 3 Consider the code X = {x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 } = {00, 0010, 1000, 11, 1111, 010, 011}.

U 4 = U 2 .
So we have: R 0 = {6, 7}, R 1 = {1, 2, 3} , R 2 = {4, 5}. Then X 0 = {010, 011}, X 1 = {00, 0010, 1000} , X 2 = {11, 111} and P C (X) = {X 0 , X 1 , X 2 } is the canonical partition of X.

Example 4 Consider the code X = {000, 0010, 001, 10, 1}. Set:

x 1 = 000, x 2 = 0010, x 3 = 001, x 4 = 10, x 5 = 1.

We construct the sequence:

U 1 = {(0, {2, 3}), (0, {4, 5})},
where

K i = α -1 i (X i ).
Consider now another alphabet B = {b 1 , b 2 , . . . , b n } and the alphabetic morphism β : Σ * → B * defined as follows:

β(a) = b i ⇔ a ∈ A i .
Let ρ(P ) : A * → B * be the relation defined by the following graph

G(ρ(P )) = {(α(v), β(v))|v ∈ K}.
By the theorem of Nivat, ρ(P ) is a rational relation.

Let us now recall that a relation ρ :

A * → B * is a function if |ρ(u)| = 1 for all words u ∈ A * .
The main result of this section is the following theorem.

Theorem 9 A partition P is a coding partition iff ρ(P ) is a function.

Proof: Let ρ = ρ(P ). From the definition of ρ we see that there is a bijection between the set of the P -factorizations of a word w ∈ X + and the set of the words v ∈ K such that α(v) = w. Moreover since β is injective, P is a coding partition if and only if for each word w ∈ X + , |{β(v) : v ∈ K, α(v) = w}| = 1, that is if and only if ρ is a function. ✷

In [START_REF] Schutzenberger | Sur les Relations Rationnelles[END_REF] M. P. Schutzenberger proved that it is decidable whether a rational relation is a function. As a consequence, we obtain the following corollary of the previous theorem.

Corollary 10 Given a partition P = {X 1 , X 2 , . . . , X n } such that X i , for i = 1, 2, . . . , n, is a rational set, then it is decidable whether P is a coding partition.

Let us now consider the (more difficult) problem to determine the canonical partition of a rational code X. If the canonical partition has infinitely many classes, it is not clear what means to compute such a partition. Remark that the characteristic partition of a rational code X may have infinitely many classes. Consider, for instance, an infinite U D code X: the characteristic partition coincides with the discrete partition, i.e. each class contains only one element and there exist infinitely many classes. However, in such a case, the canonical partition is the trivial partition, composed by only one class. In all examples of rational codes that we know, the number of classes of the canonical partition is always finite and each class is a rational set. So we formulate the following conjecture. CONJECTURE : If X is rational, the number of classes of P C (X) is finite and each class of P C (X) is a rational set.

If the conjecture is true, the restrictive conditions considered in this section are not actually a restriction, but correspond to the general case.

Remark further that, if X is not rational, then P C (X) can have infinitely many classes, as shown by the following example.

Example 5 Consider the code

X = {(a n b) 2 |n ≥ 0} ∪ {(a n b) 3 |n ≥ 0}.
It is easy to verify that P C (X) contains infinitely many classes and that any class X i is of the form

X i = {(a i b) 2 , (a i b) 3 }, i ∈ N.

Coding partitions and varieties of codes

The notion of coding partition allows to decompose a code in such a way that the ambiguities are bordered into the single components of the code and a sort of mutual unambiguity holds between its different components. In recent years, conditions of decipherability weaker than U D have been investigated, formalized in terms of the notion of variety of codes, and a sort of classification of ambiguities of codes has been introduced. It is then interesting to study the relationships between the "type" of ambiguity of the single components in the partition, and that of the whole code.

Let us first briefly introduce the basic definitions and the motivations about the notion of variety of codes. The investigation on decipherability conditions weaker than U D was initiated in [START_REF] Lempel | On multiset decipherable codes[END_REF] by Lempel, who introduced the notion of multiset decipherable (M SD) codes. Here the information of interest is the multiset of code words used in the encoding process so that the order in which transmitted words are received is immaterial. In a more formal way, a code X is a M SD code if the equality

x 1 x 2 • • • x n = y 1 y 2 • • • y m ,
with x 1 , x 2 , . . . , x n , y 1 , y 2 , . . . , y m ∈ X, implies the equality of the two multisets {x 1 , x 2 , . . . , x n } and {y 1 , y 2 , . . . , y m }.

In [START_REF] Guzmán | Decipherability of codes[END_REF] Guzmán considers also the notion of set decipherable (SD) codes. In this case the original message is recovered up to commutativity and actual count of occurrences, i.e. two factorizations of the same message yield the same set of code words. Denote by UD, MSD and SD the classes of U D, M SD and SD codes, respectively. It is clear that UD ⊆ MSD ⊆ SD and has been shown that the two inclusions are strict.

In the same paper [START_REF] Guzmán | Decipherability of codes[END_REF] Guzmán introduces a very general concept of decipherability using varieties of monoids. Unique decipherability, multiset decipherability and set decipherability then appear as very special cases of such general concept.

Let X be a code and let M be a monoid. We say that X is decipherable in M if every map f : X → M extends to a (unique) homomorphism f : X * → M .

Let K be a class of codes and V a class of monoids. We denote by M(K) the class of all momoids in which every X ∈ K is decipherable. Conversely, C(V) represents the class of all codes decipherable in every M ∈ V.

A variety of codes is a class of codes K such that C(M(K)) = K.

The following holds (see [START_REF] Guzmán | Decipherability of codes[END_REF]):

U 1 =

 1 {(10, {1, 2}), (11, {4, 5})}, U 2 = {(ε, {4, 5}), (00, {1, 2, 3}), (11, {4, 5})}, U 3 = {(ε, {1, 2, 3}), (ε, {4, 5}), (10, {1, 2, 3}), (11, {4, 5})},

† Partially supported by Italian MURST Project of National Relevance "Linguaggi Formali e Automi: Metodi, Modelli e Applicazioni" 1365-8050

U 2 = {(00, {1, 2, 3}), (00, {1, 4, 5}), (01, {2, 3}), (01, {3, 4, 5}), (010, {2, 3}), (010, {2, 4, 5})}, U 3 = {(0, {1, 2, 3}), (0, {1, 4, 5}), (1, {1, 2, 3}), (1, {1, 3, 4, 5}), (10, {1, 2, 3}), (10, {1, 2, 4, 5})}, U 4 = {(ε, {1, 2, 3, 4}), (ε, {1, 2, 3, 5}), (ε, {1, 2, 4, 5}), (ε, {1, 3, 4, 5}), (0, {1, 2, 3, 4}), (0, {1, 2, 3, 5}), (0, {1, 2, 4, 5}), (0, {1, 3, 4, 5}), (00, {1, 2, 3}), (00, {1, 4, 5}), (01, {1, 2, 3}), (01, {1, 3, 4, 5}), (010, {1, 2, 3}), (010, {1, 2, 4, 5})}, We claim that, in this case, we can stop the computation. Indeed since U 4 contains the pairs (ε, {1, 2, 3, 4}), (ε, {1, 2, 3, 5}), (ε, {1, 2, 4, 5}), (ε, {1, 3, 4, 5})}, it follows that S X = {1, 2, 3, 4, 5} and that the partition corresponding to the equivalence τ is composed by only one class. Then the canonical partition of X is the trivial partition and then X is totally ambiguous.

The rational case

If a code X is infinite, one can have partitions having an infinite number of classes and, moreover, each class can contain infinitely many elements. In this section we consider first partitions having a finite number of classes and such that each class is a rational set. So we have a concatenatively independent partition

such that each X i is a rational set. In order to give an algorithm to decide whether a partition is a coding partition, we need some preliminary definitions and results from the theory of rational relations. Let us recall that a rational relation ρ :

is a rational subset of the product monoid A * × B * .

M. Nivat has given the following characterization of a rational relation (see [START_REF] Eilenberg | Automata, Languages and Machines[END_REF]).

Theorem 8 Let ρ : A * → B * be a relation. Then ρ is a rational relation iff there exist a new finite alphabet Σ, two alphabetic morphisms α : Σ * → A * and β : Σ * → B * , and a rational subset

Come now back to the partition P = {X 1 , X 2 , . . . , X n }, where each X i is a rational set over the alphabet A. Let A 1 , A 2 , . . . , A n be n disjoint copies of the alphabet A, and set Σ = n i=1 A i . Let α i : A i → A be the bijection of A i and A, for i = 1, 2, . . . , n and let α : Σ * → A * be the extension of the α i to Σ * : α| Ai = α i for i = 1, 2, . . . , n. Set

• UD is a variety of codes corresponding to the variety of all monoids.

• MSD is a variety of codes corresponding to the variety of commutative monoids.

• SD is a variety of codes corresponding to the variety of semilattices i.e. the variety of commutative monoids that are idempotent.

The varieties of codes have been investigated from different points of view. In particular, the papers [START_REF] Guzmán | Decipherability of codes[END_REF] (see also [START_REF] Weber | The finest homophonic partition and related code concepts[END_REF]) studies the problem to decide whether a code belongs to a given variety. In [START_REF] Burderi | Varieties of Codes and Kraft Inequality[END_REF] the authors study the problem to characterize those varieties of codes where the Kraft inequality is satisfied.

Let us now come back to partitions. Let P = {X 1 , X 2 , . . .} be a partition of a code X. We are interested to investigate whether there is some relationship between the varieties corresponding to the classes X i 's and the variety corresponding to the code X. The result of this section, that generalizes a result obtained in [START_REF] Burderi | Varieties of Codes and Kraft Inequality[END_REF], is given by the following theorem.

Theorem 11 Let P = {X 1 , X 2 , . . .} be a coding partition of a code X and let K be a variety of codes. If X i ∈ K for i ≥ 1, then X ∈ K.

Proof: Let N be the variety of monoids associate to the variety K of codes. We have to show that for all monoids M ∈ N , X is decipherable in M . Let M ∈ N , and let f : X → M be a map from X to M . Denote, for i ≥ 1, by g i the restrictions of f to X i :

, we get the unique homomorphism extending f , and so X is decipherable in M . ✷

Using the fact that the varieties of codes form a complete lattice (see Corollary 1.6 in [START_REF] Guzmán | Decipherability of codes[END_REF]) we have the next corollary.

Corollary 12 Let P = {X 1 , X 2 , . . .} be a coding partition of a code X and let K i be varieties of codes such that X i ∈ K i , i ≥ 1. Then X belongs to the join i≥1 K i .

Therefore, in particular, if each X i is a U D code, then also X is a U D code. In the same way, if each X i is a M SD code, then also X is a M SD code, etc. In a coding partition, the properties of the individual classes are transferred to the whole code.


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

Computation of L ⊕ for several cubic Pisot numbers

Keywords: Tribonacci number, β-numeration, β-integers, Rauzy fractal

In this article, we are dealing with β-numeration, which is a generalization of numeration in a non-integer base. We consider the class of simple Parry numbers such that

We prove that these elements define Rauzy fractals that are stable under a central symmetry. We use this result to compute, for several cases of cubic Pisot units, the maximal length among the lengths of the finite β-fractional parts of sums of two β-integers, denoted by L⊕. In particular, we prove that L⊕ = 5 in the Tribonacci case.

Introduction

This article deals with β-numeration, which is a generalization of numeration in a non-integer base. The β-numeration is born in the late 50's [START_REF] Rényi | Representations for real numbers and their ergodic properties[END_REF][START_REF] Parry | On the β-expansions of real numbers[END_REF]. It has known a major realization with the arrival of quasicrystals during the 80's [START_REF] Shechtman | Metalic phase with with long-range orientational order and no translational symmetry[END_REF], since the β-numeration allows a modelling of quasicrystals [START_REF] Burdík | Beta-integers as natural counting systems for quasicrystals[END_REF][START_REF] Barache | Pisot-cyclotomic quasilattices and their symmetry semigroups[END_REF]. The number systems defined by the β-numeration are 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], 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] and theoretical computer science [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. Nowadays, the interactions between these domains still set up the core of the research on β-numeration. 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 = k∈N * ε k β -k , where the sequence (ε k ) k∈N * , called expansion of x in base β, is defined on the alphabet A β = {0, . . . , [β]}. Among the expansions of 1 in base β, the greatest for the lexicographic order is called β-expansion of 1, and denoted by d β [START_REF] Akiyama | Pisot numbers and greedy algorithm[END_REF]. This expansion is constructed by the greedy algorithm, that is, d β (x) = 0.ε 1 . . . ε n . . ., with for all k ∈ N * , ε k = [βT k-1 β (x)], where T β : [0, 1] -→ [0, 1[, x -→ {βx}. The notion of β-expansion was historically introduced by Rényi [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 a dynamical system associated to this numeration.

Let us observe that a natural expansion of 1 in base β is 1. However, defining d β (1) as the greatest sequence for the lexicographic order among expansions of 1 in base β provides useful algebraic informations on β. This is why d β (1) is not defined as 1. Another interesting expansion of 1 in base β is the greatest sequence for the lexicographical order among those which do not end by 0's. This expansion, denoted by d * β [START_REF] Akiyama | Pisot numbers and greedy algorithm[END_REF], is an improper expansion of 1 in base β. At the opposite of the case of numerations in integer bases, d * β (1) is worthwhile since it enables to define the Parry condition, defined below, which plays a key role in the construction and the study of the associated arithmetical language L β . Notably, Parry showed that for any x ∈ [0, 1[, d β (x) is 1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France the only expansion of x in base β which satisfies the following condition called the Parry condition [START_REF] Parry | On the β-expansions of real numbers[END_REF]: for all n ∈ N, S n ((ε k ) k∈N * ) < lex d * β [START_REF] Akiyama | Pisot numbers and greedy algorithm[END_REF],

where S is the shift map: A N * β → A N * β defined by S((ε k ) k∈N * ) = (ε k+1 ) k∈N * . The factors of a sequence in A N * β that fulfills the Parry condition are said to be admissible, and they form the arithmetical language L β .

In the same way as for elements of [0, 1], any positive real number x > 1 can be uniquely expanded as x = n i=0 ε -i β i + i∈N * ε i β -i , where (ε i ) i≥-n satisfies the Parry condition. The part with non-negative powers of β is then called the β-integer part of x, denoted by [x] β ; the part with negative powers of β is called the β-fractional part of x, denoted by {x} β = x -[x] β . This allows a natural generalization for the definition of integers in base β.

Definition 0.1 The set of β-integers, denoted by Z β , is the set of real numbers x for which there exists n ∈ N such that x = ± n k=0 v k β k , where v n . . . v 0 is an admissible word.

The following set, Fin(β), is introduced in [START_REF] Frougny | Finite beta-expansions[END_REF]. It allows to generalize the framework of numeration to the case of a non-integral base, since the elements of Fin(β) play the role of decimal numbers in base β. Definition 0.2 The set of real numbers having a finite β-fractional part is

Fin(β) = k∈N β -k Z β .
Remark 1 For a given algebraic number β > 1, the relation Fin(β) = Z[β -1 ] is known as the finiteness property, denoted by (F).

Whereas not yet fully characterized, the class of numbers satisfying the finiteness property has been extensively studied, and relations with ergodic and combinatorial properties of the associated dynamical system have been highlighted. Moreover, 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 1.4. 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 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. One may refer to [START_REF] Akiyama | Pisot numbers and greedy algorithm[END_REF][START_REF] Akiyama | On the boundary of self affine tilings generated by Pisot numbers[END_REF][START_REF] Frougny | Finite beta-expansions[END_REF] for additional informations.

The sets Z β and Fin(β) are not stable under usual operations like addition and multiplication. For example, when β is the golden ratio 1+ √ 5

2 , which is called the Fibonacci case, one checks that β -1 + β -2 = 1. Then 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 Fibonacci case is the most studied one, since

1+ √ 5 2
is the only Pisot number of degree two which belongs to ]1, 2[. This means that 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 several properties of this numeration. It is clear that

1 ∈ Z β , since 1 ∈ A β holds for any β > 1. Since 1 + 1 = 2 = β + β -2 , one has d β (2) = 10.01, hence Z β is not stable under addition.
Likewise, let β be the positive root of the polynomial X 4 -2X 3 -X -1. Then d β (1) = 0.2011, with 1, 2 ∈ Z β and d β (3) = 10.111(00012) ∞ , hence the sum of two β-integers can have an infinite β-expansion.

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, the required β-expansion will not be produced after a finite 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 finite length of the β-fractional parts which may appear when one adds or multiplies two β-integers. The computation of these values gives an indication on the difficulty of performing arithmetics on Z β .

Definition 0.3 The bound L ⊕ is defined as min{n ∈ N|∀x, y ∈ Z β , x + y ∈ Fin(β) ⇒ β n (x + y) ∈ Z β } when this set is not empty, +∞ otherwise. The bound L ⊙ is defined as min{n ∈ N|∀x, y ∈ Z β , xy ∈ Fin(β) ⇒ β n xy ∈ Z β } when this set is not empty, +∞ otherwise.
Let us explain now why we are interested in the case where L ⊕ and L ⊙ are finite. Indeed, if the sum or the product of two β-integer belongs to Fin(β), then the length of the β-fractional part of this sum or product is bounded by a constant which only depends on β. In this case, one can decide whether a given improper expansion can be renormalized into a finite or an ultimately periodic expansion, in the sense that, if during the renormalization process one gets a β-fractional part of length greater than L ⊕ , then the improper expansion corresponds to a real number that does not belong to Fin(β). Conversely, if the set of lengths of sums of two β-integers is unbounded, then performing arithmetics in Z β will be very difficult if not impossible, since one cannot compute in a finite time any operation on β-integers.

It has been proven that L ⊕ and L ⊙ are finite when β is a Pisot number, respectively in [START_REF] Frougny | Finite beta-expansions[END_REF] and [START_REF] Guimond | Combinatorial properties of infinite words associated with cut-and-project sequences[END_REF]. The computation of these values is however not so easy, especially for L ⊙ . The case of quadratic Pisot numbers has been studied 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] otherwise. 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 for L ⊕ and L ⊙ for Pisot numbers satisfying additional algebraic properties. We prove in a forthcoming article [START_REF] Bernat | Arithmetic automaton for Perron numbers[END_REF] that the bounds L ⊕ and L ⊙ are finite for the more general case of Perron numbers.

Let us detail now connections between arithmetics in base β and the study of some mathematical structures, namely, model sets and Meyer sets, which allow a modelling of quasicrystals. For any β > 1, Z β is a discrete subset of R. The question of finding an algebraic characterization of numbers β such that Z β is uniformly discrete is still open; however it is know that Z β is uniformly discrete when β is a Parry number. Since Z β is relatively dense in R for all β > 1, Z β is a Delone set [START_REF] Lagarias | Geometric models for quasicrystals I. Delone sets of finite type[END_REF] as soon as Z β is uniformly discrete. If moreover there exists F , a finite set, such that Z β + Z β ⊂ Z β + F , Z β is said to be a Meyer set [START_REF] Meyer | Quasicrystals, Diophantine approximation and algebraic numbers[END_REF]. Such sets satisfy a strong property of regularity. A particular subset of Meyer sets is the class of model sets, which are produced by a cut-and-project scheme. Roughly speaking, these sets are obtained as the intersection of the lattice Z d with a window, that is, a compact set of a space called internal space, that is pushed up along a half-line of another space called physical space. In the particular case of β-numeration, the window is the Rauzy fractal T defined in Section 1.4. See also [START_REF] Meyer | Algebraic numbers and harmonic analysis[END_REF][START_REF] Moody | Meyer sets and their duals[END_REF] for additional details.

When Z β is a Meyer set, a method which enables the computation of a minimal finite set F satisfying Z β + Z β ⊂ Z β + F is defined in [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF] and studied in [START_REF] Gazeau | Geometric study of the set of β-integers for a Perron number and mathematical quasicrystals[END_REF], where the problem of recognizing the language which consists of sums of β-integers is studied as well. This question is related to the determination of L ⊕ , since one can choose the sets of β-fractional parts of length less than L ⊕ for F when the finiteness property (F) holds. Note however that the set of β-fractional parts of length less than L ⊕ is not optimal, since they may exist another set F 0 which contains less elements such that Z β + Z β ⊂ Z β + F 0 . Let us remind that Z β is a Meyer set when β is a Pisot number [START_REF] Burdík | Beta-integers as natural counting systems for quasicrystals[END_REF], and that Z β is a Meyer set implies that β is either a Pisot or a Salem number [START_REF] Meyer | Quasicrystals, Diophantine approximation and algebraic numbers[END_REF].

The aim of this paper is, first to study a geometrical property for a particular subclass of Parry numbers, then to apply these results in order to improve the computation of an upper bound for L ⊕ . This allows us to determine the exact value of L ⊕ for several cases of cubic Pisot numbers. This article is structured in the following way. Section 1 gathers definitions and notations that are introduced in the framework of β-numeration. Section 2 is devoted to the class of β which satisfy the following relation:

there exist d ≥ 2, k 1 , k d ∈ N, k 1 ≥ k d such that d β (1) = 0.k d-1 1 k d . (1)
Such numbers define confluent numeration systems, introduced and studied by Frougny [START_REF] Frougny | Confluent linear numeration systems[END_REF]. This is why we will refer to confluent Parry numbers for any Parry number satisfying (1) from now on. We find the following geometric interpretation for confluent Parry numbers. Proposition 2.5. Let β be a confluent Parry number. There exists

- → C ∈ R d-1 such that the Rauzy fractal T is stable under the central symmetry S-→ C : R d-1 → R d-1 , - → X -→ 2 - → C - - → X .
For a given Pisot number β, we introduce and study a symmetric centered set T ′ , which contains the Rauzy fractal T . The equality T ′ = T holds exactly when β is a confluent Parry number. The study of T ′ in Section 3.1 provides inequalities satisfied by any Galois conjugate of β (Propositions 3.4, 3.5). This allows us to improve a method detailed in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], which enables the computation of upper and lower bounds for L ⊕ under an algebraic condition on β. In particular, we determine the exact value of L ⊕ for several cases of cubic Pisot units in Section 3.2. Finally, we focus in Section 3.3 on the Tribonacci case, that is, when β is the positive root of the polynomial X 3 -X 2 -X -1. We improve by the following theorem the result 5 ≤ L ⊕ ≤ 6 [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. Theorem 3.9. When d β (1) = 0.111, we have L ⊕ = 5.

Definitions and notation

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

Substitutions

Let A be a finite set that is called alphabet. Endowed with the concatenation, A generates a monoid called set of finite words, denoted by A * . Let ε denote the empty word. When A is a totally ordered set, the sets A Z , A N and A * are endowed with the lexicographic order < lex .

Let v = v 1 . . . v n ∈ A * . The number of letters of v, called length of v, is denoted by |v|; the number of occurrences of a ∈ A in v is denoted by |v| a . A word w is called factor of v if there exists p, s ∈ A * such that v = pws. The mirror image of v = v 1 . . . v n is defined as v = v n . . . v 1 ,

and the mirror image map as the map A

* → A * , u -→ ũ. A word v ∈ A * is said to be a palindrome when v = v. When v ∈ A N , we set |v| = +∞; a word w is said to be a factor of v if there exists v ′ , a prefix of v, such that w is a factor of v ′ . Let A = {a 1 , . . . , a d }. Let ( e j ) j∈[[1,...,d]] be the canonical basis of Z d . The morphism f : A * → Z d that fulfills f (a j ) = e j for all j ∈ [[1, . . . , d]] is called the abelianization homomorphism.
Any map σ : A → A * , extended to a morphism on A * by concatenation, is called substitution. The substitution σ is said non-erasing if for every a ∈ A, σ(a) = ε. Let σ be a substitution defined on the alphabet A. The incidence matrix of σ is defined as the square matrix

M σ ∈ M d (N) such that, for every (i, j) ∈ [[1, . . . , d]] 2 , M σ [i, j] = |σ(a j )| ai . The substitution is primitive if there exists n ∈ N such that for every (i, j) ∈ [[1, . . . , d]] 2 , M n σ [i, j] ≥ 1. The substitution is said to be unimodular if |det M σ | = 1.
The substitution is said to be of Pisot type if the eigenvalues of the incidence matrix M σ satisfy the following: there exists a dominant eigenvalue β > 1 such that for every other eigenvalue α, one has 0 < |α| < 1. Note that the characteristic polynomial of M σ is irreducible when σ is of Pisot type. Let us remind that a Pisot number is an algebraic integer whose any Galois conjugate α = β satisfies |α| < 1, and that the dominant eigenvalue of M σ is a Pisot numbers when σ is of Pisot type.

Let σ be a substitution. If there exists k ∈ N * such that σ k (ω) = ω, we say that ω is a periodic point of σ. In particular, when σ(ω) = ω, ω is said to be a fixed point of σ. When σ is primitive, we denote by L σ the language generated by the substitution, that is,

L σ = k∈N {factors of σ k (a)},
where a ∈ A. Note that, since we assume that σ is primitive, the definition of L σ does not depend on the choice of a.

Introduction to β-numeration

Let β > 1 be an algebraic integer. The set N ∩ [0, β[ is called β-alphabet and denoted by A β . Let x ∈ [0, 1]. Any sequence (ε k ) k∈N * ∈ A N * β satisfying x = k∈N * ε k β -k is called expansion of x in base β.
The notion of expansion of x in base β is extended on R + by considering sequences of A Z β . Among the expansions of x in base β, the greatest for the lexicographical order is called β-expansion of x. This expansion, denoted by d β (x) = 0.ε 1 . . ., is constructed by the greedy algorithm, that is,

ε k = [βT k-1 β (x)] for all k ∈ N * , where T β : [0, 1[→ [0, 1[, y -→ {βy}. Let d β denote the map: [0, 1] → A N * β , x -→ (ε i ) i∈N * . We recall that the map d β is increasing if A N *
β is endowed with the lexicographic order.

Parry showed in [START_REF] Parry | On the β-expansions of real numbers[END_REF] that, for any x ∈ [0, 1[, d β (x) is the unique expansion of x in base β which satisfy the following relation called Parry condition:

for all n ∈ N, S n (v) < lex d * β (1). ( 2
)
Any word or sequence v ∈ A * β ∪ A N β which satisfy ( 2) is said to be admissible. Let L β denote the set of admissible words. The set of non-negative β-integers, denoted by Z + β , is defined as the set of non-negative real numbers

x satisfying x = n k=0 v i β i , where v n . . . v 0 ∈ L β . The set of β-integers is defined as Z β = ±Z + β . Since Z + β is a discrete set, one may define for x ∈ R + the β-integer part of x as [x] β = max p∈Z + β {p ≤ x}, and the β-fractional part of x as {x} β = x -[x] β . For x > 1, we set d β (x) = v.
w, where v and w respectively are the unique expansions of [x] β and {x} β in base β which satisfy the Parry condition.

For x ∈ R + , let l i (x) denote the length of the β-integer part of x, that is, l i (x) = N + 1, where N ∈ N satisfies β N ≤ x < β N +1 when x ≥ 1, 0 otherwise. If there exists M ∈ N such that ε M =
0 and ε n = 0 for all n > M , we say that the β-expansion of x is finite. In this case, the ending consecutive occurences of the letter 0 are omitted; d β (x) = ε N . . . ε 0 .ε -1 . . . ε -M , and we set l f (x) = M , which denotes the length of the β-fractional part of x. The set of non-negative real numbers having a finite β-expansion is denoted by Fin(β) + , and we set Fin(β) = ±Fin(β) + . When d β (1) is either finite or ultimately periodic, β is said to be a Parry number. More precisely, β is said to be a sofic Parry number when d β (1) is ultimately periodic, and a simple Parry number when d β (1) is finite. The notion of Parry number was historically introduced by Parry [START_REF] Parry | On the β-expansions of real numbers[END_REF] as β-number. 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 Pisot numbers are Parry numbers. When β is a simple Parry number, we denote by m the length of d β (1). In the sofic Parry case, we respectively denote by n and p the lengths of the preperiod and of the period of d β (1), and we set m = n + p for convenience. More details about Parry numbers can be found in [START_REF] Lothaire | Algebraic Combinatorics On Words[END_REF].

Remark 2 One easily checks that m ≥ d, where d is the algebraic degree of β. There exist Parry numbers such that m > d; for instance, the smallest Parry number is the positive root of the polynomial X 3 -X -1, for which one has d β (1) = 0.10001.

Let β be an algebraic integer such that there exists a Galois conjugate α of β which satisfies |α| < 1. Let z ∈ C. We call α-expansion of z any admissible sequence (ε k ) k∈Z such that z = k∈Z ε k α -k .

Remark 3 There exist complex numbers having multiple α-expansions. For instance, consider the Fibonacci case, for which the Galois conjugate of β is α = 1- √ 5

2 . Let the admissible sequences (ε k ) k∈Z and (δ k ) k∈Z be defined by ε j = 1 when j ∈ 2N + 1, ε j = 0 otherwise;

δ j = 1 when j ∈ {-1} ∪ 2N * , δ j = 0 otherwise. Then -1 = k∈Z ε k β -k = k∈Z δ k β -k .
Hence the real number -1 admits both (ε k ) k∈Z and (δ k ) k∈Z as α-expansions.

Notion of β-substitution

For any Parry number β, it is possible to define a substitution which is associated to β in a canonical way. Let β be a simple (resp. sofic) Parry number, with

d β (1) = 0.k 1 . . . k m (resp. d β (1) = 0.k 1 . . . k n (k n+1 . . . k n+p ) ∞ ).
We remind that the elements of (k j ) j∈[ [1,...,m]] are nonnegative integers, and that for all n ∈ N * , S n (d β (1)) < lex d β (1). The substitution σ β is defined on {a 1 , . . . , a m } by:

1. for all j ∈ [[1 . . . m -1]], σ β (a j ) = a kj 1 a j+1 , 2. σ β (a m ) = a km 1 in the simple Parry case, σ β (a m ) = a km 1 a n+1 otherwise.
The substitution associated in this way to a simple (sofic) Parry number β is called a simple (sofic) β-substitution, and is denoted by σ β . Note that a β-substitution is primitive, admits a unique fixed point ω β and is defined on an alphabet containing at least two letters. In particular, the set of the factors of ω β defines a language denoted by L σ . See [START_REF] Fabre | Substitutions et β-systèmes de numération[END_REF][START_REF] Thurston | Groups, tilings and finite state automata[END_REF], where these substitutions are introduced, for more details.

When β is a simple (sofic) Parry number, the incidence matrix

M σ of σ is            k 1 . . . .
           (simple case) or            k 1 . . . .
           (sofic case).
Remark 4 Let us recall that, if σ β is of Pisot type, then β is a Pisot number, but the converse is false. For example, the positive root β of the polynomial X 3 -X -1 is a Pisot number, whereas σ β is not of Pisot type, since the characteristic polynomial of the incidence matrix is X 5 -X 4 -1 = (X 3 -X -1)(X 2 -X + 1), which admits two roots of modulus 1.

Rauzy fractals

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 defined by the associated β-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 Pisot number of degree d, and {α j } j∈[[1,...,r+s]] be the set of the Galois conjugates which differ from β and which have a non-negative imaginary part. Let

µ β (X) = X d - d j=1 b j X d-j
denote the minimal polynomial of β on Z, which admits r + 1 real roots and 2s complex roots, hence d -1 = r + 2s. For convenience, we set

J = [[1, . . . , r + s]].
Let M β be the companion matrix of µ β , defined as follows: , which can be chosen such that the following equalities hold:

M β =         b 1 . . . . . . . . .
- → e 1 = j∈J - → v j + - → w , ∀j ∈ [[1, . . . , s]], ∀i ∈ [[1, . . . , d]], v r+j [i] = v r+s+j [i],
where v k [i] denotes the i-th coordinate of v k ∈ R r × C d-r and z -→ z the standard conjugacy on C. These relations allow us to define -→ p D and, for all j ∈ J, --→ p Hj , which are the projections on each associated subspace along the direct sum of the others. We then set p D and, for all j ∈ J, p Hj as the coordinate maps in the base ( -→ w , -→ v 1 , . . . , ---→ v r+2s ) of the associated projection maps, that is, one gets for all

- → X ∈ R d : --→ p Hj ( - → X ) = p Hj ( - → X ) - → v j , for all j ∈ [[1, . . . , r]], --→ p Hj ( - → X ) = p Hj ( - → X ) Re( - → 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)).

Rauzy fractals and symmetric sets

In this section, we introduce a geometric representation set T ′ for the numeration defined by β, a given algebraic number. The set T ′ , which admits a symmetric property that we explain later, contains the Rauzy fractal T . Then, following [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], the study of T ′ provides inequalities satisfied by the images under τ j of the finite β-fractional parts of sums of two β-integers. This allows us to define an algorithm which improves the determination of an upper bound and of a lower bound for L ⊕ .

Set of β-integers and admissibility

The set of non-negative β-integers is defined as

Z + β = n∈N { n k=0 v k β k , v n . . . v 0 ∈ L β }.
When one performs arithmetics on β-integers, the computation of the admissibility condition is not so easy, and the renormalization process significantly slows down any algorithmic process. If we remove the admissibility condition, we obtain a set that contains Z + β , which is

Σ + β = n∈N { n k=0 v k β k , v n . . . v 0 ∈ A n+1 β }.
Note that, for any x ∈ Z + β , there exists a unique admissible word v n . . . v 0 ∈ L β such that x = n k=0 v k β k , whereas there may exist x ∈ Σ β , n ∈ N and two distincts words v, w ∈ A * β such that

x = n k=0 v k β k = n k=0
w k β k . As an example, the words 100 and 011 represent the same real number in Fibonacci base, since

β 2 = β + 1.
The word 011 is defined on A * β , but it does not belong to L β . Hence, if β is such that Z + β = Σ + β , we can omit the admissibility condition in order to generate the set of β-integers.

The set of Parry numbers for which Z + β = Σ + β is exactly the set of numbers which define confluent numeration systems, which were introduced and studied by Frougny [START_REF] Frougny | Confluent linear numeration systems[END_REF]. Confluent numeration systems characterize numeration systems for which any finite expansion on the alphabet A β can be renormalized as an admissible word which represent a β-integer. Therefore confluent Parry numbers, that is, Parry numbers which define a confluent numeration system, are the numbers for which there is no carry propagating to the right. We will use later the following proposition, which gathers different results from [START_REF] Frougny | Complexity of infinite words associated with beta-expansions[END_REF] and [START_REF] Frougny | Confluent linear numeration systems[END_REF].

Proposition 2.1 [START_REF] Frougny | Complexity of infinite words associated with beta-expansions[END_REF][START_REF] Frougny | Confluent linear numeration systems[END_REF] Let β be a Parry number. The following assertions are equivalent.

One has d

β (1) = 0.k d-1 1 k d , with k 1 , k d ∈ N and k 1 ≥ k d ,
2. the language L σ is stable under mirror image, 3. there exist infinitely many prefixes of ω, the fixed point of σ β , that are palindromes,

one has Z

+ β = Σ + β .
When any of these assertions holds, β is said to be a confluent Parry number.

It is proved in [START_REF] Frougny | Finite beta-expansions[END_REF] that confluent Parry numbers are Pisot numbers such that Fin(β) = Z[β -1 ], that is, the finiteness property holds true. Moreover, the class of confluent Parry numbers defines a class of β-substitutions whose associated dynamical system has purely discrete spectrum [START_REF] Solomyak | Substitutions, adic transformations, and beta-expansions[END_REF], and the complexity of their substitutive language is affine [START_REF] Frougny | Complexity of infinite words associated with beta-expansions[END_REF].

The symmetric property for confluent Parry numbers

We focus on a geometric property for the Rauzy fractal T defined by a Pisot number β, indeed, we see in this section that τ (Σ + β ) is stable under a central symmetry map defined below. Note that, since Z + β ⊂ Σ + β , we get T ⊂ τ (Σ + β ). Moreover, according to Proposition 2.1, the set of confluent Parry number characterizes the Parry numbers for which T = τ (Σ + β ). We will see in Section 3.1 that the relations developed here enable a covering of T with balls having arbitrarily small positive radius, in a more accurate way than in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. In particular, this covering is accurate enough to allow the computation, in several cases of cubic Pisot numbers, of the maximal length of the finite β-fractional parts for the sums of two β-integers.

Definition 2.2 Let d ∈ N * , and let E be a bounded set of R r × C s ≃ R d-1 . The set E is said to be centrally symmetric if there exists - → C ∈ R r × C s such that E is stable under the symmetry S-→ C : R r × C s → R r × C s , - → X -→ 2 - → C - - → X .
( - → C ) = [β]
2(1-αj ) , for all j ∈ J.

Proof: First, note that τ (Σ j β ) is a bounded set of R r ×C s ≃ R d-1 , and that p Hj (τ

(Σ + β )) = τ j (Σ + β ). Let - → X ∈ τ (Σ + β ). There exists a sequence (ε n ) n∈N ∈ A N β such that p Hj ( - → X ) = n∈N ε n α n j for all j ∈ J. Let (δ n ) n∈N ∈ A N β be defined by δ n = [β] -ε n for all n ∈ N. We define - → Y ∈ R r × C s by p Hj ( - → Y ) = n∈N δ n α n j for all j ∈ J. Then p Hj ( - → Y ) = [β] 1-αj -p Hj ( - → X
) for all j ∈ J. Moreover, -→ Y can be described as the limit of a sequence (

-→ Y n ) n∈N ∈ τ (Σ j β ), whose elements are defined by p Hj ( -→ Y n ) = n k=0 δ k α k j for all j ∈ J. Since τ (Σ j β ) is a compact set, we deduce that - → Y ∈ T . Hence, if we define - → C ∈ R r × C s by p Hj ( - → C ) = [β]
2(1-αj ) for all j ∈ J, we obtain that τ (Σ + β ) is stable under the symmetry of center -→ C , which ends the proof. ✷ Definition 2.4 The symmetrized tile is defined as T ′ = τ (Σ + β ). One directly deduces from Proposition 2.1 and Lemma 2.3 the following: Proposition 2.5 Let β be a confluent Parry number. Then T is a centrally symmetric set.

Remark 5 When β is the sofic Parry number defined by the polynomial

X 2 -(k 1 + 1)X + k 1 -k 2 with k 1 > k 2 > 0, one has d β (1) = 0.k 1 k ∞ 2 , T = [0, k1β 2 β 2 -k 2 2
] and

T ′ = [0, k1β β-k2 ].
Hence T is a centrally symmetric set with T T ′ . We do not know whether there exist others Parry numbers for which T is centrally symmetric with T T ′ .

The following proposition characterizes centrally symmetrical Rauzy fractals that contain their center -→ C . Since there exist Rauzy fractals that are not connected, it is not clear whether -→ C ∈ T for any confluent Parry number. Proof: Let β be a confluent Parry number. We consider the two cases k 1 even and k 1 odd. When

k 1 is even, k1 2 ∈ A β and ( n i=0 k1 2 β i ) n∈N is a sequence of β-integers.
For any j ∈ J, the image under τ j of the elements of this sequence is (

n i=0 k1 2 α i j ) n∈N , which tends to k1 2 1 1-αj . Since k 1 = [β], we get k1 2 1 1-αj = p Hj ( - → C ) according to Lemma 2.3. Since T is closed, we deduce that - → C ∈ T . Suppose now that k 1 is odd, with β root of X d -k 1 d-1 i=1 X i -k d . If k 1 -k d is even, we have d-1 i=0 k1 2 β i = 1 2 β d + k1-k d 2 . One has i∈N k1 2 α i j = l∈N ( d i=0 k1 2 α i+l(d+1) j ) = l∈N ( k1+1 2 α d j + k1-k d 2 )α l(d+1) j . Let ( -→ C n ) n∈N ∈ (R d-1 ) N be defined by p Hj ( -→ C n ) = n l=0 ( k1+1 2 α d j + k1-k d 2 )α l(d+1) j
for all j ∈ J and for all n ∈ N. Since k 1 -k d and k 1 +1 are even, with

k 1 ≥ k d ≥ 1, k1+1 2 and k1-k d 2 ∈ A β . Additionally, the word ( k1+1 2 0 d-1 k1-k d 2
) n is admissible for all n ∈ N. This means that the sequence of β-integers

(p n ) n∈N , defined by p n = n l=0 ( k1+1 2 β d + k1-k d 2 )β l(d+1) , satisfies τ (p n ) = -→ C n for all n ∈ N, hence -→ C n ∈ T for all n ∈ N.
Using again Lemma 2.3 and the compactness of T , we deduce that

- → C ∈ T . ✷ Remark 6 Since p Hj ( - → C ) = [β] 2(1-αj ) for any j ∈ J, - → C = - → 0 .
By the way, let us give a geometric interpretation of Proposition 2.5. Assume that β is a confluent Parry number, with d β (1) = 0.k d-1 1 k d . According to Proposition 2.1, the associated substitutive language L σ defined by the substitution σ β is stable under the mirror image map. Moreover, there exist infinitely many palindromic prefixes for ω, the fixed point of σ β . Indeed, let (ω vn ) n∈N be the sequence defined by ω vn = h n (a 1 ) for all n ∈ N, where the map h is defined by

h : L σ -→ L σ , v -→ σ β (v)a k1 1 .
One checks that h preserves the set of palindromes of L σ , which implies that (ω vn ) n∈N is a sequence of palindromic prefixes of ω. Let v ∈ A and x = p D (f (v)), where f denotes the abelianization map. We remind that, by definition of the map p D defined in Section 1.4, one has p D (f (a 1 )) = 1 and p D (σ(w)) = β.p D (f (w)) for all w ∈ L σ . Thus, one has

p D (f (h(v))) = βx + k 1 , hence for all n ∈ N, p D (f (h n (a 1 ))) = g n (1)
, where g : R → R is the affine map defined by g(x) = βx + k 1 .

Since ω vn is a palindrome, the set

E n = {f (ω k ), k ∈ [[0, . . . , v n ]]} is a centrally symmetrical set of Z d . Hence p D (E n ) and p H (E n ) respectively are centrally symmetrical sets of R and R d-1 . Let -→ C n denote the center of p H (E n ). Then for all j ∈ J, p Hj ( -→ C n ) = g vn j (1) 2
, where g j is the affine map: x -→ α j x + k 1 . Let c j be the fixed point of g j for all j ∈ J. Since β is a Pisot number, g j is a contracting map for all j ∈ J, hence the sequence (p Hj (

-→ C n )) n∈N tends to cj 2 . Let - → C be the limit of the sequence ( -→ C n ) n∈N . Since p Hj ( - → C ) = cj 2 , and since k 1 = [β], the center of T satisfies p Hj ( - → C ) = [β]
2(1-αj ) for all j ∈ J. We retrieve the result of Lemma 2.3, since T = T ′ . Note that, rather than the foregoing construction of T as the limit of centrally symmetric sets, constructed by considering prefixes of the fixed point ω of σ β , it is also possible to describe T as the image of the closure of p H (f ( ω ′ .ω ′ )) under a translation map, where ω ′ .ω ′ is a two-sided palindrome whose factors belong to L σ . This construction, and the previous one, cannot be completed when β is a Parry number which is not confluent, since L σ contains only finitely many palindromes in this case.

There is no reason for the tile T to be a centrally symmetric set when β is a Parry number which is not confluent. See for instance Figure 2 and Figure 3, which respectively represent, for the numeration system defined by d β (1) = 0.101, first, the Rauzy fractal T , then the sets T ∪ S-→ C (T ) and T ′ with different levels of shading. In this section, we are interested in computing L ⊕ , or at least computing a better upper bound for L ⊕ than those determined in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. First, we focus in 3.1 on several algebraic inequalities, provided by Propositions 3.4 and 3.5, that are satisfied by the image under τ of the finite β-fractional parts that are obtained as the β-fractional parts of the sum of two β-integers. Whereas these relations do not allow us to compute directly the set of these finite β-fractional parts, we can discard, thanks to an algorithm defined in Section 3.2, the β-fractional parts which do not satisfy these inequalities. In particular, this allows us to compute L ⊕ for several cases of Pisot units, since, among the remaining β-fractional parts that were not discarded by the algorithm A, we find an element of Fin(β), whose β-fractional part is of length L ⊕ , which is the sum of two β-integers.

Fractional parts of sums or differences of β-integers

Let β be a Pisot number, and let (w

i ) i∈N ∈ A N β . Let (v i ) i∈N be defined for all i ∈ N by v i = [β]-w i . Since (v i ) i∈N ∈ A N β , T ′ = τ (Σ + β ) contains both T and S-→ C (T ) = - → X ∈T {2 - → C - - → X }, where - → C is the center of T ′ .
We deduce from T ⊂ T ′ that inequalities satisfied by elements of T ′ are satisfied by elements of T as well. Note that there is no reason that T S-→ C (T ) = T ′ , see Figure 3.

First, let us recall some results of [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], where a method is described in order to compute upper bounds for L ⊕ and L ⊙ . Let α j denote a Galois conjugate of β such that |α j | < 1. We define for all n ∈ N * the real numbers

M n (j) = max x∈Z + β {|τ j (x)|, x < β n }, H n (j) = M n (j) 1 -|α j | n and H(j) = sup x∈Z + β |τ j (x)|.
Let us give a geometric interpretation for H n (j). Indeed, H n (j) is the upper bound of the modulus of complex numbers z ∈ T such that, for all j ∈ J, p Hj (z) admits a periodic α j -expansion of period n. Hence, for all j ∈ J, H l (j) ≥ H k (j) for all k, l ∈ N such that l|k, and H k (j) ≥ H(j) for all k ∈ N * .

The following inequality, used for instance in the proof of Proposition 3.2, holds.

Proposition 3.1 For all x ∈ Z β and n ∈ N * , |τ j (x)| < H n (j).
Proposition 3.1 allows us to obtain the following result, which provides upper bounds for L ⊕ and L ⊙ . Proposition 3.2 [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF] Let β > 1 be an algebraic integer. If there exists a Galois conjugate α j of β such that K(j) = inf

z∈Z + β βZ + β |τ j (z)| > 0, then L ⊕ < ln 2 + ln H(j) -ln K(j) -ln |α j | and L ⊙ < 2 ln H(j) -ln K(j) -ln |α j | .
In particular, assume that d β (1) = 0.k 1 k 2 k 3 , and that β has two complex Galois conjugates. Then β is a Pisot cubic number; the finiteness property holds [START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF], which implies due to [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF] that 0 is an inner point of T . Hence K(j) > 0, and the required conditions of Proposition 3.2 are satisfied. Proposition 3.2 is a consequence of Proposition 3.1. Indeed, let x and y ∈ Z β with x+y ∈ Fin(β). Since l f (x + y) ≤ L ⊕ , one gets |τ j (x)| + |τ j (y)| < 2H(j) and |τ j (x + y)| > |α j | L⊕ K(j). Hence the upper bound for L ⊕ , and the case of multiplication is performed in a similar way. We focus now on the search of better inequalities satisfied by elements of Fin(β), since this will allow us to deduce better upper bounds for L ⊕ and L ⊙ . Inequalities improving Proposition 3.1 are detailed below in Propositions 3.4 and 3.5.

Since Z +

β ⊂ Σ + β , any inequality satisfied by elements of τ (Σ + β ) is satisfied by τ (Z + β ) as well. Hence the study of τ (Σ + β ) will provide additional inequalities satisfied by elements of T . First, we define for all n ∈ N * the real numbers

M ′ n (j) = max x∈Σ + β {|τ j (x)|, x < β n }, H ′ n (j) = M ′ n (j) 1 -|α j | n and H ′ (j) = sup x∈Σ + β |τ j (x)|.
Similarly as in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], we obtain using the triangle inequality the following property.

Lemma 3.3 For all x ∈ Z β , |τ j (x)| < H ′ n (j) and |τ j (x) -2p Hj ( - → C )| < H ′ n (j).
Proof: The first assertion is deduced from Proposition 3.1, whereas the second assertion is a consequence of S-→ C (T ) ⊂ T ′ . ✷ Note that, since H ′ (j) ≥ H(j), the first inequality of Lemma 3.3 is a weaker condition than the inequality of Proposition 3.1. However, it is more convenient to compute H ′ (j), since the definitions of H ′ n (j) and H ′ (j) do not use the admissibility condition on words. We obtain additional algebraic inequalities, satisfied by finite β-fractional parts of the sums of two β-integers, thanks to the following proposition. Proposition 3.4 Let x, y ∈ Z + β with x ≥ y. If x + y ∈ Fin(β), then:

1. |τ j ({x + y} β ) -2p Hj ( - → C )| < 3H ′ (j); 2. |τ j ({x + y} β )| < (2 + |α j |)H(j).
If x -y ∈ Fin(β), then:

1. |τ j ({x -y} β ) + 2p Hj ( - → C )| < 3H ′ (j); 2. |τ j ({x -y} β )| < (2 + |α j |)H(j).
Proof: First, let us consider the case of addition of positive β-integers. Let x, y ∈ Z + β such that x + y ∈ Fin(β). The first assertion is a consequence of Lemma 3.3, using the fact that, since x, y and [x + y] β are β-integers, we get

|τ j (x) -2p Hj ( - → C )| < H ′ (j), |τ j (y) -2p Hj ( - → C )| < H ′ (j) and |τ j ([x + y] β ) -2p Hj ( - → C )| < H ′ (j).
Let us prove the second assertion. If 0 is a suffix of the expansion of either x, y, or [x + y] β , then one of these three β-integers, say x, satisfies |τ j (x)| < |α j |H(j), which improves the inequality of the first assertion. On the other hand, suppose that none of the β-expansions of x, y and [x + y] β admits 0 as a suffix. Denote respectively by x 0 , y 0 and z 0 the suffixes of x, y and [x + y] β . Then, one of the following nonnegative β-integers x ′ = x -min{x 0 , y 0 }, y ′ = y -min{x 0 , y 0 } or z ′ = y -min{x 0 , y 0 } admits 0 as a suffix, and both x ′ + y = z ′ + {x + y} β and x + y ′ = z ′ + {x + y} β hold. Among the β-integers x, x ′ , y, y ′ , one of them belongs to βZ + β . This proves that there exist x ′ , y ′ ∈ Z + β , with either x ′ or y ′ ∈ βZ + β , such that {x + y} β = {x ′ + y ′ } β , hence |τ j ({x + y} β )| < (2 + |α j |)H(j). The case of the subtraction of two positive β-integers is handled in the same way. ✷

These relations improve those found in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF]. We obtain Proposition 3.5 in a similar way, which enables the computation of L ⊕ in Section 3.2 for several cases of cubic Pisot units.

Remark 7 Proposition 3.4 means that 3H ′ (j) and (2 + |α j |)H(j) are both upper bounds for |τ j ({x + y} β )| when x and y are β-integers such that [x + y] β ∈ Fin(β). When β is a confluent Parry number, H(j) = H ′ (j), which means that (2 + |α j |)H(j) provides a better upper bound for |τ j ({x+y} β )| than 3H ′ (j). However, when β is the positive root of the polynomial X 3 -X 2 -1, we check by pure computation that 3H ′ (j) < (2 + |α j |)H(j). Hence, in the general case of Pisot numbers, we do not know which of the two upper bounds 3H ′ (j) and (2+|α j |)H(j) for |τ j ({x+y} β )| is better than the other one.

The following proposition is an improvement of Proposition 3.4, in the sense that it sums up the inequalities concerning the elements of T . In particular, we obtain as a result an accurate covering of T by balls having arbitrarily small positive radius. As a consequence, we construct the algorithm A described in Section 3.2, which computes a set of admissible words whose β-fractional parts are of a bounded length. This set contains the finite β-fractional parts of sums of two positive β-integers.

| k<0 ν k α k j + N -1 k=0 (ν k -ε k -δ k )α k j -α N j p Hj ( - → C )| < 3H ′ (j)(1 + |α j |) 2 |α j | N .
Proof: First, we know due to Lemma 2.3 that -→ C is the center of the centrally symmetric set T ′ , with p Hj (

- → C ) = [β] 2(1-αj ) = k≥0 [β]
2 α k j for all j ∈ J.

Let x, y ∈ Z + β such that {x + y} β ∈ Fin(β). Let (ε k ) k∈Z , (δ k ) k∈Z and (ν k ) k∈Z respectively be the β-expansion of x, y and x + y. We remind that, by hypothesis, ε k = δ k = 0 for all k < 0, and that (ε k -δ k -ν k ) k∈Z consists of only finitely many non-zeros elements. Since {x + y} β + [x + y] β -x -y = 0, one gets for all N ∈ N * :

k<0 ν k α k j + N -1 k=0 (ν k -ε k -δ k )α k j = - k≥N (ν k -ε k -δ k )α k j = -α N j k∈N (ν k+N -ε k+N -δ k+N )α k j .
Since for all j ∈ J, one has p Hj (

- → C ) = k∈N [β] 2 α k j = [β]
2(1-αj ) , we obtain:

k≥N (ν k -ε k -δ k )α k j = α N j k∈N (ν k+N -ε k+N -δ k+N + [β] 2 )α k j -p Hj ( - → C ) . Moreover, ν k+N -ε k+N -δ k+N + [β] 2 ∈ [-3 [β] 2 , 3 [β] 2 ] for all k ∈ N. Hence | k<0 ν k α k j + N -1 k=0 (ν k -ε k -δ k )α k j -α N j p Hj ( - → C )| < 3 2 |α j | N R, where R = sup{| k∈N v k α k j |, (v k ) k∈N ∈ [-[β], [β]] N }. Since { k∈N v k α k j , (v k ) k∈N ∈ [-[β], [β]
] N } is a convex set, and using a similar argument as in the proof of Proposition 3.4, we get:

R = max x ′ ,y ′ ∈Σ + β |τ j (x ′ -y ′ )| ≤ (1 + |α j |)H ′ (j).
✷ Note that we do not use the admissibility in the proof of Propositions 3.4 and 3.5. This means that, whereas we are looking for inequalities concerning elements which belong to T , these inequalities hold in fact for elements of T ′ .

The relation given by Proposition 3.5 produces a good approximation of T ′ , in the sense that it enables an accurate covering of T ′ with balls having arbitrarily small positive radius. More precisely, the coordinates on H j of the centers of these balls are

N -1 k=0 (ν k -ε k -δ k )α k j -p Hj ( - → C )
when ν, ε and δ describe the set of admissible words of length N , and their radii are 3 2 |α j | N R. It could be possible that the set T is only a "small" subset of T ′ . In this case, the inequality satisfied by elements of T in Proposition 3.5 is not accurate enough, and we need to improve the relation satisfied by elements of T in order to compute the exact value of L ⊕ , or at least a better upper bound for L ⊕ than those given by Proposition 3.2. Note that the class of confluent Parry numbers is in some sense optimal, since T = T ′ corresponds to the case where a good approximation of T ′ is a good approximation of T as well.

Algorithmic computation of L ⊕ in several cubic Pisot cases

In this section, we are interested in the set of finite β-fractional parts that are obtained when one sums two positive β-integers. We introduce L + ⊕ as the maximal length of the finite β-fractional parts of the sum of two positive β-integers. Note that L ⊕ , the maximal length of the finite βfractional parts of the sum of two β-integers, can also be defined as the maximal length of the finite β-fractional parts that we obtain after adding or subtracting two positive β-integers. Hence, if one can both compute L + ⊕ and the maximal length of the finite β-fractional parts of the difference of two positive β-integers, we deduce the value of L ⊕ . β , and it represents an element of [0, 1[. In order to obtain a better upper bound for L ⊕ than those computed in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], we define the following algorithm A.

Let

1. We set for B an upper bound for L ⊕ , for instance the upper bound computed in Proposition 3.2, and we set N = 1.

2. We check whether there exists words v = v B . . . v 1 ∈ L β and w = w 0 . . . w N -1 in L ′ β such that the inequality given by Proposition 3.5 holds, that is, if we have for all j ∈ J

| B k=1 v k α -k j + N -1 k=0 w k α k j -α N j p j ( - → C )| < 3H ′ (j)(1 + |α j |) 2 |α| N . (3)
3. When (3) is satisfied for no v ∈ L β and no w ∈ L ′ β , we decrease by 1 the value of B, we set N = 1 and we return to point 2.

4. When there exists v ∈ L β and w ∈ L ′ β such that (3) holds, we increase by 1 the value of N and we return to point 2.

Since B ∈ N, there eventually exists an admissible word v such that (3) is satisfied for any w ∈ L ′ β . This algorithm lowers the value of B, that is, it provides a better upper bound for L + ⊕ . However, we cannot check if this algorithm computes the value of L + ⊕ . Additionally, even if the algorithm computes the exact value of L + ⊕ after finitely many steps, we do not known when the exact value of L + ⊕ is reached. In this case, it suffices then to find two β-integers x and y such that d β (x + y) has a fractional part of the required length to deduce the exact value of L + ⊕ . We finally perform the same computations for the case of the difference of two positive β-integers in order to obtain L ⊕ .

Let us focus now on the case of cubic Pisot numbers. Let β be the positive root of the polynomial P

(X) = X 3 -k 1 X 2 -k 2 X -1, where k 1 , k 2 ∈ N 2 satisfy k 1 ≥ max{1, k 2 }.
Suppose moreover that P has two complex conjugate roots, that we denote by α and α. For k 2 large enough, this condition is satisfied when k 2 ≤ 2 √ k 1 , and is not satisfied otherwise. Due to [START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF], we know that the finiteness property (F) holds in this case. It is also proved in this article that, when β is a Pisot unit which satisfies (F), then 0 is an inner point of T . Hence K = min We deduce that x 1 + y 1 = z 1 + β -1 + β -5 + β -6 , hence the 3-uple (x 1 , y 1 , z 1 ) belongs to S 6 . However, l i (z 1 ) ≤ l i (z 0 ) -3, which contradicts the minimality of l i (z 0 ). Hence S 6 is empty, and L + ⊕ < 6. ✷ Theorem 3.9 When d β (1) = 0.111, then L ⊕ = 5.

Proof: Proposition 3.8 proves that L + ⊕ = 5. In order to obtain the result on Z β instead of Z + β , it suffices to note that, since Z β = ±Z + β , we can suppose that x + y > 0, thus [x + y] β ∈ Z + β without loss of generality. Moreover, if x + y > 0, then x or y is positive, and the case where they are both positive is exactly the case previously studied. Thus, we only have to check whether there exist x, -y ∈ Z + β , x -y > 0 such that l f (x -y) = 6. However, we check by an exhaustive computation that there exists N ∈ N for which the inequality (3) used in the algorithm A does not hold for any admissible word v of length 6. Since L ⊕ ≥ 5, this proves that L ⊕ = L + ⊕ = 5. ✷ Remark 8 Let us explain why the algorithm A described in Section 3.2 does not improve the relation 5 ≤ L ⊕ ≤ 6 given by [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF] in the Tribonacci case. This is due to the fact that the inequality provided by Proposition 3.5, a priori satisfied by images under τ j of β-integers, also extends to elements of T . For instance, the complex number 1 1-α 3 belong to T , since it is the limit of the sequence ( n k=0 α 3k ) n∈N , which consists of images of β-integers under τ . Hence 1 1-α 3 + 1 1-α 3 = 2 1-α 3 is the sum of two elements which belong to T . Moreover, 2 1-α 3 is the limit of the sequence (( n k=0 α 3k+1 + α 3k+2 ) + α -1 + α -5 + α -6 ) n∈N , which consists of images of elements of Fin(β), having β -1 + β -5 + β -6 as β-fractional part, under τ . This means that, whereas there do not exist x, y ∈ Z β such that {x + y} β = β -1 + β -5 + β -6 , there exists a complex number, namely It would be interesting to compute the value of L ⊙ for the Tribonacci case. Due to [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF], we know that 4 ≤ L ⊙ ≤ 5. Similarly as in the case of addition, one checks by pure computation that there exists only one real number x such that l f (x) = 5, namely x = β -1 + β -3 + β -5 , which could be the β-fractional part of the product of two β-integers. We do not know whether there exist two β-integers x and y such that {xy} β = β -1 + β -3 + β -5 ; nevertheless we find that the complex numbers 1+α 1-α 3 , 1 1-α 3 and α 2 1-α 3 belong to T with 1+α 1-α 3 . 1 1-α 3 = α 2 1-α 3 + α -1 + α -3 + α -5 . Hence there exists an α-expansion of 1+α 1-α 3 . 1 1-α 3 , the product of two elements which belong to T , which admits an α-fractional part whose fractional part is α -1 + α -3 + α -5 . However, these informations are not sufficient to determine whether there exist x, y ∈ Z β such that {xy} β = β -1 + β -3 + β -5 .

Definition 1 . 1

 11 The set {τ (x), x ∈ Z + β } is called Rauzy fractal or central tile, denoted by T . Note that a Rauzy fractal is a compact set by definition, since it is a bounded set.

Fig. 1 :

 1 Fig. 1: Rauzy fractal T defined by d β (1) = 0.111

Proposition 2 . 6

 26 Let β be a confluent Parry number. If either k 1 or k 1 -k d is even, then -→ C ∈ T .

Fig. 2 :

 2 Fig. 2: T defined by d β (1) = 0.101 Fig. 3: T ′ defined by d β (1) = 0.101

Proposition 3 . 5

 35 Let x, y ∈ Z + β with x > y, x = k∈N ε k β k and y = k∈N δ k β k . Suppose that x + y ∈ Fin(β). Let (ν k ) k∈Z be the β-expansion of x + y. Then, for all N ∈ N * :

  L ′ β be the set which consists of words (ν k -ε k -δ k ) k∈[[1,...,n]] , where the words (ν k ) k∈[[1,...,n]] , (ε k ) k∈[[1,...,n]] and (δ k ) k∈[[1,...,n]] belong to L β . Note that the words of L ′ β are defined on the alphabet [[-2[β], . . . , [β]]]. Let x, y ∈ Z + β . Then the expansion in base β of x + y -[x + y] β constructed digit by digit belongs to L ′

  )| > 0, and the required conditions of Proposition 3.2 hold for the class of Parry numbers we consider. We respectively denote byL ⊕ (k 1 , k 2 ) and L + ⊕ (k 1 , k 2 ) the value of L ⊕ and L +⊕ for the associated numeration system, defined byd β (1) = 0.k 1 k 2 1. Proposition 3.6 The algorithm A computes L ⊕ (k 1 , k 2 ) when k 1 ≤ 3. We get: 1. L ⊕ (1, 0) = 11 and L + ⊕ (1, 0) = 10, 2. L ⊕ (1, 1) ≤ 6, 3. L ⊕ (2, 0) = L + ⊕ (2, 0) = 7,4. L ⊕ (2, 1) = 5 and L + ⊕ (2, 1) = 4, 5. L ⊕ (2, 2) = L + ⊕ (2, 2) = 5.

2 1 -

 1 α 3 , which is the sum of two elements of T and admits an α-expansion whose fractional part is of length 6. For any x ∈ Fin(β) [0, 1[, let d β (x) = 0.v and T .v = τ ({y ∈ Fin(β), {y} β = x}). Due to Messaoudi [27], the fact that the complex numbers 2 1-α 3 and 1 1-α 3 both have three α-expansions means that they belong to the fractal boundary of three different tiles T .x . By computation, one gets { 2 1-α 3 } ⊂ T .100011 ∩ T .001 ∩ T .011 and { 1 1-α 3 } ⊂ T ∩ T .001 ∩ T .011 . Figure 4 gives a geometrical representation of these relations.

Fig. 4 :

 4 Fig. 4: Tiles T , T.011, T.001 and T.100011

  . . . . . . . . k m

	1	0 . . . . . . . . . 0
	0	. . .	. . .			. . .
	. . .	. . .	. . .	. . .		0
	. . .		. . .	. . .	. . .	. . .
	0 . . . . . . 0	1	0

Acknowledgements

I am indebted to Valérie Berthé and Pierre Arnoux for their advices and corrections. I also thank Julien Cassaigne, Petr Ambrož, Zuzana Másáková, Edita Pelantová, Shigeki Akiyama and Anne Siegel for many interesting talks, remarks and ideas developed in this paper. I strongly thank the referees for their valuable comments and corrections.

Note that the inequality L ⊕ (1, 1) ≤ 6 was already known, see [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF].

Example 2 When d β (1) = 0.101, one has

From a practical point of view, we noticed that, except in the Tribonacci case, the algorithm A computes L ⊕ (k 1 , k 2 ) in a finite number of steps for any example of a pair (k 1 , k 2 ) among those that satisfy the needed conditions, that is, for which β is the positive root of the polynomial X 3 -k 1 X 2 -k 2 X -1 and admits two complex Galois conjugates.

The particular case of Tribonacci

We end our study by the Tribonacci case, that is, β is the real root of the polynomial X 3 -X 2 -X -1. Since β admits two complex Galois conjugates, we set from now on α = α 1 and τ = τ 1 . Note that this definition of τ coincides with the previous definition of τ given in Section 1.4. The previous method does not allow us to determine the exact value of L ⊕ (1, 1), since the admissible word 100011, which represents the β-fractional part β -1 + β -5 + β -6 is not discarded by the algorithm described in Section 3.2. Hence we do not know whether there exist two β-integers x and y such that {x + y} β = β -1 + β -5 + β -6 . This explains why the particular case of Tribonacci needs additional computations.

We prove in this section that L ⊕ (1, 1) = 5, thanks to the following lemma.

Lemma 3.7 Let β be the Tribonacci number, that is, d β (1) = 0.111. Suppose that there exist x, y ∈ Z + β such that l f (x + y) = 6. Then, we have:

2. the real numbers x-1 β 3 , y-1 β 3 and

are β-integers.

Proof: The first assertion is a consequence of Proposition 3.6, since we prove by pure computation that the relation (3) only holds for v an admissible word of length 6, namely when v = 100011. Additionally, we obtain only one possibility for the suffix of length 3 of w ∈ L ′ β , which is (-1)(-1)2. This suffix corresponds to the suffix of length 3 of the expansion in base β of x + y -[x + y] β constructed digit by digit. This implies that the β-expansions of the β-integers x, y and [x + y] β must respectively admit 001, 001 and 110 as suffixes, which proves the second assertion. ✷ Proposition 3.8 When d β (1) = 0.111, then L + ⊕ = 5.

Proof: Suppose that there exist x 0 and y 0 ∈ Z + β such that {x 0 + y 0 } β = β -1 + β -5 + β -6 . This means that the set

} is not empty. Let z 0 = [x 0 + y 0 ] β . Let (x 0 , y 0 , z 0 ) ∈ S 6 such that l i (z 0 ), the length of the β-fractional part of z 0 , is minimal. Due to Lemma 3.7, there exists (x 1 , y 1 , z 1 ) ∈ (Z + β ) 3 such that x 0 = 1 + β 3 x 1 , y 0 = 1 + β 3 y 1 and z 0 = β + β 2 + β 3 z 1 . Thus, we get: