闻乐 发自 凹非寺
量子位 | 公众号 QbitAI
一位“门外汉”闲来无事学了几个月的新理论,居然找到了百年难题的最优解。
用的还是已经被淘汰的老方法。
不得不说,buff有点多(doge)。
这位“门外汉”Boaz Klartag破解的问题是高维空间球体堆积,顾名思义,是探究如何在给定的高维空间中尽可能多地填充球体。
给定一个d维空间,用Klartag的方法进行堆积,数量可扩大至先前纪录的d倍。
也就是说,在100维空间中,可以堆积球体的数量大约为先前数量的100倍;在百万维空间中,可以堆积大约100万倍的球体。
这是自罗杰斯在1947年发表论文以来,在球体堆积效率方面最具实质性的改进。
而且他使用的方法,还是早就被主流数学家们抛弃的罗杰斯的“椭球体起始”方法。
其研究结果对于实际应用领域也有重要意义,能为无线通信领域效果提升带来新思路。
数十年的微小进展
早在17世纪初,物理学家开普勒就提出,通过像杂货店堆放橙子那样堆叠三维球体,可以填充大约74%的空间,并猜测这是最佳排列方式。
然而,这一猜想的证明却耗费了数学家们将近400年时间。
对于空间球体堆积这一问题,数学家赫尔曼·闵可夫斯基(Hermann Minkowski)在1905年提出了一种直观的思维方式:
在空间中重复排列的点的周围绘制球体,这些点被称为格点,这样可以将寻找球体堆积问题最优解转化为寻找排列最有效的格点的问题。
例如,在二维空间中,最佳的格点是“六边形”,那么产生的堆积看起来就像这样:
但罗杰斯在1947年提供了一种不同的视角:
可以从任何晶格开始——即使是次优的晶格,与其在每个点周围画一个球体,不如在一个点周围画一个称为椭圆体的类似长方体的结构,这样它的表面会接触但不会超出晶格中的其他点。
最后,把这些椭球体“挤压”成标准球体。二维空间示意图如下。
罗杰斯还提出了一种算法,可以利用这个椭球体作为起点来构建密集的球体堆积。
该方法的优势在于,即使起始点的晶格效率不高,也能得到高效的球体堆积,关键在于选择正确的椭球体。
然而,这也增加了新的复杂性:与仅由半径定义的球体不同,椭球体由多个不同长度的轴定义,维度越高,可拉伸的方向越多,椭球体的起始形状选择也越多。
于是,数学家们逐渐放弃了罗杰斯的方法,回归到闵可夫斯基的方法,专注于寻找最优的晶格。
多年来,尽管高维球体堆积的方法有所改进,但这些进展都微乎其微。
除了维度8(2016年的E8格堆积方法)和24(2017年的利奇格堆积方法)之外,在更高维度中,数学家们至今仍未能确定最佳答案。
这种停滞状态持续了几十年,直到Klartag这位专注于研究凸形状而不是高维球体的“局外人”的出现。
将凸形状迁移到球体堆积
Boaz Klartag是魏茨曼科学研究所的数学家,说是门外汉,主要是因为他的主要研究领域是几何学。
去年11月,在完成一个重要项目后,他利用难得的空闲时间,开始学习晶格理论。
当他读到罗杰斯将椭球体变成球体堆积的技巧时,他想知道为什么数学家们放弃了这种方法——
椭球体是凸形,所以Klartag知道如何操纵它们!
他还意识到罗杰斯使用的初始椭球体虽然直观但效率低下,他说:
在高维度里,你根本不知道该怎么去扩展它。自由度太高了。
Klartag认为,只需要构造一个更好的椭球体——
一个在其边界与晶格中的其他点接触之前能够覆盖更多空间的椭球体,这样他就能创造新的堆积记录。
于是,他开始改进早就被主流数学家们放弃的罗杰斯 (Claude Ambrose Rogers)的“椭球起始方法”。
他采用了一种他很熟悉的方法,通过随机过程沿各个轴生长和收缩椭球体边界。
每当边界扩展到足以接触晶格中的新的点时,他就会冻结椭球体在该方向上的生长,从而确保该点永远不会落入椭球体内部。
但椭球体可以在所有其他方向上继续膨胀,直到撞到另一个点。
通过这种方式,椭球体的形状会以不规则的方式改变,逐渐探索周围的空间,最终其边界会触及足够的点,从而阻止椭球体进一步生长。
为了方便理解,下面展示了二维空间的示意图。
随着时间的推移,这项技术平均而言会使椭球体的体积增大。
但它是否能够增大到足以超越罗杰斯直观的椭球体呢?
由于Klartag的过程是随机的,每次实施都会产生不同的椭球体。于是,他评估了这些椭球体可能达到的体积范围,调整了椭球体随机生长过程的细节。
就这样,他找到了比罗杰斯几十年前使用的椭球体体积更大的椭球体。
这样,他就证明了,至少在某些情况下,这个方法会产生足够大的椭球体来刷新堆积纪录。
在今年4月,他公开了相关工作。
在完成这项工作后,Klartag表示还将继续探索凸形状与晶格之间的联系:
我的目标是让这两个领域不像现在这样脱节。
Klartag的结果也重新点燃了关于任意高维度中最优堆积方法的辩论。
长期以来,数学家们认为高度对称、基于晶格的堆积是尽可能密集排列球体的最佳方式。
然而,在2023年,一个团队发现了一种不完全依赖于重复晶格的堆积方式,这是在Klartag的结果出现之前的记录,一些数学家认为这证明了在寻找最佳球体堆积时需要更多的无序性。
现在,Klartag的结果支持了有序(Klartag方法实际上是基于概率分布)和对称性可能才是最终方向的观点。
但仍有一些数学家还在讨论是否存在更优方法。
此外,在无线通信中,信号可看作高维空间中的 “点”,而噪声则像包裹这些点的 “球体”。
为避免信号混淆(即不同信号点被噪声球覆盖),需要将信号点在高维空间中尽可能密集且不重叠地排列——这在本质上就是球体填充问题。
可以说,球体填充问题的进展可以给无线通信领域效果提升带来新的思路。
论文地址:https://www.weizmann.ac.il/math/klartag/sites/math.klartag/files/uploads/oranges.pdf
参考链接: