COWLES FOUNDATION FOR RESEARCH IN ECONOMICS
AT YALE UNIVERSITY

Box 208281
New Haven, CT 06520-8281

COWLES FOUNDATION DISCUSSION PAPER NO. 965

"Shortest Integer Vectors"

Herbert E. Scarf and David F. Shallcross

January 1991

Let A be a fixed integer matrix of size m by n and consider all b for which the body is full dimensional. We examine the set of shortest non-zero integral vectors with respect to the family of norms. We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of 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 at the polynomial bound.

Keywords: Indivisibilities, integer programming, geometry, numbers

JEL Classification: C60, C61