白天打工，晚上科研，Google大腦研究科學家解決了困擾數學界幾十年的猜想

2022 年 10 月中旬，Justin Gilmer 從加州飛往紐約，在東海岸拜訪了他以前的導師 Michael Saks，一位羅格斯大學的數學家。

敘舊期間，他們並未談到數學。事實上，自從 2015 年在羅格斯大學獲得博士學位後，Gilmer 就再也沒認真思考過數學問題。那時候他決定不在學術界發展，同時開始自學程式設計。當他和 Saks 共同用餐時，Gilmer 向導師講述了他在谷歌的工作：機器學習和人工智慧。

在校園的小路上，Gilmer 邊走邊回憶，2013 年，他花了一年多的時間走在這條路上，思考一個叫做「並封閉集猜想（又稱Frankl猜想）」的問題。這一直是個沒有結果的難題。 Gilmer 所做的一切努力，只是成功地教會了自己，為什麼這個關於數字集合的看似簡單的問題會如此難以解決。

但在七年後的這次訪問後，Gilmer 突然有了全新的靈感。他開始思考如何應用資訊理論來解決並封閉集猜想。經過一個月的研究後，通往證明的路徑不斷打開。 11 月，他在 arXiv 上發布了研究結果，宣佈在證明整個猜想方面取得了重大進展。

論文連結：https://arxiv.org/pdf/2211.09055.pdf

這篇論文掀起了後續研究的熱潮。牛津大學、麻省理工學院和高等研究院等機構的數學家們迅速在 Gilmer 的新方法基礎上工作。

什麼是並封閉集猜想？

並封閉集合猜想與數的集合相關，如 {1，2} 和 {2，3，4}。你可以對集合進行運算，包括取它們的並集，也就是合併它們。例如，{1，2} 和 {2，3，4} 的並集是 {1，2，3，4}。

如果該族中任何兩個集合的並集等於族中任何現有的集合，這個集合或族被認為是「並集封閉」的。例如，考慮這個由四個集合組成的族：{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}。

將任何一對組合起來，你就會得到一個已經在族中存在的集合，所以說這個族是並封閉集的。

數學家們早在20 世紀60 年代就討論過並封閉集猜想，但直到1979 年它才得到了第一次正式陳述，是在Péter Frankl 的一篇論文中，他是一位匈牙利數學家，80 年代移民到日本，除了數學還熱愛街頭表演。

Frankl 猜想，如果一個集合的族是並封閉集合的，那麼它必須至少有一個元素（或數字）出現在至少一半的集合中。這是一個自然存在的閾值，原因有二。

Justin Gilmer

首先，在現成的並封閉集族的例子中，其中所有元素正好出現在50% 的集合中。比方說，你可以用數字 1 到 10 組成所有不同的集合，總共會有 1024 個這樣的集合。它們構成了一個並封閉集族，10 個元素中的每一個都出現在其中的 512 個集合。

在 Frankl 提出這個猜想的時候，還沒有人提出過一個猜想不成立的並且封閉集族的例子。所以 50% 似乎是正確的預測。

這並不意味著它很容易被證明。在 Gilmer 的工作之前，許多論文只能設法建立了隨族中集合數量變化的閾值（而不是對所有大小的集合族都是相同的 50% 閾值）。

哥倫比亞大學的 Will Sawin 說：「感覺它應該很容易，而且它與許多容易的問題相似，但它一直未被攻克。」

缺乏進展既反映了這個問題的棘手性質，也反映了許多數學家寧願不去想它。他們擔心自己會浪費多年的職業生涯，追逐一個不可能解決的問題。 Gilmer 記得 2013 年的某一天，他去 Saks 的辦公室提到這個並封閉集猜想，這些也曾經與這個問題搏鬥過的導師把他趕出了房間。

不確定性的洞察

在訪問羅格斯大學之後，Gilmer 的腦海中滾動著這個問題，試圖理解為什麼它是如此困難。他用一個基本事實提示自己：如果你有一個由 100 個集組合組成的族，有 4950 種不同的方式來選擇二者並將他們結合起來。然後他想：如果沒有任何元素至少以某種頻率出現在這些結合中，那麼 4950 種不同的結合又怎麼可能映射到 100 個集合呢？

在這一點上，他已經在通往解決的路上了，儘管他還不自知。

資訊理論在 20 世紀上半葉發展，其中最著名的是 Claude Shannon 1948 年的論文《通訊的數學理論》。這篇論文提供了一種精確的方法來計算發送訊息所需的資訊量，基於圍繞著訊息表達內容的不確定性的大小。這種資訊和不確定性之間的關聯，正是香農的卓越見解。

資訊理論經常出現在組合學中，這是一個與計數物件有關的數學領域，這也是 Gilmer 在研究生時期研究的內容。但當他飛回加州的家中時，他還擔心將資訊理論與並封閉集猜想聯繫起來的方式是一個業餘者的天真見解。

「說實話，我有點驚訝之前沒有人想到這個，」Gilmer 表示。 「但也許我不應該感到驚訝，因為我自己也想了一年，而且我是懂信息理論的。」

探索難題

##Gilmer 對數學的鑽研來自於自己對數學的熱愛。他平日主要忙於谷歌的日常工作，閒暇時間就潛心研究數學問題。上班時他也帶著一本數學教科書，以便隨時找出忘記的公式。 Gilmer 腳踏實地，也仰望星空 —— 他喜歡看著名數學家 Tim Gowers 的博客，這會讓他備受鼓舞。

Gilmer 謙虛地說：「也許你認為解決數學難題的人不應該查閱《Elements of Information Theory（資訊理論基礎）》第2 章，但我查閱了。」

Gilmer 提出的方法是設想一個並封閉集族，其中任何元素在所有集合中出現的機率都小於1%。這是一個反例，如果它真的存在，將證偽 Frankl 的猜想。

假設從這個族中隨機選擇兩個集合 A 和 B，問：集合 A 包含數字 1 的機率是多少？集合 B 呢？由於每個元素出現在任何給定集合中的機率略低於 1%，因此不應期望 A 或 B 包含 1。這意味著如果兩者實際上都不包含 1，我們不會感到驚訝，當然也不會獲得任何資訊。

接下來，考慮 A 和 B 的並集包含 1 的機率。這仍然不太可能，但比1 出現在任何一個單獨集合中的機率大一些，是1 出現在A 中的機率與1 出現在B 中的機率總和減去1 同時出現在兩者中的機率。所以 A 和 B 的並集包含 1 的機率約低於 2%。

這仍然很低，但更接近 50% 的猜想，這意味著需要更多資訊才能共享結果。換句話說，如果存在一個並封閉集族，其中任何元素在所有集合中出現的機率都小於 1%，則兩個集合的並集比任何一個集合本身包含的資訊要多。

「逐個元素證明猜想的思路非常聰明」，普林斯頓大學的 Ryan Alweiss 評論道。

Gilmer 的工作開始接近 Frankl 的猜想。這是因為很容易證明：在並封閉集族中，兩個集合的並集包含的資訊必然少於兩個集合本身 —— 而不是更多。

原因很簡單，以包含 1024 個不同集合的並封閉集族為例，每個集合中元素是 1 到 10 的數字。如果隨機選擇其中兩個集合，平均會得到包含五個元素的並集。 （在這 1024 個集合中，有 252 個包含五個元素，這是最常見的集合大小。）也有可能我們會得到一個包含大約七個元素的並集。但是只有 120 種不同的組合方法能得到包含七個元素的並集。

關鍵是，兩個隨機選擇的集合包含的元素比其並集具有更多的不確定性。並集更像是具備更多元素、可能性較少的更大集合。當你在一個並封閉集族中對兩個集合進行並集操作時，你可能會知道合併結果，就像是拋出一個有偏重的硬幣，你很容易猜到硬幣落向哪面，並集包含的資訊少於兩個集合本身的資訊。

基於此，Gilmer 認為至少要有一個元素在集合中出現的機率大於等於 1%。

失之東隅，收之桑榆

當Gilmer 在11 月16 日發布他的證明時，他附上了一條說明—— 他認為使用他的方法可能更接近完整猜想的證明，有可能將閾值提高到38%。

五天后，三個不同的數學家團體在幾個小時內相繼發表了論文，他們在 Gilmer 的工作基礎上做到了這一點。這場爆發似乎已經將 Gilmer 的方法發揮到了極致，不過要達到 50%，可能需要更多的新想法。

不過，對於後續論文的一些作者來說，他們想知道為什麼 Gilmer 不自己做完相對簡單的達到 38% 的研究。事實上，原因並不複雜：在脫離數學超過 5 年後，Gilmer 只是不知道如何進行技術分析工作來實現這一目標。

「我有點生疏，老實說，我被困住了，」Gilmer 說。 「但我很想知道數學社群會把它帶到哪裡。」

但Gilmer 也認為，使他失去實踐機會的同一原因，在某種程度上也使他的證明首先成為了可能：「這是唯一的解釋—— 為什麼我在研究生院想了一年這個問題毫無進展，離開數學六年之後再回到這個問題上卻取得了突破。除了機器學習讓我的想法產生變化之外，我不知道還有什麼解釋。」

以上是白天打工，晚上科研，Google大腦研究科學家解決了困擾數學界幾十年的猜想的詳細內容。更多資訊請關注PHP中文網其他相關文章！