Fw: [問卦] 【七維空間是否成立？】數學家集結 40 台

看板specialman作者 (館長加油啊！)時間3年前 (2020/09/04 22:11), 3年前編輯推噓0(0推 0噓 3→)
留言3則, 1人參與, 3年前最新討論串1/1
※ [本文轉錄自 Gossiping 看板 #1VKSlQ1K ] 作者: Glamsight (安穩殘憶) 看板: Gossiping 標題: [問卦] 【七維空間是否成立？】數學家集結 40 台 時間: Fri Sep 4 13:08:40 2020 難題備註請放最後面 違者新聞文章刪除 1.媒體來源: ※ 例如蘋果日報、自由時報（請參考版規下方的核准媒體名單） 科技橘報 2.記者署名: ※ 若新聞沒有記者名字或編輯名字，請勿張貼，否則會被水桶14天 ※ 外電至少要有來源或編輯 如:法新社 責任編輯：賴佩萱 3.完整新聞標題: ※ 標題沒有完整寫出來 ---> 依照板規刪除文章 【七維空間是否成立？】數學家集結 40 台電腦算力，半小時破解困擾 90 年的凱勒猜想 難題 4.完整新聞內文: ※ 社論特稿都不能貼！違者刪除（政治類水桶3個月)，貼廣告也會被刪除喔！可詳看版規 https://imgur.com/lC2J66P.jpg
【我們為什麼挑選這篇文章】德國數學家 Ott-Heinrich Keller 於 90 年前提出了所謂 的「凱勒猜想」，這是一個用相同瓷磚覆蓋空間的問題。他對每個維度的空間做出論斷： 在 n 維空間裡，用 n 維立方體填充空間，兩個相鄰的單位體會共用 n-1 個維面。 有關各維度的論證一一浮出檯面，唯讀 7 維空間遲遲未解，但近期在 40 台電腦的強大 算力下，這個難題終於有解了！（責任編輯：賴佩萱） 本文經 AI 新媒體量子位（公眾號 ID：QbitAI）授權轉載，轉載請連繫出處 數學家會程式碼，誰也擋不住！就連困擾人類 90 年的數學猜想也擋不住。來自史丹佛、 CMU 等名校的 4 名數學家，將一個數學難題轉化成了對 10 億個結果進行「暴力搜索」 。 冷門數學題終於破解 他們把這串程式碼輸入 40 台電腦組成的計算集群，30 分鐘後，電腦給出了一個 200 GB 大小的證明結果： 凱勒猜想在不超過 7 維的空間是成立的 。 現在，任何人都可以去 GitHub 上複製這串程式碼，驗證這一數學定理。比較意外的是， 這段獲得電腦學術會議 IJCAR（國際自動推理聯合會議）最佳論文獎的程序，上線 GitHub 半年，只獲得一顆星。 https://imgur.com/0MgdeBp.jpg
那麼，這 4 位數學家要證明的「凱勒猜想」到底是什麼？為何非要用電腦來證明？電腦 證明的結果可靠嗎？ 下面讓我們一一道來。 什麼是凱勒猜想？ 假如用一批完全相同的正方形瓷磚鋪滿地面，中間不留空隙。顯然，瓷磚之間會共用一條 邊，如下圖藍線所示： https://imgur.com/m2H75xz.jpg
在 3 維空間中，如果要用立方體佔滿空間，是不是也和 2 維空間類似呢？ 想像一下，如果像下圖那樣在空間中隨便放入幾個立方體，由此展開填滿整個空間，那麼 唯一的辦法就是讓接上的立方體共用藍色的面。 https://imgur.com/GgqVF5C.jpg
2 維、3 維皆如此，更高維度的空間會怎樣？1930 年，德國數學家凱勒猜測，如果用 n 維立方體填滿無限空間，則立方體之間必然會出現「面對面」，對於任意維度都成立 。 這便是凱勒猜想。 但數學猜想不能僅靠直覺，必須有嚴格的證明。90 年來，數學家一直不懈努力。1940 年 ，數學家 Perron 證明了凱勒猜想在 1 到 6 維空間是成立的 ；1992 年，另外兩位數學 家 Lagarias 和 Shor 證明，凱勒猜想在 10 維空間上是不成立的 （注：這位 Shor 就 是那個提出用量子計算機求解質因數分解的數學家） 那還有 3 個維度沒有解決呢！在 7 維、8 維、9 維 三個維度空間中，凱勒猜想是否成 立？ 有數學論證表明，如果凱勒猜想在 n 維空間上是錯的，那麼它在比 n 更高的維度上也一 定是錯的。2002 年，數學家 Mackey 已證明，凱勒猜想在 8 維空間不成立，因此在 9 維空間也不成立 。 至此，7 維空間成為唯一的難題。 修改證明方法：電腦「圖論」 可能你已經發現，從上世紀 90 年代以來，凱勒猜想的證明速度大大加快，數學家只用 了 10 年時間就把問題縮小到三個維度。 這主要得益於兩位數學家的貢獻。當年，Perron 求解 1 到 6 維度時，沒有特殊的捷徑 。而到 1990 年，凱勒猜想的證明方法發生了巨大的變化。 數學家 Corrádi 和 Szabó 提出了一種新的方法，把原來無限空間的問題變成有限、離 散的問題，也讓電腦解決凱勒猜想成為可能。 他們巧妙地把凱勒猜想變成圖論問題，就是構造所謂的凱勒圖（Keller Graph），而圖論 正是電腦所擅長的。 在這種方法的指導下，Lagarias 和 Shor 兩人很快在 2 年後就證明了 10 維空間的情況 ：凱勒猜想不成立。又過了 10 年，Mackey 證明，凱勒猜想在 8 維空間不成立。 那麼，凱勒圖究竟是什麼，它為什麼能夠加速凱勒猜想的證明？ 解析「凱勒圖」構造 首先，我們從最簡單的 2 維情況說起。現在，我們有一種牌，牌上畫著兩個有顏色的點 ，兩個點是有順序的，不能調換，比如，1 黑 2 白≠1 白 2 黑。 兩個點總共可以塗 4 種顏色，顏色分成 2 對：紅色對綠色、白色對黑色。數學家已經證 明，分配給點的顏色相當於正方形在空間中的坐標。兩張牌的顏色是否配對標示了兩個正 方形的相對位置。 點的顏色與正方形的具體關係是這樣的： 1. 兩對點完全相同，表示兩個正方形完全重疊 https://imgur.com/DjtdhwG.jpg
2. 兩對點顏色都不同，且顏色都不配對，表示兩個正方形有部分重疊 https://imgur.com/qeWl5Gk.jpg
3. 一對點顏色相同，另一對點顏色配對，表示兩個正方形共用一個邊 https://imgur.com/zZA2qUN.jpg
4. 一對點顏色不同，另一對點顏色配對，表示兩個正方形的邊相互接觸但不重合 https://imgur.com/Tyt43Sx.jpg
2 個點的凱勒圖，要用 2 對顏色去填充牌面，總共有 16 種情況。然後我們把這 16 張 牌擺在桌上，只有符合前面條件 4 的兩張牌，才能用線將二者連起來，這樣就構成了一 張「凱勒圖」。 https://imgur.com/Tzwm2zy.jpg
包含 16 張牌的凱勒圖就描繪了正方形填補平面的所有可能。如果 2 維空間中凱勒猜想 不成立，那麼我們肯定能找到 4 個正方形，它們之間沒有共用的邊，但是能夠無縫隙地 填在一起，然後在屏幕上無限複製這 4 個正方形，就能填滿整個螢幕。 實際上並不可能。如果按此操作，只會得到有著無數孔隙（下圖紫色部分）的填充方式。 https://imgur.com/eh3E2V8.jpg
對應到凱勒圖中，就是在圖中找到 4 張牌，它們兩兩之間都有連線（在數學上，這叫做 完全圖）；顯然，在 2 維問題的凱勒圖中，我們找不到這樣的 4 張牌（可以自己去上面 的凱勒圖中找找看）。 https://imgur.com/Xwv1HkE.jpg
這樣，我們把就把 n 維立方體以及位移 s 與牌的點數 n、顏色對數 s 聯繫起來。 作為更一般的規則，如果要證明 n 維凱勒猜想是錯的，就要在對應的凱勒圖中找到 2n 張牌，且這些牌兩兩相連，但正因為你找不到 4 個張牌組成的完全圖，所以 2 維空間的 凱勒猜想是對的。 為了在 3 維空間中證明凱勒猜想，可以使用 216 張牌，每張牌上 3 個點，並可以使用 3 對顏色（這一點相對靈活）；然後，我們需要尋找 23=8 張牌，它們兩兩之間都有連線 ，但還是找不到。 到了 8 維空間中，我們總算可以找到符合條件的 256 張牌，所以 8 維空間的凱勒猜想 是錯的。 https://imgur.com/moZYPjh.jpg
8 維空間中的一個反例（一個凱勒圖的完全子圖） 七維空間為什麼那麼難解？ 接下來的事情就是在 7 維空間對應的凱勒圖上尋找完全子圖。然而這個問題卻從 8 維問 題解決後被擱置了 17 年。 根據前面的說明，求解 8 維空間和 10 維空間的凱勒猜想，要尋找 28=256 和 210=1024 張牌的子圖，而 7 維空間只要尋找 27=128 張牌的子圖。 後者的難度似乎更小，7 維空間的問題應該更簡單啊！其實不然，因為從某種意義上說， 8 維和 10 維可以「分解」為容易計算的較低維度，但 7 維不行。 證明了 10 維情況的 Lagarias 說：「7 維不好，因為它是質數，這意味著你無法將其分 解為低維，因此別無選擇，只能處理這些圖的全部組合。」 對於人腦來說，尋找大小為 128 的子圖是一項艱鉅的任務，但這恰恰是電腦擅長回答的 問題。 電腦幫幫忙！超強博士生做到了 此前證明 8 維問題的 CMU 教授 Mackey 拉上了史丹佛的數學系博士生 Brakensiek 和專 長電腦輔助證明的助理教授 Heule。 回憶起立項的那天，Mackey 說，Brakensiek 是真正的天才，看著他就像看著 NBA 總決 賽里的 LeBron James。Brakensiek 本人確實很厲害，他曾是 2013/14 兩屆國際訊息學 奧林匹克賽（International Olympiad in Informatics，IOI）金牌得主。 https://imgur.com/jA7lu1i.jpg
論文第一作者 Brakensiek 言歸正傳。為了方便電腦求解，他們換了個方向來思考：先設定牌上有 7 個點、6 種可 能的顏色，按照前面的「條件 4」對這些牌上色，看看能不能找到 128 種不同的填色方 法，如果找不到，那麼凱勒猜想成立。 用電腦輔助證明數學問題，還需要把它變成一系列邏輯運算，也就是處理 0 和 1 之間的 與或非關係。 若要求解 7 維，則總共包含 39000 個不同布爾變量（0 或 1），有 239000 種可能性 ，這是一個非常非常大的數字，有 11741 位數。 https://imgur.com/sL6KzzX.jpg
數學家利用排除法和對稱性，縮小可能解方 一台普通電腦只能處理 324 位數種可能，離解決問題還遠得很，就算交給超級計算機也 不夠；但是，這幾位數學家想到了排除法，只要得到結論，而不必實際檢查所有可能性。 效率才是王道！ 比如，用電腦規則給 128 張牌上色，當你塗到第 12 張牌的時候，發現找不到符合條件 的下一張牌了。那麼所有包含這 12 張牌的排列都可以排除；提升效率的另一種方式是利 用對稱性。如果已經驗證了某種排列不可能，那與之對稱的所有情況都可以排除。 透過這兩種方法，他們把搜索空間縮小到 10 億（230）。這樣一來，用電腦搜索變成了 可能。 最終，他們僅計算了半個小時，便有了答案。 電腦沒有找到符合條件的 128 張牌，所以 7 維空間的凱勒猜想確實成立 。實際上，電 腦提供的不僅僅是一個答案，證明的內容多達 200 GB。4 位論文作者將證明送入電腦的 證明檢查器，確認了它的可靠性。 解決了凱勒猜想後，Heule 的下一個目標是用電腦證明數學裡「最簡單的不可能問題」— — 3n+1 猜想，去年陶哲軒已經「幾乎」解決了這個問題，現在可能只差一步之遙了。 5.完整新聞連結 (或短網址): ※ 當新聞連結過長時，需提供短網址方便網友點擊 https://bit.ly/32XdSkZ 6.備註: ※ 一個人一天只能張貼一則新聞，被刪或自刪也算額度內，超貼者水桶，請注意 ※ 備註請勿張貼三日內新聞(包含連結、標題等) 嗯嗯，跟我想的一樣。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.90.228 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1599196122.A.054.html ※ 編輯: Glamsight (140.112.90.228 臺灣), 09/04/2020 13:09:14
→
09/04 13:09, 3年前 , 1F
嗯 我也是這麼認為
09/04 13:09, 1F
推
09/04 13:09, 3年前 , 2F
我去年就想出來了，只是筆記本空間不夠寫不下證明過程
09/04 13:09, 2F
推
09/04 13:09, 3年前 , 3F
估狗:我用一臺十秒就夠了
09/04 13:09, 3F
→
09/04 13:11, 3年前 , 4F
關於這個 我想到一個絕妙的證明方法 可惜推文太短寫不下
09/04 13:11, 4F
推
09/04 13:11, 3年前 , 5F
快推 免得被說不懂
09/04 13:11, 5F
推
09/04 13:12, 3年前 , 6F
跟我想的一樣
09/04 13:12, 6F
噓
09/04 13:12, 3年前 , 7F
所以你要問甚麼卦?
09/04 13:12, 7F
推
09/04 13:12, 3年前 , 8F
七樓已經解出來了。準備領諾貝爾獎
09/04 13:12, 8F
推
09/04 13:13, 3年前 , 9F
跟我自己算的 一樣
09/04 13:13, 9F
推
09/04 13:13, 3年前 , 10F
跟我想的一樣
09/04 13:13, 10F
噓
09/04 13:13, 3年前 , 11F
END
09/04 13:13, 11F
推
09/04 13:13, 3年前 , 12F
嗯 謝謝數學家們幫我驗算
09/04 13:13, 12F
推
09/04 13:14, 3年前 , 13F
7維是什麼鬼 時間上面還有其他緯度？
09/04 13:14, 13F
推
09/04 13:14, 3年前 , 14F
先推 和我想的一樣
09/04 13:14, 14F
推
09/04 13:15, 3年前 , 15F
之前我就快算出來。只是硬碟裝不下就沒公開給大家
09/04 13:15, 15F
推
09/04 13:17, 3年前 , 16F
我記得目前假設到了11維度
09/04 13:17, 16F
推
09/04 13:17, 3年前 , 17F
果然 跟我想的不一樣
09/04 13:17, 17F
→
09/04 13:18, 3年前 , 18F
嗯嗯 跟我想的標題不一樣
09/04 13:18, 18F
→
09/04 13:19, 3年前 , 19F
1.時間不是空間維度 2.這是數學公式上的維度 不是物
09/04 13:19, 19F
推
09/04 13:19, 3年前 , 20F
我找一下大學暑假無聊的時候自己推導的筆記本
09/04 13:19, 20F
→
09/04 13:19, 3年前 , 21F
理空間維度
09/04 13:19, 21F
→
09/04 13:19, 3年前 , 22F
可以先講講啥麼是五維空間好嘛?
09/04 13:19, 22F
推
09/04 13:21, 3年前 , 23F
坐等老高解說
09/04 13:21, 23F
推
09/04 13:22, 3年前 , 24F
光看標題就知道結果了 EZ
09/04 13:22, 24F
噓
09/04 13:22, 3年前 , 25F
媒體來源都寫錯
09/04 13:22, 25F
推
09/04 13:22, 3年前 , 26F
嗯嗯跟我手算的一樣
09/04 13:22, 26F
推
09/04 13:22, 3年前 , 27F
跟我想的差不多~
09/04 13:22, 27F
推
09/04 13:24, 3年前 , 28F
這個問題我在5年前就想出來了，只是我太忙沒寫出來而已
09/04 13:24, 28F
推
09/04 13:25, 3年前 , 29F
不明覺厲
09/04 13:25, 29F
推
09/04 13:26, 3年前 , 30F
嗯嗯 我也這麼認為
09/04 13:26, 30F
→
09/04 13:27, 3年前 , 31F
11維度 好像是超弦理論推的
09/04 13:27, 31F
推
09/04 13:27, 3年前 , 32F
我先去吐一下
09/04 13:27, 32F
推
09/04 13:27, 3年前 , 33F
這麼高次元的存在
09/04 13:27, 33F
推
09/04 13:29, 3年前 , 34F
我還是去看老高好了
09/04 13:29, 34F
→
09/04 13:30, 3年前 , 35F
嗯嗯，我在看諾蘭片的時候就知道了
09/04 13:30, 35F
推
09/04 13:31, 3年前 , 36F
我國小玩積木有想過類似的 問老師他也不懂想說就算了
09/04 13:31, 36F
→
09/04 13:31, 3年前 , 37F
靠杯完全看不懂
09/04 13:31, 37F
推
09/04 13:32, 3年前 , 38F
我居然仔細的看完了
09/04 13:32, 38F
推
09/04 13:32, 3年前 , 39F
我早知道解開 覺得沒什麼可 訴大家的必要
09/04 13:32, 39F
還有 78 則推文
推
09/04 15:40, 3年前 , 118F
學過離散就大概看的懂名詞 ㄏㄏ 但是還是看不懂整篇
09/04 15:40, 118F
推
09/04 15:42, 3年前 , 119F
推文追蹤
09/04 15:42, 119F
推
09/04 15:44, 3年前 , 120F
可以說中文嗎
09/04 15:44, 120F
推
09/04 16:21, 3年前 , 121F
嗯嗯 跟我想的一樣
09/04 16:21, 121F
推
09/04 16:21, 3年前 , 122F
?___?
09/04 16:21, 122F
推
09/04 16:21, 3年前 , 123F
我前幾天算完還沒發表 被他們搶先一步
09/04 16:21, 123F
推
09/04 16:28, 3年前 , 124F
嗯嗯 我也這麼想的
09/04 16:28, 124F
推
09/04 16:30, 3年前 , 125F
嗯嗯 跟我想得一樣
09/04 16:30, 125F
推
09/04 16:31, 3年前 , 126F
噢...
09/04 16:31, 126F
推
09/04 16:36, 3年前 , 127F
好有趣，推
09/04 16:36, 127F
推
09/04 16:52, 3年前 , 128F
幹我準備要口試這個
09/04 16:52, 128F
推
09/04 17:02, 3年前 , 129F
原來如此 我也是這麼想
09/04 17:02, 129F
推
09/04 17:03, 3年前 , 130F
頭好痛
09/04 17:03, 130F
推
09/04 17:03, 3年前 , 131F
這個用量子電腦算應該有可能吧
09/04 17:03, 131F
→
09/04 17:06, 3年前 , 132F
這實驗跟我推論結果差不多，可惜我放在抽屜忘了發期刊
09/04 17:06, 132F
推
09/04 17:13, 3年前 , 133F
推
09/04 17:13, 133F
推
09/04 17:15, 3年前 , 134F
我 我懂了（噴血
09/04 17:15, 134F
→
09/04 17:23, 3年前 , 135F
跟我想的一樣
09/04 17:23, 135F
推
09/04 17:40, 3年前 , 136F
未看先猜一定有人回"我也是這樣想的"
09/04 17:40, 136F
推
09/04 17:42, 3年前 , 137F
要不是謎片塞滿了 不然早就算出來了
09/04 17:42, 137F
推
09/04 17:52, 3年前 , 138F
記者文章寫的不錯 有寫到重點
09/04 17:52, 138F
推
09/04 18:33, 3年前 , 139F
一顆星笑死 不過應該是沒人看得懂在幹嘛
09/04 18:33, 139F
推
09/04 18:34, 3年前 , 140F
這篇絕對不是記者寫的 妓者沒有這種程度
09/04 18:34, 140F
推
09/04 18:38, 3年前 , 141F
我心算就知道了，只是我懶的寫下來
09/04 18:38, 141F
推
09/04 19:09, 3年前 , 142F
程式碼有點怪怪的 我覺得這樣寫會有問題
09/04 19:09, 142F
推
09/04 19:10, 3年前 , 143F
嗯嗯 差不多
09/04 19:10, 143F
推
09/04 19:18, 3年前 , 144F
「8維以上就錯了還需要證明七維？」拼圖空一塊在那感覺很差
09/04 19:18, 144F
推
09/04 19:31, 3年前 , 145F
這記者誰啊？寫的不錯
09/04 19:31, 145F
推
09/04 19:33, 3年前 , 146F
我之前也差點算到了，可惜硬碟要清出空間塞A片
09/04 19:33, 146F
推
09/04 19:39, 3年前 , 147F
閱。
09/04 19:39, 147F
推
09/04 19:55, 3年前 , 148F
當初5.25磁片裝不下
09/04 19:55, 148F
推
09/04 20:12, 3年前 , 149F
完全看不懂
09/04 20:12, 149F
推
09/04 20:18, 3年前 , 150F
好猛
09/04 20:18, 150F
→
09/04 20:32, 3年前 , 151F
幹 是對三維的人有什麼幫助啦...
09/04 20:32, 151F
推
09/04 20:52, 3年前 , 152F
跟我想的一樣
09/04 20:52, 152F
推
09/04 21:43, 3年前 , 153F
好 跟我想的一樣
09/04 21:43, 153F
※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: NoPTT (1.171.183.132 臺灣), 09/04/2020 22:11:26
→
09/05 02:28, 3年前 , 154F
這篇其實不錯，撰文者努力科普了，而且我還大致看得懂，
09/05 02:28, 154F
→
09/05 02:29, 3年前 , 155F
表示用心的文章有發生效用
09/05 02:29, 155F
→
09/05 02:29, 3年前 , 156F
但也是因為這篇想證明的東西不難想像啦～目的算是好懂的
09/05 02:29, 156F
‣ 更多 NoPTT 的文章
文章代碼(AID): #1VKaiFY_ (specialman)