只用2頁紙，北大數學校友攻破計算機30年難題！過程淺顯直白，看懂僅需線性代數基礎_風聞

邊策 發自 凹非寺

量子位 報道 | 公眾號 QbitAI

數學世界中有很多猜想，比如哥德巴赫猜想、黎曼猜想，有些問題已經困擾了全人類幾百年。

如果某一天，某個人突然跳出來説：“我只用幾頁紙，就證明了XX猜想。”大家一定會覺得這人是個“民科”。

最近，有位華人數學家黃皓宣佈，他證明了一個困擾計算機理論界30年的猜想，而且只用了兩頁紙。乍一看到這則消息，可能很多人的第一反應是：不會又是個“民科”吧？

然而事情並沒有這麼簡單。翻閲黃皓的履歷我們會發現，他本科畢業於北大數學系，並在2012獲得了UCLA的博士學位，現在他已經是美國埃默裏大學數學與計算機科學系的助理教授。

黃皓是真的解決了問題。他給出兩頁證明過程，只需要本科的知識就足以理解。數學界的同行們在拜讀過後，無不被他大道至簡的智慧所折服。

我們量子位將以儘量通俗的方式還原證明過程，與你一起解決這個跨世紀難題——布爾函數敏感度猜想（Boolean function sensitivity conjecture）。

首先，讓我們先從布爾函數説起。

布爾函數

（以下是布爾函數的解釋，熟悉編程的同學可以直接跳到第二部分。）

我們知道，數字電路都由邏輯門的組合實現任意功能，最常見的兩種邏輯門是與門和或門。

與門（AND）只有在輸入全是1的時候，才會輸出1，否則輸出0。

或門（OR）只要有一個輸入是1，輸出就是1，只有當輸入全是0的時候，輸出才是0。

同樣在輸入是(1,1)的情況下，與門會非常敏感，只要其中一個輸入發生變化，結果就會變成0。而或門只有兩個輸入全部發生變化的時候，結果才會變為0。

與門和或門只有兩個bit的輸入，是最簡單的情形。當有n個輸入bit輸入的時候，情形就變得複雜起來。

舉一個日常的例子，當你攢了多年的錢終於湊足首付後，要去銀行申請購房貸款。

銀行櫃員給了你一張表，裏面有很多很多問題，你只能回答是或否。最終你填寫的內容被一套複雜的過程處理，卻得出不能貸款給你的結論。

這套處理過程的輸入是布爾變量（是或否），輸出也是布爾變量（是否批准貸款），因此是一個布爾函數。

事後的你再回想起來，覺得可以把某些問題的回答反過來，也許還能通過申請。最終你發現需要改掉超過7個問題，才能改變審批的結果。

那麼我們就説，這個布爾函數在你最初答案的條件下敏感度是7。

對於一個布爾函數f，在某個輸入x（x是n個bit的布爾變量）的情況下，有超過s個布爾變量變化時，結果才會反轉。我們就説布爾函數f在輸入為x時的敏感度為s(f,x)。

所有敏感度s(f,x)的最大值s叫做布爾函數f的敏感度。

1989年，Nisan和Szegedy兩位猜測，s是關於n的一個多項式。這便是布爾函數敏感度猜想（Boolean function sensitivity conjecture）。

布爾函數敏感度猜想出現以來，就一直是計算機科學理論中最令人頭疼的開放性問題之一。解決了它就解決了邏輯電路、算法上的很多理論問題，比如我們熟知的n位二進制信號的奇偶校驗。

變成幾何遊戲

但是想直接證明布爾函數敏感度猜想實在太難了。好在1992年有兩位數學家Gotsman和Linial巧妙地把它變成了一個通俗的幾何遊戲。

他們把數字電路中的n比特轉化為n維空間中立方體的頂點。

比如一個2比特的輸入總共有4種可能性：00、01、10、11。相當於正方形的四個頂點：(0,0)、(0,1)、(1,0)、(1,1)。正方形就是二維空間中立方體。

同樣的，如果是3比特，就對應三維立方體的8個頂點，以此類推到更高的維度。

在立方體中，相鄰的兩個頂點只有一個座標值有差異，分別為0和1，其他座標值則完全相同。

因此，從立方體中的一個頂點移到它的相鄰頂點，就相當於把布爾函數輸入中的某個比特進行翻轉。（妙啊！）

既然布爾函數的輸入可以用頂點座標來表示，那麼輸出呢？我們可以用兩種顏色來定義。

比如用紅色表示0，藍色表示1。如果某個頂點是紅色，意味着頂點三個座標值組成的3比特輸入布爾函數後會得到0。

舉個例子：

在上圖的那個布爾函數中，若輸入是(0,1,1)，輸出將會是1。

倘若我們把第一位翻轉，好在布爾函數對這個變化並不敏感，輸出仍然是1，在圖中相當於把頂點移到了它的右邊，顏色還是藍色。

然而第三位翻轉後，布爾函數對這個變化是敏感的，輸出變為0，相當於把頂點移到了它的下邊，顏色從藍色變成紅色。

​如果在某種情況下，輸入結果的任何一位發生翻轉，輸出結果都會從1變成0，那也就意味着這個藍點周圍都是紅點，這個點的敏感度就是0，沒有藍點與它直接相連。

一個點周圍與它同色的點的數量，等於布爾函數在這個頂點的敏感度。布爾函數的敏感度就是所有頂點敏感度中的最大值。

於是布爾函數敏感度猜想可以簡化為N維立方體上的簡單問題：

如果將n維立方體的超過一半的頂點染成紅色，其餘染成藍色，是否總有一些紅點有同色的鄰居？如果有，周圍紅點的數量最多是多少？

Gotsman和Linial兩位的原話是這樣的：

設S是n維布爾超立方體{0,1} n任意子集，其大小為2n-1+1。那麼在S中必然存在一個點，在S中至少有nc個鄰居。（2n-1+1恰好比n維立方體的總頂點數一半多1個。）

其中c是一個介於0和1之間的常數，後面我們可以看到c=1/2。

如果被染成紅色的頂點恰好等於總頂點數的一半。它們可能互不相鄰。在三維立方體中就能找到一個例子：四個點（0,0,0），（1,1,0），（1,0,1）和（0,1,1）恰好都斜跨對角線。（下圖中的紅點）

但是，只要哪怕多增加一個點塗成紅色，紅點之間就必須出現連接。

靈感突發

即使布爾函數敏感度猜想已經在27年前已經被簡化，但是這個問題還是被繼續擱置了20多年。

直到7年前，當時博士剛剛畢業的黃皓，和新澤西州立大學的數學教授Michael Saks一起吃飯，聽對方聊到這個猜想。

黃皓默默地把這個問題加到了自己的“任務清單”裏。

藉助柯西

為了解決這個問題，黃皓想到使用一個200年前的數學定理：柯西交錯定理（Cauchy interlace theorem）。

這個定理將矩陣與它的子矩陣的特徵值聯繫起來，使其成為研究高低維立方體之間關係的完美工具。二維立方體(正方形)是三維立方體的一個面，因此是後者的一個子集。

柯西交錯定理的表述如下：

A是一個n×n階矩陣，B是A的m×m階主子矩陣(m<n)。矩陣A的特徵值為λ1 ≥ λ2 ≥ ̈ ̈ ̈ ≥λn，矩陣B的特徵值為μ1 ≥ μ2 ≥ ̈ ̈ ̈ ≥μm，那麼：

已經接近答案了，還差點什麼呢？可能是錢吧。

黃皓決定申請美國國家科學基金會撥款，進一步研究探討這一問題。

就在上個月，黃皓坐在馬德里的一家酒店裏，寫他的科研基金申請書時，突然靈感迸發：可以改變矩陣中某些數字的符號，推動證明過程，直至得出結果。

他構造了一組2n×2n階矩陣，定義為：

可以很容易用數學歸納法證明：

根據矩陣特徵值的定義，An的特徵值只能是√n 和-√n 。

而An的對角元素全部是0，因此矩陣的跡Tr(An)=0。我們知道矩陣的跡等於所有特徵值之和，所以√n 和-√n 的數量必須相等，都是2n-1個。

相鄰矩陣

如果H是一個有m個頂點的圖（由點和它們之間連線組成的圖形），A是一個對稱矩陣，並且A是圖H的相鄰矩陣。

所謂相鄰矩陣，是指A的第u行第v列元素表示H的第u個點和第v個點是否相鄰，如果不相鄰，這個元素就等於0；如果相鄰，這個元素就是-1或者1；此外對角元素必須等於0。

容易驗證，前面我們構造的矩陣An就是n維立方體Qn的相鄰矩陣。

假設圖H是n維立方體的一部分（準確地説，叫做立方體Qn的誘導子圖），那麼H的相鄰矩陣是An的一個主子矩陣。

假設λ1是矩陣A的最大本徵值，v是λ1對應的本徵向量，v1是本徵向量v裏絕對值最大的一個分量。

上面推導過程中第一個不等號成立的原因是和的絕對值小於絕對值的和。

第二個不等號也很簡單：∆(H)是圖H的敏感度，而左邊是某個點的敏感度，圖的敏感度是其所有點敏感度的最大值。

所以∆(H)≥|λ1|，即圖H的敏感度∆(H)大於矩陣A的最大本徵值的絕對值。

A是An的子矩陣。倘若H包含2n-1+1個頂點，帶入到柯西交錯定理中：

前面已經證明∆(H)≥|λ1|，所以∆(H)≥√n，而∆(H)就是n個bit布爾函數的敏感度。

證明完畢！

通過這種簡單的方式，黃皓證明了：在n維立方體中超過一半點的任何子集中，總會有一些點連接到至少√n 個其他同色的點，從這個結果中可以立即得出敏感度猜想。

尾巴

“我希望黃皓今年秋天能夠在碩士的組合數學課程講授（證明過程），只要一節課就夠了。”

法國國家科研中心的Clarie Mathieu看到了黃皓的證明時，不禁感嘆證明過程的簡單。

黃皓的結果甚至超過了證明靈敏度猜想所必需的結果，應該還會產生關於複雜性度量的新見解。比如用於n位二進制字符串的奇偶校驗算法。

“它增加了我們的工具包，可以幫助回答布爾函數分析中的其他問題，”哥倫比亞大學計算機科學教授Servedio説，“我認為很多人在聽到這個消息之後會在那個晚上睡得更輕鬆。”

不知道是什麼讓黃皓突然產生了靈感，但是有位網友説出了一種可能性：寫科研基金申請或許真的能幫助科研吧（笑）。

關於黃皓

黃皓2007年從北京大學數學系畢業，赴加州大學洛杉磯分校深造，於2012年獲得數學系博士學位，並獲得當年的學位論文獎學金。

他畢業後在普林斯頓大學高等研究院、明尼蘇達大學數學研究所從事博士後研究工作，之後進入埃默裏大學數學系，擔任助理教授，先後在Journal of Combinatorial Theory等學術期刊上發表過21篇學術論文。

黃皓的主要研究方向是極值與概率組合、結構圖論、理論計算機科學。

傳送門

論文鏈接：

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

https://arxiv.org/abs/1907.00847