Claus Peter Schnorr

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₁,…,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.