填顏色的數學︰超級電腦運算兩天 數學家得出100隻硬碟才能裝滿的證明

填顏色的數學︰超級電腦運算兩天 數學家得出100隻硬碟才能裝滿的證明
Photo Credit: Håkan Dahlström, CC BY 2.0
我們想讓你知道的是

三位數學家最近發表一個證明,需要超級電腦運算來驗證,整個運算的數據多達200TB,破了以往紀錄。

唸給你聽
powered by Cyberon

在派對上任意找6個人,當中要麼有3個人互相認識,要麼有3個人互不相識。不相信?且看以下圖解,來自關於數學家艾迪胥(Erdős Pál)的記錄片《N is a Number》︰

Ramsey 1
《N is a Number》截圖

我們先把6個人分別以A、B、C、D、E及F點代表。兩點以藍線相連的話,就代表兩人相識;以紅線相連,則代表兩人不認識。

Ramsey 2
《N is a Number》截圖 

從A開始連線,由於餘下有5個人,必定有最少3個人互相認識(藍線),或最少3個人互不認識(紅線)。換言之,必然有最少3點跟A相連是同一顏色。在此假設A認識C、D及E。

Ramsey 3
《N is a Number》截圖 

讓我們先忽略B及F,只考慮C、D及E。只要當中有兩人互相認識,便會跟A組成一個藍色三角形。而如果他們都互不認識,就組成一個紅色三角形。

因此在任何情況下,都會出現一個淨色三角形。變回原本的用語,那就代表6個人之中,必然找到3個互相認識或互不認識的人。

藍斯理論

這條「朋友或陌生人定理」,是藍斯理論(Ramsey Theory)的一個應用。這套理論以早逝的邏輯學家、哲學家及經濟學家藍斯(Frank Ramsey)命名,源於他為解決一個數理邏輯問題而證明的定理。

此定理在組合數學中發常重要,其後藍斯理論獨立發展成數學的一個重要分支,主力研究以下這類問題︰到底有多少個元素,才能保證某類結構——例如包含一個淨色三角形——必然出現?

另外,藍斯理論亦在無限組合數學、集合論中發展,演變成無限藍斯理論。

100美元的問題

數學家格拉咸(Ronald Graham)是藍斯理論的專家,他曾經懸紅100美元解決以下問題︰

能否把每個自然數(0及所有正整數)填上紅色或藍色,使得任何畢氏三數組 (a, b, c)——即滿足方程 a2+b2=c2 的自然數組——都必然包含兩種顏色?

具體一點說,假設我們有無限條長度分別為1厘米、2厘米、3厘米…的木條(對於任何自然數n,剛好有一條n厘米的木條)。我們能否把它們都髹上紅色或藍色,令人無法拼出一個純紅色或純藍色的直角三角形?

今年5月初,三名數學家透過超級電腦輔助,證明了這並不可能。換言之,無論你如何為那些木條分配顏色,總會存在一個淨色的直角三角形。

超級電腦也需要計算兩天

三人證明了,假如限制在7824或以下的數字,問題所要求的情況還是可以做到的,例如以下是其中一組答案(白色代表可以是任意的顏色)︰

ptn7824
Image Credit: Marijn Heule

不過只要增加到7825,就總會有同一顏色的數字a、b及c滿足方程a2+b2=c2

乍聽下去,驗證似乎很簡單,把所有組合都試一遍就是了。不過,要把7825個數字分成紅、藍兩組,總共有超過102355個可能性,這個數字之大使人無法用電腦逐個試驗。因此他們利用演算法,讓電腦能夠在合理時間內完成運算,也降低運算成本。

即使把問題簡化後,仍需要大量運算。三人使用德州大學奧斯汀分校的超級電腦Stampede,以當中800個核心去計算,最終花去兩天時間才解決問題並驗證答案。

為甚麼是7825?

由於整個證明所包含的數據多達200TB(等如20萬GB),假設每個硬碟有2TB容量,仍需要100個硬碟。作者表示,即使檔案壓縮了也有14TB,難以把「完整證明」放上網絡。最終他們只把運算所需的檔案壓縮後公開,「僅有」68GB,讓學界可以自行下載及驗證。

200TB的數據令這個證明成為數學史上最長的證明,大幅破了此前的紀錄。原本的紀錄保持者是來自利物浦大學的Alexei Lisitsa及Boris Konev,在2014年,兩人以電腦輔助證明了艾迪胥一個猜想的特例,當中使用了13GB的數據。

雖然數學家無法直接檢視13GB的證明,只能以電腦獨立再運算來確認其可靠,但去年數學家陶哲軒也提出一個28頁長的證明,完整地解決了艾迪胥的問題。

論文其中一名作者Oliver Kullmann承認,雖然電腦協助他們解決了今次的問題,但只未有告訴他們為何不可能如此分配顏色,以及為何是7825。這需要留待未來的數學家提出較簡單的證明、建立理論,像陶哲軒一樣為數學界提供洞見。

相關文章︰

資料來源︰