Minkowski and KZ reduction of nearly orthogonal lattice bases
Sanjeeb Dash, Ramesh Neelamani, Gregory B. Sorkin · 2011
We prove that if a lattice basis is nearly orthogonal (the angle between any basis vector and the linear subspace spanned by the other basis vectors is at least 3 radians), then a KZ-reduced basis can be obtained from it in polynomial time. We also show that if a nearly orthogonal lattice basis has nearly equal vector lengths (within a certain constant factor of one another), then the basis is Minkowski reduced. We use these results to show thatmi.i.d. random vectors drawn from a uniform distribution over the unit ball in R n form a Minkowski-reduced basis of the lattice generated by the vectors asymptotically almost surely as n tends to infinity, if m cn for any constant c < 1/4, and form a KZ-reduced basis for c < 1/5. The result on Minkowski reduction in lattices generated by random vectors extends a result of Donaldson (1979) who proved this property for fixed m as n tends to infinity.