Volume of an n-ball
en.wikipedia.org
en.wikipedia.org
The unit “1” in terms of hypervolume is a n-hypercube with side length 1, so the question is really, how many of those hypercubes fit into an n-ball of a given radius.
Now, the thing I realized is that a unit hypercube in n dimensions is an unimaginably weird object. Its side length is, by definition, 1. But as n goes to infinity, the distance between the center and the corners of this unit hypercube goes to infinity — this follows directly from the Pythagorean Theorem. The center of the hyperfaces, on the other hand, is always only 0.5 distance units away from the center of the cube. An inscribed ball touches those hyperfaces, so 0.5 is also the radius of that inscribed ball. This makes the hypercube in some sense very “spiky”, with parts of the boundary close to the center (0.5) and other parts infinitely far away. Also, there are 2^n of those corners.
Indeed, and that’s just another way of stating the submission headline, most of the volume of the hypercube is near those spiky corners. Stated another way, as n goes to infinity, none of the volume of a hypercube is at a bounded distance from the center. And note that we’re still talking about a unit hypercube, so the side length in all of this always remains 1.
So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume?
One way to make the weirdness of the "other parts infinitely far away" concrete is to recall that, say, the Empire State Building can fit entirely inside of an n-cube with sides of 1 cm, for sufficiently large n. The length of the diagonal of such a cube grows without bound, and so does any constant-dimensional cross-section.
Extremely high-dimensional spaces are extremely spacious. (People experience this with ML and statistics, where random points in very high-dimensional data sets are almost certain to be extremely far apart from one another in a Euclidean metric.)
> So, if you accept the math, the question is: Is the quoted result really something unintuitive about high-dimensional balls, which are perfectly symmetrical objects? Or is the “weirdness”, in terms of human intuition, better blamed on the hypercubes we implicitly compare them to when we talk about volume?
That's a terrific way to put it. We can think of the n-balls as bizarrely small (and/or bizarrely round), or we can think of the n-cubes as bizarrely huge (and/or bizarrely spiky). Then we could say that the latter eventually contain absurdly much space, while the former continue to contain only a moderate, reasonable amount of space!
https://en.wikipedia.org/wiki/Main_Page#/media/File:Mars_top...
and thought about all of those circular craters, then realized that the circularity of the craters is a consequence of symmetry (and also of conservation of energy). The sphericity of Mars itself is also a consequence of physical principles like that.
So in terms of physical laws and physical phenomena, n-balls show up much more readily than n-cubes, and in some senses have a much simpler description.
If you weren't already on a street grid in a city and using that grid to navigate, a parent might say to a child "don't wander more than one kilometer from home" and would naturally generate a circle rather than a square as the locus of points that are close enough.
Nature and people care a lot about proximity, which is to say distance, which then generates n-balls. So maybe they are more fundamental and more intuitive for certain purposes. But the curse of dimensionality is going to make either balls or cubes weird in enough dimensions, and counterintuitive to intuitions formed with just three dimensions. The balls are going to be surprisingly tiny ("there's very little nearby here") and the cubes are going to be surprisingly vast ("space is so spacious").
My sole attempt at writing an essay for my local SF fan club, when I was in high school, was to apply this observation to explain ... err .. handwave .. how the TARDIS can be bigger on the inside, eg, as seen in The Invasion of Time.
Of course, back then the TARDIS was only 68,000 tons - about the size of an aircraft carrier. (In Castrovalva, 1/4 of the TARDIS - 17,000 tons - was ejected.) Figuring 400 meters length in a (2m)^n box gives at least n = 40,000 dimensions.
Nowadays it has enough mass to fracture a planet, contains a collapsing star, etc. Life was simpler in the 1980s. :)
That’s a striking illustration. Even the entire Earth fits into a 1 cm n-cube, but — and that’s important — only diagonally.
I still find this analogy confusing, because the units don’t match. The Empire State Building has some volume in cm^3, but the hypercube volume is cm^n. 1 cm^5 is not 100 times more volume than 1 cm^3, right?
Am I thinking about it wrong? I guess you can think about filling up a 3D cube with quasi-2D slices, is it like that?
Ah, thinking about the other comments a bit, you mean the diagonal of the hypercube can be larger than the biggest dimension of the building?
No, you can fit the whole thing inside the 1mm hypercube, as long as you have enough dimensions. Once you have fit the height of the building along one diagonal, you can add new dimensions and rotate the building along that diagonal so that the width and the height will fit along the diagonals of the other dimensions.
That reference to symmetry made me thing of another way to look at this: the overlap between two random unit n-hypercubes goes to zero as n goes to infinity (or does it?).
For example, if you peel away the outer 1% of a n-dimensional sphere or cube, you’re left with 0,99^n of its volume. As n goes to infinity, that goes down to zero.
See also the curse of dimensionality (https://en.wikipedia.org/wiki/Curse_of_dimensionality), or https://www.math.ucdavis.edu/~strohmer/courses/180BigData/18..., which, for example, compares the n-dimensional sphere with radius 1 to n-dimensional hypercubes with side length 1. In two and three dimensions, the cube easily fits in the sphere; in four, it just fits. In higher dimensions, you can’t fit that hypercube in the hyper sphere, even though the diameter of the sphere is twice that of a side of the cube.
Somewhere, in the past, there's a "popular science" level essay on modern string theory that casually discusses the volume of radius ball and similar geometric implications as regards modern string theory in 10 or 11 dimensions as opposed to bosonic 26 dimensional theory and of course normal human scale 3-D. For example, if, hypothetically, in a very thought experiment manner, you wanted to squirt ping pong ball shaped "things" between packed protons in 3D, the gap would max out at X length whereas in 11D you could squoosh a somewhat larger ping pong ball between the packed gaps or was it actually a denser pack, whatever. Yeah I'm well aware the physics doesn't work that way but it was more of an imaginative geometrical essay.
Sounds like the kind of thing you'd find in an 80s or older "mathematical recreations" column in Scientific American magazine, but its not, or I didn't find it in an index. Which doesn't necessarily mean my inability to find it proves its not there, LOL. But that comparison does accurately relate the general level of casualness and length of the essay and being of general interest to the general educated scientific public.
It was just a fun read, a decade or three ago, and I would merely enjoy reading it again if its free on the net.
Its a typical search problem, searching for terms like "string theory essay" is going to return too much whereas overly specific searches return nothing. So there's some magic middle level of search term complexity that would find it; no idea what those search terms would be, mildly curious HOW anyone finds the article as much as I'm curious about re-reading it.
If nothing else this would be an entertaining 2020's physics blog poster topic or maybe a future xkcd comic LOL.
If you have an n-dimensional integer lattice with unit n-spheres at each even-numbered point, you get inscribed n-spheres. For n = 2, those circles are tiny: about 29% (1-1/sqrt(2)) of the radius of the bigger (r = 1) ones. At n = 3, they're somewhat bigger but still small. At n = 4, they're the same size. At n = 5+, the inscribed n-spheres are actually larger than the unit spheres, which means they extend farther despite being "inscribed". This is probably impossible to visualize, because it's never that way in our 3-dimensional world.
High dimensional spaces also make it difficult to come up with good distance metrics. In 1000+ dimensions, nearly all the volume is on the boundary, and neighborhoods in the classical sense (e.g. visible clusters) don't exist. It's trivial to come up with metrics that "work" but it often requires domain knowledge to come up with ones that are useful.
I find this is an important concept to keep in mind when designing systems and products. When you reach a certain complexity, most cases are edge cases and designing only for the “typical” case serves almost nobody.
> Volume of an n-ball tends to a limiting value of 0 as n goes to infinity
Another way to say this is that if you inscribe a circle in a square, or a sphere in a cube, or in general an n-ball inside an n-cube, then in higher dimensions the n-ball takes up almost none of the space of the n-cube.
I think macro-scale higher dimensions as a hard sci fi topic would also have weird aerodynamic and heat exchanger effects. How would the ratio of radiative cooling to convective cooling vary if the world had 10,11,100,100000000 dimensions instead of 3?
Intuitively if we had 4 dimensions of space I think automotive-type radiators could be quite a bit smaller for a given heat exchange?
A (uniformly) random point in an n-dimensional cube will have random coordinates from zero to 1, with no other constraint on their size.
I think anyone with a basic understanding of arithmetic should be able to answer that.
I think any great teacher can break down many complicated subjects (like the nature of the surface of a higher dimensional sphere) into a series of simpler subjects (if you have to choose a bunch of numbers so they add up to 100, will the numbers tend to be on the small side?), but that in no way implies a person capable of counting change will intuit this series of simpler subjects themselves.
I must ask, somewhat rhetorically, isn't that obvious?
The only frameworks required to reach this conclusion are the Pythagorean theorem (8th grade geometry), the definition of a circle (same), and the ability to generalize the Pythagorean theorem to higher dimensions. I take it this last bit is where you think people would struggle. I don't think so. Looking at the theorem, there are basically 2 ways one might attempt to generalize it, and the incorrect way (a^n + b^n + ... )^(1/n) can be demonstrated to fall on its face pretty easily by considering small values of higher dimensioned components.
I consider these a "basic understanding of arithmetic" as these frameworks have been around for thousands of years and are expected knowledge for the youngest of teenagers. Yes some hand holding may be required to generalize the idea of distance to higher dimensions, but I'd wager not as much as you seem to think.
Testing this is interesting. If a random person at a bar can be given a refresher on the above frameworks and reach the desired conclusion themselves in 5 minutes or less, would you grant the problem is "obvious to people who haven't been trained in college-level mathematical thinking, or people who don't think about higher-dimensional objects using the handlebars of abstraction"?
If you choose n uniformly random values in [-1/2, 1/2] (the unit cube) then the sum of squares will be concentrated around n/12 (just take the variance).
This is way more than 1, which is what you would need to stay inside the unit ball.
It can't be, in the same sense that it's not true that π square meters (the area of a unit circle) is less than (4/3)π cubic meters (the volume of a unit sphere); they are simply not comparable quantities. What is true, as wging very nicely put it (https://news.ycombinator.com/item?id=31349002), is that the (n + 1)-ball (of radius 1) eventually takes up a smaller fraction of the (n + 1)-cube (of side 2) than the n-ball does of the n-cube.
I agree that this is still probably sufficiently unintuitive that the best one can do is to argue why one shouldn't disbelieve it, not to try to make it intuitive; but nonetheless I will share one of the closest things I've seen to an explanation, which is that the number of corners in a cube grows exponentially with the dimension of the cube, so that, sooner or later, the cube is "mostly corners"—and the ball does not poke into the corners.
Volume is the ratio of the n-ball to the n-cube.
Saying that n+1-ball has “smaller volume” than the n-ball is equivalent to saying that the ratio of the n+1-ball to the n+1-cube is smaller than the ratio of the n-ball to the n-cube.
> I understand how the proportional space of an n-ball bounded in an n-cube can go to zero
The volume comment is saying that the ratio of the n-ball to its bounding n-cube goes to zero faster than (base-2) exponential:
The bounding n-cube is 2^n times the unit n-cube.
For r=1
A two-dimensional n-ball is a circle. If you extend it into 3 dimensions, by default it is a cylinder, of h=1 and r=1. That’s not a 3-dimensional n-ball however.
If you increase the dimensions of that 2-dimensional n-ball into 3 dimensions, it becomes a 3-dimensional n-ball—-a sphere of r=1.
And now you have a sphere that is smaller than the circle that was extended into 3 dimensions as a cylinder. The ball-ness of the n-ball formula chopped off the corners of the cylinder.
And that chopping off continues in higher dimensions.
If you have enough circles, they will form a cylinder.
What's surprising is that volume of a n-ball reaches maximum in 5 dimensions and surface of an n-sphere - in 7 dimensions.
A while back, I wanted a way to find the volume of a unit 4-ball without calculus, but I couldn’t find anything. I ended up coming up with the approach below, which uses probability. Comments and criticism welcome.
We want to find the volume of a 4-dimensional unit ball. Let the center of the 4-ball be the origin. Enclose the 4-ball in an origin-centered, axis-aligned 4-dimensional cube of side length 2. Choose a point uniformly at random inside the 4-cube. What is the probability that the point lies within the 4-ball? If we knew this, we could find the volume of the 4-ball, because P[point inside 4-ball] = (volume of 4-ball)/(volume of 4-cube), and we know that the volume of the 4-cube is 2⁴.
We will find P[point inside 4-ball]. Let (a,b,c,d) be the point's coordinates. Since they were picked uniformly at random within the 4-cube and the 4-cube's coordinates range from −1 to 1, we know that a, b, c, and d are each uniformly distributed from −1 to 1 (in symbols: a ~ U(−1,1), b ~ U(−1,1), etc.).
The radius of the 4-ball is 1, so the point is inside the 4-ball just when the radius of the point is less than 1. In symbols:
P[point inside 4-ball] = P[a² + b² + c² + d² < 1].
Since all four terms sum to less than 1, surely the first two do as well. Therefore, we have:
P[point inside 4-ball] = P[a² + b² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1]
The last two terms must also sum to less than 1, so we have:
P[point inside 4-ball] = P[a² + b² < 1] P[c² + d² < 1] P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1]
Now a lemma: Suppose x ~ U(−1,1) and y ~ U(−1,1). Then P[x² + y² < 1] = π/4.
Proof: Since x ~ U(−1,1) and y ~ U(−1,1), P[x² + y² < 1] is the probability that (x,y) lies within an open unit disc, given that it lies within the enclosing 2x2 square. This is simply the area of a unit disc divided by the area of the enclosing 2x2 square, so we have P[a² + b² < 1] = π/4. Similarly for the probability that c² + d² < 1.
Using the lemma on the first two factors, we have:
P[point inside 4-ball] = (π/4)(π/4)P[a² + b² + c² + d² < 1 | a² + b² < 1 ∧ c² + d² < 1]
Now for a second lemma: Suppose x ~ U(−1,1), y ~ U(−1,1), and x² + y² < 1. Then x² + y² ~ U(0,1).
Proof: The assumptions can be visualized as throwing a dart randomly at an origin-centered unit disc enclosed in an origin-centered, axis-aligned 2x2 square. If the dart falls outside the disc, we throw again, until it falls within the disc.
Let (x,y) be the coordinates of the point, and consider the probability that the point falls inside an origin-centered disc of area A, where 0 ≤ A < π (the area of the outer unit disc). This happens just when the radius of the point (the distance from it to the origin) is less than the radius of the inner circle. The radius of the point is √(x² + y²), and the radius of the inner circle is √(A/π). Therefore, the desired probability is P[√(x² + y²) < √(A/π)]. Squaring both sides yields P[point inside disc of area A] = P[x² + y² < A/π].
Since the area of the inner disc is A and the area of the enclosing unit disc is π, we have P[point inside disc of area A] = A/π, or P[x² + y² < A/π] = A/π, for 0 ≤ A/π ≤ 1. By the definition of a uniform distribution over the reals, P[X < x] = x for 0 ≤ x ≤ 1 if and only if X ~ U(0,1). Hence, we have shown that x² + y² ~ U(0,1).
Now back to the main problem. Write u = a² + b² and v = c² + d². Since a ~ U(−1,1), b ~ U(−1,1), and a² + b² < 1, we know, by the second lemma, that a² + b² ~ U(0,1). Similarly, we know that c² + d² ~ U(0,1). Therefore, we can write:
P[point inside 4-ball] = (π/4)(π/4)P[u + v < 1 | u ~ U(0,1) ∧ v ~ U(0,1)]
The value of the probability expression in that formula is simply the area below the triangle in a square, or 1/2, so we have:
P[point inside 4-ball] = (π/4)(π/4)(1/2) = π²/32
Applying this to our original formula yields:
(volume of unit 4-ball) = (π²/32)×(2⁴) = π²/2.
P[point inside 2n-ball] = (π/4)^n P[x1 + x2 + ... + xn < 1 | x ~ U([0,1]^n)]
Instead of the area below a triangle we have the volume inside a unit simplex, or 1/n!, and of course the volume of the 2n-cube is 2^(2n) or 4^n, giving the 2n-ball’s volume as:
(π/4)^n 4^n / n! = π^n / n!
Simple single-variable calculus would be acceptable, like finding the area under the curve y = 1 – √x when x ranges from 0 to 1, but I’d prefer to avoid nested integrals and trigonometric integrals and derivatives.
double nbv[27];
double nss[27];
// n-ball volume constants (index is exponent and n-ball dimension)
// nbv[n] = nss[n-1]/n (n > 0)
// nbv[n] = 2pi * nbv[n-2]/n (n > 1)
nbv[0]= 1.0;
nbv[1]= 2.0;
nbv[2]= M_PI;
nbv[3]= 4.0 * M_PI / 3.0;
nbv[4]= pow(M_PI, 2.0) / 2.0;
nbv[5]= 8.0 * pow(M_PI, 2.0) / 15.0;
nbv[6]= pow(M_PI, 3.0) / 6.0;
nbv[7]= 16.0 * pow(M_PI, 3.0) / 105.0;
nbv[8]= pow(M_PI, 4.0) / 24.0;
nbv[9]= 32.0 * pow(M_PI, 4.0) / 945.0;
nbv[10]= pow(M_PI, 5.0) / 120.0;
nbv[11]= 64.0 * pow(M_PI, 5.0) / 10395.0;
nbv[12]= pow(M_PI, 6.0) / 720.0;
nbv[13]= 128.0 * pow(M_PI, 6.0) / 135135.0;
nbv[14]= pow(M_PI, 7.0) / 5040.0;
nbv[15]= 256.0 * pow(M_PI, 7.0) / 2027025.0;
nbv[16]= pow(M_PI, 8.0) / 40320.0;
nbv[17]= 512.0 * pow(M_PI, 8.0) / 34459425.0;
nbv[18]= pow(M_PI, 9.0) / 362880.0;
nbv[19]=1024.0 * pow(M_PI, 9.0) / 654729075.0;
nbv[20]= pow(M_PI, 10.0) / 3628800.0;
nbv[21]=2048.0 * pow(M_PI, 10.0) / 13749310575.0;
nbv[22]= pow(M_PI, 11.0) / 39916800.0;
nbv[23]=4096.0 * pow(M_PI, 11.0) / 316234143225.0;
nbv[24]= pow(M_PI, 12.0) / 479001600.0;
nbv[25]=8192.0 * pow(M_PI, 12.0) / 7905853580625.0;
nbv[26]= pow(M_PI, 13.0) / 6227020800.0;
// n-sphere surface area constants (index is exponent and n-sphere dimension and n-ball dimension - 1)
// nss[n] = 2pi * nbv[n-1] (n > 0)
nss[0]= 2.0;
nss[1]= 2.0 * M_PI;
nss[2]= 4.0 * M_PI;
nss[3]= 2.0 * pow(M_PI, 2.0);
nss[4]= 8.0 * pow(M_PI, 2.0) / 3.0;
nss[5]= pow(M_PI, 3.0);
nss[6]= 16.0 * pow(M_PI, 3.0) / 15.0;
nss[7]= pow(M_PI, 4.0) / 3.0;
nss[8]= 32.0 * pow(M_PI, 4.0) / 105.0;
nss[9]= pow(M_PI, 5.0) / 12.0;
nss[10]= 64.0 * pow(M_PI, 5.0) / 945.0;
nss[11]= pow(M_PI, 6.0) / 60.0;
nss[12]= 128.0 * pow(M_PI, 6.0) / 10395.0;
nss[13]= pow(M_PI, 7.0) / 360.0;
nss[14]= 256.0 * pow(M_PI, 7.0) / 135135.0;
nss[15]= pow(M_PI, 8.0) / 2520.0;
nss[16]= 512.0 * pow(M_PI, 8.0) / 2027025.0;
nss[17]= pow(M_PI, 9.0) / 20160.0;
nss[18]= 1024.0 * pow(M_PI, 9.0) / 34459425.0;
nss[19]= pow(M_PI, 10.0) / 181440.0;
nss[20]= 2048.0 * pow(M_PI, 10.0) / 654729075.0;
nss[21]= pow(M_PI, 11.0) / 1814400.0;
nss[22]= 4096.0 * pow(M_PI, 11.0) / 13749310575.0;
nss[23]= pow(M_PI, 12.0) / 19958400.0;
nss[24]= 8192.0 * pow(M_PI, 12.0) / 316234143225.0;
nss[25]= pow(M_PI, 13.0) / 239500800.0;
nss[26]=16384.0 * pow(M_PI, 13.0) / 7905853580625.0;