为了把球堆得更密集，数学家想到的办法是随机把球抛出去

luyuanhong

为了把球堆得更密集，数学家想到的办法是随机把球抛出去

四位数学家打破了 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 年来在一般球体堆积问题上的第一个重大进展。


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

“这是一段美丽的数学，”麻省理工学院的数学家赵宇飞说。“有新的、开创性的想法。”

改进基线

在二维平面上排列圆的最紧密方法是采用六边形图案，将圆放置在每个六边形的角和中心。这样的网格填充了 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 菲尔兹奖》《 “拉马努金复生才能解决”：E8 格与装球问题》）


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

微软研究院的数学家 Henry Cohn 说：“我喜欢[装球堆积]的一点是，它是一条连接数学、计算机科学和物理学中许多不同领域的线索。”他与 Viazovska 合作研究了 24 维的证明。

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

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

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

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 说。“这绝对是非常快的，从某种程度上来说，这有点出乎意料。

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

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

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

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



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

为此，他们使用了一种称为 Rodl nibble 的技术（译者注：Vojtěch Rodl 是捷克裔美国数学家，nibble 表示小口咬，即蚕食，其方法接近随机贪婪算法，参阅《小乐数学科普：数学家在常见的空间类型中发现隐藏的结构——译自 Quanta Magazine 量子杂志》），其中迭代删除（或“nibble”）图的片段。

“这是一种超级有影响力的技术，”Sahasrabu^dhe说。“它可以追溯到上世纪 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/t ... at-random-20240430/ 。

Quanta Magazine 返朴 2024-05-17 08:01 北京