On Grünbaum's problem for symmetric configurations

2026/07/24 by Andrii Arman, Andriy Bondarenko, Andriy Prymak +1
#math.MG

paper · pdf

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 ℝⁿ. 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 α₀. Specialized to the two-point case, i.e., for subsets of Boolean cubes, this gives the explicit lower bound g_n≥ (1.160235457…-o(1))ⁿ, improving the previous best bound (2/√3-o(1))ⁿ. 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 α₀ is not attained by any finitely supported distribution.

Related

• Mean width of regular polytopes and expected maxima of correlated Gaussian variables
• Improved Lower Bounds on the Size of Balls over Permutations with the Infinity Metric
• Covering large-dimensional Euclidean spaces by random translates of a given convex body
• Nearly linear lattice coverings of arbitrary convex bodies
• Density estimates for k-impassable lattices of balls and general convex bodies in \Bbb Rⁿ