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 a least radians), then the basis is nearly KZ-reduced for some ordering of the basis vectors. It follows that a KZ-reduced basis can be obtained from a nearly orthogonal basis in polynomial time. We also show that if a nearly orthogonal lattice basis has nearly equal vector lengths (they are within a certain constant factor of one another), then the basis is Minkowski reduced. We use this result to show that m i.i.d. random vectors drawn from a uniform distribution over the unit ball in
form a Minkowski-reduced basis of the lattice generated by the vectors almost surely as n tends to infinity, if
for a constant
. This result extends a result of Donaldson (1979) who proved the above property for fixed m as n tends to infinity.
By: Sanjeeb Dash; Ramesh Neelamani; Gregory B. Sorkin
Published in: RC24696 in 2008
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .