zbMATH — the first resource for mathematics

Hermite’s constant and lattice algorithms. (English) Zbl 1230.11155
Nguyen, Phong Q. (ed.) et al., The LLL algorithm. Survey and applications. Dordrecht: Springer (ISBN 978-3-642-02294-4/hbk; 978-3-642-02295-1/ebook). Information Security and Cryptography, 19-69 (2010).
The paper surveys the algorithms to find the shortest vector in \(n\)-dimensional lattices and their connections with the Hermite’s constant \(\gamma_n\), constant related with the problem of lattice sphere packing in \(\mathbb{R}^n\), see the book of J. H. Conway and N. J. A. Sloane [Sphere packings, lattices and groups. 3rd ed. New York, NY: Springer (1999; Zbl 0915.52003)]. The constant \(\gamma_n\) verifies the Hermite’s inequality \(\gamma_n\leq \gamma_2^{n-1}\,\, (\gamma_2=(4/3)^{1/2})\).
After introducing the necessary mathematical background about lattices and lattice reduction (or reduced bases) the paper outlines the Shortest Vector Problem (SVP) and its approximation versions. The section “Two-dimensional case” reviews the reduction algorithm of Lagrange (or Gauss) for the case \(n=2\). Then the paper explains the best known approximation algorithm: the celebrated Lenstra-Lenstra-Lovasz (LLL) algorithm [Math. Ann. 261, 513–534 (1982; Zbl 0488.12001)], which can be seen “as an (efficient) algorithmic version of Hermite’s inequality on Hermite’s constant”.
The section “Solving the exact SVP” presents the two main exact algorithms (enumeration and sieving) for the SVP, which both use the LLL algorithm as a tool. Finally the last section is devoted to detail the Gama-Nguyen’s slide algorithm [N. Gama and P. Q. Nguyen, in: STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM). 207–216 (2008; Zbl 1230.11153)], a blockwise generalization of the LLL algorithm. The blockwise algorithms can be interpreted as algorithmic versions of a generalization of the Hermite’s inequality, the Mordell’s inequality: \(\gamma_n\leq \gamma_k^{(n-1)(k-1)},\,\, 2\leq k\leq n\).
For the entire collection see [Zbl 1179.11003].

11Y16 Number-theoretic algorithms; complexity
11H06 Lattices and convex bodies (number-theoretic aspects)
11H31 Lattice packing and covering (number-theoretic aspects)
11H55 Quadratic forms (reduction theory, extreme forms, etc.)
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
PDF BibTeX Cite
Full Text: DOI