業餘數學家為一道填色難題帶來突破!

評論
評論

本篇來自 關鍵評論網 ,INSIDE 經授權轉載。

1950 年秋天,當時仍在芝加哥大學就讀的數學家尼爾遜(Edward Nelson)對於「四色問題」感到興趣。這個問題是︰

對於任何地圖,假如希望把所有區域填上顏色,而且分享邊界的區域不能使用同一顏色,那麼最少要用多少種顏色?這個問題當時尚未解決,數學家知道三種顏色並不足夠,而五種顏色則夠用,因此問題是,只用四種顏色是否足夠?(故稱為四色問題。)

答案是︰足夠。這個問題要到 1976 年才獲得解決,而且需要依靠電腦計算證明,1950 年時僅得 18 歲的尼爾遜自然未有找到答案。不過他在研究四色問題期間,想到一個相關問題︰

在平面上任意選取無限多點,而且把距離為 1cm(單位其實不重要,重點是距離相等)的點連起來。如果要為這些點填上顏色,而且相連的點不可使用相同顏色(下文不再複述這項要求),那麼最少要用多少種顏色?這個數字稱為「平面色數」(chromatic number of the plane, CNP)。

四到七之間

數學家加林(Solomon W. Golomb)發現的以下這圖顯示,答案最少要四種顏色︰

GolombGraphProperties
GolombGraphProperties

Image Credit: MathsPoetry

尼爾遜把這個問題稱為「第二個四色問題」,問題涉及的圖稱為「等距圖」(unit distance graph),圖中每條直線——在圖論中稱為邊——的長度相等,故圖中由同一條邊連接的相鄰節點距離相等,而且邊數可以無限多。

這個問題現在被稱為夏維格—尼爾遜問題(Hadwiger-Nelson problem),因為數學家夏維格(Hugo Hadwiger)在 1945 年解決另一個問題時,提出了有助證明「CNP=7」的想法(見下段,但他要到 1961 年才提出證明),以及有段時間不少人誤以為他率先提出這個問題。

比夏維格早提出證明的是數學家伊斯堡(John Isbell),後者是尼爾遜最早一批提及其問題的人。當時尼爾遜已經知道答案下限是四,伊斯堡問他︰「那麼上限是多少?」尼爾遜說他不知道,伊斯堡便找出答案。他跟夏維格一樣,使用以下填上七種顏色的密鋪平面圖案(先忽略黑線圖案)︰

 
Hadwiger-Nelson_tessellation
Hadwiger-Nelson_tessellation

Image Credit: David Eppstein, Public Domain

假設六角形的邊長為 1cm,那麼在一個六角形內兩點最遠距離為 2cm,連接另一個同色六角形的話,最短距離——圖中 a、b 兩點之距離——則為√7cm,即約 2.65cm。因此我們只需把這些六角形縮小 2.1 倍,便能確保任何相隔 1cm 的兩點,都不會在同一顏色的六角形上——在任何一個六角形中放一條 1cm 的直線,線的另一端必然在另一種顏色的六角形內。

因此在 1950 年的時候,尼爾遜和伊斯堡已經知道平面色數介乎四到七之間。

在數學專欄作家葛登能(Martin Gardner)、多產數學家艾狄胥(Erdős Pál)等人的介紹下,數學界得悉這個問題,然而多年來沒有取得太大進展,數學家仍然只知道「4≤CNP≤7」這條不等式。

研究如何令人長壽的業餘數學家

直到今個月(2018 年 4 月)初,網絡論文預印本存庫 arXiv 出現了一篇文章,題目是 〈平面色數最少是五〉。這篇由迪桂(Aubrey de Grey)所寫的論文,描述了如何構造一個多達 1581 個頂點的等距圖,並解釋如何以電腦檢查無法用四種顏色填上所有頂點,從而證明平面色數最少是五,也就是說,現在只餘下三個可能答案︰五、六或七。

一個久無進展的難題取得突破,在數學界並不罕見,今次較為難得的是,迪桂是個業餘數學家。他在劍橋大學電腦科學系畢業,並因其妻子、專研果蠅的遺傳學家卡本特(Adelaide Carpenter)而對生物學和程式產生興趣,透過妻子教授和閱讀自學生物學。在 2000 年他更因為一本關於線粒體 DNA 和老化的著作,獲劍橋大學頒發博士學位。

6838320854_7ecb9bc4e3_o
6838320854_7ecb9bc4e3_o

Photo Credit: SHARE Conference,

迪桂現於他有份創辦的 SENS 研究基金會擔任首席科學家,致力研究以技術逆傳老化帶來的負面影響。他曾於接受《BBC》訪問時表示,醫學技術發展可以令人壽命大幅延長,人類甚至可能活至 1000 歲。

許多年前,迪桂曾迷上玩黑白棋,並因此認識了一些同樣喜愛這個遊戲的數學家。他們向迪桂介紹了圖論,此後他不時會研究這門學科。他說︰「當我需要從工作中休息時,我偶爾會想數學。」去年聖誕,他剛好有時間想這個數學問題。

證明概要

整個證明的起點,是一個由正六邊形及中心共七點構成的等距圖,迪桂稱為圖 H。他指出,要把下圖 H 填上最多四種顏色,如果不考慮旋轉、鏡射或交換顏色的話,其實只有以下四種方式︰

Graph_H
Graph_H

圖 H 的四種填色方式。Image Credit: Aubrey de Grey 2018

留意上面兩種方式中,均有三點相同顏色,下面兩種則沒有。

接下來迪桂構造了一個包含 52 份圖 H 的等距圖,稱為圖 L,他證明如果要把圖 L 填上四種顏色的話,最少有一個圖 H 包含相同顏色的三點。

Graph_L
Graph_L

由 52 個圖 H 所構成的圖 L Image Credit: Aubrey de Grey 2018

圖 2 中黑線畫出來的圖,由數學家李奧·摩沙(Leo Moser)和威廉·摩沙(William Moser)兩兄弟於 1961 年發現,這個在正五邊形內畫上四個等邊三角形的圖,同樣需要最少四種顏色,換言之其色數為四。

迪桂以摩沙兄弟的發現為基礎,構造出一個有 301 個頂點的圖 W,再把圖 W 複製七份,每份的中心點分別放在圖 H 的各點上,構造出一個含 1345 個頂點的圖 M。利用 MacBook Air 及 Mathematica 11,他只需要幾分鐘便檢查完各種為圖 M 填上四種顏色的方法,發現其中心的圖 H 都不會有三點相同顏色。

Graph_W_and_M
Graph_W_and_M

有 301 個頂點的圖 W(左)和有 1345 個頂點的圖 M(右)Image Credit: Aubrey de Grey 2018

於是他把圖 M 複製 52 份,各份中間的圖 H 均對應圖 L 中的圖 H(圖 L 中有 52 份圖 H),得出一個非常龐大的圖 N——總共有 20,425 個頂點!

由於超過 2 萬個頂點實在太多,迪桂其後把 N 簡化,最終構造出「只」有 1581 個頂點的等距圖 G,同樣需要最少五種顏色才可填滿所有頂點(而連接同一條邊的兩個頂點不會有相同顏色)。

接力挑戰難題

雖然迪桂的論文僅是放到網上的預印本,尚未通過期刊的同行審查,但他已把數據公開,其他數學家可以驗證。數學家米臣(Dustin G. Mixon)在網誌上表示,他跟另一數學家已獨立驗證其結果,並把頂點數目減至 1577 點。

現時夏維格—尼爾遜問題已成為「博學者計劃」(Polymath Project)的第 16 號計劃。這項計劃始於 2009 年 1 月,由劍橋大學數學家高華斯(Timothy Gowers)提出,希望透過數學家在網絡討論,令尚未解決的難題取得進展。博學者計劃的網頁表示,第 16 號計劃有三項明確目標︰

  • 找到更小及色數為 5 的等距圖;
  • 減少依賴電腦協助證明;
  • 用類似的圖研究相關問題,例如尋找色數為 6 的等距圖。

德州大學奧斯汀分校的電腦科學家浩勞(Marijn Heule)已找到頂點數目為 826 個、必須用五種顏色才能填滿的等距圖(見圖 7)。更小的等距圖除了更容易驗證外,也可能給其他研究這個問題的人啟發,進一步解決夏維格—尼爾遜問題。

826_3000px
826_3000px

Image Credit: Marijn Heule

數學家格拉咸(Ronald Graham)曾提出,會給最先找到平面色數的人 1000 美元獎金,而他似乎相信平面色數在五到六之間,因為他亦表示給最先證明平面色數大於五的人 100 美元獎金——這筆獎金相信屬於迪桂;最先證明平面色數小於六者更可獲得 250 美元。

雖然把平面色數的上限降低,看來要比提升其下限困難,不過迪桂的突破相信會令夏維格—尼爾遜問題更受關注,也許問題在不久將來會被解決。

相關文章︰

資料來源︰


精選熱門好工作

營運工讀生 (Part-time Intern)

Wanted
臺北市.台灣

獎勵 NT$4,000

行銷企劃主管

安力國際開發股份有限公司
臺北市.台灣

獎勵 NT$20,000

資深UI / UX 設計師(中壢)

雷麒科技有限公司
桃園市.台灣

獎勵 NT$20,000

評論