×

The parametric Frobenius problem. (English) Zbl 1339.11042

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.

MSC:

11D07 The Frobenius problem
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
11H06 Lattices and convex bodies (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Danny Calegari and Alden Walker. Integer hulls of linear polyhedra and scl in families. Transactions of the American Mathematical Society, 365:5085-5102, 2011. · Zbl 1300.11100
[2] Sheng Chen, Nan Li, and Steven V. Sam. Generalized Ehrhart polynomials. Trans. Amer. Math. Soc., 364(1):551-569, 2012. · Zbl 1238.11045
[3] Eug‘ene Ehrhart. Sur les poly‘edres rationnels homoth´etiques ‘a n dimensions. C. R. Acad. Sci. Paris, 254:616-618, 1962. · Zbl 0100.27601
[4] David Einstein, Daniel Lichtblau, Adam Strzebonski, and Stan Wagon. Frobenius numbers by lattice point enumeration. Integers, 7:A15, 63, 2007. · Zbl 1229.11049
[5] J. L. Ram´ırez Alfons´ın. The Diophantine Frobenius problem, volume 30 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2005. · Zbl 1134.11012
[6] J. B. Roberts. Note on linear forms. Proc. Amer. Math. Soc., 7:465-469, 1956. · Zbl 0071.03902
[7] Øystein J. Rødseth. On a linear Diophantine problem of Frobenius. J. Reine Angew. Math., 301:171-178, 1978. · Zbl 0374.10011
[8] James J. Sylvester. Mathematical questions with their solutions. Educational Times, 41(21), 1884.
[9] Stan Wagon, personal comunication. the electronic journal of combinatorics 22(2) (2015), #P2.3615
[10] Kevin Woods. The unreasonable ubiquitousness of quasi-polynomials. Electron. J. Combin., 21(1):#P1.44, 2014. · Zbl 1300.05031
[11] Kevin Woods.Presburger arithmetic, rational generating functions, and quasipolynomials. Journal of Symbolic Logic, 80:433-449, 2015. · Zbl 1353.03074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.