填顏色的數學︰超級電腦運算兩天，數學家得出100隻硬碟才能裝滿的證明
自 Kayue | The News Lens – 2016年6月2日星期四下午5:01
Facebook 馬上成為Yahoo 新聞的Fans
在派對上任意找6個人，當中要麼有3個人互相認識，要麼有3個人互不相識。不相信？且看以下圖解，來自關於數學家艾迪胥（Erdős Pál）的記錄片《N is a Number》︰
我們先把6個人分別以A、B、C、D、E及F點代表。兩點以藍線相連的話，就代表兩人相識；以紅線相連，則代表兩人不認識。
從A開始連線，由於餘下有5個人，必定有最少3個人互相認識（藍線），或最少3個人互不認識（紅線）。換言之，必然有最少3點跟A相連是同一顏色。在此假設A認識C、D及E。
讓我們先忽略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或以下的數字，問題所要求的情況還是可以做到的，例如以下是其中一組答案（白色代表可以是任意的顏色）︰
不過只要增加到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。這需要留待未來的數學家提出較簡單的證明、建立理論，像陶哲軒一樣為數學界提供洞見。
沒有留言:
張貼留言