×

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. (English) Zbl 0723.11029

The authors derive estimates relating the following quantities of a lattice L in Euclidean space: (i) the (Euclidean) lengths of the basis vectors of a lattice basis which is reduced in the sense of Korkine- Zolotareff, (ii) the successive minima of L and its dual lattice \(L^*\), (iii) the covering radius \(\mu\) (L) of L, (iv) Hermite’s constants.
They also develop methods which allow to compute in polynomial time lower bounds for the first successive minimum and the distance of a given vector from the closest lattice point. They give a short account on the computational complexity of finding shortest (closest) vectors in a lattice. Finally, they generalize several of their estimates to arbitrary symmetric convex distance functions.

MSC:

11H55 Quadratic forms (reduction theory, extreme forms, etc.)
11H06 Lattices and convex bodies (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
11H50 Minima of forms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Babai: On Lovász’ lattice reduction and the nearest lattice point problem,Combinatorica,6 (1986), 1–13. · Zbl 0593.68030 · doi:10.1007/BF02579403
[2] J. W. S. Cassels:An introduction to the geometry of numbers, Springer-Verlag, Berlin,1971.
[3] J. H. Conway, andN. J. A. Sloane:Sphere packings, lattices and groups, Springer-Verlag, New York,1988.
[4] M. Grötschel, L. Lovász, andA. Schrijver:Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin,1988.
[5] P. M. Gruber, andC. G. Lekkerkerker:Geometry of numbers, North-Holland, Amsterdam,1987.
[6] C. Hermite: Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres, Deuxième lettre,J. Reine Angew. Math. 40 (1850), 279–290. · ERAM 040.1109cj · doi:10.1515/crll.1850.40.279
[7] F. John: Extremum problems with inequalities as subsidiary conditions, K. O. Friedrichs, O. E. Neugebauer, J. J. Stoker (eds),Studies and essays presented to R. Courant on his 60th birthday, 187–204, Interscience Publishers, New York,1948.
[8] R. Kannan: Minkowski’s convex body theorem and integer programming,Math. Oper. Res. 12 (1987), 415–440. · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[9] A. Korkine, andG. Zolotareff: Sur les formes quadratiques,Math. Ann. 6 (1873), 366–389. · JFM 05.0109.01 · doi:10.1007/BF01442795
[10] J. L.Lagrange: Recherches d’arithmétique,Nouv. Mém. Acad. Berlin (1773), 265–312; vres, vol. VIII, 693–753.
[11] A. K. Lenstra, H. W. Lenstra, Jr., andL. Lovász: Factoring polynomials with rational coefficients,Math. Ann. 261 (1982), 515–534. · Zbl 0488.12001 · doi:10.1007/BF01457454
[12] H. W. Lenstra, Jr.: Integer programming with a fixed number of variables,Math. Oper. Res. 8 (1983), 538–548. · Zbl 0524.90067 · doi:10.1287/moor.8.4.538
[13] L. Lovász: An algorithmic theory of numbers, graphs and convexity,CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania,1986. · Zbl 0606.68039
[14] K. Mahler: A theorem on inhomogeneous diophantine inequalities,Nederl. Akad. Wetensch., Proc. 41 (1938), 634–637. · Zbl 0019.05105
[15] K.Mahler:The geometry of numbers, duplicated lectures, Boulder, Colorado,1950. · Zbl 0041.01203
[16] J. Milnor, andD. Husemoller:Symmetric bilinear forms, Springer-Verlag, Berlin,1973.
[17] N. V. Novikova: Korkin-Zolotarev reduction domains of positive quadratic forms inn variables and a reduction algorithm for these domains,Dokl. Akad. Nauk SSSR 270 (1983), 48–51; English translation:Soviet Math. Dokl. 27 (1983), 557–560. · Zbl 0535.10033
[18] C. A. Rogers:Packing and covering, Cambridge University Press, Cambridge,1964. · Zbl 0176.51401
[19] S. S. Ryshkov: Geometry of positive quadratic forms (Russian),Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974),1, 501–506,Canad. Math. Congress, Montreal, Que., 1975.
[20] S. S. Ryshkov, andE. P. Baranovskii: Classical methods in the theory of lattice packings,Uspekhi Mat. Nauk 34, 4 (208) (1979), 3–63; English translation:Russian Math. Surveys 34 (4) (1979), 1–68.
[21] C. P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms,Theoret. Comput. Sci. 53 (1987), 201–224. · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8
[22] B. L. van der Waerden: Die Reduktionstheorie der positiven quadratischen Formen,Acta Math. 96 (1956), 265–309. · Zbl 0072.03601 · doi:10.1007/BF02392364
[23] B. L. van der Waerden: H. Gross (eds),Studien zur Theorie der quadratischen Formen, BirkhÄuser-Verlag, Basel,1968. · Zbl 0185.11002
[24] P. van Emde Boas: AnotherNP-complete partition problem and the complexity of computing short vectors in a lattice,Report 81-04, Department of Mathematics, University of Amsterdam, Amsterdam,1981.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.