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\in {\mathbb{Z}}_{\ge 2}$ , a
multiple packing is a set $\mathcal{C}$ of points in ${\mathbb{R}}^{n}$ such that
any point in ${\mathbb{R}}^{n}$ lies in the intersection of at most $L-1$ balls
of radius $\sqrt{nN}$ around points in $\mathcal{C}$ . We study this problem
for both bounded point sets whose points have norm at most $\sqrt{nP}$ for some
constant $P>0$ and unbounded point sets whose points are allowed to be anywhere
in ${\mathbb{R}}^{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.

PREPRINT

# Multiple Packing: Lower Bounds via Error Exponents

Yihan Zhang and Shashank Vatedka

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

## Abstract

## Preprint

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