  We consider the problem of minimizing a polynomial function over the integer
lattice. Though impossible in general, we use a known sufficient condition for
the existence of continuous minimizers to guarantee the existence of integer
minimizers as well. In case this condition holds, we use sos programming to
compute the radius of a p-norm ball which contains all integer minimizers. We
prove that this radius is smaller than the radius known from the literature.
Furthermore, we derive a new class of underestimators of the polynomial
function. Using a Stellensatz from real algebraic geometry and again sos
programming, we optimize over this class to get a strong lower bound on the
integer minimum. Our radius and lower bounds are evaluated experimentally. They
show a good performance, in particular within a branch and bound framework.
