zbMATH — the first resource for mathematics

Dual vectors and lower bounds for the nearest lattice point problem. (English) Zbl 0653.10026
Let \(L\) be a lattice in \(\mathbb R^ n\) and let \(L^*\) be its dual. The author shows that for each \(x\in\mathbb R^ n\setminus L\) there exists a nonzero \(v\in L^*\) such that \[ \frac{| \{(x,v)\}|}{\| v\|}\geq c_ n\cdot d(x,L), \] where \((x,v)\) is the usual inner product on \(\mathbb R^ n,\) \(\{\alpha\}\) the minimal distance of \(\alpha\) to an integer, \(d(x,L)\) is the distance from \(x\) to \(L\) and \(c_ n\geq (6n^ 2+1)^{-1}.\) The proof is not constructible. The best known constructible proof gives a value \(c_ n\geq 9^{-n}.\)
Reviewer: F. van der Linden

11H99 Geometry of numbers
11H31 Lattice packing and covering (number-theoretic aspects)
68R05 Combinatorics in computer science
Full Text: DOI
[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, Heidelberg 1971. · Zbl 0209.34401
[3] P.Van Emde Boas, AnotherNP-complete problem and the complexity of computing short vectors in a lattice,Math. Dept. Report 81-04. Univ. of Amsterdam, April 1981.
[4] R.Kannan, Minkowski’s convex body theorem and integer programming,to appear in Mathematics of Operations Research. · Zbl 0639.90069
[5] A. I.Khinchin, A quantitative formulation of Kronecker’s theory of approximation,Inv. Akad. Nauk. SSSR (ser. Mat),12 113–122 (in russian). · Zbl 0030.02002
[6] A. Korkine andG. Zolotarev, Sur les formes quadratiques,Mathematiche Annalen,6 (1973), 366–389. · JFM 05.0109.01 · doi:10.1007/BF01442795
[7] J. C.Lagarias, H. W.Lenstra and C. P.Schnorr, Korkine-Zolotarev bases and the successive minima of a lattice and its reciprocal lattice,to appear in Combinatorica. · Zbl 0723.11029
[8] A. K. Lenstra, H. W. Lenstra andL. Lovász, Factoring polynomials withrational coefficients,Math. Ann. 261 (1982), 515–534. · Zbl 0488.12001 · doi:10.1007/BF01457454
[9] L.Lovász,personal communication.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.