面對數學史上最簡單的未解之謎,陶哲軒給出了幾十年來最重要的證明

編者按：本文來自微信公眾號「新智元」（ID：AI_era），來源：quantamagazine，編輯：大明、小芹，36氪經授權發布。

任取一個正整數，如果是偶數，將其除以2。如果是奇數，將其乘以3再加1，然後重複這個過程，最後結果都是1。

這個問題就是著名的「克拉茨猜想」。它幾乎可以說是數學史上未解問題中表達形式最簡單的一個，也因此成為數學這棵參天大樹上最誘人的那顆果實。

不少資深數學家警告稱，這個問題簡直有毒，堪稱魅惑十足的「海妖之歌」：你走進來就再也出不去，再也無力做出其他任何有意義的成果。密西根大學數學家、克拉茨猜想問題專家Jeffrey Lagarias表示：「這是一個危險的問題，很多人為其如痴如醉，但目前看真的不可能解決。」

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

9月8日，陶哲軒在個人博客上貼出了一份證明，表明了至少對絕大部分自然數，克拉茨猜想都是正確的。儘管這份證明算不上是完整證明，但已經算是在這個堪稱「有毒」的問題上取得的重大進展。

「我沒指望能完全解決這個問題，但目前取得的進展已經超出了我的預期。」陶哲軒說。

克拉茨猜想：最簡單的「不可能解決」的問題

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

其表述形式之簡單讓它聽起來像是聚會上的一個遊戲。對於任何一個正整數，如果是奇數，則將其乘以3並加1。如果是偶數，則將其除以2。不斷重複這個過程，最後會發生什麼？

直覺上看，你可能會覺得最開始的數字不同會影響最終得到的結果。也許某些數字為開端，最後的結果是1，而以另外一些數字為開端，則會趨於無窮大。

但是克拉茨預測並非如此。他推測，如果最開始的數是正整數，重複這個過程的次數足夠多，則無論最開始的數是多少，最終結果都將是1。這之後，1成為初始數，會陷入循環：1、4、2 、1、4，2，1……

多年以來，許多人都對克拉茲猜想的表述之簡單（該猜想又被稱為著名的「 3x +1問題」）而對這個問題深深著迷。目前，數學家們測試了五百億個數，結果克拉茨猜想全部是正確的。

「這個問題看上去沒有任何理解門檻，你只要知道『乘以3』和『除以2』，就可以完全理解。數學家馬克·錢伯蘭（Marc Chamberland）說，誘人之處正在於此。Chamberland曾經自製了一段關於該問題的YouTube熱門視頻，稱這個問題為「最簡單的不可能解決的問題」。

以下是一個克拉茨猜想驗證網頁，大家可以自己試試。

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

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

上世紀70年代，數學家證明，幾乎所有的克拉茨數列，即重複克拉茨猜想的計算過程中得到的數列，最後得到的數字都將小於第一個數字，顯然這是個不完全證明。但也有證據表明，幾乎所有克拉茨數列的最終值都在向1靠近。

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

隨著時間的推移，很多數學家得出這樣的結論，即：克拉茨猜想證明問題完全超出了當前的理解範圍，因此最好將精力花在其他問題上，因為再繼續下去也是徒勞。

南卡羅來納大學的喬舒亞·庫珀在一封電子郵件中說：「克拉茨猜想是一個眾所周知的難題，以至於數學家傾向於在每次討論前都加上一個警告，以免浪費時間對它進行研究。」

意外的提示：陶哲軒從匿名網友留言獲啟發

早在40年前，Lagarias就對這個猜想深感興趣，當時他還是一個學生。幾十年來，他一直充當克拉茨猜想問題非官方信息收集人。他整理了與該問題相關的論文庫，並於2010年以《極限挑戰：3x+1問題》為題將其中一些論文成集出版。

Lagarias說：「現在，在我對這個問題有了更多了解之後，我仍然覺得它是不可能解決的。」

陶哲軒通常不會在「不可能解決」的問題上浪費時間。2006年，他獲得了數學領域的最高榮譽「菲爾茲獎」，被廣泛認為是年輕一代中最傑出的數學家之一。他習慣於解決問題，而不是追逐夢想。

陶哲軒曾說：「數學家這個頭銜實際上對職業生涯是有害的。它可能導致一個人沉迷於一些重量級問題，這些問題超出了任何人的能力，會浪費很多時間。」

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

今年8月，一位匿名讀者在他的個人博客上發表了評論，建議他嘗試去解決「幾乎所有」數字的克拉茨猜想，而不是嘗試完全解決。

陶哲軒說：「我沒有回覆，但這條留言確實讓我再次考慮了這個問題。」

他意識到，Collatz猜想在某種程度上類似於一種方程式的形式，即偏微分方程，他正是這個領域取得了職業生涯中一些最重要的成果。

輸入和輸出：來自偏微分方程的啟示

偏微分方程可以用於模擬宇宙中許多最基本的物理過程，例如流體的演化或重力在時空中的波動。它們發生在系統的未來位置（例如將石頭扔進池塘後五秒鐘的狀態）取決於兩個或多個因素（例如水的粘度和速度）的影響的情況下。看上去，複雜的偏微分方程似乎與克拉茨猜想這樣的簡單算術問題無關。

但陶哲軒意識到，二者之間有相似之處。使用偏微分方程，也可以插入一些值，獲取其他值，再重複這一過程。所有這些都是為了了解系統的未來狀態。對於任何給定的偏微分方程，數學家都想知道，某些初始值最終會導致無窮大的輸出值，還是會產生有限值，而不管以什麼值作為開頭。

在陶哲軒看來，偏微分方程和克拉茨猜想具有相同的風格。因此，他認為研究偏微分方程的思路也可以應用於克拉茨猜想的證明。

一種特別有用的技術涉及一種統計方法，可以用於研究少量初始值（例如，池塘中水的少量初始配置）的長期行為，並以此出發推斷所有可能初始設置下的長期行為。

如果引申到克拉茨猜想上，可以理解為從大量數字樣本開始，目標是研究在應用克拉茨流程時這些數字的行為。如果樣本中接近100％的數字最終恰好等於1或非常接近1，您可能會得出結論，幾乎所有數字的行為方式都是相同的。

但是要使結論正確，必須非常仔細地構建樣本。就像在總統選舉中構建選民樣本一樣。為了從民調中準確地推斷出整個人口的投票意願，需要以正確比例對共和黨人、民主黨人，以男女同等的權重對樣本進行加權。

數字具有自己的「人口統計學」特徵。比如存在奇偶性、是3的倍數，或者數字之間通過其他微妙的方式體現彼此的不同。構造數字樣本時，可以將其加權為包含某些種類、但不包含其他種類的數字。選擇的權重質量越好，就越能得出關於整體數字的結論。

小心探尋數字加權，陶哲軒給出克拉茨猜想最強證明

陶哲軒所面臨的挑戰遠比弄清楚如何用合適的權重創建一個初始數字樣本要困難得多。在Collatz過程的每一個步驟中，處理的數字都在變化。一個明顯的變化是，樣本中幾乎所有的數字都變小了。

另一個可能不那麼明顯的變化是，這些數字可能會開始聚集在一起。例如，你可以從一個均勻的分布開始，比如從1到100萬的數字。但是經過五次Collatz迭代之後，這些數字很可能集中在數軸上的幾個小區間內。換句話說，你可能一開始有一個很好的樣本，但是五步之後，它就完全扭曲了。

陶哲軒在一封電子郵件中說：「通常情況下，人們會認為迭代後的分布與最初的分布完全不同。」

陶哲軒的關鍵見解是找出如何在整個Collatz過程中選擇一個很大程度上保持原有權重的數字樣本。

例如，陶哲軒的初始樣本加權後不包含3的倍數，因為Collatz過程很快就排除了3的倍數。陶哲軒提出的其他一些權重更複雜。他把初始樣本的權重取為除以3後餘數為1的數字，而不是除以3後餘數為2的數字。

結果是，即使在Collatz過程繼續進行時，陶哲軒的初始樣本仍然保持其特性。

「他找到了進一步推進這個過程的方法，這樣經過一些步驟之後，你仍然知道發生了什麼，」Soundararajan說。「當我第一次看到這篇論文時，我非常激動，認為它非常引人注目。」

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

可以說，這是該猜想歷史上最強的證明結果。

Lagarias說：「這是我們對這個問題的了解取得的一大進步。這肯定是很長一段時間以來最好的結果。」

陶哲軒的方法幾乎肯定不能完全證明克拉茨猜想。原因是他的初始樣本在過程的每一步之後仍然有一點偏斜。只要樣本中仍然包含許多與1相距甚遠的不同值，則偏差就很小。但隨著Collatz過程仍在繼續，樣本中的數字趨近於1，小的偏差效應越來越明顯——類比來說，民意調查中當樣本容量很大時，一個輕微的誤算影響不大；但當樣本量很小時，就會產生較大的影響。

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

陶哲軒說：「你可以儘可能接近克拉茨猜想，但要完全證明，目前仍然遙不可及。」

參考連結：

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