有鑑於我的blog目標應該是推廣有趣的數學(in particular, extremal combinatorics)，我也該發點我不會做但別人會做的數學XD。由於建中/競賽/台大學弟Saintan最近在PhD job market上浮浮沉沉(?)並努力把它跟Shagnik最近的結果趕出來放上arXiv，就來介紹一下他們在幹麻吧！

我們先從經典的問題開始。問題很好敘述，所以就先上問題吧。

問題：給你的子集中的個子集，假設蒐集起來是，使得對於任何，也落在裡。請問是否存在一個元素出現在至少個中的集合裡？

由於這個set family 在取兩兩union這個操作下是closed的，所以猜測這命題是對的的猜想被稱為union-closed猜想。

而是緊的，因為你可以考慮所有個集合，每個元素都出現在個集合中。

在大約兩年前的某個月黑風高的夜晚(?)，arXiv上忽然冒出一篇來自google的Justin Gilmer的文章，證明了上面這個問題的弱化版本。他證明了總是有某個元素出現在至少有個集合裡。雖然看起來離還有很大一段距離，但在extremal combinatorics這是一大突破，至少他說明了線性in 是對的order。在此之前人類知道的只有更弱的界(存在元素在個集合裡)或是加強假設(假設固定的時候足夠大)的情況。而令人意外的是，這篇的證明相當的短，而在他的paper中也提到，如果把所有步驟都做到最好，可以得到。而證明的主要工具還是entropy(還沒看過Alon-Spencer的The Probabilistic Method第14.6章的讀者請點擊右上角資訊欄(#))。假設大家都會entropy的定義的話，就讓我們來看看這個證明的想法吧！

以下是Gilmer的證明(https://arxiv.org/abs/2211.09055)加上Will Sawin的優化(https://arxiv.org/abs/2211.11504)的證明outline。目標是假設每個元素都出現在不到個集合裡的話，導出矛盾。

首先，最核心的想法就是，如果你均勻隨機且獨立的從裡面取兩個集合，那根據定義這個隨機的集合也總是落在中，所以根據uniform bound它的entropy 。然而如果每個元素都出現很少次，那它出現在的機率就很低，那取完聯集每個元素出現在的機率會比起原本更接近，而我們都知道一個bit翻到(或是)機率越接近的話，entropy會越大，所以有可能可以證明，那就矛盾了！所以以下會專注在證明這條不等式上。

由於我們會用到每個元素出現的機率，我們就會想要考慮把集合 跟一個長度為的向量identify，就是說by abuse of notation，作為向量第紀錄的是在不在集合裡面。然後我們想要一位一位的看第位對entropy的影響，所以我們定義是的第位，是的前位，其他類似的符號同理。

那根據entropy的chain rule我們知道可以拆成的和，所以我們只需要證明每一項都是正的即可。我們固定任何一個，由於出現在不到個集合裡，所以的機率不到，也就有。

我們知道。而由於是獨立的，我們有。所以我們只需要證明。假設在給定的時候，分別是是的機率。則會是取決於的取值在的隨機變數。

令表示機率為的硬幣的entropy。我們知道conditional entropy可以想成是reveal conditional variable的entropy的期望值(對conditional variable取期望值)。我們還知道知道當固定的時候的分布是一個機率的硬幣，而的分布是一個機率的硬幣。於是我們可以把寫成，其中是對取期望值。然後關於第個元素出現在裡的機率的條件，可以改寫為。

於是呢，我們成功把問題化簡為一個關於機率分布的不等式問題：

問題：假設是上的一個機率分布。令是兩個服從且獨立的隨機變數，且。試證明。

證明之前，我們先來看看為什麼是這個數字。假設你前面的bit都沒給你任何資訊(或是你再看第一個bit)的話，那都是固定的數字，然後期望值取了個寂寞。這時候你會有，然後你想要的是，但我們知道，而的時候，所以union之後entropy反而離最高峰更遠了。

我們回到上面那個問題的證明。接下來我們稍微講一下這個證明的關鍵，詳細細節請看Sawin的paper。

注意到我們要證大於零的那項只取決於我一開始給你的分布，所以基本上我們就是要問說固定期望值之下，哪個讓那項最小。

我們假設就是讓那項最小的機率分布。其中一個重要的觀察是同時也是讓最小的分布among所有。我們可以用這件事情刻劃該長怎樣。

我們令，則努力對微分可以得到的反曲點至多只有一個。於是用數奧常見的EV (?)，也就是把凸的部分的分布都往中間挪，凹的部分往外面挪，這樣取值的期望值會更小。所以我們可以假設的機率集中在兩個點上，然後再努力一點就可以得到想要的不等式了。

證明大致就是這樣，可以繼續講故事了(?)。到現在為止最好的紀錄稍微比再更好一點。目前知道的是，離還有一段距離。

那Saintan跟Shagnik做了什麼呢？人們問了最常出現的元素，就會很自然問第二常第三常出現之類的。於是他們給出了以下的敘述的證明，大致上回答了這個問題。(https://arxiv.org/abs/2412.03862 and https://arxiv.org/abs/2412.03863)

定理：令。假設是union-closed且。則第常出現的元素出現在至少個集合裡。

而這個定理是緊的，構造就留給讀者思考(或是去看他們paper XD)。那好奇的讀者就會問拉，呢？Saintan表示他還在努力，剩下一堆finite case。而會剩finite case的原因也很妙，因為他們的bound來自兩邊。當很小的時候，傳統的方法的反而是會打贏的，而當大的時候，可以用類似上面的entropy方法做。其中需要更改的部分只有，你會有個bit的entropy貢獻不一定是正的，但實際上也不會負的太多，所以還是可以被其他bit的貢獻蓋過。