可用于火星通信

梦晨 萧箫 发自 凹非寺

非常AI 报道 | 公众号 QbitAI

你能想象，一个等角线问题，竟然困扰了数学家们70余年？

等角线的定义很简单，穿过一个点的一组直线，任2条之间夹角都相等就是等角线。

比如在二维平面相互垂直的两条直线或，或相互成60度角的3条直线。

3条直线形成的6个60度夹角，也刚好把一个二维空间分成6部分，合起来就是360度。

3也就是二维空间中等角线数量的最大值了，很极限的满足了任意两条直线之间夹角都相等这个条件。

如果再多一条直线，无论怎么摆条件都无法成立。

到了3维空间，情况要复杂一些，不过通过想象和画图也可以找出，等角线最多可以有6条，此时的夹角是63.4度。

△图源：MIT 作者：Zilin Jiang

到这里都还不难，然而推广到4维、5维、6维……N维呢？

高维空间等角线数量最大值问题，一困扰数学家们就是几十年。

科学家们长久以来只能给出一个范围，而没办法算出精确的数值。

现在，这一难题终于被MIT助理教授赵宇飞带领团队突破了，已被四大顶刊之一的《数学年刊》接受，预计于2022年的第一期发表。

普林斯顿大学教授Noga Alon对此评价：

这是一个美妙的结果，为几何极值中一个已经被广泛研究的问题提供了惊人的答案。

火星通信就用上了

在解答问题前，你可能有一个疑惑，研究这个做什么？

其实，寻找高维空间中的等角线最大值不仅有理论数学上的意义，也有一定的应用价值。

特别是嘈杂通信环境下的信息编码和传输问题。

比如正在遥远火星上探索的天问一号和祝融号，它们传回地球的信号该如何保证准确性？

信号在如此长的距离中传输，不可避免会遇到许多噪声。

像地球上飞机与塔台间的通信，手机移动信号等都会造成干扰，这样火星探测器发出的信号等传到地球早就变了样。

地球这边的接收方其实一直是靠猜去试图理解火星上传回的信息，这样问题就转化成了“发送方以什么形式编码信息，能让接收方更容易猜？”。

数学家们想到的一种办法，是把信息打包成“球形编码”，可以理解成把信息放在像经纬度一样的坐标点上。

关键在于只使用有限数量的点，只要不同点之间的距离足够远又有规律，接收一方就不容易把两个点的内容混淆。

只不过这里的球说的不是日常中能见到的三维球体，而是用数学描述的高维几何球体。

找到等角线就可以找出那些用来编码信息效果最好的点。

要理解这个问题，还是先回到简单的二维平面说起。

前面说到，二维平面上的等角线最多有3条，相互之间呈60度夹角。

用这3条直线可以构造出一个正六边形，它的6个顶点就适合用来构造球形编码（虽然在二维空间还只能叫圆形），相邻的点之间距离相等，经过噪声干扰后也不容易被误判成另一个点。

之所以要寻找等角线数量的最大值，是因为合适的点越多能发送的信息量也就越多。

如果换成三维，就是经过正二十面体中心的6条对角线。

不过三维球形编码能发送的数据量，对于火星与地球间通信来说还是远远不够。

如何计算出更高维空间中等角线的最大值，就成了数学家们努力的目标。

用矩阵研究高维几何

很长一段时间里，数学家们能做到的就是证明等角线数量的最大值大致不能超过维度数的平方。

更具体一些，设维度数为d，d维空间的等角线数量最大值不能超过下面这个值：

直到2017年，苏黎世联邦理工学院的Benny Sudakov教授的研究才在这一问题上取得了重要进展。

Sudakov的方法是用线性代数和图论的方法来研究这个问题。

还是拿二维平面举例，先沿着每条线画一个单位向量：

再去计算每两条向量之间的点积：

接下来需要图论的方法建立一个图，向量是图中的点。如果向量间的点积是正的，边就是红色；点积是负的，边就是蓝色。

进而可以用矩阵表示这个图：

△图源：Quantum Magzine

高维等角线也可以按这个方法转换成矩阵表示，比如5维空间中的8个等角线：

△图源：Quantum Magzine

这样一个不直观、不方便研究的高维几何问题，就可以用上图论和线性代数里的诸多数学工具。

对于这种将高维几何问题转换的思路，西门菲沙大学的Jonathan Jedwab形容道：

这就像拿光照射3维物体，能看见它在一个方向的2维投影图；如果在光照下移动3维物体，就能比较不同方向得到的2维投影图，从而获得更多高维物体的信息。

在对这些矩阵进行研究的过程中，图论中的拉姆齐定理给了Sudakov灵感。

拉姆齐定理认为，找一个最小的自然数R(k,l)=n ，使得n个人中必定有k个人互相认识或l个人互不相识。

这里的k和l，刚好能和矩阵中的正负数对应起来，也就是上面图中的红色和蓝色。

通过将拉姆齐定理的相关结论灵活应用于等角线研究中，Sudakov等人最终证明：

对任何d维的图，在特定角度（约70.7°）下，等角线的最大数目是2d-2；对于其他任何角度，等角线最大数目不超过1.93d。

然而，这并不算是一个真正确定的结果，只是再次收紧了“等角线数量”的最大值范围。

现在，来自MIT的赵宇飞团队，利用一个发现的新定理，给出了这个难题的确定公式。

新定理解决70年难题

赵宇飞团队先是在对等角线进行研究中，发现并证明了一个新定理。

这个定理认为，有界度图（bounded degree graph）必须具有次线性第二特征值重数。

其中，度指在图论中，顶点相连接的边的数目，因此有限图一定是有界度图。

神奇的是，这个定理之前并没有人给出过，但发现它也确实需要非常的洞察力。

依据发现的新定理，赵宇飞团队成功解决了这个70年一直悬而未解的问题：

在给定角度的情况下，所有足够大的任意维度空间中，等角线数量的最大值是多少。

具体来说，这篇论文的结论如下：

给定数值α满足0＜α＜1，计算出给定角度arccos α，设d维图中等角线数量的最大值为。

设k代表邻接矩阵谱半径为(1 − α)/(2α)的图的最小顶点数。

如果k＜∞，那么对于所有足够大的d，都有：

否则有：

特殊地，在k(k为整数)≥2的情况下，对于所有足够大的d，有：

在此之前，数学家们的研究一直都停留在研究最大值的范围上，没有人能给出在指定角度下，任意维度的等角线数量最大值的确定公式。

对于这项研究，赵宇飞表示：

当时我有预感，团队会在等角线上取得一些不错的进展，但完全解决整个问题还是超出了我的预期。

本来是学生暑期项目，最小作者00后

这次论文背后的团队导师赵宇飞（Yufei Zhao），在武汉出生，1999年随父母移民加拿大。

据中新网报道，赵宇飞在中学时被选入资优班，他的数学老师表示“15年间，从未给过学生满分，直至遇到他”。

目前，赵宇飞在MIT任助理教授。

他在MIT获得数学和计算机科学双学士学位后，于剑桥大学取得硕士学位，并于2015年获MIT博士学位。

在求学期间，赵宇飞深入研究了大图（足够大的图graph）的规律，尤其是对其中的“图正则引理”进行了深入研究。

他认为，在图数据越来越庞大的当下，大图的世界是无限的，而图正则原理、图极限等数学方法，正是解决图数据问题的重要工具。

也正是基于这一领域的研究成果，赵宇飞获得了有“诺奖风向标”之称的斯隆奖、柯尼希奖（König Prize ）和MIT未来科学家奖。

虽然他的主要研究领域是加性组合，不过他兴趣广泛，对极值问题和概率论，以及理论计算机科学中的很多问题都感兴趣。

值得注意的是，赵宇飞的学生Ashwin Sah在本科期间，还曾经对本次研究用到的拉姆齐数理论做出过重要突破。

这次与等角线最大值问题结缘，是从2018年先在这一问题作出突破的Sudakov教授到MIT访问交流开始。

赵宇飞是那次交流活动的主持人。

Sudakov研究这一问题是受卡耐基梅隆大学的一位学者Bukh Boris启发，而本次研究的另一位作者博士后姜子麟在博士时的导师正是Boris。

到了2019年暑期，赵宇飞和姜子麟带着共同的兴趣将这一课题作为MIT数学系暑期研究项目开展。

学生中的3人张盛桐、姚远和Jonathan Tidor参与了这个项目，5人组成了研究小组。

一开始他们只是觉得这个问题足够大，是一个暑期研究的好项目，也没想着能取得多大进展。

没想到，最后直接一举解决了。

合影里中间一位是赵宇飞。

左数第一位姜子麟，北大数院校友，CMU博士，以色列理工学院博士后，发表这篇论文期间，他曾经在MIT进行博士后工作。

2017年，他曾经与MIPT的Alexandr Polyanskii证明了离散几何中的一个重要猜想“球带猜想”（Zone Conjecture），解决了困扰数学家们长达四十余年的问题。

左数第二位是Jonathan Tidor，现MIT博士生，主要研究方向是加性组合、高阶傅里叶分析和离散几何。

右数第二位姚远，上外附中校友，目前是MIT研究生，2016年美国队IMO金牌满分选手，连续两届获得阿里全球数学竞赛优秀奖和铜奖，普特南大学生数学竞赛特等奖（fellow）。

右数第一位张盛桐，上海中学校友，MIT本科生（2000年出生），连续三届获得阿里全球数学竞赛银奖、2016年国家队IMO金牌，有“加强版IMO”之称的普特南大学生数学竞赛特等奖（fellow）。

据赵宇飞教授2019年的博客，发表这篇文章时，姚远和张盛桐分别都还是MIT的本科生，其中姚远就读大二，张盛桐则刚上大一：

本科生阶段的研究成果就登上四大顶刊之一《数学年刊》，也是很厉害了。

ArXiv论文地址：
https://arxiv.org/abs/1907.12466

参考链接：
[1]https://annals.math.princeton.edu/articles/18190
[2]https://math.mit.edu/directory/profile.php?pid=1354
[3]https://news.mit.edu/2021/mathematicians-solve-old-geometry-problem-equiangular-lines-1004
[4]https://www.quantamagazine.org/a-new-path-to-equal-angle-lines-20170411/
[5]https://www.quantamagazine.org/how-spherical-codes-work-20170412/
[6]https://www.zilin.one/
[7]https://www.quantamagazine.org/how-spherical-codes-work-20170412/
[8]https://www.linkedin.com/in/shengtong-zhang-73a642197/
[9]https://math.mit.edu/directory/profile?pid=2324
[10]https://yufeizhao.com/blog/2019/07/30/equiangular-lines-with-a-fixed-angle/
[11]https://news.mit.edu/2019/mit-students-place-highly-putnam-mathematical-competition-0304
[12]http://www.chinanews.com/hr/mzhrxw/news/2006/07-24/762695.shtml

— 完 —