a1 Fachbereich Mathematik/Informatik, Universität Frankfurt, Postfach 111932, D–60054 Frankfurt a.M., Germany. email: email@example.com
A lattice basis bi,…,bm is called block reduced with block size β if for every β consecutive vectors bi,…,bi+β−1, the orthogonal projections of bi,…,bi+β−1 in span(bi,…,bi−1) are reduced in the sense of Hermite and Korkin–Zolotarev. Let λi denote the successive minima of lattice L, and let b1,…,bm 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.
(Received September 04 1992)
(Revised March 03 1994)