The volume of a ball of radius r in n dimensions is
B(n,r) = π^{n/2}/Γ(n/2+1) r^n
If you look at the volumes of the balls (blue circles) inscribed inside hypercubes with edge length 1 and volume 1, they go to zero as n gets larger:
lim n→∞ B(n,½) = 0
If you look at the volumes of the balls (red circles) that circumscribe each hypercube (of diagonal √n), they go to infinity:
lim n→∞ B(n,½√n) = ∞
But what if you always choose the radius of an n-ball so that its volume is exactly 1 (green circles)?
r₁(n) = Γ(n/2+1)^{1/n} / √π
This gives us B(n,r₁(n)) = 1
It turns out that:
lim n→∞ (r₁(n) - √[n/(2eπ)]) = 0
In other words, r₁(n) is asymptotic to a multiple of √n, so it approaches a fixed ratio with the length of the diagonal of the hypercube with the same volume.
@gregeganSF Asymptotics for the volume of the regular hypersimplex were computed by Böröczky and Henk, it's a nontrivial exercise in asymptotic integration IIRC
@dimpase This seems to be for spherical geometry, which is (presumably) much harder than the Euclidean case, because I just did the Euclidean case pretty easily, albeit with a little help from Mathematica.
The circumradius of a regular n-simplex of unit volume is asymptotic to n/e.
I was wondering if it would be proportional to √n, like the n-cube and n-ball, but no, it really is fundamentally different.
@gregeganSF it's about the intersection of a regular simplicial cone with the hypersphere, I think. In this context it's relevant to randomised rounding used in semidefinite optimisation-based approximation algorithms for combinatorial problems, such as MAX CUT.
It’s kind of hilarious how finicky limits can be when there are exponents that go to infinity.
Even though we have the identity:
B(n,r₁(n)) = 1
and the limit:
lim n→∞ (r₁(n) - √[n/(2eπ)]) = 0
it turns out that:
lim n→∞ B(n, √[n/(2eπ)]) = 0
rather than 1, as you might hope.
The approximation of r₁(n) by √[n/(2eπ)] just gets better and better as n gets larger ... but it doesn’t get better fast enough for the small discrepancy to stay small after raising both numbers to the nth power and computing the volume of the n-ball.
@gregeganSF - I wonder what it would be like if we lived in 1,000,000-dimensional space. I guess there's a lot of evidence that life can't exist in such high dimensions, but if we did... we'd probably have very different intuitions about geometry, what's weird and what's normal.
@OscarCunningham - yes, it's hard to imagine an easy experiment to exactly determine the dimensionality of this space it's so high... not that I know what anything would feel like in such a reality.
"if we lived in 1,000,000-dimensional space. I guess there's a lot of evidence that life can't exist in such high dimensions,"
Max Tegmark wrote a 1997 paper that was an excellent exploration of that, although it had D > big, not D = 1,000,000
"On the dimensionality of spacetime", M Tegmark 1997, Classical and Quantum Gravity, 14, L69-L75
Splash page that links to paper, because it has a nice graph that serves to summarize at a glance (# time dimensions versus # space dimensions versus viability/nonviability for life and indeed matter):
@dougmerritt - I just meant that someone can think a paper is "famous" without having any external evidence that it's famous. I see I blogged about Tegmark's work in "week146", back in 2000:
"Dimensionally cursed phenomena occur in domains such as numerical analysis, sampling, combinatorics, machine learning, data mining and databases. The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. In order to obtain a reliable result, the amount of data needed often grows exponentially with the dimensionality. Also, organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. "
@narain To be honest, I was being a bit sloppy; the ratio between the circumradius of a unit-volume orthoplex and n/(2e) goes to 1, but to make the difference go to zero you need to use:
(n + log(√[2π n]))/(2e)
But the dominant term is still linear in n.
For the simplex, to make the difference go to zero you also need to add a correction to n/e, but in that case it’s a constant term, not logarithmic.
Add comment