這篇文章內容翻譯自論文 Cracking the problem with 33,論文研究了方程 在一些小的
值的解掌呜,并首次將33寫成了3個整數(shù)的立方和。完成中文可以查看項目 qiwihui/cracking-the-problem-with-33翩肌。截止到目前念祭,100以內的自然數(shù)就剩下42還沒有找到關于立方和的整數(shù)解了粱坤!
Answer to the Ultimate Question of Life, the Universe, and Everything. -- 42
以下是論文正文翻譯:
解決33問題
作者:ANDREW R. BOOKER
摘要 受到Tim Browning和Brady Haran的 Numberphile 視頻"未解決的33問題"的啟發(fā),我們研究了方程 在一些小的
值的解株旷。 我們找到了
的第一個已知解晾剖。
1. 簡介
令 為正整數(shù),其中
循头。 然后Heath-Brown [HB92] 推測 有無限多的三元組
滿足
早在1954年就開始對(1)進行各種數(shù)值研究 [MW55]盒使;請參閱 [BPTYJ07]少办,了解截至2000年的這些研究的歷史英妓。 自那時起進行的計算由于Elkies [Elk00] 而被算法所主導。我們所知道的最新內容是Huisman [Hui16] 的論文腿倚, 該論文確定了(1)的所有解敷燎,其中 且
硬贯。 特別是,Huisman報告說除了13個
的值以外的所有解決方案都是已知的:
Elkies的算法通過使用格基減少(lattice basis reduction)在Fermat曲線 附近尋找有理點來工作墨状;它非常適合同時找到許多
值的解肾砂。 在本文中,我們描述了一種在k值確定時更有效的不同方法源葫。 它的優(yōu)點是可以找到所有具有 最小 坐標界限的解息堂,而不是Elkies算法中的最大坐標床未。 這總是產生搜索范圍的非平凡的擴張(nontrivial expansion)薇搁,因為除了可以單獨考慮的有限多個例外之外啃洋,還有
此外,根據經驗,通常情況是其中一個變量比其他變量小得多貌踏,因此我們希望實際上增益更大祖乳。
我們的策略類似于一些早期的方法(特別參見 [HBLtR93]眷昆,[Bre95],[KTS97] 和 [BPTYJ07])帅刊, 并且基于觀察: 的任何解都具有
作為一個因子赖瞒。 相對于早期研究栏饮,我們的主要貢獻是注意到,通過一些時間空間權衡芒划,運行時間在高度邊界內非常接近線性, 并且在現(xiàn)代64位計算機上實現(xiàn)時非常實用涮帘。
更詳細地說,假設 是(1)的解立莉,并且不失一般性,假設
刹淌。 然后我們有
如果 則
有勾,并且
的每個值都產生一個解。 否則籍琳,設
喝峦, 我們看到
可以除
并且
得到
因此,給定 的候選值眉踱,通過遍歷
的所有除數(shù)册烈,有一個有效的程序來查找
和
的所有相應值匿情。這個基本算法在假設整數(shù)分解的時間復雜度的標準啟發(fā)式(standard heuristics)下,已經能在 時間
內找到滿足
的所有解驾中。 在下一節(jié)中,我們將解釋如何避免因子分解并更有效地實現(xiàn)相同目的。
感謝 感謝Roger Heath-Brown提供了有用的意見和建議侄柔。
2. 方法
為了便于表示暂题,我們假設 薪者;請注意,這適用于(2)中的所有
悬槽。 由于上述基本算法對于尋找小解是合理的初婆,因此我們將假設
屑咳。 此外兆龙,如果我們將(1)專門用于
的解详瑞,那么我們得到Thue方程
,這是有效可解的计寇。 使用 PARI/GP [The18] 中的Thue求解器番宁,我們驗證了(2)中的
不存在這樣的解蝶押。 因此棋电,我們可以進一步假設
。
由于 于未,我們有
同樣烘浦,因為 和
, 我們有
片习。將(1)的兩邊乘以
藕咏,我們得到
令 饥悴,并且
西设。 如果
則
由于 , 這與我們的假設不相容禽绪,即
和
印屁。 因此我們必然有
雄人。
接下來,減少(4)模3并回想我們的假設 ,我們有
設 使得
正罢。 然后翻具,由于每個立方數(shù)都與
或
相等裆泳, 我們必然有
, 因此
民泵。 基于(3),當且僅當
以及
是平方數(shù)時鳞尔, 我們得到(1)的解莽鸿。
總之,找到(1)的所有解并且滿足 乒疏,
和
怕吴,對于每個與3互質的
转绷,解決以下系統(tǒng)就足夠了:
我們解決這個問題的方法很簡單:我們通過它們的主要因子分解遞歸地計算 的值, 并應用中國剩余定理來將
的解減少到素數(shù)模冪的情況下煞肾, 其中標準算法可以適用籍救。設
表示
模
的立方根數(shù)闪萄。通過標準分析估計桃煎,由于
不是立方數(shù)为迈,我們有
啟發(fā)式地葫辐,計算對所有素數(shù) 的
的解 可以用
上的整數(shù)在
算術運算來完成; 見例如 [[NZM91]剂陡,§2.9鸭栖,練習8]中描述的算法晕鹊。假設這一點溅话,可以看出, 使用Montgomery的批量反轉技巧[[Mon87]循狰,§10.3.1],計算對所有正整數(shù)
的
的根的剩余工作可以再次用
算術運算完成关炼。
因此儒拂,我們可以在線性時間內計算滿足(5)的第一行的所有 社痛, 作為算術進展(arithmetic progressions)的并集斩箫。為了檢測最后一行的解乘客,有一個快速的方法來確定
是一個平方數(shù) 至關重要浪默。我們首先注意到對于固定
,這種情況減少到在橢圓曲線上找到積分點花竞; 特別是厌蔽,令
和
,從(3)中我們看到(X,Y)位于Mordell曲線上
因此,對于固定 吃警,存在至多有限多個解安券,并且它們可以被有效地約束。 對于
的一些小值,找到(6)上的所有積分點并檢查是否產生任何滿足(1)的解是切實可行的。 例如锹淌,使用Magma[[BCFS18]烟号,§128.2.8]中的積分點函數(shù)(functionality),我們驗證了如(2)中的
和
情況下沒有解, 除了
。
接下來我們自然注意到一些同余和可分性約束:
引理 設 為(5)的解,設
為素數(shù)邑狸, 設
硅堆,
。則
(i) ;
(ii) 如果 則
;
(iii) 如果 則
;
(iv) 如果 則
。
證明 令 , 令
,我們有
, 觀察到
,模27,我們有
這消失了模9,所以為了使 成為平方數(shù),它也必須消除mod 27。 于是
減少(1)模2我們得到 ,這得到(i)。
接下來設 和
,這樣就有
如果 則
, 但是當
時這是不可能的,因為
不是
的平方模。因此,在這種情況下我們必須
。
接下來假設 。 我們考慮以下情況丹墨,涵蓋所有可能性:
- 若
則
英染,那么
闪金。
- 若
且
恃疯, 則
,那么
。
- 若
則
。
- 如果
且
則
,這是不可能的。
因此,在任何情況我們得出結論 联四。
最后伟姐,假設 和
。如果
則無需證明的,所以假設不然。 由于
,我們必須有
,因為
通過部分(iii)得出 , 因此
。
因此,一旦 的殘差類(residue class)固定, 則其殘差模
是確定的散址。還要注意,條件(ii)和(iii)對于測試
是有效的。
然而,即使有這些優(yōu)化含滴,也有 對
滿足(5)的第一行和引理的結論(i)和(iv)。 因此,為了實現(xiàn)比
更好的運行時間遗菠,需要從一開始就消除一些
值叭喜。 我們通過標準的時間空間交換來實現(xiàn)這一目標。確切地說,設置
腕够, 并且讓
是區(qū)間
之間的素數(shù)的乘積蒿囤。 根據素數(shù)定理,我們得到
。如果
是平方數(shù), 那么對于任意素數(shù)
我們有
其中 。 當
時, 我們首先為每個殘差類
計算該函數(shù), 并且僅選擇對于每個
滿足(7)的那些殘基。 由Hasse約束,允許的殘差的數(shù)量最多為
因此,要考慮的 值的總數(shù)最多為
對于沒有以這種方式消除的 柏副,我們遵循類似的策略, 其中一些其他輔助模
由較大的素數(shù)組成,以加速平方測試玛歌。 我們預先計算模為
的立方數(shù)表和Legendre符號模
, 因此將測試(7)簡化為了表查找。只有當所有這些測試都通過時吞歼, 我們才能在多精度算術中計算
并應用一般的平方檢驗,這種情況對于一小部分候選值來說都是如此睦擂。 事實上摆马,我們期望Legendre測試的數(shù)量平均有限,所以總的來說乓搬, 找到所有解決方案的
應該要求不超過
次表查找和對
中整數(shù)的算術運算。
因此,當 符合機器字大小時,我們預計運行時間幾乎是線性的着降,這就是我們在實踐中觀察到的
发侵。
3. 實現(xiàn)
我們在C中實現(xiàn)了上述算法,其中有一些內聯(lián)匯編程序來源于由Ben Buhrow [Buh19] 編寫的Montgomery算法 [Mon85], 以及Kim Walisch的用于枚舉素數(shù)的 primesieve 庫 [Wal19]。
該算法自然地在具有超過 的素因子和 具有
-平滑的素數(shù)的
的值之間分配。 前一組
消耗超過運行時間的三分之二遂鹊,但更容易并行化。 我們在布里斯托大學高級計算研究中心的大規(guī)模并行集群Bluecrystal Phase 3上運行了這一部分赋咽。 對于平滑的
宦赠,我們使用了一個單獨的32核和64核節(jié)點的小集群毡琉。
我們搜索了滿足 和
的(1)的解丐谋,找到了以下結果:
總計算在三個星期的實際時間中大約使用了15個核年吏饿。
參考文獻
(略)
School of Mathematics, University of Bristol, University Walk, Bristol, BS8 1TW, United Kingdom
E-mail address: andrew.booker@bristol.ac.uk