Emmanuel Cabanillas

A variant of Ostrowski numeration

In this article, we propose a variant of the usual Ostrowski α-numeration ( where α is a real in [0, 1[) that codes integers ( positive as well as negative) and reals of [0, 1[ ( instead of [-α, 1-α[), so that for every integer n, n and {nα} have the same coding sequence. These coding sequences respect natural lexicographic orders and will be used to prove well known results on order properties of Kronecker sequences ({nα -β}) n .

1 Introduction

overview

Ostrowski's numeration system is based on convergents (q n ) n∈N of a real α ∈ [0, 1[ and code, with a sequence of digits non negative integers as well as reals in [-α, 1 -α[ ( see [START_REF] Ostrowski | bemerkungen zur Theorie der Diophantischen Approximationnen I,II[END_REF] for the original article and [START_REF] Berthé | autour du système de numération d'Ostrowski[END_REF] for a survey). Definitions are mentioned in 2. [START_REF] Berthé | autour du système de numération d'Ostrowski[END_REF] In 2.2 and 2.3, we propose a variant of this system : it is still based on (q n ) n , but the " markovian condition" is changed and we will be able to code any integer n and any real {nα} with the same finite sequence ( {x} denotes the fractional part of a real x). We study separately the cases α irrational and α rational. This last case could appear uninteresting, but it is useful for applications to numerical semigroups for example ( see [START_REF] Cabanillas | quotients of numerical semigroups generated by two numbers[END_REF]).

In 3, we give some dynamical aspects of this α-numeration.

In 4, we use it to explore some order properties of Kronecker sequences ({nα + β}) n , as the famous " three distance theorem". These sequences have been widely studied with various points of view and we refer to [START_REF] Berthé | autour du système de numération d'Ostrowski[END_REF] for an exhaustive bibliography.

notations

All along this paper, we will denote : Z the set of integers, N * the set of positive integers and N the set of non negative integers.

For all reals x, ⌊x⌋ denotes its floor ,⌈x⌉ its ceiling and {x} its fractional part. For a sequence d = (d k ) k∈N * , we use the following notations for slices of d : for all integers r, s such that 0 < r s :

d [r,s] = (d r , d r+1 , • • • , d s ) ; d [r,∞] = (d r , d r+1 , • • • )
We will also use concatenation of sequences and intuitive notations as (3, 5, 0 4 , 1, 6, 0 ∞ ) to denote (3, 5, 0, 0, 0, 0, 1, 6, 0, 0, 0, • • • ). Moreover, if (a k ) k∈N * is a sequence of positive integers and if we restrict ourself to sequences in k {0 • • • a k }, then max at the index k will denote a k : for example, (max, 1, 0, max, 3, • • • , ) means (a 1 , 1, 0, a 4 , 3, ...). So, the notation max r or (max, 0) r , where r ∈ N ∪ {∞} will often be used. For example : (0 2 , max 3 , 0 4 , (max, 0) ∞ ) denotes the sequence (0, 0, a 3 , a 4 , a 5 , 0, 0, 0, 0, a 10 , 0, a 12 , 0, a 14 , 0, • • • ).

For α-numeration, we will often use two lexicographic orders on sequences of R N * : ◮ the reversed lexicographic order ( RLO) denoted

R : d R d ′ ⇔ d = d ′ or ∃j ∈ N * , d j < d ′ j ∀i > j, d i = d ′ i
◮ the alternate lexicographic order ( ALO) denoted

A : d A d ′ ⇔ d = d ′ or ∃j ∈ N * , (-1) j-1 d j < (-1) j-1 d ′ j ∀i ∈ {1 • • • j -1}, d i = d ′ i
ALO is a total order on R N * , but RLO is only a partial order on R N * . Now, RLO is a total order on on R (N * ) , the set of real sequences that ends with 0 ∞ .

We will also use ALO with a shift on indices for continued fraction expansions in 1.3 ( named CFE in this paper).

continued fraction expansions

All results given in this subsection are well known and we just want to underline some notations and simple facts.

• Every irrational θ can be uniquely represented by its continued fraction expansion ( CFE) and we will write θ = [t 0 , t 1 , • • • ] = [t k ] k∈N , such that t k ∈ N * for all k ∈ N * and t 0 ∈ Z. θ is the limit of the " convergents" ([t 0 , t 1 , • • • , t n ]) n , a sequence of rationals defined inductively by :

∀x ∈ R, ∀x 1 , • • • , x n ∈ R * + , [x] = x ; [x, x 1 , • • • , x n ] = x + 1 [x 1 , • • • , x n ] (1)
We will denote, for all integer n, pn qn ( or pn(θ) qn(θ) if necessary) the reduced fraction that represents

[t 0 , t 1 , • • • , t n ].
In addition, if we define ϕ :

ϕ : Z × (N * ) N * → R\Q (t k ) k∈N → [t k ] k∈N
this map is bijective and increasing, with the Alternate Lexicographic Order ( ALO) on Z × (N * ) N defined by :

(t k ) k∈N A (t ′ k ) k∈N ⇔ (∀k ∈ N, t k = t ′ k ) or ∃j ∈ N, ∀k ∈ {0 • • • j -1}, t k = t ′ k (-1) j t j < (-1) j t ′ j
We also have an expression for the inverse function of ϕ :

ϕ -1 : R\Q → Z × (N * ) N * θ → (t k ) k∈N , with t 0 = ⌊θ⌋; ∀k ∈ N * , t k = AT k-1 ({θ})
where T is the Gauss map : ]0, 1[→ [0, 1[, x → {1/x} and A : x → ⌊1/x⌋. We know that T k (α) = 0 for all k ∈ N if and only if α is irrational in ]0, 1[.

• The case of rationals seems easier, since these one are represented by finite CFE, namely the convergents of irrationals. But, we would like to associate to them infinite CFE, in order to extend ϕ to an increasing map with ALO.

We introduce an ∞ number : N * will denote N * ∪ {∞}, with the usual extension of the order ( ∀n ∈ N * , n < ∞) and of the operations ( ∀n ∈ N, n + ∞ = ∞ and 1/∞ = 0). Then, we can end CFE of rationals with an infinite sequence of ∞. With those conventions, the former map ϕ extends to an increasing and bijective map φ from a subset E of Z × (N * ) N * to R. Then, φ-1 is given by the same expressions, if we extend T and A to [0, 1[, with T (0) = 0 and A(0) = ∞.

We can precise E : it is the set of sequences (t k ) k such that t 0 ∈ Z and t k ∈ N * for k ∈ N * , such that t k = ∞ ⇒ (t k+1 = ∞ and ( t k-1 = 1 or k = 1)). So to say : if the sequence contains ∞, the last " finite digit" in the CFE is greater or equal to 2. We will prefer an alternative way : we will end CFE of rationals with [1, ∞ ∞ ], where ∞ ∞ denotes an infinite sequence of ∞. Then, we extend naturally the ALO to sequences of CFE, described by :

C = {(t k ) ∈ Z × N * × (N * ) N , ∀k 2, (t k = ∞ ⇒ (t k+1 = ∞ and t k-1 ∈ {∞, 1})}
The extension of ϕ to an increasing and bijective map ϕ 1 from C to R is quite natural, but its inverse function will use more complicated maps T 1 and A 1 :

We consider the map I : u → ⌈u⌉ -1 and A 1 , T 1 both defined on [0, 1] by :

A 1 :      0 → ∞ 1 → 1 x → I(1/x) if x = 0, 1 ; T 1 :            0 → 0 1 → 0 x → 1 if 1/x ∈ N\{0, 1} x → {1/x} else
We can now express the inverse function of ϕ 1 :

ϕ -1 1 : R → C θ → (t k ) k∈N , with t 0 = I(θ); ∀k ∈ N * , t k = A 1 T k-1 1 (θ -I(θ))
For convenience, we abreviate CFE of rationals and omit ∞ ∞ , the infinite " ∞" ending sequence. So, 9/4 = [2, 3, 1] and ∀n ∈ Z, n = [n -1, 1].

N.B : all along this paper, CFE of a real ( so for any rational) α will denote ϕ -1 1 (α), but the notation [t 0 , t 1 , • • • , t k ] will be more general ( see ( 1)).

semi-convergents and best rationals

• Let α be a real with CFE [a k ] k∈N and (p k /q k ) k its convergents sequence, such that

p k /q k = [a 0 , • • • , a k ],
for all k such that a k < ∞ ( see beginning of this section).

A semi-convergent of α is any rational of the form

mp k +p k-1 mq k +q k-1 , with m ∈ {0 • • • a k } and k ∈ N such that a k < ∞ ( we take m > 0 if k = 0 to avoid 1/0 !). So, convergents are particular semi-convergents. Lemma 1 Let α be a real with CFE [a k ] k∈N . Semi-convergents of α are exactly the rationals with CFE [a 0 , • • • , a s-1 , b s , 1], such that s ∈ N, b s ∈ {1 • • • a s } and a s+1 < ∞.

Proof :

Consequence of the definition and the well known fact : ∀m ∈ N, [a 0 , • • • , a s-1 , m] = mps-1+ps-2 mqs-1+qs-2 .

• Let α be a rational and [a 0 , a 1 , a 2 , • • • , a r , 1] its CFE. ( we denote a r+1 = 1)

We have the following induction formula :

p -2 = 0 ; p -1 = 1 ; ∀n ∈ {0 • • • r + 1} , p n = a n p n-1 + p n-2 q -2 = 1 ; q -1 = 0 ; ∀n ∈ {0 • • • r + 1} , q n = a n q n-1 + q n-2
We have α

= pr+p r-1 qr+q r-1 = p r+1 q r+1 . Let α ′ = [a ′ 0 , a ′ 1 , • • • , a ′ r ′ , 1
] be an other rational with r ′ r. With obvious notations, we see that , for n ∈ {0 • • • r} :

(∀k ∈ {0 • • • n}, a k a ′ k ) ⇒ ∀k ∈ {0 • • • n}, p k p ′ k and q k q ′ k
In addition, for j, n integers such that 1 j n r :

(a j < a ′ j and ∀k ∈ {1 • • • j -1}, a k a ′ k ) ⇒ q j < q ′ j
• Now, we would like to precise the CFE of reals in ←→ [θ, θ ′ ] ( denotes the set of reals that are between θ and θ ′ , even if θ > θ ′ ), where θ and θ ′ are two different reals and find the rationals in this interval with the lowest reduced denominator.

First, we introduce a simple and natural notion : Definition 1 ( CFE-depth of a real) . let x be a real. We name CFE-depth of x the non negative integer, denoted µ(x) and defined by : µ

(x) = +∞ if x is irrational and µ(x) = s, if x = [a 0 , a 1 , • • • , a s , 1] is the CFE of x.
We remark that :

µ(x) = 0 ⇔ x ∈ Z ; ∀n ∈ Z, µ(x + n) = µ(x) ; ∀x ∈ Z, µ(T (x)) = µ(x) -1 We denote θ = [t k ] k∈N and θ ′ = [t ′
k ] k∈N , according to our ϕ 1 -representation. We will abreviate t and t ′ these CFE-sequences. We denote r the smallest integer k such that t k = t ′ k . Then we have r min(µ(θ), µ(θ ′ )) + 2, when θ or θ ′ is rational ( if they are both irrationals, r is finite ! ). Indeed, the extremal case when r = µ(θ)

+ 2 for example corresponds to θ = [t 0 , • • • , t r-2 , 1] and θ ′ = [t 0 , • • • , t r-2 , 1, t ′ r , ...], with t ′ r < ∞. We remark that, all integers in ←→ [θ, θ ′ ]
minimize the denominator of their reduced fraction : it is 1 !! So, we can suppose that ⌊θ⌋ = ⌊θ ′ ⌋ and even that θ, θ ′ ∈ [0, 1[. The following Lemma proves that, in that case, there is only one rational in ←→ [θ, θ ′ ], that minimizes the value of its denominator : it is usually named the " best rational" in

←→ [θ, θ ′ ] Proposition 1 let θ and θ ′ be two different reals in [0, 1[ and θ = [t k ] k∈N , θ ′ = [t ′ k ] k∈N their respective CFE. We denote r the lowest integer k such that t k = t ′ k . (i) there is a unique rational in ←→ [θ, θ ′ ] that minimizes the denominator. We denote it γ. -if r min(µ(θ), µ(θ ′ )), then γ = [t 0 , • • • , t r-1 , min(t r , t ′ r ), 1]. -else, µ(θ) < µ(θ ′ ) ( up to swap) and γ = θ. (ii) in both cases, µ(γ) min(µ(θ), µ(θ ′ )) and γ = [t 0 , • • • , t s-1 , min(t s , t ′ s ), 1], where s = µ(γ) r and ∀k ∈ {0 • • • s -1}, t k = t ′ k . (iii) the best rational in ←→ [θ, θ ′ ]
is the common semi-convergent of θ and θ ′ with the greatest denominator.

Proof :

(i) if r min(µ(θ), µ(θ ′ )). Suppose that t r < t ′ r . We have for (d k ) k∈N ∈ C: [d k ] k∈N ∈ ←→ [θ, θ ′ ] ⇔ ∀k < j, d k = t k = t ′ k σ r (t) A σ r (d) A σ r (t ′ ) ( * )
where σ is the usual shift : for any sequence u, ∀k ∈ N, σ(u) k = u k+1 . But, if we want the lowest denominator for the rational [d k ] k∈N , we have to choose the lowest d k or the ∞ value ( if possible), for all k. So we have to choose first d r = t r and then, the condition (*) becomes :

σ r+1 (d) A σ r+1 (t). So, we choose d r+1 = 1 and ∀k > r + 1, d k = ∞.
-else, one at least of µ(θ) and µ(θ ′ ) is finite and they can not be equal, since r can not be greater than both of them. Suppose µ(θ) < µ(θ ′ ), then we have µ(θ) < r and ∀k ∈ {0 • • • µ(θ)}, t k = t ′ k . So, the same arguments as in the previous case prove that θ is the best rational in

←→ [θ, θ ′ ].
(ii) it is plain in the first case, since µ(γ) = r. If µ(θ) < r and µ(θ) < µ(θ ′ ), then γ = θ and t s = t ′ s .

(iii) is a consequence of (ii), Lemma 1 and the remark following it.

Remark : as a direct consequence of (iii) : θ is the best rational in

←→ [θ, θ ′ ] if and only if θ is a semi-convergent of θ ′ .
• Let α be a real, [a k ] k∈N * its CFE and r = µ(α), the CFE-depth of α. So, we denote [a 0 , a 1 , • • • , a r , 1] the CFE of α if α is rational. We also denote (p n /q n ) n the usual sequence of convergents of α.

We consider the usual notion of best rational approximation of a real α : for p, q two integers, p/q is said a best rational approximation of α if and only if :

∀q ′ ∈ {1 • • • q -1} , ∀p ′ ∈ Z , p ′ q ′ -α > p q -α
It is well known that best rational approximation of a real are exactly its reduced convergents. Now, we can consider two sided similar definitions :

Definition 2 ( best sided rational approximation) . for p, q two integers, p/q is said a best left rational approximation of α if and only if :

∀q ′ ∈ {1 • • • q -1} , ∀p ′ ∈ Z , p ′ q ′ < p q α or p ′ q ′ > α
p/q is said a best right rational approximation of α if and only if :

∀q ′ ∈ {1 • • • q -1} , ∀p ′ ∈ Z , p ′ q ′ > p q α or p ′ q ′ < α
Here is a corollary of Proposition 1 :

Corollary 1 .

(i) best left rational approximations of α are the semi-convergents of α, that are lower than α.

(ii) best right rational approximations of α are the semi-convergents of α, that are greater than α.

Proof :

(i) we remark that p/q is a best left rational approximation of α if and only if p/q is the best rational in [p/q, α] and use the remark below Proposition 1. Same arguments for (ii).

If we denote (p k /q k ) k the reduced convergents of α, then : -its best left rational approximations are :

p 2i + mp 2i+1 q 2i + mq 2i+1 ; i ∈ {0 • • • (µ(α) -1)/2} ; m ∈ {0 • • • a 2i+2 }
-its best right rational approximations are :

p 2i-1 + mp 2i q 2i-1 + mq 2i ; i ∈ {1 • • • µ(α)/2} ; m ∈ {0 • • • a 2i+1 } 2 A numeration system 2.

Ostrowski's numeration

We will only deal here with the case α irrational, even if the rational case is interesting ( see next section). We denote Ω α the set of sequences of integers defined as follows ( we denote [a k ] k∈N the continued fraction expansion of α) :

Ω α = {(d n ) n∈N * , d 1 ∈ {0 • • • a 1 -1}, ∀k ∈ N * \{1}, d k ∈ {0 • • • a k } and (d k = a k ⇒ d k-1 = 0)}
What we call " markovian condition" is the last implication :

d k = a k ⇒ d k-1 = 0.
From this set of infinite sequences, we extract two subsets, that will be our numeration sets for reals and integers respectively : O α is the set of sequences d of Ω α such that d does not " end with" (max, 0) ∞ , an infinite sequence a k 0a k+2 0 • • • . So to say, there is an infinite number of even and an infinite number of odd values of k such that d k < a k . Now, O (α) is the set of sequences d of Ω α ( or O α ) that ends with an infinite sequence of 0 : so to say d k = 0 for any sufficiently large k.

We define then two maps :

f α :    O (α) → N d → ∞ k=1 d k q k-1 ; g α :    O α → [-α, 1 -α[ d → ∞ k=1 d k (αq k-1 -p k-1 )
It is well known that f α and g α are well defined and are bijective. Moreover :

∀d ∈ O (α) , {f α (d)α} = {g α (d)}
But, we will emphasize an other aspect : the maps above are increasing for the usual order on N and R respectively and following orders on O (α) and O α .

-the reversed lexicographic order ( RLO) on O (α) :

d R d ′ ⇔ d = d ′ or ∃j ∈ N * , d j < d ′ j ∀i > j, d i = d ′ i
-the alternate lexicographic order ( ALO) on O α :

d A d ′ ⇔ d = d ′ or ∃j ∈ N * , (-1) j-1 d j < (-1 j-1 d ′ j ∀i ∈ {1 • • • j -1}, d i = d ′ i
These are total orders on these sets respectively.

Our aim is to find a variant of Ostrowski numeration that has same properties, but that code reals of [0, 1[ instead of [-α, 1 -α[ and also all integers, positive as well as negative ones.

We will see that it suffices to change the markovian condition : instead of

d k = a k ⇒ d k-1 = 0, we take d k = 0 ⇒ (d k-1 = a k-1 or d i = 0 for all i k).
2.2 α-numeration for a rational α Why do we consider this case α rational ? Indeed, the set {{nα}, n ∈ N} is finite and trivial. It can not define a base of numeration for [0, 1[. But the order properties of the sequence ({nα}) n∈N are not obvious and our Ostrowski-like numeration will help.

• Let α be a rational in [0, 1[ and α = [0, a 1 , • • • , a r , 1] its CFE. We will denote (p k /q k ) 0 k r+1 its convergents, so that α = p r+1 q r+1 . Definition 3 ( α-admissible sequences) . a sequence d in N r is said α-admissible if and only if :

∀j ∈ {1 • • • r}, d j ∈ {0 • • • a j } d j = 0 ⇒ (∀i j, d i = 0) or d j-1 = a j-1
We will denote E α the set of α-admissible sequences.

Remark : for j = 1, the second condition reduces to

d 1 = 0 ⇒ ∀i 1, d i = 0. So to say, d = (0, • • • , 0) is the only element of E α , whose first coordinate is 0. Lemma 2 . (i) ∀d ∈ E α , ∀k ∈ {1 • • • r}, k i=1 d i q i-1 < q k + q k-1 (ii) let d, d ′ ∈ E α and n ∈ {1 • • • r} such that d ′ n > 0. ∀k ∈ {1 • • • n}, k i=1 (d i -d ′ i )q i-1 < q k
Proof :

(i) by plain induction on k.

(ii) by induction ( on 2 ranks) on k :

-it is true for k = 0 ( obvious) and for k = 1 : indeed d ′ 1 > 0 ( else, we would have

d ′ = 0 and d ′ n = 0) : then (d 1 -d ′ 1 )q 0 (a 1 -1)q 0 = q 1 -1.
-we suppose that it is true for the ranks k -2 and k -1, where k is an integer in {2 • • • n}. Then, we have two cases for the rank k :

◮ Case 1 : d k -d ′ k a k -1, then, with the induction hypothesis on rank k -1 : k i=1 (d i -d ′ i )q i-1 < q k-1 + (a k -1)q k-1 = a k q k-1 = q k -q k-2 < q k the last inequality is true, for k 2. ◮ Case 2 : d k = a k , d ′ k = 0, then d ′ k-1 = a k-1 ( else, we would have d ′ j = 0 for all j k, but d ′ n = 0) and d k-1 -d ′ k-1 0. So with the induction hypothesis on rank k -2 : k i=1 (d i -d ′ i )q i-1 < q k-2 + a k q k-1 = q k
We consider the reversed lexicographic order ( RLO) denoted

R on N r : d R d ′ ⇔ d = d ′ or ∃j ∈ {1 • • • r}, d j < d ′ j ∀i ∈ {j + 1 • • • r}, d i = d ′ i
It is a total order on E α .

Lemma 3 the map

Ψ α below is increasing from (E α , R ) to ({0 • • • q r+1 -1}, ). Ψ α :      E α → {0 • • • q r+1 -1} d → r j=1 d j q j-1
Proof :

First, for all d ∈ E α , Ψ α (d) ∈ {0 • • • q r+1 -1}, with Lemma 2 (i). Now, let prove that Ψ α is increasing. Let d, d ′ ∈ E α , such that d < R d ′ . We have j ∈ {1 • • • r}, such that : d j < d ′ j and ∀i ∈ {j + 1 • • • r}, d i = d ′ i So : Ψ α (d ′ ) -Ψ α (d) = j-1 i=1 (d ′ i -d i )q i-1 + (d ′ j -d j )q j-1
We just have to prove that :

j-1 i=1 (d i -d ′ i )q i-1 < q j-1 , since d ′ j -d j 1. This is shown by Lemma 2 (ii), for d ′ j > 0.
Now, we prove that Ψ α is surjective : the following algorithm explains the inverse function of Ψ α . We will denote

m k = q k + q k-1 for any k ∈ {0 • • • r}. So m r = q r+1 . Algorithm 1 let n ∈ {0 • • • m r -1}.
With the following algorithm, we have d ∈ E α and Ψ α (d) = n.

Input: n Output: (d i ) i∈{1•••r} for k ← r to 1 step -1 do d k ← max 0, n-q k-2 q k-1 ; n ← n -d k q k-1 end Proof :
We begin with a remark : if n < m s for an integer s ∈ {1 • • • r}, then :

d k = 0 for k ∈ {s + 1 • • • r}. Indeed, we will have n < m k for all k ∈ {s • • • r} so n -q k-2 < q k-1 for all k ∈ {s + 1 • • • r}.
Let us prove the result by induction on s, where s in an integer such that n

∈ {0 • • • m s -1} : -for s = 1, m 1 = a 1 + 1. Let n ∈ {0 • • • a 1 }. Then d 1 = n and d = (d 1 ) ∈ E α , Ψ α (d) = d 1 = n. -we suppose that the algorithm is available for all n ∈ {0 • • • m s-1 -1}, with s 2. Let n ∈ {m s-1 • • • m s -1}. Then q s-1 n -q s-2 < (a s + 1)q s-1 , so d s ∈ {1 • • • a s }. We denote n 1 = n -d s q s-1
, the value of n after the loop for k = s. We have :

q s-2 n 1 < q s-1 + q s-2 = m s-1 . By induction hypothesis, d ′ = (d 1 , • • • , d s-1 ) ∈ E α and n 1 = Ψ α (d ′ ) = s-1 i=1 d i q i-1 . But, n = n 1 + d s q s-1 and so Ψ α (d) = n, because we have d ∈ E α : indeed, we have 2 subcases : ◮ Case 1 : if n 1 m s-2 , then d s-1 > 0 and, since (d 1 , • • • , d s-1 ) ∈ E α , then d ∈ E α . ◮ Case 2 : if n 1 < m s-2
( which leads to s 3, for m 0 = q 0 ), then d s-1 = 0 and n 2 = n 1 ( n 2 : the value of n after the loop for k = s -1). But, since n 1 q s-2 , then n 2 -q s-4 a s-2 q s-3 and finally

d s-2 = a s-2 . By induction hypothesis, d ′ = (d 1 , • • • , d s-3 , a s-2 , 0) is α-admissible, so d ∈ E α .
Proposition 2 Ψ α is an order isomorphism between (E α , R ) and ({0 • • • q r+1 -1}, ).

Remark : as a direct consequence : E α has q r+1 elements. Proof :

a direct consequence of Lemma 3 and Algorithm 1

• Now, we will deal with α-numeration for elements of U α = {{kα}, k ∈ N}. Since, α = p r+1 q r+1 and this fraction is reduced, we have

U α = { n q r+1 , n ∈ {0 • • • q r+1 -1}}.
So, this set is very simple, but we will focus on the map k → {kα}, with the order point of view :

We consider the alternate lexicographic order ( ALO) denoted

A on R r : d A d ′ ⇔ d = d ′ or ∃j ∈ {1 • • • r}, (-1) j-1 d j < (-1) j-1 d ′ j ∀i ∈ {1 • • • j -1}, d i = d ′ i
It is another total order on E α . We define also :

∀i ∈ {-2 • • • r}, δ i = (-1) i (q i α -p i )
We have, with a 0 = 0 here :

δ -2 = α ; δ -1 = 1 ; δ 0 = {α} = α ; ∀i ∈ {0 • • • r}, δ i = -a i δ i-1 + δ i-2
Let T be the Gauss map : ]0, 1[→ [0, 1[, x → {1/x}. By induction on i, with the fact that :

a i = 1 T i-1 (α) if i r -1, we obtain : ∀i ∈ {0 • • • r -1}, δ i δ i-1 = T i (α) Beware : for i = r, T r-1 (α) = [0, a r , 1] = 1 ar+1 , so : δ r δ r-1 = δ r-2 -a r δ r-1 δ r-1 = 1 T r-1 (α) -a r = 1 So : δ r = δ r-1 . We will prove ( proof of Algorithm 2) that δ r = δ r-1 = 1 q r+1 . To summarize this : ∀i ∈ {0 • • • r -1}, 0 < δ i < δ i-1 ; δ r = δ r-1 = 1 q r+1 Lemma 4 let d, d ′ ∈ E α and j ∈ {1 • • • r}, , then : (-1) j-1 (d ′ j -d j ) > 0 ⇒ r i=j+1 (-1) i (d ′ i -d i )δ i-1 < δ j-1
Proof :

First, we remark that, for all i, we have (-

1) i (d ′ i -d i ) a i , so : r i=j+1 (-1) i (d ′ i -d i )δ i-1 r i=j+1 a i δ i-1 = r i=j+1 (δ i-2 -δ i ) = δ j-1 + δ j -δ r-1 -δ r ◮ Case 1 : if (-1) j+1 (d ′ j+1 -d j+1 ) a j+1 -1, then : r i=j+1 (-1) i (d ′ i -d i )δ i-1 δ j-1 -δ r-1 -δ r < δ j-1 ◮ Case 2 : if (-1) j+1 (d ′ j+1 -d j+1 ) = a j+1 . ◮◮ Subcase 1 : if j is even, d ′ j+1 = 0 and d j+1 = a j+1 .
We can not have d ′ j = a j , for, with our hypothesis, d j > d ′ j . So d ′ i = 0 for all i > j and :

r i=j+1 (-1) i (d ′ i -d i )δ i-1 = a j+1 δ j - r i=j+2 (-1) i d i δ i-1 (r-j-1)/2 p=0 a j+2p+1 δ j+2p = = (r-j-1)/2 p=0 (δ j+2p-1 -δ j+2p+1 ) = δ j-1 -δ r ′ < δ j-1
with r ′ = r or r -1. ◮◮ Subcase 2 : if j is odd, similar arguments lead to the same conclusion ( we swap d and d ′ ). Proposition 3 . (i) the map Λ α ( defined below) is an order isomorphism, with ALO on E α :

Λ α :      E α → n q r+1 , n ∈ {0 • • • q r+1 -1} d → r j=1 d j (-1) j-1 δ j-1 (ii) we have : ∀n ∈ {0 • • • q r+1 -1}, {nα} = Λ α (Ψ -1 α (n)) Proof : (i) First, we will show that Λ α is increasing : let d, d ′ ∈ E α with d < A d ′ . Then, we have j ∈ {1 • • • r} such that : (-1) j-1 d j < (-1) j-1 d ′ j and ∀i < j, d i = d ′ i So : Λ α (d ′ ) -Λ α (d) = (-1) j-1 (d ′ j -d j )δ j-1 + r i=j+1 (-1) i-1 (d ′ i -d i )δ i-1 Now : (-1) j-1 (d ′ j -d j )δ j-1 δ j-1 so with Lemma 4, we obtain : Λ α (d ′ ) -Λ α (d) > 0
Now that we have proved that Λ α is increasing, we can easily deduce that Λ

α (E α ) ⊂ [0, 1[ : first, remark that (0, • • • , 0) is the lowest element of E α ( with ALO), so Λ α (d) 0 for all d ∈ E α . Now, (a 1 , 0, a 3 , 0, • • • ) is the greatest element of E α for ALO, so : ∀d ∈ E α , Λ α (d) (r-1)/2 p=0 a 2p+1 δ 2p = (r-1)/2 p=0 (δ 2p-1 -δ 2p+1 ) = δ -1 -δ r ′ < 1 with r ′ = r or r -1.
(ii) we just have to show this equality to complete the proof :

let d ∈ E α . It is sufficient to prove that Λ α (d) = {Ψ α (d)α}. Now : Λ α (d) = r j=1 d j (q j-1 α -p j-1 ) = αΨ α (d) -k
where k = r j=1 d j p j-1 is an integer. So Λ α (d) = {Ψ α (d)α} modulo 1. But, we have seen that both terms are in [0, 1[, q.e.d.

Remarks : result (ii) means that the map n → {nα} ( with 0 n < q r+1 ), is, from the order point of view, the " same thing" as the identity (E α , RLO) → (E α , ALO).

We can sum up these formulae :

∀n ∈ {0 • • • q r+1 -1}, with d = Ψ -1 α (n) : n = r j=1 d j q j-1 ; ⌊nα⌋ = r j=1 d j p j-1 ; {nα} = r j=1 (-1) j-1 d j δ j-1
The following algorithm expresses the inverse function of Λ α .

Algorithm 2 let β ∈ { n q r+1 , n ∈ N}. Applying the algorithm below, we have :

(i) b ∈ E α . (ii) β = Λ α (b). Input: β Output: (b i ) i∈{1•••r} for k ← 1 to r do b k ← min a k , β δ k-1 ; β ← b k δ k-1 -β end Proof :
First, we denote (β k ) k∈{0•••r} the finite sequence defined by :

β 0 = β ; ∀k ∈ {1 • • • r} , β k = b k δ k-1 -β k-1
Thus, β k is the value of β after k loops in Algorithm 2. So, we have :

b k = min(a k , ⌈β k-1 /δ k-1 ⌉) (i) let us verify that b ∈ E α : by induction on k, we will prove that "(b 1 , • • • , b k ) is α-admissible and that -δ k < β k < δ k-1 for all k ∈ {0 • • • r}". -it is true for k = 0, since δ 0 = α > 0 and δ -1 = 1. -we suppose that it is true for k -1 with k ∈ {1 • • • r}. Then, β k-1 δ k-1 > -1, so β k-1 δ k-1 0 and 0 b k a k . If b k-1 > 0, then (b 1 , • • • , b k ) is α-admissible, for (b 1 , • • • , b k-1 ) ∈ E α . If b k-1 = 0, then β k-2 0

and we have 2 cases :

◮ Case 1 : if β k-2 = 0, then by obvious induction, β i = 0 and b i = 0 for all i k -1. ◮ Case 2 : else, we have β k-2 < 0 , so k 3 and :

β k-3 = b k-2 δ k-3 -β k-2 > b k-2 δ k-3 So β k-3 δ k-3 > b k-2 , which leads to b k-2 = a k-2 .
In these both cases, we have : (b 1 , • • • , b k ) satisfies the conditions of E α . Now : by induction hypothesis, we have :

-δ k-1 < β k-1 < δ k-2 ◮ Case 1 : if β k-1 δ k-1 a k , then : b k = β k-1 δ k-1 so β k-1 b k δ k-1 , so β k 0 and b k < β k-1 δ k-1 + 1, so β k < δ k-1 . ◮ Case 2 : if β k-1 δ k-1 > a k , then b k = a k and β k < 0. Moreover :
β k = a k δ k-1 -β k-1 > a k δ k-1 -δ k-2 = -δ k (ii) Λ α (b) = r k=1 (-1) k b k δ k-1 = r k=1 ((-1) k β k -(-1) k-1 β k-1 ) = (-1) r β r -β we also have β = Λ α (b) + (-1) r β r . Now, -δ r < β r < δ r-1 . Claim : " for every k ∈ {-1 • • • r-1}
, q r+1 δ k is the k th remainder, denoted ρ k in the euclidean algorithm between p r+1 and q r+1 and we have ρ r-1 = 1." Indeed, by double induction on k : -it is true for k = -1 and k = 0, since q r+1 δ -1 = q r+1 = ρ -1 and q r+1 δ 0 = p r+1 = ρ 0 .

-then, both sequences satisfy the same double induction formula :

∀k ∈ {1 • • • r -1}, q r+1 δ k = q r+1 δ k-2 -a k q r+1 δ k-1 ; ρ k = ρ k-2 -a k ρ k-1
Now, euclidean algorithm stops when we obtain a rest equal to 0, and the former rest is the greatest common divisor of ρ -1 and ρ 0 , namely 1 here, since the convergent fractions are reduced. So, ρ r-1 = 1. But, we have chosen the continued fraction expansion of α, that ends with 1, so ρ r-2 = a r + 1, and

q r+1 δ r = ρ r-2 -a r ρ r-1 = 1.
We conclude : δ r = δ r-1 = 1 qr+1 and |β r | ∈ [0, 1/q r+1 [. Now, the former facts show that β k q r+1 ∈ Z for all k, so : β r = 0.

• We can easily extend this numeration to [0, 1[, by adding a last " digit" that can range in [0, 1[. First, we extend the ALO to

E α × [0, 1[ : (d, ǫ) A (d ′ , ǫ ′ ) if and only if (d = d ′ and ǫ ǫ ′ ) or d < A d ′ .
Corollary 2 the map Λα is an order isomorphism, with ALO on E α × [0, 1[ :

Λα :      E α × [0, 1[→ [0, 1[ (d, ǫ) → r j=1 d j (-1) j-1 δ j-1 + ǫδ r Proof :
a direct consequence of Proposition 3.

Remark : if Λα (d, ǫ) = β then ǫ = {q r+1 β}, with usual notations.

α-numeration for an irrational α

• Let α be an irrational and [a k ] k∈N its CFE. We extend our notion of α-admissible sequence : Definition 4 (α-admissible sequences) . a sequence d in N N * is said α-admissible if and only if d does not end with (max, 0) ∞ , an infinite sequence of a k , 0, a k+2 , 0, • • • ( so to say there are an infinite number of even and odd indices k such that d k > 0 or d k+1 < a k ) and :

∀j ∈ N * , d j ∈ {0 • • • a j } d j = 0 ⇒ (∀i j, d i = 0) or d j-1 = a j-1
Thus, the null-sequence is the only α-admissible sequence that begins with 0. We denote E α the set of α-admissible sequences and E (α) the subset of E α of sequences, that ends with 0 ∞ , an infinite sequence of 0.

• We consider two lexicographic total order, respectively on E α and E (α) : -the reversed lexicographic order ( RLO) on E (α) :

d R d ′ ⇔ d = d ′ or ∃j ∈ N * , d j < d ′ j ∀i > j, d i = d ′ i
-the alternate lexicographic order ( ALO) on E α :

d A d ′ ⇔ d = d ′ or ∃j ∈ N * , (-1) j-1 d j < (-1 j-1 d ′ j ∀i ∈ {1 • • • j -1}, d i = d ′ i • We define : ∀i ∈ N ∪ {-1} , δ i = (-1) i (q i α -p i )
with, as usual p i /q i being the reduced fraction of the convergent [a 0 , • • • , a i ]. We have then :

δ -1 = 1 ; δ 0 = α ; ∀i ∈ N * , δ i = -a i δ i-1 + δ i-2
Let T be the Gauss map : ]0, 1[\Q →]0, 1[\Q, x → {1/x}. By induction on i, with the fact that :

a i = 1 T i-1 (α) if i ∈ N * , we obtain : ∀i ∈ N , δ i δ i-1 = T i (α) (δ i )
i∈N is a decreasing and positive sequence, that converges towards 0.

Lemma 5 let d, d ′ ∈ E α and j ∈ {1 • • • r}, , then : (-1) j-1 (d ′ j -d j ) > 0 ⇒ ∞ i=j+1 (-1) i (d ′ i -d i )δ i-1 < δ j-1
Proof :

We have 2 cases :

◮ Case 1 : if (-1) j+1 (d ′ j+1 -d j+1 ) a j+1 -1, then : ∞ i=j+1 (-1) i (d ′ i -d i )δ i-1 (a j+1 -1)δ j + ∞ i=j+2 (-1) i (d ′ i -d i )δ i-1
But, nor d nor d ′ ends with (max, 0) ∞ , an infinite sequence of " (a k , 0)", so :

∃k > j + 1, (-1) k (d ′ k -d k ) < a k ; ∀i > j, (-1) i (d ′ i -d i ) a i
We deduce :

∞ i=j+2 (-1) i (d ′ i -d i )δ i-1 < ∞ i=j+2 a i δ i-1 = ∞ i=j+2 (δ i-2 -δ i ) = δ j+1 + δ j
We conclude :

∞ i=j+1 (-1) i (d ′ i -d i )δ i-1 < a j+1 δ j + δ j+1 = δ j-1 ◮ Case 2 : if (-1) j+1 (d ′ j+1 -d j+1 ) = a j+1 . ◮◮ Subcase 1 : if j is even, d ′
j+1 = 0 and d j+1 = a j+1 . We can not have d ′ j = a j , for (-1) j-1 d j < (-1) j-1 d ′ j , so d ′ i = 0 for all i > j and, since d does not end with (max, 0) ∞ , then :

∞ i=j+1 (-1) i (d ′ i -d i )δ i-1 = a j+1 δ j - ∞ i=j+2 (-1) i d i δ i-1 < ∞ p=0 a j+2p+1 δ j+2p
Indeed, (-1) j+2p d j+2p δ j+2p-1 0, for all p ∈ N, since j is even. So :

∞ i=j+1 (-1) i (d ′ i -d i )δ i-1 < ∞ p=0 (δ j+2p-1 -δ j+2p+1 ) = δ j-1
◮◮ Subcase 2 : if j is odd, similar arguments lead to the same conclusion ( we swap d and d ′ ).

• Now, we define two maps on these sets : Proposition 4 .

(i) the map Ψ α ( defined below) is an order isomorphism from (E (α) , R ) to (N, ).

Ψ α :      E (α) → N d → ∞ j=1 d j q j-1
(ii) the map Λ α ( defined below) is an order isomorphism from (E α , A ) to ([0, 1[, ). :

Λ α :      E α → [0, 1) d → ∞ j=1 d j (-1) j-1 δ j-1
(iii) we have :

∀n ∈ N, {nα} = Λ α (Ψ -1 α (n))
Remark 1 : the infinite sum in the definition of Ψ α is in fact a finite one. The infinite sum in the definition of Λ α is well defined since :

∀j ∈ N * , 0 d j δ j-1 a j δ j-1 = δ j-2 -δ j
Remark 2 : if we had defined E α without the restriction about the ending of the sequences, then the result about Λ α would have been valid, except that : for x ∈ {{nα}, n ∈ N}, x would have three ( two for 0) preimages : the one in E (α) and those that end with (max, 0) ∞ , an infinite sequence of "a k , 0".

Proof :

(i) see proof of Lemma 3 and proof of Algorithm 1.

(ii) first, we will prove that Λ α is increasing : let d, d ′ ∈ E α such that d < A d ′ . Then, we have j ∈ N * such that :

(-1) j-1 d j < (-1) j-1 d ′ j and ∀i < j, d i = d ′ i So : Λ α (d ′ ) -Λ α (d) = (-1) j-1 (d ′ j -d j )δ j-1 + ∞ i=j+1 (-1) i-1 (d ′ i -d i )δ i-1
But, (-1) j-1 (d ′ j -d j )δ j-1 δ j-1 , so with Lemma 5, we obtain : Λ α (d ′ ) -Λ α (d) > 0. Now that we have proved that Λ α is increasing, we can easily deduce that Λ α (E α ) ⊂ [0, 1[ : first, remark that (0, • • • , 0) is the lowest element of E α ( with ALO), so Λ α (d) 0 for all d ∈ E α . In addition, if j is even (-1) j-1 d j δ j-1 0 and if j is odd, say j = 2p + 1, with p a non negative integer, then (-1) j-1 d j δ j-1 a 2p+1 δ 2p , this inequality being strict for at least one p, so :

∀d ∈ E α , Λ α (d) < ∞ p=0 a 2p+1 δ 2p = ∞ p=0 (δ 2p-1 -δ 2p+1 ) = δ -1 = 1
For the surjectivity, we refer to Algorithm 3(ii) below. (iii) see proof of Proposition 3(ii).

Algorithm 3 . (i) the inverse function of Ψ α is defined by the following algorithm :

Let n ∈ N and r = max({k ∈ N, n < q k + q k-1 }). We define d by : ∀k > r, d k = 0 and

Input : n Output : (d i ) i∈{1•••r} for k = r to k = 1 with step -1 : d k = max 0, n-q k-2 q k-1 n ← n -d k q k-1
(ii) the inverse function of Λ α is defined by the following ( infinite) " algorithm" : Let β ∈ [0, 1[. We denote β 0 = β and define the sequences b = (b k ) k∈N * and (β k ) k∈N * by :

Input : β Output : (b i ) i∈N * for k = 1 to k = ∞ with step 1 : b k = min a k , β k-1 δ k-1 β k = b k δ k-1 -β k-1
Proof :

(i) see proof of Algorithm 1.

(ii) the proof that b ∈ E α is the same as the proof of Algorithm 2, with the additional argument : b does not end with (max, 0) ∞ , an infinite sequence of " (a k , 0)", that will be shown below. First, we remark that (β k ) k converges towards 0, for (-1)

k β k -(-1) k-1 β k-1 = (-1) k b k δ k-1
is the general term of a convergent serie. We can define β ′ = ∞ j=1 b j (-1) j-1 δ j-1 and verify that β ′ = β :

β ′ = ∞ j=1 (-1) j-1 (β j + β j-1 ) = β 0 = β
Suppose that b ends with (max, 0) ∞ : this means that, we have r ∈ N * , such that :

(r = 1 or b r-1 = 0) ; ∀p ∈ N, b r+2p = a r+2p ; b r+2p+1 = 0 So : β = r-1 j=1 b j (-1) j-1 δ j-1 + (-1) r-1 ∞ p=0 a r+2p δ r+2p-1 = r-1 j=1 b j (-1) j-1 δ j-1 + (-1) r-1 δ r-2 If r = 1, then β = δ -1 = 1, so r 2 and we recognize β = Λ α (b ′ ), where b ′ = (b 1 , • • • , b r-2 , b r-1 -1) ∈ E (α)
. Using the proof of Algorithm 2, we obtain β r-1 = 0, so b ends with an infinite sequence of " 0". We can sum up these formulae : for all non negative integers n, if we denote d = Ψ -1 α (n) :

n = ∞ j=1 d j q j-1 ; ⌊nα⌋ = ∞ j=1 d j p j-1 ; {nα} = ∞ j=1 (-1) j-1 d j δ j-1
Notations : if no ambiguity, we will denote n

= (d 1 , d 2 , • • • , d s ) α the Ψ α -numeration of an integer n and β = (b 1 , • • • ) α the Λ α -numeration of a real β of [0, 1[.
Remark 1 : we denote N α the completion of (N, D), where D is the distance defined by :

∀n, n ′ ∈ N, D(n, n ′ ) = |{n ′ α} -{nα}|
Proposition 4 proves that N α can be represented ( bijectively) by

E α : if n ∈ N α is represented by d ∈ E α then we could define : {nα} := ∞ j=1
(-1) j-1 d j δ j-1 . We obtain a bijective map :

N α → [0, 1[ ; n → {nα}
Remark 2 : in next subsection, we will study the effect of the symmetry β → 1 -β on α-numeration of reals of [0, 1[. But now, we are interested in this symmetry acting both on α and β, which gives a much simpler result : -first, let α be a real in ]0, 1/2[ and let us consider the CFE of α and 1 -α :

α = [a k ] k∈N ⇒ 1 -α = [0, 1, a 1 -1, a [2,∞] ] Indeed, if we denote 1 -α = [a ′ k ] k∈N , α 1 = [a [2,∞] ] and α ′ 1 = [a ′ [2,∞] ], then a ′ 0 = a 0 = 0, a ′ 1 = 1 and : α = 1 a 1 + α 1 ; 1 -α = 1 1 + α ′ 1 So : α ′ 1 = 1 1 -α -1 = 1 1 α -1 = 1 a 1 -1 + α 1 -secondly : let α ∈]0, 1/2[, β ∈]0, 1[ and (b k ) k its α-numeration, then : 1 -β = (1, b 1 -1, b [2,∞] ) 1-α
Indeed : if we denote δ ′ i the analoguous of δ i ( related to α) for 1 -α ( see above), then :

δ ′ -1 = 1 ; δ ′ 0 = 1 -α ; ∀i 1, δ ′ i = δ i-1
The last equality is obtained with obvious induction and previous result on CFE. Now, we just have to verify that :

δ ′ 0 -(b 1 -1)δ ′ 1 + i 2 (-1) i-1 b i-1 δ ′ i-1 = 1 -β
that is an easy calculation...

α-numeration of negative integers

Let α be an irrational in ]0, 1[ and [a k ] k∈N its CFE. We have seen at 2.3 that E α , the set of α-admissible sequences is in bijective correspondance with [0, 1[, via the following map :

Λ α : d = (d k ) k∈N * → ∞ k=1 d k δ ′ k-1
where δ ′ is the sequence defined by :

δ ′ -1 = -1 ; δ ′ 0 = α ; ∀k ∈ N * , δ ′ k = a k δ ′ k-1 + δ ′ k-2
with notations of 2.3, we have :

∀k ∈ {-1 • • • + ∞}, δ ′ k = q k α -p k = (-1) k δ k
In addition δ ′ converges towards 0 and we could set δ ′ ∞ = 0.

In order to define the α-numeration of negative integers, we consider the natural involution of [0, 1[, that we denote C : the complement to 1.

C : C(0) = 0 ∀x ∈]0, 1[, C(x) = 1 -x We also have : ∀x ∈ [0, 1[, C(x) = {-x}.
We can see C as the usual conjugacy over the unit circle U, the set of complex of moduli one, via the bijection : [0, 1[→ U, x → e 2iπx . C is decreasing, when restricted to ]0, 1[. Question : is there a simple and natural expression of conjugate involution C α of E α , induced by C, via Λ α , that is :

C α = Λ -1 α • C • Λ α
Thinking of the analoguous problem for usual (b k ) k basis-numeration, where b is an integer bigger than 1, we could try to use a kind of " complement to (a k ) k∈N * " transformation. Indeed, (a k ) k∈N * is the biggest sequence in E α for the usual lexicographic order. But, we also have to add 1 to the first digit, so, let m be the following sequence :

m 1 = a 1 + 1 ; ∀k > 1, m k = a k
We extend the definition of Ψ α to all real sequences in l

1 (δ ′ ) = {u ∈ R N * , k |u k δ ′ k | < +∞}. L α : l 1 (δ ′ ) → R; d → ∞ k=1 d k δ ′ k-1
Then, L α (m) = 1, for :

∞ k=1 m k δ ′ k-1 = α + ∞ k=1 a k δ ′ k-1 = α + ∞ k=1 (δ ′ k -δ ′ k-2 ) = α -δ ′ -1 -δ ′ 0 = 1
Since L α is linear, we have :

∀d ∈ l 1 (δ ′ ), L α (m -d) = 1 -L α (d)
In particular, for d ∈ E α , we obtain :

L α (m -d) = 1 -Ψ α (d).
So, the question is : do we always have m -d ∈ E α ? Unfortunately, no. But, m -d ∈ E α in most cases.

First, since d does not end with (max, 0) ∞ ( see 1.2), that is also the case for m -d.

Secondly, if d is not the null sequence, then m k -d k ∈ {0 • • • a k } for all k ∈ N * , and m 1 -d 1 > 0.
Finally, the only case where d ∈ E α and m -d ∈ E α is when m -d contains a finite word of consecutive 0, that is not preceeded by a maximal digit ( say d k = a k ) and that is not succeeded by a 0. We will name such a word, a not admissible word. Such a word can appear in m -d, for d can contain a word with consecutive maximal digits.

We will see below how to convert such a sequence into an α-admissible sequence. First, let ∼ denote the equivalence relation on l 1 (δ ′ ), induced by L α :

∀u, v ∈ l 1 (δ ′ ), u ∼ v ⇔ L α (u) = L α (v)
This relation ∼ is compatible with the linear structure of l 1 (δ ′ ).

We have, for all r, s ∈ N * :

(0 r , 1, (max, 0) s-1 , max, -1, 0 ∞ ) ∼ 0 ∞ (1)
Indeed :

L α ((0 r , 1, (max, 0) s-1 , max, -1, 0 ∞ )) = δ ′ r + s k=1 a r+2k δ ′ r+2k-1 -δ ′ r+2s = = δ ′ r + s k=1 (δ ′ r+2k -δ ′ r+2k-2 ) -δ ′ r+2s = 0
Case 1 : a list of an even number of consecutive 0 ( not preceeded by a maximal digit and not succeeded by a 0). So, if we have a sequence (e k ) k , such that e Then, adding (e k ) k to relation (1), we obtain :

(e k ) k 1 ∼ (e [1,r] , 1, (max, 0) s-1 , max, e r+2s+1 -1, e [r+2s+2,∞] )
Thus, the new sequence (e ′ k ) k only contains admissible words in its first r + 2s + 1 digits.

Case 2 : a list of an odd number of consecutive 0 ( not preceeded by a maximal digit and not succeeded by a 0). So, if we have a sequence (e k ) k , such that e [1,r] only contains admissible words and such that e r = a r , e r+2s = 0 and e k = 0 for k ∈ {r

+ 1 • • • r + 2s -1} ( r, s ∈ N * ).
Then, adding (e k ) k to relation (1) ( with r -1 instead of r), we obtain :

(e k ) k 1 ∼ (e [1,r-1] , e r + 1, (max, 0) s-1 , max, e r+2s -1, e [r+2s+1,∞] )
Thus, the new sequence (e ′ k ) k does not contain any not admissible word in its first r +2s digits.

In both cases, we have converted the not admissible word of (e k ) k into an admissible word, giving the same image for L α . This provides a ( possibly infinite) process to convert any not admissible element of m -E α into an element of E α . We only have to browse once the sequence (e k ) k to convert it into an equivalent α-admissible sequence :

Process of conversion : let d denote an α-admissible sequence that is not the null sequence and e = m -d. Then

e ∈ {1 • • • a 1 } × k>1 {0 • • • a k }.
We denote (r j ) j and (s j ) j the sequences of positive integers such that, the finite lists of consecutive 0 in e are for indices from r j + 1 to r j + 2s j or r j + 2s j -1, depending on the parity of the lengths (l j ) j of these lists. We apply then the inductive following process :

We suppose that we have converted the digits of e for the indices k r j . Then : we can suppose that e r j < a j ( if e r j = a j , then we change r j ← r j + 1) and e r+l j +1 > 0.

-Case 1 : if l j is even, then : e ← (e [1,r j ] , 1, (max, 0) s j -1 , max, e r j +2s j +1 -1, e [r j +2s j +2,∞] ) -Case 2 : if l j is odd, then : e ← (e [1,r j -1] , e r j + 1, (max, 0) s j -1 , max, e r j +2s j -1, e [r j +2s j +1,∞] ) So, this process explicits the map C α , that is the relation between the α-numerations of β and 1 -β for a real β ∈]0, 1[. We will name this map : CFE-complement. Now, let us consider the particular case of β = {nα}, where n ∈ N * . We have seen in 2.3 that n and β have the same α-numeration. Since {-nα} = 1 -β, it is natural to define the α-numeration of -n as follows :

Definition 5 (α-numeration of a negative integer) . for any positive integer n, we define the α-numeration of -n as the CFE-complement of the α-numeration of n.

Notations : we denote E c (α) the subset of E α of sequences ending with max ∞ , that is to say :

E c (α) = {e ∈ E α , ∃k ∈ N, ∀i > k, e i = a i } We have then E c (α) = C α (E (α)
) and E c (α) is the set of α-admissible sequences that " α-numerate" negative integers ( see Proposition below).

We will also denote F α = E (α) ∪ E c (α) and we extend RLO, that we defined on E (α) , to F α :

∀d, d ′ ∈ F α , d < R d ′ ⇔ ∃k ∈ N * , ((d k < d ′ k , ∀i > k, d i = d ′ i ) or (∀i k, d i = a i , d ′ i = 0
)) Remark : the above process of conversion is, in that frame, an algorithm, since an element of E c (α) only contains a finite number of lists of consecutive 0.

Proposition 5 we can extend Ψ α from E (α) to F α as follows :

∀e ∈ E c (α) , Ψ α (e) = -1 - ∞ k=1 (a k -e k )q k-1
hence, Ψ α is an order isomorphisme from (F α , R ) to (Z, ) and we still have :

∀n ∈ Z, Λ α ( Ψ -1 α (n)) = {nα} Proof :
-Formula and injectivity : let e ∈ E c (α) . First, we remark that the sum in the definition of Ψ α (e) is finite, since e k = a k for k large enough. Let denote d = m -e and :

n = ∞ k=1 d k q k-1 ; β = ∞ k=1 d k δ ′ k-1
Now, Ψ α (e) = -n and n is a positive integer ( d ends with 0 ∞ and d 1 > 0), so Ψ α (e) ∈ Z * -. But d is not always in E (α) . Nevertheless β ∈]0, 1[ for :

β = L α (d) = L α (m) -L α (e) = 1 -Λ α (e)
indeed, e ∈ E α . Finally :

nα -β = ∞ k=1 d k p k-1 ∈ N so : β = {nα}. We obtain : Λ α (e) = 1 -β = {-nα}. We can conclude : ∀e ∈ F (α) , Λ α (e) = { Ψ α (e)α} (1) Since, Λ α is injective, we deduce that Ψ α is injective. -Surjectivity : let n ∈ N * , d = Ψ -1 α (n) and e = Λ -1 α (1 -{nα}).
Then, e ∈ E c (α) ( see the beginning of this section) and, with (1) :

Λ α (e) = { Ψ α (e)α} = 1 -{nα} = {-nα} So, Ψ α (e) = -n, for Ψ α (e) ∈ Z. So, Ψ α is surjective. -Increase : let e, e ′ ∈ E c (α) such that e < R e ′ . -Case 1 : if e ∈ E c
(α) and e ′ ∈ E (α) , then Ψ α (e) < 0 Ψ α (e ′ ). -Case 2 : if e, e ′ ∈ E (α) , we have proved in Proposition 2 that Ψ α (e) < Ψ α (e ′ ).

-Case 3 : if e, e ′ ∈ E c (α) , then :

Ψ α (e ′ ) -Ψ α (e) = ∞ k=1 (e ′ k -e k )q k-1 = Ψ α (d ′ ) -Ψ α (d) where d = ((e k ) k∈{1•••r} , 0 ∞ ) and d ′ = ((e ′ k ) k∈{1•••r} , 0 ∞ ), the integer r being such that e ′ i = e i = a i for i > r. Since e, e ′ are α-admissible, we can claim that d, d ′ ∈ E (α) . So, with Proposition 2, Ψ α (d ′ ) -Ψ α (d) > 0. So, Ψ α (e ′ ) -Ψ α (e) > 0.
We have proved that Ψ α is increasing on F α .

Note that the definition of Ψ α in Proposition 5 could be given by the same formula for d in E (α) and for d in E c (α) , with the following convention : +∞ = 0, so that q n ---→ n→∞ 0. Indeed, if we define :

∀d ∈ F α , Ψ α (d) = ∞ k=1 d k q k-1 then, it is convenient, since : ∞ k=1 a k q k-1 = ∞ k=1 (q k -q k-2 ) = 0 + 0 -q 0 -q -1 = -1
We also have, with this convention a coherent result for both " improper expansions" of an integer n, herited from improper expansions of {nα} ( see remark 2, below Proposition 4), whose proper expansion is (d

1 , d 2 , • • • , d r ) with d r > 0. Indeed, these improper expansions are (d [1,r] , 1, (max, 0) ∞ ) and (d [1,r-1] , d r + 1, (max, 0) ∞ ) ( if d r < a r ) or (d [1,r] , 0, 1, (max, 0) ∞ ) ( if d r = a r ). Moreover : ∀s ∈ N, ∞ j=0 a s+2j+1 q s+2j = ∞ j=0
(q s+2j+1 -q s+2j-1 ) = 0 -q s-1 3 Complements

dynamic generating α-numeration

• What follows is inspired by the analoguous result for the usual Ostrowski numeration made by Ito in [START_REF] Ito | some skew product transformations associated with continued fractions and their invariant measures[END_REF] : Proposition 6 let α be an irrational and [a k ] k∈N its CFE. Let β ∈ [0, 1[ and (b k ) k its αnumeration. We have :

∀k ∈ N * , (a k , b k ) = AH k-1 (α, β)
where H is a self map of the open trapezoid U defined by : for (x,

y) ∈ R 2 (x, y) ∈ U ⇔ 0 < x < 1 -x < y < 1 H : (x, y) → 1 x , min 1 x , y x - y x A : (x, y) → 1 x , min 1 x , y x
Remark 1 : we could prefer the following expressions, distinguishing two cases :

∀(x, y) ∈ U, A(x, y) = (⌊1/x⌋, ⌈y/x⌉) ; H(x, y) = ({1/x}, {-y/x}) if y x⌊1/x⌋ A(x, y) = (⌊1/x⌋, ⌊1/x⌋) ; H(x, y) = ({1/x}, {-y/x} -1) else Indeed, if y > x⌊1/x⌋, then : ⌊1/x⌋ < y/x < 1/x, so ⌊1/x⌋ = ⌈y/x⌉ -1.

Proof :

we denote (α k , γ k ) = H k (α, β) for all k ∈ N. We avoid here the notation β k for it is used below as reference to Algorithm 3. We already know that a k = p x (AH k-1 (α, β)), where p x : (x, y) → x, since T (x) = p x (H(x, y)) for all x, y ∈]0, 1[ ( T is the Gauss map, see 1.3). By definition, we have :

γ 0 = β ; ∀k ∈ N * , γ k = min(a k , ⌈γ k-1 /α k-1 ⌉) - γ k-1 α k-1 We denote γ ′ k = β k δ k-1
, with notations of Algorithm 3 ( see 2.3). We also have :

∀i ∈ N, α i = T i (α) = δ i δ i-1 so γ ′ i α i = β i δ i
Thus, according to Algorithm 3 on reals :

∀k ∈ N * , b k = min(a k , ⌈β k-1 /δ k-1 ⌉) ; β k = b k δ k-1 -β k-1
We deduce :

∀k ∈ N * , γ ′ k = b k - γ ′ k-1 α k-1
Yet, γ ′ 0 = β = γ 0 and we obtain, by obvious induction :

γ k = γ ′ k for all integer k ∈ N. Then : ∀k ∈ N * , b k = min(a k , ⌈γ k-1 /α k-1 ⌉)
This ends the proof.

α-germs and orbits of α-rotation

Our α-numeration is related to f α , the rotation on the circle R/Z defined by :

∀x ∈ R/Z, f α (x) = α + x ( mod 1)
Let α be an irrational and [a k ] k its CFE. We know that f α is topologically transitive : its orbits are dense in X = R/Z. Moreover, it is uniquely ergodic : there is only one f α -invariant ( and ergodic) measure on X : the Lebesgue measure. Now, we will explicit the conjugate of f α on E α , namely the map g α : E α → E α , such that :

Λ α • g α = f α • Λ α
We remind some notations : E α is the set of α-admissible sequences and

F α = E (α) ∪ E c (α)
, where

E (α) = {(d k ) k ∈ E α , ∃n ∈ N, ∀k > n, d k = 0} ; E c (α) = {(d k ) k ∈ E α , ∃n ∈ N, ∀k > n, d k = a k }
We will use an equivalence relation on E α , that defines the notion of germ of a sequence :

∀d, d ′ ∈ E α , d d ′ ⇔ ∃k ∈ N, ∀i > k, d i = d ′ i
We remark that the class of ( 0) is E (α) and that the class of (a k ) k∈N * is E c (α) . More generally, we can extend RLO to each class of germs of E α , as follows :

(d k ) k < R (d ′ k ) k ⇔ ∃j ∈ N * , d j < d ′ j ∀k > j, d k = d ′ k
Remark : for each class of germs of E α , RLO is a total order and every element of the class has a successor ( except for E c (α) , where (a k ) k∈N * is the maximal element) and a predecessor ( except for E (α) , where (0) is the minimal element).

• The following Proposition explicits the orbits of g α . Before that, we remark that : for β, β ′ ∈ R/Z, β and β ′ are in the same orbit of f α if and only if it exists n ∈ Z, such that β ′ -β = nα mod 1. So, an orbit of g α is the set of α-numerations of the {β + nα}, n ∈ Z, for some β ∈ [0, 1[. Proposition 7 Let α be an irrational, [a k ] k its CFE and g α defined as above, then : (i) the orbits of g α are exactly the classes of germs of E α , except for the orbit of (0), that is F α . (ii) g α is the successor map on each of theses classes ( with RLO).

Proof :

First, the class of (0), via g α , is F α , the set of α-numerations of the {nα}, n ∈ Z, as we have seen in previous subsection 3.

β ′ -β = r k=1 (b ′ k -b k )δ ′ k-1
but, δ ′ i = αq i -p i and q i , p i are integer for all i ∈ N. So, β ′ -β ∈ Z + αZ and we conclude that β ′ is in the f α -orbit of β and that b ′ is in the g α -orbit of b.

Conversely, suppose that b ′ is in the g α -orbit of b. We want to show that b and b ′ have the same germ. By obvious induction, it suffices to show that this is the case for b ′ = g α (b), that is to say for β ′ = β + α. But, since b is not (a k ) k , then there exists an index r such that b r < a r . We denote

d = (b [1,r] , 0 ∞ ). Then, the successor of d in (E (α) , RLO) is d ′ such that d ′ i = 0 for all i > r. We claim now that b ′ = (d ′ (1,r] , b [r+1,∞] ). Indeed, b ′ ∈ E α and : Λ α (b ′ ) -Λ α (b) = Λ α (d ′ ) -Λ α (d) = α
So, b ′ and b have the same germ. By the way, we have also proved that g α is the successor map on the class of germ of b.

Remark 1 : this proves that R/(Z + αZ) is represented, via our α-numeration Λ α , by germs of sequences of E α .

Remark 2 : we can define, on each orbit X of f α , a natural order, which makes them isomorphic to (Z, ) ( but not canonically) :

∀x, x ′ ∈ X, x x ′ ⇔ ∃n ∈ N, x ′ = f n α (x)
In the same way, each class of germ of (E α , RLO) ( except for the class of (0), where we consider F α ) is isomorphic to (Z, ).

• Now, we define, for any x in R, ||x||, the distance of x to Z. We also have : ||x|| = min({x}, {-x}). Later, we define several maps on R by : for all

β ∈ R D α (β) = lim inf n→+∞ (n||nα -β||) ; D + α (β) = lim inf n→+∞ (n{nα -β}) ; D - α (β) = lim inf n→+∞ (n{β -nα}) Remark 3 : D α = min(D + α , D - α )
, for lim inf " respects" the min.

Remark 4 : these 3 maps are f α -invariant. Indeed, if x ∈ R, then :

∀n ∈ N * , n{nα -(x + α)} = {(n -1)α -x} = j + 1 j × j{jα -x}
where j = n -1. But, j+1 j converges to 1 as j tends to infinity, so the lim inf is the same... This proves that these maps could be defined on R/(Z + αZ), the additive group of orbits of f α and so they only depend on the germ of the α-numeration of β ∈ R/Z. In other words, these maps only depand on the asymptotic behaviour of the α-numeration of β.

It is well known that D α (0) is null if and only if the sequence of partial quotients of α is unbounded and that D α (0) can be defined, restricting n to the denominators of convergents of α. But, we have more precise results :

lim inf n→+∞ 1 a n + 2 D α (0) lim inf n→+∞ 1 a n
Moreover, Dirichlet's theorem on diophantine approximation gives ( see [START_REF] Cassels | an introduction to Diophantine approximation[END_REF]) :

∀β ∈ R, D α (β) 1
And Minkowski has proved that ( see [START_REF] Cassels | an introduction to Diophantine approximation[END_REF] again) :

∀β ∈ R\(Z + αZ), min(D α (β), D α (1 -β)) 1 4
In 4.3, we give some results that helps to compute D + α (β) and D - α (β), in relation to the α-numeration of β.

shift and inductive structure

• Let α be a real in [0, 1[ and [0, a 1 , a 2 , • • • ] its CFE. We denote a = (a 1 , • • • ) and σ the usual shift on sequences. We have seen that : if α is not null, then [0, σ(a)] is the CFE of T 1 (α), where T 1 is an extension of the Gauss map, described in 1.3. We recall that µ(α) = +∞ if α is not rational and µ(α) = r if α is rational and its CFE is [0, a 1 , • • • , a r , 1]. We define inductively the sequence : (α k ) k by :

α 0 = α ; ∀k ∈ {1 • • • µ(α)}, α k = 1 α k-1
With the remark above, we obtain :

∀k ∈ {0 • • • µ(α) -1}, α k = [0, a k+1 , • • • ] = [0, σ k (a)]
Moreover, if α is rational and r = µ(α), then α r = 0, for α r-1 = [0, a r , 1] = 1 ar+1 .

According to the definition of the sets (E α k ) k , we can claim :

∀b ∈ E α , ∀k ∈ N, (σ k (b) ∈ E α k ⇔ b k+1 = 0 or σ k (b) = (0))
In particular :

E T (α) ⊂ σ(E α ) and σ(E α )\E T (α) = {0} × (E T 2 (α) \{(0)})
In addition, if we denote for any k ∈ {0 • • • a 1 -1} : -E α,k : the set of α-admissible sequences whose first digit is k. We have E α,0 = {(0)}.

-E α,a 1 : the set of α-admissible sequences whose first digit is a 1 and second is non null, except for (a 1 , 0, 0, • • • ), that is in this set. -E ′ α,a 1 : the set of α-admissible sequences whose first digit is a 1 and second is null, except for (a 1 , 0, 0, • • • ), that is not in this set.

(E α,k ) k∈{0•••a 1 } ∪ E ′
α,a 1 is clearly a partition of E α and ALO induces an order on these subsets : ( where B < A B ′ means that for every b ∈ B and b

′ ∈ B ′ , we have b < A b ′ ) E α,0 < A E α,1 < A E α,2 < A • • • < A E α,a 1 < A E ′ α,a 1 Lemma 6 . (i) for any k ∈ {1 • • • a 1 }, the map ( see below) is a bijective decreasing map ( induced by σ). σ k : (E α,k , A ) → (E T (α) , A ) (k, d [2,∞] ) → (d [2,∞] )
(ii) the map ( see below) is a bijective increasing map ( induced by σ 2 ).

σ (2) :

(E ′ α,a 1 , A ) → (E T 2 (α) \{(0)}, A ) (a 1 , 0, d [3,∞] ) → (d [3,∞] ) Proof :
direct consequence of former remarks and definition of sets E α and ALO.

So to say, (E α , < A ) consists in one null element, followed by a 1 ordered copies of (E T (α) , < A ′ ) and, at the end a copy of (E T 2 (α) \{(0)}, < A ), where < A ′ denotes inversed ALO.

We also define a sequence (γ k ) k of reals :

γ 0 = β ; ∀k ∈ {1 • • • µ(α)}, γ k = 1 α k-1 (b k α k-1 -γ k-1 ) Lemma 8 let k ∈ {0 • • • µ(α) -2}. ⊲ Case 1 : if b k+1 = 0 or σ k (b) = (0), then γ k = (b [k+1,∞] ) α k = σ k (b) α k . ⊲ Case 2 : else γ k < 0 and γ k+1 = (b [k+2,∞] ) α k+1 = σ k+1 (b) α k+1 .
Proof :

we will use same notations as in previous proof. First, we remark that ( by obvious induction) :

∀x ∈]0, 1[, ∀i ∈ N, q i (x) = a 1 (x)q i-1 (T (x)) + p i-1 (T (x)) ; p i (x) = q i-1 (T (x))
We denote r = µ(α) and argue with induction on k. It is clear for

k = 0. Suppose it is true for k -1, with k ∈ {1 • • • r -2}. -if b k = 0 or σ k-1 (b) = (0), then γ k-1 = (b [k,∞] ) α k-1 . So : γ k-1 = r j=k b j [α k-1 q j-k (α k-1 ) -p j-k (α k-1 )] = r j=k b j [α k-1 (a k q j-k-1 (α k ) + p j-k-1 (α k )) -q j-k-1 (α k )]
The term of the above sum for j = k is equal to b k α k-1 , so :

γ k = 1 α k-1 (b k α k-1 -γ k-1 ) = r j=k+1 b j q j-k-1 (α k ) α k-1 -(a k q j-k-1 (α k ) + p j-k-1 (α k )) But, 1 α k-1 = a k + α k , so : γ k = r j=k+1 b j [α k q j-k-1 (α k ) -p j-k-1 (α k )]
γ k = r j=k+2 b j [α k q j-k-1 (α k ) -p j-k-1 (α k )]
so :

γ k+1 = - γ k α k = r j=k+2 b j p j-k-1 (α k ) α k -q j-k-1 (α k ) = r j=k+2 b j [α k+1 q j-k-2 (α k+1 ) -p j-k-2 (α k+1 )]
the last equality is obtained as above in Case 1... Now, (b [k+2,r] ) ∈ E α k+1 and γ k+1 = (b [k+2,r] ) α k+1 . We deduce that γ k+1 ∈]0, 1[ and γ k < 0.

-if b k = 0 and b k+1 = 0, then, with induction hypothesis, we obtain the result since we are in Case 1.

Remark : for a positive integer n, we have ⌊nα⌋ < ⌊nα ′ ⌋ if and only if there exists an integer p such that α < p/n α ′ .

Proof :

(i) is a consequence of the remark.

(ii) the best rational in ←→ [α, p/q] is the common semi-convergent of α and p/q, that has the greatest denominator ( see Proposition 1 (iii)). But, semi-convergents of p/q are either p/q or p ′ /q ′ where p ′ , q ′ are integers such that 1 q ′ < q. So, we have two cases.

If p/q is a semi-convergent of α, then there are no integers a, b such that b ∈ {1 • • • q -1} and α < a/b p/q or p/q < a/b α. The previous remark implies ⇒ of (ii).

If p/q is not a semi-convergent of α, then the best rational in ←→ [α, p/q] is p ′ /q ′ with p ′ , q ′ two integers such that 0 < q ′ < q. If p/q < α then p/q < p ′ /q ′ α and we use remark 2. Else, since α is not the nearest left strict convergent of p/q, we have p", q" two integers such that α < p"/q" < p/q and 0 < q" < q. We conclude with remark 2.

• We also have direct consequences for sums of ⌊kα⌋ and {kα} : we will denote

∀n ∈ N, ∀x ∈ R, I n (x) = n-1 k=0 ⌊kx⌋ ; F n (x) = n-1 k=0 {kx}
Obviously, F n is 1-periodic, I n is non decreasing and :

∀n ∈ N, ∀x ∈ R, I n (x) + F n (x) = n(n -1)x 2 (1)
Moreover, let p, n be 2 positive integers and d = gcd(p, n). We denote n ′ = n/d and p ′ = p/d. Then n ′ and p ′ are coprime, so

kp ′ n ′ , k ∈ {0 • • • n ′ -1} = j n ′ , j ∈ {0 • • • n ′ -1} . So, we have, since kp ′ n ′ k is n ′ -periodic : ∀p, n ∈ N * , F n p n = n -gcd(p, n) 2 (2)
We also have, for two reals x and x ′ :

I n (x) = I n (x ′ ) ⇔ ∀k ∈ {0 • • • n -1}, ⌊kx⌋ = ⌊kx ′ ⌋
So, Proposition 8 gives : I n (x) = I n (x ′ ) if and only if n is lower or equal to the denominator of the reduced best rational in ]x, x ′ ], if x < x ′ .

In [START_REF] Brown | sums of fractional parts of integer multiples of an irrational[END_REF], we can find an expression of I n (x) and F n (x) in terms of the Ostrowski x-numeration of n. In what follows, we restrict ourselves to a special case : Corollary 4 Let α be a real and p/q a fraction of integers, such that α is not the nearest left strict convergent of p/q. p q a reduced semi-convergent of α ⇔ q-1 k=0 ⌊kα⌋ = (p -1)(q -1) 2

Proof :

direct consequence (1),(2) and Proposition 8 (ii).

Remark :

we deduce an expression of the mean value of ({kα}) 1 k<q if p q is a reduced semi-convergent of α : 1 q -1 Let α be a real, [a k ] k∈N * its CFE and r = µ(α), the CFE-depth of α. So, we denote [a 0 , a 1 , • • • , a r , 1] the CFE of α if α is rational. We also denote (p n /q n ) n the usual sequence of convergents of α. We consider points of R 2 with the product order : (x, y) (x ′ , y ′ ) if and only if x x ′ and y y ′ .

We recall some notations mentioned at 3.2 : for any x in R, ||x||, the distance of x to Z. We also have : ||x|| = min({x}, {-x}). Remarks : we could also consider approximations of β by nα mod 1, for negative integers n.

Best sided α-approximations of a real are easier to describe than best α-approximations. But, there is a simple relation : a best α-approximation is also a best right or left α-approximation of β.

First, we remark that these notions are closely related to minimal points in R the respective α-numeration of ν and β. We denote σ the usual shift on sequences. We will also use the two total orders on finite sequences of reals : RLO, denoted R and ALO, denoted A ( see 1.2 and 2.3).

We also denote :

N (α, β, ν) = {k ∈ {0 • • • ν -1}, {kα} < β} ; E(α, β, ν) = {d ∈ E (α) , d < R n and d < A b}
With the results of section 2.3. we can claim that : Ψ α gives a one to one correspondance between N (α, β, ν) and E(α, β, ν). We will denote C(α, β, ν) the cardinality of these finite sets.

We will denote α = [a k ] k∈N the CFE of α ( with a 0 = 0) and r the CFE depth of α ( r = +∞ if and only if α is irrational). We suppose ν q if α is a rational and p/q is a reduced fraction that represents α. As in section 3.3, we use the following notations :

α 0 = α ; ∀k ∈ {1 • • • r}, α k = 1 α k-1 ν 0 = ν ; ∀k ∈ {1 • • • r -2}, ν k = ⌊ν k-1 α k-1 ⌋ if n k = 0 or n k+1 = 0 ⌊ν k-1 α k-1 ⌋ + 1 else β 0 = β ; ∀k ∈ {1 • • • r}, β k = 1 α k-1 (b k α k-1 -β k-1 )
Remark 1 :

d ∈ E (α) ⇔ d = (0) or d 1 ∈ {1 • • • a 1 } σ(d) ∈ E (α 1 ) or      d 1 = a 1 d 2 = 0 σ 2 (d) ∈ E (α 2 ) \{(0)}
These three cases are exclusive.

  [1,r] = [e 1 , • • • , e r ] only contains admissible words and such that e r = a r , e r+2s+1 = 0 and e k = 0 for k ∈ {r + 1 • • • r + 2s} ( where r, s ∈ N * ).

Remark 2 :

 2 let us verify that H(U ) ⊂ U : if y x⌊1/x⌋, that is obvious. Else, {-y/x} -1 = -{y/x} > -{1/x}, for ⌊1/x⌋ < y/x < 1/x and so {y/x} < {1/x} ( see remark 1).

1 .

 1 Let β ∈ [0, 1[ such that β ∈ {{nα}, n ∈ Z}. We denote b = (b k ) k its α-numeration and C the class of germ of b in E α .If b ′ ∈ C, then we have an integer r ∈ N, such that b ′ i = b i for all integer i > r. We denote β ′ = Λ α (b ′ ), then :

Case 1 :

 1 b k+1 = 0 or b k+2 = 0 : we recognize the α k -numeration of γ k , since (b [k+1,r] ) ∈ E α k , with our hypothesis. Case 2 : b k+1 = 0 and b k+2 = 0, then (b [k+1,r] ) ∈ E α k and :

-p 2 4. 3

 23 best left or right α-approximation of a real in [0,1[

Definition 6 (

 6 best α-approximation of a real) . let α and β be two reals in [0, 1[ and n a non negative integer. ⊲ {nα} is a best α-approximation of β if and only if :∀k ∈ {0 • • • n -1}, ||nα -β|| < ||kα -β|| ⊲ {nα} is a best right ( resp. left) α-approximation of β if and only if : ∀k ∈ {0 • • • n -1}, {nα -β} < {kα -β} ( resp. {β -nα} < {β -kα})

2

 2 of sequences ({nα -β}, n) n∈N and ({β -nα}, n) n∈N : best right ( resp. left) α-approximations of β are obtained for the values of n such that ({nα -β}, n) ( resp. ({β -nα}, n)) is a minimal point of the sequence ({kα -β}, k) k∈N ( resp. ({β -kα}, k) k∈N ).Moreover :∀x ∈ R, {x -β} = {x} -β ∈ [0, 1 -β[ if {x} β {x} + 1 -β ∈ [1 -β, 1[ if {x} < βFinally : (1 -β, 0) is a trivial minimal point of ({nα -β}, n) n∈N , so the other minimal points must verify {nα} β.Proposition 9 (best right ( positive) α-approximations) . ⊲ Case 1 : α is rational and [0,a 1 , • • • , a r , 1] is its CFE. We suppose that β ∈ {{nα}, n ∈ N} and denote (b 1 , b 2 , • • • , b r ) the α-numeration of β ( see 2.2).Best right ( positive) α-approximations of β are the {nα} for n = 0, for n = r i=1 b i q i-1 and for the following n :n = 2k-1 i=1 b i q i-1 + jq 2k-1 ; j ∈ {0 • • • b 2k -1} ; k ∈ {1 • • • ⌊r/2⌋} ⊲ Case 2 : if α is irrational and [a k ] k∈Nis its CFE. Let β be a real in [0, 1[ and (b k ) k∈N * its α-numeration. ( see 2.

3 )

 3 Best right ( positive) α-approximations of β are the {nα} for n = 0, for n = s i=1 b i q i-1 , if b k = 0 for all integer k > s, and for the following n :n = 2k-1 i=1 b i q i-1 + jq 2k-1 ; j ∈ {0 • • • b 2k -1} ; k ∈ N * 4.4 measure of repartition of ({kα}) 0 k<ν• If α is an irrational, we know that the sequence of probability measures (µ n ) n defined as below converges ( for weak-star topology) to the Lebesgue measure.∀ν ∈ N * , µ ν = 1 νwhere D x is the Dirac-measure in x.Can we precise these measures ? That is the aim of the following study. It is sufficient to give an expression of µ ν ([0, β[), where β is any real of [0, 1[. So, we want to count integers k in {0 • • • ν -1}, such that, given a real β in [0, 1[, we have {kα} < β.• Another approach of this question is the following : note L the lattice in R 2 generated by (1, 0) and (α, 1). What is the cardinality of L ∩ R, if R is the rectangle : R = [0, β[×[0, ν[ ? • For two reals α and β in [0, 1[ and for a positive integer ν, we denote n = (n k ) k and b = (b k ) k

Remark 2 :

 2 let d ∈ E (α) , then :d < R n ⇔ σ(d) < R σ(n) or (σ(d) = σ(n) and d 1 < n 1 ) d < A b ⇔ d 1 < b 1 or (d 1 = b 1 and σ(b) < A σ(d))

We deduce a result on Kronecker sequences : Corollary 3 let α be a real in [0, 1[, T the usual Gauss map x → {1/x}. We denote a 1 = ⌊1/α⌋ and K α = {{kα}, k ∈ N}.

The following union are disjoint :

direct consequence of Lemma 6

• Now, we would like to specify the effect of the shift on the integers and reals of [0, 1[, via their α or T (α)-numerations.

We define a sequence of integers (ν k ) k by :

-2} and n = (n i ) i the α-numeration of ν ( we denote ν = (n) α for example these numeration...)

Proof :

we will denote p k (x) and q k (x) for the reduced of the k th convergent of a real x, for any non negative integer k and [a 0 (x), a 1 (x), • • • , a k (x), ...] its CFE. We have remarked that, if we denote T (x) = 1 {x} , then : ∀j ∈ N * , a j (T (x)) = a j+1 (x)

By obvious induction, we can deduce that :

∀x ∈ [0, 1[, ∀j ∈ N, q j-1 (T (x)) = p j (x)

We denote r = µ(α). Now, we will use an induction on k ∈ {0 • • • r -2}. Result (i) is true for k = 0 ( we are in Case 1) . Suppose it is true for k -1, where k ∈ {1 • • • r -2}, then :

with n ′ k = 1 or n k , but n ′ k > 0 in all cases. ◮ Case 1 : if n k+1 = 0 or σ k (n) = (0), then : with the formula that follows the proof of Algorithm 3 and (1) :

4 Order properties of Kronecker sequences 4.1 a one-page proof of the "three distance theorem"

In this section, we will be interested in lengths of subdivisions of [0, 1] by finite sets {{kα}, k ∈ {1 • • • N -1}}, where α is a real in [0, 1[ and N a positive integer.

Let us remark that, if we consider subdivisions of the circle S 1 , that is to say of R/Z, then their lengths are invariant by translations. In that case, subdivisions by sets like {{kα + β}, k ∈ {0 • • • N -1}} are the same, from a metric point of view, for all real β.

The well known 3 distance theorem ( see [START_REF] Sòs | on the distribution mod 1 of the sequence n α[END_REF]) claims that these subdivisions are quite simple : they all contains at most 3 different lengths, one being the sum of the others :

Let α be a real in [0, 1[, with CFE [a k ] k . We denote, as usual, p n /q n the reduced fraction of the convergent [a 0 , • • • , a n ] and δ n = (-1) n (αq n -p n ). We remind that (δ n ) n is a positive and decreasing sequence that converges towards 0 ( if α is irrational).

Let N be a positive integer. If α is rational, we suppose that N q, where q is the denominator of the reduced fraction of α. So, the set {{kα}, k ∈ {0 • • • N -1}} contains exactly N elements.

of length taking at most 3 values, one being the sum of the others.

We can precise a bit : let s be the lowest integer such that N q s + q s-1 , then :

, the lengths of above intervals take 2 values :

, the lengths of above intervals take 3 values : δ s-1 , δ s + iδ s-1 and δ s + (i + 1)δ s-1

Proof :

According to propositions 2 and 4, algorithm 1 and 3, we can write : N -1 = (n 1 , • • • , n s ) α , with n s = 0. Let denote (u j ) j∈{0•••N -1} the increasing sequence that enumerates our set {{kα}, k ∈ {0 • • • N -1}}. We have u 0 = 0 and denote u N = 1. The aim of this result is to prove that u j -u j-1 take at most 3 values, when j ranges over {1 • • • N }.

We will denote E(N ) the set of α-admissible sequences that are lower or equal, for RLO, than (n i ) i . These sequences are the α-numeration of integers of {0

We denote j the integer such that u j = {kα}. Then u j-1 = {k ′ α}, where k ′ = ((k ′ i ) i ) α and (k ′ i ) i is the predecessor of (k i ) i in (E(N ), ALO). In a similar way u j+1 = {k"α}, where k" = ((k" i ) i ) α and (k" i ) i is the successor of (k i ) i in (E(N ), ALO).

We will suppose that s is even, because the other case can easily be deduced ( see end of the proof).

Then, K ′ ∈ E(N ) and K ′ is the predecessor of (k i ) i in (E(N ), ALO). So :

We denote t the greatest odd integer i such that

). That is to say if and only if :

So, the length δ s-2 -n s δ s-1 always occur in our subdivision, but the length δ s-2 -(n s -1)δ s-1 occur if and only if N = q s-2 + (n s + 1)q s-1 . We put i = a s -n s and obtain the conditions of Theorem 1.

◮ Case 3 : the last interval. What about 1 -u j , where j = (K) α and K is the greatest element of (E(N ), ALO) ? Then K = ((max, 0) s/2 ), so :

So, the case s even is proven ! If s is odd, we use similar arguments, replacing "predecessor" by " successor" and "u j -u j-1 " by "u j+1 -u j ".

4.2 order coincidence of ({nα}) n and ({nα ′ }) n

• Let α and α ′ be two different reals in [0, 1). We look for the greatest N such that ({nα}) n∈{0•••N -1} and ({nα ′ }) n∈{0•••N -1} are in the same order in the following meaning :

({nα}) n∈I is in the same order than ({nα ′ }) n∈I if and only if (∀n,

where I is an interval of Z. This property is related with another one, concerning integral parts : Lemma 9 let α, α ′ ∈ R and N a positive integer. The following assertions are equivalent :

thus, the sign of {n ′ α} -{nα} only depends on ǫ. We have the same equalities and remark with α ′ and ǫ ′ instead of α and ǫ.

(ii) ⇒ (i) : suppose that (ii) is true. Then, with above notations, we have ǫ = ǫ ′ , so {n ′ α} -{nα} and {n ′ α ′ } -{nα ′ } have the same sign.

(i) ⇒ (ii) : suppose that (ii) is false. Then we have an integer

, then, with above notations : ǫ = 0 and ǫ ′ = 1, so {n ′ α} -{nα} and {n ′ α ′ } -{nα ′ } do not have the same sign.

• Suppose that α is a real and p/q is a convergent of α. We claim that :

, since p and q are coprime, so ⌊nα⌋ = np q .

• Is this result still valid for semi-convergents instead of convergents ? for other reduced rationals ? The following result gives the answer...and a bit more.

Proposition 8 . (i) let α and α ′ be two reals such that 0 < α < α ′ < 1. We denote γ the best rational in ]α, α ′ ] and q the denominator of its reduced fraction. Then

(ii) let α be a real in [0, 1) and p/q a reduced fraction, with q ∈ N * , such that α is not the nearest left strict convergent of p/q. p/q is a semi-convergent of α ⇔ ∀k ∈ {0 • • • q -1}, ⌊kα⌋ = ⌊kp/q⌋ Proof :

We denote t = min({i, b 2i = 0}), except if all b 2i are null : we then denote t the greatest integer i such that b 2i-1 = 0: so we have, in that case, b = (max, 0) t . Then, for all cases ( see definition of E (α) ), we have :

Following last remarks above Proposition 9, we need the α-numeration, say ν, of the least integer n such that {nα} β. According to Proposition 2,3,4, it is the minimum of elements d of E (α) for RLO, such that

is minimal ( for RLO) among these one and satisfies ν A b. Now, if we denote n 1 = Ψ α (ν) this least integer n such that {nα} β, then :

So, for the product order in Z 2 :

If b k = 0 for all integer k 2t, then ν = b and {n 1 α -β} = 0, so this gives the only minimal point ( with n = 0).

For the other cases : if n n 1 , let denote d its α-numeration. Then, the minimality condition for ({nα -β}, n) is equivalent to : d A b and d is minimal among these ( elements of E α greater than b for ALO) for the product of orders (ALO,RLO).

Of course, ν is the first ( for RLO) of these minimal ( for (ALO,RLO)) elements. The next one ( for RLO) must satisfy : d < A ν and d is minimal for RLO : it gives the successive (b Best left ( positive) α-approximations of β are the {nα} for n = r i=1 b i q i-1 and for the following

Best left ( positive) α-approximations of β are the {nα} for n = s i=1 b i q i-1 , if b k = 0 for all integer k > s, and the following n :

the proof is similar to those of previous Proposition.

Proposition 11 we denote n = (n k ) k the α-numeration of ν and b = (b k ) k the α-numeration of β. We denote s the minimum of the lengths of n and b, when we drop the eventual infinite " 0-tail". So, n s or b s is not null, but σ s (n) or σ s (b) is the null sequence.

Proof :

we want to enumerate sequences d of E (α) such that d < R n and d < A b. We will consider several cases and subcases, depending on the cancellation of the b i and n i ... First, we remark that b 1 > 0 and n 1 > 0, for we can suppose that b = (0) and n = (0). ◮ Case 1 : b 2 > 0. ◮◮ subcase 1 : n 2 > 0 or σ(n) = (0). Let us count sequences d as follows :

, counting these sequences is the same, according to Lemma 6, as counting sequences u of E (α1) ( since

1 sequences d for this subcase, where ǫ ′ 1 = 1 if and only if u can be equal to σ(b), so if and only if σ(b) < R σ(n) and 0 else.

If we summarize this subcase, we obtain :

◮◮ subcase 2 :

this is the same count as in the previous subcase, except that : we have σ

. So, we must replace min(b 1 , n 1 ) by 1 : this is the role of τ 1 . Furthermore, the condition σ

1 sequences d for this subcase. Now, with all previous arguments, we obtain

and n 2 = 0, so we must replace 0 by 1 for the value of n 2 in the formula for τ 2 and ǫ 2 . But, it does not change the result, for b 2 = 0 ! At the end, ν 2 = (σ 2 (n)) α2 , so the induction goes on.

If we summarize this subcase, we obtain ( here ǫ 1 = 0) : -if d 2 > 0, then counting these sequences is the same as counting sequences d such that d 2 > 0 and σ(d) < R σ(n), so counting sequences u ∈ E (α1) such that u = (0) and u < R σ(n). With the same arguments as in Case 1 ( separating 2 cases : if n 2 is null or not), we obtain ν 1 -1 such sequences.

-if d 2 = 0. We will study 3 subcases, depending on n 2 and n 3 : ◮◮ subcase 1 : if n 2 = 0, then we count sequences d such that σ 2 (d) < R σ 2 (n) and σ 2 (d) < A σ 2 (b). So, we obtain C(α 2 , β 2 , ν 2 ) such sequences, because σ 2 (n) and σ 2 (b) are the α 2 -numeration of ν 2 and β 2 respectively. ◮◮ subcase 2 : if n 2 = 0 and ( n 3 = 0 or σ 2 (n) = (0)), then we count sequences d such that

If we summarize this case 2 :

Now, let us summarize and generalize all cases : for all

where ǫ" i = 1 if n i+1 = 0, (n i+2 = 0 or σ i+1 (n) = (0)) and σ i+1 (n) < A σ i+1 (b) and 0 else. We claim that :

Moreover, ǫ" i = 0, so the equality is true.

-if n i+1 > 0 , then σ i (b) < R σ i (n) ⇔ σ i+1 (b) R σ i+1 (n).

If σ i+1 (b) = σ i+1 (n), then ǫ i+1 = 0, τ i+1 = 0, ǫ ′ i = 1, ǫ ′ i+1 = 0 and ǫ" i = 0, so the equality is true. If σ i+1 (b) = σ i+1 (n), then ǫ ′ i = ǫ ′ i+1 . If n i+2 = 0 or σ i+1 (n) = (0) then ǫ" i = 1 -ǫ i+1 and τ i+1 = 0. Else, ǫ i+1 = 0 ( for b i+2 = 0),ǫ" i = 0 and τ i+1 = 1. In both cases, the equality is true.

From this equality, we deduce that : if b i+1 = 0, and σ i (b) = (0), then

So, the induction formula for b i+1 > 0 can be generalized to all cases and we conclude with : if s = 1, then n = (n 1 ) or b = (b 1 ). In the first case, ν 1 = 0 and C(α, β, ν) counts the d = (d 1 ) such that 0 d 1 < n 1 and d 1 < b 1 . So C(α, β, ν) = min(b 1 , n 1 ) = τ 1 and ǫ 1 = 0 = ǫ ′ 1 , since σ(n) = (0). In the second case, we have σ(b) = (0) = σ(n). Our former arguments give : C(α, β, ν) = b 1 ν 1 + τ 1 + ǫ 1 -1 and ǫ ′ 1 = 1. This is the initialization of our induction.

• We can deduce similar results for conditions with large inequalities instead of strict ones.