圖片來(lái)源@全景視覺(jué)

鈦媒體注：本文來(lái)自于新智元（ID：AI_era），來(lái)源：quantamagazine，編輯：大明、小芹，鈦媒體經(jīng)授權(quán)發(fā)布。

任取一個(gè)正整數(shù)，如果是偶數(shù)，將其除以2。如果是奇數(shù)，將其乘以3再加1，然后重復(fù)這個(gè)過(guò)程，最后結(jié)果都是1。

這個(gè)問(wèn)題就是著名的“克拉茨猜想”。它幾乎可以說(shuō)是數(shù)學(xué)史上未解問(wèn)題中表達(dá)形式最簡(jiǎn)單的一個(gè)，也因此成為數(shù)學(xué)這棵參天大樹(shù)上最誘人的那顆果實(shí)。

不少資深數(shù)學(xué)家警告稱，這個(gè)問(wèn)題簡(jiǎn)直有毒，堪稱魅惑十足的“海妖之歌”：你走進(jìn)來(lái)就再也出不去，再也無(wú)力做出其他任何有意義的成果。密歇根大學(xué)數(shù)學(xué)家、克拉茨猜想問(wèn)題專家Jeffrey Lagarias表示：“這是一個(gè)危險(xiǎn)的問(wèn)題，很多人為其如癡如醉，但目前看真的不可能解決。”

但不信邪的人總是有的。陶哲軒就是其中之一，他已經(jīng)取得了迄今為止在克拉茨猜想問(wèn)題上走的最遠(yuǎn)的成果。

9月8日，陶哲軒在個(gè)人博客上貼出了一份證明，表明了至少對(duì)絕大部分自然數(shù)，克拉茨猜想都是正確的。盡管這份證明算不上是完整證明，但已經(jīng)算是在這個(gè)堪稱“有毒”的問(wèn)題上取得的重大進(jìn)展。

“我沒(méi)指望能完全解決這個(gè)問(wèn)題，但目前取得的進(jìn)展已經(jīng)超出了我的預(yù)期。”陶哲軒說(shuō)。

克拉茨猜想：最簡(jiǎn)單的“不可能解決”的問(wèn)題

克拉茨猜想據(jù)稱是上世紀(jì)30年代由德國(guó)數(shù)學(xué)家Lothar  Collatz提出的。但其具體出處不詳，已知的，從西拉古斯大學(xué)大學(xué)傳到貝爾實(shí)驗(yàn)室，再到芝加哥大學(xué)。因早期有眾多的傳播者，所以在傳播過(guò)程中，克拉茨猜想收獲了許多名字：3n+1猜想、奇偶?xì)w一猜想、烏拉姆(Ulam)問(wèn)題、角谷猜想等。

其表述形式之簡(jiǎn)單讓它聽(tīng)起來(lái)像是聚會(huì)上的一個(gè)游戲。對(duì)于任何一個(gè)正整數(shù)，如果是奇數(shù)，則將其乘以3并加1。如果是偶數(shù)，則將其除以2。不斷重復(fù)這個(gè)過(guò)程，最后會(huì)發(fā)生什么？

直覺(jué)上看，你可能會(huì)覺(jué)得最開(kāi)始的數(shù)字不同會(huì)影響最終得到的結(jié)果。也許某些數(shù)字為開(kāi)端，最后的結(jié)果是1，而以另外一些數(shù)字為開(kāi)端，則會(huì)趨于無(wú)窮大。

但是克拉茨預(yù)測(cè)并非如此。他推測(cè)，如果最開(kāi)始的數(shù)是正整數(shù)，重復(fù)這個(gè)過(guò)程的次數(shù)足夠多，則無(wú)論最開(kāi)始的數(shù)是多少，最終結(jié)果都將是1。這之后，1成為初始數(shù)，會(huì)陷入循環(huán)：1、4、2 、1、4，2，1……

多年以來(lái)，許多人都對(duì)克拉茲猜想的表述之簡(jiǎn)單（該猜想又被稱為著名的“ 3x +1問(wèn)題”）而對(duì)這個(gè)問(wèn)題深深著迷。目前，數(shù)學(xué)家們測(cè)試了幾百億億個(gè)數(shù)，結(jié)果克拉茨猜想全部是正確的。

“這個(gè)問(wèn)題看上去沒(méi)有任何理解門(mén)檻，你只要知道‘乘以3’和‘除以2’，就可以完全理解。數(shù)學(xué)家馬克·錢(qián)伯蘭（Marc Chamberland）說(shuō)，誘人之處正在于此。Chamberland曾經(jīng)自制了一段關(guān)于該問(wèn)題的YouTube熱門(mén)視頻，稱這個(gè)問(wèn)題為“最簡(jiǎn)單的不可能解決的問(wèn)題”。

以下是一個(gè)克拉茨猜想驗(yàn)證網(wǎng)頁(yè)，大家可以自己試試。

https://www.dcode.fr/collatz-conjecture

雖然克拉茨猜想的表述和理解都非常簡(jiǎn)單，但嚴(yán)格證明卻非常困難。

上世紀(jì)70年代，數(shù)學(xué)家證明，幾乎所有的克拉茨數(shù)列，即重復(fù)克拉茨猜想的計(jì)算過(guò)程中得到的數(shù)列，最后得到的數(shù)字都將小于第一個(gè)數(shù)字，顯然這是個(gè)不完全證明。但也有證據(jù)表明，幾乎所有克拉茨數(shù)列的最終值都在向1靠近。

從1994年以來(lái)，一直到陶哲軒今年取得新進(jìn)展之前，Ivan Korec保持著對(duì)這個(gè)問(wèn)題證明的最佳記錄，數(shù)列的最終值在逐步變小。但距離問(wèn)題的核心仍然有很大距離。

隨著時(shí)間的推移，很多數(shù)學(xué)家得出這樣的結(jié)論，即：克拉茨猜想證明問(wèn)題完全超出了當(dāng)前的理解范圍，因此最好將精力花在其他問(wèn)題上，因?yàn)樵倮^續(xù)下去也是徒勞。

南卡羅來(lái)納大學(xué)的喬舒亞·庫(kù)珀在一封電子郵件中說(shuō)：“克拉茨猜想是一個(gè)眾所周知的難題，以至于數(shù)學(xué)家傾向于在每次討論前都加上一個(gè)警告，以免浪費(fèi)時(shí)間對(duì)它進(jìn)行研究。”

意外的提示：陶哲軒從匿名網(wǎng)友留言獲啟發(fā)

早在40年前，Lagarias就對(duì)這個(gè)猜想深感興趣，當(dāng)時(shí)他還是一個(gè)學(xué)生。幾十年來(lái)，他一直充當(dāng)克拉茨猜想問(wèn)題非官方信息收集人。他整理了與該問(wèn)題相關(guān)的論文庫(kù)，并于2010年以《極限挑戰(zhàn)：3x+1問(wèn)題》為題將其中一些論文成集出版。

Lagarias說(shuō)：“現(xiàn)在，在我對(duì)這個(gè)問(wèn)題有了更多了解之后，我仍然覺(jué)得它是不可能解決的。”

陶哲軒通常不會(huì)在“不可能解決”的問(wèn)題上浪費(fèi)時(shí)間。2006年，他獲得了數(shù)學(xué)領(lǐng)域的最高榮譽(yù)“菲爾茲獎(jiǎng)”，被廣泛認(rèn)為是年輕一代中最杰出的數(shù)學(xué)家之一。他習(xí)慣于解決問(wèn)題，而不是追逐夢(mèng)想。

陶哲軒曾說(shuō)：“數(shù)學(xué)家這個(gè)頭銜實(shí)際上對(duì)職業(yè)生涯是有害的。它可能導(dǎo)致一個(gè)人沉迷于一些重量級(jí)問(wèn)題，這些問(wèn)題超出了任何人的能力，會(huì)浪費(fèi)很多時(shí)間。”

但陶哲軒也不是完全不碰這些問(wèn)題。每年，他都會(huì)選擇一個(gè)尚未解決的著名問(wèn)題中嘗試一兩天。多年來(lái)，他為解決克拉茨猜想問(wèn)題作了幾次嘗試，但都沒(méi)有成功。

今年8月，一位匿名讀者在他的個(gè)人博客上發(fā)表了評(píng)論，建議他嘗試去解決“幾乎所有”數(shù)字的克拉茨猜想，而不是嘗試完全解決。

陶哲軒說(shuō)：“我沒(méi)有回復(fù)，但這條留言確實(shí)讓我再次考慮了這個(gè)問(wèn)題。”

他意識(shí)到，Collatz猜想在某種程度上類似于一種方程式的形式，即偏微分方程，他正是這個(gè)領(lǐng)域取得了職業(yè)生涯中一些最重要的成果。

輸入和輸出：來(lái)自偏微分方程的啟示

偏微分方程可以用于模擬宇宙中許多最基本的物理過(guò)程，例如流體的演化或重力在時(shí)空中的波動(dòng)。它們發(fā)生在系統(tǒng)的未來(lái)位置（例如將石頭扔進(jìn)池塘后五秒鐘的狀態(tài)）取決于兩個(gè)或多個(gè)因素（例如水的粘度和速度）的影響的情況下。看上去，復(fù)雜的偏微分方程似乎與克拉茨猜想這樣的簡(jiǎn)單算術(shù)問(wèn)題無(wú)關(guān)。

但陶哲軒意識(shí)到，二者之間有相似之處。使用偏微分方程，也可以插入一些值，獲取其他值，再重復(fù)這一過(guò)程。所有這些都是為了了解系統(tǒng)的未來(lái)狀態(tài)。對(duì)于任何給定的偏微分方程，數(shù)學(xué)家都想知道，某些初始值最終會(huì)導(dǎo)致無(wú)窮大的輸出值，還是會(huì)產(chǎn)生有限值，而不管以什么值作為開(kāi)頭。

在陶哲軒看來(lái)，偏微分方程和克拉茨猜想具有相同的風(fēng)格。因此，他認(rèn)為研究偏微分方程的思路也可以應(yīng)用于克拉茨猜想的證明。

一種特別有用的技術(shù)涉及一種統(tǒng)計(jì)方法，可以用于研究少量初始值（例如，池塘中水的少量初始配置）的長(zhǎng)期行為，并以此出發(fā)推斷所有可能初始設(shè)置下的長(zhǎng)期行為。

如果引申到克拉茨猜想上，可以理解為從大量數(shù)字樣本開(kāi)始，目標(biāo)是研究在應(yīng)用克拉茨流程時(shí)這些數(shù)字的行為。如果樣本中接近100％的數(shù)字最終恰好等于1或非常接近1，您可能會(huì)得出結(jié)論，幾乎所有數(shù)字的行為方式都是相同的。

但是要使結(jié)論正確，必須非常仔細(xì)地構(gòu)建樣本。就像在總統(tǒng)選舉中構(gòu)建選民樣本一樣。為了從民調(diào)中準(zhǔn)確地推斷出整個(gè)人口的投票意愿，需要以正確比例對(duì)共和黨人、民主黨人，以男女同等的權(quán)重對(duì)樣本進(jìn)行加權(quán)。

數(shù)字具有自己的“人口統(tǒng)計(jì)學(xué)”特征。比如存在奇偶性、是3的倍數(shù)，或者數(shù)字之間通過(guò)其他微妙的方式體現(xiàn)彼此的不同。構(gòu)造數(shù)字樣本時(shí)，可以將其加權(quán)為包含某些種類、但不包含其他種類的數(shù)字。選擇的權(quán)重質(zhì)量越好，就越能得出關(guān)于整體數(shù)字的結(jié)論。

小心探尋數(shù)字加權(quán)，陶哲軒給出克拉茨猜想最強(qiáng)證明

陶哲軒所面臨的挑戰(zhàn)遠(yuǎn)比弄清楚如何用合適的權(quán)重創(chuàng)建一個(gè)初始數(shù)字樣本要困難得多。在Collatz過(guò)程的每一個(gè)步驟中，處理的數(shù)字都在變化。一個(gè)明顯的變化是，樣本中幾乎所有的數(shù)字都變小了。

另一個(gè)可能不那么明顯的變化是，這些數(shù)字可能會(huì)開(kāi)始聚集在一起。例如，你可以從一個(gè)均勻的分布開(kāi)始，比如從1到100萬(wàn)的數(shù)字。但是經(jīng)過(guò)五次Collatz迭代之后，這些數(shù)字很可能集中在數(shù)軸上的幾個(gè)小區(qū)間內(nèi)。換句話說(shuō)，你可能一開(kāi)始有一個(gè)很好的樣本，但是五步之后，它就完全扭曲了。

陶哲軒在一封電子郵件中說(shuō)：“通常情況下，人們會(huì)認(rèn)為迭代后的分布與最初的分布完全不同。”

陶哲軒的關(guān)鍵見(jiàn)解是找出如何在整個(gè)Collatz過(guò)程中選擇一個(gè)很大程度上保持原有權(quán)重的數(shù)字樣本。

例如，陶哲軒的初始樣本加權(quán)后不包含3的倍數(shù)，因?yàn)镃ollatz過(guò)程很快就排除了3的倍數(shù)。陶哲軒提出的其他一些權(quán)重更復(fù)雜。他把初始樣本的權(quán)重取為除以3后余數(shù)為1的數(shù)字，而不是除以3后余數(shù)為2的數(shù)字。

結(jié)果是，即使在Collatz過(guò)程繼續(xù)進(jìn)行時(shí)，陶哲軒的初始樣本仍然保持其特性。

“他找到了進(jìn)一步推進(jìn)這個(gè)過(guò)程的方法，這樣經(jīng)過(guò)一些步驟之后，你仍然知道發(fā)生了什么，”Soundararajan說(shuō)。“當(dāng)我第一次看到這篇論文時(shí)，我非常激動(dòng)，認(rèn)為它非常引人注目。”

陶哲軒使用這種加權(quán)技術(shù)證明了，幾乎所有的Collatz初始值(99%甚至更多)最終都達(dá)到一個(gè)非常接近1的值。這使他能夠得出99%的初始值大于1千萬(wàn)億的克拉茨數(shù)列，最終結(jié)果小于200的結(jié)論。 

可以說(shuō)，這是該猜想歷史上最強(qiáng)的證明結(jié)果。

Lagarias說(shuō)：“這是我們對(duì)這個(gè)問(wèn)題的了解取得的一大進(jìn)步。這肯定是很長(zhǎng)一段時(shí)間以來(lái)最好的結(jié)果。”

陶哲軒的方法幾乎肯定不能完全證明克拉茨猜想。原因是他的初始樣本在過(guò)程的每一步之后仍然有一點(diǎn)偏斜。只要樣本中仍然包含許多與1相距甚遠(yuǎn)的不同值，則偏差就很小。但隨著Collatz過(guò)程仍在繼續(xù)，樣本中的數(shù)字趨近于1，小的偏差效應(yīng)越來(lái)越明顯——類比來(lái)說(shuō)，民意調(diào)查中當(dāng)樣本容量很大時(shí)，一個(gè)輕微的誤算影響不大；但當(dāng)樣本量很小時(shí)，就會(huì)產(chǎn)生較大的影響。

要完全證明這個(gè)猜想，很可能需要另一種方法。因此，陶哲軒的工作既是勝利，也是對(duì)為克拉茨猜想著迷的數(shù)學(xué)家的一種警告：就在你以為自己可能已經(jīng)把問(wèn)題逼到了絕路的時(shí)候，它卻溜走了。

陶哲軒說(shuō)：“你可以盡可能接近克拉茨猜想，但要完全證明，目前仍然遙不可及。”

參考鏈接：

https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/

陶哲軒博客：

https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/

論文：

https://arxiv.org/abs/1909.03562