The parametric Frobenius problem

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

The Frobenius problem (11D07) Lattices and convex bodies (number-theoretic aspects) (11H06) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: Given relatively prime positive integers a_1,...,a_n, the Frobenius number is the largest integer that cannot be written as a nonnegative integer combination of the a_i. We examine the parametric version of this problem: given a_i=a_i(t) as functions of t, compute the Frobenius number as a function of t. A function f is a quasi-polynomial if there exists a period m and polynomials f_0,...,f_{m-1} such that f(t)=f_{t mod m}(t) for all positive integers t. We conjecture that, if the a_i(t) are polynomials (or quasi-polynomials) in t, then the Frobenius number agrees with a quasi-polynomial, for sufficiently large t. We prove this in the case where the a_i(t) are linear functions, and also prove it in the case where n (the number of generators) is at most 3.

Review text

Summary: Given relatively prime positive integers \(a_1,...,a_n\), the Frobenius number is the largest integer that cannot be written as a nonnegative integer combination of the \(a_i\). We examine the parametric version of this problem: given \(a_i=a_i(t)\) as functions of \(t\), compute the Frobenius number as a function of \(t\). A function \(f:\mathbb{Z}_+\to\mathbb{Z}\) is a quasi-polynomial if there exists a period \(m\) and polynomials \(f_0,...,f_{m-1}\) such that \(f(t)=f_{t\mathrm{mod} m}(t)\) for all \(t\). We conjecture that, if the \(a_i(t)\) are polynomials (or quasi-polynomials) in \(t\), then the Frobenius number agrees with a quasi-polynomial, for sufficiently large \(t\). We prove this in the case where the \(a_i(t)\) are linear functions, and also prove it in the case where \(n\) (the number of generators) is at most 3.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: The parametric Frobenius problem

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