A note on the distribution of the distance from a lattice

Ishay Haviv, Vadim Lyubashevsky, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Pages (from-to)162-176
Number of pages15
JournalDiscrete and Computational Geometry
Volume41
Issue number1
DOIs
StatePublished - Jan 2009

Keywords

  • Computational complexity
  • Covering radius
  • Geometrical invariants
  • Lattices
  • Second moment

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A note on the distribution of the distance from a lattice'. Together they form a unique fingerprint.

Cite this