The parametric Frobenius problem

MaRDI QIDQ2346475zbMATH OpenFDO

Authors Bjarke Hammersholt Roune, Kevin M. Woods

Publication date 2 June 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06009, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p36

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

zbMATH Keywords

quasi-polynomialsFrobenius problem

Mathematics Subject Classification ID

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

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.

Recommendations

• scientific article; zbMATH DE number 18540
• The multidimensional Frobenius problem
• The Frobenius Problem and Its Generalizations
• Frobenius' problem
• scientific article; zbMATH DE number 4214113
• On the Frobenius problem
• scientific article; zbMATH DE number 1065046
• On the multidimensional Frobenius problem
• On a Frobenius problem for polynomials
• scientific article; zbMATH DE number 554876

Cites work

• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Frobenius numbers by lattice point enumeration
• Generalized Ehrhart polynomials
• Integer hulls of linear polyhedra and scl in families
• Note on Linear Forms
• On a linear Diophantine problem of Frobenius.
• The unreasonable ubiquitousness of quasi-polynomials

Cited in

(11)

• Apéry sets of shifted numerical monoids
• Parametric polyhedra with at least k lattice points: their semigroup structure and the k-Frobenius problem
• The unreasonable ubiquitousness of quasi-polynomials
• Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior
• Graver bases of shifted numerical semigroups with 3 generators
• A plethora of polynomials: a toolbox for counting problems
• Parametrizing an integer linear program by an integer
• scientific article; zbMATH DE number 5485564 (Why is no real title available?)
• On parametrized families of numerical semigroups
• Bounding quantification in parametric expansions of Presburger arithmetic
• On a Frobenius problem for polynomials

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)