科学网—球堆积的全新纪录出自始料未及之处
精选
已有 284 次阅读
2025-7-19 09:41
| 个人分类: 编码 | 系统分类: 科研笔记
球堆积的全新纪录出自始料未及之处
仅仅花费了几个星期，一个彻底的新人就解决了球堆积领域最大的未解难题之一。
Joseph Howlett 著
左 芬 译
【译注：原文2025年7月7日刊载于Quanta Magazine，链接见文末。】
在 数学领域中，对最优模式的追寻从未停止过。球堆积问题——如何将球尽可能高效地塞进一个（高维）盒子里——也不例外。它已经引诱数学家们数个世纪了，并且在加密、远距离通信以及更多领域有着重要的应用。
它绝不像看上去那么简单。17世纪早期，物理学家Johannes Kepler证实，将三维球像杂货店堆橙子那样堆起来，会占据大约74%的空间。他猜想这就是最好的排布方式了。然而数学家们花了接近400年才证明出来。
在更高的维度中，数学家们仍然不知晓答案。（奇特的8维和24维例外。）过了这么些年，他们想出过更好的堆积。但是这些改进很小，且相对罕见。
如今，在4月份在线公布的一份简短的手稿中，数学家Boaz Klartag超出了这些此前的纪录一大截。一些研究者甚至认为他的结果可能接近最优了。
作为这一研究方向的新人，Klartag实现他的堆积方法——在所有高维度中适用——靠的是复苏专家们数十年前就已抛弃的一种技术。他的工作深入到了关于高维最优堆积本质的多个旷世持久的论争之中。它们应该是有序还是无序的？它们究竟能紧密到什么程度？
“这真的是一个神奇的突破，”耶路撒冷市希伯来大学数学家Gil Kalai说道，“这类问题已经让数学家们兴奋快100年了。”
两种图像
1905 年，数学家Hermann Minkowski找到了一种直观的方式来考虑球堆积。从空间中重复排布的点，也就是所谓格出发。接着在每个点周围画一个球。这样一来，在给定维度下找到最优球堆积的问题实际上就成为，找到一个格，它的点排布得尽可能高效。比如说，在两维中，最优的格是“六方的”，并且给出如下的堆积：
可是在1947年，一个名叫Claude Ambrose Rogers的数学家给出了另一种视角。从任何格出发都可以，他说——哪怕是一个次优的。不要在每个点周围画一个球，在其周围画一个椭圆的形状，也就是椭球体，使它的表面接触到但不要越过格的其它点。
Rogers 想出了一种算法，以这个椭球体作为出发点，接着构造出一种紧密的球堆积。它运作的方式如下：
Rogers 方法的优点在于，你无需从一个特别有效的格出发来得到一个有效的球堆积。你只需选择合适的椭球体。不过这引入了新的复杂性。不同于球，用一个数——半径——就可以定义好，椭球体是由不同长度的数条轴定义的。维度越高，你可以拉伸椭球的方向就越多，因而你的初始椭球形状的选项也就越多。
“在很高的维度里，你不知道怎么生成它。你有太多自由了。”Klartag说道。
数学家们最终返回了Minkowski的方法，聚焦于寻找合适的格。他们逐渐更加擅长于格理论，而远离了Rogers的几何视角。
这一策略带来了高维球堆积的进展。不过大多数情况下，它们只对Rogers堆积改进相对较小的幅度。数学家们还希望有更大的提升。
数十年里，他们没有取得成功。需要一个新人来打破这一停滞局面。
外部视角
魏茨曼科学研究所数学家Klartag一直以来就对格和球堆积很好奇。他只是没有时间来学习更多关于它们的内容。他研究几何，而非格理论，并且通常研究凸形状——不会内陷的形状。这些形状带有各种各样的对称性，尤其是在高维中。Klartag确信这会使得它们极其强大：他主张，凸形状是被低估了的数学工具。
Boaz Klartag 早就猜测凸几何领域的方法会有助于球堆积问题。他只是一直没时间检验他的直觉——直到现在。
接着去年11月，在完成了他常规研究方向的一个主要项目后，Klartag注意到他的日程表非同寻常地空缺。“我想，我都47岁了，我这辈子都想研究格，如果我现在还不动手的话就再也没有机会了。”他说。他让一个朋友，特拉维夫大学的Barak Weiss来辅导他开始这一新探索。
Weiss 为Klartag以及几个其他同行开设了一个小型研讨班，来研究相关文献。Klartag的作业包括仔细阅读Minkowski和Rogers的球堆积诀窍。
当他读到Rogers把椭球体变成球堆积的花招时，他纳闷为什么数学家们会抛弃这一方法。椭球体是凸形状，因此Klartag知道有大量精巧的方式可以操纵它们。他还意识到，Rogers使用的初始椭球体尽管直观，但不高效。他所要做的就是构造一个更好的椭球体——一个在边界触及格中其它点前包含更多空间的——然后他就可以创下新的堆积记录。
“我想，我都47岁了，我这辈子都想研究格，如果我现在还不动手的话就再也没有机会了。” —— Boaz Klartag
他从一种熟知的方法开始。他按照一种随机过程沿着椭球体的每个轴对它的边界进行生长和收缩。一旦边界扩展到与格中的一个新点接触，他就冻结椭球体在那个方向的生长。这确保该点永远不会落到椭球体内部来。不过椭球体还可以在每个其它方向持续膨胀，直到它触及另一个点。这样一来，椭球体会以断断续续的运动方式改变形状，逐渐地探索它周围的空间。最终，边界会触及足够多的点，进而阻止椭球体进一步生长。
随着时间的推移，这一技术通常会让椭球体的体积增长。但它是否会增长到足以超越Rogers的直观椭球体呢？
因为Klartag的过程是随机的，他在每次实施时会产生一个不同的椭球体。他计算了这些椭球体可能拥有的体积范围。如果他可以找出一个体积比Rogers使用的那个大一些的，他就可以采用Rogers的原始方法把它变成一种更加紧密的球堆积。
不过Klartag没能找到哪怕一个足够大的椭球体。于是他微调了他的随机生长过程的细节。仅仅一到两周后，他就得以证明，至少在有些时候，这一过程会产生大到足以创下新纪录的椭球体。
他立刻知会了Weiss他的结果。“我们下周见一面吧，我会告诉你我错在哪，”Klartag告诉他的导师。不过到了那时候，Klartag对他的证明更加自信了。
逼近真理
证明成立。Klartag的新起始椭球，当变成球堆积后，给出了自Rogers 1947的文章之后在堆积率上最显著的改进。对于一个给定维度 ，Klartag可以堆积此前结果能达到的球数的 倍。也就是说，在100维空间里，他的方法差不多可以堆积100倍的球数；而在1百万维空间里，则可以差不多堆积1百万倍的球数。
Klartag 仅仅用了几个星期时间学习，再用几个星期时间撰写证明，就敲开了格与球堆积领域里的一个核心问题。“这感觉有些不公平，”他说。不过这往往就是数学推进的方式：有时候一个棘手的问题所需要的就是一些新颖的想法，因此到你当前的领域之外去闯荡一下会很有收获。 Klartag所熟知的凸几何这样一个通常来说远离的研究领域，结果正好是这一问题所需要的。“由于我之前的工作，这一想法一直在我的脑海里盘旋，”他说，“很明显这个我可以试一下。”
他的结果还让这一领域关于任意高维中最优堆积本质的一场论争再次复苏。有段时间，数学家们认为高度对称的，基于格的堆积会是尽可能紧密地堆积球的最佳方式。可是在2023年，一个团队发现了一种并不需要完全按照重复的格来实现的堆积。在Klartag的结果出现之前，这就是最佳记录了。一些数学家将其视为得出最优球堆积需要用到更多无序性的证据。
如今Klartag的工作则支持另一种理念，即有序和对称性可能才是最终的前进方向。
此外，还有关于球堆积究竟能达到多密集的论争。一些数学家认为Klartag的堆积离最优解只有毫厘之差了——几乎已经尽可能密集了。其他人觉得还有改进的空间。“我委实不知道在这一点上该认可哪种观点，”伊利诺伊大学芝加哥分校数学家Marcus Michelen说道，“我觉得所有情况都可能发生。”
答案会影响在加密和通信中的潜在应用。因此，尽管Klartag的结果在这些应用中并不会立刻排上用场，它已经激发了人们初步的热衷。“这一问题对于工程师而言是宏大的，并且一直没什么进展，”希伯来大学信息论科学家Or Ordentlich说道，“这让我们激动无比。”
对于Klartag而言，他希望他的工作能够开启对Rogers时代传统的回归，让凸几何和格理论像当时那样更加紧密地联系起来。“我觉得我们如今对凸形状的理解应该会对格有所帮助，不仅仅是在堆积上。”他说。
“我的目标是让这两个领域不再像如今那么彼此脱节，”他补充道，“这曾是我的计划，我还将继续求索下去。”
原文链接：
https://www.quantamagazine.org/new-sphere-packing-record-stems-from-an-unexpected-source-20250707/
转载本文请联系原作者获取授权，同时请注明本文来自左芬科学网博客。 链接地址： https://blog.sciencenet.cn/blog-863936-1494329.html
上一篇： PCP定理的故事