Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New sphere-packing record stems from an unexpected source

quantamagazine.org

Post reply on HN
Print view View original

211–220 of 226 posts

Re: New sphere-packing record stems from an unexpected source

#211

Post by dotancohen »

Scene_Cast2 wrote: post #170
dotancohen wrote: post #100

Earlier quoted context omitted.

I see, thank you. Another thing that I'm sure you explored, and I'd love to hear how it went, would be to rearrange the elements in the vectors such that perhaps the denser parts could be more contiguous, and the sparser parts could be more contiguous, on average. That sounds like something that would be easier to compress. Were the distributions such that a rearrangement like this might have been possible? Or were t…

What ended up launching is a fancy product quantization based on k-means. Some of the tricks were storing magnitude separately (i.e. removing the mean) and rearranging dimensions based on variance (and/or rotation based on PCA) for PQ to work better. I also remember trying to fit a distribution so that I can generate synthetic data (not for a lack of data, but more for understanding the problem space better). The syn…

I was just wondering, it seems like an interesting problem to explore.

Re: New sphere-packing record stems from an unexpected source

#212

Post by godelski »

Someone wrote: post #159

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, an…

  > how weird large-dimensional space is
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.
[0] https://math.stackexchange.com/a/2286226

[1] http://www.geom.uiuc.edu/~banchoff/Flatland/

[2] https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-s...

[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

Re: New sphere-packing record stems from an unexpected source

#213

Post by [deleted] »

Dylan16807 wrote: post #171
zmgsabst wrote: post #123

Earlier quoted context omitted.

As I pointed out, eg, the high number of correction terms when trying to tune the model to actual particle accelerator data is evidence that our model is missing something. (And some things are plain missing: neutrino behavior, dark matter, dark energy, etc.) In the same way that a high number of epicycles was evidence our theory of geocentrism was wrong — even though adding epicycles did compute increasingly accurat…

The comment you originally replied to was about entanglement, not the entire standard model. The math there is very simple, not built on correction terms.

[deleted]

Re: New sphere-packing record stems from an unexpected source

#214

Post by williamscales »

SubiculumCode wrote: post #196
kazinator wrote: post #145

Earlier quoted context omitted.

> Hell, most “dumb” people understand, recognize, and appreciate this ability. That remark reminds me of all the praise heaped by commenters onto videos that explain complex topics glibly. Like "I've been struggling to understand this for 20 years, until this video", etc.

Except, when, which is often the case in mathematics, there is actual way to reduce the complexity of a topic to be understandable to most people without sacrificing veracity for digestible half truths.

I’m reminded of Feynman’s answer on explaining magnetism.

In other words, ICP were not so far off base when they asked “magnets, how do they work?”

Re: New sphere-packing record stems from an unexpected source

#215

Post by godelski »

ivanbakel wrote: post #209
HappMacDonald wrote: post #207

Earlier quoted context omitted.

> (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.

Citation(s):

https://en.wikipedia.org/wiki/Volume_of_an_n-ball

https://en.wikipedia.org/wiki/Hypercube

Re: New sphere-packing record stems from an unexpected source

#216

Post by krnsll »

Sure Klartag isnt a sphere packing specialist by training, but he's one of the best problem solvers around. He just resolved the Hyperplane Conjecture earlier this year and has contributed to progress on related problems in convexity theory such as: KLS Conjecture, Mahler Conjecture, Central Limit Theorem for Convex Bodies, to name a few. His student Eldan's work on Stochastic Localization has also proven critical in log-concave sampling algorithms (related to the KLS conjecture, and he gave a talk at the ICM).

Also, the toolkit one uses in convex geometry, especially some of the harmonic analysis tools are quite handy in the study of sphere packing.

So "unexpected"? Not quite.

Re: New sphere-packing record stems from an unexpected source

#217

Post by bumby »

dghughes wrote: post #179
falcor84 wrote: post #177

Earlier quoted context omitted.

and I'm reminded of this xkcd about the pattern of lights: https://xkcd.com/722/

I've often thought how my cat must think I am insane. I sit in from of a medium-sized glowing rectangle, I occasionally look at a small glowing rectangle, then in the evening stare at a really large glowing rectangle.

I’ve thought the same about our dogs when we stare for hours at “the light box.”

I wonder if it’s anything like what I feel when I watch them sniff the same bush for a seemingly endless amount of time like it’s the most interesting thing in the world.

Re: New sphere-packing record stems from an unexpected source

#218

Post by IncRnd »

TimTheTinker wrote: post #174
IncRnd wrote: post #48

Earlier quoted context omitted.

Hmmmm, what might Feynman say about a horse? So, what's a horse? Well, you look at it: it’s this big animal, standing on four legs, with muscles rippling under its skin, breathing steam into the cold air. And already — that’s amazing. Because somehow, inside that animal, grass gets turned into motion. Just grass! It eats plants, and then it runs like the wind. Now, let’s dig deeper. You see those legs? Bones and tend…

Sounds like an LLM's impression of Feynman.

It does seem that way, doesn't it. Feynman passed away 37 years ago, so he wasn't available for this.

Re: New sphere-packing record stems from an unexpected source

#219

Post by fraserphysics »

meindnoch wrote: post #190
fraserphysics wrote: post #189

Don't Shannon's channel coding theorem and rate-distortion theorem establish bounds on possible sphere packing?

That's in Z_{2}^n, not in R^n.

I think the result for Gaussian channels is in R^n.

Re: New sphere-packing record stems from an unexpected source

#220

Post by jacobolus »

shkkmo wrote: post #198
jacobolus wrote: post #122

Earlier quoted context omitted.

Perhaps so. If you hunt you might be able to find a new summary table somewhere (I didn't find one in a very brief skim around). My impression was this new work was more about high-dimensional cases than necessary a dramatic improvement for every low-dimensional example.

I mean, it says it directly in the article: > His result has also revived a debate in the field about the nature of the optimal packing in arbitrarily high dimensions. For a while, mathematicians considered highly symmetric, lattice-based packings to be the best way to arrange spheres as densely as possible. But in 2023, a team found a packing that didn’t rely neatly on a repeating lattice; before Klartag’s result, i…

If you click through to the link from your quoted sentence, the 2023 paper "provided a new recipe for how to densely pack spheres in all arbitrarily high dimensions", and from the description the new paper also seems to address the same question.

This is different from asking about the best-known specific packing in n dimensions when n = 7, 10, 19, or whatever.

In a few of the specific low dimensional cases, my impression is that the best currently known packing is not regular, and I don't see any evidence that this has changed. Perhaps this new method will give people a way to beat those records, or perhaps not.

Post reply on HN