Preliminaries
The distance $d(K, L)$ between symmetric convex bodies $K$ and $L$ is the least positive $d$ for which there is a linear image $\tilde L$ of $L$ such that $\tilde L ⊂ K ⊂ d\tilde L$. Note that this distance is multiplicative, not additive: in order to get a metric (on the set of linear equivalence classes of symmetric convex bodies), we would need to take $\log d$ instead of $d$. In particular, if $K$ and $L$ are identical then $d(K, L) = 1$.
More details on this MathSE post.
Question
I have trouble understanding the reformulation of the following theorem which provides a lower bound on the number of facets of a symmetric polytope in $\mathbb{R}^n$. The proof of the theorem and the discussion hereafter (in the article I am reading) depends heavily on this reformulation - so I need help in understanding it. I quote:
Theorem 2.1. Let $K$ be a (symmetric) polytope in $\mathbb{R}^n$ with $d(K,B_2^n) = d$. Then $K$ has at least $\exp\left(\frac{n}{2d^2}\right)$ facets. On the other hand, for each $n$, there is a polytope with $4^n$ facets whose distance from the ball is at most $2$.
The distance being referred to in the above discussion is defined in the Preliminaries section of this post.
The arguments in this lecture, including the result just stated, go back to the early days of packing and covering problems. A classical reference for the subject is [Rogers 1964]. Before we embark upon a proof of Theorem 2.1, let’s look at a reformulation that will motivate several more sophisticated results later on. A symmetric convex body in $\mathbb{R}^n$ with $m$ pairs of facets can be realized as an $n$-dimensional slice (through the center) of the cube in $\mathbb{R}^m$. This is because such a body is the intersection of $m$ slabs in $\mathbb{R}^n$, each of the form $\{x: |\langle x, v\rangle| \le 1\}$, for some nonzero vector $v$ in $\mathbb{R}^n$. This is shown in Figure $8$ (below).
I'm able to decipher that $\{x: |\langle x, v\rangle| \le 1\}$ is a collection of hyperplanes of the form $\{x: \langle x, v\rangle = k\}$ where $-1\le k\le 1$, hence forming a slab. However,
- Why is the slice $n$-dimensional? What's the cube they are talking about?
- How did we change our perspective from $\mathbb{R}^n$ to $\mathbb{R}^m$? I didn't get that.
In the figure above, where is the cube?, where is the polytope?, are we working with $m=3$ (since there seem to be $3$ pairs of opposite facets)?
Thus $K$ is the set $\{x: |\langle x, v_i\rangle| \le 1, 1 ≤ i ≤ m\}$, for some sequence $(v_i)_1^m$ of vectors in $\mathbb{R}^n$. The linear map $$T:x\mapsto (\langle x,v_1\rangle,\ldots \langle x,v_m\rangle)$$ embeds $\mathbb{R}^n$ as a subspace $H$ of $\mathbb{R}^m$, and the intersection of $H$ with the cube $[−1, 1]^m$ is the set of points $y$ in $H$ for which $|y_i| \le 1$ for each coordinate $i$. So this intersection is the image of $K$ under $T$. Conversely, any $n$-dimensional slice of $[−1,1]^m$ is a body with at most $m$ pairs of faces. Thus, the result we are aiming at can be formulated as follows:
"The cube in $\mathbb{R}^m$ has almost spherical sections whose dimension $n$ is roughly $\log m$ and not more."
- I do see that $$H = \{(\langle x,v_1\rangle,\ldots \langle x,v_m\rangle)\in\mathbb{R}^m:x\in\mathbb{R}^n\}$$ is a subspace of $\mathbb{R}^m$. So the intersection of $H$ with $[-1,1]^m$ is the set of points $y\in H$ such that for every $i$, we have $|y_i|\le 1$. So we have $|\langle x,v_i\rangle|\leq 1$ for every $i$ (since the points are in $H$) - which gives $x\in K$. As a result, the intersection of $H$ with $[-1,1]^m$ is the image of $K$ under $T$.
- Why is any $n$-dimensional slice of $[−1,1]^m$ a body with at most $m$ pairs of faces?
- What is meant by almost spherical sections in the cube?
I need help in understanding the reformulation of Theorem 2.1 to the last statement above, via the process outlined in the quoted extract. I would appreciate a detailed explanation, and/or anything that might help me! Thanks a lot for your patience in reading this long post!
References:
- Lecture 2 (Pg. 8-9) of these notes.
The cube, which is just $[-1,1]^m\subseteq\mathbb R^m$, is not visible in the diagram since they have only shown the polytope itself (in $\mathbb{R}^n$). The "$n$-dimensional slice" is explained in the subsequent paragraph. The corresponding embedding is being described by a linear transformation, namely the map $T$.
To understand this better, perhaps you could think of the polytope in $2$ dimensions given by $v_1=\left(\frac{1}{2},0\right)$, $v_2=\left(\frac{1}{4},\frac{\sqrt{3}}{4}\right)$, and $v_3 = \left(\frac{1}{4},-\frac{\sqrt{3}}{4}\right)$ - this is just a hexagon that is inscribed in the unit ball $B_2^2$. So what does the map $T$ do? It embeds this hexagon in $\mathbb{R}^3$ as the intersection of $[-1,1]^3$ with some subspace:
Similarly, you can view the intersection of any subspace of $\mathbb{R}^m$ with $[-1,1]^m$ as a polytope in a lower dimension.
Note that each face of the polytope formed by a slice corresponds to an $(m-1)$-dimensional face of $[-1,1]^m$. Since there are $2m$ such faces, (the polytope corresponding to) any slice can have at most $2m$ faces.
Roughly, it just means a slice of the cube whose distance from the Euclidean ball (in that dimension) is not too large. The theorem you are reading says that a polytope that is at a small distance from the Euclidean ball has exponentially many facets. Alternatively, if you consider a slice of the cube, it can only be close to the Euclidean ball if it has exponentially many facets, which can only be true if the dimension you take is very small (logarithmic).
The exact statement regarding $\log m$ is actually made more precise in Dvoretzky's Theorem which is discussed in the final lecture of the notes you are reading - you could look ahead at the statement of this theorem right now. It states
which, sans constant, is more or less what the author has said here.
The proof you are interested in does not really use this $\log m$ formulation, it just uses the fact that you can think of a polytope in $\mathbb{R}^n$ with $m$ pairs of faces as an $n$-dimensional slice of $[-1,1]^m$.