KORKIN-ZOLOTAREV BASES AND SUCCESSIVE MINIMA OF A LATTICE AND ITS RECIPROCAL LATTICE

Let Ai(L), Ai(L*) denote the successive minima of a lattice L and its reciprocal lattice L*, and let [bl,..., bn] be a basis of L that is reduced in the sense of Korkin and Zolotarev. We prove that [4/(/+ 3)]),i(L) 2 _< [bi [ 2 < [(i + 3)/4])~i(L) 2 and Ibil2An_i+l(L*) 2 < _ [(i + 3)/4][(n- i + 4)/417 ~ 2, where "y ~ =- min(Tj: 1 < j _< n} and 7j denotes Hermite's constant. As a consequence the inequalities 1 < Ai(L)An_i+x(L * ) < n2/6 are obtained for n> 7. Given a basis B of a lattice L in R m of rank n and x E R m, we define polynomial time computable quantities A(B) and #(x, B) that are lower bounds for A1 (L) and/~(x, L), where/x(x, L) is the Euclidean distance from x to the closest vector in L. If in addition B is reciprocal to a Korkin-Zolotarev basis of L*, then AI(L) < 3,~A(B) n *2 X and #(x, L) 2 _< (E i = l "ri)~ ( , B) 2-1. In t roduct ion The problem of selecting from all bases for a latt ice a canonical basis with desirable propert ies is called reduction theory. The classical question mot ivat ing the invention of reduct ion theory is the determinat ion of the min ima of posit ive definite integral quadrat ic forms. Lagrange [10] developed a reduct ion theory for b inary quadrat ic forms, and the general s tudy of the higher dimensional case wa