Petr Ambrož

Zuzana Masáková

Edita Pelantová

Addition and multiplication of beta-expansions in generalized Tribonacci base

Keywords: beta-expansion, numeration system, Pisot number

We study properties of β-numeration systems, where β > 1 is the real root of the polynomial x 3 -mx 2x-1, m ∈ N, m ≥ 1. We consider arithmetic operations on the set of β-integers, i.e., on the set of numbers whose greedy expansion in base β has no fractional part. We show that the number of fractional digits arising under addition of β-integers is at most 5 for m ≥ 3 and 6 for m = 2, whereas under multiplication it is at most 6 for all m ≥ 2. We thus generalize the results known for Tribonacci numeration system, i.e., for m = 1. We summarize the combinatorial properties of infinite words naturally defined by β-integers. We point out the differences between the structure of β-integers in cases m = 1 and m ≥ 2.

Introduction

In this paper we study the properties of a non-standard numeration system related to an irrational base β for a class of cubic numbers β.

The definition of a numeration system based on a real number β > 1 is given by the fact that every non-negative x has a unique expression in the form of its β-expansion,

x = k i=-∞ a i β i , (1)
where the coefficients a i are non-negative integers and

0 ≤ x - k i=n a i β i < β n for all n ∈ Z, n ≤ k. (2)
A real number x for which the β-expansion of |x| is of the form |x| = k i=0 a i β i is called a β-integer. The set of β-integers is denoted by Z β . We say that a real x has a finite β-expansion, if x is an element of the set

Fin(β) := ∞ n=0 1 β n Z β .
(3)

1365-8050 c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

If β = 10, then the β-expansion of x is the ordinary decimal expansion of x and Z β = Z. An equality Z β = Z holds for every rational integer β ∈ Z, β > 1.

If β / ∈ Z, the condition (2) implies that the coefficients a i of the β-expansion satisfy a i ∈ {0, 1, . . . , ⌊β⌋} for all i ≤ k. However, not all power series with such coefficients corresponds to a β-expansion of some real x. For the characterization of admissible sequences of coefficients one needs to introduce the so-called Rényi expansion of 1,

d β (1) = t 1 t 2 t 3 • • • , where t 1 = ⌊β⌋ and ∞ n=2 t n β n is the β-expansion of 1 - t 1 β . (4)
A number β, for which d β (1) is eventually periodic is called a Parry number. If moreover d β (1) = t 1 t 2 t 3 • • • has only a finite number of non-zero entries t i , then β is called a simple Parry number and the vanishing coefficients at the end of d β (1) are omitted. Expansions of β-integers are characterized by the Parry condition [START_REF] Parry | On the β-expansions of real numbers[END_REF]: k i=0 a i β i with a i ∈ {0, 1, 2, . . . } is a β-expansion of some x > 0 if and only if a i a i-1 • • • a 0 ≺ t 1 t 2 t 3 • • •, i.e., a i a i-1 • • • a 0 is lexicographically strictly smaller than t 1 t 2 t 3 • • • for any i = k, k -1, . . . , 0.

Unlike numeration systems with an integer base, the set Z β of β-integers is not closed under addition and multiplication if β / ∈ Z. However, this does not exclude that Fin(β) is a ring. A necessary condition so that Fin(β) is closed under addition and multiplication is that β is a Pisot-Vijayaraghavan (PV) number and a simple Parry number [START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF][START_REF] Frougny | Finite beta-expansions[END_REF]. Recall that PV numbers are defined as real algebraic integers greater than 1 such that their conjugates are inside the unit complex circle. It is known that every PV number is a Parry number.

Some sufficient conditions on a simple Parry number β so that Fin(β) is a ring are also known (i) . In [START_REF] Frougny | Finite beta-expansions[END_REF] it is shown that if

d β (1) = t 1 t 2 • • • t m satisfies t 1 ≥ t 2 ≥ • • • ≥ t m > 0 then Fin(β) is a ring. Hollander [Hol96] has shown that t 1 > t 2 + t 3 + • • • t m is
a sufficient condition so that Fin(β) is a ring. For cubic PV units β Akiyama [START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF] has shown that Fin(β) is a ring if and only if β is a simple Parry number, i.e., d β (1) is finite. A weaker form of the condition (F) is the so-called weak finiteness property, studied in [START_REF] Akiyama | A certain finiteness property of Pisot number systems[END_REF].

For performing the arithmetic operations in the numeration system based on β it is important not only to know that the result has a finite fractional part, but to know the length of the fractional part. We therefore study the quantities

L ⊕ = L ⊕ (β) := min{n ∈ N 0 | ∀ x, y ∈ Z β , x + y ∈ Fin(β) ⇒ x + y ∈ β -n Z β } , (5)
L ⊗ = L ⊗ (β) := min{n ∈ N 0 | ∀ x, y ∈ Z β , xy ∈ Fin(β) ⇒ xy ∈ β -n Z β } . (6)
In [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF] it is shown that for β a PV number, one has L ⊕ < +∞. In [START_REF] Guimond | Arithmetics of beta-expansions[END_REF] the same result is given for L ⊗ . First known values for L ⊕ , L ⊗ have been provided in [START_REF] Burdík | Betaintegers as natural counting systems for quasicrystals[END_REF] for quadratic PV units. Article [START_REF] Guimond | Arithmetics of beta-expansions[END_REF] states exact values and estimates on L ⊕ , L ⊗ for arbitrary quadratic PV numbers. The first cubic case was studied by Messaoudi. In [START_REF] Messaoudi | Généralisation de la multiplication de Fibonacci[END_REF] he shows for the so-called Tribonacci numeration system, i.e., for the base β with minimal polynomial x 3 -x 2 -x -1, that L ⊗ ≤ 9, and states the conjecture of Arnoux that L ⊗ = 3. In [START_REF] Messaoudi | Tribonacci multiplication[END_REF] he improves the upper (i) We say that the number β has Property (F) if the set Fin(β) is a ring bound to L ⊗ ≤ 6. In [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF] it is shown that 4 ≤ L ⊗ ≤ 5 and 5 ≤ L ⊕ ≤ 6. Final exact value L ⊕ = 5 has been given with an elegant proof by Bernat [START_REF] Bernat | Propriétés arithmétiques de la β-numération[END_REF].

In this paper we study a class of cubic units β > 1, roots of

x 3 = mx 2 + x + 1 , m ∈ N . (7)
We call such base β the generalized Tribonacci number, since the Tribonacci case is obtained for m = 1. The equation x 3 = mx 2 + x + 1 has a unique real solution β. It satisfies m < β < m + 1. The other two roots β ′ and β ′′ are mutually complex conjugates

|β ′ | = |β ′′ | < 1. Obviously, we have ββ ′ β ′′ = 1 , β + β ′ + β ′′ = m . (8)
The Rényi expansion of 1 is d β (1) = m11. Therefore the digits in a β-expansion take values in {0, 1, . . . , m} and the Parry condition implies for a 0 , a 1 , . . . , a k ∈ N 0 that

k i=0 a i β i is a β-expansion ⇐⇒ a i a i-1 a i-2 ≺ m11 for all i = 2, 3, . . . , k . (9)
Due to the results of Frougny and Solomyak [START_REF] Frougny | Finite beta-expansions[END_REF] or Akiyama [START_REF] Akiyama | Self affine tiling and Pisot numeration system[END_REF] the set Fin(β) is a ring for all m.

Our aim is to provide estimates on the quantities L ⊕ (β), L ⊗ (β) for these generalized Tribonacci numbers β. Since the Tribonacci case m = 1 has been already solved, we consider m ≥ 2.

Lower bounds on L ⊕ (β), L ⊗ (β) can be clearly obtained as the length of the fractional part of the sum, respectively product of some elements x, y ∈ Z β .

Proposition 1 Let β be the real root of

x 3 = mx 2 + x + 1. Then L ⊕ (β) ≥    5 for m = 2 , 4 for m ≥ 3 , L ⊗ (β) ≥ 4 for m ≥ 2 . ( 10
)
Proof: We have for m = 2,

(β 4 + β 2 + 2β) -(β 3 + 2) = 2β 3 + 2 + β -3 + β -4 + β -5 , (11) 2
× (β 6 + 2β 5 + 2β 3 + β 2 + 2) = β 7 + β 6 + 2β 4 + 2β + β -2 + 2β -3 + β -4 , (12)
and for m ≥ 3,

(mβ 3 + m) + (mβ 3 + m) = 2 × (mβ 3 + m) = = β 4 + (m -1)β 3 + (m -1)β 2 + 2β + + (m -3)β -1 + (m -1)β -2 + 2β -3 + β -4 . (13)

✷

The main result of this paper is providing the upper bounds on L ⊕ (β) and L ⊗ (β). Using a specific method of estimation, which will be explained in the next section, we obtain 5 ≤ L ⊕ ≤ 6, for m = 2, and 4 ≤ L ⊕ ≤ 5, for m ≥ 3, (Theorem 4). Let us mention that for two special m the exact value of L ⊕ (β) is known [START_REF] Bernat | Propriétés arithmétiques de la β-numération[END_REF], namely for m = 2 is L ⊕ (β) = 5 and for m = 3 is L ⊕ (β) = 4. Further, we study L ⊗ (β). We establish 4 ≤ L ⊗ ≤ 6 for m ≥ 2, (Theorem 5). Note that the exact value of L ⊗ (β) is not known even in Tribonacci case m = 1.

The proofs of Theorems 4 and 5 use real quadratic forms and their differences. It is noteworthy that the similar computation was the bottleneck of [START_REF] Akiyama | A self-similar tiling generated by the minimal Pisot number[END_REF] and [START_REF] Gjini | A self-similar tiling generated by the Pisot number which is the root of the equation x 3 -x 2 -1 = 0[END_REF] in studying topology of Thurston-Rauzy fractals associated with β-expansions.

Although we study the numeration systems mainly from the arithmetical point of view, its combinatorial properties are also very interesting. At the end of the paper we present some combinatorial properties of the set of β-integers which can be derived from general results in the literature for the class of generalized Tribonacci numbers.

2 Methods of upper estimation of L ⊕ (β), L ⊗ (β)

Let us present the methods for finding upper estimates of L ⊕ , L ⊗ and the one chosen for the class of generalized Tribonacci numbers explain in detail. Two methods for estimation of L ⊕ , L ⊗ are known. First of them uses the so-called Meyer property of the set of β-integers, namely that

Z β + Z β ⊂ Z β + F for a finite set F . (14)
In [START_REF] Akiyama | Automata for arithmetic Meyer sets[END_REF] one studies the question of minimizing the finite set F . For multiplication, one has a similar property [START_REF] Guimond | Arithmetics of beta-expansions[END_REF]: If β is a PV number, then

Z β • Z β ⊂ Z β + G for a finite set G . ( 15
)
This method is used in [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF] to find values of L ⊕ (β), L ⊗ (β) where β is a PV number, solution of the equation

x 3 = 25x 2 + 15x + 2.
The second much more used method for estimation of L ⊕ , L ⊗ is based on the following theorem. Several versions of this method are employed in [AFMP03, Ber05, GMP04, Mes00, Mes02].

Theorem 2 ([GMP04]) Let β > 1 be an algebraic number, and let β ′ be its conjugate. For z ∈ Q β we denote by z ′ the image of z under the field isomorphism

′ : Q(β) → Q(β ′ ). If H := sup |z ′ | z ∈ Z β < +∞ , (16)
K := inf |z ′ | z ∈ Z β \ βZ β > 0 , ( 17
)
then 1 |β ′ | L⊕ < 2H K and 1 |β ′ | L⊗ < H 2 K . ( 18
)
In the above theorem we require existence of at least one conjugate of β such that the constant H is finite and K is positive. The former is ensured if |β ′ | < 1. To decide whether K > 0 or K = 0 is much more complicated. In the paper [START_REF] Ambrož | Arithmetics on number systems with irrational bases[END_REF] there is given a sufficient condition for a number β so that K = 0. An example for such number β is the already mentioned solution of the equation x 3 = 25x 2 + 15x + 2. Indeed, for such β one cannot employ Theorem 2. A sufficient condition for β so that K > 0 was given by Akiyama [START_REF] Akiyama | Cubic Pisot units with finite beta expansions[END_REF]. Akiyama proved that for β PV unit such that Fin(β) is a ring, the origin is an inner point of the central tile in the conjugated plane, i.e., of the closure of the set {z ′ | z ∈ Z β }. This implies K is positive for all conjugates of β. In such a case one chooses the conjugate which provides the best estimates on L ⊕ , L ⊗ .

Our aim is to provide estimates on the quantities L ⊕ (β), L ⊗ (β) for the generalized Tribonacci numbers β. We use the method based on Theorem 2. Recall that one has to choose a suitable conjugate of β. However, in the case of generalized Tribonacci numbers, both conjugates of β have the same modulus < 1, and thus both of them will provide the same values of constants H, K. Moreover, since β is a cubic PV unit with finite Rényi expansion of 1, set Fin(β) is a ring and therefore constant K in Theorem 2 is positive.

It is a difficult problem to determine the exact values of H and K. However, in order to obtain bounds on L ⊕ and L ⊗ it suffices to find some "reasonable" upper estimate on H and lower estimate on K.

Upper estimate on H. For a given p ∈ N, every z ∈ Z β can be written as

z = (a 0 + a 1 β + • • • + a p-1 β p-1 ) + β p (a p + • • • + a 2p-1 β p-1 ) + . . . , (19)
with the integer coefficients satisfying the admissibility condition a i a i-1 a i-2 ≺ m11. Using triangular inequality, the modulus of the conjugate z ′ can be estimated by

|z ′ | ≤ 1 + |β ′ | p + |β ′ | 2p + . . . Max p = Max p 1 -|β ′ | p =: H p , (20)
where

Max p := max |z ′ | z ∈ Z β , |z| < β p . (21)
We therefore have

H ≤ H p for all p ∈ N. ( 22
)
Lower estimate on K. For a given p ∈ N, and for all z ∈ Z β we have

|z ′ | ≥ |a 0 + a 1 β + • • • + a p-1 β p-1 | -|β ′ | p |a p + a p+1 β ′ + . . . | . ( 23
)
Note that the last term on the right hand side is a modulus of a β-expansion of a conjugate of some x ∈ Z β and therefore it is bounded by H (or H q for some q ∈ N). With the notation

Min p := min |z ′ | z ∈ Z β \ βZ β , |z| < β p , (24)
we obtain an estimate

K ≥ K p,q := Min p -|β ′ | p H q for all p, q ∈ N. ( 25
)
We see that the problem of the upper bounds on L ⊕ and L ⊗ has been reduced to the problem of finding Max p and Min p for a suitable value of p. Recall from the definition of Max p and Min p (equations ( 21) and ( 24)) that both of them are calculated using the modulus |z ′ | of the image of β-integers |z| < β p under the field morphism. It turns more convenient to study the square of this quantity.

Let us consider a β-integer z, such that |z| < β p , i.e., z is of the form z = a 0 +a 1 β +a 2 β 2 +• • •+ a p-1 β p-1 , where the integer coefficients a i satisfy the admissibility condition a i a i-1 a i-2 ≺ m11. Since the conjugates of β are mutually complex conjugated we have

|z ′ | 2 = z ′ z ′′ = p-1 i=0 a i β ′ i p-1 j=0 a j β ′′ j = p-1 i=0 p-1 j=0 a i a j β ′ i β ′′ j . ( 26
)
We use the relation ββ ′ β ′′ = 1 to derive for j > i,

a i a j β ′ i β ′′ j + a j a i β ′ j β ′′ i = a i a j β ′ j-i 1 β i + a i a j β ′′ j-i 1 β i = a i a j β i 2ℜ(β ′ j-i ) . ( 27
)
Substituting this to the expression for |z ′ | 2 , we obtain

|z ′ | 2 = p-1 k=0 a 2 k β k + 0≤i<j≤p-1 a i a j β i 2ℜ(β ′ j-i ) . (28)
Therefore, |z ′ | 2 is a real quadratic form of integer variables a 0 , a 1 , . . . , a p-1 . In order to express it in a simpler form, we need to determine the coefficients 2ℜ(β ′ j-i ). Let us denote c k := 2ℜ(β ′ k ).

For calculation of c k we find a recurrent formula,

c k c 1 = (β ′k + β ′′k )(β ′ + β ′′ ) = β ′k+1 + β ′k β ′′ + β ′′k β ′ + β ′′k+1 = c k+1 + β ′ β ′′ (β ′k-1 + β ′′k-1 ) = c k+1 + 1 β c k-1 . (29)
Let us enumerate several initial coefficients,

c 0 = 2 , ( 30a
)
c 1 = - 1 β + 1 β 2 , (30b)
c 2 = - 2 β - 1 β 2 - 2 β 3 - 1 β 4 , (30c)
c 3 = 3 β 2 + 2 β 3 - 3 β 4 - 3 β 5 - 1 β 6 , (30d)
c 4 = 2 β 2 - 4 β 3 - 7 β 4 + 6 β 6 + 4 β 7 + 1 β 8 . ( 30e
)
Note that for m ≥ 3 the coefficients satisfy c 1 < 0, c 2 < 0, c 3 > 0 and c 4 > 0.

Our aim is to find Max p and Min q for suitable p, q so that the bounds on L ⊕ , L ⊗ obtained by Theorem 2 are best possible. Computer experiments show that optimal constants are H 3 , K 5,3 , that is to say the values of H n and K m,n change too little with increasing n, m and do not provide better estimates on the values of L ⊕ and L ⊗ . Thus we need to calculate Max 3 and Min 5 .

Since we are interested in Max 3 , the real quadratic form |z ′ | 2 to be examined simplifies to

Q 1 (a 2 , a 1 , a 0 ) := |z ′ | 2 = a 2 0 + a 2 1 β + a 2 2 β 2 + a 0 a 1 c 1 + a 0 a 2 c 2 + a 1 a 2 β c 1 . (31)
In order to calculate the value of Max 3 we have to find the maximum of the quadratic form Q 1 (a 2 , a 1 , a 0 ) on the set

S 1 := {(a 2 , a 1 , a 0 ) ∈ Z 3 | 0 ≤ a i ≤ m, a 2 a 1 a 0 ≺ m11} . (32)
Similarly, for calculation of Min 5 , we use the quadratic form

Q 2 (a 4 , a 3 , a 2 , a 1 , a 0 ) := |z ′ | 2 = a 2 0 + a 2 1 β + a 2 2 β 2 + a 2 3 β 3 + a 2 4 β 4 + a 0 a 1 c 1 + a 0 a 2 c 2 + + a 0 a 3 c 3 + a 0 a 4 c 4 + a 1 a 2 β c 1 + a 1 a 3 β c 2 + a 1 a 4 β c 3 + a 2 a 3 β 2 c 1 + a 2 a 4 β 2 c 2 + a 3 a 4 β 3 c 1 . ( 33
)
We have to find a minimum of this quadratic form on the set

S := {(a 4 , a 3 , a 2 , a 1 , a 0 ) ∈ Z 5 | m ≥ a i ≥ 0, a 0 > 0 and a k+2 a k+1 a k ≺ m11} . (34)
The condition a 0 = 0 in the definition of set S corresponds to the condition z ∈ Z β \ βZ β in the definition of Min p .

For finding the extremal values of the quadratic forms, we inspect the first differences of the quadratic form for each variable a i , each time fixing all yet appointed values of the variables. The difference in a variable a i will be denoted ∆ ai := Q(. . . , a i + 1, . . . ) -Q(. . . , a i , . . . ) ,

where a i ≤ m -1 and the variables a j , j = i take values at most m. Using this method we further prove the following result.

Proposition 3 Let β > 1 be the real root of the equation

x 3 = mx 2 + x + 1 for m ∈ N, m ≥ 2. Then Max 3 = max |z ′ | z ∈ Z β , |z| < β 3 = m , (36)
Min 5 = min |z ′ | z ∈ Z β \ βZ β , |z| < β 5 =    β -2 (β + 1) for m ≥ 3 |1 + 2β ′ 2 + 2β ′ 4 | for m = 2 . ( 37
)
Since the proof of this proposition mainly consists of a rather technical analysis of the behavior of the quadratic forms Q 1 , Q 2 , we postpone it to a separate Section 4.

The main result

In the preceding sections we have found the values of Max 3 and Min 5 . According to the definitions (20) and (25) we have for m ≥ 3,

H 3 = Max 3 1 -|β ′ | 3 = mβ 3/2 β 3/2 -1 (38) and K 5,3 = Min 5 -|β ′ | 5 H 3 = β + 1 β 2 - m β(β 3/2 -1) . (39)
Now, we will use these values to obtain upper estimates on the value of L ⊕ .

Theorem 4 Let β > 1 be the real root of the equation

x 3 = mx 2 + x + 1 for m ∈ N. Then 4 ≤ L ⊕ (β) ≤ 5 for m ≥ 3 , ( 40
) 5 ≤ L ⊕ (β) ≤ 6 for m = 2 . ( 41
)
Proof: The upper bound L ⊕ ≤ 6 for m = 2 can be easily checked numerically. Since

2H K < 2H 3 K 5,3 ≃ 18.4596 < 1 |β ′ | 7 ≃ 26.3628 , (42)
according to the Theorem 2 we have L ⊕ ≤ 6.

Let us assume m ≥ 3. Again according to the Theorem 2 we have

1 |β ′ | L⊕ < 2H K ≤ 2H 3 K 5,3 . (43)
We will prove the inequality

2H 3 K 5,3 = 2mβ 3/2 β 3/2 -1 1 β+1 β 2 - m β(β 3/2 -1) < β 3 = 1 |β ′ | 6 , (44)
which implies L ⊕ ≤ 5. After a few simple operations the inequality (44) is transformed into

2mβ 1/2 + mβ < (β + 1)(β 3/2 -1) . (45)
For m ≥ 4 the proof of the inequality (45) will be based on the fact that β > β 1/2 + 2, which holds since

β > β 1/2 + 2 ⇔ (β -2) 2 > β ⇔ mβ + 1 + 1 β -4β + 4 > β . (46)
Now we estimate the left hand side of (45)

mβ 1/2 (2 + β 1/2 ) < β 1/2 mβ < β 1/2 mβ + 1 β = β 1/2 (β 2 -1) = = β 1/2 (β -1)(β + 1) = (β + 1)(β 3/2 -β 1/2 ) < (β + 1)(β 3/2 -1) , (47)
which proves (45).

In the omitted case m = 3, the inequality (45) can be proved directly. ✷

The following theorem yields the main result for multiplication -the estimates of the value of the coefficient L ⊗ .

Theorem 5 Let β > 1 be the real root of the equation

x 3 = mx 2 + x + 1 for m ∈ N, m ≥ 2. Then 4 ≤ L ⊗ (β) ≤ 6 . ( 48
)
Proof: Let us assume m ≥ 3. According to the Theorem 2 it suffices to show

H 2 K ≤ H 2 3 K 5,3 = m2 (1 -β -3/2 ) 2 1 β+1 β 2 -β -5/2 m 1-β -3/2 < 1 |β ′ | 7 , ( 49
)
which can be transformed into

(1 + m)β 3 + β 2 + (m + 2)β + 1 > (m + 2)β + m 2 + 2 β 3/2 . ( 50
)
By m ≤ β < m + 1 we can estimate the left hand side of (50) as

(1 + m)β 3 + β 2 + (m + 2)β + 1 ≥ (1 + m)m 3 + m 2 + (m + 2)m + 1 ≥ m 3 (1 + m) + m 2 , ( 51
)
whereas the right hand side as

(m + 2)β + m 2 + 2 β 3/2 < ((m + 2)(m + 1) + m 2 + 2)(m + 1) 3/2 ≤ 3m 2 (m + 1) 3/2 , ( 52
)
where the last inequality holds for m ≥ 4. The omitted cases will be treated separately at the end of the proof.

Using last two estimates we have

3m 2 (m + 1) 3/2 ≤ m 2 + m 3 (1 + m) . ( 53
)
It is easy to check that this inequality holds for m ≥ 10. Since our estimates were too rough to check the validity of (50) for m ≤ 9, we verified the proposition numerically for these cases as well as for the case m = 2 which was omitted at the beginning of the proof. ✷

Let us mention that computer experiments support the hypothesis that L ⊗ (β) = 4 for m ≥ 2.

Proof of Proposition 3

In this section we provide the proof of Proposition 3. For that we will use the notions of quadratic forms introduced in Section 2. We start with determining the value of Min 5 , since the results will be used in the other part of the proof for Max 3 .

Determining Min 5 . In the case m = 2 the set S 2 defined in (34) has only 79 elements. It is easy to enumerate them one by one and to find the value of Min 5 . Therefore, from now we will consider m ≥ 3.

1) Difference ∆ a0 . The inspected first difference of the quadratic form Q 2 is

∆ a0 = 2a 0 + 1 + c 1 a 1 + c 2 a 2 + c 3 a 3 + c 4 a 4 . ( 54
)
Since a 0 ≥ 1, c 1 < 0, c 2 < 0, c 3 > 0, c 4 > 0 and a 1 , . . . , a 4 ∈ {0, . . . , m} we have

∆ a0 ≥ 3 + mc 1 + mc 2 = 3 -m 1 β + 1 β 2 -m 2 β - 1 β 2 - 2 β 3 - 1 β 4 ≥ 3 - 3m β > 0 , ( 55
)
where the last inequality follows from the fact that m = ⌊β⌋. Therefore, the form is increasing in the variable a 0 and so the minimum is reached at the smallest possible value of a 0 , i.e., at a 0 = 1. From now on we will consider a 0 = 1.

2) Difference ∆ a1 . The inspected difference is

∆ a1 = 2a 1 + 1 β + c 1 + c 1 a 2 β + c 2 a 3 β + c 3 a 4 β . (56)
Since

c 1 < 0, c 2 < 0, c 3 > 0 we have ∆ a1 ≥ 2a 1 β - 1 β 2 - m β 1 β + 1 β 2 - m β 2 β - 1 β 2 - 2 β 3 - 1 β 4 2a 1 β - 3m + 1 β 2 . (57)
The right side of the inequality is strictly greater than zero for a 1 ≥ 2. The minimum is therefore reached for either a 1 = 0, a 1 = 1 or a 1 = 2.

3) Difference ∆ a2 . The inspected difference is

∆ a2 = 2a 2 + 1 β 2 + c 2 + c 1 a 1 β + c 1 a 3 β 2 + c 2 a 4 β 2 . ( 58
)
For the difference ∆ a2 := Q 2 (a 4 , a 3 , a 2 + 1, a 1 , a 0 ) -Q 2 (a 4 , a 3 , a 2 , a 1 , a 0 ) one needs to consider only a 2 ≤ m -1. Since c 1 , c 2 < 0, we obtain

∆ a2 ≤ 2m -1 β 2 + c 2 = 2m -1 β 2 - 2m -1 β 2 - 1 β 4 = - 1 β 4 < 0. (59)
The quadratic form is decreasing in the variable a 2 and the minimum is reached for the highest possible (w.r.t. Parry's condition) value of a 2 .

4) Difference ∆ a3 . The inspected difference is

∆ a3 = 2a 3 + 1 β 3 + c 3 + c 2 a 1 β + c 1 a 2 β 2 + c 1 a 4 β 3 . (60)
We have shown that the minimum of the quadratic form is reached for a 1 ∈ {0, 1, 2}. It is suitable to discuss the cases a 1 ∈ {0, 1} and a 1 = 2 separately.

Let us assume a 1 ∈ {0, 1}. Since a 2 , a 4 ≤ m < β and c 1 , c 2 < 0 we have

∆ a3 ≥ 1 β 3 + c 3 + c 2 β + c 1 β + c 1 β 2 = 2(m -1) β 4 + 1 β 6 > 0 . (61)
This means that for a 1 ∈ {0, 1} the minimum of the form is reached for a 3 = 0. Moreover, we already know that the minimum is reached for the highest possible value of a 2 (w.r.t. Parry's condition), therefore, we will inspect following candidates for the minimum (a 4 , 0, m -1, 1, 1) and (a 4 , 0, m, 0, 1). The discussion for a 1 = 2 will be postponed for this moment.

5) Difference ∆ a4 . The inspected difference is

∆ a4 = 2a 4 + 1 β 4 + c 4 + c 3 a 1 β + c 2 a 2 β 2 + c 1 a 3 β 3 . ( 62
)
For the quintuple (a 4 , 0, m -1, 1, 1) we obtain

∆ a4 ≥ 1 β 4 + c 4 + c 3 1 β + c 2 m -1 β 2 > 0 . (63)
Hence we have the first candidate for the point where the form Q 2 (a 4 , a 3 , a 2 , a 1 , a 0 ) reaches its minimum q 1 := (0, 0, m -1, 1, 1) .

For the quintuple (a 4 , 0, m, 0, 1) we obtain

∆ a4 ≤ 2m + 1 β 4 + c 4 + c 2 m β 2 < 0 . (65)
Second candidate for the point where the form Q 2 (a 4 , a 3 , a 2 , a 1 , a 0 ) reaches its minimum is

q 2 := (m, 0, m, 0, 1) . (66)
Here, we get back to the case a 1 = 2. We inspect the difference ∆ a4 for the quintuple (a 4 , a 3 , a 2 , 2, 1). Note that due to the Parry's condition a 2 ≤ m -1. We can estimate

∆ a4 ≥ 1 β 4 + c 4 + c 3 2 β + c 2 m -1 β 2 + c 1 m β 3 = 2 β 3 + 2m -1 β 4 - 3 β 5 > 0 . (67)
Hence we have to inspect the candidate (0, a 3 , a 2 , 2, 1).

We treat separately the case a 3 = m, which implies a 2 = 0. So we have the third candidate

q 3 := (0, m, 0, 2, 1) (68)
and the cases a 3 ≤ m -1, where according to the negativity of ∆ a2 the value of corresponding variable is a 2 = m -1. The difference ∆ a3 for the quintuple (0, a 3 , m -1, 2, 1) is

∆ a3 = 2a 3 + 1 β 3 + c 3 + c 2 2 β + c 1 m -1 β 2 = 2a 3 -2m + 6 β 3 + 1 -m β 4 - 2 β 5 - 1 β 6 . ( 69
)
It is easy to see that for a 3 ≤ m -3 the ∆ a3 < 0 and that for a 3 ≥ m -2 the ∆ a3 > 0. Therefore the fourth candidate for the minimum is

q 4 := (0, m -2, m -1, 2, 1) . ( 70
)
By computing the values of the quadratic form Q 2 in the points q 1 , q 2 , q 3 and q 4 we obtain

(β + 1) 2 β4 = Q 2 (q 1 ) < min{Q 2 (q 2 ), Q 2 (q 3 ), Q 2 (q 4 )} . (71)
Therefore, Min 2 5 = β -4 (β + 1) 2 for m ≥ 3.

Determining Max 3 . Similarly as in the previous part of the proof we will now inspect the first differences of the quadratic form Q 1 in the individual variables.

From the definition of Max 3 we need to determine the maximal value of Q 1 over the set S 1 , which allows the coefficients a 0 , a 1 , a 2 take any values in {0, 1, . . . , m} with the admissibility condition. However, it is sufficient to consider a 0 > 0, since Q 1 reaches its maximum on such a point. Otherwise, we would have

Max 3 = |0 + a 1 β ′ + a 2 (β ′ ) 2 | = |β ′ ||a 1 + a 2 β ′ | ≤ |β ′ |Max 2 < Max 2 , (72)
which is in contradiction with Max 2 ≤ Max 3 .

The inspection of the difference ∆ a0 of the quadratic form Q 1 is very similar to the one of Q 2 in the first part of the proof. We have

∆ a0 = 2a 0 + 1 + a 1 c 1 + a 2 c 2 , (73)
a 0 ≥ 1, c 1 < 0 and c 2 < 0. Hence

∆ a0 ≥ 3 + mc 1 + mc 2 ≥ 3 - 3m β > 0 , ( 74
)
the form is increasing in the variable a 0 and so the maximum is reached for the highest possible value of a 0 (w.r.t. Parry's condition).

Since

∆ a1 = 2a 1 + 1 β + c 1 a 0 + c 1 a 2 β ( 75
)
is a linear function in the variable a 1 and the coefficient 2 β at a 1 is positive, the difference ∆ a1 is either positive for all values of a 1 or negative for all values of a 1 or negative for some initial values of a 1 and then positive, regardless of the values of a 0 and a 2 .

Anyway, the maximum in the variable a 1 is reached for some extremal value of a 1 . The same reasoning works also for the maximum in the variable a 2 .

One can easily see that there are only six candidates fulfilling preceding conditions on the values of the variables a 2 , a 1 and a 0 :

a 2 a 1 a 0 q 1 0 0 m q 2 0 m -1 m q 3 0 m 1 q 4 m -1 m -1 m q 5 m -1 m 1 q 6 m 0 m (76)
Finally, by computing the values of the quadratic form Q 1 (a 2 , a 1 , a 0 ) in the points q 1 , . . . , q 6 we have

1. Q 1 (0, 0, m) = m 2 . 2. Q 1 (0, m -1, m) = m 2 + (m-1) 2 β -m(m -1) 1 β + 1 β2 < m 2 . 3. Q 1 (0, m, 1) = 1 + m 2 β -m 1 β + 1 β 2 < m 2 . 4. Q 1 (m -1, m -1, m) = m 2 + (m-1) 2 β + (m-1) 2 β 2 -m(m -1) 1 β + 1 β 2 - -(m -1) 2 1 β 2 + 1 β 3 -m(m -1) 2 β -1 β 2 -2 β 3 -1 β 4 < m 2 . 5. Q 1 (m -1, m, 1) = 1 + m 2 β + (m-1) 2 β 2 -m 1 β + 1 β 2 -m(m -1) 1 β 2 + 1 β 3 - -(m -1) 2 β -1 β 2 -2 β 3 -1 β 4 < m 2 . 6. Q 1 (m, 0, m) = m 2 + m 2 β 2 -m 2 2 β -1 β 2 -2 β 3 -1 β 4 < m 2 .
Therefore, Max 2 3 = m 2 and the proposition is proved.

Combinatorial properties of β-integers

It is known [START_REF] Thurston | Groups, tilings, and finite state automata[END_REF] that the set Z β has no accumulation points and that the distances between adjacent points in Z β take values in the set {

∞ i=1 t i+k β i | k ∈ N 0 } provided that β is
For example, if m = 2, then we generate the fixed point of the substitution by

a → aab → aabaabac → aabaabacaabaabacaaba → • • • (78)
and we obtain the infinite word u β from Figure 1.

For the description of combinatorial properties of an infinite word, crucial is the notion of a factor. We say that a finite word w = w 0 w 1 . . . w n-1 is a factor of length n of the infinite word u = u 0 u 1 u 2 • • •, if for some i we have w 0 w 1 • • • w n-1 = u i u i+1 • • • u i+n-1 . The function that to an integer n associates the number C(n) of different factors of length n in the infinite word u is called the complexity of u. It is known that the complexity of the infinite word u β is C(n) = 2n + 1 for all β such that d β (1) = m11. A proof can be found in [START_REF] Frougny | Complexity of infinite words associated with beta-expansions[END_REF].

For m = 1, the infinite word u β is called the Tribonacci word. It is known [START_REF] Arnoux | Représentation géométrique de suites de complexité 2n + 1[END_REF] that it is an Arnoux-Rauzy word, which means that for every length n ∈ N there exists a unique factor w of u β of length n, such that aw, bw and cw are factors of u β , and there exists a unique factor v of u β of length n, such that va, vb and vc are factors of u β .

It is known that if an infinite word is Arnoux-Rauzy, then the set of its factors is invariant under mirror image, i.e., with every factor w 0 w 1 • • • w n-1 the infinite word contains the factor w n-1 • • • w 1 w 0 . As a consequence, the infinite word u β for m ≥ 2 cannot be Arnoux-Rauzy, because its set of factors is not stable under mirror image. This can be seen easily from the substitution (77) under which u β is invariant: ca m b is a factor of u β , while ba m c is not.

Although the word u β is for m ≥ 2 not Arnoux-Rauzy, it is still true that for every length n ∈ N there exists a unique factor w of u β of length n, such that aw, bw and cw are factors of u β . However, one does not have a word v which could be extended with all the three letters to the right.

The invariance of the set of factors of the infinite word u β decides about a property of the image of Z β under the field isomorphism ′ : Q(β) → Q(β ′ ), the so-called Rauzy fractal. Figure 2 shows the set

Z ′ β = k i=0 a i β ′i k i=0 a i β i ∈ Z β (79)
drawn in the complex plane, for the cases m = 1, m = 2. Bernat in [START_REF] Bernat | Propriétés arithmétiques de la β-numération[END_REF] has shown that if m = 1, the closure of Z ′ β is a set centrally-symmetric with respect to the point c = 1 2 (1 -β ′ ) -1 . As it can be seen from Figure 2,Z ′ β for m = 2 does not have this property.

Fig. 1 :

 1 Fig. 1: The set Z β ∩ [0, +∞) for d β (1) = 211 and the corresponding word u β .

( a )

 a Tribonacci numeration system. (b) Numeration system with minimal polynomial x 3 -2x 2x -1.

Fig. 2 :

 2 Fig. 2: Central tiles in conjugated plane.

Acknowledgements

The authors acknowledge financial support of Czech Science Foundation GA ČR 201/05/0169, and by the grant LC06002 of the Ministry of Education, Youth, and Sports of the Czech Republic.


Petra Kocábová

Zuzana Masáková

Edita Pelantová

Ambiguity in the m-bonacci numeration system

Keywords: numeration system, generalized Fibonacci numbers, greedy expansion, palindromes 1365-8050

We study the properties of the function R (m) (n) defined as the number of representations of an integer n as a sum of distinct m-Bonacci numbers

) k≥1 . We describe the palindromic structure of the sequence (R (m) (n)) n∈N , which is richer than in the case of Fibonacci numeration system.

, given by F (m) i = 2 i-1 , for i ∈ {1, 2, . . . , m}, F

(m) k+m = F (m) k+m-1 + F (m) k+m-2 + • • • + F (m) k
, for k ≥ 1. We give a matrix formula for calculating R (m) (n) from the greedy expansion of n. We determine the maximum of R (m) (n) for n with greedy expansion of fixed length k, i.e. for F

(m) k ≤ n < F (m)
k+1 . Unlike the Fibonacci case m = 2, the values of the maxima are not related to the sequence (F

Introduction

Any strictly increasing sequence (G k ) k∈N , with G k ∈ N, G 1 = 1, defines a system of numeration where every positive integer can be written as a linear combination a k G k , where a k ∈ N 0 , see for instance [START_REF] Grabner | Odometers and systems of numeration[END_REF]. Some sequences (G k ) k∈N have even nicer property: Every positive integer can be expressed as a sum of distinct elements of the sequence (G k ) k∈N . The necessary and sufficient condition so that it is possible is that the sequence satisfies G 1 = 1 and G n -1 ≤ n-1 i=1 G i for all n ∈ N. Example of such a sequence is (2 k-1 ) k≥1 or (F k ) k≥1 , the sequence of Fibonacci numbers. The expression of n in the form

n = G is + G is-1 + • • • + G i1 , where i s > i s-1 > • • • > i 1 ≥ 1 ,
is called a representation of n in the numeration system (G k ) k∈N . This representation can be written using a sequence of coefficients (a k ) k∈N ∈ {0, 1} N as n = ∞ i=1 a i G i , where only a finite number of elements of the sequence (a k ) k∈N are non-zero. The maximal index k such that a k = 0 are called the length of the representation. The representation can be coded by the word a k a k-1 • • • a 1 in the alphabet {0, 1}. In the writing of number representations we adopt the usual convention that the concatenation of l copies of a finite word is written w l , for l = 0, 1, 2, . . . . For example, the representation of the number n = G k+2 + G k is coded by the word 1010 k-1 .

If (G k ) k∈N = (2 k-1 ) k≥1 , then the representation of every integer n in the system (G k ) k∈N is unique, and the word a k a k-1 • • • a 1 is the binary expansion of n. If we choose for (G k ) k∈N the Fibonacci sequence G k = F k , given by the recurrence F k+2 = F k+1 + F k , F 0 = F 1 = 1, then most integers have several representations. The number of distinct representations, denoted by R(n), is a function studied by many authors [START_REF] Berstel | An excercise on Fibonacci representations[END_REF][START_REF] Bicknell-Johnson | The number of representations of using distinct Fibonacci numbers, counted by recursive formulas[END_REF][START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF][START_REF] Kocábová | Integers with a maximal number of Fibonacci representations[END_REF].

On the set of representations of a given integer n in the system (G k ) k∈N one can introduce the lexicographic order in the following way: We say that the representation

v l v l-1 • • • v 1 of the number n is greater than the representation u k u k-1 • • • u 1 of n if l > k or l = k and the first non zero element in the sequence v k -u k , v k-1 -u k-1 , • • • , v 1 -u 1 is
positive. This order is sometimes called the radix order. The lexicographically greatest representation of a given number n is called the greedy expansion of n.

In this paper we study the measure of ambiguity of the representation of integers in the generalized Fibonacci numeration systems, the so-called m-Bonacci systems defined for m ≥ 2 by recurrence

F (m) 1 = 1, F (m) 2 = 2, . . . , F (m) m = 2 m-1 , F (m) k+m = F (m) k+m-1 + F (m) k+m-2 + • • • + F (m) k , for k ≥ 1 . (1)
The 2-Bonacci sequence is thus the ordinary Fibonacci sequence; 3-Bonacci sequence is usually called the Tribonacci sequence. Combinatorial properties of the m-Bonacci numeration system have been discussed in [START_REF] Grabner | Combinatorial and arithmetical properties of linear numeration systems[END_REF], in order to study the Garsia entropy connected with Pisot numbers β fulfilling

β m = β m-1 + • • • + β + 1.
The m-Bonacci numeration systems are studied in [START_REF] Frougny | Fibonacci representations and finite automata[END_REF] from the point of view of automata theory. It is proven that addition of integers written in the m-Bonacci numeration system can be performed by means of a finite state automaton, whereas it is impossible to convert an m-Bonacci representation of an integer into its standard binary expansion by a finite state automaton.

It has been shown already in [START_REF] Kautz | Fibonacci codes for synchronization control[END_REF] that every non-negative integer n can be represented as a sum of distinct elements of the m-Bonacci sequence. Such representation of n may not be unique. We denote by R (m) (n) the number of different representations of n. The recurrence relation for m-Bonacci numbers ensures that starting from an arbitrary representation of n we can get any other representation of n by interchanging 10 m ↔ 01 m or vice versa in the word coding the representation of n.

Obviously, the lexicographically greatest (greedy) representation of n does not contain the block 1 m . Let us denote the greedy expansion of n in the numeration system (F

R (m) (n) = R (m) 0 (n) + R (m) 1 (n) .
The aim of the paper is to study the properties of the function R (m) (n). First we show that the Berstel matrix formula [START_REF] Berstel | An excercise on Fibonacci representations[END_REF] for calculation of the value R (2) (n) from the greedy expansion n m can be generalized for m ≥ 3. In the next section we focus on the study of the segment of the sequence

R (m) (n) for F (m) k ≤ n < F (m)
k+1 , i.e. for such integers n whose greedy expansion has constant length k. For the Fibonacci numeration system it is known [START_REF] Bicknell-Johnson | The number of representations of using distinct Fibonacci numbers, counted by recursive formulas[END_REF][START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF] that among numbers with a fixed length k of the greedy expansion only n = F

(2) k+1 -1 satisfies R (2) (n) = 1, and moreover, the segments of the sequence R (2) (n) between two unit values are palindromes. For the m-Bonacci numeration system with m ≥ 3 we show that the number of integers n in the segment [F

(m) k , F (m) k+1 ) with a unique representation R (m) (n) = 1 is equal to the (m -1)-Bonacci number F (m-1) k
. Thus the number of 1's in the corresponding segment of the sequence (R (m) (n)) n∈N increases, however, we show that the palindromic structure of the sequence (R (m) (n)) n∈N remains preserved.

In the rest of the paper we determine the maximum of the function (R (m) (n)) n∈N in the mentioned segment. For m = 2, i.e. the Fibonacci numeration system, the maxima have been determined in [START_REF] Kocábová | Integers with a maximal number of Fibonacci representations[END_REF]

, max R (2) (n) F (2) k ≤ n < F (2) k+1 =      F (2) k+1 2 for k odd , 2F (2)
k-2 2

for k even .

We shall thus concentrate on determining the values of the maxima for m ≥ 3. Unlike the Fibonacci case, the values of the maxima are not related to the sequence (F

(m) k ) k≥1 .
2

The number of representations of n in the m-Bonacci system

The number of representations of a given integer n is related to the possible interchanges 10 m ↔ 01 m in the greedy expansion of n. For example, if n m is of length k ≤ m, then no interchange is possible and we have

R (m) (n) = 1. If the length of n m is m + 1, then only n m = 10 m admits such an interchange. It follows that R (m) (n) = 1 , for 1 ≤ n ≤ F (m) m+2 -1, n = F (m) m+1 , R (m) (F (m) m+1 ) = 2 . (2)
The aim of this section is to derive a compact formula for calculating the values of the function R (m) (n). Both the formula and its proof are slight generalizations of the result of [START_REF] Berstel | An excercise on Fibonacci representations[END_REF][START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF] for the case m = 2. Consider therefore m ≥ 3.

First we state several simple observations, which transpose the calculation of the value R (m) 0 (n) and R (m) 1 (n) for an integer n with s 1's in its greedy expansion to calculation of R (m) 0 (n) and R (m) 1 (n) for some ñ whose greedy expansion has strictly smaller number s < s of 1's. In the following, we shall identify the writing R (m) (n) with R (m) (w), where w is the word in the alphabet {0, 1} coding the greedy expansion of n, i.e. a word starting with 1.

Fact 2.1 If 0 ≤ l ≤ m -2, then R (m) 0 (10 l w) = 0, therefore R (m) 1 (10 l w) = R (m) (w). In matrix form, R (m) 0 (10 l w) R (m) 1 (10 l w) = 0 0 1 1 R (m) 0 (w) R (m) 1 (w) . Remark 2.2 (i) Note that R (m) 0 (10 l w) = 0 does not imply l ≤ m-2. It is not difficult to see that R (m)
0 (w) = 0 implies that the word w is of the form w = (10 m-1 ) s w, where s ≥ 0 and w is either the empty word, or a word of the form w = 10 l w for l ≤ m -2. Therefore the smallest n 1 such that n 1 m = k and for which R (m) 0 (n 1 ) = 0 is the number with greedy expansion

n 1 m =    (10 m-1 ) s , if s := k m ∈ N , (10 m-1 ) s 10 k-ms-1 , if s := [ k m ] = k m . (3)
At the same time, for every n such that

n 1 ≤ n < F (m) k+1 we have R (m) 0 (n) = 0. (ii)
In the word n 1 m of the form (3) one cannot perform any interchange 10 m ↔ 01 m , and therefore R (m) (n 1 ) = 1. We have thus found the smallest number n such that

F (m) k ≤ n < F (m) k+1 and R (m) (n) = 1. Note that in the Fibonacci numeration system R (2) 0 (n) = 0 already implies R (2) (n) = 1. For m ≥ 3 this is not valid. As an example, consider n m = 110 k-2 for k ≥ m + 2. Such n satisfies R (m) 0 (n) = 0 and R (m) (n) ≥ 2.
(iii) Let us express explicitly the value of n 1 . Every 1 in the word n 1 m at the position i > m represents the number

F (m) i = F (m) i-1 + F (m) i-2 + • • • + F (m) i-m . The 1 at a position i ≤ m represents F (m) i = 2 i-1 = 1 + F (m) i-1 + F (m) i-2 + • • • + F (m) 1 .
The number n 1 with greedy expansion of the form (3) is therefore equal to

n 1 = 1 + k-1 i=1 F (m) i . Fact 2.3 R (m) 0 (10 m-1 w) = R (m) 0 (w) and R (m) 1 (10 m-1 w) = R (m) (w). In a matrix form, R (m) 0 (10 m-1 w) R (m) 1 (10 m-1 w) = 1 0 1 1 R (m) 0 (w) R (m) 1 (w) . Fact 2.4 If l ≥ m, then we have R (m) 0 (10 l w) = R (m) (10 l-m w) and R (m) 1 (10 l w) = R (m) 1 (10 l-m w). In a matrix form, R (m) 0 (10 l w) R (m) 1 (10 l w) = 1 1 0 1 R (m) 0 (10 l-m w) R (m) 1 (10 l-m w)
.

Lemma 2.5 Let n m = 10 l w, where w = ñ m for some integer ñ. Then

R (m) 0 (10 l w) R (m) 1 (10 l w) = l+1 m l m 1 1 R (m) 0 (w) R (m) 1 (w)
.

R (m) 0 (10 l ) R (m) 1 (10 l ) = l+1 m l m 1 1 0 1 . Since R (m) (n) = R (m) 0 (n) + R (m)
1 (n), we can formulate the result. For that we introduce the following notation,

M (l) = M m (l) := l+1 m l m 1 1 . (4)
Theorem 2.6 Let n m = 10 rs 10 rs-1 • • • 10 r1 be the greedy expansion of the integer n in the m-Bonacci numeration system. Then

R (m) (n) = (1 1)M (r s )M (r s-1 ) • • • M (r 1 ) 0 1 . ( 5
)
3 Integers with a unique representation in the m-Bonacci numeration system

In order that an integer n has only one representation in the m-Bonacci numeration system, the lexicographically greatest and the lexicographically smallest representation must coincide.

Consider

n in the interval [F (m) k , F (m)
k+1 ). The word coding the greedy expansion of n has the form

u k u k-1 • • • u 1 , where u 1 , . . . , u k-1 ∈ {0, 1} and u k = 1 . (6)
If k < m, then an arbitrary word of the above form is a greedy expansion of some integer n. At the same time it is obvious that in such a word one cannot perform any interchange 10 m ↔ 01 m and therefore this integer n has only one m-Bonacci representation. Let

U (m) k = # n F (m) k ≤ n < F (m) k+1 , R (m) (n) = 1 .
We have derived that

U (m) k = 2 k-1 , for k = 1, 2, . . . , m -1 . (7)
Consider now k ≥ m. A word of length k satisfying ( 6) is a greedy expansion of some integer n, if and only if it does not contain the string 1 m . In order that no interchange 10 m ↔ 01 m is possible in this word, so that R (m) (n) = 1, the word cannot contain the string 0 m . Therefore U (m) k is equal to the number of words

u k u k-1 • • • u 1 such that u 1 , . . . , u k-1 ∈ {0, 1}, u k = 1, and
u k u k-1 • • • u 1 does not contain the strings 0 m , 1 m . ( 8
)
In order to determine U (m) k , we divide words satisfying (8) into 2(m-1) disjoint groups according to their suffix v ∈ S := {10, 10 2 , 10 3 . . . , 10 m-1 , 01, 01 2 , 01 3 , . . . , 01 m-1 } .

The number of words satisfying [START_REF] Grabner | Odometers and systems of numeration[END_REF] with suffix v will be denoted by A v k . Obviously,

U (m) k = v∈S A v k .
Since every word w of length k satisfying ( 8) is of the form w = w0 or w = w1, where w is a word of length k -1 satisfying (8), we obtain recurrence relations

A 10 k = A 01 k-1 + A 01 2 k-1 + • • • + A 01 m-1 k-1 , (9)
A 10 l k = A 10 l-1 k-1 , for l = 2, 3, . . . , m -1 , (10)
A 01 k = A 10 k-1 + A 10 2 k-1 + • • • + A 10 m-1 k-1 , (11)
A 01 l k = A 01 l-1 k-1 , for l = 2, 3, . . . , m -1 . (12)
Equations ( 9) and [START_REF] Kocábová | Integers with a maximal number of Fibonacci representations[END_REF] imply that U 9) and [START_REF] Kocábová | Integers with a maximal number of Fibonacci representations[END_REF] and taking sum, we obtain . It has even the same initial conditions (cf. ( 1) and ( 7)). We have thus derived the following statement. Proposition 3.1 For m ≥ 3 the number of integers n with greedy expansion of length k having unique representation in the m-Bonacci numeration system is equal to the k-th element of the (m -1)-Bonacci system. Formally,

U (m) k = A 10 k+1 + A 01 k+1 = (A 10 k + A 01 k ) + (A 10 k-1 + A 01 k-1 ) + • • • + (A 10 k-m+2 + A 01 k-m+2 ) .
#{n | F (m) k ≤ n < F (m) k+1 and R (m) (n) = 1} = F (m-1) k .
A general theory for counting the number of words with forbidden strings is developed in [START_REF] Guibas | String overlaps, pattern matching, and nontransitive games[END_REF].

4 Palindromic structure of R (m) (n)
Let us recall that transition between different representations of the same integer n is allowed by the interchange 10 m ↔ 01 m . Note that the block 10 m is the complement of the block 01 m , in the sense that every 1 is substituted by 0 and every 0 is substituted by 1. Taking complement of the word

n m = 1u k-1 • • • u 1 , we obtain the word 0(1 -u k-1 )(1 -u k-2 ) • • • (1 -u 1 )
, which is an m-Bonacci representation of an integer, which we denote by n. It is obvious that

R (m) (n) = R (m) (n) . Since n + n = k i=1 F (m) i (13)
the center of the symmetry of the function

R (m) (n) is in the value c = 1 2 k i=1 F (m) i
. Thus the sequence R (m) (n) n∈N contains a palindrome, which ends with the value R (m) (F (m) k+1 -1) and starts with the value R (

k i=1 F (m) i -F (m) k+1 +1
). Note that the center of the symmetry c satisfies

F (m) k < c < F (m) k+1 for k ≥ m + 2. According to (2), the values R (m) (1), . . . R (m) (F (m) m+2 -1) are all equal to 1 except R (m) (F (m) m+1 ) = 2, thus only k ≥ m + 2 is interesting. Remark 4.1 For m = 2, i.e. for the Fibonacci sequence, we have k i=1 F (2) i = F (2)
k+2 -2. Thus the beginning of the palindrome is at F

F (m) i -F (m) k+1 + 1 < F (m) k-1 .

Therefore having calculated the values of the function

R (m) (n) for n ≤ F (m) k -1, most of the values R (m) (n) for F (m) k ≤ n < F (m)
k+1 can be obtained from the palindromic structure. Let us determine the smallest number

n 0 ∈ [F (m) k , F (m) k+1 ), whose complement n0 lies in the range [1, F (m) k
), where we assume having the knowledge of the values of R (m) . Obviously n0 = F (m) k -1 and from (13) we have

n 0 = k-1 i=1 F (m) i + 1. For k ≥ m + 2 we have n 0 > F k . Note that n 0 is the same as the number n 1 from Remark 2.2. Thus the values R (m) (n) for n0 +1 = F (m) k ≤ n ≤ n 0 -1 are not equal to 1. The sequence R (m) (n 0 + 1), R (m) (n 0 + 2), . . . , R (m) (n 0 -1)
3 2 2 2 2 2 2 3 1 1 1 1 1 2 2 1 1 1 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 1 1 ↓ R (3) (44) ↑ center of the palindrome ↓ n 0 = 52 ↓ R (3) (80)
Using the matrix formula we obtain

Max a(m + 1) + b ≥ R (m) (n) = (1 1) 1 1 1 1 a 0 1 = 2 a , for b ∈ {0, 1, . . . , m -2} .
For k = a(m + 1) + m -1 the value of R (m) (n) at n with the greedy expansion n m = 10 2m-1 (10 m ) a-1 is equal to

Max a(m + 1) + m -1 ≥ R (m) (n) = (1 1) 2 1 1 1 1 1 1 1 a-1 0 1 = 2 a + 2 a-2 .
For k = a(m + 1) + m the value of R (m) (n) at n with the greedy expansion

n m = 10 m-1 (10 m ) a is equal to Max a(m + 1) + m ≥ R (m) (n) = (1 1) 1 0 1 1 1 1 1 1 a 0 1 = 2 a + 2 a-1 .
In the remaining part of this section we show that the above values are equal to Max(k).

Let us describe what form of the greedy expansion an argument of the maxima may have. For that we introduce the following notions. c d be integer matrices with non-negative components. We say that X majores X (written

X ≻ X) if ã ≥ a, b ≥ b, ã + c ≥ a + c and b + d > b + d . (14)
Definition 5.2 We say that the string 10 ti 10 ti-1 • • • 10 t1 is forbidden for maximality, if there exists a word 10 uj 10 uj-1 • • • 10 u1 such that

t 1 + t 2 + • • • + t i + i = u 1 + u 2 + • • • + u j + j , u 1 , u j > 0 , M (t i )M (t i-1 ) • • • M (t 1 ) ≺ M (u j )M (u j-1 ) • • • M (u 1 ) . (15)
Proposition 5.3 Let n be an integer such that n m = 10 rs 10 rs-1 • • • 10 r1 and

Max(k) = R (m) (n) and F (m) k ≤ n < F (m) k+1 .
Then 10 r l 10 r l-1 • • • 10 r l-i+1 is not a string forbidden for maximality for any integers l, i, such that

1 ≤ l -i + 1 ≤ l ≤ s.
Proof: We prove the proposition by contradiction. Let n m = 10 rs 10 rs-1 • • • 10 r1 contain a string 10 ti 10 ti-1 • • • 10 t1 forbidden for maximality, i.e. there exists l ≤ s such that r l = t i , r l-1 = t i-1 , . . . , r l-i+1 = t 1 , then the word

10 rs • • • 10 r l+1 10 uj 10 uj-1 • • • 10 u1 10 r l-i • • • 10 r1
has the same length as the greedy expansion n m . The condition u 1 , u j > 0 ensures that the new word is a greedy expansion of some integer ñ. Put

A = I 2 , if l = s , M (r s ) • • • M (r l+1 ) , if l < s , B = I 2 , if l-i = 0 , M (r l-i ) • • • M (r 1 ) , if l-i > 0 .
and

X = a b c d = M (t i ) • • • M (t 1 ) and X = ã b c d = M (u j ) • • • M (u 1 ) .
In this notation R (m) (n) = (1 1)AXB 0 1 and R (m) (ñ) = (1 1)A XB 0 1 . Denote (x y) = (1 1)A and z u = B 0 1 . From the form of the matrices A, B it can be easily seen that x ≥ y ≥ 1 and z ≥ 0, u ≥ 1. Since X ≺ X, their components satisfy (14). We have

R (m) (ñ) -R (m) (n) = (x y) ã b c d z u -(x y) a b c d z u = = (ã -a)x + (c -c)y , ( b -b)x + ( d -d)y z u ≥ ≥ (ã + c -a -c)y , ( b + d -b -d)y z u ≥ (0 1) 0 1 = 1 .
Therefore R (m) (ñ) > R (m) (n), and n was not the argument of the maxima. ✷

The above proposition enables us to restrict the set of candidates for the arguments of the maxima. Let us recall that we consider m ≥ 3, if not stated otherwise. Proof: It is sufficient to show that the string 10 t where t > 2m and t = 3m -1 is forbidden for maximality. Consider the string 10 u2 10 u1 = 10 t-m-1 10 m . Both strings 10 t and 10 u2 10 u1 have the same length, and u 1 , u 2 > 0. In order to verify

M (t) = t+1 m t m 1 1 ≺ M (u 2 )M (u 1 ) = t m + t-1 m -2 t m + t-1 m -2 2 2
it suffices to show that the inequality

t + 1 m ≤ t m + t -1 m -2
is satisfied for t > 2m and t = 3m -1. ✷

The above claim shows which strings of the type 10 t are forbidden for maximality. The following claims studies this question for some other types of strings.

Claim 5.5 The string 10 m-1 10 3m-1 is forbidden for maximality.

Proof: The proof is done by induction on the length k = a(m + 1) + b of the greedy expansion. The veracity of the statement for the initial values has been established at the beginning of this section. We have also proved that the maxima are greater or equal to the mentioned values. It is therefore sufficient to show that these values are also upper bounds on the maxima.

Assume that n is the argument of the maximum Max(k). We show that the structure of strings of 0's in the greedy expansion n m = 10 rs 10 rs-1 • • • 10 r1 is only of certain form. First suppose that R

(m) 0 (n) = 0. Then Max(k) = R (m) (10 rs 10 rs-1 • • • 10 r1 ) = R (m) (10 rs-1 • • • 10 r1 ) ≤ Max(k -r s -1) ,
and the statement follows from the induction hypothesis. It is therefore sufficient to consider n such that R

We show that the coefficients r i (and in particular the exponent y) can take only certain values. If there exists an index i such that 0 ≤ r i ≤ m-2, then (16

) implies i < s. Since M (r i ) = 0 0 1 1 , we have M (r i+1 )M (r i ) = [ r i+1 m ] [ r i+1 m ] 1 1
. This implies

Max(k) = R (m) (10 rs • • • 10 r1 ) ≤ R (m) (10 rs • • • 10 ri+1 10 ri-1 • • • 10 r1 ) ≤ Max(k -r i -1) ,
and the statement follows from the induction hypothesis. Similarly, if there exists i such that m + 1 ≤ r i ≤ 2m -2, then M (r i ) = M (m), and therefore Max(k) ≤ Max(kr i + m), and again the statement follows from the induction hypothesis. Therefore using Claim 5.4 and Remark 5.10 we can restrict our consideration to coefficients r s , r s-1 , . . . , r 2 ∈ {m -1, m, 2m -1, 2m, 3m -1} and r 1 ∈ {m, 2m}.

It follows that y in (16) takes only values y ∈ {m, 2m -1, 2m, 3m -1}. We shall now discuss the possibilities according to the values of x and y.

x = 1: Let us discuss the case x = 1. The condition y ≥ m and Claim 5.5 say that y ∈ {m, 2m, 2m -1}.

• Let n m = 10 m-1 10 m w, where the length of the word w is k -(2m + 1). Since We distinguish:

-If b ∈ {0, 1, . . . , m -2}, then using the induction hypothesis Max(a(m + 1) + b) ≤ 3(2 a-2 + 2 a-4 ) < 2 a , as required.

-If b = m -1, then similarly Max(a(m + 1) + m -1) ≤ 3(2 a-2 + 2 a-3 ) < 2 a + 2 a-2 .

-If b = m, then Max(a(m + 1) + m) ≤ 3 • 2 a-1 = 2 a + 2 a-1 .

• Let n m = 10 m-1 10 2m w, where the length of the word w is k -(3m + 1). Since -If b = m -1, then Max(a(m + 1) + m -1) ≤ 5(2 a-2 ) = 2 a + 2 a-2 .

-If b = m, then Max(a(m + 1) + m) ≤ 5 • 2 a-2 < 2 a + 2 a-1 .

• Let now n m = 10 m-1 10 2m-1 w. Claims 5.7, 5.8 and 5.9 imply that the word w is of the form w = 10 m w or w = 10 2m w. Thus we distinguish:

-Let n m = 10 m-1 10 2m-1 10 m w. Since Note that Claim 5.8 is valid only for m ≥ 4.

x = 0: Let us study the case x = 0. We have to consider y ∈ {m, 2m -1, 2m, 3m -1}.

)

  k≥1 by n m . It can be written in the form n m = 10 rs 10 rs-1 10 rs-

Proof: 1 ( 1 ,

 11 Let us write l = am + b, where b ∈ {0, 1, . . . , m -1}. If b ≤ m -2, then for the calculation of the values R 10 l w) one uses a times Fact 2.4 and then Fact 2.the statement is proved. If b = m -1, we use a times Fact 2.4 and then Fact 2.3.In order to derive the formula for calculation of R (m) (n), we need to derive the values R ) for integers n with only one 1 in their greedy expansion. It is easy to see that R

  l ) = l m , which can be written by

for l = 2 , 3 ,

 23 . . . , m -1. Similarly, from (12) we obtain A 01 l k = A 01 k-l+1 for l = 2, 3, . . . , m -1. Substituting this into (

  The sequence (A 10 k+1 + A 01 k+1 ) k∈N = (U (m) k ) k∈N thus satisfies the same recurrence relation as the (m -1)-Bonacci sequence F (m-1) k

2

 2 For m ≥ 3, we have for the starting index of the palindrome k i=1

8 - 1 =

 81 is a palindrome which does not contain the number 1. Example 4.3 For the Tribonacci numeration system, i.e. for m = 3, the values of the function R 80 are the following.

Definition 5 . 1

 51 Let X = a b c d and X = ã b

Claim 5 . 4

 54 Let n have the greedy expansion n m = 10 rs • • • 10 r1 of length k and let Max(k) = R (m) (n). Then for every i it holds that r i ≤ 2m or r i = 3m -1.

≥ 1 .

 1 According to Remark 2.2, the greedy expansion n m of n is lexicographically smaller than n 1 m . Together with Claim 5.6 it implies that n m = (10 m-1 ) x 10 y w , where x ∈ {0, 1} , y ≥ m , and w is the empty word or the greedy expansion of an integer.

(1 1

 1 )M (r s )M (r s-1 ) = (1 (k) = 3R (m) (w) ≤ 3Max(k -2m -1). We express k = a(m + 1) + b, where b ∈ {0, 1, . . . , m}. Therefore Max a(m + 1) + b ≤ 3Max (a -2)(m + 1) + b + 1 .

(1 1 )

 1 M (r s )M (r s-1 ) = ((k) = 5R (m) (w) ≤ 5Max(k -3m -1). We again express k = a(m + 1) + b, where b ∈ {0, 1, . . . , m}. We have therefore Max a(m + 1) + b ≤ 5Max (a -3)(m + 1) + b + 2 .We distinguish-If b ∈ {0, 1, . . . , m -2}, then using the induction hypothesis Max(a(m + 1) + b) ≤ 5(2 a-3 + 2 a-4 ) < 2 a , as required.

(1 1 )

 1 M (m -1)M (2m -1)M (m) = 8(1 1) and the length of the word w is k -4m -1, we haveMax(k) ≤ 8Max(k -4m -1) ≤ 2 3 Max(k -3(m + 1)) ,which implies the desired result.-Let n m = 10 m-1 10 2m-1 10 2m w. Since (1 1)M (m -1)M (2m -1)M (2m) = 13(1 1) and the length of the word w is k -5m -1, we haveMax(k) ≤ 13Max(k -5m -1) ≤ 2 4 Max(k -4(m + 1)) ,which implies the desired result.

  • • • 10 r2 10 r1 , where r i ∈ N 0 , and for every i such that m -1 ≤ i ≤ s we have r i-m+2 + r i-m+3 + • • • + r i ≥ 1. The length of the greedy expansion n m is s + r s + r s-1 + • • • + r 1 .If the lengths of n m is k, then every other representation of n has the length either k or k -1. Representations of length k are called 'long' representations and their number is denoted by R

	'short' and their number is denoted by R	(m) 1 (n); the other representations are called 0 (n). Obviously, we have (m)

Acknowledgements

The authors acknowledge partial support by Czech Science Foundation GA ČR 201/05/0169, and by the grant LC06002 of the Ministry of Education, Youth, and Sports of the Czech Republic.

Note that the value 1 appears in the line 21 times, where 21 = F

(2) 7

as corresponds to Proposition 3.1. The line does not show the entire palindrome; the missing values are R (3) (15), . . . , R (3) (43).

We end this section with a theorem whose proof for m = 2 can be found in [START_REF] Bicknell-Johnson | The number of representations of using distinct Fibonacci numbers, counted by recursive formulas[END_REF][START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF]. The proof for m ≥ 3 follows by induction on the length of the greedy expansion of n from Remark 4.2.

Theorem 4. [START_REF] Bicknell-Johnson | The smallest positive integer having F k representations as sums of distinct Fibonacci numbers[END_REF] The segment of the sequence R (m) (n) between two consecutive 1's forms a palindrome, i.e. if R (m) (p) = R (m) (q) = 1 and R (m) (n) > 1 for all n, p < n < q, then the sequence R (m) (p), R (m) (p + 1), . . . , R (m) (q -1), R (m) (q) is invariant under mirror image.

Maxima of the function

The aim of this section is to determine the maximal value of the function R (m) on integers with a fixed length of the greedy expansion. Denote

The values Max(k) for small k can be determined easily. We will use them as the initial step for the proof of the main theorem, which will be done by induction.

• If k ≤ m, then in the expansion of the length k one cannot perform any interchange

• For m < k ≤ 2m one can perform at most one interchange 10 m ↔ 01 m and therefore

• For k = 2m + 1 one can perform in the strings 10 m-1 10 m and 10 2m two interchanges in a given order. Therefore Max(2m + 1) = 3 .

• For 2m + 1 < k ≤ 3m one can perform on suitable chosen words two independent interchanges. Therefore Max(k) = 4 , for 2m + 2 ≤ k ≤ 3m .

• For k = 3m + 1 we can see by similar arguments that Max(3m + 1) = 5 .

In order to obtain a lower bound on Max(k), we determine the value R (m) (n) on the integers represented by the following words: for k = a(m + 1), a(m + 1) + 1, . . . , a(m + 1) + m -2 consider n with the greedy expansion of the form

Proof: The string (10 m ) 2 10 2m-3 has the same length as 10 m-1 10 3m-1 and the corresponding matrix, M 2 (m)M (2m-3) = 4 4 4 4 , majores the matrix M (m-1)M (3m-1) = 3 2 4 3 corresponding to the string 10 m-1 10 3m-1 . ✷ Claim 5.6 The string 10 m-1 10 m-1 is forbidden for maximality.

Proof: The string 10 2m-1 has the same length as 10 m-1 10 m-1 and the corresponding matrix M (2m -1) = 2 1 1 1 majores the matrix M 2 (m -1) = 1 0 2 1 corresponding to the string 10 m-1 10 m-1 . ✷ Claim 5.7 The string 10 m-1 10 2m-1 10 m-1 is forbidden for maximality.

Proof: The string (10 m ) 2 10 2m-3 has the same length and the corresponding matrix M 2 (m)M (2m-3) = 4 4 4 4 majores the matrix M (m -1)M (2m -1)M (m -1) = 3 1 5 2 corresponding to the string 10 m-1 10 2m-1 10 m-1 . ✷ Claim 5.8 The string 10 m-1 10 2m-1 10 2m-1 is forbidden for maximality for m ≥ 4.

Proof: The string 10 m-1 10 2m-1 10 2m-1 has the length 5m and the corresponding matrix is M (m -1)M (2m -1)M (2m -1) = 5 3 8 5 . Such matrix is majored by the matrix M 3 (m)M (2m -4) = 8 8 8 8 corresponding to the string (10 m ) 3 10 2m-4 , which has the same length 5m. ✷ Claim 5.9 The string 10 m-1 10 2m-1 10 3m-1 is forbidden for maximality.

Proof: The string 10 m-1 10 2m-1 10 3m-1 with the corresponding matrix is M (m -1)M (2m -1)M (3m-1) = 7 5 11 8 has the length as the string 10 2m 10 2m 10 2m-3 whose matrix is M 2 (2m)M (2m-3) = 12 12 6 6 . ✷

• Let n m = 10 m w. Since (1 1)M (m) = 2(1 1), we have Max(k) = 2Max(k -(m + 1)), what was to be proved.

• Let n m = 10 y w, where y ∈ {2m-1, 2m, 3m-1}. In this case the complement of n has the greedy expansion n m = 10 m-1 w or 10 m w, where w is a greedy expansion of an integer. Such cases were already discussed before. Since R (m) (n) = R (m) (n), the case is solved.

This completes the proof for m ≥ 4. Recall that the assumption m ≥ 4 was used at one point of the discussion. For m = 3 we have to consider n m = 10 m-1 10 2m-1 10 2m-1 w = 10 2 10 5 10 5 w. The discussion splits into cases according to the prefix of w. Necessarily, w = (10 5 ) k 10 ri • • • 10 r1 for some k ≥ 0, r i = 5. Since it has been shown that r 1 ∈ {3, 6}, we must have i ≥ 1.

If r i = 3, then n 3 contains the string 10 5 10 5 10 3 . The corresponding matrix is M (5)M ( 5)M (3) = 3) corresponding to the string 10 3 10 3 10 3 10 3 of the same length as 10 5 10 5 10 3 . Thus 10 5 10 5 10 3 is forbidden for maximality.

If r i = 6, then n 3 contains the string 10 5 10 5 10 6 . The corresponding matrix is M (5)M ( 5)M (6) = 13 13 8 8

which is majored by 16 16 8 8

= M (6)M (3)M (3)M (3) corresponding to the string 10 6 10 3 10 3 10 3 of the same length as 10 5 10 5 10 6 . Thus 10 5 10 5 10 6 is forbidden for maximality.

If r i = 8, then n 3 contains the string 10 5 10 8 . The corresponding matrix is M (5)M (8) = 7 5 4 3 which is majored by 8 8 4 4 = M (6)M (3)M (3) corresponding to the string 10 6 10 3 10 3 of the same length as 10 5 10 8 . Thus 10 5 10 8 is forbidden for maximality.

Last, if r i = 2, then n 3 contains the string 10 2 (10 5 ) j 10 2 for some j ≥ 2. The corresponding matrix is M (2)M 2 (5)M (2) = F2j F2j-1 F2j-1 F2j-2 which is majored by F2j+2 F2j+1

F2j+1 F2j

= M j+1 (5) corresponding to the string (10 5 ) j+1 of the same length as 10 2 (10 5 ) j 10 2 . Thus 10 2 (10 5 ) j 10 2 is forbidden for maximality. ✷

Comments and open problems

Although the numeration systems related to m-Bonacci numbers have been extensively studied from many different points of view, there remains a number of problems to be explored, even in the most simple Fibonacci case m = 2.

One of these problems is to find a closed formula for the sequence A(n) giving the least integer having n representations as sums of distinct Fibonacci numbers, which is a sort of inverse to the function R (2) (n). Some results about A(n) are given in [START_REF] Bicknell-Johnson | The least integer having p Fibonacci representations, p prime[END_REF][START_REF] Bicknell-Johnson | The smallest positive integer having F k representations as sums of distinct Fibonacci numbers[END_REF]. However, according to our knowledge, analogous function for m-Bonacci numeration system has never been studied.

Another interesting question related to R (2) is the function rk(n) defined in [START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF], counting the number of occurrences of a value n among numbers R (2) (F k ), R (2) (F k + 1), . . . , R (2) (F k+1 -1) for sufficiently large k. The authors of [START_REF] Edson | On representations of positive integers in the Fibonacci base[END_REF] show that the function is well defined, give a recurrent formula using the Euler function and exact value for n prime. The function rk(n) illustrates the exceptionality of the Fibonacci case m = 2, because similar function cannot be defined if m ≥ 3. We have already seen that the number of occurrences of the value R (m) (n) = 1 among R (m) (F k ), R (m) (F k + 1), . . . , R (m) (F k+1 -1) increases with k to infinity. Similarly, it can be shown for other values R (m) (n).

The literature often concentrates on the study of ambiguity in generalized Fibonacci numeration systems, where one allows coefficients only in {0, 1}. When omitting the limitation on


Yousri Daldoul

Djamal- Eddine Meddour
email: djamal.meddour@orange.com

Toufik Ahmed

A New Design of the IEEE 802.11 MAC Layer to Enhance the Scalability of the DMS Service

Keywords: IEEE 802.11v, Directed Multicast Service, multicast to unicast conversion, reliable multicast transport, scalable DMS

The Directed Multicast Service (DMS) is defined within the IEEE 802.11v amendment to enhance the reliability of the multicast transport over the WLAN networks by converting a multicast traffic into unicast. Therefore DMS guarantees the same unicast reliability degree to multicast traffic at the cost of the bandwidth. While DMS can be used to deliver a standard multicast stream to a limited number of receivers, it does not scale well for high throughput traffic like High Definition (HD) TV streams. In this paper we study the DMS scalability and we evaluate the transmission queue behavior using both constant and variable bit rate traffic. We show that in the case of a real time video streaming, losses caused by queue rejections may exceed the packet loss rate of the legacy multicast, limiting therefore the reliability of the DMS service. We propose a scalable version of DMS called S-DMS which executes the DMS service on the base layer and switches between DMS and the legacy multicast for the enhancement layer of a video traffic to avoid queue rejections. We show that S-DMS is able to increase considerably the number of admitted multicast members and protects the essential packets from both queuing rejections and channel losses. (

I. INTRODUCTION

Nowadays, multimedia services are becoming very famous and are delivered everywhere using the new generation of smart phones and tablets in addition to the dedicated devices like TVs. To provide such services without any location constraints, the wireless technologies remain the preferred delivery way. Considering resource limitation of wireless technologies, designing a transport protocol requires at the same time to guarantee the Quality of Service (QoS) of the delivered services and to optimize the use of the bandwidth.

The IEEE 802.11 WLAN is one of the most available wireless networks. It is deployed everywhere thanks to the reduced cost of the required infrastructure and is able to provide the appropriate bandwidth for many services even those requiring high data rates like multimedia traffics. While many services require a unicast transport, other services need multicast like TV and several other real time broadcast services. Since the legacy multicast procedure does not use any feedback policy and is therefore unreliable, the use of such transport will reduce considerably the QoS of the delivered services.

The Directed Multicast Service (DMS) is one of the principle solutions trying to resolve the unreliability issue of the multicast transport. This service is defined by the IEEE 802.11v amendment [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: IEEE 802.11 Wireless Network Management[END_REF] and operates in the MAC layer. DMS allows transmitting each multicast packet in unicast to each multicast member. Thus this ACK policy guarantees the same unicast reliability level to multicast services on the cost of the bandwidth. Therefore DMS can be used to stream a standard multicast traffic to a limited group size, but does not scale well for High Definition (HD) streams like HDTV even using the high throughput 802.11n PHY layer since the effectively available bandwidth remains limited and variable [START_REF] Li | WBest: A bandwidth estimation tool for IEEE 802.11 wireless networks[END_REF][START_REF] Rehman | Multicast Video Streaming over WiFi Networks: Impact of Multipath Fading and Interference[END_REF] for three main reasons. 1) The channel bit error rate (BER). 2) The interference with other systems using the same spectrum.

3) The bandwidth is shared with other applications, cells and devices including the legacy low-throughput devices.

Even if DMS resolves efficiently the transmission failures using the unicast retransmission policy, packet losses caused by the transmission queue rejections may exist, limiting therefore the reliability of the service. Such rejections are due to queue overflow and are frequent with real time traffics having a bit rate exceeding the available bandwidth. Since most multimedia services are delivered using UDP and are time sensitive applications, packets rejected by the transmission queue are definitely lost.

In this paper we evaluate the scalability of DMS using constant and variable bit rate (CBR and VBR) traffics and we measure the transmission queue overflow. We show that the packet loss rate caused by queue rejection exceeds in many cases the packet error rate caused by the wireless channel conditions. We design a scalable version of the DMS service called S-DMS. Our service is appropriate for layered streams. In such stream, every picture contains one base layer ensuring the minimum quality and one or many enhancement layers progressively improving the video quality. In the remaining we consider that a layered stream contains one base layer and only one enhancement layer which is the superposition of all the available enhancement layers. S-DMS classifies multicast packets into two layers: base and enhancement layers, and sends each multicast packet of the base layer using DMS. Packets belonging to the enhancement layer are sent either using DMS or using the legacy multicast, depending on the available bandwidth. S-DMS is able therefore to reduce significantly the queue rejection ratio. We show that S-DMS is able to increase considerably the number of admitted members while guaranteeing an optimized QoS for all the joining clients. We evaluate S-DMS with layered streams encoded using the H.264 Scalable Video Coding (H.264/SVC) standard [START_REF] Schwarz | Overview of the Scalable Video Coding Extension of the H.264/AVC Standard[END_REF].

The remainder of this paper is organized as follows. Section II introduces related work of some proposed multicast protocols we have studied, highlighting their problems and drawbacks. In section III we evaluate the scalability of DMS and the behavior of the transmission queue using both CBR and VBR traffics. We present the scalable DMS (S-DMS) service in section IV. We devote section V to evaluate the performance of S-DMS. Finally, we conclude in section VI.

II. RELATED WORKS

Several protocols were designed to resolve the unreliability issue of the multicast transport in the IEEE 802.11 networks [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: MAC Enhancements for Robust Audio Video Streaming[END_REF][START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: IEEE 802.11 Wireless Network Management[END_REF][START_REF] Daldoul | IEEE 802.11n aggregation performance study for the multicast[END_REF][START_REF] Chandra | DirCast: A practical and efficient Wi-Fi multicast system[END_REF][START_REF] Choi | Transparent Unicast Translation to Improve Quality of Multicast over Wireless LAN[END_REF][START_REF] Jakubczak | A cross-layer design for scalable mobile video[END_REF][START_REF] Fan | D-Cast: DSC based Soft Mobile Video Broadcast[END_REF][START_REF] Sen | Scalable WiFi Media Delivery through Adaptive Broadcasts[END_REF][START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF][START_REF] Daldoul | The impact of the reliability on the fairness between the unicast and the multicast in highly loaded WLANs[END_REF][START_REF] Choi | Leader-based Rate Adaptive Multicasting for Wireless LANs[END_REF][START_REF] Choi | Multicasting multimedia streams in IEEE 802.11 networks: a focus on reliability and rate adaptation[END_REF]. In [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: MAC Enhancements for Robust Audio Video Streaming[END_REF] the IEEE 802.11aa draft defines the Reliable Groupcast with Retries (GCR) service. This service provides two retry policies for the group addressed packets: GCR-Unsolicited-Retry and GCR-Block-Ack.

When the GCR-Unsolicited-Retry policy is used, the multicast source defines a retry limit, say "N", and transmits each multicast frame "N" times without waiting for any feedback after each transmission. The retransmission of the same frame several times allows the sender to increase the probability of the correct reception at the multicast receivers. However the use of this policy does not guarantee the QoS and generates a significant overhead particularly when the value of "N" is high.

The GCR-Block-Ack feedback policy guarantees the same unicast reliability to the multicast traffic. Within this policy the sender transmits a block of frames and asks each multicast member to acknowledge individually using an individual Block Ack Request (BAR) frame. A member is allowed to send a Block Ack (BACK) only when it receives a BAR. The GCR-Block-Ack feedback procedure is illustrated in Fig. 1.

When the Block Ack is used with the unicast transfer, the originator may send packets using the "Normal Ack" policy if there are no enough buffered packets to be transmitted using the Block Ack facility. However the 802.11aa proposal does not define a simplified reliable policy to deliver few packets. Thus, to take advantage of the GCR-Block-Ack reliability, a Block Ack agreement should be established for all the multicast session duration and should be used even for transmitting a single packet. This case incurs an important overhead and reduces the efficiency of the feedback policy [START_REF] Daldoul | IEEE 802.11n aggregation performance study for the multicast[END_REF].

The implementation of the GCR service within a legacy STA requires some modifications in the MAC layer. However some hardware modifications are required to support The GCR-Block-Ack policy since the BACK is managed by the radio card in order to respect the timing constraints. The GCR-Unsolicited-Retry policy does not have such constraints and requires software modifications only to be available.

In [START_REF] Chandra | DirCast: A practical and efficient Wi-Fi multicast system[END_REF], authors design the DirCast system to enhance the QoS of multicast services over the IEEE 802.11 networks. DirCast selects one member called "target client" for each multicast group, then sends multicast packets in unicast to the selected client. The other clients receive the packets by monitoring the channel in the promiscuous mode. Since transmission failures may occur while listening in the promiscuous mode, DirCast sends extra FEC packets. These FEC packets allow the nontarget members to recover any packet they missed. However, the transmission of the additional packets will increase the delivery delays and may incur congestion losses. Furthermore only promiscuous-enabled clients may participate in multicast sessions. Hence, users should switch manually to this mode. Moreover, the use of the promiscuous mode increases the processing load on the STA's kernel and reduces therefore the system performance.

SoftCast, a cross-layer design for mobile video, is presented in [START_REF] Jakubczak | A cross-layer design for scalable mobile video[END_REF]. SoftCast compresses the video pixels to bit sequences like a video codec would do, then maps these bits to complex samples in order to protect them from channel errors and packet losses, like a PHY layer would do. However, the SoftCast encoder uses only linear real codes for both compression and channel coding in order to ensure that the final coded simples are linearly related to the original pixels. Therefore, increasing the channel noise progressively perturbs the transmitted bits in proportion to their importance to the original video; a high-quality channel perturbs only the least significant bits while bad channel conditions still preserve the most significant bits. Thus, each receiver decodes the received signal into a video whose quality is proportional to the quality of its specific instantaneous channel.

The design of SoftCast relies on the following 3 assumptions. 1) The bit errors are caused only by the channel noise. 2) All received packets are processed and forwarded to the upper layer even if they contain errors. 3) Neither feedback nor bit rate adaptation are used. However the first assumption is not compliant with a typical 802.11 network where errors and losses are frequently caused by interference and packets collisions. In this case, the received bits will be correlated with the collision source content and not with the original video pixel. In SoftCast all received packets are processed even if they contain errors. However an error may occur in the MAC header preventing the MAC layer from forwarding the packet to the appropriate application. Moreover, SoftCast can not use any encryption algorithm to protection the data because this will remove the wanted linearity between the transmitted signal and the original video pixel. D-Cast, a similar proposal to SoftCast, is presented in [START_REF] Fan | D-Cast: DSC based Soft Mobile Video Broadcast[END_REF] with the main aim of enhancing the compression performance of the SoftCast video encoder. However, D-Cast still has the aforementioned weakness of SoftCast.

Medusa [START_REF] Sen | Scalable WiFi Media Delivery through Adaptive Broadcasts[END_REF] is designed to allow packets retransmission based on the encapsulated content priority. Yet the retry policy is implemented and managed by a third party server called the medusa proxy. This proxy is installed between the video server and the AP. The proposed retry policy operates based on "reception reports" periodically generated by each client and emitted to the proxy. Such design incurs important delays for packet loss recovery since the proxy should wait the next report of each client to decide whether or not a particular packet should be retransmitted.

The proposal of [START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF] combines the use of DMS with the legacy multicast to carry a video stream to a multicast group based on the frame priority. In this proposal, the Intra coded frames (I frames) are always transmitted using DMS while the remaining frames are always delivered using multicast. Yet, I frames have the most important size among the video pictures, generating therefore the highest instantaneous bit rate. Hence the proposal of [START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF] can not avoid the queue rejections better than DMS and still has a limited scalability. The main difference between S-DMS and [START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF] is three-fold. 1) S-DMS is designed for a layered stream where the bit rate of the base layer is always lower than the stream bit rate. Hence S-DMS is able to protect base layer packets against queue rejections for important multicast group sizes. 2) S-DMS switches between DMS and multicast to transmit the enhancement layer packets while the proposal of [START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF] sends lower priority packets always using multicast. Thus S-DMS is more reliable for carrying enhancement data. 3) S-DMS achieves selective rejection to protect base layer packets from queue overflow. Such a mechanism is not defined within [START_REF] Feng | Video Stream Groupcast Optimization in WLAN[END_REF].

In spite of its limited scalability, DMS remains among the simplest reliable multicast protocols to implement. All required changes for a legacy AP to support DMS are software updates and legacy STAs can take advantage of this service even without supporting all the 802.11v specifications. However, no work has studied the scalability of this service. In the next section we try to fill this gap and we show the impact of queue overload on the reliability of DMS.

III. OVERVIEW OF THE DIRECTED MULTICAST SERVICE SCALABILITY AND ITS IMPACT ON THE TRANSMISSION QUEUE

In basic UDP connections, the application uses the default socket configuration1 which blocks the transmission when the transmission queue is full and resumes when the queue is available again. This configuration allows the application to avoid losses caused by queue overflow. However real time applications like live555 [START_REF]The LiveMedia Framework[END_REF] are more sensitive to delays and configure therefore the socket in order to reject packets coming to date once the queue is overloaded. In the remaining we consider that all packets forwarded to the MAC layer once the queue is full are rejected.

We evaluate the queue overload using DMS with a CBR and a VBR flows. We propose a simple analytical model to estimate the average dequeue rate of the transmission queue using a CBR stream. We define X as the number of transmission attempts. The probability for a given member M i , i=1..K, to receive correctly a packet in any of the N first transmissions is given in Equation ( 1):

(1)
where Ps(i) is the packet success rate for M i . Therefore, Ps(i) is a function of the data length and the bit error rate. The probability to receive a packet correctly in X=0 attempts, P i (X=0) = 0. For simplicity we consider that all packets have the same length. We express the MAC layer efficiency as perceived by a given member M i in Equation ( 2):

E i = (data_length /PHY_rate)/transmission_time (2)
We obtain the average packet transmission time in Equation (3) for a retry limit of 7:

(

where BT(N) is the average backoff time of the N th transmission,

(5)

Hence, we derive in Equation ( 6), the efficiency equation as perceived by M i :

(6)
where r i is the used rate to send packets to member M i . To estimate the average dequeue rate we compute the average transmission rate according to Equation [START_REF] Choi | Transparent Unicast Translation to Improve Quality of Multicast over Wireless LAN[END_REF]. We consider the case of CBR stream delivered to K members using DMS.

For simplicity we consider that all members are served with the same data rate and have the same transmission efficiency. Hence we get the average transmission rate in Equation ( 8):

(8)

Finally we derive the average dequeue rate in Equation ( 9):

(9)
We depict the analytical (Theo) dequeue rate and the dequeue rate measured using ns3 [START_REF]NS-3, the Network Simulator[END_REF] in Fig. 2. We obtained these results using three different CBR streams of 12, 15 and 18 packets per frame (ppf) and 25 frames per second (fps). Each packet has a MAC data length of 1500 Bytes. We fixed the maximum queue size to 150 packets2 and used a transmission rate of 54Mbps to serve all the 6 members. We configured the wireless channel to have a packet loss rate of 5%. Fig. 2 shows that the AP may serve up to 15ppf to 6 members without causing any queue rejection. However, a flow of 18ppf exceeds the dequeuing rate and causes several rejections starting from the forth frame in this example.

We compute in Fig. 3 the allowed number of ppf for a CBR video stream of 25 fps for different multicast group sizes. We consider that all members are served using the same data rate.

The results are obtained using our analytical model. We assumed that only one stream is served and no other traffic is sharing the channel. Therefore the obtained results show the maximum allowed ppf and may decrease considerably according to the medium load and the channel conditions. In the remaining of this section we evaluate DMS using VBR video streams. We considered 3 uncompressed sequences from [START_REF]YUV test video sequences[END_REF]. Then we encoded them into 5 streams using JSVM9.16 [START_REF]JSVM Software Manual[END_REF]. All the videos have 25fps and are summarized in Table 1. In Fig. 4 and Fig. 5 we evaluated the scalability of DMS using a PHY data rate of 54Mbps to serve all the group members. The wireless channel generates an average packet loss of 5%.

Fig. 4 shows that DMS is able to serve the 4CIF resolution of "CITY" stream to only one member without causing any queue rejection. Once the group size exceeds one member, the packet loss ratio caused by queue rejection exceeds the one caused by the wireless channel. Therefore, the legacy multicast becomes more reliable than DMS. For the CIF and the QCIF resolutions, the scalability of DMS is limited to 3 and 13 members respectively in case of a non shared medium. We see that the scalability of DMS is very limited. This scalability will be considerably decreased when the medium is shared with other STAs and other streams. Fig. 5 evaluates the scalability of DMS using 3 different video contents of the same resolution. We show that DMS is able to stream the CIF resolution to 3 or 4 members, depending on the video bit rate, without causing any queue rejection. Therefore, DMS can not be deployed to serve 2 or more multicast sessions to more than 3 receivers in each group. We show that the packet delivery ratio of the legacy multicast is higher than DMS once the group size exceeds 6 members.

Figure 5. DMS scalability using different video contents

The reduced scalability of DMS allows a private usage of this service to provide a reliable multicast transport for 2 or 3 family members or friends. However, DMS can not be used in a public environment like in an airport or in a coffee to stream a TV channel or a live football match to many receivers while providing Internet connection to other STAs.

IV. THE SCALABLE DIRECTED MULTICAST SERVICE

Like DMS, S-DMS operates in the MAC layer. The basic concept of S-DMS relies on 3 main operations. packets are classified into one base layer and one enhancement layer. 2) S-DMS transmits packets belonging to the base layer using DMS and packets belonging to the enhancement layer using either DMS or the legacy multicast, depending on the available bandwidth. 3) If a packet of the base layer requires being enqueued when the transmission queue is full, S-DMS erases the last enqueued packet of the enhancement layer to provide space for the incoming packet.

The first requirement to run S-DMS is to provide information on the layer to which the enqueued packets belong. This information is available at the application level and may be forwarded to the MAC layer using several ways. The first way is to stamp packets by adding the required information into the socket structure which carries a packet from the application level to the MAC layer. The second way is to add the needed information into an additional header and encapsulate it within the packet. This header will be processed and removed in the MAC layer. Another possible way is to parse the enqueued packets in the MAC layer. However the use of this way requires that the MAC layer should be aware about the upper layer protocols and the encapsulations headers.

In this paper we do not define a special way to stamp a packet, but we consider that such a way is already implemented. Furthermore, stamping a packet is necessary in the sender side only. Once the packet is transmitted, the destination MAC layer does not need to know any special information about the packet and should process it like an ordinary packet.

To accomplish the two other functionalities of S-DMS, we defined a new queuing concept based on the use of the main transmission queue together with one virtual queue called the Virtual Enhancement layer Queue (VEQ) and one queue reserved to save unicast packets converted from one multicast packet. The latter queue is called DMS Queue.

The new design of the MAC queue is illustrated in Fig. 6.

The second requirement of the S-DMS service is to decide whether to use DMS or the legacy multicast to send a packet of the enhancement layer. Packets belonging to the base layer are always sent using DMS. Since estimating the available bandwidth is not an easy task, the best way to evaluate the average load of the WLAN is to measure the queuing delay [START_REF] Shin | Call Admission Control in IEEE 802.11 WLANs Using QP-CAT[END_REF]. Therefore we define a queuing delay limit called DelayToUseDMS. All unicast packets and non-stamped multicast packets are dequeued and transmitted without any additional processing. Concerning stamped multicast packets, at the dequeuing time, if the packet belongs to the base layer or if the queuing delay of this packet does not exceed DelayToUseDMS, then the packet is converted to unicast and saved into the DMS Queue. Afterwards packets in this intermediate queue are transmitted till the queue is empty. The entire dequeuing process is illustrated in Fig. 7.

The value of DelayToUseDMS has no impact on the queue rejection ratio of the base layer packets since they are always transmitted using DMS. However a relatively high delay value may be useless if the enhancement layer packets are rejected before switching to multicast. Furthermore, if the delay value is relatively very low, the enhancement layer packets may be always transmitted using the legacy multicast. We believe that an appropriate value of DelayToUseDMS should be about one time the packetizing rate of the video stream. Such a value allows the MAC layer to accelerate the transmission rate in order to make space for new packets arriving at the next packetizing interval. Thus for a video stream of 25fps, DelayToUseDMS may be set to 40ms.

The third operation of S-DMS relies on the use of the VEQ. This queue does not store real packets, but saves only references of the enhanced layer packets stored in the main queue. Thus when the main queue is full and one packet should be erased to make space to the incoming base layer packet, VEQ is used to provide a speed way to erase the appropriate packet from the main queue.

When a unicast packet, a non-stamped multicast packet or an enhancement layer multicast packet arrives at the MAC layer and the main queue is full, the arriving packet is automatically rejected since we consider that the arriving packet has the same priority than any other enhancement layer packet already stored. The entire enqueuing process is illustrated in Fig. 8. The implementation of S-DMS requires only some software updates in the multicast source and does not need any hardware change. The main challenge of S-DMS is to avoid any modification or additional configuration at the receiver equipment in order to be compliant with legacy 802.11 STAs.

In S-DMS we do not define an admission policy for joining members, consequently any client willing to participate in the streaming session is accepted. We leave the decision to join or to leave a session to the only intension of the customer who may decide based on the received video quality. Moreover, this paper does not define a particular procedure to manage group membership. Like in 802.11aa, we consider that such procedure is already defined and the members' adresses of each group are managed and stored in the MAC layer.

V. SIMULATION RESULTS

In this section we evaluate the S-DMS overall performance using the ns3 simulator. In Fig. 9 we measure the queue load during the video packetizing intervals and we present the maximum queue size recorded after the enqueuing of one video frame and the minimum size measured just before the packetizing of the next frame. The gap between the maximum size and the minimum size represents the number of served packets. We limit our measurements on 25 packetizing intervals. These results are obtained using 4 different CBR streams of 15, 25, 45 and 55 ppf. All streams have 25 fps where 20% of the packets of every frame belong to the base layer and 80% to the enhancement layer. Each packet has a MAC data length of 1500 Bytes. We used a transmission rate of 54Mbps to serve all the 6 members. We consider that the channel has a packet loss rate of 5%. In the remaining of this section we set the value of DelayToUseDMS to 40ms. In Fig. 9(a) all frame packets are transmitted and the queue is emptied before packetizing the next frame. Thus all packets are delivered using DMS. In Fig. 9(b) and 9(c) however, the available bandwidth is not enough to send all the enqueued packets using DMS. Therefore S-DMS switches to multicast to accelerate the dequeuing rate in order to avoid the queue rejections. In Fig. 9(d) the packet incoming rate exceeds the dequeuing rate even using multicast. Thus S-DMS performs a selective rejection to protect the base layer packets.

In Fig. 9, we notice that the length of the first segment of each sub figure has the smallest size among other segments. This is explained by the fact that during the transmission of the first video frame, none of the stored packets has reached DelayToUseDMS. Thus only DMS was used. Starting from the second packetizing time, the queuing delay of several packets exceeded the predefined delay limit. Therefore multicast is used together with DMS, allowing the delivery of more packets. Hence the segments size increase. In the remaining, we evaluate S-DMS with VBR streams using the SVC videos illustrated in Table 1. We depict in Fig. 10 the queuing rejection ratio for 4 different videos. In Fig. 11 and 12, we present the frame delivery ratio based on the successfully constructed frames at the receivers' side. A frame is successfully constructed if all its packets are correctly received. We consider two different videos. We notice that S-DMS is able to deliver reliably the base layer frames to at least 25 members while the scalability of DMS is limited to 4 members in Fig. 11 and to 10 members in Fig. 12. Moreover we observe that there is lesser decrease in frame delivery rate among the enhancement layer using S-DMS compared to DMS. Fig. 11 shows that the legacy 802.11 multicast outperforms S-DMS when delivering enhancement layer frames to more than 17 members. This is explained by the fact that S-DMS performs several queue rejections to protect the base quality as depicted in Fig. 10(a).

We notice based on Fig. 11 and 12, that using 802.11, the base layer delivery rate exceeds significantly the enhancement layer delivery rate despite the packet error rate is the same. This is justified by the fact that the base layer size in each video picture is lower than the enhancement layer size, and the probability to receive correctly a particular video frame decreases with the increasing number of the packets encapsulating the frame. In the remaining of this section we changed our simulation scenario and we consider the case of a good channel condition where the packet losses are caused only by transmission collisions. We set up an infrastructure WLAN with one AP and 6 associated STAs. The AP streams one multicast video to a multicast group of 6 members. In this scenario we consider that the channel is shared between all the nodes and every node generates single unicast traffic of a constant bit rate. We increase this bit rate progressively to evaluate the performance of S-DMS and we compare it with DMS and the legacy 802.11 multicast procedure.

In Fig. 13 the AP streams CITY_4CIF in addition to one unicast flow. We see that S-DMS delivers reliably the base layer to all members when the generated unicast traffic rate is up to 1.9Mbps per node. In this scenario we show that DMS is useless and does not guarantee any QoS. Moreover, almost all the enhancement layer frames are lost using DMS. The comparison of the 3 protocols using a lower bit rate stream is illustrated in Fig. 14. We notice that S-DMS outperforms significantly DMS. S-DMS also outperforms 802.11 since our protocol is able to avoid the queue overflow and delivers several enhancement layer packets reliably using unicast once the bandwidth is available. The protection feature of the base layer allows S-DMS to preserve the base quality against both queue rejections and channel losses.

VI. CONCLUSION

In this paper we studied the DMS proposal to guarantee the same unicast reliability level to the multicast transport and we show that DMS has a very limited scalability even using high PHY data rates. We demonstrate that the major weakness of DMS is the uncontrolled transmission overflow. Therefore we introduced a scalable version of the DMS service called S-DMS which behaves better against queue rejections. This service is designed for layered streams like those coded using SVC. S-DMS classifies a multicast video into one base layer and one enhancement layer, then transmits the base layer using DMS and switches between DMS and multicast to deliver the enhancement layer. S-DMS is able to perform a selective reject in order to protect the most important packets from queue rejection. We show throw simulation that our proposal can deliver reliably the base layer to an important group size and outperforms therefore DMS. S-DMS is also able to avoid sharp decrease of the provided QoS.

Figure 1 .

 1 Figure 1. Typical frame exchange scenario with GCR-Block-Ack policy

Figure 2 .

 2 Figure 2. Queue behavior using DMS and a CBR stream

Figure 3 .

 3 Figure 3. The maximum allowed stream rate using DMS

Figure 4 .

 4 Figure 4. DMS scalability using VBR with different resolutions

Figure 7 .

 7 Figure 7. Flowchart of the dequeuing process using S-DMS

Figure 9 .

 9 Figure 9. Queue load using S-DMS and a CBR stream

Figure 10 .Figure 8 .Fig. 10 (

 10810 Figure 10. Comparing the Queue rejection ratio of S-DMS with that of DMS using 4 different video streams: (a) CITY_4CIF, (b) CITY_CIF, (c) FOOT_CIF and (d) FORE_CIF

Figure 11 .Figure 12 .

 1112 Figure 11. Frame delivery ratio using CITY_4CIF

Figure 13 .

 13 Figure 13. Frame delivery ratio for 6 members using CITY_4CIF

Figure 14 .

 14 Figure 14. Frame delivery ratio for 6 members using FOOT_CIF

Table 1 .

 1 Videos caracteristicsVideo name Resolution Video bit rate Base l. bit rate Enhanc. l.

	bit rate

The default configuration of UDP sockets blocks sending until queue space is available by disabling O_NONBLOCK under Linux and FIONBIO under Windows. Live555 sets O_NONBLOCK/FIONBIO. Thus if space is not available, the packet is definitely lost.

The maximum queue size in the MadWifi[START_REF]The MadWifi drive[END_REF] and ath9k[START_REF]The ath9k driver[END_REF] drivers and in the ns3 simulator are 50, 123 and 400 packets respectively by default. We reduced the maximum queue size of ns3 to reduce the queuing delays. We set the size limit to 150 packets.