Welcome to MathOverflow

Question

6

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

edited Jun 28 at 17:08

asked Jun 27 at 13:54

Valerio Capraro
3,595●11●25

Igor Rivin · Answer 1 · 2012-06-27 14:04:25Z UTC

4

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)

answered Jun 27 at 14:04

Igor Rivin
31.2k●3●37●71

	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$... – Valerio Capraro Jun 27 at 14:23
	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! – Valerio Capraro Jun 27 at 14:40
	For your problem $T=1,$ and the inequality is vacuously satisfied... – Igor Rivin Jun 27 at 15:15
	Yes, indeed! thanks again – Valerio Capraro Jun 27 at 15:33
	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? – Valerio Capraro Jun 30 at 16:48

Doubling dimension of a Euclidean space

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.