Earlier today there was an article about neanderthal's rendering fat.
The comments pointed out that anthropologist did not know that boiling was possible before the invention of pottery. Another comment pointed out that science teachers knew that it was possible because that was something they would do in class.
Final comment was about how people ReDiscover things in different fields - - like the trapezoidal rule for integration being discovered by someone studying glucose.
This is just yet another example of how bringing expertise from a different area can help.
I have trouble explaining to my parents how my job is a real thing. I can only imagine trying to explain ‘I study shapes, but only ones that don’t jut inwards’.
Neat. I spent a month trying to use sphere packing approaches for a better compression algorithm (I had a large amount of vectors, they were grouped through clustering). Turned out that theoretical approaches only really work for uniform data and not any sort of real-world data.
This was a very confusing article, full of filler. I couldn't stand to read the "detective story" style.
Sounds like the technique is for high-dimensional ellipsoids. It relies on putting them on a grid, shrinking, then expanding according to some rules. Evidently this can produce efficient packing arrangements.
I don't think there's any shocking result ("record") for literal sphere packing. I actually encountered this in research when dynamically constructing a codebook for an error-correcting code. The problem reduces to sphere packing in N-dim space. With less efficient, naive approaches, I was able to get results that were good enough and it didn't seem to matter for what I was doing. But it's cool that someone is working on it.
A better title would have been something like: "Shrink-and-grow technique for efficiently packing n-dimensional spheres"
I hated maths as a kid, now I love this stuff; pure maths for its own sake. Super impressive! It's a dream of mine to discover anything useful in the field.
> For a given dimension d, Klartag can pack d times the number of spheres that most previous results could manage. That is, 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.
Those numbers sound wild. For various comms systems does this mean several orders of magnitude bandwidth improvement or power reduction?
> The answer matters for potential applications to cryptography and communications
Someone can take this challenge to provide a more secure and reliable communication systems hopefully with more energy efficiency, very much an exciting research direction.
I feel like mathematicians should be able to do a second doctorate level degree a few years after their first PhD, that must be in a adjacent field of their own, but not the same.
> Klartag is convinced that this makes them extremely powerful: Convex shapes, he argues, are underappreciated mathematical tools.
I agree with this and I'm not even a mathematician, I've seen convex hull algorithms pop up in unexpected places to solve problems I would never have thought of using convex hull algorithms for, like a paper on automatic palette decomposition of images.
I wonder; is this essentially why LLM tech is useful for certain Fields-medal level problems? i.e. because the LLM search construct has no barrier between sub-fields; nor between distant ones? Only multiple likely paths?
In context of packing problem, it's a bit meta to me...
An LLM contains a k-dimensional packing of known knowledge. This packing is highly inefficient because it has holes and unbridged dimensions. By injecting random seed (prompts) into the LLM probability space, it gets perturbed. Sometimes this perturbation fills a hole in the packing and/or connects two adjacent units in way nobody thought of before because it wasn't fashionable any more, or wasn't top of mind. Thus new knowledge is created within the same k-dimensional box through a novel joining-of of existing know-how.
From the article:
> Klartag had broken open a central problem in the world of lattices and sphere packing after just a few months of study and a few weeks of proof writing. “It feels almost unfair,” he said. But that’s often how mathematics works: Sometimes all a sticky problem needs is a few fresh ideas, and venturing outside one’s immediate field can be rewarding. Klartag’s familiarity with convex geometry, usually a separate area of study, turned out to be just what the problem required. “This idea was at the top of my mind because of my work,” he said. “It was obvious to me that this was something I could try.”
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.
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
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.
25 comments
[ 0.22 ms ] story [ 39.4 ms ] threadThe comments pointed out that anthropologist did not know that boiling was possible before the invention of pottery. Another comment pointed out that science teachers knew that it was possible because that was something they would do in class.
Final comment was about how people ReDiscover things in different fields - - like the trapezoidal rule for integration being discovered by someone studying glucose.
This is just yet another example of how bringing expertise from a different area can help.
EDIT: groped -> grouped
Sounds like the technique is for high-dimensional ellipsoids. It relies on putting them on a grid, shrinking, then expanding according to some rules. Evidently this can produce efficient packing arrangements.
I don't think there's any shocking result ("record") for literal sphere packing. I actually encountered this in research when dynamically constructing a codebook for an error-correcting code. The problem reduces to sphere packing in N-dim space. With less efficient, naive approaches, I was able to get results that were good enough and it didn't seem to matter for what I was doing. But it's cool that someone is working on it.
A better title would have been something like: "Shrink-and-grow technique for efficiently packing n-dimensional spheres"
Those numbers sound wild. For various comms systems does this mean several orders of magnitude bandwidth improvement or power reduction?
Someone can take this challenge to provide a more secure and reliable communication systems hopefully with more energy efficiency, very much an exciting research direction.
I agree with this and I'm not even a mathematician, I've seen convex hull algorithms pop up in unexpected places to solve problems I would never have thought of using convex hull algorithms for, like a paper on automatic palette decomposition of images.
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
In context of packing problem, it's a bit meta to me...
An LLM contains a k-dimensional packing of known knowledge. This packing is highly inefficient because it has holes and unbridged dimensions. By injecting random seed (prompts) into the LLM probability space, it gets perturbed. Sometimes this perturbation fills a hole in the packing and/or connects two adjacent units in way nobody thought of before because it wasn't fashionable any more, or wasn't top of mind. Thus new knowledge is created within the same k-dimensional box through a novel joining-of of existing know-how.
From the article:
> Klartag had broken open a central problem in the world of lattices and sphere packing after just a few months of study and a few weeks of proof writing. “It feels almost unfair,” he said. But that’s often how mathematics works: Sometimes all a sticky problem needs is a few fresh ideas, and venturing outside one’s immediate field can be rewarding. Klartag’s familiarity with convex geometry, usually a separate area of study, turned out to be just what the problem required. “This idea was at the top of my mind because of my work,” he said. “It was obvious to me that this was something I could try.”
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.
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:
[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
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.