12
$\begingroup$

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,

Valerio

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

1 Answer 1

10
$\begingroup$

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)

$\endgroup$
4
  • $\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$ Jun 27, 2012 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$ Jun 27, 2012 at 14:40
  • $\begingroup$ For your problem $T=1,$ and the inequality is vacuously satisfied... $\endgroup$
    – Igor Rivin
    Jun 27, 2012 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$ Jun 30, 2012 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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