Parametric Polyhedra with at least $k$ Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

Given an integral $d\times n$ matrix $A$, the well-studied affine semigroup $Sg(A)=\{b:Ax=b,x\in {\mathbb{Z}}^n,x\ge 0\}$ can be stratified by the number of lattice points inside the parametric polyhedra $P_A(b)=\{x:Ax=b,x\ge 0\}$. Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset $S{g}_{\ge k}(A)$ of all vectors $b \in \mbox{ Sg}(A)$suchthat$P_A(b) \cap {\mathbb Z}^n $hasatleast$k$ solutions. We demonstrate that this set is finitely generated, it is a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors $b$ for which $P_A(b)\cap {\mathbb{Z}}^n$ has exactly $k$ solutions or fewer than $k$ solutions. (2) A computational complexity theory. We show that, when $n$, $k$ are fixed natural numbers, one can compute in polynomial time an encoding of $S{g}_{\ge k}(A)$ as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least $k$ solutions. (3) Applications and computation for the $k$-Frobenius numbers. Using Generating functions we prove that for fixed $n,k$ the $k$-Frobenius number can be computed in polynomial time. This generalizes a well-known result for $k=1$ by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of $k$-Frobenius numbers and their relatives.