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

The authors derive estimates relating the following quantities of a lattice L in Euclidean space: (i) the (Euclidean) lengths of the basis vectors of a lattice basis which is reduced in the sense of Korkine- Zolotareff, (ii) the successive minima of L and its dual lattice \(L^*\), (iii) the covering radius \(\mu\) (L) of L, (iv) Hermite's constants. They also develop methods which allow to compute in polynomial time lower bounds for the first successive minimum and the distance of a given vector from the closest lattice point. They give a short account on the computational complexity of finding shortest (closest) vectors in a lattice. Finally, they generalize several of their estimates to arbitrary symmetric convex distance functions.