×

A note on the distribution of the distance from a lattice. (English) Zbl 1163.68040

Summary: Let \(\mathbb L\) be an \(n\)-dimensional lattice, and let \(x\) be a point chosen uniformly from a large ball in \(\mathbb R^{n }\). In this note we consider the distribution of the distance from \(x\) to \(\mathbb L\), normalized by the largest possible such distance (i.e., the covering radius of \(\mathbb L\)). By definition, the support of this distribution is \([0,1]\). We show that there exists a universal constant \(\alpha _{2}\) that provides a natural “threshold” for this distribution in the following sense. For any \(\varepsilon >0\), there exists a \(\delta >0\) such that for any lattice, this distribution has mass at least \(\delta \) on \([\alpha _{2} - \varepsilon ,1]\); moreover, there exist lattices for which the distribution is tightly concentrated around \(\alpha _{2}\) (and so the mass on \([\alpha _{2}+\varepsilon ,1]\) can be arbitrarily small). We also provide several bounds on \(\alpha _{2}\) and its extension to other \(\ell _{p }\) norms. We end with an application from the area of computational complexity. Namely, we show that \(\alpha _{2}\) is exactly the approximation factor of a certain natural \(\mathsf{AM}\) protocol for the Covering Radius Problem.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York (2000) · Zbl 0996.05001
[2] Barnes, E.S.: The covering of space by spheres. Can. J. Math. 8, 293-304 (1956) · Zbl 0072.03603
[3] Barnes, E.S., Sloane, N.J.A.: The optimal lattice quantizer in three dimensions. SIAM J. Algebr. Discrete Methods 4(1), 30-41 (1983) · Zbl 0509.52010 · doi:10.1137/0604005
[4] Boppana, R., Håstad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25, 127-132 (1987) · Zbl 0653.68037 · doi:10.1016/0020-0190(87)90232-8
[5] Conway, J.H., Sloane, N.J.: Sphere Packings, Lattices and Groups, 3rd edn. Springer, Berlin (1998) · Zbl 0917.11027
[6] Durbin, J.: Distribution Theory for Tests Based on the Sample Distribution Function. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia (1973) · Zbl 0267.62002
[7] Forney, G. D., On the duality of coding and quantizing, Piscataway, NJ, 1992, Providence · Zbl 0800.94010
[8] Guruswami, V., Micciancio, D., Regev, O.: The complexity of the covering radius problem on lattices and codes. Comput. Complex. 14(2), 90-121 (2005). Preliminary version in CCC’04 · Zbl 1085.68063 · doi:10.1007/s00037-005-0193-y
[9] Haviv, I., Regev, O.: Hardness of the covering radius problem on lattices. In: Proc. of 21th IEEE Annual Conference on Computational Complexity (CCC) (2006) · Zbl 1286.68192
[10] Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994) · Zbl 0833.68049
[11] Vallentin, F.: Sphere covering, lattices, and tilings (in low dimensions). Ph.D. thesis, Munich University of Technology (2003)
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.