A Note on Lattice Packings via Lattice Refinements

ABSTRACT

Rogers proved in a constructive way that every packing lattice Λ of a symmetric convex body K in is contained in a packing lattice whose covering radius is less than 3. By a slight modification of Rogers’ approach better bounds for l_p-balls are obtained. Together with Rogers’ constructive proof, this leads, for instance, to a simple o(n^n/2) running time algorithm that refines successively the packing lattice Dⁿ (checkboard lattice) of the unit ball Bⁿ and terminates with a packing lattice with density . We have also implemented this algorithm and in small dimensions (⩽ 25) and for certain simple structured start lattices like or Dⁿ the algorithm often terminates with packing lattices achieving the best-known lattice densities.

KEYWORDS:

• algorithm
• covering radius
• covering
• lattice
• l_p-balls
• packing
• packing-covering ratio

2000 AMS SUBJECT CLASSIFICATION:

• 52C07
• 52C17
• 11H06

Notes

On a 3.1 GHz Intel Core i7 processor.