诺贝尔数学奖（2021年数学界）

　　诺贝尔数学奖（2021年数学界）
　　作者 | 陈大鑫、维克多
　　编辑 | 青暮
　　3月17日晚，被誉为数学界＂诺贝尔奖＂的阿贝尔奖揭晓。
　　2021年挪威科学院决定将阿贝尔奖授予来自匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹（László Lovász）和美国普林斯顿高等研究院教授艾维·维格森（Avi Wigderson）。
　　以表彰他们＂对理论计算机科学和离散数学的基础性贡献，以及在将它们推动至现代数学的中心领域方面的领导作用。＂
　　阿贝尔奖（Abel Prize）是挪威政府于 2001 年为纪念挪威著名数学家尼尔斯·亨利克·阿贝尔二百周年诞辰而设立的一项数学奖，旨在表彰对数学领域拥有非凡深度和影响力的贡献。2003 年6月3日，由挪威自然科学与文学院的五名数学家院士组成的委员会正式将该奖项颁布给阿贝尔奖第一位获奖者，此后每年颁布一次，750万挪威克朗（约合人民币575万元）。
　　该奖项与菲尔兹奖、沃尔夫数学奖并称国际数学界＂三大奖＂。
　　迄今为止，阿贝尔奖已拥有20多位获奖者，也成为了国际所公认的「数学界诺贝尔奖」，也算是弥补诺贝尔科学奖项中没有数学奖的遗憾——这也正是该奖项设立的初衷之一。
　　1两位理论计算机科学先驱
　　Lovász和Wigderson是理论计算机科学的先驱，其工作为从互联网安全到网络研究的应用奠定了基础。＂他们都为理解计算中的随机性和探索有效计算的边界做出了根本性贡献。＂
　　Wigderson表示，该奖项不仅验证了他自己工作的意义，而且还验证了计算理论的价值。他说：＂我认为这对于该领域非常重要。＂
　　2021年阿贝尔奖获得者Avi Wigderson（图片来源：Dan Komoda /美国高等研究院，新泽西州普林斯顿）
　　Lovász说：＂如今，区分纯数学和应用数学越来越困难，而且我认为这是一个很好的发展趋势。＂
　　2021年阿贝尔奖获得者László Lovász（来源：匈牙利科学院）
　　至少从古希腊时代开始，算法就一直是数学的中心，哪怕是孩子在学校学习的简单程序（例如长除法）。但是自从20世纪计算机问世以来，研究的重点已经从＂一种算法可以解决这个问题吗？＂变为＂一种算法，至少在原理上可以在真实的计算机上、合理的时间内解决这个问题＂。
　　IAS的数学家Peter Sarnak表示，Lavaz和Wigderson在这个发展过程中发挥了核心作用。＂算法复杂性理论和解决问题速度的研究是在20世纪60年代和70年代发展起来的，他们被证明是该领域绝对的领导者。＂
　　＂在许多方面，他们的工作都是相辅相成的。Lovász是在数学方面，而Wigderson则是在计算机科学方面，但是他们研究的许多问题都是相关的。＂圣地亚哥大学加利福尼亚大学的计算机科学家Russell Impagliazzo说，他与两位研究人员都有过合作。
　　Lovász和Wigderson （Oslo 2012. 图源Oberwolfach ）
　　2从数学到计算
　　Lovász于1948年出生在布达佩斯，在一个鼓励有才华的孩子竞争解决难题的环境中成长。他从小就是数学明星，在十几岁的时候，他就在国际数学奥林匹克竞赛上获得了三枚金牌，并且在匈牙利的一场比赛表演中大获全胜，这场比赛将数学神童放在玻璃隔离间中并挑战他们自主解决难题的能力。
　　他的早期灵感大部分来自现代最多产的数学家Paul Erdős。布达佩斯Alfréd Rényi数学研究所的数学家Péter Pál Pálfy说，Erdős的工作重点是离散对象（例如网络中的节点）及其关系的数学，而不是几何等领域中典型的连续变量。
　　Paul Erdős将Lovász引入了图论领域。当时，图论是数学上的死水领域，以提出诸如四色定理（现已被证明）之类的有趣问题而闻名，该定理是说：任何一张地图中最多仅用四种颜色就可以为国家/地区着色，而使得没有两个相邻国家/地区使用相同的颜色。
　　＂我不会说它晦涩难懂，但是图论最早肯定不是主流数学，因为许多问题只是一些趣味性难题。＂Lovász说。但是，当Lovász在1970年22岁时获得博士学位时，情况已经悄然发生了变化，一个主要原因是计算机科学的诞生和迅速发展。
　　计算机可以处理离散量（1和0的二进制字符串），而组合学是离散对象的数学，它的主要子领域之一正是图论，它研究连接顶点和边构成的网络。因此，它为研究理论计算机科学中出现的很多问题提供了一种强大的语言。
　　离散数学领域中的网络理论曾经被＂纯＂数学家所鄙视，而如今它对其他数学领域和应用（如大数据分析）都变得至关重要，Lovász的职业生涯就始于这个时期。他对基础研究及其应用颇感兴趣，并且在微软担任全职研究人员长达七年，担任两个学术职位。
　　Lovász将计算机和图论的兴起视为有利的历史共识，可以与早于一个多世纪以前用于分析一个应用物理问题的方法（一种先进的微积分形式）相提并论。Lovász说：＂我有时会类比18和19世纪的分析和物理学，在这些领域中，它们是相互牵制的。而在图论和计算机科学中也发生了类似的事情。＂
　　Lovász最著名的成果之一是他与两位荷兰数学理论家Arjen和Hendrik Lenstra一起设计的算法。这种被称为LLL的算法将一个由整数组成的大向量分解为相同类型的最短向量的总和。LLL算法适用于称为格的几何对象，这些几何对象是空间中的点集，其坐标通常具有整数值。
　　LLL算法解决了有关其属性的一个基本问题：格中的哪个点最接近原点？这个简单的问题通常很难解决，尤其是在涉及高维空间以及格中的点变形的情况下。LLL算法没有完全解决问题，而是找到了一个很好的近似解，确定了一个点并确保没有其他点更接近原点。
　　由于此几何模型的广泛适用性，它在纯数学的各个领域（比如分解多项式）都有应用，并且对于数据加密的研究变得至关重要。基于整数向量的密码学密钥被认为对未来的互联网安全性很重要，因为与当今通信中通常使用的密钥不同，人们认为它们不会被未来的量子计算机所破解。
　　＂这是基本算法之一。它在理论上很重要，并且有许多实际用途。＂ IDC Herzliya和耶路撒冷希伯来大学的Gil Kalai说，他曾是阿贝尔奖委员会的成员。
　　Lovász最重要的另一个贡献和概率有关。在1960年代，Paul Erdős开发了所谓的概率方法来回答有关图的问题。通常，数学家想知道是否存在具有某些属性的图。回答这些问题的一种方法是实际找到一个能满足条件的图形。但是Erdős意识到另一种方法证明了随机选择的图形将具有很高的概率具有此属性。
　　不幸的是，Erdős的概率方法仅在确定具有常见属性的图的存在方面效果最好。19世纪70年代，Lovász与Erdős合作设计了一种补充技术，称为Lovász局部引理，用于证明非常稀有的图的存在。从那以后，它就成为了该领域的主要技术之一。
　　Lovász在其学术生涯中还解决了图论中的许多其他难题，包括Kneser 猜想，即为某个图着色所需的最小颜色数以及保证图完美匹配和相关结构的条件的问题。他还自己提出了一些猜想，这些猜想如今仍在指导着图论领域，其中包括两个问题，即KLS猜想和EFL猜想，它们在最近几个月内才取得了重大研究成果。
　　截至目前，Lovász已经获得了许多荣誉，包括1999年沃尔夫奖、1999年克努斯奖、2001年哥德尔奖和2010年京都奖。
　　3从计算到数学
　　Wigderson于1956年出生于以色列海法。阿贝尔奖的表彰认可了他对计算机科学几乎所有领域的贡献，在其中他用可能找到的任何数学工具来解决任何问题，即使对于看似遥远的研究领域也是如此。Sarnak说，Wigderson对他的研究领域的热情具有＂传染性＂。
　　到他十几岁的时候，计算机科学家才刚刚开始草拟一个基本的理论框架，这个框架最终贯穿了他的大部分学术生涯。该框架称为复杂性理论，涉及基于算法难以解决的问题对计算问题进行分类。难度的主要衡量标准是计算步骤的数量，最基本的区别是＂easy＂与＂hard＂。
　　一个简单的计算问题的示例是将两个数字相乘。不管数量有多大，计算机都可以迅速找到乘积的。这个问题属于＂ P＂的复杂度类中，它包含所有易于解决的计算问题。
　　相比之下，找到一个数的质因数是一个很难解决的计算问题。没有已知的算法可以快速分解所有数字。但是，如果告诉你一个数字的质因数，就很容易验证它们是否正确。该问题属于＂ NP＂的复杂度类，该类包含可能难以解决但其答案易于验证的计算问题。
　　1970年代初期，计算机科学家在计算复杂性领域制定了指导性猜想，询问P中的问题列表是否恰好与NP中的问题相对应，即著名的＂P/NP问题＂，这也是克雷数学研究所七个千禧年大奖难题之一。
　　此问题在1977年还很新颖，那时候Wigderson也进入了以色列理工学院。随后几十年里，Wigderson对复杂性理论做出许多基础性的贡献，例如将一些复杂问题进行归类。
　　回顾过去，Wigderson说：＂当我开始读研究生的时候，计算复杂性已经慢慢开始成熟了，在这期间，我自己对问题的认识也加深了＂。
　　在20世纪80年代后期， Wigderson和Ran Raz合作尝试解决计算机复杂性中的完美匹配问题：假设有20台机器，有20个任务待执行，由于每台机器只能完成这些任务的一部分，如何分配机器才能完成所有任务，且每台机器只执行一项任务。
　　Wigderson 和 Raz提出的解决思路是：加一些限制条件，假设工作在这个问题上的计算机够进行大多数标准的计算运算（如 ＂与＂、 ＂或＂），同时某些运算是被禁止的，例如＂非＂。
　　当然，计算机科学家最想证明的是，没有条件约束下，一个计算问题是hard。但到目前为止，他们还没有做到这一点（否则我们就知道P是否等于NP）。因此相反，他们试图证明，当你限制计算资源和可用时间来解决匹配这样的问题时，不存在快速的算法。
　　Wigderson说：＂如果你想找到算法的局限性，当在最一般的情况下无法做到时，就要加以限制，然后将一只胳膊绑在他们的背上。＂ 在1990年，他和Lovász证明，如果没有数字电路中的逻辑＂非＂操作，则没有很好的方法并行使用许多计算机来解决电路中的匹配问题。
　　Wigderson自1999年以来一直在高等研究院进行研究，他在复杂性理论方面取得了许多其他成果，其中包括一种称为之字形乘积的技术，该技术可以直接连接到纯数学的多个领域，并提供了一种走迷宫策略，其中只需要跟踪固定数量的交叉路口。Wigderson的工作广度反映了自他加入以来，计算复杂性领域扩展的方式。
　　Wigderson最著名的另一项成就是阐明了随机性在计算中的作用。在许多情况下，例如寻找迷宫的出路，基于具有比喻性的硬币翻转现象使算法可以快速找到解决方案。Sarnak说：＂如果允许进行随机选择，许多程序的运行速度实际上会快得多。＂
　　Wigderson及其合作者在1990年代发表的两篇论文中证明，在某些假设下，始终可以将快速随机算法转换为快速确定性算法。这从理论上保证了随机算法确实可以找到正确的解决方案。结果确定了被称为＂ BPP＂的复杂性类与＂ P＂复杂性类完全相同。它将数十年来对随机算法的研究巧妙地结合到了复杂性理论的主体中，并改变了计算机科学家看待随机算法的方式。
　　Wigderson的另一项主要工作在信息经济中变得越来越重要。它涉及＂零知识证明（zero-knowledge proofs）＂，这是一种允许某人在不透露任何有关文件内容信息的情况下验证文件正确性的方法。