Semigroups of Polyhedra with Prescribed Number of Lattice Points and the k-Frobenius Problem

Iskander Aliev, Jesus A. De Loera, Quentin Louveaux

Published 2014-09-18Version 1

The well-studied semigroup sg(A)={b: b=Ax, x non-negative integral vector} can be stratified by the sizes of the polyhedral fibers IP_A(b)={x: Ax=b, x non-negative integral vector}. The key theme of this paper is a structure theory that characterizes precisely the set sg_{\ge k}(A) of all vectors b in sg(A) such that their fiber IP_A(b) has at least k solutions. We demonstrate that this set is finitely generated, 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 IP_A(b) has exactly k solutions or fewer than k solutions. The main result of this paper shows that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of sg_{\ge k}(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have at least k solutions. Using this tool we prove that for fixed n,k the k-Frobenius number can be computed in polynomial time, generalizing a well-known result of R. Kannan.