SHORTEST INTEGER VECTORS

Let A be a fixed integer matrix of size m by n and consider all b for which the body K(b) = {x: Ax less-than-or-equal-to b} is full dimensio nal. We examine the set of shortest nonzero integral vectors with resp ect to the family of norms whose unit balls are given by (K(b) - K(b)) . We show that the number of such shortest vectors is polynomial in th e bit size of A, for fixed n. We also show the existence, for any n, o f a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree as the polynomial bound.