懸宕50幾年的「赫德米猜想」,被一位年輕數學家用三頁論文擊碎

懸宕50幾年的「赫德米猜想」,被一位年輕數學家用三頁論文擊碎
Photo Credit: Shutterstock/達志影像

我們想讓你知道的是

懸宕50幾年的「赫德米猜想」是圖論領域主要猜想之一,許多學者對它的正確性深信不疑。然而去(2019)年中,俄國年輕數學家希多夫(僅30歲)提出一項令人跌破眼鏡的結果,證明赫德米猜想錯了。

文:陳宏賓(UniMath創辦人、中興大學應用數學系助理教授)

最近數學家在許多重要議題上面取得研究進展,其中一項是關於懸宕50幾年的「赫德米猜想」(Hedetniemi's conjecture),是圖論領域主要猜想之一,許多學者對它的正確性深信不疑。然而,去(2019)年中,俄國年輕數學家希多夫(僅30歲)提出一項令人跌破眼鏡的結果,證明赫德米猜想錯了。

「各位同學,翻開課本第56頁,今天老師要來教大家乘法。」如果你的小學數學老師沒有時常請假的話,你應該會在課堂上學到像這樣的題目:「小明一天的零用錢有20元,請問三天後小明有多少零用錢?」又或者,「民眾在七天可以買三片口罩,請問14天最多可以買到幾片口罩?」

乘法
圖片來源:陳宏賓

當然,顯而易見,如果小明沒有把錢拿去消費,民眾也找不到其他管道買口罩的情況下,答案就是20元x3=60元,以及3片x2=6片口罩。

乘法用數學式子運算直接就能處理,更直觀一點,一項物品的「倍數」觀念,基本上可以視為將該物品「複製貼上」那麼多次的總量。當然,物品是任何東西都能適用,即使是「圖」也不例外,這裡所謂的圖是指由點和邊(點與點的關係)所構成的一個抽象概念。

一個圖乘以普通數字就是將該圖複製那麼多次,如下:

乘法_1
圖片來源:陳宏賓

圖的乘法是什麼?

那麼問題來了,如果想要延伸乘法的概念到「圖乘以圖」又該如何定義。例如以下該等於什麼?

1
圖片來源:陳宏賓

延伸定義的一種方法是讓「前圖」乘以3倍(就是貼3次),然後這3塊相對應的地方都要呈現「後圖」的關聯狀態。這種常見的圖乘法是相對直觀的方式,稱為笛卡爾乘積(Cartesian product)。

G
圖片來源:陳宏賓

由於邊與邊相乘的結果形同一個方形,因此圖G和圖H的笛卡爾乘積,一般記為G□H。下圖是較複雜的例子:

GoH_1
圖片來源:陳宏賓

今天的重點是另一種定義方法,稱為張量積(tensor product)。它的運算方式形如交叉,因此記為GxH,如下圖中兩點{a,b}x兩點{c,d}會產生4個點(a,c)(a,d)(b,c)(b,d),每個點對應到原本圖G和圖H中各1個點形成的點對,兩點是否相連的準則仰賴其對應點是否在原圖中都相連。意即如果a和b相連,且c和d相連,則(a,c)和(b,d)相連。請看下例:

GxH_0
圖片來源:陳宏賓

下面這圖更複雜一點,不過簡言之,相連的條件就是「在原本兩圖中同時都相連」。

GxH_1

各位觀眾,我說了這麼多,你覺得乘法是不是很有趣呢?

赫德米猜想的考驗

接下來,我們要進入圖的傳統點著色問題。一個傳統的點著色要求將圖中的每一頂點著色,同時使得相連的點必須著不同顏色。最少需要多少種顏色才能夠達成目標?這個數量稱為圖的「點著色數」(chromatic number)。

笛卡爾乘積形成的圖,由於包含了原來兩圖的結構,很明顯,笛卡爾積圖的點著色數「至少需要」兩圖中點著色數較大的那個量。1957年Gert Sabidussi證明這個量也就足夠了,把「至少需要」換成「恰好」,完整的刻劃笛卡爾積運算的點著色性質。

另一方面,張量積形成的圖用其中任一個原圖的點著色數就足夠將整個圖塗好色:參考原圖的著色法,每一層依照都塗相同的顏色即可,由於「相連的條件就是在原本兩圖中同時都相連。」,因此參考原圖的著色法就避開了同色的困擾。當然,根據上面的推理我們知道應參考著色數較小的那個圖來做比較有利。

coloring_(1)
圖片來源:陳宏賓
張量積所形成的新圖著色完全參考左圖,是個合法的著色。當然,換成參考上圖也可以。

至此,一個很自然的問題是,能不能用更少顏色呢?

1966年史帝芬.赫德米(Stephen Hedetniemi)在博士論文中提出這項猜測,他認為不可能更少了,也就是說:

作張量積後的點著色數,和原圖的點著色數較小的那個相同。

這個後來被稱為赫德米猜想(Hedetniemi's conjecture)的難題,是圖論領域的主要猜測之一。過去數十年來,許多研究圖論的學者也都曾嘗試解決這個問題,對於它的正確性,多年來有人持正面、也有人持反面態度。隨著時間過去,有許多證據浮現,然而卻一直未能有人能真正解決這個問題。

由一個剛畢業的博士所提出來的猜想,可想而知剛開始時並不會受到太多關注。赫德米猜想之所以成為學界的熱門題目,是搭了知名數學家艾狄胥(Paul Erdős)和羅瓦胥(László Lovász)的便車,兩位大師在合作的一篇論文中指出,赫德米猜想如果正確的話,能夠用來破解他們論文中的另一道難題,一項關於拉姆西著色數(chromatic Ramsey number)的猜測。因為這個緣故,赫德米猜想一夕成為學者競相追逐的聖盃。

後來,艾狄胥-羅瓦胥的猜測,被曾在台灣的中山大學、現在在浙江師範大學工作的朱緒鼎教授解決了。他在2001年提出一個當時看來相當大膽的問題:

赫德米猜想在分數著色數的形式對不對呢?

約莫10年後,他回答了自己提的疑問,證明赫德米猜想的分數著色數(fractional chromatic number)版本是正確的,而他這項結果就足以證明艾狄胥-羅瓦胥猜測。分數著色是一種比傳統著色更細緻的形式,在此暫不贅述,要讀者知道的是即使在分數著色版本取得進展,原本的赫德米猜想仍是未知。不過,這卻提供了更進一步證據,讓人們有更多理由相信赫德米猜想是正確的。

希多夫的三頁論文

然而,一個反例就足以毀滅千千萬萬個美好假象。去(2019)年夏天,30歲的俄國年輕數學家亞羅斯拉夫.希多夫(Yaroslav Shitov )提出一個反例,狠狠地擊碎了赫德米猜想,震驚全世界圖論學家。朱緒鼎老師在演講時這麼形容他內心的震撼:

我的博士論文主要研究題目之一就是赫德米猜想,數十年來一直深信它是正確的,沒想到竟然這麼美麗的猜想會錯了。

希多夫的論文出乎意料的「短」,包含首頁摘要和末頁參考文獻僅僅只用了三頁!簡短但卻非常難以理解,我當時斷斷續續花了兩個禮拜才搞懂。你可能會認為,把反例的圖給出來,驗證一下不符合猜想的結論就搞定了,兩頁證明差不多是這樣吧。我下載論文當時跟你想的一樣,不過事實並非如此。

比全宇宙原子數量還要大的反例圖的一根毛


猜你喜歡


【一圖看懂】民生基礎建設的資安防禦為何重中之重?ACW SOUTH沙崙基地打造天然氣、石化、變電所三大測試場域為大眾保駕護航

【一圖看懂】民生基礎建設的資安防禦為何重中之重?ACW SOUTH沙崙基地打造天然氣、石化、變電所三大測試場域為大眾保駕護航
Photo Credit:TNL Brand Studio

我們想讓你知道的是

這幾年的新冠疫情、俄烏戰事奪走許多寶貴生命,讓網路流行一句「你的歲月靜好,是有人為你負重前行。」當我們能夠安居樂業過著恬靜生活,其實是仰賴一群人在社會各個角落堅守崗位,多數人才能享受無虞的生活及安全的家園。

【工業局】沙崙資安_1
Photo Credit:TNL Brand Studio

我們在食衣住行許多方面皆與水、電、天然氣等資源息息相關,在高度數位化的現代,臺灣在面對這些資源的基礎建設時,網路安全的防禦為何比其他國家更需謹慎面對?這件事可以從俄烏戰爭獲得啟發。

從俄烏戰爭居安思危,臺灣每月面臨4000萬次的網路攻擊

有人說如果有一天真的發生第三次世界大戰,那一定會發生在網路上。從近期的俄烏戰爭來看,除了使用傳統槍砲坦克,更值得注意的是雙方都派出大量IT駭客,攻擊對方的油水電重要基礎建設的伺服器、通訊設施,企圖阻斷即時資訊,藉此癱瘓敵方的民生設備運作。

事實上,一般駭客不會主動攻擊一個國家的基礎建設,大多是鎖定企業等級為目標,像是美國燃油管線營運公司,受到來自東歐的勒索病毒攻擊,被迫暫停營運同時還要支付新台幣1億4,000萬元的贖金,造成當地民眾恐慌,發生一波搶購燃油熱潮。

而臺灣因為政治戰略的因素,外部駭客總是虎視眈眈,想要癱瘓我國的民生關鍵基礎設施。過去幾年間臺灣每月平均受到2,000萬到4,000萬次外來攻擊,甚至懷疑一起大型惡意軟體攻擊,幕後的駭客是有國家力量在撐腰。

臺灣民生建設資安防禦迫在眉睫,ACW SOUTH沙崙基地扮演關鍵角色

身為島國的臺灣,電力、石油、天然氣及水利等資源設備,是供應國內經濟發展及民生需求的重要資產。面對各項能源設備資安的防護,我國經濟部長王美花過去就曾公開表示,「油電水等關鍵設施假使被破壞,後果不堪設想,所以資安是重要基本功,一定要發展做好防護措施。

身為國內首屈一指的「ACW SOUTH沙崙資安服務基地」(以下簡稱 ACW SOUTH資安基地),承接起重責大任,提供資安實驗場域,模擬攻防演訓及產品驗測服務;也會邀請資安服務廠商與工控營運業者到沙崙場域,進行實作的技術交流。

ACW SOUTH資安基地計畫團隊表示,「透過資安服務商與工控營運業者的交流分享,有助促進產業對於工控資安了解與場域運用;同時我們也會辦理工控資安等相關課程、研討會及交流會,鏈結資安與工控業者幫助雙方有更深入的技術合作。」

目前ACW SOUTH資安基地的「關鍵基礎設施工控場域」主要有「石化/化工、天然氣及變電所」三套系統,模擬五套攻擊劇本,協助相關基礎設備的管理者,在受到攻擊當下知道該如何反應,及早因應強化資安防禦實力。萬一遭遇偽造工作站監看數據、偽造命令操控電磁閥和空壓機、電驛傳輸通訊中斷等攻擊事件,就能立刻啟動應變流程。

走訪ACW SOUTH資安基地關鍵基礎設施,了解三大測試場域功能有多強

場域一、石化基礎設施
2020年臺灣兩大石化公司接連傳出資安攻擊事件,部分資訊系統感染勒索軟體病毒,造成加油站的支付系統停擺,導致消費者付款機制受到影響。

ACW SOUTH資安基地提供的化工模擬製程實體運作機櫃,是全台首座「石化/化工製程水位控制平台」,模擬情境為一般化工反應槽連續式循環水流水位控制,以水為循環流體模擬,可提供研究測試與訓練使用、自主開發攻防情境。來現場測試的業者,可透過視覺式監控介面與DCS收集現場監測儀表的即時資訊,做到收集完整數據紀錄及警報,具體測試資安防護設備與解決方案。

場域二、天然氣基礎設施
美國一家天然氣壓縮公司曾經受到勒索軟體攻擊,駭客透過魚叉式網釣攻擊入侵IT網路,再找機會滲透到OT網路,並在這兩個網路部署勒索軟體,導致人機介面、伺服器完全失能,公司業務被迫停擺兩天。

ACW SOUTH資安基地的儲槽氣體壓力監控系統,模擬情境為天然氣廠氣體儲槽壓力,使用空壓機模擬天然氣體,當氣體壓力高於或低於警報值時,系統畫面警示工作站主機,並同時記錄數據變化、警報和事件。

場域三、變電所基礎設施
2021年台電董事長說台電遭駭客攻擊幾乎每天發生;俄烏戰爭過程,俄羅斯駭客也曾嘗試對烏克蘭發電廠下手,利用資料破壞軟體發動攻擊,藉此癱瘓高壓變電所,讓烏克蘭當地無電可用。

電力系統無論在發電、輸電及配電的任一部分發生故障,都有可能影響整個供電系統異常,因此保護電驛的作用就在及早隔離故障,避免影響到後續的相關設備。ACW SOUTH資安基地的保護電驛監控系統採用IEC61850標準來進行網路通訊,可用來監視、記錄電驛突發事件,藉此模擬變電所遭受攻擊的危機處理。

要讓臺灣關鍵基礎設施免於駭客襲擊,可說是天方夜譚,但我們能做的是提升資安、強化防禦韌性,更有餘裕時間來防禦或補救攻擊。ACW SOUTH資安基地的關鍵基礎設施,目前打造了三大測試場域,擁有可實際演練的攻防腳本,並進行資安產品的驗測。

ACW SOUTH資安基地深知臺灣以製造業起家,尤其近年半導體領域成為舉世聞名的護國神山;另外因應全球淨零碳排議題,綠能也是前景可期的重要產業。因此在ACW SOUTH資安基地除了有關鍵基礎設施,還設計智慧製造、智慧綠能、半導體及物聯網等主題,可為相關業者做攻防演訓及產品驗測,有助提升我國整體資安防禦力。

「經濟部工業局 廣告」


猜你喜歡