網絡論壇 4chan 以宅文化聞名，然而一個匿名網友多年前發布的帖子裡竟然包含了優雅的數學證明。最近這條證明被重新發現，數學家們對它進行了驗算，並在最終的論文中將“4chan 匿名網友”列為第一作者。
圖片來源：Pixabay
來源Quanta Magazine
撰文 Erica Klarreich
編譯 戚譯引
2011 年 9 月 16 日，一名動漫愛好者在 4chan 上提出了一個數學問題，討論動漫《涼宮春日的憂鬱》的觀看次序。這部動漫的第一季包含時間旅行劇情，最初以非時間線性順序播出，重播和 DVD 版也都采取了不同的順序。粉絲們在網上交流最佳的觀看順序，而有位 4chan 網友提問：要想以每一種可能的順序觀看這部劇集，那麽播放列表的最短長度是多少？
一小時之內，有匿名網友提交了答案——這不是一個完整的解答，而是所需的最少劇集數量的下界（lower bound）。論證中給出了對於任何數量的劇集的計算方式，並表明對於包含 14 集的《涼宮春日的憂鬱》第一季，觀眾需要至少觀看 93,884,313,611 集，才能看到所有可能的順序。“請檢查（證明），看看有沒有什麽可能的漏洞，”這個匿名網友寫道。
七年來，這個證明並未進入數學界的視線——顯然當時只有一名專業的數學家看到了它，而且他沒有仔細檢查。直到上個月，它才迎來了命運的轉折點。澳大利亞科幻作家格雷格·伊根（Greg Egan）證明了所需劇集數量的上界（upper bound），重新引發了數學家對這個問題的興趣，並讓 2011 年那個匿名發布的下界證明也得到了關注。這兩個證明都被視為重要的研究進展，為解開一個困擾了數學家至少 25 年的問題提供了啟發。
數學家們很快驗證，伊根的上界和匿名網友計算的下界適用於任何長度的集合。數據可視化公司 Kiln 的一名數學家羅賓·休斯頓（Robin Houston）和馬凱特大學（Marquette University）的傑伊·潘通（Jay Pantone）分別獨立驗證了 4chan 匿名網友的工作。“要驗證這個證明是對是錯花了不少工夫，”潘通說，因為證明的關鍵思想並沒有得到特別明確的表達。
如今，休斯頓、潘通和弗羅裡達大學（University of Florida）的文斯·維特（Vince Vatter）共同發表了一份正式的證明，他們在論文中將“4chan 匿名網友”列為第一作者。
休斯頓說：“如此優雅地證明了一個不為人知的問題，而且還出現在這樣一個不太可能的地方，這種情況還真奇怪。”
排列之城
如果一部劇集只有 3 集，那麽它有 6 種可能的觀看次序：123、132、213、231、312 和 321。你可以把這六種次序連起來，得到一個長度為 18 集的播放列表，其中包含了所有可能的次序，但還有一種更加高效的方式，就是 123121321（共 9 集）。這樣的序列包含了一個具備 n 個元素的集合中所有可能的排列（permutation），叫做超排列（superpermutation）。
1993 年，丹尼爾·艾什洛克（Daniel Ashlock）和詹內特·蒂洛森（Jenett Tillotson）發現，如果觀察n取不同值的超排列，我們很快會發現其中的規律和階乘（factorial）有關。階乘寫作n!，指所有小於或等於 n 的正整數的乘積（例如 4! = 4 × 3 × 2 × 1）。
如果某個劇集只有 1 集，那麽最短的超排列的長度就是 1!。對於包含 2 集的劇集，最短的超排列（121）的長度是 2! + 1!。在 3 集的情況下（例如前面的案例），最短的長度為 3! + 2! + 1!；而到了 4 集的時候，最短的序列是123412314231243121342132413214321，序列長度是 4! + 3! + 2! + 1!。超排列的階乘規律變成了一種經驗智慧（儘管沒人能證明它適用於所有的 n），並且數學家後來對 n=5 的情形進行了驗證。
要體現 5 個元素所有可能的排列，序列的最小長度是 5! + 4! + 3! + 2! + 1! = 153。| 圖片來源：Pixabay
直到 2014 年，休斯頓證明這條規律在 n=6 時不成立，讓數學家嚇了一跳。按照階乘計算，以每一種可能的順序觀看6部劇集，播放列表至少包含 873 集，然而休斯頓找到了一種辦法，讓它變成了 872 集。而且，由於有一種簡單的方式能夠將 n 個元素的較短超排列轉換成 n+1 個元素的較短超排列，休斯頓的案例說明，階乘規律對所有 n>6 的情況都不再適用。
休斯頓的工作將超排列問題進行了重構，將其轉換成著名的旅行推銷員問題（traveling salesman problem），即尋找穿過一系列城市的最短路線。具體而言，超排列與“不對稱”旅行推銷員問題有關，即連接兩個城市的路線需要收費（不同方向收費可能不同），此時推銷員的目標是找到穿過所有城市的最便宜的路線。
這個轉換過程很簡單。假設每種排列都是一座“城市”，再想象連接兩種排列的路線。在超排列問題中，我們希望能夠得到能夠包含所有可能排列的最短的序列，所以我們的目標是在各個排列之間“旅行”，每次旅行都會對開始的排列加上幾個字節。因此，定義每條路線的“路費”為需要在上一個排列後面添加的字節數，例如在 n=3 的情況下，從 231 到 312 花費 1 美元，因為我們只要在 231 後面加上一個 2，就能得到 312。按照這樣的設定，連接城市之間開支最少的路線就對應了最短的超排列。
圖片來源：Lucy Reading-Ikkanda/Quanta Magazine / 翻譯：科研圈
這種轉換意味著休斯頓可以將解答旅行推銷員問題的算法拿來解決超排列問題。旅行推銷員問題是一個著名的 NP 困難問題，也就是說沒有一種有效的算法能夠適用於所有的情況。但是，有的算法可以高效地解決一部分情況下的問題，而另一些算法能夠計算出足夠接近的答案。休斯頓採用了後者，計算出了那個長度為 872 的超排列。
由於他算出的只是一個近似解，這也許並非最好的超排列。潘通說，數學家們正在運行一次大型電腦搜索，尋找 6 個元素的最短超排列。他說：“我們知道這次搜索將在有限的時間內完成，但是我們不知道那會是一星期還是一百萬年。沒有進度條。”
錯誤的次序
當休斯頓完成那項工作的時候，那篇匿名發布的 4chan 帖子已經在互聯網的角落裡安靜地待了近三年。其實在帖子發布幾天后，蒙特埃裡森大學（Mount Allison University）的一名數學家納撒尼爾·約翰斯頓（Nathaniel Johnston）就在另一個網站上看到了它的副本——他並不是沉迷動漫，只是在谷歌上搜索超排列相關的內容。
約翰斯頓讀了那條證明，覺得它看起來還靠譜，但他並沒有投入太多的精力去自習檢查。當時數學家認為對超排列的階乘計算很可能是對的，而當你自認為知道了一個問題的準確答案，那麽它的下界看起來就沒什麽意思了。換言之，超排列的研究進程也沒有遵守它的播放次序。
約翰斯頓後來在一兩個網站上看到了這個下界，他說：“我不認為有誰留意到這個證明。”
然後，到了今年的 9 月 26 日，加利福尼亞大學河濱分校（University of California, Riverside）的數學家約翰·巴耶茲（John Baez）在推特上發布了休斯頓 2014 年的發現，用來舉例介紹本以為顯而易見、實際上並不正確的數學規律。這條推特引起了科幻作家伊根的注意。伊根在幾十年前就讀於數學系，後來他成了一名屢屢獲獎的科幻小說家（有趣的是，他在 1994 年的突破性作品就叫《置換城市》（Permutation City）。）伊根在郵件中寫道：“我對數學的興趣從未減退。”
伊根想知道能否構建一個比休斯頓的答案更短的超排列。他閱讀了相關文獻，了解如何通過超排列網絡構建較短路線，在幾個星期後就找到了他需要的東西。在一兩天內，他算出了n 個元素的最短超排列的長度上界，就是 n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3。它和原先的階乘公式相似，但去掉了很多項。
休斯頓說：“這絕對打敗了先前的上界。”
與此同時，4chan 的匿名帖子計算的下界和新的上界極其接近，就是 n! + (n – 1)! + (n – 2)! + n – 3。當伊根的答案被公之於眾之後，約翰斯頓提醒其他的數學家關注匿名帖子中的證明，而休斯頓和潘通很快驗證它是正確的。和休斯頓的工作一樣，新的下界和上界都通過旅行推銷員問題實現了超排列：下界體現了必須經過的路費大於 1 美元的路線的最小數量，而上界計算出僅從路費為 1 美元和 2 美元的路線經過的方式，適用於不同的 n 值。
研究人員目前正在努力將上界和下界相結合，找出超排列問題的唯一解。巴耶茲預言：“也許人們終於要對這個問題蓋棺定論了。現在的形勢不錯。”
而對於涼宮春日的粉絲來說，伊根的計算給出了在僅僅 93,924,230,411 集中看完第一季所有可能順序的實用方式。粉絲們可以馬上開始努力觀看，或者再等等看數學家能不能把這個數字縮小一點。不過匿名網友計算的下界說明，最終波動範圍不太可能超過 4 千萬集。
香港九龍灣馬來街興發大廈15樓D室