An Optimization Problem for Lattices

作者：Hajdu L^*; Kovacs T; Petho A; Pohst M

来源：Experimental Mathematics, 2013, 22(4): 443-455.

DOI：10.1080/10586458.2013.833489

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

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 . We define the p, q-norm N-p,N-q() of the lattice and show that this norm always exists. In fact, our results yield an algorithm for the calculation of N-p,N-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,N-q() can be calculated. Finally, we illustrate our methods by several numerical examples.

• 出版日期2013-10-2