Looking for Cover's hubris-busting ${\mathbb R}^{N\gg3}$ counterexamples
In lecture 4 of his Introduction to Dynamical Linear Systems course, right after interpreting the inner product in ${\mathbb R}^N$ in terms of the cosine of the subtended angle, Stanford's Stephen Boyd goes into humorous aside in which he pokes fun at the notion that one can "visualize" and reason about ${\mathbb R}^N$—for some $N$ greater than, say, $5$—by relying on intuitive analogies with ${\mathbb R}^2$ or ${\mathbb R}^3$.
(FWIW, I found Boyd's commentary pretty funny. It starts at 59'46" of the YouTube video, and goes for about 3 minutes.)
At some point during this riff, Boyd remarks that "[the late Stanford professor Thomas] Cover has a series of examples showing that [when it comes to ${\mathbb R}^{N\gg3}$] you know nothing!" He then adds something like "I should really collect some of these from him, 'cuz they're really good... There are about four of 'em..."
I've been positively haunted by this mythical list of counterexamples ever since I heard Boyd's mention of it.
If anyone can point me to some version of Cover's list I'd greatly appreciate it.
The matter goes beyond satisfying my idle curiosity. I feel this is an issue that really does need a bit of awareness-raising in the research community. I'm surrounded by researchers who blithely rely on their ${\mathbb R}^3$-based intuitions to reason about algorithms that search through an "energy landscape" (i.e. a hypersurface) in ${\mathbb R}^{1\; \mathrm{bazillion}}$, and they poo-pooh any concern over the applicability of said intuitions, and the soundness of the reasoning based on them. (Heck, even assuming that what holds in, say, ${\mathbb R}^2$ will necessarily hold in ${\mathbb R}^3$, or that what holds in ${\mathbb R}^1$ will necessarily hold in ${\mathbb R}^2$, can get one all wet...)
So my hope is that Cover's list will rattle them enough to show them their hubris.
Solution 1:
I don't know if this is on Cover's list, but maybe it should be:
For $n=2$ and $3$, any tiling of ${\mathbb R}^n$ by unit $n$-cubes has two with a complete facet in common. But it's not true for $n \ge 10$: see http://arxiv.org/pdf/math.MG/9210222.pdf
Solution 2:
The most basic surprise, in my opinion, is that the ratio of the volume of the unit sphere to the volume of the cube circumscribing that sphere tends to 0 as the dimension of the space tends to $\infty$. In other words, a high-dimensional sphere takes up almost no space in the cube that circumscribes it. See pp.4--5 in http://www.cc.gatech.edu/~kingravi/ML%20and%20High%20Dim%20Spaces.pdf.
Another surprise that is a random pair of directions in a high-dimensional space are probably going to be nearly orthogonal. This is discussed on the page http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/ (search for the term "high-dimensional geometry") and p. 23 at http://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/chap1-high-dim-space.pdf.