困擾學界幾十年的集合難題，竟被圈外人一個月搞定？？？

是的，你沒看錯。

當事人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分類器，用于識別句子中人名、地名、機構名等各命名實體之間的關系。

參考鏈接：

[1]https://www.quantamagazine.org/long-out-of-math-an-ai-programmer-cracks-a-pure-math-problem-20230103/

[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