困扰了科学家将近一个世纪的数学难题，两位数学家终于解决了

luyuanhong

困扰了科学家将近一个世纪的数学难题，两位数学家终于解决了

作者：诸平 | 发表时间：2024-4-14 20:59 | 个人分类：数学研究 | 系统分类：海外观察


Fig. 1 Jacques Verstraete and Sam Mattheus, researchers at the University of California, San Diego, have made a significant breakthrough in Ramsey theory by solving the r(4,t) problem, a challenge that has eluded mathematicians for decades.


Fig. 2 Ramsey problems, such as r(4,5) are simple to state, but as shown in this graph, the possible solutions are nearly endless, making them very difficult to solve. Credit: Jacques Verstraete


Fig. 3 Fan Chung and Ron Graham. Erdos on graphs: his legacy of unsolved problems. A. K. Peters, Ltd, January 1998. pp. 142. Published online by Cambridge University Press:  01 August 2016

据美国加州大学圣地亚哥分校（University of California - San Diego 简称 UCSD , San Diego, La Jolla, CA, USA）2024 年 4 月 11 日提供的消息，加州大学圣地亚哥分校（UCSD）的数学家与比利时布鲁塞尔自由大学(Vrije Universiteit Brussel, Brussels, Belgium) 的数学家合作，发现了拉姆齐数（Ramsey numbers）背后的秘密。这个数学难题困扰了科学家将近一个世纪，两位数学家终于解决了它（This Math Problem Stumped Scientists for Almost a Century – Two Mathematicians Have Finally Solved It）。

我们都有过这样的经历：盯着数学题看，题目似乎不可能解决。如果找到一个问题的解决方案需要花费将近一个世纪的时间呢？对于涉猎拉姆齐理论（Ramsey theory）的数学家来说，情况就是如此。事实上，自 20 世纪 30 年代以来，在解决拉姆齐问题（Ramsey problems）方面几乎没有取得任何进展。

现在，UCSD 的研究人员雅克·佛斯特拉（Jacques Verstraete）和萨姆·马特乌斯（Sam Mattheus）已经找到了 r(4,t) 的答案，这个长期存在的拉姆齐问题困扰了数学界几十年。

拉姆齐问题到底是什么？（What was Ramsey's problem, anyway ?）

用数学术语来说，图就是一系列的点和点之间的线。拉姆齐理论认为，如果图足够大，你一定能在图中找到某种顺序，要么是一组点之间没有线，要么是一组点之间有所有可能的线，这些集合被称为“团”（“cliques”）。它被写成 r(s,t) ，其中 s 是有直线的点，t 是没有直线的点。

对于我们这些不研究图论的人来说，最著名的拉姆齐问题 r(3,3) 有时被称为关于“朋友和陌生人的定理”（“the theorem on friends and strangers”），并通过一个聚会来解释：在一个 6 人的小组中，你会发现至少有 3 个人彼此都认识，或者 3 个人彼此都不认识。故 r(3,3) 的答案是 6 。

雅克·佛斯特拉说：“这是一个自然的事实，一个绝对的真理。不管情况如何，也不管你选择哪 6 个人，你会发现 3 个人都彼此认识，或者 3 个人都互不认识。你也许能找到更多，但你可以保证至少有 3 个人在一个或另一个团内。”

数学家发现 r(3,3) = 6 之后发生了什么？自然，他们想知道 r(4,4) ，r(5,5) 和 r(4,t) 其中不连接的点的数量是可变的。r(4,4) 的解是 18 ，它是用保罗·埃德斯（Paul Erdos）和乔治·塞凯赖什（George Szekeres）在 20 世纪 30 年代创造的一个定理证明的。目前，r(5,5) 仍然是未知的。

好的问题会反击（A good problem fights back）

为什么这么简单的陈述就这么难解决？事实证明，它比看起来要复杂得多。假设你知道 r(5,5) 的解在 40-50 之间。如果你从 45 个点开始，就会有超过 10234 个图形需要考虑！

雅克·佛斯特拉解释说：“因为这些数字是出了名的难以找到，数学家们寻找的是估计。这就是萨姆·马特乌斯和我在最近的工作中所取得的成就。我们如何找到拉姆齐数的最佳估计，而不是确切的答案？ ”相关研究结果于 2024 年 3 月 5 日已经在《数学年鉴》（Annals of Mathematics）杂志网站发表—— Sam Mattheus, Jacques Verstraete. The asymptotics of r(4,t). Annals of Mathematics, 2024,198(2): 819-941. DOI: 10.4007/annals.2024.199.2.8. Published online: 5 March 2024. https://annals.math.princeton.edu/2024/199-2/p08

数学专业的学生很早就学会了拉姆齐问题，所以 r(4,t) 在雅克·佛斯特拉的大部分职业生涯中一直是他关注的对象。事实上，他第一次看到这个问题是在《埃德斯在图上的问题和传奇》（Erdos on Graphs: His Legacy of Unsolved Problems）一书中，此书由加州大学圣地亚哥分校的两位教授，金芳蓉（英文名：Fan Chung Graham , 学术论文所用的英文名：Fan Chung）和已故的葛立恒（Ron Graham / Ronald Lewis Graham，31 October 1935 - 6 July 2020）合著的（Fig.3）。这个问题是来自保罗·埃德斯的一个猜想，他们将为第一个能解决这个问题的人支付 250 美元（$250）的奖金。

雅克·佛斯特拉说:“很多人都认为 r(4,t) 是一个 90 多年来一直存在的开放性问题。但这并不是我研究的重点。每个人都知道这很难，每个人都试图弄清楚，所以除非你有一个新的想法，否则你不可能取得任何进展。”

大约 4 年前，雅克·佛斯特拉和美国伊利诺斯大学芝加哥分校（University of Illinois-Chicago）的数学家杜茹瓦·穆巴里（Dhruv Mubayi）一起研究另一个拉姆齐问题。他们一起发现，伪随机图（pseudorandom graphs）可以推进这些老问题的现有知识。

1937 年，保罗·埃德斯发现使用随机图可以给出拉姆齐问题很好的下界。雅克·佛斯特拉和杜茹瓦·穆巴里发现，从伪随机图中抽样通常比随机图给出更好的拉姆齐数边界。这些可能答案的上限和下限收紧了他们可以做出的估计范围。换句话说，他们越来越接近真相了。

2019 年，令数学界高兴的是，雅克·佛斯特拉和杜茹瓦·穆巴里使用伪随机图来求解 r(3,t) 。然而，雅克·佛斯特拉努力构建一个可以帮助求解 r(4,t) 的伪随机图。

他开始涉足组合学（combinatorics）之外的不同数学领域，包括有限几何（finite geometry）、代数（algebra）和概率论（probability）。最终，他与萨姆·马特乌斯合作，萨姆·马特乌斯是他小组里的博士后学者，他具有有限几何方面的背景知识。

雅克·佛斯特拉说：“事实证明，我们需要的伪随机图可以在有限几何中找到。萨姆·马特乌斯是一个理想之人来帮助我们建立我们所需要的。”

一旦他们有了伪随机图，他们仍然需要解决一些数学问题。这花了将近一年的时间，但最终，他们意识到他们有了一个解决方案：r(4,t) 接近于 t 的三次函数。如果你想要一个聚会，总是有 4 个人彼此都认识，或者 t 个人彼此都不认识，你需要大约 t^3 人在场。这里需要说明，因为，记住，这是一个估计，而不是一个确切的答案。但是 t^3 已非常接近确切的答案了。

这些发现目前正在接受《数学年鉴》（Annals of Mathematics）的审查。

雅克·佛斯特拉说:“我们确实花了好几年才解决这个问题。有很多次我们被困住了，想知道我们到底能不能解决这个问题。但是一个人不应该放弃，不管需要多长时间。”

雅克·佛斯特拉强调毅力的重要性，这也是他经常提醒学生的一点。“如果你发现这个问题很难，你被卡住了，那就意味着这是一个好问题。金芳蓉说，好的问题会反击。你不能指望它自己就会显露出来。

雅克·佛斯特拉知道这种顽强的决心会得到很好的回报:“我接到金芳蓉的电话，说她欠我 250 美元。”

上述介绍，仅供参考。欲了解更多信息，敬请注意浏览原文或者相关报道。

原文摘要



链接地址： https://blog.sciencenet.cn/blog-212210-1429663.html