An Optimization Problem for Lattices

Abstract

We present theoretical and computational results concerning an optimization problem for lattices, related to a generalization of the concept of dual lattices. Let Λ be a k-dimensional lattice in (with 0<k⩽n), and . We define the p, q-norm N _p,q (Λ) of the lattice Λ and show that this norm always exists. In fact, our results yield an algorithm for the calculation of N _p,q (Λ). Further, since this general algorithm is not efficient, we discuss more closely two particular choices for p, q that arise naturally. Namely, we consider the case (p, q)=(2, ∞), and also the choice (p, q)=(1, ∞). In both cases, we show that in general, an optimal basis of Λ as well as N _p,q (Λ) can be calculated. Finally, we illustrate our methods by several numerical examples.

2000 AMS Subject Classification:

• 06B99

Keywords:

• lattices
• dual lattices
• bases of lattices
• basis reduction
• LLL-reduction

7. ACKNOWLEDGMENTS

The authors are grateful to the referee for helpful and useful suggestions that improved the presentation of the paper considerably.

This research was supported in part by the TÁMOP 4.2.2. C-11/1/KONV-2012-0001 project, implemented through the New Hungary Development Plan, cofinanced by the European Social Fund and the European Regional Development Fund, and OTKA grants K75566, K100339, K104208, NK101680.