2015/10/05 by Shen, Bobby
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1510.01349
The Frobenius number of relatively prime positive integers a1, …, an is the largest integer that is not a nononegative integer combination of the ai. Given positive integers a1, …, an with n ≥ 2, the set of multiples of gcd(a1, …, an) which have less than m distinct representations as a nonnegative integer combination of the ai is bounded above, so we define fm, ℓ(a1, …, an) to be the ℓth largest multiple of gcd(a1, …, an) with less than m distinct representations (which generalizes the Frobenius number) and gm(a1, …, an) to be the number of positive multiples of gcd(a1, …, an) with less than m distinct representations. In the parametric Frobenius problem, the arguments are polynomials. Let P1, …, Pn be integer valued polynomials of one variable which are eventually positive. We prove that fm, ℓ(P1(t), …, Pn(t)) and gm(P1(t), …, Pn(t)), as functions of t, are eventually quasi-polynomial. A function h is eventually quasi-polynomial if there exist d and polynomials R0, …, Rd-1 such that for such that for sufficiently large integers t, h(t)=R_t \pmodd(t). We do so by formulating a type of parametric problem that generalizes the parametric Frobenius Problem, which we call a parametric exclusion problem. We prove that the ℓth largest value of some polynomial objective function, with multiplicity, for a parametric exclusion problem and the size of its feasible set are eventually quasi-polynomial functions of t.