×

On the Frobenius number of Fibonacci numerical semigroups. (English) Zbl 1177.11017

Let \(s_1, s_2, \dots, s_n\) be positive integers such that their greatest common divisor is one. Let \(S =\langle s_1, \dots, s_n\rangle\) be the numerical semigroup generated by \(s_1, \dots, s_n\). A Fibonacci numerical semigroup is a numerical semigroup generated by a set of Fibonacci numbers \(F_{i_1},\dots, F_{i_r}\), for some integers \(3\leq i_1 < \dots < i_r\) where \(\gcd(F_{i_1},\dots, F_{i_r}) = 1\).
The Frobenius number, denoted by \(g(s_1, \dots, 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, \dots, s_n\). It is well known that \(g(s_1, s_2) = s_1s_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, when \(S\) is an arithmetical sequence \(g(S)\) is known [J. B. Roberts, Proc. Am. Math. Soc. 7, 465–469 (1956; Zbl 0071.03902)] \[ g(a, a + d, \dots, a + kd) = a\left(\left\lfloor \frac{a-2}{k}\right\rfloor\right)+ d(a-1). \tag{1} \]
In this note, the authors investigate the value of \(g(F_i, F_j , F_l)\) for some triples \(3\leq i < j < l\) (\(\gcd(F_i, F_j , F_l) = 1\); recall that \(\gcd(F_i, F_{i+l}) = 1\) if \(i \nmid l\)).
They consider \(g(F_i, F_{i+2}, F_l)\) with \(l \geq i+3\). The case \(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 +2}F_{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\geq 3\) and then the calculation of \(g(F_i, F_{i+2}, F_{i+k})\) is more complicated. The authors’ main result is then as follows.
Theorem 1. Let \(i, k \geq 3\) be integers and let \(r = \lfloor \frac{F_i-1}{F_k}\rfloor\). Then,
\[ g(F_i, F_{i+2}, F_{i+k}) = (F_i-1)F_{i+2} - F_i(rF_{k-2} + 1) \;\text{if}\;r = 0 \;\text{or}\;r \geq 1 \;\text{and}\;F_k-2F_i < (F_i - rF_k)F_{i+2}, \] and \[ g(F_i, F_{i+2}, F_{i+k}) =(rF_k-1)F_{i+2}- F_i((r-1)F_{k-2} + 1) \;\text{otherwise}. \]
Let \(N(a_1, \dots, a_n)\) be the number of positive integers with no representation by a nonnegative integer combination of \(a_1, \dots, a_n\). Then Theorem 1 yields the following result.
Corollary 2. Let \(i, k \geq 3\) be integers and let \(r = \lfloor \frac{F_i-1}{F_k}\rfloor\). 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}. \]
In the proof of Theorem 1 the authors use a result of A. Brauer and J. E. Shockley [J. Reine Angew. Math. 211, 215–220 (1962; Zbl 0108.04604)].

MSC:

11D07 The Frobenius problem
20M14 Commutative semigroups
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
11B34 Representation functions
PDFBibTeX XMLCite
Full Text: arXiv EMIS