這篇文章內容翻譯自論文 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