technical Perspective
A high-Dimensional Surprise
By Rocco A. Servedio

HigH-diMensiOnAl spAce is a counterin-tuitive place, where natural geometric intuitions from the familiar three-dimensional world may lead us badly astray. As a simple example consider the Earth, which has a radius of about 3,950 miles (let’s pretend it is a perfect sphere). What fraction of the Earth’s surface lies within 1/100 of its radius, that is, within 39. 5 miles, from the equator? A reasonable guess would be “about 1/100,” and that is almost exactly correct. Now let’s think high-dimensionally: what fraction of the surface of a d-dimensional sphere lies within 1/100 of its radius from its equator? Again one might guess “about 1/100,” but this is wildly incorrect: all but an exponentially small (in terms of d) fraction of the d-dimensional sphere’s surface lies within 1/100 of its radius from the equator. Strange as it seems, virtually all the real estate on d -dimensional Earth is in the tropics!

The challenges of dealing with high-dimensional space are familiar to researchers in fields like machine learning and combinatorial optimization, where the “curse of dimensionality” arises often. Tasks that are easy in few dimensions—finding a simple curve to fit data points, computing the volume of a region—can become frustratingly difficult or even provably intractable (assuming P!=NP) in high-dimensional space. Yet sometimes the tables are turned, and things that seem difficult or impossible based on our low-dimensional intuition can, near-magically, become possible in high dimension. The following paper describes such a situation, where a clever construction inspired by ideas from computational complexity theory proves the existence of what seems like a too-good-to-be-true high-dimensional object.

The authors reveal an unexpect-
ed connection between spheres and
cubes and construct a new geometric
object that has some of the most fun-
damental properties of both shapes.
Turning first to cubes, they are the ca-
nonical shape that can be used to “tile
space” according to a regular grid-like
lattice leaving no holes or unfilled
space (think of slicing a block of cheese
into cubes). Of course a simple cube is
not the only shape that can do this—for
example, adding bumps to the top and
carving matching divots into the bot-
tom of a cube yields a different, Lego-
like shape that also fits perfectly with
itself to fill space with no holes under
a grid-like tiling. Any shape that can do
this is called a “cubical tile.”
A sphere is certainly not a cubical
tile, since a grid-like pattern of 3D
spheres leaves a lot of empty space un-
filled. In higher dimensions spheres
do even worse: the fraction of unfilled
space becomes exponentially larger (as
a function of d) than the fraction actu-
ally filled by the spheres. But spheres
reign supreme for a different property:
they have the smallest surface-area-to-
volume ratio of any shape, in three or
any number of dimensions. (This is
one reason why water towers have their
familiar round shape—small surface
area means less building material and
more uniform water temperature.) In
fact, while a d-dimensional cube of vol-
ume 1 has surface area 2d, a d-dimen-
sional sphere of volume 1 has surface
area only about 4. 13 d, which is much
smaller in high dimensions.

References

1. Choe. J. on the existence and regularity of fundamental domains with least boundary area. J. Differential Geom. 29 (1989), 623–663.

2. ran, r. a counterexample to strong parallel repetition. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (2008), 369–373.