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

作者: Kelsey Houston-Edwards

来源: 返朴

发布日期: 2024-05-17 08:01:11

四位数学家打破了75年的记录,他们找到了一种更密集的方法来堆积高维球体。他们使用图论和随机抛球的方法,成功地在更高维度上创造了已知最密集的装球堆积,并首次对罗杰斯界限进行了渐近改进。

为了把球堆得更密集,数学家想到的办法是随机把球抛出去。四位数学家打破了75年的记录,他们找到了一种更密集的方法来堆积高维球体。数学家喜欢将概念推广到更高的维度。有时这很容易。如果你想快捷地将二维正方形堆积在一起,可以像摆棋盘那样排列它们。如果要将3维立方体摆在一起,那你可以像搬箱子一样把它们堆起来。数学家可以很容易地扩展这些排列,在更高维的空间堆积立方体,使其完美地充满空间。堆积球体要困难得多。

数学家知道如何将圆(或足球)堆积在一起,使它们之间的空隙最小。但在四维或更多的维度上,最密堆积方案完全是一个谜。(2016年解决的8维和24维除外。)已知的2维、3维、8维和24维最密球体堆积看起来像“格子”,充满了图形和对称性。但在其他维度上,最好的堆积可能完全混乱。

2023年12月,Sahasrabudhe与他在剑桥的同事Marcelo Campos、伦敦国王学院的Matthew Jenssen和芝加哥伊利诺伊大学的Marcus Michelen一起,为如何在所有任意高维度下最密堆积球体提供了新的方法。这是75年来在一般球体堆积问题上的第一个重大进展。在二维平面上排列圆的最紧密方法是采用六边形图案,将圆放置在每个六边形的角和中心。

这样的网格填充了90%以上的平面。1611年,物理学家约翰内斯·开普勒想到了堆积3维球体的最优方法。对于基础层,他将球体堆积成六边形排列,就像圆形一样。然后,他在第一层球体上放置了第二层球体,填补了空隙。但随后需要做出选择。第三层可以直接处于第一层正上方,或者可以偏移一下。在这两种情况下,堆积型式都会重复;而且球体填充的空间量完全相同:大约74%。

1831年,19世纪最杰出的数学家之一卡尔·弗里德里希·高斯证明了开普勒的构型是最好的格,但他不能排除掉某种不规则排列的可能性,因为它可能是更密的堆积(该可能性最终在千禧年之交被排除在外)。在更高的维度上,数学家们束手无策。然后,在2016年,Maryna Viazovska利用八维空间特有的对称性的存在,证明特定格是最优的。她还与合作者合作,将证明推广到24维。

她因这项工作获得了2022年菲尔兹奖,这是数学界的最高奖项。在任何维度中,如果你从一个非常大的盒子开始,然后连续地用球填充它,在你找到足够大的开口的地方粘一个球——那么球体将至少占据盒子体积的1/2?,其中d是空间的维数。因此,在2维空间中,它们将填充至少1/4的空间,而在3维空间中,它们将填充至少1/8的空间,依此类推。在相对较小的维度中,数学家通常知道特定的堆积比这个一般界限要好得多。

1905年,数学家赫尔曼·闵可夫斯基证明,在任意维度中,存在一个格,通过在格上的每一点放置一个球体,可以装入两倍于基线数量的球。下一个实质性的进展发生在1947年,当时英国数学家克劳德·安布罗斯·罗杰斯提出了一个更好的格。闵可夫斯基对基线的改进是通过一个常数因子,而罗杰斯的方案是对基线的“渐近”改进,这意味着随着维度数量的增加,堆积效率的差异也会增加。

在过去的75年里,有一些结果是在罗杰斯的堆积上有了一个常数倍的改进,但直到现在,还没有人能够找到一种在所有维度上都适用的渐近改进。Campos、Jenssen、Michelen和Sahasrabudhe四人在疫情初期就开始合作,他们每天在Zoom上开会数小时——尽管一开始并没有讨论这个问题。

在2023年秋天第一次见面之前,他们共同撰写了三篇论文,当时Jenssen和Michelen来到剑桥进行了为期一个月的访问。这时,他们把目光投向了装球堆积问题。数学家使用图论来解决这个问题,图是由边连接的顶点的集合。图经常被用于组合学和概率论,这正是上述作者的主要研究领域。几乎所有装球密度的下限都来自对格结构的研究。但最近的论文使用图论来创建高度无序的堆积——这是一种非常不同的方法。

为了创建堆积,他们首先在空间中随机散布点。这些点最终将成为堆积球体的中心。然后,他们在任何两个彼此太近的点之间画线,以这两点为中心的球体会重叠。从这个图中,他们想提取一个独立集,即没有两个顶点由一条边连接的顶点集合。如果他们在独立集的所有点上画球,球就不会重叠。这样就会形成一种装球堆积。创建一个稀疏的独立集很容易,只需从图中相距较远的区域抓取几个顶点即可。

但是,要制造一个密集的球体堆积,包含尽可能多的球,他们需要一个非常大的独立集。他们的挑战是使用原始图中的大部分顶点提取出一个独立的集合。为此,他们使用了一种称为R?dl nibble的技术,其中迭代删除图的片段。他们首先遍历图中的每个顶点。在每一点,他们抛出一枚硬币,硬币反面的重量很大。如果硬币翻转落下来是反面,他们什么也不做。如果它落下来是正面,他们就会删除顶点并将其添加到一个新图中。

这个“Nibble”过程使用原始图的相对较小的部分创建了一个独立集。但是这个独立集还不够大。因此,他们重复了这个过程,从原始图中“蚕食”了更多的部分,并将它们添加到新图中。最后,他们得到了原始图的一个大的独立集,而这正是他们想要的。这一进步是证明的最后一个组成部分。凭借大的独立集,他们在更高维度上创造了已知最密集的装球堆积,并首次对罗杰斯界限进行了渐近改进。

UUID: c24df2f0-688f-4a92-9a11-f61eaa1cd424

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/返朴公众号-pdf2txt/2024/返朴_2024-05-17「转」_为了把球堆得更密集,数学家想到的办法是随机把球抛出去.txt

是否为广告: 否

处理费用: 0.0079 元