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

图源：Samuel Velasco/Quanta Magazine

1611年，物理学家约翰内斯·开普勒（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”过程使用原始图的相对较小的部分创建了一个独立集。但是这个独立集还不够大。因此，他们重复了这个过程，从原始图中“蚕食”了