Theorem 1.8.5 - Convex Bodies: The Brunn-Minkowski Theory

Question

I'm trying to study for myself a little of Convex Geometry and I have some doubts with respect the proof of the Theorem 1.8.5 of the book Convex Bodies: The Brunn-Minkowski Theory. Before I presented the proof and my doubts, I will put the definitions used in the theorem below.

$\textbf{Definitions used in the theorem:}$

(i) $\mathcal{C}^n := \{ A \subset \mathbb{R}^n \ ; \ A \neq \emptyset \ \text{and} \ A \ \text{is compact} \}$.

(ii) $B^n = \overline{B(0,1)} := \{ x \in \mathbb{R}^n \ ; \ d(x,0) \leq 1 \}$.

(iii) The Hausdorff distance of the sets $K, L \in \mathcal{C}^n$ is defined by

$$\delta (K,L) := \max \left \{ \sup_{x \in K} \inf_{y \in L} |x - y|, \sup_{x \in L} \inf_{y \in K} |x - y| \right \}$$

or, equivalently, by

$$\delta (K,L) := \min \{ \lambda \geq 0 \ ; \ K \subset L + \lambda B^n, L \subset K + \lambda B^n \} $$

$\textbf{Theorem 1.8.5.}$ From each bounded sequence in $\mathcal{C}^n$ one can select a convergent subsequence.

$\textbf{Proof:}$

Let $(K^0_i)_{i \in \mathbb{N}}$ be a sequence in $\mathcal{C}^n$ whose elements are contained in some cube $C$ of edge length $\gamma$. For each $m \in \mathbb{N}$, the cube $C$ can be written as a union of $2^{mn}$ cubes of length $2^{-m}\gamma$. For $K \in \mathcal{C}^n$, let $A_m(K)$ denote the union of all such cubes that meet $K$. Since (for each $m$) the number of subcubes is finite, the sequence $(K^0_i)_{i \in \mathbb{N}}$ has a subsequence $(K^1_i)_{i \in \mathbb{N}}$ such that $A_1(K^1_i) =: T_1$ is independent of $i$. Similarly, there is an union $T_2$ of subcubes of length $2^{-2} \gamma$ and a subsequence $(K^2_i)_{i \in \mathbb{N}}$ of $(K^1_i)_{i \in \mathbb{N}}$ such that $A_2(K^2_i) = T_2$. Continuing in this way, we obtain a sequence $(T_m)_{m \in \mathbb{N}}$ of union of subcubes (of edge length $2^{-m} \gamma$ for given $m$) and to each $m$ a sequence $(K^m_i)_{i \in \mathbb{N}}$ such that

$$A_m(K^m_i) = T_m \ (1.61)$$

and

$$(K^m_i)_{i \in \mathbb{N}} \ \text{is a subsequence of} \ (K^k_i)_{i \in \mathbb{N}} \ \text{for} \ k < m. (1.62)$$

By $(1.61)$ we have $K^m_i \subset K^m_j + \lambda B^n$ with $\lambda = 2^{-m} \sqrt{n \gamma}$, hence $\delta(K^m_i, K^m_j) \leq 2^{-m} \sqrt{n \gamma}$ ($i,j,m \in \mathbb{N})$ and thus, by $(1.62)$,

$$\delta(K^m_i,K^k_j) \leq 2^{-m} \sqrt{n \gamma} \hspace{1cm} \text{for} \ i,j \in \mathbb{N} \ \text{and} \ k \geq m.$$

For $K_m := K^m_m$, it follows that

$$\delta(K_m, K_k) \leq 2^{-m} \sqrt{n \gamma} \hspace{1cm} \text{for} \ i,j \in \mathbb{N} \ \text{and} \ k \geq m.$$

Thus, $(K_m)_{m \in \mathbb{N}}$ is a Cauchy sequence and hence convergent because $(\mathcal{C}^n, \delta)$ is complete. This is the subsequence that proves the assertation. $\square$

My doubts are

1. When the author states "Since (for each $m$) the number of subcubes is finite the sequence $(K^0_i)_{i \in \mathbb{N}}$ has a subsequence $(K^1_i)_{i \in \mathbb{N}}$ such that $A_1(K^1_i) =: T_1$ is independent of $i$", I dind't understand why exists the subsequence $(K^1_i)_{i \in \mathbb{N}}$ and why $T_1$ is independent of $i$.

2. Why $(1.62)$ implies that $\delta(K^m_i,K^k_j) \leq 2^{-m} \sqrt{n \gamma} \ \text{for} \ i,j \in \mathbb{N} \ \text{and} \ k \geq m$?

Thanks in advance!

Answer 1

Let's first look at a proof of Bolzano-Weierstrass and then see how we may see your theorem as a generalisation of it.

THEOREM: (Bolzano-Weierstrass): Let $a_n$ be a bounded sequence in $\Bbb R$. Then there exists a convergent subsequence $a_{i_n}$ (i.e. $a_{i_n}$ is convergent and $i_n\in\Bbb N$ strictly increasing).

PROOF: Let $b^1_n=a_n$ be our first sequence and let it be bounded by $[u_1,v_1]$ with $\ell=v_1-u_1.$ If $\ell=0$ then the sequence is already convergent so done. Otherwise we continue by induction: We have $b^k_n$ a subsequence of $a_n$ bounded by $[u_k,v_k]$ with $u_k<v_k$. Let $w = \frac12(u_k+v_k)$ be the midpoint and consider the intervals $[u_k,w]$ and $[w,v_k]$. Now as there are two intervals and each of the infinitely many elements of $b^k_n$ is in at least one of them, there must be an interval which contains infinitely many of the $b_n^k$ (this is applying the pigeonhole principle), so set $[u_{k+1},v_{k+1}]$ to be that interval and $b^{k+1}_n$ to be the subsequence of $b_n^k$ (and hence of $a_n$) which is contained in $[u_{k+1},v_{k+1}].$

For our subsequence we choose $c_n = b^n_n.$ So how do we prove that that converges? Well we know that each the sequence $b_n^k$ is contained inside $[u_k,v_k]$ and that the size of $[u_k,v_k]$ is $2^{1-k}\ell$ so the maximum possible value for $|b_n^k-b_m^k|$ is $2^{1-k}\ell$. But as for $j\le k$, $b_n^j$ is a subsequence of $b_n^k$ and so each $b_m^k$ equals $b_{m'}^j$ for some $m'$ depending on $m$. Thus $|b_n^j-b_m^k|\le2^{1-j}\ell$ for $j\le k$. Therefore we conclude that our subsequence $c_n$ is Cauchy and thus convergent.

So how can we adapt this to your Theorem?

Well instead of having just two different intervals, we are in $n$-dimensional space so you would split up some (hyper-)cube into a union $2^n$ smaller (hyper-)cubes. But now instead of single points in the sequence you have (bounded) compact sets so instead of each element of the sequence living in one of your divisions, it lives in some union of your divisions. However there's still a finite number of possible unions-of-cubes so we can still use the pigeonhole principle to find some union containing an infinite subsequence. But now as we don't get a subsequence in a single cube, we can't just halve that one again. Instead we have to break up each of our smaller cubes. Because each step looks at the subsequence generated from the previous step, we are guaranteed that the union-of-cubes-containing-infinitely-many-elements must be a subset of the previous union of cubes.

So how do we need to change the distances? Well the argument about distances between different "levels" of subsequences still works. What about distances in a single layer? Well using the notation from the question, we have $T_m$ a union of cubes of side-length $2^-m\gamma,$ and $K^m_i$ a sequence such that each element $K^m_i$ meets each cube of $T_m.$ So if we want to measure the distance between two elements, say $K_i^m$ and $K_j^m$, we need to care about the $\sup\inf$ of distances between their elements. Fix some $x\in K_i^m$. This must be in one of the cubes $C$ of $T_m$, and as $K_j^m$ meets each of those cubes, there must be some $y\in C\cap K_j^m$. Now we can bound the distance $|x-y|$ by looking at the geometry of the cube—the longest distance will be along the diagonal and that has length $\sqrt{n(2^{-m}\gamma)^2}=2^{-m}\gamma\sqrt n$, so I don't quite agree with the Theorem there but this error does not make a difference to the result. This lets us conclude that $|x-y|\le2^{-m}\gamma\sqrt n$ and so $\inf_{y\in T_j^m}|x-y|\le2^{-m}\gamma\sqrt n$ and so $\delta(T_i^m,T_j^m)\le2^{-m}\gamma\sqrt n$ (we get both parts of the $\max$ in the definition of $\delta(A,B)$ because we can just swap $i,j$). Now we apply the "subsequences of subsequences with vanishing bounding" rule we saw in the prrof of Bolzano-Weierstrass above to get that the sequence $T_n^n$ is Cauchy and so converges.

Is that enough to fill in the gaps? comment if you want me to clarify any of it.

Answer 2

1. Consider the finite set $Z$ of all finite unions of $2^{nm}$ cubes. For each $T\in Z$ consider the set of indices $$ M(T) := \{i\in\mathbb{N}:\ A_1(K^0_i) = T\}. $$ Since $Z$ is finite, then there exists at least one $T_1\in Z$ such that $M(T_1)$ is infinite, and so you can construct your subsequence using the ordered indices of $M(T_1)$.

2. For $k>m$ you know that $(K^k_j)$ is a subsequence of $(K^m_i)$, i.e. $K^k_j = K^m_{n_j}$ with $n_1 < n_2 < \ldots$. Hence $$ \delta(K^m_i, K^k_j) = \delta(K^m_i, K^m_{n_j}) \leq 2^{-m} \sqrt{n\gamma}. $$

Answer 3

1. In this step you take $m = 1$, therefore you have $2 ^ n$ subcubes. Now each element from your sequence $(K^0_i)$ intersects some of those cubes. There are $2^{2^n}$ possible ways in which each element can intersect our $2^n$ cubes - for each cube it either intersect it or it doesn't. (maybe that number minus one, because no set is empty, but that doesn't really matter). So, some of the $2^{2^n}$ ways occurs infinitely many times and you put exactly those elements of $(K^0_i)$ to be in new $(K^1_i)$. Now clearly, $T_1$ is independent of $i$, because that is the way you constructed it.

2. You have $(*):\delta(K^m_i, K^m_j) \leq 2^{-m} \sqrt{n\gamma}, \forall i, j, m \in \mathbb{N}$ and you want to prove $\delta(K^m_i, K^k_j) \leq 2^{-m} \sqrt{n\gamma}, \forall i, j, \in \mathbb{N}, k \geq m$. So take inidices $i, j$ and $k \geq m$ from $\mathbb{N}$. Due to $(1.62)$ there exists some $l \in \mathbb{N}$ such that $K^k_j = K^m_l$, so now you want to prove $\delta(K^m_i, K^m_l) \leq 2^{-m} \sqrt{n\gamma}$, but this is exactly $(*)$. This part is really nothing smart, so I hope this helped because this is really just digging through indices. I assumed from your question that you figured out how to get that $(*)$ holds, but if I got that wrong, i can explain that part in more detail too.