離散數學走進舞台中央-科學人雜誌
不可勝數

離散數學走進舞台中央

2012-06-01 李國偉
2012年阿貝爾獎頒給了塞莫瑞迪,表彰他對離散數學與計算機科學的貢獻。


第10屆阿貝爾獎(Abel Prize)於5月22日頒給塞莫瑞迪(Endre Szemeredi),獎額約100萬美元。塞莫瑞迪是匈牙利科學院數學研究所的成員,也在美國路特格大學計算機科學系任教。挪威科學與人文學院的阿貝爾獎委員會讚揚他:「對於離散數學(discrete mathematics)與理論計算機科學做出基礎的貢獻,在加性數論(additive number theory)與遍歷理論(ergodic theory)上都產生深刻與長遠的影響。」


筆者曾在2008年5月號本專欄介紹過19世紀英年早逝的挪威大數學家阿貝爾,以及為紀念他而設的數學大獎,此次不再贅述。阿貝爾獎是以終生成就來評判是否可以獲獎,今年頒給離散數學大師塞莫瑞迪,代表離散數學已經從數學的邊緣地帶走入了舞台中央。


塞莫瑞迪在中學時雖然數學很好,但他不是那種解題快手,而是能見旁人所不及之處的深思者。中學畢業後他讀了一年醫學系,可是因為實在受不了解剖課的氣味,才徹底投入數學的懷抱。就像許多匈牙利的離散數學高手一樣,他也是因為艾狄胥(Paul Erdos)的導引,很快就做出了一流的數學成果。


塞莫瑞迪已經發表200多篇論文,涵蓋領域與影響範圍均十分驚人,但最膾炙人口的還是他1975年的成名之作。這個工作涉及所謂的算術數列(arithmetic progression),就是一串正整數,其中任何一對相鄰的數,都相差一個定數(稱之為公差)。譬如:3, 8, 13, 18, 23, 28是長度為6、公差為5的算術數列。但2, 5, 8, 10, 12就不是算術數列,因為相鄰項有的差2、有的差3。


著名的塞莫瑞迪定理的精髓,可用下面這種單人遊戲來說明。假如給你一個小數目(譬如6),又給你一個大數目(譬如18000),你的任務是從1到18000之間盡量多挑一些數字出來,但是要迴避出現長度為6的算術數列。你稍微想一想,就知道這個遊戲對你實在不利,因為不斷挑選數字,最終就把從1至18000之間所有數字都選出來,那時候長度為6的算術數列可就多得很了。其實不要走到這麼無聊的結局,你的直覺會告訴你,只要挑出來的數字佔總數相當高的比例,那麼間隔規律的算術數列就很可能會出現。


塞莫瑞迪定理的驚人之處在於,他發現不管你用多麼巧妙的策略迴避算術數列,在離挑選所有數字很遠很遠之前,算術數列就非出現不可了。說得明確些,給定正整數k,我們要從1到n中挑出數字,而S(k,n)代表在滿足不包含長度為k的算術數列條件下,所能挑選出的最多個數字。塞莫瑞迪定理說當n夠大時,S(k,n)與n相比非常地小。譬如說你雖然想迴避掉長度為23的算術數列,可是只要n足夠巨大,S(k,n)/n甚至只要超過0.1%,長度為23的算術數列便必然會出現,換句話說你的單人遊戲就敗局了。塞莫瑞迪1975年發表的論文屬於「初等證明」,也就是沒有用到其他高深的數學理論,但其艱難的程度幾乎達到邏輯推理的極致,當時甚少人能讀得懂。


塞莫瑞迪定理本身並不見得有多少直接應用,重要的是在他分析問題時,引進了一些非常深刻的剖析離散結構的觀點,對日後離散數學以及計算機算法分析產生本質的影響。


圖(graph)是最具代表性的離散結構,它用一些結點代表物件,有關係的物件則用線段連結起來。這種模式可用來描述各種類型的網路。塞莫瑞迪定理的核心思想,後來被汲取出來寫成著名的「塞莫瑞迪規則性引理」(Szemeredi Regularity Lemma):只要圖非常複雜,其內部就會出現非常像隨機的網路結構。如此機率與統計的方法就能運用到網路的分析上。在一個時時離不開網路的時代裡,你可以想像塞莫瑞迪開創的研究方向,會產生多麼廣泛的影響了。


# 關鍵字:名家專欄不可勝數
更多文章
活動推薦更多
追蹤科學人