23
$\begingroup$

If $N \geq 3$, why can we cover $\mathbb R^N$ with open balls of a fixed radius $r$ such that each point is in at most $N + 1$ balls?

This is a claim in a proof of Lions' Vanishing Lemma, as presented in Willem's Minimax Theorems (Lemma 1.21). Probably very simple but I am not able to write a proper proof.

$\endgroup$
26
  • 2
    $\begingroup$ @PaulFrost Doesn't matter - the two versions of the result are trivially equivalent. $\endgroup$ – David C. Ullrich Aug 1 '20 at 18:06
  • 2
    $\begingroup$ @DaniloGregorin: No. The centres of $3$ balls are coplanar, so imagine the balls resting on a flat surface. You can rest a fourth ball in the hollow that they form, and there will be a volume immediately below it that is not covered by any of the four. It’s fairly clear intuitively that there is no way to cover that volume without using a ball that intersects all $3$ of the original balls. $\endgroup$ – Brian M. Scott Aug 1 '20 at 18:42
  • 2
    $\begingroup$ @DavidC.Ullrich Equivalent - yes. Trivially? $\endgroup$ – Paul Frost Aug 1 '20 at 23:55
  • 3
    $\begingroup$ @DavidC.Ullrich Doubling the radius could increase the number of balls intersecting at some points. Even adding a small $\epsilon$ to the radius may not work, if there's no lower bound on the pairwise distances between non-intersecting closed balls. $\endgroup$ – aschepler Aug 2 '20 at 14:03
  • 4
    $\begingroup$ @DCao But regular simplices don't tesselate in $\mathbb{R}^n$ when $n>2$. (math.stackexchange.com/a/3087543/2236) $\endgroup$ – aschepler Aug 3 '20 at 23:45
5
+100
$\begingroup$

user125932 mentioned in a comment that this seems to be an open problem, since it would imply that the covering density of any $n$-dimensional ball is at most $n+1$. As of 2018, it still seems that nobody can prove a better upper bound on that covering density than $Θ( n · \log n )$; see here and here. In particular, the first linked paper explicitly states that as $n→∞$, unit balls can cover $\mathbb{R}^n$ with density $\big(\frac12+o(1)\big)\ n\ln n$, as Corollary 2.

$\endgroup$
4
  • $\begingroup$ I think that you are answering a different question. If I understood correctly, OP asks about the maximal number of balls at any given point, while your answer treats the question of the average number of balls at a given point, and the latter number is obviously smaller than the former. $\endgroup$ – Louis Hainaut Aug 13 '20 at 8:36
  • 3
    $\begingroup$ @LouisHainaut: But that inequality is obviously enough to demonstrate that the question is an open problem, which is exactly what I stated in my post. (I said nothing about the maximum depth of the covering.) $\endgroup$ – user21820 Aug 13 '20 at 9:03
  • 3
    $\begingroup$ for those that are interested, it is known that a covering exists in which every point is contained in at most $O(n \log n)$ balls -- this was proved by Erdős and Rogers here, refining Rogers' $O(n \log n)$ upper bound on the covering density. $\endgroup$ – user125932 Aug 14 '20 at 6:29
  • $\begingroup$ @user125932: Nice, thanks for your comment! $\endgroup$ – user21820 Aug 14 '20 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.