三立方數和一直是困擾數學(xué)家的難題之一，一些數字的求解非常簡(jiǎn)單，例如 29 可以寫(xiě)成 3^3+1^3+1^3 (27 + 1 + 1)。2019 年，MIT 數學(xué)家 Andrew Sutherland 和布里斯托大學(xué)教授 Andrew Booker 不僅首次攻克了 100 以?xún)茸匀粩档淖詈笠粋€(gè)關(guān)卡——42，還找到了自然數 3 的第 3 組三立方和解。近日，相關(guān)研究在《美國國家科學(xué)院院刊》（PNAS）上發(fā)表。
本文來(lái)自微信公眾號：機器之心（ID：almosthuman2014），編輯：魔王、杜偉，原文標題：《3的三個(gè)整數立方和有多少個(gè)解？全球40萬(wàn)臺計算機助力，MIT研究登上PNAS》
1992 年，數學(xué)家羅杰希思 - 布朗（Roger Heath-Brown）提出猜想，所有自然數都可以被寫(xiě)成 3 個(gè)數立方之和。
2019 年，數學(xué)家 Andrew Sutherland 和 Andrew Booker 首次將 42 寫(xiě)成 3 個(gè)整數的立方和，這意味著(zhù) 100 以?xún)茸匀粩等勘还テ?/strong>。
Andrew Sutherland（左）和 Andrew Sutherland（右）。
但是，兩人并未停止探索的腳步，而是“揮刀向更強”：找出自然數 3 的下一個(gè)解。在發(fā)現 42 的立方和解之后數周，他們即解決了這個(gè)難題。近期，Sutherland 和 Booker 的相關(guān)研究文章發(fā)表在了《美國國家科學(xué)院院刊》（PNAS）上。
文章鏈接：https://www.pnas.org/content/118/11/e2022377118
三立方數和問(wèn)題
1957 年，英國數學(xué)家莫德?tīng)枺↙ouis Mordell）提出一個(gè)問(wèn)題：哪些正整數可以寫(xiě)成三個(gè)立方數之和？（這三個(gè)數可正、可負，也可以等于 0。）這就是著(zhù)名的“三立方數和問(wèn)題”。
1992 年，英國牛津大學(xué)的羅杰 · 西斯–布朗提出了一個(gè)猜想：除了 9n±4 型自然數外，所有自然數都可以用無(wú)窮多種不同方式寫(xiě)成三個(gè)立方數的和。
20 世紀，三立方數和問(wèn)題的研究進(jìn)展（圖源：https://math.mit.edu/~drew/Waterloo2019.pdf）
2000 年，美國哈佛大學(xué)的諾姆 · 埃爾吉斯提出了一個(gè)實(shí)用的算法，成功找到了許多較小整數的立方和算式。
2015 年，數學(xué)家蒂姆 · 布朗寧發(fā)布了一段解釋該問(wèn)題的視頻。當時(shí)小于 100 的整數幾乎都被解決，只剩下 33、42 和 74 這三個(gè)數。
2019 年 9 月，數學(xué)家 Andrew Sutherland 和 Andrew Booker 破解了 100 以?xún)茸匀粩档淖詈笠粋€(gè)難關(guān)——42。
之后短短數周時(shí)間，他們又解決了一個(gè)更大的難題：找到了自然數 3 的第 3 個(gè)三立方數和解。
自然數 3 的又一個(gè)三立方數和解
對于 x^3+y^3+z^3 = 3，恐怕連高中生都能給出 x、y、z 的解：
那么，還有沒(méi)有其他解呢？
這個(gè)問(wèn)題困擾了數學(xué)家幾十年。1953 年，數學(xué)家莫德?tīng)柼岢鰡?wèn)題：對于自然數 3，是否存在其他解？
Sutherland 表示：“這更像是莫德?tīng)柊l(fā)起的一個(gè)挑戰。解決這個(gè)問(wèn)題的有趣之處并不是求出特定解，而是更好地了解這些公式的求解難度。這是我們用來(lái)衡量自己的標準?！?/p>
自 1953 年莫德?tīng)枓伋鲞@個(gè)問(wèn)題后，60 多年都沒(méi)人發(fā)現答案。直到 2019 年，Andrew Sutherland 和 Andrew Booker 破解了 42 的三立方數和解，并很快找到了 3 的第三個(gè)解。
這一發(fā)現直接回答了莫德?tīng)柕膯?wèn)題?；蛟S更重要的是，這個(gè)包含 21 位數字的解直到 2019 年才被發(fā)現，說(shuō)明對于 3 或其他自然數還存在更多解。
“莫德?tīng)柕膯?wèn)題太難了，因此數學(xué)和計算社區對此曾經(jīng)存在嚴重懷疑?！盨utherland 說(shuō)道，“解包含的數字如此之大。但是找到這個(gè)解之后，我相信肯定存在更多其他解?！?/p>
如何求解？
為了找出 42 和 3 的解，該團隊一開(kāi)始使用現有的算法，將三立方數和方程轉換為他們認為更易于求解的形式：
這一算法最初由英國數學(xué)家羅杰希思 - 布朗提出，根據他的猜想，每個(gè)適當的 k 應該有無(wú)限多個(gè)解。該團隊通過(guò)將 x+y 表示為單個(gè)參數 d 進(jìn)一步修改了這一算法。然后他們將兩邊都除以 d 并保留余數，進(jìn)一步簡(jiǎn)化了問(wèn)題表示。
牛津大學(xué)數學(xué)家羅杰希思 - 布朗。
Sutherland 解釋道：“你現在可以將 k 視為 z 的立方根，并對 d 進(jìn)行取模運算。因此，想象一下在算法系統中只關(guān)心對 d 取模運算后的余數會(huì )怎么樣。我們嘗試計算 k 的立方根?！?/p>
有了這個(gè)更簡(jiǎn)潔的方程，要想找到 k=3 時(shí) x, y 和 z 的最終解，研究人員只需找到 d 和 z 的值即可。但是，他們必須搜索的數字空間無(wú)限大。因此，研究人員使用數學(xué)“篩分”法大大減少 d 的可能解的空間，進(jìn)而優(yōu)化了該算法。
Sutherland 表示：“這涉及一些非常先進(jìn)的數論。使用我們已知的數域結構，來(lái)避免搜尋我們不需要考慮的空間?！?/p>
全球 40 多萬(wàn)臺計算機助力 42 和 3 的三立方數和解
該團隊還開(kāi)發(fā)了一些可以將算法搜索高效地分解為數十萬(wàn)個(gè)并行處理流的方法。如果僅在一臺計算機上運行該算法，則需要花費數百年的時(shí)間才能找到 k=3 的解。而將該求解過(guò)程分割為數百萬(wàn)個(gè)較小任務(wù)后，每個(gè)任務(wù)可以在單個(gè)計算機上獨立運行，這樣該團隊可以進(jìn)一步加速搜索進(jìn)程。
2019 年 9 月，研究人員通過(guò) Charity Engine 項目將他們的計劃付諸實(shí)踐，該項目旨在利用閑置的家庭計算機來(lái)共同求解數學(xué)難題，任何個(gè)人計算機都可以免費下載該項目。當時(shí)，Charity Engine 網(wǎng)格涵蓋全球超 40 萬(wàn)臺計算機。作為 Charity Engine 新軟件平臺的測試，Booker 和 Sutherland 可以在該網(wǎng)格上運行其算法。
Charity Engine 項目。圖源：https://thenextweb.com/apps/2011/12/14/charity-engine-donate-spare-pc-power-and-stand-a-chance-to-win-a-1m-invites/
Sutherland 表示：“Charity Engine 網(wǎng)格中每臺計算機的任務(wù)是尋找素因數在此范圍內的 d 值，但受到其他條件的約束。此外我們必須搞清楚如何將求解過(guò)程分解為大約 400 萬(wàn)個(gè)任務(wù)，每臺計算機大約花費 3 個(gè)小時(shí)來(lái)完成一個(gè)任務(wù)?！?/p>
很快，全球網(wǎng)格返回了 K=42 的首個(gè)解，并在兩周后，研究人員證實(shí)找到了 k=3 的第 3 個(gè)解。他們在 T 恤上打印出了這一里程碑式的解。
K=3 存在第 3 個(gè)三立方和解的事實(shí)表明，Heath-Brown 最初的猜想是正確的，除了這一最新解之外，還有無(wú)窮多個(gè)解。羅杰希思 - 布朗還預測，解之間的空間隨搜索范圍呈指數增長(cháng)。例如，x, y 和 z 的第 4 個(gè)解可能不再是 21 位數，可能是難以置信的 28 位數。
對此，Sutherland 表示：“每個(gè)新解所需的工作量會(huì )增加 1000 萬(wàn)倍。因此，第 4 個(gè)解或許需要 1000 萬(wàn) ×40 萬(wàn)臺計算機才能找到，甚至還不一定夠。我不知道能否找到第 4 個(gè)解，但我確信它始終就在那里?！?/p>
參考鏈接：
https://news.mit.edu/2021/solution-3-sum-cubes-puzzle-0311
https://math.mit.edu/~drew/Waterloo2019.pdf
https://www.ituring.com.cn/book/tupubarticle/34408
本文來(lái)自微信公眾號：機器之心（ID：almosthuman2014）
聯(lián)系客服
