Basic question on 'bounded implies totally bounded'

[psie]

TL;DR Summary

I am reading a proof of the fact that if $E\subset\mathbb R^n$ is bounded, then it is totally bounded. This proof is from Gamelin's and Greene's book on topology. I have a question about the proof.

Recall, a set $X$ is totally bounded if for each $\epsilon>0$, there exists a finite number of open balls of radius $\epsilon>0$ that cover $X$.

Proof: Since $E$ is bounded, it is contained in some cube $T=[-b,b]^n$ and it suffices to show that $T$ is totally bounded since a subspace of a totally bounded metric space is totally bounded. For this, let $\epsilon>0$. Then the balls $B(\epsilon j,\epsilon)$ cover $T$, where $j=(j_1,\ldots,j_n)$ ranges over all integral lattice points of $\mathbb R^n$ which satisfy $\epsilon |j_i|\leq 2b$, $1\leq i\leq n$ (recall, an integral lattice point is a point whose coordinates are integers). Since there are only finitely many such lattice points, $T$ is totally bounded.

Question: How can I verify that the balls $B(\epsilon j,\epsilon)$ cover $T$? In particular, why the condition $\epsilon |j_i|\leq 2b$, $1\leq i\leq n$?

 

[PeroK]

TL;DR Summary: I am reading a proof of the fact that if $E\subset\mathbb R^n$ is bounded, then it is totally bounded. This proof is from Gamelin's and Greene's book on topology. I have a question about the proof.

Recall, a set $X$ is totally bounded if for each $\epsilon>0$, there exists a finite number of open balls of radius $\epsilon>0$ that cover $X$.



Question: How can I verify that the balls $B(\epsilon j,\epsilon)$ cover $T$? In particular, why the condition $\epsilon |j_i|\leq 2b$, $1\leq i\leq n$?

Why not work through an example for $n =2$ and $b = 1$.

 

[psie]

Why not work through an example for $n =2$ and $b = 1$.

I have tried, but I don't see how to generalize. The condition $\epsilon j_i\in [-2b,2b]$ is kind of clear; if $n=1$ and $T=[-5,5]$, it does not suffice to cover $T$ by open balls of radius $1/3$ centered at the points $-5,-4,\ldots,4,5$. We need more points to center at.

Here's my reasoning so far: if $x\in T$, then $x_i\in [-b,b]$ for $1\leq i\leq n$. Let $j\in \mathbb R^n$ satisfy $\epsilon j_i\in [-2b,2b]$ for $1\leq i\leq n$. Now I want to show $d(x,\epsilon j)<\epsilon$, but I am not sure how to do that. I suspect one would like to consider a third point and use the triangle inequality somehow. I am not sure.

 

[PeroK]

I must admit I don't see that works. I reckon you need the lattice points for each coordinate to be $\frac{\epsilon}{\sqrt n}$ apart.

 

[mathwonk]

it looks to me as if 2b should be just b (assuming b is an integer, which you can do). I.e. one can cover the cube by balls of unit radius centered at the integral lattice points within the (closed) cube. This is essentially the general case. I.e. similarly one can cover the cube by balls of radius 1/3 centered at points in the cube which are 1/3 of integer lattice points.... one can cover the cube by balls of radius e, centered at points within the cube which are e times an integer lattice point.

in post #3, you need also points centered at ±1/3, ±2/3,....,±15/3. i.e. all j such that (1/3)j ≤ 5.

Based on this example, I would suggest choosing another book.

 

[PeroK]

it looks to me as if 2b should be just b (assuming b is an integer, which you can do). I.e. one can cover the cube by balls of unit radius centered at the integral lattice points within the (closed) cube. This is essentially the general case. I.e. similarly one can cover the cube by balls of radius 1/3 centered at points in the cube which are 1/3 of integer lattice points.... one can cover the cube by balls of radius e, centered at points within the cube which are e times an integer lattice point.

in post #3, you need also points centered at ±1/3, ±2/3,....,±15/3. i.e. all j such that (1/3)j ≤ 5.

Based on this example, I would suggest choosing another book.

Doesn't that factor of 3 increase with the dimension $n$?

 

[mathwonk]

I don't think so. in dim 2, you need balls centered at (0,0), (±1/3,±1/3), (±1/3,±2/3), (±2/3,±1/3), (±2/3,±2/3), ....

all you are doing is marking off new lattice points in the unit cube, at every point of form (j/m,.....,k/m). so when e = 1/m, you would have I guess, 1 + m^n such points in the cube [0,1]^n.

He also makes it more confusing by using negative numbers. One can translate any bounded set into an expansion of [0,1]^n.

Basically he is making an easy argument hard. Just note that unit radius balls, centered at integer lattice points, cover [0,C]^n, for any integer C, and then just scale that down by multiplying by e, where C = b/e.

oops, now I see why maybe he used 2b. If e is not of form 1/m, we want to be sure our scaled down lattice points do cover the cube [0,b]^n.

maybe I'm wrong, but I would just blow up the cube [0,b]^n, by dividing by 1/e, i.e. to [0,b/e]^n. Then choose an integer m ≥ b/e, and cover the cube [0,m]^n, hence also the blown up cube [0,b/e]^n, by unit radius balls centered at integer lattice points. Then shrink everything down again by multiplying by e, to get the original cube [0,b]^n covered by balls of radius e, centered at points with coordinates of form ej, where j is an integer.

(of course it suffices to assume e = 1/k, for some integer k, so we may in fact assume b/e is itself an integer.)

does that seem ok?

 

[PeroK]

I don't think so. in dim 2, you need balls centered at (0,0), (±1/3,±1/3), (±1/3,±2/3), (±2/3,±1/3), (±2/3,±2/3), ....

I was looking at a simple approach, where for every $x$ we can find a point $l$ in the lattice, such that:
$$\forall i: |x_i - l_i| \le \frac s 2$$Where $s$ is the linear lattice spacing. Then:
$$|x - l| = \sqrt{\sum_{i = 1}^n (x_i - l_i)^2} \le \frac s 2 \sqrt n$$In fact, it seems that for any lattice, we can always find $x$ where we have equality. That suggests to me that we need the linear spacing to depend on $n$.

 

[mathwonk]

perhaps I am ignoring the fact that the diagonal of a cube goes up with n?

I think you are right. so there are two steps perhaps. one, show that for every e>0, there is some k such that the cube of radius 1/k is inscribed in a ball of radius e. two, then show that every cube of edge length b can be subdivided into small cubes of edge length 1/k.

these are both easy, but apparently also easy to get wrong, at least for me. I just eyeballed it for n=2, where 1+1 > sqrt(n).

thank you!

(or just finesse step one by using the "max norm", so that ball becomes a cube.)

 

[mathwonk]

so I think I finally see it, and of course it is what you said all along.

1). it suffices to consider just the unit cube [0,1]^n, since every cube can be covered by finitely many copies of that one.

2). for every integer k, we can subdivide the unit cube into finitely many (k^n) subcubes of edge length 1/k.

3). Since the sub cube of edge length 1/k has diagonal sqrt(n)/k, we can cover that subcube by one open euclidean ball of radius sqrt(n)/k, centered at the center of the sub cube, so as long as we choose k large enough so that sqrt(n)/k < e, i.e. so that k > sqrt(n)/e, we are done.

i.e. as you said in post #4, we want edge length 1/k < e/sqrt(n).

 

[psie]

so I think I finally see it, and of course it is what you said all along.

1). it suffices to consider just the unit cube [0,1]^n, since every cube can be covered by finitely many copies of that one.

2). for every integer k, we can subdivide the unit cube into finitely many (k^n) subcubes of edge length 1/k.

3). Since the sub cube of edge length 1/k has diagonal sqrt(n)/k, we can cover that subcube by one open euclidean ball of radius sqrt(n)/k, centered at the center of the sub cube, so as long as we choose k large enough so that sqrt(n)/k < e, i.e. so that k > sqrt(n)/e, we are done.

i.e. as you said in post #4, we want edge length 1/k < e/sqrt(n).

I appreciate your solution, but how would one amend the intended proof?

Clearly the balls $B(\epsilon j,\epsilon)$ do not cover $T$. Given $\epsilon > 0$, the vector $\frac{\epsilon}{2}(1, 1,\ldots, 1)$ will be a distance $\geq \sqrt{n}\frac{\epsilon}{2}$ away from each vector of the form $\epsilon j$ where $j$ is a point on the integer lattice. So for $n\geq 4$ it won't belong to any ball of the form $B(\epsilon j, \epsilon)$.

Would the balls $B(\frac{\varepsilon j}{\sqrt{n}}, \varepsilon)$ work? Why? How would the condition $\varepsilon |j_i|\leq 2b$ be changed?

 

[mathwonk]

forgive me, I have mostly lost interest in grading gamelins homework. but I would say you should change e|ji| to e|ji|/(sqrt(n), and assume e<1 and b an integer.

 

[PeroK]

I appreciate your solution, but how would one amend the intended proof?

Clearly the balls $B(\epsilon j,\epsilon)$ do not cover $T$. Given $\epsilon > 0$, the vector $\frac{\epsilon}{2}(1, 1,\ldots, 1)$ will be a distance $\geq \sqrt{n}\frac{\epsilon}{2}$ away from each vector of the form $\epsilon j$ where $j$ is a point on the integer lattice. So for $n\geq 4$ it won't belong to any ball of the form $B(\epsilon j, \epsilon)$.

Would the balls $B(\frac{\varepsilon j}{\sqrt{n}}, \varepsilon)$ work? Why? How would the condition $\varepsilon |j_i|\leq 2b$ be changed?

In this case, I think you should have focused on getting the required inequality first. That is:

I was looking at a simple approach, where for every $x$ we can find a point $l$ in the lattice, such that:
$$\forall i: |x_i - l_i| \le \frac s 2$$Where $s$ is the linear lattice spacing. Then:
$$|x - l| = \sqrt{\sum_{i = 1}^n (x_i - l_i)^2} \le \frac s 2 \sqrt n$$In fact, it seems that for any lattice, we can always find $x$ where we have equality. That suggests to me that we need the linear spacing to depend on $n$.

Let $\epsilon > 0$ and choose $s = \frac \epsilon {\sqrt n}$ as the lattice spacing. Now, choose integer $N$ such that $Ns > b$. We have our set of numbers:
$$S = \{js: j \in \mathbb Z, \text {and} \ -N \le j \le N \}$$And define the ($(2N + 1)^n$) lattice points as:
$$L = \{(l_1, l_2, \dots l_n): \forall i \ l_i \in S\}$$And we see that:
$$\forall x \in T, \exists l \in L: |x - l| \le \frac \epsilon 2 < \epsilon$$And, therefore, the finite set of open ballls $B(L, \epsilon)$ covers $T$, as required.

Note that if and when a proof is wrong, you may be able to patch it up, but sometimes you have to redo the whole thing and introduce some new ideas.

 

[mathwonk]

And notice that, since e<1 and b is an integer, that e/sqrt(n) < b, so taking all ji such that e|ji|/(sqrt(n) ≤ 2b, we do get for |ji| maximal = N, that indeed Ne/sqrt(n) = Ns ≥ 2b-e/sqrt(n) > b, as PeroK shows is what we want. I.e. so that we have enough lattice points to cover the cube.

 

[psie]

I appreciate both of your solutions, and I'm sorry to drag this out. Upon further thought, I think the authors of the text are correct in claiming that $T=[-b,b]^n$ is totally bounded by balls of the form $B(\varepsilon j,\varepsilon)$, where $j\in\mathbb Z^n$ with $\varepsilon|j_i|< 2b$ (note the strict inequality), provided we equip $\mathbb R^n$ with the maximum metric. Here's my attempt at deriving the condition $\varepsilon|j_i|<2b$ rather than $\varepsilon|j_i|\leq 2b$.

If $\varepsilon>b$, then we can simply take $B(0,\varepsilon)=(-\varepsilon,\varepsilon)^n$ and this will contain $T$ and clearly satisfy the condition.

For $\varepsilon\leq b$, observe that any point $x\in \mathbb R^n$ will be a distance less than $1$ from an integral lattice point. Consequently, any point in $\mathbb R^n$ is less than a distance $\varepsilon$ from $\varepsilon j$ for some $j\in\mathbb Z^n$. In particular, each $t\in T$ belongs to some ball $B(\varepsilon j,\varepsilon)$ as $j$ ranges in $\mathbb Z^n$. We want to pick only those $j$ such that $B(\varepsilon j,\varepsilon)\cap T\neq\varnothing$.

Let $x\in\mathbb R^n$ be such that $\varepsilon x$ is in $T$ and in $B(\varepsilon j,\varepsilon)$ for some $j\in\mathbb Z^n$, then \begin{align*} \varepsilon x\in [-b,b]^n\land d(\varepsilon x,\varepsilon j)<\varepsilon &\iff \forall i(-b\leq \varepsilon x_i\leq b \land |x_i-j_i|<1) \\ &\iff \forall i(-b/\varepsilon\leq x_i\leq b/\varepsilon\land j_i-1<x_i<j_i+1) \\ \end{align*} Now, contemplating the last statement, the interval $(j_i-1,j_i+1)$ will not contain points of $[-b/\varepsilon,b/\varepsilon]$ if $-b/\varepsilon \geq j_i+1$ or $j_i-1 \geq b/\varepsilon$. So negating this, the interval $(j_i-1,j_i+1)$ will contain points of $[-b/\varepsilon,b/\varepsilon]$ if $-b/\varepsilon <j_i+1$ and $j_i-1 < b/\varepsilon$, i.e. $\varepsilon |j_i|<\varepsilon+b$, and since we had $\varepsilon\leq b$, we get the desired condition, but with strict inequality, that is $$\varepsilon |j_i|<2b.$$

 

[psie]

If we wanted an even sharper bound, we could notice that the distance from a point $x\in\mathbb R^n$ to an integral lattice point is actually less than or equal to $\frac12$. We would then get $$\varepsilon |j_i|<\frac{\varepsilon}{2}+b\leq \frac32 b.$$

 

[mathwonk]

note: it was mentioned in post #9 that using the max norm would finesse changing the radius of the balls, by changing balls into cubes.