We present structural results on solutions to the Diophantine system $A{\boldsymbol y} = {\boldsymbol b}$, ${\boldsymbol y} \in \mathbb Z^t_{\ge 0}$ with the smallest number of non-zero entries. Our tools are algebraic and number theoretic in nature and include Siegel's Lemma, generating functions, and commutative algebra. These results have some interesting consequences in discrete optimization.

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions to systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer k, we prove that there exists a constant c(n,k), depending only on the dimension n and k, such that if a polyhedron {x∈Rn: Ax≤b} contains exactly k integer points, then there exists a subset of the rows, of cardinality no more than c(n,k), defining a polyhedron that contains exactly the same k integer points. In this case c(n,0)=2n as in the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant c(n,k) and discuss some consequences, including a Clarkson-style algorithm to find the l-th best solution of an integer program with respect to the ordering induced by the objective function.