介绍
在十月中旬， 贾斯汀吉尔默 从加利福尼亚飞往纽约参加朋友的婚礼。 在东海岸时，他拜访了他的前顾问， 迈克尔萨克斯，罗格斯大学的数学家，七年前吉尔默在那里获得了博士学位。
萨克斯和吉尔默共进午餐，但他们没有谈论数学。 事实上，自从 2015 年从罗格斯大学毕业后，吉尔默就没有认真考虑过数学。那时他决定不想在学术界谋求职业，而是开始自学编程。 吉尔默和萨克斯一起吃饭的时候，向他的老导师讲述了他在谷歌的工作，他在那里从事机器学习和人工智能方面的工作。
吉尔默访问罗格斯大学那天天气晴朗。 当他四处走动时，他回忆起 2013 年他是如何度过一年中大部分时间走在同一条校园小路上，思考一个叫做联合封闭猜想的问题。 这是一种固执，尽管没有结果：尽管吉尔默付出了所有努力，但他只是成功地自学了为什么关于数字集的看似简单的问题如此难以解决。
“我认为很多人都会思考这个问题，直到他们对自己理解为什么困难感到满意为止。 我在这上面花的时间可能比大多数人都多，”吉尔默说。
在他 16 月的访问之后，出乎意料的事情发生了：他有了一个新想法。 吉尔默开始思考如何应用信息论中的技术来解决联合封闭猜想。 他追求这个想法一个月，每次都希望它失败。 但取而代之的是，通往证明的道路不断开辟。 终于，在 XNUMX 月 XNUMX 日，他 发布了首创的结果 这让数学家在证明完整猜想方面取得了很大进展。
这篇论文引发了一系列后续工作。 牛津大学、麻省理工学院和高等研究院等机构的数学家迅速建立了吉尔默的新方法。 但在他们这样做之前，他们提出了自己的问题：这个人到底是谁？
半满
联合封闭猜想是关于称为集合的数字集合，例如 {1, 2} 和 {2, 3, 4}。 您可以对集合执行操作，包括获取它们的并集，这意味着组合它们。 例如，{1, 2} 和 {2, 3, 4} 的并集是 {1, 2, 3, 4}。
如果族中任何两个集合的并集等于族中任何现有集合，则集合的集合或族被认为是“联合封闭的”。 例如，考虑这个由四组组成的家族：
{1}、{1、2}、{2、3、4}、{1、2、3、4}。
组合任何一对，您就会得到一个已经在家庭中的集合，从而使家庭联合关闭。
早在 1960 年代，数学家们就讨论过联合封闭猜想的各种版本，但它在 1979 年的一篇论文中获得了第一份正式声明 彼得·弗兰克尔，一位匈牙利数学家，于 1980 年代移居日本，并将街头表演列为他的追求之一。
Frankl 推测，如果一个集合族是并闭的，它必须至少有一个元素（或数字）出现在至少一半的集合中。 这是一个自然的门槛，原因有二。
首先，有现成的联合封闭族的例子，其中所有元素恰好出现在集合的 50% 中。 例如，就像您可以制作数字 1 到 10 的所有不同组合一样。 有 1,024 个这样的集合，形成一个联合封闭的家庭，10 个元素中的每一个都出现在其中的 512 个中。 其次，在弗兰克尔做出这个猜想的时候，还没有人提出过这个猜想不成立的工会封闭家庭的例子。
所以 50% 似乎是正确的预测。
这并不意味着它很容易证明。 在 Frankl 的论文发表后的几年里，几乎没有什么结果。 在 Gilmer 的工作之前，这些论文只能设法建立随系列中集合数量而变化的阈值（而不是为所有规模的集合系列设置相同的 50% 阈值）。
“感觉应该是容易的，和很多容易的问题类似，但是已经抵挡住了攻击，”说 威尔萨文 哥伦比亚大学。
缺乏进展既反映了问题的棘手性质，也反映了许多数学家不愿考虑它的事实； 他们担心自己会因为追逐一个无法解决的诱人问题而失去多年的职业生涯。 吉尔默记得 2013 年的一天，他去 Saks 的办公室并提出了工会关闭的猜想。 他的顾问——过去曾亲自解决过这个问题——差点把他赶出房间。
“迈克说，'贾斯汀，你会让我再次思考这个问题，我不想那样做，'”吉尔默说。
不确定性的洞察力
在访问罗格斯大学之后，吉尔默在脑海中盘旋着这个问题，试图理解为什么它如此困难。 他用一个基本事实来提示自己：如果你有一个 100 组的家庭，那么有 4,950 种不同的方法来选择两个并合并它们。 然后他问自己：如果 4,950 个不同的并集中没有元素以至少某种频率出现在这些并集中，怎么可能映射回仅仅 100 个集合？
甚至在那个时候他就在寻找证明的路上，尽管他还不知道。 来自信息论的技术，提供了一种严谨的思考方式，可以让你思考当你随机拉出一对物体时会发生什么，这会把他带到那里。
信息论发展于 20 世纪上半叶，最著名的是克劳德·香农 (Claude Shannon) 1948 年的论文，“关于通讯的数学理论” 该论文提供了一种精确的方法来计算发送消息所需的信息量，该方法基于消息确切内容的不确定性。 这个链接—— 信息与不确定性之间 ——这是香农非凡的、基本的洞察力。
举个玩具的例子，假设我抛硬币五次并将结果序列发送给你。 如果是普通硬币，则需要五位信息才能传输。 但如果它是一枚装满硬币的硬币——比如说，99% 的可能会正面朝上——它需要的时间要少得多。 例如，我们可以提前约定，如果装载的硬币五次都是正面朝上，我将向您发送 1（一位信息），这很可能会发生。 与有偏见的抛硬币相比，公平抛硬币的结果更令人惊讶，因此信息也更多。
同样的想法也适用于数字集合中包含的信息。 如果我有一族闭并集合——比如由数字 1,024 到 1 组成的 10 个集合——我可以随机选择两个集合。 然后我可以将每组的元素传达给你。 发送该消息所需的信息量反映了这些元素的不确定性：例如，第一组中的第一个元素为 50 的可能性为 1%（因为 1 出现在家庭），正如有 50% 的机会在一系列公平的抛硬币中第一个结果是正面。
信息论经常出现在组合学中，这是一个与计数对象有关的数学领域，这正是吉尔默作为研究生所研究的领域。 但是当他飞回加利福尼亚的家时，他担心他认为将信息论与闭联合猜想联系起来的方式是业余爱好者的天真见解：工作的数学家肯定以前遇到过这个闪亮的物体并将其视为傻瓜的黄金.
“老实说，我有点惊讶之前没有人想到这一点，”吉尔默说。 “但也许我不应该感到惊讶，因为我自己已经考虑了一年，而且我知道信息论。”
更有可能
吉尔默在完成他在谷歌的工作后，在晚上以及整个 XNUMX 月下半月和 XNUMX 月初的周末处理这个问题。 一群数学家多年前在 开放式协作 在著名数学家蒂姆·高尔斯 (Tim Gowers) 的博客上。 他还带着一本教科书工作，这样他就可以查找他忘记的公式。
“你会认为得出好结果的人不应该查阅第 2 章 信息论要素，但我做到了，”吉尔默说。
吉尔默的策略是想象一个联合封闭的家庭，其中没有元素出现在所有集合的 1% 中——一个反例，如果它真的存在，将证伪弗兰克尔的猜想。
假设您从该系列中随机选择两组 A 和 B，并考虑可能包含在这些集合中的元素，一次一个。 现在问：集合 A 包含数字 1 的几率是多少？ B组呢？ 由于每个元素出现在任何给定集合中的几率略低于 1%，因此您不会期望 A 或 B 包含 1。这意味着如果您了解到实际上两者都不包含 XNUMX，则不会感到惊讶，也不会获得什么信息做。
接下来，考虑 A 和 B 的并集包含 1 的可能性。这仍然不太可能，但它比它出现在任何一个单独集合中的可能性更大。 它是它出现在 A 中的可能性和它出现在 B 中的可能性减去它出现在两者中的可能性的总和。 所以，可能不到 2%。
这仍然很低，但更接近 50-50 的提议。 这意味着需要更多信息才能共享结果。 换句话说，如果存在一个联合封闭族，其中没有元素出现在至少 1% 的所有集合中，则两个集合的联合中的信息比两个集合中的任何一个本身的信息都多。
“逐个元素地揭示事物并查看你学到的信息量的想法非常聪明。 这就是证明的主要思想，”说 瑞安阿尔维斯 普林斯顿大学。
在这一点上，吉尔默开始接近弗兰克尔的猜想。 这是因为很容易证明在联合封闭的家庭中，两个集合的联合包含的信息必然少于集合本身——而不是更多。
要了解原因，请考虑包含 1,024 个不同集合的联合封闭系列，您可以从数字 1 到 10 组成这些集合。如果您随机选择其中两个集合，平均而言，您最终会得到包含五个元素的集合。 （在这 1,024 个集合中，有 252 个包含五个元素，这是最常见的集合大小。）您还可能最终得到一个包含大约七个元素的并集。 但是只有 120 种不同的方法来制作包含七个元素的集合。
关键是，两个随机选择的集合的内容比它们的并集具有更多的不确定性。 联合偏向于具有更多元素的更大集合，其可能性更少。 当你在一个联合封闭的家庭中对两个集合进行联合时，你有点知道你会得到什么——就像当你抛出一个有偏见的硬币时——这意味着联合包含的信息少于它所包含的集合。
有了这个，吉尔默就有了证据。 他知道即使没有元素出现在 1% 的集合中，联合也被迫包含更多信息。 但是工会必须包含更少的信息。 因此必须至少有一个元素出现在至少 1% 的集合中。
推到 50
当 Gilmer 在 16 月 38 日发布他的证明时，他附上了一条注释，他认为使用他的方法可以更接近完整猜想的证明，有可能将阈值提高到 XNUMX%。
五天后， 三 不同 团体 的数学家在几个小时内发布了基于吉尔默工作的论文。 额外 文件 其次，但最初的爆发似乎已经将吉尔默的方法发挥到了极致； 达到 50% 可能需要更多的新想法。
不过，对于后续论文的一些作者来说，达到 38% 相对简单，他们想知道为什么 Gilmer 不自己做。 最简单的解释结果证明是正确的：在五年多没有数学之后，吉尔默只是不知道如何做一些必要的技术分析工作来实现它。
“我有点生疏，老实说，我被困住了，”吉尔默说。 “但我很想知道社区会把它带到哪里。”
然而，吉尔默认为让他无法实践的同样情况可能首先使他的证明成为可能。
“这是我唯一能解释为什么我在研究生院思考了一年的问题却毫无进展，我离开数学六年，然后回到问题上并取得了这一突破，”他说。 “除了机器学习让我的想法产生偏见之外，我不知道如何解释它。”
更正： 2023 年 1 月 3 日
最初的标题称吉尔默为“谷歌工程师”。 事实上，他是一名研究员。
