阿贝尔奖得主László Lovász（拉兹洛·洛瓦兹）近期在HLF海德堡桂冠论坛谈论了离散数学和连续数学之间的模糊界限。
作者：Benjamin Skuse 英国科普作家 2024-11-13 译者：zzllrr小乐（数学科普公众号）2024-11-14 |
|---|
第11届海德堡奖桂冠论坛HLF中的“火花”会议（spark session，精选的获奖者简短全体演讲，每次持续15至20分钟）极其精彩纷呈，涉及从鼓舞人心的到荒诞不经的，以及介于两者之间的一切。
例如，9月24日星期二，在本周的第一场火花会议期间，与会者从安德烈·奥昆科夫（Andrei Okounkov，1969 -，2006年菲尔兹奖得主）那儿了解了对划分的新认识，划分（partition，有时也称为分割、分拆）是一个简单的数学对象，是当今许多高等数学的核心。不久之后，他们被肯·汤普森（Ken Thompson，1943 -，1983年图灵奖得主）讲述的一则长篇轶事所吸引，其中涉及一伙野生动物从他家偷坚果，以及他如何处理这件事。
9月26日星期四举行的第二场火花会议同样精彩纷呈，可能稍微偏向于讨论人工智能将如何重塑社会。但有一场演讲脱颖而出，它为整个数学领域提供了一种非常不同的、也许有用的视角：“离散或连续：数学的两个世界？”演讲者是匈牙利数学家拉兹洛·洛瓦兹（László Lovász，1948 -，又译名拉斯洛·洛瓦兹）。——参见 小乐数学科普：对话阿贝尔奖得主拉兹洛·洛瓦兹（László Lovász）by 拉斐拉·穆拉斯（Raffaella Mulas）
图源：HLFF
适合做的数学 |
|---|
洛瓦兹与艾维·维格森（Avi Wigderson，1956 -）共同获得2021年阿贝尔奖，“以表彰他们对理论计算机科学和离散数学的基础性贡献，以及在将其塑造为现代数学核心领域方面的领导作用。”洛瓦兹的基础性贡献可以追溯到他的青少年时期，当时他的数学偶像、匈牙利同胞保罗·埃尔德什（Paul Erdős,1913 - 1996）启发洛瓦兹进入组合数学领域，特别着重于图的性质。
组合学（combinatorics，计数模式的数学）和图论（graph theory，连接模式的数学）都涉及具有离散值的对象。洛瓦兹和他研究这些“离散”主题的同事很快就在1970年代意识到，这种类型的数学可以直接应用于新兴的计算机科学领域。因此，洛瓦兹在20世纪的整个职业生涯横跨离散数学和计算机科学，在此过程中在这两个领域做出了基础性且有影响力的发现。
直到世纪之交，他才开始涉足更传统的连续数学世界，看看离散数学和连续数学之间的界限在哪里，它们之间的联系是什么，以及分析离散和连续世界之间的相互作用是否可以开启更深层的数学理解。
两个不同世界的互动 |
|---|
在洛瓦兹的火花演讲中，他首先描述了离散数学和连续数学中使用的方法和概念如何完全不同。连续数学处理实数轴和微分方程等对象，并使用导数（derivative）、积分（integral）、傅立叶展开（Fourier expansion）和许多更完善的分析方法。离散数学中的对象是独立有区分的，例如整数。“在离散数学中，我们也有方法 - 例如，归纳或计数或有限对象的随机构造 - 而且这些方法也变得越来越成功，”他说。
这两个不同的数学分支的交汇点正是洛瓦兹感兴趣的领域。两者之间最明显的相互作用是在连续结构必然被离散化的计算中。“我们通过一些离散对象（例如一组三角形）来近似各种连续对象（例如光滑表面），这些对象完全近似于表面，”洛瓦兹说道。事实上，涉及偏微分方程问题的任何数值解都涉及离散化。
图源：HLFF | 译制：zzllrr小乐
离散化的反面又是什么情况呢？使离散问题连续化？“拿一根钢条来举例——这是一个离散的物体还是连续的物体？”洛瓦兹问道。“现在我们知道它是一个由有限数量的原子组成的网络——它是一个离散的物体——但如果工程师必须确定如果这根钢条作为桥梁的一部分会发生什么，那么他就不会分析所有这些原子”。取而代之的是，工程师会将离散的钢条逼近为连续物体，其微分方程涉及密度、压力、温度等函数。“你可以求解这些微分方程和桥架。”
图源：HLFF | 译制：zzllrr小乐
横跨两个世界的现象 |
|---|
尽管这些联系早已为人所知，但直到21世纪初数学家开始研究图序列的极限之前，很少有人尝试严格研究和度量它们。“假设存在一系列有限图或有限网格，并假设它们在无限序列中变得越来越大，”洛瓦兹解释道。
完全图（complete graph）就是一个很好的例子。这些对象的每一对不同的顶点都由唯一的边连接。仔细观察，即使是具有99个顶点的完全图也与具有100个顶点的完全图几乎相同。
“随着你的研究，它们会变得越来越相似，这意味着通过一些定义良好的统计，它们变得越来越难以区分，”洛瓦兹说。“有几个人贡献了这种图序列的极限是什么的理论，并且连续的对象出现在极限中。”
如今，洛瓦兹最感兴趣的是在连续和离散环境中都出现某一现象的情况。例如，著名的幂级数展开连接了离散函数序列和连续解析函数，如下所示：
f(x) = 1/(1 - x) = ∑xⁿ {n = 0 到 ∞}，其中|x| < 1
这种类型的联系看起来很深刻，考虑其中一个方面所获得的直觉和洞察力通常对另一方面非常有用。
变得贪婪 |
|---|
为了说明这些类型的联系可以在更加模糊的领域中被发现，洛瓦兹转向了熟悉的：图论。为此，他引入了一些术语。拟阵（matroid）概括了各种数学对象，例如图和向量空间，并由两个元素组成：基础集（ground set）和独立集（independent set）。例如，要从图出发定义拟阵，我们可以将基础集设为边集，然后将独立集设为不包含环（cycle，也称为闭路、环路、循环）的边集。环由图中的一系列相邻且不同的顶点组成，除了第一个和最后一个顶点相同。
尽管这看起来非常抽象，但拟阵可以建模许多图论问题，反之亦然。对拟阵命题的证明也同时提供了对拟阵所概括的对象的相应命题的证明，这使得拟阵理论成为离散数学中许多领域的强大工具。
其中一个领域是最优化（optimization）。如果最优化问题具有拟阵结构，则适当的“贪婪算法”（greedy algorithm，又称为“贪心算法”）将获得最优解。贪婪算法本质上在每一步都做出局部最优选择，以找到该优化问题的全局最优解。
贪婪算法最早由捷克数学家奥塔卡·博鲁夫卡（Otakar Borůvka，1899 - 1995）于1926年作为最小生成树问题的解决方案提出。图的生成树（spanning tree）是没有环但仍连接每个顶点的边的子集。可能有许多生成树，但最小生成树总的边权重最小。
理解这一点的一个简单方法是想象一家电信公司在你的本地区域铺设宽带电缆。如果电信公司只需要沿着某些道路（边）埋设电缆，他们可以绘制一个包含这些道路连接的房屋（顶点）的图，并为那些铺设电缆可能更昂贵的道路分配更大的边权重。该图的生成树将是那些没有环路但仍连接每个房屋的路径的子集，最小生成树将是总成本最低的生成树，代表铺设电缆最便宜的路径。
Borůvka的贪婪算法旨在通过逐条选择边来构建生成树，因此永远不会创建环，并且始终选择“最便宜”的边来提供新的连接。“该算法给出了精确的最优值，它是拟阵理论中的基本算法，”洛瓦兹补充道。
“事实证明，在连续环境中，有一个技术性很强但也非常重要的定理，即如果在Borel集（拓扑空间的所有开集取可数次交并补所得到的集合）上有一个子模集函数（submodular set function），则存在一个荷（charge，有限可加性测度）小于或等于此子模函数，并且开头部分的函数值是相等的，”洛瓦兹说。尽管他说细节并不重要，但他的观点很简单：“这有点像贪婪算法的连续版本。”
贪婪算法的离散版本和连续版本
图源：HLFF | 译制：zzllrr小乐
数学领域还有许多其他例子，有一门完整的学科致力于研究离散数学和连续数学之间的联系，逐渐将这两个不同的领域编织在一起。但是，这种跨越离散和连续数学世界的方法能否成为解决其他科学（例如物理学）中基本问题的线索？它甚至可以帮助我们直观地了解现实的本质吗？从广义上讲，传统思维认为宇宙是一个包含离散物体的空间和时间的四维连续体（连续统）。我们是否能够将整体视为一个连续体和一个（巨大的）离散结构，并依靠这两种视角来获得新的见解？
在他简短的演讲中，洛瓦兹没有时间深入探讨这些深刻的问题。但他确实提供了值得深思的东西。
整个火花会议，包括洛瓦兹的演讲，可以点此链接查看：https://youtu.be/rczSYAH3Rb8
参考资料 |
|---|
近期文章 |
|---|
小乐数学科普：AI人工智能如何改变预测科学？——译自Quanta Magazine量子杂志
小乐数学科普：菲尔兹奖得主吴宝珠谈论伽罗瓦的不朽遗产——译自HLF海德堡桂冠论坛
小乐数学科普：2024年Salem塞勒姆奖授予Miguel Walsh（米格尔·沃尔什）和王艺霖
· 开放 · 友好 · 多元 · 普适 · 守拙 ·
让数学
更加
易学易练
易教易研
易赏易玩
易见易得
易传易及
欢迎评论、点赞、在看、在听
收藏、分享、转载、投稿
点击左下角 阅读原文
查看原始文章出处
点击zzllrr小乐
公众号主页
右上角
设为星标★
数学科普不迷路！
