为了将球体紧密堆积起来，数学家们会随机抛出它们

原创 Quanta Magazine zzllrr小乐

四位数学家打破了75年的记录，找到了一种更密集的方法来堆积高维球体。

视频源：Dave Whyte / Quanta Magazine

作者：Kelsey Houston-Edwards 量子杂志特约作家 2024-4-30

译者：zzllrr小乐（数学科普公众号） 2024-5-4

数学家喜欢将概念推广到更高的维度。有时这很容易。

如果你想将二维正方形高效堆积在一起，可以像棋盘那样排列它们。要将三维立方体塞在一起，你可以像移动盒子一样堆叠它们。数学家可以很容易地扩展这些排列，堆积更高维的空间中的立方体完美地填充空间。

堆积球体要困难得多。数学家知道如何将圆（或足球）堆积在一起，以尽量减少它们之间的空隙。但在四个或更多的维度上，最高效的堆积方案完全是一个谜。（2016年解决的8维和24维除外。）

“这听起来很简单，”剑桥大学的数学家朱利安·萨哈斯拉布德（Julian Sahasrabudhe）说。“可能有20种不同的方法可以解决这个问题。这似乎就是发生的事情——有很多不同的想法。”

已知的2、3、8和24维最优球体堆积看起来像格子，充满了模式和对称性。但在每一个其他维度上，最好的堆积可能是完全混乱的。

“我认为，这是此问题非常诱人的一个方面。这个问题真的非常开放，”普林斯顿高等研究院IAS的数学家Akshay Venkatesh说。“我们就是不知道答案。”

去年12月，Sahasrabudhe与他在剑桥的同事Marcelo Campos、伦敦国王学院的Matthew Jenssen和芝加哥伊利诺伊大学的Marcus Michelen一起，为如何在所有任意高维度下密集堆积球体提供了新的方法。 https://arxiv.org/abs/2312.10026这是75年来在一般球体堆积问题上的第一个重大进展。

“这是一段美丽的数学，”麻省理工学院的数学家赵宇飞（Yufei Zhao）说。“有新的、突破性的想法。”

改进基线

在二维平面上排列圆的最紧密方法是采用六边形图案，将圆放置在每个六边形的角和中心。这样的网格填充了90%以上的平面。

图源：Samuel Velasco/Quanta Magazine

1611年，物理学家约翰内斯·开普勒（Johannes Kepler，1571 - 1630）想到了堆积三维球体的最优方法。对于基础层，他将球体堆积成六边形排列，就像圆形一样。

然后，他在第一层球体上放置了第二层球体，填补了空隙。但随后需要做出选择。第三层可以直接处于第一层正上方：

或者可以偏移一下：

在这两种情况下，模式都会重复。在这两种情况下，球体填充的空间量完全相同：大约74%。

1831年，19世纪最杰出的数学家之一卡尔·弗里德里希·高斯（Carl Friedrich Gauss，1777 - 1855）证明了开普勒的构型是最好的晶格（重复的网格状构型），但他不能排除掉一些不规则排列可以做得更好的可能性。（该可能性最终在千禧年之交被排除在外）。

在更高的维度上，数学家们不知所措。然后，在2016年，玛丽娜·维亚佐夫斯卡（Maryna Viazovska，1984 -） 利用八维空间特有的对称性的存在性来证明特定晶格是最优的。她还与合作者合作，将证明推广到24维。她因这项工作获得了2022年菲尔兹奖，这是数学界的最高奖项。详情参阅：、 “我喜欢[球体堆积]的一点是，它是连接数学、计算机科学和物理学中许多不同领域的一条线，”Microsoft微软研究院的数学家亨利·科恩（Henry Cohn）说，他与维亚佐夫斯卡（Viazovska）合作研究了24维的证明。

这些已知的最优堆积——一维、二维、三维、八维和24维——似乎并不能推广到更高的维度。在更高的维度上，数学家不知道最优排列会填充多少百分比的空间。取而代之的是，他们试图近似它。

在任何维度中，如果你从一个非常大的盒子开始，然后连续地用球填充它——在你找到足够大的开口的地方粘一个球——那么球体将至少占据盒子体积的1/2ᵈ，其中d是空间的维数。因此，在二维空间中，它们将填充至少1/4的空间，而在三维空间中，它们将填充至少1/8的空间，依此类推。在相对较小的维度中，数学家通常知道特定的堆积比这个一般界限要好得多。（例如，开普勒的三维堆积占据了74%的空间，远远超过最低的12.5%。但1/2ᵈ这个基线很有用，因为它适用于所有维度。

左起：马库斯·米歇伦（Marcus Michelen）、马塞洛·坎波斯（Marcelo Campos）、朱利安·萨哈斯拉布德（Julian Sahasrabudhe）和马修·詹森（Matthew Jenssen）

在萨哈斯拉布德的剑桥办公室，在为期一个月的访问的最后一天，他们打破了保持了75年的球体堆积记录。

图源：Julia Wolf

“这是一种基线，”赵说。建立推广到任意维度的更好基线的进展缓慢。

1905年，数学家赫尔曼·闵可夫斯基（Hermann Minkowski，1864 - 1909）证明，在任意维度中，存在一个晶格，通过在晶格上的每一点放置一个球体，可以装入两倍于基线的球。

下一个实质性的改进发生在1947年，当时英国数学家克劳德·安布罗斯·罗杰斯（Claude Ambrose Rogers，1920 - 2005）提出了一个更好的晶格。闵可夫斯基对基线的改进是通过一个常数因子，而罗杰斯的方案是对基线的“渐近”改进，这意味着随着维度数量的增加，堆积效率的差异也会增加。在 50维，罗杰斯可以堆积的空间大约是基线的50倍，但在1000维，他的堆积大约是基线的1000倍。

在过去的75年里，在各处零散的一些结果使罗杰斯的堆积有了一个常数倍的改进，但直到现在，还没有人能够找到另一种在所有维度上都有效的渐近改进。

连接点

Campos、Jenssen、Michelen和Sahasrabudhe在疫情初期就开始合作，每天在Zoom上开会数小时——尽管一开始并没有讨论这个问题。在去年秋天第一次见面之前，他们共同撰写了三篇论文，当时Jenssen和Michelen来到剑桥进行了为期一个月的访问。这时，他们把目光投向了球体堆积问题。

“在那段时间里，我们开始并基本上完成了球体堆积问题，”Michelen说。“这绝对是非常快的，在某些方面，这有点令人惊讶。

玛丽娜·维亚佐夫斯卡（Maryna Viazovska）使用8维和24维特有的对称性来证明最优球体堆积的存在性。

图源：2022 EPFL洛桑联邦理工学院/Fred Merz CC-BY-SA 4.0

数学家使用图论来解决这个问题，图是由边（线）连接的顶点（点）的集合。图经常被用于组合学和概率论，这是上述作者的主要研究领域。几乎所有球体密度的下限都来自对晶格结构的研究。但最近的论文使用图论来创建高度无序的堆积——这是一种非常不同的方法。

“当我们第一次开始谈论它时，它似乎有点吓人，”Sahasrabudhe说。“我们意识到可以将其建模为图。然后我们开始更加有回到家的感觉。”

为了创建堆积，他们首先在空间中随机散布点。这些点最终将成为堆积球体的中心。然后，他们画了一条线，连接任何两个彼此太近的点——以这两点为中心的球体会重叠。

从这个图中，他们想提取一个独立集（independent set），即一个顶点的集合，其中没有两个顶点由一条边连接，如下图红点所示。如果他们在独立集的所有点上画球，球就不会重叠。这样就会形成一种球形堆积。

创建一个稀疏的独立集很容易 —— 只需从图中相距较远的区域抓取几个顶点即可。但是，为了制造一个密集的球体堆积——尽可能多地填充球体——他们需要一个非常大的独立集。他们的挑战是使用原始图中的大部分顶点提取出一个独立的集合。

为此，他们使用了一种称为Rödl蚕食（Rödl nibble）的技术（Vojtěch Rödl是捷克裔美国数学家，nibble表示小口咬，即蚕食，其方法接近随机贪婪算法，zzllrr小乐译注，参阅 ），其中迭代删除（或“蚕食”）图的片段。

“这是一种超级有影响力的技术，”Sahasrabudhe说。“它可以追溯到80年代，但在过去的10到15年里，大家真的一直在锤炼它。”

他们首先遍历图中的每个顶点。在每一点，他们（比喻而言）抛出一枚硬币，硬币反面的重量很大。如果硬币翻转落下来是反面，他们什么也不做。如果它落下来是正面，他们就会删除顶点并将其添加到一个新图中。

这个蚕食过程使用原始图的相对较小的部分创建了一个独立集。但是这个独立集还不够大。因此，他们重复了这个过程，从原始图中啃取了更多的部分，并将它们添加到新图中。最后，他们得到了原始图的一个大的独立集，而这正是他们想要的。

这一进步是证明的最后一个组成部分。凭借大的独立集，他们在更高维度上创造了已知最密集的球体堆积，并首次对罗杰斯界限进行了渐近改进。“这篇新论文让我感到惊讶的是，它是一个多么美好、简单的想法，”佐治亚理工学院的理论计算机科学家威尔·珀金斯（Will Perkins）说。

虽然新结果是一个重大改进，但这并不是最终答案。没有人知道新的球体堆积与最优堆积有多接近。

2010年，物理学家弗朗切斯科·赞波尼（Francesco Zamponi）和乔治·帕里西（Giorgio Parisi）提出理论，最好的“无定形”（amorphous）或无序的球体堆积的密度将是最近突破的两倍。因此，数学家们可能已经接近了球体以无序方式堆积的极限。但是，以规则模式堆积的球体可能会明显更密集。

在秩序与混乱的常年比赛中，新的球体堆积为无序加上了1分。但数学家们仍然没有决定出是有序还是无序会胜出。

“在这种情况下，我认为这是一个真正的谜，”Perkins说。

参考资料

https://www.quantamagazine.org/to-pack-spheres-tightly-mathematicians-throw-them-at-random-20240430/

https://arxiv.org/abs/2312.10026

· 开放 · 友好 · 多元 · 普适 · 守拙 ·