On Grünbaum's problem for symmetric configurations

Abstract

Let $g_n$ be the largest number of Euclidean balls of diameter $1$ which may be needed to cover a set of diameter $1$ in ${\mathbb{R}}^n$. We study this problem for finite sets invariant under all coordinate permutations. We prove that the exponential growth rate in this symmetric problem can be characterized exactly as a finite-alphabet squared-error rate-distortion supremum $\hat{I}{\pm }_0$. Specialized to the two-point case, i.e., for subsets of Boolean cubes, this gives the explicit lower bound \[g_n\ge (1.160235457\ldots-o(1))^n,\] improving the previous best bound $(2/\sqrt{3}-o(1){)}^n$. Using Fix's Gaussian characterization of the rate-distortion problem, we give a numerical three-point construction with exponent base greater than $1.160497831$. Finally, we show that $\hat{I}{\pm }_0$ is not attained by any finitely supported distribution.

15 pages