來源：市場資訊

（來源：機器人全球資訊）

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

敘舊期間，他們并未談及數(shù)學。事實上，自從 2015 年在羅格斯大學獲得博士學位后，Gilmer 就再沒認真思考過數(shù)學問題。那時候他決定不在學術界發(fā)展，同時開始自學編程。當他和 Saks 共同用餐時，Gilmer 向?qū)熤v述了自己在谷歌的工作：機器學習和人工智能。

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

但在七年后的這次訪問后，Gilmer 突然有了全新的靈感。他開始思考如何應用信息論來解決并封閉集猜想。經(jīng)過一個月的研究后，通往證明的路徑不斷打開。11 月，他在 arXiv 上發(fā)布了研究結(jié)果，宣布在證明整個猜想方面取得了重大進展。

論文鏈接：https://arxiv.org/pdf/2211.09055.pdf

這篇論文掀起了后續(xù)研究的熱潮。牛津大學、麻省理工學院和高等研究院等機構(gòu)的數(shù)學家們迅速在 Gilmer 的新方法基礎上開展工作。

什么是并封閉集猜想？

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

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

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

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

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

首先，在現(xiàn)成的并封閉集族的例子中，其中所有元素正好出現(xiàn)在 50% 的集合中。比如說，你可以用數(shù)字 1 到 10 組成所有不同的集合，總共會有 1024 個這樣的集合。它們構(gòu)成了一個并封閉集族，10 個元素中的每一個都出現(xiàn)在其中的 512 個集合。

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

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

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

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

不確定性的洞察

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

在這一點上，他已經(jīng)在通往破解的路上了，盡管他還不自知。

信息論在 20 世紀上半葉得到發(fā)展，其中最著名的是 Claude Shannon 1948 年的論文《通信的數(shù)學理論》。這篇論文提供了一種精確的方法來計算發(fā)送信息所需的信息量，基于圍繞著信息表達內(nèi)容的不確定性的大小。這種信息和不確定性之間的關聯(lián)，正是香農(nóng)的卓越見解。

信息論經(jīng)常出現(xiàn)在組合學中，這是一個與計數(shù)對象有關的數(shù)學領域，這也是 Gilmer 在研究生時期研究的內(nèi)容。但當他飛回加州的家中時，他還擔心將信息論與并封閉集猜想聯(lián)系起來的方式是一個業(yè)余者的天真見解。

「說實話，我有點驚訝之前沒有人想到這個，」Gilmer 表示?！傅苍S我不應該感到驚訝，因為我自己也想了一年，而且我是懂信息論的?！?/p>

探索難題

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

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

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

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

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

這仍然很低，但更接近 50% 的猜想，這意味著需要更多信息才能共享結(jié)果。換句話說，如果存在一個并封閉集族，其中任何元素在所有集合中出現(xiàn)的概率都小于 1%，則兩個集合的并集比任何一個集合本身包含的信息要多。

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

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

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

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

基于此，Gilmer 認為至少要有一個元素在集合中出現(xiàn)的概率大于等于 1%。

失之東隅，收之桑榆

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

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

不過，對于后續(xù)論文的一些作者來說，他們想知道為什么 Gilmer 不自己做完相對簡單的達到 38% 的研究。事實上，原因并不復雜：在脫離數(shù)學超過 5 年之后，Gilmer 只是不知道如何進行技術分析工作來實現(xiàn)這一目標。

「我有點生疏，老實說，我被困住了，」Gilmer 說。「但我很想知道數(shù)學社區(qū)會把它帶到哪里。」

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

原文鏈接：https://www.quantamagazine.org/long-out-of-math-an-ai-programmer-cracks-a-pure-math-problem-20230103/