電腦立大功!數學家靠 C++、MATLAB,成功破解 44 年「有理四面體」難題

本文經 AI 新媒體量子位(公眾號 ID:QbitAI)授權轉載,轉載請連繫出處
作者:量子位

電腦程式又為數學家立功了。

最近,來自美國、加拿大、瑞士的 4 位數學家,用 C++  和 MATLAB 程式解出了一個 6 元 105 項方程的 59 組特殊解。

求解完這個方程,也就證明了「有理四面體」(rational tetrahedra)總共只有 59 個「特殊」形狀和 2 個系列,從而解決了一個 44 年的數學難題。

而提出這一難題的,正是去年因新冠而去世的著名數學家約翰·康威(John Conway)。

△ 59 個「有理四面體」單獨解(圖片來自:QuantaMagazine)

1976 年,康威給出了求解該問題的方程。1995 年,兩位數學家找到了其中 59 組特殊解,但是他們不確定有沒有遺漏。

△ 有理四面體具有兩組「連續」解和 59 組單獨解

得益於電腦硬體的發展,現在只用 MacBook Pro 和幾台至強 CPU 電腦,在幾天內就完成了對所有解的搜索。

結果證明,那兩位數學家在 20 多年前其實已經得到了完整的答案。

什麼是有理四面體?

四面體,顧名思義,就是四個三角形圍成的立體圖形。

四面體每兩個面之間都組成一個二面角。四面體有 6 條棱,因此有 6 個二面角。

△ 四面體中有 6 個二面角(圖片來自 Poonen 手稿)

有理四面體是指四面體中的 6 個二面角都是有理數角度(與 180° 角的比值是有理數)。

就好像三角形的內角和公式數學公式: a+b+c=180°一樣,四面體的 6 個二面角之間也有一種關係,只不過這種關係要複雜得多。

定義 θij 為四面體第 i 個面與第 j 個面的夾角(顯然 θ ij =θ ji),那麼這 6 個二面角之間的關係可以行列式表示為:

因為是有理四面體,所以 θ ij =Qπ(弧度),Q 是有理數。

我們把行列式展開後,會得到一個包含 17 項的方程,而且方程中還有餘弦函數,求解難度很大。

但是數學家們想到了一個巧妙的化簡方法。

歐拉公式

接下來,數學家們用到了「最美數學公式」——歐拉公式——來簡化方程。

歐拉公式將複數(實數+虛數)的指數函數與三角函數聯繫起來:

i 是虛數,即 -1 的平方根。如果用圖像的方式理解歐拉公式,那就是:

很顯然,無論 θ 值如何變化,e iθ 到 0 點的距離一定是 1。

所以如果我們定義複數:

那麼這個複數一定是在以原點為圓心,半徑為 1 的圓上。

△ 方程 z 5 =1 的 5 個解都在單位圓上

現在,方程裡的三角函數可以用複數來替代了:

這樣,上面的行列式從一個三角函數方程變成了一個多項式方程:

但問題也隨之而來,這個方程總共有 105 項,而且是一個 6 元方程!不過好消息是,我們知道這 6 個未知數都在那個半徑為 1 的圓上(稱作「單位根」)。

巧妙的是,複數 z ij 與 x 軸的夾角 θ ij 正好就是四面體的二面角,因此這些解不僅在圓上,與 x 軸夾角也必須是 π 弧度的有理數倍。

1995 年,在那個沒有性能強勁 PC 的年代,來自 UC 伯克利的 Poonen 和滑鐵盧大學的 Rubinstein 通過插入六個有理數的組合,來猜測這個方程的解,他們總共找到了 59 組。

這樣做帶來一個問題是:可以找到解,但是不能保證把所有解一網打盡。

一次數學家之間,偶然的碰撞

問題一擱置就是 20 多年,直到去年 3 月,Poonen 參加了一次講座。

在那一次的講座上,研究數論的數學家 Kedlaya 介紹了自己的工作:搜索了不同多項式方程的單位根。

這不就和尋找「有理二面體」的問題等價嗎?

Poonen 很快就給 Kedlaya 發郵件,說明自己的來意:你們研究的「正是我在 1990 年代需要的東西」。

收到郵件後,Kedlaya 與另一位研究單位根的數學家 Kolpakov 取得了聯繫。另一邊,Poonen 也聯繫上了他當年的的老搭檔 Rubinstein。

△ 聯手解決「有理四面體」的四位數學家

四人迅速組團,開始著手工作。

即便現在的電腦性能相比 20 多年前提升許多,但想要找到一個 6 元 105 向方程的所有有理數解,還是不可能想像的。

必須要把搜索範圍進一步縮小。

首先,他們「化整為零」。

在新論文中他們證明了,這個 105 項的複雜多項式方程可以用多個更簡單的多項式表示,把這個 6 元方程轉化成了數百個簡單方程的集合。

尋找這些較簡單方程的單位根,比原方程的搜索範圍小得多。而且由於簡單的方程與復雜的方程之間的對應關係,找到一個方程的根,能幫助找到另一個方程的根。

搜索上限的問題解決了,但搜索的間隔還是太小,搜索空間依然很龐大,工作無法繼續。

然後,他們的第二步是,利用對稱性進一步壓縮搜索空間。

他們知道方程的解具有一定的對稱性,如果在區間的一部分上有解,那麼在區間的另一部分上也必須有解。

這樣一來,他們就可以開發出新算法,利用這種對稱性結構來更有效地進行搜索。

經過幾個月的努力,他們完成了任務的分解。除去編程,整個搜索只佔用了幾顆 Intel Core 與至強處理器數小時的時間。

電腦終於找到了所有特殊解,真的只有 59 個!(另外還有兩組「連續」解。)

現在,他們的算法已經公佈在 GitHub 上。

2020 年 11 月,四個數學家把論文發佈到 arXiv 上,44 年後終於用電腦的方法完成了康威的願望。

也算是告慰了康威的在天之靈,他們在論文首頁上寫著:“In memory of John H. Conway”。

後續

解決這個問題後,Poonen 本人親自撰寫了一篇科普文章,還和西蒙斯基金會聯合錄製了一段科普影片。

Poonen 列出了三個重要的四面體問題,最早的要追溯到 2300 多年前亞里士多德的疑問:什麼樣的四面體能堆滿整個空間?

1900 年,數學家大衛·希爾伯特給出了另一個疑問:什麼樣的四面體可以經過有限次的切割重組為一個等體積的立方體?

至於第三個問題,就是剛剛解決的有理二面體問題。而前兩個問題,人們現在還不知道答案。

如果非要問這個有理二面體有什麼實際價值,Poonen 給出了一個有趣的案例:

假設我們要在一個星球上建造 N 個城市,讓這 N 個城市每兩個之間的距離都是有理數,那麼我們應如何規劃?

(註:指城市之間的球面距離與赤道周長的比值是有理數。)

△ 如何在星球上建造兩兩距離皆為有理數的城市(圖片來自 Poonen 手稿)

因為有理四面體問題的解決,現在這個問題有兩個方案:

一個是讓赤道上均勻分佈幾個城市,再把剩下兩座城市放在南極北極。

而如果想讓城市在星球上分佈得更均勻一點,也就是上圖右邊的方法,那麼 N 不能超過 30,否則無解。

(本文經 AI 新媒體量子位 授權轉載,並同意 TechOrange 編寫導讀與修訂標題,原文標題為 〈计算机搞定 44 年几何难题,原来这 2 个人 25 年前猜对了 〉。首圖來源:Pixabay CC Licensed

延伸閱讀

【七維空間是否成立?】數學家集結 40 台電腦算力,半小時破解困擾 90 年的凱勒猜想難題
【手癢快拿出紙筆】百年未解的山羊吃草難題,德國數學家用「複變函數」破解了
【內附開源碼】Google 研發「公式製造機」,讓你瞬間變身數學天才


混合辦公蔚為風潮,企業 IT 防疫你做了嗎?

同事們不斷回報 Wi-Fi 網路連線、資訊存取等問題嗎? 立即斬斷這些疑難雜症,全公司的連線體驗一次超進化,還可獲得 2021 雲端網管黃金白皮書 >> 進入測驗

點關鍵字看更多相關文章: