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

業餘數學家為一道填色難題帶來突破
Image Credit: Marijn Heule
我們想讓你知道的是

圖論中一項跟填色有關的難題,自1950年提出以來沒有太大進展,數學家只知道答案在四到七之間,近來一位業餘數學家則把答案下限提升至五。

唸給你聽
powered by Cyberon

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

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

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

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

四到七之間

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

GolombGraphProperties
Image Credit: MathsPoetry, CC BY-SA 3.0
圖1

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

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

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

Hadwiger-Nelson_tessellation
Image Credit: David Eppstein, Public Domain
圖2

假設六角形的邊長為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
Photo Credit: SHARE Conference, CC BY 2.0
圖3︰迪桂

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

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

證明概要

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

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

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

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

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

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

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

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

於是他把圖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
Image Credit: Marijn Heule
圖7

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

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

相關文章︰

資料來源︰

或許你會想看
更多『新聞』文章 更多『科學』文章 更多『Kayue』文章
Loader