Every $2^{−k} r$ -separated set in every ball $B(x , r )$ in $X$ has at most $N^k$ points in a doubling space

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

[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?

• @M W thank for the hints¡ i can conclude the problem Aug 24 at 22:04
• No problem, glad to help.
– M W
Aug 24 at 22:14