Hayes - An Adventure in the nth Dimension, Topologia i Geometria
[ Pobierz całość w formacie PDF ]
A reprint from
American Scientist
the magazine of Sigma Xi, The Scientific Research Society
This reprint is provided for personal and noncommercial use. For any other use, please send a request Brian Hayes by
electronic mail to bhayes@amsci.org.
Computing Science
An Adventure in the
N
th Dimension
Brian Hayes
T
he area enclosed by a circle is
cal term for a solid spherical object.
“Sphere” itself is generally reserved
for a hollow shell, like a soap bubble.
More formally, a sphere is the locus
of all points whose distance from the
center is equal to the radius
r
. A ball
is the locus of points whose distance
from the center is less than or equal
to
r
. And while I’m trudging through
this mire of terminology, I should men-
tion that “
n
-ball” and “
n
-cube” refer
to an
n
-dimensional object inhabiting
n
-dimensional space. This may seem
too obvious to bother stating, but
some branches of mathematics adopt
a different convention. In topology, a
2-sphere lives in 3-space.)
On the mystery
of a ball that fills
a box, but vanishes
in the vastness
of higher dimensions
π
r
2
. The volume inside a sphere
is
4
∕
3
π
r
3
. These are formulas I learned too
early in life. Having committed them to
memory as a schoolboy, I ceased to ask
questions about their origin or mean-
ing. In particular, it never occurred to
me to wonder how the two formulas
are related, or whether they could be
extended beyond the familiar world
of two- and three-dimensional objects
to the geometry of higher-dimensional
spaces. What’s the volume bounded
by a four-dimensional sphere? Is there
some master formula that gives the mea-
sure of a round object in
n
dimensions?
Some 50 years after my first expo-
sure to the formulas for area and vol-
ume, I have finally had occasion to look
into these broader questions. Finding
the master formula for
n
-dimensional
volumes was easy; a few minutes with
Google and Wikipedia was all it took.
But I’ve had many a brow-furrowing
moment since then trying to make
sense of what the formula is telling me.
The relation between volume and di-
mension is not at all what I expected;
indeed, it’s one of the zaniest things I’ve
ever come upon in mathematics. I’m
appalled to realize that I have passed
so much of my life in ignorance of this
curious phenomenon. I write about it
here in case anyone else also missed
school on the day the class learned
n
-
dimensional geometry.
we played on a two-dimensional field.
If we had lost our ball in a space of
many dimensions, we might still be
looking for it.
The mathematician Richard Bell-
man labeled this effect “the curse of
dimensionality.” As the number of
spatial dimensions goes up, finding
things or measuring their size and
shape gets harder. This is a matter of
practical consequence, because many
computational tasks are carried out in
a high-dimensional setting. Typically
each variable in a problem description
is mapped to a separate dimension.
A few months ago I was prepar-
ing an illustration of Bellman’s curse
for an earlier Computing Science col-
umn. My first thought was to show
the ball-in-a-box phenomenon. Put an
n
-dimensional ball in an
n
-dimension-
al cube just large enough to receive
it. As
n
increases, the fraction of the
cube’s volume occupied by the ball
falls dramatically.
In the end I chose a different and
simpler scheme for the illustration. But
after the column appeared [“Quasi-
random Ramblings,” July–August], I
returned to the ball-in-a-box question
out of curiosity. I had long thought that
I understood it, but I realized that I had
almost no quantitative data on the rela-
tive size of the ball and the cube.
(In this context “ball” is not just a
plaything but also the mathemati-
The Master Formula
An
n
-ball of radius 1 (a “unit ball”)
will just fit inside an
n
-cube with
sides of length 2. The surface of the
ball kisses the center of each face of
the cube. In this configuration, what
fraction of the cubic volume is filled
by the ball?
The question is answered easily in
the familiar low-dimensional spaces
we are all accustomed to living in. At
the bottom of the hierarchy is one-
dimensional geometry, which is rather
dull: Everything looks like a line seg-
ment. A 1-ball with
r
= 1 and a 1-cube
with
s
= 2 are actually the same object—
a line segment of length 2. Thus in one
dimension the ball completely fills the
cube; the volume ratio is 1.0.
In two dimensions, a 2-ball inside a
2-cube is a disk inscribed in a square,
and so this problem can be solved with
one of my childhood formulas. With
r
= 1, the area π
r
2
is simply π, whereas
the area of the square,
s
2
, is 4; the ratio
of these quantities is about 0.79.
In three dimensions, the ball’s vol-
ume is
4
∕
3
π, whereas the cube has a vol-
ume of 8; this works out to a ratio of
approximately 0.52.
On the basis of these three data points,
it appears that the ball fills a smaller and
Lost in Space
In those childhood years when I was
memorizing volume formulas, I also
played a lot of ball games. Often the
game was delayed when we lost the
ball in the weeds beyond right field. I
didn't know it then, but we were lucky
Brian Hayes is senior writer for
American Scien-
tist
. Additional material related to the
Comput-
ing Science
org. Address: 11 Chandler St. #2, Somerville, MA
02144. E-mail: brian@bit-player.org
442 American Scientist, Volume 99
© 2011 Brian Hayes. Reproduction with permission only.
Contact bhayes@amsci.org.
smaller fraction of the cube as
n
increas-
es. There’s a simple, intuitive argument
suggesting that the trend will continue:
The regions of the cube that are left va-
cant by the ball are the corners. Each
time
n
increases by 1, the number of
corners doubles, so we can expect ever
more volume to migrate into the nooks
and crannies near the cube’s vertices.
To go beyond this appealing but non-
quantitative principle, I would have to
calculate the volume of
n
-balls and
n
-
cubes for values of
n
greater than 3.
The calculation is easy for the cube. An
n
-cube with sides of length
s
has vol-
ume
s
n
. The cube that encloses a unit
ball has
s
=2, so the volume is 2
n
.
But what about the
n
-ball? As I have
already noted, my early education
failed to equip me with the necessary
formula, and so I turned to the Web.
What a marvel it is! (And it gets better
all the time.) In two or three clicks I
had before me a Wikipedia page titled
“Deriving the volume of an
n
-ball.”
Near the top of that page was the for-
mula I sought:
the gamma function, unlike the facto-
rial, is also defined for numbers oth-
er than integers. For example, Γ(½) is
equal to
√
–
.
But then I looked at the continuation
of the table:
n
1
V
(
n
,1)
2
The Incredible Shrinking
n
-Ball
When I discovered the
n
-ball formula,
I did not pause to investigate its prov-
enance or derivation. I was impatient
to plug in some numbers and see what
would come out. So I wrote a hasty
one-line program in Mathematica and
began tabulating the volume of a unit
ball in various dimensions. I had defi-
nite expectations about the outcome.
I believed that the volume of the unit
ball would increase steadily with
n
,
though at a lower rate than the volume
of the enclosing
s
= 2 cube, thereby
confirming Bellman’s curse of dimen-
sionality. Here are the first few results
returned by the program:
2
3.1416
4
3
3
4.1888
1
2
2
4
4.9348
15
2
8
5
5.2638
1
6
3
6
5.1677
105
3
16
7
4.7248
24
4
1
8
4.0587
32
945
4
9
3.2985
120
5
1
10
2.5502
Beyond the fifth dimension, the vol-
ume of a unit
n
-ball
decreases
as
n
in-
creases! I tried a few larger values of
n
, finding that
V
(20, 1) is about 0.0258,
and
V
(100, 1) is in the neighborhood of
10
–40
. Thus it looked very much like
the
n
-ball dwindles away to nothing as
n
approaches infinity.
n
V
(
n
,1)
1
2
2
3.1416
4
3
3
4.1888
Doubly Cursed
I had thought that I understood Bell-
man’s curse: Both the
n
-ball and the
n
-cube grow along with
n
, but the cube
expands faster. In fact, the curse is far
more damning: At the same time the
cube inflates exponentially, the ball
shrinks to insignificance. In a space of
100 dimensions, the fraction of the cubic
volume filled by the ball has declined to
1.8 × 10
–70
. This is far smaller than the
volume of an atom in relation to the
2
r
n
(
2
+ 1)
.
1
2
2
V
(
n, r
) =
4
4.9348
8
15
2
5
5.2638
Later in this column I’ll say a few
words about where this formula came
from, both mathematically and histori-
cally, but for now I merely note that the
only part of the formula that ventures
beyond routine arithmetic is the gamma
function, Γ, which is an elaboration on
the idea of a factorial. For positive inte-
gers, Γ(
n
+ 1) =
n
! = 1×2×3×...×
n
. But
I noted immediately that the val-
ues for one, two and three dimensions
agreed with the results I already knew.
(This kind of confirmation is always
reassuring when you run a program
for the first time.) I also observed that
the volume was slowly increasing with
n
, as I had expected.
3-ball in 3-cube
2-ball in 2-cube
1-ball in 1-cube
r
= 1
r
= 1
s
= 2
volume ratio = 1.0
s
= 2
volume ratio = 0.79
volume ratio = 0.52
Balls in boxes offer a simple system for studying geometry across a series of spatial dimensions. A ball is the solid object bounded by a sphere;
the boxes are cubes with sides of length 2, which makes them just large enough to accommodate a ball of radius 1. In one dimension
(left)
the
ball and the cube have the same shape: a line segment of length 2. In two dimensions
(middle)
and three dimensions
(right)
the ball and cube
are more recognizable. As dimension increases, the ball fills a smaller and smaller fraction of the cube’s internal volume. In three dimensions
the filled fraction is about half; in 100-dimensional space, the ball has all but vanished, filling only 1.8 × 10
–70
of the cube’s volume.
© 2011 Brian Hayes. Reproduction with permission only.
Contact bhayes@amsci.org.
www.americanscientist.org
2011 November–December 443
volume of the Earth. The ball in the box
has all but vanished. If you were to se-
lect a trillion points at random from the
interior of the cube, you’d have almost
no chance of landing on even one point
that is also inside the ball.
What makes this disappearing act
so extraordinary is that the ball in
question is still the largest one that
could possibly be stuffed into the
cube. We are not talking about a pea
rattling around loose inside a refrig-
erator carton. The ball’s diameter is
still equal to the side length of the
cube. The surface of the ball touches
every face of the cube. (A face of an
n
-
cube is an (
n
–1)-cube.) The fit is snug;
if the ball were made even a smidgen
larger, it would bulge out of the cube
on all sides. Nevertheless, in terms
of volume measure, the ball is nearly
crushed out of existence, like a black
hole collapsing under its own mass.
How can we make sense of this
seeming paradox? One way of un-
derstanding it is to acknowledge that
the ball fills the middle of the cube,
but the cube doesn’t have much of
a middle; almost all of its volume is
away from the center, huddling in
the corners. A simple counting argu-
ment gives a clue to what’s going on.
As noted above, the ball touches the
enclosing cube at the center of each
face, but it does not reach out into the
corners. A 100-cube has just 200 faces,
but it has 2
100
corners.
Another approach to understanding
the collapse of the
n
-ball is to imag-
ine poking skewers through the cube
along various diameters. (A diameter
is any straight line that passes through
the center point.) The shortest diam-
eters run from the center of a face to
the center of the opposite face. For the
cube enclosing a unit ball, the length
of this shortest diameter is 2, which is
both the side length of the cube and
the diameter of the ball. Thus a skewer
on the shortest diameter lies inside the
ball throughout its length.
The longest diameters of the cube
extend from a corner through the cen-
ter point to the opposite corner. For
an
n
-cube with side length
s
= 2, the
length of this diameter is 2
√
–
. Thus
in the 100-cube surrounding a unit
ball, the longest diameter has length
20; only 10 percent of this length lies
within the ball. Moreover, there are
just 100 of the shortest diameters, but
there are 2
99
of the longest ones.
Here is still another mind-bending
trick with balls and boxes to suggest
just how weird space becomes in higher
dimensions. I learned of it from Barry
Cipra, who published a description in
Volume 1 of
What’s Happening in the
Mathematical Sciences
(1991). On the
plane, a square with sides of length 4
will accommodate four unit disks in
a two-by-two array, with room for a
smaller disk in the middle; the radius
of that smaller disk is √
–
– 1. In three
dimensions the equivalent 3-cube fits
eight unit balls, plus a smaller ninth ball
in the middle, whose radius is √
–
– 1. In
the general case of
n
dimensions, the
box has room for 2
n
unit
n
-balls in a
rectilinear array, with one additional
ball in the vacant central space, and the
central ball has a radius of
√
–
– 1. Look
what happens when
n
reaches 9. The
“smaller” central ball now has a radius
of 2, which makes it twice the size of
the 512 surrounding balls. Furthermore,
the central ball has expanded to reach
the sides of the bounding box, and will
burst through the walls with any fur-
ther increase in dimension.
What’s So Special About the 5-Ball?
I was taken by surprise when I learned
that the volume of a unit
n
-ball goes to
zero as
n
goes to infinity; I had expect-
ed the opposite. But something else
surprised me even more—the fact that
the volume function is not monotonic.
Either a steady increase or a steady
decrease seemed more plausible than
having the volume grow for a while,
then reach a peak at some finite value
of
n
, and thereafter decline. This be-
havior singles out a particular dimen-
sion for special attention. What is it
about five-dimensional space that al-
lows a unit 5-ball to spread out more
expansively than any other
n
-ball?
I can offer an answer, although it
doesn’t really explain much. The answer
is that everything depends on the value
of π. Because π is a little more than 3, the
volume peak comes in five dimensions;
if π were equal to 17, say, the unit ball
with maximum volume would be found
in a space with 33 dimensions.
To see how π comes to have this role,
we’ll have to return to the formula
for
n
-ball volume. We can get a rough
sense of the function’s behavior from
a simplified version of the formula.
In the first place, if we are interested
only in the unit ball, then
r
is always
equal to 1, and the
r
n
term can be ig-
nored. That leaves a power of π in the
numerator and a gamma function in
the denominator. If we consider only
even values of
n
, so that
n
/2 is always
an integer, we can replace the gamma
function with a factorial. For brevity,
let
m
=
n
/2; then all that remains of the
formula is this ratio: π
m
/
m
!.
The simplified formula says that the
n
-ball volume is determined by a race
between π
m
and
m
!. Initially, for the
smallest values of
m
, π
m
sprints ahead;
for example, at
m
= 2 we have π
2
≈ 10,
which is greater than 2! = 2. In the long
run, however,
m
! will surely win this
race. Both π
m
and
m
! are products of
m
factors, but in π
m
the factors are all
equal to π, whereas in
m
! they range
from 1 up to
m
. Numerically,
m
! first
exceeds π
m
when
m
= 7, and thereafter
the factorial grows very much larger.
This simplified analysis accounts
for the major features of the volume
n
= 5.2569464
V
(
n
,1) = 5.277768
5
4
3
2
1
0
5
10
15
20
dimension
n
The volume of a unit ball in
n
dimensions reveals an intriguing spectrum of variations. Up
to dimension 5, the ball’s volume increases with each increment to
n
; then the volume starts
diminishing again, and ultimately goes to zero as
n
goes to infinity. If dimension is considered
a continuous variable, the peak volume comes at n=5.2569464
(green dot)
.
© 2011 Brian Hayes. Reproduction with permission only.
Contact bhayes@amsci.org.
444 American Scientist, Volume 99
curve, at least in a qualitative way. The
volume of a unit ball has to go to zero
in infinite-dimensional space because
zero is the limit of the ratio π
m
/
m
!. In
low dimensions, on the other hand,
the ratio is increasing with
m
. And if
it’s going uphill for small
m
and down-
hill for large
m
, there must be some
intermediate value where the function
reaches a maximum.
To get a quantitative fix on the loca-
tion of maximum, we must return to
the formula in its original form and
consider odd as well as even num-
bers of dimensions. Indeed, we can
take a step beyond mere integer di-
mensions. Because the gamma func-
tion is defined for all real numbers, we
can treat dimension as a continuous
variable and ask with finer resolution
where the maximum volume occurs.
A numerical solution to this calculus
problem—found with further help
from Mathematica—shows a peak in
the volume curve at
n
≈ 5.2569464; at
this point the unit ball has a volume of
5.2777680.
With a closely related formula, we
can also calculate the surface area of an
n
-ball. Like the volume, this quantity
reaches a peak and then falls away to
zero. The maximum is at
n
≈ 7.2569464,
or in other words two dimensions
larger than the volume peak.
The Dimensions of the Problem
The arithmetic behind all these results
is straightforward; attaching meaning
to the numbers is not so easy. In par-
ticular, I can see numerically—by com-
paring powers of π with factorials—
why the unit ball’s volume reaches a
maximum at
n
= 5. But I have no geo-
metric intuition about five-dimension-
al space that would explain this fact.
Perhaps readers with deeper vision
will be able to provide some insight.
The results on noninteger dimen-
sions are quite otherworldly. The no-
tion of fractional dimensions is famil-
iar enough, but it is generally applied
to objects, not to spaces. For example,
the Sierpinsky triangle, with its end-
lessly nested holes within holes, is as-
signed a dimension of 1.585, but the
triangle is still drawn on a plane of
dimension 2. What would it mean to
construct a space with 5.2569464 mu-
tually perpendicular coordinate axes?
I can’t imagine—and that’s not just a
figure of speech.
Another troubling question is
whether it really makes sense to com-
The graph of
n
-ball volume as a function of dimension was plotted more than 100 years ago
by Paul Renno Heyl, who was then a graduate student at the University of Pennsylvania. The
volume graph is the lower curve, labeled “content.” The upper curve gives the ball’s surface
area, for which Heyl used the term “boundary.” The illustration is from Heyl’s 1897 thesis,
“Properties of the locus r = constant in space of n dimensions.”
pare volumes across dimensions. Each
dimension requires its own units of
measure, and so the relative magni-
tudes of the numbers attached to those
units don’t mean much. Is a disk of
area 10 square centimeters larger or
smaller than a ball of volume 5 cubic
centimeters? We can’t answer; it’s like
comparing apples and orange juice.
Nevertheless, I believe there is indeed
a valid basis for making comparisons.
In each dimension volume is to be mea-
sured in terms of a standard volume
in
that dimension
. The obvious standard
is the unit cube (sometimes called the
“measure polytope”), which has a vol-
ume of 1 in all dimensions. Starting at
n
= 1, the unit ball is larger than the unit
cube, and the ball-to-cube ratio gets still
still larger through
n
= 5; then the trend
reverses, and eventually the ball is much
smaller than the unit cube. This chang-
ing ratio of ball volume to cube volume
is the phenomenon to be explained.
Slicing the Onion
The volume formulas I learned as a
child were incantations to be memo-
rized rather than understood. I would
like to do better now. Although I can-
not give a full derivation of the
n
-ball
formula—for lack of both space and
mathematical acumen—perhaps the
following remarks will shed some light.
The key idea is that an
n
-ball has
within it an infinity of (
n
– 1)-balls.
For example, a series of parallel slices
through the body of an onion turns a
3-ball into a stack of 2-balls. Another set
of cuts, perpendicular to the first series,
© 2011 Brian Hayes. Reproduction with permission only.
Contact bhayes@amsci.org.
www.americanscientist.org
2011 November–December 445
[ Pobierz całość w formacie PDF ]