On the Frobenius Number of Fibonacci Numerical Semigroups

arXiv:math/0606717v1 [math.CO] 28 Jun 2006 On the Frobenius Number of Fibonacci Numerical Semigroups J.M. Mar´ın∗ Dep. Matem´atica Aplicada I Universidad de Sevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain J. L. Ram´ırez Alfons´ın† Equipe Combinatoire et Optimisation, Universit´e Pierre et Marie Curie (Paris 6), Case 189 - 4 Place Jussieu, 75252 Paris, Cedex 05, France and M.P. Revuelta‡ Dep. Matem´atica Aplicada I Universidad de Sevilla. Avda. Reina Mercedes s/n. 41012 Sevilla, Spain September 19, 2018 Abstract In this paper we compute the Frobenius number of certain Fibonacci numerical semigroups, that is, numerical semigroups generated by a set of Fibonacci numbers, in terms of Fibonacci numbers. ∗e-mail: [email protected] †e-mail: [email protected] ‡e-mail: [email protected] 1 1 Introduction Let s1,...,snbe positive integers such that their greatest commun divisor is one. Let S=< s1,...,sn>be the numerical semigroup1gener- ated by s1,...,sn. A Fibonacci numerical semigroup is a numerical semigroup generated by a set of Fibonacci numbers Fi1,...,Fir, for some integers 3≤i1<···< irwhere g.c.d.(Fi1,...,Fir) = 1. The so-called Frobenius number, denoted by g(s1,...,sn), 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 s1,...,sn. It is well known that g(s1, s2) = s1s2−s1−s2. 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] the value of g(S) when Sis an arithmetical sequence g(a, a +d, . . . , a +kd) = aa−2 k+d(a−1) (1) We refer the reader to [2] where a complete account on the Frobenius problem can be found. In this paper, we investigate the value of g(Fi, Fj, Fl) for some triples 3≤i < j < l (we always assume that g.c.d.(Fi, Fj, Fl) = 1, recall that g.c.d.(Fi, Fi+l) = 1 if i6 | l). We first notice that g(Fi, Fi+1, Fl) = g(Fi, Fi+1) for any integer l≥i+ 2. Indeed, since Fl=Fi+m=FmFi+1 +Fm−1Fiis a nonnegative integer combination of Fiand Fi+1 then the semigroups < Fi, Fi+1, Fl>and < Fi, Fi+1 >generate the same set of elements and thus they have the same Frobenius number. 1Recall that a semigroup (S, ∗) consists of a nonempty set Sand an associative binary operation ∗on S. If, in addition, there exists an element, which is usually denoted by 0, in Ssuch that a+ 0 = 0 + a=afor 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. 2 Let us consider then g(Fi, Fi+2, Fl) with l≥i+ 3. We notice that the case when l=i+ 3 is a consequence of equation (1) since the triple {Fi, Fi+2, Fi+3}={Fi, Fi+Fi+1, Fi+ 2Fi+1}form an arithmetical sequence. However, it can be checked that {Fi, Fi+2, Fi+k}do not form an arithmetical sequence when k≥3 and the calculation of g(Fi, Fi+2, Fi+k) is more complicated. We state our main result. Theorem 1.1 Let i, k ≥3be integers and let r=⌊Fi−1 Fk⌋. Then, g(Fi, Fi+2, Fi+k) =          (Fi−1)Fi+2 −Fi(rFk−2+ 1) if r= 0 or r≥1and Fk−2Fi<(Fi−rFk)Fi+2, (rFk−1)Fi+2 −Fi((r−1)Fk−2+ 1) otherwise. Let N(a1,...,an) be the number of positive integers with no representation by a nonnegative integer combination of a1,...,an. We refer the reader to [2, Chapter 5] for results related to N(a1,...,an). Theorem 1.1 yields to the following result. Corollary 1.2 Let i, k ≥3be integers and let r=⌊Fi−1 Fk⌋.Then, N(Fi, Fi+2, Fi+k) = (Fi−1)(Fi+2 −1) −rFk−2(2Fi−Fk(1 + r)) 2· 2 Fibonacci semigroups In order to prove Theorem 1.1 we need the following result due to Brauer and Shockley [1]. Lemma 2.1 Let 1< a1<··· < anbe integers with g.c.d.(a1,...,an) = 1. Then, g(a1,...,an) = max l∈{1,2,...,an−1}{tl} − a1 3 where tlis the smallest positive integer congruent to lmodulo a1, that is representable as a nonnegative integer combination of a2,...,an. Proof. Let Lbe a positive integer. If L≡0 mod a1then Lis a nonnegative integer combination of a1. If L≡lmod a1then Lis a nonnegative integer combination of a1,...,anif and only if L≥tl.⊓⊔ Proof of Theorem 1.1. Let T∗={t∗ 0,...,t∗ Fi−1}where t∗ lbe the smallest positive integer congruent to lmodulo Fi, that is representable as a nonnegative integer combination of Fi+2 and Fi+k. We shall find t∗ lfor each l= 0,1,...,Fi−1. To this end, we consider all nonnegative integer combinations of Fi+2 and Fi+k. We construct the following table, denoted by T1, having as entry tx,y the combination of the form xFi+2 +yFi+kwith integers x, y ≥0, see below. x\y0 1 2 ··· 0 0 Fi+k2Fi+k··· 1Fi+2 Fi+k+Fi+2 2Fi+k+Fi+2 ··· 2 2Fi+2 Fi+k+ 2Fi+2 2Fi+k+ 2Fi+2 ··· 3 3Fi+2 Fi+k+ 3Fi+2 2Fi+k+ 3Fi+2 ··· . . .. . .. . .. . . Fk−1(Fk−1)Fi+2 Fi+k+ (Fk−1)Fi+2 2Fi+k+ (Fk−1)Fi+2 ··· . . .. . .. . .. . . We notice that Fi+k=Fk−2Fi+1 +Fk−1Fi+2 =Fk−2(Fi+2 −Fi)+Fk−1Fi+2 =Fi+2Fk−Fk−2Fi so, we obtain that xFi+2 +yFi+k=xFi+2 +y(Fi+2Fk−Fk−2Fi) = (x+yFk)Fi+2 −yFk−2Fi. Thus, T1can also be given by the following table, denoted by T2, 4 x\y0 1 2 · · · r··· 0 0 FkFi+2 −Fk−2Fi2FkFi+2 −2Fk−2Fi· · · rFkFi+2 −rFk−2Fi··· 1Fi+2 (1 + Fk)Fi+2 −Fk−2Fi(1 + 2Fk)Fi+2 −2Fk−2Fi· · · (1 + rFk)Fi+2 −rFk−2Fi··· 22Fi+2 (2 + Fk)Fi+2 −Fk−2Fi(2 + 2Fk)Fi+2 −2Fk−2Fi· · · (2 + rFk)Fi+2 −rFk−2Fi··· . . .. . .. . .. . .. . . llFi+2 (l+Fk)Fi+2 −Fk−2Fi(l+ 2Fk)Fi+2 −2Fk−2Fi· · · (l+rFk)Fi+2 −rFk−2Fi··· . . .. . .. . .. . .. . . Fk−1(Fk−1)Fi+2 (2Fk−1)Fi+2 −Fk−2Fi(3Fk−1)Fi+2 −2Fk−2Fi· · · . . .. . .. . .. . .. . . Let Sbe the set formed by the first Fk−1 entries of columns zero, one, two, and so on, that is, S={t0,0, t1,0, . . . , tFk−1,0, t0,1, t1,1,...,tFk−1,1,...,t0,r, t1,r,...,tFk−1,r,...}. Remark 2.2 (a) Let r=⌊Fi−1 Fk⌋and set Fi−1 = rFk+lfor some integer 0≤l≤Fk−1. Let S′={t0,0, t1,0,...,tFk−1,0, t0,1, t1,1,...,tFk−1,1,...,t2,r, t1,r,...,tl,r}, Then, for each tx,y = (x+yFk)Fi+2 −yFk−2Fi∈S′we have that 0≤x+yFk≤Fi−1. Moreover, since g.c.d.(Fi+2, Fi) = 1 then S′ forms a complete system of rests modulo Fi. (b) The elements of Scan be represented as sx=xFi+2 − ⌊ x Fk⌋Fk−2Fifor x= 0,1,.... Indeed, it can be checked that S=Sq≥1Sqwhere Sq={sqFk, sqFk+1,...,s(q+1)Fk−1}={t0,q,...,tFk−1,q} for each integer q= 0,1,2,.... (c) By using table T2we have that ti,j < tk,l for all i≤kand all j≤l. 5 Lemma 2.3 Let tu,v be an entry of T1such that tu,v 6∈ S′. There exists tx,y ∈S′such that tu,v ≡tx,y mod Fiand tu,v > tx,y. Proof. We first notice that the set Scan be written as follows {s0, . . . , sFk−1, sFk, . . . , s2Fk−1, . . . , srFk, . . . , srFk+l=sFi−1, sFi, . . . , sFi+Fk−1, sFi+Fk, . . . , sFi+2Fk−1, . . . , sFi+rFk, . . . , s2Fi−1, s2Fi, . . . , s2Fi+Fk−1, s2Fi+Fk, . . . , s2Fi+2Fk−1, . . . , s2Fi+rFk, . . . , s3Fi−1,...} where S′={s0,...,sFk−1, sFk,...,s2Fk−1,...,srFk,...,sFi−1}. We have two cases. Case A) Suppose that tu,v ∈S\S′. Then tu,v is of the form spFi+gfor some integers p≥1 and 0 ≤g≤Fi−1. It is clear that, sg=gFi+2−g FkFiFk−2≡(pFi+g)Fi+2−pFi+g FkFiFk−2=gpFi+gmod Fi. We will show that spFi+g> sg. To this end, it suffice to prove that sFi+g> sg(since spFi+g≥sFi+g). Recall that r=⌊Fi−1 Fk⌋and that Fi−1 = rFk+l for some integer 0 ≤l≤Fk−1. We have two subcases. Subcase a) If r= 0 then Fk≥Fi. If Fk=Fithen sFi+g=tg,1and, by Remark 2.2 (c), tg,0< tg,1. If Fk> Fithen sFi+g=tq,0for some integer q≥Fiand, by Remark 2.2 (c), tg,0< tq,0. Subcase b) If r≥1 then sFi+g> sgholds if and only if (Fi+g)Fi+2 −Fi+g FkFiFk−2> gFi+2 −g FkFiFk−2 6 or equivalently if and only if Fi+2 > Fk−2Fi+g Fk−g Fk· Let g=mFk+nwith 0 ≤n≤Fk−1. Since Fi−1 = rFk+lwith 0≤l≤Fk−1 then Fi−1 + g+ 1 Fk=$rFk+l+mFk+n+ 1 Fk%≤r+m+ 1 and thus Fi+g Fk−g Fk≤r+m+ 1 −m=r+ 1. So, it is enough to show that Fi+2 >(r+ 1)Fk−2or equivalently to show that Fi+Fi+1 >(r+1)Fk−2. Since Fi=rFk+l+1 then the latter inequality holds if and only if rFk+l+ 1 + Fi+1 > rFk−2+Fk−2, that is, if and only if r(Fk−Fk−2) + l+ 1 + Fi+1 =r(Fk−1) + l+ 1 + Fi+1 > Fk−2 which is true since r≥1. Case B) Suppose that tu,v 6∈ S. Then we have that 0 ≤x≤Fk−1< u. If v≥ythen, by Remark 2.2 (c), tx,y < tx,v < tu,v. So, we suppose that v < y. Since, tu,v ≡tx,y mod Fithen u+vFk≡x+yFkmod Fibut, by Remark 2.2 (a), 0 ≤x+yFk≤Fi−1 so u+vFk=d(x+yFk) for some integer d≥1 and thus u+vFk≥x+yFk. Also, since v < y, then −vFk−2Fi>−yFk−2Fi. So, combining the last two inequalities we have that tu,v = (u+vFk)Fi+2 −vFk−2Fi>(x+yFk)Fi+2 −yFk−2Fi=tx,y. 7 ⊓⊔ Therefore, by the above lemma, we have that for each x= 0,...,Fi−1, sxis the smallest positive integer congruent to lmodulo Fi, for some integer 0≤l≤Fi−1, that is representable as a nonnegative integer combination of Fi+2 and Fi+k, that is, S′=T∗. Now, by Remark 2.2 (c), if r≥1 then tFk−1,i = max 0≤x≤Fk−1{tx,i|tx,i ∈S′}for each i= 0,...,r−1, tFk−1,r−1= max 0≤i≤r−1{tFk−1,i|tFk−1,i ∈S′}, and tl,r = max 0≤x≤l{tx,r|tx,r ∈S′}. Thus, max{s|s∈S′}=(tl,r if r= 0, max{tFk−1,r−1, tl,r}otherwise. The result follows since tl,r > tFk−1,r−1if and only if (rFk+l)Fi+2−rFk−2Fi= (Fi−1)Fi+2−rFk−2Fi>(rFk−1)Fi+2−(r−1)Fk−2Fi or equivalently, if and only if Fi+2(Fi−rFk)> Fk−2Fi.⊓⊔ We will use the following result due to Selmer [4] to show Corollary 1.2. Lemma 2.4 Let 1< a1<··· < anbe integers with g.c.d.(a1,...,an) = 1. If L={1,...,a1−1}then 8 N(a1,...,an) = 1 a1X l∈L tl−a1−1 2· where tlis the smallest positive integer congruent to lmodulo a1, that is representable as a nonnegative integer combination of a2,...,an. Proof. The number of M≡l6≡ 0 mod a1with 0 < M < tlis given by ⌊t1 a1⌋. By assuming that 0 < l < a1, we have ⌊tl a1⌋=tl−l a1. The result follows by summing over l∈L.⊓⊔ Proof of Corollary 1.2. Let r=⌊Fi−1 Fk⌋and set Fi−1 = rFk+lfor some integer 0 ≤l≤Fk−1. By Lemma 2.4 and Remark 2.2 (b), we have N(Fi, Fi+2, Fi+k) = 1 FiP s∈S′ s−Fi−1 2 =1 Fi Fi−1 P j=0 (jFi+2 −Fk−2⌊j Fk⌋Fi)−Fi−1 2 =1 FiFi+2 (Fi−1)Fi 2−1 Fi(Fk−2Fi)Fi−1 P j=0 jj Fkk−Fi−1 2. By using the table T1, it is easy to verify that Fi−1 X j=0 j Fk= 0 + Fk+ 2Fk+···+ (r−1)Fk+r(l+ 1) = Fk(r−1)r 2+r(l+ 1) and, since l+ 1 = Fi−rFk, then 9