On the number of lattice points in a small sphere and a recursive lattice decoding algorithm

Meyer, Annika

In: Designs, Codes and Cryptography, 2013, vol. 66, no. 1-3, p. 375-390

Aggiungi alla tua lista
    Let L be a lattice in $${\mathbb{R}^n}$$ . This paper provides two methods to obtain upper bounds on the number of points of L contained in a small sphere centered anywhere in $${\mathbb{R}^n}$$ . The first method is based on the observation that if the sphere is sufficiently small then the lattice points contained in the sphere give rise to a spherical code with a certain minimum angle. The second method involves Gaussian measures on L in the sense of Banaszczyk (Math Ann 296:625-635, 1993). Examples where the obtained bounds are optimal include some root lattices in small dimensions and the Leech lattice. We also present a natural decoding algorithm for lattices constructed from lattices of smaller dimension, and apply our results on the number of lattice points in a small sphere to conclude on the performance of this algorithm