Relation between the covers by sets of small diameter and the size of uniformly separated sets

Question

Sorry I didn't find a better title. Here is the problem and my solution so far, I'd appreciate if someone could told me if is correct and for the last point, which at first sight seems to be complicated, give me a hint [also, someone knows the name of the functions described below, seems to be very interesting and I'd like to see more about their properties].Thanks in advance.

DEFINITION: Let $(S,d)$ a totally bounded metric space. Given $\epsilon>0$, let $N(\varepsilon, S)$ be the smallest $n$, s.t. $S=\bigcup_{1\le j\le n}A_j$ for some sets with diameter $2\varepsilon$ and $D(\varepsilon,S)$ be the largest number $m$ of points $x_i$ for $i\in \{0\ldots m\}$ s.t. $x_i\not=x_j$ whenever $i\not=j$ .

Show that for any metric space $(S,d)$ and $\varepsilon>0$, $N(\varepsilon,S)\le D(\varepsilon,S)\le N(\varepsilon/2,S)$

Proof: Let $ m=D(\varepsilon,S)$ and $n= N(\varepsilon,S)$ and suppose for sake of contradiction that $m<n$. Let $\mathcal{A}=\{A_1,\ldots A_n\}$ a family of sets such that the diameter for each $A_i$ is at most $2\varepsilon$ and $\bigcup \mathcal{A}=S$. Let $X=\{x_1,\ldots x_m\}$ a set of points for which $d(x_i, x_j)>\varepsilon$ whenever $i\not=j$.

Thus, there must be some $y\in S\setminus X$ such that,$d(x_i,y)>\varepsilon$ for all $i$. If not, for all $y\in S\setminus X$ we have $d(x_i,y)\le\varepsilon$ for some $i$, and for each $x_i$ there is a set in $\mathcal{A}$ containning $x_i$, which we call $A_{x_i}$. Then $\{A_{x_1}\ldots A_{x_m}\}\subsetneqq \mathcal{A}$ and $\bigcup \{A_{x_1}\ldots A_{x_m}\}=S$, contradicting the minimality of $n$. Therefore, we must have a $y\in S\setminus X$ with $d(x_i,y)>\varepsilon$ for all $x_i$, but this yields a contradiction on the maximality of the set of points $m$.

Now suppose $n=N(\varepsilon/2,S)<m=D(\varepsilon,S)$ and let $\mathcal{A}$ similar as above, only we change the diameter of each set in the family to at most $\varepsilon$ and the set $X$ exactly as above. Thus, by the pigeon-hole principle at least one $A_r\in\mathcal{A}$ contains two distinct points $x_i,x_j$ but since $d(x_i,x_j)\le \text{diam} A_r\le \varepsilon$, we have a contradiction.

Hence $N(\varepsilon,S)\le D(\varepsilon,S)\le N(\varepsilon/2,S)$.

Evaluate $N(\varepsilon,S),D(\varepsilon,S)$ in $[0,1]$ for all $\varepsilon>0$

Here where I got stuck, at first seems complicated any hint, please? Nobody?

Answer 1

Your proof of inequalities between $N$ and $D$ is correct.

The evaluation for $[0,1]$ consists of two steps: general argument for an inequality in one direction, and a concrete example showing the inequality in the other direction.

• To get an upper bound on $D(\epsilon,[0,1])$, suppose that $\{x_i\}$ is the set with pairwise distances $>\epsilon$. Order the points as $x_1<x_2<\dots<x_n$. Conclude that $(n-1)\epsilon< x_n-x_1\le 1$.

• For a matching lower bound on $D(\epsilon,[0,1])$, construct an appropriately separated set explicitly.

• To get an upper bound on $N(\epsilon,[0,1])$, construct an eligible cover explicitly

• For a lower bound on $N(\epsilon,[0,1])$, use $N(\epsilon,[0,1])\ge D(2\epsilon,[0,1])$.