On sublattice determinants in reduced bases

Gabor Pataki (gaborunc.edu)
Mustafa Tural (turalemail.unc.edu)

Abstract: We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the norms of the first few basis vectors.

Keywords: basis reduction, subdeterminants, shortest vector, geometry of numbers

Category 1: Integer Programming (Other )

Category 2: Other Topics (Other )

Citation: Technical Report 08-02, Department of Statistics and Operations Research, University of North Carolina at Chapel Hill

Download: [Postscript][PDF]

Entry Submitted: 04/24/2008
Entry Accepted: 04/24/2008
Entry Last Modified: 05/08/2008

Modify/Update this entry