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

撰文 | Kelsey Houston-Edwards

翻译 | zzllrr小乐

数学家喜欢将概念推广到更高的维度。有时这很容易。如果你想快捷地将二维正方形堆积在一起，可以像摆棋盘那样排列它们。如果要将3维立方体摆在一起，那你可以像搬箱子一样把它们堆起来。数学家可以很容易地扩展这些排列，在更高维的空间堆积立方体，使其完美地充满空间。堆积球体要困难得多。数学家知道如何将圆（或足球）堆积在一起，使它们之间的空隙最小。但在四维或更多的维度上，最密堆积方案完全是一个谜。（2016年解决的8维和24维除外。）

“这听起来很简单，”剑桥大学的数学家Julian Sahasrabudhe说。“可能有20种不同的方法可以解决这个问题。这似乎就是发生的事情——有很多不同的想法。”已知的2维、3维、8维和24维最密球体堆积看起来像“格子”，充满了图形和对称性。但在其他维度上，最好的堆积可能是完全混乱的。“我认为，这是此问题非常诱人的一面。这个问题真的非常开放，”普林斯顿高等研究院（IAS）的数学家Akshay Venkatesh说。“我们就是不知道答案。”2023年12月，Sahasrabudhe与他在剑桥的同事Marcelo Campos、伦敦国王学院的Matthew Jenssen和芝加哥伊利诺伊大学的Marcus Michelen一起，为如何在所有任意高维度下最密堆积球体提供了新的方法。[1]这是75年来在一般球体堆积问题上的第一个重大进展。“这是一段美丽的数学，”麻省理工学院的数学家赵宇飞说。“有新的、开创性的想法。”

改进基线

在二维平面上排列圆的最紧密方法是采用六边形图案，将圆放置在每个六边形的角和中心。这样的网格填充了90%以上的平面。图源：Samuel Velasco/Quanta Magazine1611年，物理学家约翰内斯·开普勒（Johannes Kepler，1571-1630）想到了堆积3维球体的最优方法。对于基础层，他将球体堆积成六边形排列，就像圆形一样。然后，他在第一层球体上放置了第二层球体，填补了空隙。但随后需要做出选择。第三层可以直接处于第一层正上方： 或者可以偏移一下：在这两种情况下，堆积型式都会重复；而且球体填充的空间量完全相同：大约74%。1831年，19世纪最杰出的数学家之一卡尔·弗里德里希·高斯（Carl Friedrich Gauss，1777-1855）证明了开普勒的构型是最好的格（lattice，重复的网格结构），但他不能排除掉某种不规则排列的可能性，因为它可能是更密的堆积（该可能性最终在千禧年之交被排除在外）。在更高的维度上，数学家们束手无策。然后，在2016年，Maryna Viazovska（1984-）利用八维空间特有的对称性的存在，证明特定格是最优的。她还与合作者合作，将证明推广到24维。她因这项工作获得了2022年菲尔兹奖，这是数学界的最高奖项。（编者注：参见《攻克高维版本球堆积问题——乌克兰女数学家获得2022菲尔兹奖》《 “拉马努金复生才能解决”：E₈格与装球问题》）

微软研究院的数学家Henry Cohn说：“我喜欢[装球堆积]的一点是，它是一条连接数学、计算机科学和物理学中许多不同领域的线索。”他与Viazovska合作研究了24维的证明。这些已知的最优堆积——1维、2维、3维、8维和24维——似乎并不能推广到更高的维度。在更高的维度上，数学家不知道最优排列会填充多少百分比的空间。取而代之的是，他们试图近似它。在任何维度中，如果你从一个非常大的盒子开始，然后连续地用球填充它，在你找到足够大的开口的地方粘一个球——那么球体将至少占据盒子体积的1/2ᵈ，其中d是空间的维数。因此，在2维空间中，它们将填充至少1/4的空间，而在3维空间中，它们将填充至少1/8的空间，依此类推。在相对较小的维度中，数学家通常知道特定的堆积比这个一般界限要好得多（例如，开普勒的3维堆积占据了74%的空间，远远超过最低的12.5%。但1/2ᵈ这个基线很有用，因为它适用于所有维度。）。

左起Marcus Michelen、Marcelo Campos、Julian Sahasrabudhe和Matthew Jenssen，在Sahasrabudhe的剑桥办公室，在为期一个月的访问的最后一天，他们打破了保持了75年的装球堆积记录。丨图源：Julia Wolf

“这是一种基线，”赵宇飞说。建立推广到任意维度的更好基线的进展缓慢。1905年，数学家赫尔曼·闵可夫斯基（Hermann Minkowski，1864-1909）证明，在任意维度中，存在一个格，通过在格上的每一点放置一个球体，可以装入两倍于基线数量的球。下一个实质性的进展发生在1947年，当时英国数学家克劳德·安布罗斯·罗杰斯（Claude Ambrose Rogers，1920-2005）提出了一个更好的格。闵可夫斯基对基线的改进是通过一个常数因子，而罗杰斯的方案是对基线的“渐近”（asymptotic）改进，这意味着随着维度数量的增加，堆积效率的差异也会增加。在50维，罗杰斯可以堆积的空间大约是基线的50倍，但在1000维，他的堆积大约是基线的1000倍。在过去的75年里，有一些结果是在罗杰斯的堆积上有了一个常数倍的改进，但直到现在，还没有人能够找到一种在所有维度上都适用的渐近改进。

连接点

Campos、Jenssen、Michelen和Sahasrabudhe四人在疫情初期就开始合作，他们每天在Zoom上开会数小时——尽管一开始并没有讨论这个问题。在2023年秋天第一次见面之前，他们共同撰写了三篇论文，当时Jenssen和Michelen来到剑桥进行了为期一个月的访问。这时，他们把目光投向了装球堆积问题。“在那段时间里，我们才开始，接着基本上完成了装球堆积问题，”Michelen说。“这绝对是非常快的，从某种程度上来说，这有点出乎意料。

Maryna Viazovska使用8维和24维特有的对称性来证明最密装球堆积的存在性。丨图源：2022 EPFL/Fred Merz – CC-BY-SA 4.0

数学家使用图论来解决这个问题，图是由边（线）连接的顶点（点）的集合。图经常被用于组合学和概率论，这正是上述作者的主要研究领域。几乎所有装球密度的下限都来自对格结构的研究。但最近的论文使用图论来创建高度无序的堆积——这是一种非常不同的方法。“当我们第一次开始谈论它时，它似乎有点吓人，”Sahasrabudhe说。“我们意识到可以将其建模为图。然后我们开始感觉更自在了。”为了创建堆积，他们首先在空间中随机散布点。这些点最终将成为堆积球体的中心。然后，他们在任何两个彼此太近的点之间画线，以这两点为中心的球体会重叠。从这个图中，他们想提取一个独立集（independent set），即没有两个顶点由一条边连接的顶点集合，如下图红点所示。如果他们在独立集的所有点上画球，球就不会重叠。这样就会形成一种装球堆积。创建一个稀疏的独立集很容易，只需从图中相距较远的区域抓取几个顶点即可。但是，要制造一个密集的球体堆积，包含尽可能多的球，他们需要一个非常大的独立集。他们的挑战是使用原始图中的大部分顶点提取出一个独立的集合。为此，他们使用了一种称为Rödl nibble的技术（译者注：Vojtěch Rödl是捷克裔美国数学家，nibble表示小口咬，即蚕食，其方法接近随机贪婪算法，参阅《小乐数学科普：数学家在常见的空间类型中发现隐藏的结构——译自Quanta Magazine量子杂志》），其中迭代删除（或“nibble”）图的片段。“这是一种超级有影响力的技术，”Sahasrabudhe说。“它可以追溯到上世纪80年代，但在过去的10到15年里，大家真的一直在锤炼它。”他们首先遍历图中的每个顶点。在每一点，他们（比喻而言）抛出一枚硬币，硬币反面的重量很大。如果硬币翻转落下来是反面，他们什么也不做。如果它落下来是正面，他们就会删除顶点并将其添加到一个新图中。这个“Nibble”过程使用原始图的相对较小的部分创建了一个独立集。但是这个独立集还不够大。

因此，他们重复了这个过程，从原始图中“蚕食”了更多的部分，并将它们添加到新图中。最后，他们得到了原始图的一个大的独立集，而这正是他们想要的。这一进步是证明的最后一个组成部分。凭借大的独立集，他们在更高维度上创造了已知最密集的装球堆积，并首次对罗杰斯界限进行了渐近改进。“这篇新论文让我感到惊讶的是，它是一个多么美好、简单的想法，”佐治亚理工学院的理论计算机科学家Will Perkins表示。虽然新结果是一个重大改进，但这并不是最终答案。没有人知道新的装球堆积与最密堆积有多接近。2010年，物理学家Francesco Zamponi和Giorgio Parisi提出理论，最好的“无定形”（amorphous）或无序的装球堆积的密度将是最近突破的两倍。因此，数学家们可能已经接近了球体以无序方式堆积的极限。不过，有规则的装球堆积密度也有可能大大提高。在常年的秩序与混乱之争中，新的装球堆积为无序加上了1分。但数学家们对有序还是无序会胜出仍没有定论。“在这种情况下，我认为这是一个真正的谜，”Perkins说。

注释

[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/。