2025/10/29 by Bukh, Boris, Gao, Jun, Liu, Xizhi +2 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.2510.25685
Determining the minimum density of a covering of ℝn by Euclidean unit balls as n→∞ is a major open problem, with the best known results being the lower bound of (e-3/2+o(1))n by Coxeter, Few and Rogers [Mathematika 6, 1959] and the upper bound of (1/2+o(1) )n ln n by Dumer [Discrete Comput. Geom. 38, 2007]. We prove that there are ball coverings of ℝn attaining the asymptotically best known density (1/2+o(1) )n ln n such that, additionally, every point of ℝn is covered at most (1.79556... + o(1)) n ln n times. This strengthens the result of Erdős and Rogers [Acta Arith. 7, 1961/62] who had the maximum multiplicity at most (e + o(1)) n ln n. On the other hand, we show that the method that was used for the best known ball coverings (when one takes a random subset of centres in a fundamental domain of a suitable lattice in ℝn and extends this periodically) fails to work if the density is less than (1/2+o(1))nln n; in fact, this result remains true if we replace the ball by any convex body K. Also, we observe that a ``worst'' convex body K here is a cube, for which the packing density coming from random constructions is only (1+o(1))nln n.