查看原文
其他

数学家破解百年高维“球体填充问题”

2016-04-12 士奇 知社学术圈

海归学者发起的公益学术平台

分享信息,整合资源

交流学术,偶尔风月

有些人的工作是在噪声图像中分离信号,以寻找来自数十亿公里外的外星文明;有些人在研究弦理论,以探索宇宙中基本要素的内在联系;有些人则在食品店堆放水果,以求最节省空间的方法从而码得最多。奇妙的是,这些看似无关的事情都因为数学纽带而联系到一起——它们都涉及到球体填充问题。只不过有些球体存在于其他维度。让我们看看数学家有什么最新发现。文末可下载相关预印论文。




早在1611年,开普勒就已经推测出如何码放相同大小的球体能够达到最密集效果。他认为,形如金字塔那样的堆积方式乃是正解,就像在水果店里见到的桔子那样。球与球之间总会存在空隙,通过进一步研究,数学家们发现在满满一袋子网球里面,大约36%的空间都是空气。假如你能够精心排布这些网球,那么这个比例可以降低到26% (亦称26%法),但是人们在一百年前就已经认识到,26%乃是其极限。而对于开普勒的猜想,直到1998年,才被现在匹兹堡大学的Thomas Hales教授所证明。据说当时数学论证文档长达250页,还动用了猛犸象计算机。


其实,玩数学的人还会在高维度下鼓弄球体填充游戏——球的定义依然不变,但“距离”这一概念则在我们熟知的三维系统 (比如x,y,z轴) 之外获得了更多属性。其实,高维球体的定义并不复杂:在高维空间下到给定球心距离相等的一组点所构成的即为高维球体。重要的是,在多维环境下将具有更多的码放方法。所以寻找能够空间利用率最高的球体排布可能性一直是主要挑战。


不过,我们很难对高维度下的球体填充进行视觉呈现,但它们却是非常实际的存在:高密度的球体填充与我们常见的纠错代码有着密切关系。早在上世纪60年代,John Leech试图纠正信号在传播过程中所积累的错误或噪声。他发现在24维度下处理数据会非常实用,尤其对于从5亿英里以外传送回木星图像这种工作来说。



旅行者1号


十年后,旅行者1号和2号确实采用了这一方法。1977年,NASA在发射木星和土星探测器前曾面临着重要难题:在极低的电力供应下,如何将旅行者号拍摄的彩色图片传送回地球?当时所采取的方式是将图像转换为一组24位的二进制序列,成为“代码字”。代码字以无线电波的形式发射进宇宙,波峰和波谷分别代表1和0。但数据传输总会伴随着噪声,有时1会失真为0,有时0又会变成1。所以要还原旅行者号的图像,就需要纠错。


一方面,代码字需要足够清晰显著以便识别;另一方面,在24位的限制下,相对含混模糊的代码字才能提供更多的可能性,以及更快的数据传输速度。这样的矛盾与需求也随之转化为几何问题,比特位对应在了空间坐标上,每段代码字都成为一个24维空间下球体的球心。如果球体发生重叠,那么相关的代码字也将无法被识别。为了最大化地传输数据并且进行纠错,问题最终演变为:如何在24维空间下最密集地填充球体?



E8 lattice points


长久以来,数学家们已经积累了大量证据,几乎要默认E8和Leech晶格 (两者分别为8维度和24维度下极为美妙且对称的球体填充模型) 就是两种维度下的最佳填充方法。但他们一直缺少一项关键证据,即一个能够计算可容许球体最大密度的函数。


如今,乌克兰数学家Maryna Viazovska似乎已经找到了答案。今年3月,她先后在论文预印网站上贴出了两个重要的成果。她首先从8维空间球体排布开始说起,证明了E8晶格 (E8 lattice) 在8维空间中具有最大密度。E8很像是高维版本的“26%法”问题,只不过在8维空间下,球体之间拥有更多空隙,可以多塞进去一些。



Maryna Viazovska


当然,弦理论家并不会摆弄球体,他们只是将E8结构当作不同维度下的弦理论彼此关联方式中的重要组成部分。弦理论从26个维度开始,并需要折叠简化至我们所熟知的3维。E8则包含了折叠所需要的所有必要属性。


数学家和物理学家认为这绝不是一个巧合。他们觉得这样一个维度是最为简单有效的,因为再添加任何一维空间都会使其更难以解释。可能他们还真说对了,Viazovska已经可以证明E8结构不会留下任何额外空间,对于8维球体填充来说这是最高效的方法。



不过她并没有止步于此。在发布了8维研究后,一些希望解决24维问题的数学家找到她,于是他们开始研究 “Leech晶格”。Leech晶格对信息的处理方式就好比在24维度下排布球体,数学家们也一直认为这是最有效的解决方法。仅仅在E8文章公布一周之后,Viazovska和同事们又搞定了24维的问题


尽管两篇文章尚未接受同行评议,在数学圈内似乎并没有什么质疑。由于E8和Leech晶格与数学和物理的诸多领域关系密切, Viazovska等人的发现对未来的研究有着重要意义。


原文链接

http://www.sciencealert.com/a-mathematician-just-solved-the-centuries-old-sphere-problem-in-higher-dimensions?perpetual=yes&limitstart=1

https://www.quantamagazine.org/20131220-nudging-spheres-closer-little-by-little/

https://www.quantamagazine.org/20160330-sphere-packing-solved-in-higher-dimensions/


公号下回复“球体填充”可获取8维预印论文

扩展阅读
 

物理学的终结?看宇宙中最危险的两个量

霍金2016年BBC演讲:黑洞有没有毛?

现代数学艺术的七朵奇花


本文由知社原创编译,转载请联系授权投稿、授权、合作事宜请联系

service@scholarset.com 或微信ID: scholarset

回复“目录”或“分类”,浏览知社更多精华。长按二维码识别,可以关注/进入公众号进行回复。

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存