|
早打工，晚科研，谷歌大脑研究科学家破解了困扰数学界几十年猜想时间：2023-03-15 离开数学界七年后，一直从事 AI 领域工作的谷歌研究科学家 Justin Gilmer，却突破了研究生时期未曾获得进展的难题。 2022 年 10 月中旬，Justin Gilmer 从加利福尼亚飞往纽约，在东海岸拜访了他以前的导师 Michael Saks，一位罗格斯大学的数学家。 叙旧期间，他们并未谈及数学。事实上，自从 2015 年在罗格斯大学获得博士学位后，Gilmer 就再没认真思考过数学问题。那时候他决定不在学术界发展，同时开始自学编程。当他和 Saks 共同用餐时，Gilmer 向导师讲述了自己在谷歌的工作：机器学习和人工智能。 在校园的小路上，Gilmer 边走边回忆，2013 年，他花了一年多的时间走在这条路上，思考一个叫做「并封闭集猜想（又称Frankl猜想）」的问题。这一直是个没有结果的难题。Gilmer 所做的一切努力，只是成功地教会了自己，为什么这个关于数字集合的看似简单的问题会如此难以解决。 但在七年后的这次访问后，Gilmer 突然有了全新的灵感。他开始思考如何应用信息论来解决并封闭集猜想。经过一个月的研究后，通往证明的路径不断打开。11 月，他在 arXiv 上发布了研究结果，宣布在证明整个猜想方面取得了重大进展。
论文链接：https://arxiv.org/pdf/2211.09055.pdf 这篇论文掀起了后续研究的热潮。牛津大学、麻省理工学院和高等研究院等机构的数学家们迅速在 Gilmer 的新方法基础上开展工作。 什么是并封闭集猜想？ 并封闭集猜想与数的集合相关，如 {1，2} 和 {2，3，4}。你可以对集合进行运算，包括取它们的并集，也就是合并它们。例如，{1，2} 和 {2，3，4} 的并集是 {1，2，3，4}。 如果该族中任何两个集合的并集等于族中任何现有的集合，这个集合或族被认为是「并集封闭」的。例如，考虑这个由四个集合组成的族：{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}。 将任何一对组合起来，你就会得到一个已经在族中存在的集合，所以说这个族是并封闭集的。 数学家们早在 20 世纪 60 年代就讨论过并封闭集猜想，但直到 1979 年它才得到了第一次正式陈述，是在 Péter Frankl 的一篇论文中，他是一位匈牙利数学家，80 年代移民到日本，除了数学还热爱街头表演。 Frankl 猜想，如果一个集合的族是并封闭集的，那么它必须至少有一个元素（或数字）出现在至少一半的集合中。这是一个自然存在的阈值，原因有二。
Justin Gilmer 首先，在现成的并封闭集族的例子中，其中所有元素正好出现在 50% 的集合中。比如说，你可以用数字 1 到 10 组成所有不同的集合，总共会有 1024 个这样的集合。它们构成了一个并封闭集族，10 个元素中的每一个都出现在其中的 512 个集合。 在 Frankl 提出这个猜想的时候，还没有人提出过一个猜想不成立的并封闭集族的例子。所以 50% 似乎是正确的预测。 这并不意味着它很容易被证明。在 Gilmer 的工作之前，很多论文只能设法建立了随族中集合数量变化的阈值（而不是对所有大小的集合族都是相同的 50% 阈值）。 哥伦比亚大学的 Will Sawin 说：「感觉它应该很容易，而且它与很多容易的问题相似，但它一直未被攻克。」 缺乏进展既反映了这个问题的棘手性质，也反映了许多数学家宁愿不去想它。他们担心自己会浪费多年的职业生涯，去追逐一个不可能解决的问题。Gilmer 记得 2013 年的一天，他去 Saks 的办公室提到这个并封闭集猜想，这些也曾经与这个问题搏斗过的导师把他赶出了房间。 不确定性的洞察 在访问罗格斯大学之后，Gilmer 的脑海中滚动着这个问题，试图理解为什么它是如此困难。他用一个基本事实提示自己：如果你有一个由 100 个集组合组成的族，有 4950 种不同的方式来选择二者并将他们结合起来。然后他想：如果没有任何元素至少以某种频率出现在这些结合中，那么 4950 种不同的结合又怎么可能映射到 100 个集合呢？ 在这一点上，他已经在通往破解的路上了，尽管他还不自知。 信息论在 20 世纪上半叶得到发展，其中最著名的是 Claude Shannon 1948 年的论文《通信的数学理论》。这篇论文提供了一种精确的方法来计算发送信息所需的信息量，基于围绕着信息表达内容的不确定性的大小。这种信息和不确定性之间的关联，正是香农的卓越见解。 信息论经常出现在组合学中，这是一个与计数对象有关的数学领域，这也是 Gilmer 在研究生时期研究的内容。但当他飞回加州的家中时，他还担心将信息论与并封闭集猜想联系起来的方式是一个业余者的天真见解。 「说实话，我有点惊讶之前没有人想到这个，」Gilmer 表示。「但也许我不应该感到惊讶，因为我自己也想了一年，而且我是懂信息论的。」 探索难题 Gilmer 对数学的钻研来源于自己对数学的热爱。他工作日主要忙于谷歌的日常工作，闲暇时间就潜心研究数学问题。上班时他也带着一本数学教科书，以便随时查找忘记的公式。Gilmer 脚踏实地，也仰望星空 —— 他喜欢看著名数学家 Tim Gowers 的博客，这会让他备受鼓舞。 Gilmer 谦虚地说道：「也许你认为解决数学难题的人不应该查阅《Elements of Information Theory（信息论基础）》第 2 章，但我查阅了。」 Gilmer 提出的方法是设想一个并封闭集族，其中任何元素在所有集合中出现的概率都小于 1%。这是一个反例，如果它真的存在，将证伪 Frankl 的猜想。 假设从这个族中随机选择两个集合 A 和 B，问：集合 A 包含数字 1 的概率是多少？集合 B 呢？由于每个元素出现在任何给定集合中的概率略低于 1%，因此不应期望 A 或 B 包含 1。这意味着如果两者实际都不包含 1，我们也不会感到惊讶，当然也不会获得什么信息。 接下来，考虑 A 和 B 的并集包含 1 的概率。这仍然不太可能，但比 1 出现在任何一个单独集合中的概率大一些，是 1 出现在 A 中的概率与 1 出现在 B 中的概率之和减去 1 同时出现在两者中的概率。所以 A 和 B 的并集包含 1 的概率约低于 2%。 这仍然很低，但更接近 50% 的猜想，这意味着需要更多信息才能共享结果。换句话说，如果存在一个并封闭集族，其中任何元素在所有集合中出现的概率都小于 1%，则两个集合的并集比任何一个集合本身包含的信息要多。 「逐个元素证明猜想的思路非常聪明」，普林斯顿大学的 Ryan Alweiss 评价道。 Gilmer 的工作开始接近 Frankl 的猜想。这是因为很容易证明：在并封闭集族中，两个集合的并集包含的信息必然少于两个集合本身 —— 而不是更多。 原因很简单，以包含 1024 个不同集合的并封闭集族为例，每个集合中元素是 1 到 10 的数字。如果随机选择其中两个集合，平均会得到包含五个元素的并集。（在这 1024 个集合中，有 252 个包含五个元素，这是最常见的集合大小。）也有可能我们会得到一个包含大约七个元素的并集。但是只有 120 种不同的组合方法能得到包含七个元素的并集。 关键是，两个随机选择的集合包含的元素比其并集具有更多的不确定性。并集更像是一个具备更多元素、可能性更少的更大集合。当你在一个并封闭集族中对两个集合进行并集操作时，你可能会知道合并结果，就像是抛出一个有偏重的硬币，你很容易猜到硬币落向哪面，并集包含的信息少于两个集合本身的信息。 基于此，Gilmer 认为至少要有一个元素在集合中出现的概率大于等于 1%。 失之东隅，收之桑榆 当 Gilmer 在 11 月 16 日发布他的证明时，他附上了一条说明 —— 他认为使用他的方法可能更接近完整猜想的证明，有可能将阈值提高到 38%。 五天后，三个不同的数学家团体在几个小时内相继发表了论文，他们在 Gilmer 的工作基础上做到了这一点。这场爆发似乎已经将 Gilmer 的方法发挥到了极致，不过要想达到 50%，可能需要更多的新想法。 不过，对于后续论文的一些作者来说，他们想知道为什么 Gilmer 不自己做完相对简单的达到 38% 的研究。事实上，原因并不复杂：在脱离数学超过 5 年之后，Gilmer 只是不知道如何进行技术分析工作来实现这一目标。 「我有点生疏，老实说，我被困住了，」Gilmer 说。「但我很想知道数学社区会把它带到哪里。」 但 Gilmer 也认为，使他失去实践机会的同一原因，在某种程度上也使他的证明首先成为了可能：「这是唯一的解释 —— 为什么我在研究生院想了一年这个问题毫无进展，离开数学六年之后再回到这个问题上却取得了突破。除了机器学习让我的想法产生变化之外，我不知道还有什么解释。」 |
