Optimization Online


On sublattice determinants in reduced bases

Gabor Pataki (gabor***at***unc.edu)
Mustafa Tural (tural***at***email.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society