第六百六十九章 Frankl的并封閉集合猜想

　　對于一個(gè)包含至少2個(gè)集合的、對并運(yùn)算封閉的有限集合族，至少存在一個(gè)元素，使得它在至少一半的集合里出現(xiàn)過。

　　我們來解讀一下這個(gè)猜想說的啥。

　　首先集合，就是包含了一系列元素的合集，這里面的元素既可以是數(shù)字，也可以是變量等。

　　例如這是一個(gè)我們常見的數(shù)集，而且是有限的（只包括3個(gè)元素）：{1，2，3}

　　至于無限數(shù)集，就像是自然數(shù)集、有理數(shù)集、整數(shù)集這種由無限個(gè)元素組成的集合。

　　當(dāng)然，集合也有集合，它們組合起來，就可以被叫做集族，例如下圖中F就是一個(gè)集族：

　　在這些集族中，有一類特殊的集族對并運(yùn)算封閉。

　　對集族中的集合而言，并運(yùn)算就是對兩個(gè)集合求并集；至于并運(yùn)算封閉，即是指在對任意兩個(gè)集合進(jìn)行并運(yùn)算后，其結(jié)果仍然在這個(gè)集族中。

　　以下面這個(gè)集族為例：{1}{1，2}{1，2，3}{1，2，3，4}

　　無論是對{1}、{1，2}求并集，還是對{2，3，4}、{1}求并集，還是對{1，2}、{2，3，4}求并集……任意兩個(gè)集合求并集，其結(jié)果都會在這個(gè)集族中。

　　所以，上面這個(gè)集族就符合并封閉集合這一要求，而并封閉猜想也正是基于此而提出。

　　值得注意的是，這一猜想中的“一半”是緊致的，畢竟對于任何一個(gè)集合的子集族，所有的元素恰好在一半的集合里出現(xiàn)過。

　　它于1979年被一個(gè)叫Péter Frankl的數(shù)學(xué)家提出，所以也一度被叫做Frankl猜想。

　　看起來似乎不難，然而到實(shí)際解決時(shí)，一眾數(shù)學(xué)家才發(fā)現(xiàn)這并不簡單。

　　達(dá)特茅斯學(xué)院數(shù)學(xué)教授Peter Winkler曾經(jīng)在1987年就這個(gè)猜想給出尖銳的評價(jià)：

　　并封閉集合猜想確實(shí)很有名，除了它的起源和它的答案。

　　為了解決這個(gè)問題，數(shù)學(xué)家們也已經(jīng)嘗試過不少方法。

　　例如有人試著給猜想加上一些限制條件，讓它在這些情況下成立。

　　像是將它和圖論中的二分圖（Bipartite Graph）聯(lián)系起來，證明具備其中某種性質(zhì)的集族，在這個(gè)猜想的條件下成立。

　　又或是給其中的元素加以限制，再加以證明……

　　BUT，無論是哪種方法，距離真正需要證明的猜想都還差不少距離。

　　來自哥倫比亞大學(xué)的助理教授Will Sawin對此評價(jià)稱：

　　它看起來似乎是個(gè)不難解決的東西，畢竟長得和那種“容易解決的問題”很像。

　　然而，如今卻沒有任何一個(gè)證明能真正搞定它。

　　問題就這樣進(jìn)度緩慢，直到2022年秋天，谷歌研究員Justin Gilmer借著朋友結(jié)婚的契機(jī)，回到了羅格斯大學(xué)校園。

　　Gilmer回母校的時(shí)間是2022年10月，此時(shí)距他畢業(yè)離開數(shù)學(xué)學(xué)術(shù)圈，已過去7年。這些年來，他自覺無心專注純數(shù)學(xué)領(lǐng)域，轉(zhuǎn)而自學(xué)編程，投身了IT行業(yè)。

　　此次返校，他拜訪了導(dǎo)師薩克斯，還四處轉(zhuǎn)了轉(zhuǎn)。

　　就在散步中，他突然回憶起——當(dāng)年自己徘徊于校園小徑，苦苦思索的一個(gè)數(shù)學(xué)問題：

　　沒錯(cuò)，就是那個(gè)對“并封閉集合猜想”的證明。

　　讀博期間，Gilmer絞盡腦汁，花了一整年時(shí)間卻毫無進(jìn)展，只是搞明白了為什么這一看似簡單的問題難以解決。

　　為此，他還去找過導(dǎo)師薩克斯。但導(dǎo)師也曾在該問題上停滯不前，因而他既不看好Gilmer的研究，也不愿重新碰這一領(lǐng)域。據(jù)Gilmer回憶，當(dāng)時(shí)導(dǎo)師差點(diǎn)把他趕出房間。

　　但現(xiàn)在，重回校園轉(zhuǎn)一圈的Gilmer有了個(gè)新想法：用信息論及相關(guān)原理解決并封閉猜想問題。

　　Gilmer的思路是找反例。

　　根據(jù)并封閉集合猜想，一個(gè)正常的并封閉集族中，至少應(yīng)該有一個(gè)元素在多于一半的集合中出現(xiàn)。

　　既然如此，只要想辦法構(gòu)造一個(gè)特殊的集族，里面沒有一個(gè)元素出現(xiàn)在超過1%的集合中，這個(gè)猜想就會被證偽，反之如果構(gòu)造不出來，那么猜想就可能成立。

　　現(xiàn)在，我們用信息論視角看這一猜想：

　　正常來說，如果從集族中任意挑出兩個(gè)集合，這兩個(gè)集合取并集后，并集中的元素比原來兩個(gè)集合更多，其信息熵應(yīng)該比原來的單獨(dú)兩個(gè)集合更低。

　　然而如果基于“沒有一個(gè)元素出現(xiàn)在超過1%集合”這個(gè)限制條件，任意兩個(gè)集合取并集后，計(jì)算出來的信息熵竟然比原來的單獨(dú)兩個(gè)集合更高。

　　這顯然是不可能的，因此不存在這么一個(gè)特殊的集族，Glimer的反例也沒有找到。

　　但這也就意味著在“并封閉”集族中，至少存在一個(gè)元素，會出現(xiàn)在超過1%的集合中。

　　2022年11月16日，Gilmer將這一思路寫成論文，發(fā)表在了arXiv上。

　　當(dāng)然，他這篇論文還不是“完全體”，也就是說并沒有完全證明并封閉集合猜想——

　　畢竟這只是至少1%，還不意味著原來的并封閉集合猜想中的至少50%就成立。

　　但這個(gè)新思路已經(jīng)足夠讓學(xué)界震動。

　　普林斯頓大學(xué)數(shù)學(xué)家Ryan Alweiss評價(jià)“引入信息量”這一操作：非常聰明。

　　僅僅幾天后，就有3個(gè)不同的數(shù)學(xué)研究組基于他的研究，先后發(fā)表了研究論文，隨后也有更多研究者跟進(jìn)，他們所在院校機(jī)構(gòu)有牛津、普林斯頓、哥大、布里斯托等。

　　在后續(xù)研究中，對“并封閉集合猜想”的概率值證明，被推進(jìn)到了38%。

　　令這些數(shù)學(xué)家好奇的是，基于Gilmer的研究，他自己上手將概率值推進(jìn)到38%并不難。

　　對此，Gilmer表示，自己已經(jīng)五年多沒碰數(shù)學(xué)了，確實(shí)不知道如何進(jìn)行分析工作來將其進(jìn)一步推進(jìn)下去。

　　不過，他也認(rèn)為，正是因?yàn)閷ο嚓P(guān)數(shù)學(xué)方法的生疏，讓他跳出了常理，用圈外辦法取得突破。