Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

Let _i(L), _i(L^*) denote the successive minima of a latticeL and its reciprocal latticeL ^*, and let b₁,..., b _n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that and, where and _j denotes Hermite's constant. As a consequence the inequalities are obtained forn7. Given a basisB of a latticeL in ^m of rankn andx ^m , we define polynomial time computable quantities(B) and(x,B) that are lower bounds for ₁(L) and(x,L), where(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL ^*, then ₁(L) _n ^* (B) and.The research of the second author was supported by NSF contract DMS 87-06176. The research of the third author was performed at the University of California, Berkeley, with support from NSF grant 21823, and at AT&T Bell Laboratories.