JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

球填裝與 Helly-Radon-Carathéodory 定理

等大的球能多密地填滿空間,以及三個關於相交凸集的小定理為何悄悄支配著整個組合幾何——這一關的收尾,正是填裝與數字 n+1 交會之處。

這一關走過的路,以及落腳之處

這一關以凸體與從外側觸碰它的支撐超平面開場,再走到多面體以及 Euler 與 Dehn-Sommerville 的面計數,接著用Brunn-Minkowski 不等式與混合體積秤量體積,最後以Minkowski 格點定理把空間算術化。這最後一篇,就是把線頭收攏的地方。我們拿起兩個聽來像廚房問題的提問:等大的球能堆得多緊,以及要驗證多少才能斷定一整族凸集共有一點?前者是球填裝,後者是 Helly-Radon-Carathéodory 三定理。

這兩個主題看似互不相識,卻都繫於同一個隱藏的常數:在 R^n 中,凸性由數字 n+1 統治。凸包中的一點,早已是原始點裡至多 n+1 個的平均;一族凸集,只要其中每 n+1 個都有交,整族瞬間就有公共交;而我們真正能證明為最優的填裝,只住在那些恰好存在極為剛硬的格的維度(8 與 24)。請把 n+1 記在心上——它是底下一切的低調主角。

Carathéodory:凸包由小委員會拼成

從三者中最節省的一個開始。Carathéodory 定理說:若點 x 落在 R^n 中某集合 S 的凸包裡,則 x 已經落在 S 中至多 n+1 個點的凸包之中。無論 S 多麼龐雜——百萬個散落的點、整片區域——其凸包內的每一點,都是一個規模僅 n+1 的小委員會的加權平均。在平面(n=2)中,這表示凸包的每一點都落在某個三頂點皆屬於 S 的三角形內;在空間(n=3)中則落在某個四面體內。

為何是 n+1 而非更少?證明是一個乾淨的維數計數。設 x 寫成 m 個點的凸組合,且 m > n+1。那麼這 m 個點仿射相關,因為 R^n 至多容納 n+1 個仿射獨立的點——於是存在非平凡關係 sum c_i = 0 且 sum c_i v_i = 0,諸 c_i 不全為零。沿著這個關係滑動權重,齊步增減,直到某個權重首先觸零;你便丟掉了一個點,而 x 仍是其餘各點的凸組合。重複直到只剩 n+1 個點。你所利用的這個關係,正是在側翼候場的 Radon。

Radon 與 Helly:交集何時被迫出現

Radon 定理是引擎室。R^n 中任意 n+2 個點都可分割成兩個不相交的組,使兩組的凸包相交。在平面中這是一個關於四點的事實:任意 4 個點恰落入兩種情形之一——三點構成三角形而第四點在其內(把內點對三角形分開),或四點呈凸位置(分成兩條交叉的對角線)。無論哪種,兩個子凸包都重疊。其證明沿用 Carathéodory 那條仿射相關關係:n+2 個點時,關係 sum c_i = 0、sum c_i v_i = 0 必然存在;把係數為正的點放一組、為負的放另一組,重新縮放使兩側權重各自和為 1,則兩個組合的共同值就是那個見證點。

由 Radon,Helly 定理可對集合個數作歸納而推得。Helly 說:在有限多個 R^n 中的凸集裡,若其中每 n+1 個都有公共點,則全體共有一個公共點。最引人注目之處是這由局部到整體的躍遷——你從不一次審視整族,只看它的 (n+1) 元子族。在直線上(n=1)它退化為一個可徒手看出的事實:兩兩相交的區間有公共點。取最大的左端點 a 與最小的右端點 b;「每兩個相交」便迫使 a <= b,而 [a, b] 中任一點都屬於全部區間。

球填裝:一個沒有簡單答案的簡單問題

現在轉到這一關的另一極。球填裝問題求 R^n 中全等、互不重疊的球所能覆蓋的最大比例——填裝密度。維度 2 的答案是硬幣的蜂巢排列,密度 pi / sqrt(12) ~ 0.9069,已被嚴格證明(先 Thue,後 Fejes Tóth)。維度 3 的答案是水果攤的橘子堆,即面心立方排列,密度 pi / sqrt(18) ~ 0.7405——也就是克卜勒猜想,1611 年提出,直到 Hales 於 1998 年的電腦輔助證明才解決,並遲至 2014 年才完成機器形式化。

這裡誠實至關重要。維度 3 以上幾乎一切都未解——只有兩個奇蹟例外。維度 8 的最密填裝是 E_8 格,維度 24 是 Leech 格;兩者的最優性都遲至 2016 年才被證明(Viazovska 證維度 8,隨後 Cohn-Kumar-Miller-Radchenko-Viazovska 證 24)。其工具是一張神奇的證書:一個輔助函數,其傅立葉變換恰在正確的半徑處消失,逼出一個恰好與該格密度分毫不差的上界。對其餘所有 n >= 4 的維度,確切的最優密度就只是未知。這直接繞回上一篇:這些紀錄填裝都是填裝,因此數的幾何正是此問題的自然居所。

n=2:   pi/sqrt(12)  ~ 0.9069    hexagonal       (proved: Thue / Fejes Toth)
n=3:   pi/sqrt(18)  ~ 0.7405    FCC / Kepler     (proved: Hales)
n=8:   pi^4/384     ~ 0.2537    E_8 lattice      (proved: Viazovska)
n=24:  pi^12/12!    ~ 0.00193   Leech lattice    (proved: CKMRV)
other n>=4:                     optimal density  UNKNOWN
所有已知最優球填裝密度的維度——一份短得驚人的清單。

為何兩半其實是同一門學問

填裝與組合凸性之間的橋樑是線性規劃界。Cohn 與 Elkies 把填裝重塑為對函數的最優化:選一個具備恰當符號型態與傅立葉行為的輔助函數,它便證明了密度的一個上界。這正是 HellyCarathéodory 的精神——以一張小而可查的證書,取代不可能的全域搜尋。Viazovska 的突破,在於用模形式在維度 8 與 24 中構造出恰好緊的證書。組合凸性與解析填裝是同一思想的兩面:在凸幾何中,全域真理被一個有限的、低維的見證所釘定。

  1. 實務上運用 Helly:把目標表述為「是否存在單一一點屬於每個集合?」,驗證每個集合確實是凸的,然後只檢查 (n+1) 重交——若那些全都非空,則全域交也非空。
  2. 要取得填裝上界(Cohn-Elkies):找一函數 f,滿足 f(0) > 0、當 |x| >= r 時 f(x) <= 0、且其傅立葉變換處處非負;則填裝密度至多為一個由 f 直接讀出的比值。
  3. 要辨認該界何時為緊:它必須恰好吻合某個已知的格填裝——這發生於 E_8(n=8)與 Leech(n=24),而就我們能證明的範圍而言,幾乎別無他處。

這便為凸與離散這一關收尾。你現在能同時從三個角度閱讀同一個凸體:作為被支撐超平面釘住的形狀,作為受 Brunn-Minkowski 支配的體積,以及作為服從 Helly-Radon-Carathéodory 之 n+1 律的組合物件。同一個體,三座塔——而球填裝正是三者彼此倚靠之處。

常見陷阱與誠實的界限

繼續攀登前,幾點提醒。其一,每個定理中的常數是周圍維度的 n+1(Radon 則為 n+2),且它不取決於你有多少集合或多少點——這個只與維度相關的常數,正是這些結果如此強大之處,也正是當某集合非凸時它們瞬間瓦解的原因。其二,「已知最密」不等於「可能最密」:對多數維度,我們握有的是無人勝過的填裝,而非無人能勝過的證明。其三,克卜勒與維度 8/24 的結果是有完整證明的真定理,但 8/24 維的證明倚賴深刻的模形式構造——導引能陳述並闡明它們,卻無法重現它們,你應對這道鴻溝對自己誠實。

最後,別把「密度隨維度遞減」當成定律。在我們少數能計算的情形它確實驟降,但一般高維 n 的真正最優密度仍屬未知,而且隨 n 增大,最佳下界與上界之間的差距甚至持續擴大。一如這道階梯上的別處,關於開放問題的誠實——除 8 與 24 兩個例外,幾乎所有高於 3 的維度其最優填裝仍未解——對一位研究生讀者的幫助,遠勝於一份整潔卻虛假的圓滿感。