## 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 language | English (US) |
---|---|

Pages (from-to) | 162-176 |

Number of pages | 15 |

Journal | Discrete and Computational Geometry |

Volume | 41 |

Issue number | 1 |

DOIs | |

State | Published - 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