詹士萧箫发自凹非寺
量子位公众号 QbitAI
困扰学界几十年的集合难题，竟被圈外人一个月搞定？？？
是的，你没看错。
当事人 Justin Gilmer，毕业已 7 年，目前是谷歌研究员，于数学界并无名头，连其导师也并不看好他所做的研究，以至于成果发表后——
牛津、普林斯顿等高等学研机构数学家们看到名字，纷纷好奇：
这人谁啊？
不仅身份引人好奇，其破题方法也不按圈内常规路数，个中灵感来自通信祖师爷香农的信息论。
这项开创性成果及幕后历程刚被一些媒体介绍，在 Reddit 和 Hacker News 上引来不少网友热议。
有网友表示：看到信息论在意想不到的领域应用，真是酷炸了。
还有网友就着话题，秀了一把自己以信息论解决问题的经历。
所以，这位远离纯数学学术研究的大哥解决了什么问题？又如何在一个月内搞定的？
往下看。
这个猜想究竟是什么？
这位谷歌研究员突破的难题，名叫union-closed sets conjecture（并封闭集合猜想）。
该猜想认为，对于一个包含至少 2 个集合的、对并运算封闭的有限集合族，至少存在一个元素，使得它在至少一半的集合里出现过。
我们来解读一下这个猜想说的啥。
首先集合，就是包含了一系列元素的合集，这里面的元素既可以是数字，也可以是变量等。
例如这是一个我们常见的数集，而且是有限的（只包括 3 个元素）：
（至于无限数集，就像是自然数集、有理数集、整数集这种由无限个元素组成的集合）
当然，集合也有集合，它们组合起来，就可以被叫做集族，例如下图中F就是一个集族：
在这些集族中，有一类特殊的集族对并运算封闭。
对集族中的集合而言，并运算就是对两个集合求并集；至于并运算封闭，即是指在对任意两个集合进行并运算后，其结果仍然在这个集族中。
以下面这个集族为例：
无论是对{1}、{1,2}求并集，还是对{2,3,4}、{1}求并集，还是对{1,2}、{2,3,4}求并集……任意两个集合求并集，其结果都会在这个集族中。
所以，上面这个集族就符合并封闭集合这一要求，而并封闭猜想也正是基于此而提出。
值得注意的是，这一猜想中的“一半”是紧致的，毕竟对于任何一个集合的子集族，所有的元素恰好在一半的集合里出现过。
它于 1979 年被一个叫Péter Frankl 的数学家提出，所以也一度被叫做 Frankl 猜想。
看起来似乎不难，然而到实际解决时，一众数学家才发现这并不简单。
△Peter Winkler
达特茅斯学院数学教授 Peter Winkler 曾经在 1987 年就这个猜想给出尖锐的评价：并封闭集合猜想确实很有名，除了它的起源和它的答案。
△对此有同行表示，起源至少没答案难 orz
为了解决这个问题，数学家们也已经尝试过不少方法。
例如有人试着给猜想加上一些限制条件，让它在这些情况下成立。
像是将它和图论中的二分图（Bipartite Graph）联系起来，证明具备其中某种性质的集族，在这个猜想的条件下成立。
又或是给其中的元素加以限制，再加以证明……
BUT，无论是哪种方法，距离真正需要证明的猜想都还差不少距离。
来自哥伦比亚大学的助理教授 Will Sawin 对此评价称：它看起来似乎是个不难解决的东西，毕竟长得和那种“容易解决的问题”很像。
然而，如今却没有任何一个证明能真正搞定它。
问题就这样进度缓慢，直到 2022 年秋天，谷歌研究员 Justin Gilmer 借着朋友结婚的契机，回到了罗格斯大学校园。
用信息论突破了1%
Gilmer 回母校的时间是 2022 年 10 月，此时距他毕业离开数学学术圈，已过去 7 年。这些年来，他自觉无心专注纯数学领域，转而自学编程，投身了 IT 行业。
此次返校，他拜访了导师萨克斯，还四处转了转。
就在散步中，他突然回忆起——当年自己徘徊于校园小径，苦苦思索的一个数学问题：
没错，就是那个对“并封闭集合猜想”的证明。
读博期间，Gilmer 绞尽脑汁，花了一整年时间却毫无进展，只是搞明白了为什么这一看似简单的问题难以解决。
为此，他还去找过导师萨克斯。但导师也曾在该问题上停滞不前，因而他既不看好 Gilmer 的研究，也不愿重新碰这一领域。据 Gilmer 回忆，当时导师差点把他赶出房间。
但现在，重回校园转一圈的 Gilmer 有了个新想法：用信息论及相关原理解决并封闭猜想问题。
△ 信息论奠基人克劳德・香农
信息论发源于 20 世纪上半叶，其最为出名的论文是香农在 1948 年发表的《通信的数学原理》，其中提出以“消除不确定性”的多少，来评价通信过程中的信息量大小。
这个不确定性要怎么理解呢？
以掷硬币游戏为例，假设我们需要掷 5 次硬币，然后输出结果序列，每次结果为 1 比特。
如果现在我们抛掷的是一枚普通硬币（正反概率各 50%），那么我们至少需要 5 个比特来传递信息。
但如果给这枚硬币做点手脚（让它正面朝上的概率 99%），我们就完全可以提前规定，在硬币 5 次都是正面朝上时，只用 1 个比特来传递信息。
这样，被用以衡量文本、图片等内容大小的比特，也能成为描述事件发生不确定性的信息熵单位，而信息论也成为现代通信奠基之作，构建起今日的信息社会。
受到信息论的启发，Gilmer 决心下场再战。
此后一个月中，他利用下班后的晚上及周末时间，试探性地进行了摸索。有意思的是，由于长时间未接触理论，他一边研究还一边拿着本信息论教科书，以备随时查阅。
研究过程中，Gilmer 还发现自己研究的问题并非无人关心，其实几年前，就有几位数学家在菲尔兹奖得主 Tim Gowers 博客里探讨过该问题。这让他有了更多信心。
△ Tim Gowers 博客的相关研究内容
Gilmer 的思路是找反例。
根据并封闭集合猜想，一个正常的并封闭集族中，至少应该有一个元素在多于一半的集合中出现。
既然如此，只要想办法构造一个特殊的集族，里面没有一个元素出现在超过1% 的集合中，这个猜想就会被证伪，反之如果构造不出来，那么猜想就可能成立。
现在，我们用信息论视角看这一猜想：
正常来说，如果从集族中任意挑出两个集合，这两个集合取并集后，并集中的元素比原来两个集合更多，其信息熵应该比原来的单独两个集合更低。
然而如果基于“没有一个元素出现在超过1% 集合”这个限制条件，任意两个集合取并集后，计算出来的信息熵竟然比原来的单独两个集合更高。
这显然是不可能的，因此不存在这么一个特殊的集族，Glimer 的反例也没有找到。
但这也就意味着在“并封闭”集族中，至少存在一个元素，会出现在超过1% 的集合中。
2022 年 11 月 16 日，Gilmer 将这一思路写成论文，发表在了 arXiv 上。
当然，他这篇论文还不是“完全体”，也就是说并没有完全证明并封闭集合猜想——
毕竟这只是至少1%，还不意味着原来的并封闭集合猜想中的至少 50%就成立。
但这个新思路已经足够让学界震动。
普林斯顿大学数学家 Ryan Alweiss 评价“引入信息量”这一操作：非常聪明。
仅仅几天后，就有 3 个不同的数学研究组基于他的研究，先后发表了研究论文，随后也有更多研究者跟进，他们所在院校机构有牛津、普林斯顿、哥大、布里斯托等。
在后续研究中，对“并封闭集合猜想”的概率值证明，被推进到了 38%。
令这些数学家好奇的是，基于 Gilmer 的研究，他自己上手将概率值推进到 38% 并不难。
对此，Gilmer 表示，自己已经五年多没碰数学了，确实不知道如何进行分析工作来将其进一步推进下去。
不过，他也认为，正是因为对相关数学方法的生疏，让他跳出了常理，用圈外办法取得突破。
深度学习界的万引大佬
虽说此前在数学界没什么名头，Justin Gilmer 也并非等闲之辈。
他任职于谷歌大脑团队，Google Scholar 上引用破万，主要研究方向为深度学习、组合型、随机图论。
从其研究成果看，Justin Gilmer 主攻图神经网络，高引论文涉及：消息传递神经网络（MPNN）、关系归纳偏差与图神经网络、显著图等领域。
上述研究中，最高引用数为 4789，标题为：Neural Message Passing for Quantum Chemistry。
该文定义了一种图上监督学习框架，消息传递神经网络（MPNN），并将其应用于分子特性预测上。
以量子化学为例，该框架根据原子性质（对应节点特征）和分子结构（对应边特征）预测了 13 种物理化学性质。
这一成果在领域内影响深远，腾讯 AI Lab 的云深智药平台，其框架之一也基于 MPNN 改进发展而来。
另值得一提的是，Justin Gilmer 还到过中国北京，2007 年夏天他在微软亚研短暂呆过 3 个月。
根据其领英账号，Gilmer 当时在一个 4 人团队，参与构建 SVM 分类器，用于识别句子中人名、地名、机构名等各命名实体之间的关系。
参考链接：
[2]https://news.ycombinator.com/item?id=34236889
[3]https://mp.weixin.qq.com/s/lj-jTonC2sqwWKgZZBXVVw
[4]https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.081/Henning/UCSurvey.pdf
