困擾學界幾十年的集合難題，竟被圈外人一個月搞定？？？
是的，你沒看錯。
當事人 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
