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

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

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

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

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

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

什么是并封閉集猜想？

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

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

將任何一對(duì)組合起來(lái)，你就會(huì)得到一個(gè)已經(jīng)在族中存在的集合，所以說(shuō)這個(gè)族是并封閉集的。

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

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

?

Justin Gilmer

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

在 Frankl 提出這個(gè)猜想的時(shí)候，還沒(méi)有人提出過(guò)一個(gè)猜想不成立的并封閉集族的例子。所以 50% 似乎是正確的預(yù)測(cè)。

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

哥倫比亞大學(xué)的 Will Sawin 說(shuō)：「感覺(jué)它應(yīng)該很容易，而且它與很多容易的問(wèn)題相似，但它一直未被攻克。」

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

不確定性的洞察

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

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

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

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

「說(shuō)實(shí)話，我有點(diǎn)驚訝之前沒(méi)有人想到這個(gè)，」Gilmer 表示?！傅苍S我不應(yīng)該感到驚訝，因?yàn)槲易约阂蚕肓艘荒?，而且我是懂信息論的?！?/span>

探索難題

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

Gilmer 謙虛地說(shuō)道：「也許你認(rèn)為解決數(shù)學(xué)難題的人不應(yīng)該查閱《Elements of Information Theory（信息論基礎(chǔ)）》第 2 章，但我查閱了?！?/span>

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

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

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

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

「逐個(gè)元素證明猜想的思路非常聰明」，普林斯頓大學(xué)的 Ryan Alweiss 評(píng)價(jià)道。

Gilmer 的工作開始接近 Frankl 的猜想。這是因?yàn)楹苋菀鬃C明：在并封閉集族中，兩個(gè)集合的并集包含的信息必然少于兩個(gè)集合本身 —— 而不是更多。

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

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

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

失之東隅，收之桑榆

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

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

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

「我有點(diǎn)生疏，老實(shí)說(shuō)，我被困住了，」Gilmer 說(shuō)?！傅液芟胫罃?shù)學(xué)社區(qū)會(huì)把它帶到哪里?！?/span>

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