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

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

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

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

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

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

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

四到七之間

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

Image Credit: MathsPoetry

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

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

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

 

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 和老化的著作,獲劍橋大學頒發博士學位。

Photo Credit: SHARE Conference,

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

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

證明概要

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

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

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

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

由 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 都不會有三點相同顏色。

有 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)。更小的等距圖除了更容易驗證外,也可能給其他研究這個問題的人啟發,進一步解決夏維格—尼爾遜問題。

Image Credit: Marijn Heule

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

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

相關文章︰

資料來源︰


洞見機會,創新未來──新創如何用雲端打出一手好牌:AWS Startup Day 7 月 15 日線上重磅回歸

AWS Startup Day 即將於 7 月 15 日重磅回歸,此次不只聚焦新創趨勢與數位應用,更聯合 AWS 創投新創媒合會,提供參與者豐富的資源,所有與新創生態系相關的夥伴都不容錯過。
評論
Photo Credit:AWS
評論

隨著 Web3.0 去中心化的趨勢開展與現在進行式的產業數位轉型浪潮,雲端技術早已成為許多早期新創發展產品或服務的關鍵金鑰,甚至為其奠定高速發展的穩健根基。而台灣雲端服務供應龍頭 AWS(亞馬遜網路服務公司)更自 Web2.0 時代開始就從未缺席,始終在技術新知、應用實務等方方面面致力支持新創,其中最具代表性的免費論壇活動──AWS Startup Day 也即將於今年 7 月 15 日重磅回歸,在線上和參與者相會!

今年度 AWS Startup Day 持續聚焦新創趨勢與數位應用,精心規劃八場新創專題演說,非常適合長期關注新創生態系統的相關人士,或是正要起步、成長的新創夥伴報名參加。

立即報名 2022 AWS Startup Day!

五大特色議程安排,給你滿滿新創觀點與技術乾貨

Photo Credit:AWS

「新創如何運用雲端科技打出一手好牌,投注資源延續未來業務?」這是今年 AWS Startup Day 欲探討的核心議題之一。為解答雲端科技之於新創企業的珍貴價值,AWS 以「國際市場」、「創投趨勢」、「多元創業」、「雲端技術」、「焦點產業」等五大特色精心規劃講座內容,完整收錄新創趨勢脈動、雲端技術實務、佈局策略觀點與創投媒合等新創事業歷程的重要節點。為此,AWS 不只力邀 Web3.0、電商、串流、B2B 解決方案等不同領域的新創合作夥伴,分享選擇 AWS 開展新創事業的策略考量,更毫不藏私地解析雲端技術如何快速又穩定的開拓事業。

Photo Credit:AWS

無論新創還是育成,想要洞見機會就不能錯過 AWS Startup Day

Photo Credit:AWS

任何產業或技術的發展,不單要前人的引領,也需要後繼者無窮盡的創新思維與打破框架的勇氣,缺乏其中一個環節,生態系都無法平衡永續。所以無論是天使創投、孵化器,還是剛起步或處於早期新創的企業,只要你身為新創生態系統中的一份子,渴望尋求創意突破或開展新興業務,AWS Startup Day 都是你絕對不能錯過的最佳活動。

填單取得 2022 AWS Startup Day 免費入場券!

尋找下一個新創獨角獸──同場加映 AWS 年度創投新創媒合會

本次 AWS Startup Day 除新創及創投相關講座外,AWS 更直接邀請多家國際及台灣知名創投公司,與 AWS Startup Day 同場舉辦今年度唯一的線上「新創創投媒合會」,欲透過串聯本地深具潛力的新創與創投,幫助台灣新創企業獲得更豐富的資源,孕育下一個獨角獸。

根據 AWS 釋出的消息,媒合會將以早期天使輪或 Pre-A 輪融資為主,重點關注 AI/ML工具和平台、智能零售、MarTech、Web3.0、媒體和娛樂等產業,並以快速輪流的形式替新創獲得最大的曝光。

立即報名 2022 AWS Startup Day,共構台灣新創生態系統!