Block Reduced Lattice Bases and Successive Minima

Source abstract

A lattice basis b i ,…, b m is called block reduced with block size β if for every β consecutive vectors b i ,…, b i +β−1 , the orthogonal projections of b i ,…, b i +β−1 in span( b i ,…, b i −1 ) ⊥ are reduced in the sense of Hermite and Korkin–Zolotarev. Let λ i denote the successive minima of lattice L , and let b 1 ,…, b m be a basis of L that is block reduced with block size β. We prove that for i = 1,…, m where γ β is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that where the maximum is taken over all block reduced bases of all lattices L . We present critical block reduced bases achieving this maximum. Using block reduced bases, we improve Babai's construction of a nearby lattice point. Given a block reduced basis with block size β of the lattice L , and given a point x in the span of L , a lattice point υ can be found in time β O(β) satisfying These results also give improvements on the method of solving integer programming problems via basis reduction.