# 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.

-
Borsuk's conjecture is a candidate: every body of diameter $1$ in $n$-space can be cut into $n+1$ pieces with diameter less than $1$. Known to be false for all $n\gt297$. mathworld.wolfram.com/BorsuksConjecture.html –  Gerry Myerson Jan 29 '13 at 3:03
I've emailed Boyd; I will report anything I hear from him about this. –  MJD Jan 29 '13 at 17:06

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

-
Seems to be true for $n\le6$, false for $n\ge8$, and open for $n=7$, according to en.wikipedia.org/wiki/Keller's_conjecture –  Gerry Myerson Jan 29 '13 at 2:57

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.

-

I also don't know about the list, but this simple geometric construction might be there. I remember it being attributed to Vitali Milman.

• Divide $n$-dimensional cube $Q$ into $2^n$ equal cubes in the natural way;
• Inscribe a ball in each of these $2^n$ cubes;
• There is some room left at the center of $Q$; inscribe a ball there.

This is how it works in two dimensions: $Q$ is the black square.

You can imagine a similar $3$-dimensional picture with $8$ blue balls and a small red one in the middle.

The red ball is contained in $Q$ when $n\le 9$, but not when $n\ge 10$.

-

Concentration of measure phenomena provide great examples of how our intuition based on low-dimensional space is unreliable in high-dimensions.

Compare unit balls in the metric spaces $\mathbb R^n$ endowed with, resp. the Euclidean metric $L_2$, versus $L_1$, and $L_{\infty}$.

The unit balls of $L_2$ are bounded by "round" spheres and are sandwiched between the other two, namely they contain the $L_1$ balls and are contained in the $L_{\infty}$ balls for any $n$.

For $n=2$, the $L_2$ unit ball is a circle, the $L_1$ unit ball is a diamond (convex hull of $\{e_1,e_2,-e_1,-e_2\}$) and the $L_{\infty}$ ball is the square $[-1,1]\times[-1,1]$.

For $n=3$ the $L_2$ ball is the ordinary ball, the $L_1$ ball is (I believe) an octahedron, and the $L_{\infty}$ ball is a cube.

(If I have time I'll add graphics w/ Mathematica)

As $n \to \infty$:

(1) the ratio of the volumes of $L_2$ to $L_{\infty}$ unit balls and ratio of the volumes of the $L_1$ to $L_2$ balls both go to zero.

(2) If you are programming genetic algorithms or random searches in high dimensions and want to generate uniform directions, another problem comes up with the naive algorithm of choosing uniform, independent increments: the measure of the $L_{\infty}$ "hypercube" balls becomes increasingly concentrated at the exponentially increasing ($2^n$) corners. Knuth developed a clever algorithm that yields a uniform measure on the sphere in any dimension.

• You may also want to check Diestel's book Graph Theory - I'm pretty sure in it towards the end he comments on how badly our intuition fails in high dimensions. Don't kill me if I'm wrong here - going by memory.
-

We expect a normally-distributed random variable to take values close to the mean, and in low dimensions it does. But in high dimensions, it does not. The volume of a thin hyperspherical shell increases so rapidly as its radius increases that even though the variable has greatest probability density near the mean, most of the probability mass is far from the mean, and a random variable is extremely unlikely to take a value close to the mean.

Specifically, Let $X$ be a normally-distributed random variable in $n$ dimensions with mean at $\bf 0$ and variance $\sigma^2$. Then the expected squared distance from $\bf 0$ is $E\big(|X|^2\big) = n\sigma^2$ , and the probability of $X$ being found farther than $\epsilon n\sigma^2$ from this distance is exponential in $\epsilon$. For large $n$, $X$ takes values close to $\bf 0$ with probability approximately 0; it is nearly always found in a very thin spherical shell of radius $\sigma\sqrt n$.

This is in stark contrast to low-dimensional cases, where we expect normally-distributed variables to have values close to the mean most of the time.

As a result of this, the overlap of two normally-distributed variables with different means is essentially zero when the number of dimensions is large; this is again contrary to the intuition from lower dimensions.

-
Well, that depends on how close is "close". Even in dimension $2$ the density of $|Z|$ is $0$ at $0$. I don't know what is unintuitive here. –  Robert Israel Jan 29 '13 at 19:06
Extremely close. I have elaborated. –  MJD Jan 29 '13 at 22:38
Radius $\sqrt{n}\sigma$, not $n \sigma^2$. –  Robert Israel Jan 30 '13 at 0:55
And it's not that thin. According to my calculations the variance of $|X|/\sigma$ is $n - \dfrac{2 \Gamma((n+1)/2)^2}{\Gamma(n/2)^2}$ which is approximately $1/2$. –  Robert Israel Jan 30 '13 at 1:18