A Threshold Number for the Shortest Vector Problem in the Infinity Norm

Stefan Kuhlmann, Robert Weismantel

For an integer full column rank matrix $A$, we consider the lattice that consists of all integer combinations of columns of $A$. We prove that a shortest non-zero vector $Az$ has i…