Document Type
Discussion Paper
Publication Date
1-1-1991
CFDP Number
965
CFDP Pages
8
Abstract
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.
Recommended Citation
Scarf, Herbert E. and Shallcross, David F., "Shortest Integer Vectors" (1991). Cowles Foundation Discussion Papers. 1208.
https://elischolar.library.yale.edu/cowles-discussion-paper-series/1208