Generalized Frobenius numbers: bounds and average behavior (Q2919666)

Given a vector of positive integers \(a= (a_1, \ldots, a_n)\) with \(\gcd(a_1, \ldots, a_n)=1\) and a positive integer \(s\), the \(s\)-Frobenius number \(F_s(a)\) is defined as the largest integer which cannot be written as a linear combination of the \(a_i\)'s with nonnegative integer coefficients in at least \(s\) distinct ways. This notion generalizes the usual Frobenius number, obtained for \(s=1\).NEWLINENEWLINEThe main theorem of the paper under review provides the following inequalities for \(F_s(a)\): NEWLINE\[NEWLINEs^\frac{1}{n-1}[(n-1)!\, a_1\cdots a_n]^\frac{1}{n-1} - (a_1 + \cdots a_n) \leq F_s(a) \leq F_1(a)+ (s-1)^\frac{1}{n-1}[(n-1)!\, a_1 \cdots a_n ]^\frac{1}{n-1}. NEWLINE\]NEWLINE The lower bound generalizes a known inequality for \(F_1(a)\) proved by \textit{M. Hujter} [``On a sharp upper and lower bounds for the Frobenius problem''. (Hungarian). Working paper MO/32, Computer and Automation Inst., Hung. Acad. Sci. (1982)]. As a consequence of these bounds, the authors are able to extend results on the classical Frobenius number from \textit{I. Aliev} et al. [J. Comb. Theory, Ser. A 118, No. 2, 525--531 (2011; Zbl 1237.11013)] and \textit{Han Li} [\url{http://arxiv.org/abs/1101.3021} (2011)] to conclude that the expected size of \(F_s(a)\) is close to its lower bound.