高维等角线并非无限:MIT华人团队用谱图理论解决持续70年的数学难题

百家 作者:机器之心 2021-10-11 16:08:01

机器之心报道

编辑:杜伟、陈萍
本想着或许可以取得一些不错的进展,没想到取得了意料之外的收获。

等角线(Equiangular Lane)是一个数学用语,通常在数学上这样表示:在△ABC 中,在线段 BC 上取 P、Q,使得∠BAP=∠CAQ,则称 AP、AQ 为△ABC 中的等角线。


更简单的说,等角线是空间中通过一个点的线,其对角都是相等的。想象一下二维正六边形的三条对角线,三维正二十面体的六个对顶点的连接线,参见下图:


然而,数学家们并不局限于三维。有研究者认为在更高维度也存在等角线,并且在高维度上,等角线的可能性几乎是无限的。据了解,这是一个困惑了数学家们至少 70 年的问题。

来自 MIT 的研究者认为在高维空间中等角线并不是无限的。他们突破性的研究决定了可以放置的线的最大可能数量,以便这些线以相同的给定角度成对分开。论文将发表在 2022 年 1 月的《数学年鉴》上。


论文地址:https://arxiv.org/pdf/1907.12466.pdf

论文作者包括 MIT 数学系助理教授赵宇飞(Yufei Zhao),以及本科生 Yuan Yao 和 Shengtong Zhang、博士生 Jonathan Tidor 和博士后 Zilin Jiang。

中间为赵宇飞。图源:Sandi Miller/MIT Department of Mathematics

赵宇飞于 2017 年 7 月加入 MIT 数学系,担任助理教授。2010 年赵宇飞获得 MIT 数学和计算机科学双学士学位,2011 年获得剑桥大学数学硕士学位,2015 年获得 MIT 博士学位。他的主要研究领域是组合数学(Combinatorics),他对组合数学中的极值、概率和加法问题以及与数学和理论计算机科学其他领域的联系感兴趣。此外他还一直在开发连接图论和加法组合数学的工具。

等角线的数学可以用图论编码。这篇论文为一个被称为谱图理论(spectral graph theory)的数学领域提供了新的见解,并且为研究网络提供了有力的数学工具。其中谱图理论带来了计算机科学中的重要算法,如谷歌搜索引擎 PageRank 算法。
 
这种对等角线的新理解为编码和通信领域带来了巨大的意义。等角线是「球形编码」的示例,它是信息理论中的重要工具,允许不同方面在一个嘈杂的通信渠道上相互发送信息,如 NASA 与其火星探测器之间发送的信息。

持续 70 年的问题终于有了满意的解决方案

1973 年,荷兰乌得勒支大学数学系的 P.W.HLemmens 和埃因霍芬理工大学数学系的 J.J Seidel 在论文《Equiangular lines》中提出研究具有给定角度的等角线的最大值问题。


论文地址:https://www.sciencedirect.com/science/article/pii/0021869373901233?via%3Dihub

普林斯顿大学数学系教授诺加 · 阿隆(Noga Alon)表示,「这是一个美丽的结果,为极值几何中自 1960 年代以来受到广泛关注并得到充分研究的一个问题提供了令人意想不到的答案。」

但正如论文通讯作者赵宇飞所言,MIT 的新工作为这一问题提供了「令人满意的解决方案」。他表示,「最初关于这一问题就有了一些好想法,但之后人们的研究停滞了近三十年时间。」

数年前,苏黎世联邦理工学院数学系教授 Benny Sudakov 在内的研究团队在这一问题上取得了一些重要进展。2018 年 2 月在访问 MIT 时,Benny Sudakov 在组合数学研究研讨会上介绍了他关于等角线的工作。

论文一作 Zilin Jiang 在其 CMU 前博士生导师 Bukh Boris 的工作基础上受到启发,并在 2019 年夏季与赵宇飞组队,同时邀请 Jonathan Tidor、Yuan Yao 和 Shengtong Zhang 加入团队。对此,赵宇飞解释道,「当时我想要找到一个不错的夏季研究项目,这个问题非常值得研究。最开始只想着或许可以取得一些不错的进展,但彻底解决这一问题完全在我的意料之外。」

这项研究得到了艾尔弗 · 斯隆基金(Alfred P. Sloan Foundation)和美国国家科学基金会的部分支持。在过程中,Yuan Yao 和 Shengtong Zhang 通过 MIT 数学系夏季本科生研究项目(SPUR)参与这项研究。这一成果为他们赢得了 SPUR 项目的 Rogers Jr. 最佳论文奖。

解决方案中使用到的最关键的数学工具之一是谱图理论,该理论告诉人们如何使用线性代数工具来理解图和网络。通过将一张图变成矩阵并查看其特征值来获得图中的「谱」。

与谱图理论的联系。在等角集合中每条线的方向上选择一个单位向量。通过考虑 Gram 矩阵,我们将问题重新转化为与关联图的邻接矩阵的频谱有关的问题。等角线和谱图论之间的联系在早期的工作中已经众所周知,使得等角线成为代数图论的基础问题之一。

与谱图理论的关系。在等角集的每条边的方向上选择一个单位向量。通过选择格拉姆矩阵(Gram matrix),研究者将该问题转化为与关联图邻接矩阵频谱相关的问题。等角线和谱图理论之间的关联在早期的工作中已为人熟知,从而使等角线成为代数图理论的一个基础问题。

该研究在光谱图理论中提供了一个新的定理——有界(bounded)标度图必须具备亚线性的第二特征值多重性。这一证明需要巧妙地将图谱与图的小块频谱联系起来。

参考链接:
https://www.cnbeta.com/articles/science/1188279.htm
https://news.mit.edu/2021/mathematicians-solve-old-geometry-problem-equiangular-lines-1004

CUDA编程基础——利用CUDA实现卷积操作


10月11日20:00-21:30,CUDA编程基础系列分享第三期:利用CUDA实现卷积操作。本次分享主要介绍CUDA流、cuBLAS、cuFFT、cuDNN、编程实例之利用CUDA实现卷积操作。


点击阅读原文,报名预约直播吧。

© THE END 

转载请联系本公众号获得授权

投稿或寻求报道:content@jiqizhixin.com

关注公众号:拾黑(shiheibook)了解更多

[广告]赞助链接:

四季很好,只要有你,文娱排行榜:https://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/

公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接