Four mathematicians broke a 75-year record by finding a denser way to stack high-dimensional spheres.
撰文 | Kelsey Houston-Edwards
翻译 | zzllrr小乐
Mathematicians like to generalize concepts to higher dimensions. Sometimes it's easy.
If you want to quickly stack 2D squares on top of each other, you can arrange them like a chessboard. If you want to put 3D cubes together, you can stack them like boxes. Mathematicians can easily extend these permutations, stacking cubes in higher-dimensional space so that they fill the space perfectly.
It is much more difficult to stack spheres. Mathematicians know how to stack circles (or footballs) together so that the gaps between them are minimal. But in four or more dimensions, the densest stacking scheme is a complete mystery. (Except for the 8-dimensional and 24-dimensional that were resolved in 2016.) ）
"It sounds simple," says Julian Sahasrabudhe, a mathematician at the University of Cambridge. "There could be 20 different ways to go about this. That's what seems to happen – there are a lot of different ideas. ”
The densest known 2-, 3-, 8-, and 24-dimensional sphere stacks look like "lattices", full of graphics and symmetry. But in other dimensions, the best stack can be completely chaotic.
"I think that's the very enticing side of the question. It's a really open question," said Akshay Venkatesh, a mathematician at the Institute for Advanced Study (IAS) in Princeton. "We just don't know the answer."
In December 2023, Sahasrabudhe, along with his colleagues Marcelo Campos in Cambridge, Matthew Jenssen at King's College London, and Marcus Michelen at the University of Illinois at Chicago, offered a new approach to how to stack spheres in the densest possible range of all arbitrary dimensions. [1] This was the first major development in 75 years on the problem of general sphere accumulation.
"It's a beautiful piece of math," said Yufei Zhao, a mathematician at the Massachusetts Institute of Technology. "There are new, groundbreaking ideas."
Improve baselines
The tightest way to arrange circles on a two-dimensional plane is to adopt a hexagonal pattern, placing the circles at the corners and centers of each hexagon. Such a mesh fills more than 90% of the plane.
图源:Samuel Velasco/Quanta Magazine
In 1611, the physicist Johannes Kepler (1571-1630) came up with the idea of an optimal way to stack three-dimensional spheres. For the base layer, he stacked the spheres in a hexagonal arrangement, like a circle.
He then placed a second sphere on top of the first sphere, filling the gap. But then a choice needs to be made. The third layer can be directly above the first layer:
Or you can offset it a bit:
In both cases, the stacking pattern is repeated; And the amount of space that the sphere fills is exactly the same: about 74%.
In 1831, Carl Friedrich Gauss (1777-1855), one of the most prominent mathematicians of the 19th century, proved that Kepler's configuration was the best lattice (repeated grid structure), but he could not rule out the possibility of some kind of irregular arrangement, since it could have been a denser stack (a possibility that was eventually ruled out at the turn of the millennium).
In the higher dimensions, mathematicians are helpless. Then, in 2016, Maryna Viazovska (1984-) used the existence of symmetry peculiar to eight-dimensional space to prove that a particular lattice is optimal. She also works with collaborators to generalize proof to 24 dimensions. She received the 2022 Fields Medal for this work, the highest award in mathematics. (Editor's note: See "Overcoming the Problem of Ball Accumulation in the High-Dimensional Version - Ukrainian Female Mathematician Wins the 2022 Fields Medal" and "Ramanujan's Resurrection Can Only Be Solved": E₈ Grid and the Ball Loading Problem)
Henry Cohn, a mathematician at Microsoft Research, said, "One of the things I like about [ball stacking] is that it's a thread that connects many different fields in mathematics, computer science, and physics. "He worked with Viazovska on the 24-dimensional proof.
These known optimal accumulations—1-, 2-, 3-, 8-, and 24-dimensional—do not seem to generalize to higher dimensions. In higher dimensions, mathematicians don't know how much percentage of space the optimal arrangement will fill. Instead, they tried to approximate it.
In any dimension, if you start with a very large box and then fill it with balls in succession, sticking a ball where you find an opening large enough - then the sphere will occupy at least 1/2 of the box's volume, where d is the dimension of space. So, in 2 dimensional spaces, they will fill at least 1/4 of the space, while in 3 dimensions, they will fill at least 1/8 of the space, and so on. In relatively small dimensions, mathematicians usually know that a particular stack is much better than this general limit (e.g., Kepler's 3-dimensional stack occupies 74% of the space, far more than the lowest of 12.5%). But the 1/2d baseline is useful because it applies to all dimensions. ）。
左起Marcus Michelen、Marcelo Campos、Julian Sahasrabudhe和Matthew Jenssen,在Sahasrabudhe的剑桥办公室,在为期一个月的访问的最后一天,他们打破了保持了75年的装球堆积记录。 丨图源:Julia Wolf
"It's a kind of baseline," Mr. Zhao said. Slow progress in establishing a better baseline for generalization to any dimension.
In 1905, mathematician Hermann Minkowski (1864-1909) demonstrated that in any dimension, there is a lattice that can fit twice the number of balls from the baseline by placing a sphere at each point on the lattice.
The next substantial advance occurred in 1947, when the British mathematician Claude Ambrose Rogers (1920-2005) proposed a better lattice. Minkowski's improvement on the baseline is through a constant factor, while Rogers' scheme is an "asymptotic" improvement of the baseline, meaning that as the number of dimensions increases, so does the difference in stacking efficiency. In the 50th dimension, Rogers can stack about 50 times the space of the baseline, but in the 1000th dimension, he stacks about 1000 times the baseline.
Over the past 75 years, there have been some results that have resulted in a constant-fold improvement in Rogers' stacking, but until now, no one has been able to find an asymptotic improvement that works in all dimensions.
Tie the dots
Campos, Jenssen, Michelen and Sahasrabudhe began working together early in the pandemic, meeting for hours a day on Zoom — though they didn't discuss it at first. They co-authored three papers before meeting for the first time in the fall of 2023, when Jenssen and Michelen came to Cambridge for a month-long visit. At this point, they set their sights on the ball stacking problem.
"In that time, we just started and then basically finished the ball stacking problem," Michelen said. "It's definitely very fast, and in a way, it's a bit unexpected.
Maryna Viazovska使用8维和24维特有的对称性来证明最密装球堆积的存在性。 丨图源:2022 EPFL/Fred Merz – CC-BY-SA 4.0
Mathematicians solve this problem using graph theory, which is a collection of vertices (points) connected by edges (lines). Graphs are often used in combinatorics and probability theory, which is the main area of research of the authors mentioned above. Almost all of the lower limits of the spherical density come from the study of the lattice structure. But recent papers use graph theory to create highly disordered stacking – a very different approach.
"When we first started talking about it, it seemed a little scary," Sahasrabudhe said. "We realized that we could model it as a graph. Then we started to feel more at ease. ”
To create the pile, they first scatter points randomly in space. These points will eventually become the center of the stacked sphere. They then draw a line between any two points that are too close to each other, and spheres centered on those two points will overlap.
From this graph, they want to extract an independent set, i.e., a set of vertices where no two vertices are connected by an edge, as shown by the red dot in the image below. If they draw balls on all the points of the independent set, the balls will not overlap. This creates a kind of ball-loading pile.
It's easy to create a sparse independent set by grabbing a few vertices from areas in the graph that are far apart. However, to make a dense ball stack containing as many balls as possible, they need a very large set of free-standings. Their challenge was to extract a separate set using most of the vertices in the original graph.
To do this, they used a technique called Rödl nibble, a method close to a random greedy algorithm, in which fragments of graphs are iteratively deleted (or "nibble").
"It's a super impactful technology," Sahasrabudhe said. "It dates back to the '80s, but you've really been honing it for the last 10 to 15 years."
They first traverse each vertex in the graph. At each point, they toss (figuratively) a coin, which weighs a lot on the reverse side. If the flip of the coin falling is the tail, they do nothing. If it falls heads, they delete the vertex and add it to a new graph.
This "Nibble" process creates a separate set using a relatively small portion of the original graph. But this independent set is not large enough. So, they repeated the process, "cannibalizing" more parts from the original diagram and adding them to the new diagram. In the end, they got a large independent set of primitive graphs, and that's exactly what they wanted.
This progress is the last component of the proof. With large independent sets, they created the densest known ball-loading stack in higher dimensions, and for the first time, made asymptotic improvements to the Rogers boundary. "What amazes me with this new paper is what a beautiful, simple idea it is," said Will Perkins, a theoretical computer scientist at Georgia Tech.
While the new results are a significant improvement, this is not the final answer. No one knows how close the new loading stack is to the densest stack.
In 2010, physicists Francesco Zamponi and Giorgio Parisi theorized that the best "amorphous" or disordered ball-loading packs would be twice as dense as the most recent breakthroughs. As a result, mathematicians may have approached the limit of spheres stacking in a disordered manner. However, it is also possible to significantly increase the packing density with regular balls.
In the perennial battle between order and chaos, the new loading pile adds 1 point to Discord. But mathematicians are still inconclusive whether order or disorder will prevail.
"In this case, I think it's a real mystery," Perkins said.
exegesis
[1] https://arxiv.org/abs/2312.10026
本文经授权转自“zzllrr小乐”公众号，原标题《小乐数学科普：为了将球体紧密堆积起来，数学家们会随机抛出它们——译自Quanta Magazine》；《返朴》对译文进行了校订。 本文译自Kelsey Houston-Edwards ，To Pack Spheres Tightly, Mathematicians Throw Them at Random，原文链接：https://www.quantamagazine.org/to-pack-spheres-tightly-mathematicians-throw-them-at-random-20240430/。
Special Reminder
1. Enter the "Boutique Column" at the bottom menu of the "Huipu" WeChat official account to view a series of popular science articles on different themes.
2. "Back to Park" provides the function of searching for articles by month. Follow the official account and reply to the four-digit year + month, such as "1903", to get the article index in March 2019, and so on.