# zbMATH — the first resource for mathematics

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. (English) Zbl 0723.11029
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.

##### MSC:
 11H55 Quadratic forms (reduction theory, extreme forms, etc.) 11H06 Lattices and convex bodies (number-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 11H50 Minima of forms
Full Text: