摘要: 吻球數問題 (kissing number problem) 是數學界著名且至今尚未完全解決的難題, 其中三維情形在克卜勒、 牛頓等大師於歷史層面的催化下更顯引人入勝。 本文除了介紹吻球數問題之外, 也會詳述俄國數學家 Oleg R. Musin 在西元 2006 年發表的對三維吻球數的解決手法。 該方法使用了二十世紀誕生之 Delsarte 線性規劃方法的拓展形式。 以往的線性規劃方式可以證明在八維與二十四維的吻球數, 媒介是設計一個輔助多項式 $f(t)$, 使得變數落在 $[\cos\pi, \cos\pi / 3]$ 區間都會是非正實數, 搭配蓋根包爾多項式 (Gegenbauer polynomials) 基底係數非負的特性可以評估吻球數的上界, 進而在上述兩個維度上取得進展, 但是這個流程在三維時僅能估計出上界為 13, 因此 Musin 軟化了輔助多項式的條件, 允許 $f(t)$ 在一個小於 $60^\circ$ 的角 $\theta_0$, 變數落於 $[\cos\pi, \cos(\pi - \theta_0)]$ 可以為遞降的非負函數, 此時論述視角會聚焦在以北極為中心, 夾角 $\theta_0$ 所形成的球蓋 (spherical cap), 配合球面三角公式、 微積分、 以及程式的操作下, 得出三維吻球數為 12, 而此數又稱作牛頓數。}

1. 歷史進展

1.1. 克卜勒猜想與吻球數問題

試問在三維空間中心部署一顆單位球, 最多有幾顆單位球可以同時與中心單位球保持碰觸？

這個問題是離散幾何領域當中十分有名的, 此即三維空間上的吻球數問題 (kissing number problem, 見圖 1 (c)), 其中吻球 (kiss) 的字詞是援引自撞球的術語, 用來描述在兩顆撞球碰撞時的行為; 而實際上我們也會考慮在任意維度上的情形。

吻球數問題的探悉可以幫助理解最密堆疊問題 (sphere packing problem), 這個議題是說 : 給定數顆單位球後, 試找出在 $n$ 維度歐式空間中使其堆疊密度最高的布置方法。 在一書《六角的雪花》中克卜勒 (Kepler) 曾指出 : 根據對石榴種子的觀察, 推測說在自然界中由於植物果實的空間有限, 因此所有種子都必須緊密地聚合在一起, 在種子成長時顯然會經過一種排列, 使得整個空間利用會是最佳的, 若以單一種子為中心, 周圍將有十二顆種子包圍之並以正二十面體之頂點形式排列。 以單位球取代種子來說, 克卜勒便認為在三維空間中, 使用六方最密堆疊會是數顆單位球的最佳堆疊方式。 著名的克卜勒猜想 (Kepler's conjecture) 由此而生。

回到我們的主題, 在一維數線上, 吻球數這個問題是顯而易見的 : 左右各一顆球, 總共二顆; 在平面上, 我們以球為中心依照角度劃分六等分, 在每個等分射線上擺上一顆球, 總共六顆也可以完整地包覆中心球。

在三維情形, 考慮一單位球於原點處, 此時布置十二顆單位球在一正二十面體的頂點上 $$ (0, \pm r, \pm r\varphi),\quad (\pm r, \pm r\varphi, 0),\quad (\pm r\varphi, 0, \pm r), $$ 其中 $\varphi = (1+\sqrt{5}) / 2$ 且 $r = 4 / \sqrt{10 + 2 \sqrt{5}}$, 則此十二顆球可以在不互相重疊的條件下與中心球碰觸。 然而當實際擺放時, 會發現這些球之間會有相當程度的空隙。 以上面的範例來說, 任鄰近二球心的距離大約是 2.1, 大於二單位球不重疊情況下、 球心最低距離 2。

圖1: 吻球數問題在不同維度情形。

在這個「鬆弛」現象下, 筆者便想請教各位讀者 : 當我們有計畫性地挪動上頭的球, 是否有機會空出足夠的空間擺放第十三顆球呢？

在 1950 年代, 英國有一位督學名叫特恩布爾 (H.W. Turmbull), 專門研究牛頓 (Isaac Newton) 的生平事蹟。 在研究過許多文章、 信件與筆記後, 他找出了兩份當時與吻球數問題有關的文獻。 一份是兩位科學家牛頓與大衛$\cdot$葛瑞高里 (David Gregory) 在 1694 年於劍橋討論時的備忘錄, 另一份則是葛瑞高里位於牛津基督教堂內的一未公開筆記 ^{2 2} 歷史細節可參考 George G. Szpiro 原著, 葉偉文先生翻譯之《刻卜勒的猜想》 第五、 六章, 或是由 Rob Kusner 等人撰寫之 《Configuration Spaces of Equal Spheres Touching a Given Sphere: The Twelve Spheres Problem》 內文第二節。 。

備忘錄涵蓋的主題可謂包羅萬象, 而其中一個主題, 備忘錄編號 13 的事項中, 出現了葛瑞高里同樣也向牛頓詢問的題目 :

「一顆堅硬的球, 能不能與同樣大小的 13 顆球同時保持接觸？」

在另一份未公開筆記 ^{3 3} 根據 J. Leech 所述, 此筆記位於牛津大學基督堂學院。 中, 葛瑞高里同樣拋出這道問題, 但此時一個具爭議的論述產生 :

「在三維空間中可同時有十三顆等大小的球碰觸中心球。」

這段宣稱便與牛頓在《1671 年討論固定星星的表 A table of ye fixed starrs for ye year 1671》中提到的相互牴觸 : 同樣的是文中也提到 13 這個數字, 但不同的是他把中間那顆也算進去了。

至此整件事情開始撲朔迷離, 究竟是「最多 13 顆同時碰觸」, 還是「最多 12 顆同時碰觸」呢？而這個問題直到近兩個半世紀後才獲得解答。

1.2. 十九世紀末到現在

Reinhold Hoppe 在 1894 年時提出一個解法, 但所使用的方法有些錯誤 ^{4 4} 黑爾斯 (Thomas Hales) 在 1994 年也發表文章分析 Reinhold Hoppe 方法的問題。 , 到了二十世紀中期, 許特 (Kurt Schütte) 與範德瓦爾登 (van der Waerden) 在 1953 年給出了第一份完整的證明, 隨後 1956 年里希 (John Leech) 提出了一個優雅證明的草圖, 其後 Aigner 和 Ziegler 在兩人出版的書中將里希提出的證明完成; 在近代, 也有許多數學家提出更多更簡潔的方法來解決這個問題, 而本篇文章深入探討的方法也是其中之一 --- Oleg R. Musin 在 2006 年所發表的文章; 他使用了 Delsarte 之線性規劃為基礎所衍生的方法 (an extension of Delsarte's method) 去解決這個問題, 也利用了球面幾何方面的特性與線性規劃工具去輔助這項研究工作, 而其證明過程將會在下一個章節進行詳細說明。

另外, 科學人雜誌 2012 年 10 月號李國偉教授的「球球有限制」介紹了平均 Kiss 數問題, 其中提到了 1994 年 Greg Kuperberg 與 Oded Schramm 將此上界降低到 15, 若有興趣的讀者也可以參考閱讀。

1.3. 其餘維度

除了三維空間的吻球數之外, 數學家也為了了解在其他維度空間中的吻球數, 紛紛展開了研究, 但不幸的是目前大於三維的維度空間中僅有四維、 八維與二十四維空間有著精確的解答, 其餘維度目前都僅能估計出其上下界。在最近的研究進展中, 主要分成線性規劃 (Linear Programming) 結合半正定規劃 (Semi-definite Programming, SDP) 方法的流派,,、 以及線性規劃結合幾何手法的流派,; 而截至目前為止, 在 24 維度以下的吻球數已知上下界如表 1 所示, 且表中能夠發現在四維以上中, 僅四、 八、 與二十四維度的上下界會非常可愛地碰在一起。

2. 三維吻球數證明手法

2.1. 問題描述

我們可以將吻球數轉換成將單位球擺在原點 $O$, 其它與其相切且彼此相切的單位球球心為

表1: 二至二十四維度目前已知吻球數之上下界

Dimension	Lower bound		Upper bound
1		2
2		6
3		12
4		24
5	40		44
6	72		78
7	126		134
8		240
9	306		364
10	500		554
11	582		870
12	840		1357
13	1154		2069
14	1606		3183
15	2564		4866
16	4320		7355
17	5346		11072
18	7398		16572
19	10668		24812
20	17400		36764
21	27720		54584
22	49896		82340
23	93150		124416
24		196560

$O_1, O_2, \ldots, O_N$, 現在的目的為證明 $N \leq 12 $。 而接下來的論述需要時常用到 $\angle{O_i O O_j}$, 為求簡潔我們定義 $\phi_{ij} = \angle{O_i O O_j}$。 由圖 2 可知 $\phi_{ij} \geq 60^\circ$, 所以 $\cos\phi_{ij} \leq \dfrac{1}{2} $。 接著為方便表示, 我們將不同數量 $N$ 個淺色球佈點的所有可能表示成 $X = \{x_1, x_2,\ldots, x_N\}$, 其中 $x_i$ 為單位球與中心球的切點。

2.2. 方法描述

由於論述的過程較長, 因此在正式開始鋪陳前, 我們有必要事先組織其證明手法。

對於任一 $X$, 我們將設計一個特殊的多項式函數 $f:\mathbb{R}\to\mathbb{R}$, 使得下列值 $$ \sum_{i=1}^N\sum_{j=1}^N f(\cos\phi_{ij}) $$ 本身會是有界的, 其中下界由引理一與引理二得出, 並且該下界會與點數 $N$ 有關; 上界則是由引理三得出, 推論中會大量利用函數 $f$ 的特性, 以及球面幾何上的性質去逐步得到上界, 同樣與點數 $N$ 有關; 最終根據不等式的處理, 得出 $N\lt 13$ 之結果, 即三維吻球數小於 13 這項定理。

2.3. 引理與定理描述

首先介紹勒壤得多項式 (Legendre polynomial) $G_k(t)$, 其為蓋根包爾多項式 (Gegenbauer polynomial) $G^{(n)}_k$ 在 $n = 3$ 的情況; 讀者可以將蓋根包爾多項式理解成他是一個以 $t$ 為變數的一元 $k$ 次多項式, 並且 $n$ 為組成該多項式的一個係數, 或者說常數; 而勒壤得多項式以遞迴表示方法如下 : $$ G_0(t) = 1,\quad G_1(t) = t,\quad G_k(t) = \frac{(2k - 1) t G_{k-1} - (k-1)G_{k-2}}{k}. $$

在 1942 年數學家 I.J. Schoenberg 證明了在一 $X$ 任意給定下, 一矩陣 $$ [G_k^{(n)}(\cos\phi_{ij})]_{i,j} = \begin{bmatrix} ~G_k^{(n)}(\cos\phi_{11})~ & \cdots & ~G_k^{(n)}(\cos\phi_{1N})~ \\ \vdots & & \vdots \\ ~G_k^{(n)}(\cos\phi_{N1}) ~&~ \cdots ~&~ G_k^{(n)}(\cos\phi_{NN})~ \end{bmatrix} $$ 是半正定 (positive semi-definite) 的, 意思是說對於任何一個向量 $v\in\mathbb{R}^N$, 值 $v^T [G_k^{(n)}(\cos\phi_{ij})] v$ 必為非負實數。 因此, 令 $v=(1,\ldots,1)\in\mathbb{R}^N$ 時, 我們便得到以下第一個引理 :

引理 1(Delsarte's Inequality). 對於任意 $X$, 我們有 $$ \sum_{i=1}^N \sum_{j=1}^N G_k (\cos\phi_{ij}) =\sum_{i=1}^N \sum_{j=1}^N G_k^{(3)} (\cos\phi_{ij}) = v^T [G_k^{(3)}(\cos\phi_{ij})] v \geq 0. $$

接著利用線性規劃工具 ^{5 5} 關於線性規劃方法可參考附錄 A 。 , 我們可以找到一多項式 $$ f(t) = \sum_{k=0}^9 c_k G_k (t) = G_0 + \frac{8}{5} G_1 + \frac{87}{25} G_2 + \frac{33}{20} G_3 + \frac{49}{25} G_4 + \frac{1}{10}G_5 + \frac{8}{25}G_9 $$ 滿足以下給定條件 :

1. $c_0 = 1$, 對於 $k\gt 0$ 則有 $c_k\geq 0$,
2. $\cos\theta_0 = t_0 \approx 0.5907$, 且
3. $f(t)$ 在區間 $[-1, -t_0]$ 遞減。

在係數 $c_k$ 非負的條件給定下, 我們就有足夠假設去推論出目標函數 $$ S(X) := \sum_{i=1}^N\sum_{j=1}^N f(\cos\phi_{ij}) $$ 的下界 :

引理 2 對於任一 $X$, 我們有 $$ S(X) \geq N^2. $$

證明: 把函數展開, 由引理一我們得知 $$ \begin{aligned} S(X) &= \sum_{i=1}^N\sum_{j=1}^N f(\cos\phi_{ij}) \\ &= \sum_{i=1}^N\sum_{j=1}^N \sum_{k=0}^9 c_k G_k (\cos\phi_{ij}) \\ &= \sum_{i=1}^N\sum_{j=1}^N c_0 G_0(\cos\phi_{ij}) + \sum_{k=1}^9 c_k \sum_{i=1}^N\sum_{j=1}^N G_k (\cos\phi_{ij}) \\ &\geq \sum_{i=1}^N\sum_{j=1}^N c_0 G_0(\cos\phi_{ij}) = N^2. \end{aligned} $$ 故 $S(X)\geq N^2$. $\Box$

緊接著我們介紹引理三, 但先不證明它 :

引理 3. 對於一 $X$ 滿足對於任意相異點 $x_i$ 與 $x_j$ 有 $\cos\phi_{ij} \lt 1/2$, 則 $$ S(X) \lt 13N. $$

建立在這個強引理的基礎上, 搭配引理二可得到三維吻球數問題的核心定理 :

定理 4. 三維吻球數為 $12 $。

證明: 由引理二及引理三我們有 $$ N^2 \leq S(X) \lt 13N. $$ 由於 $N$ 為正整數, 我們有 $$ N \lt 13, $$ 並且已知三維吻球數的下界為 $12$, 故三維吻球數為 $12 $。 $\Box$

很開心地我們得到了最重要的成果, 現在我們剩下一個疑問 : 要如何證明引理三？

3. 引理三證明

我們將證明引理三的過程分成幾個階段 : 問題簡化、 探討球形蓋上最多點數並進行上界估計。

3.1. 球面餘弦定理

在證明引理三之前, 我們先介紹球面餘弦定理 (Spherical law of cosines), 即為 : $$ \cos\phi = \cos\theta_1\cos\theta_2 + \sin\theta_1\sin\theta_2\cos\varphi. $$

證明: 如下圖三角形所示(3), 並令 $O$ 為單位圓心, 由於在單位球面上三角形的形狀並不會因移動與旋轉改變, 所以我們可以對三角形做以下操作 :

1. 將三角形移動到 $A$ 點在北極點上 (即 $(0, 0, 1)$ ), 並將其旋轉至 $B$ 點在本初子午線上,
2. 此時 $B$ 點與 $C$ 之球座標分別為 $(1, \theta_1, 0)$ 與 $(1, \theta_2, \varphi)$,
3. 將 $B$ 點與 $C$ 點之座標轉為直角坐標, 則此時 $B = (\sin \theta_1, 0, \cos \theta_1)$ 與 $C = (\sin \theta_2 \cos \varphi, \sin \theta_2 \sin \varphi, \cos \theta_2)$,
4. 由於 $\cos \varphi$ 為 $\overline{OB}$ 與 $\overline{OC}$ 向量之內積, 將其內積後則完成球面餘旋定理之證。$\Box$

3.2. 問題簡化

回顧由上述由線性規劃之條件找出的函數 $f$ 具備以下性質 :

1. $f(t)$ 在 $t \in [-1, -t_0]$ 時遞減 ($ t_0$ 為一常數),
2. $f(t)$ 在 $t \in (-t_0, \frac{1}{2}]$ 時小於 $0$,
3. $f(-t_0) = 0$ 且 $t_0 \approx 0.5907$。

接著我們令 $$ S_i(X) := \sum^{N}_{j = 1} f(\cos(\phi_{ij})). $$ 相當於在 $S(X)$ 中, 我們固定一個點 $x_i$ 並將其與其他點 $x_j$ 內積帶入函數值取和 (包括 $x_i$ 本身), 接著我們把目標放在對於每個固定的 $x_i$, 若我們有 $$ S_i(X) = \sum^{N}_{j = 1} f(\cos(\phi_{ij})) \lt 13, $$ 建立在上述目標上, 我們可得到 $$ S(X) = \sum^{N}_{i = 1} S_i(X) = \sum^{N}_{i = 1}\sum^{N}_{j = 1} f(\cos(\phi_{ij})) \lt \sum^{N}_{i = 1}13 = 13N, $$ 也就是引理三之敘述。

在 $t_0$ 給定下, 我們有 $\theta_0 = \arccos(t_0) \approx 53.794^{\circ}$, 不失一般性我們將 $x_i$ 視為南極點, 並定義 $e_0$ 為北極點; 由於 $f(t)$ 在 $t \in (-t_0, 1/2]$ 中皆為小於等於零的實數, 因此在點 $x_i$ 中, 我們可以將 $\cos\phi_{ij}$ 落在區間 $[-1, -t_0]$ 的點 $x_j$ 蒐集起來並令其為 $Y = \{y_1, \ldots, y_m \}$ (假設 $Y$ 中有 $m$ 個元素), 為了承接接下來的證明, 我們將 $y_j$ 與北極點 $e_0$ 的球面距離定義為 $\theta_j$, 即 $y_j$ 與 $x_i$ 的球面距離為 $180^{\circ} - \theta_j$; 此時 $Y$ 為使得 $f(\cos(180^{\circ} - \theta_j))$ 大於零的點之集合, 且由於 $f(1) \geq 0$, 我們可以推得 $S_i(X)$ 的值會小於 $f(1)$ 加上所有 $Y$ 中的點 $y_j$ 與 $x_i$ 內積 $\cos(180^{\circ} - \theta_j) = -\cos(\theta_j)$ 帶入 $f$ 取值之和 (令其為 $H(Y)$ ), 即 $$ S_i(X) \leq f(1) + \sum_{y_j \in Y}f(-\cos(\theta_j)) := H(Y). $$ 這樣一來, 我們可以將 $Y$ 集合上的點 $y_j$ 在幾何上的含意轉換成是落於以北極點為中心, 與北極點夾角小於等於 $\theta_0$ 的球蓋 (spherical cap) 上(見圖 5)。

至此我們發現說從原本的問題, 經由上界的估計轉化為僅考慮在特定球蓋上的佈點問題。意即, 固定一點 $x_i$, 僅蒐集點 $x_j$ 使得內積值丟進去函數 $f(x_i\cdot x_j)\geq 0$, 相當於取 $-1 \leq x_i\cdot x_j \leq -t_0$, 這些內積值帶入函數 $f$ 的總和即為 $S_i(X)$ 的上界。

對於一點 $x_i$ 以及點集合 $Y = \{y_1, \ldots, y_m\}$, 我們現在考慮在球蓋上的點 $y_1, \ldots, y_m$ 在吻球數問題上的限制條件。 具體來說 :

1. 任意兩相異點 $y_i, y_j$ 夾角皆大於等於 $60^{\circ}$, 即 $\phi_{ij} %= \mathrm{dist}(y_i, y_j) \ge 60^{\circ}$,
2. 任何 $y_i$ 須落在球蓋中, 即 $\theta_j := \angle e_0 O y_j \leq \theta_0 $。

接著我們令 $h_m$ 為 $Y$ 在不同 $m$ 的情況中其 $H(Y)$ 的最大值, 由於對於所有固定點 $x_i$ 與其相對應的 $m$ 我們有 $S_i(X) \leq H(Y) \leq h_m$, 所以我們只需證明出對於所有可能 $m$, $h_m$ 皆會小於 $13$; 而為了能夠對每一個 $m$ 的情形去做討論, 我們必須先找到在球蓋中滿足吻球數限制條件的最多點數為何, 即找 $m$ 的最大值。

3.3. 探討球形蓋上最多可能點數

將 $x_i$ 固定在南極點後, 滿足吻球數條件之球蓋上所有點 $Y = \{ y_1, \ldots, y_m \}$, 每個點 $y_i$ 都有著對應的球座標 $(\theta_i, \varphi_i)$, $\theta_i$ 為點 $y_i$ 與北極點 $e_0$ 的夾角且 $\varphi_i$ 是 $y_i$ 與本初子午線的夾角。

接著我們討論在球蓋上符合吻球數條件的點數最多有幾個, 而這時我們需要觀察 $Y$ 中任兩點 $y_i, y_j$ 之間的最小夾角度數。

顯然地, $\mu\gt 1$, 而在 $m \geq 2$ 時, 因為 $\theta_0 \approx 53.794^{\circ} \lt 60^{\circ}$, 且 $Y$ 中任兩點夾角都必須大於等於 $60^{\circ}$, 所以不會有任何一點 $y_i$ 在北極點 $e_0$ 上, 即 $\theta_i \gt 0$; 現在我們考慮在 $Y$ 中任意兩點與 $e_0$ 形成的三角形 $\Delta y_iy_je_0$ :

藉由 $Y$ 中任兩點夾角皆大於等於 $60^{\circ}$ 以及餘弦函數遞減的性質, 在此三角形中 $y_i$ 與 $y_j$ 的內積值 $\cos\phi_{ij}$ 會小於等於 $1/2$, 由球面餘弦定理可得 $$ \frac{1}{2} \geq \cos(\phi_{ij}) = \cos\theta_i\cos\theta_j + \sin\theta_i\sin\theta_j\cos(\varphi_i - \varphi_j). $$ 故 $$ \cos(\varphi_i - \varphi_j) \le \frac{\frac{1}{2} - \cos\theta_i\cos\theta_j}{\sin\theta_i\sin\theta_j}. $$ 給定函數 $$ Q(\alpha, \beta) := \frac{\frac{1}{2} - \cos\alpha\cos\beta}{\sin\alpha\sin\beta}\,. $$ 此時 $\cos(\varphi_i - \varphi_j) \leq Q(\theta_i, \theta_j)$, 由於 $Q(\alpha, \beta)$ 在固定 $\beta$ 時對 $\alpha$ 是遞增函數, 且 $Q(\alpha, \beta) = Q(\beta, \alpha)$, 故 $$ Q(\alpha, \beta) \le Q(\theta_0, \beta) = Q(\beta, \theta_0) \le Q(\theta_0, \theta_0). $$ 這時我們就能找到 $\cos(\varphi_i - \varphi_j)$ 的最大值 : $$ \cos(\varphi_i - \varphi_j) \le \frac{\frac{1}{2} - \cos^2\theta_0}{\sin^2\theta_0} = \frac{\frac{1}{2} - t_0^2}{1 - t_0^2}. $$ 如此一來我們就能夠得到任兩點最小的夾角值 $\varphi_i - \varphi_j$ : $$ \varphi_i - \varphi_j \geq \arccos(\frac{\frac{1}{2} - t_0^2}{1 - t_0^2}) \approx 76^{\circ}. $$

由於正五邊形之兩點夾角為 $72^{\circ}$, 在 $m = 5$ 時一定會有任兩點夾角 $\varphi_i - \varphi_j$ 小於等於 $72^\circ$, 與條件不符, 因此我們可以推得 $Y$ 中最多只會有四個點, 接著我們只需說明 $h_0, h_1, h_2, h_3, h_4$ 皆小於 13, 即完成引理三證明。

3.4. 討論最佳狀態及其上界估計

得知球形蓋上的最多可能點數後, 接著便是針對每一種可能去評估 $H(Y)$ 的上界。由於在球形蓋上的點 $y_i$ 與 $e_0$ 的距離和函數值呈遞減關係, 因此應盡可能將 $y_i$ 向 $e_0$ 靠攏。

結論來說, 根據某些理由 (細節請見 Appendix B),

• 當 $\vert Y \vert = 2$ 時, $e_0$ 會落於弧線 $y_1 y_2$ 上, 且 $y_1 y_2$ 長度為 $\dfrac \pi{3}$,
• 當 $\vert Y \vert = 3$ 時, $\Delta = y_1 y_2 y_3$ 會成為一個邊長為 $\dfrac \pi{3}$ 的正三角形, 且 $e_0$ 會位於該三角形內部,
• 當 $\vert Y \vert = 4$ 時, $\Diamond = y_1 y_2 y_3 y_4$ 會成為一個邊長為 $\dfrac \pi{3}$ 的菱形, 且 $e_0$ 會位於該菱形內部。

在開始逐項討論前, 先註記 $h_0 = f(1) = 10.11 \lt 13$.

3.4.1. $ \vert Y \vert=1$ : 我們與 $e_0$ 的距離

根據 $f$ 的特性, 我們得知 $y_1$ 在 $e_0$ 時, 對應的值為 $f(-\cos\theta) = f(-1)$, 是區間 $[-1, 0.5]$ 的最大值, 故 $h_1 = f(1) + f(-1) = 12.88 \lt 13$.

3.4.2. $ \vert Y \vert=2$ : 跨越 $e_0$ 的線段 $y_1 y_2$

圖7: $ \tilde{F}_1$

給定函數 $$ F_1(\psi) = \max_{\frac{\psi}{2}\leq \theta \leq \theta_0} \{ \tilde F_1 (\theta, \psi) \}, $$ 其中 $\tilde F_1(\theta, \psi) = f(-\cos\theta) + f(-\cos(\psi - \theta))$.

在式 $\tilde F_1$ 當中, $\theta$ 代表 $\theta_1$, 而 $\psi$ 代表 $\phi_{1,2}$, 因為我們要求線段跨越 $e_0$, 唯一決定 $\theta_2$, 因此 $F_1(\psi)$ 可以理解成 $y_1 y_2$ 長度為 $\psi$ 的前提下, $f(-\cos\theta_1) + f(-\cos\theta_2)$ 的上界, 並且由於 $f$ 為遞減函數, 所以 $F_1(\psi)$ 也是一個遞減函數。

令 $\psi=\pi/3$, 我們可以得到 $$ h_2 = f(1) + F_1(\pi/3) \approx 12.8749 \lt 13. $$

3.4.3. $ \vert Y \vert=4$ : 包含 $e_0$ 的菱形 $\Diamond = y_1 y_2 y_3 y_4$

因為 $m=4$ 的推理過程中會再次使用 $F_1$ 這個函數, 為了連貫性我們先跳過 $m=3$ 的情形。

對於菱形的兩個對角線 $y_1 y_3$ 與 $y_2 y_4$, 我們令二對角線的交點為 $\bar{y}$, 對球上三角形 $y_1 y_2 \bar{y}$ 套用球面餘弦定理 : $$ \begin{aligned} \frac{1}{2} &= \cos\phi_{1,2} \\ &= \cos\frac{d_1}{2}\cos\frac{d_2}{2} + \sin\frac{d_1}{2}\sin\frac{d_2}{2}\cos{\frac{\pi}{2}} \\ &= \cos\frac{d_1}{2}\cos\frac{d_2}{2}. \end{aligned} $$

並且定義一週期函數 $$ \rho(s) = 2\arccos\left( \frac{1}{2 \cos (s/2) } \right), $$

使其滿足以下特性 :

1. $\rho$ 在開區間 $(0, \pi)$ 遞減,
2. $\rho(d_1) = d_2$,
3. $\rho(d_2) = d_1$,
4. $\rho(\pi/2) = \pi/2$, 且
5. $\rho(\rho(s)) = s$ 對於 $s\in(0, \pi)$.

不失一般性地假設 $d_1\leq d_2$, 由於 $d_2\leq 2\theta_0$ (球蓋直徑) 以及 $\rho$ 的函數特性, 我們會得到 $$ \rho(2\theta_0) \leq \rho(d_2) = d_1 \leq \frac{\pi}{2} \leq d_2 \leq 2\theta_0. $$ 接著考慮兩種狀況, 當 $\rho(2\theta_0) \leq d_1 \leq 77^\circ$ 時, 考慮兩對角線我們會取得以下二不等式 : $$ \begin{aligned} f(-\cos\theta_1) + f(-\cos\theta_3) &\leq F_1 (d_1) \leq F_1 (\rho (2\theta_0)), \\ f(-\cos\theta_2) + f(-\cos\theta_4) &\leq F_1 (d_2) = F_1 (\rho(d_1)) \leq F_1 (\rho(77^\circ)). \end{aligned} $$ 綜合得第一種狀況的上界 $$ \begin{aligned} H(Y) &= f(1) + \sum_{i=1}^4 f(-\cos(\theta_i)) \\ &\leq f(1) + F_1 (\rho(77^\circ)) + F_1(\rho(2\theta_0)) \approx 12.9171 \leq 13. \end{aligned} $$ 而當 $77^\circ \leq d_1 \leq 90^\circ$ 時, 引用相似的手法我們有 $$ \begin{aligned} f(-\cos\theta_1) + f(-\cos\theta_3) &\leq F_1 (d_1) \leq F_1 (77^\circ), \\ f(-\cos\theta_2) + f(-\cos\theta_4) &\leq F_1 (d_2) \leq F_1 (90^\circ). \end{aligned} $$ 相結合後得到第二種狀況的上界 $$ \begin{aligned} H(Y) &= f(1) + \sum_{i=1}^4 f(-\cos(\theta_i)) \\ &\leq f(1) + F_1 (77^\circ) + F_1(90^\circ) \approx 12.9182 \leq 13. \end{aligned} $$ 故 $h_4 \leq \max\{ 12.9172, 12.9182 \} \lt 13$.

3.4.4. $ \vert Y \vert=3$ : 包含 $e_0$ 邊長 $\pi/3$ 的正三角形 $\Delta = y_1 y_2 y_3$

首先不失一般性地宣稱 $\theta_1 \leq \theta_2 \leq \theta_3 \leq \theta_0$, 並定義 $R_0$ 為邊長 $\pi/3$ 正三角形 $\Delta$ 的外接圓半徑 (根據計算該值為 $\arccos\sqrt{2/3}$ ), 此時我們會有 $R_0 \leq \theta_3 \leq \theta_0$ 這個性質。

令 $y_c$ 為 $\Delta$ 的中心, 給定 $\gamma = \angle y_1 y_3 y_c = \angle y_2 y_3 y_c$, 根據計算該值為 $\arccos\sqrt{2/3}$, 正巧得到 $\gamma = R_0$, 並且令 $u = \angle e_0 y_3 y_c$, 分別從兩三角形 $y_1 y_3 e_0$ 與 $y_2 y_3 e_0$ 我們得到 $$ \begin{aligned} \cos\theta_1 &= \cos\frac{\pi}{3} \cos\theta_3 + \sin\frac{\pi}{3} \sin\theta_3 \cos (\gamma - u) \\ &= \cos\frac{\pi}{3} \cos\theta_3 + \sin\frac{\pi}{3} \sin\theta_3 \cos (R_0 - u), \\ \cos\theta_2 &= \cos\frac{\pi}{3} \cos\theta_3 + \sin\frac{\pi}{3} \sin\theta_3 \cos (\gamma + u) \\ &= \cos\frac{\pi}{3} \cos\theta_3 + \sin\frac{\pi}{3} \sin\theta_3 \cos (R_0 + u). \end{aligned} $$

從以上推論中, 我們會發現在距離的觀點下, $u$ 與 $\theta_3$ 可唯一決定三點距離。根據假設 $u$ 必須介於 $0$ 與 $u_0$ 之間, 並且

1. 當 $u=u_0:=\arccos((\cot \theta_3) / \sqrt{3}) - R_0$ 時, $\theta_2 = \theta_3$,
2. 當 $u=0$ 時, $\theta_1 = \theta_2$,
3. 而當 $0\lt u\lt u_0$ 時, $\theta_1 \lt \theta_2 \lt \theta_3$.

現給定在區間 $[R_0, \theta_0]$ 的函數 $$ F_2(\psi) = \max_{0\leq u \leq u_0} \tilde{F}_2 (u, \psi), $$ 其中 $$ \begin{aligned} \tilde{F}_2(u, \psi) &= f(1) + f(-\cos\theta_1) + f(-\cos\theta_2) \\ &= f(1) + f(-\cos\frac{\pi}{3}\cos\psi - \sin\frac{\pi}{3}\sin\psi\cos(R_0 - u)) \\ &\qquad + f(-\cos\frac{\pi}{3}\cos{\psi} - \sin\frac{\pi}{3}\sin\psi\cos(R_0 + u)). \end{aligned} $$ 留意到 $f$ 在區間 $[-1, -\theta_0]$ 為遞減函數, 且 $F_2$ 在區間 $[R_0, \theta_0]$ 是一個遞增函數, 一個簡易的觀點是當 $y_3$ 與 $e_0$ 距離越遠, 意味著另兩點 $y_2$ 和 $y_1$ 距離便隨之下降。現定義一區間 $[R_0, \theta_0]$ 的有限取樣 $$ \{\psi_1, \ldots, \psi_6 \} = \{R_0, 38^\circ, 41^\circ, 44^\circ, 48^\circ, \theta_0\}. $$ 對於 $\psi_i \leq \theta_3 \leq \psi_{i+1}$, 我們有 $$ H(Y) = \tilde F_2(u, \psi) + f(-\cos\theta_3) \lt w_i := F_2 (\psi_{i+1}) + f(-\cos\psi_i). $$ 並且透過計算, 我們得到 $$ \{w_1,\ldots,w_5\} \approx \{ 12.9425, 12.9648, 12.9508, 12.9606, 12.9519 \}, $$ 故 $h_3 \lt \max_i \{w_i\} \lt 13$. 總和所有結果, 得 $h_m = \max\{h_0, \ldots, h_4\} \lt 13$, 至此引理三證明完畢。

4. 驗證數值結果

若讀者有興趣於數值結果的來龍去脈, 可參考筆者在 GitHub 上的 Python 公開專案 ^{6 6} https://github.com/StephLin/kissing-number-problem-r3 並依照專案說明以計算在文章中所出現的所有上界。

h2:	12.874869834882462
h4:	12.917070958008141
	12.918143697010624
h3:	12.942527302266296
	12.964797422562022
	12.9508335817848
	12.960647320409375
	12.951894003307714

A. 線性規劃應用於係數 $c_k$ 數值方法

此套線性方法為 Musin 於四維吻球數文章中 提出, 同時也應用到三維情形。

首先目標是我們要尋找一組由係數 $c_k$ 決定的多項式 $$ f(t) = 1 + \sum_{k=1}^d c_k G_k (t) $$ 使得他在滿足基本條件 : (C1) $c_k\geq 0$ 對於 $1\leq k \leq d$; (C2) $f(a) \lt f(b)$ 對於 $-1\leq a \lt b\leq -t_0$; (C3) $f(t) \leq 0$ 對於 $-t_0 \leq t \leq z$ 下讓 $h_{\max} = \max_m{h_m}$ 越小越好。但是這會產生兩個問題 :

1. $m$ 的範圍需要給定;
2. 對於任意 $m$, 我們並不確定何種球蓋佈點 $Y$ 會使得 $H(Y) = h_m $。

因此 Musin 在這裡使用的方法是假設 $m$ 的範圍落在 $\{1, 2, 3, 4\}$, 並且針對 $m$ 的情況, 假設 $Y$ 的最佳排列形式以評估 $h_m$ : $$ H(Y) = f(1) + m f(-\cos\rho_m),\quad \cos\rho_m = \left\{ \begin{aligned} & \sqrt{(1 + (m-1)z ) / m} && \mathrm{ if}\; m \neq 4, \\ & \sqrt{z} && \mathrm{ if}\; m = 4. \end{aligned} \right. $$ 我們令一變數 $F_0$ 以描述上界 $H(Y) \leq F_0 + f(1)$, 此時便可得到第四條限制項 (C4) $f(-\cos\rho_m) \leq F_0 / m$ 對於 $m\in \{1, 2, 3, 4\}$, 同時獲得最小化問題之目標函數 : $$ E := F_0 + 1 + c_1 + \dots + c_d. $$

演算法

輸入 : $n=3$, $z=0.5$, $t_0\approx 0.5907$, $d=9$, $N$.
輸出 : $c_1, \ldots, c_d$, $F_0$, $E$.

首先將 (C2) 與 (C3) 離散化, 令 $a_j = -1 + \varepsilon j$, $\leq j \leq N$, $\varepsilon = (1 + z) / N$, 接著透過線性規劃方法以最小化能量函數 $$ E - 1 = F_0 + \sum_{k=1}^d c_k $$ 限制於 $$ c_k \geq 0,\quad 1 \leq k \leq d;\qquad \sum_{k=1}^d c_k G_k (a_j) \leq \sum_{k=1}^d c_k G_k (a_{j+1}), a_j\in [-1, -t_0]; $$ $$ 1 + \sum_{k=1}^d c_k G_k (a_j) \leq 0,\quad a_j\in [-t_0, z];\qquad 1 + \sum_{k=1}^d c_k G_k (-\cos\rho_m) \leq F_0 / m,\quad m\in I_n. $$ 經線性規劃得到之 $F_0$, $c_1, \ldots, c_d$ 即為解答。

B. 球形蓋上最佳佈點證明

在附錄一我們針對 $S(X)$, 考慮上界產生時在球型蓋上點的分布情形。 因為點與 $e_0$ 的距離和函數值呈遞減關係, 因此我們在尋找上界發生點佈置時, 應考慮盡可能將點朝向 $e_0$ 靠攏。

接著我們針對 $m=2, 3, 4$ 的狀況, 逐項討論其分布情形。

B.1. Case $m=2$

若 $e_0\not\in y_1 y_2$, 則弧 $y_1 y_2$ 可以整個往 $e_0$ 方向拖曳, 以縮短距離。而若 $y_1 y_2 \gt \dfrac \pi{3}$, 則其中一點 $y_1$ 或 $y_2$ 可以沿著弧線往 $e_0$ 拖曳, 以縮短距離。

故綜合來說, $e_0$ 會落於弧線 $y_1 y_2$ 上, 且 $y_1 y_2$ 長度為 $\dfrac \pi{3}$。

B.2. Case $m=3$

結論而言, $e_0 \in \Delta$, 否則整個三角形可以往 $e_0$ 方向拖曳, 以縮短距離; 另一方面我們固定任意 $i$, 若對於所有 $j\neq i$ 可使得 $\phi_{ij} \gt 60^{\circ}$, 則 $y_i$ 有辦法向 $e_0$ 拖曳, 等價於使 $\theta_1$ 下降, 這使得對於任意 $y_i$, 必定存在至少另一點 $y_j$ 滿足 $\phi_{ij} =\dfrac \pi{3} $。 不失一般性, 我們稱 $y_1 y_2 = y_1 y_3 = \dfrac \pi{3} $。

當 $y_2 y_3 \gt \dfrac \pi{3}$, $y_3$ 可以就 $y_1$ 為中心旋轉一小角度以靠近 $e_0$, 故 $y_2 y_3 = \dfrac \pi{3}$, $\Delta$ 為邊長 $\dfrac \pi{3}$ 的正三角形, 且 $e_0$ 會位於該三角形內部。

B.3. Case $m=4$

首先說明 $\Diamond = y_1 y_2 y_3 y_4$ 必須是凸多邊形 : 假設 $y_4\in y_1 y_2 y_3$, 此時垂直於弧 $e_0 y_4$ 的圓將 $S^2$ 分為兩個半球 : $H_1$ 和 $H_2 $。 假設 $e_0\in H_1$, 則至少一個 $y_i$ (例如圖中的 $y_3$ ) 落於 $H_2 $。

由於角度 $\angle e_0 y_4 y_3 \gt 90^{\circ}$, 這會使得 $\theta_3 \gt 60^{\circ} \gt \theta_0$, 此時矛盾產生, 故 $\Diamond := \mathrm{conv\ } Y $。

在 $m=3$ 的情形中, 我們解釋了對於任意 $y_i$, 必定存在至少另一點 $y_j$ 滿足 $\phi_{ij} = 60^{\circ}$, 這個現象在 $m=4$ 的時候依舊成立。 這時我們需要額外說明 : 對於任意 $y_i$, 必定存在至少兩點 $y_{j_1}$ 與 $y_{j_2}$ 滿足 $\phi_{i, j_1} = \phi_{i, j_2} = 60^{\circ} $。 要說明這件事情, 不失一般性地給定 $\phi_{1,2}=60$ 且對於 $i\gt 2$ 有 $\phi_{1i}\geq 60$, 我們分成兩個狀況討論。

• 第一種條件是假設 $e_0\not\in y_1 y_2$, 這時 $y_1$ 可就 $y_2$ 為中心旋轉一個小角度以靠近 $e_0$, 且不違背限制條件。
• 第二種條件是假設 $e_0\in y_1 y_2$, 此時若有 $i\gt 2$ 或 $j\gt 2$ 滿足$ \phi_{ij} =60^\circ$, 那麼弧本身必定不包含 $ e_0$, 因為若包含其中就代表 $y_1 y_2$ 和 $y_i y_j$ 為二對角線, 這會使得必定存在邊長是小於$ 60^\circ$, 進而違背限制條件。因此對於 $i\gt 2$, 必定存在至少兩點 $y_{j_1}$ 與$ y_{j_2}$ 滿足 $\phi_{i, j_1} = \phi_{i, j_2} = 60^{\circ} $。 列舉所有條件後, 只會有一種例外情況是 $\phi_{1,2}=\phi_{2,3}=\phi_{3,4} =\phi_{4,2}=\psi \lt \phi_{4,1}$, 但這會使得整個三角形 $y_2 y_3 y_4$ 可以就 $y_2$ 為中心往 $e_0$ 靠近, 且不違背限制條件。

綜合兩種條件, 得知對於任意 $y_i$, 必定存在至少兩點 $y_{j_1}$ 與 $y_{j_2}$ 滿足 $\phi_{i, j_1} = \phi_{i, j_2} = 60^\circ$。 透過這個條件且已知兩對角線長度不可同時為 $\dfrac \pi{3}$, 透過窮舉可知此四邊形 $\Diamond = y_1 y_2 y_3 y_4$ 應為邊長為 $\dfrac \pi{3}$ 的菱形, 且 $e_0$ 會位於該菱形內部。

致謝： 我們感謝成功大學江嘉恩同學仔細地閱讀草稿並給出珍貴建議。

參考文獻

---本文作者俞韋亘任教中央大學數學系, 林育愷與李家妤撰寫時分別為中央大學數學系大學部四年級與二年級學生---