INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A14

ON THE FROBENIUS NUMBER OF FIBONACCI NUMERICAL SEMIGROUPS

J.M. Marín

Dept. Matemática Aplicada I. Universidad deSevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain

                               jmarin@us.es

J. L. Ramírez Alfonsín

Combinatoire et Optimisation, UniversitéPierre et Marie Curie (Paris 6), France

                          ramirez@math.jussieu.fr

M.P. Revuelta

Dept. Matemática Aplicada I. Universidad deSevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain

                               pastora@us.es

Received: 8/29/06, Revised: 3/9/07, Accepted: 3/14/07, Published: 3/26/07

Abstract

In this note we investigate the Frobenius number of Fibonacci numerical semigroups, that is, numerical semigroups generated by a set of Fibonacci numbers.

1. Introduction

Let s_{1}, s_{2}, …, s_{n} be positive integers such that their greatest common divisor is one. Let S =< s_{1}, …, s_{n} > be the numerical semigroup^{1} generated by s_{1}, …, s_{n}. A Fibonacci numerical semigroup is a numerical semigroup generated by a set of Fibonacci numbers F_{i_{1}}, …, F_{i_{r}}, for some integers 3 ≤ i_{1} < ⋯ < i_{r} where gcd(F_{i_{1}}, …, F_{i_{r}}) = 1.

The so-called Frobenius number, denoted by g(s_{1}, …, s_{n}), is defined as the largest integer not belonging to S, that is, the largest integer that is not representable as a nonnegative integer combination of s_{1}, …, s_{n}. It is well known that g(s_{1}, s_{2}) = s_{1}s_{2} − s_{1} − s_{2}. In general, finding g(S) is a difficult problem and so formulas and upper bounds for particular sequences are of interest. For instance, it is known [3] g(S) when S is an arithmetical sequence

g(a, a + d, …, a + kd) = a (⌊\frac{a − 2}{k}⌋) + d(a − 1)  (1)

1Recall that a semigroup (S, ∗) consists of a nonempty set S and an associative binary operation ∗ on S.

If, in addition, there exists an element, which is usually denoted by 0, in S such that a + 0 = 0 + a = a for all a ∈ S, we say that (S, ∗) is a monoid. A numerical semigroup is a submonoid of IN such that the greatest common divisor of its elements is equal to one.

We refer the reader to [2] where a complete account on the Frobenius problem can be found.

In this note, we investigate the value of g(F_{i}, F_{j}, F_{l}) for some triples 3 ≤ i < j < l (we always assume that gcd(F_{i}, F_{j}, F_{l}) = 1; recall that gcd(F_{i}, F_{i+l}) = 1 if i |̸ l).

We first notice that g(F_{i}, F_{i+1}, F_{l}) = g(F_{i}, F_{i+1}) for any integer l ≥ i + 2. Indeed, since F_{l} = F_{i+m} = F_{m}F_{i+1} + F_{m−1}F_{i} is a nonnegative integer combination of F_{i} and F_{i+1} then the semigroups < F_{i}, F_{i+1}, F_{l} > and < F_{i}, F_{i+1} > generate the same set of elements and thus they have the same Frobenius number.

Let us consider then g(F_{i}, F_{i+2}, F_{l}) with l ≥ i + 3. We notice that the case when l = i + 3 is a consequence of equation (1) since the triple {F_{i}, F_{i+2}, F_{i+3}} = {F_{i}, F_{i} + F_{i+1}, F_{i} + 2F_{i+1}} form an arithmetical sequence. However, it can be checked that {F_{i}, F_{i+2}, F_{i+k}} do not form an arithmetical sequence when k ≥ 3 and the calculation of g(F_{i}, F_{i+2}, F_{i+k}) is more complicated.

We state our main result.

Theorem 1. Let i, k ≥ 3 be integers and let r = ⌊\frac{F_{i}−1}{F_{k}}⌋. Then,

g(F_{i}, F_{i+2}, F_{i+k}) = \{ \begin{matrix}(F_{i} − 1)F_{i+2} − F_{i}(rF_{k−2} + 1) & if r = 0 or r ≥ 1 and \\ & F_{k−2}F_{i} < (F_{i} − rF_{k})F_{i+2}, \\ (rF_{k} − 1)F_{i+2} − F_{i}((r − 1)F_{k−2} + 1) & otherwise. \end{matrix}

Let N(a_{1}, …, a_{n}) be the number of positive integers with no representation by a nonnegative integer combination of a_{1}, …, a_{n}. Theorem 1 yields to the following result.

Corollary 2. Let i, k ≥ 3 be integers and let r = ⌊\frac{F_{i}−1}{F_{k}}⌋.Then,

N(F_{i}, F_{i+2}, F_{i+k}) = \frac{(F_{i} − 1)(F_{i+2} − 1) − rF_{k−2}(2F_{i} − F_{k}(1 + r))}{2}·

2. Fibonacci semigroups

In order to prove Theorem 1 we need the following result due to Brauer and Shockley [1].

Lemma 3. Let 1 < a_{1} < ⋯ < a_{n} be integers with gcd(a_{1}, …, a_{n}) = 1. Then,

g(a_{1}, …, a_{n}) = max_{l∈{1,2,...,a_{n}−1}}{t_{l}} − a_{1},

where t_{l} is the smallest positive integer congruent to l modulo a_{1}, that is representable as a nonnegative integer combination of a_{2}, …, a_{n}.

Proof. Let L be a positive integer. If L ≡ 0(mod a_{1}) then L is a nonnegative integer combination of a_{1}. If L ≡ l(mod a_{1}) then L is a nonnegative integer combination of a_{1}, …, a_{n} if and only if L ≥ t_{l}. ⊓ ⊔

Let T^{∗} = {t_{0}^{∗}, …, t_{F_{i}−1}^{∗}} where t_{l}^{∗} is the smallest positive integer congruent to l modulo F_{i}, that is representable as a nonnegative integer combination of F_{i+2} and F_{i+k}. By Lemma 3, it suffices to find t_{l}^{∗} for each l = 0, 1, …, F_{i} − 1. To this end, we consider all nonnegative integer combinations of F_{i+2} and F_{i+k}. We construct the following table, denoted by T_{1}, having as entry t_{x,y} the combination of the form xF_{i+2} + yF_{i+k} with integers x, y ≥ 0, see below.

x\y  0  1  2  ⋯
0  0  F_{i+k}  2F_{i+k}  ⋯
1  F_{i+2}  F_{i+k} + F_{i+2}  2F_{i+k} + F_{i+2}  ⋯
2  2F_{i+2}  F_{i+k} + 2F_{i+2}  2F_{i+k} + 2F_{i+2}  ⋯
3  3F_{i+2}  F_{i+k} + 3F_{i+2}  2F_{i+k} + 3F_{i+2}  ⋯
⋮  ⋮  ⋮  ⋮
F_{k} − 1 (F_{k} − 1)F_{i+2} F_{i+k} + (F_{k} − 1)F_{i+2} 2F_{i+k} + (F_{k} − 1)F_{i+2} ⋯
⋮  ⋮  ⋮  ⋮

We notice that

F_{i+k} = F_{k−2}F_{i+1} + F_{k−1}F_{i+2} = F_{k−2}(F_{i+2} − F_{i}) + F_{k−1}F_{i+2} = F_{i+2}F_{k} − F_{k−2}F_{i}

so, we obtain that

xF_{i+2} + yF_{i+k} = xF_{i+2} + y(F_{i+2}F_{k} − F_{k−2}F_{i}) = (x + yF_{k})F_{i+2} − yF_{k−2}F_{i}.

Thus, T_{1} can also be given by the following table, denoted by T_{2},

x\y  0  1  2  ⋯  r  ⋯
0  0  F_{k}F_{i+2} − F_{k−2}F_{i}  2F_{k}F_{i+2} − 2F_{k−2}F_{i}  ⋯  rF_{k}F_{i+2} − rF_{k−2}F_{i}  ⋯
1  F_{i+2}  (1 + F_{k})F_{i+2} − F_{k−2}F_{i} (1 + 2F_{k})F_{i+2} − 2F_{k−2}F_{i} ⋯ (1 + rF_{k})F_{i+2} − rF_{k−2}F_{i} ⋯
2  2F_{i+2}  (2 + F_{k})F_{i+2} − F_{k−2}F_{i} (2 + 2F_{k})F_{i+2} − 2F_{k−2}F_{i} ⋯ (2 + rF_{k})F_{i+2} − rF_{k−2}F_{i} ⋯
⋮  ⋮  ⋮  ⋮  ⋮
l  lF_{i+2}  (l + F_{k})F_{i+2} − F_{k−2}F_{i} (l + 2F_{k})F_{i+2} − 2F_{k−2}F_{i} ⋯ (l + rF_{k})F_{i+2} − rF_{k−2}F_{i} ⋯
⋮  ⋮  ⋮  ⋮  ⋮
F_{k} − 1 (F_{k} − 1)F_{i+2} (2F_{k} − 1)F_{i+2} − F_{k−2}F_{i} (3F_{k} − 1)F_{i+2} − 2F_{k−2}F_{i}  ⋯
⋮  ⋮  ⋮  ⋮  ⋮

Let S be the set formed by the first F_{k} − 1 entries of columns zero, one, two, and so on, that is, S = {t_{0,0}, t_{1,0}, …, t_{F_{k}−1,0}, t_{0,1}, t_{1,1}, …, t_{F_{k}−1,1}, …, t_{0,r}, t_{1,r}, …, t_{F_{k}−1,r}, …}.

Remark 4.

(a) Let r = ⌊\frac{F_{i}−1}{F_{k}}⌋ and set F_{i} − 1 = rF_{k} + l for some integer 0 ≤ l ≤ F_{k} − 1. Let

S′ = {t_{0,0}, t_{1,0}, …, t_{F_{k}−1,0}, t_{0,1}, t_{1,1}, …, t_{F_{k}−1,1}, …, t_{2,r}, t_{1,r}, …, t_{l,r}},

Then, for each t_{x,y} = (x + yF_{k})F_{i+2} − yF_{k−2}F_{i} ∈ S′ we have that 0 ≤ x + yF_{k} ≤ F_{i} − 1. Moreover, since gcd(F_{i+2}, F_{i}) = 1 then S′ forms a complete system of rests modulo F_{i}.

(b) The elements of S can be represented as s_{x} = xF_{i+2} − ⌊\frac{x}{F_{k}} ⌋F_{k−2}F_{i} for x = 0, 1, . . .. Indeed, it can be checked that S = ⋃_{q≥1} S_{q} where

S_{q} = {s_{qF_{k}}, s_{qF_{k}+1}, …, s_{(q+1)F_{k}−1}} = {t_{0,q}, …, t_{F_{k}−1,q}}

for each integer q = 0, 1, 2, . . ..

(c) By using table T_{2} we have that t_{i,j} < t_{k,l} for all i ≤ k and all j ≤ l.

Lemma 5. Let t_{u,v} be an entry of T_{1} such that t_{u,v} ∉ S′. Then, there exists t_{x,y} ∈ S′ such that t_{u,v} ≡ t_{x,y}(mod F_{i}) and t_{u,v} > t_{x,y}.

Proof. We first notice that the set S can be written as follows

\begin{matrix}\{s_{0}, & … & , s_{F_{k}−1}, & s_{F_{k}}, & … & , s_{2F_{k}−1}, & … & , s_{rF_{k}}, & … & , s_{rF_{k}+l} = s_{F_{i}−1}, \\ s_{F_{i}}, & … & , s_{F_{i}+F_{k}−1}, & s_{F_{i}+F_{k}}, & … & , s_{F_{i}+2F_{k}−1}, & … & , s_{F_{i}+rF_{k}}, & … & , s_{2F_{i}−1}, \\ s_{2F_{i}}, & … & , s_{2F_{i}+F_{k}−1}, & s_{2F_{i}+F_{k}}, & … & , s_{2F_{i}+2F_{k}−1}, & … & , s_{2F_{i}+rF_{k}}, & … & , s_{3F_{i}−1}, …\} \end{matrix}

where S′ = {s_{0}, …, s_{F_{k}−1}, s_{F_{k}}, …, s_{2F_{k}−1}, …, s_{rF_{k}}, …, s_{F_{i}−1}}. We have two cases.

Case A. Suppose that t_{u,v} ∈ S \ S′. Then t_{u,v} is of the form s_{pF_{i}+g} for some integers p ≥ 1 and 0 ≤ g ≤ F_{i} − 1. It is clear that,

s_{g} = gF_{i+2} − ⌊\frac{g}{F_{k}} ⌋ F_{i}F_{k−2} ≡ (pF_{i} + g)F_{i+2} − ⌊\frac{pF_{i} + g}{F_{k}} ⌋ F_{i}F_{k−2} = g_{pF_{i}+g}(mod F_{i}.)

We will show that s_{pF_{i}+g} > s_{g}. To this end, it suffices to prove that s_{F_{i}+g} > s_{g} (since s_{pF_{i}+g} ≥ s_{F_{i}+g}). Recall that r = ⌊\frac{F_{i}−1}{F_{k}}⌋ and that F_{i} − 1 = rF_{k} + l for some integer 0 ≤ l ≤ F_{k} − 1. We have two subcases.

Subcase a. If r = 0 then F_{k} ≥ F_{i}. If F_{k} = F_{i} then s_{F_{i}+g} = t_{g,1} and, by Remark 4(c), t_{g,0} < t_{g,1}. If F_{k} > F_{i} then s_{F_{i}+g} = t_{q,0} for some integer q ≥ F_{i} and, by Remark 4(c), t_{g,0} < t_{q,0}.

Subcase b. If r ≥ 1, then s_{F_{i}+g} > s_{g} holds if and only if

(F_{i} + g)F_{i+2} − ⌊\frac{F_{i} + g}{F_{k}} ⌋ F_{i}F_{k−2} > gF_{i+2} − ⌊\frac{g}{F_{k}} ⌋ F_{i}F_{k−2}

or equivalently if and only if

F_{i+2} > F_{k−2} (⌊\frac{F_{i} + g}{F_{k}} ⌋ − ⌊\frac{g}{F_{k}} ⌋) ·

Let g = mF_{k} + n with 0 ≤ n ≤ F_{k} − 1. Since F_{i} − 1 = rF_{k} + l with 0 ≤ l ≤ F_{k} − 1, then

⌊\frac{F_{i} − 1 + g + 1}{F_{k}}⌋ = ⌊\frac{rF_{k} + l + mF_{k} + n + 1}{F_{k}}⌋ ≤ r + m + 1

and thus

⌊\frac{F_{i} + g}{F_{k}} ⌋ − ⌊\frac{g}{F_{k}} ⌋ ≤ r + m + 1 − m = r + 1.

So, it is enough to show that F_{i+2} > (r + 1)F_{k−2} or equivalently to show that F_{i} + F_{i+1} > (r + 1)F_{k−2}. Since F_{i} = rF_{k} + l + 1 then the latter inequality holds if and only if rF_{k} + l + 1 + F_{i+1} > rF_{k−2} + F_{k−2}, that is, if and only if

r(F_{k} − F_{k−2}) + l + 1 + F_{i+1} = r(F_{k−1}) + l + 1 + F_{i+1} > F_{k−2}

which is true since r ≥ 1.

Case B. Suppose that t_{u,v} ∉ S. Then we have that 0 ≤ x ≤ F_{k} − 1 < u. If v ≥ y then, by Remark 4(c), t_{x,y} < t_{x,v} < t_{u,v}. So, we suppose that v < y. Since, t_{u,v} ≡ t_{x,y}(mod F_{i}) then u + vF_{k} ≡ x + yF_{k}(mod F_{i}) but, by Remark 4(a), 0 ≤ x + yF_{k} ≤ F_{i} − 1 so u + vF_{k} = d(x + yF_{k}) for some integer d ≥ 1 and thus u + vF_{k} ≥ x + yF_{k}. Also, since v < y, then −vF_{k−2}F_{i} > −yF_{k−2}F_{i}. So, combining the last two inequalities we have that

t_{u,v} = (u + vF_{k})F_{i+2} − vF_{k−2}F_{i} > (x + yF_{k})F_{i+2} − yF_{k−2}F_{i} = t_{x,y}.
⊓ ⊔

We may now prove Theorem 1.

Proof of Theorem 1. Let T^{∗} = {t_{0}^{∗}, …, t_{F_{i}−1}^{∗}} where t_{l}^{∗} is the smallest positive integer congruent to l modulo F_{i}, that is representable as a nonnegative integer combination of F_{i+2} and F_{i+k}. Let s_{x} = xF_{i+2} − ⌊\frac{x}{F_{k}} ⌋F_{k−2}F_{i} for x = 0, 1, . . .. By Lemma 5, we have that for each x = 0, …, F_{i} − 1, s_{x} is the smallest positive integer congruent to l modulo F_{i}, for some integer 0 ≤ l ≤ F_{i} −1, that is representable as a nonnegative integer combination of F_{i+2} and F_{i+k}, that is, S′ = T^{∗} where S′ = {s_{0}, …, s_{F_{k}−1}, s_{F_{k}}, …, s_{2F_{k}−1}, …, s_{rF_{k}}, …, s_{F_{i}−1}}. Now, by Remark 4(c), if r ≥ 1 then

t_{F_{k}−1,i} = max_{0≤x≤F_{k}−1}{t_{x,i}|t_{x,i} ∈ S′} for each i = 0, …, r − 1,

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A14 6

t_{F_{k}−1,r−1} = max_{0≤i≤r−1}{t_{F_{k}−1,i}|t_{F_{k}−1,i} ∈ S′},

and

t_{l,r} = max_{0≤x≤l}{t_{x,r}|t_{x,r} ∈ S′}.

Thus,

max\{s|s ∈ S′\} = \{ \begin{matrix}t_{l,r} & if r = 0, \\ max\{t_{F_{k}−1,r−1}, t_{l,r}\} & otherwise. \end{matrix}

The result follows since t_{l,r} > t_{F_{k}−1,r−1} if and only if

(rF_{k} + l)F_{i+2} − rF_{k−2}F_{i} = (F_{i} − 1)F_{i+2} − rF_{k−2}F_{i} > (rF_{k} − 1)F_{i+2} − (r − 1)F_{k−2}F_{i} or equivalently, if and only if F_{i+2}(F_{i} − rF_{k}) > F_{k−2}F_{i}. ⊓ ⊔

We will use the following result due to Selmer [4] to show Corollary 2. Lemma 6. Let 1 < a_{1} < ⋯ < a_{n} be integers with gcd(a_{1}, …, a_{n}) = 1. If L = {1, …, a_{1}−1} then N(a_{1}, …, a_{n}) = \frac{1}{a_{1}} ∑_{l∈L} t_{l} − \frac{a_{1} − 1}{2}, where t_{l} is the smallest positive integer congruent to l modulo a_{1}, that is representable as a nonnegative integer combination of a_{2}, …, a_{n}. Proof. The number of M ≡ l ≢ 0(mod a_{1}) with 0 < M < t_{l} is given by ⌊\frac{t_{1}}{a_{1}} ⌋. By assuming that 0 < l < a_{1}, we have ⌊\frac{t_{l}}{a_{1}} ⌋ = \frac{t_{l}−l}{a_{1}}. The result follows by summing over l ∈ L. ⊓ ⊔ Proof of Corollary 2. Let r = ⌊\frac{F_{i}−1}{F_{k}}⌋ and set F_{i} −1 = rF_{k} +l for some integer 0 ≤ l ≤ F_{k} −1. By Lemma 6 and Remark 4(b), we have

N(F_{i}, F_{i+2}, F_{i+k}) = \frac{1}{F_{i}} ∑_{s∈S′} s − \frac{F_{i}−1}{2}

= \frac{1}{F_{i}} ∑_{j=0}^{F_{i}−1}(jF_{i+2} − F_{k−2}⌊\frac{j}{F_{k}} ⌋F_{i}) − \frac{F_{i}−1}{2}

= \frac{1}{F_{i}} (F_{i+2} \frac{(F_{i}−1)F_{i}}{2} ) − \frac{1}{F_{i}} (F_{k−2}F_{i}) ∑_{j=0}^{F_{i}−1} ⌊\frac{j}{F_{k}} ⌋ − \frac{F_{i}−1}{2}.

By using the table T_{1}, it is easy to verify that

∑_{j=0}^{F_{i}−1} ⌊\frac{j}{F_{k}} ⌋ = 0 + F_{k} + 2F_{k} + ⋯ + (r − 1)F_{k} + r(l + 1) = \frac{F_{k}(r − 1)r}{2} + r(l + 1)

and, since l + 1 = F_{i} − rF_{k}, that

N(F_{i}, F_{i+2}, F_{i+k}) = \frac{F_{i+2}(F_{i}−1)}{2} − F_{k−2} (\frac{F_{k}(r−1)r}{2} + r(F_{i} − rF_{k})) − \frac{F_{i}−1}{2}
= \frac{(F_{i}−1)(F_{i+2}−1)}{2} − F_{k−2} (\frac{F_{k}r^{2}−F_{k}r+2F_{i}r−2r^{2}F_{k}}{2} )
= \frac{(F_{i}−1)(F_{i+2}−1)−rF_{k−2}(2F_{i}−F_{k}(1+r))}{2}·
⊓ ⊔

We end with the following problem. Problem. Find upper (and lower) bounds (or formulas) for g(F_{i}, F_{j}, F_{k}) for further triples 3 ≤ i < j < k.

References

[1] A. Brauer and J.E. Shockley, On a problem of Frobenius, Journal für Reine und Angewandte Mathematik 211 (1962), 215-220.

[2] J.L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford Lectures Series in Mathematics and its Applications 30, Oxford University Press, (2005).

[3] J.B. Roberts, Note on linear forms, Proc. Amer. Math. Soc. 7 (1956), 465-469.

[4] E.S. Selmer, On the linear diophantine Problem of Frobenius, Journal für Reine und Angewandte Mathematik 293/294(1) (1977), 1-17.