10 ms·
New sphere-packing record stems from an unexpected source
- tomrod 1y agoVery cool. Sphere packing comes up in a lot of contexts in applied problems. Looking forward to reviewing the paper.
- readthenotes1 1y agoEarlier 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.
- ahns 1y agoThe aforementioned trapezoidal rule (Tai's method): https://diabetesjournals.org/care/article/17/2/152/17985/A-Mathematical-Model-for-the-Determination-of https://diabetesjournals.org/care/article/17/2/152/17985/A-M...
- pinkmuffinere 1y agoI haven't read that thread, but I don't believe that anthropologists thought boiling was impossible before the invention of pottery. Here's one youtube video that demos a method for survival scenarios, I'm sure there are many others: https://www.youtube.com/shorts/0zun_UxO2vU https://www.youtube.com/shorts/0zun_UxO2vU. I know I don't have the context, but unless there are sources for the remarkable claim, it just doesn't make sense. It doesn't pass "the laugh test"
- smallerize 1y agohttps://www.science.org/doi/10.1126/sciadv.adv1257 https://www.science.org/doi/10.1126/sciadv.adv1257 "Underlining earlier work by Speth (61), experiments recently demonstrated that organic perishable containers, e.g., made out of deer skin or birch bark, placed directly on a fire, are capable of heating water sufficiently to process food, with the advantages of wet-cooking beginning at lower, sub-boiling temperatures than thus far acknowledged (62)." Reference 61 goes to this 2015 paper: https://scholar.google.com/scholar_lookup?title=When+did+humans+learn+to+boil%3F&author=J.+D.+Speth&publication_year=2015&journal=PaleoAnthropology&pages=54-67 https://scholar.google.com/scholar_lookup?title=When+did+hum... "to alert archaeologists and others to the fact that one can easily and effectively boil in perishable containers made of bark, hide, leaves, even paper and plastic, placed directly on the fire and without using heated stones."
- pinkmuffinere 1y agoThanks for the link! Not to be argumentative, but I do want to highlight a couple points that I think may be the root misunderstanding: 1. The 2015 paper doesn’t indicate that it was unknown that you can boil water without pottery. It is meant to alert people to an already known fact. Maybe silly, but I do think there’s a distinction here — it’s not that the pinnacle of human knowledge was missing this, it’s that common sense was missing it. I’d compare this to the article “things SDEs assume about names”. Edit: then again, playing devils advocate against myself, the first paper does say “…sub-boiling temperatures than _thus far acknowledged_” (emphasis mine), which would seem to indicate that this was more than just a common misunderstanding. 2. The 2015 paper is not about boiling water in general, it’s about boiling it in a specific way. (Whereas the initial discussion was about boiling water by any method)
- rukuu001 1y agoI know right? If I, as a yokel kid knew this, it astonishes me people like that wouldn’t know it
- stavros 1y agoOh no, did he drink that murky mudwater?! I get it if my life depended on it, but for a demonstration video?! I gagged.
- knicholes 1y agoIf only there were some sort of expert in everything that we could ask, it could pull expertise from all various sciences into one response. I think everyone just needs to start using LLMs.
- knicholes 1y agoBy the way, for anyone down voting, ask o3 if humans could render fat before they had pottery. It takes seconds to find the answer.
- theteapot 1y agoNoob question: Is the optimal sphere packing correlated with a regular lattice? I.e. that's the case for 2D,3D right? If so does this extend to ND?
- fiforpg 1y agoNot necessarily—in 3d there are uncountably many non-lattice packings. They all have the same density as the FCC lattice though. To construct these packings, shift horizontal layers of FCC horizontally with respect to each other. It is conjectured that in higher dimensions, the densest packing is always non-lattice. The rationale being that there is just not enough symmetry in such spaces.
- Jaxan 1y agoWell these new results (denser packings than before) are regular lattices which might suggest that the optimal packing could be a lattice. (Until the record is broken again by a irregular packing ;-)
- jacobolus 1y agoBesides 2 and 3 dimensions, it's also the case in 8 and 24 dimensions (The E₈ lattice and Leech lattice, respectively). These were proven in 2017 by Maryna Viazovska, with some collaborators for the second paper. https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8 https://doi.org/10.4007/annals.2017.185.3.8 See also https://www.ams.org/journals/notices/201702/rnoti-p102.pdf https://www.ams.org/journals/notices/201702/rnoti-p102.pdf For other dimensions, this is an open question; it seems unlikely to be true in general. For some dimensions the densest known irregular packing is denser than the densest known regular packing.
- shkkmo 1y ago> For some dimensions the densest known irregular packing is denser than the densest known regular packing. I thought that was one of the important results from the paper, the most efficient packing for all dimensions is symmetrical again and this increase was significant enough it seems unlikely that existing non-symmetrical methods will be able to beat it.
- clickety_clack 1y agoI 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’.
- dkarl 1y agoI've found it's best to explain my job using unintelligible jargon. There are three choices, really: You can give a quick explanation in terms they understand, which makes your job sound easy and makes them wonder how anybody gets paid to do it. You can explain what you do and why it's important in terms they understand, but it'll take so long they'll get bored and wish they hadn't asked. Or you can give a quick explanation using jargon that they don't understand, which will leave them bored but impressed, which is the best of the bad options.
- tomrod 1y agoI choose the worst of all options and go into excruciating detail.
- bell-cot 1y agoThereby minimizing how often anyone asks you - which makes that the best long-term option?
- EvanAnderson 1y agoThat would only work if you were getting repeat inquiries from the same person. Otherwise it's just the longest possible option for each new inquiry. I always opt for excruciating detail because it's what I enjoy the most.
- bell-cot 1y ago> That would only work if ... Sounds like none of the people you answered, in excruciating detail, cared to warn other people about what would happen if they asked you.
- DonHopkins 1y agoJoey Chestnut?
- vanderZwan 1y agoI'm afraid I don't get the reference :)
- wmeredith 1y agoHe is the world champion of eating hotdogs. He can eat 73 or something. The joke is that he's packing them into his stomach.
- vanderZwan 1y agoThanks!
- Scene_Cast2 1y agoNeat. 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. EDIT: groped -> grouped
- Gregaros 1y ago_May_ be a case for extending out what has been explored by theory to cover more useful ground (or not, depending on whether real-world usecases like yours are too heterogenous for effective general techniques).
- soulofmischief 1y agoYou really shouldn't grope your vectors.
- dotancohen 1y agoRoger, Rodger. Over, Oveur.
- GuinansEyebrows 1y agoyou're Kareem Abdul-Jabar!
- dotancohen 1y agoI'm sure you've already explored this, but is there some precompression operation that you could do to the vectors such that they're no longer sparse, and therefore relatively uniform?
- Scene_Cast2 1y agoThey weren't sparse, they were dense but the "density" was quite non-uniform (think typical learned ML vectors). Not too far from an N-dimensional gaussian (I ended up reading research on quantizing Gaussian distributions, but that didn't help either as we didn't have a perfectly gaussian thing).
- gbxyz 1y ago[flagged]
- layer8 1y agoThis should have practical applications for cow packing in physics.
- NooneAtAll3 1y agodoes anyone know at what lowest dimension does this construction beats known best packing?
- imoreno 1y agoThis 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"
- bGl2YW5j 1y ago"Shrink-and-grow technique for efficiently packing n-dimensional spheres" isn't obtuse enough. I think something like "Hypertopological Constriction-Expansion Dynamics in Quasistatic R^n-Ball Conglomeration" would be even more apt.
- bGl2YW5j 1y agoI 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.
- lupire 1y agoThe delight of pure maths is in its uselessness :-)
- dsp_person 1y ago> 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?
- lupire 1y agoI think not, because moving to a higher dimension is exponentially worse (density ~ n^2/2^n) than this linear improvement. So it's only helpful for naturally high dimensional objects. Digital objects do not have a natural dimension (byte length), so you can choose a small dimension. https://en.m.wikipedia.org/wiki/Sphere_packing https://en.m.wikipedia.org/wiki/Sphere_packing
- tonetegeatinst 1y agoThe addition of a dimension can be thought of as adding another variable or "axis" in simpler terms. Due to the added variable aka axis, you have increased the size of complexity. 2d shapes packed in a 2d boundary vs 3d objects in 3d space. The difference is fitting quarters on a paper vs marbles in a perfect cube. Now imagine having to find the most optimal method of packing for objects of Nth degree in Nth constraint. For example packing object that have 256 dimensional or variables into a constraint that also is 256 of complexity. I feel as your dimension aka variable increases....the amount of information to compute grows quite quickly. We can rule out some things as non optimal or non perfect, but we can also get close to perfection via trial and error. I see this as an example of the traveling salesman issue. Do you stick with a randomly selected answer, do you go with the current most optimal solution, or do you invest time and effort into finding a new solution but you risk finding a worse solution. At the end of the day is the packing efficient gains worth the computational complexity of N dimension of N constraint given it will take an unknown amount of time to find a more efficient packing solution, and the new solution could be anywhere from 0.1% to 80% more efficient.
- yorwba 1y ago
- teleforce 1y ago> 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.
- deadbabe 1y agoCan’t you just montecarlo the hell out of this thing?
- slwvx 1y agoI don't think so. You can't just "Montecarlo the hell" out of a post-quantum cryptographic scheme [1] which are also based on lattices. Even if that analogy isn't quite apt, I don't think looking for a good random lattice is a good way to find the densest possible lattice [2]. [1] https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography [2] https://en.wikipedia.org/wiki/Random_close_pack#For_spheres https://en.wikipedia.org/wiki/Random_close_pack#For_spheres
- crazygringo 1y agoAccording to the article, that's precisely what he did. But he did it in a better way, randomly expanding ellipses. And when you're dealing with hundreds of dimensions, it's incredibly easy to be montecarlo-ing in the wrong directions...
- fcanesin 1y agoI 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.
- vanderZwan 1y agoI feel like most sciences should have this, it would accelerate science a lot via the cross-pollination of ideas and techniques. But I can imagine that drawing connections between different branches of maths would be especially powerful, yes
- karmakurtisaani 1y agoIt's possible! From somewhat famous mathematicians, at least Bela Bollobas has 2 PhDs: one in discrete geometry and one in functional analysis. Try doing that in the modern academic environment tho..
- wyan 1y agoThe purpose of a PhD is to certify that you're able to do independent research. Many researchers retrain (or just add a research interest) in adjacent fields during their postdocs or later. At that point it's just research.
- rando234789 1y agocheck out the idea of a habilitation: https://en.wikipedia.org/wiki/Habilitation https://en.wikipedia.org/wiki/Habilitation at least in germany, it is pretty much what you describe
- aleph_minus_one 1y agoBeside the habilitation example of rando234789 (https://news.ycombinator.com/item?id=44498702 https://news.ycombinator.com/item?id=44498702), in Russia (and Ukraine) there indeed exist two "doctorate levels": кандидат наук [Candidate of Sciences] and доктор наук [Doctor of Science].
- xnsmsjdskw 1y ago[flagged]
- vanderZwan 1y ago> 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. https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB.pdf https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
- tsunamifury 1y agoWhy does this seem incredibly obvious to me?
- paintbox 1y agoProbably because you overestimate your knowledge.
- tsunamifury 1y agoThis doesn’t follow at all. In fact it’s an admission of not understanding. Did you struggle to figure that out?
- ncr100 1y agoPerhaps because the challenge was explained well? Or because "the devil is in the details". The article does mention that phenomenon, deceptive simplicity.
- adityaathalye 1y agoI 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.”
- Someone 1y agoFTA: “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.
- shrx 1y agoThis doesn't hold true for 2 and 3 dimensions, though.
- ted_dunning 1y agoIf it holds for 10 or 20 dimensions, the consequences are still pretty important.
- asboans 1y ago“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.
- sota_pop 1y agoI’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”.
- kibwen 1y agoThere's a great 3blue1brown video that demonstrates this unintuitive result in a relatively intuitive way: https://youtube.com/watch?v=zwAD6dRSVyI https://youtube.com/watch?v=zwAD6dRSVyI
- cellular 1y agoIt said his proof was basically by example. He proved more were possible.
- fraserphysics 1y agoDon't Shannon's channel coding theorem and rate-distortion theorem establish bounds on possible sphere packing?
- meindnoch 1y agoThat's in Z_{2}^n, not in R^n.
- fraserphysics 1y agoI think the result for Gaussian channels is in R^n.
- krnsll 1y agoSure 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.