Let $X$ be a doubling metric space with constant $N$ and let $k \geq 1$ be an integer. Then every $2^{−k} r$ -separated set in every ball $B(x , r )$ in $X$ has at most $N^k$ points.

Let $S$ be a maximal $2^{-k}$ separated subset of a $B(x,r)$ then $B(x,r) \subset \cup_{y \in S} B(y, \frac{r}{2^k})$ for the maximality, now i try to use the doubling condition of the meric space but i cant conclude, any hint or help i will be very grateful


1 Answer 1


[Update, I have corrected the note on closed vs open balls. The balls in this problem do NOT have to be open, they can be closed as well.]

I believe this theorem is off by a factor of $2$, and should be asking you to prove every $2^{1-k}r$-separated set has at most $N^k$ points. In $\mathbb R$ with doubling constant $2$, a $\frac{1}{2}$-separated set in B(0,1)=[-1,1] can have cardinality at most $4$. Here I assume strict inequality in the definition of $r$-separated.

[Note that I am assuming the balls in this problem and in the definition of the doubling constant to be closed. But regardless of opened or closed, the problem as stated fails in $\mathbb R$ if the exponent is $-k$.]

Some hints for how to proceed:

Hint 1: Firstly, there is no need to take a maximal $2^{1-k}r$ separated set - you are proving the result for arbitrary $2^{1-k}r$ separated sets. So let $S$ be an arbitrary such set.

Hint 2: Do NOT use $S$ as the set of centers for the balls. Instead use the doubling property to make your own collection of balls.

Hint 3: More precisely, you're going to want to use the doubling property $n$ times in a row, first to cover $B(x,r)$ with balls of radius $\frac{r}{2}$, then to cover those balls with balls of radius $\frac{r}{4}$, etc.

Hint 4: After you you get a covering of balls of radius $\frac{r}{2^{k}}$, how many times can $S$ intersect each of those balls?

  • $\begingroup$ @M W thank for the hints¡ i can conclude the problem $\endgroup$
    – Nick Weber
    Aug 24 at 22:04
  • 1
    $\begingroup$ No problem, glad to help. $\endgroup$
    – M W
    Aug 24 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .