The doubling dimension of a metric space $X$ is the smallest positive integer $k$ such that every ball of $X$ can be covered by $2^k$ balls of half the radius.

It is well known that the doubling dimension $d(n)$ of the Euclidean space $\mathbb R^n$ is $O(n)$, which means that there is a constant $C$ such that for large $n$ one has $d(n)\leq Cn$. A posteriori, I can find a new constant $D$ that works for all $n$. I would like to have an explicit description of this new constant. In other words,

Question: What explicit and possibly nice and small constant $D>0$ would guarantee that $d(n)\leq Dn$, for all $n$?

Edit. As observed by Igor Rivin, $D=\log 2$ should be good for $n\geq7$, by a theorem of Verger-Gaugry. Any idea for all $n$? I have to clarify that at the moment I am not interested in the best possible constant, but in some good-looking constant, something to make aesthetically pleasant a certain formula that I found out.

Thank you in advance,


  • $\begingroup$ Just as a side remark: afaik $d(1)=2$ and $d(2)=7$, hence $D \geq 3.5$ $\endgroup$ – cubic lettuce Feb 21 '15 at 23:34

As shown in this paper,Theorem 1.2, $D \leq \log 2.$ I remark that this paper came up in my answer to this question, and there is a bug for small $n$ ($n < 7$), but the author's interest was apparently similar to yours, so the large $n$ results should be correct. (the paper is: "Covering a Ball with Smaller Equal Balls in $\mathbb{R}^n," by Jean-Louis Verger-Gaugry)

  • $\begingroup$ Thank you very much. What can we say for small $n$? I am really interested in all values of $n$. Maybe also to know that say $D=2$ is good enough would be OK. Indeed, for the moment I want to put this constant in a as nice as possible formula for all $n$ and then maybe discuss the fact that can be sharpened for $n\geq7$... $\endgroup$ – Valerio Capraro Jun 27 '12 at 14:23
  • $\begingroup$ I am having a look at the paper and maybe I am missing something. He fixes a radius $T>\frac12$ and answers the question of how many balls of radius $\frac12$ are needed to cover a ball of radius $T$. My case is little different, because the covering balls have radius $T/2$. Well, it is possible that one can go down inductively and apply that formula, but I am little in trouble with that terrible formula. Moreover, that formula holds only for $T\leq\frac{n}{2\log(n)}$... In two words: I'm confused! $\endgroup$ – Valerio Capraro Jun 27 '12 at 14:40
  • $\begingroup$ For your problem $T=1,$ and the inequality is vacuously satisfied... $\endgroup$ – Igor Rivin Jun 27 '12 at 15:15
  • $\begingroup$ I am sorry, but I cannot understand how you get $\log 2$. Indeed, let $f(n)$ be Verger-Gaugry's estimation in Theorem 1.2 but without $2^n$. It seems to me that $d$ should verify the property that $\log_2(f(n))\leq(d-1)n$, for all $n$. One can easily see that every $d>1$ is eventually good, but the function $f(n)$ diverges and then it seems to me impossible to find a constant $d\leq1$. Am I missing something? $\endgroup$ – Valerio Capraro Jun 30 '12 at 16:48

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.