FTA: “in 100-dimensional space, his method packs roughly 100 times as many spheres; in a million-dimensional space, it packs roughly 1 million times as many“
Nice example of how weird large-dimensional space is. Apparently, when smart minds were asked to put as many 100-dimensional oranges in a 100-dimensional crate as they could, so far, the best they managed to do was fill less than 1% of its space with oranges, and decades of searching couldn’t find a spot to put another one.
“Fill less than 1% of its space” becomes a very counter intuitive statement in any case when discussing high dimensions. If you consider a unit n-sphere bounded by a unit cube, the fraction occupied by the sphere vanishes for high n. (Aside: Strangely, the relationship is non monotonic and is actually maximal for n=6). For n=100 the volume of the unit 100-sphere is around 10^-40 (and you certainly cannot fit a second sphere in this cube…) so its not surprising that the gains to be made in improving packing can be so large.
> (Aside: Strangely, the relationship is non monotonic and is actually maximal for n=6)
For this aside I crave a citation.
When n=1 the sphere fit is 100% as both simplex and sphere are congruent in that dimension. And dismissing n=0 as degenerate (fit is undefined there I suppose: dividing by zero measure and all that) that (first) dimension should be maximal with a steady decline thereafter thus also monotonic.
This looks to have been a conflation by the GP between the volume of the unit sphere itself and its ratio to the volume of its bounding cube (which is not the unit cube.) The volume of the sphere does top out at an unintuitive dimension, but indeed the ratio of the two is always decreasing - and intuitively, each additional dimension just adds more space between the corners of the cube and the face of the sphere.
You don't need to involve the hypercube at all. You can just look at the volume of a hypersphere (n-ball). The dimension where the maximal volume of the n-ball lives depends on the radius, and for the unit n-ball, the max is at 5D, not 6D. As D->inf, then V->inf too.
This relationship doesn't happen to the hypercube btw. Really, it is about the definition of each object. The volume of the hypercube just continues to grow. So of course the ratio is going to explode...
As an extra fun tidbit, I'll add that when we work with statistics some extra wildness appears. For example, there is a huge difference between the geometry of the uniform distribution and the gaussian (normal) distribution, both of which can be thought of as spheres. Take any two points in each distribution and draw a line connecting them and interpolate along that line. For the unit distribution, everything will work as expected. But for the gaussian distribution you'll find that your interpolated points are not representative of the distribution! That's because the normal distribution is "hollow". In math speak, we say "the density lies along the shell." Instead, you have to interpolate along the geodesic. Which is a fancy word to mean the definition of a line but aware of the geometry (i.e. you're traveling on the surface). Easiest way to visualize this is thinking about interpolating between two cities on Earth. If you draw a straight line you're gonna get a lot of dirt. Instead, if you interpolate along the surface you're going to get much better results, even if that includes ocean, barren land, and... some cities and towns and other things. That's a lot more representative than what's underground.
I’m familiar with this example of hyper-geometry. Put more abstractly, my intuition always said something like “the volume of hyper geometric shapes becomes more distributed about their surface as the number of dimensions increases”.
It's rather crazy that we humans can't really even intuit about a single extra dimension. Or even a single fewer! There's a lot of people who will say that they can visualize things in the 4th dimension but I've yet to find someone who can actually do this. This includes a large number of mathematicians (it's never the mathematicians that claim this...)
I really like the animation in this Math Overflow post[0], because it has a lot of hidden complexity that most people don't think about. The animation is actually an illusion, and you are "hallucinating". That top image projecting a cube down onto a plane? Well... that isn't a cube. We've already projected the cube into 2D! Technically this is 3D. But the 3rd dimension isn't a spacial dimension, it is a time dimension. Which itself is a helpful lesson in learning about the abstraction of dimensions! So we hallucinate a cube, rotating, and then see the projected image on a plane, which we hallucinate as a square that isn't skewed but instead has depth. This is all rather wild in of itself.
The truth is that we struggle to imagine 2D! And most people will claim to be able to visualize 2D and the claim will go uncontested.
If you haven't read Flatland[1], I'd encourage everyone to do so. A lot of people get it wrong. They read it as an analogy 1 dimension down. Where we 3 dimensional creatures are analogous to the 2D creatures and a 4D creature would be as baffling as a 3D creature is to the Flatlander. While that is true, there is a trick being played on you. You think understanding 2D is really easy. But I guarantee you what you're visualizing is inaccurate. Frankly, the book isn't perfectly accurate either.
But really put yourself in the Flatlander's shoes. In a real Flatlander's shoes, not the ones of the book. Be the Square Flatlander and imagine yourself looking at a Triangle. What do you see? I'm betting it is a line? But this is incorrect. You've given it thickness, you've given it a third dimension. Try this again and again, adding more depth and challenging yourself to imagine a real Flatland. You'll find you can't.
Instead, we can visualize and reason about a 2D space embedded within 3D. You might say I'm being nitpicky here, but if I weren't then it would be perfectly fine to say that this[2,3] is a 4-dimensional hypercube instead of a representation of a 4D hypercube.
I actually think understanding this goes a long way to help understanding very high dimensions. If you are forced to face the great difficulty of accurately visualizing one more or one fewer dimension, you are less likely to fool yourself when trying to reason about much higher dimensions.
And as Feynman once said:
The first principle is that you must not fool yourself and you are the easiest person to fool.
[3] Good video of Carl Sagan where he holds a 3D projection of the hypercube. The shadow. But anything I show you has to be embedded in 2D... He picks it up at 6:20 https://www.youtube.com/watch?v=UnURElCzGc0
Nice example of how weird large-dimensional space is. Apparently, when smart minds were asked to put as many 100-dimensional oranges in a 100-dimensional crate as they could, so far, the best they managed to do was fill less than 1% of its space with oranges, and decades of searching couldn’t find a spot to put another one.