Combinatorics, Probability and Computing

Research Article

Block Reduced Lattice Bases and Successive Minima

C. P. Schnorra1

a1 Fachbereich Mathematik/Informatik, Universität Frankfurt, Postfach 111932, D–60054 Frankfurt a.M., Germany. email: schnorr@informatik.uni-frankfurt.de

Abstract

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)xs22A5 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

S0963548300001371eqnU1

where γβ is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that

S0963548300001371eqnU2

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

S0963548300001371eqnU3

These results also give improvements on the method of solving integer programming problems via basis reduction.

(Received September 04 1992)

(Revised March 03 1994)