《Quanta Magazine》量子雜志每周都會解釋推動現代研究的最重要思想之一。本周，資深數學作家Jordana Cepelewicz揭示了隨機性如何成為數學家最強大的工具之一。

作者：Jordana Cepelewicz 量子雜志作家 2024-6-10

譯者：zzllrr小樂（數學科普公眾號）2024-6-11

有時，一個想法的時機就會到來。1940年代末，隨機性可以成為一種強大工具的想法傳到了新澤西州。位于默里山的貝爾電話實驗室的電氣工程師克勞德·香農（Claude Shannon，1916 - 2001）使用隨機碼證明了在任意噪聲信道上傳輸信息是可能的。

Claude Shannon，1916 - 2001

在西南約 30 英里的IAS高等研究院工作的匈牙利數學家保羅·埃爾德什（Paul Erd?s，1913 - 1996）獨立地使用依賴于隨機性的論證證明了圖論的一個開創性結果。

Paul Erd?s，1913 - 1996

圖源：Mathigon

數學中的圖論涉及點的集合，其中一些點由線連接。埃爾德什證明，在足夠小的圖中，可以避免創建全部連通或全部不連通的點集（稱為團clique）。

在物理學中，隨機性的作用在上一代發生了深刻的變化，因為量子力學的發現表明宇宙本質上是隨機的。但是，盡管物理學家將隨機性視為一項需要克服的挑戰，但數學家和工程師卻想出了如何利用它的方法。正如牛津大學的拉胡爾·桑塔納姆（Rahul Santhanam）所解釋的那樣，隨機性幫助數學家解決問題的方式有些自相矛盾。

他們經常用它來證明給定的數學結構存在，但并不說明如何構建它。例如，埃爾德什對無團圖存在的證明并沒有說明如何構建它們。相反，他表明，如果你考慮給定大小的所有可能圖的集合，并隨機選擇一個，那么找到沒有“禁忌”團的圖的概率大于零。這意味著這樣的圖一定存在。

香農的成果開創了信息論這一學科，該學科探討在特定情況下理論上可以傳輸多少信息——盡管它不一定能說明最佳傳輸方式。與埃爾德什一樣，香農沒有具體說明如何創建一種在嘈雜信道上可靠傳輸的方案。但他利用隨機性證明了這種方式一定存在。

從那時起，數學家們不僅將隨機性作為一種工具應用于圖論和信息論，還將其應用于幾何學、分析學（一種高級形式的微積分）、組合學（計數方法的研究）和計算機科學。今年早些時候，高等研究院的Avi Wigderson 獲得了圖靈獎（參見 ），這是計算機科學領域的最高榮譽之一，部分原因是他研究了隨機性和計算之間的聯系。

圖源：Quanta Magazine

近年來，數學家們一直在探索概率方法的極限，并對其可能失敗的地方有了直覺。“試圖利用隨機性來推動事情發展是非常自然的，”一位數學家告訴我。然而，“隨機性只能讓你走這么遠。”

最新動態和值得關注的內容

盡管如此，它還是能讓你走得很遠。研究人員繼續追隨埃爾德什的腳步，利用隨機性證明了拉姆齊理論領域的許多結果，該理論研究的是圖中的團不可避免地形成。例如，在2020年，兩位數學家改進了圖必須達到多大才能不可避免地出現某些模式的數字下限。第二年，量子雜志報道了一個證明， 標志著在解決拉姆齊理論中最古老的問題之一方面取得了重大進展，該問題是關于無序字符串可以有多長。去年，我報道了另一個拉姆齊結果 （參見 ），其中隨機性至關重要。

概率方法也使得證明其他類型結構的存在成為可能。2017年，數學家將一個隨機過程堆疊在另一個隨機過程之上，結果發現在所有這些無序中出現了一致的幾何圖案。“無序會收斂到一種普遍形式，”凱文·哈特內特 （Kevin Hartnett）寫道。“當一個隨機系統看起來最混亂的時候，精致的幾何秩序就會顯現出來。”去年，我寫了一篇文章，介紹數學家如何使用概率方法來證明存在無數個被稱為子空間設計的配置——與糾錯碼相關的對象（參見 ）——“它們的存在根本不明顯”，一位數學家告訴我。

在所有這些工作中，數學家必須巧妙地運用隨機性。例如，在2022年，我報道了卡恩-卡萊猜想（Kahn-Kalai conjecture）的開創性證明（參見 ），這是一個主要問題，它詢問在圖和其他系統中何時發生相變。兩位數學家通過隨機選擇圖和集合的片段，直到逐漸建立起所需的結構，而不是一下子應用隨機性來給出答案。

隨機性似乎與數學所宣稱的一切完全相反——數學是堅定不移地追求邏輯，尋找模式和結構，提出簡潔無懈可擊的論據。然而，它卻成為數學最有用的工具之一。

網絡上的資料

• Noga Alon和Joel Spencer合著了《概率方法》一書（參見 ），介紹了隨機性作為組合學工具的開發和使用。這是該領域的標準參考書 https://maa.org/press/maa-reviews/the-probabilistic-method-0 。

• Slate有一本2022年的書摘，https://slate.com/technology/2022/06/bridle-ways-of-being-excerpt-computer-randomness.html 介紹了真正隨機的含義以及如何用機器產生隨機性。

• YouTube的Numberphile頻道有一個 2014年的視頻 https://www.youtube.com/watch?v=xdiL-ADRTxQ ，介紹了拉姆齊理論中的基本問題。

參考資料

https://mailchi.mp/quantamagazine.org/the-counterintuitive-power-of-randomness

https://maa.org/press/maa-reviews/the-probabilistic-method-0

https://slate.com/technology/2022/06/bridle-ways-of-being-excerpt-computer-randomness.html

https://www.youtube.com/watch?v=xdiL-ADRTxQ

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

右上角

數學科普不迷路！