Exercise 4.2.5 [HDP Book Vershynin]: Packing the balls into K

Question

Suppose $T$ is a normed space. Prove that packing number $P(K,d,\epsilon)$ of $K \subset T$ is the largest number of closed disjoint balls with centers in $K$ and radii $\epsilon/2$. Show by example that the previous statement may be false for a general metric space $T$.

Def:(Packing numbers). A subset $\cal{N}$ of a metric space $(T,d)$ is $\epsilon$-separated if $d(x,y)>\epsilon$ for all distinct points $x,y\in \cal{N}$. The largest possible cardinality of an $\epsilon$-separated subset of a given set $K\subset T$ is called the packing number of $K$ and is denoted by $P(K,d,\epsilon)$

Proof: Suppose $P(K,d,\epsilon)= n$, so there are $n$ points in $K$ which are $\epsilon$-separated. Each of these $n$ points can be thought as a center of a $\epsilon/2$ radius ball. Then there are $n$ closed disjoint balls of radius $\epsilon/2$, that have their center in K. It remains to show that $n$ is largest number. Assume that there are $n+1$ such $\epsilon/2$ radius closed disjoint balls that have centers in $K$, which implies that $K$ has $n+1$ $\epsilon$-separated points, which is contradictory to the fact that $K$ has a packing number $n$. Hence there can be at-most $n$ such balls.

Doubt: The above proof holds true for any metric space, which is not correct according to the question. Please help.

Answer 1

Let $(T,d)$ be a finite metric space with two elements $T=\{a,b\}$ such that $d(a,b) =\epsilon$ and $K = T$ . Obviously $P(K,d,\epsilon)=1$, since the $\epsilon$-net can be only $\{a\}$ or $\{b\}$. However the number of disjoint closed balls with centers in $K$ and radii $\epsilon/2$ is 2 : one ball is $\{a\}$ and the second $\{b\}$ .

(I hope I'm not missing some subtility )

Answer 2

Popescu Claudiu gave a great counter-example in general metric space.

Now I discussed why your original proof can only work in normed space: notice that the difference between normed space and metric space is that normed space must be a linear space, which means any $a,b \in T$ must have, say, $(a+b)/2 \in T$. But metric space does not need to, just as above counter-example shows.

Thus, for above example, if it is also a normed space then we must have $(a+b)/2 \in T$ and so the Ball $B(a,\epsilon/2)$ and $B(b, \epsilon/2)$ are not disjoint.