Skip to main content
SpringerLink
Log in

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

Letλ i(L), λi(L*) denote the successive minima of a latticeL and its reciprocal latticeL *, and let [b1,..., b n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that

and

, where

andγ j denotes Hermite's constant. As a consequence the inequalities

are obtained forn≥7. Given a basisB of a latticeL in ℝm of rankn andx∃ℝm, we define polynomial time computable quantitiesλ(B) andΜ(x,B) that are lower bounds for λ1(L) andΜ(x,L), whereΜ(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL *, then λ1(L)≤γ * n λ(B) and

.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Babai: On Lovász' lattice reduction and the nearest lattice point problem,Combinatorica,6 (1986), 1–13.

    Google Scholar 

  2. J. W. S. Cassels:An introduction to the geometry of numbers, Springer-Verlag, Berlin,1971.

    Google Scholar 

  3. J. H. Conway, andN. J. A. Sloane:Sphere packings, lattices and groups, Springer-Verlag, New York,1988.

    Google Scholar 

  4. M. Grötschel, L. Lovász, andA. Schrijver:Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin,1988.

    Google Scholar 

  5. P. M. Gruber, andC. G. Lekkerkerker:Geometry of numbers, North-Holland, Amsterdam,1987.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  8. R. Kannan: Minkowski's convex body theorem and integer programming,Math. Oper. Res. 12 (1987), 415–440.

    Google Scholar 

  9. A. Korkine, andG. Zolotareff: Sur les formes quadratiques,Math. Ann. 6 (1873), 366–389.

    Article  MathSciNet  Google Scholar 

  10. J. L.Lagrange: Recherches d'arithmétique,Nouv. Mém. Acad. Berlin (1773), 265–312; ∄uvres, 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.

    Article  Google Scholar 

  12. H. W. Lenstra, Jr.: Integer programming with a fixed number of variables,Math. Oper. Res. 8 (1983), 538–548.

    Google Scholar 

  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.

    Google Scholar 

  14. K. Mahler: A theorem on inhomogeneous diophantine inequalities,Nederl. Akad. Wetensch., Proc. 41 (1938), 634–637.

    Google Scholar 

  15. K.Mahler:The geometry of numbers, duplicated lectures, Boulder, Colorado,1950.

  16. J. Milnor, andD. Husemoller:Symmetric bilinear forms, Springer-Verlag, Berlin,1973.

    Google Scholar 

  17. N. V. Novikova: Korkin-Zolotarev reduction domains of positive quadratic forms inn≤8 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.

    Google Scholar 

  18. C. A. Rogers:Packing and covering, Cambridge University Press, Cambridge,1964.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  21. C. P. Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms,Theoret. Comput. Sci. 53 (1987), 201–224.

    Article  Google Scholar 

  22. B. L. van der Waerden: Die Reduktionstheorie der positiven quadratischen Formen,Acta Math. 96 (1956), 265–309.

    Google Scholar 

  23. B. L. van der Waerden: H. Gross (eds),Studien zur Theorie der quadratischen Formen, BirkhÄuser-Verlag, Basel,1968.

    Google Scholar 

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AT&T Bell Laboratories, Murray Hill, New Jersey, USA

    J. C. Lagarias

  2. Department of Mathematics, University of California, Berkeley, California, USA

    H. W. Lenstra Jr.

  3. UniversitÄt Frankfurt, Frankfurt, F. R. Germany

    C. P. Schnorr

Authors
  1. J. C. Lagarias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. W. Lenstra Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. P. Schnorr
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The research of the second author was supported by NSF contract DMS 87-06176. The research of the third author was performed at the University of California, Berkeley, with support from NSF grant 21823, and at AT&T Bell Laboratories.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lagarias, J.C., Lenstra, H.W. & Schnorr, C.P. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10, 333–348 (1990). https://doi.org/10.1007/BF02128669

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02128669

AMS subject classification (1980)

Search

Navigation