53年歷史的猜想被否定，數學家找到赫德涅米猜想反例

2020-09-24 大老李聊數學

大家好，我是大老李，這期節目讓我們在質數話題中插播一則新聞，它有關數學家在圖論領域裡的一個發現。在今年9月，俄羅斯數學家雅羅索夫·什託夫（Yaroslav Shitov ）發表了一篇僅三頁的論文，論文中，其發現了一個有53年歷史的圖論領域中的猜想的反例，從而推翻推翻了這一猜想，這個猜想名為：史蒂芬·赫德涅米猜想（Stephen Hedetniemi conjecture）。

要理解這個猜想，需要了解兩個概念，圖的「最小著色數」和圖的「張量積」(Tensor Product)。這兩個名詞聽上去很高大上，其實說清楚不難。

數學裡的「圖」就是一些點和一些連接點的線。這裡點的位置，線的形狀長度等等完全不考慮，只考慮點和線的連接關係。而兩個點之間的連線稱為「邊」，兩個點之間有一條邊相連稱為「相鄰」。

（圖論中的一張「圖」：僅考慮點和連線關係）

圖的著色問題，了解「四色定理」的聽眾應該也很熟悉了，就是對一幅圖中的點進行著色，要求相鄰的兩個的兩個點的顏色不同。「四色定理」是說對平面圖，至多四種顏色著色就夠了。「平面圖」就是那種可以「攤平」，使得所有邊可以不交叉的圖，那種圖，最多用四種顏色就可以著色，使相鄰兩點的顏色都不同，這就是「四色定理」。當然，對非平面圖，你需要的顏色更多。

(「平面圖」是那種沒有邊相交的圖。上圖中的左圖是平面圖，因其可以轉化為右圖，使得沒有邊相交)

「圖的最小著色數」的意思就是，對一幅圖最少需要幾種顏色著色，可以使任何相鄰兩點的顏色不同，這個顏色種類數量，就是圖的「最小著色數」。

再講一下圖的張量積，其實也不難理解，就是定義了一種兩幅圖的「乘法」，圖與圖乘起來得到另一張圖。這種乘法的定義我們藉助一道「應用題」來理解：

假設大老李要搞一次相親會，大老李認識一些單身男性朋友。大老李的太太也認識一些單身女性朋友，所以大老李想把他們集中在一起，搞一次相親會。

在相親會中，大老李設計了一個遊戲環節，是4人一組，兩男兩女參加。但是我知道我認識的那些男性朋友有些是互相認識的，我太太認識的女性朋友，有些也是互相認識的。遊戲時，我希望參加的兩位男士是互相認識的，兩位女士也互相認識，這樣玩遊戲氣氛更輕鬆熱烈點。

到底我邀請的那些參加相親會的朋友能否滿足這樣的分組條件呢？當然，這裡假設參會的男女人數相等，而且都是偶數。

那這道題我可以這樣解決，我先把參會的男性用一個點表示，兩人如果相識則連一條線。這樣得到一張男性朋友關係圖。同樣方法可以畫出女性朋友關係圖。

然後，我要參考這對兩張圖進行一個操作，得到一張新的圖。操作方法如下：將所有男性朋友女性朋友可能兩兩組合，組成一對，在新的圖中作為一個點表示，每個人可以重複組合出現。

比如，如果原來有a個男性和a個女性，那麼根據簡單的組合算法，新的圖就會有a^2個點，每個點代表一對可能的組合。

然後，我要給這些點之間連線，連線規則是：取兩個點，分別考察每個點所代表的組合對中的男性和女性。如果這兩個男性和女性在原先的圖中之間有連線，則把這兩個點連一條線，否則不連線。舉個例子就明白。

比如，如果我邀請參加相親會的男性是哈利波特，羅恩，馬爾福；女性方面是：赫敏，金妮，張秋。


(大老李邀請的男女朋友關係示意圖)

那如果有一個點是表示的是哈利波特，金妮；另一個點表示的羅恩和赫敏，那麼你需要把它們之間連條線，因為哈利波特和羅恩，以及赫敏與金妮算是好朋友。如果有一個點是表示的是哈利波特和張秋；另一個點表示馬爾福和金妮，那麼就不連線，因為哈利波特與馬爾福肯定不是好朋友，張秋與金妮也沒啥交集。總之，新的圖中點要連線的話，要求就是在老的圖中，對應點也有連線。

另外說明一點，自己與自己不需要連線，比如「哈利波特-赫敏」與「哈利波特-金妮」之間就不用連線了。

(根據前面的關係圖求得的張量積圖，它斷開成了兩部分)

以上我們就定義了一種從兩張圖進行一種組合，得到新的一張圖的運算，數學裡稱這種運算叫「張量積」，聽我這麼一解釋是不是也很簡單。其實叫它「積」是有點道理的，至少你能看到新的圖的點數是老的兩張圖的點數之積。

而對我來說，如果我能根據邀請來的男性和女性朋友關係圖，求得一張張量積的圖，那我知道，在這張張量積的圖中，任意一條線段兩端所代表的兩男兩女是適合才加這個相親遊戲的。當然，這個方法也許很笨，但至少說明了什麼是圖的張量積，後面我有時會簡稱為兩張圖的「積」。

另外，在數學中的張量積並不要求參與運算的兩張圖的點數相等。你也可以去分析張量積的一些性質，比如有沒有交換律，結合律等等。但這都不重要，今天我們要考慮的是兩張圖的最小著色數與運算後所得的圖的最小著色數的關係。

很早以前，數學家就證明了，兩張圖的積的最小著色數小於等於原先兩張圖的最小著色數的較小者。比如，如果原先兩張圖的最小著色數是4和5，則它們的積的最小著色數小於等於4。而很多人做了嘗試，發現「小於」這種情況做不到 ，實驗結果都是「等於」這種情況。

於是，1966年，當時還在讀博士的史蒂芬·赫德涅米，現為克萊姆森大學（位於美國卡羅萊納州）教授，在其博士學位論文裡作出了一個猜想：圖的張量積的最小著色數等於原先兩張圖的最小著色數的最小者，後來被成為：史蒂芬·赫德涅米猜想。

（史蒂芬·赫德涅米猜想）

此後50多年裡，數學家沒能找出任何反例，倒是證明了一些比原猜想稍弱的命題，比如有人證明了，如果原先兩張圖中的其中一個的最小著色數小於等於4，則赫德涅米猜想是正確的。

但是這次，什託夫卻找到了一個赫德涅米猜想的一個反例，即兩個圖的張量積的最小著色數比原先兩個圖都小。他的基本思路是利用了之前有關「冪圖」的一個結論，冪是冪次的冪。就像之前介紹求張量積的運算，如果一個圖G與自身求張量積，那麼結果可以寫成，類似可以有,等等。

但這類說的「冪圖」裡的運算，是另一種冪次。它的特點是底數和指數都是一個圖。比如有圖G,H，那麼和都是一張圖，都叫「冪圖」(Exponential Graph)。冪圖的定義略有點囉嗦，就不在音頻裡講了。但是叫它冪圖的肯定是有原因的。比如，如果圖G有a個頂點，圖H有b個頂點，那麼這張圖的頂點數就是。

Exponential Graph / 冪圖 定義：

Given a definition below (source: On Hedetniemi&/media/File:Graph-tensor-product.svg

相關焦點

  • 數論中著名的猜想
    數論中的這些猜想，不像其他數學分支那樣需要很多的背景知識，它們看上去是那麼的淺顯，乃至初中生甚至高年級的小學生也能讀懂命題，但是千萬不要被它「憨厚的外表」所蒙蔽了，要解決這些數學問題，非得有深厚的數學功底才能揭開其神秘面紗。接下來就講述一些歷史上的數論猜想。
  • 日本數學家稱證明ABC猜想 論文幾乎無人能懂
    丟番圖分析的困難性是頗為出名的，著名德國數學家希爾伯特曾樂觀地希望能找到其「一攬子」解決方案，可惜這個希望後來落了空，被證明是不可能實現的。與數學家們的努力平行，自2006年起，由荷蘭萊頓大學數學系牽頭，一些數學和計算機愛好者建立了一個名為ABC@Home的分布式計算系統，用以尋找ABC猜想所允許的那些反例。截至2012年9月，該系統已經找到了超過2300萬個反例，而且還在以每天幾萬個的速度穩定增加著。
  • 費馬:猜想還在繼續 - 遇見數學
    猜想的提出費馬是一位業餘數學家，在數學領域裡被譽為「業餘數學之王」，在他逝世後，人們在整理他的書稿時發現了這個猜想，因為他巨大的影響力，以「費馬大定理」之名公布，之後，從他的描述語境中，數學家們試圖重塑他的或是找到猜想的證明過程，不服氣的專業數學家們幾乎所有的都有研究過
  • 黎曼猜想:證明它,你將會不朽;否定它,後果很嚴重!
    另一個佐證來自兩位數學家阿達馬和瓦萊·普桑。1896年，他們各自獨立地證明了一個比黎曼猜想稍弱的推論——素數定理。果然，阿達馬活到了98歲，瓦萊·普桑活到了96歲。 出生于波蘭的數學家歐德裡茲科提出了另一個說法，那就是：誰若否定了黎曼猜想，誰就會going to die。歐德裡茲科甚至開玩笑說，其實黎曼猜想已經被否定了，只不過那個倒黴蛋沒來得及發表文章就已死去。
  • 困擾數學家90年的猜想,被計算機搜索30分鐘解決了
    曉查 發自 凹非寺量子位 報導 | 公眾號 QbitAI數學家會代碼，誰也擋不住！就連困擾人類90年的數學猜想也擋不住。來自斯坦福、CMU等高校的4名數學家，將一個數學難題轉化成了對10億個結果進行「暴力搜索」。
  • 困擾數學家90年的猜想，被計算機搜索30分鐘解決了
    但數學猜想不能僅靠直覺，必須有嚴格的證明。90年來，數學家一直不懈努力。1940年，數學家Perron證明了凱勒猜想在1到6維空間是正確的。在7維、8維、9維三個維度空間中，凱勒猜想是否成立？只要解決這三個維度，纏繞數學家幾十年的問題就徹底搞定了。
  • 只用三頁紙,他就推翻了困擾學界半世紀的重要猜想
    這一猜想已經被證明是正確的，但它的衍生問題仍然讓數學家著迷不已。最近，一位俄羅斯數學家發表了一篇僅有三頁的論文，推翻了該領域存在了 53 年的一個重要猜想。 幾十年以來，數學家積累了一系列有關這一猜想的研究證據，其中一些表明它是正確的，而另一些則認為它是錯誤的。儘管數學家們對於這個猜想的正確與否各執一詞，但似乎每個人都同意，無論是證明還是證偽都非常困難。 「我個人認為這個猜想應該是真的，因為很多聰明的人都研究過它，如果有的話，應該早能夠找到一個反例。」
  • 只用三頁紙,他推翻了困擾學界半世紀的重要猜想
    這一猜想已經被證明是正確的，但它的衍生問題仍然讓數學家著迷不已。最近，一位俄羅斯數學家發表了一篇僅有三頁的論文，推翻了該領域存在了 53 年的一個重要猜想。 幾十年以來，數學家積累了一系列有關這一猜想的研究證據，其中一些表明它是正確的，而另一些則認為它是錯誤的。儘管數學家們對於這個猜想的正確與否各執一詞，但似乎每個人都同意，無論是證明還是證偽都非常困難。 「我個人認為這個猜想應該是真的，因為很多聰明的人都研究過它，如果有的話，應該早能夠找到一個反例。」
  • 「四色猜想」是什麼為什麼它困惑了大多數數學家近半個世紀!
    數學家從節約的角度考慮，任何地圖，使得相鄰的地區塗上不同的顏色，至少得用多少種顏色呢?四色問題或者四色猜想的結論是：四色足夠! 百年拼搏史 說起來，這個問題可能有許多人發現過，但是第一個明確記錄在案的是剛從倫敦大學畢業不久的英國青年弗蘭西斯·葛斯瑞。1852年，他給一張英國地圖著色時發現，四種顏色足夠。
  • 專訪菲爾茲獎得主高爾斯:漫遊音樂與數學,發現古老猜想反例
    這一理論由波蘭數學家巴拿赫（S.Banach)在1920年提出。「關於巴拿赫空間，有一些古老猜想，例如，是否每個巴拿赫空間帶有某種性質？」高爾斯在專訪中告訴澎湃新聞（www.thepaper.cn）記者，「在之前，沒有人知道是否存在反例。」56歲的高爾斯一頭白髮，身型瘦高。他說話語速不快，回答記者提問時會不時地陷入思考，偶爾被自己逗笑。
  • 破解「哥德巴赫猜想」的數學家
    這曾是一個舉世震驚的奇蹟：一位屈居於6平方米小屋的數學家，借一盞昏暗的煤油燈，伏在床板上，用一支筆，耗去了幾麻袋的草稿紙，攻克了世界著名數學難題「哥德巴赫猜想」中的「1+2」，創造了距摘取這顆數論皇冠上的明珠「1+1」只是一步之遙的輝煌。
  • 一種「簡單而全新」的方法證明了黎曼猜想,引發了全世界數學家們的...
    儘管無數一流數學家向證明黎曼猜想發起衝擊，卻無一人能成功——不過就在昨天（9月24號），著名數學家、菲爾茲獎和阿貝爾獎雙料得主阿蒂亞爵士或將成為這樣一個劃時代的人物。他表示，自己基於馮·諾依曼、希策布魯赫和狄拉克 等人的成果，使用一種「簡單而全新」的方法證明了黎曼猜想，引發了全世界數學家們的關注。
  • 能推翻一個數學猜想!
    Yaroslav Shitov是一名俄羅斯的數學家，他在arXiv發表了一篇論文，在這篇只有3頁長（主體部分僅有2頁）的論文中，他推翻了數學家Stephen Hedetniemi在1966年提出的一個猜想。
  • 黎曼猜想被證明了!
    伯恩哈德 · 黎曼（Bernhard Riemann，1826-1866）黎曼猜想最初於 1859 年由德國數學家波恩哈德·黎曼提出。但是，只要找到了一個點不在線上，那就推翻了黎曼猜想。現在，數學家使用計算機，已經驗證了最初的15億個這樣的點，全都符合黎曼猜想的排列規律。不過，至今尚無人給出完整的理論證明。
  • 數學界大事發生,京都大學宣布望月新一解決「ABC猜想」
    1996年，望月因解決了格羅滕迪克提出的一個猜想，而在國際上名聲大噪，緊接著在1998年的國際數學家大會上，望月受邀做了報告，至此，望月成功進入國際數學界的「上流社會」。 所有的一切，看著都異常順利，也許，在不久的將來還有一枚菲爾茲獎章在等著。
  • 數學大反例合集
    根據 MathWorld 的描述，1899 年 Perrin 本人曾經做過試驗，隨後 Malo 在 1900 年， Escot 在 1901 年，以及 Jarden 在 1966 年都做過搜索，均未發現任何反例。直到 1982 年， Adams 和 Shanks 才發現第一個反例 n = 271 441 ，它等於 521 × 521 ，卻也能整除 f(271 441) 。
  • 數學家張益唐破譯「孿生素數猜想」
    而隨著素數的增大，下一個素數離上一個素數應該越來越遠，故古希臘數學家歐幾裡得猜想，存在無窮多對素數，他們只相差2，例如3和5，5和7，2003663613×2195000-1和2003663613×2195000+1等等。　　這就是所謂的孿生素數猜想，它與黎曼猜想、哥德巴赫猜想一樣讓無數數論學者為之著迷。
  • 數學天才望月新一證明abc猜想,只有十幾個數學家能懂
    這一次望月新一的證明，全篇超過600頁，2012年就已發表，但足足經過了8年的同行評審才通過，期間開過多次研討會——但依然有很多數學家無法理解。 曉查 發自 凹非寺 量子位 報導 | 公眾號 QbitAI abc猜想，數學界懸而未決的重要猜想，它的證明過程經過8年的同行評審，終於要在期刊上發表了。 論文作者是日本的天才數學家望月新一，他33歲起就在京都大學擔任數學教授。
  • 歐拉函數及其猜想
    歐拉函數的推論都很容易證明，難的是歐拉函數產生的各種猜想。猜想1：對於素數p，φ(p)=p−1，那麼猜想「如果φ(n)=n−1，n是素數嗎？（2020年）     對這個猜想進行過嘗試的數學家只能猜：    ①如果有反例，這個n應該很大很大吧            目前已經證明，n>5.5×10     ②如果有反例，這個n應該有很多因子吧            目前已經證明，至少213個因子    ③即使有反例，也應該很少很少吧我把這個猜想稱為
  • 數學天才望月新一證明abc猜想,全球只有十幾個數學家讀懂
    abc猜想，數學界懸而未決的重要猜想，它的證明過程經過8年的同行評審，終於要在期刊上發表了。論文作者是日本的天才數學家望月新一，他33歲起就在京都大學擔任數學教授。同時也正因為如此，才有了學界長達8年的爭論。什麼是abc猜想？abc猜想，最初由法國數學家約瑟夫·奧斯特萊和大衛·馬瑟，在1985年提出。並且一經提出，abc猜想就成為數論領域的重要猜想之一。