Multiple Packing: Lower Bounds via Error Exponents

Yihan Zhang and Shashank Vatedka

Submitted on 8 November 2022, last revised on 9 November 2022


We derive lower bounds on the maximal rates for multiple packings in high-dimensional Euclidean spaces. Multiple packing is a natural generalization of the sphere packing problem. For any N>0 and LZ2, a multiple packing is a set C of points in Rn such that any point in Rn lies in the intersection of at most L1 balls of radius nN around points in C. We study this problem for both bounded point sets whose points have norm at most nP for some constant P>0 and unbounded point sets whose points are allowed to be anywhere in Rn. Given a well-known connection with coding theory, multiple packings can be viewed as the Euclidean analog of list-decodable codes, which are well-studied for finite fields. We derive the best known lower bounds on the optimal multiple packing density. This is accomplished by establishing a curious inequality which relates the list-decoding error exponent for additive white Gaussian noise channels, a quantity of average-case nature, to the list-decoding radius, a quantity of worst-case nature. We also derive various bounds on the list-decoding error exponent in both bounded and unbounded settings which are of independent interest beyond multiple packing.


Comment: The paper arXiv:2107.05161 has been split into three parts with new results added and significant revision. This paper is one of the three parts. The other two are arXiv:2211.04407 and arXiv:2211.04406

Subjects: Mathematics - Metric Geometry; Computer Science - Information Theory