小乐数学科普：随机性所具有的反直觉力量——《量子杂志》每周数学随笔

文摘 2024-06-11 10:07 江苏

《Quanta Magazine》量子杂志每周都会解释推动现代研究的最重要思想之一。本周，资深数学作家Jordana Cepelewicz揭示了随机性如何成为数学家最强大的工具之一。

作者：Jordana Cepelewicz 量子杂志作家 2024-6-10

译者：zzllrr小乐（数学科普公众号）2024-6-11

有时，一个想法的时机就会到来。1940年代末，随机性可以成为一种强大工具的想法传到了新泽西州。位于默里山的贝尔电话实验室的电气工程师克劳德·香农（Claude Shannon，1916 - 2001）使用随机码证明了在任意噪声信道上传输信息是可能的。

Claude Shannon，1916 - 2001

在西南约 30 英里的IAS高等研究院工作的匈牙利数学家保罗·埃尔德什（Paul Erdős，1913 - 1996）独立地使用依赖于随机性的论证证明了图论的一个开创性结果。

Paul Erdős，1913 - 1996

图源：Mathigon

数学中的图论涉及点的集合，其中一些点由线连接。埃尔德什证明，在足够小的图中，可以避免创建全部连通或全部不连通的点集（称为团clique）。

在物理学中，随机性的作用在上一代发生了深刻的变化，因为量子力学的发现表明宇宙本质上是随机的。但是，尽管物理学家将随机性视为一项需要克服的挑战，但数学家和工程师却想出了如何利用它的方法。正如牛津大学的拉胡尔·桑塔纳姆（Rahul Santhanam）所解释的那样，随机性帮助数学家解决问题的方式有些自相矛盾。

他们经常用它来证明给定的数学结构存在，但并不说明如何构建它。例如，埃尔德什对无团图存在的证明并没有说明如何构建它们。相反，他表明，如果你考虑给定大小的所有可能图的集合，并随机选择一个，那么找到没有“禁忌”团的图的概率大于零。这意味着这样的图一定存在。

香农的成果开创了信息论这一学科，该学科探讨在特定情况下理论上可以传输多少信息——尽管它不一定能说明最佳传输方式。与埃尔德什一样，香农没有具体说明如何创建一种在嘈杂信道上可靠传输的方案。但他利用随机性证明了这种方式一定存在。

从那时起，数学家们不仅将随机性作为一种工具应用于图论和信息论，还将其应用于几何学、分析学（一种高级形式的微积分）、组合学（计数方法的研究）和计算机科学。今年早些时候，高等研究院的Avi Wigderson 获得了图灵奖（参见小乐数学科普：复杂性理论先驱艾维·维格森 Avi Wigderson荣获图灵奖——译自Quanta Magazine量子杂志），这是计算机科学领域的最高荣誉之一，部分原因是他研究了随机性和计算之间的联系。

图源：Quanta Magazine

近年来，数学家们一直在探索概率方法的极限，并对其可能失败的地方有了直觉。“试图利用随机性来推动事情发展是非常自然的，”一位数学家告诉我。然而，“随机性只能让你走这么远。”

最新动态和值得关注的内容

尽管如此，它还是能让你走得很远。研究人员继续追随埃尔德什的脚步，利用随机性证明了拉姆齐理论领域的许多结果，该理论研究的是图中的团不可避免地形成。例如，在2020年，两位数学家改进了图必须达到多大才能不可避免地出现某些模式的数字下限。第二年，量子杂志报道了一个证明，标志着在解决拉姆齐理论中最古老的问题之一方面取得了重大进展，该问题是关于无序字符串可以有多长。去年，我报道了另一个拉姆齐结果（参见小乐数学科普：数学家发现预测图结构的新方法），其中随机性至关重要。

概率方法也使得证明其他类型结构的存在成为可能。2017年，数学家将一个随机过程堆叠在另一个随机过程之上，结果发现在所有这些无序中出现了一致的几何图案。“无序会收敛到一种普遍形式，”凯文·哈特内特（Kevin Hartnett）写道。“当一个随机系统看起来最混乱的时候，精致的几何秩序就会显现出来。”去年，我写了一篇文章，介绍数学家如何使用概率方法来证明存在无数个被称为子空间设计的配置——与纠错码相关的对象（参见小乐数学科普：数学家在常见的空间类型中发现隐藏的结构——译自Quanta Magazine量子杂志）——“它们的存在根本不明显”，一位数学家告诉我。

在所有这些工作中，数学家必须巧妙地运用随机性。例如，在2022年，我报道了卡恩-卡莱猜想（Kahn-Kalai conjecture）的开创性证明（参见小乐数学科普：优雅的六页证明揭示了随机结构的涌现——译自Quanta Magazine量子杂志），这是一个主要问题，它询问在图和其他系统中何时发生相变。两位数学家通过随机选择图和集合的片段，直到逐渐建立起所需的结构，而不是一下子应用随机性来给出答案。

随机性似乎与数学所宣称的一切完全相反——数学是坚定不移地追求逻辑，寻找模式和结构，提出简洁无懈可击的论据。然而，它却成为数学最有用的工具之一。

网络上的资料

Noga Alon和Joel Spencer合著了《概率方法》一书（参见小乐数学科普：《概率方法》作者荣获2021年斯蒂尔数学阐述奖），介绍了随机性作为组合学工具的开发和使用。这是该领域的标准参考书 https://maa.org/press/maa-reviews/the-probabilistic-method-0 。