2022/11/08 by Zhang, Yihan, Vatedka, Shashank
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2211.04408
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 L∈ℤ≥2 , a multiple packing is a set C of points in ℝn such that any point in ℝn lies in the intersection of at most L-1 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 ℝn . 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.