Emmanuel Cabanillas
email: emmanuel.cabanillas@ac-montpellier.fr

Quotients of numerical semigroups generated by two numbers

In this article, we study the quotients of numerical semigroups, generated by two coprime positive numbers, denoted <a,b> d . We give formulae for the usual invariants of these semigroups, expressed in terms of continued fraction expansions and Ostrowski-like numeration of some rationals, simply related to inputs a, b, d. So, we obtain quadratic complexity algorithms to compute these invariants. As a consequence, we will show that, for these numerical semigroups, the type is always lower than the embedding dimension and deduce Wilf's property. We also consider the " reverse problem" : given I a finite set of integers, we obtain an expression of all possible triplets (a, b, d), such that I is the set of minimal generators of <a,b> d .

1 Introduction

basics about numerical semigroups

We give here some definitions and elementary results without proofs. See [START_REF] Assi | Numerical Semigroups and Applications[END_REF], [START_REF] García-Sánchez | Numerical semigroups[END_REF] and [START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF] ( References) for more details. First, we will use some classical notations : -we denote N the set of all non negative integers, N * the set of positive integers and Z the set of integers.

-for every couple of integers p, q, the notation {p, .., q} means the set of integers k such that p k q. We extend this notation to {p, .., ∞} = {k ∈ Z, k p}.

-for an element x and two subsets I and J of an additive group G, we will use the classical notations : I + J = {i + j, i ∈ I, j ∈ J} ; -I = {-i, i ∈ I} ; x + J = {x + j, j ∈ J} -we will also denote for an integer n, a subset K of Z, an element x of G and a subset J of G : nJ = {nj, j ∈ J} ; xK = {kx, k ∈ K} • A numerical semigroup S is a cofinite submonoid of (N, +), where N denotes the set of non negative integers. We can also define a numerical semigroup with a system of generators. Let B be a non empty subset of N and < B > the set of all non negative integer combinations of finite subsets of B. Then < B > is a numerical semigroup ( generated by B) if and only if the elements of B are coprime ( not necesseraly pairwise coprime). In the case of finite B ( which is the general case), say B = {n 1 , n 2 , • • • , n r }, then :

< B >= r k=1 x k n k ; x 1 , x 2 , • • • , x r ∈ N
Let S be a numerical semigroup. • An element s of S is irreducible in S if and only if there is no positive elements s ′ and s" of S such that s = s ′ + s". The set of irreducible elements of S will be denoted Irr(S). It is well known that Irr(S) is the minimal set of generators of S : that is to say Irr(S) generates S and every set of generators of S contains Irr(S). Irr(S) is finite and its cardinality is called the embedding dimension of S, denoted by e(S).

Irr(S) is also the set of minimal elements of S\{0}, for the order S induced by S :

∀x, y ∈ Z, (x S y ⇔ yx ∈ S)

The smallest positive element of S is called the multiplicity of S and is denoted m(S). It is also the lowest element of Irr(S).

• The finite set N\S is often named the set of gaps of S and is denoted G(S). Its cardinality, named the genus of S, is denoted g(S). The greatest element of G(S) is called the Frobenius number of S and is denoted f (S), with the convention that f (N) = -1. It is in general difficult to compute this Frobenius number, but a lot of investigations have been made ( [11] References). The number f (S) + 1 is sometimes called the conductor of S and denoted c(S). The set of elements of S lower than f (S) will be denoted by S 0 , so that we have the following partition of N : N = G(S) ∪ S 0 ∪ {c(S), .., +∞} So, we have : #S 0 = c(S)g(S)

• Note that if s ∈ S, then f (S)s ∈ S, so that : f (S) -S 0 ⊂ G(S) so #S 0 g(S) and g(S) c(S)

1 2
A particular case if when we have an equality : then S is said symmetric.

• The Frobenius number of S is a particular case of the notion of pseudo-Frobenius numbers ( PF numbers in this paper) of S, that can be defined as the maximal elements of Z\S for the order S . PF(S) will denote the set of these elements : it is a subset of G(S) 2 and f (S) is its greatest element ( for the usual order on Z). The cardinality of PF(S) is the type of S, denoted t(S). PF(S) is also the minimal subset of Z that satisfies the following " symmetry property" :

Z\S = PF(S) -S = p∈PF(S) (p -S)
If we restrict to N, then we obtain :

G(S) ⊂ PF(S) -S 0 = p∈PF(S) (p -S 0 )
The above inclusion proves that : g(S) t(S)#S 0 and then :

g(S) c(S) 1 - 1 t(S) + 1
• Wilf 's property for a numerical semigroup S is the following :

g(S) c(S) 1 - 1 e(S)
Wilf 's conjecture claims that this inequality holds for every numerical semigroup ( [17]References). It has been proven in many cases ( [START_REF] Dhayni | Problems in numerical semigroup[END_REF], [START_REF] Dobbs | On a question of Wilf concerning numerical semigroups[END_REF], [START_REF] Froberg | On numerical semigroups[END_REF], [START_REF] Kaplan | Counting numerical semigroups by genus and some cases of a question of Wilf[END_REF], [START_REF] Sammartano | Numerical semigroups with large embedding dimension satisfy Wilf's conjecture[END_REF] ), but the general case still remains open. According to the previous inequalities, it would be sufficient to prove that t(S) < e(S). Unfortunately, it is not true for all numerical semigroups ( see example after Theorem 11 in [START_REF] Froberg | On numerical semigroups[END_REF]). Note that the ratio g(S)/c(S) could be named : the " density of gaps of S".

• The quotient of S by a positive integer d is defined by : S/d = {x ∈ N, dx ∈ S} It is a numerical semigroup and we remark that S/d = N if and only if d ∈ S. We also have an obvious calculation rule, when we consider quotients of a quotient :

∀d, d ′ ∈ N * , S/d d ′ = S dd ′
Many investigations have been made to relate invariants of S/d to invariant of S ( see introduction of [START_REF] Adeniran | on the genus of a quotient of a numerical semigroup[END_REF] for details and further references).

In this paper, we will study the most simple case, that is, when S is generated by two integers : let a and b be two coprime integers greater than one. Since Sylvester in 1882 ( [START_REF] Sylvester | Excursus on rational fractions and partitions[END_REF]), we know that < a, b > is symmetric and we have simple formulae for f and g :

f (< a, b >) = ab -a -b ; g(< a, b >) = (a -1)(b -1) 2
Curiously, < a, b > is very simple, but its quotients are not in general ! It was an open problem to express the invariants of S = <a,b> d , in terms of a, b, d ( [START_REF] Delgado | Numerical semigroup problem list[END_REF]). A recent paper ( [1]References) gives an expression of g(< a, b > /d) with a sum of integral parts, using Hilbert series. We will obtain another formulation for g(< a, b > /d) in Theorem 10, which could easily be relied to the previous one.

• Another motivation, for the study of these numerical semigroups, lies in the fact that they can be defined by two alternative ways : -let a, b, c be positive integers, then the set of integers x that verify ax mod b cx ( where mod denotes the remainder ) is a numerical semigroup, named proportionally modular. In [START_REF] Rosales | Proportionally modular Diophantine inequalities and full semigroups[END_REF], it is shown that : a numerical semigroup is proportionally modular if and only if it exists three pairwise coprime positive integers a, b, d such that S = <a,b> d . Furthermore, it is proven in [START_REF] Robles-Pérez | Equivalent proportionally modular Diophantine inequalities[END_REF], that we can choose b = a + 1. In [START_REF] Rosales | Proportionally modular Diophantine inequalities and full semigroups[END_REF], they build a set of generators of these <a,b> d , but it is not always minimal... -an equivalent definition is : for q and q ′ two rationals such that q < q ′ , N∩ < [q, q ′ ] > defines a numerical semigroup, that is proportionally modular ( [9]).

• A question at the end of [START_REF] Adeniran | on the genus of a quotient of a numerical semigroup[END_REF] is about the invariants of S/d, when S is generated by an arithmetic sequence. We prove in our paper that, in that case, S is itself a quotient of < a, b > for some a and b, which is a particular case of a more general result exposed in [START_REF] García-Sánchez | The set of solutions of a proportionally modular Diophantine inequality[END_REF]( References) : a numerical semigroup S is of the form <a,b> d , for some a, b, d if and only if Irr(S) can be enumerated by what we call a modular-convex sequence of positive integers (n k ) k∈{0,..,r} : ∀k ∈ {1, .., r -1},

n k-1 + n k+1 n k ∈ {2, .., ∞}
We give a new proof of this result and we also give explicit formulae for all possible a, b and d : Theorems 1 , 2 , 3 in section 3.4 . When S is generated by an arithmetic sequence ( which corresponds to the case when n k-1 +n k+1 n k = 2 for all k), we obtain ( see Corollary 1 at the end of 3.4 ) : for a, q, r positive integers such that a and q are coprime < a, a + q, a + 2q, • • • , a + rq >= < a, a 2 + q(ar + 1) > ar + 1 This is a particular case of more general results and formulae, but it can be proven directly with elementary considerations. Combining this with Theorems 4 ,5 , 6 , 7 , 8 , 9 and 10 ( see section 5), that give expressions of invariants of <a,b> d and our remark about (S/d)/d ′ = S/dd ′ , we obtain the answer to the above question...

overview of the article

First, in section 2, following an idea of [START_REF] Rosales | Proportionally modular Diophantine inequalities and full semigroups[END_REF], we use a representation of a numerical semigroup S as a subset of the cylinder Z 2 /wZ, where w = (b, -a) is a non null vector of Z 2 , via an additive map (x, y) → ax+by, where a and b are two coprime elements of S. For the numerical semigroups we are interseted in, that is <a,b> d , this will give a " lattice-stair case shape" representation : the intersection of a lattice and a regular stair case shape subset of Z 2 ( modulo wZ).

This approach leads in 2.2 to simple relations between G(S), Irr(S), PF(S) and elements or minimal sets ( for the product order on Z 2 ) of the above lattice in some rectangles. We remark in 2.3 that these minimal sets can be parametrized by " double inductive" sequences of points, that are convex and unimodular : we name them " modular-convex" ( see above).

In 3, we relate these sequences with a kind of continued fraction expansion and use them to solve the " reverse problem" : we obtain in 3.4 a complete expression of all triplets of pairwise coprime positive integers a, b, d such that 1 < a < b and Irr( <a,b> d ) is a given finite subset of N. In order to solve the " direct problem" ( express invariants of <a,b> d in terms of a, b, d), we need another parametrization of the above minimal sets by Kronecker sequences ({nα -β}, n) n . So, we use some general considerations about usual Diophantine approximation ( 4.1 and 4.2), as well as some more unusual ( 4.3 ) Ostrowski-like numeration ( detailed in [START_REF] Cabanillas | A variant of Ostrowski numeration[END_REF] References).

Finally, we give in section 5. all formulae about the usual invariants of numerical semigroups <a,b> d . We end this paper with the remarkable property : e(S)t(S) 1 for every numerical semigroup S of this type <a,b> d . This inequlity implies Wilf's property for these numerical semigroups, as mentioned in 1.1.

some notations and definitions

• For any real x, we denote respectively ⌊x⌋, ⌈x⌉ and {x} the floor, ceil and fractional part of x.

• For a vector u of Z 2 , we will denote x(u) and y(u) its coordinates. We will denote the natural partial product order on Z 2 : u v if and only if (x(u) x(v) and y(u) y(v)).

Then, for a subset U of Z 2 , min(U ) and max(U ) are respectively the sets of minimal and maximal elements of U , for this product order on Z 2 .

• If M is a submonoid of (R n , +), we will denote :

M 0 = {u ∈ M, -u ∈ M } ; M * = M \M 0 Irr(M ) = {u ∈ M * , ∀v, v ′ ∈ M * , u = v + v ′ }
Lemma 1 let ψ : Z p → R n be an additive map ( n and p are positive integers) and M be a submonoid of ψ(Z p ). Then :

(ψ -1 (M )) 0 = ψ -1 (M 0 ) ; (ψ -1 (M )) * = ψ -1 (M * ) ; Irr(ψ -1 (M )) = ψ -1 (Irr(M ))
Proof :

first two results are well known and almost obvious. Let u ∈ Irr(ψ -1 (M )). We denote m = ψ(u).

Suppose that m = n + n ′ , with n, n ′ ∈ M * . Then, we have v, v ′ ∈ ψ -1 (M ), w ∈ ker(ψ), such that u = v + v ′ + w and ψ(v) = n, ψ(v ′ ) = n ′ . But, if we denote v" = v ′ + w, then u = v + v" and ψ(v") = n ′ . So, v, v" ∈ (ψ -1 (M )) * : contradiction with our hypothesis on u. So, m ∈ Irr(M ). Conversely, let m ∈ Irr(M ) and u ∈ ψ -1 (M * ), such that ψ(u) = m. Suppose that u = v + v ′ , with v, v ′ ∈ (ψ -1 (M )) * , then m = n + n ′ , where n = ψ(v) and n ′ = ψ(v ′ ). So, n, n ′ ∈ M * : contradiction with our hypothesis on m. So, u ∈ Irr(ψ -1 (M )). • A subset U of Z 2 is said to be w-invariant if and only if U + w = U . Lemma 2 if U is a w-invariant subset of Z 2 , for w ∈ Z 2 , then min(U ), max(U ), Z 2 \U are w-invariant. ( then max(Z 2 \U ) is also w-invariant) Proof : Suppose that w + U = U . Let u ∈ min(U ) and u ′ = u + w, then u ′ ∈ U , since U is w-invariant. If there is u" ∈ U such that u" u ′ , then v = u" -w ∈ U ( U is w-invariant) and v u. So that, v = u since u is minimal in U . Then u" = u ′
and u ′ is minimal in U . This proves that w + min(U ) ⊂ min(U ). But U is also (-w)-invariant, then -w + min(U ) ⊂ min(U ) and finally min(U ) is w-invariant. The other results are proven in the same way.

2 Representations in Z 2

• one of the simple ideas of this paper is to use Lemma 1 in the particular case, when M is a numerical semigroup ( so n = 1) and p = 2 : so we have a numerical semigroup S and a representation ψ of S in Z 2 , that is a map ψ :

Z 2 → R, such that S ⊂ ψ(Z 2 ).
Hence, if we denote M = ψ -1 (S), we just have to study Irr(M ) to easily deduce results on Irr(S). For that aim, we will consider minimal elements of M * , for the product order on Z 2 . So, we need to have simple relations between Irr(M ) and min(M * ).

Question : for what kind of submonoids M of (Z 2 , +, ), do we have : Irr(M ) = min(M * ) ?

We can give an elementary exemple : Irr(N 2 ) = min((N 2 ) * ) = {(1, 0); (0, 1)}.

We will not answer the question, but only give a partial result, that will be sufficient for our purpose.

Lemma 3 let L be a sublattice of Z 2 and w ∈ L, such that w, -w ∈ N 2 .

Then, for M = (L ∩ N 2 ) + wZ, we have :

M 0 = wZ ; Irr(M ) = min(M * ) Proof : First, wZ ⊂ M 0 . On the other hand, if m ∈ M 0 , then m = m ′ + k ′ w and -m = m" + k"w, where m ′ , m" ∈ L ∩ N 2 and k ′ , k" ∈ Z.
Then, m ′ + m" = jw, where j ∈ Z. So, jw 0 : contradiction with our hypothesis on w, if j = 0. Hence, j = 0 and m ′ + m" = 0. We deduce that m ′ = m" = 0, for m ′ , m" ∈ N 2 . So, m ∈ wZ.

We remark that M ⊂ L, since w ∈ L.

Let u ∈ Irr(M ), then u ∈ M * . We suppose that there exists v ∈ M * such that u > v. Then v ′ = u-v > 0 and v ′ ∈ L, for u, v ∈ L. So, v ′ ∈ M * , for M 0 = wZ and w, -w ∈ N 2 : no elements of M 0 is positive. So u = v + v ′ , with v, v ′ ∈ M * : contradiction with our hypothesis on u. So, u ∈ min(M * ).

Conversely : if u ∈ min(M * ). Suppose that u = v + v ′ and v, v ′ ∈ M * . Then, we can find m, m ′ ∈ L ∩ (N 2 ) * and k, k ′ ∈ Z, such that : v = m + kw and v ′ = m ′ + k ′ w. Now, we denote v" = v ′ + kw and we have u = m + v", where m > 0 and v" ∈ M * , for v ′ = v" ( mod M 0 ). So, u > v" : contradiction with our hypothesis on u. So, u ∈ Irr(M ).

• For a and b two coprime positive integers, we define two maps by :

ϕ : Z 2 → Z (x, y) → ax + by ; ψ : Z 2 → (1/d)Z (x, y) → (ax + by)/d
These maps are additive group morphisms. They are strictly increasing, surjective and their kernel is wZ, where w = (-b, a).

Let S =< a, b > be the numerical semigroup generated by a and b and S ′ = S d . We denote L the lattice defined by L = {(x, y) ∈ Z 2 , ax + by = 0 ( mod d)}. We will prove in Lemma 5 :

ϕ -1 (S) = N 2 + wZ ; ψ -1 (S ′ ) = L ∩ (N 2 + wZ) = (L ∩ N 2 ) + wZ
So, this representation of <a,b> d in Z 2 is of the above type and will allow us ( see Lemma 1 and 3) to claim that :

ψ -1 Irr < a, b > d = min(L ∩ ((N 2 ) * + wZ))
This is detailed in this section and in 3.2.

2.1 a lattice-stair case shape representation

• Let S be a numerical semigroup and d a positive integer. We have then :

d(S/d) = {s ∈ S, s = 0( mod d)} = S ∩ dZ
Let a and b be two coprime integers. With the two maps defined just above ( previous page), we have :

ψ -1 (S/d) = ϕ -1 (d(S/d)) = ϕ -1 (S) ∩ L
where L is the lattice :

L = {(x, y) ∈ Z 2 , ax + by = 0( mod d)} = ϕ -1 (dZ) = ψ -1 (Z)
and :

ψ -1 (N) = L ∩ H + ; ψ -1 (G(S/d)) = (H + \ϕ -1 (S)) ∩ L
where H + denotes the halfplane {(x, y) ∈ Z 2 , ax + by 0}. L is generated by w = (b, -a), v 2 = (0, d) and v 1 = (d, 0) ( but it is not a basis) : indeed these three vectors are in L and since a and d are coprime, for every y in Z, we can find x ∈ Z such that (x, y) ∈ wZ + v 2 Z. So with the former remark, we obtain, adding multiples of v 1 , all the points of L.

• We will study the simplest case, namely when S is generated by two coprime integers a, b. We begin with some remarks.

< d ′ a, b > dd ′ = < a, b > d (ii) if d divides f (< a, b >) = ab -a -b, then <a,b> d is symmetric and f ( <a,b> d ) = f (<a,b>) d .
Proof :

(i) let k be an integer :

kdd ′ ∈< d ′ a, b >⇔ ∃x, y ∈ N, kdd ′ = xd ′ a + yb ⇔ ∃x, z ∈ N, kd = xa + zb ⇔ kd ∈< a, b > as if d ′ divides yb, then it divides y, because d ′ and b are coprime. (ii) we denote f = f (<a,b> d and suppose that f is an integer. Then df ∈< a, b >, so f is a gap of <a,b> d . In addition, dn ∈< a, b > for all integer n such that n > f , because dn > f (< a, b >). So, f = f ( <a,b> d ). If n is a gap of <a,b> d , then dn is a gap of < a, b >, so df -dn ∈< a, b >, for < a, b > is symmetric. Hence, f -n ∈ <a,b> d . Conversely, if s ∈ <a,b> d and s < f , then f -s is a gap of <a,b> d . So, <a,b> d is symmetric.
Thus, we will suppose that d is a positive integer, coprime with a and b. We will also suppose that d = a and d = b. Indeed : if, more generally, d ∈< a, b > then kd ∈< a, b > for all non negative integer k and then <a,b> d = N.

• The representation of S =< a, b > and S ′ = S/d are simple : S is represented in Z 2 by a " full stair-case shape" and S ′ by its intersection with the lattice L. This is proven by the following Lemma :

Lemma 5 let a, b, d be three positive pairwise coprime integers. Let S =< a, b > and S ′ = <a,b> d . We denote w = (b, -a). Let T be the triangle, " upper-half" of the rectangle {1, .., b -1} × {-(a -1), .., -1} :

T = {(x, y) ∈ Z 2 , x ∈ {1, .., b -1}, y ∈ {-a + 1, .., -1}, ax + by > 0} (i) (N 2 + wZ, T + wZ) is a partition of H + = {(x, y) ∈ Z 2 , ax + by 0}. (ii) ϕ -1 (S) = N 2 + wZ ; ϕ -1 (G(S)) = T + wZ (iii) ψ -1 (S ′ ) = (L ∩ N 2 ) + wZ ; ψ -1 (G(S ′ )) = (L ∩ T ) + wZ ψ is bijective from L ∩ T to G(S ′ ).
Proof :

(i) if u ∈ (N 2 + wZ) ∩ (T + wZ), then we have u = u 1 + k 1 w = u 2 + k 2 w, where u 1 ∈ T, u 2 ∈ N 2 , k 1 , k 2 ∈ Z. So u 1 -u 2 = kw,
where k ∈ Z. Note u 1 = (x 1 , y 1 ) and u 2 = (x 2 , y 2 ). We have

x 1 ∈ {1, .., b -1}, x 2 ∈ N, y 1 ∈ {-a + 1, .., -1}, y 2 ∈ N, k ∈ Z such that : x 1 -x 2 =
kb and y 2y 1 = ka. So ka > 0, thus k 1 and x 2 < 0 : contradiction... This proves that (N 2 + wZ) ∩ (T + wZ) = ∅.

On the other hand, if (x, y) ∈ H + , then x b -y a . We consider two cases : Case 1 : if ⌊x/b⌋ = ⌊-y/a⌋ and x/b, y/a are not integers, then if we denote k this common integer, we have : x = kb + x ′ and y = -ka + y ′ , with (x ′ , y ′ ) ∈ T . , so (x, y) ∈ T + wZ.

Case 2 : if x/b = -y/a and are integers, then (x, y) ∈ wZ ⊂ (N 2 + wZ). Case 3 : if ⌊x/b⌋ > ⌊-y/a⌋, then if we denote k = ⌊x/b⌋, we have x = kb + x ′ and y = -ka + y ′ , with (x ′ , y ′ ) ∈ N 2 , so (x, y) ∈ N 2 + wZ.

(ii) We have ϕ(N 2 ) = S and use (i) for G(S). (iii) with the general remarks at the beginning of the section and the fact that L is w-invariant :

ψ -1 (S ′ ) = L ∩ (N 2 + wZ) = (L ∩ N 2 ) + wZ
the same arguments rules for G(S ′ ). Now, ψ is bijective from T ∩ L to G(S ′ ), since for every u ∈ T, k ∈ Z * , u + kw ∈ T .

• For now in this section, we adopt the following hypothesis and notations : -we suppose that a, b, d are pairwise coprime.

-we denote L ′ = L\{(0, 0)} and S ′ = <a,b> d . -the symbol A ψ ≃ B means that A and B are in bijective correspondence via ψ.

-we use the usual product order on Z 2 ( partial order).

Lemma 6 . (i)

S ′ \{0} ψ ≃ (N × {0, .., a -1}) ∩ L ′ (ii) Irr(S ′ ) ⊂ ψ(min(({0, .., d} × {0, .., a -1}) ∩ L ′ ) (iii) d < b ⇒ Irr(S ′ ) ψ ≃ min(({0, .., d} × {0, .., a -1}) ∩ L ′ )
Remark : Irr(S ′ ) is the minimal set of S ′ \{0} for the order S on Z. The result (i) would suggest that, since ψ is increasing, then Irr(S ′ ) is via ψ in one to one correspondence with min(E), where E = (N × {0, .., a -1}) ∩ L ′ ..., but this is not true in general, because ψ is not an order isomorphism on these sets. We can have u, u ′ ∈ E, with ψ(u) S ′ ψ(u ′ ) and u u ′ : it is the case if u ′ u + w and y(u ′ ) < y(u).

Proof :

-(i) ψ is injective on (N×{0, .., a-1})∩L ′ , because for two different elements u, u ′ of this set, u ′ -u ∈ wZ ( as |x(u ′u)| < a). Moreover, let u ∈ (N 2 ∩ L ′ ) + wZ, then :

u = kw + u ′ with k = - y(u) a and y(u ′ ) ∈ {0, .., a -1}
in addition, u = jw + u" for some integer j and u" ∈ N 2 , so : u ′ = u" + (jk)w. We deduce y(u ′ ) (kj)a, so kj 0, and

x(u ′ ) (j -k)b 0. Then, u ′ ∈ (N × {0, .., a -1}) ∩ L. In addition, u ∈ wZ, so u" ∈ wZ, hence u ′ = (0, 0). -(ii) Let s ∈ Irr(S ′ ) and u ∈ (N × {0, .., a -1}) ∩ L ′ such that s = ψ(u) ( see (i)). If x(u) > d, then u = (d, 0) + u ′ with u ′ ∈ (N × {0, .., a -1}) ∩ L ′ , so s = a + s ′ , with s ′ = ψ(u ′ ) ∈ S ′
and s ′ = 0, which is in contradiction with s ∈ Irr(S ′ ), since a ∈ S ′ . We have proven that x(u) d, and so that u ∈ ({0, .., d} × {0, .., a -1}) ∩ L ′ . Now, we want to prove that u is minimal in M = ({0, .., d} × {0, .., a -1}) ∩ L ′ . If it is not, then we have u ′ ∈ M , such that u ′ < u. Let u" = uu ′ , then u" ∈ L ′ and 0 x(u ′ ) x(u) d, so x(u") ∈ {0, .., d}, and with similar arguments, y(u") ∈ {0, .., a -1}. So u" ∈ M and s = s ′ + s", with

s ′ = ψ(u ′ ), s" = ψ(u") ∈ S ′ \{0}. It is impossible since s ∈ Irr(S ′ ).
-(iii) Reversely : let u ∈ min(M ) and s = ψ(u). Then, s ∈ S ′ and s = 0. We would like to prove that s is irreducible in S ′ : if it was not, then we would have s 1 and s 2 in S ′ such that s = s 1 + s 2 and s 1 , s 2 non null. Let u 1 and u 2 be the unique elements in (N × {0, .., a -1}) ∩ L ′ ( see (i)), such that s 1 = ψ(u 1 ) and

s 2 = ψ(u 2 ). Then, ψ(u) = ψ(u 1 + u 2 ) and u 1 + u 2 ∈ (N × {0, .., 2a -2}) ∩ L ′ . So, u = u 1 + u 2 or u = u 1 + u 2 + w.
In the last case, we have x(u) b, so that, if d < b, we obtain a contradiction. In that case d < b, we can conclude that u = u 1 + u 2 and then u 1 , u 2 ∈ M , since they have non negative x. Then, u is not minimal in this set, as u 1 > 0 and u 2 > 0 : contradiction. So ψ(S ′ ) = min(M ) and we conclude with (i).

2.2 relations between invariants of <a,b> d and a lattice in a rectangle

• We begin with the genus g(S ′ ). At the beginning of the previous subsection, we have seen in Lemma 5 that T ∩ L and G(S ′ ) ( see notations in this Lemma) are in bijective correspondence via ψ. We will use another property with the following Proposition :

Proposition 1 let R 0 be the rectangle : {1, .., b -1} × {-(a -1), .., -1} and L the lattice L = {(x, y) ∈ Z 2 , ax + by = 0[d]}. g < a, b > d = 1 2 #(L ∩ R 0 ) Proof :
The above remark proves that g(S ′ ) = #(T ∩L). In addition, the symetry of Z 2 , σ : (x, y) → (b-x, -a-y) carries T onto T ′ such that (T, T ′ ) is a partition of R 0 . Indeed, T = {(x, y) ∈ R 0 , ax + by > 0}, so T ′ = {(x, y) ∈ R 0 , ax + by < 0}. Moreover, there is no point (x, y) in R 0 such that ax + by = 0, since a and b are coprime. So, the result is proven.

• Next proposition is our main result to express minimal generators of <a,b>

Proof :

We use Lemma 6 (iii). ◮ Case 1 : if d < a < b : then, (d, 0) and (0, d) ∈ min(L ′ ∩ ({0, .., d} × {0, .., a -1})) ( remind that L has exactly one point on every Z-line or row of length d), so a, b ∈ Irr(S ′ ) and we have also Irr(S ′ )\{a, b} ψ ≃ min(L ∩ {1, .., d -1} 2 ), since (0, d) and (d, 0) are not comparable with all elements of this set. Moreover, if u ∈ {0, .., d} × {d, .., a -1}, then (0, d) < u. ◮ Case 2 : if a < d < b : then (d, 0) ∈ min(L ′ ∩ ({0, .., d} × {0, .., a -1})), but (0, d) is not in this set ! We conclude in the same way as above. ◮ Case 3 : if a < b < d : this case is more intricate.

-we have seen in Lemma 6 (ii), that : if s ∈ Irr(S ′ ), then s = ψ(u), with u ∈ min(({0, .., d} × {0, .., a -1}) ∩ L ′ ). We have x(u) x 0 , with the definition of x 0 , for if y(u) = 0, then u = (d, 0) and x 0 < d ( see property of L again). Let us prove that "x(u) x 0 + b -1 ". If x(u) x 0 + b, we denote u ′ = uw, so u 0 u ′ , where u 0 = (x 0 , y 0 ) ∈ L ′ ∩ ({0, .., d} × {0, .., a -1}). So, if we denote s 0 = ψ(u 0 ), we obtain s 0 S ′ s = ψ(u ′ ). But, s 0 ∈ S ′ and s 0 = 0 : contradiction with s ∈ Irr(S ′ ) ! So, u ∈ ({x 0 , .., x 1 } × {0, .., a -1}) ∩ L) and is minimal in it, since it is minimal in a bigger set.

-on the other hand, suppose that u ∈ min(({x 0 , .., x 1 } × {0, .., a -1}) ∩ L) and s = ψ(u), then s ∈ S ′ and s = 0. Suppose that s = s 1 + s 2 , with s 1 and s 2 in S ′ and s 1 , s 2 non null. Let u 1 and u 2 be the unique elements in (N × {0, .., a -1}) ∩ L ′ , such that s 1 = ψ(u 1 ) and

s 2 = ψ(u 2 ). Then, ψ(u) = ψ(u 1 + u 2 ) and u 1 + u 2 ∈ (N × {x 0 , .., 2a -2}) ∩ L ′ . So, u = u 1 + u 2 or u = u 1 + u 2 + w.
In the last case, we have x(u) b+x 0 > x 1 : contradiction. So, u = u 1 +u 2 and u is not minimal in ({x 0 , .., x 1 }×{0, .., a-1})∩L), since u 1 , u 2 are in this set and are not null ( x 0 x(u 1 ), x(u 2 ) and x(u 1 ) + x(u 2 ) = x(u) x 1 ).

We have proved that : if u ∈ min(({x 0 , .., x 1 } × {0, .., a -1}) ∩ L), then ψ(u) ∈ Irr(S ′ ), so the result is obtained with Lemma 6 (i), since ψ is bijective over this set. To finish : (0, d) ∈ {x 0 , .., x 1 } × {0, .., a -1}) ∩ L) and (d, 0) ∈ {x 0 , .., x 1 } × {0, .., a -1}) ∩ L if and only if x 1 d. In that case, it is minimal in this set !

• Now, in the same way as for Irr(S ′ ), the set PF(S ′ ) can be related with maximal points of a certain rectangle of L : Lemma 7 we denote R the rectangle of Z 2 defined by : R = {bd, .., b -1} × {-d, .., -1}. We denote the numerical semigroup S = <a,b> d , the lattice L = {(x, y) ∈ Z 2 , ax + by = 0[d]} and the triangle T = {(x, y) ∈ Z 2 , x ∈ {1, .., b -1}, y ∈ {-a + 1, .., -1}, ax + by > 0}. Then :

PF(S) ψ ≃ max(L ∩ R) ∩ T
We can precise if we distinguish several cases :

◮ Case 1 : if d < a < b : PF(S) ψ ≃ max(L ∩ R) ◮ Case 2 : if a < d < b : PF(S) ψ ≃ max(L ∩ {b -d, .., b -1} × {-(a -1), .., -1}) ∩ T ◮ Case 3 : if a < b < d : PF(S) ψ ≃ max(L ∩ {1, .., b -1} × {-(a -1), .., -1}) ∩ T
Remark : this result will be improved in next subsection, after we have proved that these maximal points are in T ( see Proposition 4). But now, we can use the following argument : let C be a square of Z 2 , say C = {x 0 , .., x 0 + c -1} × {y 0 , y 0 + c -1, .., } , and E a subset of C, that contains exactly one point on every row and one point on every line. Then, minimal points of E are all under ( or on) the diagonal x + y = x 0 + y 0 + c -1 : these points (x, y) verify : x+y x 0 +y 0 +c-1. The proof is obvious, with reducio ad absurdum for instance.

Proof :

We will use similar arguments as in proof of the previous result. As a reminder :

G(S ′ ) ψ ≃ L ∩ T ( see Lemma 5 (iii)).
-Let s ∈ PF(S ′ ), then s ∈ G(S ′ ), so we have u ∈ L ∩ T such that s = ψ(u). We claim : u ∈ L ∩ R : indeed, if u ∈ L ∩ R ( only possible if d < max(a, b)), then u + (d, 0) or u + (0, d) ∈ L ∩ T and so s + a or s + b ∈ G(S ′ ), which contradicts our hypothesis on s. Suppose that u is not maximal in L ∩ R, then we have u ′ ∈ L ∩ R such that u < u ′ . Let u" = u ′u, then u" ∈ N 2 ∩ L ′ so s" = ψ(u") ∈ S ′ . But, s" = 0, since u" > 0. Now s + s" = ψ(u ′ ) ∈ S ′ : contradiction with our hypothesis on s.

-Conversely, let u ∈ max(L ∩ R) ∩ T and s = ψ(u). Then u ∈ L ∩ T , so s ∈ G(S ′ ). Suppose that s ∈ PF(S ′ ), then we have s ′ ∈ S ′ , such that s ′ = 0 and s" = s + s ′ ∈ S ′ . Let u ′ ∈ L ′ ∩ N 2 , such that ψ(u ′ ) = s ′ and u" ∈ L ∩ T , such that ψ(u") = s" ( indeed s" ∈ G(S ′ ), for s" > 0). Then, ψ(u + u ′ ) = ψ(u"), so u + u ′ = u" + kw, for some integer k. With first coordinate in Z 2 , we obtain :

1 x(u + u ′ ) = x(u" + kw) < (k + 1)b so k 0.
With second coordinate, we obtain :

-a < y(u + u ′ ) = y(u" + kw) < -ak so k 0. We deduce : k = 0 and so u < u", since u ′ > 0 : it is in contradiction with our hypothesis. We have proved the first assertion.

◮ Case 1 : if d < a < b : with the remark above, max(R ∩ L) is a subset of the upper-half triangle of the square R ∩ L. Then this triangle is a subset of T and the result is proven.

◮ Case 2 : if a < d < b : let denote R ′ = {b -d, .., b -1} × {-(a -1), .., -1}). Then, max(R ∩ L) ∩ T ⊂ max(R ′ ∩ L) ∩ T , for R ∩ T ⊂ R ′ ⊂ R.
On the other hand, no element of R\R ′ is greater than any element of R ′ ( look at y), so the result is proven. ◮ Case 3 : if a < b < d : same arguments as in Case 2 with R" = {1, .., b -1} × {-(a -1), .., -1}).

minimal points of a lattice in a rectangle

• Proposition 2 and Lemma 5 are about minimal points of a lattice in a rectangle ( in R 2 with the product order). Indeed, if we use an "half turn symmetry" in R 2 , such as u → vu, then maximal points are turned into minimal points and vice versa... Lemma 8 Let L be a lattice of R 2 and R = {x 0 , .., x 0 + c} × {y 0 , .., y 0 + c ′ }\{(x 0 , y 0 )}, where x 0 , y 0 are two reals and c, c ′ are two positive reals.

if (u k ) k∈{1,..,e} is x-monotonous or y-monotonous and describes min(L ∩ R), then : (i) both (x(u k )) k and (y(u k )) k are monotonous : one is increasing and the other is decreasing.

(ii) ∀i ∈ {2, .., e -1}, u i+1 + u i-1 2u i that is to say : (u i -u i-1 )
i is an increasing sequence in Z 2 ( with the product order).

(iii) we have equality in (ii) for a fixed i ∈ {2, .., e -1} if and only if

2u i -u i-1 ∈ R.
Remark 1 : we could name order-convex the property (ii).

Remark 2 : the curve connecting the (u k ) k is the " under border" of the convex hull of L ∩ R in R 2 . Remark 3 : (iii) means that (u iu i-1 ) i is constant as long as possible : the curve connecting the (u k ) k remains straight as long as it does not get out of the rectangle.

Proof :

(i) if only one of (x(u k )) k and (y(u k )) k is monotonous, then we can find i such that u i and u i+1 are comparable, which is not possible ! (ii) we remark that the conclusion is unchanged if we reverse the indexation of the sequence, so that we can suppose that (x(u k )) k is decreasing. Thus, (y

(u k )) k is increasing. Let i ∈ {2, .
., e -1} and we denote

v i = u i+1 + u i-1 -u i . Then, v i ∈ L ∩ R, for : x(u i+1 ) < x(v i ) < x(u i-1 ) ; y(u i-1 ) < y(v i ) < y(u i+1 )
So, there exists k ∈ {1, .., e}, such that u k v i . But, the previous inequalities show that k can not be different from i, so u i v i ...q.e.d. (iii) if we have equality, then 2u iu i-1 = u i+1 ∈ R. Conversely : if 2u iu i-1 ∈ R, then if we denote t i that element, we have u i+1 t i ( see proof of (ii)) and

t i ∈ L ∩ R. But u i+1 is minimal in L ∩ R, so u i+1 = t i .
• Now, we are able to propose a statement that improves Lemma 7 : Proposition 3 a, b, d are three pairwise coprime positive integers. We denote ψ :

Z 2 → (1/d)Z; (x, y) → (ax + by)/d and L = {(x, y), ax + by = 0[d]} = ψ -1 (Z).
The symbol ψ ≃ means that both sets are in bijective correspondance via ψ.

PF < a, b > d ψ ≃ max(L ∩ {b -δ, .., b -1} × {-δ ′ , .., -1})
where δ = min(d, b -1) and δ ′ = min(d, a -1).

Proof :

we denote R 1 = {b -δ, .., b -1} × {-δ ′ , .., -1}
). If we compare this statement with Lemma 7, we have just to show that max(L ∩ R 1 ) ⊂ T , with notations of Lemma 7. This has been done in the case d < min(a, b).

If a < d < b, then R 1 = {b -d, .., b -1} × {-(a -1), .., -1}. We denote R 0 = {b -d, .
., b} × {-a, .., -1} and we claim that max(L ∩ R 1 ) = max(L ∩ R 0 )\{(b, -a)}. Indeed, (b, -a) is a point of L and it is the only one in R 0 on the row y = b. So, (b, -a) ∈ max(L ∩ R 0 ) and max(L ∩ R 1 ) ⊂ max(L ∩ R 0 ), since there is no point in L ∩ (R 0 \R 1 ) that is greater than a point of R 1 . Our equality is proven. By now, our former Lemma proves ( via an half-turn ) that max(L ∩ R 0 ) can be enumerated by an "order-concave" sequence of points : max

(L ∩ R 0 ) = {u k , k ∈ {0, .., t}}, such that u 0 = (b, -a) and (u k -u k-1 ) k is decreasing. We deduce that : max(L ∩ R 1 ) = {u k , k ∈ {1, .., t}} ⊂ T , for u t = (x 1 , -1) the unique point of L that lies on the Z 2 -segment of length d : x ∈ {b -d, .., b -1}, y = -1. If d > max(a, b), then R 1 = {1, .., b -1} × {-(a -1), .
., -1}. We use similar arguments as in previous case with R 0 = {0, .., b -1} × {-a, .., 0}, as we remark that (0, 0) and (b, -a) are points of L, that are maximal points of L ∩ R 0 ( no point of L on the Z 2 -segment x ∈ {1, .., b}, y = 0). Moreover, no point of R 1 is greater than one of these two points.

• In order to study the minimal generators of <a,b> d , we consider a particular case of Lemma 8 :

Lemma 9 .
let L be a lattice of R 2 and R = {0, .., c} × {0, .., c ′ }\{(0, 0)}, where c, c ′ are positive reals. We can describe min(L ∩ R) by a sequence

(u i ) i∈{1,..,e} , such that (u 1 , u 2 ) is a Z-basis of L ( if e 2), (x(u i )) i , (y(u i )) i are monotonous and : ∀i ∈ {2, .., e -1}, ∃k i ∈ {2, .., +∞}, u i+1 + u i-1 = k i u i (1) moreover : ∀i ∈ {2, .., e -1}, k i = min(n ∈ N, nu i u i-1 ) (2)
Proof :

Let us consider (u k ) k∈{1,..,e} = min(L ∩ R), such that (x(u k )) k is decreasing and e = #(min(L ∩ R)). Then, (y(u k )) k is increasing ( see arguments of the proof of the previous Lemma). If e 2, then (u 1 , u 2 ) is a Z-basis of L, because there is no point of L in the interior ( in R 2 , or Q 2 ) of the triangle based on (0, u 1 , u 2 ), hence by symmetry u → u 1 + u 2 -u, there are no points in the interior of the parallelogram based on (0, u 1 , u 2 , u 1 + u 2 ).
Now, let us prove the induction formula. Let i ∈ {2, .., e -1}. Let j be the grestest integer such that u i+1 + u i-1 ju i and ρ = u i+1 + u i-1ju i . Then, ρ (0, 0) and j 2, according to the previous Lemma. If ρ = (0, 0), our result is proven. Else, we have x(ρ) < x(u i ) or y(ρ) < y(u i ). Suppose that x(ρ) < x(u i ). We also have :

y(ρ) y(u i+1 ) + y(u i-1 ) -2y(u i ) < y(u i+1 ) -y(u i ) < y(u i+1 )
Hence, ρ ∈ L∩R and it exists k ∈ {1, .., e}, such that u k ρ. But x(ρ) < x(u k ) if k i and y(ρ) < y(u k ) if k > i, so this is impossible. We use similar arguments if y(ρ) < y(u i ), proving that x(ρ) < x(u i-1 ).

Conclusion : ρ = (0, 0) and our formula is proven. We end this proof with the expression of k i as a minimum. Let i ∈ {1, .., e -1}. As u i+1 0, then k i u i u i-1 . If there exists a positive integer n < k i such that nu i u i-1 , then : we denote w = nu i -u i-1 , so u i+1 = w + (k in)u i > w. So, 0 w < u i+1 and w ∈ L. In addition, w = 0, since u i-1 = nu i ( this would imply u i u i-1 ). Hence, w ∈ R ∩ L and w < u i+1 : contradiction.

Remark : with hypothesis of previous Lemma, we can also conclude that

(u i , u i+1 ) is a Z-basis of L if i ∈ {1, ..,

e -1} ( obvious induction with formula (1)).

This has a direct consequence on Irr <a,b> d , when we use Proposition 2 : Let a, b, d be three pairwise coprime positive integers, then we can find a finite sequence of positive integers (m k ) k∈{1,..,e} , such that m 1 and m 2 are coprime, Irr <a,b> d = {m k , k ∈ {1, .., e}} and :

∀i ∈ {2, .., e -1},

∃k i ∈ {2, .., +∞}, m i+1 + m i-1 = k i m i
As proven in [START_REF] García-Sánchez | The set of solutions of a proportionally modular Diophantine inequality[END_REF], the converse is also true, if in addition we suppose that m i ∈< m k , k = i > for all i ∈ {1, .., e} ! We will explore that in next section.

The reverse problem

• Let us consider the set A of triplets of positive integers (a, b, d) such that 1 < a < b and a, b, d are pairwise coprime. We also consider the following map :

I : A → P(N) (a, b, d) → Irr <a,b> d
In [START_REF] García-Sánchez | The set of solutions of a proportionally modular Diophantine inequality[END_REF], we can find a precise description of the range of I : it is the set B of finite subset of N, that can be enumerated by a sequence (n k ) k∈{1,..,e} , such that :

     (i) ∀k ∈ {1, .., e}, n k ∈< n i , i = k > (ii) gcd(n 1 , n 2 ) = 1 (iii) ∀i ∈ {2, .., e -1}, ∃c i ∈ N, n i-1 + n i+1 -2n i = c i n i
We have proved half of this result at the end of previous section. We will prove the other half, giving the preimage of each element of B.

Remark 1 : we mention that < P > is the N-span of P in a monoid, so (i) could be named " N-independance of the (n i ) i " and is obvious for a minimal set of generators of a semigroup. This implies that the (n k ) k are pairwise distincts.

Property (ii) could be generalized ( as a consequence of (iii)) :

∀i ∈ {1, .., e -1}, gcd(n i , n i+1 ) = 1
Property (iii) implies that (n i ) i is convex and that, in a sense, "the second derivative of

(n i ) i " is a ( integral) multiple of (n i ) i : if we denote δ(n) = (n i -n i-1 ) i and δ(n) = (n i+1 -n i ) i then δδ(n) = δδ(n) = c × n
where c is a N-valued sequence.

Remark 2 : If the sequence (n k ) k∈{1,..,e} satisfies conditions (i),(ii) and (iii), then, for every k 1 , k 2 ∈ {1, .., e}, such that k 1 k 2 , the sequence (n k ) k∈{k 1 ,..,k 2 } satisfies (i),(ii) and (iii).

Question : given such a finite subset I of N, how many indexations of its elements do exist such that the above conditions (i),(ii),(iii) are satisfied ?

If I contains more that one element, then it exists as least two indexations : (n k ) k∈{1,..,e} and (n e+1-k ) k∈{1,..,e} . In some cases, there exist other indexations : for example, if I = {7, 11, 59}, we have 4 indexations of I that satisfy (i),(ii) and (iii) :

(59, 11, 7) ; [START_REF] Froberg | On numerical semigroups[END_REF][START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF]59) ; [START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF][START_REF] Froberg | On numerical semigroups[END_REF]59) ; (59,[START_REF] Froberg | On numerical semigroups[END_REF][START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF] As a consequence, we can find 2 triplets (a, b, d) of pairwise coprime integers such that d < a < b and Irr( <a,b> d ) = I ( see Thoerem 1 in 3.4) :

Irr < 7, 59 > 6 = {7, 11, 59} = Irr < 11, 59 > 10
3.1 modular-convex sequences

• Let us denote ∆ the operator of discrete second derivative of R n -valued sequences ( n ∈ N * ) : ∆ : u → v such that ∀i, v i = u i-1 + u i+1 -2u i
Then, we have ∆ = δδ = δδ, with notations of remark 1 above. In 2.4 and Lemma 9, we have proved that the minimal set of a lattice of R 2 in a rectangle R = ({0, .., c} × {0, .., c ′ })\{(0, 0)} can be enumerated by a sequence u, satisfying the relation :

∆(u) = c × u
where c is a sequence valued in N. In other words :

∀i, ∃c i ∈ N, u i+1 + u i-1 = (c i + 2)u i
We also have a SL 2 (Z)-matricial version :

∀i, ∃d i ∈ {2, .., +∞}, u i+1 u i = d i -1 1 0 u i u i-1
For convenience, we will name such sequences with the very unperfect term " modular-convex", for this mix of unimodular matrices and convexity-like property :

Definition 1 a R n valued sequence (u i ) i∈J is modular-convex if and only if it exists a N- valued sequence (c i ) i∈ ∼ J , such that ∆(u) = c × u. ( J is an interval of integers and ∼ J is J without its finite extremities )
Remark 1 : a numerical modular-convex sequence is not always convex. But, we have a simple result : if (x i ) i∈{0,..,r} is a numerical modular-convex sequence such that x 1 max(0, x 0 ), then it is convex. Indeed, by obvious induction, we prove that x i is non negative for i > 0 and (x ix i-1 ) i 1 is non decreasing and non negative.

• Now, we take interest in these sequences and will show that they are fully given by three terms : first, second and last one. In addition, the coefficients (d i ) i are related with some continued fraction development :

Proposition 4 let u, v, w ∈ R n such that u, v are linearly independant ( so n 2) ∃r ∈ N * , ∃(u i ) i∈{0,..,r} modular-convex, such that      u 0 = u u 1 = v u r = w ⇔ ∃p, q ∈ N,      0 < p < q gcd(p, q) = 1 w = -pu + qv
in that case, the sequence (u i ) i is unique and the integers c = (c i ) i such that ∆(u) = c × u are given by the following algorithm, where we denote d i = c i + 2 :

t 0 = p q , ∀i ∈ {1, .., r -1}, d i = 1 t i ; t i+1 = - 1 t i and t r = 0 ( stop condition )
Remark 2 : the above coefficients (d i ) i∈{1,..,r-1} are the coefficients of the ceiling continued fraction expansion of q p . That is to say :

q p = d 1 - 1 d 2 - 1 d 3 -• • •
Unlike the usual continued fraction algorithm, that is of quadratic complexity in terms of the binary size of inputs, this one is exponential in worst cases : indeed, if we take q = n and p = n -1, then we obtain a sequence of n -1 digits all equal to 2, for the ceiling continued fraction expansion of 1/n.

There exists a relation between this two types of continued fraction expansion, but it is not obvious and will be explicited in 4.1.

However, we can easily give some relation for ceiling convergents : we denote ⌈d 1 , d 2 , • • • , d r ⌉, the ceiling continued fraction expansion of q p , as above. We also define, for i ∈ {1, .., r}, the ceiling convergent

q i p i = ⌈d 1 , d 2 , • • • , d i ⌉. Hence : ∀i ∈ {1, .., r}, p i = d i p i-1 -p i-2 , q i = d i q i-1 -q i-2
with p -1 = -1, p 0 = 0, q -1 = 0, q 0 = 1. The proof of this result is similar to the proof for classical partial quotients...

Proof :

(i) We suppose that we have a modular-convex sequence (u i ) i∈{0,..,r} in R n such that u 0 = u, u 1 = v and u r = w. Let us denote (-x i , y i ) the coordinates of u i in (u, v), for it is clear that all u i are integer combinations of (u, v). We also denote (d i ) i∈{1,..,r-1} , such that :

∀i ∈ {1, .., r -1}, u i+1 = d i u i -u i-1
Then, all d i are integers greater than one. We have x 0 = -1, x 1 = 0, x 2 = 1 and y 0 = 0, y 1 = 1, y 2 = d 1 . Yet, (x i ) i and (y i ) i are modular-convex and x 1 max(x 0 , 0) and y 1 max(y 0 , 0), so ( see Remark 1) they are convex. In addition, x 1x 0 > 0 and y 1y 0 > 0, so (x i ) i 0 and (y i ) i 0 are increasing sequences. Likewise, if we denote ǫ i = y ix i for i ∈ {0, .., r}, then (ǫ i ) i is modular-convex, so convex and non decreasing, since ǫ 0 = ǫ 1 > 0. Thus, ǫ i > 0 for all i. So, 0 < p < q and half of (i) is proven.

With same arguments, we prove that (d 1 x iy i ) i 2 is a non negative and increasing sequence, for

d 1 x 2 -y 2 = 0 and d 1 x 3 -y 3 = 1. Similarly, we prove that (y i -(d 1 -1)x i ) i 1 is a positive and increasing sequence, for y 1 -(d 1 -1)x 1 = 1y 2 -(d 1 -1)x 2 . So : ∀i ∈ {2, .., r}, d 1 = ⌈y i /x i ⌉
Thus, in particular, d 1 = ⌈y r /x r ⌉ = ⌈q/p⌉. Now, we can do the same with (u 1 , u 2 ) instead of (u 0 , u 1 ), for u 1 and u 2 are linearly independant and all u i , i ∈ {1, .., r} are in the lattice generated by these two vectors, and so on... If we denote, for k ∈ {1, .., r}, (-X k , Y k ) the coordinates of u r in the basis (u k-1 , u k ) of the lattice L generated by (u 0 , u 1 ), then : X 1 = x r = p, Y 1 = y r = q and X r = 0, Y r = 1. We also have the following induction relations :

∀k ∈ {1, .., r -1}, X k = Y k+1 ; Y k = d k Y k+1 -X k+1
We deduce, by obvious decreasing induction on k, that gcd(X k , Y k ) = 1 for all k, so gcd(p, q) = 1. Now, we have proved that d 1 = ⌈Y 1 /X 1 ⌉ and more generally that

d k = ⌈Y k /X k ⌉ for all k ∈ {1, .., r -1}. So, if we denote t k = X k Y k , then t r = 0 and : ∀k ∈ {1, .., r -1}, d k = 1 t k ; t k+1 = d k - 1 t k = - 1 t k
(ii) Now, we suppose that w = qvpu, with p, q two coprime positive integers, such that p < q. We define a finite sequence (d i ) i∈{1,..,r-1} , as we use the algorithm detailed in Proposition 4. Indeed, we obtain t r = 0 for a certain positive integer r, because if we denote t k = X k Y k the reduced fraction ( for k 1), then :

∀k 1, 0 X k+1 < Y k+1 = X k for t k+1 ∈ [0, 1[. Since, for all k, we have t k ∈ [0, 1[, then 1/t k > 1, so d k 2.
We define the sequence (u i ) i∈{1,..,r} in L by :

u 0 = u, u 1 = v, ∀i ∈ {1, .., r -1}, u i+1 = d i u i -u i-1
This sequence is modular-convex and u r = w, according to (i) above.

3.2 irreducible elements of certain submonoids of Z or Z 2

• The following result is a complement to Lemma 9 and is important for next subsection : as usual, we consider the product order on Z 2 and denote C * = N 2 \{(0, 0)} the positive cone.

Lemma 10 let d and m be two coprime integers such that 0 < m < d. Let u 0 = (d, 0), u 1 = (m, 1) and L = Span Z (u 0 , u 1 ). We denote (d i ) i∈{1,..,r-1} the coefficients of the ceiling continued development of m/d and (u i ) i∈{0,..,r} the modular-convex sequence defined by u 0 , u 1 and u r = (0, d) ( see Proposition 4, for (0, d) = -mu 0 + du 1 ). Reminder : (x(u i )) i is decreasing and (y(u i )) i is increasing.

Let a, b be two integers such that 0 < a < b and w = (b, -a) ∈ L. We denote S * = C * + wZ.

(i) min(L ∩ C * ) = {u i , i ∈ {0, .., r}} (ii) min(L ∩ S * ) ⊂ min(L ∩ C * ) + wZ (iii) ◮ Case 1 : if d < a < b : min(L ∩ S * ) = {u i , i ∈ {0, .., r}} + wZ ◮ Case 2 : if a < d < b : min(L ∩ S * ) = {u i , i ∈ {0, .., s}} + wZ where y(u s ) < a y(u s+1 ). ◮ Case 3 : if d < a < b : min(L ∩ S * ) = {u i , i ∈ {σ, .., s}} + wZ
where y(u s ) < a y(u s+1 ) and x(u σ ) < b + x(u s ) x(u σ-1 ).

Remark 1 : as we have seen in Lemma 2, min(L ∩ S * ) is w-invariant, since S * and L are w-invariant. So, we can choose representatives of "classes modulo w" of minimal points in the strip :

A = {(x, y), x ∈ N, y ∈ {0, .., a -1}}
We remark that the u i that appear above are in A.

Remark 2 : we could summarize the above three cases in one formulation :

min(L ∩ S * ) = {u i , i ∈ {σ, .., s}} + wZ
where y(u s ) < a y(u s+1 ) and x(u σ ) < b + x(u s ) x(u σ-1 ). With additional border conditions : x -1 = y r+1 = +∞.

Proof :

(i) we remark that for all x, y ∈ Z, xu 0 + yu 1 = (xd + ym, y), so : on every " horizontal segment" of Z 2 of length d, there is a unique point of L. On the other hand, since m and d are coprime, xd + ym = 0 only if y is a multiple of d : so on every " vertical segment" of Z 2 of length d, there is a unique point of L. We deduce that u 0 , u 1 , u r ∈ min(L ∩ C * ) and so min(L ∩ C * ) = min(L ∩ R), with R = ({0, .., d} 2 ) * . Now, according to Lemma 9, min(L ∩ R) can be enumerated by a modular-convex sequence (v i ) i∈{0,..,r ′ } such that (x(v i )) i is decreasing and (y(v i ) i is increasing. So, v 0 = u 0 , v 1 = u 1 and v r ′ = u r . Now, using Proposition 4, we deduce that r ′ = r and v i = u i for all i ∈ {0, .., r}.

(ii) let u ∈ min(L ∩ S * ) and u ∈ A. Then, u ∈ L ∩ C * , since A ⊂ C * . If there exists v ∈ L ∩ C * such that v < u, then v ∈ L ∩ S * , which contradicts the fact that u is minimal in L ∩ S * . So, u ∈ min(L ∩ C * ). We have proved that : min(L ∩ S * ) ∩ A ⊂ min(L ∩ C * )
We deduce (ii) with Remark 1 above.

(iii) ◮ Case 1 : if d < a < b. Let i ∈ {0, .., r}, then u i ∈ A. Moreover : 0 x(u i ) d < b and 0 y(u i ) d < a
Now, we suppose that we have v ∈ L ∩ S * such that v < u i . Then, there exists an integer k, such that v ′ = vkw ∈ C * . But, k can not be positive, for we would have x(v ′ ) = x(v)kb < 0 and k can not be negative, for we would have y(v ′ ) = y(v) + ka < 0. Hence k = 0 and v ∈ C * , which contradicts (i)... So, u ∈ min(L ∩ S * ). We conclude with (ii). ◮ Case 2 : if a < d < b. We use the same arguments as in Case 1, if i ∈ {0, .., s}. If, i ∈ {s + 1, .., r}, then u i ∈ A. In addition, x(u i ) 0 and y(u i ) a, so

u i > (-b + d, a) = u 0 -w. But, u 0 -w ∈ L ∩ S * , so u i ∈ min(L ∩ S * ). ◮ Case 3 : if a < b < d. If i ∈ {s + 1, .., r}, then u i ∈ A. If i ∈ {0, .., σ -1}, let v = u s + w ∈ L ∩ S * . Then v < u i , for x(v) = b + x(u s ) x(u i ) and y(v) = y(u s ) -a < 0 y(u i ). So u i ∈ min(L ∩ S * ).
Now, let i ∈ {σ, .., s}. We suppose that there exists v ∈ L ∩ S * such that v < u i . Then, we claim that v ∈ C * . Indeed : we have an integer

k such that v ′ = v -kw ∈ A. --if k < 0, then y(v) = y(v ′ ) -ka a, which contradicts v < u i , for y(u i ) < a. --if k > 0, then 0 x(v ′ ) x(v) -kb x(u i ) -b < x(u s ) But, v ′ ∈ L ∩ C * ,
so there exists j ∈ {0, .., r}, such that v ′ u j ( see (i)). The above inequality proves that j > s and so y(v ′ ) y(u j ) a, which contradicts v ′ ∈ A.

So, v ∈ L ∩ C * and v < u i : it is impossible according to (i).

• the previous Lemma is important, because these minimal sets are related with minimal generators and irreducible elements ( see beginning of section 2.) in the following meaning : Let M be a submonoid of (R n , +) such that 0 is the unique invertible element of M . Gen(M ) denotes the intersection of all sets of generators ( as a submonoid) of M . The elements of Gen(M ) are the minimal generators of M .

Lemma 11 let L be a lattice of Z 2 . min(L ∩ (N 2 ) * ) = Gen(L ∩ N 2 ) = Irr(L ∩ N 2 )
Proof :

we denote C * = (N 2 ) * . -" Irr ⊂ min" : if u ∈ L ∩ C * is not minimal in L ∩ C * , then there exists v ∈ L ∩ C * such that v < u. Note v ′ = u -v, then v ′ ∈ L ∩ C * and u = v + v ′ , so u ∈ Irr(L ∩ N 2 ). -" min ⊂ Gen" : if m ∈ min(L ∩ C * ) and (u k ) k∈I is a system of generators of L ∩ N 2 , say L ∩ N 2 =< u k , k ∈ I >. Then , m = k∈I α k u k ,
where α k ∈ N for all k. Yet, m = (0, 0), thus there exists a k ∈ I, such that α k 1 and so m u k , since all u i (0, 0). Yet u k ∈ L ∩ C * , so m = u k and m belongs to every set of generators of L ∩ N 2 .

-" Gen ⊂ Irr" : suppose that u ∈ L ′ ∩ N 2 and u ∈ Irr(L ∩ N 2 ). Then, we can find u 1 and u 2 in L ′ ∩ N 2 , such that u = u 1 + u 2 . So that we can replace u by (u 1 , u 2 ) in any system of generators of L ∩ N 2 that would contain u : u ∈ Gen(L ∩ N 2 ).

• We now state a result that will we improved later ( see Theorem 5). It gives an expression of Irr( <a,b> d ) in terms of a, b, d and is a consequence of Lemma 8 and Proposition 2.

y 0 = 0, y 1 = 1, ∀i ∈ {1, .., r -1}, y i+1 = d i y i -y i-1 x 0 = d, x 1 = m, ∀i ∈ {1, .., r -1}, x i+1 = d i x i -x i-1
in addition, we denote y r+1 = x -1 = +∞.

n 0 = a, n 1 = am + b d , ∀i ∈ {1, .., r -1}, n i+1 = d i n i -n i-1
Then x r = 0, y r = d, n r = b, (x i ) i is decreasing and (y i ) i is increasing. In addition :

◮ Case 1 : if d < a < b Irr < a, b > d = {n i , i ∈ {0, .., r}} ◮ Case 2 : if a < d < b Irr < a, b > d = {n i , i ∈ {0, .., s}}
where s is such that y s < a y s+1 .

◮ Case 3 : if a < b < d Irr < a, b > d = {n i , i ∈ {σ, .., s}}
where s is such that y s < a y s+1 and σ is such that x σ < x s + b x σ-1 .

Proof :

If we denote q i /p i the reduced fraction of ⌈d 1 , d 2 , • • • , d i ⌉ ( see the remark below Proposition 4), then, with obvious induction :

∀i ∈ {0, .., r}, x i = -dp i-1 + mq i-1 , y i = q i-1 , n i = -ap i-1 + τ q i-1
where τ = am+b d . So x r = -dp r-1 +mq r-1 = -dm+md = 0, y r = q r-1 = d and n r = -ap r-1 +τ q r-1 = -am + τ d = b. Now, by obvious induction, (y i ) i is increasing and (x i ) i is decreasing.

Let us consider now ( with the product order in Z 2 ) :

L = {(x, y) ∈ Z 2 , ax + by = 0[d]} ; M = min(L ∩ N 2 \{(0, 0)})
But (d, 0) and (0, d) are in M , so M = min(L ∩ (({0, .., d}) 2 ) * ). So, according to Lemma 7, M can be enumerated by a finite modular-convex sequence (u i ) i∈{0,..,r} such that (x(u i )) i is decreasing and (y(u i )) i is increasing. We have u 0 = (d, 0) and u r = (0, d). Moreover, (m, 1) ∈ L, so (m, 1) ∈ M and u 1 = (m, 1). Now, u r = -mu 0 + du 1 and 0 < m < d. In addition, gcd(m, d) = 1, since gcd(b, d) = 1. With Proposition 4, (u i ) i satisfy the induction relation :

∀i ∈ {1, .., r -1}, u i+1 = d i u i -u i-1
So, x i = x(u i ) and y i = y(u i ) for i ∈ {0, .., r}. We deduce : n i = ψ(u i ) for i ∈ {0, .., r}, where ψ : (x, y) → ax+by

N-independance of sequences of integers

• Now, we are almost ready to give the solutions of the " reverse problem", that is to say : to provide all triplets of coprime positive integers a, b, d such that 0 < a < b and Irr( <a,b> d ) is a given finite subset of N. At the beginning of this section, we have reminded the necessary conditions for a finite subset I of N to be the set of minimal generators of some <a,b> d . One of them is of course, that elements of I are N-independant. Let us precise this notion and give a useful criterion :

First, we remind a notation : for a subset A of a monoid M , < A > denotes the submonoid of M generated by A.

Definition 2 elements of a subset A of a monoid M are N-independant if and only if :

∀a ∈ A, a ∈< A\{a} >
Remark : we will name also " A is N-independant" such a definition.

For our purpose, we deal with the particular case of the monoid N. Let A be a subset of N. We claim that :

A is N-independant ⇔ Irr(< A >) = A
Question : given a finite set A of positive integers, do we have an efficient algorithm to know if A is N-independant or not ? It is difficult to answer this question in general, but in the particular case when A can be enumerated by a modular-convex sequence, we have a simple criterion, stated in Proposition 6. But, first, we need an arithmetic Lemma, that will be also useful later ( see Theorem 2 and 3) :

Lemma 12 let a, b, c be three non null integers such that b and c are coprime. There exists an infinity of positive integer k, such that a and kcb are coprime.

Proof :

for any prime divisor p of a, we consider : With chinese remainder Lemma, we obtain that k is such that kcb and a are coprime if and only if k take certain values modulo q = p∈P(a) p. Now, we propose a result that gives a criterion for a modular-convex sequence of positive integers to be N-independant, but also the description of Irr(< A >) for A enumerated by such a sequence. We will use what we have named the " ceiling continued fraction expansion " of a rational x, denoted ⌈d 1 , d 2 , • • • , d r ⌉, as well as q i p i i>0 the finite sequence of " ceiling partial quotients" of x, defined by ( see 3.1):

K p = {k ∈ Z, kc = b[p]} if c = 0[p], then K p is
p -1 = -1, p 0 = 0, ∀i ∈ {1, .., r}, p i = d i p i-1 -p i-2
q -1 = 0, q 0 = 1, ∀i ∈ {1, .., r}, q i = d i q i-1q i-2 Proposition 6 let (n i ) i∈{0,..,r} be a modular-convex sequence of positive integers such that n 0 and n 1 are coprime. We denote (d i ) i the sequence of integers such that :

∀i ∈ {1, .., r -1}, d i ∈ N, d i 2, n i+1 = d i n i -n i-1
We also denote q i p i the reduced fraction of ⌈d 1 , d 2 , • • • , d i ⌉ for all i ∈ {1, .., r -1} ( see 3.1). More explicitly, (q i ) i∈{-1,..,r-1} is the following sequence :

q -1 = 0, q 0 = 1, ∀i ∈ {0, .., r -1}, q i = d i q i-1 -q i-2 (i) {n i , i ∈ {0, .., r}} is N-independant ⇔ q r-1 < min(n 0 , n r ) (ii) Irr(< n i , i ∈ {0, .., r} >) = {n i , i ∈ {σ, .., s}}
where s is such that y s < n 0 y s+1 and σ is such that x σ < x s + n r x σ-1 , with x -1 = y r+1 = +∞ and : ∀i ∈ {0, .., r}, y i = q i-1 ;

x i = p r-1 q i-1 -q r-1 p i-1
Remark 1 : as we have already seen in 3.1, the algorithm that computes the " ceiling continued fraction expansion" of a fraction is of exponential complexity in worst cases. But here, the entries are the (d i ) i , so computing q r-1 is very fast... Remark 2 : again, we have already mentioned that, for a modular-convex sequence (n j ) j∈{0,..,r} , we have gcd(n i-1 , n i ) = gcd(n 0 , n 1 ) for all i ∈ {1, .., r}, so gcd((n j ) j∈{0,..,r} ) = gcd(n 0 , n 1 ). A bit more general statement of Proposition 6 would propose the criterion :

{n i , i ∈ {0, .., r}} is N-independant ⇔ q r-1 < min(n 0 , n r ) gcd(n 0 , n 1 )
Remark 3 : The proof will appear to be an application of Lemma 10. It is quite direct, if the first and last term of the sequence are coprime, but more intricate when they are not. We will use an argument of limit in that last case...

Proof :

(i) is a direct consequence of (ii), for y r = q r-1 = x 0 and x r = 0. ( see below) (ii) let u 0 = (q r-1 , 0), u 1 = (p r-1 , 1) and (u i ) i∈{0,..,r} defined by : ∀i ∈ {1, .., r -1},

u i+1 = d i u i -u i-1
Then x(u i ) = x i and y(u i ) = y i for all i ∈ {0, .., r}, by obvious induction. So, u r = (0, q r-1 ). We also remark that :

∀i ∈ {0, .., r}, x i = p r-1 q i-1 -q r-1 p i-1 = p r-1 p i-1 q r-1 q i-1
We denote a = n 0 and b = n r and define a map ψ from Z 2 to (1/q r-1 )Z :

∀x, y ∈ Z, ψ(x, y) = ax + by q r-1

We have ψ(u 0 ) = n 0 and ψ(u r ) = n r . We claim that : ψ(u i ) = n i for all i. Indeed, if we denote ǫ i = ψ(u i )n i for all i, then ǫ 0 = 0 and :

∀i ∈ {1, .., r -1}, ǫ i+1 = d i ǫ i -ǫ i-1
Then, by obvious induction, ǫ i = ǫ 1 y i for all i ∈ {0, .., r}. But, ǫ r = 0 and y r = q r-1 , so ǫ 1 = 0. We deduce :

∀i ∈ {0, .., r}, ψ(u i ) = n i Now, we denote L = Span Z (u 0 , u 1 ). With Lemma 10 and 11, we obtain :

Gen(L ∩ N 2 ) = min(L ∩ (N 2 ) * ) = {u i , i ∈ {0, .., r}}
Let S =< n i , , i ∈ {0, .., r} >. Then, S = ψ(L ∩ N 2 ). We also remark that, if we denote w = (b, -a), then w = n 1 u 0au 1 ∈ L, for n 1 = apr-1+b qr-1 .

◮ Case 1 : if gcd(n 0 , n r ) = 1. Then, ker(ψ) = wZ, so :

ψ -1 (S) = (L ∩ N 2 ) + wZ = L ∩ (N 2 + wZ)
So with Lemma 1 and 3, ψ -1 (Irr(S)) = min(L ∩ S * ), where S * = (N 2 ) * + wZ. We conclude with Lemma 10. ◮ Case 2 : if gcd(n 0 , n r ) > 1. According to Lemma 12, there exist an infinite number of integer d r , such that d r 2 and n 0 , n r+1 are coprime, if we denote n r+1 = d r n rn r-1 . For these values of n r+1 , the sequence (n j ) j∈{0,..,r+1} satisfy the assumptions of Case 1. We denote :

q r = d r q r-1 -q r-2 ; p r = d r p r-1 -p r-2
So, we obtain :

Irr(< n i , i ∈ {0, .., r + 1} >) = {n i , i ∈ {σ, .., s ′ }} where s ′ is such that y ′ s ′ < n 0 < y ′ s ′ +1 and σ is such that x ′ σ < x ′ s ′ +n r+1 < x ′ σ-1 , with x ′ -1 = y ′ r+2 = +∞ and (x ′ i ) i , (y ′ i ) i defined by : ∀i ∈ {-1, .., r + 1}, y ′ i = q i-1 ; x ′ i = p r p i-1 q r q i-1
So, y ′ i = y i for all i ∈ {0, .., r}, while y r+1 = +∞ and y ′ r+1 = q r . So, we just have to choose d r large enough so that q r > n 0 , to obtain s ′ = s ( s being defined as in Proposition 5). Again, we can choose d r large enough such that n r+1 ∈< n 0 , n 1 >. Then, < n i , i ∈ {0, .., r + 1} >=< n i , i ∈ {0, .., r} >. Now, we denote (X i ) i the sequence defined by : ∀i ∈ {0, .., r -1}, X i = p r-2 p i-1 q r-2 q i-1

Then, we can write : ∀i ∈ {0, .., r -1}, x ′ i = tx i -X i where t = d r We also have : n r+1 = tn rn r-1 . So, the conditions on (x ′ i ) i , mentioned above, become :

n r-1 + X s -X σ < t(n r + x s -x σ ) (1) t(n r + x s -x σ-1 ) n r-1 + X s -X σ-1 (2)
Since t can be as large as we want, condition (1) is equivalent to :

n r + x s -x σ > 0 or n r + x s -x σ = 0 n r-1 + X s -X σ < 0 Suppose now that x σ -x s = n r = b.
We have u σ , u s ∈ L and w ∈ L ( see remark just before Case 1), so v = u σu sw ∈ L. But x(v) = 0, so y(v) = kq r-1 , for some integer k ( there is only one point of L on each vertical line of Z 2 of length q r-1 ). So, n σn s = kn r : contradiction with the fact that n s , n σ ∈ Irr(< n i , i ∈ {0, .., r} >). We have proved that n r + x sx σ = 0, so condition (1) and (2) ( that we treat with similar arguments) are equivalent ( for t large enough) to :

x σ < x s + n r < x σ-1 ⇔ x σ < x s + n r x σ-1

solutions

• We remind our " reverse problem" : if r is a positive integer and (n i ) i∈{0,..,r} is a finite sequence of positive integers satisfying conditions (i),(ii),(iii) detailed at the beginning of section 3, what are the triplets (a, b, d) of coprime positive integers, such that a < b and Irr( <a,b> d ) = {n i , i ∈ {0, .., r}} ?

We also recall some notations : we have defined by induction in 3.1 the notation ⌈d

0 , d 1 , d 2 , • • • , d i ⌉, as follows : ⌈d 0 , d 1 , d 2 , • • • , d i ⌉ = d 0 - 1 ⌈d 1 , d 2 , • • • , d i ⌉
This is a variant of the usual convergents of continued fraction and has been named : " ceiling convergents". The (d i ) i are integers such that d i 2 for all positive i. To every real α, we can associate such a sequence of (d i ) i which is infinite if α is irrational and finite else ( plus an infinite (+∞)-tail). Then, α is the limit of the sequence of above " ceiling convergents". The algorithm to obtain these coefficients has been detailed for rationals in 3.1 and is generalized in 4.1 to the case of irrationals.

Remark : in the proof of next three Theorems, we will have integers a, b, d, m, n 1 such that b = dn 1am, gcd(d, m) = 1 and gcd(a, n 1 ) = 1. We will deduce then : gcd(a, b) = gcd(a, d) = gcd(b, d)

• First, we look for solutions (a, b, d) such that d < a < b. In that case, the situation is very constraint and we obtain a finite number of solution ( one in general) :

Theorem 1 ( Reverse-problem, solutions (a, b, d) such that d < a < b) . let I be a finite subset of N\{0, 1}.

(i) if I is N-independant and can be enumerated by a modular-convex sequence (n k ) k∈{0,..,r} , such that : gcd(n 0 , n r ) = 1 and n 0 < n r , then I = Irr( <a,b> d ), where a = n 0 , b = n r and d ∈ {1, .., a -1} such that dn 1 = b[a].

(ii) there are as many triplets of coprime integers (a, b, d) such that 1 < d < a < b and I = Irr( <a,b> d ), as there are sequences of integers (n k ) k that verify conditions of (i). Proof :

(i) we denote a = n 0 , b = n r and (d i ) i∈{1,..,r-1} the sequence of integers such that :

∀i ∈ {1, .., r -1}, d i 2, n i+1 = d i n i -n i-1
Let m, d be coprime positive integers such that :

1 - m d = ⌈1, d 1 , d 2 , • • • , d r-1 ⌉ that is : d m = ⌈d 1 , d 2 , • • • , d r-1 ⌉
Since I is N-independant, we can use Proposition 6 and claim that : d < min(a, b).

In addition, by obvious induction ( see the proof of Proposition 5, for example) :

∀i ∈ {0, .., r}, n i = q i-1 n 1p i-1 n 0 ; where

q i p i = ⌈d 1 , d 2 , • • • , d i ⌉ so b = n r = dn 1 -mn 0 and am + b = dn 1 = 0[d].
In addition, a and b are coprime, so a, b, d are pairwise coprime ( see remark above). Yet, m ∈ {1, .., d -1} and d ∈< a, b >, so we can apply Proposition 5 ( Case 1) and we obtain our result.

(ii) direct consequence of (i) and Proposition 5 ( Case 1).

Examples : at the beginning of this section, we have seen an example of a N-independant set of integers, namely I = {7, 11, 59}, that can be enumerated by two different modular-convex sequences verifying conditions of Theorem 1 (i) : [START_REF] Froberg | On numerical semigroups[END_REF][START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF]59) What about I = {10, 17, 24} ? I is N-independant ( esay to check) and is enumerated by the modular-convex sequence (10, 17, 24) ( d 1 = 2), but 10 and 24 are not coprime. We also remark that [START_REF] Wilf | A circle-of-lights algorithm for the money-changing problem[END_REF][START_REF] Kaplan | Counting numerical semigroups by genus and some cases of a question of Wilf[END_REF]24) is not modular-convex. So, there is no enumeration of I by a sequence verifying conditions of (i) : for all triplets (a, b, d) of pairwise coprime positive integers such that d < a < b, we can claim that I = Irr( <a,b> d ).

• Secondly, we consider solutions such that a < d < b. In that case, we can extend in one direction the sequence (n i ) i in a modular-convex sequence. We then obtain an infinite number of solutions :

Theorem 2 ( Reverse-problem, solutions (a, b, d) such that a < d < b) . let I be a finite subset of N\{0, 1} that is N-independant and can be enumerated by a modularconvex sequence (n k ) k∈{0,..,r} , such that n 0 and n 1 are coprime. We denote (d i ) i∈{1,..,r-1} the sequence of integers such that :

∀i ∈ {1, .., r -1}, d i 2, n i+1 = d i n i -n i-1
(i) Let ρ be an integer such that ρ > r and (d i ) i∈{r,..,ρ-1} a sequence of integers bigger than 1.

We denote d and m the coprime positive integers such that

d m = ⌈d 1 , d 2 , • • • , d ρ-1 ⌉ and q i p i the reduced fraction of ⌈d 1 , d 2 , • • • , d i ⌉ for all i ∈ {1, .., ρ -1}.
We denote a = n 0 and b = dn 1mn 0 . Then :

     gcd(a, b) = 1 a q r d < b ⇒ a < d < b
Irr <a,b> d = I

(ii) all triplets of pairwise coprime (a, b, d) such that Irr <a,b> d = I and a < d < b can be obtained as in (i).

(iii) there is an infinity of pairwise coprime (a, b, d) such that Irr <a,b> d = I, a < d < b and ρ = r + 1 in (i).

Proof :

(i) we suppose that a and b are coprime, a q r and d < b. We have d = q ρ-1 and (q i ) i is an increasing sequence, so : a q r d < b.

Yet, a = d, for gcd(a, b) = 1. So a < d < b. We use Proposition 5 ( case 2) and obtain :

Irr < a, b > d = {n i , i ∈ {0, .., s}}
where s is the index such that y s < a y s+1 and y i = q i-1 for all i ( obvious induction on i). But, a q r by hypothesis and q r-1 < a, because I is N-independant ( see Proposition 6). So s = r and we obtain our result (i). (ii) a direct consequence of Proposition 5 ( case 2). (iii) using (i), the question is to find what values of d r , integer greater than 1, are such that : gcd(a, d r n rn r-1 ) = 1 (1) ; a < d r q r-1q r-2 < d r n rn r-1 [START_REF] Assi | Numerical Semigroups and Applications[END_REF] Indeed, if we choose ρ = r +1, then d = q r = d r q r-1 -q r-2 and b = n r+1 = d r n r -n r-1 . But, q r-1 < n r , for I is N-independant ( see Proposition 6). So, condition (2) is valid for d r large enough. Now, n r-1 and n r are coprime, since n 0 , n 1 are coprime ( see remark 1 at the beginning of 3). So, with Lemma 12, condition (1) is valid for an infinite number of positive integers d r ... that proves our result.

Examples : we go back to our previous examples at the end of Theorem 1. We take I = {7, 11, 59}, we denote a = 7 and we search integers d 2 such that d 2 2, b = 59d 2 -11, d = 6d 2 -1 and gcd(a, b) = 1, a < d < b. We remark that the condition a < d < b will always be verified here and that the condition gcd(a, b) = 1 is equivalent to d 2 = -1 [START_REF] Froberg | On numerical semigroups[END_REF]. So :

∀k ∈ {2, .., +∞}, k = -1[7] ⇒ Irr < 7, 59k -11 > 6k -1 = {7, 11, 59}
Same arguments with the enumeration of I by [START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF][START_REF] Froberg | On numerical semigroups[END_REF]59), that is also modular-convex, gives :

∀k ∈ {2, .., +∞}, k = -1[11] ⇒ Irr < 11, 59k -7 > 10k -1 = {7, 11, 59}
We consider now I = {10, 17, 24} and obtain with similar arguments : • Finally, we search the solutions such that a < b < d. In that case, we can extend in both directions the sequence (n i ) i in a modular-convex sequence. We then obtain an infinite number of solutions :

∀k ∈ {6, .., +∞}, k = 3[5] ⇒ Irr < 10, 24k -17 > 2k -1 = {10,
Theorem 3 ( Reverse-problem : solutions (a, b, d) such that a < b < d) . let I be a finite subset of N\{0, 1} that is N-independant and can be enumerated by a modularconvex sequence (n k ) k∈{0,..,r} , such that n 0 and n 1 are coprime. We denote (d i ) i∈{1,..,r-1} the sequence of integers such that :

∀i ∈ {1, .., r -1}, d i 2, n i+1 = d i n i -n i-1
(i) Let ρ and ν be integers such that ρ > r and ν < 0. Let (d i ) i∈{ν+1,..,ρ-1} be an extension of (d i ) i∈{1,..,r-1} in a sequence of integers bigger than 1, that defines an extension of (n i ) i∈{0,..,r} in a modular-convex sequence (n i ) i∈{ν,..,ρ} , such that n i > 0 for all i. We denote d and m the coprime positive integers such that d m = ⌈d ν+1 , • • • , d ρ-1 ⌉ and q i p i the reduced fraction of ⌈d ν+1 , d ν+2 , • • • , d i ⌉ for all i ∈ {ν + 1, .., ρ -1}. Moreover q ν-1 = 0, q ν = 1 and p ν-1 = -1, p ν = 0. We denote a = n ν and b = dn ν+1mn ν and x i = mq i-1dp i-1 for all i ∈ {ν, .., ρ}. Then, n ρ = b and :

           gcd(a, b) = 1 a q r a < b < d x 0 < x r + b x -1 ⇒ Irr < a, b > d = I
(ii) all triplets of pairwise coprime (a, b, d) such that Irr <a,b> d = I and a < b < d can be obtained as in (i).

(iii) there is an infinity of pairwise coprime (a, b, d) such that Irr <a,b> d = I, a < b < d such that ν = -1, ρ = r + 1 in (i).

Proof :

(i) by obvious induction, we obtain : ∀i ∈ {ν, .., ρ}, n i = ax i + by i d where y i = q i-1

so n ρ = b, for x ρ = dmmd = 0 and y ρ = q ρ-1 = d. Now, we suppose that a and b are coprime, a q r and a < b < d. Then, a, b, d are pairwise coprime and using Proposition 5 Case 3, with indices in range {ν, .., ρ} instead of {0, .., r}, we obtain :

Irr < a, b > d = {n i , i ∈ {σ, .., s}}
where s, σ ∈ {ν, .., ρ} such that y s < a y s+1 and

x σ < x s + b x σ-1 .
But, a q r by hypothesis and q r-1 < a, because I is N-independant ( see Proposition 6). So s = r.

Our hypothesis x 0 < x r + b x -1 gives σ = 0, so we obtain result (i).

(ii) a direct consequence of Proposition 5 ( case 3), with a shift on indices of (n i ) i so that σ = 0.

(iii) so, we restrict ourselves to the extension of (d i ) i and (n i ) i by one term in both directions : that is to say, we choose ρ = r + 1 and ν = -1. Then, we search d 0 and d r two integers such that d 0 , d r 2 and :

n r+1 , n -1 ∈ N * (1) ; gcd(n 0 , n r+1 ) = 1 (2) ; d > max(n -1 , n r+1 ) (3) ; x 0 < x r +n r+1 x -1 (4)
where :

n r+1 = d r n r -n r-1 , n -1 = d 0 n 0 -n 1 and x -1 = d , x 0 = m d/m being the reduced fraction of ⌈d 0 , d 1 , • • • , d r ⌉ and q i /p i being the reduced fraction of ⌈d 0 , d 1 , • • • , d i ⌉.
In addition, p -1 = 0 and q -1 = 1. So, p r = m and q r = d. We can simplify condition (4). Indeed, we have here x r = 1, for x r = D r with following notation and result : ∀i ∈ {ν, .., ρ}, D i = q i-1 q i p i-1 p i then D i+1 = D i yet D ν = 1, so x r = 1. Condition (4) can be rewritten : m n r+1 < d. Now, d and m depends on d 0 and d r : we denote Q i /P i the reduced fraction of ⌈d 1 , • • • , d i ⌉, for all i ∈ {1, .., r}. We can also set P -1 = -1, P 0 = 0 and Q -1 = 0, Q 0 = 1. By obvious induction, we deduce :

∀i ∈ {-1, .., r}, p i = Q i ; q i = d 0 Q i -P i So : m = d r Q r-1 -Q r-2 ; d = d 0 (d r Q r-1 -Q r-2 ) -(d r P r-1 -P r-2 )
Let us summarize : -condition (1) is satisfied if d 0 and d r are large enough.

-condition (2) is satisfied for an infinite number of d 0 , when d r is fixed ( for gcd(n 1 , n 0 ) = 1) and for an infinite number of d r , when d 0 is fixed ( for gcd(n r-1 , n r ) = 1), according to Lemma 12.

-condition [START_REF] Cabanillas | A variant of Ostrowski numeration[END_REF]

reduces to d > n -1 if condition (4) is satisfied. But, if d r is large enough so that : d r Q r-1 -Q r-2 > n 0 , then d > n -1 , if d 0 is large enough ( see expressions of d and n -1 above) -condition (4) is equivalent to m n r+1 < d. But, since (n 0 , • • • , n r ) is N-independant, we have Q r-1 < n r ( see Proposition 6 (i))
, so m < n r+1 for d r large enough. Now, if d r is fixed, then n r+1 , P r and Q r are fixed and for d 0 large enough, we will have d > n r+1 , because :

d = d 0 Q r -P r
Conclusion : we first choose ( and fix) d r large enough so that n r+1 > 0, d r Q r-1 -Q r-2 > n 0 and n r+1 m. Then, we can choose an infinity of integers d 0 2 such that n -1 > 0, gcd(n 0 , n r+1 ) = 1, d > n -1 and d > n r+1 . That proves (iii).

Examples : again, we take our two examples :

First, I = {7, 11, 59}, enumerated by the modular-convex sequence [START_REF] Froberg | On numerical semigroups[END_REF][START_REF] Ramirez-Alfonsin | the Diophantine Frobenius Problem[END_REF]59)

∀k, j ∈ N, j 6, k 2 gcd(11j -7, 59k -7) = 1 ⇒ Irr < 11j -7, 59k -7 > 10kj -k -j = {7,
∀k, j ∈ N, j 13, k 6 gcd(10j -17, 24k -17) = 1 ⇒ Irr < 10j -17, 24k -17 > 2kj -k -j = {10, 17, 24}
• Now, we end this section with a very particular case : when I is an arithmetic sequence.

Corollary 1 let a and k be two coprime integers greater than 1 and r ∈ {1, .., a -1}. Then :

< a + jk, j ∈ {0, .., r} >= < a, a 2 + dk > ar + 1
If a and r are coprime, wa have a simpler result :

< a + jk, j ∈ {0, .., r} >= < a, a + rk > r Proof :

first, the sequence (a+jk) j∈{0,..,r} is N-independant. Indeed, with Proposition 6 and its notations, we have d i = 2 for all i ∈ {0, .., r -1}, so q i = i + 1, by obvious induction. Hence, we obtain q r-1 = r < a < a+ rk.

If a and r are coprime, then a and b are coprime, when we set b = a + rk. Moreover, if we denote d = r and n 1 = a + k, then d ∈ {1, .., a -1} and :

dn 1 = ar + rk = b mod a
So, we can apply Theorem 1 and obtain the result in that case. In the general case, we use Theorem 2 (i) and its notations, with ρ = r + 1 and d r = a + 1. We obtain d = ar + 1 and b = a 2 + dk. In addition, a and b are coprime and a q r = d < b.

Remark : as mentioned in the introduction, this result can be proven directly...

Diophantine approximation 4.1 two kinds of continued fraction expansions

All results given in this subsection are well known and we just want to recall some notations and simple facts. For all reals x, ⌊x⌋ denotes its floor ,⌈x⌉ its ceiling and {x} its fractional part. We have x = ⌊x⌋ + {x}.

• We have met in 3.1 the notion of " ceiling continued fraction expansion of a rational". We will precise the definition and remind some results about usual continued fraction expansion. One usually uses the Gauss map T , defined on ]0, 1[, by T (x) = {1/x} to define the usual continued fraction expansion of an irrational. We will rather use here a variant :

Let F and C be the following maps defined on R :

F :      R ∪ {+∞} →]1, +∞] x → +∞ if x ∈ Z ∪ {+∞} x → 1 {x} else ; C :      R ∪ {+∞} →]1, +∞] x → +∞ if x ∈ Z ∪ {+∞} x → 1 1-{x} else
We use the natural convention : ⌊+∞⌋ = ⌈+∞⌉ = +∞. By obvious induction, we can prove that : if α is not rational, then F k (α) = +∞ and C k (α) = +∞ for every k ∈ N. It is a consequence of euclidean algorithm on integers that : if α is rational, then F k (α) = C k (α) = +∞ for some positive integer k. Now, given a real α, we define two sequences ( named partial quotients ) by :

∀k ∈ N, a k = ⌊F k (α)⌋ ; d k = ⌈C k (α)⌉ If, α is an irrational, then a k and d k are positive integers for all k ∈ N and d k 2 if k > 0. If, α is a rational, then a k = d k = +∞ for k large enough.
[a k ] k∈N is the usual continued fraction expansion of x ( we could also name it the " floor continued fraction expansion" of x) and ⌈d k ⌉ k∈N is the " ceiling continued fraction expansion" of x. We usually define the ( usual or ceiling) convergents of α relative to these continued fraction expansions by : ∀i ∈ N,

p i q i = [a 0 , a 1 , • • • , a i ] ; p ′ i q ′ i = ⌈d 0 , d 1 , • • • , d i ⌉
if necessary, we will precise p i (α) q i (α) . The above brackets are inductively defined by ( with the usual convention : 1/∞ = 0) :

[a 0 , a 1 , • • • , a i ] = a 0 + 1 [a 1 , • • • , a i ] ; ⌈d 0 , d 1 , • • • , d i ⌉ = d 0 - 1 ⌈d 1 , • • • , d i ⌉
Thus, we can express these with finite fraction superpositions :

[a 0 , a 1 , • • • , a i ] = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + • • • ; ⌈d 0 , d 1 , • • • , d i ⌉ = d 0 - 1 d 1 - 1 d 2 - 1 d 3 -• • •
The sequences of ( usual or ceiling) convergents of α converge towards α.

For example : if α = 1+ √ 5 2
( the so-called " golden ratio"), then : a k = 1 for all k ∈ N, d 0 = 2 and d k = 3 for all k ∈ N * . Indeed : for these expansions we have :

x = 1 + 1 x and x = 2 - 1 1 +
x With these parallel definitions, we could expect similar properties...but, this is not the case : First, a useful Lemma that relates iterates of F and C : Lemma 13 let α be a real, but not an integer. We denote a = ⌊F (α)⌋.

∀i ∈ {1, .., a}, C i (α) = 1 + 1 F (α) -i So : C a (α) = 1 + F 2 (α)
Proof :

Second result is a direct consequence of the first result, which is obtained by finite induction on i : -it is true for i = 1, since, if we denote ǫ = {α}, then :

C(α) = 1 1 -ǫ and 1 + 1 F (α) -1 = 1 + 1 1 ǫ -1 = 1 + ǫ 1 -ǫ = 1 1 -ǫ -suppose it is true for i -1, with i ∈ {2, .., a}, then we remark that C i-1 (α) ∈]1, 2] for F (α)
i. The special case when i = a = F (α) leads to C i-1 (α) = 2 and so C i (α) = +∞ = 1 + 1 0 ( with usual convention). Now, we suppose that F (α) > a, so that C i-1 (α) ∈]1, 2[. Then :

C i (α) = 1 1 -{C i-1 (α)} = 1 2 -C i-1 (α) = F (α) -(i -1) F (α) -i = 1 + 1 F (α) -i
The following Lemma states the relations between the two kinds of partial quotients seen above, for the case of irrationals. The case of rationals will be treated later, for we will choose an alternate version of usual " last partial quotient" for a rational. Lemma 14 let α be an irrational and [a k ] k∈N , ⌈d k ⌉ k∈N its usual and ceiling continued fraction expansions. (i) ⌈d k ⌉ k∈N * is obtained from [a k ] k 1 by the following substitution of patterns :

∀i ∈ N * , (a 2i-1 , a 2i ) → ((2, ) a 2i-1 -1 , a 2i + 2)
(ii) for the converse : we denote (k i ) i∈N an increasing sequence of non negative integers such that k 0 = 0 and (

d k i ) i∈N * is the subsequence of values of (d k ) k∈N * such that d k = 2. Then : ∀i ∈ N * , a 2i-1 = k i -k i-1 a 2i = d k i - 2
Proof :

(ii) is a direct consequence of (i). For (i), we use previous Lemma : we will explain the process for the first step, namely i = 1. First, we recall that C i (α) and F j (α) are never integer since α is not rational. Then, as mentioned in the proof of Lemma 13, C i (α) ∈]1, 2[ for all i ∈ {1, .., a 1 -1}, so d i = 2 for these values of i.

Later, C a1 (α) = 1 + F 2 (α) and F 2 (α) is not an integer, so :

⌈C a1 (α)⌉ = 2 + ⌊F 2 (α)⌋
which proves that d a1 = a 2 + 2. Finally :

{C a1 (α)} = {F 2 (α)}
so, the process continues at the next step...

• There are two ways for usual continued fraction expansion of rationals : those ending with an integer greater than 1 ( and an infinite sequence of ∞) or those ending with 1 ( and an infinite sequence of ∞).

For example, 5/7 has two usual continued fraction expansions : [0, 1, 2, 2] and [0, 1, 2, 1, 1] ( the ending ∞ sequence has been omitted). We will choose the second way and denote CFE this kind of usual continued fraction expansion. The set of sequences representing CFE of this type, for reals, is then :

C = {(t k ) ∈ Z × N * × (N * ) N , ∀k 2, (t k = ∞ ⇒ (t k+1 = ∞ and t k-1 ∈ {∞, 1})}
Since we will be interested by natural order on reals and especially on rationals, we mention the corresponding order on CFE sequences : if we define ϕ by

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

(t k ) k∈N A (t ′ k ) k∈N ⇔ (∀k ∈ N, t k = t ′ k ) or ∃j ∈ N, ∀k < j, t k = t ′ k (-1) j t j < (-1) j t ′ j
• Now is the time to give a " rational version" of Lemma 14 :

Lemma 15 let α be a rational and (ii) ⌈d k ⌉ k∈{1,..,ρ} is obtained from [a k ] k∈{1,..,r} by the following substitution of patterns :

[a 0 , • • • , a r , 1], ⌈d 0 , d 1 , • • • , d ρ ⌉ its
∀i ∈ {1, .., ⌊r/2⌋}, (a 2i-1 , a 2i ) → ((2, ) a 2i-1 -1 , a 2i + 2)
if r is odd, then we add d ρ = 2.

(iii) for the converse : let (k i ) i∈{0,..,s} be an increasing sequence of non negative integers such that k 0 = 0, k s = ρ and (d k i ) i∈{1,..,s-1} is the subsequence of values of (d k ) k∈{1,..,ρ-1} such that d k = 2. Then s = ⌊(r + 1)/2⌋ and :

∀i ∈ {1, .., s}, a 2i-1 = k i -k i-1 a 2i = d k i -2 ( if 2i r)
Proof :

(i) and (ii) are direct consequences of (iii), that we prove as in the proof of Lemma 14, adding the following fact. If F (α) is an integer, then r = 1, a 1 = F (α) -1 and C a1 (α) = 2 ( see Lemma 13, with a = a 1 + 1). So,

d a1 = 2, ρ = a 1 , s = 1 and a 1 = k 1 -k 0 . If F 2 (α) is an integer, then a 1 = ⌊F (α)⌋, a 2 = F 2 (α) -1 and C a1 (α) = a 2 + 2 ( see Lemma 13). So, r = 2, d a1 = a 2 + 2, ρ = a 1 and s = 1.
As in the proof of Lemma 14, this can be generalized to the case : F j (α) is an integer for a positive integer j.

semi-convergents and best rational in an interval

• Let α be a real with CFE [a k ] k∈N and (p k /q k ) k its convergents sequence. 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 16 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 < ∞.

Remark : it would not be difficult to deduce that the ceiling convergents of α are exactly the semi-convergents of α that are greater or equal than α. ( see Lemma 15 and order on CFE)

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 .
• 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. : Definition 3 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 and will abreviate t and t ′ these CFE-sequences. We denote r the smallest integer k such that t k = t ′ k . If we suppose that t r < t ′ r , 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 result claims 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 7 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, so ∀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 :

see [3]( References) 1.4 Proposition 1.
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} , ∀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 : for p, q two integers, p/q is said a best left rational approximation of α if and only if :

∀q ′ ∈ {1, .., q} , ∀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} , ∀p ′ ∈ Z , p ′ q ′ p q α or p ′ q ′ < α
Here is a corollary of Proposition 7 :

Corollary 2 . (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 7. 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 } 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 q = max{N ∈ N, ∀n ∈ {0, .., N -1}, ⌊nα⌋ = ⌊nα ′ ⌋} (ii) let α be a real in [0, 1) and p/q a reduced fraction, with q ∈ N * , such that α is not the best left strict convergent of p/q. p/q is a semi-convergent of α ⇔ ∀k ∈ {0, .., q -1}, ⌊kα⌋ = ⌊kp/q⌋ Proof :

see proof of Proposition 8 in 4.2 of [3] ( References)
4.3 α-numeration for a rational α

• 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 its convergents, so that α = p r+1 /q r+1 . Definition 4 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.
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 α Proposition 9 the map Ψ α is an order isomorphism 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 :

see [3] 2.2. ( References)
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 k = 1 with step -1 :

d k = max 0, n-q k-2 q k-1 n ← n -d k q k-1
Remark : as a direct consequence : E α has q r+1 elements.

• 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 N 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-2 -a r δ r-1 δ r-1 = 1 T r-1 (α) -a r = 1
So : δ r = δ r-1 . We also have ( see [...]) δ 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 Proposition 10 . (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 :

see [3] 2.

( References).

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 ( with β 0 = β), we have :

(i) b ∈ E α . (ii) β = Λ α (b). 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
• We will also need a more general case : but it is sufficient to sort among the former values of n, those which are lower than N :

Lemma 18 let N ∈ {1, .., q -1}. We denote (N 1 , N 2 , • • • , N s ) the α-numeration of N , with N s > 0. The minimal points in R 2 of the set {({nα}, n), 1 n N } are for the following values of n :

(i) with the α-numeration of n ( the 0-tail is not written) :

(1) ; (1, j), j ∈ {1, .., a 2 } ; (1, a 2 , 0, j), j ∈ {1, .., a 4 }; (ii) with denominators of convergents of α :

q 0 ; q 2k-2 + jq 2k-1 , j ∈ {1, .., a ′ 2k }, k ∈ {1, .., ⌊s/2⌋}
where a ′ 2k = a 2k if 2k < s, and a ′ s = N s .

Proof :

It is a consequence of the former Lemma, when we remember ( see Proposition 9) that Ψ α is an increasing map from E α to {0, .., q -1}, with RLO. So, we just have to select, among the d of the previous results those which are lower than (N 1 , N 2 , • • • , N s ) for RLO. Indeed, no ({kα}, k), with k > N is lower than any ({nα}, n), with n N ...

• We generalize a bit more again , adding another condition : We denote t = min{i > 0, b 2i+1 > 0} and t = ⌊s ′ /2⌋ if ∀i > 0, b 2i+1 = 0 ( s ′ is even in that case). (i) with the α-numeration of n :

Lemma
(1, a 2 , 0, a 4 , • • • , a 2t-2 , 0, j) , j ∈ {b 2t , .., a ′ 2t } ; and

(1, a 2 , 0, a 4 , • • • , a 2k-2 , 0, j) ; j ∈ {1, .., a ′ 2k } ; k ∈ {t + 1, .., ⌊s/2⌋} where a ′ 2k = a 2k if 2k < s ; a ′ s = N s .
(ii) with denominators of convergents of α :

q 2k-2 + jq 2k-1 , j ∈ {c 2k , .., a ′ 2k }, k ∈ {t, .., ⌊s/2⌋}
with the same notations as in (i) and :

c 2k = b 2k if k = t 1 else .
Lemma 20 let q be a positive integer and α = p q , β = p ′ q , with p, p ′ ∈ {1, .., q -1} and p, q coprime. We denote α

= [0, a 1 , • • • , a r , 1] the CFE and (b 1 , b 2 , • • • , b s ) the α-numeration of β, where b s > 0. We denote t = (s + 1)/2 if ∀i > 0, b 2i = 0 min{i ∈ N * , b 2i = 0} else ( s is odd in the first case).
Minimal points of ({nα -β}, n) 1 n<q are obtained for following n, given by their α-numeration : (1) ( first ), (b i ) i ( last) and :

(1, a 2 , 0, • • • , a 2k-2 , 0, j) ; j ∈ {1, .., a 2k } ; k ∈ {1, .., t -1} (b 1 , b 2 , • • • , b 2k-1 , j) ; j ∈ {0, .., b 2k -1} ; k ∈ {t, .., ⌊s/2⌋}
Remark 1 : if b 2 > 0, that is to say if t = 1, then the first shape of α-numeration of n is absent. In addition, if b 1 = 1 and b 2 > 0, then we count two times the first minimal point for n = 1.

Remark 2 : if b 2i = 0 for all i, then the second shape of α-numeration of n is absent, except for (b i ) i .

Remark 3 : if the sequence begins at i = 0 instead of i = 1, then the point (1β, 0) obtained for n = 0 is obviously a minimal point of the sequence. So, the other minimal points ({nα}, n) must verify {nα} β. They are obtained for n with α-numeration :

(b 1 , b 2 , • • • , b 2k-1 , j) ; j ∈ {0, .., b 2k -1} ; k ∈ {t, .., ⌊s/2⌋} Proof :
As long as {nα} < β, minimal points of our sequence are obtained for the same values of n than those of ({nα}, n) n , because {nα -β} = {nα} + 1β. We remark that ( see definition of But, the above δ satisfies ν A b and ν is minimal ( for RLO) among these one. Furthermore :

∀n < n 1 , {nα -β} ∈ [1 -β, 1[ ; {n 1 α -β} ∈ [0, 1 -β[
Note that this is also true if b 2i = 0 for all i > 0 and that, in that case, we have ν = b and so {να} = β and no minimal point after this one... We return to the general case : we have seen just above that the lowest integer n such that {nα}

β is n 1 = (b 1 , b 2 , • • • , b 2t-1 ) α . So, for n < n 1 ,

multiplicity

The multiplicity of <a,b> d is the smallest positive integer k such that kd ∈< a, b >. We could deduce a formula from the result concerning the irreducible elements, because the multiplicity is the smallest element among these one. But, the following theorem is much more interesting, for it gives a very simple expression of m( <a,b> d ) in terms of " best rational in an interval"...

Lemma 21 let n be a positive integer and a, b be two coprime positive integers. We suppose that n = xayb = ab( x b -y a ), with x, y integers. Then :

n ∈< a, b > \(a{0, .., b -1}) ⇔ x b = y a Proof :
-we suppose that n ∈< a, b > \(a{0, .., b -1}), then we can find two integers i, j, such that n = ai + bj, j is positive and i is non negative. Indeed, if j = 0, then n = ai and i b, so n = ai ′ + bj ′ , with i ′ = ib and j ′ = a. So : (xi)a = (y + j)b. But, a and b are coprime, so it exists an integer k such that :

xi = kb and y + j = ka Proof :

We can write α ′ = x b and α = y a , with x and y are integers such that d = axby basic arithmetic, since a and b are coprime). We remark that : since d ∈< a, b >, then, with our previous Lemma, ⌊α⌋ = ⌊α ′ ⌋. We denote p/q the reduced best rational in [α, α ′ ]. We have two cases : if p/q = α, then q = a for y and a are coprime ( d and a are coprime). So qd ∈< a, b >. Else, we have qd = ab(qαaα ′ ) and ⌊qα⌋ = ⌊qα ′ ⌋ ( see Proposition 8), since p/q is the best rational in ]α, α ′ ] and α < α ′ . So our previous Lemma gives : qd ∈< a, b >. In both cases, we have qd ∈< a, b >. Now, for k ∈ {1, .., q -1}, kd = akxbky and Proposition 8 gives : ⌊kα⌋ = ⌊kα ′ ⌋ ( there is no rational i/k in ]α, α ′ ]). So : kd ∈< a, b > or kd ∈ aN. If kd ∈ aN, then k ∈ aN, for a and d are coprime. But q a, for α = y a , so k < a, contradiction.

minimal generators

• We begin with a result that describes precisely the minimal generators of <a,b> d , namely Irr( <a,b> d ) and so its cardinality e( <a,b> d ). The case d > max(a, b) is the most intricate... Let (p k /q k ) k its reduced convergents and for k ∈ {-1, .., r + 1}, δ k = (-1) k (q k αp k ), as defined in 4.3. We denote τ = am+b d and µ i = τ q iap i for all i ∈ {0, .., r}. We denote

(N 1 , • • • , N s ) the α-numeration of a -1 ( with N s > 0). We denote x 0 = d(δ s-2 -N s δ s-1 ) if s is even dδ s-1 else ; ν = N s if s is even 0 else .
All sets below are written with pairwise distincts elements.

◮ Case 1 : d < a < b. e < a, b > d = 3 + ⌊r/2⌋ k=1 a 2k Irr < a, b > d = {a ; b ; τ ; µ 2k-2 + jµ 2k-1 , j ∈ {1, .., a 2k }, k ∈ {1, .., ⌊r/2⌋}} ◮ Case 2 : a < d < b or (a < b < d and x 0 + b > d). e < a, b > d = 2 + ⌊ s-1 2 ⌋ k=1 a 2k + ν Irr < a, b > d = a ; τ ; µ 2k-2 + jµ 2k-1 , j ∈ {1, .., a 2k } if k ∈ {1, .., ⌊ s-1 2 ⌋} j ∈ {1, .., N s } if k = s/
2 , • • • , b s ′ ) its α-numeration, where b s ′ > 0. We also denote t = min{i > 0, b 2i+1 > 0} and t = s ′ /2 if ∀i > 0, b 2i+1 = 0 ( s ′ is even in that case).
Then , a ∈ Irr <a,b> d and :

Irr < a, b > d = µ 2k-2 + jµ 2k-1 , j ∈ {c 2k , .., a ′ 2k } , k ∈ {t, .., ⌊s/2⌋} where c 2k = b 2k if k = t 1 else and a ′ 2k = a 2k if 2k < s N s if 2k = s . e < a, b > d = 1 + a 2t -b 2t + ⌊ s-1 2

Examples :

We take a = 151 and b = 503. Then : -Now, e <a,b> d = 3 if and only if a 2k = 0 for all k > 0, with notations of Theorem 5. But, the a i are positive integers for positive indices i, so it means that r = 0 or 1. This is equivalent to the fact that α = [a 0 , a 1 , 1] or α = [a 0 , 1]. But, α ∈ Z, since d does not divide b, so : -Now, e <a,b> d is maximal if and only if all points (d{nα}, n) n∈{1,..,d-1} are minimal in L∩{1, .., d-1} 2 ( see proof of Theorem 5). This means that the sequence ({nα}) n∈{1,..,d-1} is decreasing ( with notations of Theorem 2). This is equivalent to d{α} = d -1, since all these points have different x and different y in {1, .., d -1}. In that case, d{nα} = dn for all n ∈ {1, .., d -1}. Hence, all the points above are pairwise not comparable. We can conclude :

Irr < a, b > 6 = {109,
e < a, b > d = 3 ⇔ 1 {α} ∈ N * ⇔ d m ∈ N * But,
e < a, b > d = d + 1 ⇔ m = d -1[d] ⇔ d/(b -a)
In that case, the minimal generators are : a, b and the -we have with same arguments as in Case 1 :

e(S ′ ) = 2 ⇔ s = 1 ⇔ a -1 a 1 ⇔ a -1 ⌊1/α⌋ ⇔ a -1 d/m
In that case, according to Theorem 5, Irr(S ′ ) = {a, τ }.

-we have e(S ′ ) = a if and only if all points (d{nα}, n) n∈{1,..,a-1} are minimal in L ∩ {1, .., d -1} × {1, .., a-1} ( see proof of Theorem 5). This means that the sequence ({nα}) n∈{1,..,a-1} is decreasing, that is to say u n+1u n = α -1 if we denote u 0 = 1 and u n = {nα}. This is equivalent to , (a -1)(1α) < 1 and gives our condition. In that case, we obtain :

∀n ∈ {1, .., a -1}, {nα} = α -(n -1)(1 -α) = nα -(n -1)
We deduce easily the expression of irreducible elements of S ′ . ◮ Case 4 : if a < b < d and x 0 + b m. We use Proposition 2, with the fact that there is no point in L ∩ {1, .., x 1 } × {0, .., a -1}, on the lines y = 0 and y = 1. So it remains a -2 lines for possible minimal points... -we have e(S ′ ) = a -2 if and only if each of the a -2 remaining lines contains one minimal point. This is equivalent to the fact that the sequence ({nα}) 2 n a-1 is decreasing and β. This gives our conditions, after similar considerations as in Case 2. The result on Irr(S ′ ) in that case is obtained as in Case 2.

pseudo-Frobenius numbers

We will distinguish several cases to make the statements more readable and in our proofs, we will use different " half-turn" in Z 2 to compute maximal points of a lattice in a rectangle ( see 2.3) :

• Let us begin with special cases, when PF is reduced to a single element or is obtained from Irr via a symmetry :

f < a, b > d = f (< a, b >) d = ab -a -b d ◮ Case 2 : if a = 1[d], then : PF < a, b > d = (a -1)b d -Irr < a, b > d \{b} ◮ Case 3 : if b = 1[d], then : PF < a, b > d = (b -1)a d -Irr < a, b > d \{a}
For cases 2 and 3, we obtain : t = e -1 for <a,b> b i (q i-1 αp i-1 ) + j(q 2k-1 αp 2k-1 ) + aβ Indeed, {nα -β} = {nα}β, becasue {nα} < β for these values of n. ( see Lemma 20). This gives our formula... For the type t(S ′ ), we remark that ψ is injective over R, if d < min(a, b) ( see Proposition 3).

• To be complete, we end with the case d > min(a, b), that is somwhat different : in the proof we use an half-turn u → vu, with v = (b, 0).

the Frobenius number

• Once we can compute PF-numbers of a numerical semigroup, we know that the Frobenius number is the greatest of them. In the expressions of PF-numbers that appear in Theorems 7 and 8, we have two parameters j and k that have values in a finite interval of integers. Moreover, we remark that, if k is fixed, then these expressions on j → H k (j) are affine, so monotonous. Hence, the maximum is obtained for an extremal value of j : that is to say 0 or 1 or a 2k or b 2k -1 ( if b 2k = 0 !). Remark that (b k ) k is not the same for Theorem Now, for which k do we obtain a maximum ? To answer this question, we think of our representation ( ψ : (x, y) → (ax + by)/d) of S = <a,b> d in Z 2 and remember that the points representing PF(S) ( see Lemma 8 and Proposition 3) can be parametrized by an x-decreasing sequence (u k ) k∈{1,..,t} that is order-concave in Z 2 ( with the partial product order), which means that : (u ku k-1 ) k is decreasing. But Theorem 7 and 8 give the PF-numbers of S, say (ψ(u i )) i , respecting the previous order ( see proof of these theorems). Consequence : if we denote (h i ) i that sequence of integers, then (h ih i-1 ) i is decreasing, for ψ is increasing ( a and b are positive). So, h i is the Frobenius number of S for the unique i such that h ih i-1 > 0 and h i+1h i < 0.

Yet, the slope of our affine functions H k is -µ 2k-1 , see notations in Theorem 7 and 8. So, (µ 2k-1 ) k is increasing and we will discuss the sign of µ 2k-1 . We recall that : ∀i ∈ {0, .., r}, µ i = τ q iap i = aq i α + b ad -

p i q i
where a, b, d are three positive pairwise coprime integers, α = m d , m ∈ {1, .., d -1} coprime with d, such that am + b = 0[d] and (p i /q i ) i∈{0,..,r} are the usual convergents of α. So, for all integer k ∈ {1, .., ⌊(r + 1)/2⌋} :

µ 2k-1 > 0 ⇔ p 2k-1 q 2k-1 -α < b ad ⇐ q 2 2k-1 > ad b
But, we will need more precise notations... Question : could we find a simpler formula for f ( <a,b> d ) ? If we refer to our proof and notations of Theorem 4, we can claim that : But, it is not so easy to compute this max...

  the general case for <a,b> d is when a, b, d are pairwise coprime. Indeed, for any integer d ′ coprime with b :

d: 2 ≃◮≃

 2 Proposition let L be the lattice L = {(x, y) ∈ Z 2 , ax + by = 0[d]}. ◮ Case 1 : if d < a < b, then a, b ∈ Irr <a,b> d min(L ∩ {1, .., d -1} 2 ) Case 2 : if a < d < b, then a ∈ Irr <a,b> d , b ∈ Irr <a,b> d min(L ∩ ({1, .., d -1} × {1, .., a -1})) ◮ Case 3 : if a < b < d, then : Irr < a, b > d ψ ≃ min(L ∩ {1, .., x 1 } × {0, .., a -1}) where x 0 = min{x(u), u ∈ (N × {1, .., a -1}) ∩ L} and x 1 = min(d, x 0 + b -1). so a ∈ Irr <a,b> d ⇔ x 0 > db. Remark : if d > max(a, b) and x 0 + b > d, then the result of Case 3 is the same as for Case 2. We can summarize all these cases as follows : there exists two positive integers c and c ′ such that : Irr <a,b> d ψ ≃ min(L ′ ∩ {0, .., c} × {0, .., c ′ }), where L ′ = L\{(0, 0)}. For case 1, c = c ′ = d, for case 2, c = d and c ′ = a -1, for case 3, c = x 1 and c ′ = a -1.

Proposition 5

 5 let a, b, d be three pairwise coprime positive integers such that d ∈< a, b > and d > 1. We denote m ∈ {1, .., d -1}, such that am + b = 0[d]. We denote ⌈d 1 , • • • , d r-1 ⌉ the ceiling continued fraction expansion of d m ( see the algorithm of Proposition 4) and define sequences of integers, by double induction :

  d . At the end, results for Irr <a,b> d are direct consequences of Proposition 2 ...

  empty, since b = 0[p] ( b and c are coprime). Else, K p is a class of congruence modulo p, say : K p = {k ∈ Z, k = r p [p]}. So, if we denote P(a) the finite set of prime divisor of a that does not divide c : ∀k ∈ Z, (gcd(a, kcb) = 1 ⇔ ∀p ∈ P(a), k = r p [p])

  17, 24}What do we obtain for k = 2, 4, 5, that is for values of k such that b > a > d ? Using Proposition 5, we obtain ( I = {10, 17,

( d 1

 1 = 6). We denote k = d 2 and j = d 0 . Then d = 6kj -k -j, m = 6k -1, b = 59k -11 and a = 7j -11. If k and j are two integers bigger than 1 and such that d > max(a, b) m > 0 and gcd(a, b) = 1, then Irr( <a,b> d ) = I. So : ∀k, j ∈ N, j 10, k 2 gcd(7j -11, 59k -11) = 1 ⇒ Irr < 7j -11, 59k -11 > 6kjkj = {7, 11, 59} On the other hand, I = {7, 11, 59} is enumerated by the modular-convex sequence (11, 7, 59) ( d 1 = 10). We denote k = d 2 and j = d 0 . Then d = 10kjkj, m = 10k -1, b = 59k -7 and a = 11j -7. If k and j are two integers bigger than 1 and such that d > max(a, b) m > 0 and gcd(a, b) = 1, then Irr( <a,b> d ) = I. So :

  11, 59} Now, we consider I = {10, 17, 24}, enumerated by the modular-convex sequence (10, 17, 24) ( d 1 = 2). We denote k = d 2 and j = d 0 . Then d = 2kjkj, m = 2k -1, b = 24k -17 and a = 10j -17. If k and j are two integers bigger than 1 and such that d > max(a, b) m > 0 and gcd(a, b) = 1, then Irr( <a,b> d ) = I. So :

  usual and ceiling continued fraction expansions. ( ∞-tails are not mentioned) (i) r and ρ are related by the following formula :

  19 let N ∈ {1, .., q -1} and (N 1 , N 2 , • • • , N s ) its α-numeration of N , with N s > 0. Let β ∈ {{nα}, n ∈ N}, and (b 1 , b 2 , • • • , b s ′ ) its α-numeration, with b s ′ > 0. We suppose β = 0. The minimal points in R 2 of the set {({nα}, n) such that , 1 n N and {nα} β} are : ◮ Case 1 : if b 1 2 or b 2 = 0, that is to say α β, these are the same as in former Lemma ! ◮ Case 2 : else ( b 1 = 1 and b 2 > 0).

  E α ) : ∀i ∈ {1, .., t -1}, b 2i = 0 ; b 2i-1 = a 2i-1 Now, we need the α-numeration, say ν, of n 1 , the least integer n such that {nα} β. If α β then n 1 = 1. Else, with Proposition 9, ν is the minimum of elements d = (d 1 , • • • , d r ) of E α for RLO, such that d A b, where b = (b k ) k∈{1,..,r} and A means for ALO. We claim that ν = (b 1 , b 2 , • • • , b 2t-1 ). Indeed, the condition d A b implies that : ∀i ∈ {1, .., t -1}, d 2i = 0 = b 2i ; d 2i-1 = a 2i-1 = b 2i-1 and d 2t-1 b 2t-1

  we use values of n of Lemma 18 : we obtain first part of our result ( that involves the (ai )), for b 2t-1 > 0 : indeed b 2t > 0 and b 2t-2 = 0. Now, if n n 1 , let denote d = (d 1 , • • • , d r ) 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). So,d must verify (b 1 , • • • , b s ) A d < A (b 1 , • • • , b 2t-1 ). It gives the successive values of d : (b 1 , • • • , b 2t-1 , j) as j ∈ {0, .., b 2t -1}. Later, if b 2t+2 = 0, the first ( for RLO) d that verify d A b and that is lower ( for ALO) than (b 1 , b 2 , • • • , b 2t-1 , b 2t -1) is (b 1 , b 2 , • • • , b 2t-1 , b 2t , b 2t+1 ).Then, we have (b 1 , b 2 , • • • , b 2t-1 , b 2t , b 2t+1 , j) with j taking successive values of {1, .., b 2t+2 -1}...and so on.

5

  Invariants of <a,b> d Let a and b be two coprime positive integers. We want to study the invariants of <a,b> d . We remind that we can suppose, without loss of generality, that a, b, d are pairwise coprime. In addition, we can also suppose that d ∈< a, b >, because <a,b> d = N if d ∈< a, b >.

2 .

 2 So : y a < k x b and we deduce x b = y a . -we suppose that x b = y a . We have n ab = x b -y a and n is positive, so, there exists an integer k such that : y a < k x b . Now, we denote i = xkb and j = kay. Then, i ∈ N, j ∈ N * and n = axby = ai + bj. So, n ∈< a, b >. Now, suppose that n ∈ a{0, .., b-1}. Then we can use our first argument with j = 0 and i ∈ {0, .., b-1}.We obtain : it exists an integer k such that :xi = kb and y = kaSo, y a = k = y a . But x b = k + i b ∈ [k, k + 1[, so x b = y a : contradiction.Theorem 4 let a, b, d be three pairwise coprime positive integers such that d ∈< a, b > and d We can find α ′ ∈ 1 b Z and α ∈ 1 a Z such that α ′α = d ab . Then : m < a, b > d = the denominator of the reduced best rational in [α, α ′ ]

Theorem 5

 5 let a, b, d be three pairwise coprime positive integers such that d ∈< a, b >. Let m ∈ {1, .., d -1} such that am + b = 0[d]. Let α = m/d and [0, a 1 , • • • , a r , 1] its CFE.

2 ◮◮

 2 Case 3 : a < b < d and m < x 0 + b d. Same results as in Case 2, except that a ∈ Irr <a,b> d and so e <a,b> d Case 4 : a < b < d and x 0 + b m. We denote β = x 0 +b-1 d and (b 1 , b

⌋ k=t+1 a= 3 ⇔ 1 . 1 . 3 .Remark 1 :

 k=t+131131 2k + ν Remark : the hypothesis of Case 4 is equivalent to β < α, that is to say b 1 = 1 and b 2 > 0. • What are the extremal possible values of e <a,b> d and when does it happen ? Proposition 12 ( Extremal cases) We keep the notations of previous theorem. ◮ Case 1 : if d < a < b, then : d/(a + b). In that case, Irr <a,b> d = {a, b, a+b d }. ⊲ e <a,b> d = d + 1 ⇔ d/(ba). In that case, Irr <a,b> d = a + n(b-a) d , n ∈ {0, .., d} . ◮ Case 2 : if a < d < b or (a < b < d and x 0 + b > d) , then : In that case, Irr <a,b> d = {a, τ }. ⊲ e <a,b> d = a ⇔ m d > 1 -1 a-1 . In that case, Irr <a,b> d = {a + n(τa), n ∈ {0, .., a -1}}. ◮ Case 3 : if a < b < d and m < x 0 + b d, then : In that case, Irr <a,b> d = {a + n(τa), n ∈ {1, .., a -1}}. ◮ Case 4 : if a < b < d and x 0 + b m, then : In that case, Irr <a,b> d = {a + n(τa), n ∈ {2, .., a -1}}. for all of these cases, Irr <a,b> d has elements in arithmetic progression, with expression a + n(τa), but the range of n is different for each fo these cases. Remark 2 : if a < d < b and d divides a+b, then m = 1, so m d < 1 a-1 and Irr <a,b> d = {a, τ }, this is consistent with respect to Case 1. Similarly, if a < d < b and d divides ba, then m = d -1, so m d > 1 -1 a-1 and e is maximal, as in Case 1.

  d and m are coprime, so e <a,b> d = 3 is equivalent to m = 1[d], that is to say a + b = 0[d]. In that case, we have 3 minimal generators of <a,b> d : a, b and τ .

1 d

 1 (a(dn) + bn) where n ∈ {1, .., d -1}. ◮ Case 2 : if a < d < b or (a < b < d and x 0 + b > d), again, with Theorem 5 and Proposition 2, we obtain both inequalities.

◮ Case 3 :

 3 if a < b < d and m < x 0 + b d... see Theorem 5 and Case 2.

Theorem 6 (

 6 Easy cases) . let a, b, d be 3 pairwise coprime positive integers such that d ∈< a, b > and a < b. ◮ Case 1 : if (a -1)(b -1) = 1[d], then <a,b> d is symmetric ( its type is one) and :

•Theorem 7 (b i q i- 1 .b i q i- 1 +

 711 d . Remark : Case 1 is not compatible with Case 2 or Case 3. But we can have a = b = 1[d] : in that case, we have d < min(a, b) and b-a = 0[d], so Irr(< a, b > /d) = a + n(b-a) d , n ∈ {0, .., d} . We obtain, if we denote f = abab : nb -(d -1n)a], n ∈ {0, .., d -1} Proof : we will denote S ′ = <a,b> d and, as in Lemma 7 : ψ Z 2 → (1/d)Z (x, y) → ax+by d and :L = {(x, y) ∈ Z 2 , ax + by = 0[d]} ; R = {bd, .., b -1} × {-d, .., -1} ◮ Case 1 : if (a -1)(b -1) = 1[d], then (b -1, -1) is an element of L. So, it is the maximum of L ∩ R.We conclude that <a,b> d has only one PF-number, which isψ(b -1, -1)... ◮ Case 2 : if a = 1[d], then (b, -1) is in L, but not in R. Let us consider σ : (x, y) → (bx, -1y), that maps L ∩ R onto L ∩ R ′ , where R ′ = {1, .., d} × {0, .., d -1}. So, max(L ∩ R) = σ(min(L ∩ R ′ )). But L ∩ R ′ = (L ∩ R")\{(0, d)}, if we denote R" = {0, .., d} 2 \{(0, 0)}. This implies that min(L ∩ R ′ ) = min(L ∩ R")\{(0, d)}, for (0, d) is a minimal point of L ∩ R". In addition, d < a < b, so Irr(S ′ ) = ψ(min(L ∩ R")) = ψ(min(L ∩ R")) ∪ {b} ( seeProposition 2). Now, we obtain, with Lemma 7 :PF(S ′ ) = ψ(max(L ∩ R)) = abb d -(Irr(S ′ )\{b}) ◮ Case 3 : if b = 1[d], then (b -1, 0) is in L, but not in R. Let us consider σ ′ : (x, y) → (b -1x, -y). We have d < b. If d < a, we argue as in Case 2. Else : PF(S ′ ) = ψ(max(L ∩ A)), where A = {bd, .., b -1} × {-(a -1), .., -1} ( see Proposition 3). Yet, σ ′ (L ∩ A) = L ∩ A ′ , where A ′ = {0, .., d -1} × {1, .., a -1}. But, Irr(S ′ ) = ψ(min(L ∩ A ′ 2 )), where A ′ 2 = {1, .., d} × {0, .., a -1} ( see Proposition 2). Now (d, 0) is a minimal point of L ∩ A ′ 2 and there is no point in L ∩ A ′ with x = 0, so : min(L ∩ A ′ ) = min(L ∩ A ′2 )\{(d, 0)} and we conclude as above... In the previous proof, we have used the half-turnu → vu in Z 2 , with v = (b, -1) or v = (b -1, 0). Now,we will use it with v = (b -1, -1). The case d < min(a, b) ) . let a, b, d be three pairwise coprime positive integers, such that d < min(a, b) and d does not divide abab. Let m ∈ {1, .., d -1} such that am + b = 0[d]. We denote α = m d , [0, a 1 , a 2 , • • • , a r , 1] its CFE and (p k /q k ) k its convergents. We denote τ = am+b d , β = 1 -{ b-1+m d } and (b 1 , b 2 , • • • , b r ) the α-numeration of β.We denote B = {i ∈ {1, .., ⌊r/2⌋}, b 2i = 0} , µ i = τ q iap i for all i ∈ {0, .., r} and :f = abab = f (< a, b >) ; f 1 = f d a(1β) ; f 2 = d = {f 1 , f 2 } ∪ f d + aβjµ 2k-1 -2k-1 i=1 b i µ i-1 , j ∈ {0, .., b 2k -1}, k ∈ if d does not divide fand d < a < b, then the type of <a,b> d is at least equal to 2, so <a,b> d is not symmetric. Proof : let S ′ = <a,b> d . We use Lemma 7 ( or Proposition 3) : PF(S ′ ) = ψ(max(R ∩ L))where ψ :Z 2 → 1 d Z (x, y) → ax+by d ; L = ψ -1 (Z) and R = {bd, .., b -1} × {-d, .., -1}. But, we can describe R ∩ L with the finite sequence (b -1g(n), -n -1) n∈{0,..,d-1} , where g(n) is the integer of {0, .., d -1} such that a(b -1g(n))b(n + 1) = 0[d]. We obtain : ∀n ∈ {0, .., d -1}, a(b -1g(n))b(n + 1) = 0[d] ⇔ ag(n) = a(b -1 + m + mn)[d] ⇔ g(n) = b -1 + m + mn[d]Indeed, d and a are coprime. So :∀n ∈ {0, .., d -1}, g(n) = d b -1 + m + mn dWe remark that :g(0) = 0 ⇔ b -1 + m = 0[d] ⇔ a(b -1 + m) = 0[d] ⇔ abab = 0[d] Since f = 0[d], then g(0) = 0 and : max((b -1g(n), -n -1) n∈{0,..,d-1} ) = σ(min((g(n), n) n∈{0,..,d-1} ))Where σ :Z 2 → Z 2 (x, y) → (b -1x, -1y) .We use now Lemma 20 ( and Remark 3 below it), that gives minimal points of ({nα -β}, n) n∈{0,..,d-1} , where α = m d and β = {-b-1+m d } = 1 -{ b-1+m d } ∈]0, 1[, since d does not divide b -1 + m ( see above). For a general n ( corresponding to a minimal point of ({nα-β}, n) n∈{0,..,d-1} ), we obtain the PF-number of S ′ : fbn d -a{nα -β} For n = 0, we have g(0) = d(1β) ( this corresponds to the trivial minimal point (1β, 0)). This gives the PF-number for S ′ : f 1 = f da(1β). For n, whose α-numeration is (b k ) k ( this means that n is the integer in {0, .., d-1}, such that {nα} = β), we obtain {nα -β} = 0 and so this gives the PF-number for S ′ : f 2 = f -nb d , where n = r i=1 For the general case n, whose α-numeration is (b 1 , • • • , b 2k-1 , j), with j ∈ {0, .., b 2k -1} and k ∈ B, we obtain : jq 2k-1a 2k-1 i=1

Theorem 8 (F 2 = a b d + a -jµ 2k- 1 -- 1 i=1 b i µ i- 1 2 t◮

 821112 The case d > min(a, b)) . let a, b, d be 3 pairwise coprime integers, such that 1 < min(a, b) < d and d does not divide abab.Let m ∈ {1, .., d -1} such that am+ b = 0[d]. We denote α = m d , [0, a 1 , a 2 , • • • , a r , 1] its CFE and (p k /q k ) k its convergents. We denote τ = am+b d ( a positive integer), β = {aα} = 1-b d , (b 1 , b 2 , • • • , b s ) the α-numeration of β,where b s > 0 and µ i = τ q iap i for all i ∈ {0, .., r}.We also denote B = {i ∈ {1, .., ⌊s/2⌋}, b 2i = 0} and k 0 = (s + 1)/2 if B = ∅ min(B) else ( s is odd in the first case). Last notations :F 0 = a b d τ if α < β ; F 0 = ∅ else F 1 = a b d µ 2k-2jµ 2k-1 , j ∈ {1, .., a 2k }, k ∈ {1, .., k 0 -1} 2k, j ∈ {0, .., b 2k -1}, k ∈ B ◮ Case 1 : if a < d < b PF < a, b > d = F 0 ⊔ F 1 ⊔ F Case 2 : if d > max(a, b) PF < a, b > d = F 2 ; t < a, b > d = ⌊s/2⌋ k=k 0 b 2k

7 and 8 . 1 i=1b-µ 2k- 2 -b

 812 We denote B = {i ∈ {1, .., ⌊r/2⌋}, b 2i = 0} and obtain :◮ if d < min(a, b) f < a, b > d = max f 1 , f 2 , f d + aβjµ 2k-1 -2ki µ i-1 , j = 0, j = b 2k -1, k ∈ B ◮ if a < d jµ 2k-1 , j = 1, j = a 2k , k ∈ {1, .., k 0 -1}, , a b d + ajµ 2k-1 -2k-1 i=1 b i µ i-1 , j = 0, j = b 2k -1, k ∈ B) ◮ if d > max(a, b) : i µ i-1 , j = 0, j = b 2k -1, k ∈ B

Theorem 9 1 i=1 b i µ i- 1 ,2k 2 - 1 i=1 b i µ i- 1 ◮ 1 i=1 b i µ i- 1 ,2k 2 - 1 i=1 b i µ i- 1 - 1 i=1 b i µ i- 1 ◮ 1 i=1 b i µ i- 1 ,2k 2 - 1 i=1 b i µ i- 1

 911211112111111211 let a, b, d be three pairwise coprime integers. Let m ∈ {1, .., d -1} such that am+ b = 0[d]. We denote α = m d , [0, a 1 , a 2 , • • • , a r , 1] its CFE and (p k /q k ) k its convergents. We denote τ = am+b d , µ i = τ q iap i for i ∈ {-1, .., r} , f = f (< a, b >) = abab. A -= {i, b 2i = 0 and µ 2i-1 < 0} ; A + = {i, b 2i = 0 and µ 2i-1 > 0} k 1 = max(A -) ; k 2 = min(A + ) ◮ Case 1 : if d divides f then f <a,b> d = f d . ◮ Case 2 : if d < min(a, b), then we denote β = 1 -b+m-1 d = (b 1 , • • • , b r ) α . if A -= ∅ , f < aaβmin -µ 2k 1 -1 + 2k Case 3 : if a < d < b, we denote 1 -b d = (b 1 , • • • , b r ) α . γ = min (i ∈ {1, .., ⌊(r + 1)/2⌋}, +µ 2i-1 > 0) ; k 0 = k 0 = ⌊r/2⌋ if b 2i = 0 for all integer i min(i, b 2i = 0) else if γ < k 0 min -µ 2k 1 -1 + 2k if γ = k 0 , f < a, b > d = a b d min µ 2k 0 -2 , -a + 2k 0 Case 4 : if d > max(a, b), , we denote 1 -b d = (b 1 , • • • , b r ) α . Then : else , f < a, b > d = a b d + amin -µ 2k 1 -1 + 2k

  ∈ N\(a{0, .., b -1}), ⌊kα⌋ = ⌊kα ′ ⌋}

  ( d 1 = 6) and (11, 7, 59) ( d 1 = 10),

	so we have :	Irr(	< 7, 59 > 6	) = Irr(	< 11, 59 > 10	) = {7, 11, 59}

  • • • ; (1, a 2 , 0, • • • , a 2⌊s/2⌋-2 , 0, j), j ∈ {1, .., µ} where µ = N s if s is even, µ = a s-1 if s is odd.we can sum up this with : (1) and (d k ) k∈{1,..,r} , such that d 1 = 1 and :∀i ∈ {1, .., k -1}, d 2i = a 2i , d 2i+1 = 0 , d 2k ∈ {1, .., a ′ 2k }, ∀i > 2k, d i = 0, k ∈ {1, .., ⌊s/2⌋}where a ′ 2k = a 2k if 2k < s, and a ′ s = N s .

except when S = N, where G(S) = ∅ and PF(S) = {-1}

4.4 minimal points of ({nα -β}, n) n

In this subsection, we prove several Lemma about minimal points of this sequence, in different cases, from the simplest to the more intricate. These results will be useful, when we will study in section 5, Irr and PF of <a,b> d , since points of L in a rectangle of vertice d can be parametrized by such sequences ( see 2.2).

• First, we study minimal points in R 2 , with the product order, of the sequence ({nα}, n) 1 n N , where N is a positive integer. With Proposition 10, we can affirm that these points have the property that if n = Ψ α (d), then for any other d ′ ∈ E α , we have d < d ′ for ALO or for RLO ! The following Lemma gives the result for the particular case N = q -1, where q is the denominator of the reduced fraction of α. We denote, as usual, [a 0 , a 1 , • • • , a r , 1] the CFE of α.

Lemma 17 the minimal points in R 2 of the set {({nα}, n), 1 n q -1} are for the following integers n, given by three equivalent formulations : (i) with the α-numeration of n ( the 0-tail is not written) :

(1) ; (1, j), j ∈ {1, .., a 2 } ; (1, a 2 , 0, j), j ∈ {1, .., a 4 }; • • • ; (1, a 2 , 0, • • • , 0, j), j ∈ {1, .., a 2⌊r/2⌋ } we can sum up this with : (1) and sequences (d k ) k∈{1,..,r} such that d 1 = 1 and : ∀i ∈ {1, .., k -1}, d 2i = a 2i , d 2i+1 = 0, d 2k ∈ {1, .., a 2k }, ∀i > 2k, d i = 0, k ∈ {1, .., ⌊r/2⌋} (ii) with denominators of convergents of α : q 0 ; q 2k-2 + jq 2k-1 , j ∈ {1, .., a 2k }, k ∈ {1, .., ⌊r/2⌋} (iii) with diophantine approximation : these are the denominators of the reduced semiconvergents of α, that are lower than α.

Proof :

-let us verify that these points are minimal : for [START_REF] Adeniran | on the genus of a quotient of a numerical semigroup[END_REF], it is obvious. We denote A p = (a 2 , 0, a 4 , 0, • • • , a 2p-2 , 0), for any positive integer p ( with A 1 = (), the empty sequence).

Let d = (1, A p , j) for j ∈ {1, .., a 2p } and p r/2. If d ′ < d for ALO and d ′ = 0, then d ′ = (1, A p , j ′ ) with j ′ > j, or d ′ = (1, A p , j, 0, k), with k ∈ {1, .., a 2p+2 }. In both cases, we have d ′ > d for RLO.

-now, let us verify that no other point is minimal : if d ′ is not among these α-numeration of integers n, then let k be the least integer such that d ′ k is different from all the d k of (i). Then, we claim that k is odd. Indeed, if k were even, we would have d ′ = (1, A p , d ′ k , ...), with k = 2p + 2 and d ′ k = 0. So d ′ = (1, A p ), according to our definition of α-admissible sequences, but this is in the list (i).

So, k is odd and if we denote d = (1, A p , d k-1 ), with k = 2p + 1, then d < d ′ for ALO and RLO.

-(ii) and (iii) are direct consequences of (i)

Remark : if t > ⌊s/2⌋, then there is no minimal element, so the set is empty : there is no integer n such that n ∈ {1, .., N } and {nα} β.

Proof :

Let denote E = {({nα}, n), n ∈ {1, .., N }} and E ′ = {({nα}, n) ∈ E, {nα} β}. We claim that :

Indeed, The second subset is obviously included in the first one and no element of E\E ′ is lower than any element of E ′ .

So, we just have to select among minimal elements ({nα}, n) of E, whose α-numeration, say d, is given by former Lemma, those that verify : {nα} β, that is to say

where k ∈ {1, .., ⌊s/2⌋}, with a ′ 2k = a 2k if 2k < s, and

◮◮ subcase 2 : suppose that b 2i+1 = 0 for all i > 0. Then, s ′ can not be odd, so :

The same arguments as above prove that a minimal element of former Lemma is in E ′ if and only if d i = b i for all i < s ′ and d s ′ b s ′ . The formula still rules.

• Now, we will need another generalization : we study the minimal points in R 2 , with the product order, of the sequence ({nα -β}, n) n 0 n<q , where n 0 = 0 or 1, q is a positive integer and α = p q , β = p ′ q , with p, p ′ ∈ {1, .., q -1} and p, q coprime. First, we remark that :

If the sequence begins with the index i at 0, the point (1β, 0) obtained for n = 0 is obviously a minimal point of the sequence. So, the other minimal points ({nα}, n) must verify {nα} β. We have the same situation if the sequence begins at i = 1 and if α β.

If the sequence begins at i = 1 and if α < β, then the " first" minimal points will be such that {nα} < β and the following such that {nα} β. So, the lowest integer n such that {nα} β is important.

The case α = β is obvious ( only one or two minimal points for n = 0 and n = 1).

number of integers k such that {kα} β and k ν

We consider two rationals α = p q and β = m q in [0, 1[ and a positive integer ν, such that : gcd(p, q) = 1 ; 0 < m < q ; 0 < ν < q

We denote n = (n k ) k and b = (b k ) k 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 4.3).

We also denote :

C(α, β, ν) = #{k ∈ {0, .., ν}, {kα} β}

We will denote [a 0 , a 1 , • • • , a r , 1] the CFE of α ( with a 0 = 0).

We also use the following notations :

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.

where :

Proof :

as in section 2, we denote S ′ = <a,b> d and ψ :

We can describe ({1, .., d -1}) 2 ∩ L with the finite sequence (d{nα}, n) n∈{1,..,d-1} . Indeed : For all ∀n ∈ {1, .. In addition, each d × d square in L contains a unique point on each line and on each row... Now, let us prove that, if a < d, then : x 0 = min{x(u), u ∈ L ∩ (N × {1, .., a -1})}, in order to use Proposition 2. First, we can replace, in this formula, N by {0, .., d -1}, for L is (d, 0)-invariant. We have seen above that L ∩ ({0, .., d

., a -1}). Using our α-numeration and Lemma 18, we obtain that this minimum is obtained for the following value of n :

This implies that x 0 = x ′ 0 and our formula...

◮ Case 1 : with Proposition 2 :

But, with remarks at the beginning of this proof and Lemma 17, we have min(({1, .., d -1}) 2 ∩ L)) enumerated by (d{α}, 1) and the (d{nα}, n) with :

We obtain ( see Proposition 10 and formulae around) :

But ψ is into on ({1, .., d -1}) 2 since d < a < b, so we deduce the formula for e <a,b> d . Moreover, we have ψ(d{α}, 1) = a{α} + b d = τ and ∀k ∈ {1, .., r}, j ∈ {1, .., a 2k } :

◮ Case 2 : if a < d < b, the arguments are essentially the same as in Case 1. The only difference is a limitation on the value of n : with Proposition 2, we have n ∈ {1, .., a -1} instead of n ∈ {1, .., d -1}.

With Lemma 18, we obtain the result. If a < b < d and x 0 + b > d : with Proposition 2 and its notations, we have x 1 = d and a ∈ Irr(S ′ ). In addition :

for a is obtained with the point (d, 0) in L. So, the results are the same as in the case a < d < b.

But ({1, .., x 0 + b -1} × {1, .., a -1}) ∩ L is enumerated by the (d{nα}, n), such that {nα} β and n a -1. Our hypothesis m < x 0 + b means that α β, so the point (d{α}, 1) is in ({1, .., x 0 + b -1} × {1, .., a -1}) ∩ L. We deduce that the condition "{nα} β" is dispensable for the minimal points of ({1, .., x 0 +b-1}×{1, .., a-1})∩L. Thus, we are in the same condition as in previous Case, except for a...

Proof :

We suppose that a < b, so a < d. This proof will be similar to the proof of Theorem 7. We mention the notations used in this one : S ′ = <a,b> d and with Proposition 3 :

The difference with the proof of Theorem 7 lies in R and in the parametrization of R∩L : we will use the sequence

Yet a < d and (b, -a) is a point of L, so there is no point of L among the (b, -n) n∈{1,..,a-1} . Hence,

.,a-1} by the map σ : (x, y) → (bx, -y) and :

we distinguish two kinds of minimal point of ({nα -β}, n) n∈{1,..,a-1} :

-those that satisfy {nα} < β, which corresponds to ( see Proof of Theorem 7) :

For these minimal points, we have {nα -β} = {nα} + 1β = {nα} + b d -⌊b/d⌋. We deduce the formula for the elements of F 1 .

-those that satisfy {nα} β, which corresponds to :

For these minimal points, we have {nα -β} = {nα}β = {nα} + b d -⌊b/d⌋ -1. We deduce the formula for the elements of F 2 .

Now, if we want to conclude for PF-numbers of S ′ , we just have to remark that Lemma 20 also gives a minimal point of U for n = 1, which is (d{α -β}, 1). If α > β, that point is in F 2 and already counted. Else, it gives a new PF-number : a⌊b/d⌋τ .

For the type, we just have to count elements of PF(S ′ ), keeping in mind that the sets F 0 , F 1 , F 2 are pairwise disjoints and that the parametrization of their elements is injective. ◮ Case 2 : if d > max(a, b). We keep above arguments with the additional condition that h(n) < b : this gives the condition {nα -β} < 1β, that is {nα} β. We conclude with Lemma 20.

Proof :

◮ Case 1 : has already been shown at Theorem 6.

◮ Case 2 : we use and refer to Theorem 7. We remind the result of this Theorem : if we denote

◮◮ subcase 1 : if A -= ∅, then µ 2k-1 > 0 for all k in B, with notations of Theorem 7. So, the Frobenius is obtained for the "first" pseudo-Frobenius in the list, namely f 1 . ◮◮ subcase 2 : if A + = ∅, then µ 2k-1 < 0 for all k in B, with notations of Theorem 7. So, the Frobenius is obtained for the "last" pseudo-Frobenius in the list, namely f 2 . ◮◮ subcase 3 : if both A -and A + are non empty, then the Frobenius is obtained for one of the two following pseudo-Frobenius, listed in Theorem 7 :

f -being the greater of PF-numbers parametrized by k such that µ 2k-1 < 0 ( k = k 1 and j = b 2k-1 -1) and f + being the greater of PF-number parametrized by k such that µ 2k-1 > 0 ( k = k 2 and j = 0). Our formula is a direct consequence.

◮ Case 3 : we use and refer to Theorem 8. We remind the principle notations and result in that case :

◮◮ subcase 1 : if γ < k 0 , then the Frobenius of S is among the elements of F 1 , for µ 2k-1 > 0 for k k 0 -1. It is obtained for one of the following pseudo-Frobenius listed in F 1 :

f -being the greater of PF-numbers parametrized by k such that µ 2k-1 < 0 ( k = γ -1 and j = a 2γ-2 ) and f + being the greater of PF-number parametrized by k such that µ 2k-1 > 0 ( k = γ and j = 0). But, f + = f -and we deduce our formula. ◮◮ subcase 2 : if γ > k 0 , then the Frobenius of S is among the elements of F 2 , becasue µ 2k-1 < 0 for k = k 0 . Now, the arguments are the same as in Case 1 subcase 3... ◮◮ subcase 3 : if γ = k 0 , then µ 2k0-3 < 0 and µ 2k0-1 > 0. So, the Frobenius of S is one of the following integers :

f -being the greater of PF-numbers parametrized by k such that µ 2k-1 < 0 ( k = k 0 -1 and j = a 2k0-2 ) and f + being the greater of PF-number parametrized by k such that µ 2k-1 > 0 ( k = k 0 and j = 0). ◮ Case 4 : the arguments are the same as in Case 3 subcase 2, for we only consider F 2 ... In particular, we obtain :

genus

Proof :

According to Proposition 1, we have to count points in R ∩ L, where :

, ax + by = 0 mod m} But, we know that L contains exactly one point one every " horizontal" or " vertical" segment of length d. So, if we denote N = #(R ∩ L), we have : Remark 1 : that expression of g is not symmetric in terms of a and b, even if the product βν is. But it proves that :

where Hence, the term C(α, β, ν) -1βν can be interpreted as a "signed deviation from the random mean value"... Remark 3 : this expression of g and especially that of f is too intricate to help us about Wilf's property...

comparison of t and e, Wilf's property

• We have already mentionned that minimal generators and pseudo-Frobenius numbers of a numerical semigroup S have similar properties : they are respectively minimal and maximal sets of S\{0} and Z\S for the order induced by S. That kind of symmetry could imply some relation between their finite cardinality. Unfortunately, this is not the case : we have t(S) < e(S), if e(S) 3, but for e(S) 4, t(S) can be as large as we want ( [7] References). Nonetheless, we know that t(S) < m(S), considering rests modulo m(S). So, this is remarkable that t(S) < e(S) when S is a proportionally modular semigroup, that is to say S = <a,b> d , for some three pairwise coprime integers a, b, d :

Theorem 11 if a, b, d are 3 pairwise coprime positive integers such that d ∈< a, b >, then :

So, Wilf's property holds for these numerical semigroups ! Remark : before presenting a proof, we want to underline that, depending on the respective positions of a, b, d, this proof will be either obvious or laborious ( never difficult nonetheless).

We are however convinced that this inequality, between e and t, could be deduced from a deeper result about minimal points in a lattice of Z 2 . This will be perhaps the subject of a next article... To make this 3-pages proof readable, here is a summary : since we use Theorem 5, 6, 7 and 8, we must distinguish several cases. ◮ Case 3 : if a < d < b, the proof is more technical and we will study two subcases depending on α-numeration of a -1 and a : a general subcase, where these numerations have the same length and an exceptional subcase. But, we keep some room to manoeuvre.

◮ Case 4,5,6 : if d > max(a, b). Proofs are becoming longer, more intricate and we show that some exceptional subcases are impossible. Case 6 fills almost half of the proof...

Proof :

We denote S = <a,b> d . We will use some previous Theorems and their notations, as well as our αnumeration. We refer the reader to the statements of these theorems and to section 4.3. ◮ Case 1 : we suppose that we are in one of the three " easy cases" of Theorem 6 : if d divides abab, then t(S) = 1 and e(S) 2. If, d divides a -1 or b -1, then Theorem 6 proves that t(S) = e(S) -1.

◮ Case 2 : we suppose that d < min(a, b).

With Theorems 5 and 7, we obtain :

But, ∀k ∈ {1, .., ⌊r/2⌋}, b 2k a 2k , so the inequality is true. We notice, that e(S) = t(S) + 1 if and only if : ∀k ∈ {1, .., ⌊r/2⌋}, b 2k = a 2k .

◮ Case 3 : we suppose that a < d < b.

We use Theorems 5 and 8 with the common notations α, (a k ) k , k 0 . We also denote (b k ) k , the αnumeration of a, (N k ) k the α-numeration of a -1 and s = max(i, N i = 0). ◮◮ Subcase 1 : if b k = 0 for all k > s. where c s+1 = 1 if s is odd and c s+1 = 0 else. We make a distinction according to the parity of s : ◮◮◮ if s is even : then b 2k = 0 for all k, c s+1 = 0 and ν = N s = a s , so e(S)t(S) 2. ◮◮◮ if s is odd : then b 2k = a 2k for all 2k < s, c s+1 = 1 and ν = 0. In addition, α > β, for b 1 = 1 and b 2 > 0 ( we remark that if s = 1, then b 2 = 1). So e(S)t(S) = 1.

We use again Theorem 5 and 8 with their notations. For the notation (b k ) k , we will use it for the α-numeration of a ( that is also the α-numeration of 1 -b d ). Moreover s = max(i, N i > 0). Where c s = b s if s is even and 0 else. We remark that if k 0 > 1, then we can easily conclude, thanks to the term a 2 1 and the Case 4.

t(S) =

If s is odd, then ν = 0 = c s and e(S)t(S) 1.

If s is even : if b s = N s , we also have e(S)t(S) 1. If b s = N s + 1, then b 2k = a 2k and b 2k+1 = 0 for all k < s/2, except b 1 = 1. We will show that this is not possible. Indeed, we have ( see 4.3 ) :

which contradicts our hypothesis. ◮◮ Subcase 2 : again we refer to Case 3 Subcase 2. If s is even, then with same arguments, e(S)-t(S) 1.

If s is odd, we will show that it is not possible : indeed, we would have

Again, we use Theorem 5 and 8. Since some common notations name different things in each theorem, we will precise this : we use k 1 instead of t in Theorem 5 and we do not use s in Theorem 8, since it names s = max(i,

We mention that, since (b k ) k is the successor of (N k ) k for ALO in E α , then σ = s in the general case or σ = s + 1 in one exceptional case ( see Case 3 subcase 2). We have with Theorems 5 and 8 :

We underline the definitions of k 0 and k 1 : Step 1 : we will prove that k 0 > k 1 . First, we remark that b ′ 2i+1 = 0 if i ∈ {1, .., k 1 -1} and b ′ 2i = a 2i if i < k 1 . In addition, b ′ 2k1 > 0 if k 1 > 1. Indeed : if b ′ 2i+1 for all i > 0, then 2k 1 = s ′ . Else, b ′ 2k1+1 > 0 and b ′ 2k1-1 = 0. Yet : (b ′ k ) k = (1, a 2 , 0, a 4 , 0, • • • , 0, a 2k1-2 , 0, b ′ 2k1 , ...) and so :

Then :

But, this inequality is also true if k 1 = 1, since δ 0 = α ( see N.B. above).

On the other hand, using similar arguments for (b k ) k , we obtain : Now, (δ i ) i is non increasing, so k 0 > k 1 .

Step 2 : ◮◮ Subcase 1 : if b k = 0 for all k > s. That is to say, if σ = s. where c s+1 = 1 if s is odd and c s+1 = 0 else. If, s is even, then νc s+1 = N s > 0, so e(S)t(S) 1. If s is odd, this is not possible ( see Case 5, subcase 2).