Generalized Frobenius numbers: bounds and average behavior

DOI10.4064/AA155-1-5MaRDI QIDQ2919666zbMATH OpenOpenAlexFDO

Authors Lenny Fukshansky, Martin Henk, Iskander Aliev

Publication date 5 October 2012

Published in Acta Arithmetica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.0841, http://orca.cf.ac.uk/70674/1/1105.0841.pdf

zbMATH Keywords

covering radiusdistribution of latticesgeneralized Frobenius numberinhomogeneous minimumsuccessive minima

Mathematics Subject Classification ID

The Frobenius problem (11D07) Counting solutions of Diophantine equations (11D45) Lattices and convex bodies (number-theoretic aspects) (11H06)

Abstract: We produce new upper and lower bounds for the s-Frobenius number by relating it to the so called s-covering radius of a certain convex body with respect to a certain lattice; this generalizes a well-known theorem of R. Kannan for the classical Frobenius number. Using these bounds, we obtain results on the average behavior of the s-Frobenius number, extending analogous recent investigations for the classical Frobenius number by a variety of authors. We also derive bounds on the s-covering radius, an interesting geometric quantity in its own right.

Review text

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.

Recommendations

• Bounds on generalized Frobenius numbers
• An extreme family of generalized Frobenius numbers
• Some estimated formulas for the Frobenius numbers
• scientific article; zbMATH DE number 2084918
• An optimal lower bound for the Frobenius problem
• scientific article; zbMATH DE number 1112790
• The Frobenius number associated with the number of representations for sequences of repunits
• Extremal Frobenius numbers in a class of sets
• On a generalization of the coin exchange problem for three variables
• Every positive integer is the Frobenius number of a numerical semigroup with three generators

Cited in

(10)

• Commutative algebra of generalised Frobenius numbers
• The upper bound of Frobenius related length functions
• Integer points in knapsack polytopes and s-covering radius
• Positive semigroups and generalized Frobenius numbers over totally real number fields
• Integer knapsacks: average behavior of the Frobenius numbers
• Symmetric semigroups with three generators
• A note on lower bounds for Frobenius traces
• Expected Frobenius numbers
• The generalized Frobenius problem via restricted partition functions
• Bounds on generalized Frobenius numbers

This page was built for publication: Generalized Frobenius numbers: bounds and average behavior

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2919666)