arxiv: 2604.17509 · v2 · submitted 2026-04-19 · 🧮 math.MG · cs.DM· math.CA· math.CO

Recognition: unknown

Rado's covering problem for cubes and balls: a semi-survey

Gian Maria Dall'Ara , Adrian Dumitrescu

Authors on Pith no claims yet

Pith reviewed 2026-05-10 05:17 UTC · model grok-4.3

classification 🧮 math.MG cs.DMmath.CAmath.CO

keywords rado covering constanthomothetic copieshigh-dimensional geometrysphere packing boundvitali covering lemmacubesballsdisjoint subcollection

0 comments

The pith

For high-dimensional balls the Rado constant satisfies (1 + ε_d) 3^{-d} ≤ F(B^d) ≤ 2.447^{-d} with ε_d vanishing exponentially, the upper bound coming from sphere-packing density limits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the largest constant F(K) such that any finite collection of homothetic copies of a convex body K always contains a disjoint subcollection whose total volume is at least F(K) times the volume of the union. For d-dimensional cubes the bounds are (e^{-1} + o(1)) 2^{-d} / (d log d) ≤ F(Q^d) ≤ 2^{-d}. For Euclidean balls the estimates tighten to (1 + ε_d) 3^{-d} ≤ F(B^d) ≤ 2.447^{-d}, where the upper bound is obtained by applying the Kabatiansky-Levenshtein sphere-packing upper bound. These exponential decay rates quantify how severely overlap forces one to discard most of the covered volume when selecting a disjoint subfamily in high dimensions. A reader cares because the constants connect a 1928 selection problem directly to classical packing densities and to the efficiency of Vitali-type covering arguments.

Core claim

Rado's covering constant F(K) is defined as the largest c in [0,1] such that every finite collection of homothetic copies of K admits a subfamily with pairwise-disjoint interiors whose total measure is at least c times the measure of the union. For the cube the paper proves (e^{-1} + o(1)) 2^{-d} / (d log d) ≤ F(Q^d) ≤ 2^{-d}. For the ball it proves (1 + ε_d) 3^{-d} ≤ F(B^d) ≤ 2.447^{-d} with ε_d decaying exponentially, the upper bound obtained by transferring the Kabatiansky-Levenshtein sphere-packing density bound.

What carries the argument

The Rado constant F(K), the largest guaranteed fraction of union volume selectable by a disjoint subcollection from any finite homothetic covering by K.

Load-bearing premise

The Kabatiansky-Levenshtein upper bound on sphere-packing density transfers directly to an upper bound on F(B^d) with no extra dimension-dependent losses.

What would settle it

A concrete finite collection of homothetic d-balls, for sufficiently large d, in which the largest volume fraction attainable by any disjoint subcollection is smaller than (1 + ε_d) 3^{-d} would falsify the lower bound; a collection allowing a disjoint subcollection larger than 2.447^{-d} would falsify the upper bound.

Figures

Figures reproduced from arXiv: 2604.17509 by Adrian Dumitrescu, Gian Maria Dall'Ara.

**Figure 1.** Figure 1: Left: a largest square (shaded) and three others that intersect it. Right: four congruent squares sharing a common point. Thus, letting S be the sub-collection of selected cubes, | ∪Q′∈C Q ′ | ≤ | ∪Q∈S 3Q| ≤ X Q∈S |3Q|. Now observe that if a set in R d is dilated by a factor λ > 0, its volume gets multiplied by a factor λ d , so (taking into account the disjointness of S) the rightmost term in the above ch… view at source ↗

**Figure 2.** Figure 2: The family of intervals [0, 1], [2, 3 + ε], [3, 4] on the line, where Rad´o’s strategy outperforms Vitali’s. In his letter to Sierpinski, Rad´o also raises the problem of proving an analogous statement in two dimensions, that is, determining the best possible constant c for which any finite collection C of axis-parallel squares in R 2 admits a disjoint sub-collection S such that (3) | ∪Q∈S Q| ≥ c| ∪Q∈C Q|.… view at source ↗

**Figure 3.** Figure 3: A collection of six squares that are brought into “grid position” by two horizontal and three vertical translations. Note that the independence number of the collection strictly decreases here. The key observation is that the area covered by C(h) is an affine (thus also monotone) function of h, at least for h in the interval [h−, h+], where h+ > 0 is the smallest translation for which a new square becomes … view at source ↗

**Figure 4.** Figure 4: A counterexample obtained from almost-counterexamples A (drawn schematically as four blue rectangles). Let us verify that C is indeed a counterexample. A disjoint sub-collection S of C may contain either one or none of the four unit squares. Let us discuss the two cases separately. If S contains none of the unit squares, then property (1) in the definition of almost-counterexample guarantees that S has de… view at source ↗

**Figure 5.** Figure 5: Left: an almost-counterexample with 52 squares of side 1 and 2. Right: the same almost-counterexample with the vertices of 19 “fictitious” squares of side 2 superimposed (only relevant in the analysis). In order to show property (2), it is enough to prove that, if D contains none of the small bottom squares, then it covers 0% of the area of one of the fictitious squares. We use red to color squares in D an… view at source ↗

**Figure 6.** Figure 6: Case 1 (left) and Case 2 (right) of the analysis. All the unit squares in the bottom row are considered marked. Case 1. The 2 × 2 square in rows 2, 3 and columns 6, 7 is red. We will reach a contradiction in a few forced steps: (i) the unit square in row 2 and column 10 is red. (ii) the 2×2 square in rows 2, 3 and columns 12, 13 is red. (iii) Now 0% of the 2 × 2 fictitious blue square in rows 3, 4 and colu… view at source ↗

read the original abstract

What is the largest constant $c\in [0,1]$ with the property that every finite collection $\mathcal{C}$ of axis-parallel squares in the plane admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $c$ of the area covered by $\mathcal{C}$? This problem was first raised by T.~Rad\'o in 1928, who was motivated by a classical covering lemma in real analysis due to Vitali. R.~Rado later generalized the problem from axis-parallel squares in the plane to homothetic copies of any given convex body $K$ in $\mathbb{R}^d$, where now we are looking for an optimal constant $F(K)$. Our utmost interest is for cubes and balls in the high-dimensional regime $d\rightarrow \infty$. The estimates that we currently have for cubes are much more precise than those for balls: namely if $Q^d$ is a $d$-dimensional cube, then \[ (e^{-1}+o(1))\frac{2^{-d}}{d \log{d}} \leq F(Q^d)\leq 2^{-d}, \] while denoting $B^d$ a $d$-dimensional Euclidean ball, then \[ (1+\epsilon_d)3^{-d}\leq F(B^d)\leq 2.447^{-d}, \] where $\epsilon_d>0$ vanishes exponentially fast as $d\rightarrow \infty$. The latter upper bound is obtained here by using the Kabatiansky--Levenshtein bound for the sphere packing problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The main new item is an upper bound F(B^d) ≤ 2.447^{-d} obtained by importing the Kabatiansky-Levenshtein packing result, but the variable-radius nature of the Rado collections raises a question about direct transfer.

read the letter

The paper's central contribution is the explicit high-dimensional upper bound 2.447^{-d} for the Rado constant on balls, derived from the Kabatiansky-Levenshtein sphere-packing density. For cubes the bounds are already sharper, with the lower estimate of order 2^{-d}/(d log d) and a clean 2^{-d} upper bound. The work also records the lower bound (1 + ε_d) 3^{-d} for balls, with ε_d decaying exponentially. It functions as a semi-survey that pulls together the known estimates and highlights the high-d regime for both shapes. The link between the covering constant and packing density is a reasonable move and appears not to have been written down before in the references given in the abstract. The presentation is straightforward and the constants are concrete, which is helpful for anyone tracking these selection constants. The soft spot is the step that applies the Kabatiansky-Levenshtein bound. That result concerns equal-radius spheres, while Rado's problem for balls permits homothetic copies of arbitrary radii. In low dimensions unequal-radius packings can be denser, so it is not automatic that the same base 2.447 survives without extra factors or a separate argument that the worst-case covering still respects the equal-radius density. The abstract says the bound is obtained here by using the packing result, but the reduction needs to be checked to confirm there are no hidden losses in high dimensions. If the manuscript supplies a clean justification, the claim stands; otherwise the stated rate could be slightly loose. This is material for people working on discrete geometry, Vitali-type covering lemmas, or high-dimensional packing-covering relations. A reader who already knows the classical Rado problem will pick up the updated asymptotics quickly. It is worth sending to peer review because the explicit constants and the packing connection are substantive enough to merit referee scrutiny, even if the transfer argument requires verification.

Referee Report

1 major / 2 minor

Summary. The manuscript is a semi-survey on Rado's covering problem: for a convex body K in R^d, F(K) is the largest c such that any finite collection C of homothetic copies of K admits a disjoint subcollection S whose total measure is at least c times the measure of the union of C. The paper focuses on the high-dimensional asymptotics for cubes Q^d and Euclidean balls B^d. It states the bounds (e^{-1}+o(1)) 2^{-d}/(d log d) ≤ F(Q^d) ≤ 2^{-d} for cubes and (1+ε_d) 3^{-d} ≤ F(B^d) ≤ 2.447^{-d} (ε_d vanishing exponentially) for balls, with the ball upper bound obtained by invoking the Kabatiansky-Levenshtein sphere-packing bound.

Significance. If the transfer of the Kabatiansky-Levenshtein bound is justified, the work supplies the first explicit exponential upper bound on F(B^d) and sharpens the picture of the high-d regime for both cubes and balls. The cube estimates are more refined and include an explicit lower-order factor; the ball lower bound is stated with an exponentially small error term. The manuscript collects prior results and adds the KL-derived upper bound, which would be a useful contribution to geometric set theory if the variable-radius issue is resolved.

major comments (1)

[Abstract / ball upper-bound derivation] Abstract and the section deriving the ball upper bound: the statement that F(B^d) ≤ 2.447^{-d} is obtained from the Kabatiansky-Levenshtein bound requires an explicit reduction. KL applies to packings of congruent spheres, yet the Rado problem permits balls of arbitrary radii. The manuscript must show that the exponential rate survives the passage to variable radii (or cite a suitable extension); without this, the claimed base 2.447 may not hold.

minor comments (2)

[Cube estimates] Clarify whether the cube lower bound is fully self-contained or relies on an external probabilistic argument; add a brief reference to the source of the 1/(d log d) factor.
[Ball lower bound] The notation ε_d is introduced without an explicit decay rate; a short sentence stating the exponential vanishing would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for an explicit justification when applying the Kabatiansky-Levenshtein bound. We respond to the major comment below.

read point-by-point responses

Referee: [Abstract / ball upper-bound derivation] Abstract and the section deriving the ball upper bound: the statement that F(B^d) ≤ 2.447^{-d} is obtained from the Kabatiansky-Levenshtein bound requires an explicit reduction. KL applies to packings of congruent spheres, yet the Rado problem permits balls of arbitrary radii. The manuscript must show that the exponential rate survives the passage to variable radii (or cite a suitable extension); without this, the claimed base 2.447 may not hold.

Authors: We agree that the manuscript invokes the Kabatiansky-Levenshtein bound to derive the upper estimate F(B^d) ≤ 2.447^{-d} without supplying an explicit reduction from the congruent-sphere case to the variable-radius setting permitted by the definition of F(B^d). The current text states the bound but does not detail why the exponential rate carries over. We will revise the relevant section (and update the abstract if necessary) to include a self-contained argument showing that the exponential upper bound remains valid when arbitrary radii are allowed. This revision will either provide a direct reduction (e.g., by normalizing radii or by a limiting procedure that preserves the worst-case ratio) or cite an appropriate extension of the sphere-packing bound. We view this as a necessary clarification that strengthens the paper. revision: yes

Circularity Check

0 steps flagged

No circularity: upper bound on F(B^d) imported from independent external theorem

full rationale

The paper states that the upper bound F(B^d) ≤ 2.447^{-d} is obtained by applying the Kabatiansky-Levenshtein sphere-packing bound, an externally established result by different authors. No self-definitional loops, fitted inputs renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work by the same authors appear in the derivation. The lower bound (1+ε_d)3^{-d} and all cube estimates are likewise presented without internal reduction to the paper's own fitted quantities or definitions. The argument remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard Euclidean geometry, Lebesgue measure, and prior results on sphere packing and covering; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard axioms of Euclidean space and Lebesgue measure theory
Invoked to define areas, homotheties, and the covering constant F(K).

pith-pipeline@v0.9.0 · 5588 in / 1384 out tokens · 63718 ms · 2026-05-10T05:17:43.540303+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

31 extracted references · 3 canonical work pages

[1]

Ajtai, The solution of a problem of T

M. Ajtai, The solution of a problem of T. Rad´ o,Bulletin de l’Acad´ emie Polonaise des Sciences, S´ erie des Sciences Math´ ematiques, Astronomiques et Physiques21(1973), 61–63

1973
[2]

Bereg, A

S. Bereg, A. Dumitrescu, and M. Jiang, Maximum area independent sets in disk intersection graphs,International Journal of Computational Geometry & Applications20(2)(2010), 105–118

2010
[3]

Bereg, A

S. Bereg, A. Dumitrescu, and M. Jiang, On covering problems of Rado,Algorithmica57(3)(2010), 538-561

2010
[4]

H. F. Blichfeldt, A new principle in the geometry of numbers, with some applications,Transactions of the American Mathematical Society15(3)(1914), 227–235

1914
[5]

Y. D. Burago and V. A. Zalgaller,Geometric Inequalities, Springer, New York, 1988

1988
[6]

J. H. Conway and N. J. A. Sloane,Sphere Packings, Lattices and Groups, third edition, Grundlehren der math- ematischen Wissenschaften, 290, Springer, New York, 1999

1999
[7]

T. M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects,Journal of Algorithms 46(2)(2003), 178–189

2003
[8]

Campos, M

M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe, A new lower bound for sphere packing, preprint, 2023,arXiv.org/abs/2312.10026

work page arXiv 2023
[9]

Cohn and Y

H. Cohn and Y. Zhao, Sphere packing bounds via spherical codes,Duke Mathematical Journal163(10)(2014), 1965–2002

2014
[10]

H. T. Croft, K. Falconer, and R. K. Guy,Unsolved Problems in Intuitive Mathematics vol. 2: Unsolved Problems in Geometry, Springer Science & Business Media (1991)

1991
[11]

Dall’Ara, On the best constant in the finitary Vitali covering lemma for high dimensional cubes, preprint, 2025,arXiv.org/abs/2510.06817

G. Dall’Ara, On the best constant in the finitary Vitali covering lemma for high dimensional cubes, preprint, 2025,arXiv.org/abs/2510.06817

work page arXiv 2025
[12]

Davenport and G

H. Davenport and G. Haj´ os, Problem 35 (in Hungarian),Matematikai Lapok2(1951), 68

1951
[13]

Erlebach, K

T. Erlebach, K. Jansen, and E. Seidel, Polynomial-time approximation schemes for geometric intersection graphs, SIAM Journal on Computing,34(6)(2005), 1302–1323

2005
[14]

Hadwiger and H

H. Hadwiger and H. Debrunner,Combinatorial Geometry in the Plane(English translation by Victor Klee), Holt, Rinehart and Winston, New York, 1964

1964
[15]

Helly, ¨Uber Mengen konvexer K¨ orper mit gemeinschaftlichen Punkten,Jahresbericht der Deutschen Mathematiker-Vereinigung32(1923), 175–176

E. Helly, ¨Uber Mengen konvexer K¨ orper mit gemeinschaftlichen Punkten,Jahresbericht der Deutschen Mathematiker-Vereinigung32(1923), 175–176

1923
[16]

H. W. E. Jung, ¨Uber die kleinste Kugel die eine r¨ aumliche Figur einschliesst,Journal f¨ ur die reine und angewandte Mathematik (Crelles Journal),123(1901), 241–257. 16

1901
[17]

G. A. Kabatiansky and V. I. Levenshtein, Bounds for packings on a sphere and in space,Problems of Information Transmission14(1)(1978), 1–17

1978
[18]

Klartag, Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid, preprint, 2025, arXiv.org/abs/2504.05042

B. Klartag, Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid, preprint, 2025, arXiv.org/abs/2504.05042

work page arXiv 2025
[19]

Krivelevich, S

M. Krivelevich, S. Litsyn, and A. Vardy, A lower bound on the density of sphere packings via graph theory, International Mathematics Research Notices43(2004), 2271–2279

2004
[20]

W. A. Kuperberg, Optimal arrangements in packing congruent balls in a spherical container,Discrete and Computational Geometry37(2007), 205–212

2007
[21]

Nordlander, Ett ¨ overt¨ ackningsproblem,Nordisk Matematisk Tidskrift6(1958), no

G. Nordlander, Ett ¨ overt¨ ackningsproblem,Nordisk Matematisk Tidskrift6(1958), no. 1, 29–31 (In Swedish.)

1958
[22]

Rad´ o, Sur un probl` eme relatif ` a un th´ eor` eme de Vitali,Fundamenta Mathematicae11(1928), 228–229 (In French.)

T. Rad´ o, Sur un probl` eme relatif ` a un th´ eor` eme de Vitali,Fundamenta Mathematicae11(1928), 228–229 (In French.)

1928
[23]

Rado, Some covering theorems (I),Proceedings of the London Mathematical Society(2)51(1949), 232–264

R. Rado, Some covering theorems (I),Proceedings of the London Mathematical Society(2)51(1949), 232–264

1949
[24]

R. Rado. Some covering theorems (II).Proceedings of the London Mathematical Society(2)53(1951), 243–267

1951
[25]

Rado, Some covering theorems (III),Journal of the London Mathematical Society(1)43(1968), 127–130

R. Rado, Some covering theorems (III),Journal of the London Mathematical Society(1)43(1968), 127–130

1968
[26]

R. A. Rankin, The closest packing of spherical caps inndimensions,Glasgow Mathematical Journal2(3)(1955), 139–144

1955
[27]

Rudin,Real and Complex Analysis, 3rd edition, McGraw-Hill Book Co., New York, (1987)

W. Rudin,Real and Complex Analysis, 3rd edition, McGraw-Hill Book Co., New York, (1987)

1987
[28]

A. S. Sokolin, Concerning a problem of Rad´ o,Doklady Akademii Nauk SSSR26(1940), 871–872, (In Russian.)

1940
[29]

Vitali, Sui gruppi di punti e sulle funzioni di variabili reali,Atti dell’Accademia delle Scienze di Torino43 (1908), 229–246 (In Italian.)

G. Vitali, Sui gruppi di punti e sulle funzioni di variabili reali,Atti dell’Accademia delle Scienze di Torino43 (1908), 229–246 (In Italian.)

1908
[30]

Covering problem of Rado.Wikipedia, The Free Encyclopedia.https://en.wikipedia

Wikipedia contributors. Covering problem of Rado.Wikipedia, The Free Encyclopedia.https://en.wikipedia. org/w/index.php?title=Covering_problem_of_Rado&oldid=1322896164; accessed 26-February-2026

2026
[31]

F. Severi

V. A. Zalgaller, Remarks on Rad´ o’s problem,Matematicheskoe Prosveshchenie, Ser. 2,5(1960), 141–148, (In Russian.) Gian Maria Dall’Ara Istituto Nazionale di Alta Matematica “F. Severi” and Scuola Normale Superiore, Pisa, Italy Email address:dallara@altamatematica.it Adrian Dumitrescu Algoresearch L.L.C., Milwaukee, WI, USA, and Research Institute of the ...

1960