選自Quanta Magazine

作者：Erica Klarreich

機器之心編譯

編輯：魔王

在著名的埃爾德什等差數(shù)列猜想證明之路上，數(shù)學(xué)界可能又前進了一步。

埃爾德什等差數(shù)列猜想（Erd?s conjecture on arithmetic progressions），又稱埃爾德什 - 圖蘭猜想（Erd?s-Turan conjecture），是由匈牙利數(shù)學(xué)家、沃爾夫數(shù)學(xué)獎得主保羅 · 埃爾德什與保羅 · 圖蘭（Pál Turán）共同提出的關(guān)于調(diào)和發(fā)散數(shù)列的等差子序列的數(shù)論猜想。

該猜想的內(nèi)容是：

埃爾德什等差數(shù)列猜想內(nèi)容。（圖源：維基百科）

2004 年，陶哲軒和本 · 格林證明了該猜想的弱化版本。

最近，兩位數(shù)學(xué)家 Thomas Bloom 和 Olof Sisask 解決了這一著名猜想的第一大部分，即整數(shù)無窮數(shù)列一定包含長度至少為三的等差數(shù)列（如 26, 29, 32）。

埃爾德什一生中提出了數(shù)千個問題，但哪些數(shù)列包含「等差數(shù)列」這個問題是他的一生最愛。

「我認為很多人將該猜想看作埃爾德什的 NO. 1 問題，」劍橋大學(xué)數(shù)學(xué)系教授 Timothy Gowers 表示。他是 1998 年菲爾茲獎獲得者，曾花費大量時間試圖證明這一猜想?！噶钊烁吲d的是，一些加性組合研究者有志于探究該猜想?！?/p>

通常，越稠密的數(shù)列越有可能包含等差數(shù)列，因此埃爾德什提出了一種簡單的數(shù)列稠密度測試：求數(shù)列中所有數(shù)字的倒數(shù)和。如果數(shù)字多到可以令倒數(shù)和發(fā)散，則埃爾德什猜想該數(shù)列應(yīng)包含任意長度的等差數(shù)列，如等差三元組、四元組等。

最近，來自劍橋大學(xué)的 Thomas Bloom 和來自斯德哥爾摩大學(xué)的 Olof Sisask 發(fā)表論文，證明了這一猜想適用于等差三元組（如 5, 7, 9）。他們證明，只要數(shù)列中所有元素的倒數(shù)和發(fā)散，則它必然包含無窮多個等差三元組（即包含三個數(shù)字的等差數(shù)列）。

Thomas Bloom 和 Olof Sisask

「這一發(fā)現(xiàn)是這么多年來的標志性事件，這是一件大事。」加州理工學(xué)院 Nets Katz 教授說道。

質(zhì)數(shù)集合的倒數(shù)和是發(fā)散的。20 世紀 30 年代，Johannes van der Corput 使用質(zhì)數(shù)的特殊結(jié)構(gòu)表明，它們確實包含無窮多個等差三元組（如 17, 23, 29）。

但 Bloom 和 Sisask 的新發(fā)現(xiàn)意味著，在證明質(zhì)數(shù)數(shù)列包含無窮多個三元組時，無需掌握質(zhì)數(shù)的獨特結(jié)構(gòu)。你只需要知道，質(zhì)數(shù)的數(shù)量足夠多，足以使其倒數(shù)和發(fā)散，而這一點在幾個世紀之前就被數(shù)學(xué)家們發(fā)現(xiàn)了。

牛津大學(xué)數(shù)學(xué)研究所高級研究員 Tom Sanders 在一封郵件中表示：「Bloom 和 Sisask 的研究結(jié)果表明，即使質(zhì)數(shù)具備與以往完全不同的結(jié)構(gòu)，它們?nèi)匀荒軌虮ＷC擁有無窮多個等差數(shù)列?！?/p>

Bloom 和 Sisask 發(fā)表的論文長達 77 頁，這需要數(shù)學(xué)家花費一定的時間和精力認真閱讀和評審。不過，很多人樂觀地認為他們的證明是正確的?！高@個證明確實很像樣?！乖缙诠ぷ鳛檫@一結(jié)果奠定了基礎(chǔ)的 Nets Katz 表示。

Bloom 和 Sisask 的定理表明，只要數(shù)列足夠稠密，特定的模式就一定會出現(xiàn)。該發(fā)現(xiàn)符合牛津大學(xué) Sarah Peluse 對數(shù)學(xué)領(lǐng)域的基本口號：「完全的無序是不可能的?！梗ㄟ@句話最初出自數(shù)學(xué)家 Theodore Motzki。）

被掩蓋的「稠密性」

只要數(shù)列足夠稀疏，則使其不包含等差數(shù)列是件很簡單的事情。例如，對于序列 1, 10, 100, 1,000, 10,000, …（其倒數(shù)和為有盡小數(shù) 1.11111…）。這些數(shù)字的稠密度極速下降，你永遠無法從中找出一個長度 3 的等差數(shù)列。

你或許會思考，是否存在非常稠密但不包含等差數(shù)列的數(shù)集？

你可以從頭開始嘗試，使數(shù)列中所有數(shù)字無法形成一個等差數(shù)列。最后得到了序列 1, 2, 4, 5, 10, 11, 13, 14, …。第一眼看上去似乎很稠密，但是隨著數(shù)字越來越大，該數(shù)列變得非常稀疏，例如當?shù)竭_ 20 位數(shù)字時，只有大約 0.000009% 的數(shù)字出現(xiàn)在數(shù)列中。1946 年，F(xiàn)elix Behrend 提出了更稠密的示例，但是它們很快就變得稀疏了，數(shù)字到達 20 位時，數(shù)列中只出現(xiàn)了全部數(shù)字的 0.001%。

現(xiàn)在我們來看另一個極端。如果你的數(shù)列包含幾乎所有整數(shù)，那么它必然包含等差數(shù)列。

但是在這兩個極端之間是廣闊且神秘未知的中間領(lǐng)域。數(shù)列稀疏性達到什么程度，仍能確保數(shù)集包含等差數(shù)列呢？

埃爾德什提供了一個可能的答案。他認為倒數(shù)和可以用來揭示「稠密性」：最大數(shù)字為 N 的數(shù)列的稠密性至少逼近 1/N 的位數(shù)。也就是說，數(shù)列越來越稀疏是可以的，只要稀疏化速度足夠慢就行：如果數(shù)列中最大的數(shù)是 5 位數(shù)，則稠密性至少是 1/5；如果數(shù)列中存在 20 位數(shù)，則稠密性至少是 1/20，依此類推。

當這一稠密性條件得到滿足時，埃爾德什猜想，該數(shù)列應(yīng)包含無窮多個任意長度的等差數(shù)列。

1991 年 6 月，埃爾德什在劍橋大學(xué)授課。

1953 年，Klaus Roth 開始證明埃爾德什等差數(shù)列猜想。在三年后幫他獲得 1958 年菲爾茲獎的一項工作中，他構(gòu)建了一個可以確保存在等差三元組的稠密性函數(shù)，其稠密性沒有埃爾德什猜想得那么低，但是隨著數(shù)列越來越長，該值趨近于 0。Roth 的定理意味著數(shù)列稠密性將最終低于 1%，再低于 0.1%，再低于 0.01%…… 只要稠密性低于這些閾值的速度足夠慢，則該數(shù)列必然包含等差數(shù)列。

Roth 的方法依賴于這一事實：具備其所選稠密性的大多數(shù)數(shù)列「想要」包含等差數(shù)列，它們包含足夠多不同的數(shù)字對，這些數(shù)字對的中心值也屬于該數(shù)列，從而出現(xiàn)等差三元組。

棘手的部分在于如何將這一屬性從「大多數(shù)」泛化到「全部」數(shù)列，甚至那些結(jié)構(gòu)盡量避免等差數(shù)列的數(shù)列。

基于一個高度結(jié)構(gòu)化的數(shù)列，Roth 想到使用傅里葉變換映射其「頻譜」，從而蒸餾數(shù)列結(jié)構(gòu)。這可以檢測出數(shù)列中表現(xiàn)強烈的重復(fù)模式，也是 X 光片和無線電頻譜底層技術(shù)所涉及的數(shù)學(xué)知識。

一些頻率出現(xiàn)的時候要比別的頻率更加強烈，這些變體更突出了模式本身，例如強頻率可能表明數(shù)列包含更多奇數(shù)。如果是這樣，你只需專注于奇數(shù)，這樣你就可以得到比最初更加稠密的集合了。Roth 證明，經(jīng)過有限數(shù)量的蒸餾后，可以獲得足夠稠密的數(shù)字集合，且它們包含等差數(shù)列。

在過去的半個世紀中，Roth 的方法啟發(fā)了解析數(shù)論領(lǐng)域的許多發(fā)展。斯坦福大學(xué)數(shù)學(xué)系教授 Jacob Fox 表示，「這些是很有影響力的想法。」

從紙牌游戲中找等差數(shù)列

Roth 的觀點僅對最開始比較稠密的數(shù)集有效，否則重復(fù)的蒸餾只會使數(shù)集衰減。其他數(shù)學(xué)家逐漸發(fā)現(xiàn)一些方法，可以從 Roth 的方法中得到更多，但卻無法解決埃爾德什等差數(shù)列猜想中的稠密性問題。Fox 表示，「這似乎是很難跨越的檻兒?！?/p>

2011 年，Katz 和 Michael Bateman 發(fā)現(xiàn)了在更簡單設(shè)置下克服上述障礙的方法：在 Set 紙牌游戲中，尋找符合三元組模式的紙牌。他們發(fā)現(xiàn)，存在一種精確的方式，可以將匹配的 Set 三元組紙牌看作等差數(shù)列，而且就像在整數(shù)數(shù)列中那樣，你可以詢問放下哪部分紙牌才能確保找到至少一個三元組。

這個問題是整數(shù)數(shù)列對應(yīng)問題的簡化版模型，因此數(shù)學(xué)家希望 Bateman 和 Katz 的發(fā)現(xiàn)可以為證明埃爾德什等差數(shù)列猜想提供突破口，尤其是與其他近期進展結(jié)合之后。

在 Bateman 和 Katz 的論文發(fā)表后不久，Gowers 啟動了一個大規(guī)模線上合作項目——Polymath，進行此類嘗試。

但是，這個項目很快擱淺?！高@需要很高超的技術(shù)能力，這個項目更適合一兩個為此堅持了很久的人來執(zhí)行?！笹owers 表示。

幸運的是，Bloom 和 Sisask 出現(xiàn)并做了嘗試。最初，二人受到埃爾德什等差數(shù)列猜想中技術(shù)之美的吸引，開始各自思考該猜想?！高@是我最初涉及的研究問題之一?！筍isask 說道。

2014 年，Bloom 和 Sisask 聯(lián)手。2016 年，他們認為自己得到了解決方案。Bloom 甚至在一次講座中宣布了結(jié)果，不過后來發(fā)現(xiàn)其中一些論據(jù)站不住腳。于是他們繼續(xù)努力，深入探索 Bateman 和 Katz 方法的內(nèi)部原理，并最終提出了新的思路，能夠?qū)⑵溆^點從 Set 紙牌遷移到整數(shù)范疇。

Katz 表示，二人發(fā)表的新論文看起來「萬事俱備」，「我不相信他們之前的論斷，但我相信這次的結(jié)果。」

Fox 認為，Bloom 和 Sisask 的工作是「一項偉大的成就」。他和其他數(shù)學(xué)家急切地想要探索能否將這篇新論文中的技術(shù)應(yīng)用到其他問題中?！肝艺J為，這個方法將會產(chǎn)生巨大影響，」Fox 說道。

當然，這項工作距離完整地證明埃爾德什等差數(shù)列猜想還很遠。Bloom 和 Sisask 只證明了等差三元組的部分，還沒有證明更長的數(shù)列。

即使二人已經(jīng)解決掉了等差三元組問題，很多數(shù)學(xué)家仍將埃爾德什等差數(shù)列猜想看作「紅鯡魚」（即為分散注意力而提出的不相干事實或論點）。證明埃爾德什稠密性能夠確保等差三元組的存在很難，數(shù)學(xué)家懷疑使這一保障失效的稠密性或許更低，可能只比 Behrend 構(gòu)建的避免等差數(shù)列的數(shù)集稠密性稍高一點。

「我們并未完全解決該猜想，我們只是對此多了一點深刻認識。」Bloom 說道。

Fox 表示，Bloom 和 Sisask 或許已經(jīng)竭盡所能地推進當前的方法?！肝覀冃枰嬲男鹿ぞ?，能夠更好地挖掘出新東西?！笷ox 說道。但是他還表示：「現(xiàn)在或許并不是故事的結(jié)局?！?/p>

原文鏈接：https://www.quantamagazine.org/landmark-math-proof-clears-hurdle-in-top-erdos-conjecture-20200803/

Amazon SageMaker 是一項完全托管的服務(wù)，可以幫助開發(fā)人員和數(shù)據(jù)科學(xué)家快速構(gòu)建、訓(xùn)練和部署機器學(xué)習(xí) 模型。SageMaker完全消除了機器學(xué)習(xí)過程中每個步驟的繁重工作，讓開發(fā)高質(zhì)量模型變得更加輕松。

現(xiàn)在，企業(yè)開發(fā)者可以免費領(lǐng)取1000元服務(wù)抵扣券，輕松上手Amazon SageMaker，快速體驗5個人工智能應(yīng)用實例。

? THE END

轉(zhuǎn)載請聯(lián)系本公眾號獲得授權(quán)

投稿或?qū)で髨蟮溃篶ontent@jiqizhixin.com

原標題：《陶哲軒之后，有人在這個猜想的證明之路上又前進了一步》

閱讀原文