Exponential improvements in Rado's covering problem

Abstract

Let B^d denote the d-dimensional Euclidean ball of unit radius. What is the largest constant f(B^d) ∈ [0,1] with the property that every finite collection 𝒞 of unit balls in ℝ^d admits a disjoint sub-collection 𝒮 occupying at least a fraction f(B^d) of the volume of 𝒞? This problem was first raised by T. Radó in 1928, for axis-parallel squares in the plane; the author was motivated by a classical covering lemma in real analysis due to Vitali. The case of Euclidean balls was first considered by R. Rado in 1949. Until last year the best known estimates on f(B^d) for unit balls where very far apart: (1+ε_d) 3^−d ≤ f(B^d) ≤ 2^−d, where 0<ε_d=o_{d→ ∞}(1). Recently, the authors of this note observed that an exponential improvement on the upper bound follows from the Kabatiansky--Levenshtein spherical code bound, while the lower bound was improved by a linear factor by C.~Xie and G.~Ge (see arxiv:2608.09744). The current best estimates for large d are c · d · 3^−d ≤ f(B^d) ≤ 2.447^−d, where c>0 is an absolute constant. Here we offer the first exponential improvement of the lower bound in almost 80 years, which narrows the gap to: 2.910^−d ≤ f(B^d) ≤ 2.447^−d. Our method is constructive and yields a polynomial time algorithm for finding a disjoint sub-collection realizing the estimate. Moreover the same technique gives similar exponentially improved lower bounds for all symmetric convex bodies satisfying a uniform convexity assumption, e.g., ℓ^p-balls for all p∈ (1,∞).

Fractional illumination and the optimal exponential rate in Hadwiger's covering conjecture
Yegor Gorodzha
arXiv20 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv
On asymptotic Lebesgue's universal covering problem
A. Arman, A. Bondarenko, A. Prymak +1
Bulletin of the London Mathematical Society7 Oct 2026Peer-reviewedCC BY-NCFull textGeometry & topologyHAL
Curves of constant width and Lebesgue's covering problem
Ujjwal Mishra
arXiv1 Sep 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
An Exact Algorithm for the Max-Min Covering Location Blocker Problem
Yun-Tian Zhang, Chen Chen, Fabio Furini +1
arXiv23 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Closed escape path of smallest diameter in forest: dual formulation of Lebesgue's universal covering problem
Zhipeng Deng
arXiv26 Sep 2026PreprintCC BY-NC-ND 4.0Full textGeometry & topology Optimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{dallara2026exponential,
  title = {{Exponential improvements in Rado's covering problem}},
  author = {Gian Maria Dall'Ara and Adrian Dumitrescu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.25288},
  eprint = {2609.25288},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25288},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Exponential improvements in Rado's covering problem
AU  - Gian Maria Dall'Ara
AU  - Adrian Dumitrescu
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2609.25288
UR  - https://arxiv.org/abs/2609.25288
AB  - Let B^d denote the d-dimensional Euclidean ball of unit radius. What is the largest constant f(B^d) ∈ [0,1] with the property that every finite collection 𝒞 of unit balls in ℝ^d admits a disjoint sub-collection 𝒮 occupying at least a fraction f(B^d) of the volume of 𝒞? This problem was first raised by T. Radó in 1928, for axis-parallel squares in the plane; the author was motivated by a classical covering lemma in real analysis due to Vitali. The case of Euclidean balls was first considered by R. Rado in 1949. Until last year the best known estimates on f(B^d) for unit balls where very far apart: (1+ε_d) 3^−d ≤ f(B^d) ≤ 2^−d, where 0<ε_d=o_d→ ∞(1). Recently, the authors of this note observed that an exponential improvement on the upper bound follows from the Kabatiansky--Levenshtein spherical code bound, while the lower bound was improved by a linear factor by C.~Xie and G.~Ge (see arxiv:2608.09744). The current best estimates for large d are c · d · 3^−d ≤ f(B^d) ≤ 2.447^−d, where c>0 is an absolute constant. Here we offer the first exponential improvement of the lower bound in almost 80 years, which narrows the gap to: 2.910^−d ≤ f(B^d) ≤ 2.447^−d. Our method is constructive and yields a polynomial time algorithm for finding a disjoint sub-collection realizing the estimate. Moreover the same technique gives similar exponentially improved lower bounds for all symmetric convex bodies satisfying a uniform convexity assumption, e.g., ℓ^p-balls for all p∈ (1,∞).
ER  -

Abstract

Related

Cite