幾十年數學難題被谷歌研究員意外突破！_風聞

詹士 蕭簫 發自 凹非寺

量子位 | 公眾號 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分類器，用於識別句子中人名、地名、機構名等各命名實體之間的關係。

參考鏈接：

[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